% modsymbols.tex \documentclass[11pt]{article} \textwidth=1.3\textwidth \hoffset=-.7in \textheight=1.1\textheight \voffset=-.4in \title{Manin symbols and modular forms\\{\large (first draft)}} \author{W. Stein\footnote{UC Berkeley, Department of Mathematics, Berkeley, CA 94720, USA.}} \include{macros} \begin{document} \maketitle %\begin{abstract} %\end{abstract} \tableofcontents \section{Introduction} \begin{quote} ``The object of numerical computation is theoretical advance.'' -- Atkin \end{quote} The definition of the spaces $S_k(\Gamma)$ of modular forms as functions on the upper half plane $\h$ satisfying a certain equation is very abstract. The definition of the Hecke operators even more so. We are fortunate that we now have methods available which allow us to transform the vector space of cusp forms of given weight $\geq 2$ and level $N$ into a concrete object, which can be explicitely computed. We have the work of Atkin-Lehner, Birch-Swinnerton-Dyer, Cremona, Manin, Mazur, Merel, and many others to thank for this. The Eichler-Selberg trace formulas, as developed in \cite{hijikata} and \cite{wada}, can be used to compute characteristic polynomials of Hecke operators and hence gain some information about spaces of modular forms. It is also sometimes possible to write down explicit basis in terms of $\Theta$-series and to compute the action of Hecke operators on their $q$-expansions. Other methods include computing the Hecke operators and $q$-expansions using Brandt matrices and quaternion algebras as in \cite{pizer} or \cite{kohel}, or the module of supersingular points in ``characteristic $N$'' as exploited by Mestre and Oesterle in \cite{mestre}. Though the above methods are each beautiful and well suited to certain applications, we will not discuss them further here. Instead we focus on the modular symbols method, as it also has many advantages. We will only discusss the theory in this summary paper, leaving an explicit description of the objects involved for later. Nonetheless there is a definite gap between the {\em theory} on the one hand, and an efficient running machine implimentation on the other. To impliment the algorithms hinted at below requires making absolutely everything completely explnicit and then finding intelligent and efficient ways of performing the necessary manipulations. This is a nontrivial and tedious task, with room for error at every step. Our exposition follows very closely that of \cite{merel}. \subsection{Notation} Let $\Gamma$ be a finite index subgroup of $\sltwoz$ and $k\geq 2$ an integer. If $k$ is odd, assume $-1\not\in\Gamma$, so that the modular forms theory is nonempty. Let $\P^1(\Q) = \Q\union\{\infty\}$. \section{Modular symbols and modular forms} \subsection{Modular symbols} Let $\M$ be the $\Z$-module generated by formal symbols $\{\alpha,\beta\}$, $\alpha, \beta\in\P^1(\Q)$, subject to the relations $$\{\alpha,\beta\}+\{\beta,\gamma\}+\{\gamma,\alpha\}=0.$$ Thus $\{\alpha,\beta\}=-\{\beta,\alpha\}$ and $\{\alpha,\alpha\}=0$. There is a left action of $g\in\gltwoq$ given by $g.\{\alpha,\beta\}=\{g\alpha,g\beta\}$. \comment{% This map has no good properties, so far as I can see! There is a natural homomorphism $$\cD_0\into\M:\quad \alp\mapsto \{0,\alp\}$$ By Manin's trick Lemma~\ref{maninstrick} this map is surjective, [and I think the relations defining $\M$ exactly make it injective]. } Let $$V_k=\Sym^{k-2}_\Z(\Z\cross\Z)=\Z_{k-2}[X,Y]$$ be the free $\Z$-module of homogeneous polynomimals in two variables of degree $k-2$. There is a {\em left} action of $g=\abcd{a}{b}{c}{d}\in\mtwoz$ given by $$g.P(X,Y) = P(\det(g)g^{-1}(X,Y)) = P(dX-bY,-cX+aY).$$ %Note that $g$ induces an automorphism of the algebra %$\Z[X,Y]$ which restricts to a linear endomorphism %of each homogeneous piece, and that %$$g.(h.P(X,Y))=g.P(\det(h)h^{-1}(X,Y))=P(((X,Y)g)h)=(gh).P(X,Y).$$ The space $$\M_k := V_k\tensor_\Z \M.$$ is equipped with a left action of $\mtwoz$ given by $$g.(P\tensor x) =g.P\tensor g.x.$$ %Note that $\M_k$ is {\em not} $V_k\tensor_{\Z[\mtwoz]}\M_k$ %with its induced action. Let $$\M_k(\Gamma):=H_0(\Gamma,\M_k)$$ be the zeroth homology group. Thus $\M_k(\Gamma)$ is the quotient of $\M_k$ by the relations $g.x=x$ for all $x\in\M_k$ and $g\in\Gamma$. The elements of $\M_k(\Gamma)$ are called {\em modular symbols of weight $k$ for $\Gamma$}. As we will see later, using Shapiro's lemma and an explicit computation, $$\M_k(\Gamma)\tensor\C\isom H^1(\Gamma,V_k\tensor\C).$$ The theory of Eichler and Shimura embeds modular forms in $H^1(\Gamma,V_k\tensor\C)$. \subsection{Manin symbols} Let $e=\{0,\infty\}\in\M$. \comment{Note furthermore that $\psltwoz=\sltwoz/\{\pm 1\}$ is the free product of the cyclic group of order $2$ generated by $S$ and the cyclic group of order $3$ generated by $\tau$.} \begin{proposition}[Manin's trick]~\label{maninstrick} The elements $g.e$ for $g\in\sltwoz$ generate $\M$. \end{proposition} \begin{proof} (From \cite{cremona1}.) Writing $\{\alpha,\beta\}=\{0,\beta\}-\{0,\alp\}$, it suffices to show that every symbol of the form $\{0,\alp\}$ is in the group generated by the $g.e$. Let $$\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}=\alp$$ denote the continued fraction convergents of the rational number $\alp$. Then $$p_j q_{j-1} - p_{j-1} q_j = (-1)^{j-1}\qquad \text{for }-1\leq j\leq r.$$ Hence $$\{0,\alp\} =\sum_{j=-1}^{r}\left\{\frac{p_{j-1}}{q_{j-1}},\frac{p_j}{q_j}\right\} = \sum_{j=-1}^{r}g_j.e$$ where $g_j = \mtwo{(-1)^{j-1}p_j}{p_{j-1}}{(-1)^{j-1}q_j}{q_{j-1}}$. \end{proof} To a pair $g\in\sltwoz$ and $P\in V_k$ define the {\em Manin symbol} $$[P,g]=g.(P\tensor e)\in\M_k(\Gamma).$$ The matrices $$\sigma=\mtwo{0}{-1}{1}{0}\quad \text{and} \quad \tau=\mtwo{0}{-1}{1}{-1}$$ satisfy $$\sigma^4=1,\,\,\tau^3=1$$ and generate $\sltwoz$. \begin{proposition}~\label{maninsymbols} Let $g\in\sltwoz$ and $P\in V_k$. The symbol $[P,g]$ depends only on $P$ and the class $\Gamma g$. When $g$ runs through $\sltwoz$ and $P$ runs through $V_k$, the Manin symbols generate $\M_k(\Gamma)$ ({\em maybe}, at least this should be true after tensoring with $\Q$). Furthermore, they satisfy \begin{eqnarray*} \mbox{}[P,g]+[\sigma^{-1}P,g\sigma]&=&0,\\ \mbox{}[P,g]+[\tau^{-1}P,g\tau]+[\tau^{-2}P,g\tau^2]&=&0, \\ \end{eqnarray*} \end{proposition} \begin{proof} The first assertion follows from the construction of $\M_k(\Gamma)$. The correct version of the second assertion (should somehow) follow from Lemma~\ref{maninstrick}. For the third assertion note the following relations: \begin{eqnarray*} e + \sigma(e) &=& \{0,\infty\} + \{\sigma(0),\sigma(\infty)\}\\ &=&\{0,\infty\}+\{\infty,0\}=0,\\ \\ e+\tau(e)+\tau^2(e) &=& \{0,\infty\} + \{\tau(0),\tau(\infty)\} + \{\tau^2(0),\tau^2(\infty)\}\\ &=& \{0,\infty\} + \{1,0\} + \{\infty,1\} = 0. \end{eqnarray*} Thus \begin{eqnarray*} \mbox{}[P,g]+[\sigma^{-1}P,g\sigma] &=& g(P\tensor e) + g\sigma(\sigma^{-1}P\tensor e)\\ &=& gP\tensor e + gP\tensor g\sigma e\\ &=& gP\tensor g(e+\sigma(e)) = 0,\\ \\ \mbox{}[P,g]+[\tau^{-1}P,g\tau]+[\tau^{-2}P,g\tau^2]&=& g(P\tensor e) + g\tau(\tau^{-1}P\tensor e) + g\tau^2(\tau^{-2}P\tensor e) \\ &=& gP\tensor g(e+\tau(e)+\tau^2(e)) = 0. \end{eqnarray*} \end{proof} \begin{theorem} The above relations generate all relations satisfied by the Manin symbols. (Maybe one must tensor with $\Q$.) \end{theorem} \begin{remark} Not only do not know whether or not this is true before tensoring with $\Q$, I do not know how to prove this. \end{remark} %Note that the relation $[P,g]=[j^{-1}P,gj]$ is imposed %by repeated application of the $\sigma$ relation because $\sigma^2=j$. The Manin symbol $[P,g]$ can be written as $\Z$-linear combinations of Manin symbols $$[X^q Y^{k-2-q},g],\quad \text{with } 0 \leq q \leq k-2.$$ Since $[\sltwoz:\Gamma]$ is finite, $\M_k(\Gamma)$ is a finitely generated abelian group. In particular, we can write down an explicit basis which is then readily amenable to machine computation. We write $[X^q Y^{k-2-q},g]=[q,g]$ to simplify notation. Let $g_1,\ldots,g_n$ be a set of coset representatives for $\Gamma$ in $\sltwoz$. Then $\M_k(\Gamma)$ is generated by $$\{[q,a_i] : 0\leq q\leq k-2, \, 1\leq i\leq n\}$$ subject to the relations given by Proposition~\ref{maninsymbols}. Note that $\M_k(\Gamma)$ may contain nontrivial torsion, which is not well understood (by me!). % what is the torsion? \subsection{Cuspidal modular symbols} \comment{ %About my paper "Universal...", there are a few mistakes there %(one reason other than my own fault, is the fact that that I never %saw the proofs). Some of them are insignificant. One you have to %be careful about is the fact that the parameterization of the cusps %of X_1(N) is wrong. It is easy to fix it anyway. One should replace %the set I called P_N by the disjoint union of the (Z/gcd(d,N)Z)^* where %d runs through Z/NZ. Then everything works mutatis mutandis. } In this section we assume $k$ is even. There is a similar definition when $k$ is odd. Let $\cD_0=\Div^0(\P^1(\Q))$ be the group of divisors of degree zero supported on $\P^1(\Q)$ and note that $\gltwoq$ acts on $\cD_0$ on the left by linear fractional transformations. Let $\cC(\Gamma)=H_0(\Gamma)=H_0(\Gamma,\cD_0)$ be the zeroth homology of $\Gamma\subset\sltwoz$ acting on $\cD_0=\Div^0(\P^1(\Q))$, so $H_0(\Gamma)$ is the free abelian group generated by the set of orbits $\Gamma\backslash P^1(\Q)$. It is the free abelian group on the cusps of the modular curve $X({\Gamma})$. There is a map $\M_k(\Gamma)\into\cC(\Gamma)$ which on Manin symbols is $$[P,g]\mapsto P(1,0)[g(\infty)]-P(0,1)[g(0)].$$ Let $\cS_k(\Gamma)$ be the kernel of this map. \subsection{Duality between modular symbols and modular forms} \subsubsection{Weight 2} The first homology group $H_1(X_{\Gamma},\Z)$ of the modular curve $X_{\Gamma}$, viewed as a real $2$-manifold, is a free abelian group of rank $2g$, where $g$ is the genus of $X_{\Gamma}$. The global differentials $\Omega(X) = H^0(X,\Omega)$ on $X_{\Gamma}$, now viewed as a Riemann surface, form a $g$ dimensional complex vector space. It is equal to the complex vector space $S_2(\Gamma)$ of cusp forms. There is a nondegenerate pairing \begin{eqnarray*} H_1(X_{\Gamma},\Z)\tensor \Omega(X)&\ra& \C\\ \langle \gamma, \omega \rangle &\mapsto& \int_{\gamma} \omega. \end{eqnarray*} Taking coefficients in $\R$ we have $$H_1(X_{\Gamma},\R)=H_1(X_{\Gamma},\Z)\tensor\R.$$ Extending the above pairing gives a natural injection of $H_1(X_{\Gamma},\R)$ into the dual space of $\Omega(X)$. Since the two spaces have the same real dimension, this injection must be an isomorphism. Suppose now that $k=2$. We can identify modular symbols $\{\alp,\beta\}$ for $\Gamma$ as elements of $H_1(X_{\Gamma},\R)$, and we have the formula, $$\langle \{\alp,\beta\}, \omega\rangle = \int_{\alp}^{\beta} \omega.$$ In fact, modular symbols were first introduced in this way by Birch in \cite{birch} in his work with Swinnerton-Dyer on the special value at $s=1$ of the $L$-function associated to a (modular) elliptic curve. \subsubsection{Higher weight} The duality generalizes to higher weight. Let $f:\h\into\C$ be a map. For $g=\abcd{a}{b}{c}{d}\in\gltwoq$ and $z\in\h$, define \begin{eqnarray*} f|[g]_k(z)&=&(cz+d)^{-k} f(gz)(\det g)^{k-1}\\ f|[\overline{g}]_k(z)&=&(c\overline{z}+d)^{-k} f(gz)(\det g)^{k-1} \end{eqnarray*} We denote by $S_k(\Gamma)$ (resp. $\overline{S_k(\Gamma)}$) the complex vector space of holomorphic (resp. antiholomorphic) cusp forms of weight $k$ for $\Gamma$. There is a canonical isomorphism of real vector spaces between $S_k(\Gamma)$ and $\overline{S_k(\Gamma)}$ which associates to $f$ the antiholomorphic modular form $z\mapsto \overline{f(z)}$. There is a pairing $$(S_k(\Gamma)\oplus \overline{S_k(\Gamma)})\cross \M_k(\Gamma)\into\C$$ given by the rule $$\langle f_1+f_2,P\tensor\{\alpha,\beta\}\rangle = \int_{\alp}^{\beta} f_1(z)P(z,1)dz + \int_{\alp}^{\beta} f_2(z)P(\overline{z},1)dz $$ where $f_1\in S_k(\Gamma)$ and $f_2\in \overline{S_k(\Gamma)}$. \begin{theorem}~\label{pairing} The following pairing, obtained from the above one, is nondegenerate: $$(S_k(\Gamma)\oplus\overline{S_k(\Gamma)})\cross \cS_k(\Gamma) \into \C.$$ \end{theorem} \subsection{Complex conjugation} Let $\eta=\abcd{-1}{0}{0}{1}$ and $\tilde{\eta}=\abcd{1}{0}{0}{-1}$. Assume in this section that $\eta^{-1}\Gamma\eta=\Gamma$. \begin{proposition} The map $\iota$ which associates to $f\in S_k(\Gamma)\oplus\overline{ S_k(\Gamma)}$ the function $z\mapsto f(-\overline{z})$ is a complex linear involution of $S_k(\Gamma)\oplus\overline{ S_k(\Gamma)}$ which exchanges $S_k(\Gamma)$ and $\overline{ S_k(\Gamma)}$. \end{proposition} Define an involution $\iota^{\star}$ on $\M_k(\Gamma)$ by $$\iota^{\star}(P\tensor x)= -\tilde{\eta}P\tensor\eta x.$$ This involution is adjoint to $\iota$ with respect to the pairing of Theorem~\ref{pairing}. Moreover $\iota^{\star}$ acts as follows on Manin symbols $$\iota^{\star}([P,g]) = -[\tilde{\eta}P,\eta g \eta^{-1}].$$ Let $\cS_k(\Gamma)^{+}$ denote the subspace of elements of $\cS_k(\Gamma)$ fixed by $\iota^{\star}$. \begin{proposition} The bilinear pairing induced by the pairing $\langle . , . \rangle$ $$S_k(\Gamma)\cross \cS_k(\Gamma)^{+}\into\C$$ is nondegenerate. \end{proposition} \subsection{Eichler-Shimura} Eichler and Shimura found a way to embed modular forms into a cohomology group. There is also a way to embed modular symbols into the same cohomology group. The complex vector space $V_k\tensor_{\Gamma} \sltwoz$ is endowed with a {\em right} action of $\sltwoz$ given by the formula $$(P\tensor g).\gamma = (\gamma^{-1}P)\tensor (g\gamma).$$ \begin{proposition} We have an isomorphism of complex vector spaces $$H^1(\sltwoz,V_k\tensor_{\Gamma} \sltwoz\tensor\C)\isom\M_k(\Gamma)\tensor\C.$$ \end{proposition} \begin{proof} This is Proposition 9 of \cite{merel}. The proof involves explicit computations with cocycles using the fact that $\sltwoz$ is generated by $\sigma$ and $\tau$. \end{proof} \begin{remark} It might be possible to replace tensoring with $\C$ by something less severe. \end{remark} \begin{lemma}[Shapiro] Let $H$ be a subgroup of a group $G$ and let $A$ be a $\Z[H]$-module. Then $$H^q(G,\Hom_H(\Z[G],A))=H^q(H,A)\qquad\text{for all $q\geq 0$}.$$ \end{lemma} \begin{corollary} There is an isomorphism $$\M_k(\Gamma)\tensor\C \isom H^1(\Gamma, V_k\tensor\C).$$ \end{corollary} \begin{proof} Since $\Gamma$ has finite index in $\sltwoz$ there is an isomorphism $$\Hom_{\Gamma}(\Z[\sltwoz],V_k\tensor\C) \isom V_k\tensor_{\Gamma} \sltwoz\tensor\C.$$ Now apply Shapiro's lemma. \end{proof} Define the {\em parabolic} cohomology group $H^1_P$ by the exactness of the following sequence $$0\into H^1_P(\Gamma,V_k\tensor \C) \into H^1(\Gamma,V_k\tensor\C) \into \bigoplus_{\text{cusps $\alp$}} H^1(\Gamma_{\alp},V_k\tensor\C)$$ where $\Gamma_{\alp}$ is the stabilizer in $\Gamma$ of the cusp $\alp$ of $X_{\Gamma}$. For $f\in M_k(\Gamma)$ define a class in $H^1(\Gamma,V_k\tensor\C)$ by the cocycle $$\gamma\mapsto \int_{z_0}^{\gamma(z_0)} f(z) \binom{z}{1}^{k-2}dz.$$ Here $z_0$ is a basepoint, $v^{k-2}$ denotes the image of $v\tensor\cdots\tensor v$ in $\Sym^{k-2}(\C\cross\C)$ and the integral is that of a vector-valued differential. There is a similiar construction for holomorphic differentials. \begin{theorem}[Eichler-Shimura] The map above gives rise to isomorphisms \begin{eqnarray*} M_k(\Gamma)\oplus\overline{S_k(\Gamma)}&\into &H^1(\Gamma,V_k\tensor \C)\\ S_k(\Gamma)\oplus\overline{S_k(\Gamma)}&\into &H^1_P(\Gamma,V_k\tensor \C). \end{eqnarray*} \end{theorem} %\subsection{Characters} % put Hijikata trace formula for the case $N=1$ here. \section{Linear maps} \subsection{Linear operators} Let $\Delta\subset\mtwoz$ such that $\Gamma\Delta\Gamma=\Delta$ and such that $\Gamma\backslash\Delta$ is finite. Note that $\Delta$ is a union of double cosets of $\Gamma\backslash\mtwoz/\Gamma$. Let $R$ be a set of representatives of $\Gamma\backslash\Delta$. \comment{ Two examples are $\Gamma=\Gamma_1(N)$ with $$\Delta = \Delta_1(N) = \{\abcd{a}{b}{c}{d}\in M_2(\Z) : \det > 0, \,\,c\con a-1\con 0\pmod {N}\},$$ and $\Gamma=\Gamma_0(N)$ with $$\Delta = \Delta_0(N) = \{\abcd{a}{b}{c}{d}\in M_2(\Z) : \det > 0,\,\, c\con 0\pmod {N}, \,(a,N)=1\}.$$ Define the {\em Hecke ring} $R(\Gamma,\Delta)$ as follows. It is the free $\Z$-module generated by the double cosets $\Gamma\alp\Gamma$, $\alp\in\Delta$. Define multiplication between two double cosets $u=\Gamma\alp\Gamma$ and $v=\Gamma\beta\Gamma$ as follows. Consider their coset decompositions $\Gamma\alp\Gamma = \coprod_{i}\Gamma\alpha_i$ and $\Gamma\beta\Gamma = \coprod_{i}\Gamma\beta_i$. Then $\Gamma\alp\Gamma\beta\Gamma=\union_{i,j}\Gamma\alp_i\beta_j$ (not necessarily disjoint), and so $\Gamma\alp\Gamma\beta\Gamma$ is a finite union of double cosets of the form $\Gamma\gamma\Gamma$. Define $$u\cdot v = \sum_{w} m(u,v;w)w$$ where the sum is extended over all double cosets $w=\Gamma\gamma\Gamma\subset\Gamma\alp\Gamma\beta\Gamma$, and $$m(u,v;w)=\#\{(i,j) : \Gamma\alp_i\beta_j = \Gamma\gamma\}$$ for $w=\Gamma\gamma\Gamma$. Thus equipped, $R(\Gamma,\Delta)$ becomes an associate, and in fact commutative, ring with $\Gamma=\Gamma\cdot 1\cdot\Gamma$ as the unit element. } \subsubsection{Action on modular forms} Let $M_k(\Gamma)$ be the space of modular forms of weight $k$ for $\Gamma$. For $f\in M_k(\Gamma)$, define an operator $T_{\Delta}$ by $$T_\Delta(f) = \sum_{\alp\in R} f|[\alp]_k$$ This is a well-defined linear action on $M_k(\Gamma)$ which preserves the subspace $S_k(\Gamma)$. \subsubsection{Action on modular symbols} Similiarly, define an operator $T_{\Delta}$ on the space $\M_k(\Gamma)$ of modular symbols by $$T_\Delta(x) = \sum_{\alp\in R} \alp.x.$$ \subsubsection{Hecke operators} Suppose now that $\Gamma=\Gamma_1(N)$. Let $n\geq 1$ be an integer and set $$\Delta_n=\{\abcd{a}{b}{c}{d}\in M_2(\Z) : \det = n,\,N|c,\, N|(a-1)\}.$$ Then the $n$th {\em Hecke operator} is $T_{\Delta_n}$. If $\Gamma=\Gamma_0(N)$ the condition that $N|(a-1)$ is relaxed to $(N,a)=1$. \subsection{Action on Manin symbols} We now describe how to explicitely compute the action of the Hecke operators on $\M_k(\Gamma)$. Recall, we have an explicit ``generators and relations'' description of $\M_k(\Gamma)$ in terms of Manin symbols. The action of the Hecke operators (and other linear operators) described in the previous section is given in terms of modular symbols. We {\em could} describe the action of an operator on a Manin symbol by taking the Manin symbol, finding the corresponding modular symbol, acting by the operator, and then converting back to a sum of Manin symbols. This process is painfully inefficient as it involves repeated application of Proposition~\ref{maninstrick}. This was how computations were originally done until Mazur and Merel described the action of the Hecke operators directly in terms of Manin symbols. Let $n>0$ be an integer. We denote by $\mtwoz_n$ the set of matrices of $\mtwoz$ of determinant $n$. \begin{definition}[Condition (M)] We say that an element $\sum_{g} a_g g\in\C[\mtwoz_n]$ satisfies condition (M) if for all cosets $\cC\in \mtwoz_n/\sltwoz$, we have in $\C[\P^1(\Q)]$, $$\sum_{g\in \cC} a_g ([g(\infty)] - [g(0)]) = [\infty]-[0].$$ \end{definition} Note that the condition (M) depends neither on the level or the weight. Suppose now that $\Gamma=\Gamma_1(N)$ (or $\Gamma_0(N)$). There is a bijection between cosets $\Gamma\backslash\sltwoz$ and pairs of integers $(u,v)$ satisfying a certain equivalence. The bijection associates to a $2\times 2$ matrix its bottom two entries. We may thus view the Manin symbols as pairs $[P,(u,v)]$. \begin{theorem}[Merel] Let $[P,(u,v)]$ be a Manin symbol. Suppose $\sum_{g} a_g g\in\C[\mtwoz_n]$ satisfies condition (M). Then we have $$T_n([P(X,Y),(u,v)]) = \sum_{g=\abcd{a}{b}{c}{d}\in\mtwoz_n} a_g [P(aX+bY,cX+dY),(au+cv,bu+dv)]$$ where the sum is restricted to the matrices $g$ such that $\gcd(au+cv,bu+dv)=1$ (if $(n,N)=1$ this restriction is unnecessary). \end{theorem} \begin{proof} See section 2 of \cite{merel}. \end{proof} The element $\sum_{g \in\mtwoz_n} g \in \C[\mtwoz_n]$ satisfies condition (M). In Merel's paper one can find other families of simpler (more sparse) elements satisfying condition (M). \comment{ For one of the families $S_n$ there is an asymptotic formula for the number $|S_n|$ of nonzero summands: $$|S_n| \sim \frac{12\log 2}{\pi^2} \sigma(n)\log n, \quad\text{as $n\ra\infty$}$$ where $\sigma(n)$ is the sum of the positive divisors of $n$. Let $s(n)$ be the right hand side, rounded down to the nearest integer. Then $$s(10)=34,\quad s(100)=842,\quad s(250)=2177,\quad s(500)=5719,\quad s(1000)=13622.$$ Finding a family minimizing these numbers is extremely important in computing many Hecke eigenvalues. \begin{remark} Cremona has improved on this slightly to give even simpler elements $\mathcal{X}_n\in\C[\mtwoz_n]$ which can be used to compute the Hecke action, but which I don't think satisfies condition (M). He proves this in his book for weight $2$, but I think his elements work for any positive weight. \end{remark} } %\subsection{Atkin-Lehner operators} %\subsection{Newforms} \comment{ \subsection{Characters} Let $N$ be a positive integer and let $\chi:(\Z/N\Z)^{\star}\into\C^{\star}$ be a character. Let $\Z[\chi]=\Z[\chi(\Z/N\Z)^{\star}]$. Define $\M_k(N,\chi)$ to be the quotient of $\M_k(\Gamma_1(N))\tensor\Z[\chi]$ by the equivalence relation which identifies the Manin symbol $[P,(\lambda u,\lambda v)]$ with $\chi(\lambda)[P,(u,v)]$. Define $\S_k(N,\chi)\subset \M_k(N,\chi)$. \begin{proposition} The pairing $$(S_k(N,\chi)\sum\overline{ S_k(N,\chi)} \cross \cS_k(N,\chi)\into \C$$ is nondegenerate. \end{proposition} Thus the space $\S_k(N,\chi)\tensor\C$ obtained from modular symbols is related to the cusp forms $S_k(N,\chi)$. } \comment{ \section{Computation} \subsection{Coset representatives~\label{cosetrep}} \begin{proposition} For $j=1,2$, let $g_j=\abcd{a_j}{b_j}{c_j}{d_j}\in\sltwoz$. The following are equivalent. \begin{enumerate} \item The right cosets $\Gamma_0(N)g_1$ and $\Gamma_0(N) g_2$ are equal, \item $c_1d_2\con c_2 d_1\pmod{N}$, \item There exists $u\in(\Z/N\Z)^{\star}$ such that $c_1\con u c_2$ and $d_1\con u d_2$ $\pmod{N}$. \end{enumerate} \end{proposition} \begin{proof} Proposition 2.2.1 of \cite{cremona1}. \end{proof} \begin{proposition} For $j=1,2$, let $\alp_j=p_j/q_j$ be cusps written in lowest terms. The following are equivalent: \begin{enumerate} \item $\alp_2=g\alp_1$ for some $g\in\Gamma_0(N)$, \item $q_2\con u q_1\pmod{N}$ and $up_2\con p_1\pmod{\gcd(q_1,N)}$, with $\gcd(u,N)=1$, \item $s_1 q_2\con s_2 q_1\pmod{gcd(q_1 q_2,N)}$, where $s_j$ satisfies $p_j s_j \con 1\pmod {q_j}$. \end{enumerate} \end{proposition} \begin{proof} Proposition 2.2.3 of \cite{cremona1}. \end{proof} } %\subsection{Cusp equivalence} %\subsection{Newforms} %\subsection{Computing Hecke eigenvalues} %\subsection{Computing $L^{(r)}(f,1)$} %\section{Computing in characteristic $p$} %\section{Equations for modular curves} %\section{Congruences between newforms} %\section{$\Spec(\T)$} %\section{Implimentation} %\subsection{Coset representatives} %\subsection{Linear algebra} %\subsection{Complexity} %\section{Examples} %\subsection{Level $37$} %\subsection{$X_0(389)$} \section{Generating $H_1(\Gamma,\Z)$} How can we generate $H_1(\Gamma,\Z)$ using modular symbols? \begin{theorem} Choose any $\alp\in\Q\union\{\infty\}$, it doesn't matter which. Then the map $$\Gamma\ra H_1(\Gamma,\Z): \quad \gamma\mapsto\{\alp,\gamma(\alp)\}$$ is a surjective group homomorphism. \end{theorem} So, knowing generators for $\Gamma$ would be enough. Now specialize to the case $\Gamma=\Gamma_0(N)$. Here is one guess for what {\em might} be true. \begin{question} Do the Manin symbols $(c,d)$ with $(c,N)=(d,N)=1$ generate $H_1(X_0(N),\Z)$? \end{question} When $N$ is prime those Manin symbols lie in $H_1(X_0(N),\Z)$ because they correspond to paths from the non-$\infty$ cusp to itself. Let $(c,d)$ be such a Manin symbol and choose $a,b$ so that $M=\abcd{a}{b}{c}{d}\in\sltwoz$. Then the Modular symbol corresponding to $(c,d)$ is $M.\e=M.\{0,\infty\}=\{M(0),M(\infty)\}$. Since $c$ and $d$ are both coprime to $N$, the cusps $[\frac{a}{c}]$ and $[\frac{b}{d}]$ are the same (remember, we are assuming $N$ is prime so that there are only two cusps). The only other way to force the cusps to be the same would be to force $b$ and $d$ to both be divisible by $N$, but then $(c,d)$ would not be a Manin symbol. I do not know if these Manin symbols are enough to generate all integral modular symbols. But, we can set up some computer computations to get an idea of whether or not we should expect this. {\bf Computation 1.} Let $H=H_1(X_0(N),\Z)$. Let $V$ be the submodule of $H$ generated by the modular symbols $\{\infty,\gamma(\infty)\}$ where $\gamma=\abcd{a}{b}{N}{d}$ and $0<a<N$. Let $W$ be the submodule of $H_1(X_0(N),\Q)$ generated by the Manin symbols $(c,d)$ for which both $c$ and $d$ are coprime to $N$. If things were as easy as imaginable then both $V$ and $W$ would be equal to $H$ (and to each other). If $W$ is properly contained in $V$ then we learn that the answer to the question is {\em NO}. In the prime case, if $V$ is properly contained in $W$ we learn that $V$ does not generate $H$, which is also interesting. We compute $V$ and $W$ for $11\leq N\leq 100$, and the module index $[V:W]$. Whenever there is a - for the index, this means that that {\em neither} $V$ nor $W$ span $H_1(X_0(N),\Q)$ over $\Q$. In these cases we didn't compute the actual index. \begin{center} \begin{tabular}{|c|c|}\hline $N$&$[W:V]$\\ \hline 11 & 1\\ 14 & 1\\ 15 & 1\\ 17 & 1\\ 19 & 1\\ 20 & 1\\ 21 & 1\\ 22 & 1\\ 23 & 1\\ 24 & 1\\ 26 & 1\\ 27 & 1\\ 28 & 1\\ 29 & 1\\ 30 & -\\ 31 & 1\\ 32 & 1\\ 33 & 1\\ 34 & 1\\ 35 & 1\\ 37 & 1\\ 38 & 1\\ 39 & 1\\ 41 & 1\\ 42 & -\\ 43 & 1\\ 44 & 1\\ 45 & 1\\ 46 & 1\\ 47 & 1\\ 48 & -\\ 49 & 1\\ 50 & 1\\ 51 & 1\\ 52 & 1\\ 53 & 1\\ 54 & -\\ 55 & 1\\ 56 & -\\ 57 & 1\\ 58 & 1\\ 59 & 1\\ 60 & -\\ 61 & 1\\ 62 & 1\\ \hline \end{tabular} \begin{tabular}{|c|c|}\hline $N$&$[W:V]$\\ \hline 63 & 1\\ 64 & 1\\ 65 & 1\\ 66 & -\\ 67 & 1\\ 68 & 1\\ 69 & 1\\ 70 & -\\ 71 & 1\\ 72 & -\\ 73 & 1\\ 74 & 1\\ 75 & 1\\ 76 & 1\\ 77 & 1\\ 78 & -\\ 79 & 1\\ 80 & -\\ 81 & 1\\ 82 & 1\\ 83 & 1\\ 84 & -\\ 85 & 1\\ 86 & 1\\ 87 & 1\\ 88 & -\\ 89 & 1\\ 90 & -\\ 91 & 1\\ 92 & 1\\ 93 & 1\\ 94 & 1\\ 95 & 1\\ 96 & -\\ 97 & 1\\ 98 & 1\\ 99 & 1\\ 100 & -\\ 101 & 1\\ 102 & -\\ 103 & 1\\ 104 & -\\ 105 & -\\ 106 & 1\\ 107 & 1\\ \hline \end{tabular} \begin{tabular}{|c|c|}\hline $N$&$[W:V]$\\ \hline 108 & -\\ 109 & 1\\ 110 & -\\ 111 & 1\\ 112 & -\\ 113 & 1\\ 114 & -\\ 115 & 1\\ 116 & 1\\ 117 & 1\\ 118 & 1\\ 119 & 1\\ 120 & -\\ 121 & 1\\ 122 & 1\\ 123 & 1\\ 124 & 1\\ 125 & 1\\ 126 & -\\ 127 & 1\\ 128 & 1\\ 129 & 1\\ 130 & -\\ 131 & 1\\ 132 & -\\ 133 & 1\\ 134 & 1\\ 135 & -\\ 136 & -\\ 137 & 1\\ 138 & -\\ 139 & 1\\ 140 & -\\ 141 & 1\\ 142 & 1\\ 143 & 1\\ 144 & -\\ 145 & 1\\ 146 & 1\\ 147 & 1\\ 148 & 1\\ 149 & 1\\ 150 & -\\ 151 & 1\\ 152 & -\\ \hline \end{tabular} \begin{tabular}{|c|c|}\hline $N$&$[W:V]$\\ \hline 153 & 1\\ 154 & -\\ 155 & 1\\ 156 & -\\ 157 & 1\\ 158 & 1\\ 159 & 1\\ 160 & -\\ 161 & 1\\ 162 & -\\ 163 & 1\\ 164 & 1\\ 165 & -\\ 166 & 1\\ 167 & 1\\ 168 & -\\ 169 & 1\\ 170 & -\\ 171 & 1\\ 172 & 1\\ 173 & 1\\ 174 & -\\ 175 & 1\\ 176 & -\\ 177 & 1\\ 178 & 1\\ 179 & 1\\ 180 & -\\ 181 & 1\\ 182 & -\\ 183 & 1\\ 184 & -\\ 185 & 1\\ 186 & -\\ 187 & 1\\ 188 & 1\\ 189 & -\\ 190 & -\\ 191 & 1\\ 192 & -\\ 193 & 1\\ 194 & 1\\ 195 & -\\ 196 & -\\ 197 & 1\\ \hline \end{tabular} \end{center} {\bf Conclusion:} Neither obvious set of elements of $H_1(X_0(N),\Z)$ will, in general, generate. It might be necessary to look at \begin{verbatim} R. S. Kulkarni, An arithmetic-geometry method of the study of the subgroups of the modular group, American Journal of mathematics 113, 1991, 1053-1133 \end{verbatim} and find explicit generators. \begin{thebibliography}{HHHHHHH} \bibitem[B]{birch} B. Birch, {\em Elliptic curves, a progress report,} AMS conference on number theory, Stonybrook (1969), 396--400. \bibitem[CR1]{cremona1} J.E. Cremona, {\em Algorithms for modular elliptic curves, 2nd edition}, Cambridge University Press, (1997). \bibitem[CR2]{cremona2} J.E. Cremona, {\em Modular symbols for $\Gamma_1(N)$ and elliptic curves with everywhere good reduction}, Math. Proc. Camb. Phil. Soc. {\bf 111} (1992), 199--218. \bibitem[HJ]{hijikata} H. Hijikata, {\em Explicit formula of the traces of Hecke operators for $\Gamma_0(N)$}, J. Math. Soc. Japan. {\bf 26} (1974), 56--82. \bibitem[K]{kohel} D. Kohel, {\em Hecke module structure of quaternions}, (1998), preprint. \bibitem[M]{merel} L. Merel, {\em Universal fourier expansions of modular forms}, Springer L.N.M. 1585, (1994). \bibitem[M1]{mestre} J.F. Mestre, {\em La m\'{e}thode des graphs. Exemples et applications}, Taniguchi Symp., Proceedings of the international conference on class numbers and fundamental units of algebraic number fields (Katata, 1986), 217--242, Nagoya Univ., Nagoya, 1986. \bibitem[P]{pizer} A. Pizer, {\em An algorithm for computing modular forms on $\Gamma_0(N)$}, Journal of Algebra {\bf 64} (1980), 340--390. \bibitem[S]{stein} W. Stein, {\em Modular forms database}, {\tt http://boole.berkeley.edu/\~{\mbox{}}was/Tables}. \bibitem[ST1]{steven1} G. Stevens, {\em Rigid analytic modular symbols}, (preprint). \bibitem[WA]{wada} H. Wada, {\em A table of Hecke operators. II}, Proc. Japan Acad., {\bf 49} (1973), 380--384. \bibitem[W1]{wang1} X. Wang, {\em The hecke algebra on the cohomology of $\Gamma_0(p_0)$}, Nagoya Math. J., {\bf 121} (1991), 97--125. \bibitem[W1]{wang2} X. Wang, {\em The hecke operators on $S_k(\Gamma_1(N))$}, J. Symbolic Computation, {\bf 18} (1994), 187--198. \end{thebibliography} \end{document}