Burnside Theorem formula and how to count orbits with examples
Burnside developed and proved Burnside's lemma in 1897, but historically speaking, Frobenius had already discovered it in 1887, and Cauchy had discovered this much prior, in 1845. As a result, it is also occasionally referred to as the "Cauchy-Frobenius Lemma". Based on internal symmetry, Burnside's lemma enables us to determine the number of equivalence classes in the sets.
In this article, we will learn more about the Burnside theorem and the Burnside theorem example.
History of William Burnside
William Burnside
Born: 2 July 1852
Died: 21 August 1927
Nationality: British
Contribution: He introduced the world to Burnside's theorem.
Statement of the Theorem
In group theory, Burnside's theorem asserts that group G is solvable if it is a finite group of order, where p and q are prime numbers, and a and b are non-negative integers. As a result, the order of every non-Abelian finite simple group is divisible by at least three unique primes.
Burnside Theorem Proof
$G$ is a simple group with a trivial centre, and $a$ is not zero.
Since $G$ is minimum, if it had a nontrivial proper normal subgroup\[H\], both \[H\] and \[\dfrac{G}{H}\] would be solvable, which would go against our presumption. So, $G$ is easy.
$G$ Would be a finite q-group, nilpotent, and solvable if they were equal to zero.
$G$ cannot also be abelian because it would then be solved. $G$ Centre must be basic because $G$ is simple.
There is an element \[g\] of \[G\] which has \[{{q}^{d}}\] conjugates, for some \[d>0\].
By the first statement of Sylow's theorem, G has a subgroup S of order pa because S is a nontrivial p-group, and its centre Z(S) is nontrivial. Fix a nontrivial element g\epsilon Z(S) . The number of conjugates of g is equal to the index of its stabiliser subgroup \[{{G}_{g}}\], which divides the index \[{{g}^{b}}\] of S (because S is a subgroup of \[{{G}_{g}}\]). Hence, this number is of the form \[{{q}^{d}}\]. Moreover, the integer d is strictly positive since g is nontrivial and therefore not central in G.
There exists a nontrivial irreducible representation \[\rho \] with character \[X\], such that its dimension \[n\] is not divisible by \[q\] and the complex number \[X(g)\] is not zero.
Let \[{{({{\chi }_{i}})}_{1~\le ~i~\le ~h}}\] be the family of irreducible characters of G over \[\sum\limits_{}^{} {_{{X_i}}} \], (here $({{X}_{1}})$ denotes the trivial character). Since $g$ is not in the same conjugacy class as 1, the orthogonality relation for the columns of the group's character table gives:
\[0 = \sum\limits_{i = 1}^h {{x_i}(1)} {x_i}(g) = 1 + \sum\limits_{i = 2}^h {{x_i}(1)} {x_i}(g)\]
Now the χi(g) are algebraic integers because they are sums of roots of unity. If all the nontrivial irreducible characters which don't vanish at g take a value divisible by q at 1, we deduce that
\[\dfrac{{ - 1}}{q} = \sum\limits_{i \ge 2,{x_i}(g) \ne 0}^{} {\dfrac{{{x_i}(1)}}{q}} {x_i}(g)\]
Burnside Lemma Applications
The number of unique ways that something can be done can be determined using Burnside's Counting Theory. This theory has intriguing implications in areas like switching theory and chemistry, secondary to its geometric applicability.
Burnside's Lemma and Polya's Enumeration Theorem can be used to determine the number of distinct colours present in an object.
Solved Examples
1. Determine how many different ways the four corners of a square may be coloured with two colours.
Ans: Naming each corner of the square, we have,
The number of ways to arrange the colours of the corner is ${{2}^{4}}=16$
${{D}_{4}}$ is the symmetries of the square.
${{R}_{0}}$ fixes all 16 arrangements.
${{R}_{90}}$ & ${{R}_{270}}$ fix arrangements with all 4 colours the same colour
Under ${{R}_{180}}\text{ }\!\!~\!\!\text{ : }\{1,3\}\text{ }\!\!~\!\!\text{ and }\!\!~\!\!\text{ }\{2,4\}$
From these vertices $1$ and $3$ are of same colours $2$ and $4$ are of same colours
So, ${{R}_{180}}$ fixes $4$ colourings
Under $H$, it fixes $4$ colourings.
Under ${{n}^{3}}$ $D$, it fixes $8$ colourings (as ${{2}^{3}}=8$)
Similarly, D fixes $8$ colourings
$\dfrac{1}{\left| {{D}_{4}} \right|}\underset{\phi \in {{D}_{4}}}{\mathop \sum }\,|fix(\phi )|=\dfrac{1}{8}(16+2\cdot 2+4+2\cdot 4+2\cdot 8)=\dfrac{1}{8}(48)=6$
So, we have non-equivalent colours.
2. Determine how many different ways the four edges of a square may be coloured with six different colours.
Ans: The number of ways to arrange the colours of the edges of a square is ${{6}^{4}}$.
From Identity, we have ${{6}^{4}}$number of fixed colourings.
From the Rotation of order $4$, we have a $6$ number of fixed colourings.
From Rotation of order $2$, we have ${{6}^{2}}$ number of fixed colourings.
From edge Reflection, we have ${{6}^{3}}$ number of fixed colourings.
From Diagonal Reflection, we have ${{6}^{2}}$ number of fixed colourings.
From Burnside Theorem, we have,
$\dfrac{1}{\left| {{D}_{4}} \right|}\underset{\phi \in {{D}_{4}}}{\mathop \sum }\,|fix(\phi )|=\dfrac{1}{8}\left( {{6}^{4}}+2\cdot 6+{{6}^{2}}+2\cdot {{6}^{3}}+2\cdot {{6}^{2}} \right)=2310$
Therefore, $2310$ in total.
3. Let's say we cut a cake into six identical pieces. How many different ways can we decorate the cake with $n$ different colours if each piece gets one colour?
Ans: Total arrangement of colours is ${{n}^{6}}$.
The symmetry group of the cake is $G=\left\{ {{R}_{0}},{{R}_{60}},{{R}_{120}},{{R}_{180}},{{R}_{240}},{{R}_{300}} \right\}$
For rotations of order $6$ we have $\{1,2,3,4,5,6\}$($n$ colourings)
For rotations of order $3$ we have $\{1,3,5\}$&$\{2,4,6\}$( ${{n}^{2}}$colourings)
For \[{{R}_{180}}\] we have $\{1,4\},\{2,5\},\{3,6\}$( ${{n}^{3}}$colourings)
$\dfrac{1}{|G|}\underset{\phi \in G}{\mathop \sum }\,|fix(\phi )|=\dfrac{1}{6}\left( {{n}^{6}}+2n+2{{n}^{2}}+{{n}^{3}} \right).$
Important Formulae
\[\dfrac{{ - 1}}{q} = \sum\limits_{i \ge 2,{x_i}(g) \ne 0}^{} {\dfrac{{{x_i}(1)}}{q}} {x_i}(g)\]
- \[0 = \sum\limits_{i = 1}^h {{x_i}(1)} {x_i}(g) = 1 + \sum\limits_{i = 2}^h {{x_i}(1)} {x_i}(g)\]
Summary
Burnside's lemma is a result of group theory that can help when counting objects with symmetry taken into account. It gives a formula to count objects, where two objects that are related by a symmetry (rotation or reflection, for example) are not to be counted as distinct.
FAQs on Burnside Theorem in Group Theory Explained
1. What is Burnside’s Theorem?
Burnside’s Theorem states that the number of distinct objects under a group action equals the average number of objects fixed by the group elements. In combinatorics, it is usually written as the formula |X/G| = (1/|G|) \sum_{g \in G} |\text{Fix}(g)|, where:
- G is a finite group,
- X is a set the group acts on,
- Fix(g) is the set of elements fixed by group element g.
2. What is the formula for Burnside’s Lemma?
The formula for Burnside’s Lemma is |X/G| = (1/|G|) \sum_{g \in G} |\text{Fix}(g)|. Here:
- |X/G| is the number of distinct orbits (unique configurations).
- |G| is the order of the group.
- |Fix(g)| counts elements unchanged by g.
3. How do you use Burnside’s Theorem to count colorings?
To use Burnside’s Theorem for counting colorings, compute the average number of colorings fixed by each symmetry of the object. Steps:
- Identify the symmetry group G.
- For each g \in G, count the colorings fixed by g.
- Add all fixed counts.
- Divide by |G|.
4. What is an orbit in Burnside’s Theorem?
An orbit is the set of elements that can be transformed into each other by the group action. Formally, the orbit of x is Orb(x) = {g·x : g ∈ G}. In Burnside’s Theorem, each orbit corresponds to one distinct configuration under symmetry, so counting orbits means counting fundamentally different arrangements.
5. What does Fix(g) mean in Burnside’s Lemma?
Fix(g) is the set of elements in X that remain unchanged under the group element g. Mathematically, Fix(g) = {x ∈ X : g·x = x}. Its size, |Fix(g)|, is crucial in Burnside’s formula because the theorem averages these fixed counts to determine the number of distinct orbits.
6. Can you give a simple example of Burnside’s Theorem?
A simple example is counting 2-colorings of a triangle’s vertices under rotation. The rotation group has 3 elements:
- Identity fixes 2³ = 8 colorings.
- Each nontrivial rotation fixes 2 colorings.
7. What is the difference between Burnside’s Lemma and the Orbit-Stabilizer Theorem?
Burnside’s Lemma counts the number of distinct orbits, while the Orbit-Stabilizer Theorem relates the size of a single orbit to its stabilizer. Specifically:
- Burnside’s Lemma: counts total orbits using fixed points.
- Orbit-Stabilizer Theorem: states |Orb(x)| = |G| / |Stab(x)|.
8. Why is Burnside’s Theorem useful in combinatorics?
Burnside’s Theorem is useful because it simplifies counting problems with symmetry by avoiding overcounting. Instead of listing all configurations, you:
- Account for symmetries directly,
- Compute fixed points under each symmetry,
- Use the averaging formula.
9. Is Burnside’s Lemma the same as the Cauchy-Frobenius Lemma?
Yes, Burnside’s Lemma is another name for the Cauchy-Frobenius Lemma. The theorem was known earlier to Cauchy and Frobenius, but became widely associated with Burnside due to his work in group theory. The standard formula remains |X/G| = (1/|G|) \sum_{g ∈ G} |Fix(g)|.
10. What are common mistakes when applying Burnside’s Theorem?
Common mistakes in using Burnside’s Theorem include miscounting fixed points and ignoring symmetries. Key points to remember:
- Always use the correct symmetry group G.
- Count only configurations fixed by each group element.
- Include the identity element.
- Divide the total fixed count by |G|.
