Sharedwww / talks / 2005-03-23-pyconn-sage / pycon-sage.texOpen in CoCalc
Author: William A. Stein
1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2
% pycon-sage.tex -- pycon talk about SAGE.
3
%
4
% (c) 2005,
5
% William Stein
6
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
7
8
\documentclass[landscape]{slides}
9
\newcommand{\page}[1]{\begin{slide}#1\vfill\end{slide}}
10
%\renewcommand{\page}[1]{}
11
\newcommand{\apage}[1]{\begin{slide}#1\vfill\end{slide}}
12
13
\newcommand{\eps}[4]{\rput[lb](#1,#2){%
14
\includegraphics[width=#3\textwidth]{#4}}}
15
16
\usepackage{fullpage}
17
\usepackage{amsmath}
18
\usepackage{amsfonts}
19
\usepackage{amssymb}
20
\usepackage{amsthm}
21
\usepackage{graphicx}
22
\theoremstyle{plain}
23
\newtheorem{theorem}{Theorem}
24
\newtheorem{proposition}[theorem]{Proposition}
25
\newtheorem{corollary}[theorem]{Corollary}
26
\newtheorem{claim}[theorem]{Claim}
27
\newtheorem{lemma}[theorem]{Lemma}
28
\newtheorem{conjecture}[theorem]{Conjecture}
29
\usepackage{pstricks}
30
\newrgbcolor{dbluecolor}{0 0 0.6}
31
\newrgbcolor{dredcolor}{0.5 0 0}
32
\newrgbcolor{dgreencolor}{0 0.4 0}
33
\newcommand{\dred}{\dredcolor\bf}
34
\newcommand{\dblue}{\dbluecolor\bf}
35
\newcommand{\dgreen}{\dgreencolor\bf}
36
37
38
\title{\bf\dred SAGE: System for Arithmetic Geometry Experimentation\\
39
{\tt http://modular.fas.harvard.edu/SAGE/}}
40
\author{\large William Stein\\
41
Asst. Professor of Mathematics, Harvard University}
42
\date{March 24, 2005, PYCON, Washington, D.C.\\
43
}
44
\bibliographystyle{amsalpha}
45
\newcommand{\section}[1]{\begin{center}{\dblue \bf\Large #1}\end{center}}
46
\newcommand{\Q}{\mathbb{Q}}
47
\newcommand{\Z}{\mathbb{Z}}
48
\newcommand{\defn}[1]{{\em #1}}
49
\renewcommand{\H}{\HH}
50
\newcommand{\hra}{\hookrightarrow}
51
\newcommand{\isom}{\cong}
52
\newcommand{\ds}{\displaystyle}
53
54
55
\begin{document}
56
\small
57
58
\page{
59
\maketitle
60
}
61
62
\page{
63
\section{Arithmetic Geometry}
64
65
Arithmetic geometry is about geometric questions that have an
66
arithmetic flavor. Sample famous
67
problems:
68
69
\begin{itemize}
70
\item {\dblue Fermat's Last Theorem:} $x^n+y^n=z^n$ has no solutions
71
with $n\geq 3$ and $x,y,z$ all nonzero integers. Andrew Wiles
72
proved this in 1995 using elliptic curves and modular forms.
73
74
\item {\dblue The Birch and Swinnerton-Dyer Conjecture:} Discovered
75
from computations in the 1960s. Simple criterion for whether or not
76
for given $a,b$ the elliptic curve $y^2=x^3+ax+b$ has infinitely
77
many rational solutions. (Clay $\$10^6$ dollar problem.)
78
79
\item {\dblue The Riemann Hypothesis:} Nontrivial zeros of Riemann
80
Zeta function are on line ${\rm Re}(s)=1/2$. Solution gives deep
81
understanding of distribution of the prime numbers
82
$2,3,5,7,11,13,\ldots.$ (Clay million dollar problem.)
83
84
\item {\dblue Cryptography:} Factor integers quickly. E.g.,
85
Hendrik Lenstra, used elliptic curves to give a new algorithms for
86
this. The number field sieve is a sophisticated algorithm for
87
factoring and uses computation in number fields. Also,
88
cryptosystems come from elliptic curves over finite fields.
89
90
\end{itemize}
91
}
92
93
%\page{
94
%\section{Arithmetic Geometers}
95
%{\large
96
%\vfill
97
%Arithmetic geometers are people who spend their lives trying very hard
98
%to solve extremely difficult number theory problems, some of which
99
%have been unsolved for thousands of years. They greatly appreciate good
100
%computational tools.
101
%\vfill
102
%{\tiny Tate, Mazur, Elkies, Coates, Wiles, Fontaine, Stark,
103
%Ribet, Langlands, Skinner, Conrad, Cremona, Poonen, ...}
104
%}
105
%}
106
107
\page{
108
\section{The Problem}
109
Create a system for doing computations with the mathematical objects
110
mentioned above. Main Goals:
111
\vfill
112
\begin{itemize}
113
114
\item {\dblue Efficient:} Be very fast -- comparable to or faster
115
than anything else available. This is very difficult, since most
116
systems are closed source, algorithms are often not published, and
117
finding fast algorithms is often extremely difficult (years of work,
118
Ph.D. theses, luck, etc.)
119
120
\item {\dblue Open Source:} The source code must be available and
121
readable, so users can understand what the system is really doing
122
and trust the results more.
123
124
\item {\dblue Comprehensive:} Implements enough different things to be
125
really useful.
126
127
\item {\dblue Well documented:} Reference manual, API reference with
128
examples for every function, and at least one published book. Make
129
documentation and source a peer reviewed package, so get
130
academic credit like a journal publication.
131
132
\item {\dblue Extensible:} Be able to define new data
133
types or derive from builtin types, or make code written in your
134
favorite language part of the system.
135
136
\item {\dblue Free:} Must be sufficiently free (at least GPL).
137
138
\end{itemize}
139
}
140
141
142
\page{
143
\section{Existing Mature Systems}
144
\begin{itemize}
145
\item {\dblue Mathematica, Maple, and MATLAB:} Arithmetic geometers are not
146
their target audience. Mathematica does well at special functions,
147
and both do calculus very well, which is almost never useful in
148
arithmetic geometry. These systems are {\em closed source,
149
very expensive, for profit}.
150
151
%
152
153
\item {\dblue MAGMA:} {\em By far} the best software for arithmetic
154
geometry. It's very efficient, comprehensive, and well documented.
155
Great design and class hierarchy. BUT: It's closed source (but
156
non-profit), expensive, and not easily extensible (no user defined
157
types or C/C++-extension code). I've contributed substantially to MAGMA.
158
159
\item {\dblue PARI:} Efficient, open source, extendible and free. But
160
the documentation is not good enough and the memory management is
161
not robust enough. Also, PARI does not do nearly as much as what is
162
needed.
163
164
\item {\dblue Maxima, Octave, etc.:} Open source, but not for arithmetic
165
geometry.
166
\end{itemize}
167
(There's always something else that I don't know about.)
168
169
{\em All these system use their own custom programming language.}
170
} % end page
171
172
\page{
173
\section{SAGE: System for Arithmetic Geometry Experimentation}
174
I am creating a system using Python that will hopefully
175
solve the problem. I've been working on this for one year (and I've
176
been writing arithmetic geometry software since 1998, in C++ and
177
for MAGMA).
178
Please download and try it, though it is still {\em far from ready} for
179
prime time:
180
\begin{center}
181
{\tt http://modular.fas.harvard.edu/SAGE/}.
182
\end{center}
183
\begin{itemize}
184
185
\item {\em Like SciPy/Numarray but for arithmetic geometry. }
186
187
\item {\dblue Financial Support:} My NSF Grant DMS-0400386, and
188
hopefully grad students when I go to UC San Diego as a tenured
189
professor in July. I intend to apply for other grants as well.
190
This is a very long-term project.
191
192
\item {\dblue Tools:} Python, Pyrex, GMP, PARI, mwrank, SWIG, NTL.
193
These are all are GPL'd and SAGE provides (or will provide) a
194
unified interface for using them. Also, I'm writing lots of new
195
code, mainly related to my areas of expertise (modular forms, and
196
linear algebra over exact fields). Not reinventing wheel. Using
197
design ideas from MAGMA.
198
199
\item {\dblue Current Platforms:} Linux, Solaris, OS X, Windows (cygwin).
200
Architecture independent, so no use of psyco.
201
202
\end{itemize}
203
} % end page
204
205
\page{
206
\section{Advantages to Using Python}
207
Asside from being open source, building an arithmetic geometry
208
system on Python has several advantages.
209
\begin{itemize}
210
\item {\dred Object persistence} is very easy in Python---but very
211
difficult in many other math systems.
212
213
% \item That function arguments can be of any type is extremely
214
%important in writing mathematics code. E.g., a generic echelon
215
%for matrices over {\em any field} is straightforward to write.
216
217
\item Good support for {\dred doctest} and automatic extraction of API
218
documentation from docstrings. Having lots of examples that are
219
tested and guaranteed to work as indicated.
220
221
\item Memory management: MAGMA also does reference counting but does
222
{\em not} deal with {\dred circular references}. Python does.
223
224
\item Python has {\dred many packages} available now that might be useful to
225
arithmetic geometers:
226
numarray/Numeric/SciPy, 2d and 3d graphics, networking (for
227
distributed computation), database hooks, etc.
228
229
\item Easy to {\dred compile} Python on many platforms.
230
231
\end{itemize}
232
}
233
234
\begin{slide}
235
\section{Standard Python Math Annoyances}
236
\vfill
237
Everybody who does mathematics using Python runs into these problems:
238
\vfill
239
\begin{itemize}
240
\item \verb|**| versus \verb|^| -- easy for me
241
to get used to, but must define \verb|^| to give
242
an error on any arithmetic SAGE type. (In IPython shell lines can
243
be pre-parsed, so this can be solved nicely.)
244
245
\item \verb|sin(2/3)| has {\em much} different behavior in Python than
246
in any standard math system.
247
248
\end{itemize}
249
\vfill
250
251
I think the best solution is to leave the Python language
252
exactly as is, and write a pre-parser for IPython so that the command
253
line behavior of IPython is what one expects in
254
arithmetic geometry, e.g., typing {\tt a = 2/3} will create {\tt a} as
255
an exact rational number, and typing {\tt a = 3\verb|^|4} will set
256
{\tt a} to 81. One must still obey the standard Python rules when
257
writing code in a file.
258
259
260
\vfill\end{slide}
261
262
\begin{slide}
263
\section{Demo}
264
{\tiny
265
\begin{verbatim}
266
was@form:~$ sage
267
268
**********************************************************
269
* SAGE Version 0.2 *
270
* System for Arithmetic Geometry Experimentation *
271
* (c) William Stein, 2005 *
272
* http://modular.fas.harvard.edu/SAGE *
273
* Distributed under the terms of the GPL *
274
**********************************************************
275
Help: object? -> Documentation about 'object'.
276
277
>>> Q
278
Rational Field
279
>>> a = Q("2/3")
280
>>> a
281
2/3
282
>>> a in Q
283
True
284
>>> type(a)
285
<type 'rational.Rational'>
286
>>> 3^4 # illustration of IPython hack!
287
81
288
>>> 3\^4 # usual Python behavior (xor)
289
7
290
\end{verbatim}}
291
292
Create a matrix as an element of a space of matrices.
293
{\tiny
294
\begin{verbatim}
295
>>> M = MatrixSpace(Q,3)
296
>>> M
297
Full MatrixSpace of 3 by 3 dense matrices over Rational Field
298
>>> B = M.basis()
299
>>> len(B)
300
9
301
>>> B[1]
302
[0 1 0]
303
[0 0 0]
304
[0 0 0]
305
>>> A = M(range(9)); A
306
[0 1 2]
307
[3 4 5]
308
[6 7 8]
309
>>> A.reduced_row_echelon_form()
310
[ 1 0 -1]
311
[ 0 1 2]
312
[ 0 0 0]
313
>>> A^20
314
[ 2466392619654627540480 3181394780427730516992 3896396941200833493504] ...
315
>>> A.kernel()
316
Vector space of degree 3, dimension 1 over Rational Field
317
Basis matrix:
318
[ 1 -2 1]
319
>>> kernel(A) # functional notation, like in MAGMA
320
\end{verbatim}
321
}
322
323
Compute with an elliptic curve.
324
{\tiny
325
\begin{verbatim}
326
>>> E = EllipticCurve([0,0,1,-1,0])
327
>>> E
328
y^2 + y = x^3 - x
329
>>> P = E([0,0])
330
>>> 10*P
331
(161/16, -2065/64)
332
>>> 20*P
333
(683916417/264517696, -18784454671297/4302115807744)
334
>>> E.conductor()
335
37
336
>>> print E.anlist(30) # coefficients of associated modular form
337
[0, 1, -2, -3, 2, -2, 6, -1, 0, 6, 4, -5, -6, -2, 2, 6, -4, 0, -12,
338
0, -4, 3, 10, 2, 0, -1, 4, -9, -2, 6, -12]
339
>>> M = ModularSymbols(37)
340
>>> D = M.decomposition()
341
>>> D
342
[Subspace of Modular Symbols of dimension 1 and level 37,
343
Subspace of Modular Symbols of dimension 2 and level 37,
344
Subspace of Modular Symbols of dimension 2 and level 37]
345
>>> D[1].T(2)
346
Linear function defined by matrix:
347
[0 0]
348
[0 0]
349
>>> D[2].T(2)
350
Linear function defined by matrix:
351
[-2 0]
352
[ 0 -2]
353
\end{verbatim}
354
}
355
356
\end{slide}
357
358
359
\end{document}
360
361