Group action, orbits, and stabilizers

Group action¶

Definition: If $G$ is a group with identity element $e$ , and $X$ is a set, then a group action $α$ of $G$ on $X$ is a function

α : G \times X \to X

that satisfies two axioms for all $g, h \in G, x \in X$ :

identity: $α (e, x) = x$
compatibility $α (g, α (h, x)) = α (g h, x)$

with $α (g, x)$ often shortened to $g x$ or $g \cdot x$ when there's no ambiguity of the action being considered in the context. The group $G$ is said to act on $X$ ; a set $X$ together with the action of $G$ is called a $G$ -set.

From these two axioms, we know that the function that maps $x$ to $g \cdot x$ is a bijection, since we have the inverse map $g^{- 1}$ such that $g^{- 1} \cdot (g \cdot x) = x$ .

Orbits and stabilizers¶

Consider a group $G$ acting on a set $X$ .

Definition: The orbit of an element $x \in X$ is the set of elements in $X$ which $x$ can be moved to through the group action, denoted by $G \cdot x$ :

G \cdot x = {g \cdot x | g \in G}

Proposition: If and only if there exists a $g \in G$ such that $g \cdot x = y$ for $x, y \in X$ , we say that $x \sim y$ . This is an equivalence relation.

Proof:

Reflectivity: $e\cdot x = x\implies x\sim x $
Symmetry: $x \sim y ⟹ g \cdot x = y ⟹ x = g^{- 1} \cdot y ⟹ y \sim x$
Transitivity: $x \sim y \land y \sim z ⟹ g \cdot x = y, h \cdot y = z ⟹ h \cdot (g \cdot x) = (h g) \cdot x = z ⟹ x \sim z$

This proposition implies that the set of orbits of $X$ under the group action $G$ forms a partition of $X$ .

Definition: Given $g \in G$ and $x \in X$ with $g \cdot x = x$ , we say $x$ is fixed under the action of $g$ . For every $x \in X$ , its stabilizer in $G$ is the set of all elements $g \in G$ that fixes $x$ , denoted as $G_{x}$ :

G_{x} = {g \in G | g \cdot x = x}

The stabilizer is more often called a stabilizer subgroup! Indeed, we can prove this by verifying the conditions:

For $g \in G_{x}$ , we have

x = e \cdot x = (g^{- 1} g) \cdot x = g^{- 1} \cdot (g \cdot x) = g^{- 1} \cdot x

Thus $g^{- 1} \in G_{x}$ .

The identity element $e$ is clearly in $G_{x}$ since $e \cdot x = x$ .

For $g, h \in G_{x}$ ,

g h \cdot x = g \cdot (h \cdot x) = g \cdot x = x ⟹ g h \in G_{x}

Thus, $G_{x}$ is a subgroup of $G$ .

Orbit-stabilizer theorem¶

Theorem: For a finite group $G$ acting on a set $X$ and any element $x \in X$ .

| G \cdot x | = [G : G_{x}] = \frac{| G |}{| G_{x} |}

Proof: For a fixed $x \in X$ , consider the map $f : G \to X$ given by mapping $g$ to $g \cdot x$ . By definition, the image of $f (G)$ is the orbit of $G \cdot x$ . If two elements $g, h \in G$ have the same image:

f (g) = f (h) ⟺ g \cdot x = h \cdot x ⟺ g^{- 1} h \cdot x = x ⟺ g^{- 1} h \in G_{x} ⟺ h \in g G_{x}

In other words, $f (g) = f (h)$ if and only if they are in the same coset for the stabilizer subgroup $G_{x}$ . Hence, $f$ induces a bijection between the set $G / G_{x}$ of cosets and the orbit $G \cdot x$ which sends $g G_{x} \mapsto g \cdot x$ . Combining the bijection with lagrange theorem gives orbit-stabilizer theorem as desired.

Burnside's Lemma¶

This is a lemma useful in taking account of symmetry when counting mathematical objects. It can be proven by orbit-stabilizer theorem and we will show that in later sections.

Theorem: Let $G$ be a finite group acting on a set $X$ . For each $g \in G$ , let $X^{g}$ denote the set of elements in $X$ that are fixed by $g$ :

X^{g} = {x \in X | g \cdot x = x}

Burnside's lemma provides a formula for the number of orbits, denoted by $X / G$ :

| X / G | = \frac{1}{| G |} \sum_{g \in G} | X^{g} |

Examples¶

First, we want to see how we can apply it in real life. Suppose we want to see how many ways we can color a cube with 3 colors, it would be simply $3^{6} = 729$ ways. However, what if two colorings are essentially the same after some rotations?

Let $X$ be the set of all $3^{6}$ color combination and $G$ be the rotational symmtery group of the cube acting on $X$ in the natural manner. There are $6 \times 4 = 24$ elements in $G$ .

Then two elements of $X$ belong to the same orbit if one can be rotated to the other. Hence, we are finding the number of orbits! Now, it suffices to calculate $X^{g}$ for all $g \in G$ :

the identity element fixes all elements of $X$ .
six 90-degree face rotations, each fixes $3^{3}$ elements of $X$ .
three 180-degree face rotations, each fixes $3^{4}$ elements of $X$ .
eight vertex rotations, each fixes $3^{2}$ elements of $X$ .
six edge flip, each fixes $3^{3}$ elements of $X$ .

Hence, the average fix size is

\frac{1}{24} (3^{6} + 6 \times 3^{3} + 3 \times 3^{4} + 8 \times 3^{2} + 6 \times 3^{3}) = 57

Finally, how do we prove this lemma?

Proof: First, we would like to re-express the sum over group elements $g \in G$ as an equivalent sum over elements $x \in X$ :

\sum_{g \in G} | X^{g} | = | {(g, x) \in G \times X | g \cdot x = x} | = \sum_{x \in X} | G_{x} |

By orbit-stabilizer theorem, we can rewrite the equation into:

\sum_{x \in X} | G_{x} | = | G | \sum_{x \in X} \frac{1}{| G \cdot x |}

Finally, notice that the set of orbits partition $X$ , so we can break the sum into separate sums over each individual orbit:

\sum_{x \in X} \frac{1}{| G \cdot x |} = \sum_{A \in X / G} \sum_{x \in A} \frac{1}{| A |} = | X / G |

Putting everything together, we get:

| X / G | = \frac{1}{| G |} \sum_{g \in G} | X^{g} |