Symmetry and the idea of a group

Abstract algebra studies sets equipped with operations, and the rules those operations obey. That description sounds dry, but the subject grew out of very concrete questions: why there is a formula for the roots of a quadratic, a cubic and a quartic equation but none for a general quintic; why a crystal can have a fourfold axis of rotation but never a fivefold one; how many essentially different ways there are to color the faces of a cube; which positions of a Rubik's cube can be reached by turning its faces. Each of these questions turns out to be a question about symmetry, and the mathematical language of symmetry is the theory of groups.

This course is a first course in group theory. It assumes MATH-228 Introduction to Proofs, or an equivalent: you should be comfortable reading and writing proofs, with sets and functions, with equivalence relations and partitions, and with induction. Linear algebra (MATH-221) is useful for some examples but not required. The sequel, MATH-323 Abstract Algebra II, studies rings, fields and polynomials and ends with Galois theory, which answers the question about the quintic. Here we build the language and the main theorems of groups: subgroups, cosets and Lagrange's theorem, homomorphisms and quotients, the isomorphism theorems and group actions, ending with a capstone on counting with symmetry.

What is a symmetry?

Take a square cut from cardboard and lying in a square hole of the same size. A symmetry of the square is a way of picking it up and putting it back into the hole. You may rotate it, you may flip it over, but when you are finished it must fill the hole exactly. We do not care how the square moved in between; we care only about where each point ends up. So a symmetry is a function from the square to itself that preserves distances, a rigid motion, and that maps the square onto itself.

How many symmetries does a square have? Label the corners 1, 2, 3, 4 counterclockwise. A symmetry is determined by where it sends the corners, because a rigid motion is fixed once you know where it sends three points that are not on a line. Corner 1 can go to any of the four corners. Once corner 1 is placed, corner 2, which is adjacent to it, must go to one of the two corners adjacent to the new position of corner 1. After that everything is forced. So there are at most \(4 \cdot 2 = 8\) symmetries, and all eight actually occur: four rotations and four reflections.

• The rotations are by \(0^\circ\), \(90^\circ\), \(180^\circ\) and \(270^\circ\) counterclockwise about the center. Call them \(e\), \(r\), \(r^2\) and \(r^3\). The rotation by \(0^\circ\) does nothing; it is still a symmetry, the identity.

• The reflections are in the two diagonals and in the two lines through the midpoints of opposite sides. Reflecting is the same as flipping the cardboard over about that line.

Combining symmetries

The key observation is that symmetries can be combined. If you perform one symmetry and then another, the result is again a way of picking the square up and putting it back, so it is a symmetry. We write \(ab\) for the symmetry that does \(b\) first and then \(a\), the same convention used for composing functions: \((ab)(x) = a(b(x))\). For example \(r r = r^2\) is the half turn, and \(r^3 r = r^4 = e\), because four quarter turns bring every corner home.

Combining a rotation with a reflection gives a reflection, and combining two reflections gives a rotation. Try it with the cardboard square: flip it about the vertical line, then about a diagonal, and you will find that every corner has moved one place around the square, so the result is a quarter turn. This little experiment already shows something important. If \(s\) is the reflection in the vertical line and \(t\) the reflection in a diagonal, then \(ts\) and \(st\) are quarter turns in opposite directions. The order in which we combine symmetries matters: \(st \ne ts\).

Four properties of combining symmetries will turn out to be the whole story.

• Closure: combining two symmetries gives a symmetry.

• Associativity: for symmetries \(a, b, c\), doing \(c\), then \(b\), then \(a\) gives the same result however we group the steps, so \((ab)c = a(bc)\). This holds because composition of functions is associative.

• Identity: the do-nothing symmetry \(e\) satisfies \(ea = ae = a\) for every symmetry \(a\).

• Inverses: every symmetry \(a\) can be undone. There is a symmetry \(a^{-1}\) with \(a a^{-1} = a^{-1} a = e\). For a rotation by \(90^\circ\) the inverse is the rotation by \(270^\circ\); every reflection is its own inverse.

The definition of a group

A set together with a way of combining its elements that satisfies those four properties is called a group. The point of the definition is that these four properties, and nothing else about squares or rotations, are enough to prove a great many theorems, and those theorems then apply at once to every situation in which the four properties hold. Lesson 2 states the definition formally and gives many examples; here is a preview.

\[ \text{A group is a set } G \text{ with an operation } (a, b) \mapsto ab \text{ such that the operation is associative, there is an identity, and every element has an inverse.} \]

Closure is built in by saying that the operation takes two elements of \(G\) and returns an element of \(G\). The symmetries of the square form a group of 8 elements, called the dihedral group of order 8 and written \(D_4\) in this course; some books write \(D_8\), counting elements instead of corners. The symmetries of a regular \(n\)-gon form the dihedral group \(D_n\) with \(2n\) elements, studied in lesson 5.

Groups appear far beyond geometry. The integers under addition form a group: adding integers gives an integer, addition is associative, 0 is an identity, and the inverse of \(n\) is \(-n\). The nonzero real numbers under multiplication form a group, with identity 1 and inverse \(1/x\). The invertible \(2 \times 2\) real matrices under matrix multiplication form a group. The rearrangements of a deck of cards form a group under 'do one shuffle and then another'. In each case the elements are different kinds of objects and the operation means something different, but the four properties hold.

Symmetries as permutations

Because a symmetry of the square is determined by where it sends the corners, we can record it as a permutation of \(\{1, 2, 3, 4\}\): a bijection from the set to itself. The quarter turn \(r\) sends \(1 \mapsto 2\), \(2 \mapsto 3\), \(3 \mapsto 4\) and \(4 \mapsto 1\). Recording symmetries this way turns geometric questions into calculations a computer can do. The code below lists the six symmetries of an equilateral triangle as permutations of its corners, composes every pair and checks the four group properties by brute force.

from itertools import product

# a permutation of the corners 0, 1, 2 is stored as a tuple p with p[i] = image of i
e  = (0, 1, 2)
r  = (1, 2, 0)          # rotate 120 degrees: 0->1, 1->2, 2->0
r2 = (2, 0, 1)          # rotate 240 degrees
s0 = (0, 2, 1)          # reflect in the line through corner 0
s1 = (2, 1, 0)          # reflect in the line through corner 1
s2 = (1, 0, 2)          # reflect in the line through corner 2
names = {e: "e", r: "r", r2: "r2", s0: "s0", s1: "s1", s2: "s2"}
G = list(names)

def comp(a, b):
    """ab means: do b first, then a."""
    return tuple(a[b[i]] for i in range(3))

print("     " + " ".join(f"{names[b]:>3}" for b in G))
for a in G:
    print(f"{names[a]:>3}  " + " ".join(f"{names[comp(a, b)]:>3}" for b in G))

closed = all(comp(a, b) in names for a, b in product(G, G))
assoc = all(comp(comp(a, b), c) == comp(a, comp(b, c)) for a, b, c in product(G, G, G))
ident = all(comp(e, a) == a == comp(a, e) for a in G)
inv = all(any(comp(a, b) == e == comp(b, a) for b in G) for a in G)
print("closure", closed, "| associative", assoc, "| identity", ident, "| inverses", inv)
print("r s0 =", names[comp(r, s0)], "but s0 r =", names[comp(s0, r)])

       e   r  r2  s0  s1  s2
  e    e   r  r2  s0  s1  s2
  r    r  r2   e  s2  s0  s1
 r2   r2   e   r  s1  s2  s0
 s0   s0  s1  s2   e   r  r2
 s1   s1  s2  s0  r2   e   r
 s2   s2  s0  s1   r  r2   e
closure True | associative True | identity True | inverses True
r s0 = s2 but s0 r = s1

The output is the multiplication table, or Cayley table, of the group: the entry in row \(a\) and column \(b\) is \(ab\). In the output, every row and every column contains each element exactly once. That is not an accident of this example; lesson 2 proves it for every group. The last line shows that \(r s_0 \ne s_0 r\), so the order of combination matters here too.

Commutative and noncommutative groups

A group in which \(ab = ba\) for all elements \(a\) and \(b\) is called abelian, after the Norwegian mathematician Niels Henrik Abel, who proved in 1824 that the general quintic equation cannot be solved by radicals. The integers under addition and the rotations of the square on their own are abelian. The full symmetry group of the square or the triangle is not. Much of the difficulty, and much of the interest, of group theory comes from noncommutative groups, and you must train yourself not to assume \(ab = ba\) unless you have a reason. In particular \((ab)^{-1}\) is \(b^{-1}a^{-1}\), not \(a^{-1}b^{-1}\): to undo putting on socks and then shoes, you take off the shoes first.

A short history

Group theory has several roots. Joseph-Louis Lagrange studied, in 1770 and 1771, how the roots of a polynomial equation are rearranged by the formulas that solve it, and proved a special case of the theorem that now bears his name. Évariste Galois, before his death in a duel in 1832 at the age of 20, saw that the solvability of an equation depends on the structure of a group of permutations of its roots, and he was the first to use the word group in this sense. Augustin-Louis Cauchy developed the theory of permutations in the 1840s. Arthur Cayley gave the first abstract definition of a group in 1854, and in 1872 Felix Klein proposed in his Erlangen program that each kind of geometry is the study of the properties preserved by a group of transformations.

Meanwhile groups entered physics and chemistry. In 1891 Evgraf Fedorov and Arthur Schoenflies, working independently, classified the 230 space groups that describe the possible symmetries of crystals. Group theory is now a standard tool in quantum mechanics, in particle physics, where the symmetry groups of the fundamental forces organize the known particles, in chemistry, where the symmetry group of a molecule predicts which vibrations show up in its infrared spectrum, and in cryptography, where the security of many systems rests on calculations in very large groups.

A puzzle as a group

The Rubik's cube is a good example of a group that is easy to describe and hard to understand. The elements are the positions you can reach from the solved cube by turning faces, or equivalently the sequences of turns, where two sequences count as the same if they have the same effect. Combining means doing one sequence after another. The solved position is the identity, every sequence can be undone by doing the inverse turns in reverse order (exactly the rule \((ab)^{-1} = b^{-1}a^{-1}\)), and associativity holds because these are all rearrangements of the stickers.

The group has \(43\,252\,003\,274\,489\,856\,000\), about \(4.3 \times 10^{19}\), elements. Lessons 4 and 12 explain where that number comes from. It is not the number of ways to arrange the stickers, which is far larger, because some arrangements cannot be reached by turning faces: you cannot, for example, flip a single edge piece in place. Proving facts like that is exactly the kind of thing group theory is for. In 2010 a team using computer time donated by Google showed that every position can be solved in at most 20 face turns.

The plan of the course

The twelve lessons follow a standard path. Lessons 2 to 5 define groups and study the most important examples: the integers modulo \(n\), the symmetric groups of all permutations, and the dihedral groups of symmetries of polygons. Lesson 6 studies subgroups, the groups inside a group, and lesson 7 proves Lagrange's theorem: the size of a subgroup divides the size of the group. Lessons 8 to 10 study homomorphisms, the maps between groups that respect the operation, and the quotient groups and isomorphism theorems they lead to. Lesson 11 introduces group actions, which formalize the idea of a group of symmetries acting on a set, and lesson 12 uses actions to count colourings and patterns up to symmetry.

Every lesson includes runnable Python. Finite groups are ideal for experiment: a computer can check the group properties on a multiplication table, list subgroups, test conjectures and count orbits. As in MATH-228, experiments suggest what to prove, but only proofs settle questions. A pattern that holds for every group of order at most 30 may fail at order 32, and groups have a way of surprising people who generalize too quickly.