Chapter 8

p-Groups and the Sylow Theorems

Mathematics is the tool specially suited for dealing with abstract concepts of any kind. There is no limit to its power in this field.

—Paul Adrien Maurice Dirac

Historically, the theory of groups was concerned only with groups of permutations of a set. This point of view is reinforced by Cayley's theorem, which shows that every abstract group can be viewed as a subgroup of a group of permutations. The concept of an abstract group became important because it focuses attention on those aspects of a group of permutations that do not depend on the underlying set. However, this abstract formulation of the theory loses sight of the combinatorial aspects that are more in evidence for groups of permutations. And these counting methods give important information about abstract groups. The best example is Lagrange's theorem, which is based on the fact that a subgroup partitions the group into cosets each having the same number of elements as the subgroup.

In Section 8.2, we derive another such counting theorem, the class equation, from a partition of a finite group and use it, among other things, to deduce many properties of groups of prime power order. Then, in Section 8.3, we present a far-reaching counting method that includes the proof of Lagrange's theorem and the class equation and which, in Section 8.4, we use to prove the Sylow theorems. These beautiful results guarantee the presence of subgroups of prime power order in every finite group and inform us about how many such subgroups there are. 351

8.1 Products and Factors

An important goal of the theory of groups is to prove structure theorems, that is to describe all groups of a certain type in terms of particular constructions of well-known subgroups of that type. For example, in Section 7.2 we showed that every finite abelian group is a finite direct product of cyclic subgroups. We begin this section by describing when a group G is isomorphic to a finite direct product G₁ × G₂ × × G_n of subgroups of G. These direct factors G_i are also images of G, and we gain some insight as to how to describe these images in the second part of this section.

Products of Subgroups

If X and Y are nonempty subsets of a group, define their product as follows:

XY = {xy x X and y Y}.

This is an associative multiplication; indeed if Z is another nonempty subset then

(XY)Z = {xyz x X, y Y and z Z} = X(YZ).

as the reader can verify. Moreover, {1}X = X = X{1} for all nonempty sets X, so the set of all nonempty subsets of G is a monoid with unity {1}. Moreover, the map a {a} is a group embedding (one-to-one homomorphism), so we identify G as a subgroup of this monoid by identifying a = {a} for all a G. Hence, we write X{a} = Xa and {a}X = aX, which agrees with our earlier usage for cosets Ha and conjugates a⁻¹Ha of a subgroup H.

These products are most useful for subgroups. If H and K are subgroups of some group, the product HK is again a subgroup if and only if HK = KH (Lemma 2 §2.8), and this holds if either H G or K G (where K G means K is normal in G). The following result will be used several times in this chapter.

Lemma 1. Modular law. If H, K, and M are subgroups of a group and H ⊆ M then H(K ∩ M) = HK ∩ M.

Proof. The inclusion H(K ∩ M) ⊆ HK ∩ M is clear because H ⊆ M. If x HK ∩ M, say x = hk = m, then k = h⁻¹m K ∩ M, so x = hk H(K ∩ M).

For reference, Theorem 6 §2.8 reads

(*)

The next theorem is an important extension of this which requires only that K G. Recall that the isomorphism theorem for groups asserts that, if α: G → H is a group homomorphism, then ker α G and G/ker α ≅ Gα.

Theorem 1. Second Isomorphism Theorem. Let H and K be subgroups of a group G with K G. Then HK is a subgroup of G, K HK, H ∩ K H, and

Proof. HK is a subgroup by Lemma 2 §2.8, and K HK because K ⊆ HK. Define α: H → HK/K by α(h) = Kh. (Note that Kh is in HK/K because H ⊆ HK.) Then α is a homomorphism, and it is onto because, if x HK = KH, say x = kh, then Kx = K(kh) = (Kk)h = Kh = α(h). Now the theorem follows from the isomorphism theorem because ker (α) = {h H Kh = K} = H ∩ K.

If H and K are both finite subgroups, we saw in Corollary 1 to Theorem 6 §2.8 that whenever H ∩ K = {1}. Here is a useful generalization.

Theorem 2. Let H and K be finite subgroups of a group. Then

Proof. Write N = H ∩ K for convenience. Let Nk₁, . . ., Nk_m be the distinct cosets of N in K, so that is the index of N in K.

Claim. HK = Hk₁∪ Hk₂ ∪ ∪Hk_m, a disjoint union.

Proof. If k K, then k = nk_i for some n N. If h H then hk = (hn)k_i Hk_i, which proves that HK ⊆Hk₁ ∪ ∪ Hk_n. Thus, HK = Hk₁ ∪ ∪ Hk_m. To see that this is a disjoint union, suppose that Hk_i ∩ Hk_j is nonempty. Then Hk_i = Hk_j, so Hence, Nk_i = Nk_j, so i = j. This proves the Claim.

Finally, the Claim gives , as required.

We now give two generalizations of Theorem 6 §2.8—see (*) above; the first drops the condition that H ∩ K = {1}.

Theorem 3. If H G and K G then

Proof. Write N = H ∩ K for convenience, and define

 by α(hk) = (Nh, Nk).

Then α is well defined because hk = h₁k₁ means Hence, hN = h₁N, so Nh = Nh₁ because N G. Similarly, Nk = Nk₁.

Claim. α is a homomorphism.

Proof. Write x = hk and y = h₁k₁ in HK = KH, and write kh₁ = h₂k₂ in HK. Then xy = hh₂ k₂k₁ so α(xy) = (Nh Nh₂, Nk₂ Nk₁). On the other hand, we have α(x)α(y) = (Nh Nh₁, Nk Nk₁), so we must prove that Nh Nh₂ = Nh Nh₁ and Nk₂ Nk₁ = Nk Nk₁, equivalently (since G/N is a group) Nh₂ = Nh₁ and Nk₂ = Nk. But we have kh₁ = h₂k₂, so

because K G, and

because H G.

Hence, Nh₂ = Nh₁ and Nk₂ = Nk, which proves the Claim.

With the Claim, α is an onto homomorphism, so we are done by the isomorphism theorem because ker α = {hk Nh = N and Nk = N} = N.

Our second generalization of Theorem 6 §2.8—see (*) above; is to extend it to more than two factors. We require the following result, interesting in itself.

Lemma 2. The following are equivalent for subgroups G₁, G₂, . . ., G_n of a group:

Proof. Given (1), if g₁g₂ g_n = 1 then g_n (G₁G₂ . . . G_n−1) ∩ G_n = {1}, so g_n = 1 and g₁g₂ g_n−1 = 1. Now repeat the procedure to obtain g_n−1 = 1. Continue to prove (1) ⇒ (2). The proof that (2) ⇒ (1) is left to the reader.

Call subgroups G₁, G₂, . . ., G_n unconnected if the conditions in Lemma 2 are satisfied. Using this notion, we now give a useful characterization of when a group is isomorphic to a direct product of finitely many subgroups.

Theorem 4. Let G be a group and assume that G = G₁G₂ G_n where the G_i are subgroups. Then the following conditions are equivalent:

In this case G ≅ G₁ × G₂ × × G_n, and each g G is uniquely represented as a product g = g₁g₂ g_n, where g_i G_i for each i.

Proof. (1) ⇒ (2). Given (1), let g_i G_i, g_j G_j and i ≠ j. Assume i < j, so that G_i ∩ G_j ⊆ (G₁G₂ . . . G_j−1) ∩ G_j = {1}. If we write then a G_i because Similarly a G_j, so a G_i ∩ G_j = {1}. Hence a = 1, so g_ig_j = g_jg_i, as required.

(2) ⇒ (1). Let b G_k, a G; we want a⁻¹ba G_k. If a = a₁a₂ a_n, a_i G_i then, since b commutes with each of by (2), we have

But and so commutes with each of a_k+1, . . ., a_n. It follows that , so G_k G. This proves (1).

(3) (4) and (4) ⇒ (2). Both (3) and (4) imply that the G_i are unconnected.

(2) ⇒ (4). Choose b_k G_k ∩ (G₁ G_k−1G_k+1 G_n) and write b_k = a₁ a_k−1 · a_k+1 a_n with a_i G_i for each i. Since b_k commutes with these a_i, this gives , so b_k = 1 by (2) and Lemma 2. This proves (4).

Now define θ: G₁ × G₂ × × G_n → G by θ(g₁, g₂, . . ., g_n) = g₁g₂ g_n. This is onto because G = G₁G₂ G_n, and it is a homomorphism because the G_i commute elementwise. (Note, this does not require that the G_i are abelian.) As θ is one-to-one (because the G_i are unconnected), θ is an isomorphism, and so G ≅ G₁ × G₂ × × G_n. Finally, if g = a₁a₂ a_n = b₁b₂ b_n, a_i G_i, b_i G_i; we must show a_i = b_i for all i. First . Since b₂ commutes with by (2), we get . Continue to get . Hence, each by Lemma 2, proving the last sentence of the Theorem.

The Correspondence Theorem

If α: G → H is an onto group homomorphism, the group H = α(G) is called a homomorphic image of G, or simply an image of G. Thus, the image α(G) enjoys any property of G that is preserved by homomorphisms, for example, being abelian or cyclic. The image is a simplified version of the group and so is easier to study. The idea is to learn about the group G by investigating its homomorphic images.

The isomorphism theorem (Theorem 4 §2.10) provides a fundamental tool for investigating a homomorphic image α(G) of a group G. It asserts that α(G) is isomorphic to a factor group of G, indeed that α(G) ≅ G/K, where K denotes the kernel of α. On the other hand, if K is any normal subgroup of G, the factor group G/K is a homomorphic image of G via the coset homomorphism G → G/K given by g Kg. Thus, studying the images α(G) of G is the same as studying the factors G/K of G. The factors of G are very closely connected to G itself and we now focus on these factors and how to use them to study the group G.

Because many properties of G can be described in terms of the subgroups of G, we need to be able to obtain information about these subgroups from knowledge of the subgroups of a factor group G/K. The next theorem provides a method of doing this. It gives a very useful correspondence between the set of subgroups of G that contain K and the set of all subgroups of G/K. Moreover, the correspondence is such that, if we can determine all the subgroups in one of these sets, we can easily compute the subgroups in the other set.

To show how this correspondence works let K G, and consider the set of subgroups H of G such that K ⊆ H. For any such H, define

H/K = {Kh h H}.

Lemma 3. If K ⊆ H ⊆ G are groups and K G, then

Proof. (1) This is because H/K is the image of H under the coset map G → G/K.

(2) Clearly H ⊆ H₁ implies H/K ⊆ H₁/K. Conversely, assume H/K ⊆ H₁/K, and let h H. Then Kh H/K = H₁/K, say Kh = Kh₁ for some h₁ H₁. As K ⊆ H₁ this gives h Kh₁ ⊆ H₁h₁ ⊆ H₁, so H⊆ H₁.

Theorem 5. Correspondence Theorem. If K G are groups, define a map

Θ: {H K ⊆ H ⊆ G, H is a subgroup is a subgroup}

by Θ(H) = H/K. Let H, H₁ and H₂ be subgroups of G containing K. Then:

Proof. (1) The map Θ is one-to-one by Lemma 2, and it is onto by (2).

(2) Given a subgroup define as in (2). Then H is a subgroup of G and K ⊆ H. Moreover because implies that g H, whence Kg H/K. Conversely, if Kg H/K then Kg = Kh for some h H so, as K ⊆ H, g Kh ⊆ Hh ⊆ H. But then by the definition of H, and we have shown that Hence as required.

(3) This restates Lemma 2.

(4) Assume H/K H₁/K. To show H H₁, let h H and h₁ H₁. Then

Hence for some h′ H, so because K ⊆ H. As h H was arbitrary, this shows that H H₁.

Conversely, let H H₁. Then (Kh₁)⁻¹Kh for all h₁ H₁, h H, because As h H was arbitrary, this shows that (Kg)⁻¹(H/K)Kg ⊆ H/K. Hence H/K H₁/K, as required.

(5) and (6) These are left as Exercises 9 and 10.

If K G, the bijection H ↔ H/K in Theorem 5 pairs all subgroups H ⊇ K of G with all subgroups H/K of G/K. Not only is this correspondence a bijection, it also pairs normal subgroups with normal subgroups by (4) and preserves inclusion by (3). This last fact means that the lattice diagram of all subgroups of G/K has the same form as the lattice diagram of all subgroups of G that contain K. In particular, the bijection pairs G with G/K, and it pairs K with K/K = {K}—the trivial subgroup of G/K. This is illustrated in the following two examples.

Example 1. Let , where o(a) = 12, and let and Draw the lattice diagram of all subgroups of G, and use the correspondence theorem to obtain the lattice of all subgroups of G/K and G/K₁.

Solution. The subgroups of G are given by the divisors of 12, and the subgroup lattice for G appears on the left in the diagram (see Example 14 §2.4). The subgroups of G/K are thus determined (using the correspondence theorem) by the subgroups and K of G that contain K. Thus the lattice diagram for G/K shown in the center diagram can be “read off” from the diagram for G.

Similarly and K₁ are the only subgroups containing K₁, and they give the subgroup lattice for G/K₁ on the right.

Example 2. Consider the octic group G = D₄ = {1, a, a², a³, b, ba, ba², ba³}, where o(a) = 4, o(b) = 2 and aba = b. If K = {1, a²}, determine all the subgroups H of G such that K ⊆ H ⊆ G.

Solution. By Example 4 §2.9, K = Z(G), and G/K = {K, Ka, Kb, Kba} ≅ K₄, the Klein group. Hence, the subgroups of G/K are {K}, G/K, and

The subgroup lattice diagram of G/K is shown at the left in the diagram.

The correspondence theorem ensures that, for each i, there is a unique subgroup H_i of G such that K ⊆ H_i and Explicitly, (2) of Theorem 5 gives

The correspondence theorem also shows that these are the only subgroups H such that K ⊆ H ⊆ G, and that the lattice of such subgroups (in the right diagram) has the same form as the subgroup lattice of G/K. Furthermore, the fact that , and are normal in (the abelian group) G/K guarantees that H₁, H₂, and H₃ are normal in G. (Of course this also follows because they are of index 2 in G.)

An important special case of the correspondence theorem describes when a factor group is simple. If K G, the group G/K is simple if and only if the only normal subgroups are the trivial subgroup K/K = {K} and the whole group G/K. Hence, the correspondence theorem shows that the only normal subgroups H such that K ⊆ H ⊆ G are H = K and H = G. A normal subgroup K ≠ G with this latter property is called a maximal normal subgroup of G. This discussion is summarized in

Theorem 6. A normal subgroup K G is a maximal normal subgroup if and only if G/K is simple.

Every finite group G ≠ {1} has maximal normal subgroups—choose any proper normal subgroup (possibly {1}) of maximal order. Hence, G has finite simple factor groups by Theorem 2, which shows that finite simple groups are quite common. In fact they serve as “ building blocks” by which we can study the structure of finite groups in general. We return to this topic in Chapter 9.

The correspondence theorem describes the subgroups of a factor group G/K, where K G. We now turn to the images of G/K. Of course they are all images of G, and so have the form G/H for some H G. They are described next by an important consequence of the isomorphism theorem that will be needed later.

Theorem 7. Third Isomorphism Theorem. Let K ⊆ H ⊆ G be groups, where K G and H G. Then H/K G/K and

.

Proof. Define α: G/K → G/H by α(Kg) = Hg for all g in G. This is well defined because Kg = Kg₁ implies whence Hg = Hg₁. With this it is easy to verify that α is an onto homomorphism, and ker (α) = {Kg Hg = H} = H/K. Hence, the isomorphism theorem (Theorem 4 §2.10) completes the proof.

Our final example provides a good illustration of how the second and third isomorphism theorems are used. A group G is called a metacyclic group if a normal subgroup K G exists such that both K and G/K are cyclic. Every cyclic group is metacyclic (take K = {1}) as is D_n (take K to be the cyclic subgroup of index 2). Thus, D_n is metacyclic but not cyclic.

Example 3. Show that every subgroup and every image of a metacyclic group is again metacyclic.

Solution. Let G be metacyclic, say K and G/K are both cyclic where K G.

If H is a subgroup of G then H ∩ K H, and H ∩ K is cyclic (being a subgroup of the cyclic group K). On the other hand, H/(H ∩ K) ≅ HK/K by the second isomorphism theorem, and HK/K is cyclic (it is a subgroup of G/K). It follows that H/(H ∩ K) is cyclic, whence H is metacyclic.

Now let G/N be any image of G, where N G. Then NK G by Theorem 1, so NK/N G/N. Moreover, NK/N is cyclic because NK/N ≅ K/(N ∩ K) is an image of the cyclic group K. On the other hand, (G/N)/(NK/N) ≅ G/NK is cyclic because G/NK ≅ (G/K)/(NK/K) is an image of the cyclic group G/K. This means that G/N is metacyclic.

Exercises 8.1

8.2 Cauchy's Theorem

If p is a prime and G is a group of order pⁿ, every element of G has order a power of p by Lagrange's theorem. The converse is also true. If every element of a finite group G has p-power order, then |G| = pⁿ for some n ≥ 0. The proof of this result requires several theorems that are important in themselves and reveal many other properties of groups of p-power order.

Recall that two subgroups H and K of a group G are called conjugate in G if K = gHg⁻¹ for some g G. This relation is an equivalence on the set of all subgroups of G, and the analogous equivalence on the elements of G is an important tool in this section. Thus, two elements a and b of a group G are said to be conjugate in G if b = gag⁻¹ for some g G. This is an equivalence on G and the equivalence class of a G is denoted

classa = {x G x is conjugate to a} = {gag⁻¹ g G},

and is called the conjugacy class of a.

Hence the conjugacy classes partition a group G. Clearly, class1 = {1} in any group and, more generally, classa = {a} if and only if a Z(G). Also, if a and b are conjugate, then o(a) = o(b) because gag⁻¹ is the image of a under an inner automorphism of G. Hence, all elements in a conjugacy class have the same order.

Example 1. Partition D₃ into conjugacy classes.

Solution. Let D₃ = {1, a, a², b, ba, ba²}, where o(a) = 3, o(b) = 2, and aba = b. We have class1 = {1}. As a and a² are the only elements of order 3, we have classa ⊆ {a, a²}. But a² = bab⁻¹, so classa = {a, a²}. Similarly, classb = {b, ba, ba²} because aba⁻¹ = ba and a²ba⁻² = ba².

It can be shown (Exercise 15) that two permutations in S_n are conjugate if and only if they have the same cycle structure; that is, when factored into disjoint cycles they have the same number of cycles of each length.

Example 2. The conjugacy classes of S₄ are

If K is a normal subgroup of G, then gKg⁻¹ = K for all g G, and so K contains the conjugacy class of each of its elements. Conversely, any subgroup that is a union of conjugacy classes must be normal (Exercise 5). This proves

Theorem 1. If H is a subgroup of a group G, then H G if and only if H is a union of conjugacy classes.

If D₃ = {1, a, a², b, ba, ba²}, as in Example 1, Theorem 1 shows that any normal subgroup K of D₃ must be a union of the conjugacy classes {1}, {a, a²}, and {b, ba, ba²}. Because 1 K and |K| divides |D₃| = 6, the only normal subgroups of D₃ are {1}, {1, a, a²}, and D₃. Similarly, Example 2 gives Example 3 (Exercise 17).

Example 3. The normal subgroups of S₄ are {ε}, A₄, S₄, and

K = {ε, (12)(34), (13)(24), (14)(23)}.

The relationship between conjugacy classes and normality is even closer than that shown in Theorem 1. If X ⊆ G is a nonempty subset, write

N(X) = N_G(X) = {g G gXg⁻¹ = X}.

This is a subgroup of G for every X (Exercise 12), called the normalizer of X in G. We write N(X) = N_G(X) if the group G must be emphasized, and we abbreviate N({a}) = N(a) for a G. Note that N(a) = {g G ga = ag}. For this reason, N(a) is often called the centralizer of a in G. The normalizer of a subgroup has the following properties which explain the name.

Lemma 1. Let H be a subgroup of a group G.

Proof. Let H K and k K. Then kHk⁻¹ = H, so k N(H). Thus, K ⊆ N(H) proving (2). If we take K = H in (2), we get H ⊆ N(H), whence H N(H).

We can summarize Lemma 1 by saying that N(H) is the largest subgroup of G in which H is normal. In particular, H G if and only if N(H) = G. At the other extreme, it can happen that N(H) = H (consider H = {ε, (12)} in S₃).

Much of the importance of normalizers stems from their connection with conjugation. Recall that |G: H| denotes the index in G of a subgroup H ⊆ G.

Theorem 2. Let G be a finite group.

Proof. We prove (1); (2) is analogous (Exercise 13). Write N(a) = N. The index Since classa = {gag⁻¹ g G}, define a mapping

ϕ: classa → {gN g G}  by ϕ(gag⁻¹) = gN.

It suffices to prove that ϕ is a bijection. Now N = {x G ax = xa}, so we have

gag−1 = hah−1		(h−1g)a = a(h−1g)
		h−1g N
		gN = hN

This shows that ϕ is well defined and one-to-one; as ϕ is onto, this proves (1).

Combining Theorem 2 with the fact that classa = {gag⁻¹ g G} gives

a Z(G) classa = {a} N(a) = G.

In particular, the center Z(G) is the union of all the singleton conjugacy classes. This leads to the following useful theorem.

Theorem 3. The Class Equation. Let G be a finite group and let class a₁, classa₂, . . ., classa_n be the nonsingleton conjugacy classes. Then

Proof. The conjugacy classes partition G, so is the sum of the sizes of these classes. But the number of elements in classa_i is |G: N(a_i)| by Theorem 2, and is the number of singleton classes. The class equation follows.

Example 4. Consider the quaternion group Q = {1, − 1, i, − i, j, − j, k, − k} as in Example 9 §2.8. The conjugacy classes are {1}, { − 1}, {i, − i}, {j, − j}, and {k, − k}. We have N(i) = {1, − 1, i, − i} so that |Q: N(i)| = 2 = |classi|, as in Theorem 2. Because Z(Q) = {1, − 1}, the class equation is apparent.

The class equation is reminiscent of Lagrange's theorem in that it provides arithmetic information about the group. That Lagrange's theorem is useful is beyond doubt; the usefulness of the class equation lies in the fact that each term |G: N(a)| is a divisor of |G| which is not equal to 1 when a ∉ Z(G). This fact is particularly useful when |G| is a prime power as we shall see.

However, before doing so we use the class equation to prove an important theorem about general finite groups—due to A. L. Cauchy. If G is a finite group, the order of each element divides |G| by Lagrange's theorem. The converse is false. For example, |A₄| = 12 but A₄ has no element of order 6. However, a partial converse does hold.

Theorem 4. Cauchy's Theorem. If a prime p divides the order of a finite group G, then G has an element of order p.

Proof. If G is abelian, a (self-contained) proof has already been given (Lemma 1 §7.2). In general, we use induction on |G|. The theorem is easily verified if |G| ≤ 3. If |G| > 3, let classa₁, . . ., classa_n denote the nonsingleton conjugacy classes so that |N(a_i)| < |G|. If p divides |N(a_i)| for any i, the proof is complete by induction. Otherwise, p divides |G: N(a_i)| for each i, and hence p divides |Z(G)| by the class equation. As Z(G) is abelian, Lemma 1 §7.2 completes the proof.

As with many important theorems, the method of proof of Cauchy's theorem is at least as important as the result itself. In Section 8.3, we present a sweeping generalization of the class equation, which yields a wealth of information about finite groups.

p-Groups

We use Cauchy's theorem frequently below. One of the most important applications is to characterize groups of prime power order. If p is a prime, a group G is called a p-group if the order of every element of G is a power of p.

Lemma 2. If G is a finite group and p is a prime, then |G| is a power of p if and only if G is a p-group.

Proof. Assume that o(g) is a power of p for all g G. If |G| is not a power of p, let q divide |G|, where q ≠ p is a prime, Then Cauchy's theorem shows that G has an element of order q, contrary to hypothesis. Hence, |G| is a power of p. The converse follows by Lagrange's theorem.

Thus, Lemma 2 characterizes the finite p-groups. The next result holds for all p-groups, finite or not, and we leave the routine proof as Exercise 21.

Theorem 5. Let K ⊆ G be groups with K G and let p be a prime. Then G is a p-group if and only if both K and G/K are p-groups.

Although infinite p-groups exist (Exercise 23), we focus on the finite case. Theorem 6 is fundamental, and the proof provides a good illustration of how to use the class equation.

Theorem 6. If p a prime and G ≠ {1} is a finite p-group, then Z(G) ≠ {1}.

Proof. Let classa₁, . . ., classa_n denote the nonsingleton conjugacy classes in G. Because N(a_i) ≠ G for each i by Theorem 2, and because |G: N(a_i)| divides |G| for each i, it follows that p divides |G: N(a_i)| for each i. But then p divides |Z(G)| by the class equation; in particular Z(G) ≠ {1}.

Theorem 6 is very useful in the study of p-groups where p is a prime. We give two applications; the first characterizes of all groups of order p².

Theorem 7. If G is a group and |G| = p² where p is a prime, then G is abelian and either or G ≅ C_p × C_p.

Proof. To prove that G is abelian, we show that Z(G) = G. As Z(G) ≠ {1} by Theorem 6, it suffices to show that |Z(G)| = p is impossible. But, if it holds, then G/Z(G) is cyclic (it has order p), which implies that G is abelian by Theorem 2 §2.9, a contradiction. Hence |Z(G)| ≠ p, so Z(G) = G and G is abelian. Now assume that G is not cyclic so that every element g satisfies g^p = 1. Choose a ≠ 1 in G and write Then choose b ∉ H and write Because |K| = p = |H|, we have H ∩ K = {1}, so HK ≅ H × K by Theorem 3 §8.1. Hence |HK| = p² = |G|, so G = HK ≅ H × K ≅ C_p × C_p.

The extension of Theorem 7 to groups of order p³ is false: If p = 2, the nonabelian groups D₄ and Q both have order 2³. More generally, if p is an odd prime, Exercises 30 and 31 give nonabelian groups G₁ and G₂ of order p³ such that g^p = 1 for all g G₁, and G₂ contains an element of order p².

The next result shows that, although a finite p-group need not be abelian, it has an abundance of normal subgroups; in fact, it has one of every possible order. The proof again depends on Theorem 6 and provides a tour de force through the methods we have developed for dealing with finite groups.

Theorem 8. Let G be a finite p -group of order pⁿ. Then there exists a series

G = G₀ ⊃ G₁ ⊃ ⊃ G_n = {1}

of subgroups of G such that G_i G, |G_i| = pⁿ⁻ⁱ, and |G_i/G_i+1| = p for all i.

Proof. The existence of such a series is obvious if n = 1, so we proceed by induction on n. If |G| = pⁿ⁺¹, we have Z(G) ≠ {1} by Theorem 6. By Cauchy's theorem, choose a Z(G) such that o(a) = p, and write Then G_n G and G/G_n has order pⁿ⁻¹ so, by induction, let (G/G_n) ⊃ X₁ ⊃ ⊃ X_n = {G_n} be a series of subgroups of G/G_n such that X_i G/G_n and |X_i/X_i+1| = p for each i. The correspondence theorem (Theorem 5 §8.1) ensures that each X_i has the form X_i = G_i/G_n, where G_i G and Furthermore, X_i ⊃ X_i+1 implies that G_i ⊃ G_i+1, and G_i/G_i+1 ≅ X_i/X_i+1 by the third isomorphism theorem (Theorem 7 §8.1). Hence, G ⊃ G₁ ⊃ ⊃ G_n ⊃ {1} is the required series for G.

Note that Theorem 8 shows that if G is a p-group and n ≥ 1, then every subgroup H ⊆ G is contained in a subgroup M with Such subgroups must be normal as we shall see in the Corollary to Theorem 1 §8.3, so G/M ≅ C_p and M is maximal.

The existence of a series of subgroups such as that in Theorem 8 gives important information about the group. Such series are studied in Chapter 9.

Augustin Louis Cauchy (1789–1857)  Cauchy was certainly one of the great mathematicians, and it is said that he and his contemporary Gauss were the last to know all the mathematics of their time. But, unlike Gauss, Cauchy published profusely (surpassed only by Euler and Cayley), and produced 789 papers on topics as diverse as optics, elasticity, differential equations, mechanics, determinants, permutation groups, and probability. He was the effective founder of the theory of functions of a complex variable. In addition he wrote three classic textbooks on analysis in which he firmly established standards of rigor that are now accepted by all analysts and carry down to today's calculus texts. We owe our modern notions of limit and continuity to him. In algebra, Cauchy is remembered as the first to formulate earlier work with permutations in an abstract way and so to create a formal theory of groups of permutations. This work led Cayley (in 1854) to the modern notion of an abstract group.

Cauchy was born in Paris and, after a stellar career in school, enrolled as an engineer in Napoleon's army. He continued his mathematical research and, at the age of 26, became a professor at the École Polytechnique. He soon established himself as the leading mathematician in France. He also enjoyed teaching, and this pedagogical bent probably accounts for the influence his books had.

Exercises 8.2

8.3 Group Actions

A mathematician, like a painter or a poet, is a maker of patterns.

—Godfrey Harold Hardy

If G is a finite group of order n, Cayley's theorem asserts that there exists a one-to-one group homomorphism G → S_n. The proof proceed as follows. Given a G, we define the multiplication map σ_a: G → G by σ_a(g) = ag for all g G. We can easily verify that σ_a is a bijection and so belongs to the group S_G of all permutations of the set G. The proof is then completed by observing that the map G → S_G given by a σ_a is a one-to-one homomorphism and so embeds G in the permutation group S_G. (Of course, S_G ≅ S_n because |G| = n).

The action of the permutation σ_a: G → G is left multiplication by a. The key observation in this section is that there are sets other than G on which an element of G can act by multiplication. For example, if H is a subgroup of G of index m, let X = {gH g G} denote the set of all left cosets. Then for a G we define

τ_a: X → X by τ_a(g) = a(gH) = agH, for all gH in X.

One verifies that τ_a is a (well defined) bijection for each a G and so τ_a S_X. Moreover, τ_ab = τ_aτ_b because τ_ab(gH) = abgH = a(bgH) = τ_a[τ_b(gH)] for all g. Since this holds for all a and b, the map

ϕ: G → S_X  given by  ϕ(a) = τ_a, for all a G

is a group homomorphism. However, unlike the map in Cayley's theorem, ϕ may have a nontrivial kernel:

ker ϕ	=	{a G agH = gH for all g G}
	=	{a G g−1ag H for all g G}
	=	{a G a gHg−1 for all g G}
	=	gGgHg−1.

This group is important enough to warrant a name.

If H is a subgroup of a group G, the core of H in G, denoted coreH, is defined to be the intersection of all the conjugates of H in G; that is,

coreH = {a G a gHg⁻¹ for all g G} = _gGgHg⁻¹.

Thus, coreH G by the preceding discussion, and coreH ⊆ H because H is a conjugate of itself. Furthermore, coreH is the largest normal subgroup of G that is contained in H. We record this fact for reference, and leave the proof as Exercise 9.

Lemma 1. Let H be a subgroup of a group G.

Our present interest in coreH comes from Theorem 1.

Theorem 1. Extended Cayley Theorem. If H is a subgroup of finite index m in a group G, there is a group homomorphism θ: G → S_m with ker θ = coreH ⊆ H.

Proof. If X = {gH g G}, let ϕ: G → S_X be defined as above. As |X| = m, there is an isomorphism δ: S_X → S_m, so we obtain a homomorphism δϕ: G → S_m, and ker δϕ = ker ϕ = coreH by the preceding discussion. Then θ = δϕ does it.

This is Cayley's theorem when H = {1}. Example 1 illustrates how to use it.

Example 1. If |G| = 36 and G has a subgroup H of order 9, 1⁸⁹ then G is not simple. Indeed, |G: H| = 4 so, by Theorem 1, there is a homomorphism θ: G → S₄, with ker θ ⊆ H. If ker θ = {1}, then G ≅ θ(G), a contradiction as |G| = 36 and |θ(G)| ≤ |S₄| = 24. So ker θ ≠ {1} is normal in G.

In Section 2.8, we showed that any subgroup of index 2 is normal. The next result gives a generalization that is especially useful for finite p -groups.

Corollary. Let p be the smallest prime dividing the order of a finite group G. Then any subgroup of G of index p is normal in G.

Proof. Let |G| = p^kq^mrⁿ , where p< q < r are primes. If |G: H| = p, then |H| = p^k−1q^mrⁿ . By Theorem 1 let θ: G → S_p be a homomorphism with ker θ ⊆ H and write K = ker θ. If , then we have divides |S_p| = p ! and so divides (p − 1) !. But this implies that k₀ = m₀ = n₀ = = 0 because every divisor of (p − 1) ! is less than p. Hence, H = K G.

We give more applications of the extended Cayley theorem later; our present aim is to generalize it. The key to the theorem is the existence of the homomorphism ϕ: G → S_X, where G is a group and X is some set. Because the image ϕ(G) of G is a subgroup of S_X, the natural place to begin is to consider this situation.

Hence suppose that X is a nonempty set and that G is a subgroup of the group S_X of all permutations of X. For x X and σ G, the element σ(x) of X is specified, which amounts to a mapping G × X → X where (σ, x) σ(x). We can now describe an apparently more general situation.

Group Actions

Let G be a group and let X be a nonempty set. A mapping G × X → X, denoted (a, x) a · x, is called an action of G if it satisfies the following conditions.

A1 1 · x = x for all x X.

A2 a · (b · x) = (ab) · x for all x X and for all a, b G.

In this case, G is said to act on X and X is called a G-set.⁹⁰

Hence an action of G on X is nothing more than a multiplication of any element x of X by any element a of G to yield a (uniquely determined) element a · x of X that satisfies axioms A1 and A2. There are many examples of such actions, and Example 2 recaptures the above discussion.

Example 2. If X is any nonempty set and G ⊆ S_X is any group of permutations of X, define σ · x = σ(x) for all x X and σ G. Then axioms A1 and A2 are clearly satisfied; in fact, A2 is the definition of composition of mappings.

Example 3. Let H be a subgroup of a group G. Consider G as a set for the moment and let H act on G by h · x = hx for all x G, h H. This is clearly an action; and H is said to act on G by left multiplication.

Example 4. If G is a group, let G act on itself by a · x = axa⁻¹ for all x G and a G. Then axiom A1 is clear and A2 holds because

a · (b · x) = a(bxb⁻¹)a⁻¹ = (ab)x(ab)⁻¹ = (ab) · x

for x G and a, b G. In this case, G is said to act on itself by conjugation.

Example 5. Let H be a subgroup of a group G and let X = {gH g G} denote the set of left cosets of H in G. If a G and gH X then a · (gH) = agH is well defined (verify) and so is an action of G on X. As we have shown, this action plays an essential role in the derivation of the extended Cayley theorem.

Example 6. If X is any set and G is any group, we define the trivial action by a · x = x for all x X and a G. Clearly, the axioms are satisfied.

Examples 2–6 show that group actions are commonly occurring phenomena, and other examples below underline this conclusion. Lemma 2 isolates two useful properties of group actions that we use repeatedly.

Lemma 2. Let X be a G -set, where G is a group, and let x, y X and a, b G.

Proof. Clearly, (1) follows from (2) and axiom A1. If a · x = b · y, then

(b⁻¹a) · x = b⁻¹ · (a · x) = b⁻¹ · (b · y) = (b⁻¹b) · y = 1 · y = y,

which proves half of (2). The other implication is proved similarly.

We can now give a natural generalization of the extended Cayley theorem. If G is a group, X is a G-set and a G, define

σ_a: X → X  by  σ_a(x) = a · x for all x X.(*)

Then Lemma 2 shows that σ_a is a bijection and so is a member of the group S_X of all permutations of X. Moreover, if a, b G, then axiom A2 gives

σ_ab(x) = (ab) · x = a · (b · x) = σ_a[σ_b(x)] = (σ_aσ_b)(x)

for all x S. Hence, σ_ab = σ_aσ_b so the map θ: G → S_X, defined by θ(a) = σ_a for all a G, is a group homomorphism. This gives parts (1) and (2) of

Theorem 2. Let G be a group, let X be a G-set, and let σ_a be defined as in (*), where a G. Then

Proof. It remains to prove (3). But a ker θ means that is, σ_a(x) = x for all x X. This condition means that a · x = x for all x, as required.

If H is a subgroup of G, the extended Cayley theorem is clearly the special case of Theorem 2 where X = {gH|g G} and the action of G on X is given by a · (gH) = agH for all gH X and a G. In this case ker θ = coreH. In general, if X is a G-set then ker θ G is given by

ker θ = {a G a · x = x for all x X}.

The normal subgroup ker θ is called the fixer of the action. The reason for the name is that ker θ consists of the elements of G that fix every x X. Here an element x X is said to be fixed by a G if a · x = x.

Example 7. Let G be a group and let G act on itself by conjugation: a · x = axa⁻¹ for all x G and a G. Here the bijection σ_a: G → G in Theorem 2 is the inner automorphism of G induced by a. Hence θ(G) = innG, where θ: G → S_G is the homomorphism in Theorem 2, and the fixer is ker θ = {a G a · x = x for all x G} = Z(G) in this case. Thus, Theorem 2 gives G/Z(G) ≅ innG, a result derived earlier (Theorem 5 §2.10).

Orbit Decomposition Theorem

So far, the theory of group actions has been motivated by the urge to generalize the extended Cayley theorem. However, the theory yields an additional bonus: It provides a fundamental, natural generalization of the class equation.

Recall that elements x and y in a group G are called conjugate in G if y = axa⁻¹ for some a G. If we regard G as acting on itself by conjugation, this condition is y = a · x for some a G. This suggests a generalization: If X is a G-set, we define a relation ≡ on X as follows. If x, y X, we write

x ≡ y (modG), if y = a · x for some a G.

One easily verifies that ≡ is an equivalence on X (Exercise 17). Moreover, we may describe the equivalence class [x] of an element x of X in terms of the action: [x] = {y X y ≡ x} = {a · x a G}. This equivalence class is called the orbit of x under G and is denoted

G · x = {a · x a G}.

Hence, if G acts on itself by conjugation, the orbits are just the conjugacy classes. Cosets also occur as orbits.

Example 8. Let H be a subgroup of a group G and let H act on G by left multiplication: h · x = hx for all x G, h H. Then the orbit of x G is the right coset Hx = H · x.

A key step in the derivation of the class equation is the observation that the number of elements in the conjugacy class of x G is just the index in G of the normalizer N(x) of x in G. Surprisingly, if X is any G-set, the size of each orbit is the index of a certain subgroup of G.

Lemma 3. If X is a G -set and x X, write S(x) = {a G a · x = x}. Then

Proof. The proof of (1) is left as Exercise 23. Given x X, write S(x) = S and define a function ϕ: G · x → {gS g G} by ϕ(g · x) = gS. Then

g · x = h · x (h⁻¹g) · x = x h⁻¹g S gS = hS,

so ϕ is well defined and one-to-one. Since ϕ is clearly onto, this proves (2) because

If X is a G-set and x X, the subgroup

S(x) = {a G a · x = x}

is called the stabilizer ⁹¹ of x. If G acts on itself by conjugation the stabilizer of x in G is S(x) = {a G axa⁻¹ = x} = N(x) is the normalizer of x, and the orbit of x is G · x = {gxg⁻¹ g G} = classx. Hence, Lemma 3 gives |classx| = |G: N(x)| in this case, a result proved earlier (Theorem 2 §8.2).

If X is a G-set and x X, the orbit of x is G · x = {a · x a G}. Combining this with Lemma 3 gives equivalent conditions that the orbit is a singleton

G · x = {x} a · x = x, for all a G S(x) = G.(**)

The set of all such elements x is denoted

X_f = {x X a · x = x for all a G}

and is called the fixed subset of X under the action of G. With this we can give the promised generalization of the class equation.

Theorem 3. Orbit Decomposition Theorem. Let a group G act on a finite set X ≠ ∅ and let G · x₁, G · x₂, . . ., G · x_n denote the nonsingleton orbits. Then

Proof. The fixed subset X_f is the union of the singleton orbits by (**). Because the orbits partition X, Now apply Lemma 3.

Theorem 3 becomes the class equation if X = G and G acts on itself by conjugation because the fixed subset is G_f = {x G axa⁻¹ = x for all a G} = Z(G).

In the terminology of Theorem 3 the index |G: S(x_i)| = |G · x_i| is finite because X is a finite set and, if the group G is itself finite, it is a divisor of |G|. This property is particularly important when G is a finite p-group, where p is a prime, because then p divides |G: S(x_i)| for each i. Hence, Theorem 3 shows that p divides |X| − |X_f| in this case, which is important enough to record as Theorem 4.

Theorem 4. Let p be a prime and let G be a finite p-group. If X is a finite G-set, then p divides |X| − |X_f|.

We use this result repeatedly in the next Section. For now we illustrate how to use it by proving an important property of finite p -groups that will recur in Chapter 9.

Theorem 5. Let G be a finite p -group, where p is a prime. If H ≠ G is a subgroup, then N(H) ≠ H.

Proof. Let X = {xH x G} denote the set of left cosets of H in G, and let H act on X by left multiplication: h · (xH) = hxH for all x G and h H. Then p divides |X| = |G: H| and so |X_f| ≠ 1 by Theorem 4. Now

Hence, N(H) ≠ H since otherwise X_f = {H}, contrary to |X_f| ≠ 1.

We conclude this section by sketching J.H. McKay's beautiful proof ⁹² of Cauchy's theorem, which applies Theorem 4 and avoids proving the abelian case separately. If G is a group and p is a prime divisor of |G|, we must find an element of order p in G. McKay's idea is to consider the set of p-tuples with product 1:

X = {(a₁, . . ., a_p) a_i G, a₁a₂ a_p = 1}.

What is needed is a p-tuple (a, a, . . ., a) in X with a ≠ 1. To this end, let the (additive) group act on X by “ cycling” the p-tuples:

, for all

We leave to the reader the task of verifying that this is an action (well defined) and that the fixed subset is X_f = {(a, a, . . ., a) a^p = 1}. Hence, Cauchy's theorem follows if |X_f| ≠ 1, and this in turn holds (by Theorem 4) if p divides |X|. But this latter condition follows because p divides and |X| = |G|^p−1 (indeed, in choosing (a₁, . . ., a_p) in X, the elements a₁, . . ., a_p−1 can be selected arbitrarily from G). This completes a most elegant proof.

Exercises 8.3

8.4 The Sylow Theorems

Lagrange's theorem asserts that the order of each subgroup of a finite group G is a divisor of |G|. The converse is false: A₄ has no subgroup of order 6 even though |A₄| = 12. However, if p^k divides the order of G where p is a prime, then G does have a subgroup of order p^k. This remarkable theorem was first proven in 1872 (for permutation groups) by the Norwegian mathematician Ludwig Sylow and has been ranked with Lagrange's theorem as being among the most important results about finite groups. The version presented here for abstract groups was proven in 1887 by Georg Frobenius, and this proof uses only Cauchy's theorem and the class equation. We give another more modern direct proof using the theory of group actions at the end of this section.

Theorem 1. Let G be a finite group. If p is a prime and p^k divides |G| for some k ≥ 0, then G has a subgroup of order p^k.

Proof. It is clear if k = 0, so assume k ≥ 1. Proceed by induction on |G|. The theorem is clear if |G| = 1, 2, or 3. In general, by the class equation, where classa₁, . . ., classa_n are the nonsingleton conjugacy classes. If p^k divides |N(a_i)| for some i then N(a_i) has a subgroup of order p^k by induction because

So assume that p^k does not divide |N(a_i)| for every i ≥ 1. Because p^k divides for all i, it follows that p divides |G: N(a_i)| for every i. Hence, p divides |Z(G)| by the class equation so, by Cauchy's theorem, choose a Z(G) with o(a) = p. If we write then K G and Moreover, p^k−1 divides because p^k divides Hence, again by induction, G/K has a subgroup H/K with As we are done.

Sylow originally proved Theorem 1 in the special case where p^k is the highest power of the prime p that divides the order of the group.

Corollary. Sylow's First Theorem. If G is a group of order pⁿm, where p is a prime and p does not divide m, then G has a subgroup of order pⁿ.

If G is a group of order pⁿm, where p is a prime and p does not divide m, any subgroup of order pⁿ is called a Sylow p-subgroup of G.

Example 1. Write D₃ = {1, a, a², b, ba, ba²}, where o(a) = 3, o(b) = 2, and aba = b. Then H = {1, a, a²} is the unique Sylow 3-subgroup, but {1, b}, {1, ba}, and {1, ba²} are three Sylow 2-subgroups. Hence, the Sylow 2-subgroups may not be normal or unique. We show later that a Sylow p-subgroup is normal if and only if it is unique.

Example 2. If G is a finite abelian group and p is a prime divisor of |G|, let G(p) = {a G o(a) = p^k for some k ≥ 0}. This set is a subgroup (because G is abelian) and so is a p -subgroup of G that contains every p-subgroup. It is thus the unique Sylow p-subgroup of G, called the p- primary component of G.

Corollary 2 of Theorem 3 §7.2 shows that every finite abelian group is isomorphic to the direct product of its primary components and thus of its distinct Sylow p-subgroups. We characterize when this happens in a nonabelian group in Section 9.3.

A Sylow p-subgroup P of a finite group G is a p-subgroup of G of maximum possible order (by Theorem 1). Note that each conjugate aPa⁻¹ of P is also a Sylow p-subgroup because |aPa⁻¹| = |P|. The converse is also true: Every Sylow p-subgroup is conjugate to P. In fact, every p-subgroup of G is contained in a conjugate of P (and so is contained in a Sylow p-subgroup of G)

Theorem 2. Let P be a Sylow p -subgroup of a finite group G. If H is any p-subgroup of G, then H ⊆ aPa⁻¹ for some a G.

Proof. Let X = {aP a G} be the set of left cosets of P in G and let H act on X by left multiplication: h · aP = haP for all h H. Write |G| = pⁿm, where p does not divide m. Then |X| = |G: P| = m, so p does not divide |X|. Hence (because H is a p -group) Theorem 4 §8.3 shows that p does not divide |X_f|, where X_f is the fixed subset. In particular, X_f is not empty, so let aP X_f, a G. Then haP = h · aP = aP for all h H, whence a⁻¹ha P for all h H. Thus H ⊆ aPa⁻¹, as required.

Taking H to be any Sylow p-subgroup of G, we obtain

Corollary 1. Sylow's Second Theorem. If G is a finite group, any two Sylow p-subgroups of G are conjugate in G.

Because a subgroup of G is normal in G if and only if it equals all its conjugates in G, we get Corollary 2.

Corollary 2. A Sylow p -subgroup of a finite group G is normal in G if and only if it is unique.

Example 3. Given D₃, as in Example 1, the Sylow 2-subgroups {1, b}, {1, ba}, and {1, ba²} must be conjugate. In fact, a{1, b}a⁻¹ = {1, ba} and a²{1, b}a⁻² = {1, ba²}.

The next result identifies a fundamental technique due to Giovanni Frattini. We return to this in Section 9.3.

Corollary 3. Frattini Argument. Let H G and let P be a Sylow p-subgroup of H. Then we have G = HN_G(P), where N_G(P) is the normalizer of P in G.

Proof. Suppose g G. Then gPg⁻¹ ⊆ H because H G, so gPg⁻¹ is also a Sylow p-subgroup of H. By Corollary 1, h(gPg⁻¹)h⁻¹ = P for some h H, so hg N_G(P). The result follows.

If K G, Example 4, employs Theorem 2 to provide some useful information about the Sylow subgroups of K and G/K.

Example 4. Let K G, where G is a finite group, and let p be a prime.

Solution.

(1) We begin with one of the implications in (1).

Claim: If P is a Sylow p-subgroup of G then P ∩ K is a Sylow p-subgroup of K.

Proof. P ∩ K is a p-subgroup of K, so let P ∩ K ⊆ X where X is a Sylow p-subgroup of K. But X is a p -subgroup of G so X ⊆ aPa⁻¹ for some a G by Theorem 2. It follows that

a⁻¹(P ∩ K)a ⊆ a⁻¹Xa ⊆ P ∩ (a⁻¹Ka) = P ∩ K.

Hence, these sets are equal, and in particular P ∩ K = X. This proves the Claim.

Now if H is a Sylow p-subgroup of K, then H ⊆ P for some Sylow p-subgroup P of G. Hence, H ⊆ P ∩ K, so H = P ∩ K by the Claim. This proves (1).

(2) Let |G| = pⁿm where p does not divide m. By Lagrange's theorem, let where k ≤ n and r|m. Thus . Let be some Sylow p-subgroup of so . Then |H| = pⁿr. So if P is a Sylow p-subgroup of H, then P is a Sylow p-subgroup of G, and it remains to show PK = H. But by the second isomorphism theorem (Theorem 1 §8.1), and |P ∩ K| = p^k by (1). Hence, so |PK| = pⁿr = |H|. Since PK ⊆ H, this gives PK = H, as required. The proof that each of the groups is a Sylow p -subgroup of is left to the reader.

The third Sylow theorem is concerned with the number of Sylow p -subgroups of a finite group G where p is a prime. We will denote this by n_p or n_p(G) if the group must be identified. Although determining n_p from the order of the group is not possible in general, we can deduce a good deal of numerical information.

Theorem 3. Sylow's Third Theorem. Let G be a group of order pⁿm, where p is a prime, n ≥ 1, and p does not divide m. If n_p denotes the number of distinct Sylow p-subgroups of G, then:

Proof. By Sylow's second theorem, (3) follows by Theorem 2 §8.2, so n_p divides |G| = pⁿm. Hence, (2) follows from (1) because (1) implies that gcd (p, n_p) = 1.

To prove (1), let X denote the set of all Sylow p-subgroups of G so that |X| = n_p. Fix P in X and let P act on X by conjugation. If X_f is the fixed subset, then n_p = |X| ≡ |X_f| modulo p by Theorem 4 §8.3, so it suffices to show that X_f = {P}. We have X_f = {Q X aQa⁻¹ = Q for all a P}, so P X_f is clear. If Q X_f, then P ⊆ N(Q), so both P and Q are Sylow p -subgroups of N(Q) (they are p-subgroups of maximal order). But Q N(Q), so Q = P follows by Corollary 2 of Theorem 2. Hence X_f = {P}, as required.

Examples 5–9 illustrate the power of the Sylow theorems and how to apply them to particular groups.

Example 5. If p and q are primes, show that no group G of order pq is simple.

Solution. If p = q, then G is abelian by Theorem 7 §8.2, so G is not simple because |G| = p² is not a prime. So assume that p > q. Then n_p ≡ 1 (modp) and n_p|q by Theorem 3, so n_p = 1 because q < p. Thus, there is just one Sylow p-subgroup, and it is normal by Corollary 2 of Theorem 2.

Example 6. Show that every group of order 175 is abelian.

Solution. Observe |G| = 175 = 5² · 7. Then n₅|7 and n₅ ≡ 1 (mod5) by Theorem 3, from which n₅ = 1. Hence, there is just one Sylow 5-subgroup P of G and so P G. Similarly n₇|5² so n₇ = 1, 5, or 25, and n₇ ≡ 1 (mod7). Thus n₇ = 1, so there is a unique Sylow 7-subgroup Q of G and Q G. Now P ∩ Q = {1} because gcd (|P|, |Q|) = 1, so |PQ| = |P||Q| = |G|. Thus G = PQ, so G ≅ P × Q by Theorem 3 §8.1. But P and Q are abelian by Theorem 7 §8.2, so G is abelian.

Example 7. Show that there is no simple group of order 56.

Solution. If |G| = 56 = 2³ · 7, then n₇ divides 8 and n₇ ≡ 1 (mod7). This means that n₇ = 1 or n₇ = 8. If n₇ = 1, then the Sylow 7-subgroup is normal. If n₇ = 8, there are eight distinct cyclic subgroups in G of order 7. Because the intersection of any two of these subgroups equals {1}, there are 8 · 6 = 48 elements of order 7. This leaves eight elements, so the Sylow 2-subgroup is unique and hence normal.

Example 8. Show that there is no simple group of order 72.

Solution. If |G| = 72 = 2³ · 3², then n₂ = 1, 3, or 9 and n₃ = 1 or 4 by Theorem 3, so the method in Example 7 fails. However, let P denote any Sylow 3-subgroup of G. If n₃ = 1, then P G. If n₃ = 4, then |G: N(P)| = 4 by Sylow's third theorem. Thus, Theorem 1 §8.3 provides a homomorphism θ: G → S₄, with ker θ ⊆ N(P), and ker θ ≠ {1} because |G| = 72 does not divide |S₄| = 24. As ker θ G and N(P) ≠ G, we are done.

A famous theorem of William Burnside asserts that no group of order pⁿq^m is simple where p and q are primes. The proof involves the theory of group representations and is beyond the scope of this book. However, we can do the following case.

Example 9. Show that no group of order p²q² is simple when p and q are primes.

Solution. Let |G| = p²q². If p = q, then Z(G) ≠ {1} by Theorem 6 §8.2 and we are finished. So assume that p > q. We have n_p = 1, q, or q², and n_p ≡ 1 (modp). If n_p = 1, the Sylow p-subgroup is normal and we are done. The case n_p = q is impossible because q < p. So assume that n_p = q², obtaining q² ≡ 1 (modp). Then p divides q² − 1 = (q − 1)(q + 1), so either p|(q − 1) or p|(q + 1). Because p > q, the first alternative is impossible; the second implies that q+ 1 ≥ p > q from which q + 1 = p. This means that p = 3 and q = 2, so |G| = 36. But then any Sylow 3-subgroup has index 4, so there is a homomorphism θ: G → S₄ by Theorem 1 §8.3. This homomorphism cannot be one-to-one, so ker θ is normal in G.

We are now going to use the Sylow theorems to characterize the groups of order less than 16. It turns out that three of these groups belong to a family of groups that resemble the dihedral groups and are constructed in much the same way. We let n = 2m be an even positive integer, let and let

and  

Then A and B are invertible complex matrices, and we can easily verify that |A| = n, ABA = B, and B² = A^m. One verifies that

G = {I, A, A², . . ., Aⁿ⁻¹, B, BA, . . ., BAⁿ⁻¹}

is a subgroup of and |G| = 2n because has index 2 in G. As for D_n, we abstract this situation as follows.

If n = 2m, m ≥ 1, the dicyclic group Q_n is the group of order 2n presented as

Q_n = {1, a, , aⁿ⁻¹, b, ba, , baⁿ⁻¹}, where o(a) = n, aba = b, and b² = a^m.

The condition that |Q_n| = 2n amounts to the requirement that The group Q_n is presented just like D_n, except that here n = 2m must be even and b² = a^m (recall that b² = 1 in the dihedral case). Again, a^kba^k = b for all so

a^kb = ba^−k = ba^n−k,   for all

This equation shows that (ba^k)² = b² = a^m for all k so, as |a^m| = 2, we get

|ba^k| = 4,   for all

(in contrast to |ba^k| = 2 in D_n). Two of these dicyclic groups are already familiar, as we see in Example 10.

Example 10. Q₂ ≅ C₄ because |Q₂| = 4. We claim that Q₄ ≅ Q, the quaternion group (Section 2.8). Indeed Q = { ± 1, ± i, ± j, ± k} and, writing a = i and b = j, we have o(a) = 4, aba = b, and b² = a². Hence Q ≅ Q₄.

Theorem 4. Every group G of order 8 is isomorphic to one of C₈, C₄ × C₂, C₂ × C₂ × C₂, D₄, or Q₄ = Q.

Proof. If G is abelian, then G is isomorphic to one of C₈, C₄ × C₂, or C₂ × C₂ × C₂ by Example 8 §2.8 (or by Corollary 2 of Theorem 6 §7.2). If G is not abelian, then x² = 1 cannot hold for all x G, so there exists a G, o(a) = 4. Write If b ∉ K, then G = K ∪ Kb, and we claim that aba = b. Indeed bab⁻¹ K because K G, and o(bab⁻¹) = o(a) = 4. As bab⁻¹ ≠ a because G is not abelian, we get bab⁻¹ = a⁻¹; that is, aba = b. Hence, if o(b) = 2 for some b ∉ K, then G ≅ D₄. Otherwise, o(b) = 4 for all b ∉ K. But then a² is the only element of G of order 2, so b² = a² for all b ∉ K. Thus G ≅ Q₄.

In order to determine the groups of order 12, we need Lemma 1.

Lemma 1. The only subgroup of S_n of index 2 is A_n.

Proof. If |S_n: K| = 2, then K S_n and |S_n/K| = 2, so σ² K for all σ S_n. If σ is a 3-cycle, then σ³ = ε so σ = σ⁴ K. But A_n is generated by the 3-cycles (Lemma 4 §2.8), so A_n ⊆ K. This implies that A_n = K because |S_n: A_n| = 2.

Theorem 5. Every group of order 12 is isomorphic to one of C₁₂, C₆ × C₂, A₄, D₆, or Q₆.

Proof. Let P and Q be Sylow subgroups with |P| = 3 and |Q| = 4. If G is abelian, G ≅ P × Q, so either G ≅ C₃ × C₄ ≅ C₁₂ or G ≅ C₃ × C₂ × C₂ ≅ C₆ × C₂. If G is nonabelian, there is a homomorphism θ: G → S₄ with ker θ ⊆ P. If ker θ = {1}, then G ≅ A₄ by Lemma 2. So assume P G. Similarly, we have ϕ: G → S₃ with ker ϕ ⊆ Q. Write ker ϕ = L. Then L ≠ {1}, and L = Q implies that Q G, so G ≅ P × Q is abelian. Hence |L| = 2, so LP ≅ L × P ≅ C₆.

So let a G have order 6 and write If b ∉ K, then G = K ∪ Kb and aba = b, as in Theorem 4. Finally, b² K because |G/K| = 2, and it remains to show that b² = 1 (G ≅ D₆) or b² = a³ (G ≅ Q₆). If b² = a or a⁵, then o(b) = 12 and G is abelian. If b² = a², then b³ = ba² = a⁻²b = a⁴b, so b² = a⁴, a contradiction. Hence b² ≠ a² and, similarly, b² ≠ a⁴.

These results, together with earlier work, enable us to describe all the groups of order 15 or less. If p is a prime, the only group of order p is C_p. There are two groups of order 2p: C_2p and D_p (Theorem 3 §2.6). And there are two groups of order p²: and C_p × C_p (Theorem 7 §8.2). We have already described the groups of order 8 or 12, and the only group of order 15 is C₁₅ (Exercise 4). This list describes every group of order at most 15. The description of the groups of order 16 is more complicated (there are 14), and the general problem of describing all groups of a given order is extremely difficult.⁹³

We conclude this section with an elegant direct proof of Theorem 1. The argument requires a number-theoretic fact. Recall that the binomial coefficient nr is defined by for 0 ≤ r ≤ n.

Lemma 2. Let p be a prime and let m, n, and k be positive integers. Then pⁿ divides m if and only if pⁿ divides p^kmp^k.

Proof. Since p^kmp^k = p^km(p^km − 1) (p^km − i) [p^km − (p^k − 1)]p^k(p^k − 1) (p^k − i) [p^k − (p^k − 1)], it suffices to show that

pⁿ divides (p^km − i)   pⁿ divides (p^k − i) for each i = 1, 2, . . ., p^k − 1.

Observe that if pⁿ divides (p^km − i) then n < k (otherwise p^k|i). Hence, the proof is completed by the observation that (p^km − i) = (p^km − p^k) + (p^k − i).

With this we can give Helmut Wielandt's elegant proof⁹⁴ of Theorem 1, which does not use induction or Cauchy's theorem (and so provides another proof of Cauchy's theorem).

Proof of Theorem 1. If p^k divides |G|, let X = {U ⊆ G U a subset, |U| = p^k} and define an action of G on X by a · U = aU for all U in X and a in G. Given U in X, let S(U) = {a G aU = U} denote the stabilizer. Write |G| = p^km and write where p does not divide

Claim. V in X exists such that p^r+1 does not divide |G: S(V)|.

Proof. If not, p^r+1 divides the order of every orbit in X (by Lemma 3 §8.3) and so divides |X|. But |X| = p^kmp^k, which means that p^r+1 divides m by Lemma 3. Hence a contradiction. This proves the Claim.

Now let V be as in the claim and write S = S(V). We show that |S| = p^k, so S is the desired subgroup of G. Now p^r+1 does not divide by the Claim, from which p^k does divide |S|. In particular, p^k ≤ |S|. But if then Sv ⊆ V by the definition of S, so |S| = |Sv| ≤ |V| = p^k. Thus |S| = p^k, as required.

Peter Ludvig Mejdell Sylow (1832–1918)  Sylow was born in Norway and spent most of his professional life as a high school teacher in Halden. Despite onerous teaching duties, he found time to study the works of Abel and, in 1862–1863, he gave lectures on Galois theory and permutation groups at Christiania University in Oslo. The Sylow theorems were published in 1872 for permutation groups (Georg Frobenius extended them to abstract groups in 1887). These theorems are among the most important results on finite groups. Sylow applied them to show that any equation whose Galois group has prime-power order is solvable in radicals.

In addition to his study of groups, Sylow spent eight years editing the works of Abel. After his retirement from teaching high school, he was appointed to a chair at Christiania University, a position he held for the rest of his life.

Exercises 8.4

8.5 Semidirect Products

There is no doubt that forming direct products is an important method of constructing groups using smaller groups: For example, all finite abelian groups can be constructed by forming direct products of cyclic groups. In this brief section, we describe a more general way to form a group from smaller groups.

Let K and H be subgroups of a group G and assume that G = KH, where K ∩ H = {1}. If both K G and H G then G ≅ K × H by Theorem 3 §8.1. In view of this, a natural question is what happens if only one of K and H is normal in G, say K G. Since G = KH and K ∩ H = {1}, each element g G has a unique representation as g = kh where k K and h H. Given another element g₁ = k₁h₁ of G, the key to understanding the group G is to describe the product gg₁ in the same form. This can be accomplished as follows:

gg₁ = khk₁h₁ = [k(hk₁h⁻¹)](hh₁),(*)

where hk₁h⁻¹ K because K G.

To describe this more formally, let a G and define a map σ_a: K → K by σ_a(k) = aka⁻¹ for all k K. This makes sense because K G, and σ_a is an automorphism of K for each a G. Hence (*) becomes

(kh)(k₁h₁) = [k σ_h(k₁)](hh₁).(**)

Now observe that the map θ: H → aut(K) given by θ(h) = σ_h is a group homomorphism.⁹⁵ This provides a way to turn this around: Starting with K, H, and θ, we can recreate G, using (**) to motivate the multiplication.

Theorem 1. Let K and H be groups and let θ: H → aut K be a homomorphism. Write θ(h) = σ_h for all h H. If G = K × H is the cartesian product, define an operation on G as follows:

(k, h)(k₁, h₁) = (k σ_h(k₁), hh₁), for all (k, h) and (k₁, h₁) in G.

Write K₁ = K × 1 and H₁ = 1 × H. Then:

Proof. (2) and (3) are routine verifications. As to (1), the operation is associative because the products [(k, h)(k₁, h₁)](k₂, h₂) and (k, h)[(k₁, h₁)(k₂, h₂)] each simplify to hh₁h₂). The verification of this, and of the rest of (1), is left to the reader.

If K and H are groups and θ: H → aut K is a homomorphism, the group G constructed in Theorem 1 is called the semidirect product of K by H, and is denoted K × _θH. Theorem 1, and the discussion preceding it, give an important characterization of semidirect products (often taken as the definition).

Theorem 2. Let G be a group.

Example 1. A direct product K × H is a semidirect product (let θ: H → aut K be the trivial homomorphism: θ(h) = 1_K for each h H).

Example 2. The dihedral group D_n = {1, a, . . ., aⁿ⁻¹, b, ba, . . ., baⁿ⁻¹} is given by o(a) = n, o(b) = 2 and aba = b. If we write and then it is clear that D_n = KH, K D_n (it has index 2) and K ∩ H = {1}, so

D_n ≅ C_n × _θC₂ for some θ: C₂→ aut C_n.

In fact, the multiplication in D_n is given by a^kb = ba^−k for all k, so ba^kb⁻¹ = (a^k)⁻¹. Hence θ: C₂→ aut C_n, where θ(b) is the automorphism x x⁻¹.

It is interesting to observe that D₆ ≅ C₃ × _θC₂ by Example 2, and C₆ ≅ C₃ × _θC₂ by Example 1. Hence, a semidirect product K × _θH is not uniquely determined by K and H; the homomorphism θ must be specified.

The next result determines all groups of order pq where p and q are primes. The theorem illustrates the way that semidirect products can be used to give the detailed structure of all groups of a given order, and it extends the theorem (Theorem 3 §2.6) that every group of order 2p is either cyclic or dihedral.

Theorem 3. Let G be a group of order pq where p ≤ q are primes.

(1) If p = q then G is cyclic or G ≅ C_p × C_p.

(2) If p < q and q6 ≡ 1 (mod p) then G is cyclic.

(3) If p < q and q ≡ 1 (mod p) then either G is cyclic or whereo(a) = q, o(b) = p and ab = ba^m, and where 1 ≤ m ≤ q − 1 and m^p ≡ 1 (mod q). [Here, all choices for m result in isomorphic groups.]

Proof. By Cauchy's theorem, choose a, b G such that o(a) = q and o(b) = p, and write and Then K G by the Corollary to Theorem 1 §8.3. Clearly K ∩ H = {1}, so G = KH and it follows that G is a semidirect product by Theorem 2.

(1) This is Theorem 7 §8.2.

(2) As usual, let n_p denote the number of Sylow p-subgroups of G. Then Sylow's third theorem (Theorem 3 §8.4) gives n_p ≡ 1 (mod p) and n_p q. Hence if q6 ≡ 1 (mod p) then n_p = 1, so H G, and we have G ≅ K × H ≅ C_q × C_p ≅ C_pq.

(3) So assume q ≡ 1 (mod p). Since let

b⁻¹ab = a^x where (*)

Then Continuing in this way gives

, for any k ≥ 1.

But b^p = 1 so this gives and hence x^p ≡ 1 (mod q). Since let have order p (by Cauchy's theorem). Then x = 1, m, m², . . ., m^p−1 are all solutions to x^p ≡ 1 (mod q). Moreover, there are no other solutions because x^p − 1 = 0 has at most p roots in If x = 1 in (*) then ba = ab so G is abelian, and hence cyclic. If x = m in (*) then b⁻¹ab = a^m so ab = ba^m and we have the situation in (3).

Finally, to realize the other solutions x = m^r where 1 < r ≤ p − 1, we change the generators of G. If we put b₁ = b^r then o(b₁) = p and because o(b) = p is a prime. Hence Furthermore, so this construction realizes the solution when x = m^r in (*).

Other such theorems are possible, but we conclude by identifying one quite general situation in which a finite group G is necessarily a semidirect product, namely if G has a normal subgroup K and and are relatively prime. The next result of Issai Schur deals with the case when K is abelian.

Theorem 4. Schur's Theorem. Suppose G has an abelian normal subgroup K, where and are relatively prime. Then G has a subgroup of order

Proof. Put and In each coset a of G/K select an element g_a G and assume that g₁ = 1, where 1 denotes the unity of G/K. If a, b G/K then g_ag_b = g_abk(a, b) for a uniquely determined element k(a, b) K. If g_a(g_bg_c) = (g_ag_b)g_c is written out it follows that

k(a, bc) k(b, c) = k(ab, c) a, b)g_c].(*)

Now write k(b) = ∏ _aG/Kk(a, b). If the product of each side of equation (*) is taken as a ranges over G/K, we obtain (since K is abelian)

Now let nn′ ≡ 1 (mod m) and write k(a for all a G/K. Raising both sides of (**) to the power −n′ yields

(***)

Finally, write H ={g_ak_a a G/K}, Then () gives

This means that H is a subgroup and that the map a g_ak_a is an onto homomorphism G/K → H. It is one-to-one because g_ak_a = g_bk_b implies that so g_a = g_b by the choice of these elements.

Along with I. Schur, H. Zassenhaus is also credited with the general version of the next theorem.⁹⁶

Theorem 5. Schur-Zassenhaus Theorem. Let G be a group of order kn where k and n are relatively prime. Assume that G has a normal subgroup K of order k. Then G has a subgroup H of order n, and so is a semidirect product K × _θH.

Proof. It suffices to show that H exists (then K ∩ H = {1} because the orders are relatively prime, and hence G = KH. We may assume that k > 1. The proof is by induction on

Case 1. K contains a proper subgroup M such that M G.

Write Then K/M G/M, and so G/M has a subgroup L/M of order n (by induction). But then M L and so L contains a subgroup of order n (again by induction). Hence, the theorem is proved in this case.

Case 2. K contains no proper subgroup that is normal in G.

In this case let P be a Sylow p-subgroup of K, and let N = N(P) be the normalizer of P in G. Then P is a Sylow p-subgroup of G (because gcd(k, n) = 1), and so has conjugates in G. These are all in K so, as N ∩ K is the normalizer of P in K, we obtain Hence so Consequently NK = G and so N/(N ∩ K) ≅ G/K has order n.

If it happens that N ≠ G this shows that N contains a subgroup of order n (by induction), and we are done. So assume that N = G. This means that P G, and hence that Z G where Z is the center of P (being characteristic in P, see Corollary 3 of Theorem 3 §2.8). Since Z ≠ 1 by Theorem 6 §8.2, it follows that Z = K (we are in Case 2). Thus, K is abelian and we are done by Schur's theorem (Theorem 4).

Exercises 8.5

8.6 An Application to Combinatorics

A main theme in this chapter has been to apply counting arguments to gain information about a finite group G by defining G-sets and using the orbit decomposition theorem. In this section, we turn this successful technique around and use the group to gain information about the sets it acts on. Specifically, we get a formula for the number of distinct orbits, which is useful in solving certain combinatorial problems. We begin by deriving this formula that is of interest in its own right, and then describing how it applies to combinatorics.

If X is any G-set and x X, the stabilizer of x in X is the subgroup

S(x) = {a G a · x = x}

of all elements of G that fix x. Dually, if a G we write

F(a) = {x X a · x = x},

the set of elements of X fixed by a. We refer to these sets frequently because of the following result of Cauchy and Frobenius.

Theorem 1. Cauchy-Frobenius Lemma. ⁹⁷ Let X be a G -set and assume that G and X are finite. If n is the number of distinct orbits of G in X, then

n = 1|G| ∑ _aG|F(a)|.

Proof. The proof proceeds by the time-honored method of counting the elements of a set Y in two ways and equating the results. In this case, consider the subset Y = {(a, x) x X, a G, a · x = x} of G × X. Then

|Y| = ∑ _aG|F(a)|(*)

because, for each element a of G, there are exactly |F(a)| pairs in Y with first component a. In the same way, we obtain

|Y| = ∑ _xX|S(x)|.

However, we can refine this second sum because X is partitioned into orbits by the action of G. If G · x₁, . . ., G · x_n are the n distinct orbits, then each x X belongs to exactly one orbit G · x_i, so

(**)

Now recall that |G · x| = |G: S(x)| holds for all x X (Lemma 3 §8.3). If x G · x_i, then G · x = G · x_i and so |S(x)| = |S(x_i)|. Hence (**) becomes

Combining this with (*) gives n|G| = |Y| = ∑ _aG|F(a)|. The lemma follows.

As an illustration, let G act on itself by conjugation, so the orbits are the conjugacy classes. If a G, then F(a) = {x G axa⁻¹ = x} = N(a) is the normalizer of a in G. Thus, the Cauchy–Frobenius lemma gives the following Corollary.

Corollary. A finite group G has (1/|G|) ∑ _aG|N(a)| distinct conjugacy classes.

Before applying the Cauchy–Frobenius lemma, we must consider a technicality. If G is a group and X is a nonempty set, a function X × G → X, written (x, g) x · g, is called a right action of G on X if x · 1 = x and (x · a) · b = x · (ab) hold for all a, b G and all x X. Clearly, all the results for G -sets can be proved for right actions. In fact, we can easily verify that a * x = x · a⁻¹ defines a (left) action of F on X. The reason for mentioning this is that right actions occur naturally in the examples that follow.

The combinatorial applications in which we are interested can all be described using the following format. Let D and C be nonempty finite sets and let C^D denote⁹⁸ the set of all mappings λ: D → C. Suppose that G is a subgroup of S_D. Given σ G and λ C^D, we have D → ^σD → ^λC, so it is natural to define

λ · σ = λσ = the composition of the maps.

This is a right action of G on the permutation group C^D (the axioms are elementary properties of composition of mappings), and it plays a central role in our discussion. Example 1 is typical.

Example 1. If q colors are available, find the number of ways in which a pyramid can be painted if the edges of the base are all of length 1 and the sides are of length 2. Assume that each face is painted a single color.

Solution. Label the faces 1, 2, 3, and 4 as shown in the figure at the right. Then the labeled pyramid can be colored in q⁴ ways because there are q color choices for each face. The problem is that many of these colorings are indistinguishable when the labels are removed. The reason is that one labeled coloring may be carried to another by a motion of the pyramid, so both result in the same unlabeled coloring. To make this more precise, let

D = {1, 2, 3, 4}  and  C = the set of q colors.

Then each map λ: D → C determines a labeled coloring, the color of face i being λ(i). Conversely, each labeled coloring determines such a map, so we may identify C^D with the set of labeled colorings. Now let G ⊆ S_D = S₄ be the group of motions of the pyramid, where a motion is identified with the permutation of the face labels that it induces. Then G acts on C^D on the right as discussed previously, and we claim that the unlabeled colorings can be identified with the orbits of G in the set C^D of labeled colorings. Indeed, if λ and μ are labeled colorings in C^D, then

λ and μ lead to indistinguishable colorings when the labels are removed;

  λ is achieved by first moving the pyramid and then applying μ;

  λ = μσ for some σ G;

  λ and μ are in the same G -orbit.

Hence, the number of unlabeled colorings is equal to the number of orbits, so the Cauchy–Frobenius lemma applies. In this case G = {ε, σ, σ²}, where σ = (234). We have F(ε) = C^D, so |F(ε)| = q⁴. Next,

F(σ) = {λ λσ = λ} = {λ λ(2) = λ(3) = λ(4)}.

Hence a coloring λ is in F(σ) just when sides 2, 3, and 4 are all the same color. We may choose this color in q ways and color the base in q ways, so |F(σ)| = q². Similarly, |F(σ²)| = q², so the number of orbits is by Theorem 1.

The technique used in Example 1 can be used in the same way to count the number of ways to color the edges or vertices of a figure. In general, we label the objects to be colored as 1, 2, 3, . . ., n. The group G is the subgroup of S_n consisting of all permutations of these objects resulting from a rigid motion of the figure. We then identify the colorings with the set C^D of all mappings from D = {1, 2, . . ., n} to the set C of colors. If λ is such a map and σ G, the map λσ colors object i the same as the map λ colors object σ(i). As σ is a motion of the figure, the results are indistinguishable when the labels are removed, so the number of distinguishable unlabeled colorings equals the number of orbits (as in Example 1). Hence, the Cauchy–Frobenius lemma applies.

Before giving more examples, we describe a convenient way to compute |F(σ)| in the Cauchy–Frobenius lemma, where σ S_n, D = {1, 2, . . ., n}, and S_n acts on C^D, as before. If σ is factored into disjoint cycles, we customarily ignore a cycle (k) of length 1 because σ fixes k. However, our present purpose requires that we include such cycles.

For example, if n = 7, we now think of σ = (14)(357) in S₇ as a product of four disjoint cycles: σ = (14)(2)(357)(6). If q colors are available in C, we claim that |F(σ)| = q⁴. Indeed, given λ: D → C, we have

λ F(σ) λσ = λ λ(1) = λ(4) and λ(3) = λ(5) = λ(7),

so there are q choices for each of the colors λ(1) = λ(4), λ(2), λ(3) = λ(5) = λ(7), and λ(6) and hence q⁴ possibilities for the map λ.

The obvious generalization is valid. If σ S_n, then |F(σ)| = q^c, where c is the number of cycles in the factorization in S_n of σ into disjoint cycles (including cycles of length 1). The integer c is called the cycle index of σ and is denoted c = cycσ. We record this as Theorem 2.

Theorem 2. Let C be a set of q colors and let S_n act on C^D by composition of maps, where D = {1, 2, . . ., n}. Then

|F(σ)| = q^cycσfor any σ S_n.

If G is a subgroup of S_n, the number of orbits of G in C^D is

(1/|G|) ∑ _σGq^cycσ.

Example 2. Suppose that a chemical molecule is modeled in the form of an equilateral triangle with the atoms at the vertices as shown in the figure below. If q colors are available and each atom is painted a single color, how many distinct ways can the molecule be colored? (The edges are not painted.)

Solution. Here the three vertices, labeled 1, 2, and 3, are permuted by motions in S₃. Because of the high degree of symmetry of the equilateral triangle, every permutation in S₃ can be achieved by a motion, so S₃ is the group of motions. By Theorem 2 we get

By Theorem 1 there are colorings (orbits).

In Example 3, we vary the theme by insisting that no color is repeated. This amounts to labeling the various facets of the object with distinct colors.

Example 3. Suppose that children's blocks are to be constructed as cubes with each of the six faces painted a different color. If q ≥ 6 colors are available, how many distinct blocks can be made?

Solution. Let D = {1, 2, 3, 4, 5, 6} and let C be the set of q colors, as before. Because the faces are distinct colors, a coloring in this case is a one-to-one mapping λ: D → C. Let X ⊆ C^D denote the set of all such mappings. If G is the group of motions of the cube, G acts on X by composition because λσ is one-to-one whenever σ G and λ X. If σ ≠ ε in G, then F(σ) = {λ λσ = λ} is empty. (If λ F(σ), then σ(i) = j implies that λ(j) = λ[σ(i)] = λ(i), from which i = j). Thus |F(σ)| = 0 if σ ≠ ε, whereas |F(ε)| = q !/[(q − 6) !] because F(ε) = X. Hence, the Cauchy–Frobenius lemma gives the number of colorings as q !/[|G|(q − 6) !], so it remains only to compute |G|. Label the faces of the cube 1, 2, 3, 4, 5, and 6. If we initially place the cube with side 1 on top, we determine a motion by choosing which side ends up on top (six choices) and then choosing one of four rotations fixing the top and bottom faces (four choices). Thus, there are 6 · 4 = 24 choices in all, so |G| = 24 and there are q / [24(q − 6) !] possible blocks. If q = 6 (the minimal number of colors), there are 6 !/‘ 24 = 30 possible blocks.

The argument in Example 3 gives the general result in Theorem 3.

Theorem 3. Let D = {1, 2, . . ., n}, let C be a set of q ≥ n colors, and let X ⊆ C^D denote the set of one-to-one mappings D → C. If G is a subgroup of S_n, then G acts on X by composition of maps, and the number of orbits is q !/[|G|(q − n) !].

Needless to say, this theory has been developed further, and these examples provide only a glimpse of the possibilities. For example, we could ask how many ways a cube can be painted with q colors when exactly two faces are red or when at least two faces are red. In 1937, George Polya answered such questions, and many others, by giving an elegant and comprehensive generalization of the Cauchy–Frobenius lemma.⁹⁹ This is beyond the scope of this book.

Exercises 8.6

Notes

89 Such a subgroup H must in fact exist (see Theorem 1 §8.4).

90 An action on the right may be defined by . This is nothing new because is then an action in the present sense.

91 Another name for S(x) is the isotropy group of x.

92 American Mathematical Monthly, Vol. 66, 1956, p. 119.

93. A lot is known about the number of groups of order pⁿ for a prime p. For example there are 2328 groups of order 2⁷, and 9310 groups of order 3⁷. See O'Brien, I.A. and Vaughan-Lee, M.R. Journal of Algebra 292 (2005), 243–258, for more information.

94 Wielandt, H., Ein Bewise Fur die Existenz der Sylowgruppen, Archiv der Mathematik 10 (1959), 401–402.

95 This amounts to saying that is an action of the group G on K. Such actions were studied in Section 8.3, where K was only required to be a set.

96 The result was credited to Schur by Zassenhaus in his book The Theory of Groups, 2nd English Edition, Chelsea, 1958.

97 The lemma was known to Cauchy and Frobenius in the mid-1800s, and was rediscovered by William Burnside in 1900. Hence, it is also called Burnside's lemma.

98 This exponential notation is used because .

99 For an exposition of Polya's theory (by N. G. de Bruijn), see Beckenbach, E., ed., Applied Combinatorial Mathematics, New York: Wiley, 1964. Another good treatment appears in Roberts, F.S., Applied Combinatorics, Englewood Cliffs, NJ. Prentice-Hall, 1984, Chapter 7.