Sharedwww / talks / 2005-08-03-sdsc / sdsc.texOpen in CoCalc
Author: William A. Stein
1
\documentclass[landscape]{slides}
2
\usepackage{fullpage}
3
\usepackage[hypertex]{hyperref}
4
\usepackage{amsmath}
5
\newcommand{\abcd}[4]{\left(
6
\begin{smallmatrix}#1&#2\\#3&#4\end{smallmatrix}\right)}
7
\newcommand{\eps}[4]{\rput[lb](#1,#2){%
8
\includegraphics[width=#3\textwidth]{#4}}}
9
10
\newcommand{\ds}{\displaystyle}
11
12
\usepackage{fancybox}
13
\usepackage{graphicx}
14
15
\usepackage{pstricks}
16
\newrgbcolor{dbluecolor}{0 0 0.6}
17
\newrgbcolor{dredcolor}{0.5 0 0}
18
\newrgbcolor{dgreencolor}{0 0.4 0}
19
\newcommand{\dred}{\dredcolor\bf}
20
\newcommand{\dblue}{\dbluecolor\bf}
21
\newcommand{\dgreen}{\dgreencolor\bf}
22
\newcommand{\hd}[1]{\begin{center}\LARGE\bf\dblue #1\vspace{-2.5ex}\end{center}}
23
\newcommand{\rd}[1]{{\bf \dred #1}}
24
\newcommand{\gr}[1]{{\bf \dgreen #1}}
25
\newcommand{\defn}[1]{{\bf \dblue #1}}
26
27
\newcommand{\Q}{\mathbf{Q}}
28
29
\author{\rd{William A. Stein}\\
30
Associate Professor of Mathematics\\
31
University of California, San Diego}
32
\date{\rd{San Diego Supercomputing Center: August 3, 2005}}
33
%\include{macros}
34
35
\setlength{\fboxsep}{1em}
36
\setlength{\parindent}{0cm}
37
38
\newcommand{\page}[1]{\begin{slide}#1\vfill\end{slide}}
39
%\renewcommand{\page}[1]{}
40
\newcommand{\apage}[1]{\begin{slide}#1\vfill\end{slide}}
41
\newcommand{\heading}[1]{\begin{center} \Large \dblue #1 \end{center}}
42
43
\title{\blue \bf An Introduction to the\\Modular Forms Database Project:\\
44
{\large My
45
Dream Computation (not a toy problem!)}}
46
47
\begin{document}
48
\page{
49
\maketitle
50
}
51
52
\page{
53
\heading{The Pythagorean Theorem}
54
\psset{unit=3.0}
55
\pspicture(0,0)(4,3)
56
\psline[linecolor=blue, linewidth=0.06](0,0)(4,0)
57
\psline[linecolor=blue, linewidth=0.06](4,0)(4,3)
58
\psline[linecolor=blue, linewidth=0.06](4,3)(0,0)
59
\rput(2.6,0.8){{\LARGE $a^2+b^2=c^2$}}
60
\rput(1.9,1.8){{\LARGE $c$}}
61
\rput(4.3,1.3){{\LARGE $a$}}
62
\rput(2.2,-0.35){{\LARGE $b$}}
63
\rput(6,1.5){\includegraphics{pics/pythagoras15}}
64
\rput[cb](6.0,-0.35){Pythagoras}
65
\rput[cb](6.0,-0.6){Approx 569--475BC}
66
\endpspicture
67
}
68
69
70
\page{
71
\heading{Pythagorean Triples}
72
\psset{unit=1.0}
73
\pspicture(0,0)(10,12)
74
\rput[lb](5,1.5){\includegraphics[width=0.65\textwidth]{pics/plimpton2}}
75
\rput[lb](18,12.5){\includegraphics[width=0.1\textwidth]{pics/tower}}
76
\rput[lb](5,0.7){Triples of integers $a,b,c$ such that}
77
\rput[lb](9,-0.5){{\Large $a^2+b^2=c^2$}}
78
\rput[lb](0,0){{$\begin{array}{|c|}\hline
79
\vspace{-2ex}\\
80
( 3, 4, 5 )\\
81
( 5, 12, 13 )\\
82
( 7, 24, 25 )\\
83
( 9, 40, 41 )\\
84
( 11, 60, 61 )\\
85
( 13, 84, 85 )\\
86
( 15, 8, 17 )\\
87
( 21, 20, 29 )\\
88
( 33, 56, 65 )\\
89
( 35, 12, 37 )\\
90
( 39, 80, 89 )\\
91
( 45, 28, 53 )\\
92
( 55, 48, 73 )\\
93
( 63, 16, 65 )\\
94
( 65, 72, 97 )\\
95
( 77, 36, 85 )
96
\vspace{-1ex}\\\vdots \\
97
\hline
98
\end{array}
99
$}}
100
\endpspicture
101
} % end page
102
103
104
\page{
105
\heading{Enumerating Pythagorean Triples}
106
107
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
108
% Graph: param
109
%% (Contact: William Stein, http://modular.fas.harvard.edu)
110
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
111
\psset{unit=4.0}
112
\pspicture(-1.300,-1.200)(1.300,1.300)
113
\newrgbcolor{mycolor}{0.00 0.00 0.00}\mycolor
114
%RGB color (0.40000000000000002, 0.40000000000000002, 0.40000000000000002)
115
\newrgbcolor{mycolor}{0.40 0.40 0.40}\mycolor
116
117
%linewidth = 0.02
118
\psset{linewidth=0.02}
119
%- axes
120
\psline[linecolor=mycolor]{->}(-1.300,0.000)(1.300,0.000)
121
\rput[lb](1.600,0.000){}
122
\psline[linecolor=mycolor]{->}(0.000,-1.200)(0.000,1.300)
123
\rput[lb](0.000,1.600){}
124
125
%linewidth = 0.03
126
\psset{linewidth=0.03}
127
%RGB color (0.10000000000000001, 0.10000000000000001, 1.0)
128
\newrgbcolor{mycolor}{0.10 0.10 1.00}\mycolor
129
130
%Circle at (0, 0) of radius 1
131
\pscircle[linecolor=mycolor](0, 0){1}
132
%RGB color (1.0, 0.0, 0.0)
133
\newrgbcolor{mycolor}{1.00 0.00 0.00}\mycolor
134
135
%Line from (-1.5, -0.25) to (1.2, 1.1000000000000001)
136
\psline[linecolor=mycolor]{<->}(-1.5, -0.25)(1.2, 1.1000000000000001)
137
%RGB color (0.0, 0.0, 0.0)
138
\newrgbcolor{mycolor}{0.00 0.00 0.00}\mycolor
139
140
%Solid dot at (-1.000,0.000) of radius 0.05
141
\pscircle*[linecolor=mycolor](-1.000,0.000){0.050}
142
%Solid dot at (0.000,0.500) of radius 0.05
143
\pscircle*[linecolor=mycolor](0.000,0.500){0.050}
144
%Solid dot at (0.000,0.500) of radius 0.05
145
\pscircle*[linecolor=mycolor](0.000,0.500){0.050}
146
%RGB color (0.10000000000000001, 1.0, 0.10000000000000001)
147
\newrgbcolor{mycolor}{0.10 1.00 0.10}\mycolor
148
149
%Solid dot at (0.580,0.800) of radius 0.08
150
\pscircle*[linecolor=mycolor](0.580,0.800){0.080}
151
%RGB color (0.0, 0.0, 0.0)
152
\newrgbcolor{mycolor}{0.00 0.00 0.00}\mycolor
153
154
\rput[lb](-1.59, 0.050000000000000003){{$(-1,0)$}}
155
\rput[lb](0.1, 0.34999999999999998){{$(0,t)$}}
156
\rput[lb](0.4, 0.95){{$(x,y)$}}
157
158
\rput[lb](2,-0.5){$\begin{array}{rl}
159
\ds{\rm Slope} \,=\, t&\ds=\quad\! \frac{y}{x+1}\vspace{2.5ex}\\
160
\ds x &=\quad\! \ds\frac{1-t^2}{1+t^2}\vspace{2.5ex}\\
161
\ds y &=\quad\! \ds\frac{2t}{1+t^2}\\
162
\end{array}$
163
}
164
165
\rput[lb](-1.3,-1.5){If $t=\frac{r}{s}$, then
166
$\dgreencolor \qquad a=s^2-r^2, \quad b=2rs, \quad c=s^2+r^2$}
167
\rput[lb](-1.3,-1.7){is a Pythagorean triple, and all primitive
168
unordered triples}
169
\rput[lb](-1.3,-1.9){arise in this way.}
170
171
\endpspicture
172
} % end page
173
174
\page{
175
\heading{Fermat's ``Last Theorem''\hspace{3em}\mbox{}}
176
No ``Pythagorean triples'' with exponent $3$ or higher.
177
178
\psset{unit=1.0}
179
\pspicture(-3,0)(10,12)
180
\eps{0}{-1}{0.4}{pics/diophantus1}
181
\eps{10}{-1}{0.28}{pics/diophantus2}
182
\eps{10}{4}{0.26}{pics/wiles_diophantus}
183
\eps{14.7}{13.7}{0.2}{pics/fermat3}
184
\endpspicture
185
} % end page
186
187
188
\page{
189
\heading{\large Wiles's Proof of FLT Uses Elliptic Curves}
190
\vspace{-3ex}
191
{\large An {\dred elliptic curve} is a nonsingular plane cubic curve with
192
a rational point (possibly ``at infinity'').}
193
\vspace{1ex}
194
195
\psset{unit=1.75}
196
\pspicture(-2.000,-3.000)(2.000,2.000)
197
\newrgbcolor{mycolor}{0.00 0.00 0.00}\mycolor
198
%RGB color (0.69999999999999996, 0.69999999999999996, 0.69999999999999996)
199
\newrgbcolor{mycolor}{0.70 0.70 0.70}\mycolor
200
%Grid divided into 2 subdivisions
201
\newrgbcolor{glc}{0.00 0.00 0.00}
202
\psgrid[gridcolor=mycolor, subgriddiv=2, gridlabelcolor=glc]
203
204
205
%RGB color (0.20000000000000001, 0.20000000000000001, 0.20000000000000001)
206
\newrgbcolor{mycolor}{0.20 0.20 0.20}\mycolor
207
208
%linewidth = 0.02
209
\psset{linewidth=0.02}
210
%$x$-$y$ axes
211
\psline[linecolor=mycolor]{->}(-2.000,0.000)(2.000,0.000)
212
\psline[linecolor=mycolor]{->}(0.000,-3.000)(0.000,2.000)
213
\newrgbcolor{mycolor}{0.00 0.00 0.00}\mycolor
214
215
\rput[lb](2.1,2.6){{\large $\infty$}}
216
\newrgbcolor{mycolor}{0.00 0.00 1.00}\mycolor
217
\pscircle*[linecolor=mycolor](2.0,2.6){0.05}
218
\newrgbcolor{mycolor}{0.00 0.00 0.00}\mycolor
219
\mycolor
220
\rput[lb](2.150,0.000){{\Large $x$}}
221
\rput[lb](0.000,2.150){{\Large $y$}}
222
\newrgbcolor{mycolor}{0.20 0.20 0.20}\mycolor
223
224
225
%linewidth = 0.05
226
\psset{linewidth=0.05}
227
%RGB color (0.0, 0.0, 1.0)
228
\newrgbcolor{mycolor}{0.00 0.00 1.00}\mycolor
229
230
%Elliptic curve with invariants [0,0,1,-1,0]
231
\pscurve[linecolor=mycolor](2.000,-3.000)(1.967,-2.927)(1.933,-2.854)(1.900,-2.782)(1.867,-2.711)(1.833,-2.640)(1.800,-2.569)(1.767,-2.499)(1.733,-2.430)(1.700,-2.361)(1.667,-2.292)(1.633,-2.225)(1.600,-2.157)(1.567,-2.090)(1.533,-2.024)(1.500,-1.958)(1.467,-1.892)(1.433,-1.827)(1.400,-1.763)(1.367,-1.698)(1.333,-1.634)(1.300,-1.571)(1.267,-1.508)(1.233,-1.445)(1.200,-1.382)(1.167,-1.319)(1.133,-1.257)(1.100,-1.194)(1.067,-1.130)(1.033,-1.066)(1.000,-1.000)(0.967,-0.932)(0.933,-0.860)(0.900,-0.781)(0.867,-0.685)(0.867,-0.315)(0.900,-0.219)(0.933,-0.140)(0.967,-0.068)(1.000,-0.000)(1.033,0.066)(1.067,0.130)(1.100,0.194)(1.133,0.257)(1.167,0.319)(1.200,0.382)(1.233,0.445)(1.267,0.508)(1.300,0.571)(1.333,0.634)(1.367,0.698)(1.400,0.763)(1.433,0.827)(1.467,0.892)(1.500,0.958)(1.533,1.024)(1.567,1.090)(1.600,1.157)(1.633,1.225)(1.667,1.292)(1.700,1.361)(1.733,1.430)(1.767,1.499)(1.800,1.569)(1.833,1.640)(1.867,1.711)(1.900,1.782)(1.933,1.854)(1.967,1.927)(2.000,2.000)(2.033,2.074)\pscurve[linecolor=mycolor](0.267,-0.548)(0.233,-0.671)(0.233,-0.671)(0.200,-0.741)(0.200,-0.741)(0.167,-0.797)(0.167,-0.797)(0.133,-0.845)(0.133,-0.845)(0.100,-0.889)(0.100,-0.889)(0.067,-0.929)(0.067,-0.929)(0.033,-0.966)(0.033,-0.966)(-0.000,-1.000)(-0.000,-1.000)(-0.033,-1.032)(-0.033,-1.032)(-0.067,-1.062)(-0.067,-1.062)(-0.100,-1.091)(-0.100,-1.091)(-0.133,-1.117)(-0.133,-1.117)(-0.167,-1.142)(-0.167,-1.142)(-0.200,-1.165)(-0.200,-1.165)(-0.233,-1.186)(-0.233,-1.186)(-0.267,-1.205)(-0.267,-1.205)(-0.300,-1.223)(-0.300,-1.223)(-0.333,-1.239)(-0.333,-1.239)(-0.367,-1.253)(-0.367,-1.253)(-0.400,-1.266)(-0.400,-1.266)(-0.433,-1.276)(-0.433,-1.276)(-0.467,-1.284)(-0.467,-1.284)(-0.500,-1.291)(-0.500,-1.291)(-0.533,-1.295)(-0.533,-1.295)(-0.567,-1.297)(-0.567,-1.297)(-0.600,-1.296)(-0.600,-1.296)(-0.633,-1.293)(-0.633,-1.293)(-0.667,-1.288)(-0.667,-1.288)(-0.700,-1.279)(-0.700,-1.279)(-0.733,-1.267)(-0.733,-1.267)(-0.767,-1.252)(-0.767,-1.252)(-0.800,-1.233)(-0.800,-1.233)(-0.833,-1.210)(-0.833,-1.210)(-0.867,-1.182)(-0.867,-1.182)(-0.900,-1.149)(-0.900,-1.149)(-0.933,-1.109)(-0.933,-1.109)(-0.967,-1.060)(-0.967,-1.060)(-1.000,-1.000)(-1.000,-1.000)(-1.033,-0.924)(-1.033,-0.924)(-1.067,-0.821)(-1.067,-0.821)(-1.100,-0.638)(-1.100,-0.638)(-1.100,-0.362)(-1.067,-0.179)(-1.033,-0.076)(-1.000,-0.000)(-0.967,0.060)(-0.933,0.109)(-0.900,0.149)(-0.867,0.182)(-0.833,0.210)(-0.800,0.233)(-0.767,0.252)(-0.733,0.267)(-0.700,0.279)(-0.667,0.288)(-0.633,0.293)(-0.600,0.296)(-0.567,0.297)(-0.533,0.295)(-0.500,0.291)(-0.467,0.284)(-0.433,0.276)(-0.400,0.266)(-0.367,0.253)(-0.333,0.239)(-0.300,0.223)(-0.267,0.205)(-0.233,0.186)(-0.200,0.165)(-0.167,0.142)(-0.133,0.117)(-0.100,0.091)(-0.067,0.062)(-0.033,0.032)(-0.000,0.000)(0.033,-0.034)(0.067,-0.071)(0.100,-0.111)(0.133,-0.155)(0.167,-0.203)(0.200,-0.259)(0.233,-0.329)(0.267,-0.452)(0.267,-0.548)
232
233
234
%RGB color (0.0, 0.0, 0.0)
235
\newrgbcolor{mycolor}{0.00 0.00 0.00}\mycolor
236
237
%"{\LARGE $y^2+y = x^3-x$}" at position (-1, -3.7000000000000002)
238
\rput[lb](-1.8, -4){{\large\dblue $y^2+y = x^3-x$}}
239
240
\rput[lb](5,2){{\dgreen EXAMPLES}}
241
\rput[lb](4,1){\Large $y^2+y = x^3-x$}
242
\rput[lb](4,0){{\Large $x^3 + y^3 = 1$} (Fermat cubic)}
243
\rput[lb](4,-1){{\Large $y^2 = x^3+ax+b$}}
244
\rput[lb](4,-2){{\Large $3x^3+4y^3+5=0$}}
245
\newrgbcolor{mycolor}{1.00 0.00 0.00}\mycolor
246
\psset{linewidth=0.02}
247
\psline[linecolor=mycolor](2.7,-1.5)(11,-2)
248
\psline[linecolor=mycolor](2.7,-2)(11,-1.5)
249
\endpspicture
250
}
251
252
\page{\heading{\mbox{}\hspace{2em}The Frey Elliptic Curve}
253
\psset{unit=1.0}
254
\pspicture(0,0)(1,1)
255
\eps{0}{-1}{0.23}{pics/frey2005}
256
\endpspicture
257
\par\noindent{}Suppose Fermat's conjecture is \rd{FALSE}.
258
Then there is a prime $\ell\geq 5$ and coprime
259
positive integers $a,b,c$ with
260
$
261
a^\ell + b^\ell = c^\ell.
262
$
263
264
Consider the corresponding Frey elliptic curve:
265
$$
266
y^2 = x(x-a^\ell)(x+b^\ell).
267
$$
268
269
\begin{center}
270
{\dblue{Ribet's Theorem:}} This elliptic curve is not {\em modular}.
271
272
{\gr{Wiles's Theorem:}} This elliptic curve is {\em modular}.
273
274
{\rd{Conclusion:}} Fermat's conjecture is true.
275
\end{center}
276
}
277
278
\page{
279
\heading{Counting Solutions Modulo $p$}
280
\vspace{-5ex}
281
282
$$N(p) = \text{\# of solutions }\,(\text{mod }p)$$
283
$$y^2 + y = x^3 - x \pmod{7}$$
284
\begin{center}
285
\psset{unit=0.7in}
286
\pspicture(0,0)(6,6)
287
\psgrid[gridcolor=lightgray, subgriddiv=1, gridlabels=10pt]
288
\psline[linewidth=0.03]{->}(0,0)(6,0)\psline[linewidth=0.03]{->}(0,0)(0,6)
289
\pscircle*[linecolor=blue](2,2){0.1999999999999999999999999999}
290
\pscircle*[linecolor=blue](0,0){0.1999999999999999999999999999}
291
\pscircle*[linecolor=blue](6,0){0.1999999999999999999999999999}
292
\pscircle*[linecolor=blue](1,0){0.1999999999999999999999999999}
293
\pscircle*[linecolor=blue](1,6){0.1999999999999999999999999999}
294
\pscircle*[linecolor=blue](6,6){0.1999999999999999999999999999}
295
\pscircle*[linecolor=blue](0,6){0.1999999999999999999999999999}
296
\pscircle*[linecolor=blue](2,4){0.1999999999999999999999999999}
297
\pscircle*[linecolor=blue](7,7){0.1999999999999999999999999999}
298
\rput[bl](7.2,7){$\infty$}
299
\put(6.3,3){\LARGE $N(7) = 9$}
300
%\eps{-3}{-1}{0.07}{pics/gnome1}
301
%\eps{-4}{-1.1}{0.07}{pics/gnome1}
302
%\eps{-2}{-1.2}{0.07}{pics/gnome1}
303
%\rput[bl](-3.5,-1.5){{\tiny Point counting gnomes}}
304
\endpspicture{}\qquad
305
\end{center}
306
} % end page
307
308
309
\page{
310
\heading{Counting Points\hspace{2em}\mbox{}}
311
312
{\dgreen\mbox{}\hspace{1em}\noindent{}Cambridge \rd{EDSAC:} The first\\
313
\mbox{}\hspace{1em}point counting supercomputer...}\\
314
\psset{unit=1.0}
315
\pspicture(0,0)(0,0)
316
\eps{0.3}{-10.5}{0.57}{pics/edsac}
317
\eps{14}{-.75}{0.3}{pics/birch_and_swinnerton-dyer}
318
\eps{14}{-10.5}{0.4}{pics/swinnerton_dyer-count}
319
\put(13,-1.5){Birch and Swinnerton-Dyer}
320
\endpspicture
321
322
} % end page
323
324
\page{
325
\heading{The Hecke \dred{Eigenvalue}}
326
\psset{unit=1.0}
327
\pspicture(0,0)(0,0)
328
\eps{18}{-5}{0.3}{pics/hasse}
329
\put(19.5,-6){Hasse}
330
\endpspicture
331
Let
332
{\LARGE
333
$$
334
a_p = p+1 - N(p).
335
$$
336
}
337
Hasse proved that
338
{\Huge\dblue
339
$$
340
|a_p| \leq 2\sqrt{p}.
341
$$}
342
For $y^2+y=x^3-x$:
343
$$
344
a_2 = -2,\quad a_3 = -3,\quad a_5 = -2,\quad a_7 = -1,
345
\quad a_{11} = -5,\quad a_{13} = -2,$$
346
$$a_{17}=0,\quad a_{19} = 0,\quad a_{23}=2,\quad a_{29}=6,\quad \ldots $$
347
} % end page
348
349
350
\page{
351
\heading{Elliptic Curves are ``Modular''}
352
An elliptic curve is {\em\rd{modular}} if the numbers
353
$a_p$ are coefficients of a ``modular form''.
354
355
{\bf Theorem (Wiles et al.):} {\em Every elliptic curve over the rational
356
numbers is modular.}
357
358
\psset{unit=1.0}
359
\pspicture(0,0)(0,0)
360
\eps{7}{-6}{0.4}{pics/wiles-princeton}
361
\put(6.4,-7){{\tiny Wiles at the Institute for Advanced Study}}
362
\endpspicture
363
}
364
365
366
\page{
367
\heading{Modular Forms}
368
The definition of modular
369
forms as holomorphic functions satisfying
370
a certain equation is very abstract.
371
372
I will skip the abstract definition, and instead give you an
373
explicit ``engineer's recipe'' for producing modular forms.
374
In the meantime, here's a picture:
375
376
\psset{unit=1.0}
377
\pspicture(0,0)(0,0)
378
\eps{5}{-9}{0.6}{pics/modform37a}
379
\endpspicture
380
381
382
}
383
384
\page{
385
\heading{Computing Modular Forms: Motivation}
386
387
\vfill
388
389
\rd{Motivation:} Data about modular forms is \rd{extremely} useful to
390
many research mathematicians (e.g., number theorists, cryptographers). This data is like the astronomer's telescope images.
391
392
\vfill
393
394
I want to compute modular forms on a \rd{\Huge huge} scale using the SDSC
395
resources, and make the resulting database widely available. I have
396
done this on a small scale during the last 5 years --- see {\tt
397
http://modular.fas.harvard.edu/Tables/}
398
\vfill
399
400
}
401
402
\page{
403
\heading{What to Compute: Newforms}
404
405
For each positive integer $N$ there is a finite list of \rd{newforms}
406
of level $N$. E.g., for $N=37$ the newforms are
407
\begin{align*}
408
f_1 &= q - 2q^2 - 3q^3 + 2q^4 - 2q^5 + 6q^6 - q^7 + \cdots\\
409
f_2 &= q + q^3 - 2q^4 - q^7 + \cdots,
410
\end{align*}
411
where $q=e^{2\pi i z}$.
412
413
The newforms of level~$N$ determine all the modular forms of level $N$
414
(like a basis in linear algebra). The coefficients are algebraic integers.
415
{\em Goal: compute these newforms.}
416
417
{\small Bad idea -- write down many elliptic curves and compute the numbers
418
$a_p$ by counting points over finite fields. No good -- this misses
419
most of the interesting newforms, and gets newforms of all kinds of
420
random levels, but you don't know if you get everything of a given
421
level.}
422
423
}
424
425
\page{
426
\heading{An Engineer's Recipe for Newforms}
427
Fix our positive integer $N$. For simplicity assume that $N$ is prime.
428
{\small
429
\begin{enumerate}
430
\item Form the $N+1$ dimensional $\Q$-vector space $V$ with basis the
431
symbols $[0], \ldots, [N-1], [\infty]$.
432
\item Let $R$ be the suspace of $V$ spanned by the following
433
vectors, for\\ $x=0,\ldots, N\!-\!1, \infty$:
434
\begin{align*}
435
& [x] - [N-x] \\
436
& [x] + [x.S] \\
437
& [x] + [x.T] + [x.T^2] \\
438
\end{align*}
439
$S=\abcd{0}{-1}{1}{\hfill 0}$, $T=\abcd{0}{-1}{1}{-1}$,
440
and $x.\abcd{a}{b}{c}{d} = (ax + c)/(bx+d)$.
441
442
\item Compute the quotient vector space $M = V/R$. This involves
443
``intelligent'' {\dblue sparse Gauss elimination} on a matrix with
444
$N+1$ columns.
445
446
\item Compute the matrix $T_2$ on $M$ given by
447
$$ [x]\mapsto [x.\abcd{1}{0}{0}{2}] + [x.\abcd{2}{0}{0}{1}] + [x.\abcd{2}{1}{0}{1}]
448
+ [x.\abcd{1}{0}{1}{2}].
449
$$
450
This matrix is unfortunately not sparse.
451
Similar recipe for matrices $T_n$ for any $n$.
452
453
\item Compute the {\dblue characteristic polynomial} $f$ of $T_2$.
454
455
\item {\dblue Factor} $f = \prod g_i^{e_i}$. Assume all $e_i=1$ (if not,
456
use a random linear combination of the $T_n$.)
457
458
\item Compute the {\dblue kernels} $K_i=\ker(g_i(T_2))$. The {\dblue eigenvalues}
459
of $T_3$, $T_5$, etc., acting on an {\dblue eigenvector} in $K_i$
460
give the coefficients $a_p$ of the newforms of level~$N$.
461
\end{enumerate}
462
}
463
}
464
465
466
\page{
467
\heading{Implementation}
468
\begin{itemize}
469
\item I implemented code for computing modular forms that's
470
included with \rd{MAGMA}:\\
471
{\tt http://magma.maths.usyd.edu.au/magma/}.
472
473
\item Unfortunately, MAGMA is expensive and closed source, so I'm
474
reimplementing everything as part of \rd{SAGE}:\\
475
{\tt http://modular.fas.harvard.edu/sage/}.
476
477
\item I'm teaching a \rd{course} on this topic at UCSD this Fall.
478
479
\item I'm finishing a \rd{book} on these algorithms that will be
480
published by the American Mathematical Society.
481
482
\end{itemize}
483
}
484
485
\page{ \heading{The Modular Forms Database Project}
486
{\small\begin{itemize}
487
\item Create a database of all newforms of level $N$ for each $N<100000$.
488
This will require many gigabytes to store. (50GB?)
489
\item So far this has only been done for $N<7000$ (and is incomplete),
490
so $100000$ is a \rd{major challenge}.
491
492
\item Involves sparse linear algebra over $\Q$ on spaces of
493
dimension up to $200000$ and dense linear algebra on spaces
494
of dimension up to $25000$.
495
496
\item Easy to parallelize -- run one process for
497
each $N$.
498
499
\item Will be very useful to number theorists and cryptographers.
500
501
\item John Cremona has done something similar but only for the
502
newforms corresponding to elliptic curves (he's at around 84000
503
right now).
504
\end{itemize}
505
}
506
}
507
508
\end{document}
509
510
511
512