\comment{
$Header: /home/was/papers/thesis/RCS/algorithms.tex,v 1.14 2000/05/15 00:13:18 was Exp $
$Log: algorithms.tex,v $
Revision 1.14 2000/05/15 00:13:18 was
quick fix!
Revision 1.13 2000/05/10 20:31:51 was
done.
Revision 1.12 2000/05/10 09:30:12 was
indexing and cleaning up.
Revision 1.11 2000/05/10 03:45:57 was
Wrote an introduction.
Revision 1.10 2000/05/09 22:47:19 was
fixed modular degree notation m_ instead of \delta_
Revision 1.9 2000/05/09 19:51:48 was
Fixed section{The Cap} problem
Revision 1.8 2000/05/09 19:49:45 was
More details on the modular degree.
Revision 1.7 2000/05/08 18:47:46 was
added lario ref
Revision 1.6 2000/05/08 03:27:43 was
Fixed errors pointed out by Hendrik.
}
\chapter{Applications of modular symbols}
\label{chap:computing}
In the previous chapter we introduced several spaces of modular
symbols, and observations such as ``Manin's trick'' suggested that we
could compute with them. The duality between modular symbols and
modular forms hints that modular symbols might be useful in computing
information about modular forms. In the present chapter, we gather
together the fruits of our investigation into this connection.
Sections~\ref{sec:computingmk}--\ref{sec:decomposemodsym} of this
chapter give a method to compute the irreducible components of the
spaces $\sM_k(N,\eps)$ of modular symbols. In
Section~\ref{sec:intersection} we observe that computing intersections
of certain abelian varieties can be reduced to linear algebra
over~$\Z$ by viewing the abelian varieties as complex tori and
considering the appropriate diagrams. In
Sections~\ref{sec:ratperiod}, we continue this trend by pointing out
that many invariants of the complex torus attached to a modular form
can be computed without computing any approximate period lattices. In
Section~\ref{sec:torsionsubgroup}, we discuss well-known methods for
computing both an upper and lower bound on the order of the torsion
subgroup of certain abelian varieties. Section~\ref{sec:moddeg}
presents an algorithm for computing the modular degree of the complex
torus associated to a newform.
In Section~\ref{sec:ratpartformula} we aim squarely at the
problem of gathering data related to the Birch and Swinnerton-Dyer
conjecture\index{BSD conjecture!and $L(A,j)/\Omega_j$}
and its generalizations, where we give a formula for the
rational numbers $|L(A_f,j)/\Omega_j|$ attached to a newform. In
Section~\ref{sec:maninconstant} we compare the ratio computed in the
previous section to the one considered in the Birch and
Swinnerton-Dyer conjecture;\index{BSD conjecture}
the two numbers differ by a Manin\index{Manin}
constant, which we bound. Finally, in Section~\ref{sec:analytic} we
give algorithms for approximating the period lattice and related
numerical quantities associated to a newform of arbitrary weight.
\section{Computing the space of modular symbols}
\index{Modular symbols!computing}
\label{sec:computingmk}
\begin{definition}
Let~$W$ be a subspace of a finite-dimensional vector space~$V$.
To \defn{compute} the quotient $V/W$ means to
give a matrix representing the projection $V\ra V/W$, with
respect to some basis for~$V$ and some basis~$B$ for $V/W$, along with
a lift to~$V$ of each element of~$B$.
\end{definition}
In other words, to compute $V/W$ means to create a
reduction function that assigns
to each element of~$V$ its canonical representative
on the ``free basis''~$B$.
Let~$N$ be a positive integer, fix a mod~$N$ Dirichlet
character~$\eps$\index{Dirichlet character}, let
$K:=\Q[\eps]$ be the smallest extension
containing the values of~$\eps$, and let $\O:=\Z[\eps]$.
\begin{algorithm}\label{alg:MkNK}
\index{Algorithm for computing!space of modular symbols}
Given a positive integer~$N$, a Dirichlet
character~$\eps$\index{Dirichlet character},
and an integer $k\geq 2$
this algorithm computes $\sM_k(N,\eps;K)$.
We compute the quotient presentation given
in Theorem~\ref{thm:maninsymbols}
in three steps.
\begin{enumerate}
\item Let $V_1$ be the finite-dimensional $K$-vector space
generated by the Manin symbols\index{Manin symbols}\index{Manin}
$[X^iY^{k-2-i}, (u,v)]$
for $i=0,\ldots, k-2$ and $0\leq u,v < N$ with $\gcd(u,v,N)=1$.
Let~$W_1$ be the subspace of~$V_1$ generated by all differences
$$[X^iY^{k-2-i}, (\lambda u,\lambda v)] -
\eps(\lambda)[X^iY^{k-2-i}, (u, v)].$$
Because all relations are two-term, it
is easy to compute $V_2:=V_1/W_1$.
In computing this quotient, we do not have to
explicitly compute the {\em large} matrix representing
the linear map $V_1\ra V_2$, as it can be replaced by a suitable
``reduction procedure'' involving
arithmetic in $\Z/N\Z$.
\item
Let~$\sigma$ act on the set of
Manin symbols as in Section~\ref{sec:maninsymbols}; thus
$$[X^iY^{k-2-i}, (u, v)]\sigma = (-1)^i[Y^iX^{k-2-i}, (v,-u)].$$
Let~$W_2$ be the subspace of~$V_2$ generated by the sums
$x + x\sigma$ for $x\in V_2$.
Because all relations are two-term relations, it is
easy to compute $V_3 := V_2/W_2$.
\item Let~$\tau$ act on Manin symbols as in
Section~\ref{sec:maninsymbols};
thus
$$[X^iY^{k-2-i}, (u, v)]\tau =
[(-Y)^i(X-Y)^{k-2-i}, (v,-u-v)].$$
Note that the symbol on the right can be written as a sum
of generating Manin symbols\index{Manin symbols}.
Let~$W_3$ be the subspace of~$V_3$ generated by the sums
$x + x\tau + x\tau^2$
where~$x$ varies over the images of a basis of~$V_2$
({\em not} just a basis for $V_3$!).
Using some form of Gaussian elimination, we compute $V_3/W_3$.
Finally, $\sM_k(N,\eps;K)\ncisom V_3/W_3$.
\end{enumerate}
\end{algorithm}
\begin{proof}
For $\lambda \in (\Z/N\Z)^*$, denote by $\langle \lambda \rangle$ the right
action of~$\lambda$ on Manin symbols\index{Manin symbols}; thus
$$[X^iY^{k-2-i}, (u,v)]\langle \lambda \rangle
= [X^iY^{k-2-i}, (\lambda{}u,\lambda{}v)].$$
By Theorem~\ref{thm:maninsymbols} the space $\sM_k(N,\eps;K)$ is isomorphic
to the quotient of the vector spaces~$V_1$ of Step~1 modulo the relations
$x+x\sigma=0$, $x+x\tau+x\tau^2=0$, and $x\langle \lambda \rangle=\lambda x$
as~$x$ varies over all Manin symbols and~$\lambda$ varies over $(\Z/N\Z)^*$.
As motivation, we note that a naive
computation of $V_1$ modulo the $\sigma$, $\tau$, and
$\langle \lambda\rangle$ relations using Gaussian elimination
is far too inefficient. This is why we compute the
quotient in three steps. The complexity of Steps~1 and
Steps~2 are negligible. The difficulty occurs in Step~3;
at least the relations of this step occur in a space of dimension much
smaller than that of~$V_1$.
To see that the algorithm is correct, it is necessary only to observe
that $\sigma$ and $\tau$ both commute with all diamond-bracket operators
$\langle \lambda \rangle$; this is an immediate consequence of the
above formulas. We remark that in Step~3 it is in
general {\em necessary} to compute the quotient
by all relations $x + x\tau + x\tau^2$ with~$x$ the image of a basis
vector for $V_2$ instead
of just~$x$ in~$V_3$ because~$\sigma$ and~$\tau$ do not commute.
\end{proof}
\begin{remark}
In implementing the above algorithm, one should take special care in
Steps~1 and~2 because the relations can together force certain of the
Manin symbols to equal~$0$. For example, there might be relations of
the form $x_1+x_2=0$ and $x_1-x_2=0$ which together force $x_1=x_2=0$.
\end{remark}
\begin{remark}
To compute the plus-one quotient
$\sM_k(N,\eps;K)_{+}$, it
is necessary to modify Step~2 of Algorithm~\ref{alg:MkNK}
by including in~$W_2$ the differences $x - x I$
where $I=\abcd{-1}{0}{\hfill 0}{1}$, and
$$[X^iY^{k-2-i}, (u,v)] I
= (-1)^i[X^iY^{k-2-i}, (-u,v)].$$
Likewise, to compute the minus-one quotient we include the sums $x + x I.$
Note, as in the remarks in the proof of Algorithm~\ref{alg:MkNK},
we can not add in the~$I$ relations in Step~1 because~$I$ and~$\sigma$
do not commute.
\end{remark}
\begin{algorithm}\label{alg:MkNO}
\index{Algorithm for computing!integral modular symbols}
Given a positive integer~$N$, a Dirichlet
character~$\eps$\index{Dirichlet character}, and an integer $k\geq 2$,
this algorithm computes the $\O$-modules $\sM_k(N,\eps)$ and
$\sS_k(N,\eps)$. (We assume as given algorithms for performing
standard operations on $\O$-modules.)
\begin{enumerate}
\item Using Algorithm~\ref{alg:MkNK}
compute the $K$-vector space $V:=\sM_k(N,\eps;K)$.
\item Compute the $\O$-lattice~$L$ in~$V$ generated
by the classes of the finitely many symbols $[X^iY^{k-2-i}, (u,v)]$
for $i=0,\ldots, k-2$ and $0\leq u,v < N$ with $\gcd(u,v,N)=1$.
It is only necessary to take one symbol in each
$\eps$-equivalence class, so there are
$(k-2+1)\cdot\#\P^1(\Z/N\Z)$ generating symbols.
This computes $\sM_k(N,\eps)$.
\item To compute the submodule $\sS_k(N,\eps)$ of~$L$, we use
the algorithm of Section~\ref{sec:computeboundary}
to compute the
boundary map $\delta:\sM_k(N,\eps;K)\ra B_k(N,\eps;K)$.
Then $\sS_k(N,\eps)$ is the kernel of~$\delta$ restricted
to the lattice~$L$.
\end{enumerate}
\end{algorithm}
As a check, using the formulas of Section~\ref{sec:dimensionformulas},
we compute the dimension of the space $S_k(N,\eps)$ of cusp
forms and compare with the dimension of $\sS_k(N,\eps;K)$
computed in Algorithm~\ref{alg:MkNO}. The latter dimension must
equal twice the former one.
\section{Computing the Hecke algebra}
\index{Hecke algebra!computation of}
\label{sec:computinghecke}
In this section we give an upper bound on the number of Hecke
operators needed to generate the Hecke algebra
\index{Hecke algebra!generators as module}
as a $\Z$-module. The bound on Hecke
operators\index{Hecke operators} is an application
of~\cite{sturm:cong}, which was described to the author by
Ribet\index{Ribet} and Agashe\index{Agashe} when $k=2$ and the level
is prime. There are much better bounds on the number of Hecke
operators needed to generate the Hecke algebra
\index{Hecke algebra!generators as ring}
as a {\em ring}, but we do not investigate them here.
Let~$\Gamma$ be a subgroup of $\SL_2(\Z)$ that contains $\Gamma_1(N)$
for some~$N$. Let $S_k(\Gamma;\C)$ be the space of weight-$k$ cuspforms
for~$\Gamma$, and let $\T\subset\End(S_k(\Gamma;\C))$ be the
corresponding Hecke algebra. We now give a bound~$r$ such
that the Hecke operators~$T_n$\index{Hecke operators}, with $n\leq r$, generate~$\T$ as a
$\Z$-module.
For any ring $R\subset \C$, let $S_k(\Gamma;R)$ denotes the space of
cuspforms for~$\Gamma$ with Fourier
coefficients in~$R$.
Since $S_k(\Gamma;\C) = S_k(\Gamma;\Z)\tensor_\Z \C$, it makes sense to define
$$S_k(\Gamma;R):=S_k(\Gamma;\Z)\tensor_{\Z} R$$
for {\em any} ring $R$.
The following proposition is well known.
\begin{proposition}\label{prop:perfectpair}
For any ring~$R$, the pairing
$$ \T_R\tensor_RS_k(N;R) \ra R$$
that sends $(T,f)$ to $a_1(Tf)$
is a perfect pairing, where
$\T_R = \T\tensor_{\Z} R$. Furthermore, we have $(T_n,f)=a_n(f)$, where $T_n$ is
the $n$th Hecke operator.
\end{proposition}
Let
$$\mu = [\sltwoz:\Gamma],$$
and denote by $\lceil{}x\rceil$ the smallest integer $\geq x$.
\index{Bound of!Sturm}\index{Sturm bound}
\begin{theorem}[Sturm]
\label{thm:sturm}
Let~$\lambda$ be a prime ideal in the ring~$\O$ of integers in some
number field. If $f\in S_k(\Gamma;\O)$ satisfies
$a_n(f)\con 0\pmod{\lambda}$ for $n\leq \lceil{}\frac{k}{12}\mu\rceil$,
then $f\con 0\pmod{\lambda}$.
\end{theorem}
\begin{proof}
Theorem 1 of \cite{sturm:cong}.
\end{proof}
\begin{proposition}\label{prop:determine}
If $f\in S_k(\Gamma)$ satisfies
$a_n(f)=0$ for
$n\leq r=\left\lceil\frac{k}{12}\mu\right\rceil$,
then $f=0$.
\end{proposition}
\begin{proof}
We must show that the composite map
$S_k(\Gamma)\hookrightarrow\C[[q]]\into\C[[q]]/(q^{r+1})$
is injective. Because~$\C$ is a flat $\Z$-module and
$S_k(\Gamma;\Z)\tensor\C = S_k(\Gamma)$, it suffices
to show that the map $F:S_k(\Gamma;\Z)\into\Z[[q]]/(q^{r+1})$ is injective.
Suppose $F(f)=0$, and let~$p$ be a prime number.
Then $a_n(f)=0$ for $n\leq r$, hence plainly
$a_n(f)\con 0\pmod{p}$ for any such~$n$.
Theorem~\ref{thm:sturm} implies that $f\con 0\pmod{p}$.
Duplicating this argument shows that the coefficients
of~$f$ are divisible by all primes~$p$, so they are~$0$.
\end{proof}
\begin{theorem}\label{thm:bound}
As a $\Z$-module, $\T$ is generated by $T_1,\ldots,T_r$,
where $r=\lceil \frac{k}{12}\mu \rceil $.
\end{theorem}
\begin{proof}
Let~$Z$ be the submodule of~$\T$ generated by
$T_1,T_2,\ldots,T_r$. Consider the exact sequence of
additive abelian groups
$0\into Z \xrightarrow{\,i\,} \T \into \T/Z \into 0.$
Let~$p$ be a prime and tensor this sequence with~$\F_p$ to obtain
the exact sequence
$$Z\tensor \F_p\xrightarrow{\,\overline{i}\,}
\T\tensor\F_p \into (\T/Z)\tensor\F_p\into 0.$$
Put $R=\Fp$ in Proposition~\ref{prop:perfectpair}, and suppose that
$f\in S_k(N,\Fp)$ pairs to~$0$ with each of $T_1,\ldots, T_r$.
Then by Proposition~\ref{prop:perfectpair}, $a_m(f)=a_1(T_m f)=0$ in
$\Fp$ for each~$m$, $1\leq m\leq r$. Theorem~\ref{thm:sturm}
then asserts that $f = 0$. Thus the pairing, when restricted
to the image of $Z\tensor\Fp$ in $\T\tensor\Fp$, is also perfect. Thus
$\dim_{\Fp} \overline{i}(Z\tensor\Fp)
= \dim_{\Fp} S_k(N,\Fp)= \dim_{\Fp} \T\tensor\Fp,$
so $(\T/Z) \tensor \F_p = 0$; repeating this argument for
all~$p$ shows that $\T/Z=0$.
\end{proof}
\section{Representing and enumerating Dirichlet characters}
Recall that a
\defn{Dirichlet character}
\index{Dirichlet character}
is a homomorphism $\eps:(\Z/N\Z)^*\ra \C^*$.
The following lemma is well known.
\begin{lemma}
If~$p$ is an odd prime, then $(\Z/p^n\Z)^*$ is a cyclic group.
The group $(\Z/2^n\Z)^*$ is generated by~$-1$ and~$5$.
\end{lemma}
We use the following representation of Dirichlet characters.
Factor~$N$ as a product of prime powers: $N=\prod_{i=1}^r p_i^{e_i}$ with
$p_i < p_{i+1}$ and each $e_i>0$; then
$(\Z/N\Z)^* \isom \prod_{i=1}^r (\Z/p_i^{e_i}\Z)^*$.
If $p_i$ is odd then the lemma implies that $(\Z/p_i^{e_i}\Z)^*$ is cyclic.
If $p_1=2$, then $(\Z/p_1^{e_1}\Z)^*$ is a product
$\langle -1 \rangle \cross \langle 5 \rangle$
of two cyclic groups, both possibly trivial.
For each~$i$, we let $a_i\in(\Z/p_i^{e_i}\Z)^*$ be the smallest generator of
the $i$th factor $(\Z/p_i^{e_i}\Z)^*$. If $p_1=2$, let $a_1$ and $a_2$
correspond to the two factors $\langle -1 \rangle$ and
$\langle 5 \rangle$, respectively; then $a_3$ corresponds to $p_2$, etc.
Here~$a_i$ is smallest in the
sense that the minimal lift $\tilde{a}_i\in\Z_{>0}$ is smallest.
Let~$n$ be the exponent of $(\Z/N\Z)^*$, and
let $\zeta=e^{2\pi i /n}\in \C^*$.
To give~$\eps$ is the same as giving the images of each generator
of~$a_i$ as a power of~$\zeta$. We thus represent~$\eps$ as
a vector of elements of~$\C^*$ with respect to a canonically chosen,
but unnatural, basis.
Alternatively, the vector representing a character~$\eps$ can be equivalently
viewed as a vector in $(\Z/n\Z)^r$, where again~$n$ is the exponent of $(\Z/N\Z)^*$.
Such a vector represents a character if and only if the $i$th component
of the vector has additive order
dividing $\vphi(p_i^{e_i})$. If $p_1=2$, then
there are $r+1$ entries instead of~$r$ entries, and the condition
is suitably modified.
If a vector $v=[d_1,\ldots,d_r]$ represents a character~$\eps$,
then each of the Galois conjugate characters is represented
by $[md_1,\ldots,md_r]$ where~$m$ varies over elements of
$(\Z/n\Z)^*$.
When performing actual machine computations, we work in the smallest
field that contains all of the values of~$\eps$.
Thus if $d=\gcd(d_1,\ldots,d_r,n)$, then we work in the subfield
$\Q(\zeta^d)$, which is cheaper than working in $\Q(\zeta)$.
It is sometimes important to work in characteristic~$\ell$.
Then the notation is as above, except~$\zeta$ is replaced by a
primitive $m$th root of unity, where~$m$ is the prime-to-$\ell$
part of~$n$. Note that the primitive
$n$th roots of unity in characteristic~$\ell$ need not be conjugate;
for example, both~$2$ and~$3$ are square roots of~$-1$ in $\F_5$, but
they are not conjugate. Thus we must specify~$\zeta$ as part
of the notation when giving a mod~$\ell$ Dirichlet character.
\begin{example}
Suppose~$N=p$ is an odd prime.
The group of mod~$p$ Dirichlet characters (in characteristic~$0$)
is isomorphic to
$\Z/(p-1)\Z$, and two characters~$a$ and~$b$ are Galois
conjugate if and only if there is an element $x\in(\Z/(p-1)\Z)^*$
such that $xa=b$.
A character is determined up to Galois conjugacy by its order,
so the set of classes of mod~$p$ Dirichlet characters are
in bijection with the set of divisors~$d$ of $p-1=\#(\Z/p\Z)^*$.
Let $p$ be an odd prime. The
quadratic mod~$p$ character is denoted $[(p-1)/2]$.
The quadratic mod~$2p$ character is denoted by
$[0,0,(p-1)/2]$; the quadratic mod~$4p$ character is denoted
$[(p-1)/2,0,(p-1)/2]$. If $n\geq 3$, then the exponent of
$(\Z/2^n\Z)^*$ is $2^{n-2}$, so the nontrivial
mod~$2^n$ character that factors through $(\Z/4\Z)^*$ is denoted
$[2^{n-3},0]$.
\end{example}
\begin{definition}\index{Dirichlet character!conductor of|textit}
\index{Conductor of Dirichlet character|textit}
The {\em conductor} of a character $\eps:(\Z/N\Z)^*\ra \C^*$
is the smallest divisor~$M$ of~$N$ such that~$\eps$ factors through
the natural reduction map $(\Z/N\Z)^*\ra (\Z/M\Z)^*$.
\end{definition}
For simplicity, we assume that~$N$ is odd.
To compute the conductor of~$\eps$, let~$v$ be the vector in
$(\Z/n\Z)^r$ that represents $\eps$, as above.
Since both
$(\Z/p_i^{e_i}\Z)^*$ and $(\Z/p_i^d\Z)^*$ are
cyclic and the reduction map is surjective,
we find that $p_i^d$, with $d\leq e_i$,
divides the conductor of~$\eps$ if and only if
the $i$th component of~$v$ has additive order
dividing $\vphi(p_i^{d})$. We can thus compute the
power of $p_i$ dividing the conductor of~$\eps$ by
computing the smallest~$d$ such that $p_i^d \con p_i^{d-1}$
modulo the order of the $i$th component of~$v$.
\section{The dimension of $S_k(N,\eps)$}
\index{Dimension of $S_k(N,\eps)$}
\label{sec:dimensionformulas}
An explicit formula for the dimension of $S_k(N,\eps)$ is given in
\cite{cohen-oesterle:dimensions}, without proof.
For the reader's convenience, we reproduce it here.
\begin{theorem}[Cohen-Oesterl\'{e}]
Let~$k\geq 2$ be an integer and $\eps:(\Z/N\Z)^*\ra\C^*$ be a Dirichlet character
such that $\eps(-1)=(-1)^k$. Then
\begin{align*}
\dim S_k(N,\eps) =
\delta &+
\frac{k-1}{12}\cdot N \cdot \prod_{p\mid N}\left(1+\frac{1}{p}\right)
\quad-\quad\frac{1}{2}\cdot \prod_{p\mid N} \lambda(r_p,s_p,p)\\
&+\gamma_k\hspace{-5ex}\sum_{\{ x \in (\Z/N\Z)^* \,:\, x^2+1 = 0\}} \hspace{-5ex}\eps(x)
\qquad+\qquad\mu_k\hspace{-5ex}
\sum_{\{ x \in (\Z/N\Z)^* \,:\, x^2+x+1= 0\}} \hspace{-5ex}\eps(x).
\end{align*}
Let~$f$ be the conductor of~$\eps$, i.e., the smallest~$M$
such that~$\eps$ factors through $(\Z/M\Z)^*$.
If $p\mid N$, then $r_p$ (resp. $s_p$) denotes the exponent
of~$p$ in the prime factorization of~$N$ (resp.~$f$).
Furthermore,
\begin{align*}
\lambda(r_p,s_p,p)
&:= \begin{cases}
p^{r'}+p^{r'-1} &
\text{if } 2s_p \leq r_p = 2r'\\
2p^{r'} & \text{if } 2s_p \leq r_p=2r'+1\\
2p^{r_p-s_p} & \text{if } 2s_p > r_p
\end{cases} \\
\gamma_k &:= \begin{cases}
0 & \text{if $k$ is odd}\\
-\frac{1}{4} & \text{if } k\con 2\pmod{4}\\
\frac{1}{4} & \text{if } k\con 0\pmod{4}
\end{cases} \\
\mu_k &:= \begin{cases}
0 & \text{if }k\con 1\pmod{3}\\
-\frac{1}{3} & \text{if } k\con 2\pmod{3}\\
\frac{1}{3} & \text{if } k\con 0\pmod{3}
\end{cases} \\
\delta &:= \begin{cases}
1 &\text{if $k=2$ and $\eps$ is trivial}\\
0 &\text{otherwise}
\end{cases}
\end{align*}
\end{theorem}
\comment{
An alternative, more cumbersome, way to compute the dimension
of $S_k(N,\eps)$ is to compute the trace of $T_1$ using the
trace formula; see~\cite{hijikata:trace}, where the formula is
given, along with a proof. The author of this thesis has done this and has
found that the resulting formulas look very similar; the answers given
are the same, but he was not able to simplify the trace
formula enough so that its evaluation is nearly as fast as
the Cohen-Oesterl\'e formula above.
}
\section{Decomposing the space of modular symbols}
\label{sec:decomposemodsym}
Consider the space $\sS_k(N,\eps)$ of cuspidal modular symbols
of level~$N$ and character~$\eps$ over $K=\Q(\eps)$.
In this section we describe how
to decompose the new part of $\sS_k(N,\eps)$
as a direct sum of $\T$-modules corresponding to the Galois conjugacy
classes of newforms with character~$\eps$. As an application, we can
compute the $q$-expansions of the normalized cuspidal newforms of
level $N$ and character $\eps$. Using the theory of
Atkin-Lehner~\cite{atkin-lehner} as extended by
Li~\cite{winnie:newforms}, it is then possible to construct a basis
for the space $S_k(N,\eps;\C)$ of cusp forms.
The algorithm is, for the most part, a straightforward generalization
of the method used by Cremona~\cite{cremona:algs}\index{Cremona} to
enumerate the $\Q$-rational weight-two newforms corresponding to
modular elliptic curves. Nevertheless, we present several tricks
learned in the course of doing computations, which speed up the
algorithm. One useful trick that Cremona also made use of
is to work in the space
dual to modular symbols\index{Modular symbols} as
described in the next section.
\subsection{Duality}
Let $K=\Q[\eps]$, and
let $\sS_k(N,\eps;K)^\dual$ denote $\Hom_K(\sS_k(N,\eps;K),K)$
equipped with its natural right $\T$-action: for
$\vphi\in\sS_k(N,\eps;K)^\dual$,
$$(\vphi T)(x) = \vphi(Tx).$$
The natural pairing
\begin{equation}\label{eqn:pairing}
\langle\,,\,\rangle:\sS_k(N,\eps;K)^\dual \cross \sS_k(N,\eps;K) \ra K
\end{equation}
given by $\langle\vphi,x\rangle = \vphi(x)$
satisfies
$\langle\vphi{}T,x\rangle = \langle\vphi ,T{}x\rangle$.
Viewing the elements $T\in\T$ as sitting inside
$\End(\sS_k(N,\eps;K))$,
the transpose map $T\mapsto T^t$
allows us to view $\sS_k(N,\eps;K)^\dual$
as a left $\T$-module.
\begin{proposition}\label{prop:heckeduality}
Let $V\subset \sS_k(N,\eps;K)^{\new}$ be an irreducible
new $\T$-submodule and set $I=\Ann_\T V$.
Then the characteristic polynomial of each $T_p$ on
$\sS_k(N,\eps;K)^{\dual}[I]$ is the
same as the characteristic polynomial of $T_p$ on~$V$.
\end{proposition}
\begin{proof}
We may assume for the purposes of proving the proposition that $K=\Qbar$.
There is a basis of simultaneous $\T$-eigenvectors for
$\sS_k(N,\eps;K)^{\new}$. With respect to this basis,~$\T$
acts via diagonal matrices. The systems of eigenvalues coming
from the old subspace are distinct from the systems of
eigenvalues on the new space. Thus the dimension of
$\sS_k(N,\eps;K)^{\dual}[I]$
is the same as the dimension of~$V$, instead of being too large.
The proposition now follows by noting that the characteristic polynomial
of a matrix is the same as the characteristic polynomial of its
transpose.
\end{proof}
The degeneracy maps\index{Degeneracy maps} $\alp_t$ and $\beta_t$ of
Section~\ref{sec:degeneracymaps} give rise to
maps $\alp_t^{\dual}$ and $\beta_t^{\dual}$
between the dual spaces and having
the dual properties to those of $\alp_t$ and $\beta_t$.
In particular, they commute with the Hecke
operators\index{Hecke operators!and degeneracy maps}
$T_p$ for $p$ prime to $N$.
The new and old subspace\index{New subspace}\index{Old subspace}
of $\sS_k(N,\eps;K)^\dual$
are defined as in Definition~\ref{def:newandoldsymbols}.
\begin{algorithm}\label{alg:decompmknew}
\index{Algorithm for computing!decomposition of space of modular symbols}
This algorithm computes a decomposition
of $\sS_k(N,\eps;K)^{\dual\new}$ into irreducible submodules $V$.
Using Algorithm~\ref{alg:MkNK} compute $\sS_k(N,\eps;K)$.
Then compute the maps $\beta_t$ using Algorithm~\ref{alg:degenreps}
and intersect the transposes of their kernels in order to
obtain $\sS_k(N,\eps)^{\dual\new}$.
Compute the boundary map $\delta:\sS_k(N,\eps;K)\ra B_k(N,\eps;K)$
using Algorithm~\ref{alg:cusplist}.
We cut out the cuspidal submodule $\sS_k(N,\eps;K)^{\dual\new}$
using the Hecke operators,\index{Hecke operators}
Algorithm~\ref{alg:efficienttpdual},
and Proposition~\ref{prop:heckeduality}.
Set $p=2$ and perform the following steps.
\begin{enumerate}
\item Using Algorithm~\ref{alg:efficienttpdual},
compute a matrix $A$ representing the Hecke
operator $T_p$\index{Hecke operators}
on $\sS_k(N,\eps;K)^{\dual\new}$.
\item Compute and factor the characteristic polynomial~$F$ of~$A$.
\item For each irreducible factor~$f$ of~$F$
compute $V_f = \ker(f(A))$.
Then, compute the $+1$ and $-1$ eigen-subspaces $V_f^+$ and $V_f^-$
for the star involution. Let~$W$ denote one of these two eigen-subspaces,
and use the following criteria
to determine whether or not~$W$ is irreducible:
\begin{enumerate}
\item If~$p$ is greater than the Sturm
bound\index{Sturm bound}\index{Bound of!Sturm}
(see Theorem~\ref{thm:bound}) then~$W$
must be irreducible.
\item
If the characteristic polynomial of some element $T\in \T$
acting on $W$ is irreducible, then~$W$ is irreducible.
\end{enumerate}
\item If $W$ is irreducible, record~$W$ and consider
the next factor of the characteristic polynomial in step~3. Otherwise,
replace~$p$ by the next prime larger than~$p$ and replace
$\sS_k(N,\eps;K)^{\dual\new}$ by $W$,
then repeat the above sequence of steps, beginning with step~1.
\end{enumerate}
\end{algorithm}
\subsection{Efficient computation of Hecke operators on the dual space}
\index{Hecke operators!computation on subspace of dual}
\index{Algorithm for computing!Hecke operators on the dual}
In this section we give a method for computing the action
of the Hecke operators $T_p\in\T$ on
an invariant subspace
$V\subset \sS_k(N,\eps;K)^{\dual}$.
A naive way to compute the right action of $T_p$ on $V$
is to compute a matrix representing $T_p$ on $\sS_k(N,\eps;K)$,
transpose to obtain $T_p$ on $\sS_k(N,\eps;K)^\dual$,
and then restrict to~$V$ using Gaussian elimination.
To compute $T_p$ on $\sS_k(N,\eps;K)$, observe that $\sS_k(N,\eps;K)$
has a basis $e_1,\!\ldots,e_n$, where each $e_i$
is a Manin symbol\index{Manin symbols} $[P,(c,d)]$, and that the action
of $T_p$ on $[P,(c,d)]$ can be computed using
Section~\ref{subsec:heckeonmanin}.
In practice, $d=\dim V$ will often be much less than~$n$;
we now describe how to compute $T_p$ on~$V$ in $d/n$ of the
time it takes using the above naive method. This is a
substantial savings when~$d$ is small.
Transposing the injection
$V\hookrightarrow \sS_k(N,\eps;K)^{\dual}$,
we obtain a surjection $\sS_k(N,\eps;K)\ra V^\dual$.
There exists a subset $e_{i_1},\!\ldots, e_{i_d}$
of the $e_i$ whose image forms
a basis for $V^\dual$. With some care, it is then possible
to compute $T_p$ on $V^{\dual}$ by computing $T_p$ on each of
$e_{i_1},\!\ldots, e_{i_d}$.
In the rest of this section, we
describe in terms of matrices a definite way to carry out this
computation.
Let~$V$ be an $n\times m$ matrix whose rows generate an
$n$-dimensional subspace of an $m$-dimensional space of row vectors.
Let~$T$ be an $m\times m$-matrix and suppose that~$V$ has rank~$n$ and
that $VT$ is contained in the row space of~$V$. Let~$E$ be an
$m\times n$ matrix with the property that the $n\times n$ matrix $VE$
is invertible, with inverse~$D$.
\begin{proposition}
$VT = VTEDV.$
\end{proposition}
\begin{proof}
Observe that
$$V(EDV) = (VED)V = IV = V.$$
Thus right multiplication by $EDV$
$$ v \mapsto vEDV$$
induces the {\em identity map} on the row space of $V$.
Since $VT$ is contained in the row space of $V$, we have
$$(VT)EDV = VT,$$
as claimed.
\end{proof}
We have not computed $T$, but we can
compute $T$ on each basis element $e_1,\ldots,e_n$
of the ambient space--unfortunately, $n$ is extremely large.
Our problem: quickly compute the action of
$T^t$ on the invariant subspace spanned
by the rows of $V$. Can this be done without
having to compute $T$ on all $e_i$?
Yes, the following algorithm shows how using
a subset of only $d=\dim V$ of the $e_i$.
\begin{algorithm}\label{alg:efficienttpdual}
\index{Algorithm for computing!Hecke operators on the dual}
Let~$T$ be any linear transformation
which leaves~$V$ invariant and for
which we can compute $T(e_i)$ for $i=1,\ldots, d$.
This algorithm computes the matrix representing the
action of $T$ on $V$ while computing $T(e_i)$ for
only $\dim V$ of the~$i$.
Choose any $m\times n$ matrix~$E$ whose columns are
sparse linear combinations of the $e_i$ and such that
$VE$ is invertible.
For this we find a set of positions so that elements of the space
spanned by the columns of~$V$ are determined by the entries in
these spots. This is accomplished by row reducing, and setting~$E$
equal to the pivot columns.
Using Gaussian elimination, compute the inverse~$D$ of the
$n\times n$ matrix $VE$.
The matrix representing the action of~$T$ with respect
to~$V$ is then
$$V(TE)D=V(TE)(VE)^{-1}.$$
\end{algorithm}
\begin{proof}
Let~$A$ be any matrix so that
$VA$ is the $n\times n$ identity
matrix.
By the proposition we have
$$VTA = (VTEDV)A = VTED(VA) = VTED = V(TE)D.$$
To see that $VTA$ represents~$T$,
observe that by the proposition,
\begin{eqnarray*}
VTAV &=& (VTEDV)AV=(VTEDV\!A)V\\
&=& (VTED)(V\!A)V=(VTED)V=VT
\end{eqnarray*}
so that $VTA$ gives the correct linear combination of the rows of~$V$.
\end{proof}
\subsection{Eigenvectors}\label{sec:eigenvector}
Once a $\T$-simple subspace of $\sS^*$ has been identified, the
following algorithm, which was suggested to the author
by H.~Lenstra, produces an eigenvector
defined over an extension of the base field.
\begin{algorithm}
\index{Algorithm for computing!an eigenvector}
Let $A$ be an $n\times n$ matrix over an arbitrary field $K$ and
suppose that the characteristic polynomial $f(x)=x^n+\cdots+a_1 x + a_0$
of~$A$ is irreducible. Let $\alpha$ be a root of $f(x)$
in an algebraic closure~$\Kbar$ of~$K$.
Factor $f(x)$ over $K(\alp)$ as
$f(x) = (x-\alp) g(x)$.
Then for any element $v\in K^n$ the vector
$g(A)v$ is either $0$ or it is an eigenvector of~$A$ with eigenvalue~$\alp$.
The vector $g(A)v$ can be computed by finding
$Av$, $A(Av)$, $A(A(Av))$, and then using that
$$g(x)=x^{n-1}+c_{n-2} x^{n-2}+\cdots+c_1 x+ c_0,$$
where the coefficients $c_i$ are determined by the recurrence
$$c_0 = - a_0/\alp,\qquad c_i = (c_{i-1}-a_i)/\alp.$$
We will prove below that $g(A)v\neq 0$ for all vectors~$v$ not
in a proper subspace of $K^n$. Thus with high probability, a
``randomly chosen''~$v$ will have the property that $g(A)v\neq 0$.
Alternatively, if $v_1,\ldots v_n$ form a basis for $K^n$, then
$g(A)v_i$ must be nonzero for some~$i$.
\end{algorithm}
\begin{proof}
By the Cayley-Hamilton theorem \cite[XIV.3]{lang:algebra}
we have that $f(A)=0$. Consequently, for any $v\in K^n$,
we have $(A-\alp)g(A)v=0$ so that $A g(A)v = \alp v$.
Since $f$ is irreducible it is the polynomial of least
degree satisfied by $A$ and so $g(A)\neq 0$.
Therefore $g(A)v\neq 0$ for all $v$ not in the proper
closed subset $\ker(g(A))$.
\end{proof}
\subsection{Eigenvalues}\label{sec:eigenvalues}
\index{Eigenforms!computing}
In this section we give an algorithm for
computing the $q$-expansion of one of the newforms
corresponding to a factor of $\sS_k(N,\eps;K)^{\new}$.
This is a generalization of the algorithm described
in \cite[\S2.9]{cremona:algs}.
\begin{algorithm}\label{alg:eigenvalues}
\index{Algorithm for computing!eigenvalues}
Given a factor $V\subset \sS_k(N,\eps;K)^{\dual\new}$
as computed by Algorithm~\ref{alg:decompmknew}
this algorithm computes the $q$-expansion of
one of the corresponding Galois conjugate newforms.
\begin{enumerate}
\item Using Algorithm~\ref{alg:efficienttpdual} compute
the action of the $*$-involution (Section~\ref{sec:heckeops})
on~$V$. Then compute the $+1$ eigenspace $V^+\subset V$.
\item Find an element $T\in\T$\index{Hecke operators} such that the
characteristic polynomial of the matrix~$A$
of~$T$ acting on $V^+$ is irreducible.
Such a~$T$\index{Hecke operators}
must exist by the primitive element theorem
\cite[V.4]{lang:algebra}.
(Note: It is {\em not} always the case that $T$ can be
taken to equal some Hecke operator $T_n$. The first
example with $k=2$ and $\eps=1$ occurs at level $N=512$.)
\item Using Algorithm~\ref{sec:eigenvector} compute
an eigenvector~$e$ for~$A$ over an extension of~$K$.
\item Because~$e$ is an eigenvector and the pairing
given in Equation~\ref{eqn:pairing} respects the
Hecke action, we have that for any Hecke operator\index{Hecke operators}
$T_n$ and element $w\in \sS_k(N,\eps;K)$\footnote{In fact, any element
of $\sM_k(N,\eps;K)$ could be used!), that
$$a_n \langle e, w \rangle
= \langle e T_n, w\rangle
= \langle e, T_n w \rangle.$$
Choose~$w$ so that $\langle e,w\rangle \ne 0$. Then
$$a_n =\frac {\langle e, T_n w \rangle}
{\langle e, w \rangle}.$$
The $a_n$ can now be computed by
computing $\langle e, w \rangle$ once and for all,
and then computing $\langle e, T_n w \rangle$ for
each~$n$.
It is best to choose~$w$ in such a way that
$T_n w$ can be computed quickly.
\end{enumerate}
\end{algorithm}
The beauty of this algorithm is that when~$w$
is a Manin symbol\index{Manin symbols} $[P(X,Y),(c,d)]$ the
computation of $T_p w = \sum_{x\in R_p} wx$ is very quick, requiring
us to only sum over the Heilbronn
matrices\index{Heilbronn matrices} of determinant~$p$ once.
In practice we compute only the eigenvalues~$a_p$ using
the above algorithm, then use the following
recurrences to obtain the~$a_n$:
\begin{eqnarray*}
a_{nm} &=& a_n a_m \qquad\text{if $(n,m)=1$, and}\\
a_{p^r}&=& a_{p^{r-1}}a_p - \eps(p) p^{k-2} a_{p^{r-2}}.
\end{eqnarray*}
\subsection{Sorting and labeling eigenforms}
\label{sec:sorting}
\index{Ordering of eigenforms}
\index{Eigenforms!sorting and labeling}
Systematically ordering the factors is essential,
so that we can later refer to them.
In Section~\ref{sec:eigenvalues} we saw how to associate
to each new factor a sequence $a_n$ of Hecke eigenvalues.
These can be used to sort the factors.
Except in the case of weight~$2$ and trivial character,
we use the following ordering. To each eigenvector
associate the following sequence of integers
$$\tr(a_1), \tr(a_2), \,\tr(a_3),\, \tr(a_4),\,
\tr(a_5), \, \tr(a_6),\, \ldots$$
where the trace is from $K_f=\Q(\ldots a_n\ldots)$ down to $\Q$.
Sort the eigenforms by ordering the
sequences in dictionary order with
minus coming before plus.
Since we included $\tr(a_1)$, this ordering gathers together
factors of the same dimension.
Furthermore, the sequence of traces determines the Galois conjugacy class
of~$f$, because the
$g=\sum_{n\geq 1} \tr(a_n) q^n $
is the trace of~$f$, hence~$g$ lies in the $\C$-vector space
spanned by the Galois conjugates of~$f$.
When $k=2$ and the character is trivial we
use a different and somewhat complicated ordering
because it extends the notation for elliptic curves
that was introduced in the second edition of \cite{cremona:algs}
and has since become standard.
Sort the factors of $\sS_k(N,\eps)^{\new}$ as follows.
First by dimension, with smallest dimension first.
Within each dimension, sort in binary order,
by the signs of the Atkin-Lehner
\index{Atkin-Lehner involution!and ordering eigenforms}
involutions
with $-$ corresponding to~$0$ and~$+$ to~$1$. For example, if there
are three Atkin-Lehner involutions then the sign patterns
are sorted as follows:
$$+++, -++, +-+, --+, ++-, -+-, +--, ---.$$
Finally, let $p$ be the smallest prime not dividing $N$.
Within each of the Atkin-Lehner classes, sort by
the magnitudes of the $K_f/\Q$-trace of
$a_p$ breaking ties by letting the positive trace be first.
If there are still any ties, repeat the final step with the
next smallest prime not dividing~$N$, etc.
(Note: It's not clear to the author that ties will always eventually
be broken, though in his computation they always have been.)
\section{Intersections and congruences}
\index{Congruences!computing}
\label{sec:intersection}
Consider a complex torus $J=V/\Lambda$, and let
$A=V_A/\Lambda_A$ and $B=V_B/\Lambda_B$ be subtori whose
intersection $A\intersect B$ is finite.
\begin{proposition}\label{prop:intersection}
There is a natural isomorphism of groups
$$A\intersect B \isom
\left(\frac{\Lambda}{\Lambda_A + \Lambda_B}\right)_{\tor.}$$
\end{proposition}
\begin{proof}
There is an exact sequence
$$0\ra A\intersect B \ra A \oplus B \ra J.$$
Consider the diagram
$$\xymatrix{
& {\Lambda_A \oplus\Lambda_B}\ar[d] \ar[r] & {\Lambda} \ar[r]\ar[d]&
{\Lambda/(\Lambda_A + \Lambda_B)}\ar[d]\\
& {V_A \oplus V_B}\ar[d] \ar[r] & V \ar[r]\ar[d] & {V/(V_A+V_B)}\ar[d]\\
{A\intersect B}\ar[r] & A\oplus B\ar[r] & J \ar[r] & J/(A+ B).}$$
The snake lemma\index{Snake lemma} gives an exact sequence
$$0 \ra
A\intersect B \ra
\Lambda/(\Lambda_A + \Lambda_B) \ra
V/(V_A+V_B).$$
Since $V/(V_A+V_B)$ is a $\C$-vector space, the torsion
part of $\Lambda/(\Lambda_A + \Lambda_B)$ must map to~$0$.
No non-torsion in $\Lambda/(\Lambda_A + \Lambda_B)$ could
map to~$0$, because if it did then $A\intersect B$ would not
be finite. The lemma follows.
\end{proof}
The following formula for the intersection of~$n$
subtori is obtained in a similar way.
\begin{proposition}
For $i=1,\ldots,n$ let $A_i = V_i/\Lambda_i$ be a subtorus of
$J=V/\Lambda$, and assume that each pairwise intersection
$A_i \intersect A_j$ is finite.
Then
$$A_1\intersect \cdots \intersect A_n
\isom
\left(\frac{\Lambda\oplus \cdots \oplus \Lambda}
{f(\Lambda_1\oplus\cdots\oplus \Lambda_n)}\right),$$
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)$.
\end{proposition}
\begin{remark}
Using this proposition the author constructed the
T-shirt\index{T-shirt design} design in Figure~\ref{cap:tshirt}.
\begin{figure}
\begin{center}
\includegraphics{shirt.eps}
\end{center}
\caption{T-shirt design}
\label{cap:tshirt}
\end{figure}
\end{remark}
\begin{example}\label{ex:kilford}
L.~Kilford of London, England has recently discovered an example at
prime level $503$ in which ``multiplicity one'' fails. One
verification of his example uses the above proposition. Let~$E_1$,
$E_2$, and $E_3$ be the three elliptic curves of conductor $503$, and
for each $i=1,2,3$, let $\m_i$ be the maximal ideal of $\T\subset
\End(J_0(503))$ generated by~$2$ and all $T_p-a_p(E_i)$, with~$p$
prime. Each of the Galois representations $E_i[2]$ is irreducible,
and one can check that $\m_1=\m_2=\m_3$. If multiplicity one holds,
then $E_1[2] = E_2[2] = E_3[2]$ inside of $J_0(503)$. However, this
is not the case, as a modular symbols computation in the integral
homology $H_1(X_0(N),\Z)$ reveals that $E_1\intersect E_2 = \{0\}$.
\end{example}
\subsection{A strategy for computing congruences}
Let~$N$ be a positive integer, $k\geq 2$ an integer, and~$\eps$ a
mod~$N$ Dirichlet character. Suppose~$f$ and~$g$ are newforms in
$S_k(N,\eps;\Qbar)$. The following proposition gives rise to an
algorithm for computing most congruences\index{Congruences!between
$q$-expansions}\index{Algorithm for computing!congruences}
\index{Congruences!computed using homology}
between infinite Fourier expansions\index{Fourier coefficients}.
The advantage of the algorithm is that it only involves finite exact
computations and does not rely on the computation of $q$-expansions. A
disadvantage is that congruences between $q$-expansions need not be
reflected by the corresponding modular symbols, so the proposition
need not give all congruences. This is illustrated in
Example~\ref{ex:kilford}.
The author first learned about this strategy from the section entitled
``First strategy: Computing $m$-congruences of period lattices'' in
\cite{cremona-mazur}.
\begin{proposition}\label{prop:degcong}
Suppose~$f$ and~$g$ are newforms in $S_k(N,\eps;\Qbar)$.
Let $I_f$ and $I_g$ be the corresponding annihilators
in the Hecke algebra~$\T$\index{Hecke algebra!and congruences}.
Let $\Lambda = \sS_k(N,\eps;\O)$, and set
$\Lambda_f=\Lambda[I_f]$
and $\Lambda_g=\Lambda[I_g]$.
If $p\mid \#\left(\frac{\Lambda}{\Lambda_f + \Lambda_g}\right)_{\tor}$
then there is a prime~$\wp$ of residue characteristic~$p$ such
that $f\con g \pmod{\wp}$.
\end{proposition}
\begin{proof}
Consider the exact sequence
$$0 \ra \Lambda_f \oplus \Lambda_g \ra \Lambda \ra
\Lambda/(\Lambda_f+\Lambda_g) \ra 0$$
where the first map is $(a,b)\mapsto a-b$.
Upon tensoring this sequence with~$\F_p$ we obtain:
$$Z
\ra (\Lambda_f \tensor\F_p) \oplus (\Lambda_g \tensor\F_p)
\ra \Lambda\tensor\F_p \ra (\Lambda/(\Lambda_f+\Lambda_g))\tensor\F_p\ra 0,$$
where $Z=\Tor^1(\Lambda/(\Lambda_f+\Lambda_g),\F_p)$.
Denote by $\im(\Lambda_f)$ the image of $\Lambda_f\tensor\F_p$
in $\Lambda\tensor\F_p$
and likewise for $\Lambda_g$.
Our assumption that~$p$ divides the torsion part
of $\Lambda/(\Lambda_f+\Lambda_g)$ implies that~$Z$
is nonzero, so $\im(\Lambda_f)$ and $\im(\Lambda_g)$
have nonzero intersection inside the $\F_p$-vector
space $\Lambda\tensor\F_p$.
The Hecke algebra~$\T$ acts on $\im(\Lambda_f)$
through its action on~$f$, that is, through the quotient $\T/I_f$;
similarly,~$\T$ acts on $\im(\Lambda_g)$ through $\T/I_g$.
Thus~$\T$ acts on the nonzero $\T\tensor\F_p$-module
$\im(\Lambda_f)\intersect \im(\Lambda_g)$
through $\T/(I_f+I_g+p)$. This implies that
$I_f+I_g+p$ is not the unit ideal, which is equivalent
to the assertion of the proposition.
\end{proof}
\section{The rational period mapping}
\label{sec:ratperiod}
Consider a triple $(N,k,\eps)$, and let $K=\Q[\eps]$.
Let~$I$ be an ideal in the Hecke algebra~$\T$
\index{Hecke algebra!and rational period mapping} associated to $(N,k,\eps)$.
The rational period mapping associated
to~$I$ is a map from the space $\sM_k(N,\eps;K)$ of
modular symbols to a finite dimensional $K$-vector space.
It is a computable analogue of the classical integration
pairing, and is of great value in extracting the rational parts
of analytic invariants; e.g., of special values of $L$-functions.
In the next section we use it to compute the
image of cuspidal points on $J(N,k,\eps)$.
\begin{definition}\label{defn:theta}
Let $D:=\Hom_K(\sM_k(N,\eps;K),K)[I]$; the
\defn{rational period mapping}\index{Rational period mapping|textit}
is the natural quotient map
$$\Theta_I : \sM_k(N,\eps;K) \ra \frac{\sM_k(N,\eps;K)}
{\bigcap\, \{\ker(\vphi) : \vphi \in D\}}.$$
If $f\in S_k(N,\eps)$ is a newform, set $\Theta_f:=\Theta_{I_f}$
where $I_f$ is the annihilator of~$f$ in the Hecke algebra.
\end{definition}
\begin{algorithm}\label{alg:ratperiod}
\index{Algorithm for computing!rational period mapping}
This algorithm computes $\Theta_I$.
Choose a basis for $W=\sM_k(N,\eps;K)$ and use it
to view~$W$ as a space of column vectors equipped with
a left action of~$\T$.
View $W^*=\Hom_K(\sM_k(N,\eps;K),K)$ as the
space of row vectors of length equal to $\dim \sM_k(N,\eps;K)$;
thus~$W^*$ is dual to~$W$ via the natural pairing between
row and column vectors. The Hecke operators\index{Hecke operators}
act on $W^*$ on the right.
Compute a basis $\vphi_1,\ldots,\vphi_{n}$ for
the $K$-vector space $W^*[I]$.
Then the rational period mapping with respect to
this basis is $\vphi_1\cross \cdots \cross \vphi_n$;
it is given by the matrix whose rows
are $\vphi_1,\ldots,\vphi_n$.
\end{algorithm}
\begin{proof}
The kernels of $\vphi_1\cross \cdots \cross \vphi_n$
and $\Theta_I$ are the same.
\end{proof}
\begin{example}\label{ex:ratperiod1}
Let~$I$ be the annihilator of the newform $f=q-2q^2+\cdots \in M_2(37,1;\Q)$
corresponding to the elliptic curve {\bf 37k2A}.
There is a basis for $W=\sM_2(37,1;\Q)$ such that
$$T_2 = \left(\begin{matrix}
-1& 1 &1&-1& 0\\
1&-1& 1& 0& 0\\
0& 0&-2& 1& 0\\
0& 0& 0& 0& 0\\
0& 0& 0& 1& 3\\
\end{matrix}\right)$$
The characteristic polynomial of $T_2$ is $x^2(x+2)^2(x-3)$.
Thus $W[I]=\ker(T_2+2)$ is spanned by the column
vectors $(1,-1,0,1/2,0)^t$ and
$(0,0,1,-1/2,0)^t$, and $W^*[I]=\ker(T_2^{t}+2)$ is spanned by the row vectors
$(1,0,-1,0,0)$ and $(0,1,-1,0,0)$. The rational period mapping
is $\Theta_I((a,b,c,d,e)^t) = (a-c,b-c)$.
\end{example}
\begin{lemma}\label{lem:ratperiodlemma}
$$\dim \sM_k(N,\eps;K)[I] = \dim \Hom_K(\sM_k(N,\eps;K),K)[I].$$
\end{lemma}
\begin{proof}
Let $W=\sM_k(N,\eps;K)$ and $W^*$ be its dual.
Let $a_1,\ldots,a_n$ be a set of generators for~$I$.
Choose a basis for~$W$ that is compatible with the following filtration:
$$0\subset (\ker(a_1)\intersect\cdots\intersect\ker(a_n))
\subset (\ker(a_1)\intersect\cdots\intersect\ker(a_{n-1}))
\subset\cdots \subset \ker(a_1)\subset W.$$
The rank of a matrix
equals the rank of its transpose, so the dimension of $\ker(a_1)$ is
the same as the dimension of $\ker(a_1^t)$, that is,
$\dim W[(a_1)] = \dim W^*[(a_1)]$.
Since~$\T$ is commutative,~$a_2$ leaves $\ker(a_1)$ invariant;
because of how we chose our basis for~$W$,
the transpose of $a_2|_{\ker(a_1)}$ is $a_2^t|_{\ker(a_1^t)}$.
Thus again, $\dim (\ker(a_2|_{\ker(a_1)}))$ equals
$\dim (\ker(a_2^t|_{\ker(a_1^t)}))$.
Proceeding inductively, we prove the lemma.
\end{proof}
\begin{corollary}
Suppose $\sM_k(N,\eps;K)[I]\subset \sS_k(N,\eps;K)$, and
let $P:\sM_k(N,\eps;K)\ra \Hom_\C(S_k(N,\eps;\C)[I],\C)$
be the classical period map induced by the integration
pairing. Then $\ker(P) = \ker(\Theta_I)$.
\end{corollary}
\begin{proof}
Since $P(\sM_k(N,\eps;\O))$ is known to be a finite-covolume
$\O$-lattice in the complex vector space $\Hom_\C(S_k(N,\eps;\C)[I],\C)$,
the $K$-dimension of $\im(P)$ equals
$2\cdot \dim_\C S_k(N,\eps;\C)[I]$,
which in turn equals
$\dim_K \sM_k(N,\eps;K)[I]$.
Thus by Lemma~\ref{lem:ratperiodlemma} the
images $\im(P)$ and $\im(\Theta_I)$ have the same
dimension, hence $\ker(P)$ and $\ker(\Theta_I)$ also have the
same dimension. It thus suffices to prove the inclusion
$\ker(\Theta_I)\subset\ker(P)$.
Suppose $\Theta_I(x)=0$; then $\vphi(x)=0$ for all
$x\in W^*[I]$, where $W=\sM_k(N,\eps;K)$.
Thus $\vphi(x)=0$ for all $\vphi\in (W\tensor\C)^*[I]$.
Since the integration pairing that defines~$P$ respects
the action of~$\T$, the composition of~$P$ with any linear
functional lies in $(W\tensor\C)^*[I]$. Thus $P(x)=0$,
as required.
\end{proof}
\section{The images of cuspidal points}
\label{sec:torsionsubgroup}
\label{sec:cuspdiff}
\index{Cuspidal points}
Consider a triple $(N,k,\eps)$, and let $K=\Q[\eps]$.
Recall that integration defines a period mapping
$$P : \sM_k(N,\eps;K)\ra \Hom_\C(S_k(N,\eps;\C),\C).$$
A \defn{cuspidal point} of
$$J=J(N,k,\eps):=
\frac{\Hom_\C(S_k(N,\eps;\C),\C)}
{P(\sS_k(N,\eps;\O))}$$
is a point that is in the image under~$P$ of $\sM_k(N,\eps;\O)$.
It is of great interest to compute the structure of
the cuspidal subgroup of~$J$ and of the quotients of~$J$.
For example, when $k=2$ and $\eps=1$, the torus~$J$
can be identified with $J_0(N)(\C)$.
In this case,
Manin\index{Manin} proved
(see~\cite{manin:parabolic}) that the cuspidal
point $\{0,\infty\}$ is a torsion point in $J_0(N)(\Q)$, so
its order gives a lower bound on $J_0(N)(\Q)_{\tor}$.
\begin{algorithm}[Cuspidal subgroup]
\index{Algorithm for computing!cuspidal subgroup}
Let~$I$ be an ideal in the Hecke algebra~$\T$.\index{Hecke algebra!and cuspidal subgroup}
This algorithm computes the cuspidal subgroup
of the quotient $A_I$ of~$J$.
Using Algorithm~\ref{alg:MkNO}
compute $\sM_k(N,\eps;\O)$ and $\sS_k(N,\eps;\O)$.
Using Algorithm~\ref{alg:ratperiod},
compute the rational period mapping~$\Theta_I$.
Then the cuspidal subgroup is the
subgroup of $\Theta_I(\sS_k(N,\eps;\O))$ generated
by the elements $\Theta_I(x)$ for $x\in \sM_k(N,\eps;\O)$.
In particular, the point of $A_I(\C)$ corresponding
to $X^iY^{k-2-i}\{\alp,\beta\}$ is
the image of $\Theta_I(X^iY^{k-2-i}\{\alp,\beta\})$ in the quotient
of $\Theta_I(\sM_k(N,\eps;\O))$ by $\Theta_I(\sS_k(N,\eps;\O))$.
\end{algorithm}
\begin{example}
This example continues Example~\ref{ex:ratperiod1}.
The basis chosen is also a basis for $\sM_2(37,1;\Z)$,
so by computing the boundary map, or the integer
kernel of $T_2(T_2+2)$, we find that $\sS_2(37,1;\Z)$
is spanned by $(1,0,0,0,0)$, $(0,1,0,0,0)$,
$(0,0,1,0,0)$, and $(0,0,0,1,0)$.
Thus $\Theta_I(\sS_2(37,1;\Z))$ is generated by
$(1,0)$ and $(0,1)$.
The modular symbols $\{0,\infty\}$ is represented
by $(0,0,0,0,-1)$, so the image of the cusp $(0)-(\infty)\in J_0(37)$
is~$0$ in {\bf 37k2A}.
The rational period mapping associated to {\bf 37k2B} (with respect
to some basis) is
$$\Theta_I((a,b,c,d,e)^t) = (a-c-2d+\frac{2}{3}e,\,\,
b+c+2d-\frac{2}{3}e).$$
Thus $\Theta_I(\sS_2(37,1;\Z))$ is generated by
$(1,0)$ and $(0,1)$.
The image of $\{0,\infty\}$ is
is $\frac{2}{3}(1,-1)$, so the image of
$(0)-(\infty)$ in {\bf 37k2B} has order~$3$.
\end{example}
\subsection{Rational torsion}
Let~$f$ be a newform of weight $2$, and suppose
$\eps=1$. Manin\index{Manin} proved that $(0)-(\infty)$ defines an element
of $J_0(N)(\Q)_{\tor}$. Thus the order of the
image of $(0)-(\infty)$ provides a lower bounds on
$\# A_f(\Q)_{\tor}$.
In general, many other points in the cuspidal subgroup can be rational.
Determining which would give a better lower bound on the rational
subgroup; the author has not yet carried out such computations
(see, however,~\cite{stevens:thesis}).
\index{Torsion subgroup!lower bounds on|textit}
\subsection{Upper bound on torsion: Counting points mod~$p$}
\index{Torsion subgroup!upper bounds on|textit}
Let~$f$ be a newform of weight $2$, and suppose
$\eps=1$.
The Hecke algebra~$\T$\index{Hecke algebra!bounds torsion} acts through
a quotient $\overline{\T}$ on the subspace of $S_2(\Gamma_0(N))$ spanned
by the Galois conjugates of~$f$. Let $\chi_p(X)$ be the characteristic
polynomial of the image of $T_p$ in $\overline{\T}$.
Suppose $p\nmid N$ and let $N_p=\# A_f(\F_p)$ be the number of points
on the mod~$p$ reduction of the abelian variety $A_f$.
\begin{proposition}
For each prime~$p$ not dividing~$N$,
$$N_p = \chi_p(p+1).$$
\end{proposition}
\begin{proof}
This is probably well-known, but we give a
proof (which was suggested to the author by Matt Baker).
It follows from the Eichler-Shimura\index{Eichler-Shimura relation}
theorem that the
following relation holds in the endomorphism ring of $A_f/{\F_p}$:
$$T_p = \Frob + \Ver = \Frob + p/\Frob.$$
Let $\ell\neq p$ be a prime.
If the characteristic polynomial of $\Frob$ on
an $\ell$-adic Tate module of $A_f/\F_p$ is $F(t)$, and
the characteristic polynomial of $T_p$
on differentials $H^0(A_f/\F_p,\Omega)$
is $f(t)$, then we have $f(t)=x^{-d}F(x)$,
where $t=x+(p/x)$ and $d=\dim A_f$. In
other words, the relation above gives an easy conversion
between~$f$ and~$F$.
Since it's a general fact that $\#A_f(\Fp)=F(1)$, we have
$\#A_f(\Fp)=f(p+1).$
\end{proof}
The following theorem is proved using formal
groups.
\begin{theorem}
Let $A$ be an abelian variety over~$\Q$, with good reduction outside~$N$.
Suppose $p\nmid N$. Then the kernel of the reduction map
$A(\Q)_{\tor}\ra A(\F_p)$
is killed by~$p$. If $p>2$ then
the kernel is trivial.
\end{theorem}
By taking gcd's we obtain an upper bound on $\# A(\Q)_{\tor}$.
This upper bound is not in general sharp; in fact, it is unchanged
if~$A$ is replaced by any isogenous abelian variety.
For example, $X_0(11)$ and $X_1(11)$ are isogenous, but have different
torsion subgroups.
\section{The modular degree}
\label{sec:moddeg}
\index{Modular degree}
Let~$f$ be a newform of level~$N$, weight
$k\geq 2$ and character~$\eps$ such that $\eps^2=1$.
In this section we define and give an algorithm to
compute the modular degree of the torus $A_f$ attached to~$f$.
\begin{definition}\label{defn:modulardegree}
The \defn{modular map}\index{Modular map} is the
map $\theta_f:\Adual_f \ra A_f$ that is
induced by the bottom row of
Diagram~\ref{dgm:uniformization} on page~\pageref{dgm:uniformization}.
The \defn{modular degree}\index{Modular degree}~$m_f$
of~$f$ (or of~$A_f$) is the degree of this map.
If~$f$ has weight two, then $\theta_f$ is a polarization so
by \cite[Thm.~13.3]{milne:abvars} its degree is a perfect square;
in this case we {\em instead} define the modular degree $m_f$ to
be the positive square root of the degree of $\theta_f$.
\end{definition}
\begin{remark}
When $E/\Q$ be a modular elliptic curve of conductor~$N$
that is an optimal quotient\index{Optimal quotient} of $J_0(N)$,
then $m_f$ is the usual modular degree, which is
the least degree of a map $X_0(N)\ra E$.
\end{remark}
\begin{remark}
When $k\neq 2$, the degree of~$\theta_f$ need not be a perfect square.
For example, there is a one-dimensional quotient $A_f$
associated to the unique rational newform
$$f = q + 2q^2 - 8q^3 + 4q^4 + 5q^5 - 16q^6 - 4q^7+ \cdots\in S_4(10)$$
such that the kernel of $\theta_f$ is isomorphic to
$\Z/10\Z$.
Next, for a newform~$f$
let $\theta_f'$ be the part of $\#\ker(\theta_f)$ that is
coprime to the level. There is a newform in $f\in S_4(\Gamma_0(77))$
such that $\theta_f'$ is not a perfect square at~$2$. For identification
purposes, we remark that the field generated by the Fourier coefficients
of~$f$ has discriminant $2^3\cdot 3^3\cdot 2417$.
\end{remark}
\begin{algorithm}
\index{Algorithm for computing!modular kernel}
Let $I_f$ be the annihilator of~$f$ in the Hecke algebra\index{Hecke algebra}.
The modular kernel $\ker(\theta_f)$ is isomorphic to
the cokernel of the natural map
$\sS[I_f] \ra \Phi_f(\sS)$ of Diagram~\ref{dgm:uniformization}
on page~\pageref{dgm:uniformization}.
This cokernel can be computed by replacing~$\Phi_f$
by the rational period map~$\Theta_{I_f}$.
\end{algorithm}
\begin{proof}
For concreteness, we give the proof only in the case of weight-two and
trivial character. The proof in the general case is similar.
Let $S = S_2(\Gamma_0(N),\C)$ be the complex vector space of
weight-two modular forms of level~$N$, and set $H = H_1(X_0(N),Z)$.
The integration pairing $S\times H \rightarrow \C$
induces a natural map
$$\Phi_f:H\rightarrow \Hom(S[I_f],\C).$$
Using the classical
Abel-Jacobi theorem, we deduce the following commutative diagram,
which has exact columns, but whose rows are not exact.
$$\[email protected]=.5cm{
0\ar[d] & 0\ar[d] & 0\ar[d] \\
H[I_f]\ar[d]\ar[r] & H\ar[d]\ar[r]&\Phi_f(H)\ar[d] \\
\Hom(S,\C)[I_f]\ar[d]\ar[r] &\Hom(S,\C)\ar[d]\ar[r] &\Hom(S[I_f],\C)\ar[d]\\
{A_f^{\vee}(\C)}\ar[d]\ar[r]
\[email protected]/_3.5pc/[rr]& J_0(N)(\C)\ar[d]\ar[r]& A_f(\C)\ar[d]\\
0 & 0 & 0 \\
}$$
By the snake lemma\index{Snake lemma},
the kernel of $A_f^{\vee}(\C)\rightarrow A_f(\C)$ is isomorphic to the
cokernel of the map $H[I_f] \rightarrow \Phi_f(H)$,
which proves the proposition.
\end{proof}
\begin{remark}\label{rem:moddegmestre}
Suppose $E$ is an optimal quotient of $J_0(p)$, with~$p$ prime.
The surjectivity result in \cite{mestre-oesterle:crelle} implies that
it is possible to efficiently compute the modular degree using only
the method of graphs.
For more details, see Chapter~\ref{chap:compgroups}.
\end{remark}
\section{The rational part of $L(A_f,j)$}
\label{sec:ratpartformula}
\label{sec:rationalvals}
\index{Rational part of $L(A,j)$}
\index{Special value $L(A,j)$!rational part of}
Let $k\geq 2$ be an integer, and let $\eps:(\Z/N\Z)^*\ra\C^*$ be a
Dirichlet character such that $\eps^2=1$. This assumption on $\eps$
is made only for simplicity; there is no fundamental obstruction to
considering arbitrary characters. For the remainder of this section
we fix a newform $f\in S_k(N,\eps)$. We will compute certain rational
numbers associated to~$f$.
The author was motivated to prove the results of this section after
seeing Agashe's\index{Agashe} results in the case $k=2$ and $\eps=1$;
see \cite[Ch.~4]{agashe:phd}.
\subsection{$L$-functions}
\begin{definition}\label{defn:lseries}
The $L$-series\index{$L$-series|textit} associated to~$f$ is
the complex-analytic function
$$L(f,s) \defeq \sum_{n=1}^{\infty} a_n n^{-s}.$$
\end{definition}
Hecke\index{Hecke} proved that $L(f,s)$ has an analytic continuation
to the whole complex plane. In particular, it makes sense to consider
the values $L(f,j)$ where $j\in\{1,2,\ldots,k-1\}$ is an integer in
the ``critical strip.'' The general consesus is that these special
values have deep arithmetic significance, in the sense that the
quotients $L(f,j)/\omega_{f,j}$ should be algebraic numbers, where
$\omega_{f,j}$ is an appropriate period of~$f$, and that these algebraic
numbers should encode deep arithmetic properties of the motive
attached to~$f$.
For simplicity, especially when doing explicit computations, it is
desirable to work exclusively with ratios that are rational numbers
instead of algebraic numbers. For this purpose, we consider instead
the complex torus~$A_f$ attached to~$f$, and introduce
$$L(A_f,s) := \prod_{i=1}^d L(f_i,s),$$
where $f_1,\ldots, f_d$ are the distinct Galois-conjugates of~$f$.
As we will see, $L(A_f,j)/\Omega_j\in\Q$, where $\Omega_j$ will be
defined below.
Though the notation $L(A_f,s)$ suggests that there might be a way to
attach an $L$-function to a general complex torus, this is definitely
{\em not} what we have in mind. For our present purposes, the notation
$L(A_f,s)$ is nothing more than a convenient shorthand for the product
of the $L$-functions attached to the Galois conjugates of~$f$.
However, in the case when $k=2$ and $\eps=1$, the $L$-function
$L(A_f,s)$ is known to be the canonical $L$-series\index{$L$-series}
associated to the abelian variety $A_f/\Q$; see, e.g., the discussion
in
\cite[Sec.~7]{darmon-merel}.
\subsection{Winding elements}
Generalizing Mazur\index{Mazur} and Merel's\index{Merel} terminology when $k=2$, we define
winding elements as follows.
\begin{definition}[Winding element]\label{defn:windingelement}
For $1\leq i \leq k-1$, the
$i$th \defn{winding element}\index{Winding element} is
$$\e_i := X^{i-1}Y^{k-2-(i-1)}\{0,\oo\}\in\sM_k(N,\eps;\Z).$$
\end{definition}
For example, when $k=2$ there is one winding element
$\e = \e_1 = \{0,\infty\}$.
See \cite[\S2.2]{mazur-sd} for a topologically motivated discussion
of the terminology ``winding element.''
\subsection{Real and minus volumes}
\label{sec:realvolume}
We briefly review the association of a complex torus to a Galois-conjugacy
class of newforms.
Consider the space $S_k(N,\eps;\Z)$ of cusp forms in
$S_k(N,\eps)$ whose $q$-expansion at infinity has
Fourier coefficients which lie in~$\Z$.
Let $V$ be the $\C$-vector space spanned by the Galois
conjugates $f_1,\ldots, f_d$ of~$f$, and choose a $\Z$-basis
$g_1,\ldots,g_d$ for the intersection $V\intersect S_k(N,\eps;\Z)$.
Then integration via the pairing of Theorem~\ref{thm:perfectpairing}
against $g_1,\ldots, g_d$ defines a map
$\sS_k(N,\eps;\Z)\ra \C^d$ whose
cokernel is $A_f(\C)$.
Viewing $A_f(\C)$ in this way, the standard measure on $\C^d$
defines a measure on $A_f(\C)$.
Because $\eps^2=1$, the complex torus $A(\C)$ is equipped
with an action of complex conjugation.
There are two distinguished additive subgroups of $A(\C)$: the subgroup
$A(\R)$ of elements fixed under complex conjugation, and the
subgroup $A(\C)^{-}$ of elements sent to their additive inverse
by complex conjugation. When~$j$ is odd, let $\Omega_j$
be the measure of the subgroup fixed under conjugation, and when~$j$
is even, let $\Omega_j$ be the measure of the subgroup
sent to its inverse under conjugation, times $i^d$, where $d$ is
the dimension of~$A$.
When~$j$ is odd, we call $\Omega_j$ the \defn{real volume}; otherwise,
we call $\Omega_j$ the \defn{minus volume}
(see Definition~\ref{defn:realminusvolume}).
\index{Real volume|textit}
\index{Minus volume|textit}
\subsection{The theorem}
We are now prepared to state a theorem that gives a computable
expression for the ratio $|L(A_f,j)/\Omega_j|$. This theorem grew out
of joint work with Agashe.\index{Agashe} It generalizes
Cremona's\index{Cremona} method for
computation $L(E,1)/\Omega_E$ when~$E$ is an elliptic curve
(see~\cite[\S2.8]{cremona:algs}).
As an immediate corollary of the formula, we see that
$|L(A_f,j)/\Omega_j|$ is a rational number. This was already known
when $f\in S_2(\Gamma_0(N))$ (see \cite[\S2]{gross:central}). The
author remains ignorant as to whether or not the general corollary was
known before, or even if the real numbers $\Omega_j$, exactly as
defined here, had been previously considered. However, rationality of
certain related period ratios has been known for some time, due to
work of Manin\index{Manin}, Shimura\index{Shimura},
and Hatada. For a clear historical summary of
these rationality results see Li's MathSciNet review of
\cite{hatada:rationality}. See also~\cite{mazur:arithmetic_values, mazur-sd}.
We take the absolute value of $L(A_f,j)/\Omega_j$ for simplicity only
because at present we do not wish to worry about powers of the $4$th
root of unity~$i$.
\begin{theorem}\label{ratpart}
\index{Algorithm for computing!rational part of $L(A,j)$}
Let $f\in S_k(N,\eps)$ be a newform, where $k\geq 2$ and $\eps^2=1$,
and let $j\in\{1,2,\ldots,k-1\}$ be an integer in the critical strip.
Let~$\sigma=(-1)^{j-1}$, and
let $\Theta_f$ be the rational period mapping associated to~$f$
(see Definition~\ref{defn:theta}).
Then
$$\left|\frac{L(A_f,j)}{\Omega_j}\right|
= [\Theta_f(\sS_k(N,\eps;\Z)^\sigma) : \Theta_f(\T{}\e_j)],$$
where $\sS_k(N,\eps;\Z)^\sigma$ denotes the submodule of
$\sS_k(N,\eps;\Z)$ on which the $*$-involution acts as~$\sigma$,
and $\Omega_j$ is the real or minus volume of~$A_f$,
as in Section~\ref{sec:realvolume}.
The right hand expression in the formula is a lattice index, whose
definition is given below.
\end{theorem}
\begin{remark}
In the context of the BSD conjecture\index{BSD conjecture!and $\Omega_A$},
$\Omega_{A_f} = \Omega_1 \cdot c_\infty$,
where $c_\infty$ is the number of connected components of
$A_f(\R)$.
\end{remark}
The theorem involves lattice indexes, which we define as follows.
\begin{definition}\index{Lattice|textit}
Let~$V$ be a finite-dimensional
vector space over~$\R$. A \defn{lattice} $L\subset V$
is a free abelian group of rank equal to the dimension
of~$V$ such that $\R L=V$.
If $L, M\subset V$ are lattices, the \defn{lattice
index}\label{pg:latticeindex}\index{Lattice index|textit}
\index{Index of lattices|textit}
$[L:M]\in\R$ is the absolute value of the
determinant of an automorphism of~$V$
taking~$L$ isomorphically onto~$M$.
For convenience we set $[L:M]=0$ for any lattice~$L$ and
additive abelian group~$M$ contained in~$V$
and of rank strictly smaller than $\dim V$.
\end{definition}
The following fact allows us to compute the lattice the index without
using complex numbers.
\begin{lemma}\label{latticeker}
Suppose $\tau_i : V\ra W_i$, $i=1,2$, are surjective linear maps such that
$\ker(\tau_1)=\ker(\tau_2)$. Let~$L$ and~$M$ be lattices in~$V$
such that $\tau_i(L)$ and $\tau_i(M)$ are both lattices for $i=1,2$.
Then
$$[\tau_1(L):\tau_1(M)] = [\tau_2(L):\tau_2(M)].$$
\end{lemma}
\begin{proof}
Surjectivity and equality of kernels insures that there is a unique
isomorphism $\iota:W_1\ra W_2$ such that $\iota\tau_1 = \tau_2$.
Let~$\sigma$ be an automorphism
of $W_1$ such that $\sigma(\tau_1(L))=\tau_1(M)$.
Then
$$\iota\sigma\iota^{-1}(\tau_2(L)) = \iota\sigma\tau_1(L)=\iota\tau_1(M)=\tau_2(M).$$
Since conjugation does not change the determinant,
$$[\tau_2(L):\tau_2(M)]=|\det(\iota\sigma\iota^{-1})|
=|\det(\sigma)| = [\tau_1(L):\tau_1(M)].$$
\end{proof}
\vspace{1in}
\begin{proof}[Proof of Theorem~\ref{ratpart}]
Let $\Phi=\Phi_f$ be the period map\index{Period mapping}
$\sM_k(N,\eps;\Z) \ra \C^d$
defined by fixing a basis $f_1,f_2,\ldots,f_d$ of the conjugates
of the {\em newform}~$f$;
thus $$\Phi(x) = (\langle f_1, x\rangle,
\langle f_2, x\rangle,\ldots
\langle f_d, x\rangle)\in \C^d.$$
We view $\C^d$
as an algebra with unit element $\mathbf{1}=(1,\ldots,1)$ equipped
with an action of the Hecke operators\index{Hecke operators}.
The operator $T_p$ acts as $(a_p^{(1)},\ldots,a_p^{(d)})$,
where the components $a_p^{(j)}$ are the Galois conjugates of $a_p$.
Let $\Z^d\subset\R^d\subset\C^d$ be the standard submodules.
For brevity, set $\sS=\sS_k(N,\eps;\Z)$.
Let $\mu(\Phi(\sS^\sigma))$ be the measure of a fundamental domain
for the lattice $\Phi(\sS^\sigma)$; equivalently,
$\mu(\Phi(\sS^\sigma))$ is the absolute value of the determinant
of a basis for $\Phi(\sS^\sigma)$.
Observe that
$\mu(\Phi(\sS^\sigma))=[\Z^d:\Phi(\sS^\sigma)]$
and
$|L(A_f,j)|=[\Z^d:\Phi(\e_j)\Z^d].$
Let $W\subset\C^d$ be the $\Z$-module spanned by the ``columns'' of a
basis for $S_k(N,\eps;\Z)[I_f]$. More precisely, if $g_1,\ldots, g_d$
is a basis, then the $n$th column is the vector
$(a_n(g_1),\ldots, a_n(g_d))$, where $a_n(g_i)$ is the
coefficient of $q^n$ in the $q$-expansion of $g_i$ at infinity.
Because~$\Omega_j$ is computed with
respect to a basis for $S_k(N,\eps;\Z)[I_f]$,
$$\mu(\Phi(\sS^\sigma))=[W:\T\mathbf{1}]\cdot \Omega_j.$$
Observe that $S_k(N,\eps;\Z)$ is saturated, in the sense that there
are no nontrivial linear relations between the $g_i$ when reduced
modulo any prime~$p$. To see this, note that if $\sum a_i g_i \con
0\pmod{p}$, then $\frac{1}{p}\sum a_i g_i\in S_k(N,\eps;\Z)$ which,
if the~$a_i$ are not all~$0$, is contrary
to our assumption that $g_1,\ldots, g_d$ are a $\Z$-basis. Because
``row rank = column rank'', the same must be true for the ``columns''
defined in the previous paragraph, so $[\Z^d:W]=1$.
It follows that $[\Z^d:\T\mathbf{1}]=[W:\T\mathbf{1}].$
The following calculation combines together the above
observations using properties of the lattice index:
\begin{eqnarray*}
[\Phi(\sS^\sigma):\Phi(\T{}\e_j)]
&=& [\Phi(\sS^\sigma):\Z^d]
\cdot[\Z^d:\Phi(\T{}\e_j)]\\
&=& \frac{1}{[\Z^d:\Phi(\sS^\sigma)]} \cdot [\Z^d:\Phi(\T\e_j)]\\
&=&\frac{1}{\mu(\Phi(\sS^\sigma))}\cdot [\Z^d:\Phi(\e_j)\Z^d]\cdot [\Phi(\e_j)\Z^d:\Phi(\T\e_j)]\\
&=&\frac{|L(A_f,j)|}{\mu(\Phi(\sS^\sigma))}\cdot[\Phi(\e_j)\Z^d:\Phi(\T\e_j)]\\
&=&\frac{|L(A_f,j)|}{\mu(\Phi(\sS^\sigma))}\cdot[\Phi(\e_j)\Z^d:\Phi(\e_j)\T{}\mathbf{1}]\\
&=&\frac{|L(A_f,j)|}{|\Omega_j|\cdot [W:\T\mathbf{1}]}\cdot[\Z^d:\T{}\mathbf{1}]\\
&=&\frac{|L(A_f,j)|}{|\Omega_j|}.\\
\end{eqnarray*}
Theorem~\ref{ratpart} now follows by using Lemma~\ref{latticeker},
to replace~$\Phi$ by~$\Theta_f$.
\end{proof}
\subsection{Bounding the denominator of the ratio}
In this section we bound the denominators of the ratios appearing
in the previous section. We begin with
the following lemma, which follows easily from the
alternative description of the
boundary map given in Proposition~\ref{prop:boundary}.
\begin{lemma}
For $j=2,\ldots, k-2$ the winding element $\e_j$ lies in
$\sS_k(N,\eps;\Z)$.
\end{lemma}
\begin{proof}
Recall that $\e_j = P(X,Y)\{0,\infty\}$ where
$P(X,Y) = X^{j-1}Y^{k-2-(j-1)}$.
Since $2\leq j\leq k-2$, it follows that
$P(1,0)=P(0,1)=0$, so Propositison~\ref{prop:boundary} implies
that $\e_j$ maps to~$0$ under the boundary map.
\end{proof}
\begin{proposition}
For $j=2,\ldots, k-2$,
$$\frac{L(A_f,j)}{\Omega_j} \in \Z.$$
\end{proposition}
\begin{proof}
This follows from Theorem~\ref{ratpart} because
$\Theta_f(\T \e_j) \subset \Theta_f(\sS_k(N,\eps;\Z)^{\sigma})$,
so the lattice index is an integer.
\end{proof}
For the rest of this section, we assume for simplicity that $\eps=1$.
\begin{lemma}\label{lemma:eisact}
For $j=1$ and $j=k-1$, we have for each $p\nmid N$ that
$$(T_p - (1+p^{k-1})) \e_j \in \sS_k(N,\eps;\Z).$$
\end{lemma}
\begin{proof}
This is a standard calculation; see, e.g., \cite[\S2.8]{cremona:algs}
for the case when $k=2$.
\end{proof}
\begin{proposition}\label{cor:denominator}
Let $j\in\{1,\ldots,k-1\}$, and
let~$n$ be the order of the image in $A_f(\C)$ of the modular symbol
$\e_j$, so $n=1$ if $j\not\in \{1, k-1\}$. Then
$$ \frac{L(A_f,j)}{\Omega_j}\in \frac{1}{n}\Z.$$
\end{proposition}
\begin{proof}
Let~$x$ denote the image of $\e_j\in A_f(\C)$,
and set $I=\Ann(x)\subset\T$. Though we write $A_f(\C)$ here and
below, we will always work within the subgroup of $A_f(\C)$ generated
by the image of $\sM_k(N,\eps;\Z)$ under the period map.
First we check that the Hecke operators all act as
scalars on~$x$. Since~$f$ is a {\em newform}, the Hecke
operators\index{Hecke operators} $T_p$, for $p\mid N$, act as~$0$ or
$\pm p^{k/2-1}$ on~$f$, and hence in the same way on $A_f(\C)$ (see,
e.g., the end of section 6 of \cite{diamond-im}). If $p\nmid N$,
Lemma~\ref{lemma:eisact} shows that $T_p(x) = (1+p^{k-1})x$.
Let $C=\Z{}x$ denote the cyclic subgroup of $A_f(\C)$ generated
by~$x$, so~$n$ is the order of~$C$. Since the Hecke operators
act as scalars on~$C$, we are pleased to find that there is
an injection $\T/I\hookrightarrow C$ which sends
$T_p$ to $T_p(x)$.
Setting $\sS=\sS_k(N,\eps;\Z)$ and applying Theorem~\ref{ratpart}
we find that
\begin{eqnarray*}
\pm \frac{L(A_f,j)}{\Omega_j} &=& [\Theta_f(\sS^+):\Theta_f(\T{}e)]\\
&=& [\Theta_f(\sS^+):\Theta_f(I\e)]\cdot [\Theta_f(I\e):\Theta_f(\T{}\e)]\\
&=& [\Theta_f(\sS^+):I\Theta_f(\e)]\cdot [I\Theta_f(\e):\T{}\Theta_f(\e)]\\
&=& \frac{[\Theta_f(\sS^+):I\Theta_f(\e)]}{[\T{}\Theta_f(\e):I\Theta_f(\e)]}.
\end{eqnarray*}
To conclude that
$$\frac{[\Theta_f(\sS^+):I\Theta_f(\e)]}{[\T{}\Theta_f(\e):I\Theta_f(\e)]} \in \frac{1}{n}\Z$$
we make two observations.
By the construction of $A_f(\C)$, the ideal~$I$ consists of those
elements of~$\T$ that send $\Theta_f(\e)$ into $\Theta_f(\sS^+)$, so
$[\Theta_f(\sS^+):I\Theta_f(\e)]\in\Z$. Second, there is a surjective map
$$\T/I \ra \frac{\T\Theta_f(\e)}{I\Theta_f(\e)}$$
sending $t$ to $t \Theta_f(\e)$, so $[\T{}\Theta_f(\e):I\Theta_f(\e)]$
divides $n=\#C=\#(\T/I)$.
\end{proof}
\begin{remark}[Historical notes]
In the special case when $k=2$, the modular symbol $\e_1$ corresponds
to $(0)-(\infty)\in J_0(N)$. In this situation, Manin\index{Manin!comment on BSD} proves at the
bottom of page~28 of \cite{manin:parabolic} that $(0)-(\infty)\in
J_0(N)(\Q)$, and asserts in the footnote to
\cite[Cor.~3.6]{manin:parabolic} that $(0)-(\infty)$ has finite order.
Based on observations such as a special case of the above proposition,
he declares: ``These explicit formulas have the structure predicted by
the Birch-Swinnerton-Dyer conjectures.''
\index{BSD conjecture!Manin's remarks on}
The main result of this section was inspired by a weaker result of
Agashe,\index{Agashe}
which can be found in Chapter~4 of~\cite{agashe:phd}. Agashe
considers only the case $k=2$ and replaces~$n$ by the order of the
subgroup of $J_0(N)(\Qbar)$ generated by {\em all} cusps.
\end{remark}
\comment{
\begin{proposition}\label{cor:denominator}
Let $n$ be the order of the image in $A_f(\Q)$ of the point
$(0)-(\infty)\in J_0(N)(\Q)$. Then
$$ \frac{L(A_f,1)}{\Omega_1}\in \frac{1}{n}\Z.$$
\end{proposition}
Manin\index{Manin} proved at the bottom of page~28 of \cite{manin:parabolic}
that $(0)-(\infty)\in J_0(N)(\Q)$, and asserts in the footnote
to \cite[Cor.~3.6]{manin:parabolic} that $(0)-(\infty)$
has finite order.
\begin{proof}
Let~$x$ denote the image of $(0)-(\infty)\in A_f(\Q)$
and set $I=\Ann(x)\subset\T$. Since~$f$ is a {\em newform},
the Hecke operators\index{Hecke operators}
$T_p$, for $p\mid N$, act as~$0$ or $\pm 1$ on
$A_f(\Q)$ (see, e.g., the end of section 6 of \cite{diamond-im}).
If $p\nmid N$ a standard calculation (see, e.g., \cite[\S2.8]{cremona:algs})
combined with the Abel-Jacobi\index{Abel-Jacobi}
theorem shows that $T_p(x) = (p+1)x$.
In terms of homology, this is the assertion that
$(T_p-(p+1))\{0,\infty\} \in H_1(X_0(N),\Z)$ for $p\nmid N$.
Let $C=\Z{}x$ denote the
cyclic subgroup of $A_f(\Q)$ generated by~$x$,
so~$n$ is the order of~$C$.
There is an injection
$ \T/I\hookrightarrow C$
sending $T_p$ to $T_p(x)$.
By Theorem~\ref{ratpart} we have
\begin{eqnarray*}
\pm L(A_f,1)/\Omega_f^0 &=& [\Theta(\sS^+):\Theta(\T{}e)]\\
&=& [\Theta(\sS^+):\Theta(I\e)]\cdot [\Theta(I\e):\Theta(\T{}\e)]\\
&=& [\Theta(\sS^+):I\Theta(\e)]\cdot [I\Theta(\e):\T{}\Theta(\e)]\\
&=& \frac{[\Theta(\sS^+):I\Theta(\e)]}{[\T{}\Theta(\e):I\Theta(\e)]} \in \frac{1}{n}\Z.
\end{eqnarray*}
The final inclusion follows from two observations.
By Abel-Jacobi,~$I$ consists of those
elements of~$\T$ that send $\Theta(\e)$ into $\Theta(\sS^+)$, so
$[\Theta(\sS^+):I\Theta(\e)]\in\Z$. Second, there is a surjective map
$$\T/I \ra \frac{\T\Theta(\e)}{I\Theta(\e)}$$
sending $t$ to $t \Theta(\e)$, so $[\T{}\Theta(\e):I\Theta(\e)]$
divides $n=\#C=\#(\T/I)$.
\end{proof}
}
\section{The Manin constant}\label{sec:maninconstant}
\index{Manin constant}
In this section $k=2$ and $\eps=1$; we
sometimes omit~$k$ and~$\eps$ from the notation.
The assumption that $k=2$ will be essential, because we
do not know how to define a Manin constant in other weights,
let alone bound it.
Consider the optimal quotient~$A$ of~$J_0(N)$ corresponding
to a {\em newform}~$f$ on $\Gamma_0(N)$ of weight~$2$.
Let~$I_A$ be the kernel of the natural map from the Hecke algebra
\index{Hecke algebra} to $\End(A)$.
The \defn{Manin constant\label{defn:maninconstant}}~$c_A$ of~$A$ is
the lattice
index
$$c_A := [S_2(\Gamma_0(N);\Z)[I_A]:H^0(\cA,\Omega_{\cA/\Z})]$$
taken inside of $S_2(\Gamma_0(N);\Q)$.
Though, a priori, $c_A$ is a rational number, the work of
\cite{katzmazur} implies that $c_A\in\Z$
(see, e.g., \cite{agashe-stein:manin}).
Generalizing a theorem of Mazur\index{Mazur}, we prove that~$c_A$
is a unit in $\Z[\frac{1}{2m}]$, where~$m$ is the largest
square dividing~$N$. Essentially no new ideas beyond what Mazur used
are involved.
We then conjecture that $c_A=1$,
and give supporting numerical evidence.
For related results involving modular ``building blocks'' for
$J_1(N)$, we refer the reader to~\cite[\S4]{ganz-lario:manin}.
\subsection{The primes that might divide~$c_A$}
In the special case $\dim A=1$, the Manin constant\index{Manin constant}
is the classical Manin
constant of~$A$, and in~\cite{mazur:rational} Mazur\index{Mazur} proved
that~$c_A$ is a unit in $\Z[\frac{1}{2m}]$.
We generalize his proof to obtain the analogous result in
dimension greater than~$1$.
\begin{theorem}
Let $A$ be the new optimal quotient of~$J_0(N)$ corresponding
to a newform~$f$. Then the Manin\index{Manin constant} constant~$c_A$ is a unit
in $\Z[\frac{1}{2m}]$, where~$m$ is the largest square
dividing~$N$.
\end{theorem}
\begin{proof}
The reader is strongly recommended to keep the proof of
Proposition~3.1 in \cite{mazur:rational} at hand while
reading the following argument.
Let~$\pi$ denote the map $J_0(N)\ra A$;
let~$\cA$ denote the N\'eron model\index{N\'eron model}
of~$A$ over~$R:=\Z[\frac{1}{2m}]$, and~$\cJ$ the
N\'eron model of $J_0(N)$ over~$R$.
Let~$\cX$ be the minimal proper regular model for $X_0(N)$ over~$R$.
As in Mazur's\index{Mazur} proof in~\cite{mazur:rational}, consider the diagram
\begin{equation}\label{eqn:qexp}
H^0(\cA,\Omega_{\cA}) \xrightarrow{\pi^*} H^0(\cJ,\Omega_{\cJ})
\isom H^0(\cX,\Omega_\cX^{\text{reg}})
\xrightarrow{\text{ $q$-exp }} R[[q]].
\end{equation}
(Note that ``$\Omega_\cX^{\text{reg}}$'' is not defined to be the usual
sheaf of differentials; see, e.g., the discussion
in \cite[pg.~67]{mazur:eisenstein}.)
The map~$\pi^*$ must be an inclusion, by \cite[Cor.~1.1]{mazur:rational}.
To show that the Manin constant is a unit in~$R$, it
suffices to check that the image of $H^0(\cA,\Omega_{\cA})$
in $R[[q]]$ is {\em saturated}\index{Saturated}, in the sense that the
cokernel is torsion free; indeed, the image of
$S_2(\Gamma_0(N);R)[I]$ is saturated and
$S_2(\Gamma_0(N);R)[I]\tensor\Q =
\text{$q$-exp}(\pi^*(H^0(\cA,\Omega_{\cA})))\tensor\Q$.
For the image of $H^0(\cA,\Omega_{\cA})$ in $R[[q]]$ to be
saturated means that the quotient~$D$
is torsion free. Let~$\ell$ be a prime not dividing~$2m$;
tensoring
$$0\ra H^0(\cA,\Omega_{\cA})\xrightarrow{\text{$q$-exp}}
R[[q]]\ra D\ra 0$$
with~$\Fl$ we obtain
$$0 \ra D[\ell] \ra H^0(\cA,\Omega_{\cA})\tensor\Fl\ra
\Fl[[q]] \ra D\tensor\Fl \ra 0.$$
Here we have used that $\Tor^1(D,\Fl)$ is the $\ell$-torsion in~$D$,
and that $\Tor^1(-,\Fl)$ vanishes on the torsion-free group $R[[q]]$.
(Alternatively, we could have used the snake lemma\index{Snake lemma}.)
To show that $D[\ell]=0$, it suffices to prove that the map
$\Psi:H^0(\cA,\Omega_{\cA})\tensor\Fl\ra \Fl[[q]]$
is injective.
Since $\ell\neq 2$ and~$A$ is an optimal quotient,
\cite[Cor 1.1]{mazur:rational} gives an exact sequence
$$0 \ra H^0(\cA/\Zl,\Omega_{\cA/\Zl}) \ra
H^0(\cJ/\Zl,\Omega_{\cJ/\Zl}) \ra
H^0(\cB/\Zl,\Omega_{\cB/\Zl}) \ra 0$$
where $\cB$ is the N\'eron model
of $\ker(J\ra A)$. In particular, $H^0(\cB/\Zl,\Omega_{\cB/\Zl})$
is torsion free, so
\begin{align*}
H^0(\cA/\Zl,\Omega_{\cA/\Zl})\tensor\Fl \ra
H^0(\cJ/\Zl,\Omega_{\cJ/\Zl})\tensor\Fl
&\isom H^0(\cX/\Zl,\Omega^{\text{reg}}_{\cX/\Zl})\tensor\Fl\\
&\isom H^0(\cX/\Fl,\Omega^{\text{reg}}_{\cX/\Fl})
\end{align*}
is injective. (The last isomorphism is by
\cite[Prop.~3.3, pg.~68]{mazur:eisenstein}.)
We also remark that
$$H^0(\cA,\Omega_{\cA})\tensor\Fl\isom
H^0(\cA/\Zl,\Omega_{\cA/\Zl})\tensor\Fl,$$
because~$\Zl$ is torsion free, hence flat over~$R$.
Thus the map
$$H^0(\cA,\Omega_{\cA})\tensor\Fl\ra
H^0(\cX/\Fl,\Omega^{\text{reg}}_{\cX/\Fl})$$
is injective.
If $\ell\nmid N$, then injectivity of~$\Psi$ now follows from
the $q$-expansion principle, which asserts that the
$q$-expansion map $H^0(\cX/\Fl,\Omega^{\text{reg}}_{\cX/\Fl})\ra \Fl[[q]]$
is injective.
Suppose~$\ell$ does divide~$N$, and let
$\omega\in \ker(\Psi)$.
Since $\ell \mid N$ and $\ell\nmid 2m$, we have that $\ell \mid\mid N$;
thus $\cX/\Fl$ breaks up into a union of two irreducible
components, and the $q$-expansion principle\index{$q$-expansion principle}
implies only that~$\omega$
vanishes on the irreducible component containing the cusp~$\infty$.
However, since~$A$ is {\em new} and corresponds to a {\em single}
eigenform,~$\omega$ is an eigenvector for the involution~$W_N$
(since~$f$ and all of its conjugates are). Since~$W_N$ permutes
the two components,~$\omega$ must be~$0$ on all $\cX/\Fl$.
Therefore $\omega=0$, and hence~$\Psi$ is injective.
\end{proof}
\subsection{Numerical evidence for the $c_A=1$ conjecture}
\index{Manin constant!conjecture about|textit}
\index{Conjecture!that Manin constant equals $1$|textit}
In the paper~\cite{empirical}, the authors
show that $c_A=1$ for~$28$ two-dimensional optimal
quotients\index{Optimal quotient}
of $J_0(N)$ (see Section~\ref{sec:analytic-empirical}).
The non-square-free levels treated are:
$$N=3^2\cdot 7,\quad 3^2\cdot 13,
\quad 5^3,\quad 3^3\cdot 5,\quad 3\cdot 7^2,
\quad 5^2\cdot 7,\quad 2^2\cdot 47,\quad 3^3\cdot 7.$$
In every case, $c_A = 1$.
\begin{conjecture}[Agashe\index{Conjecture!Agashe and Stein}
\index{Agashe!conjecture of}\index{Agashe}]
Let~$A$ be an optimal quotient of $J_0(N)$, and let
$c_A$ be the corresponding Manin constant\index{Manin constant}.
Then $c_A=1$.
\end{conjecture}
\section{Analytic invariants}
\index{Analytic invariants}
\label{sec:analytic}
Fix a newform
$$f =\sum_{n\geq 1} a_n q^n\in S_k(N,\eps),$$
{\bf and assume that $\eps^2=1$.}
\begin{remark}
Our assumption that $\eps^2=1$ does not imply that~$f$ has totally
real Fourier coefficients.
There is an eigenform in $S_2(24,\eps)$ whose Fourier coefficients
are not totally real, where~$\eps$ is one of the
characters of conductor~$8$.
\end{remark}
Let $K_f = \Q(\ldots a_n \ldots)$ and
let $f_1,\ldots,f_d$ be the Galois conjugates of~$f$,
where $d=[K_f:\Q]$.
As in Section~\ref{sec:tori},
we consider the complex torus\index{Complex torus} $A_f$ attached to~$f$.
In this section we describe how to compute the torus $A_f$ and
the special values at the critical integers $1,2,\ldots,k-1$
of the~$L$ function $L(A_f,s)$ associated to $A_f$.
(See~\ref{defn:lseries} for the definition of $L(A_f,s)$.)
Let
$$f = \sum_{n\geq 1} a_n q^n \in M_k(N,\eps)$$
be a modular form (we do not assume
that~$f$ is an eigenform).
We recall the integration pairing\index{Integration pairing}
of Theorem~\ref{thm:perfectpairing} (which we normalize
by $-2\pi i$ for convenience):
$$
\langle\,, \,\rangle:\, M_k(N,\eps) \cross \sM_k(N,\eps)
\lra \C$$
$$\langle f , P\{\alp,\beta\}\rangle =
-\twopii \int_{\alp}^{\beta} f(z)P(z,1) dz.$$
Let $I_f\subset \T$ be the kernel of the
map $\T\ra K_f$ sending~$T_n$ to~$a_n$.
The integration pairing
gives rise to the period mapping\label{defn:periodmapping}
$$\Phi_f : \sM_k(N,\eps) \ra \Hom_\C(S_k(N,\eps)[I_f],\C),$$
and $A_f = \Hom_\C(S_k(N,\eps)[I_f],\C)/\Phi_f(\sS_k(N,\eps))$
is the cokernel.
\subsection{Extended modular symbols}\label{defn:extendedmodsyms}
\index{Extended modular symbols|textit}
For the purposes of computing periods, it
is advantageous to extend the notion of modular
symbols\index{Modular symbols} to allows symbols of the form
$P\{z,w\}$ where~$z$ and~$w$ are now
arbitrary elements of $\h^*=\h\union\P^1(\Q)$.
The free abelian group $\esM_k$
of \defn{extended modular symbols}
is spanned by such symbols, and is of uncountable
rank over~$\Z$. However, it is still equipped with
an action of $\gzero$ and we can form the
largest torsion-free quotient
$\esM_k(N,\eps)$ of $\esM_k$ by
the relations $\gam x = \eps(\gam)x$ for
$\gam\in\gzero$.
The integration
pairing\index{Integration pairing!and extended modular symbols}
extends to $\esM_k(N,\eps)$. There is a natural
embedding
$\iota: \sM_k(N,\eps)\hookrightarrow \esM_k(N,\eps)$
which respects the pairing in the sense that
$\langle f, \iota(x)\rangle = \langle f , x\rangle.$
In many cases it is advantageous to replace
$x\in\sM_k(N,\eps)$ first by $\iota(x)$, and then
by an equivalent sum $\sum y_i$ of symbols
$y_i\in \esM_k(N,\eps)$.
The period
$\langle f, x\rangle$
is then replaced by the equivalent
sum of periods $\sum \langle f , y_i\rangle$.
The latter is frequently {\em much} easier to approximate
numerically.
\subsection{Numerically computing period integrals}
Consider a point~$\alp$ in the upper half plane
and any one of the (extended) modular
symbols\index{Extended modular symbols}
$X^mY^{k-2-m}\{\alp,\infty\}$.
Given a cusp form $g =\sum_{n\geq 1} b_n q^n\in S_k(N,\eps)$
and an integer $m\in \{0,1,\ldots,k-2\}$, we find that
\begin{equation}\label{intsum}
\langle g, \, X^mY^{k-2-m}\{\alpha,\infty\}\rangle =
\twopii \int_{\alpha}^{i\infty} g(z)z^m dz =
\twopii \sum_{n=1}^{\oo} b_n \int_{\alpha}^{i\infty} e^{2\pi i n z} z^m dz.
\end{equation}
The reversal of summation and integration is justified because
the imaginary part of~$\alp$ is positive so that the sum
converges absolutely. This is made explicit in the following
lemma, which can be proved using repeated integration by parts.
\begin{lemma}\label{lem:intexp}
\begin{equation}\label{intexp}
\int_{\alpha}^{i\infty} e^{2\pi i n z} z^m dz
\,\,=\,\, e^{2\pi i n \alpha}
\sum_{s=0}
CoCalc Public Fileswww / papers / thesis / algorithms.texOpen with one click!