Burnside's Lemma
Introduction
Burnside's Lemma, also known as Burnside's Counting Theorem or the Cauchy-Frobenius Lemma, is a result in group theory, a branch of abstract algebra. It provides a method for counting the distinct objects in a set that are invariant under a group of symmetries. This lemma is particularly useful in combinatorics for counting the number of distinct configurations of objects that are subject to symmetrical transformations. The lemma is named after the British mathematician William Burnside, although it was known earlier to Augustin-Louis Cauchy and Ferdinand Frobenius.
Mathematical Formulation
Burnside's Lemma states that if \( G \) is a finite group acting on a set \( X \), then the number of distinct orbits is given by:
\[ |X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g| \]
where \( |X/G| \) denotes the number of distinct orbits, \( |G| \) is the order of the group \( G \), and \( |X^g| \) is the number of elements in \( X \) that are fixed by the group element \( g \).
Explanation of Terms
- **Group Action**: A group \( G \) is said to act on a set \( X \) if there is a function \( G \times X \to X \) such that for all \( g, h \in G \) and \( x \in X \), \( e \cdot x = x \) (where \( e \) is the identity element of \( G \)) and \( (gh) \cdot x = g \cdot (h \cdot x) \).
- **Orbit**: The orbit of an element \( x \in X \) under the action of \( G \) is the set \( \{ g \cdot x \mid g \in G \} \).
- **Fixed Points**: An element \( x \in X \) is said to be fixed by \( g \in G \) if \( g \cdot x = x \).
Applications
Burnside's Lemma is widely used in various fields, including combinatorics, chemistry, and computer science. Its primary application is in counting problems where symmetry plays a crucial role.
Combinatorial Enumeration
In combinatorics, Burnside's Lemma is used to count the number of distinct colorings, arrangements, or configurations of objects that are invariant under a group of symmetries. For example, it can be used to determine the number of distinct ways to color the faces of a cube using a given set of colors, accounting for rotations of the cube.
Chemical Isomer Counting
In chemistry, the lemma aids in counting distinct chemical isomers, which are molecules with the same molecular formula but different arrangements of atoms. The symmetrical properties of molecular structures can be analyzed using group theory, and Burnside's Lemma helps in determining the number of unique isomers.
Graph Theory
In graph theory, Burnside's Lemma is used to count the number of distinct graphs or graph colorings that are invariant under a group of automorphisms. This is particularly useful in the study of symmetrical graphs and networks.
Proof of Burnside's Lemma
The proof of Burnside's Lemma involves the concept of double counting. Consider the set of pairs \( (x, g) \) where \( x \in X \) and \( g \in G \) such that \( g \cdot x = x \). The number of such pairs can be counted in two different ways:
1. **By Fixed Points**: For each \( g \in G \), count the number of elements \( x \in X \) that are fixed by \( g \). This gives the sum \( \sum_{g \in G} |X^g| \).
2. **By Orbits**: For each \( x \in X \), count the number of group elements \( g \in G \) that fix \( x \). This is equal to the order of the stabilizer subgroup of \( x \), denoted \( |G_x| \). By the Orbit-Stabilizer Theorem, the size of the orbit of \( x \) is \( |G|/|G_x| \), and thus the total number of pairs is \( |G| \times |X/G| \).
Equating these two counts gives the formula for Burnside's Lemma.
Historical Context
Burnside's Lemma is named after William Burnside, who popularized its use in his work on group theory. However, the result was known earlier to mathematicians such as Cauchy and Frobenius. The lemma is a fundamental result in the theory of group actions and has been instrumental in the development of modern combinatorics and algebra.
Limitations and Extensions
While Burnside's Lemma is a powerful tool, it has limitations. It applies only to finite groups and finite sets. Extensions of the lemma have been developed to handle infinite groups and continuous symmetries, such as in the context of Lie groups and algebraic groups.
Polya's Enumeration Theorem
One significant extension of Burnside's Lemma is Polya's Enumeration Theorem, which generalizes the lemma to count distinct colorings of objects where the colors are drawn from a finite set. Polya's theorem incorporates the concept of generating functions and provides a systematic way to handle more complex counting problems involving symmetries.