Burnside's lemma

From Wikipedia, the free encyclopedia

Burnside's lemma, sometimes also called Burnside's counting theorem, the Cauchy–Frobenius lemma, the orbit-counting theorem, or the Lemma that is not Burnside's, is a result in group theory that 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 Frobenius (1887).[1] Burnside's Lemma counts "orbits", which is the same thing as counting distinct objects taking account of a symmetry. Other ways of saying it are counting distinct objects up to an equivalence relation R, or counting objects that are in canonical form.

In the following, let G be a finite group that acts on a set X. For each g in G, let Xg denote the set of elements in X that are fixed by g (also said to be left invariant by g), that is, Xg = { xX | g.x = x }. Burnside's lemma asserts the following formula for the number of orbits, denoted |X/G|:[2]

Thus the number of orbits (a natural number or +∞) is equal to the average number of points fixed by an element of G (which is also a natural number or infinity). If G is infinite, the division by |G| may not be well-defined; in this case the following statement in cardinal arithmetic holds:

Examples of applications to enumeration[edit]

Necklaces[edit]

There are 8 possible bit vectors of length 3, but only four distinct 2-colored necklaces of length 3: 000, 001, 011, and 111, because 100 and 010 are equivalent to 001 by rotation; similarly 110 and 101 are equivalent to 011. The formula is based on the number of rotations, which in this case is 3 (including the null rotation), and the number of bit vectors left unchanged by each rotation. All 8 bit vectors are unchanged by the null rotation, and two (000 and 111) are unchanged by each of the other two rotations, giving: .

For length 4, there are 16 possible bit vectors; 4 rotations; the null rotation leaves all 16 bit vectors unchanged; the 1-rotation and 3-rotation each leave two bit vectors unchanged (0000 and 1111); the 2-rotation leaves 4 bit vectors unchanged (0000, 0101, 1010, and 1111); giving: . These are: 0000, 0001, 0011, 0101, 0111, and 1111.

Colorings of a cube[edit]

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 group G of the cube act on X in the natural manner. Then two elements of X belong to the same orbit precisely 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.

Cube with coloured faces
  • 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

8 Queens Puzzle[edit]

In the eight queens puzzle there are 92 solutions, of which 12 fundamental solutions are distinct up to rotation and reflection of the board. There are 8 combinations of rotations and reflections, including the null action. The null action leaves all 92 solutions unchanged. Four of the 92 solutions are symmetrical, unchanged by 180° rotation. That gives: .[3]

abcdefgh
8
Chessboard480.svg
f8 white queen
d7 white queen
g6 white queen
a5 white queen
h4 white queen
b3 white queen
e2 white queen
c1 white queen
8
77
66
55
44
33
22
11
abcdefgh
The only symmetrical solution to the eight queens puzzle (up to rotation and reflection)

Notation[edit]

The Lemma uses notation from group theory and set theory, and is subject to misinterpretation without that background, but is useful nonetheless. In particular, Xg does not mean exponentiation, X/G does not mean division, and |G| does not mean absolute value.

Proof[edit]

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:

(Here Xg = {x ∈ X | g.x = x} is the subset of all points of X fixed by g ∈ G, whereas Gx = {g ∈ G | g.x = x} is the stabilizer subgroup of G that fixes the point x ∈ X.)

The orbit-stabilizer theorem says that there is a natural bijection for each x ∈ X between the orbit of x, G·x = {g·x | g ∈ G} ⊆ X, and the set of left cosets G/Gx of its stabilizer subgroup Gx. 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 (X = G) to be by conjugation, g.x = gxg−1, in which case Gx instantiates to the centralizer of x in G.

Ease of application[edit]

Unlike some formulas, applying Burnside's Lemma is usually not as simple as plugging in a few readily available values. In general, for a set X of n objects and a group G of m actions, there are nm cases to consider as to whether a particular action leaves a particular object unchanged. The null action is often easy to account for, for example when X is the set of bit vectors of length k, the size of X is 2k. But there is no known simple formula for the 92 solutions unaffected by the null action in the 8-queens puzzle. In some cases, clever insight can account for the effects of certain actions. For example when X is the set of bit vectors of length k, and k is prime, rotations other than the null rotation will leave only two bit vectors unchanged, those with all zeros or all ones.

Enumeration vs. generation[edit]

Burnside's Lemma counts distinct objects, but it doesn't generate them. In general, combinatorial generation with isomorph rejection considers the same |G| actions, g, on the same |X| objects, x. But instead of checking that g.x=x, it checks that g.x has not already been generated. One way to accomplish this is by checking that g.x is not lexicographically less than x, using the lexicographically least member of each equivalence class as the class representative.[4] Counting the objects generated with an isomorph-rejection technique such as this provides a way of checking that Burnside's Lemma was correctly applied.

History: the lemma that is not Burnside's[edit]

William Burnside stated and proved this lemma, attributing it to Frobenius 1887, 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[5] (see also Stigler's law of eponymy). This is less ambiguous than it may seem: Burnside contributed many lemmas to this field.[citation needed]

See also[edit]

Notes[edit]

References[edit]

  • Burnside, William (1897). Theory of Groups of Finite Order. Cambridge University Press – via Project Gutenberg. Also available here at Archive.org. (This is the first edition; the introduction to the second edition contains Burnside's famous volte face regarding the utility of representation theory.)
  • Frobenius, Ferdinand Georg (1887), "Ueber die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul", Crelle's Journal, 101 (4): 273–299, doi:10.3931/e-rara-18804.
  • Neumann, Peter M. (1979), "A lemma that is not Burnside's", The Mathematical Scientist, 4 (2): 133–141, ISSN 0312-3685, MR 0562002.
  • Cheng, Yuanyou (1986), A generalization of Burnside's lemma to multiply transitive groups, journal of Hubei University of Technology, ISSN 1003-4684.
  • Rotman, Joseph (1995), An introduction to the theory of groups, Springer-Verlag, ISBN 0-387-94285-8.