CoCalc Public Fileswww / papers / thesis / modsyms.tex
Author: William A. Stein
Compute Environment: Ubuntu 18.04 (Deprecated)
1\comment{
2% $Header: /home/was/papers/thesis/RCS/modsyms.tex,v 1.7 2000/05/10 20:31:58 was Exp$
3
4$Log: modsyms.tex,v$
5Revision 1.7  2000/05/10 20:31:58  was
6done.
7
8Revision 1.6  2000/05/10 08:53:23  was
9misc. don't remember.
10
11Revision 1.5  2000/05/09 03:02:10  was
12Re-indexed the whole chapter.
13
14Revision 1.4  2000/05/08 15:48:28  was
15Added $Log: modsyms.tex,v$
16Added Revision 1.7  2000/05/10 20:31:58  was
19Added Revision 1.6  2000/05/10 08:53:23  was
22Added Revision 1.5  2000/05/09 03:02:10  was
25
26}
27
28
29\chapter{Modular symbols}%
30\label{chap:modsym}\index{Modular symbols}%
31Modular symbols permeate this thesis.  In their simplest incarnation,
32modular symbols provide a finite presentation for the homology group
33$H_1(X_0(N),\Z)$ of the Riemann surface $X_0(N)$.  This presentation
34is equipped with such a rich structure that from it we can deduce the
35action of the Hecke operators; this is already sufficient information for
36us to compute a basis for the space $S_2(\Gamma_0(N),\C)$ of cusp
37forms.
38
39We recall the definition of spaces of modular symbols in
40Sections~\ref{sec:defnofmodsyms}--\ref{cuspidalsymbols}.  Then in
41Section~\ref{sec:duality}, we review the
42duality between modular symbols and modular forms.
43In Section~\ref{sec:heckeops}, we see that
44modular symbols are furnished with analogues of each of the standard
45operators that one finds on spaces of modular forms, and in
46Section~\ref{sec:degeneracymaps} we see that the same is true of the
47degeneracy maps.  Section~\ref{sec:maninsymbols} describes Manin
48symbols, which supply a convenient finite presentation for the space of
49modular symbols.  Finally, Section~\ref{sec:tori} introduces the
50complex torus attached to a newform, which appears in various guises
51throughout this thesis.
52
53
54Before continuing, we offer an apology.  We will only consider modular
55symbols that are already equipped with a fixed Dirichlet character.
56Though fixing a character complicates the formulas, the resulting increase
57in efficiency is of extreme value in computational applications.
58Fixing a character allows us to compute in just the part of the space
59of modular symbols for $\Gamma_1(N)$ that interests us.  We apologize
60for any inconvenience this may cause the less efficiency minded
62
63{\bf Acknowledgment.}  This chapter and the next were greatly
64influenced by the publications of Cremona~\cite{cremona:gammaone,
65cremona:algs}\index{Cremona} and Merel~\cite{merel:1585}\index{Merel},
66along with the foundational contributions of
67Manin~\cite{manin:parabolic}, Mazur~\cite{mazur:arithmetic_values,
68mazur:symboles}, and Shokurov~\cite{sokurov:modsym}.  Cremona's
69book~\cite{cremona:algs} provides a motivated roadmap that guides the
70reader who wishes to compute with modular symbols in the familiar
71context of elliptic curves, and Merel's\index{Merel} article provides an accessible
72overview of the action of Hecke operators on higher weight modular
73symbols, and the connection between modular symbols and related
74cohomology theories.
75
76\section{The definition of modular symbols}
77\label{sec:defnofmodsyms}
78Fix a positive integer~$N$, an integer $k\geq 2$, and a continuous
79homomorphism
80  $$\eps:(\Z/N\Z)^*\ra\C^*$$
81such that $\eps(-1)=(-1)^k$.
82We call~$N$ the \defn{level}\index{Level of modular symbols|textit},~$k$ the
83\defn{weight}\index{Weight of modular symbols|textit},
84and~$\eps$ the \defn{Dirichlet character}.\index{Dirichlet character|textit}
85
86
87Consider the quotient of the abelian group generated by all formal symbols
88$\{\alp,\beta\}$, with $\alp, \beta\in\P^1(\Q)=\Q\union\{\infty\}$,
89by the following relations:
90  $$\{\alp,\beta\}+\{\beta,\gamma\}+\{\gamma,\alp\} = 0,$$
91for all $\alp,\beta,\gamma\in\P^1(\Q)$.
92Let $\sM$ be the torsion-free quotient of this group by its torsion
93subgroup.  Because $\sM$ is torsion free, $\{\alp,\alp\}=0$ and
94$\{\alp,\beta\} = -\{\beta,\alp\}$.
95\index{Modular symbols!relations satisfied by}
96
97\begin{remark}
98One is motivated to consider these relations by viewing
99$\{\alp,\beta\}$ as the homology class of an appropriate
100path from~$\alpha$ to~$\beta$ in the upper half plane.
101\end{remark}
102
103Let $V_{k-2}$\label{defn:vk} be the $\Z$-submodule of $\Z[X,Y]$ made up of
104all homogeneous polynomials of degree $k-2$, and set
105   $\sM_k := V_{k-2}\tensor\sM.$
106\label{pg:higherweightmodsym}
107For $g=\abcd{a}{b}{c}{d}\in\GL_2(\Q)$ and $P\in V_{k-2}$, let
108\begin{align*}
109     gP(X,Y) &= P\left(\det(g)g^{-1}\vtwo{X}{Y}\right)
110             = P\left(\mtwo{\hfill d}{-b}{-c}{\hfill a}\vtwo{X}{Y}\right)\\
111             &= P(dX-bY,-cX+aY).
112\end{align*}
113This defines a left action of $\GL_2(\Q)$ on $V_{k-2}$;
114it is a left action because
115\begin{align*}
116 (gh)P(v) &= P(\det(gh)(gh)^{-1}v)
117          = P(\det(h)h^{-1}\det(g)g^{-1}v)\\
118          &= gP(\det(h)h^{-1}v) = g(hP(v)).
119\end{align*}
120Combining this action with the action of $\GL_2(\Q)$ on $\P^1(\Q)$
121by linear fractional transformations gives
122a left action of $\GL_2(\Q)$ on $\sM_k$:
123  $$g (P \tensor \{\alp,\beta\}) = g(P)\tensor\{g(\alp),g(\beta)\}.$$
124Finally, for $g=\abcd{a}{b}{c}{d}\in\Gamma_0(N)$, let
125$\eps(g) := \eps(\overline{a})$,
126where $\overline{a}\in\Z/N\Z$ is the reduction modulo~$N$ of~$a$.
127
128Let
129$$\Z[\eps] := \Z[\eps(a) : a \in \Z/N\Z]$$
130be the subring of~$\C$ generated by the values of the
131character~$\eps$.
132\begin{definition}[Modular symbols]\label{defn:modsym}
133\index{Modular symbols|textit}%
134The space of \defn{modular symbols} $\sM_k(N,\eps)$
135of level~$N$, weight~$k$ and character~$\eps$ is
136the largest torsion-free quotient of $\sM_k\tensor\Z[\eps]$ by the
137$\Z[\eps]$-submodule generated by the
138relations $gx-\eps(g)x$ for all $x\in\sM_k$
139and all $g\in\Gamma_0(N)$.
140\end{definition}
141Denote by $P\{\alp,\beta\}$ the image
142of $P\tensor\{\alp,\beta\}$ in $\sM_k(N,\eps)$.
143For any $\Z[\eps]$-algebra~$R$, let
144$$\sM_k(N,\eps;R) := \sM_k(N,\eps)\tensor_{Z[\eps]} R.$$
145See Section~\ref{sec:computingmk} for an algorithm which
146can be used to compute $\sM_k(N,\eps;\Q(\eps))$.
147
148\section{Cuspidal modular symbols}
149\label{cuspidalsymbols}
150\index{Cuspidal modular symbols|textit}
151Let~$\sB$ be the  free abelian group generated by the symbols
152$\{\alp\}$ for all $\alp\in\P^1(\Q)$.
153There is a left action of~$\GL_2(\Q)$ on~$\sB$ given by
154$g\{\alp\}=\{g(\alp)\}$.
155Let $\sB_k := V_{k-2}\tensor \sB$, and let $\GL_2(\Q)$ act
156on $\sB_k$ by $g(P\{\alp\}) = (gP)\{g(\alp)\}$.
157\begin{definition}[Boundary modular symbols]\label{def:boundarysymbols}
158The space $\sB_k(N,\eps)$ of
159\index{Boundary modular symbols|textit}%
160\defn{boundary modular symbols}
161is the largest torsion-free quotient
162of $\sB_k\tensor\Z[\eps]$ by the relations
163$gx = \eps(g) x$ for all
164$g\in \Gamma_0(N)$ and $x\in \sB_k$.
165\end{definition}
166Denote by $P\{\alp\}$ the image of $P\tensor\{\alp\}$
167in $\sB_k(N,\eps)$.
168The \defn{boundary map}
169  $$\delta: \sM_k(N,\eps) \ra \sB_k(N,\eps)$$
170is defined by
171 $$\delta(P\{\alp,\beta\}) = 172 P\{\beta\}-P\{\alp\}.$$
173\begin{definition}[Cuspidal modular symbols]%
174\label{defn:cuspidalmodularsymbols}%
175\index{Cuspidal modular symbols|textit}%
176The space $\sS_k(N,\eps)$ of
177\defn{cuspidal modular symbols}
178is the kernel of~$\delta$.
179\end{definition}
180The three spaces defined above fit together in the
181following exact sequence:
182  $$0\ra \sS_k(N,\eps) \ra\sM_k(N,\eps)\xrightarrow{\,\delta\,} 183 \sB_k(N,\eps).$$
184
185
186
187\section{Duality between modular symbols and modular forms}%
188\label{sec:duality}
189\index{Modular symbols!duality with modular forms}%
190\index{Modular forms!duality with modular symbols}%
191\index{Integration pairing}%
192For any positive integer~$k$, any $\C$-valued function~$f$ on
193the complex upper half plane
194$$\h:=\{z \in \C : \im(z) > 0\},$$
195and any matrix $\gamma\in\GL_2(\Q)$, define a function
196$f|[\gamma]_k$ on~$\h$ by
197 $$(f|[\gamma]_k)(z) = \det(\gamma)^{k-1}\frac{f(\gamma z)}{(cz+d)^{k}}.$$
198\begin{definition}[Cusp forms]\index{Cusp forms|textit}
199Let $S_k(N,\eps)$ be the complex vector space of holomorphic
200functions $f(z)$ on~$\h$ that satisfy
201the equation
202  $$f|[\gamma]_k = \eps(\gamma)f$$
203for all $\gamma\in\Gamma_0(N)$, and such that~$f$
204is holomorphic and vanishes at all cusps, in the sense of
205\cite[pg.~42]{diamond-im}.
206\end{definition}
207
208\begin{definition}[Antiholomorphic cusp forms]%
209\index{Cusp forms!antiholomorphic|textit}%
210\index{Antiholomorphic cusp forms|textit}
211Let $\Sbar_k(N,\eps)$ be the space of
212\defn{antiholomorphic cusp forms};
213the definition is as above, except
214$$\frac{f(\gamma z)}{(c\overline{z}+d)^k} = \overline{\eps}(\gamma) f(z)$$
215for all $\gamma\in\Gamma_0(N)$.\footnote{The $\overline{\eps}$
216should be replaced by~$\eps$ in this formula, as
217in \cite[\S2.5]{merel:1585}.}
218\end{definition}
219There is a canonical isomorphism of real vector spaces
220between $S_k(N,\eps)$ and $\Sbar_k(N,\eps)$ that associates
221to~$f$ the antiholomorphic cusp form defined by the function
222$z\mapsto \overline{f(z)}$.
223
224\begin{theorem}[Merel]\label{thm:perfectpairing}\index{Merel}
225There is a  pairing
226\begin{equation*}
227    \langle\,\, , \, \, \rangle:
228    (S_k(N,\eps)\oplus \Sbar_k(N,\eps)) \cross \sM_k(N,\eps;\C)
229   \ra \C
230\end{equation*}
231given by
232$$\langle f\oplus g, P\{\alp,\beta\}\rangle = 233 \int_{\alp}^{\beta} f(z)P(z,1) dz 234 + \int_{\alp}^{\beta} g(z)P(\zbar,1) d\zbar,$$
235where the path from~$\alp$ to~$\beta$ is,
236except for the endpoints, contained in~$\h$.
237The pairing is perfect when restricted to $\sS_k(N,\eps;\C)$.
238\end{theorem}
239\begin{proof}
240Take the~$\eps$ part of each side of~\cite[Thm.~3]{merel:1585}.
241\end{proof}
242
243
244\section{Linear operators}
245\label{sec:heckeops}
246\subsection{Hecke operators}\label{heckeops:modsym}
247\index{Hecke operators}\index{Operators!Hecke}
248For each positive integer~$n$ and each space~$V$ of modular symbols or modular
249forms, there is a \defn{Hecke operator}~$T_n$, which acts
250as a linear endomorphism of~$V$.
251For the definition of $T_n$ on modular symbols,
252see~\cite[\S2]{merel:1585}.
253Alternatively, because we consider only modular symbols
254with character, the following
255recipe completely determines the Hecke operators.
256First, when $n=p$ is prime, we have
257$$T_p(x) = \left[ \mtwo{p}{0}{0}{1} + \sum_{r \md p} 258 \mtwo{1}{r}{0}{p}\right] x,$$
259where the first matrix is omitted if $p\mid N$.
260If~$m$ and~$n$ are coprime, then $T_{mn} = T_mT_n$.
261Finally, if~$p$ is a prime, $r\geq 2$ is an integer,~$\varepsilon$ is
262the Dirichlet character of associated to~$V$, and~$k$ is the weight
263of~$V$, then
264  $$T_{p^r} = 265 T_p T_{p^{r-1}} - \varepsilon(p) p^{k-1} T_{p^{r-2}}.$$
266
267\begin{definition}\index{Hecke algebra|textit}
268The \defn{Hecke algebra associated to $V$} is the subring
269 $$\T=\T_V = \Z[\ldots T_n \ldots]$$
270of $\End(V)$ generated by all Hecke operators $T_n$, with $n=1,2,3,\ldots$.
271\end{definition}
272
273\begin{proposition}\label{prop:modsympairing}
274The pairing of Theorem~\ref{thm:perfectpairing} respects the
275action of the Hecke operators\index{Hecke operators!respect pairing},
276in the sense that $\langle f T, x \rangle = \langle f , T x \rangle$
277for all $T\in \T$, $x\in\sM_k(N,\eps)$,
278 and $f\in S_k(N,\eps)\oplus \Sbar_k(N,\eps)$.
279\end{proposition}
280\begin{proof}
281See~\cite[Prop.~10]{merel:1585}.
282\end{proof}
283
284\subsection{The $*$-involution}\label{sec:starinvolution}
285\index{Star involution|textit}\index{Operators!$*$-involution|textit}
286The matrix $j=\abcd{-1}{0}{\hfill0}{1}$ defines
287an involution~$*$ of $\sM_k(N,\eps)$ given by
288$x\mapsto x^*=j(x)$.  Explicitly,
289\begin{equation*}
290(P(X,Y)\{\alp,\beta\})^* = P(X,-Y)\{-\alp,-\beta\}.
291\end{equation*}
292Because the space of modular symbols is constructed as a quotient,
293it is not obvious that the $*$-involution is well defined.%
294\index{Star involution!is well defined}
295\begin{proposition}
296The $*$-involution is well defined.
297\end{proposition}
298\begin{proof}
299Recall that $\sM_k(N,\eps)$ is the largest torsion-free quotient of the
300free $\Z[\eps]$-module generated by symbols
301$x=P\{\alp,\beta\}$ by the submodule generated by
302relations $\gamma x - \eps(\gamma)x$ for
303all $\gamma\in \Gamma_0(N)$.
304In order to check that the operator~$*$ is well defined, it
305suffices to check, for any $x\in\sM_k$, that
306$*(\gamma x - \eps(\gamma)x)$ is of
307the form $\gamma' y - \eps(\gamma') y$, for some~$y$ in $\sM_k$.
308Note that if $\gamma=\abcd{a}{b}{c}{d}\in \Gamma_0(N)$, then
309$j\gamma j^{-1} = \abcd{\hfill a}{-b}{-c}{\hfill d}$ is also in $\Gamma_0(N)$
310and $\eps(j\gamma j^{-1}) = \eps(\gamma)$.  We have
311\begin{align*}
312    j(\gamma x - \eps(\gamma) x) &=
313           j \gamma x - j \eps(\gamma) x \\
314        &= j \gamma j^{-1} j x - \eps(\gamma) j x\\
315        &= (j\gamma j^{-1}) (j x) - \eps(j \gamma j^{-1}) (jx).
316\end{align*}
317\end{proof}
318
319If~$f$ is a modular form\index{Modular forms}, let $f^*$ be the holomorphic
320function $\overline{f(-\overline{z})}$, where the bar
321denotes complex conjugation.
322   The Fourier coefficients\index{Fourier coefficients}
323of $f^*$ are the complex conjugates of those of~$f$; though $f^*$
324is again a holomorphic modular form\index{Modular forms}, its character
325is $\overline{\eps}$ instead of~$\eps$.
326The pairing of Theorem~\ref{thm:perfectpairing}
327is the restriction of a pairing on the full spaces without
328character, and we have the following proposition.
329\index{Star involution!and integration pairing}
330\begin{proposition}\label{prop:starpairing}\footnote{G. Weber pointed
331out that this isn't correct.  It is correct if the pairing is replaced
332by $(f,x) = -2\pi i\langle f, x\rangle$ and $x$ is
333restricted to modular symbols that are fixed by complex
334conjugation.}
335We have
336\begin{equation*}
337\langle f^*,  x^* \rangle = \overline{\langle f, x\rangle}.
338\end{equation*}
339\end{proposition}
340
341\begin{definition}[Plus-one quotient]\index{Plus-one quotient|textit}%
342\index{Modular symbols!plus-one quotient of}
343\index{Modular symbols!minus-one quotient of}
344The \defn{plus-one quotient} $\sM_k(N,\eps)_+$ is the
345largest torsion-free quotient of $\sM_k(N,\eps)$ by the relations
346$x^*-x=0$ for all $x\in \sM_k(N,\eps)$.
347Similarly, the \defn{minus-one quotient}\index{Minus-one quotient}
348is the quotient of $\sM_k(N,\eps)$ by all relations
349$x^*+x=0$, for $x\in\sM_k(N,\eps)$.
350\end{definition}
351
352\begin{warning} We were forced to make
353a choice in our definition of the operator~$*$.
354Fortunately, it agrees with that of~\cite[\S2.1.3]{cremona:algs},
355but {\em not} with the choice made in~\cite[\S1.6]{merel:1585}.
356\end{warning}
357
358\subsection{The Atkin-Lehner involutions}\label{sec:atkin-lehner}
359\index{Operators!Atkin-Lehner|textit}
360\index{Atkin-Lehner involution|textit}
361In this section we assume
362that~$k$ is even and $\eps^2=1$.
363The assumption on~$\eps$ is necessary only so that
364the involution we are about to define preserves
365$\sM_k(N,\eps)$.  More generally, it is possible to define
366a map which sends $\sM_k(N,\eps)$ to $\sM_k(N,\overline{\eps})$.
367
368To each divisor~$d$ of~$N$ such that $(d,N/d)=1$ there is an
369\defn{Atkin-Lehner involution}~$W_d$ of $\sM_k(N,\eps)$,
370which is defined as follows.  Using the Euclidean algorithm, choose
371integers $x,y,z,w$ such that
372         $$dxw - (N/d)yz = 1.$$
373Next let $g=\abcd{dx}{y}{Nz}{dw}$ and define
374     $$W_d(x) \define \frac{1}{d^{\frac{k-2}{2}}}\cdot g(x).$$
375For example, when $d=N$ we have $g=\abcd{0}{-1}{N}{\hfill 0}$.
376The factor of $d^{\frac{k-2}{2}}$ is necessary to normalize
377$W_d$ so that it is an involution.
378
379On modular forms there is an Atkin-Lehner involution,
380also denoted $W_d$,\index{Modular forms!and Atkin-Lehner involution}
381which acts by $W_d(f) = f|[W_d]_k$.  These two like-named involutions
382are compatible with the integration pairing:
383$$\langle W_d(f), x\rangle = \langle f, W_d(x)\rangle.$$
384\index{Atkin-Lehner involution!and integration pairing}
385
386\section{Degeneracy maps}
387\label{sec:degeneracymaps}
388\label{pg:degeneracymaps}
389\index{Degeneracy maps}
390In this section, we describe natural maps between spaces of
391modular symbols of different levels.
392
393Fix a positive integer~$N$ and a Dirichlet
394character\index{Dirichlet character}
395$\eps : (\Z/N\Z)^*\ra \C^*$.  Let~$M$ be a positive divisor
396of~$N$ that is divisible by the conductor of~$\eps$, in the sense
397that~$\eps$ factors through $(\Z/M\Z)^*$ via the natural map
398$(\Z/N\Z)^*\ra (\Z/M\Z)^*$ composed with some uniquely defined
399character $\eps':(\Z/M\Z)^*\ra\C^*$.  For any positive divisor~$t$ of
400$N/M$, let $T=\abcd{1}{0}{0}{t}$ and fix a choice $D_t=\{T\gamma_i : 401i=1,\ldots, n\}$ of coset representatives for $\Gamma_0(N)\backslash 402T\Gamma_0(M)$.
403
404\begin{warning}
405There is a mistake in \cite[\S2.6]{merel:1585}:
406 The quotient $\Gamma_1(N)\backslash\Gamma_1(M)T$'' should be replaced
407by $\Gamma_1(N)\backslash T\Gamma_1(M)$''.
408\end{warning}
409\begin{proposition}
410For each divisor~$t$ of $N/M$ there are well-defined linear maps
411\begin{align*}
413      \alp_t(x) = (tT^{-1})x = \mtwo{t}{0}{0}{1} x\\
415      \beta_t(x) = \sum_{T\gam_i\in D_t} \eps'(\gam_i)^{-1}T\gam_i{} x.
416\end{align*}
417Furthermore,
418  $\alp_t\circ \beta_t$ is multiplication by
419  $t^{k-2}\cdot [\Gamma_0(M) : \Gamma_0(N)].$
420\end{proposition}
421\begin{proof}
422To show that~$\alp_t$ is well defined, we must show that for
423each $x\in\sM_k(N,\eps)$ and $\gam=\abcdmat\in\Gamma_0(N)$, that we
424have
425  $$\alp_t(\gamma x -\eps(\gamma) x)=0\in\sM_k(M,\eps').$$
426We have
427$$\alp_t(\gam x) = \mtwo{t}{0}{0}{1}\gam x 428 = \mtwo{a}{tb}{c/t}{d}\mtwo{t}{0}{0}{1} x 429 = \eps'(a)\mtwo{t}{0}{0}{1} x,$$
430so
431$$\alp_t(\gamma x -\eps(\gamma) x) 432 = \eps'(a)\alp_t(x) - \eps(\gamma)\alp_t(x) = 0.$$
433
434We next verify that~$\beta_t$ is well defined.
435Suppose that $x\in\sM_k(M,\eps')$ and $\gamma\in\Gamma_0(M)$;
436then $\eps'(\gam)^{-1}\gam x = x$, so
437\begin{align*}
438\beta_t(x)
439    &= \sum_{T\gam_i\in D_t}
440        \eps'(\gam_i)^{-1}T\gam_i{}\eps'(\gam)^{-1}\gam{} x\\
441    &= \sum_{T\gam_i\gam\in D_t}
442        \eps'(\gam_i\gam)^{-1}T\gam_i{}\gam{} x.
443\end{align*}
444This computation shows that the definition of~$\beta_t$
445does not depend on the choice~$D_t$ of coset representatives.
446To finish the proof that~$\beta_t$ is well defined
447we must show that, for $\gam\in\Gamma_0(M)$, we have
448$\beta_t(\gam x) = \eps'(\gam)\beta_t(x)$ so that $\beta_t$
449respects the relations that define $\sM_k(M,\eps)$.
450Using that~$\beta_t$ does not depend on the choice of
451coset representative, we find that for $\gamma\in\Gamma_0(M)$,
452\begin{align*}
453  \beta_t(\gam x)
454     &= \sum_{T\gam_i\in D_t} \eps'(\gam_i)^{-1}T\gam_i{} \gam{} x\\
455     &= \sum_{T\gam_i\gam^{-1}\in D_t}
456         \eps'(\gam_i\gam^{-1})^{-1}T\gam_i{}\gam{}^{-1} \gam{} x\\
457     &= \eps'(\gam)\beta_t(x).\\
458\end{align*}
459To compute $\alp_t\circ\beta_t$, we use
460that $\#D_t = [\Gamma_0(N) : \Gamma_0(M)]$:
461\begin{align*}
462 \alp_t(\beta_t(x)) &=
463    \alp_t \left(\sum_{T\gamma_i}
464        \eps'(\gam_i)^{-1}T\gam_i x\right)\\
465  &= \sum_{T\gamma_i}
466        \eps'(\gam_i)^{-1}(tT^{-1})T\gam_i x\\
467  &= t^{k-2}\sum_{T\gamma_i}
468        \eps'(\gam_i)^{-1}\gam_i x\\
469  &= t^{k-2}\sum_{T\gamma_i} x \\
470  &= t^{k-2} \cdot [\Gamma_0(N) : \Gamma_0(M)] \cdot x.
471\end{align*}
472The scalar factor of $t^{k-2}$ appears instead
473of~$t$, because~$t$ is acting on~$x$ as an element of $\GL_2(\Q)$
474{\em not} as an an element of~$\Q$.
475\end{proof}
476
477\begin{definition}[New and old modular symbols]%
478\label{def:newandoldsymbols}%
479\index{New modular symbols|textit}%
480\index{Old modular symbols|textit}%
481\index{Modular symbols!new and old subspace of|textit}%
482The subspace $\sM_k(N,\eps)^{\new}$
483of \defn{new modular symbols} is the
484intersection of the kernels of the $\alp_t$ as~$t$
485runs through all positive divisors of $N/M$ and~$M$
486runs through positive divisors of~$M$ strictly less than~$N$
487and divisible by the conductor of~$\eps$.
488The subspace $\sM_k(N,\eps)^{\old}$
489of \defn{old modular symbols}
490is the subspace generated by the images of the $\beta_t$
491where~$t$ runs through all positive divisors of $N/M$ and~$M$
492runs through positive divisors of~$M$ strictly less than~$N$
493and divisible by the conductor of~$\eps$.
494\end{definition}
495
496{\bf WARNING:} The new and old subspaces need not be disjoint, as
497the following example illustrates!
498This is contrary to the statement on page~80 of~\cite{merel:1585}.
499\begin{example}
500We justify the above warning.
501Consider, for example, the case $N=6$, $k=2$, and trivial character.
502The spaces $\sM_2(2)$ and $\sM_2(3)$ are each of dimension~$1$, and
503each is generated by the modular symbol $\{\infty,0\}$.
504The space $\sM_2(6)$ is of dimension~$3$, and is generated by
505the~$3$ modular symbols $\{\infty, 0\}$, $\{-1/4, 0\}$,
506and $\{-1/2, -1/3\}$.
507The space generated by the~$2$ images
508of $\sM_2(2)$ under the~$2$ degeneracy
509maps has dimension~$2$, and likewise for $\sM_2(3)$.
510Together these images generate $\sM_2(6)$, so $\sM_2(6)$ is
511equal to its old subspace.
512However, the new subspace is nontrivial because
513the two degeneracy maps $\sM_2(6) \ra \sM_2(2)$ are equal,
514as are the two degeneracy maps $\sM_2(6) \ra \sM_2(3)$.
515In particular, the intersection of the kernels of the degeneracy
516maps has dimension at least~$1$ (in fact, it equals~$1$).
517
518Computationally, it appears that something similar to this happens
519if and only if the weight is~$2$, the character is trivial,
520and the level is composite.  This behavior is probably related
521to the nonexistence of a characteristic~$0$ Eisenstein series
522of weight~$2$ and level~$1$.
523\end{example}
524
525The following tempting argument is incorrect;
526the error lies in the fact that
527an element of the old subspace
528is a {\em linear combination} of $\beta_t(y)$'s
529for various~$y$'s and~$t$'s:
530If~$x$ is in both the new and old subspace,
531then $x=\beta_t(y)$ for some modular symbol~$y$
532of lower level.  This implies $x=0$ because
533 $$0 = \alp_t(x) = \alp_t(\beta_t(y))= 534t^{k-2}\cdot[\Gamma_0(N):\Gamma_0(M)] \cdot{}y.\text{''}$$
535
536
537\begin{remark}
538The map $\beta_t\circ\alp_t$ cannot in general be multiplication by
539a scalar since $\sM_k(M,\eps')$
540usually has smaller dimension than $\sM_k(N,\eps)$.
541\end{remark}
542
543\comment{
544\begin{example}
545The proposition implies that $\beta_t$ is injective in
546characteristic~$0$. This need not be the case in positive
547characteristic, as the following example illustrates.
548Let~$p$ be any prime, and let $\eps:(\Z/N\Z)^* \ra 549\Fbar_p^*$ be the reduction to characteristic~$p$
550of a Dirichlet character.
551There is again a map $\beta_{t,p}:\sM_k(M,\eps';\Fbar_p) \ra 552\sM_k(N,\eps;\Fbar_p)$, where the space $\sM_k(N,\eps;\Fbar_p)$ is
553defined by choosing a maximal ideal $\wp$ lying over~$p$ in an
554appropriate extension $\O$ of~$\Z$, and letting~$R=\Fbar_p$
555be an algebraic closure of the finite field~$\O/\wp$.
556When~$p$
557does not divide $t^{k-2}\cdot [\Gamma_0(M) : \Gamma_0(N)]$, the
558proposition shows that $\beta_{t,p}$ is injective.  However,
559$\beta_t\tensor\F_p$ need not be injective for all~$p$.  For example,
560suppose $M=14$, $N=28$, and $\eps=1$. Then there are bases with
561respect to which the matrix of $\beta_1$ is the transpose of
562$$\left( 563\begin{matrix} 5641&0&0&1&0&0&0&0&0\\ 565 0&1&0&0&1&0&0&0&0\\ 566 0&0&1&0&0&1&0&0&0\\ 567 0&0&0&0&0&0&2&1&-1\\ 568 0&0&0&0&0&0&0&1&1 569\end{matrix} 570\right),$$
571and the row vector $(0,0,0,1,1)$ is in the kernel of the mod~$2$
572reduction of this matrix.
573\end{example}
574}
575
576\subsection{Computing coset representatives}%
577\index{Coset representatives}
578\begin{definition}[Projective line mod~$N$]%
579\index{Projective line modulo~$N$|textit}%
580Let~$N$ be a positive integer.
581Then the \defn{projective line}
582$\P^1(N)$ is the set of
583pairs $(a,b)$, with $a, b\in\Z/N\Z$ and $\gcd(a,b,N)=1$, modulo
584the eqivalence relation which identifies $(a,b)$ and $(a',b')$ if and only
585if $ab'\con ba'\pmod{N}$.
586\end{definition}
587
588Let~$M$ be a positive divisor of~$N$ and~$t$ a
589divisor of~$N/M$.  The following {\em random} algorithm
590computes a set~$D_t$ of representatives for the orbit space
591$\Gamma_0(M)\backslash T\Gamma_0(N).$
592There are deterministic algorithms for computing
593$D_t$, but all of the ones the author has found are
594{\em vastly} less efficient than the following random algorithm.
595\begin{algorithm}\label{alg:degenreps}%
596\index{Algorithm for computing!coset representatives}
597      Let $\Gamma_0(N/t,t)$ denote the subgroup of $\SL_2(\Z)$
598consisting of matrices that are upper triangular modulo $N/t$ and lower
599triangular modulo~$t$.   Observe that two right cosets
600 of $\Gamma_0(N/t,t)$ in $\SL_2(\Z)$,  represented by
601$\abcd{a}{b}{c}{d}$ and $\abcd{a'}{b'}{c'}{d'}$,
602are equivalent if and only if
603$(a,b)=(a',b')$ as points of $\P^1(t)$
604and $(c,d)=(c',d')$ as points of $\P^1(N/t)$.
605Using the following algorithm, we compute right coset
606representatives for $\Gamma_0(N/t,t)$
607inside~$\Gamma_0(M)$.
608\begin{enumerate}
609       \item Compute the number $[\Gamma_0(M):\Gamma_0(N)]$ of cosets.
610       \item Compute a random element $x \in \Gamma_0(M)$.
611       \item If~$x$ is not equivalent to anything generated so
612              far, add it to the list.
613       \item Repeat steps (2) and (3) until the list is as long
614             as the bound of step (1).
615\end{enumerate}
616There is a natural bijection between
617       $\Gamma_0(N)\backslash T \Gamma_0(M)$
618and $\Gamma_0(N/t,t)\backslash \Gamma_0(M)$,
619under which~$T\gamma$ corresponds to~$\gamma$.
620Thus we obtain coset representatives for
621 $\Gamma_0(N)\backslash T\Gamma_0(M)$
622by left multiplying each
623coset representative of $\Gamma_0(N/t,t)\backslash\Gamma_0(M)$  by~$T$.
624\end{algorithm}
625
626\subsection{Compatibility with modular forms}%
627\index{Degeneracy maps!compatibility}%
628The degeneracy maps defined above
629are compatible with the corresponding degeneracy maps
630$\tilde{\alp}_t$ and $\tilde{\beta}_t$
631on modular forms\index{Modular forms}.  This is because the degeneracy
632maps on modular forms are defined by summing over the
633same coset representatives $D_t$.
634Thus we have the following compatibilities.
635\begin{align*}
636  \langle \tilde{\alp}_t(f), x \rangle &= \langle f, \alp_t(x)\rangle,\\
637  \langle \tilde{\beta}_t(f), x\rangle &=  \langle f, \beta_t(x) \rangle .
638\end{align*}
639If~$p$ is prime to~$N$, then $T_p\alp_t = \alp_t T_p$
640   and $T_p\beta_t = \beta_t T_p$.
641
642\section{Manin symbols}%
643\label{sec:maninsymbols}%
644\index{Manin symbols}%
645From the definition given in
646Section~\ref{sec:defnofmodsyms}, it is not obvious
647that $\sM_k(N,\eps)$ is of finite rank.  The Manin
648symbols provide a finite presentation of~$\sM_k(N,\eps)$
649that is vastly more useful from a computational point of view.
650\index{Modular symbols!finite presentation of}
651
652\begin{definition}[Manin symbols]\label{defn:maninsymbols}%
653\index{Manin symbols|textit}%
654The \defn{Manin symbols} are the set of pairs
655           $$[P(X,Y),(u,v)]$$
656where $P(X,Y)\in V_{k-2}$ and
657$0\leq u,v < N$ with $\gcd(u,v,N)=1$.
658\end{definition}
659Define a {\em right} action of $\GL_2(\Q)$ on
660the free $\Z[\eps]$-module~$M$ generated by the Manin
661symbols as follows. The element $g=\abcd{a}{b}{c}{d}$ acts by
662\begin{equation*}
663[P,(u,v)]g=[g^{-1}P(X,Y),(u,v) g]
664    = [P(aX+bY,cX+dY),(au+cv,bu+dv)].
665\end{equation*}
666Let $\sigma=\abcd{0}{-1}{1}{\hfill 0}$ and $\tau=\abcd{0}{-1}{1}{-1}$\label{defn:sigmatau}.
667Let $\sM_k(N,\eps)'$ be the largest torsion-free quotient
668of~$M$ by the relations
669\begin{align*}
670\mbox{}x + x\sigma &= 0,\\
671\mbox{}x + x\tau+ x\tau^2 &= 0,\\
672   \eps(\lambda) [P,(u,v)]- [P,(\lambda u, \lambda v)] &=0.
673\end{align*}
674
675\begin{theorem}\label{thm:maninsymbols}
676There is a natural isomorphism
677$\vphi:\sM_k(N,\eps)'\lra\sM_k(N,\eps)$ given by
678$$[X^iY^{2-k-i},(u,v)] \mapsto g(X^iY^{k-2-i}\{ 0,\infty\})$$
679where $g=\abcd{a}{b}{c}{d}\in\SL_2(\Z)$ is any matrix
680such that $(u,v)\con (c,d) \pmod{N}$.
681\end{theorem}
682\begin{proof}
683In~\cite[\S1.2, \S1.7]{merel:1585} it is proved that
684$\vphi\tensor_{\Z[\eps]}\C$ is
685an isomorphism, so~$\vphi$ is injective and well defined.
686The discussion in Section~\ref{sec:modmanconv} below
687(Manin's trick'')\index{Manin's trick}\index{Manin symbols!and Manin's trick}
688shows that every element in $\sM_k(N,\eps)$ is a $\Z[\eps]$-linear
689combination of elements in the image, so~$\vphi$ is surjective as well.
690\end{proof}
691
692\subsection{Conversion between modular and Manin symbols}%
693\index{Manin symbols!conversion to modular symbols}%
694\index{Modular symbols!conversion to Manin symbols}%
695\label{sec:modmanconv}%
696For some purposes it is better to work with modular symbols, and for
697others it is better to work with Manin symbols.  For example, there
698are descriptions of the Atkin-Lehner involution\index{Atkin-Lehner involution}
699in terms of both Manin
700and modular symbols; it appears more efficient to compute this
701involution using modular symbols.  On the other hand, practically
702Hecke operators can be computed more efficiently using Manin symbols.
703It is thus essential to be able to convert between these two
704representations.  The conversion from Manin to modular symbols is
705straightforward, and follows immediately from
706Theorem~\ref{thm:maninsymbols}.  The conversion back is accomplished
707using the method used to prove Theorem~\ref{thm:maninsymbols}; it is
708known as Manin's trick'',\index{Manin's trick|textit}\index{Manin!trick of|textit} and involves continued fractions\index{Continued fractions}.
709
710Given a Manin symbol $[X^iY^{k-2-i},(u,v)]$\index{Manin symbols},
711we write down a corresponding modular symbol\index{Modular symbols}
712as follows.
713Choose $\abcd{a}{b}{c}{d}\in\SL_2(\Z)$ such that
714$(c,d)\con (u,v)\pmod{N}$.  This is possible
715by Lemma~1.38 of~\cite[pg.~20]{shimura:intro}; in practice,
716finding $\abcd{a}{b}{c}{d}$ is not completely trivial, but
717can be accomplished using the extended Euclidean
718algorithm.
719Then
720 \begin{eqnarray*}
721 [X^iY^{k-2-i},(u,v)] &\corrto&
722    \abcd{a}{b}{c}{d}(X^iY^{k-2-i}\{ 0,\infty\})\\
723    &&= (dX-bY)^i(-cX+aY)^{2-k-i}
724       \left\{\frac{b}{d},\,\frac{a}{c}\right\}.\\
725\end{eqnarray*}
726
727In the other direction, suppose that we are given a modular
728symbol $P(X,Y)\{\alp,\beta\}$ and wish to represent it as a
729sum of Manin symbols.   Because
730    $$P\{a/b,c/d\} = P\{a/b,0\}+P\{0,c/d\},$$
731it suffices to write $P\{0,a/b\}$ in
732terms of Manin symbols.
733Let
734$$0=\frac{p_{-2}}{q_{-2}} = \frac{0}{1},\,\, 735\frac{p_{-1}}{q_{-1}}=\frac{1}{0},\,\, 736\frac{p_0}{1}=\frac{p_0}{q_0},\,\, 737\frac{p_1}{q_1},\,\, 738\frac{p_2}{q_2},\,\ldots,\,\frac{p_r}{q_r}=\frac{a}{b}$$
739denote the continued fraction convergents of the
740rational number $a/b$.
741Then
742$$p_j q_{j-1} 743 - p_{j-1} q_j = (-1)^{j-1}\qquad \text{for }-1\leq j\leq r.$$
744If we let
745$g_j = \mtwo{(-1)^{j-1}p_j}{p_{j-1}}{(-1)^{j-1}q_j}{q_{j-1}}$,
746then $g_j\in\sltwoz$ and
747\begin{align*}
748  P(X,Y)\{0,a/b\}
749 &=P(X,Y)\sum_{j=-1}^{r}\left\{\frac{p_{j-1}}{q_{j-1}},\frac{p_j}{q_j}\right\}\\
750 &=\sum_{j=-1}^{r} g_j((g_j^{-1}P(X,Y))\{0,\infty\})\\
751 &=\sum_{j=-1}^{r} [g_j^{-1}P(X,Y),((-1)^{j-1}q_j,q_{j-1})].
752\end{align*}
753Note that in the $j$th summand, $g_j^{-1}P(X,Y)$, replaces $P(X,Y)$.
754Since $g_j\in\sltwoz$ and $P(X,Y)$ has integer coefficients,
755the polynomial $g_j^{-1}P(X,Y)$ also has integer coefficients,
756so no denominators are introduced.
757
758The continued fraction expansion $[c_1,c_2,\ldots,c_n]$
759of the rational number $a/b$ can be computed
760using the Euclidean algorithm.
761The first term, $c_1$, is the quotient'': $a = bc_1+r$,
762with $0\leq r < b$.
763Let $a'=b$, $b'=r$ and compute $c_2$ as
764$a'=b'c_2+r'$, etc., terminating when the
765remainder is $0$.  For example, the expansion
766of $5/13$ is $[0,2,1,1,2]$.
767The numbers $$d_i=c_1+\frac{1}{c_2+\frac{1}{c_3+\cdots}}$$
768will then be the (finite) convergents.
769For example if $a/b=5/13$, then the convergents are
770  $$0/1,\,\, 1/0,\,\, d_1=0,\,\, d_2=\frac{1}{2},\,\, d_3=\frac{1}{3},\,\, 771 d_4=\frac{2}{5},\,\, d_5=\frac{5}{13}.$$
772
773
774
775\subsection{Hecke operators on Manin symbols}%
776\index{Hecke operators!on Manin symbols}%
777\index{Manin symbols!and Hecke operators}%
778\label{subsec:heckeonmanin}%
779Thoerem~2 of \cite{merel:1585} gives a description of
780the Hecke operators~$T_n$
781directly  on the space of Manin symbols.
782This avoids the expense of first converting a Manin
783symbol to a modular symbol, computing~$T_n$ on the modular symbol,
784and then converting back.  For the reader's convenience, we very
785briefly recall Merel's\index{Merel} theorem here, along with
786an enhancement due to Cremona\index{Cremona}.
787
788As in~\cite[\S2.4]{cremona:algs}, define~$R_p$ as follows.
789When $p=2$,
790$$R_2 := \left\{\mtwo{1}{0}{0}{2}, 791 \mtwo{2}{0}{0}{1}, \mtwo{2}{1}{0}{1}, 792 \mtwo{1}{0}{1}{2}\right\}.$$
793When~$p$ is odd,~$R_p$ is the set of $2\times 2$ integer
794matrices $\abcd{a}{b}{c}{d}$ with determinant~$p$, and either
795\begin{enumerate}
796\item $a>|b|>0$, $d>|c|>0$, and $bc<0$; or
797\item $b=0$, and $|c|<d/2$; or
798\item $c=0$, and $|b|<a/2$.
799\end{enumerate}
800\begin{proposition}
801For $[P(X,Y),(u,v)]\in\sM_k(N,\eps)$ and~$p$ a prime, we have
802\begin{align*}T_p([P(X,Y),(u,v)])
803  &= \sum_{g\in R_p} [P(X,Y),(u,v)].g \\
804  &= \sum_{\abcd{a}{b}{c}{d}\in R_p} [P(aX+bY,cX+dY),(au+cv,bu+dv)],
805\end{align*}
806where the sum is restricted to matrices $\abcd{a}{b}{c}{d}$
807such that $\gcd(au+cv,bu+dv,N)=1$.
808\end{proposition}
809\begin{proof}
810For the case $k=2$ and an algorithm to compute $R_p$,
811see \cite[\S2.4]{cremona:algs}.
812The general case follows from~\cite[Theorem 2]{merel:1585} applied
813to the set~$\sS$ of~\cite[\S3]{merel:1585} by observing that
814when~$p$ is an odd {\em prime} $\sS_p'$ is empty.
815\end{proof}
816
817\subsection{The cuspidal and boundary spaces in terms of Manin symbols}%
818\index{Manin symbols!and cuspidal subspace}%
819\index{Manin symbols!and boundary space}%
820\index{Cuspidal modular symbols!and Manin symbols}%
821\index{Boundary modular symbols!and Manin symbols}%
822This section is a review  of Merel's\index{Merel} explicit description
823of the boundary map in terms of Manin symbols\index{Manin symbols}
824for $\Gamma=\Gamma_1(N)$
825(see~\cite[\S1.4]{merel:1585}).  In the next section, we
826describe a very efficient way to compute the boundary map.
827
828Let~$\cR$ be the equivalence relation
829on $\Gamma\backslash\Q^2$ which identifies
830the element
831$[\Gamma\smallvtwo{\lambda u}{\lambda v}]$
832with $\sign(\lambda)^k[\Gamma\smallvtwo{u}{v}]$,
833for any $\lambda\in\Q^*$.  Denote by $B_k(\Gamma)$
834the finite dimensional $\Q$-vector space
835with basis the equivalence classes
836$(\Gamma\backslash\Q^2)/\cR$.
837The dimension of this space is $\#(\Gamma\backslash\P^1(\Q))$.
838\begin{proposition}
839The map
840$$\mu:\sB_k(\Gamma)\ra B_k(\Gamma), 841\qquad P\left\{\frac{u}{v}\right\}\mapsto 842 P(u,v)\left[\Gamma\vtwo{u}{v}\right]$$
843is well defined and injective.
844Here $u$ and $v$ are assumed coprime.
845\end{proposition}
846Thus the kernel of $\delta:\sS_k(\Gamma)\ra \sB_k(\Gamma)$
847is the same as the kernel of $\mu\circ \delta$.
848\begin{proposition}\label{prop:boundary}
849Let $P\in V_{k-2}$ and $g=\abcd{a}{b}{c}{d}\in\sltwoz$.  We have
850$$\mu\circ\delta([P,(c,d)]) 851 = P(1,0)[\Gamma\smallvtwo{a}{c}] 852 -P(0,1)[\Gamma\smallvtwo{b}{d}].$$
853\end{proposition}
854
855
856\subsection{Computing the boundary map}%
857\index{Boundary map}%
858\label{sec:computeboundary}%
859In this section we describe how to compute the
860map $\delta:\sM_k(N,\eps)\ra B_k(N,\eps)$
861given in the previous section.
862The algorithm presented here
863generalizes the one in~\cite[\S2.2]{cremona:algs}.
864To compute the image of $[P,(c,d)]$, with
865$g=\abcd{a}{b}{c}{d}\in\sltwoz$,
866we must compute the class of $[\smallvtwo{a}{c}]$ and of
867$[\smallvtwo{b}{d}]$.
868Instead of finding a canonical form for cusps, we
869use a quick test for equivalence modulo scalars.
870In the following algorithm, by the $i$th standard
871cusp\index{Cusps!and boundary map} we mean
872the $i$th basis vector for a basis of $B_k(N,\eps)$.  The
873basis is constructed as the algorithm is called successively.
874We first give the algorithm, then prove the facts
875used by the algorithm in testing equivalence.
876
877\begin{algorithm}\label{alg:cusplist}
878\index{Algorithm for computing!cusps}
879Given a cusp $[\smallvtwo{u}{v}]$ this algorithm computes an
880integer~$i$ and a scalar~$\alp$ such that $[\smallvtwo{u}{v}]$ is
881equivalent to~$\alp$ times the $i$th standard cusp.  First, using
882Proposition~\ref{prop:cusp1} and Algorithm~\ref{alg:cusp1}, check
883whether or not $[\smallvtwo{u}{v}]$ is equivalent, modulo scalars, to
884any cusp found so far.  If so, return the index of the representative
885and the scalar.  If not, record $\smallvtwo{u}{v}$ in the
886representative list.  Then, using Proposition~\ref{prop:cuspdies},
887check whether or not $\smallvtwo{u}{v}$ is forced to equal zero by the
888relations.  If it does not equal zero, return its position in the list
889and the scalar~$1$.  If it equals zero, return the scalar~$0$ and the
890position~$1$; keep $\smallvtwo{u}{v}$ in the list, and record that it
891is zero.
892\end{algorithm}
893
894In the case considered in Cremona's book \cite{cremona:algs}, the
895relations between cusps involve only the trivial character, so they do
896not force any cusp classes to vanish.  Cremona gives the following two
897criteria for equivalence.
898\begin{proposition}[Cremona]\label{prop:cusp1}\index{Cremona}
899Let $\smallvtwo{u_i}{v_i}$, $i=1,2$ be written so that
900$\gcd(u_i,v_i)=1$.
901\begin{enumerate}
902\item There exists $g\in\Gamma_0(N)$ such that
903    $g\smallvtwo{u_1}{v_1}=\smallvtwo{u_2}{v_2}$ if and only if
904 $$s_1 v_2 \con s_2 v_1 \pmod{\gcd(v_1 v_2,N)},\, 905\text{ where s_j satisfies u_j s_j\con 1\pmod{v_j}}.$$
906\item There exists $g\in\Gamma_1(N)$ such that
907    $g\smallvtwo{u_1}{v_1}=\smallvtwo{u_2}{v_2}$ if and only if
908 $$v_2 \con v_1 \pmod{N}\text{ and } u_2 \con u_1 \pmod{\gcd(v_1,N)}.$$
909\end{enumerate}
910\end{proposition}
911\begin{proof}
912The first is Proposition 2.2.3 of \cite{cremona:algs}, and
913the second is Lemma 3.2 of \cite{cremona:gammaone}.
914\end{proof}
915
916\begin{algorithm}\label{alg:cusp1}%
917\index{Algorithm for computing!equivalent cusps}%
918Suppose $\smallvtwo{u_1}{v_1}$ and
919$\smallvtwo{u_2}{v_2}$
920are equivalent modulo $\Gamma_0(N)$.
921This algorithm computes a matrix $g\in\Gamma_0(N)$ such
922that $g\smallvtwo{u_1}{v_1}=\smallvtwo{u_2}{v_2}$.
923Let $s_1, s_2, r_1, r_2$ be solutions to
924$s_1 u_1 -r_1 v_1 =1$ and
925$s_2 u_2 -r_2 v_2 =1$.
926Find integers $x_0$ and $y_0$ such
927that $x_0v_1v_2+y_0N=1$.
928Let $x=-x_0(s_1v_2-s_2v_1)/(v_1v_2,N)$
929and $s_1' = s_1 + xv_1$.
930Then $g=\mtwo{u_2}{r_2}{v_2}{s_2} 931 \cdot \mtwo{u_1}{r_1}{v_1}{s_1'}^{-1}$
932sends $\smallvtwo{u_1}{v_1}$ to $\smallvtwo{u_2}{v_2}$.
933\end{algorithm}
934\begin{proof}
935This follows from the proof of Proposition~\ref{prop:cusp1} in
936\cite{cremona:algs}.
937\end{proof}
938
939
940To see how the~$\eps$ relations, for nontrivial~$\eps$,
941make the situation more complicated, observe that it is
942possible that $\eps(\alp)\neq \eps(\beta)$ but
943$$\eps(\alp)\left[\vtwo{u}{v}\right] =\left[\gamma_\alp \vtwo{u}{v}\right]= 944 \left[\gamma_\beta \vtwo{u}{v}\right]=\eps(\beta)\left[\vtwo{u}{v}\right];$$
945One way out of this difficulty  is to construct
946the cusp classes for $\Gamma_1(N)$, then quotient
947out by the additional~$\eps$ relations using
948Gaussian elimination. This is far too
949inefficient to be useful in practice because the number of
950$\Gamma_1(N)$ cusp classes can be unreasonably large.
951Instead, we give a quick test to determine whether or not
952a cusp vanishes modulo the $\eps$-relations.
953
954\begin{lemma}\label{lem:canlift}
955Suppose $\alp$ and $\alp'$ are integers
956such that $\gcd(\alp,\alp',N)=1$.
957Then there exist integers $\beta$ and $\beta'$,
958congruent to $\alp$ and $\alp'$ modulo $N$, respectively,
959 such that $\gcd(\beta,\beta')=1$.
960\end{lemma}
961\begin{proof}
962By \cite[1.38]{shimura:intro} the map
963$\SL_2(\Z)\ra\SL_2(\Z/N\Z)$ is surjective.
964By the Euclidean algorithm, there exist
965integers $x$, $y$ and $z$ such that
966$x\alp + y\alp' + zN = 1$.
967Consider the matrix
968$\abcd{y}{-x}{\alp}{\hfill\alp'}\in \SL_2(\Z/N\Z)$
969and take $\beta$, $\beta'$ to be the bottom
970row of a lift of this matrix to $\SL_2(\Z)$.
971\end{proof}
972
973\begin{proposition}\label{prop:cuspdies}\index{Cusps!criterion for vanishing}
974Let~$N$ be a positive integer and~$\eps$ a Dirichlet
975character\index{Dirichlet character!and cusps} of modulus~$N$.
976Suppose $\smallvtwo{u}{v}$ is a cusp with $u$ and $v$ coprime.
977Then $\smallvtwo{u}{v}$ vanishes modulo the relations
978$$\left[\gamma\smallvtwo{u}{v}\right]= 979\eps(\gamma)\left[\smallvtwo{u}{v}\right],\qquad 980\text{all \gamma\in\Gamma_0(N)}$$
981if and only if there exists $\alp\in(\Z/N\Z)^*$,
982with $\eps(\alp)\neq 1$, such that
983\begin{align*}
984 v &\con \alp v \pmod{N},\\
985 u &\con \alp u \pmod{\gcd(v,N)}.
986\end{align*}
987\end{proposition}
988\begin{proof}
989First suppose such an~$\alp$ exists.
990By Lemma~\ref{lem:canlift}
991there exists $\beta, \beta'\in\Z$ lifting
992$\alp,\alp^{-1}$ such that $\gcd(\beta,\beta')=1$.
993The cusp $\smallvtwo{\beta u}{\beta' v}$
994has coprime coordinates so,
995by Proposition~\ref{prop:cusp1} and our
996congruence conditions on~$\alp$, the cusps
997$\smallvtwo{\beta{}u}{\beta'{}v}$
998and $\smallvtwo{u}{v}$ are equivalent by
999an element of $\Gamma_1(N)$.
1000This implies that $\left[\smallvtwo{\beta{}u}{\beta'{}v}\right] 1001 =\left[\smallvtwo{u}{v}\right]$.
1002Since $\left[\smallvtwo{\beta{}u}{\beta'{}v}\right] 1003 = \eps(\alp)\left[\smallvtwo{u}{v}\right]$,
1004our assumption that $\eps(\alp)\neq 1$
1005forces $\left[\smallvtwo{u}{v}\right]=0$.
1006
1007Conversely, suppose $\left[\smallvtwo{u}{v}\right]=0$.
1008Because all relations are two-term relations, and the
1009$\Gamma_1(N)$-relations identify $\Gamma_1(N)$-orbits,
1010there must exists $\alp$ and $\beta$ with
1011  $$\left[\gamma_\alp \vtwo{u}{v}\right] 1012 =\left[\gamma_\beta \vtwo{u}{v}\right] 1013 \qquad\text{ and }\eps(\alp)\ne \eps(\beta).$$
1014Indeed, if this did not occur,
1015then we could mod out by the $\eps$ relations by writing
1016each $\left[\gamma_\alp \smallvtwo{u}{v} \right]$
1017in terms of  $\left[\smallvtwo{u}{v}\right]$, and there would
1018be no further relations left to kill
1019$\left[\smallvtwo{u}{v}\right]$.
1020Next observe that
1021$$1022\left[\gamma_{\beta^{-1}\alp} 1023 \vtwo{u}{v}\right] 1024 = \left[\gamma_{\beta^{-1}}\gamma_\alp 1025 \vtwo{u}{v}\right] 1026 = \eps(\beta^{-1})\left[\gamma_\alp 1027 \vtwo{u}{v}\right] 1028 = \eps(\beta^{-1})\left[\gamma_\beta 1029 \vtwo{u}{v}\right] 1030 = \left[\vtwo{u}{v}\right].$$
1031Applying Proposition~\ref{prop:cusp1} and
1032noting that $\eps(\beta^{-1}\alp)\neq 1$ shows
1033that $\beta^{-1}\alp$ satisfies the properties
1034of the $\alp$'' in the statement of the
1035proposition we are proving.
1036\end{proof}
1037
1038We enumerate the possible~$\alp$ appearing
1039in Proposition~\ref{prop:cuspdies} as follows.
1040Let $g=(v,N)$ and list the
1041$\alp=v\cdot\frac{N}{g}\cdot{}a+1$, for $a=0,\ldots,g-1$,
1042such that $\eps(\alp)\neq 0$.
1043
1044{\vspace{3ex}\em\par\noindent Working in the
1045plus one\index{Plus-one quotient} or
1046minus one quotient\index{Minus-one quotient}.}
1047Let~$s$ be a sign, either~$+1$ or~$-1$.
1048To compute $\sS_k(N,\eps)_s$ it is necessary
1049to replace $B_k(N,\eps)$ by its quotient modulo the
1051$\left[ \smallvtwo{-u}{\hfill v}\right] 1052= s \left[\smallvtwo{u}{v}\right]$
1053for all cusps $\smallvtwo{u}{v}$.
1054Algorithm~\ref{alg:cusplist} can be modified to deal
1055with this situation as follows.
1056Given a cusp $x=\smallvtwo{u}{v}$, proceed as
1057in Algorithm~\ref{alg:cusplist} and check if
1058either $\smallvtwo{u}{v}$ or $\smallvtwo{-u}{\hfill v}$
1059is equivalent (modulo scalars) to any cusp seen so far.  If not,
1060use the following trick to determine whether
1061the $\eps$ and $s$-relations
1062kill the class of $\smallvtwo{u}{v}$:
1063use the unmodified Algorithm~\ref{alg:cusplist}
1064to compute the scalars $\alp_1, \alp_2$ and
1065standard indices $i_1$, $i_2$ associated to
1066$\smallvtwo{u}{v}$ and $\smallvtwo{-u}{\hfill v}$, respectively.
1067The $s$-relation kills the class of  $\smallvtwo{u}{v}$
1068if and only if $i_1=i_2$ but $\alp_1\neq s\alp_2$.
1069
1070
1071\section{The complex torus attached to a modular form}%
1072\index{Complex torus}%
1073\index{Modular forms!associated complex torus}%
1074\label{sec:tori}%
1075Fix integers $N\geq 1$, $k\geq 2$, and let~$\eps$ be a mod~$N$
1076Dirichlet character\index{Dirichlet character}.
1077For the rest of this section assume that $\eps^2=1$.
1078
1079We construct a lattice in $\Hom(S_k(N,\eps),\C)$ that is invariant
1080under complex conjugation and under the action of the Hecke
1081operators.\index{Hecke operators} The quotient of
1082$\Hom(S_k(N,\eps),\C)$ by this lattice is a complex torus
1083$J_k(N,\eps)$, which is equipped with an action of the Hecke operators
1084and of complex conjugation.
1085
1086The reader may wish to compare our construction with a closely related
1087construction of Shimura\index{Shimura}~\cite{shimura:surles}.  Shimura
1089torus the structure of an abelian variety over~$\C$.  Note that his
1090torus is, a priori, different than our torus.  We do not know if
1091our torus has the structure of abelian variety over~$\C$.
1092
1093When $k=2$, the torus $J_2(N,\eps)$ is the set of complex points of an
1094abelian variety, which is actually defined over $\Q$; when $k>2$,
1095the study of these complex tori is of interest in trying to understand the
1096conjectures of Bloch and Kato (see \cite{bloch-kato})%
1097\index{Conjecture!Bloch and Kato}%
1098\index{Bloch and Kato conjecture} on motifs\index{Motifs} attached
1099to modular forms\index{Modular forms}.
1100
1101Let $\sS=\sS_k(N,\eps)$ (respectively, $S=S_k(N,\eps)$)
1102be the space of cuspidal modular symbols (respectively, cusp forms)
1103of weight~$k$, level~$N$, and character~$\eps$.
1104The Hecke algebra~$\T$\index{Hecke algebra!and integration pairing}
1105acts in a way compatible with the
1106integration pairing\index{Integration pairing!and complex torus}
1107$\langle\,,\,\rangle 1108 : S \cross \sS \ra \C$.
1109This pairing induces a $\T$-module
1110homomorphism $\Phi:\sS\ra S^*=\Hom_\C(S,\C)$,
1111called the \defn{period mapping}.%
1112\index{Period mapping|textit}
1113Because $\eps^2=1$, the $*$-involution\index{Star involution} preserves~$S$.
1114\begin{proposition}
1115The period mapping~$\Phi$\index{Period mapping!is injective}
1116is injective and $\Phi(\sS)$ is a lattice in~$S^*$.
1117\end{proposition}
1118\begin{proof}
1119By Theorem~\ref{thm:perfectpairing},
1120 $$\sS\tensor_{\R}\C\isom 1121 \Hom_\C(S\oplus \Sbar,\C).$$
1122Because $\eps^2=1$, we have $S = S_k(N,\eps;\R)\tensor_{\R}\C$.
1123Set $S_\R := S_k(N,\eps;\R)$ and likewise define $\Sbar_\R$.
1124We have
1125$$\Hom_\C(S\oplus \Sbar,\C) = 1126 \Hom_\R(S_\R \oplus \Sbar_\R,\R)\tensor_\R \C.$$
1127Let $\sS_{\R} = \sS_k(N,\eps;\R)$ and $\sS_{\R}^+$ be the
1128subspace fixed under~$*$.  By Proposition~\ref{prop:starpairing}
1129we have maps
1130$$\sS_{\R}^+ \ra \Hom_{\R}(S_{\R}\oplus\Sbar_\R,\R) 1131 \ra \Hom_{\R}(S_{\R},\R)$$
1132and
1133$$\sS_{\R}^- \ra \Hom_{\R}(S_{\R}\oplus\Sbar_\R,i\R) 1134 \ra \Hom_{\R}(S_{\R},i\R).$$
1135The map $\sS_{\R}^+\ra \Hom_{\R}(S_{\R},\R)$ is
1136an isomorphism: the point is that if
1137$\langle \bullet, x\rangle$, for $x\in \sS_{\R}^+$,
1138vanishes on $S_\R$ then it  vanishes on  the
1139whole of $S\oplus \Sbar$.  Likewise, the map
1140$\sS_{\R}^-\ra \Hom_{\R}(S_{\R},i\R)$
1141is an isomorphism.  Thus
1142$$\sS\tensor\R = \sS_{\R} \isom \Hom_{\R}(S_{\R},\R) 1143\oplus \Hom_{\R}(S_{\R},i\R) 1144\isom \Hom_{\C}(S,\C).$$
1145Finally, we observe that~$\sS$ is by definition
1146torsion free, which completes the proof.
1147\end{proof}
1148
1149The torus $J_k(N,\eps)$ fits into an exact sequence
1150$$0\lra \sS \xrightarrow{\quad\Phi\quad} 1151 \Hom_\C(S,\C) \lra J_k(N,\eps) \lra 0.$$
1152Let $f\in S$ be a newform and $S_f$ the complex vector
1153space spanned by the Galois conjugates of~$f$.
1154The period map $\Phi_f$ associated to~$f$ is the map
1155$\sS\ra \Hom_\C(S_f,\C)$
1156obtained by composing~$\Phi$ with restriction to $S_f$.
1157Set
1158  $$A_f := \Hom_\C(S_f,\C) / \Phi_f(\sS).$$
1159
1160We associate\label{pg:dual} to~$f$ a subtorus of~$J$ as follows.
1161\index{Complex torus!dual of}%
1162\index{Modular forms!associated subtorus}%
1163Let $I_f = \Ann_{\T}(f)$ be the annihilator
1164of~$f$ in the Hecke algebra\index{Hecke algebra}, and set
1165    $$\Adual_f := \Hom_\C(S,\C)[I_f]/\Phi(\sS[I_f])$$
1166where $\Hom_\C(S,\C)[I_f] = \intersect_{t \in I_f} \ker(t)$.
1167
1168The following diagram summarizes the tori just defined;
1169its columns are exact but its rows need not be.
1170\begin{equation}\label{dgm:uniformization}
1171\[email protected]=.9pc{
1172    0\ar[d]            &        0\ar[d]             &  0\ar[d]   \\
1173  \sS[I_f]\ar[r]\ar[dd] &  \sS\ar[r]\ar[dd]&\Phi_f(\sS)\ar[dd] \\
1174                      &                 &      \\
1175\Hom_\C(S,\C)[I_f]\ar[r]\ar[dd] &\Hom_\C(S,\C)\ar[r]\ar[dd] &\Hom_\C(S[I_f],\C)\ar[dd]\\
1176                      &                 &      \\
1178& J_k(N,\eps) \ar[r]\ar[d]& A_f \ar[d]\\
1179    0   &   0    &  0   \\
1180}\end{equation}
1181
1182
1183\subsection{The case when the weight is $2$}%
1184\index{Complex torus!in weight two}%
1185When $k=2$ and $\eps=1$ the above is just Shimura's\index{Shimura}
1186classical association of an abelian variety to a modular
1187form\index{Modular forms}; see~\cite[Thm.~7.14]{shimura:intro}
1188and~\cite{shimura:factors}.  In this case $A_f$ and $\Adual_f$ are
1189abelian varieties that are defined over~$\Q$.  Furthermore $A_f$ is an
1190\defn{optimal quotient}\index{Optimal quotient|textit} of~$J$, in the sense
1191that the kernel of the map $J\ra A_f$ is connected.
1192For a summary of the main results in this situation,
1193see Section~\ref{sec:optquoj0n}.
1194
1195
1196