Lecture 3 : Numbers and symbolic expressions

References:

• Programming in Python and Sage

• Introduction to Symbolic Computation, Lectures 4, 5, 6, 7, 14 28

• Basic properties of the integers in Sage

Summary:
In todays lecture, we'll start with a reminder of conditional execution (if) and loop (for) in Python, and the datatype of dictionaries. Then we discuss various types of numbers in SageMath, such as integers, rationals, algebraic numbers and more. In the last part, we discuss symbolic expressions and how to use them to solve equations.

Python warmup : conditional execution (if/else)

Sometimes we want to perform some operations in our code (like computing the inverse of a matrix $A$) only if certain conditions are satisfied (the matrix $A$ is invertible), and maybe do something else otherwise (print a warning). This can be done in Python using the if/else construction:

Here the general pattern is:

if CONDITION:
    do_something()
    do_more_of_something()
else:
    do_something_else()
    maybe_more_of_something_else()

Note that the indentation (using a Tab = 4 spaces) is important!

Here CONDITION is an expressiong evaluating to a bool, which is either True or False. Basic ingredients for such conditions:

• A == B, A != B for checking equality (or not-equality)

• A <= B, A > B etc for comparisons of two values

• Logical operations: Cond1 and Cond2, Cond1 or Cond2, not Cond1

It is possible to omit the else part, in which case nothing is done if CONDITION is not satisfied.

Exercise

Given real parameters $p,q$ of the quadratic equation $$x^2 + p x + q = 0$$ write some code which prints the set of solutions $x \in \mathbb{R}$ (which you have to compute yourself, since solving equations only comes later in the lecture).

Hint: It's never too late in life to look at the formula for the solutions of a general quadratic equation.

Solution: (uncomment to see)

Note that we can have an if-block inside another if- or else-block, using double indentation (and so on):

Python warmup: for-loops

Sometimes we want to perform an operation for all $n$ in a range of values. This can be accomplished by a for-loop. As an example, below we compute the sum of the numbers $n=0,1, \ldots, 100$:

The general pattern is:

for n in ITERABLE:
    do_something()

Above, we have used range(N) as the ITERABLE, which outputs the numbers $0,1, \ldots, N-1$, which is why we had to take range(101) to sum from $0$ to $100$.

Exercise

Count for how many of the numbers $n=0,1, \ldots, 2022$ the value $\sin(n)$ is negative.

Solution (uncomment to see)

Similarly, we have the variations:

• range(N0, N) for the numbers $N_0, N_0+1, \ldots, N-1$,

• range(N0, N, d) for the numbers $N_0, N_0+d, N_0+2d, \ldots, N_0+k\cdot d$, where $k$ is maximal such that $N_0+k\cdot d<N$

Some more interesting examples:

Since we are not just using Python, but SageMath, we also have some cool iterables, like the symmetric group $S_n$ given by SymmetricGroup(n):

For more information about iterables, see this tutorial.

Python warmup: dictionaries

Dictionaries are a useful data structure in Python, which encodes a map from a finite set of objects to some other objects:

We can easily add new assignments to the dictionary (or change old ones):

There is also a connection to the for-loops we saw above: on the one hand, dictionaries are themselves Iterables:

On the other hand, similar to the constructions of lists like [k^2 for k in range(10)] that we already saw, we can also create dictionaries in this way:

Exercise

• Create dictionaries f,g implementing the maps $$f : \{1,2,3\} \to \{5,6\}, 1 \mapsto 5, 2 \mapsto 6, 3 \mapsto 5,\\ g : \{4,5,6\} \to \{7,8,9\}, 4 \mapsto 9, 5 \mapsto 8, 6 \mapsto 9.$$

• Create the dictionary h implementing the composition $g \circ f$.

Solution (uncomment to see)

Numbers

Last time, we already saw some interesting rings implemented in SageMath:

• ZZ the integers

• QQ the rational numbers

• RR the real numbers (floating point operations!)

• CC the complex numbers (floating point operations!)

• GF(q) the finite field $\mathbb{F}_q$ with $q$ elements

In this section, we will learn more about elements of these rings (commonly known as "numbers") and what we can do with them.

Integers

When we type an expression like 42 in SageMath, this will produce an Integer:

Integer division and remainder

Apart from the usual division a/b of two Integers (which mostly produces a Rational), we can also use a//b to compute the largest integer which is at most $a/b$:

The remainder (or modulus) of this division can be computed with a%b:

Exercise

Check whether the number $17^{17}-1$ is divisible by $3$.

Solution (uncomment to see)

Exercise

Compute the last $3$ digits of the integer $$a = (((2^2)^2)^\ldots)^2$$ where the number $2$ appears

• $5$ times, or

• $500$ times

in the formula for $a$.

Hint 1: Since the number of digits of an integer roughly doubles when taking its square, we can estimate that $a$ has more decimal digits than the number of atoms in the universe. Keep in mind that the code you use for solving the exercise must run on a computer which is part of the universe!
Hint 2: If you have ignored Hint 1, you probably at some point want to click on Kernel -> Interrupt in the menu to stop the computation, and maybe also on Kernel -> Restart to clear your memory.

Solution (uncomment to see)

Factorization

We can also compute the prime factorization of an integer:

To actually extract the information from this factorization, to use it in further computations, the following conversions are useful:

Exercise

Find the largest $m \geq 1$ such that the number $100!$ is divisible by $2^m$.

Solution (uncomment to see)

Conversely, we can look up the primes in the interval $[a,b-1]$ using primes(a,b):

Oops, this function returns a generator, i.e. an iterable that can be used in a for loop, without having to first compute all the numbers it will put out:

To just look at the numbers, you can convert this generator object into a list:

Python int vs. SageMath Integer

Remember the exercise from the first lecture to create a multiplication table of the integers from $1$ to $10$:

Let's see what happens instead if we wanted to create a division table:

By golly, what happened? It turns out that the integers that range spits out are actually of type int in Python, and not of type Integer:

Therefore, the division above is a division of int values, which returns a float:

To repair this, you can convert either numerator or denominator of the fraction into an Integer:

Thus a nice and mathematically accurate division table can be obtained as follows:

This type of conversion works more generally:

Exercise

An integer $a$ is a perfect power if there exist integers $b,e$ with $e>1$ such that $a=b^e$.

For the integers $1, \ldots, 20$ print line by line whether they are perfect powers or not, e.g. the output should start like this:

1 True
2 False
3 False
4 True
5 False
...

Solution (uncomment to see)

Rational numbers

If you want to do an exact computation with real numbers (e.g. in linear algebra), it is best when you can stay inside the rational numbers, since they have an exact representation as a fraction. Many operations we saw for Integers above work analogously for Rationals:

Some more useful functions (which also work for integers or real numbers):

Exercise

Among the numbers of the form $p/q$ for $p,q \in \{1, \ldots, 20\}$, which is closest to $\pi$?
Hint: Have a variable storing the best approximation you have so far, and when going through all numbers $p/q$ replace the current optimum if one of them comes closer.

Solution (uncomment to see)

Real and complex numbers

We already saw that RR and CC are the fields of real and complex numbers, implemented with floating-point arithmetic. In particular, the computations here are no longer exact:

Since we mostly talk about symbolic computations in this course, we won't go deeper into this topic for now, but here are some links where you can find more information:

• Computing with real numbers

• Fixed and Arbitrary Precision Numerical Fields

• Sage Quickstart for Numerical Analysis

Algebraic numbers

One nice field in which exact computations are possible is the field $\overline{\mathbb{Q}}$ of algebraic numbers. These are complex numbers which are a zero of some polynomial with rational coefficients. The unique such polynomial of minimal degree and with leading coefficient $1$ is called the minimal polynomial.

Then we can do things like taking roots of an algebraic number.

Even though below it is displayed as a decimal number, behind the scenes it still remembers its exact representation:

Then we can do fun things, like compute an expansion of a real algebraic number as a continued fraction:

This says that $$\sqrt{2} = 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2+ \ldots} }}$$ If you haven't seen it, it's a fun exercise to prove this!

Exercise

Compute the minimal polynomial and continued fraction of the golden ratio $$\phi = \frac{1 + \sqrt{5}}{2}\,.$$

Solution (uncomment to see)

Finite fields

Given a prime number $p$, there exists the finite field $$\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$$ of integers modulo $p$, which has precisely $p$ elements. More generally, for a prime power $q=p^r$, $(r \geq 1)$, there exists a unique field $\mathbb{F}_q$ with $q$ elements. It is not given by $\mathbb{Z}/q \mathbb{Z}$ though! Instead it is given as an extension $$\mathbb{F}_q = \mathbb{F}_p[z]/(f(z)),$$ where $z$ is a variable and $f \in \mathbb{F}_p[z]$ is an irreducible polynomial of degree $r$.

This finite field can be created in SageMath using FiniteField(q) (or GF(q) for short).

If we actually need to write elements of $\mathbb{F}_q$, we can use the following line to specify the variable used in the definition:

We can check e.g. that $z+z+z=0$, since $z+z+z = 3 \cdot z = 0 \cdot z = 0$, as $3 = 0 \in \mathbb{F}_{3^2}$.

We can also type formulas using standard integers like 17. Of course by default they give elements of type Integer, but SageMath is smart enough to convert them to elements of $\mathbb{F}_p \subseteq \mathbb{F}_q$. We are later going to see more about how this works.

And we can check which irreducible polynomial $f$ was used to define $\mathbb{F}_q = \mathbb{F}_p[z]/(f(z))$; SageMath automatically picks one for us:

Here is a cool exercise using finite fields, which hints at some quite deep mathematics:

Exercise

Given a prime power $q$, let $\mathbb{L}_q(f)$ be the set of solutions $(x,y,z) \in \mathbb{F}_q^3$ of the equation $$f = x^3 y - 3x^2 z^2 - yz + 4 \stackrel{\text{!}}{=} 0 \in \mathbb{F}_q.$$

• Compute the cardinality $|\mathbb{L}_2(f)|$ by going through all points in $\mathbb{F}_2^3$ and counting how many of them satisfy the equation.

• Compute the cardinality $|\mathbb{L}_q(f)|$ for a few more values of $q$ and then make a guess how it grows with $q$.
  Hint: There is a function in SageMath giving you a list of all prime powers $q$ up to $n-1$. Can you guess its name and confirm with Tab-completion?

Solution: (uncomment to see)

Symbolic expressions

We have already seen in some examples that SageMath can do computations involving formal variables. These happen in the so-called Symbolic Ring, which is denoted by SR in SageMath.

Creating and comparing symbolic expressions

To get started, we declare some variable names using the function var.

Then we can ask to perform operations, like expanding the formula we entered above:

We can also try to check whether two formulas are equivalent:

This is not restricted to algebraic equations:

Exercise

Try to check the following identities, some of which are true and some of which are false. Which one does SageMath get wrong? $$a \leq \max(a,b) \\ \exp(a) \cdot \exp(b) = \exp(a+b) \\ \frac{1}{\frac{1}{a}-\frac{1}{b}} = \frac{a \cdot b}{a - b} \\ \frac{1}{2}(a+b) \leq \max(a,b) \\ (a+b+c)^2 = a^2 + b^2 + c^2 + 2 \cdot(ab + ac + bc) \\ \sin\left(\frac{\pi}{4}\right) = \frac{1}{\sqrt{2}}$$

Solution (uncomment to see)

Substitution

We can make variable substitutions as follows:

Note that the argument of f.subs is a dictionary, sending variables appearing in f to their new values. Alternatively, we can treat f as if it was a function, and call it (but specifying the names of the variables as follows):

Formal sums

We can also evaluate some formal summations, e.g. the famous identity $$1 +2 + \ldots + n = \frac{n(n+1)}{2}$$ Indeed, to compute $$\sum_{a=a_0}^{a_1} f(a)$$ we use sum(f,a,a0,a1), where a is a variable and f is again a symbolic expression.

The answer is again a symbolic expression, so we can e.g. substitute some value for n or compute a further symbolic sum:

Solving equations

Maybe you have wondered why writing f == g for two symbolic expressions does not immediately give either True or False, but again a symbolic expression:

The reason is that we can now use this expression to state an equation (or a system of equations) that we want to solve:

The second argument is the variable for which we want to solve. To specify multiple equations (or inequalities) we give a list of these as the first argument of solve:

To get an output that can be used in further computations, we can specify the optional parameter solution_dict=True to obtain a list of dictionaries giving our solutions:

Finally, we can also solve for multiple variables:

Exercise

Solve the following (systems of) equalities for the variables $x,y,n,\ldots$: $$x^3 + 2 x^2 - 21 x + 18 = 0, \\ x^2 + p x + q = 0,\\ \sum_{k=0}^n 2^k = 4095\\ x^2 + y^2 = 1, x + y = 1$$

Solution (uncomment to see)

We can also add some assumptions about the variables:

Here is how we get rid of the assumptions again:

Assignments

Exercise

Given a number $d \in \{2,3, \ldots, 9\}$ here are the rules of a game named $d$-Blup:

The participants stand in a circle and count upwards starting from $1$, except that for every number either divisible by $d$ or ending on the digit $d$, they have to say "Blup" instead. If you say something wrong or take too long, you are out, and the others start again.

A correct $3$-Blup would start as follows:

Player  1 : "1"
Player  2 : "2"
Player  3 : "Blup"
Player  4 : "4"
...
Player 11 : "11"
Player 12 : "Blup"
Player 13 : "Blup"
...

Given d, write a program that prints the first 50 things the players need to say, i.e.

1
2
Blup
4
...

Hint: Recall that given integers a,b with b nonzero, you can compute the remainder of the division of a by b using a % b.

Solution: (uncomment to see)

Exercise

The Collatz conjecture states that for the function $$ f : \mathbb{Z}_{\geq 1} \to \mathbb{Z}_{\geq 1}, n \mapsto \begin{cases} 3n+1 & \text{for $nParseError: KaTeX parse error: Expected 'EOF', got '}' at position 5: odd}̲,\\ n/2 & \text…nParseError: KaTeX parse error: Expected 'EOF', got '}' at position 6: even}̲ \end{cases} $and any positive integer$n$, the sequence$n$,$f(n)$,$f(f(n))$,$\ldots$ eventually hits the number $1$. Test the Collatz conjecture for the first $100$ integers.
Hint: The while-loop

while CONDITION:
    do_something()

repeats the following code block until the CONDITION becomes False.

Solution (uncomment to see)

Exercise

The Pólya conjecture states that given a natural number $n>1$, there are among the set $$\{1, \ldots, n\}$$ at least as many elements with an odd number of prime factors as elements with an even number of prime factors. Here prime factors are counted with multiplicity, i.e. $12 = 2 \cdot 2 \cdot 3$ has $3$ prime factors according to this definition.

• Test the Pólya conjecture for the integers $2 \leq n \leq n_0$, for an $n_0$ of your choice.

• Google the Pólya conjecture.

Solution: (uncomment to see)

Exercise

Given an integer $c \geq 0$ let $T_c \subseteq \mathbb{Z}^2$ be the set of points in $\mathbb{Z}^2$ contained in the triangle spanned by $(0,0), (0,c), (c,0)$. Or in other words $$T_c = \{(x,y) \in \mathbb{Z}^2 : x,y \geq 0, x+y \leq c\}.$$ We claim that the function $$g : \mathbb{Z}_{\geq 0} \to \mathbb{Z}, c \mapsto \sum_{(x,y) \in T_c} x \cdot y$$ is given by a polynomial in $c$. Compute this polynomial and check your result in a few cases.

Solution (uncomment to see)