Computing with Newforms

In this chapter we pull together results and algorithms from Chapter Modular Forms of Weight 2, Dirichlet Characters, Linear Algebra, and General Modular Symbols and explain how to use linear algebra techniques to compute cusp forms and eigenforms using modular symbols.

We first discuss in Section Dirichlet Character Decomposition how to decompose M_k(\Gamma_1(N)) as a direct sum of subspaces corresponding to Dirichlet characters. Next in Section Atkin-Lehner-Li Theory we state the main theorems of Atkin-Lehner-Li theory, which decomposes S_k(\Gamma_1(N)) into subspaces on which the Hecke operators act diagonalizably with “multiplicity one”. In Section Computing Cusp Forms we describe two algorithms for computing modular forms. One algorithm finds a basis of q-expansions, and the other computes eigenvalues of newforms.

Dirichlet Character Decomposition

The group (\Z/N\Z)^* acts on M_k(\Gamma_1(N)) through diamond-bracket operators \langle d \rangle, as follows. For d\in(\Z/N\Z)^*, define

f|\dbd{d} = f^{\left[\abcd{a}{b}{c}{d'}\right]_k},

where \abcd{a}{b}{c}{d'} \in \SL_2(\Z) is congruent to \abcd{d^{-1}}{0}{0\hfill }{d}\pmod{N}. Note that the map \SL_2(\Z)\to \SL_2(\Z/N\Z) is surjective (see Exercise 1.12), so the matrix \abcd{a}{b}{c}{d'} exists. To prove that \dbd{d} preserves M_k(\Gamma_1(N)), we prove the more general fact that \Gamma_1(N) is a normal subgroup of

\Gamma_0(N) = \left\{ \mtwo{a}{b}{c}{d} \in \SL_2(\Z) :
\mtwo{a}{b}{c}{d}\con \mtwo{*}{*}{0}{*}\pmod{N}

This will imply that \dbd{d} preserves M_k(\Gamma_1(N)) since \abcd{a}{b}{c}{d'} \in \Gamma_0(N).

Lemma 9.1

The group \Gamma_1(N) is a normal subgroup of \Gamma_0(N), and the quotient \Gamma_0(N)/\Gamma_1(N) is isomorphic to (\Z/N\Z)^*.


See Exercise 9.1.

Alternatively, one can prove that \dbd{d} preserves M_k(\Gamma_1(N)) by showing that \dbd{d}\in \T and noting that M_k(\Gamma_1(N)) is preserved by \T (see Remark Remark 9.11).

The diamond-bracket action is the action of \Gamma_0(N)/\Gamma_1(N)\isom(\Z/N\Z)^* on M_k(\Gamma_1(N)). Since M_k(\Gamma_1(N)) is a finite-dimensional vector space over \C, the \dbd{d} action breaks M_k(\Gamma_1(N)) up as a direct sum of factors corresponding to the Dirichlet characters D(N,\C) of modulus N.

Proposition 9.2

We have

M_k(\Gamma_1(N)) = \bigoplus_{\eps \in D(N,\C)} M_k(N,\eps),


M_k(N,\eps) = \bigl\{ f \in \M_k(\Gamma_1(N)) : f|\dbd{d} = \eps(d) f,
\text{ all }d \in (\Z/N\Z)^*\bigr\}.


The linear transformations \dbd{d}, for the d\in(\Z/N\Z)^*, all commute, since \dbd{d} acts through the abelian group \Gamma_0(N)/\Gamma_1(N). Also, if e is the exponent of (\Z/N\Z)^*, then \dbd{d}^e = \dbd{d^e} = \dbd{1} = 1, so the matrix of \dbd{d} is diagonalizable. It is a standard fact from linear algebra that any commuting family of diagonalizable linear transformations is simultaneously diagonalizable (see Exercise 5.1), so there is a basis f_1,\ldots, f_n for M_k(\Gamma_1(N)) such that all \dbd{d} act by diagonal matrices. The system of eigenvalues of the action of (\Z/N\Z)^* on a fixed f_i defines a Dirichlet character, i.e., each f_i has the property that f_i |\dbd{d} = \eps_i(d), for all d\in(\Z/N\Z)^* and some Dirichlet character \eps_i. The f_i for a given \eps then span M_k(N,\eps), and taken together the M_k(N,\eps) must span M_k(\Gamma_1(N)).

Definition 9.3

If f\in M_k(N,\eps), we say that \eps is the character of the modular form f.

The spaces M_k(N,\eps) are a direct sum of subspaces S_k(N,\eps) and E_k(N,\eps), where S_k(N,\eps) is the subspace of cusp forms, i.e., forms that vanish at all cusps (elements of \Q \union \{\infty\}), and E_k(N,\eps) is the subspace of Eisenstein series, which is the unique subspace of M_k(N,\eps) that is invariant under all Hecke operators and is such that M_k(N,\eps) = S_k(N,\eps) \oplus E_k(N,\eps). The space E_k(N,\eps) can also be defined as the space spanned by all Eisenstein series of weight k and level N, as defined in Chapter Eisenstein Series and Bernoulli Numbers. The space E_k(N,\eps) can be defined in a third way using the Petersson inner product (see [Lan95, Section VII.5]).

The diamond-bracket operators preserve cusp forms, so the isomorphism of Proposition 9.2 restricts to an isomorphism of the corresponding cuspidal subspaces. We illustrate how to use Sage to make a table of dimension of M_k(\Gamma_1(N)) and M_k(N,\eps) for N=13.

sage: G = DirichletGroup(13)
sage: G
Group of Dirichlet characters of modulus 13 over
Cyclotomic Field of order 12 and degree 4
sage: dimension_modular_forms(Gamma1(13),2)
sage: [dimension_modular_forms(e,2) for e in G]
[1, 0, 3, 0, 2, 0, 2, 0, 2, 0, 3, 0]

Next we do the same for N=100.

sage: G = DirichletGroup(100)
sage: G
Group of Dirichlet characters of modulus 100 over
Cyclotomic Field of order 20 and degree 8
sage: dimension_modular_forms(Gamma1(100),2)
sage: v = [dimension_modular_forms(e,2) for e in G]; v
[24, 0, 0, 17, 18, 0, 0, 17, 18, 0, 0, 21, 18, 0, 0, 17,
18, 0, 0, 17, 24, 0, 0, 17, 18, 0, 0, 17, 18, 0, 0, 21,
18, 0, 0, 17, 18, 0, 0, 17]
sage: sum(v)

Atkin-Lehner-Li Theory

In Section Degeneracy Maps we defined maps between modular symbols spaces of different level. There are similar maps between spaces of cusp forms. Suppose N and M are positive integers with M\mid N and that t is a divisor of N/M. Let

(1)\alpha_t : S_k(\Gamma_1(M)) \to S_k(\Gamma_1(N))

be the degeneracy map, which is given by f(q) \mapsto f(q^t). There are also maps \beta_t in the other direction; see [Lan95, Ch. VIII].

The old subspace of S_k(\Gamma_1(N)), denoted S_k(\Gamma_1(N))_{\old}, is the sum of the images of all maps \alpha_t with M a proper divisor of N and t any divisor of N/M (note that \alpha_t depends on t, N, and M, so there is a slight abuse of notation). The new subspace of S_k(\Gamma_1(N)), which we denote by S_k(\Gamma_1(N))_{\new}, is the intersection of the kernel of all maps \beta_t with M a proper divisor of N. One can use the Petersson inner product to show that

S_k(\Gamma_1(N)) = S_k(\Gamma_1(N))_{\new} \oplus S_k(\Gamma_1(N))_{\old}.

Moroever, the new and old subspaces are preserved by all Hecke operators.

Let \T = \Z[T_1, T_2, \ldots ] be the commutative polynomial ring in infinitely many indeterminates T_n. This ring acts (via T_n acting as the n^{th} Hecke operator) on S_k(\Gamma_1(N)) for every integer N. Let \T^{(N)} be the subring of \T generated by the T_n with \gcd(n,N)=1.

Theorem 9.4

We have a decomposition

(2)S_k(\Gamma_1(N)) =
\bigoplus_{M\mid N} \bigoplus_{d\mid N/M} \alpha_d(S_k(\Gamma_1(M))_{\new}).

Each space S_k(\Gamma_1(M))_{\new} is a direct sum of distinct (nonisomorphic) simple \T^{(N)}_{\C}-modules.


The complete proof is in [Li75]. See also [DS05, Ch. 5] for a beautiful modern treatement of this and related results.

The analogue of Theorem 9.4 with \Gamma_1 replaced by \Gamma_0 is also true (this is what was proved in [AL70]). The analogue for S_k(N,\eps) is also valid, as long as we omit the spaces S_k(\Gamma_1(M),\eps) for which \cond(\eps) \nmid M.

Example 9.5

If N is prime and k\leq 11, then S_k(\Gamma_1(N))_{\new} = S_k(\Gamma_1(N)), since S_k(\Gamma_1(1))=0.

One can prove using the Petersson inner product that the operators T_n on S_k(\Gamma_1(N)), with \gcd(n,N)=1, are diagonalizable. Another result of Atkin-Lehner-Li theory is that the ring of endomorphisms of S_k(\Gamma_1(N))_{\new} generated by all Hecke operators equals the ring generated by the Hecke operators T_n with (n,N)=1. This statement need not be true if we do not restrict to the new subspace, as the following example shows.

Example 9.6

We have

S_2(\Gamma_0(22)) = S_2(\Gamma_0(11)) \oplus \alpha_2(S_2(\Gamma_0(11))),

where each of the spaces S_2(\Gamma_0(11)) has dimension 1. Thus S_2(\Gamma_0(22))_{\new} = 0. The Hecke operator T_2 on S_2(\Gamma_0(22)) has characteristic polynomial x^2+2x+2, which is irreducible. Since \alpha_2 commutes with all Hecke operators T_n, with \gcd(n,2)=1, the subring \T^{(22)} of the Hecke algebra generated by operators T_n with n odd is isomorphic to \Z (the 2\times 2 scalar matrices). Thus on the full space S_2(\Gamma_0(22)), we do not have \T^{(22)}=\T. However, on the new subspace we do have this equality, since the new subspace has dimension 0.

Example 9.7

The space S_2(\Gamma_0(45)) has dimension 3 and basis

f_{0} &= q - q^{4} - q^{10} - 2q^{13} - q^{16} + 4q^{19} + \cdots, \\
f_{1} &= q^{2} - q^{5} - 3q^{8} + 4q^{11} - 2q^{17} + \cdots, \\
f_{2} &= q^{3} - q^{6} - q^{9} - q^{12} + q^{15} + q^{18} + \cdots. \\

The new subspace S_2(\Gamma_0(45))_{\new} is spanned by the single cusp form

q + q^{2} - q^{4} - q^{5} - 3q^{8} - q^{10} + 4q^{11} - 2q^{13} + \cdots.

We have S_2(\Gamma_0(45/5)) = 0 and S_2(\Gamma_0(15)) has dimension 1 with basis

q - q^{2} - q^{3} - q^{4} + q^{5} + q^{6} + 3q^{8} + q^{9} - q^{10} - 4q^{11} + q^{12} - 2q^{13} + \cdots.

We use Sage to verify the above assertions.

sage: S = CuspForms(Gamma0(45), 2, prec=14); S
Cuspidal subspace of dimension 3 of Modular Forms space
of dimension 10 for Congruence Subgroup Gamma0(45) of
weight 2 over Rational Field
sage: S.basis()
q - q^4 - q^10 - 2*q^13 + O(q^14),
q^2 - q^5 - 3*q^8 + 4*q^11 + O(q^14),
q^3 - q^6 - q^9 - q^12 + O(q^14)
sage: S.new_subspace().basis()
(q - q^4 - q^10 - 2*q^13 + O(q^14),)
sage: CuspForms(Gamma0(9),2)
Cuspidal subspace of dimension 0 of Modular Forms space
of dimension 3 for Congruence Subgroup Gamma0(9) of
weight 2 over Rational Field
sage: CuspForms(Gamma0(15),2, prec=10).basis()
q - q^2 - q^3 - q^4 + q^5 + q^6 + 3*q^8 + q^9 + O(q^10)

Example 9.8

This example is similar to Example 9.6, except that there are newforms. We have

S_2(\Gamma_0(55)) = S_2(\Gamma_0(11)) \oplus \alpha_5(S_2(\Gamma_0(11)))
\oplus S_2(\Gamma_0(55))_{\new},

where S_2(\Gamma_0(11)) has dimension 1 and S_2(\Gamma_0(55))_{\new} has dimension 3. The Hecke operator T_5 on S_2(\Gamma_0(55))_{\new} acts via the matrix

{-2}{\hfill 2}{\hfill -1}
{-1}{\hfill 1}{-1}
{\hfill 1}{-2}{\hfill 0}

with respect to some basis. This matrix has eigenvalues 1 and -1. Atkin-Lehner theory asserts that T_5 must be a linear combination of T_n, with \gcd(n,55)=1. Upon computing the matrix for T_2, we find by simple linear algebra that T_5 = 2T_2 - T_4.

Definition 9.9

A newform is a \T-eigenform f\in S_k(\Gamma_1(N))_{\new} that is normalized so that the coefficient of q is 1.

We now motivate this definition by explaining why any \T-eigenform can be normalized so that the coefficient of q is 1 and how such an eigenform has the property that its Fourier coefficients are exactly the Hecke eigenvalues.

Proposition 9.10

If f=\sum_{n=0}^{\infty} a_n q^n \in M_k(N,\eps) is an eigenvector for all Hecke operators T_n normalized so that a_1=1, then T_n(f) = a_n f.


If \eps=1, then f\in M_k(\Gamma_0(N)) and this is Lemma 3.22. However, we have not yet considered Hecke operators on q-expansions for more general spaces of modular forms.

The Hecke operators T_p, for p prime, act on S_k(N,\eps) by

T_p\left(\sum_{n=0}^{\infty} a_n q^n\right) =
\sum_{n=0}^{\infty} \left( a_{np}q^n + \eps(p) p^{k-1}

and there is a similar formula for T_m with m composite. If f=\sum_{n=0}^{\infty} a_n q^n is an eigenform for all T_p, with eigenvalues \lambda_p, then by the above formula

(3)\lambda_p f = \lambda_p a_1 q + \lambda_p a_2 q^2 + \cdots = T_p(f) = a_{p} q +
\text{higher terms}.

Equating coefficients of q, we see that if a_1=0, then a_p=0 for all p; hence a_n=0 for all n, because of the multiplicativity of Fourier coefficients and the recurrence

a_{p^r} = a_{p^{r-1}} a_p - \eps(p)
p^{k-1} a_{p^{r-2}}.

This would mean that f=0, a contradiction. Thus a_1\neq 0, and it makes sense to normalize f so that a_1=1. With this normalization, (3) implies that \lambda_p = a_p, as desired.

Remark 9.11

The Hecke algebra \T_\Q on M_k(\Gamma_1(N)) contains the operators \dbd{d}, since they satisfy the relation T_{p^2} =
T_p^2 - \dbd{p}p^{k-1}. Thus any \T-eigenform in M_k(\Gamma_1(N)) lies in a subspace M_k(N,\eps) for some Dirichlet character \eps. Also, one can even prove that \dbd{d} \in \Z[\ldots,T_n,\ldots] (see Exercise 9.2).

Computing Cusp Forms

Let \sS_k(N,\eps;\C) be the space of cuspidal modular symbols as in Chapter General Modular Symbols. Let \iota^* be the map of (?), and let \sS_k(N,\eps;\C)^+ be the plus one quotient of cuspidal modular symbols, i.e., the quotient of \sS_k(N,\eps;\C) by the image of \iota^*-1. It follows from Theorem 1.44 and compatibility of the degeneracy maps (for modular symbols they are defined in Section Degeneracy Maps) that the \T-modules S_k(N,\eps)_{\new} and \sS_k(N,\eps;\C)^+_{\new} are dual as \T-modules. Thus finding the systems of \T-eigenvalues on cusp forms is the same as finding the systems of \T-eigenvalues on cuspidal modular symbols.

Our strategy to compute S_k(N,\eps) is to first compute spaces S_k(N,\eps)_{\new} using the Atkin-Lehner-Li decomposition (2). To compute S_k(N,\eps)_{\new} to a given precision, we compute the systems of eigenvalues of the Hecke operators T_p on the space V=\sS_k(N,\eps;\C)^+_{\new}, which we will define below. Using Proposition 9.10, we then recover a basis of q-expansions for newforms. Note that we only need to compute Hecke eigenvalues T_p, for p prime, not the T_n for n composite, since the a_n can be quickly recovered in terms of the a_p using multiplicativity and the recurrence.

For some problems, e.g., construction of models for modular curves, having a basis of q-expansions is enough. For many other problems, e.g., enumeration of modular abelian varieties, one is really interested in the newforms. We next discuss algorithms aimed at each of these problems.

A Basis of q-Expansions

The following algorithm generalizes Algorithm 3.26. It computes S_k(N,\eps) without finding any eigenspaces.

Algorithm 9.12

Given integers m, N and k and a Dirichlet character \eps with modulus N, this algorithm computes a basis of q-expansions for S_k(N,\eps) to precision O(q^{m+1}).

  1. [Compute Modular Symbols] Use Algorithm 1.59 to compute

    V = \sS_k(N,\eps)^+\tensor \Q(\eps),

    viewed as a K=\Q(\eps) vector space, with an action of the T_n.

  2. [Basis for Linear Dual] Write down a basis for V^* = \Hom(V,\Q(\eps)). E.g., if we identify V with K^n viewed as column vectors, then V^* is the space of row vectors of length n, and the pairing is the row \times column product.

  3. [Find Generator] Find x\in V such that \T{} x = V by choosing random x until we find one that generates. The set of x that fail to generate lie in a union of a finite number of proper subspaces.

  4. [Compute Basis] The set of power series

    f_i = \sum_{n=1}^{m} \psi_i(T_n(x)) q^n + O(q^{m+1})

    forms a basis for S_k(N,\eps) to precision m.

In practice Algorithm 9.12 seems slower than the eigenspace algorithm that we will describe in the rest of this chapter. The theoretical complexity of Algorithm 9.12 may be better, because it is not necessary to factor any polynomials. Polynomial factorization is difficult from the worst-case complexity point of view, though it is usually fast in practice. The eigenvalue algorithm only requires computing a few images T_p(x) for p prime and x a Manin symbol on which T_p can easily be computed. The Merel algorithm involves computing T_n(x) for all n and for a fairly easy x, which is potentially more work.

Remark 9.13

By “easy x “, I mean that computing T_n(x) is easier on x than on a completely random element of \sS_k(N,\eps)^+, e.g., x could be a Manin symbol.

Newforms: Systems of Eigenvalues

In this section we describe an algorithm for computing the system of Hecke eigenvalues associated to a simple subspace of a space of modular symbols. This algorithm is better than doing linear algebra directly over the number field generated by the eigenvalues. It only involves linear algebra over the base field and also yields a compact representation for the answer, which is better than writing the eigenvalues in terms of a power basis for a number field. In order to use this algorithm, it is necessary to decompose the space of cuspidal modular symbols as a direct sum of simples, e.g., using Algorithm 7.17.

Fix N and a Dirichlet character \eps of modulus N, and let


be the +1 quotient of modular symbols (see equation (?)).

Algorithm 9.14

Given a \T-simple subspace W\subset V of modular symbols, this algorithm outputs maps \psi and e, where \psi : \T_K \to W is a K-linear map and e:W \isom L is an isomorphism of W with a number field L, such that a_n = e (\psi(T_n)) is the eigenvalue of the n^{th} Hecke operator acting on a fixed \T-eigenvector in W\tensor\Qbar. (Thus f = \sum_{n=1}^{\infty} e(\psi(T_n)) q^n is a newform.)

  1. [Compute Projection] Let \vphi:V \to W' be any surjective linear map such that \ker(\vphi) equals the kernel of the \T-invariant projection onto W. For example, compute \vphi by finding a simple submodule of V^*=\Hom(V,K) that is isomorphic to W, e.g., by applying Algorithm 7.17 to V^* with T replaced by the transpose of T.

  2. [Choose v]label{step:eig:v} Choose a nonzero element v\in{}V such that \pi(v)\neq 0 and computation of T_n(v) is “easy”, e.g., choose v to be a Manin symbol.

  3. [Map from Hecke Ring] Let \psi be the map \T \to W', given by \psi(t) = \pi(t v). Note that computation of \psi is relatively easy, because v was chosen so that tv is relatively easy to compute. In particular, if t=T_p, we do not need to compute the full matrix of T_p on V; instead we just compute T_p(v).

  4. [Find Generator] Find a random T \in \T such that the iterates

    \psi(T^0), \quad \psi(T), \quad \psi(T^2), \quad \ldots, \quad \psi(T^{d-1})

    are a basis for W', where W has dimension d.

  5. [Characteristic Polynomial] Compute the characteristic polynomial f of T|_W, and let L=K[x]/(f). Because of how we chose T in step (4), the minimal and characteristic polynomials of T|_W are equal, and both are irreducible, so L is an extension of K of degree d=\dim(W).

  6. [Field Structure] In this step we endow W' with a field structure. Let e:W'\to L be the unique K-linear isomorphism such that

    e(\psi(T^i)) \con x^i \pmod{f}

    for i = 0,1,2,...,\deg(f)-1. The map e is uniquely determined since the \psi(T^i) are a basis for W'. To compute e, we compute the change of basis matrix from the standard basis for W' to the basis \{\psi(T^i)\}. This change of basis matrix is the inverse of the matrix whose rows are the \psi(T^i) for i=0,...,\deg(f)-1.

  7. [Hecke Eigenvalues] Finally for each integer n\geq 1, we have

    a_n = e(\psi(T_n)) = e(\pi(T_n(v))),

    where a_n is the eigenvalue of T_n. Output the maps \psi and e and terminate.

One reason we separate \psi and e is that when \dim(W) is large, the values \psi(T_n) take less space to store and are easier to compute, whereas each one of the values e(\psi(n)) is huge. [1] The function e typically involves large numbers if \dim(W) is large, since e is obtained from the iterates of a single vector. For many applications, e.g., databases, it is better to store a matrix that defines e and the images under \psi of many T_n.

Example 9.15

The space S_2(\Gamma_0(23)) of cusp forms has dimension 2 and is spanned by two \Gal(\Qbar/\Q)-conjugate newforms, one of which is

f = q + aq^2 + (-2a - 1)q^3 + (-a - 1)q^4 + 2aq^5 + \cdots,

where a=(-1+\sqrt{5})/2. We will use Algorithm 9.14 to compute a few of these coefficients.

The space \sM_2(\Gamma_0(23))^+ of modular symbols has dimension 3. It has the following basis of Manin symbols:

[(0,0)],\quad [(1,0)], \quad [(0,1)],

where we use square brackets to differentiate Manin symbols from vectors. The Hecke operator

T_2 = \left(\begin{array}{ccc}

has characteristic polynomial (x-3)(x^2 + x - 1). The kernel of T_2-3 corresponds to the span of the Eisenstein series of level 23 and weight 2, and the kernel V of T_2^2+T_2-1 corresponds to S_2(\Gamma_0(23)). (We could also have computed V as the kernel of the boundary map \sM_2(\Gamma_0(23))^+\to \sB_2(\Gamma_0(23))^+.) Each of the following steps corresponds to the step of Algorithm 9.14 with the same number.

  1. [Compute Projection] We compute projection onto V (this will suffice to give us a map \phi as in the algorithm). The matrix whose first two columns are the echelon basis for V and whose last column is the echelon basis for the Eisenstein subspace is



B^{-1} = \left(\begin{array}{ccc}

so projection onto V is given by the first two rows:

\pi = \left(\begin{array}{ccc}

  1. [Choose v] Let v=(0,1,0)^t. Notice that \pi(v)=(1,0)^t\neq 0, and v=[(1,0)] is a sum of only one Manin symbol.

  2. [Map from Hecke Ring] This step is purely conceptual, since no actual work needs to be done. We illustrate it by computing \psi(T_1) and \psi(T_2). We have

    \psi(T_1) = \pi(v) = (1,0)^t


    \psi(T_2) = \pi(T_2(v)) = \pi((0,0,1/2)^t) = (0,1/2)^t.

  3. [Find Generator] We have

    \psi(T_2^0) = \psi(T_1) = (1,0)^t,

    which is clearly independent from \psi(T_2)=(0,1/2)^t. Thus we find that the image of the powers of T=T_2 generate V.

  4. [Characteristic Polynomial] The matrix of T_2|_V is \abcd{0}{2}{1/2}{-1}, which has characteristic polynomial f=x^2+x-1. Of course, we already knew this because we computed V as the kernel of T_2^2+T_2-1.

  5. [Field Structure] We have

    \psi(T_2^0) = \pi(v) = (1,0)^t
\text{ and }
\psi(T_2) = (0,1/2).

    The matrix with rows the \psi(T_2^i) is \abcd{1}{0}{0}{1/2}, which has inverse e=\abcd{1}{0}{0}{2}. The matrix e defines an isomorphism between V and the field

    L=\Q[x]/(f) = \Q((-1+\sqrt{5})/2).

    I.e., e((1,0))=1 and e((0,1))=2x, where x=(-1+\sqrt{5})/2.

  6. [Hecke Eigenvalues] We have a_n = e(\Psi(T_n)). For example,

    \qquad\qquad  a_1 &= e(\Psi(T_1)) = e((1,0)) = 1,\\
a_2 &= e(\Psi(T_2)) = e((0,1/2)) = x,\\
a_3 &= e(\Psi(T_3)) = e(\pi(T_3(v))) \!=\! e(\pi((0,-1,-1)^t))\\
&= e((-1,-1)^t)\!=\! -1-2x,\\
a_4 &= e(\Psi(T_4)) = e(\pi((0,-1,-1/2)^t)) = e((-1,-1/2)^t) = -1-x,\\
a_5 &= e(\Psi(T_5)) = e(\pi((0,0,1)^t)) = e((0,1)^t) = 2x,\\
a_{23} &=   e(\Psi(T_{23})) = e(\pi((0,1,0)^t)) = e((1,0)^t) = 1,\\
a_{97} &= e(\Psi(T_{23})) = e(\pi((0,14,3)^t)) = e((14,3)^t) = 14+6x.

Example 9.16

It is easier to appreciate Algorithm 9.14 after seeing how big the coefficients of the power series expansion of a newform typically are, when the newform is defined over a large field. For example, there is a newform

f = \sum_{n=1}^{\infty} a_n q^n\in S_2(\Gamma_0(389))

such that if \alpha = a_2, then

1097385680 \cdot &a_3(f) =
-20146763x^{19} + 102331615x^{18} + 479539092x^{17} \\
&- 3014444212x^{16} - 3813583550x^{15} + 36114755350x^{14} \\
&+ 6349339639x^{13} - 227515736964x^{12} + 71555185319x^{11} \\
&+ 816654992625x^{10} - 446376673498x^{9} - 1698789732650x^{8} \\
&+ 1063778499268x^{7} + 1996558922610x^{6} - 1167579836501x^{5}\\
& - 1238356001958x^{4} + 523532113822x^{3} + 352838824320x^{2} \\
&- 58584308844x - 25674258672.

In contrast, if we take v=\{0,\infty\} = (0,1) \in \sM_2(\Gamma_0(389))^+, then

T_3(v) = -4(1,0) + 2(1,291) - 2(1,294) - 2(1,310) + 2(1,313) + 2(1,383).

Storing T_3(v), T_5(v), \ldots as vectors is more compact than storing a_3(f), a_5(f), \ldots directly as polynomials in a_2!

Congruences between Newforms

This section is about congruences between modular forms. Understanding congruences is crucial for studying Serre’s conjectures, Galois representations, and explicit construction of Hecke algebras. We assume more background in algebraic number theory here than elsewhere in this book.

Congruences between Modular Forms

Let \Gamma be an arbitrary congruence subgroup of \SL_2(\Z), and suppose f\in M_k(\Gamma) is a modular form of integer weight k for \Gamma. Since \abcd{1}{N}{0}{1}\in\Gamma for some integer N, the form f has a Fourier expansion in nonnegative powers of q^{1/N}. For a rational number n, let a_n(f) be the coefficient of q^n in the Fourier expansion of f. Put

\ord_q(f) = \min\{n\in \Q : a_n \neq 0\},

where by convention we take \min \emptyset = +\infty, so \ord_q(0)=+\infty.

The j-invariant


j = \frac{1}{q} + 744 + 196884 q + \cdots

be the j-function, which is a weight 0 modular function that is holomorphic except for a simple pole at \infty and has integer Fourier coefficients (see, e.g., [Ser73, Section VIII.3.3]).

Lemma 9.17

Suppose g is a weight 0 level 1 modular function that is holomorphic except possibly with a pole of order n at \infty. Then g is a polynomial in j of degree at most n. Moreover, the coefficients of this polynomial lie in the ideal I generated by the coefficients a_m(g) with m\leq  0.


If n=0, then g\in M_0(\SL_2(\Z))=\C, so g is constant with constant term in I, so the statement is true. Next suppose n>0 and the lemma has been proved for all functions with smaller order poles. Let \alpha = a_n(g), and note that

\ord_q(g - \alpha j^n) =
\ord_q\left(g - \alpha \cdot \left(\frac{1}{q} + 744 + 196884 q + \cdots \right)^n\right) > -n.

Thus by induction h=g - \alpha j^{n} is a polynomial in j of degree <n with coefficients in the ideal generated by the coefficients a_m(g) with m< 0. It follows that g=\alpha \cdot j^n - h satisfies the conclusion of the lemma.

Sturm’s Theorem

If \O is the ring of integers of a number field, \m is a maximal ideal of \O, and f=\sum a_n q^n \in \O[[q^{1/N}]] for some integer N, let

\ord_\m(f) = \ord_q(f \!\!\mod{\m}) = \min\{n\in\Q : a_n \not\in \m\}.

Note that \ord_\m(fg) = \ord_\m(f) + \ord_\m(g). The following theorem was first proved in [Stu87].

Theorem 9.18

Let \m be a prime ideal in the ring of integers \O of a number field K, and let \Gamma be a congruence subgroup of \SL_2(\Z) of index m and level N. Suppose f\in M_k(\Gamma,\O) is a modular form and

\ord_\m(f) > \frac{km}{12}

or f \in S_k(\Gamma,\O) is a cusp form and

\ord_\m(f) > \frac{km}{12} - \frac{m-1}{N}.

Then f\con 0\pmod{\m}.


Case 1: First we assume \Gamma=\SL_2(\Z). Let

\Delta  = q + 24q^2 + \cdots \in S_{12}(\SL_2(\Z),\Z)

be the \Delta function. Since \ord_\m(f) > k/12, we have \ord_\m(f^{12}) > k. We have

= 12 \cdot \ord_q(f) - k\cdot \ord_q(\Delta) \geq -k,

since f is holomorphic at infinity and \Delta has a zero of order 1. Also

(5)\ord_\m(f^{12}\cdot \Delta^{-k}) =  \ord_\m(f^{12}) - k\cdot \ord_\m(\Delta)
> k - k = 0.

Combining (4) and (5), we see that

f^{12} \cdot \Delta^{-k} = \sum_{n\geq -k} b_n q^n,

with b_n \in \O and b_n\in \m if n\leq 0.

By Lemma 9.17,

f^{12} \cdot \Delta^{-k} \in \m[j]

is a polynomial in j of degree at most k with coefficients in \m. Thus

f^{12} \in \m[j]\cdot \Delta^k,

so since the coefficients of \Delta are integers, every coefficient of f^{12} is in \m. Thus \ord_\m(f^{12}) = +\infty, hence \ord_\m(f) = +\infty, so f=0, as claimed.

Case 2: \Gamma Arbitrary

Let N be such that \Gamma(N)\subset \Gamma, so also f \in M_k(\Gamma(N)). If g\in M_k(\Gamma(N)) is arbitrary, then because \Gamma(N) is a normal subgroup of \SL_2(\Z), we have that for any \gamma \in\Gamma(N) and \delta \in \SL_2(\Z),

(g^{[\delta]_k})^{[\gamma]_k} = g^{[\delta\gamma]_k}
= g^{[\gamma'\delta]_k} = (g^{[\gamma']_k})^{[\delta]_k}
= g^{[\delta]_k},

where \gamma'\in\SL_2(\Z). Thus for any \delta\in \SL_2(\Z), we have that g^{[\delta]_k} \in M_k(\Gamma(N)), so \SL_2(\Z) acts on M_k(\Gamma(N)).

It is a standard (but nontrivial) fact about modular forms, which comes from the geometry of the modular curve X(N) over \Q(\zeta_N) and \Z[\zeta_N], that M_k(\Gamma(N)) has a basis with Fourier expansions in \Z[\zeta_N][[q^{1/N}]] and that the action of \SL_2(\Z) on M_k(\Gamma(N)) preserves

M_k(\Gamma(N),\Q(\zeta_N)) = M_k(\Gamma(N)) \cap{}

and the cuspidal subspace S_k(\Gamma(N),\Q(\zeta_N)). In particular, for any \gamma\in\SL_2(\Z),

f^{[\gamma]_k} \in M_k(\Gamma(N), K(\zeta_N))

Moreover, the denominators of f^{[\gamma]_k} are bounded, since f is an \O[\zeta_N]-linear combination of a basis for M_k(\Gamma(N),\Z[\zeta_N]), and the denominators of f^{[\gamma]_k} divide the product of the denominators of the images of each of these basis vectors under [\gamma]_k.

Let L=K(\zeta_N). Let \wM be a prime of \O_L that divides \m \O_L. We will now show that for each \gamma\in\SL_2(\Z), the Chinese Remainder Theorem implies that there is an element A_\gamma\in L^* such that

(6)A_\gamma \cdot f^{[\gamma]_k} \in M_k(\Gamma(N), \O_L)
\qquad \text{and}
\qquad \ord_{\wM} (A_{\gamma} \cdot f^{[\gamma]_k}) < \infty.

First find A \in L^* such that A\cdot f^{[\gamma]_k} has coefficients in \O_L. Choose \alpha\in \wM with \alpha \not\in \wM^2, and find a negative power \alpha^t such that \alpha^t\cdot A\cdot f^{[\gamma]_k} has \wM-integral coefficients and finite valuation. This is possible because we assumed that f is nonzero. Use the Chinese Remainder Theorem to find \beta\in \O_L such that \beta\con 1\pmod{\wM} and \beta\con 0\pmod{\wp} for each prime \wp\neq \wM that divides (\alpha). Then for some s we have

\beta^s \cdot \alpha^t \cdot A\cdot f^{[\gamma]_k}
= A_\gamma \cdot f^{[\gamma]_k}
\in M_k(\Gamma(N),\O_L)

and \ord_{\wM}(A_\gamma \cdot f^{[\gamma]_k}) < \infty.


\SL_2(\Z) = \bigcup_{i=1}^m \Gamma{} \gamma_i

with \gamma_1 = \abcd{1}{0}{0}{1}, and let

F = f \cdot \prod_{i=2}^m A_{\gamma_i} \cdot f^{[\gamma_i]_k}.

Then F \in M_{km}(\SL_2(\Z)) and since \wM\cap \O_K = \m, we have \ord_{\wM}(f) = \ord_{\m}(f), so

\ord_{\wM}(F) \geq \ord_{\wM}(f) = \ord_{\m}(f) > \frac{km}{12}.

Thus we can apply Case 1 to conclude that

\ord_{\wM}(F) = +\infty.


(7)\infty = \ord_{\wM}(F) = \ord_\m(f) + \sum_{i=2}^m \ord_{\wM}(A_{\gamma_i}

so \ord_\m(f)=+\infty, because of (6).

We next obtain a better bound when f is a cusp form. Since [\gamma]_k preserves cusp forms, \ord_{\wM}(A_{\gamma_i} f^{[\gamma]_k}) \geq \frac{1}{N} for each i. Thus

\ord_{\wM}(F) \geq \ord_{\wM}(f)  + \frac{m-1}{N} = \ord_{\m}(f) + \frac{m-1}{N} > \frac{km}{12},

since now we are merely assuming that

\ord_{\m}(f) > \frac{km}{12}
- \frac{m - 1}{N}.

Thus we again apply Case 1 to conclude that \ord_{\wM}(F) = +\infty, and using (7), conclude that \ord_\m(f)=+\infty.

Corollary 9.19

Let \m be a prime ideal in the ring of integers \O of a number field. Suppose f,g\in M_k(\Gamma,\O) are modular forms and

a_n(f) \con  a_n(g) \pmod{\m}

for all

\ds\frac{km}{12} - \frac{m-1}{N} & \text{ if }f-g \in S_k(\Gamma,\O),\vspace{2pt}\\
\ds\frac{km}{12} & \text{otherwise},

where m=[\SL_2(\Z):\Gamma]. Then f\con g\pmod{\m}.

Buzzard proved the following corollary, which is extremely useful in practical computations. It asserts that the Sturm bound for modular forms with character is the same as the Sturm bound for \Gamma_0(N).

Corollary 9.20

Let \m be a prime ideal in the ring of integers \O of a number field. Suppose f,g\in M_k(N,\eps,\O) are modular forms with Dirichlet character \eps:(\Z/N\Z)^* \to \C^* and assume that

a_n(f) \con  a_n(g) \pmod{\m}
\qquad\text{for all}\qquad
n \leq  \frac{km}{12},


m=[\SL_2(\Z):\Gamma_0(N)] =
\#\P^1(\Z/N\Z) = N \cdot \prod_{p|N}\left(1+\frac{1}{p}\right).

Then f\con g\pmod{\m}.


Let h=f-g and let r=km/12, so \ord_\m(h) > r. Let s be the order of the Dirichlet character \eps. Then h^s \in M_{ks}(\Gamma_0(N)) and

\ord_\m(h^s) > sr = \frac{ksm}{12}.

By Theorem 9.18, we have \ord_\m(h^s) = \infty, so \ord_\m(h) = \infty. It follows that f\con g\pmod{\m}.

Congruence for Newforms

Sturm’s paper [Stu87] also applies some results of Asai on q-expansions at various cusps to obtain a more refined result for newforms.

Theorem 9.21

Let N be a positive integer that is square-free, and suppose f and g are two newforms in S_k(N,\eps,\O), where \O is the ring of integers of a number field, and suppose that \m is a maximal ideal of \O. Let I be an arbitrary subset of the prime divisors of N. If a_p(f) = a_p(g) for all p\in I and if

a_p(f) \con a_p(g)\pmod{\m}

for all primes

p \leq \frac{k\cdot [\SL_2(\Z):\Gamma_0(N)]}{12 \cdot 2^{\#I}},

then f\con g\pmod{\m}.

The paper [BS02] contains a similar result about congruences between newforms, which does not require that the level be square-free. Recall from Definition Definition 4.18 that the conductor of a Dirichlet character \eps is the largest divisor c of N such that \eps factors through (\Z/c\Z)^\times.

Theorem 9.22

Let N>4 be any integer, and suppose f and g are two normalized eigenforms in S_k(N,\eps;\O), where \O is the ring of integers of a number field, and suppose that \m is a maximal ideal of \O. Let I be the set of prime divisors of N that do not divide \frac{N}{\cond(\eps)}. If

a_p(f) \con a_p(g)\pmod{\m}

for all primes p\in I and for all primes

p \leq \frac{k\cdot [\SL_2(\Z):\Gamma_0(N)]}{12 \cdot 2^{\#I}},

then f\con g\pmod{\m}.

For the proof, see Lemma 1.4 and Corollary 1.7 in [BS02, Section 1.3].

Generating the Hecke Algebra

The following theorem appeared in [LS02, Appendix], except that we give a better bound here. It is a nice application of the congruence result above, which makes possible explicit computations with Hecke rings \T.

Theorem 9.23

Suppose \Gamma is a congruence subgroup that contains \Gamma_1(N) and let

(8)r=\frac{km}{12} - \frac{m - 1}{N},

where m=[\SL_2(\Z):\Gamma]. Then the Hecke algebra

\T=\Z[\ldots, T_n,\ldots] \subset \End(S_k(\Gamma))

is generated as a \Z-module by the Hecke operators T_n for n\leq r.


For any ring R, let S_k(N,R) = S_k(N;\Z)\otimes{}R, where S_k(N;\Z)\subset \Z[[q]] is the submodule of cusp forms with integer Fourier expansion at the cusp \infty, and let \T{}_R =
\T{}\otimes_\Z R. For any ring R, there is a perfect pairing

S_k(N,R) \otimes_R \T{}_R \rightarrow R

given by \langle f,T\rangle\mapsto a_1(T(f)) (this is true for R=\Z, hence for any R).

Let M be the submodule of \T{} generated by T_1,T_2,\ldots,T_r, where r is the largest integer \leq {\frac{kN}{12}}\cdot [\SL_2(\Z):\Gamma]. Consider the exact sequence of additive abelian groups

0\rightarrow M \mathop{\rightarrow}\limits^{i}\ \T{}
\rightarrow \T{}/M \rightarrow 0.

Let p be a prime and use the fact that tensor product is right exact to obtain an exact sequence

M\otimes \F_p \mathop{\rightarrow}\limits^{\overline{i}}\
\T \otimes\F_p \rightarrow (\T{}/M)\otimes\F_p\rightarrow 0.

Suppose that f\in S_k(N,\F_p) pairs to 0 with each of T_1,\ldots, T_r. Then

a_m(f)=a_1(T_m f)=\langle f, T_m\rangle =

in \F_p for each m\leq r. By Theorem 9.18, it follows that f = 0. Thus the pairing restricted to the image of M\otimes\F_p in \T_{\F_p} is nondegenerate, so because (8) is perfect, it follows that

\dim_{\F_p} \overline{i}(M\otimes\F_p) =  \dim_{\F_p} S_k(N,\F_p).

Thus (\T{}/M) \tensor \F_p = 0. Repeating the argument for all primes p shows that \T{}/M=0, as claimed.

Remark 9.24

In general, the conclusion of Theorem 9.23 is not true if one considers only T_n where n runs over the primes less than the bound. Consider, for example, S_2(11), where the bound is 1 and there are no primes \leq 1. However, the Hecke algebra is generated as an algebra by operators T_p with p\leq r.


Exercise 9.1

Prove that the group \Gamma_1(N) is a normal subgroup of \Gamma_0(N) and that the quotient \Gamma_0(N)/\Gamma_1(N) is isomorphic to (\Z/N\Z)^*.

Exercise 9.2

Prove that the operators \dbd{d} are elements of \Z[\ldots,T_n,\ldots]. [Hint: Use Dirichlet’s theorem on primes in arithmetic progression.]

Exercise 9.3

Find an example like Example 9.6 but in which the new subspace is nonzero. More precisely, find an integer N such that the Hecke ring on S_2(\Gamma_0(N)) is not equal to the ring generated by Hecke operators T_n with \gcd(n,N)=1 and S_2(\Gamma_0(N))_{\new}\neq 0.

Exercise 9.4

  1. Following Example 9.15, compute a basis for S_2(\Gamma_0(31)).
  2. Use Algorithm 9.12 to compute a basis for S_2(\Gamma_0(31)).


[1]John Cremona initially suggested to me the idea of separating these two maps.