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<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}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s