\documentclass{book}
\author{William Stein}
\title{Computing With Modular Forms}

\usepackage{index}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage[all]{xy}
\usepackage{sage}

\newcommand{\code}[1]{{\tt #1}}

\usepackage{xspace}  % to allow for text macros that don't eat space 
\newcommand{\SAGE}{{\sf SAGE}\xspace}
\newcommand{\sage}{\SAGE}


%\newcommand{\comment}[1]{}

%\usepackage[hyperindex,pdfmark]{hyperref}
\usepackage[hypertex]{hyperref}

%\newcommand{\edit}[1]{{\bf [[Todo: #1]]}}
\newcommand{\edit}[1]{}
\newcommand{\examplesession}[1]{}
\newcommand{\gzero}{\Gamma_0(N)}
\newcommand{\esM}{\overline{\sM}}
\newcommand{\sM}{\mathbb{M}}
\newcommand{\sS}{\mathbb{S}}
\newcommand{\sB}{\mathbb{B}}
\newcommand{\eE}{\mathbf{E}}
\newcommand{\Adual}{A^{\vee}}
\newcommand{\Bdual}{B^{\vee}}

\newcommand{\defn}[1]{{\em \index*{#1}}}
\newcommand{\solution}[1]{\vspace{1em}\par\noindent{\bf Solution #1.} }
\newcommand{\todo}[1]{{\bf [[TODO: #1]]}}
\newcommand{\done}[1]{\noindent {\small \textsf{Done: #1}}\\}
\newcommand{\danger}[1]{\marginpar{\small \textsl{#1}}}
\renewcommand{\div}{\mbox{\rm div}}
\DeclareMathOperator{\chr}{char}
\DeclareMathOperator{\ind}{ind}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\oo}{\infty}
\DeclareMathOperator{\abs}{abs}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\cores}{cores}
\DeclareMathOperator{\coker}{coker}
\DeclareMathOperator{\image}{image}
\DeclareMathOperator{\prt}{part}
\DeclareMathOperator{\proj}{proj}
\DeclareMathOperator{\Br}{Br}
\DeclareMathOperator{\Ann}{Ann}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\Tan}{Tan}
\DeclareMathOperator{\Eis}{Eis}
\newcommand{\unity}{\mathbf{1}}
\DeclareMathOperator{\Pic}{Pic}
\DeclareMathOperator{\Vol}{Vol}
\DeclareMathOperator{\Vis}{Vis}
\DeclareMathOperator{\Reg}{Reg}
%\DeclareMathOperator{\myRes}{Res}
%\newcommand{\Res}{\myRes}
\DeclareMathOperator{\Res}{Res}
\newcommand{\an}{{\rm an}}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\Sel}{Sel}
\DeclareMathOperator{\Mat}{Mat}
\DeclareMathOperator{\BSD}{BSD}
\DeclareMathOperator{\id}{id}
%\DeclareMathOperator{\dz}{dz}
\newcommand{\dz}{dz}
%\DeclareMathOperator{\Re}{Re}
\renewcommand{\Re}{\mbox{\rm Re}}
%\DeclareMathOperator{\Im}{Im}
\DeclareMathOperator{\Selmer}{Selmer}
\newcommand{\pfSel}{\widehat{\Sel}}
\newcommand{\qe}{\stackrel{\mbox{\tiny ?}}{=}}
\newcommand{\isog}{\simeq}
\newcommand{\e}{\mathbf{e}}
\newcommand{\bN}{\mathbf{N}}

% ---- SHA ----
\DeclareFontEncoding{OT2}{}{} % to enable usage of cyrillic fonts
  \newcommand{\textcyr}[1]{%
    {\fontencoding{OT2}\fontfamily{wncyr}\fontseries{m}\fontshape{n}%
     \selectfont #1}}
\newcommand{\Sha}{{\mbox{\textcyr{Sh}}}}

%\font\cyr=wncyr10 scaled \magstep 1
%\font\cyr=wncyr10

%\newcommand{\Sha}{{\cyr X}}
\newcommand{\set}{=}
\newcommand{\Shaan}{\Sha_{\mbox{\tiny \rm an}}}
\newcommand{\TS}{Shafarevich-Tate group}

\newcommand{\Gam}{\Gamma}
\renewcommand{\Im}{\text{Im}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cJ}{\mathcal{J}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cV}{\mathcal{V}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\ds}{\displaystyle}
\newcommand{\M}{\mathcal{M}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\E}{\mathcal{E}}
\renewcommand{\L}{\mathcal{L}}
\newcommand{\J}{\mathcal{J}}
\DeclareMathOperator{\new}{new}
\DeclareMathOperator{\Morph}{Morph}
\DeclareMathOperator{\old}{old}
\DeclareMathOperator{\Sym}{Sym}
\DeclareMathOperator{\Symb}{Symb}
%\newcommand{\Sym}{\mathcal{S}{\rm ym}}
\newcommand{\dw}{\delta(w)} 
\newcommand{\dwh}{\widehat{\delta(w)}}      
\newcommand{\dlwh}{\widehat{\delta_\l(w)}} 
\newcommand{\dash}{-\!\!\!\!-\!\!\!\!-\!\!\!\!-} 
\DeclareMathOperator{\tor}{tor}  
\newcommand{\Frobl}{\Frob_{\ell}}
\newcommand{\tE}{\tilde{E}}
\renewcommand{\l}{\ell}
\renewcommand{\t}{\tau}
\DeclareMathOperator{\cond}{cond}
\DeclareMathOperator{\Spec}{Spec}
\DeclareMathOperator{\Div}{Div}
\DeclareMathOperator{\Jac}{Jac}
\DeclareMathOperator{\res}{res}
\DeclareMathOperator{\Ker}{Ker}
\DeclareMathOperator{\Coker}{Coker}
\DeclareMathOperator{\sep}{sep}
\DeclareMathOperator{\sign}{sign}
\DeclareMathOperator{\unr}{unr}
\DeclareMathOperator{\Char}{char}
\newcommand{\N}{\mathcal{N}}
\newcommand{\U}{\mathcal{U}}
\newcommand{\Kbar}{\overline{K}}
\newcommand{\Lbar}{\overline{L}}
\newcommand{\gammabar}{\overline{\gamma}}
\newcommand{\q}{\mathbf{q}}
\renewcommand{\star}{\times}
\newcommand{\gM}{\mathfrak{M}}
\newcommand{\gA}{\mathfrak{A}}
\newcommand{\gP}{\mathfrak{P}}
\newcommand{\bmu}{\boldsymbol{\mu}}
\newcommand{\union}{\cup}
\newcommand{\Tl}{T_{\ell}}
\newcommand{\into}{\rightarrow}
\newcommand{\onto}{\rightarrow\!\!\!\!\rightarrow}
\newcommand{\intersect}{\cap}
\newcommand{\meet}{\cap}
\newcommand{\cross}{\times}
\DeclareMathOperator{\md}{mod}
\DeclareMathOperator{\toric}{toric}
\DeclareMathOperator{\tors}{tors}
\DeclareMathOperator{\Frac}{Frac}
\DeclareMathOperator{\corank}{corank}
\newcommand{\rb}{\overline{\rho}}
\newcommand{\ra}{\rightarrow}
\newcommand{\xra}[1]{\xrightarrow{#1}}
\newcommand{\hra}{\hookrightarrow}
\newcommand{\kr}[2]{\left(\frac{#1}{#2}\right)}
\newcommand{\la}{\leftarrow}
\newcommand{\lra}{\longrightarrow}
\newcommand{\riso}{\xrightarrow{\sim}}
\newcommand{\da}{\downarrow}
\newcommand{\ua}{\uparrow}
\newcommand{\con}{\equiv}
\newcommand{\Gm}{\mathbb{G}_m}
\newcommand{\pni}{\par\noindent}
\newcommand{\iv}{^{-1}}
\newcommand{\alp}{\alpha}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\cpp}{{\tt C++}}
\newcommand{\tensor}{\otimes}
\newcommand{\bg}{{\tt BruceGenus}}
\newcommand{\abcd}[4]{\left(
        \begin{smallmatrix}#1&#2\\#3&#4\end{smallmatrix}\right)}
\newcommand{\mthree}[9]{\left(
        \begin{matrix}#1&#2&#3\\#4&#5&#6\\#7&#8&#9
        \end{matrix}\right)}
\newcommand{\mtwo}[4]{\left(
        \begin{matrix}#1&#2\\#3&#4
        \end{matrix}\right)}
\newcommand{\vtwo}[2]{\left(
        \begin{matrix}#1\\#2
        \end{matrix}\right)}
\newcommand{\smallmtwo}[4]{\left(
        \begin{smallmatrix}#1&#2\\#3&#4
        \end{smallmatrix}\right)}
\newcommand{\twopii}{2\pi{}i{}}  
\newcommand{\eps}{\varepsilon}
\newcommand{\vphi}{\varphi}
\newcommand{\gp}{\mathfrak{p}}
\newcommand{\W}{\mathcal{W}}
\newcommand{\oz}{\overline{z}}
\newcommand{\Zpstar}{\Zp^{\star}}
\newcommand{\Zhat}{\widehat{\Z}}
\newcommand{\Zbar}{\overline{\Z}}
\newcommand{\Zl}{\Z_{\ell}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\GQ}{G_{\Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\D}{{\mathbf D}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\Sbar}{\overline{S}}
\newcommand{\K}{{\mathbf K}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Cp}{{\mathbf C}_p}
\newcommand{\Sets}{\mbox{\rm\bf Sets}}
\newcommand{\bcC}{\boldsymbol{\mathcal{C}}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\Qbar}{\overline{\Q}}
\newcommand{\kbar}{\overline{k}}
\newcommand{\dual}{\bot}
\newcommand{\T}{\mathbb{T}}
\newcommand{\calT}{\mathcal{T}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cbT}{\mathbf{\mathcal{T}}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\Fl}{\F_{\ell}}
\newcommand{\Fell}{\Fl}
\newcommand{\Flbar}{\overline{\F}_{\ell}}
\newcommand{\Flnu}{\F_{\ell^{\nu}}}
\newcommand{\Fbar}{\overline{\F}}
\newcommand{\Fpbar}{\overline{\F}_p}
\newcommand{\fbar}{\overline{f}}
\newcommand{\Qp}{\Q_p}
\newcommand{\Ql}{\Q_{\ell}}
\newcommand{\Qell}{\Q_{\ell}}
\newcommand{\Qlbar}{\overline{\Q}_{\ell}}
\newcommand{\Qlnr}{\Q_{\ell}^{\text{nr}}}
\newcommand{\Qlur}{\Q_{\ell}^{\text{ur}}}
\newcommand{\Qltm}{\Q_{\ell}^{\text{tame}}}
\newcommand{\Qv}{\Q_v}
\newcommand{\Qpbar}{\Qbar_p}
\newcommand{\Zp}{\Z_p}
\newcommand{\Fp}{\F_p}
\newcommand{\Fq}{\F_q}
\newcommand{\Fqbar}{\overline{\F}_q}
\newcommand{\Ad}{Ad}
\newcommand{\adz}{\Ad^0}
\renewcommand{\O}{\mathcal{O}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\Og}{O_{\gamma}}
\newcommand{\isom}{\cong}
\newcommand{\ncisom}{\approx}   % noncanonical isomorphism
\DeclareMathOperator{\ab}{ab}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Frob}{Frob}
\DeclareMathOperator{\Fr}{Fr}
\DeclareMathOperator{\Ver}{Ver}
\DeclareMathOperator{\Norm}{Norm}
\DeclareMathOperator{\norm}{norm}
\DeclareMathOperator{\disc}{disc}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\PSL}{PSL}
\DeclareMathOperator{\PGL}{PGL}
\DeclareMathOperator{\Gal}{Gal}
\DeclareMathOperator{\SL}{SL}
\DeclareMathOperator{\SO}{SO}
\newcommand{\galq}{\Gal(\Qbar/\Q)}
\newcommand{\rhobar}{\overline{\rho}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\et}{\text{\rm\'et}}

\newcommand{\sltwoz}{\SL_2(\Z)}
\newcommand{\sltwo}{\SL_2}
\newcommand{\gltwoz}{\GL_2(\Z)}
\newcommand{\mtwoz}{M_2(\Z)}
\newcommand{\gltwoq}{\GL_2(\Q)}
\newcommand{\gltwo}{\GL_2}
\newcommand{\gln}{\GL_n}
\newcommand{\psltwoz}{\PSL_2(\Z)}
\newcommand{\psltwo}{\PSL_2}
\newcommand{\h}{\mathfrak{h}}
\renewcommand{\a}{\mathfrak{a}}
\newcommand{\p}{\mathfrak{p}}
\newcommand{\m}{\mathfrak{m}}
\newcommand{\trho}{\tilde{\rho}}
\newcommand{\rhol}{\rho_{\ell}}
\newcommand{\rhoss}{\rho^{\text{ss}}}
\newcommand{\dbd}[1]{\langle #1 \rangle}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\order}{order}
\DeclareMathOperator{\ur}{ur}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\Mor}{Mor}
\DeclareMathOperator{\HH}{H}
\renewcommand{\H}{\HH}
\DeclareMathOperator{\Ext}{Ext}
\DeclareMathOperator{\Tor}{Tor}
\newcommand{\smallzero}{\left(\begin{smallmatrix}0&0\\0&0
                        \end{smallmatrix}\right)}
\newcommand{\smallone}{\left(\begin{smallmatrix}1&0\\0&1
                        \end{smallmatrix}\right)}

\newcommand{\pari}{{\sc Pari}\index{Pari}}
\newcommand{\python}{{\sc Python}\index{Python}}
\newcommand{\magma}{{\sc Magma}\index{Magma}}
\newcommand{\manin}{{\sc Manin}\index{Manin}}

\newcommand{\zbar}{\overline{z}}
\newcommand{\dzbar}{d\overline{z}}

%%%% Theoremstyles
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{alg}[theorem]{Algorithm}
\newtheorem{question}[theorem]{Question}
\newtheorem{problem}[theorem]{Problem}

%\theoremstyle{remark}
\newtheorem{goal}[theorem]{Goal}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{remarks}[theorem]{Remarks}
\newtheorem{example}[theorem]{Example}
\newtheorem{warning}[theorem]{Warning}
\newtheorem{exercise}[theorem]{Exercise}

\numberwithin{section}{chapter}
\numberwithin{equation}{section}
\numberwithin{figure}{section}
\numberwithin{table}{section}

\bibliographystyle{amsalpha}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Environments
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newenvironment{algorithm}[1]{%
\begin{alg}[#1]\index{algorithm!#1}\sf
}%
{\end{alg}}
\newenvironment{steps}%
{\begin{itemize}\setlength{\itemsep}{0.1ex}}{\end{itemize}}

\newcommand{\exref}[2]{Exercise~\ref{#1}.\ref{#2}}

\newenvironment{exercises}
{\section{Exercises}
 \renewcommand{\labelenumi}{\thechapter.\theenumi}
  \begin{enumerate}
}{\end{enumerate}}

\newcommand{\hd}[1]{\vspace{1ex}\noindent{\bf #1} }
\newcommand{\nf}[1]{\underline{#1}} 
\newcommand{\cbar}{\overline{c}}
\DeclareMathOperator{\rad}{rad}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\makeindex

\begin{document}
\maketitle

%\hfill
%\begin{center}
%Copyright (c) 2004 William Stein\\
%\end{center}
%The author grants permission to copy, distribute and/or modify this
%document under the terms of the GNU Free Documentation License,
%Version 1.2 or any later version published by the Free Software
%Foundation; with no Invariant Sections, no Front-Cover Texts, and no
%Back-Cover Texts.  A copy of the license is included in the Appendix.
%\hfill

\tableofcontents

\chapter*{Preface}
\addcontentsline{toc}{chapter}{\numberline{}Preface}

This is a book about algorithms for computing with modular forms that
started as a series of notes for a graduate course at Harvard
University in 2004.  This book is meant to answer the question ``How
do {\em you} compute spaces of modular forms'', by both providing a
clear description of the specific algorithms that are used and
explaining how to apply them using \SAGE \cite{sage}.

I have spent many years trying to find good practical ways to compute
with classical modular forms for congruence subgroups of $\SL_2(\Z)$,
and have implemented most of these algorithms several times, first in
C++ \cite{stein:hecke}, then in MAGMA \cite{magma}, and most recently
as part of \SAGE.  Much of this work has involved turning formulas and
constructions burried in obscure research papers into precise
computational recipes, then testing these in many cases and
eliminating subtle inaccuracies (published theorems sometimes contain
small mistakes that appear magnified when implemented and run on a
computer).  The goal of this book is to explain some of what I have
learned along the way.
%, and also describe unsolved problems whose
%solution would move the theory forward.

The author is aware of no other books on computing with modular forms,
the closest work being Cremona's book \cite{cremona:algs}, which is
about computing with elliptic curves, and Cohen's book
\cite{cohen:course_ant} about algebraic number theory.  The field is
not yet mature, and there are missing details and potential
improvements to many of the algorithms, which you the reader might
fill in, and which would be greatly appreciated by other
mathematicians.  

This book focuses on how best to compute the spaces $M_k(N,\eps)$ of
modular forms, where $k\geq 2$ is an integer and~$\eps$ is a Dirichlet
character modulo~$N$.  I will spend the most effort explaining the
algorithms that appear so far to be the best (in practice!) for such
computations.  I will not discuss computing half-integral weight
forms, weight one forms, forms for non-congruence subgroups or groups
other than $\GL_2$, Hilbert and Siegel modular forms, trace formulas,
$p$-adic modular forms, and modular abelian varieties, all of which
are topics for another book.

The reader is not assumed to have prior exposure to modular forms, but
should be familiar with abstract algebra, basic algebraic number
theory, Riemann surfaces, and complex analysis.


%The text of this book is licensed under the GNU Free Documentation
%License, Version 1.2, November 2002.  This means that you may freely
%copy this book.  For the precise details, see the Appendix.

%\noindent{}{\bf Acknowledgement:} None yet.
% \mbox{}\vspace{2ex} 

% \noindent{}William Stein\\
% {\tt http://modular.fas.harvard.edu}\\
% {\tt was@math.harvard.edu}

\vspace{2ex}
\noindent{}{\bf Acknowledgement.} 
Kevin Buzzard made many helpful remarks which were helpful in finding
the algorithms in Chapter~\ref{ch:dirichlet}.  Noam Elkies made many
remarks about chapters 1 and 2.  The students in the Harvard course
made helpful remark; in particular, Abhinav Kumar made observations
about computing widths of cusps, Thomas James Barnet-Lamb about how to
represent Dirichlet characters, and Tseno V. Tselkov, Jennifer
Balakrishnan and Jesse Kass made other remarks.

Parts of Chapter~\ref{ch:modform} follow
\cite[Ch.~VII]{serre:arithmetic} closely, though we adjust the
notation, definitions, and order of presentation to be consistent with
the rest of this book. (For example, Serre writes $2k$ for the weight
instead of~$k$.)

\vspace{2ex}
\noindent{\bf Grant Information.}
This material is based upon work supported by the National Science
Foundation under Grant No. 0400386.

%\section*{TODO}
%\begin{enumerate}
%\item Mention Denis Charles's work on analyzing algorithms,
%computing, etc.
%\end{enumerate}








%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
%   NEW CHAPTER 
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%







\chapter{Modular Forms}\label{ch:modform}

\edit{Write an introduction.}

\section{Basic Definitions}
Modular forms are certain types of functions on
the {\em complex upper half plane}
$$
  \h = \{z \in \C : \Im(z) > 0\}.
$$
The group
$$
 \SL_2(\R) = 
\left\{ \mtwo{a}{b}{c}{d} : ad-bc=1,\text{ and } a,b,c,d\in\R\right\}
$$
acts on $\h$ via linear fractional transformations,
as follows.
If
$\gamma = \abcd{a}{b}{c}{d} \in \SL_2(\R)$ and $z\in\h$,
then (see \exref{ch:modform}{ex:upperhalfpres})
\begin{equation}\label{eqn:lft}
  \gamma(z) = \frac{az + b}{cz + d} \in \h.
\end{equation}

\begin{definition}[Modular Group]
The \defn{modular group} is 
the subgroup $\SL_2(\Z)$ of $\SL_2(\R)$ of matrices
with integer entries.  Thus $\SL_2(\Z)$ is the group of
all matrices $\abcd{a}{b}{c}{d}$ with $a,b,c,d\in\Z$
and $ad-bc=1$.
\end{definition}
For example, the
matrices 
\begin{equation}\label{eqn:ST}
S=\mtwo{0}{-1}{1}{\hfill 0}
\qquad\text{and} \qquad
T=\mtwo{1}{1}{0}{1}
\end{equation} 
are both elements of $\SL_2(\Z)$;
the matrix $S$ defines the function $z\mapsto -1/z$,
and~$T$ the function $z\mapsto z+1$.
\begin{theorem}
The group $\SL_2(\Z)$ is generated by $S$ and $T$.
\end{theorem}
\begin{proof}
  See e.g. \cite[\S{}VII.1]{serre:arithmetic}, which uses the
  fundamental domain~$\cF$ consisting of all elements of $\h$ that
  satisfy $|z|\geq 1$ and $\Re(z)\leq 1/2$.
\end{proof}

%begin_sage
In \sage we compute the group $\SL_2(\Z)$ and its generators as follows:
\begin{verbatim}
sage: G = SL(2,Z)
sage: print G
The modular group SL(2,Z)
sage: S, T = G.gens()
sage: S
[ 0 -1]
[ 1  0]
sage: T
[1 1]
[0 1]
\end{verbatim}
%end_sage

\begin{definition}[Holomorphic and Meromorphic]
  Let $R$ be an open subset of $\C$.  A function $f:R\to \C$ is
  \defn{holomorphic} if $f$ is complex differentiable at every point
  $z\in R$, i.e., for each $z\in R$ the limit $\lim_{h\to 0}
  (f(z+h)-f(z))/h$ exists, where~$h$ may approach~$0$ along any path.
  The function $f: R\to\C\cup \{\infty\}$ is \defn{meromorphic}
    if it is holomorphic except (possibly) at a discrete set $S$ of
    points in~$ R$, and at each $\alpha\in S$ there is a positive
    integer $n$ such that $(z-\alpha)^n f(z)$ is holomorphic at
    $\alpha$.
\end{definition}

The function $f(z) = e^z$ is a holomorphic function on~$\h$
(in fact on all of $\C$).  The function $1/(z-i)$ is meromorphic
on~$\h$, and fails to be analytic at~$i$.

Modular forms are holomorphic functions on $\h$ that transform in a
particular way under a subgroup of $\SL_2(\Z)$.  Before definining
general modular forms, we define modular forms of level $1$.

\section{Modular Forms of Level 1}\label{sec:modform1}


\begin{definition}[Weakly Modular Function]
A \defn{weakly modular function} of weight $k\in\Z$ is a meromorphic
function $f$ on $\h$ such that 
 for all $\gamma=\abcd{a}{b}{c}{d}\in\SL_2(\Z)$ and all $z\in\h$
we have
\begin{equation}\label{eqn:modfunc}
   f(z) = (cz+d)^{-k} f(\gamma(z)).
 \end{equation}
\end{definition}
The constant functions are weakly modular of weight $0$.
There are no nonzero weakly modular functions of odd weight
(see \exref{ch:modform}{ex:nomodformodd}), and it is by
no means obvious that there are any weakly modular functions
of even weight $k\geq 2$.
The product of two weakly modular functions of weights $k_1$
and $k_2$ is a weakly modular function of weight $k_1+k_2$ 
(see \exref{ch:modform}{ex:wmfprod}),
so once we find some nonconstant weakly modular functions, we'll
find many of them.

When $k$ is even (\ref{eqn:modfunc}) has a possibly 
more conceptual interpretation; namely
 (\ref{eqn:modfunc}) is the same as
$$
  f(\gamma(z))d(\gamma(z))^{k/2} = f(z)dz^{k/2}.
$$
Thus (\ref{eqn:modfunc}) simply says that 
the weight~$k$ ``differential form'' $f(z)dz^{k/2}$
is fixed under the action of every element of
$\SL_2(\Z)$.  


Since $\SL_2(\Z)$ is generated by the matrices $S$ and $T$
of (\ref{eqn:ST}), to show
that a meromorphic function~$f$ on $\h$ is a 
weakly modular function all we have to do is show
that for all $z\in\h$ we have 
\begin{equation}\label{eqn:modfunc2}
  f(z+1) = f(z) \qquad\text{and}\qquad f(-1/z) = z^k f(z).
\end{equation}

Suppose that $f$ is a weakly modular function of some weight~$k$.
Then $f$ might have a \defn{Fourier expansion}, which we try to obtain
as follows.  Let $q=q(z)=e^{2\pi i z}$, which we view as a holomorphic
function $\C\union{\infty} \to D$, where $D$ is the closed unit disk.
Let $D'$ be the punctured unit disk, i.e., $D$ with the origin
removed, and note that $q:\C \to D'$.  By (\ref{eqn:modfunc2}) we have
$f(z+1)=f(z)$, so there is a set-theoretic map $F:D' \to \C$ such that
for every $z\in\h$ we have $F(q(z)) = f(z)$.  This function $F$ is
thus a complex-valued function on the open unit disk.  It may or
may not be well behaved at $0$.

Suppose that $F$ is well-behaved at $0$, namely that for some
$m\in\Z$ and all $q$ in a neighborhood of $0$ we have the equality
$$
 F(q) = \sum_{n=m}^{\infty} a_n q^n.
$$
If this is the case, we say that~$f$ is 
\defn{meromorphic at $\infty$}.  If, moreover,
$m\geq 0$, then we say 
that~$f$ is \defn{holomorphic at  $\infty$}.

\begin{definition}[Modular Function]
A \defn{modular function} of weight~$k$ is a weakly modular function
of weight~$k$ that is meromorphic at $\infty$.
\end{definition}

\begin{definition}[Modular Form]
  A \defn{modular form} of weight~$k$ (and level $1$) is a modular
  function of weight~$k$ that is holomorphic on $\h$ and at $\infty$.
\end{definition}

If $f$ is a modular form, then  there are complex numbers
$a_n$ such that for all $z\in \h$, 
\begin{equation}\label{eqn:qexp1}
f(z) = \sum_{n=0}^{\infty} a_n q^n = \sum_{n=0}^{\infty} a_n e^{2 \pi i n z}.
\end{equation}
\begin{proposition}
The above series converges for all $z\in\h$.
\end{proposition}
\begin{proof}n
The function $f(q)$ is holomorphic on $D$, so 
its Taylor series converges absolutely
in $D$.   See also \cite[\S{}VII.4]{serre:arithmetic}
for an explicit bound on the $|a_n|$.
\end{proof}
We set $f(\infty)=a_0$, since $q^{2\pi i z}\to 0$ as 
$z\to i \infty$, and the value of $f$ at $\infty$
should be the value of $F$ at $0$, which is $a_0$
from the power series. 

\begin{definition}[Cusp Form]
A \defn{cusp form}  of weight~$k$ (and level $1$) is a modular form of 
weight~$k$ such that $f(\infty)=0$, i.e., $a_0=0$.
\end{definition}


\section{Modular Forms of Any Level}\label{sec:modformN}
We next define spaces of modular forms of arbitrary level.  For
example, when $k=2$ these are closely related to elliptic curves and
abelian varieties.

A \defn{congruence subgroup} of
$\SL_2(\Z)$ is any subgroup that contains
$$\Gamma(N) = \ker(\SL_2(\Z)\to \SL_2(\Z/N\Z))$$ 
for some $N$.  The smallest such~$N$ is the \defn{level} of $\Gamma$.
For example, 
$$
  \Gamma_1(N) = \left\{ \mtwo{a}{b}{c}{d} \in \SL_2(\Z) : 
                    \mtwo{a}{b}{c}{d}\con \mtwo{1}{*}{0}{1}\pmod{N}
                \right\}
$$
and
$$
  \Gamma_0(N) = \left\{ \mtwo{a}{b}{c}{d} \in \SL_2(\Z) : 
                    \mtwo{a}{b}{c}{d}\con \mtwo{*}{*}{0}{*}\pmod{N}
                \right\}
$$
are congruence subgroups of level~$N$.

Let $k$ be an integer.
Define the \defn{weight~$k$ right action} of $\GL_2(\Q)$ on 
the set of functions~$f:\h\to\C$  as follows.  
If $\gamma=\abcd{a}{b}{c}{d}\in\GL_2(\Q)$, let
$$
  f|[\gamma]_k = \det(\gamma)^{k-1} (cz+d)^{-k} f(\gamma(z)).
$$
\begin{proposition}
The action $f\mapsto f|[\gamma]_k$ is a right action
of $\GL_2(\Z)$ on the set of all functions $f:\h\to\C$; in
particular, 
$$
  f|[\gamma_1\gamma_2]_k = (f|[\gamma_1]_k)|[\gamma_2]_k,
$$
\end{proposition}
\begin{proof}
See \exref{ch:modform}{ex:grpact}.
\end{proof}

\begin{definition}[Weakly Modular Function]
A \defn{weakly modular function} of weight $k$ for a
congruence subgroup $\Gamma$ is a meromorphic
function $f :\h \to \C$ such that 
$f|[\gamma]_k = f$ for all $\gamma \in \Gamma$.
\end{definition}

A central object in the theory of modular forms (and modular symbols)
is the set of all {\em cusps}
$$
  \P^1(\Q) = \Q \union \{\infty\}.
$$
The set of cusps for a congruence subgroup $\Gamma$ is the set
$C(\Gamma)$ of orbits of $\P^1(\Q)$ under the action of $\Gamma$.  (We
will often identify elements of $C(\Gamma)$ with a representative
element from the orbit.)  For example, if $\Gamma=\SL_2(\Z)$ there is
exactly one orbit.
\begin{lemma}\label{lem:sl2ztrans}
  For any cusps $\alpha, \beta\in\P^1(\Q)$ there exists
  $\gamma\in\SL_2(\Z)$ such that $\gamma(\alpha) = \beta$.
\end{lemma}
\begin{proof}
This is \exref{ch:modform}{ex:sl2ztrans}.
\end{proof}

\begin{proposition}
For any congruence subgroup $\Gamma$, the set $C(\Gamma)$
of cusps is finite. 
\end{proposition}

In order to define modular forms for general congruence subgroups we
need to make sense of what it means for a function to be holomorphic
on the \defn{extended upper halfplane}
$$
  \h^* = \h\union \P^1(\Q).
$$
In Section~\ref{sec:modform1} we considered a weakly modular
function~$f$ on $\SL_2(\Z)$
to be holomorphic at~$\infty$ if its $q$-expansion 
is of the form
$\sum_{n=0}^{\infty} a_n q^n$.

In order to make sense of holomorphicity of a weakly modular
function $f$  for $\Gamma$ at any $\alpha\in\Q$,
we first prove a lemma.
\begin{lemma}
If $f :\h\to\C$ is a weakly modular function of weight $k$
for a congruence subgroup $\Gamma$, and $\delta \in \SL_2(\Z)$,
then $f|[\delta]_k$ is a weakly modular function for
$\delta^{-1}\Gamma \delta$.
\end{lemma}
\begin{proof}
If $s = \delta^{-1} \gamma\delta \in \delta^{-1}\Gamma \delta$,
then 
$$ 
   (f|[\delta]_k)|[s]_k = f|[\delta s]_k
          = f|[\delta \delta^{-1}\gamma\delta]_k
          = f|[\gamma\delta]_k = f|[\delta]_k.
$$
\end{proof}

Fix a weight~$k$ weakly modular function~$f$ for some congruence
subgroup~$\Gamma$, and suppose $\alpha \in \Q$.  In
Section~\ref{sec:modform1} we constructed the $q$-expansion of $f$ by
using that $f(z) = f(z+1)$, which held since
$T=\mtwo{1}{1}{0}{1}\in\SL_2(\Z)$.  Unfortunately, there are
congruence subgroups $\Gamma$ such that $T\not\in\Gamma$.  Moreover,
even if we are interested only in modular forms for $\Gamma_1(N)$,
where we have $T\in\Gamma_1(N)$ for all~$N$, we have to consider
$q$-expansions at infinity for modular forms on groups $\delta^{-1}
\Gamma_1(N)\delta$, and these need not contain~$T$.  Fortunately, $T^N
= \mtwo{1}{N}{0}{1} \in \Gamma(N)$, so a congruence subgroup of level
$N$ contains $T^N$.  Thus for our $f$ we have $f(z+h) = f(z)$ for some
positive integer $h$, and again when~$f$ is meromorphic at infinity we
obtain a Fourier expansion
\begin{equation}\label{eqn:qser}
   f(z) = \sum_{n=m}^{\infty} a_n q^{n/N},
\end{equation}
but instead it is in powers of the function $q^{1/N} = e^{2 \pi i z
  /N}$.  We say that $f$ is holomorphic at $\infty$ if in
(\ref{eqn:qser}) we have $m\geq 0$.  

What about the other cusps $\alpha\in\P^1(\Q)$? By
Lemma~\ref{lem:sl2ztrans} there is a $\gamma\in\SL_2(\Z)$ such that
$\gamma(\infty)=\alpha$.  We declare~$f$ to be \defn{holomorphic at
  the cusp~$\alpha$} if the weakly modular function $f|[\gamma]_k$ is
holomorphic at $\infty$.

\begin{definition}[Modular Form]
A {\em modular form} of integer weight $k$ for a congruence subgroup
$\Gamma$ is a weakly modular function $f:\h^*\to \C$ that
is holomorphic on $\h^*$.
\end{definition}

\begin{proposition}
A weakly modular function $f$ of weight $k$ for $\Gamma$
is holomorphic at every element of $\P^1(\Q)$ if 
 is holomorphic at a set of representative elements
for $C(\Gamma)$.
\end{proposition}
\begin{proof}
Let $c_1,\ldots, c_n \in \P^1(\Q)$ be representatives
for the set of cusps for $\Gamma$.
If $\alpha \in \P^1(\Q)$ then there is $\gamma\in\Gamma$
such that $\alpha = \gamma(c_i)$ for some $i$.
By hypothesis $f$ is holomorphic at $c_i$, so if $\delta\in\SL_2(\Z)$
is such that $\delta(\infty) = c_i$, then $f|[\delta]_k$
is holomorphic at $\infty$.  Since $f$ is a weakly modular
function,
\begin{equation}\label{eqn:prop:holoall}
  f|[\delta]_k = (f|[\gamma]_k)|[\delta]_k = f|[\gamma\delta]_k.
\end{equation}
But $\gamma(\delta(\infty)) = \gamma(c_i) = \alpha$, so 
(\ref{eqn:prop:holoall}) implies that $f$ is holomorphic 
at~$\alpha$.
\end{proof}


\subsection{Computing Widths of Cusps}
Let $\Gamma$ be a congruence subgroup of level~$N$.  Suppose
$\alpha\in C(\Gamma)$ is a cusp, and choose $\gamma\in\SL_2(\Z)$ such
that $\gamma(\infty)=\alpha$.  The minimal $h$ such that
$\abcd{1}{h}{0}{1} \in \gamma^{-1}\Gamma\gamma$ is called the
\defn{width} of the cusp $\alpha$ for the group $\Gamma$.  In this
section we discuss how to compute~$h$.

\begin{algorithm}{Width of Cusp}
  Given a congruence subgroup $\Gamma$ of level $N$ and a cusp
  $\alpha$ for $\Gamma$, this algorithm computes the width $h$ of
  $\alpha$.  We assume that $\Gamma$ is given by congruence conditions,
e.g., $\Gamma=\Gamma_0(N)$ or $\Gamma_1(N)$.
\begin{steps}
\item{}[Find $\gamma$] Use the extended Euclidean algorithm
to find $\gamma\in\SL_2(\Z)$ such that $\gamma(\infty)=\alpha$,
as follows.
If $\alpha=\infty$ set $\gamma\set 1$; otherwise, write 
$\alpha=a/b$, find $c,d$ such that $ad-bc=1$, and set
$\gamma \set \abcd{a}{b}{c}{d}$.
\item{}[compute Conjugate Matrix] Compute the following matrix in $M_2(\Z[x])$:
$$
  \delta(x) \set \gamma \mtwo{1}{x}{0}{1} \gamma^{-1}.
$$
Note that the entries of $\delta(x)$ are constant or
linear in $x$.
\item{}[Solve] The congruence conditions that define $\Gamma$ give
  rise to four linear congruence conditions on $x$.  Use techniques
  from elementary number theory (or enumeration) to find the smallest
  simultaneous positive solution $h$ to these four equations.
\end{steps}
\end{algorithm}

\begin{example}
\begin{enumerate}
\item
Suppose $\alpha=0$ and $\Gamma=\Gamma_0(N)$ or $\Gamma_1(N)$.
Then $\gamma=\abcd{0}{1}{1}{0}$ has the property that $\gamma(\infty)=\alpha$.
Next, the congruence condition is 
$$\delta(x) = \gamma \mtwo{1}{x}{0}{1} \gamma^{-1} = \mtwo{1}{0}{x}{1} 
  \con \mtwo{1}{*}{0}{1}\pmod{N}.
$$
Thus the smallest positive solution is $h=N$, so the width of $0$
is~$N$.

\item Suppose $N=pq$ where $p,q$ are distinct primes, and let $\alpha=1/p$.
Then $\gamma=\abcd{1}{0}{p}{1}$ sends $\infty$ to $\alpha$.
The congruence condition for $\Gamma_0(pq)$ is 
$$
\delta(x) = \gamma \mtwo{1}{x}{0}{1} \gamma^{-1} = \mtwo{1-px}{x}{-p^2 x}{px+1}
  \con \mtwo{*}{*}{0}{*}\pmod{pq}.
$$
Since $p^2x \con 0\pmod{pq}$, we see that $x=q$ is the smallest solution.
Thus $1/p$ has width $q$, and symmetrically $1/q$ has width~$p$.
\end{enumerate}
\end{example}
\begin{remark}
For $\Gamma_0(N)$, once we enforce that the bottom 
left entry is $0\pmod{N}$, and use that the determinant is 1, the 
coprimality from the other two congruences is automatic.
So there is one congruence to solve in the $\Gamma_0(N)$ case.
There are 2 congruences in the $\Gamma_1(N)$ case. 
\end{remark}




\section{Examples of Modular Forms of Level $1$}\label{sec:level_one_eisen}

In this section you will finally see some examples of modular forms of
level $1$!  We will first introduce the Eisenstein series, one of each
weight, then define $\Delta$, which is a cusp form of weight $12$.  In
Section~\ref{sec:struct1} we will prove the structure theorem,
which says that using addition and multiplication of these forms, we
can generate all modular forms of level $1$.

For an even integer $k\geq 4$, the \defn{non-normalized weight~$k$
  Eisenstein series} is
$$
  G_k(z) = \sum_{m,n\in\Z}^{*} \frac{1}{(mz+n)^k},
$$
where for a given $z$, the sum is over all $m,n\in\Z$ such that
$mz+n\neq 0$.

\begin{proposition}
The function $G_k(z)$ is a modular form of weight~$k$, i.e.,
 $ G_k \in M_k(\SL_2(\Z))$.
\end{proposition}
\begin{proof}
See \cite[\S{} VII.2.3]{serre:arithmetic} for a proof
that $G_k(z)$ defines a holomorphic function on $\h^*$.
To see that $G_k$ is modular, observe that
$$
  G_k(z+1) = \sum^* \frac{1}{(m(z+1)+n)^k} = \sum^* \frac{1}{(mz+(n+m))^k} = 
\sum^* \frac{1}{(mz+n)^k},
$$
and
$$
G_k(-1/z) = \sum^* \frac{1}{(-m/z+n)^k} = \sum^* \frac{z^k}{(-m+nz)^k}
  = z^k \sum^* \frac{1}{(mz+n)^k} = z^k G_k(z).
$$
\end{proof}

\begin{proposition}
$G_k(\infty) = 2\zeta(k)$,
where $\zeta$ is the Riemann zeta function.
\end{proposition}
\begin{proof}
Taking the limit as $z\to i\infty$ in the definition 
of $G_k(z)$, we obtain $\sum^*_{n\in\Z} \frac{1}{n^k}$, since
the terms involving $z$ all go to $0$ as $z\mapsto i\infty$.  
This sum is twice $\zeta(k) = \sum_{n\geq 1} \frac{1}{n^k}$.
\end{proof}

For example, 
$$G_4(\infty) = 2\zeta(4) = \frac{1}{3^2\cdot 5} \pi^4$$
and 
$$G_6(\infty) = 2\zeta(6) = \frac{2}{3^3\cdot 5\cdot 7} \pi^6.$$


\subsection{The Cusp Form $\Delta$}
Suppose $E=\C/\Lambda$ is an elliptic curve over $\C$, viewed as a quotient
of $\C$ by a lattice $\Lambda=\Z\omega_1+\Z\omega_2$, with $\omega_1/\omega_2\in\h$.
Then
$$
  \wp_{\Lambda}(u) = \frac{1}{u^2} + \sum_{k=4,\text{ ($k$ even)}}^{\infty} (k-1)
      G_k(\omega_1/\omega_2) u^{k-2},
$$
and 
$$
  (\wp')^2 = 4\wp^3 - 60 G_4(\omega_1/\omega_2) \wp - 140 G_6(\omega_1/\omega_2).
$$
The discriminant of the cubic $4x^3 - 60G_4(\omega_1/\omega_2) x - 
140 G_6(\omega_1/\omega_2)$ is $16\Delta(\omega_1/\omega_2)$, where
$$
 \Delta = (60 G_4)^3 - 27(140 G_6)^2
$$
is a cusp form of weight $12$.  
\begin{lemma}\label{lem:delnz}
The cusp form $\Delta$ has a $0$ only at $\infty$.
\end{lemma}
\begin{proof}
Let $\omega_1, \omega_2$ be as above.
Since~$E$ is an elliptic curve, $\Delta(\omega_1/\omega_2)\neq 0$.
\end{proof}

\subsection{Fourier Expansions of Eisenstein Series}
Recall from (\ref{eqn:qexp1}) that elements $f$ of $M_k(\SL_2(\Z))$ can be
expressed as formal power series in terms of $q(z)=e^{2\pi i z}$, and
that this expansion is called the Fourier expansion of $f$.
The following proposition gives the Fourier expansion of the
Eisenstein series $G_k(z)$.

\begin{proposition}\label{prop:qexpGk}
For every even integer $k\geq 4$, we have
$$
  G_k(z) = 2\zeta(k) + 2\cdot \frac{(2\pi i)^{k}}{(k-1)!}\cdot
     \sum_{n=1}^{\infty} \sigma_{k-1}(n) q^n,
$$
where $\sigma_d(n)$ is the sum of the $d$th powers of the divisors
of~$n$.
\end{proposition}
\begin{proof}
  See \cite[\S VII.4]{serre:arithmetic}, which uses a series of clever
  manipulations of series, starting with the identity
$$
  \pi \cot(\pi z) = \frac{1}{z} + \sum_{m=1}^{\infty} 
     \left( \frac{1}{z+m} + \frac{1}{z-m}\right).
$$
\end{proof}

From a computational point of view, the $q$-expansion for $G_k$ from
Proposition~\ref{prop:qexpGk} is unsatisfactory, because it involves
transcendental numbers.  To understand more clearly what is going on,
we introduce the \defn{Bernoulli numbers} $B_n$ for $n\geq 0$ 
{\em defined} by the following equality of formal power series:
\begin{equation}\label{eqn:def_bernoulli}
  \frac{x}{e^x - 1} = \sum_{n=0}^{\infty} B_n \frac{x^n}{n!}.
\end{equation}
Expanding the power series on the left we have $$
\frac{x}{e^x - 1} =
1 - \frac{x}{2} + \frac{x^2}{12} - \frac{x^4}{720} + \frac{x^6}{30240}
- \frac{x^8}{1209600} + \cdots $$
As this expansion suggests, the
Bernoulli numbers $B_n$ with $n>1$ odd are~$0$ (see
\exref{ch:modform}{ex:odd_bernoulli}).
Expanding the series further, we obtain the following table:
\vspace{0.5ex}

\noindent{}$\ds B_{0}=1,\quad B_{1}=-\frac{1}{2},\quad B_{2}=\frac{1}{6},\quad
B_{4}=-\frac{1}{30},\quad B_{6}=\frac{1}{42},\quad
B_{8}=-\frac{1}{30},\quad $\vspace{1.5ex}

\noindent{}$\ds
B_{10}=\frac{5}{66},\quad
B_{12}=-\frac{691}{2730},\quad
B_{14}=\frac{7}{6},\quad
B_{16}=-\frac{3617}{510},\quad
B_{18}=\frac{43867}{798},\quad
$\vspace{1.5ex}

\noindent{}
$\ds{}\!\!B_{20}=-\frac{174611}{330},\quad
B_{22}=\frac{854513}{138},\quad
B_{24}=-\frac{236364091}{2730},\quad
B_{26}=\frac{8553103}{6}.
%B_{28}=-\frac{23749461029}{870},\quad
$\vspace{1ex}

%begin_sage
Use the \code{bernoulli} command to compute Bernoulli
numbers in \sage. 
\begin{verbatim}
sage: bernoulli(12)
-691/2730
sage: bernoulli(50)
495057205241079648212477525/66
\end{verbatim}
%end_sage


For us, the significance of the Bernoulli numbers is their connection
with values of~$\zeta$ at positive even integers.
\begin{proposition}\label{prop:zeta_even}
If $k\geq 2$ is an even integer, then
$$
  \zeta(k) = -\frac{(2\pi i)^{k}}{2\cdot k!}\cdot B_k.
$$
\end{proposition}
\begin{proof}
The proof in \cite[\S VII.4]{serre:arithmetic} 
involves manipulating a power series expansion for $z \cot(z)$.
\end{proof}

\begin{definition}[Normalized Eisenstein Series]
The \defn{normalized Eisenstein series} of even weight~$k\geq 4$ is
$$
  E_k = \frac{(k-1)!}{2\cdot (2\pi i)^k}\cdot G_k 
$$
\end{definition} 
Combining Propositions~\ref{prop:qexpGk} and
\ref{prop:zeta_even} we see that
\begin{equation}\label{eqn:ekexp}
 E_k = -\frac{B_k}{2k} + q + \sum_{n=2}^{\infty} \sigma_{k-1}(n) q^n.
\end{equation}
It is thus now simple to explicitly write down Eisenstein series
(see \exref{ch:modform}{ex:expeis}).


\begin{warning} Our series $E_k$ is normalized so that the coefficient
  of~$q$ is~$1$, but often in the literature $E_k$ is normalized so
  that the constant coefficient is~$1$.  We use the normalization with
  the coefficient of~$q$ equal to~$1$, because then the eigenvalue of
  the $n$th Hecke operator (see Section~\ref{sec:hecke_one}) is the
  coefficient of~$q^n$.  Our normalization is also 
  convenient when considering congruences between cusp forms and
  Eisenstein series.
\end{warning}

\section{Structure Theorem}\label{sec:struct1}
If $f$ is a nonzero meromorphic function on $\h$ and $w\in\h$, let
$\ord_w(f)$ be the largest integer~$n$ such that $f/(w-z)^n$ is
holomorphic at $w$.  If $f = \sum_{n=m}^{\infty} a_n q^n$ with
$a_m\neq 0$, let $\ord_{\infty}(f)=m$.  We will use the following
theorem to give a presentation for the vector space of modular forms
of weight~$k$; this presentation will allow us to obtain an algorithm
to compute a basis for this space.

Let $\cF$ be the subset of $\h$ of numbers $z$ with $|z|\geq 1$ and
$\Re(z)\leq 1/2$.  This is the standard fundamental domain for
$\SL_2(\Z)$.

\begin{theorem}[Valence Formula]\label{thm:valence}
Suppose $f \in M_k(\SL_2(\Z))$ is nonzero.  Then
$$
  \ord_{\infty}(f) + \frac{1}{2}\ord_i(f) + \frac{1}{3} \ord_{\rho}(f)
   + \sum_{w\in D}^* \ord_w(f) = \frac{k}{12},
$$
where $\ds \sum^*_{w \in D}$ is the sum over elements of $\cF$
other than~$i$ or~$\rho$.
\end{theorem}
\begin{proof}
Serre proves this theorem in \cite[\S{}VII.3]{serre:arithmetic} using
the residue theorem from complex analysis.
\end{proof}

Let $M_k=M_k(\SL_2(\Z))$ denote the complex vector space of modular
forms of weight~$k$ for $\SL_2(\Z)$, and let~$S_k=S_k(\SL_2(\Z))$
denote the subspace of weight~$k$ cusp forms for $\SL_2(\Z)$.  We have
an exact sequence
$$
  0 \to S_k \to M_k \to \C 
$$
that sends $f\in M_k$ to $f(\infty)$.  When $k\geq 4$ is even, the
space $M_k$ contains the Eisenstein series $G_k$ and
$G_k(\infty)=2\zeta(k)\neq 0$, so the map $M_k\to \C$ is surjective,
so the following sequence is exact:
$$
  0 \to S_k \to M_k \to \C  \to 0  \qquad\text{(when $k\geq 4$ is even)}
$$

Thus when $k\geq 4$ is even $\dim(S_k)=\dim(M_k)-1$ hence
$$
  M_k = S_k \oplus \C G_k.
$$

\begin{proposition}\label{prop:mk_vanish}
For $k<0$ and $k=2$, we have $M_k=0$.  
\end{proposition}
\begin{proof}
Suppose $f\in M_k$ is nonzero yet $k=2$ or $k<0$.  By 
Theorem~\ref{thm:valence}, 
$$
  \ord_{\infty}(f) + \frac{1}{2}\ord_i(f) + \frac{1}{3} \ord_{\rho}(f)
   + \sum_{w\in D}^* \ord_w(f) = \frac{k}{12}\leq 1/6.
$$
This is impossible because each quantity on the left-hand
side is nonnegative so whatever the sum is, it is too big
(or $0$, in which $k=0$).
\end{proof}

\begin{theorem}\label{thm:delta_iso}
Multiplication by $\Delta$ defines an isomorphism $M_{k-12}\to S_k$.
\end{theorem}
\begin{proof}
(We follow \cite[\S{}VII.3.2]{serre:arithmetic} closely.)
We apply Theorem~\ref{thm:valence} to $G_4$ and~$G_6$.
If $f=G_4$, then
$$
  \ord_{\infty}(f) + \frac{1}{2}\ord_i(f) + \frac{1}{3} \ord_{\rho}(f)
   + \sum_{w\in D}^* \ord_w(f) = \frac{4}{12} = \frac{1}{3},
$$
with the $\ord$s all nonnegative,
so $\ord_{\rho}(G_4) = 1$ and $\ord_w(G_4) = 0$ for all $w\neq \rho$.
Likewise $\ord_{i}(G_6) = 1$ and $\ord_w(G_6) = 0$ for all $w\neq i$.
Thus $\Delta(i)\neq 0$, so $\Delta$ is not identically~$0$ (this
also follows from Lemma~\ref{lem:delnz} above).
Since $\Delta$ has weight~$12$ and $\ord_\infty(\Delta)\geq 1$,
Theorem~\ref{thm:valence} implies that~$\Delta$ has a simple
zero at $\infty$ and does not vanish on~$\h$.
Thus if $f\in S_k$ and we let $g=f/\Delta$, then $g$ is holomorphic
and satisfies the appropriate transformation formula, so~$g$
is a modular form of weight $k-12$.
\end{proof}

\begin{corollary}
  For $k=0,4,6,8,10,14$, the vector space $M_k$ has dimension~$1$, with
  basis $1$, $G_4$, $G_6$, $E_8$, $E_{10}$, and $E_{14}$, respectively, and
  $S_k=0$.
\end{corollary}
\begin{proof}
  Combining Proposition~\ref{prop:mk_vanish} with
  Theorem~\ref{thm:delta_iso} we see that the spaces $M_k$ for $k\leq
  10$ can not have dimension bigger than~$1$, since then $M_{k'}\neq
  0$ for some $k'<0$.  Also $M_{14}$ has dimension at most $1$, since
  $M_2$ has dimension $0$.  Each of the indicated spaces of weight
  $\geq 4$ contains the indicated Eisenstein series, so has
  dimension~$1$, as claimed.
\end{proof}

\begin{corollary}\label{cor:dim1}
$\dim M_k = \begin{cases}
   0 & \text{if }k\text{ is odd}, \\ 
   \lfloor{} k/12 \rfloor{} & \text{if } k\con 2\pmod{12},\\
   \lfloor{} k/12 \rfloor{}+1 & \text{if } k\not\con 2\pmod{12},
\end{cases}
$
where $\lfloor{}x \rfloor{}$ is the biggest integer $\leq x$.
\end{corollary}
\begin{proof}
As we have seen above, the formula is true when $k\leq 12$.
By Theorem~\ref{thm:delta_iso}, the dimension increases by $1$
when~$k$ is replaced by $k+12$.
\end{proof}

\begin{theorem}\label{thm:mk_one_basis}
The space $M_k$ has as basis the
modular forms $G_4^a G_6^b$, where $a,b$
are all pairs of nonnegative integers such that 
$4a+6b=k$.
\end{theorem}
\begin{proof}
We first prove by induction that the modular forms
$G_4^a G_6^b$ generate $M_k$, the cases $k\leq 12$
being clear (e.g., when $k=0$ we have $a=b=0$ and basis~$1$).
Choose some pair of integers $a,b$ such that $4a+6b=k$ 
(it is an elementary exercise to show these exist).
The form $g=G_4^a G_6^b$ is not a cusp form, since
it is nonzero at $\infty$.  Now suppose $f\in M_k$
is arbitrary.  Since $M_k = S_k \oplus \C G_k$, there
is $\alpha\in\C$ such that $f - \alpha g \in S_k$.
Then by Theorem~\ref{thm:delta_iso}, there is $h \in M_{k-12}$
such that $f - \alpha g = \Delta h$.  By induction,
$h$ is a polynomial in $G_4$ and $G_6$ of the required
type, and so is $\Delta$, so $f$ is as well.

Suppose there is a nontrivial linear relation between the $G_4^a
G_6^b$ for a given~$k$.  By multiplying the linear relation by a
suitable power of $G_4$ and $G_6$, we may assume that that we have
such a nontrivial relation with $k\con 0\pmod{12}$.  Now divide the
linear relation by $G_6^{k/12}$ to see that $G_4^3/G_6^2$ satisfies a
polynomial with coefficients in $\C$.  Hence $G_4^3/G_6^2$ is a root
of a polynomial, hence a constant, which is a contradiction since the
$q$-expansion of $G_4^3/G_6^2$ is not constant.
\end{proof}

\begin{algorithm}{Basis for $M_k$}\label{alg:basis}
Given integers~$n$ and~$k$, this algorithm computes
a basis of $q$-expansions for the complex vector
space $M_k$ mod $q^n$.   The $q$-expansions output
by this algorithm have coefficients in $\Q$.
\begin{steps}
\item{}[Simple Case] If $k=0$ output the basis with
just $1$ in it, and terminate; otherwise if $k<4$ or~$k$ 
is odd, output the empty basis and terminate.
\item{}[Power Series] Compute $E_4$ and $E_6$ mod $q^n$
using the formula from (\ref{eqn:ekexp}) and
the definition (\ref{eqn:def_bernoulli}) of Bernoulli
numbers.\edit{Look up what the {\em real} algorithm
for doing this is.}
\item{}[Initialize] Set $b\set 0$.   
%Precompute the powers $E_4^2, E_4^3, \ldots E_4^m$ mod $q^n$,
%where $m=\lfloor{} k/4\rfloor{}$, and likewise for
%$E_6$, but with $m=\lfloor{} k/6\rfloor{}$.
\item{}[Enumerate Basis] For each integer~$b$ between~$0$ and
$\lfloor k/6\rfloor$, compute $a=(k-6b)/4$.
If~$a$ is an integer, compute and output the basis
element $E_4^a E_6^b \mod{q^n}$.  When we compute, e.g.,
$E_4^a$, do the computation by finding
$E_4^m\pmod{q^n}$ for each $m\leq a$, and save these
intermediate powers, so they can be reused later, and
likewise for powers of $E_6$.
\end{steps}
\end{algorithm}
\begin{proof}
This is simply a translation of Theorem~\ref{thm:mk_one_basis}
into an algorithm, since $E_k$ is a nonzero scalar multiple
of $G_k$.  That the $q$-expansions have coefficients
in $\Q$ follows from (\ref{eqn:ekexp}).
\end{proof}

\begin{example}
We compute a basis for $M_{24}$, which is the space with
smallest weight whose dimension is bigger than $1$.
It has as basis $E_4^6$, $E_4^3 E_6^2$, and $E_6^4$, whose explicit
expansions are
\begin{align*}
  E_4^6 &= \frac{1}{191102976000000} +
   \frac{1}{132710400000}q + \frac{203}{44236800000}q^2 + \cdots\\
E_4^3 E_6^2 &= 
    \frac{1}{3511517184000} - \frac{1}{12192768000}q - \frac{377}{4064256000}q^2
  + \cdots \\
  E_6^4 &= \frac{1}{64524128256} - \frac{1}{32006016}q + 
    \frac{241}{10668672}q^2 +\cdots 
\end{align*}
\end{example}

In Section~\ref{sec:vmthesis}, we will discuss properties
of the reduced row echelon form of any basis for $M_k$, which
have better properties than the above basis.


\section{The Victor Miller Basis}\label{sec:vmthesis}
\begin{lemma}[Victor Miller]\label{lem:vm}
The space $S_k$ has a basis $f_1,\ldots, f_{d}$ such
that if $a_i(f_j)$ is the $i$th coefficient of $f_j$, then
$a_i(f_j) = \delta_{i,j}$ for $i=1,\ldots, {d}$.  Moreover
the $f_j$ all lie in $\Z[[q]]$.
\end{lemma}
This is a straightforward construction involving $E_4$, $E_6$ and
$\Delta$.  The following proof very closely follows \cite[Ch.~X,
Thm.~4.4]{lang:modular}, which is in turn follows the
first lemma of Victor Miller's thesis.
\begin{proof}
Let $d=\dim S_k$.
Since $B_4 = -1/30$ and $B_6=1/42$, we note that
$$
 F_4 = -\frac{8}{B_4} \cdot E_4 = 1 + 240q + 2160q^2 + 6720q^3 + 17520q^4 + \cdots
$$ and 
$$
  F_6 = -\frac{12}{B_6}\cdot E_6 = 1 - 504q - 16632q^2 - 122976q^3 - 532728q^4
+\cdots 
$$
have $q$-expansions in $\Z[[q]]$ with leading
coefficient~$1$.
Choose integers $a,b\geq 0$ such that 
$$
  4a+6b\leq 14 \qquad\text{and}\qquad 4a + 6b \con k \pmod{12},
$$
with $a=b=0$ when $k\con 0\pmod{12}$, and
let 
$$
  g_j = \Delta^j F_6^{2(d-j)+a} F_4^b,\qquad\qquad \text{for } j=1,\ldots,d.
$$
Then
$$
 a_j(g_j) = 1, \qquad\text{and}\qquad a_i(g_j)=0\qquad\text{when}\qquad i<j.
$$
Hence the $g_j$ are linearly independent over $\C$, and thus form
a basis for $S_k$.  Since $F_4, F_6$, and $\Delta$ are all in $\Z[[q]]$,
so are the $g_j$.  The $f_i$ may then be constructed from the $g_j$
by Gauss elimination.  The coefficients of the resulting power series lie in 
$\Z$ because each time we clear a column we use the power series
$g_j$ whose leading coefficient is $1$ (so no denominators are introduced).
\end{proof}
\begin{remark}
The basis coming from Victor Miller's lemma is canonical, 
since it is just the reduced row echelon form of any basis.
Also the {\em integral} linear combinations are precisely
the modular forms of level $1$ with integral $q$-expansion.
\end{remark}

We extend the Victor Miller basis to all $M_k$ by taking
a multiple of $G_k$ with constant term $1$, and subtracting
off the $f_i$ from the Victor Miller basis so that the
coefficients of $q, q^2, \ldots q^d$ of 
the resulting expansion are $0$.  We call the extra basis
element $f_0$.
\edit{Argue: Is $G_k$ integral?}




\begin{example}
If $k=24$, then $d=2$.  Choose $a=b=0$, since $k\con 0\pmod{12}$.
Then 
$$g_1 = \Delta F_6^2 = 
q - 1032q^2 + 245196q^3 + 10965568q^4 + 60177390q^5 - \cdots
$$
and 
$$
g_2 = \Delta^2 = q^2 - 48q^3 + 1080q^4 - 15040q^5 + \cdots
$$
We let $f_2=g_2$ and 
$$ 
f_1 = g_1 + 1032 g_2
 = q + 195660q^3 + 12080128q^4 + 44656110q^5 - \cdots.
$$
\end{example}
\examplesession{
> n4 := Newforms(MF(1,4))[1][1];
> F4 := n4*240;
> F4;
1 + 240*q + 2160*q^2 + 6720*q^3 + 17520*q^4 + 30240*q^5 + 
60480*q^6 + 82560*q^7 + O(q^8)
> n6 := Newforms(MF(1,6))[1][1];
> n6
> ';

>> ';
     ^
User error: Unexpected newline in literal identifier
> n6;
-1/504 + q + 33*q^2 + 244*q^3 + 1057*q^4 + 3126*q^5 + 8052*q^6 + 
16808*q^7 + O(q^8)
> F6 := n6*(-504);
> F4;
1 + 240*q + 2160*q^2 + 6720*q^3 + 17520*q^4 + 30240*q^5 + 
60480*q^6 + 82560*q^7 + O(q^8)
> F6;
1 - 504*q - 16632*q^2 - 122976*q^3 - 532728*q^4 - 1575504*q^5 - 
4058208*q^6 - 8471232*q^7 + O(q^8)
> Delta := Newforms(CS(MF(1,12)))[1][1];
> Delta;
q - 24*q^2 + 252*q^3 - 1472*q^4 + 4830*q^5 - 6048*q^6 - 16744*q^7
+ O(q^8)
> Delta*F6^2;
q - 1032*q^2 + 245196*q^3 + 10965568*q^4 + 60177390*q^5 - 
1130921568*q^6 + 870123128*q^7 + O(q^8)
> Delta^2;
q^2 - 48*q^3 + 1080*q^4 - 15040*q^5 + 143820*q^6 - 985824*q^7 + 
O(q^8)
> 1032*Delta^2 + Delta*F6^2;
q + 195660*q^3 + 12080128*q^4 + 44656110*q^5 - 982499328*q^6 - 
147247240*q^7 + O(q^8)
> S := CS(MF(1,36));
> Basis(S);
[
    q + 57093088*q^4 + 37927345230*q^5 + 5681332472832*q^6 + 
    288978305864000*q^7 + O(q^8),
    q^2 + 194184*q^4 + 7442432*q^5 - 197264484*q^6 + 
    722386944*q^7 + O(q^8),
    q^3 - 72*q^4 + 2484*q^5 - 54528*q^6 + 852426*q^7 + O(q^8)
]
}

\begin{example}
When $k=36$, the Victor Miller basis, including $f_0$, is
\begin{align*}
f_0 &= 1 + \quad\,\,\, 6218175600q^4 + 15281788354560q^5 + \cdots\\
 f_1 &= \,\,\,\,\,\,  q + \quad\,\, 57093088q^4 + \,\,\,\,\,\,\,\,\,\,37927345230q^5 +\cdots\\
 f_2 &=  \qquad q^2 +  \,\,\,\,\,\,194184q^4 + \quad\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, 7442432q^5 + \cdots \\
 f_3 &=  \qquad\quad\,\, q^3 -\,\,\,\,\,\,\,\,\,\, 72q^4 +\qquad\quad\,\,\,\,\,\,\,\,\,\,\,\,  2484q^5 + \cdots
\end{align*}
\end{example}


\begin{remark}
%(Elkies) 
%\begin{enumerate}
%\item 
If you wish to write $f \in M_k$ as a polynomial
  in~$E_4$ and~$E_6$, then it is wasteful to compute the Victor
Miller basis.
  Instead, use the upper triangular basis $\Delta^j F_6^{2(d-j)+a} F_4^b$,
  and match coefficients from $q^0$ to $q^d$.  

%\item When $4\mid{}k$, the zeroth form $f_0$ in the Miller basis is also
%  the theta function of an extremal self-dual even lattice
%  of dimension $2k$ (if one exists).  More generally, if a lattice
%  is with $c$ of extremality then its theta function differs from $f_0$
%  by a linear combination of  $f_d, f_{d-1}, ..., f_{d+1-c}$.
%\end{enumerate}
\end{remark}

\section{Hecke Operators}\label{sec:hecke_one}
For any positive integer~$n$, let
$$
S_n = \left\{\mtwo{a}{b}{0}{d} \in M_2(\Z) \,\,:\,\,
a\geq 1,\,\, ad=n, \text{ and } 0\leq b <d\right\}.
$$
Note that the set $S_n$ is in bijection with the set of sublattices of
$\Z^2$ of index~$n$, where $\abcd{a}{b}{c}{d}$ corresponds to
$L=\Z\cdot (a,b) + \Z\cdot (0,d)$, as one can see, e.g., by using
Hermite normal form (the analogue of reduced row 
echelon form over~$\Z$).


\begin{definition}[Hecke Operator $T_{n,k}$]
The~$n$th Hecke operator $T_{n,k}$ of weight~$k$
is the operator on functions on $\h$ defined by
$$
T_{n,k}(f) = \sum_{\gamma \in S_n} 
f|[\gamma]_k.
$$
\end{definition}
\begin{remark}
  It would make more sense to write $T_{n,k}$ on the right, e.g.,
  $f|T_{n,k}$, since $T_{n,k}$ is defined using a right group action.
  However, if $n,m$ are integers, then $T_{n,k}$ and $T_{m,k}$ commute
  (by Proposition~\ref{prop:hecke_com} below), so it does not matter
  whether we consider the Hecke operators as acting on the right or
  left.
\end{remark}

\begin{proposition}\label{prop:tn_presweak}
  If~$f$ is a weakly modular function of weight~$k$, then so is
  $T_{n,k}(f)$, and if~$f$ is also a modular function, then so is
  $T_{n,k}(f)$.
\end{proposition}
\begin{proof}
Suppose $\gamma\in\SL_2(\Z)$.  Since~$\gamma$ 
induces an automorphism of $\Z^2$, the set 
$$S_n \cdot \gamma = \{ \delta \gamma : \delta\in S_n\}$$
is also in bijection with the sublattices
of $\Z^2$ of index~$n$.  
Then for each element $\delta\gamma \in S_n\cdot \gamma$, there
is $\sigma\in\SL_2(\Z)$ such that $\sigma\delta\gamma\in S_n$ (the
element~$\sigma$ 
transforms $\delta\gamma$ to Hermite normal form),
and the set of elements $\sigma\delta\gamma$ is equal to $S_n$.
Thus 
$$
 T_{n,k}(f) = \sum_{\sigma\delta\gamma\in S_n} f|[\sigma\delta\gamma]_k 
     = \sum_{\delta\in S_n} f|[\delta\gamma]_k
     = T_{n,k}(f)|[\gamma]_k.
$$

Since $f$ is holomorphic on $\h$, 
each $f|[\gamma]_k$ is holomorphic on $\h$.
A finite sum of holomorphic functions is holomorphic,
so $T_{n,k}(f)$ is holomorphic.

\end{proof}

We will frequently drop $k$ from the notation in $T_{n,k}$, since
the weight $k$ is implicit in the modular function to which
we apply the Hecke operator.  Thus we henceforth make the
convention that if we write $T_{n}(f)$ and~$f$ is modular, 
then we mean $T_{n,k}(f)$, where~$k$ is the weight of~$f$.

\begin{proposition}\label{prop:hecke_com}
On weight $k$ modular functions we have
\begin{equation}\label{eqn:hecke_mul}
  T_{mn} = T_{n} T_{m} \qquad\qquad\qquad\qquad\quad
 \text{if }(n,m)=1,
\end{equation}
and
\begin{equation}\label{eqn:hecke_recur}
  T_{p^n} = T_{p^{n-1}} T_p\, -\, p^{k-1} T_{p^{n-2}}, \qquad\!\!
\text{if $p$ is prime}.
\end{equation}
\end{proposition}
\begin{proof}
  Let $L$ be a lattice of index $mn$.  The quotient $\Z^2/L$ is an
  abelian group of order $mn$, and $(m,n)=1$, so $\Z^2/L$ decomposes
  uniquely as a direct sum of a subgroup order~$m$ with a subgroup of
  order~$n$.  Thus there exists a unique lattice $L'$ such that
  $L\subset L'\subset \Z^2$, and $L'$ has index $m$ in $\Z^2$.  The
  lattice $L'$ corresponds to an element of $S_m$, and the index~$n$
  subgroup $L\subset L'$ corresponds to multiplying that element on
  the right by some uniquely determined element of $S_n$.  We thus
  have $$ \SL_2(\Z) \cdot S_{m} \cdot S_n = \SL_2(\Z) \cdot S_{mn}, $$
  i.e., the set products of elements in $S_m$ with elements of $S_n$
  equal the elements of $S_{mn}$, up to $\SL_2(\Z)$-equivalence.  It
  then follows from the definitions that for any $f$, we have
  $T_{mn}(f) = T_{n}(T_m(f))$.

  We will show that $T_{p^n} + p^{k-1} T_{p^{n-2}} = T_p T_{p^{n-1}}$.
  Suppose~$f$ is a weight~$k$ weakly modular function.  
Using that $f|[p]_k = (p^2)^{k-1}p^{-k} f = p^{k-2} f$, we have
$$
 \sum_{x\in S_{p^n}} f|[x]_k\,\, +\,\, p^{k-1}\!\!\! \sum_{x\in
      S_{p^{n-2}}} f|[x]_k
   =  \sum_{x\in S_{p^n}} f|[x]_k \,\,\,+\, p\!\!\!\! \sum_{x\in pS_{p^{n-2}}} f|[x]_k.
$$
  Also $$T_p T_{p^{n-1}}(f) = \sum_{y\in S_p} \sum_{x\in S_{p^{n-1}}}
  f|[x]_k|[y]_k = \sum_{x \in S_{p^{n-1}}\cdot S_p} f|[x]_k. $$
  Thus it suffices to show that $S_{p^n}$ union~$p$ copies of $p
  S_{p^{n-2}}$ is equal to $S_{p^{n-1}}\cdot S_p$, where we consider
  elements up to left $\SL_2(\Z)$-equivalence (i.e., the left
action of $\SL_2(\Z)$).

  Suppose~$L$ is a sublattice of $\Z^2$ of index $p^n$, so~$L$
  corresponds to an element of $S_{p^n}$.  First suppose~$L$ is not
  contained in $p\Z^2$.  Then the image of~$L$ in $\Z^2/p\Z^2 =
  (\Z/p\Z)^2$ is of order~$p$, so if $L'=p\Z^2 + L$, then
  $[\Z^2:L']=p$ and $[L:L']=p^{n-1}$, and $L'$ is the only lattice
  with this property.  Second suppose that $L\subset p\Z^2$ if of
  index $p^n$, and that $x\in S_{p^n}$ corresponds to $L$.  Then every
  one of the $p+1$ lattices $L'\subset \Z^2$ of index~$p$
  contains~$L$. Thus there are $p+1$ chains $L\subset L'\subset \Z^2$
with $[\Z^2:L']=p$.

The chains $L\subset L'\subset\Z^2$ with $[\Z^2:L']=p$ and
$[\Z^2:L]=p^{n-1}$ are in bijection with the elements of
$S_{p^{n-1}}\cdot S_p$.  On the other hand the union of $S_{p^n}$ with
$p$ copies of $p S_{p^{n-2}}$ corresponds to the lattices~$L$ of index
$p^{n}$, but with those that contain $p\Z^2$ counted $p+1$ times. The
structure of the set of chains $L\subset L'\subset\Z^2$ that we
derived in the previous paragraph gives the result.
\end{proof}

\begin{corollary}
The Hecke operator $T_{p^n}$, for prime~$p$, is a polynomial in $T_p$.
If $n,m$ are any integers then $T_n T_m = T_m T_n$.
\end{corollary}
\begin{proof}
  The first statement is clear from (\ref{eqn:hecke_recur}), and this
  gives commutativity when $m$ and $n$ are both powers of $p$.  Combining
  this with (\ref{eqn:hecke_mul}) gives the second statement in general.
\end{proof}

% \begin{remark}
% Emmanuel Kowalski made the following remark on the number theory lists
% in June 2004 when asked about the polynomials $f_n(X)$ such
% that $T_{p^n} = f_n(T_p)$.
% \begin{quote}
% If you normalize the Hecke operators by considering
% $$
%         S_{n,k} = n^{-(k-1)/2} T_{n,k}
% $$
% then the recursion on the polynomials $P_r(X)$ such that 
% $S_{p^r,k}=P_r(S_{p,k})$ becomes
% $$
%         X P_r  = P_{r+1} + P_{r-1},
% $$
% which is the recursion satisfied by the Chebychev polynomials $U_r$ such
% that
% $$
%         U_r(2 \cos t) = \frac{\sin((r+1) t)}{ \sin(t)}.
% $$
% Alternatively, those give the characters of the symmetric powers of the
% standard representation of $\SL_2(\R)$, evaluated on a rotation matrix
% $$
% \mtwo{\cos(t)}{-\sin(t)}{\sin(t)}{\hfill \cos(t)}.
% $$
% For references, see for instance \cite[p.~97]{iwaniec:topics}
% or \cite[p.~78, p.~81]{serre:asymptotique}, and there are certainly many others.
% \end{quote}
% \end{remark}

\begin{proposition}\label{prop:qexpTn}
Suppose $f = \sum_{n\in\Z} a_n q^n$ is a modular function
of weight~$k$.
Then 
$$
   T_{n}(f)
     = \sum_{m\in\Z} 
\left(\sum_{1\leq d\,\mid\, (n,m)} d^{k-1} a_{mn/d^2}\right) q^m.
$$
In particular, if $n=p$ is prime, then
$$
  T_p(f) = \sum_{m\in \Z} \left(a_{mp} + p^{k-1} a_{m/p}\right) q^m,
$$
where $a_{m/p}=0$ if $m/p\not\in\Z$.
\end{proposition}
The proposition is not that difficult to prove (or at least the proof
is easy to follow), and is proved in \cite[\S
VII.5.3]{serre:arithmetic} by writing out $T_n(f)$ explicitly and
using that $\sum_{0\leq b<d} e^{2\pi i bm/d}$ is $d$ if $d\mid m$
and~$0$ otherwise.  A corollary of Proposition~\ref{prop:qexpTn} is
that $T_n$ preserves $M_k$ and $S_k$.
\begin{corollary}\label{cor:tpres} 
 The Hecke operators preserve $M_k$ and $S_k$.
\end{corollary}
\begin{remark} We knew this already---for $M_k$ it's
  Proposition~\ref{prop:tn_presweak}, and for $S_k$ it's easy to show
  directly that if $f(i\infty)=0$ then $T_n f$ also vanishes at
  $i\infty$.
\end{remark}

\begin{example}
Recall that 
$$
E_4 = \frac{1}{240} + q + 9q^2 + 28q^3 + 73q^4 + 126q^5 + 252q^6 + 344q^7
+\cdots.
$$
Using the formula of Proposition~\ref{prop:qexpTn}, we see
that 
$$
T_2(E_4) = (1/240 + 2^3\cdot (1/240)) + 9q + (73 + 2^3\cdot 1) q^2 + \cdots \\
    = 9 E_4.
$$
Since $M_k$ has dimension $1$, and we have proved that $T_2$
preserves $M_k$, we know that $T_2$ acts as a scalar.  Thus
we know just from the constant coefficient of $T_2(E_4)$ that
$T_2(E_4) = 9 E_4$.
More generally, $T_p(E_4) = (1+p^3)E_4$.
In fact for any $k$ one has that
$$
 T_n(E_k) = \sigma_{k-1}(n) E_k,
$$
for any integer $n\geq 1$ and even weight $k\geq 4$.
\end{example}

\begin{example}
  By Corollary~\ref{cor:tpres}, the Hecke operators $T_n$ also
  preserve the subspace $S_k$ of $M_k$.  Since $S_{12}$ has dimension
  $1$ (spanned by $\Delta$), we see that~$\Delta$ is an
  eigenvector for every $T_n$.  Since the coefficient of $q$ in the
  $q$-expansion of $\Delta$ is~$1$, the eigenvalue of $T_n$ on
  $\Delta$ is the $n$th coefficient of $\Delta$.  Moreover the
  function $\tau(n)$ that gives the $n$th coefficient of $\Delta$ is a
  multiplicative function.  Likewise, one can show that the series
  $E_k$ are eigenvectors for all $T_n$, and because in this book we
  normalize $E_k$ so that the coefficient of $q$ is~$1$, the
  eigenvalue of $T_n$ on $E_k$ is the coefficient $\sigma_{k-1}(n)$
  of~$q^n$.
\end{example}

\section{Computing Hecke Operators}
In this section we describe a simple algorithm for computing matrices
of Hecke operators on $M_k$.

\begin{algorithm}{Hecke Operator}
  This algorithm computes a matrix for the Hecke operator $T_n$ on the
 Victor Miller basis for $M_k$.
\begin{steps}
\item{}[Compute dimension] Set $d\set \dim(S_k)$, which we
  compute using Corollary~\ref{cor:dim1}.
\item{}[Compute basis] Using the algorithm
implicit in Lemma~\ref{lem:vm}, compute a
  basis $f_0,\ldots, f_d$ for $M_k$ modulo $q^{dn+1}$.
\item{}[Compute Hecke operator] Using the formula from
  Proposition~\ref{prop:qexpTn}, compute $T_n(f_i) \pmod{q^{d+1}}$ for
  each $i$.
\item{}[Write in terms of basis]\label{usevm} The elements 
$T_n(f_i) \pmod{q^{d+1}}$
  uniquely determine linear combinations of $f_0,f_1,\ldots, f_d
  \pmod{q^d}$.  These linear combinations are trivial to find
once we have computed $T_n(f_i) \pmod{q^{d+1}}$,
since the basis of~$f_i$ are in reduced row echelon form,
so the combinations are just the first few coefficients 
of the power series $T_n(f_i)$.
\item{}[Write down matrix] The matrix of $T_n$ acting from the right is
  the matrix whose columsn are the linear combinations found in the
  previous step, i.e., whose columns are the coefficients of $T_n(f_i)$.
\end{steps}
\end{algorithm}
\begin{proof}
  First note that we compute a modular form~$f$ modulo $q^{dn+1}$ in
  order to compute $T_n(f)$ modulo $q^{d+1}$.  This follows from
  Proposition~\ref{prop:qexpTn}, since in the formula the $d$th
  coefficient of $T_n(f)$ involves only $a_{dn}$, and smaller-indexed
  coefficients of~$f$.  The uniqueness assertion of Step~\ref{usevm}
  follows from Lemma~\ref{lem:vm} above.
\end{proof}



\begin{example}
This is the Hecke operator $T_2$ on $M_{36}$ is:
$$
\left(
\begin{matrix}
\hfill 34359738369&\hfill0&\hfill6218175600&\hfill9026867482214400\\
0&\hfill0&\hfill34416831456&\hfill5681332472832\\
0&\hfill1&\hfill194184&\hfill-197264484\\
0&\hfill0&\hfill-72&\hfill-54528\\
\end{matrix}\right)
$$
It has characteristic polynomial 
$$
(x - 34359738369) \cdot
(x^3 - 139656x^2 - 59208339456x - 1467625047588864),
$$
where the cubic factor is irreducible.
\end{example}

\begin{conjecture}[Maeda]
The characteristic polynomial of $T_2$ on $S_k$ is irreducible for any~$k$.
\end{conjecture}

Kevin Buzzard even observed that in many specific cases the Galois
group of the characteristic polynomial of $T_2$ is the full symmetric group
(see \cite{buzzard:t2}).  See also \cite{farmer-james:maeda} for more
evidence for Maeda's conjecture.
\edit{Isn't there something from a recent Berkeley grad student.}

% \section{Computing Characteristic Polynomials}
% \begin{algorithm}{Characteristic Polynomial}
% This algorithm computes the characteristic
% polynomial of $T_p$ acting on $M_k(\SL_2(\Z))$.
% \end{algorithm}
% \section{Some Open Problems}
% \subsection{Maeda's Conjecture}
% \begin{conjecture}
% The characteristic polynomial of $T_2$ is irreducible.
% \end{conjecture}


\subsection{A Conjecture about Complexity}


Let\edit{Lead in about coefficients of elliptic curve
modform, etc.???}
\begin{align*}
\Delta &= \sum_{n=1}^{\infty} \tau(n) q^n \\
  & = q - 24q^2 + 252q^3 - 1472q^4 + 4830q^5 - 6048q^6 - 16744q^7\\
  &\qquad  + 84480q^8 - 113643q^9 - 115920q^{10} + 534612q^{11} - \\
  &\qquad  370944q^{12} - 577738q^{13} + 401856q^{14} + 1217160q^{15} + \\
  &\qquad  987136q^{16} - 6905934q^{17} + 2727432q^{18} + 10661420q^{19} + 
  \cdots 
\end{align*}
be the $\Delta$-function.
\begin{conjecture}[Edixhoven]\label{conj:edixhoven}
There is an algorithm to compute $\tau(p)$, for prime $p$, that
is polynomial-time in $\log(p)$.
More generally, suppose $f=\sum a_n q^n$ is an eigenform in some space
$M_k(N,\eps)$, where $k\geq 2$.  Then there is an algorithm
to compute $a_p$, for $p$ prime, in time polynomial in $\log(p)$.
\end{conjecture}


Bas Edixhoven, Jean-Marc Couveignes and Robin de Jong have mostly
proved that $\tau(p)$ can be computed in polynomial time; their
approach involves sophisticated techniques from arithmetic geometry
(e.g., \'etale cohomology, motives, Arakelov theory). This is work in
progress and has not been written up completely yet.  The ideas
Edixhoven uses are inspired by the ones introduced by Schoof, Elkies
and Atkin for quickly counting points on elliptic curves over finite
fields (see \cite{MR1413578}).

More precisely, Edixhoven describes his strategy as follows:
\begin{enumerate}
\item We compute the mod $\ell$ Galois representations associated to
  $\Delta$.  In particular, we produce a polynomial $f$ such that
  $\Q[x]/(f)$ is the corresponding field. This is then used to obtain
  $\tau(p) \pmod{\ell}$ and do a Schoof like algorithm for computing
  $\tau(p)$.

\item We compute the field of definition of suitable points of
  order~$\ell$ on $J_1(\ell)$ to do part 1.

\item The method is to approximate the polynomial $f$ in some sense
  (e.g., over the complex numbers, or modulo many small primes $r$),
  and use an estimate from Arakelov theory to determine a
  precision that will suffice.
\end{enumerate}

The rest of this book is about methods for computing subspaces of
$M_k(\Gamma_1(N))$ for general $N$ and $k$.  These general methods are
much more complicated than the methods presented in this chapter,
since there are many more forms of small weight, and it can be
difficult to obtain them.  These forms of higher level have subtle and
deep connections with arithmetic geometric objects such as elliptic
curves, abelian varieties, and motives.

\begin{exercises}
\item\label{ex:upperhalfpres}
Suppose $\gamma = \abcd{a}{b}{c}{d}$ is a matrix with real entries
and positive determinant.  Prove that if $z\in\C$ is a complex
number with positive imaginary part, then the imaginary
part of $\gamma(z) = (az+b)/(cz+d)$ is also positive.

\item\label{ex:meromorphic}
\begin{enumerate}
\item Prove that a polynomial is an analytic function on $\C$.
\item Prove that a rational function (quotient of two polynomials)
is a meromorphic function on $\C$.
\end{enumerate}

\item \label{ex:wmfprod}
Suppose $f$ and $g$ are weakly modular functions with $f\neq 0$.
\begin{enumerate}
\item Prove that the product $fg$ is a weakly modular function.
\item Prove that $1/f$ is a weakly modular function.
\item If $f$ and $g$ are modular functions, show that $fg$
is a modular function.
\item If $f$ and $g$ are modular forms, show that $fg$
is a modular form.
\end{enumerate}

\item \label{ex:nomodformodd}
Suppose $f$ is a weakly modular function of odd weight $k$.
Show that $f=0$.

\item \label{ex:conggamma1}
\begin{enumerate}
\item Prove that $\Gamma_1(N)$ is a group.
\item Prove that $\Gamma_1(N)$ has finite index in $\SL_2(\Z)$
(Hint: it contains the kernel of the homomorphism
$\SL_2(\Z) \to \SL_2(\Z/N\Z)$.)
\end{enumerate}

\item \label{ex:grpact}
Let $k$ be an integer, and for any function
$f:\h^*\to \C$ and $\gamma=\abcd{a}{b}{c}{d}\in\GL_2(\Q)$,
set $f|[\gamma]_k(z) = (cz+d)^{-k} f(\gamma(z))$. 
Prove that if $\gamma_1, \gamma_2 \in \SL_2(\Z)$,
then for all $z\in \h^*$ we have 
$$
 f|[\gamma_1 \gamma_2]_k(z)  = ((f|[\gamma_1]_k)|[\gamma_2]_k)(z).
$$

\item \label{ex:sl2ztrans}
Prove that for any $\alpha, \beta\in\P^1(\Q)$, there exists
  $\gamma\in\SL_2(\Z)$ such that $\gamma(\alpha) = \beta$.

\item \label{ex:expeis} By hand use (\ref{eqn:ekexp}) write down the
  coefficients of $1$, $q$, $q^2$, and $q^3$ of the Eisenstein series
  $E_8$.

\item \label{ex:vm} Explicitly compute the Victor Miller basis for
$M_{28}(\SL_2(\Z))$.

\end{exercises}

% \subsection{The Gouvea-Mazur Conjecture}
% \edit{False in general, but .... (copy from last year).}









%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
%   NEW CHAPTER 
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%












\chapter{Dirichlet Characters}\label{ch:dirichlet}

Fix an integral domain~$R$ and a root~$\zeta$ of unity in~$R$.
\begin{definition}[Dirichlet Character]
  A \defn{Dirichlet character} modulo~$N$ over~$R$ with given choice
  of $\zeta\in R$ is a map $\eps:\Z\to R$ such that there
is a homomorphism $f:(\Z/N\Z)^* \to \langle \zeta \rangle$ for which
$$
 \eps(a) = \begin{cases} 
       0 &\text{if }(a,N)>1,\\
     f\,(a\!\!\!\!\mod{N}) &\text{if }(a,N)=1.
   \end{cases}
$$
\end{definition}   
We denote the group of such Dirichlet characters by $D(N,R,\zeta)$, or
by just $D(N,R)$, when the choice of $\zeta$ is clear.  It follows
immediately from the definition that elements of
$D(N,R)$ are in bijection with  homomorphisms $(\Z/N\Z)^* \to
\langle \zeta \rangle$.

In this chapter we develop a systematic theory for computing
with Dirichlet characters.   These will be extremely important
everywhere in the rest of this book, when we compute with
spaces $M_k(\Gamma_1(N))$ of modular forms for 
$$
  \Gamma_1(N) = \left\{ \mtwo{a}{b}{c}{d} \in \SL_2(\Z) : 
                    \mtwo{a}{b}{c}{d}\con \mtwo{1}{*}{0}{1}\pmod{N}
                \right\}.
$$
For example, Eisenstein series in $M_k(\Gamma_1(N))$ are associated
to pairs of Dirichlet characters.  Also the complex vector space 
$M_k(\Gamma_1(N))$ with its structure as a module over the Hecke algebra
decomposes as a direct sum
$$
    M_k(\Gamma_1(N)) = \bigoplus_{\eps\in D(N,\C)} M_k(\Gamma_1(N))(\eps).
$$
Each space $M_k(\Gamma_1(N))(\eps)$ is frequently much easier
to compute with than the full $M_k(\Gamma_1(N))$.    
For example, $M_2(\Gamma_1(100))$ has dimension $370$, whereas
$M_2(\Gamma_1(100))(1)$ has dimension only $24$, and 
$M_2(\Gamma_1(389))$ has dimension $6499$, whereas
$M_2(\Gamma_1(389))(1)$ has dimension only $33$.

\begin{remark}
If 
$$
  \Gamma_0(N) = \left\{ \mtwo{a}{b}{c}{d} \in \SL_2(\Z) : 
                    \mtwo{a}{b}{c}{d}\con \mtwo{*}{*}{0}{*}\pmod{N}
                \right\},
$$
then $M_k(\Gamma_1(N))(1) = M_k(\Gamma_0(N))$.
\end{remark}


\section{Decomposing Modular Forms Using Dirichlet Characters}
The group $(\Z/N\Z)^*$ acts on $M_k(\Gamma_1(N))$ through the
\defn{diamond-bracket operators}~$\langle d \rangle$.
For $d\in(\Z/N\Z)^*$, define
$$
   f|\dbd{d} = f|[\abcd{a}{b}{c}{d'}]_k,
$$
where $\abcd{a}{b}{c}{d'} \in \SL_2(\Z)$ is congruent to
$\abcd{d^{-1}}{0}{0}{d}\pmod{N}$.  Note that the map
$\SL_2(\Z)\to \SL_2(\Z/N\Z)$ is surjective (see \exref{ch:eisen}{ex:surjred}),
so it makes sense to consider the matrix $\abcd{a}{b}{c}{d'}$.
To prove that $\dbd{d}$ preserves $M_k(\Gamma_1(N))$,
we prove the more general fact that $\Gamma_1(N)$ is normal
in 
$$  \Gamma_0(N) = \left\{ \mtwo{a}{b}{c}{d} \in \SL_2(\Z) : 
                    \mtwo{a}{b}{c}{d}\con \mtwo{*}{*}{0}{*}\pmod{N}
                \right\}.
$$
This will imply that $\dbd{d}$ preserves $M_k(\Gamma_1(N))$
since $\abcd{a}{b}{c}{d'} \in \Gamma_0(N)$.

\begin{lemma}
The group $\Gamma_1(N)$ is a normal subgroup of $\Gamma_0(N)$,
and the quotient $\Gamma_0(N)/\Gamma_1(N)$ is
isomorphic to $(\Z/N\Z)^*$.
\end{lemma}
\begin{proof}
Consider the surjective homomorphism $r:\SL_2(\Z)\to \SL_2(\Z/N\Z)$.
Then $\Gamma_1(N)$ is the exact inverse image of the subgroup $H$ of
matrices of the form $\abcd{1}{*}{0}{1}$ and $\Gamma_0(N)$
is the inverse image of the subroup $T$ of upper triangular matrices.
It thus suffices to observe that $H$ is normal in $T$, which is clear.
Finally, the quotient $T/H$ is isomorphic to the group of diagonal
matrices in $\SL_2(\Z/N\Z)^*$, which is isomorphic to $(\Z/N\Z)^*$.
\end{proof}

The diamond bracket action is simply the action of
$\Gamma_0(N)/\Gamma_1(N)\isom(\Z/N\Z)^*$ on $M_k(\Gamma_1(N))$. 
Since $M_k(\Gamma_1(N))$ is a vector space over $\C$,
the $\dbd{d}$ action breaks $M_k(\Gamma_1(N))$ up as a direct
sum of factors corresponding to the Dirichlet characters $D(N,C)$ of 
modulus~$N$.  
\begin{proposition}
We have
$$
  M_k(\Gamma_1(N)) = \bigoplus_{\eps \in D(N,\C)} M_k(N,\eps),
$$
where
$$
  M_k(N,\eps) = \bigl\{ f \in \M_k(\Gamma_1(N)) : f|\dbd{d} = \eps(d) f
                    \text{ all }d \in (\Z/N\Z)^*\bigr\}.
$$
\end{proposition}
\begin{proof}
  The linear transformations $\dbd{d}$, for the $d\in(\Z/N\Z)^*$, all
  commute, since $\dbd{d}$ acts through the abelian group
  $\Gamma_0(N)/\Gamma_1(N)$.  Also, if $e$ is the exponent of
  $(\Z/N\Z)^*$, then $\dbd{d}^e = \dbd{d^e} = \dbd{1} = 1$, so the
  matrix of $\dbd{d}$ is diagonalizable.  It is a standard fact from
  linear algebra that any commuting family of diagonalizable linear
  transformations is simultaneously diagonalizable (see
  \exref{ch:eisen}{ex:diag}), so there is a basis $f_1,\ldots, f_n$
  for $M_k(\Gamma_1(N))$ so that all $\dbd{d}$ act by diagonal
  matrices.  The eigenvalues of the action of $(\Z/N\Z)^*$ on a fixed
  $f_i$ defines a Dirichlet character, i.e., each $f_i$ has
  the property that $f_i |\dbd{d} = \eps_i(d)$, for all
  $d\in(\Z/N\Z)^*$ and some Dirichlet character $\eps_i$.  The $f_i$
  for a given $\eps$ then span $M_k(N,\eps)$, and taken together the
  $M_k(N,\eps)$ must span $M_k(\Gamma_1(N))$.
\end{proof}

\begin{definition}[Character of Modular Form]
If $f\in M_k(N,\eps)$, we say that~$f$ \defn{has character} $\eps$.
\end{definition}
\begin{remark}
People also often write that $f$ has ``nebentypus character'' $\eps$.
I rarely hear anyone actually {\em say} nebentypus, and it's somewhat
redundant, so I will simply omit it in this book.
\end{remark}

% There is an inner product $\langle \, , \, \rangle $ on $M_k(Gamma_1(N))$
% called the \defn{Petersson inner product}.  It is nondegenerate and
% if $T_n$ is a Hecke operator, then $
The spaces $M_k(N,\eps)$ are a direct sum of subspaces
$S_k(N,\eps)$ and $E_k(N,\eps)$, where $S_k(N,\eps)$ is the
subspace of cusp forms, i.e., forms that vanish at {\em all}
cusps (elements of $\Q \union \{\infty\}$), and $E_k(N,\eps)$
is the subspace of Eisenstein series, which is the unique
subspace of $M_k(N,\eps)$ that is invariant under all Hecke
operators and is such that 
$M_k(N,\eps) = S_k(N,\eps) \oplus E_k(N,\eps)$.
The space $E_k(N,\eps)$ can also be defined as the space
spanned by all Eisenstein series of weight $k$ and level~$N$,
as defined below.  It can also be defined using the Petersson
inner product.

\begin{remark}
The notation $M_k(N)$ will not be used anywhere in this book
(except in this sentence).
\end{remark}

%Remark: Edixhoven once told me that if you
%could compute $\tau(n)$ for {\em all} $n$, not just prime~$n$, in
%polynomial time, then you could factor integers in polynomial time.


\section{Representation and Arithmetic}
\begin{lemma}\label{lem:dual}
  The groups $(\Z/N\Z)^*$ and $\Hom((\Z/N\Z)^*,\C^*)\isom D(N,\C^*)$
  are non-canonically isomorphic.
\end{lemma}
\begin{proof}
  This follows from the more general fact that for any abelian
  group~$G$, we have that $G\ncisom \Hom(G,\C^*)$.  To prove that this
  latter non-canonical isomorphism exists, first reduce to the case
  when~$G$ is cyclic of order~$n$, in which case the statement follows
  because $\zeta_n\in\C^*$, so $\Hom(G,\C^*)\isom \Hom(G,\langle
  \zeta_n\rangle)$ is also cyclic of order~$n$.
\end{proof}

\begin{corollary}\label{cor:dir_ord}
We have $\#D(N,R) \mid \vphi(N)$, with equality
if and only if the order of our choice of $\zeta\in R$
is a multiple of the exponent of the group $(\Z/N\Z)^*$.
\end{corollary}

\begin{example}
The group $D(5,\C)$ has elements 
$\{[1], [i], [-1], [-i]\}$,
so is cyclic of order $\vphi(5)=4$.
In contrast,  the group $D(5,\Q)$ has only the
two elements $[1]$ and $[-1]$ and order $2$.
\end{example}

Fix a positive integer~$N$, and write $N=\prod_{i=1}^{n} {p_i^{e_i}}$
where $p_1<p_2<\cdots < p_n$ are the prime divisors of~$N$.  By
\exref{ch:dirichlet}{ex:cyclic}, each factor $(\Z/p_i^{e_i}\Z)^*$ is a
cyclic group $C_i=\langle g_i \rangle$, except if $p_1=2$ and $e_1\geq
3$, in which case $(\Z/p_1^{e_1}\Z)^*$ is a product of the cyclic
subgroup $C_0 = \langle -1 \rangle$ of order $2$ with the cyclic
subgroup $C_1 = \langle 5\rangle$.  In all
cases we have $$
(\Z/N\Z)^* \isom \prod_{0\leq i\leq n} C_i = \prod_{0\leq i \leq n} \langle g_i \rangle.
$$
For~$i$ such that $p_i>2$, choose the generator $g_i$ of $C_i$ to be
the element of $\{2,3,\ldots, p_i^{e_i}-1\}$ that is smallest and
generates.  Finally, use the Chinese Remainder Theorem (see
\cite[\S1.3.3]{cohen:course_ant})) to lift each $g_i$ to an element in
$(\Z/N\Z)^*$, also denoted $g_i$, that is~$1$ modulo each $p_j^{e_j}$
for $j\neq i$.

\begin{algorithm}{Minimal generator for $(\Z/p^r\Z)^*$}\label{alg:mingens}
Given an odd prime power $p^r$, this algorithm computes
a minimal generator for $(\Z/p^r\Z)^*$.
\begin{steps}
\item{}[Factor Group Order] Factor $n=\phi(p^r) = p^{r-1}\cdot 2\cdot
  ((p-1)/2)$ as a product $\prod p_i^{e_i}$ of primes.  This is
  equivalent in difficulty to factoring $(p-1)/2$.  (See chapters 8
  and 10 of \cite{cohen:course_ant} for integer factorization
  algorithms.)
\item{}[Initialize]\label{step:gen_init} Set $g\set 2$.  
\item{}[Generator?] Using the binary powering algorithm (see
  \cite[\S1.2]{cohen:course_ant}), compute $g^{n/p_i}\pmod{p^r}$, for
  each prime divisor $p_i$ of~$n$.  If any of these powers are $1$,
  set $g\set g+1$ and go to Step~\ref{step:gen_init}. 
If no powers are $1$, output $g$ and terminate.
\end{steps}
\end{algorithm}
For the proof, see \exref{ch:dirichlet}{ex:orderalg}.

\begin{example}
A minimal generator for $(\Z/49\Z)^*$ is $3$.  
We have $n=\vphi(49)=42=2\cdot 3\cdot 7$, and 
$$
  2^{n/2} \con 1, \qquad 2^{n/3} \con 18, \qquad 2^{n/7} \con 15 \pmod{49}.
$$
so $2$ is not a generator for $(\Z/49\Z)^*$.  (We see
this just from $2^{n/2}\con 1\pmod{49}$.)  However 
$$
  3^{n/2} \con 48, \qquad 3^{n/3} \con 30, \qquad 3^{n/7} \con 43 \pmod{49}.
$$
\end{example}

\begin{example}\label{ex:mingens}
In this example
we compute minimal generators for $N=25$, $100$, and $200$:
\begin{enumerate}
\item
The minimal generator for $(\Z/25\Z)^*$ is $2$.

\item
Minimal generators for $(\Z/100\Z)^*$, lifted
to numbers modulo $100$, are $g_0=51$, $g_1=1$ and $g_2=77$.
Notice that $g_0\con -1\pmod{4}$ and $g_0\con 1\pmod{25}$, that $g_1=1$ since $2\mid N$, but
$8\nmid N$, and $g_2\con 2\pmod{25}$ is the minimal generator modulo~$25$.

\item
Minimal generators for $(\Z/200\Z)^*$, lifted
to numbers modulo $200$, are 
$g_0 = 151$, $g_1 = 101$, and $g_2=177$.  Note
that $g_0\con -1\pmod{4}$, that $g_1\con 5\pmod{8}$,
and $g_2\con 2\pmod{25}$.
\end{enumerate}
\end{example}

Fix an element~$\zeta$ of finite multiplicative order in a ring~$R$,
and let $D(N,R)$ denote the group of Dirichlet characters modulo~$N$
over~$R$, with image in $\langle \zeta\rangle \union \{0\}$.  We
specify an element $\eps\in D(N,R)$ by giving the list
\begin{equation}\label{eqn:epslist}
[\eps(g_0), \eps(g_1), \ldots, \eps(g_n)]
\end{equation}
of images of the generators of $(\Z/N\Z)^*$.  (Note if $N$ is even,
the number of elements of the list (\ref{eqn:epslist}) does {\em not}
depend on whether or not $8\mid N$---there are always two factors
corresponding to $2$.)  This representation completely
determines~$\eps$ and is convenient for arithmetic operations with
Dirichlet characters.  It is analogous to representing a linear
transformation by a matrix.  See Section~\ref{sec:alter_rep} for
a discussion of alternative ways to represent Dirichlet characters.


\begin{example}\label{ex:char}
If $N=200$, then $g_0=151$, $g_1=101$ and $g_2=177$, as
we saw in Example~\ref{ex:mingens}.  The
exponent of $(\Z/200\Z)^*$ is $20$, since that
is the least common multiple of the exponents of
$4=\#(\Z/8\Z)^*$ and $20=\#(\Z/25\Z)^*$.
The orders of $g_0$, $g_1$ and $g_2$ are $2$, $2$, and $20$.
Let $\zeta=\zeta_{20}$ be a primitive $20$th root of
unity in $\C$.  Then the following are generators
for $D(20,\C)$:
$$
  \eps_0 = [-1,1,1],\qquad
  \eps_1 = [1,-1,1],\qquad
  \eps_2 = [1,1,\zeta],
$$
and $\eps=[1,-1,\zeta^5]$ is an example element of order~$4$.
To evaluate $\eps(3)$, we write~$3$ in
terms of $g_0$, $g_1$, and $g_2$.
First, reducing $3$ modulo~$8$, we see that 
$3 \con g_0 \cdot g_1\pmod{8}$.  Next 
reducing $3$ modulo $25$, and trying powers of 
$g_2=2$, we find that $e\con g_2^7\pmod{25}$.  
Thus 
\begin{align*}
  \eps(3) &= \eps(g_0 \cdot g_1 \cdot g_2^7)\\
          &= \eps(g_0) \eps(g_1) \eps(g_2)^7\\
          &= 1 \cdot (-1) \cdot (\zeta^5)^7\\
          &= -\zeta^{35} = -\zeta^{15}.
\end{align*}
\end{example}

Example~\ref{ex:char} illustrates that if~$\eps$ is represented using
a list as described above, evaluation of~$\eps$ on an arbitrary
integer is inefficient without extra information; it requires solving
the discrete log problem in $(\Z/N\Z)^*$.  In fact, for a general
character~$\eps$ calculation of~$\eps$ will probably be at least as
hard as finding discrete logarithms no matter what representation we
use (quadratic characters are easier---see Algorithm~\ref{alg:kronecker}).
\begin{algorithm}{Evaluate $\eps$}\label{alg:eval_eps}
Given a Dirichlet character $\eps$ modulo~$N$, represented
by a list $[\eps(g_0), \eps(g_1), \ldots, \eps(g_n)]$,
and an integer~$a$, this algorithm computes~$\eps(a)$.
\begin{steps}
\item{}[GCD] Compute $g=\gcd(a,N)$.  If $g>1$, output~$0$ and terminate.
\item{}[Discrete Log]\label{step:eval_fb} For each $i$, write $a\pmod{p_i^{e_i}}$ as a
  power $m_i$ of $g_i$ using some algorithm for solving the discrete
  log problem (see below).  (If $p_i=2$, write
  $a\pmod{p_i^{e_i}}$ as $(-1)^{m_0}\cdot 5^{m_1}$.)  This step is
  analogous to writing a vector in terms of a basis.
\item{}[Multiply] Compute and output $\prod \eps(g_i)^{m_i}$ as an
  element of~$R$, and terminate.  This is analogous to multiplying a
  matrix times a vector.
\end{steps}
\end{algorithm}
By \exref{ch:dirichlet}{ex:dlogadd} we have an isomorphism
of groups
$$
(1+p^{n-1}(\Z/p^n\Z),\,\times) \isom (\Z/p\Z,\,+),
$$
so one sees by
induction that Step~\ref{step:eval_fb} is ``about as difficult'' as finding a
discrete log in $(\Z/p\Z)^*$.  There is an algorithm called
``baby-step giant-step'', which solves the discrete log problem in
$(\Z/p\Z)^*$ in time $O(\sqrt{\ell})$, 
where $\ell$ is the largest prime factor of $p-1=\#(\Z/p\Z)^*$
(note that the discrete log problem in $(\Z/p\Z)^*$ reduces
to a series of discrete log problems in each prime order cyclic
factor).
This is unfortunately still
exponential in the number of digits of~$\ell$.
\begin{algorithm}{Baby-Step Giant Step Discrete Log}
\label{alg:baby_giant_dlog}
Given a prime $p$, a generator $g$ of $(\Z/p\Z)^*$,
and an element $a\in (\Z/p\Z)^*$, this algorithm
finds an $n$ such that $g^n=a$.  
(Note that this algorithm works in any cyclic group,
not just $(\Z/p\Z)^*$.)
\begin{steps}
\item{}[Make Lists] 
Let $m=\lceil{} \sqrt{p}\rceil{}$ be the ceiling of $\sqrt{p}$,
and
construct two lists $$
g,\, g^m,\, \ldots, \,g^{(m-1)m}, g^{m^2}
\qquad\qquad\text{(giant steps)} $$
and 
$$
ag,\, ag^2,\, \ldots, \,
ag^{m-1}, ag^m \qquad\qquad\text{(baby steps)}.
$$
\item{}[Find Match]\label{step:find_match}
Sort the two lists and
find a match $g^{im} = a g^j$. Then $a = g^{im-j}$.
\end{steps}
\end{algorithm}
\begin{proof}
  We prove that there will always be a match. Since we know that $a=g^k$ for some $k$
  with $0\leq k\leq p-1$ and any such $k$ can be written in the form
  $im-j$ for $0\leq i,j\leq m-1$, we will find such a match.
\end{proof}

Algorithm~\ref{alg:baby_giant_dlog} uses nothing special about
$(\Z/p\Z)^*$, so it works in a generic group.  It is a theorem that
there is no faster algorithm to find discrete logs in a ``generic
group'' (see \cite{shoup:lower,nechaev:lower}).  Fortunately there are
much better subexponential algorithms for solving the discrete log
problem in $(\Z/p\Z)^*$, which use the special structure of this group.
They use the number field sieve (see e.g., \cite{gordon:dlog}), which
is also the best known algorithm for factoring integers.  This class
of algorithms has been very well studied by cryptographers; though
sub-exponential, solving discrete log problems when $p$ is large is
still extremely difficult.  For a more in-depth survey see
\cite{gordon:dlp}.


The specific applications of Dirichlet characters in this book involve
computing modular forms, and for these applications~$N$ will be fairly
small, e.g., $N<10^6$.  Also we will evaluate~$\eps$ on a {\em huge}
number of random elements, inside inner loops of algorithms.  Thus for
our purposes it will often be better to make a table of all values
of~$\eps$, so that evaluation of~$\eps$ is extremely fast.  The
following algorithm computes a table of all values of $\eps$, and it
does not require computing any discrete logs since we are computing
{\em all} values.

\begin{algorithm}{Values of $\eps$}
Given a Dirichlet character $\eps$ represented by the list
of values of $\eps$ on the minimal generators $g_i$ of $(\Z/N\Z)^*$, this algorithm
creates a list of all the values of $\eps$.
\begin{steps}
\item{}[Initialize] For each minimal generator $g_i$, set $a_i\set 0$.
  Let $n = \prod g_i^{a_i}$, and set $z\set 1$.  Create a list~$v$
  of~$N$ values, all initially set equal to $0$.  When this algorithm
  terminates the list~$v$ will have the property that 
  $$v\,\,[x
  \!\!\!\!\!\pmod{N}] = \eps(x).$$
  Notice that we index $v$ starting
  at $0$.
\item{}[Add Value to Table]\label{step:add_value} Set $v[n] \set z$.
\item{}[Finished?] If each $a_i$ is one less than the order of $g_i$, output~$v$ 
and terminate.
\item{}[Increment] Set $a_0\set a_0 + 1$, $n\set n\cdot g_0\pmod{N}$,
and $z\set z\cdot \eps(g_0)$.  If $a_0\geq \ord(g_0)$, set $a_0\to 0$,
then set $a_1\set a_1 + 1$, $n\set n\cdot g_1\pmod{N}$, and 
$z\set z\cdot \eps(g_1)$.  If $a_1\geq \ord(g_1)$, do what you just
did with $a_0$, but with all subscripts replaced by $1$.  Etc.
(Imagine a car odometer.)  Go to Step~\ref{step:add_value}.
\end{steps}
\end{algorithm}



% \begin{algorithm}{Unit Generators}
% Given an integer~$N$, this algorithm finds minimal generators for the
% cyclic factors of $(\Z/N\Z)^*$ corresponding to the prime powers that
% exactly divide~$N$.
% \end{algorithm}

% \begin{algorithm}{Generators}
%   Given an integer $N$ and a root of unity $\zeta\in R$, this
%   algorithm computes generators for the group of Dirichlet characters
%   modulo~$N$ with values in $\langle \zeta \rangle \union \{0 \}$.
% \end{algorithm}

Frequently people describe quadratic characters in terms of the
Kronecker symbol. The following algorithm gives a way to go between
the two representations.

\begin{algorithm}{Kronecker Symbol}\label{alg:kronecker}
  Given an integer~$N$, this algorithm computes a representation of
  the Kronecker symbol $\kr{a}{N}$ as a Dirichlet character.
\begin{steps}
\item Compute the minimal generators $g_i$ of $(\Z/N\Z)^*$
using Algorithm~\ref{alg:mingens}.
\item Compute $\kr{g_i}{N}$ for each $g_i$ using one
of the algorithms of \cite[\S1.1.4]{cohen:course_ant}.
\end{steps}
\end{algorithm}
\begin{remark}
  The algorithms in \cite[\S1.1.4]{cohen:course_ant} for computing the
  Kronecker symbol run in time quadratic in the number of digits of
  the input, so they do not require computing discrete logarithms.
(They use, e.g., that $\kr{a}{p} \con a^{(p-1)/2}\pmod{p}$, when
$p$ is an odd prime.)
  If~$N$ is very large and we are only interested in evaluating
  $\eps(a) = \kr{a}{N}$ for a few $a$, then viewing~$\eps$ as a
  Dirichlet character in the sense of this chapter leads to a less
  efficient way to compute with~$\eps$.  The algorithmic discussion of
  characters in this chapter is most useful for working with the full
  group of characters, and characters that cannot be expressed in
  terms of Kronecker characters.
\end{remark}

\begin{example}
We compute the Dirichlet character associated to the
Kronecker symbol $\kr{a}{200}$.
We find that $\kr{g_i}{200}$, for $i=0,1,2$, where the
$g_i$ are as in Example~\ref{ex:char}:
%session
\begin{verbatim}
sage: kronecker(151,200)
1
sage: kronecker(101,200)
-1
sage: kronecker(177,200)
1
\end{verbatim}
Thus the corresponding character is defined by $[1,-1,1]$.
\end{example}

\begin{remark}[Elkies]
  Jacobi reciprocity must be used to efficiently compute the Jacobi
  symbol $\kr{m}{n}$.  It's faster than computing $a^{(p-1)/2}$
  when~$p$ is prime, but more significantly it makes it possible to
  compute Jacobi symbols $\kr{m}{n}$ for all $m,n$ without knowing the
  factorization of~$n$---which of course would be a computation much
  longer than quadratic.
\end{remark}


\begin{example}
We compute the character associated to $\kr{a}{420}$.
We have $420=4\cdot 3\cdot 5\cdot 7$, and minimal generators
are 
$$
  g_0 = 211,\quad g_1=1, \quad g_2 = 281, \quad g_3=337, \quad g_4=241.
$$
We have $g_0\con -1\pmod{4}$, $g_2\con 2\pmod{3}$, $g_3\con 2\pmod{5}$
and $g_4\con 3\pmod{7}$.
Using PARI again we find $\kr{g_0}{420}=\kr{g_1}{420}=1$
and $\kr{g_2}{420}=\kr{g_3}{420}=\kr{g_4}{420}=-1$, so the
corresponding character is $[1,1,-1,-1,-1]$.
\end{example}

\section{Algorithms}

The following algorithm for computing the order of~$\eps$ reduces
the problem to computing the orders of powers of $\zeta$ in $R$.
\begin{algorithm}{Order of Character}\label{alg:dir_order}
  This algorithm computes the order of a Dirichlet
  character $\eps\in D(N,R)$.
\begin{steps}
\item Compute the order $r_i$ of each $\eps(g_i)$, for each minimal
  generator $g_i$ of $(\Z/N\Z)^*$.  Since the order of $\eps(g_i)$ is
  divisor of $n=\#(\Z/p_i^{e_i}\Z)^*$, we can compute its order by
  factoring~$n$ and considering the divisors of~$n$.
\item Compute and output the least commmon multiple of the integers
  $r_i$.
\end{steps}
\end{algorithm}
\begin{remark}
  Computing the order of $\eps(g_i) \in R$ is potentially difficult
  and tedious.  Using a different (simultaneous) representation of
  Dirichlet characters avoids having to compute the order of elements
  of $R$.  See Section~\ref{sec:alter_rep}.
\end{remark}


The next algorithm factors $\eps$ as a product of ``local'' characters,
one for each prime divisor of $N$.  It is useful for other algorithms,
and also for explicit computations with the Hijikita trace formula 
(see \cite{hijikata:trace}). This factorization is easy to compute
because of how we represent $\eps$.

\begin{algorithm}{Factorization of Character}\label{alg:dirfac}
Given a Dirichlet character $\eps\in D(N,R)$, with $N=\prod p_i^{e_i}$, 
this algorithm finds Dirichlet characters $\eps_i$ modulo $p_i^{e_i}$, such
that for all $a\in(\Z/N\Z)^*$, we have 
$\eps(a) = \prod \eps_i(a\!\!\pmod{p_i^{e_i}})$.
If $2\mid N$, the steps are as follows:
\begin{steps}
\item Let $g_i$ be the minimal generators of $(\Z/N\Z)^*$, so $\eps$
is given by a list $$[\eps(g_0),\ldots, \eps(g_n)].$$
\item\label{step:singletons} For $i=2,\ldots, n$, let $\eps_i$ be the element of $D(p_i^{e_i},R)$
defined by the singleton list $[\eps(g_i)]$.
\item\label{step:extra2} Let $\eps_1$ be the element of $D(2^{e_1},R)$ defined
by the list $[\eps(g_0), \eps(g_1)]$ of length~$2$.   Output the
$\eps_i$ and terminate.
\end{steps}
If $2\nmid N$, then omit Step~\ref{step:extra2}, and include
all $i$ in Step~\ref{step:singletons}.
\end{algorithm}
The factorization of Algorithm~\ref{alg:dirfac} is unique since each
$\eps_i$ is determined by the image of the canonical map
$(\Z/p_i^{e_i}\Z)^*$ in $(\Z/N\Z)^*$, which sends $a\pmod
{p_i^{e_i}}$ to the element of $(\Z/N\Z)^*$ that is
$a\pmod{p_i^{e_i}}$ and $1 \pmod{p_j^{e_j}}$ for $j\neq i$.

\begin{example}\label{ex:prodlocal}
If $\eps = [1,-1,\zeta^5] \in D(200,\C)$, then 
$\eps_1 = [1,-1]\in D(8,\C)$ and $\eps_2 = [\zeta^5]\in D(25,\C)$.
\end{example}



\begin{definition}[Conductor]\label{defn:conductordir}
The \defn{conductor} of a Dirichlet character $\eps\in D(N,R)$
is the smallest positive divisor $c\mid N$ such that 
there is a character $\eps' \in D(c,R)$ for which 
$\eps(a) = \eps'(a)$ for all $a\in\Z$ with $(a,N)=1$.
A Dirichlet character is \defn{primitive} if its modulus equals
its conductor.  The character $\eps'$ associated to~$\eps$
with modulus equal to the conductor of~$\eps$ is called
the \defn{primitive character associated to}~$\eps$.
\end{definition}
We will be interested in conductors later, when computing new
subspaces of spaces of modular forms with character.  Also certain
formulas for special values of~$L$ functions are only valid for
primitive characters.

\begin{algorithm}{Conductor}\label{alg:conductor}
  This algorithm computes the conductor of a Dirichlet
  character~$\eps \in D(N,R)$.
\begin{steps}
\item{}[Factor Character]\label{step:factor_dir} Using Algorithm~\ref{alg:dirfac}, find
  characters~$\eps_i$ whose product is~$\eps$.
\item{}[Compute Orders] Using Algorithm~\ref{alg:dir_order}, compute
  the orders~$r_i$ of each~$\eps_i$.
\item{}[Conductors of Factors]\label{step:cond_fac}
For each $i$, either set $c_i\to 1$ if $\eps_i$
is the trivial character (i.e., of order $1$), or set $c_i \set
  p_i^{\ord_{p_i}(r_i)+1}$, where $\ord_{p}(n)$ is the largest power
  of $p$ that divides~$n$.
\item{}[Adjust at $2$?] If $p_1=2$ and $\eps_1(5)\neq 1$, set
$c_1\set 2c_1$.  
\item{}[Finished] Output $c = \prod c_i$ and terminate.
\end{steps}
\end{algorithm}
\begin{proof}
Let $\eps_i$ be the local factors of~$\eps$, as in Step~\ref{step:factor_dir}.
We first show that the product of the conductors $f_i$ of the $\eps_i$ is
the conductor~$f$ of~$\eps$.  Since $\eps_i$ factors through $(\Z/f_i\Z)^*$,
the product~$\eps$ of the $\eps_i$ factors through $(\Z/\prod f_i\Z)^*$,
so the conductor of~$\eps$ divides $\prod f_i$.  Conversely, if 
$\ord_{p_i}(f) < \ord_{p_i}(f_i)$ for some~$i$, then we could factor $\eps$
as a product of local (prime power) characters differently, which contradicts
that this factorization is unique.

It remains to prove that if~$\eps$ is a nontrivial character modulo
$p^n$, where~$p$ is a prime, and~$r$ is the order of~$\eps$, then the
conductor of~$\eps$ is $p^{\ord_p(r)+1}$, except possibly if $8\mid
p^n$.  Since the order and conductor of $\eps$ and of the associated
primitive character $\eps'$ are the same, we may assume $\eps$ is
primitive, i.e., that $p^n$ is the conductor of~$\eps$; note that that
$n>0$, since~$\eps$ is nontrivial.  

% If $m=\ord_p(r)$, so $p^m$ is the order
% of~$\eps$, then by Corollary~\ref{cor:dir_ord}, 
% $$
% p^m =
%   \ord(\eps) \mid \#D(p^n,R) \mid \#(\Z/p^n\Z)^* = p^{n-1}(p-1), $$
% so
% $m+1\leq n$.  It remains to show that $n\leq m+1$, except possibly
% when $8\mid p^n$, when $n\leq m+2$.   

First suppose $p$ is odd.
Then the abelian group $D(p^n,R)$ splits as a direct sum $D(p,R)\oplus D(p^n,R)'$,
where $D(p^n,R)'$ is the $p$-power torsion subgroup of $D(p^n,R)$.
Also $\eps$ has order $u\cdot p^m$, where $u$, which
is coprime to~$p$, is the order of the image of $\eps$
in $D(p,R)$ and $p^m$ is the order of the image in $D(p^n,R)'$.
If $m=0$, then the order of $\eps$ is coprime to $p$, so 
$\eps$ is in $D(p,R)$, which means that $n=1$,
so $n=m+1$, as required.  If $m>0$, then $\zeta\in R$ 
must have order divisible by $p$, so~$R$ has characteristic not
equal to~$p$.  The conductor of $\eps$ does not change if we
adjoin roots of unity to~$R$, so in light of Lemma~\ref{lem:dual}
we may assume that $D(N,R) \ncisom (\Z/N\Z)^*$.
It follows that for each $n'\leq n$, the $p$-power subgroup
$D(p^{n'},R)'$ of $D(p^{n'},R)$ is the $p^{n'-1}$-torsion
subgroup of $D(p^n,R)'$.   Thus $m=n-1$, since
$D(p^n,R)'$ is by assumption the smallest such group that 
contains the projection of~$\eps$.  This proves the 
formula of Step~\ref{step:cond_fac}.   We leave the argument
when $p=2$ as an exercise (see \exref{ch:dirichlet}{ex:cond2}).
\end{proof}

\begin{example}\label{ex:char_cond}
If $\eps = [1,-1,\zeta^5] \in D(200,\C)$, then
as we saw in Example~\ref{ex:prodlocal},~$\eps$ 
is the product of $\eps_1=[1,-1]$ and $\eps_2 = [\zeta^5]$.
Because $\eps_1(5)=-1$, the conductor of $\eps_1$ is $8$.
The order of $\eps_2$ is $4$ (since $\zeta$ is a $20$th
root of unity), so the conductor of $\eps_2$ is $5$.
Thus the conductor of~$\eps$ is $40=8\cdot 5$.
\end{example}

The following two algorithms restrict and extend characters to a
compatible modulus.  Using them it is easy to define multiplication of
two characters $\eps\in D(N,R)$ and $\eps'\in D(N',R')$, as long as
$R$ and $R'$ are subrings of a common ring.  To carry out the
multiplication, just extend bother characters to characters modulo
$\lcm(N,N')$, then multiply.

\begin{algorithm}{Restriction of Character}\label{alg:restrict}
Given a Dirichlet character $\eps\in D(N,R)$ and a divisor
$N'$ of $N$ that is a multiple of the conductor of $\eps$,
this algorithm finds a characters $\eps' \in D(N',R)$, such
that $\eps'(a) = \eps(a)$, for all $a\in\Z$ with $(a,N)=1$.
\begin{steps}
\item{}[Conductor] Compute the conductor of~$\eps$ using
  Algorithm~\ref{alg:conductor}, and verify that indeed $N'$ is
  divisible by the conductor and divides $N$.
\item{}[Minimal Generators] Compute the minimal generators $g_i$ for
  $(\Z/N'\Z)^*$.
\item{}[Values of Restriction]\label{step:addmod} For each $i$,
  compute $\eps'(g_i)$ as follows.  Find a multiple $aN'$ of $N'$ such
  that $(g_i+aN',\,N)=1$; then $\eps'(g_i) = \eps(g_i+aN')$.
\item{}[Output Character] Output the Dirichlet character modulo~$N'$
  defined by $[\eps'(g_0),\ldots, \eps'(g_n)]$.
\end{steps}
\end{algorithm}
\begin{proof}
The only part that is not clear is that in Step~\ref{step:addmod}
there is an $a$ such that $(g_i+aN', N)=1$.  If
we write $N=N_1\cdot N_2$, with $(N_1,N_2)=1$, and $N_1$ divisible
by all primes that divide $N'$, then $(g_i,N_1)=1$ since
$(g_i,N')=1$.  By the Chinese Remainder Theorem, 
there is an $x\in\Z$ such that $x\con g_i\pmod{N_1}$ and
$x\con 1\pmod{N_2}$. Then $x = g_i + b N_1 = g_i + (bN_1/N')\cdot N'$
and $(x,N)=1$, which completes the proof.
\end{proof}


\begin{algorithm}{Extension of Character}\label{alg:extend}
Given a Dirichlet character $\eps\in D(N,R)$ and a multiple
$N'$ of $N$,
this algorithm finds a characters $\eps' \in D(N',R)$, such
that $\eps'(a) = \eps(a)$, for all $a\in\Z$ with $(a,N')=1$.
\begin{steps}
\item{}[Minimal Generators] Compute the minimal generators $g_i$ for
  $(\Z/N'\Z)^*$.
\item{}[Evaluate] Compute $\eps(g_i)$ for each~$i$.  Since $(g_i,N')=1$,
we also have $(g_i,N)=1$.
\item{}[Output Character] Output the character defined by 
$[\eps(g_0),\ldots, \eps(g_n)]$.
\end{steps}
\end{algorithm}


We finish with an algorithm that computes the Galois orbit
of an element in $D(N,R)$.  This can be used to divide
$D(N,R)$ up into Galois orbits, which is useful for modular
forms computations, because, e.g., the spaces $M_k(\Gamma_1(N))(\eps)$
and $M_k(\Gamma_1(N))(\eps')$ are canonically isomorphic if $\eps$
and $\eps'$ are conjugate.
\begin{algorithm}{Galois Orbit}
Given a Dirichlet character $\eps\in D(N,R)$, this algorithm
computes the orbit of~$\eps$ under the action of $G=\Gal(\overline{F}/F)$,
where~$F$ is the prime subfield of $\Frac(R)$, so $F=\Fp$ or $\Q$.
\begin{steps}
\item{}[Order of $\zeta$] Let $n$ be the order of the chosen root $\zeta\in R$.
\item{}[Nontrivial Automorphisms]\label{step:nontriv_aut}
If $\Char(R)=0$, let
$$
 A = \{a : 2\leq a <n \text{ and }(a,n) = 1\}.
$$
If $\Char(R)=p>0$, compute the multiplicative order~$r$ of~$p$ modulo~$n$,
and let
$$
  A = \{p^m : 1\leq m < r\}.
$$
\item{}[Compute Orbit] Compute and output the {\em set} of unique elements $\eps^a$ 
for each $a\in A$ (there could be repeats, so we output unique elements only).
\end{steps}
\end{algorithm}
\begin{proof}
We prove that the nontrivial automorphisms of $\langle \zeta\rangle$ in characteristic~$p$
are as in Step~\ref{step:nontriv_aut}. 
It is well-known that every automorphism in characteristic~$p$ on 
$\zeta\in\Fpbar$ is of the form $x\mapsto x^{p^s}$, for some~$s$.
The images of $\zeta$ under such automorphisms are
$$
  \zeta, \zeta^p, \zeta^{p^2}, \ldots.
$$
Suppose $r>0$ is minimal such that $\zeta=\zeta^{p^r}$.  Then the
orbit of $\zeta$ is $\zeta,\ldots, \zeta^{p^{r-1}}$.
Also $p^r\con 1\pmod{n}$, where $n$ is the multiplicative order of~$\zeta$,
so~$r$ is the multiplicative order of~$p$ modulo~$n$, which completes
the proof.
\end{proof}

\begin{example}
The Galois orbits of characters in $D(20,\C^*)$ are as follows:
\begin{align*}
  G_0 &= \{ [1,1,1]\},\\
  G_1 &= \{[-1,1,1]\}, \\
  G_2 &= \{[1,1,\zeta_4],\,\, [1,1,-\zeta_4]\}\\
  G_3 &= \{[-1,1,\zeta_4],\,\, [-1,1,-\zeta_4]\}\\  
  G_4 &= \{[1,1,-1]\}, \\
  G_5 &= \{[-1,1,-1]\}
\end{align*}
The conductors of the characters in orbit $G_0$ are $1$, in
order $G_1$ are $4$, in orbit $G_2$ they are $5$, in
$G_3$ they are $20$, in $G_4$ the conductor is $5$, 
and in $G_5$ the conductor is $20$. (You should verify this.)
\end{example}

\section{Alternative Representations of Characters}\label{sec:alter_rep}
Let~$N$ be a positive integer and~$R$ an integral domain, with fixed
root of unity~$\zeta$ order~$n$, and let $D(N,R)=D(N,R,\zeta)$.  As in
the rest of this chapter, write $N=\prod p_i^{e_i}$, and let
$C_i=\langle g_i\rangle $ be the corresponding cyclic factors of
$(\Z/N\Z)^*$.  In this section we discuss other ways to represent
elements $\eps \in D(N,R)$.  Each representation has advantages and
disadvantages, and no single representation is best. 
It emerged while writing this chapter that simultaneously using
more than one representation of elements of $D(N,R)$ would be best.
It is easy to convert between them, and some algorithms are much
easier using one representation, than when using another.  
In this section we present two other representations, each which
has advantages and disadvantages.   But, we emphasize that there
is frequently no reason to restrict to only one representation!


We could represent $\eps$ by giving a list $[b_0,\ldots, b_n]$, where
each $b_i\in\Z/n\Z$ and $\eps(g_i) = \zeta^{b_i}$.  Then arithmetic in
$D(N,R)$ is arithmetic in $(\Z/n\Z)^{n+1}$, which is very efficient.
A drawback to this approach is that it is easy to accidently consider
sequences that do not actually correspond to elements of $D(N,R)$,
though it is not really any easier to do this than with the
representation we use elsewhere in this chapter.  Also the choice of
$\zeta$ is less clear, which can cause confusion.  Finally, the orders
of the local factors is more opaque, e.g., compare $[-1,\zeta_{40}]$
with $[20,1]$.  Overall this representation is not too bad, and is
more like representing a linear transformation by a matrix.
It has the {\bf advantage} over the representation discussed earlier
in this chapter that arithmetic in $D(N,R)$ is very efficient,
and doesn't require any operations in the ring $R$; such operations
could be quite slow, e.g., if $R$ were a large cyclotomic field.

Another way to represent~$\eps$ would be to give a list $[b_0,\ldots,
b_n]$ of integers, but this time with $b_i\in \Z/\gcd(s_i,n)\Z$, where
$s_i$ is the order of $g_i$.  Then $$\eps(g_i) = \zeta^{b_i \cdot
  n/(\gcd(s_i,n))},$$
which is already complicated enough to ring
warning bells.  With this representation we set up an identification
$$
D(N,R)\isom \bigoplus_i \Z/\gcd(s_i,n)\Z, $$
and arithmetic is
efficient.  This approach is seductive because every sequence of
integers determines a character, and the sizes of the integers in the
sequence nicely indicate the local orders of the character.  However,
giving analogues of many of the algorithms discussed in this chapter
that operate on characters represented this way is tricky.  For
example, the representation depends very much on the order of $\zeta$,
so it is difficult to correctly compute natural maps $D(N,R) \to
D(N,S)$, for $R\subset S$ rings, whereas for the representation
elsewhere in this chapter such maps are trivial to compute.  This was
the representation the author (Stein) implemented in MAGMA.

The PARI documentation says the following (where we have preserved
the incorrect typesetting):
\begin{quote}
  ``A {\em character} on the Abelian group $\oplus(\Z/N_i\Z)g_i$ is
  given by a row vector $\chi=[a_1,\ldots,a_n]$ such that $\chi(\prod
  g_i^{n_i}) = exp(2i \pi \sum a_i n_i/N_i)$.''
\end{quote}
This means that the abelian group has independent
generators $g_i$ of order $N_i$.  This definition says
that, e.g., the value
of the character on $g_1$ is 
$$
\chi(g_1) = (e^{2\pi i/N_1})^{a_1}.
$$
Thus the integers $a_i$ are integers modulo $N_i$, and this
representation is basically the same as the one we described
in the previous paragraph (and which the author does not like).




\begin{exercises}
\item\label{ex:cyclic}
This exercise is about the structure of the units of $\Z/p^n\Z$.
\begin{enumerate}
\item If~$p$ is odd and~$n$ is a positive integer,
prove that $(\Z/p^n\Z)^*$  is cyclic.
\item If $n\geq 3$ prove that $(\Z/2^n\Z)^*$ is a direct
sum of the cylclic subgroups $\langle -1 \rangle$
and $\langle 5 \rangle$, of orders 2 and $2^{n-2}$, 
respectively.
\end{enumerate}

\item \label{ex:orderalg}
Prove that Algorithm~\ref{alg:mingens} works, i.e., that 
if $g\in(\Z/p^r\Z)^*$ and $g^{n/p_i}\neq 1$ for all $p_i\mid n=\vphi(n)$,
then $g$ is a generator of $(\Z/p^r\Z)^*$.

\item \label{ex:dlogadd}
Let $p$ be an odd prime and $n\geq 2$ an integer, and prove
that
$$
  (1+p^{n-1}(\Z/p^n\Z),\,\times) \isom (\Z/p\Z,\,+).
$$
Use this to show that solving the discrete log problem
in $(\Z/p^n\Z)^*$ is ``not much harder'' than
solving the discrete log problem in $(\Z/p\Z)^*$.

\item \label{ex:cond2}
Suppose $\eps$ is a nontrivial Dirichlet character modulo $2^n$
of order~$r$ over the complex numbers $\C$.
Prove that the conductor of $\eps$ is
$$
  c = \begin{cases} 
       2^{\ord_2(r) + 1} & \text{if $\eps(5)=1$}\\
       2^{\ord_2(r) + 2} & \text{if $\eps(5)\neq 1$.}
     \end{cases}
$$

\item
\begin{enumerate}
\item Find an irreducible quadratic polynomial~$f$ over $\F_5$.
\item Then $\F_{25} = \F_5[x]/(f)$.  Find an element with multiplicative
order $5$ in $\F_{25}$.
\item Make a list of all Dirichlet characters in $D(25,\F_{25},\zeta)$.
\item Divide these characters up into orbits for the action
of $\Gal(\Fbar_5/\F_5)$.
\end{enumerate}


\end{exercises}










%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
%   NEW CHAPTER 
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%












\chapter{Eisenstein Series}\label{ch:eisen}
We introduce generalized Bernoulli numbers attached to Dirichlet
characters, and give an algorithm to enumerate the Eisenstein series
in $M_k(N,\eps)$.  We will wait until Chapter~\ref{ch:modsym} for an
algorithm to compute all cusp forms in $M_k(N,\eps)$.


\edit{There is something called the Akiyama-Tanigawa algorithm
for computing Bernoulli numbers.  It's in a paper by
Kaneko, Masanobu from Electronic
Journal of Integer Sequences, Vol. (3) article 00.2.9, 2000.}


\section{Generalized Bernoulli Numbers}
Suppose $\eps$ is a Dirichlet character modulo~$N$ over~$\C$.
\begin{definition}[Generalized Bernoulli Number]
Define the \defn{generalized Bernoulli numbers} $B_{k,\eps}$
attached to~$\eps$ by the following 
identity of infinite series:
$$
\sum_{a=1}^{N-1} \frac{\eps(a) \cdot x \cdot e^{ax}}{e^{Nx}-1}
                \,\, = \,\, 
\sum_{k=0}^{\infty} B_{k,\eps} \cdot \frac{x^k}{k!}.
$$
\end{definition}
If $\eps$ is the trivial character of modulus $1$ and $B_k$
are as in Section~\ref{sec:level_one_eisen}, then
$B_{k,\eps} = B_k$, except when $k=1$, in which case
$B_{1,\eps} = -B_1 = 1/2$ (see \exref{ch:eisen}{ex:bern_triv}).

Let $\Q(\eps)$ denote the field generated by the values
of the character $\eps$, so $\Q(\eps)$ is the cyclotomic
extension $\Q(\zeta_n)$, where $n$ is the order of $\eps$.
\begin{algorithm}{Bernoulli Numbers}\label{alg:gen_bernoulli}
Given an integer $k\geq 0$ and any
Dirichlet character  $\eps$ with modulus~$N$, this algorithm computes
the generalized Bernoulli numbers $B_{j,\eps}$, for $j\leq k$.
\begin{steps}
\item{}\label{step:ber1} Compute $g \set x/(e^{Nx}-1) \in \Q[[x]]$ to
  precision $O(x^{k+1})$ by computing $e^{Nx}-1 = \sum_{n\geq 1} N^n x^n/n!$ 
to precision $O(x^{k+2})$, and computing the inverse
$x/(e^{Nx}-1)$.  For completeness, note that if 
$f = a_0 + a_1 x + a_2x^2 + \cdots$, then we have
the following recursive formula for the coefficients $b_n$ of the
expansion of $1/f$:
$$
 b_n \set - \frac{b_0}{a_0} \cdot (b_{n-1}a_1 + b_{n-2}a_2 + \cdots + b_0 a_n).
$$
\item{}\label{step:ber2} For each $a=1,\ldots, N$, compute $f_a \set g
  \cdot e^{ax}\in\Q[[x]]$, to precision $O(x^{k+1})$.  This requires
computing $e^{ax}=\sum_{n\geq 0} a^n x^n/n!$ to precision $O(x^{k+1})$.
(One can omit computation of $e^{Nx}$ if $N>1$.)

\item{}\label{step:ber4} Then for $j\leq k$, we have 
$$B_{j,\eps} \set j!\cdot 
  \sum_{a=1}^{N} \eps(a) \cdot c_j(f_a),
$$ where $c_j(f_a)$ is the
  coefficient of $x^j$ in~$f_a$.
\end{steps}
\end{algorithm}
Note that in Steps~\ref{step:ber1} and \ref{step:ber2} we compute the
power series doing arithmetic only in $\Q[[x]]$, not in
$\Q(\eps)[[x]]$, which could be much less efficient if $\eps$ has
large order.   One could also write down a recurrence formula
for $B_{j,\eps}$, but this would simply encode arithmetic
in power series rings and the definitions in a formula.

\begin{example}
Let $\eps$ be the nontrivial character with modulus~$4$. Thus~$\eps$ 
has order~$2$ and takes values in~$\Q$.  Then the Bernoulli
numbers $B_{k,\eps}$ for $k$ even are all $0$ and for $k$ odd
they are
\begin{align*}
B_{1,\eps} &= -1/2\\
B_{3,\eps} &= 3/2\\
B_{5,\eps} &= -25/2\\
B_{7,\eps} &= 427/2\\
B_{9,\eps} &= -12465/2\\
B_{11,\eps} &= 555731/2\\
B_{13,\eps} &= -35135945/2\\
B_{15,\eps} &= 2990414715/2\\
B_{17,\eps} &= -329655706465/2\\
B_{19,\eps} &= 45692713833379/2.
\end{align*}
%G = DirichletGroup(4)
%e = G._0
%[e.bernoulli(k) for k in range(20) if k%2==1]
%print "\n".join(['B_{%s,\\eps} &= %s\\\\'%(k,e.bernoulli(k)) for k in range(20) if k%2==1])
These Bernoulli numbers can be divisible by large primes.  For example,
$B_{17,\eps} = 5\cdot 17^2 \cdot 228135437 / 2$.
\end{example}

\begin{example}
  This examples illustrates that the generalized Bernoulli numbers
  need not be rational numbers.  Suppose~$\eps$ is the mod~$5$ character
such that $\eps(2) = i = \sqrt{-1}$.  Then  $B_{k,\eps}=0$ for $k$ even
and
\begin{align*}
B_{1,\eps} &= \frac{-i - 3}{5}\\
B_{3,\eps} &= \frac{6i + 12}{5}\\
B_{5,\eps} &= \frac{-86i - 148}{5}\\
B_{7,\eps} &= \frac{2366i + 3892}{5}\\
B_{9,\eps} &= \frac{-108846i - 176868}{5}\\
B_{11,\eps} &= \frac{7599526i + 12309572}{5}\\
B_{13,\eps} &= \frac{-751182406i - 1215768788}{5}\\
B_{15,\eps} &= \frac{99909993486i + 161668772052}{5}\\
B_{17,\eps} &= \frac{-17209733596766i - 27846408467908}{5}\\
%B_{19,\eps} &= \frac{3727215827984246i + 6030787602527332}{5}.
\end{align*}

% G = DirichletGroup(5)
% e = G.gen(0)
% s = "\n".join(['B_{%s,\\eps} &= \\frac{%s}{5}\\\\'%(k,5*e.bernoulli(k)) for k in range(20) if k%2==1]); s=s.replace("*zeta_4","i")
% print s

\end{example}


\begin{proposition}
If $\eps(-1) \neq (-1)^k$, then $B_{k,\eps}=0$.
\end{proposition}


\section{Explicit Basis for the Eisenstein Subspace}
Suppose $\chi$ and $\psi$ are primitive Dirichlet characters with
conductors $L$ and $M$, respectively.  
Let
\begin{equation}\label{eqn:eisen}
 E_{k,\chi,\psi}(q) = c_0 + \sum_{m \geq 1} \left(
                  \sum_{n|m} \psi(n) \cdot \chi(m/n) \cdot n^{k-1}\right) q^{m}
\in \Q(\chi, \psi)[[q]],
\end{equation}
where 
$$
c_0 = \begin{cases} 0 & \text{ if } L>1, \\
\ds- \frac{B_{k,\psi}}{2k} & \text{ if } L=1.
\end{cases}
$$
Note that when $\chi=\psi=1$ and $k\geq 4$, then $E_{k,\chi,\psi} = E_k$,
where $E_k$ is from Chapter~\ref{ch:modform}.

Miyake proves statements that imply the following theorems in
\cite[Ch.~7]{miyake}.  We will not prove them in this book since
developing the theory needed to prove them would take us far afield
from our goal, which is to compute $M_k(N,\eps)$.
\begin{theorem}\label{thm:eisser}
Suppose $t$ is a positive integer and $\chi$, $\psi$ are as above,
and that~$k$ is a positive integer such that $\chi(-1)\psi(-1) = (-1)^k$.
Except when $k=2$ and $\chi=\psi=1$, the power series 
$E_{k,\chi,\psi}(q^t)$ defines an element of 
$M_k(MLt,\chi/\psi)$.
If $\chi=\psi=1$, $k=2$, $t>1$,  and $E_2 = E_{k,\chi,\psi}$, then 
$E_2(q) - t E_2(q^t)$ is a modular form in $M_2(\Gamma_0(t))$.
\end{theorem}

\begin{theorem}\label{thm:eisgen}
The Eisenstein series in $M_k(N, \eps)$ coming from Theorem~\ref{thm:eisser}
form a basis for the Eisenstein subspace $E_k(N,\eps)$.
\end{theorem}

\begin{theorem}\label{thm:eiseigen}
The Eisenstein series 
$E_{k,\chi,\psi}(q) \in M_k(ML)$ defined above
is an eigenvector for all Hecke operators $T_n$.  
Also $E_2(q) - t E_2(q^t)$, for $t>1$, is an eigenform.
\end{theorem}
Since $E_{k,\chi,\psi}(q)$ is normalizes so the coefficient
of~$q$ is $1$, the eigenvalue of $T_m$  is 
$$\sum_{n|m} \psi(n) \cdot \chi(m/n) \cdot n^{k-1}.$$
Also for $f = E_2(q) - t E_2(q^t)$ with $t>1$ prime, the coefficient of~$q$ 
is~$1$, and $T_m(f) = \sigma_{1}(m)\cdot f$ for $(m,t)=1$, and $T_t(f) = 
((t+1)-t)f = f$.

\begin{algorithm}{Enumerating Eisenstein Series}\label{alg:enum_eisen}
  Given a weight~$k$ and a Dirichlet character~$\eps$ of modulus~$N$,
  this algorithm computes a basis for the Eisenstein
  subspace $E_k(N,\eps)$ of $M_k(N,\eps)$ to precision $O(q^r)$.
\begin{steps}
\item{}[Weight 2 Trivial Character?] If $k=2$ and $\eps=1$, output the
  Eisenstein series $E_2(q) - tE_2(q^t)$, for each divisor $t\mid N$ with $t\neq
  1$, then terminate.
\item{}[Compute Dirichlet Group] Let $G\set D(N,\Q(\zeta_n))$ be the group of Dirichlet
characters with values in $\Q(\zeta_n)$, where~$n$ is the exponent
fo $(\Z/N\Z)^*$.
\item{}[Compute Conductors]\label{step:enum_eisen3}  Compute the conductor of every element of $G$ (which just
involves computing the orders of the local components of each character).
%View~$\eps$ as an element of~$G$, and compute
%the conductor $\cond(\eps)$ of~$\eps$.
\item{}[List Characters $\chi$]\label{step:enum_eisen4} Form a list $V$ all Dirichlet characters $\chi \in G$ 
such that $\cond(\chi)\cdot \cond(\chi/\eps)$ divides~$N$.
\item{}[Compute Eisenstein Series] For each character $\chi$ in $V$, let $\psi = \chi/\eps$, and
compute $E_{k,\chi,\psi}(q^t)\pmod{q^r}$ for each divisor~$t$ of 
$N/(\cond(\chi)\cdot \cond(\psi))$.  We compute $E_{k,\chi,\psi}(q^t) \pmod{q^r}$
using (\ref{eqn:eisen}) and Algorithm~\ref{alg:gen_bernoulli}.

\end{steps}
\end{algorithm}

\begin{remark}
Algorithm~\ref{alg:enum_eisen} is what I currently use in my programs.
It might be better to first reduce to the prime power case by writing
all characters as product of local characters and combine
Steps~\ref{step:enum_eisen3} and \ref{step:enum_eisen4} into a single
step that involves orders.  However, this might make things more
complicated and obscure.
\end{remark}

\begin{example}
The following is a basis of Eisenstein series 
$E_{2,\chi,\psi}$ for $E_2(\Gamma_1(13))$.
%skip
\begin{verbatim}
f1 = 1/2 + q + 3*q^2 + 4*q^3 + O(q^4)

f2 = (-7/13*zeta_12^2 - 11/13) + q + (2*zeta_12^2 + 1)*q^2 
                               + (-3*zeta_12^2 + 1)*q^3 + O(q^4)

f3 = q + (zeta_12^2 + 2)*q^2 + (-1*zeta_12^2 + 3)*q^3 + O(q^4)

f4 = (-1*zeta_12^2) + q + (2*zeta_12^2 - 1)*q^2 
                        + (3*zeta_12^2 - 2)*q^3 + O(q^4)

f5 = q + (zeta_12^2 + 1)*q^2 + (zeta_12^2 + 2)*q^3 + O(q^4)

f6 = (-1) + q + (-1)*q^2 + 4*q^3 + O(q^4)

f7 = q + q^2 + 4*q^3 + O(q^4)

f8 = (zeta_12^2 - 1) + q + (-2*zeta_12^2 + 1)*q^2 
                         + (-3*zeta_12^2 + 1)*q^3 + O(q^4)

f9 = q + (-1*zeta_12^2 + 2)*q^2 + (-1*zeta_12^2 + 3)*q^3 + O(q^4)

f10 = (7/13*zeta_12^2 - 18/13) + q + (-2*zeta_12^2 + 3)*q^2 
                                   + (3*zeta_12^2 - 2)*q^3 + O(q^4)

f11 = q + (-1*zeta_12^2 + 3)*q^2 + (zeta_12^2 + 2)*q^3 + O(q^4)
\end{verbatim}
\end{example}

\begin{exercises}
\item\label{ex:has_width} Suppose $\gamma\in\SL_2(\Z)$ and $N$
is a positive integer.  Prove that there is a positive integer~$h$
such that $\abcd{1}{h}{0}{1} \in \gamma^{-1}\Gamma_1(N)\gamma$.

\item\label{ex:surjred} Prove that the map $\SL_2(\Z)\to
  \SL_2(\Z/N\Z)$ is surjective.  (Hint: There is a proof of a more
  general result near the beginning of Shimura's book \cite{shimura:intro}.)

\item\label{ex:gamma0} Prove that $M_k(N,1) = M_k(\Gamma_0(N))$.

\item\label{ex:diag} Suppose $A$ and $B$ are diagonalizable 
linear transformations of a finite-dimensional vector space~$V$
and that both $A$ and $B$ are diagonalizable.  Prove there is a basis
for $V$ so that the matrices of $A$ and $B$ with respect to that
both are simultaneously diagonal.

\item\label{ex:bern_triv} If $\eps$ is the trivial character of
  modulus $1$ and $B_k$ are as in Section~\ref{sec:level_one_eisen},
  then $B_{k,\eps} = B_k$, except when $k=1$, in which case
  $B_{1,\eps} = -B_1 = 1/2$.

\item\label{ex:odd_bernoulli} 
Prove that if $n>1$ is odd, then the Bernoulli number $B_n$ is $0$.

\end{exercises}









%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
%   NEW CHAPTER 
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%












\chapter{Dimensions Formulas}
\label{ch:dim}

When computing with spaces of modular forms, it is helpful to have
easy-to-compute formulas for dimensions of these spaces, and certain
of their subspaces.  For example, they provide a double-check on the
output of the algorithms from Chapter~\ref{ch:modsym} that compute
explicit bases for spaces of modular forms.  Alternatively, dimension
formulas can be used to improve the efficiency of some of the
algorithms in Chapter~\ref{ch:modsym}, since we can use them to determine
the ranks of certain matrices without having to explicitly compute
them.  If we know the dimension of $M_k(N,\eps)$, and we have a
process for computing $q$-expansions of elements of $M_k(N,\eps)$,
e.g., multiplying together $q$-expansions of certain forms of smaller
weight or searching for $\theta$-series attached to quadratic forms,
then we can tell when we are done generating $M_k(N,\eps)$.

This chapter contains formulas the author knows for computing
dimensions of spaces of modular forms, along with some hints about how
to compute them, when this isn't obvious.  In several cases we give
dimension formulas for spaces that haven't yet been defined in this
book, so we define them in this chapter (e.g., we will discuss
newforms and oldforms further).  We also give many examples, which
were computed using the modular symbols algorithms from
Chapter~\ref{ch:modsym}.

Many of the dimension formulas and algorithms we give below grew out
of a program that Bruce Caskel wrote (around 1996) in PARI, which
Kevin Buzzard extended.  Their program codified dimension formulas
that Buzzard and Caskel found or extracted from the literature (mainly
\cite[\S2.6]{shimura:intro}).  The algorithm for dimensions of spaces
with nontrivial character are from~\cite{cohen-oesterle:dimensions},
with some slight refinements from Kevin Buzzard.

For the rest of this chapter,~$N$ denotes a positive integer and $k\geq
2$ is an integer.  We give {\bf no formulas} for dimensions of spaces
of weight $1$ modular forms, because it is an {\em open problem} to give
such formulas; the geometric methods used to derive the formulas below
do not apply in the case $k=1$.  If $k=0$, the only modular forms are
the constants, and for $k<0$ the dimension of $M_k(N,\eps)$ is $0$.

For a nonzero integer $N$ and a prime~$p$, let $v_p(N)$ be the
largest~$e$ such that $p^e \mid N$.  In the formulas below,~$p$ always
denotes a prime number.  Let $M_k(N,\eps)$ be the space of modular
forms of level~$N$ weight~$k$ and character~$\eps$, and $S_k(N,\eps)$
and $E_k(N,\eps)$ the cuspidal and Eisenstein subspaces.  

The dimension formulas below for $S_k(\Gamma_0(N))$,
$S_k(\Gamma_1(N))$, $E_k(\Gamma_0(N))$ and $E_k(\Gamma_1(N))$ below
are almost straight from \cite[\S2.6]{shimura:intro} (see also
\cite[\S2.5]{miyake}), and they are derived using the Riemann-Roch
Theorem applied to the covering $X_0(N)\to X_0(1)$ or $X_1(N)\to
X_1(1)$ and appropriately chosen divisors.  It would be natural to
give a sample argument along these lines at this point, but I will not
since it easy to find such arguments in  other books and survey
papers (see, e.g., \cite{diamond-im}).  So you will not learn much about how to
derive dimension formulas from this chapter.  What you will learn is
what is known about dimension formulas and what some of the obscure
references are.

\section{Modular Forms for $\Gamma_0(N)$}\label{sec:dimg0}
Define functions of a positive integer~$N$ by the following formulas:
\begin{align*}
\mu_0(N) &= \prod_{p\mid N} \left( p^{v_p(N)} + p^{v_p(N)-1} \right) \\
\mu_{0,2}(N) &= \begin{cases}
    0 & \text{if $4\mid N$,}\\
  \prod_{p\mid N} \left(1 + \kr{-4}{p}\right) & \text{otherwise.}
\end{cases}\\
\mu_{0,3}(N) &= \begin{cases}
    0 & \text{if $2\mid N$ or $9\mid N$,}\\
  \prod_{p\mid N} \left(1 + \kr{-3}{p}\right) & \text{otherwise.}
\end{cases}\\
c_0(N) &= \sum_{d\mid N} \vphi(\gcd(d,N/d)) \\
g_0(N) &= 1 + \frac{\mu_0(N)}{12} - \frac{\mu_{0,2}(N)}{4} - \
               \frac{\mu_{0,3}(N)}{3} - \frac{c_0(N)}{2}\\
\end{align*}
Note that $\mu_0(N)$ is the index of $\Gamma_0(N)$ in $\SL_2(\Z)$.
Also $g_0(N)$ is the genus of the modular curve $X_0(N)$, and $c_0(N)$
is the number of cusps of $X_0(N)$.

\begin{proposition}
We have $\dim S_2(\Gamma_0(N)) = g_0(N)$, and
for $k\geq 4$ even, 
\begin{align*}
\dim S_k(\Gamma_0(N)) &= 
 (k-1) \cdot (g_0(N) - 1) \,\,+ \,\,
\left( \frac{k}{2} - 1 \right) \cdot c_0(N) \,\, +  \\
  &\qquad\qquad  \mu_{0,2}(N)\cdot \left\lfloor\frac{k}{4}\right\rfloor \,\,+ \,\,
     \mu_{0,3}(N)\cdot \left\lfloor \frac{k}{3}\right\rfloor.
\end{align*}
The dimension of the Eisenstein subspace is as follows:
$$
  \dim E_k(\Gamma_0(N)) = 
\begin{cases}
c_0(N) & \text{if $k\neq 2$,}\\
c_0(N)-1 & \text{if $k=2$.}
\end{cases}
$$
\end{proposition}

The following table contains the dimension of $S_k(\Gamma_0(N))$
for some sample values of $N$ and $k$:
\begin{center}
\begin{tabular}{|l|llll|}\hline
$N$ & $\dim S_2(\Gamma_0(N))$ & $\dim S_4(\Gamma_0(N))$ & 
      $\dim S_6(\Gamma_0(N))$ & $\dim S_{24}(\Gamma_0(N))$\\\hline
1 & 0 & 0 & 0 & 2\\
10 & 0 & 3 & 5 & 33\\
11 & 1 & 2 & 4 & 22\\
100 & 7 & 36 & 66 & 336\\
389 & 32 & 97 & 161 & 747\\
1000 & 131 & 430 & 730 & 3430\\
2004 & 331 & 1002 & 1674 & 7722\\
100000 & 14801 & 44800 & 74800 & 344800\\\hline
\end{tabular}
\end{center}

\subsection{New and Old Subspaces}
For each divisor $N'$ of $N$, there are natural maps 
$$
\alpha_d :
M_k(\Gamma_0(N')) \to M_k(\Gamma_0(N)), 
$$
corresponding to the
divisors $d$ of $N/N'$, and maps 
$$
\beta_d: M_k(\Gamma_0(N)) \to
M_k(\Gamma_0(N')).  
$$
such that $\beta_d\circ \alpha_d$ is
multiplication by a nonzero scalar.  On $q$-expansions,
$\alpha_d(f(q)) = f(q^d)$, and the definition of $\beta_d$ is a
more complicated ``trace map'' (see, e.g., \cite{lang:modular}). 

The space $M_k(\Gamma_0(N))$ decomposes as a direct sum 
$$
M_k(\Gamma_0(N))  = M_k(\Gamma_0(N))^{\old} \oplus M_k(\Gamma_0(N))^{\new},
$$
where 
$M_k(\Gamma_0(N))^{\old}$ is the subspace generated by all images
$\alpha_d(M_k(\Gamma_0(N'))$ where $N'$ runs through proper divisors
of $N$ and $d$ runs through all divisors of $N/N'$.  
The new subspace $M_k(\Gamma_0(N))^{\new}$ can be defined as either
the intersection of the kernels of all maps $\beta_d$
to lower level, or the largest Hecke-stable complement of
$M_k(\Gamma_0(N))^{\old}$. 

Atkin and Lehner \cite{atkin-lehner} proved that
the space $S_k(\Gamma_0(N))$ is built out of new subspaces,
in the following sense.
\begin{theorem}[Atkin-Lehner]\label{thm:atkin-lehner}
We have an isomorphism
$$S_k(\Gamma_0(N)) = 
   \sum_{M\mid N} \sum_{d\mid N/M} \alpha_d(S_k(\Gamma_0(M))^{\new}).
$$
This is an isomorphism of $\T'$ modules, where $\T'$ is the
anemic Hecke algebra, i.e., the subring generated by Hecke
operators $T_n$ with $\gcd(n,N)=1$.
\end{theorem}
This theorem reduces the problem of computing $S_k(\Gamma_0(N))$ to
that of computing $S_k(\Gamma_0(M))^{\new}$ for divisors~$M$ of~$N$,
a fact that will be central later in this book.
Atkin and Lehner also prove that one can completely determine
$S_k(\Gamma_0(M))^{\new}$ just from the information of how the Hecke
operators act on it (their ``multiplicity one'' theory).  
Atkin and Lehner's work was generalized to fairly arbitrary congruence
subgroups of $\SL_2(\Z)$ by Winnie Li in her Berkeley Ph.D. thesis
under A. Ogg (see \cite{winnie:newforms}).

If $N''\mid N'\mid N$, then the maps $\alpha_d$ from
$M_k(\Gamma_0(N''))$ to $M_k(\Gamma_0(N))$ factor through
$M_k(\Gamma_0(N'))$.  Thus in the definition of
$M_k(\Gamma_0(N))^{\old}$ and $M_k(\Gamma_0(N))^{\new}$, it would
suffice to consider only proper divisors $N'$ of $N$ such that $N/N'$
is prime.  

\vspace{1ex}
\noindent{\bf Warning:} For a fixed $N'=N/p$, the images of $\alpha_1$ and $\alpha_p$
need {\em not} always be linearly independent (see
Example~\ref{ex:new_old} below).  However, the images of the new
subspace $S_k(\Gamma_0(N'))^{\new}$ are linearly independent, 
as asserted by Theorem~\ref{thm:atkin-lehner}.
 
\begin{proposition}\label{prop:newg0}
The dimension of the new subspace is
$$
 \dim S_k(\Gamma_0(N))^{\new} = \sum_{M\mid N} \overline{\mu}(N/M) 
   \cdot \dim S_k(\Gamma_0(M)),
$$
where the sum is over the positive divisors of $N$, and for an integer $R$,
$$
\overline{\mu}(R) = 
\begin{cases} 
 0 & \text{if $p^3\mid R$ for some $p$}\\
\ds \prod_{p\mid\mid R} -2 & \text{otherwise},
\end{cases}
$$
where the product is over primes that exactly divide $n$.
(Note that $\overline{\mu}$ is {\em not} the Moebius function, but
is similar to it.)
\end{proposition}\label{prop:dimg0}
Let $f(n) = \dim S_k(\Gamma_0(n))$ and
$g(n)=\dim S_k(\Gamma_0(n))^{\new}$.
Theorem~\ref{thm:atkin-lehner} implies that 
\begin{equation}\label{eqn:mumu}
  f(N) = \sum_{M\mid N} \sigma_0(N/M) g(M),
\end{equation}
where $\sigma_0(N/M)$ is the number of divisors of $N/M$.
Presumably there is an analogue of Moebius inversion,
but for functions with the property in (\ref{eqn:mumu}),
which involves the function $\overline{\mu}$. 




\begin{example}\label{ex:new_old}
The space $M_2(\Gamma_0(45))$ has dimension $10$ and basis
%skip
\begin{verbatim}
1 + 12*q^15 + O(q^20),
q + q^7 + 3*q^16 + 6*q^19 + O(q^20),
q^2 + 4*q^11 + 3*q^14 + q^17 + O(q^20),
q^3 + q^12 + q^15 + 3*q^18 + O(q^20),
q^4 + q^7 + 2*q^13 + 4*q^16 + 2*q^19 + O(q^20),
q^5 + O(q^20),
q^6 + 2*q^12 + 2*q^15 - q^18 + O(q^20),
q^8 + q^14 + q^17 + O(q^20),
q^9 - 2*q^15 + 3*q^18 + O(q^20),
q^10 + O(q^20)
\end{verbatim}
The new subspace is spanned by the single cusp form
%skip
\begin{verbatim}
q + q^2 - q^4 - q^5 - 3*q^8 - q^10 + 4*q^11 - 2*q^13 + O(q^14)
\end{verbatim}
First consider $N'=45/3=15$.  The space $M_2(\Gamma_0(15))$ has
basis
%skip
\begin{verbatim}
1 + 12*q^5 + O(q^8),
q + q^4 + q^5 + 3*q^6 + 2*q^7 + O(q^8),
q^2 + 2*q^4 + 2*q^5 - q^6 + 2*q^7 + O(q^8),
q^3 - 2*q^5 + 3*q^6 + O(q^8)
\end{verbatim}
There are two maps $\alpha_1$ and $\alpha_3$ from 
$M_2(\Gamma_0(15))$ to $M_2(\Gamma_0(45))$. 
The one dimension space $M_2(\Gamma_0(5))$ embeds
in $M_2(\Gamma_0(15))$ via $f(q)\mapsto f(q)$
and $f(q)\mapsto f(q^3)$.  We have a commutative diagram
$$
\xymatrix{
                          & {M_2(\Gamma_0(15))}\ar[rd]^{\alpha_3} \\
{M_2(\Gamma_0(5))}\ar[ur]^{\alpha_1}\ar[dr]^{\alpha_3} &  & {M_2(\Gamma_0(45)).}\\
                          & {M_2(\Gamma_0(15))}\ar[ur]^{\alpha_1}
}$$
This diagram illustrates that the intersection of the two images of 
$M_2(\Gamma_0(15))$ has dimension at least $1$.  In fact, the
sum of the images of the two maps from $M_2(\Gamma_0(15))$ is a 
$7$-dimensional subspace of $M_2(\Gamma_0(45))$.

Next consider $N'=45/5=9$, where the space $M_2(\Gamma_0(9))=E_2(\Gamma_0(9))$ has
as basis the three forms
%skip
\begin{verbatim}
1 + 12*q^3 + 36*q^6 + O(q^8),
q + 7*q^4 + 8*q^7 + O(q^8),
q^2 + 2*q^5 + O(q^8)
\end{verbatim}
There are two maps $\alpha_1$ and $\alpha_5$ from 
$M_2(\Gamma_0(9))$ to $M_2(\Gamma_0(45))$. 
The images of these two maps span a space of dimension $6$,
and this space intersects the span of the images of $M_2(\Gamma_0(15))$
in a space of dimension $4$.  Thus the old subspace
$M_2(\Gamma_0(45))^{\old}$ has dimension $9$, and the
new subspace has dimension $1$.  The new subspace
is spanned by the single cusp form
%skip
\begin{verbatim}
q + q^2 - q^4 - q^5 - 3*q^8 - q^10 + 4*q^11 + O(q^12)
\end{verbatim}
\end{example}

\begin{remark}
  Csirik, Wetherell, and Zieve prove in
  \cite{csirik-wetherell-zieve:g0} that a random positive integer has
  probability~$0$ of being a value of $g_0(N)=\dim S_2(\Gamma_0(N))$,
  and give bounds on the size of the set of values of $g_0(N)$ below
  some given~$x$.  For example, they show that $150, 180, 210, 286,
  304, 312, \ldots$ are the first few integers that are not of the
  form $g_0(N)$ for some~$N$.
\end{remark}


\section{Modular Forms for $\Gamma_1(N)$}
This section follows Section~\ref{sec:dimg0} closely, but with
suitable modifications with $\Gamma_0(N)$ replaced by $\Gamma_1(N)$.
The notion of new and old subspaces for $\Gamma_1(N)$ is exactly the
same as for $\Gamma_0(N)$; simply replace $\Gamma_0(N)$ by
$\Gamma_1(N)$ in the discussion of new and old forms in
Section~\ref{sec:dimg0}.

Define functions of a positive integer~$N$ by the following formulas:
\begin{align*}
\mu_1(N) &= 
\begin{cases}
\mu_0(N) & \text{if $N=1,2$,}\\
\ds\frac{\phi(N)\cdot \mu_0(N)}{2} & \text{otherwise.}
\end{cases} \\
\mu_{1,2}(N) &= \begin{cases}
    0 & \text{if $N\geq 4$,}\\
  \mu_{0,2}(N) & \text{otherwise.}
\end{cases}\\
\mu_{1,3}(N) &= \begin{cases}
    0 & \text{if $N\geq 4$,}\\
    \mu_{0,3}(N) & \text{otherwise.}
\end{cases}\\
c_1(N) &= 
\begin{cases}
  c_0(N) & \text{if $N=1,2$,}\\
  3      & \text{if $N=4$,}\\
  \ds \sum_{d \mid N} \frac{\phi(d)\phi(N/d)}{2} & \text{otherwise}.
\end{cases} \\
g_1(N) &= 1 + \frac{\mu_1(N)}{12} - \frac{\mu_{1,2}(N)}{4} - \frac{\mu_{1,3}(N)}{3}
            - \frac{c_1(N)}{2}
\end{align*}
Note that $g_1(N)$ is the genus of the modular curve $X_1(N)$, 
and $c_1(N)$ is the number of cusps of $X_1(N)$.
\todo{Make sure this is right for $N\leq 5$.}

\begin{proposition}
  We have $\dim S_2(\Gamma_1(N)) = g_1(N)$.  If $N\leq 2$, then $$\dim
  S_k(\Gamma_1(N)) = \dim S_k(\Gamma_0(N)),$$
  where $\dim
  S_k(\Gamma_0(N))$ is given by the formula of
  Proposition~\ref{prop:dimg0}.  If $k\geq 3$, let $$
  a = (k-1)(g_1(N)
  - 1) + \left(\frac{k}{2} -1\right)\cdot c_1(N).  $$
  Then for $N\geq
  3$, $$
  \dim S_k(\Gamma_1(N)) =
\begin{cases}
 a + 1/2 & \text{if $N=4$ and $2\nmid k$,}\\
 a + \lfloor{}