# Strong Induction Proofs of Cauchy’s Theorem and Sylow’s First Theorem

Here are three really fun little proofs of some of the strongest results in group theory, all of which use very similar methods (strong induction and the class equation) in subtly different ways. They require a little bit of background (only some of which I’ve provided), and you should not expect to grasp it with a quick read-through. I encourage you to read through slowly and carefully, making sure you understand each step of the proofs. I promise it will feel rewarding once you’re done!

# Background

These proofs mostly rely on the Class Equation. I’ll spend a little bit of time showing where it comes from. (You can skip this section if you already know or don’t care where it comes from.)

Partition Equation: Suppose G acts on X. Then the orbits of this action partition X. That is, the orbits of any two elements either share all their elements or none of them, and every element in X is in some orbit. So |X| = ∑|orb(x)|, where the sum is taken over representatives from each orbit.

Orbit Stabilizer Theorem: For any x in X, |orb(x)||stab(x)| = |G|. Here stab(x) refers to the subset of G that fixes x (“stabilizes” it) under the group action. So stab(x) = {g in G : g•x = x}.

Stabilizers are Subgroups: The stabilizer of any x in X is a subgroup of G.

Now we look at the special case of G acting on itself by conjugation. I.e. we define g • x = gxg-1. The orbit of any element x is its conjugacy class Cl(x), and stab(x) is x’s centralizer C(x). So the partition equation for the conjugacy action is |G| = ∑|Cl(x)|, where the sum is taken over representatives of conjugacy classes. And the Orbit Stabilizer Theorem becomes |Cl(x)|⋅|C(x)| = |G|.

Cl(x) = {gxg-1 for all g ∈ G}
C(x) = {g in G such that gx = xg}

You can easily show that for any central element in G (that is, for any element that commutes with every other element in G), its conjugacy class just contains itself. This means that |Z(G)| terms in this sum are equal to 1. So we can rewrite our equation, taking this into account. This gives us the Class Equation.

Class Equation: |G| = |Z(G)| + ∑|Cl(x)|, where the sum is taken over non-central representatives of conjugacy classes.

• Z(G) is a subgroup of G, so |Z(G)| ≥ 1.
• Since the terms in the sum are by definition sizes of conjugacy classes of non-central elements, none of them have size 1. That is, |Cl(x)| > 1 for every non-central x.
• All terms divide |G|. This follows for Z(G) by Lagrange’s theorem (because it’s a subgroup). And it must be true for each |Cl(x)| by the Orbit-Stabilizer Theorem.

That’s all we need! We’re ready to prove Cauchy’s Theorem and Sylow’s First Theorem!

# Proof of Cauchy’s Theorem

Cauchy’s theorem: G has a subgroup of size p for every prime p that divides |G|.

Part 1: First we show that Cauchy’s theorem holds for all abelian groups. This can be proven by strong induction. The base case is |G| = p, which trivially has a subgroup of size p (itself). Now we take a look at any larger group G such that p divides |G|. The strong inductive hypothesis is that Cauchy’s theorem holds for all abelian groups of size less than |G|.

Now, take any non-identity element g in G. Let H = <g>.

• Case 1: Suppose p divides |H|. Then g|H|/p is an element of order p.
• Case 2: Suppose p doesn’t divide |H|. Then p must divide |G/H| (since |G| = |H|⋅|G/H|). Since G is an abelian group, G/H is also an abelian group. And since we chose g to be non-identity, |H| > 1, so |G/H| < |G|. Thus by the inductive hypothesis, G/H contains an element xH of order p. But this implies that |x| is a multiple of p. After all, xH is order p, and (xH)|x| = x|x|H = eH = H. So x|x|/p is an element of order p. Done!

Now that we’ve proven Cauchy’s theorem for all abelian groups, we go on to prove it for all groups.

Part 2: We use strong induction again. The base case is |G| = p, which is trivial. Now, suppose G is a group such that |G| is divisible by prime p. The strong induction hypothesis is that Cauchy’s theorem holds for all groups of size less than |G|.

Let’s examine the Class Equation: |G| = |Z(G)| + ∑|Cl(x)|.

• Case 1: Suppose that for some x, |Cl(x)| is not divisible by p. Then for this x, |C(x)| must be divisible by p (since |Cl(x)||C(x)| = |G|). Since centralizers are subgroups, C(x) is a subgroup with size divisible by p. Furthermore, since |Cl(x)| > 1, |C(x)| < |G|. So by the induction hypothesis, C(x) has a subgroup of size p.
• Case 2: For all x, |Cl(x)| is divisible by p. But so is |G|. So |Z(G)| must be divisible by p as well. But Z(G) is abelian, so it must have a subgroup of size p (by Part 1).

And we’re done!!

With this result in hand, we can go even deeper and prove Sylow’s First Theorem. This one is slightly more involved, so take a breather if you need one…

… And now let’s dive into it!

# Proof of Sylow’s First Theorem

Here’s Sylow’s First Theorem: For every prime power in the factorization of |G|, there is a subgroup of that size. In other words, if G is a finite group such that pn divides |G| for some prime p, then G has a subgroup of order pn.

Again, we proceed by strong induction. Our base case is |G| = p, which is trivial. Now we look at a larger group G, and assume that the theorem is true for all groups of size less than |G|.

Class Equation: |G| = |Z(G)| + ∑|Cl(x)|.

• Case 1: Suppose at least one of the terms in the sum ∑|Cl(x)| isn’t divisible by p. Then for this x, |C(x)| must be divisible by pn (since |Cl(x)||C(x)| = |G|). Since centralizers are subgroups, we have a subgroup with size divisible by pn. Furthermore, since each |Cl(x)| > 1, |C(x)| < |G|. So by the induction hypothesis, C(x) has a subgroup of size pn.
• Case 2: Each |Cl(x)| is divisible by p, as is |G|. So |Z(G)| must be divisible by p. So by Cauchy, Z(G) has an element of order p, say g. Define N = <g>. N is normal, since it’s in the center. So G/N is a group. |G/N| = |G|/|N| = |G|/p, so by induction, G/N has a subgroup H of size pn-1. Now, consider the canonical homomorphism φ: G → G/N defined by φ(g) = gN. It turns out that φ-1(H), the inverse image of H, is a subgroup of G with size pn, just what we were looking for!
• Why is |φ-1(H)| = pn? Well, each element of G/N is a coset, and all cosets have the same size, namely |N|. This means that |N| elements are mapped to any given coset by φ. H is a subset of G/N, so it contains |H| cosets, each of which is mapped to by |N| elements. Since cosets are disjoint, there is no overlap. So φ-1(H) = |N|⋅|H| = p⋅pn-1 = pn.

(Proofs can be found in Judson’s Abstract Algebra)