Sharedwww / Tables / modsymbols.texOpen in CoCalc
% modsymbols.tex

\title{Manin symbols and modular forms\\{\large (first draft)}}
\author{W. Stein\footnote{UC Berkeley, Department of Mathematics, Berkeley, CA  94720, USA.}}
``The object of numerical computation is theoretical advance.''

-- Atkin

The definition of the
spaces $S_k(\Gamma)$ of modular forms as functions on the upper half
plane $\h$ satisfying a certain equation is very abstract.
The definition of the Hecke operators even more so.  

We are fortunate that we now have methods available which allow us 
to transform the vector space of cusp forms of given weight $\geq 2$
and level $N$ into a concrete object, which can be
explicitely computed.  We have the work
of Atkin-Lehner, Birch-Swinnerton-Dyer, 
Cremona, Manin, Mazur, Merel, and many others 
to thank for this.

The Eichler-Selberg trace formulas, as developed in \cite{hijikata} and \cite{wada},
can be used to compute characteristic polynomials of Hecke operators and hence
gain some information about spaces of modular forms. 
It is also sometimes possible to write down explicit basis in terms of 
$\Theta$-series and to compute the action of Hecke operators on their $q$-expansions. 
Other methods include computing the Hecke operators and $q$-expansions
using Brandt matrices and quaternion algebras as in \cite{pizer} 
or \cite{kohel}, or the module of supersingular points in 
``characteristic $N$'' as  exploited by Mestre and Oesterle in \cite{mestre}.

Though the above methods are each beautiful and well suited to certain applications, 
we will not discuss them further here.  Instead we focus
on the modular symbols method, as it also has many advantages.  We will only 
discusss the theory in this summary paper, leaving an explicit description
of the objects involved for later.  Nonetheless there is a definite
gap between the {\em theory} on the one hand, and an efficient running 
machine implimentation on the other.  To impliment the algorithms
hinted at below requires making absolutely everything completely explnicit
and then finding intelligent and efficient ways of performing the
necessary manipulations.  This is a nontrivial and tedious task, with
room for error at every step. 

Our exposition follows very closely that of \cite{merel}. 

Let $\Gamma$ be a finite index subgroup of $\sltwoz$ and
$k\geq 2$ an integer. If $k$ is odd, assume $-1\not\in\Gamma$,
so that the modular forms theory is nonempty. 
Let $\P^1(\Q) = \Q\union\{\infty\}$.

\section{Modular symbols and modular forms}
\subsection{Modular symbols}
Let $\M$ be the $\Z$-module generated by formal symbols
$\{\alpha,\beta\}$, $\alpha, \beta\in\P^1(\Q)$, subject
to the relations
Thus $\{\alpha,\beta\}=-\{\beta,\alpha\}$ 
and $\{\alpha,\alpha\}=0$. There is a left action
of $g\in\gltwoq$ given by

\comment{% This map has no good properties, so far as I can see!
There is a natural  homomorphism
$$\cD_0\into\M:\quad \alp\mapsto \{0,\alp\}$$
By Manin's trick Lemma~\ref{maninstrick} this map is surjective,
[and I think the relations defining $\M$ exactly make
it injective].

Let $$V_k=\Sym^{k-2}_\Z(\Z\cross\Z)=\Z_{k-2}[X,Y]$$ be the
free $\Z$-module of homogeneous polynomimals in two variables
of degree $k-2$. 
There is a {\em left} action of $g=\abcd{a}{b}{c}{d}\in\mtwoz$ 
given by $$g.P(X,Y) = P(\det(g)g^{-1}(X,Y)) = P(dX-bY,-cX+aY).$$
%Note that $g$ induces an automorphism of the algebra
%$\Z[X,Y]$ which restricts to a linear endomorphism
%of each homogeneous piece, and that
The space
$$\M_k := V_k\tensor_\Z \M.$$
is equipped with a left action of $\mtwoz$ given by
$$g.(P\tensor x)
  =g.P\tensor g.x.$$
%Note that $\M_k$ is {\em not} $V_k\tensor_{\Z[\mtwoz]}\M_k$
%with its induced action. 
Let $$\M_k(\Gamma):=H_0(\Gamma,\M_k)$$ be the zeroth homology group.
Thus $\M_k(\Gamma)$ is the quotient of $\M_k$ by the relations
$g.x=x$ for all $x\in\M_k$ and $g\in\Gamma$. 
The elements of $\M_k(\Gamma)$ are called
{\em modular symbols of weight $k$ for $\Gamma$}.
As we will see later, using Shapiro's lemma and an explicit computation,
$$\M_k(\Gamma)\tensor\C\isom H^1(\Gamma,V_k\tensor\C).$$
The theory of Eichler and Shimura embeds modular forms
in $H^1(\Gamma,V_k\tensor\C)$. 

\subsection{Manin symbols}
Let $e=\{0,\infty\}\in\M$. 

\comment{Note furthermore that $\psltwoz=\sltwoz/\{\pm 1\}$
is the free product of the
cyclic group of order $2$ generated by $S$ and the cyclic group of order
$3$ generated by $\tau$.}

\begin{proposition}[Manin's trick]~\label{maninstrick}
The elements $g.e$ for $g\in\sltwoz$ generate $\M$. 
(From \cite{cremona1}.) Writing $\{\alpha,\beta\}=\{0,\beta\}-\{0,\alp\}$,
it suffices to show that every symbol of the form
$\{0,\alp\}$ is in the group generated by
the $g.e$.   Let
$$\frac{p_{-2}}{q_{-2}} = \frac{0}{1},\,
denote the continued fraction convergents of the rational number $\alp$. 
$$p_j q_{j-1} - p_{j-1} q_j = (-1)^{j-1}\qquad \text{for }-1\leq j\leq r.$$
 = \sum_{j=-1}^{r}g_j.e$$
$g_j = \mtwo{(-1)^{j-1}p_j}{p_{j-1}}{(-1)^{j-1}q_j}{q_{j-1}}$.

To a pair $g\in\sltwoz$ and $P\in V_k$ define 
the {\em Manin symbol} 
$$[P,g]=g.(P\tensor e)\in\M_k(\Gamma).$$

The matrices
$$\sigma=\mtwo{0}{-1}{1}{0}\quad \text{and} \quad \tau=\mtwo{0}{-1}{1}{-1}$$
and generate $\sltwoz$.

Let $g\in\sltwoz$ and $P\in V_k$. The symbol
$[P,g]$ depends only on $P$ and the class $\Gamma g$.  When
$g$ runs through $\sltwoz$ and $P$ runs through $V_k$,
the Manin symbols generate $\M_k(\Gamma)$ ({\em maybe}, at
least this should be true after tensoring with $\Q$).
Furthermore, they satisfy
\mbox{}[P,g]+[\tau^{-1}P,g\tau]+[\tau^{-2}P,g\tau^2]&=&0, \\
The first assertion follows from the construction of $\M_k(\Gamma)$. 
The correct version of the second assertion 
(should somehow) follow from Lemma~\ref{maninstrick}.
For the third assertion note the following relations:
 e + \sigma(e) &=& \{0,\infty\}
        + \{\sigma(0),\sigma(\infty)\}\\
e+\tau(e)+\tau^2(e) &=& 
           \{0,\infty\} + \{\tau(0),\tau(\infty)\}
                      + \{\tau^2(0),\tau^2(\infty)\}\\
          &=& \{0,\infty\} + \{1,0\} + \{\infty,1\} = 0.
\mbox{}[P,g]+[\sigma^{-1}P,g\sigma] &=& 
            g(P\tensor e) + g\sigma(\sigma^{-1}P\tensor e)\\
    &=& gP\tensor e + gP\tensor g\sigma e\\
    &=& gP\tensor g(e+\sigma(e)) = 0,\\
        g(P\tensor e) + g\tau(\tau^{-1}P\tensor e) + g\tau^2(\tau^{-2}P\tensor e) \\
&=& gP\tensor g(e+\tau(e)+\tau^2(e)) = 0.

The above relations generate all relations satisfied by the Manin symbols.
(Maybe one must tensor with $\Q$.)
Not only do not know whether or not this is true before tensoring with $\Q$,
I do not know how to prove this. 

%Note that the relation $[P,g]=[j^{-1}P,gj]$ is imposed
%by repeated application of the $\sigma$ relation because $\sigma^2=j$. 

The Manin symbol $[P,g]$ can be written as $\Z$-linear combinations of
Manin symbols $$[X^q Y^{k-2-q},g],\quad \text{with } 0 \leq q \leq k-2.$$  Since
$[\sltwoz:\Gamma]$ is finite, $\M_k(\Gamma)$ is a finitely
generated abelian group.   In particular, we can write down an 
explicit basis which is then readily amenable to machine computation.  
We write $[X^q Y^{k-2-q},g]=[q,g]$ to simplify notation. 
Let $g_1,\ldots,g_n$ be a set of coset representatives for
$\Gamma$ in $\sltwoz$.  Then $\M_k(\Gamma)$ is generated by
$$\{[q,a_i] : 0\leq q\leq k-2, \, 1\leq i\leq n\}$$
subject to the relations given by Proposition~\ref{maninsymbols}.

Note that $\M_k(\Gamma)$ may contain nontrivial torsion, which is
not well understood (by me!). 

% what is the torsion?

\subsection{Cuspidal modular symbols}

%About my paper "Universal...", there are a few mistakes there
%(one reason other than my own fault, is the fact that that I never
%saw the proofs). Some of them are insignificant. One you have to
%be careful about is the fact that  the parameterization of the cusps
%of X_1(N) is wrong. It is easy to fix it anyway. One should replace
%the set I called P_N by the disjoint union of the (Z/gcd(d,N)Z)^* where
%d runs through Z/NZ. Then everything works mutatis mutandis.             
In this section we assume $k$ is even.  There is a similar definition
when $k$ is odd. 

Let $\cD_0=\Div^0(\P^1(\Q))$ be the group of divisors
of degree zero supported on $\P^1(\Q)$ and note that
$\gltwoq$ acts on $\cD_0$ on the left by linear
fractional transformations.

Let $\cC(\Gamma)=H_0(\Gamma)=H_0(\Gamma,\cD_0)$ be the zeroth
homology of $\Gamma\subset\sltwoz$ acting on $\cD_0=\Div^0(\P^1(\Q))$,
so $H_0(\Gamma)$ is the free abelian group generated 
by the set of orbits $\Gamma\backslash P^1(\Q)$.  It is the free abelian group on the 
cusps of the modular curve $X({\Gamma})$.  There is a map 
$\M_k(\Gamma)\into\cC(\Gamma)$ which on Manin symbols is
$$[P,g]\mapsto P(1,0)[g(\infty)]-P(0,1)[g(0)].$$
Let $\cS_k(\Gamma)$ be the kernel of this map. 

\subsection{Duality between modular symbols and modular forms}
\subsubsection{Weight 2}
The first homology group $H_1(X_{\Gamma},\Z)$ of the modular curve
$X_{\Gamma}$, viewed as a real $2$-manifold, is a free abelian group 
of rank $2g$, where $g$ is the genus of $X_{\Gamma}$. 
The global differentials $\Omega(X) = H^0(X,\Omega)$ 
on $X_{\Gamma}$, now viewed as a Riemann surface, form a 
$g$ dimensional complex vector space.  It is equal to the
complex vector space $S_2(\Gamma)$ of cusp forms. 
There is a nondegenerate pairing
H_1(X_{\Gamma},\Z)\tensor \Omega(X)&\ra& \C\\
\langle \gamma, \omega \rangle &\mapsto& \int_{\gamma} \omega.
Taking coefficients in $\R$ we have
Extending the above pairing gives 
a natural injection of $H_1(X_{\Gamma},\R)$ 
into the dual space of $\Omega(X)$.  Since the
two spaces have the same real dimension, this injection
must be an isomorphism.  

Suppose now that $k=2$.  We can identify modular symbols
$\{\alp,\beta\}$ for $\Gamma$ as elements of 
$H_1(X_{\Gamma},\R)$, and we have the formula,
$$\langle \{\alp,\beta\}, \omega\rangle
     = \int_{\alp}^{\beta} \omega.$$
In fact, modular symbols were first introduced in this way 
by Birch in \cite{birch} in his work 
with Swinnerton-Dyer on the special value at $s=1$ of
the $L$-function associated to a (modular) elliptic curve. 

\subsubsection{Higher weight}
The duality generalizes to higher weight. 
Let $f:\h\into\C$ be a map.  For $g=\abcd{a}{b}{c}{d}\in\gltwoq$ and $z\in\h$,
f|[g]_k(z)&=&(cz+d)^{-k} f(gz)(\det g)^{k-1}\\
f|[\overline{g}]_k(z)&=&(c\overline{z}+d)^{-k} f(gz)(\det g)^{k-1}
We denote by $S_k(\Gamma)$ (resp. $\overline{S_k(\Gamma)}$) the complex
vector space of holomorphic (resp. antiholomorphic) cusp forms of
weight $k$ for $\Gamma$.   There is a canonical isomorphism of 
real vector spaces between $S_k(\Gamma)$ and $\overline{S_k(\Gamma)}$
which associates to $f$ the antiholomorphic modular form 
$z\mapsto \overline{f(z)}$. 

There is a pairing 
$$(S_k(\Gamma)\oplus \overline{S_k(\Gamma)})\cross \M_k(\Gamma)\into\C$$
given by the rule
$$\langle f_1+f_2,P\tensor\{\alpha,\beta\}\rangle
   = \int_{\alp}^{\beta} f_1(z)P(z,1)dz 
    + \int_{\alp}^{\beta} f_2(z)P(\overline{z},1)dz $$
where $f_1\in S_k(\Gamma)$ and $f_2\in \overline{S_k(\Gamma)}$. 

The following pairing, obtained from the above one, 
is nondegenerate:
$$(S_k(\Gamma)\oplus\overline{S_k(\Gamma)})\cross \cS_k(\Gamma)
\into \C.$$

\subsection{Complex conjugation}
Let $\eta=\abcd{-1}{0}{0}{1}$ and $\tilde{\eta}=\abcd{1}{0}{0}{-1}$. 
Assume in this section that  $\eta^{-1}\Gamma\eta=\Gamma$. 
\begin{proposition} The map $\iota$ which associates to 
$f\in S_k(\Gamma)\oplus\overline{ S_k(\Gamma)}$ the
function $z\mapsto f(-\overline{z})$ is a complex
linear involution of $S_k(\Gamma)\oplus\overline{ S_k(\Gamma)}$
which exchanges $S_k(\Gamma)$ and $\overline{ S_k(\Gamma)}$. 
Define an involution $\iota^{\star}$ on $\M_k(\Gamma)$ by
$$\iota^{\star}(P\tensor x)= -\tilde{\eta}P\tensor\eta x.$$
This involution is adjoint to $\iota$ with respect to
the pairing of Theorem~\ref{pairing}.  Moreover $\iota^{\star}$
acts as follows on Manin symbols
$$\iota^{\star}([P,g]) = -[\tilde{\eta}P,\eta g \eta^{-1}].$$
Let $\cS_k(\Gamma)^{+}$ denote the subspace of elements
of $\cS_k(\Gamma)$ fixed by $\iota^{\star}$. 
The bilinear pairing induced by the pairing $\langle . , . \rangle$
$$S_k(\Gamma)\cross \cS_k(\Gamma)^{+}\into\C$$
is nondegenerate.

Eichler and Shimura found a way to embed 
modular forms into a cohomology group. 
There is also a way to embed modular symbols into the same cohomology

The complex
vector space $V_k\tensor_{\Gamma} \sltwoz$ is endowed
with a {\em right} action of $\sltwoz$ given by the formula
$$(P\tensor g).\gamma = (\gamma^{-1}P)\tensor (g\gamma).$$
We have an isomorphism of complex vector spaces
$$H^1(\sltwoz,V_k\tensor_{\Gamma} \sltwoz\tensor\C)\isom\M_k(\Gamma)\tensor\C.$$
This is Proposition 9 of \cite{merel}.
The proof involves explicit computations with cocycles using the fact that
$\sltwoz$ is generated by $\sigma$ and $\tau$.

It might be possible to replace tensoring with $\C$ by something
less severe.

Let $H$ be a subgroup of a group $G$ and let $A$ be a $\Z[H]$-module.
$$H^q(G,\Hom_H(\Z[G],A))=H^q(H,A)\qquad\text{for all $q\geq 0$}.$$

There is an isomorphism
$$\M_k(\Gamma)\tensor\C \isom H^1(\Gamma, V_k\tensor\C).$$
Since $\Gamma$ has finite index in $\sltwoz$ there is an isomorphism
      \isom V_k\tensor_{\Gamma} \sltwoz\tensor\C.$$
Now apply Shapiro's lemma.

Define the {\em parabolic} cohomology group $H^1_P$ by the exactness
of the following sequence
$$0\into H^1_P(\Gamma,V_k\tensor \C) \into
       H^1(\Gamma,V_k\tensor\C) \into
     \bigoplus_{\text{cusps $\alp$}} H^1(\Gamma_{\alp},V_k\tensor\C)$$
where $\Gamma_{\alp}$ is the stabilizer in $\Gamma$ of the cusp $\alp$
of $X_{\Gamma}$. 

For $f\in M_k(\Gamma)$ define a class in $H^1(\Gamma,V_k\tensor\C)$
by the cocycle
$$\gamma\mapsto \int_{z_0}^{\gamma(z_0)} f(z) 
Here $z_0$ is a basepoint, $v^{k-2}$ denotes the image
of $v\tensor\cdots\tensor v$ in $\Sym^{k-2}(\C\cross\C)$
and the integral is that of a vector-valued differential.
There is a similiar construction for holomorphic

The map above gives rise to isomorphisms
M_k(\Gamma)\oplus\overline{S_k(\Gamma)}&\into &H^1(\Gamma,V_k\tensor \C)\\
S_k(\Gamma)\oplus\overline{S_k(\Gamma)}&\into &H^1_P(\Gamma,V_k\tensor \C).

% put Hijikata trace formula for the case $N=1$ here.
\section{Linear maps}

\subsection{Linear operators}
Let $\Delta\subset\mtwoz$ such that 
$\Gamma\Delta\Gamma=\Delta$ and such that
$\Gamma\backslash\Delta$ is finite. Note
that $\Delta$ is a union of double cosets
of $\Gamma\backslash\mtwoz/\Gamma$.  Let
$R$ be a set of representatives of $\Gamma\backslash\Delta$.

Two examples are $\Gamma=\Gamma_1(N)$ with
$$\Delta = \Delta_1(N) = \{\abcd{a}{b}{c}{d}\in M_2(\Z)
  : \det > 0, \,\,c\con a-1\con 0\pmod {N}\},$$
and $\Gamma=\Gamma_0(N)$ with
$$\Delta = \Delta_0(N) = \{\abcd{a}{b}{c}{d}\in M_2(\Z)
  : \det > 0,\,\, c\con 0\pmod {N}, \,(a,N)=1\}.$$

Define the {\em Hecke ring} $R(\Gamma,\Delta)$ as follows. 
It is the free $\Z$-module generated by the double cosets 
$\Gamma\alp\Gamma$, $\alp\in\Delta$.  Define multiplication
between two double cosets $u=\Gamma\alp\Gamma$ and
$v=\Gamma\beta\Gamma$ as follows.  Consider their coset decompositions
$\Gamma\alp\Gamma = \coprod_{i}\Gamma\alpha_i$
and $\Gamma\beta\Gamma = \coprod_{i}\Gamma\beta_i$.
Then $\Gamma\alp\Gamma\beta\Gamma=\union_{i,j}\Gamma\alp_i\beta_j$
(not necessarily disjoint), and so $\Gamma\alp\Gamma\beta\Gamma$
is a finite union of double cosets of the form $\Gamma\gamma\Gamma$.
$$u\cdot v = \sum_{w} m(u,v;w)w$$
where the sum is extended over all double cosets 
$w=\Gamma\gamma\Gamma\subset\Gamma\alp\Gamma\beta\Gamma$, and
$$m(u,v;w)=\#\{(i,j) : \Gamma\alp_i\beta_j = \Gamma\gamma\}$$
for $w=\Gamma\gamma\Gamma$.  Thus equipped,
$R(\Gamma,\Delta)$ becomes an associate, and in fact commutative,
ring with $\Gamma=\Gamma\cdot 1\cdot\Gamma$ as the unit element.
\subsubsection{Action on modular forms}
Let $M_k(\Gamma)$ be the space of modular forms of weight $k$ for $\Gamma$.
For $f\in M_k(\Gamma)$, define an operator $T_{\Delta}$ by
$$T_\Delta(f) = \sum_{\alp\in R} f|[\alp]_k$$
This is a well-defined linear action 
on $M_k(\Gamma)$ which preserves the subspace $S_k(\Gamma)$. 

\subsubsection{Action on modular symbols}
Similiarly, define an operator $T_{\Delta}$ on the
space $\M_k(\Gamma)$ of modular symbols by
$$T_\Delta(x) = \sum_{\alp\in R} \alp.x.$$

\subsubsection{Hecke operators}
Suppose now that $\Gamma=\Gamma_1(N)$.  Let $n\geq 1$ be an
integer and set
$$\Delta_n=\{\abcd{a}{b}{c}{d}\in M_2(\Z) : 
   \det = n,\,N|c,\, N|(a-1)\}.$$
Then the $n$th {\em Hecke operator} is $T_{\Delta_n}$. 
If $\Gamma=\Gamma_0(N)$ the condition that $N|(a-1)$ is relaxed to

\subsection{Action on Manin symbols}
We now describe how to explicitely compute the action of the 
Hecke operators on $\M_k(\Gamma)$.
Recall, we have an explicit ``generators and relations''
description of $\M_k(\Gamma)$ in terms of Manin symbols. 
The action of the Hecke operators (and other linear operators)
described in the previous section is given in terms of 
modular symbols.  We {\em could} describe the action of
an operator on a Manin symbol by taking the Manin symbol,
finding the corresponding modular symbol, acting by the
operator, and then converting back to a sum of Manin symbols.
This process is painfully inefficient as it involves repeated
application of Proposition~\ref{maninstrick}.  This was
how computations were originally done until Mazur and Merel
described the action of the Hecke operators directly in terms
of Manin symbols. 

Let $n>0$ be an integer.  We denote by $\mtwoz_n$ the set of 
matrices of $\mtwoz$ of determinant $n$. 

\begin{definition}[Condition (M)]
We say that an element $\sum_{g} a_g g\in\C[\mtwoz_n]$
satisfies condition (M) if for all cosets
$\cC\in \mtwoz_n/\sltwoz$, we have in $\C[\P^1(\Q)]$,
$$\sum_{g\in \cC} a_g ([g(\infty)] - [g(0)]) = [\infty]-[0].$$
Note that the condition (M) depends neither on the level
or the weight. 

Suppose now that $\Gamma=\Gamma_1(N)$ (or $\Gamma_0(N)$). 
There is a bijection between
cosets $\Gamma\backslash\sltwoz$ and pairs of integers 
$(u,v)$ satisfying a certain equivalence.  The bijection associates
to a $2\times 2$ matrix its bottom two entries.  We may thus view
the Manin symbols as pairs $[P,(u,v)]$. 

Let $[P,(u,v)]$ be a Manin symbol. Suppose $\sum_{g} a_g g\in\C[\mtwoz_n]$
satisfies condition (M).  Then we have 
$$T_n([P(X,Y),(u,v)]) = \sum_{g=\abcd{a}{b}{c}{d}\in\mtwoz_n} 
     a_g [P(aX+bY,cX+dY),(au+cv,bu+dv)]$$
where the sum is restricted to the matrices $g$ such that 
$\gcd(au+cv,bu+dv)=1$ (if $(n,N)=1$ this restriction is
See section 2 of \cite{merel}.

The element $\sum_{g \in\mtwoz_n} g \in \C[\mtwoz_n]$
satisfies condition (M).  In Merel's paper one can find other families of simpler
(more sparse) elements satisfying condition (M).

For one of the families $S_n$ there is an
asymptotic formula for the number $|S_n|$ of nonzero summands:
$$|S_n| \sim  \frac{12\log 2}{\pi^2} \sigma(n)\log n, \quad\text{as $n\ra\infty$}$$
where $\sigma(n)$ is the sum of the positive divisors of $n$. 
Let $s(n)$ be the right hand side, rounded down to the nearest integer.  Then
$$s(10)=34,\quad  s(100)=842,\quad  s(250)=2177,\quad   
         s(500)=5719,\quad    s(1000)=13622.$$
Finding a family minimizing these numbers is extremely important in
computing many Hecke eigenvalues. 

Cremona has improved on this slightly to give even simpler 
elements $\mathcal{X}_n\in\C[\mtwoz_n]$ which can be used to compute
the Hecke action, but which I don't think satisfies condition (M). 
He proves this in his book for weight $2$, but I think his elements 
work for any positive weight.
%\subsection{Atkin-Lehner operators}
Let $N$ be a positive integer and let 
$\chi:(\Z/N\Z)^{\star}\into\C^{\star}$ be 
a character. Let $\Z[\chi]=\Z[\chi(\Z/N\Z)^{\star}]$. 
Define $\M_k(N,\chi)$ to be the quotient of
$\M_k(\Gamma_1(N))\tensor\Z[\chi]$ by the equivalence relation
which identifies the Manin symbol
$[P,(\lambda u,\lambda v)]$ with $\chi(\lambda)[P,(u,v)]$. 
Define $\S_k(N,\chi)\subset \M_k(N,\chi)$. 
The pairing
$$(S_k(N,\chi)\sum\overline{ S_k(N,\chi)} \cross
   \cS_k(N,\chi)\into \C$$
is nondegenerate.
Thus the space $\S_k(N,\chi)\tensor\C$ obtained from modular symbols
is related to the cusp forms $S_k(N,\chi)$. 

\subsection{Coset representatives~\label{cosetrep}}
For $j=1,2$, let $g_j=\abcd{a_j}{b_j}{c_j}{d_j}\in\sltwoz$. 
The following are equivalent.
\item The right cosets $\Gamma_0(N)g_1$ and 
$\Gamma_0(N) g_2$ are equal,
\item $c_1d_2\con c_2 d_1\pmod{N}$,
\item There exists $u\in(\Z/N\Z)^{\star}$ such that
$c_1\con u c_2$ and $d_1\con u d_2$  $\pmod{N}$. 
Proposition 2.2.1 of \cite{cremona1}.

For $j=1,2$, let $\alp_j=p_j/q_j$ be cusps written in lowest terms.
The following are equivalent:
\item $\alp_2=g\alp_1$ for some $g\in\Gamma_0(N)$,
\item $q_2\con u q_1\pmod{N}$ and $up_2\con p_1\pmod{\gcd(q_1,N)}$,
with $\gcd(u,N)=1$,
\item $s_1 q_2\con s_2 q_1\pmod{gcd(q_1 q_2,N)}$, where
$s_j$ satisfies $p_j s_j \con 1\pmod {q_j}$. 
Proposition 2.2.3 of \cite{cremona1}.

%\subsection{Cusp equivalence}
%\subsection{Computing Hecke eigenvalues}

%\subsection{Computing $L^{(r)}(f,1)$}
%\section{Computing in characteristic $p$}
%\section{Equations for modular curves}
%\section{Congruences between newforms}
%\subsection{Coset representatives}
%\subsection{Linear algebra}

%\subsection{Level $37$}

\section{Generating $H_1(\Gamma,\Z)$}
How can we generate $H_1(\Gamma,\Z)$ using modular symbols?  
Choose any $\alp\in\Q\union\{\infty\}$, it doesn't
matter which.  Then the map
$$\Gamma\ra H_1(\Gamma,\Z): \quad \gamma\mapsto\{\alp,\gamma(\alp)\}$$
is a surjective group homomorphism. 
So, knowing generators for $\Gamma$ would be enough.

Now specialize to the case $\Gamma=\Gamma_0(N)$. 
Here is one guess for what {\em might} be true. 
Do the Manin symbols $(c,d)$ with $(c,N)=(d,N)=1$ 
generate $H_1(X_0(N),\Z)$?
When $N$ is prime those Manin symbols lie in
$H_1(X_0(N),\Z)$ because they correspond
to paths from the non-$\infty$ cusp to itself. 
Let $(c,d)$ be such a Manin symbol and choose 
$a,b$ so that $M=\abcd{a}{b}{c}{d}\in\sltwoz$.
Then the Modular symbol corresponding to $(c,d)$
is $M.\e=M.\{0,\infty\}=\{M(0),M(\infty)\}$. 
Since $c$ and $d$ are both coprime to $N$, the
cusps $[\frac{a}{c}]$ and $[\frac{b}{d}]$ are
the same (remember, we are assuming $N$ is prime
so that there are only two cusps).   The only
other way to force the cusps to be the same would
be to force $b$ and $d$ to both be divisible by $N$,
but then $(c,d)$ would not be a Manin symbol.

I do not know if these Manin symbols are enough
to generate all integral modular symbols.  But,
we can set up some computer computations to get an
idea of whether or not we should expect this.

{\bf Computation 1.} Let $H=H_1(X_0(N),\Z)$.
Let $V$ be the submodule of $H$ generated by
the modular symbols $\{\infty,\gamma(\infty)\}$
where $\gamma=\abcd{a}{b}{N}{d}$ and $0<a<N$. 
Let $W$ be the submodule of $H_1(X_0(N),\Q)$ generated
by the Manin symbols $(c,d)$ for which both
$c$ and $d$ are coprime to $N$.
If things were as easy as imaginable then
both $V$ and $W$ would be equal to $H$ (and
to each other).  If $W$ is properly contained
in $V$ then we learn that the answer to the question
is {\em NO}.  In the prime case, if $V$ is properly
contained in $W$ we learn that $V$ does not
generate $H$, which is also interesting. 

We compute $V$ and $W$ for $11\leq N\leq 100$, and the 
module index $[V:W]$. 
Whenever there is a - for the index, this means that
that {\em neither} $V$ nor $W$ span $H_1(X_0(N),\Q)$
over $\Q$.  In these cases we didn't compute the actual index.

$N$&$[W:V]$\\ \hline
11 & 1\\
14 & 1\\
15 & 1\\
17 & 1\\
19 & 1\\
20 & 1\\
21 & 1\\
22 & 1\\
23 & 1\\
24 & 1\\
26 & 1\\
27 & 1\\
28 & 1\\
29 & 1\\
30 & -\\
31 & 1\\
32 & 1\\
33 & 1\\
34 & 1\\
35 & 1\\
37 & 1\\
38 & 1\\
39 & 1\\
41 & 1\\
42 & -\\
43 & 1\\
44 & 1\\
45 & 1\\
46 & 1\\
47 & 1\\
48 & -\\
49 & 1\\
50 & 1\\
51 & 1\\
52 & 1\\
53 & 1\\
54 & -\\
55 & 1\\
56 & -\\
57 & 1\\
58 & 1\\
59 & 1\\
60 & -\\
61 & 1\\
62 & 1\\
$N$&$[W:V]$\\ \hline
63 & 1\\
64 & 1\\
65 & 1\\
66 & -\\
67 & 1\\
68 & 1\\
69 & 1\\
70 & -\\
71 & 1\\
72 & -\\
73 & 1\\
74 & 1\\
75 & 1\\
76 & 1\\
77 & 1\\
78 & -\\
79 & 1\\
80 & -\\
81 & 1\\
82 & 1\\
83 & 1\\
84 & -\\
85 & 1\\
86 & 1\\
87 & 1\\
88 & -\\
89 & 1\\
90 & -\\
91 & 1\\
92 & 1\\
93 & 1\\
94 & 1\\
95 & 1\\
96 & -\\
97 & 1\\
98 & 1\\
99 & 1\\
100 & -\\
101 & 1\\
102 & -\\
103 & 1\\
104 & -\\
105 & -\\
106 & 1\\
107 & 1\\
$N$&$[W:V]$\\ \hline
108 & -\\
109 & 1\\
110 & -\\
111 & 1\\
112 & -\\
113 & 1\\
114 & -\\
115 & 1\\
116 & 1\\
117 & 1\\
118 & 1\\
119 & 1\\
120 & -\\
121 & 1\\
122 & 1\\
123 & 1\\
124 & 1\\
125 & 1\\
126 & -\\
127 & 1\\
128 & 1\\
129 & 1\\
130 & -\\
131 & 1\\
132 & -\\
133 & 1\\
134 & 1\\
135 & -\\
136 & -\\
137 & 1\\
138 & -\\
139 & 1\\
140 & -\\
141 & 1\\
142 & 1\\
143 & 1\\
144 & -\\
145 & 1\\
146 & 1\\
147 & 1\\
148 & 1\\
149 & 1\\
150 & -\\
151 & 1\\
152 & -\\
$N$&$[W:V]$\\ \hline
153 & 1\\
154 & -\\
155 & 1\\
156 & -\\
157 & 1\\
158 & 1\\
159 & 1\\
160 & -\\
161 & 1\\
162 & -\\
163 & 1\\
164 & 1\\
165 & -\\
166 & 1\\
167 & 1\\
168 & -\\
169 & 1\\
170 & -\\
171 & 1\\
172 & 1\\
173 & 1\\
174 & -\\
175 & 1\\
176 & -\\
177 & 1\\
178 & 1\\
179 & 1\\
180 & -\\
181 & 1\\
182 & -\\
183 & 1\\
184 & -\\
185 & 1\\
186 & -\\
187 & 1\\
188 & 1\\
189 & -\\
190 & -\\
191 & 1\\
192 & -\\
193 & 1\\
194 & 1\\
195 & -\\
196 & -\\
197 & 1\\


{\bf Conclusion:} Neither obvious set of elements
of $H_1(X_0(N),\Z)$ will, in general, generate. 
It might be necessary to look at
R. S. Kulkarni, An arithmetic-geometry method of the study
of the subgroups of the modular group, American Journal of mathematics
113, 1991, 1053-1133
and find explicit generators.

\bibitem[B]{birch} B. Birch, {\em Elliptic curves, a progress report,}
AMS conference on number theory, Stonybrook (1969), 396--400.

\bibitem[CR1]{cremona1} J.E. Cremona,
{\em Algorithms for modular elliptic curves, 2nd edition},
Cambridge University Press, (1997).

\bibitem[CR2]{cremona2} J.E. Cremona,
{\em Modular symbols for $\Gamma_1(N)$ and elliptic curves with
everywhere good reduction}, Math. Proc. Camb. Phil. Soc. 
{\bf 111} (1992), 199--218.

\bibitem[HJ]{hijikata} H. Hijikata,
{\em Explicit formula of the traces of Hecke operators for 
$\Gamma_0(N)$}, J. Math. Soc. Japan. {\bf 26} (1974), 56--82. 

\bibitem[K]{kohel} D. Kohel, {\em Hecke module structure of quaternions},
(1998), preprint.

\bibitem[M]{merel} L. Merel,
{\em Universal fourier expansions of modular forms},
Springer L.N.M. 1585, (1994). 

\bibitem[M1]{mestre} J.F. Mestre,
   {\em La m\'{e}thode des graphs. Exemples et applications}, 
Taniguchi Symp., Proceedings of the international 
conference on class numbers and fundamental units of 
algebraic number fields (Katata, 1986), 217--242, Nagoya Univ., Nagoya, 1986.

\bibitem[P]{pizer} A. Pizer, {\em An algorithm for computing modular forms
on $\Gamma_0(N)$}, Journal of Algebra {\bf 64} (1980), 340--390.

\bibitem[S]{stein} W. Stein,
{\em Modular forms database},

G. Stevens, {\em Rigid analytic modular symbols},

H. Wada, {\em A table of Hecke operators. II},
Proc. Japan Acad., {\bf 49} (1973), 380--384.

X. Wang, {\em The hecke algebra on the cohomology of $\Gamma_0(p_0)$},
Nagoya Math. J., {\bf 121} (1991), 97--125.

X. Wang, {\em The hecke operators on $S_k(\Gamma_1(N))$},
J. Symbolic Computation, {\bf 18} (1994), 187--198.