Burnside's lemma
Burnside's lemma, sometimes also called Burnside's counting theorem, the Cauchy–Frobenius lemma, or the orbit-counting theorem, is a result in group theory that is often useful in taking account of symmetry when counting mathematical objects.
It was discovered by Augustin Louis Cauchy and Ferdinand Georg Frobenius, and became well-known after William Burnside quoted it.
For example, in describing possible organic compounds of certain type, one considers them up to spatial rotation symmetry: different rotated drawings of a given molecule are chemically identical.
Burnside's lemma asserts the following formula for the number of orbits, denoted |X/G|:[2]
That is, rotation equivalence splits the set X of strings into four orbits:
The general case of n bits and k colors is given by a necklace polynomial.
Let X be the set of 36 possible face color combinations that can be applied to a fixed cube, and let the rotation group G of the cube act on X by moving the colored faces: two colorings in X belong to the same orbit precisely when one is a rotation of the other.
Rotationally distinct colorings correspond to group orbits, and can be found by counting the sizes of the fixed sets for the 24 elements of G, the colorings left unchanged by each rotation: A detailed examination may be found here.
In general, the number of rotationally distinct colorings of the faces of a cube in n colors is: In the proof of Burnside's lemma, the first step is to re-express the sum over the group elements g ∈ G as an equivalent sum over the set of elements x ∈ X: Here Xg = {x ∈ X | g.x = x} is the set of points of X fixed by g ∈ G, whereas Gx = {g ∈ G | g.x = x} is the stabilizer subgroup of G, symmetries that fix the point x ∈ X.)
The orbit-stabilizer theorem says that for each x ∈ X there is a natural bijection between the orbit G·x = {g·x | g ∈ G} and the set of left cosets G/Gx.
Lagrange's theorem implies: The sum may therefore be rewritten as: Writing X as the disjoint union of its orbits in X/G: Putting everything together gives the desired result: This is similar to the proof of the conjugacy class equation, which considers the conjugation action of G on itself: X = G and g.x = gxg−1, so that the stabilizer of x is centralizer: Gx = ZG(x).
Burnside's lemma counts distinct objects, but it does not construct them.
In general, combinatorial generation with isomorph rejection considers the symmetries of g, on objects x.
[3] Counting the objects generated with such a technique can verify that Burnside's lemma was correctly applied.
William Burnside stated and proved this lemma in his 1897 book on finite groups, attributing it to Frobenius 1887.
[4] Misnaming scientific discoveries is referred to as Stigler's law of eponymy.
