Aug 3, 2023

From Burnside to Polya: A Short Introduction to Group Theory

Consider this famous necklace counting problem:

Assume a necklace can be made with \( n \ (1\le n\le 10^5) \) beads. Each bead can be painted with one of the \( k\ (1\le k\le 10^5) \) colors. We consider two necklaces the same if after rotating and flipping they look identical. How many different necklaces are there in total?

The solution to this problem is often represented in terms of group theory jargon. In this post we will try to explain and demystify the process.

Permutation and Group Action

One of the easiest ways to describe a necklace is to use some array to record the color of every bead in counter-clockwise order starting from some bead (say the top one). Consider an example of 5 beads and 2 colors. We can try to describe the arrangement with an array of length 5. Let us call this array a representation of the necklace. For instance, the arrangement below can be described as \( (0, 1, 1, 0, 0) \):

Now one thing about why this problem is hard is because that the same necklace can rotate and flip, thus having different representations. For instance, the necklace below is the same as the necklace above, but has a different representation \( (1, 0, 0, 0, 1) \):

In order to study how different representations are equivalent to each other, we want to study how a necklace can rotate and flip. It is easy to notice that after some operation, the total number of beads have not changed; they merely changed positions with each other in the representation. Therefore, it is tempting to write down the operation as some form of permutation of representation, i.e.:

We can verify that this permutation of representation is a valid rotation and notice that when \( (a_1,a_2,a_3,a_4,a_5) \) is \( (0, 1, 1, 0, 0) \), \( (a_3,a_4,a_5,a_1,a_2) \) turns out to be indeed \( (1, 0, 0, 0, 1) \). In order to simplify the writing, we can simply dot down the permutation as \( (3, 4, 5, 1, 2) \). Note how a permutation is different from a representation of a necklace, despite that they are both arrays of length 5. We can also write down this fact with a simpler math statement:

Now we will be able to assert one thing: if one representation \( a \) is able to get to some representation \( b \) after a valid operation permutation \( p \), i.e. \( pa = b \), then we know that \( a \) and \( b \) are equivalent. Then we need to figure out one thing: how many valid permutations are there and what are they? Fortunately, for this example, we can easily think about how the necklace can rotate and flip: without flipping, the necklace can rotate 5 times before getting back to the initial representation; the same goes with flipping. Therefore, there are a total of 10 valid permutations, listed below:

This set of permutations \( P=(p_1,p_2,\cdots,p_{10}) \) is called a group action in math jargon because it can 'act' on a representation of necklace to create a new representation. It also bears some resemblance to what mathematicians call a group. Most notably, we observe that two permutations \( p_1, p_2 \) can 'multiply' to create a new permutation that is equivalent to applying \( p_1 \) first and \( p_2 \) second.

For instance, let us say that we have some representation \( a\in A \) that we want to apply \( p_1=(2, 3, 4, 5, 1) \) and then \( p_2=(3, 4, 5, 1, 2) \) again, we can easily verify that this is equivalent to rotating clockwise once then twice and thus equivalent to rotating three times - \( (4, 5, 1, 2, 3) \). We can then verify the equation with some random representation:

One way to compute this multiplication is to treat \( p_1 \) as some representation and apply \( p_2 \) to it. We observe that this set of permutations do have some interesting properties that make mathematicians call it a group:

• The multiplication of any two permutations \( p_2p_1 \) is still in the set. This is called closure.
• Take any three permutations and we have \( p_3(p_2p_1)=(p_3p_2)p_1 \). This is called associativity.
• There exists a permutation \( e=(1,2,3,4,5) \) that means doing nothing (the identity element).
• For every permutation \( p \) there exists an inverse permutation \( p' \) to 'undo the operation', i.e. \( p'p=e \).

We have taken a detour to the land of the group action. However, with all these good properties we can start to think about and solve our necklace problem.

Burnside's Lemma: Observe the Invariant

One trivial idea that does not work is to observe that every representation can be permuted 10 different ways and thus divide the total number of representations \( |A| = 2^5 \) by 10. The reason why it does not work is that there may be multiple permutations that tranforms representation \( a \) to representation \( b \). For instance, both \( (3, 4, 5, 1, 2) \) and \( (2, 1, 5, 4, 3) \) transforms \( (0, 1, 1, 0, 0) \) to \( (1, 0, 0, 0, 1) \), so a simple division does not work.

Fortunately, there is some useful observation to think about the issue:

(Coset): Denote \( P(a, b) \) as the set of permutations that tranforms representation \( a \) to \( b \). If \( |P(a, b)| > 0 \), then \( |P(a, b)| = |P(a, a)| \).

Yes, somehow the number of permutations that transforms \( a \) to \( b \) is the same as the number of permutations that transforms \( a \) to itself! To intuitively think of a proof, consider any permutation \( p_0 \) that transforms \( a \) to \( b \). Then, for every permutation \( p' \) in \( P(a, a) \), we can claim that \( p''=p_0p' \) is a permutation that transforms \( a \) to \( b \). It takes a little finesse to show that every \( p'' \) is different and that this is a bijection (mainly by using the inversion of \( p_0 \), but it can be done with patience).

Now we consider every representation that some random \( a\in A \) can reach, also known as \( a \)'s orbit \( [P\cdot a] \). We observe that every element in \( [P\cdot a] \) is highly symmetric: they all have the same number of permutations to get to each other, as well as get to itself. Therefore,

This gives us some insight: we can just think about every pair of representations and permutations \( (a, p) \) such that \( pa=a \), and the number of the pairs is exactly the number of different orbits times \( |P| \). Now we turn back to the original problem: we want to figure out how many different representations there are in a certain set of representations \( A \) (namely \( 2^5 \) representations in our example), up to a certain group action \( P \). Notice that what we want is exactly the number of different orbits, and thus can be calculated by finding all the pairs and dividing by \( |P| \):

This equation is called Burnside's Lemma.

Polya's Theorem: Counting the Number of Invariants

Now the problem is very simple: given some permutation \( p \), we want to figure out the number of representations that does not change when transformed by \( p \). This is not a very difficult problem: let us say that \( p = (a_0, a_1, \cdots, a_5) \). We observe that 0 and \( a_0 \) must have the same color; the same goes for 1 and \( a_1 \), etc. Eventually, we end up with several blocks that must have the same color. If you know that permutations can be written as cycles, then you can see that the number of cycles are the number of blocks. Anyway, let us say that we have \( c(p) \) distinct blocks for this permutation, then the number of representations is exactly \( m^{c(p)} \), where \( m \) is the number of colors.

This gives us the final Polya's Theorem:

Practice Problem

• POJ 2409
• Codeforces 1065E