Burnside's Lemma

The lemma Burnside expresses the number of orbits of a (usually) finite group , based on an amount acts (see group effect ), by means on the fixed points of the individual elements from group. ${\displaystyle G}$ ${\displaystyle X}$

The naming after William Burnside is actually wrong, he mentions the sentence in his book On the theory of groups of finite order from 1897, but attributes it there to Ferdinand Georg Frobenius (1887). The lemma was already known to Augustin Louis Cauchy (1845) and is therefore sometimes also called the Cauchy-Frobenius lemma. The name Burnside counting set is also common because it is a preliminary stage of Pólya's counting theorem (1937), a refinement and extension of Burnside's lemma.

Let be a finite group operating on a set , the set of fixed points in under the group element ( ). Then applies to the number of orbits (paths of points that emerge from each other when acting on ) the effect of on : ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle X^{g}}$ ${\displaystyle X}$ ${\displaystyle g\in G}$ ${\displaystyle X^{g}=\{x\in X:gx=x\}}$ ${\displaystyle |X/G|}$ ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle G}$ ${\displaystyle X}$

${\displaystyle |X/G|={\frac {1}{|G|}}\sum _{g\in G}|X^{g}|}$.

Burnside's term Lemma is not entirely clear.

The proof is based on identity

${\displaystyle \sum _{g\in G}|X^{g}|=|\{(g,x)\in G\times X\mid g\cdot x=x\}|=\sum _{x\in X}|G_{x}|}$,

where the stabilizer subgroup is to ( ). The lemma follows by applying the orbital formula taking into account the fact that is the disjoint union of the orbits. ${\displaystyle G_{x}}$ ${\displaystyle x}$ ${\displaystyle G_{x}=\{g\in G:gx=x\}}$ ${\displaystyle X}$

example

A cube is colored with three colors in the side surfaces, so that the amount of side coloring is (with elements), the number of different coloring (orbits) is sought with regard to the rotational symmetry of the cube. The colors are not all different with regard to the rotational symmetry, some are in the same orbit (that is, they emerge from each other by rotating the cube). ${\displaystyle X}$ ${\displaystyle 3^{6}}$

Cube with side coloring

According to Burnside's lemma, the number of orbits can be expressed by the number of fixed points of the elements of the rotating group:

• The identity leaves all elements of unchanged. ${\displaystyle 3^{6}}$ ${\displaystyle X}$
• There are six rotations of one side of 90 degrees, each of which leaves elements unchanged. ${\displaystyle 3^{3}}$
• There are three 180 degree rotations of the pages, each of which leaves elements unchanged. ${\displaystyle 3^{4}}$
• There are eight 120 degree rotations with the axis of rotation through corner points, each with fixed points. ${\displaystyle 3^{2}}$
• There are six 180 degree rotations with the axis of rotation through edges, with fixed points. ${\displaystyle 3^{3}}$

According to Burnside's lemma, this results in the number of orbits:

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

In general, the following applies to colors: ${\displaystyle n}$

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

literature

• Peter M. Neumann : A lemma that is not Burnside's , The Mathematical Scientist, Volume 4, 1979, pp. 133-141.
• Frank Harary , EM Palmer: Graphical Enumeration , Academic Press 1973
• Joseph Rotman : An introduction to the theory of groups , Springer-Verlag, 1995

Web links

• Burnside's Lemma , Art of Problem Solving
• Cauchy-Frobenius-Lemma , Mathworld (Eric Weisstein)

Individual evidence

1. ↑ Frobenius, On the Congruence According to a Double Module formed from two finite groups, J. reine angew. Math., Volume 101, 1887, pp. 273–299
2. ↑ Burnside also published it in On Some Properties of Groups of Odd Order , Proc. London Math. Soc., Volume 33, 1900, pp. 162-184
3. ↑ Cauchy, Comptes Rendus Acad. Sci. Paris, Volume 21, 1845, p. 835, and in Œuvres Complètes d'Augustin Cauchy, Volume 9, Gauthier-Villars 1896, pp. 342-360