A NECESSARY CONDITION FOR TRANSITIVITY OF AFINITE PERMUTATION GROUPMARSTON CONDER AND JOHN MCKAYABSTRACTSuppose the group G is generated by permutations gvg2,...,g, acting on a set CI of size n, such that8182--8, 's the identity permutation. If the generator gt has exactly ci cycles (for 1 ^/ < s), and G istransitive on Ci, then n(s—2)—YJ'(-I c, + 2 is a non-negative even integer. This is proved using an elementarygraph-theoretic argument.In this paper we give a simple proof of a necessary condition involving the numberof cycles of any generating set for a finite permutation group. Specifically, we provethe following:Suppose G is a group of permutations of a set CI of size n, and G isgenerated by the elements g1,g2, ...,gs, whose product is the identity permutation. If thegenerator gt has exactly c{ cycles on CI {for 1 ^ / ^ s) and G is transitive on CI, thenn(s—2) — X!i-ic( + 2 must be a non-negative integer.Naturally we assume s ^ 2. The hypothesis g1g2--g8 = 1 simply requires that gg isthe inverse of the product of the first s— 1 generators (which together generate Gthemselves). By 'cycles' we mean 1-cycles (fixed points) as well as 2-cycles(transpositions), 3-cycles, and so on.It is an easy exercise to show that if the permutation gonfl has c cycles, then gis even if and only if c = n modulo 2. Further, because the product of the generators8i>82>--'>8* °f G is the identity, all but an even number of them will be evenpermutations. It therefore follows that Y£-\\ c< = ns modulo 2, and henceTHEOREM. n(s-2)-tc< + 2will have even parity independent of the transitivity of G on CI. The more importantaspect of the conclusion of the theorem is that X<-ic< ^ n(s—2)+ 2; accordinglythe theorem places an upper bound on the number of cycles of the generators chosenforG.For a trivial but perhaps illuminating application, suppose 5 = 2. Then gx = gl1,so cx = c2 and G = <£i,g2> = <£i>> and the theorem gives c1-\\-c2 < 2, thereforecx = c2= 1. In other words, the cyclic group is transitive on CI if and only if gx isa single H-cycle.Similarly when s = 3 we obtain c1 + c2 + c3 < n + 2. Albeit in a slightly differentform, the same conclusion was obtained by Singerman in [6, Theorem 10], using theReceived 10 November 1987.1980 Mathematics Subject Classification 20B05, 05C25.The first author is grateful to the Alexander von Humboldt Stiftung and to the Universitat Tubingenfor support and facilities provided during the time this paper was written.Bull. London Math. Soc. 20 (1988) 235-238236 M. CONDER AND J. MCKAYRiemann-Hurwitz equation. One interesting corollary is that if p, q and r are primeintegers, then the abstract group (x,y,z\\xp = / = zr = xyz = 1> has a transitivepermutation representation of degree n (and therefore a subgroup of index n)In the special case where s = 3 and one of the generators has order 2, a more directproof is possible (as in [2, Section 2]), but the proof we give below for the general caseis much simpler!In fact the general case has been proved already, first by Ree [4] using the theoryof Riemann surfaces, and then more directly by Feit, Lyndon and Scott [3]. The latterauthors noticed that the number of cycles of a permutation is equal to the multiplicityof 1 as an eigenvalue of the associated permutation matrix; this idea was extended byScott in [5], giving a generalization of Ree's theorem to matrix groups.Proof of the Theorem. We begin by defining the directed graph F, as follows:vertices of F are the points of Cl, and each point aeQ is joined by a directed edgelabelled g, to the corresponding point a\"*, for 1 ^ i < s.Every vertex of F has out-degree s and in-degree s, and because G is transitive onQ, the graph F is connected. (In fact F is a Schreier coset graph, as its vertices may beidentified with the cosets of the stabilizer of any point.)We now embed the graph F into an orientable surface S, by assigning the sameparticular rotation of edges at each vertex, namely that indicated in Figure 1. Readersunfamiliar with this technique may read about it in [1, Chapter 5], for example.FIG. 1. Rotation of edges at each vertex a.The Euler characteristic x of the surface S is related to the genus y of S byX = 2 — 2y, and can be calculated using the standard formula x — V—E+F, whereV, E and F denote respectively the numbers of vertices, edges and faces of theembedded graph. Clearly V = |Q| = n and E = ns, so it remains for us to determine F.By our choice of the rotation of edges at each vertex, it is clear that there areprecisely n faces bounded by a directed edge sequence of the form {gx,g2,gz, ..,£,)•Further, each cycle of each permutation gt corresponds to a face of the embeddedgraph, with the elements of the cycle coinciding with the vertices of the face! In otherwords, there are ci faces bounded only by edges labelled gt, for 1 < / ^ s. Togetherthese faces account for all the edges of F, hence F= n+ Y,UicvA NECESSARY CONDITION FOR TRANSITIVITY OF A FINITE PERMUTATION GROUP 237Thus we obtain 2 — 2y = / = n—ns+ 11+^1.1 ca sothatw(.s — 2)— £*-ic< + 2 = 2y,completing our proof.Finally we explain how Ree's original proof of this theorem relates to ours, usingthe dual F* of the embedded graph F given above.The vertices of F* are defined to be the faces of F, with two such vertices adjacentin F* if and only if as faces of F they have an edge in common in F, and these verticesare of two sorts: those corresponding to the product g1 g2.. .gs, and those coming fromthe cycles of the individual generators. Let us call vertices of the first sort 7r-points,and label each of the second sort with the corresponding gt (for 1 ^ i ^ s). The graphF* can be embedded in the same surface as before, with faces of F* in one-to-onecorrespondence with the vertices of F. A typical face of F* is illustrated in Figure 2(with edges of F indicated by broken lines).FIG. 2. A typical face of F*.FIG. 3. The underlying structure on the sphere.The associated surface is an «-sheeted branched covering of the Riemann sphere,just like the one constructed in [4]. This can be seen as follows.For each //identify all c( of the vertices of F* labelled gt, and form branch-pointsby identifying adjacent edges of F* coming out of each vertex gt. (This is just likepicking up corners of a piece of dough and gathering them together.) The edges of Flabelled gt all go to a single loop around the now unique gt vertex, while the n 7r-pointsare identified with each other to form a single unramified point. The resulting surfaceis a sphere (carrying the structure illustrated in Figure 3), and so the original surfaceis an H-sheeted covering of this sphere, with branch-points corresponding to the gi (for1 < i < s).Moreover, the group G is the monodromy group of the surface, permuting its nsheets in the obvious way.We would like to thank Gareth Jones and David Singerman for their kindassistance with the latter part of the above explanation.238 M. CONDER AND J. MCKAYReferences1. N. L. BIGGS and A. T. WHITE, Permutation groups and combinatorial structures, London Math. Soc.Lecture Note Series 33 (Cambridge University Press, 1979).2. M. D. E. CONDER, 'Some results on quotients of triangle groups', Bull. Austral. Math. Soc. 30 (1984)73-90.3. W. FEIT, R. LYNDON and L. L. SCOTT, 'A remark about permutations', J. Combin. Theory, Ser. A 18(1975) 234-235.4. R. REE, 'A theorem on permutations', J. Combin. Theory, Ser. A 10 (1971) 174-175.5. L. L. SCOTT, 'Matrices and cohomology', Ann. of Math. 105 (1977) 473-492.6. D. SINGERMAN, 'Subgroups of Fuchsian groups and finite permutation groups', Bull. London Math.Soc. 2 (1970) 319-323.Department of Mathematics and Statistics University of Auckland Private Bag Auckland New Zealand Department of Computer ScienceConcordia University1455 de Maisonneuve Blvd WestMontreal H3G 1M8Canada
