HOME

TheInfoList



OR:

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 In abstract algebra, group theory studies the algebraic structures known as groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces, can all be seen as ...
that is often useful in taking account of symmetry when counting mathematical objects. Its various eponyms are based on
William Burnside :''This English mathematician is sometimes confused with the Irish mathematician William S. Burnside (1839–1920).'' __NOTOC__ William Burnside (2 July 1852 – 21 August 1927) was an English mathematician. He is known mostly as an early res ...
, George Pólya,
Augustin Louis Cauchy Baron Augustin-Louis Cauchy (, ; ; 21 August 178923 May 1857) was a French mathematician, engineer, and physicist who made pioneering contributions to several branches of mathematics, including mathematical analysis and continuum mechanics. He w ...
, 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 . 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 Two mathematical objects ''a'' and ''b'' are called equal up to an equivalence relation ''R'' * if ''a'' and ''b'' are related by ''R'', that is, * if ''aRb'' holds, that is, * if the equivalence classes of ''a'' and ''b'' with respect to ''R'' a ...
an equivalence relation ''R'', or counting objects that are in
canonical form In mathematics and computer science, a canonical, normal, or standard form of a mathematical object is a standard way of presenting that object as a mathematical expression. Often, it is one which provides the simplest representation of an obj ...
. In the following, let ''G'' be a
finite Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb Traditionally, a finite verb (from la, fīnītus, past particip ...
group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...
that
acts The Acts of the Apostles ( grc-koi, Πράξεις Ἀποστόλων, ''Práxeis Apostólōn''; la, Actūs Apostolōrum) is the fifth book of the New Testament; it tells of the founding of the Christian Church and the spread of its message ...
on a
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
''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'' = . Burnside's lemma asserts the following formula for the number of orbits, denoted , ''X''/''G'', : , X/G, = \frac\sum_, X^g, . Thus the number of orbits (a natural number or +∞) is equal to the
average In ordinary language, an average is a single number taken as representative of a list of numbers, usually the sum of the numbers divided by how many numbers are in the list (the arithmetic mean). For example, the average of the numbers 2, 3, 4, 7 ...
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 In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. Th ...
holds: , G, , X/G, = \sum_, X^g, .


Examples of applications to enumeration


Necklaces

There are 8 possible
bit vector A bit array (also known as bitmask, bit map, bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level pa ...
s of length 3, but only four distinct 2-colored
necklaces A necklace is an article of jewellery that is worn around the neck. Necklaces may have been one of the earliest types of adornment worn by humans. They often serve ceremonial, religious, magical, or funerary purposes and are also used as symbol ...
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: 4 = \frac(8+2+2). 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: 6 = \frac(16+2+4+2). These are: 0000, 0001, 0011, 0101, 0111, and 1111.


Colorings of a cube

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''. * 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 Here is an adverb that means "in, on, or at this place". It may also refer to: Software * Here Technologies, a mapping company * Here WeGo (formerly Here Maps), a mobile app and map website by Here Television * Here TV (formerly "here!"), a ...
. The average fix size is thus : \frac\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\left(n^6+3n^4 + 12n^3 + 8n^2\right).


8 Queens Puzzle

In the
eight queens puzzle The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. There are 92 solutions. ...
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: 12 = \frac(92+4).


Notation

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

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'': :\sum_, X^g, = , \, = \sum_ , G_x, . (Here ''Xg'' =  is the subset of all points of ''X'' fixed by ''g'' ∈ ''G'', whereas ''Gx'' =  is the
stabilizer subgroup In mathematics, a group action on a space is a group homomorphism of a given group into the group of transformations of the space. Similarly, a group action on a mathematical structure is a group homomorphism of a group into the automorphis ...
of G that fixes the point ''x'' ∈ ''X''.) The orbit-stabilizer theorem says that there is a natural
bijection In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
for each ''x'' ∈ ''X'' between the orbit of ''x'', ''G·x'' =  ⊆ ''X'', and the set of left cosets ''G/Gx'' of its stabilizer subgroup ''Gx''. With Lagrange's theorem this implies :, G \cdot x, = \,:\,G_x= , G, / , G_x, . Our sum over the set ''X'' may therefore be rewritten as :\sum_ , G_x, = \sum_ \frac = , G, \sum_\frac. 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_\frac = \sum_ \sum_ \frac = \sum_ 1 = , X/G, . Putting everything together gives the desired result: :\sum_, X^g, = , G, \cdot , X/G, . This proof is essentially also the proof of the
class equation In mathematics, especially group theory, two elements a and b of a group are conjugate if there is an element g in the group such that b = gag^. This is an equivalence relation whose equivalence classes are called conjugacy classes. In other wo ...
formula, simply by taking the action of ''G'' on itself (''X'' = ''G'') to be by conjugation, ''g''.''x'' = ''gxg''−1, in which case ''G''''x'' instantiates to the centralizer of ''x'' in ''G''.


Ease of application

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 2''k''. 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

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. 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

William Burnside :''This English mathematician is sometimes confused with the Irish mathematician William S. Burnside (1839–1920).'' __NOTOC__ William Burnside (2 July 1852 – 21 August 1927) was an English mathematician. He is known mostly as an early res ...
stated and proved this lemma, attributing it to , in his 1897 book on finite groups. But, even prior to Frobenius, the formula was known to
Cauchy Baron Augustin-Louis Cauchy (, ; ; 21 August 178923 May 1857) was a French mathematician, engineer, and physicist who made pioneering contributions to several branches of mathematics, including mathematical analysis and continuum mechanics. He w ...
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 (see also
Stigler's law of eponymy Stigler's law of eponymy, proposed by University of Chicago statistics professor Stephen Stigler in his 1980 publication ''Stigler’s law of eponymy'', states that no scientific discovery is named after its original discoverer. Examples include ...
). This is less ambiguous than it may seem: Burnside contributed many lemmas to this field.


See also

* Pólya enumeration theorem *
Cycle index Cycle, cycles, or cyclic may refer to: Anthropology and social sciences * Cyclic history, a theory of history * Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr. * Social cycle, various cycles in soc ...


Notes


References

* Also availabl
here
at
Archive.org The Internet Archive is an American digital library with the stated mission of "universal access to all knowledge". It provides free public access to collections of digitized materials, including websites, software applications/games, music, ...
. (This is the first edition; the introduction to the second edition contains Burnside's famous ''volte face'' regarding the utility of representation theory.) * . * . * . * {{citation , last=Rotman , first=Joseph , title=An introduction to the theory of groups , publisher=Springer-Verlag , year=1995 , isbn=0-387-94285-8. Lemmas in group theory