Group Actions and Burnside's Lemma

A group action formalizes how groups encode symmetries by assigning each group element a permutation of a set
Burnside's Lemma: number of orbits = (1/|G|) Σ_{g∈G} |Fix(g)|, where Fix(g) is the set of elements fixed by g
Orbits partition a set into equivalence classes of elements related by group action; elements in same orbit are "equivalent"
Key insight: count fixed points under all symmetries and average, converting geometric problems into algebraic computation
Applications span combinatorics (distinct colorings, necklaces), graph theory, and enumerative combinatorics via Pólya theory
Historically discovered by Cauchy (1845) and Frobenius (1887), but commonly misattributed to Burnside's 1897 textbook

Group Actions and Burnside's Lemma

Overview

Group actions provide a powerful framework for understanding symmetry by formalizing how Group Theory|groups act on sets. Rather than viewing groups in isolation as abstract algebraic structures, group actions reveal how groups encode symmetries of geometric objects, combinatorial configurations, and other mathematical structures. A group action assigns to each group element a permutation of a set, subject to compatibility conditions that ensure the group structure is preserved. This perspective transforms abstract algebra into a concrete tool for counting, classification, and understanding structural properties.

The central counting theorem in this area, known as Burnside's Lemma (or the Cauchy-Frobenius Lemma), provides an elegant formula for counting distinct objects under symmetry. When a group acts on a finite set, elements that can be transformed into one another are considered equivalent—this partitions the set into orbits. Burnside's Lemma states that the number of orbits equals the average number of fixed points over all group elements. This simple formula has profound applications in Combinatorics, solving problems from counting distinct colorings of geometric objects to enumeration in Graph Theory.

Historically, this result was known to Cauchy (1845) and Frobenius (1887) before Burnside mentioned it in his 1897 textbook without proof. The common attribution to Burnside represents a historical irony—he neither discovered it nor claimed credit. Nevertheless, the lemma's power in solving symmetry-based counting problems has made it a cornerstone of Enumerative Combinatorics and Polya Theory.

When counting objects under symmetry, don't count each orbit individually—instead, count how many objects each symmetry fixes, then average over all symmetries. This converts a difficult geometric counting problem into straightforward algebra.

Group Action: Let

G

be a Group Theory|group and

X

a set. A (left) group action of

G

X

is a function

\cdot : G \times X \to X

, written

(g, x) \mapsto g \cdot x

, satisfying:

$e \cdot x = x$ for all $x \in X$ (identity axiom)
$g \cdot (h \cdot x) = (g h) \cdot x$ for all $g, h \in G$ and $x \in X$ (compatibility axiom)

For a group action $G$ on $X$ :

The orbit of $x \in X$ is $G \cdot x = {g \cdot x : g \in G}$
The stabilizer of $x \in X$ is $G_{x} = {g \in G : g \cdot x = x}$
The set of fixed points of $g \in G$ is $X^{g} = {x \in X : g \cdot x = x}$
An action is faithful if distinct group elements induce distinct permutations of $X$

Burnside's Lemma: If

G

is a finite group acting on a finite set

X

, then the number of orbits is

∣ Orb (X) ∣ = \frac{1}{∣ G ∣} g \in G \sum ∣ X^{g} ∣

Core Theory

Orbit-Stabilizer Theorem

Theorem [1] (Orbit-Stabilizer): Let

G

be a finite group acting on a set

X

, and let

x \in X

. Then

∣ G ∣ = ∣ G \cdot x ∣ \cdot ∣ G_{x} ∣

That is, the size of the orbit of

x

times the size of its stabilizer equals the group order.

Define $ϕ : G \to G \cdot x$ by $ϕ (g) = g \cdot x$ . We claim that $ϕ$ is surjective and that each element of $G \cdot x$ has exactly $∣ G_{x} ∣$ preimages.

Surjectivity: By definition of the orbit, every element of

G \cdot x

has the form

g \cdot x

for some

g \in G

, so

ϕ

is surjective. Fiber count: Consider

y = g \cdot x \in G \cdot x

. We count

∣ ϕ^{- 1} (y) ∣

. We have

h \in ϕ^{- 1} (y)

if and only if

h \cdot x = g \cdot x

. Applying

g^{- 1}

to both sides:

g^{- 1} h \cdot x = x

, which holds if and only if

g^{- 1} h \in G_{x}

. Thus

h \in g G_{x}

, the left coset of

G_{x}

containing

g

Conversely, if $h = g k$ for some $k \in G_{x}$ , then $h \cdot x = g (k \cdot x) = g \cdot x = y$ . Therefore $ϕ^{- 1} (y) = g G_{x}$ , which has cardinality $∣ G_{x} ∣$ by Lagrange's Theorem.

Since every element of $G \cdot x$ has exactly $∣ G_{x} ∣$ preimages under $ϕ$ , we have $∣ G ∣ = ∣ G \cdot x ∣ \cdot ∣ G_{x} ∣$ . □

Burnside's Lemma

Theorem [2] (Burnside's Lemma): Let

G

be a finite group acting on a finite set

X

. Then the number of orbits is

∣ Orb (X) ∣ = \frac{1}{∣ G ∣} g \in G \sum ∣ X^{g} ∣

We use a double-counting argument on the set $S = {(g, x) \in G \times X : g \cdot x = x}$ .

First count: For each

g \in G

, count pairs with first coordinate

g

. This gives

∣ S ∣ = g \in G \sum ∣ X^{g} ∣

Second count: For each

x \in X

, count pairs with second coordinate

x

. This gives

∣ S ∣ = x \in X \sum ∣ G_{x} ∣

By the Orbit-Stabilizer Theorem, $∣ G_{x} ∣ = ∣ G ∣/∣ G \cdot x ∣$ . Therefore:

∣ S ∣ = x \in X \sum \frac{∣ G ∣}{∣ G \cdot x ∣}

To evaluate this sum, partition $X$ into orbits $O_{1}, O_{2}, \dots, O_{k}$ . For each orbit $O_{i}$ , every element $x \in O_{i}$ has the same orbit size, namely $∣ O_{i} ∣$ . Thus:

∣ S ∣ = i = 1 \sum k x \in O_{i} \sum \frac{∣ G ∣}{∣ O _{i} ∣} = i = 1 \sum k ∣ O_{i} ∣ \cdot \frac{∣ G ∣}{∣ O _{i} ∣} = i = 1 \sum k ∣ G ∣ = k ∣ G ∣

Equating our two counts: $\sum_{g \in G} ∣ X^{g} ∣ = k ∣ G ∣$ . Therefore $k = \frac{1}{∣ G ∣} \sum_{g \in G} ∣ X^{g} ∣$ . □

Common Error: Burnside's Lemma applies to counting orbits, not individual elements. When solving a coloring problem, the answer is the number of distinct colorings under the group action, not the total number of ways to color. Also, the lemma requires the group action to be well-defined—verify both axioms! Many attempted applications fail because the proposed action doesn't satisfy

g (h \cdot x) = (g h) \cdot x

. William Burnside (1852-1927) — English mathematician who popularized this counting lemma in his influential 1897 textbook "Theory of Groups of Finite Order," though he credited the result to Frobenius and it was actually known earlier to Cauchy.

Examples and Applications

1

Counting Distinct Necklaces: How many distinct necklaces can be made with

n

beads, each colored with one of

k

colors, where two necklaces are the same if one can be rotated to obtain the other?

Let $X$ be the set of all $k^{n}$ colorings of $n$ positions, and let $G = C_{n}$ (the Cyclic Group of order $n$ ) act by rotation. The generator $r$ of $C_{n}$ rotates by $360°/ n$ , so $r^{j}$ rotates by $j \cdot 360°/ n$ .

For a coloring to be fixed by $r^{j}$ , it must have period dividing $j$ . Equivalently, the coloring must be constant on each of the $g cd (n, j)$ "cycles" created by $r^{j}$ . There are $k$ choices for each cycle's color, giving $∣ X^{r^{j}} ∣ = k^{g c d (n, j)}$ fixed points.

By Burnside's Lemma:

∣ Orb (X) ∣ = \frac{1}{n} j = 0 \sum n - 1 k^{g c d (n, j)}

For $n = 4, k = 2$ : The GCDs are $g cd (4, 0) = 4, g cd (4, 1) = 1, g cd (4, 2) = 2, g cd (4, 3) = 1$ .

∣ Orb (X) ∣ = \frac{1}{4} (2^{4} + 2^{1} + 2^{2} + 2^{1}) = \frac{16 + 2 + 4 + 2}{4} = 6

There are 6 distinct 4-bead necklaces with 2 colors.

2

Coloring Cube Faces: In how many distinguishable ways can the 6 faces of a cube be colored using 3 colors, where two colorings are the same if one can be rotated to obtain the other?

The Rotation Group of the cube has order 24 (the group of orientation-preserving symmetries). We classify rotations by type:

Identity: 1 element, fixes all $3^{6} = 729$ colorings
Face rotations (90° and 270° about axis through opposite face centers): 6 elements (3 axes, 2 rotations each), each fixes colorings where 4 faces in a cycle have the same color: $3^{3} = 27$ colorings
Face rotations (180°): 3 elements, each fixes colorings where opposite pairs match: $3^{4} = 81$ colorings
Edge rotations (180° about axis through opposite edge midpoints): 6 elements, each creates 3 pairs: $3^{3} = 27$ colorings
Vertex rotations (120° and 240° about axis through opposite vertices): 8 elements (4 axes, 2 rotations each), each creates 2 triples: $3^{2} = 9$ colorings

By Burnside's Lemma:

∣ Orb (X) ∣ = \frac{1}{24} (1 \cdot 729 + 6 \cdot 27 + 3 \cdot 81 + 6 \cdot 27 + 8 \cdot 9) = \frac{729 + 162 + 243 + 162 + 72}{24} = \frac{1368}{24} = 57

Why Finiteness Matters: Consider the action of

(Z, +)

on itself by translation:

n \cdot x = x + n

. Every orbit has the form

{x + n : n \in Z} = Z

, so there is exactly 1 orbit.

However, for each $n \in Z$ , the fixed point set is $X^{n} = {x : x + n = x} = \emptyset$ when $n \neq = 0$ , and $X^{0} = Z$ when $n = 0$ . The "Burnside average" is undefined since we cannot average over an infinite group.

More subtly, even if we could interpret $\frac{1}{∣ Z ∣} \sum_{n \in Z} ∣ X^{n} ∣$ formally (say, as 0), this doesn't equal the number of orbits (which is 1). Burnside's Lemma fundamentally requires finiteness of both $G$ and $X$ .

The Averaging Perspective: Imagine you're counting distinct patterns on a symmetric object. The naïve count overcounts because each distinct pattern appears multiple times (once for each symmetry that produces it). But how much overcounting occurs varies—patterns with more symmetry appear fewer times!

Burnside's Lemma sidesteps this complexity with a beautiful trick: instead of tracking each pattern's multiplicity, consider each symmetry operation and count what it doesn't change. The identity leaves everything fixed (contributes the total count), while other symmetries only fix special symmetric patterns. The average over all symmetries automatically weights by orbit sizes—high-symmetry patterns (small orbits) contribute more per orbit, exactly canceling their multiplicity. This transforms a hard combinatorial problem into straightforward algebra.

Historical Development

The lemma now known as Burnside's Lemma was first proved by Augustin-Louis Cauchy in 1845 in his work on permutation groups. Ferdinand Georg Frobenius rediscovered and published it in 1887 in his paper "Über die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul." William Burnside mentioned the result in his 1897 textbook Theory of Groups of Finite Order, attributing it to Frobenius but providing no proof.

The attribution to Burnside appears to stem from the influence of his widely-read textbook rather than original discovery. In the 1960s, several authors (notably John Howard Redfield and George Pólya) pointed out this historical inaccuracy, with some suggesting "Cauchy-Frobenius Lemma" as more appropriate. Despite this, "Burnside's Lemma" remains the standard name—a reminder that mathematical nomenclature often reflects textbook influence over historical priority.

The lemma gained prominence through Polya Enumeration Theory|Pólya's Enumeration Theorem (1937), which extends Burnside's counting technique using cycle indices to count objects by weight. This generalization transformed the lemma from a curiosity into a cornerstone of Enumerative Combinatorics, with applications spanning chemistry (counting isomers), computer science (symmetry reduction), and physics (statistical mechanics).

Connections to Other Areas

Representation Theory and Character Theory: Burnside's Lemma has a profound generalization in Representation Theory. The number of orbits equals the Inner Product of the trivial character with the Permutation Representation:

∣ Orb (X) ∣ = ⟨ χ_{X}, 1 ⟩

where

χ_{X} (g) = ∣ X^{g} ∣

is the character counting fixed points. This reveals that Burnside's Lemma is fundamentally about decomposing the permutation representation into Irreducible Representation|irreducibles—the number of orbits counts how many copies of the trivial representation appear. This connection bridges combinatorics with the deep structure theory of representations, enabling tools like Frobenius Reciprocity to solve counting problems.

Group Actions and Burnside's Lemma