Section 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 \(\cgC\text{,}\) let \(\sim\) be the equivalence relation induced by this action. (As before, the action of \(\pi\in G\) on \(\cgC\) will be denoted \(\pi^*\text{.}\)) Denote the equivalence class containing \(C\in \cgC\) by \(\langle C\rangle\). For \(\pi\in G\text{,}\) let \(\fix_\cgC(\pi)=\{C\in \cgC\colon \pi^*(C) = C\}\text{,}\) the set of colorings fixed by \(\pi\text{.}\) For \(C\in\cgC\text{,}\) let \(\stab_G(C)=\{\pi\in G\colon \pi(C) = C\}\) be the stabilizer of \(C\) in \(G\text{,}\) the permutations in \(G\) that fix \(C\text{.}\)
To illustrate these concepts before applying them, refer back to
Figure 15.2. Using that information, we can determine that
\(\fix_\cgC(r_2) = \{C_1,C_{10},C_{11},C_{16}\}\text{.}\) Determining the stabilizer of a coloring requires finding the rows of the table in which it appears. Thus,
\(\stab_{D_8}(C_7) = \{\iota,h\}\) and
\(\stab_{D_8}(C_{11}) = \{\iota,r_2,p,n\}\text{.}\)
Proposition 15.8.
Let a group \(G\) act on a finite set \(\cgC\text{.}\) Then for all \(C\in \cgC\text{,}\)
\begin{equation*}
\sum_{C'\in\langle C\rangle} |\stab_G(C')| = |G|.
\end{equation*}
Proof.
Let \(\stab_G(C) = \{\pi_1,\dots,\pi_k\}\) and \(T(C,C') = \{\pi\in G\colon \pi^*(C) = C'\}\text{.}\) (Note that \(T(C,C) = \stab_G(C)\text{.}\)) Take \(\pi\in T(C,C')\text{.}\) Then \(\pi\circ \pi_i\in T(C,C')\) for \(1\leq i\leq k\text{.}\) Furthermore, if \(\pi\circ \pi_i = \pi\circ \pi_j\text{,}\) then \(\pi^{-1}\circ\pi\circ \pi_i=\pi^{-1}\circ\pi\circ \pi_j\text{.}\) Thus \(\pi_i=\pi_j\) and \(i=j\text{.}\) If \(\pi'\in T(C,C')\text{,}\) then \(\pi\inv\circ \pi'\in T(C,C)\text{.}\) Thus, \(\pi\inv\circ\pi' = \pi_i\) for some \(i\text{,}\) and hence \(\pi' = \pi\circ \pi_i\text{.}\) Therefore \(T(C,C') = \{\pi\circ\pi_1,\dots,\pi\circ\pi_k\}\text{.}\) Additionally, we observe that \(T(C',C) = \{\pi\inv\colon \pi\in T(C,C')\}\text{.}\) Now for all \(C'\in\langle C\rangle\text{,}\)
\begin{equation*}
|\stab_G(C')|=|T(C',C')|=|T(C',C)| =
|T(C,C')| = |T(C,C)| = |\stab_G(C)|.
\end{equation*}
Therefore,
\begin{equation*}
\sum_{C'\in\langle C\rangle}|\stab_G(C')| =
\sum_{C'\in\langle C\rangle} |T(C,C')|.
\end{equation*}
Now notice that each element of \(G\) appears in \(T(C,C')\) for precisely one \(C'\in\langle C\rangle\text{,}\) and the proposition follows.
Lemma 15.9. Burnside’s Lemma.
Let a group \(G\) act on a finite set \(\cgC\text{.}\) If \(N\) is the number of equivalence classes of \(\cgC\) induced by this action, then
\begin{equation*}
N = \frac{1}{|G|} \sum_{\pi\in G} |\fix_\cgC(\pi)|.
\end{equation*}
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 \cgC\colon \pi(C) = C\}\text{.}\) Notice that \(\sum_{\pi \in G} |\fix_\cgC(\pi)| = |X|\text{,}\) since each term in the sum counts how many ordered pairs of \(X\) have \(\pi\) in their first coordinate. Similarly, \(\sum_{C\in \cgC} |\stab_G(C)| = |X|\text{,}\) with each term of this sum counting how many ordered pairs of \(X\) have \(C\) as their second coordinate. Thus, \(\sum_{\pi \in G} |\fix_\cgC(\pi)|=\sum_{C\in \cgC} |\stab_G(C)|\text{.}\) Now note that the latter sum may be rewritten as
\begin{equation*}
\sum_{\substack{\text{equivalence} \\\text{classes } \langle
C\rangle} }\left( \sum_{C'\in\langle C\rangle}
|\stab_G(C')|\right).
\end{equation*}
By
Proposition 15.8, the inner sum is
\(|G|\text{.}\) Therefore, the total sum is
\(N\cdot |G|\text{,}\) 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.
You have attempted
of
activities on this page.