Intro to SageMath¶

Nadia Lafrenière¶

Dartmouth College (🇺🇸) $\xrightarrow{🚌}$ Concordia University (🇨🇦)¶

EAUMP-ICTP School on Enumerative Combinatorics¶

Arusha, Tanzania, July 24, 2023¶

What is Sage?¶

  • SAGE = System for Algebra and Geometry Experimentation
  • Open-source mathematical software
  • Works for all areas of math (even though some specific resources may exist outside of Sage)
  • Written in Python. Sage and Python have the same syntax.
  • Includes many existing software, from R (statistics) to Gap (group theory), PARI (number theory) to Maxima (symbolic computations). And of course, the Jupyter notebook

Open-source?¶

Open-source software must have four freedoms:

  • Freedom to use (for free)
  • Freedom to inspect how the program is built $\implies$ source code is available
  • Freedom to redistribute
  • Freedom to modify, then redistribute $\implies$ source code is available

The art of not reinventing the wheel¶

  • Many open-source mathematical software existed before Sage
  • Over 100 components (pre-existing software) are now in Sage, and included with its installation.

  • These libraries, softwares and databases are often very good and extensively used.

  • Sage interfaces with common mathematical databases

Python¶

  • General purpose programming language
  • Now ranked as the most popular programming language
  • Simple syntax, oriented-object and functional paradigms
  • Sage uses Python, and adds math functions to it

A community¶

  • SageMath Days
  • Virtual community: Volunteer developers from around the world

Sage for combinatorics¶

  • Huge community!
  • Not many other options for combinatorics: all developers contribute to SageMath
  • Very well developed: Sage knows way more math than any combinatorialist does!

Example of a combinatorial question¶

We can ask SageMath some simple questions, and it gives us the answer!

How many subsets of $\{1,2,...,6\}$ have no two consecutive numbers?

Example of a combinatorial question¶

How many subsets of $\{1,2,...,6\}$ have no two consecutive numbers?

In [1]:
# Very naive algorithm
n = 6
S = Set(range(1, n+1))  # range(a, b) gives all the integers between a and b-1, including the boundary
number_not_consecutive = 0
for E in S.subsets():
    has_consecutive = False
    for e in E:
        if e + 1 in E:
            has_consecutive = True
            break  # to make the execution of the code shorter (will not ask for all e in E)
    if not has_consecutive:
        number_not_consecutive += 1  # Add 1 to number_not_consecutive
number_not_consecutive
Out[1]:
21

Example of a combinatorial question¶

We can generalize this question:

How many subsets of $\{1,2,...,n\}$ have no two consecutive numbers?

In [2]:
# Very naive algorithm
sequence_no_consecutive = []
for n in range(10):
    S = Set(range(1, n+1))  # range(a, b) gives all the integers between a and b-1, including the boundary
    number_not_consecutive = 0
    for E in S.subsets():
        has_consecutive = False
        for e in E:
            if e + 1 in E:
                has_consecutive = True
                break  # to make the execution of the code shorter (will not ask for all e in E)
        if not has_consecutive:
            number_not_consecutive += 1  # Add 1 to number_not_consecutive
    sequence_no_consecutive.append(number_not_consecutive)
print(sequence_no_consecutive)
[1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

Example of a combinatorial question¶

What is this sequence?

In [3]:
# What is this sequence?
oeis(sequence_no_consecutive)
Out[3]:
0: A000045: Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.
1: A212804: Expansion of (1 - x)/(1 - x - x^2).
2: A104763: Triangle read by rows: Fibonacci(1), Fibonacci(2), ..., Fibonacci(n) in row n.
In [4]:
# Is it really counted by the Fibonacci numbers?!
oeis.browse()

Exploring SageMath's code¶

We can look up the documentation, and explore SageMath's code, right from the interface!

Example (for which you don't even need to know the math!)

How many (integer) partitions of 13 have only parts at most 3?

In [1]:
Partitions?
In [6]:
len(Partitions(13, max_part=3))
Out[6]:
21

Exploring SageMath's code¶

Notice that we did not even need to know what a partition or a part is to solve this problem. But it is always good to know what you are doing (as a piece of advice...)

An integer partition (often just called a partition) of the number $n$ is a decreasing list of positive integers whose sum is $n$.

For example, $(2,1,1)$ is a partition of $4$.

Exploring SageMath's code¶

How are partitions counted, anyway? We can read the source code by using ??.

In [2]:
number_of_partitions??

The code refers to the algorithm 'FLINT', which stands for Fast Library for Number Theory. This means that it uses external code (that is included in Sage anyway), but this code might be written in another programming language.

We can verify that this is a fast algorithm, by asking Sage how long it takes to count partitions of 1000.

In [8]:
%time number_of_partitions(1000)
CPU times: user 575 µs, sys: 76 µs, total: 651 µs
Wall time: 2.23 ms
Out[8]:
24061467864032622473692149727991

The algorithm is very fast to count all 24061467864032622473692149727991 partitions of 1,000.

Let us compare it with the method that enumerates all partitions, then counts them.

In [9]:
%time len(Partitions(1000))
---------------------------------------------------------------------------
OverflowError                             Traceback (most recent call last)
File <timed eval>:1

OverflowError: cannot fit 'int' into an index-sized integer

There are too many partitions of 1,000 to store them before counting them.

Combinatorial explosion¶

The size of many combinatorial sets grows very rapidly. This is called the combinatorial explosion. It means that there exists a threshold where obtaining data is impossible. It can be because:

  • It takes too long.
  • It takes more memory (storage) than what our computer has.
In [10]:
print(f"There are {number_of_partitions(10)} partitions of 10, and {number_of_partitions(100)} partitions of 100.")
print(f"There are {factorial(4)} permutations of 4, and {factorial(10)} permutations of 10.")
There are 42 partitions of 10, and 190569292 partitions of 100.
There are 24 permutations of 4, and 3628800 permutations of 10.

Algorithms that are already in SageMath are often, not always, optimized to use just what is needed of memory and time.

If you want to do "large" computations, you have to be mindful of the limitations of your machine.

Before you go...¶

Asking for help with SageMath:

  • Enter the name of the function, and add a question mark. This displays the documentation. Example: number of partitions?
  • Enter the name of the function, and add two question marks. This displays the source code. Example: number of partitions??
  • Ask SageMath: https://ask.sagemath.org/ is a forum where people ask questions about Sage. Your question might have been asked before! You can also ask questions, but then you have to wait for the answer.
  • There are a lot of information in the SageMath tutorials https://doc.sagemath.org/html/en/tutorial/, but sometimes too much, and it can be hard to find what you are looking for.
  • And as with many things, sometimes an internet search goes a long way. Make sure to enter SageMath, as there is a popular software also called Sage that is used for accounting.

Wrap-up¶

Why I use SageMath?

  • Because I'm lazy, and my computer can perform my computations faster and more accurately than me
  • To learn about cutting-edge math, since the documentation and code usually contain the best algorithms.
  • To explore how large some quantities are, to make conjectures, and sometimes as authority in a conversation or with students