proving the famous theorems related to sylow subgroups
This semester I’m taking a course in Group Theory and Galois Theory at UFMG. This post will be about the famous Sylow theorems, and I plan on making a follow-up post about the fundamental theorem of finite abelian groups.
Let \(G\) be a finite group of order \(n\), and let \(\nu_p(n)\) denote the largest power of \(p\) that divides \(n\), where \(p\) is a prime. Any subgroup \(H \leq G\) of \(G\) with order \(\nu_p(n)\) is called a Sylow \(p\)-subgroup. We’ll show that such groups exists for all primes \(p\), and then proceed to prove some interesting properties related to them.
We’ll need two basic results from number theory in order to prove the Sylow Theorems.
Theorem (Legendre’s Formula): If \(n\) is a natural number and \(p\) is a prime, then
\[\nu_p(n!) = \sum_{k \geq 1}\Big\lfloor\frac{n}{p^k}\Big\rfloor\]Proof: The proof of this result becomes much easier when we get some intuitive feeling for what \(\nu_p(n!)\) represents. This quantity is precisely the exponent of \(p\) in the prime factorization of the input \(n!\), but since \(n!\) is a product of numbers and \(p\) is prime, this implies that if \(p\) divides \(n!\), then it must divide one of terms in the factorial, i.e., \(p\) must divide a number that is lesser than or equal to \(n\). This means that there is a multiple of \(p\) that is at most \(n\), and conversely any number \(m \leq n\) that is a multiple of \(p\) contributes with at least one factor of \(p\) in the prime factorization of \(n!\). Thus, the number of multiples of \(p\) is a lower bound on \(\nu_p(n!)\), since each contributes with at least one factor of \(p\). However, after factoring \(p\) from each of these, there might still be multiples of \(p\) left, namely those that are multiples of \(p^2\), and so we can again factor \(p\) out of each of these. We can repeat this for each \(p^k\) ultil \(p^k > n\), i.e., until \(k > \lfloor\log_p(n)\rfloor\), and at this point there will be no factors of \(p\) left in \(n!\).
Now lets make this precise. Let \(n = qp + r\), where \(q,r\) are non-negative integers such that \(0 \leq r < p\), and note that
\[\frac{n}{p} = q + \frac{r}{p}\]and since \(r/p < 1\), it follows that
\[\Big\lfloor\frac{n}{p}\Big\rfloor = q\]This means that \(\lfloor\frac{n}{p}\rfloor\) is precisely the number of multiples of \(p\) that are lesser than or equal to \(n\), and also note that \(q > 0\) iff \(p \leq n\). Now consider the following inductive procedure:
After doing this, we’ll have factored out
\[\sum_{k=1}^{\lfloor\log_p(n)\rfloor}\Big\lfloor\frac{n}{p^k}\Big\rfloor = \sum_{k \geq 1}\Big\lfloor\frac{n}{p^k}\Big\rfloor\]factors of \(p\) from \(n!\), showing that
\[\nu_p(n!) \geq \sum_{k \geq 1}\Big\lfloor\frac{n}{p^k}\Big\rfloor\]On the other hand, by the arguments made before, any factor of \(p\) in \(n!\) must come from a multiple of \(p\) that is at most \(n\), but by construction the previous procedure factors out all possible factors of \(p\) from each of these multiples, hence the previous quantity is also an upper bound on \(\nu_p(n!)\), which proves the desired result.
\[\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\blacksquare\]We can now use this fact to prove an important Lemma.
Lemma: If \(p\) is a prime and \(n\) is a non-negative integer, then \(p\) does not divide
\[{n \choose p^{\nu_p(n)}}\]Proof: Let \(\alpha = \nu_p(n)\), then
\[{n \choose p^{\alpha}} = \frac{n!}{(p^{\alpha})!(n-p^{\alpha})!}\]The idea now is to show that \(p^{\nu_p(n!)}\) appears in this denominator. By Legendre’s formula, we have
\[\nu_p(p^{\alpha}!) = \sum_{k\geq 1}\Big\lfloor\frac{p^{\alpha}}{p^k}\Big\rfloor\quad\text{and}\quad \nu_p((n-p^{\alpha})!) = \sum_{k\geq 1}\Big\lfloor\frac{n-p^{\alpha}}{p^k}\Big\rfloor\]Now note that if \(a,b\) are non-negative integers, then the exponent of \(p\) in the prime factorization of \(ab\) will be the sum of the exponents of \(p\) in the factorizations of \(a\) and \(b\), i.e., \(\nu_p(ab) = \nu_p(a) + \nu_p(b)\). This implies that
\[\nu_p((p^{\alpha})!(n-p^{\alpha})!) = \sum_{k\geq 1} \Big\lfloor\frac{p^{\alpha}}{p^k}\Big\rfloor + \Big\lfloor\frac{n-p^{\alpha}}{p^k}\Big\rfloor\\\]Now fix \(k \geq 1\) and note that
\[n = \Big\lfloor\frac{n}{p^k}\Big\rfloor p^k + r\]where \(0 \leq r < p^k\) and \(\Big\lfloor\frac{n}{p^k}\Big\rfloor\) are unique, on the other hand
\[\begin{split} n &= (n-p^{\alpha}) + p^{\alpha}\\ &= (\Big\lfloor\frac{n-p^{\alpha}}{p^k}\Big\rfloor p^k + r') + (\Big\lfloor\frac{p^{\alpha}}{p^k}\Big\rfloor p^k + r'')\\ &= (\Big\lfloor\frac{n-p^{\alpha}}{p^k}\Big\rfloor + \Big\lfloor\frac{p^{\alpha}}{p^k}\Big\rfloor)p^k + (r'+r'')\\ \Rightarrow \Big\lfloor\frac{n}{p^k}\Big\rfloor p^k + r &= (\Big\lfloor\frac{n-p^{\alpha}}{p^k}\Big\rfloor + \Big\lfloor\frac{p^{\alpha}}{p^k}\Big\rfloor)p^k + (r'+r'') \end{split}\]and since \(0 \leq r',r'' < p^k\), the uniqueness of the euclidean division implies that \(r = r' + r''\) and
\[\Big\lfloor\frac{n}{p^k}\Big\rfloor = \Big\lfloor\frac{n-p^{\alpha}}{p^k}\Big\rfloor + \Big\lfloor\frac{p^{\alpha}}{p^k}\Big\rfloor\]for all \(k \geq 1\), hence
\[\nu_p(n!) = \nu_p((p^{\alpha})!(n-p^{\alpha})!)\]implying that the largest exponent of p in the factorization \(n!\) already appears in \((p^{\alpha})!(n-p^{\alpha})!\), and so \(p\) does not divide \({n \choose p^{\alpha}}\).
\[\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\blacksquare\]Theorem (First Sylow theorem): If \(G\) is a finite group of order \(n\), and \(p\) be a prime, then there exists a Sylow \(p\)-subgroup of \(G\).
Proof:
Let \(\nu_p(n) = \alpha\), and consider \(F = \{ X \subseteq G:\vert X\vert = p^\alpha \}\) as the set of all subsets of \(G\) with cardinality precisely \(p^\alpha\), and note that the cardinality of \(F\) is given by
\[{n \choose p^\alpha}.\]We observe that \(G\) acts on \(F\) via right multiplication
\[g \in G,X \in F:Xg = \{xg:x \in X\}\]The orbits form a partition of \(F\), and since by the previous Lemma we know that \(p\) does not divide \(\vert F\vert\), it follows that there must be some orbit \(GX\) s.t. \(p\) does not divide \(\vert GX\vert\). Let \(H = G_X\) denote the stabilizer of \(X\) w.r.t. \(G\), and this subgroup will be our candidate for a Sylow \(p\)-subgroup of \(G\). By the Orbit-Stabilizer theorem we have
\[\vert G\vert = \vert GX\vert \vert G_X\vert.\]Since by definition \(p^\alpha\) divides \(\vert G\vert\) and since \(p\) does note divide \(\vert GX\vert\), it follows that \(p^\alpha\) divides \(\vert H\vert\), hence \(p^\alpha \leq \vert H\vert\). Now in order to prove the upper bound, we observe that \(H\) acts on \(X\) via right multiplication since \(H \leq G\), and if \(x \in X\), the the stabilizer of \(x\) w.r.t. to \(H\) is
\[H_x = \{g \in H:xg = x\} = \{1\},\]since both \(x,g \in G\), hence again by the Orbit-Stabilizer theorem we have
\[\vert H\vert = \vert Hx\vert \vert H_x\vert = \vert Hx\vert\]however note that \(X\) is partitioned by the orbits \(Hx\), hence \(\vert Hx\vert \leq \vert X\vert = p^\alpha\), thus
\[\vert H\vert = \vert Hx\vert \leq p^\alpha\]implying that \(\vert H\vert = p^\alpha\), as desired.
\[\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\blacksquare\]Theorem (Second Sylow theorem): If \(G\) is a finite group of order \(n\), and \(p\) be a prime, then if \(P,Q\) are Sylow \(p\)-subgroups, then \(P\) and \(Q\) are conjugate, i.e., there exists some \(g \in G\) such that \(Q = P^g = \{gxg^{-1}\vert x \in P\}\).
Proof: Again let \(\nu_p(n) = \alpha\), and let \(P^G = \{P^g\vert g \in G\}\) be the orbit of \(P\) w.r.t. the action of \(G\) via conjugation on the set of all of its subgroups. The Orbit-Stabilizer theorem gives us
\[\vert G \vert = \vert P^G \vert \vert N_G(P) \vert,\]where \(N_G(P)\) is the normalizer of \(P\) in \(G\), and since \(P \leq N_G(P)\), it follows that \(p^\alpha\) divides \(\vert N_G(P) \vert\), implying that \(p\) does not divide \(\vert P^G \vert\). On the other hand, \(Q\) acts on \(P^G\) via conjugation, thus if \(C_1,...,C_r\) are the orbits of this action, again by the Ortbit-Stabilizer theorem w.r.t. \(Q\) we get that \(\vert C_i \vert = p^{a_i}\), for some \(a_i \geq 0\). But since these orbits partition \(P^G\) and \(p\) does not divide \(\vert P^G \vert\), we must have some orbit \(C_i = \{K\}\) with size one, with \(K \in P^G\). By definition, this means that \(Q \leq N_G(K)\), and thus \(KQ\) is a subgroup of \(G\), with order given by
\[\vert KQ \vert = \frac{\vert K \vert \vert Q \vert}{\vert K \cap Q \vert} = p^\alpha,\]where the last equality follows since \(p^\alpha\) is the largest power of \(p\) that divides \(n\), and since \(KQ\) is a subgroup, i.e., \(K \cap Q = K = Q\), which concludes the proof.
\[\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\blacksquare\]Theorem (Third Sylow theorem): The number of Sylow \(p\)-groups of a finite group is congruent to \(1\) modulo \(p\).
Proof: Let \(P\) be a \(p\)-Sylow subgroup, thus by the previous theorem we know that \(P^G\) is the set of all \(p\)-Sylow subgroups, hence we need to show that \(\vert P^G\vert \equiv 1 \mod p\) . Note that \(P\) acts on \(P^G\) by conjugation, and that \(\{P\}\) is an orbit of such action, since \((P^1)^x = P\) for all \(x \in P\). Now assume that there is some \(\{R\}\) that is also an orbit of size \(1\) in this action, thus \(R^x = R\) for any \(x \in P\), implying that \(P \leq N_G(R)\), i.e., \(P\) normalizes \(R\). We’ve seen in the previous proof that this means that \(PR\) is a subgroup of \(G\), but since they are both \(p\)-Sylow subgroups, this implies that \(P = R\). Hence there is only one orbit of size one in the action of \(P\) on \(P^G\), and since the size of the orbits must divide the order of \(P\), this implies that all other orbits have size equal to some positive power of \(p\). Now since these same orbits partition \(P^G\), we get that \(\vert P^G\vert = 1 + pk\), where \(k \in \mathbb{N}\), hence \(\vert P^G\vert \equiv 1 \mod p\), as desired.
\[\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\blacksquare\]There are some some results in mathematics that are really important and yet have quite boring and laborius proofs that don’t highligh some specially interesting idea, but this is certainly not the case with the Sylow Theorems. The results in and of themselves are extremely important – e.g. one of the many proofs of fundamental theorem of algebra requires the first theorem – however the techniques used to prove them are to me their most interesting aspect. The idea of looking at the action of a subgroup on the orbits of another is something that in retrospect seems like a rather straighforward idea, but is something that I doubt I would have come up with by myself, and I’m quite glad that I’ve added this technique to my “toolbox”.