Abstract Algebra
Group Actions and Orbits
How many distinct necklaces arise from 10 beads in 4 colors? Or distinct colorings of a cube's faces? Without group actions, this is a hard combinatorial puzzle. With them, it's an elegant formula. Group actions are the language in which nature describes symmetry.
- Pólya's enumeration theorem (an extension of Burnside's lemma) is used in chemistry to count structural isomers of molecules
- In computer graphics and game design: generating unique tiles, maps, and patterns that account for symmetry - a direct application of the orbit-stabilizer theorem
Предварительные знания
Group Actions: Definition and Examples
A **group action** of G on a set X is a map G × X → X, written (g, x) ↦ g·x, satisfying: 1. **Identity:** e·x = x for all x ∈ X 2. **Compatibility:** (gh)·x = g·(h·x) for all g,h ∈ G, x ∈ X Each g ∈ G defines a permutation σ_g: X → X, x ↦ g·x. This gives a homomorphism G → Sym(X) - a **permutation representation** of the group.
**Three canonical actions:** 1. G acting on itself by left multiplication - always faithful (Cayley's theorem: every group embeds into some Sₙ). 2. G acting on itself by conjugation - orbits are conjugacy classes, stabilizers are centralizers. 3. G acting on cosets - used in the proof of the Sylow theorems.
The **orbit** of x ∈ X: Orb(x) = {g·x | g ∈ G}. The **stabilizer** of x: Stab(x) = {g ∈ G | g·x = x} - this is a subgroup of G! The set X is partitioned into orbits (equivalence: x ~ y ⟺ ∃g: g·x = y).
The group S₃ acts on {1,2,3} in the standard way. What is the orbit of the element 1?
The Orbit-Stabilizer Theorem
**Orbit-Stabilizer Theorem:** For an action of G on X and any x ∈ X: |Orb(x)| × |Stab(x)| = |G| Equivalently: |Orb(x)| = [G : Stab(x)] (the index of the stabilizer). Proof: the map G/Stab(x) → Orb(x), gStab(x) ↦ g·x, is a bijection.
**Corollary: counting conjugacy classes.** When G acts on itself by conjugation: Orb(x) = Cl(x), Stab(x) = C_G(x) (centralizer). The theorem gives |Cl(x)| = [G : C_G(x)]. Summing over class representatives yields the class equation: |G| = Σ [G : C_G(xᵢ)].
A **transitive action** is one with a single orbit (all of X). In that case: |G| = |X| × |Stab(x)| for any x. Non-transitive actions partition X into several orbits; the theorem applies to each orbit separately.
A group G of order 24 acts transitively on a set X with 8 elements. What is the order of the stabilizer of any point?
Burnside's Lemma: Counting with Symmetry
**Burnside's Lemma (Pólya-Burnside theorem):** The number of orbits of a finite group G acting on a finite set X equals: |X/G| = (1/|G|) × Σ_{g∈G} |Fix(g)| where Fix(g) = {x ∈ X | g·x = x} is the set of **fixed points** of g.
**Algorithm for counting distinct patterns:** 1. Identify the symmetry group G and set of colorings X. 2. For each g ∈ G, compute |Fix(g)| - the number of colorings unchanged by g. 3. Apply the formula: distinct patterns = (1/|G|) × Σ |Fix(g)|. Key observation: Fix(g) consists of colorings that are constant on each cycle of the permutation g. If g has c(g) cycles when acting on positions, then |Fix(g)| = k^{c(g)}, where k is the number of colors.
**Historical confusion:** The lemma bears Burnside's name, though Burnside himself attributed it to Frobenius (1887). True authorship belongs to Frobenius. This is one of the most famous instances of Stigler's law: scientific discoveries are rarely named after their actual discoverers.
Number of distinct objects = total count / order of the symmetry group
This formula is wrong. The correct formula is (1/|G|) × Σ_{g∈G} Fix(g). Simple division would work only if all orbits have the same size (which is rarely the case).
Colorings with built-in symmetry (e.g., monochromatic necklaces) have smaller orbits - simple division undercounts them.
How many distinct colorings of the faces of a cube with 3 colors exist (up to rotation)? |G(cube)| = 24.
Key Ideas
- Group action G on X: (g,x) ↦ g·x with e·x=x and (gh)·x=g·(h·x)
- Orbit of x: Orb(x) = {g·x | g ∈ G}; Stabilizer of x: Stab(x) = {g | g·x = x} ≤ G
- Orbit-Stabilizer Theorem: |Orb(x)| × |Stab(x)| = |G|
- Burnside's Lemma: |X/G| = (1/|G|) × Σ_{g∈G} |Fix(g)|
- Conjugation action: orbits = conjugacy classes, stabilizers = centralizers
Further Paths
Group actions are the foundation for proving the Sylow theorems and for representation theory. In representation theory, groups act on vector spaces by linear transformations.
- Sylow Theorems — The proof of the Sylow theorems is a clever application of a group acting on a set of cosets
- Solvable Groups — The class equation (from the conjugation action) is a key tool in the theory of solvable groups
Вопросы для размышления
- Derive from the orbit-stabilizer theorem: if G acts transitively on X, then |G| = |X| × |Stab(x)|. How does this relate to Lagrange's theorem?
- How many distinct necklaces of 4 beads in 2 colors are there, counting rotations and reflections? Use Burnside's lemma for D₄.
- What does 'transitive action' mean in terms of orbits? Give examples of a transitive and a non-transitive action of S₃.