Graduate Texts In Mathematics John D. Dixon Brian Mortimer

hand, the polynomial X 5 - 2 has a group of order 20 as its Galois group.The algebraic symmetries of the polynomial described by the Galois groupare not at all obvious.The development of the theory of permutations and permutation groupsover the last two centuries was originally motivated by use of permutationgroups as a tool for exploring geometrical, algebraic and combinatorial symmetries. Naturally, the study of permutation groups gave rise to problemsof intrinsic interest beyond this initial focus on concrete symmetries, andhistorically this led to the concept of an abstract group at the end of thenineteenth century.product of disjoint cycles. A permuta,tion c E SJj7n(n) is ca,lled an rcycle (r 1, 2, . ) if for T distinct pointtl 11, ''/2) . ,IT of n) c maps Iionto IH 1 (i 1, . , r - 1), maps IT onto 11, and leaves all other pointsfixed; and c is called an infinite cycle if for some doubly infinite sequenceli(i E Z), c maps Ii onto IHI for each i and leaves all other points fixed.The second common way to specify a permutation is to write x as a productof disjoint cycles, where by disjoint we mean that no two cycles move acommon point (this product is only a formal product in the case thatn is infinite). It is a general result (see Exercise 1.2.5 below) that everypermutation can be written in essentially one way in this form.EXAMPLE1.2 Symmetric GroupsLet rt be an arbitrary nonempty set; we shall often refer to its elements aspoints. A bijection (a one-to-one, onto mapping) of rt onto itself is calleda permutation of rt. The set of all permutations of rt forms a group, undercomposit on of mappings, called the symmetric group on rt. We shall denotethis group by Sym(rt) (other common notations are SD. and SD.), and writeSn to denote the special group Sym(n) when n is a positive integer andn {I, 2, . ,n}. A permutation group is just a subgroup of a symmetricgroup. If rt and rt' are two non empty sets of the same cardinality (thatis, there is a bijection a I---t a' from rt onto n') then the group Sym(rt) isisomorphic to the group Sym(rt') via the mapping x I---t x' defined by:x' takes a' to f3' when x takes a to f3.In particular, Sym(rt) Sn whenever Irtl1. 2.1. Letnbe the finite field of 7 elements consisting of{O, I, . ,6} with addition and multiplication taken modulo 7. Then the n.Exercises1.2.1 Show in detail that the mapping described above does give anisomorphism from Sym(rt) onto Sym(rt').1.2.2 Prove that if rt is finite and Inl n, then ISym(rt) I n!.1.2.3 (For those who know something about infinite cardinalities.) Showthat if rt is infinite, then ISym(rt) I 21D.1. In particular, Sym(N) hasuncountably many elements when N is the set of natural numbers.There are two common ways in which permutations are written (at leastfor the finite case). First of all, the mapping x : rt --- rt may be writtenout explicitly in the formx :where the top row is some enumeration of the points of nand f3i is theImage of ai under x for each i. The other notation is to write x as amapping awrittenI---t4a 1 defines a permutation of n. This permutation can be( 152342635o 6)4or as a product of disjoint cycles(015)(2)(364) (2)(015)(643) . (015)(364)EXAMPLE 1.2.2. Let n rJJ (the rational numbers). Then the mappinga 1- 2a is a permutation of n. This permutation fixes the point 0, and theremaining points lie in infinite cycles of the form( . , a2- 2 , a2- 1 , a, a2 1, a2 2 , . . ).Our convention is to consider permutations as functions acting on theright. This means that a product xy of permutations should be read as:first apply x and then y (some authors follow the opposite convention). Forexample, (142)(356)(4123) (1) (2) (3564).Exercises1.2.4 Show that an r-cycle (a1 . aT) is equal to an s-cycle (f31 . (3s)on the same set n if and only if r s and for some h we haveaHh f3i for each i where the indices are taken modulo r. Showthat two infinite cycles ( . a-1aOa1 . ) and ( . f3-1f30f31 . ) onthe same set are equal if and only if for some h, aHh f3i for all i.1.2.5 Prove that each permutation x E Sym(n) can be written as a product of disjoint cycles. Show that this product is unique up to theorder in which the cycles appear in the product and the inclusion orexclusion of I-cycles (corresponding to the points left fixed by x).[Hint: Two symbols, say a and (3, will lie in the same cycle for x ifand only if some power of x maps a onto f3. This latter conditiondefines an equivalence relation on n and hence a partition of n into

1.:3.disjoint subsets. Note that when D is infinite, x may have infinitecycles and may also have infinitely many cycles. In the latter casethe product as disjoint cycles has to be interpreted suitably.]1.2.6 Suppose that x and yare permutations in Sym(D), and that y CI C2 . . . as a product of disjoint cycles. Show that x-Iyx c c .where each cycle Ci of y is replaced by a cycle c of the same length,and each point in Ci is replaced in c by its image under x. Inparticular, if a is the image of ai under x then we haveX-I(all' . ,ak)x (a , . . ,a ).1.2.7 Show that two permutations x, y E Sym(D.) are conjugate inSym(D.) if and only if they have the same number of cycles of eachtype (including I-cycles). Give an example of two infinite cycles inSym(N) which are not conjugate.1.2.8 If the permutation x is a product of k disjoint cycles of finite lengthsml, . , mk, show that the order of x as a group element is the leastcommon multiple of these lengths. What is the largest order of anelement in S20?1.2.9 Find the cycle decomposition of the permutation induced by theaction of ccnnplex conjugation on the set of roots of X 5 - X 1.1.2.10 Which permutations of the set D. : {Xl, X 2, X 3, Xli} leave thepolynomial Xl X 2 - X3 - X 4 invariant? Find a polynomial inthese variables which is left invariant under all permutations in thegroup ((X I X 2 X 3 X 4), (X2X4)) but not by all of Sym(D.).1.2.11 For each i, 2 :::; i :::; n, let Li {(I, i), (2, i), . . , (i - 1, i), J}where J is the identity element of Sn. Show that each x E Sn canbe written uniquely as a product x X2X3 . Xn with Xi E Li,.(This is the basis for a technique to generate random elements of3'17 with uniform distribution.)1.2.12 Let s(n, k) denote the number of permutations in Sn which haveexactly k cycles (including I-cycles). Show thatnL s(n, k)Xk X(X 1) . (X n - 1).k l(The s(n, k) are known as "Stirling numbers of the first kind" .)1.2.13 Let a(n, m) denote the number of permutations x E Sn such thatxm 1 (with a(O, m) 1). Show that a(n,m)xn { Xd}n!exp Ld.L71 0diml.2.14 Find necessary and sufficient conditions on the pair i, j in order that((12 . n), (ij)) Sn.1.2.15 Show that for all i, 1 i :::; n, ((23 . n), (Ii)) Sn.Group Actions1.2.16 Let n 2, and let T be the set of all permutations informITtk: (i k-i)for k 3,4, . , n Sn of thel.ISiSk/2(i) Show that T generates Sn and that each xE Sn can be writtenas a product of 2n - 3 or fewer elements from T.(ii) (Unsolved problem) Find the least integer In such that everyx E Sn can be written as a product of at most In elements fromT.1.3 Group ActionsThe examples described in Sect. 1.1 show how permutation groups areinduced by the actio:q. of groups of geometrical symmetries and field automorphisms on specified sets. This idea of a group acting on a set can beformalized as follows.Let G be a group and D. be a nonempty set, and suppose that for eacha E D. and each x E G we have defined an element of D. denoted by aX (inother words, (a, x) I---' a c is a function of D. x G into D.). Then we say thatthis defines an action of G on D. ( or G acts on D.) if we have:(i) a 1 a for all a E D. (where 1 denotes the identity elemept of G); and(ii) (aX)Y a XY for all a E D. and all x, y E G.Whenever we speak about a group acting on a set we shall implicitlyassume that the set is nonempty.EXAMPLE 1.3.1. The group of symmetries of the cube acts on a variety ofsets including: the set of eight vertices, the set of six faces; the set of twelveedges, and the set of four principal diagonals. In each case properties (i)and (ii) are readily verified.EXAMPLE l.3.2. Every subgroup G of Sym(D) acts naturally on D. whereaX is simply the image of a under the permutation x. Except when explicitly stated otherwise, we shall assume that this is the action we are dealingwith whenever we have a group of peqIlutations.If a group G acts on a (nonempty) set D., then to each element x E G wecan associate a mapping x of D. into itself, namely, a I---' aX. The mappingx is a bijection since it has x-I as its inverse (using properties (i) and(ii)); hence we have a mapping p : G - Sym(fJ) given by p(x) : X.Moreover, using (i) and (ii) again, we see that p is a group homomorphismsipce for all a E D and all x, y E G, the image of a under xy is the sameas its image under the product x y. In general, any homomorphism of G

l.4. Orbits anci Stabilizer;;into Sym(D) is call d a (permutation) representation of G on D. Hence,we see that each actIOn of G on D gives rise to a representation of G on D.Conversel , representatio s correspond to actions(see Exercise 1.3.1), sowe may thmk of group actIOns and permutation representations as differentways of describing the same situation.The following concepts related to a group action will be referred to repeatedly. The degree of an action (or a representation) is the size of D.The k rnel of the action is the kernel (ker p) of the representation P; andan actIOn (or representation) is faithful when ker P 1. The "first homo rphism theorem" shows that, when the action is faithful, the image 1m PIS Isomorphic to G. In some applications the relevant action is of the group acting on a setdIrectly related to the group itself, as the following examples illustrate.EXAMPLE 1.3.3. (Cayley representation) For any group G we can takeD : G and define an action by right multiplication: aX : ax witha, ax E D nd x E.G. (Check that this is an action!). The correspondingrepresentatIOn of G mto Sym( G) is called the (right) regular representation.It is faithful since the kernel{x E G I aX a for all a ED}equals 1. This shows that every group is isomorphic to a permutation group.EXAMPLE 1.3.4. (Action on right cosets) For any group G and any subgroup H Of. G we can take H : {Ha I a E G} as the set of rightcosets of H m G, and define an action of G on r H by right multiplication: Ha)X : Hax with Ha, Hax E H and x E G. We denote the correspondmg representation of G on r H by PH. Since H ax H a ? x E a -1 H a h ,rExercises1.3.1 Let P : G -) Sym(fl) be a representation of the group G on the setD. Show that this defines an action of G on D, by setting (ye : o:p(x)for all 0: E D, and x E G, and that P is the representation whichcorresponds to this action.1.3.2 Explain why we do not usually get an action of a group G on itself1by defining aX : xa. Show, however, that aX : x- a does givean action of G on itself (called the left regular representation of G.Similarly, show how to define an action of a group on the set of leftcosets aH (a E G) of a subgroup H .1.3.3 Show that the kernel of PH in Example 1.3.4 is equal to the largestnormal subgroup of G contained in the subgroup H.1.3.4 Use the previous exercise to prove that if Gis a.group with a subgroupH of finite index n, then G has a normal subgroup K contained inH whose index in G is finite and divides n!. In particular, if H hasindex 2 then H is normal in G.1.3.5 Let G be a finite group, and let p be the smallest prime which dividesthe order of G. If G has a subgroup H of index p, show that if mustbe normal in G. In particular, in a finite p-group (that is, a group oforder pk for some prime p) any subgroup of index p is normal. [Hint:Use the previous exercise.]1.3.6 (Number theory application) Let p be a prime congruent to 1 ( mod 4),and consider the setD,: {(x,y,z) E N na- 1 Ha.aECIn general, PHis not faithful (see Exercise 1.3.3).EXAMPLE 1.3.5. Suppose that G and H are both subgroups of a groupK a.nd t at G normalizes H. Then we can define an action of G on H bycon)ugatzon: aX : x-lax with a, x-lax E H and x E G. In this case thekernel of the corresponding representation is the centralizer of H in G:Cc(H) : {x E G I ax xa forall a E H}.The most common situation where this action occurs is when H G orH J G (that is, H is a normal subgroup of G).31x 2 4yz p}.Show that the mappingrker PH7(x, y, z)I-t(x 2z, z, y - x - z)(2y - x, y, x - y z){ (x - 2y,x - y z,y)if x y - zif y - z x 2yif x 2yis a permutation of order 2 on D with exactly one fixed point. Conclude that the permutation (x, y, z) I-t (x, z, y) must also have atleast one fixed point, and so x 2 4y2 p for some x, yEN.1.4 Orbits and StabilizersWhen a group G acts on a set D, a typical point 0: is moved by elementsof G to various other points. The set of these images is called the orbit of0: under G, and we denote it pyo:C : {o:xIxEG}.

1.'1. Orbits and StabilizersA kind of dual role is played by the set of elements in G which fix a specifiedpoint a. This is called the stabilizer of a in G and is denotedThe important properties of these objects are summarized in the followingtheorem.Theorem l.4A. Suppose that G is a group acting on a set n and thatx, y E G and a, 13 E n. Then:(i) Two orbits a G and j3G are either equal (as sets) or disJ'oint) so the setof all orbits is a partition of n into mutually disjoint subsets.(ii) The stabilizer Go: is a subgroup of G and Gf3 x-lGo:x whenever13 aX. Moreover) aX a Y { :::?- Go:x Go:y.(iii) (The orbit-stabilizer property) laG I IG : Go: I for all a E n. Inparticular) if G is finite then laGI IGo:l IGI.If 0 E a G then 0 aU for some u E G. Since ux runs overthe elements of G as x runs over G, oG {OX I x E G} {a UX I x EG} a G. Hence, if a G and j3G have any element 0 in common, thennP oG j3G. Since every clement a E n lies in at least one orbit(namely, a G ), this proves (i).Clearly 1 E Go:, and whenever x, y E Go: then xy-l E Gct' Thus Go: isa subgroup. If 13 aX then we also have:PROOF.yand so x-lGeyXaX aYE G f3 { :::?-a XY aX{ :::?-xyx -1EGo:Gf3. Finally,{ :::?-a XY-I a{ :::?-xy-l EGo:{ :::?-Go:x (ii) The index IG : Go: I Inl for each a.(iii) If G is finite then the action of G is regular{ :::?-IGI 9Inl.EXAMPLE 1.4.1. We illustrate these concepts by calculating the order ofthe group G of symmetries of the cube (Sect.1.1). Consider the action ofG on the set n of vertices labelled as in Fig. 1.1. If x denotes the rotationof the cube through an angle of 90 0 around an axis through the midpointsof the front and back faces, then the corresponding permutation x inducedon n is (1342)(5786). A similar rotation y through a vertical axis inducesthe permutation y (1265)(3487). Thus the orbits of the subgroup (x)are 1 (x) {I, 3,4, 2} and 5(x) {5, 7, 8, 6} and, similarly, (y) has orbits{I, 2, 6, 5} and {3, 4,8, 7}. Since G (x, y), the group G itself has a singleorbit and so is transitive on f2. The orbit-stabilizer property now showsthat IG : GIl Inl 8.Next consider the action of the subgroup G l . Any symmetry of the cubewhich fixes vertex 1 must also fix the opposite vertex 8, and map the vertices2, 3 and 5 amongst themselves. The rotation z of 120 0 about the axisthrough vertices 1 and 8 induces the permutation z (1)(253)(467)(8) (253)(467) on f2 and lies in G l , so {2, 5, 3} is an orbit for G I . Thus thestabilizer Gl2 of 2 in Gl satisfies IG I : Gl2 3 by the orbit-stabilizerproperty.Finally, consider the stabilizer of two points G 12 . Each symmetry whichfixes vertices 1 and 2 must also fix vertices 7 and 8, and so G 12 has a singlenontrivial element, namely a reflection w in the plane through vertices 1,2, 7 and 8 which induces the permutation w (35) (46). Thus we concludethat1Go:yand so (ii) is proved. Now (iii) follows immediately since (ii) shows that thedistinct points in a G are in bijective correspondence with the right cosets0of Go: in G, and for finite groups IG : Go: I IGI / IGo:l.A group G acting on a set f2 is said to be transitive on f2 if it has onlyone orbit, and so a G n for all a E n. Equivalently, G is transitive iffor every pair of points a,j3 E n there exists x E G such that aX 13.A group which is not transitive is called intransitive. A group G actingtransitively on a set n is said to act regularly if Go: 1 for each a E n(equivalently, only the identity fixes any point). The previous theorem thenhas the following immediate corollary.Corollary 1.4A. Suppose that G is transitive in its action on the set n.Then:(i) The stabilizers Go: (a E f2) form a single conjugacy class of subgroupsofG.EXAMPLE 1.4.2. Let G be a group and consider the conjugation actionof G on itself defined in Example 1.3.5. The orbits in this action are theconjugacy classes where two elements a, bEG lie in the same conjugacyclass { :::?- x-lax b for some x E G. The stabilizer of an element a E Gis equal to the centralizer GG(a) {x E G I ax xa}. The orbit-stabilizerproperty shows that the size of the conjugacy class containing a is equal toIG : GG(a)l· In particular, if G is finite then every conjugacy class has sizedividing IGI.Exercises1.4.1 Let G be a group acting transitively on a set f2, H be a subgroupof G and Go: be a point stabilizer of G. Show that G Go:H { :::?G HGo: { :::?- H is transitive. In particular, the only transitivesubgroup of G containing Go: is G itself. (This fact is frequentlyuseful. )

I.S. Blucks alld l'rillliLiviLy1.4.2 Show that the action of the group of symmetries of the cube on theset of six faces of the cube is transitive, and deduce that the groupof symmetries has a subgroup of index 6.1.4.3 Let H G1 be the group of symmetries of the cube which fix vertex1. What are the orbits of H on the set of 12 edges of the cube?1.4.4 Calculate the order of the symmetry group of the regular dodecahedron.1.4.5 Let K be a group. Show that we can define an action of the directproduct K x K on the set K by: a(x,y) : x-lay for all a E Kand (x, y) E K x K. Show that this action is transitive and find thestabilizer K l . When is the action faithful?1.4.6 Suppose that G is a group acting on the set nand H is a subgroup ofG, and let .6, be an orbit for H. Show that .6,x is an orbit for x-lHxfor each x E G. If G is transitive on nand H J G, show'

Graduate Texts in Mathematics TAKEUTIIZARlNG. Introduction to 33 HIRSCH. Differential Topology. Axiomatic Set Theory. 2nd ed. 34 SPITZER. Principles of Random Walk. 2 OXTOBY. Measure and Category. 2nd ed. 2nd ed. 3 SCHAEFER. Topological Vector Spaces. 35 WERMER. Banach Algebras and Several 4 HILTON/STAMMBACH. A Course in Complex