.. _ch:modform2: Modular Forms of Weight 2 ========================= .. chapter:: 3 We saw in Chapter :ref:`ch:level1` (especially Section :ref:`sec:struct1`) that we can compute each space `M_k(\SL_2(\Z))` explicitly. This involves computing Eisenstein series `E_4` and `E_6` to some precision, then forming the basis `\{E_4^a E_6^b : 4a+6b = k, 0\leq a,b \in \Z\}` for `M_k(\SL_2(\Z))`. In this chapter we consider the more general problem of computing `S_2(\Gamma_0(N))`, for any positive integer `N`. Again we have a decomposition .. math:: M_2(\Gamma_0(N)) = S_2(\Gamma_0(N)) \oplus \Eis_2(\Gamma_0(N)), where `\Eis_2(\Gamma_0(N))` is spanned by generalized Eisenstein series and `S_2(\Gamma_0(N))` is the space of cusp forms, i.e., elements of `M_2(\Gamma_0(N))` that vanish at *all* cusps. In Chapter :ref:`ch:eisen` we compute the space `\Eis_2(\Gamma_0(N))` in a similar way to how we computed `M_k(\SL_2(\Z))`. On the other hand, elements of `S_2(\Gamma_0(N))` often cannot be written as sums or products of generalized Eisenstein series. In fact, the structure of `M_2(\Gamma_0(N))` is, in general, much more complicated than that of `M_k(\SL_2(\Z))`. For example, when `p` is a prime, `\Eis_2(\Gamma_0(p))` has dimension `1`, whereas `S_2(\Gamma_0(p))` has dimension about `p/12`. Fortunately an idea of Birch, which he called modular symbols, provides a method for computing `S_2(\Gamma_0(N))` and indeed for much more that is relevant to understanding special values of `L`-functions. Modular symbols are also a powerful theoretical tool. In this chapter, we explain how `S_2(\Gamma_0(N))` is related to modular symbols and how to use this relationship to explicitly compute a basis for `S_2(\Gamma_0(N))`. In Chapter :ref:`ch:modsym` we will introduce more general modular symbols and explain how to use them to compute `S_k(\Gamma_0(N))`, `S_k(\Gamma_1(N))` and `S_k(N,\eps)` for any integers `k\geq 2` and `N` and character `\eps`. Section :ref:`sec:modformhecke` contains a very brief summary of basic facts about modular forms of weight `2`, modular curves, Hecke operators, and integral homology. Section :ref:`sec:modsym` introduces modular symbols and describes how to compute with them. In Section :ref:`sec:maninboundary` we talk about how to cut out the subspace of modular symbols corresponding to cusp forms using the boundary map. Section :ref:`sec:basiss2one` is about a straightforward method to compute a basis for `S_2(\Gamma_0(N))` using modular symbols, and Section :ref:`sec:computingmodform` outlines a more sophisticated algorithm for computing newforms that uses Atkin-Lehner theory. Before reading this chapter, you should have read Chapter :ref:`ch:modform` and Chapter :ref:`ch:level1`. We also assume familiarity with algebraic curves, Riemann surfaces, and homology groups of compact Riemann surfaces. .. _sec:modformhecke: Hecke Operators --------------- Recall from Chapter :ref:`ch:modform` that the group `\Gamma_0(N)` acts on `\h^*=\h\cup \P^1(\Q)` by linear fractional transformations. The quotient `\Gamma_0(N)\backslash \h^*` is a Riemann surface, which we denote by `X_0(N)`. See :cite:`[Ch. 2]{diamond-shurman}` for a detailed description of the topology on `X_0(N)`. The Rieman surface `X_0(N)` also has a canonical structure of algebraic curve over `\Q`, as is explained in :cite:`[Ch. 7]{diamond-shurman}` (see also :cite:`[\S6.7]{shimura:intro}`). Recall from Section :ref:`sec:modformN` that a cusp form of weight `2` for `\Gamma_0(N)` is a function `f` on `\h` such that `f(z)dz` defines a holomorphic differential on `X_0(N)`. Equivalently, a cusp form is a holomorphic function `f` on `\h` such that a. the expression `f(z)dz` is invariant under replacing `z` by `\gamma(z)` for each `\gamma\in \Gamma_0(N)` and b. `f(z)` vanishes at every cusp for `\Gamma_0(N)`. The space `S_2(\Gamma_0(N))` of weight `2` cusp forms on `\Gamma_0(N)` is a finite-dimensional complex vector space, of dimension equal to the genus `g` of `X_0(N)`. The space `X_0(N)(\C)` is a compact oriented Riemann surface, so it is a `2`-dimensional oriented real manifold, i.e., `X_0(N)(\C)` is a `g`-holed torus (see :ref:`diagram:homology`). Condition (b) in the definition of `f` means that `f` has a Fourier expansion about each element of `\P^1(\Q)`. Thus, at `\infty` we have .. math:: f(z) &= a_1 e^{2\pi i z} + a_2 e^{2 \pi i 2z} + a_3 e^{2 \pi i 3z} + \cdots\\ &= a_1 q + a_2 q^2 + a_3 q^3 + \cdots, where, for brevity, we write `q=q(z)=e^{2\pi i z}`. .. example:: Let `E` be the elliptic curve defined by the equation `y^2 + xy = x^3 + x^2 - 4x - 5`. Let `a_p = p+1-\#\tilde{E}(\F_p)`, where `\tilde{E}` is the reduction of `E` mod `p` (note that for the primes that divide the conductor of `E` we have `a_3=-1`, `a_{13}=1`).2 For `n` composite, define `a_n` using the relations at the end of Section :ref:`sec:computingmodform`. .. index:: single: Shimura-Taniyama conjecture pair: conjecture; Shimura-Taniyama Then the Shimura-Taniyama conjecture asserts that .. math:: f&=q + a_2 q^2 + a_3 q^3 + a_4 q^4 + a_5 q^5 + \cdots\\ &= q + q^2 - q^3 -q^4 + 2q^5 + \cdots is the `q`-expansion of an element of `S_2(\Gamma_0(39))`. This conjecture, which is now a theorem (see :cite:`breuil-conrad-diamond-taylor`), asserts that any `q`-expansion constructed as above from an elliptic curve over `\Q` is a modular form. This conjecture was mostly proved first by Wiles :cite:`wiles:fermat` as a key step in the proof of Fermat's last theorem. Just as is the case for level `1` modular forms (see Section :ref:`sec:hecke_one`) there are commuting Hecke operators `T_1, T_2, T_3, \ldots` that act on `S_2(\Gamma_0(N))`. To define them conceptually, we introduce an interpretation of the modular curve `X_0(N)` as an object whose points *parameterize* elliptic curves with extra structure. .. proposition:: :label: prop:modulix0n The complex points of `Y_0(N)=\Gamma_0(N)\backslash \h` are in natural bijection with isomorphism classes of pairs `(E,C)`, where `E` is an elliptic curve over `\C` and `C` is a cyclic subgroup of `E(\C)` of order `N`. The class of the point `\lambda \in \h` corresponds to the pair .. math:: \left(\C/(\Z + \Z \lambda), \quad \left(\frac{1}{N}\Z + \Z\lambda\right)/(\Z + \Z \lambda)\right). .. proof:: See :ref:`ex:x0n`. Suppose `n` and `N` are coprime positive integers. There are two natural maps `\pi_1` and `\pi_2` from `Y_0(n\cdot N)` to `Y_0(N)`; the first, `\pi_1`, sends `(E,C)\in Y_0(n\cdot N)(\C)` to `(E,C')`, where `C'` is the unique cyclic subgroup of `C` of order `N`, and the second, `\pi_2`, sends `(E,C)` to `(E/D, C/D)`, where `D` is the unique cyclic subgroup of `C` of order `n`. These maps extend in a unique way to algebraic maps from `X_0(n\cdot N)` to `X_0(N)`: .. math:: :label: eqn:corrx0n \xymatrix{ & X_0(n\cdot N) \ar[dl]_{\pi_2}\ar[dr]^{\pi_1}\\ X_0(N) & & X_0(N).} The `n^{th}` :defn:`Hecke operator` `T_n` is `{\pi_1}_* \circ \pi_2^*`, where `\pi_2^*` and `{\pi_1}_*` denote pullback and pushforward of differentials, respectively. (There is a similar definition of `T_n` when `\gcd(n,N)\neq 1`.) Using our interpretation of `S_2(\Gamma_0(N))` as differentials on `X_0(N)`, this gives an action of Hecke operators on `S_2(\Gamma_0(N))`. One can show that these induce the maps of :ref:`prop:qexpTn` on `q`-expansions. .. example:: There is a basis of `S_2(39)` so that .. math:: T_2 = \mthree{\hfill 1}{\hfill 1}{\hfill 0}{-2}{-3}{-2}{\hfill 0}{\hfill 0}{\hfill 1} \quad\text{and}\quad T_5 = \mthree{-4}{-2}{-6}{\hfill4}{\hfill4}{\hfill4}{\hfill0}{\hfill0}{\hfill2}. Notice that these matrices commute. Also, the characteristic polynomial of `T_2` is `(x - 1) \cdot (x^{2} + 2x - 1)`. Homology ~~~~~~~~ The first homology group `\H_1(X_0(N),\Z)` is the group of closed `1`-cycles modulo boundaries of `2`-cycles (formal sums of images of `2`-simplexes). Topologically `X_0(N)` is a `g`-holed torus, where `g` is the genus of `X_0(N)`. Thus `\H_1(X_0(N),\Z)` is a free abelian group of rank `2g` (see, e.g., :cite:`[Ex. 19.30]{greenberg-harper}` and :cite:`[\S6.1]{diamond-shurman}`), with two generators corresponding to each hole, as illustrated in the case `N=39` in :ref:`diagram:homology`. .. figure:: :label: diagram:homology The homology of `X_0(39)` .. image:: images/torus39.* :align: center .. math:: \H_1(X_0(39),\Z) \isom \Z\cross\Z\cross\Z\cross\Z\cross\Z\cross\Z The homology of `X_0(N)` is closely related to modular forms, since the Hecke operators `T_n` also act on `\H_1(X_0(N),\Z)`. The action is by pullback of homology classes by `\pi_2` followed by taking the image under `\pi_1`, where `\pi_1` and `\pi_2` are as in :eq:`eqn:corrx0n`. Integration defines a pairing .. math:: :label: eqn:pairing \langle\,,\,\rangle: S_2(\Gamma_0(N)) \cross \H_1(X_0(N),\Z) \ra \C. Explicitly, for a path `x`, .. math:: \langle f , x \rangle = 2\pi i \cdot \int_{x} f(z) dz. .. theorem:: :label: thm:pairing2 The pairing :eq:`eqn:pairing` is nondegenerate and Hecke equivariant in the sense that for every Hecke operator `T_n`, we have `\langle f T_n, x\rangle = \langle f, T_n x\rangle`. Moreover, it induces a perfect pairing .. math:: \langle\,,\,\rangle: S_2(\Gamma_0(N)) \cross \H_1(X_0(N),\R) \ra \C. This is a special case of the results in Section :ref:`sec:pairing`. As we will see, modular symbols allow us to make explicit the action of the Hecke operators on `\H_1(X_0(N),\Z)`; the above pairing then translates this into a wealth of information about cusp forms. We will also consider the relative homology group `\H_1(X_0(N),\Z;\{\text{cusps}\})` of `X_0(N)` :defn:`relative to the cusps`; it is the same as usual homology, but i n addition we allow paths with endpoints in the cusps instead of restricting to closed loops. Modular symbols provide a "combinatorial" presentation of `\H_1(X_0(N),\Z)` in terms of paths between elements of `\P^1(\Q)`. .. _sec:modsym: Modular Symbols --------------- Let `\sM_2` be the free abelian group with basis the set of symbols `\{\alpha,\beta\}` with `\alpha,\beta\in\P^1(\Q)` modulo the 3-term relations .. math:: \{\alpha,\beta\} + \{\beta,\gamma\} + \{\gamma,\alpha\} = 0 above and modulo any torsion. Since `\sM_2` is torsion-free, we have .. math:: \{\alpha,\alpha\} = 0\qquad\text{and}\qquad \{\alpha,\beta\} = -\{\beta,\alpha\}. .. warning:: The symbols `\{\alpha,\beta\}` satisfy the relations `\{\alpha,\beta\} = -\{\beta,\alpha\}`, so order matters. The notation `\{\alpha,\beta\}` looks like the set containing two elements, which strongly (and incorrectly) suggests that the order does not matter. This is the standard notation in the literature. .. increase_counter:: .. figure:: :label: figure:modsym The modular symbols `\{\alpha,\beta\}` and `\{0,\infty\}` .. image:: images/alpha-beta.* :align: center As illustrated in :ref:`figure:modsym`, we "think of" this modular symbol as the homology class, relative to the cusps, of a path from `\alpha` to `\beta` in `\h^*`. Define a :defn:`left action of $\GL_2(\Q)$` on `\sM_2` by letting `g\in\GL_2(\Q)` act by .. math:: g\{\alpha, \beta\} = \{g(\alpha), g(\beta)\}, and `g` acts on `\alpha` and `\beta` via the corresponding linear fractional transformation. The space `\sM_2(\Gamma_0(N))` of :defn:`modular symbols for `\Gamma_0(N)`` is the quotient of `\sM_2` by the submodule generated by the infinitely many elements of the form `x - g(x)`, for `x` in `\sM_2` and `g` in `\Gamma_0(N)`, and modulo any torsion. A modular symbol for `\Gamma_0(N)` is an element of this space. We frequently denote the equivalence class of a modular symbol by giving a representative element. .. example:: :label: ex:01 Some modular symbols are `0` no matter what the level `N` is! For example, since `\gamma=\abcd{1}{1}{0}{1}\in \Gamma_0(N)`, we have .. math:: \{\infty,0\} = \{\gamma(\infty),\gamma(0)\} = \{\infty,1\}, so .. math:: 0 = \{\infty,1\}-\{\infty,0\} = \{\infty,1\} + \{0,\infty\} = \{0,\infty\} + \{\infty,1\} = \{0,1\}. See :ref:`ex:modsymzero` for a generalization of this observation. There is a natural homomorphism .. math:: :label: eqn:homtoms \varphi: \sM_2(\Gamma_0(N)) \to \H_1(X_0(N),\{\text{cusps}\},\Z) that sends a formal linear combination of geodesic paths in the upper half plane to their image as paths on `X_0(N)`. In :cite:`manin:parabolic` Manin proved that :eq:`eqn:homtoms` is an isomorphism (this is a fairly involved topological argument). Manin identified the subspace of `\sM_2(\Gamma_0(N))` that is sent isomorphically onto `\H_1(X_0(N),\Z)`. Let `\sB_2(\Gamma_0(N))` denote the free abelian group whose basis is the finite set `C(\Gamma_0(N)) = \Gamma_0(N)\backslash \P^1(\Q)` of cusps for `\Gamma_0(N)`. The :defn:`boundary map` .. math:: \delta: \sM_2(\Gamma_0(N))\ra \sB_2(\Gamma_0(N)) sends `\{\alpha,\beta\}` to `\{\beta\}-\{\alpha\}`, where `\{\beta\}` denotes the basis element of `\sB_2(\Gamma_0(N))` corresponding to `\beta\in\P^1(\Q)`. The kernel `\sS_2(\Gamma_0(N))` of `\delta` is the subspace of :defn:`cuspidal modular symbols`. Thus an element of `\sS_2(\Gamma_0(N))` can be thought of as a linear combination of paths in `\h^*` whose endpoints are cusps and whose images in `X_0(N)` are homologous to a `\Z`-linear combination of closed paths. .. theorem:: Manin The map `\varphi` above induces a canonical isomorphism .. math:: \sS_2(\Gamma_0(N)) \isom \H_1(X_0(N),\Z). .. proof:: This is :cite:`[Thm. 1.9]{manin:parabolic}`. For any (commutative) ring `R` let .. math:: \sM_2(\Gamma_0(N), R) = \sM_2(\Gamma_0(N)) \tensor_\Z R and .. math:: \sS_2(\Gamma_0(N), R) = \sS_2(\Gamma_0(N)) \tensor_\Z R. .. proposition:: :label: prop:dimsym2 We have .. math:: \dim_\C\sS_2(\Gamma_0(N),\C) = 2\dim_\C S_2(\Gamma_0(N)). .. proof:: We have .. math:: \dim_\C\sS_2(\Gamma_0(N),\C) = \rank_\Z \sS_2(\Gamma_0(N)) = \rank_\Z \H_1(X_0(N),\Z) = 2g. .. example:: We illustrate modular symbols in the case when `N=11`. Using Sage (below), which implements the algorithm that we describe below over `\Q`, we find that `\sM_2(\Gamma_0(11);\Q)` has basis `\{\infty,0\}`, `\{-1/8,0\}`, `\{-1/9,0\}`. A basis for the integral homology `\H_1(X_0(11),\Z)` is the subgroup generated by `\{-1/8,0\}` and `\{-1/9,0\}`. .. index:: pair: Sage; modular symbols of level `11` :: sage: set_modsym_print_mode ('modular') sage: M = ModularSymbols(11, 2) sage: M.basis() ({Infinity,0}, {-1/8,0}, {-1/9,0}) sage: S = M.cuspidal_submodule() sage: S.integral_basis() # basis over ZZ. ({-1/8,0}, {-1/9,0}) sage: set_modsym_print_mode ('manin') # set it back .. _sec:manintrick: Computing with Modular Symbols ------------------------------ In this section, we describe a trick of Manin that we will use to prove that spaces of modular symbols are computable. By :ref:`ex:conggamma1` the group `\Gamma_0(N)` has finite index in `\SL_2(\Z)`. Fix right coset representatives `r_0, r_1, \ldots, r_m` for `\Gamma_0(N)` in `\SL_2(\Z)`, so that .. math:: \SL_2(\Z) = \Gamma_0(N)r_0 \, \union\, \Gamma_0(N)r_1 \, \union\, \cdots \, \union\, \Gamma_0(N)r_m, where the union is disjoint. For example, when `N` is prime, a list of coset representatives is .. math:: \mtwo{1}{0}{0}{1}, \mtwo{1}{0}{1}{1}, \mtwo{1}{0}{2}{1}, \mtwo{1}{0}{3}{1}, \ldots, \mtwo{\hfill 1}{0}{N-1}{1}, \mtwo{0}{-1}{1}{\hfill 0}. Let .. math:: :label: eqn:p1znz \P^1(\Z/N\Z)= \{(a:b) \,: \, a,b\in\Z/N\Z, \, \,\gcd(a,b,N)=1 \,\}/\sim where `(a:b)\sim (a':b')` if there is `u\in(\Z/N\Z)^*` such that `a=ua', b=ub'`. .. proposition:: :label: prop:p1bij There is a bijection between `\P^1(\Z/N\Z)` and the right cosets of `\Gamma_0(N)` in `\SL_2(\Z)`, which sends a coset representative `\abcd{a}{b}{c}{d}` to the class of `(c:d)` in `\P^1(\Z/N\Z)`. .. proof:: See :ref:`ex:bij`. See :ref:`prop:gamma1cosets` for the analogous statement for `\Gamma_1(N)`. We now describe an observation of Manin (see :cite:`[\S1.5]{manin:parabolic}`) that is crucial to making `\sM_2(\Gamma_0(N))` computable. It allows us to write any modular symbol `\{\alpha, \beta\}` as a `\Z`-linear combination of symbols of the form `r_i\{0,\infty\}`, where the `r_i\in \SL_2(\Z)` are coset representatives as above. In particular, the finitely many symbols `r_0\{0,\infty\}, \ldots, r_m\{0,\infty\}` generate `\sM_2(\Gamma_0(N))`. .. proposition:: :label: prop:manintrick [Manin] Let `N` be a positive integer and `r_0,\ldots, r_m` a set of right coset representatives for `\Gamma_0(N)` in `\SL_2(\Z)`. Every `\{\alpha, \beta\} \in \sM_2(\Gamma_0(N))` is a `\Z`-linear combination of `r_0\{0,\infty\}, \ldots, r_m\{0,\infty\}`. We give two proofs of the proposition. The first is useful for computation (see :cite:`[\S2.1.6]{cremona:algs}`); the second (see :cite:`[\S2]{mtt}`) is easier to understand conceptually since it does not require any knowledge of continued fractions. .. proof:: Continued Fractions Proof of :ref:`prop:manintrick` Since .. math:: \{\alpha,\beta\}=\{0,\beta\}-\{0,\alpha\}, it suffices to consider modular symbols of the form `\{0,b/a\}`, where the rational number `b/a` is in lowest terms. Expand `b/a` as a continued fraction and consider the successive convergents in lowest terms: .. math:: \frac{b_{-2}}{a_{-2}} = \frac{0}{1},\quad \frac{b_{-1}}{a_{-1}} = \frac{1}{0},\quad \frac{b_0}{a_0} = \frac{b_0}{1},\, \ldots,\quad \frac{b_{n-1}}{a_{n-1}},\quad \frac{b_n}{a_n}= \frac{b}{a} where the first two are included formally. Then .. math:: b_k a_{k-1} - b_{k-1} a_k = (-1)^{k-1}, so that .. math:: g_k = \mtwo{b_k}{\hfill (-1)^{k-1}b_{k-1}}{a_k}{(-1)^{k-1}a_{k-1}}\in \SL_2(\Z). Hence .. math:: \left\{\frac{b_{k-1}}{a_{k-1}}, \frac{b_k}{a_k}\right\} = g_k \{ 0, \infty\} = r_i \{0,\infty\}, for some `i`, is of the required special form. Since .. math:: \{0,b/a\} = \{0,\infty\} + \{\infty,b_0\} + \left\{\frac{b_0}{1}, \frac{b_1}{a_1}\right\} + \cdots + \left\{\frac{b_{n-1}}{a_{n-1}}, \frac{b_n}{a_n}\right\}, this completes the proof. .. proof:: Inductive Proof of :ref:`prop:manintrick` As in the first proof it suffices to prove the proposition for any symbol `\{0,b/a\}`, where `b/a` is in lowest terms. We will induct on `a\in\Z_{\geq 0}`. If `a=0`, then the symbol is `\{0,\infty\}`, which corresponds to the identity coset, so assume that `a>0`. Find `a'\in\Z` such that .. math:: ba'\con 1\pmod{a}; then `b' = (b a' - 1)/a \in\Z` so the matrix .. math:: \delta = \mtwo{b}{b'}{a}{a'} is an element of `\SL_2(\Z)`. Thus `\delta = \gamma \cdot r_j` for some right coset representative `r_j` and `\gamma \in \Gamma_0(N)`. Then .. math:: \{0, b/a\} - \{0, b'/a'\} = \{b'/a', b/a\} = \mtwo{b}{b'}{a}{a'}\cdot \{0,\infty\} = r_j \{0,\infty\}, as elements of `\M_2(\Gamma_0(N))`. By induction, `\{0, b'/a'\}` is a linear combination of symbols of the form `r_k\{0,\infty\}`, which completes the proof. .. example:: Let `N=11`, and consider the modular symbol `\{0,4/7\}`. We have .. math:: \frac{4}{7} = 0 + \frac{1}{1+\frac{1}{1+\frac{1}{3}}}, so the partial convergents are .. math:: \frac{b_{-2}}{a_{-2}} = \frac{0}{1},\quad \frac{b_{-1}}{a_{-1}} = \frac{1}{0},\quad \frac{b_0}{a_0} = \frac{0}{1},\quad \frac{b_1}{a_1} = \frac{1}{1},\quad \frac{b_2}{a_2} = \frac{1}{2},\quad \frac{b_3}{a_3} = \frac{4}{7}. Thus, noting as in :ref:`ex:01` that `\{0,1\}=0`, we have .. math:: :nowrap: \begin{eqnarray*} \{0,4/7\} &=& \{0,\infty\} +\{\infty,0\} + \{0,1\}+ \{1,1/2\} + \{1/2,4/7\}\\ &=& \mtwo{1}{-1}{2}{-1}\{0,\infty\} + \mtwo{4}{1}{7}{2}\{0,\infty\}\\ &=& \mtwo{1}{0}{9}{1}\{0,\infty\} + \mtwo{1}{0}{9}{1}\{0,\infty\}\\ &=& 2 \cdot \left[\mtwo{1}{0}{9}{1}\{0,\infty\}\right]. \end{eqnarray*} We compute the convergents of `4/7` in Sage as follows (note that `0` and `\infty` are excluded): .. index:: pair: Sage; continued fraction convergents :: sage: convergents(4/7) [0, 1, 1/2, 4/7] .. _sec:maninsyms: Manin Symbols ~~~~~~~~~~~~~ As above, fix coset representatives `r_0,\ldots,r_m` for `\Gamma_0(N)` in `\SL_2(\Z)`. Consider formal symbols `[r_i]'` for `i=0,\ldots, m`. Let `[r_i]` be the modular symbol `r_i\{0,\infty\} = \{r_i(0), r_i(\infty)\}`. We equip the symbols `[r_0]',\ldots,[r_m]'` with a :defn:`right action of $\SL_2(\Z)$`, which is given by `[r_i]'.g = [r_j]'`, where `\Gamma_0(N) r_j = \Gamma_0(N) r_i g`. We extend the notation by writing `[\gamma]' = [\Gamma_0(N)\gamma]' = [r_i]'`, where `\gamma \in \Gamma_0(N) r_i`. Then the right action of `\Gamma_0(N)` is simply `[\gamma]'.g = [\gamma g]'`. :ref:`thm:sl2zgen` implies that `\SL_2(\Z)` is generated by the two matrices `\sigma = \abcd{0}{-1}{1}{\hfill0}` and `\tau=\abcd{1}{-1}{1}{\hfill0}`. Note that `\sigma=S` from :ref:`thm:sl2zgen` and `\tau = TS`, so `T = \tau\sigma \in \langle \sigma, \tau\rangle.` The following theorem provides us with a finite presentation for the space `\M_2(\Gamma_0(N))` of modular symbols. .. index:: pair: modular symbols; finite presentation .. theorem:: Manin :label: thm:manin_present Consider the quotient `M` of the free abelian group on Manin symbols `[r_0]',\ldots,[r_m]'` by the subgroup generated by the elements (for all `i`): .. math:: {[r_i]'} + [r_i]'\sigma \qquad\text{ and }\qquad {[r_i]'} + [r_i]'\tau + [r_i]'\tau^2 , and modulo any torsion. Then there is an isomorphism .. math:: \Psi: M \xrightarrow{\,\sim\,} \sM_2(\Gamma_0(N)) given by `[r_i]' \mapsto [r_i] = r_i \{0,\infty\}`. .. proof:: We will only prove that `\Psi` is surjective; the proof that `\Psi` is injective requires much more work and will be omitted from this book (see :cite:`[\S1.7]{manin:parabolic}` for a complete proof). :ref:`prop:manintrick` implies that `\Psi` is surjective, assuming that `\Psi` is well defined. We next verify that `\Psi` is well defined, i.e., that the listed 2-term and 3-term relations hold in the image. To see that the first relation holds, note that .. math:: {[r_i]} + [r_i]\sigma &= \{r_i(0),r_i(\infty)\} + \{r_i\sigma(0), r_i\sigma(\infty)\}\\ &= \{r_i(0),r_i(\infty)\} + \{r_i(\infty), r_i(0)\} \\ & = 0. For the second relation we have .. math:: {[r_i]} + [r_i]\tau + [r_i]\tau^2 &= \{r_i(0),r_i(\infty)\} + \{r_i\tau(0), r_i\tau(\infty)\} + \{r_i\tau^2(0), r_i\tau^2(\infty)\} \\ &= \{r_i(0),r_i(\infty)\} + \{r_i(\infty), r_i(1)\} + \{r_i(1), r_i(0)\} \\ &= 0. .. index:: pair: Sage; modular symbols .. example:: :label: ex:sagemodsym1 By default Sage computes modular symbols spaces over `\Q`, i.e., `\sM_2(\Gamma_0(N);\Q) \isom \sM_2(\Gamma_0(N))\tensor\Q`. Sage represents (weight `2`) Manin symbols as pairs `(c,d)`. Here `c,d` are integers that satisfy `0\leq c,d < N`; they define a point `(c:d) \in \P^1(\Z/N\Z)`, hence a right coset of `\Gamma_0(N)` in `\SL_2(\Z)` (see :ref:`prop:p1bij`). Create `\sM_2(\Gamma_0(N);\Q)` in Sage by typing ``ModularSymbols(N, 2)``. We then use the Sage command :obj:`manin_generators` to enumerate a list of generators `[r_0], \ldots, [r_n]` as in :ref:`thm:manin_present` for several spaces of modular symbols. .. index:: pair: Sage; Manin symbols :: sage: M = ModularSymbols(2,2) sage: M Modular Symbols space of dimension 1 for Gamma_0(2) of weight 2 with sign 0 over Rational Field sage: M.manin_generators() [(0,1), (1,0), (1,1)] sage: M = ModularSymbols(3,2) sage: M.manin_generators() [(0,1), (1,0), (1,1), (1,2)] sage: M = ModularSymbols(6,2) sage: M.manin_generators() [(0,1), (1,0), (1,1), (1,2), (1,3), (1,4), (1,5), (2,1), (2,3), (2,5), (3,1), (3,2)] Given ``x=(c,d)``, the command ``x.lift_to_sl2z(N)`` computes an element of `\SL_2(\Z)` whose lower two entries are congruent to `(c,d)` modulo `N`. :: sage: M = ModularSymbols(2,2) sage: [x.lift_to_sl2z(2) for x in M.manin_generators()] [[1, 0, 0, 1], [0, -1, 1, 0], [0, -1, 1, 1]] sage: M = ModularSymbols(6,2) sage: x = M.manin_generators()[9] sage: x (2,5) sage: x.lift_to_sl2z(6) [1, 2, 2, 5] The :obj:`manin_basis` command returns a list of indices into the Manin generator list such that the corresponding symbols form a basis for the quotient of the `\Q`-vector space spanned by Manin symbols modulo the `2`-term and `3`-term relations of :ref:`thm:manin_present`. :: sage: M = ModularSymbols(2,2) sage: M.manin_basis() [1] sage: [M.manin_generators()[i] for i in M.manin_basis()] [(1,0)] sage: M = ModularSymbols(6,2) sage: M.manin_basis() [1, 10, 11] sage: [M.manin_generators()[i] for i in M.manin_basis()] [(1,0), (3,1), (3,2)] Thus, e.g., every element of `\sM_2(\Gamma_0(6))` is a `\Q`-linear combination of the three symbols `[(1,0)]`, `[(3,1)]`, and `[(3,2)]`. We can write each of these as a modular symbol using the :obj:`modular_symbol_rep` function. .. index:: pair: Sage; modular symbols printing .. link :: sage: M.basis() ((1,0), (3,1), (3,2)) sage: [x.modular_symbol_rep() for x in M.basis()] [{Infinity,0}, {0,1/3}, {-1/2,-1/3}] The :obj:`manin_gens_to_basis` function returns a matrix whose rows express each Manin symbol generator in terms of the subset of Manin symbols that forms a basis (as returned by :obj:`manin_basis`). :: sage: M = ModularSymbols(2,2) sage: M.manin_gens_to_basis() [-1] [ 1] [ 0] Since the basis is `(1,0)`, this means that in `\sM_2(\Gamma_0(2);\Q)`, we have `[(0,1)] = -[(1,0)]` and `[(1,1)] = 0`. (Since no denominators are involved, we have in fact computed a presentation of `\sM_2(\Gamma_0(2);\Z)`.) To convert a Manin symbol `x=(c,d)` to an element of a modular symbols space `M`, use :obj:`M(x)`: :: sage: M = ModularSymbols(2,2) sage: x = (1,0); M(x) (1,0) Next consider `\sM_2(\Gamma_0(6);\Q)`: :: sage: M = ModularSymbols(6,2) sage: M.manin_gens_to_basis() [-1 0 0] [ 1 0 0] [ 0 0 0] [ 0 -1 1] [ 0 -1 0] [ 0 -1 1] [ 0 0 0] [ 0 1 -1] [ 0 0 -1] [ 0 1 -1] [ 0 1 0] [ 0 0 1] Recall that our choice of basis for `\sM_2(\Gamma_0(6);\Q)` is `[(1,0)], [(3,1)], [(3,2)]`. Thus, e.g., the first row of this matrix says that `[(0,1)] = -[(1,0)]`, and the fourth row asserts that `[(1,2)] = -[(3,1)] + [(3,2)]`. :: sage: M = ModularSymbols(6,2) sage: M((0,1)) -(1,0) sage: M((1,2)) -(3,1) + (3,2) Hecke Operators --------------- .. _sec:heckemodsym: Hecke Operators on Modular Symbols ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ When `p` is a prime not dividing `N`, define .. math:: T_p(\{\alpha,\beta\}) = \mtwo{p}{0}{0}{1}\{\alpha,\beta\} + \sum_{r \hspace{-.6em}\mod p} \mtwo{1}{r}{0}{p} \{\alpha,\beta\}. The Hecke operators are compatible with the integration pairing `\langle\, , \, \rangle` of Section :ref:`sec:modformhecke`, in the sense that `\langle f T_p, x\rangle = \langle f, T_p x \rangle`. When `p\mid N`, the definition is the same, except that the matrix `\abcd{p}{0}{0}{1}` is not included in the sum (see :ref:`thm:modsymformpairing`). There is a similar definition of `T_n` for `n` composite (see Section :ref:`sec:gendefn`). .. example:: For example, when `N=11`, we have .. math:: :nowrap: \begin{eqnarray*} T_2\{0,1/5\} &=& \{0,2/5\} + \{0,1/10\} + \{1/2,3/5\}\\ &=& -2\{0,1/5\}. \end{eqnarray*} See :ref:`diagram:t2`. .. figure:: :label: diagram:t2 Image of `\{0,1/5\}` under `T_2` .. image:: images/t2.* :align: center .. _sec:heckemanin: Hecke Operators on Manin Symbols ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ In :cite:`merel:1585`, L. Merel gives a description of the action of `T_p` directly on Manin symbols `[r_i]` (see Section :ref:`sec:hecke_on_manin` for details). For example, when `p=2` and `N` is odd, we have .. math:: :label: eqn:t2merel T_2([r_i]) = [r_i]\mtwo{1}{0}{0}{2} + [r_i]\mtwo{2}{0}{0}{1} + [r_i]\mtwo{2}{1}{0}{1} + [r_i]\mtwo{1}{0}{1}{2}. For any prime, let `C_p` be the set of matrices constructed using the following algorithm (see :cite:`[\S2.4]{cremona:algs}`): .. algorithm:: Cremona's Heilbronn Matrices :label: alg:crheil .. index:: Heilbronn matrices Given a prime `p`, this algorithm outputs a list of `2\times 2` matrices of determinant `p` that can be used to compute the Hecke operator `T_p`. 1. Output `\mtwo{1}{0}{0}{p}`. 2. For `\ds r = \left\lceil -\frac{p}{2} \right\rceil, \ldots, \left\lfloor \frac{p}{2} \right\rfloor`: a. Let `x_1 = p`, `x_2 = -r`, `y_1 = 0`, `y_2 = 1`, `a=-p`, `b=r`. b. Output `\mtwo{x_1}{x_2}{y_1}{y_2}`. c. As long as `b\neq 0`, do the following: i. Let `q` be the integer closest to `a/b` (if `a/b` is a half integer, round away from `0`). ii. Let `c=a-bq`, `a=-b`, `b=c`. iii. Set `x_3=qx_2 - x_1,\, x_1 = x_2,\, x_2 = x_3`, and\\ `y_3=qy_2 - y_1,\, y_1 = y_2,\, y_2 = y_3`. iv. Output `\mtwo{x_1}{x_2}{y_1}{y_2}`. .. proposition:: Cremona, Merel Let `C_p` be as above. Then for `p\nmid N` and `[x]\in \M_2(\Gamma_0(N))` a Manin symbol, we have .. math:: T_p([x]) = \sum_{g \in C_p} [xg]. .. proof:: See Proposition~2.4.1 of :cite:`cremona:algs`. There are other lists of matrices, due to Merel, that work even when `p\mid N` (see Section :ref:`sec:hecke_on_manin`). .. index:: pair: Sage; Heilbronn matrices The command ``HeilbronnCremonaList(p)``, for `p` prime, outputs the list of matrices from :ref:`alg:crheil`. :: sage: HeilbronnCremonaList(2) [[1, 0, 0, 2], [2, 0, 0, 1], [2, 1, 0, 1], [1, 0, 1, 2]] sage: HeilbronnCremonaList(3) [[1, 0, 0, 3], [3, 1, 0, 1], [1, 0, 1, 3], [3, 0, 0, 1], [3, -1, 0, 1], [-1, 0, 1, -3]] sage: HeilbronnCremonaList(5) [[1, 0, 0, 5], [5, 2, 0, 1], [2, 1, 1, 3], [1, 0, 3, 5], [5, 1, 0, 1], [1, 0, 1, 5], [5, 0, 0, 1], [5, -1, 0, 1], [-1, 0, 1, -5], [5, -2, 0, 1], [-2, 1, 1, -3], [1, 0, -3, 5]] sage: len(HeilbronnCremonaList(37)) 128 sage: len(HeilbronnCremonaList(389)) 1892 sage: len(HeilbronnCremonaList(2003)) 11662 .. index:: pair: Sage; Hecke operator `T_2` .. example:: We compute the matrix of `T_2` on `\sM_2(\Gamma_0(2))`: :: sage: M = ModularSymbols(2,2) sage: M.T(2).matrix() [1] .. index:: pair: Sage; Hecke operators `\sM_2(\Gamma_0(6))` .. example:: We compute some Hecke operators on `\sM_2(\Gamma_0(6))`: :: sage: M = ModularSymbols(6, 2) sage: M.T(2).matrix() [ 2 1 -1] [-1 0 1] [-1 -1 2] sage: M.T(3).matrix() [3 2 0] [0 1 0] [2 2 1] sage: M.T(3).fcp() # factored characteristic polynomial (x - 3) * (x - 1)^2 For `p\geq 5` we have `T_p = p+1`, since `M_2(\Gamma_0(6))` is spanned by generalized Eisenstein series (see Chapter :ref:`ch:eisen`). .. index:: pair: Sage; Hecke operators `\sM_2(\Gamma_0(39))` .. example:: We compute the Hecke operators on `\sM_2(\Gamma_0(39))`: :: sage: M = ModularSymbols(39, 2) sage: T2 = M.T(2) sage: T2.matrix() [ 3 0 -1 0 0 1 1 -1 0] [ 0 0 2 0 -1 1 0 1 -1] [ 0 1 0 -1 1 1 0 1 -1] [ 0 0 1 0 0 1 0 1 -1] [ 0 -1 2 0 0 1 0 1 -1] [ 0 0 1 1 0 1 1 -1 0] [ 0 0 0 -1 0 1 1 2 0] [ 0 0 0 1 0 0 2 0 1] [ 0 0 -1 0 0 0 1 0 2] sage: T2.fcp() # factored characteristic polynomial (x - 3)^3 * (x - 1)^2 * (x^2 + 2*x - 1)^2 The Hecke operators commute, so their eigenspace structures are related. .. link :: sage: T2 = M.T(2).matrix() sage: T5 = M.T(5).matrix() sage: T2*T5 - T5*T2 == 0 True sage: T5.charpoly().factor() (x^2 - 8)^2 * (x - 6)^3 * (x - 2)^2 The decomposition of `T_2` is a list of the kernels of `(f^e)(T_2)`, where `f` runs through the irreducible factors of the characteristic polynomial of `T_2` and `f^e` exactly divides this characteristic polynomial. Using Sage, we find them: :: sage: M = ModularSymbols(39, 2) sage: M.T(2).decomposition() [ Modular Symbols subspace of dimension 3 of Modular Symbols space of dimension 9 for Gamma_0(39) of weight 2 with sign 0 over Rational Field, Modular Symbols subspace of dimension 2 of Modular Symbols space of dimension 9 for Gamma_0(39) of weight 2 with sign 0 over Rational Field, Modular Symbols subspace of dimension 4 of Modular Symbols space of dimension 9 for Gamma_0(39) of weight 2 with sign 0 over Rational Field ] .. _sec:maninboundary: Computing the Boundary Map -------------------------- In Section :ref:`sec:modsym` we defined a map `\delta: \sM_2(\Gamma_0(N)) \to \sB_2(\Gamma_0(N))`. The kernel of this map is the space `\sS_2(\Gamma_0(N))` of cuspidal modular symbols. This kernel will be important in computing cusp forms in Section :ref:`sec:computingmodform` below. .. index:: pair: boundary map; computing To compute the boundary map on `[\gamma]`, note that `[\gamma] = \{\gamma(0),\gamma(\infty)\}`, so if `\gamma=\abcd{a}{b}{c}{d}`, then .. math:: \delta([\gamma]) = \{\gamma(\infty)\} - \{\gamma(0)\} = \{a/c\} - \{b/d\}. Computing this boundary map would appear to first require an algorithm to compute the set `C(\Gamma_0(N)) = \Gamma_0(N) \backslash \P^1(\Q)` of cusps for `\Gamma_0(N)`. In fact, there is a trick that computes the set of cusps in the course of running the algorithm. First, give an algorithm for deciding whether or not two elements of `\P^1(\Q)` are equivalent modulo the action of `\Gamma_0(N)`. Then simply construct `C(\Gamma_0(N))` in the course of computing the boundary map, i.e., keep a list of cusps found so far, and whenever a new cusp class is discovered, add it to the list. The following proposition, which is proved in :cite:`[Prop. 2.2.3]{cremona:algs}`, explains how to determine whether two cusps are equivalent. .. proposition:: Cremona :label: prop:cusp1g0 Let `(c_i,d_i)`, `i=1,2`, be pairs of integers with `\gcd(c_i,d_i)=1` and possibly `d_i=0`. There is `g\in\Gamma_0(N)` such that `g (c_1/d_1)=c_2/d_2` in `\P^1(\Q)` if and only if .. math:: s_1 d_2 \con s_2 d_1 \pmod{\gcd(d_1 d_2,N)} where `s_j` satisfies `c_j s_j\con 1\pmod{d_j}`. .. index:: pair: Sage; boundary map pair: Sage; cuspidal submodule In Sage the command :obj:`boundary_map()` computes the boundary map from `\sM_2(\Gamma_0(N))` to `\sB_2(\Gamma_0(N))`, and the :obj:`cuspidal_submodule` command computes its kernel. For example, for level `2` the boundary map is given by the matrix `[1 \,\,\, -1]`, and its kernel is the `0` space: :: sage: M = ModularSymbols(2, 2) sage: M.boundary_map() Hecke module morphism boundary map defined by the matrix [ 1 -1] Domain: Modular Symbols space of dimension 1 for Gamma_0(2) of weight ... Codomain: Space of Boundary Modular Symbols for Congruence Subgroup Gamma0(2) ... sage: M.cuspidal_submodule() Modular Symbols subspace of dimension 0 of Modular Symbols space of dimension 1 for Gamma_0(2) of weight 2 with sign 0 over Rational Field The smallest level for which the boundary map has nontrivial kernel, i.e., for which `\sS_2(\Gamma_0(N))\neq 0`, is `N=11`. :: sage: M = ModularSymbols(11, 2) sage: M.boundary_map().matrix() [ 1 -1] [ 0 0] [ 0 0] sage: M.cuspidal_submodule() Modular Symbols subspace of dimension 2 of Modular Symbols space of dimension 3 for Gamma_0(11) of weight 2 with sign 0 over Rational Field sage: S = M.cuspidal_submodule(); S Modular Symbols subspace of dimension 2 of Modular Symbols space of dimension 3 for Gamma_0(11) of weight 2 with sign 0 over Rational Field sage: S.basis() ((1,8), (1,9)) The following illustrates that the Hecke operators preserve `\sS_2(\Gamma_0(N))`: .. link :: sage: S.T(2).matrix() [-2 0] [ 0 -2] sage: S.T(3).matrix() [-1 0] [ 0 -1] sage: S.T(5).matrix() [1 0] [0 1] A nontrivial fact is that for `p` prime the eigenvalue of each of these matrices is `p+1 - \#E(\F_p)`, where `E` is the elliptic curve `X_0(11)` defined by the (affine) equation `y^2 + y = x^3 - x^2 - 10x - 20.` For example, we have .. link :: sage: E = EllipticCurve([0,-1,1,-10,-20]) sage: 2 + 1 - E.Np(2) -2 sage: 3 + 1 - E.Np(3) -1 sage: 5 + 1 - E.Np(5) 1 sage: 7 + 1 - E.Np(7) -2 The same numbers appear as the eigenvalues of Hecke operators: .. link :: sage: [S.T(p).matrix()[0,0] for p in [2,3,5,7]] [-2, -1, 1, -2] In fact, something similar happens for every elliptic curve over `\Q`. The book :cite:`diamond-shurman` (especially Chapter~8) is about this striking numerical relationship between the number of points on elliptic curves modulo `p` and coefficients of modular forms. .. _sec:basiss2one: Computing a Basis for `S_2(\Gamma_0(N))` ----------------------------------------- This section is about a method for using modular symbols to compute a basis for `S_2(\Gamma_0(N))`. It is not the most efficient for certain applications, but it is easy to explain and understand. See Section :ref:`sec:computingmodform` for a method that takes advantage of additional structure of `S_2(\Gamma_0(N))`. Let `\sM_2(\Gamma_0(N);\Q)` and `\sS_2(\Gamma_0(N);\Q)` be the spaces of modular symbols and cuspidal modular symbols over `\Q`. Before we begin, we describe a simple but crucial fact about the relation between cusp forms and Hecke operators. .. index:: Hecke operator If `f = \sum b_n q^n \in \C[[q]]` is a power series, let `a_n(f) = b_n` be the `n` coefficient of `f`. Notice that `a_n` is a `\C`-linear map `\C[[q]] \to \C`. .. index:: Hecke operator As explained in :cite:`[Prop. 5.3.1]{diamond-shurman}` and :cite:`[\S{}VII.3]{lang:modular}` (recall also :ref:`prop:qexpTn`), the Hecke operators `T_n` act on elements of `M_2(\Gamma_0(N))` as follows (where `k=2` below): .. math:: :label: eqn:hecke2 T_n\left(\sum_{m=0}^{\infty} a_m q^m\right) = \sum_{m=0}^{\infty} \left(\sum_{1\leq d\,\mid\, \gcd(n,m)} \eps(d) \cdot d^{k-1} \cdot a_{mn/d^2}\right) q^m, where `\eps(d)=1` if `\gcd(d,N)=1` and `\eps(d)=0` if `\gcd(d,N)\neq 1`. (Note: More generally, if `f \in M_k(\Gamma_1(N))` is a modular form with Dirichlet character `\eps`, then the above formula holds; above we are considering this formula in the special case when `\eps` is the trivial character and `k=2`.) .. lemma:: :label: lem:hecketn Suppose `f\in \C[[q]]` and `n` is a positive integer. Let `T_n` be the operator on `q`-expansions (formal power series) defined by :eq:`eqn:hecke2`. Then .. math:: a_1(T_n(f)) = a_n(f). .. proof:: The coefficient of `q` in :eq:`eqn:hecke2` is `\eps(1)\cdot 1 \cdot a_{1 \cdot n/1^2} = a_n`. The :defn:`Hecke algebra` `\T` is the ring generated by all Hecke operators `T_n` acting on `M_k(\Gamma_1(N))`. Let `\T'` denote the image of the Hecke algebra in `\End(S_2(\Gamma_0(N)))`, and let `\T'_\C=\T'\tensor_\Z\C` be the `\C`-span of the Hecke operators. Let `\tT_\C` denote the subring of `\End(\C[[q]])` generated over `\C` by all Hecke operators acting on formal power series via definition :eq:`eqn:hecke2`. .. proposition:: :label: prop:tildeduality There is a bilinear pairing of complex vector spaces .. math:: \C[[q]] \cross \tT_\C \to \C given by .. math:: \langle f, t \rangle = a_1(t(f)). If `f` is such that `\langle f, t\rangle = 0` for all `t\in \tT_\C`, then `f=0`. .. proof:: The pairing is bilinear since both `t` and `a_1` are linear. Suppose `f\in \C[[q]]` is such that `\langle f, t\rangle = 0` for all `t\in \tT_\C`. Then `\langle f, T_n\rangle = 0` for each positive integer `n`. But by :ref:`lem:hecketn` we have .. math:: a_n(f) = a_1(T_n(f)) = 0 for all `n`; thus `f=0`. .. proposition:: :label: prop:duality There is a perfect bilinear pairing of complex vector spaces .. math:: S_2(\Gamma_0(N)) \cross \T'_\C \to \C given by .. math:: \langle f, t \rangle = a_1(t(f)). .. proof:: The pairing has `0` kernel on the left by :ref:`prop:tildeduality`. Suppose that `t\in\T'_\C` is such that `\langle f, t\rangle =0` for all `f \in S_2(\Gamma_0(N))`. Then `a_1(t(f)) = 0` for all `f`. For any `n`, the image `T_n(f)` is also a cusp form, so `a_1(t(T_n(f))) = 0` for all `n` and `f`. Finally the fact that `\T'` is commutative and :ref:`lem:hecketn` together imply that for all `n` and `f`, .. math:: 0 = a_1(t(T_n(f))) = a_1(T_n(t(f))) = a_n(t(f)), so `t(f)=0` for all `f`. Thus `t` is the `0` operator. Since `S_2(\Gamma_0(N))` has finite dimension and the kernel on each side of the pairing is `0`, it follows that the pairing is perfect, i.e., defines an *isomorphism* .. math:: \T'_\C \isom \Hom_{\C}(S_2(\Gamma_0(N));\C). By :ref:`prop:duality` there is an isomorphism of vector spaces .. math:: :label: eqn:s2isomtdual \Psi: S_2(\Gamma_0(N)) \xrightarrow{\,\,\isom\,\,} \Hom(\T'_\C,\C) that sends `f \in S_2(\Gamma_0(N))` to the homomorphism .. math:: t \mapsto a_1(t(f)). For any `\C`-linear map `\vphi:\T'_\C\to \C`, let .. math:: f_{\vphi} = \sum_{n=1}^{\infty} \vphi(T_n)q^n \in\C[[q]]. .. lemma:: The series `f_{\vphi}` is the `q`-expansion of `\Psi^{-1}(\vphi) \in S_2(\Gamma_0(N))`. .. proof:: Note that it is not even *a priori* obvious that `f_{\vphi}` is the `q`-expansion of a modular form. Let `g = \Psi^{-1}(\vphi)`, which is by definition the unique element of `S_2(\Gamma_0(N))` such that `\langle g, T_n \rangle = \vphi(T_n)` for all `n`. By :ref:`lem:hecketn`, we have .. math:: \langle f_{\vphi}, T_n \rangle = a_1(T_n(f_\vphi)) = a_n(f_{\vphi}) = \vphi(T_n), so `\langle f_{\vphi} - g, T_n \rangle = 0` for all `n`. :ref:`prop:tildeduality` implies that `f_\vphi - g = 0`, so `f_{\vphi} = g = \Psi^{-1}(\vphi)`, as claimed. **Conclusion:** The cusp forms `f_{\vphi}`, as `\vphi` varies through a basis of `\Hom(\T'_\C,\C)`, form a basis for `S_2(\Gamma_0(N))`. In particular, we can compute `S_2(\Gamma_0(N))` by computing `\Hom(\T'_{\C},\C)`, where we compute `\T'` in any way we want, e.g., using a space that contains an isomorphic copy of `S_2(\Gamma_0(N))`. .. algorithm:: Basis of Cusp Forms :label: alg:s2basis Given positive integers `N` and `B`, this algorithm computes a basis for `S_2(\Gamma_0(N))` to precision `O(q^B)`. 1. Compute `\sM_2(\Gamma_0(N);\Q)` via the presentation of Section :ref:`sec:maninsyms`. 2. Compute the subspace `\sS_2(\Gamma_0(N);\Q)` of cuspidal modular symbols as in Section :ref:`sec:maninboundary`. 3. Let `d=\frac{1}{2}\cdot \dim\sS_2(\Gamma_0(N);\Q)`. By :ref:`prop:dimsym2`, `d` is the dimension of `S_2(\Gamma_0(N))`. 4. Let `[T_n]` denote the matrix of `T_n` acting on a basis of `\sS_2(\Gamma_0(N);\Q)`. For a matrix `A`, let `a_{ij}(A)` denote the `ij`th entry of `A`. For various integers `i,j` with `0\leq i,j \leq d-1`, compute formal `q`-expansions .. math:: f_{ij}(q) = \sum_{n=1}^{B-1} a_{ij}([T_n])q^n + O(q^{B}) \in \Q[[q]] until we find enough to span a space of dimension `d` (or exhaust all of them). These `f_{ij}` are a basis for `S_2(\Gamma_0(N))` to precision `O(q^{B})`. Examples ~~~~~~~~ We use Sage to demonstrate :ref:`alg:s2basis`. .. index:: pair: Sage; basis for `S_2(\Gamma_0(N))` .. example:: The smallest `N` with `S_2(\Gamma_0(N))\neq 0` is `N=11`. :: sage: M = ModularSymbols(11); M.basis() ((1,0), (1,8), (1,9)) sage: S = M.cuspidal_submodule(); S Modular Symbols subspace of dimension 2 of Modular Symbols space of dimension 3 for Gamma_0(11) of weight 2 with sign 0 over Rational Field We compute a few Hecke operators, and then read off a nonzero cusp form, which forms a basis for `S_2(\Gamma_0(11))`: .. link :: sage: S.T(2).matrix() [-2 0] [ 0 -2] sage: S.T(3).matrix() [-1 0] [ 0 -1] Thus .. math:: f_{0,0} = q - 2q^2 - q^3 + \cdots \in S_2(\Gamma_0(11)) forms a basis for `S_2(\Gamma_0(11))`. .. example:: We compute a basis for `S_2(\Gamma_0(33))` to precision `O(q^6)`. :: sage: M = ModularSymbols(33) sage: S = M.cuspidal_submodule(); S Modular Symbols subspace of dimension 6 of Modular Symbols space of dimension 9 for Gamma_0(33) of weight 2 with sign 0 over Rational Field .. link Thus `\dim S_2(\Gamma_0(33)) = 3`. .. link :: sage: R. = PowerSeriesRing(QQ) sage: v = [S.T(n).matrix()[0,0] for n in range(1,6)] sage: f00 = sum(v[n-1]*q^n for n in range(1,6)) + O(q^6) sage: f00 q - q^2 - q^3 + q^4 + O(q^6) This gives us one basis element of `S_2(\Gamma_0(33))`. It remains to find two others. We find .. link :: sage: v = [S.T(n).matrix()[0,1] for n in range(1,6)] sage: f01 = sum(v[n-1]*q^n for n in range(1,6)) + O(q^6) sage: f01 -2*q^3 + O(q^6) and .. link :: sage: v = [S.T(n).matrix()[1,0] for n in range(1,6)] sage: f10 = sum(v[n-1]*q^n for n in range(1,6)) + O(q^6) sage: f10 q^3 + O(q^6) This third one is (to our precision) a scalar multiple of the second, so we look further. .. link :: sage: v = [S.T(n).matrix()[1,1] for n in range(1,6)] sage: f11 = sum(v[n-1]*q^n for n in range(1,6)) + O(q^6) sage: f11 q - 2*q^2 + 2*q^4 + q^5 + O(q^6) This latter form is clearly not in the span of the first two. Thus we have the following basis for `S_2(\Gamma_0(33))` (to precision `O(q^6)`): .. math:: f_{00} &= q - q^{2} - q^{3} + q^{4} + \cdots,\\ f_{11} &= q - 2q^{2} + 2q^{4} + q^{5} + \cdots,\\ f_{10} &= q^{3} + \cdots. .. example:: Next consider `N=23`, where we have .. math:: d = \dim S_2(\Gamma_0(23)) = 2. The command :obj:`q_expansion_cuspforms` computes matrices `T_n` and returns a function `f` such that `f(i,j)` is the `q`-expansion of `f_{i,j}` to some precision. (For efficiency reasons, `f(i,j)` in Sage actually computes matrices of `T_n` acting on a basis for the linear dual of `\sS_2(\Gamma_0(N))`.) :: sage: M = ModularSymbols(23) sage: S = M.cuspidal_submodule() sage: S Modular Symbols subspace of dimension 4 of Modular Symbols space of dimension 5 for Gamma_0(23) of weight 2 with sign 0 over Rational Field sage: f = S.q_expansion_cuspforms(6) sage: f(0,0) q - 2/3*q^2 + 1/3*q^3 - 1/3*q^4 - 4/3*q^5 + O(q^6) sage: f(0,1) O(q^6) sage: f(1,0) -1/3*q^2 + 2/3*q^3 + 1/3*q^4 - 2/3*q^5 + O(q^6) Thus a basis for `S_2(\Gamma_0(23))` is .. math:: f_{0,0} &= q - \frac{2}{3}q^{2} + \frac{1}{3}q^{3} - \frac{1}{3}q^{4} - \frac{4}{3}q^{5} + \cdots, \\ f_{1,0} &= -\frac{1}{3}q^{2} + \frac{2}{3}q^{3} + \frac{1}{3}q^{4} - \frac{2}{3}q^{5} + \cdots. Or, in echelon form, .. math:: & q - q^{3} - q^{4} + \cdots\\ & \,\,\,\,\,q^{2} - 2q^{3} - q^{4} + 2q^{5} + \cdots which we computed using .. link :: sage: S.q_expansion_basis(6) [ q - q^3 - q^4 + O(q^6), q^2 - 2*q^3 - q^4 + 2*q^5 + O(q^6) ] .. _sec:computingmodform: Computing `S_2(\Gamma_0(N))` Using Eigenvectors ----------------------------------------------- In this section we describe how to use modular symbols to construct a basis of `S_2(\Gamma_0(N))` consisting of modular forms that are eigenvectors for every element of the ring `\T^{(N)}` generated by the Hecke operator `T_p`, with `p\nmid N`. Such eigenvectors are called :defn:`eigenforms`. Suppose `M` is a positive integer that divides `N`. As explained in :cite:`[VIII.1--2]{lang:modular}`, for each divisor `d` of `N/M` there is a natural :defn:`degeneracy map` `\alpha_{M,d} : S_2(\Gamma_0(M))\ra S_2(\Gamma_0(N))` given by `\alpha_{M,d}(f(q)) = f(q^d)`. The :defn:`new subspace` of `S_2(\Gamma_0(N))`, denoted `S_2(\Gamma_0(N))_{\new}`, is the complementary `\T`-submodule of the `\T`-module generated by the images of all maps `\alpha_{M,d}`, with `M` and `d` as above. It is a nontrivial fact that this complement is well defined; one possible proof uses the Petersson inner product (see :cite:`[\S{}VII.5]{lang:modular}`). .. index:: Petersson inner product The theory of Atkin and Lehner :cite:`atkin-lehner` (see :ref:`thm:ALL` below) asserts that, as a `\T^{(N)}`-module, `S_2(\Gamma_0(N))` decomposes as follows: .. math:: S_2(\Gamma_0(N)) \quad = \bigoplus_{M | N, \,\, d | N/M} \beta_{M,d}(S_2(\Gamma_0(M))_{\new}). To compute `S_2(\Gamma_0(N))` it suffices to compute `S_2(\Gamma_0(M))_{\new}` for each `M\mid N`. We now turn to the problem of computing `S_2(\Gamma_0(N))_{\new}`. Atkin and Lehner :cite:`atkin-lehner` proved that `S_2(\Gamma_0(N))_{\new}` is spanned by eigenforms for all `T_p` with `p\nmid N` and that the common eigenspaces of all the `T_p` with `p\nmid N` each have dimension `1`. Moreover, if `f\in S_2(\Gamma_0(N))_{\new}` is an eigenform then the coefficient of `q` in the `q`-expansion of `f` is nonzero, so it is possible to normalize `f` so the coefficient of `q` is `1` (such a *normalized* eigenform in the new subspace is called a :defn:`newform`). With `f` so normalized, if `T_p(f) = a_p f`, then the `p^{th}` Fourier coefficient of `f` is `a_p`. If `f=\sum_{n=1}^{\infty} a_n q^n` is a normalized eigenvector for all `T_p`, then the `a_n`, with `n` composite, are determined by the `a_p`, with `p` prime, by the following formulas: `a_{nm}=a_n a_m` when `n` and `m` are relatively prime and `a_{p^r} = a_{p^{r-1}} a_p - p a_{p^{r-2}}` for `p\nmid N` prime. When `p \mid N`, `a_{p^r}=a_p^r`. We conclude that in order to compute `S_2(\Gamma_0(N))_{\new}`, it suffices to compute all systems of eigenvalues `\{a_2, a_3, a_5, \ldots\}` of the prime-indexed Hecke operators `T_2, T_3, T_5, \ldots` acting on `S_2(\Gamma_0(N))_{\new}`. Given a system of eigenvalues, the corresponding eigenform is `f=\sum_{n=1}^{\infty} a_n q^n`, where the `a_n`, for `n` composite, are determined by the recurrence given above. In light of the pairing `\langle\, ,\, \rangle` introduced in Section :ref:`sec:modformhecke`, computing the above systems of eigenvalues `\{a_2,a_3, a_5, \ldots \}` amounts to computing the systems of eigenvalues of the Hecke operators `T_p` on the subspace `V` of `\sS_2(\Gamma_0(N))` that corresponds to the new subspace of `S_2(\Gamma_0(N)).` For each proper divisor `M` of `N` and each divisor `d` of `N/M`, let `\phi_{M,d}:\sS_2(\Gamma_0(N)) \ra \sS_2(\Gamma_0(M))` be the map sending `x` to `\abcd{d}{0}{0}{1}x`. Then `V` is the intersection of the kernels of all maps `\phi_{M,d}`. Computing the systems of eigenvalues of a collection of commuting diagonalizable endomorphisms is a problem in linear algebra (see Chapter :ref:`ch:linalg`). .. example:: All forms in `S_2(\Gamma_0(39))` are new. Up to Galois conjugacy, the eigenvalues of the Hecke operators `T_2`, `T_3`, `T_5`, and `T_7` on `\sS_2(\Gamma_0(39))` are `\{1, -1, 2, -4 \}` and `\{a, 1, -2a-2, 2a+2\}`, where `a^2+2a-1=0`. Each of these eigenvalues occur in `\sS_2(\Gamma_0(39))` with multiplicity two; for example, the characteristic polynomial of `T_2` on `\sS_2(\Gamma_0(39))` is `(x - 1)^2\cdot(x^2+2x-1)^2`. Thus `S_2(\Gamma_0(39))` is spanned by .. math:: f_1&=q + q^2 - q^3 - q^4 + 2q^5 - q^6 - 4q^7 + \cdots, \\ f_2&= q + aq^2 + q^3 + (-2a - 1)q^4 + (-2a - 2)q^5 + aq^6 + (2a + 2)q^7 + \cdots, \\ f_3&= q + \sigma(a)q^2 + q^3 + (-2\sigma(a) - 1)q^4 + (-2\sigma(a) - 2)q^5 + \sigma(a)q^6 + \cdots, where `\sigma(a)` is the other `\Gal(\Qbar/\Q)`-conjugate of `a`. Summary ~~~~~~~ To compute the `q`-expansion of a basis for `S_2(\Gamma_0(N))`, we use the degeneracy maps so that we only have to solve the problem for `S_2(\Gamma_0(M))_{\new}`, for all integers `M\mid N`. Using modular symbols, we compute all systems of eigenvalues `\{a_2, a_3,a_5,\ldots\}`, and then write down the corresponding eigenforms `\sum a_n q^n`. Exercises ---------- .. exercise:: :label: ex:x0n Suppose that `\lambda, \lambda' \in \h` are in the same orbit for the action of `\Gamma_0(N)`, i.e., that there exists `g\in \Gamma_0(N)` such that `g(\lambda) = \lambda'`. Let `\Lambda = \Z + \Z\lambda` and `\Lambda' = \Z + \Z\lambda'`. Prove that the pairs `(\C/\Lambda,(\frac{1}{N}\Z+\Lambda)/\Lambda)` and `(\C/\Lambda', (\frac{1}{N}\Z + \Lambda')/\Lambda')` are isomorphic. (By an isomorphism `(E,C)\to (F,D)` of pairs, we mean an isomorphism `\phi: E\to F` of elliptic curves that sends `C` to `D`. You may use the fact that an isomorphism of elliptic curves over `\C` is a `\C`-linear map `\C\to\C` that sends the lattice corresponding to one curve onto the lattice corresponding to the other.) .. exercise:: :label: ex:modsymzero Let `n,m` be integers and `N` a positive integer. Prove that the modular symbol `\{n,m\}` is `0` as an element of `\sM_2(\Gamma_0(N))`. [Hint: See :ref:`ex:01`.] .. exercise:: :label: ex:bij Let `p` be a prime. a. List representative elements of `\P^1(\Z/p\Z)`. b. What is the cardinality of `\P^1(\Z/p\Z)` as a function of `p`? c. Prove that there is a bijection between the right cosets of `\Gamma_0(p)` in `\SL_2(\Z)` and the elements of `\P^1(\Z/p\Z)` that sends `\abcd{a}{b}{c}{d}` to `(c:d)`. (As mentioned in this chapter, the analogous statement is also true when the level is composite; see :cite:`[\S2.2]{cremona:algs}` for complete details.) \end{enumerate} .. exercise:: :label: ex:intermsofmanin Use the inductive proof of :ref:`prop:manintrick` to write `\{0,4/7\}` in terms of Manin symbols for `\Gamma_0(7)`. .. exercise:: :label: ex:heckes2g03 Show that the Hecke operator `T_2` acts as multiplication by `3` on the space `\sM_2(\Gamma_0(3))` as follows: a. Write down right coset representatives for `\Gamma_0(3)` in `\SL_2(\Z)`. b. List all eight relations coming from :ref:`thm:manin_present`. c. Find a single Manin symbols `[r_i]` so that the three other Manin symbols are a nonzero multiple of `[r_i]` modulo the relations found in the previous step. d. Use formula :eq:`eqn:t2merel` to compute `T_2([r_i])`. You will obtain a sum of four symbols. Using the relations above, write this sum as a multiple of `[r_i]`. (The multiple must be `3` or you made a mistake.)