An introduction to Sage.
A Brief Introduction to Sage Math
This document aims to give a crash-course to Sage. There are many additional resources for help, including the built-in documentation (discussed below), the official Sage tutorial, and the (highly recommended) open textbook Computational Mathematics with SageMath.
Sage is free and open source. Information on running a local installation can be found on the Sage installation guide. Alternatively, Sage can be run "in the cloud" by making a (free) account on the CoCalc website.
This document is written as a Jupyer notebook, the most common (and convenient) way to write and execute Sage code. A notebook is composed of cells. Most of the cells in this notebook consist of an Input section (containing Sage code) and (potentially) an output section (containing the result of evaluating that Sage code) some code cells simply perform a computation without returning anything (for instance, updating the values of variables). A few cells (including the current one) consist of formatted text and LaTeX equations, written using the Markdown markup language. A third type of cell contains plain, unformatted text.
To execute a piece of Sage code, click on the Input section of the corresponding code cell and hit Shift + Enter (only hitting Enter simply adds a new line). The reader should execute each statement as they work through the notebook, and is encouraged to modify the code and play around as they go. Note that skipping a cell may result in errors when later cells are executed (for instance, if one skips a code block defining a variable and later tries to run code calling that variable). There are a selection of short exercises throughout, and a few larger exercises in the final section. To add a new cell, click to the left of any cell and press the "a" key. To delete a cell, click to the left of a cell and press the "d" key. These (and other) tasks can also be accomplished through the menu bars at the top of the page.
Additional details on the topics most closely related to combinatorics are covered in a follow-up notebook, available by clicking here.
Part 1: The Basics of Sage
We begin with an explanation of arithmetic in Sage, if statements, for and while loops, and Sage functions (in the programming sense; symbolic mathematical functions are described in Part 2 below).
Part 2: The Symbolic Ring and Sage Types
We now see how to manipulate symbolic variables and abstract functions, including basic calculus operations and plotting, and how to determine the type and parent of an object.
---------------------------------------------------------------------------
NameError Traceback (most recent call last)
/ext/sage/sage-9.1_1804/local/lib/python3.7/site-packages/sage/all_cmdline.py in <module>()
1 # Using any other (undeclared) variable will give an error
----> 2 poly2 = y**Integer(2) - Integer(1)
NameError: name 'y' is not defined
MAKE SURE YOU UNDERSTAND THIS CRUCIAL POINT: This behaviour occurs because Sage variables (for instance, x on the left hand side of x = 2) are distinct from the underlying symbolic variables used to define symbolic expressions. By default the Sage variable x is initialized to a symbolic variable "x", and the expression poly above is defined in terms of this symbolic variable. Changing the Sage variable x to a new value does nothing to the underlying symbolic variable "x", which is why the value of poly does not change after setting x = 2.
Part 3: Mathematical and Algebraic Objects (rings and fields, polynomials, and power series)
Working over the symbolic ring should be familiar anyone with experience in the Maple and Mathematica computer algebra packages. However, the separation of Sage variables from symbolic variables allows Sage great flexibility for defining and working with mathematical objects. In this section we discuss the different mathematical domains supported in Sage and how to define and work with mathematical objects.
Part 4: Linear Algebra
Part 5: Polynomial System Solving
Exercises
(Exercise 1)
An efficient method of computing high powers for an element of a ring is to use binary powering, through the formula Write a recursive function bin_pow(x,n)
which takes an element from a ring (your implementation should not care which) and a natural number and returns in approximately multiplications using binary powering.
(Exercise 2)
Recall again the Fibonacci numbers defined by the recursive formula for and . Show that the th Fibonacci number can be recovered from the matrix product Using the bin_pow
function from Exercise 1, find the one millionth Fibonacci number. If is the matrix being raised to the th power, the command print(timeit('bin_pow(M,1000000)'))
will measure the time it takes Sage to run this command. How does the time change if is defined over different rings (for instance, as a matrix over the integers, over the rationals, and over algebraic numbers)?
Note: Because Sage has built-in optimizations for powering a matrix, using your binary powering function may not be faster than running M^N
. However, your function should only be slower by a small constant amount of time (not changing much, if at all, with ).
(Exercise 3)
Create the field extension of the rational numbers obtained by adjoining an eigenvalue of the matrix from Exercise 2. Working over this field extension, diagonalize . Deduce an explicit expression for the th Fibonacci number.
(Exercise 4)
The fastest method of determining terms in a linearly recurrent sequence, such as the Fibonacci numbers, is not to use matrix powers (although this is much faster than naively using the recurrence). Instead, the idea is to compute powers of elements in a residue class ring defined by such a recurrence.
Skipping the details of why this works, define the residue class ring of polynomials in with rational coefficients modulo the polynomial . Let be the image of in this ring. Use Sage to compute the powers . Can you see how to recover the th Fibonacci number from ?
Use your bin_pow
method from Exercise 1 to compute the one millionth Fibonacci number using this approach. Use the timeit
command described above to compare the amount of time it takes to run bin_pow(xbar,1000000)
, bin_pow(M,1000000)
, and M^1000000
, where xbar
denotes and is the matrix from Exercise 2. Which is fastest?
(Exercise 5)
A simple random walk of length on the lattice is a sequence of steps from the set picked uniformly at random. Create a function which takes a natural number and returns a plot displaying a simple random walk of length . Create a plot overlaying the result of 100 random walks of length 100, each of a distinct colour.