| Hosted by CoCalc | Download
Kernel: SageMath 9.1

Lecture 5 : Algebra

References:

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:

sum([3,-2,6])

Combined with list comprehension:

sum([i for i in range(1,101)])

We can in fact leave off the brackets above:

sum(i for i in range(1,101))

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):

sum([[1,2],[3,4]])
sum([[1,2],[3,4]], [])

A more interesting application of this last point:

sum([[3*i,3*i+1] for i in range(6)],[])

Exercise

The Euler-Mascheroni constant is defined as the limit γ=limn(log(n)+k=1n1k)=1(1x1x)dx \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

plot(1/floor(x), 1,12, color='red', fill=1/x) + plot(1/x, 1, 12)

Compute its approximation for n=1000n=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:

prod(i for i in range(1,51)) == factorial(50)

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 S3S_3?

S3 = list(SymmetricGroup(3)) prod(S3)

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):

{prod(p) for p in Permutations(S3)}

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:

L = [2,3,5,7] [a^2 for a in L]

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

[a*b for a in L for b in L]

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:

[a*b for a in L for b in L if a*b > 20]

Exercise

Create the list of

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

  • all entries of {0,1}3={(0,0,0),(1,0,0),,(1,1,1)}\{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\{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:

from itertools import product

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:

M = [0,1] list(product(M, ['a', 'b', 'c']))
list(product(M, repeat=3))

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

N = [M, M, ['a', 'b', 'c']] list(product(*N))

Exercise

Consider the following list LL of integers:

L = [17,23,31,32,44,59,61,63]

A variant of the Subset sum problem asks: what are the ways of writing the number 150150 as a sum a1+a2+a3+a4=150,(a1,a2,a3,a4L)? 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,)(G, \circ) of a set GG and an operation :G×GG\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 Sn={permutations of {1,,n}} S_n = \{\text{permutations of }\{1, \ldots, n\}\} generated by some elements.

The full symmetric group SnS_n is created as follows:

S6 = SymmetricGroup(6); S6

Let's look at a random element of S6S_6:

S6.random_element()

We see that it is represented in cycle notation. E.g. the element (1,4)(2,3,6)S6(1,4)(2,3,6) \in S_6 is the permutation sending 14, 41, 23, 36, 62, 55. 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:

cycle = ((1,4),(2,3,6)) a = S6(cycle); a
a(1)

Alternatively, we use the following:

b = S6("(1,3) (2,5,4)"); b

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

print(a*b) print([a^i for i in range(7)]) print(b.inverse())

¡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 aba \circ b standing for first applying bb and then aa. It leads to strange things as follows:

a(b(1))
(a*b)(1)
(b*a)(1)

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,,n}\{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:

CyclicPermutationGroup(5)
DihedralGroup(8)
A = AlternatingGroup(5); A
A.is_subgroup(SymmetricGroup(5))

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 SnS_n. We can see this in an example by iterating through the group to look at its elements:

H = DihedralGroup(3) for g in H: print(g)

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

H.gens()

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:

H = PermutationGroup([(1,2,3,4,5), ((2,5),(3,4))])

Looking at a picture of a 55-gon, we see that these two permutations correspond to a rotation and a reflection at the yy-axis: image.png

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

H.order()
H.is_isomorphic(DihedralGroup(5))

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

Exercise

Here is a beautiful hand-drawn picture of a cube: image.png

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

  • Compute the subgroup HH of S8S_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.

G = SymmetricGroup(3) a = G('(1,2,3)') H = G.subgroup([a]); H
H.is_normal()
G.quotient(H)

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

list(G.subgroups())
list(G.conjugacy_classes_subgroups())

Exercise

An element σSn\sigma \in S_n is called a derangement if the permutation σ\sigma of {1,,n}\{1, \ldots, n\} has no fixed point, i.e. if σ(i)i\sigma(i) \neq i for all 1in1 \leq i \leq n. Denote by DnD_n the number of derangements in SnS_n, so that pn=Dn/n!p_n = D_n/n! is the probability that a random permutation σSn\sigma \in S_n has no fixed points. Make some experiments and guess a formula for the limit of pnp_n as nn \to \infty.
Hint: Maybe look at some examples of 1/pn1/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 GG to HH , we need to specify the images of the generators of GG. Let's try to construct a homomorphisms from G=S5G = S_5 to the cyclic group HH of order 44:

G = SymmetricGroup(5) G.gens()
H = CyclicPermutationGroup(4) list(H)

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

phi = PermutationGroupMorphism_im_gens(G, H, [H('()'), H('(1,3)(2,4)')]); phi

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

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

im = phi.image(G); im
ker = phi.kernel(); ker
im.is_isomorphic(G.quotient(ker))

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:

def gap_group_to_SageMath(A): B = A.IsomorphismPermGroup() return PermutationGroup(gap_group = B.Image()) def groups_of_order(n): number = ZZ(gap.NumberSmallGroups(n)) # groups numbered from 1 to number return [gap_group_to_SageMath(gap.SmallGroup(n,i)) for i in range(1,number+1)]
groups_of_order(1)
groups_of_order(2)
groups_of_order(8)

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 GG is solvable if there exists a sequence of subgroups 1=G0<G1<<Gk=G 1 = G_0 < G_1 < \ldots < G_k = G such that Gj1G_{j-1} is normal in GjG_j and such that the quotient Gj/Gj1G_j / G_{j-1} is abelian for j=1,,kj=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 GG with generating set SS, the Cayley graph of (G,S)(G,S) is the oriented graph which has one vertex for each element of the group, and an oriented edge from gg to ghgh for each gG,hSg \in G,h \in S.

H = DihedralGroup(6) H.cayley_graph()

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 RR, we can create the polynomial ring S=R[x1,...,xn]S = R[x_1, ..., x_n] over RR, where we can choose the variable names freely. Here is an example with the base ring R=QR = \mathbb{Q}:

S.<x,y> = PolynomialRing(QQ) f = x^2 + 2*x*y + y^2

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):

f.degree()

Recall that an element ff of a ring SS is prime if p0p \neq 0 and pp is not a unit and whenever pp divides aba \cdot b for some a,bSa,b \in S then pp divides aa or pp divides bb.

f.is_prime()

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

factor(f)

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:

T = PolynomialRing(ZZ, 'x', 9); T
X = T.gens(); X
g = X[0]*X[1]; g

Exercise

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

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

  • F2[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:

S.<x,y> = PolynomialRing(QQ) f = x^2 + 2*x*y + y^2 + 17*x + 32 f.dict()

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

P.<x> = PolynomialRing(QQ) g = x^2 + 1 g.is_irreducible()
S.<i> = QQ.extension(g) S
S.degree()

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

Q.<x> = PolynomialRing(S) # the ring Q = S[x] gS = Q(g) # gS is the polynomial g = x^2 + 1 seen as an element of Q gS.is_irreducible()
factor(gS)

Exercise

Construct the following field extensions of K=QK = \mathbb{Q}: L=K[x]/(x22),N=L[y]/(y2x). L = K[x]/(x^2-2),\\ N = L[y]/(y^2-x). Check that L/KL/K and N/LN/L are Galois extensions (use Tab-completion and the documentation via ? to find the right commands). Also check that N/KN/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 gQ[x]g \in \mathbb{Q}[x] which has a root in NN 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:

P.<x> = PolynomialRing(QQ) g = x^2 + 1 S.<i> = QQ.extension(g)
G = S.galois_group(); G
list(G)
G[1](i)

Finally, we can create ideals in polynomial rings:

PR.<x,y> = PolynomialRing(QQ) f = x^2 - y g = x^3 - x J = Ideal([f,g]) J
y-x^4 in J
J.is_prime()
(y in J, y-1 in J)
y*(y-1) in J

In the background, SageMath computes a so-called Gröbner basis of the ideal JJ. 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 J1,J2J_1, J_2 equal,

  • what is the intersection J1J2J_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 x2y=0,x3x=0 x^2 -y = 0, x^3 - x = 0 above, whose left-hand sides generate the ideal JJ:

X = J.variety(QQ); X

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 Mat4×4(F2)\mathrm{Mat}_{4 \times 4}(\mathbb{F}_2) which are invertible

Solution (uncomment to see)

Exercise

For a subgroup GSnG \subseteq S_n of SnS_n, denote by p(G)={σG:σ is a derangement}G. p(G) = \frac{|\{\sigma \in G: \sigma\text{ is a derangement}\}|}{|G|}\,. The numbers pnp_n from the first exercise about derangements above are exactly pn=p(Sn)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 GSnG \subseteq S_n satisfies p(G)=pnp(G) = p_n, then G=SnG = S_n.

Using clever arguments, they prove the theorem for n12n \geq 12, and for n11n \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 n11n \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 TT of the polynomial g=x53x3+x23Q[x]g = x^5 - 3 x^3 + x^2 -3 \in \mathbb{Q}[x] by iteratively adjoining roots of the polynomial to Q\mathbb{Q}. What is the degree of the field extension T/QT/\mathbb{Q}?

Solution (uncomment to see)