MODULAR SYMBOLS AND THE COMPUTATION OF MODULAR ELLIPTIC CURVES

J.E.CREMONA

1 Introduction 2

2 Modular curves and homology 2 2.1 The upper half-plane, the modular group and cusp forms 2 2.2 The duality between cusp forms and homology 4 2.3 Real structure 6 2.4 Modular symbol formalism 7 2.5 Rational Structure and the Manin-Drinfeld Theorem 8 2.6 Triangulations and homology 9

3 M-symbols and Γ_{0}(N) 11

4 Hecke operators 13

5 Rational newforms and modular elliptic curves 14 5.1 Rational newforms 14 5.2 Fourier coefficients and L-series 14 5.3 The ratio L(f, 1)/Ω(f) 15 5.4 Finding newforms 16

6 Analytic formulas 18 6.1 Computing L(f, 1) and L(f ⊗ χ, 1) 18 6.2 Computing L^{(r)}(f, 1) for r ≥ 1 19 6.3 Computing periods directly 20

7 From newform to lattice to curve 20 7.1 Finding the period lattice 20 7.2 Finding the equation of the curve 23

8 Worked example: N = 11 24

9 Results for N ≤ 5077 29

10 Further applications of the method 30

References 30

1. Introduction

Modular symbols are used to compute the homology of certain manifiolds which arise in number theory, related to modular forms and elliptic curves. The idea originated with Birch, but Manin was the first to develop them systematically. Now they occur in many different guises, from the relatively concrete to the relatively abstract: for example, they are also used in K-theory.

In these lecture notes we will show how modular symbols may be used in the computation of certain modular forms, and hence modular elliptic curves (over the rationals ℚ). Everything here will be completely explicit; the methods have all been implemented by the author as a set of programs (in C++) which will, in principle, output for any given positive integer N, a complete set of elliptic curves over ℚ of conductor N, up to isogeny.

It is impractical to make these notes completely self-contained. Prerequisite background knowledge expected of the reader consists of: basic theory of holomorphic modular forms for the modular group Γ = PSL_{2}(ℤ) and its congruence subgroups; a few results from Riemann surface theory. We will also need a little basic algebraic topology (mainly the definition of homology groups in terms of triangulations of a surface); this will be outlined very briefly in section 2.2 below.

References for modular symbols include: Lang’s book [14], the articles [15] and [16] and the author’s book [6]. A good reference which also includes a detailed account of the theoretical construction of modular elliptic curves is Knapp’s book [10]. These notes follow Chapter 2 of [6] closely, with certain details added or omitted in places.

2. Modular curves and homology

2.1. The upper half-plane, the modular group and cusp forms. Let H denote the upper half-plane

H = {z = x + iy ∈ ℂ | y > 0},

and H^{∗} = H ∪ ℚ ∪ {∞} the extended upper half-plane, obtained by including the cusps ℚ∪{∞}. The group P SL_{2}(ℝ) acts on H^{∗} via linear fractional transformations:

( \begin{matrix}a & b \\ c & d \end{matrix} ): z ↦ \frac{az + b}{cz + d};

these are the isometries of the hyperbolic geometry on H, for which geodesics are either half-lines perpendicular to the real axis ℝ, or semicircles perpendicular to ℝ.

The modular group Γ = PSL_{2}(ℤ) is a discrete subgroup of PSL_{2}(ℝ) (in the topology induced from SL(2, ℝ) ⊂ M_{2}(ℝ) ≅ ℝ^{4}), and acts discontinuously on H, in the sense that for each z ∈ H the orbit Γ.z is discrete. Note that the cusps ℚ ∪ {∞} form a complete Γ-orbit.

Γ is generated by the matrices S = ( \begin{matrix}0 & −1 \\ 1 & 0 \end{matrix} ): z ↦ −1/z and T = ( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ): z ↦

z + 1. This fact, and the related fact that a fundamental region for the action of Γ on H is given by the set

(2.1.1)  F := \{z = x + iy ∈ H | |x| ≤ \frac{1}{2}, |z| ≥ 1\},

are standard and will not be proved here. Both results depend essentially on the fact that ℤ is Euclidean.

Let G be a subgroup of Γ of finite index e. Then G also acts discretely on H. A fundamental region for G on H is given by ∪M_{i}.F, where the M_{i}, (for 1 ≤ i ≤ e), are right coset representatives for G in Γ.

Let X_{G} = G\H^{∗} denote the quotient space; this may be given the structure of a compact Riemann surface. Around most points the local parameter is just z, but more care is needed about the “parabolic points” or cusps, and the “elliptic points” which have non-trivial stabilisers in the Γ-action. These elliptic points for G (if any) are in the orbits of i (stabilised by S of order 2), and of ρ = (1 + \sqrt{−3})/2 (stabilised by T S of order 3). See the books of Lang [14], Shimura [19] or Knapp [10] for details of the Riemann surface construction.

Let g denote the genus of the surface X_{G}; as a real manifold, X_{G} is a g-holed torus. (Strictly speaking, X_{G} is not a manifold unless G has no elements of finite order, because of the branching over the elliptic points. However this makes no difference in practice and we may safely ignore it.) We will be concerned with the explicit computation of the 1-homology H_{1}(X_{G}, ℤ), which is a free ℤ-module of rank 2g. (See §2.2 below for a brief review of homology). This homology will be expressed in terms of “modular symbols”, defined below. We must also explain the connection between homology, modular forms, and elliptic curves. First we review the definition of cusp forms.

The space of cusp forms of weight 2 for G will be denoted by S_{2}(G) . These cusp forms are holomorphic functions f(z) (for z ∈ H) which satisfy

(1) f | M = f for all M ∈ G, where

(f | ( \begin{matrix}a & b \\ c & d \end{matrix} ))(z) = (cz + d)^{−2}f(\frac{az + b}{cz + d}).

Thus, since (cz + d)^{−2} = (d/dz)(M(z)) for M = ( \begin{matrix}a & b \\ c & d \end{matrix} ), we have

f(M(z))d(M(z)) = f(z)dz ∀M ∈ G.

(2) f(z) behaves nicely at the cusps. The significance of this condition is that, by (1), a cusp form of weight 2 for G is the pull-back of a (holomorphic) differential on the Riemann surface G\H, of which X_{G} is the compactification after adding the (finitely many) G-inequivalent cusps, and we want this differential to be holomorphic on the whole of X_{G}. In future we will identify cusp forms of weight 2 for G with holomorphic differentials on X_{G}. From standard Riemann surface theory, we then know that S_{2}(G) is a complex vector space of dimension g.

We can make explicit the condition that f(z)dz is holomorphic at the cusp ∞ (for the other cusps, see one of the references on the theory of modular forms). The stabiliser of ∞ in Γ is the infinite cyclic subgroup generated by T; if h is the least positive integer such that T^{h} ∈ G, then clearly we have

Stab(∞) ∩ G = ⟨T^{h}⟩ ,

and every f ∈ S_{2}(G) has a Fourier expansion of the form

(2.1.2)  f(z) = ∑_{n=1}^{∞} a_{n}e^{2πinz/h}

with coefficients a_{n} ∈ ℂ. The integer h is called the width of the cusp ∞; for G = Γ_{0}(N), the case we will be most interested in, we have h = 1, since T ∈ Γ_{0}(N).

2.2. The duality between cusp forms and homology.

The basis for our method is the explicit computation of the homology (specifically, the rational 1-homology) of the Riemann surface X_{G}. This is useful for various reasons. On the one hand, this gives us a very explicit vector space on which Hecke operators act, which is isomorphic (or more strictly, dual) to the space of cusp forms. Thus by computing homology and the Hecke action on it, we are indirectly also able to obtain information about the space of cusp forms. The Fourier coefficients of the cusp forms are determined by their Hecke eigenvalues (see §5.2), so we obtain these indirectly as eigenvalues of Hecke operators acting on homology. Secondly, in order to actually compute the elliptic curves attached to these cusp forms, we need to know their periods, which are obtained by integrating the corresponding differentials around closed paths on the surface X_{G}; since two paths give the same period (for all forms) if and only if they are homologous (essentially by Cauchy’s Theorem on X_{G}), it is clear that to determine the whole period lattice we will also require an explicit knowledge of the homology of X_{G}.

The integral homology H_{1}(X_{G}, ℤ) is most easily defined geometrically: it is the abeilan group obtained by taking as generators all closed paths on X_{G}, and factoring out by the relation that two closed paths are equivalent (or homologous) if one can be continuously deformed into the other. If the genus of the surface X_{G} is g, this gives a free abelian group of rank 2g: roughly speaking, the surface is a g-holed torus, and there are two generating loops around each hole. To determine this homology group in practice, one triangulates the surface, so that every path is homologous to a path along the edges of the triangulation. Now the generators are the directed edges of the triangulation, modulo relations given by the sum of the edges around each triangle being homologous to zero. A typical element of H_{1}(X_{G}, ℤ) will then be given as a ℤ-linear combination of these directed edges. In §2.6 below, we will make this very explicit: there will be one edge of the triangulation for each coset of G in Γ, and the triangle relations will be expressed algebraically in terms of the coset action of Γ. This description will entirely algebraicise the situation, in a way which is then easy to implement on a computer.

For any other ring R, the homology with coefficients in R is obtained simply by tensoring with R:

H_{1}(X_{G}, R) = H_{1}(X_{G}, ℤ) ⊗_{ℤ} R.

Explicitly, one just takes R-linear combinations of the 2g generators of the ℤ-module H_{1}(X_{G}, ℤ) (“extension of scalars”); the result is then an R-module. In what follows we will only need to take R = ℚ, R = ℝ, and R = ℂ.

Let H_{1}(X_{G}, ℝ) = H_{1}(X_{G}, ℤ) ⊗_{ℤ} ℝ, which is a real vector space of dimension 2g. Abstractly, this space is obtained by formal extension of scalars from H_{1}(X_{G}, ℤ); but we can be more concrete, if we introduce the notion of modular symbols.

First let α, β ∈ H^{∗} be points equivalent under the action of G, so that β = M(α) for some M ∈ G. Any smooth path (for instance, a geodesic path) from α to β in H^{∗} projects to a closed path in the quotient space X_{G}, and hence determines an integral homology class in H_{1}(X_{G}, ℤ), which depends only on α and β and not on the path chosen, because H^{∗} is simply connected. (In fact, the class depends only on M: see (5) in Lemma 2.4.1 below). We denote this homology class by the modular symbol {α, β}_{G}, or simply {α, β} when the group G is clear from the context.

Conversely, every integral homology class γ ∈ H_{1}(X_{G}, ℤ) can be represented by such a modular symbol {α, β}. Also, if f ∈ S_{2}(G) then the integral

∫_{γ} 2πif(z)dz = 2πi ∫_{α}^{β} f(z)dz

is well-defined, since f(z) is holomorphic, and will be denoted ⟨γ, f⟩. The (complex) value of such an integral is called a period of the cusp form f, or of the associated differential.

Let f_{1}, f_{2}, …, f_{g} be a fixed basis for S_{2}(G), so that the differentials 2πif_{j}(z)dz are a basis for the holomorphic differentials on X_{G}. Also let γ_{1}, γ_{2}, …, γ_{2g} be a fixed ℤ-basis for the integral homology H_{1}(X_{G}, ℤ). Then we may form the 2g × g complex period matrix

Ω = (ω_{jk}) = (⟨γ_{j}, f_{k}⟩) .

By standard Riemann surface theory, the 2g rows of Ω are linearly independent over ℝ, and so their ℤ-span is a lattice (discrete subgroup) Λ of rank 2g in ℂ^{g}. The quotient J(G) = ℂ^{g}/Λ is the Jacobian of X_{G}: it is an abelian variety of dimension g.

The symbols {α, β} give ℂ-linear functionals S_{2}(G) → ℂ via f ↦ ⟨{α, β}, f⟩ = 2πi ∫_{α}^{β} f(z)dz. We may identify H_{1}(X_{G}, ℝ) with the space of all ℂ-linear functionals on S_{2}(G) as follows: given an element γ ∈ H_{1}(X_{G}, ℝ) we can write γ uniquely in the form

γ = ∑_{j=1}^{2g} c_{j}γ_{j}

with coefficients c_{j} ∈ ℝ. Define ⟨γ, f⟩ = ∑_{j=1}^{2g} c_{j} ⟨γ_{j}, f⟩. Then the corresponding functional is

f ↦ ⟨γ, f⟩ .

Conversely, given a functional ω: S_{2}(G) → ℂ, the vector (ω(f_{1}), ω(f_{2}), …, ω(f_{g})) ∈ ℂ^{g} may be expressed uniquely as an ℝ-linear combination of the rows of Ω, so there exist real scalars c_{j} (1 ≤ j ≤ 2g) such that

ω(f) = ∑_{j=1}^{2g} c_{j} ⟨γ_{j}, f⟩

for all f ∈ S_{2}(G); then ω(f) = ⟨γ, f⟩ where γ = ∑_{j=1}^{2g} c_{j}γ_{j} ∈ H_{1}(X_{G}, ℝ).

In particular, let α, β ∈ H^{∗} be arbitrary (not necessarily in the same G-orbit); then the functional

f ↦ ∫_{α}^{β} 2πif(z)dz

corresponds to a unique element γ = ∑_{j=1}^{2g} c_{j}γ_{j} ∈ H_{1}(X_{G}, ℝ), and we define the modular symbol {α, β}_{G} ∈ H_{1}(X_{G}, ℝ) to be this element. Clearly this definition agrees with the earlier one in the special case where β = M(α) for some M ∈ G; indeed, this case holds if and only if all c_{j} ∈ ℤ.

By the field of definition of an element γ ∈ H_{1}(X_{G}, ℝ) we mean the field generated over ℚ by its coefficients c_{j} (with respect to the ℤ-basis for the integral homology, as above). For example, γ is rational (has field of definition ℚ) if and only if γ ∈ H_{1}(X_{G}, ℚ).

We now have an ℝ-bilinear pairing

(2.2.1)  S_{2}(G) × H_{1}(X_{G}, ℝ) ⟶ ℂ

given by

(f, γ) ↦ ⟨γ, f⟩ = ∫_{γ} 2πif(z)dz

which gives an exact duality between the two spaces on the left if we view S_{2}(G) as a real vector space of dimension 2g.

To interpret this as a duality over ℂ, we can give H_{1}(X_{G}, ℝ) the structure of a vector space over ℂ (of dimension g) as follows. Given γ ∈ H_{1}(X_{G}, ℝ) and c ∈ ℂ, we define cγ to be that element of H_{1}(X_{G}, ℝ) which satisfies ⟨cγ, f⟩ = ⟨γ, cf⟩ for all f ∈ S_{2}(G); in other words, cγ is the element corresponding to the functional f ↦ c ⟨γ, f⟩. Now the map (f, γ) ↦ ⟨γ, f⟩ is ℂ-bilinear, and our dual pairing (2.2.1) between homology and cusp forms is an exact duality over ℂ.

2.3. Real Structure.

For suitable groups G we can restrict the duality described above to a duality between real vector spaces of dimension g. This has important implications for explicit computations, where a halving of the dimension (from 2g to g) gives a significant saving of effort.

Let J = ( \begin{matrix}−1 & 0 \\ 0 & 1 \end{matrix} ). We say that a subgroup G of Γ is of real type if J normalises

G. Explicitly, let M = ( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ G; then M^{∗} := J^{−1}MJ = ( \begin{matrix}a & −b \\ −c & d \end{matrix} ), and G

is of real type when M ∈ G ⟺ M^{∗} ∈ G. This will be true, in particular, for the congruence subgroups Γ_{0}(N) and Γ_{1}(N) of most interest to us.

For z ∈ H set z^{∗} = −\overline{z}. Then a trivial calculation shows that w = M(z) ⟺ w^{∗} = M^{∗}(z^{∗}); it follows that, for G of real type, the map z ↦ z^{∗} induces a welldefined map on the quotient X_{G}, and hence also on homology, via {α, β} ↦ {α^{∗}, β^{∗}}. Clearly this is an ℝ-linear involution on H_{1}(X_{G}, ℝ). Hence we obtain a decomposition into +1 and −1 eigenspaces for ∗:

H_{1}(X_{G}, ℝ) = H_{1}^{+}(X_{G}, ℝ) ⊕ H_{1}^{−}(X_{G}, ℝ).

Remark. The involution ∗ also acts on the integral homology H_{1}(X_{G}, ℤ), and we may set H_{1}^{±}(X_{G}, ℤ) = H_{1}^{±}(X_{G}, ℝ) ∩ H_{1}(X_{G}, ℤ). However the direct sum H_{1}^{+}(X_{G}, ℤ) ⊕ H_{1}^{−}(X_{G}, ℤ) will in general have finite index in H_{1}(X_{G}, ℤ).

We now define dually an involution, also denoted ∗, on the space S_{2}(G) where G is of real type. For a holomorphic function f on H, we set f^{∗}(z) = \overline{f(z^{∗})}. The following facts are now easily verified:

(1) If f has Fourier expansion f(z) = ∑ a_{n}q^{n} (where q = exp(2πiz/h) as in (2.1.2) above), then f^{∗}(z) = ∑ \overline{a_{n}}q^{n}. In other words, the Fourier coeffients of f^{∗} are the conjugates of those of f.

(2) For M ∈ Γ, we have f^{∗} | M = (f | M^{∗})^{∗}.

(3) ⟨γ^{∗}, f^{∗}⟩ = \overline{⟨γ, f⟩} for all f, γ.

As a formal consequence of fact (2), we immediately see that, for G of real type, the map f ↦ f^{∗} is an ℝ-linear map from S_{2}(G) to itself, which is an involution. Denote by S_{2}(G)_{ℝ} the ℝ-subspace of S_{2}(G) fixed by this involution, which by fact (1) consists of those cusp forms with real Fourier coefficients. Then dim_{ℝ}(S_{2}(G)_{ℝ}) = g, and S_{2}(G)_{ℝ} spans S_{2}(G) over ℂ.

For nonzero f ∈ S_{2}(G)_{ℝ} we have (from fact (3)):

⟨γ, f⟩ ∈ ℝ ⟺ γ ∈ H_{1}^{+}(X_{G}, ℝ),

and also

⟨γ, f⟩ ∈ iℝ ⟺ γ ∈ H_{1}^{−}(X_{G}, ℝ).

Moreover, multiplication by i on H_{1}(X_{G}, ℝ) interchanges the “real” and “pure imaginary” eigenspaces H_{1}^{±}(X_{G}, ℝ) since

γ ∈ H_{1}^{+} ⟺ ⟨γ, f⟩ ∈ ℝ  ∀f ∈ S_{2}(G)_{ℝ}
⟺ ⟨iγ, f⟩ ∈ iℝ ∀f ∈ S_{2}(G)_{ℝ}
⟺ iγ ∈ H_{1}^{−}.

It follows that dim H_{1}^{+}(X_{G}, ℝ) = dim H_{1}^{−}(X_{G}, ℝ) = g.

Also, since the period ⟨γ, f⟩ is real for γ ∈ H_{1}^{+} and f ∈ S_{2}(G)_{ℝ}, the duality over ℂ we had earlier now restricts to a duality over ℝ:

(2.3.1)  S_{2}(G)_{ℝ} × H_{1}^{+}(X_{G}, ℝ) ⟶ ℝ.

It follows that the real vector spaces S_{2}(G)_{ℝ} and H_{1}^{+}(X_{G}, ℝ) are dual to each other. We will exploit this duality (which also respects the action of Hecke and other operators, see below), as we will compute H_{1}(X_{G}, ℝ) explicitly in order to gain information about the cusp forms in S_{2}(G). Also, this duality is crucial in the definition of modular elliptic curves.

2.4. Modular symbol formalism.

The following simple properties of the modular symbols {α, β} are now immediate.

Lemma 2.4.1. Let α, β, γ ∈ H^{∗}, and let M, M_{1}, M_{2} ∈ G. Then

(1) {α, α} = 0;

(2) {α, β} + {β, α} = 0;

(3) {α, β} + {β, γ} + {γ, α} = 0;

(4) {Mα, Mβ}_{G} = {α, β}_{G};

(5) {α, Mα}_{G} = {β, Mβ}_{G};

(6) {α, M_{1}M_{2}α}_{G} = {α, M_{1}α}_{G} + {α, M_{2}α}_{G};

(7) {α, Mα}_{G} ∈ H_{1}(X_{G}, ℤ).

Proof. Only (5) and (6) are not quite obvious. For (5), write {α, Mα} = {α, β}+ {β, Mβ} + {Mβ, Mα}, using (2) and (3); now the first and third terms cancel by (4). For (6), we have {α, M_{1}M_{2}α} = {α, M_{1}α} + {M_{1}α, M_{1}M_{2}α} = {α, M_{1}α} + {α, M_{2}α} using (4). □

Corollary 2.4.2. The map M ↦ {α, Mα}_{G} is a surjective group homomorphism G → H_{1}(X_{G}, ℤ), which is independent of α ∈ H^{∗}.

The kernel of this homomorphism contains all commutators and elliptic elements (since the latter have finite order, and the image is a torsion-free abelian group), and also all parabolic elements: for if M ∈ G is parabolic, it is a conjugate of T and hence fixes some α ∈ ℚ ∪ {∞}, so M ↦ {α, Mα} = 0. In fact, the kernel is generated by these elements, but we will not prove that here.

2.5. Rational Structure and the Manin-Drinfeld Theorem.

We have seen that every element γ of H_{1}(X_{G}, ℤ) has the form {α, Mα} with M ∈ G and α ∈ H^{∗} arbitrary; usually we take α to be a cusp, so that γ is a path between G-equivalent cusps. It is not clear in general what is the field of definition of a modular symbol {α, β}_{G} for which α and β are both cusps. However, when G is a congruence subgroup, this is answered by the Manin-Drinfeld Theorem.

A congruence subgroup of Γ is a subgroup G such that membership of G is determined by means of congruence conditions on the entries of a matrix in Γ. A moment’s thought shows that this is equivalent to the condition that for some positive integer N, G contains the principal congruence subgroup Γ(N), which is defined to be the subgroup of Γ consisting of matrices congruent to the identity modulo N. The least such N is called the level of G.

The most important congruence subgroups are Γ(N) itself;

Γ_{0}(N) = \{( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ Γ | c ≡ 0 (mod N)\};

and

Γ_{1}(N) = \{( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ Γ | c ≡ 0, a ≡ 1 (mod N)\} .

We can now state the Manin-Drinfeld Theorem.

Theorem 2.5.1. (Manin, Drinfeld) Let G be a congruence subgroup of the modular group Γ. Then for all pairs of cusps α, β ∈ H^{∗} we have

{α, β}_{G} ∈ H_{1}(X_{G}, ℚ).

In particular, the modular symbol {0, ∞}_{G} is rational; the denominator of this element is very important in many ways.

Thus the rational homology H_{1}(X_{G}, ℚ) is generated by paths between cusps (since it is generated by the integral homology), and conversely every path between cusps is rational. We will see how to use this fact to develop an algorithm for computing the rational homology in the next section.

The proof of the Manin-Drinfeld Theorem involves the use of Hecke operators (see Lang’s book [14], for example). Using Hecke operators we can also prove that the space of cusp forms S_{2}(G) has a ℚ-structure, namely a basis consisting of forms with rational Fourier coefficients (when G is a congruence subgroup). This is related to the fact that the modular curve X_{G}, which as a Riemann surface is certainly an algebraic curve over ℂ, can in fact be given the structure of an algebraic curve over the field of algebraic numbers \overline{ℚ} (and even over the N’th cyclotomic field, if G has level N). This rational structure is crucial to the construction of modular elliptic curves, to ensure that we obtain elliptic curves defined over ℚ.

The duality between cusp forms and homology does not descend entirely to ℚ, however, because even if f ∈ S_{2}(G) has rational Fourier coefficients and γ ∈ H_{1}(X_{G}, ℚ), the period ⟨γ, f⟩ will not be rational. Rationality questions for periods of modular forms have been studied extensively, notably by Manin, but we will not go into this further here.

2.6. Triangulations and homology.

From now on we will assume that G is a congruence subgroup, so that the rational homology of X_{G} is precisely the homology generated by paths between cusps.

We will compute the homology of X_{G} by first triangulating the upper half-plane H^{∗}, using a tessellation of hyperbolic triangles, and then passing to the quotient. This will give us a very explicit triangulation of the surface X_{G}, using which we can write down explicit generators and relations for its 1-homology.

For M ∈ Γ let (M) := {M(0), M(∞)}, viewed as a path in H^{∗}, the image under M of the imaginary axis {0, ∞}. These geodesic paths form the oriented edges of a triangulation of H^{∗} whose vertices are the cusps ℚ ∪ {∞}. Explicitly, there is an edge from ∞ to n for all n ∈ ℤ, and an edge between rational numbers a/c and b/d such that ad − bc = 1. The triangles of the triangulation are images under M ∈ Γ of the basic triangle with vertices at 0, 1 and ∞ and edges (I), (T S), ((T S)^{2}). We denote by ⟨M⟩ the image of this triangle under M, which has vertices M(0), M(1) and M(∞) and edges (M), (MT S) and (M(T S)^{2}). This representation of the triangles is unique except for the relation

⟨M⟩ = ⟨MT S⟩ = ⟨M(T S)^{2}⟩ .

Also, triangles ⟨M⟩ and ⟨MS⟩ meet along the edge (M) since (MS) = −(M) (the negative sign indicating reverse orientation).

We will use the symbol (M)_{G} to denote the image of the path (M) in the quotient X_{G}, and also its image in the rational homology. The geometric observations of the previous paragraph now give us the following relations between these symbols:

(M)_{G} + (MT S)_{G} + (M(T S)^{2})_{G} = 0
(M)_{G} + (MS)_{G} = 0.

We also clearly have the relations

(2.6.1)  (M′M)_{G} = (M)_{G}

for all M′ ∈ G, so we may use as generators of the rational homology the finite set of symbols (M_{i})_{G}, (1 ≤ i ≤ e), where as before M_{1}, …, M_{e} are a set of right coset representatives for G in Γ.

Let C(G) be the ℚ-vector space with basis the formal symbols (M)_{G} for each M in Γ, identified by the relations (2.6.1), so that dim(C(G)) = e = [Γ : G].

Let B(G) be the subspace of C(G) spanned by all elements of the form

(M)_{G} + (MS)_{G},
(M)_{G} + (MT S)_{G} + (M(T S)^{2})_{G}.

Let C_{0}(G) be the ℚ-vector space spanned by the G-cusps [α]_{G} for α ∈ ℚ ∪ {∞} (so that [α]_{G} = [β]_{G} ⟺ β = M(α) for some M ∈ G). Define the boundary map δ: C(G) → C_{0}(G) by

δ((M)_{G}) = [M(∞)]_{G} − [M(0)]_{G}

and set Z(G) = ker(δ). Note that B(G) ⊆ Z(G), by a trivial calculation using the facts that S transposes 0 and ∞ while T S cycles 0, 1 and ∞.

Finally we define H(G) = Z(G)/B(G). The crucial result, due in this form to Manin [15, Theorem 1.9], is that this formal construction does in fact give us the rational homology of X_{G}:

Theorem 2.6.1. H(G) is isomorphic to H_{1}(X_{G}, ℚ), the isomorphism being induced by

(M)_{G} ↦ {M(0), M(∞)}_{G}.

We may thus use the symbol (M)_{G} either as an abstract symbol obeying certain relations, or to denote an element of H_{1}(X_{G}, ℚ), without confusion. In future, as the subgroup G will be fixed, we will omit the subscript on these symbols and blur the distinction between (M) as a path in the upper half-plane and (M)_{G} as representing an element of the rational 1-homology of X_{G}.

Note that the form of the relations between the generating symbols (M) does not depend at all on the specific group G. In particular we do not have to consider explicitly the shape of a fundamental region for the action of G on H^{∗}, or how the edges of such a region are identified. This represents a major simplification compared with earlier approaches, such as that used by Tingley [22]. In order to develop this result into an explicit algorithm for computing homology, we need to have a specific set of right coset representatives for the subgroup G of Γ, and also to have a test for G-equivalence of cusps. These are purely algebraic problems which can easily be solved for arithmetically defined subgroups G such as congruence subgroups. Observe that from this point on, we do not have to do any geometry at all.

One final remark before we specialise to the case G = Γ_{0}(N): every path between cusps may be expressed as a finite sum of paths of the form (M) with M ∈ Γ.

3. M-SYMBOLS AND Γ_{0}(N) 11

Writing {α, β} = {0, β} − {0, α}, it suffices to do this for modular symbols of the form {0, α}. Let

\frac{p_{−2}}{q_{−2}} = \frac{0}{1}, \frac{p_{−1}}{q_{−1}} = \frac{1}{0}, \frac{p_{0}}{1} = \frac{p_{0}}{q_{0}} , \frac{p_{1}}{q_{1}} , \frac{p_{2}}{q_{2}} , …, \frac{p_{k}}{q_{k}} = α

denote the continued fraction convergents of the rational number α. Then, as is well-known,

p_{j}q_{j−1} − p_{j−1}q_{j} = (−1)^{j−1} for −1 ≤ j ≤ k.

Hence

\{0, α\} = ∑_{j=−1}^{k} \{\frac{p_{j−1}}{q_{j−1}} , \frac{p_{j}}{q_{j}} \} = ∑_{j=−1}^{k} \{M_{j}(0), M_{j}(∞)\} = ∑_{j=−1}^{k}(M_{j})

where M_{j} = ( \begin{matrix}(−1)^{j−1}p_{j} & p_{j−1} \\ (−1)^{j−1}q_{j} & q_{j−1} \end{matrix} ).

These conversions are easy to implement using the Euclidean algorithm.

3. M-symbols and Γ_{0}(N)

We now specialise to the case G = Γ_{0}(N):

Γ_{0}(N) = \{( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ Γ | c ≡ 0 (mod N)\} .

The index of Γ_{0}(N) in Γ is given (see [19, Proposition 1.43]) by

[Γ : Γ_{0}(N)] = N ∏_{p|N} (1 + p^{−1}) .

Define H(N) = H(Γ_{0}(N)) and X_{0}(N) = X_{G}. After Theorem 2.6.1, we will identify H(N) with H_{1}(X_{0}(N), ℚ) by identifying (M) with {M(0), M(∞)}.

The next Lemma is needed to determine right coset representatives for Γ_{0}(N) in Γ.

Lemma 3.1.1. For i = 1, 2 let M_{i} = ( \begin{matrix}a_{i} & b_{i} \\ c_{i} & d_{i} \end{matrix} ) ∈ Γ. The following are equivalent.

(1) The right cosets Γ_{0}(N)M_{1} and Γ_{0}(N)M_{2} are equal;

(2) c_{1}d_{2} ≡ c_{2}d_{1} (mod N);

(3) There exists u with gcd(u, N) = 1 such that c_{1} ≡ uc_{2} and d_{1} ≡ ud_{2} (mod N).

On the set of ordered pairs (c, d) ∈ ℤ^{2} such that gcd(c, d, N) = 1 we now define the relation ∼, where

(3.1.1)  (c_{1}, d_{1}) ∼ (c_{2}, d_{2}) ⟺ c_{1}d_{2} ≡ c_{2}d_{1} (mod N).

By Lemma 3.1.1, this is an equivalence relation. The equivalence class of (c, d) will be denoted (c : d), and such symbols will be called M-symbols (after Manin, who introduced them in [15]). The set of these M-symbols modulo N is P^{1}(N) = P^{1}(ℤ/Nℤ), the projective line over the ring of integers modulo N.

Notice that in an M-symbol (c : d), c and d are only determined modulo N, and that we can always choose them such that gcd(c, d) = 1.

Lemma 3.1.1 now implies the following.

Proposition 3.1.2. There exist bijections

P^{1}(N) ⟷ [Γ : Γ_{0}(N)] ⟷ {(M) : M ∈ [Γ : Γ_{0}(N)]}

given by

(3.1.2)  (c : d) ↔ M = ( \begin{matrix}a & b \\ c & d \end{matrix} ) ↔ (M) = \{b/d, a/c\}

where a, b ∈ ℤ are chosen so that ad − bc = 1. □

Note that a different choice of a, b in (3.1.2) has the effect of multiplying M on the left by a power of T, which does not change the right coset of M, or the symbol (M), since T ∈ Γ_{0}(N) for all N.

The right coset action of Γ on [Γ : Γ_{0}(N)] induces an action on P^{1}(N):

(3.1.3)  (c : d) ( \begin{matrix}p & q \\ r & s \end{matrix} ) = (cp + dr : cq + ds).

The boundary map δ now takes the form

(3.1.4)  δ: (c : d) ↦ [a/c] − [b/d].

In order to compute ker(δ), we must be able to determine when two cusps are Γ_{0}(N)-equivalent. This is achieved by the following result.

Lemma 3.1.3. For i = 1, 2 let α_{i} = p_{i}/q_{i} be cusps written in lowest terms. The following are equivalent:

(1) α_{2} = M(α_{1}) for some M ∈ Γ_{0}(N);

(2) q_{2} ≡ uq_{1} (mod N) and up_{2} ≡ p_{1} (mod gcd(q_{1}, N)), with gcd(u, N) = 1.

(3) s_{1}q_{2} ≡ s_{2}q_{1} (mod gcd(q_{1}q_{2}, N)), where s_{j} satisfies p_{j}s_{j} ≡ 1 (mod q_{j}).

Henceforth, we can therefore assume that H(N) is given explicitly in terms of M-symbols. Certain symbols will be generators, and each M-symbol (c : d) will be expressed as a ℚ-linear combination of these generating symbols, by means of the 2-term relations

(3.1.5)  (c : d) + (−d : c) = 0

and 3-term relations

(3.1.6)  (c : d) + (c + d : −c) + (d : −c − d) = 0.

When we search for Hecke eigenspaces (see next section) we will need to work in the smaller space H^{+}(N) (the +1-eigenspace for the ∗-involution). This can be done by including extra relations

(3.1.7)  (c : d) = (−c : d)

between M-symbols, and also identifying the cusps [α] and [α^{∗}]. Effectively we are viewing H^{+}(N) as the quotient H(N)/H^{−}(N) when we do this. One can also view this space H^{+}(N) as the homology of the quotient of H^{∗} by the group generated by Γ_{0}(N) and the matrix J of determinant −1, provided that one defines the action of matrices with negative determinant appropriately. Working in H^{+}(N) has several advantages: we have half the number of generators (identifying M-symbols in pairs via (3.1.7)), and can also halve the number of 3-term relations between them, as the 3-term relations for (c : d) and (d : c) now give the same information. Geometrically, we have folded the upper half-plane in half along the imaginary half-axis, and the triangles of our triangulation then coincide in pairs.

4. Hecke operators

For each prime p not dividing N, the Hecke operator T_{p} acts on modular symbols {α, β} via

(4.1.1)  T_{p}: \{α, β\} ↦ \{pα, pβ\} + ∑_{k mod p} \{\frac{α + k}{p} , \frac{β + k}{p} \} .

This action induces a linear map from H(N) to itself, provided that p does not divide N, which we again denote by T_{p}.

There are also Hecke operators, which we also denote T_{p}, acting on the space S_{2}(N) = S_{2}(Γ_{0}(N)) of cusp forms of weight 2 for Γ_{0}(N), defined for all primes p not dividing the level N. See one of the modular form references for the definition. The notation for the action of T_{p} on S_{2}(N) is f ↦ f |T_{p}.

These actions on S_{2}(N) and H(N) are compatible, in the sense that they respect the duality between cusp forms and homology:

⟨{α, β}, f |T_{p} ⟩ = ⟨T_{p}{α, β}, f⟩ .

Secondly, for each prime q dividing N there is an involution operator W_{q} acting on H(N) and S_{2}(N). The product of all the W_{q} for q dividing N is the Fricke involution

W_{N}, coming from the transformation z ↦ −1/Nz, with matrix ( \begin{matrix}0 & −1 \\ N & 0 \end{matrix} ).

The operators T_{p} for primes p not dividing N and W_{q} for primes q dividing N together generate a commutative ℚ-algebra, called the Hecke algebra and denoted 𝕋. Moreover, each operator is self-adjoint with respect to the so-called Petersson inner product on S_{2}(N), and so there exist bases for S_{2}(N) consisting of simultaneous eigenforms for all the T_{p} and W_{q}, with real eigenvalues. (See [1, Theorem 2] or [14, Corollary 2 to Theorem 4.2].) Similarly, the action of 𝕋 on H(N) ⊗ ℝ can also be diagonalised.

Finally, recall from section 2.3 that the transformation z ↦ z^{∗} = −\overline{z} on H also induces an involution on H(N) denoted ∗. This operator commutes with all the T_{p} and W_{q}, which thus preserve the eigenspaces H^{+}(N) and H^{−}(N). Moreover, H^{+}(N) and H^{−}(N) are isomorphic as modules for the Hecke algebra 𝕋. It follows that in order to compute eigenvalues of Hecke operators, we can restrict our attention to H^{+}(N). This has some practical significance, as indicated above.

In order to compute the action of the Hecke operators T_{p}, there are several ways to proceed. We may assume that we have an explicit basis for the homology H(N) given in terms of M-symbols. One approach is to convert these generating Msymbols to modular symbols {α, β}, apply T_{p} to each of these, giving linear combinations of modular symbols, and then using the continued fraction method to reconvert all of these back to M-symbols. Alternatively, it is possible to compute the action of T_{p} directly on the M-symbols. This method is based on so-called Brandt matrices: see [17] for details. The Brandt matrix method is faster in practice, particularly if we precompute the Brandt matrices for all small primes p. Lastly, once we have found a one-dimensional eigenspace in H^{+}(N) corrsponding to a newform f, there are tricks one can use to compute many more Hecke eigenvalues of f without having to compute the complete action of T_{p} on the whole space H^{+}(N). These methods are vital in practice, where we might have to compute eigenvalues of T_{p} for several thousand primes p: see the subsection 5.3 and [6] for details.

5. Rational newforms and modular elliptic curves

5.1. Rational newforms.

The space S_{2}(N) of cusp forms of weight 2 for Γ_{0}(N) is a complex vector space of dimension g (the genus of X_{0}(N)); it also has a rational structure, namely a basis consisting of forms with rational Fourier coefficients. We are interested here in “rational newforms” f: that is, forms f which have rational Fourier coefficients a(n, f), are simultaneous eigenforms for all the Hecke operators, and which are also “newforms” in the sense of Atkin and Lehner (see [1]). We briefly recall the definition.

For each proper divisor M of N and each g ∈ S_{2}(M), the forms g(Dz) for divisors D of N/M are in S_{2}(N). The subspace S_{2}^{old}(N) of S_{2}(N) spanned by all such forms is called the space of oldforms. There is also an inner product on S_{2}(N), called the Petersson inner product, with respect to which the Hecke operators are selfadjoint (Hermitian). Define S_{2}^{new}(N) to be the orthogonal complement in S_{2}(N) of S_{2}^{old}(N) with respect to the Petersson inner product. The restriction of the Hecke algebra 𝕋 to S_{2}^{new}(N) is semisimple; S_{2}^{new}(N) has a basis consisting of simultaneous eigenforms, and these eigenforms are called newforms.

Because of the rational structure on S_{2}(N), the Hecke operators can be expressed explicitly as matrices with rational entries; even with integral entries, since each T_{p} maps the integral homology H_{1}(X_{0}(N), ℤ) to itself. We can compute these matrices explicitly, and find their eigenvalues and eigenvectors using standard linear algebra.

In general, newforms come in conjugate sets of d ≥ 1 forms with eigenvalues generating an algebraic number field of degree d. The periods of such a set of conjugates {f} form a lattice Λ of rank 2d in ℂ^{d}, and hence an abelian variety A_{f} = ℂ^{d}/Λ, which is defined over ℚ. Here we will only be interested in the case d = 1, where the Hecke eigenvalues and hence Fourier coefficients of f are rational (in fact integers, being eigenvalues of integral matrices and hence algebraic integers). We will call such a form f a rational newform. Thus a rational newform f has an associated period lattice Λ_{f}:

Λ_{f} = {⟨{α, β}, f⟩ | α, β ∈ H^{∗}, α ≡ β (mod Γ_{0}(N))}

which is a discrete rank 2 subgroup of ℂ. Then E_{f} = ℂ/Λ_{f} is an elliptic curve, the modular elliptic curve attached to f. Moreover it is known that E_{f} is defined over ℚ, has conductor N, and has L-series L(E_{f}, s) = ∑ a(n, f)n^{−s} where f = ∑ a(n, f) exp(2πinz). (See [20], [19], [3].)

5.2. Fourier coefficients and L-series.

The Fourier coefficients a(n, f) of a newform f(z) = ∑ a(n, f) exp(2πinz) are obtained from the Hecke eigenvalues of f as follows (see [1]). Firstly, for a newform f we always have a(1, f) ≠ 0, and we normalise so that a(1, f) = 1. Then:

If p is a prime not dividing N, and f |T_{p} = a_{p}f, then a(p, f) = a_{p}. By standard estimates, the integer a_{p} satisfies |a_{p}| < 2\sqrt{p}.

If q is a prime dividing N, and f |W_{q} = ε_{q}f with ε_{q} = ±1, then

(5.2.1)  a(q, f) = \{ \begin{matrix}−ε_{q} & if q^{2} ∤ N, \\ 0 & if q^{2}|N. \end{matrix}

For prime powers, we have the recurrence relation

(5.2.2)  a(p^{r+1}, f) = a(p, f)a(p^{r}, f) − δ_{N}(p)pa(p^{r−1}, f)  (r ≥ 1)

where

δ_{N}(p) = \{ \begin{matrix}1 & if p ∤ N, \\ 0 & if p|N. \end{matrix}

Finally, for composite indices we have multiplicativity: a(mn, f) = a(m, f)a(n, f) when m and n are coprime.

The sign of the functional equation of the L-series L(f, s) attached to the newform f is minus the eigenvalue ε_{N} of the Fricke involution W_{N}; in the above notation, it is − ∏_{q|N} ε_{q}. Explicitly, we have

Λ(f, 2 − s) = −ε_{N}Λ(f, s),

where

Λ(f, s) = N^{s/2}(2π)^{−s}Γ(s)L(f, s) = ∫_{0}^{∞} f(iy/\sqrt{N})y^{s−1}dy.

Also, for ℜ(s) > 3/2 we have the Dirichlet series and Euler product expansions of L(f, s):

L(f, s) = ∑_{n=1}^{∞} \frac{a(n, f)}{n^{s}}

= ∏_{p∤N} (1 − a(p, f)p^{−s} + p^{1−2s})^{−1} ∏_{q|N} (1 − a(q, f)q^{−s})^{−1} .

The sign of the functional equation tells us the parity of the analytic rank of the elliptic curve E_{f}, which is (by definition) the order of L(f, s) at s = 1. By the Birch– Swinnerton-Dyer conjecture (BSD), this should equal the rank of the Mordell-Weil group E_{f}(ℚ). If the analytic rank is odd, then obviously L(f, 1) = 0, and we expect E_{f}(ℚ) to be infinite: indeed, this has been proved in the rank 1 case by Kolyvagin et al. (see [11]). In the next subsection we will see how to determine whether or not L(f, 1) = 0 in all cases.

5.3. The ratio L(f, 1)/Ω(f).

The real periods of the rational newform f are the periods ⟨γ, f⟩ where γ ∈ H_{1}^{+}(X_{0}(N), ℤ); these are all integer multiples of the least positive real period Ω_{0}(f). We set

Ω(f) = \{ \begin{matrix}2Ω_{0}(f) & if the period lattice of f is rectangular, \\ Ω_{0}(f) & otherwise. \end{matrix}

Thus Ω(f)/Ω_{0}(f) is the number of components of the real locus of the elliptic curve E_{f}. Also note that in each case, Ω(f) is twice the least real part of a period of f. This is useful since, when we are working in H^{+}(N), we can only (at that stage) determine the projection of the period lattice Λ_{f} onto the real axis.

A simple calculation with modular symbols shows that, for a prime p not dividing N, we have

(5.3.1)  (1 + p − T_{p}) · {0, ∞} = ∑_{k=0}^{p−1}{0, k/p}.

Integrating 2πif(z)dz along both sides of (5.3.1) gives

(5.3.2)  (1 + p − a_{p}) · L(f, 1) = − ∑_{k=0}^{p−1} ⟨{0, k/p}, f⟩ .

where a_{p} = a(p, f), and we have the used the fact that L(f, 1) = − ⟨{0, ∞}, f⟩. Since p does not divide N, each modular symbol {0, k/p} on the right of (5.3.1) is integral: that is, in H_{1}(X_{0}(N), ℤ). Thus the right-hand side of (5.3.2) is a period of f. It is even a real period, since the right-hand side of (5.3.1) is ∗-invariant, hence equal to n(p, f)Ω(f)/2 for some integer n(p, f). Hence we have the relation

(5.3.3)  \frac{L(f, 1)}{Ω(f)} = \frac{n(p, f)}{2(1 + p − a_{p})}.

Note that 1 + p − a_{p} > 0, since |a_{p}| < 2\sqrt{p}.

In practice the integer n(p, f) is computed as follows. Corresponding to the rational newform f there is a one-dimensional eigenspace in H^{+}(N) (which we may identify with the column space ℚ^{g} after fixing a basis). Let v_{f} be a dual eigenvector with the same eigenvalues of f, i.e., a row vector which is a left eigenvector for all the operator matrices; normalise v_{f} to lie in ℤ^{g} and have coprime entries (this determines v_{f} uniquely up to sign). Let u_{p} be a column vector in ℤ^{g} expressing (minus) the right-hand side of (5.3.1) in terms of our basis for H^{+}(N). Then n(p, f) is simply the dot product v_{f} · u_{p}. If necessary, we may replace v_{f} by −v_{f} in order to make both sides of (5.3.3) positive.

Formula (5.3.3) is significant in several ways. On the one hand, let E_{f} be the modular elliptic curve attached to f as above. Then L(E_{f}, 1) = L(f, 1), and Ω_{0}(f) = Ω_{0}(E_{f}), the least positive real period of E_{f}. Thus, once we know a_{p} and n(p, f) for a single prime p, we can evaluate the rational number L(E_{f}, 1)/Ω(E_{f}), whose value is predicted by the Birch–Swinnerton-Dyer conjecture (BSD) for E_{f}. We stress that we have obtained this rational number exactly, algebraically; in particular, we know for certain whether or not L(f, 1) = 0, without any approximation necessary.

Secondly, having computed the right-hand side of (5.3.3) for a single prime p, we may (if L(f, 1) ≠ 0) use the fact that n(p, f)/(1 + p − a_{p}) is independent of p to compute the eigenvalue a_{p} quickly for other p, by computing n(p, f). This is how we compute a large number of Hecke eigenvalues (and hence Fourier coefficients) in practice. A variation of this trick can be used when L(f, 1) = 0: see [6] for details.

5.4. Finding newforms.

With this background we may now make more precise what we mean by “computing the modular elliptic curves of conductor N”. We do the following:

(1) Compute the space H^{+}(N) in terms of M-symbols and their relations.

(2) Compute the action of sufficiently many Hecke operators W_{q} and T_{p} on H^{+}(N) to determine the one-dimensional eigenspaces with rational eigenvalues; by duality, we now know the rational newforms in S_{2}(N). (Oldforms can be recognised, since in any systematic computation we will have already found them at some lower level M dividing N.)

(3) Find a ℤ-basis for the period lattice Λ_{f}, for each rational newform f, computing the generating periods to high precision.

(4) Given a ℤ-basis for Λ_{f}, compute the coefficients of an equation for the attached elliptic curve E_{f}.

(5) As well as the period lattice of the curves E_{f}, we can also compute the rational number L(E_{f}, 1)/Ω(E_{f}) (exactly) and the real value L(E_{f}, 1) (approximately). Also, when L(E_{f}, 1) = 0 we can also determine the order of vanishing of L(E_{f}, s) at s = 1, giving the analytic rank r of E_{f}, and the value of the derivative L^{(r)}(E_{f}, 1), which is important in the Birch–Swinnerton-Dyer conjecture; we will not discuss the latter computation here, except briefly to give the relevant formulas in a later section.

We would like to make completely explicit exactly what we mean when we say that for a given level N we “know” the rational newforms in S_{2}(N). Our knowledge is both algebraic and analytic; also, it is important to understand exactly how much information we can obtain from working in H^{+}(N), and how much requires the full space H(N) to be available.

The first phase of our computations works in H^{+}(N), and is entirely algebraic. In this phase, we find all the 1-dimensional eigenspaces in H^{+}(N) for all the Hecke operators (which only involve computing the full action of all the W_{q} and of the T_{p} for a few small primes p), from which we know how many rational newforms there are, and hence how many modular elliptic curves of conductor N there are, up to isogeny. For each newform, we also know the first few Euler factors of its L-series L(f, s), the sign of its functional equation and also whether or not the L-series vanishes at s = 1. This tells us partial information about the analytic rank of the associated curve E_{f}: we know its parity and whether or not it is zero. (The first case where the rank is not equal to the minimal value consistent with this information is at level 5077, where we know from these algebraic considerations that the rank is odd, but where the curve turns out to have rank 3. Determining that the analytic rank is 3 rather than 1 in this case is not a purely algebraic computation, as it involves proving that the first derivative of the L-series vanishes at s = 1.)

In this first phase, we can also compute approximations to the value L(f, 1) (when it is non-zero) and to the period Ω(f), though we do not know at this stage whether Ω(f)/Ω_{0}(f) = 1 or 2. In other words, we can compute the projection of the period lattice Λ_{f} onto the real axis. Of course, this is insufficient information from which to construct the curve E_{f}.

These “analytic” quantities (periods) will necessarily be computed approximately, by summing certain infinite series whose coefficients involve the Fourier coefficients of f (see the next section). In order to achieve sufficient accuracy we may have to compute many thousands of these Fourier coefficients, and it is therefore necessary to have efficient ways of doing this, such as the method described above (in section 5.3).

To determine the full period lattice for each newform f, it is necessary to compute the full 2g-dimensional space H(N). This is what we call the second phase of the computation. In H(N) we find, for each rational newform f, the two-dimensional eigenspace associated to f (which is split into two one-dimensional eigenspaces by the ∗-involution). Once we have this two-dimensional eigenspace, it is a simple matter of linear algebra to determine elements γ_{1}, γ_{2} ∈ H_{1}(X_{0}(N), ℤ) such that the periods ω_{i} = ⟨γ_{i}, f⟩ are a ℤ-basis for the period lattice Λ_{f}. Then we may compute these generating periods, again approximately. From ω_{1} and ω_{2} we can compute approximations to the c_{4} and c_{6} invariants of the elliptic curve E_{f}. These are known to be rational (since E_{f} is defined over ℚ). Moreover, recent work of Edixhoven [9] on the Manin constant implies that these computed values of c_{4} and c_{6} are integral, which is of course crucial if we are to recognise them from floating point approximations. Given the integers c_{4} and c_{6}, it is then easy to find a standard Weierstrass equation for the curve E_{f}.

For large N (say over 3000), we have found this second phase (working in H(N)) to be very costly in computation time and in storage requirements. Hence we have been led to develop an indirect approach to determining the period lattice of each rational newform f. This new approach is extremely fast, but does have one critical disadvantage: we can (in most cases) determine a period lattice Λ′_{f} which is a sublattice of finite index in the full period lattice Λ_{f}, and such that ℂ/Λ′_{f} is an elliptic curve E′_{f} of conductor N with L(E′_{f}, s) = L(f, s), but we do not know that Λ′_{f} = Λ_{f}, so that E′_{f} might only be isogenous to the curve E_{f}. Secondly, we can only use this method in case N is not a perfect square, since we have to be able to choose primes l ≡ ±1 (mod 4) with (\frac{−N}{l} ) of prescribed sign (see next section).

This new method relies on the fact that the values L(f ⊗ χ, 1) for quadratic characters χ (with conductor coprime to N) are, on the one hand, easy to compute to high precision (given enough Fourier coefficients of the newform f); and on the other hand, they are simple multiples of integral periods of f. In our original approach we used modular symbols in H(N) to determine these multiples exactly and explicitly, so that two computations of L(f ⊗ χ, 1) for suitable characters χ were enough to determine the period lattice. We will discuss this situation, and the computation of steps (3) and (4), in greater detail in section 7 below.

6. Analytic formulas

In this section we collect together all the analytic formulas we need for evaluation of periods and special values of L-series. For brevity, proofs will be sketched or omitted; see [6] for details.

We keep the notation of previous sections: f will always be a rational newform for Γ_{0}(N), with Fourier coefficients a(n, f), normalised so that a(1, f) = 1.

6.1. Computing L(f, 1) and L(f ⊗ χ, 1).

Recall from section 5.2 that the eigenvalue ε_{N} of the Fricke involution is minus the sign of the functional equation of L(f, s), so that when ε_{N} = +1 we have L(f, 1) = 0 trivially (in this case the analytic rank is odd, hence trivially positive).

When ε_{N} = −1, we use the formula

(6.1.1)  L(f, 1) = 2 ∑_{n=1}^{∞} \frac{a(n, f)}{n} exp(−2πn/\sqrt{N}).

Essentially, L(f, 1) is the integral of f along the imaginary axis; when ε_{N} = −1 this integral is expressed as double the integral from i/\sqrt{N} to i∞.

The formula (5.3.3) we derived above, which expresses L(f, 1) as an explicit multiple of the real period Ω(f), can be generalised to useful effect. Let l be an odd prime not dividing N, and χ the quadratic character modulo l. Define

(f ⊗ χ)(z) = ∑_{n=1}^{∞} χ(n)a(n, f) exp(2πinz).

Then f ⊗ χ is a newform in S_{2}(Nl^{2}), whose Fricke eigenvalue ε_{Nl^{2}}(f ⊗ χ) is equal to χ(−N)ε_{N}(f). Hence for χ(−N) = ε_{N} we have L(f ⊗ χ, 1) = 0 trivially, while if χ(−N) = −ε_{N} we have

(6.1.2)  L(f ⊗ χ, 1) = 2 ∑_{n=1}^{∞} \frac{χ(n)a(n, f)}{n} exp(−2πn/l\sqrt{N}).

Set l^{∗} = χ(−1)l ≡ 1 (mod 4), and P (l, f) = \sqrt{l^{∗}}L(f ⊗ χ, 1). The generalization of (5.3.3) we need is

P (l, f) = ⟨γ_{l}, f⟩

where

γ_{l} = ∑_{k=0}^{l−1} χ(k) {0, k/l} .

Since l does not divide N, the cycle γ_{l} is in the integral homology, so P (l, f) is an integral period for each l. Also, it is easy to see that γ_{l}^{∗} = χ(−1)γ_{l}, so that this period P (l, f) is real or imaginary according as χ(−1) = +1 or −1, i.e., according as l ≡ ±1 (mod 4). Moreover, by expressing the cycle γ_{l} in terms of our fixed basis for H_{1}(X_{0}(N), ℤ), we may determine explicit integers m^{±}(l, f) (where ±1 = χ(−1)) such that if x and y denote the least positive real and imaginary parts of periods of f respectively, then P (l, f) = m^{+}(l, f)x or m^{−}(l, f)yi.

It is now clear that we will be able to express the period lattice for f in terms of the quantities P (l, f), provided that we can find auxiliary primes l of either sign such that χ(−N) = −ε_{N}. This is always possible in practice (and guaranteed theoretically by a theorem of Murty and Murty [18]), provided that N is not a perfect square. In this exceptional case, we compute the periods of f more directly (see subsection 6.3 below).

6.2. Computing L^{(r)}(f, 1) for r ≥ 1.

Let f be a newform in S_{2}(N) with W_{N}-eigenvalue ε_{N}, and suppose that the order of L(f, s) at s = 1 is at least r, where ε_{N} = (−1)^{r−1}. Then

(6.2.1)  L^{(r)}(f, 1) = 2(r!) ∑_{n=1}^{∞} \frac{a(n, f)}{n}G_{r}(\frac{2πn}{\sqrt{N}} )

where

G_{r}(x) = \frac{1}{(r − 1)!} ∫_{1}^{∞} e^{−xy}(log y)^{r−1} \frac{dy}{y} .

The functions G_{r}(x) which appear here satisfy the functional equations G′_{r}(x) = (−1/x)G_{r−1}(x), with G_{0}(x) = e^{−x}. For r = 1, the function G_{1}(x) = ∫_{1}^{∞} e^{−xy}dy/y, the exponential integral. For good ways of evaluating this, and for higher values of r, see [6] or the paper [2], where this formula was used to evaluate L^{(3)}(f, 1) for the newform f ∈ S_{2}(5077) attached to the elliptic curve of rank 3 and conductor 5077.

6.3. Computing periods directly.

To compute integral periods of a newform f, we may use essentially the same method as in [22]. It suffices to compute ⟨γ, f⟩ for a single cycle γ such that the real and imaginary parts are both nonzero; then by taking real and imaginary parts, and by expressing γ as a linear combination of our basis for H_{1}(X_{0}(N), ℤ), we may determine the generating periods ω_{1} and ω_{2}. (In some cases it may give better accuracy in practice to use two different cycles, one for the real period and one for the imaginary period, but for simplicity we will assume that this is not the case.)

Let M = ( \begin{matrix}a & b \\ Nc & d \end{matrix} ) ∈ Γ_{0}(N), with c > 0. Set y_{0} = 1/(Nc), x_{1} = −dy_{0}, and

x_{2} = ay_{0}, and let γ = {0, M(0)} ∈ H(N). Then

(6.3.1)  ⟨γ, f⟩ = ∑_{n=1}^{∞} \frac{a(n, f)}{n} exp(−2πny_{0}) (exp(2πinx_{2}) − exp(2πinx_{1})) .

In practice we will try to choose M so that c is as small (and hence y_{0} as large) as possible, to speed convergence in the series (6.3.1).

Observe that the convergence in (6.3.1) will not be so fast as in (6.1.1), since we now have a power series in exp(−2π/(Nc)) for an integer c ≥ 1, instead of in exp(−2π/\sqrt{N}). Similarly, (6.1.2) will usually be better than (6.3.1), unless the auxiliary prime l is greater than c\sqrt{N}.

7. From newform to lattice to curve

7.1. Finding the period lattice.

Let f be, as above, a rational newform in S_{2}(N). We wish to determine a ℤ-basis for the period lattice Λ_{f}. We work in the 2g-dimensional space H(N), identified with the column space ℚ^{2g} by fixing a basis for H(N) which is also a ℤ-basis for the integral homology H(N, ℤ) := H_{1}(X_{0}(N), ℤ).

Let v^{+} and v^{−} be dual eigenvectors corresponding to f, i.e. row vectors in the row-space ℚ^{2g} which are left eigenvectors for the Hecke algebra 𝕋 with the same eigenvalues as f; we also suppose that v^{±} are eigenvectors for the ∗-involution with eigenvalues ±1 respectively. We may normalise v^{±} so that each is in ℤ^{2g} and primitive (that is, with coprime entries); then each is uniquely determined up to sign.

There exist positive real numbers x and y such that for each cycle γ in H(N, ℤ), expressed as a column vector in ℤ^{2g}, we have

⟨γ, f⟩ = (v^{+}γ)x + (v^{−}γ)yi.

Here the products v^{±}γ are scalar products (row vector times column vector). There are two possibilities for the period lattice Λ_{f}: if v^{+} ≡ v^{−} (mod 2), then Λ_{f} = ⟨2x, x + yi⟩; otherwise Λ_{f} = ⟨x, yi⟩. We call these two cases “Type 1” and “Type 2” respectively.

The “direct” method of computing the lattice Λ_{f} is to compute ⟨γ, f⟩ for a cycle γ such that v^{±}γ are both non-zero, using the formula (6.3.1). This is the only method we can use when N is a perfect square; otherwise we obtain better precision by obtaining the periods indirectly, using special values of twisted L-series.

Recall from section 6.1 that for each odd prime l not dividing the level N we have defined integral periods

P (l, f) = \sqrt{l^{∗}}L(f ⊗ χ, 1) = ⟨γ_{l}, f⟩ ,

where l^{∗} = ±l ≡ 1 (mod 4) and γ_{l} = ∑_{a (mod l)} χ(a){0, a/l}. If l ≡ 1 (mod 4) then v^{−}γ_{l} = 0, since γ_{l} ∈ H^{+}(N), and now the integer m^{+}(l, f) := v^{+}γ_{l} satisfies

P (l, f) = m^{+}(l, f)x;

Secondly, when l ≡ −1 (mod 4) we have v^{+}γ_{l} = 0, since γ_{l} ∈ H^{−}(N), and the integer m^{−}(l, f) := v^{−}γ_{l} satisfies

P (l, f) = m^{−}(l, f)yi.

Hence to compute x and y, and so determine the period lattice, we simply have to find primes l^{±} ≡ ±1 (mod 4) such that the integers m^{±} = v^{±}γ_{l^{±}} are non-zero, and set x = P (l^{+}, f)/m^{+} and yi = P (l^{−}, f)/m^{−}.

We stress that, apart from the numerical evaluation of the periods P (l^{±}, f) (using the series for L(f ⊗χ, 1) in section 6.1), all these computations are purely algebraic: we express the cycles γ_{l} in terms of our homology basis using continued fractions, and take the dot products of the resulting column vectors with our dual eigenvectors v^{±} to obtain the integers m^{±}.

The result of this algebraic computation consists of the following data for each rational newform f: primes l^{±} congruent respectively to ±1 modulo 4; nonzero integers m^{±}; and the type (1 or 2) of the lattice. To compute the lattice from this data set of five integers, we compute the periods P (l^{±}, f) using formula (6.1.2), divide by m^{±} respectively to obtain x and y, and take Λ_{f} to be the lattice with ℤ-basis 2x, x + yi (if type 1) or x, yi (if type 2). In practice we store just these five integers (with the Hecke eigenvalues from which we can obtain the Fourier coefficients), and recompute the periods when we need them. In particular, if at the first attempt we are unable to compute the integer invariants c_{4}, c_{6} of the curve E_{f} to sufficient precision to recognise them, then we will return to H^{+}(N) in order to compute more Hecke eigenvalues, and then recompute the periods to greater precision without having to recompute H(N).

In fact, the data l^{+} and m^{+} can be computed earlier in the first H^{+}(N) phase, since they only depend on the real projection of the period lattice. Hence we can already compute the real period x from the data we have from the first phase. Moreover, it is easy to find a suitable prime l^{−} once we know the Hecke eigenvalues of f, by numerically computing P (l, f) for several primes l ≡ −1 (mod 4) until we find a value which is clearly non-zero.

It follows that the only purpose of the extremely expensive second phase of the computation, working in H(N), is to determine the integer factor m^{−} and the type of the lattice. Our new method, which we have used systematically for larger levels (N > 3200), is simply to guess the value of m^{−} by trying each positive integer m in turn. For each m ≥ 1 we set yi = P (l^{−}, f)/m and test the two possible lattices (one of each type). If either lattice has approximate integer invariants c_{4} and c_{6}, and the rounded integral values are valid invariants of an elliptic curve over ℚ, and the resulting curve has conductor N, then we store for later use the successful value m^{−} of m and the type, and consider the curve E′_{f} we have found as a possible candidate for the actual modular elliptic curve E_{f}.

As we pointed out above, the curves E_{f} and E′_{f} are certainly isogenous; they even have the same real period. In many cases, the curve E′_{f} has no rational isogenies; in such a case we can conclude that E_{f} = E′_{f} with no ambiguity. In any case, we can compute the isogeny class of curves isogenous to E′_{f} via rational isogenies, and the only loss is that we do not always know exactly which curve in the class is the “strong Weil curve” E_{f}. (A further disadvantage is that we cannot compute the degree of the modular parametrisation of E_{f}, as this requires knowledge of H(N): see section 10 below.)

The huge advantage of this method is that in only a few seconds computation time, as soon as we have a rational newform, we can (almost always) write down an associated curve E′_{f}; before this was implemented, it could take many hours of computation time to determine H(N), find the eigenvectors v^{±}, and hence determine the factor m^{−} and the lattice type, before we could compute E_{f}.

For an example of this method (with N = 11) see the next section.

Finally we discuss some variants of the trick just described.

1. We may use same trick to find l^{+} and m^{+} if we have not computed them earlier. Then we are obtaining the period lattice and equation of the curve using only: the Fourier coefficients of f (i.e. the coefficients of the L-series of the curve); the sign of the functional equation; and the conductor N. No modular symbol information at all is needed in this case. In fact, one may even guess the sign of the functional equation and compute the conductor if all one has is the L-series.

2. Let l_{1} and l_{2} be two primes ≡ −1 (mod 4) for which −N has the correct quadratic character, so that P (l_{1}, f) and P (l_{2}, f) are both not trivially zero. We may compute the periods P (l_{j}, f); assume that these are nonzero (or use different primes l_{j}). We know that there exist nonzero integers m_{j} such that P (l_{j}, f) = m_{j}yi for j = 1, 2. Therefore P (l_{2}, f)/P (l_{1}, f) = m_{2}/m_{1}, and we may compute a floating point approximation to this rational number. In practice (provided we have many Fourier coefficients, and the primes l_{j} are small) we will be able to recognise this rational number using continued fractions. Its denominator is then a factor of the unknown integer m_{1}. If we do this for several different values of l_{2} (with the same l_{1}) then the least common multiple of the denominators will often give us a useful factor of m_{1}, and then in our search for the exact value we may restrict to multiples of this factor. This is useful in practice.

3. Another possibility, which we have not yet implemented, is to compute H^{−}(N) in order to determine m^{−} exactly, as we do m^{+} from H^{+}(N). This would be no harder than the original computation of H^{+}(N), and in fact it would be easier to find the eigenvector corresponding to each newform f, since we already know its eigenvalues. The result would be that we would have computed exactly all the data we need in a shorter time than would be required for computing H(N), except for the type of the lattice. Then the only ambiguity is that we would not know the type, and would have to try both types to see which results in a curve with integral coefficients. If both types succeeded (as does happen), we would only know the curve E_{f} up to a 2-isogeny.

7.2. Finding the equation of the curve.

So far we have described how to compute, to a certain precision, the periods ω_{1} and ω_{2} which generate the period lattice Λ_{f} of the modular curve E_{f} = ℂ/Λ_{f} attached to each rational newform f in S_{2}(N). Now we turn to the question of finding an equation for E_{f}.

Set τ = ω_{1}/ω_{2}. Interchanging ω_{1} and ω_{2} if necessary, we may assume that Im(τ) > 0. By applying the well-known algorithm for moving a point in the upper half-plane H into the usual fundamental region for SL(2, ℤ) we may assume that |Re(τ)| ≤ 1/2 and |τ| ≥ 1, so that Im(τ) ≥ \sqrt{3}/2. One merely replaces (ω_{1}, ω_{2}) by (ω_{1} − nω_{2}, ω_{2}) for suitable n ∈ ℤ and (ω_{1}, ω_{2}) by (−ω_{2}, ω_{1}) until both conditions are satisfied. In practice one must be careful about rounding errors, as it is quite possible to have both |τ| < 1 and | − 1/τ| < 1 after rounding, which is liable to prevent the algorithm from terminating.

Set q = exp(2πiτ). Then the lattice invariants c_{4} ( = 12g_{2}) and c_{6} ( = 216g_{3}) are given by (7.2.1)

c_{4} = (\frac{2π}{ω_{2}} )^{4} (1 + 240 ∑_{n=1}^{∞} \frac{n^{3}q^{n}}{1 − q^{n}} ) and c_{6} = (\frac{2π}{ω_{2}} )^{6} (1 − 504 ∑_{n=1}^{∞} \frac{n^{5}q^{n}}{1 − q^{n}} )

(see, for example, [13, p.47]). Since |q| = exp(−2πIm(τ)) ≤ exp(−π\sqrt{3}) < 0 · 005, these series converge extremely rapidly. Thus, assuming that ω_{1} and ω_{2} are known to sufficient precision, we can compute c_{4} and c_{6} as precisely as required.

Since E_{f} is defined over ℚ, the numbers c_{4} and c_{6} are rational, but there is no a priori reason why they should be integral. Fortunately, a result of Edixhoven [9] shows that they are integral. Hence, provided that we have computed the periods and then c_{4} and c_{6} to sufficient precision, we will be able to recognise the corresponding exact integer values.

This only presents practical difficulties when c_{4} and c_{6} are large, since to date our programs use standard double precision, which yields around 16 decimal places. In several cases this meant that we could recognise c_{4}, but the last digit or digits of c_{6} were undetermined. In these situations, we are helped by the fact that we know that c_{4} and c_{6} are the invariants of an elliptic curve of conductor N. This implies the following congruence conditions (see [12], [5] or [6]):

(1)

c_{4}^{3} − c_{6}^{2} = 1728Δ

where Δ is a non-zero integer divisible by the primes dividing N; (2) for primes p ≥ 5 which divide N, we have

p | c_{4} ⟺ p | c_{6} ⟺ p^{2} | N;

(3) c_{6} ≢ 9 (mod 27);

(4) either c_{6} ≡ −1 (mod 4), or c_{4} ≡ 0 (mod 16) and c_{6} ≡ 0, 8 (mod 32).

Note that in condition (1) we should not assume that Δ is only divisible by the “bad primes” which divide N, since we do not know that c_{4} and c_{6} are the invariants of a minimal model. However, Edixhoven’s result does bound the non-minimality, and in practice all the equations of curves we have constructed are minimal, verifying the conjecture (Manin’s “c = 1” conjecture) that this should always be the case. Conditions (2)–(4) do assume minimality at the relevant primes.

Since c_{4} is smaller than c_{6}, the usual situation is that we know c_{4}, but we use the above congruence conditions to help us find c_{6} in case it has more than 16 digits.

Given integral invariants c_{4}, c_{6} satisfying (1), (3) and (4) above the coefficients [a_{1}, a_{2}, a_{3}, a_{4}, a_{6}] of a standard Weierstrass equation for the curve may be obtained as follows (see [6]):

b_{2} = −c_{6} mod 12 ∈ {−5, …, 6};
b_{4} = (b_{2}^{2} − c_{4})/24;
b_{6} = (−b_{2}^{3} + 36b_{2}b_{4} − c_{6})/216;
a_{1} = b_{2} mod 2 ∈ {0, 1};
a_{3} = b_{6} mod 2 ∈ {0, 1};
a_{2} = (b_{2} − a_{1}^{2})/4;
a_{4} = (b_{4} − a_{1}a_{3})/2;
a_{6} = (b_{6} − a_{3}^{2})/4;

where all divisions are exact. We may then compute the conductor of the curve E = [a_{1}, a_{2}, a_{3}, a_{4}, a_{6}] using Tate’s algorithm ([21], [6]), to check that it is equal to N. We may also compute its rank to compare with the analytic rank. Finally, we can compute all curves isogenous to E over ℚ: see [6] for one way to do this. This final list of curves will, according to the Shimura-Taniyama-Weil conjectures, contain all elliptic curves defined over ℚ with conductor N (up to isomorphism). At the time of writing (April 1995) this has been proved (by Wiles and Taylor, following Ribet, Frey and others) provided that N is divisible by neither 4 nor 25.

8. Worked example: N = 11

We give here a worked example of the methods described in the preceding section. The level chosen is N = 11, which is the first non-trivial level. As 11 is prime, this is rather special: the M-symbols are easy to work with (there are only 12 of them), there are no oldforms, the value of L(f, 1) is non-zero so that mass production of Hecke eigenvalues is easy, and as the level is not square our short cut for finding the period lattice will work. Nevertheless, it is instructive to see how much information it is possible to obtain here, with only a page or two of essentially hand computation (with the help of a pocket calculator at the end).

8. WORKED EXAMPLE: N = 11 25

For simplicity we will only work in H(11), rather than the smaller quotient space H^{+}(11). The M-symbols for N = 11 are (c : 1) for c modulo 11 and (1 : 0), which we abbreviate as (c) and (∞) respectively, with |c| ≤ 5. (Similarly with other prime levels). The 2-term and 3-term relations are as follows.

\begin{aligned}(0) + (∞) & = 0 \\ (1) + (−1) & = 0 \\ (2) + (5) & = 0 \\ (−2) + (−5) & = 0 \\ (3) + (−4) & = 0 \\ (−3) + (4) & = 0 \end{aligned}  \begin{aligned}(0) + (∞) + (−1) & = 0 \\ (1) + (−2) + (5) & = 0 \\ (2) + (4) + (−4) & = 0 \\ (3) + (−5) + (−3) & = 0 \end{aligned}

Solving these equations we can express all 12 symbols in terms of A = (2), B = (3) and C = (0):

\begin{aligned}(0) & = C \\ (∞) & = −C \\ (1) = (−1) & = 0 \\ (2) = (−2) & = A \\ (5) = (−5) & = −A \end{aligned}  \begin{aligned}(3) & = B \\ (−3) & = A − B \\ (4) & = B − A \\ (−4) & = −B \end{aligned}

There are two classes of cusps, [0] and [∞], with [a/b] = [0] if 11 ∤ b and [a/b] = [∞] if 11 | b. Hence δ((c)) = δ({0, 1/c}) = [1/c] − [0] = 0 for c ≢ 0. It follows that

H(11) = ker(δ) = ⟨A, B⟩ ,

with 2g = dim H(11) = 2, so that the genus is 1. There is therefore one newform f. This makes the rest of the calculation simpler, as we do not have to find and split off eigenspaces.

The conjugation ∗ involution maps (c) ↦ (−c), so A^{∗} = A and B^{∗} = A−B. This

has matrix ( \begin{matrix}1 & 1 \\ 0 & −1 \end{matrix} ) with respect to the basis A, B. The +1- and −1-eigenspaces

are generated by A and A−2B respectively, and we have left eigenvectors v^{+} = (2, 1) and v^{−} = (0, 1). Thus the period lattice is non-rectangular, and Ω(f) = Ω_{0}(f) = ⟨A, f⟩.

If we had worked in H^{+}(11), viewed as the quotient H(11)/H^{−}(11), by including relations (c) = (−c), the effect would be to identify (c) and (−c). This gives a 1-dimensional space generated by \overline{B} with \overline{A} = 2\overline{B}, where the bars denote the projections to the quotient. Notice that although \overline{B} is a generator here, the integral of f over B is not a real period; its real part is half the real period. However we do still have Ω(f) = ⟨B + B^{∗}, f⟩ = 2Re ⟨B, f⟩, so we could compute Ω(f) in this context without actually knowing whether it was 1 or 2 times the smallest real period.

To compute Hecke eigenvalues we may work in the subspace ⟨A⟩; since this subspace is conjugation invariant (being the +1-eigenspace) we will have T_{p}(A) = a_{p}A for all p ≠ 11. We first compute T_{2} explicitly, converting the M-symbol A = (2 : 1) to the modular symbol {0, 1/2}:

T_{2}(A) = T_{2} (\{0, \frac{1}{2}\}) = \{0, 1\} + \{0, \frac{1}{4}\} + \{\frac{1}{2}, \frac{3}{4}\}

= \{0, 1\} + \{0, \frac{1}{4}\} + \{\frac{1}{2}, 1\} + \{1, \frac{3}{4}\}

= (1 : 1) + (4 : 1) + (1 : 2) + (−4 : 1) = (0) + (4) + (−5) + (−4) = 0 + (B − A) + (−A) + (−B) = −2A,

so that a_{2} = −2. Now (1 + 2 − a_{2})L(f, 1) = ⟨{0, 1/2} , f⟩ = ⟨A, f⟩ = Ω(f), giving

\frac{L(f, 1)}{Ω(f)} = \frac{1}{5}.

For all primes p ≠ 11 we will evaluate μ_{p} = ∑_{a=0}^{p−1} {0, a/p} = n_{p}A for a certain integer n_{p}, since then also 1/5 = n_{p}/(1 + p − a_{p}), giving

a_{p} = 1 + p − 5n_{p}.

At this stage we already know that the corresponding elliptic curve has rank 0, and that 1+p−a_{p} ≡ 0 (mod 5) for all p ≠ 11, so that it will possess a rational 5-isogeny.

To save time, we can use the fact that {0, a/p}^{∗} = {0, −a/p}; thus for odd p we need only evaluate half the sum, say

μ′_{p} = ∑_{a=1}^{(p−1)/2} \{0, \frac{a}{p}\} ,

and then set μ_{p} = μ′_{p} + (μ′_{p})^{∗}.

For p = 3, we have μ′_{3} = {0, 1/3} = (3 : 1) = (3) = B, so μ_{3} = B + B^{∗} = A, giving n_{3} = 1 and a_{3} = 1 + 3 − 5n_{3} = −1.

For p = 5 we compute:

\{0, \frac{1}{5}\} = (5 : 1) = (5) = −A;
\{0, \frac{2}{5}\} = \{0, \frac{1}{2}\} + \{\frac{1}{2}, \frac{2}{5}\}
= (2 : 1) + (−5 : 2) = (2) + (3) = A + B;
μ′_{5} = (−A) + (A + B) = B;
μ_{5} = B + B^{∗} = A,  so that n_{5} = 1;
a_{5} = 1 + 5 − 5n_{5} = 1.

Similarly, with p = 7 we have n_{7} = 2, so that a_{7} = 1 + 7 − 5n_{7} = −2, and with p = 13 we have n_{13} = 2 so that a_{13} = 4.

For the ‘bad prime’ q = 11 we compute the involution W_{11} induced by the action

of the matrix ( \begin{matrix}0 & −1 \\ 11 & 0 \end{matrix} ):

W_{11}(A) = ( \begin{matrix}0 & −1 \\ 11 & 0 \end{matrix} ) \{0, \frac{1}{2}\} = \{∞, \frac{−2}{11}\}

= \{∞, 0\} + \{0, \frac{−1}{5}\} + \{\frac{−1}{5}, \frac{−2}{11}\}

= (1 : 0) + (−5 : 1) + (11 : 5)

= (∞) + (−5) + (0)

= −A,

so that the eigenvalue ε_{11} of W_{11} is −1. In fact, this was implicit earlier, since L(f, 1) ≠ 0 implies that the sign of the functional equation is +1, which is minus the eigenvalue of the Fricke involution W_{11}.

The Fourier coefficients a(n) = a(n, f) for 1 ≤ n ≤ 16 are now

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ a(n) & 1 & −2 & −1 & 2 & 1 & 2 & −2 & 0 & −2 & −2 & 1 & −2 & 4 & 4 & −1 & −4 \end{matrix}

where we have used multiplicativity, and:

a(11) = −ε_{11} = +1;
a(4) = a(2)^{2} − 2a(1) = 2;
a(8) = a(2)a(4) − 2a(2) = 0;
a(16) = a(2)a(8) − 2a(4) = −4;
a(9) = a(3)^{2} − 3a(1) = −2.

We know that the period lattice Λ_{f} has a ℤ-basis of the form [ω_{1}, ω_{2}] = [2x, x+iy], where ω_{1} = ⟨A, f⟩ and ω_{2} = ⟨B, f⟩. We can compute the real period ω_{1} = Ω(f) = 5L(f, 1) by computing L(f, 1):

L(f, 1) = 2 ∑_{n=1}^{∞} \frac{a(n)}{n}t^{n}

where t = exp(−2π/\sqrt{11}) = 0.15 . . .. Using the first 16 terms which we have already gives this to 13 decimal places:

L(f, 1) = 0.2538418608559 …;

thus

ω_{1} = Ω(f) = 1.269209304279 ….

For the imaginary period y we twist with a prime l ≡ 3 (mod 4). Here l = 3 will do, since

γ_{3} = \{0, \frac{1}{3}\} − \{0, \frac{−1}{3}\} = (3) − (−3) = 2B − A ≠ 0.

To project onto the minus eigenspace we take the dot product of this cycle (expressed as a vector (−1, 2)) with v^{−} = (0, 1) to get m^{−}(3) = 2. Hence yi = P (3, f)/2, or y = \sqrt{3}L(f ⊗ 3, 1)/2. Summing the series for L(f ⊗ 3, 1) to 16 terms gives only 4 decimals:

L(f ⊗ 3, 1) = 1.6845 ….

This is less accurate than L(f, 1), since this is a power series in exp(−2π/3\sqrt{11}) = 0.53 …, compared with 0.15 . . .. Hence y = 1.4588 …, so that

ω_{2} = 0.634604652139 … + 1.4588 … i.

So far we have only used the Hecke eigenvalues a_{p} for p ≤ 13, and only 16 terms of each series. If we use these approximate values for the period lattice generators ω_{1} and ω_{2} we already find the approximate values c_{4} = 495.99 and c_{6} = 20008.09 which round to the integer values c_{4} = 496 and c_{6} = 20008. Taking the first 25 a_{p} and the first 100 terms of the series gives

c_{4} = 495.9999999999954 …  and  c_{6} = 20008.0000000085.

The exact values c_{4} = 496 and c_{6} = 20008 are the invariants of an elliptic curve of conductor 11, which is therefore the modular curve E_{f}:

y^{2} + y = x^{3} − x^{2} − 10x − 20.

This is the first curve in our tables, with code 11A1 (or Antwerp code 11B). The value L(f, 1)/Ω(f) = 1/5 agrees with the value predicted by the Birch–Swinnerton-Dyer conjecture for L(E_{f}, 1)/Ω(E_{f}) , provided that E_{f} has trivial Tate–Shafarevich group � . A 2-descent shows that the 2-primary component of � is indeed trivial.

Lastly, we illustrate the method explained at the end of the previous section, where we “guess” the imaginary period and lattice type. Having computed P (3, f) = 2.9176 … i ≠ 0, we consider the lattices ⟨x, yi⟩ and ⟨2x, x + yi⟩, where x = 1.2692 … (from above) and yi = P (3, f)/m^{−}, for m^{−} = 1, 2, 3, . . .. When m^{−} = 1 we do not find integral invariants, but for m^{−} = 2 and lattice type 1 we find the curve E_{f} = [0, −1, 1, −10, −20] given above.

Using the first variant of the method, where we do not even know x, we can take l^{+} = 5 since P (5, f) = 6.346 … ≠ 0. The correct value of m^{+} here is 10; if we do not know this, but try m^{+} = 1, 2, 3 … in a double loop with m^{−}, the first valid lattice we come across is with (m^{+}, m^{−}) = (2, 2) and type 1, which leads to the curve E′ = [0, −1, 1, 0, 0] of conductor 11; this is 5-isogenous to the “correct” curve E_{f}, which comes from (m^{+}, m^{−}) = (10, 2) and type 1.

We may also consider the ratios P (l, f)/P (3, f) for other primes l ≡ 3 (mod 4); we restrict to those l satisfying (\frac{−11}{l}) = (\frac{l}{11}) = +1, since otherise P (l, f) is trivially 0 (since the sign of the functional equation for the corresponding L(f ⊗ χ, s) is then −1). We find the following table of values (rounded: they are only computed approximately):

\begin{matrix}l & 3 & 23 & 31 & 47 & 59 & 67 & 71 & 103 & 163 & 179 & 191 & 199 & 223 & 251 \\ \frac{P (l, f)}{P (3, f)} & 1 & 1 & 1 & 0 & 1 & 9 & 1 & 0 & 4 & 25 & 1 & 4 & 1 & 1 \end{matrix}

9. RESULTS FOR N ≤ 5077 29

The zero values for l = 47 and l = 103 indicate that the corresponding twists of the newform f have positive even analytic rank (and we have checked that the corresponding twists of the curve E_{f} do have rank 2). As all these values are integral here (a priori they are only known to be rational) we do not find any nontrivial divisor of m^{−} (which we know in fact equals 2). The fact that all the integers are perfect squares is an amusing observation, but has a simple explanation in terms of the numbers appearing in the Birch–Swinnerton-Dyer conjecture for the twists of E_{f}.

Finally, there is one other curve E′′ isogenous to E_{f} in addition to E′ (found above). If the period lattice of E_{f} = [0, −1, 1, −10, −20] is [2x, yi] with x = 0.6346... and y = 1.4588..., then E′ = [0, −1, 1, 0, 0] has period lattice [10x, 5x + yi], and E′′ = [0, −1, 1, −7820, 263580] has lattice [x/5, 2x/5 + yi]. These curves are linked by 5-isogenies E ↔ E′ and E ↔ E′′.

9. Results for N ≤ 5077

We have carried out the computations described above for all levels N up to 5077. (The reason for stopping at 5077 rather than, say, 5000, was to verify that the known curve of rank 3 and conductor 5077 was the first case of a modular elliptic curve of rank 3.)

For each N we found the rational newforms, and computed many Hecke eigenvalues for each; in the worst case we needed all a_{p} for p < 30000. For each form we computed a period lattice, and hence found a corresponding curve of conductor N. At present (February 1995), we have found the full period lattice and hence E_{f} only for N ≤ 3200; for 3200 < N < 5077 we have only used the method of section 7 to find a suitable curve, which we only know to be isogenous to E_{f}. For each curve, we verified (in most cases, including all cases of rank 2) that the rank was equal to the analytic rank, and by finding the Mordell-Weil group of each curve (again, in most cases) we were able to compute the value predicted by the Birch Swinnerton-Dyer conjecture for the order of the Tate–Shafarevich group.

We summarise the results obtained in the following table, where for brevity we only give the numbers of newforms found, subdivided by rank. The first examples of each rank are: N = 11 for rank 0; N = 37 for rank 1; N = 389 for rank 2; and N = 5077 for rank 3.

Rational newforms for Γ_{0}(N)

N ≤ 5077
Range of N Total r = 0 r = 1 r = 2 r = 3
1–1000 2463 1321 1124  18  0
1001–2000 3391 1575 1737  79  0
2001–3000 3661 1663 1852 146  0
3001–4000 3836 1664 2006 166  0
4001–5000 3948 1684 2086 178  0
5001–5077  284 121 148  14  1
1–5077 17583 8028 8953 601  1

10. Further applications of the method

Using the methods desribed in these notes, several other applications are possible, which we mention here briefly:

1. Associated with each rational newform f for Γ_{0}(N), we have a map φ: X_{0}(N) → E_{f}, called the modular parametrization of the curve E_{f}. We can compute this map (or more precisely its lift H → ℂ) very explicitly numerically: if τ = x + yi ∈ H, then

φ(τ) = 2πi ∫_{∞}^{τ} f(z)dz (τ ∈ H)

= ∑_{n=1}^{∞} \frac{a(n, f)}{n} exp(−2πny) exp(2πinx).

This gives a complex number z modulo Λ_{f}, and hence by composing with the Weierstrass functions we may obtain from each τ ∈ H an explicit point P (τ) ∈ E_{f}(ℂ). For suitable choices of τ this point P (τ) may be interesting, a Heegner point for example. Using this formula we can thus compute Heegner points on the modular elliptic curves E_{f} (of rank 1). We have carried this out in a few cases, but not yet systematically.

2. Given an explicit representation for the full homology H(N), it is possible to compute, via an exact algebraic formula, the degree of the modular parametrization φ: X_{0}(N) → E_{f}. This is described in detail in [8].

3. Variation of the methods described here can be used to find cusp forms of weight 2 for other congruence subgroups, such as Γ_{1}(N). The case of Γ_{1}(N) is described in more detail in [7].

4. In another direction, modular symbol methods may be used over other fields. The case of imaginary quadratic fields, which involves 3-dimensional hyperbolic geometry instead of the 2-dimensional upper half-plane H, is the subject of active research by the author and his students past and present.

References

1. A. O. L. Atkin and J. Lehner, Hecke operators on Γ_{0}(m), Math. Ann. 185 (1970), 134–160.

2. J. P. Buhler, B. H. Gross and D. B. Zagier, On the conjecture of Birch and Swinnerton Dyer for an elliptic curve of rank 3, Math. Comp. 44 (1985), 473–481.

3. H. Carayol, Sur les représentations l-adiques attachées aux formes modulaires de Hilbert, Comptes-Rendus de l’Acad. des Sci. 296,I (1983), 629.

4. H. Cohen, A course in Computational Number Theory, Graduate Texts in Mathematics 138, Springer, 1993.

5. I. Connell, Notes on elliptic curves, (Unpublished lecture notes, McGill University), 1991.

6. J. E. Cremona, Algorithms for Modular Elliptic Curves, Cambridge University Press, 1992.

7. J. E. Cremona, Modular symbols for Γ_{1}(N) and elliptic curves with everywhere good reduction, Math. Proc. Camb. Phil. Soc. 111 (1992), 199–218.

8. J. E. Cremona, Computing the degree of tha modular parametrization of a modular elliptic curve, Math. Comp. (1995) (to appear).

9. B. Edixhoven, On the Manin constants of modular elliptic curves, Arithmetic Algebraic Geometry, Progress in Mathematics 89, Birkhauser, 1991, pp. 25–39.

10. A. W. Knapp, Elliptic Curves, Mathematical Notes 40, Princeton University Press, 1992.

11. V. I. Kolyvagin, Finiteness of E(ℚ) and � _{E/ℚ} for a subclass of Weil curves, Math. USSR Izvest. 32 (1989), 523–542.

12. A. Kraus, Quelques remarques à propos des invariants c_{4}, c_{6} et Δ d’une courbe elliptique, Acta Arith. 54 (1989), 75–80.

13. S. Lang, Elliptic functions, Addison-Wesley, 1973.

14. S. Lang, Introduction to modular forms, Springer-Verlag, 1976.

15. Ju. I. Manin, Parabolic points and zeta-functions of modular curves, Math. USSR-Izv. 6 (1972), 19–64.

16. B. Mazur, Courbes elliptiques et symboles modulaires, Séminaire Bourbaki No. 414 (1972), 277–294.

17. L. Merel, Opérateurs de Hecke pour Γ_{0}(N) et fractions continues, Annales de l’Institut Fourier de l’Université de Grenoble 41 no.3 (1991), 519–537.

18. M. R. Murty and V. K. Murty, Mean values of derivatives of modular L-series, Ann. Math. 133 (1991), 447–475.

19. G. Shimura, Introduction to the arithmetic theory of automorphic functions, Math. Soc. Japan No.11, 1971.

20. H. P. F. Swinnerton Dyer and B. J. Birch, Elliptic curves and modular functions, Modular Functions of One Variable IV, Lecture Notes in Mathematics 476, Springer-Verlag, 1975.

21. J. Tate, Algorithm for determining the singular fiber in an elliptic pencil, Modular Functions of One Variable IV, Lecture Notes in Mathematics 476, Springer-Verlag, 1975.

22. D. J. Tingley, Elliptic curves uniformised by modular functions, Oxford D.Phil. thesis 1975.

23. D. Zagier, Modular Parametrizations of Elliptic Curves, Canadian. Math. Bull. 28 (1985), 372–384.