\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{hyperref}
\hypersetup{colorlinks=true,urlcolor=blue,citecolor=blue,linkcolor=blue}
\usepackage{courier}
\usepackage{tikz}
\usepackage{tikz-cd}
\usetikzlibrary{calc,matrix,arrows,decorations.markings}
\usepackage{array}
\usepackage{color}
\usepackage{enumerate}
\usepackage{nicefrac}
\usepackage{listings}
\lstset{
	basicstyle=\small\ttfamily,
	keywordstyle=\color{blue},
	language=python,
	xleftmargin=16pt,
}

\textwidth=5.8in
\textheight=9in
\topmargin=-0.5in
\headheight=0in
\headsep=.5in
\hoffset  -.4in
\pagestyle{empty}

% growing list of useful macros, use these where appropriate and add to this list as needed
\newcommand{\kbar}{\bar{k}}
\newcommand{\Fp}{\mathbb{F}_p}
\newcommand{\Fpbar}{\overline{\mathbb{F}}_p}
\newcommand{\Fq}{\mathbb{F}_q}
\newcommand{\Fqbar}{\overline{\mathbb{F}}_q}
\newcommand{\Fqm}{\mathbb{F}_{q^m}}
\newcommand{\Fqn}{\mathbb{F}_{q^n}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Qbar}{\overline{\Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\renewcommand{\H}{\mathbf{H}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Zhat}{\widehat\Z}
\newcommand{\Zbar}{\overline\Z}
\newcommand{\Kbar}{\overline K}
\newcommand{\Ksep}{{K^{\rm sep}}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\Aut}{{\rm Aut}}
\newcommand{\Gal}{{\rm Gal}}
\newcommand{\SL}{{\rm SL}}
\newcommand{\SO}{{\rm SO}}
\newcommand{\GL}{{\rm GL}}
\newcommand{\PGL}{{\rm PGL}}
\newcommand{\PSL}{{\rm PSL}}
\newcommand{\dy}{\,dy}
\newcommand{\dx}{\,dx}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\kron}[2]{\bigl(\frac{#1}{#2}\bigr)}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\ceil}[1]{\lceil{#1}\frac{1}eil}
\newcommand{\Exp}{{\rm E}}
\renewcommand{\O}{\mathcal{O}}
\newcommand{\OK}{\O_K}
\newcommand{\T}{{\rm T}}
\newcommand{\N}{{\rm N}}
\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\Li}{\operatorname{Li}}
\newcommand{\ord}{\operatorname{ord}}
\newcommand{\Cl}{\operatorname{Cl}}
\newcommand{\disc}{\operatorname{disc}}
\newcommand{\p}{\mathfrak{p}}
\newcommand{\q}{\mathfrak{q}}
\renewcommand{\r}{\mathfrak{r}}
\newcommand{\m}{{\mathfrak m}}
\renewcommand{\c}{{\mathfrak c}}
\renewcommand{\a}{{\mathfrak a}}
\newcommand{\Frob}{{\rm Frob}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\Res}{\operatorname{Res}}
\newcommand{\Div}{\operatorname{Div}}
\newcommand{\tor}{{\rm tors}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\D}{\mathbf{D}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\A}{\mathbb{A}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\CP}{\mathbb{CP}}
\newcommand{\RP}{\mathbb{RP}}
\newcommand{\ab}{{\rm ab}}
\newcommand{\Ind}{\operatorname{Ind}}
\newcommand{\CoInd}{\operatorname{CoInd}}
\newcommand{\Inf}{\operatorname{Inf}}
\newcommand{\inv}{\operatorname{inv}}
\newcommand{\smat}[4]{{\left(\begin{smallmatrix} #1 & #2 \\ #3 & #4 \end{smallmatrix}\right)}}
\newcommand{\abcd}{\smat{a}{b}{c}{d}}
\newcommand{\Rmat}{\smat{1}{-1}{1}{0}}
\newcommand{\Smat}{\smat{0}{-1}{1}{0}}
\newcommand{\Tmat}{\smat{1}{1}{0}{1}}
\newcommand{\Umat}{\smat{1}{0}{1}{1}}
\newcommand{\M}{\mathbb{M}}
\newcommand{\B}{\mathbb{B}}
\renewcommand{\S}{\mathbb{S}}
\renewcommand{\T}{\mathbb{T}}

\newtheorem*{theorem}{Theorem}
\theoremstyle{definition}
\newtheorem*{definition}{Definition}
\newtheorem*{remark}{Remark}

\begin{document}
\setlength{\unitlength}{1in}
\begin{center}
\large
\textbf{18.786 Number Theory II\hspace{198pt}Spring~2018}\\\vspace{4pt}
\textbf{Problem Set \#5\hspace{228pt}Due: 5/16/2018}
\normalsize
\begin{picture}(5.8,.1) 
\put(0,0) {\line(1,0){5.8}}
\end{picture}
\end{center}

\subsection*{Description}

Your solutions are to be written up in latex and submitted as a pdf-file with a filename of the form \texttt{SurnamePset5.pdf} via e-mail to \texttt{drew@math.mit.edu} by \textbf{noon} on the date due.
Collaboration is permitted/encouraged, but you must identify your collaborators, and any references consulted.
If there are none, write ``\textbf{Sources consulted:\ none}" at the top of your problem set.
The first person to spot each non-trivial typo/error in any of the problem sets or lecture notes will receive 1-5 points of extra credit.
\medskip

\noindent
\textbf{Instructions:} Solve problem 1 then complete the survey.  Since there is only one problem on this problem set, you are free to skip one step with no penalty (so if you get stuck on something, or just find a particular step tedious, feel free to skip it).

\subsection*{Problem 1. Modular symbols for $\boldsymbol{S_2(\Gamma_0(N))}$ (99 points)}

Modular symbols are one of the main techniques used to explicitly compute modular forms (both Sage and Magma rely on them), and they also have several theoretical applications.
Let us first fix some notation.  Let $\H:=\{\tau\in \C:\Im \tau >0\}$ denote the extended upper half plane, let $\P^1(\Q):= \Q\cup \{\infty\}$, and let
\[
\mathbf H^*:= \mathbf H\cup \P^1(\Q)
\]
denote the extended upper half plane.
Recall that the cusps of $\Gamma(1)=\SL_2(\Z)$ constitute a single orbit $\P^1(\Q)$.
For any distinct pair $\alpha,\beta\in \P^1(\Q)$ there is a unique geodesic with endpoints $\alpha$ and $\beta$.
We use $[\alpha,\beta]$ to denote the oriented geodesic that starts at $\alpha$ and ends at $\beta$; it corresponds to a directed loop on the Riemann surface $X(1)=\H^*/\Gamma(1)$.

Let $\M_2$ be the $\Z$-module generated by the formal symbols $\{[\alpha,\beta]:\alpha,\beta\in \P^1(\Q)\}$ modulo the relations\footnote{The notation $\{\alpha,\beta\}$ (rather than $[\alpha,\beta]$) is standard, but we shall avoid this misleading notation.}
\[
[ \alpha,\beta] + [\beta,\gamma] + [\gamma,\alpha] = 0,
\]
and modulo torsion (so $[\alpha,\alpha]=0$, since $[\alpha,\alpha]+[\alpha,\alpha]+[\alpha,\alpha]=0$, and $[\alpha,\beta] = - [\beta,\alpha]$, since  $[\alpha,\beta]+[\beta,\alpha]+[\alpha,\alpha]=0$).
We equip $\M_2$ with a left $\GL_2(\Q)$-action by defining
\[
g [\alpha,\beta] :=  [g\alpha,g\beta].
\]
We also define $\B_2:= \Z[\P^1(\Q)]$ as the free $\Z$-module with basis $\P^1(\Q)$, on which $\GL_2(\Q)$ acts on the left via linear fractional transformations: $\abcd (x:y):=(ax+by:cx+dy)$.
Let us fix notation for the following elements of $\SL_2(Z)$:
\[
\sigma:= S:= \smat{0}{-1}{1}{0},\qquad T:=\smat{1}{1}{0}{1},\qquad \tau:=T\sigma = \smat{1}{-1}{1}{0}.
\]
Recall that $\SL_2(\Z)=\langle S, T\rangle=\langle \sigma,\tau\rangle$, and that the map from $\SL_2(\Z)$ to the finitely presented group $\langle s,t|s^2=t^3=1\rangle$ defined by $\sigma\mapsto s, \tau\mapsto t$ is surjective with kernel $\pm 1$ (see Problem 6 on Problem Set 3).

\begin{enumerate}[{\bf (a)}]
\item Show that the map $\M_2\to \B_2$ defined by $[\alpha,\beta]\mapsto \alpha-\beta$ is an injective homomorphism of left $\Z[\SL_2(\Z)]$-modules with image $\B_2^0:=\{\sum n_P P\in \B_2: \sum n_P=0\}$. 
 \item Show that the map $\Z[\SL_2(\Z)]\to \B_2$ defined by $\gamma\mapsto \gamma (1\!:\!0)-\gamma(0\!:\!1)$ is a homomorphism of left $\Z[\SL_2(\Z)]$-modules with kernel $\langle 1+\sigma, 1+\tau+\tau^2\rangle$ (a left $\Z[\SL_2(\Z)]$-ideal) and image $\B_2^0$.  Conclude that the map $\Z[\SL_2(\Z)]\to\M_2$ defined by $\gamma\mapsto \gamma[0,\infty]$ is surjective with kernel $\langle 1+\sigma, 1+\tau+\tau^2\rangle$.
\end{enumerate}

For any subgroup $\Gamma\le \SL_2(\Z)$ we can view $\M_2$ and $\B_2$ as $\Z[\Gamma$]-modules (one could formally write $\Res^{\SL_2(\Z)}_\Gamma\M_2$ and $\Res^{\GL_2(\Z)}_\Gamma\B_2$, but we will avoid this clutter when it is clear from context that we are working with $\Z[\Gamma]$-modules).
Henceforth we shall assume that $\Gamma\le \SL_2(\Z)$ is a finite index subgroup (you may assume $\Gamma=\Gamma_0(N)$ if you wish).
We define the $\Z[\Gamma]$-modules of coinvariants:
\begin{align*}
\M_2(\Gamma):= (\M_2)_\Gamma=\M_2/I_\Gamma \M_2,\\
\B_2(\Gamma):= (\B_2)_\Gamma=\B_2/I_\Gamma \B_2,
\end{align*}
where $I_\Gamma:=\ker(\sum n_\gamma\gamma\mapsto \sum n_\gamma)=\langle \gamma-1:\gamma\in \Gamma\rangle\subseteq \Z[\Gamma]$ is the augmentation ideal.
We call $\M_2(\Gamma)$ the space of \emph{modular symbols for $\Gamma$} (of weight 2), and $\B_2(\Gamma)$ is the \emph{boundary space} for $\Gamma$.
To simplify the presentation in what follows, let us replace $\M_2(\Gamma)$ and $\B_2(\Gamma)$ by their torsion-free quotients (as in \cite{Stein}).

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{2}
\item Show that for all $m,n\in \Z$ and $N\in \Z_{\ge 1}$ we have $[m,n] = 0$ in $\M_2(\Gamma_0(N))$ (in particular, the $\Z[\SL_2(\Z)]$-modules $\M_2$ and $\M_2(\Z[\SL_2(\Z)])$ are not the same).
\item Let $\SL_2(\Z)=\Gamma\gamma_1\sqcup \cdots\sqcup \Gamma\gamma_n$ be a right coset decomposition for $\Gamma\le \SL_2(\Z)$.
Show that $\{\gamma_1[0,\infty],\cdots,\gamma_n[0,\infty]\}$ generates $\M_2(\Gamma)$ as a $\Z$-module; thus $\M_2(\Gamma)$ is a finitely generated abelian group.
\item Let $\Z[\Gamma\backslash\SL_2(\Z)]$ be the free abelian group on right cosets $\{\Gamma\alpha:\alpha\in \SL_2(\Z)\}$ equipped with the right $\SL_2(\Z)$-action $(\Gamma\alpha)\beta=\Gamma\alpha\beta$.  Let $\M_2'(\Gamma)$ be the quotient of $\Z[\Gamma\backslash\SL_2(\Z)]$ modulo its image under the right $\Z[\SL_2(\Z)]$-ideal
\[
\langle 1+\sigma, 1+\tau+\tau^2, 1-J\rangle,
\]
where $J:=\smat{-1}{0}{0}{-1}$, and modulo any torsion.  Show that the map $\Gamma\gamma\mapsto \gamma[0,\infty]$ defines an isomorphism of $\Z$-modules $\M_2'(\Gamma)\simeq \M_2(\Gamma)$.
\item Let $\P^1(\Z/N\Z):=\{(a:b):a,b\in \Z/N\Z \text{ with }\gcd(a,b,N)=1\}$ where we define $(a:b) = (a':b')$ if $a'=ua$ and $b'=ub$ for some $u\in (\Z/N\Z)^{\times}$.
Show that the map $\Gamma_0(N) \abcd\mapsto (c:d)$ defines a bijection $\Gamma_0(N)\backslash\SL_2(\Z)\overset\sim\longrightarrow \P^1(\Z/N\Z)$.
\end{enumerate}


Let $X_\Gamma:=\Gamma\backslash \H^*$.  There is a natural homomorphism
\[
\varphi\colon \M_2(\Gamma)\to H_1(X_\Gamma,\{\text{cusps}\}, \Z)
\]
that sends $\Z$-linear combinations of geodesic paths in $\H^*$ to their images in $X_\Gamma=\Gamma\backslash \H^*$.
Here we are taking homology \emph{relative to the cusps}; this means that in addition to loops, we include homology classes of paths that start and end at cusps (cusps of $X_\Gamma$ are $\Gamma$-orbits of cusps $\P^1(\Q)\subseteq \H^*$).  If $X_\Gamma$ has only one cusp (as when $\Gamma=\SL_2(\Z)$), this is just usual homology.
We now define the \emph{boundary map}
\begin{align*}
\delta\colon \M_2(\Gamma) &\to \B_2(\Gamma)\\
[ \alpha,\beta] &\mapsto \beta-\alpha.
\end{align*}
The kernel of this map is the subspace $\S_2(\Gamma)$ of \emph{cuspidal modular symbols}.

\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{6}
\item Prove that the restriction of $\varphi$ to the subspace of cuspidal modular symbols defines an isomorphism of free $\Z$-modules $\S_2(\Gamma)\overset\sim\to H_1(X_\Gamma,\Z)$.
There are several approaches to this: (a) follow Manin's topological proof in \cite{Manin}, (b) use group cohomology as in \cite{Wiese}, (c) view $H_1(X_\Gamma,\Z)$ as a lattice in $S_2(\Gamma)^\vee$ via the integration pairing.  Feel free to assume $\Gamma=\Gamma_0(p)$ with $p$ prime if you wish (there are then exactly 2 cusps).
\item Let $(s_1:t_1),(s_2:t_2)\in \P^1(\Q)$ be cusps with $\gcd(s_1,t_1)=\gcd(s_2,t_2)=1$.  Show that $(s_1:t_1)-(s_2:t_2)=0\in \B_2(\Gamma_0(N))$ if and only if there exists $a_1,a_2\in \Z$ such that $a_1t_2\equiv a_2t_1\bmod \gcd(t_1t_2,N)$ and $a_is_i\equiv 1\bmod t_i$ for $i=1,2$.
\end{enumerate}

We now specialize to $\Gamma=\Gamma_0(N)$.  We want to define the action of the Hecke algebra $\T(N):=\T(\Gamma_0(N),\Delta_0(N),\Z)$ on the space of modular symbols $\M_2(N):=\M_2(\Gamma_0(N))$ and the isomorphic space of Manin symbols $\M_2'(N):=\M_2'(\Gamma_0(N))$, where
\[
\Delta_0(N):=\left\{\abcd\in \Z^{2\times 2}:c\equiv 0\bmod N, a\perp N, ad-bc>0\right\}
\]
as usual.
If $\Gamma_0(N)\alpha\Gamma_0(N)$ is a Hecke operator, with $\alpha\in \Delta_0(N)$, and
\[
\Gamma_0(N)\alpha\Gamma_0(N)=\Gamma_0(N)\gamma_1\sqcup\cdots\sqcup \Gamma_0(N)\gamma_n
\]
is a right coset decomposition, then for $[\alpha,\beta]\in \M_2(N)$ we define
\[
\Gamma_0(N)\alpha\Gamma_0(N)[\alpha,\beta]:= \sum_{1\le i\le n}\gamma_i[\alpha,\beta].
\]
For example, for the Hecke operator $T_p:= \Gamma_0(N)\smat{1}{0}{0}{p}\Gamma_0(N)$ with $p\nmid N$ prime we have
\[
T_p([\alpha,\beta]):= \smat{p}{0}{0}{1}[\alpha,\beta] + \sum_{0\le r<p}\smat{1}{r}{0}{p}[\alpha,\beta].
\]
To define the action of $T_p$ on $\M'_2(N)$ we will use the bijection $\Gamma_0(N)\backslash\SL_2(\Z)\overset\sim\rightarrow\P^1(\Z/N\Z)$ from part {\bf (e)} to represent elements of $\M'_2(N)$ as elements of $\Z[\P^1(\Z/N\Z)]$.  We now define
\[
T_p((c:d)):=\sum_{M\in R_p}(c:d)M,
\]
where $M$ acts by matrix multiplication on the right of the row vector $(c:d)$ and $R_p$ is the set of \emph{Heilbronn matrices}.
The isomorphism $\M_2'(N)\overset\sim\rightarrow \M_2(N)$ is given by
\[
(c:d)=\Gamma_0(N)\abcd\mapsto \abcd[0,\infty] = [\tfrac{b}{d}, \tfrac{a}{c}]. 
\]
Thus the Heilbronn matrices $R_p$ must satisfy
\begin{equation}\label{Rp}
T_p((c:d))=\sum_{M\in R_p}(c:d)M \mapsto  \smat{p}{0}{0}{1}[\tfrac{b}{d},\tfrac{a}{c}]+\sum_{0\le r< p}\smat{1}{r}{0}{p}[\tfrac{b}{d},\tfrac{a}{c}]
\end{equation}
Recall that every rational number $s/t$ has a continued fraction expansion with successive convergents in lowest terms:
\[
\frac{s_{-2}}{t_{-2}}=\frac{0}{1},\ \frac{s_{-1}}{t_{-1}}=\frac{1}{0},\ \frac{s_0}{t_0}=\frac{s_0}{1},\ \ldots,\ \frac{s_{n-1}}{t_{n-1}},\ \frac{s_n}{t_n}=\frac{s}{t}
\]
with $s_nt_{n-1}-s_{n-1}t_n=(-1)^{n+1}$ so that
\[
\begin{pmatrix}s_n & (-1)^{n+1}s_{n-1}\\t_n & (-1)^{n+1}t_{n-1}\end{pmatrix}\in \SL_2(\Z).
\]
\begin{enumerate}[{\bf (a)}]
\setcounter{enumi}{8}
\item Show that we can match the first term on the RHS of \eqref{Rp} by taking $M=\smat{1}{0}{0}{p}\in R_p$.  Then show that, given $(c:d)$, for each $0\le r < p$ one can choose $a,b\in \Z$ so that $ad-bc=1$ and $A:=\smat{1}{r}{0}{p}\abcd\smat{1}{r}{0}{p}^{-1}\in \SL_2(\Z)$, and a sequence of matrices $A_0,\ldots,A_n$ such that
\[
\sum_{0\le i\le n} A A_iS[0,\infty] = A[\tfrac{r}{p},\infty] =\smat{1}{r}{0}{p}[\tfrac{b}{d},\tfrac{a}{c}].
\]
Now show that if define $M_i:=\smat{p}{-r}{0}{1}A_iS$ for $0\le i\le n$ then we will have
\[
\sum_{0\le i\le n}(c:d)M_i \mapsto \smat{1}{r}{0}{p}[\tfrac{b}{d},\tfrac{a}{c}]
\]
under the isomorphism $\M_2'(N)\overset\sim\rightarrow \M_2(N)$.  Conclude that a suitable set of Heilbronn matrices $R_p$ exists (to compute them in Sage using \texttt{HelbronnCremonaList(p)}).

\item Describe an algorithm that, given a positive integer $N$ computes a basis for $S_2(\Gamma_0(N))$ consisting of cuspidal forms with integer Fourier coefficients $a_n$ (not necessarily newforms), with $a_n$ computed for sufficiently many $n$ to distinguish your basis elements, and give an algorithm for computing the matrix of any Hecke operator $T_p$ for $p\nmid N$ acting on this basis using the tools you developed above.  Illustrate your algorithm for $N=23$ and $p=2,3$ (feel free to use Sage to perform the computations, the point is to explain what you are doing).
\end{enumerate}

\subsection*{Problem 4. Survey (1 point)}
Complete the following survey by rating each problem you attempted on a scale of 1 to~10 according to how interesting you found it (1 = ``mind-numbing," 10 = ``mind-blowing"), and how difficult you found it (1 = ``trivial," 10 = ``brutal").  Also estimate the amount of time you spent on each problem to the nearest half hour.

\begin{center}
\begin{tabular}{l|r|r|r|}
& Interest & Difficulty & Time Spent\\\hline
Problem 1 & & & \\\hline
\end{tabular}
\end{center}

\begin{thebibliography}{99}
\bibitem{Manin} J. Manin, \href{https://doi.org/10.1070/IM1972v006n01ABEH001867}{\textit{Parabolic points and zeta-functions of modular curves}}, Math. USSR Izv \textbf{6} (1972).
\bibitem{Stein} W. Stein, \href{https://wstein.org/books/modform/modform/}{\textit{Modular forms: a computational approach}}, AMS, 2007.
\bibitem{Wiese} G. Wiese, \href{http://math.uni.lu/~wiese/thesis/Thesis.pdf}{\textit{Modular forms of weight one over finite fields}}, Ph.D. thesis, Universiteit Leiden, 2005. 
\end{thebibliography}

\end{document}