%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% pycon-sage.tex -- pycon talk about SAGE.
%
%  (c) 2005,
%    William Stein
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[landscape]{slides}\usepackage[active]{srcltx}
\newcommand{\page}[1]{\begin{slide}#1\vfill\end{slide}}
%\renewcommand{\page}[1]{}
\newcommand{\apage}[1]{\begin{slide}#1\vfill\end{slide}}

\newcommand{\eps}[4]{\rput[lb](#1,#2){%
    \includegraphics[width=#3\textwidth]{#4}}}

\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphicx} 
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{conjecture}[theorem]{Conjecture}
\usepackage{pstricks} 
\newrgbcolor{dbluecolor}{0 0 0.6}
\newrgbcolor{dredcolor}{0.5 0 0}
\newrgbcolor{dgreencolor}{0 0.4 0}
\newcommand{\dred}{\dredcolor\bf}
\newcommand{\dblue}{\dbluecolor\bf}
\newcommand{\dgreen}{\dgreencolor\bf}


\title{\bf\dred SAGE: System for Arithmetic Geometry Experimentation\\
{\tt http://modular.fas.harvard.edu/SAGE/}}
\author{\large William Stein\\
Asst. Professor of Mathematics, Harvard University}
\date{March 24, 2005, PYCON, Washington, D.C.\\
}
\bibliographystyle{amsalpha}
\newcommand{\section}[1]{\begin{center}{\dblue \bf\Large #1}\end{center}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\defn}[1]{{\em #1}}
\renewcommand{\H}{\HH}
\newcommand{\hra}{\hookrightarrow}
\newcommand{\isom}{\cong}
\newcommand{\ds}{\displaystyle}


\begin{document}
\small

\page{
\maketitle
}

\page{
\section{Arithmetic Geometry}

Arithmetic geometry is about geometric questions that have an
arithmetic flavor.  Sample famous
problems:

\begin{itemize}
  \item {\dblue Fermat's Last Theorem:} $x^n+y^n=z^n$ has no solutions
with $n\geq 3$ and $x,y,z$ all nonzero integers.  Andrew Wiles
proved this in 1995 using elliptic curves and modular forms.

\item {\dblue The Birch and Swinnerton-Dyer Conjecture:} Discovered
  from computations in the 1960s.  Simple criterion for whether or not
  for given $a,b$ the elliptic curve $y^2=x^3+ax+b$ has infinitely
  many rational solutions.  (Clay $\$10^6$ dollar problem.)

\item {\dblue The Riemann Hypothesis:} Nontrivial zeros of Riemann
  Zeta function are on line ${\rm Re}(s)=1/2$.  Solution gives deep
  understanding of distribution of the prime numbers
  $2,3,5,7,11,13,\ldots.$ (Clay million dollar problem.)

\item {\dblue Cryptography:} Factor integers quickly.  E.g.,
  Hendrik Lenstra, used elliptic curves to give a new algorithms for
  this.  The number field sieve is a sophisticated algorithm for
  factoring and uses computation in number fields.  Also,
  cryptosystems come from elliptic curves over finite fields.

\end{itemize}
}

%\page{
%\section{Arithmetic Geometers}
%{\large
%\vfill
%Arithmetic geometers are people who spend their lives trying very hard
%to solve extremely difficult number theory problems, some of which
%have been unsolved for thousands of years.  They greatly appreciate good
%computational tools.
%\vfill
%{\tiny Tate, Mazur, Elkies, Coates, Wiles, Fontaine, Stark, 
%Ribet, Langlands, Skinner, Conrad, Cremona, Poonen, ...}
%}
%}

\page{
\section{The Problem}
Create a system for doing computations with the mathematical objects
mentioned above.   Main Goals:
\vfill
\begin{itemize}

\item {\dblue Efficient:} Be very fast -- comparable to or faster
  than anything else available.  This is very difficult, since most
  systems are closed source, algorithms are often not published, and
  finding fast algorithms is often extremely difficult (years of work,
  Ph.D. theses, luck, etc.)

\item {\dblue Open Source:} The source code must be available and
  readable, so users can understand what the system is really doing
  and trust the results more. 

\item {\dblue Comprehensive:} Implements enough different things to be
  really useful.

\item {\dblue Well documented:} Reference manual, API reference with
  examples for every function, and at least one published book.  Make
  documentation and source a peer reviewed package, so get
  academic credit like a journal publication.

\item {\dblue Extensible:} Be able to define new data
  types or derive from builtin types, or make code written in your
  favorite language part of the system.

\item {\dblue Free:} Must be sufficiently free (at least GPL).

\end{itemize}
}


\page{
\section{Existing Mature Systems}
\begin{itemize}
\item {\dblue Mathematica, Maple, and MATLAB:} Arithmetic geometers are not
  their target audience.  Mathematica does well at special functions,
  and both do calculus very well, which is almost never useful in
  arithmetic geometry.  These systems are {\em closed source,
    very expensive, for profit}.  

%

\item {\dblue MAGMA:} {\em By far} the best software for arithmetic
  geometry.  It's very efficient, comprehensive, and well documented.
  Great design and class hierarchy.  BUT: It's closed source (but
  non-profit), expensive, and not easily extensible (no user defined
  types or C/C++-extension code).  I've contributed substantially to MAGMA.

\item {\dblue PARI:} Efficient, open source, extendible and free.  But
  the documentation is not good enough and the memory management is
  not robust enough.  Also, PARI does not do nearly as much as what is
  needed.

\item {\dblue Maxima, Octave, etc.:} Open source, but not for arithmetic
geometry.
\end{itemize}
(There's always something else that I don't know about.)

{\em All these system use their own  custom programming language.}
} % end page

\page{
\section{SAGE: System for Arithmetic Geometry Experimentation}
I am creating a system using Python that will hopefully
solve the problem.  I've been working on this for one year (and I've
been writing arithmetic geometry software since 1998, in C++ and
for MAGMA).
Please download and try it, though it is still {\em far from ready} for
prime time:
\begin{center}
{\tt http://modular.fas.harvard.edu/SAGE/}.
\end{center}
\begin{itemize}

\item {\em Like SciPy/Numarray but for arithmetic geometry. }

\item {\dblue Financial Support:} My NSF Grant DMS-0400386, and
  hopefully grad students when I go to UC San Diego as a tenured
  professor in July.  I intend to apply for other grants as well.
  This is a very long-term project.

\item {\dblue Tools:} Python, Pyrex, GMP, PARI, mwrank, SWIG, NTL.
  These are all are GPL'd and SAGE provides (or will provide) a
  unified interface for using them.  Also, I'm writing lots of new
  code, mainly related to my areas of expertise (modular forms, and
  linear algebra over exact fields).  Not reinventing wheel.  Using
  design ideas from MAGMA.

\item {\dblue Current Platforms:} Linux, Solaris, OS X, Windows (cygwin).
   Architecture independent, so no use of psyco.   

\end{itemize}
} % end page

\page{
\section{Advantages to Using Python}
Asside from being open source, building an arithmetic geometry
system on Python has several advantages.
\begin{itemize}
\item {\dred Object persistence} is very easy in Python---but very
  difficult in many other math systems.

%  \item That function arguments can be of any type is extremely
%important in writing mathematics code.  E.g., a generic echelon
%for matrices over {\em any field} is straightforward to write.

\item Good support for {\dred doctest} and automatic extraction of API
  documentation from docstrings.  Having lots of examples that are
  tested and guaranteed to work as indicated.

\item Memory management: MAGMA also does reference counting but does
  {\em not} deal with {\dred circular references}.  Python does.

\item Python has {\dred many packages} available now that might be useful to
  arithmetic geometers:
  numarray/Numeric/SciPy, 2d and 3d graphics, networking (for
  distributed computation), database hooks, etc.

\item Easy to {\dred compile} Python on many platforms.

\end{itemize}
}

\begin{slide}
\section{Standard Python Math Annoyances}
\vfill
Everybody who does mathematics using Python runs into these problems:
\vfill
\begin{itemize}
 \item \verb|**| versus \verb|^| -- easy for me 
   to get used to, but must define \verb|^| to give 
   an error on any arithmetic SAGE type.  (In IPython shell lines can
   be pre-parsed, so this can be solved nicely.)

 \item \verb|sin(2/3)| has {\em much} different behavior in Python than
 in any standard math system.  

\end{itemize}
\vfill 

I think the best solution is to leave the Python language
exactly as is, and write a pre-parser for IPython so that the command
line behavior of IPython is what one expects in
arithmetic geometry, e.g., typing {\tt a = 2/3} will create {\tt a} as
an exact rational number, and typing {\tt a = 3\verb|^|4} will set
{\tt a} to 81.  One must still obey the standard Python rules when
writing code in a file.


\vfill\end{slide}

\begin{slide}
\section{Demo}
{\tiny
\begin{verbatim}
    was@form:~$ sage
    
    **********************************************************
    *  SAGE Version 0.2                                      *
    *  System for Arithmetic Geometry Experimentation        *
    *  (c) William Stein, 2005                               *
    *  http://modular.fas.harvard.edu/SAGE                   *
    *  Distributed under the terms of the GPL                *
    **********************************************************
    Help: object? -> Documentation about 'object'.
    
    >>> Q
         Rational Field
    >>> a = Q("2/3")
    >>> a
         2/3
    >>> a in Q
         True
    >>> type(a)
         <type 'rational.Rational'>
    >>> 3^4    # illustration of IPython hack!
         81
    >>> 3\^4   # usual Python behavior (xor)
         7
\end{verbatim}}

Create a matrix as an element of a space of matrices.
{\tiny
\begin{verbatim}
    >>> M = MatrixSpace(Q,3)
    >>> M
    Full MatrixSpace of 3 by 3 dense matrices over Rational Field
    >>> B = M.basis()
    >>> len(B)
    9
    >>> B[1]
    [0 1 0]
    [0 0 0]
    [0 0 0]
    >>> A = M(range(9)); A
    [0 1 2]
    [3 4 5]
    [6 7 8]
    >>> A.reduced_row_echelon_form()
    [ 1  0 -1]
    [ 0  1  2]
    [ 0  0  0]
    >>> A^20
    [ 2466392619654627540480  3181394780427730516992  3896396941200833493504] ...
    >>> A.kernel()
    Vector space of degree 3, dimension 1 over Rational Field
    Basis matrix:
    [ 1 -2  1]
    >>> kernel(A)   # functional notation, like in MAGMA
\end{verbatim}
}

Compute with an elliptic curve.
{\tiny 
\begin{verbatim}
    >>> E = EllipticCurve([0,0,1,-1,0])
    >>> E
         y^2 + y = x^3 - x
    >>> P = E([0,0])
    >>> 10*P
         (161/16, -2065/64)
    >>> 20*P
         (683916417/264517696, -18784454671297/4302115807744)
    >>> E.conductor()
         37
    >>> print E.anlist(30)    # coefficients of associated modular form
        [0, 1, -2, -3, 2, -2, 6, -1, 0, 6, 4, -5, -6, -2, 2, 6, -4, 0, -12, 
         0, -4, 3, 10, 2, 0, -1, 4, -9, -2, 6, -12]
    >>> M = ModularSymbols(37)
    >>> D = M.decomposition()
    >>> D
    [Subspace of Modular Symbols of dimension 1 and level 37,
     Subspace of Modular Symbols of dimension 2 and level 37,
     Subspace of Modular Symbols of dimension 2 and level 37]
    >>> D[1].T(2)
    Linear function defined by matrix:
    [0 0]
    [0 0]
    >>> D[2].T(2)
    Linear function defined by matrix:
    [-2  0]
    [ 0 -2]
\end{verbatim}
}  

\end{slide}


\end{document}