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
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 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 -expansions, and the other computes eigenvalues
of newforms.

The group acts on through
*diamond-bracket operators* , as follows.
For , define

where is congruent to
. Note that the map
is surjective (see *Exercise 1.12*),
so the matrix exists.
To prove that preserves ,
we prove the more general fact that is a
normal subgroup of

This will imply that preserves since .

Lemma 9.1

The group is a normal subgroup of , and the quotient is isomorphic to .

Proof

See *Exercise 9.1*.

Alternatively, one can prove that preserves
by showing that and noting that
is preserved by (see
Remark *Remark 9.11*).

The *diamond-bracket action* is the action of
on . Since
is a finite-dimensional vector space over , the
action breaks up as a direct sum of
factors corresponding to the Dirichlet characters of
modulus .

Proposition 9.2

We have

where

Proof

The linear transformations , for the , all
commute, since acts through the abelian group
. Also, if is the exponent of
, then , so the
matrix of 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
for such that all act by diagonal
matrices. The system of eigenvalues of the action of on a fixed
defines a Dirichlet character, i.e., each has
the property that , for all
and some Dirichlet character . The
for a given then span , and taken together the
must span .

Definition 9.3

If , we say that is
the *character of the modular form* .

The spaces are a direct sum of subspaces
and , where is the
subspace of cusp forms, i.e., forms that vanish at *all*
cusps (elements of ), and
is the subspace of Eisenstein series, which is the unique
subspace of that is invariant under all Hecke
operators and is such that
.
The space can also be defined as the space
spanned by all Eisenstein series of weight and level ,
as defined in Chapter *Eisenstein Series and Bernoulli Numbers*.
The space 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
and for .

```
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)
13
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 .

```
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)
370
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)
370
```

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

(1)

be the *degeneracy map*, which is given by .
There are also maps in the other direction; see
[**Lan95**, Ch. VIII].

The *old subspace* of , denoted ,
is the sum of the images of all maps with a proper divisor
of and any divisor of (note that depends on
, , and , so there is a slight abuse of notation).
The *new subspace* of , which we denote by
, is the intersection
of the kernel of all maps with a proper divisor
of . One can use the Petersson inner product to show
that

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

Let be the commutative polynomial ring in infinitely many indeterminates . This ring acts (via acting as the Hecke operator) on for every integer . Let be the subring of generated by the with .

Theorem 9.4

We have a decomposition

(2)

Each space is a direct sum of distinct (nonisomorphic) simple -modules.

Proof

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 replaced by
is also true (this is what was proved in
[**AL70**]). The analogue for is also valid,
as long as we omit the spaces for which
.

Example 9.5

If is prime and , then , since .

One can prove using the Petersson inner product that the operators on , with , are diagonalizable. Another result of Atkin-Lehner-Li theory is that the ring of endomorphisms of generated by all Hecke operators equals the ring generated by the Hecke operators with . 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

where each of the spaces has dimension . Thus . The Hecke operator on has characteristic polynomial , which is irreducible. Since commutes with all Hecke operators , with , the subring of the Hecke algebra generated by operators with odd is isomorphic to (the scalar matrices). Thus on the full space , we do not have . However, on the new subspace we do have this equality, since the new subspace has dimension .

Example 9.7

The space has dimension and basis

The new subspace is spanned by the single cusp form

We have and has dimension with basis

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

where has dimension and has dimension . The Hecke operator on acts via the matrix

with respect to some basis. This matrix has eigenvalues and . Atkin-Lehner theory asserts that must be a linear combination of , with . Upon computing the matrix for , we find by simple linear algebra that .

Definition 9.9

A *newform* is a -eigenform
that is normalized so that the coefficient of is .

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

Proposition 9.10

If is an eigenvector for all Hecke operators normalized so that , then .

Proof

If , then and this
is *Lemma 3.22*. However, we have not
yet considered Hecke operators on -expansions for
more general spaces of modular forms.

The Hecke operators , for prime, act on by

and there is a similar formula for with composite. If is an eigenform for all , with eigenvalues , then by the above formula

(3)

Equating coefficients of , we see that if , then for all ; hence for all , because of the multiplicativity of Fourier coefficients and the recurrence

This would mean that , a contradiction. Thus , and it makes sense to normalize so that . With this normalization, (3) implies that , as desired.

Remark 9.11

The Hecke algebra on contains the
operators , since they satisfy the relation . Thus any -eigenform in
lies in a subspace for some
Dirichlet character . Also, one can even prove that
(see
*Exercise 9.2*).

Let be the space of cuspidal modular symbols as in
Chapter *General Modular Symbols*. Let be the map of
(?), and let
be the *plus one quotient* of cuspidal modular symbols,
i.e., the quotient of by the image of .
It follows from
*Theorem 1.44* and compatibility of the
degeneracy maps (for modular symbols they are defined
in Section *Degeneracy Maps*) that the -modules
and are dual as -modules.
Thus finding the systems of -eigenvalues on cusp forms is the same
as finding the systems of -eigenvalues on cuspidal modular
symbols.

Our strategy to compute is to first compute spaces
using the Atkin-Lehner-Li decomposition
(2). To compute to a given
precision, we compute the systems of eigenvalues of the Hecke
operators on the space , which we
will define below. Using *Proposition 9.10*, we then
recover a basis of -expansions for newforms. Note that we only
need to compute Hecke eigenvalues , for prime, not the
for composite, since the can be quickly recovered in terms
of the using multiplicativity and the recurrence.

For some problems, e.g., construction of models for modular curves, having a basis of -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.

The following algorithm generalizes *Algorithm 3.26*.
It computes without finding any eigenspaces.

Algorithm 9.12

Given integers , and and a Dirichlet character with modulus , this algorithm computes a basis of -expansions for to precision .

[Compute Modular Symbols] Use

*Algorithm 1.59*to computeviewed as a vector space, with an action of the .

[Basis for Linear Dual] Write down a basis for . E.g., if we identify with viewed as column vectors, then is the space of row vectors of length , and the pairing is the row column product.

[Find Generator] Find such that by choosing random until we find one that generates. The set of that fail to generate lie in a union of a finite number of proper subspaces.

[Compute Basis] The set of power series

forms a basis for to precision .

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 for
prime and a Manin symbol on which can easily be
computed. The Merel algorithm involves computing for
all and for a fairly easy , which is potentially more work.

Remark 9.13

By “easy “, I mean that computing is easier on than on a completely random element of , e.g., could be a Manin symbol.

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 and a Dirichlet character of modulus , and let

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

Algorithm 9.14

Given a -simple subspace of modular symbols, this algorithm outputs maps and , where is a -linear map and is an isomorphism of with a number field , such that is the eigenvalue of the Hecke operator acting on a fixed -eigenvector in . (Thus is a newform.)

[Compute Projection] Let be any surjective linear map such that equals the kernel of the -invariant projection onto . For example, compute by finding a simple submodule of that is isomorphic to , e.g., by applying

*Algorithm 7.17*to with replaced by the transpose of .[Choose ]label{step:eig:v} Choose a nonzero element such that and computation of is “easy”, e.g., choose to be a Manin symbol.

[Map from Hecke Ring] Let be the map , given by . Note that computation of is relatively easy, because was chosen so that is relatively easy to compute. In particular, if , we do not need to compute the full matrix of on ; instead we just compute .

[Find Generator] Find a random such that the iterates

are a basis for , where has dimension .

[Characteristic Polynomial] Compute the characteristic polynomial of , and let . Because of how we chose in step

*(4)*, the minimal and characteristic polynomials of are equal, and both are irreducible, so is an extension of of degree .[Field Structure] In this step we endow with a field structure. Let be the unique -linear isomorphism such that

for . The map is uniquely determined since the are a basis for . To compute , we compute the change of basis matrix from the standard basis for to the basis . This change of basis matrix is the inverse of the matrix whose rows are the for .

[Hecke Eigenvalues] Finally for each integer , we have

where is the eigenvalue of . Output the maps and and terminate.

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

Example 9.15

The space of cusp forms has dimension and is spanned by two -conjugate newforms, one of which is

where . We will use

Algorithm 9.14to compute a few of these coefficients.The space of modular symbols has dimension . It has the following basis of Manin symbols:

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

has characteristic polynomial . The kernel of corresponds to the span of the Eisenstein series of level and weight , and the kernel of corresponds to . (We could also have computed as the kernel of the boundary map .) Each of the following steps corresponds to the step of

Algorithm 9.14with the same number.

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

and

so projection onto is given by the first two rows:

[Choose ] Let . Notice that , and is a sum of only one Manin symbol.

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

and

[Find Generator] We have

which is clearly independent from . Thus we find that the image of the powers of generate .

[Characteristic Polynomial] The matrix of is , which has characteristic polynomial . Of course, we already knew this because we computed as the kernel of .

[Field Structure] We have

The matrix with rows the is , which has inverse . The matrix defines an isomorphism between and the field

I.e., and , where .

[Hecke Eigenvalues] We have . For example,

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

such that if , then

In contrast, if we take , then

Storing as vectors is more compact than storing , , directly as polynomials in !

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.

Let be an arbitrary congruence subgroup of , and suppose is a modular form of integer weight for . Since for some integer , the form has a Fourier expansion in nonnegative powers of . For a rational number , let be the coefficient of in the Fourier expansion of . Put

where by convention we take , so .

Let

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

Lemma 9.17

Suppose is a weight level modular function that is holomorphic except possibly with a pole of order at . Then is a polynomial in of degree at most . Moreover, the coefficients of this polynomial lie in the ideal generated by the coefficients with .

Proof

If , then , so is constant with constant term in , so the statement is true. Next suppose and the lemma has been proved for all functions with smaller order poles. Let , and note that

Thus by induction is a polynomial in of degree with coefficients in the ideal generated by the coefficients with . It follows that satisfies the conclusion of the lemma.

If is the ring of integers of a number field, is a maximal ideal of , and for some integer , let

Note that .
The following theorem was first proved in [**Stu87**].

Theorem 9.18

Let be a prime ideal in the ring of integers of a number field , and let be a congruence subgroup of of index and level . Suppose is a modular form and

or is a cusp form and

Then .

Proof

**Case 1: First we assume** .
Let

be the function. Since , we have . We have

(4)

since is holomorphic at infinity and has a zero of order . Also

(5)

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

with and if .

By *Lemma 9.17*,

is a polynomial in of degree at most with coefficients in . Thus

so since the coefficients of are integers, every coefficient of is in . Thus hence , so , as claimed.

**Case 2:** **Arbitrary**

Let be such that , so also . If is arbitrary, then because is a normal subgroup of , we have that for any and ,

where . Thus for any , we have that , so acts on .

It is a standard (but nontrivial) fact about modular forms, which comes from the geometry of the modular curve over and , that has a basis with Fourier expansions in and that the action of on preserves

and the cuspidal subspace . In particular, for any ,

Moreover, the denominators of are bounded, since is an -linear combination of a basis for , and the denominators of divide the product of the denominators of the images of each of these basis vectors under .

Let . Let be a prime of that divides . We will now show that for each , the Chinese Remainder Theorem implies that there is an element such that

(6)

First find such that has coefficients in . Choose with , and find a negative power such that has -integral coefficients and finite valuation. This is possible because we assumed that is nonzero. Use the Chinese Remainder Theorem to find such that and for each prime that divides . Then for some we have

and .

Write

with , and let

Then and since , we have , so

Thus we can apply Case 1 to conclude that

Thus

(7)

so , because of (6).

We next obtain a better bound when is a cusp form. Since preserves cusp forms, for each . Thus

since now we are merely assuming that

Thus we again apply Case 1 to conclude that and using (7), conclude that .

Corollary 9.19

Let be a prime ideal in the ring of integers of a number field. Suppose are modular forms and

for all

where . Then .

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 .

Corollary 9.20

Let be a prime ideal in the ring of integers of a number field. Suppose are modular forms with Dirichlet character and assume that

where

Then .

Proof

Let and let , so . Let be the order of the Dirichlet character . Then and

By *Theorem 9.18*, we have ,
so . It follows that .

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

Theorem 9.21

Let be a positive integer that is square-free, and suppose and are two newforms in , where is the ring of integers of a number field, and suppose that is a maximal ideal of . Let be an arbitrary subset of the prime divisors of . If for all and if

for all primes

then .

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 is the largest divisor
of such that factors through .

Theorem 9.22

Let be any integer, and suppose and are two normalized eigenforms in , where is the ring of integers of a number field, and suppose that is a maximal ideal of . Let be the set of prime divisors of that do not divide . If

for all primes and for all primes

then .

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

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 .

Theorem 9.23

Suppose is a congruence subgroup that contains and let

(8)

where . Then the Hecke algebra

is generated as a -module by the Hecke operators for .

Proof

For any ring , let , where is the submodule of cusp forms with integer Fourier expansion at the cusp , and let . For any ring , there is a perfect pairing

given by (this is true for , hence for any ).

Let be the submodule of generated by , where is the largest integer . Consider the exact sequence of additive abelian groups

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

Suppose that pairs to with each of . Then

in for each . By *Theorem 9.18*, it
follows that . Thus the pairing restricted to the image of
in is nondegenerate, so
because (8) is perfect, it follows that

Thus . Repeating the argument for all primes shows that , as claimed.

Remark 9.24

In general, the conclusion of
*Theorem 9.23* is not true if one considers only
where runs over the primes less than the bound.
Consider, for example, , where the bound is and
there are no primes .
However, the Hecke algebra is generated as an algebra
by operators with .

Exercise 9.1

Prove that the group is a normal subgroup of and that the quotient is isomorphic to .

Exercise 9.2

Prove that the operators are elements of . [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 such that the Hecke
ring on is not equal to the ring generated by
Hecke operators with and
.

Exercise 9.4

- Following
*Example 9.15*, compute a basis for . - Use
*Algorithm 9.12*to compute a basis for .

Footnotes

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