.. _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.