Group Actions and Burnside's Lemma

⚡ Key Takeaways

Group Actions and Burnside's Lemma — A group action is a homomorphism from a group $G$ into the symmetric group of a set $X$ , encoding symmetry as transformations. Burnside's Lemma (the Cauchy–Frobenius Lemma) counts the number of orbits as the average number of fixed points: $|X/G| = \frac{1}{|G|}\sum_{g\in G}|\mathrm{Fix}(g)|$ . Applies to combinatorial enumeration under symmetry (colorings of beads, faces, graphs). Originated with Cauchy (1845) and Frobenius (1887); popularized by Burnside (1897).

💡 The Core Insight

Symmetry partitions a set into orbits — clusters of elements interchangeable by the group. Counting orbits directly is awkward, but there is a beautiful double-counting bridge: the total number of (element, symmetry-that-fixes-it) incidences equals both the sum over elements of their stabilizer sizes and the sum over group elements of their fixed-point sets. Dividing by $|G|$ converts this into the headline formula — orbits = average fixed points.

DefinitionGroup Action

Let $G$ be a group with identity $e$ , and let $X$ be a set. A (left) group action of $G$ on $X$ is a function $\cdot : G \times X \to X$ , written $g \cdot x$ , satisfying:

1

\quad e \cdot x = x \quad \text{for all } x \in X

Derivation hint: The identity axiom; the neutral element must act as the identity transformation.

2

\quad g \cdot (h \cdot x) = (gh) \cdot x \quad \text{for all } g,h \in G,\ x \in X

Derivation hint: The compatibility axiom; acting by $h$ then $g$ equals acting by the product $gh$ . Here $G$ is the group, $X$ the underlying set, $g,h \in G$ group elements, $x \in X$ a point. An action is faithful if distinct group elements act as distinct permutations.

DefinitionPermutation Representation

Each $g \in G$ induces a map $\sigma_g : X \to X$ , $\sigma_g(x) = g\cdot x$ . Axioms [1]–[2] make $\sigma_g$ a bijection with inverse $\sigma_{g^{-1}}$ , and the assignment

3

\quad \sigma : G \to \mathrm{Sym}(X), \qquad \sigma(g) = \sigma_g

Derivation hint: $\sigma_g \circ \sigma_h = \sigma_{gh}$ follows from [2]; bijectivity from $\sigma_g \sigma_{g^{-1}} = \sigma_e = \mathrm{id}$ via [1]. is a group homomorphism. Conversely, every homomorphism $G \to \mathrm{Sym}(X)$ defines an action. Thus a group action IS a homomorphism into the symmetric group.

DefinitionOrbit and Stabilizer

For $x \in X$ :

4

\quad \mathrm{Orb}(x) = G\cdot x = \{\, g\cdot x : g \in G \,\} \subseteq X

Derivation hint: The orbit is the set of all points reachable from $x$ by group elements.

5

\quad \mathrm{Stab}(x) = G_x = \{\, g \in G : g\cdot x = x \,\} \le G

Derivation hint: $\mathrm{Stab}(x)$ is a subgroup — it contains $e$ and is closed under products and inverses by axioms [1]–[2]. The set of orbits is denoted $X/G$ , and $|X/G|$ is the number of orbits.

TheoremOrbit–Stabilizer Theorem

For a group $G$ acting on $X$ and any $x \in X$ , there is a bijection between the orbit of $x$ and the set of left cosets of its stabilizer:

6

\quad |\mathrm{Orb}(x)| = [G : \mathrm{Stab}(x)] = \frac{|G|}{|\mathrm{Stab}(x)|} \quad (\text{when } G \text{ finite})

Derivation hint: The map $g\,\mathrm{Stab}(x) \mapsto g\cdot x$ is a well-defined bijection from $G/\mathrm{Stab}(x)$ onto $\mathrm{Orb}(x)$ .

TheoremBurnside's Lemma / Cauchy–Frobenius Lemma

Let a finite group $G$ act on a finite set $X$ . For $g \in G$ let $\mathrm{Fix}(g) = \{\, x \in X : g\cdot x = x \,\}$ . Then the number of orbits is the average number of fixed points:

7

\quad |X/G| = \frac{1}{|G|}\sum_{g\in G} |\mathrm{Fix}(g)|

Derivation hint: Double-count the set $\{(g,x) : g\cdot x = x\}$ by summing over $g$ (gives $\sum|\mathrm{Fix}(g)|$ ) and over $x$ (gives $\sum|\mathrm{Stab}(x)|$ ), then apply orbit–stabilizer.

ProofProof of Burnside's Lemma

Define the incidence set

8

\quad S = \{\, (g,x) \in G\times X : g\cdot x = x \,\}

Derivation hint: $S$ collects all pairs of a symmetry and a point it fixes; we count $|S|$ two ways.

Step 1 — Count $S$ by summing over $g$ . Fixing $g$ first, the points $x$ paired with it are exactly $\mathrm{Fix}(g)$ :

9

\quad |S| = \sum_{g\in G} |\mathrm{Fix}(g)|

Derivation hint: Partition $S$ by its first coordinate $g$ ; the fiber over $g$ has size $|\mathrm{Fix}(g)|$ .

Step 2 — Count $S$ by summing over $x$ . Fixing $x$ first, the elements $g$ paired with it are exactly $\mathrm{Stab}(x)$ :

10

\quad |S| = \sum_{x\in X} |\mathrm{Stab}(x)|

Derivation hint: Partition $S$ by its second coordinate $x$ ; the fiber over $x$ has size $|\mathrm{Stab}(x)|$ .

Step 3 — Apply orbit–stabilizer. By [6], $|\mathrm{Stab}(x)| = |G|/|\mathrm{Orb}(x)|$ , so

11

\quad \sum_{x\in X} |\mathrm{Stab}(x)| = \sum_{x\in X} \frac{|G|}{|\mathrm{Orb}(x)|} = |G|\sum_{x\in X} \frac{1}{|\mathrm{Orb}(x)|}

Derivation hint: Substitute the orbit–stabilizer identity into [10] and factor out $|G|$ .

Step 4 — Sum the reciprocals orbit by orbit. Group the points of $X$ into their orbits $O_1,\dots,O_k$ (a disjoint partition). Within a single orbit $O_i$ , every point shares the same orbit size $|O_i|$ , so the points contribute $|O_i|\cdot\frac{1}{|O_i|} = 1$ :

12

\quad \sum_{x\in X}\frac{1}{|\mathrm{Orb}(x)|} = \sum_{i=1}^{k}\sum_{x\in O_i}\frac{1}{|O_i|} = \sum_{i=1}^{k} 1 = k = |X/G|

Derivation hint: Each orbit contributes exactly $1$ to the sum, so the total is the number of orbits.

Step 5 — Combine. Equate [9] with [11] using [12]:

13

\quad \sum_{g\in G}|\mathrm{Fix}(g)| = |G|\cdot |X/G| \;\Longrightarrow\; |X/G| = \frac{1}{|G|}\sum_{g\in G}|\mathrm{Fix}(g)| \qquad\blacksquare

Derivation hint: Divide both sides by $|G|$ to isolate the orbit count.

∎

mathematician · Ferdinand Georg Frobenius | 1849–1917

Frobenius proved the orbit-counting formula in 1887, well before Burnside's 1897 textbook (where it appears without attribution, leading to the durable misnomer "Burnside's Lemma"). Cauchy had stated the transitive case in 1845. Frobenius was a towering figure of the Berlin school: he founded character theory of finite groups with Issai Schur and Richard Dedekind, proved the Frobenius theorem on division algebras, and gave the modern treatment of group representations. Historians of mathematics often advocate the name Cauchy–Frobenius Lemma to credit the actual discoverers — Burnside himself attributed the result to Frobenius in his book.

🧠 Intuition

Picture coloring the four corners of a square with 2 colors. There are $2^4 = 16$ raw colorings, but many are "the same" if you allow rotating the square — rotating by $90°$ shouldn't produce a new necklace. The symmetry group (here, the rotation group $C_4$ ) acts on the 16 colorings, and orbits = genuinely distinct designs. To count orbits directly you would have to inspect each design and merge equivalents — tedious and error-prone. Burnside flips the problem: instead of asking "how many distinct designs?", ask "for each symmetry, how many designs does it leave untouched?" The identity fixes all 16; a $90°$ rotation only fixes monochrome designs (all corners equal), of which there are 2. Averaging these local counts over the whole group magically returns the global orbit count. The lemma works because each orbit, no matter its size, contributes exactly its "fair share" of $1$ when you weight by reciprocal orbit size — that is the content of Step 4.

Figure

A group action partitioning a set into orbits; arrows show how group elements move points within an orbit

ExampleNecklaces: 6 beads, 2 colors, rotations only

Given: Color the 6 beads of a circular necklace using black/white. The symmetry group is the cyclic group $C_6 = \{r^0,r^1,\dots,r^5\}$ of rotations. Count distinct necklaces.

Step 1 — Total colorings: $|X| = 2^6 = 64$ .

Step 2 — Fixed points of each rotation. A rotation $r^k$ permutes the 6 positions in cycles; a coloring is fixed iff all positions in each cycle share a color. The number of cycles of $r^k$ is $\gcd(6,k)$ , so $|\mathrm{Fix}(r^k)| = 2^{\gcd(6,k)}$ .

$k$	$\gcd(6,k)$	$\|\mathrm{Fix}(r^k)\| = 2^{\gcd}$
0	6	64
1	1	2
2	2	4
3	3	8
4	2	4
5	1	2

Step 3 — Apply Burnside [7]:

14

\quad |X/G| = \frac{1}{6}(64 + 2 + 4 + 8 + 4 + 2) = \frac{84}{6} = 14

Derivation hint: Sum the fixed-point column and divide by $|G| = 6$ .

Answer: $\boxed{14 \text{ distinct necklaces}}$ (no units — a pure count).

ExampleColoring cube faces with 3 colors

Given: Paint the 6 faces of a cube, each one of 3 colors. Two colorings are equivalent if related by a rotation of the cube. The rotation group has $|G| = 24$ . Count distinct cubes.

Step 1 — Total colorings: $|X| = 3^6 = 729$ .

Step 2 — Classify the 24 rotations by their cycle structure on faces, computing $\mathrm{Fix} = 3^{(\#\text{cycles})}$ :

Type	Count	Face cycle structure	#cycles	$\mathrm{Fix}=3^{\#}$
identity	1	$1^6$	6	729
face $90°,270°$	6	$1^2 4^1$	3	27
face $180°$	3	$1^2 2^2$	4	81
vertex $120°,240°$	8	$3^2$	2	9
edge $180°$	6	$2^3$	3	27

Step 3 — Weighted sum.

15

\quad \sum_g |\mathrm{Fix}(g)| = 1(729) + 6(27) + 3(81) + 8(9) + 6(27) = 729 + 162 + 243 + 72 + 162 = 1368

Derivation hint: Multiply each $\mathrm{Fix}$ value by the number of group elements of that type, then add.

Step 4 — Apply Burnside [7]:

16

\quad |X/G| = \frac{1368}{24} = 57

Derivation hint: Divide the total incidence count by $|G| = 24$ .

Answer: $\boxed{57 \text{ distinct colored cubes}}$ .

⚠️ Common mistake

The average must be an integer — but not because each term is. The right side of [7] divides $\sum|\mathrm{Fix}(g)|$ by $|G|$ and is guaranteed to come out a whole number, even though individual fixed-point counts and partial sums need not be divisible by $|G|$ . If your computation yields a non-integer, you have made an arithmetic error or miscounted a cycle structure.

Burnside requires finite $G$ and finite $X$ . The averaging $\frac{1}{|G|}\sum$ is meaningless for infinite groups; there are continuous analogues (averaging over a compact group with Haar measure) but they are not Burnside's Lemma.

$\mathrm{Fix}(g)$ is a subset of $X$ , not a subgroup. Beginners conflate $\mathrm{Fix}(g)$ (points fixed by a single $g$ ) with $\mathrm{Stab}(x)$ (group elements fixing a single $x$ ). The former lives in $X$ , the latter in $G$ . The proof's double-counting hinges on keeping them distinct.

Counterexample

The naive "divide by group size" shortcut fails. A tempting but wrong heuristic: "with $|X|$ colorings and $|G|$ symmetries, there are roughly $|X|/|G|$ orbits." For the 6-bead necklace this gives $64/6 \approx 10.67$ , but the true count is 14. The discrepancy arises because orbits have unequal sizes — symmetric colorings (like all-black) have small orbits, inflating the orbit count above the naive estimate. Only Burnside's careful averaging over fixed points, not over $X$ , gives the correct answer. The naive estimate is exact only when the action is free (every stabilizer trivial), so that all orbits have full size $|G|$ .

connection

Group actions are the connective tissue of algebra. The Orbit-Stabilizer Theorem underwrites the proof of Burnside and equally drives the Sylow Theorems (via groups acting on coset spaces and subgroup sets by conjugation). The conjugation action of $G$ on itself, $g\cdot x = gxg^{-1}$ , has orbits equal to Conjugacy Classes and stabilizers equal to centralizers — giving the class equation. Burnside's Lemma generalizes to the Pólya Enumeration Theorem, which refines fixed-point counting into a cycle-index polynomial that tracks how many beads of each color appear. The homomorphism viewpoint [3] connects to Cayley's Theorem (every group embeds in a symmetric group via the regular action) and to Group Representations (linear actions on vector spaces).

🔬 Where this appears

⏳ History

- 1845 — Augustin-Louis Cauchy states and uses the orbit-counting result in the special case of transitive permutation groups, in his memoirs on substitutions.

- 1849–1854 — Arthur Cayley introduces the abstract group concept and the regular representation, laying groundwork for actions as permutations.

- 1872 — Felix Klein's Erlangen Program reframes geometry as the study of invariants under group actions, elevating the action concept to a foundational principle.

- 1887 — Ferdinand Georg Frobenius proves the general orbit-counting lemma for arbitrary finite group actions — the true first appearance of [7].

- 1897 — William Burnside publishes Theory of Groups of Finite Order, stating the lemma (attributing it to Frobenius); the result later wrongly bears Burnside's name.

- 1927 — J. Howard Redfield discovers the generating-function refinement of orbit counting, anticipating Pólya, but his paper is overlooked for decades.

- 1937 — George Pólya independently develops the cycle-index / Pattern Inventory theorem, generalizing Burnside and applying it to chemical isomer counting; it becomes the Pólya Enumeration Theorem.

- 1960s–1970s — Historians (notably Peter Neumann) document the misattribution, popularizing the corrected name Cauchy–Frobenius Lemma, sometimes wryly called "the lemma that is not Burnside's."

- 1980s–present — Burnside/Pólya methods become standard in algorithmic combinatorics, computer algebra systems, and the enumeration of chemical and physical structures.

open-problem

Burnside's Lemma counts orbits but does not list representatives or describe orbit sizes — extracting one canonical element per orbit (the orbit problem / canonical form problem) can be computationally expensive, and for large symmetry groups (e.g. graph isomorphism) finding canonical representatives is far harder than counting. Pólya theory extends the count to a full generating function but still does not yield explicit representatives. For infinite groups acting on infinite sets, orbit counting requires measure-theoretic averaging over compact groups (Haar integration), and for non-compact groups there may be no meaningful finite count at all; the ergodic-theoretic study of orbit equivalence and orbit-counting in these settings remains a deep, active research area. Even the asymptotic growth of the number of unlabeled structures (graphs, hypergraphs) as $n\to\infty$ , where Burnside is the starting tool, connects to open enumeration questions.

Formal Statement

Why It Holds

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also