Intuitive explanation of the Burnside Lemma

The Burnside Lemma looks like it should have an intuitive explanation. Does anyone have one?

Answer

As an example, we consider the number of ways of colouring a cube with n colours with uniqueness up to rotation. We call each unique colouring where rotations are not allowed a static colouring and each unique one where they are allowed a dynamic colouring. We define the the set of orbits to be the (disjoint) static colourings that correspond to each dynamic colouring. We will use rotations to mean a rotation that makes the cube occupy the same space, and as being unique if it is a unique function from the cube to the cube. This includes the identity rotation. Intuitively, the lemma says:

Proposition 1. #Orbits * #Rotations = Sum for each rotation r of #static colourings unchanged by this rotation

We will now consider each orbit O separately. Pick a static colouring c inside O. Suppose two (possibly equal) rotations p, q give the same static colouring, d, when applied on c. Then p1q fixes d. Additionally, suppose r (possibly the identity) fixes d. p1pr will also fix d. So pr will take c to d. Since pr is different for each r, and p1q is different for each q, the mapping functions are injective in both directions and there is a bijection between the q and r values.

So, for each O, the number of rotations is the sum over each static colorings x in O times the number of rotations producing x. This can be rewritten as the sum over each rotation r of the number of static colourings in O fixed by r (due to the bijection in the previous paragraph). We get proposition 1 by adding over all O.

The general proof is quite similar to this, except that it uses group theory.

Attribution
Source : Link , Question Author : Casebash , Answer Author : Community

Leave a Comment