15.3: Burnside's Lemma

Burnside's lemma relates the number of equivalence classes of the action of a group on a finite set to the number of elements of the set fixed by the elements of the group. Before stating and proving it, we need some notation and a proposition. If a group \(G\) acts on a finite set \(\mathcal{C}\), let ~ be the equivalence relation induced by this action. (As before, the action of \(\pi∈G\) on \(\mathcal{C}\) will be denoted \(\pi^∗\).) Denote the equivalence class containing \(C∈\mathcal{C}\) by ⟨\(C\)⟩. For \(\pi∈G\), let \(fix_C⁡(\pi)=\{C∈ \mathcal{C}:\pi^∗(C)=C\}\), the set of colorings fixed by \(\pi\). For \(C∈ \mathcal{C}\), let \(stab_G⁡(C)=\{\pi∈G: \pi (C)=C\}\) be the stabilizer of \(C\) in \(G\), the permutations in \(G\) that fix \(C\).

To illustrate these concepts before applying them, refer back to Figure 15.2. Using that information, we can determine that \(fix_C⁡(r_2)=\{C_1,C_{10},C_{11},C_{16}\}\). Determining the stabilizer of a coloring requires finding the rows of the table in which it appears. Thus, \(stab_{D8}⁡(C_7)=\{ι,h\}\) and \(stab_{D8}⁡(C_{11})=\{ι,r_2,p,n\}\).

Proposition 15.8.

Let a group \(G\) act on a finite set \(\mathcal{C}\). Then for all \(C \in \mathcal{C}\),

\(\displaystyle \sum_{C' \in ⟨C⟩} |stab_G(C')| = |G|\).

Proof

Let \(stab_G⁡(C)=\{\pi_1,…,\pi_k\}\) and \(T(C,C′)=\{\pi∈G:\pi^∗(C)=C′\}\). (Note that \(T(C,C)=stab_G⁡(C)\).) Take \(\pi∈T(C,C′)\). Then \(\pi \circ \pi_1 ∈T(C,C′)\) for \(1≤i≤k\). Furthermore, if \(\pi \circ \pi_i = \pi \circ \pi_j\), then \(\pi^{-1} \circ \pi \circ \pi_i = \pi^{-1} \circ \pi \circ \pi_j\). Thus \(\pi_i = \pi_j\) and \(i=j\). If \(\pi'∈T(C,C′)\), then \(\pi^{−1} \circ \pi′∈T(C,C)\). Thus, \(\pi−1 \circ \pi′=\pi_i\) for some \(i\), and hence \(\pi′= \pi \circ \pi_i\). Therefore \(T(C,C′)=\{\pi \circ \pi_1,…,\pi \circ \pi_k\}\). Additionally, we observe that \(T(C′,C)=\{\pi^{-1}:\pi∈T(C,C′)\}\). Now for all \(C′∈⟨C⟩\),

\(|stab_G⁡(C′)|=|T(C′,C′)|=|T(C′,C)|=|T(C,C′)|=|T(C,C)|=|stab_G⁡(C)|\).

Therefore,

\(\displaystyle \sum_{C' \in ⟨C⟩} |stab_G(C')| = \sum_{C' \in ⟨C⟩} |T(C,C')|\).

Now notice that each element of \(G\) appears in \(T(C,C′)\) for precisely one \(C′∈⟨C⟩\), and the proposition follows.

With Proposition 15.8 established, we are now prepared for Burnside's lemma.

Lemma 15.9. Burnside's Lemma.

Let a group \(G\) act on a finite set \(\mathcal{C}\). If \(N\) is the number of equivalence classes of \(\mathcal{C}\) induced by this action, then

\(N = \dfrac{1}{|G|} \displaystyle \sum_{\pi \in G} |fix_{\mathcal{C}}(\pi)|\).

Before we proceed to the proof, note that the calculation in Burnside's lemma for the example of 2-coloring the vertices of a square is exactly the calculation we performed at the end of Section 15.1.

Proof

Let \(X=\{(\pi,C) \in G \times \mathcal{C}: \pi (C)=C\}\). Notice that \(\sum_{\pi \in G} |fix_C⁡(\pi )|=|X|\), since each term in the sum counts how many ordered pairs of \(X\) have \(\pi\) in their first coordinate. Similarly, \(\sum_{C \in \mathcal{C}}|stab_G⁡(C)|=|X|\), with each term of this sum counting how many ordered pairs of \(X\) have \(C\) as their second coordinate. Thus, \(\sum_{C \in \mathcal{C}} |fix_C⁡(\pi)|=\sum_{C \in \mathcal{C}} |stab_G⁡(C)|\). Now note that the latter sum may be rewritten as

\(\displaystyle \sum_{equivalence \\ classes ⟨C⟩} (\sum_{C' \in ⟨C⟩} |stab_G(C')|)\).

By Proposition 15.8, the inner sum is \(|G|\). Therefore, the total sum is \(N \cdot |G|\), so solving for \(N\) gives the desired equation.

Burnside's lemma helpfully validates the computations we did in the previous section. However, what if instead of a square we were working with a hexagon and instead of two colors we allowed four? Then there would be \(4^6=4096\) different colorings and the dihedral group of the hexagon has 12 elements. Assembling the analogue of Figure 15.2 in this situation would be a nightmare! This is where the genius of Pólya's approach comes into play, as we see in the next section.