Orbit-Stabilizer Theorem

Suppose that $G$ is a finite group that acts on some finite set $A$. If $Ga$ is an orbit of some fixed $a \in A$, then we might be interested in how $|Ga|$ is related to $|G|$. Since elements of the stabilizer of $a$ are, in a certain sense, equivalent when it comes to looking at the nontrivial elements of $Ga$, we can consider $G$ modulo the stabilizer of $a$ so that we look only at the irredundant elements of $G$ when it comes to computing $Ga$. Intuitively, this means that there should be some kind of bijection between $Ga$ and $G/\mathrm{Stab}(a)$. So, then, for each element of $Ga$, there are $|\mathrm{Stab}(a)|$ equivalent ways to write that particular element. Summing up over all such elements must give us $|G|$ total elements of $G$. Stated more precisely, we have the following theorem along with a more traditional, less counting-biased proof.

Theorem (Orbit-Stabilizer Theorem). Let $G$ be a finite group acting on a finite set $A$ and fix $a \in A$. Then

Proof. By Lagrange’s Theorem, we know that

Thus, it suffices to show that there is a bijection $f:Ga \to G/\mathrm{Stab}(a)$. Since the action of $G$ is transitive on $Ga$, we may write any element of $Ga$ as $ga$ for some $g\in G$. Thus, define $f$ by $ga \mapsto g \mathrm{Stab}(a)$. Surjectivity is immediate. For injectivity, note that

So then $g^{1}ha = a$. Thus, $ga = ha$ and we are done.

Recall that theorems such as Lagrange’s theorem and the orbit-stabilizer theorem give us ways to enumerate certain objects via group actions. A classical example among the literature (of combinatorics? group theory?) is to consider a necklace with beads of different colors. There are two kinds of symmetries: reflective and rotational. If we want to consider how many distinct rearrangements of the necklace there are, then we just need to count the number of orbits of the dihedral group!

Polya theory, of course, extends well beyond just enumerating the number of ways to put together a necklace. A good reference is Chapter 7 of Stanley’s Algebraic Combinatorics: Walks, Trees, Tableaux, and More. Jeremy Martin also has a nice writeup in his notes on algebraic combinatorics, section 11.3. One day, I hope to find some time to write up a little on Polya theory.