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 GG acting on a finite set AA. The number of orbits in this group action is given by 1GgGAg\frac 1 { \lvert G \rvert } \sum_{g \in G}{\lvert A^g \rvert} where AgA^g denotes all those elements aAa \in A fixed by gg.
Proof
Take finite GG acting on finite AA. Let FF denote the set of pairs consisting of a gGg \in G and an aAa \in A fixed by gg; that is, F={(g,a)G×Aga=a}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 FF. Way 1. We can decompose FF along elements gGg \in G as F=gG{aAga=a}=gGAgF = \bigcup_{g \in G} \{ a \in A \mid g \bull a = a \} = \bigcup_{g \in G} A^g giving rise to the identity F=gGAg\lvert F \rvert = \sum_{g \in G}{\lvert A^g \rvert} Way 2. We can decompose FF along elements aAa \in A as F=aA{gGga=a}=aAstab(a)F = \bigcup_{a \in A} \{ g \in G \mid g \bull a = a \} = \bigcup_{a \in A} \text{stab}(a) where stab(a)\text{stab}(a) denotes the stabilizer of aa. This gives rise to the identity F=aAstab(a)\lvert F \rvert = \sum_{a \in A}{\lvert \text{stab}(a) \rvert} Way 3. Similar to way 2, we can decompose FF along elements aAa \in A; however, we will additionally group these elements by orbit: F=orbit OaOstab(a)F = \bigcup_{\text{orbit } O} \bigcup_{a \in O} {\text{stab}(a)} This is possible because the orbits form a partition of AA. This gives rise to the identity F=orbit OaOstab(a)\lvert F \rvert = \sum_{\text{orbit } O} \sum_{a \in O} {\lvert \text{stab}(a) \rvert} Now note that for any given orbit OO we have *
Adding a reference here to the orbit-stabilizer theorem, since references within math typesetting are not recognized =(
aOstab(a)=aOGorbit(a)1orbit-stabilizer theorem=aOGO1aO    orbit(a)=O=O(GO1)sum body invariant wrt sum variable=G\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 F=orbit OG\lvert F \rvert = \sum_{\text{orbit }O} \lvert G \rvert In other words, when decomposing FF along orbits, each orbit OO contributes exactly G\lvert G \rvert to the final sum. Now we will rewrite this one final time as F=G# of orbits\lvert F \rvert = \lvert G \rvert \cdot \#\text{ of orbits} Combining the three established identities, we get F=gGAg=aAstab(a)=G# of orbits\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 G\lvert G \rvert, we get 1GgGAg=# of orbits\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 F\lvert F \rvert.
As a final remark, I include the following possibly-helpful diagram which my professor made. In this diagram, we have G=Z/4G = \mathbb Z / 4 acting by rotation on A=24A = \mathbf 2^4 (length-4 bitstrings). Along the y-axis we have elements gZ/4g \in \mathbb Z / 4, along the x-axis we have elements a24a \in \mathbf 2^4, and in cells we have gag \bull a. Elements of FF are circled in green, and orbits are circled in grey. Our first way of counting FF, which is along elements gGg \in G, is visualized here by summing green-circled elements along rows. Likewise, our second way of counting FF, along elements aAa \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=G4 = \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 2\mathbf 2 denote the set {0,1}\{0,1\}; then we can write the set of (non-cyclic) bitstrings as 23\mathbf 2^3. Organized by length, 23\mathbf 2^3 looks like this:
000 100 010 001 011 101 110 111
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 23/\mathbf 2^3 / \sim, which we can visualize as so:
000 100 010 001 011 101 110 111
Separately, consider the group Z/3\mathbb Z / 3 acting on 23\mathbf 2^3 by rotation; that is, where nˉb\bar n \bull b is bb rotated nn times. Such a group action exhibits the following orbits:
000 100 010 001 011 101 110 111
Note that the orbits of this group action correspond exactly to the equivalence classes of 23/\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 1Z/3r=0ˉ,1ˉ,2ˉ(23)r=13(8+2+2)=4\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 23/\mathbf 2^3/\sim by noting that our answer is 23/=4\lvert \mathbf 2^3/\sim \rvert = 4.
1Z/r=0ˉ,,1(2)r\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: