CoCalc Public Fileswww / 168 / notes / modular_forms_book / current.texOpen with one click!
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
403
This is a book about algorithms for computing with modular forms that
404
started as a series of notes for a graduate course at Harvard
405
University in 2004. This book is meant to answer the question ``How
406
do {\em you} compute spaces of modular forms'', by both providing a
407
clear description of the specific algorithms that are used and
408
explaining how to apply them using \SAGE \cite{sage}.
409
410
I have spent many years trying to find good practical ways to compute
411
with classical modular forms for congruence subgroups of $\SL_2(\Z)$,
412
and have implemented most of these algorithms several times, first in
413
C++ \cite{stein:hecke}, then in MAGMA \cite{magma}, and most recently
414
as part of \SAGE. Much of this work has involved turning formulas and
415
constructions burried in obscure research papers into precise
416
computational recipes, then testing these in many cases and
417
eliminating subtle inaccuracies (published theorems sometimes contain
418
small mistakes that appear magnified when implemented and run on a
419
computer). The goal of this book is to explain some of what I have
420
learned along the way.
421
%, and also describe unsolved problems whose
422
%solution would move the theory forward.
423
424
The author is aware of no other books on computing with modular forms,
425
the closest work being Cremona's book \cite{cremona:algs}, which is
426
about computing with elliptic curves, and Cohen's book
427
\cite{cohen:course_ant} about algebraic number theory. The field is
428
not yet mature, and there are missing details and potential
429
improvements to many of the algorithms, which you the reader might
430
fill in, and which would be greatly appreciated by other
431
mathematicians.
432
433
This book focuses on how best to compute the spaces $M_k(N,\eps)$ of
434
modular forms, where $k\geq 2$ is an integer and~$\eps$ is a Dirichlet
435
character modulo~$N$. I will spend the most effort explaining the
436
algorithms that appear so far to be the best (in practice!) for such
437
computations. I will not discuss computing half-integral weight
438
forms, weight one forms, forms for non-congruence subgroups or groups
439
other than $\GL_2$, Hilbert and Siegel modular forms, trace formulas,
440
$p$-adic modular forms, and modular abelian varieties, all of which
441
are topics for another book.
442
443
The reader is not assumed to have prior exposure to modular forms, but
444
should be familiar with abstract algebra, basic algebraic number
445
theory, 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.}
461
Kevin Buzzard made many helpful remarks which were helpful in finding
462
the algorithms in Chapter~\ref{ch:dirichlet}. Noam Elkies made many
463
remarks about chapters 1 and 2. The students in the Harvard course
464
made helpful remark; in particular, Abhinav Kumar made observations
465
about computing widths of cusps, Thomas James Barnet-Lamb about how to
466
represent Dirichlet characters, and Tseno V. Tselkov, Jennifer
467
Balakrishnan and Jesse Kass made other remarks.
468
469
Parts of Chapter~\ref{ch:modform} follow
470
\cite[Ch.~VII]{serre:arithmetic} closely, though we adjust the
471
notation, definitions, and order of presentation to be consistent with
472
the rest of this book. (For example, Serre writes $2k$ for the weight
473
instead of~$k$.)
474
475
\vspace{2ex}
476
\noindent{\bf Grant Information.}
477
This material is based upon work supported by the National Science
478
Foundation 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}
512
Modular forms are certain types of functions on
513
the {\em complex upper half plane}
514
$$
515
\h = \{z \in \C : \Im(z) > 0\}.
516
$$
517
The 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
$$
522
acts on $\h$ via linear fractional transformations,
523
as follows.
524
If
525
$\gamma = \abcd{a}{b}{c}{d} \in \SL_2(\R)$ and $z\in\h$,
526
then (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]
532
The \defn{modular group} is
533
the subgroup $\SL_2(\Z)$ of $\SL_2(\R)$ of matrices
534
with integer entries. Thus $\SL_2(\Z)$ is the group of
535
all matrices $\abcd{a}{b}{c}{d}$ with $a,b,c,d\in\Z$
536
and $ad-bc=1$.
537
\end{definition}
538
For example, the
539
matrices
540
\begin{equation}\label{eqn:ST}
541
S=\mtwo{0}{-1}{1}{\hfill 0}
542
\qquad\text{and} \qquad
543
T=\mtwo{1}{1}{0}{1}
544
\end{equation}
545
are both elements of $\SL_2(\Z)$;
546
the matrix $S$ defines the function $z\mapsto -1/z$,
547
and~$T$ the function $z\mapsto z+1$.
548
\begin{theorem}
549
The 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
558
In \sage we compute the group $\SL_2(\Z)$ and its generators as follows:
559
\begin{verbatim}
560
sage: G = SL(2,Z)
561
sage: print G
562
The modular group SL(2,Z)
563
sage: S, T = G.gens()
564
sage: S
565
[ 0 -1]
566
[ 1 0]
567
sage: 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
585
The 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
587
on~$\h$, and fails to be analytic at~$i$.
588
589
Modular forms are holomorphic functions on $\h$ that transform in a
590
particular way under a subgroup of $\SL_2(\Z)$. Before definining
591
general 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]
597
A \defn{weakly modular function} of weight $k\in\Z$ is a meromorphic
598
function $f$ on $\h$ such that
599
for all $\gamma=\abcd{a}{b}{c}{d}\in\SL_2(\Z)$ and all $z\in\h$
600
we have
601
\begin{equation}\label{eqn:modfunc}
602
f(z) = (cz+d)^{-k} f(\gamma(z)).
603
\end{equation}
604
\end{definition}
605
The constant functions are weakly modular of weight $0$.
606
There are no nonzero weakly modular functions of odd weight
607
(see \exref{ch:modform}{ex:nomodformodd}), and it is by
608
no means obvious that there are any weakly modular functions
609
of even weight $k\geq 2$.
610
The product of two weakly modular functions of weights $k_1$
611
and $k_2$ is a weakly modular function of weight $k_1+k_2$
612
(see \exref{ch:modform}{ex:wmfprod}),
613
so once we find some nonconstant weakly modular functions, we'll
614
find many of them.
615
616
When $k$ is even (\ref{eqn:modfunc}) has a possibly
617
more 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
$$
622
Thus (\ref{eqn:modfunc}) simply says that
623
the weight~$k$ ``differential form'' $f(z)dz^{k/2}$
624
is fixed under the action of every element of
625
$\SL_2(\Z)$.
626
627
628
Since $\SL_2(\Z)$ is generated by the matrices $S$ and $T$
629
of (\ref{eqn:ST}), to show
630
that a meromorphic function~$f$ on $\h$ is a
631
weakly modular function all we have to do is show
632
that 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
637
Suppose that $f$ is a weakly modular function of some weight~$k$.
638
Then $f$ might have a \defn{Fourier expansion}, which we try to obtain
639
as follows. Let $q=q(z)=e^{2\pi i z}$, which we view as a holomorphic
640
function $\C\union{\infty} \to D$, where $D$ is the closed unit disk.
641
Let $D'$ be the punctured unit disk, i.e., $D$ with the origin
642
removed, 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
644
for every $z\in\h$ we have $F(q(z)) = f(z)$. This function $F$ is
645
thus a complex-valued function on the open unit disk. It may or
646
may not be well behaved at $0$.
647
648
Suppose 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
$$
653
If this is the case, we say that~$f$ is
654
\defn{meromorphic at $\infty$}. If, moreover,
655
$m\geq 0$, then we say
656
that~$f$ is \defn{holomorphic at $\infty$}.
657
658
\begin{definition}[Modular Function]
659
A \defn{modular function} of weight~$k$ is a weakly modular function
660
of 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
668
If $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}
671
f(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}
674
The above series converges for all $z\in\h$.
675
\end{proposition}
676
\begin{proof}n
677
The function $f(q)$ is holomorphic on $D$, so
678
its Taylor series converges absolutely
679
in $D$. See also \cite[\S{}VII.4]{serre:arithmetic}
680
for an explicit bound on the $|a_n|$.
681
\end{proof}
682
We 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$
684
should be the value of $F$ at $0$, which is $a_0$
685
from the power series.
686
687
\begin{definition}[Cusp Form]
688
A \defn{cusp form} of weight~$k$ (and level $1$) is a modular form of
689
weight~$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}
694
We next define spaces of modular forms of arbitrary level. For
695
example, when $k=2$ these are closely related to elliptic curves and
696
abelian varieties.
697
698
A \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))$$
701
for some $N$. The smallest such~$N$ is the \defn{level} of $\Gamma$.
702
For 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
$$
708
and
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
$$
714
are congruence subgroups of level~$N$.
715
716
Let $k$ be an integer.
717
Define the \defn{weight~$k$ right action} of $\GL_2(\Q)$ on
718
the set of functions~$f:\h\to\C$ as follows.
719
If $\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}
724
The action $f\mapsto f|[\gamma]_k$ is a right action
725
of $\GL_2(\Z)$ on the set of all functions $f:\h\to\C$; in
726
particular,
727
$$
728
f|[\gamma_1\gamma_2]_k = (f|[\gamma_1]_k)|[\gamma_2]_k,
729
$$
730
\end{proposition}
731
\begin{proof}
732
See \exref{ch:modform}{ex:grpact}.
733
\end{proof}
734
735
\begin{definition}[Weakly Modular Function]
736
A \defn{weakly modular function} of weight $k$ for a
737
congruence subgroup $\Gamma$ is a meromorphic
738
function $f :\h \to \C$ such that
739
$f|[\gamma]_k = f$ for all $\gamma \in \Gamma$.
740
\end{definition}
741
742
A central object in the theory of modular forms (and modular symbols)
743
is the set of all {\em cusps}
744
$$
745
\P^1(\Q) = \Q \union \{\infty\}.
746
$$
747
The 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
749
will often identify elements of $C(\Gamma)$ with a representative
750
element from the orbit.) For example, if $\Gamma=\SL_2(\Z)$ there is
751
exactly 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}
757
This is \exref{ch:modform}{ex:sl2ztrans}.
758
\end{proof}
759
760
\begin{proposition}
761
For any congruence subgroup $\Gamma$, the set $C(\Gamma)$
762
of cusps is finite.
763
\end{proposition}
764
765
In order to define modular forms for general congruence subgroups we
766
need to make sense of what it means for a function to be holomorphic
767
on the \defn{extended upper halfplane}
768
$$
769
\h^* = \h\union \P^1(\Q).
770
$$
771
In Section~\ref{sec:modform1} we considered a weakly modular
772
function~$f$ on $\SL_2(\Z)$
773
to be holomorphic at~$\infty$ if its $q$-expansion
774
is of the form
775
$\sum_{n=0}^{\infty} a_n q^n$.
776
777
In order to make sense of holomorphicity of a weakly modular
778
function $f$ for $\Gamma$ at any $\alpha\in\Q$,
779
we first prove a lemma.
780
\begin{lemma}
781
If $f :\h\to\C$ is a weakly modular function of weight $k$
782
for a congruence subgroup $\Gamma$, and $\delta \in \SL_2(\Z)$,
783
then $f|[\delta]_k$ is a weakly modular function for
784
$\delta^{-1}\Gamma \delta$.
785
\end{lemma}
786
\begin{proof}
787
If $s = \delta^{-1} \gamma\delta \in \delta^{-1}\Gamma \delta$,
788
then
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
796
Fix a weight~$k$ weakly modular function~$f$ for some congruence
797
subgroup~$\Gamma$, and suppose $\alpha \in \Q$. In
798
Section~\ref{sec:modform1} we constructed the $q$-expansion of $f$ by
799
using that $f(z) = f(z+1)$, which held since
800
$T=\mtwo{1}{1}{0}{1}\in\SL_2(\Z)$. Unfortunately, there are
801
congruence subgroups $\Gamma$ such that $T\not\in\Gamma$. Moreover,
802
even if we are interested only in modular forms for $\Gamma_1(N)$,
803
where 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
808
positive integer $h$, and again when~$f$ is meromorphic at infinity we
809
obtain a Fourier expansion
810
\begin{equation}\label{eqn:qser}
811
f(z) = \sum_{n=m}^{\infty} a_n q^{n/N},
812
\end{equation}
813
but 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
817
What about the other cusps $\alpha\in\P^1(\Q)$? By
818
Lemma~\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
821
holomorphic at $\infty$.
822
823
\begin{definition}[Modular Form]
824
A {\em modular form} of integer weight $k$ for a congruence subgroup
825
$\Gamma$ is a weakly modular function $f:\h^*\to \C$ that
826
is holomorphic on $\h^*$.
827
\end{definition}
828
829
\begin{proposition}
830
A weakly modular function $f$ of weight $k$ for $\Gamma$
831
is holomorphic at every element of $\P^1(\Q)$ if
832
is holomorphic at a set of representative elements
833
for $C(\Gamma)$.
834
\end{proposition}
835
\begin{proof}
836
Let $c_1,\ldots, c_n \in \P^1(\Q)$ be representatives
837
for the set of cusps for $\Gamma$.
838
If $\alpha \in \P^1(\Q)$ then there is $\gamma\in\Gamma$
839
such that $\alpha = \gamma(c_i)$ for some $i$.
840
By hypothesis $f$ is holomorphic at $c_i$, so if $\delta\in\SL_2(\Z)$
841
is such that $\delta(\infty) = c_i$, then $f|[\delta]_k$
842
is holomorphic at $\infty$. Since $f$ is a weakly modular
843
function,
844
\begin{equation}\label{eqn:prop:holoall}
845
f|[\delta]_k = (f|[\gamma]_k)|[\delta]_k = f|[\gamma\delta]_k.
846
\end{equation}
847
But $\gamma(\delta(\infty)) = \gamma(c_i) = \alpha$, so
848
(\ref{eqn:prop:holoall}) implies that $f$ is holomorphic
849
at~$\alpha$.
850
\end{proof}
851
852
853
\subsection{Computing Widths of Cusps}
854
Let $\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
856
that $\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
859
section 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,
865
e.g., $\Gamma=\Gamma_0(N)$ or $\Gamma_1(N)$.
866
\begin{steps}
867
\item{}[Find $\gamma$] Use the extended Euclidean algorithm
868
to find $\gamma\in\SL_2(\Z)$ such that $\gamma(\infty)=\alpha$,
869
as follows.
870
If $\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
$$
877
Note that the entries of $\delta(x)$ are constant or
878
linear 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
889
Suppose $\alpha=0$ and $\Gamma=\Gamma_0(N)$ or $\Gamma_1(N)$.
890
Then $\gamma=\abcd{0}{1}{1}{0}$ has the property that $\gamma(\infty)=\alpha$.
891
Next, 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
$$
895
Thus the smallest positive solution is $h=N$, so the width of $0$
896
is~$N$.
897
898
\item Suppose $N=pq$ where $p,q$ are distinct primes, and let $\alpha=1/p$.
899
Then $\gamma=\abcd{1}{0}{p}{1}$ sends $\infty$ to $\alpha$.
900
The 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
$$
905
Since $p^2x \con 0\pmod{pq}$, we see that $x=q$ is the smallest solution.
906
Thus $1/p$ has width $q$, and symmetrically $1/q$ has width~$p$.
907
\end{enumerate}
908
\end{example}
909
\begin{remark}
910
For $\Gamma_0(N)$, once we enforce that the bottom
911
left entry is $0\pmod{N}$, and use that the determinant is 1, the
912
coprimality from the other two congruences is automatic.
913
So there is one congruence to solve in the $\Gamma_0(N)$ case.
914
There 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
922
In this section you will finally see some examples of modular forms of
923
level $1$! We will first introduce the Eisenstein series, one of each
924
weight, then define $\Delta$, which is a cusp form of weight $12$. In
925
Section~\ref{sec:struct1} we will prove the structure theorem,
926
which says that using addition and multiplication of these forms, we
927
can generate all modular forms of level $1$.
928
929
For 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
$$
934
where for a given $z$, the sum is over all $m,n\in\Z$ such that
935
$mz+n\neq 0$.
936
937
\begin{proposition}
938
The 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}
942
See \cite[\S{} VII.2.3]{serre:arithmetic} for a proof
943
that $G_k(z)$ defines a holomorphic function on $\h^*$.
944
To 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
$$
949
and
950
$$
951
G_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)$,
958
where $\zeta$ is the Riemann zeta function.
959
\end{proposition}
960
\begin{proof}
961
Taking the limit as $z\to i\infty$ in the definition
962
of $G_k(z)$, we obtain $\sum^*_{n\in\Z} \frac{1}{n^k}$, since
963
the terms involving $z$ all go to $0$ as $z\mapsto i\infty$.
964
This sum is twice $\zeta(k) = \sum_{n\geq 1} \frac{1}{n^k}$.
965
\end{proof}
966
967
For example,
968
$$G_4(\infty) = 2\zeta(4) = \frac{1}{3^2\cdot 5} \pi^4$$
969
and
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$}
974
Suppose $E=\C/\Lambda$ is an elliptic curve over $\C$, viewed as a quotient
975
of $\C$ by a lattice $\Lambda=\Z\omega_1+\Z\omega_2$, with $\omega_1/\omega_2\in\h$.
976
Then
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
$$
981
and
982
$$
983
(\wp')^2 = 4\wp^3 - 60 G_4(\omega_1/\omega_2) \wp - 140 G_6(\omega_1/\omega_2).
984
$$
985
The discriminant of the cubic $4x^3 - 60G_4(\omega_1/\omega_2) x -
986
140 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
$$
990
is a cusp form of weight $12$.
991
\begin{lemma}\label{lem:delnz}
992
The cusp form $\Delta$ has a $0$ only at $\infty$.
993
\end{lemma}
994
\begin{proof}
995
Let $\omega_1, \omega_2$ be as above.
996
Since~$E$ is an elliptic curve, $\Delta(\omega_1/\omega_2)\neq 0$.
997
\end{proof}
998
999
\subsection{Fourier Expansions of Eisenstein Series}
1000
Recall from (\ref{eqn:qexp1}) that elements $f$ of $M_k(\SL_2(\Z))$ can be
1001
expressed as formal power series in terms of $q(z)=e^{2\pi i z}$, and
1002
that this expansion is called the Fourier expansion of $f$.
1003
The following proposition gives the Fourier expansion of the
1004
Eisenstein series $G_k(z)$.
1005
1006
\begin{proposition}\label{prop:qexpGk}
1007
For 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
$$
1012
where $\sigma_d(n)$ is the sum of the $d$th powers of the divisors
1013
of~$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
1024
From a computational point of view, the $q$-expansion for $G_k$ from
1025
Proposition~\ref{prop:qexpGk} is unsatisfactory, because it involves
1026
transcendental numbers. To understand more clearly what is going on,
1027
we 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}
1032
Expanding the power series on the left we have $$
1033
\frac{x}{e^x - 1} =
1034
1 - \frac{x}{2} + \frac{x^2}{12} - \frac{x^4}{720} + \frac{x^6}{30240}
1035
- \frac{x^8}{1209600} + \cdots $$
1036
As this expansion suggests, the
1037
Bernoulli numbers $B_n$ with $n>1$ odd are~$0$ (see
1038
\exref{ch:modform}{ex:odd_bernoulli}).
1039
Expanding 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
1043
B_{4}=-\frac{1}{30},\quad B_{6}=\frac{1}{42},\quad
1044
B_{8}=-\frac{1}{30},\quad $\vspace{1.5ex}
1045
1046
\noindent{}$\ds
1047
B_{10}=\frac{5}{66},\quad
1048
B_{12}=-\frac{691}{2730},\quad
1049
B_{14}=\frac{7}{6},\quad
1050
B_{16}=-\frac{3617}{510},\quad
1051
B_{18}=\frac{43867}{798},\quad
1052
$\vspace{1.5ex}
1053
1054
\noindent{}
1055
$\ds{}\!\!B_{20}=-\frac{174611}{330},\quad
1056
B_{22}=\frac{854513}{138},\quad
1057
B_{24}=-\frac{236364091}{2730},\quad
1058
B_{26}=\frac{8553103}{6}.
1059
%B_{28}=-\frac{23749461029}{870},\quad
1060
$\vspace{1ex}
1061
1062
%begin_sage
1063
Use the \code{bernoulli} command to compute Bernoulli
1064
numbers in \sage.
1065
\begin{verbatim}
1066
sage: bernoulli(12)
1067
-691/2730
1068
sage: bernoulli(50)
1069
495057205241079648212477525/66
1070
\end{verbatim}
1071
%end_sage
1072
1073
1074
For us, the significance of the Bernoulli numbers is their connection
1075
with values of~$\zeta$ at positive even integers.
1076
\begin{proposition}\label{prop:zeta_even}
1077
If $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}
1083
The proof in \cite[\S VII.4]{serre:arithmetic}
1084
involves manipulating a power series expansion for $z \cot(z)$.
1085
\end{proof}
1086
1087
\begin{definition}[Normalized Eisenstein Series]
1088
The \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}
1093
Combining 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}
1098
It 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}
1113
If $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
1115
holomorphic 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
1117
theorem to give a presentation for the vector space of modular forms
1118
of weight~$k$; this presentation will allow us to obtain an algorithm
1119
to compute a basis for this space.
1120
1121
Let $\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}
1126
Suppose $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
$$
1131
where $\ds \sum^*_{w \in D}$ is the sum over elements of $\cF$
1132
other than~$i$ or~$\rho$.
1133
\end{theorem}
1134
\begin{proof}
1135
Serre proves this theorem in \cite[\S{}VII.3]{serre:arithmetic} using
1136
the residue theorem from complex analysis.
1137
\end{proof}
1138
1139
Let $M_k=M_k(\SL_2(\Z))$ denote the complex vector space of modular
1140
forms of weight~$k$ for $\SL_2(\Z)$, and let~$S_k=S_k(\SL_2(\Z))$
1141
denote the subspace of weight~$k$ cusp forms for $\SL_2(\Z)$. We have
1142
an exact sequence
1143
$$
1144
0 \to S_k \to M_k \to \C
1145
$$
1146
that sends $f\in M_k$ to $f(\infty)$. When $k\geq 4$ is even, the
1147
space $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,
1149
so 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
1154
Thus 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}
1160
For $k<0$ and $k=2$, we have $M_k=0$.
1161
\end{proposition}
1162
\begin{proof}
1163
Suppose $f\in M_k$ is nonzero yet $k=2$ or $k<0$. By
1164
Theorem~\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
$$
1169
This is impossible because each quantity on the left-hand
1170
side 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}
1175
Multiplication 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.)
1179
We apply Theorem~\ref{thm:valence} to $G_4$ and~$G_6$.
1180
If $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
$$
1185
with the $\ord$s all nonnegative,
1186
so $\ord_{\rho}(G_4) = 1$ and $\ord_w(G_4) = 0$ for all $w\neq \rho$.
1187
Likewise $\ord_{i}(G_6) = 1$ and $\ord_w(G_6) = 0$ for all $w\neq i$.
1188
Thus $\Delta(i)\neq 0$, so $\Delta$ is not identically~$0$ (this
1189
also follows from Lemma~\ref{lem:delnz} above).
1190
Since $\Delta$ has weight~$12$ and $\ord_\infty(\Delta)\geq 1$,
1191
Theorem~\ref{thm:valence} implies that~$\Delta$ has a simple
1192
zero at $\infty$ and does not vanish on~$\h$.
1193
Thus if $f\in S_k$ and we let $g=f/\Delta$, then $g$ is holomorphic
1194
and satisfies the appropriate transformation formula, so~$g$
1195
is 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
$
1220
where $\lfloor{}x \rfloor{}$ is the biggest integer $\leq x$.
1221
\end{corollary}
1222
\begin{proof}
1223
As we have seen above, the formula is true when $k\leq 12$.
1224
By Theorem~\ref{thm:delta_iso}, the dimension increases by $1$
1225
when~$k$ is replaced by $k+12$.
1226
\end{proof}
1227
1228
\begin{theorem}\label{thm:mk_one_basis}
1229
The space $M_k$ has as basis the
1230
modular forms $G_4^a G_6^b$, where $a,b$
1231
are all pairs of nonnegative integers such that
1232
$4a+6b=k$.
1233
\end{theorem}
1234
\begin{proof}
1235
We first prove by induction that the modular forms
1236
$G_4^a G_6^b$ generate $M_k$, the cases $k\leq 12$
1237
being clear (e.g., when $k=0$ we have $a=b=0$ and basis~$1$).
1238
Choose some pair of integers $a,b$ such that $4a+6b=k$
1239
(it is an elementary exercise to show these exist).
1240
The form $g=G_4^a G_6^b$ is not a cusp form, since
1241
it is nonzero at $\infty$. Now suppose $f\in M_k$
1242
is arbitrary. Since $M_k = S_k \oplus \C G_k$, there
1243
is $\alpha\in\C$ such that $f - \alpha g \in S_k$.
1244
Then by Theorem~\ref{thm:delta_iso}, there is $h \in M_{k-12}$
1245
such that $f - \alpha g = \Delta h$. By induction,
1246
$h$ is a polynomial in $G_4$ and $G_6$ of the required
1247
type, and so is $\Delta$, so $f$ is as well.
1248
1249
Suppose there is a nontrivial linear relation between the $G_4^a
1250
G_6^b$ for a given~$k$. By multiplying the linear relation by a
1251
suitable power of $G_4$ and $G_6$, we may assume that that we have
1252
such a nontrivial relation with $k\con 0\pmod{12}$. Now divide the
1253
linear relation by $G_6^{k/12}$ to see that $G_4^3/G_6^2$ satisfies a
1254
polynomial with coefficients in $\C$. Hence $G_4^3/G_6^2$ is a root
1255
of 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}
1260
Given integers~$n$ and~$k$, this algorithm computes
1261
a basis of $q$-expansions for the complex vector
1262
space $M_k$ mod $q^n$. The $q$-expansions output
1263
by this algorithm have coefficients in $\Q$.
1264
\begin{steps}
1265
\item{}[Simple Case] If $k=0$ output the basis with
1266
just $1$ in it, and terminate; otherwise if $k<4$ or~$k$
1267
is odd, output the empty basis and terminate.
1268
\item{}[Power Series] Compute $E_4$ and $E_6$ mod $q^n$
1269
using the formula from (\ref{eqn:ekexp}) and
1270
the definition (\ref{eqn:def_bernoulli}) of Bernoulli
1271
numbers.\edit{Look up what the {\em real} algorithm
1272
for 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$.
1279
If~$a$ is an integer, compute and output the basis
1280
element $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
1283
intermediate powers, so they can be reused later, and
1284
likewise for powers of $E_6$.
1285
\end{steps}
1286
\end{algorithm}
1287
\begin{proof}
1288
This is simply a translation of Theorem~\ref{thm:mk_one_basis}
1289
into an algorithm, since $E_k$ is a nonzero scalar multiple
1290
of $G_k$. That the $q$-expansions have coefficients
1291
in $\Q$ follows from (\ref{eqn:ekexp}).
1292
\end{proof}
1293
1294
\begin{example}
1295
We compute a basis for $M_{24}$, which is the space with
1296
smallest weight whose dimension is bigger than $1$.
1297
It has as basis $E_4^6$, $E_4^3 E_6^2$, and $E_6^4$, whose explicit
1298
expansions are
1299
\begin{align*}
1300
E_4^6 &= \frac{1}{191102976000000} +
1301
\frac{1}{132710400000}q + \frac{203}{44236800000}q^2 + \cdots\\
1302
E_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
1310
In Section~\ref{sec:vmthesis}, we will discuss properties
1311
of the reduced row echelon form of any basis for $M_k$, which
1312
have 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}
1317
The space $S_k$ has a basis $f_1,\ldots, f_{d}$ such
1318
that 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
1320
the $f_j$ all lie in $\Z[[q]]$.
1321
\end{lemma}
1322
This is a straightforward construction involving $E_4$, $E_6$ and
1323
$\Delta$. The following proof very closely follows \cite[Ch.~X,
1324
Thm.~4.4]{lang:modular}, which is in turn follows the
1325
first lemma of Victor Miller's thesis.
1326
\begin{proof}
1327
Let $d=\dim S_k$.
1328
Since $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
$$
1336
have $q$-expansions in $\Z[[q]]$ with leading
1337
coefficient~$1$.
1338
Choose integers $a,b\geq 0$ such that
1339
$$
1340
4a+6b\leq 14 \qquad\text{and}\qquad 4a + 6b \con k \pmod{12},
1341
$$
1342
with $a=b=0$ when $k\con 0\pmod{12}$, and
1343
let
1344
$$
1345
g_j = \Delta^j F_6^{2(d-j)+a} F_4^b,\qquad\qquad \text{for } j=1,\ldots,d.
1346
$$
1347
Then
1348
$$
1349
a_j(g_j) = 1, \qquad\text{and}\qquad a_i(g_j)=0\qquad\text{when}\qquad i<j.
1350
$$
1351
Hence the $g_j$ are linearly independent over $\C$, and thus form
1352
a basis for $S_k$. Since $F_4, F_6$, and $\Delta$ are all in $\Z[[q]]$,
1353
so are the $g_j$. The $f_i$ may then be constructed from the $g_j$
1354
by 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}
1359
The basis coming from Victor Miller's lemma is canonical,
1360
since it is just the reduced row echelon form of any basis.
1361
Also the {\em integral} linear combinations are precisely
1362
the modular forms of level $1$ with integral $q$-expansion.
1363
\end{remark}
1364
1365
We extend the Victor Miller basis to all $M_k$ by taking
1366
a multiple of $G_k$ with constant term $1$, and subtracting
1367
off the $f_i$ from the Victor Miller basis so that the
1368
coefficients of $q, q^2, \ldots q^d$ of
1369
the resulting expansion are $0$. We call the extra basis
1370
element $f_0$.
1371
\edit{Argue: Is $G_k$ integral?}
1372
1373
1374
1375
1376
\begin{example}
1377
If $k=24$, then $d=2$. Choose $a=b=0$, since $k\con 0\pmod{12}$.
1378
Then
1379
$$g_1 = \Delta F_6^2 =
1380
q - 1032q^2 + 245196q^3 + 10965568q^4 + 60177390q^5 - \cdots
1381
$$
1382
and
1383
$$
1384
g_2 = \Delta^2 = q^2 - 48q^3 + 1080q^4 - 15040q^5 + \cdots
1385
$$
1386
We let $f_2=g_2$ and
1387
$$
1388
f_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;
1396
1 + 240*q + 2160*q^2 + 6720*q^3 + 17520*q^4 + 30240*q^5 +
1397
60480*q^6 + 82560*q^7 + O(q^8)
1398
> n6 := Newforms(MF(1,6))[1][1];
1399
> n6
1400
> ';
1401
1402
>> ';
1403
^
1404
User 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 +
1407
16808*q^7 + O(q^8)
1408
> F6 := n6*(-504);
1409
> F4;
1410
1 + 240*q + 2160*q^2 + 6720*q^3 + 17520*q^4 + 30240*q^5 +
1411
60480*q^6 + 82560*q^7 + O(q^8)
1412
> F6;
1413
1 - 504*q - 16632*q^2 - 122976*q^3 - 532728*q^4 - 1575504*q^5 -
1414
4058208*q^6 - 8471232*q^7 + O(q^8)
1415
> Delta := Newforms(CS(MF(1,12)))[1][1];
1416
> Delta;
1417
q - 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;
1420
q - 1032*q^2 + 245196*q^3 + 10965568*q^4 + 60177390*q^5 -
1421
1130921568*q^6 + 870123128*q^7 + O(q^8)
1422
> Delta^2;
1423
q^2 - 48*q^3 + 1080*q^4 - 15040*q^5 + 143820*q^6 - 985824*q^7 +
1424
O(q^8)
1425
> 1032*Delta^2 + Delta*F6^2;
1426
q + 195660*q^3 + 12080128*q^4 + 44656110*q^5 - 982499328*q^6 -
1427
147247240*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}
1440
When $k=36$, the Victor Miller basis, including $f_0$, is
1441
\begin{align*}
1442
f_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
1454
If 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
1456
Miller 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}
1469
For any positive integer~$n$, let
1470
$$
1471
S_n = \left\{\mtwo{a}{b}{0}{d} \in M_2(\Z) \,\,:\,\,
1472
a\geq 1,\,\, ad=n, \text{ and } 0\leq b <d\right\}.
1473
$$
1474
Note 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
1477
Hermite normal form (the analogue of reduced row
1478
echelon form over~$\Z$).
1479
1480
1481
\begin{definition}[Hecke Operator $T_{n,k}$]
1482
The~$n$th Hecke operator $T_{n,k}$ of weight~$k$
1483
is the operator on functions on $\h$ defined by
1484
$$
1485
T_{n,k}(f) = \sum_{\gamma \in S_n}
1486
f|[\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}
1504
Suppose $\gamma\in\SL_2(\Z)$. Since~$\gamma$
1505
induces an automorphism of $\Z^2$, the set
1506
$$S_n \cdot \gamma = \{ \delta \gamma : \delta\in S_n\}$$
1507
is also in bijection with the sublattices
1508
of $\Z^2$ of index~$n$.
1509
Then for each element $\delta\gamma \in S_n\cdot \gamma$, there
1510
is $\sigma\in\SL_2(\Z)$ such that $\sigma\delta\gamma\in S_n$ (the
1511
element~$\sigma$
1512
transforms $\delta\gamma$ to Hermite normal form),
1513
and the set of elements $\sigma\delta\gamma$ is equal to $S_n$.
1514
Thus
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
1521
Since $f$ is holomorphic on $\h$,
1522
each $f|[\gamma]_k$ is holomorphic on $\h$.
1523
A finite sum of holomorphic functions is holomorphic,
1524
so $T_{n,k}(f)$ is holomorphic.
1525
1526
\end{proof}
1527
1528
We will frequently drop $k$ from the notation in $T_{n,k}$, since
1529
the weight $k$ is implicit in the modular function to which
1530
we apply the Hecke operator. Thus we henceforth make the
1531
convention that if we write $T_{n}(f)$ and~$f$ is modular,
1532
then we mean $T_{n,k}(f)$, where~$k$ is the weight of~$f$.
1533
1534
\begin{proposition}\label{prop:hecke_com}
1535
On 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}
1540
and
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.
1563
Using 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
1574
action 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$
1585
with $[\Z^2:L']=p$.
1586
1587
The 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
1592
structure of the set of chains $L\subset L'\subset\Z^2$ that we
1593
derived in the previous paragraph gives the result.
1594
\end{proof}
1595
1596
\begin{corollary}
1597
The Hecke operator $T_{p^n}$, for prime~$p$, is a polynomial in $T_p$.
1598
If $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}
1636
Suppose $f = \sum_{n\in\Z} a_n q^n$ is a modular function
1637
of weight~$k$.
1638
Then
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
$$
1644
In 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
$$
1648
where $a_{m/p}=0$ if $m/p\not\in\Z$.
1649
\end{proposition}
1650
The proposition is not that difficult to prove (or at least the proof
1651
is easy to follow), and is proved in \cite[\S
1652
VII.5.3]{serre:arithmetic} by writing out $T_n(f)$ explicitly and
1653
using that $\sum_{0\leq b<d} e^{2\pi i bm/d}$ is $d$ if $d\mid m$
1654
and~$0$ otherwise. A corollary of Proposition~\ref{prop:qexpTn} is
1655
that $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}
1666
Recall that
1667
$$
1668
E_4 = \frac{1}{240} + q + 9q^2 + 28q^3 + 73q^4 + 126q^5 + 252q^6 + 344q^7
1669
+\cdots.
1670
$$
1671
Using the formula of Proposition~\ref{prop:qexpTn}, we see
1672
that
1673
$$
1674
T_2(E_4) = (1/240 + 2^3\cdot (1/240)) + 9q + (73 + 2^3\cdot 1) q^2 + \cdots \\
1675
= 9 E_4.
1676
$$
1677
Since $M_k$ has dimension $1$, and we have proved that $T_2$
1678
preserves $M_k$, we know that $T_2$ acts as a scalar. Thus
1679
we know just from the constant coefficient of $T_2(E_4)$ that
1680
$T_2(E_4) = 9 E_4$.
1681
More generally, $T_p(E_4) = (1+p^3)E_4$.
1682
In fact for any $k$ one has that
1683
$$
1684
T_n(E_k) = \sigma_{k-1}(n) E_k,
1685
$$
1686
for 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}
1705
In this section we describe a simple algorithm for computing matrices
1706
of 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
1715
implicit 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
1724
once we have computed $T_n(f_i) \pmod{q^{d+1}}$,
1725
since the basis of~$f_i$ are in reduced row echelon form,
1726
so the combinations are just the first few coefficients
1727
of 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}
1745
This is the Hecke operator $T_2$ on $M_{36}$ is:
1746
$$
1747
\left(
1748
\begin{matrix}
1749
\hfill 34359738369&\hfill0&\hfill6218175600&\hfill9026867482214400\\
1750
0&\hfill0&\hfill34416831456&\hfill5681332472832\\
1751
0&\hfill1&\hfill194184&\hfill-197264484\\
1752
0&\hfill0&\hfill-72&\hfill-54528\\
1753
\end{matrix}\right)
1754
$$
1755
It has characteristic polynomial
1756
$$
1757
(x - 34359738369) \cdot
1758
(x^3 - 139656x^2 - 59208339456x - 1467625047588864),
1759
$$
1760
where the cubic factor is irreducible.
1761
\end{example}
1762
1763
\begin{conjecture}[Maeda]
1764
The characteristic polynomial of $T_2$ on $S_k$ is irreducible for any~$k$.
1765
\end{conjecture}
1766
1767
Kevin Buzzard even observed that in many specific cases the Galois
1768
group 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
1770
evidence 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
1788
Let\edit{Lead in about coefficients of elliptic curve
1789
modform, 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*}
1798
be the $\Delta$-function.
1799
\begin{conjecture}[Edixhoven]\label{conj:edixhoven}
1800
There is an algorithm to compute $\tau(p)$, for prime $p$, that
1801
is polynomial-time in $\log(p)$.
1802
More 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
1804
to compute $a_p$, for $p$ prime, in time polynomial in $\log(p)$.
1805
\end{conjecture}
1806
1807
1808
Bas Edixhoven, Jean-Marc Couveignes and Robin de Jong have mostly
1809
proved that $\tau(p)$ can be computed in polynomial time; their
1810
approach involves sophisticated techniques from arithmetic geometry
1811
(e.g., \'etale cohomology, motives, Arakelov theory). This is work in
1812
progress and has not been written up completely yet. The ideas
1813
Edixhoven uses are inspired by the ones introduced by Schoof, Elkies
1814
and Atkin for quickly counting points on elliptic curves over finite
1815
fields (see \cite{MR1413578}).
1816
1817
More 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
1834
The 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
1836
much more complicated than the methods presented in this chapter,
1837
since there are many more forms of small weight, and it can be
1838
difficult to obtain them. These forms of higher level have subtle and
1839
deep connections with arithmetic geometric objects such as elliptic
1840
curves, abelian varieties, and motives.
1841
1842
\begin{exercises}
1843
\item\label{ex:upperhalfpres}
1844
Suppose $\gamma = \abcd{a}{b}{c}{d}$ is a matrix with real entries
1845
and positive determinant. Prove that if $z\in\C$ is a complex
1846
number with positive imaginary part, then the imaginary
1847
part 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)
1853
is a meromorphic function on $\C$.
1854
\end{enumerate}
1855
1856
\item \label{ex:wmfprod}
1857
Suppose $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$
1862
is a modular function.
1863
\item If $f$ and $g$ are modular forms, show that $fg$
1864
is a modular form.
1865
\end{enumerate}
1866
1867
\item \label{ex:nomodformodd}
1868
Suppose $f$ is a weakly modular function of odd weight $k$.
1869
Show 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}
1880
Let $k$ be an integer, and for any function
1881
$f:\h^*\to \C$ and $\gamma=\abcd{a}{b}{c}{d}\in\GL_2(\Q)$,
1882
set $f|[\gamma]_k(z) = (cz+d)^{-k} f(\gamma(z))$.
1883
Prove that if $\gamma_1, \gamma_2 \in \SL_2(\Z)$,
1884
then 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}
1890
Prove 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
1934
Fix 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
1938
is 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}
1946
We denote the group of such Dirichlet characters by $D(N,R,\zeta)$, or
1947
by just $D(N,R)$, when the choice of $\zeta$ is clear. It follows
1948
immediately from the definition that elements of
1949
$D(N,R)$ are in bijection with homomorphisms $(\Z/N\Z)^* \to
1950
\langle \zeta \rangle$.
1951
1952
In this chapter we develop a systematic theory for computing
1953
with Dirichlet characters. These will be extremely important
1954
everywhere in the rest of this book, when we compute with
1955
spaces $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
$$
1961
For example, Eisenstein series in $M_k(\Gamma_1(N))$ are associated
1962
to 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
1964
decomposes as a direct sum
1965
$$
1966
M_k(\Gamma_1(N)) = \bigoplus_{\eps\in D(N,\C)} M_k(\Gamma_1(N))(\eps).
1967
$$
1968
Each space $M_k(\Gamma_1(N))(\eps)$ is frequently much easier
1969
to compute with than the full $M_k(\Gamma_1(N))$.
1970
For 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}
1976
If
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
$$
1982
then $M_k(\Gamma_1(N))(1) = M_k(\Gamma_0(N))$.
1983
\end{remark}
1984
1985
1986
\section{Decomposing Modular Forms Using Dirichlet Characters}
1987
The group $(\Z/N\Z)^*$ acts on $M_k(\Gamma_1(N))$ through the
1988
\defn{diamond-bracket operators}~$\langle d \rangle$.
1989
For $d\in(\Z/N\Z)^*$, define
1990
$$
1991
f|\dbd{d} = f|[\abcd{a}{b}{c}{d'}]_k,
1992
$$
1993
where $\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}),
1996
so it makes sense to consider the matrix $\abcd{a}{b}{c}{d'}$.
1997
To prove that $\dbd{d}$ preserves $M_k(\Gamma_1(N))$,
1998
we prove the more general fact that $\Gamma_1(N)$ is normal
1999
in
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
$$
2004
This will imply that $\dbd{d}$ preserves $M_k(\Gamma_1(N))$
2005
since $\abcd{a}{b}{c}{d'} \in \Gamma_0(N)$.
2006
2007
\begin{lemma}
2008
The group $\Gamma_1(N)$ is a normal subgroup of $\Gamma_0(N)$,
2009
and the quotient $\Gamma_0(N)/\Gamma_1(N)$ is
2010
isomorphic to $(\Z/N\Z)^*$.
2011
\end{lemma}
2012
\begin{proof}
2013
Consider the surjective homomorphism $r:\SL_2(\Z)\to \SL_2(\Z/N\Z)$.
2014
Then $\Gamma_1(N)$ is the exact inverse image of the subgroup $H$ of
2015
matrices of the form $\abcd{1}{*}{0}{1}$ and $\Gamma_0(N)$
2016
is the inverse image of the subroup $T$ of upper triangular matrices.
2017
It thus suffices to observe that $H$ is normal in $T$, which is clear.
2018
Finally, the quotient $T/H$ is isomorphic to the group of diagonal
2019
matrices in $\SL_2(\Z/N\Z)^*$, which is isomorphic to $(\Z/N\Z)^*$.
2020
\end{proof}
2021
2022
The 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))$.
2024
Since $M_k(\Gamma_1(N))$ is a vector space over $\C$,
2025
the $\dbd{d}$ action breaks $M_k(\Gamma_1(N))$ up as a direct
2026
sum of factors corresponding to the Dirichlet characters $D(N,C)$ of
2027
modulus~$N$.
2028
\begin{proposition}
2029
We have
2030
$$
2031
M_k(\Gamma_1(N)) = \bigoplus_{\eps \in D(N,\C)} M_k(N,\eps),
2032
$$
2033
where
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]
2058
If $f\in M_k(N,\eps)$, we say that~$f$ \defn{has character} $\eps$.
2059
\end{definition}
2060
\begin{remark}
2061
People also often write that $f$ has ``nebentypus character'' $\eps$.
2062
I rarely hear anyone actually {\em say} nebentypus, and it's somewhat
2063
redundant, 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 $
2069
The 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
2071
subspace of cusp forms, i.e., forms that vanish at {\em all}
2072
cusps (elements of $\Q \union \{\infty\}$), and $E_k(N,\eps)$
2073
is the subspace of Eisenstein series, which is the unique
2074
subspace of $M_k(N,\eps)$ that is invariant under all Hecke
2075
operators and is such that
2076
$M_k(N,\eps) = S_k(N,\eps) \oplus E_k(N,\eps)$.
2077
The space $E_k(N,\eps)$ can also be defined as the space
2078
spanned by all Eisenstein series of weight $k$ and level~$N$,
2079
as defined below. It can also be defined using the Petersson
2080
inner product.
2081
2082
\begin{remark}
2083
The 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}
2107
We have $\#D(N,R) \mid \vphi(N)$, with equality
2108
if and only if the order of our choice of $\zeta\in R$
2109
is a multiple of the exponent of the group $(\Z/N\Z)^*$.
2110
\end{corollary}
2111
2112
\begin{example}
2113
The group $D(5,\C)$ has elements
2114
$\{[1], [i], [-1], [-i]\}$,
2115
so is cyclic of order $\vphi(5)=4$.
2116
In contrast, the group $D(5,\Q)$ has only the
2117
two elements $[1]$ and $[-1]$ and order $2$.
2118
\end{example}
2119
2120
Fix a positive integer~$N$, and write $N=\prod_{i=1}^{n} {p_i^{e_i}}$
2121
where $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
2123
cyclic group $C_i=\langle g_i \rangle$, except if $p_1=2$ and $e_1\geq
2124
3$, in which case $(\Z/p_1^{e_1}\Z)^*$ is a product of the cyclic
2125
subgroup $C_0 = \langle -1 \rangle$ of order $2$ with the cyclic
2126
subgroup $C_1 = \langle 5\rangle$. In all
2127
cases 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
$$
2130
For~$i$ such that $p_i>2$, choose the generator $g_i$ of $C_i$ to be
2131
the element of $\{2,3,\ldots, p_i^{e_i}-1\}$ that is smallest and
2132
generates. 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}$
2135
for $j\neq i$.
2136
2137
\begin{algorithm}{Minimal generator for $(\Z/p^r\Z)^*$}\label{alg:mingens}
2138
Given an odd prime power $p^r$, this algorithm computes
2139
a 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}.
2151
If no powers are $1$, output $g$ and terminate.
2152
\end{steps}
2153
\end{algorithm}
2154
For the proof, see \exref{ch:dirichlet}{ex:orderalg}.
2155
2156
\begin{example}
2157
A minimal generator for $(\Z/49\Z)^*$ is $3$.
2158
We 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
$$
2162
so $2$ is not a generator for $(\Z/49\Z)^*$. (We see
2163
this 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}
2170
In this example
2171
we compute minimal generators for $N=25$, $100$, and $200$:
2172
\begin{enumerate}
2173
\item
2174
The minimal generator for $(\Z/25\Z)^*$ is $2$.
2175
2176
\item
2177
Minimal generators for $(\Z/100\Z)^*$, lifted
2178
to numbers modulo $100$, are $g_0=51$, $g_1=1$ and $g_2=77$.
2179
Notice 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
2183
Minimal generators for $(\Z/200\Z)^*$, lifted
2184
to numbers modulo $200$, are
2185
$g_0 = 151$, $g_1 = 101$, and $g_2=177$. Note
2186
that $g_0\con -1\pmod{4}$, that $g_1\con 5\pmod{8}$,
2187
and $g_2\con 2\pmod{25}$.
2188
\end{enumerate}
2189
\end{example}
2190
2191
Fix an element~$\zeta$ of finite multiplicative order in a ring~$R$,
2192
and let $D(N,R)$ denote the group of Dirichlet characters modulo~$N$
2193
over~$R$, with image in