Permutation Groups

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<j < k}$ . 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}$

Damek Davis' Blog

Tag: Permutation Groups