Lecture 5 : Algebra

References:

• Introduction to Symbolic Computation, Lectures 11, 12, 28, 38, 40

• Group theory and Sage

• Polynomials in Sage

• Extensions of rings in Sage

Summary:
We start the lecture by recalling the useful sum and prod functions in Python, as well as more general iterators (in particular more fancy list comprehensions and tools for products of iterators). In the mathematical part, we begin by discussing (finite) groups and how to generate and identify them. Then we discuss polynomial rings and how to use them to study field extensions or ideals.

Python warmup : sum and prod

Two extremely useful constructions are the Python functions sum and prod for computing sums and products of elements in a list (or more general iterable). Here is the basic usage:

Combined with list comprehension:

We can in fact leave off the brackets above:

Apart from summing integers (or rational numbers, etc), we can in fact sum everything that has a + operation. In some of these cases, we should specify by hand the "neutral element" that sum should start with, which is given as a second argument (the default is the int 0):

A more interesting application of this last point:

Exercise

The Euler-Mascheroni constant is defined as the limit $$\gamma = \lim_{n \to \infty} \left(- \log(n) + \sum_{k=1}^n \frac{1}{k} \right) = \int_1^\infty \left(\frac{1}{\lfloor x \rfloor} - \frac{1}{x} \right) dx$$

Compute its approximation for $n=1000$ (alternatively: compute its first 4 digits) using the sum function. Remark: If you are done early, try to find out if SageMath has this constant stored somewhere.

Solution (uncomment to see)

As you can imagine, the function prod works much the same:

We can again take products of more general things. Here is an example: what do you think is the product of all elements in the symmetric group $S_3$?

The correct answer is: this depends on the order in which we multiply them! Just for fun, here is the set of all elements we can get like this (we'll see these constructions in more detail below and in the next lecture):

If you are interested in the question what elements you can get like this, have a look at the following answer to a question on math.stackexchange and the paper cited there.

Python warmup: more iterators

In this short section, we'll see a bunch of very useful constructions of iterators (used in for-loops or the constructions of lists).

First is a more general version of list comprehension that we have seen before. As a reminder, here is the basic version:

More generally, we can have multiple for in the list comprehension:

As you can see, the output is the list we would have obtained as follows:

result = []
for a in L:
    for b in L:
        result.append(a*b)

In particular, the order of the for-loops matters.

In addition we can have an if-condition at the end of the list comprehension. Elements are only added to the list if this comprehension is satisfied:

Exercise

Create the list of

• all integers $a$ between 100 and 200 satisfying $a\ \mathrm{mod}\ 3 = 2,\ a\ \mathrm{mod}\ 7 = 4$

• all entries of $\{0,1\}^3 = \{(0,0,0), (1,0,0), \ldots, (1,1,1)\}$

Solution (uncomment to see)

In the exercise above, if we had wanted to compute the list $\{0,1\}^{10}$, it would have required to write lots of for statements by hand. Instead, we can use the function itertools.product, which we need to import by hand as follows before using it:

The function product takes iterables A, B, ... and returns a generator that we would obtain from the code

((a,b,..) for a in A for b in B ...)

Here is a first example:

Given a list N of lists, the function product(*N) essentially computes the cartesian product of these lists (hence the name):

Exercise

Consider the following list $L$ of integers:

A variant of the Subset sum problem asks: what are the ways of writing the number $150$ as a sum $$a_1 + a_2 + a_3 + a_4 = 150,\quad (a_1, a_2, a_3, a_4 \in L)?$$ Find all such tuples.

Solution (uncomment to see)

Group theory

One of the fundamental objects in algebra are groups. These are abstractly defined as a tuple $(G, \circ)$ of a set $G$ and an operation $\circ : G \times G \to G$ satisfying certain axioms (associativity, existence of neutral and inverse elements).

While SageMath can work with some forms of infinite groups (in particular with finitely presented groups), we will mostly look at finite groups today. These are represented in SageMath as permutation groups, i.e. subgroups of some symmetric group $$S_n = \{\text{permutations of }\{1, \ldots, n\}\}$$ generated by some elements.

The full symmetric group $S_n$ is created as follows:

Let's look at a random element of $S_6$:

We see that it is represented in cycle notation. E.g. the element $(1,4)(2,3,6) \in S_6$ is the permutation sending $$1 \mapsto 4,\ 4 \mapsto 1,\ 2 \mapsto 3,\ 3 \mapsto 6,\ 6 \mapsto 2,\ 5 \mapsto 5.$$ If we want to create this particular element, this works as follows:

Alternatively, we use the following:

Now we can multiply, invert or raise elements to some power in the groups $S_6$:

¡Careful!
In SageMath, the convention is that given permutations a,b, the permutation a*b is the permutation obtained by first applying a and then applying b. This is different from the standard notation $a \circ b$ standing for first applying $b$ and then $a$. It leads to strange things as follows:

I must say that I find this a bit strange, but for many operations (computing inverses, subgroups generated by a subset, etc) this order does not really matter. You should just think of the SymmetricGroup(n) acting on the set $\{1, \ldots, n\}$ from the right.

Of course we can also create more general finite groups, some of which are given by pre-defined functions:

The phrase as a permutation group already indicates that the elements of these groups are specified by certain permutations, indicating that they are naturally seen as subgroups of some $S_n$. We can see this in an example by iterating through the group to look at its elements:

In many cases, it's sufficient to just have a look at the generators of the group, which we can obtain as follows:

Apart from the specific groups mentioned above, we can also create a group ourselves by generating it inside a symmetric group by a list of permutations:

Looking at a picture of a $5$-gon, we see that these two permutations correspond to a rotation and a reflection at the $y$-axis:

Thus we expect (and can confirm) that the group generated by them is equal to the dihedral group with $2 \cdot 5$ elements:

Let's use this to try identifying a concrete group:

Exercise

Here is a beautiful hand-drawn picture of a cube:

• Find a list of rotations which generate all symmetries of this cube in $\mathrm{SO}(3)$.

• Compute the subgroup $H$ of $S_8$ generated by the permutations these rotations induce on the corners of the cube.

• Find out what group it is and verify your answer with the is_isomorphic function.

Solution (uncomment to see)

Of course SageMath also knows about subgroups, their properties (like being normal) and quotient groups.

We can also list all subgroups of $G$ (possibly up to conjugation):

Exercise

An element $\sigma \in S_n$ is called a derangement if the permutation $\sigma$ of $\{1, \ldots, n\}$ has no fixed point, i.e. if $\sigma(i) \neq i$ for all $1 \leq i \leq n$. Denote by $D_n$ the number of derangements in $S_n$, so that $p_n = D_n/n!$ is the probability that a random permutation $\sigma \in S_n$ has no fixed points. Make some experiments and guess a formula for the limit of $p_n$ as $n \to \infty$.
Hint: Maybe look at some examples of $1/p_n$.

Suggested sub-exercises (uncomment to see)

Solution (uncomment to see)

We can also do some computations with group homomorphisms (though I would say this is less well-developed). To specify such a homomorphism from $G$ to $H$ , we need to specify the images of the generators of $G$. Let's try to construct a homomorphisms from $G = S_5$ to the cyclic group $H$ of order $4$:

I claim that there exists a homomorphism $\varphi : G \to H$ sending $(1,2,3,4,5)$ to the neutral element, and sending $(1,2)$ to the element $(1,3)(2,4)$:

Now we can compute image and kernel of this morphism and verify the first isomorphism theorem:

Given a group homomorphism $\varphi : G \to H$ we have $\mathrm{im}(\varphi) \cong G/\mathrm{ker}(\varphi)$.

There are many more properties of groups and their elements which can be checked or computed using SageMath (e.g. whether a group is abelian or simple, the order of an element, etc). For most of these, you should be able to find them simply by guessing the name and using Tab-completion, or by googling).

Finally, there are also libraries containing all isomorphism classes of groups of a given (small) order, in particular those of order at most 1023. This can be useful e.g. for checking a conjecture that you might have, or for trying to identify a given group. These libraries are implemented in the computer algebra system GAP, which SageMath uses in the background to do group theory computations.

When preparing this lecture, I found that there was not really a convenient way to access these databases, but based on this answer on math.stackexchange it is not so hard to write a function for this:

Exercise

The Feit-Thompson theorem states that every group of odd order is solvable. Check the theorem for orders at most 99.
Remark: A group $G$ is solvable if there exists a sequence of subgroups $$1 = G_0 < G_1 < \ldots < G_k = G$$ such that $G_{j-1}$ is normal in $G_j$ and such that the quotient $G_j / G_{j-1}$ is abelian for $j=1, \ldots, k$. However, you won't need to know this for solving the exercise ...

Solution (uncomment to see)

Just for fun, we finish with a nice picture: given a group $G$ with generating set $S$, the Cayley graph of $(G,S)$ is the oriented graph which has one vertex for each element of the group, and an oriented edge from $g$ to $gh$ for each $g \in G,h \in S$.

For a fun application of group theory: this lecture explains how to solve a Rubik's cube using SageMath (in fact, the interface of SageMath to GAP).

Polynomial rings and field extensions

Given a base ring $R$, we can create the polynomial ring $S = R[x_1, ..., x_n]$ over $R$, where we can choose the variable names freely. Here is an example with the base ring $R = \mathbb{Q}$:

Compared to symbolic expressions in the variables x,y, the polynomials in S have some additional functions (which don't make sense for general symbolic expressions):

Recall that an element $f$ of a ring $S$ is prime if $p \neq 0$ and $p$ is not a unit and whenever $p$ divides $a \cdot b$ for some $a,b \in S$ then $p$ divides $a$ or $p$ divides $b$.

Since $S = \mathbb{Q}[x,y]$ is a unique factorization domain, an element which is not prime must be reducible:

The construction S.<x,y,...> = PolynomialRing(QQ) automatically sets the variables x,y,... to be generators of the new ring S. We can also first create the ring abstractly, and then get our hands on the generators manually:

Exercise

Is the polynomial $f=X^8 + Y^8$ a prime element in

• $\mathbb{Q}[x,y]$

• $\mathbb{F}_2[x,y]$

If not, specify a factorization.

Solution (uncomment to see)

Given a polynomial, we can get access to its coefficients as follows:

Using polynomials, we can now also play around with finite field extensions. Recall that given a field $K$ and an irreducible polynomial $g \in K[x]$, the quotient $S = K[x]/(g)$ is a field extension of $K$ of order $\mathrm{deg}(g)$.

Since in the ring $S$ we adjoined a root of the polynomial $g$, it is no longer irreducible considered as an element of $S[x]$:

Exercise

Construct the following field extensions of $K = \mathbb{Q}$: $$L = K[x]/(x^2-2),\\ N = L[y]/(y^2-x).$$ Check that $L/K$ and $N/L$ are Galois extensions (use Tab-completion and the documentation via ? to find the right commands). Also check that $N/K$ is not Galois. This is the classical example showing that it's not true that the composition of two Galois extensions is Galois.
Bonus exercise: Find an irreducible polynomial $g \in \mathbb{Q}[x]$ which has a root in $N$ but does not split as a product of linear factors.

Solution (uncomment to see)

Speaking of Galois extensions: we can of course also compute the Galois group of a field extension, and it naturally operates on elements of the larger field:

Finally, we can create ideals in polynomial rings:

In the background, SageMath computes a so-called Gröbner basis of the ideal $J$. This is a particular set of generators of the ideal, such that there exist algorithms for answering questions like:

• is a given element of the polynomial ring contained in the ideal,

• are two ideals $J_1, J_2$ equal,

• what is the intersection $J_1 \cap J_2$ of two ideals, ...

In some cases, these can even be used to compute the solution set of a system of polynomial equations explicitly, in particular if this solution set is finite. Here is how we compute the solution set of the equations $$x^2 -y = 0, x^3 - x = 0$$ above, whose left-hand sides generate the ideal $J$:

These are really interesting topics and algorithms, but since this lecture focuses primarily on applications, we will not go further into details here.

Assignments

Exercise

Compute the following:

• the list of prime numbers between 100 and 200 which end in the digit '3'

• the number of matrices in $\mathrm{Mat}_{4 \times 4}(\mathbb{F}_2)$ which are invertible

Solution (uncomment to see)

Exercise

For a subgroup $G \subseteq S_n$ of $S_n$, denote by $$p(G) = \frac{|\{\sigma \in G: \sigma\text{ is a derangement}\}|}{|G|}\,.$$ The numbers $p_n$ from the first exercise about derangements above are exactly $p_n = p(S_n)$. Last year, my friend Kaloyan Slavov (working at ETH Zurich) and Bjorn Poonen showed the following fun theorem.

Theorem (PS21)
If a subgroup $G \subseteq S_n$ satisfies $p(G) = p_n$, then $G = S_n$.

Using clever arguments, they prove the theorem for $n \geq 12$, and for $n \leq 11$ they use a computer program written in Magma. However, Magma is neither free nor open source! Show them that SageMath can also be used to prove their theorem for $n \leq 11$!
Hint: We already had an exercise about derangements above, so you might be able to recycle some of your code there!

Solution (uncomment to see)

Exercise

Compute the splitting field $T$ of the polynomial $g = x^5 - 3 x^3 + x^2 -3 \in \mathbb{Q}[x]$ by iteratively adjoining roots of the polynomial to $\mathbb{Q}$. What is the degree of the field extension $T/\mathbb{Q}$?

Solution (uncomment to see)