3913-Getting started with the notebook.sagews

AMS Short Course: Computing with Elliptic Curves using Sage

January 2-3, 2012

Lecture 1: Introduction to Python and Sage

Kiran S. Kedlaya (MIT/UC San Diego)

This lecture is an introduction to using the computer algebra system Sage. In the process, we will also introduce the Python programming language, on which Sage is built; however, we'll keep the programming discussion to a minimum because it is easy to find Python tutorials and other documentation online. (For example, try the Beginner's Guide to Python.)

All of the lectures in this minicourse are meant to be interactive, so you are strongly encouraged to follow along on your own computer as we go along. To make this possible, we begin by explaining how to run Sage on your own computer. There are two natural ways to do this.

• Since Sage is free for everyone, you may install Sage on your own computer and run it locally using the command line. Go to http://www.sagemath.org and follow the links to download and install Sage. (Warning: this is a bit tricky if you run Windows. Ask one of us for help if you get stuck.)
• Besides the command line, Sage also offers a graphical interface, the Sage Notebook, in which you use your web browser as a client to access a Sage server on some possibly different machine. For example, right now, I am running Sage on my local computer as a server, and using this browser to connect to that server in order to display this presentation. However, there also exists a public notebook server on which anyone can create an account and run Sage! This is by far the easiest way to try out Sage right now. To do so, point your browser to http://www.sagenb.org.

To simplify the exposition, I'm mostly going to stick to explaining the notebook interface. We will come back to the command line later.

Getting started with the notebook

If you have successfully started a notebook session, you should see something that looks much like this window, except that instead of all of this text, you should just see an empty box like the one below.

This box is called a cell, and can be used to evaluate any Sage command. For example, try clicking on the cell, typing 2+2, and clicking "evaluate". (A shortcut for "evaluate" is Shift+Enter.)

2+2

4

Note that the answer appears immediately below, and then a new cell is generated so that you can type another command. You can also go back and edit the previous cell, but the answer won't change until you evaluate again. You can even insert new cells between existing cells: if you click on the blue bar that shows up when you mouse between two existing cells, a new cell will pop up in between.

If you Shift-click instead, you get a text box like this, which supports some formatting and even basic TeX commands. This is one way to add annotations to a notebook; a more direct one is simply to insert comments in cells themselves. The # character denotes a comment, and forces everything to the end of the line to be ignored.

2+2 # should equal 4

4

Besides individual calculator-style expressions, a cell can contain a sequence of instructions; hit Enter to separate instructions. (This is why Shift-Enter is the shortcut for evaluation, not Enter.) The last expression is evaluated and printed; you can also add "print" commands to force additional printing.

x = 5
y = 7
print x+y
x*y

12 35

Each cell evaluation remembers any definitions from cells that were evaluated previously, including variables and functions (more on which later).

x+y

12

Warning: Sage will let you evaluate cells out of order. It is the order of evaluation that counts, not the order of appearance in the worksheet.

If you try to evaluate a cell which contains a mistake, such as trying to use a variable which is not yet defined, Sage will give you a (hopefully) useful error message. You can click on the output to see a more verbose error message, which may help you isolate the problem if it occurs in a large cell.

z

Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_5.py", line 10, in <module> exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("eg=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in <module> File "/tmp/tmptwbxbG/___code___.py", line 2, in <module> exec compile(u'z' + '\n', '', 'single') File "", line 1, in <module> NameError: name 'z' is not defined

Basic Python/Sage objects

Let's get familiar with some basic types of Python/Sage objects. These will all be things that can be assigned to variables, which we have already seen how to do in the case of integers.

x = 2+2
print x

4

Note that variables do not need to be declared before being used; in particular, there is no need to specify in advance what type of object is going to be assigned to a given variable.

So far our variable names have only been one character long. However, this is not required: you may use any sequence of letters, numbers, and the underscore _ as a variable name as long as it starts with a letter and does not coincide with a Python reserved wood (such as "print"). Considered choice of variable names may make your code easier for a human to understand.

square_root_of_2 = sqrt(2)
print square_root_of_2^4

4

Besides integers, some other basic types of objects include rational numbers, real numbers, and complex numbers (where capital I denotes the chosen square root of -1). These support the usual arithmetic operations.

print 7 % 3 ## modular reduction
print 7 // 3 ## integer division
print 10/6 ## returns a rational number
print exp(2.7)
print (2+I)*(3+I)

Another basic object type is strings, which are enclosed in either single or double quotes (there is a subtle distinction which is not relevant here). One common operation on strings is concatenation.

'3' + '4'

Arrays

Besides simple types like numbers and strings, one also has compound types like arrays. Arrays can be specified using square brackets (the entries need not be all of one type).

print [3, 4] + [5, 'six'] ## plus sign denotes composition

One also uses square brackets to access the individual entries of an array, or even to assign them. Two important things to note:

• Python indexes starting from 0, not 1.
• You may also use negative indices: -n denotes the n-th term from the end.

u = [2, 3, 4]
print u[0] ## first element
print u[-1] ## last element
u[1] = 1 ## modify an existing entry
print u[-2] ## should equal u[1]
u[3] = 5 ## this won't work

[2, 3] [0, 1, 2, 3, 4] [3, 5, 7, 9, 11]

Some other ways to construct arrays are the following.

• One can concatenate existing arrays using the + operator (see above).
• One can modify in place entries of an existing array (see above).
• One can form slices of an existing array by picking out a range of values. This is the safest way to make a copy of an array (see below).
• Some functions return arrays, such as the "range" function.
• One can use list comprehensions to apply a function to each term of one array to make a new array. There is also the option to put in a conditional statement to pick out only some of the terms of the original array (using == for equality, rather than = which means assignment). This is a lot like how mathematicians make sets!

u = [2,3,4,5]
print u[1:3] ## left index is included, right index is not
print u[:4] ## left index defaults to 0
print u[1:] ## right index defaults to the length of the array
print range(5) ## range(n) includes 0, excludes n
print range(3,13) ## specify left and right endpoints as for slices
print [x^2 for x in u if x%2==1]

[3, 4] [2, 3, 4, 5] [3, 4, 5] [0, 1, 2, 3, 4] [3, 4, 5, 6, 7, 8, 9, 10, 11, 12] [9, 25]

Warning: arrays are copied by reference, not by value. This is in fact true for all Python/Sage objects, but the fact that arrays can be modified after they are created (that is, they are mutable) creates a real danger.

a = [1,2,3]
b = a ## does not create a new array!
b[1] = -1
print "a = ", a ## has now been modified
c = a[:] ## this does create a new array
c[-1] = 4
print "a = ", a
print "c = ", c

Conditional evaluation

Like most programming languages, Python supports conditional evaluation via such mechanisms as for loops, while loops, and if-then-else constructions. Here is an example.

for i in range(5):
    if i%2 == 0:
        print i, "is an even",
    else:
        print i, "is an odd",
    print "number"
print "loop complete"

Let's step through this example in detail.

• The first line creates the for loop. The range is created using the "range" function described above.
• Everything within the for loop is indented. This is not optional! Python uses this indentation to figure out where the loop starts and ends. The notebook will help you: after you type the "for" line (ending with the colon), the next line will be indented appropriately.
• The "if" command takes a Boolean expression. As we saw before,  == denotes equality, as opposed to a single = which denotes an assignment.
• The "else" command is optional. Again, the indentation tells Python where the if and else clauses begin and end.
• The "print" command can take multiple arguments, and adds a line break unless you end it with a comma.

Here is another example, this time of a while loop. Note the effect of the "continue" and "break" statements.

t = 4
while t < 10:
    t += 1 ## has the same effect as t = t + 1
    if t%2 == 0:
        continue ## jump to the next iteration of the loop
    print t
    if t > 8:
        break ## jump out of the loop

5 7 9

Functions

By now, you have probably noticed that much Python functionality is provided via callable functions, such as "range". Sage extends this functionality by specifying many new advanced mathematical functions.

prime_pi(1000) ## The number of primes up to 1000

168

Sage includes a couple of handy techniques for inquiring about functions. One of these is tab completion: if you type part of the name of a function and hit Tab, Sage will attempt to complete the name of the function. On one hand, this can save a lot of typing.

charac

Perhaps more usefully, if more than one completion is possible, Sage will show you all possible completions; this can be a useful way to find out about what is available in Sage. (This technique is even more possible when applied to object methods; see below.)

ran

Another important inquiry technique is introspection: if one evaluates the name of a function followed by a ?, Python will show you a bit of documentation about that function. For instance, if you have forgotten how to specify a range other than 0, ..., n-1, we can use introspection on the range function.

range?

Python and Sage also allow for user-defined functions. As with variables, these may be defined in one cell and then used in later cell evaluations. (These will not admit introspection unless you do some extra work, but they will admit tab completion.)

def strange_sum(a, b):
    c = a+b
    return(a+b+c)

strange_sum(2, 3)

10

strange_sum

File: /tmp/tmpDTc7pM/___code___.py

Type: <type 'function'>

Definition: strange_sum(a, b)

Docstring:

x.__init__(...) initializes x; see x.__class__.__doc__ for signature

Mathematical objects in Sage

One important difference between Python and some lower-level programming languages like C is that Python is object-oriented. That is, besides the variables and functions that one can define globally, one can also create objects with their own variables and functions attached to them. In Sage, this framework is used to implement the construction of mathematical objects in a rigorous fashion which corresponds pretty well to the way mathematicians are used to thinking about these objects. For example, one can create such objects as the ring of integers and the field of rational numbers.

Z = IntegerRing()
Q = RationalField()

One can then feed these into more complicated constructions, like the ring of polynomials in a single variable.

R.<T> = PolynomialRing(Q)

In this example, we have created a polynomial ring over the rationals with a distinguished generator, to which we have assigned the name T. We can now generate elements of the ring R simply by writing down expressions in T.

 

poly = T^3 + 1
print poly.parent()
print poly.parent() == R

Univariate Polynomial Ring in T over Rational Field True

The "parent" command here is an example of a method of the object poly.

Now that we can make polynomials over the rationals, what can we do with them? An excellent way to find out is to use tab completion: if one types "poly." and then hits Tab, one is presented a list of all of the methods associated to poly.

poly.factor() ## can also be invoked as factor(poly)

(T + 1) * (T^2 - T + 1)

In the previous example, the "factor" method did not require any additional arguments. In other examples, one or more arguments may be required.

poly.xgcd(T-2) ## extended GCD; can also be invoked as xgcd(poly, T-2)

(1, 1/9, -1/9*T^2 - 2/9*T - 4/9)

This syntax might seem a bit strange: the extended GCD operation is essentially symmetric in its variables, so calling it in an asymmetric fashion may be counterintuitive. There is an extremely good reason for using the object-oriented syntax, namely tab completion. One can for instance type "poly." and his Tab to see the list of all of the methods associated to poly!

The ease of looking up the operations available on a given type of mathematical object is one of my favorite features of Sage. Even Magma, which has both object orientation and tab completion, fails on this point because functions are not viewed as object methods, but intsead all inhabit a single namespace.

poly.

As for bare functions, one can also type a few characters and get only the methods that start with the characters you type. For example, if you can't remember whether the method for factoring a polynomial is called "factor", "factorize", "factorise", "factorization", or "factorisation", you can check by doing a tab completion:

poly.factor

There can sometimes be some ambiguity about what the correct parent of a mathematical object should be. For instance, 3/4 is a rational number, but it can also be viewed as a polynomial over the rationals, e.g., when one wants to add or multiply it with another such polynomial. For the most part, Sage will take care of this for you automatically.

poly2 = poly + 3/4
print poly2.parent()

Univariate Polynomial Ring in T over Rational Field

Sometimes, however, one needs to make this change of parent explicit, e.g., in case one wants to call a method which exists for polynomials but not for rationals. For example, this fails:

poly2 = 3/4
poly2.coefficients()

Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_18.py", line 10, in <module> exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("cG9seTIgPSAzLzQKcG9seTIuY29lZmZpY2llbnRzKCk="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in <module> File "/tmp/tmpQVqB2i/___code___.py", line 4, in <module> exec compile(u'poly2.coefficients()' + '\n', '', 'single') File "", line 1, in <module> File "element.pyx", line 328, in sage.structure.element.Element.__getattr__ (sage/structure/element.c:2794) File "parent.pyx", line 277, in sage.structure.parent.getattr_from_other_class (sage/structure/parent.c:2940) File "parent.pyx", line 175, in sage.structure.parent.raise_attribute_error (sage/structure/parent.c:2709) AttributeError: 'sage.rings.rational.Rational' object has no attribute 'coefficients'

This change of parent (called coercion) is usually accomplished by the following syntax, which looks like plugging the element into the new parent viewed as a function.

poly2 = R(3/4)
poly2.coefficients()

[3/4]

Plotting

Sage has many more mathematical features than we can introduce here (but which are well-documented). One feature which will be used later is plotting of various kinds. (We only need 2D plotting her; there are also extremely cool 3D plotting capabilities, but you can discover those on your own.)

plot(sin, 0, pi) ## Plotting a built-in function

var('x') ## Define a symbolic variable named x
plot(x, (x, 0, 1)) ## Plot a function specified in terms of a symbolic variable

def f(x):
    return(x^2+1)
    
plot(f, -1, 1) ## Plot a user-defined function

plot(lambda x: x^2+1, -1, 1) ## Same thing using an inline function

plot([sin(x), cos(x)], (x, 0, pi/2)) ## Plot multiple functions on the same axes

scatter_plot([(x^2,x^3) for x in range(-5,5)]) ## plot a collection of points

Exception handling

This last point is a bit technical, but it will arise in the later lectures. As we saw earlier, if you make a mistake, Sage normally interrupts the computation to return an error message explaining what went wrong.

print (3 / (1-1))

Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_65.py", line 10, in <module> exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("cHJpbnQgMyAvICgxLTEp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in <module> File "/tmp/tmp3wJWzU/___code___.py", line 3, in <module> exec compile(u'print _sage_const_3 / (_sage_const_1 -_sage_const_1 )' + '\n', '', 'single') File "", line 1, in <module> File "element.pyx", line 1555, in sage.structure.element.RingElement.__div__ (sage/structure/element.c:12777) File "integer.pyx", line 1662, in sage.rings.integer.Integer._div_ (sage/rings/integer.c:11824) File "integer_ring.pyx", line 286, in sage.rings.integer_ring.IntegerRing_class._div (sage/rings/integer_ring.c:5195) ZeroDivisionError: Rational division by zero

One can explicitly create these errors as a debugging tool.

def f(n):
    if n < 0:
        raise ValueError, "Argument of f must be nonnegative"
    return(sqrt(n))
    
print f(1)
print f(-1)

1

Traceback (most recent call last): print f(-1) File "", line 1, in <module> File "/tmp/tmpCTqYxL/___code___.py", line 9, in <module> exec compile(u'print f(-_sage_const_1 )' + '\n', '', 'single') File "", line 1, in <module> File "/tmp/tmpCTqYxL/___code___.py", line 5, in f raise ValueError, "Argument of f must be nonnegative" ValueError: Argument of f must be nonnegative

One can also catch these errors to a limited extent, using the try and except commands.

def f(x,y):
    try:
        n = 1/x
        print "inversion complete"
        return(n + y[0])
    except ZeroDivisionError:
        return 0

print f(1, [2,3]) ## normal evaluation
print f(0, [4,5]) ## exception encountered, skipping the internal print statement
print f(2, []) ## this exception is not caught, so causes an error
print f(3, [3, 4]) ## we never get this far

inversion complete 3 0 inversion complete

Traceback (most recent call last): return 0 File "", line 1, in <module> File "/tmp/tmpYij_EM/___code___.py", line 13, in <module> print f(_sage_const_2 , []) ## this exception is not caught, so causes an error File "/tmp/tmpYij_EM/___code___.py", line 7, in f return(n + y[_sage_const_0 ]) IndexError: list index out of range

Conclusion: what else can Sage do?

To conclude, we point out a few more advanced things that can be accomplished using Sage, just to give the flavor of what the possibilities are. These are mostly complementary to the advanced functionality for elliptic curves that will be highlighted in the subsequent lectures.

• Communicate with other mathematical software. Sage itself ships with many well-regarded free software packages, such as Pari (number theory), Gap (group theory), Singular (commutative algebra), R (statistics), etc. Sage can also communicate with nonfree packages such as Mathematica, Maple, Matlab, and Magma if you have them installed. This means that you can access the power of many software packages while (mostly) only having to deal with one well-designed programming language!
• Communicate with TeX at various levels. For instance, any Sage object has a method that returns its representation in TeX. An even more spectacular example is SageTeX, a TeX package that allows your TeX document to pass inputs to Sage and retrieve the answers!
• Annotate notebooks by inserting formatted text and even TeX code between the cells, as in this presentation.