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}{\begin{slide}#1\vfill\end{slide}}
10%\renewcommand{\page}{}
11\newcommand{\apage}{\begin{slide}#1\vfill\end{slide}}
12
13\newcommand{\eps}{\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\\
41Asst. Professor of Mathematics, Harvard University}
42\date{March 24, 2005, PYCON, Washington, D.C.\\
43}
44\bibliographystyle{amsalpha}
45\newcommand{\section}{\begin{center}{\dblue \bf\Large #1}\end{center}}
46\newcommand{\Q}{\mathbb{Q}}
47\newcommand{\Z}{\mathbb{Z}}
48\newcommand{\defn}{{\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
65Arithmetic geometry is about geometric questions that have an
66arithmetic flavor.  Sample famous
67problems:
68
69\begin{itemize}
70  \item {\dblue Fermat's Last Theorem:} $x^n+y^n=z^n$ has no solutions
71with $n\geq 3$ and $x,y,z$ all nonzero integers.  Andrew Wiles
72proved 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} 109Create a system for doing computations with the mathematical objects 110mentioned 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 165geometry. 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} 174I am creating a system using Python that will hopefully 175solve the problem. I've been working on this for one year (and I've 176been writing arithmetic geometry software since 1998, in C++ and 177for MAGMA). 178Please download and try it, though it is still {\em far from ready} for 179prime 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} 207Asside from being open source, building an arithmetic geometry 208system 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 237Everybody 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 251I think the best solution is to leave the Python language 252exactly as is, and write a pre-parser for IPython so that the command 253line behavior of IPython is what one expects in 254arithmetic geometry, e.g., typing {\tt a = 2/3} will create {\tt a} as 255an 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 257writing 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                   *
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
292Create 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
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
323Compute 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.T(2)
346    Linear function defined by matrix:
347    [0 0]
348    [0 0]
349    >>> D.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