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