#jsDisabledContent { display:none; } My Account | Register | Help
 Flag as Inappropriate This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate?          Excessive Violence          Sexual Content          Political / Social Email this Article Email Address:

# Burnside's lemma

Article Id: WHEBN0000251900
Reproduction Date:

 Title: Burnside's lemma Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

### 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 Frobenius (1887).[1]

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), i.e. Xg = { xX | g.x = x }. Burnside's lemma asserts the following formula for the number of orbits, denoted |X/G|:[2]

|X/G| = \frac{1}{|G|}\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 (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:

|G| |X/G| = \sum_{g \in G}|X^g|.

## Contents

• Example application 1
• Proof 2
• History: the lemma that is not Burnside's 3
• See also 4
• Notes 5
• References 6

## Example application

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

\frac{1}{24}\left(3^6+6\cdot 3^3 + 3 \cdot 3^4 + 8 \cdot 3^2 + 6 \cdot 3^3 \right) = 57.

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

\frac{1}{24}\left(n^6+3n^4 + 12n^3 + 8n^2\right).

## 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 elements x ∈ X:

\sum_{g \in G}|X^g| = |\{(g,x)\in G\times X \mid g.x = x\}| = \sum_{x \in X} |G_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

|G.x| = [G\,:\,G_x] = |G| / |G_x|.

Our sum over the set X may therefore be rewritten as

\sum_{x \in X} |G_x| = \sum_{x \in X} \frac{|G|}{|G. x|} = |G| \sum_{x \in X}\frac{1}{|G. x|}.

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.

\sum_{x \in X}\frac{1}{|G. x|} = \sum_{A\in X/G} \sum_{x\in A} \frac{1}{|A|} = \sum_{A\in X/G} 1 = |X/G|.

Putting everything together gives the desired result:

\sum_{g \in G}|X^g| = |G| \cdot |X/G|.

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.

## History: the lemma that is not Burnside's

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[3] (see also Stigler's law of eponymy). This is less ambiguous than it may seem: Burnside contributed many lemmas to this field.

## Notes

1. ^ Burnside 1897, §119
2. ^ Rotman 1995, Chapter 3
3. ^ Neumann 1979

## References

• Burnside, William (1897) Theory of Groups of Finite Order, representation theory.)
• .
• .
• Rotman, Joseph (1995), An introduction to the theory of groups, Springer-Verlag, .
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.

Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.

By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.