Burnside's lemma, sometimes also called Burnside's counting theorem, the Cauchy–Frobenius lemma, orbit-counting theorem, or The Lemma that is not Burnside's, is a result in group theory which is often useful in taking account of symmetry when counting mathematical objects. Its various eponyms are based on William Burnside, George Pólya, Augustin Louis Cauchy, and Ferdinand Georg Frobenius. The result is not due to Burnside himself, who merely quotes it in his book 'On the Theory of Groups of Finite Order', attributing it instead to. In the following, let G be a finite group that acts on a setX. For each g in G let Xg denote the set of elements in X that are fixed byg, i.e. Xg =. Burnside's lemma asserts the following formula for the number of orbits, denoted |X/G|: Thus the number of orbits is equal to the average number of points fixed by an element ofG. If G is infinite, the division by |G| may not be well-defined; in this case the following statement in cardinal arithmetic holds:
The number of rotationally distinct colourings of the faces of a cube using three colours can be determined from this formula as follows. Let X be the set of 36 possible face colour combinations that can be applied to a cube in one particular orientation, and let the rotation groupG of the cubeact on X in the natural manner. Then two elements of X belong to the same orbitprecisely when one is simply a rotation of the other. The number of rotationally distinct colourings is thus the same as the number of orbits and can be found by counting the sizes of the fixed sets for the 24 elements of G.
one identity element which leaves all 36 elements of X unchanged
six 90-degree face rotations, each of which leaves 33 of the elements of X unchanged
three 180-degree face rotations, each of which leaves 34 of the elements of X unchanged
eight 120-degree vertex rotations, each of which leaves 32 of the elements of X unchanged
six 180-degree edge rotations, each of which leaves 33 of the elements of X unchanged
A detailed examination of these automorphisms may be found here. The average fix size is thus Hence there are 57 rotationally distinct colourings of the faces of a cube in three colours. In general, the number of rotationally distinct colorings of the faces of a cube in n colors is given by
Proof
The first step in the proof of the lemma is to re-express the sum over the group elements g ∈ G as an equivalent sum over the set of elements x ∈ X: The orbit-stabilizer theorem says that there is a natural bijection for each x ∈ X between the orbit of x, G.x = ⊆ X, and the set of left cosets G/Gx of its stabilizer subgroupGx. With Lagrange's theorem this implies Our sum over the set X may therefore be rewritten as Finally, notice that X is the disjoint union of all its orbits in X/G, which means the sum over X may be broken up into separate sums over each individual orbit. Putting everything together gives the desired result: This proof is essentially also the proof of the class equation formula, simply by taking the action of G on itself to be by conjugation, g.x = gxg−1, in which case Gx instantiates to the centralizer of x in G.
History: the lemma that is not Burnside's
stated and proved this lemma, attributing it to, in his 1897 book on finite groups. But, even prior to Frobenius, the formula was known to Cauchy in 1845. In fact, the lemma was apparently so well known that Burnside simply omitted to attribute it to Cauchy. Consequently, this lemma is sometimes referred to as the lemma that is not Burnside's. This is less ambiguous than it may seem: Burnside contributed many lemmas to this field.
