%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%1% pycon-sage.tex -- pycon talk about SAGE.2%3% (c) 2005,4% William Stein5%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%67\documentclass[landscape]{slides}8\newcommand{\page}[1]{\begin{slide}#1\vfill\end{slide}}9%\renewcommand{\page}[1]{}10\newcommand{\apage}[1]{\begin{slide}#1\vfill\end{slide}}1112\newcommand{\eps}[4]{\rput[lb](#1,#2){%13\includegraphics[width=#3\textwidth]{#4}}}1415\usepackage{fullpage}16\usepackage{amsmath}17\usepackage{amsfonts}18\usepackage{amssymb}19\usepackage{amsthm}20\usepackage{graphicx}21\theoremstyle{plain}22\newtheorem{theorem}{Theorem}23\newtheorem{proposition}[theorem]{Proposition}24\newtheorem{corollary}[theorem]{Corollary}25\newtheorem{claim}[theorem]{Claim}26\newtheorem{lemma}[theorem]{Lemma}27\newtheorem{conjecture}[theorem]{Conjecture}28\usepackage{pstricks}29\newrgbcolor{dbluecolor}{0 0 0.6}30\newrgbcolor{dredcolor}{0.5 0 0}31\newrgbcolor{dgreencolor}{0 0.4 0}32\newcommand{\dred}{\dredcolor\bf}33\newcommand{\dblue}{\dbluecolor\bf}34\newcommand{\dgreen}{\dgreencolor\bf}353637\title{\bf\dred SAGE: System for Arithmetic Geometry Experimentation\\38{\tt http://modular.fas.harvard.edu/SAGE/}}39\author{\large William Stein\\40Asst. Professor of Mathematics, Harvard University}41\date{March 24, 2005, PYCON, Washington, D.C.\\42}43\bibliographystyle{amsalpha}44\newcommand{\section}[1]{\begin{center}{\dblue \bf\Large #1}\end{center}}45\newcommand{\Q}{\mathbb{Q}}46\newcommand{\Z}{\mathbb{Z}}47\newcommand{\defn}[1]{{\em #1}}48\renewcommand{\H}{\HH}49\newcommand{\hra}{\hookrightarrow}50\newcommand{\isom}{\cong}51\newcommand{\ds}{\displaystyle}525354\begin{document}55\small5657\page{58\maketitle59}6061\page{62\section{Arithmetic Geometry}6364Arithmetic geometry is about geometric questions that have an65arithmetic flavor. Sample famous66problems:6768\begin{itemize}69\item {\dblue Fermat's Last Theorem:} $x^n+y^n=z^n$ has no solutions70with $n\geq 3$ and $x,y,z$ all nonzero integers. Andrew Wiles71proved this in 1995 using elliptic curves and modular forms.7273\item {\dblue The Birch and Swinnerton-Dyer Conjecture:} Discovered74from computations in the 1960s. Simple criterion for whether or not75for given $a,b$ the elliptic curve $y^2=x^3+ax+b$ has infinitely76many rational solutions. (Clay $\$10^6$ dollar problem.)7778\item {\dblue The Riemann Hypothesis:} Nontrivial zeros of Riemann79Zeta function are on line ${\rm Re}(s)=1/2$. Solution gives deep80understanding of distribution of the prime numbers81$2,3,5,7,11,13,\ldots.$ (Clay million dollar problem.)8283\item {\dblue Cryptography:} Factor integers quickly. E.g.,84Hendrik Lenstra, used elliptic curves to give a new algorithms for85this. The number field sieve is a sophisticated algorithm for86factoring and uses computation in number fields. Also,87cryptosystems come from elliptic curves over finite fields.8889\end{itemize}90}9192%\page{93%\section{Arithmetic Geometers}94%{\large95%\vfill96%Arithmetic geometers are people who spend their lives trying very hard97%to solve extremely difficult number theory problems, some of which98%have been unsolved for thousands of years. They greatly appreciate good99%computational tools.100%\vfill101%{\tiny Tate, Mazur, Elkies, Coates, Wiles, Fontaine, Stark,102%Ribet, Langlands, Skinner, Conrad, Cremona, Poonen, ...}103%}104%}105106\page{107\section{The Problem}108Create a system for doing computations with the mathematical objects109mentioned above. Main Goals:110\vfill111\begin{itemize}112113\item {\dblue Efficient:} Be very fast -- comparable to or faster114than anything else available. This is very difficult, since most115systems are closed source, algorithms are often not published, and116finding fast algorithms is often extremely difficult (years of work,117Ph.D. theses, luck, etc.)118119\item {\dblue Open Source:} The source code must be available and120readable, so users can understand what the system is really doing121and trust the results more.122123\item {\dblue Comprehensive:} Implements enough different things to be124really useful.125126\item {\dblue Well documented:} Reference manual, API reference with127examples for every function, and at least one published book. Make128documentation and source a peer reviewed package, so get129academic credit like a journal publication.130131\item {\dblue Extensible:} Be able to define new data132types or derive from builtin types, or make code written in your133favorite language part of the system.134135\item {\dblue Free:} Must be sufficiently free (at least GPL).136137\end{itemize}138}139140141\page{142\section{Existing Mature Systems}143\begin{itemize}144\item {\dblue Mathematica, Maple, and MATLAB:} Arithmetic geometers are not145their target audience. Mathematica does well at special functions,146and both do calculus very well, which is almost never useful in147arithmetic geometry. These systems are {\em closed source,148very expensive, for profit}.149150%151152\item {\dblue MAGMA:} {\em By far} the best software for arithmetic153geometry. It's very efficient, comprehensive, and well documented.154Great design and class hierarchy. BUT: It's closed source (but155non-profit), expensive, and not easily extensible (no user defined156types or C/C++-extension code). I've contributed substantially to MAGMA.157158\item {\dblue PARI:} Efficient, open source, extendible and free. But159the documentation is not good enough and the memory management is160not robust enough. Also, PARI does not do nearly as much as what is161needed.162163\item {\dblue Maxima, Octave, etc.:} Open source, but not for arithmetic164geometry.165\end{itemize}166(There's always something else that I don't know about.)167168{\em All these system use their own custom programming language.}169} % end page170171\page{172\section{SAGE: System for Arithmetic Geometry Experimentation}173I am creating a system using Python that will hopefully174solve the problem. I've been working on this for one year (and I've175been writing arithmetic geometry software since 1998, in C++ and176for MAGMA).177Please download and try it, though it is still {\em far from ready} for178prime time:179\begin{center}180{\tt http://modular.fas.harvard.edu/SAGE/}.181\end{center}182\begin{itemize}183184\item {\em Like SciPy/Numarray but for arithmetic geometry. }185186\item {\dblue Financial Support:} My NSF Grant DMS-0400386, and187hopefully grad students when I go to UC San Diego as a tenured188professor in July. I intend to apply for other grants as well.189This is a very long-term project.190191\item {\dblue Tools:} Python, Pyrex, GMP, PARI, mwrank, SWIG, NTL.192These are all are GPL'd and SAGE provides (or will provide) a193unified interface for using them. Also, I'm writing lots of new194code, mainly related to my areas of expertise (modular forms, and195linear algebra over exact fields). Not reinventing wheel. Using196design ideas from MAGMA.197198\item {\dblue Current Platforms:} Linux, Solaris, OS X, Windows (cygwin).199Architecture independent, so no use of psyco.200201\end{itemize}202} % end page203204\page{205\section{Advantages to Using Python}206Asside from being open source, building an arithmetic geometry207system on Python has several advantages.208\begin{itemize}209\item {\dred Object persistence} is very easy in Python---but very210difficult in many other math systems.211212% \item That function arguments can be of any type is extremely213%important in writing mathematics code. E.g., a generic echelon214%for matrices over {\em any field} is straightforward to write.215216\item Good support for {\dred doctest} and automatic extraction of API217documentation from docstrings. Having lots of examples that are218tested and guaranteed to work as indicated.219220\item Memory management: MAGMA also does reference counting but does221{\em not} deal with {\dred circular references}. Python does.222223\item Python has {\dred many packages} available now that might be useful to224arithmetic geometers:225numarray/Numeric/SciPy, 2d and 3d graphics, networking (for226distributed computation), database hooks, etc.227228\item Easy to {\dred compile} Python on many platforms.229230\end{itemize}231}232233\begin{slide}234\section{Standard Python Math Annoyances}235\vfill236Everybody who does mathematics using Python runs into these problems:237\vfill238\begin{itemize}239\item \verb|**| versus \verb|^| -- easy for me240to get used to, but must define \verb|^| to give241an error on any arithmetic SAGE type. (In IPython shell lines can242be pre-parsed, so this can be solved nicely.)243244\item \verb|sin(2/3)| has {\em much} different behavior in Python than245in any standard math system.246247\end{itemize}248\vfill249250I think the best solution is to leave the Python language251exactly as is, and write a pre-parser for IPython so that the command252line behavior of IPython is what one expects in253arithmetic geometry, e.g., typing {\tt a = 2/3} will create {\tt a} as254an exact rational number, and typing {\tt a = 3\verb|^|4} will set255{\tt a} to 81. One must still obey the standard Python rules when256writing code in a file.257258259\vfill\end{slide}260261\begin{slide}262\section{Demo}263{\tiny264\begin{verbatim}265was@form:~$ sage266267**********************************************************268* SAGE Version 0.2 *269* System for Arithmetic Geometry Experimentation *270* (c) William Stein, 2005 *271* http://modular.fas.harvard.edu/SAGE *272* Distributed under the terms of the GPL *273**********************************************************274Help: object? -> Documentation about 'object'.275276>>> Q277Rational Field278>>> a = Q("2/3")279>>> a2802/3281>>> a in Q282True283>>> type(a)284<type 'rational.Rational'>285>>> 3^4 # illustration of IPython hack!28681287>>> 3\^4 # usual Python behavior (xor)2887289\end{verbatim}}290291Create a matrix as an element of a space of matrices.292{\tiny293\begin{verbatim}294>>> M = MatrixSpace(Q,3)295>>> M296Full MatrixSpace of 3 by 3 dense matrices over Rational Field297>>> B = M.basis()298>>> len(B)2999300>>> B[1]301[0 1 0]302[0 0 0]303[0 0 0]304>>> A = M(range(9)); A305[0 1 2]306[3 4 5]307[6 7 8]308>>> A.reduced_row_echelon_form()309[ 1 0 -1]310[ 0 1 2]311[ 0 0 0]312>>> A^20313[ 2466392619654627540480 3181394780427730516992 3896396941200833493504] ...314>>> A.kernel()315Vector space of degree 3, dimension 1 over Rational Field316Basis matrix:317[ 1 -2 1]318>>> kernel(A) # functional notation, like in MAGMA319\end{verbatim}320}321322Compute with an elliptic curve.323{\tiny324\begin{verbatim}325>>> E = EllipticCurve([0,0,1,-1,0])326>>> E327y^2 + y = x^3 - x328>>> P = E([0,0])329>>> 10*P330(161/16, -2065/64)331>>> 20*P332(683916417/264517696, -18784454671297/4302115807744)333>>> E.conductor()33437335>>> print E.anlist(30) # coefficients of associated modular form336[0, 1, -2, -3, 2, -2, 6, -1, 0, 6, 4, -5, -6, -2, 2, 6, -4, 0, -12,3370, -4, 3, 10, 2, 0, -1, 4, -9, -2, 6, -12]338>>> M = ModularSymbols(37)339>>> D = M.decomposition()340>>> D341[Subspace of Modular Symbols of dimension 1 and level 37,342Subspace of Modular Symbols of dimension 2 and level 37,343Subspace of Modular Symbols of dimension 2 and level 37]344>>> D[1].T(2)345Linear function defined by matrix:346[0 0]347[0 0]348>>> D[2].T(2)349Linear function defined by matrix:350[-2 0]351[ 0 -2]352\end{verbatim}353}354355\end{slide}356357358\end{document}359360361