# Parker’s Lemma is Equivalent to Burnside’s Lemma

You can view a pdf of this entry here.

Let ${G}$ be a finite group that acts on a finite set, ${X}$. Given elements ${g \in G}$ and ${x \in X}$, we introduce the cycle notation, ${(xgx\cdots g^{k-1}x)}$ to denote that ${g^kx = x}$, but ${g^jx \neq x}$ for all ${0. We say that ${(xgx\cdots g^{k-1}x)}$ is a ${k}$-cycle in ${g}$. Conceptually, this is a natural construction: the action of ${G}$ on ${X}$ induces a map, ${G \rightarrow S_{X}}$, of ${G}$ into the symmetric group of ${X}$. This allows us to decompose the image of any element ${g \in G}$ into disjoint cycles.

Let the expression ${c_{k}(g)}$ denote the number of ${k}$-cycles of ${g}$. Let ${X^{(k,G)}}$ be the set of all ${k}$-cycles contained in elements of ${G}$. In particular, for ${k = 1}$, ${X^{(1, G)} = \{(x) : x\in X\}}$ because ${1}$-cycles are fixed points of elements of ${G}$, and ${1\in G}$ fixes every element of ${X}$. Note that if ${X^{(k, G)}}$ is nonempty, then ${G}$ acts on ${X^{(k, G)}}$ by conjugation: if ${c = (xhx \cdots h^{k-1}x)}$, then ${g\cdot c = (gx ghx \cdots gh^{k-1}x)}$ is a cycle in ${ghg^{-1}}$, so ${g\cdot c \in X^{(k, G)}}$. Parker’s lemma is the following:

Lemma 1 (Parker’s Lemma) The number of orbits of ${G}$ on ${X^{(k,G)}}$ is

$\displaystyle \begin{array}{rcl} \left|X^{(k, G)}/G\right| &=& \frac{1}{|G|} \sum_{g \in G} kc_k(g). \end{array}$

At first glance, this lemma appears to be a straightforward application of Burnside’s orbit counting lemma:

$\displaystyle \begin{array}{rcl} \left| X/G\right| &=& \frac{1}{|G|} \sum_{g \in G} \text{Fix}_{X}(g) \end{array}$

In fact, the case ${k = 1}$ is Burnside’s lemma: the number, ${c_1(g)}$, is the number of ${1}$-cycles of ${g}$, i.e. ${\text{Fix}_{X}(g)}$. However, for ${k \geq 2}$, if ${X^{(k, G)}}$ is nonempty, then ${kc_{k}(1) = 0 \neq \text{Fix}_{X^{(k, G)}}(1) = \left|X^{(k, G)}\right|}$. Thus, we cannot simply equate terms: ${\text{Fix}_{X^{(k, G)}}(g) \neq kc_k(g)}$, in general. The difficulties described above suggest that Parker’s lemma is a stronger statement than Burnside’s lemma. In fact, I am unaware of any proof in the literature that deduces Parker’s lemma as a consequence of Burnside’s Lemma. The aim of this post is to establish Parker’s lemma as a simple consequence of Burnside’s lemma.

Proof: We assume that ${X^{(k, G)}}$ is nonempty, otherwise the result is trivial. We note that by Burnside’s lemma

$\displaystyle \begin{array}{rcl} \left|X^{(k, G)}/G\right| &=& \frac{1}{|G|} \sum_{g \in G} \text{Fix}_{X^{(k, G)}} (g). \end{array}$

Define subsets ${Z_1, Z_2 \subseteq G\times X^{(k, G)}}$ by

$\displaystyle \begin{array}{rcl} Z_1 &=& \{ (g, c) \in G \times X^{(k, G)} : g \cdot c = c \} \\ Z_2 &=& \{ (g, c) \in G \times X^{(k, G)} : c \text{ is a cycle in } g \}. \end{array}$

For each ${c \in X^{(k, G)}}$, choose ${g_c}$ such that ${(g_c, c) \in Z_2}$. Let ${H_c}$ be the pointwise stabilizer of ${c}$. Then ${g_cH_c}$ is the set of elements of ${G}$ that contain ${c}$, and ${\langle g_c\rangle H_c}$ is the stabilizer of ${c}$. Note that ${g_c^i H_c \neq g_c^j H_c}$ for ${0 < i,j \leq k}$, with ${i \neq j}$. Indeed, if ${g_c^i = g_c^j h}$, where ${h \in H_c}$, then ${g_c^{i-j} = h}$ is disjoint from ${c}$, i.e. ${i-j \equiv 0 \mod k}$, which is a contradiction. Thus, because ${g_c^k \in H_c}$, we see that ${\text{Stab}(c) = \langle g_c \rangle H_c = \bigcup_{i = 1}^k g_c^i H_c}$ is a partition of ${\text{Stab}(c)}$. Therefore, ${|\text{Stab}(c)| = k |g_c H_c|}$, and hence

$\displaystyle \begin{array}{rcl} |Z_1| &=& |\bigcup_{c} \text{Stab}(c) \times \{c\}| \\ &=& \sum_{c} k\left| g_c H_c\right| \\ &=& k |Z_2|, \end{array}$

because ${ Z_2 = \bigcup_{c} \left(g_c H_c \times \{c\}\right)}$. Now, we count the order of ${Z_1}$ and ${Z_2}$ by counting points along the fiber of the canonical projection

$\displaystyle \begin{array}{rcl} \pi_G : G \times X^{(k, G)} &\rightarrow& G. \end{array}$

Indeed,

$\displaystyle \begin{array}{rcl} |Z_1| &=& \sum_{g \in G} \left|\pi^{-1}_G (g) \cap Z_1\right| = \sum_{g \in G} \text{Fix}_{X^{(k, G)}}; \\ |Z_2| &=& \sum_{g \in G} \left|\pi^{-1}_G (g) \cap Z_2\right| = \sum_{g \in G} c_k(g). \end{array}$

Thus,

$\displaystyle \begin{array}{rcl} \left|X^{(k, G)}/G\right| &=& \frac{1}{|G|} \sum_{g \in G} \text{Fix}_{X^{(k, G)}} (g) = \frac{|Z_1|}{|G|} = \frac{k|Z_2|}{|G|} = \frac{1}{|G|} \sum_{g \in G} k c_k(g), \end{array}$

as desired.

${\Box}$