Introduction to Group Theory and Applications Gruppentheorie mit Anwendungen in der Kombinatorik Ju(cid:127)rgen Bierbrauer September 2, 2000 2 Contents 1 Introduction to Group Theory 5 1.1 De(cid:12)nition of groups . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Groups of symmetry . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Group tables . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 Permutations and the symmetric groups . . . . . . . . . . . . 11 1.5 Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.6 Cosets and Lagrange's theorem . . . . . . . . . . . . . . . . . 15 1.7 Divisors and the Euclidean algorithm . . . . . . . . . . . . . . 16 1.8 Congruences and the cyclic groups . . . . . . . . . . . . . . . 19 1.9 Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.10 Isomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.11 Calculating in cyclic groups . . . . . . . . . . . . . . . . . . . 21 1.12 Direct products . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.13 Normal subgroups and factor groups . . . . . . . . . . . . . . 23 1.14 Group homomorphisms . . . . . . . . . . . . . . . . . . . . . . 25 1.15 The signum and alternating groups . . . . . . . . . . . . . . . 26 1.16 Permutation representations . . . . . . . . . . . . . . . . . . . 29 1.17 Orbits and the orbit lemma . . . . . . . . . . . . . . . . . . . 30 1.18 The dihedral groups . . . . . . . . . . . . . . . . . . . . . . . 32 1.19 The cube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.20 Prime (cid:12)elds . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 1.21 Finite (cid:12)elds . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 1.22 Linear groups . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 1.23 Group automorphisms and conjugation . . . . . . . . . . . . . 46 1.24 Commutators . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 1.25 Characteristic subgroups . . . . . . . . . . . . . . . . . . . . . 48 1.26 The semidirect product . . . . . . . . . . . . . . . . . . . . . . 48 3 4 CONTENTS 1.27 Permutation representations inside G . . . . . . . . . . . . . . 49 1.28 Conjugacy classes . . . . . . . . . . . . . . . . . . . . . . . . . 51 1.29 Products of subgroups . . . . . . . . . . . . . . . . . . . . . . 52 1.30 p-groups and Sylow's theorems . . . . . . . . . . . . . . . . . . 53 1.31 Proof of the Sylow theorems . . . . . . . . . . . . . . . . . . . 55 1.32 Simple groups . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 1.33 Composition series . . . . . . . . . . . . . . . . . . . . . . . . 57 1.34 Solvable and nilpotent groups . . . . . . . . . . . . . . . . . . 58 1.35 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2 Permutation groups 63 2.1 Normal subgroups . . . . . . . . . . . . . . . . . . . . . . . . . 66 2.2 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3 The classical simple groups 69 3.1 Scalar products . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.2 The symplectic groups . . . . . . . . . . . . . . . . . . . . . . 70 3.2.1 Hyperbolic planes . . . . . . . . . . . . . . . . . . . . . 70 3.2.2 Case n > 2 . . . . . . . . . . . . . . . . . . . . . . . . 70 3.3 The unitary groups . . . . . . . . . . . . . . . . . . . . . . . . 72 3.4 The orthogonal groups in odd characteristic . . . . . . . . . . 74 3.5 Witt's theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 78 3.5.1 Proof of Witt's theorem . . . . . . . . . . . . . . . . . 81 3.6 Symmetric scalar products in characteristic 2 . . . . . . . . . . 83 3.7 Quadratic forms in characteristic 2 . . . . . . . . . . . . . . . 84 3.7.1 The 3-dimensional case in characteristic 2 . . . . . . . 88 3.8 A table of groups, orders and isomorphisms . . . . . . . . . . 88 4 Polya's enumeration theory 91 4.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 5 Block designs 97 5.1 Some easy direct constructions . . . . . . . . . . . . . . . . . . 99 5.2 Steiner triple systems . . . . . . . . . . . . . . . . . . . . . . . 101 5.3 Some easy recursive constructions . . . . . . . . . . . . . . . . 104 5.4 A link to permutation groups . . . . . . . . . . . . . . . . . . 106 5.5 The groups PGL2(q) . . . . . . . . . . . . . . . . . . . . . . . 106 5.5.1 Circle geometries . . . . . . . . . . . . . . . . . . . . . 108 CONTENTS 5 5.5.2 A class of 4-designs . . . . . . . . . . . . . . . . . . . . 109 5.6 The projective linear groups . . . . . . . . . . . . . . . . . . . 111 5.7 The simplicity of PSLn(q): . . . . . . . . . . . . . . . . . . . . 112 5.8 Quadrics and ovals . . . . . . . . . . . . . . . . . . . . . . . . 115 5.9 The large Witt designs . . . . . . . . . . . . . . . . . . . . . . 116 5.10 Golay code and Witt designs . . . . . . . . . . . . . . . . . . . 121 5.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 A Transfer and fusion 125 B Transitive extensions, Mathieu groups 129 C The small Witt design 133 6 CONTENTS Chapter 1 Introduction to Group Theory 1.1 De(cid:12)nition of groups We start with a formal de(cid:12)nition. 1.1 De(cid:12)nition. Let G be a set and let a product operation : G(cid:2)G (cid:0)! G be de(cid:12)ned. Then (G;(cid:1)) is a group if the following hold: (cid:15) g1(g2g3) = (g1g2)g3 for all gi 2 G (associativity). (cid:15) There is an element e 2 G (the neutral element) such that eg = ge = g for all g 2 G: (cid:0)1 (cid:15) For every g 2 G there is an element g 2 G ( the inverse element) (cid:0)1 (cid:0)1 such that gg = g g = e: 0 Observe that the neutral element is uniquely determined (ife is a neutral 0 0 element, then by de(cid:12)nition ee = e = e). We also write the neutral element as 1: A (cid:12)rst general result are the cancellation laws, which hold in any group. 1.2 Theorem (cancellation laws). Let G be a group. Then the following hold: (cid:15) If ax = ay; then x = y (cid:15) If xa = ya; then x = y: 7 8 CHAPTER 1. INTRODUCTION TO GROUP THEORY A B C D Figure 1.1: The rectangular playing card (cid:0)1 Proof. Assume ax = ay: Multiply by the inverse a from the left and use associativity: (cid:0)1 (cid:0)1 x = a ax = a ay = y: The same procedure works in the other case. As a consequence we see that every element a has a uniquely deter- (cid:0)1 mined inverse a and that equations ax = b and xa = b have unique (cid:0)1 (cid:0)1 solutions x (x = a b in the (cid:12)rst case, x = ba in the second case). A group G is (cid:12)nite if the set G is (cid:12)nite. The cardinality of G is then called the order of the group. A group G is commutative (or abelian) if ab = ba for all a;b 2 G: If ab = ba we also say that a and b commute. It is one objective of this course to show that allsorts of algebraic, combi- natorial or geometric structures give rise to groups in a natural way. Group theory helps understanding the situation in all these seemingly diverse cases. Our (cid:12)rst class of examples are groups of symmetry. 1.2 Groups of symmetry As a toy example consider a rectangular playing card. The symmetry group of the card is de(cid:12)ned as the set of all permutations of the corners 1.2. GROUPS OF SYMMETRY 9 A;B;C;D which have the property that the card looks alike before and after the permutation is applied. Recall that a permutation of a set is a bijective (onto and one-to-one) mapping of the set. There are three types of pairs of corners in our card: those pairs connected by a long edge, those connected by a short edge and those not connected by an edge. We can reformulate our condition: a permutation of the corners fA;B;C;Dg is a symmetry if and only if (cid:15) the image of any long edge is a long edge, (cid:15) the image of any short edge is a short edge, and (cid:15) the image of any non-edge is a non-edge (cid:18) (cid:19) A B C D Letusconsiderthepermutation :Thisnotationmeans A C D B that the permutation maps A 7! A;B 7! C;C 7! D;D 7! B: Is this a sym- metry of the rectangular playing card or not? No, because the pair fA;Bg of corners (a long edge) is mapped to fA;Cg (a short edge). Let us determine all symmetries of our card: one symmetry is always there, the permutation (cid:18) (cid:19) A B C D e = ; which does nothing(the neutral element). Anything A B C D else? Geometric intuition will help: if we imagine a horizontal axis through the centers of edges AC and BD and we rotate our card about that axis (cid:18) (cid:19) A B C D (in 3-space), we obtain the symmetry a = : An analo- C D A B (cid:18) (cid:19) A B C D gous rotation about a vertical axis yields b = : Another B A D C idea is to re(cid:13)ect at the center of the card. This gives us the symmetry (cid:18) (cid:19) A B C D c = : Is this all? Yes. It is not hard to convince ourselves D C B A that any symmetry is uniquely determined as soon as we know the image of A: If for example A 7! D; then B; the unique partner forming a long edge with A; must be mapped to C; the unique partner to form a long edge with D; and so forth. 1.3 Theorem. The symmetry group of the rectangular card is the group V = fe;a;b;cg of order 4. 10 CHAPTER 1. INTRODUCTION TO GROUP THEORY Thisisthe(cid:12)rstgroupweactuallysaw, anditisaninterestinggroup. Why is it a group and what is the group operation? Each symmetry is a mapping, more speci(cid:12)cally a permutation. When two permutations are given, we can form the composite function. If each of f and g is a symmetry, then also the compositions f (cid:14)g and g(cid:14)f are symmetries. We can check the group axioms from De(cid:12)nition 1.1. Associativity is obvious as composition of functions is (cid:0)1 associative. The neutral element is the lazy permutation e; the inverse f of permutation (symmetry) f is the inverse mapping. 1.4 De(cid:12)nition. We de(cid:12)ne the product of two permutations (on the same set) as the composition of functions. Here we adopt the convention that fg is the composite function, which is obtained by applying f (cid:12)rst and then g: With this terminology we have for example ab = c (in words: if we apply (cid:12)rst permutation a; then b; the result is permutation c:) More in general we see, that the product of any two di(cid:11)erent non-neutral elements of V is the third. Here is another example, the quadratic card. This time there are only edges and non-edges. A symmetry is a permu- tation of the corners, which satis(cid:12)es (cid:15) the image of any edge is an edge, and (cid:15) the image of any non-edge is a non-edge In fact, it su(cid:14)ces that the (cid:12)rst condition be satis(cid:12)ed. If the image of every edge is an edge, then the non-edges will automatically be mapped to non-edges. It is also clear, that the group V from Theorem 1.3 is contained in the symmetry group of the quadratic card. Is that all? No, here is a symmetry of the quadratic card, which is not a symmetry of the rectangular (cid:18) (cid:19) A B C D card: u = : By now we know that the symmetries form A C B D a group, with the group product from De(cid:12)nition 1.4. As we already have the symmetries from V; each new symmetry like u gives us at least four new symmetries: u;v = ua;w = ub;x = uc: These must be di(cid:11)erent of each other and of the elements of V; because of the cancellation laws (see (cid:18) (cid:19) (cid:18) (cid:19) A B C D A B C D Theorem 1.2). We obtain v = ; w = ; C A D B B D A C (cid:18) (cid:19) A B C D x = : We have eight symmetries so far. This is all. In D B C A