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 acting on a finite set . The number of orbits in this group action is given by
where denotes all those elements fixed by .
Proof
Take finite acting on finite . Let denote the set of pairs consisting of a and an fixed by ; that is,
The proof essentially proceeds by giving three different ways to count this set .
Way 1. We can decompose along elements as
giving rise to the identity
Way 2. We can decompose along elements as
where denotes the stabilizer of . This gives rise to the identity
Way 3. Similar to way 2, we can decompose along elements ; however, we will additionally group these elements by orbit:
This is possible because the orbits form a partition of . This gives rise to the identity
Now note that for any given orbit we have *
Adding a reference here to the orbit-stabilizer theorem, since references within math typesetting are not recognized =(
Plugging this back into the identity, we get
In other words, when decomposing along orbits, each orbit contributes exactly to the final sum.
Now we will rewrite this one final time as
Combining the three established identities, we get
Picking out the second and fourth expressions, and dividing both by , we get
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 .
As a final remark, I include the following possibly-helpful diagram which my professor made. In this diagram, we have acting by rotation on (length-4 bitstrings). Along the y-axis we have elements , along the x-axis we have elements , and in cells we have .
Elements of are circled in green, and orbits are circled in grey.
Our first way of counting , which is along elements , is visualized here by summing green-circled elements along rows. Likewise, our second way of counting , along elements , 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 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 denote the set ; then we can write the set of (non-cyclic) bitstrings as . Organized by length, looks like this:
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 by noting that our answer is .