Capstone: counting with symmetry and Burnside's lemma

Lesson 1 asked how many different necklaces can be made from beads of a few colours, when two necklaces that differ by a rotation or a flip count as the same. Questions of this kind, counting objects up to symmetry, appear in chemistry (how many isomers does a molecule have?), in combinatorics, in computer science and in puzzles. They are hard to answer by listing, because it is easy to count one object twice. This capstone lesson answers them with a single counting formula derived from the orbit–stabilizer theorem, and then brings the course together with a look at the group of the Rubik's cube.

The problem

Colour the four corners of a square, each black or white. There are \(2^4 = 16\) colourings, but many of them are the same pattern seen from a different angle. If we may rotate the square, how many genuinely different patterns are there? Listing them is still feasible: all white, all black, one black, three black, two adjacent black, two opposite black, giving 6. For a necklace of 12 beads in 4 colours there are \(4^{12} = 16{,}777{,}216\) colourings, and listing is hopeless.

The language of lesson 11 states the problem precisely. A symmetry group \(G\) acts on the set \(X\) of all colourings, and two colourings are 'the same pattern' when they lie in the same orbit. The number of patterns is the number of orbits.

Burnside's lemma

For \(g \in G\), let \(\operatorname{Fix}(g) = \{x \in X : g \cdot x = x\}\), the set of points left unchanged by \(g\).

Theorem (Burnside's lemma). If a finite group \(G\) acts on a finite set \(X\), the number of orbits is

\[ \frac{1}{|G|} \sum_{g \in G} |\operatorname{Fix}(g)|, \]

the average number of points fixed by an element of \(G\).

Proof: count the set of pairs \(P = \{(g, x) \in G \times X : g \cdot x = x\}\) in two ways. Grouping by \(g\), \(|P| = \sum_{g} |\operatorname{Fix}(g)|\). Grouping by \(x\), \(|P| = \sum_{x} |G_x|\). By orbit–stabilizer, \(|G_x| = |G|/|Gx|\), so

\[ |P| = |G| \sum_{x \in X} \frac{1}{|Gx|}. \]

Now split the last sum by orbits. An orbit \(\mathcal{O}\) contributes \(|\mathcal{O}|\) terms, each equal to \(1/|\mathcal{O}|\), for a total of 1. So the sum equals the number of orbits, and dividing by \(|G|\) gives the formula.

The name is a historical accident. William Burnside included the result in his 1897 book on finite groups, the first in English, and later writers attached his name to it. It had been known to Cauchy in 1845 and was published by Frobenius in 1887, which is why many authors call it the Cauchy–Frobenius lemma, and Peter Neumann once called it 'the lemma that is not Burnside's'.

The lemma is useful because \(\operatorname{Fix}(g)\) is usually easy to count. A colouring is fixed by a symmetry \(g\) exactly when it is constant on each cycle of the permutation \(g\) induces on the positions being coloured. So if \(g\) has \(c(g)\) cycles on the positions and there are \(k\) colours, \(|\operatorname{Fix}(g)| = k^{c(g)}\). The whole method reduces to finding the cycle types of the group elements, which lesson 4 taught.

Necklaces and bracelets

Consider \(n\) beads equally spaced on a circle, each one of \(k\) colours. Under rotations, the group \(C_n\) acts, and rotation by \(j\) positions splits the beads into \(\gcd(j, n)\) cycles, each of length \(n/\gcd(j, n)\). Burnside gives the number of necklaces

\[ N(n, k) = \frac{1}{n} \sum_{j=0}^{n-1} k^{\gcd(j, n)} = \frac{1}{n} \sum_{d \mid n} \varphi(d)\, k^{n/d}, \]

where the second form groups the rotations by their order \(d\): exactly \(\varphi(d)\) rotations have order \(d\) (lesson 3), and each has \(n/d\) cycles. For \(n = 6\), \(k = 3\):

\[ N(6, 3) = \tfrac{1}{6}(3^6 + 3^1 + 3^2 + 3^3 + 3^2 + 3^1) = \tfrac{780}{6} = 130. \]

If the necklace may also be turned over, the group is \(D_n\), and the patterns are often called bracelets. For \(n = 6\) there are three reflections through opposite beads, each with 4 cycles (two fixed beads and two swapped pairs), and three through opposite gaps, each with 3 cycles. With \(k = 3\) colours they fix \(3 \cdot 3^4 + 3 \cdot 3^3 = 243 + 81 = 324\) colourings in total, so the number of bracelets is \((780 + 324)/12 = 92\).

As a check on the formula, take \(n = p\) prime: \(N(p, k) = (k^p + (p - 1)k)/p\). Since this counts something, it is an integer, so \(p \mid k^p - k\). That is Fermat's little theorem again, proved this time by counting necklaces.

Colouring the faces of a cube

How many ways are there to paint the six faces of a cube with up to three colours, if two cubes that can be turned to look alike count as the same? The group is the rotation group of order 24 from lesson 11. Its elements fall into five types, and we count the cycles each type has on the six faces.

The counts \(1 + 6 + 3 + 8 + 6\) add to 24, as they must: 3 face axes each give two quarter turns and one half turn; 4 vertex axes each give two third turns; 6 edge axes each give one half turn. Burnside's lemma now gives

\[ \frac{1}{24}(k^6 + 3k^4 + 12k^3 + 8k^2) \]

distinct cubes. For \(k = 2\) that is \((64 + 48 + 96 + 32)/24 = 10\), and for \(k = 3\) it is \((729 + 243 + 324 + 72)/24 = 1368/24 = 57\).

The same method counts chemical isomers. Replacing two of the six hydrogen atoms of benzene by chlorine amounts to colouring two vertices of a hexagon, up to the symmetries of \(D_6\). There are \(\binom{6}{2} = 15\) colourings, and Burnside's lemma, or a short look, gives 3 orbits: the ortho, meta and para forms of dichlorobenzene, all of which are real compounds. George Pólya turned this approach into a general enumeration theorem in 1937, partly anticipated by J. H. Redfield in 1927, and used it to count families of chemical compounds.

Checking the counts by computer

Burnside's lemma replaces a search through all colourings by a sum over the group, which is much smaller. For small cases we can still do both and compare. The code below counts orbits directly, by picking out a canonical representative of each orbit, and by Burnside's formula, for square corners, necklaces and bracelets of six beads, and cube faces.

from itertools import product

def compose(a, b):
    return tuple(a[b[i]] for i in range(len(b)))

def generate(gens):
    e = tuple(range(len(gens[0])))
    G, frontier = {e}, [e]
    while frontier:
        new = []
        for g in frontier:
            for h in gens:
                x = compose(h, g)
                if x not in G:
                    G.add(x); new.append(x)
        frontier = new
    return G

def cycles(p):
    seen, c = set(), 0
    for i in range(len(p)):
        if i not in seen:
            c += 1
            while i not in seen:
                seen.add(i); i = p[i]
    return c

def orbits_direct(G, n, k):
    reps = set()
    for col in product(range(k), repeat=n):
        reps.add(min(tuple(col[g[i]] for i in range(n)) for g in G))
    return len(reps)

def orbits_burnside(G, k):
    return sum(k ** cycles(g) for g in G) // len(G)

def dihedral(n, flips=True):
    r = tuple((i + 1) % n for i in range(n))
    s = tuple((-i) % n for i in range(n))
    return generate([r, s] if flips else [r])

# faces of a cube: 0 top, 1 bottom, 2 front, 3 back, 4 left, 5 right
spin = (0, 1, 4, 5, 3, 2)          # quarter turn about the vertical axis
tip = (2, 3, 1, 0, 4, 5)           # quarter turn about the left-right axis
cube = generate([spin, tip])

cases = [("square corners, rotations", dihedral(4, False), 4, 2),
         ("square corners, D4", dihedral(4), 4, 2),
         ("6-bead necklaces, 3 colours", dihedral(6, False), 6, 3),
         ("6-bead bracelets, 3 colours", dihedral(6), 6, 3),
         ("cube faces, 2 colours", cube, 6, 2),
         ("cube faces, 3 colours", cube, 6, 3)]
for name, G, n, k in cases:
    print(f"{name:30s} |G| = {len(G):2d}  direct {orbits_direct(G, n, k):4d}  Burnside {orbits_burnside(G, k):4d}")

square corners, rotations      |G| =  4  direct    6  Burnside    6
square corners, D4             |G| =  8  direct    6  Burnside    6
6-bead necklaces, 3 colours    |G| =  6  direct  130  Burnside  130
6-bead bracelets, 3 colours    |G| = 12  direct   92  Burnside   92
cube faces, 2 colours          |G| = 24  direct   10  Burnside   10
cube faces, 3 colours          |G| = 24  direct   57  Burnside   57

The two columns agree in every case, and the cube's group, generated by two quarter turns, has the expected 24 elements.

The group of the Rubik's cube

The Rubik's cube, invented by Ernő Rubik in 1974, is a finite group in physical form. Its elements are the positions reachable from the solved state, and the product of two positions is the result of applying one sequence of moves after the other. The group is generated by the six quarter turns of the faces.

Its order can be found with the ideas of this course. The 8 corner pieces can be arranged in \(8!\) ways and twisted in \(3^8\) ways; the 12 edge pieces can be arranged in \(12!\) ways and flipped in \(2^{12}\) ways. Not all of these combinations are reachable. Every face turn is a 4-cycle on corners and a 4-cycle on edges, hence an odd permutation of each, so the parities of the corner and edge permutations are always equal: a homomorphism argument like the sign map of lesson 4 rules out half the arrangements. The total twist of the corners is always 0 modulo 3, and the total flip of the edges is always 0 modulo 2, ruling out further factors of 3 and 2. Conversely, everything not ruled out can be reached. So the order of the group is

\[ \frac{8! \cdot 3^8 \cdot 12! \cdot 2^{12}}{2 \cdot 3 \cdot 2} = 43{,}252{,}003{,}274{,}489{,}856{,}000 \approx 4.3 \times 10^{19}. \]

Each conservation law is the kernel of a homomorphism to a small abelian group, and the reachable group is the intersection of the kernels inside the group of all assembled positions, which has index 12. In 2010 a team led by Tomas Rokicki, using computer time donated by Google, showed that every position can be solved in at most 20 face turns, a number known as God's number; that is, the Cayley graph of the group with respect to the 18 face turns (quarter turns and half turns) has diameter 20.

Looking back and ahead

The course began with the symmetries of a triangle and a square and has arrived at a working theory. Groups are sets with an associative operation, an identity and inverses (lesson 2). The cyclic, dihedral and symmetric groups give the basic examples (lessons 3 to 5). Subgroups and cosets lead to Lagrange's theorem (lessons 6 and 7). Homomorphisms, normal subgroups and quotients relate groups to one another, organized by the isomorphism theorems (lessons 8 to 10). Group actions bring us back to symmetry with the orbit–stabilizer theorem and its consequences: the class equation, Cauchy's and Sylow's theorems, and Burnside's counting formula (lessons 11 and 12).

MATH-323 adds a second operation. Rings and fields, such as \(\mathbb{Z}\), the polynomials and the integers modulo a prime, have both addition and multiplication; their ideals play the role of normal subgroups, and the isomorphism theorems reappear almost word for word. The course culminates in Galois theory, which assigns to each polynomial a group of permutations of its roots and proves, using the simplicity of \(A_5\) from lesson 9, that the general quintic equation has no solution by radicals.