.. _ch:modformcomp: Computing with Newforms ======================= .. chapter:: 9 In this chapter we pull together results and algorithms from Chapter :ref:`ch:modform2`, :ref:`ch:dirichlet`, :ref:`ch:linalg`, and :ref:`ch:modsym` and explain how to use linear algebra techniques to compute cusp forms and eigenforms using modular symbols. We first discuss in Section :ref:`sec:decompdirchar` how to decompose `M_k(\Gamma_1(N))` as a direct sum of subspaces corresponding to Dirichlet characters. Next in Section :ref:`sec:ALL` 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 :ref:`sec:compcuspforms` we describe two algorithms for computing modular forms. One algorithm finds a basis of `q`-expansions, and the other computes eigenvalues of newforms. .. _sec:decompdirchar: Dirichlet Character Decomposition --------------------------------- The group `(\Z/N\Z)^*` acts on `M_k(\Gamma_1(N))` through :defn:`diamond-bracket operators` `\langle d \rangle`, as follows. For `d\in(\Z/N\Z)^*`, define .. math:: 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 :ref:`ex:surjred`), 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 .. math:: \Gamma_0(N) = \left\{ \mtwo{a}{b}{c}{d} \in \SL_2(\Z) : \mtwo{a}{b}{c}{d}\con \mtwo{*}{*}{0}{*}\pmod{N} \right\}. This will imply that `\dbd{d}` preserves `M_k(\Gamma_1(N))` since `\abcd{a}{b}{c}{d'} \in \Gamma_0(N)`. .. lemma:: 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)^*`. .. proof:: See :ref:`ex:g0g1quo`. 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 :ref:`rem:dbdinhecke`). The :defn:`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:: :label: prop:dcdecomp We have .. math:: M_k(\Gamma_1(N)) = \bigoplus_{\eps \in D(N,\C)} M_k(N,\eps), where .. math:: 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\}. .. proof:: 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 :ref:`ex:diag`), 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:: Character of Modular Form If `f\in M_k(N,\eps)`, we say that `\eps` is the :defn:`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 :ref:`ch:eisen`. The space `E_k(N,\eps)` can be defined in a third way using the Petersson inner product (see :cite:`[\S{}VII.5]{lang:modular}`). .. index:: Petersson inner product The diamond-bracket operators preserve cusp forms, so the isomorphism of :ref:`prop:dcdecomp` 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`. .. index:: pair: Sage; dimension with character :: 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 `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) 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 .. _sec:ALL: Atkin-Lehner-Li Theory ---------------------- In Section :ref:`sec:degen` 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 .. math:: :label: eqn:degenmf \alpha_t : S_k(\Gamma_1(M)) \to S_k(\Gamma_1(N)) be the :defn:`degeneracy map`, which is given by `f(q) \mapsto f(q^t)`. There are also maps `\beta_t` in the other direction; see :cite:`[Ch.~VIII]{lang:modular}`. The :defn:`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 :defn:`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 .. math:: 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:: Atkin, Lehner, Li :label: thm:all We have a decomposition .. math:: :label: eqn:decomp 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. .. proof:: The complete proof is in :cite:`winnie:newforms`. See also :cite:`[Ch.~5]{diamond-shurman}` for a beautiful modern treatement of this and related results. The analogue of :ref:`thm:all` with `\Gamma_1` replaced by `\Gamma_0` is also true (this is what was proved in :cite:`atkin-lehner`). 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:: 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:: :label: ex:onlyold We have .. math:: 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:: :label: ex:new_old The space `S_2(\Gamma_0(45))` has dimension `3` and basis .. math:: 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 .. math:: 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 .. math:: 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:: This example is similar to :ref:`ex:onlyold`, except that there are newforms. We have .. math:: 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 .. math:: \mthree {-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:: Newform :label: def:newform A :defn:`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:: :label: prop:eigncoeffs 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`. .. proof:: If `\eps=1`, then `f\in M_k(\Gamma_0(N))` and this is :ref:`lem:hecketn`. 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 .. math:: 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} a_{n}q^{np}\right), 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 .. math:: :label: eqn:eigenexp \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 .. math:: 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, :eq:`eqn:eigenexp` implies that `\lambda_p = a_p`, as desired. .. remark:: :label: rem:dbdinhecke 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 :ref:`ex:dbdinhecke`). .. _sec:compcuspforms: Computing Cusp Forms -------------------- Let `\sS_k(N,\eps;\C)` be the space of cuspidal modular symbols as in Chapter :ref:`ch:modsym`. Let `\iota^*` be the map of :eq:`eqn:iota`, and let `\sS_k(N,\eps;\C)^+` be the :defn:`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 :ref:`thm:modsymformpairing` and compatibility of the degeneracy maps (for modular symbols they are defined in Section :ref:`sec:degen`) 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 :eq:`eqn:decomp`. 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 :ref:`prop:eigncoeffs`, 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 :ref:`alg:s2basis`. It computes `S_k(N,\eps)` without finding any eigenspaces. .. algorithm:: Merel's Algorithm for Computing a Basis :label: alg:merelqexp 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 :ref:`alg:modsympresent` to compute .. math:: 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 .. math:: 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 :ref:`alg:merelqexp` seems slower than the eigenspace algorithm that we will describe in the rest of this chapter. The theoretical complexity of :ref:`alg:merelqexp` *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:: 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. .. _sec:syseigen: 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 :ref:`alg:decomp`. Fix `N` and a Dirichlet character `\eps` of modulus `N`, and let .. math:: V=\sM_k(N,\eps)^+ be the `+1` quotient of modular symbols (see equation :eq:`eqn:iota`). .. algorithm:: System of Eigenvalues :label: alg:eigsys 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 :ref:`alg:decomp` 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)`. .. _alg:ap:gen: 4. [Find Generator] Find a random `T \in \T` such that the iterates .. math:: \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 :ref:`(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 .. math:: 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 .. math:: 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. [#f1]_ 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:: :label: ex:23 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 .. math:: f = q + aq^2 + (-2a - 1)q^3 + (-a - 1)q^4 + 2aq^5 + \cdots, where `a=(-1+\sqrt{5})/2`. We will use :ref:`alg:eigsys` 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: .. math:: [(0,0)],\quad [(1,0)], \quad [(0,1)], where we use square brackets to differentiate Manin symbols from vectors. The Hecke operator .. math:: T_2 = \left(\begin{array}{ccc} 3&0&0\\ 0&0&2\\ -1&1/2&-1 \end{array}\right) 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 :ref:`alg:eigsys` 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 .. math:: \left(\begin{array}{ccc} 0&0&1\\ 1&0&-2/11\\ 0&1&-3/11 \end{array}\right) and .. math:: B^{-1} = \left(\begin{array}{ccc} 2/11&1&0\\ 3/11&0&1\\ 1&0&0 \end{array}\right), so projection onto `V` is given by the first two rows: .. math:: \pi = \left(\begin{array}{ccc} 2/11&1&0\\ 3/11&0&1 \end{array}\right). 2. [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. 3. [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 .. math:: \psi(T_1) = \pi(v) = (1,0)^t and .. math:: \psi(T_2) = \pi(T_2(v)) = \pi((0,0,1/2)^t) = (0,1/2)^t. 4. [Find Generator] We have .. math:: \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`. 5. [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`. 6. [Field Structure] We have .. math:: \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 .. math:: 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`. 7. [Hecke Eigenvalues] We have `a_n = e(\Psi(T_n))`. For example, .. math:: \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:: It is easier to appreciate :ref:`alg:eigsys` 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 .. math:: f = \sum_{n=1}^{\infty} a_n q^n\in S_2(\Gamma_0(389)) such that if `\alpha = a_2`, then .. math:: 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 .. math:: 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 .. math:: \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 ````````````````` Let .. math:: j = \frac{1}{q} + 744 + 196884 q + \cdots .. index:: `j`-function 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., :cite:`[Section~VIII.3.3]{serre:arithmetic}`). .. lemma:: :label: lem:jform 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`. .. proof:: 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 .. math:: \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 ` \frac{km}{12} or `f \in S_k(\Gamma,\O)` is a cusp form and .. math:: \ord_\m(f) > \frac{km}{12} - \frac{m-1}{N}. Then `f\con 0\pmod{\m}`. .. proof:: **Case 1: First we assume** `\Gamma=\SL_2(\Z)`. Let .. math:: \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 .. math:: :label: eqn:sturm1 \ord_q(f^{12}\cdot\Delta^{-k}) = 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 .. math:: :label: eqn:sturm2 \ord_\m(f^{12}\cdot \Delta^{-k}) = \ord_\m(f^{12}) - k\cdot \ord_\m(\Delta) > k - k = 0. Combining :eq:`eqn:sturm1` and :eq:`eqn:sturm2`, we see that .. math:: 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 :ref:`lem:jform`, .. math:: f^{12} \cdot \Delta^{-k} \in \m[j] is a polynomial in `j` of degree at most `k` with coefficients in `\m`. Thus .. math:: 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)`, .. math:: (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 .. math:: M_k(\Gamma(N),\Q(\zeta_N)) = M_k(\Gamma(N)) \cap{} (\Q(\zeta_N)[[q^{1/N}]]) and the cuspidal subspace `S_k(\Gamma(N),\Q(\zeta_N))`. In particular, for any `\gamma\in\SL_2(\Z)`, .. math:: 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 .. math:: :label: eqn:sturm_crt 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 .. math:: \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`. Write .. math:: \SL_2(\Z) = \bigcup_{i=1}^m \Gamma{} \gamma_i with `\gamma_1 = \abcd{1}{0}{0}{1}`, and let .. math:: 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 .. math:: \ord_{\wM}(F) \geq \ord_{\wM}(f) = \ord_{\m}(f) > \frac{km}{12}. Thus we can apply Case 1 to conclude that .. math:: \ord_{\wM}(F) = +\infty. Thus .. math:: :label: eqn:sturm:ords \infty = \ord_{\wM}(F) = \ord_\m(f) + \sum_{i=2}^m \ord_{\wM}(A_{\gamma_i} f^{[\gamma]_k}), so `\ord_\m(f)=+\infty`, because of :eq:`eqn:sturm_crt`. 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 .. math:: \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 .. math:: \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 :eq:`eqn:sturm:ords`, conclude that `\ord_\m(f)=+\infty`. .. corollary:: 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 .. math:: a_n(f) \con a_n(g) \pmod{\m} for all .. math:: n\leq \begin{cases} \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}, \end{cases} 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:: Buzzard 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 .. math:: a_n(f) \con a_n(g) \pmod{\m} \qquad\text{for all}\qquad n \leq \frac{km}{12}, where .. math:: 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}`. .. proof:: 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 .. math:: \ord_\m(h^s) > sr = \frac{ksm}{12}. By :ref:`thm:sturm`, 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 :cite:`sturm:cong` also applies some results of Asai on `q`-expansions at various cusps to obtain a more refined result for newforms. .. theorem:: Sturm 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 .. math:: a_p(f) \con a_p(g)\pmod{\m} for all primes .. math:: p \leq \frac{k\cdot [\SL_2(\Z):\Gamma_0(N)]}{12 \cdot 2^{\#I}}, then `f\con g\pmod{\m}`. The paper :cite:`buzzard-stein:artin` contains a similar result about congruences between newforms, which does not require that the level be square-free. Recall from Definition :ref:`defn:conductordir` 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:: 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 .. math:: a_p(f) \con a_p(g)\pmod{\m} for all primes `p\in I` and for all primes .. math:: 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 :cite:`[\S1.3]{buzzard-stein:artin}`. Generating the Hecke Algebra ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The following theorem appeared in :cite:`[Appendix]{lario-schoof}`, 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:: :label: thm:heckegen Suppose `\Gamma` is a congruence subgroup that contains `\Gamma_1(N)` and let .. math:: :label: eqn:perfectR r=\frac{km}{12} - \frac{m - 1}{N}, where `m=[\SL_2(\Z):\Gamma]`. Then the Hecke algebra .. index:: pair: Hecke algebra; generators over `\Z` .. math:: \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`. .. proof:: 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 .. math:: 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 .. math:: 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 .. math:: 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 .. math:: a_m(f)=a_1(T_m f)=\langle f, T_m\rangle = 0 in `\F_p` for each `m\leq r`. By :ref:`thm:sturm`, 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 :eq:`eqn:perfectR` is perfect, it follows that .. math:: \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:: In general, the conclusion of :ref:`thm:heckegen` 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`. Exercises --------- .. exercise:: :label: ex:g0g1quo 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:: :label: ex:dbdinhecke 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:: :label: exer:onlyold Find an example like :ref:`ex:onlyold` 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:: :label: ex:31 a. Following :ref:`ex:23`, compute a basis for `S_2(\Gamma_0(31))`. b. Use :ref:`alg:merelqexp` to compute a basis for `S_2(\Gamma_0(31))`. .. rubric:: Footnotes .. [#f1] John Cremona initially suggested to me the idea of separating these two maps.