Abstract Algebra · Undergraduate
Group Actions, Orbits and Burnside's Lemma
Quick answer
A group acts on a set when each group element moves the set's elements around in a way that respects the group operation, as rotations move the beads of a necklace. The orbit of an element is everything it can be moved to; its stabilizer is the set of group elements that leave it fixed, and |orbit| · |stabilizer| = |G|. Burnside's lemma counts orbits: average, over the group, the number of elements each one fixes. With it, there are 6 different necklaces of 4 beads in 2 colors, not 16.
What you'll learn
- Describe a group action and compute orbits and stabilizers
- Apply the orbit–stabilizer theorem
- Count fixed points of each group element
- Count colorings up to symmetry with Burnside's lemma
Groups that move things
A group acts on a set when each sends each to some , with and . The rotations of a square act on its colorings; the permutations of act on .
- The orbit of is : every place can be moved to.
- The stabilizer of is : the elements that leave in place.
- is the set of that leaves in place.
Orbit–stabilizer theorem. .
Burnside’s lemma. The number of orbits is the average number of fixed points:
Why averaging fixed points counts orbits
Count the pairs with in two ways. By , it is . By , it is . By orbit–stabilizer, each contributes , so the elements of one orbit together contribute exactly . Each orbit adds to the count, so the total is times the number of orbits. Dividing by gives the lemma. It is a combinatorial double count in a group.
Worked examples
Common mistakes
Practice problems
-
How many -bead necklaces in colors are there up to rotation?
Answer
Full solution
.
-
How many -bead necklaces in colors are there up to rotation only?
Answer
Full solution
.
-
How many -bead necklaces in colors are there up to rotation?
Answer
Full solution
Rotations by to steps have cycles, fixing colorings. The sum is , and .
-
How many -bead necklaces in colors are there up to rotation?
Answer
Full solution
Each of the nonzero rotations is a single -cycle and fixes : .
-
acts on . What is the stabilizer of , and how large is the orbit?
Answer
The stabilizer is , of order ; the orbit has elements.
Full solution
.
-
A group of order acts on a set, and an element has a stabilizer of order . How big is its orbit?
Answer
Full solution
by orbit–stabilizer.
-
Count the -bead, -color necklaces up to rotations and flips.
Answer
Full solution
Add the four flips: two through opposite beads fix each, two through opposite gaps fix each. .
-
A student counts -bead, -color necklaces as . What is wrong?
Answer
Orbits differ in size, so dividing evenly fails; the answer is .
Full solution
All-light and all-dark necklaces are orbits of size , and the alternating one has size . Burnside’s lemma accounts for this.
Frequently asked questions
What is a group action?
A rule that lets each element g of a group G move each element x of a set X to g·x, with e·x = x and g·(h·x) = (gh)·x.
What are orbits and stabilizers?
The orbit of x is the set {g·x : g in G} of places x can be moved to. The stabilizer of x is the subgroup {g : g·x = x} of elements that leave it fixed.
What is the orbit–stabilizer theorem?
For a finite group, |orbit of x| · |stabilizer of x| = |G|.
What is Burnside's lemma?
The number of orbits equals the average number of fixed points: (1/|G|) Σ |Fix(g)|, where Fix(g) is the set of elements g leaves unchanged.
How many 4-bead necklaces in 2 colors are there up to rotation?
6. The rotations by 0, 1, 2, 3 positions fix 16, 2, 4 and 2 colorings, and (16 + 2 + 4 + 2)/4 = 6.