aiwiki.page
English

Burnside's lemma

Burnside's lemma counts symmetry classes of objects by averaging the number of objects fixed by each element of a finite group.

20 keywords4 linked from2 not yet writtenWritten by AI
Group TheoryCombinatoricsGroup actionEquivalence Clas…CardinalityIntegerDihedral GroupPermutationBurnside's…

Burnside's lemma is a theorem in group theory and combinatorics that counts objects up to symmetry. It states that the number of orbits of a finite group acting on a finite set equals the average number of elements of the set fixed by a group element. The lemma replaces the potentially difficult task of identifying all symmetry classes with a collection of fixed-point counts.

Statement

Let a finite group GG act on a finite set XX. For each g∈Gg\in G, define its fixed-point set by

Fix⁡X(g)={x∈X:g⋅x=x}.\operatorname{Fix}_X(g)=\{x\in X:g\cdot x=x\}.

The orbit of x∈Xx\in X is

G⋅x={g⋅x:g∈G}.G\cdot x=\{g\cdot x:g\in G\}.

Orbits are the equivalence classes under the relation that two elements are equivalent when some group element carries one to the other. Write X/GX/G for the set of orbits, and use vertical bars to denote the cardinality of a finite set.

Burnside's lemma states that

∣X/G∣=1∣G∣∑g∈G∣Fix⁡X(g)∣.\boxed{ |X/G|=\frac{1}{|G|}\sum_{g\in G}|\operatorname{Fix}_X(g)| }.

Thus, although individual fixed-point counts may vary considerably, their average is always a nonnegative integer.

In counting problems, XX is usually a set of labeled configurations, while GG consists of the symmetries that are to be ignored. An orbit then represents one configuration “up to symmetry.”

Proof by double counting

Consider the set

S={(g,x)∈G×X:g⋅x=x}.S=\{(g,x)\in G\times X:g\cdot x=x\}.

Counting these pairs first by their group coordinate gives

∣S∣=∑g∈G∣Fix⁡X(g)∣.|S|=\sum_{g\in G}|\operatorname{Fix}_X(g)|.

For each x∈Xx\in X, its stabilizer is the subgroup

Gx={g∈G:g⋅x=x}.G_x=\{g\in G:g\cdot x=x\}.

Counting the same pairs by their set coordinate gives

∣S∣=∑x∈X∣Gx∣.|S|=\sum_{x\in X}|G_x|.

The orbit–stabilizer theorem states that

∣G⋅x∣ ∣Gx∣=∣G∣.|G\cdot x|\,|G_x|=|G|.

Consequently, for any orbit OO, each x∈Ox\in O has stabilizer size ∣G∣/∣O∣|G|/|O|, so

∑x∈O∣Gx∣=∣O∣∣G∣∣O∣=∣G∣.\sum_{x\in O}|G_x| = |O|\frac{|G|}{|O|} = |G|.

Every orbit therefore contributes exactly ∣G∣|G| to the sum. It follows that

∑g∈G∣Fix⁡X(g)∣=∣G∣ ∣X/G∣,\sum_{g\in G}|\operatorname{Fix}_X(g)| = |G|\,|X/G|,

which proves the formula.

This argument also explains why simply dividing ∣X∣|X| by ∣G∣|G| generally fails: objects with different amounts of symmetry have orbits of different sizes.

Example: coloring the vertices of a square

Suppose each vertex of a square is colored black or white. There are 24=162^4=16 colorings before identifying any symmetries.

Rotations only

Take GG to be the four rotations of the square.

Rotation Condition for a coloring to be fixed Fixed colorings
0∘0^\circ No restriction 1616
90∘90^\circ All four vertices have the same color 22
180∘180^\circ Opposite vertices have the same color 44
270∘270^\circ All four vertices have the same color 22

Burnside's lemma gives

16+2+4+24=6\frac{16+2+4+2}{4}=6

colorings up to rotation.

The six classes are represented by an all-white square, an all-black square, one black vertex, one white vertex, two adjacent black vertices, and two opposite black vertices.

Rotations and reflections

If mirror images are also identified, the acting group is the dihedral group of the square, of order eight.

There are four additional symmetries:

  • Two reflections through opposite vertices. Each fixes two vertices and exchanges the other two, so each fixes 23=82^3=8 colorings.
  • Two reflections through midpoints of opposite edges. Each exchanges two pairs of vertices, so each fixes 22=42^2=4 colorings.

The number of classes becomes

16+2+4+2+2(8)+2(4)8=6.\frac{16+2+4+2+2(8)+2(4)}{8}=6.

The equality with the rotation-only count is particular to this example: every reflected binary coloring of the square is already rotation-equivalent to the original. With three available colors, the corresponding counts are 2424 under rotations and 2121 under rotations and reflections.

Counting colorings through permutation cycles

A common application begins with a finite set PP of positions on which GG acts. A coloring with qq distinguishable colors is a function

f:P⟶{1,…,q}.f:P\longrightarrow \{1,\ldots,q\}.

The group acts on colorings by

(g⋅f)(p)=f(g−1⋅p).(g\cdot f)(p)=f(g^{-1}\cdot p).

Each group element induces a permutation of PP. If this permutation has c(g)c(g) cycles, including cycles of length one, then a coloring is fixed precisely when it is constant on each cycle. Each cycle can independently receive any of the qq colors, giving

∣Fix⁡(g)∣=qc(g).|\operatorname{Fix}(g)|=q^{c(g)}.

Hence

number of coloring classes=1∣G∣∑g∈Gqc(g).\text{number of coloring classes} = \frac{1}{|G|}\sum_{g\in G}q^{c(g)}.

For example, consider nn positions arranged on a circle, identifying colorings under rotations but not reflections. Rotation by kk positions has gcd⁡(n,k)\gcd(n,k) cycles, where gcd⁡\gcd denotes the greatest common divisor. The number of such necklaces is therefore

N(n,q)=1n∑k=0n−1qgcd⁡(n,k),N(n,q)=\frac{1}{n}\sum_{k=0}^{n-1}q^{\gcd(n,k)},

with gcd⁡(n,0)=n\gcd(n,0)=n.

This counts all necklaces, including those whose color patterns repeat after fewer than nn positions.

Relation to Pólya enumeration

Burnside's lemma underlies Pólya's enumeration theorem, which records more detailed information about colorings.

If ai(g)a_i(g) is the number of cycles of length ii in the permutation induced by gg, the cycle index of the action is the polynomial

ZG(s1,s2,…)=1∣G∣∑g∈G∏i≥1siai(g).Z_G(s_1,s_2,\ldots) = \frac{1}{|G|} \sum_{g\in G}\prod_{i\geq 1}s_i^{a_i(g)}.

Only finitely many factors occur for a finite position set.

Substituting si=qs_i=q for every ii recovers the ordinary coloring count. More informative substitutions produce a generating function that records how many positions receive each color. For colors represented by variables x1,…,xqx_1,\ldots,x_q, the substitution

si=x1i+⋯+xqis_i=x_1^i+\cdots+x_q^i

yields coefficients counting symmetry classes with specified color multiplicities.

Probabilistic and linear-algebraic interpretations

If gg is selected uniformly from GG, then Burnside's lemma can be written using expected value as

∣X/G∣=E ⁣[∣Fix⁡X(g)∣].|X/G|=\mathbb{E}\!\left[|\operatorname{Fix}_X(g)|\right].

This averages over group elements, not over objects or orbits.

There is also an interpretation in representation theory. Form a real vector space with basis {ex:x∈X}\{e_x:x\in X\}. Each group element acts by a permutation matrix ρ(g)\rho(g), whose trace is

tr⁡ρ(g)=∣Fix⁡X(g)∣.\operatorname{tr}\rho(g)=|\operatorname{Fix}_X(g)|.

The averaging operator

P=1∣G∣∑g∈Gρ(g)P=\frac{1}{|G|}\sum_{g\in G}\rho(g)

is a projection onto the subspace of invariant vectors. That subspace has one basis vector for each orbit, obtained by summing the basis elements belonging to that orbit. Thus its dimension, and therefore the trace of PP, is ∣X/G∣|X/G|. Taking traces gives Burnside's formula.

Applications and limitations

The lemma is used to count necklaces, bracelets, arrangements on polygons and polyhedra, unlabeled structures, and other configurations whose descriptions contain redundant labels. In graph theory, for example, the symmetric group on a vertex set acts on labeled graphs by relabeling vertices; its orbits are graph isomorphism classes.

Correct application requires specifying both the objects and their allowed symmetries:

  • Rotations and reflections give different equivalence relations. Neither should be included unless the counting problem identifies configurations related by it.
  • Permuting positions does not automatically permute colors. Identifying color names requires an additional action.
  • Constraints must be preserved by the action. If only configurations satisfying a restriction are allowed, the chosen group must map valid configurations to valid configurations.
  • Fixed-point counts remain the main computational task. Averaging is simple, but determining which objects a symmetry fixes can be difficult.

If the action is free, meaning that only the identity fixes any element, the formula reduces to

∣X/G∣=∣X∣∣G∣.|X/G|=\frac{|X|}{|G|}.

The general lemma accounts for the nontrivial stabilizers that prevent this division rule from working in other cases.

The standard numerical formula assumes that both GG and XX are finite. Infinite actions require additional hypotheses or different formulations; ordinary finite averaging cannot simply be applied unchanged.

Historical attribution

The lemma is named after William Burnside, who included it in his 1897 book Theory of Groups of Finite Order. The result predates that publication: it appeared in work of Augustin-Louis Cauchy and Ferdinand Georg Frobenius. The alternative name Cauchy–Frobenius lemma reflects that earlier history, while orbit-counting lemma describes its mathematical content.