CoCalc Public Fileswww / papers / thesis / src / algorithms.tex
Author: William A. Stein
Compute Environment: Ubuntu 18.04 (Deprecated)
1\comment{
2$Header: /home/was/papers/thesis/RCS/algorithms.tex,v 1.14 2000/05/15 00:13:18 was Exp$
3
4$Log: algorithms.tex,v$
5Revision 1.14  2000/05/15 00:13:18  was
6quick fix!
7
8Revision 1.13  2000/05/10 20:31:51  was
9done.
10
11Revision 1.12  2000/05/10 09:30:12  was
12indexing and cleaning up.
13
14Revision 1.11  2000/05/10 03:45:57  was
15Wrote an introduction.
16
17Revision 1.10  2000/05/09 22:47:19  was
18fixed modular degree notation m_ instead of \delta_
19
20Revision 1.9  2000/05/09 19:51:48  was
21Fixed section{The Cap} problem
22
23Revision 1.8  2000/05/09 19:49:45  was
24More details on the modular degree.
25
26Revision 1.7  2000/05/08 18:47:46  was
28
29Revision 1.6  2000/05/08 03:27:43  was
30Fixed errors pointed out by Hendrik.
31
32}
33
34\chapter{Applications of modular symbols}
35\label{chap:computing}
36In the previous chapter we introduced several spaces of modular
37symbols, and observations such as Manin's trick'' suggested that we
38could compute with them.  The duality between modular symbols and
39modular forms hints that modular symbols might be useful in computing
40information about modular forms.  In the present chapter, we gather
41together the fruits of our investigation into this connection.
42
43Sections~\ref{sec:computingmk}--\ref{sec:decomposemodsym} of this
44chapter give a method to compute the irreducible components of the
45spaces $\sM_k(N,\eps)$ of modular symbols.  In
46Section~\ref{sec:intersection} we observe that computing intersections
47of certain abelian varieties can be reduced to linear algebra
48over~$\Z$ by viewing the abelian varieties as complex tori and
49considering the appropriate diagrams.  In
50Sections~\ref{sec:ratperiod}, we continue this trend by pointing out
51that many invariants of the complex torus attached to a modular form
52can be computed without computing any approximate period lattices.  In
53Section~\ref{sec:torsionsubgroup}, we discuss well-known methods for
54computing both an upper and lower bound on the order of the torsion
55subgroup of certain abelian varieties.  Section~\ref{sec:moddeg}
56presents an algorithm for computing the modular degree of the complex
57torus associated to a newform.
58
59In Section~\ref{sec:ratpartformula} we aim squarely at the
60problem of gathering data related to the Birch and Swinnerton-Dyer
61conjecture\index{BSD conjecture!and $L(A,j)/\Omega_j$}
62and its generalizations, where we give a formula for the
63rational numbers $|L(A_f,j)/\Omega_j|$ attached to a newform.  In
64Section~\ref{sec:maninconstant} we compare the ratio computed in the
65previous section to the one considered in the Birch and
66Swinnerton-Dyer conjecture;\index{BSD conjecture}
67the two numbers differ by a Manin\index{Manin}
68constant, which we bound.  Finally, in Section~\ref{sec:analytic} we
69give algorithms for approximating the period lattice and related
70numerical quantities associated to a newform of arbitrary weight.
71
72\section{Computing the space of modular symbols}%
73\index{Modular symbols!computing}%
74\label{sec:computingmk}%
75\begin{definition}
76Let~$W$ be a subspace of a finite-dimensional vector space~$V$.
77To \defn{compute} the quotient $V/W$ means to
78give a matrix representing the projection $V\ra V/W$, with
79respect to some basis for~$V$ and some basis~$B$ for $V/W$, along with
80a lift to~$V$ of each element of~$B$.
81\end{definition}
82In other words, to compute $V/W$ means to create a
83reduction function that assigns
84to each element of~$V$ its canonical representative
85on the free basis''~$B$.
86
87Let~$N$ be a positive integer, fix a mod~$N$ Dirichlet
88character~$\eps$\index{Dirichlet character}, let
89$K:=\Q[\eps]$ be the smallest extension
90containing the values of~$\eps$, and  let $\O:=\Z[\eps]$.
91
92\begin{algorithm}\label{alg:MkNK}%
93\index{Algorithm for computing!space of modular symbols}
94Given a positive integer~$N$, a Dirichlet
95character~$\eps$\index{Dirichlet character},
96and an integer $k\geq 2$
97this algorithm computes $\sM_k(N,\eps;K)$.
98We compute the quotient presentation given
99in Theorem~\ref{thm:maninsymbols}
100in three steps.
101\begin{enumerate}
102\item Let $V_1$ be the finite-dimensional $K$-vector space
103generated by the Manin symbols\index{Manin symbols}\index{Manin}
104$[X^iY^{k-2-i}, (u,v)]$
105for $i=0,\ldots, k-2$ and $0\leq u,v < N$ with $\gcd(u,v,N)=1$.
106Let~$W_1$ be the subspace of~$V_1$ generated by all differences
107$$[X^iY^{k-2-i}, (\lambda u,\lambda v)] - 108\eps(\lambda)[X^iY^{k-2-i}, (u, v)].$$
109Because all relations are two-term, it
110is easy to compute $V_2:=V_1/W_1$.
111In computing this quotient, we do not have to
112explicitly compute the {\em large} matrix representing
113the linear map $V_1\ra V_2$, as it can be replaced by a suitable
114reduction procedure'' involving
115arithmetic in $\Z/N\Z$.
116\item
117Let~$\sigma$ act on the set of
118Manin symbols as in Section~\ref{sec:maninsymbols}; thus
119$$[X^iY^{k-2-i}, (u, v)]\sigma = (-1)^i[Y^iX^{k-2-i}, (v,-u)].$$
120Let~$W_2$ be the subspace of~$V_2$ generated by the sums
121$x + x\sigma$ for $x\in V_2$.
122Because all relations are two-term relations, it is
123easy to compute $V_3 := V_2/W_2$.
124\item Let~$\tau$ act on Manin symbols as in
125Section~\ref{sec:maninsymbols};
126thus
127$$[X^iY^{k-2-i}, (u, v)]\tau = 128 [(-Y)^i(X-Y)^{k-2-i}, (v,-u-v)].$$
129Note that the symbol on the right can be written as a sum
130of generating Manin symbols\index{Manin symbols}.
131Let~$W_3$ be the subspace of~$V_3$ generated by the sums
132$x + x\tau + x\tau^2$
133where~$x$ varies over the images of a basis of~$V_2$
134({\em not} just a basis for $V_3$!).
135Using some form of Gaussian elimination, we compute $V_3/W_3$.
136Finally, $\sM_k(N,\eps;K)\ncisom V_3/W_3$.
137\end{enumerate}
138\end{algorithm}
139\begin{proof}
140For $\lambda \in (\Z/N\Z)^*$, denote by $\langle \lambda \rangle$ the right
141action of~$\lambda$ on Manin symbols\index{Manin symbols}; thus
142   $$[X^iY^{k-2-i}, (u,v)]\langle \lambda \rangle 143 = [X^iY^{k-2-i}, (\lambda{}u,\lambda{}v)].$$
144By Theorem~\ref{thm:maninsymbols} the space $\sM_k(N,\eps;K)$ is isomorphic
145to the quotient of the vector spaces~$V_1$ of Step~1 modulo the relations
146$x+x\sigma=0$, $x+x\tau+x\tau^2=0$, and $x\langle \lambda \rangle=\lambda x$
147as~$x$ varies over all Manin symbols and~$\lambda$ varies over $(\Z/N\Z)^*$.
148
149As motivation, we note that a naive
150computation of $V_1$ modulo the $\sigma$, $\tau$, and
151$\langle \lambda\rangle$ relations using Gaussian elimination
152is far too inefficient.  This is why we compute the
153quotient in three steps.  The complexity of Steps~1 and
154Steps~2 are negligible. The difficulty occurs in Step~3;
155at least the relations of this step occur in a space of dimension much
156smaller than that of~$V_1$.
157
158To see that the algorithm is correct, it is necessary only to observe
159that $\sigma$ and $\tau$ both commute with all diamond-bracket operators
160$\langle \lambda \rangle$; this is an immediate consequence of the
161above formulas.  We remark that in Step~3 it is in
162general {\em necessary} to compute the quotient
163by all relations $x + x\tau + x\tau^2$ with~$x$ the image of a basis
164vector for $V_2$ instead
165of just~$x$ in~$V_3$ because~$\sigma$ and~$\tau$ do not commute.
166\end{proof}
167
168\begin{remark}
169In implementing the above algorithm, one should take special care in
170Steps~1 and~2 because the relations can together force certain of the
171Manin symbols to equal~$0$.  For example, there might be relations of
172the form $x_1+x_2=0$ and $x_1-x_2=0$ which together force $x_1=x_2=0$.
173\end{remark}
174
175\begin{remark}
176To compute the plus-one quotient
177$\sM_k(N,\eps;K)_{+}$, it
178is necessary to modify Step~2 of Algorithm~\ref{alg:MkNK}
179by including in~$W_2$ the differences $x - x I$
180where $I=\abcd{-1}{0}{\hfill 0}{1}$, and
181$$[X^iY^{k-2-i}, (u,v)] I 182 = (-1)^i[X^iY^{k-2-i}, (-u,v)].$$
183Likewise, to compute the minus-one quotient we include the sums $x + x I.$
184Note, as in the remarks in the proof of Algorithm~\ref{alg:MkNK},
185we can not add in the~$I$ relations in Step~1 because~$I$ and~$\sigma$
186do not commute.
187\end{remark}
188
189
190\begin{algorithm}\label{alg:MkNO}%
191\index{Algorithm for computing!integral modular symbols}%
192Given a positive integer~$N$, a Dirichlet
193character~$\eps$\index{Dirichlet character}, and an integer $k\geq 2$,
194this algorithm computes the $\O$-modules $\sM_k(N,\eps)$ and
195$\sS_k(N,\eps)$.  (We assume as given algorithms for performing
196standard operations on $\O$-modules.)
197\begin{enumerate}
198\item Using Algorithm~\ref{alg:MkNK}
199compute the $K$-vector space $V:=\sM_k(N,\eps;K)$.
200\item Compute the $\O$-lattice~$L$ in~$V$ generated
201by the classes of the finitely many symbols $[X^iY^{k-2-i}, (u,v)]$
202for $i=0,\ldots, k-2$ and $0\leq u,v < N$ with $\gcd(u,v,N)=1$.
203It is only necessary to take one symbol in each
204$\eps$-equivalence class, so there are
205$(k-2+1)\cdot\#\P^1(\Z/N\Z)$ generating symbols.
206This computes $\sM_k(N,\eps)$.
207\item To compute the submodule $\sS_k(N,\eps)$ of~$L$, we use
208the algorithm of Section~\ref{sec:computeboundary}
209to compute the
210boundary map $\delta:\sM_k(N,\eps;K)\ra B_k(N,\eps;K)$.
211Then $\sS_k(N,\eps)$ is the kernel of~$\delta$ restricted
212to the lattice~$L$.
213\end{enumerate}
214
215\end{algorithm}
216
217As a check, using the formulas of Section~\ref{sec:dimensionformulas},
218we compute the dimension of the space $S_k(N,\eps)$ of cusp
219forms and compare with the dimension of $\sS_k(N,\eps;K)$
220computed in Algorithm~\ref{alg:MkNO}.  The latter dimension must
221equal twice the former one.
222
223
224\section{Computing the Hecke algebra}%
225\index{Hecke algebra!computation of}%
226\label{sec:computinghecke}%
227
228In this section we give an upper bound on the number of Hecke
229operators needed to generate the Hecke algebra%
230\index{Hecke algebra!generators as module}
231as a $\Z$-module.  The bound on Hecke
232operators\index{Hecke operators} is an application
233of~\cite{sturm:cong}, which was described to the author by
234Ribet\index{Ribet} and Agashe\index{Agashe} when $k=2$ and the level
235is prime.  There are much better bounds on the number of Hecke
236operators needed to generate the Hecke algebra%
237\index{Hecke algebra!generators as ring}
238as a {\em ring}, but we do not investigate them here.
239
240Let~$\Gamma$ be a subgroup of $\SL_2(\Z)$ that contains $\Gamma_1(N)$
241for some~$N$.  Let $S_k(\Gamma;\C)$ be the space of weight-$k$ cuspforms
242for~$\Gamma$, and let $\T\subset\End(S_k(\Gamma;\C))$ be the
243corresponding Hecke algebra.  We now give a bound~$r$ such
244that the Hecke operators~$T_n$\index{Hecke operators}, with $n\leq r$, generate~$\T$ as a
245$\Z$-module.
246
247For any ring $R\subset \C$, let $S_k(\Gamma;R)$ denotes the space of
248cuspforms for~$\Gamma$ with Fourier
249coefficients in~$R$.
250Since $S_k(\Gamma;\C) = S_k(\Gamma;\Z)\tensor_\Z \C$, it makes sense to define
251     $$S_k(\Gamma;R):=S_k(\Gamma;\Z)\tensor_{\Z} R$$
252for {\em any} ring $R$.
253The following proposition is well known.
254\begin{proposition}\label{prop:perfectpair}
255For any ring~$R$, the pairing
256$$\T_R\tensor_RS_k(N;R) \ra R$$
257that sends $(T,f)$ to $a_1(Tf)$
258is a perfect pairing, where
259$\T_R = \T\tensor_{\Z} R$.  Furthermore, we have $(T_n,f)=a_n(f)$, where $T_n$ is
260the $n$th Hecke operator.
261\end{proposition}
262
263Let
264      $$\mu = [\sltwoz:\Gamma],$$
265and denote by $\lceil{}x\rceil$ the smallest integer $\geq x$.
266\index{Bound of!Sturm}\index{Sturm bound}
267\begin{theorem}[Sturm]
268\label{thm:sturm}
269Let~$\lambda$ be a prime ideal in the ring~$\O$ of integers in some
270number field.  If $f\in S_k(\Gamma;\O)$ satisfies
271$a_n(f)\con 0\pmod{\lambda}$ for $n\leq \lceil{}\frac{k}{12}\mu\rceil$,
272then  $f\con 0\pmod{\lambda}$.
273\end{theorem}
274\begin{proof}
275Theorem 1 of \cite{sturm:cong}.
276\end{proof}
277\begin{proposition}\label{prop:determine}
278If $f\in S_k(\Gamma)$ satisfies
279 $a_n(f)=0$ for
280 $n\leq r=\left\lceil\frac{k}{12}\mu\right\rceil$,
281then $f=0$.
282\end{proposition}
283\begin{proof}
284We must show that the composite map
285$S_k(\Gamma)\hookrightarrow\C[[q]]\into\C[[q]]/(q^{r+1})$
286is injective.  Because~$\C$ is a flat $\Z$-module and
287$S_k(\Gamma;\Z)\tensor\C = S_k(\Gamma)$, it suffices
288to show that the map $F:S_k(\Gamma;\Z)\into\Z[[q]]/(q^{r+1})$ is injective.
289Suppose $F(f)=0$, and let~$p$ be a prime number.
290Then $a_n(f)=0$ for $n\leq r$, hence plainly
291$a_n(f)\con 0\pmod{p}$ for any such~$n$.
292Theorem~\ref{thm:sturm} implies that $f\con 0\pmod{p}$.
293Duplicating this argument shows that the coefficients
294of~$f$ are divisible by all primes~$p$, so they are~$0$.
295\end{proof}
296
297\begin{theorem}\label{thm:bound}
298As a $\Z$-module, $\T$ is generated by $T_1,\ldots,T_r$,
299where $r=\lceil \frac{k}{12}\mu \rceil$.
300\end{theorem}
301\begin{proof}
302Let~$Z$ be the submodule of~$\T$ generated by
303$T_1,T_2,\ldots,T_r$.  Consider the exact sequence of
305  $0\into Z \xrightarrow{\,i\,} \T \into \T/Z \into 0.$
306Let~$p$ be a prime and tensor this sequence with~$\F_p$ to obtain
307the exact sequence
308  $$Z\tensor \F_p\xrightarrow{\,\overline{i}\,} 309 \T\tensor\F_p \into (\T/Z)\tensor\F_p\into 0.$$
310Put $R=\Fp$ in Proposition~\ref{prop:perfectpair}, and suppose that
311$f\in S_k(N,\Fp)$ pairs to~$0$ with each of $T_1,\ldots, T_r$.
312Then by Proposition~\ref{prop:perfectpair}, $a_m(f)=a_1(T_m f)=0$ in
313$\Fp$ for each~$m$, $1\leq m\leq r$.  Theorem~\ref{thm:sturm}
314then asserts that $f = 0$. Thus the pairing, when restricted
315to the image of $Z\tensor\Fp$ in $\T\tensor\Fp$, is also perfect.  Thus
316$\dim_{\Fp} \overline{i}(Z\tensor\Fp) 317 = \dim_{\Fp} S_k(N,\Fp)= \dim_{\Fp} \T\tensor\Fp,$
318so $(\T/Z) \tensor \F_p = 0$; repeating this argument for
319all~$p$ shows that $\T/Z=0$.
320\end{proof}
321
322% dirichlet.tex
323\section{Representing and enumerating Dirichlet characters}
324Recall that a
325\defn{Dirichlet character}%
326\index{Dirichlet character}
327is a homomorphism $\eps:(\Z/N\Z)^*\ra \C^*$.
328
329The following lemma is well known.
330\begin{lemma}
331If~$p$ is an odd prime, then $(\Z/p^n\Z)^*$ is a cyclic group.
332The group $(\Z/2^n\Z)^*$ is generated by~$-1$ and~$5$.
333\end{lemma}
334We use the following representation of Dirichlet characters.
335Factor~$N$ as a product of prime powers:  $N=\prod_{i=1}^r p_i^{e_i}$ with
336$p_i < p_{i+1}$ and each $e_i>0$; then
337$(\Z/N\Z)^* \isom \prod_{i=1}^r (\Z/p_i^{e_i}\Z)^*$.
338If $p_i$ is odd then the lemma implies that $(\Z/p_i^{e_i}\Z)^*$ is cyclic.
339If $p_1=2$, then $(\Z/p_1^{e_1}\Z)^*$ is a product
340$\langle -1 \rangle \cross \langle 5 \rangle$
341of two cyclic groups, both possibly trivial.
342For each~$i$, we let $a_i\in(\Z/p_i^{e_i}\Z)^*$ be the smallest generator of
343the $i$th factor $(\Z/p_i^{e_i}\Z)^*$.  If $p_1=2$, let $a_1$ and $a_2$
344correspond to the two factors $\langle -1 \rangle$ and
345$\langle 5 \rangle$, respectively; then $a_3$ corresponds to $p_2$, etc.
346Here~$a_i$ is smallest in the
347sense that the minimal lift $\tilde{a}_i\in\Z_{>0}$ is smallest.
348Let~$n$ be the exponent of $(\Z/N\Z)^*$, and
349let $\zeta=e^{2\pi i /n}\in \C^*$.
350To give~$\eps$ is the same as giving the images of each generator
351of~$a_i$ as a power of~$\zeta$.  We thus represent~$\eps$ as
352a vector of elements of~$\C^*$ with respect to a canonically chosen,
353but unnatural, basis.
354
355Alternatively, the vector representing a character~$\eps$ can be equivalently
356viewed as a  vector in $(\Z/n\Z)^r$, where again~$n$ is the exponent of $(\Z/N\Z)^*$.
357Such a vector represents a character if and only if the $i$th component
358of the vector has additive order
359dividing $\vphi(p_i^{e_i})$.  If $p_1=2$, then
360there are $r+1$ entries instead of~$r$ entries, and the condition
361is suitably modified.
362If a vector $v=[d_1,\ldots,d_r]$ represents a character~$\eps$,
363then each of the Galois conjugate characters is represented
364by $[md_1,\ldots,md_r]$ where~$m$ varies over elements of
365$(\Z/n\Z)^*$.
366
367
368When performing actual machine computations, we work in the smallest
369field that contains all of the values of~$\eps$.
370Thus if $d=\gcd(d_1,\ldots,d_r,n)$, then we work in the subfield
371$\Q(\zeta^d)$, which is cheaper than working in $\Q(\zeta)$.
372
373It is sometimes important to work in characteristic~$\ell$.
374Then the notation is as above, except~$\zeta$ is replaced by a
375primitive $m$th root of unity, where~$m$ is the prime-to-$\ell$
376part of~$n$.   Note that the primitive
377$n$th roots of unity in characteristic~$\ell$ need not be conjugate;
378for example, both~$2$ and~$3$ are square roots of~$-1$ in $\F_5$, but
379they are not conjugate.  Thus we must specify~$\zeta$ as part
380of the notation when giving a mod~$\ell$ Dirichlet character.
381
382\begin{example}
383Suppose~$N=p$ is an odd prime.
384The group of mod~$p$ Dirichlet characters (in characteristic~$0$)
385is isomorphic to
386$\Z/(p-1)\Z$, and two characters~$a$ and~$b$ are Galois
387conjugate if and only if there is an element $x\in(\Z/(p-1)\Z)^*$
388such that $xa=b$.
389A character is determined up to Galois conjugacy by its order,
390so the set of classes of mod~$p$ Dirichlet characters are
391in bijection with the set of divisors~$d$ of $p-1=\#(\Z/p\Z)^*$.
392
393Let $p$ be an odd prime.  The
394quadratic mod~$p$ character is denoted $[(p-1)/2]$.
395The quadratic mod~$2p$ character is denoted by
396$[0,0,(p-1)/2]$; the quadratic mod~$4p$ character is denoted
397$[(p-1)/2,0,(p-1)/2]$.  If $n\geq 3$, then the exponent of
398$(\Z/2^n\Z)^*$ is $2^{n-2}$, so the nontrivial
399mod~$2^n$ character that factors through $(\Z/4\Z)^*$ is denoted
400$[2^{n-3},0]$.
401\end{example}
402
403\begin{definition}\index{Dirichlet character!conductor of|textit}%
404\index{Conductor of Dirichlet character|textit}%
405The {\em conductor} of a character $\eps:(\Z/N\Z)^*\ra \C^*$
406is the smallest divisor~$M$ of~$N$ such that~$\eps$ factors through
407the natural reduction map $(\Z/N\Z)^*\ra (\Z/M\Z)^*$.
408\end{definition}
409
410For simplicity, we assume that~$N$ is odd.
411To compute the conductor of~$\eps$, let~$v$ be the vector in
412$(\Z/n\Z)^r$ that represents $\eps$, as above.
413Since  both
414$(\Z/p_i^{e_i}\Z)^*$ and $(\Z/p_i^d\Z)^*$ are
415cyclic and the reduction map is surjective,
416we find that $p_i^d$, with $d\leq e_i$,
417divides the conductor of~$\eps$  if and only if
418the $i$th component of~$v$ has additive order
419dividing $\vphi(p_i^{d})$.   We can thus compute the
420power of $p_i$ dividing the conductor of~$\eps$ by
421computing the smallest~$d$ such that $p_i^d \con p_i^{d-1}$
422modulo the order of the $i$th component of~$v$.
423
424
425\section{The dimension of $S_k(N,\eps)$}%
426\index{Dimension of $S_k(N,\eps)$}%
427\label{sec:dimensionformulas}%
428An explicit formula for the dimension of $S_k(N,\eps)$ is given in
429\cite{cohen-oesterle:dimensions}, without proof.
430For the reader's convenience, we reproduce it here.
431\begin{theorem}[Cohen-Oesterl\'{e}]
432Let~$k\geq 2$ be an integer and $\eps:(\Z/N\Z)^*\ra\C^*$ be a Dirichlet character
433such that $\eps(-1)=(-1)^k$.  Then
434\begin{align*}
435\dim S_k(N,\eps) =
436 \delta &+
437  \frac{k-1}{12}\cdot N \cdot \prod_{p\mid N}\left(1+\frac{1}{p}\right)
439  &+\gamma_k\hspace{-5ex}\sum_{\{ x \in (\Z/N\Z)^* \,:\,  x^2+1 =  0\}} \hspace{-5ex}\eps(x)
441\sum_{\{ x \in (\Z/N\Z)^* \,:\, x^2+x+1= 0\}} \hspace{-5ex}\eps(x).
442\end{align*}
443Let~$f$ be the conductor of~$\eps$, i.e., the smallest~$M$
444such that~$\eps$ factors through $(\Z/M\Z)^*$.
445If $p\mid N$, then $r_p$ (resp. $s_p$) denotes the exponent
446of~$p$ in the prime factorization of~$N$ (resp.~$f$).
447Furthermore,
448\begin{align*}
449\lambda(r_p,s_p,p)
450 &:= \begin{cases}
451   p^{r'}+p^{r'-1} &
452            \text{if } 2s_p \leq r_p = 2r'\\
453   2p^{r'}   & \text{if } 2s_p \leq r_p=2r'+1\\
454   2p^{r_p-s_p} & \text{if } 2s_p > r_p
455\end{cases} \\
456\gamma_k &:= \begin{cases}
457    0 & \text{if $k$ is odd}\\
458    -\frac{1}{4} & \text{if } k\con 2\pmod{4}\\
459    \frac{1}{4} & \text{if } k\con 0\pmod{4}
460\end{cases} \\
461\mu_k &:= \begin{cases}
462    0 & \text{if }k\con 1\pmod{3}\\
463    -\frac{1}{3} & \text{if } k\con 2\pmod{3}\\
464    \frac{1}{3} & \text{if } k\con 0\pmod{3}
465\end{cases} \\
466  \delta &:= \begin{cases}
467           1 &\text{if $k=2$ and $\eps$ is trivial}\\
468           0 &\text{otherwise}
469\end{cases}
470\end{align*}
471\end{theorem}
472\comment{
473An alternative, more cumbersome, way to compute the dimension
474of $S_k(N,\eps)$ is to compute the trace of $T_1$ using the
475trace formula; see~\cite{hijikata:trace}, where the formula is
476given, along with a proof.  The author of this thesis has done this and has
477found that the resulting formulas look very similar; the answers given
478are the same, but he was not able to simplify the trace
479formula enough so that its evaluation is nearly as fast as
480the Cohen-Oesterl\'e formula above.
481}
482
483\section{Decomposing the space of modular symbols}
484\label{sec:decomposemodsym}
485
486Consider the space $\sS_k(N,\eps)$ of cuspidal modular symbols
487of level~$N$ and character~$\eps$ over $K=\Q(\eps)$.
488In this section we describe how
489to decompose the new part of $\sS_k(N,\eps)$
490as a direct sum of $\T$-modules corresponding to the Galois conjugacy
491classes of newforms with character~$\eps$.  As an application, we can
492compute the $q$-expansions of the normalized cuspidal newforms of
493level $N$ and character $\eps$.  Using the theory of
494Atkin-Lehner~\cite{atkin-lehner} as extended by
495Li~\cite{winnie:newforms}, it is then possible to construct a basis
496for the space $S_k(N,\eps;\C)$ of cusp forms.
497
498The algorithm is, for the most part, a straightforward generalization
499of the method used by Cremona~\cite{cremona:algs}\index{Cremona} to
500enumerate the $\Q$-rational weight-two newforms corresponding to
501modular elliptic curves.  Nevertheless, we present several tricks
502learned in the course of doing computations, which speed up the
503algorithm.  One useful trick that Cremona also made use of
504is to work in the space
505dual to modular symbols\index{Modular symbols} as
506described in the next section.
507
508\subsection{Duality}
509Let $K=\Q[\eps]$, and
510let $\sS_k(N,\eps;K)^\dual$ denote $\Hom_K(\sS_k(N,\eps;K),K)$
511equipped with its natural right $\T$-action: for
512$\vphi\in\sS_k(N,\eps;K)^\dual$,
513   $$(\vphi T)(x) = \vphi(Tx).$$
514The natural pairing
515 \begin{equation}\label{eqn:pairing}
516\langle\,,\,\rangle:\sS_k(N,\eps;K)^\dual \cross \sS_k(N,\eps;K) \ra K
517\end{equation}
518given by $\langle\vphi,x\rangle = \vphi(x)$
519satisfies
520  $\langle\vphi{}T,x\rangle = \langle\vphi ,T{}x\rangle$.
521
522Viewing the elements $T\in\T$ as sitting inside
523$\End(\sS_k(N,\eps;K))$,
524the transpose map $T\mapsto T^t$
525allows us to view $\sS_k(N,\eps;K)^\dual$
526as a left $\T$-module.
527\begin{proposition}\label{prop:heckeduality}
528Let $V\subset \sS_k(N,\eps;K)^{\new}$ be an irreducible
529new $\T$-submodule and set $I=\Ann_\T V$.
530Then the characteristic polynomial of each  $T_p$ on
531$\sS_k(N,\eps;K)^{\dual}[I]$ is the
532same as the characteristic polynomial of $T_p$ on~$V$.
533\end{proposition}
534\begin{proof}
535We may assume for the purposes of proving the proposition that $K=\Qbar$.
536There is a basis of simultaneous $\T$-eigenvectors for
537$\sS_k(N,\eps;K)^{\new}$.  With respect to this basis,~$\T$
538acts via diagonal matrices.   The systems of eigenvalues coming
539from the old subspace are distinct from the systems of
540eigenvalues on the new space.  Thus the dimension of
541$\sS_k(N,\eps;K)^{\dual}[I]$
542is the same as the dimension of~$V$, instead of being too large.
543The proposition now follows by noting that the characteristic polynomial
544of a matrix is the same as the characteristic polynomial of its
545transpose.
546\end{proof}
547
548The degeneracy maps\index{Degeneracy maps} $\alp_t$ and $\beta_t$ of
549Section~\ref{sec:degeneracymaps} give rise to
550maps $\alp_t^{\dual}$ and $\beta_t^{\dual}$
551between the dual spaces and having
552the dual properties to those of $\alp_t$ and $\beta_t$.
553In particular, they commute with the Hecke
554operators\index{Hecke operators!and degeneracy maps}
555$T_p$ for $p$ prime to $N$.
556The new and old subspace\index{New subspace}\index{Old subspace}
557of $\sS_k(N,\eps;K)^\dual$
558are defined as in Definition~\ref{def:newandoldsymbols}.
559
560\begin{algorithm}\label{alg:decompmknew}%
561\index{Algorithm for computing!decomposition of space of modular symbols}%
562This algorithm computes a decomposition
563of $\sS_k(N,\eps;K)^{\dual\new}$ into irreducible submodules $V$.
564
565Using Algorithm~\ref{alg:MkNK} compute $\sS_k(N,\eps;K)$.
566Then compute the maps $\beta_t$ using Algorithm~\ref{alg:degenreps}
567and intersect the transposes of their kernels in order to
568obtain $\sS_k(N,\eps)^{\dual\new}$.
569Compute the boundary map $\delta:\sS_k(N,\eps;K)\ra B_k(N,\eps;K)$
570using Algorithm~\ref{alg:cusplist}.
571We cut out the cuspidal submodule $\sS_k(N,\eps;K)^{\dual\new}$
572using the Hecke operators,\index{Hecke operators}
573Algorithm~\ref{alg:efficienttpdual},
574and Proposition~\ref{prop:heckeduality}.
575Set $p=2$ and perform the following steps.
576\begin{enumerate}
577\item Using Algorithm~\ref{alg:efficienttpdual},
578compute a matrix $A$ representing the Hecke
579operator $T_p$\index{Hecke operators}
580on $\sS_k(N,\eps;K)^{\dual\new}$.
581\item Compute and factor the characteristic polynomial~$F$ of~$A$.
582\item For each irreducible factor~$f$ of~$F$
583compute $V_f = \ker(f(A))$.
584Then, compute the $+1$ and $-1$ eigen-subspaces $V_f^+$ and $V_f^-$
585for the star involution.  Let~$W$ denote one of these two eigen-subspaces,
586and use the following criteria
587to determine whether or not~$W$ is irreducible:
588\begin{enumerate}
589\item If~$p$ is greater than the Sturm
590bound\index{Sturm bound}\index{Bound of!Sturm}
591(see Theorem~\ref{thm:bound}) then~$W$
592must be irreducible.
593\item
594If the characteristic polynomial of some element $T\in \T$
595acting on $W$ is irreducible, then~$W$ is irreducible.
596\end{enumerate}
597\item If $W$ is irreducible, record~$W$ and consider
598the next factor of the characteristic polynomial in step~3.  Otherwise,
599replace~$p$ by the next prime larger than~$p$ and replace
600$\sS_k(N,\eps;K)^{\dual\new}$ by $W$,
601then repeat the above sequence of steps, beginning with step~1.
602\end{enumerate}
603\end{algorithm}
604
605
606\subsection{Efficient computation of Hecke operators on the dual space}%
607\index{Hecke operators!computation on subspace of dual}%
608\index{Algorithm for computing!Hecke operators on the dual}%
609In this section we give a method for computing the action
610of the Hecke operators $T_p\in\T$ on
611an invariant subspace
612$V\subset \sS_k(N,\eps;K)^{\dual}$.
613A naive way to compute the right action of $T_p$ on $V$
614is to compute a matrix representing $T_p$ on $\sS_k(N,\eps;K)$,
615transpose to obtain $T_p$ on $\sS_k(N,\eps;K)^\dual$,
616and then restrict to~$V$ using Gaussian elimination.
617To compute $T_p$ on $\sS_k(N,\eps;K)$, observe that $\sS_k(N,\eps;K)$
618has a basis $e_1,\!\ldots,e_n$, where each $e_i$
619is a Manin symbol\index{Manin symbols} $[P,(c,d)]$, and that the action
620of $T_p$ on $[P,(c,d)]$ can be computed using
621Section~\ref{subsec:heckeonmanin}.
622
623In practice, $d=\dim V$ will often be much less than~$n$;
624we now describe how to compute $T_p$ on~$V$ in $d/n$ of the
625time it takes using the above naive method.  This is a
626substantial savings when~$d$ is small.
627Transposing the injection
628$V\hookrightarrow \sS_k(N,\eps;K)^{\dual}$,
629we obtain a surjection $\sS_k(N,\eps;K)\ra V^\dual$.
630There exists a subset $e_{i_1},\!\ldots, e_{i_d}$
631of the $e_i$ whose image forms
632a basis for $V^\dual$.   With some care, it is then possible
633to compute $T_p$ on $V^{\dual}$ by computing $T_p$ on each of
634$e_{i_1},\!\ldots, e_{i_d}$.
635
636In the rest of this section, we
637describe in terms of matrices a definite way to carry out this
638computation.
639Let~$V$ be an $n\times m$ matrix whose rows generate an
640$n$-dimensional subspace of an $m$-dimensional space of row vectors.
641Let~$T$ be an $m\times m$-matrix and suppose that~$V$ has rank~$n$ and
642that $VT$ is contained in the row space of~$V$.  Let~$E$ be an
643$m\times n$ matrix with the property that the $n\times n$ matrix $VE$
644is invertible, with inverse~$D$.
645\begin{proposition}
646$VT = VTEDV.$
647\end{proposition}
648\begin{proof}
649Observe that
650 $$V(EDV) = (VED)V = IV = V.$$
651Thus right multiplication by $EDV$
652      $$v \mapsto vEDV$$
653induces the {\em identity map} on the row space of $V$.
654Since $VT$ is contained in the row space of $V$, we have
655                     $$(VT)EDV = VT,$$
656as claimed.
657\end{proof}
658
659We have not computed $T$, but we can
660compute $T$ on each basis element $e_1,\ldots,e_n$
661of the ambient space--unfortunately, $n$ is extremely large.
662Our problem: quickly compute the action of
663$T^t$ on the invariant subspace spanned
664by the rows of $V$.  Can this be done without
665having to compute $T$ on all $e_i$?
666Yes,  the following algorithm shows how using
667a subset of only $d=\dim V$ of the $e_i$.
668
669\begin{algorithm}\label{alg:efficienttpdual}%
670\index{Algorithm for computing!Hecke operators on the dual}%
671Let~$T$ be any linear transformation
672which leaves~$V$ invariant and for
673which we can compute $T(e_i)$ for $i=1,\ldots, d$.
674This algorithm computes the matrix representing the
675action of $T$ on $V$ while computing $T(e_i)$ for
676only $\dim V$ of the~$i$.
677
678Choose any $m\times n$ matrix~$E$ whose columns are
679sparse linear combinations of the $e_i$ and such that
680$VE$ is invertible.
681For this we find a set of positions so that elements of the space
682spanned by the columns of~$V$ are determined by the entries in
683these spots. This is accomplished by row reducing, and setting~$E$
684equal to the pivot columns.
685Using Gaussian elimination, compute the inverse~$D$ of the
686$n\times n$ matrix $VE$.
687The matrix representing the action of~$T$ with respect
688to~$V$ is then
689  $$V(TE)D=V(TE)(VE)^{-1}.$$
690\end{algorithm}
691\begin{proof}
692Let~$A$ be any matrix so that
693$VA$ is the $n\times n$ identity
694matrix.
695By the proposition we have
696  $$VTA = (VTEDV)A = VTED(VA) = VTED = V(TE)D.$$
697To see that $VTA$ represents~$T$,
698observe that by the proposition,
699   \begin{eqnarray*}
700   VTAV &=& (VTEDV)AV=(VTEDV\!A)V\\
701        &=& (VTED)(V\!A)V=(VTED)V=VT
702   \end{eqnarray*}
703so that $VTA$ gives the correct linear combination of the rows of~$V$.
704\end{proof}
705
706\subsection{Eigenvectors}\label{sec:eigenvector}
707Once a $\T$-simple subspace of $\sS^*$ has been identified, the
708following algorithm, which was suggested to the author
709by H.~Lenstra, produces an eigenvector
710defined over an extension of the base field.
711
712\begin{algorithm}%
713\index{Algorithm for computing!an eigenvector}%
714Let $A$ be an $n\times n$ matrix over an arbitrary field $K$ and
715suppose that the characteristic polynomial $f(x)=x^n+\cdots+a_1 x + a_0$
716of~$A$ is irreducible.   Let $\alpha$ be a root of $f(x)$
717in an algebraic closure~$\Kbar$ of~$K$.
718Factor $f(x)$ over $K(\alp)$ as
719 $f(x) = (x-\alp) g(x)$.
720Then for any element $v\in K^n$ the vector
721$g(A)v$ is either $0$ or it is an eigenvector of~$A$ with eigenvalue~$\alp$.
722The vector $g(A)v$ can be computed by finding
723$Av$, $A(Av)$, $A(A(Av))$, and then using that
724  $$g(x)=x^{n-1}+c_{n-2} x^{n-2}+\cdots+c_1 x+ c_0,$$
725where the coefficients $c_i$ are determined by the recurrence
726$$c_0 = - a_0/\alp,\qquad c_i = (c_{i-1}-a_i)/\alp.$$
727
728We will prove below that $g(A)v\neq 0$ for all vectors~$v$ not
729in a proper subspace of $K^n$.  Thus with high probability, a
730randomly chosen''~$v$ will have the property that $g(A)v\neq 0$.
731Alternatively, if $v_1,\ldots v_n$ form a basis for $K^n$, then
732$g(A)v_i$ must be nonzero for some~$i$.
733\end{algorithm}
734\begin{proof}
735By the Cayley-Hamilton theorem \cite[XIV.3]{lang:algebra}
736we have that $f(A)=0$.  Consequently, for any $v\in K^n$,
737we have $(A-\alp)g(A)v=0$ so that $A g(A)v = \alp v$.
738Since $f$ is irreducible it is the polynomial of least
739degree satisfied by $A$ and so $g(A)\neq 0$.
740Therefore $g(A)v\neq 0$ for all $v$ not in the proper
741closed subset $\ker(g(A))$.
742\end{proof}
743
744\subsection{Eigenvalues}\label{sec:eigenvalues}%
745\index{Eigenforms!computing}%
746In this section we give an algorithm for
747computing the $q$-expansion of one of the newforms
748corresponding to a factor of $\sS_k(N,\eps;K)^{\new}$.
749This is a generalization of the algorithm described
750in \cite[\S2.9]{cremona:algs}.
751
752\begin{algorithm}\label{alg:eigenvalues}
753\index{Algorithm for computing!eigenvalues}
754Given a factor $V\subset \sS_k(N,\eps;K)^{\dual\new}$
755as computed by Algorithm~\ref{alg:decompmknew}
756this algorithm computes the $q$-expansion of
757one of the corresponding Galois conjugate newforms.
758\begin{enumerate}
759\item Using Algorithm~\ref{alg:efficienttpdual} compute
760the action of the $*$-involution (Section~\ref{sec:heckeops})
761on~$V$.  Then compute the $+1$ eigenspace $V^+\subset V$.
762\item Find an element $T\in\T$\index{Hecke operators}  such that the
763characteristic polynomial of the matrix~$A$
764of~$T$ acting on $V^+$ is irreducible.
765Such a~$T$\index{Hecke operators}
766 must exist by the primitive element theorem
767\cite[V.4]{lang:algebra}.
768(Note: It is {\em not} always the case that $T$ can be
769taken to equal some Hecke operator $T_n$.  The first
770example with $k=2$ and $\eps=1$ occurs at level $N=512$.)
771\item Using Algorithm~\ref{sec:eigenvector} compute
772an eigenvector~$e$ for~$A$ over an extension of~$K$.
773\item Because~$e$ is an eigenvector and the pairing
774given in Equation~\ref{eqn:pairing} respects the
775Hecke action, we have that for any Hecke operator\index{Hecke operators}
776$T_n$ and element $w\in \sS_k(N,\eps;K)$\footnote{In fact, any element
777of $\sM_k(N,\eps;K)$ could be used!), that
778$$a_n \langle e, w \rangle 779 = \langle e T_n, w\rangle 780 = \langle e, T_n w \rangle.$$
781Choose~$w$ so that $\langle e,w\rangle \ne 0$.  Then
782$$a_n =\frac {\langle e, T_n w \rangle} 783 {\langle e, w \rangle}.$$
784The $a_n$ can now be computed by
785computing $\langle e, w \rangle$ once and for all,
786and then computing $\langle e, T_n w \rangle$ for
787each~$n$.
788It is best to choose~$w$ in such a way that
789$T_n w$ can be computed quickly.
790\end{enumerate}
791\end{algorithm}
792The beauty of this algorithm is that when~$w$
793is a Manin symbol\index{Manin symbols} $[P(X,Y),(c,d)]$ the
794computation of $T_p w = \sum_{x\in R_p} wx$ is very quick, requiring
795us to only sum over the Heilbronn
796matrices\index{Heilbronn matrices} of determinant~$p$ once.
797
798In practice we compute only the eigenvalues~$a_p$ using
799the above algorithm, then use the following
800recurrences to obtain the~$a_n$:
801\begin{eqnarray*}
802  a_{nm} &=& a_n a_m \qquad\text{if $(n,m)=1$, and}\\
803  a_{p^r}&=& a_{p^{r-1}}a_p - \eps(p) p^{k-2} a_{p^{r-2}}.
804\end{eqnarray*}
805
806
807\subsection{Sorting and labeling eigenforms}%
808\label{sec:sorting}%
809\index{Ordering of eigenforms}%
810\index{Eigenforms!sorting and labeling}%
811Systematically ordering the factors is essential,
812so that we can later refer to them.
813In Section~\ref{sec:eigenvalues} we saw how to associate
814to each new factor a sequence $a_n$ of Hecke eigenvalues.
815These can be used to sort the factors.
816
817Except in the case of weight~$2$ and trivial character,
818we use the following ordering.  To each eigenvector
819associate the following sequence of integers
820$$\tr(a_1), \tr(a_2), \,\tr(a_3),\, \tr(a_4),\, 821\tr(a_5), \, \tr(a_6),\, \ldots$$
822where the trace is from $K_f=\Q(\ldots a_n\ldots)$ down to $\Q$.
823Sort the eigenforms by ordering the
824sequences in dictionary order with
825minus coming before plus.
826Since we included $\tr(a_1)$, this ordering gathers together
827factors of the same dimension.
828Furthermore, the sequence of traces determines the Galois conjugacy class
829of~$f$, because the
830$g=\sum_{n\geq 1} \tr(a_n) q^n$
831is the trace of~$f$, hence~$g$ lies in the $\C$-vector space
832spanned by the Galois conjugates of~$f$.
833
834When $k=2$ and the character is trivial we
835use a different and somewhat complicated ordering
836because it extends the notation for elliptic curves
837that was introduced in the second edition of \cite{cremona:algs}
838and has since become standard.
839Sort the factors of $\sS_k(N,\eps)^{\new}$ as follows.
840First by dimension, with smallest dimension first.
841Within each dimension, sort in binary order,
842by the signs of the Atkin-Lehner%
843\index{Atkin-Lehner involution!and ordering eigenforms}
844involutions
845with $-$ corresponding to~$0$ and~$+$ to~$1$.  For example, if there
846are three Atkin-Lehner involutions then the sign patterns
847are sorted as follows:
848$$+++, -++, +-+, --+, ++-, -+-, +--, ---.$$
849Finally, let $p$ be the smallest prime not dividing $N$.
850Within each of the Atkin-Lehner classes, sort by
851the magnitudes of the $K_f/\Q$-trace of
852$a_p$ breaking ties by letting the positive trace be first.
853If there are still any ties, repeat the final step with the
854next smallest prime not dividing~$N$, etc.
855(Note: It's not clear to the author that ties will always eventually
856be broken, though in his computation they always have been.)
857
858\section{Intersections and congruences}
859\index{Congruences!computing}
860\label{sec:intersection}
861
862Consider a complex torus $J=V/\Lambda$, and let
863$A=V_A/\Lambda_A$ and $B=V_B/\Lambda_B$ be subtori whose
864intersection $A\intersect B$ is finite.
865\begin{proposition}\label{prop:intersection}
866There is a natural isomorphism of groups
867$$A\intersect B \isom 868 \left(\frac{\Lambda}{\Lambda_A + \Lambda_B}\right)_{\tor.}$$
869\end{proposition}
870\begin{proof}
871There is an exact sequence
872$$0\ra A\intersect B \ra A \oplus B \ra J.$$
873Consider the diagram
874$$\xymatrix{ 875 & {\Lambda_A \oplus\Lambda_B}\ar[d] \ar[r] & {\Lambda} \ar[r]\ar[d]& 876 {\Lambda/(\Lambda_A + \Lambda_B)}\ar[d]\\ 877 & {V_A \oplus V_B}\ar[d] \ar[r] & V \ar[r]\ar[d] & {V/(V_A+V_B)}\ar[d]\\ 878 {A\intersect B}\ar[r] & A\oplus B\ar[r] & J \ar[r] & J/(A+ B).}$$
879The snake lemma\index{Snake lemma} gives an exact sequence
880$$0 \ra 881 A\intersect B \ra 882 \Lambda/(\Lambda_A + \Lambda_B) \ra 883 V/(V_A+V_B).$$
884Since $V/(V_A+V_B)$ is a $\C$-vector space, the torsion
885part of $\Lambda/(\Lambda_A + \Lambda_B)$ must map to~$0$.
886No non-torsion in $\Lambda/(\Lambda_A + \Lambda_B)$ could
887map to~$0$, because if it did then $A\intersect B$ would not
888be finite.  The lemma follows.
889\end{proof}
890
891The following formula for the intersection of~$n$
892subtori is obtained  in a similar way.
893\begin{proposition}
894For $i=1,\ldots,n$ let $A_i = V_i/\Lambda_i$ be a subtorus of
895$J=V/\Lambda$, and assume that each pairwise intersection
896$A_i \intersect A_j$ is finite.
897Then
898$$A_1\intersect \cdots \intersect A_n 899 \isom 900\left(\frac{\Lambda\oplus \cdots \oplus \Lambda} 901 {f(\Lambda_1\oplus\cdots\oplus \Lambda_n)}\right),$$
902where $f(x_1,\ldots,x_n)=(x_1-x_2,x_2-x_3,x_3-x_4,\ldots,x_{n-1}-x_n)$.
903\end{proposition}
904
905\begin{remark}
906Using this proposition the author constructed the
908\begin{figure}
909\begin{center}
910\includegraphics{shirt.eps}
911\end{center}
912\caption{T-shirt design}
913\label{cap:tshirt}
914\end{figure}
915\end{remark}
916
917
918\begin{example}\label{ex:kilford}
919L.~Kilford of London, England has recently discovered an example at
920prime level $503$ in which multiplicity one'' fails.  One
921verification of his example uses the above proposition.  Let~$E_1$,
922$E_2$, and $E_3$ be the three elliptic curves of conductor $503$, and
923for each $i=1,2,3$, let $\m_i$ be the maximal ideal of $\T\subset 924\End(J_0(503))$ generated by~$2$ and all $T_p-a_p(E_i)$, with~$p$
925prime.  Each of the Galois representations $E_i[2]$ is irreducible,
926and one can check that $\m_1=\m_2=\m_3$. If multiplicity one holds,
927then $E_1[2] = E_2[2] = E_3[2]$ inside of $J_0(503)$.  However, this
928is not the case, as a modular symbols computation in the integral
929homology $H_1(X_0(N),\Z)$ reveals that $E_1\intersect E_2 = \{0\}$.
930\end{example}
931
932
933\subsection{A strategy for computing congruences}
934Let~$N$ be a positive integer, $k\geq 2$ an integer, and~$\eps$ a
935mod~$N$ Dirichlet character.  Suppose~$f$ and~$g$ are newforms in
936$S_k(N,\eps;\Qbar)$.  The following proposition gives rise to an
937algorithm for computing most congruences\index{Congruences!between
938$q$-expansions}\index{Algorithm for computing!congruences}%
939\index{Congruences!computed using homology}
940between infinite Fourier expansions\index{Fourier coefficients}.
941
942The advantage of the algorithm is that it only involves finite exact
943computations and does not rely on the computation of $q$-expansions.  A
944disadvantage is that congruences between $q$-expansions need not be
945reflected by the corresponding modular symbols, so the proposition
946need not give all congruences.  This is illustrated in
947Example~\ref{ex:kilford}.
948
950First strategy: Computing $m$-congruences of period lattices'' in
951\cite{cremona-mazur}.
952
953\begin{proposition}\label{prop:degcong}
954Suppose~$f$ and~$g$ are newforms in $S_k(N,\eps;\Qbar)$.
955Let $I_f$ and $I_g$ be the corresponding annihilators
956in the Hecke algebra~$\T$\index{Hecke algebra!and congruences}.
957Let $\Lambda = \sS_k(N,\eps;\O)$, and set
958$\Lambda_f=\Lambda[I_f]$
959and $\Lambda_g=\Lambda[I_g]$.
960If $p\mid \#\left(\frac{\Lambda}{\Lambda_f + \Lambda_g}\right)_{\tor}$
961then there is a prime~$\wp$ of residue characteristic~$p$ such
962that $f\con g \pmod{\wp}$.
963\end{proposition}
964\begin{proof}
965Consider the exact sequence
966$$0 \ra \Lambda_f \oplus \Lambda_g \ra \Lambda \ra 967 \Lambda/(\Lambda_f+\Lambda_g) \ra 0$$
968where the first map is $(a,b)\mapsto a-b$.
969Upon tensoring this sequence with~$\F_p$ we obtain:
970$$Z 971 \ra (\Lambda_f \tensor\F_p) \oplus (\Lambda_g \tensor\F_p) 972 \ra \Lambda\tensor\F_p \ra (\Lambda/(\Lambda_f+\Lambda_g))\tensor\F_p\ra 0,$$
973where $Z=\Tor^1(\Lambda/(\Lambda_f+\Lambda_g),\F_p)$.
974Denote by $\im(\Lambda_f)$ the image of $\Lambda_f\tensor\F_p$
975in $\Lambda\tensor\F_p$
976and likewise for $\Lambda_g$.
977Our assumption that~$p$ divides the torsion part
978of $\Lambda/(\Lambda_f+\Lambda_g)$ implies that~$Z$
979is nonzero, so $\im(\Lambda_f)$ and $\im(\Lambda_g)$
980have nonzero intersection inside the $\F_p$-vector
981space $\Lambda\tensor\F_p$.
982The Hecke algebra~$\T$ acts on $\im(\Lambda_f)$
983through its action on~$f$, that is, through the quotient $\T/I_f$;
984similarly,~$\T$ acts on $\im(\Lambda_g)$ through $\T/I_g$.
985Thus~$\T$ acts on the nonzero $\T\tensor\F_p$-module
986$\im(\Lambda_f)\intersect \im(\Lambda_g)$
987through $\T/(I_f+I_g+p)$.  This implies that
988$I_f+I_g+p$ is not the unit ideal, which is equivalent
989to the assertion of the proposition.
990\end{proof}
991
992% ratperiod.tex
993\section{The rational period mapping}%
994\label{sec:ratperiod}%
995Consider a triple $(N,k,\eps)$, and let $K=\Q[\eps]$.
996Let~$I$ be an ideal in the Hecke algebra~$\T$
997\index{Hecke algebra!and rational period mapping} associated to $(N,k,\eps)$.
998The rational period mapping associated
999to~$I$ is a map from the space $\sM_k(N,\eps;K)$ of
1000modular symbols to a finite dimensional $K$-vector space.
1001It is a computable analogue of the classical integration
1002pairing, and is of great value in extracting the rational parts
1003of analytic invariants; e.g., of special values of $L$-functions.
1004In the next section we use it to compute the
1005image of cuspidal points on $J(N,k,\eps)$.
1006
1007\begin{definition}\label{defn:theta}
1008Let $D:=\Hom_K(\sM_k(N,\eps;K),K)[I]$;  the
1009\defn{rational period mapping}\index{Rational period mapping|textit}
1010is the natural quotient map
1011$$\Theta_I : \sM_k(N,\eps;K) \ra \frac{\sM_k(N,\eps;K)} 1012{\bigcap\, \{\ker(\vphi) : \vphi \in D\}}.$$
1013If $f\in S_k(N,\eps)$ is a newform, set $\Theta_f:=\Theta_{I_f}$
1014where $I_f$ is the annihilator of~$f$ in the Hecke algebra.
1015\end{definition}
1016
1017\begin{algorithm}\label{alg:ratperiod}%
1018\index{Algorithm for computing!rational period mapping}%
1019This algorithm computes $\Theta_I$.
1020Choose a basis for $W=\sM_k(N,\eps;K)$ and use it
1021to view~$W$ as a space of column vectors equipped with
1022a left action of~$\T$.
1023View $W^*=\Hom_K(\sM_k(N,\eps;K),K)$ as the
1024space of row vectors of length equal to $\dim \sM_k(N,\eps;K)$;
1025thus~$W^*$ is dual to~$W$ via the natural pairing between
1026row and column vectors.  The Hecke operators\index{Hecke operators}
1027act on $W^*$ on the right.
1028Compute a basis $\vphi_1,\ldots,\vphi_{n}$ for
1029the $K$-vector space $W^*[I]$.
1030Then the rational period mapping with respect to
1031this basis is $\vphi_1\cross \cdots \cross \vphi_n$;
1032it is given by the matrix whose rows
1033are $\vphi_1,\ldots,\vphi_n$.
1034\end{algorithm}
1035\begin{proof}
1036The kernels of $\vphi_1\cross \cdots \cross \vphi_n$
1037and $\Theta_I$ are the same.
1038\end{proof}
1039
1040
1041\begin{example}\label{ex:ratperiod1}
1042Let~$I$ be the annihilator of the newform $f=q-2q^2+\cdots \in M_2(37,1;\Q)$
1043corresponding to the elliptic curve {\bf 37k2A}.
1044There is a basis for $W=\sM_2(37,1;\Q)$ such that
1045$$T_2 = \left(\begin{matrix} 1046-1& 1 &1&-1& 0\\ 1047 1&-1& 1& 0& 0\\ 1048 0& 0&-2& 1& 0\\ 1049 0& 0& 0& 0& 0\\ 1050 0& 0& 0& 1& 3\\ 1051\end{matrix}\right)$$
1052The characteristic polynomial of $T_2$ is $x^2(x+2)^2(x-3)$.
1053Thus $W[I]=\ker(T_2+2)$ is spanned by the column
1054vectors $(1,-1,0,1/2,0)^t$ and
1055$(0,0,1,-1/2,0)^t$, and $W^*[I]=\ker(T_2^{t}+2)$ is spanned by the row vectors
1056$(1,0,-1,0,0)$ and $(0,1,-1,0,0)$.  The rational period mapping
1057is $\Theta_I((a,b,c,d,e)^t) = (a-c,b-c)$.
1058\end{example}
1059
1060\begin{lemma}\label{lem:ratperiodlemma}
1061  $$\dim \sM_k(N,\eps;K)[I] = \dim \Hom_K(\sM_k(N,\eps;K),K)[I].$$
1062\end{lemma}
1063\begin{proof}
1064Let $W=\sM_k(N,\eps;K)$ and $W^*$ be its dual.
1065Let $a_1,\ldots,a_n$ be a set of generators for~$I$.
1066Choose a basis for~$W$ that is compatible with the following filtration:
1067$$0\subset (\ker(a_1)\intersect\cdots\intersect\ker(a_n)) 1068\subset (\ker(a_1)\intersect\cdots\intersect\ker(a_{n-1})) 1069\subset\cdots \subset \ker(a_1)\subset W.$$
1070The rank of a matrix
1071equals the rank of its transpose, so the dimension of $\ker(a_1)$ is
1072the same as the dimension of $\ker(a_1^t)$, that is,
1073$\dim W[(a_1)] = \dim W^*[(a_1)]$.
1074Since~$\T$ is commutative,~$a_2$ leaves $\ker(a_1)$ invariant;
1075because of how we chose our basis for~$W$,
1076the transpose of $a_2|_{\ker(a_1)}$ is $a_2^t|_{\ker(a_1^t)}$.
1077Thus again, $\dim (\ker(a_2|_{\ker(a_1)}))$ equals
1078$\dim (\ker(a_2^t|_{\ker(a_1^t)}))$.
1079 Proceeding inductively, we prove the lemma.
1080\end{proof}
1081
1082\begin{corollary}
1083Suppose $\sM_k(N,\eps;K)[I]\subset \sS_k(N,\eps;K)$, and
1084let $P:\sM_k(N,\eps;K)\ra \Hom_\C(S_k(N,\eps;\C)[I],\C)$
1085be the classical period map induced by the integration
1086pairing.  Then $\ker(P) = \ker(\Theta_I)$.
1087\end{corollary}
1088\begin{proof}
1089Since $P(\sM_k(N,\eps;\O))$ is known to be a finite-covolume
1090$\O$-lattice in the complex vector space $\Hom_\C(S_k(N,\eps;\C)[I],\C)$,
1091the $K$-dimension of $\im(P)$ equals
1092$2\cdot \dim_\C S_k(N,\eps;\C)[I]$,
1093which in turn equals
1094$\dim_K \sM_k(N,\eps;K)[I]$.
1095Thus by Lemma~\ref{lem:ratperiodlemma} the
1096images $\im(P)$ and $\im(\Theta_I)$ have the same
1097dimension, hence $\ker(P)$ and $\ker(\Theta_I)$ also have the
1098same dimension.  It thus suffices to prove the inclusion
1099$\ker(\Theta_I)\subset\ker(P)$.
1100Suppose $\Theta_I(x)=0$; then $\vphi(x)=0$ for all
1101$x\in W^*[I]$, where $W=\sM_k(N,\eps;K)$.
1102Thus $\vphi(x)=0$ for all $\vphi\in (W\tensor\C)^*[I]$.
1103Since the integration pairing that defines~$P$ respects
1104the action of~$\T$, the composition of~$P$ with any linear
1105functional lies in $(W\tensor\C)^*[I]$.  Thus $P(x)=0$,
1106as required.
1107\end{proof}
1108
1109
1110% cuspdiff.tex
1111\section{The images of cuspidal points}%
1112\label{sec:torsionsubgroup}%
1113\label{sec:cuspdiff}%
1114\index{Cuspidal points}%
1115Consider a triple $(N,k,\eps)$, and let $K=\Q[\eps]$.
1116Recall that integration defines a period mapping
1117$$P : \sM_k(N,\eps;K)\ra \Hom_\C(S_k(N,\eps;\C),\C).$$
1118A \defn{cuspidal point} of
1119$$J=J(N,k,\eps):= 1120\frac{\Hom_\C(S_k(N,\eps;\C),\C)} 1121 {P(\sS_k(N,\eps;\O))}$$
1122is a point that is in the image under~$P$ of $\sM_k(N,\eps;\O)$.
1123It is of great interest to compute the structure of
1124the cuspidal subgroup of~$J$ and of the quotients of~$J$.
1125For example, when $k=2$ and $\eps=1$, the torus~$J$
1126can be identified with $J_0(N)(\C)$.
1127In this case,
1128Manin\index{Manin} proved
1129(see~\cite{manin:parabolic}) that the cuspidal
1130point $\{0,\infty\}$ is a torsion point in $J_0(N)(\Q)$, so
1131its order gives a lower bound on $J_0(N)(\Q)_{\tor}$.
1132
1133
1134\begin{algorithm}[Cuspidal subgroup]%
1135\index{Algorithm for computing!cuspidal subgroup}%
1136Let~$I$ be an ideal in the Hecke algebra~$\T$.\index{Hecke algebra!and cuspidal subgroup}
1137This algorithm computes the cuspidal subgroup
1138of the quotient $A_I$ of~$J$.
1139Using Algorithm~\ref{alg:MkNO}
1140compute $\sM_k(N,\eps;\O)$ and $\sS_k(N,\eps;\O)$.
1141Using Algorithm~\ref{alg:ratperiod},
1142compute the rational period mapping~$\Theta_I$.
1143Then the cuspidal subgroup is the
1144subgroup of $\Theta_I(\sS_k(N,\eps;\O))$ generated
1145by the elements $\Theta_I(x)$ for $x\in \sM_k(N,\eps;\O)$.
1146In particular, the point of $A_I(\C)$ corresponding
1147to $X^iY^{k-2-i}\{\alp,\beta\}$ is
1148the image of $\Theta_I(X^iY^{k-2-i}\{\alp,\beta\})$ in the quotient
1149of $\Theta_I(\sM_k(N,\eps;\O))$ by $\Theta_I(\sS_k(N,\eps;\O))$.
1150\end{algorithm}
1151
1152\begin{example}
1153This example continues Example~\ref{ex:ratperiod1}.
1154The basis chosen is also a basis for $\sM_2(37,1;\Z)$,
1155so by computing the boundary map, or the integer
1156kernel of $T_2(T_2+2)$, we find that $\sS_2(37,1;\Z)$
1157is spanned by $(1,0,0,0,0)$, $(0,1,0,0,0)$,
1158$(0,0,1,0,0)$, and $(0,0,0,1,0)$.
1159Thus $\Theta_I(\sS_2(37,1;\Z))$ is generated by
1160$(1,0)$ and $(0,1)$.
1161The modular symbols $\{0,\infty\}$ is represented
1162by $(0,0,0,0,-1)$, so the image of the cusp $(0)-(\infty)\in J_0(37)$
1163is~$0$ in {\bf 37k2A}.
1164
1165The rational period mapping associated to {\bf 37k2B} (with respect
1166to some basis) is
1167$$\Theta_I((a,b,c,d,e)^t) = (a-c-2d+\frac{2}{3}e,\,\, 1168 b+c+2d-\frac{2}{3}e).$$
1169Thus $\Theta_I(\sS_2(37,1;\Z))$ is generated by
1170$(1,0)$ and $(0,1)$.
1171The image of $\{0,\infty\}$ is
1172is $\frac{2}{3}(1,-1)$, so the image of
1173$(0)-(\infty)$ in {\bf 37k2B} has order~$3$.
1174\end{example}
1175
1176\subsection{Rational torsion}
1177Let~$f$ be a newform of weight $2$, and suppose
1178$\eps=1$.  Manin\index{Manin} proved that $(0)-(\infty)$ defines an element
1179of $J_0(N)(\Q)_{\tor}$.  Thus the order of the
1180image of $(0)-(\infty)$ provides a  lower bounds on
1181$\# A_f(\Q)_{\tor}$.
1182In general, many other points in the cuspidal subgroup can be rational.
1183Determining which would give a better lower bound on the rational
1184subgroup; the author has not yet carried out such computations
1185(see, however,~\cite{stevens:thesis}).
1186\index{Torsion subgroup!lower bounds on|textit}
1187
1188\subsection{Upper bound on torsion: Counting points mod~$p$}%
1189\index{Torsion subgroup!upper bounds on|textit}%
1190Let~$f$ be a newform of weight $2$, and suppose
1191$\eps=1$.
1192The Hecke algebra~$\T$\index{Hecke algebra!bounds torsion} acts through
1193a quotient $\overline{\T}$ on the subspace of $S_2(\Gamma_0(N))$ spanned
1194by the Galois conjugates of~$f$. Let $\chi_p(X)$ be the characteristic
1195polynomial of the image of $T_p$ in $\overline{\T}$.
1196Suppose $p\nmid N$ and  let $N_p=\# A_f(\F_p)$ be the number of points
1197on the mod~$p$ reduction of the abelian variety $A_f$.
1198\begin{proposition}
1199For each prime~$p$ not dividing~$N$,
1200    $$N_p = \chi_p(p+1).$$
1201\end{proposition}
1202\begin{proof}
1203This is probably well-known, but we give a
1204proof (which was suggested to the author by Matt Baker).
1205It follows from the Eichler-Shimura\index{Eichler-Shimura relation}
1206theorem that the
1207following relation holds in the endomorphism ring of $A_f/{\F_p}$:
1208    $$T_p = \Frob + \Ver = \Frob + p/\Frob.$$
1209Let $\ell\neq p$ be a prime.
1210If the characteristic polynomial of $\Frob$ on
1211an $\ell$-adic Tate module of $A_f/\F_p$ is $F(t)$, and
1212the characteristic polynomial of $T_p$
1213on differentials $H^0(A_f/\F_p,\Omega)$
1214is $f(t)$, then we have $f(t)=x^{-d}F(x)$,
1215where $t=x+(p/x)$ and $d=\dim A_f$.  In
1216other words, the relation above gives an easy conversion
1217between~$f$ and~$F$.
1218Since it's a general fact that $\#A_f(\Fp)=F(1)$, we have
1219        $\#A_f(\Fp)=f(p+1).$
1220\end{proof}
1221
1222The following theorem is proved using formal
1223groups.
1224\begin{theorem}
1225Let $A$ be an abelian variety over~$\Q$, with good reduction outside~$N$.
1226Suppose $p\nmid N$.  Then the kernel of the reduction map
1227$A(\Q)_{\tor}\ra A(\F_p)$
1228is killed by~$p$.  If $p>2$ then
1229the kernel is trivial.
1230\end{theorem}
1231
1232By taking gcd's we obtain an upper bound on $\# A(\Q)_{\tor}$.
1233This upper bound is not in general sharp; in fact, it is unchanged
1234if~$A$ is replaced by any isogenous abelian variety.
1235For example, $X_0(11)$ and $X_1(11)$ are isogenous, but have different
1236torsion subgroups.
1237
1238\section{The modular degree}%
1239\label{sec:moddeg}%
1240\index{Modular degree}%
1241Let~$f$ be a newform of level~$N$, weight
1242$k\geq 2$ and character~$\eps$ such that $\eps^2=1$.
1243In this section we define and give an algorithm to
1244compute the modular degree of the torus $A_f$ attached to~$f$.
1245
1246\begin{definition}\label{defn:modulardegree}
1247The \defn{modular map}\index{Modular map} is the
1248map $\theta_f:\Adual_f \ra A_f$ that is
1249induced by the bottom row of
1250Diagram~\ref{dgm:uniformization} on page~\pageref{dgm:uniformization}.
1251The \defn{modular degree}\index{Modular degree}~$m_f$
1252of~$f$ (or of~$A_f$) is the degree of this map.
1253If~$f$ has weight two, then $\theta_f$ is a polarization so
1254by \cite[Thm.~13.3]{milne:abvars} its degree is a perfect square;
1255in this case we {\em instead} define the modular degree $m_f$ to
1256be the positive square root of the degree of $\theta_f$.
1257\end{definition}
1258
1259\begin{remark}
1260When $E/\Q$ be a modular elliptic curve of conductor~$N$
1261that is an optimal quotient\index{Optimal quotient} of $J_0(N)$,
1262then $m_f$ is the usual modular degree, which is
1263the least degree of a map $X_0(N)\ra E$.
1264\end{remark}
1265
1266\begin{remark}
1267When $k\neq 2$, the degree of~$\theta_f$ need not be a perfect square.
1268For example, there is a one-dimensional quotient $A_f$
1269associated to the unique rational newform
1270    $$f = q + 2q^2 - 8q^3 + 4q^4 + 5q^5 - 16q^6 - 4q^7+ \cdots\in S_4(10)$$
1271such that the kernel of $\theta_f$ is isomorphic to
1272$\Z/10\Z$.
1273
1274Next, for a newform~$f$
1275let $\theta_f'$ be the part of $\#\ker(\theta_f)$ that is
1276coprime to the level.  There is a newform in $f\in S_4(\Gamma_0(77))$
1277such that $\theta_f'$ is not a perfect square at~$2$.  For identification
1278purposes, we remark that the field generated by the Fourier coefficients
1279of~$f$ has discriminant $2^3\cdot 3^3\cdot 2417$.
1280\end{remark}
1281
1282\begin{algorithm}%
1283\index{Algorithm for computing!modular kernel}%
1284Let $I_f$ be the annihilator of~$f$ in the Hecke algebra\index{Hecke algebra}.
1285The modular kernel $\ker(\theta_f)$ is isomorphic to
1286the cokernel of the natural map
1287$\sS[I_f] \ra \Phi_f(\sS)$ of Diagram~\ref{dgm:uniformization}
1288on page~\pageref{dgm:uniformization}.
1289This cokernel can be computed by replacing~$\Phi_f$
1290by the rational period map~$\Theta_{I_f}$.
1291\end{algorithm}
1292\begin{proof}
1293For concreteness, we give the proof only in the case of weight-two and
1294trivial character. The proof in the general case is similar.
1295Let $S = S_2(\Gamma_0(N),\C)$ be the complex vector space of
1296weight-two modular forms of level~$N$, and set $H = H_1(X_0(N),Z)$.
1297The integration pairing $S\times H \rightarrow \C$
1298induces a natural map
1299$$\Phi_f:H\rightarrow \Hom(S[I_f],\C).$$
1300Using the classical
1301Abel-Jacobi theorem, we deduce the following commutative diagram,
1302which has exact columns, but whose rows are not exact.
1303$$\[email protected]=.5cm{ 1304 0\ar[d] & 0\ar[d] & 0\ar[d] \\ 1305 H[I_f]\ar[d]\ar[r] & H\ar[d]\ar[r]&\Phi_f(H)\ar[d] \\ 1306\Hom(S,\C)[I_f]\ar[d]\ar[r] &\Hom(S,\C)\ar[d]\ar[r] &\Hom(S[I_f],\C)\ar[d]\\ 1307 {A_f^{\vee}(\C)}\ar[d]\ar[r] 1308 \[email protected]/_3.5pc/[rr]& J_0(N)(\C)\ar[d]\ar[r]& A_f(\C)\ar[d]\\ 1309 0 & 0 & 0 \\ 1310}$$
1311By the snake lemma\index{Snake lemma},
1312the kernel of $A_f^{\vee}(\C)\rightarrow A_f(\C)$ is isomorphic to the
1313cokernel of the map $H[I_f] \rightarrow \Phi_f(H)$,
1314which proves the proposition.
1315\end{proof}
1316
1317\begin{remark}\label{rem:moddegmestre}
1318Suppose $E$ is an optimal quotient of $J_0(p)$, with~$p$ prime.
1319The surjectivity result in \cite{mestre-oesterle:crelle} implies that
1320it is possible to efficiently compute the modular degree using only
1321the method of graphs.
1322For more details, see Chapter~\ref{chap:compgroups}.
1323\end{remark}
1324
1325
1326\section{The rational part of $L(A_f,j)$}%
1327\label{sec:ratpartformula}%
1328\label{sec:rationalvals}%
1329\index{Rational part of $L(A,j)$}%
1330\index{Special value $L(A,j)$!rational part of}%
1331Let $k\geq 2$ be an integer, and let $\eps:(\Z/N\Z)^*\ra\C^*$ be a
1332Dirichlet character such that $\eps^2=1$.  This assumption on $\eps$
1333is made only for simplicity; there is no fundamental obstruction to
1334considering arbitrary characters.  For the remainder of this section
1335we fix a newform $f\in S_k(N,\eps)$.  We will compute certain rational
1336numbers associated to~$f$.
1337
1338The author was motivated to prove the results of this section after
1339seeing Agashe's\index{Agashe} results in the case $k=2$ and $\eps=1$;
1340see \cite[Ch.~4]{agashe:phd}.
1341
1342
1343\subsection{$L$-functions}
1344\begin{definition}\label{defn:lseries}
1345The $L$-series\index{$L$-series|textit} associated to~$f$ is
1346the complex-analytic function
1347  $$L(f,s) \defeq \sum_{n=1}^{\infty} a_n n^{-s}.$$
1348\end{definition}
1349Hecke\index{Hecke} proved that $L(f,s)$ has an analytic continuation
1350to the whole complex plane.  In particular, it makes sense to consider
1351the values $L(f,j)$ where $j\in\{1,2,\ldots,k-1\}$ is an integer in
1352the critical strip.''  The general consesus is that these special
1353values have deep arithmetic significance, in the sense that the
1354quotients $L(f,j)/\omega_{f,j}$ should be algebraic numbers, where
1355$\omega_{f,j}$ is an appropriate period of~$f$, and that these algebraic
1356numbers should encode deep arithmetic properties of the motive
1357attached to~$f$.
1358
1359For simplicity, especially when doing explicit computations, it is
1360desirable to work exclusively with ratios that are rational numbers
1362the complex torus~$A_f$ attached to~$f$, and introduce
1363            $$L(A_f,s) := \prod_{i=1}^d L(f_i,s),$$
1364where $f_1,\ldots, f_d$ are the distinct Galois-conjugates of~$f$.
1365As we will see, $L(A_f,j)/\Omega_j\in\Q$, where $\Omega_j$ will be
1366defined below.
1367
1368Though the notation $L(A_f,s)$ suggests that there might be a way to
1369attach an $L$-function to a general complex torus, this is definitely
1370{\em not} what we have in mind.  For our present purposes, the notation
1371$L(A_f,s)$ is nothing more than a convenient shorthand for the product
1372of the $L$-functions attached to the Galois conjugates of~$f$.
1373However, in the case when $k=2$ and $\eps=1$, the $L$-function
1374$L(A_f,s)$ is known to be the canonical $L$-series\index{$L$-series}
1375associated to the abelian variety $A_f/\Q$; see, e.g., the discussion
1376in
1377\cite[Sec.~7]{darmon-merel}.
1378
1379\subsection{Winding elements}
1380Generalizing Mazur\index{Mazur} and Merel's\index{Merel} terminology when $k=2$, we define
1381winding elements as follows.
1382\begin{definition}[Winding element]\label{defn:windingelement}
1383For $1\leq i \leq k-1$, the
1384$i$th \defn{winding element}\index{Winding element} is
1385 $$\e_i := X^{i-1}Y^{k-2-(i-1)}\{0,\oo\}\in\sM_k(N,\eps;\Z).$$
1386\end{definition}
1387For example, when $k=2$ there is one winding element
1388$\e = \e_1 = \{0,\infty\}$.
1389See \cite[\S2.2]{mazur-sd} for a topologically motivated discussion
1390of the terminology winding element.''
1391
1392
1393\subsection{Real and minus volumes}
1394\label{sec:realvolume}
1395We briefly review the association of a complex torus to a Galois-conjugacy
1396class of newforms.
1397Consider the space $S_k(N,\eps;\Z)$ of cusp forms in
1398$S_k(N,\eps)$ whose $q$-expansion at infinity has
1399Fourier coefficients which lie in~$\Z$.
1400Let $V$ be the $\C$-vector space spanned by the Galois
1401conjugates $f_1,\ldots, f_d$ of~$f$, and choose a $\Z$-basis
1402$g_1,\ldots,g_d$ for the intersection $V\intersect S_k(N,\eps;\Z)$.
1403Then integration via the pairing of Theorem~\ref{thm:perfectpairing}
1404against $g_1,\ldots, g_d$ defines a map
1405$\sS_k(N,\eps;\Z)\ra \C^d$ whose
1406cokernel is $A_f(\C)$.
1407Viewing $A_f(\C)$ in this way, the standard measure on $\C^d$
1408defines a measure on $A_f(\C)$.
1409
1410Because $\eps^2=1$, the complex torus $A(\C)$ is equipped
1411with an action of complex conjugation.
1412There are two distinguished additive subgroups of $A(\C)$: the subgroup
1413$A(\R)$ of elements fixed under complex conjugation, and the
1414subgroup $A(\C)^{-}$ of elements sent to their additive inverse
1415by complex conjugation.  When~$j$ is odd, let $\Omega_j$
1416be the measure of the subgroup fixed under conjugation, and when~$j$
1417is even, let $\Omega_j$ be the measure of the subgroup
1418sent to its inverse under conjugation, times $i^d$, where $d$ is
1419the dimension of~$A$.
1420When~$j$ is odd, we call $\Omega_j$ the \defn{real volume}; otherwise,
1421we call $\Omega_j$ the \defn{minus volume}
1422(see Definition~\ref{defn:realminusvolume}).
1423\index{Real volume|textit}%
1424\index{Minus volume|textit}%
1425
1426\subsection{The theorem}
1427We are now prepared to state a theorem that gives a computable
1428expression for the ratio $|L(A_f,j)/\Omega_j|$.  This theorem grew out
1429of joint work with Agashe.\index{Agashe}  It generalizes
1430Cremona's\index{Cremona} method for
1431computation $L(E,1)/\Omega_E$ when~$E$ is an elliptic curve
1432(see~\cite[\S2.8]{cremona:algs}).
1433
1434As an immediate corollary of the formula, we see that
1435$|L(A_f,j)/\Omega_j|$ is a rational number.  This was already known
1436when $f\in S_2(\Gamma_0(N))$ (see \cite[\S2]{gross:central}).  The
1437author remains ignorant as to whether or not the general corollary was
1438known before, or even if the real numbers $\Omega_j$, exactly as
1439defined here, had been previously considered.  However, rationality of
1440certain related period ratios has been known for some time, due to
1441work of Manin\index{Manin}, Shimura\index{Shimura},
1442and Hatada.  For a clear historical summary of
1443these rationality results see Li's MathSciNet review of
1445
1446We take the absolute value of $L(A_f,j)/\Omega_j$ for simplicity only
1447because at present we do not wish to worry about powers of the $4$th
1448root of unity~$i$.
1449
1450\begin{theorem}\label{ratpart}%
1451\index{Algorithm for computing!rational part of $L(A,j)$}%
1452Let $f\in S_k(N,\eps)$ be a newform, where $k\geq 2$ and $\eps^2=1$,
1453and let $j\in\{1,2,\ldots,k-1\}$ be an integer in the critical strip.
1454Let~$\sigma=(-1)^{j-1}$, and
1455let $\Theta_f$ be the rational period mapping associated to~$f$
1456(see Definition~\ref{defn:theta}).
1457Then
1458$$\left|\frac{L(A_f,j)}{\Omega_j}\right| 1459 = [\Theta_f(\sS_k(N,\eps;\Z)^\sigma) : \Theta_f(\T{}\e_j)],$$
1460where $\sS_k(N,\eps;\Z)^\sigma$ denotes the submodule of
1461$\sS_k(N,\eps;\Z)$ on which the $*$-involution acts as~$\sigma$,
1462and $\Omega_j$ is the real or minus volume of~$A_f$,
1463as in Section~\ref{sec:realvolume}.
1464The right hand expression in the formula is a lattice index, whose
1465definition is given below.
1466\end{theorem}
1467
1468\begin{remark}
1469In the context of the BSD conjecture\index{BSD conjecture!and $\Omega_A$},
1470$\Omega_{A_f} = \Omega_1 \cdot c_\infty$,
1471where $c_\infty$ is the number of connected components of
1472$A_f(\R)$.
1473\end{remark}
1474
1475The theorem involves lattice indexes, which we define as follows.
1476\begin{definition}\index{Lattice|textit}
1477Let~$V$ be a finite-dimensional
1478vector space over~$\R$.  A \defn{lattice} $L\subset V$
1479is a free abelian group of rank equal to the dimension
1480of~$V$ such that $\R L=V$.
1481If $L, M\subset V$ are lattices, the \defn{lattice
1482 index}\label{pg:latticeindex}\index{Lattice index|textit}%
1483\index{Index of lattices|textit}
1484$[L:M]\in\R$ is the absolute value of the
1485determinant of an automorphism of~$V$
1486taking~$L$ isomorphically onto~$M$.
1487For convenience we set $[L:M]=0$ for any lattice~$L$ and
1488additive abelian group~$M$ contained in~$V$
1489and of rank strictly smaller than $\dim V$.
1490\end{definition}
1491
1492The following fact allows us to compute the lattice the index without
1493using complex numbers.
1494\begin{lemma}\label{latticeker}
1495Suppose $\tau_i : V\ra W_i$, $i=1,2$, are surjective linear maps such that
1496$\ker(\tau_1)=\ker(\tau_2)$.  Let~$L$ and~$M$ be lattices in~$V$
1497such that $\tau_i(L)$ and $\tau_i(M)$ are both lattices for $i=1,2$.
1498Then
1499     $$[\tau_1(L):\tau_1(M)] = [\tau_2(L):\tau_2(M)].$$
1500\end{lemma}
1501\begin{proof}
1502Surjectivity and equality of kernels insures that there is a unique
1503isomorphism $\iota:W_1\ra W_2$ such that $\iota\tau_1 = \tau_2$.
1504Let~$\sigma$ be an automorphism
1505of $W_1$ such that $\sigma(\tau_1(L))=\tau_1(M)$.
1506Then
1507$$\iota\sigma\iota^{-1}(\tau_2(L)) = \iota\sigma\tau_1(L)=\iota\tau_1(M)=\tau_2(M).$$
1508Since conjugation does not change the determinant,
1509$$[\tau_2(L):\tau_2(M)]=|\det(\iota\sigma\iota^{-1})| 1510 =|\det(\sigma)| = [\tau_1(L):\tau_1(M)].$$
1511\end{proof}
1512
1513
1514\vspace{1in}
1515
1516\begin{proof}[Proof of Theorem~\ref{ratpart}]
1517Let $\Phi=\Phi_f$ be the period map\index{Period mapping}
1518$\sM_k(N,\eps;\Z) \ra \C^d$
1519defined by fixing a basis $f_1,f_2,\ldots,f_d$ of the conjugates
1520of the {\em newform}~$f$;
1521thus $$\Phi(x) = (\langle f_1, x\rangle, 1522 \langle f_2, x\rangle,\ldots 1523 \langle f_d, x\rangle)\in \C^d.$$
1524We view $\C^d$
1525as an algebra  with unit element $\mathbf{1}=(1,\ldots,1)$ equipped
1526with an action of the Hecke operators\index{Hecke operators}.
1527The operator $T_p$ acts as $(a_p^{(1)},\ldots,a_p^{(d)})$,
1528where the components $a_p^{(j)}$ are the  Galois conjugates of $a_p$.
1529Let $\Z^d\subset\R^d\subset\C^d$ be the standard submodules.
1530
1531For brevity, set $\sS=\sS_k(N,\eps;\Z)$.
1532Let $\mu(\Phi(\sS^\sigma))$ be the measure of a fundamental domain
1533for the lattice $\Phi(\sS^\sigma)$; equivalently,
1534$\mu(\Phi(\sS^\sigma))$ is the absolute value of the determinant
1535of a basis for $\Phi(\sS^\sigma)$.
1536Observe that
1537    $\mu(\Phi(\sS^\sigma))=[\Z^d:\Phi(\sS^\sigma)]$
1538and
1539 $|L(A_f,j)|=[\Z^d:\Phi(\e_j)\Z^d].$
1540
1541Let $W\subset\C^d$ be the $\Z$-module spanned by the columns'' of a
1542basis for $S_k(N,\eps;\Z)[I_f]$. More precisely, if $g_1,\ldots, g_d$
1543is a basis, then the $n$th column is the vector
1544$(a_n(g_1),\ldots, a_n(g_d))$, where $a_n(g_i)$ is the
1545coefficient of $q^n$ in the $q$-expansion of $g_i$ at infinity.
1546Because~$\Omega_j$ is computed with
1547respect to a basis for $S_k(N,\eps;\Z)[I_f]$,
1548   $$\mu(\Phi(\sS^\sigma))=[W:\T\mathbf{1}]\cdot \Omega_j.$$
1549
1550Observe that $S_k(N,\eps;\Z)$ is saturated, in the sense that there
1551are no nontrivial linear relations between the $g_i$ when reduced
1552modulo any prime~$p$.  To see this, note that if $\sum a_i g_i \con 15530\pmod{p}$, then $\frac{1}{p}\sum a_i g_i\in S_k(N,\eps;\Z)$ which,
1554if the~$a_i$ are not all~$0$, is contrary
1555to our assumption that $g_1,\ldots, g_d$ are a $\Z$-basis.  Because
1556row rank = column rank'', the same must be true for the columns''
1557defined in the previous paragraph, so $[\Z^d:W]=1$.
1558It follows that $[\Z^d:\T\mathbf{1}]=[W:\T\mathbf{1}].$
1559
1560The following calculation combines together the above
1561observations using properties of the lattice index:
1562\begin{eqnarray*}
1563[\Phi(\sS^\sigma):\Phi(\T{}\e_j)]
1564     &=& [\Phi(\sS^\sigma):\Z^d]
1565                \cdot[\Z^d:\Phi(\T{}\e_j)]\\
1566     &=& \frac{1}{[\Z^d:\Phi(\sS^\sigma)]} \cdot [\Z^d:\Phi(\T\e_j)]\\
1567     &=&\frac{1}{\mu(\Phi(\sS^\sigma))}\cdot [\Z^d:\Phi(\e_j)\Z^d]\cdot [\Phi(\e_j)\Z^d:\Phi(\T\e_j)]\\
1568     &=&\frac{|L(A_f,j)|}{\mu(\Phi(\sS^\sigma))}\cdot[\Phi(\e_j)\Z^d:\Phi(\T\e_j)]\\
1569     &=&\frac{|L(A_f,j)|}{\mu(\Phi(\sS^\sigma))}\cdot[\Phi(\e_j)\Z^d:\Phi(\e_j)\T{}\mathbf{1}]\\
1570     &=&\frac{|L(A_f,j)|}{|\Omega_j|\cdot [W:\T\mathbf{1}]}\cdot[\Z^d:\T{}\mathbf{1}]\\
1571     &=&\frac{|L(A_f,j)|}{|\Omega_j|}.\\
1572\end{eqnarray*}
1573Theorem~\ref{ratpart} now follows by using Lemma~\ref{latticeker},
1574to replace~$\Phi$ by~$\Theta_f$.
1575\end{proof}
1576
1577
1578\subsection{Bounding the denominator of the ratio}
1579In this section we bound the denominators of the ratios appearing
1580in the previous section. We begin with
1581the following lemma, which follows easily from the
1582alternative description of the
1583boundary map given in Proposition~\ref{prop:boundary}.
1584\begin{lemma}
1585For $j=2,\ldots, k-2$ the winding element $\e_j$ lies in
1586$\sS_k(N,\eps;\Z)$.
1587\end{lemma}
1588\begin{proof}
1589Recall that $\e_j = P(X,Y)\{0,\infty\}$ where
1590$P(X,Y) = X^{j-1}Y^{k-2-(j-1)}$.
1591Since $2\leq j\leq k-2$, it follows that
1592$P(1,0)=P(0,1)=0$, so Propositison~\ref{prop:boundary} implies
1593that $\e_j$ maps to~$0$ under the boundary map.
1594\end{proof}
1595\begin{proposition}
1596For $j=2,\ldots, k-2$,
1597$$\frac{L(A_f,j)}{\Omega_j} \in \Z.$$
1598\end{proposition}
1599\begin{proof}
1600This follows from Theorem~\ref{ratpart} because
1601$\Theta_f(\T \e_j) \subset \Theta_f(\sS_k(N,\eps;\Z)^{\sigma})$,
1602so the lattice index is an integer.
1603\end{proof}
1604
1605For the rest of this section, we assume for simplicity that $\eps=1$.
1606\begin{lemma}\label{lemma:eisact}
1607For $j=1$ and $j=k-1$, we have for each $p\nmid N$ that
1608$$(T_p - (1+p^{k-1})) \e_j \in \sS_k(N,\eps;\Z).$$
1609\end{lemma}
1610\begin{proof}
1611This is a standard calculation; see, e.g., \cite[\S2.8]{cremona:algs}
1612for the case when $k=2$.
1613\end{proof}
1614
1615\begin{proposition}\label{cor:denominator}
1616Let $j\in\{1,\ldots,k-1\}$, and
1617let~$n$ be the order of the image in $A_f(\C)$ of the modular symbol
1618$\e_j$, so $n=1$ if $j\not\in \{1, k-1\}$.  Then
1619$$\frac{L(A_f,j)}{\Omega_j}\in \frac{1}{n}\Z.$$
1620\end{proposition}
1621
1622\begin{proof}
1623Let~$x$ denote the image of $\e_j\in A_f(\C)$,
1624and set $I=\Ann(x)\subset\T$.   Though we write $A_f(\C)$ here and
1625below, we will always work within the subgroup of $A_f(\C)$ generated
1626by the image of $\sM_k(N,\eps;\Z)$ under the period map.
1627
1628First we check that the Hecke operators all act as
1629scalars on~$x$.  Since~$f$ is a {\em newform}, the Hecke
1630operators\index{Hecke operators} $T_p$, for $p\mid N$, act as~$0$ or
1631$\pm p^{k/2-1}$ on~$f$, and hence in the same way on $A_f(\C)$ (see,
1632e.g., the end of section 6 of \cite{diamond-im}).  If $p\nmid N$,
1633Lemma~\ref{lemma:eisact} shows that $T_p(x) = (1+p^{k-1})x$.
1634
1635Let $C=\Z{}x$ denote the cyclic subgroup of $A_f(\C)$ generated
1636by~$x$, so~$n$ is the order of~$C$.  Since the Hecke operators
1637act as scalars on~$C$, we are pleased to find that there is
1638an injection $\T/I\hookrightarrow C$ which sends
1639$T_p$ to $T_p(x)$.
1640
1641Setting $\sS=\sS_k(N,\eps;\Z)$ and applying Theorem~\ref{ratpart}
1642we find that
1643\begin{eqnarray*}
1644\pm \frac{L(A_f,j)}{\Omega_j} &=& [\Theta_f(\sS^+):\Theta_f(\T{}e)]\\
1645     &=& [\Theta_f(\sS^+):\Theta_f(I\e)]\cdot [\Theta_f(I\e):\Theta_f(\T{}\e)]\\
1646     &=& [\Theta_f(\sS^+):I\Theta_f(\e)]\cdot [I\Theta_f(\e):\T{}\Theta_f(\e)]\\
1647     &=& \frac{[\Theta_f(\sS^+):I\Theta_f(\e)]}{[\T{}\Theta_f(\e):I\Theta_f(\e)]}.
1648\end{eqnarray*}
1649To conclude that
1650$$\frac{[\Theta_f(\sS^+):I\Theta_f(\e)]}{[\T{}\Theta_f(\e):I\Theta_f(\e)]} \in \frac{1}{n}\Z$$
1651we make two observations.
1652By the construction of $A_f(\C)$, the ideal~$I$ consists of those
1653elements of~$\T$ that send $\Theta_f(\e)$ into $\Theta_f(\sS^+)$, so
1654$[\Theta_f(\sS^+):I\Theta_f(\e)]\in\Z$.  Second, there is a surjective map
1655$$\T/I \ra \frac{\T\Theta_f(\e)}{I\Theta_f(\e)}$$
1656sending $t$ to $t \Theta_f(\e)$, so $[\T{}\Theta_f(\e):I\Theta_f(\e)]$
1657divides $n=\#C=\#(\T/I)$.
1658\end{proof}
1659
1660
1661\begin{remark}[Historical notes]
1662In the special case when $k=2$, the modular symbol $\e_1$ corresponds
1663to $(0)-(\infty)\in J_0(N)$.  In this situation, Manin\index{Manin!comment on BSD} proves at the
1664bottom of page~28 of \cite{manin:parabolic} that $(0)-(\infty)\in 1665J_0(N)(\Q)$, and asserts in the footnote to
1666\cite[Cor.~3.6]{manin:parabolic} that $(0)-(\infty)$ has finite order.
1667Based on observations such as a special case of the above proposition,
1668he declares: These explicit formulas have the structure predicted by
1669the Birch-Swinnerton-Dyer conjectures.''
1670\index{BSD conjecture!Manin's remarks on}
1671
1672The main result of this section was inspired by a weaker result of
1673Agashe,\index{Agashe}
1674which can be found in Chapter~4 of~\cite{agashe:phd}.  Agashe
1675considers only the case $k=2$ and replaces~$n$ by the order of the
1676subgroup of $J_0(N)(\Qbar)$ generated by {\em all} cusps.
1677\end{remark}
1678
1679
1680\comment{
1681\begin{proposition}\label{cor:denominator}
1682Let $n$ be the order of the image in $A_f(\Q)$ of the point
1683$(0)-(\infty)\in J_0(N)(\Q)$.  Then
1684$$\frac{L(A_f,1)}{\Omega_1}\in \frac{1}{n}\Z.$$
1685\end{proposition}
1686Manin\index{Manin} proved at the bottom of page~28 of \cite{manin:parabolic}
1687that $(0)-(\infty)\in J_0(N)(\Q)$, and asserts in the footnote
1688to \cite[Cor.~3.6]{manin:parabolic} that $(0)-(\infty)$
1689has finite order.
1690
1691\begin{proof}
1692Let~$x$ denote the image of $(0)-(\infty)\in A_f(\Q)$
1693and set $I=\Ann(x)\subset\T$.   Since~$f$ is a {\em newform},
1694the Hecke operators\index{Hecke operators}
1695$T_p$, for $p\mid N$, act as~$0$ or $\pm 1$ on
1696$A_f(\Q)$ (see, e.g., the end of section 6 of \cite{diamond-im}).
1697If $p\nmid N$ a standard calculation (see, e.g., \cite[\S2.8]{cremona:algs})
1698combined with the Abel-Jacobi\index{Abel-Jacobi}
1699theorem shows that $T_p(x) = (p+1)x$.
1700In terms of homology, this is the assertion that
1701$(T_p-(p+1))\{0,\infty\} \in H_1(X_0(N),\Z)$ for $p\nmid N$.
1702
1703Let $C=\Z{}x$ denote the
1704cyclic subgroup of  $A_f(\Q)$ generated by~$x$,
1705so~$n$ is the order of~$C$.
1706There is an injection
1707$\T/I\hookrightarrow C$
1708sending $T_p$ to $T_p(x)$.
1709By Theorem~\ref{ratpart} we have
1710\begin{eqnarray*}
1711\pm L(A_f,1)/\Omega_f^0 &=& [\Theta(\sS^+):\Theta(\T{}e)]\\
1712     &=& [\Theta(\sS^+):\Theta(I\e)]\cdot [\Theta(I\e):\Theta(\T{}\e)]\\
1713     &=& [\Theta(\sS^+):I\Theta(\e)]\cdot [I\Theta(\e):\T{}\Theta(\e)]\\
1714     &=& \frac{[\Theta(\sS^+):I\Theta(\e)]}{[\T{}\Theta(\e):I\Theta(\e)]} \in \frac{1}{n}\Z.
1715\end{eqnarray*}
1716The final inclusion follows from two observations.
1717By Abel-Jacobi,~$I$ consists of those
1718elements of~$\T$ that send $\Theta(\e)$ into $\Theta(\sS^+)$, so
1719$[\Theta(\sS^+):I\Theta(\e)]\in\Z$.  Second, there is a surjective map
1720$$\T/I \ra \frac{\T\Theta(\e)}{I\Theta(\e)}$$
1721sending $t$ to $t \Theta(\e)$, so $[\T{}\Theta(\e):I\Theta(\e)]$
1722divides $n=\#C=\#(\T/I)$.
1723\end{proof}
1724}
1725
1726
1727\section{The Manin constant}\label{sec:maninconstant}
1728\index{Manin constant}
1729In this section $k=2$ and $\eps=1$; we
1730sometimes omit~$k$ and~$\eps$ from the notation.
1731The assumption that $k=2$ will be essential, because we
1732do not know how to define a Manin constant in other weights,
1733let alone bound it.
1734
1735Consider the optimal quotient~$A$ of~$J_0(N)$ corresponding
1736to a {\em newform}~$f$ on $\Gamma_0(N)$ of weight~$2$.
1737Let~$I_A$ be the kernel of the natural map from the Hecke algebra
1738\index{Hecke algebra} to $\End(A)$.
1739The \defn{Manin constant\label{defn:maninconstant}}~$c_A$ of~$A$ is
1740the lattice
1741index
1742 $$c_A := [S_2(\Gamma_0(N);\Z)[I_A]:H^0(\cA,\Omega_{\cA/\Z})]$$
1743taken inside of $S_2(\Gamma_0(N);\Q)$.
1744Though, a priori, $c_A$ is a rational number, the work of
1745\cite{katzmazur} implies that $c_A\in\Z$
1746(see, e.g., \cite{agashe-stein:manin}).
1747
1748
1749Generalizing a theorem of Mazur\index{Mazur}, we prove that~$c_A$
1750is a unit in $\Z[\frac{1}{2m}]$, where~$m$ is the largest
1751square dividing~$N$.  Essentially no new ideas beyond what Mazur used
1752are involved.
1753We then conjecture that $c_A=1$,
1754and give supporting numerical evidence.
1755
1756For related results involving modular building blocks'' for
1757$J_1(N)$, we refer the reader to~\cite[\S4]{ganz-lario:manin}.
1758
1759\subsection{The primes that might divide~$c_A$}
1760In the special case $\dim A=1$, the Manin constant\index{Manin constant}
1761is the classical Manin
1762constant of~$A$, and in~\cite{mazur:rational} Mazur\index{Mazur} proved
1763that~$c_A$ is a unit in $\Z[\frac{1}{2m}]$.
1764We generalize his proof to obtain the analogous result in
1765dimension greater than~$1$.
1766\begin{theorem}
1767Let $A$ be the new optimal quotient of~$J_0(N)$ corresponding
1768to a newform~$f$.  Then the Manin\index{Manin constant} constant~$c_A$ is a unit
1769in $\Z[\frac{1}{2m}]$, where~$m$ is the largest square
1770dividing~$N$.
1771\end{theorem}
1772\begin{proof}
1773The reader is strongly recommended to keep the proof of
1774Proposition~3.1 in \cite{mazur:rational} at hand while
1776
1777Let~$\pi$ denote the map $J_0(N)\ra A$;
1778let~$\cA$ denote the N\'eron model\index{N\'eron model}
1779of~$A$ over~$R:=\Z[\frac{1}{2m}]$, and~$\cJ$ the
1780N\'eron model of $J_0(N)$ over~$R$.
1781Let~$\cX$ be the minimal proper regular model for $X_0(N)$ over~$R$.
1782As in Mazur's\index{Mazur} proof in~\cite{mazur:rational}, consider the diagram
1783\begin{equation}\label{eqn:qexp}
1784H^0(\cA,\Omega_{\cA}) \xrightarrow{\pi^*} H^0(\cJ,\Omega_{\cJ})
1785                      \isom H^0(\cX,\Omega_\cX^{\text{reg}})
1786                          \xrightarrow{\text{ $q$-exp }} R[[q]].
1787\end{equation}
1788(Note that $\Omega_\cX^{\text{reg}}$'' is not defined to be the usual
1789sheaf of differentials; see, e.g., the discussion
1790in \cite[pg.~67]{mazur:eisenstein}.)
1791The map~$\pi^*$ must be an inclusion, by \cite[Cor.~1.1]{mazur:rational}.
1792To show that the Manin constant is a unit in~$R$, it
1793suffices to check that the image of $H^0(\cA,\Omega_{\cA})$
1794in $R[[q]]$ is {\em saturated}\index{Saturated}, in the sense that the
1795cokernel is torsion free; indeed, the image of
1796$S_2(\Gamma_0(N);R)[I]$ is saturated and
1797$S_2(\Gamma_0(N);R)[I]\tensor\Q = 1798\text{$q$-exp}(\pi^*(H^0(\cA,\Omega_{\cA})))\tensor\Q$.
1799
1800For the image of $H^0(\cA,\Omega_{\cA})$ in $R[[q]]$ to be
1801saturated means that the quotient~$D$
1802is torsion free.  Let~$\ell$ be a prime not dividing~$2m$;
1803tensoring
1804$$0\ra H^0(\cA,\Omega_{\cA})\xrightarrow{\text{q-exp}} 1805 R[[q]]\ra D\ra 0$$
1806with~$\Fl$ we obtain
1807$$0 \ra D[\ell] \ra H^0(\cA,\Omega_{\cA})\tensor\Fl\ra 1808 \Fl[[q]] \ra D\tensor\Fl \ra 0.$$
1809Here we have used that $\Tor^1(D,\Fl)$ is the $\ell$-torsion in~$D$,
1810and that $\Tor^1(-,\Fl)$ vanishes on the torsion-free group $R[[q]]$.
1811(Alternatively, we could have used the snake lemma\index{Snake lemma}.)
1812To show that $D[\ell]=0$, it suffices to prove that the map
1813$\Psi:H^0(\cA,\Omega_{\cA})\tensor\Fl\ra \Fl[[q]]$
1814is injective.
1815
1816Since $\ell\neq 2$ and~$A$ is an optimal quotient,
1817\cite[Cor 1.1]{mazur:rational} gives an exact sequence
1818  $$0 \ra H^0(\cA/\Zl,\Omega_{\cA/\Zl}) \ra 1819 H^0(\cJ/\Zl,\Omega_{\cJ/\Zl}) \ra 1820 H^0(\cB/\Zl,\Omega_{\cB/\Zl}) \ra 0$$
1821where $\cB$ is the N\'eron model
1822of $\ker(J\ra A)$.  In particular, $H^0(\cB/\Zl,\Omega_{\cB/\Zl})$
1823is torsion free, so
1824\begin{align*}
1825H^0(\cA/\Zl,\Omega_{\cA/\Zl})\tensor\Fl \ra
1826          H^0(\cJ/\Zl,\Omega_{\cJ/\Zl})\tensor\Fl
1827       &\isom H^0(\cX/\Zl,\Omega^{\text{reg}}_{\cX/\Zl})\tensor\Fl\\
1828       &\isom H^0(\cX/\Fl,\Omega^{\text{reg}}_{\cX/\Fl})
1829\end{align*}
1830is injective. (The last isomorphism is by
1831\cite[Prop.~3.3, pg.~68]{mazur:eisenstein}.)
1832We also remark that
1833$$H^0(\cA,\Omega_{\cA})\tensor\Fl\isom 1834H^0(\cA/\Zl,\Omega_{\cA/\Zl})\tensor\Fl,$$
1835because~$\Zl$ is torsion free, hence flat over~$R$.
1836Thus the map
1837$$H^0(\cA,\Omega_{\cA})\tensor\Fl\ra 1838H^0(\cX/\Fl,\Omega^{\text{reg}}_{\cX/\Fl})$$
1839is injective.
1840
1841If $\ell\nmid N$, then injectivity of~$\Psi$ now follows from
1842the $q$-expansion principle, which asserts that the
1843$q$-expansion map $H^0(\cX/\Fl,\Omega^{\text{reg}}_{\cX/\Fl})\ra \Fl[[q]]$
1844is injective.
1845
1846Suppose~$\ell$ does divide~$N$, and let
1847$\omega\in \ker(\Psi)$.
1848Since $\ell \mid N$ and $\ell\nmid 2m$, we have that $\ell \mid\mid N$;
1849thus $\cX/\Fl$ breaks up into a union of two irreducible
1850components, and the $q$-expansion principle\index{$q$-expansion principle}
1851implies only that~$\omega$
1852vanishes on the irreducible component containing the cusp~$\infty$.
1853However, since~$A$ is {\em new} and corresponds to a {\em single}
1854eigenform,~$\omega$ is an eigenvector for the involution~$W_N$
1855(since~$f$ and all of its conjugates are).  Since~$W_N$ permutes
1856the two components,~$\omega$ must be~$0$ on all $\cX/\Fl$.
1857Therefore $\omega=0$, and hence~$\Psi$ is injective.
1858\end{proof}
1859
1860\subsection{Numerical evidence for the $c_A=1$ conjecture}%
1862\index{Conjecture!that Manin constant equals $1$|textit}%
1863In the paper~\cite{empirical}, the authors
1864show that $c_A=1$ for~$28$ two-dimensional optimal
1865quotients\index{Optimal quotient}
1866of $J_0(N)$ (see Section~\ref{sec:analytic-empirical}).
1867The non-square-free levels treated are:
1868 $$N=3^2\cdot 7,\quad 3^2\cdot 13, 1869 \quad 5^3,\quad 3^3\cdot 5,\quad 3\cdot 7^2, 1870 \quad 5^2\cdot 7,\quad 2^2\cdot 47,\quad 3^3\cdot 7.$$
1871In every case, $c_A = 1$.
1872
1873\begin{conjecture}[Agashe\index{Conjecture!Agashe and Stein}%
1874\index{Agashe!conjecture of}\index{Agashe}]
1875Let~$A$ be an optimal quotient of $J_0(N)$, and let
1876$c_A$ be the corresponding Manin constant\index{Manin constant}.
1877Then $c_A=1$.
1878\end{conjecture}
1879
1880
1881\section{Analytic invariants}%
1882\index{Analytic invariants}%
1883\label{sec:analytic}%
1884Fix a newform
1885    $$f =\sum_{n\geq 1} a_n q^n\in S_k(N,\eps),$$
1886{\bf and assume that $\eps^2=1$.}
1887\begin{remark}
1888Our assumption that $\eps^2=1$ does not imply that~$f$ has totally
1889real Fourier coefficients.
1890There is an eigenform in  $S_2(24,\eps)$ whose Fourier coefficients
1891are not totally real, where~$\eps$ is one of the
1892characters of conductor~$8$.
1893\end{remark}
1894
1895Let $K_f = \Q(\ldots a_n \ldots)$ and
1896let $f_1,\ldots,f_d$ be the Galois conjugates of~$f$,
1897where $d=[K_f:\Q]$.
1898As in Section~\ref{sec:tori},
1899we consider the complex torus\index{Complex torus} $A_f$ attached to~$f$.
1900In this section we describe how to compute the torus $A_f$ and
1901the special values at the critical integers $1,2,\ldots,k-1$
1902of the~$L$ function $L(A_f,s)$ associated to $A_f$.
1903(See~\ref{defn:lseries} for the definition of $L(A_f,s)$.)
1904
1905Let
1906  $$f = \sum_{n\geq 1} a_n q^n \in M_k(N,\eps)$$
1907be a modular form (we do not assume
1908that~$f$ is an eigenform).
1909We recall the integration pairing\index{Integration pairing}
1910of Theorem~\ref{thm:perfectpairing} (which we normalize
1911by $-2\pi i$ for convenience):
1912$$1913 \langle\,, \,\rangle:\, M_k(N,\eps) \cross \sM_k(N,\eps) 1914 \lra \C$$
1915$$\langle f , P\{\alp,\beta\}\rangle = 1916 -\twopii \int_{\alp}^{\beta} f(z)P(z,1) dz.$$
1917Let $I_f\subset \T$ be the kernel of the
1918map $\T\ra K_f$ sending~$T_n$ to~$a_n$.
1919The integration pairing
1920gives rise to the period mapping\label{defn:periodmapping}
1921$$\Phi_f : \sM_k(N,\eps) \ra \Hom_\C(S_k(N,\eps)[I_f],\C),$$
1922and $A_f = \Hom_\C(S_k(N,\eps)[I_f],\C)/\Phi_f(\sS_k(N,\eps))$
1923is the cokernel.
1924
1925\subsection{Extended modular symbols}\label{defn:extendedmodsyms}%
1926\index{Extended modular symbols|textit}%
1927For the purposes of computing periods, it
1928is advantageous to extend the notion of modular
1929symbols\index{Modular symbols} to allows symbols of the form
1930$P\{z,w\}$ where~$z$ and~$w$ are now
1931arbitrary elements of $\h^*=\h\union\P^1(\Q)$.
1932The  free abelian group $\esM_k$
1933of \defn{extended modular symbols}
1934is spanned by such symbols, and is of uncountable
1935rank over~$\Z$.  However, it is still equipped with
1936an action of $\gzero$ and we can form the
1937largest torsion-free quotient
1938$\esM_k(N,\eps)$ of $\esM_k$ by
1939the relations $\gam x = \eps(\gam)x$ for
1940$\gam\in\gzero$.
1941
1942The integration
1943pairing\index{Integration pairing!and extended modular symbols}
1944extends to $\esM_k(N,\eps)$.  There is a natural
1945embedding
1946$\iota: \sM_k(N,\eps)\hookrightarrow \esM_k(N,\eps)$
1947which respects the pairing in the sense that
1948   $\langle f, \iota(x)\rangle = \langle f , x\rangle.$
1949In many cases it is advantageous to replace
1950$x\in\sM_k(N,\eps)$ first by $\iota(x)$, and then
1951by an equivalent sum $\sum y_i$ of symbols
1952$y_i\in \esM_k(N,\eps)$.
1953The period
1954   $\langle f, x\rangle$
1955is then replaced by the  equivalent
1956sum of periods $\sum \langle f , y_i\rangle$.
1957The latter is frequently {\em much} easier to approximate
1958numerically.
1959
1960
1961\subsection{Numerically computing period integrals}
1962Consider a point~$\alp$ in the upper half plane
1963and any one of the (extended) modular
1964symbols\index{Extended modular symbols}
1965$X^mY^{k-2-m}\{\alp,\infty\}$.
1966Given a cusp form $g =\sum_{n\geq 1} b_n q^n\in S_k(N,\eps)$
1967and an integer $m\in \{0,1,\ldots,k-2\}$, we find that
1968\begin{equation}\label{intsum}
1969\langle g, \, X^mY^{k-2-m}\{\alpha,\infty\}\rangle =
1970\twopii \int_{\alpha}^{i\infty} g(z)z^m dz =
1971\twopii \sum_{n=1}^{\oo} b_n \int_{\alpha}^{i\infty} e^{2\pi i n z} z^m dz.
1972\end{equation}
1973The reversal of summation and integration is justified because
1974the imaginary part of~$\alp$ is positive so that the sum
1975converges absolutely.  This is made explicit in the following
1976lemma, which can be proved using repeated integration by parts.
1977\begin{lemma}\label{lem:intexp}
1978\begin{equation}\label{intexp}
1979\int_{\alpha}^{i\infty} e^{2\pi i n z} z^m dz
1980   \,\,=\,\, e^{2\pi i n \alpha}
1981      \sum_