.. _ch:periods: Computing Periods ================= .. chapter:: 10 .. index:: pair: newform; associated period map This chapter is about computing period maps associated to newforms. We assume you have read Chapters :ref:`ch:modsym` and :ref:`ch:modformcomp` and that you are familiar with abelian varieties at the level of :cite:`rosen:abvars`. In Section :ref:`sec:periodintro` we introduce the period map and give some examples of situations in which computing it is relevant. Section :ref:`sec:newformabvar` is about how to use the period mapping to attach an abelian variety to any newform. In Section :ref:`defn:extendedmodsyms`, we introduce extended modular symbols, which are the key computational tool for quickly computing periods of modular symbols. We turn to numerical computation of period integrals in Section :ref:`sec:numper`, and in Section :ref:`sec:wntrick` we explain how to use Atkin-Lehner operators to speed convergence. In Section :ref:`sec:computephi` we explain how to compute the full period map with a minimum amount of work. Section :ref:`sec:findall` briefly sketches three approaches to computing all elliptic curves of a given conductor. This chapter was inspired by :cite:`cremona:algs`, which contains similar algorithms in the special case of a newform `f=\sum a_n q^n \in S_2(\Gamma_0(N))` with `a_n\in\Z`. See also :cite:`dokchitser:lfun` for algorithmic methods to compute special values of very general `L`-functions, which can be used for approximating `L(f,s)` for arbitrary `s`. .. _sec:periodintro: The Period Map -------------- Let `\Gamma` be a subgroup of `\SL_2(\Z)` that contains `\Gamma_1(N)` for some `N`, and suppose .. math:: f =\sum_{n\geq 1} a_n q^n\in S_k(\Gamma) is a newform (see Definition :ref:`def:newform`). In this chapter we describe how to approximately compute the complex period mapping .. math:: \Phi_f : \sM_k(\Gamma) \to \C, given by .. math:: \Phi_f(P\{\alpha,\beta\}) = \langle f,\, P\{\alpha,\beta\} \rangle = \int_{\alpha}^{\beta} f(z) P(z,1) d z, as in Section :ref:`sec:pairing`. As an application, we can approximate the special values `L(f,j)`, for `j=1,2,\ldots, k-1` using :eq:`eqn:lfunc_ms`. We can also compute the period lattice attached to a modular abelian variety, which is an important step, e.g., in enumeration of `\Q`-curves (see, e.g., :cite:`gonz_lario_quer`) or computation of a curve whose Jacobian is a modular abelian variety `A_f` (see, e.g., :cite:`wang:factors`). .. _sec:newformabvar: Abelian Varieties Attached to Newforms -------------------------------------- Fix a newform `f\in S_k(\Gamma)`, where `\Gamma_1(N)\subset \Gamma` for some `N`. Let `f_1,\ldots, f_d` be the `\Gal(\Qbar/\Q)`-conjugates of `f`, where `\Gal(\Qbar/\Q)` acts via its action on the Fourier coefficients, which are algebraic integers (since they are the eigenvalues of matrices with integer entries). Let .. math:: :label: eqn:vf V_f = \C f_1 \oplus \cdots \oplus \C f_d \subset S_k(\Gamma) be the subspace of cusp forms spanned by the `\Gal(\Qbar/\Q)`-conjugates of `f`. One can show using the results discussed in Section :ref:`sec:ALL` that the above sum is direct, i.e., that `V_f` has dimension `d`. The integration pairing induces a `\T`-equivariant homomorphism .. math:: \Phi_f : \sM_k(\Gamma) \ra V_f^* = \Hom_\C(V_f,\C) from modular symbols to the `\C`-linear dual `V_f^*` of `V_f`. Here `\T` acts on `V_f^*` via `(\vphi t)(x) = \vphi(tx)`, and this homomorphism is `\T`-stable by :ref:`thm:tequivar`. The :defn:`abelian variety attached to $f$` is the quotient .. math:: A_f(\C) = V_f^*/\Phi_f(\sS_k(\Gamma;\Z)). Here `\sS_k(\Gamma;\Z)=\sS_k(\Gamma)`, and we include the `\Z` in the notation to emphasize that these are integral modular symbols. See :cite:`shimura:surles` for a proof that `A_f(\C)` is an abelian variety (in particular, `\Phi_f(\sS_k(\Gamma;\Z))` is a lattice, and `V_f^*` is equipped with a nondegenerate Riemann form). When `k=2`, we can also construct `A_f` as a quotient of the modular Jacobian `\Jac(X_\Gamma)`, so `A_f` is an abelian variety canonically defined over `\Q`. In general, we have an exact sequence .. math:: 0 \to \Ker(\Phi_f) \to \sS_k(\Gamma) \to V_f^* \to A_f(\C) \to 0. .. remark:: When `k=2`, the abelian variety `A_f` has a canonical structure of abelian variety over `\Q`. Moreover, there is a conjecture of Ribet and Serre in :cite:`ribet:abvars` that describes the simple abelian varieties `A` over `\Q` that should arise via this construction. In particular, the conjecture is that `A` is isogenous to some abelian variety `A_f` if and only if `\End(A/\Q)\tensor\Q` is a number field of degree `\dim(A)`. The abelian varieties `A_f` have this property since `\Q(\ldots, a_n(f),\ldots)` embeds in `\End(A/\Q)\tensor\Q` and the endomorphism ring over `\Q` has degree at most `\dim(A)` (see :cite:`ribet:abvars` for details). Ribet proves that his conjecture is a consequence of Serre's conjecture :cite:`serre:conjectures` on modularity of mod `p` odd irreducible Galois representations (see Section :ref:`sec:apps`). Much of Serre's conjecture has been proved by Khare and Wintenberger (not published). In particular, it is a theorem that if `A` is a simple abelian variety over `\Q` with `\End(A/\Q)\tensor\Q` a number field of degree `\dim(A)` and if `A` has good reduction at `2`, then `A` is isogenous to some abelian variety `A_f`. .. remark:: When `k>2`, there is an object called a :defn:`Grothendieck motive` that is attached to `f` and has a canonical "structure over `\Q` ". See :cite:`scholl:motivesinvent`. .. _defn:extendedmodsyms: Extended Modular Symbols ------------------------ In this section, we extend the notion of modular symbols to allows symbols of the form `P\{w,z\}` where `w` and `z` are arbitrary elements of `\h^*=\h\union\P^1(\Q)`. .. definition:: Extended Modular Symbols The abelian group \sym{\esM_k} of :defn:`extended modular symbols` of weight `k` is the `\Z`-span of symbols `P\{w,z\}`, with `P\in V_{k-2}` a homogeneous polynomial of degree `k-2` with integer coefficients, modulo the relations .. math:: P\cdot (\{w,y\} + \{y,z\} + \{z,w\}) = 0 and modulo any torsion. Fix a finite index subgroup `\Gamma\subset \SL_2(\Z)`. Just as for usual modular symbols, `\esM_k` is equipped with an action of `\Gamma`, and we define the space of :defn:`extended modular symbols` of weight `k` for `\Gamma` to be the quotient .. math:: \esM_k(\Gamma) = (\esM_k/\langle \gamma x - x : \gamma\in\Gamma, x \in \esM_k\rangle)/\tor. The quotient `\esM_k(\Gamma)` is torsion-free and fixed by `\Gamma`. The integration pairing extends naturally to a pairing .. math:: :label: eqn:extpair \left(S_k(\Gamma) \oplus \overline{S}_k(\Gamma)\right) \times \esM_k(\Gamma) \to \C, where we recall from :eq:`eqn:sbar` that `\overline{S}_k(\Gamma)` denotes the space of antiholomorphic cusp forms. Moreover, if .. math:: \iota: \sM_k(\Gamma)\rightarrow \esM_k(\Gamma) is the natural map, then `\iota` respects :eq:`eqn:extpair` in the sense that for all `f \in S_k(\Gamma) \oplus \overline{S}_k(\Gamma)` and `x\in \sM_k(\Gamma)`, we have .. math:: \langle f, x\rangle = \langle f , \iota(x)\rangle. As we will see soon, it is often useful to replace `x\in\sM_k(\Gamma)` first by `\iota(x)` and then by an equivalent sum `\sum y_i` of symbols `y_i\in \esM_k(N,\eps)` such that `\langle f, \sum y_i \rangle` is easier to compute numerically than `\langle f, x\rangle`. Let `\eps` be a Dirichlet character of modulus `N`. If `\gamma=\abcd{a}{b}{c}{d} \in \SL_2(\Z)`, let `\eps(\gamma)=\eps(d)`.\index{`\eps(\gamma)`} Let \sym{\esM_k(N,\eps)} be the quotient of `\esM_k(N,\Z[\eps])` by the relations `\gamma(x) - \eps(\gamma) x`, for all `x \in \sM_k(N,\Z[\eps])`, `\gamma \in \Gamma_0(N)`, and modulo any torsion. .. _sec:numper: Approximating Period Integrals ------------------------------ In this section we assume `\Gamma` is a congruence subgroup of `\SL_2(\Z)` that contains `\Gamma_1(N)` for some `N`. Suppose `\alp\in \h`, so `\Im(\alpha)>0` and `m` is an integer such that `0\leq m\leq k-2`, and consider the extended modular symbol `X^mY^{k-2-m}\{\alp,\infty\}`. Let `\langle \cdot, \cdot \rangle` denote the integration pairing from Section :ref:`sec:pairing`. Given an arbitrary cusp form `f =\sum_{n=1}^{\infty} a_n q^n\in S_k(\Gamma)`, we have .. math:: \Phi_f(X^mY^{k-2-m}\{\alpha,\infty\}) &= \left\langle f, \, X^mY^{k-2-m}\{\alpha,\infty\}\right\rangle \\ &= \int_{\alpha}^{\infty} f(z)z^m dz \\ &= \sum_{n=1}^{\oo} a_n \int_{\alpha}^{\infty} e^{2\pi i n z} z^m dz. \label{eqn:intsum} The reversal of summation and integration is justified because the imaginary part of `\alp` is positive so that the sum converges absolutely. The following lemma is useful for computing the above infinite sum. .. lemma:: :label: lem:intexp .. math:: :label: intexp \int_{\alpha}^{\infty} e^{2\pi i n z} z^m dz \,\,=\,\, e^{2\pi i n \alpha} \sum_{s=0}^m \left( \frac{(-1)^s \alpha^{m-s}} {(2\pi i n)^{s+1}} \prod_{j=(m+1)-s}^m j\right). .. proof:: See :ref:`ex:intexp` In practice we will usually be interested in computing the period map `\Phi_f` when `f \in S_k(\Gamma)` is a newform. Since `f` is a newform, there is a Dirichlet character `\eps` such that `f \in S_k(N,\eps)`. The period map `\Phi_f : \sM_k(\Gamma) \to \C` then factors through the quotient `\sM_k(N,\eps)`, so it suffices to compute the period map on modular symbols in `\sM_k(N,\eps)`. The following proposition is an analogue of :cite:`[Prop. 2.1.1(5)]{cremona:algs}`. .. proposition:: :label: modsym-errorterm For any `\gamma\in \Gamma_0(N)`, `P\in V_{k-2}` and `\alp\in\h^*`, we have the following relation in `\esM_k(N,\eps)`: .. math:: :nowrap: \begin{eqnarray*} P\{\oo, \gamma(\oo)\} &=& P\{\alp,\gamma(\alp)\} + (P - \eps(\gamma)\gamma^{-1}P)\{\oo,\alp\}\\ &=& \eps(\gamma)(\gamma^{-1}P)\{\alp, \oo\} - P\{\gamma(\alp),\oo\}. \end{eqnarray*} .. proof:: By definition, if `x\in\sM_k(N,\eps)` is a modular symbol and `\gamma\in\Gamma_0(N)`, then `\gamma{}x=\eps(\gamma)x`. Thus `\eps(\gamma)\gamma^{-1}x=x`, so .. math:: :nowrap: \begin{eqnarray*} P\{\oo, \gamma(\oo)\} &=& P\{\oo,\alp\} + P\{\alp,\gamma(\alp)\} + P\{\gamma(\alp),\gamma(\oo)\}\\ &=& P\{\oo,\alp\} + P\{\alp,\gamma(\alp)\} + \eps(\gamma)\gamma^{-1}(P\{\gamma(\alp),\gamma(\oo)\})\\ &=& P\{\oo,\alp\} + P\{\alp,\gamma(\alp)\} + \eps(\gamma)(\gamma^{-1}P)\{\alp, \oo\}\\ &=& P\{\alp,\gamma(\alp)\} + P\{\oo,\alp\} - \eps(\gamma)(\gamma^{-1}P)\{\oo, \alp\}\\ &=& P\{\alp,\gamma(\alp)\} + (P - \eps(\gamma)\gamma^{-1}P)\{\oo,\alp\}. \end{eqnarray*} The second equality in the statement of the proposition now follows easily. In the case of weight `2` and trivial character, the "error term" .. math:: :label: eqn:erroreqn (P - \eps(\gamma)\gamma^{-1}P)\{\oo,\alp\} vanishes since `P` is constant and `\eps(\gamma)=1`. In general this term does not vanish. However, we can suitably modify the formulas found in :cite:`[2.10]{cremona:algs}` and still obtain an algorithm for computing period integrals. .. algorithm:: Period Integrals Given `\gamma\in\Gamma_0(N)`, `P\in V_{k-2}` and `f\in S_k(N,\eps)` presented as a `q`-expansion to some precision, this algorithm outputs an approximation to the period integral `\langle f, \,P\{\oo, \gamma(\oo)\}\rangle`. 1. Write `\gamma=\abcd{\hfill a}{b}{cN}{d}\in\gzero`, with `a,b,c,d\in\Z`, and set `\alpha = \frac{-d+i}{cN}` in Proposition :ref:`modsym-errorterm`. 2. Replacing `\gamma` by `-\gamma` if necessary, we find that the imaginary parts of `\alpha` and `\gamma(\alpha)=\frac{a+i}{cN}` are both equal to the positive number `\frac{1}{cN}`. 3. Use :eq:`eqn:intsum` and :ref:`lem:intexp` to compute the integrals that appear in Proposition :ref:`modsym-errorterm`. It would be nice if the modular symbols of the form `P\{\oo,\gamma(\oo)\}` for `P\in V_{k-2}` and `\gamma\in \Gamma_0(N)` were to generate a large subspace of `\sM_k(N,\eps)\tensor\Q`. When `k=2` and `\eps=1`, Manin proved in :cite:`manin:parabolic` that the map `\Gamma_0(N)\ra H_1(X_0(N),\Z)` sending `\gamma` to `\{0,\gamma(0)\}` is a surjective group homomorphism. When `k>2`, the author does not know a similar group-theoretic statement. However, we have the following theorem. .. theorem:: :label: onlyoo Any element of `\sS_k(N,\eps)` can be written in the form .. math:: \sum_{i=1}^n P_{i}\{\infty,\gamma_i(\infty)\} for some `P_i\in V_{k-2}` and `\gamma_i\in\gzero.` Moreover, `P_i` and `\gamma_i` can be chosen so that `\sum P_i = \sum \eps(\gamma_i)\gamma_i^{-1}(P_i)`, so the error term :eq:`eqn:erroreqn` vanishes. .. figure:: :label: fig:trans "Transporting" a transportable modular symbol. :: \begin{figure} \begin{center} \begin{picture}(230,150)(0,0) \put(-10,10){\line(1,0){200}} \put(10,10){\circle*{3}} \put(10,0){`\infty`} \qbezier(10,10)(50,40)(75,10) \put(49,25){\vector(1,0){1}} \put(45,28){`P`} \put(75,10){\circle*{3}} \put(75,0){`\gamma \infty`} \qbezier(75,10)(130,50)(140,10) \put(120,30){\vector(1,0){1}} \put(115,34){`Q`} \put(140,10){\circle*{3}} \put(140,0){`\beta \infty`} \put(20,90){\circle*{3}} \put(17,96){`\alpha`} \qbezier(20,90)(50,120)(55,60) \put(40,100){\vector(1,0){1}} \put(40,104){`P`} \put(55,60){\circle*{3}} \put(60,54){`\gamma \alpha`} \qbezier(55,60)(70,180)(100,140) \put(87,150){\vector(1,0){1}} \put(85,154){`Q`} \put(100,140){\circle*{3}} \put(100,146){`\beta \alpha`} \comment{ \qbezier(10,10)(-10,30)(10,50) \qbezier(10,50)(40,70)(20,90) \put(5,45){\vector(2,3){1}} \qbezier(75,10)(90,30)(75,40) \qbezier(75,40)(60,50)(55,60) \put(69,45){\vector(1,-1){1}} \put(80,35){\vector(-1,2){1}} \qbezier(140,10)(160,30)(140,50) \qbezier(140,50)(90,80)(110,90) \qbezier(110,90)(130,100)(100,120) \qbezier(100,120)(90,130)(100,140) \put(110,90){\vector(-1,-1){1}} } \put(100,50){\vector(-1,4){10}} \put(50,40){\vector(-1,4){10}} \put(140,155){\parbox[t][4in][l]{2in} { The modular symbol .. math:: P\{\infty ,\gamma \infty \}+Q\{\gamma \infty ,\beta \infty \} .. math:: \hspace{2em}=P\{\infty ,\gamma \infty \}+Q\{\infty ,\beta \infty \}-Q\{\infty ,\gamma \infty \} can be "transported" to .. math:: P\{\alpha,\gamma \alpha\}+Q\{\gamma \alpha,\beta \alpha\}, provided that .. math:: P\,+\,Q\,-\,Q=\gamma ^{-1}P\,+\,\beta ^{-1}Q\,-\,\gamma ^{-1}Q. The author and Helena Verrill prove this theorem in :cite:`stein-verrill:transportable`. The condition that the error term vanishes means that one can replace `\infty` by any `\alpha` in the expression for the modular symbol and obtain an equivalent modular symbol. For this reason, we call such modular symbols :defn:`transportable`, as illustrated in :ref:`fig:trans`. Note that in general not every element of the form `P\{\oo,\gamma(\oo)\}` must lie in `\sS_k(N,\eps)`. However, if `\gamma P = P`, then `P\{\oo,\gamma(\oo)\}` does lie in `\sS_k(N,\eps)`. It would be interesting to know under what circumstances `\sS_k(N,\eps)` is generated by symbols of the form `P\{\oo,\gamma(\oo)\}` with `\gamma P = P`. This sometimes fails for `k` odd; for example, when `k=3`, the condition `\gamma P = P` implies that `\gamma\in\gzero` has an eigenvector with eigenvalue `1`, and hence is of finite order. When `k` is even, the author can see no obstruction to generating `\sS_k(N,\eps)` using such symbols. .. _sec:wntrick: Speeding Convergence Using Atkin-Lehner --------------------------------------- Let `w_N = \abcd{0}{-1}{N}{\hfill 0} \in \Mat_2(\Z)`. Consider the Atkin-Lehner involution `W_N` on `M_k(\Gamma_1(N))`, which is defined by .. math:: W_N(f) &= N^{(2-k)/2} \cdot f|_{[w_N]_k}\\ &= N^{(2-k)/2} \cdot f\left(-\frac{1}{Nz}\right) \cdot N^{k-1} \cdot (Nz)^{-k}\\ &= N^{-k/2} \cdot z^{-k} \cdot f\left(-\frac{1}{Nz}\right). Here we take the positive square root if `k` is odd. Then `W_N^2 = (-1)^k` is an involution when `k` is even. There is an operator on modular symbols, which we also denote `W_N`, which is given by .. math:: W_N(P \{\alpha, \beta\}) &= N^{(2-k)/2} \cdot w_N(P) \{w_N(\alpha), w_N(\beta)\}\\ &=N^{(2-k)/2} \cdot P(-Y,NX) \left\{-\frac{1}{\alpha N}, -\frac{1}{\beta N}\right\}, and one has that if `f \in S_k(\Gamma_1(N))` and `x\in\sM_k(\Gamma_1(N))`, then .. math:: \langle W_N(f), x\rangle = \langle f, W_N(x) \rangle. If `\eps` is a Dirichlet character of modulus `N`, then the operator `W_N` sends `S_k(N,\eps)` to `S_k(\Gamma_1(N),\overline{\eps})`. Thus if `\eps^2=1`, then `W_N` preserves `S_k(N,\eps)`. In particular, `W_N` acts on `S_k(\Gamma_0(N))`. The next proposition shows how to compute the pairing `\langle f, P\{\oo,\gamma(\oo)\} \rangle` under certain restrictive assumptions. It generalizes a result of :cite:`cremona:periods` to higher weight. .. (Compare also :cite:`goldfeld:complexity`.) .. proposition:: :label: wntrick Let `f \in S_k(N,\eps)` be a cusp form which is an eigenform for the Atkin-Lehner operator `W_N` having eigenvalue `w\in \{\pm 1\}` (thus `\eps^2=1` and `k` is even). Then for any `\gamma\in\Gamma_0(N)` and any `P\in V_{k-2}`, with the property that `\gamma P = \eps(\gamma)P`, we have the following formula, valid for any `\alpha\in\h`: .. math:: \langle f, P\{\oo,\gamma(\oo)\}\rangle &= \Bigl\langle f, \quad w \frac{P(Y,-NX)}{N^{k/2-1}}\{w_N(\alp),\oo\}\\ &\quad + \left(P - w \frac{P(Y,-NX)}{N^{k/2-1}} \right)\left\{i/\sqrt{N},\oo\right\} -P\left\{\gamma(\alp),\oo\right\} \Bigr\rangle. Here `\ds w_N(\alpha) = -\frac{1}{N\alpha}`. .. proof:: By Proposition :ref:`modsym-errorterm` our condition on `P` implies that `P\{\oo,\gamma(\oo)\}= P\{\alp,\gamma(\alp)\}`. We describe the steps of the following computation below. .. math:: &\Bigl\langle f,\quad P\{\alp,\gamma(\alp)\}\Bigr\rangle \\ &=\left\langle f,\quad\!\! P\{\alp,i/\sqrt{N}\} + P\{i/\sqrt{N},W(\alp)\}+P\{W(\alp),\gamma(\alp)\} \right\rangle \\ &=\left\langle f,\quad\!\! w \frac{W(P)}{N^{k/2-1}} \{W(\alp),i/\sqrt{N}\} + P\{i/\sqrt{N},W(\alp)\}+P\{W(\alp),\gamma(\alp)\} \right\rangle. For the first equality, we break the path into three paths, and in the second, we apply the `W`-involution to the first term and use that the action of `W` is compatible with the pairing `\langle \,,\, \rangle` and that `f` is an eigenvector with eigenvalue `w`. In the following sequence of equalities we combine the first two terms and break up the third; then we replace `\{ W(\alp), i/\sqrt{N}\}` by `\{W(\alp),\infty\}+\{\infty,i/\sqrt{N}\}` and regroup: .. math:: &w \frac{W(P)}{N^{k/2-1}} \{W(\alp),i/\sqrt{N}\} + P\{i/\sqrt{N},W(\alp)\}+P\{W(\alp),\gamma(\alp)\}\\ &= \left(w \frac{W(P)}{N^{k/2-1}}-P\right) \{W(\alp),i/\sqrt{N}\} +P\{W(\alp),\oo\} - P\{\gamma(\alp),\oo\}\\ &= w \frac{W(P)}{N^{k/2-1}}\{W(\alp),\oo\} +\left(P - w \frac{W(P)}{N^{k/2-1}}\right)\{i/\sqrt{N},\oo\} -P\{\gamma(\alp),\oo\}. A good choice for `\alp` is `\alp=\gamma^{-1}\left(\frac{b}{d}+\frac{i}{d\sqrt{N}}\right)`, so that `W(\alp) = \frac{c}{d}+\frac{i}{d\sqrt{N}}`. This maximizes the minimum of the imaginary parts of `\alp` and `W(\alp)`, which results in series that converge more quickly. Let `\gamma=\abcd{a}{b}{c}{d}\in \Gamma_0(N)`. The polynomial .. math:: P(X,Y) = (cX^2 + (d-a)XY - bY^2)^{\frac{k-2}{2}} satisfies `\gamma(P)=P`. We obtained this formula by viewing `V_{k-2}` as the `(k-2)^{th}` symmetric product of the `2`-dimensional space on which `\gzero` acts naturally. For example, observe that since `\det(\gamma)=1`, the symmetric product of two eigenvectors for `\gamma` is an eigenvector in `V_{2}` having eigenvalue `1`. For the same reason, if `\eps(\gamma)\neq 1`, there need not be a polynomial `P(X,Y)` such that `\gamma(P)=\eps(\gamma) P`. One remedy is to choose another `\gamma` so that `\eps(\gamma)=1`. Since the imaginary parts of the terms `i/\sqrt{N}`, `\alp` and `W(\alp)` in the proposition are all relatively large, the sums appearing at the beginning of Section :ref:`sec:numper` converge quickly if `d` is small. It is *important* to choose `\gamma` in Proposition :ref:`wntrick` with `d` small; otherwise the series will converge very slowly. .. remark:: Is there a generalization of Proposition :ref:`wntrick` without the restrictions that `\eps^2=1` and `k` is even? Another Atkin-Lehner Trick ~~~~~~~~~~~~~~~~~~~~~~~~~~ Suppose `E` is an elliptic curve and let `L(E,s)` be the corresponding `L`-function. Let `\eps\in\{\pm 1\}` be the root number of `E`, i.e., the sign of the functional equation for `L(E,s)`, so `\Lambda(E,s) =\eps\Lambda(E,2-s)`, where `\Lambda(E,s) = N^{s/2} (2\pi)^{-s}\Gamma(s) L(E,s)`. Let `f=f_E` be the modular form associated to `E` (which exists by :cite:`wiles:fermat, breuil-conrad-diamond-taylor`). If `W_N(f) = w f`, then `\eps = -w` (see :ref:`ex:funceqn`). We have .. math:: L(E,1) &= -2\pi \int_{0}^{\infty} f(z)\, dz \\ &= -2\pi i \, \left\langle f,\, \{0,\infty\}\right\rangle\\ &=-2\pi i\, \left\langle f, \{0,i/\sqrt{N}\} + \{i/\sqrt{N}, \infty\}\right\rangle\\ &=-2\pi i\, \left\langle wf, \{w_N(0), w_N(i/\sqrt{N})\} + \{i/\sqrt{N}, \infty\}\right\rangle\\ &=-2\pi i\, \left\langle wf, \{\infty , i/\sqrt{N}\} + \{i/\sqrt{N}, \infty\}\right\rangle\\ &=-2\pi i\, (w-1) \left\langle f, \{\infty , i/\sqrt{N}\} \right\rangle.\\ If `w=1`, then `L(E,1)=0`. If `w= -1`, then .. math:: :label: eqn:lone L(E,1) = 4\pi i \left\langle f, \{\infty , i/\sqrt{N}\} \right\rangle = 2 \sum_{n=1}^{\infty} \frac{a_n}{n} e^{-2\pi n/\sqrt{N}}. For more about computing with `L`-functions of elliptic curves, including a trick for computing `\eps` quickly without directly computing `W_N`, see :cite:`[\S7.5]{cohen:course_ant}` and :cite:`[\S2.11]{cremona:algs}`. One can also find higher derivatives `L^{(r)}(E,1)` by a formula similar to :eq:`eqn:lone` (see :cite:`[\S2.13]{cremona:algs}`). The methods in this chapter for obtaining rapidly converging series are not just of computational interest; see, e.g., :cite:`greenberg:bsd` for a nontrivial theoretical application to the Birch and Swinnerton-Dyer conjecture. .. _sec:computephi: Computing the Period Mapping ---------------------------- .. index:: pair: period mapping; computation of Fix a newform `f=\sum a_nq^n\in S_k(\Gamma)`, where `\Gamma_1(N)\subset \Gamma` for some `N`. Let `V_f` be as in :eq:`eqn:vf`. Let `\Theta_f:M_k(\Gamma;\Q) \to V` be *any* `\Q`-linear map with the same kernel as `\Phi_f`; we call any such map a :defn:`rational period mapping` associated to `f`. Let `\Phi_f` be the period mapping associated to the `\Gal(\Qbar/\Q)`-conjugates of `f`. We have a commutative diagram .. math:: \xymatrix{ {\sM_k(\Gamma;\Q)}\ar[dr]_{\Theta_f}\ar[rr]^{\Phi_f} & & \Hom_\C(V_f,\C) \\ & V\ar@{^(->}[ur]^{i_f} } Recall from Section :ref:`sec:newformabvar` that the cokernel of `\Phi_f` is the abelian variety `A_f(\C)`. The Hecke algebra `\T` acts on the linear dual .. math:: \sM_k(\Gamma;\Q)^* = \Hom (\sM_k(\Gamma), \Q) by `(t \vphi)(x) = \vphi(tx)`. Let `I=I_f\subset \T` be the kernel of the ring homomorphism `\T\ra \Z[a_2, a_3, \ldots]` that sends `T_n` to `a_n`. Let .. math:: \sM_k(\Gamma;\Q)^*[I] = \{\vphi \in \sM_k(\Gamma;\Q)^* : t \vphi = 0 \text{ all }t \in I\}. Since `f` is a newform, one can show that `\sM_k(\Gamma;\Q)^*[I]` has dimension `d`. Let `\theta_1, \ldots, \theta_d` be a basis for `\sM_k(\Gamma;\Q)^*[I]`, so .. math:: \Ker(\Phi_f) = \Ker(\theta_1) \oplus \cdots \oplus \Ker(\theta_d). We can thus compute `\Ker(\Phi_f)`, hence a choice of `\Theta_f`. To compute `\Phi_f`, it remains to compute `i_f`. Let `S_k(\Gamma;\Q)` denote the space of cusp forms with `q`-expansion in `\Q[[q]]`. By :ref:`ex:qvs` .. math:: S_k(\Gamma; \Q)[I] = S_k(\Gamma)[I] \cap \Q[[q]] is a `\Q`-vector space of dimension `d`. Let `g_1,\ldots,g_d` be a basis for this `\Q`-vector space. We will compute `\Phi_f` with respect to the basis of `\Hom_\Q(S_k(\Gamma;\Q)[I];\C)` dual to this basis. Choose elements `x_1,\ldots,x_d\in \sM_k(\Gamma)` with the following properties: 1. Using Proposition :ref:`modsym-errorterm` or Proposition :ref:`wntrick`, it is possible to compute the period integrals `\langle g_i, x_j \rangle`, `i,j\in\{1,\ldots, d\}`, efficiently. 2. The `2d` elements `v+\eta(v)` and `v-\eta(v)` for `v=\Theta_f(x_1),\ldots,\Theta_f(x_d)` span a space of dimension `2d` (i.e., they span `\sM_k(\Gamma)/\Ker(\Phi_f)`). Given this data, we can compute .. math:: i_f (v+\eta(v)) = 2\Re(\langle g_1, x_i\rangle, \ldots, \langle g_d, x_i\rangle) and .. math:: i_f(v-\eta(v)) = 2i\Im(\langle g_1, x_i\rangle, \ldots, \langle g_d, x_i\rangle). We break the integrals into real and imaginary parts because this increases the precision of our answers. Since the vectors `v_n+\eta(v_n)` and `v_n-\eta(v_n)`, `n=1,\ldots,d`, span `\sM_k(N,\eps;\Q)/\Ker(\Phi_f)`, we have computed `i_f`. .. remark:: We want to find symbols `x_i` satisfying the conditions of Proposition :ref:`wntrick`. This is usually possible when `d` is very small, but in practice it is difficult when `d` is large. .. remark:: The above strategy was motivated by :cite:`[\S2.10]{cremona:algs}`. .. _sec:findall: All Elliptic Curves of Given Conductor -------------------------------------- Using modular symbols and the period map, we can compute all elliptic curves over `\Q` of conductor `N`, up to isogeny. The algorithm in this section gives all :defn:`modular elliptic curves` (up to isogeny), i.e., elliptic curves attached to modular forms, of conductor `N`. Fortunately, it is now known by :cite:`wiles:fermat, breuil-conrad-diamond-taylor, taylor-wiles:fermat` that every elliptic curve over `\Q` is modular, so the procedure of this section gives all elliptic curves (up to isogeny) of given conductor. See :cite:`cremona:history` for a nice historical discussion of this problem. .. algorithm:: Elliptic Curves of Conductor `N` Given `N> 0`, this algorithm outputs equations for all elliptic curves of conductor `N`, up to isogeny. 1. [Modular Symbols] Compute `\sM_2(\Gamma_0(N))` using Section :ref:`sec:compg0n`. .. _step:rateigen: 2. [Find Rational Eigenspaces] Find the `2`-dimensional eigenspaces `V` in `\sM_2(\Gamma_0(N))_{\new}` that correspond to elliptic curves. Do *not* use the algorithm for decomposition from Section :ref:`sec:decompmodsym`, which is too complicated and gives more information than we need. Instead, for the first few primes `p\nmid N`, compute all eigenspaces `\Ker(T_p - a)`, where `a` runs through integers with `-2\sqrt{p} < a < 2\sqrt{p}`. Intersect these eigenspaces to find the eigenspaces that correspond to elliptic curves. To find just the new ones, either compute the degeneracy maps to lower level or find all the rational eigenspaces of all levels that strictly divide `N` and exclude them. .. _step:ratnew: 3. [Find Newforms] Use :ref:`alg:eigsys` to compute to some precision each newform `f=\sum_{n=1}^{\infty} a_n q^n \in \Z[[q]]` associated to each eigenspace `V` found in step :ref:`(2) `. 4. [Find Each Curve] For each newform `f` found in step :ref:`(3) `, do the following: a. [Period Lattice] Compute the corresponding period lattice `\Lambda=\Z\omega_1 + \Z\omega_2` by computing the image of `\Phi_f`, as described in Section :ref:`sec:computephi`. .. _step:tau: b. [Compute `\tau`] Let `\tau=\omega_1/\omega_2`. If `\Im(\tau)<0`, swap `\omega_1` and `\omega_2`, so `\Im(\tau)>0`. By successively applying generators of `\SL_2(\Z)`, we find an `\SL_2(\Z)` equivalent element `\tau'` in `\cF`, i.e., `|\Re(\tau')|\leq 1/2` and `|\tau|\geq 1`. c. [`c`-invariants] Compute the invariants `c_4` and `c_6` of the lattice `\Lambda` using the following rapidly convergent series: .. math:: c_4 &= \left(\frac{2\pi}{\omega_2}\right)^4 \cdot \left(1+240\sum_{n=1}^{\infty}\frac{n^3q^n}{1-q^n}\right),\\ c_6 &= \left(\frac{2\pi}{\omega_2}\right)^6 \cdot \left(1-504\sum_{n=1}^{\infty}\frac{n^5q^n}{1-q^n}\right), where `q=e^{2\pi i \tau'}`, where `\tau'` is as in step :ref:`(b) `. A theorem of Edixhoven (that the Manin constant is an integer) implies that the invariants `c_4` and `c_6` of `\Lambda` are integers, so it is only necessary to compute `\Lambda` to large precision to completely determine them. d. [Elliptic Curve] An elliptic curve with invariants `c_4` and `c_6` is .. math:: E: \quad y^2 = x^3 -\frac{c_4}{48}x -\frac{c_6}{864}. .. _step:correct: e. [Prove Correctness] Using Tate's algorithm, find the conductor of `E`. If the conductor is not `N`, then recompute `c_4` and `c_6` using more terms of `f` and real numbers to larger precision, etc. If the conductor is `N`, compute the coefficients `b_p` of the modular form `g=g_E` attached to the elliptic curve `E`, for `p\leq \#\P^1(\Z/N\Z)/6`. Verify that `a_p = b_p`, where `a_p` are the coefficients of `f`. If this equality holds, then `E` must be isogenous to the elliptic curve attached to `f`, by the Sturm bound (:ref:`thm:sturm`) and Faltings's isogeny theorem. If the equality fails for some `p`, recompute `c_4` and `c_6` to larger precision. There are numerous tricks to optimize the above algorithm. For example, often one can work separately with `\sM_k(\Gamma_0(N))_{\new}^+` and `\sM_k(\Gamma_0(N))_{\new}^-` and get enough information to find `E`, up to isogeny (see :cite:`cremona:periods`). Once we have one curve from each isogeny class of curves of conductor `N`, we find each curve in each isogeny class (which is another interesting problem discussed in :cite:`cremona:algs`), hence all curves of conductor `N`. If `E/\Q` is an elliptic curve, then any curve isogenous to `E` is isogenous via a chain of isogenies of prime degree. There is an *a priori* bound on the degrees of these isogenies due to Mazur. Also, there are various methods for finding all isogenies of a given degree with domain `E`. See :cite:`[\S3.8]{cremona:algs}` for more details. Finding Curves: `S`-Integral Points ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ In this section we briefly survey an alternative approach to finding curves of a given conductor by finding integral points on other elliptic curves. Cremona and others have developed a complementary approach to the problem of computing all elliptic curves of given conductor (see :cite:`cremona-lingham`). Instead of computing all curves of given conductor, we instead consider the seemingly more difficult problem of finding all curves with good reduction outside a finite set `S` of primes. Since one can compute the conductor of a curve using Tate's algorithm :cite:`[\S3.2]{tate:antwerpiv, cremona:algs}`, if we know all curves with good reduction outside `S`, we can find all curves of conductor `N` by letting `S` be the set of prime divisors of `N`. There is a strategy for finding all curves with good reduction outside `S`. It is not an algorithm, in the sense that it is always guaranteed to terminate (the modular symbols method above *is* an algorithm), but in practice it often works. Also, this strategy makes sense over any number field, whereas the modular symbols method does not (there are generalizations of modular symbols to other number fields). Fix a finite set `S` of primes of a number field `K`. It is a theorem of Shafarevich that there are only finitely many elliptic curves with good reduction outside `S` (see :cite:`[Section~IX.6]{silverman:aec}`). His proof uses that the group of `S`-units in `K` is finite and Siegel's theorem that there are only finitely many `S`-integral points on an elliptic curve. One can make all this explicit, and sometimes in practice one can compute all these `S`-integral points. The problem of finding all elliptic curves with good reduction outside of `S` can be broken into several subproblems, the main ones being 1. determine the following finite subgroup of `K^*/(K^*)^m`: .. math:: K(S,m) = \{x \in K^*/(K^*)^m \, : \, m \mid \ord_\p(x) \text{ all } \p\not\in S\}; 2. find all `S`-integral points on certain elliptic curves `y^2=x^3 + k`. In :cite:`cremona-lingham`, there is one example, where they find all curves of conductor `N=2^8\cdot 17^2 = 73984` by finding all curves with good reduction outside `\{2, 17\}`. They finds `32` curves of conductor `73984` that divide into `16` isogeny classes. (Note that `\dim S_2(\Gamma_0(N)) = 9577`.) Finding Curves: Enumeration ~~~~~~~~~~~~~~~~~~~~~~~~~~~ One can also find curves by simply enumerating Weierstrass equations. For example, the paper :cite:`stein-watkins:ants5` discusses a database that the author and Watkins created that contains hundreds of millions of elliptic curves. It was constructed by enumerating Weierstrass equations of a certain form. This database does not contain *every* curve of each conductor included in the database. It is, however, fairly complete in some cases. For example, using the Mestre method of graphs :cite:`mestre:graphs`, we verified in :cite:`rank4` that the database contains all elliptic curve of prime conductor `< 234446`, which implies that the smallest conductor rank `4` curve is composite. Exercises --------- .. exercise:: :label: ex:intexp Prove :ref:`lem:intexp`. .. exercise:: :label: ex:funceqn Suppose `f \in S_2(\Gamma_0(N))` is a newform and that `W_N(f) = w f`. Let `\Lambda(E,s) = N^{s/2} (2\pi)^{-s} \Gamma(s) L(E,s)`. Prove that .. math:: \Lambda(E,s) = -w \Lambda(E,2-s). [Hint: Show that `\Lambda(f,s) = \int_{0,\infty} f(iy/\sqrt{N})y^{s-1}\, dy`. Then substitute `1/y` for `y`.] .. exercise:: :label: ex:qvs Let `f=\sum a_n q^n \in \C[[q]]` be a power series whose coefficients `a_n` together generate a number field `K` of degree `d` over `\Q`. Let `V_f` be the complex vector space spanned by the `\Gal(\Qbar/\Q)`-conjugates of `f`. a. Give an example to show that `V_f` need not have dimension `d`. b. Suppose `V_f` has dimension `d`. Prove that `V_f \cap \Q[[q]]` is a `\Q`-vector space of dimension `d`. .. exercise:: :label: ex:11 Find an elliptic curve of conductor `11` using Section :ref:`sec:findall`.