CoCalc Public Fileswww / 168 / notes / modular_forms_book / current.tex
Author: William A. Stein
Compute Environment: Ubuntu 18.04 (Deprecated)
1\documentclass{book}
2\author{William Stein}
3\title{Computing With Modular Forms}
4
5\usepackage{index}
6\usepackage{amsmath}
7\usepackage{amsfonts}
8\usepackage{amssymb}
9\usepackage{amsthm}
10\usepackage[all]{xy}
11\usepackage{sage}
12
13\newcommand{\code}[1]{{\tt #1}}
14
15\usepackage{xspace}  % to allow for text macros that don't eat space
16\newcommand{\SAGE}{{\sf SAGE}\xspace}
17\newcommand{\sage}{\SAGE}
18
19
20%\newcommand{\comment}[1]{}
21
22%\usepackage[hyperindex,pdfmark]{hyperref}
23\usepackage[hypertex]{hyperref}
24
25%\newcommand{\edit}[1]{{\bf [[Todo: #1]]}}
26\newcommand{\edit}[1]{}
27\newcommand{\examplesession}[1]{}
28\newcommand{\gzero}{\Gamma_0(N)}
29\newcommand{\esM}{\overline{\sM}}
30\newcommand{\sM}{\mathbb{M}}
31\newcommand{\sS}{\mathbb{S}}
32\newcommand{\sB}{\mathbb{B}}
33\newcommand{\eE}{\mathbf{E}}
34\newcommand{\Adual}{A^{\vee}}
35\newcommand{\Bdual}{B^{\vee}}
36
37\newcommand{\defn}[1]{{\em \index*{#1}}}
38\newcommand{\solution}[1]{\vspace{1em}\par\noindent{\bf Solution #1.} }
39\newcommand{\todo}[1]{{\bf [[TODO: #1]]}}
40\newcommand{\done}[1]{\noindent {\small \textsf{Done: #1}}\\}
41\newcommand{\danger}[1]{\marginpar{\small \textsl{#1}}}
42\renewcommand{\div}{\mbox{\rm div}}
43\DeclareMathOperator{\chr}{char}
44\DeclareMathOperator{\ind}{ind}
45\DeclareMathOperator{\im}{im}
46\DeclareMathOperator{\oo}{\infty}
47\DeclareMathOperator{\abs}{abs}
48\DeclareMathOperator{\lcm}{lcm}
49\DeclareMathOperator{\cores}{cores}
50\DeclareMathOperator{\coker}{coker}
51\DeclareMathOperator{\image}{image}
52\DeclareMathOperator{\prt}{part}
53\DeclareMathOperator{\proj}{proj}
54\DeclareMathOperator{\Br}{Br}
55\DeclareMathOperator{\Ann}{Ann}
56\DeclareMathOperator{\End}{End}
57\DeclareMathOperator{\Tan}{Tan}
58\DeclareMathOperator{\Eis}{Eis}
59\newcommand{\unity}{\mathbf{1}}
60\DeclareMathOperator{\Pic}{Pic}
61\DeclareMathOperator{\Vol}{Vol}
62\DeclareMathOperator{\Vis}{Vis}
63\DeclareMathOperator{\Reg}{Reg}
64%\DeclareMathOperator{\myRes}{Res}
65%\newcommand{\Res}{\myRes}
66\DeclareMathOperator{\Res}{Res}
67\newcommand{\an}{{\rm an}}
68\DeclareMathOperator{\rank}{rank}
69\DeclareMathOperator{\Sel}{Sel}
70\DeclareMathOperator{\Mat}{Mat}
71\DeclareMathOperator{\BSD}{BSD}
72\DeclareMathOperator{\id}{id}
73%\DeclareMathOperator{\dz}{dz}
74\newcommand{\dz}{dz}
75%\DeclareMathOperator{\Re}{Re}
76\renewcommand{\Re}{\mbox{\rm Re}}
77%\DeclareMathOperator{\Im}{Im}
78\DeclareMathOperator{\Selmer}{Selmer}
79\newcommand{\pfSel}{\widehat{\Sel}}
80\newcommand{\qe}{\stackrel{\mbox{\tiny ?}}{=}}
81\newcommand{\isog}{\simeq}
82\newcommand{\e}{\mathbf{e}}
83\newcommand{\bN}{\mathbf{N}}
84
85% ---- SHA ----
86\DeclareFontEncoding{OT2}{}{} % to enable usage of cyrillic fonts
87  \newcommand{\textcyr}[1]{%
88    {\fontencoding{OT2}\fontfamily{wncyr}\fontseries{m}\fontshape{n}%
89     \selectfont #1}}
90\newcommand{\Sha}{{\mbox{\textcyr{Sh}}}}
91
92%\font\cyr=wncyr10 scaled \magstep 1
93%\font\cyr=wncyr10
94
95%\newcommand{\Sha}{{\cyr X}}
96\newcommand{\set}{=}
97\newcommand{\Shaan}{\Sha_{\mbox{\tiny \rm an}}}
98\newcommand{\TS}{Shafarevich-Tate group}
99
100\newcommand{\Gam}{\Gamma}
101\renewcommand{\Im}{\text{Im}}
102\newcommand{\X}{\mathcal{X}}
103\newcommand{\cH}{\mathcal{H}}
104\newcommand{\cA}{\mathcal{A}}
105\newcommand{\cF}{\mathcal{F}}
106\newcommand{\cG}{\mathcal{G}}
107\newcommand{\cJ}{\mathcal{J}}
108\newcommand{\cL}{\mathcal{L}}
109\newcommand{\cV}{\mathcal{V}}
110\newcommand{\cO}{\mathcal{O}}
111\newcommand{\cQ}{\mathcal{Q}}
112\newcommand{\cX}{\mathcal{X}}
113\newcommand{\ds}{\displaystyle}
114\newcommand{\M}{\mathcal{M}}
115\newcommand{\B}{\mathcal{B}}
116\newcommand{\E}{\mathcal{E}}
117\renewcommand{\L}{\mathcal{L}}
118\newcommand{\J}{\mathcal{J}}
119\DeclareMathOperator{\new}{new}
120\DeclareMathOperator{\Morph}{Morph}
121\DeclareMathOperator{\old}{old}
122\DeclareMathOperator{\Sym}{Sym}
123\DeclareMathOperator{\Symb}{Symb}
124%\newcommand{\Sym}{\mathcal{S}{\rm ym}}
125\newcommand{\dw}{\delta(w)}
126\newcommand{\dwh}{\widehat{\delta(w)}}
127\newcommand{\dlwh}{\widehat{\delta_\l(w)}}
128\newcommand{\dash}{-\!\!\!\!-\!\!\!\!-\!\!\!\!-}
129\DeclareMathOperator{\tor}{tor}
130\newcommand{\Frobl}{\Frob_{\ell}}
131\newcommand{\tE}{\tilde{E}}
132\renewcommand{\l}{\ell}
133\renewcommand{\t}{\tau}
134\DeclareMathOperator{\cond}{cond}
135\DeclareMathOperator{\Spec}{Spec}
136\DeclareMathOperator{\Div}{Div}
137\DeclareMathOperator{\Jac}{Jac}
138\DeclareMathOperator{\res}{res}
139\DeclareMathOperator{\Ker}{Ker}
140\DeclareMathOperator{\Coker}{Coker}
141\DeclareMathOperator{\sep}{sep}
142\DeclareMathOperator{\sign}{sign}
143\DeclareMathOperator{\unr}{unr}
144\DeclareMathOperator{\Char}{char}
145\newcommand{\N}{\mathcal{N}}
146\newcommand{\U}{\mathcal{U}}
147\newcommand{\Kbar}{\overline{K}}
148\newcommand{\Lbar}{\overline{L}}
149\newcommand{\gammabar}{\overline{\gamma}}
150\newcommand{\q}{\mathbf{q}}
151\renewcommand{\star}{\times}
152\newcommand{\gM}{\mathfrak{M}}
153\newcommand{\gA}{\mathfrak{A}}
154\newcommand{\gP}{\mathfrak{P}}
155\newcommand{\bmu}{\boldsymbol{\mu}}
156\newcommand{\union}{\cup}
157\newcommand{\Tl}{T_{\ell}}
158\newcommand{\into}{\rightarrow}
159\newcommand{\onto}{\rightarrow\!\!\!\!\rightarrow}
160\newcommand{\intersect}{\cap}
161\newcommand{\meet}{\cap}
162\newcommand{\cross}{\times}
163\DeclareMathOperator{\md}{mod}
164\DeclareMathOperator{\toric}{toric}
165\DeclareMathOperator{\tors}{tors}
166\DeclareMathOperator{\Frac}{Frac}
167\DeclareMathOperator{\corank}{corank}
168\newcommand{\rb}{\overline{\rho}}
169\newcommand{\ra}{\rightarrow}
170\newcommand{\xra}[1]{\xrightarrow{#1}}
171\newcommand{\hra}{\hookrightarrow}
172\newcommand{\kr}[2]{\left(\frac{#1}{#2}\right)}
173\newcommand{\la}{\leftarrow}
174\newcommand{\lra}{\longrightarrow}
175\newcommand{\riso}{\xrightarrow{\sim}}
176\newcommand{\da}{\downarrow}
177\newcommand{\ua}{\uparrow}
178\newcommand{\con}{\equiv}
179\newcommand{\Gm}{\mathbb{G}_m}
180\newcommand{\pni}{\par\noindent}
181\newcommand{\iv}{^{-1}}
182\newcommand{\alp}{\alpha}
183\newcommand{\bq}{\mathbf{q}}
184\newcommand{\cpp}{{\tt C++}}
185\newcommand{\tensor}{\otimes}
186\newcommand{\bg}{{\tt BruceGenus}}
187\newcommand{\abcd}[4]{\left(
188        \begin{smallmatrix}#1&#2\\#3&#4\end{smallmatrix}\right)}
189\newcommand{\mthree}[9]{\left(
190        \begin{matrix}#1&#2&#3\\#4&#5&#6\\#7&#8&#9
191        \end{matrix}\right)}
192\newcommand{\mtwo}[4]{\left(
193        \begin{matrix}#1&#2\\#3&#4
194        \end{matrix}\right)}
195\newcommand{\vtwo}[2]{\left(
196        \begin{matrix}#1\\#2
197        \end{matrix}\right)}
198\newcommand{\smallmtwo}[4]{\left(
199        \begin{smallmatrix}#1&#2\\#3&#4
200        \end{smallmatrix}\right)}
201\newcommand{\twopii}{2\pi{}i{}}
202\newcommand{\eps}{\varepsilon}
203\newcommand{\vphi}{\varphi}
204\newcommand{\gp}{\mathfrak{p}}
205\newcommand{\W}{\mathcal{W}}
206\newcommand{\oz}{\overline{z}}
207\newcommand{\Zpstar}{\Zp^{\star}}
208\newcommand{\Zhat}{\widehat{\Z}}
209\newcommand{\Zbar}{\overline{\Z}}
210\newcommand{\Zl}{\Z_{\ell}}
211\newcommand{\Q}{\mathbb{Q}}
212\newcommand{\GQ}{G_{\Q}}
213\newcommand{\R}{\mathbb{R}}
214\newcommand{\D}{{\mathbf D}}
215\newcommand{\cC}{\mathcal{C}}
216\newcommand{\cD}{\mathcal{D}}
217\newcommand{\cP}{\mathcal{P}}
218\newcommand{\cS}{\mathcal{S}}
219\newcommand{\Sbar}{\overline{S}}
220\newcommand{\K}{{\mathbf K}}
221\newcommand{\C}{\mathbb{C}}
222\newcommand{\Cp}{{\mathbf C}_p}
223\newcommand{\Sets}{\mbox{\rm\bf Sets}}
224\newcommand{\bcC}{\boldsymbol{\mathcal{C}}}
225\renewcommand{\P}{\mathbb{P}}
226\newcommand{\Qbar}{\overline{\Q}}
227\newcommand{\kbar}{\overline{k}}
228\newcommand{\dual}{\bot}
229\newcommand{\T}{\mathbb{T}}
230\newcommand{\calT}{\mathcal{T}}
231\newcommand{\cT}{\mathcal{T}}
232\newcommand{\cbT}{\mathbf{\mathcal{T}}}
233\newcommand{\cU}{\mathcal{U}}
234\newcommand{\Z}{\mathbb{Z}}
235\newcommand{\F}{\mathbb{F}}
236\newcommand{\Fl}{\F_{\ell}}
237\newcommand{\Fell}{\Fl}
238\newcommand{\Flbar}{\overline{\F}_{\ell}}
239\newcommand{\Flnu}{\F_{\ell^{\nu}}}
240\newcommand{\Fbar}{\overline{\F}}
241\newcommand{\Fpbar}{\overline{\F}_p}
242\newcommand{\fbar}{\overline{f}}
243\newcommand{\Qp}{\Q_p}
244\newcommand{\Ql}{\Q_{\ell}}
245\newcommand{\Qell}{\Q_{\ell}}
246\newcommand{\Qlbar}{\overline{\Q}_{\ell}}
247\newcommand{\Qlnr}{\Q_{\ell}^{\text{nr}}}
248\newcommand{\Qlur}{\Q_{\ell}^{\text{ur}}}
249\newcommand{\Qltm}{\Q_{\ell}^{\text{tame}}}
250\newcommand{\Qv}{\Q_v}
251\newcommand{\Qpbar}{\Qbar_p}
252\newcommand{\Zp}{\Z_p}
253\newcommand{\Fp}{\F_p}
254\newcommand{\Fq}{\F_q}
255\newcommand{\Fqbar}{\overline{\F}_q}
256\newcommand{\Ad}{Ad}
257\newcommand{\adz}{\Ad^0}
258\renewcommand{\O}{\mathcal{O}}
259\newcommand{\A}{\mathcal{A}}
260\newcommand{\Og}{O_{\gamma}}
261\newcommand{\isom}{\cong}
262\newcommand{\ncisom}{\approx}   % noncanonical isomorphism
263\DeclareMathOperator{\ab}{ab}
264\DeclareMathOperator{\Aut}{Aut}
265\DeclareMathOperator{\Frob}{Frob}
266\DeclareMathOperator{\Fr}{Fr}
267\DeclareMathOperator{\Ver}{Ver}
268\DeclareMathOperator{\Norm}{Norm}
269\DeclareMathOperator{\norm}{norm}
270\DeclareMathOperator{\disc}{disc}
271\DeclareMathOperator{\ord}{ord}
272\DeclareMathOperator{\GL}{GL}
273\DeclareMathOperator{\PSL}{PSL}
274\DeclareMathOperator{\PGL}{PGL}
275\DeclareMathOperator{\Gal}{Gal}
276\DeclareMathOperator{\SL}{SL}
277\DeclareMathOperator{\SO}{SO}
278\newcommand{\galq}{\Gal(\Qbar/\Q)}
279\newcommand{\rhobar}{\overline{\rho}}
280\newcommand{\cM}{\mathcal{M}}
281\newcommand{\cB}{\mathcal{B}}
282\newcommand{\cE}{\mathcal{E}}
283\newcommand{\cR}{\mathcal{R}}
284\newcommand{\et}{\text{\rm\'et}}
285
286\newcommand{\sltwoz}{\SL_2(\Z)}
287\newcommand{\sltwo}{\SL_2}
288\newcommand{\gltwoz}{\GL_2(\Z)}
289\newcommand{\mtwoz}{M_2(\Z)}
290\newcommand{\gltwoq}{\GL_2(\Q)}
291\newcommand{\gltwo}{\GL_2}
292\newcommand{\gln}{\GL_n}
293\newcommand{\psltwoz}{\PSL_2(\Z)}
294\newcommand{\psltwo}{\PSL_2}
295\newcommand{\h}{\mathfrak{h}}
296\renewcommand{\a}{\mathfrak{a}}
297\newcommand{\p}{\mathfrak{p}}
298\newcommand{\m}{\mathfrak{m}}
299\newcommand{\trho}{\tilde{\rho}}
300\newcommand{\rhol}{\rho_{\ell}}
301\newcommand{\rhoss}{\rho^{\text{ss}}}
302\newcommand{\dbd}[1]{\langle #1 \rangle}
303\DeclareMathOperator{\tr}{tr}
304\DeclareMathOperator{\order}{order}
305\DeclareMathOperator{\ur}{ur}
306\DeclareMathOperator{\Tr}{Tr}
307\DeclareMathOperator{\Hom}{Hom}
308\DeclareMathOperator{\Mor}{Mor}
309\DeclareMathOperator{\HH}{H}
310\renewcommand{\H}{\HH}
311\DeclareMathOperator{\Ext}{Ext}
312\DeclareMathOperator{\Tor}{Tor}
313\newcommand{\smallzero}{\left(\begin{smallmatrix}0&0\\0&0
314                        \end{smallmatrix}\right)}
315\newcommand{\smallone}{\left(\begin{smallmatrix}1&0\\0&1
316                        \end{smallmatrix}\right)}
317
318\newcommand{\pari}{{\sc Pari}\index{Pari}}
319\newcommand{\python}{{\sc Python}\index{Python}}
320\newcommand{\magma}{{\sc Magma}\index{Magma}}
321\newcommand{\manin}{{\sc Manin}\index{Manin}}
322
323\newcommand{\zbar}{\overline{z}}
324\newcommand{\dzbar}{d\overline{z}}
325
326%%%% Theoremstyles
327\theoremstyle{plain}
328\newtheorem{theorem}{Theorem}[section]
329\newtheorem{proposition}[theorem]{Proposition}
330\newtheorem{corollary}[theorem]{Corollary}
331\newtheorem{claim}[theorem]{Claim}
332\newtheorem{lemma}[theorem]{Lemma}
333\newtheorem{conjecture}[theorem]{Conjecture}
334
335\theoremstyle{definition}
336\newtheorem{definition}[theorem]{Definition}
337\newtheorem{alg}[theorem]{Algorithm}
338\newtheorem{question}[theorem]{Question}
339\newtheorem{problem}[theorem]{Problem}
340
341%\theoremstyle{remark}
342\newtheorem{goal}[theorem]{Goal}
343\newtheorem{remark}[theorem]{Remark}
344\newtheorem{remarks}[theorem]{Remarks}
345\newtheorem{example}[theorem]{Example}
346\newtheorem{warning}[theorem]{Warning}
347\newtheorem{exercise}[theorem]{Exercise}
348
349\numberwithin{section}{chapter}
350\numberwithin{equation}{section}
351\numberwithin{figure}{section}
352\numberwithin{table}{section}
353
354\bibliographystyle{amsalpha}
355
356%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
357%% Environments
358%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
359\newenvironment{algorithm}[1]{%
360\begin{alg}[#1]\index{algorithm!#1}\sf
361}%
362{\end{alg}}
363\newenvironment{steps}%
364{\begin{itemize}\setlength{\itemsep}{0.1ex}}{\end{itemize}}
365
366\newcommand{\exref}[2]{Exercise~\ref{#1}.\ref{#2}}
367
368\newenvironment{exercises}
369{\section{Exercises}
370 \renewcommand{\labelenumi}{\thechapter.\theenumi}
371  \begin{enumerate}
372}{\end{enumerate}}
373
374\newcommand{\hd}[1]{\vspace{1ex}\noindent{\bf #1} }
375\newcommand{\nf}[1]{\underline{#1}}
376\newcommand{\cbar}{\overline{c}}
377\DeclareMathOperator{\rad}{rad}
378
379%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
380
381
382\makeindex
383
384\begin{document}
385\maketitle
386
387%\hfill
388%\begin{center}
389%Copyright (c) 2004 William Stein\\
390%\end{center}
391%The author grants permission to copy, distribute and/or modify this
392%document under the terms of the GNU Free Documentation License,
393%Version 1.2 or any later version published by the Free Software
394%Foundation; with no Invariant Sections, no Front-Cover Texts, and no
395%Back-Cover Texts.  A copy of the license is included in the Appendix.
396%\hfill
397
398\tableofcontents
399
400\chapter*{Preface}
401\addcontentsline{toc}{chapter}{\numberline{}Preface}
402
403This is a book about algorithms for computing with modular forms that
404started as a series of notes for a graduate course at Harvard
405University in 2004.  This book is meant to answer the question How
406do {\em you} compute spaces of modular forms'', by both providing a
407clear description of the specific algorithms that are used and
408explaining how to apply them using \SAGE \cite{sage}.
409
410I have spent many years trying to find good practical ways to compute
411with classical modular forms for congruence subgroups of $\SL_2(\Z)$,
412and have implemented most of these algorithms several times, first in
413C++ \cite{stein:hecke}, then in MAGMA \cite{magma}, and most recently
414as part of \SAGE.  Much of this work has involved turning formulas and
415constructions burried in obscure research papers into precise
416computational recipes, then testing these in many cases and
417eliminating subtle inaccuracies (published theorems sometimes contain
418small mistakes that appear magnified when implemented and run on a
419computer).  The goal of this book is to explain some of what I have
420learned along the way.
421%, and also describe unsolved problems whose
422%solution would move the theory forward.
423
424The author is aware of no other books on computing with modular forms,
425the closest work being Cremona's book \cite{cremona:algs}, which is
426about computing with elliptic curves, and Cohen's book
427\cite{cohen:course_ant} about algebraic number theory.  The field is
428not yet mature, and there are missing details and potential
429improvements to many of the algorithms, which you the reader might
430fill in, and which would be greatly appreciated by other
431mathematicians.
432
433This book focuses on how best to compute the spaces $M_k(N,\eps)$ of
434modular forms, where $k\geq 2$ is an integer and~$\eps$ is a Dirichlet
435character modulo~$N$.  I will spend the most effort explaining the
436algorithms that appear so far to be the best (in practice!) for such
437computations.  I will not discuss computing half-integral weight
438forms, weight one forms, forms for non-congruence subgroups or groups
439other than $\GL_2$, Hilbert and Siegel modular forms, trace formulas,
440$p$-adic modular forms, and modular abelian varieties, all of which
441are topics for another book.
442
443The reader is not assumed to have prior exposure to modular forms, but
444should be familiar with abstract algebra, basic algebraic number
445theory, Riemann surfaces, and complex analysis.
446
447
448%The text of this book is licensed under the GNU Free Documentation
449%License, Version 1.2, November 2002.  This means that you may freely
450%copy this book.  For the precise details, see the Appendix.
451
452%\noindent{}{\bf Acknowledgement:} None yet.
453% \mbox{}\vspace{2ex}
454
455% \noindent{}William Stein\\
456% {\tt http://modular.fas.harvard.edu}\\
457% {\tt [email protected]}
458
459\vspace{2ex}
460\noindent{}{\bf Acknowledgement.}
461Kevin Buzzard made many helpful remarks which were helpful in finding
462the algorithms in Chapter~\ref{ch:dirichlet}.  Noam Elkies made many
463remarks about chapters 1 and 2.  The students in the Harvard course
464made helpful remark; in particular, Abhinav Kumar made observations
465about computing widths of cusps, Thomas James Barnet-Lamb about how to
466represent Dirichlet characters, and Tseno V. Tselkov, Jennifer
467Balakrishnan and Jesse Kass made other remarks.
468
469Parts of Chapter~\ref{ch:modform} follow
470\cite[Ch.~VII]{serre:arithmetic} closely, though we adjust the
471notation, definitions, and order of presentation to be consistent with
472the rest of this book. (For example, Serre writes $2k$ for the weight
473instead of~$k$.)
474
475\vspace{2ex}
476\noindent{\bf Grant Information.}
477This material is based upon work supported by the National Science
478Foundation under Grant No. 0400386.
479
480%\section*{TODO}
481%\begin{enumerate}
482%\item Mention Denis Charles's work on analyzing algorithms,
483%computing, etc.
484%\end{enumerate}
485
486
487
488
489
490
491
492
493%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
494%
495%
496%   NEW CHAPTER
497%
498%
499%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
500
501
502
503
504
505
506
507\chapter{Modular Forms}\label{ch:modform}
508
509\edit{Write an introduction.}
510
511\section{Basic Definitions}
512Modular forms are certain types of functions on
513the {\em complex upper half plane}
514$$515 \h = \{z \in \C : \Im(z) > 0\}. 516$$
517The group
518$$519 \SL_2(\R) = 520\left\{ \mtwo{a}{b}{c}{d} : ad-bc=1,\text{ and } a,b,c,d\in\R\right\} 521$$
522acts on $\h$ via linear fractional transformations,
523as follows.
524If
525$\gamma = \abcd{a}{b}{c}{d} \in \SL_2(\R)$ and $z\in\h$,
526then (see \exref{ch:modform}{ex:upperhalfpres})
527\begin{equation}\label{eqn:lft}
528  \gamma(z) = \frac{az + b}{cz + d} \in \h.
529\end{equation}
530
531\begin{definition}[Modular Group]
532The \defn{modular group} is
533the subgroup $\SL_2(\Z)$ of $\SL_2(\R)$ of matrices
534with integer entries.  Thus $\SL_2(\Z)$ is the group of
535all matrices $\abcd{a}{b}{c}{d}$ with $a,b,c,d\in\Z$
536and $ad-bc=1$.
537\end{definition}
538For example, the
539matrices
540\begin{equation}\label{eqn:ST}
541S=\mtwo{0}{-1}{1}{\hfill 0}
542\qquad\text{and} \qquad
543T=\mtwo{1}{1}{0}{1}
544\end{equation}
545are both elements of $\SL_2(\Z)$;
546the matrix $S$ defines the function $z\mapsto -1/z$,
547and~$T$ the function $z\mapsto z+1$.
548\begin{theorem}
549The group $\SL_2(\Z)$ is generated by $S$ and $T$.
550\end{theorem}
551\begin{proof}
552  See e.g. \cite[\S{}VII.1]{serre:arithmetic}, which uses the
553  fundamental domain~$\cF$ consisting of all elements of $\h$ that
554  satisfy $|z|\geq 1$ and $\Re(z)\leq 1/2$.
555\end{proof}
556
557%begin_sage
558In \sage we compute the group $\SL_2(\Z)$ and its generators as follows:
559\begin{verbatim}
560sage: G = SL(2,Z)
561sage: print G
562The modular group SL(2,Z)
563sage: S, T = G.gens()
564sage: S
565[ 0 -1]
566[ 1  0]
567sage: T
568[1 1]
569[0 1]
570\end{verbatim}
571%end_sage
572
573\begin{definition}[Holomorphic and Meromorphic]
574  Let $R$ be an open subset of $\C$.  A function $f:R\to \C$ is
575  \defn{holomorphic} if $f$ is complex differentiable at every point
576  $z\in R$, i.e., for each $z\in R$ the limit $\lim_{h\to 0} 577 (f(z+h)-f(z))/h$ exists, where~$h$ may approach~$0$ along any path.
578  The function $f: R\to\C\cup \{\infty\}$ is \defn{meromorphic}
579    if it is holomorphic except (possibly) at a discrete set $S$ of
580    points in~$R$, and at each $\alpha\in S$ there is a positive
581    integer $n$ such that $(z-\alpha)^n f(z)$ is holomorphic at
582    $\alpha$.
583\end{definition}
584
585The function $f(z) = e^z$ is a holomorphic function on~$\h$
586(in fact on all of $\C$).  The function $1/(z-i)$ is meromorphic
587on~$\h$, and fails to be analytic at~$i$.
588
589Modular forms are holomorphic functions on $\h$ that transform in a
590particular way under a subgroup of $\SL_2(\Z)$.  Before definining
591general modular forms, we define modular forms of level $1$.
592
593\section{Modular Forms of Level 1}\label{sec:modform1}
594
595
596\begin{definition}[Weakly Modular Function]
597A \defn{weakly modular function} of weight $k\in\Z$ is a meromorphic
598function $f$ on $\h$ such that
599 for all $\gamma=\abcd{a}{b}{c}{d}\in\SL_2(\Z)$ and all $z\in\h$
600we have
601\begin{equation}\label{eqn:modfunc}
602   f(z) = (cz+d)^{-k} f(\gamma(z)).
603 \end{equation}
604\end{definition}
605The constant functions are weakly modular of weight $0$.
606There are no nonzero weakly modular functions of odd weight
607(see \exref{ch:modform}{ex:nomodformodd}), and it is by
608no means obvious that there are any weakly modular functions
609of even weight $k\geq 2$.
610The product of two weakly modular functions of weights $k_1$
611and $k_2$ is a weakly modular function of weight $k_1+k_2$
612(see \exref{ch:modform}{ex:wmfprod}),
613so once we find some nonconstant weakly modular functions, we'll
614find many of them.
615
616When $k$ is even (\ref{eqn:modfunc}) has a possibly
617more conceptual interpretation; namely
618 (\ref{eqn:modfunc}) is the same as
619$$620 f(\gamma(z))d(\gamma(z))^{k/2} = f(z)dz^{k/2}. 621$$
622Thus (\ref{eqn:modfunc}) simply says that
623the weight~$k$ differential form'' $f(z)dz^{k/2}$
624is fixed under the action of every element of
625$\SL_2(\Z)$.
626
627
628Since $\SL_2(\Z)$ is generated by the matrices $S$ and $T$
629of (\ref{eqn:ST}), to show
630that a meromorphic function~$f$ on $\h$ is a
631weakly modular function all we have to do is show
632that for all $z\in\h$ we have
633\begin{equation}\label{eqn:modfunc2}
634  f(z+1) = f(z) \qquad\text{and}\qquad f(-1/z) = z^k f(z).
635\end{equation}
636
637Suppose that $f$ is a weakly modular function of some weight~$k$.
638Then $f$ might have a \defn{Fourier expansion}, which we try to obtain
639as follows.  Let $q=q(z)=e^{2\pi i z}$, which we view as a holomorphic
640function $\C\union{\infty} \to D$, where $D$ is the closed unit disk.
641Let $D'$ be the punctured unit disk, i.e., $D$ with the origin
642removed, and note that $q:\C \to D'$.  By (\ref{eqn:modfunc2}) we have
643$f(z+1)=f(z)$, so there is a set-theoretic map $F:D' \to \C$ such that
644for every $z\in\h$ we have $F(q(z)) = f(z)$.  This function $F$ is
645thus a complex-valued function on the open unit disk.  It may or
646may not be well behaved at $0$.
647
648Suppose that $F$ is well-behaved at $0$, namely that for some
649$m\in\Z$ and all $q$ in a neighborhood of $0$ we have the equality
650$$651 F(q) = \sum_{n=m}^{\infty} a_n q^n. 652$$
653If this is the case, we say that~$f$ is
654\defn{meromorphic at $\infty$}.  If, moreover,
655$m\geq 0$, then we say
656that~$f$ is \defn{holomorphic at  $\infty$}.
657
658\begin{definition}[Modular Function]
659A \defn{modular function} of weight~$k$ is a weakly modular function
660of weight~$k$ that is meromorphic at $\infty$.
661\end{definition}
662
663\begin{definition}[Modular Form]
664  A \defn{modular form} of weight~$k$ (and level $1$) is a modular
665  function of weight~$k$ that is holomorphic on $\h$ and at $\infty$.
666\end{definition}
667
668If $f$ is a modular form, then  there are complex numbers
669$a_n$ such that for all $z\in \h$,
670\begin{equation}\label{eqn:qexp1}
671f(z) = \sum_{n=0}^{\infty} a_n q^n = \sum_{n=0}^{\infty} a_n e^{2 \pi i n z}.
672\end{equation}
673\begin{proposition}
674The above series converges for all $z\in\h$.
675\end{proposition}
676\begin{proof}n
677The function $f(q)$ is holomorphic on $D$, so
678its Taylor series converges absolutely
679in $D$.   See also \cite[\S{}VII.4]{serre:arithmetic}
680for an explicit bound on the $|a_n|$.
681\end{proof}
682We set $f(\infty)=a_0$, since $q^{2\pi i z}\to 0$ as
683$z\to i \infty$, and the value of $f$ at $\infty$
684should be the value of $F$ at $0$, which is $a_0$
685from the power series.
686
687\begin{definition}[Cusp Form]
688A \defn{cusp form}  of weight~$k$ (and level $1$) is a modular form of
689weight~$k$ such that $f(\infty)=0$, i.e., $a_0=0$.
690\end{definition}
691
692
693\section{Modular Forms of Any Level}\label{sec:modformN}
694We next define spaces of modular forms of arbitrary level.  For
695example, when $k=2$ these are closely related to elliptic curves and
696abelian varieties.
697
698A \defn{congruence subgroup} of
699$\SL_2(\Z)$ is any subgroup that contains
700$$\Gamma(N) = \ker(\SL_2(\Z)\to \SL_2(\Z/N\Z))$$
701for some $N$.  The smallest such~$N$ is the \defn{level} of $\Gamma$.
702For example,
703$$704 \Gamma_1(N) = \left\{ \mtwo{a}{b}{c}{d} \in \SL_2(\Z) : 705 \mtwo{a}{b}{c}{d}\con \mtwo{1}{*}{0}{1}\pmod{N} 706 \right\} 707$$
708and
709$$710 \Gamma_0(N) = \left\{ \mtwo{a}{b}{c}{d} \in \SL_2(\Z) : 711 \mtwo{a}{b}{c}{d}\con \mtwo{*}{*}{0}{*}\pmod{N} 712 \right\} 713$$
714are congruence subgroups of level~$N$.
715
716Let $k$ be an integer.
717Define the \defn{weight~$k$ right action} of $\GL_2(\Q)$ on
718the set of functions~$f:\h\to\C$  as follows.
719If $\gamma=\abcd{a}{b}{c}{d}\in\GL_2(\Q)$, let
720$$721 f|[\gamma]_k = \det(\gamma)^{k-1} (cz+d)^{-k} f(\gamma(z)). 722$$
723\begin{proposition}
724The action $f\mapsto f|[\gamma]_k$ is a right action
725of $\GL_2(\Z)$ on the set of all functions $f:\h\to\C$; in
726particular,
727$$728 f|[\gamma_1\gamma_2]_k = (f|[\gamma_1]_k)|[\gamma_2]_k, 729$$
730\end{proposition}
731\begin{proof}
732See \exref{ch:modform}{ex:grpact}.
733\end{proof}
734
735\begin{definition}[Weakly Modular Function]
736A \defn{weakly modular function} of weight $k$ for a
737congruence subgroup $\Gamma$ is a meromorphic
738function $f :\h \to \C$ such that
739$f|[\gamma]_k = f$ for all $\gamma \in \Gamma$.
740\end{definition}
741
742A central object in the theory of modular forms (and modular symbols)
743is the set of all {\em cusps}
744$$745 \P^1(\Q) = \Q \union \{\infty\}. 746$$
747The set of cusps for a congruence subgroup $\Gamma$ is the set
748$C(\Gamma)$ of orbits of $\P^1(\Q)$ under the action of $\Gamma$.  (We
749will often identify elements of $C(\Gamma)$ with a representative
750element from the orbit.)  For example, if $\Gamma=\SL_2(\Z)$ there is
751exactly one orbit.
752\begin{lemma}\label{lem:sl2ztrans}
753  For any cusps $\alpha, \beta\in\P^1(\Q)$ there exists
754  $\gamma\in\SL_2(\Z)$ such that $\gamma(\alpha) = \beta$.
755\end{lemma}
756\begin{proof}
757This is \exref{ch:modform}{ex:sl2ztrans}.
758\end{proof}
759
760\begin{proposition}
761For any congruence subgroup $\Gamma$, the set $C(\Gamma)$
762of cusps is finite.
763\end{proposition}
764
765In order to define modular forms for general congruence subgroups we
766need to make sense of what it means for a function to be holomorphic
767on the \defn{extended upper halfplane}
768$$769 \h^* = \h\union \P^1(\Q). 770$$
771In Section~\ref{sec:modform1} we considered a weakly modular
772function~$f$ on $\SL_2(\Z)$
773to be holomorphic at~$\infty$ if its $q$-expansion
774is of the form
775$\sum_{n=0}^{\infty} a_n q^n$.
776
777In order to make sense of holomorphicity of a weakly modular
778function $f$  for $\Gamma$ at any $\alpha\in\Q$,
779we first prove a lemma.
780\begin{lemma}
781If $f :\h\to\C$ is a weakly modular function of weight $k$
782for a congruence subgroup $\Gamma$, and $\delta \in \SL_2(\Z)$,
783then $f|[\delta]_k$ is a weakly modular function for
784$\delta^{-1}\Gamma \delta$.
785\end{lemma}
786\begin{proof}
787If $s = \delta^{-1} \gamma\delta \in \delta^{-1}\Gamma \delta$,
788then
789$$790 (f|[\delta]_k)|[s]_k = f|[\delta s]_k 791 = f|[\delta \delta^{-1}\gamma\delta]_k 792 = f|[\gamma\delta]_k = f|[\delta]_k. 793$$
794\end{proof}
795
796Fix a weight~$k$ weakly modular function~$f$ for some congruence
797subgroup~$\Gamma$, and suppose $\alpha \in \Q$.  In
798Section~\ref{sec:modform1} we constructed the $q$-expansion of $f$ by
799using that $f(z) = f(z+1)$, which held since
800$T=\mtwo{1}{1}{0}{1}\in\SL_2(\Z)$.  Unfortunately, there are
801congruence subgroups $\Gamma$ such that $T\not\in\Gamma$.  Moreover,
802even if we are interested only in modular forms for $\Gamma_1(N)$,
803where we have $T\in\Gamma_1(N)$ for all~$N$, we have to consider
804$q$-expansions at infinity for modular forms on groups $\delta^{-1} 805\Gamma_1(N)\delta$, and these need not contain~$T$.  Fortunately, $T^N 806= \mtwo{1}{N}{0}{1} \in \Gamma(N)$, so a congruence subgroup of level
807$N$ contains $T^N$.  Thus for our $f$ we have $f(z+h) = f(z)$ for some
808positive integer $h$, and again when~$f$ is meromorphic at infinity we
809obtain a Fourier expansion
810\begin{equation}\label{eqn:qser}
811   f(z) = \sum_{n=m}^{\infty} a_n q^{n/N},
812\end{equation}
813but instead it is in powers of the function $q^{1/N} = e^{2 \pi i z 814 /N}$.  We say that $f$ is holomorphic at $\infty$ if in
815(\ref{eqn:qser}) we have $m\geq 0$.
816
817What about the other cusps $\alpha\in\P^1(\Q)$? By
818Lemma~\ref{lem:sl2ztrans} there is a $\gamma\in\SL_2(\Z)$ such that
819$\gamma(\infty)=\alpha$.  We declare~$f$ to be \defn{holomorphic at
820  the cusp~$\alpha$} if the weakly modular function $f|[\gamma]_k$ is
821holomorphic at $\infty$.
822
823\begin{definition}[Modular Form]
824A {\em modular form} of integer weight $k$ for a congruence subgroup
825$\Gamma$ is a weakly modular function $f:\h^*\to \C$ that
826is holomorphic on $\h^*$.
827\end{definition}
828
829\begin{proposition}
830A weakly modular function $f$ of weight $k$ for $\Gamma$
831is holomorphic at every element of $\P^1(\Q)$ if
832 is holomorphic at a set of representative elements
833for $C(\Gamma)$.
834\end{proposition}
835\begin{proof}
836Let $c_1,\ldots, c_n \in \P^1(\Q)$ be representatives
837for the set of cusps for $\Gamma$.
838If $\alpha \in \P^1(\Q)$ then there is $\gamma\in\Gamma$
839such that $\alpha = \gamma(c_i)$ for some $i$.
840By hypothesis $f$ is holomorphic at $c_i$, so if $\delta\in\SL_2(\Z)$
841is such that $\delta(\infty) = c_i$, then $f|[\delta]_k$
842is holomorphic at $\infty$.  Since $f$ is a weakly modular
843function,
844\begin{equation}\label{eqn:prop:holoall}
845  f|[\delta]_k = (f|[\gamma]_k)|[\delta]_k = f|[\gamma\delta]_k.
846\end{equation}
847But $\gamma(\delta(\infty)) = \gamma(c_i) = \alpha$, so
848(\ref{eqn:prop:holoall}) implies that $f$ is holomorphic
849at~$\alpha$.
850\end{proof}
851
852
853\subsection{Computing Widths of Cusps}
854Let $\Gamma$ be a congruence subgroup of level~$N$.  Suppose
855$\alpha\in C(\Gamma)$ is a cusp, and choose $\gamma\in\SL_2(\Z)$ such
856that $\gamma(\infty)=\alpha$.  The minimal $h$ such that
857$\abcd{1}{h}{0}{1} \in \gamma^{-1}\Gamma\gamma$ is called the
858\defn{width} of the cusp $\alpha$ for the group $\Gamma$.  In this
859section we discuss how to compute~$h$.
860
861\begin{algorithm}{Width of Cusp}
862  Given a congruence subgroup $\Gamma$ of level $N$ and a cusp
863  $\alpha$ for $\Gamma$, this algorithm computes the width $h$ of
864  $\alpha$.  We assume that $\Gamma$ is given by congruence conditions,
865e.g., $\Gamma=\Gamma_0(N)$ or $\Gamma_1(N)$.
866\begin{steps}
867\item{}[Find $\gamma$] Use the extended Euclidean algorithm
868to find $\gamma\in\SL_2(\Z)$ such that $\gamma(\infty)=\alpha$,
869as follows.
870If $\alpha=\infty$ set $\gamma\set 1$; otherwise, write
871$\alpha=a/b$, find $c,d$ such that $ad-bc=1$, and set
872$\gamma \set \abcd{a}{b}{c}{d}$.
873\item{}[compute Conjugate Matrix] Compute the following matrix in $M_2(\Z[x])$:
874$$875 \delta(x) \set \gamma \mtwo{1}{x}{0}{1} \gamma^{-1}. 876$$
877Note that the entries of $\delta(x)$ are constant or
878linear in $x$.
879\item{}[Solve] The congruence conditions that define $\Gamma$ give
880  rise to four linear congruence conditions on $x$.  Use techniques
881  from elementary number theory (or enumeration) to find the smallest
882  simultaneous positive solution $h$ to these four equations.
883\end{steps}
884\end{algorithm}
885
886\begin{example}
887\begin{enumerate}
888\item
889Suppose $\alpha=0$ and $\Gamma=\Gamma_0(N)$ or $\Gamma_1(N)$.
890Then $\gamma=\abcd{0}{1}{1}{0}$ has the property that $\gamma(\infty)=\alpha$.
891Next, the congruence condition is
892$$\delta(x) = \gamma \mtwo{1}{x}{0}{1} \gamma^{-1} = \mtwo{1}{0}{x}{1} 893 \con \mtwo{1}{*}{0}{1}\pmod{N}. 894$$
895Thus the smallest positive solution is $h=N$, so the width of $0$
896is~$N$.
897
898\item Suppose $N=pq$ where $p,q$ are distinct primes, and let $\alpha=1/p$.
899Then $\gamma=\abcd{1}{0}{p}{1}$ sends $\infty$ to $\alpha$.
900The congruence condition for $\Gamma_0(pq)$ is
901$$902\delta(x) = \gamma \mtwo{1}{x}{0}{1} \gamma^{-1} = \mtwo{1-px}{x}{-p^2 x}{px+1} 903 \con \mtwo{*}{*}{0}{*}\pmod{pq}. 904$$
905Since $p^2x \con 0\pmod{pq}$, we see that $x=q$ is the smallest solution.
906Thus $1/p$ has width $q$, and symmetrically $1/q$ has width~$p$.
907\end{enumerate}
908\end{example}
909\begin{remark}
910For $\Gamma_0(N)$, once we enforce that the bottom
911left entry is $0\pmod{N}$, and use that the determinant is 1, the
912coprimality from the other two congruences is automatic.
913So there is one congruence to solve in the $\Gamma_0(N)$ case.
914There are 2 congruences in the $\Gamma_1(N)$ case.
915\end{remark}
916
917
918
919
920\section{Examples of Modular Forms of Level $1$}\label{sec:level_one_eisen}
921
922In this section you will finally see some examples of modular forms of
923level $1$!  We will first introduce the Eisenstein series, one of each
924weight, then define $\Delta$, which is a cusp form of weight $12$.  In
925Section~\ref{sec:struct1} we will prove the structure theorem,
926which says that using addition and multiplication of these forms, we
927can generate all modular forms of level $1$.
928
929For an even integer $k\geq 4$, the \defn{non-normalized weight~$k$
930  Eisenstein series} is
931$$932 G_k(z) = \sum_{m,n\in\Z}^{*} \frac{1}{(mz+n)^k}, 933$$
934where for a given $z$, the sum is over all $m,n\in\Z$ such that
935$mz+n\neq 0$.
936
937\begin{proposition}
938The function $G_k(z)$ is a modular form of weight~$k$, i.e.,
939 $G_k \in M_k(\SL_2(\Z))$.
940\end{proposition}
941\begin{proof}
942See \cite[\S{} VII.2.3]{serre:arithmetic} for a proof
943that $G_k(z)$ defines a holomorphic function on $\h^*$.
944To see that $G_k$ is modular, observe that
945$$946 G_k(z+1) = \sum^* \frac{1}{(m(z+1)+n)^k} = \sum^* \frac{1}{(mz+(n+m))^k} = 947\sum^* \frac{1}{(mz+n)^k}, 948$$
949and
950$$951G_k(-1/z) = \sum^* \frac{1}{(-m/z+n)^k} = \sum^* \frac{z^k}{(-m+nz)^k} 952 = z^k \sum^* \frac{1}{(mz+n)^k} = z^k G_k(z). 953$$
954\end{proof}
955
956\begin{proposition}
957$G_k(\infty) = 2\zeta(k)$,
958where $\zeta$ is the Riemann zeta function.
959\end{proposition}
960\begin{proof}
961Taking the limit as $z\to i\infty$ in the definition
962of $G_k(z)$, we obtain $\sum^*_{n\in\Z} \frac{1}{n^k}$, since
963the terms involving $z$ all go to $0$ as $z\mapsto i\infty$.
964This sum is twice $\zeta(k) = \sum_{n\geq 1} \frac{1}{n^k}$.
965\end{proof}
966
967For example,
968$$G_4(\infty) = 2\zeta(4) = \frac{1}{3^2\cdot 5} \pi^4$$
969and
970$$G_6(\infty) = 2\zeta(6) = \frac{2}{3^3\cdot 5\cdot 7} \pi^6.$$
971
972
973\subsection{The Cusp Form $\Delta$}
974Suppose $E=\C/\Lambda$ is an elliptic curve over $\C$, viewed as a quotient
975of $\C$ by a lattice $\Lambda=\Z\omega_1+\Z\omega_2$, with $\omega_1/\omega_2\in\h$.
976Then
977$$978 \wp_{\Lambda}(u) = \frac{1}{u^2} + \sum_{k=4,\text{ (k even)}}^{\infty} (k-1) 979 G_k(\omega_1/\omega_2) u^{k-2}, 980$$
981and
982$$983 (\wp')^2 = 4\wp^3 - 60 G_4(\omega_1/\omega_2) \wp - 140 G_6(\omega_1/\omega_2). 984$$
985The discriminant of the cubic $4x^3 - 60G_4(\omega_1/\omega_2) x - 986140 G_6(\omega_1/\omega_2)$ is $16\Delta(\omega_1/\omega_2)$, where
987$$988 \Delta = (60 G_4)^3 - 27(140 G_6)^2 989$$
990is a cusp form of weight $12$.
991\begin{lemma}\label{lem:delnz}
992The cusp form $\Delta$ has a $0$ only at $\infty$.
993\end{lemma}
994\begin{proof}
995Let $\omega_1, \omega_2$ be as above.
996Since~$E$ is an elliptic curve, $\Delta(\omega_1/\omega_2)\neq 0$.
997\end{proof}
998
999\subsection{Fourier Expansions of Eisenstein Series}
1000Recall from (\ref{eqn:qexp1}) that elements $f$ of $M_k(\SL_2(\Z))$ can be
1001expressed as formal power series in terms of $q(z)=e^{2\pi i z}$, and
1002that this expansion is called the Fourier expansion of $f$.
1003The following proposition gives the Fourier expansion of the
1004Eisenstein series $G_k(z)$.
1005
1006\begin{proposition}\label{prop:qexpGk}
1007For every even integer $k\geq 4$, we have
1008$$1009 G_k(z) = 2\zeta(k) + 2\cdot \frac{(2\pi i)^{k}}{(k-1)!}\cdot 1010 \sum_{n=1}^{\infty} \sigma_{k-1}(n) q^n, 1011$$
1012where $\sigma_d(n)$ is the sum of the $d$th powers of the divisors
1013of~$n$.
1014\end{proposition}
1015\begin{proof}
1016  See \cite[\S VII.4]{serre:arithmetic}, which uses a series of clever
1017  manipulations of series, starting with the identity
1018$$1019 \pi \cot(\pi z) = \frac{1}{z} + \sum_{m=1}^{\infty} 1020 \left( \frac{1}{z+m} + \frac{1}{z-m}\right). 1021$$
1022\end{proof}
1023
1024From a computational point of view, the $q$-expansion for $G_k$ from
1025Proposition~\ref{prop:qexpGk} is unsatisfactory, because it involves
1026transcendental numbers.  To understand more clearly what is going on,
1027we introduce the \defn{Bernoulli numbers} $B_n$ for $n\geq 0$
1028{\em defined} by the following equality of formal power series:
1029\begin{equation}\label{eqn:def_bernoulli}
1030  \frac{x}{e^x - 1} = \sum_{n=0}^{\infty} B_n \frac{x^n}{n!}.
1031\end{equation}
1032Expanding the power series on the left we have $$1033\frac{x}{e^x - 1} = 10341 - \frac{x}{2} + \frac{x^2}{12} - \frac{x^4}{720} + \frac{x^6}{30240} 1035- \frac{x^8}{1209600} + \cdots$$
1036As this expansion suggests, the
1037Bernoulli numbers $B_n$ with $n>1$ odd are~$0$ (see
1038\exref{ch:modform}{ex:odd_bernoulli}).
1039Expanding the series further, we obtain the following table:
1040\vspace{0.5ex}
1041
1042\noindent{}$\ds B_{0}=1,\quad B_{1}=-\frac{1}{2},\quad B_{2}=\frac{1}{6},\quad 1043B_{4}=-\frac{1}{30},\quad B_{6}=\frac{1}{42},\quad 1044B_{8}=-\frac{1}{30},\quad$\vspace{1.5ex}
1045
1046\noindent{}$\ds 1047B_{10}=\frac{5}{66},\quad 1048B_{12}=-\frac{691}{2730},\quad 1049B_{14}=\frac{7}{6},\quad 1050B_{16}=-\frac{3617}{510},\quad 1051B_{18}=\frac{43867}{798},\quad 1052$\vspace{1.5ex}
1053
1054\noindent{}
1055$\ds{}\!\!B_{20}=-\frac{174611}{330},\quad 1056B_{22}=\frac{854513}{138},\quad 1057B_{24}=-\frac{236364091}{2730},\quad 1058B_{26}=\frac{8553103}{6}. 1059%B_{28}=-\frac{23749461029}{870},\quad 1060$\vspace{1ex}
1061
1062%begin_sage
1063Use the \code{bernoulli} command to compute Bernoulli
1064numbers in \sage.
1065\begin{verbatim}
1066sage: bernoulli(12)
1067-691/2730
1068sage: bernoulli(50)
1069495057205241079648212477525/66
1070\end{verbatim}
1071%end_sage
1072
1073
1074For us, the significance of the Bernoulli numbers is their connection
1075with values of~$\zeta$ at positive even integers.
1076\begin{proposition}\label{prop:zeta_even}
1077If $k\geq 2$ is an even integer, then
1078$$1079 \zeta(k) = -\frac{(2\pi i)^{k}}{2\cdot k!}\cdot B_k. 1080$$
1081\end{proposition}
1082\begin{proof}
1083The proof in \cite[\S VII.4]{serre:arithmetic}
1084involves manipulating a power series expansion for $z \cot(z)$.
1085\end{proof}
1086
1087\begin{definition}[Normalized Eisenstein Series]
1088The \defn{normalized Eisenstein series} of even weight~$k\geq 4$ is
1089$$1090 E_k = \frac{(k-1)!}{2\cdot (2\pi i)^k}\cdot G_k 1091$$
1092\end{definition}
1093Combining Propositions~\ref{prop:qexpGk} and
1094\ref{prop:zeta_even} we see that
1095\begin{equation}\label{eqn:ekexp}
1096 E_k = -\frac{B_k}{2k} + q + \sum_{n=2}^{\infty} \sigma_{k-1}(n) q^n.
1097\end{equation}
1098It is thus now simple to explicitly write down Eisenstein series
1099(see \exref{ch:modform}{ex:expeis}).
1100
1101
1102\begin{warning} Our series $E_k$ is normalized so that the coefficient
1103  of~$q$ is~$1$, but often in the literature $E_k$ is normalized so
1104  that the constant coefficient is~$1$.  We use the normalization with
1105  the coefficient of~$q$ equal to~$1$, because then the eigenvalue of
1106  the $n$th Hecke operator (see Section~\ref{sec:hecke_one}) is the
1107  coefficient of~$q^n$.  Our normalization is also
1108  convenient when considering congruences between cusp forms and
1109  Eisenstein series.
1110\end{warning}
1111
1112\section{Structure Theorem}\label{sec:struct1}
1113If $f$ is a nonzero meromorphic function on $\h$ and $w\in\h$, let
1114$\ord_w(f)$ be the largest integer~$n$ such that $f/(w-z)^n$ is
1115holomorphic at $w$.  If $f = \sum_{n=m}^{\infty} a_n q^n$ with
1116$a_m\neq 0$, let $\ord_{\infty}(f)=m$.  We will use the following
1117theorem to give a presentation for the vector space of modular forms
1118of weight~$k$; this presentation will allow us to obtain an algorithm
1119to compute a basis for this space.
1120
1121Let $\cF$ be the subset of $\h$ of numbers $z$ with $|z|\geq 1$ and
1122$\Re(z)\leq 1/2$.  This is the standard fundamental domain for
1123$\SL_2(\Z)$.
1124
1125\begin{theorem}[Valence Formula]\label{thm:valence}
1126Suppose $f \in M_k(\SL_2(\Z))$ is nonzero.  Then
1127$$1128 \ord_{\infty}(f) + \frac{1}{2}\ord_i(f) + \frac{1}{3} \ord_{\rho}(f) 1129 + \sum_{w\in D}^* \ord_w(f) = \frac{k}{12}, 1130$$
1131where $\ds \sum^*_{w \in D}$ is the sum over elements of $\cF$
1132other than~$i$ or~$\rho$.
1133\end{theorem}
1134\begin{proof}
1135Serre proves this theorem in \cite[\S{}VII.3]{serre:arithmetic} using
1136the residue theorem from complex analysis.
1137\end{proof}
1138
1139Let $M_k=M_k(\SL_2(\Z))$ denote the complex vector space of modular
1140forms of weight~$k$ for $\SL_2(\Z)$, and let~$S_k=S_k(\SL_2(\Z))$
1141denote the subspace of weight~$k$ cusp forms for $\SL_2(\Z)$.  We have
1142an exact sequence
1143$$1144 0 \to S_k \to M_k \to \C 1145$$
1146that sends $f\in M_k$ to $f(\infty)$.  When $k\geq 4$ is even, the
1147space $M_k$ contains the Eisenstein series $G_k$ and
1148$G_k(\infty)=2\zeta(k)\neq 0$, so the map $M_k\to \C$ is surjective,
1149so the following sequence is exact:
1150$$1151 0 \to S_k \to M_k \to \C \to 0 \qquad\text{(when k\geq 4 is even)} 1152$$
1153
1154Thus when $k\geq 4$ is even $\dim(S_k)=\dim(M_k)-1$ hence
1155$$1156 M_k = S_k \oplus \C G_k. 1157$$
1158
1159\begin{proposition}\label{prop:mk_vanish}
1160For $k<0$ and $k=2$, we have $M_k=0$.
1161\end{proposition}
1162\begin{proof}
1163Suppose $f\in M_k$ is nonzero yet $k=2$ or $k<0$.  By
1164Theorem~\ref{thm:valence},
1165$$1166 \ord_{\infty}(f) + \frac{1}{2}\ord_i(f) + \frac{1}{3} \ord_{\rho}(f) 1167 + \sum_{w\in D}^* \ord_w(f) = \frac{k}{12}\leq 1/6. 1168$$
1169This is impossible because each quantity on the left-hand
1170side is nonnegative so whatever the sum is, it is too big
1171(or $0$, in which $k=0$).
1172\end{proof}
1173
1174\begin{theorem}\label{thm:delta_iso}
1175Multiplication by $\Delta$ defines an isomorphism $M_{k-12}\to S_k$.
1176\end{theorem}
1177\begin{proof}
1178(We follow \cite[\S{}VII.3.2]{serre:arithmetic} closely.)
1179We apply Theorem~\ref{thm:valence} to $G_4$ and~$G_6$.
1180If $f=G_4$, then
1181$$1182 \ord_{\infty}(f) + \frac{1}{2}\ord_i(f) + \frac{1}{3} \ord_{\rho}(f) 1183 + \sum_{w\in D}^* \ord_w(f) = \frac{4}{12} = \frac{1}{3}, 1184$$
1185with the $\ord$s all nonnegative,
1186so $\ord_{\rho}(G_4) = 1$ and $\ord_w(G_4) = 0$ for all $w\neq \rho$.
1187Likewise $\ord_{i}(G_6) = 1$ and $\ord_w(G_6) = 0$ for all $w\neq i$.
1188Thus $\Delta(i)\neq 0$, so $\Delta$ is not identically~$0$ (this
1189also follows from Lemma~\ref{lem:delnz} above).
1190Since $\Delta$ has weight~$12$ and $\ord_\infty(\Delta)\geq 1$,
1191Theorem~\ref{thm:valence} implies that~$\Delta$ has a simple
1192zero at $\infty$ and does not vanish on~$\h$.
1193Thus if $f\in S_k$ and we let $g=f/\Delta$, then $g$ is holomorphic
1194and satisfies the appropriate transformation formula, so~$g$
1195is a modular form of weight $k-12$.
1196\end{proof}
1197
1198\begin{corollary}
1199  For $k=0,4,6,8,10,14$, the vector space $M_k$ has dimension~$1$, with
1200  basis $1$, $G_4$, $G_6$, $E_8$, $E_{10}$, and $E_{14}$, respectively, and
1201  $S_k=0$.
1202\end{corollary}
1203\begin{proof}
1204  Combining Proposition~\ref{prop:mk_vanish} with
1205  Theorem~\ref{thm:delta_iso} we see that the spaces $M_k$ for $k\leq 1206 10$ can not have dimension bigger than~$1$, since then $M_{k'}\neq 1207 0$ for some $k'<0$.  Also $M_{14}$ has dimension at most $1$, since
1208  $M_2$ has dimension $0$.  Each of the indicated spaces of weight
1209  $\geq 4$ contains the indicated Eisenstein series, so has
1210  dimension~$1$, as claimed.
1211\end{proof}
1212
1213\begin{corollary}\label{cor:dim1}
1214$\dim M_k = \begin{cases} 1215 0 & \text{if }k\text{ is odd}, \\ 1216 \lfloor{} k/12 \rfloor{} & \text{if } k\con 2\pmod{12},\\ 1217 \lfloor{} k/12 \rfloor{}+1 & \text{if } k\not\con 2\pmod{12}, 1218\end{cases} 1219$
1220where $\lfloor{}x \rfloor{}$ is the biggest integer $\leq x$.
1221\end{corollary}
1222\begin{proof}
1223As we have seen above, the formula is true when $k\leq 12$.
1224By Theorem~\ref{thm:delta_iso}, the dimension increases by $1$
1225when~$k$ is replaced by $k+12$.
1226\end{proof}
1227
1228\begin{theorem}\label{thm:mk_one_basis}
1229The space $M_k$ has as basis the
1230modular forms $G_4^a G_6^b$, where $a,b$
1231are all pairs of nonnegative integers such that
1232$4a+6b=k$.
1233\end{theorem}
1234\begin{proof}
1235We first prove by induction that the modular forms
1236$G_4^a G_6^b$ generate $M_k$, the cases $k\leq 12$
1237being clear (e.g., when $k=0$ we have $a=b=0$ and basis~$1$).
1238Choose some pair of integers $a,b$ such that $4a+6b=k$
1239(it is an elementary exercise to show these exist).
1240The form $g=G_4^a G_6^b$ is not a cusp form, since
1241it is nonzero at $\infty$.  Now suppose $f\in M_k$
1242is arbitrary.  Since $M_k = S_k \oplus \C G_k$, there
1243is $\alpha\in\C$ such that $f - \alpha g \in S_k$.
1244Then by Theorem~\ref{thm:delta_iso}, there is $h \in M_{k-12}$
1245such that $f - \alpha g = \Delta h$.  By induction,
1246$h$ is a polynomial in $G_4$ and $G_6$ of the required
1247type, and so is $\Delta$, so $f$ is as well.
1248
1249Suppose there is a nontrivial linear relation between the $G_4^a 1250G_6^b$ for a given~$k$.  By multiplying the linear relation by a
1251suitable power of $G_4$ and $G_6$, we may assume that that we have
1252such a nontrivial relation with $k\con 0\pmod{12}$.  Now divide the
1253linear relation by $G_6^{k/12}$ to see that $G_4^3/G_6^2$ satisfies a
1254polynomial with coefficients in $\C$.  Hence $G_4^3/G_6^2$ is a root
1255of a polynomial, hence a constant, which is a contradiction since the
1256$q$-expansion of $G_4^3/G_6^2$ is not constant.
1257\end{proof}
1258
1259\begin{algorithm}{Basis for $M_k$}\label{alg:basis}
1260Given integers~$n$ and~$k$, this algorithm computes
1261a basis of $q$-expansions for the complex vector
1262space $M_k$ mod $q^n$.   The $q$-expansions output
1263by this algorithm have coefficients in $\Q$.
1264\begin{steps}
1265\item{}[Simple Case] If $k=0$ output the basis with
1266just $1$ in it, and terminate; otherwise if $k<4$ or~$k$
1267is odd, output the empty basis and terminate.
1268\item{}[Power Series] Compute $E_4$ and $E_6$ mod $q^n$
1269using the formula from (\ref{eqn:ekexp}) and
1270the definition (\ref{eqn:def_bernoulli}) of Bernoulli
1271numbers.\edit{Look up what the {\em real} algorithm
1272for doing this is.}
1273\item{}[Initialize] Set $b\set 0$.
1274%Precompute the powers $E_4^2, E_4^3, \ldots E_4^m$ mod $q^n$,
1275%where $m=\lfloor{} k/4\rfloor{}$, and likewise for
1276%$E_6$, but with $m=\lfloor{} k/6\rfloor{}$.
1277\item{}[Enumerate Basis] For each integer~$b$ between~$0$ and
1278$\lfloor k/6\rfloor$, compute $a=(k-6b)/4$.
1279If~$a$ is an integer, compute and output the basis
1280element $E_4^a E_6^b \mod{q^n}$.  When we compute, e.g.,
1281$E_4^a$, do the computation by finding
1282$E_4^m\pmod{q^n}$ for each $m\leq a$, and save these
1283intermediate powers, so they can be reused later, and
1284likewise for powers of $E_6$.
1285\end{steps}
1286\end{algorithm}
1287\begin{proof}
1288This is simply a translation of Theorem~\ref{thm:mk_one_basis}
1289into an algorithm, since $E_k$ is a nonzero scalar multiple
1290of $G_k$.  That the $q$-expansions have coefficients
1291in $\Q$ follows from (\ref{eqn:ekexp}).
1292\end{proof}
1293
1294\begin{example}
1295We compute a basis for $M_{24}$, which is the space with
1296smallest weight whose dimension is bigger than $1$.
1297It has as basis $E_4^6$, $E_4^3 E_6^2$, and $E_6^4$, whose explicit
1298expansions are
1299\begin{align*}
1300  E_4^6 &= \frac{1}{191102976000000} +
1301   \frac{1}{132710400000}q + \frac{203}{44236800000}q^2 + \cdots\\
1302E_4^3 E_6^2 &=
1303    \frac{1}{3511517184000} - \frac{1}{12192768000}q - \frac{377}{4064256000}q^2
1304  + \cdots \\
1305  E_6^4 &= \frac{1}{64524128256} - \frac{1}{32006016}q +
1306    \frac{241}{10668672}q^2 +\cdots
1307\end{align*}
1308\end{example}
1309
1310In Section~\ref{sec:vmthesis}, we will discuss properties
1311of the reduced row echelon form of any basis for $M_k$, which
1312have better properties than the above basis.
1313
1314
1315\section{The Victor Miller Basis}\label{sec:vmthesis}
1316\begin{lemma}[Victor Miller]\label{lem:vm}
1317The space $S_k$ has a basis $f_1,\ldots, f_{d}$ such
1318that if $a_i(f_j)$ is the $i$th coefficient of $f_j$, then
1319$a_i(f_j) = \delta_{i,j}$ for $i=1,\ldots, {d}$.  Moreover
1320the $f_j$ all lie in $\Z[[q]]$.
1321\end{lemma}
1322This is a straightforward construction involving $E_4$, $E_6$ and
1323$\Delta$.  The following proof very closely follows \cite[Ch.~X,
1324Thm.~4.4]{lang:modular}, which is in turn follows the
1325first lemma of Victor Miller's thesis.
1326\begin{proof}
1327Let $d=\dim S_k$.
1328Since $B_4 = -1/30$ and $B_6=1/42$, we note that
1329$$1330 F_4 = -\frac{8}{B_4} \cdot E_4 = 1 + 240q + 2160q^2 + 6720q^3 + 17520q^4 + \cdots 1331$$ and
1332$$1333 F_6 = -\frac{12}{B_6}\cdot E_6 = 1 - 504q - 16632q^2 - 122976q^3 - 532728q^4 1334+\cdots 1335$$
1336have $q$-expansions in $\Z[[q]]$ with leading
1337coefficient~$1$.
1338Choose integers $a,b\geq 0$ such that
1339$$1340 4a+6b\leq 14 \qquad\text{and}\qquad 4a + 6b \con k \pmod{12}, 1341$$
1342with $a=b=0$ when $k\con 0\pmod{12}$, and
1343let
1344$$1345 g_j = \Delta^j F_6^{2(d-j)+a} F_4^b,\qquad\qquad \text{for } j=1,\ldots,d. 1346$$
1347Then
1348$$1349 a_j(g_j) = 1, \qquad\text{and}\qquad a_i(g_j)=0\qquad\text{when}\qquad i<j. 1350$$
1351Hence the $g_j$ are linearly independent over $\C$, and thus form
1352a basis for $S_k$.  Since $F_4, F_6$, and $\Delta$ are all in $\Z[[q]]$,
1353so are the $g_j$.  The $f_i$ may then be constructed from the $g_j$
1354by Gauss elimination.  The coefficients of the resulting power series lie in
1355$\Z$ because each time we clear a column we use the power series
1356$g_j$ whose leading coefficient is $1$ (so no denominators are introduced).
1357\end{proof}
1358\begin{remark}
1359The basis coming from Victor Miller's lemma is canonical,
1360since it is just the reduced row echelon form of any basis.
1361Also the {\em integral} linear combinations are precisely
1362the modular forms of level $1$ with integral $q$-expansion.
1363\end{remark}
1364
1365We extend the Victor Miller basis to all $M_k$ by taking
1366a multiple of $G_k$ with constant term $1$, and subtracting
1367off the $f_i$ from the Victor Miller basis so that the
1368coefficients of $q, q^2, \ldots q^d$ of
1369the resulting expansion are $0$.  We call the extra basis
1370element $f_0$.
1371\edit{Argue: Is $G_k$ integral?}
1372
1373
1374
1375
1376\begin{example}
1377If $k=24$, then $d=2$.  Choose $a=b=0$, since $k\con 0\pmod{12}$.
1378Then
1379$$g_1 = \Delta F_6^2 = 1380q - 1032q^2 + 245196q^3 + 10965568q^4 + 60177390q^5 - \cdots 1381$$
1382and
1383$$1384g_2 = \Delta^2 = q^2 - 48q^3 + 1080q^4 - 15040q^5 + \cdots 1385$$
1386We let $f_2=g_2$ and
1387$$1388f_1 = g_1 + 1032 g_2 1389 = q + 195660q^3 + 12080128q^4 + 44656110q^5 - \cdots. 1390$$
1391\end{example}
1392\examplesession{
1393> n4 := Newforms(MF(1,4))[1][1];
1394> F4 := n4*240;
1395> F4;
13961 + 240*q + 2160*q^2 + 6720*q^3 + 17520*q^4 + 30240*q^5 +
139760480*q^6 + 82560*q^7 + O(q^8)
1398> n6 := Newforms(MF(1,6))[1][1];
1399> n6
1400> ';
1401
1402>> ';
1403     ^
1404User error: Unexpected newline in literal identifier
1405> n6;
1406-1/504 + q + 33*q^2 + 244*q^3 + 1057*q^4 + 3126*q^5 + 8052*q^6 +
140716808*q^7 + O(q^8)
1408> F6 := n6*(-504);
1409> F4;
14101 + 240*q + 2160*q^2 + 6720*q^3 + 17520*q^4 + 30240*q^5 +
141160480*q^6 + 82560*q^7 + O(q^8)
1412> F6;
14131 - 504*q - 16632*q^2 - 122976*q^3 - 532728*q^4 - 1575504*q^5 -
14144058208*q^6 - 8471232*q^7 + O(q^8)
1415> Delta := Newforms(CS(MF(1,12)))[1][1];
1416> Delta;
1417q - 24*q^2 + 252*q^3 - 1472*q^4 + 4830*q^5 - 6048*q^6 - 16744*q^7
1418+ O(q^8)
1419> Delta*F6^2;
1420q - 1032*q^2 + 245196*q^3 + 10965568*q^4 + 60177390*q^5 -
14211130921568*q^6 + 870123128*q^7 + O(q^8)
1422> Delta^2;
1423q^2 - 48*q^3 + 1080*q^4 - 15040*q^5 + 143820*q^6 - 985824*q^7 +
1424O(q^8)
1425> 1032*Delta^2 + Delta*F6^2;
1426q + 195660*q^3 + 12080128*q^4 + 44656110*q^5 - 982499328*q^6 -
1427147247240*q^7 + O(q^8)
1428> S := CS(MF(1,36));
1429> Basis(S);
1430[
1431    q + 57093088*q^4 + 37927345230*q^5 + 5681332472832*q^6 +
1432    288978305864000*q^7 + O(q^8),
1433    q^2 + 194184*q^4 + 7442432*q^5 - 197264484*q^6 +
1434    722386944*q^7 + O(q^8),
1435    q^3 - 72*q^4 + 2484*q^5 - 54528*q^6 + 852426*q^7 + O(q^8)
1436]
1437}
1438
1439\begin{example}
1440When $k=36$, the Victor Miller basis, including $f_0$, is
1441\begin{align*}
1442f_0 &= 1 + \quad\,\,\, 6218175600q^4 + 15281788354560q^5 + \cdots\\
1443 f_1 &= \,\,\,\,\,\,  q + \quad\,\, 57093088q^4 + \,\,\,\,\,\,\,\,\,\,37927345230q^5 +\cdots\\
1444 f_2 &=  \qquad q^2 +  \,\,\,\,\,\,194184q^4 + \quad\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, 7442432q^5 + \cdots \\
1445 f_3 &=  \qquad\quad\,\, q^3 -\,\,\,\,\,\,\,\,\,\, 72q^4 +\qquad\quad\,\,\,\,\,\,\,\,\,\,\,\,  2484q^5 + \cdots
1446\end{align*}
1447\end{example}
1448
1449
1450\begin{remark}
1451%(Elkies)
1452%\begin{enumerate}
1453%\item
1454If you wish to write $f \in M_k$ as a polynomial
1455  in~$E_4$ and~$E_6$, then it is wasteful to compute the Victor
1456Miller basis.
1457  Instead, use the upper triangular basis $\Delta^j F_6^{2(d-j)+a} F_4^b$,
1458  and match coefficients from $q^0$ to $q^d$.
1459
1460%\item When $4\mid{}k$, the zeroth form $f_0$ in the Miller basis is also
1461%  the theta function of an extremal self-dual even lattice
1462%  of dimension $2k$ (if one exists).  More generally, if a lattice
1463%  is with $c$ of extremality then its theta function differs from $f_0$
1464%  by a linear combination of  $f_d, f_{d-1}, ..., f_{d+1-c}$.
1465%\end{enumerate}
1466\end{remark}
1467
1468\section{Hecke Operators}\label{sec:hecke_one}
1469For any positive integer~$n$, let
1470$$1471S_n = \left\{\mtwo{a}{b}{0}{d} \in M_2(\Z) \,\,:\,\, 1472a\geq 1,\,\, ad=n, \text{ and } 0\leq b <d\right\}. 1473$$
1474Note that the set $S_n$ is in bijection with the set of sublattices of
1475$\Z^2$ of index~$n$, where $\abcd{a}{b}{c}{d}$ corresponds to
1476$L=\Z\cdot (a,b) + \Z\cdot (0,d)$, as one can see, e.g., by using
1477Hermite normal form (the analogue of reduced row
1478echelon form over~$\Z$).
1479
1480
1481\begin{definition}[Hecke Operator $T_{n,k}$]
1482The~$n$th Hecke operator $T_{n,k}$ of weight~$k$
1483is the operator on functions on $\h$ defined by
1484$$1485T_{n,k}(f) = \sum_{\gamma \in S_n} 1486f|[\gamma]_k. 1487$$
1488\end{definition}
1489\begin{remark}
1490  It would make more sense to write $T_{n,k}$ on the right, e.g.,
1491  $f|T_{n,k}$, since $T_{n,k}$ is defined using a right group action.
1492  However, if $n,m$ are integers, then $T_{n,k}$ and $T_{m,k}$ commute
1493  (by Proposition~\ref{prop:hecke_com} below), so it does not matter
1494  whether we consider the Hecke operators as acting on the right or
1495  left.
1496\end{remark}
1497
1498\begin{proposition}\label{prop:tn_presweak}
1499  If~$f$ is a weakly modular function of weight~$k$, then so is
1500  $T_{n,k}(f)$, and if~$f$ is also a modular function, then so is
1501  $T_{n,k}(f)$.
1502\end{proposition}
1503\begin{proof}
1504Suppose $\gamma\in\SL_2(\Z)$.  Since~$\gamma$
1505induces an automorphism of $\Z^2$, the set
1506$$S_n \cdot \gamma = \{ \delta \gamma : \delta\in S_n\}$$
1507is also in bijection with the sublattices
1508of $\Z^2$ of index~$n$.
1509Then for each element $\delta\gamma \in S_n\cdot \gamma$, there
1510is $\sigma\in\SL_2(\Z)$ such that $\sigma\delta\gamma\in S_n$ (the
1511element~$\sigma$
1512transforms $\delta\gamma$ to Hermite normal form),
1513and the set of elements $\sigma\delta\gamma$ is equal to $S_n$.
1514Thus
1515$$1516 T_{n,k}(f) = \sum_{\sigma\delta\gamma\in S_n} f|[\sigma\delta\gamma]_k 1517 = \sum_{\delta\in S_n} f|[\delta\gamma]_k 1518 = T_{n,k}(f)|[\gamma]_k. 1519$$
1520
1521Since $f$ is holomorphic on $\h$,
1522each $f|[\gamma]_k$ is holomorphic on $\h$.
1523A finite sum of holomorphic functions is holomorphic,
1524so $T_{n,k}(f)$ is holomorphic.
1525
1526\end{proof}
1527
1528We will frequently drop $k$ from the notation in $T_{n,k}$, since
1529the weight $k$ is implicit in the modular function to which
1530we apply the Hecke operator.  Thus we henceforth make the
1531convention that if we write $T_{n}(f)$ and~$f$ is modular,
1532then we mean $T_{n,k}(f)$, where~$k$ is the weight of~$f$.
1533
1534\begin{proposition}\label{prop:hecke_com}
1535On weight $k$ modular functions we have
1536\begin{equation}\label{eqn:hecke_mul}
1537  T_{mn} = T_{n} T_{m} \qquad\qquad\qquad\qquad\quad
1538 \text{if }(n,m)=1,
1539\end{equation}
1540and
1541\begin{equation}\label{eqn:hecke_recur}
1542  T_{p^n} = T_{p^{n-1}} T_p\, -\, p^{k-1} T_{p^{n-2}}, \qquad\!\!
1543\text{if $p$ is prime}.
1544\end{equation}
1545\end{proposition}
1546\begin{proof}
1547  Let $L$ be a lattice of index $mn$.  The quotient $\Z^2/L$ is an
1548  abelian group of order $mn$, and $(m,n)=1$, so $\Z^2/L$ decomposes
1549  uniquely as a direct sum of a subgroup order~$m$ with a subgroup of
1550  order~$n$.  Thus there exists a unique lattice $L'$ such that
1551  $L\subset L'\subset \Z^2$, and $L'$ has index $m$ in $\Z^2$.  The
1552  lattice $L'$ corresponds to an element of $S_m$, and the index~$n$
1553  subgroup $L\subset L'$ corresponds to multiplying that element on
1554  the right by some uniquely determined element of $S_n$.  We thus
1555  have $$\SL_2(\Z) \cdot S_{m} \cdot S_n = \SL_2(\Z) \cdot S_{mn},$$
1556  i.e., the set products of elements in $S_m$ with elements of $S_n$
1557  equal the elements of $S_{mn}$, up to $\SL_2(\Z)$-equivalence.  It
1558  then follows from the definitions that for any $f$, we have
1559  $T_{mn}(f) = T_{n}(T_m(f))$.
1560
1561  We will show that $T_{p^n} + p^{k-1} T_{p^{n-2}} = T_p T_{p^{n-1}}$.
1562  Suppose~$f$ is a weight~$k$ weakly modular function.
1563Using that $f|[p]_k = (p^2)^{k-1}p^{-k} f = p^{k-2} f$, we have
1564$$1565 \sum_{x\in S_{p^n}} f|[x]_k\,\, +\,\, p^{k-1}\!\!\! \sum_{x\in 1566 S_{p^{n-2}}} f|[x]_k 1567 = \sum_{x\in S_{p^n}} f|[x]_k \,\,\,+\, p\!\!\!\! \sum_{x\in pS_{p^{n-2}}} f|[x]_k. 1568$$
1569  Also $$T_p T_{p^{n-1}}(f) = \sum_{y\in S_p} \sum_{x\in S_{p^{n-1}}} 1570 f|[x]_k|[y]_k = \sum_{x \in S_{p^{n-1}}\cdot S_p} f|[x]_k.$$
1571  Thus it suffices to show that $S_{p^n}$ union~$p$ copies of $p 1572 S_{p^{n-2}}$ is equal to $S_{p^{n-1}}\cdot S_p$, where we consider
1573  elements up to left $\SL_2(\Z)$-equivalence (i.e., the left
1574action of $\SL_2(\Z)$).
1575
1576  Suppose~$L$ is a sublattice of $\Z^2$ of index $p^n$, so~$L$
1577  corresponds to an element of $S_{p^n}$.  First suppose~$L$ is not
1578  contained in $p\Z^2$.  Then the image of~$L$ in $\Z^2/p\Z^2 = 1579 (\Z/p\Z)^2$ is of order~$p$, so if $L'=p\Z^2 + L$, then
1580  $[\Z^2:L']=p$ and $[L:L']=p^{n-1}$, and $L'$ is the only lattice
1581  with this property.  Second suppose that $L\subset p\Z^2$ if of
1582  index $p^n$, and that $x\in S_{p^n}$ corresponds to $L$.  Then every
1583  one of the $p+1$ lattices $L'\subset \Z^2$ of index~$p$
1584  contains~$L$. Thus there are $p+1$ chains $L\subset L'\subset \Z^2$
1585with $[\Z^2:L']=p$.
1586
1587The chains $L\subset L'\subset\Z^2$ with $[\Z^2:L']=p$ and
1588$[\Z^2:L]=p^{n-1}$ are in bijection with the elements of
1589$S_{p^{n-1}}\cdot S_p$.  On the other hand the union of $S_{p^n}$ with
1590$p$ copies of $p S_{p^{n-2}}$ corresponds to the lattices~$L$ of index
1591$p^{n}$, but with those that contain $p\Z^2$ counted $p+1$ times. The
1592structure of the set of chains $L\subset L'\subset\Z^2$ that we
1593derived in the previous paragraph gives the result.
1594\end{proof}
1595
1596\begin{corollary}
1597The Hecke operator $T_{p^n}$, for prime~$p$, is a polynomial in $T_p$.
1598If $n,m$ are any integers then $T_n T_m = T_m T_n$.
1599\end{corollary}
1600\begin{proof}
1601  The first statement is clear from (\ref{eqn:hecke_recur}), and this
1602  gives commutativity when $m$ and $n$ are both powers of $p$.  Combining
1603  this with (\ref{eqn:hecke_mul}) gives the second statement in general.
1604\end{proof}
1605
1606% \begin{remark}
1607% Emmanuel Kowalski made the following remark on the number theory lists
1608% in June 2004 when asked about the polynomials $f_n(X)$ such
1609% that $T_{p^n} = f_n(T_p)$.
1610% \begin{quote}
1611% If you normalize the Hecke operators by considering
1612% $$1613% S_{n,k} = n^{-(k-1)/2} T_{n,k} 1614%$$
1615% then the recursion on the polynomials $P_r(X)$ such that
1616% $S_{p^r,k}=P_r(S_{p,k})$ becomes
1617% $$1618% X P_r = P_{r+1} + P_{r-1}, 1619%$$
1620% which is the recursion satisfied by the Chebychev polynomials $U_r$ such
1621% that
1622% $$1623% U_r(2 \cos t) = \frac{\sin((r+1) t)}{ \sin(t)}. 1624%$$
1625% Alternatively, those give the characters of the symmetric powers of the
1626% standard representation of $\SL_2(\R)$, evaluated on a rotation matrix
1627% $$1628% \mtwo{\cos(t)}{-\sin(t)}{\sin(t)}{\hfill \cos(t)}. 1629%$$
1630% For references, see for instance \cite[p.~97]{iwaniec:topics}
1631% or \cite[p.~78, p.~81]{serre:asymptotique}, and there are certainly many others.
1632% \end{quote}
1633% \end{remark}
1634
1635\begin{proposition}\label{prop:qexpTn}
1636Suppose $f = \sum_{n\in\Z} a_n q^n$ is a modular function
1637of weight~$k$.
1638Then
1639$$1640 T_{n}(f) 1641 = \sum_{m\in\Z} 1642\left(\sum_{1\leq d\,\mid\, (n,m)} d^{k-1} a_{mn/d^2}\right) q^m. 1643$$
1644In particular, if $n=p$ is prime, then
1645$$1646 T_p(f) = \sum_{m\in \Z} \left(a_{mp} + p^{k-1} a_{m/p}\right) q^m, 1647$$
1648where $a_{m/p}=0$ if $m/p\not\in\Z$.
1649\end{proposition}
1650The proposition is not that difficult to prove (or at least the proof
1651is easy to follow), and is proved in \cite[\S
1652VII.5.3]{serre:arithmetic} by writing out $T_n(f)$ explicitly and
1653using that $\sum_{0\leq b<d} e^{2\pi i bm/d}$ is $d$ if $d\mid m$
1654and~$0$ otherwise.  A corollary of Proposition~\ref{prop:qexpTn} is
1655that $T_n$ preserves $M_k$ and $S_k$.
1656\begin{corollary}\label{cor:tpres}
1657 The Hecke operators preserve $M_k$ and $S_k$.
1658\end{corollary}
1659\begin{remark} We knew this already---for $M_k$ it's
1660  Proposition~\ref{prop:tn_presweak}, and for $S_k$ it's easy to show
1661  directly that if $f(i\infty)=0$ then $T_n f$ also vanishes at
1662  $i\infty$.
1663\end{remark}
1664
1665\begin{example}
1666Recall that
1667$$1668E_4 = \frac{1}{240} + q + 9q^2 + 28q^3 + 73q^4 + 126q^5 + 252q^6 + 344q^7 1669+\cdots. 1670$$
1671Using the formula of Proposition~\ref{prop:qexpTn}, we see
1672that
1673$$1674T_2(E_4) = (1/240 + 2^3\cdot (1/240)) + 9q + (73 + 2^3\cdot 1) q^2 + \cdots \\ 1675 = 9 E_4. 1676$$
1677Since $M_k$ has dimension $1$, and we have proved that $T_2$
1678preserves $M_k$, we know that $T_2$ acts as a scalar.  Thus
1679we know just from the constant coefficient of $T_2(E_4)$ that
1680$T_2(E_4) = 9 E_4$.
1681More generally, $T_p(E_4) = (1+p^3)E_4$.
1682In fact for any $k$ one has that
1683$$1684 T_n(E_k) = \sigma_{k-1}(n) E_k, 1685$$
1686for any integer $n\geq 1$ and even weight $k\geq 4$.
1687\end{example}
1688
1689\begin{example}
1690  By Corollary~\ref{cor:tpres}, the Hecke operators $T_n$ also
1691  preserve the subspace $S_k$ of $M_k$.  Since $S_{12}$ has dimension
1692  $1$ (spanned by $\Delta$), we see that~$\Delta$ is an
1693  eigenvector for every $T_n$.  Since the coefficient of $q$ in the
1694  $q$-expansion of $\Delta$ is~$1$, the eigenvalue of $T_n$ on
1695  $\Delta$ is the $n$th coefficient of $\Delta$.  Moreover the
1696  function $\tau(n)$ that gives the $n$th coefficient of $\Delta$ is a
1697  multiplicative function.  Likewise, one can show that the series
1698  $E_k$ are eigenvectors for all $T_n$, and because in this book we
1699  normalize $E_k$ so that the coefficient of $q$ is~$1$, the
1700  eigenvalue of $T_n$ on $E_k$ is the coefficient $\sigma_{k-1}(n)$
1701  of~$q^n$.
1702\end{example}
1703
1704\section{Computing Hecke Operators}
1705In this section we describe a simple algorithm for computing matrices
1706of Hecke operators on $M_k$.
1707
1708\begin{algorithm}{Hecke Operator}
1709  This algorithm computes a matrix for the Hecke operator $T_n$ on the
1710 Victor Miller basis for $M_k$.
1711\begin{steps}
1712\item{}[Compute dimension] Set $d\set \dim(S_k)$, which we
1713  compute using Corollary~\ref{cor:dim1}.
1714\item{}[Compute basis] Using the algorithm
1715implicit in Lemma~\ref{lem:vm}, compute a
1716  basis $f_0,\ldots, f_d$ for $M_k$ modulo $q^{dn+1}$.
1717\item{}[Compute Hecke operator] Using the formula from
1718  Proposition~\ref{prop:qexpTn}, compute $T_n(f_i) \pmod{q^{d+1}}$ for
1719  each $i$.
1720\item{}[Write in terms of basis]\label{usevm} The elements
1721$T_n(f_i) \pmod{q^{d+1}}$
1722  uniquely determine linear combinations of $f_0,f_1,\ldots, f_d 1723 \pmod{q^d}$.  These linear combinations are trivial to find
1724once we have computed $T_n(f_i) \pmod{q^{d+1}}$,
1725since the basis of~$f_i$ are in reduced row echelon form,
1726so the combinations are just the first few coefficients
1727of the power series $T_n(f_i)$.
1728\item{}[Write down matrix] The matrix of $T_n$ acting from the right is
1729  the matrix whose columsn are the linear combinations found in the
1730  previous step, i.e., whose columns are the coefficients of $T_n(f_i)$.
1731\end{steps}
1732\end{algorithm}
1733\begin{proof}
1734  First note that we compute a modular form~$f$ modulo $q^{dn+1}$ in
1735  order to compute $T_n(f)$ modulo $q^{d+1}$.  This follows from
1736  Proposition~\ref{prop:qexpTn}, since in the formula the $d$th
1737  coefficient of $T_n(f)$ involves only $a_{dn}$, and smaller-indexed
1738  coefficients of~$f$.  The uniqueness assertion of Step~\ref{usevm}
1739  follows from Lemma~\ref{lem:vm} above.
1740\end{proof}
1741
1742
1743
1744\begin{example}
1745This is the Hecke operator $T_2$ on $M_{36}$ is:
1746$$1747\left( 1748\begin{matrix} 1749\hfill 34359738369&\hfill0&\hfill6218175600&\hfill9026867482214400\\ 17500&\hfill0&\hfill34416831456&\hfill5681332472832\\ 17510&\hfill1&\hfill194184&\hfill-197264484\\ 17520&\hfill0&\hfill-72&\hfill-54528\\ 1753\end{matrix}\right) 1754$$
1755It has characteristic polynomial
1756$$1757(x - 34359738369) \cdot 1758(x^3 - 139656x^2 - 59208339456x - 1467625047588864), 1759$$
1760where the cubic factor is irreducible.
1761\end{example}
1762
1763\begin{conjecture}[Maeda]
1764The characteristic polynomial of $T_2$ on $S_k$ is irreducible for any~$k$.
1765\end{conjecture}
1766
1767Kevin Buzzard even observed that in many specific cases the Galois
1768group of the characteristic polynomial of $T_2$ is the full symmetric group
1769(see \cite{buzzard:t2}).  See also \cite{farmer-james:maeda} for more
1770evidence for Maeda's conjecture.
1771\edit{Isn't there something from a recent Berkeley grad student.}
1772
1773% \section{Computing Characteristic Polynomials}
1774% \begin{algorithm}{Characteristic Polynomial}
1775% This algorithm computes the characteristic
1776% polynomial of $T_p$ acting on $M_k(\SL_2(\Z))$.
1777% \end{algorithm}
1778% \section{Some Open Problems}
1779% \subsection{Maeda's Conjecture}
1780% \begin{conjecture}
1781% The characteristic polynomial of $T_2$ is irreducible.
1782% \end{conjecture}
1783
1784
1785\subsection{A Conjecture about Complexity}
1786
1787
1788Let\edit{Lead in about coefficients of elliptic curve
1789modform, etc.???}
1790\begin{align*}
1791\Delta &= \sum_{n=1}^{\infty} \tau(n) q^n \\
1792  & = q - 24q^2 + 252q^3 - 1472q^4 + 4830q^5 - 6048q^6 - 16744q^7\\
1793  &\qquad  + 84480q^8 - 113643q^9 - 115920q^{10} + 534612q^{11} - \\
1794  &\qquad  370944q^{12} - 577738q^{13} + 401856q^{14} + 1217160q^{15} + \\
1795  &\qquad  987136q^{16} - 6905934q^{17} + 2727432q^{18} + 10661420q^{19} +
1796  \cdots
1797\end{align*}
1798be the $\Delta$-function.
1799\begin{conjecture}[Edixhoven]\label{conj:edixhoven}
1800There is an algorithm to compute $\tau(p)$, for prime $p$, that
1801is polynomial-time in $\log(p)$.
1802More generally, suppose $f=\sum a_n q^n$ is an eigenform in some space
1803$M_k(N,\eps)$, where $k\geq 2$.  Then there is an algorithm
1804to compute $a_p$, for $p$ prime, in time polynomial in $\log(p)$.
1805\end{conjecture}
1806
1807
1808Bas Edixhoven, Jean-Marc Couveignes and Robin de Jong have mostly
1809proved that $\tau(p)$ can be computed in polynomial time; their
1810approach involves sophisticated techniques from arithmetic geometry
1811(e.g., \'etale cohomology, motives, Arakelov theory). This is work in
1812progress and has not been written up completely yet.  The ideas
1813Edixhoven uses are inspired by the ones introduced by Schoof, Elkies
1814and Atkin for quickly counting points on elliptic curves over finite
1815fields (see \cite{MR1413578}).
1816
1817More precisely, Edixhoven describes his strategy as follows:
1818\begin{enumerate}
1819\item We compute the mod $\ell$ Galois representations associated to
1820  $\Delta$.  In particular, we produce a polynomial $f$ such that
1821  $\Q[x]/(f)$ is the corresponding field. This is then used to obtain
1822  $\tau(p) \pmod{\ell}$ and do a Schoof like algorithm for computing
1823  $\tau(p)$.
1824
1825\item We compute the field of definition of suitable points of
1826  order~$\ell$ on $J_1(\ell)$ to do part 1.
1827
1828\item The method is to approximate the polynomial $f$ in some sense
1829  (e.g., over the complex numbers, or modulo many small primes $r$),
1830  and use an estimate from Arakelov theory to determine a
1831  precision that will suffice.
1832\end{enumerate}
1833
1834The rest of this book is about methods for computing subspaces of
1835$M_k(\Gamma_1(N))$ for general $N$ and $k$.  These general methods are
1836much more complicated than the methods presented in this chapter,
1837since there are many more forms of small weight, and it can be
1838difficult to obtain them.  These forms of higher level have subtle and
1839deep connections with arithmetic geometric objects such as elliptic
1840curves, abelian varieties, and motives.
1841
1842\begin{exercises}
1843\item\label{ex:upperhalfpres}
1844Suppose $\gamma = \abcd{a}{b}{c}{d}$ is a matrix with real entries
1845and positive determinant.  Prove that if $z\in\C$ is a complex
1846number with positive imaginary part, then the imaginary
1847part of $\gamma(z) = (az+b)/(cz+d)$ is also positive.
1848
1849\item\label{ex:meromorphic}
1850\begin{enumerate}
1851\item Prove that a polynomial is an analytic function on $\C$.
1852\item Prove that a rational function (quotient of two polynomials)
1853is a meromorphic function on $\C$.
1854\end{enumerate}
1855
1856\item \label{ex:wmfprod}
1857Suppose $f$ and $g$ are weakly modular functions with $f\neq 0$.
1858\begin{enumerate}
1859\item Prove that the product $fg$ is a weakly modular function.
1860\item Prove that $1/f$ is a weakly modular function.
1861\item If $f$ and $g$ are modular functions, show that $fg$
1862is a modular function.
1863\item If $f$ and $g$ are modular forms, show that $fg$
1864is a modular form.
1865\end{enumerate}
1866
1867\item \label{ex:nomodformodd}
1868Suppose $f$ is a weakly modular function of odd weight $k$.
1869Show that $f=0$.
1870
1871\item \label{ex:conggamma1}
1872\begin{enumerate}
1873\item Prove that $\Gamma_1(N)$ is a group.
1874\item Prove that $\Gamma_1(N)$ has finite index in $\SL_2(\Z)$
1875(Hint: it contains the kernel of the homomorphism
1876$\SL_2(\Z) \to \SL_2(\Z/N\Z)$.)
1877\end{enumerate}
1878
1879\item \label{ex:grpact}
1880Let $k$ be an integer, and for any function
1881$f:\h^*\to \C$ and $\gamma=\abcd{a}{b}{c}{d}\in\GL_2(\Q)$,
1882set $f|[\gamma]_k(z) = (cz+d)^{-k} f(\gamma(z))$.
1883Prove that if $\gamma_1, \gamma_2 \in \SL_2(\Z)$,
1884then for all $z\in \h^*$ we have
1885$$1886 f|[\gamma_1 \gamma_2]_k(z) = ((f|[\gamma_1]_k)|[\gamma_2]_k)(z). 1887$$
1888
1889\item \label{ex:sl2ztrans}
1890Prove that for any $\alpha, \beta\in\P^1(\Q)$, there exists
1891  $\gamma\in\SL_2(\Z)$ such that $\gamma(\alpha) = \beta$.
1892
1893\item \label{ex:expeis} By hand use (\ref{eqn:ekexp}) write down the
1894  coefficients of $1$, $q$, $q^2$, and $q^3$ of the Eisenstein series
1895  $E_8$.
1896
1897\item \label{ex:vm} Explicitly compute the Victor Miller basis for
1898$M_{28}(\SL_2(\Z))$.
1899
1900\end{exercises}
1901
1902% \subsection{The Gouvea-Mazur Conjecture}
1903% \edit{False in general, but .... (copy from last year).}
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1914%
1915%
1916%   NEW CHAPTER
1917%
1918%
1919%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932\chapter{Dirichlet Characters}\label{ch:dirichlet}
1933
1934Fix an integral domain~$R$ and a root~$\zeta$ of unity in~$R$.
1935\begin{definition}[Dirichlet Character]
1936  A \defn{Dirichlet character} modulo~$N$ over~$R$ with given choice
1937  of $\zeta\in R$ is a map $\eps:\Z\to R$ such that there
1938is a homomorphism $f:(\Z/N\Z)^* \to \langle \zeta \rangle$ for which
1939$$1940 \eps(a) = \begin{cases} 1941 0 &\text{if }(a,N)>1,\\ 1942 f\,(a\!\!\!\!\mod{N}) &\text{if }(a,N)=1. 1943 \end{cases} 1944$$
1945\end{definition}
1946We denote the group of such Dirichlet characters by $D(N,R,\zeta)$, or
1947by just $D(N,R)$, when the choice of $\zeta$ is clear.  It follows
1948immediately from the definition that elements of
1949$D(N,R)$ are in bijection with  homomorphisms $(\Z/N\Z)^* \to 1950\langle \zeta \rangle$.
1951
1952In this chapter we develop a systematic theory for computing
1953with Dirichlet characters.   These will be extremely important
1954everywhere in the rest of this book, when we compute with
1955spaces $M_k(\Gamma_1(N))$ of modular forms for
1956$$1957 \Gamma_1(N) = \left\{ \mtwo{a}{b}{c}{d} \in \SL_2(\Z) : 1958 \mtwo{a}{b}{c}{d}\con \mtwo{1}{*}{0}{1}\pmod{N} 1959 \right\}. 1960$$
1961For example, Eisenstein series in $M_k(\Gamma_1(N))$ are associated
1962to pairs of Dirichlet characters.  Also the complex vector space
1963$M_k(\Gamma_1(N))$ with its structure as a module over the Hecke algebra
1964decomposes as a direct sum
1965$$1966 M_k(\Gamma_1(N)) = \bigoplus_{\eps\in D(N,\C)} M_k(\Gamma_1(N))(\eps). 1967$$
1968Each space $M_k(\Gamma_1(N))(\eps)$ is frequently much easier
1969to compute with than the full $M_k(\Gamma_1(N))$.
1970For example, $M_2(\Gamma_1(100))$ has dimension $370$, whereas
1971$M_2(\Gamma_1(100))(1)$ has dimension only $24$, and
1972$M_2(\Gamma_1(389))$ has dimension $6499$, whereas
1973$M_2(\Gamma_1(389))(1)$ has dimension only $33$.
1974
1975\begin{remark}
1976If
1977$$1978 \Gamma_0(N) = \left\{ \mtwo{a}{b}{c}{d} \in \SL_2(\Z) : 1979 \mtwo{a}{b}{c}{d}\con \mtwo{*}{*}{0}{*}\pmod{N} 1980 \right\}, 1981$$
1982then $M_k(\Gamma_1(N))(1) = M_k(\Gamma_0(N))$.
1983\end{remark}
1984
1985
1986\section{Decomposing Modular Forms Using Dirichlet Characters}
1987The group $(\Z/N\Z)^*$ acts on $M_k(\Gamma_1(N))$ through the
1988\defn{diamond-bracket operators}~$\langle d \rangle$.
1989For $d\in(\Z/N\Z)^*$, define
1990$$1991 f|\dbd{d} = f|[\abcd{a}{b}{c}{d'}]_k, 1992$$
1993where $\abcd{a}{b}{c}{d'} \in \SL_2(\Z)$ is congruent to
1994$\abcd{d^{-1}}{0}{0}{d}\pmod{N}$.  Note that the map
1995$\SL_2(\Z)\to \SL_2(\Z/N\Z)$ is surjective (see \exref{ch:eisen}{ex:surjred}),
1996so it makes sense to consider the matrix $\abcd{a}{b}{c}{d'}$.
1997To prove that $\dbd{d}$ preserves $M_k(\Gamma_1(N))$,
1998we prove the more general fact that $\Gamma_1(N)$ is normal
1999in
2000$$\Gamma_0(N) = \left\{ \mtwo{a}{b}{c}{d} \in \SL_2(\Z) : 2001 \mtwo{a}{b}{c}{d}\con \mtwo{*}{*}{0}{*}\pmod{N} 2002 \right\}. 2003$$
2004This will imply that $\dbd{d}$ preserves $M_k(\Gamma_1(N))$
2005since $\abcd{a}{b}{c}{d'} \in \Gamma_0(N)$.
2006
2007\begin{lemma}
2008The group $\Gamma_1(N)$ is a normal subgroup of $\Gamma_0(N)$,
2009and the quotient $\Gamma_0(N)/\Gamma_1(N)$ is
2010isomorphic to $(\Z/N\Z)^*$.
2011\end{lemma}
2012\begin{proof}
2013Consider the surjective homomorphism $r:\SL_2(\Z)\to \SL_2(\Z/N\Z)$.
2014Then $\Gamma_1(N)$ is the exact inverse image of the subgroup $H$ of
2015matrices of the form $\abcd{1}{*}{0}{1}$ and $\Gamma_0(N)$
2016is the inverse image of the subroup $T$ of upper triangular matrices.
2017It thus suffices to observe that $H$ is normal in $T$, which is clear.
2018Finally, the quotient $T/H$ is isomorphic to the group of diagonal
2019matrices in $\SL_2(\Z/N\Z)^*$, which is isomorphic to $(\Z/N\Z)^*$.
2020\end{proof}
2021
2022The diamond bracket action is simply the action of
2023$\Gamma_0(N)/\Gamma_1(N)\isom(\Z/N\Z)^*$ on $M_k(\Gamma_1(N))$.
2024Since $M_k(\Gamma_1(N))$ is a vector space over $\C$,
2025the $\dbd{d}$ action breaks $M_k(\Gamma_1(N))$ up as a direct
2026sum of factors corresponding to the Dirichlet characters $D(N,C)$ of
2027modulus~$N$.
2028\begin{proposition}
2029We have
2030$$2031 M_k(\Gamma_1(N)) = \bigoplus_{\eps \in D(N,\C)} M_k(N,\eps), 2032$$
2033where
2034$$2035 M_k(N,\eps) = \bigl\{ f \in \M_k(\Gamma_1(N)) : f|\dbd{d} = \eps(d) f 2036 \text{ all }d \in (\Z/N\Z)^*\bigr\}. 2037$$
2038\end{proposition}
2039\begin{proof}
2040  The linear transformations $\dbd{d}$, for the $d\in(\Z/N\Z)^*$, all
2041  commute, since $\dbd{d}$ acts through the abelian group
2042  $\Gamma_0(N)/\Gamma_1(N)$.  Also, if $e$ is the exponent of
2043  $(\Z/N\Z)^*$, then $\dbd{d}^e = \dbd{d^e} = \dbd{1} = 1$, so the
2044  matrix of $\dbd{d}$ is diagonalizable.  It is a standard fact from
2045  linear algebra that any commuting family of diagonalizable linear
2046  transformations is simultaneously diagonalizable (see
2047  \exref{ch:eisen}{ex:diag}), so there is a basis $f_1,\ldots, f_n$
2048  for $M_k(\Gamma_1(N))$ so that all $\dbd{d}$ act by diagonal
2049  matrices.  The eigenvalues of the action of $(\Z/N\Z)^*$ on a fixed
2050  $f_i$ defines a Dirichlet character, i.e., each $f_i$ has
2051  the property that $f_i |\dbd{d} = \eps_i(d)$, for all
2052  $d\in(\Z/N\Z)^*$ and some Dirichlet character $\eps_i$.  The $f_i$
2053  for a given $\eps$ then span $M_k(N,\eps)$, and taken together the
2054  $M_k(N,\eps)$ must span $M_k(\Gamma_1(N))$.
2055\end{proof}
2056
2057\begin{definition}[Character of Modular Form]
2058If $f\in M_k(N,\eps)$, we say that~$f$ \defn{has character} $\eps$.
2059\end{definition}
2060\begin{remark}
2061People also often write that $f$ has nebentypus character'' $\eps$.
2062I rarely hear anyone actually {\em say} nebentypus, and it's somewhat
2063redundant, so I will simply omit it in this book.
2064\end{remark}
2065
2066% There is an inner product $\langle \, , \, \rangle$ on $M_k(Gamma_1(N))$
2067% called the \defn{Petersson inner product}.  It is nondegenerate and
2068% if $T_n$ is a Hecke operator, then $2069The spaces$M_k(N,\eps)$are a direct sum of subspaces 2070$S_k(N,\eps)$and$E_k(N,\eps)$, where$S_k(N,\eps)$is the 2071subspace of cusp forms, i.e., forms that vanish at {\em all} 2072cusps (elements of$\Q \union \{\infty\}$), and$E_k(N,\eps)$2073is the subspace of Eisenstein series, which is the unique 2074subspace of$M_k(N,\eps)$that is invariant under all Hecke 2075operators and is such that 2076$M_k(N,\eps) = S_k(N,\eps) \oplus E_k(N,\eps)$. 2077The space$E_k(N,\eps)$can also be defined as the space 2078spanned by all Eisenstein series of weight$k$and level~$N$, 2079as defined below. It can also be defined using the Petersson 2080inner product. 2081 2082\begin{remark} 2083The notation$M_k(N)$will not be used anywhere in this book 2084(except in this sentence). 2085\end{remark} 2086 2087%Remark: Edixhoven once told me that if you 2088%could compute$\tau(n)$for {\em all}$n$, not just prime~$n$, in 2089%polynomial time, then you could factor integers in polynomial time. 2090 2091 2092\section{Representation and Arithmetic} 2093\begin{lemma}\label{lem:dual} 2094 The groups$(\Z/N\Z)^*$and$\Hom((\Z/N\Z)^*,\C^*)\isom D(N,\C^*)$2095 are non-canonically isomorphic. 2096\end{lemma} 2097\begin{proof} 2098 This follows from the more general fact that for any abelian 2099 group~$G$, we have that$G\ncisom \Hom(G,\C^*)$. To prove that this 2100 latter non-canonical isomorphism exists, first reduce to the case 2101 when~$G$is cyclic of order~$n$, in which case the statement follows 2102 because$\zeta_n\in\C^*$, so$\Hom(G,\C^*)\isom \Hom(G,\langle
2103  \zeta_n\rangle)$is also cyclic of order~$n$. 2104\end{proof} 2105 2106\begin{corollary}\label{cor:dir_ord} 2107We have$\#D(N,R) \mid \vphi(N)$, with equality 2108if and only if the order of our choice of$\zeta\in R$2109is a multiple of the exponent of the group$(\Z/N\Z)^*$. 2110\end{corollary} 2111 2112\begin{example} 2113The group$D(5,\C)$has elements 2114$\{[1], [i], [-1], [-i]\}$, 2115so is cyclic of order$\vphi(5)=4$. 2116In contrast, the group$D(5,\Q)$has only the 2117two elements$[1]$and$[-1]$and order$2$. 2118\end{example} 2119 2120Fix a positive integer~$N$, and write$N=\prod_{i=1}^{n} {p_i^{e_i}}$2121where$p_1<p_2<\cdots < p_n$are the prime divisors of~$N$. By 2122\exref{ch:dirichlet}{ex:cyclic}, each factor$(\Z/p_i^{e_i}\Z)^*$is a 2123cyclic group$C_i=\langle g_i \rangle$, except if$p_1=2$and$e_1\geq
21243$, in which case$(\Z/p_1^{e_1}\Z)^*$is a product of the cyclic 2125subgroup$C_0 = \langle -1 \rangle$of order$2$with the cyclic 2126subgroup$C_1 = \langle 5\rangle$. In all 2127cases we have $$2128(\Z/N\Z)^* \isom \prod_{0\leq i\leq n} C_i = \prod_{0\leq i \leq n} \langle g_i \rangle. 2129$$ 2130For~$i$such that$p_i>2$, choose the generator$g_i$of$C_i$to be 2131the element of$\{2,3,\ldots, p_i^{e_i}-1\}$that is smallest and 2132generates. Finally, use the Chinese Remainder Theorem (see 2133\cite[\S1.3.3]{cohen:course_ant})) to lift each$g_i$to an element in 2134$(\Z/N\Z)^*$, also denoted$g_i$, that is~$1$modulo each$p_j^{e_j}$2135for$j\neq i$. 2136 2137\begin{algorithm}{Minimal generator for$(\Z/p^r\Z)^*$}\label{alg:mingens} 2138Given an odd prime power$p^r$, this algorithm computes 2139a minimal generator for$(\Z/p^r\Z)^*$. 2140\begin{steps} 2141\item{}[Factor Group Order] Factor$n=\phi(p^r) = p^{r-1}\cdot 2\cdot
2142  ((p-1)/2)$as a product$\prod p_i^{e_i}$of primes. This is 2143 equivalent in difficulty to factoring$(p-1)/2$. (See chapters 8 2144 and 10 of \cite{cohen:course_ant} for integer factorization 2145 algorithms.) 2146\item{}[Initialize]\label{step:gen_init} Set$g\set 2$. 2147\item{}[Generator?] Using the binary powering algorithm (see 2148 \cite[\S1.2]{cohen:course_ant}), compute$g^{n/p_i}\pmod{p^r}$, for 2149 each prime divisor$p_i$of~$n$. If any of these powers are$1$, 2150 set$g\set g+1$and go to Step~\ref{step:gen_init}. 2151If no powers are$1$, output$g$and terminate. 2152\end{steps} 2153\end{algorithm} 2154For the proof, see \exref{ch:dirichlet}{ex:orderalg}. 2155 2156\begin{example} 2157A minimal generator for$(\Z/49\Z)^*$is$3$. 2158We have$n=\vphi(49)=42=2\cdot 3\cdot 7$, and 2159$$2160 2^{n/2} \con 1, \qquad 2^{n/3} \con 18, \qquad 2^{n/7} \con 15 \pmod{49}. 2161$$ 2162so$2$is not a generator for$(\Z/49\Z)^*$. (We see 2163this just from$2^{n/2}\con 1\pmod{49}$.) However 2164$$2165 3^{n/2} \con 48, \qquad 3^{n/3} \con 30, \qquad 3^{n/7} \con 43 \pmod{49}. 2166$$ 2167\end{example} 2168 2169\begin{example}\label{ex:mingens} 2170In this example 2171we compute minimal generators for$N=25$,$100$, and$200$: 2172\begin{enumerate} 2173\item 2174The minimal generator for$(\Z/25\Z)^*$is$2$. 2175 2176\item 2177Minimal generators for$(\Z/100\Z)^*$, lifted 2178to numbers modulo$100$, are$g_0=51$,$g_1=1$and$g_2=77$. 2179Notice that$g_0\con -1\pmod{4}$and$g_0\con 1\pmod{25}$, that$g_1=1$since$2\mid N$, but 2180$8\nmid N$, and$g_2\con 2\pmod{25}$is the minimal generator modulo~$25$. 2181 2182\item 2183Minimal generators for$(\Z/200\Z)^*$, lifted 2184to numbers modulo$200$, are 2185$g_0 = 151$,$g_1 = 101$, and$g_2=177$. Note 2186that$g_0\con -1\pmod{4}$, that$g_1\con 5\pmod{8}$, 2187and$g_2\con 2\pmod{25}$. 2188\end{enumerate} 2189\end{example} 2190 2191Fix an element~$\zeta$of finite multiplicative order in a ring~$R$, 2192and let$D(N,R)$denote the group of Dirichlet characters modulo~$N$2193over~$R\$, with image in