Burnside's lemma

Let G be a finite group that acts on a set X. For each g in G, let X^g denote the set of elements in X that are fixed by g (left invariant by g): that is, X^g = \{ x \in X : g\cdot x = x\}. Burnside's lemma asserts the following formula for the number of orbits, denoted |X/G|: |X/G| = \frac{1}\sum_{g \in G}|X^g|. Thus the number of orbits (a natural number or +∞) is equal to the average number of points fixed by an element of G. For an infinite group G, there is still a bijection: G \times X/G \ \longleftrightarrow\ \coprod_{g \in G} X^g . == Examples ==

Necklaces There are 8 possible bit strings of length 3, but tying together the string ends gives only four distinct 2-colored necklaces of length 3, given by the canonical forms 000, 001, 011, 111: the other strings 100 and 010 are equivalent to 001 by rotation, while 110 and 101 are equivalent to 011. That is, rotation equivalence splits the set X of strings into four orbits: X = \{{000}\}\cup \{{001}, {010}, {100}\}\cup \{{011}, {101}, {110}\}\cup \{{111}\}.The Burnside formula uses the number of rotations, which is 3 including the null rotation, and the number of bit strings left unchanged by each rotation. All eight vectors are unchanged by the null rotation, and two (000 and 111) are unchanged by the other two rotations. Thus the number of orbits is: 4 = \frac{1}{3}(8+2+2). For length 4, there are 16 possible bit strings; 4 rotations; the null rotation leaves all 16 strings unchanged; the 1-rotation and 3-rotation each leave two strings unchanged (0000 and 1111); the 2-rotation leaves 4 bit strings unchanged (0000, 0101, 1010, 1111). The number of distinct necklaces is thus: 6 = \tfrac{1}{4}(16+2+4+2), represented by the canonical forms 0000, 0001, 0011, 0101, 0111, 1111. The general case of n bits and k colors is given by a necklace polynomial. Colorings of a cube Burnside's lemma can compute the number of rotationally distinct colourings of the faces of a cube using three colours. 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: • the identity element fixes all 36 colorings • six 90-degree face rotations each fix 33 colorings • three 180-degree face rotations each fix 34 colorings • eight 120-degree vertex rotations each fix 32 colorings • six 180-degree edge rotations each fix 33 colorings. A detailed examination may be found here. The average fixed-set size is thus: : |X/G| = \frac{1}{24}\left(3^6+6\cdot 3^3 + 3 \cdot 3^4 + 8 \cdot 3^2 + 6 \cdot 3^3 \right) = 57. 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: : \frac{1}{24}\left(n^6+3n^4 + 12n^3 + 8n^2\right). Conjugacy classes Let G be a finite group. Consider the group action of G on itself given by the conjugation map g \mapsto \phi_g where \phi_g(h) = g h g^{-1} . The orbits are the conjugacy classes of G and the set of fixed points of an element g is the centralizer C_G(g) . Thus, by Burnside's lemma, the number of conjugacy classes of G is equal to \frac{1} \sum_g |C_G(g)|, that is, the average size of the centralizer. == Proof ==

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: :\sum_{g \in G}|X^g| = \#\{(g,x)\in G\times X \mid g \cdot x = x\} = \sum_{x \in X} |G_x|. Here X^g = \{ x \in X : g\cdot x = x\} is the set of points of X fixed by the element g of G, whereas G_x = \{ g \in G : g\cdot x = x\} is the stabilizer subgroup of G, consisting of those symmetries that fix the point x \in X. The orbit-stabilizer theorem says that for each x \in X there is a natural bijection between the orbit G \cdot x = \{ g\cdot x : g \in G\} and the set of left cosets G / G_x. Lagrange's theorem implies that |G \cdot x| = [G : G_x] = |G| / |G_x|. The sum may therefore be rewritten as \sum_{x \in X} |G_x| = \sum_{x \in X} \frac = |G| \sum_{x \in X}\frac{1}. Writing X as the disjoint union of its orbits in X/G gives |G| \sum_{x \in X}\frac{1} = |G| \sum_{A\in X/G} \sum_{x\in A} \frac{1} = |G| \sum_{A\in X/G} 1 = |G|\cdot|X/G|. Putting everything together gives the desired result: \sum_{g \in G}|X^g| = |G| \cdot |X/G|. This is similar to the proof of the conjugacy class equation, which considers the conjugation action of G on itself, that is, it is the case X = G and g \cdot x = gxg^{-1}, so that the stabilizer of x is the centralizer G_x = Z_G(x). ==Enumeration vs. generation==

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. But instead of checking that g \cdot x = x, it checks that g \cdot x has not already been generated. One way to accomplish this is by checking that g \cdot x is not lexicographically less than x, using the lexicographically least member of each equivalence class as the canonical form of the class. Counting the objects generated with such a technique can verify that Burnside's lemma was correctly applied. ==History: the lemma that is not Burnside's==

William Burnside stated and proved this lemma in his 1897 book on finite groups, attributing it to . But even prior to Frobenius, the formula was known to Cauchy in 1845. Consequently, this lemma is sometimes referred to as the '''lemma that is not Burnside's'''. The attribution of the lemma to someone other than its original discoverer is an example of Stigler's law of eponymy. == See also ==