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