Burnside’s Lemma
Statement
Burnside’s lemma, also called the lemma that is not Burnside’s, gives an expression for the number of orbits formed by a group action. Take a finite group $G$ acting on a finite set $A$. The number of orbits in this group action is given by $\frac 1 { \lvert G \rvert } \sum_{g \in G}{\lvert A^g \rvert}$ where $A^g$ denotes all those elements $a \in A$ fixed by $g$.
Proof
Take finite $G$ acting on finite $A$. Let $F$ denote the set of pairs consisting of a $g \in G$ and an $a \in A$ fixed by $g$; that is, $F = \{ (g, a) \in G \times A \mid g \bull a = a \}$ The proof essentially proceeds by giving three different ways to count this set $F$. Way 1. We can decompose $F$ along elements $g \in G$ as $F = \bigcup_{g \in G} \{ a \in A \mid g \bull a = a \} = \bigcup_{g \in G} A^g$ giving rise to the identity $\lvert F \rvert = \sum_{g \in G}{\lvert A^g \rvert}$ Way 2. We can decompose $F$ along elements $a \in A$ as $F = \bigcup_{a \in A} \{ g \in G \mid g \bull a = a \} = \bigcup_{a \in A} \text{stab}(a)$ where $\text{stab}(a)$ denotes the stabilizer of $a$. This gives rise to the identity $\lvert F \rvert = \sum_{a \in A}{\lvert \text{stab}(a) \rvert}$ Way 3. Similar to way 2, we can decompose $F$ along elements $a \in A$; however, we will additionally group these elements by orbit: $F = \bigcup_{\text{orbit } O} \bigcup_{a \in O} {\text{stab}(a)}$ This is possible because the orbits form a partition of $A$. This gives rise to the identity $\lvert F \rvert = \sum_{\text{orbit } O} \sum_{a \in O} {\lvert \text{stab}(a) \rvert}$ Now note that for any given orbit $O$ we have *
Adding a reference here to the orbit-stabilizer theorem, since references within math typesetting are not recognized =(
\begin{align*} & \sum_{a \in O} {\lvert \text{stab}(a) \rvert} \\ &= \sum_{a \in O} {\lvert G \rvert \cdot \lvert \text{orbit(a)} \rvert^{-1}} &&\text{orbit-stabilizer theorem} \\ &= \sum_{a \in O} {\lvert G \rvert \cdot \lvert O \rvert^{-1}} && a \in O \implies \text{orbit}(a) = O \\ &= \lvert O \rvert \cdot \left( {\lvert G \rvert \cdot \lvert O \rvert^{-1}} \right) && \text{sum body invariant wrt sum variable} \\ &= \lvert G \rvert \end{align*} Plugging this back into the identity, we get $\lvert F \rvert = \sum_{\text{orbit }O} \lvert G \rvert$ In other words, when decomposing $F$ along orbits, each orbit $O$ contributes exactly $\lvert G \rvert$ to the final sum. Now we will rewrite this one final time as $\lvert F \rvert = \lvert G \rvert \cdot \#\text{ of orbits}$ Combining the three established identities, we get $\lvert F \rvert = \sum_{g \in G} {\lvert A^g \rvert} = \sum_{a \in A} {\lvert \text{stab}(a) \rvert} = {\lvert G \rvert} \cdot \#\text{ of orbits}$ Picking out the second and fourth expressions, and dividing both by $\lvert G \rvert$, we get $\frac 1 {\lvert G \rvert} \sum_{g \in G} {\lvert A^g \rvert} = \#\text{ of orbits}$ which is exactly the statement of Burnsides’s lemma; done! rk
Note that we did not actually end up using counting method #2; it’s a stepping stone to method #3 as well as a footnote of yet another way to compute $\lvert F \rvert$.
As a final remark, I include the following possibly-helpful diagram which my professor made. In this diagram, we have $G = \mathbb Z / 4$ acting by rotation on $A = \mathbf 2^4$ (length-4 bitstrings). Along the y-axis we have elements $g \in \mathbb Z / 4$, along the x-axis we have elements $a \in \mathbf 2^4$, and in cells we have $g \bull a$. Elements of $F$ are circled in green, and orbits are circled in grey. Our first way of counting $F$, which is along elements $g \in G$, is visualized here by summing green-circled elements along rows. Likewise, our second way of counting $F$, along elements $a \in A$, is a summation along columns. The third way, along orbits, is visualized by summing along columns, but grouping the columns into orbits. Note that each orbit contributes exactly $4 = \lvert G \rvert$ elements!
Example application
We can use Burnside’s Lemma in order to aid counting the number of cyclic bitstrings of a given size. For illustrative examples, let’s first consider the specific case of cyclic bitstrings of length 3. Let $\mathbf 2$ denote the set $\{0,1\}$; then we can write the set of (non-cyclic) bitstrings as $\mathbf 2^3$. Organized by length, $\mathbf 2^3$ looks like this:
Define an equivalence relation $\sim$ by identifying bitstrings which are rotations of each other. Then the set of cyclic bitstrings of length 3 is given by $\mathbf 2^3 / \sim$, which we can visualize as so:
Separately, consider the group $\mathbb Z / 3$ acting on $\mathbf 2^3$ by rotation; that is, where $\bar n \bull b$ is $b$ rotated $n$ times. Such a group action exhibits the following orbits:
Note that the orbits of this group action correspond exactly to the equivalence classes of $\mathbf 2^3 / \sim$. As such, the number of equivalence classes (and thus the number of cyclic bitstrings) is given by Burnside’s Lemma as \begin{align*} & \frac 1 { \lvert \mathbb Z/3 \rvert } \sum_{r =\bar 0, \bar 1, \bar 2} \left\lvert \left( \mathbf 2^3 \right)^r \right\rvert \\ &= \frac13\left( 8 + 2 + 2 \right) \\ &= 4 \end{align*} Further, this approach generalizes nicely rk! In general, the number of cyclic bitstrings of length $\ell$ is given by
Generalizing to longer bitstrings is really the utility of using Burnside’s lemma here; in the specific case of length-3 bitstrings we could have just stopped after constructing the diagram for $\mathbf 2^3/\sim$ by noting that our answer is $\lvert \mathbf 2^3/\sim \rvert = 4$.
$\frac 1 {\lvert \mathbb Z/\ell \rvert} \sum_{r=\bar 0, \dots, \overline {\ell - 1}} \left\lvert \left( \mathbf 2^\ell \right)^r \right\rvert$

Referenced by: