BURNSIDE'S LEMMA
Introduction

Take one square, and give each side one of three colors: red, green or blue. Each side is colored indenpendently, all combinations of colors are allowed. If you don't have a clear visual idea of what this means, here is a little demo. Click the sides of the square to change their colors.

There is a total of \(3^4 = 81\) combinations. But what if some combinations aren't considered different? After all, one could argue that these two squares are colored the same way and just rotated by \(90°\):

So, what then? How can the number of squares be counted if some of them aren't different?

Equivalence relations

First, a definition for equivalence has to be chosen. No matter how equivalence is defined, there are three properties that should always be contained in its definition:

  • Reflexivity This is straightforward: Each element should be equal to itself. The square below is equivalent to itself for any definition of equivalence, and so is every other square.

  • Symmetry When calling two things the same, the order shouldn't matter. So, if some square A is equivalent to another square B, then square B is equivalent to square A.


    then

  • Transitivity Last, it should be possible to 'transfer' equivalence over 'connecting' elements. If A and B are the same, and so are B and C, it would be strange to think of A and C as different.


    and

    then

These three lines, \(\equiv\), that look similar to the equal sign, mean that the elements to the left and right equivalent. There are two different signs to differentiate between the standard equality, where each object is only equal to itself, and custom definition.

Automorphisms

Let's go back to the example of colored squares. These squares can be turned into other squares by modifying them using some rule. Here are a few clickable examples:

  • Left Rotation by 90°.

  • Middle Cycling the right side red → green → blue.

  • Right Mirrored along a horizontal axis.

These modifications are called automorphisms. In a more general sense, automorphisms take some element and transform it into another element of the same type. Additionally, automorphisms require this transformation to be reversible.

For the rest of this text, automorphisms are simply called operations.

So, what do operations have to do with equivalence? They can actually be used to define what equivalence means! Take some set of operations, and then say: A and B are equal if applying one of these operations to A results in B. But it's not that simple...

Example: 90° rotation

Let's take the 90°-rotation as an operation. Saying A and B are equal if A rotated by 90° is B leaves some problems. The requirements for an equivalence relation aren't fulfilled yet, so let's go through them one by one:

  • Reflexivity Each element should be equivalent to itself. So, we need to add a 0° rotation to the the set of operations.
    In general, this means that the operation of 'doing nothing', also called the identity, always has to be part of the set of operations.

  • Symmetry When turning one square by 90° in one direction results in another square, the other square can be rotated by -90° to obtain the original square. Note that a 270° rotation is exactly the same as -90° rotation.
    In general, this means that for each operation in the set, the inverse operation is also needed. The inverse operation is just an undo on the original operation. Some other examples are:

    • If adding 2 to a number is an operation, so should be subtracting 2.
    • If removing an 'a' from the end of a word is an operation, so should be adding an 'a' to the end.
    • If changing the color of the right side from red to green is an operation, so should be the change from green to red.

  • Transitivity When turning one square by 90° is an operation, then two 90° turns can be chained into a 180° rotation.
    In general, chaining any two operations together should result in another operation in the set. This property is called 'closure'.

The resulting set of operations is {id, 90°, 180°, -90°}. id is the identity, the operation that does nothing. The remaining operations stand for clockwise rotations by the noted angle.

Closure and the existance of inverses need to be checked for all other, new operations as well. Luckily, they are already fulfilled. The tables below show this:

  • Inverse operations
    Operation Inverse operation
    id id
    90° -90°
    180° 180°
    -90° 90°
  • Closure
    id 90° 180° -90°
    id id 90° 180° -90°
    90° 90° 180° -90° id
    180° 180° -90° id 90°
    -90° -90° id 90° 180°
Invariance

I promise, this is the last prerequisite before this gets back to counting. Remember, the goal is still to count the number of squares if some of them are considered equal. So, what else do you need to know? This concept called invariance. Sometimes, an element doesn't change when certain operations are applied to it.

  • Left If all sides have the same color, it doesn't matter how it is rotated. It always remains the same.

  • Middle If opposite sides have the same color, a rotation by 90° or -90° changes it. A rotation by 0° or 180° doesn't.

  • Right In all other cases, the square is only invariant under 0° rotation. Every element is always invariant under the identity operation, that is basically how it is defined.

Equivalence classes

These concepts now allow us to define more precisely what it is that has to be counted, namely, the so-called equivalence classes. Each class is a box which contains only elements equal to itself.

A good example for this are even and odd numbers. In this case, every even number is equivalent to all other even numbers. The same is true for odd numbers. Take a moment to convince yourself that this really defines an equivalence on the whole numbers.

This puts each element in exactly one box. These boxes can have different sizes, however. An example for this are the 3-colored squares:

These classes are smaller if the elements inside of them are invariant under more operations.

Filling classes

These boxes are still a bit hard to handle, due to the difference in size. Let's flatten these boxes, making it such that the contain exactly as many elements as operations. For some boxes, this doesn't mean anything. For others, some elements need to be copied some times.

This gives a plan on how to calculate the number of boxes. First, calculate how many times each element appears in these filled boxes. Then, divide by the size of the new boxes, which is exactly the number of operations.

Every element appears once for each operation that doesn't change the element. This number can vary depending on the element and the operations chosen. Staying with the example of rotation, a square with the same color on every side is invariant under all operations. Others are only invariant under the identity. This has already been shown earlier.

This already gives a solution to the initial counting problem: First, find the number of operations each element is invariant under. Take the sum of these numbers. Last, divide by the number of operations.

Burnside's Lemma uses a different formulation of this, however. Instead of finding under how many operations each element is invariant, the number of invariant elements for each operation is counted. The result is the same, as both effectively count the number of pairs of an element and an operation, such that the element is invariant under the operation.

This is it, that's all you need to know. This gives the formula for Burnside's Lemma. Let \(G\) be the set of operations and \(X\) the original set of elements. Further, let \(|X^g|\) be the amount of elements in \(X\) that are invariant under some operation \(g \in G\). $$|X / G| = \frac{1}{|G|} \cdot \sum_{g \in G} |X^g|$$

Step-by-step example

Here is the step-by-step calculation for the example used so far: 3 colors, 4 sides, rotations by 0°, 90°, 180° and -90°. Then, the number of elements is $$|X / \{\text{id, 90°, 180°, -90°}\}| = \frac{1}{4} \cdot (|X^\text{id}| + |X^\text{90°}| + |X^\text{180°}| + |X^\text{-90°}|)$$

  • id Every element is invariant under the identity. The very definition of the identity is that it doesn't change any element. Therefore, \(|X^\text{id}| = |X| = 81\), as calculated in the introduction.
  • 90° When turning the square by 90° clockwise, the following side changes happen:
    • Left becomes top
    • Top becomes right
    • Right becomes bottom
    • Bottom becomes left
    If side A becomes side B, the need to have the same color to stay invariant under the operation. By the power of transitivity, it can be followed the all sides need to be the same. There are 3 squares that fullfill this criteria, the unicolored squares for each of the colors. Therefore, \(|X^\text{90°}| = 3\).
  • 180° When turning a square 180°, opposite sides swap their color. This leaves two color choices: one for the left and right side, and one for the top and bottom side. This results in \(|X^\text{180°}| = 3^2 = 9\)
  • -90° This is calculated/argued the same way 90° is, and so, \(|X^\text{-90°}| = |X^\text{90°}| = 3\)

The sum evaluates to $$|X^\text{id}| + |X^\text{90°}| + |X^\text{180°}| + |X^\text{-90°}| = 81 + 3 + 9 + 3 = 96$$ This gives the final result of $$|X / \{\text{id, 90°, 180°, -90°}\}| = \frac{1}{4} \cdot 96 = 24$$

Further examples

This is a collection of use cases of Burnside's Lemma that I've encountered.

  • Regular polygons and rotations This is the generalized version of the example up to this point: Given are n sides and k colors. Each side of the regular k-sided polygon is colored. Then, it can be rotated freely.

    The generalized formula is $$\frac{1}{k} \sum_{i = 0}^k n^{\gcd(i, k)}$$ There are k rotation operations. The rotation by i sides requires that each side is equal to the side i further ahead. This leaves a free choice for the first gcd(i, k) sides.

    A few examples for some values of k are:

    • For k = 4: \(n^3 + n^2 + 2n\)
    • For k = 6: \(n^6 + n^3 + 2n^2 + 2n\)
    • For k = 8: \(n^8 + 3n^2 + 4n\)
    • For any prime p: \(n^p + (p - 1) \cdot n\)

  • Permutations Given are k dots and n colors. Each dot is colored. Then, the dots can be exchanged freely.

    This is an example which is probably better solved without Burnside's Lemma. One can define some ordering on the colors, for example ·Red < ·Green < ·Blue < ..., and then represent every equivalence class by the sorted element. For example, the element ( ·Green, ·Blue, ·Green, ·Red ) would be represented by ( ·Red, ·Green, ·Green, ·Blue ). These are exactly the combinations with repititions.

    It follows that this is solved by the general formula for combinations with repititions: $$\begin{pmatrix} n + k - 1 \\ k \end{pmatrix}$$

  • Rotating a cube Each side of a cube is colored in one of 6 colors, such that each side has a different color. The cube can be rotated freely. This example is from Brilliant's explanation of Burnside's Lemma.

    There are 24 rotation operations. First, take any of the six sides and orient it upward. Then, take any of the four sides perpendicular to the top and orient it to the left. This leaves 6 · 4 = 24 options.
    There are 6 possible colors for the first side, 5 for the next, and so on. So, there is a total of 6! = 720 colorings.
    No coloring is invariant under any operations except for the identity, so the final result is $$\frac{1}{24} |X^\text{id}| = \frac{1}{24} \cdot 720 = 30$$