Necklaces and Groups. The Burnside Lemma

Here is a fun riddle: suppose you have beads in n different colors, and you want to make a necklace with say, 5 beads. How many different ways are there to do this?

Well, you can first look at the possible colors for the beads:

Each position can have n different colors, and there are 5 positions. So there are n⁵ different possible necklaces, right?

Well…. if you want to hang the necklaces on the wall with only one orientation (you weirdo), it is indeed the solution. However, if you actually want to wear the necklaces, this isn’t right at all.

The reason is that the previous solution doesn’t account for rotations and flips of the necklace, the beads were fixed in position although that is not necessarily true. Two colorings of the first picture may correspond to the same necklace, as you can use rotations or flips to get from one to the other.

So how do we solve this riddle? Well group theory gives us a nice way to solve this and similar problems

A Basic Introduction to Groups:

We want first understand the symmetries of the necklace, that is operations under which two necklaces are identical. This symmetries will result in what is called a group. Let’s look at the symmetries of the necklace.

The first symmetry is probably the most important, yet boring. That is, doing absolutely nothing to the necklace. This is called the identity:

Another symmetry, as stated before, is rotating the necklace. As there are five beads, rotating by a multiple of 72 degrees will preserve the necklace:

Finally, flipping the necklace also preserves it. There are five different flips, each corresponding to an axis going through one of the beads (points):

Is that all, well yes, but actually yes. The thing is, when talking about groups, it is important to talk about the group operation, which is in our case chaining two of these operations (flips and rotations) together. However, these also result in flips and rotations, so we are okay.

Here is a formal definition of what a group is:

Thinking about groups as a set of symmetries such as rotations and flips, the identity element means there is a symmetry of doing nothing, the inverse element means each symmetry can be undone, and associativity means symmetries act “nicely” when using parenthesis.

So in our case, the group G consists of the symmetries under which two necklaces are the same, with the group operation being chaining those symmetries together, the identity element being doing nothing. In group theory, this group is called D₅, the dihedral group with 2*5=10 elements (5 because there are 5 beads)

Of course, there are many, many other examples of groups. For example, the whole numbers (Z) with additions, or the real numbers, except zero, with multiplication (R/{0}). Additionally, there are many other interpretations, some more abstract, of what a group is.

To end this section, note that in the definition of a group, we did not include commutation, that is for elements a, b we have ab=ba. You can see below that for example our group D₅ does not have that conditions. Of course, some groups such as Z are commutative, those groups are also called abelian groups (after the mathematician Niels Henrik Abel).

Group Actions and the Burnside Lemma:

To understand the Burnside lemma and how it helps solving the riddle, we need first to understand the concept of group actions.

Let’s say we have some set S, we say the group G acts on the set S if for each element g in G and element s in S, there is some element g.s in S from the action of G on s, such that the two following conditions hold:

1. The identity element e acts as the identity on S. That is, for each s in S, e.s=s
2. The group actions agrees with the group multiplication. That is, for elements g, h in G and element s in S, (gh).s=g.(h.s). One way to think about this is that multiplication in the groups is like chaining the actions together.

In our case, we will look at the set S of all colorings of the 5 beaded circle (so the necklace, if hung on a wall and the beads are fixed in positions). That is, the n⁵ colorings of the circle we counted on the first attempt at the riddle.

Then, the dihedral group from earlier acts on our set S in a natural way. A rotation on one coloring will lead to another, and so will a flip

Now, remember that if for two colorings in S, if it is possible to get from one to the other using rotations and flips, they corrospond to the same necklace (when the beads are no longer fixed in position). So the actions of D_5 on S can bring one to the other. In group theory, we say this means that the two colorings are in the same orbit of G.

Formally, the orbit of an element s is all elements s’ such that s’ can be reached from s using an action, that is, there is some g in G such that g.s=s’.

So if two circle colorings are in the same orbit (can be reached from one to the other using flips and rotations), they correspond to the same necklace. Then for each orbit there is exactly one corresponding necklace, and it is not hard to see that for each necklace there is exactly one corresponding orbit. Therefore, in order to count the number of colorings of the necklace, we need to count the number of orbits.

But how do we count the orbits? Well mathematician William Burnside has an answer for that:

Now that we have Burnside’s lemma, we can solve the riddle. Let’s look at all elements of D₅ and see how many circle colorings they fix in place (how many colorings stay the same after applying the rotation/flip).

First, the easiest one. As the identity element acts by doing nothing, it fixes all n⁵ possible colorings:

Now let’s move to reflections. Each reflections axis goes through a certain beads as we can see here:

The four remaining beads are then split into two groups, mapped to each other by the action of reflection:

So for the coloring to be fixed by a reflection, the bead on the axis can be any colored (as it is mapped to itself), and each other bead must be the same color as the bead paired to it by reflection. This gives 3 degrees of freedom when coloring the beads. Hence, each reflection fixes n³ elements. As there are 5 possible reflections (one through each bead), this gives a contribution of 5n³ to the average.

Finally, let’s look at rotations, First at the simplest one, 72 degrees clockwise. The beads are mapped as follows:

So for the coloring to be fixed by rotation, bead 1 has to be the same color as bead 2, 2 the same as 3, 3 as 4, 4 as 5, and 5 as 1. Therefore, all beads must be the same color, so there are n possible colorings.

For the three other rotations (144, 216, and 288 degrees), the exact same argument can be made, so overall the rotations contribute 4n to the average.

(Can you see why 5 being a prime number has to do with the fixes of the rotations being the monochromatic colorings?)

Therefore, by Burnsides lemma the number of orbits, and thus necklace colorings, is the following average:

Q.E.D

Other similar questions:

Of course, Burnside’s lemma can be used not just for this example. Perhaps you can look at this same question with any number of beads (say 6). Or you can count the number of necklaces, without reflections. A more difficult application for burnside lemma is for coloring of 3d objects. Say what is the number of possible colorings of the faces of a cube using n colors.

To end this post, here is a fun fact. Burnside’s lemma is named after Burnside. It was actually well known well before being attributed to him (when he wrote it in a book about group theory, even there he attributed it not to himself but Frobenius). Up to 50 years even

I guess Tom Leher was right when he said the secret to sucess in mathematics is to plagerize (disclaimer: not really)