Sage Mathfest I

Introduction to Sage

Neil Calkin and Dan Warner

WWW.SAGEMATH.ORG

Mission Statement

Create a viable free open source alternative to Magma, Maple, Mathematica, and Matlab.

Summary:
Sage is about building the car instead of reinventing the wheel

1. Sage uses Python,  a mainstream programming language, instead of inventing a custom mathematics language
   
2. Use straightforward method to link programs together -- C library and pseudotty's, instead of XML servers/OpenMath.  We implement all conversion routines, instead of expecting upstream to do it: we make them communicate with Sage, whether they want to or not.
   
3. Give copious credit to contributors and be very developer friendly (easily build from source).
   
4. Reuse, improve, and contribute to existing libraries and projects (e.g., Scipy, Numpy, R, ATLAS, CVXopt, GSL), instead of starting over and competing with them.
   
5. Make the GUI using a web browser: the world of java and javascript is available and Sage integrates with the web.

Key take-away points: 

• FOSS: 100% free open source software: good for clusters, sharing, research, collaboration
• Python: very mainstream, scientific-computing friendly programming language
• Cython: optimized Python to C/C++ compiler we develop with support for C/C++ datatypes
• Interfaces: to control Matlab, Octave, Mathematica, etc., from Sage
• Self contained: can have many copies of Sage at once, so no "dependency hell"
  
• Peer reviewed: get your code refereed
• Web based: notebook interface

All aboard!

We want to pause and make sure that everyone can access Sage.

1. Access the Sage Server at  https://clemix.clemson.edu:34567
2. Install Sage on your machine, if not already downloaded get a flash drive with the correct version for your platform.

And now a short demo...

At this point we need to pause and look a little more carefully at how Sage works with Python.

First, Sage makes extensive use of classes

This example illustrated the fact that Python variables by default are "programming variables" and must be initialized. 

To create a symbolic variable we must declare the variable with the var command. 

The variable x is a special case for convenience.

This example illustrated the for loop in Python. 

First, the for statement walking through a list of objects and it ends with the colon. 

Second, the block inside the loop is indented.  There are no begin ... end constructs in Python. 

Good programming style strongly suggests that you indent subordinate blocks of code. 

Python insists that you indent and rewards you with shorter programs.

This example underscored the fact that the single "=" is assignment and the double "==" is equality.

It also showed that multiple statements can be on the same line when separated by ";"

In this example, the solution is returned in a list.  Lists are the principal data structure workhorse.

In this example we used the dictionary, which is the most sophisticated built-in data structure in Python.

Python Data Structures

The key data structures are: Lists, Tuples, and Dictionaries

Creating Lists I: [Square brackets]

Exercise: Create the list [63, 12, -10, 'a', 12], assign it to the variable L, and print the list.

Exercise: Create the empty list. (You will often need to do this.)

Creating Lists II: range

The range function provides an easy way to construct a list of integers. Here is the documentation of the range function.

range([start,] stop[, step]) -> list of integers

Return a list containing an arithmetic progression of integers.
range(i, j) returns [i, i+1, i+2, ..., j-1]; start (!) defaults to 0.
When step is given, it specifies the increment (or decrement).
For example, range(4) returns [0, 1, 2, 3].  The end point is omitted!
These are exactly the valid indices for a list of 4 elements.

Exercise: Use range to construct the list $[1,2,\ldots,50]$.

Exercise: Use range to construct the list of even numbers between 1 and 100 (including 100).

Exercise: The step argument for the range command can be negative. Use range to construct the list $[10, 7, 4, 1, -2]$.

Creating Lists III: list comprehensions

List comprehensions provide a concise way to create lists from other lists (or other data types). This technique is very similar to the mathematical notation for describing a set.

Example. We already know how to create the list $[1, 2, \ldots, 16]$:

range(1,17)

Using a list comprehension, we can create the list of even numbers as follows:

Using a list comprehension, we can also create the list $[1^2, 2^2, 3^2, ..., 16^2]$ as follows:

[i^2 for i in range(1,17)]

Exercise:

The sum of the squares of the first ten natural numbers is,

1² + 2² + ... + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Exercise: Use a list comprehension to list all the natural numbers below 20 that are multiples of 3 or 5.

Hints:

1. To get the remainder of 7 divided by 3 use 7%3.
2. To test for equality use two equal signs (==); for example, 3 == 7.

Nested list comprehensions

List comprehensions can be nested!

Examples:

Exercise: 

A Pythagorean triple is a triple $(x,y,z)$ of positive integers satisfying $x^2+y^2=z^2$. 

The Pythagorean triples whose components are at most $10$ are :  $[(3, 4, 5), (4, 3, 5), (6, 8, 10), (8, 6, 10)]$.

Using a filtered list comprehension, construct the list of Pythagorean triples whose components are at most $50$.

Accessing individual elements of lists

To access an element of the list, use the syntax L[i], where i is the index of the item.

Exercise: 

1. Construct the list L = [1,2,3,4,3,5,6]. What is L[3]?
2. What is L[1]?
3. What is the index of the first element of L?
4. What is L[-1]? What is L[-2]?
5. What is L.index(2)? What is L.index(3)?

Modifying lists: changing an element in a list

To change the item in position i of a list L:

Modifying lists: append and extend

To append an object to a list:

To extend a list by another list:

Modifying lists: reverse, sort, ...

Concatenating Lists

To concatenate two lists, add them (+). This is not a commutative operation....

Slicing Lists

You can slice a list using the syntax L[start : stop : step]. This will return a sublist of L.

Exercise: Below are some examples of slicing lists. Try to guess what the output will be before evaluating the cell.

Exercise: The following function combines a loop with the some of the list operations above. What does the function do?

Tuples

A tuple is an immutable list. That is, it cannot be changed once it is created.

The syntax for creating a tuple is to the use parentheses. 

We can create a tuple from a list, or vice-versa.

Tuples behave like lists in many respects:

Trying to modify a tuple will fail.

Generators

"Tuple-comprehension" does not exist.  The syntax produces something called a generator.  A generator allows you to process a sequence of items one at a time.  Each item is created when it is needed, and then forgotten.  This can be very efficient if we only need to use each item once.

g is now empty.

A nice 'pythonic' trick is to use generators as the argument to functions.  We do not need double parentheses for this.

Dictionaries

A dictionary is another built-in data type. Unlike lists, which are indexed by a range of numbers, dictionaries are "indexed" by keys, which can be any immutable object. Strings and numbers can always be keys (because they are immutable). Dictionaries are sometimes called "associative arrays" in other programming languages.

There are several ways to define dictionaries. One method is to use braces, {}, with comma-separated entries given in the form key:value.

Dictionaries behave as lists and tuples for several important operations.

A dictionary can have the same value multiple times, but each key can only appear once must be immutable.

Another way to add items to a dictionary is with the update() method:

We can iterate through the keys, or values, or both, of a dictionary.

Exercise: Consider the following directed graph. 

Create a dictionary whose keys are the vertices of the above directed graph, and whose values are the lists of the vertices that it points to. For instance, the vertex 1 points to the vertices 2 and 3, so the dictionary will look like:

d = { ..., 1:[2,3], ... }

Then try

g = DiGraph(d)

g.plot()

Using sage types: The srange command

Example:  Construct a $3 \times 3$ matrix whose $(i,j)$ entry is the rational number $\frac{i}{j}$.

Modifying lists has consequences!

Try to predict the results of the following commands.

Now try these:

You can use the command deepcopy to avoid these issues.

The same issues occur with dictionaries.

Some Sums

Let's now explore binomial expansions, Pascal's triangle, and more interesting sequences of sums.

Observation 1:

If we sum the first $N$ elements in column $k$ that sum will be the value of the element in the next row and column, namely, row $N+1$ and column $k+1$.

$\sum\limits_{n=k}^N P_{n,k} = P_{N+1,k+1}$

Since $P_{n,k} = \left( {\begin{array}{*{20}c} n \\ k \\ \end{array}} \right)$ this is the same as the statement

$\sum\limits_{n=k}^N \left( {\begin{array}{*{20}c} n \\ k \\ \end{array}} \right) = \left( {\begin{array}{*{20}c} N+1 \\ k+1 \\ \end{array}} \right)$

or, if we use the factorial definition of $n$ choose $k$

$\sum\limits_{n=k}^N \frac{n!}{(n-k)! k!} = \frac{(N+1)!}{(N-k)!(k+1)!}$

Actually, this observation holds for all cases, and the Theorem is easy to prove by mathematical induction. 

Observation 2:

Look at each row of Pascal's Triangle.  In all the cases in the Table, if $n$ is a prime (2, 3, 5, 7, 11), then $n$ divides all the entries in the row between the first and last, which are ones.  On the other hand, when $n$ is not a prime (4, 6, 8, 9, 10), then $n$ does not divide every entry in the row.  In particular, 4 doesn't divide 6; 6 doesn't divide 15 or 20; 8 doesn't divide 28; 9 doesn't divide 84; 10 doesn't divide 45; and 12 doesn't divide 66.

This observation also holds for all cases, and the result along with Eisenstein's criterion can be used to show that polynomials of the form

$x^{p-1} + x^{p-2} + \cdots + x + 1$

cannot be factored over the rational numbers when $p$ is a prime.