\comment{
% $Header: /home/was/papers/thesis/RCS/modsyms.tex,v 1.7 2000/05/10 20:31:58 was Exp $

$Log: modsyms.tex,v $
Revision 1.7  2000/05/10 20:31:58  was
done.

Revision 1.6  2000/05/10 08:53:23  was
misc. don't remember.

Revision 1.5  2000/05/09 03:02:10  was
Re-indexed the whole chapter.

Revision 1.4  2000/05/08 15:48:28  was
Added $Log: modsyms.tex,v $
Added Revision 1.7  2000/05/10 20:31:58  was
Added done.
Added
Added Revision 1.6  2000/05/10 08:53:23  was
Added misc. don't remember.
Added
Added Revision 1.5  2000/05/09 03:02:10  was
Added Re-indexed the whole chapter.
Added

}


\chapter{Modular symbols}%
\label{chap:modsym}\index{Modular symbols}%
Modular symbols permeate this thesis.  In their simplest incarnation,
modular symbols provide a finite presentation for the homology group
$H_1(X_0(N),\Z)$ of the Riemann surface $X_0(N)$.  This presentation
is equipped with such a rich structure that from it we can deduce the
action of the Hecke operators; this is already sufficient information for
us to compute a basis for the space $S_2(\Gamma_0(N),\C)$ of cusp
forms.

We recall the definition of spaces of modular symbols in
Sections~\ref{sec:defnofmodsyms}--\ref{cuspidalsymbols}.  Then in 
Section~\ref{sec:duality}, we review the
duality between modular symbols and modular forms.  
In Section~\ref{sec:heckeops}, we see that
modular symbols are furnished with analogues of each of the standard
operators that one finds on spaces of modular forms, and in
Section~\ref{sec:degeneracymaps} we see that the same is true of the
degeneracy maps.  Section~\ref{sec:maninsymbols} describes Manin
symbols, which supply a convenient finite presentation for the space of
modular symbols.  Finally, Section~\ref{sec:tori} introduces the
complex torus attached to a newform, which appears in various guises
throughout this thesis.


Before continuing, we offer an apology.  We will only consider modular
symbols that are already equipped with a fixed Dirichlet character.
Though fixing a character complicates the formulas, the resulting increase
in efficiency is of extreme value in computational applications.
Fixing a character allows us to compute in just the part of the space
of modular symbols for $\Gamma_1(N)$ that interests us.  We apologize
for any inconvenience this may cause the less efficiency minded
reader.

{\bf Acknowledgment.}  This chapter and the next were greatly
influenced by the publications of Cremona~\cite{cremona:gammaone,
cremona:algs}\index{Cremona} and Merel~\cite{merel:1585}\index{Merel},
along with the foundational contributions of
Manin~\cite{manin:parabolic}, Mazur~\cite{mazur:arithmetic_values,
mazur:symboles}, and Shokurov~\cite{sokurov:modsym}.  Cremona's
book~\cite{cremona:algs} provides a motivated roadmap that guides the
reader who wishes to compute with modular symbols in the familiar
context of elliptic curves, and Merel's\index{Merel} article provides an accessible
overview of the action of Hecke operators on higher weight modular
symbols, and the connection between modular symbols and related 
cohomology theories.

\section{The definition of modular symbols}
\label{sec:defnofmodsyms}
Fix a positive integer~$N$, an integer $k\geq 2$, and a continuous
homomorphism
  $$\eps:(\Z/N\Z)^*\ra\C^*$$
such that $\eps(-1)=(-1)^k$.
We call~$N$ the \defn{level}\index{Level of modular symbols|textit},~$k$ the 
\defn{weight}\index{Weight of modular symbols|textit},
and~$\eps$ the \defn{Dirichlet character}.\index{Dirichlet character|textit}


Consider the quotient of the abelian group generated by all formal symbols 
$\{\alp,\beta\}$, with $\alp, \beta\in\P^1(\Q)=\Q\union\{\infty\}$,
by the following relations:
  $$\{\alp,\beta\}+\{\beta,\gamma\}+\{\gamma,\alp\} = 0,$$
for all $\alp,\beta,\gamma\in\P^1(\Q)$.
Let $\sM$ be the torsion-free quotient of this group by its torsion
subgroup.  Because $\sM$ is torsion free, $\{\alp,\alp\}=0$ and
$\{\alp,\beta\} = -\{\beta,\alp\}$.
\index{Modular symbols!relations satisfied by}

\begin{remark}
One is motivated to consider these relations by viewing
$\{\alp,\beta\}$ as the homology class of an appropriate
path from~$\alpha$ to~$\beta$ in the upper half plane.
\end{remark}

Let $V_{k-2}$\label{defn:vk} be the $\Z$-submodule of $\Z[X,Y]$ made up of
all homogeneous polynomials of degree $k-2$, and set
   $\sM_k :=  V_{k-2}\tensor\sM.$
\label{pg:higherweightmodsym}
For $g=\abcd{a}{b}{c}{d}\in\GL_2(\Q)$ and $P\in V_{k-2}$, let
\begin{align*}
     gP(X,Y) &= P\left(\det(g)g^{-1}\vtwo{X}{Y}\right)
             = P\left(\mtwo{\hfill d}{-b}{-c}{\hfill a}\vtwo{X}{Y}\right)\\
             &= P(dX-bY,-cX+aY).
\end{align*}
This defines a left action of $\GL_2(\Q)$ on $V_{k-2}$;
it is a left action because 
\begin{align*}
 (gh)P(v) &= P(\det(gh)(gh)^{-1}v) 
          = P(\det(h)h^{-1}\det(g)g^{-1}v)\\
          &= gP(\det(h)h^{-1}v) = g(hP(v)).
\end{align*}
Combining this action with the action of $\GL_2(\Q)$ on $\P^1(\Q)$ 
by linear fractional transformations gives
a left action of $\GL_2(\Q)$ on $\sM_k$: 
  $$g (P \tensor \{\alp,\beta\}) = g(P)\tensor\{g(\alp),g(\beta)\}.$$
Finally, for $g=\abcd{a}{b}{c}{d}\in\Gamma_0(N)$, let 
$\eps(g) := \eps(\overline{a})$, 
where $\overline{a}\in\Z/N\Z$ is the reduction modulo~$N$ of~$a$.

Let 
$$\Z[\eps] := \Z[\eps(a) : a \in \Z/N\Z]$$
be the subring of~$\C$ generated by the values of the
character~$\eps$.
\begin{definition}[Modular symbols]\label{defn:modsym}
\index{Modular symbols|textit}%
The space of \defn{modular symbols} $\sM_k(N,\eps)$ 
of level~$N$, weight~$k$ and character~$\eps$ is 
the largest torsion-free quotient of $\sM_k\tensor\Z[\eps]$ by the 
$\Z[\eps]$-submodule generated by the 
relations $gx-\eps(g)x$ for all $x\in\sM_k$
and all $g\in\Gamma_0(N)$.  
\end{definition}
Denote by $P\{\alp,\beta\}$ the image
of $P\tensor\{\alp,\beta\}$ in $\sM_k(N,\eps)$.
For any $\Z[\eps]$-algebra~$R$, let 
$$\sM_k(N,\eps;R) := \sM_k(N,\eps)\tensor_{Z[\eps]} R.$$
See Section~\ref{sec:computingmk} for an algorithm which
can be used to compute $\sM_k(N,\eps;\Q(\eps))$.

\section{Cuspidal modular symbols}
\label{cuspidalsymbols}
\index{Cuspidal modular symbols|textit}
Let~$\sB$ be the  free abelian group generated by the symbols
$\{\alp\}$ for all $\alp\in\P^1(\Q)$.  
There is a left action of~$\GL_2(\Q)$ on~$\sB$ given by
$g\{\alp\}=\{g(\alp)\}$.
Let $\sB_k := V_{k-2}\tensor \sB$, and let $\GL_2(\Q)$ act
on $\sB_k$ by $g(P\{\alp\}) = (gP)\{g(\alp)\}$.  
\begin{definition}[Boundary modular symbols]\label{def:boundarysymbols}
The space $\sB_k(N,\eps)$ of 
\index{Boundary modular symbols|textit}%
\defn{boundary modular symbols} 
is the largest torsion-free quotient 
of $\sB_k\tensor\Z[\eps]$ by the relations
$gx = \eps(g) x$ for all 
$g\in \Gamma_0(N)$ and $x\in \sB_k$.
\end{definition}
Denote by $P\{\alp\}$ the image of $P\tensor\{\alp\}$
in $\sB_k(N,\eps)$.
The \defn{boundary map} 
  $$\delta: \sM_k(N,\eps) \ra \sB_k(N,\eps)$$
is defined by
 $$\delta(P\{\alp,\beta\}) =
            P\{\beta\}-P\{\alp\}.$$
\begin{definition}[Cuspidal modular symbols]%
\label{defn:cuspidalmodularsymbols}%
\index{Cuspidal modular symbols|textit}%
The space $\sS_k(N,\eps)$ of 
\defn{cuspidal modular symbols}
is the kernel of~$\delta$.  
\end{definition}
The three spaces defined above fit together in the
following exact sequence:
  $$0\ra \sS_k(N,\eps) \ra\sM_k(N,\eps)\xrightarrow{\,\delta\,}
              \sB_k(N,\eps).$$



\section{Duality between modular symbols and modular forms}%
\label{sec:duality}
\index{Modular symbols!duality with modular forms}%
\index{Modular forms!duality with modular symbols}%
\index{Integration pairing}%
For any positive integer~$k$, any $\C$-valued function~$f$ on 
the complex upper half plane 
$$\h:=\{z \in \C : \im(z) > 0\},$$
and any matrix $\gamma\in\GL_2(\Q)$, define a function 
$f|[\gamma]_k$ on~$\h$ by
 $$(f|[\gamma]_k)(z) = \det(\gamma)^{k-1}\frac{f(\gamma z)}{(cz+d)^{k}}.$$
\begin{definition}[Cusp forms]\index{Cusp forms|textit}
Let $S_k(N,\eps)$ be the complex vector space of holomorphic
functions $f(z)$ on~$\h$ that satisfy 
the equation 
  $$f|[\gamma]_k = \eps(\gamma)f$$
for all $\gamma\in\Gamma_0(N)$, and such that~$f$ 
is holomorphic and vanishes at all cusps, in the sense of
\cite[pg.~42]{diamond-im}.
\end{definition}

\begin{definition}[Antiholomorphic cusp forms]%
\index{Cusp forms!antiholomorphic|textit}%
\index{Antiholomorphic cusp forms|textit}
Let $\Sbar_k(N,\eps)$ be the space of 
\defn{antiholomorphic cusp forms}; 
the definition is as above, except 
$$\frac{f(\gamma z)}{(c\overline{z}+d)^k} = \overline{\eps}(\gamma) f(z)$$
for all $\gamma\in\Gamma_0(N)$.\footnote{The $\overline{\eps}$ 
should be replaced by~$\eps$ in this formula, as 
in \cite[\S2.5]{merel:1585}.}
\end{definition}
There is a canonical isomorphism of real vector spaces
between $S_k(N,\eps)$ and $\Sbar_k(N,\eps)$ that associates
to~$f$ the antiholomorphic cusp form defined by the function
$z\mapsto \overline{f(z)}$. 

\begin{theorem}[Merel]\label{thm:perfectpairing}\index{Merel}
There is a  pairing 
\begin{equation*}
    \langle\,\, , \, \, \rangle: 
    (S_k(N,\eps)\oplus \Sbar_k(N,\eps)) \cross \sM_k(N,\eps;\C)
   \ra \C
\end{equation*}
given by
$$\langle f\oplus g, P\{\alp,\beta\}\rangle = 
       \int_{\alp}^{\beta} f(z)P(z,1) dz 
     + \int_{\alp}^{\beta} g(z)P(\zbar,1) d\zbar,$$
where the path from~$\alp$ to~$\beta$ is, 
except for the endpoints, contained in~$\h$.  
The pairing is perfect when restricted to $\sS_k(N,\eps;\C)$.
\end{theorem}
\begin{proof}
Take the~$\eps$ part of each side of~\cite[Thm.~3]{merel:1585}.
\end{proof}


\section{Linear operators}
\label{sec:heckeops}
\subsection{Hecke operators}\label{heckeops:modsym}
\index{Hecke operators}\index{Operators!Hecke}
For each positive integer~$n$ and each space~$V$ of modular symbols or modular
forms, there is a \defn{Hecke operator}~$T_n$, which acts
as a linear endomorphism of~$V$.  
For the definition of $T_n$ on modular symbols,
see~\cite[\S2]{merel:1585}.  
Alternatively, because we consider only modular symbols 
with character, the following
recipe completely determines the Hecke operators.
First, when $n=p$ is prime, we have
$$T_p(x) = \left[ \mtwo{p}{0}{0}{1} + \sum_{r \md p}
                  \mtwo{1}{r}{0}{p}\right] x,$$
where the first matrix is omitted if $p\mid N$. 
If~$m$ and~$n$ are coprime, then $T_{mn} = T_mT_n$.
Finally, if~$p$ is a prime, $r\geq 2$ is an integer,~$\varepsilon$ is 
the Dirichlet character of associated to~$V$, and~$k$ is the weight
of~$V$, then 
  $$T_{p^r} = 
        T_p  T_{p^{r-1}} - \varepsilon(p) p^{k-1} T_{p^{r-2}}.$$

\begin{definition}\index{Hecke algebra|textit}
The \defn{Hecke algebra associated to $V$} is the subring
 $$\T=\T_V = \Z[\ldots T_n \ldots]$$
of $\End(V)$ generated by all Hecke operators $T_n$, with $n=1,2,3,\ldots$.
\end{definition}

\begin{proposition}\label{prop:modsympairing}
The pairing of Theorem~\ref{thm:perfectpairing} respects the 
action of the Hecke operators\index{Hecke operators!respect pairing}, 
in the sense that $\langle f T, x \rangle = \langle f , T x \rangle$
for all $T\in \T$, $x\in\sM_k(N,\eps)$, 
 and $f\in S_k(N,\eps)\oplus \Sbar_k(N,\eps)$. 
\end{proposition}
\begin{proof}
See~\cite[Prop.~10]{merel:1585}.
\end{proof}

\subsection{The $*$-involution}\label{sec:starinvolution}
\index{Star involution|textit}\index{Operators!$*$-involution|textit}
The matrix $j=\abcd{-1}{0}{\hfill0}{1}$ defines 
an involution~$*$ of $\sM_k(N,\eps)$ given by 
$x\mapsto x^*=j(x)$.  Explicitly,
\begin{equation*}
(P(X,Y)\{\alp,\beta\})^* = P(X,-Y)\{-\alp,-\beta\}.
\end{equation*}
Because the space of modular symbols is constructed as a quotient,
it is not obvious that the $*$-involution is well defined.%
\index{Star involution!is well defined}
\begin{proposition}
The $*$-involution is well defined.
\end{proposition}
\begin{proof}
Recall that $\sM_k(N,\eps)$ is the largest torsion-free quotient of the 
free $\Z[\eps]$-module generated by symbols 
$x=P\{\alp,\beta\}$ by the submodule generated by
relations $\gamma x - \eps(\gamma)x$ for
all $\gamma\in \Gamma_0(N)$.  
In order to check that the operator~$*$ is well defined, it
suffices to check, for any $x\in\sM_k$, that 
$*(\gamma x - \eps(\gamma)x)$ is of
the form $\gamma' y - \eps(\gamma') y$, for some~$y$ in $\sM_k$.
Note that if $\gamma=\abcd{a}{b}{c}{d}\in \Gamma_0(N)$, then 
$j\gamma j^{-1} = \abcd{\hfill a}{-b}{-c}{\hfill d}$ is also in $\Gamma_0(N)$
and $\eps(j\gamma j^{-1}) = \eps(\gamma)$.  We have
\begin{align*}
    j(\gamma x - \eps(\gamma) x) &= 
           j \gamma x - j \eps(\gamma) x \\
        &= j \gamma j^{-1} j x - \eps(\gamma) j x\\
        &= (j\gamma j^{-1}) (j x) - \eps(j \gamma j^{-1}) (jx).
\end{align*}
\end{proof}

If~$f$ is a modular form\index{Modular forms}, let $f^*$ be the holomorphic
function $\overline{f(-\overline{z})}$, where the bar
denotes complex conjugation.
   The Fourier coefficients\index{Fourier coefficients}
of $f^*$ are the complex conjugates of those of~$f$; though $f^*$
is again a holomorphic modular form\index{Modular forms}, its character
is $\overline{\eps}$ instead of~$\eps$. 
The pairing of Theorem~\ref{thm:perfectpairing}
is the restriction of a pairing on the full spaces without
character, and we have the following proposition.
\index{Star involution!and integration pairing}
\begin{proposition}\label{prop:starpairing}\footnote{G. Weber pointed 
out that this isn't correct.  It is correct if the pairing is replaced
by $(f,x) = -2\pi i\langle f, x\rangle$ and $x$ is 
restricted to modular symbols that are fixed by complex 
conjugation.}
We have
\begin{equation*}
\langle f^*,  x^* \rangle = \overline{\langle f, x\rangle}.
\end{equation*}
\end{proposition}

\begin{definition}[Plus-one quotient]\index{Plus-one quotient|textit}%
\index{Modular symbols!plus-one quotient of}
\index{Modular symbols!minus-one quotient of}
The \defn{plus-one quotient} $\sM_k(N,\eps)_+$ is the 
largest torsion-free quotient of $\sM_k(N,\eps)$ by the relations
$x^*-x=0$ for all $x\in \sM_k(N,\eps)$. 
Similarly, the \defn{minus-one quotient}\index{Minus-one quotient} 
is the quotient of $\sM_k(N,\eps)$ by all relations
$x^*+x=0$, for $x\in\sM_k(N,\eps)$.
\end{definition}

\begin{warning} We were forced to make
a choice in our definition of the operator~$*$.
Fortunately, it agrees with that of~\cite[\S2.1.3]{cremona:algs},
but {\em not} with the choice made in~\cite[\S1.6]{merel:1585}. 
\end{warning}

\subsection{The Atkin-Lehner involutions}\label{sec:atkin-lehner}
\index{Operators!Atkin-Lehner|textit}
\index{Atkin-Lehner involution|textit}
In this section we assume 
that~$k$ is even and $\eps^2=1$.
The assumption on~$\eps$ is necessary only so that
the involution we are about to define preserves
$\sM_k(N,\eps)$.  More generally, it is possible to define
a map which sends $\sM_k(N,\eps)$ to $\sM_k(N,\overline{\eps})$.

To each divisor~$d$ of~$N$ such that $(d,N/d)=1$ there is an 
\defn{Atkin-Lehner involution}~$W_d$ of $\sM_k(N,\eps)$,
which is defined as follows.  Using the Euclidean algorithm, choose
integers $x,y,z,w$ such that 
         $$dxw - (N/d)yz = 1.$$ 
Next let $g=\abcd{dx}{y}{Nz}{dw}$ and define 
     $$W_d(x) \define \frac{1}{d^{\frac{k-2}{2}}}\cdot g(x).$$
For example, when $d=N$ we have $g=\abcd{0}{-1}{N}{\hfill 0}$.  
The factor of $d^{\frac{k-2}{2}}$ is necessary to normalize
$W_d$ so that it is an involution.

On modular forms there is an Atkin-Lehner involution, 
also denoted $W_d$,\index{Modular forms!and Atkin-Lehner involution} 
which acts by $W_d(f) = f|[W_d]_k$.  These two like-named involutions
are compatible with the integration pairing:
$$\langle W_d(f), x\rangle = \langle f, W_d(x)\rangle.$$
\index{Atkin-Lehner involution!and integration pairing}

\section{Degeneracy maps}
\label{sec:degeneracymaps}
\label{pg:degeneracymaps}
\index{Degeneracy maps}
In this section, we describe natural maps between spaces of
modular symbols of different levels. 

Fix a positive integer~$N$ and a Dirichlet 
character\index{Dirichlet character} 
$\eps : (\Z/N\Z)^*\ra \C^*$.  Let~$M$ be a positive divisor
of~$N$ that is divisible by the conductor of~$\eps$, in the sense
that~$\eps$ factors through $(\Z/M\Z)^*$ via the natural map
$(\Z/N\Z)^*\ra (\Z/M\Z)^*$ composed with some uniquely defined
character $\eps':(\Z/M\Z)^*\ra\C^*$.  For any positive divisor~$t$ of
$N/M$, let $T=\abcd{1}{0}{0}{t}$ and fix a choice $D_t=\{T\gamma_i :
i=1,\ldots, n\}$ of coset representatives for $\Gamma_0(N)\backslash
T\Gamma_0(M)$.

\begin{warning}
There is a mistake in \cite[\S2.6]{merel:1585}:
 The quotient ``$\Gamma_1(N)\backslash\Gamma_1(M)T$'' should be replaced 
by ``$\Gamma_1(N)\backslash T\Gamma_1(M)$''.
\end{warning}
\begin{proposition}
For each divisor~$t$ of $N/M$ there are well-defined linear maps
\begin{align*}
\alp_t : \sM_k(N,\eps) \ra \sM_k(M,\eps'),&\qquad
      \alp_t(x) = (tT^{-1})x = \mtwo{t}{0}{0}{1} x\\
\beta_t : \sM_k(M,\eps') \ra \sM_k(N,\eps),&\qquad
      \beta_t(x) = \sum_{T\gam_i\in D_t} \eps'(\gam_i)^{-1}T\gam_i{} x.
\end{align*}
Furthermore,
  $\alp_t\circ \beta_t$ is multiplication by 
  $t^{k-2}\cdot [\Gamma_0(M) : \Gamma_0(N)].$
\end{proposition}
\begin{proof}
To show that~$\alp_t$ is well defined, we must show that for
each $x\in\sM_k(N,\eps)$ and $\gam=\abcdmat\in\Gamma_0(N)$, that we
have
  $$\alp_t(\gamma x  -\eps(\gamma) x)=0\in\sM_k(M,\eps').$$
We have
$$\alp_t(\gam x) = \mtwo{t}{0}{0}{1}\gam x
        = \mtwo{a}{tb}{c/t}{d}\mtwo{t}{0}{0}{1} x
        = \eps'(a)\mtwo{t}{0}{0}{1} x,$$
so 
$$\alp_t(\gamma x  -\eps(\gamma) x)
  = \eps'(a)\alp_t(x) - \eps(\gamma)\alp_t(x) = 0.$$

We next verify that~$\beta_t$ is well defined.
Suppose that $x\in\sM_k(M,\eps')$ and $\gamma\in\Gamma_0(M)$;
then $\eps'(\gam)^{-1}\gam x = x$, so
\begin{align*}
\beta_t(x) 
    &= \sum_{T\gam_i\in D_t} 
        \eps'(\gam_i)^{-1}T\gam_i{}\eps'(\gam)^{-1}\gam{} x\\
    &= \sum_{T\gam_i\gam\in D_t} 
        \eps'(\gam_i\gam)^{-1}T\gam_i{}\gam{} x.
\end{align*}
This computation shows that the definition of~$\beta_t$ 
does not depend on the choice~$D_t$ of coset representatives.
To finish the proof that~$\beta_t$ is well defined
we must show that, for $\gam\in\Gamma_0(M)$, we have
$\beta_t(\gam x) = \eps'(\gam)\beta_t(x)$ so that $\beta_t$
respects the relations that define $\sM_k(M,\eps)$. 
Using that~$\beta_t$ does not depend on the choice of 
coset representative, we find that for $\gamma\in\Gamma_0(M)$,
\begin{align*}
  \beta_t(\gam x) 
     &= \sum_{T\gam_i\in D_t} \eps'(\gam_i)^{-1}T\gam_i{} \gam{} x\\
     &= \sum_{T\gam_i\gam^{-1}\in D_t} 
         \eps'(\gam_i\gam^{-1})^{-1}T\gam_i{}\gam{}^{-1} \gam{} x\\
     &= \eps'(\gam)\beta_t(x).\\
\end{align*}
To compute $\alp_t\circ\beta_t$, we use 
that $\#D_t = [\Gamma_0(N) : \Gamma_0(M)]$:
\begin{align*}
 \alp_t(\beta_t(x)) &=
    \alp_t \left(\sum_{T\gamma_i}
        \eps'(\gam_i)^{-1}T\gam_i x\right)\\
  &= \sum_{T\gamma_i}
        \eps'(\gam_i)^{-1}(tT^{-1})T\gam_i x\\
  &= t^{k-2}\sum_{T\gamma_i}
        \eps'(\gam_i)^{-1}\gam_i x\\
  &= t^{k-2}\sum_{T\gamma_i} x \\
  &= t^{k-2} \cdot [\Gamma_0(N) : \Gamma_0(M)] \cdot x.
\end{align*}
The scalar factor of $t^{k-2}$ appears instead 
of~$t$, because~$t$ is acting on~$x$ as an element of $\GL_2(\Q)$
{\em not} as an an element of~$\Q$.
\end{proof}

\begin{definition}[New and old modular symbols]%
\label{def:newandoldsymbols}%
\index{New modular symbols|textit}%
\index{Old modular symbols|textit}%
\index{Modular symbols!new and old subspace of|textit}%
The subspace $\sM_k(N,\eps)^{\new}$ 
of \defn{new modular symbols} is the
intersection of the kernels of the $\alp_t$ as~$t$ 
runs through all positive divisors of $N/M$ and~$M$
runs through positive divisors of~$M$ strictly less than~$N$
and divisible by the conductor of~$\eps$.
The subspace $\sM_k(N,\eps)^{\old}$ 
of \defn{old modular symbols}
is the subspace generated by the images of the $\beta_t$
where~$t$ runs through all positive divisors of $N/M$ and~$M$
runs through positive divisors of~$M$ strictly less than~$N$
and divisible by the conductor of~$\eps$.
\end{definition}

{\bf WARNING:} The new and old subspaces need not be disjoint, as
the following example illustrates!
This is contrary to the statement on page~80 of~\cite{merel:1585}.
\begin{example}
We justify the above warning.
Consider, for example, the case $N=6$, $k=2$, and trivial character.
The spaces $\sM_2(2)$ and $\sM_2(3)$ are each of dimension~$1$, and
each is generated by the modular symbol $\{\infty,0\}$.
The space $\sM_2(6)$ is of dimension~$3$, and is generated by
the~$3$ modular symbols $\{\infty, 0\}$, $\{-1/4, 0\}$, 
and $\{-1/2, -1/3\}$.  
The space generated by the~$2$ images 
of $\sM_2(2)$ under the~$2$ degeneracy 
maps has dimension~$2$, and likewise for $\sM_2(3)$.
Together these images generate $\sM_2(6)$, so $\sM_2(6)$ is 
equal to its old subspace.
However, the new subspace is nontrivial because 
the two degeneracy maps $\sM_2(6) \ra \sM_2(2)$ are equal,
as are the two degeneracy maps $\sM_2(6) \ra \sM_2(3)$.
In particular, the intersection of the kernels of the degeneracy
maps has dimension at least~$1$ (in fact, it equals~$1$).

Computationally, it appears that something similar to this happens
if and only if the weight is~$2$, the character is trivial,
and the level is composite.  This behavior is probably related
to the nonexistence of a characteristic~$0$ Eisenstein series
of weight~$2$ and level~$1$.
\end{example}

The following tempting argument is incorrect;
the error lies in the fact that 
an element of the old subspace 
is a {\em linear combination} of $\beta_t(y)$'s
for various~$y$'s and~$t$'s:
``If~$x$ is in both the new and old subspace, 
then $x=\beta_t(y)$ for some modular symbol~$y$ 
of lower level.  This implies $x=0$ because
 $$0 = \alp_t(x) = \alp_t(\beta_t(y))= 
t^{k-2}\cdot[\Gamma_0(N):\Gamma_0(M)] \cdot{}y.\text{''}$$


\begin{remark}
The map $\beta_t\circ\alp_t$ cannot in general be multiplication by
a scalar since $\sM_k(M,\eps')$
usually has smaller dimension than $\sM_k(N,\eps)$. 
\end{remark}

\comment{
\begin{example}
The proposition implies that $\beta_t$ is injective in
characteristic~$0$. This need not be the case in positive
characteristic, as the following example illustrates.  
Let~$p$ be any prime, and let $\eps:(\Z/N\Z)^* \ra
\Fbar_p^*$ be the reduction to characteristic~$p$
of a Dirichlet character.  
There is again a map $\beta_{t,p}:\sM_k(M,\eps';\Fbar_p) \ra
\sM_k(N,\eps;\Fbar_p)$, where the space $\sM_k(N,\eps;\Fbar_p)$ is
defined by choosing a maximal ideal $\wp$ lying over~$p$ in an
appropriate extension $\O$ of~$\Z$, and letting~$R=\Fbar_p$ 
be an algebraic closure of the finite field~$\O/\wp$.
When~$p$
does not divide $t^{k-2}\cdot [\Gamma_0(M) : \Gamma_0(N)]$, the
proposition shows that $\beta_{t,p}$ is injective.  However,
$\beta_t\tensor\F_p$ need not be injective for all~$p$.  For example,
suppose $M=14$, $N=28$, and $\eps=1$. Then there are bases with
respect to which the matrix of $\beta_1$ is the transpose of
$$\left(
\begin{matrix}
1&0&0&1&0&0&0&0&0\\
 0&1&0&0&1&0&0&0&0\\
 0&0&1&0&0&1&0&0&0\\
 0&0&0&0&0&0&2&1&-1\\
 0&0&0&0&0&0&0&1&1   
\end{matrix}
\right),$$
and the row vector $(0,0,0,1,1)$ is in the kernel of the mod~$2$ 
reduction of this matrix.
\end{example}
}

\subsection{Computing coset representatives}%
\index{Coset representatives}
\begin{definition}[Projective line mod~$N$]%
\index{Projective line modulo~$N$|textit}%
Let~$N$ be a positive integer.
Then the \defn{projective line}
$\P^1(N)$ is the set of 
pairs $(a,b)$, with $a, b\in\Z/N\Z$ and $\gcd(a,b,N)=1$, modulo
the eqivalence relation which identifies $(a,b)$ and $(a',b')$ if and only
if $ab'\con ba'\pmod{N}$.
\end{definition}

Let~$M$ be a positive divisor of~$N$ and~$t$ a 
divisor of~$N/M$.  The following {\em random} algorithm
computes a set~$D_t$ of representatives for the orbit space
$\Gamma_0(M)\backslash T\Gamma_0(N).$
There are deterministic algorithms for computing
$D_t$, but all of the ones the author has found are
{\em vastly} less efficient than the following random algorithm.
\begin{algorithm}\label{alg:degenreps}%
\index{Algorithm for computing!coset representatives}
      Let $\Gamma_0(N/t,t)$ denote the subgroup of $\SL_2(\Z)$
consisting of matrices that are upper triangular modulo $N/t$ and lower
triangular modulo~$t$.   Observe that two right cosets
 of $\Gamma_0(N/t,t)$ in $\SL_2(\Z)$,  represented by 
$\abcd{a}{b}{c}{d}$ and $\abcd{a'}{b'}{c'}{d'}$,
are equivalent if and only if 
$(a,b)=(a',b')$ as points of $\P^1(t)$
and $(c,d)=(c',d')$ as points of $\P^1(N/t)$.  
Using the following algorithm, we compute right coset 
representatives for $\Gamma_0(N/t,t)$ 
inside~$\Gamma_0(M)$.
\begin{enumerate}
       \item Compute the number $[\Gamma_0(M):\Gamma_0(N)]$ of cosets.
       \item Compute a random element $x \in \Gamma_0(M)$. 
       \item If~$x$ is not equivalent to anything generated so
              far, add it to the list. 
       \item Repeat steps (2) and (3) until the list is as long 
             as the bound of step (1).
\end{enumerate}
There is a natural bijection between
       $\Gamma_0(N)\backslash T \Gamma_0(M)$
and $\Gamma_0(N/t,t)\backslash \Gamma_0(M)$,
under which~$T\gamma$ corresponds to~$\gamma$.
Thus we obtain coset representatives for
 $\Gamma_0(N)\backslash T\Gamma_0(M)$ 
by left multiplying each 
coset representative of $\Gamma_0(N/t,t)\backslash\Gamma_0(M)$  by~$T$.
\end{algorithm}

\subsection{Compatibility with modular forms}%
\index{Degeneracy maps!compatibility}%
The degeneracy maps defined above
are compatible with the corresponding degeneracy maps
$\tilde{\alp}_t$ and $\tilde{\beta}_t$
on modular forms\index{Modular forms}.  This is because the degeneracy
maps on modular forms are defined by summing over the 
same coset representatives $D_t$. 
Thus we have the following compatibilities.
\begin{align*}
  \langle \tilde{\alp}_t(f), x \rangle &= \langle f, \alp_t(x)\rangle,\\
  \langle \tilde{\beta}_t(f), x\rangle &=  \langle f, \beta_t(x) \rangle .
\end{align*}
If~$p$ is prime to~$N$, then $T_p\alp_t = \alp_t T_p$
   and $T_p\beta_t = \beta_t T_p$. 

\section{Manin symbols}%
\label{sec:maninsymbols}%
\index{Manin symbols}%
From the definition given in
Section~\ref{sec:defnofmodsyms}, it is not obvious
that $\sM_k(N,\eps)$ is of finite rank.  The Manin 
symbols provide a finite presentation of~$\sM_k(N,\eps)$
that is vastly more useful from a computational point of view. 
\index{Modular symbols!finite presentation of}

\begin{definition}[Manin symbols]\label{defn:maninsymbols}%
\index{Manin symbols|textit}%
The \defn{Manin symbols} are the set of pairs
           $$[P(X,Y),(u,v)]$$ 
where $P(X,Y)\in V_{k-2}$ and
$0\leq u,v < N$ with $\gcd(u,v,N)=1$.
\end{definition}
Define a {\em right} action of $\GL_2(\Q)$ on 
the free $\Z[\eps]$-module~$M$ generated by the Manin 
symbols as follows. The element $g=\abcd{a}{b}{c}{d}$ acts by
\begin{equation*}
[P,(u,v)]g=[g^{-1}P(X,Y),(u,v) g] 
    = [P(aX+bY,cX+dY),(au+cv,bu+dv)].
\end{equation*}
Let $\sigma=\abcd{0}{-1}{1}{\hfill 0}$ and $\tau=\abcd{0}{-1}{1}{-1}$\label{defn:sigmatau}.
Let $\sM_k(N,\eps)'$ be the largest torsion-free quotient 
of~$M$ by the relations
\begin{align*}
\mbox{}x + x\sigma &= 0,\\
\mbox{}x + x\tau+ x\tau^2 &= 0,\\
   \eps(\lambda) [P,(u,v)]- [P,(\lambda u, \lambda v)] &=0.
\end{align*}

\begin{theorem}\label{thm:maninsymbols}
There is a natural isomorphism 
$\vphi:\sM_k(N,\eps)'\lra\sM_k(N,\eps)$ given by
$$[X^iY^{2-k-i},(u,v)] \mapsto g(X^iY^{k-2-i}\{ 0,\infty\})$$
where $g=\abcd{a}{b}{c}{d}\in\SL_2(\Z)$ is any matrix
such that $(u,v)\con (c,d) \pmod{N}$.
\end{theorem}
\begin{proof}
In~\cite[\S1.2, \S1.7]{merel:1585} it is proved that 
$\vphi\tensor_{\Z[\eps]}\C$ is 
an isomorphism, so~$\vphi$ is injective and well defined.
The discussion in Section~\ref{sec:modmanconv} below 
(``Manin's trick'')\index{Manin's trick}\index{Manin symbols!and Manin's trick}
shows that every element in $\sM_k(N,\eps)$ is a $\Z[\eps]$-linear 
combination of elements in the image, so~$\vphi$ is surjective as well.
\end{proof}

\subsection{Conversion between modular and Manin symbols}%
\index{Manin symbols!conversion to modular symbols}%
\index{Modular symbols!conversion to Manin symbols}%
\label{sec:modmanconv}%
For some purposes it is better to work with modular symbols, and for
others it is better to work with Manin symbols.  For example, there
are descriptions of the Atkin-Lehner involution\index{Atkin-Lehner involution}
in terms of both Manin
and modular symbols; it appears more efficient to compute this
involution using modular symbols.  On the other hand, practically
Hecke operators can be computed more efficiently using Manin symbols.
It is thus essential to be able to convert between these two
representations.  The conversion from Manin to modular symbols is
straightforward, and follows immediately from
Theorem~\ref{thm:maninsymbols}.  The conversion back is accomplished
using the method used to prove Theorem~\ref{thm:maninsymbols}; it is
known as ``Manin's trick'',\index{Manin's trick|textit}\index{Manin!trick of|textit} and involves continued fractions\index{Continued fractions}.

Given a Manin symbol $[X^iY^{k-2-i},(u,v)]$\index{Manin symbols},
we write down a corresponding modular symbol\index{Modular symbols} 
as follows.
Choose $\abcd{a}{b}{c}{d}\in\SL_2(\Z)$ such that
$(c,d)\con (u,v)\pmod{N}$.  This is possible 
by Lemma~1.38 of~\cite[pg.~20]{shimura:intro}; in practice,
finding $\abcd{a}{b}{c}{d}$ is not completely trivial, but 
can be accomplished using the extended Euclidean 
algorithm.
Then
 \begin{eqnarray*}
 [X^iY^{k-2-i},(u,v)] &\corrto&
    \abcd{a}{b}{c}{d}(X^iY^{k-2-i}\{ 0,\infty\})\\
    &&= (dX-bY)^i(-cX+aY)^{2-k-i}  
       \left\{\frac{b}{d},\,\frac{a}{c}\right\}.\\
\end{eqnarray*}

In the other direction, suppose that we are given a modular
symbol $P(X,Y)\{\alp,\beta\}$ and wish to represent it as a 
sum of Manin symbols.   Because 
    $$P\{a/b,c/d\} = P\{a/b,0\}+P\{0,c/d\},$$
it suffices to write $P\{0,a/b\}$ in
terms of Manin symbols. 
Let
$$0=\frac{p_{-2}}{q_{-2}} = \frac{0}{1},\,\,
\frac{p_{-1}}{q_{-1}}=\frac{1}{0},\,\,
\frac{p_0}{1}=\frac{p_0}{q_0},\,\,
\frac{p_1}{q_1},\,\,
\frac{p_2}{q_2},\,\ldots,\,\frac{p_r}{q_r}=\frac{a}{b}$$
denote the continued fraction convergents of the 
rational number $a/b$. 
Then
$$p_j q_{j-1} 
  - p_{j-1} q_j = (-1)^{j-1}\qquad \text{for }-1\leq j\leq r.$$
If we let
$g_j = \mtwo{(-1)^{j-1}p_j}{p_{j-1}}{(-1)^{j-1}q_j}{q_{j-1}}$,
then $g_j\in\sltwoz$ and 
\begin{align*}
  P(X,Y)\{0,a/b\}
 &=P(X,Y)\sum_{j=-1}^{r}\left\{\frac{p_{j-1}}{q_{j-1}},\frac{p_j}{q_j}\right\}\\
 &=\sum_{j=-1}^{r} g_j((g_j^{-1}P(X,Y))\{0,\infty\})\\
 &=\sum_{j=-1}^{r} [g_j^{-1}P(X,Y),((-1)^{j-1}q_j,q_{j-1})].
\end{align*}
Note that in the $j$th summand, $g_j^{-1}P(X,Y)$, replaces $P(X,Y)$.
Since $g_j\in\sltwoz$ and $P(X,Y)$ has integer coefficients, 
the polynomial $g_j^{-1}P(X,Y)$ also has integer coefficients,
so no denominators are introduced.

The continued fraction expansion $[c_1,c_2,\ldots,c_n]$
of the rational number $a/b$ can be computed
using the Euclidean algorithm.
The first term, $c_1$, is the ``quotient'': $a = bc_1+r$, 
with $0\leq r < b$. 
Let $a'=b$, $b'=r$ and compute $c_2$ as
$a'=b'c_2+r'$, etc., terminating when the
remainder is $0$.  For example, the expansion
of $5/13$ is $[0,2,1,1,2]$. 
The numbers $$d_i=c_1+\frac{1}{c_2+\frac{1}{c_3+\cdots}}$$
will then be the (finite) convergents.  
For example if $a/b=5/13$, then the convergents are 
  $$0/1,\,\, 1/0,\,\, d_1=0,\,\, d_2=\frac{1}{2},\,\, d_3=\frac{1}{3},\,\,
    d_4=\frac{2}{5},\,\, d_5=\frac{5}{13}.$$



\subsection{Hecke operators on Manin symbols}%
\index{Hecke operators!on Manin symbols}%
\index{Manin symbols!and Hecke operators}%
\label{subsec:heckeonmanin}%
Thoerem~2 of \cite{merel:1585} gives a description of
the Hecke operators~$T_n$
directly  on the space of Manin symbols.
This avoids the expense of first converting a Manin
symbol to a modular symbol, computing~$T_n$ on the modular symbol,
and then converting back.  For the reader's convenience, we very
briefly recall Merel's\index{Merel} theorem here, along with 
an enhancement due to Cremona\index{Cremona}.

As in~\cite[\S2.4]{cremona:algs}, define~$R_p$ as follows.
When $p=2$, 
$$R_2 := \left\{\mtwo{1}{0}{0}{2},
 \mtwo{2}{0}{0}{1}, \mtwo{2}{1}{0}{1},
 \mtwo{1}{0}{1}{2}\right\}.$$
When~$p$ is odd,~$R_p$ is the set of $2\times 2$ integer 
matrices $\abcd{a}{b}{c}{d}$ with determinant~$p$, and either 
\begin{enumerate}
\item $a>|b|>0$, $d>|c|>0$, and $bc<0$; or
\item $b=0$, and $|c|<d/2$; or
\item $c=0$, and $|b|<a/2$. 
\end{enumerate}
\begin{proposition}
For $[P(X,Y),(u,v)]\in\sM_k(N,\eps)$ and~$p$ a prime, we have
\begin{align*}T_p([P(X,Y),(u,v)])
  &= \sum_{g\in R_p} [P(X,Y),(u,v)].g \\
  &= \sum_{\abcd{a}{b}{c}{d}\in R_p} [P(aX+bY,cX+dY),(au+cv,bu+dv)],
\end{align*}
where the sum is restricted to matrices $\abcd{a}{b}{c}{d}$
such that $\gcd(au+cv,bu+dv,N)=1$. 
\end{proposition}
\begin{proof}
For the case $k=2$ and an algorithm to compute $R_p$, 
see \cite[\S2.4]{cremona:algs}.
The general case follows from~\cite[Theorem 2]{merel:1585} applied
to the set~$\sS$ of~\cite[\S3]{merel:1585} by observing that 
when~$p$ is an odd {\em prime} $\sS_p'$ is empty.
\end{proof}

\subsection{The cuspidal and boundary spaces in terms of Manin symbols}%
\index{Manin symbols!and cuspidal subspace}%
\index{Manin symbols!and boundary space}%
\index{Cuspidal modular symbols!and Manin symbols}%
\index{Boundary modular symbols!and Manin symbols}%
This section is a review  of Merel's\index{Merel} explicit description 
of the boundary map in terms of Manin symbols\index{Manin symbols} 
for $\Gamma=\Gamma_1(N)$
(see~\cite[\S1.4]{merel:1585}).  In the next section, we 
describe a very efficient way to compute the boundary map.

Let~$\cR$ be the equivalence relation 
on $\Gamma\backslash\Q^2$ which identifies
the element
$[\Gamma\smallvtwo{\lambda u}{\lambda v}]$
with $\sign(\lambda)^k[\Gamma\smallvtwo{u}{v}]$,
for any $\lambda\in\Q^*$.  Denote by $B_k(\Gamma)$
the finite dimensional $\Q$-vector space
with basis the equivalence classes
$(\Gamma\backslash\Q^2)/\cR$. 
The dimension of this space is $\#(\Gamma\backslash\P^1(\Q))$.
\begin{proposition}
The map
$$\mu:\sB_k(\Gamma)\ra B_k(\Gamma),
\qquad P\left\{\frac{u}{v}\right\}\mapsto
    P(u,v)\left[\Gamma\vtwo{u}{v}\right]$$
is well defined and injective.  
Here $u$ and $v$ are assumed coprime.
\end{proposition}
Thus the kernel of $\delta:\sS_k(\Gamma)\ra \sB_k(\Gamma)$
is the same as the kernel of $\mu\circ \delta$. 
\begin{proposition}\label{prop:boundary}
Let $P\in V_{k-2}$ and $g=\abcd{a}{b}{c}{d}\in\sltwoz$.  We have
$$\mu\circ\delta([P,(c,d)])
      = P(1,0)[\Gamma\smallvtwo{a}{c}]
       -P(0,1)[\Gamma\smallvtwo{b}{d}].$$
\end{proposition}


\subsection{Computing the boundary map}%
\index{Boundary map}%
\label{sec:computeboundary}%
In this section we describe how to compute the 
map $\delta:\sM_k(N,\eps)\ra B_k(N,\eps)$
given in the previous section.  
The algorithm presented here
generalizes the one in~\cite[\S2.2]{cremona:algs}.
To compute the image of $[P,(c,d)]$, with 
$g=\abcd{a}{b}{c}{d}\in\sltwoz$,
we must compute the class of $[\smallvtwo{a}{c}]$ and of 
$[\smallvtwo{b}{d}]$.
Instead of finding a canonical form for cusps, we 
use a quick test for equivalence modulo scalars. 
In the following algorithm, by the $i$th standard 
cusp\index{Cusps!and boundary map} we mean
the $i$th basis vector for a basis of $B_k(N,\eps)$.  The
basis is constructed as the algorithm is called successively.
We first give the algorithm, then prove the facts
used by the algorithm in testing equivalence.

\begin{algorithm}\label{alg:cusplist}
\index{Algorithm for computing!cusps}
Given a cusp $[\smallvtwo{u}{v}]$ this algorithm computes an
integer~$i$ and a scalar~$\alp$ such that $[\smallvtwo{u}{v}]$ is
equivalent to~$\alp$ times the $i$th standard cusp.  First, using
Proposition~\ref{prop:cusp1} and Algorithm~\ref{alg:cusp1}, check
whether or not $[\smallvtwo{u}{v}]$ is equivalent, modulo scalars, to
any cusp found so far.  If so, return the index of the representative
and the scalar.  If not, record $\smallvtwo{u}{v}$ in the
representative list.  Then, using Proposition~\ref{prop:cuspdies},
check whether or not $\smallvtwo{u}{v}$ is forced to equal zero by the
relations.  If it does not equal zero, return its position in the list
and the scalar~$1$.  If it equals zero, return the scalar~$0$ and the
position~$1$; keep $\smallvtwo{u}{v}$ in the list, and record that it
is zero.
\end{algorithm}

In the case considered in Cremona's book \cite{cremona:algs}, the
relations between cusps involve only the trivial character, so they do
not force any cusp classes to vanish.  Cremona gives the following two
criteria for equivalence.
\begin{proposition}[Cremona]\label{prop:cusp1}\index{Cremona}
Let $\smallvtwo{u_i}{v_i}$, $i=1,2$ be written so that
$\gcd(u_i,v_i)=1$.   
\begin{enumerate}
\item There exists $g\in\Gamma_0(N)$ such that 
    $g\smallvtwo{u_1}{v_1}=\smallvtwo{u_2}{v_2}$ if and only if
 $$s_1 v_2 \con s_2 v_1 \pmod{\gcd(v_1 v_2,N)},\,
\text{ where $s_j$ satisfies $u_j s_j\con 1\pmod{v_j}$}.$$
\item There exists $g\in\Gamma_1(N)$ such that 
    $g\smallvtwo{u_1}{v_1}=\smallvtwo{u_2}{v_2}$ if and only if
 $$v_2 \con v_1 \pmod{N}\text{ and } u_2 \con u_1 \pmod{\gcd(v_1,N)}.$$
\end{enumerate}
\end{proposition}
\begin{proof}
The first is Proposition 2.2.3 of \cite{cremona:algs}, and
the second is Lemma 3.2 of \cite{cremona:gammaone}.
\end{proof}

\begin{algorithm}\label{alg:cusp1}%
\index{Algorithm for computing!equivalent cusps}%
Suppose $\smallvtwo{u_1}{v_1}$ and 
$\smallvtwo{u_2}{v_2}$ 
are equivalent modulo $\Gamma_0(N)$. 
This algorithm computes a matrix $g\in\Gamma_0(N)$ such
that $g\smallvtwo{u_1}{v_1}=\smallvtwo{u_2}{v_2}$.
Let $s_1, s_2, r_1, r_2$ be solutions to
$s_1 u_1 -r_1 v_1 =1$ and
$s_2 u_2 -r_2 v_2 =1$.
Find integers $x_0$ and $y_0$ such
that $x_0v_1v_2+y_0N=1$.
Let $x=-x_0(s_1v_2-s_2v_1)/(v_1v_2,N)$
and $s_1' = s_1 + xv_1$. 
Then $g=\mtwo{u_2}{r_2}{v_2}{s_2}
       \cdot \mtwo{u_1}{r_1}{v_1}{s_1'}^{-1}$
sends $\smallvtwo{u_1}{v_1}$ to $\smallvtwo{u_2}{v_2}$.
\end{algorithm}
\begin{proof}
This follows from the proof of Proposition~\ref{prop:cusp1} in
\cite{cremona:algs}.
\end{proof}


To see how the~$\eps$ relations, for nontrivial~$\eps$,
make the situation more complicated, observe that it is 
possible that $\eps(\alp)\neq \eps(\beta)$ but
$$\eps(\alp)\left[\vtwo{u}{v}\right] =\left[\gamma_\alp \vtwo{u}{v}\right]= 
  \left[\gamma_\beta \vtwo{u}{v}\right]=\eps(\beta)\left[\vtwo{u}{v}\right];$$
One way out of this difficulty  is to construct 
the cusp classes for $\Gamma_1(N)$, then quotient
out by the additional~$\eps$ relations using
Gaussian elimination. This is far too
inefficient to be useful in practice because the number of
$\Gamma_1(N)$ cusp classes can be unreasonably large.  
Instead, we give a quick test to determine whether or not
a cusp vanishes modulo the $\eps$-relations.

\begin{lemma}\label{lem:canlift}
Suppose $\alp$ and $\alp'$ are integers
such that $\gcd(\alp,\alp',N)=1$.
Then there exist integers $\beta$ and $\beta'$,
congruent to $\alp$ and $\alp'$ modulo $N$, respectively,
 such that $\gcd(\beta,\beta')=1$.
\end{lemma}
\begin{proof}
By \cite[1.38]{shimura:intro} the map
$\SL_2(\Z)\ra\SL_2(\Z/N\Z)$ is surjective.
By the Euclidean algorithm, there exist
integers $x$, $y$ and $z$ such that
$x\alp + y\alp' + zN = 1$.  
Consider the matrix
$\abcd{y}{-x}{\alp}{\hfill\alp'}\in \SL_2(\Z/N\Z)$
and take $\beta$, $\beta'$ to be the bottom
row of a lift of this matrix to $\SL_2(\Z)$.
\end{proof}

\begin{proposition}\label{prop:cuspdies}\index{Cusps!criterion for vanishing}
Let~$N$ be a positive integer and~$\eps$ a Dirichlet
character\index{Dirichlet character!and cusps} of modulus~$N$. 
Suppose $\smallvtwo{u}{v}$ is a cusp with $u$ and $v$ coprime.
Then $\smallvtwo{u}{v}$ vanishes modulo the relations
$$\left[\gamma\smallvtwo{u}{v}\right]=
\eps(\gamma)\left[\smallvtwo{u}{v}\right],\qquad
\text{all $\gamma\in\Gamma_0(N)$}$$
if and only if there exists $\alp\in(\Z/N\Z)^*$,
with $\eps(\alp)\neq 1$, such that
\begin{align*}
 v &\con \alp v \pmod{N},\\
 u &\con \alp u \pmod{\gcd(v,N)}.
\end{align*}
\end{proposition}
\begin{proof}
First suppose such an~$\alp$ exists.
By Lemma~\ref{lem:canlift}
there exists $\beta, \beta'\in\Z$ lifting
$\alp,\alp^{-1}$ such that $\gcd(\beta,\beta')=1$. 
The cusp $\smallvtwo{\beta u}{\beta' v}$ 
has coprime coordinates so,
by Proposition~\ref{prop:cusp1} and our
congruence conditions on~$\alp$, the cusps
$\smallvtwo{\beta{}u}{\beta'{}v}$ 
and $\smallvtwo{u}{v}$ are equivalent by
an element of $\Gamma_1(N)$.
This implies that $\left[\smallvtwo{\beta{}u}{\beta'{}v}\right]
   =\left[\smallvtwo{u}{v}\right]$.  
Since $\left[\smallvtwo{\beta{}u}{\beta'{}v}\right]
  = \eps(\alp)\left[\smallvtwo{u}{v}\right]$,
our assumption that $\eps(\alp)\neq 1$
forces $\left[\smallvtwo{u}{v}\right]=0$. 

Conversely, suppose $\left[\smallvtwo{u}{v}\right]=0$. 
Because all relations are two-term relations, and the
$\Gamma_1(N)$-relations identify $\Gamma_1(N)$-orbits,
there must exists $\alp$ and $\beta$ with
  $$\left[\gamma_\alp \vtwo{u}{v}\right]
      =\left[\gamma_\beta \vtwo{u}{v}\right]
   \qquad\text{ and }\eps(\alp)\ne \eps(\beta).$$
Indeed, if this did not occur,
then we could mod out by the $\eps$ relations by writing
each $\left[\gamma_\alp \smallvtwo{u}{v} \right]$
in terms of  $\left[\smallvtwo{u}{v}\right]$, and there would
be no further relations left to kill 
$\left[\smallvtwo{u}{v}\right]$.
Next observe that
$$
\left[\gamma_{\beta^{-1}\alp}
      \vtwo{u}{v}\right]
  = \left[\gamma_{\beta^{-1}}\gamma_\alp
      \vtwo{u}{v}\right]
 = \eps(\beta^{-1})\left[\gamma_\alp
      \vtwo{u}{v}\right]
 = \eps(\beta^{-1})\left[\gamma_\beta
      \vtwo{u}{v}\right]
 = \left[\vtwo{u}{v}\right].$$
Applying Proposition~\ref{prop:cusp1} and
noting that $\eps(\beta^{-1}\alp)\neq 1$ shows 
that $\beta^{-1}\alp$ satisfies the properties
of the ``$\alp$'' in the statement of the 
proposition we are proving.
\end{proof}

We enumerate the possible~$\alp$ appearing 
in Proposition~\ref{prop:cuspdies} as follows. 
Let $g=(v,N)$ and list the
$\alp=v\cdot\frac{N}{g}\cdot{}a+1$, for $a=0,\ldots,g-1$,
such that $\eps(\alp)\neq 0$. 

{\vspace{3ex}\em\par\noindent Working in the 
plus one\index{Plus-one quotient} or 
minus one quotient\index{Minus-one quotient}.}
Let~$s$ be a sign, either~$+1$ or~$-1$.
To compute $\sS_k(N,\eps)_s$ it is necessary
to replace $B_k(N,\eps)$ by its quotient modulo the
additional relations 
$\left[ \smallvtwo{-u}{\hfill v}\right] 
= s \left[\smallvtwo{u}{v}\right]$
for all cusps $\smallvtwo{u}{v}$. 
Algorithm~\ref{alg:cusplist} can be modified to deal
with this situation as follows. 
Given a cusp $x=\smallvtwo{u}{v}$, proceed as
in Algorithm~\ref{alg:cusplist} and check if 
either $\smallvtwo{u}{v}$ or $\smallvtwo{-u}{\hfill v}$
is equivalent (modulo scalars) to any cusp seen so far.  If not, 
use the following trick to determine whether 
the $\eps$ and $s$-relations
kill the class of $\smallvtwo{u}{v}$:
use the unmodified Algorithm~\ref{alg:cusplist} 
to compute the scalars $\alp_1, \alp_2$ and 
standard indices $i_1$, $i_2$ associated to
$\smallvtwo{u}{v}$ and $\smallvtwo{-u}{\hfill v}$, respectively.
The $s$-relation kills the class of  $\smallvtwo{u}{v}$
if and only if $i_1=i_2$ but $\alp_1\neq s\alp_2$. 


\section{The complex torus attached to a modular form}%
\index{Complex torus}%
\index{Modular forms!associated complex torus}%
\label{sec:tori}%
Fix integers $N\geq 1$, $k\geq 2$, and let~$\eps$ be a mod~$N$
Dirichlet character\index{Dirichlet character}.  
For the rest of this section assume that $\eps^2=1$. 

We construct a lattice in $\Hom(S_k(N,\eps),\C)$ that is invariant
under complex conjugation and under the action of the Hecke
operators.\index{Hecke operators} The quotient of
$\Hom(S_k(N,\eps),\C)$ by this lattice is a complex torus
$J_k(N,\eps)$, which is equipped with an action of the Hecke operators
and of complex conjugation.

The reader may wish to compare our construction with a closely related
construction of Shimura\index{Shimura}~\cite{shimura:surles}.  Shimura
observes that the Petersson pairing\index{Petersson pairing} gives his
torus the structure of an abelian variety over~$\C$.  Note that his
torus is, a priori, different than our torus.  We do not know if 
our torus has the structure of abelian variety over~$\C$.

When $k=2$, the torus $J_2(N,\eps)$ is the set of complex points of an
abelian variety, which is actually defined over $\Q$; when $k>2$, 
the study of these complex tori is of interest in trying to understand the
conjectures of Bloch and Kato (see \cite{bloch-kato})%
\index{Conjecture!Bloch and Kato}%
\index{Bloch and Kato conjecture} on motifs\index{Motifs} attached 
to modular forms\index{Modular forms}.

Let $\sS=\sS_k(N,\eps)$ (respectively, $S=S_k(N,\eps)$)
be the space of cuspidal modular symbols (respectively, cusp forms)
of weight~$k$, level~$N$, and character~$\eps$.
The Hecke algebra~$\T$\index{Hecke algebra!and integration pairing} 
acts in a way compatible with the 
integration pairing\index{Integration pairing!and complex torus}
$\langle\,,\,\rangle
 : S \cross \sS \ra \C$.
This pairing induces a $\T$-module 
homomorphism $\Phi:\sS\ra S^*=\Hom_\C(S,\C)$,
called the \defn{period mapping}.%
\index{Period mapping|textit}
Because $\eps^2=1$, the $*$-involution\index{Star involution} preserves~$S$.
\begin{proposition}
The period mapping~$\Phi$\index{Period mapping!is injective} 
is injective and $\Phi(\sS)$ is a lattice in~$S^*$. 
\end{proposition}
\begin{proof}
By Theorem~\ref{thm:perfectpairing},
 $$\sS\tensor_{\R}\C\isom 
   \Hom_\C(S\oplus \Sbar,\C).$$
Because $\eps^2=1$, we have $S = S_k(N,\eps;\R)\tensor_{\R}\C$. 
Set $S_\R := S_k(N,\eps;\R)$ and likewise define $\Sbar_\R$.
We have
$$\Hom_\C(S\oplus \Sbar,\C) = 
    \Hom_\R(S_\R \oplus \Sbar_\R,\R)\tensor_\R \C.$$
Let $\sS_{\R} = \sS_k(N,\eps;\R)$ and $\sS_{\R}^+$ be the
subspace fixed under~$*$.  By Proposition~\ref{prop:starpairing}
we have maps
$$\sS_{\R}^+ \ra \Hom_{\R}(S_{\R}\oplus\Sbar_\R,\R)
             \ra \Hom_{\R}(S_{\R},\R)$$
and
$$\sS_{\R}^- \ra \Hom_{\R}(S_{\R}\oplus\Sbar_\R,i\R)
             \ra \Hom_{\R}(S_{\R},i\R).$$
The map $\sS_{\R}^+\ra \Hom_{\R}(S_{\R},\R)$ is
an isomorphism: the point is that if
$\langle \bullet, x\rangle$, for $x\in \sS_{\R}^+$, 
vanishes on $S_\R$ then it  vanishes on  the 
whole of $S\oplus \Sbar$.  Likewise, the map
$\sS_{\R}^-\ra \Hom_{\R}(S_{\R},i\R)$
is an isomorphism.  Thus
$$\sS\tensor\R = \sS_{\R} \isom \Hom_{\R}(S_{\R},\R)
\oplus \Hom_{\R}(S_{\R},i\R) 
\isom \Hom_{\C}(S,\C).$$
Finally, we observe that~$\sS$ is by definition
torsion free, which completes the proof.
\end{proof}

The torus $J_k(N,\eps)$ fits into an exact sequence
$$0\lra \sS \xrightarrow{\quad\Phi\quad}
        \Hom_\C(S,\C) \lra J_k(N,\eps) \lra 0.$$
Let $f\in S$ be a newform and $S_f$ the complex vector
space spanned by the Galois conjugates of~$f$.
The period map $\Phi_f$ associated to~$f$ is the map 
$\sS\ra \Hom_\C(S_f,\C)$
obtained by composing~$\Phi$ with restriction to $S_f$.
Set
  $$A_f := \Hom_\C(S_f,\C) / \Phi_f(\sS).$$

We associate\label{pg:dual} to~$f$ a subtorus of~$J$ as follows.
\index{Complex torus!dual of}%
\index{Modular forms!associated subtorus}%
Let $I_f = \Ann_{\T}(f)$ be the annihilator
of~$f$ in the Hecke algebra\index{Hecke algebra}, and set
    $$\Adual_f := \Hom_\C(S,\C)[I_f]/\Phi(\sS[I_f])$$
where $\Hom_\C(S,\C)[I_f] = \intersect_{t \in I_f} \ker(t)$.

The following diagram summarizes the tori just defined;
its columns are exact but its rows need not be.
\begin{equation}\label{dgm:uniformization}
\xymatrix@=.9pc{
    0\ar[d]            &        0\ar[d]             &  0\ar[d]   \\
  \sS[I_f]\ar[r]\ar[dd] &  \sS\ar[r]\ar[dd]&\Phi_f(\sS)\ar[dd] \\
                      &                 &      \\
\Hom_\C(S,\C)[I_f]\ar[r]\ar[dd] &\Hom_\C(S,\C)\ar[r]\ar[dd] &\Hom_\C(S[I_f],\C)\ar[dd]\\
                      &                 &      \\
  {\Adual_f}\ar[r]\ar[d]
& J_k(N,\eps) \ar[r]\ar[d]& A_f \ar[d]\\
    0   &   0    &  0   \\
}\end{equation}


\subsection{The case when the weight is $2$}%
\index{Complex torus!in weight two}%
When $k=2$ and $\eps=1$ the above is just Shimura's\index{Shimura}
classical association of an abelian variety to a modular
form\index{Modular forms}; see~\cite[Thm.~7.14]{shimura:intro}
and~\cite{shimura:factors}.  In this case $A_f$ and $\Adual_f$ are
abelian varieties that are defined over~$\Q$.  Furthermore $A_f$ is an
\defn{optimal quotient}\index{Optimal quotient|textit} of~$J$, in the sense
that the kernel of the map $J\ra A_f$ is connected.
For a summary of the main results in this situation, 
see Section~\ref{sec:optquoj0n}.