%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % MSRI intro workshop paper: Computing modular forms using modular symbols % % % % William Stein, 2000 % % % % latex msri-intro.tex % % latex msri-intro.tex % % dvips -f < msri-intro.dvi > msri-intro.ps % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentclass{article} \usepackage{amsfonts} \usepackage{amsmath} \usepackage{amssymb} \usepackage{amsthm} \usepackage[all]{xy} \usepackage{graphicx} \usepackage{psfrag} \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}{Proposition}[section] \theoremstyle{remark} \newtheorem{example}[theorem]{Example} \newcommand{\abcd}[4]{\left( \begin{smallmatrix}#1\\#3\end{smallmatrix}\right)} \newcommand{\C}{\mathbf{C}} \newcommand{\cross}{\times} \newcommand{\F}{\mathbf{F}} \newcommand{\GL}{{\rm GL}} \newcommand{\h}{\mathfrak{h}} \newcommand{\isom}{\cong} \newcommand{\mtwo}[4]{\left( \begin{matrix}#1\\#3\end{matrix}\right)} \newcommand{\mthree}[9]{\left( \begin{matrix}#1\\#4\\#7 \end{matrix}\right)} \DeclareMathOperator{\new}{new} \renewcommand{\P}{\mathbf{P}} \newcommand{\Q}{\mathbf{Q}} \newcommand{\ra}{\rightarrow} \newcommand{\SL}{{\rm SL}} \newcommand{\sB}{\pmb{\mathcal{B}}} \newcommand{\sM}{\pmb{\mathcal{M}}} \newcommand{\sS}{\pmb{\mathcal{S}}} %\DeclareMathOperator{\sM}{ModSym} %\DeclareMathOperator{\sS}{CuspSym} \newcommand{\T}{\mathbf{T}} \newcommand{\union}{\cup} \newcommand{\Z}{\mathbf{Z}} \newcommand{\defn}{\em} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Silvio Levy's suggestions % %4. FIGURES: %All figures should be supplied in electronic form; we won't reproduce %figures from hard copy. Acceptable formats are Postscript (PS) and %any format that can be converted to PS in an automated way -- %Maple, Mathematica, Illustrator, gnuplot, etc. %PLEASE SUPPLY CAPTIONS FOR ALL THE FIGURES (except inline diagrams). % %5. BIBLIOGRAPHICAL REFERENCES %We use bibtex. If easy for you, please supply bibtex entries. If not, % %PLEASE DON'T INSERT FORCED LINE BREAKS OR PAGE BREAKS IN YOUR DOCUMENT! %Don't worry about fine-tuning the formatting. % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \vspace{10ex} \begin{center} \par\noindent {\sc \LARGE An introduction to computing\vspace{1ex}\\ modular forms using modular symbols}\\ \vspace{3ex} \large\bf William A. Stein \end{center} \vspace{3ex} \par\noindent Harvard University\\ Cambridge, MA 02138\\ {\sf was@math.harvard.edu}\\ {\sf http://modular.fas.harvard.edu} \vspace{1ex}\\ \vspace{2ex}\par \begin{abstract} In this survey paper, we explain how weight~$2$ modular forms on $\Gamma_0(N)$ are related to modular symbols, and how to use this relationship to explicitly compute spaces of modular forms. \end{abstract} \section*{Introduction} The definition of spaces of modular forms as functions on the upper half plane satisfying a certain equation is very abstract. The definition of the Hecke operators even more so. Nevertheless, one wishes to carry out explicit investigations involving these objects. We are fortunate that we now have methods available that allow us to transform the vector space of cusp forms of given weight and level into a concrete object, which can be explicitly computed. We have the work of Atkin and Lehner, Birch and Swinnerton-Dyer, Manin, Mazur, Merel, and many others to thank for this (see, e.g., \cite{antwerpiv, cremona:algs, mazur:symboles, merel:1585}). For example, we can use the Eichler-Selberg trace formula, as extended in \cite{hijikata:trace}, to compute characteristic polynomials of Hecke operators. Then the method described in \cite{wada1} gives a basis for certain spaces of modular forms. Alternatively, we can compute $\Theta$-series using Brandt matrices and quaternion algebras as in \cite{kohel:hecke, pizer:alg}, or we can use a closely related geometric method that involves the module of enhanced supersingular elliptic curves~\cite{mestre:graphs}. Another related method of Birch~\cite{birch:hecke_actions} is very fast, but gives only a piece of the full space of modular forms. The power of the modular symbols approach was demonstrated by Cremona in his book~\cite{cremona:algs} in which he systematically computes a large table of invariants of all elliptic curves of conductor up to $1000$ (his online tables go much further). Though the above methods are each beautiful and well suited to certain applications, we will only discuss the modular symbols method in this paper, as it has many advantages. We will primarily discuss the theory, leaving an explicit description of the objects involved for other papers. Nonetheless, there is a definite gap between the theory on the one hand, and an efficient running machine implementation on the other. To implement the algorithms hinted at below requires making absolutely everything completely explicit, 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. Fortunately, Cremona has succeeded at this in his book~\cite{cremona:algs}. See also the author's {\sc Magma}~\cite{magma} package for working with modular symbols, which is part of {\sc Magma} V2.7 (and higher), and would be useful to experiment with while reading this paper. In this paper we will focus exclusively on the case of weight-$2$ modular forms for $\Gamma_0(N)$. The methods explained here extend to modular forms of integer weight greater than~$2$ for $\Gamma_1(N)$ (nontrivial character); for more details see \cite{merel:1585} for the theory and \cite{stein:phd} for the algorithms (see also \cite{stein-verrill:transportable}). Section~\ref{sec:modformhecke} contains a brief summary of basic facts about modular forms, Hecke operators, and integral homology. Section~\ref{sec:modsym} introduces modular symbols, and describes how to compute with them. Section~\ref{sec:computingmodform} outlines an algorithm for constructing cusp forms using modular symbols in conjunction with Atkin-Lehner theory. This paper assumes some familiarity with algebraic curves, Riemann surfaces, and homology groups of compact surfaces. A few basic facts about modular forms are recalled, but only briefly. In particular, only a roundabout attempt is made to motivate why one might be interested in modular forms; for this, see, e.g., \cite{antwerpiv, cremona:algs, diamond-im, kohel:hecke, ribet-stein:serre, stein:vissha}. No prior exposure to modular symbols is assumed. \vspace{1ex}{\bf Acknowledgment.} The author would like to thank Mark Watkins and Lynn Walling for many helpful comments. \section{Modular forms and Hecke operators} \label{sec:modformhecke} The objects we will consider arise from the modular group $\SL_2(\Z)$ of two-by-two integer matrices with determinant equal to one. This group acts via linear fractional transformations on the complex upper half plane~$\h$, and also on the extended upper half plane $$\h^* = \h \union \P^1(\Q) = \h \union \Q \union \{\infty\}.$$ See \cite[\S1.3--1.5]{shimura:intro} for a careful description of the topology on~$\h^*$. A basis of neighborhoods for $\alpha\in\Q$ is given by the sets $\{\alpha\}\union D$, where~$D$ is a disc in~$\h$ that is tangent to the real line at~$\alpha$. Let~$N$ be a positive integer and consider the group $\Gamma_0(N)$ of matrices $\abcd{a}{b}{c}{d}\in\SL_2(\Z)$ such that $N\mid c$. The group $\Gamma_0(N)$ acts on $\h^*$ by linear fractional transformations, and the quotient $\Gamma_0(N)\backslash \h^*$ is a Riemann surface, which we denote by $X_0(N)$. Shimura showed in \cite[\S6.7]{shimura:intro} that $X_0(N)$ has a canonical structure of algebraic curve over~$\Q$. A {\defn cusp form} is a function~$f$ on~$\h$ such that $f(z)dz$ is a holomorphic differential on $X_0(N)$. Equivalently, a cusp form is a holomorphic function~$f$ on $\h$ such that \begin{itemize} \item[(a)] the expression $f(z)dz$ is invariant under replacing~$z$ by $\gamma(z)$ for each $\gamma\in \Gamma_0(N)$, and \item[(b)] $f(z)$ is holomorphic at each element of $\P^1(\Q)$, and moreover $f(z)$ tends to~$0$ as~$z$ tends to any element of $\P^1(\Q)$. \end{itemize} The space of cusp forms on $\Gamma_0(N)$ is a finite dimensional complex vector space, of dimension equal to the genus~$g$ of $X_0(N)$. Viewed topologically, as a $2$-dimensional real manifold, $X_0(N)(\C)$ is a $g$-holed torus. Condition (b) in the definition of $f(z)$ means that $f(z)$ has a Fourier expansion about each element of $\P^1(\Q)$. Thus, at~$\infty$ we have \begin{align*} f(z) &= a_1 e^{2\pi i z} + a_2 e^{2 \pi i 2z} + a_3 e^{2 \pi i 3z} + \cdots\\ &= a_1 q + a_2 q^2 + a_3 q^3 + \cdots, \end{align*} where, for brevity, we write $q=q(z)=e^{2\pi i z}$. \begin{example} Let~$E$ be the elliptic curve defined by the equation $y^2 + xy = x^3 + x^2 - 4x - 5$. For $p\neq 3,13$, let $a_p = p+1-\#\tilde{E}(\F_p)$, where~$\tilde{E}$ is the reduction of~$E$ mod~$p$, and let $a_3=-1$, $a_{13}=1$. For~$n$ composite, define $a_n$ using the relations at the end of Section~\ref{sec:computingmodform}. Then \begin{align*} f&=q + a_2 q^2 + a_3 q^3 + a_4 q^4 + a_5 q^5 + \cdots\\ &= q + q^2 - q^3 -q^4 + 2q^5 + \cdots \end{align*} is the $q$-expansion of a modular form on $\Gamma_0(39)$. The Shimura-Taniyama conjecture, which is now a theorem (see \cite{breuil-conrad-diamond-taylor}) asserts that any $q$-expansion constructed as above from an elliptic curve over~$\Q$ is a modular form. \end{example} The Hecke operators are a family of {\em commuting} endomorphisms of $S_2(N)$, which are defined as follows. The complex points of the open subcurve $Y_0(N)=\Gamma_0(N)\backslash \h$ are in bijection with pairs $(E,C)$, where~$E$ is an elliptic curve over~$\C$ and~$C$ is a cyclic subgroup of $E(\C)$ of order~$N$. If $p\nmid N$ then there are two natural maps $\pi_1$ and $\pi_2$ from $Y_0(pN)$ to $Y_0(N)$; the first, $\pi_1$, sends $(E,C)$ to $(E,C')$, where~$C'$ is the unique cyclic subgroup of~$C$ of order~$N$, and the second, $\pi_2$, sends a point $(E,C)\in Y_0(N)(\C)$ to $(E/D, C/D)$, where~$D$ is the unique cyclic subgroup of~$C$ of order~$p$. These maps extend in a unique way to maps from $X_0(pN)$ to $X_0(N)$: $$\xymatrix{ & X_0(pN) \ar[dl]_{\pi_2}\ar[dr]^{\pi_1}\\ X_0(N) & & X_0(N).}$$ The $p$th {\defn Hecke operator} $T_p$ is $(\pi_1)_* \circ (\pi_2)^*$; it acts on most objects attached to $X_0(N)$, such as divisors and cusp forms. There is a Hecke operator $T_n$ for every positive integer~$n$, but we will not need to consider those with~$n$ composite. \begin{example} There is a basis of $S_2(39)$ so that $$T_2 = \mthree{\hfill 1}{\hfill 1}{\hfill 0}{-2}{-3}{-2}{\hfill 0}{\hfill 0}{\hfill 1} \quad\text{and}\quad T_5 = \mthree{-4}{-2}{-6}{\hfill4}{\hfill4}{\hfill4}{\hfill0}{\hfill0}{\hfill2}.$$ Notice that these matrices commute, and that~$1$ is an eigenvalue of $T_2$, and~$2$ is an eigenvalue of $T_5$. \end{example} The first homology group $H_1(X_0(N),\Z)$ is the group of singular $1$-cycles modulo homology relations. Recall that topologically $X_0(N)$ is a $g$-holed torus, where~$g$ is the genus of $X_0(N)$. The group $H_1(X_0(N),\Z)$ is thus a free abelian group of rank $2g$ (see, e.g., \cite[Ex.~19.30]{greenberg-harper}), with two generators corresponding to each hole, as illustrated in the case $N=39$ in Figure~\ref{diagram:homology}. \begin{figure} \begin{center} \includegraphics[width=4in]{diagrams/torus39.eps} $$H_1(X_0(39),\Z) \isom \Z\cross\Z\cross\Z\cross\Z\cross\Z\cross\Z$$ \end{center} \caption{The homology of $X_0(39)$.\label{diagram:homology}} \end{figure} The Hecke operators $T_p$ act on $H_1(X_0(N),\Z)$, and integration defines a nondegenerate Hecke-equivariant pairing $$\langle\,,\,\rangle: S_2(N) \cross H_1(X_0(N),\Z) \ra \C.$$ Explicitly, for a path~$x$, $$\langle f , x \rangle = 2\pi i \int_{x} f(z) dz,$$ where the integral may be viewed as a complex line integral along an appropriate piece of the preimage of~$x$ in the upper half plane. The pairing is Hecke equivariant in the sense that for every prime~$p$, we have $\langle f T_p, x\rangle = \langle f, T_p x\rangle$. As we will see, modular symbols allow us to make explicit the action of the Hecke operators on $H_1(X_0(N),\Z)$; the above pairing then translates this into a wealth of information about cusp forms. For a more detailed survey of the basic facts about modular curves and modular forms, we urge the reader to consult Diamond and Im's excellent survey paper~\cite{diamond-im}. For a discussion of how to draw a picture of the ring generated by the Hecke operators, see~\cite[\S3.8]{ribet-stein:serre}. \section{Modular symbols}\label{sec:modsym} The modular symbols formalism provides a presentation of $H_1(X_0(N),\Z)$ in terms of paths between elements of $\P^1(\Q)$. Furthermore, a trick due to Manin gives an explicit finite list of generators and relations for the space of modular symbols. The {\defn modular symbol} defined by a pair $\alpha,\beta\in\P^1(\Q)$ is denoted $\{\alpha,\beta\}$. As illustrated in Figure~\ref{figure:modsym}, this modular symbol should be viewed as the homology class, relative to the cusps, of a geodesic path from~$\alpha$ to~$\beta$ in $\h^*$. The homology group relative to the cusps is a slight enlargement of the usual homology group, in that we allow paths with endpoints in $\P^1(\Q)$ instead of restricting to closed loops. \begin{figure} \psfrag{infinity}{$\infty$} \psfrag{alpha}{$\alpha$} \psfrag{beta}{$\beta$} \psfrag{0}{$0$} \psfrag{Q}{$\Q$} \begin{center} \includegraphics[height=2.5in]{diagrams/alpha-beta.eps} \end{center} \caption{The modular symbols $\{\alpha,\beta\}$ and $\{0,\infty\}$. \label{figure:modsym}} \end{figure} Motivated by this picture, we declare that modular symbols satisfy the following homology relations: if $\alpha,\beta,\gamma \in \Q\union\{\infty\}$, then $$\{\alpha,\beta\} + \{\beta,\gamma\} + \{\gamma,\alpha\} = 0.$$ Furthermore, the space of modular symbols is torsion free, so, e.g., $\{\alpha,\alpha\} = 0$ and $\{\alpha,\beta\} = -\{\beta,\alpha\}$. Denote by~$\sM_2$ the free abelian group with basis the set of symbols $\{\alpha,\beta\}$ modulo the three-term homology relations above and modulo any torsion. There is a left action of $\GL_2(\Q)$ on $\sM_2$, whereby a matrix~$g$ acts by $$g\{\alpha, \beta\} = \{g(\alpha), g(\beta)\},$$ and~$g$ acts on~$\alpha$ and~$\beta$ by a linear fractional transformation. The space $\sM_2(N)$ of {\defn modular symbols for $\Gamma_0(N)$} is the quotient of $\sM_2$ by the submodule generated by the infinitely many elements of the form $x - g(x)$, for~$x$ in ~$\sM_2$ and~$g$ in $\Gamma_0(N)$, and modulo any torsion. A {\defn modular symbol for $\Gamma_0(N)$} is an element of this space. We frequently denote the equivalence class that defines a modular symbol by giving a representative element. \begin{example}\label{ex:01} Since $\gamma=\abcd{1}{1}{0}{1}\in \Gamma_0(N)$, we have $\{\infty,0\} = \{\gamma(\infty),\gamma(0)\} = \{\infty,1\}.$ Thus $0 = \{\infty,1\}-\{\infty,0\} = \{\infty,1\} + \{0,\infty\} = \{0,\infty\} + \{\infty,1\} = \{0,1\}.$ \end{example} In \cite{manin:parabolic}, Manin proved that there is a natural injection $H_1(X_0(N),\Z)\hookrightarrow \sM_2(N)$. The image of $H_1(X_0(N),\Z)$ in $\sM_2(N)$ is as follows. Let $\sB_2(N)$ denote the free abelian group whose basis is the finite set $\Gamma_0(N)\backslash \P^1(\Q)$. The {\defn boundary map} $\delta: \sM_2(N)\ra \sB_2(N)$ sends $\{\alpha,\beta\}$ to $[\beta]-[\alpha]$, where $[\beta]$ denotes the basis element of $\sB_2(N)$ corresponding to $\beta\in\P^1(\Q)$. The kernel $\sS_2(N)$ of~$\delta$ is the subspace of {\defn cuspidal} modular symbols. An element of $\sS_2(N)$ can be thought of as a linear combination of paths in $\h^*$ whose endpoints are cusps, and whose images in $X_0(N)$ are a linear combination of loops. We thus obtain a map $\varphi:\sS_2(N)\ra H_1(X_0(N),\Z)$. \begin{theorem} The map~$\varphi$ given above defines a canonical isomorphism $$\sS_2(N) \isom H_1(X_0(N),\Z).$$ \end{theorem} \begin{example} We illustrate modular symbols in the case when $N=11$. Using, e.g., the author's package in \cite{magma}, one finds that $\sM_2(11)$ is the free abelian group of rank~$3$ generated by $\{-1/7,0\}$, $\{-1/5,0\}$, and $\{\infty,0\}$. The integral homology $H_1(X_0(N),\Z)$ corresponds to the abelian subgroup generated by $\{-1/7,0\}$ and $\{-1/5,0\}$. See \cite[Appendix to Ch.~II]{cremona:algs} for a more detailed description of the computation of $\sM_2(11)$. \end{example} \subsection{Manin's trick} In this section, we describe a trick of Manin that shows that the space of modular symbols can be computed. By reducing modulo~$N$, one sees that the group $\Gamma_0(N)$ has finite index in $\SL_2(\Z)$. Let $r_0, r_1, \ldots, r_m$ be distinct right coset representatives for $\Gamma_0(N)$ in $\SL_2(\Z)$, so that $$\SL_2(\Z) = \Gamma_0(N)r_o \, \union\, \Gamma_0(N)r_1 \, \union\, \cdots \, \union\, \Gamma_0(N)r_m,$$ where the union is disjoint. For example, when~$N$ is prime, a list of coset representatives is $$\mtwo{1}{0}{0}{1}, \mtwo{1}{0}{1}{1}, \mtwo{1}{0}{2}{1}, \mtwo{1}{0}{3}{1}, \ldots, \mtwo{\hfill 1}{0}{N-1}{1}, \mtwo{0}{-1}{1}{\hfill 0}.$$ In general, the right cosets of $\Gamma_0(N)$ in $\SL_2(\Z)$ are in bijection with the elements of $\P^1(\Z/N\Z)$, the bijection sending a coset representative $\abcd{a}{b}{c}{d}$ to the class of $(c:d)$ in $\P^1(\Z/N\Z)$ (see \cite[\S2.2]{cremona:algs} for complete details). The following trick of Manin (see \cite[\S1.5]{manin:parabolic} and \cite[\S2.1.6]{cremona:algs}) allows us to write every modular symbol as a $\Z$-linear combination of symbols of the form $r_i\{0,\infty\}$. In particular, the finitely many symbols $r_i\{0,\infty\}$ generate $\sM_2(N)$. Because of the relation $\{\alpha,\beta\}=\{0,\beta\}-\{0,\alpha\}$, it suffices to consider modular symbols of the form $\{0,b/a\}$, where the rational number $b/a$ is in lowest terms. Expand $b/a$ as a continued fraction and consider the successive convergents in lowest terms: $$ \frac{b_{-2}}{a_{-2}} = \frac{0}{1},\quad \frac{b_{-1}}{a_{-1}} = \frac{1}{0},\quad \frac{b_0}{a_0} = \frac{b_0}{1},\, \ldots,\quad \frac{b_{n-1}}{a_{n-1}},\quad \frac{b_n}{a_n}= \frac{b}{a} $$ where the first two are added formally. Then $$b_k a_{k-1} - b_{k-1} a_k = (-1)^{k-1},$$ so that $$g_k = \mtwo{b_k}{\hfill (-1)^{k-1}b_{k-1}}{a_k}{(-1)^{k-1}a_{k-1}}\in \SL_2(\Z).$$ Hence $$\left\{\frac{b_{k-1}}{a_{k-1}}, \frac{b_k}{a_k}\right\} = g_k \{ 0, \infty\} = r_i \{0,\infty\},$$ for some~$i$, is of the required special form. \begin{example} Let $N=11$, and consider the modular symbol $\{0,4/7\}$. We have $$\frac{4}{7} = 0 + \frac{1}{1+\frac{1}{1+\frac{1}{3}}},$$ so the partial convergents are $$\frac{b_{-2}}{a_{-2}} = \frac{0}{1},\quad \frac{b_{-1}}{a_{-1}} = \frac{1}{0},\quad \frac{b_0}{a_0} = \frac{0}{1},\quad \frac{b_1}{a_1} = \frac{1}{1},\quad \frac{b_2}{a_2} = \frac{1}{2},\quad \frac{b_3}{a_3} = \frac{4}{7}. $$ Thus, noting as in Example~\ref{ex:01} that $\{0,1\}=0$, we compute \begin{eqnarray*} \{0,4/7\} &=& \{0,\infty\} +\{\infty,0\} + \{0,1\}+ \{1,1/2\} + \{1/2,4/7\}\\ &=& \mtwo{1}{-1}{2}{-1}\{0,\infty\} + \mtwo{4}{1}{7}{2}\{0,\infty\}\\ &=& \mtwo{1}{0}{9}{1}\{0,\infty\} + \mtwo{1}{0}{9}{1}\{0,\infty\}\\ &=& 2 \cdot \left[\mtwo{1}{0}{9}{1}\{0,\infty\}\right] \end{eqnarray*} \end{example} \subsection{Manin symbols} As above, fix coset representatives $r_0,\ldots,r_m$ for $\Gamma_0(N)$ in $\SL_2(\Z)$. Denote the modular symbol $r_i\{0,\infty\}$ by $[r_i]$. The symbols $[r_0],\ldots,[r_m]$ are called {\defn Manin symbols}, and they are equipped with a right action of $\SL_2(\Z)$, which is given by $[r_i]g = [r_j]$, where $\Gamma_0(N) r_j = \Gamma_0(N) r_i g$. Recall that $\SL_2(\Z)$ is generated by the two matrices $\sigma = \abcd{0}{-1}{1}{\hfill0}$ and $\tau=\abcd{1}{-1}{1}{\hfill0}$ (see Theorem~2 of \cite[VII.1.2]{serre:arithmetic}). \begin{theorem}[Manin] The Manin symbols $[r_0],\ldots,[r_m]$ satisfy the following relations: \begin{align*} {[r_i]} + [r_i]\sigma &= 0\\ {[r_i]} + [r_i]\tau + [r_i]\tau^2 &= 0. \end{align*} Furthermore, these relations generate all relations (modulo torsion relations). \end{theorem} This theorem, which is proved in \cite[\S1.7]{manin:parabolic}, provides a finite presentation for the space of modular symbols. \subsection{Hecke operators on modular symbols} When~$p$ is a prime not dividing~$N$, define $$T_p\{\alpha,\beta\} = \mtwo{p}{0}{0}{1}\{\alpha,\beta\} + \sum_{r \hspace{-.6em}\mod p} \mtwo{1}{r}{0}{p} \{\alpha,\beta\}.$$ As mentioned before, this definition is compatible with the integration pairing $\langle\, , \, \rangle$ of Section~\ref{sec:modformhecke}, in the sense that $\langle f T_p, x\rangle = \langle f, T_p x \rangle$. When $p\mid N$, the definition is the same, except that the matrix $\abcd{p}{0}{0}{1}$ is dropped. For example, when $N=11$ we have \begin{eqnarray*} T_2\{0,1/5\} &=& \{0,2/5\} + \{0,1/10\} + \{1/2,3/5\}\\ &=& -2\{0,1/5\}. \end{eqnarray*} In \cite{merel:1585}, L.~Merel gives a description of the action of $T_p$ directly on Manin symbols $[r_i]$ (see also, \cite[\S2.4]{cremona:algs}). For example, when $p=2$ and~$N$ is odd, we have $$T_2([r_i]) = [r_i]\mtwo{1}{0}{0}{2} + [r_i]\mtwo{2}{0}{0}{1} + [r_i]\mtwo{2}{1}{0}{1} + [r_i]\mtwo{1}{0}{1}{2}.$$ \section{Computing the space of modular forms} \label{sec:computingmodform} In this section we describe how to use modular symbols to construct a basis of $S_2(N)$ consisting of modular forms that are eigenvectors for every element of the ring $\T'$ generated by the Hecke operator $T_p$, with $p\nmid N$. Such eigenvectors are called {\defn{}eigenforms}. Suppose~$M$ is a positive integer that divides~$N$. As explained in \cite[VIII.1--2]{lang:modular}, for each divisor~$d$ of $N/M$ there is a natural {\defn{}degeneracy map} $\beta_{M,d} : S_2(M)\ra S_2(N)$ given by $\beta_{M,d}(f(q)) = f(q^d)$. The {\defn{}new subspace} of $S_2(N)$, denoted $S_2(N)^{\new}$, is the complementary $\T$-submodule of the $\T$-module generated by the images of all maps $\beta_{M,d}$, with~$M$ and~$d$ as above. (It is a nontrivial fact that this complement is well defined; one possible proof uses the Petersson inner product.) The theory of Atkin and Lehner \cite{atkin-lehner} asserts that, as a $\T'$-module, $S_2(N)$ decomposes as follows: $$S_2(N) \quad = \bigoplus_{M | N, \,\, d | N/M} \beta_{M,d}(S_2(M)^{\new}).$$ To compute $S_2(N)$ it thus suffices to compute $S_2(M)^{\new}$ for each positive divisor~$M$ of~$N$. We now turn to the problem of computing $S_2(N)^{\new}$. Atkin and Lehner \cite{atkin-lehner} also proved that $S_2(N)^{\new}$ is spanned by eigenforms, each of which occurs with multiplicity one in $S_2(N)^{\new}$. Moreover, if $f\in S_2(N)^{\new}$ is an eigenform then the coefficient of~$q$ in the $q$-expansion of~$f$ is nonzero, so it is possible to normalize~$f$ so that coefficient of~$q$ is~$1$. With~$f$ so normalized, if $T_p(f) = a_p f$, then the $p$th Fourier coefficient of~$f$ is~$a_p$. If $f=\sum_{n=1}^{\infty} a_n q^n$ is a normalized eigenvector for all $T_p$, then the $a_n$, with~$n$ composite, are determined by the $a_p$, with~$p$ prime, by the following formulas: $a_{nm}=a_n a_m$ when $n$ and $m$ are relatively prime, and $a_{p^r} = a_{p^{r-1}} a_p - p a_{p^{r-2}}$ for $p\nmid N$ prime. When $p \mid N$, $a_{p^r}=a_p^r$. We conclude that in order to compute $S_2(N)^{\new}$, it suffices to compute all systems of eigenvalues $\{a_2, a_3, a_5, \ldots\}$ of the Hecke operators $T_2, T_3, T_5, \ldots$ acting on $S_2(N)^{\new}$. Given a system of eigenvalues, the corresponding eigenform is $f=\sum_{n=1}^{\infty} a_n q^n$, where the $a_n$, for~$n$ composite, are determined by the recurrence given above. In light of the pairing $\langle\, ,\, \rangle$ introduced in Section~\ref{sec:modformhecke}, computing the above systems of eigenvalues $\{a_2,a_3, a_5, \ldots \}$ amounts to computing the systems of eigenvalues of the Hecke operators $T_p$ on the subspace~$V$ of $\sS_2(N)$ that corresponds to the new subspace of $S_2(N).$ For each proper divisor~$M$ of~$N$ and each divisor~$d$ of $N/M$, let $\phi_{M,d}:\sS_2(N) \ra \sS_2(M)$ be the map sending~$x$ to $\abcd{d}{0}{0}{1}x$. Then~$V$ is the intersection of the kernels of all maps $\phi_{M,d}$. The computation of the systems of eigenvalues of a collection of commuting diagonalizable endomorphisms involves standard linear algebra techniques, such as computation of characteristic polynomials and kernels of matrices. There are, however, several tricks that greatly speed up this process, some of which are described in \cite[\S3.5.4]{stein:phd}. \begin{example} All forms in $S_2(39)$ are new. Up to Galois conjugacy, the eigenvalues of the Hecke operators $T_2$, $T_3$, $T_5$, and $T_7$ on $\sS_2(39)$ are $\{1, -1, 2, -4 \}$ and $\{a, 1, -2a-2, 2a+2\}$, where $a^2+2a-1=0$. Each of these eigenvalues occur in $\sS_2(39)$ with multiplicity two; for example, the characteristic polynomial of $T_2$ on $\sS_2(39)$ is $(x - 1)^2\cdot(x^2+2x-1)^2$. Thus $S_2(39)$ is spanned by \begin{align*} f_1&=q + q^2 - q^3 - q^4 + 2q^5 - q^6 - 4q^7 + \cdots, \\ f_2&= q + aq^2 + q^3 + (-2a - 1)q^4 + (-2a - 2)q^5 + aq^6 + (2a + 2)q^7 + \cdots, \end{align*} and the Galois conjugate of $f_2$. \end{example} \subsection{Summary} To compute the $q$-expansion, to some precision, of each eigenforms in $S_2(N)$, we use the degeneracy maps so that we only have to solve the problem for $S_2(N)^{\new}$. Here, using modular symbols, we compute all systems of eigenvalues $\{a_2, a_3, a_5,\ldots\}$, then write down each of the corresponding eigenforms $f = q + a_2 q^2 + q_3 q^3 + \cdots $. % References %\bibliographystyle{amsplain} %\bibliography{biblio} \providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace} \begin{thebibliography}{10} \bibitem{stein:vissha} A.~Agashe and W.\thinspace{}A. Stein, \emph{Visibility of {S}hafarevich-{T}ate groups of abelian varieties: {E}vidence for the {B}irch and {S}winnerton-{D}yer conjecture}, (2001). \bibitem{atkin-lehner} A.\thinspace{}O.\thinspace{}L. Atkin and J.~Lehner, \emph{Hecke operators on \protect{$\Gamma \sb{0}(m)$}}, Math. Ann. \textbf{185} (1970), 134--160. \bibitem{birch:hecke_actions} B.~J. Birch, \emph{Hecke actions on classes of ternary quadratic forms}, Computational number theory (Debrecen, 1989), de Gruyter, Berlin, 1991, pp.~191--212. \bibitem{antwerpiv} B.\thinspace{}J. Birch and W.~Kuyk (eds.), \emph{Modular functions of one variable. {I}{V}}, Springer-Verlag, Berlin, 1975, Lecture Notes in Mathematics, Vol. 476. \bibitem{magma} W.~Bosma, J.~Cannon, and C.~Playoust, \emph{The {M}agma algebra system. {I}. {T}he user language}, J. Symbolic Comput. \textbf{24} (1997), no.~3-4, 235--265, Computational algebra and number theory (London, 1993). \bibitem{breuil-conrad-diamond-taylor} C.~Breuil, B.~Conrad, F.~Diamond, and R.~Taylor, \emph{On the modularity of elliptic curves over \protect{$\Q$}: {W}ild $3$-adic exercises}, (2000), \\\protect{\sf http://www.math.harvard.edu/HTML/Individuals/Richard\_Taylor.html}. \bibitem{cremona:algs} J.\thinspace{}E. Cremona, \emph{Algorithms for modular elliptic curves}, second ed., Cambridge University Press, Cambridge, 1997. \bibitem{diamond-im} F.~Diamond and J.~Im, \emph{Modular forms and modular curves}, Seminar on {F}ermat's {L}ast {T}heorem, Providence, RI, 1995, pp.~39--133. \bibitem{greenberg-harper} M.\thinspace{}J. Greenberg and J.\thinspace{}R. Harper, \emph{Algebraic topology}, Benjamin/Cummings Publishing Co. Inc. Advanced Book Program, Reading, Mass., 1981, A first course. \bibitem{hijikata:trace} H.~Hijikata, \emph{Explicit formula of the traces of \protect{H}ecke operators for \protect{$\Gamma_0(N)$}}, J. Math. Soc. Japan \textbf{26} (1974), no.~1, 56--82. \bibitem{kohel:hecke} D.\thinspace{}R. Kohel, \emph{Hecke module structure of quaternions}, In K. Miyake, ed., {\em Class Field Theory -- Its Centenary and Prospect}, The Advanced Studies in Pure Mathematics Series, Math Soc. Japan, to appear. \bibitem{lang:modular} S.~Lang, \emph{Introduction to modular forms}, Springer-Verlag, Berlin, 1995, With appendixes by D. Zagier and W. Feit, Corrected reprint of the 1976 original. \bibitem{manin:parabolic} J.\thinspace{}I. Manin, \emph{Parabolic points and zeta functions of modular curves}, Izv. Akad. Nauk SSSR Ser. Mat. \textbf{36} (1972), 19--66. \bibitem{mazur:symboles} B.~Mazur, \emph{Courbes elliptiques et symboles modulaires}, S\'eminaire Bourbaki, 24\`eme ann\'ee (1971/1972), Exp. No. 414, Springer, Berlin, 1973, pp.~277--294. Lecture Notes in Math., Vol. 317. \bibitem{merel:1585} L.~Merel, \emph{Universal \protect{F}ourier expansions of modular forms}, On {A}rtin's conjecture for odd 2-dimensional representations (Berlin), Springer, 1994, pp.~59--94. \bibitem{mestre:graphs} J.-F. Mestre, \emph{La m\'ethode des graphes. \protect{Exemples} et applications}, Proceedings of the international conference on class numbers and fundamental units of algebraic number fields (Katata) (1986), 217--242. \bibitem{pizer:alg} A.~Pizer, \emph{An algorithm for computing modular forms on \protect{$\Gamma\sb{0}({N})$}}, J. Algebra \textbf{64} (1980), no.~2, 340--390. \bibitem{ribet-stein:serre} K.\thinspace{}A. Ribet and W.\thinspace{}A. Stein, \emph{Lectures on {S}erre's conjectures}, IAS/Park City Mathematics Institute 1999. \bibitem{serre:arithmetic} J-P. Serre, \emph{A \protect{C}ourse in \protect{A}rithmetic}, Springer-Verlag, New York, 1973, Translated from the French, Graduate Texts in Mathematics, No. 7. \bibitem{shimura:intro} G.~Shimura, \emph{Introduction to the arithmetic theory of automorphic functions}, Princeton University Press, Princeton, NJ, 1994, Reprint of the 1971 original, Kan Memorial Lectures, 1. \bibitem{stein:phd} W.\thinspace{}A. Stein, \emph{Explicit approaches to modular abelian varieties}, U.\thinspace{}C. Berkeley Ph.D. thesis (2000). \bibitem{stein-verrill:transportable} W.\thinspace{}A. Stein and H.\thinspace{}A. Verrill, \emph{Cuspidal modular symbols are transportable}, submitted (2001). \bibitem{wada1} H.~Wada, \emph{Tables of {H}ecke operations. {I}}, Seminar on {M}odern {M}ethods in {N}umber {T}heory (Tokyo), Inst. Statist. Math., 1971, p.~10. \end{thebibliography} \end{document}