Author: William A. Stein
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}{}
20
21%\usepackage[hyperindex,pdfmark]{hyperref}
22\usepackage[hypertex]{hyperref}
23
24\newcommand{\edit}{{\bf [[Todo: #1]]}}
25\newcommand{\examplesession}{}
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}}
33\newcommand{\Bdual}{B^{\vee}}
34
35\newcommand{\defn}{{\em \index*{#1}}}
36\newcommand{\solution}{\vspace{1em}\par\noindent{\bf Solution #1.} }
37\newcommand{\todo}{\noindent$\bullet$ {\small \textsf{#1}} $\bullet$\\}
38\newcommand{\done}{\noindent {\small \textsf{Done: #1}}\\}
39\newcommand{\danger}{\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}{%
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}{\xrightarrow{#1}}
169\newcommand{\hra}{\hookrightarrow}
170\newcommand{\kr}{\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}{\left(
186        \begin{smallmatrix}#1&#2\\#3&#4\end{smallmatrix}\right)}
187\newcommand{\mthree}{\left(
188        \begin{matrix}#1&#2&#3\\#4&#5&#6\\#7&#8&#9
189        \end{matrix}\right)}
190\newcommand{\mtwo}{\left(
191        \begin{matrix}#1&#2\\#3&#4
192        \end{matrix}\right)}
193\newcommand{\vtwo}{\left(
194        \begin{matrix}#1\\#2
195        \end{matrix}\right)}
196\newcommand{\smallmtwo}{\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}
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}{\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}{%
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}{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}{\vspace{1ex}\noindent{\bf #1} }
372\newcommand{\nf}{\underline{#1}}
373\newcommand{\cbar}{\overline{c}}
375
376%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
377
378
379\makeindex
380
381\begin{document}
382\maketitle
383
384
385\hfill
386\begin{center}
388\end{center}
389The author grants permission to copy, distribute and/or modify this
390document under the terms of the GNU Free Documentation License,
392Foundation; with no Invariant Sections, no Front-Cover Texts, and no
393Back-Cover Texts.  A copy of the license is included in the Appendix.
394
395\hfill
396
397\tableofcontents
398
399\chapter*{Preface}
401
402This is a book about algorithms for computing with modular forms.  I
403am writing it for a Fall 2004 graduate course at Harvard University.
404This book is meant to answer the question How do {\em you} compute
405spaces $M_k(N,\eps)$ of modular forms'', which theoretical
406mathematicians often ask me, and to provide a rigorous foundation for
407the specific algorithms I use, some of which have until now never been
408formally stated or proven to be correct, except in my head while I
409typed them into a computer language.
410
411I have spent several years trying to find the best ways to compute
412with classical modular forms for congruence subgroups of $\SL_2(\Z)$,
413and have implemented most of these algorithms several times, first in
414C++ \cite{stein:hecke}, then in MAGMA \cite{magma}, and most recently
415in Python/C++ (see Chapter~\ref{ch:manin}).  Much of this work has
416involved turning formulas and constructions burried in books and
417papers into precise computable recipes, then testing these in many
418cases and eliminating subtle inaccuracies (published theorems often
419contain very small mistakes that are greatly magnified when
420implemented and run on a computer). The goal of this book is to
421explain what I have learned along the way, and also describe unsolved
422problems whose solution would move the theory forward.
423
424The author is aware of no other books on computing with modular forms,
425the closest work being Cremona's book \cite{cremona:algs}, which is
426about computing with elliptic curves, and Cohen's book
427\cite{cohen:course_ant} about algebraic number theory.  This field is
428not mature, and there are some missing details and potential
429improvements to many of the algorithms, which you the reader might
430fill in, and which would be greatly appreciated by other
431mathematicians.  Also, it seems that nobody has tried to analyze the
432formal complexity of any of the algorithms in this book (the author
433intends to do this as he writes the book) again this is somewhere
434you might contribute.
435
436This book focuses on how best to compute the spaces $M_k(N,\eps)$ of
437modular forms, where $k\geq 2$ is an integer and~$\eps$ is a Dirichlet
438character modulo~$N$.  I will spend the most effort explaining the
439algorithms that appear so far to be the best for such computations.
440I will not discuss computing half-integral weight forms,
441weight one forms, forms for non-congruence subgroups or groups other
442than $\GL_2$, Hilbert and Siegel modular forms, trace formulas, or
443$p$-adic modular forms.  I will also write very little about computing
444with modular abelian varieties.    These are topics for another book
445or two.
446
447The reader is not assumed to have prior exposure to modular forms, but
448should have a firm grasp of abstract algebra, and be familiar with
449algebraic number theory, geometry of curves, algebraic topology of
450Riemann surfaces, and complex analysis.  For Chapter~\ref{ch:manin},
451the reader should be familiar with the Python \cite{python}
452programming language.
453
455License, Version 1.2, November 2002.  This means that you may freely
456copy 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.}
468the algorithms in Chapter~\ref{ch:dirichlet}.
469{\bf Noam Elkies:} Remarks throughout chapters 1 and 2.
470The 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}
489This chapter follows parts of \cite[Ch.~VII]{serre:arithmetic}
490closely, though we adjust the notation, definitions, and order of
491presentation to be more in line with what we will do in the rest of the
492book.  Note that Serre writes $2k$ everywhere instead of~$k$, which
493may seem like a good idea if one is only interested in modular
494forms of level~$1$, since there are no nonzero level~$1$ forms of odd
495weight.
496
497\section{Basic Definitions}
498The complex upper half plane  $\h$ is equipped with
499an 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$$
503via linear fractional transformations.
504The \defn{modular group} is
505the subgroup $\SL_2(\Z)$ of $\SL_2(\R)$ of matrices
506with integer entries.  It acts on the upper half plane
507and has as fundamental domain the
508set~$D$ of elements of $\h$ that satisfy $|z|\geq 1$
509and $\Re(z)\leq 1/2$ (see \cite[\S{}VII.1]{serre:arithmetic}).
510Using this fundamental domain, one sees that $\SL_2(\Z)$
511is generated as a group by the matrices $S=\abcd{0}{-1}{1}{0}$
512and $T=\abcd{1}{1}{0}{1}$.
513
514\begin{definition}[Weakly Modular Function]
515A \defn{weakly modular function} of weight $k$ is a meromorphic
516function $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}
522Note that there are no modular forms of odd weight, since
523(\ref{eqn:modfunc}) implies $f(z) = (-1)^k f(z)$.
524When $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$$
527so the weight~$k$ differential form $f(z)dz^{k/2}$
528is fixed by $\SL_2(\Z)$.  Note also that the product
529of two weakly modular functions of weights $k_1$
530and $k_2$ is a weakly modular function of weight $k_1+k_2$.
531
532Since $\SL_2(\Z)$ is generated by $S$ and $T$, we can show
533that a meromorphic function $f$ is a weakly modular function
534by checking that
535\begin{equation}\label{eqn:modfunc2}
537\end{equation}
538
539
540Let $q=e^{2\pi i z}$.  Since $f(z+1)=f(z)$, there is a set-theoretic
541function $\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$$
545for
546some $m\in\Z$ and all~$q$ in a neighborhood of~$0$,
547we say that~$f$ is \defn{meromorphic at $\infty$}.  If
548also $m\geq 0$, then we say
549that~$f$ is \defn{holomorphic at  $\infty$}.
550
551\begin{definition}[Modular Function]
552A \defn{modular function} of weight~$k$ is a weakly modular function
553of weight~$k$ that is meromorphic at $\infty$.
554\end{definition}
555
556\begin{definition}[Modular Form]
557A \defn{modular form} of weight~$k$ is a modular function
558of weight~$k$ that is holomorphic on $\h$ and at $\infty$.
559\end{definition}
560
561If $f$ is a modular form, then there are complex numbers $a_n$
562such that
563$$564 f = \sum_{n=0}^{\infty} a_n q^n, 565$$
566and the above series converges for all $z\in\h$
567(since $f(q)$ is holomorphic on the punctured open unit
568disk, its Laurent series converges absolutely
569in the punctured open unit;
571for a bound on $|a_n|$).
572Also 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]
576A \defn{modular form} (of level 1) of weight~$k$ is a modular function
577of weight~$k$ that is holomorphic on $\h$ and at $\infty$.
578\end{definition}
579
580\begin{definition}[Cusp Form]
581A \defn{cusp form} (of level 1) of weight~$k$ is a modular form of
582weight~$k$ such that $f(\infty)=0$, i.e., $a_0=0$.
583\end{definition}
584
585If $f$ is a nonzero meromorphic function on $\h$
586and $w\in\h$, let
587$\ord_w(f)$ be the largest integer~$n$ such that
588$f/(w-z)^n$ is holomorphic at $w$.
589If $f = \sum_{n=m}^{\infty} a_n q^n$ with $a_m\neq 0$,
590let $\ord_{\infty}(f)=m$.  We will use the following
591theorem to give a presentation for the vector space
592of modular forms of weight~$k$, which will make it possible
593to computable a basis for that space.
594
595\begin{theorem}[Valence Formula]\label{thm:valence}
596Suppose $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$$
601where $\sum^*$ is the sum over elements of the fundamental
602domain~$D$ other than~$i$ or~$\rho$.
603\end{theorem}
604Serre proves this theorem in \cite[\S{}VII.3]{serre:arithmetic} using
605the residue theorem from complex analysis.  We will not prove it in
606this book.
607
608\section{Eisenstein Series and Delta}\label{sec:level_one_eisen}
609For an even integer $k\geq 4$, define the (not-normalized)
610\defn{weight~$k$ Eisenstein series}
611to be
612$$613 G_k(z) = \sum_{m,n\in\Z}^{*} \frac{1}{(mz+n)^k}, 614$$
615where the sum is over all $m,n\in\Z$ such that $mz+n\neq 0$.
616
617\begin{proposition}
618The function $G_k(z)$ is a modular form of weight~$k$.
619\end{proposition}
620See \cite[\S{} VII.2.3]{serre:arithmetic}, where he proves
621that $G_k(z)$ defines a holomorphic function on $\h\union\{\infty\}$.
622To 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$$
627and
628$$629G_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)$,
635where $\zeta$ is the Riemann zeta function.
636\end{proposition}
637\begin{proof}
638Taking the limit as $z\to i\infty$ in the definition
639of $G_k(z)$, we obtain $\sum^*_{n\in\Z} \frac{1}{n^k}$, since
640the terms involving $z$ all go to $0$ as $z\mapsto i\infty$.
641This sum is twice $\zeta(k) = \sum_{n\geq 1} \frac{1}{n^k}$.
642\end{proof}
643
644For example, one can show that
645$$G_4(\infty) = 2\zeta(4) = \frac{1}{3^2\cdot 5} \pi^4$$
646and
647$$G_6(\infty) = 2\zeta(6) = \frac{2}{3^3\cdot 5\cdot 7} \pi^6.$$
648
649
650Suppose $E=\C/\Lambda$ is an elliptic curve over $\C$, viewed as a quotient
651of $\C$ by a lattice $\Lambda=\Z\omega_1+\Z\omega_2$, with $\omega_1/\omega_2\in\h$.
652Then
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$$
657and
658$$659 (\wp')^2 = 4\wp^3 - 60 G_4(\omega_1/\omega_2) \wp - 140 G_6(\omega_1/\omega_2). 660$$
661The discriminant of the cubic $4x^3 - 60G_4(\omega_1/\omega_2) x - 662140 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$$
666is a cusp form of weight $12$.
667Since~$E$ is an elliptic curve, $\Delta(\omega_1/\omega_2)\neq 0$.
668
669\begin{proposition}\label{prop:qexpGk}
670For 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$$
675where $\sigma_d(n)$ is the sum of the $d$th powers of the divisors
676of~$n$.
677\end{proposition}
678For the proof, see \cite[\S VII.4]{serre:arithmetic}, which uses
679clever 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
685From a computational point of view, the $q$-expansion for $G_k$ from
686Proposition~\ref{prop:qexpGk} is unsatisfactory, because it involves
687transcendental numbers.  To understand more clearly what is going on,
688we 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}
693Expanding the power series on the left we have $$694\frac{x}{e^x - 1} = 6951 - \frac{x}{2} + \frac{x^2}{12} - \frac{x^4}{720} + \frac{x^6}{30240} 696- \frac{x^8}{1209600} + \cdots$$
697As this expansion suggests, the
698Bernoulli numbers $B_n$ with $n>1$ odd are~$0$ (see
699\exref{ch:levelone}{ex:odd_bernoulli}).
700Expanding 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 704B_{4}=-\frac{1}{30},\quad B_{6}=\frac{1}{42},\quad 705B_{8}=-\frac{1}{30},\quad$\vspace{1.5ex}
706
707\noindent{}$\ds 708B_{10}=\frac{5}{66},\quad 709B_{12}=-\frac{691}{2730},\quad 710B_{14}=\frac{7}{6},\quad 711B_{16}=-\frac{3617}{510},\quad 712B_{18}=\frac{43867}{798},\quad 713$\vspace{1.5ex}
714
715\noindent{}
716$\ds{}\!\!B_{20}=-\frac{174611}{330},\quad 717B_{22}=\frac{854513}{138},\quad 718B_{24}=-\frac{236364091}{2730},\quad 719B_{26}=\frac{8553103}{6}. 720%B_{28}=-\frac{23749461029}{870},\quad 721$\vspace{1ex}
722
723For us the significance of the Bernoulli numbers is their connection with
724values of $\zeta$ at positive even integers.
725\begin{proposition}\label{prop:zeta_even}
726If $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}
731The 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]
735The \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}
740Combining 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}
757Let $M_k$ denote the complex vector space of modular forms of weight~$k$,
758and let~$S_k$ denote the subspace of cusp forms.
759We have an exact sequence
760$$761 0 \to S_k \to M_k \to \C 762$$
763that sends $f\in M_k$ to $f(\infty)$.  When $k\geq 4$ is even,
764the space $M_k$ contains $G_k$ and $G_k(\infty)=2\zeta(k)\neq 0$,
765so the map $M_k\to \C$ is surjective, and $\dim(S_k)=\dim(M_k)-1$,
766so
767$$768 M_k = S_k \oplus \C G_k. 769$$
770
771\begin{proposition}\label{prop:mk_vanish}
772For $k<0$ and $k=2$, we have $M_k=0$.
773\end{proposition}
774\begin{proof}
775Suppose $f\in M_k$ is nonzero yet $k=2$ or $k<0$.  By
776Theorem~\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$$
781This is impossible because each quantity on the left-hand
782side 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}
787Multiplication by $\Delta$ defines an isomorphism $M_{k-12}\to S_k$.
788\end{theorem}
789\begin{proof}
791We apply Theorem~\ref{thm:valence} to $G_4$ and~$G_6$.
792If $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$$
797with the $\ord$s all nonnegative,
798so $\ord_{\rho}(G_4) = 1$ and $\ord_w(G_4) = 0$ for all $w\neq \rho$.
799Likewise $\ord_{i}(G_6) = 1$ and $\ord_w(G_6) = 0$ for all $w\neq i$.
800Thus $\Delta(i)\neq 0$, so $\Delta$ is not identically~$0$ (we
801also saw this above using the Weierstrass $\wp$ function).
802Since $\Delta$ has weight~$12$ and $\ord_\infty(\Delta)\geq 1$,
803Theorem~\ref{thm:valence} implies that~$\Delta$ has a simple
804zero at $\infty$ and does not vanish on~$\h$.
805Thus if $f\in S_k$ and we let $g=f/\Delta$, then $g$ is holomorphic
806and satisfies the appropriate transformation formula, so~$g$
807is 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$
832where $\lfloor{}x \rfloor{}$ is the biggest integer $\leq x$.
833\end{corollary}
834\begin{proof}
835As we have seen above, the formula is true when $k\leq 12$.
836By Theorem~\ref{thm:delta_iso}, the dimension increases by $1$
837when~$k$ is replaced by $k+12$.
838\end{proof}
839
840\begin{theorem}\label{thm:mk_one_basis}
841The space $M_k$ has as basis the
842modular forms $G_4^a G_6^b$, where $a,b$
843are all pairs of nonnegative integers such that
844$4a+6b=k$.
845\end{theorem}
846\begin{proof}
847We first prove by induction that the modular forms
848$G_4^a G_6^b$ generate $M_k$, the cases $k\leq 12$
849being clear (e.g., when $k=0$ we have $a=b=0$ and basis~$1$).
850Choose some pair of integers $a,b$ such that $4a+6b=k$
851(it is an elementary exercise to show these exist).
852The form $g=G_4^a G_6^b$ is not a cusp form, since
853it is nonzero at $\infty$.  Now suppose $f\in M_k$
854is arbitrary.  Since $M_k = S_k \oplus \C G_k$, there
855is $\alpha\in\C$ such that $f - \alpha g \in S_k$.
856Then by Theorem~\ref{thm:delta_iso}, there is $h \in M_{k-12}$
857such that $f - \alpha g = \Delta h$.  By induction,
858$h$ is a polynomial in $G_4$ and $G_6$ of the required
859type, and so is $\Delta$, so $f$ is as well.
860
861Suppose there is a nontrivial linear relation between the $G_4^a 862G_6^b$ for a given $k$.  By multiplying the linear relation by a
863suitable power of $G_4$ and $G_6$, we may assume that that we have
864such a nontrivial relation with $k\con 0\pmod{12}$.  Now divide the
865linear relation by $G_6^{k/12}$ to see that $G_4^3/G_6^2$ satisfies a
866polynomial with coefficients in $\C$.  Hence $G_4^3/G_6^2$ is a root
867of 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}
872Given integers~$n$ and~$k$, this algorithm computes
873a basis of $q$-expansions for the complex vector
874space $M_k$ mod $q^n$.   The $q$-expansions output
875by this algorithm have coefficients in $\Q$.
876\begin{steps}
877\item{}[Simple Case] If $k=0$ output the basis with
878just $1$ in it, and terminate; otherwise if $k<4$ or~$k$
879is odd, output the empty basis and terminate.
880\item{}[Power Series] Compute $E_4$ and $E_6$ mod $q^n$
881using the formula from (\ref{eqn:ekexp}) and
882the definition (\ref{eqn:def_bernoulli}) of Bernoulli
883numbers.
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$.
890If~$a$ is an integer, compute and output the basis
891element $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
894intermediate powers, so they can be reused later, and
895likewise for powers of $E_6$.
896\end{steps}
897\end{algorithm}
898\begin{proof}
899This is simply a translation of Theorem~\ref{thm:mk_one_basis}
900into an algorithm, since $E_k$ is a nonzero scalar multiple
901of $G_k$.  That the $q$-expansions have coefficients
902in $\Q$ is Equation~\ref{eqn:ekexp}.
903\end{proof}
904
905\begin{example}
906We compute a basis for $M_{24}$, which is the space with
907smallest weight whose dimension is bigger than $1$.
908It has as basis $E_4^6$, $E_4^3 E_6^2$, and $E_6^4$, whose explicit
909expansions are
910\begin{align*}
911  E_4^6 &= \frac{1}{191102976000000} +
912   \frac{1}{132710400000}q + \frac{203}{44236800000}q^2 + \cdots\\
913E_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
921In Section~\ref{sec:vmthesis}, we will discuss properties
922of the reduced row echelon form of any basis for $M_k$, which
923have better properties than the above basis.
924
925\section{Hecke Operators}\label{sec:hecke_one}
926Let $k$ be an integer.
927Define the weight~$k$ right action of $\GL_2(\Q)$ on
928functions~$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$$
932One checks as an exercise that
933$$934 f|[\gamma_1\gamma_2]_k = (f|[\gamma_1]_k)|[\gamma_2]_k, 935$$
936i.e., that this is a right group action.
937Also $f$ is a weakly modular function if $f$ is meromorphic
938and $f|[\gamma]_k = f$ for all $\gamma\in\SL_2(\Z)$.
939
940For any positive integer~$n$, let
941$$942S_n = \left\{\mtwo{a}{b}{0}{d} \in M_2(\Z) \,\,:\,\, 943a\geq 1,\,\, ad=n, \text{ and } 0\leq b <d\right\}. 944$$
945Note 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
948Hermite normal form (the analogue of reduced row
949echelon form over~$\Z$).
950
951
952\begin{definition}[Hecke Operator $T_{n,k}$]
953The~$n$th Hecke operator $T_{n,k}$ of weight~$k$
954is the operator on functions on $\h$ defined by
955$$956T_{n,k}(f) = \sum_{\gamma \in S_n} 957f|[\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}
969If $f$ is a weakly modular function of weight~$k$,
970so is $T_{n,k}(f)$, and if $f$ is also a modular
971function, then so is $T_{n,k}(f)$.
972\end{proposition}
973\begin{proof}
974Suppose $\gamma\in\SL_2(\Z)$.  Since~$\gamma$
975induces an automorphism of $\Z^2$, the set
976$$S_n \cdot \gamma = \{ \delta \gamma : \delta\in S_n\}$$
977is also in bijection with the sublattices
978of $\Z^2$ of index~$n$.
979Then for each element $\delta\gamma \in S_n\cdot \gamma$, there
980is $\sigma\in\SL_2(\Z)$ such that $\sigma\delta\gamma\in S_n$ (the
981element $\sigma$
982is the transformation of $\delta\gamma$ to Hermite normal form),
983and the set of elements $\sigma\delta\gamma$ is equal to $S_n$.
984Thus
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
991That $f$ being holomorphic on $\h$ implies $T_{n,k}(f)$ is holomorphic
992on $\h$ follows because each $f|[\gamma]_k$ is holomorphic on $\h$,
993and a finite sum of holomorphic functions is holomorphic.
994\end{proof}
995
996We will frequently drop $k$ from the notation in $T_{n,k}$, since
997the weight $k$ is implicit in the modular function to which
998we apply the Hecke operator.  Thus we henceforth make the
999convention that if we write $T_{n}(f)$ and~$f$ is modular,
1000then we mean $T_{n,k}(f)$, where~$k$ is the weight of~$f$.
1001
1002\begin{proposition}
1003On weight $k$ modular functions we have
1004\begin{equation}\label{eqn:hecke_mul}
1006 \text{if }(n,m)=1,
1007\end{equation}
1008and
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.
1033Using 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$
1054with $[\Z^2:L']=p$.
1055
1056The 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
1061structure of the set of chains $L\subset L'\subset\Z^2$ that we
1062derived in the previous paragraph gives the result.
1063\end{proof}
1064
1065\begin{corollary}
1066The Hecke operator $T_{p^n}$, for prime~$p$, is a polynomial in $T_p$.
1067If $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}
1076Emmanuel Kowalski made the following remark on the number theory lists
1077in June 2004 when asked about the polynomials $f_n(X)$ such
1078that $T_{p^n} = f_n(T_p)$.
1079\begin{quote}
1080If you normalize the Hecke operators by considering
1081$$1082 S_{n,k} = n^{-(k-1)/2} T_{n,k} 1083$$
1084then 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$$
1089which is the recursion satisfied by the Chebychev polynomials $U_r$ such
1090that
1091$$1092 U_r(2 \cos t) = \frac{\sin((r+1) t)}{ \sin(t)}. 1093$$
1094Alternatively, those give the characters of the symmetric powers of the
1095standard representation of $\SL_2(\R)$, evaluated on a rotation matrix
1096$$1097\mtwo{\cos(t)}{-\sin(t)}{\sin(t)}{\hfill \cos(t)}. 1098$$
1099For references, see for instance \cite[p.~97]{iwaniec:topics}
1100or \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}
1105Suppose $f = \sum_{n\in\Z} a_n q^n$ is a modular function
1106of weight~$k$.
1107Then
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$$
1113In 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$$
1117where $a_{m/p}=0$ if $m/p\not\in\Z$.
1118\end{proposition}
1119The proposition is not that difficult to prove (or at least the proof
1120is easy to follow), and is proved in \cite[\S
1121VII.5.3]{serre:arithmetic} by writing out $T_n(f)$ explicitly and
1122using that $\sum_{0\leq b<d} e^{2\pi i bm/d}$ is $d$ if $d\mid m$
1123and~$0$ otherwise.  A corollary of Proposition~\ref{prop:qexpTn} is
1124that $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}
1134Recall that
1135$$1136E_4 = \frac{1}{240} + q + 9q^2 + 28q^3 + 73q^4 + 126q^5 + 252q^6 + 344q^7 1137+\cdots. 1138$$
1139Using the formula of Proposition~\ref{prop:qexpTn}, we see
1140that
1141$$1142T_2(E_4) = (1/240 + 2^3\cdot (1/240)) + 9q + (73 + 2^3\cdot 1) q^2 + \cdots \\ 1143 = 9 E_4. 1144$$
1145Since $M_k$ has dimension $1$, and we have proved that $T_2$
1146preserves $M_k$, we know that $T_2$ acts as a scalar.  Thus
1147we know just from the constant coefficient of $T_2(E_4)$ that
1148$T_2(E_4) = 9 E_4$.
1149More 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$$
1153for 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}
1173The space $S_k$ has a basis $f_1,\ldots, f_{d}$ such
1174that 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
1176the $f_j$ all lie in $\Z[[q]]$.
1177\end{lemma}
1178This is a straightforward construction involving $E_4$, $E_6$
1179and $\Delta$.  The following proof is copied almost verbatim
1180from \cite[Ch.~X, Thm.~4.4]{lang:modular}, which is in turn
1181presumably copied from the first lemma of Victor Miller's
1182thesis.
1183\begin{proof}
1184Let $d=\dim S_k$.
1185Since $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$$
1193have $q$-expansions in $\Z[[q]]$ with leading
1194coefficient~$1$.
1195Choose integers $a,b\geq 0$ such that
1196$$1197 4a+6b\leq 14 \qquad\text{and}\qquad 4a + 6b \con k \pmod{12}, 1198$$
1199with $a=b=0$ when $k\con 0\pmod{12}$, and
1200let
1201$$1202 g_j = \Delta^j F_6^{2(d-j)+a} F_4^b,\qquad\qquad \text{for } j=1,\ldots,d. 1203$$
1204Then
1205$$1206 a_j(g_j) = 1, \qquad\text{and}\qquad a_i(g_j)=0\qquad\text{when}\qquad i<j. 1207$$
1208Hence the $g_j$ are linearly independent over $\C$, and thus form
1209a basis for $S_k$.  Since $F_4, F_6$, and $\Delta$ are all in $\Z[[q]]$,
1210so are the $g_j$.  The $f_i$ may then be constructed from the $g_j$
1211by 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}
1216The basis coming from Victor Miller's lemma is canonical,
1217since it is just the reduced row echelon form of any basis.
1218Also the {\em integral} linear combinations are precisely
1219the 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
1227Miller 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
1239We extend the Victor Miller basis to all $M_k$ by taking
1240a multiple of $G_k$ with constant term $1$, and subtracting
1241off the $f_i$ from the Victor Miller basis so that the
1242coefficients of $q, q^2, \ldots q^d$ of
1243the resulting expansion are $0$.  We call the extra basis
1244element $f_0$.
1245
1246
1247
1248
1249\begin{example}
1250If $k=24$, then $d=2$.  Choose $a=b=0$, since $k\con 0\pmod{12}$.
1251Then
1252$$g_1 = \Delta F_6^2 = 1253q - 1032q^2 + 245196q^3 + 10965568q^4 + 60177390q^5 - \cdots 1254$$
1255and
1256$$1257g_2 = \Delta^2 = q^2 - 48q^3 + 1080q^4 - 15040q^5 + \cdots 1258$$
1259We let $f_2=g_2$ and
1260$$1261f_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));
1267> F4 := n4*240;
1268> F4;
12691 + 240*q + 2160*q^2 + 6720*q^3 + 17520*q^4 + 30240*q^5 +
127060480*q^6 + 82560*q^7 + O(q^8)
1271> n6 := Newforms(MF(1,6));
1272> n6
1273> ';
1274
1275>> ';
1276     ^
1277User 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 +
128016808*q^7 + O(q^8)
1281> F6 := n6*(-504);
1282> F4;
12831 + 240*q + 2160*q^2 + 6720*q^3 + 17520*q^4 + 30240*q^5 +
128460480*q^6 + 82560*q^7 + O(q^8)
1285> F6;
12861 - 504*q - 16632*q^2 - 122976*q^3 - 532728*q^4 - 1575504*q^5 -
12874058208*q^6 - 8471232*q^7 + O(q^8)
1288> Delta := Newforms(CS(MF(1,12)));
1289> Delta;
1290q - 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;
1293q - 1032*q^2 + 245196*q^3 + 10965568*q^4 + 60177390*q^5 -
12941130921568*q^6 + 870123128*q^7 + O(q^8)
1295> Delta^2;
1296q^2 - 48*q^3 + 1080*q^4 - 15040*q^5 + 143820*q^6 - 985824*q^7 +
1297O(q^8)
1298> 1032*Delta^2 + Delta*F6^2;
1299q + 195660*q^3 + 12080128*q^4 + 44656110*q^5 - 982499328*q^6 -
1300147247240*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}
1313When $k=36$, the Victor Miller basis, including $f_0$, is
1314\begin{align*}
1315f_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 \\
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
1330implicit 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,
1339since the basis of $f_i$ are in reduced row echelon form.
1340I.e., the combinations are just the first few coefficients
1341of 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}
1360This is the Hecke operator $T_2$ on $M_{36}$:
1361$$1362\left( 1363\begin{matrix} 1364\hfill 34359738369&\hfill0&\hfill6218175600&\hfill9026867482214400\\ 13650&\hfill0&\hfill34416831456&\hfill5681332472832\\ 13660&\hfill1&\hfill194184&\hfill-197264484\\ 13670&\hfill0&\hfill-72&\hfill-54528\\ 1368\end{matrix}\right) 1369$$
1370It has characteristic polynomial
1371$$1372(x - 34359738369) \cdot 1373(x^3 - 139656x^2 - 59208339456x - 1467625047588864), 1374$$
1375where the cubic factor is irreducible.
1376\end{example}
1377
1378\begin{conjecture}[Maeda]
1379The characteristic polynomial of $T_2$ on $S_k$ is irreducible for any~$k$.
1380\end{conjecture}
1381
1382Kevin Buzzard even observed that in many specific cases the Galois
1383group of the characteristic polynomial of $T_2$ is the full symmetric group
1385evidence 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?}
1399Let
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*}
1408be the $\Delta$-function.
1409\begin{conjecture}[Edixhoven]
1410There is an algorithm to compute $\tau(p)$, for prime $p$, that
1411is polynomial-time in the number of digits of~$p$.
1412\end{conjecture}
1413Bas Edixhoven and his students have been working intensely for years
1414to apply sophisticated techniques from arithmetic geometry (e.g.,
1415\'etale cohomology, motives, Arakelov theory) in order to prove that
1416such an algorithm exists (among other things), and he believes they
1417are almost there.  There is evidently a significant gap between
1418proving {\em existence} of an algorithm that shold be polynomial time,
1419and actually writing down such an algorithm with explicitly bounded
1420running times.  The ideas Edixhoven uses are very similar to the ones
1421used for counting points on elliptic curves in polynomial time (the
1422algorithm 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
1437Fix 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
1441is 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}
1449We denote the group of such Dirichlet characters by $D(N,R,\zeta)$, or
1450by just $D(N,R)$, when the choice of $\zeta$ is clear.  It follows
1451immediately from the definition that elements of
1452$D(N,R)$ are in bijection with  homomorphisms $(\Z/N\Z)^* \to 1453\langle \zeta \rangle$.
1454
1455In this chapter we develop a systematic theory for computing
1456with Dirichlet characters.   These will be extremely important
1457everywhere in the rest of this book, when we compute with
1458spaces $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$$
1464For example, Eisenstein series in $M_k(\Gamma_1(N))$ are associated
1465to 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
1467decomposes as a direct sum
1468$$1469 M_k(\Gamma_1(N)) = \bigoplus_{\eps\in D(N,\C)} M_k(\Gamma_1(N))(\eps). 1470$$
1471Each space $M_k(\Gamma_1(N))(\eps)$ is frequently much easier
1472to compute with than the full $M_k(\Gamma_1(N))$.
1473For 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}
1479If
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$$
1485then $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}
1503We have $\#D(N,R) \mid \vphi(N)$, with equality
1504if and only if the order of our choice of $\zeta\in R$
1505is a multiple of the exponent of the group $(\Z/N\Z)^*$.
1506\end{corollary}
1507
1508\begin{example}
1509The group $D(5,\C)$ has elements
1510$\{, [i], [-1], [-i]\}$,
1511so is cyclic of order $\vphi(5)=4$.
1512In contrast,  the group $D(5,\Q)$ has only the
1513two elements $$ and $[-1]$ and order $2$.
1514\end{example}
1515
1516Fix a positive integer~$N$, and write $N=\prod_{i=1}^{n} {p_i^{e_i}}$
1517where $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
1519cyclic group $C_i=\langle g_i \rangle$, except if $p_1=2$ and $e_1\geq 15203$, in which case $(\Z/p_1^{e_1}\Z)^*$ is a product of the cyclic
1521subgroup $C_0 = \langle -1 \rangle$ of order $2$ with the cyclic
1522subgroup $C_1 = \langle 5\rangle$.  In all
1523cases 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$$
1526For~$i$ such that $p_i>2$, choose the generator $g_i$ of $C_i$ to be
1527the element of $\{2,3,\ldots, p_i^{e_i}-1\}$ that is smallest and
1528generates.  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}$
1531for $j\neq i$.
1532
1533\begin{algorithm}{Minimal generator for $(\Z/p^r\Z)^*$}\label{alg:mingens}
1534Given an odd prime power $p^r$, this algorithm computes
1535a 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}.
1547If no powers are $1$, output $g$ and terminate.
1548\end{steps}
1549\end{algorithm}
1550For the proof, see \exref{ch:dirichlet}{ex:orderalg}.
1551
1552\begin{example}
1553A minimal generator for $(\Z/49\Z)^*$ is $3$.
1554We 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$$
1558so $2$ is not a generator for $(\Z/49\Z)^*$.  (We see
1559this 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}
1566In this example
1567we compute minimal generators for $N=25$, $100$, and $200$:
1568\begin{enumerate}
1569\item
1570The minimal generator for $(\Z/25\Z)^*$ is $2$.
1571
1572\item
1573Minimal generators for $(\Z/100\Z)^*$, lifted
1574to numbers modulo $100$, are $g_0=51$, $g_1=1$ and $g_2=77$.
1575Notice 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
1579Minimal generators for $(\Z/200\Z)^*$, lifted
1580to numbers modulo $200$, are
1581$g_0 = 151$, $g_1 = 101$, and $g_2=177$.  Note
1582that $g_0\con -1\pmod{4}$, that $g_1\con 5\pmod{8}$,
1583and $g_2\con 2\pmod{25}$.
1584\end{enumerate}
1585\end{example}
1586
1587Fix an element~$\zeta$ of finite multiplicative order in a ring~$R$,
1588and let $D(N,R)$ denote the group of Dirichlet characters modulo~$N$
1589over~$R$, with image in $\langle \zeta\rangle \union \{0\}$.  We
1590specify 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}
1594of images of the generators of $(\Z/N\Z)^*$.  (Note if $N$ is even,
1595the number of elements of the list (\ref{eqn:epslist}) does {\em not}
1596depend on whether or not $8\mid N$---there are always two factors
1597corresponding to $2$.)  This representation completely
1598determines~$\eps$ and is convenient for arithmetic operations with
1599Dirichlet characters.  It is analogous to representing a linear
1600transformation by a matrix.  See Section~\ref{sec:alter_rep} for
1601a discussion of alternative ways to represent Dirichlet characters.
1602
1603
1604\begin{example}\label{ex:char}
1605If $N=200$, then $g_0=151$, $g_1=101$ and $g_2=177$, as
1606we saw in Example~\ref{ex:mingens}.  The
1607exponent of $(\Z/200\Z)^*$ is $20$, since that
1608is the least common multiple of the exponents of
1609$4=\#(\Z/8\Z)^*$ and $20=\#(\Z/25\Z)^*$.
1610The orders of $g_0$, $g_1$ and $g_2$ are $2$, $2$, and $20$.
1611Let $\zeta=\zeta_{20}$ be a primitive $20$th root of
1612unity in $\C$.  Then the following are generators
1613for $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$$
1619and $\eps=[1,-1,\zeta^5]$ is an example element of order~$4$.
1620To evaluate $\eps(3)$, we write~$3$ in
1621terms of $g_0$, $g_1$, and $g_2$.
1622First, reducing $3$ modulo~$8$, we see that
1623$3 \con g_0 \cdot g_1\pmod{8}$.  Next
1624reducing $3$ modulo $25$, and trying powers of
1625$g_2=2$, we find that $e\con g_2^7\pmod{25}$.
1626Thus
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
1635Example~\ref{ex:char} illustrates that if~$\eps$ is represented using
1636a list as described above, evaluation of~$\eps$ on an arbitrary
1637integer is inefficient without extra information; it requires solving
1638the discrete log problem in $(\Z/N\Z)^*$.  In fact, for a general
1639character~$\eps$ calculation of~$\eps$ will probably be at least as
1640hard as finding discrete logarithms no matter what representation we
1641use (quadratic characters are easier---see Algorithm~\ref{alg:kronecker}).
1642\begin{algorithm}{Evaluate $\eps$}\label{alg:eval_eps}
1643Given a Dirichlet character $\eps$ modulo~$N$, represented
1644by a list $[\eps(g_0), \eps(g_1), \ldots, \eps(g_n)]$,
1645and 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}
1658By \exref{ch:dirichlet}{ex:dlogadd} we have an isomorphism
1659of groups
1660$$1661(1+p^{n-1}(\Z/p^n\Z),\,\times) \isom (\Z/p\Z,\,+), 1662$$
1663so one sees by
1664induction that Step~\ref{step:eval_fb} is about as difficult'' as finding a
1665discrete log in $(\Z/p\Z)^*$.  There is an algorithm called
1666baby-step giant-step'', which solves the discrete log problem in
1667$(\Z/p\Z)^*$ in time $O(\sqrt{\ell})$,
1668where $\ell$ is the largest prime factor of $p-1=\#(\Z/p\Z)^*$
1669(note that the discrete log problem in $(\Z/p\Z)^*$ reduces
1670to a series of discrete log problems in each prime order cyclic
1671factor).
1672This is unfortunately still
1673exponential in the number of digits of~$\ell$.
1674\begin{algorithm}{Baby-Step Giant Step Discrete Log}
1675\label{alg:baby_giant_dlog}
1676Given a prime $p$, a generator $g$ of $(\Z/p\Z)^*$,
1677and an element $a\in (\Z/p\Z)^*$, this algorithm
1678finds an $n$ such that $g^n=a$.
1679(Note that this algorithm works in any cyclic group,
1680not just $(\Z/p\Z)^*$.)
1681\begin{steps}
1682\item{}[Make Lists]
1683Let $m=\lceil{} \sqrt{p}\rceil{}$ be the ceiling of $\sqrt{p}$,
1684and
1685construct two lists $$1686g,\, g^m,\, \ldots, \,g^{(m-1)m}, g^{m^2} 1687\qquad\qquad\text{(giant steps)}$$
1688and
1689$$1690ag,\, ag^2,\, \ldots, \, 1691ag^{m-1}, ag^m \qquad\qquad\text{(baby steps)}. 1692$$
1693\item{}[Find Match]\label{step:find_match}
1694Sort the two lists and
1695find 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
1705$(\Z/p\Z)^*$, so it works in a generic group.  It is a theorem that
1706there is no faster algorithm to find discrete logs in a generic
1707group'' (see \cite{shoup:lower,nechaev:lower}).  Fortunately there are
1708much better subexponential algorithms for solving the discrete log
1709problem in $(\Z/p\Z)^*$, which use the special structure of this group.
1710They use the number field sieve (see e.g., \cite{gordon:dlog}), which
1711is also the best known algorithm for factoring integers.  This class
1712of algorithms has been very well studied by cryptographers; though
1713sub-exponential, solving discrete log problems when $p$ is large is
1714still 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;
173154580*U.1
1732Time: 0.000
1733> G := Integers(NextPrime(10^6)); U,f := UnitGroup(G);
1734> time 100@@f;
1735584760*U.1
1736Time: 0.020
1737> G := Integers(NextPrime(10^7)); U,f := UnitGroup(G);
1738> time 100@@f;
17399305132*U.1
1740Time: 0.320
1741> G := Integers(NextPrime(10^8)); U,f := UnitGroup(G);
1742> time 100@@f;
174383605942*U.1
1744Time: 2.940
1745> G := Integers(NextPrime(10^9)); U,f := UnitGroup(G);
1746> time 100@@f;
1747763676566*U.1
1748Time: 27.780
1749> G := Integers(NextPrime(10^10)); U,f := UnitGroup(G);
1750> time 100@@f;
17518121975284*U.1
1752Time: 3150.470
1753\end{verbatim}
1754Currently the {\em right} way to request computation of a discrete
1755logarithm in MAGMA is to use the {\tt Log} command.  Using this
1756command 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);
176054580
1761Time: 0.000
1762> p := NextPrime(10^8); k := GF(p); a := k!PrimitiveRoot(p);
1763> time Log(k!a, k!100);
176483605942
1765Time: 0.000
1766> p := NextPrime(10^12); k := GF(p); a := k!PrimitiveRoot(p);
1767> time Log(k!a, k!100);
1768837165108486
1769Time: 0.000
1770> p := NextPrime(10^15); k := GF(p); a := k!PrimitiveRoot(p);
1771> time Log(k!a, k!100);
1772543584576740840
1773Time: 0.060
1774> p := NextPrime(10^20); k := GF(p); a := k!PrimitiveRoot(p);
1775> time Log(k!a, k!100);
177655635183831704631320
1777Time: 0.210
1778> p := NextPrime(10^25); k := GF(p); a := k!PrimitiveRoot(p);
1779> time Log(k!a, k!100);
17808669816947492932609764592
1781Time: 0.480
1782> p := NextPrime(10^35); k := GF(p); a := k!PrimitiveRoot(p);
1783> time Log(k!a, k!100);
178428138566543929117345335749648530454
1785Time: 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);
179423346611965343882546546326674895020
1795Time: 4.940
1796\end{verbatim}
1797Thus one can deal with primes having around $35$ digits in a few seconds.
1798Moral: Having an understanding of the theoretical complexity of
1799an algorithm, is much better than just some timing with an implementation,
1800becuause you might unwittingly misuse the implementation.
1801\end{example}
1802
1803
1804The specific applications of Dirichlet characters in this book involve
1805computing modular forms, and for these applications~$N$ will be fairly
1806small, e.g., $N<10^6$.  Also we will evaluate~$\eps$ on a {\em huge}
1807number of random elements, inside inner loops of algorithms.  Thus for
1808our purposes it will often be better to make a table of all values
1809of~$\eps$, so that evaluation of~$\eps$ is extremely fast.  The
1810following algorithm computes a table of all values of $\eps$, and it
1811does not require computing any discrete logs since we are computing
1812{\em all} values.
1813
1814\begin{algorithm}{Values of $\eps$}
1815Given a Dirichlet character $\eps$ represented by the list
1816of values of $\eps$ on the minimal generators $g_i$ of $(\Z/N\Z)^*$, this algorithm
1817creates 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$
1829and terminate.
1830\item{}[Increment] Set $a_0\set a_0 + 1$, $n\set n\cdot g_0\pmod{N}$,
1831and $z\set z\cdot \eps(g_0)$.  If $a_0\geq \ord(g_0)$, set $a_0\to 0$,
1832then 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
1834did 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
1853Frequently people describe quadratic characters in terms of the
1854Kronecker symbol. The following algorithm gives a way to go between
1855the 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)^*$
1862using Algorithm~\ref{alg:mingens}.
1863\item Compute $\kr{g_i}{N}$ for each $g_i$ using one
1864of 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}
1883We compute the Dirichlet character associated to the
1884Kronecker symbol $\kr{a}{200}$. Using PARI, we
1885find 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)
18901
1891? kronecker(101,200)
1892-1
1893? kronecker(177,200)
18941
1895\end{verbatim}
1896Thus 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
1906\end{remark}
1907
1908
1909\begin{example}
1910We compute the character associated to $\kr{a}{420}$.
1911We have $420=4\cdot 3\cdot 5\cdot 7$, and minimal generators
1912are
1913$$1914 g_0 = 211,\quad g_1=1, \quad g_2 = 281, \quad g_3=337, \quad g_4=241. 1915$$
1916We have $g_0\con -1\pmod{4}$, $g_2\con 2\pmod{3}$, $g_3\con 2\pmod{5}$
1917and $g_4\con 3\pmod{7}$.
1918Using PARI again we find $\kr{g_0}{420}=\kr{g_1}{420}=1$
1919and $\kr{g_2}{420}=\kr{g_3}{420}=\kr{g_4}{420}=-1$, so the
1920corresponding character is $[1,1,-1,-1,-1]$.
1921\end{example}
1922
1923\section{Algorithms}
1924
1925The following algorithm for computing the order of~$\eps$ reduces
1926the 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
1947The next algorithm factors $\eps$ as a product of local'' characters,
1948one for each prime divisor of $N$.  It is useful for other algorithms,
1949and also for explicit computations with the Hijikita trace formula
1950(see \cite{hijikata:trace}). This factorization is easy to compute
1951because of how we represent $\eps$.
1952
1953\begin{algorithm}{Factorization of Character}\label{alg:dirfac}
1954Given a Dirichlet character $\eps\in D(N,R)$, with $N=\prod p_i^{e_i}$,
1955this algorithm finds Dirichlet characters $\eps_i$ modulo $p_i^{e_i}$, such
1956that for all $a\in(\Z/N\Z)^*$, we have
1957$\eps(a) = \prod \eps_i(a\!\!\pmod{p_i^{e_i}})$.
1958If $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$
1961is 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)$
1963defined 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
1965by the list $[\eps(g_0), \eps(g_1)]$ of length~$2$.   Output the
1966$\eps_i$ and terminate.
1967\end{steps}
1968If $2\nmid N$, then omit Step~\ref{step:extra2}, and include
1969all $i$ in Step~\ref{step:singletons}.
1970\end{algorithm}
1971The 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}
1978If $\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]
1985The \defn{conductor} of a Dirichlet character $\eps\in D(N,R)$
1986is the smallest positive divisor $c\mid N$ such that
1987there is a character $\eps' \in D(c,R)$ for which
1988$\eps(a) = \eps'(a)$ for all $a\in\Z$ with $(a,N)=1$.
1989A Dirichlet character is \defn{primitive} if its modulus equals
1990its conductor.  The character $\eps'$ associated to~$\eps$
1991with modulus equal to the conductor of~$\eps$ is called
1992the \defn{primitive character associated to}~$\eps$.
1993\end{definition}
1994We will be interested in conductors later, when computing new
1995subspaces of spaces of modular forms with character.  Also certain
1996formulas for special values of~$L$ functions are only valid for
1997primitive 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}
2008For each $i$, either set $c_i\to 1$ if $\eps_i$
2009is 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}
2018Let $\eps_i$ be the local factors of~$\eps$, as in Step~\ref{step:factor_dir}.
2019We first show that the product of the conductors $f_i$ of the $\eps_i$ is
2020the conductor~$f$ of~$\eps$.  Since $\eps_i$ factors through $(\Z/f_i\Z)^*$,
2021the product~$\eps$ of the $\eps_i$ factors through $(\Z/\prod f_i\Z)^*$,
2022so 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$
2024as a product of local (prime power) characters differently, which contradicts
2025that this factorization is unique.
2026
2027It 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
2029conductor of~$\eps$ is $p^{\ord_p(r)+1}$, except possibly if $8\mid 2030p^n$.  Since the order and conductor of $\eps$ and of the associated
2031primitive character $\eps'$ are the same, we may assume $\eps$ is
2032primitive, 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
2044First suppose $p$ is odd.
2045Then the abelian group $D(p^n,R)$ splits as a direct sum $D(p,R)\oplus D(p^n,R)'$,
2046where $D(p^n,R)'$ is the $p$-power torsion subgroup of $D(p^n,R)$.
2047Also $\eps$ has order $u\cdot p^m$, where $u$, which
2048is coprime to~$p$, is the order of the image of $\eps$
2049in $D(p,R)$ and $p^m$ is the order of the image in $D(p^n,R)'$.
2050If $m=0$, then the order of $\eps$ is coprime to $p$, so
2051$\eps$ is in $D(p,R)$, which means that $n=1$,
2052so $n=m+1$, as required.  If $m>0$, then $\zeta\in R$
2053must have order divisible by $p$, so~$R$ has characteristic not
2054equal to~$p$.  The conductor of $\eps$ does not change if we
2055adjoin roots of unity to~$R$, so in light of Lemma~\ref{lem:dual}
2056we may assume that $D(N,R) \ncisom (\Z/N\Z)^*$.
2057It 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
2059subgroup of $D(p^n,R)'$.   Thus $m=n-1$, since
2060$D(p^n,R)'$ is by assumption the smallest such group that
2061contains the projection of~$\eps$.  This proves the
2062formula of Step~\ref{step:cond_fac}.   We leave the argument
2063when $p=2$ as an exercise (see \exref{ch:dirichlet}{ex:cond2}).
2064\end{proof}
2065
2066\begin{example}\label{ex:char_cond}
2067If $\eps = [1,-1,\zeta^5] \in D(200,\C)$, then
2068as we saw in Example~\ref{ex:prodlocal},~$\eps$
2069is the product of $\eps_1=[1,-1]$ and $\eps_2 = [\zeta^5]$.
2070Because $\eps_1(5)=-1$, the conductor of $\eps_1$ is $8$.
2071The order of $\eps_2$ is $4$ (since $\zeta$ is a $20$th
2072root of unity), so the conductor of $\eps_2$ is $5$.
2073Thus the conductor of~$\eps$ is $40=8\cdot 5$.
2074\end{example}
2075
2076The following two algorithms restrict and extend characters to a
2077compatible modulus.  Using them it is easy to define multiplication of
2078two 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
2080multiplication, just extend bother characters to characters modulo
2081$\lcm(N,N')$, then multiply.
2082
2083\begin{algorithm}{Restriction of Character}\label{alg:restrict}
2084Given a Dirichlet character $\eps\in D(N,R)$ and a divisor
2085$N'$ of $N$ that is a multiple of the conductor of $\eps$,
2086this algorithm finds a characters $\eps' \in D(N',R)$, such
2087that $\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}
2102The only part that is not clear is that in Step~\ref{step:addmod}
2103there is an $a$ such that $(g_i+aN', N)=1$.  If
2104we write $N=N_1\cdot N_2$, with $(N_1,N_2)=1$, and $N_1$ divisible
2105by all primes that divide $N'$, then $(g_i,N_1)=1$ since
2106$(g_i,N')=1$.  By the Chinese Remainder Theorem,
2107there 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'$
2109and $(x,N)=1$, which completes the proof.
2110\end{proof}
2111
2112
2113\begin{algorithm}{Extension of Character}\label{alg:extend}
2114Given a Dirichlet character $\eps\in D(N,R)$ and a multiple
2115$N'$ of $N$,
2116this algorithm finds a characters $\eps' \in D(N',R)$, such
2117that $\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$,
2122we also have $(g_i,N)=1$.
2123\item{}[Output Character] Output the character defined by
2124\$[\eps