Group Theory Notes PDF

GROUP THEORY NOTES FOR THE COURSE ALGEBRA 3, MATH 370 MCGILL UNIVERSITY, FALL 2003, VERSION: November 3, 2003 EYAL Z. GOREN i  GROUP THEORY ii Con...

GROUP THEORY NOTES FOR THE COURSE ALGEBRA 3, MATH 370 MCGILL UNIVERSITY, FALL 2003, VERSION: November 3, 2003 EYAL Z. GOREN i  GROUP THEORY ii Contents Part 1. Basic Concepts and Key Examples 1 1. First definitions 1 1.1. Group 1 1.2. Subgroup and order 2 2. Main examples 4 2.1. Z, Z/nZ and (Z/nZ)× 4 2.2. The dihedral group D2n 4 2.3. The symmetric group Sn 5 2.4. Matrix groups and the quaternions 8 2.5. Groups of small order 9 2.6. Direct product 10 3. Cyclic groups 10 4. Constructing subgroups 11 4.1. Commutator subgroup 11 4.2. Centralizer subgroup 11 4.3. Normalizer subgroup 12 5. Cosets 12 6. Lagrange’s theorem 13 7. Normal subgroups and quotient groups 14 Part 2. The Isomorphism Theorems 17 8. Homomorphisms 17 8.1. Basic definitions 17 8.2. Behavior of subgroups under homomorphisms 18 9. The first isomorphism theorem 18 10. The second isomorphism theorem 20 11. The third isomorphism theorem 20 12. The lattice of subgroups of a group 22 Part 3. Group Actions on Sets 23 13. Basic definitions 23 14. Basic properties 23 15. Some examples 26 16. Cayley’s theorem 28 16.1. Applications to construction of normal subgroups 28 17. The Cauchy-Frobenius formula 29 17.1. A formula for the number of orbits 29 17.2. Applications to combinatorics 30 17.3. The game of 16 squares 32 17.4. Rubik’s cube 33 Part 4. The Symmetric Group 34 18. Conjugacy classes 34 19. The simplicity of An 35 Part 5. p-groups, Cauchy’s and Sylow’s Theorems 38 20. The class equation 38 21. p-groups 38 21.1. Examples of p groups 39  GROUP THEORY iii 22. Cauchy’s Theorem 40 23. Sylow’s Theorems 41 23.1. Examples and applications 42 Part 6. Finitely Generated Abelian Groups, Semi-direct Products and Groups of Low Order 44 24. The structure theorem for finitely generated abelian groups 44 25. Semi-direct products 44 25.1. Application to groups of order pq. 46 26. Groups of low, or simple, order 47 26.1. Groups of prime order 47 26.2. Groups of order p2 47 26.3. Groups of order pq, p < q 47 27. Groups of order 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15 47 28. Groups of order 8 48 29. Groups of order 12 49 Part 7. Composition series, the Jordan-Hölder theorem and solvable groups 50 30. Composition series 50 30.1. Two philosophies 50 30.2. Composition series 50 31. The Jordan-Hölder theorem 50 32. Solvable groups 51  GROUP THEORY 1 Part 1. Basic Concepts and Key Examples Groups are among the most rudimentary forms of algebraic structures. Because of their simplicity, in terms of their definition, their complexity is large. For example, vector spaces, which have very complex definition, are easy to classify; once the field and dimension are known, the vector space is unique up to isomorphism. In contrast, it is difficult to list all groups of a given order, or even obtain an asymptotic formula for that number. In the study of vector spaces the objects are well understood and so one focuses on the study of maps between them. One studies canonical forms (e.g., the Jordan canonical form), diagonalization, and other special properties of linear transformations (normal, unitary, nilpotent, etc.). In contrast, at least in the theory of finite groups on which this course focuses, there is no comparable theory of maps. A theory exist mostly for maps into matrix groups (such maps are called linear representation and will not be studied in this course). While we shall define such maps (called homomorphisms) between groups in general, there will be a large set of so called simple groups1 for which there are essentially no such maps: the image of a simple group under a homomorphism is for all practical purposes just the group itself. The set of atoms is large, infinite in fact. The classification of all simple groups was completed in the second half of the 20-th century and has required thousands of pages of difficult math. Thus, our focus - apart from the three isomorphism theorems - will be on the structure of the objects themselves. We will occupy ourselves with understanding the structure of subgroups of a finite group, with groups acting as symmetries of a given set and with special classes of groups (cyclic, simple, abelian, solvable, etc.). 1. First definitions Dummit & Foote §1.1 1.1. Group. A group G is a non-empty set with a function m : G × G −→ G, where we usually abbreviate m(g, h) to g ? h or simply gh, such that the following hold: (1) (Associativity) f (gh) = (f g)h for all f, g, h ∈ G. 2 (2) (Identity) There is an element e ∈ G such that for all g ∈ G we have eg = ge = g. (3) (Inverse) For every g ∈ G there is an element h ∈ G such that gh = hg = e. It follows quite easily from associativity that given any n elements g1 ,... , gn of G we can put paren- theses as we like in g1 ? · · · ? gn without changing the final outcome. For that reason we allow ourselves to write simply g1 · · · gn (though the actual computation of such product is done by successively multiplying two elements, e.g. (((g1 g2 )(g3 g4 ))g5 ) is a way to compute g1 g2 g3 g4 g5.) 1A more appropriate name might be “atomic groups”, but the terminology is too deeply rooted to deviate from it. 2In fuller notation m(f, m(g, h)) = m(m(f, g), h).  GROUP THEORY 2 The identity element is unique: if e0 has the same property then e0 = ee0 = e. Sometimes we will denote the identity element by 1 (or by 0 is the group is commutative - see below). The element h provided in axiom (3) is unique as well: if h0 has the same property then hg = e = h0 g and so hgh = h0 gh, thus h = he = hgh = h0 gh = h0 e = h0. We may therefore denote this h unambiguously by g −1. A useful identity is (f g)−1 = g −1 f −1. It is verified just by checking that g −1 f −1 indeed functions as (f g)−1 and it does: (g −1 f −1 )(f g) = g −1 (f −1 f )g = g −1 eg = g −1 g = e. −1 We define by induction g n = g n−1 g for n > 0 and g n = (g −n ) for n < 0. Also g 0 = e, by definition. One proves that g n+m = g n g m for any n, m ∈ Z. A group is called of finite order if it has finitely many elements. It is called abelian if it is commutative: gh = hg for all g, h ∈ G. 1.2. Subgroup and order. Dummit & Foote A subgroup H of a group G is a non-empty subset of G such that (i) e ∈ H, (ii) if g, h ∈ H then §§2.1, 2.3, 2.4 gh ∈ H, and (iii) if g ∈ H then also g −1 ∈ H. One readily checks that in fact H is a group. One checks that {e} and G are always subgroups, called the trivial subgroups. We will use the notation H. The order of an element h ∈ G, o(h), is defined to be the minimal positive integer n such that hn = e. If no such n exists, we say h has infinite order. Lemma 1.2.1. For every h ∈ G we have o(h) = ] < h >. end of lecture 1 Proof. Assume first that o(h) is finite. Since for every n we have hn+o(h) = hn ho(h) = hn we see that < h >= {e, h, h2 ,... , ho(h)−1 }. Thus, also ] < h > is finite and at most o(h). Suppose conversely that ] < h > is finite, say of order n. Then the elements {e = h0 , h,... , hn } cannot be distinct and thus for some 0 ≤ i < j ≤ n we have hi = hj. Therefore, hj−i = e and we conclude that o(h) is finite and o(h) is at most ] < h >. This concludes the proof. ¤ Corollary 1.2.2. If h has a finite order n then < h >= {e, h,... , hn−1 } and consists of precisely n elements (that is, there are no repetitions in this list.) It is ease to check that if {Hα ; α ∈ J} is a non-empty set of subgroups of G then ∩α∈J Hα is a subgroup as well. Let {gα : α ∈ I} be a set consisting of elements of G (here I is some index set). We denote by < {gα : α ∈ I} > the minimal subgroup of G containing {gα : α ∈ I}. It is clearly the intersection of all subgroups of G containing {gα : α ∈ I}. Lemma 1.2.3. The subgroup < {gα : α ∈ I} > is the set of all finite expressions h1 · · · ht where each hi is some gα or gα−1. Proof. Clearly < {gα : α ∈ I} > contains each gα hence all the expressions h1 · · · ht where each hi is some gα or gα−1. Thus, it is enough to show that the set of all finite expressions h1 · · · ht , where  GROUP THEORY 3 each hi is some gα or gα−1 , is a subgroup. Clearly e (equal to the empty product, or to gα gα−1 if you prefer) is in it. Also, from the definition it is clear that it is closed under multiplication. Finally, since (h1 · · · ht )−1 = h−1 −1 t · · · h1 it is also closed under taking inverses. ¤ We call < {gα : α ∈ I} > the subgroup of G generated by {gα : α ∈ I}; if it is equal to G, we say that {gα : α ∈ I} are generators for G. The Cayley graph. Suppose that {gα : α ∈ I} are generators for G. We define an oriented graph taking as vertices the elements of G and taking for every g ∈ G an oriented edge from g to ggα. If we forget the orientation, the property of {gα : α ∈ I} being a set of generators is equivalent to the graph being connected. Suppose that the set of generators consists of n elements. Then, by definition, from every vertex we have n vertices emanating and also n arriving. We see therefore that all Cayley graphs are regular graphs. This, in turn, gives a systematic way of constructing regular graphs. Suppose we take as group the symmetric group (see below) Sn and the transpositions as generators. One can think as a permutation as being performed in practice by successively swapping the places of two elements. Thus, in the Cayley graph, the distance between a permutation and the identity (the distance is defined as the minimal length of a path between the two vertices) is the minimal way to write a permutation as a product of transpositions, and could be thought of as a certain measure of the complexity of a transposition. The figure below gives the Cayley graph of S3 with respect to the generating set of transpositions. It is a 3-regular oriented graph and a 6 regular graph. B eR c (12) (23) (13)(13) (12) (23) ¢ i µ % (12) b (13) B (23) R c Q (23) (12) (23) (13) (13) (12)(12) (23) (13) (13) (12) (23) µ ¢% # µ* (123) (132)  GROUP THEORY 4 2. Main examples 2.1. Z, Z/nZ and (Z/nZ)×. The set of integers Z = {... , −2, −1, 0, 1, 2, 3,... }, with the addition Dummit & Foote operation, is an infinite abelian group. It is cyclic; both 1 and −1 are generators. §§0.1 - 0.3 The group Z/nZ of integers modulo n, {0, 1, 2,... , n − 1}, with addition modulo n, is a finite abelian group. The group Z/nZ is a cyclic group with generator 1. In fact (see the section on cyclic groups), an element x generates Z/nZ if and only if (x, n) = 1. Consider (Z/nZ)× = {a ∈ Z/nZ : (a, n) = 1} with multiplication. It is a group whose order is denoted by φ(n) (the function n 7→ φ(n) is call Euler’s phi function). To see it is a group, note that multiplication is associative and if (a, n) = 1, (b, n) = 1 then also (ab, n) = 1 (thus, we do indeed get an operation on Z/nZ× ). The congruence class 1 is the identity and the existence of inverse follows from finiteness: given a ∈ Z/nZ× consider the function x 7→ ax. It is injective: if ax = ay then a(x − y) = 0 (mod n), that is (using the same letters to denote integers in these congruence classes) n|a(x − y). Since (a, n) = 1 we conclude that n|(x − y) that is, x = y in Z/nZ. It follows that x 7→ ax is also surjective and thus there is an element x such that ax = 1. 2.2. The dihedral group D2n. Let n ≥ 3. Consider the linear transformations of the plane that Dummit & Foote take a regular polygon with n sides, symmetric about zero, unto itself. One easily sees that every such §1.2 symmetry is determine by its action of the vertices 1, 2 (thought of as vectors, they form a basis) and that it takes these vertices to the vertices i, i + 1 or i + 1, i, where 1 ≤ i ≤ n (and the labels of the vertices are read modulo n). One concludes that every such symmetry is of the form y a xb for suitable and unique a ∈ {0, 1}, b ∈ {1,... , n}, where y is the reflection fixing 1 (so takes n, 2 to 2, n) and x is the rotation taking 1, 2 to 2, 3. One finds that y 2 = e = xn and that yxy = x−1. All other relations are consequences of these. y n 1 2 x 3 Figure 2.1. Symmetries of a regular Polygon with n vertices. The Dihedral group is thus a group of order 2n generated by a reflection y and a rotation x satisfying y 2 = xn = xyxy = e. This makes sense also for n = 1, 2. end of second lecture  GROUP THEORY 5 2.3. The symmetric group Sn. Consider the set Sn consisting of all injective (hence bijective) Dummit & Foote functions, called permutations, §1.3 σ : {1, 2,... , n} −→ {1, 2,... , n}. We define m(σ, τ ) = σ ◦ τ. This makes Sn into a group, whose identity e is the identity function e(i) = i, ∀i. We may describe the elements of Sn in the form of a table: µ ¶ 1 2... n. i1 i2... in This defines a permutation σ by the rule σ(a) = ia. Another device is to use the notation (i1 i2... is ), where the ij are distinct elements of {1, 2,... , n}. This defines a permutation σ according to the following convention: σ(ia ) = ia+1 for 1 ≤ a < s, σ(is ) = i1 , and for any other element x of {1, 2,... , n} we let σ(x) = x. Such a permutation is called a cycle. One can easily prove the following facts: (1) Disjoint cycles commute. (2) Every permutation is a product of disjoint cycles (uniquely up to permuting the cycles). (3) The order of (i1 i2... is ) is s. (4) If σ1 ,... , σt are disjoint cycles of orders r1 ,... , rt then the order of σ1 ◦ · · · ◦ σt is the least common multiple of r1 ,... , rt. (5) The symmetric group has order n!. 2.3.1. The sign of a permutation, and realizing permutations as linear transformations. Dummit & Foote §3.5 Lemma 2.3.1. Let n ≥ 2. Let Sn be the group of permutations of {1, 2,... , n}. There exists a surjective homomorphism3 of groups sgn : Sn −→ {±1} (called the ‘sign’). It has the property that for every i 6= j, sgn( (ij) ) = −1. Proof. Consider the polynomial in n-variables4 Y p(x1 ,... , xn ) = (xi − xj ). i, D2 =< y, x2 >, D3 =< xy, x2 > and H1 = f (D1 ) = {(1, 1), ((ab), (AB))}, H2 = f (D2 ) = {(1, 1), (1, (AB))}, H3 = f (D3 ) = {(1, 1), ((ab), 1)}. end of lecture 9 Example 11.0.9. Let F be a field and let N = {diag[f, f,... , f ] : f ∈ F× } be the set of diagonal matrices with the same non-zero element in each diagonal entry. We proved in an assignment that N = Z(GLn (F)) and is therefore a normal subgroup. The quotient group PGLn (F) := GLn (F)/N is called the projective linear group. Let Pn−1 (F) be the set of equivalence classes of non-zero vectors in Fn under the equivalence v ∼ w if there is f ∈ F∗ such that f v = w; that is, the set of lines through the origin. The importance of the group PGLn (F) is that it acts as automorphisms on the projective n − 1-space Pn−1 (F). Let π : GLn (F) −→ PGLn (F) be the canonical homomorphism. The function det : GLn (F) −→ F∗  GROUP THEORY 22 is a group homomorphism, whose kernel, the matrices with determinant one, is denoted SLn (F). Consider the image of SLn (F) in PGLn (F); it is denoted PSLn (F). We want to analyze it and the quotient PGLn (F)/PSLn (F). The group PSLn (F) is equal to π(SLn (F)) = π(SLn (F)N ) and is isomorphic to SLn (F)N/N ∼ = SLn (F)/SLn (F) ∩ N = SLn (F)/µn (F), where by µN (F) we mean the group {f ∈ F× : f n = 1} (where we identify f with diag[f, f,... , f ]). Therefore, PSLn (F) ∼ = SLn (F)/µn (F). The group PGLn (F)/PSLn (F) is isomorphic to (GLn (F)/N )/(SLn (F)N/N ) ∼= GLn (F)/SLn (F)N. ×(n) × n × Let F be the subgroup of F consisting of the elements {f : f ∈ F }. Under the isomorphism GLn (F)/SLn (F) ∼ = F× the subgroup SLn (F)N corresponds to F×(n). We conclude that PGLn (F)/PSLn (F) ∼ = F× /F×(n). 12. The lattice of subgroups of a group Let G be a group. Consider the set Λ(G) of all subgroups of G. Define an order on this set by A ≤ B if A is a subgroup of B. This relation is transitive and A ≤ B ≤ A implies A = B. That is, the relation is really an order. The set Λ(G) is a lattice. Every two elements A, B have a minimum A ∩ B (that is if C ≤ A, C ≤ B then C ≤ A ∩ B) and a maximum < A, B > - the subgroup generated by A and B (that is C ≥ A, C ≥ B then C ≥< A, B >). If A ∈ Λ(G) then let ΛA (G) to be the set of all elements in Λ(G) that are greater or equal to A. It is a lattice in its own right. We have the property that if N C G then ΛN (G) ∼= Λ(G/N ) as lattices. Here is the lattice of subgroups of D8. Normal subgroup are boxed. VVVV D8 L LL VVVV LL LL VVVVVVVV LL VVVV L VVV < y, x2 > < yx, x2 > subgroups of order 4 UUUUii TTTT ttt t ii iiiii UUUUUUU TTTT TTTT t tt iiiiiii UUUU UU TTTT tiiit i i UUUUU TTT 2 < y > < yx > 2 < yx3 > subgroups of order 2 eeeeedddddddddddddd < yx > r rr hh hhhh eeee e r hhh eeeee ddddddd r r rrr hhhhhheheheeedededededededddddddd h h e d ee dd rherhderhedhedhedhedededededdddd {e} d How to prove that these are all the subgroups? Note that every proper subgroup has order 2 or 4 by Lagrange’s theorem. If it is cyclic then it must be one of the above, because the diagram certainly contains all cyclic subgroups. Else, it can only be of order 4 and every element different from e has order 2. It is east to verify that any two distinct elements of order 2 generate one of the subgroups we have listed. end of lecture 10  GROUP THEORY 23 Part 3. Group Actions on Sets 13. Basic definitions Let G be a group and let S be a non-empty set. We say that G acts on S if we are given a function Dummit & Foote §4.1 G × S −→ S, (g, s) 7−→ g ? s, such that; (i) e ? s = s for all s ∈ S; (ii) (g1 g2 ) ? s = g1 ? (g2 ? s) for all g1 , g2 ∈ G and s ∈ S. Given an action of G on S we can define the following sets. Let s ∈ S. Define the orbit of s Orb(s) = {g ? s : g ∈ G}. Note that Orb(s) is a subset of S, equal to all the images of the element s under the action of the elements of the group G. We also define the stabilizer of s to be Stab(s) = {g ∈ G : g ? s = s}. Note that Stab(s) is a subset of G. In fact, it is a subgroup, as the next Lemma states. One should think of every element of the group as becoming a symmetry of the set S. We’ll make more precise later. For now, we just note that every element g ∈ G defines a function S −→ S by s 7→ gs. This function, we’ll see later, is bijective. 14. Basic properties Lemma 14.0.10. (1) Let s1 , s2 ∈ S. We say that s1 is related to s2 , i.e., s1 ∼ s2 , if there exists g ∈ G such that g ? s1 = s2. This is an equivalence relation. The equivalence class of s1 is its orbit Orb(s1 ). (2) Let s ∈ S. The set Stab(s) is a subgroup of G. (3) Suppose that both G and S have finitely many elements. Then |G| |Orb(s)| =. |Stab(s)| Proof. (1) We need to show reflexive, symmetric and transitive. First, we have e ? s = s and hence s ∼ s, meaning the relation is reflexive. Second, if s1 ∼ s2 then for a suitable g ∈ G we  GROUP THEORY 24 have g ? s1 = s2. Therefore g −1 ? (g ? s1 ) = g −1 ? s2 ⇒ (g −1 g) ? s1 = g −1 ? s2 ⇒ e ? s1 = g −1 ? s2 ⇒ s1 = g −1 ? s2 ⇒ g −1 ? s2 = s1 ⇒ s2 ∼ s1. It remains to show transitive. If s1 ∼ s2 and s2 ∼ s3 then for suitable g1 , g2 ∈ G we have g1 ? s1 = s2 , g 2 ? s 2 = s3. Therefore, (g2 g1 ) ? s1 = g2 ? (g1 ? s1 ) = g2 ? s2 = s3 , and hence s1 ∼ s3. Moreover, by the very definition the equivalence class of an element s1 of S is all the elements of the form g ? s1 for some g ∈ G, namely, Orb(s1 ). (2) Let H = Stab(s). We have to show that: (i) e ∈ H; (2) If g1 , g2 ∈ H then g1 g2 ∈ H; (iii) If g ∈ H then g −1 ∈ H. First, by definition of group action we have e ? s = s. Therefore e ∈ H. Next suppose that g1 , g2 ∈ H, i.e., g1 ? s = s, g2 ? s = s. Then (g1 g2 ) ? s = g1 ? (g2 ? s) = g1 ? s = s. Thus, g1 g2 ∈ H. Finally, if g ∈ H then g ? s = s and so g −1 ? (g ? s) = g −1 ? s ⇒ (g −1 g) ? s = g −1 ? s ⇒ e ? s = g −1 ? s ⇒ s = g −1 ? s, and therefore g −1 ∈ H. (3) We claim that there exists a bijection between the left cosets of H and the orbit of s. If we show that, then by Lagrange’s theorem, |Orb(s)| = no. of left cosets of H = index of H = |G|/|H|. Define a function φ {left cosets of H} −→ Orb(s), by φ(gH) = g ? s. We claim that φ is a well defined bijection. First  GROUP THEORY 25 Well-defined: Suppose that g1 H = g2 H. We need to show that the rule φ would give the same result whether we take the representative g1 or the representative g2 to the coset, that is, we need to show g1 ? s = g2 ? s. Note that g1−1 g2 ∈ H, i.e., (g1−1 g2 ) ? s = s. We get g1 ? s = g1 ? ((g1−1 g2 ) ? s) = (g1 (g1−1 g2 )) ? s = g2 ? s. φ is surjective: Let t ∈ Orb(s) then t = g ? s for some g ∈ G. Thus, φ(gH) = g ? s = t, and we get that φ is surjective. φ is injective: Suppose that φ(g1 H) = φ(g2 H). We need to show that g1 H = g2 H. Indeed, φ(g1 H) = φ(g2 H) ⇒ g1 ? s = g2 ? s ⇒ g2−1 ? (g1 ? s) = g2−1 ? (g2 ? s) ⇒ (g2−1 g1 ) ? s = (g2−1 g2 ) ? s ⇒ (g2−1 g1 ) ? s = e ? s ⇒ (g2−1 g1 ) ? s = s ⇒ g2−1 g1 ∈ Stab(s) = H ⇒ g1 H = g2 H. ¤ Corollary 14.0.11. The set S is a disjoint union of orbits. Proof. The orbits are the equivalence classes of the equivalence relation ∼ defined in Lemma 14.0.10. Any equivalence relation partitions the set into disjoint equivalence classes. ¤ We have in fact seen that every orbit is in bijection with the cosets of some group. If H is any subgroup of G let us use the notation G/H for its cosets (note though that if H is not normal this is not a group, but just a set). We saw that if s ∈ S then there is a natural bijection G/Stab(s) ↔ Orb(s). Thus, the picture of S is as follows S a Orb(a) = G/Stab(a) b Orb(b) = G/Stab(b) c Orb(c) = G/Stab(c) Figure 14.1. The set decomposes into orbits; each is the cosets of a subgroup.  GROUP THEORY 26 15. Some examples Example 15.0.12. The group Sn acts on the set {1, 2,... , n}. The action is transitive, i.e., there is only one orbit. The stabilizer of i is S{1,2,...,i−1,i+1,...,n} ∼ = Sn−1. Example 15.0.13. The group GLn (F) acts on Fn , and also Fn − {0}. The action is transitive on Fn − {0} and has two orbits on Fn. The stabilizer of 0 is of course GLn (F); the stabilizer of a non-zero vector v1 can be written in a basis w1 , w2 ,... , wn with w1 = v1 as the matrices of the shape   1 ∗... ∗ 0 ∗... ∗   ...... .......  0 ∗... ∗ Example 15.0.14. Let H be a subgroup of G then we have an action H × G −→ G, (h, g) 7→ hg. In this example, H is “the group” and G is “the set”. Here the orbits are right cosets of H and ` ` P the stabilizers are trivial. Since G = Orb(gi ) = Hgi we conclude that |G| = i |Orb(gi )| = P P i |H|/|Stab(gi )| = i |H| and therefore that |H| | |G| and that [G : H], the number of cosets, is |G|/|H|. We have recovered Lagrange’s theorem. Example 15.0.15. Let H be a subgroup of G. Let S = {gH : g ∈ G} be the set of left cosets of H in G. Then we have an action G × S −→ S, (a, bH) 7→ abH. Here there is a unique orbit (we say G acts transitively). The stabilizer of gH is the subgroup gHg −1. Example 15.0.16. Let G = R/2πZ. It acts on the sphere by rotations: an element θ ∈ G rotates the sphere by angle θ around the north-south axes. The orbits are latitude lines and the stabilizers of every point is trivial, except for the poles whose stabilizer is G. See Figure 15.1. θ Figure 15.1. Action on the sphere by rotation.  GROUP THEORY 27 Example 15.0.17. Let G be the dihedral group D16. Recall that G is the group of symmetries of a regular octagon in the plane. G = {e, x, x2 ,... , x7 , y, yx, yx2 ,... , yx7 }, where x is the rotation clockwise by angle 2π/8 and y is the reflection through the y-axis. We have the relations x8 = y 2 = e, yxy = x−1. We let S be the set of colorings of the octagon ( = necklaces laid on the table) having 4 red vertices (rubies) and 4 green vertices (sapphires). The group G acts on S by its action on the octagon. For example, the coloring s0 in Figure 15.2 is certainly preserved under x2 and under y. Therefore, the stabilizer of s0 contains at least the set of eight elements (15.1) {e, x2 , x4 , x6 , y, yx2 , yx4 , yx6 }. Remember that the stabilizer is a subgroup and, by Lagrange’s theorem, of order dividing 16 = |G|. y x Figure 15.2. A necklace with 4 rubies and 4 sapphires. On the other hand, Stab(s0 ) 6= G because x 6∈ Stab(s0 ). It follows that the stabilizer has exactly 8 elements and is equal to the set in (15.1). According to Lemma 14.0.10 the orbit of s0 is in bijection with the left cosets of Stab(s0 ) = {e, x2 , x4 , x6 , y, yx2 , yx4 , yx6 }. By Lagrange’s theorem there are two cosets. For example, Stab(s0 ) and xStab(s0 ) are distinct cosets. The proof of Lemma 14.0.10 tells us how to find the orbit: it is the set {s0 , xs0 }, portrayed in Figure 15.3. Figure 15.3. The orbit of the necklace. end of lecture 11  GROUP THEORY 28 16. Cayley’s theorem Dummit & Foote §4.2 Theorem 16.0.18. Every finite group of order n is isomorphic to a subgroup of Sn. We first prove a lemma that puts group actions in a different context. Let A be a finite set. Let ΣA be the set of bijective functions A −→ A. Then, ΣA is a group. In fact, if we let s1 ,... , sn be the elements of A, we can identify bijective functions A −→ A with permutations of {1,... , n} and we see that ΣA ∼= Sn. Lemma 16.0.19. To give an action of a group G on a set A is equivalent to giving a homomorphism Dummit & Foote §4.1 G −→ ΣA. The kernel of this homomorphism is ∩a∈A Stab(a). Proof. An element g define a function φg : A −→ A by φg (a) = ga. We have φe being the identity function. Note that φh φg (a) = φh (ga) = hga = φhg (a) for every a and hence φh φg = φhg. In particular, φg φg−1 = φg−1 φg = Id. This shows that every φg is a bijection and the map Ψ Ψ : G −→ ΣA , g 7→ φg , is a homomorphism. (Conversely, given such a homomorphism Ψ, define a group action by g ? a := Ψ(g)(a).) The kernel of this homomorphism is the elements g such that φg is the identity, i.e., φg (a) = a for all a ∈ A. That is, g ∈ Stab(a) for every a ∈ A. The set of such elements g is just ∩a∈A Stab(a). ¤ Proof. (of Theorem) Consider the action of G on itself by multiplication (Example 15.0.14), (g, g 0 ) 7→ gg 0. Recall that all stabilizers are trivial. Thus this action gives an injective homomorphism G −→ ΣG ∼ = Sn , where n = |G|. ¤ 16.1. Applications to construction of normal subgroups. Let G be a group and H a subgroup of finite index n. Consider the action of G on the set of cosets G/H of H and the resulting homomorphism Ψ : G −→ ΣG/H ∼ = Σn , where n = [G : H]. The kernel K of Ψ is ∩a∈G/H Stab(a) = ∩g∈G Stab(gH) = ∩g∈G gHg −1. Being a kernel of a homomorphism, K is normal in G and is contained in H. Furthermore, since the resulting homomorphism G/K −→ Sn is injective we get that |G/K| = [G : K] divides [G : H]! = |Sn |. In particular, we conclude that every subgroup H of G contains a subgroup K which is normal in G and of index at most [G : H]!. Thus, for example, a simple infinite group has no subgroups of finite index. In fact, the formula K = ∩g∈G gHg −1 shows that K is the maximal subgroup of H which is normal in G. Indeed, if K 0 C G, K 0 < H then K = gKg −1 ⊂ gHg −1 and we see that K 0 ⊆ K.  GROUP THEORY 29 17. The Cauchy-Frobenius formula 17.1. A formula for the number of orbits. Theorem 17.1.1. (CFF) Let G be a finite group acting on a finite set S. Let N be the number of Rotman, op. cit., §3, Thm. 3.26 orbits of G in S. Define I(g) = |{s ∈ S : g ? s = s}| 10 (the number of elements of S fixed by the action of g). Then 1 X (17.1) N= I(g). |G| g∈G Remark 17.1.2. If N = 1 we say that G acts transitively on S. It means exactly that: For every s1 , s2 ∈ S there exists g ∈ G such that g ? s1 = s2. Proof. We define a function ( 1 g?s=s T : G × S −→ {0, 1}, T (g, s) =. 0 g ? s 6= s Note that for a fixed g ∈ G we have X I(g) = T (g, s), s∈S and that for a fixed s ∈ S we have X |Stab(s)| = T (g, s). g∈G Let us fix representatives s1 ,... , sN for the N disjoint orbits of G in S. Now, à !   X X X X X I(g) = T (g, s) =  T (g, s) g∈G g∈G s∈S s∈S g∈G X X |G| = |Stab(s)| = |Orb(s)| s∈S s∈S N X X X N X |G| |G| = = i=1 s∈Orb(si ) |Orb(s)| i=1 |Orb(si )| s∈Orb(si ) N X N X |G| = · |Orb(si )| = |G| i=1 |Orb(si )| i=1 = N · |G|. ¤ Corollary 17.1.3. Let G be a finite group acting transitively on a finite S. Suppose that |S| > 1. Then there exists g ∈ G without fixed points. 10The sum appearing in the formula means just that: If you write G = {g ,... , g } then P Pn P P 1 n g∈G I(g) is i=1 I(gi ) = I(g1 ) + I(g2 ) + · · · + I(gn ). The double summation g∈G s∈S T (g, s) appearing in the proof means that if we write S = {s1 ,... , sm } then the double sum is T (g1 , s1 ) + T (g1 , s2 ) + · · · + T (g1 , sm ) + T (g2 , s1 ) + T (g2 , s2 ) + · · · + T (g2 , sm ) + · · · + T (gn , s1 ) + T (gn , s2 ) + · · · + T (gn , sm ).  GROUP THEORY 30 Proof. By contradiction. Suppose that every g ∈ G has a fixed point in S. That is, suppose that for every g ∈ G we have I(g) ≥ 1. Since I(e) = |S| > 1 we have that X I(g) > |G|. g∈G By Cauchy-Frobenius formula, the number of orbits N is greater than 1. Contradiction. ¤ end of lecture 12 17.2. Applications to combinatorics. Example 17.2.1. How many roulettes with 11 wedges painted 2 blue, 2 green and 7 red are there when we allow rotations? Let S be the set of painted roulettes. Let us enumerate the sectors of a roulette by the numbers µ ¶µ ¶ 11 9 1,... , 11. The set S is a set of = 1980 elements (choose which 2 are blue, and then choose 2 2 out of the nine left which 2 are green). Let G be the group Z/11Z. It acts on S by rotations. The element 1 rotates a painted roulette by angle 2π/11 anti-clockwise. The element n rotates a painted roulette by angle 2nπ/11 anti-clockwise. We are interested in N – the number of orbits for this action. We use CFF. The identity element always fixes the whole set. Thus I(0) = 1980. We claim that if 1 ≤ i ≤ 10 then i doesn’t fix any element of S. We use the following lemma: Lemma 17.2.2. Let G be a finite group of prime order p. Let g 6= e be an element of G. Then hgi = G. That is, the group G is cyclic (hence commutative), generated by any non-trivial element. Proof. The subgroup hgi has more than one element because e, g ∈ hgi. By Lagrange’s theorem | hgi | divides |G| = p. Thus, | hgi | = p and therefore hgi = G. ¤ Suppose that 1 ≤ i ≤ 10 and i fixes s. Then so does hii = Z/11Z (the stabilizer is a subgroup). But any coloring fixed under rotation by 1 must be single colored! Contradiction. Applying CFF we get 10 1 X 1 N= I(n) = · 1980 = 180. 11 n=0 11 Example 17.2.3. How many roulettes with 12 wedges painted 2 blue, 2 green and 8 red are there when we allow rotations? Let S be the set of painted roulettes. Let us enumerate the sectors of a roulette by the numbers µ ¶µ ¶ 12 10 1,... , 12. The set S is a set of = 2970 elements (choose which 2 are blue, and then 2 2 choose out of the ten left which 2 are green).  GROUP THEORY 31 Let G be the group Z/12Z. It acts on S by rotations. The element 1 rotates a painted roulette by angle 2π/12 anti-clockwise. The element n rotates a painted roulette by angle 2nπ/12 anti-clockwise. We are interested in N – the number of orbits for this action. We use CFF. The identity element always fixes the whole set. Thus I(0) = 2970. We claim that if 1 ≤ i ≤ 11 and i 6= 6 then i doesn’t fix any element of S. Indeed, suppose that i fixes a painted roulette. Say in that roulette the r-th sector is blue. Then so must be the i + r sector (because the r-th sector goes under the action of i to the r + i-th sector). Therefore so must be the r + 2i sector. But there are only 2 blue sectors! The only possibility is that the r + 2i sector is the same as the r sector, namely, i = 6. If i is equal to 6 and we enumerate the sectors of a roulette by the numbers 1,... , 12 we may write i as the permutation (1 7)(2 8)(3 9)(4 10)(5 11)(6 12). In any coloring fixed by i = 6 the colors of the pairs (1 7), (2 8), (3 9), (4 10), (5 11) and (6 12) must be the same. We may choose one pair for blue, one pair for green. The rest would be red. Thus there are 30 = 6 · 5 possible choices. We summarize: element g I(g) 0 2970 i 6= 6 0 i=6 30 Applying CFF we get that there are 1 N= (2970 + 30) = 250 12 different roulettes. Example 17.2.4. In this example S is the set of necklaces made of four rubies and four sapphires laid on the table. We ask how many necklaces there are when we allow rotations and flipping-over. We may talk of S as the colorings of a regular octagon, four vertices are green and four are red. The group G = D16 acts on S and we are interested in the number of orbits for the group G. The results are the following element g I(g) e 70 x, x3 , x5 , x7 0 x2 , x6 2 x4 6 yxi for i = 0,... , 7 6 We explain how the entries in the table are obtained: µ ¶ 8 The identity always fixes the whole set S. The number of elements in S is = 70 (chossing 4 which 4 would be green). The element x cannot fix any coloring, because any coloring fixed by x must have all sections of 2 the same color (because x = (1 2 3 4 5 6 7 8)). If xr fixes a coloring s0 so does (xr )r = x(r ) because  GROUP THEORY 32 the stabilizer is a subgroup. Apply that for r = 3, 5, 7 to see that if xr fixes a coloring so does x , which is impossible. 11 Now, x2 written as a permutation is (1 3 5 7)(2 4 6 8). We see that if, say 1 is green so are 3, 5, 7 and the rest must be red. That is, all the freedom we have is to choose whether the cycle (1 3 5 7) is green or red. This gives us two colorings fixed by x2. The same rational applies to x6 = (8 6 4 2)(7 5 3 1). Consider now x4. It may written in permutation notation as (1 5)(2 6)(3 7)(4 8). In any coloring µ ¶ 4 4 fixed by x each of the cycles (1 5)(2 6)(3 7) and (4 8) must be single colored. There are thus =6 2 possibilities (Choosing which 2 out of the four cycles would be green). It remains to deal with the elements yxi. We recall that these are all reflections. There are two kinds of reflections. One may be written using permutation notation as (i1 i2 )(i3 i4 )(i5 i6 ) (with the other two vertices being fixed. For example y = (2 8)(3 7)(4 6) is of this form). The other kind is of the form (i1 i2 )(i3 i4 )(i5 i6 )(i7 i8 ). (For example yx = (1 8)(2 7)(3 6)(4 5) is of this sort). Whatever is the case, one uses similar reasoning to deduce that there are 6 colorings preserved by a reflection. One needs only apply CFF to get that there are 1 N= (70 + 2 · 2 + 6 + 8 · 6) = 8 16 distinct necklaces. 17.3. The game of 16 squares. Sam Loyd (1841-1911) was America’s greatest puzzle expert and invented thousands of ingenious and tremendously popular puzzles. In this game, we are given a 4 × 4 box with 15 squares numbered 1, 2,... , 15 and one free spot. At every step one is allowed to move an adjacent square into the vacant spot. For example 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8 7→ 7→ 7→ 7→ 9 10 11 12 9 10 11 12 9 10 12 9 10 12 9 14 10 12 13 14 15 13 14 15 13 14 11 15 13 14 11 15 13 11 15 Can one pass from the original position to the position below? 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 It turns out that the answer is no. Can you prove it? Apparently, the puzzle was originally marketed with the tiles in the impossible position with the challenge to rearrange them into the initial position! 11x(32 ) = x9 = x because x8 = e, etc.  GROUP THEORY 33 Figure 17.1. Loyd’s 14 − 15 puzzle. 17.4. Rubik’s cube. 12 In the case of the Rubik cube there is a group G acting on the cube. The group G is generated by 6 basic moves a, b, c, d, e, f (each is a rotation of a certain “third of the cube”) and could be thought of as a subgroup of the symmetric group on 54 = 9 × 6 letters. It is called the cube group. The order of the Cube Group is 227 · 314 · 53 · 72 · 11 = 43, 252, 003, 274, 489, 856, 000 One is usually interested in solving the cube. Namely, reverting it to its original position. Since the current position was gotten by applying an element τ of G, in group theoretic terms we attempt to find an algorithm of writing every G in terms of the generators a, b, c, d, e, f since then also τ −1 will have such an expression, which is nothing else than a series of moves that return the cube to its original position. It is natural do deal with the set of generators a±1 , b±1 ,... , f ±1 (why do 3 times a when you can do a−1 ??). A common question is what is the maximal number of basic operations that may be required to return a cube to its original position. Otherwise said, what is the diameter of the Cayley graph? But more than that, is there a simple algorithm of finding for every element of G an expression in terms of the generators? Now, since the Cayley graph of G has 12 edges emanating from each vertex (and is connected by definition of the cube group) it follows that to reach all positions one is forced to allow at least log12 |G| ∼ 18.2, thus at least 19, moves. Figure 17.2. The Rubik Cube. 12Also known as the Hungarian cube.  GROUP THEORY 34 Part 4. The Symmetric Group Dummit & Foote §4.3 18. Conjugacy classes Let σ ∈ Sn. We write σ as a product of disjoint cycles: σ = σ1 σ2 · · · σr. Since disjoint cycles commute, the order does not matter and we may assume that the length of the cycles is non-decreasing. Namely, if we let |(i1 i2... it )| = t (we shall call it the length of the cycle; it is equal to its order as an element of Sn ), then |σ1 | ≤ |σ2 | ≤ · · · ≤ |σr |. We may also allow cycles of length 1 (they simple stand for the identity permutation) and then we find that n = |σ1 | + |σ2 | + · · · + |σr |. We therefore get a partition p(σ) of the number n, that is, a set of non-decreasing positive integers 1 ≤ a1 ≤ a2 ≤ · · · ≤ ar such that n = a1 + a2 + · · · + ar. Note that every partition is obtained from a suitable σ. Lemma 18.0.1. Two permutations, σ and ρ, are conjugate (namely there is a τ such that τ στ −1 = ρ) if and only if p(σ) = p(ρ). Proof. Recall the formula we used before, if σ(i) = j then (τ στ −1 )(τ (i)) = τ (j). This implies that for every cycle (i1 i2... it ) we have τ (i1 i2... it )τ −1 = (τ (i1 ) τ (i2 )... τ (it )). In particular, since τ στ −1 = (τ σ1 τ −1 )(τ σ2 τ −1 ) · · · (τ σr τ −1 ), a product of disjoint cycles, we get that p(σ) = p(τ στ −1 ). Conversely, support that p(σ) = p(ρ). Say σ = σ1 σ2... σr = (i11... i1t(1) )(i21... i2t(2) )... (ir1... irt(r) ), and ρ = ρ1 ρ2... ρr = (j11... jt(1) 1 )(j12... jt(2) 2 )... (j1r... jt(r) r ). Define τ by τ (iab ) = jba , then τ στ −1 = ρ. ¤ Corollary 18.0.2. Let p(n) be the number of partitions of n.13 There are p(n) conjugacy classes in Sn. 13Since 2 = 2 = 1+1, 3 = 3 = 1+2 = 1+1+1, 4 = 4 = 2+2 = 1+3 = 1+1+2 = 1+1+1+1, 5 = 5 = 2+3 = 1+4 = 1+1+3 = 1+2+2 = 1+1+1+2 = 1+1+1+1+1... we get p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, p(5) = 7, p(6) = 11,....  GROUP THEORY 35 Next, we discuss conjugacy classes in An. Note that if σ ∈ An then since An C Sn also τ στ −1 ∈ An. That is, all the Sn -conjugacy classes of elements of An are in An. However, we would like to consider the An -conjugacy classes of elements of An. Lemma 18.0.3. The Sn -conjugacy class of an element σ ∈ An is a disjoint union of [Sn : An CSn (σ)] An -conjugacy classes. In particular, it is one An -conjugacy class if there is an odd permutation commuting with σ and is two An -conjugacy class if there is no odd permutation commuting with σ. In the latter case, the Sn -conjugacy class of σ is the disjoint union of the An -conjugacy class of σ and the An -conjugacy class of τ στ −1 , where τ can be chosen to be any odd permutation. ` Proof. Let A be the Sn -conjugacy class of σ. Write A = α∈J Aα , a disjoint union of An -conjugacy classes. We first note that Sn acts on the set B = {Aα : α ∈ J}. Indeed, if Aα is the An -conjugacy class of σα , and ρ ∈ Sn then define ρAα ρ−1 to be the An -conjugacy class of ρσα ρ−1. This is well defined: if σα0 is another representative for the An -conjugacy class of σα then σα0 = τ σα τ −1 for some τ ∈ An. It follows that ρσα0 ρ−1 = ρτ σα τ −1 ρ−1 = (ρτ ρ−1 )(ρσα ρ−1 )(ρτ ρ−1 )−1 is in the An -conjugacy class of ρσα ρ−1 (because ρτ ρ−1 ∈ An ). The action of Sn is transitive on B. Consider the An -conjugacy class of σ and denote it by A0. The stabilizer of A0 is just An CSn (σ). Indeed, ρA0 ρ−1 = A0 if and only if ρσρ−1 is in the same An -conjugacy class as σ. Namely, if and only if ρσρ−1 = τ στ −1 for some τ ∈ An , equivalently, (τ −1 ρ)σ = σ(τ −1 ρ), that is (τ −1 ρ) ∈ CSn (σ) which is to say that ρ ∈ An CSn (σ). We conclude that the size of B is the length of the orbit of A0 and hence is of size [Sn : An CSn (σ)]. Since [Sn : An ] = 2, we get that [Sn : An CSn (σ)] = 1 or 2, with the latter happening if and only if An ⊇ CSn (σ). That is, if and only if σ does not commute with any odd permutation. Moreover, the orbit consists of the An -conjugacy classes of the elements gσ, g running over a complete set of representatives for the cosets of An CSn (σ) in Sn. ¤ 19. The simplicity of An In this section we prove that An is a simple group for n 6= 4. The cases where n < 4 are trivial; Dummit & Foote for n = 4 we have seen it fails (the Klein 4-group is normal). We shall focus on the case n ≥ 5 and §§4.3, 4.6 prove the theorem inductively. We therefore first consider the case n = 5. We make the following general observation: Lemma 19.0.4. Let N C G then N is a disjoint union of G-conjugacy classes. Proof. Distinct conjugacy classes, being orbits for a group action, are always disjoint. If N is normal and n ∈ N then its conjugacy class {gng −1 : g ∈ G} is contained in N. ¤ Let us list the conjugacy classes of S5 and their sizes.  GROUP THEORY 36 Conjugacy classes in S5 cycle type representative size of conjugacy class order even? 5 (12345) 24 5 X 1+4 (1234) 30 4 × 1+1+3 (123) 20 3 X 1+ 2+ 2 (12)(34) 15 2 X 1+1+1+2 (12) 10 2 × 1 + 1+ 1+ 1+ 1 1 1 1 X 2+ 3 (12)(345) 20 6 × Let τ be a permutation commuting with (12345). Then (12345) = τ (12345)τ −1 = (τ (1) τ (2) τ (3) τ (4) τ (5)) and so τ is the permutation i 7→ i + n for n = τ (1) − 1. In particular, τ = (12345)n−1 and so is an even permutation. We conclude that the S5 -conjugacy class of (12345) breaks into two A5 -conjugacy classes, with representatives (12345), (21345). One checks that (123) commutes with the odd permutation (45). Therefore, the S5 -conjugacy class of (123) is also an A5 -conjugacy class. Similarly, the permutation (12)(34) commutes with the odd permutation (12). Therefore, the S5 -conjugacy class of (12)(34) is also an A5 -conjugacy class. We get the following table for conjugacy classes in A5. Conjugacy classes in A5 cycle type representative size of conjugacy class order 5 (12345) 12 5 5 (21345) 12 5 1+1+3 (123) 20 3 1+ 2+ 2 (12)(34) 15 2 1 + 1+ 1+ 1+ 1 1 1 1 If N C A5 then |N | divides 60 and is the sum of 1 and some of the numbers in (12, 12, 20, 15). One checks that this is impossible unless N = A5. We deduce Lemma 19.0.5. The group A5 is simple. Theorem 19.0.6. The group An is simple for n ≥ 5. Proof. The proof is by induction on n. We may assume that n ≥ 6. Let N be a normal subgroup of An and assume N 6= {1}. First step: There is a permutation ρ ∈ N, ρ 6= 1 and 1 ≤ i ≤ n such that ρ(i) = i. Indeed, let σ ∈ N be a non-trivial permutation and write it as a product of disjoint non-trivial cycles, σ = σ1 σ2... σs , say in decreasing length. Suppose that σ1 is (i1 i2... ir ), where r ≥ 3. Then conjugating by the transposition τ = (i1 i2 )(i5 i6 ), we get that τ στ −1 σ ∈ N , τ στ −1 σ(i1 ) = i1 and if r > 3 τ στ −1 σ(i2 ) = i4 6= i2. If r = 3 then σ = (i1 i2 i3 )(i4... ).... Take τ = (i1 i2 )(i3 i4 ) then τ στ −1 σ(i1 ) = i1 and τ στ −1 σ(i2 ) = τ σ(i4 ) ∈ {i3 , i5 }. Thus, τ στ −1 σ is a permutation of the kind we were seeking.  GROUP THEORY 37 It still remains to consider the case where each σi is a transposition. Then, if σ = (i1 i2 )(i3 i4 ) then σ moves only 4 elements and thus fixes some element and we are done, else σ = (i1 i2 )(i3 i4 )(i5 i6 ).... Let τ = (i1 i2 )(i3 i5 ) then τ στ −1 σ = (i2 i1 )(i5 i4 )(i3 i6 )... (i1 i2 )(i3 i4 )(i5 i6 ) · · · = (i3 i5 )(i4 i6 )... and so is a permutation of the sort we were seeking. Second step: N = An. Consider the subgroups Gi = {σ ∈ An : σ(i) = i}. We note that each Gi is isomorphic to An−1 and hence is simple. By the preceding step, for some i we have that N ∩ Gi is a non-trivial normal subgroup of Gi , hence equal to Gi. Next, note that (12)(34)G1 (12)(34) = G2 and, similarly, all the groups Gi are conjugate in An to each other. It follows that N ⊇< G1 , G2 ,... , Gn >. Now, every element in Sn is a product of (usually not disjoint) transpositions and so every element σ in An is a product of an even number of transpositions, σ = λ1 µ1... λr µr (λi , µi transpositions). Since n > 4 every product λi µi belongs to some Gj and we conclude that < G1 , G2 ,... , Gn >= An. ¤  GROUP THEORY 38 Part 5. p-groups, Cauchy’s and Sylow’s Theorems 20. The class equation Let G be a finite group. G acts on itself by conjugation: g ? h = ghg −1. The class equation is the Dummit & Foote partition of G to orbits obtained this way. The orbits are called in this case conjugacy classes. Note §4.3 that the stabilizer of h ∈ G is CG (h) and so its orbit has length [G : CG (H)]. Note thus the elements with orbit of length 1 are precisely the elements in the center Z(G) of G. We get X |G| (20.1) |G| = |Z(G)| +. |CG (x)| reps.x6∈Z(G) Remark 20.0.7. One can prove that for every n > 0 there are only finitely many finite groups with exactly n conjugacy classes. (One uses the following fact: Given n > 0 and a rational number q there are only finitely many n-tuples (c1 ,... , cn ) of natural numbers such that q = c11 + · · · + c1n.) For example, the only group with one conjugacy class is the trivial group {1}; the only group with two conjugacy classes is Z/2Z; the only groups with 3 conjugacy classes are Z/3Z and S3. 21. p-groups Let p be a prime. A finite group G is called a p-group if its order is a positive power of p. Dummit & Foote §§4.3, 6.1 Lemma 21.0.8. Let G be a finite p group. Then the center of G is not trivial. Proof. We use the class equation 20.1. Note that if x 6∈ Z(G) then CG (x) 6= G and so the integer |G| |CG (x)| is divisible by p. Thus, the left hand side of X |G| |G| − = |Z(G)| |CG (x)| reps.x6∈Z(G) is divisible by p, hence so is the right hand side. In particular |Z(G)| ≥ p. ¤ Theorem 21.0.9. Let G be a finite p group, |G| = pn. (1) For every normal subgroup HC G there is a subgroup KC G such that H < K < G and [K : H] = p. (2) There is a chain of subgroups H0 = {1} < H1 < · · · < Hn = G, such that each Hi C G and |Hi | = pi. Proof. (1) The group G/H is a p group and hence its center is a non-trivial group. Take an r−1 element e 6= x ∈ Z(G/H); its order is pr for some r. Then y = xp has exact order p. Let K 0 =< y >. It is a normal subgroup of G/H of order p (y commutes with any other −1 element). Let K = πH (K 0 ). By the Third Isomorphism Theorem K is a normal subgroup of G, K/H ∼ = K 0 so [K : H] = p. (2) The proof just given shows that every p group has a normal subgroup of p elements. Now apply repeatedly the first part. ¤  GROUP THEORY 39 21.1. Examples of p groups. 21.1.1. Groups of order p. We proved in the assignments that every such group is cyclic, thus iso- morphic to Z/pZ. 21.1.2. Groups of order p2. We shall prove in the assignments that every such group is commuta- tive. It then follows from the structure theorem for finite abelian groups that such a group is either isomorphic to Z/p2 Z or to (Z/pZ)2. 21.1.3. Groups of order p3. First, there are the abelian groups Z/p3 Z, Z/p2 Z × Z/pZ and (Z/pZ)3. We shall prove in the assignments that if G is not abelian then G/Z(G) cannot be cyclic. It follows that Z(G) ∼ = Z/pZ and G/Z(G) ∼ = (Z/pZ)2. One example of such a group is provided by the matrices   1 a b 0 1 c  , 0 0 1 where a, b, c ∈ Fp. Note that if p ≥ 3 then every element in this group is of order p (use (I + N )p = I + N p ), yet the group is non-abelian. (This group, using a terminology to be introduced later, is a semi-direct product (Z/pZ)2 o Z/pZ.) More generally the upper unipotent matrices in GLn (Fp ) are a group of order pn(n−1)/2 in which every element has order p if p ≥ n. Notice that these groups are non-abelian. Getting back to the issue of non-abelian groups of order p3 , one can prove that there is precisely one additional non-abelian group of order p3. It is generated by two elements x, y satisfying: xp = 2 y p = 1, xyx−1 = y 1+p. (This group is a semi-direct product (Z/p2 Z) o Z/pZ.) Dummit & Foote pp. 179-180, 183-184 Let x1 ,... , xd be formal symbols. The free group on x1 ,... , xd is the set of expressions (called “words”) y1... yt , where each yi is a symbol xj or x−1j , taken under the equivalence relation generated by the following basic equivalence: if v, w are words then vxj x−1 j w ∼ vw, vx−1 j xj w ∼ vw. We remark that the empty word is allowed. We define multiplication of two words v, w by putting them together into one word v ? w = vw. One checks that this is well defined on equivalence classes, that it is an associative operation, that the (equivalence class of the) empty word is the identity, and that every element has an inverse: (y1... yt )−1 = yt−1... y1−1. We thus get a group, called the free group of rank d, denoted F (d). It has the following properties: (1) given a group G, and d elements s1 ,... sd in G, there is a unique group homomorphism f : F (d) −→ G such that f (xi ) = si ; (2) if G is a group generated by d elements there is a surjective group homomorphism F (d) −→ G; (3) if w1 ,... wr are words in F (d), let N be the minimal normal subgroup containing all the wi (such exists!). The group F (d)/N is also denoted by < x1 ,... , xd |w1 ,... , wr > and is said to be given by the generators x1 ,... xd and relations w1 ,... , wr. For example, one can prove that Z/nZ ∼ =< x1 |xn1 >, Z2 ∼ =< x1 , x2 |x1 x2 x−1 −1 ∼ 2 3 2 1 x2 > and S3 =< x1 , x2 |x1 , x2 , (x1 x2 ) >. ∼ (4) if d = 1 then F (d) = Z but if d > 1 then F (d) is a non-commutative infinite group.  GROUP THEORY 40 Fix positive integers d, n. The Burnside problem asks if a group generated by d elements in which every element x satisfies xn = 1 is finite. Every such group is a quotient of the following group B(d, n): it is the free group F (d) generated by x1 ,... , xd moded out by the minimal normal subgroup containing the expressions f n where f is an element of F (d). It turns out that in general the answer is negative; B(d, n) is infinite for d ≥ 2, n ≥ 4381, n odd. There are some instances where it is finite: d ≥ 2, n = 2, 3, 4, 6. One can then ask, is there a finite group B0 (d, n) such that every finite group G, generated by d elements and in which f n = 1 for every element f ∈ G, is a quotient of B0 (d, n)? E. Zelmanov, building on the work of many others, proved that the answer is yes. He received the 1994 Fields medal for this. 22. Cauchy’s Theorem One application of group actions is to provide a simple proof of an important theorem in the theory of finite groups. Theorem 22.0.1. (Cauchy) Let G be a finite group of order n and let p be a prime dividing n. Then G has an element of order p. Proof. Let S be the set consisting of p-tuples (g1 ,... , gp ) of elements of G, considered up to cyclic permutations. Thus if T is the set of p-tuples (g1 ,... , gp ) of elements of G, S is the set of orbits for the action of Z/pZ on T by cyclic shifts. One may therefore apply CFF and get np − n |S| = + n. p Note that n 6 ||S|. Now define an action of G on S. Given g ∈ G and (g1 ,... , gp ) ∈ S we define g(g1 ,... , gp ) = (gg1 ,... , ggp ). This is a well defined action. Since the order of G is n, since n 6 ||S|, and since S is a disjoint union of orbits of G, there must be an orbit Orb(s) whose size is not n. However, the size of an orbit is |G|/|Stab(s)|, and we conclude that there must an element (g1 ,... , gp ) in S with a non-trivial stabilizer. This means that for some g ∈ G, such that g 6= e, we have (gg1 ,... , ggp ) is equal to (g1 ,... , gp ) up to a cyclic shift. This means that for some i we have (gg1 ,... , ggp ) = (gi+1 , gi+2 , gi+3 ,... , gp , g1 , g2 ,... , gi ). Therefore, gg1 = gi+1 , g 2 g1 = ggi+1 = g2i+1 ,... , g p g1 = · · · = gpi+1 = g1 (we always read the indices mod p). That is, there exists g 6= e with g p = e. ¤  GROUP THEORY 41 23. Sylow’s Theorems Let G be a finite group and let p be a prime dividing its order. Write |G| = pr m, where (p, m) = 1. Dummit & Foote By a p-subgroup of G we mean a subgroup whose order is a power of p. By a maximal p subgroup of §4.5 G we mean a p-subgroup of G not contained in a strictly larger p-subgroup. Theorem 23.0.2. Every maximal p-subgroup of G has order pr (such a subgroup is called a Sylow p-subgroup) and such a subgroup exists. All Sylow p-subgroups are conjugate to each other. The number np of Sylow p-subgroups satisfies: (i) np |m; (ii) np ≡ 1 (mod p). Remark 23.0.3. To say that P is conjugate to Q means that there is a g ∈ G such that gP g −1 = Q. Recall that the map x 7→ gxg −1 is an automorphism of G. This implies that P and Q are isomorphic as groups. Another consequence is that to say there is a unique p-Sylow subgroup is the same as saying that a p-Sylow is normal. This is often used this way: given a finite group G the first check in ascertaining whether it is simple or not is to check whether the p-Sylow subgroup is unique for some p dividing the order of G. Often one engages in combinatorics of counting how many p-Sylow subgroups can be, trying to conclude there can be only one for a given p and hence getting a normal subgroup. We first prove a lemma that is an easy case of Cauchy’s Theorem 22.0.1: Lemma 23.0.4. Let A be a finite abelian group, let p be a prime dividing the order of A. Then A Dummit & Foote has an element of order p. §3.4 Proof. We prove the result by induction on |A|. Let N be a maximal subgroup of A, distinct from A. If p divides the order of N we are done by induction. Otherwise, let x 6∈ N and let B =< x >. By maximality the subgroup BN is equal to A. On the other hand |BN | = |B| · |N |/|B ∩ N |. Thus, p divides the order of B. That is the order of x is pa for some a and so the order of xa is precisely p. ¤ Proposition 23.0.5. There is a p-subgroup of G of order pr. Proof. We prove the result by induction on the order of G. Assume first that p divides the order of Z(G). Let x be an element of Z(G) of order p and let N =< x >, a normal subgroup. The order of G/N is pr−1 m and by induction it has a p-subgroup H 0 of order pr−1. Let H be the preimage of H 0. It is a subgroup of G such that H/N ∼ = H 0 and thus H has order |H 0 | · |N | = pr. Consider now the case where p does not divide the order of G. Consider the class equation X |G| |G| = |Z(G)| +. |CG (x)| reps.x6∈Z(G) |G| We see that for some x 6∈ Z(G) we have that p does not divide |CG (x)|. Thus, pr divides CG (x). The subgroup CG (x) is a proper subgroup of G because x 6∈ Z(G). Thus, by induction CG (x), and hence G, has a p-subgroup of order pr. ¤ Lemma 23.0.6. Let P be a maximal p-subgroup and Q any p-subgroup then Q ∩ P = Q ∩ NG (P ). Proof. Since P ⊂ NG (P ) also Q ∩ P ⊂ Q ∩ NG (P ). Let H = Q ∩ NG (P ). Then, since P C NG (P ) we have that HP is a subgroup of NG (P ). Its order is |H| · |P |/|H ∩ P | and so a power of p. Since P is a maximal p-subgroup we must have HP = P and thus H ⊂ P. ¤  GROUP THEORY 42 Proof. (Of Theorem) Let P be a Sylow subgroup of G. Such exists by Proposition 23.0.5. Let S = {P1 ,... , Pa } be the set of conjugates of P = P1. That is, the subgroups gP g −1 one gets by letting g vary over G. Note that for a fixed g the map P −→ gP g −1 , x 7→ gxg −1 is a group isomorphism. Thus, every Pi is a Sylow p-subgroup. Our task is to show that every maximal p-subgroup is an element of S and find out properties of a. Let Q be any p-subgroup of G. The subgroup Q acts by conjugation on S. The size of Orb(Pi ) is |Q|/|StabQ (Pi )|. Now StabQ (Pi ) = Q ∩ NG (Pi ) = Q ∩ Pi by Lemma 23.0.6. Thus, the orbit consists of one element if Q ⊂ Pi and is a proper power of p otherwise. Take first Q to be P1. Then, the orbit of P1 has size 1. Since P1 is a maximal p-subgroup it is not contained in any other p-subgroup, thus the size of every other orbit is p. It follows, using that S is a disjoint union of orbits, that a = 1 + tp for some t. Note also that a = |G|/|NG (P )| and thus divides |G|. We now show that all maximal p-subgroups are conjugate. Suppose, to the contrary, that Q is a maximal p-subgroup which is not conjugate to P. Thus, for all i, Q 6= Pi and so Q ∩ Pi is a proper subgroup of Q. It follows then that S is a union of disjoint orbit all having size a proper power of p. Thus, p|a. This is a contradiction. ¤ 23.1. Examples and applications. 23.1.1. p-groups. Every finite p-group is of course the only p-Sylow subgroup (trivial case). 23.1.2. Z/6Z. In every abelian group the p-Sylow subgroups are normal and unique. The 2-Sylow subgroup is < 3 > and the 3-Sylow subgroup is < 2 >. 23.1.3. S3. Consider the symmetric group S3. Its 2-Sylow subgroups are {1, (12)}, {1, (13)}, {1, (23)}. Note that indeed 3|3 = 3!/2 and 3 ≡ 1 (mod 2). It has a unique 3-Sylow subgroup {1, (123), (132}. This is expected since n3 |2 = 3!/3 and n3 ≡ 1 (mod 3) implies n3 = 1. 23.1.4. S4. We want to find the 2-Sylow subgroups. Their number n2 |3 = 24/8 and is congruent to 1 modulo 2. It is thus either 1 or 3. Note that every element of S4 has order 1, 2, 3, 4. The number of elements of order 3 is 8 (the 3-cycles). Thus, we cannot have a unique subgroup of order 8 (it will contain any element of order 2 or 4). We conclude that n2 = 3. One such subgroup is D8 ⊂ S4 ; the rest are conjugates of it. Further, n3 |24/3 and n3 ≡ 1 (mod 3). If n3 = 1 then that unique 3-Sylow would need to contain all 8 element of order 3 but is itself of order 3. Thus, n3 = 4. Remark 23.1.1. A group of order 24 is never simple, though it does not mean that one of the Sylow subgroups is normal, as the example of S4 shows. However, consider the representation of a group G of order 24 on the cosets of P , where P is its 2-Sylow subgroup. It gives us, as we have seen in the past, a normal subgroup of G, contained in P , whose index divides 6 = [G : P ]! and hence is non-trivial.  GROUP THEORY 43 Call this subgroup K. Then, we see that |K| = 4; it is preserved under conjugation hence is a subgroup of all three 2-Sylow subgroups, say P, P 0 , P 00. We have the following picture S4 {{ EEE {{ E P C P0 P 00 CC yy C yy K {e} 23.1.5. Groups of order pq. Let p < q be primes. Let G be a group of order pq. Then nq |p, nq ≡ 1 (mod q). Since p < q we have nq = 1 and the q-Sylow subgroup is normal (in particular, G is never simple). Also, np |q, np ≡ 1 (mod p). Thus, either np = 1, or np = q and the last possibility can happen only for q ≡ 1 (mod p). We conclude that if p 6 |(q − 1) then both the p-Sylow P subgroup and the q-Sylow subgroup Q are normal. Note that the order of P ∩ Q divides both p and q and so is equal to 1. Let x ∈ P, y ∈ Q then [x, y] = (xyx−1 )y −1 = x(yx−1 y −1 ) ∈ P ∩ Q = {1}. Thus, P Q, which is equal to G, is abelian. We shall later see that whenever p|(q − 1) there is a non-abelian group of order pq (in fact, unique up to isomorphism). The case of S3 falls under this. 23.1.6. Groups of order p2 q. Let G be a group of order p2 q, where p and q are distinct primes. We prove that G is not simple: If q < p then np ≡ 1 (mod p) and np |q < p, which implies that np = 1 and the p-Sylow subgroup is normal. Suppose that p < q, then nq ≡ 1 (mod q) and nq |p2 , which implies that nq = 1 or p2. If nq = 1 then the q-Sylow subgroup is normal. Assume that nq = p2. Each pair of the p2 q-Sylow subgroups intersect only at the identity (since q is prime). Hence they account for 1+p2 (q−1) elements. Suppose that there were 2 p-Sylow subgroups. They intersect at most at a subgroup of order p. Thus, they contribute at least 2p2 − p new elements. All together we got at least 1 + p2 (q − 1) + 2p2 − p = p2 q + p2 − p + 1 > p2 q elements. That’s a contradiction and so np = 1; the p-Sylow subgroup is normal. Remark 23.1.2. A theorem of Burnside states that a group of order pa q b with a + b > 1 is not simple. You will prove in the assignments that groups of order pqr (p < q < r primes) are not simple. Note that |A5 | = 60 = 22 · 3 · 5 and A5 is simple. A theorem of Feit and Tompson says that a finite simple group is either of prime order, or of even order. 23.1.7. GLn (F). Let F be a finite field with q elements. The order of GLn (F) is (q n − 1)(q n − q) · · · (q n − q n−1 ) = q (n−1)n/2 (q n − 1)(q n−1 − 1) · · · (q − 1). Thus, a p-Sylow has order q (n−1)n/2. One such subgroup consists of the upper triangular matrices with 1 on the diagonal (the unipotent group):   1 ∗... ∗ 0 1 · · · ∗   ..  .  0 0... 1  GROUP THEORY 44 Part 6. Finitely Generated Abelian Groups, Semi-direct Products and Groups of Low Order 24. The structure theorem for finitely generated abelian groups The structure theorem will proved in the next semester as a corollary of the structure theorem for modules over a principal ideal domain. That same theorem will also yield the Jordan canonical form of a matrix. Theorem 24.0.3. Let G be a finitely generated abelian group. Then there exists a unique non-negative integer r and integers 1 < n1 |n2 |... |nt (t ≥ 0) such that G∼ = Zr × Z/n1 Z × · · · × Z/nt Z. Remark 24.0.4. The integer r is called the rank of G. The subgroup in G that corresponds to Z/n1 Z × · · · × Z/nt Z under such an isomorphism is canonical (independent of the isomorphism). It is the subgroup of G of elements of finite order, also called the torsion subgroup of G and sometime denoted Gtor. On the other hand, the subgroup corresponding to Zr is not canonical and depends very much on the isomorphism. A group is called free abelian group if it is isomorphic to Zr for some r (the case t = 0 in the theorem above). In this case, elements x1 ,... , xr of G that correspond to a basis of Zr are called a basis of G; every element of G has the form a1 x1 + · · · + ar xr for unique integers a1 ,... , ar. Remark 24.0.5. The Chinese remainder theorem gives that if n = pa1 1 · · · pas s , pi distinct primes, then Z/nZ ∼ = Z/pa1 1 Z × · · · × Z/pas s Z. ∼ Zr × Q Z/pbi Z. Thus, one could also write an isomorphism G = i i We shall also prove the following corollary in greater generality next semester. Corollary 24.0.6. Let G, H be two free abelian groups of rank r. Let f : G −→ H be a homomorphism such that G/f (H) is a finite group. There are bases x1 ,... , xr of G and y1 ,... , yr of H and integers 1 ≤ n1 |... |nr such that f (yi ) = ni xi. Example 24.0.7. Let G be a finite abelian p group, |G| = pn. Then G = ∼ Z/pa1 Z × · · · × Z/pas Z 1 s for unique ai satisfying 1 ≤ a1 ≤ · · · ≤ as and a1 + · · · + as = n. It follows that the number of isomorphism groups of finite abelian groups of order pn is p(n) (the partition function of n). 25. Semi-direct products Given two groups B, N we have formed their direct product G = N × B. Identifying B, N with their images {1} × B, N × {1} in G, we find that: (i) G = N B, (ii) N C G, BC G, (iii) N ∩ B = {1}. Conversely, one can easily prove that if G is a group with subgroups B, N such that: (i) G = N B, (ii) N C G, BC G, (iii) N ∩ B = {1}, then G ∼ = N × B. The definition of a semi-direct product relaxes the conditions a little.  GROUP THEORY 45 Definition 25.0.8. Let G be a group and let B, N be subgroups of G such that: (i) G = N B; (ii) N ∩ B = {1}; (iii) N C G. Then we say that G is a semi-direct product of N and B. Let N be any group. Let Aut(N ) be the set of automorphisms of the group N. It is a group in its own right under composition of functions. Let B be another group and φ : B −→ Aut(N ), b 7→ φb be a homomorphism (so φb1 b2 = φb1 ◦ φb2 ). Define a group G = N oφ B as follows: as a set G = N × B, but the group law is defined as (n1 , b1 )(n2 , b2 ) = (n1 · φb1 (n2 ), b1 b2 ). We check associativity: [(n1 , b1 )(n2 , b2 )](n3 , b3 ) = (n1 · φb1 (n2 ), b1 b2 )(n3 , b3 ) = (n1 · φb1 (n2 ) · φb1 b2 (n3 ), b1 b2 b3 ) = (n1 · φb1 (n2 · φb2 (n3 )), b1 b2 b3 ) = (n1 , b1 )(n2 · φb2 (n3 ), b2 b3 ) = (n1 , b1 )[(n2 , b2 )(n3 , b3 )]. The identity is clearly (1N , 1B ). The inverse of (n2 , b2 ) is (φb−1 (n−1 −1 2 ), b2 ). Thus G is a group. The 2 two bijections N −→ G, n 7→ (n, 1); B −→ G, b 7→ (1, b), are group homomorphisms. We identify N and B with their images in G. We claim that G is a semi-direct product of N and B. Indeed, clearly the first two properties of the definition hold. It remains to check that N is normal and it’s enough to verify that B ⊂ NG (N ). According to the calculation above: (1, b)(n, 1)(1, b−1 ) = (φb (n), 1). We now claim that every semi-direct product is obtained this way: Let G be a semi-direct product of N and B. Let φb : N −→ N be the map n 7→ bnb−1. This is an automorphism of N and the map φ : B −→ Aut(N ) is a group homomorphism. We claim that N oφ B ∼ = G. Indeed, define a map (n, b) 7→ nb. It follows from the definition that the map is surjective. It is also bijective since nb = 1 implies that n = b−1 ∈ N ∩ B hence n = 1. It remains to check that this is a group homomorphism, but (n1 · φb1 (n2 ), b1 b2 ) 7→ n1 φb1 (n2 )b1 b2 = n1 b1 n2 b−1 1 b1 b2 = (n1 b1 )(n2 b2 ). Proposition 25.0.9. A semi-direct product N oφ B is the direct product N × B if and only if φ : B −→ Aut(N ) is the trivial homomorphism. Proof. Indeed, that happens iff for all (n1 , b1 ), (n2 , b2 ) we have (n1 φb1 (n2 ), b1 b2 ) = (n1 n2 , b1 b2 ). That is, iff for all b1 , n2 we have φb1 (n2 ) = n2 , which implies φb1 = id for all b1. That is, φ is the trivial homomorphism. ¤  GROUP THEORY 46 Example 25.0.10. The Dihedral group D2n is a semi-direct product. Take N =< x >∼ = Z/nZ and B =< y >∼ = Z/2Z. Then D2n ∼ = Z/nZ oφ Z/2Z with φ1 = −1. 25.1. Application to groups of order pq. We have seen in § 23.1.5 that if p < q and p 6 |(q − 1) then every group of order pq is abelian. Assume therefore that p|(q − 1). Proposition 25.1.1. If p|(q −1) there is a unique non-abelian group, up to isomorphism, of order pq. Proof. Let G be a non-abelian group of order pq. We have seen that in every such group G the q-Sylow subgroup Q is normal. Let P be any p-Sylow subgroup. Then P ∩ Q = {1} and G = QP. Thus, G is a semi-direct product of Q and P. It is thus enough to show that there is a non-abelian semi-direct product and that any two such products are isomorphic. We may consider the case Q = Z/qZ, P = Z/pZ. Lemma 25.1.2. Aut(Q) = (Z/qZ)∗. Proof. Since Q is cyclic any group homomorphism f : Q −→ H is determined by its value on a gen- erator, say 1. Conversely, if h ∈ H is of order dividing q then there is such a group homomorphism with f (1) = h. Take H = Q. The image of f is the cyclic subgroup < h > and thus f is surjective (equivalently, isomorphic) iff h is a generator. Thus, any element h ∈ (Z/qZ)∗ determines an auto- morphism fh of Q by a 7→ ah. Note that fh (fg )(a) = fh (ag) = agh = fhg (a) and so the association h ↔ fh is a group isomorphism (Z/qZ)∗ ∼ = Aut(Q). ¤ Since (Z/qZ)∗ is a cyclic group of order q − 1 (Corollary 3.0.5), and since p|(q − 1), there is an element h of exact order p in (Z/qZ)∗. Let φ be the homomorphism determined by φ1 = fh and let G = Q oφ P. We claim that G is not abelian. (n, 0)(0, b) = (n, b), (0, b)(n, 0) = (φb (n), b). The two are always equal only if φb (n) = n for all b and n, i.e., φb = 1 for all b, but choosing b = 1 we get φ1 = h and thus a contradiction. We now show that G is unique up to isomorphism. If H is another such semi-direct product then H = Z/qZ oψ Z/pZ, where ψ1 is an element of order p (if it is the identity H is abelian) and thus ψ1 = φr1 = φr for some r prime to p. Define a map Z/qZ oψ Z/pZ −→ Z/qZ oφ Z/pZ, (n, b) 7→ (n, rb). This function is easily checked to be injective, hence bijective. We check it is a group homomorphism: In G we have (n1 , rb1 )(n2 , rb2 ) = (n1 + φrb1 (n2 ), r(b1 + b2 )) = (n1 + ψb1 (n2 ), r(b1 + b2 )) which is the image of (n1 + ψb1 (n2 ), b1 + b2 ), the product (n1 , b1 )(n2 , b2 ) in H. ¤  GROUP THEORY 47 Cases where two semi-direct products are isomorphic. It is useful to generalize the last argument. Consider a map φ : B −→ Aut(N ) be a homo- morphism and consider the group G = N oφ B. Consider two automorphisms f : N → N, g : B → B. Let S be G considered as a set and consider the self map S −→ S, (n, b) 7→ (f (n), g(b)). We may define a new group law on S by (n1 , b1 ) ? (n2 , b2 ) = f ◦ g (f −1 (n1 ), g −1 (b1 ))(f −1 (n2 ), g −1 (b2 )) = f ◦ g (f −1 (n1 ) · [φ(g −1 (b1 ))](f −1 (n2 )), g −1 (b1 )g −1 (b2 )) = (n1 · f ([φ(g −1 (b1 ))](f −1 (n2 ))), b1 b2 ) Clearly, S with t