Group Theory and Sage ¶

Author: Robert A. Beezer, University of Puget Sound

This compilation collects Sage commands that are useful for a student in an introductory course on group theory. It is not intended to teach Sage or to teach group theory. (There are many introductory texts on group theory and more information on Sage can be found via www.sagemath.org) Rather, by presenting commands roughly in the order a student would learn the corresponding mathematics they might be encouraged to experiment and learn more about mathematics and learn more about Sage. Not coincidentally, when Sage was the acronym SAGE, the “E” in Sage stood for “Experimentation.”

This guide is also distributed in PDF format and as a Sage worksheet. The worksheet version can be imported into the Sage notebook environment running in a web browser, and then the displayed chunks of code may be executed by Sage if one clicks on the small “evaluate” link below each cell, for a fully interactive experience. A PDF and Sage worksheet versions of this tutorial are available at http://abstract.ups.edu/sage-aata.html.

Changelog:

2009/01/30 Version 1.0, first complete release
2009/03/03 Version 1.1, added cyclic group size interact
2010/03/10 Version 1.3, dropped US on license, some edits.

Permutation groups ¶

A good portion of Sage’s support for group theory is based on routines from GAP (Groups, Algorithms, and Programming at https://www.gap-system.org. Groups can be described in many different ways, such as sets of matrices or sets of symbols subject to a few defining relations. A very concrete way to represent groups is via permutations (one-to-one and onto functions of the integers 1 through $n$), using function composition as the operation in the group. Sage has many routines designed to work with groups of this type and they are also a good way for those learning group theory to gain experience with the basic ideas of group theory. For both these reasons, we will concentrate on these types of groups.

Writing permutations¶

Sage uses “disjoint cycle notation” for permutations, see any introductory text on group theory (such as Judson, Section 4.1) for more on this. Composition occurs left to right, which is not what you might expect and is exactly the reverse of what Judson and many others use. (There are good reasons to support either direction, you just need to be certain you know which one is in play.) There are two ways to write the permutation $\sigma = (1\,3) (2\,5\,4)$:

As a text string (include quotes): "(1,3) (2,5,4)"
As a Python list of “tuples”: [(1,3), (2,5,4)]

Groups¶

Sage knows many popular groups as sets of permutations. More are listed below, but for starters, the full “symmetric group” of all possible permutations of 1 through $n$ can be built with the command SymmetricGroup(n).

Permutation elements Elements of a group can be created, and composed, as follows

Sage

sage: G = SymmetricGroup(5)
sage: sigma = G("(1,3) (2,5,4)")
sage: rho = G([(2,4), (1,5)])
sage: rho^(-1) * sigma * rho
(1,2,4)(3,5)

Python

>>> from sage.all import *
>>> G = SymmetricGroup(Integer(5))
>>> sigma = G("(1,3) (2,5,4)")
>>> rho = G([(Integer(2),Integer(4)), (Integer(1),Integer(5))])
>>> rho**(-Integer(1)) * sigma * rho
(1,2,4)(3,5)

Sage Live

G = SymmetricGroup(5)
sigma = G("(1,3) (2,5,4)")
rho = G([(2,4), (1,5)])
rho^(-1) * sigma * rho

Available functions for elements of a permutation group include finding the order of an element, i.e. for a permutation $\sigma$ the order is the smallest power of $k$ such that $\sigma^k$ equals the identity element $()$. For example:

Sage

sage: G = SymmetricGroup(5)
sage: sigma = G("(1,3) (2,5,4)")
sage: sigma.order()
6

Python

>>> from sage.all import *
>>> G = SymmetricGroup(Integer(5))
>>> sigma = G("(1,3) (2,5,4)")
>>> sigma.order()
6

Sage Live

G = SymmetricGroup(5)
sigma = G("(1,3) (2,5,4)")
sigma.order()

The sign of the permutation $\sigma$ is defined to be 1 for an even permutation and $-1$ for an odd permutation. For example:

Sage

sage: G = SymmetricGroup(5)
sage: sigma = G("(1,3) (2,5,4)")
sage: sigma.sign()
-1

Python

>>> from sage.all import *
>>> G = SymmetricGroup(Integer(5))
>>> sigma = G("(1,3) (2,5,4)")
>>> sigma.sign()
-1

Sage Live

G = SymmetricGroup(5)
sigma = G("(1,3) (2,5,4)")
sigma.sign()

since $\sigma$ is an odd permutation.

Many more available functions that can be applied to a permutation can be found via “tab-completion.” With sigma defined as an element of a permutation group, in a Sage cell, type sigma. (Note the “.”) and then press the Tab key. You will get a list of available functions (you may need to scroll down to see the whole list). Experiment and explore! It is what Sage is all about. You really cannot break anything.

Creating groups¶

This is an annotated list of some small well-known permutation groups that can be created simply in Sage. You can find more in the source code file SAGE_ROOT/src/sage/groups/perm_gps/permgroup_named.py.

SymmetricGroup(n): All $n!$ permutations on $n$ symbols.
DihedralGroup(n): Symmetries of an $n$-gon. Rotations and flips, $2n$ in total.
CyclicPermutationGroup(n): Rotations of an $n$-gon (no flips), $n$ in total.
AlternatingGroup(n): Alternating group on $n$ symbols having $n!/2$ elements.
KleinFourGroup(): The non-cyclic group of order 4.

Normal subgroups ¶

Checking normality¶

The code below:

begins with the alternating group $A_4$;
specifies three elements of the group (the three symmetries of the tetrahedron that are 180 degree rotations about axes through midpoints of opposite edges);
uses these three elements to generate a subgroup; and finally
illustrates the command for testing if the subgroup H is a normal subgroup of the group A4.

Sage

sage: A4 = AlternatingGroup(4)
sage: r1 = A4("(1,2) (3,4)")
sage: r2 = A4("(1,3) (2,4)")
sage: r3 = A4("(1,4) (2,3)")
sage: H = A4.subgroup([r1, r2, r3])
sage: H.is_normal(A4)
True

Python

>>> from sage.all import *
>>> A4 = AlternatingGroup(Integer(4))
>>> r1 = A4("(1,2) (3,4)")
>>> r2 = A4("(1,3) (2,4)")
>>> r3 = A4("(1,4) (2,3)")
>>> H = A4.subgroup([r1, r2, r3])
>>> H.is_normal(A4)
True

Sage Live

A4 = AlternatingGroup(4)
r1 = A4("(1,2) (3,4)")
r2 = A4("(1,3) (2,4)")
r3 = A4("(1,4) (2,3)")
H = A4.subgroup([r1, r2, r3])
H.is_normal(A4)

Quotient group¶

Extending the previous example, we can create the quotient (factor) group of $A_4$ by $H$. The commands

Sage

sage: A4 = AlternatingGroup(4)
sage: r1 = A4("(1,2) (3,4)")
sage: r2 = A4("(1,3) (2,4)")
sage: r3 = A4("(1,4) (2,3)")
sage: H = A4.subgroup([r1, r2, r3])
sage: A4.quotient(H)
Permutation Group with generators [(1,2,3)]

Python

>>> from sage.all import *
>>> A4 = AlternatingGroup(Integer(4))
>>> r1 = A4("(1,2) (3,4)")
>>> r2 = A4("(1,3) (2,4)")
>>> r3 = A4("(1,4) (2,3)")
>>> H = A4.subgroup([r1, r2, r3])
>>> A4.quotient(H)
Permutation Group with generators [(1,2,3)]

Sage Live

A4 = AlternatingGroup(4)
r1 = A4("(1,2) (3,4)")
r2 = A4("(1,3) (2,4)")
r3 = A4("(1,4) (2,3)")
H = A4.subgroup([r1, r2, r3])
A4.quotient(H)

returns a permutation group generated by (1,2,3). As expected this is a group of order 3. Notice that we do not get back a group of the actual cosets, but instead we get a group isomorphic to the factor group.

Simple groups¶

It is easy to check to see if a group is void of any normal subgroups. The commands

Sage

sage: AlternatingGroup(5).is_simple()
True
sage: AlternatingGroup(4).is_simple()
False

Python

>>> from sage.all import *
>>> AlternatingGroup(Integer(5)).is_simple()
True
>>> AlternatingGroup(Integer(4)).is_simple()
False

Sage Live

AlternatingGroup(5).is_simple()
AlternatingGroup(4).is_simple()

prints True and then False.

Composition series¶

For any group, it is easy to obtain a composition series. There is an element of randomness in the algorithm, so you may not always get the same results. (But the list of factor groups is unique, according to the Jordan-Hölder theorem.) Also, the subgroups generated sometimes have more generators than necessary, so you might want to “study” each subgroup carefully by checking properties like its order.

An interesting example is:

DihedralGroup(105).composition_series()

The output will be a list of 5 subgroups of $D_{105}$, each a normal subgroup of its predecessor.

Several other series are possible, such as the derived series. Use tab-completion to see the possibilities.

Conjugacy ¶

Given a group $G$, we can define a relation $\sim$ on $G$ by: for $a,b \in G$, $a \sim b$ if and only if there exists an element $g \in G$ such that $gag^{-1} = b$.

Since this is an equivalence relation, there is an associated partition of the elements of $G$ into equivalence classes. For this very important relation, the classes are known as “conjugacy classes.” A representative of each of these equivalence classes can be found as follows. Suppose G is a permutation group, then G.conjugacy_classes_representatives() will return a list of elements of $G$, one per conjugacy class.

Given an element $g \in G$, the “centralizer” of $g$ is the set $C(g) = \{h \in G \mid hgh^{-1} = g\}$, which is a subgroup of $G$. A theorem tells us that the size of each conjugacy class is the order of the group divided by the order of the centralizer of an element of the class. With the following code we can determine the size of the conjugacy classes of the full symmetric group on 5 symbols:

Sage

sage: G = SymmetricGroup(5)
sage: group_order = G.order()
sage: reps = G.conjugacy_classes_representatives()
sage: class_sizes = []
sage: for g in reps:
....:     class_sizes.append(group_order / G.centralizer(g).order())
...
sage: class_sizes
[1, 10, 15, 20, 20, 30, 24]

Python

>>> from sage.all import *
>>> G = SymmetricGroup(Integer(5))
>>> group_order = G.order()
>>> reps = G.conjugacy_classes_representatives()
>>> class_sizes = []
>>> for g in reps:
...     class_sizes.append(group_order / G.centralizer(g).order())
...
>>> class_sizes
[1, 10, 15, 20, 20, 30, 24]

Sage Live

G = SymmetricGroup(5)
group_order = G.order()
reps = G.conjugacy_classes_representatives()
class_sizes = []
for g in reps:
    class_sizes.append(group_order / G.centralizer(g).order())
class_sizes

This should produce the list [1, 10, 15, 20, 20, 30, 24] which you can check sums to 120, the order of the group. You might be able to produce this list by counting elements of the group $S_5$ with identical cycle structure (which will require a few simple combinatorial arguments).

Sylow subgroups ¶

Sylow’s Theorems assert the existence of certain subgroups. For example, if $p$ is a prime, and $p^r$ divides the order of a group $G$, then $G$ must have a subgroup of order $p^r$. Such a subgroup could be found among the output of the conjugacy_classes_subgroups() command by checking the orders of the subgroups produced. The map() command is a quick way to do this. The symmetric group on 7 symbols, $S_7$, has order $7! = 5040$ and is divisible by $2^4 = 16$. Let’s find one example of a subgroup of permutations on 4 symbols with order 16:

Sage

sage: G = SymmetricGroup(7)
sage: subgroups = G.conjugacy_classes_subgroups()
sage: list(map(order, subgroups))
[1, 2, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 5, 6, 6, 6, 6, 6, 6, 6, 6, 7, 8, 8, 8, 8, 8, 8, 8, 9, 10, 10, 10, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 14, 16, 18, 18, 18, 20, 20, 20, 21, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 36, 36, 36, 36, 40, 42, 48, 48, 48, 60, 60, 72, 72, 72, 72, 120, 120, 120, 120, 144, 168, 240, 360, 720, 2520, 5040]

Python

>>> from sage.all import *
>>> G = SymmetricGroup(Integer(7))
>>> subgroups = G.conjugacy_classes_subgroups()
>>> list(map(order, subgroups))
[1, 2, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 5, 6, 6, 6, 6, 6, 6, 6, 6, 7, 8, 8, 8, 8, 8, 8, 8, 9, 10, 10, 10, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 14, 16, 18, 18, 18, 20, 20, 20, 21, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 36, 36, 36, 36, 40, 42, 48, 48, 48, 60, 60, 72, 72, 72, 72, 120, 120, 120, 120, 144, 168, 240, 360, 720, 2520, 5040]

Sage Live

G = SymmetricGroup(7)
subgroups = G.conjugacy_classes_subgroups()
list(map(order, subgroups))

The map(order, subgroups) command will apply the order() function to each of the subgroups in the list subgroups. The output is thus a large list of the orders of many subgroups (96 to be precise). If you count carefully, you will see that the 49-th subgroup has order 16. You can retrieve this group for further study by referencing it as subgroups[48] (remember that counting starts at zero).

If $p^r$ is the highest power of $p$ to divide the order of $G$, then a subgroup of order $p^r$ is known as a “Sylow $p$-subgroup.” Sylow’s Theorems also say any two Sylow $p$-subgroups are conjugate, so the output of conjugacy_classes_subgroups() should only contain each Sylow $p$-subgroup once. But there is an easier way, sylow_subgroup(p) will return one. Notice that the argument of the command is just the prime $p$, not the full power $p^r$. Failure to use a prime will generate an informative error message.

Groups of small order as permutation groups ¶

We list here constructions, as permutation groups, for all of the groups of order less than 16.

---------------------------------------------------------------------------------------------
Size  Construction                                Notes
---------------------------------------------------------------------------------------------
1     SymmetricGroup(1)                           Trivial
2     SymmetricGroup(2)                           Also CyclicPermutationGroup(2)
3     CyclicPermutationGroup(3)                   Prime order
4     CyclicPermutationGroup(4)                   Cyclic
4     KleinFourGroup()                            Abelian, non-cyclic
5     CyclicPermutationGroup(5)                   Prime order
6     CyclicPermutationGroup(6)                   Cyclic
6     SymmetricGroup(3)                           Non-abelian, also DihedralGroup(3)
7     CyclicPermutationGroup(7)                   Prime order
8     CyclicPermutationGroup(8)                   Cyclic
8     D1 = CyclicPermutationGroup(4)
      D2 = CyclicPermutationGroup(2)
      G = direct_product_permgroups([D1,D2])      Abelian, non-cyclic
8     D1 = CyclicPermutationGroup(2)
      D2 = CyclicPermutationGroup(2)
      D3 = CyclicPermutationGroup(2)
      G = direct_product_permgroups([D1,D2,D3])   Abelian, non-cyclic
8     DihedralGroup(4)                            Non-abelian
8     QuaternionGroup()                           Quaternions, also DiCyclicGroup(2)
9     CyclicPermutationGroup(9)                   Cyclic
9     D1 = CyclicPermutationGroup(3)
      D2 = CyclicPermutationGroup(3)
      G = direct_product_permgroups([D1,D2])      Abelian, non-cyclic
10    CyclicPermutationGroup(10)                  Cyclic
10    DihedralGroup(5)                            Non-abelian
11    CyclicPermutationGroup(11)                  Prime order
12    CyclicPermutationGroup(12)                  Cyclic
12    D1 = CyclicPermutationGroup(6)
      D2 = CyclicPermutationGroup(2)
      G = direct_product_permgroups([D1,D2])      Abelian, non-cyclic
12    DihedralGroup(6)                            Non-abelian
12    AlternatingGroup(4)                         Non-abelian, symmetries of tetrahedron
12    DiCyclicGroup(3)                            Non-abelian
                                                  Also semi-direct  product $Z_3 \rtimes Z_4$
13    CyclicPermutationGroup(13)                  Prime order
14    CyclicPermutationGroup(14)                  Cyclic
14    DihedralGroup(7)                            Non-abelian
15    CyclicPermutationGroup(15)                  Cyclic
----------------------------------------------------------------------------------------------

Acknowledgements ¶

The construction of Sage is the work of many people, and the group theory portion is made possible by the extensive work of the creators of GAP. However, we will single out three people from the Sage team to thank for major contributions toward bringing you the group theory portion of Sage: David Joyner, William Stein, and Robert Bradshaw. Thanks!

Group Theory and Sage ¶

Basic properties of the integers ¶

Integer division¶

Greatest common divisor¶

Extended greatest common divisor¶

Divisibility¶

Factoring¶

Multiplicative inverse, modular arithmetic¶

Powers with modular arithmetic¶

Euler \(\phi\)-function¶

Primes¶

Permutation groups ¶

Writing permutations¶

Groups¶

Creating groups¶

Group functions ¶

Abelian?¶

Order¶

All elements¶

Cayley table¶

Center¶

Cayley graph¶

Subgroups ¶

Cyclic subgroups¶

Cyclic groups¶

All subgroups¶

Symmetry groups ¶

Symmetries of an equilateral triangle¶

Symmetries of an \(n\)-gon¶

Symmetries of a tetrahedron¶

Symmetries of a cube¶

Normal subgroups ¶

Checking normality¶

Quotient group¶

Simple groups¶

Composition series¶

Conjugacy ¶

Sylow subgroups ¶

Groups of small order as permutation groups ¶

Acknowledgements ¶