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 XX when each g∈Gg \in G sends each x∈Xx \in X to some g⋅xg \cdot x, with e⋅x=xe \cdot x = x and g⋅(h⋅x)=(gh)⋅xg \cdot (h \cdot x) = (gh) \cdot x. The rotations of a square act on its colorings; the permutations of SnS_n act on {1,…,n}\{1, \ldots, n\}.

  • The orbit of xx is {g⋅x:g∈G}\{g \cdot x : g \in G\}: every place xx can be moved to.
  • The stabilizer of xx is {g:g⋅x=x}\{g : g \cdot x = x\}: the elements that leave xx in place.
  • Fix(g)\text{Fix}(g) is the set of xx that gg leaves in place.

Orbit–stabilizer theorem. ∣orbit(x)∣⋅∣stabilizer(x)∣=∣G∣|\text{orbit}(x)| \cdot |\text{stabilizer}(x)| = |G|.

Burnside’s lemma. The number of orbits is the average number of fixed points:

#orbits=1∣G∣∑g∈G∣Fix(g)∣\#\text{orbits} = \frac{1}{|G|}\sum_{g \in G} |\text{Fix}(g)|
The six necklaces of four beads in two colors Six squares of four beads each, in two rows of three, one for every necklace up to rotation. Top row: all light; one dark bead; two dark beads side by side. Bottom row: two dark beads opposite each other; three dark beads; all dark.
The six necklaces of four beads in two colors

Why averaging fixed points counts orbits

Count the pairs (g,x)(g, x) with g⋅x=xg \cdot x = x in two ways. By gg, it is ∑g∣Fix(g)∣\sum_g |\text{Fix}(g)|. By xx, it is ∑x∣stabilizer(x)∣\sum_x |\text{stabilizer}(x)|. By orbit–stabilizer, each xx contributes ∣G∣∣orbit(x)∣\tfrac{|G|}{|\text{orbit}(x)|}, so the elements of one orbit together contribute exactly ∣G∣|G|. Each orbit adds ∣G∣|G| to the count, so the total is ∣G∣|G| times the number of orbits. Dividing by ∣G∣|G| gives the lemma. It is a combinatorial double count in a group.

Worked examples

Common mistakes

Practice problems

  1. How many 44-bead necklaces in 33 colors are there up to rotation?

    Answer

    2424

    Full solution

    81+3+9+34=964\tfrac{81 + 3 + 9 + 3}{4} = \tfrac{96}{4}.

  2. How many 33-bead necklaces in 33 colors are there up to rotation only?

    Answer

    1111

    Full solution

    27+3+33\tfrac{27 + 3 + 3}{3}.

  3. How many 66-bead necklaces in 22 colors are there up to rotation?

    Answer

    1414

    Full solution

    Rotations by 00 to 55 steps have 6,1,2,3,2,16, 1, 2, 3, 2, 1 cycles, fixing 64,2,4,8,4,264, 2, 4, 8, 4, 2 colorings. The sum is 8484, and 846=14\tfrac{84}{6} = 14.

  4. How many 55-bead necklaces in 22 colors are there up to rotation?

    Answer

    88

    Full solution

    Each of the 44 nonzero rotations is a single 55-cycle and fixes 22: 32+4⋅25\tfrac{32 + 4 \cdot 2}{5}.

  5. S4S_4 acts on {1,2,3,4}\{1, 2, 3, 4\}. What is the stabilizer of 44, and how large is the orbit?

    Answer

    The stabilizer is S3S_3, of order 66; the orbit has 44 elements.

    Full solution

    4⋅6=24=∣S4∣4 \cdot 6 = 24 = |S_4|.

  6. A group of order 1212 acts on a set, and an element has a stabilizer of order 33. How big is its orbit?

    Answer

    44

    Full solution

    123=4\tfrac{12}{3} = 4 by orbit–stabilizer.

  7. Count the 44-bead, 22-color necklaces up to rotations and flips.

    Answer

    66

    Full solution

    Add the four flips: two through opposite beads fix 88 each, two through opposite gaps fix 44 each. 24+248=6\tfrac{24 + 24}{8} = 6.

  8. A student counts 44-bead, 22-color necklaces as 164=4\tfrac{16}{4} = 4. What is wrong?

    Answer

    Orbits differ in size, so dividing evenly fails; the answer is 66.

    Full solution

    All-light and all-dark necklaces are orbits of size 11, and the alternating one has size 22. 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.

What to learn next