ON THE MAXIMUM ORDERS OF ELEMENTS OF FINITE ALMOST SIMPLE GROUPS AND PRIMITIVE PERMUTATION GROUPS SIMONGUEST, JOY MORRIS,CHERYL E. PRAEGER, ANDPABLO SPIGA Abstract. Wedetermineupperboundsforthemaximumorderofanelementofafinite almost simple group with socle T in terms of the minimum index m(T) of a maximal subgroup of T: for T not an alternating group we provethat, with finitely many excep- tions,themaximumelementorderisatmostm(T). Moreover,apartfromanexplicitlist 3 ofgroups, theboundcan bereducedtom(T)/4. Theseresults areapplied todetermine 1 all primitive permutation groups on a set of size n that contain permutations of order 0 greater than or equal to n/4. 2 n a J 2 1. Introduction 2 In 1903, Edmund Landau [26, 27] proved that the maximum order of an element of ] the symmetric group Sym(n) or alternating group Alt(n) of degree n is e(1+o(1))(nlogn)1/2, R though it is now known from work of Erd¨os and Turan [14, 15] that most elements have G far smaller orders, namely at most n(1/2+o(1))logn (see also [4, 5]). Both of these bounds . h compare the element orders with the parameter n, which is the least degree of a faithful t a permutation representation of Sym(n) or Alt(n). Here we investigate this problem for all m finite almost simple groups: [ Find upper bounds for the maximum element order of an almost simple group with socle 1 T in terms of the minimum degree m(T) of a faithful permutation representation of T. v 6 We discover that the alternating and symmetric groups are exceptional with regard to 6 this element order comparison. We also study maximal element orders for many natural 1 classesofsubgroupsofSym(n),inparticularformanyfamiliesofprimitivesubgroups. Our 5 most general result for almost simple groups is Theorem 1.1. For a group G we denote . 1 by meo(G) the maximum order of an element of G. We note that the value of meo(T) 0 for T a simple classical group of odd characteristic was determined in [23] and its relation 3 1 to m(T) can be deduced. If G is almost simple, say T G Aut(T) with its socle T a v: non-abelian simple group, then naturally meo(G) meo≤(Aut≤(T)). ≤ i X Theorem 1.1. Let G be a finite almost simple group with socle T, such that T = Alt(m) 6 r for any m 5. Then with finitely many exceptions, meo(G) m(T); and indeed either a ≥ ≤ T = PSL (q) forsome d,q, ormeo(G) m(T)3/4. Moreover, givenpositive ǫ,A> 0, there d ≤ exists Q = Q(ǫ,A) such that, if T = PSU (q) with q > Q, then meo(G) > Am(T)3/4 ǫ. 4 − We note again that this result gives upper bounds for meo(Aut(T)) in terms of m(T), and for meo(G) in terms of m(G) (since m(T) m(G)). Moreover equality in the up- ≤ per bound meo(Aut(T)) m(T) holds when T = PSL (q) for all but two pairs (d,q), d ≤ see Table 3 and Theorem 2.16. (Theorem 2.16 and Table 3 provide good estimates for 2000 Mathematics Subject Classification. 20B15, 20H30. Key words and phrases. primitive permutation groups; conjugacy classes; cycle structure. Address correspondence to P. Spiga, E-mail: [email protected] The second author is supported in part by the National Science and Engineering Research Council of Canada. The research is supported in part by the Australian Research Council grants FF0776186, and DP130100106. 1 2 S.GUEST,J.MORRIS,C.E.PRAEGER,ANDP.SPIGA meo(Aut(T)) for all finite classical simple groups T in terms of the field size and dimen- sion.) We are particularly interested in linear upper bounds for meo(Aut(T)) of the form cm(T) with a constant c < 1. It turns out that, after excluding the groups Alt(m) and PSL (q), suchanupperboundholdswiththeconstantc= 1/4forallbut12simplegroups d T. Theorem 1.2. For a finite non-abelian simple group T, either meo(Aut(T)) < m(T)/4, or T is listed in Table 1. M M Alt(m) PSL (q) PSU (3) PSp (2) 11 23 d 3 6 M M PSU (5) PSp (2) 12 24 3 8 M HS PSU (3) PSp (3) 22 4 4 Table 1. Exceptions in Theorem 1.2 Clearly, Theorems 1.1 and 1.2 do not provide the last word on this type of result. One might wonder, if minded so, “What is the slowest growing function of m(T) with the property that Theorem 1.2 is still valid?” (possibly allowing a finite extension of the list inTable1). Wedonotinvestigate thishere. Insteadweturnourattention tomeo(G)fora wider family of primitive permutation groups G than the almost simple primitive groups. For such groups of degree n, it also turns out that meo(G) < n/4, apart from a number of explicitly determined families and individual primitive groups. We refer to [20] for the affinecase in which G hasan abelian socle, since theproof in thatcase is very delicate and quite different from the arguments in this paper, which are based on properties of finite simple groups. Theorem 1.3. Let G be a finite primitive permutation group of degree n such that meo(G) is at least n/4. Then the socle N = Tℓ of G is isomorphic to one of the following (where ∼ k,ℓ 1): ≥ (1) Alt(m)ℓ in its natural action on ℓ-tuples of k-subsets from 1,...,m ; { } (2) PSL (q)ℓ in either of its natural actions on ℓ-tuples of points, or ℓ-tuples of hyper- d planes, of the projective space PG (q); d 1 (3) an elementary abelian group Cℓ an−d G is described in [20]; or to p (4) one of the groups in Table 2. Moreover, there exists a positive integer ℓ , depending only on T, such that ℓ ℓ . T T ≤ Remark 1.4. The possibilities for the degree n of G in Theorem 1.3(4) are, in fact, quite restricted. In column 2 of Table 6, we list the possibilities for the degree m of the permutation representation of the socle factor T of a primitive group G of PA type of degree n = mℓ. The integer ℓ can be as small as 1, in which case G is of AS type, and has maximum value ℓ , which is also listed in column 2. If G is of HS or SD type (with socle T Alt(5)2) then we simply have n = 60. Our choice of n/4 in Theorems 1.2 and 1.3 is in some sense arbitrary. However it yields a list of exceptions that is not too cumbersome to obtain and to use, and yet is sufficient to provide useful information on the normal covering number of Sym(m), an application described in [21]. (The normal covering number of a non-cyclic group G is the smallest numberofconjugacyclassesofpropersubgroupsofGsuchthattheunionofthesubgroups in all of these conjugacy classes is equal to G, that is to say the classes ‘cover’ G.) In [21] we use Theorem 1.3 to study primitive permutation groups containing elements with at most four cycles, and our results about such groups yield critical information on normal covers of Sym(n), and a consequent number theoretic application. MAXIMAL ELEMENT ORDER 3 AS type HS or SD PA type type Alt(5) M PSL (7) PSL (49) PSU (3) PSp (2) Alt(5)2 Tℓ where 11 2 2 3 6 Alt(6) M PSL (8) PSL (3) PSU (5) PSp (2) T is one of 12 2 3 3 8 Alt(7) M PSL (11) PSL (4) PSU (3) PSp (3) the groups 22 2 3 4 4 Alt(8) M PSL (16) PSL (3) in the AS type 23 2 4 Alt(9) M PSL (19) part of 24 2 HS PSL (25) this table 2 Table 2. The socles for the exceptions G in Theorem 1.3 (4) 1.1. Comments on the proof of Theorem 1.3. Our proof of Theorem 1.3 uses the bounds of Theorem 1.2, and proceeds according to the structure of G and its socle as specified by the “O’Nan–Scott type” of G. This is one of the most effective modern methods for analysing finite primitive permutation groups. The socle N of G is the subgroup generated by the minimal normal subgroups of G. For an arbitrary finite group the socle is isomorphic to a direct product of simple groups, and, for finite primitive groups these simple groups are pairwise isomorphic. The O’Nan–Scott theorem describes in detail the embedding of N in G and provides some useful information on the action of N, identifying a small number of pairwise disjoint possibilities. The subdivision we use in ourproofsisdescribedin [38]whereeight typesof primitivegroupsaredefined(depending on the structure and on the action of the socle), namely HA (Holomorphic Abelian), AS (Almost Simple), SD (Simple Diagonal), CD (Compound Diagonal), HS (Holomorphic Simple), HC (Holomorphic Compound), TW (Twisted wreath), PA (Product Action), and it follows from the O’Nan–Scott Theorem (see [30]or [13, Chapter4]) that every primitive group is of exactly one of these types. In the light of this subdivision, Theorem 1.3 asserts that a finite primitive group con- taining elements of large order relative to the degree is either of AS or PA type (with a well-understood socle), or of HA type, or it has bounded order. The proof of Theorem 1.3 forprimitivegroupsofHAtypeisinourcompanionpaper[20],whereweobtainanexplicit description of the permutations g G with order g n/4 together with detailed infor- ∈ | | ≥ mation on the structure of G. We refer the interested reader to [20] for more information on this case. 1.2. Structure of the paper. In Section 2 we determine tight upper bounds on the maximumelementordersforthealmostsimplegroupsandwegiveinTable3somevaluable information on the maximum element order of Aut(T) when T is a simple group of Lie type. In Section 3, we collect some well-established results on the minimal degree of a permutation representation for the non-abelian simple groups. (These include corrections noticed by Mazurov and Vasilev [35] to [25, Table 5.2.A].) We then prove Theorem 1.2 in ′ Section 4. The proof of Theorem 1.3, which relies on Theorem 1.2, is given in Section 5. We provide some information on the positive integers ℓ (defined in Theorem 1.2) in T Remark 5.11 and in Table 6. Finally, Section 6 contains the proof of Theorem 1.1. 2. Maximum element orders for simple groups For a finite group G, we write exp(G) for the exponent of G; that is, the minimum positive integer k for which gk = 1 for all g G. We denote the order of the element ∈ g Gby g andwewritemeo(G)for themaximum element order ofG; thatis, meo(G) = ∈ | | max g g G . Clearly, meo(G) divides exp(G). {| | | ∈ } 4 S.GUEST,J.MORRIS,C.E.PRAEGER,ANDP.SPIGA In this section we study meo(G) where G is an almost simple group. We start by considering the symmetric groups. It is well-known that meo(Sym(m)) = max lcm(n ,...,n ) m = n + +n . 1 N 1 N { | ··· } The expression meo(Sym(m)) is often referred to as Landau’s function (and is usually denoted by g(m)), in honour of Landau’s theorem in [26]. We record the main results from [26] and [34] on meo(Sym(m)), to which we will refer in the sequel. As usual log(m) denotes the logarithm of m to the base e. Theorem 2.1 ([26] and [34, Theorem 2]). For all m 3, we have ≥ log(log(m)) a mlog(m)/4 log(meo(Sym(m))) mlogm 1+ − ≤ ≤ 2log(m) (cid:18) (cid:19) p p with a = 0.975. Proof. The lower bound is proved in [26] and the upper bound is proved in [34]. (cid:3) Since Aut(Alt(m)) = Sym(m) unless m 2,6 , Theorem 2.1 gives good estimates of ∼ ∈ { } the maximum element order of Aut(Alt(m)). And since the minimal degree of a permuta- tionrepresentationofAlt(m)ism,form = 6,wefindthatAlt(m)isoneoftheexceptional 6 groups in Theorem 1.2 listed in Table 1. For the groups of Lie type, the following three lemmas will be used frequently in the proof of Theorem 1.2. Here log (x) denotes the logarithm of x to the base p and x p ⌈ ⌉ denotes the least integer k satisfying x k. We denote by J the cyclic unipotent element d ≤ of GL (q) that sends the canonical basis element e to e +e for i< d and fixes e ; that d i i i+1 d is, J is a d d unipotent Jordan block. Also, we denote the identity matrix in GL (q) by d d × I . d Lemma 2.2. Let u be a unipotent element of GL (pf) where p is prime. Then u d | | ≤ p⌈logp(d)⌉ and equality holds if and only if the Jordan decomposition of u has a block of size b such that log (d) = log (b) . ⌈ p ⌉ ⌈ p ⌉ Proof. Let b be the dimension of the largest Jordan block of u. Let B = J I , a b b b b matrix over F . Then since J is unipotent, it follows that B is nilpotent a−nd Bb =×0. pf b Now fix a positive integer k. Using the binomial theorem, we have Jpk = (I +B)pk = pk pk Bi. b b i i=0(cid:18) (cid:19) X Since pk is divisible by p for every i 1,...,pk 1 , we have Jpk = I + Bpk. In i ∈ { − } b b particular, Jpk = I if and only if Bpk = 0. Since J is a cyclic unipotent element, b is the (cid:0) (cid:1) b b b least positive integer such that Bb = 0; therefore r = log (b) is the least nonnegative ⌈ p ⌉ integer such that Bpr =0. Thus Jb = p⌈logp(b)⌉. | | Suppose that the maximum size of a Jordan block of u is b. Then by the previous paragraph, u = Jb = p⌈logp(b)⌉. Since b d, this implies that u p⌈logp(d)⌉ and that | | | | ≤ | | ≤ equality holds if and only if log (d) = log (b) . (cid:3) ⌈ p ⌉ ⌈ p ⌉ The following elementary lemma, on the direct productof cyclic groups, will be applied to the maximal tori of groups of Lie type. Lemma 2.3. Let k be a positive integer, and for each i 1,...,t , let k be a multiple of i ∈ { } k and let C = x be a cyclic group of order k . Let C be the subgroup of G := C C i i i 1 t h i ×···× of order k generated by xk1/k xkt/k. Then the exponent of the quotient group G/C is 1 ··· t k /k if t = 1 and lcm k ,...,k if t 2. 1 1 t { } ≥ MAXIMAL ELEMENT ORDER 5 Proof. If t = 1, then the exponent of x / xk1/k is clearly k /k. So suppose that t 2. h 1i h 1 i 1 ≥ Set r = lcm k ,...,k and r = exp(G/C). The group G has exponent r and so r = 1 t ′ ′ exp(G/C) {r. Conver}sely, for each i 1,...,t , we have xr′ C. Since t 2, we have ≤ ∈ { } i ∈ ≥ C C = 1 because the non-trivial elements of C all have the form xjk1/k xjkt/k with 1i ∩j < k, and so do not lie in C . Thus xr′ = 1. This shows that, for1each·i·· t1,...,t , ≤ i i ∈ { } the integer k divides r . Therefore r r , and so r = r. (cid:3) i ′ ′ ′ ≤ The following technical lemma will be applied repeatedly to estimate the maximum element order of a group of Lie type. Lemma 2.4. Suppose that m,k,f,p are positive integers where p is prime and q = pf. Then (i) qk 1 divides qkm 1 and (qkm 1)/(qk 1) p⌈logp(m)⌉; − − − − ≥ (ii) if m is odd, then qk +1 divides qkm +1; furthermore, if (p,k,m,f) = (2,1,3,1), 6 then (qkm+1)/(qk +1) p⌈logp(m)⌉; ≥ (iii) if m is even, then qk+1 divides qkm 1; furthermore, if (k,m,f) = (1,2,1), then − 6 (qkm 1)/(qk +1) p⌈logp(m)⌉. − ≥ Proof. The divisibility assertions in (i), (ii) and (iii) are obvious. For Part (i), note that (qkm 1)/(qk 1) = qk(m 1)+qk(m 2)+ +qk +1 qk(m 1). Furthermore, qk(m 1) − − − − − − ··· ≥ ≥ qm 1 pm 1 m and so m 1 log (m). However m 1 is an integer, so m 1 − ≥ − ≥ − ≥ p − − ≥ ⌈logp(m)⌉ and (qkm−1)/(qk −1) ≥ pm−1 ≥ p⌈logp(m)⌉. Assume that m is odd. The assertions hold if m = 1, so assume that m 3. Then ≥ (qkm+1)/(qk +1) qk(m 2) = pfk(m 2) m (where the last inequality holds for m 3 − − ≥ ≥ ≥ provided (p,k,m,f) = (2,1,3,1)). So, arguing as in the previous paragraph, we have 6 (qkm+1)/(qk +1) p⌈logp(m)⌉ for (p,k,m,f) = (2,1,3,1), which gives Part (ii). ≥ 6 Next, suppose that m is even. The assertions all hold for m = 2 unless (k,m,f) = (1,2,1). So assume that m 4. Then (qkm 1)/(qk+1) qk(m 2) = pfk(m 2) m. Now − − ≥ − ≥ ≥ arguing as in the first paragraph we have (qkm 1)/(qk +1) p⌈logp(m)⌉, which proves − ≥ Part (iii). (cid:3) Before proceeding and obtaining some tight bounds on the maximum element order for the groups of Lie type, we need to prove some results on centralizers of semisimple elements in PGL (q) and related classical groups. In order to do so, we introduce some d notation. Notation 2.5. Let δ = 1 unless we deal with a unitary group in which case let δ = 2. Let s be a semisimple element of PGL (qδ) and let s be a semisimple element of GL (qδ) d d projecting to s in PGL (qδ). Theaction of the matrix s on the d-dimensional vector space d V = Fd naturally defines the structure of an F s -module on V. Since s is semisimple, qδ qδh i V decomposes, by Maschke’s theorem, as a direct sum of irreducible F s -modules, that qδh i is, V = V V , with V an irreducible F s -module. Relabelling the index set 1 ⊕ ··· ⊕ l i qδh i 1,...,l if necessary, we may assume that the first t submodules V ,...,V are pairwise 1 t { } non-isomorphic (for some t 1,...,l ) and that for j t+1,...,l , V is isomorphic j ∈ { } ∈ { } to some V with i 1,...,t . Now, for i 1,...,t , let = W V W = V , the set ofiF s -su∈bm{ odules}of V isomorph∈ic{to V a}nd wrWitei W{= ≤ | W∼. Tih}e module W iqsδhusiually referred to as the homogeneouis component oif V coWrr∈esWpionding to i P the simple submodule Vi. We have V = W1 Wt. Set ai = dimF (Wi). Since ⊕ ··· ⊕ qδ V is completely reducible, we have W = V V for some m 1, where i i,1 ⊕ ··· ⊕ i,mi i ≥ Vi,j ∼= Vi, for each j ∈ {1,...,mi}. Thus we have ai = dimi, where di = dimFqδ Vi, and t d m = d. For i 1,...,t , we let x (respectively y ) denote the element in i=1 i i ∈ { } i i,j GL(W ) (respectively GL(V )) induced by the action of s on W (respectively V ). In i i,j i i,j P 6 S.GUEST,J.MORRIS,C.E.PRAEGER,ANDP.SPIGA particular, x = y y and s = x x . We note further that i i,1··· i,mi 1··· t p(s)= (d ,...,d ,d ,...,d ,...,d ,...,d ) 1 1 2 2 t t m1 times m2 times mt times is a partition of n. | {z } | {z } | {z } Now let c C (s). Given i 1,...,t and W , we see that Wc is an ∈ GLd(qδ) ∈ { } ∈ Wi F s -submodule of V isomorphic to W (because c commutes with s). Thus Wc . qδh i ∈ Wi This shows that W is C (s)-invariant. It follows that i GLd(qδ) C (s) =C (x ) C (x ) GLd(qδ) GL(W1) 1 ×···× GL(Wt) t andeveryunipotentelementofC (s)isoftheformu =u u withu C (x ) GLd(qδ) 1··· t i ∈ GL(Wi) i unipotent in GL(W ), for each i. i Since s is semisimple and V is irreducible, Schur’s lemma implies that V =F and i,j i,j ∼ qδdi that the action of y on V is equivalent to the scalar multiplication action on F by a i,j i,j qdi field generator λ of F . As V = V , we have λ = λ , for j ,j 1,...,,m i,j qδdi i,j1 ∼ i,j2 i,j1 i,j2 1 2 ∈ { i} and we write λ = λ . Under this identification, replacing x by a suitable conjugate i i,1 i in GLai(qδ) if necessary, we have xi = λiImi ∈ GLmi(qδdi) < GLai(qδ). Now a direct computation shows that CGL(Wi)(xi) ∼= GLmi(qδdi). Proposition 2.6. Let s be as in Notation 2.5. A unipotent element u of PGL (q) cen- d tralizing s has order at most max p⌈logp(m1)⌉,...,p⌈logp(mt)⌉ . { } Proof. We use the notation established in Notation 2.5. Let u be a unipotent element of PGL (q) and let u be the unique unipotent element of GL (q) projecting to u. Since d d u centralizes s, u commutes with s modulo Z(GL (q)). Thus us = (su)c, for some d scalar matrix c of GL (q). Arguing by induction, we see that, for each k 1, we have d ≥ uks = sukck. In particular, for k = q 1, since cq 1 = 1, it follows that uq 1 centralizes s. − − − Since the order of u is a p-power, we find that u centralizes s. Thus u is bounded above | | by the maximum order a unipotent element in C (s) = GL (qd1) GL (qdt). GLd(q) ∼ m1 ×···× mt The result now follows from Lemma 2.2. (cid:3) The following corollary is well-known and somehow not surprising. Corollary 2.7. meo(PGL (q)) = (qd 1)/(q 1). d − − Proof. A Singer cycle of PGL (q) has order (qd 1)/(q 1) and so meo(PGL (q)) d d − − ≥ (qd 1)/(q 1). Let g PGL (q). Then g has a unique expression as g =su= us with s d − − ∈ semisimple and u unipotent. We use Notation 2.5 for the element s. By Lemma 2.3 and the proof of Proposition 2.6, we see that if t = 1, so that d = m d , then 1 1 qd1 1 qd 1 g − p⌈logp(m1)⌉ − | | ≤ q 1 ≤ q 1 − − (using Lemma 2.4(i)). If t 2, then ≥ t 1 g lcm (qdi 1)p⌈logp(mi)⌉ i = 1,...,t (qdi 1)p⌈logp(mi)⌉, | | ≤ { − | } ≤ (q 1)t 1 − − − i=1 Y which by Lemma 2.4 (i) is at most 1 t qd 1 qd 1 (qdimi 1) − − . (q 1)t 1 − ≤ (q 1)t 1 ≤ q 1 − − − i=1 − − Y (cid:3) MAXIMAL ELEMENT ORDER 7 Remark2.8. Asonemightexpect,sometimeswehavemeo(Aut(PSL (q))) > (qd 1)/(q d − − 1). For example, PGL (4) = PSL (4) = Alt(5) and meo(PSL (4)) = 5, butAut(Alt(5)) = 2 2 ∼ 2 Sym(5) and meo(Sym(5)) = 6. Later, in Theorem 2.16 (using an application of Lang’s theorem) we will prove that, in fact, meo(Aut(PSL (q))) = (qd 1)/(q 1) in all other d − − cases. Before studying other classical groups we need the following number-theoretic lemma which will be crucial in studying the asymptotic value of meo(PSp (q)) as m tends to 2m infinity (see Corollary 2.10 and Remark 2.11). In the proof of Lemma 2.9, we denote by (a) the largest power of 2 dividing the positive integer a. 2 Lemma 2.9. Let (a ,...,a ) be a partition of d, let q be a prime power and, for each 1 t i∈ {1,...,t}, let εi ∈ {−1,1}. Then lcmti=1{qai−εi}≤ qd+1/(q−1) if q is even or t = 1, and lcmti=1{qai −εi} ≤ qd+1/2(q−1) if q is odd and t ≥ 2. Proof. Set L := lcmti=1{qai −εi}. If t = 1, then L = qd −ε1 ≤ qd +1 = qd(1+1/qd) ≤ qd+1/(q 1) and the lemma is proved. Thus we may assume that t > 1. We argue by − induction on d. Write I = i 1,...,t ε = 1 . If a = a for distinct elements i i j { ∈ { } | − } i,j I then, replacing d by d a and replacing the partition (a ,...,a ) by the same j 1 t ∈ − partition with the part aj removed, it follows by induction that L qd−aj+1/(q 1) ≤ − ≤ qd+1/2(q 1). Therefore, we may assume further that the set a consists of pairwise i i I distinct e−lements. Let α and β be distinct elements of 1,...,t{ a}n∈d write r = gcd(qaα { } − εα,qaβ εβ) and s = (gcd(q 1,2))t−1. Now − − t 1 1 1 L = lcm qai ε (qai +1) (qai 1) qai 1+ qai i=1{ − i} ≤ rs − ≤ rs qai i I i/I i I i I(cid:18) (cid:19)i/I Y∈ Y∈ Y∈ Y∈ Y∈ qd 1 qd 1 (1) = 1+ 1+ . rs qai ≤ rs qk i I (cid:18) (cid:19) k N(cid:18) (cid:19) Y∈ Y∈ Since log(1+x) x for x 0, we have ≤ ≥ 1 1 1 1 log 1+ = log 1+ = . qk qk ≤ qk q 1 k N(cid:18) (cid:19)! k N (cid:18) (cid:19) k N − Y∈ X∈ X∈ Thus L (qd/rs)exp(1/(q 1)). If r 2, then ≤ − ≥ exp(1/(q 1)) exp(1/(q 1)) 1 1 1 q − − + < 1+ = r ≤ 2 ≤ 2 q 1 q 1 q 1 − − − (the second inequality follows from the inequality exp(y) 1 + 2y, which is valid for ≤ 0 y 1), and hence L qd+1/s(q 1) and the result follows. ≤ ≤ ≤ − Thuswemayassumethatqaα εα andqaβ εβ arecoprime,fordistinctα,β 1,...,t . − − ∈ { } In particular, q is even and so s = 1. Consider distinct α,β I. A direct computation ∈ showsthatqaα+1andqaβ+1haveanon-trivialcommonfactorifandonlyif(aα)2 = (aβ)2. Thus in particular, for each k 0, there is at most one i I with (a ) = 2k. From (1), i 2 ≥ ∈ we have 1 1 (2) L qd 1+ qd 1+ ≤ qai ≤ q2k i I (cid:18) (cid:19) k 0(cid:18) (cid:19) Y∈ Y≥ (where in the last inequality we use the fact that if 2k = (ai)2, then 1+1/qai 1+1/q2k). ≤ By expanding the infinite product on the right hand side of (2), we see that 1 1 q 1+ = = q2k qr q 1 k 0(cid:18) (cid:19) r 0 − Y≥ X≥ 8 S.GUEST,J.MORRIS,C.E.PRAEGER,ANDP.SPIGA and the lemma is proved. (cid:3) In the remainder of this section the vector space V admits a non-degenerate form or quadratic form of classical type which is preserved up to a scalar multiple by the preimage in GL (qδ) of the group G. We frequently make use of a theorem of B. Huppert [22, Satz d 2], which we apply to semisimple elements s G that preserve the form. Such elements ∈ generate a subgroup acting completely reducibly on V, and by Huppert’s Theorem, V admits an orthogonal decomposition of the following form which gives finer information than we had in Notation 2.5: (3) V = V V ((V V ) (V V )) + ⊥ − ⊥ 1,1 ⊕ 1′,1 ⊥··· ⊥ 1,m1 ⊕ 1′,m1 ⊥ ··· ((V V ) (V V )) ⊥ r,1⊕ r′,1 ⊥ ··· ⊥ r,mr ⊕ r′,mr ⊥ (Vr+1,1 ⊥ ··· ⊥ Vr+1,mr+1)⊥ ··· ⊥ (Vt′,1 ⊥ ··· ⊥ Vt′,mt′) where V and V are the eigenspaces of s for the eigenvalues 1 and 1, of dimensions + − − d and d , respectively (note V is non-degenerate if d > 0 and we set d = 0 if q is + even), an−d each V is an irredu±cible F s -submodule.±Moreover for i = −r + 1,...,t, i,j qδh i ′ V is non-degenerate of dimension 2d /δ and s induces an element y of order dividing i,j i i,j qdi +1 on Vi,j (in the unitary case δ = 2 and the dimension di is odd). For i = 1,...,r, V and V are totally isotropic of dimension d /δ (here d is even if δ = 2), V V i,j i′,j i i i,j ⊕ i′,j is non-degenerate, and s induces an element yi,j of order dividing qdi 1 on Vi,j while − inducing the adjoint representation (y 1)tr on V (where xtr denotes the transpose of the i−,j i′,j matrix x). For our claims about the orders of the y , we also refer to [8, 23] for some ij standard facts on the structure of the maximal tori of the fnite classical groups. We denote by CSp (q) the conformal symplectic group, that is, the elements of 2m GL (q) preserving a given symplectic form up to a scalar multiple. Also PCSp (q) 2m 2m denotes the projection of CSp (q) in PGL (q). From [10, Table 5, page xvi], we have 2m 2m PCSp (q) : PSp (q) = gcd(2,q 1). In the rest of this section, by abuse of notation, 2m 2m | | − we write p⌈logp(0)⌉ = 1. Lemma 2.10. meo(PCSp (q)) qm+1/(q 1). 2m ≤ − Proof. Using Corollary 2.7 and the fact that PCSp (q) = PGL (q), we may assume that 2 ∼ 2 m 2. Let g be an element of PCSp (q) and write g = su = us with s semisimple and 2m ≥ u unipotent. We use Notation 2.5 for the element s. First suppose that g PSp (q), 2m ∈ and let g,s,u Sp (q) correspond to g,s,u, respectively. Consider the orthogonal s- ∈ 2m invariant decomposition of V given by (3) (and note that in this case δ = 1). Here V + and V have even dimension, and we write 2m := dimV , 2m := dimV . Note that, + + for 1 − i r, V and V are isomorphic F s -modules if and− only if y− acts as the ≤ ≤ i,j i′,j qh i i,j multiplication by 1 or 1 on V , and by definition of V this is not the case; thus V i,j i,j − ± and V are non-isomorphic. i′,j Now m = m++m +m1d1+ +mt′dt′, and by the information from (3) on the orders − ··· of the y , and the result in Proposition 2.6 (using the notation from Notation 2.5) about i,j the order of u, we see that the order of g is at most r t′ (4) lcm qdi 1 lcm qdi +1 max p⌈logp(2m±)⌉,p⌈logp(mi)⌉ i = 1,...,t′ . i=1{ − }·i=r+1{ }· { | } UsingLemma2.4, fori = 1,...,r, weseethatbyreplacing theaction of g on(V V ) i,1⊕ i′,1 ⊕ ···⊕(Vi,mi⊕Vi′,mi)withtheaction given byasemisimpleelement oforderqdimi−1(andso having only two totally isotropic irreducible F s -submodules), we obtain an element g q ′ h i such that g divides g and m = 1. In particular, replacing g by g if necessary, we may ′ i ′ | | | | assumethat g = g . With a similar argument, for those i r+1,...,t with m odd and ′ ′ i ∈{ } (p,d ,m ,f) = (2,1,3,1), we may assume that m = 1. Also, applying again Lemma 2.4, i i i 6 for i r+1,...,t , we may assume that if m is even, then (d ,m ,f)= (1,2,1). ′ i i i ∈ { } MAXIMAL ELEMENT ORDER 9 Supposethat, for some i r+1,...,t , we have (p,d ,m ,f)= (2,1,3,1). Theele- 0 ∈ { ′} i0 i0 mentg inducesonW := Vi0,1 ⊥ Vi0,2 ⊥ Vi0,3 anelementoforderdividing(q+1)p⌈logp(3)⌉ = 22 3. Let g be the element acting as g on W , inducing an element of order q +1 on ′ ⊥ · V and inducing a regular unipotent element on V V . Now, g induces on W an i0,1 i0,2 ⊥ i0,3 ′ element of order (q+1)p⌈logp(4)⌉ = 22 3. Therefore g = g′ and so, we may replace g by · | | | | g (note that in doing so the dimension of V increases by 2 and m decreases from 3 to ′ + i0 1). In particular, we may assume that m = 1 for each i r+1,...,t with m odd. i ′ i ∈ { } Supposethat, for some i r+1,...,t , we have (d ,m ,f)= (1,2,1). Theelement 0 ∈{ ′} i0 i0 g induces on W = Vi0,1 ⊥ Vi0,2 an element of order dividing (p+1)p⌈logp(2)⌉ = (p+1)p. Let g be the element acting as g on W , inducing an element of order p + 1 on V ′ ⊥ i0,1 and inducing an element of order p on V . Now, g induces on W an element of order i0,2 ′ (p+1)p. Therefore g = g and so, replacing g by g if necessary, we may assume that ′ ′ | | | | mi = 1, for each i r+1,...,t′ . Thus m = m++m +d1+ +dt′. ∈ { } − ··· Now, using Lemma 2.9, we see that the element g has order at most r t′ (5) lcm qdi 1 lcm qdi +1 max p⌈logp(2m+)⌉,p⌈logp(2m−)⌉ i=1{ − }·i=r+1{ }· { } qm+1 m+ m− qm+1 − − max p⌈logp(2m+)⌉,p⌈logp(2m−)⌉ ≤ q 1 { }≤ q 1 − − (where the last inequality follows from an easy computation). This proves the result for elements g PSp (q). If q is even then PCSp (q) = PSp (q), and the proof is ∈ 2m 2m 2m complete. Thus we may assume that q is odd, and in this case, by Lemma 2.9, the upper bound is reduced to qm+1/(2(q 1)) if t 2. ′ − ≥ We must consider elements g PCSp (q) PSp (q). Now g2 PSp (q) and we ∈ 2m \ 2m ∈ 2m have just shown that g2 qm+1/(2(q 1)) if the parameter t for g2 is at least 2, and ′ | | ≤ − hence in this case g qm+1/(q 1). Thus we may assume that t 0,1 . If t = 0 then ′ ′ | | ≤ − ∈{ } g2 max p⌈logp(2m+)⌉,p⌈logp(2m−)⌉ p⌈logp(2m)⌉ qm+1/2(q 1), | | ≤ { }≤ ≤ − where the last inequality holds unless (m,q) = (2,3) (this follows from a direct computa- tion). We verify directly the claim of the lemma for PCSp (3). Therefore we may assume 4 that the parameter t = 1 for g2. ′ In this case the parameters for g2 satisfy m = m +m +d . If m = m = 0 then + 1 + g2 is semisimple with eigenvalues λ,λ 1,λq,λ q,...,λqm−−1,λ qm−1, where λ−qm 1 = 1. − − − ± In particular, gqm 1 = I and so g has order at most qm + 1, which is less than ± 2m ± qm+1/(q 1). Thus we may assume that m + m > 0. Now (5) gives g2 (qd1 + + 1)max p−⌈logp(2m+)⌉,p⌈logp(2m−)⌉ . To bound the rig−ht hand side, we may|as|su≤me that { } m = 0 and m = d +m . A direct computation shows that, since q is odd, this bound is 1 + les−sthanqm+1/2(q 1)(andhence g qm+1/(q 1))whenm 2unless(q,m ) = (3,2) + + − | | ≤ − ≥ and g2 has order 9(3m 2 +1). If m = 1 then either g2 is semisimple and has order at − + most qm 1+1, which is less than qm+1/2(q 1), or g2 = J +h whereh has order dividing − 2 − qm 1 1. The eigenvalues of g2 are therefore λ ,...,λ , with each λ = 1 and all − 1 2m 2 i ± − 6 ± distinct, and 1 with algebraic multiplicity 2. The eigenvalues of g are therefore a, a, ν , 1 ..., ν where a = 1 and each ν2 = λ ; and since g is not semisimple, the eigenvalue 2m−2 ± i i a must have algebraic multiplicity 2. However g is a similarity with respect to the skew- symmetric form J; that is gTJg = µJ for some µ F and therefore J 1gTJ = µg 1. q − − ∈ In particular, g and µg 1 are GL (q)-conjugate and have the same eigenvalues with the − n same algebraic multiplicities. So since a is an eigenvalue of g with algebraic multiplicity 2, so is aµ and we must have µ = 1. But then g PSp (q), contradicting our assumption. ∈ 2m Finally suppose that (q,m ) = (3,2) and g2 has order 9(3m 2+1). Then the eigenvalues + − of g2 are 1,λ ,...,λ , where 1 has algebraic multiplicity 4, the λ are distinct and 1 2m 4 i − λ = 1. It follows that the eigenvalues of g are a,ν ,...,ν , where a = 1 has i 1 2m 4 6 ± − ± 10 S.GUEST,J.MORRIS,C.E.PRAEGER,ANDP.SPIGA algebraic multiplicity 4, and each ν2 = λ (since 9 divides g ). Again, since gTJg = µJ, i i | | it follows that aµ is also an eigenvalue of g with algebraic multiplicity 4, and therefore µ = 1 and g PSp (q), which is a contradiction. (cid:3) 2m ∈ Remark2.11. WenotethatCorollary2.10is,forqeven,asymptoticallythebestpossible. Indeed, let q be a 2-power, let k be a positive integer and let s be a semisimple element Vof1P⊥S·p·2·k+⊥1−V2k(qw)i∼=thSdpim2k+Fq1−V2i(=q).2iSaunpdpowseiththsatintdhuecninagtuornalVFiqahnsie-mlemodeunlteoVf odredceormqp2io−s1e+s a1s. (This is the decomposition of (3) for s where we have V = 0,r = 0,t = k and for each ′ ± i, m = 1,d = i.) Now, we have i i s = lcm q+1,q2+1,q22 +1,...,q2k−1 +1 = (q+1)(q2+1) (q2k−1 +1) | | { } ··· k 1 = q2k 1 − 1+ 1 , − q2i i=0(cid:18) (cid:19) Y which approaches q2k/(q 1) as k tends to infinity. − Moreover, theextracare thatwe usedinhandlingthesubspacesV andV in theproof + − of Corollary 2.10 may seem ostensibly artificial and unnecessary. However we remark that themaximumorderofanelementgofPSp (2)is23 (2+1) (22+1) (24+1) (28+1)(see[23, 36 · · · · p. 808]). Such an element g can be chosen to be of the form su = us (with u unipotent andssemisimple), wheretheelementufixesa30-dimensionalsubspacepointwiseandacts as a regular unipotent element on a 6-dimensional subspace W, and where the element s acts trivially on W. In particular, this shows that the contribution of V and V are + − sometimes essential in achieving the maximum element order of PSp (q). 2m The following result is a consequence of Lemma 2.10 and results in [23]. Corollary 2.12. Let q = pf with p a prime. For m 3, we have meo(PGO (q)) 2m+1 ≥ ≤ qm+1/(q 1) (with q odd), and for m 4 and ε +, , we have meo(PGOε (q)) − ≥ ∈ { −} 2m ≤ qm+1/(q 1). − Proof. If q is odd, then the result follows by comparing qm+1/(q 1) with the maximum − element order of the orthogonal groups obtained in [23]. Now, assume that q is even. It is well-known that orthogonal groups of characteristic 2 are subgroups of the symplec- tic groups, that is, PGOε (q) PCSp (q), for ε +, (see [8, Section 5] or [25, 2m ≤ 2m ∈ { −} Table 3.5.C]). It follows from Lemma 2.10 that meo(PGOε (q)) qm+1/(q 1), for 2m ≤ − ε +, . (cid:3) ∈ { −} Thenexttwolemmaswillbeusedforcomputingthemaximumelementorderforunitary groups. Lemma 2.13. Let (b ,...,b ) be a partition of d and let q be a prime power. If t 2, then 1 t ≥ lcmti=1{qbi −(−1)bi} ≤ qd−1−(−1)d−1. Moreover (qd−(−1)d)/(q+1) ≤ qd−1−(−1)d−1. Proof. For the firstpart of the lemma, we argue by induction on t. Note that q+1 divides qbi ( 1)bi for each i 1,...,t . If t = 2, then − − ∈ { } (qb1 ( 1)b1)(qb2 ( 1)b2) lcm qb1 ( 1)b1,qb2 ( 1)b2 − − − − qd−1 ( 1)d−1 { − − − − } ≤ q+1 ≤ − − (where the last inequality follows from a direct computation). Assume that t 3. Now, ≥ by induction, lcmti=−11{qbi −(−1)bi} ≤ qd−bt−1−(−1)d−bt−1. Therefore t 1 t 1 lcm qbi ( 1)bi lc−m qbi ( 1)bi (qbt ( 1)bt) i=1{ − − } ≤ q+1 i=1{ − − } − − (cid:18) (cid:19) (qd bt 1 ( 1)d bt 1)(qbt ( 1)bt) − − − − − − − − qd−1 ( 1)d−1 ≤ q+1 ≤ − −