Feeds:
Posts

Meditation on the Sylow theorems I

As an undergraduate the proofs I saw of the Sylow theorems seemed very complicated and I was totally unable to remember them. The goal of this post is to explain proofs of the Sylow theorems which I am actually able to remember, several of which use our old friend

The $p$-group fixed point theorem (PGFPT): If $P$ is a finite $p$-group and $X$ is a finite set on which $P$ acts, then the subset $X^P$ of fixed points satisfies $|X^P| \equiv |X| \bmod p$. In particular, if $|X| \not \equiv 0 \bmod p$ then this action has at least one fixed point.

There will be some occasional historical notes taken from Waterhouse’s The Early Proofs of Sylow’s Theorem.

A quick note on the definition of a Sylow subgroup

A Sylow $p$-subgroup of a finite group $G$ can be equivalently defined as either a $p$-subgroup of index coprime to $|G|$ (that is, if $|G| = p^n k$ where $\gcd(p, k) = 1$, then $|P| = p^n$) or a $p$-subgroup which is maximal with respect to inclusion. The equivalence of these two definitions requires the Sylow theorems, but we’ll want to discuss such subgroups before proving them, and for the purposes of this post it will be most convenient to adopt the first definition.

So for the rest of this post, a Sylow $p$-subgroup is a $p$-subgroup of index coprime to $p$, and we’ll refer to $p$-subgroups maximal with respect to inclusion as maximal $p$-subgroups before we prove that the two are equivalent.

Warmup: Cauchy’s theorem

We’ll start off by giving some proofs of Cauchy’s theorem. One of the proofs of Sylow I later needs it as a lemma, and some of the proofs we give here will generalize to proofs of Sylow I. First we quote the proof using the PGFPT in full from the above blog post, as Proof 1.

Cauchy’s theorem: Let $G$ be a finite group. Suppose $p$ is a prime dividing $|G|$. Then $G$ has an element of order $p$.

Proof 1 (PGFPT). $\mathbb{Z}/p\mathbb{Z}$ acts by cyclic shifts on the set

$\{ (g_1, g_2, ... g_p) \in G^p : g_1 g_2 ... g_p = 1 \} \setminus \{ (1, 1, ... 1) \in G^p \}$

since if $g_1 g_2 ... g_p = 1$ then $g_p (g_1 g_2 ... g_p) g_p^{-1} = 1$. This set has cardinality $|G|^{p-1} - 1$, which is not divisible by $p$, hence $\mathbb{Z}/p\mathbb{Z}$ has a fixed point, which is precisely a nontrivial element $g \in G$ such that $g^p = 1$. $\Box$

This proof is almost disgustingly short. By contrast, according to Waterhouse, Cauchy’s original proof runs nine pages (!) and works as follows.

First Cauchy explicitly constructs Sylow $p$-subgroups of the symmetric group $S_n$. This can be done by recursively partitioning $\{ 1, 2, \dots n \}$ into $\lfloor \frac{n}{p} \rfloor$ blocks of size $p$, considering the subgroup generated by $p$-cycles cyclically permuting each block, then partitioning the set of blocks itself into $\lfloor \frac{n}{p^2} \rfloor$ blocks-of-blocks of size $p$, cyclically permuting these, and so forth. This subgroup has size

$\displaystyle p^{ \sum_{k \ge 1} \left\lfloor \frac{n}{p^k} \right\rfloor }$

and the exponent is Legendre’s formula for the largest power $\nu_p(n!)$ of $p$ dividing $|S_n|$. It follows that this is a Sylow $p$-subgroup.

Second, Cauchy proves a special case of the following lemma, namely the special case that $H = S_n$. This lemma doesn’t appear to have a standard name, so we’ll name it

Cauchy’s $p$-group lemma: Let $G$ be a subgroup of a finite group $H$ such that $H$ has a Sylow $p$-subgroup $P$. If $p \mid |G|$, then $G$ has an element of order $p$.

Proof. We’ll prove the contrapositive: if $G$ doesn’t contain an element of order $p$, then $p$ does not divide $|G|$.

Consider the left action of $G$ on the set of cosets $H/P$. By grouping the cosets into $G$-orbits and using the orbit-stabilizer theorem we have

$\displaystyle |H/P| = \sum_{[h] \in G \backslash H/P} \frac{|G|}{|\text{Stab}_G(hP)|}$

where $G \backslash H/P$ is the collection of double cosets and the stabilizer of a coset is

$\displaystyle \text{Stab}_G(hP) = \{ g \in G : ghP = hP \} = \{ g \in G : h^{-1} gh \in P \} = h^{-1} G h \cap P$

and in particular it has order dividing $|P|$, hence a power of $p$.

If $G$ has no element of order $p$, then since any nontrivial subgroup of $P$ contains an element of order $p$, these stabilizers are all trivial, so we get that

$\displaystyle |H/P| = |G| |G \backslash H/P|$

and in particular that $|G|$ divides $|H/P|$. Since $P$ is a Sylow $p$-subgroup, $|H/P|$ isn’t divisible by $p$, and hence neither is $|G|$. $\Box$

Call a collection of finite groups cofinal if every finite group embeds into at least one of them.

Corollary: To prove Cauchy’s theorem for all finite groups, it suffices to find a cofinal collection of finite groups which have Sylow $p$-subgroups.

We can now complete Cauchy’s proof of Cauchy’s theorem.

Proof 2 (symmetric groups). The symmetric groups $\{ S_n \}$ are cofinal (this is exactly Cayley’s theorem) and have Sylow $p$-subgroups. $\Box$

But we don’t have to use the symmetric groups!

Proof 3 (general linear groups). Since the symmetric groups $S_n$ embed into the general linear groups $GL_n(\mathbb{F}_p)$, the latter are also cofinal, and we can also exhibit Sylow $p$-subgroups for them: the unipotent subgroup $U_n(\mathbb{F}_p)$ of upper triangular matrices with $1$s on the diagonal is Sylow. This follows from the standard calculation of the order

$\displaystyle |GL_n(\mathbb{F}_p)| = p^{ {n \choose 2} } (p-1)^n [n]_p!$

where $[n]_p!$ is the $p$-factorial. $\Box$

Here’s a fourth proof that doesn’t use Cauchy’s lemma and doesn’t require the clever construction of the first proof; Waterhouse says it’s used by Rotman.

Proof 4 (class equation). We induct on the order of $G$. First we observe that Cauchy’s theorem is straightforwardly true for finite abelian groups by using the Chinese remainder theorem to write a finite abelian group as a direct sum of finite abelian $p$-groups. (And then, to spell it out very explicitly, Lagrange’s theorem implies that any nontrivial element of a finite $p$-group has $p$-power order, so some power of that element has order $p$.)

Next, given a finite group $G$ such that $p \mid |G|$ we consider the class equation

$\displaystyle |G| = |Z(G)| + \sum_i \frac{|G|}{|C_G(g_i)|}$

where the sum runs over non-central conjugacy classes. If $p \mid |Z(G)|$ then we’re done by reduction to the abelian case. Otherwise, $p$ doesn’t divide $|Z(G)|$ but does divide $|G|$, so by taking both sides $\bmod p$ we conclude that there is some $g_i$ such that the centralizer $C_G(g_i)$ has index in $G$ coprime to $p$, and hence $p \mid |C_G(g_i)|$. Since $g_i$ is a non-central conjugacy class $C_G(g_i)$ has order strictly less than $|G|$ so has an element of order $p$ by the inductive hypothesis. $\Box$

Sylow I

With very little additional effort the above proof of Cauchy’s $p$-group lemma actually proves the following stronger result; Waterhouse attributes this argument, again in the special case that $H = S_n$, to Frobenius. It also doesn’t appear to have a standard name, so we’ll call it

Frobenius’ $p$-group lemma: Let $G$ be a subgroup of a finite group $H$ such that $H$ has a Sylow $p$-subgroup $P$. Then $G$ also has a Sylow $p$-subgroup, given by its intersection with some conjugate of $P$.

Proof. Consider as before the sum

$\displaystyle |H/P| = \sum_{[h] \in G \backslash H/P} \frac{|G|}{|h^{-1} G h \cap P|}$

obtained by considering the orbits of the action of $G$ on $H/P$. Since $p$ doesn’t divide $|H/P|$, at least one term on the RHS is also not divisible by $p$, so there exists some $h$ such that $h^{-1} G h \cap P$ has index coprime to $p$ and hence is a Sylow $p$-subgroup of $h^{-1} G h$; conjugating, we get that the intersection of $h P h^{-1}$ with $G$ is a Sylow $p$-subgroup of $G$ as desired. $\Box$

Corollary: To prove that Sylow subgroups exist for all finite groups, it suffices to prove that they exist for a cofinal collection of finite groups.

Now we can give two different proofs of Sylow I, as follows.

Sylow I: Every finite group $G$ has a Sylow $p$-subgroup.

(Note that with our definitions if $\gcd(p, |G|) = 1$ then this subgroup is just the trivial group.)

Proof 1 (symmetric groups). It suffices to prove the existence of Sylow subgroups for the symmetric groups $S_n$, which was done above. $\Box$

Proof 2 (general linear groups). It suffices to prove the existence of Sylow $p$-subgroups for $GL_n(\mathbb{F}_p)$, which was done above. Running the argument gives that every finite $p$-group is a subgroup of $U_n(\mathbb{F}_p)$ for some $n$, which gives an independent proof that finite $p$-groups are nilpotent. $\Box$

Proof 2 is the first proof of Sylow I given by Serre in his Finite Groups: An Introduction.

I heard a rumor years ago that these proofs existed but didn’t see them; glad that’s finally settled.

The next proof of Sylow I we’ll present is the one that I saw as an undergraduate, in Artin’s Algebra if memory serves. According to Wikipedia it’s due to Wielandt. Serre attributes it to “Miller-Wielandt” and it’s the second proof he gives.

Proof 3 (action on subsets). Write $|G| = p^k m$ where $\gcd(p, m) = 1$ and consider the action of $G$ by left multiplication on the set ${G \choose p^k}$ of $p^k$-element subsets of $G$. We’ll show that there exists a stabilizer subgroup of size $p^k$.

(I found this construction very bizarre and unmotivated as an undergraduate. I like it better now, I guess, but I’m still a little mystified.)

Key observation: An element $g \in G$ stabilizes a subset $S \subseteq G$ iff $S$ consists of cosets of the cyclic subgroup $\langle g \rangle$ generated by $g$; in particular a necessary condition is that its order must divide the size of $S$.

This means that the action of $G$ on ${G \choose p^k}$ has the property that all stabilizers must be $p$-groups (just like the action of $G$ on $H/P$ we used above). As before, decomposing this action into orbits gives

$\displaystyle {|G| \choose p^k} = \sum_{[S]} \frac{|G|}{|\text{Stab}(S)|}$

where the sum runs over a set of orbit representatives.

Lemma: $\displaystyle {p^k m \choose p^k} \ \equiv m \bmod p$.

Proof. This is a special case of Lucas’ theorem, which we proved using the PGFPT previously. $\Box$

It follows that ${|G| \choose p^k} \equiv m \bmod p$ is not divisible by $p$, so there exists some subset $S$ such that $\frac{|G|}{|\text{Stab}(S)|}$ is also not divisible by $p$. But since $|\text{Stab}(S)|$ is a power of $p$ this is only possible if $|\text{Stab}(S)| = p^k$. This stabilizer is a Sylow $p$-subgroup as desired. $\Box$

This proof is tantalizingly similar to the proof of Frobenius’ lemma above; in both cases the key is to write down an action of $G$ on a set of size relatively prime to $p$ but such that all stabilizers must be $p$-groups. But I’m not yet sure how to relate them.

We’re not done with proofs of Sylow I! The next proof is due to Frobenius; Waterhouse stresses that its early use of quotients crucially highlighted the importance of working with abstract groups rather than just groups of substitutions as was standard in early group theory. It generalizes the class equation proof of Cauchy’s theorem above.

Proof 4 (class equation). We again induct on the order of $|G|$ and start by observing that Sylow subgroups clearly exist for finite abelian groups, for example by the structure theorem. We can also use the Chinese remainder theorem.

Now, suppose that $p \mid |G|$. If $p$ also divides the order $|Z(G)|$ of the center, then $Z(G)$ contains a (central, abelian, nontrivial) Sylow $p$-subgroup $A$, which we can quotient by. Then $G/A$, by the inductive hypothesis, also contains a Sylow $p$-subgroup, and the preimage of this subgroup is a Sylow $p$-subgroup of $G$.

If $p \nmid |Z(G)|$, then again we inspect the class equation

$\displaystyle |G| = |Z(G)| + \sum_i \frac{|G|}{|C_G(g_i)|}$

where again the sum runs over non-central conjugacy classes. Since $p \mid |G|$ we conclude that there is some conjugacy class $[g_i]$ such that $p \nmid \frac{|G|}{|C_G(g_i)|}$, hence such that $|G|$ and $|C_G(g_i)|$ have the same $p$-adic valuation. By the inductive hypothesis, $C_G(g_i)$ contains a Sylow $p$-subgroup, which is then (by virtue of having the appropriate order) also a Sylow $p$-subgroup of $G$. $\Box$

This proof is the first one we’ve seen that provides a halfway reasonable algorithm for finding Sylow subgroups, which is lovely (the first three are more or less just raw existence proofs): pass to the quotient by central $p$-groups until you can’t anymore, then search for conjugacy classes whose centralizers have index relatively prime to $p$ and pass to the centralizers until you can’t anymore, then repeat.

We give one final proof. According to Waterhouse, this one is essentially Sylow’s original proof, and it naturally proves an apparently-slightly-stronger result, interpolating between Cauchy’s theorem and Sylow I. It also provides a (different) algorithm for finding Sylow subgroups.

Sylow I+: Every finite group $G$ contains a subgroup of prime power order $p^k$ whenever $p^k \mid |G|$. These subgroups can be constructed inductively by starting from an element of order $p$ and then finding an element of $p$-power order normalizing the previous subgroup.

(Note that this result is equivalent to Sylow I as usually stated once we know that finite $p$-groups admit composition series in which each quotient is $C_p$, which is not hard to prove by induction once we know that finite $p$-groups have nontrivial center, which in turn we proved previously using the PGFPT. The below proof actually gives an independent proof of the existence of such a composition series, and hence an independent proof that finite $p$-groups are nilpotent.)

Proof 5 (normalizers + PGFPT). We induct on $k$. The base case $k = 1$ is Cauchy’s theorem, which we proved above (four times!).

Now suppose we’ve found a subgroup $P$ of order $p^k$, and we’d like to see if we can find a subgroup of order $p^{k+1}$. Consider the action of $P$ by left multiplication on the cosets $G/P$. By the PGFPT the number of fixed points of this action satisfies

$\displaystyle |(G/P)^P| \equiv |G/P| \bmod p$.

On the other hand, the fixed points of this action are precisely the cosets $gP$ such that $PgP = gP$, or equivalently such that $g^{-1} P g = P$. So they are naturally in bijection with the quotient $N_G(P)/P$ of the normalizer

$\displaystyle N_G(P) = \{ g \in G : gPg^{-1} = P \}$

of $P$. So the PGFPT tells us:

Lemma: If $P$ is a $p$-subgroup of a finite group $G$, then $|G/P| \equiv |N_G(P)/P| \bmod p$.

If $p^{k+1} \mid |G|$, or equivalently if $P$ is not a Sylow $p$-subgroup, then $|G/P| \equiv 0 \bmod p$ and hence $|N_G(P)/P| \equiv 0 \bmod p$, so by Cauchy’s theorem it follows that $N_G(P)/P$ has an element $g$ of order $p$. The preimage of the cyclic subgroup $\langle g \rangle$ in $N_G(P)$ is then a $p$-subgroup of order $p^{k+1}$ as desired; more specifically it’s a subgroup $P'$ given by some extension

$\displaystyle 1 \to P \to P' \to C_p \to 1$

where $g$ generates the copy of $C_p$. So we’ve found our bigger $p$-subgroup. $\Box$

This proof gives us an algorithm for finding Sylow subgroups by starting with elements of order $p$ and repeatedly finding elements of order $p^k$ in the normalizer, and note that it also gives us a way to prove that a $p$-subgroup is Sylow without explicitly checking that its index is coprime to $p$:

Corollary (normalizer criterion): A $p$-subgroup $P$ of a finite group $G$ is a Sylow $p$-subgroup iff the quotient $N_G(P)/P$ contains no elements of order $p$.

It has another corollary we haven’t quite gotten around to proving yet:

Corollary (Sylow = maximal): Sylow $p$-subgroups are precisely the maximal $p$-subgroups.

(Before it could have been the case that there were $p$-subgroups maximal with respect to inclusion but without index coprime to $p$.)

These are all the proofs of Sylow I that I know or could track down. After having gone through all of them I think I like proof 4 (class equation) and proof 5 (normalizers) the best. Proof 3 (action on subsets) is really too opaque and too specialized; you only learn from it that Sylow subgroups exist and practically nothing else, whereas proof 4 and proof 5 both teach you more about them, including how to find them. I’m sort of amazed it took me over 10 years after I first ran into the Sylow theorems to finally see a version of Sylow’s original proof, and that when I did, I liked it so much better than the first proof I had seen.

Sylow II and III

These will be short.

Sylow II: Let $G$ be a finite group and $P$ be any Sylow $p$-subgroup. Every $p$-subgroup $K$ of $G$ is contained in a conjugate of $P$. In particular, taking $K$ to be another Sylow $p$-subgroup, every pair of Sylow $p$-subgroups is conjugate.

Proof 1. Immediate corollary of Frobenius’ lemma. $\Box$

Proof 2. Consider the action of $K$ on $G/P$. By hypothesis, $|G/P| \not \equiv 0 \bmod p$, so by the PGFPT,

$\displaystyle |(G/P)^K| \equiv |G/P| \not \equiv 0 \bmod p$.

A fixed point of the action of $K$ on $G/P$ is precisely a coset $gP$ such that $KgP = gP$, or equivalently such that $g^{-1} K g \subseteq P$, so there must be at least one such $g$ conjugating $K$ into $P$ as desired. $\Box$

Corollary (Sylow = maximal, again): Sylow $p$-subgroups are precisely the maximal $p$-subgroups.

(We’ve now proved this result in three different ways!)

Sylow III: Let $G$ be a finite group and $P$ be any Sylow $p$-subgroup. The number $n_p$ of Sylow $p$-subgroups of $G$ satisfies $n_p = |G/N_G(P)|$ and $n_p \equiv 1 \bmod p$; in particular, $n_p \mid |G|$.

Proof. Since the Sylow $p$-subgroups are conjugate, the set of Sylow $p$-subgroups is just the set of conjugates of $P$. $G$ acts transitively on this set by conjugation with stabilizer $N_G(P)$, so by orbit-stabilizer it has size $n_p = |G/N_G(P)|$ and in particular has size dividing $|G|$. We now give two proofs of the all-important congruence $n_p \equiv 1 \bmod p$.

Subproof 1 (action of $P$ on $G/P$). In Proof 5 (normalizers + PGFPT) of Sylow I above we showed that

$\displaystyle |G/P| \equiv |N_G(P)/P| \not \equiv 0 \bmod p$

and dividing both sides by $|N_G(P)/P| \bmod p$ gives the desired result.

Subproof 2 (action of $P$ on $G/N_G(P)$). This proof has the benefit of explaining what this congruence “means.” $N_G(P)/P$ can’t be divisible by $p$, so the only elements of $p$-power order that normalize $P$ are the elements of $P$, and the same must be true for any other Sylow. This implies that if we restrict the conjugation action of $G$ on the Sylows to $P$, then $P$ fixes only itself, so by the PGFPT

$\displaystyle |(G/N_G(P))^P| = 1 \equiv |G/N_G(P)| = n_p \bmod p$

and the conclusion follows. $\Box$

5 Responses

1. […] « Meditation on the Sylow theorems I […]

2. That’s a nice exposition, just wanted to point out couple of things.

In the proof of Cauchy via the class equation you write “Cauchy’s theorem is straightforwardly true for finite abelian groups by using the Chinese remainder theorem to write a finite abelian group as a direct sum of finite abelian $p$-groups. (And then, to spell it out very explicitly, Lagrange’s theorem implies that any nontrivial element of a finite $p$-group has $p$-power order, so some power of that element has order $p$.).” If I read this correctly (correct me if I don’t) then this assumes that you already know that finite abelian groups are product of finite cyclic groups. However that not necessary since we can prove it directly by induction on the group order. Indeed, let $G$ be a finite abelian group with $p\mid|G|$ and pick random $1\ne g\in G$. If $p\mid\text{ord}(g)$ then we’re done, otherwise we pass to $G/\langle g\rangle$ which contains an element of order $p$ by the induction hypothesis, its pre-image in $G$ then has order divisible by $p$.

In fact, using this we can prove Sylow I+ using the class equation (and without using the structure theorem for finite abelian groups). The case $p\nmid|Z(G)|$ is done same as above. Now let $p\mid|Z(G)|$. If $G$ is abelian then it contains element $g$ of order $p$ and $G/\langle g\rangle$ has a subgroup of order $p^{k-1}$ by the induction hypothesis and we take the preimage. If not then let $\ell=v_p(Z(G))>0$. If $k\le\ell$ then $Z(G)$ has a subgroup of order $p^k$ by the induction hypothesis. If $k>\ell$ then $Z(G)$ has a $p$-Sylow subgroup $A$ by the induction hypothesis and $G/A$ has a subgroup of order $p^{k-\ell}$ by the induction hypothesis and we take the pre-image again.

Finally, in the subproof 1 of Sylow III there should be twice $|N_G(P)/P|$ instead of $|G/N_G(P)|$.

• Thanks for the detailed comment! Re: Cauchy’s theorem, the argument I suggest doesn’t need the structure theorem for finite abelian groups; we only need to know that a finite abelian group of order $n$ is a module over $\mathbb{Z}/n$, and then we can decompose into Sylow $p$-subgroups using the Chinese remainder theorem. But your inductive argument is even more elementary!

That’s a nice proof of Sylow I+ as well. And yes, thanks for pointing out the typo.

3. Very nice! I loved the proof hidden in everything that p-groups are nilpotent using GL_n.

Two typos: In proof 1 of Cauchy’s theorem, you write floor of n^2/p, when you mean floor of n/p^2. Also in subproof 1 of Sylow III, both instances of G/N_G(P) should be N_G(P)/P.

• Thanks! Fixed.