.. _ch:modsym: General Modular Symbols ======================= .. chapter: 8 In this chapter we explain how to generalize the notion of modular symbols given in Chapter :ref:`ch:modform2` to higher weight and more general level. We define Hecke operators on them and their relation to modular forms via the integration pairing. We omit many difficult proofs that modular symbols have certain properties and instead focus on how to compute with modular symbols. For more details see the references given in this section (especially :cite:`merel:1585`) and :cite:`gabor:phd`. Modular symbols are a formalism that make it elementary to compute with homology or cohomology related to certain Kuga-Sato varieties (these are `\cE\times_X \cdots \times_X \cE`, where `X` is a modular curve and `\cE` is the universal elliptic curve over it). It is not necessary to know anything about these Kuga-Sato varieties in order to compute with modular symbols. This chapter is about spaces of modular symbols and how to compute with them. It is by far the most important chapter in this book. The algorithms that build on the theory in this chapter are central to all the computations we will do later in the book. This chapter closely follows Lo\"{i}c Merel's paper :cite:`merel:1585`. First we define modular symbols of weight `k\geq 2`. Then we define the corresponding Manin symbols and state a theorem of Merel-Shokurov, which gives all relations between Manin symbols. (The proof of the Merel-Shokurov theorem is beyond the scope of this book but is presented nicely in :cite:`gabor:phd`.) Next we describe how the Hecke operators act on both modular and Manin symbols and how to compute trace and inclusion maps between spaces of modular symbols of different levels. Not only are modular symbols useful for computation, but they have been used to prove theoretical results about modular forms. For example, certain technical calculations with modular symbols are used in Lo\"{i}c Merel's proof of the uniform boundedness conjecture for torsion points on elliptic curves over number fields (modular symbols are used to understand linear independence of Hecke operators). Another example is :cite:`grigor:phd`, which distills hypotheses about Kato's Euler system in `K_2` of modular curves to a simple formula involving modular symbols (when the hypotheses are satisfied, one obtains a lower bound on the Shafarevich-Tate group of an elliptic curve). .. _sec:modsymgen: Modular Symbols --------------- We recall from Chapter :ref:`ch:modform2` the free abelian group `\sM_2` of modular symbols. We view these as elements of the relative homology of the extended upper half plane `\h^* = \h\union \P^1(\Q)` relative to the cusps. The group `\sM_2` is the free abelian group on symbols `\{\alpha,\beta\}` with .. math:: \alpha, \beta \in \P^1(\Q) = \Q \union \{\infty\} modulo the relations .. math:: \{\alpha,\beta\} + \{\beta,\gamma\} + \{\gamma,\alpha\} = 0, for all `\alpha,\beta,\gamma\in\P^1(\Q)`, and all torsion. More precisely, .. math:: \sM_2 = (F/R)/(F/R)_{\tor}, where `F` is the free abelian group on all pairs `(\alpha,\beta)` and `R` is the subgroup generated by all elements of the form `(\alpha,\beta) + (\beta,\gamma) + (\gamma,\alpha)`. Note that `\sM_2` is a huge free abelian group of countable rank. For any integer `n\geq 0`, let `\Z[X,Y]_n` be the abelian group of homogeneous polynomials of degree `n` in two variables `X,Y`. .. remark:: Note that `\Z[X,Y]_n` is isomorphic to `\Sym^{n}(\Z\cross \Z)` as a group, but certain natural actions are different. In :cite:`merel:1585`, Merel uses the notation `\Z_{n}[X,Y]` for what we denote by `\Z[X,Y]_{n}`. Now fix an integer `k\geq 2`. Set .. math:: \sM_k = \Z[X,Y]_{k-2} \tensor_\Z \sM_2, which is a torsion-free abelian group whose elements are sums of expressions of the form `X^{i}Y^{k-2-i}\tensor \{\alpha,\beta\}`. For example, .. math:: X^3 \tensor \{0,1/2\} -17 XY^2 \tensor \{\infty,1/7\} \in \sM_{5}. Fix a finite index subgroup `G` of `\SL_2(\Z)`. Define a :defn:`left action of $G$` on `\Z[X,Y]_{k-2}` as follows. If `g=\abcd{a}{b}{c}{d}\in G` and `P(X,Y)\in \Z[X,Y]_{k-2}`, let .. math:: (g P)(X,Y) = P(dX-bY, -cX+aY). Note that if we think of `z=(X,Y)` as a column vector, then .. math:: (g P)(z) = P(g^{-1}z), since `g^{-1} = \abcd{\hfill{}d}{-b}{-c}{\hfill{}a}`. The reason for the inverse is so that this is a left action instead of a right action, e.g., if `g,h\in G`, then .. math:: ((gh)P)(z) = P((gh)^{-1}z) = P(h^{-1}g^{-1}z) = (hP)(g^{-1}z) = (g(hP))(z). Recall that we let `G` act on the left on `\sM_2` by .. math:: g\{\alpha, \beta\} = \{g(\alpha), g(\beta)\}, where `G` acts via linear fractional transformations, so if `g=\abcd{a}{b}{c}{d}`, then .. math:: g(\alpha)=\frac{a\alpha + b}{c\alpha + d}. For example, useful special cases to remember are that if `g=\abcd{a}{b}{c}{d}`, then .. math:: g(0) = \frac{b}{d} \qquad\text{and}\qquad g(\infty) = \frac{a}{c}. (Here we view `\infty` as `1/0` in order to describe the action.) We now combine these two actions to obtain a left action of `G` on `\sM_{k}`, which is given by .. math:: g(P \tensor \{\alpha, \beta\}) = (gP) \tensor\{g(\alpha), g(\beta)\}. For example, .. math:: \mtwo{\hfill 1}{\hfill 2}{-2}{-3} (X^3 \tensor \{0,1/2\}) &= (-3X - 2Y)^3 \tensor\left\{-\frac{2}{3}, -\frac{5}{8}\right\} \\ &\hspace{-4em}= (-27X^3 - 54X^2Y - 36XY^2 - 8Y^3)\tensor \left\{-\frac{2}{3}, -\frac{5}{8}\right\}. We will often write `P(X,Y)\{\alpha,\beta\}` for `P(X,Y)\tensor\{\alpha,\beta\}`. .. definition:: Modular Symbols :label: defn:modsym Let `k\geq 2` be an integer and let `G` be a finite index subgroup of `\SL_2(\Z)`. The space :defn:`$\sM_k(G)$` of :defn:`weight $k$ modular symbols for $G$` is the quotient of `\sM_k` by all relations `gx - x` for `x \in \sM_k`, `g\in G`, and by any torsion. Note that `\sM_k` is a torsion-free abelian group, and it is a nontrivial fact that `\sM_k` has finite rank. We denote modular symbols for `G` in exactly the same way we denote elements of `\sM_k`; the group `G` will be clear from context. The space of :defn:`modular symbols over a ring $R$` is .. index:: `\sM_k(G;R)` .. math:: \sM_k(G;R) = \sM_k(G)\tensor_\Z R. .. _sec:manin: Manin Symbols ------------- Let `G` be a finite index subgroup of `\SL_2(\Z)` and `k\geq 2` an integer. Just as in Chapter :ref:`ch:modform2` it is possible to compute `\sM_k(G)` using a computer, despite that, as defined above, `\sM_k(G)` is the quotient of one infinitely generated abelian group by another one. This section is about Manin symbols, which are a distinguished subset of `\sM_k(G)` that lead to a finite presentation for `\sM_k(G)`. Formulas written in terms of Manin symbols are frequently much easier to compute using a computer than formulas in terms of modular symbols. Suppose `P\in \Z[X,Y]_{k-2}` and `g\in \SL_2(\Z)`. Then the :defn:`Manin symbol` associated to this pair of elements is .. math:: [P,g] = g(P\{0,\infty\}) \in \sM_k(G). Notice that if `Gg = Gh`, then `[P,g] = [P,h]`, since the symbol `g(P\{0,\infty\})` is invariant by the action of `G` on the left (by definition, since it is a modular symbol for `G`). Thus for a right coset `Gg` it makes sense to write `[P, Gg]` for the symbol `[P,h]` for any `h\in Gg`. Since `G` has finite index in `\SL_2(\Z)`, the abelian group generated by Manin symbols is of finite rank, generated by .. math:: \bigl\{ [X^{k-2-i}Y^i, \, Gg_j] \, : \, i = 0,\ldots, k-2 \quad\text{and}\quad j = 0,\ldots, r \bigr\}, where `g_0, \ldots, g_r` run through representatives for the right cosets `G\backslash \SL_2(\Z)`. We next show that every modular symbol can be written as a `\Z`-linear combination of Manin symbols, so they generate `\sM_k(G)`. .. proposition:: :label: prop:mangen The Manin symbols generate `\sM_k(G)`. .. proof:: The proof if very similar to that of :ref:`prop:manintrick` except we introduce an extra twist to deal with the polynomial part. Suppose that we are given a modular symbol `P\{\alpha,\beta\}` and wish to represent it as a sum of Manin symbols. Because .. math:: P\{a/b,c/d\} = P\{a/b,0\}+P\{0,c/d\}, it suffices to write `P\{0,a/b\}` in terms of Manin symbols. Let .. math:: 0=\frac{p_{-2}}{q_{-2}} = \frac{0}{1},\,\, \frac{p_{-1}}{q_{-1}}=\frac{1}{0},\,\, \frac{p_0}{1}=\frac{p_0}{q_0},\,\, \frac{p_1}{q_1},\,\, \frac{p_2}{q_2},\,\ldots,\,\frac{p_r}{q_r}=\frac{a}{b} denote the continued fraction convergents of the rational number `a/b`. Then .. math:: p_j q_{j-1} - p_{j-1} q_j = (-1)^{j-1}\qquad \text{for }-1\leq j\leq r. If we let `g_j = \mtwo{(-1)^{j-1}p_j}{p_{j-1}}{(-1)^{j-1}q_j}{q_{j-1}}`, then `g_j\in\sltwoz` and .. math:: P\{0,a/b\} &=P\sum_{j=-1}^{r}\left\{\frac{p_{j-1}}{q_{j-1}},\frac{p_j}{q_j}\right\}\\ &=\sum_{j=-1}^{r} g_j((g_j^{-1}P)\{0,\infty\})\\ &=\sum_{j=-1}^{r} [g_j^{-1}P,\,\,g_j]. Since `g_j\in\sltwoz` and `P` has integer coefficients, the polynomial `g_j^{-1}P` also has integer coefficients, so we introduce no denominators. Now that we know the Manin symbols generate `\sM_k(G)`, we next consider the relations between Manin symbols. Fortunately, the answer is fairly simple (though the proof is not). Let .. math:: \sigma = \mtwo{0}{-1}{1}{\hfill 0},\qquad \tau = \mtwo{0}{-1}{1}{-1}, \qquad J = \mtwo{-1}{\hfill 0}{\hfill 0}{-1}. Define a :defn:`right action of $\SL_2(\Z)$` on Manin symbols as follows. If `h \in \SL_2(\Z)`, let .. math:: [P, g]h = [h^{-1} P, gh]. This is a right action because both `P\mapsto h^{-1}P` and `g\mapsto gh` are right actions. .. theorem:: :label: thm:mansym If `x` is a Manin symbol, then .. math:: x + x\sigma &= 0,\\ x + x\tau + x\tau^{2} &= 0,\\ x - xJ &= 0. Moreover, these are all the relations between Manin symbols, in the sense that the space `\sM_k(G)` of modular symbols is isomorphic to the quotient of the free abelian group on the finitely many symbols `[X^{i}Y^{k-2-i},Gg]` (for `i=0,\ldots, k-2` and `Gg \in G\backslash \SL_2(\Z)`) by the above relations and any torsion. .. proof:: First we prove that the Manin symbols satisfy the above relations. We follow Merel's proof (see :cite:`[\S1.2]{merel:1585}`). Note that .. math:: \sigma(0) = \sigma^2(\infty) = \infty \qquad\text{and}\qquad \tau(1) = \tau^2(0) = \infty. Writing `x=[P,g]`, we have .. math:: [P,g] + [P,g]\sigma &= [P,g] + [\sigma^{-1}P, g\sigma]\\ &= g(P\{0,\infty\}) + g\sigma (\sigma^{-1}P \{0,\infty\})\\ &= (gP) \{ g(0), g(\infty) \} + (g\sigma)(\sigma^{-1} P)\{ g\sigma(0), g\sigma(\infty)\} \\ &= (gP) \{ g(0), g(\infty) \} + (gP)\{ g(\infty), g(0)\} \\ &= (gP)\{ g(0), g(\infty) \} + \{ g(\infty), g(0)\})\\ &= 0. Also, .. math:: [P,g] &+ [P,g]\tau + [P,g]\tau^2 = [P,g] + [\tau^{-1}P, g\tau] + [\tau^{-2}P, g\tau^2]\\ &= g(P\{0,\infty\}) + g\tau(\tau^{-1}P \{0,\infty\}) + g\tau^2(\tau^{-2}P \{0,\infty\}) \\ &= (gP) \{ g(0), g(\infty) \} + (gP) \{ g \tau(0),g\tau(\infty)\} + (gP) \{ g\tau^2(0),\tau^2(\infty)\} \\ &= (gP) \{ g(0), g(\infty) \} + (gP) \{ g(1),g(0)\}) + (gP) \{ g(\infty), g(1)\} \\ &= (gP)\bigl(\{ g(0), g(\infty)\} + \{ g(\infty), g(1)\} + \{ g(1),g(0)\}\bigr) \\ &= 0. Finally, .. math:: [P,g] + [P,g]J &= g(P\{0,\infty\}) - gJ(J^{-1} P \{gJ(0), gJ(\infty)\}\\ &= (gP)\{g(0),g(\infty)\} - (gP) \{g(0),g(\infty)\}\\ &= 0, where we use that `J` acts trivially via linear fractional transformations. This proves that the listed relations are all satisfied. That the listed relations are all relations is more difficult to prove. One approach is to show (as in :cite:`[\S1.3]{merel:1585}`) that the quotient of Manin symbols by the above relations and torsion is isomorphic to a space of Shokurov symbols, which is in turn isomorphic to `\sM_k(G)`. A much better approach is to apply some results from group cohomology, as in :cite:`gabor:phd`. If `G` is a finite index subgroup and we have an algorithm to enumerate the right cosets `G\backslash \SL_2(\Z)` and to decide which coset an arbitrary element of `\SL_2(\Z)` belongs to, then :ref:`thm:mansym` and the algorithms of Chapter :ref:`ch:linalg` yield an algorithm to compute `\sM_k(G;\Q)`. Note that if `J\in G`, then the relation `x-xJ=0` is automatic. .. remark:: The matrices `\sigma` and `\tau` *do not commute*, so in computing `\sM_k(G;\Q)`, one cannot first quotient out by the two-term `\sigma` relations, then quotient out only the remaining free generators by the `\tau` relations, and get the right answer in general. Coset Representatives and Manin Symbols ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The following is analogous to :ref:`prop:p1bij`: .. proposition:: :label: prop:gamma1cosets The right cosets `\Gamma_1(N)\backslash \SL_2(\Z)` are in bijection with pairs `(c,d)` where `c,d\in\Z/N\Z` and `\gcd(c,d,N)=1`. The coset containing a matrix `\abcd{a}{b}{c}{d}` corresponds to `(c,d)`. .. proof:: This proof is copied from :cite:`[pg.~203]{cremona:gammaone}`, except in that paper Cremona works with the analogue of `\Gamma_1(N)` in `\PSL_2(\Z)`, so his result is slightly different. Suppose `\gamma_i = \abcd{a_i}{b_i}{c_i}{d_i} \in \SL_2(\Z)`, for `i=1,2`. We have .. math:: \gamma_1 \gamma_2^{-1} = \mtwo{a_1}{b_1}{c_1}{d_1} \mtwo{\hfill{}d_2}{-b_2}{-c_2}{\hfill{}a_2} =\mtwo{a_1 d_2 - b_1 c_2}{*}{c_1 d_2 - d_1 c_2}{a_2 d_1 - b_2 c_1}, which is in `\Gamma_1(N)` if and only if .. math:: :label: eqn:cos1a c_1 d_2 - d_1 c_2 \con 0 \pmod{N} and .. math:: :label: eqn:cos1b a_2 d_1 - b_2 c_1 \con a_1 d_2 - b_1 c_2 \con 1\pmod{N}. Since the `\gamma_i` have determinant `1`, if `(c_1,d_1)=(c_2,d_2)\pmod{N}`, then the congruences :eq:`eqn:cos1a`--:eq:`eqn:cos1b` hold. Conversely, if :eq:`eqn:cos1a`--:eq:`eqn:cos1b` hold, then .. math:: c_2 &\con a_2 d_1 c_2 - b_2 c_1 c_2 \\ &\con a_2 d_2 c_1 - b_2 c_2 c_1 \quad\text{ since }d_1 c_2 \con d_2 c_1 \pmod{N}\\ &\con c_1 \qquad\qquad\qquad\quad\,\text{since }a_2 d_2 - b_2 c_2 = 1, and likewise .. math:: d_2 \con a_2 d_1 d_2 - b_2 c_1 d_2 \con a_2 d_1 d_2 - b_2 d_1 c_2 \con d_1\pmod{N}. Thus we may view weight `k` Manin symbols for `\Gamma_1(N)` as triples of integers `(i,c,d)`, where `0\leq i\leq k-2` and `c, d\in\Z/N\Z` with `\gcd(c,d,N)=1`. Here `(i,c,d)` corresponds to the Manin symbol `[X^iY^{k-2-i}, \abcd{a}{b}{c'}{d'}]`, where `c'` and `d'` are congruent to `c,d \pmod{N}`. The relations of :ref:`thm:mansym` become .. math:: (i,\,c,d) + (-1)^i (k-2-i, \,d, -c) &= 0,\\ (i,\,c,d) \quad + \quad\, (-1)^{k-2} \sum_{j=0}^{k-2-i} (-1)^{j} \binom{k-2-i}{j} (j,\,d,-c-d)&\\ \qquad\qquad + \quad (-1)^{k-2-i} \sum_{j=0}^i (-1)^j \binom{i}{j} (k-2-i+j,\,-c-d,c) &=0,\\ (i,\,c,d) - (-1)^{k-2}(i,\,-c,-d) &= 0. Recall that :ref:`prop:p1bij` gives a similar description for `\Gamma_0(N)`. Modular Symbols with Character ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Suppose `G=\Gamma_1(N).` Define an action of :defn:`diamond-bracket operators` `\dbd{d}` o, with `\gcd(d,N)=1` on Manin symbols as follows: .. math:: \langle d \rangle ([P,(u,v)]) = \left[P,(du, dv)\right]. Let .. math:: \eps : (\Z/N\Z)^* \to \Q(\zeta)^* be a Dirichlet character, where `\zeta` is an `n^{th}` root of unity and `n` is the order of `\eps`. Let :defn:`$\sM_k(N,\eps)$` be the quotient of `\sM_k(\Gamma_1(N);\Z[\zeta])` by the relations (given in terms of Manin symbols) .. math:: \dbd{d}x - \eps(d)x = 0, for all `x\in \sM_k(\Gamma_1(N);\Z[\zeta])`, `d\in (\Z/N\Z)^*`, and by any `\Z`-torsion. Thus `\sM_k(N,\eps)` is a `\Z[\eps]`-module that has no torsion when viewed as a `\Z`-module. Hecke Operators --------------- Suppose `\Gamma` is a subgroup of `\SL_2(\Z)` of level `N` that contains `\Gamma_1(N)`. Just as for modular forms, there is a commutative :defn:`Hecke algebra` `\T=\Z[T_1,T_2, \ldots]`, which is the subring of `\End(\sM_k(\Gamma))` generated by all Hecke operators. Let .. math:: R_p = \left\{\mtwo{1}{r}{0}{p} : r = 0,1,\ldots, p-1 \right\} \union \left\{ \mtwo{p}{0}{0}{1}\right\}, where we omit `\abcd{p}{0}{0}{1}` if `p\mid N`. Then the :defn:`Hecke operator` `T_p` on `\sM_k(\Gamma)` is given by .. math:: T_p(x) = \sum_{g \in R_p} gx. Notice when `p\nmid N` that `T_p` is defined by summing over `p+1` matrices that correspond to the `p+1` subgroups of `\Z\times \Z` of index `p`. This is exactly how we defined `T_p` on modular forms in Definition :ref:`defn:hecke_op`. .. _sec:gendefn: General Definition of Hecke Operators ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Let `\Gamma` be a finite index subgroup of `\SL_2(\Z)` and suppose .. math:: \Delta\subset \GL_2(\Q) is a set such that `\Gamma\Delta = \Delta\Gamma = \Delta` and `\Gamma \backslash \Delta` is finite. For example, `\Delta=\Gamma` satisfies this condition. Also, if `\Gamma=\Gamma_1(N)`, then for any positive integer `n`, the set .. math:: \Delta_n = \left\{ \!\mtwo{a}{b}{c}{d}\in \Mat_2(\Z) \,:\, ad-bc=n, \quad \mtwo{a}{b}{c}{d}\con \mtwo{1}{*}{0}{n}\!\!\!\!\!\!\pmod{N} \right\} also satisfies this condition, as we will now prove. .. lemma:: :label: lem:deltan We have .. math:: \Gamma_1(N)\cdot \Delta_n = \Delta_n \cdot \Gamma_1(N) = \Delta_n and .. math:: \Delta_n = \bigcup_{a,b} \Gamma_1(N) \cdot \sigma_a \mtwo{a}{b}{0}{n/a}, where `\sigma_a \con \abcd{\hfill 1/a}{\,\, 0}{0}{ \hfill a}\pmod{N}`, the union is disjoint and `1\leq a \leq n` with `a\mid n`, `\gcd(a,N)=1`, and `0\leq b < n/a`. In particular, the set of cosets `\Gamma_1(N)\backslash \Delta_n` is finite. .. proof:: (This is Lemma 1 of :cite:`[\S2.3]{merel:1585}`.) If `\gamma\in\Gamma_1(N)` and `\delta\in\Delta_n`, then .. math:: \mtwo{1}{*}{0}{1} \cdot \mtwo{1}{*}{0}{n} \con \mtwo{1}{*}{0}{n} \cdot \mtwo{1}{*}{0}{1} \con \mtwo{1}{*}{0}{n}\pmod{N}. Thus `\Gamma_1(N)\Delta_n \subset \Delta_n`, and since `\Gamma_1(N)` is a group, `\Gamma_1(N)\Delta_n = \Delta_n`; likewise `\Delta_n\Gamma_1(N) = \Delta_n`. For the coset decomposition, we first prove the statement for `N=1`, i.e., for `\Gamma_1(N)=\SL_2(\Z)`. If `A` is an arbitrary element of `\Mat_2(\Z)` with determinant `n`, then using row operators on the left with determinant `1`, i.e., left multiplication by elements of `\SL_2(\Z)`, we can transform `A` into the form `\abcd{a}{b}{0}{n/a}`, with `1\leq a\leq n` and `0\leq b < n`. (Just imagine applying the Euclidean algorithm to the two entries in the first column of `A`. Then `a` is the `\gcd` of the two entries in the first column, and the lower left entry is `0`. Next subtract `n/a` from `b` until `0\leq b < n/a`.) Next suppose `N` is arbitrary. Let `g_1, \ldots, g_r` be such that .. math:: g_1\Gamma_1(N) \union \cdots \union g_r \Gamma_1(N) = \SL_2(\Z) is a disjoint union. If `A \in \Delta_n` is arbitrary, then as we showed above, there is some `\gamma\in\SL_2(\Z)`, so that `\gamma\cdot A = \abcd{a}{b}{0}{n/a}`, with `1\leq a \leq n` and `0\leq b < n/a`, and `a\mid n`. Write `\gamma = g_i \cdot \alpha`, with `\alpha\in\Gamma_1(N)`. Then .. math:: \alpha\cdot A = g_i^{-1} \cdot \mtwo{a}{b}{0}{n/a} \con \mtwo{1}{*}{0}{n}\pmod{N}. It follows that .. math:: g_i^{-1} \con \mtwo{1}{*}{0}{n} \cdot \mtwo{a}{b}{0}{n/a}^{-1} \con \mtwo{1/a}{*}{0}{a}\pmod{N}. Since `\abcd{1}{1}{0}{1}\in \Gamma_1(N)` and `\gcd(a,N)=1`, there is `\gamma'\in\Gamma_1(N)` such that .. math:: \gamma' g_i^{-1} \con \mtwo{1/a}{0}{0}{a}\pmod{N}. We may then choose `\sigma_a = \gamma' g_i^{-1}`. Thus every `A\in \Delta_n` is of the form `\gamma \sigma_a \abcd{a}{b}{0}{n/a}`, with `\gamma\in\Gamma_1(N)` and `a,b` suitably bounded. This proves the second claim. Let any element `\delta=\abcd{a}{b}{c}{d}\in\GL_2(\Q)` act on the left on modular symbols `\M_k\tensor\Q` by .. math:: \delta(P\{\alpha,\beta\}) = P(dX-bY,-cX+aY) \{\delta(\alpha),\delta(\beta)\}. (Until now we had only defined an action of `\SL_2(\Z)` on modular symbols.) For `g=\abcd{a}{b}{c}{d}\in \GL_2(\Q)`, let .. math:: :label: eqn:gtilde \tilde{g} = \mtwo{\hfill{}d}{-b}{-c}{\hfill{}a} = \det(g)\cdot g^{-1}. Note that `\tilde{\tilde{g}} = g`. Also, `\delta P(X,Y)=(P\circ \tilde{g})(X,Y)`, where we set .. math:: \tilde{g}(X,Y) = (dX-bY,-cX+aY). Suppose `\Gamma` and `\Delta` are as above. Fix a finite set `R` of representatives for `\Gamma\backslash \Delta`. Let .. math:: T_{\Delta} : \M_k(\Gamma) \to \M_k(\Gamma) be the linear map .. math:: T_{\Delta}(x) = \sum_{\delta\in R} \delta x. This map is well defined because if `\gamma\in\Gamma` and `x\in \M_k(\Gamma)`, then .. math:: \sum_{\delta\in R} \delta \gamma x = \sum_{\text{certain $\delta'$}} \gamma \delta' x = \sum_{\text{certain $\delta'$}} \delta' x =\sum_{\delta\in R} \delta x, where we have used that `\Delta\Gamma = \Gamma\Delta`, and `\Gamma` acts trivially on `\M_k(\Gamma)`. Let `\Gamma=\Gamma_1(N)` and `\Delta=\Delta_n`. Then the `n^{th}` Hecke operator `T_n` is `T_{\Delta_n}`, and by :ref:`lem:deltan`, .. math:: T_n(x) = \sum_{a,b} \sigma_a \mtwo{a}{b}{0}{n/a} \cdot x, where `a,b` are as in :ref:`lem:deltan`. Given this definition, we can compute the Hecke operators on `M_k(\Gamma_1(N))` as follows. Write `x` as a modular symbol `P\{\alpha,\beta\}`, compute `T_n(x)` as a modular symbol, and then convert to Manin symbols using continued fractions expansions. This is extremely inefficient; fortunately Lo\"{i}c Merel (following :cite:`mazur:symboles`) found a much better way, which we now describe (see :cite:`merel:1585`). .. _sec:hecke_on_manin: Hecke Operators on Manin Symbols ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ If `S` is a subset of `\GL_2(\Q)`, let .. math:: \tilde{S} = \{\tilde{g} : g \in S\}, where `\tilde{g}` is as in :eq:`eqn:gtilde`. Also, for any ring `R` and any subset `S\subset \Mat_2(\Z)`, let `R[S]` denote the free `R`-module with basis the elements of `S`, so the elements of `R[S]` are the finite `R`-linear combinations of the elements of `S`. One of the main theorems of :cite:`merel:1585` is that for any `\Gamma,\Delta` satisfying the condition at the beginning of Section :ref:`sec:gendefn`, if we can find `\sum u_M M \in \C[\Mat_2(\Z)]` and a map .. math:: \phi: \tilde{\Delta} \SL_2(\Z) \to \SL_2(\Z) that satisfies certain conditions, then for any Manin symbol `[P,g] \in \M_k(\Gamma)`, we have .. math:: T_\Delta([P,g]) = \sum_{gM\in \tilde{\Delta}\SL_2(\Z)\text{ with }M\in\SL_2(\Z)} u_M [\tilde{M}\cdot P,\,\, \phi(gM)]. The paper :cite:`merel:1585` contains many examples of `\phi` and `\sum u_M M \in \C[\Mat_2(\Z)]` that satisfy all of the conditions. When `\Gamma=\Gamma_1(N)`, the complicated list of conditions becomes simpler. Let :defn:`$\Mat_2(\Z)_n$` be the set of `2\times 2` matrices with determinant `n`. An element .. math:: h = \sum u_M [M] \in \C[\Mat_2(\Z)_n] :defn:`satisfies condition $C_n$` if for every `K\in \Mat_2(\Z)_n / \SL_2(\Z)`, we have that .. math:: :label: eqn:cn \sum_{M \in K} u_M([M\infty] - [M 0 ]) = [\infty] - [0] \in \C[P^1(\Q)]. If `h` satisfies condition `C_n`, then for any Manin symbol `[P,g] \in M_k(\Gamma_1(N))`, Merel proves that .. math:: :label: eqn:tnmanin T_n([P,(u,v)]) = \sum_{M} u_M [P(aX+bY, \, cX+dY), (u,v)M]. Here `(u,v)\in (\Z/N\Z)^2` corresponds via :ref:`prop:gamma1cosets` to a coset of `\Gamma_1(N)` in `\SL_2(\Z)`, and if `(u',v')=(u,v)M \in (\Z/N\Z)^2` and `\gcd(u',v',N)\neq 1`, then we omit the corresponding summand. For example, we will now check directly that the element .. math:: h_2 = \left[\mtwo{2}{0}{0}{1}\right] + \left[\mtwo{1}{0}{0}{2}\right] + \left[\mtwo{2}{1}{0}{1}\right] + \left[\mtwo{1}{0}{1}{2}\right] satisfies condition `C_2`. We have, as in the proof of :ref:`lem:deltan` (but using elementary column operations), that .. math:: \Mat_2(\Z)_2/\SL_2(\Z) &= \left\{ \mtwo{a}{0}{b}{2/a} \SL_2(\Z) : a=1,2\text{ and }0\leq b < 2/a \right\} \\ &\hspace{-2ex}= \left\{ \mtwo{1}{0}{0}{2} \SL_2(\Z),\,\,\,\, \mtwo{1}{0}{1}{2} \SL_2(\Z),\,\,\,\, \mtwo{2}{0}{0}{1} \SL_2(\Z) \right\}. To verify condition `C_2`, we consider in turn each of the three elements of `\Mat_2(\Z)_2/\SL_2(\Z)` and check that :eq:`eqn:cn` holds. We have that .. math:: \mtwo{1}{0}{0}{2} \in \mtwo{1}{0}{0}{2} \SL_2(\Z), .. math:: \mtwo{2}{1}{0}{1}, \mtwo{1}{0}{1}{2} \in \mtwo{1}{0}{1}{2} \SL_2(\Z), and .. math:: \mtwo{2}{0}{0}{1}\in \mtwo{2}{0}{0}{1} \SL_2(\Z). Thus if `K = \abcd{1}{0}{0}{2}\SL_2(\Z)`, the left sum of :eq:`eqn:cn` is `[\abcd{1}{0}{0}{2}(\infty)] - [\abcd{1}{0}{0}{2}(0)] = [\infty]-[0]`, as required. If `K=\abcd{1}{0}{1}{2} \SL_2(\Z)`, then the left side of :eq:`eqn:cn` is .. math:: [\abcd{2}{1}{0}{1}(\infty)] &- [\abcd{2}{1}{0}{1}(0)] + [\abcd{1}{0}{1}{2}(\infty)] - [\abcd{1}{0}{1}{2}(0)] \\ &= [\infty] - [1] + [1] - [0] = [\infty] - [0]. Finally, for `K = \abcd{2}{0}{0}{1}\SL_2(\Z)` we also have `[\abcd{2}{0}{0}{1}(\infty)] - [\abcd{2}{0}{0}{1}(0)] = [\infty]-[0]`, as required. Thus by :eq:`eqn:tnmanin` we can compute `T_2` on *any* Manin symbol, by summing over the action of the four matrices `\abcd{2}{0}{0}{1}, \abcd{1}{0}{0}{2}, \abcd{2}{1}{0}{1}, \abcd{1}{0}{1}{2}`. .. proposition:: Merel :label: prop:heilbronn The element .. math:: \sum_{\substack{a>b\geq 0\\d>c\geq 0\\ad-bc=n}} \left[\mtwo{a}{b}{c}{d}\right] \in \Z[\Mat_2(\Z)_n] satisfies condition `C_n`. Merel's two-page proof of :ref:`prop:heilbronn` is fairly elementary. .. remark:: .. index:: Heilbronn matrices In :cite:`[\S2.4]{cremona:algs}`, Cremona discusses the work of Merel and Mazur on Heilbronn matrices in the special cases `\Gamma=\Gamma_0(N)` and weight `2`. He gives a simple proof that the action of `T_p` on Manin symbols can be computed by summing the action of some set `R_p` of matrices of determinant `p`. He then describes the set `R_p` and gives an efficient continued fractions algorithm for computing it (but he does not prove that his `R_p` satisfy Merel's hypothesis). Remarks on Complexity ~~~~~~~~~~~~~~~~~~~~~ Merel gives another family `\mathcal{S}_n` of matrices that satisfy condition `C_n`, and he proves that as `n\to \infty`, .. math:: \#\mathcal{S}_n \sim \frac{12 \log(2)}{\pi^2} \cdot \sigma_1(n)\log(n), where `\sigma_1(n)` is the sum of the divisors of `n`. Thus for a fixed space `\sM_k(\Gamma)` of modular symbols, one can compute `T_n` using `O(\sigma_1(n)\log(n))` arithmetic operations. Note that we have fixed `\sM_k(\Gamma)`, so we ignore the linear algebra involved in computation of a presentation; also, adding elements takes a bounded number of field operations when the space is fixed. Thus, using Manin symbols the complexity of computing `T_p`, for `p` prime, is `O((p+1)\log(p))` field operations, which is *exponential* in the number of digits of `p`. .. _sec:basmaji: Basmaji's Trick ~~~~~~~~~~~~~~~ There is a trick of Basmaji (see :cite:`basmaji:thesis`) for computing a matrix of `T_n` on `\sM_k(\Gamma)`, when `n` is very large, and it is more efficient than one might naively expect. Basmaji's trick does not improve the big-oh complexity for a fixed space, but it does improve the complexity by a constant factor of the dimension of `\sM_k(\Gamma;\Q)`. Suppose we are interested in computing the matrix for `T_n` for some massive integer `n` and that `\sM_k(\Gamma;\Q)` has large dimension. The trick is as follows. Choose a list .. math:: x_1 =[P_1,g_1],\ldots,x_r = [P_r,g_r] \in V = \sM_k(\Gamma;\Q) of Manin symbols such that the map `\Psi:\T \to V^r` given by .. math:: t \mapsto (t x_1, \ldots, t x_r) is injective. In practice, it is often possible to do this with `r` "very small". Also, we emphasize that `V^r` is a `\Q`-vector space of dimension `r\cdot \dim(V)`. .. index:: Heilbronn matrices Next find Hecke operators `T_i`, with `i` small, whose images form a basis for the image of `\Psi`. Now with the above data precomputed, which only required working with Hecke operators `T_i` for small `i`, we are ready to compute `T_n` with `n` huge. Compute `y_i = T_n(x_i)`, for each `i=1,\ldots, r`, which we can compute using Heilbronn matrices since each `x_i=[P_i,g_i]` is a Manin symbol. We thus obtain `\Psi(T_n) \in V^r.` Since we have precomputed Hecke operators `T_j` such that `\Psi(T_j)` generate `V^r`, we can find `a_j` such that `\sum a_j \Psi(T_j) = \Psi(T_n)`. Then since `\Psi` is injective, we have `T_n = \sum a_j T_j`, which gives the full matrix of `T_n` on `M_k(\Gamma;\Q)`. .. _sec:cuspmodsym: Cuspidal Modular Symbols ------------------------ Let `\sB` be the free abelian group on symbols `\{\alpha\}`, for `\alpha\in\P^1(\Q)`, and set .. math:: \sB_k = \Z[X,Y]_{k-2}\tensor\sB. Define a :defn:`left action of $\SL_2(\Z)$` on `\sB_k` by .. math:: g (P \{\alpha\}) = (gP) \{g(\alpha)\}, for `g\in \SL_2(\Z)`. For any finite index subgroup `\Gamma\subset \SL_2(\Z)`, let `\sB_k(\Gamma)` be the quotient of `\sB_k` by the relations `x- gx` for all `g\in \Gamma` and by any torsion. Thus `\sB_k(\Gamma)` is a torsion-free abelian group. The :defn:`boundary map` is the map .. math:: b:\sM_k(\Gamma) \to \sB_k(\Gamma) given by extending the map .. math:: b(P\{\alpha,\beta\}) = P\{\beta\} - P\{\alpha\} linearly. The space :defn:`$\sS_k(\Gamma)$` of :defn:`cuspidal modular symbols` is the kernel .. index:: pair: cusp forms; for `\Gamma` .. math:: \sS_k(\Gamma) = \ker(\sM_k(\Gamma) \to \sB_k(\Gamma)), so we have an exact sequence .. math:: 0 \to \sS_k(\Gamma) \to \sM_k(\Gamma) \to \sB_k(\Gamma). One can prove that when `k>2`, this sequence is exact on the right. Next we give a presentation of `\sB_k(\Gamma)` in terms of "boundary Manin symbols". .. _sec:computeboundary: Boundary Manin Symbols ~~~~~~~~~~~~~~~~~~~~~~ .. index:: pair: Manin symbols; and cuspidal subspace pair: Manin symbols; and boundary space pair: cuspidal modular symbols; and Manin symbols pair: boundary modular symbols; and Manin symbols We give an explicit description of the boundary map in terms of Manin symbols for `\Gamma=\Gamma_1(N)`, then describe an efficient way to compute the boundary map. Let `\cR` be the equivalence relation on `\Gamma\backslash\Q^2` given by .. math:: [\Gamma\smallvtwo{\lambda u}{\lambda v}] \sim \sign(\lambda)^k[\Gamma\smallvtwo{u}{v}], for any `\lambda\in\Q^*`. Denote by `B_k(\Gamma)` the finite-dimensional `\Q`-vector space with basis the equivalence classes `(\Gamma\backslash\Q^2)/\cR`. The following two propositions are proved in :cite:`merel:1585`. .. proposition:: The map .. math:: \mu:\sB_k(\Gamma)\ra B_k(\Gamma), \qquad P\left\{\frac{u}{v}\right\}\mapsto P(u,v)\left[\Gamma\vtwo{u}{v}\right] is well defined and injective. Here `u` and `v` are assumed coprime. Thus the kernel of `\delta:\sS_k(\Gamma)\ra \sB_k(\Gamma)` is the same as the kernel of `\mu\circ \delta`. .. proposition:: :label: prop:boundary Let `P\in V_{k-2}` and `g=\abcd{a}{b}{c}{d}\in\sltwoz`. We have .. math:: \mu\circ\delta([P,(c,d)]) = P(1,0)[\Gamma\smallvtwo{a}{c}] -P(0,1)[\Gamma\smallvtwo{b}{d}]. .. index:: single: boundary map pair: cusps; and boundary map We next describe how to explicitly compute `\mu\circ \delta:\sM_k(N,\eps)\ra B_k(N,\eps)` by generalizing the algorithm of :cite:`[\S2.2]{cremona:algs}`. To compute the image of `[P,(c,d)]`, with `g=\abcd{a}{b}{c}{d}\in\sltwoz`, we must compute the class of `[\smallvtwo{a}{c}]` and of `[\smallvtwo{b}{d}]`. Instead of finding a canonical form for cusps, we use a quick test for equivalence modulo scalars. In the following algorithm, by the `i^{th}` symbol we mean the `i^{th}` basis vector for a basis of `B_k(N,\eps)`. This basis is constructed as the algorithm is called successively. We first give the algorithm, and then prove the facts used by the algorithm in testing equivalence. .. algorithm:: Cusp Representation :label: alg:cusplist Given a boundary Manin symbol `[\smallvtwo{u}{v}],` this algorithm outputs an integer `i` and a scalar `\alp` such that `[\smallvtwo{u}{v}]` is equivalent to `\alp` times the `i^{th}` symbol found so far. (We call this algorithm repeatedly and maintain a running list of cusps seen so far.) 1. Use :ref:`prop:cusp1g0` to check whether or not `[\smallvtwo{u}{v}]` is equivalent, modulo scalars, to any cusp found. If so, return the representative, its index, and the scalar. If not, record `\smallvtwo{u}{v}` in the representative list. 2. Using :ref:`prop:cuspdies`, check whether or not `[\smallvtwo{u}{v}]` is forced to equal `0` by the relations. If it does not equal `0`, return its position in the list and the scalar `1`. If it equals `0`, return the scalar `0` and the position `1`; keep `\smallvtwo{u}{v}` in the list, and record that it is equivalent to `0`. The case considered in Cremona's book :cite:`cremona:algs` only involve the trivial character, so no cusp classes are forced to vanish. Cremona gives the following two criteria for equivalence. .. proposition:: Cremona :label: prop:cusp1 Consider `\smallvtwo{u_i}{v_i}`, `i=1,2`, with `u_i,v_i` integers such that `\gcd(u_i,v_i)=1` for each `i`. 1. There exists `g\in\Gamma_0(N)` such that `g\smallvtwo{u_1}{v_1}=\smallvtwo{u_2}{v_2}` if and only if .. math:: s_1 v_2 \con s_2 v_1 \pmod{\gcd(v_1 v_2,N)},\, \text{ where $s_j$ satisfies $u_j s_j\con 1\!\!\!\pmod{v_j}$}. 2. There exists `g\in\Gamma_1(N)` such that `g\smallvtwo{u_1}{v_1}=\smallvtwo{u_2}{v_2}` if and only if .. math:: v_2 \con v_1 \pmod{N}\text{ and } u_2 \con u_1 \pmod{\gcd(v_1,N)}. .. proof:: The first statement is :cite:`[Prop.~2.2.3]{cremona:algs}`, and the second is :cite:`[Lem.~3.2]{cremona:gammaone}`. .. algorithm:: Explicit Cusp Equivalence :label: alg:cusp1 Suppose `\smallvtwo{u_1}{v_1}` and `\smallvtwo{u_2}{v_2}` are equivalent modulo `\Gamma_0(N)`. This algorithm computes a matrix `g\in\Gamma_0(N)` such that `g\smallvtwo{u_1}{v_1}=\smallvtwo{u_2}{v_2}`. 1. Let `s_1, s_2, r_1, r_2` be solutions to `s_1 u_1 -r_1 v_1 =1` and `s_2 u_2 -r_2 v_2 =1`. 2. Find integers `x_0` and `y_0` such that `x_0v_1v_2+y_0N=1`. 3. Let `x=-x_0(s_1v_2-s_2v_1)/(v_1v_2,N)` and `s_1' = s_1 + xv_1`. 4. Output `g=\abcd{u_2}{r_2}{v_2}{s_2} \cdot \abcd{u_1}{r_1}{v_1}{s_1'}^{-1}`, which sends `\smallvtwo{u_1}{v_1}` to `\smallvtwo{u_2}{v_2}`. .. proof:: See the proof of :cite:`[Prop. 8.13]{cremona:algs}`. The `\eps` relations can make the situation more complicated, since it is possible that `\eps(\alp)\neq \eps(\beta)` but .. math:: \eps(\alp)\left[\vtwo{u}{v}\right] =\left[\gamma_\alp \vtwo{u}{v}\right]= \left[\gamma_\beta \vtwo{u}{v}\right]=\eps(\beta)\left[\vtwo{u}{v}\right]. One way out of this difficulty is to construct the cusp classes for `\Gamma_1(N)`, and then quotient out by the additional `\eps` relations using Gaussian elimination. This is far too inefficient to be useful in practice because the number of `\Gamma_1(N)` cusp classes can be unreasonably large. Instead, we give a quick test to determine whether or not a cusp vanishes modulo the `\eps`-relations. .. lemma:: :label: lem:canlift Suppose `\alp` and `\alp'` are integers such that `\gcd(\alp,\alp',N)=1`. Then there exist integers `\beta` and `\beta'`, congruent to `\alp` and `\alp'` modulo `N`, respectively, such that `\gcd(\beta,\beta')=1`. .. proof:: By :ref:`ex:surjred` the map `\SL_2(\Z)\ra\SL_2(\Z/N\Z)` is surjective. By the Euclidean algorithm, there exist integers `x`, `y` and `z` such that `x\alp + y\alp' + zN = 1`. Consider the matrix `\abcd{y}{-x}{\alp}{\hfill\alp'}\in \SL_2(\Z/N\Z)` and take `\beta`, `\beta'` to be the bottom row of a lift of this matrix to `\SL_2(\Z)`. .. proposition:: :label: prop:cuspdies .. index:: pair: cusps; criterion for vanishing pair: Dirichlet character; and cusps Let `N` be a positive integer and `\eps` a Dirichlet character of modulus `N`. Suppose `\smallvtwo{u}{v}` is a cusp with `u` and `v` coprime. Then `\smallvtwo{u}{v}` vanishes modulo the relations .. math:: \left[\gamma\smallvtwo{u}{v}\right]= \eps(\gamma)\left[\smallvtwo{u}{v}\right],\qquad \text{all $\gamma\in\Gamma_0(N)$}, if and only if there exists `\alp\in(\Z/N\Z)^*`, with `\eps(\alp)\neq 1`, such that .. math:: v &\con \alp v \pmod{N},\\ u &\con \alp u \pmod{\gcd(v,N)}. .. proof:: First suppose such an `\alp` exists. By :ref:`lem:canlift` there exists `\beta, \beta'\in\Z` lifting `\alp,\alp^{-1}` such that `\gcd(\beta,\beta')=1`. The cusp `\smallvtwo{\beta u}{\beta' v}` has coprime coordinates so, by :ref:`prop:cusp1` and our congruence conditions on `\alp`, the cusps `\smallvtwo{\beta{}u}{\beta'{}v}` and `\smallvtwo{u}{v}` are equivalent by an element of `\Gamma_1(N)`. This implies that `\left[\smallvtwo{\beta{}u}{\beta'{}v}\right] =\left[\smallvtwo{u}{v}\right]`. Since `\left[\smallvtwo{\beta{}u}{\beta'{}v}\right] = \eps(\alp)\left[\smallvtwo{u}{v}\right]` and `\eps(\alp)\neq 1`, we have `\left[\smallvtwo{u}{v}\right]=0`. Conversely, suppose `\left[\smallvtwo{u}{v}\right]=0`. Because all relations are two-term relations and the `\Gamma_1(N)`-relations identify `\Gamma_1(N)`-orbits, there must exists `\alp` and `\beta` with .. math:: \left[\gamma_\alp \vtwo{u}{v}\right] =\left[\gamma_\beta \vtwo{u}{v}\right] \qquad\text{ and }\eps(\alp)\ne \eps(\beta). Indeed, if this did not occur, then we could mod out by the `\eps` relations by writing each `\left[\gamma_\alp \smallvtwo{u}{v} \right]` in terms of `\left[\smallvtwo{u}{v}\right]`, and there would be no further relations left to kill `\left[\smallvtwo{u}{v}\right]`. Next observe that .. math:: \left[\gamma_{\beta^{-1}\alp} \vtwo{u}{v}\right] &= \left[\gamma_{\beta^{-1}}\gamma_\alp \vtwo{u}{v}\right]\\ &= \eps(\beta^{-1})\left[\gamma_\alp \vtwo{u}{v}\right] = \eps(\beta^{-1})\left[\gamma_\beta \vtwo{u}{v}\right] = \left[\vtwo{u}{v}\right]. Applying :ref:`prop:cusp1` and noting that `\eps(\beta^{-1}\alp)\neq 1` shows that `\beta^{-1}\alp` satisfies the properties of the " `\alp` " in the statement of the proposition. We enumerate the possible `\alp` appearing in :ref:`prop:cuspdies` as follows. Let `g=(v,N)` and list the `\alp=v\cdot\frac{N}{g}\cdot{}a+1`, for `a=0,\ldots,g-1`, such that `\eps(\alp)\neq 0`. .. _sec:pairing: Pairing Modular Symbols and Modular Forms ----------------------------------------- In this section we define a pairing between modular symbols and modular forms that the Hecke operators respect. We also define an involution on modular symbols and study its relationship with the pairing. This pairing is crucial in much that follows, because it gives rise to period maps from modular symbols to certain complex vector spaces. Fix an integer weight `k\geq 2` and a finite index subgroup `\Gamma` of `\SL_2(\Z)`. Let `M_k(\Gamma)` denote the space of holomorphic modular forms of weight `k` for `\Gamma`, and let `S_k(\Gamma)` denote its cuspidal subspace. Following :cite:`[\S1.5]{merel:1585}`, let .. math:: :label: eqn:sbar \Sbar_k(\Gamma) = \{\overline{f} : f \in S_k(\Gamma)\} denote the space of :defn:`antiholomorphic` cusp forms. Here `\overline{f}` is the function on `\h^*` given by `\overline{f}(z) = \overline{f(z)}`. Define a pairing .. math:: :label: eqn:intpairing (S_k(\Gamma) \oplus \Sbar_k(\Gamma)) \times \sM_k(\Gamma) \to \C by letting .. math:: \langle (f_1, f_2), P\{\alpha,\beta\} \rangle = \int_{\alpha}^{\beta} f_1(z) P(z,1)\dz + \int_{\alpha}^{\beta} f_2(z) P(\zbar,1) \dzbar and extending linearly. Here the integral is a complex path integral along a simple path from `\alpha` to `\beta` in `\h` (so, e.g., write `z(t)=x(t) + iy(t)`, where `(x(t),y(t))` traces out the path and consider two real integrals). .. proposition:: :label: prop:pairwd The integration pairing is well defined, i.e., if we replace `P\{\alpha,\beta\}` by an equivalent modular symbol (equivalent modulo the left action of `\Gamma`), then the integral is the same. .. proof:: This follows from the change of variables formulas for integration and the fact that `f_1 \in S_k(\Gamma)` and `f_2 \in \Sbar_k(\Gamma)`. For example, if `k=2`, `g\in \Gamma` and `f\in S_k(\Gamma)`, then .. math:: \langle f, g\{\alpha,\beta\}\rangle &= \langle f, \{g(\alpha),g(\beta)\}\rangle \\ &= \int_{g(\alpha)}^{g(\beta)} f(z)dz \\ &= \int_{\alpha}^{\beta} f(g(z))d g(z) \\ &= \int_{\alpha}^{\beta} f(z)dz = \langle f, \{\alpha, \beta\}\rangle, where `f(g(z))d g(z) = f(z) dz` because `f` is a weight `2` modular form. For the case of arbitrary weight `k>2`, see :ref:`ex:pairingwd`. The integration pairing is very relevant to the study of special values of `L`-functions. The `L`-function of a cusp form `f=\sum a_n q^n \in S_k(\Gamma_1(N))` is .. math:: :label: eqn:lfs L(f,s) &= (2\pi)^{s}\Gamma(s)^{-1} \int_{0}^{\infty} f(i t)t^s \frac{dt}{t}\\ &=\sum_{n=1}^{\infty} \frac{a_n}{n^s} \qquad \text{ for }\Re(s)\gg 0. The equality of the integral and the Dirichlet series follows by switching the order of summation and integration, which is justified using standard estimates on `|a_n|` (see, e.g., :cite:`[Section~VIII.5]{knapp:elliptic}`). For each integer `j` with `1 \leq j \leq k-1`, we have, setting `s=j` and making the change of variables `t\mapsto -it` in :eq:`eqn:lfs`, that .. math:: :label: eqn:lfunc_ms L(f,j) = \frac{(-2\pi i)^{j}}{(j-1)!} \cdot \left\langle f,\,\, X^{j-1}Y^{k-2-(j-1)} \{0,\infty\} \right\rangle. The integers `j` as above are called :defn:`critical integers`. When `f` is an eigenform, they have deep conjectural significance (see :cite:`bloch-kato, scholl:motivesinvent`). One can approximate `L(f,j)` to any desired precision by computing the above pairing explicitly using the method described in Chapter :ref:`ch:periods`. Alternatively, :cite:`dokchitser:lfun` contains methods for computing special values of very general `L`-functions, which can be used for approximating `L(f,s)` for arbitrary `s`, in addition to just the critical integers `1,\ldots,k-1`. .. theorem:: Shokoruv :label: thm:shokoruvpairing The pairing .. math:: \langle \cdot\, , \, \cdot \rangle: (S_k(\Gamma) \oplus \Sbar_k(\Gamma)) \times \sS_k(\Gamma,\C) \to \C is a nondegenerate pairing of complex vector spaces. .. proof:: This is :cite:`[Thm.~0.2]{shokurov:kuga}` and :cite:`[\S1.5]{merel:1585}`. .. corollary:: We have .. math:: \dim_\C\sS_k(\Gamma,\C) = 2\dim_\C S_2(\Gamma). The pairing is also compatible with Hecke operators. Before proving this, we define an :defn:`action of Hecke operators` on `M_k(\Gamma_1(N))` and on `\Sbar_k(\Gamma_1(N))`. The definition is similar to the one we gave in Section :ref:`sec:hecke_one` for modular forms of level `1`. For a positive integer `n`, let `R_n` be a set of coset representatives for `\Gamma_1(N)\backslash \Delta_n` from :ref:`lem:deltan`. For any `\gamma=\abcd{a}{b}{c}{d} \in \GL_2(\Q)` and `f\in M_k(\Gamma_1(N))` set .. math:: f^{[\gamma]_k} = \det(\gamma)^{k-1} (cz+d)^{-k} f(\gamma(z)). Also, for `f\in \Sbar_k(\Gamma_1(N))`, set .. math:: f^{[\gamma]_k'} = \det(\gamma)^{k-1} (c\zbar+d)^{-k} f(\gamma(z)). Then for `f\in M_k(\Gamma_1(N))`, .. math:: T_n(f) = \sum_{\gamma\in R_n} f^{[\gamma]_k} and for `f\in \Sbar_k(\Gamma_1(N))`, .. math:: T_n(f) = \sum_{\gamma\in R_n} f^{[\gamma]_k'}. This agrees with the definition from Section :ref:`sec:hecke_one` when `N=1`. .. remark:: If `\Gamma` is an arbitrary finite index subgroup of `\SL_2(\Z)`, then we can define operators `T_\Delta` on `M_k(\Gamma)` for any `\Delta` with `\Delta\Gamma=\Gamma\Delta = \Delta` and `\Gamma\backslash \Delta` finite. For concreteness we do not do the general case here or in the theorem below, but the proof is exactly the same (see :cite:`[\S1.5]{merel:1585}`). Finally we prove the promised Hecke compatibility of the pairing. This proof should convince you that the definition of modular symbols is sensible, in that they are natural objects to integrate against modular forms. .. theorem:: :label: thm:tequivar If .. math:: f=(f_1,f_2)\in S_k(\Gamma_1(N)) \oplus \Sbar_k(\Gamma_1(N)) and `x \in \sM_k(\Gamma_1(N))`, then for any `n`, .. math:: \langle T_n(f), x \rangle = \langle f, T_n(x) \rangle. .. proof:: We follow :cite:`[\S2.1]{merel:1585}` (but with more details) and will only prove the theorem when `f=f_1\in S_k(\Gamma_1(N))`, the proof in the general case being the same. Let `\alpha, \beta \in \P^1(\Q)`, `P\in \Z[X,Y]_{k-2}`, and for `g=\abcd{a}{b}{c}{d}\in\GL_2(\Q)`, set .. math:: j(g,z) = cz+d. Let `n` be any positive integer, and let `R_n` be a set of coset representatives for `\Gamma_1(N)\backslash \Delta_n` from :ref:`lem:deltan`. We have .. math:: \langle T_n(f), P\{\alpha,\beta\}\rangle &= \int_{\alpha}^{\beta} T_n(f) P(z,1) \dz\\ &= \sum_{\delta\in R} \int_{\alpha}^{\beta} \det(\delta)^{k-1} f(\delta(z)) j(\delta,z)^{-k} P(z,1) \dz. Now for each summand corresponding to the `\delta\in R`, make the change of variables `u=\delta z`. Thus we make `\# R` change of variables. Also, we will use the notation .. math:: \tilde{g} = \mtwo{\hfill{}d}{-b}{-c}{\hfill{}a} = \det(g)\cdot g^{-1} for `g\in\GL_2(\Q)`. We have .. math:: \langle T_n(f), P\{\alpha,\beta\}\rangle &=\\ &\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \sum_{\delta \in R}\int_{\delta(\alpha)}^{\delta(\beta)} \det(\delta)^{k-1} f(u) j(\delta, \delta^{-1}(u))^{-k} P(\delta^{-1}(u), 1) d(\delta^{-1}(u)). We have `\delta^{-1}(u) = \tilde{\delta}(u)`, since a linear fractional transformation is unchanged by a nonzero rescaling of a matrix that induces it. Thus by the quotient rule, using that `\tilde{\delta}` has determinant `\det(\delta)`, we see that .. math:: d(\delta^{-1}(u)) = d(\tilde{\delta}(u)) = \frac{\det(\delta) du}{j(\tilde{\delta},u)^2}. We next show that .. math:: :label: eqn:bigstuff j(\delta, \delta^{-1}(u))^{-k} P(\delta^{-1}(u),1) = j(\tilde{\delta},u)^k \det(\delta)^{-k} P(\tilde{\delta}(u),1). From the definitions, and again using that `\delta^{-1}(u)=\tilde{\delta}(u)`, we see that .. math:: j(\delta, \delta^{-1}(u)) = \frac{\det(\delta)}{j(\tilde{\delta}, u)}, which proves that :eq:`eqn:bigstuff` holds. Thus .. math:: \left\langle T_n(f), P\{\alpha,\beta\}\right\rangle &= \\ &\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \sum_{\delta \in R}\int_{\delta(\alpha)}^{\delta(\beta)} \det(\delta)^{k-1} f(u) j(\tilde{\delta},u)^{k} \det(\delta)^{-k} P(\tilde{\delta}(u), 1) \frac{\det(\delta) du} {j(\tilde{\delta}, u)^2}. Next we use that .. math:: (\delta P)(u,1) = j(\tilde{\delta}, u)^{k-2} P(\tilde{\delta}(u), 1). To see this, note that `P(X,Y) = P(X/Y, 1)\cdot Y^{k-2}`. Using this we see that .. math:: (\delta P)(X,Y) &= (P\circ \tilde{\delta})(X,Y)\\ &= P\left(\tilde{\delta}\left(\frac{X}{Y}\right),1\right) \left(-c \cdot \frac{X}{Y} + a\right)^{k-2} \cdot Y^{k-2}. Now substituting `(u,1)` for `(X,1)`, we see that .. math:: (\delta P)(u,1) = P(\tilde{\delta}(u), 1) \cdot (-c u + a)^{k-2}, as required. Thus finally .. math:: \langle T_n(f), P\{\alpha,\beta\}\rangle &= \sum_{\delta \in R}\int_{\delta(\alpha)}^{\delta(\beta)} f(u) j(\tilde{\delta},u)^{k-2} P(\tilde{\delta}(u), 1) du\\ &= \sum_{\delta \in R} \int_{\delta(\alpha)}^{\delta(\beta)} f(u) \cdot ((\delta P)(u,1)) du\\ &= \langle f, \, T_n(P\{\alpha,\beta\})\rangle. Suppose that `\Gamma` is a finite index subgroup of `\SL_2(\Z)` such that if `\eta = \abcd{-1}{0}{\hfill 0}{1}`, then .. math:: \eta \Gamma \eta = \Gamma. For example, `\Gamma=\Gamma_1(N)` satisfies this condition. There is an involution `\iota^*` on `\sM_k(\Gamma)` given by .. math:: :label: eqn:star \iota^*(P(X,Y)\{\alpha,\beta\}) = -P(X,-Y)\{-\alpha,-\beta\}, which we call the :defn:`star involution`. On Manin symbols, `\iota^*` is .. math:: :label: eqn:iota \iota^*[P,(u,v)] = -[P(-X,Y), (-u,v)]. Let `\sS_k(\Gamma)^+` be the `+1` eigenspace for `\iota^*` on `\sS_k(\Gamma)`, and let `\sS_k(\Gamma)^-` be the `-1` eigenspace. There is also a map `\iota` on modular forms, which is adjoint to `\iota^*`. .. remark:: Notice the minus sign in front of `-P(X,-Y)\{-\alpha,-\beta\}` in :eq:`eqn:star`. This sign is missing in :cite:`cremona:algs`, which is a potential source of confusion (this is not a mistake, but a different choice of convention). We now state the final result about the pairing, which explains how modular symbols and modular forms are related. .. theorem:: :label: thm:modsymformpairing The integration pairing `\langle \cdot\, , \, \cdot \rangle` induces nondegenerate Hecke compatible bilinear pairings .. math:: \sS_k(\Gamma)^+ \times S_k(\Gamma) \to \C \qquad \text{and}\qquad \sS_k(\Gamma)^- \times \Sbar_k(\Gamma) \to \C. .. remark:: We make some remarks about computing the boundary map of Section :ref:`sec:computeboundary` when working in the `\pm 1` quotient. Let `s` be a sign, either `+1` or `-1`. To compute `\sS_k(N,\eps)_s`, it is necessary to replace `B_k(N,\eps)` by its quotient modulo the additional relations `\left[ \smallvtwo{-u}{\hfill v}\right] = s \left[\smallvtwo{u}{v}\right]` for all cusps `\smallvtwo{u}{v}`. :ref:`alg:cusplist` can be modified to deal with this situation as follows. Given a cusp `x=\smallvtwo{u}{v}`, proceed as in :ref:`alg:cusplist` and check if either `\smallvtwo{u}{v}` or `\smallvtwo{-u}{\hfill v}` is equivalent (modulo scalars) to any cusp seen so far. If not, use the following trick to determine whether the `\eps` and `s`-relations kill the class of `\smallvtwo{u}{v}`: use the unmodified :ref:`alg:cusplist` to compute the scalars `\alp_1, \alp_2` and indices `i_1`, `i_2` associated to `\smallvtwo{u}{v}` and `\smallvtwo{-u}{\hfill v}`, respectively. The `s`-relation kills the class of `\smallvtwo{u}{v}` if and only if `i_1=i_2` but `\alp_1\neq s\alp_2`. .. _sec:degen: Degeneracy Maps --------------- In this section, we describe natural maps between spaces of modular symbols with character of different levels. We consider spaces with character, since they are so important in applications. .. index:: Dirichlet character Fix a positive integer `N` and a Dirichlet character `\eps : (\Z/N\Z)^*\ra \C^*`. Let `M` be a positive divisor of `N` that is divisible by the conductor of `\eps`, in the sense that `\eps` factors through `(\Z/M\Z)^*` via the natural map `(\Z/N\Z)^*\ra (\Z/M\Z)^*` composed with some uniquely defined character `\eps':(\Z/M\Z)^*\ra\C^*`. For any positive divisor `t` of `N/M`, let `T=\abcd{1}{0}{0}{t}` and fix a choice `D_t=\{T\gamma_i : i=1,\ldots, n\}` of coset representatives for `\Gamma_0(N)\backslash T\Gamma_0(M)`. .. remark:: Note that :cite:`[\S2.6]{merel:1585}` contains a typo: The quotient " `\Gamma_1(N)\backslash\Gamma_1(M)T` " should be replaced by " `\Gamma_1(N)\backslash T\Gamma_1(M)` ". .. proposition:: For each divisor `t` of `N/M` there are well-defined linear maps .. math:: \alp_t : \sM_k(N,\eps) \ra \sM_k(M,\eps'),&\qquad \alp_t(x) = (tT^{-1})x = \mtwo{t}{0}{0}{1} x,\\ \beta_t : \sM_k(M,\eps') \ra \sM_k(N,\eps),&\qquad \beta_t(x) = \sum_{T\gamma_i\in D_t} \eps'(\gamma_i)^{-1}T\gamma_i{} x. Furthermore, `\alp_t\circ \beta_t` is multiplication by `t^{k-2}\cdot [\Gamma_0(M) : \Gamma_0(N)].` .. proof:: To show that `\alp_t` is well defined, we must show that for each `x\in\sM_k(N,\eps)` and `\gamma=\abcd{a}{b}{c}{d}\in\Gamma_0(N)`, we have .. math:: \alp_t(\gamma x -\eps(\gamma) x)=0\in\sM_k(M,\eps'). We have .. math:: \alp_t(\gamma{}x) = \mtwo{t}{0}{0}{1}\gamma{}x = \mtwo{a}{tb}{c/t}{d}\mtwo{t}{0}{0}{1} x = \eps'(a)\mtwo{t}{0}{0}{1} x, so .. math:: \alp_t(\gamma x -\eps(\gamma) x) = \eps'(a)\alp_t(x) - \eps(\gamma)\alp_t(x) = 0. We next verify that `\beta_t` is well defined. Suppose that `x\in\sM_k(M,\eps')` and `\gamma\in\Gamma_0(M)`; then `\eps'(\gamma)^{-1}\gamma{}x = x`, so .. math:: \beta_t(x) &= \sum_{T\gamma_i\in D_t} \eps'(\gamma_i)^{-1}T\gamma_i{}\eps'(\gamma)^{-1}\gamma{} x\\ &= \sum_{T\gamma_i\gamma\in D_t} \eps'(\gamma_i\gamma)^{-1}T\gamma_i{}\gamma{} x. This computation shows that the definition of `\beta_t` does not depend on the choice `D_t` of coset representatives. To finish the proof that `\beta_t` is well defined, we must show that, for `\gamma\in\Gamma_0(M)`, we have `\beta_t(\gamma{}x) = \eps'(\gamma)\beta_t(x)` so that `\beta_t` respects the relations that define `\sM_k(M,\eps)`. Using that `\beta_t` does not depend on the choice of coset representative, we find that for `\gamma\in\Gamma_0(M)`, .. math:: \beta_t(\gamma{}x) &= \sum_{T\gamma_i\in D_t} \eps'(\gamma_i)^{-1}T\gamma_i{} \gamma{} x\\ &= \sum_{T\gamma_i\gamma^{-1}\in D_t} \eps'(\gamma_i\gamma^{-1})^{-1}T\gamma_i{}\gamma{}^{-1} \gamma{} x\\ &= \eps'(\gamma)\beta_t(x).\\ To compute `\alp_t\circ\beta_t`, we use that `\#D_t = [\Gamma_0(N) : \Gamma_0(M)]`: .. math:: \alp_t(\beta_t(x)) &= \alp_t \left(\sum_{T\gamma_i} \eps'(\gamma_i)^{-1}T\gamma_i x\right)\\ &= \sum_{T\gamma_i} \eps'(\gamma_i)^{-1}(tT^{-1})T\gamma_i x\\ &= t^{k-2}\sum_{T\gamma_i} \eps'(\gamma_i)^{-1}\gamma_i x\\ &= t^{k-2}\sum_{T\gamma_i} x \\ &= t^{k-2} \cdot [\Gamma_0(N) : \Gamma_0(M)] \cdot x. The scalar factor of `t^{k-2}` appears instead of `t`, because `t` is acting on `x` as an element of `\GL_2(\Q)` and *not* as an an element of `\Q`. .. definition:: New and Old Modular Symbols :label: def:newandoldsymbols} .. index:: single: new modular symbols single: old modular symbols pair: modular symbols; new and old subspace of The space `\sM_k(N,\eps)_{\new}` of :defn:`new modular symbols` is the intersection of the kernels of the `\alp_t` as `t` runs through all positive divisors of `N/M` and `M` runs through positive divisors of `M` strictly less than `N` and divisible by the conductor of `\eps`. The subspace `\sM_k(N,\eps)_{\old}` of :defn:`old modular symbols` is the subspace generated by the images of the `\beta_t` where `t` runs through all positive divisors of `N/M` and `M` runs through positive divisors of `M` strictly less than `N` and divisible by the conductor of `\eps`. The new and old subspaces of cuspidal modular symbols are the intersections of the above spaces with `\sS_k(N,\eps)`. .. example:: The new and old subspaces need not be disjoint, as the following example illustrates! (This contradicts :cite:`[pg.~80]{merel:1585}`.) Consider, for example, the case `N=6`, `k=2`, and trivial character. The spaces `\sM_2(\Gamma_0(2))` and `\sM_2(\Gamma_0(3))` are each of dimension `1`, and each is generated by the modular symbol `\{\infty,0\}`. The space `\sM_2(\Gamma_0(6))` is of dimension `3` and is generated by the three modular symbols `\{\infty, 0\}`, `\{-1/4, 0\}`, and `\{-1/2, -1/3\}`. The space generated by the two images of `\sM_2(\Gamma_0(2))` under the two degeneracy maps has dimension `2`, and likewise for `\sM_2(\Gamma_0(3))`. Together these images generate `\sM_2(\Gamma_0(6))`, so `\sM_2(\Gamma_0(6))` is equal to its old subspace. However, the new subspace is nontrivial because the two degeneracy maps `\sM_2(\Gamma_0(6)) \ra \sM_2(\Gamma_0(2))` are equal, as are the two degeneracy maps .. math:: \sM_2(\Gamma_0(6)) \ra \sM_2(\Gamma_0(3)). In particular, the intersection of the kernels of the degeneracy maps has dimension at least `1` (in fact, it equals `1`). We verify some of the above claims using Sage. :: sage: M = ModularSymbols(Gamma0(6)); M Modular Symbols space of dimension 3 for Gamma_0(6) of weight 2 with sign 0 over Rational Field sage: M.new_subspace() Modular Symbols subspace of dimension 1 of Modular Symbols space of dimension 3 for Gamma_0(6) of weight 2 with sign 0 over Rational Field sage: M.old_subspace() Modular Symbols subspace of dimension 3 of Modular Symbols space of dimension 3 for Gamma_0(6) of weight 2 with sign 0 over Rational Field .. _sec:compg0n: Explicitly Computing `\sM_k(\Gamma_0(N))` ----------------------------------------- In this section we explicitly compute `\sM_k(\Gamma_0(N))` for various `k` and `N`. We represent Manin symbols for `\Gamma_0(N)` as triples of integers `(i, u,v)`, where `(u,v)\in\P^1(\Z/N\Z)`, and `(i, u,v)` corresponds to `[X^i Y^{k-2-i}, (u,v)]` in the usual notation. Also, recall from :ref:`prop:p1bij` that `(u,v)` corresponds to the right coset of `\Gamma_0(N)` that contains a matrix `\abcd{a}{b}{c}{d}` with `(u,v)\con (c,d)` as elements of `\P^1(\Z/N\Z)`, i.e., up to rescaling by an element of `(\Z/N\Z)^*`. .. _sec:p1rep: Computing `\P^1(\Z/N\Z)` ~~~~~~~~~~~~~~~~~~~~~~~~ In this section we give an algorithm to compute a canonical representative for each element of `\P^1(\Z/N\Z)`. This algorithm is extremely important because modular symbols implementations use it a huge number of times. A more naive approach would be to store all pairs `(u,v)\in (\Z/N\Z)^2` and a fixed reduced representative, but this wastes a huge amount of memory. For example, if `N=10^5`, we would store an array of .. math:: 2 \cdot 10^5 \cdot 10^5 = 20 \text{ billion integers}. Another approach to enumerating `\P^1(\Z/N\Z)` is described at the end of :cite:`[\S2.2]{cremona:algs}`. It uses the fact that is easy to test whether two pairs `(u_0,v_0), (u_1,v_1)` define the same element of `\P^1(\Z/N\Z)`; they do if and only if we have equality of cross terms `u_0 v_1 = v_0 u_1\pmod{N}` (see :cite:`[Prop.~2.2.1]{cremona:algs}`). So we consider the `0`-based list of elements .. math:: :label: eqn:zerobased (1,0), (1,1), \ldots, (1,N-1), (0,1) concatenated with the list of nonequivalent elements `(d,a)` for `d\mid N` and `a=1,\ldots, N-1`, checking each time we add a new element to our list (of `(d,a)`) whether we have already seen it. Given a random pair `(u,v)`, the problem is then to find the index of the element of our list of the equivalent representative in `\P^1(\Z/N\Z)`. We use the following algorithm, which finds a canonical representative for each element of `\P^1(\Z/N\Z)`. Given an arbitrary `(u,v)`, we first find the canonical equivalent elements `(u',v')`. If `u'=1`, then the index is `v'`. If `u'\neq 1`, we find the corresponding element in an explicit sorted list, e.g., using binary search. In the following algorithm, `a \pmod{N}` denotes the residue of `a` modulo `N` that satisfies `0 \leq a < N`. Note that we *never* create and store the list :eq:`eqn:zerobased` itself in memory. .. algorithm:: Reduction in `\P^1(\Z/N\Z)` to Canonical Form :label: alg:p1rep Given `u` and `v` and a positive integer `N`, this algorithm outputs a pair `u_0, v_0` such that `(u,v) \con (u_0,v_0)` as elements of `\P^1(\Z/N\Z)` and `s\in\Z` such that `(u,v) = (su_0, sv_0) \pmod{\Z/n\Z}`. Moreover, the element `(u_0,v_0)` does not depend on the class of `(u,v)`, i.e., for any `s` with `\gcd(N,s)=1` the input `(su,sv)` also outputs `(u_0,v_0)`. If `(u,v)` is not in `\P^1(\Z/N\Z)`, this algorithm outputs `(0,0), 0`. 1. [Reduce] Reduce both `u` and `v` modulo `N`. 2. [Easy `(0,1)` Case] If `u=0`, check that `\gcd(v,N)=1`. If so, return `s=1` and `(0,1)`; otherwise return `0`. 3. [GCD] Compute `g=\gcd(u,N)` and `s,t\in\Z` such that `g=su+tN`. 4. [Not in `P^1`?] We have `\gcd(u,v,N)=\gcd(g,v)`, so if `\gcd(g,v)>1`, then `(u,v)\not\in\P^1(\Z/N\Z)`, and we return `0`. 5. [Pseudo-Inverse] Now `g = su + tN`, so we may think of `s` as "pseudo-inverse" of `u \pmod{N}`, in the sense that `su` is as close as possible to being `1` modulo `N`. Note that since `g\mid u`, changing `s` modulo `N/g` does not change `su\pmod{N}`. We can adjust `s` modulo `N/g` so it is coprime to `N` (by adding multiples of `N/g` to `s`). (This is because `1 = s u/g + tN/g`, so `s` is a unit mod `N/g`, and the map `(\Z/N\Z)^* \to (\Z/(N/g)\Z)^*` is surjective, e.g., as we saw in the proof of :ref:`alg:restrict`.) 6. [Multiply by `s`] Multiply `(u,v)` by `s`, and replace `(u,v)` by the equivalent element `(g,sv)` of `\P^1(\Z/N\Z)`. 7. [Normalize] Compute the unique pair `(g,v')` equivalent to `(g,v)` that minimizes `v`, as follows: a. [Easy Case] If `g=1`, this pair is `(1,v)`. b. [Enumerate and Find Best] Otherwise, note that if `1\neq t\in(\Z/N\Z)^*` and `tg \con g\pmod{N}`, then `(t-1)g \con 0\pmod{N}`, so `t-1 = kN/g` for some `k` with `1\leq k \leq g-1`. Then for `t=1+kN/g` coprime to `N`, we have `(gt, vt) = (g, v+kvN/g)`. So we compute all pairs `(g, v+kvN/g)` and pick out the one that minimizes the least nonnegative residue of `vt` modulo `N`. c. [Invert `s` and Output] The `s` that we computed in the above steps multiplies the input `(u,v)` to give the output `(u_0,v_0)`. Thus we invert it, since the scalar we output multiplies `(u_0,v_0)` to give `(u,v)`. .. remark:: In the above algorithm, there are many gcd's with `N` so one should create a table of the gcd's of `0,1,2,\ldots, N-1` with `N`. .. remark:: Another approach is to instead use that .. math:: \P^1(\Z/N\Z)\isom \prod_{p\mid N} \P^1(\Z/p^{\nu_p}\Z), where `\nu_p = \ord_p(N)`, and that it is relatively easy to enumerate the elements of `\P^1(\Z/p^n\Z)` for a prime power `p^n`. .. algorithm:: List `\P^1(\Z/N\Z)` Given an integer `N>1`, this algorithm makes a sorted list of the distinct representatives `(c,d)` of `\P^1(\Z/N\Z)` with `c\neq 0,1`, as output by :ref:`alg:p1rep`. 1. For each `c=1,\ldots, N-1` with `g = \gcd(c,N) > 1` do the following: a. Use :ref:`alg:p1rep` to compute the canonical representative `(u',v')` equivalent to `(c,1)`, and include it in the list. b. If `g=c`, for each `d=2,\ldots, N-1` with `\gcd(d,N)>1` and `\gcd(c,d)=1`, append the normalized representative of `(c,d)` to the list. 2. Sort the list. 3. Pass through the sorted list and delete any duplicates. Explicit Examples ----------------- Explicit detailed examples are crucial when implementing modular symbols algorithms from scratch. This section contains a number of such examples. Examples of Computation of `\sM_k(\Gamma_0(N))` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ In this section, we compute `\sM_k(\Gamma_0(N))` explicitly in a few cases. .. example:: :label: example:m4_1 We compute `V=\sM_4(\Gamma_0(1))`. Because `S_k(\Gamma_0(1))=0` and `M_k(\Gamma_0(1))=\C E_4`, we expect `V` to have dimension `1` and for each integer `n` the Hecke operator `T_n` to have eigenvalue the sum `\sigma_3(n)` of the cubes of positive divisors of `n`. The Manin symbols are .. math:: x_0 = (0, 0, 0), \quad x_1 = (1, 0, 0), \quad x_2 = (2, 0, 0). The relation matrix is .. math:: \left(\begin{matrix} {}1&{}0&{}1\\ {}0&{}0&{}0\\ \hline {}2&{}-2&{}2\\ {}1&{}-1&{}1\\ {}2&{}-2&{}2 \end{matrix}\right), where the first two rows correspond to `S`-relations and the second three to `T`-relations. Note that we do not include all `S`-relations, since it is obvious that some are redundant, e.g., `x+xS=0` and `(xS) + (xS)S=xS + x=0` are the same since `S` has order `2`. The echelon form of the relation matrix is .. math:: \left(\begin{matrix} \hfill{}1&\hfill{}0&\hfill{}1\\ \hfill{}0&\hfill{}1&\hfill{}0\\ \end{matrix}\right), where we have deleted the zero rows from the bottom. Thus we may replace the above complicated list of relations with the following simpler list of relations: .. math:: x_0 + x_2 &= 0,\\ x_1 &= 0 from which we immediately read off that the second generator `x_1` is `0` and `x_0=-x_2`. Thus `\sM_4(\Gamma_0(1))` has dimension `1`, with basis the equivalence class of `x_2` (or of `x_0`). .. index:: Heilbronn matrices Next we compute the Hecke operator `T_2` on `\sM_4(\Gamma_0(1))`. The Heilbronn matrices of determinant `2` from :ref:`prop:heilbronn` are .. math:: h_0&=\left(\begin{matrix} \hfill{}1&\hfill{}0\\ \hfill{}0&\hfill{}2 \end{matrix}\right),\quad{}\\ h_1&=\left(\begin{matrix} \hfill{}1&\hfill{}0\\ \hfill{}1&\hfill{}2 \end{matrix}\right),\quad{}\\ h_2&=\left(\begin{matrix} \hfill{}2&\hfill{}0\\ \hfill{}0&\hfill{}1 \end{matrix}\right),\quad{}\\ h_3&=\left(\begin{matrix} \hfill{}2&\hfill{}1\\ \hfill{}0&\hfill{}1 \end{matrix}\right). To compute `T_2`, we apply each of these matrices to `x_0`, then reduce modulo the relations. We have .. math:: x_2\mtwo{1}{0}{0}{2} &= [X^2,(0,0)] \mtwo{1}{0}{0}{2} x_2,\\ x_2 \mtwo{1}{0}{1}{2} &= [X^2,(0,0)] = x_2,\\ x_2 \mtwo{2}{0}{0}{1} &= [(2X)^2,(0,0)] = 4x_2,\\ x_2 \mtwo{2}{1}{0}{1} &= [(2X+1)^2,(0,0)] = x_0 + 4x_1 + 4x_2 \sim 3x_2. Summing we see that `T_2(x_2) \sim 9x_2` in `\sM_4(\Gamma_0(1))`. Notice that .. math:: 9=1^3+2^3 = \sigma_3(2). .. index:: Heilbronn matrices The Heilbronn matrices of determinant `3` from :ref:`prop:heilbronn` are .. math:: h_0&=\left(\begin{matrix} \hfill{}1&\hfill{}0\\ \hfill{}0&\hfill{}3 \end{matrix}\right),\quad{} h_1=\left(\begin{matrix} \hfill{}1&\hfill{}0\\ \hfill{}1&\hfill{}3 \end{matrix}\right),\quad{}\\ h_2&=\left(\begin{matrix} \hfill{}1&\hfill{}0\\ \hfill{}2&\hfill{}3 \end{matrix}\right),\quad{} h_3=\left(\begin{matrix} \hfill{}2&\hfill{}1\\ \hfill{}1&\hfill{}2 \end{matrix}\right),\quad{}\\ h_4&=\left(\begin{matrix} \hfill{}3&\hfill{}0\\ \hfill{}0&\hfill{}1 \end{matrix}\right),\quad{} h_5=\left(\begin{matrix} \hfill{}3&\hfill{}1\\ \hfill{}0&\hfill{}1 \end{matrix}\right),\quad{}\\ h_6&=\left(\begin{matrix} \hfill{}3&\hfill{}2\\ \hfill{}0&\hfill{}1 \end{matrix}\right). We have .. math:: x_2 \mtwo{1}{0}{0}{3} &= [X^2,(0,0)] \mtwo{1}{0}{0}{3} = x_2,\\ x_2 \mtwo{1}{0}{1}{3} &= [X^2,(0,0)] = x_2,\\ x_2 \mtwo{1}{0}{2}{3} &= [X^2,(0,0)] = x_2,\\ x_2 \mtwo{2}{1}{2}{2} &= [(2X+1)^2,(0,0)] = x_0 + 4x_1 + 4x_2 \sim 3x_2,\\ x_2 \mtwo{3}{0}{0}{1} &= [(3X)^2,(0,0)] = 9x_2,\\ x_2 \mtwo{3}{1}{0}{1} &= [(3X+1)^2,(0,0)] = x_0 + 6x_1 + 9x_2 \sim 8x_2,\\ x_2 \mtwo{3}{2}{0}{1} &= [(3X+2)^2,(0,0)] = 4x_0 + 12x_1 + 9x_2 \sim 5x_2.\\ Summing we see that .. math:: T_3(x_2) \sim x_2 + x_2 + x_2 + 3x_2 + 9x_2 + 8x_2 + 5x_2 = 28 x_2. Notice that .. math:: 28=1^3+3^3 = \sigma_3(3). .. example:: Next we compute `\sM_2(\Gamma_0(11))` explicitly. The Manin symbol generators are .. math:: x_0= (0, 1),\quad\!\!\!\! x_1= (1, 0),\quad\!\!\!\! x_2= (1, 1),\quad\!\!\!\! x_3= (1, 2),\quad\!\!\!\! x_4= (1, 3),\quad\!\!\!\! x_5= (1, 4),\quad\!\! .. math:: x_6= (1, 5),\quad\!\!\!\! x_7= (1, 6),\quad\!\!\!\! x_8= (1, 7),\quad\!\!\!\! x_9= (1, 8),\quad\!\!\!\! x_{10}= (1, 9),\quad\!\!\!\! x_{11}= (1, 10). The relation matrix is as follows, where the `S`-relations are above the line and the `T`-relations are below it: .. math:: \left(\begin{array}{ccccccccccccc} 1&1&0&0&0&0&0&0&0&0&0&0\\ 0&0&1&0&0&0&0&0&0&0&0&1\\ 0&0&0&1&0&0&1&0&0&0&0&0\\ 0&0&0&0&1&0&0&0&1&0&0&0\\ 0&0&0&0&0&1&0&0&0&1&0&0\\ 0&0&0&0&0&0&0&1&0&0&1&0\\ \hline 1&1&0&0&0&0&0&0&0&0&0&1\\ 0&0&1&0&0&0&1&0&0&0&1&0\\ 0&0&0&1&0&1&0&0&1&0&0&0\\ 0&0&0&0&1&0&0&1&0&1&0&0 \end{array}\right). In weight `2`, two out of three `T`-relations are redundant, so we do not include them. The reduced row echelon form of the relation matrix is .. math:: \left(\begin{array}{cccccccccccc} 1&1&0&0&0&0&0&0&0&0&0&0\\ 0&0&1&0&0&0&0&0&0&0&0&0\\ 0&0&0&1&0&0&0&0&0&0&-1&0\\ 0&0&0&0&1&0&0&0&0&1&-1&0\\ 0&0&0&0&0&1&0&0&0&1&0&0\\ 0&0&0&0&0&0&1&0&0&0&1&0\\ 0&0&0&0&0&0&0&1&0&0&1&0\\ 0&0&0&0&0&0&0&0&1&-1&1&0\\ 0&0&0&0&0&0&0&0&0&0&0&1\\ 0&0&0&0&0&0&0&0&0&0&0&0 \end{array}\right). From the echelon form we see that every symbol is equivalent to a combination of `x_1=(1,0)`, `x_9=(1,8)`, and `x_{10}=(1,9)`. (Notice that columns `1`, `9`, and `10` are the pivot columns, where we index columns starting at `0`.) .. index:: Heilbronn matrices To compute `T_2`, we apply each of the Heilbronn matrices of determinant `2` from :ref:`prop:heilbronn` to `x_1`, then to `x_9`, and finally to `x_{10}`. The matrices are as in :ref:`example:m4_1` above. We have .. math:: T_2(x_1) = 3(1,0) + (1,6) \sim 3x_1 - x_{10}. Applying `T_2` to `x_9=(1,8)`, we get .. math:: T_2(x_9) = (1,3) + (1,4) + (1,5) + (1,10) \sim -2x_9. Applying `T_2` to `x_{10}=(1,9)`, we get .. math:: T_2(x_{10})= (1,4)+(1,5) + (1,7) + (1,10) \sim -x_1 - 2x_{10}. Thus the matrix of `T_2` with respect to this basis is .. math:: T_2 = \left(\begin{array}{ccc} 3&0&0\\ 0&-2&0\\ -1&0&-2 \end{array}\right), where we write the matrix as an operator on the left on vectors written in terms of `x_1`, `x_9`, and `x_{10}`. The matrix `T_2` has characteristic polynomial .. math:: (x-3) (x+2)^2. The `(x-3)` factor corresponds to the weight `2` Eisenstein series, and the `x+2` factor corresponds to the elliptic curve `E=X_0(11)`, which has .. math:: a_2 = -2 = 2+1 - \#E(\F_2). .. example:: In this example, we compute `\sM_6(\Gamma_0(3))`, which illustrates both weight greater than `2` and level greater than `1`. We have the following generating Manin symbols: .. math:: x_{0} &= [XY^4,(0,1)],\qquad x_{1} = [XY^4,(1,0)],\\ x_{2} &= [XY^4,(1,1)], \qquad x_{3} = [XY^4,(1,2)],\\ x_{4} &= [XY^3,(0,1)], \qquad x_{5} = [XY^3,(1,0)],\\ x_{6} &= [XY^3,(1,1)], \qquad x_{7} = [XY^3,(1,2)],\\ x_{8} &= [X^2Y^2,(0,1)], \qquad \!\!x_{9} = [X^2Y^2,(1,0)],\\ x_{10} &= [X^2Y^2,(1,1)], \qquad \!\!\!\!x_{11} = [X^2Y^2,(1,2)],\\ x_{12} &= [X^3Y,(0,1)], \qquad x_{13} = [X^3Y,(1,0)],\\ x_{14} &= [X^3Y,(1,1)], \qquad x_{15} = [X^3Y,(1,2)],\\ x_{16} &= [X^4Y,(0,1)], \qquad x_{17} = [X^4Y,(1,0)],\\ x_{18} &= [X^4Y,(1,1)], \qquad x_{19} = [X^4Y,(1,2)].\\ The relation matrix is already very large for `\M_6(\Gamma_0(3))`. It is as follows, where the `S`-relations are before the line and the `T`-relations after it: .. math:: \left(\begin{array}{cccccccccccccccccccc} 1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0\\ 0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0\\ 0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1\\ 0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0\\ 0&0&0&0&1&0&0&0&0&0&0&0&0&-1&0&0&0&0&0&0\\ 0&0&0&0&0&1&0&0&0&0&0&0&-1&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&-1&0&0&0&0\\ 0&0&0&0&0&0&0&1&0&0&0&0&0&0&-1&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&1&1&0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0&1&1&0&0&0&0&0&0&0&0\\\hline 1&0&0&1&0&0&0&-4&0&0&0&6&0&0&0&-4&0&1&0&1\\ 1&1&0&0&-4&0&0&0&6&0&0&0&-4&0&0&0&1&0&0&1\\ 0&0&2&0&0&0&-4&0&0&0&6&0&0&0&-4&0&0&0&2&0\\ 0&1&0&1&0&-4&0&0&0&6&0&0&0&-4&0&0&1&1&0&0\\ 0&0&0&1&1&0&0&-3&0&0&0&3&0&-1&0&-1&0&1&0&0\\ 1&0&0&0&-3&1&0&0&3&0&0&0&-1&0&0&-1&0&0&0&1\\ 0&0&1&0&0&0&-2&0&0&0&3&0&0&0&-2&0&0&0&1&0\\ 0&1&0&0&0&-3&0&1&0&3&0&0&-1&-1&0&0&1&0&0&0\\ 0&0&0&1&0&0&0&-2&1&1&0&1&0&-2&0&0&0&1&0&0\\ 1&0&0&0&-2&0&0&0&1&1&0&1&0&0&0&-2&0&0&0&1\\ 0&0&1&0&0&0&-2&0&0&0&3&0&0&0&-2&0&0&0&1&0\\ 0&1&0&0&0&-2&0&0&1&1&0&1&-2&0&0&0&1&0&0&0\\ 0&0&0&1&0&-1&0&-1&0&3&0&0&1&-3&0&0&0&1&0&0\\ 1&0&0&0&-1&0&0&-1&0&0&0&3&0&1&0&-3&0&0&0&1\\ 0&0&1&0&0&0&-2&0&0&0&3&0&0&0&-2&0&0&0&1&0\\ 0&1&0&0&-1&-1&0&0&3&0&0&0&-3&0&0&1&1&0&0&0\\ 0&1&0&1&0&-4&0&0&0&6&0&0&0&-4&0&0&1&1&0&0\\ 1&0&0&1&0&0&0&-4&0&0&0&6&0&0&0&-4&0&1&0&1\\ 0&0&2&0&0&0&-4&0&0&0&6&0&0&0&-4&0&0&0&2&0\\ 1&1&0&0&-4&0&0&0&6&0&0&0&-4&0&0&0&1&0&0&1 \end{array}\right). The reduced row echelon form of the relations matrix, with zero rows removed is .. math:: \hspace{-1em}\left(\begin{array}{cccccccccccccccccccc} 1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0\\ 0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0\\ 0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1\\ 0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0\\ 0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&3/16&-3/16\\ 0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&-1/16&1/16\\ 0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&1/2&-5/16&-3/16\\ 0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&-1/2&3/16&5/16\\ 0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&-1/6&1/12&1/12\\ 0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1/6&-1/12&-1/12\\ 0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1/4&-1/4\\ 0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&-1/4&1/4\\ 0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&-1/16&1/16\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&3/16&-3/16\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&-1/2&3/16&5/16\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&1/2&-5/16&-3/16\\ \end{array}\right). Since these relations are equivalent to the original relations, we see how `x_0, \ldots, x_{15}` can be expressed in terms of `x_{16}`, `x_{17}`, `x_{18}`, and `x_{19}`. Thus `\sM_6(\Gamma_0(3))` has dimension `4`. For example, .. math:: x_{15} \sim \frac{1}{2} x_{17} -\frac{5}{16}x_{18} - \frac{3}{16} x_{19}. Notice that the number of relations is already quite large. It is perhaps surprising how complicated the presentation is already for `\sM_6(\Gamma_0(3))`. Because there are denominators in the relations, the above calculation is only a computation of `\sM_6(\Gamma_0(3);\Q)`. Computing `\sM_6(\Gamma_0(3);\Z)` involves finding a `\Z`-basis for the kernel of the relation matrix (see :ref:`ex:hnf`). As before, we find that with respect to the basis `x_{16}`, `x_{17}`, `x_{18}`, and `x_{19}` .. math:: T_2 = \left(\begin{array}{cccc} 33&0&0&0\\ 3&6&12&12\\ -3/2&27/2&15/2&27/2\\ -3/2&27/2&27/2&15/2 \end{array}\right). Notice that there are denominators in the matrix for `T_2` with respect to this basis. It is clear from the definition of `T_2` acting on Manin symbols that `T_2` preserves the `\Z`-module `\sM_6(\Gamma_0(3))`, so there is some basis for `\sM_6(\Gamma_0(3))` such that `T_2` is given by an integer matrix. Thus the characteristic polynomial `f_2` of `T_2` will have integer coefficients; indeed, .. math:: f_2 = (x-33)^2 \cdot (x+6)^2. Note the factor `(x-33)^2`, which comes from the two images of the Eisenstein series `E_4` of level `1`. The factor `x+6` comes from the cusp form .. math:: g = q - 6q^2 + \cdots \in S_6(\Gamma_0(3)). By computing more Hecke operators `T_n`, we can find more coefficients of `g`. For example, the charpoly of `T_3` is `(x-1)(x-243)(x-9)^2`, and the matrix of `T_5` is .. math:: T_5 = \left(\begin{array}{cccc} 3126&0&0&0\\ 240&966&960&960\\ -120&1080&1086&1080\\ -120&1080&1080&1086 \end{array}\right), which has characteristic polynomial .. math:: f_5 = (x-3126)^2 (x-6)^2. The matrix of `T_7` is .. math:: T_7 = \left(\begin{array}{cccc} 16808&0&0&0\\ 1296&5144&5184&5184\\ -648&5832&5792&5832\\ -648&5832&5832&5792 \end{array}\right), with characteristic polynomial .. math:: f_7 = (x -16808)^2 (x + 40)^2. One can put this information together to deduce that .. math:: g = q - 6q^2 + 9q^3 + 4q^4 + 6q^5 - 54q^6 - 40q^7 +\cdots. .. example:: Consider `\M_2(\Gamma_0(43))`, which has dimension `7`. With respect to the symbols .. math:: x_1&=(1,0),\quad x_{32}=(1,31),\quad x_{33} = (1,32),\\ x_{39} &= (1,38),\quad x_{40} = (1,39), \quad x_{41} = (1,40),\quad x_{42} = (1,41), the matrix of `T_2` is .. math:: T_2=\left(\begin{array}{ccccccc} 3&0&0&0&0&0&0\\ 0&-2&-1&-1&-1&0&0\\ 0&1&1&0&0&-2&-1\\ 0&0&1&-1&1&0&0\\ 0&0&0&2&1&2&1\\ 0&0&-1&-1&-1&-2&0\\ -1&0&0&1&1&1&-1 \end{array}\right), which has characteristic polynomial .. math:: (x-3)(x+2)^2 (x^2-2)^2. There is one Eisenstein series and there are three cusp forms with `a_2 = -2` and `a_2 = \pm \sqrt{2}`. .. example:: To compute `\sM_2(\Gamma_0(2004);\Q)`, we first make a list of the .. math:: 4032 = (2^2 + 2) \cdot (3+1) \cdot (167 + 1) elements `(a,b)\in\P^1(\Z/2004\Z)` using :ref:`alg:p1rep`. The list looks like this: .. math:: (0, 1), (1, 0), (1, 1), (1, 2), \ldots, (668, 1), (668, 3), (668, 5), (1002, 1). For each of the symbols `x_i`, we consider the `S`-relations and `T`-relations. Ignoring the redundant relations, we find `2016` `S`-relations and `1344` `T`-relations. It is simple to quotient out by the `S`-relations, e.g., by identifying `x_i` with `-x_i S = -x_j` for some `j` (or setting `x_i=0` if `x_i S = x_i`). Once we have taken the quotient by the `S`-relations, we take the *image* of all `1344` of the `T`-relations modulo the `S`-relations and quotient out by those relations. Because `S` and `T` do not commutate, we cannot only quotient out by `T`-relations `x_i + x_i T + x_i T^2 = 0` where the `x_i` are the basis after quotienting out by the `S`-relations. The relation matrix has rank `3359`, so `\sM_2(\Gamma_0(2004);\Q)` has dimension `673`. If we instead compute the quotient `\sM_2(\Gamma_0(2004);\Q)^+` of `\sM_2(\Gamma_0(2004);\Q)` by the subspace of elements `x-\eta^*(x)`, we include relations `x_i+x_iI=0`, where `I=\abcd{-1}{0}{0}{1}`. There are now 2016 `S`-relations, 2024 `I`-relations, and 1344 `T`-relations. Again, it is relatively easy to quotient out by the `S`-relations by identifying `x_i` and `-x_i S`. We then take the image of all `2024` `I`-relations modulo the `S`-relations, and again directly quotient out by the `I`-relations by identifying `[x_i]` with `-[x_iI]=-[x_j]` for some `j`, where by `[x_i]` we mean the class of `x_i` modulo the `S`-relations. Finally, we quotient out by the `1344` `T`-relations, which involves sparse Gauss elimination on a matrix with `1344` rows and at most three nonzero entries per row. The dimension of `\sM_2(\Gamma_0(2004);\Q)^+` is `331`. Refined Algorithm for the Presentation -------------------------------------- .. algorithm:: Modular Symbols Presentation :label: alg:modsympresent This is an algorithm to compute `\sM_k(\Gamma_0(N);\Q)` or `\sM_k(\Gamma_0(N);\Q)^{\pm}`, which only requires doing generic sparse linear algebra to deal with the three term `T`-relations. 1. Let `x_0,\ldots, x_n` by a list of all Manin symbols. 2. Quotient out the two-term `S`-relations and if the `\pm` quotient is desired, by the two-term `\eta`-relations. (Note that this is more subtle than just "identifying symbols in pairs", since complicated relations can cause generators to surprisingly equal `0`.) Let `[x_i]` denote the class of `x_i` after this quotienting process. 3. Create a sparse matrix `A` with `m` columns, whose rows encode the relations .. math:: [x_i] + [x_iT] + [x_iT^2] = 0. For example, there are about `n/3` such rows when `k=2`. The number of nonzero entries per row is at most `3(k-1)`. Note that we must include rows for *all* `i`, since even if `[x_i] = [x_j]`, it need not be the case that `[x_i T] = [x_jT]`, since the matrices `S` and `T` do not commute. However, we have an a priori formula for the dimension of the quotient by all these relations, so we could omit many relations and just check that there are enough at the end---if there are not, we add in more. 4. Compute the reduced row echelon form of `A` using :ref:`alg:modech`. For `k=2`, this is the echelon form of a matrix with size about `n/3 \times n/4`. 5. Use what we have done above to read off a sparse matrix `R` that expresses each of the `n` Manin symbols in terms of a basis of Manin symbols, modulo the relations. Applications ------------ Later in This Book ~~~~~~~~~~~~~~~~~~ We sketch some of the ways in which we will apply the modular symbols algorithms of this chapter later in this book. .. index:: newform Cuspidal modular symbols are in Hecke-equivariant duality with cuspidal modular forms, and as such we can compute modular forms by computing systems of eigenvalues for the Hecke operators acting on modular symbols. By the Atkin-Lehner-Li theory of newforms (see, e.g., :ref:`thm:ALL`), we can construct `S_k(N,\eps)` for any `N`, any `\eps`, and `k\geq 2` using this method. See Chapter :ref:`ch:modform` for more details. .. index:: newform Once we can compute spaces of modular symbols, we move to computing the corresponding modular forms. We define inclusion and trace maps from modular symbols of one level `N` to modular symbols of level a multiple or divisor of `N`. Using these, we compute the quotient `V` of the new subspace of cuspidal modular symbols on which a "star involution" acts as `+1`. The Hecke operators act by diagonalizable commuting matrices on this space, and computing the systems of Hecke eigenvalues is equivalent to computing newforms `\sum a_n q^n`. In this way, we obtain a list of *all* newforms (normalized eigenforms) in `S_k(N,\eps)` for any `N`, `\eps`, and `k\geq 2`. In Chapter :ref:`ch:periods`, we compute with the period mapping from modular symbols to `\C` attached to a newform `f \in S_k(N,\eps)`. When `k=2, \eps=1` and `f` has rational Fourier coefficients, this gives a method to compute the period lattice associated to a modular elliptic curve attached to a newform (see Section :ref:`sec:findall`). In general, computation of this map is important when finding equations for modular `\Q`-curves, CM curves, and curves with a given modular Jacobian. It is also important for computing special values of the `L`-function `L(f,s)` at integer points in the critical strip. Discussion of the Literature and Research ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Modular symbols were introduced by Birch :cite:`birch:bsd` for computations in support of the Birch and Swinnerton-Dyer conjecture. Manin :cite:`manin:parabolic` used modular symbols to prove rationality results about special values of `L`-functions. Merel's paper :cite:`merel:1585` builds on work of Shokurov (mainly :cite:`sokurov:shimura`), which develops a higher-weight generalization of Manin's work partly to understand rationality properties of special values of `L`-functions. Cremona's book :cite:`cremona:algs` discusses how to compute the space of weight `2` modular symbols for `\Gamma_0(N)`, in connection with the problem of enumerating all elliptic curves of given conductor, and his article :cite:`cremona:gammaone` discusses the `\Gamma_1(N)` case and computation of modular symbols with character. There have been several Ph.D. theses about modular symbols. Basmaji's thesis :cite:`basmaji:thesis` contains tricks to efficiently compute Hecke operators `T_p`, with `p` very large (see Section :ref:`sec:basmaji`), and also discusses how to compute spaces of half integral weight modular forms building on what one can get from modular symbols of integral weight. The author's Ph.D. thesis :cite:`stein:phd` discusses higher-weight modular symbols and applies modular symbols to study Shafarevich-Tate groups (see also :cite:`agashe:phd`). Martin's thesis :cite:`martin:thesis` is about an attempt to study an analogue of analytic modular symbols for weight `1`. Gabor Wiese's thesis :cite:`gabor:phd` uses modular symbols methods to study weight 1 modular forms modulo `p`. Lemelin's thesis :cite:`lemelin:dominic` discusses modular symbols for quadratic imaginary fields in the context of `p`-adic analogues of the Birch and Swinnerton-Dyer conjecture. See also the survey paper :cite:`frey-muller`, which discusses computation with weight `2` modular symbols in the context of modular abelian varieties. The appendix of this book is about analogues of modular symbols for groups besides finite index subgroups of `\SL_2(\Z)`, e.g., for subgroup of higher rank groups such as `\SL_3(\Z)`. There has also been work on computing Hilbert modular forms, e.g., by Lassina Dembel\'e :cite:`dembele:hilbert5` Hilbert modular forms are functions on a product of copies of `\h`, and `\SL_2(\Z)` is replaced by a group of matrices with entries in a totally real field. Glenn Stevens, Robert Pollack and Henri Darmon (see :cite:`darmon-pollack`) have worked for many years to develop an analogue of modular symbols in a rigid analytic context, which is helpful for questions about computing with overconvergent `p`-adic modular forms or proving results about `p`-adic `L`-functions. Finally we mention that Barry Mazur and some other authors use the term "modular symbol" in a different way than we do. They use the term in a way that is dual to our usage; for example, they attach a "modular symbol" to a modular form or elliptic curve. See :cite:`mtt` for an extensive discussion of modular symbols from this point of view, where they are used to construct `p`-adic `L`-functions. Exercises --------- .. exercise:: :label: ex:surjredmod Suppose `M` is an integer multiple of `N`. Prove that the natural map `(\Z/M\Z)^* \to (\Z/N\Z)^*` is surjective. .. exercise:: :label: ex:surjred Prove that `\SL_2(\Z)\to \SL_2(\Z/N\Z)` is surjective (see :ref:`lem:canlift`). .. exercise:: :label: ex:m3g13 Compute `\sM_{3}(\Gamma_1(3))`. List each Manin symbol the relations they satisfy, compute the quotient, etc. Find the matrix of `T_2`. (Check: The dimension of `\sM_{3}(\Gamma_1(3))` is `2`, and the characteristic polynomial of `T_2` is `(x-3)(x+3)`.) .. exercise:: :label: ex:pairingwd Finish the proof of :ref:`prop:pairwd`. .. exercise:: :label: ex:etaconj a. Show that if `\eta = \abcd{-1}{0}{0}{1}`, then `\eta \Gamma \eta = \Gamma` for `\Gamma=\Gamma_0(N)` and `\Gamma=\Gamma_1(N)`. b. (*) Give an example of a finite index subgroup `\Gamma` such that `\eta \Gamma \eta \neq \Gamma`.