JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY Volume 12, Number 2, April 1999, Pages 497–520 S 0894-0347(99)00288-X

SIMPLE GROUPS, PERMUTATION GROUPS, AND PROBABILITY

MARTIN W. LIEBECK AND ANER SHALEV

1. Introduction

In recent years probabilistic methods have proved useful in the solution of several problems concerning finite groups, mainly involving simple groups and permutation groups. In some cases the probabilistic nature of the problem is apparent from its very formulation (see [KL], [GKS], [LiSh1]); but in other cases the use of probability, or counting, is not entirely anticipated by the nature of the problem (see [LiSh2], [GSSh]).

In this paper we study a variety of problems in finite simple groups and finite permutation groups using a unified method, which often involves probabilistic arguments. We obtain new bounds on the minimal degrees of primitive actions of classical groups, and prove the Cameron-Kantor conjecture that almost simple primitive groups have a base of bounded size, apart from various subset or subspace actions of alternating and classical groups. We use the minimal degree result to derive applications in two areas: the first is a substantial step towards the Guralnick-Thompson genus conjecture, that for a given genus g, only finitely many non-alternating simple groups can appear as a composition factor of a group of genus g (see below for definitions); and the second concerns random generation of classical groups. Our proofs are largely based on a technical result concerning the size of the intersection of a maximal subgroup of a classical group with a conjugacy class of elements of prime order.

We now proceed to describe our results in detail.

1.1. Intersections of maximal subgroups and conjugacy classes of classical groups. Let G be a finite almost simple group with socle G_{0}, a classical group with natural module V over a field of characteristic p. We say that a maximal subgroup M of G is a subspace subgroup if it is reducible on V, or is an orthogonal group on V embedded in a symplectic group with p = 2; more specifically, M is a subspace subgroup if one of the following holds:

(1) M = G_{U} for some proper non-zero subspace U of V, where U is totally singular, non-degenerate, or, if G is orthogonal and p = 2, a non-singular 1-space (U is any subspace if G_{0} = P SL(V));

\begin{matrix}c \\ ◯ \end{matrix}1999 American Mathematical Society

Received by the editors May 14, 1998 and, in revised form, August 26, 1998.

1991 Mathematics Subject Classification. Primary 20D06; Secondary 20P05.

The second author acknowledges the support of the Israel Science Foundation, administered by the Israeli Academy of Sciences and Humanities.

(2) G_{0} = P SL(V), G contains a graph automorphism of G_{0}, and M = G_{U,W} where U, W are proper non-zero subspaces of V, dim V = dim U +dim W and either U ⊆ W or V = U ⊕ W;

(3) G_{0} = Sp_{2m}(q), p = 2 and M ∩ G_{0} = O_{2m}^{±}(q). Note that in (3), if we regard G_{0} as the isomorphic orthogonal group O_{2m+1}(q), then M ∩ G_{0} = O_{2m}^{±}(q) is the stabilizer of a subspace of the natural module of dimension 2m + 1.

If M is a subspace subgroup, we call the action of G on the coset space (G : M) a subspace action of the classical group G.

All the results in this paper rely on the following theorem, which for sentimental reasons we do not number, but refer to as (⋆).

Theorem (⋆). There is a constant ϵ > 0, such that if G is any almost simple classical group, M is a maximal subgroup of G which is not a subspace subgroup, and x ∈ G is an element of prime order, then

|x^{G} ∩ M| < |x^{G}|^{1−ϵ}.

1.2. Minimal degrees. Let G be a permutation group on a set Ω. We let fix(g) denote the number of fixed points of an element g ∈ G. Let G^{♯} = G\{1}. The fixity fix(G) of G is defined by fix(G) = max{fix(g) : g ∈ G^{♯}}. The minimal degree m(G) of G is defined by m(G) = |Ω| − fix(G), and coincides with the minimal support of a non-identity element of G. The fixity ratio (or fixed point ratio) rfix(g) of an element g ∈ G is defined by rfix(g) = fix(g)/|Ω|. We also set rfix(G) = fix(G)/|Ω|. If G is an abstract group and M is a subgroup of G, then we let fix(G, M) and rfix(G, M) denote the fixity and the fixity ratio of the permutation group obtained from the action of G on the cosets of M. For g ∈ G, fix(g, M) and rfix(g, M) are defined in a similar manner.

The fixity and the minimal degree of primitive permutation groups have been studied extensively since the days of Jordan, with numerous applications. The best elementary (i.e. classification-free) bound was obtained by Babai [Ba], who showed that if G is a primitive group on a set Ω of size n, then m(G) ≥ (\sqrt{n}−1)/2, provided G does not contain the alternating group on Ω. Using the Classification Theorem, Liebeck and Saxl [LS] showed that rfix(G) ≤ 2/3 with some known exceptions (the 2/3 bound has recently been improved to 1/2 by Guralnick and Magaard [GM]). In fact the principal result of [LS] deals with almost simple groups, showing that if G is an almost simple group of Lie type over 𝔽_{q}, then for every primitive action of G we have rfix(G) ≤ \frac{4}{3q} (with a few exceptions when soc(G) = L_{2}(q), L_{4}(2) or P Sp_{4}(3)).

The following result gives a much stronger bound for classical groups, provided subspace actions are excluded.

Theorem 1.1. There is a constant ϵ > 0 such that if G is an almost simple classical group over 𝔽_{q}, with natural module of dimension n, and M is a maximal subgroup of G which is not a subspace subgroup, then

rfix(G, M) < q^{−ϵn}.

Note that such a result is not valid for subspace actions, where the fixity ratio is sometimes as large as q^{−1} (roughly). However, results from [Shi] and [GK] show that similar bounds also hold if M is a subspace subgroup, provided the subspace stabilized is not of dimension less than δn (or > n − δn), where δ = δ(ϵ).

1.3. The genus conjecture. The bound obtained in Theorem 1.1 can be applied in several contexts. First, we use it in order to obtain a partial solution to the genus conjecture of Guralnick and Thompson [GT].

To state this, let G be a finite group acting faithfully and transitively on a set Ω of size n, and let E = {x_{1}, …, x_{k}} be a generating set for G with x_{1} … x_{k} = 1. If x ∈ G has cycles of length r_{1}, …, r_{l} in its action on Ω, define the index ind(x) = ∑_{1}^{l}(r_{i} − 1). The genus g = g(G, Ω, E) is defined by

2(n + g − 1) = ∑_{i=1}^{k} ind(x_{i}),

and the genus g(G, Ω) of the permutation group (G, Ω) is the minimum value of g(G, Ω, E) over all such generating sets E. We say that G is a group of genus g if there is a faithful transitive G-set Ω such that g(G, Ω) ≤ g. Such a group is the monodromy group of a cover X → Y, where X is a compact connected Riemann surface of genus g and Y is the Riemann sphere (see [Gu] for background). Groups of genus g (particularly the case g = 0) have been extensively studied; for a survey, see [Gu]. The main conjecture in the subject, the Guralnick-Thompson genus conjecture [GT], states that if E(g) is the set of non-abelian, non-alternating composition factors of groups of genus g, then E(g) is finite for each g.

The genus conjecture was reduced to the almost simple case in [Gu, 5.1]. More specifically, one is required to show that only finitely many almost simple groups of Lie type have primitive permutation representations of given genus g.

Thus let G be an almost simple group of Lie type over the field 𝔽_{q}. It is shown in [LS] that if G has genus g, then q is bounded in terms of g. Therefore, in order to prove the conjecture it suffices to deal with classical groups in arbitrarily large dimension. The case g = 0 and G = L_{n}(q) was settled by Shih [Shi]. Recently it has been shown in [LP] that only finitely many classical groups G have primitive permutation representations of genus g provided the point-stabilizer M lies in the class S in Aschbacher’s classification of maximal subgroups of classical groups (see [As, KLi]). Here we extend this result to all but subspace actions.

Theorem 1.2. For any integer g ≥ 0 there are only finitely many classical groups in non-subspace actions having genus g.

Therefore, in order to complete the proof of the genus conjecture, it remains to deal with subspace actions of classical groups.

1.4. Base size. Recall that a base of a permutation group G on a set Ω is a subset B ⊆ Ω whose pointwise stabilizer G_{(B)} is trivial. Bases arise in estimating the orders of primitive permutation groups, and also play an important role in computational group theory (in various polynomial-time algorithms). Denote by b(G) the minimal size of a base for G. There are several conjectures suggesting upper bounds on b(G). A conjecture of Cameron and Kantor [Ca1, Conjecture 3.4, p. 343], [CK, p. 260], [Ca2, p. 638] concerns almost simple primitive groups G; it states that for such groups, b(G) is bounded by some absolute constant, unless G lies in a prescribed list of exceptions. Our next result settles this conjecture in the affirmative.

Theorem 1.3. There exists an absolute constant c such that for any almost simple primitive permutation group G, one of the following holds:

(i) G is A_{n} or S_{n} acting on k-subsets of {1, …, n} or on partitions of {1, …, n} into k parts of size n/k;

(ii) G is a classical group in a subspace action; (iii) b(G) ≤ c. Furthermore, excluding G as in (i) or (ii), the probability that a random c-tuple of elements from the permutation domain forms a base for G tends to 1 as |G| → ∞.

We note that b(G) is unbounded for the groups in parts (i)–(ii), since the orders of these groups are not bounded by a fixed polynomial function of their degree. The last statement in Theorem 1.3 is in fact conjectured explicitly in [CK].

Another conjecture concerning base size was recently settled in [GSSh]. It was shown there that, if G is a primitive permutation group not involving A_{d} (that is, having no section isomorphic to A_{d}), then b(G) ≤ f(d) for some function of f depending only on d. The function obtained in [GSSh] is quadratic, and it was asked whether a similar result holds with a linear function. The answer is provided by

Theorem 1.4. Let G be a primitive permutation group not involving A_{d}. Then b(G) is bounded above by a linear function of d.

1.5. Random generation. In spite of considerable progress in the study of generation, and random generation, of finite simple groups, some natural problems still remain open.

It has recently been shown [Di, KL, LiSh1] that a randomly chosen pair of elements of a finite simple group G generates G with probability → 1 as |G| → ∞. An interesting related problem, which first arose in [KL], deals with generation by a fixed element and a randomly chosen one. Given an element x ∈ G, let P_{x}(G) denote the probability that ⟨x, y⟩ = G, where y ∈ G is randomly chosen, and set P^{−}(G) = min{P_{x}(G) : x ∈ G^{#}}. It was conjectured in [KL] that P^{−}(G) → 1 as |G| → ∞, but this was refuted in [GKS]. While the cases of alternating groups and groups of Lie type over fields of bounded size are now well-understood (P^{−}(G) is bounded away from 1 in these cases), the behaviour of P^{−}(G) for classical groups G over unbounded fields is still unclear. We settle this as follows.

Theorem 1.5. Let G be a classical simple group in dimension n over the field 𝔽_{q}. Suppose q → ∞. Then P^{−}(G) → 1, regardless of n.

If n is bounded, then the result is proved in [GKS], so it remains to consider the case where both q and n tend to infinity, which is what we do here. We note that the case G = L_{n}(q) is settled in [Sh1] using different methods.

The next problem, posed by G. Robinson, deals with random generation of simple groups by two conjugate elements. Suppose we choose at random x ∈ G and then we choose at random a conjugate x^{y} of x. What can be said of the probability that ⟨x, x^{y}⟩ = G?

Theorem 1.6. Let G be a classical simple group, and let x, y be randomly chosen elements of G. Then the probability that ⟨x, x^{y}⟩ = G tends to 1 as |G| → ∞.

This extends results from [Sh2]. In fact Theorem 1.6 has recently been extended to all simple groups G in [GLSS].

1.6. Structure of the paper. There are three further sections. In the first, we assume Theorem (⋆) to be true, and deduce Theorems 1.1–1.6. The second and third comprise the proof of Theorem (⋆).

2. Proofs of the main results

In this section we assume that Theorem (⋆) holds, and use it to derive Theorems 1.1–1.6.

Denote by Cl(n, q) the set of almost simple groups whose socle is a classical group over 𝔽_{q} with natural module of dimension n, and by Cl_{n}(q) a quasisimple group with central factor group in Cl(n, q).

Proof of Theorem 1.1. Let G ∈ Cl(n, q), and let M be a maximal subgroup of G which is not a subspace subgroup. Write Ω for the coset space (G : M). Let x ∈ G be a non-trivial element with a maximal number of fixed points on Ω. Then fix(x) = fix(G), and by replacing x with a non-trivial power if necessary, we can assume that x has prime order. We have

rfix(G) = fix(x)/|Ω| = |x^{G} ∩ M|/|x^{G}|.

By Theorem (⋆), therefore, rfix(G) < |x^{G}|^{−ϵ}. Now all conjugacy classes of G have size greater than P (G), the smallest degree of a faithful permutation representation of G, and lower bounds for P (G) are given in [KLi, 5.2.2]. In particular we see that, excluding a finite number of possibilities for G, we have P (G) > q^{n/2}. Consequently rfix(G) < q^{−ϵn/2}, proving Theorem 1.1.

Proof of Theorem 1.2. Fix an integer g ≥ 0. Let G ∈ Cl(n, q) act faithfully and primitively on a set Ω of size m, where (G, Ω) is not a subspace action, and suppose g(G, Ω) = g.

Assume rfix(G) ≤ \frac{1}{86}. Then fix(x) ≤ m/86 for all 1 ≠ x ∈ G, whence ind(x) ≥ (85(d − 1)m)/(86d), where d is the order of x (and ind(x) is as defined in §1.3). Now G has a generating set x_{1}, …, x_{k} such that x_{1} … x_{k} = 1 and ∑ ind(x_{i}) = 2m − 2 + 2g. Therefore, writing d_{i} for the order of x_{i}, we have

\frac{85}{86}m ∑ \frac{d_{i} − 1}{d_{i}} ≤ 2m − 2 + 2g.

If ∑(d_{i} − 1)/d_{i} ≥ 85/42, it follows that m < cg for some constant c. Otherwise, one of the following holds:

(1) k = 4, (d_{1}, d_{2}, d_{3}, d_{4}) = (2, 2, 2, 2);

(2) k = 3, ∑(1/d_{i}) ≥ 1;

(3) k ≤ 2. In each case G is either solvable or isomorphic to A_{5} (see [Ma, Chapter II]).

We conclude that there are only finitely many possibilities for non-subspace actions (G, Ω) satisfying g(G, Ω) = g and rfix(G) ≤ 1/86. On the other hand, by Theorem 1.1 there are also only finitely many possibilities for non-subspace actions (G, Ω) of classical groups G such that rfix(G) > 1/86. Theorem 1.2 follows.

Proof of Theorem 1.3. Let G be an almost simple primitive permutation group on a set Ω, and suppose (G, Ω) is not as in (i) or (ii) of Theorem 1.3. We shall show that for a suitably chosen constant b, almost every b-tuple of elements of Ω forms a base for G. If G is alternating or symmetric, this holds with b = 2, by [CK, Theorem 2.2]. If G is a group of Lie type in bounded dimension, the assertion follows from [GSSh]. Thus it remains to deal with classical groups G ∈ Cl(n, q) of large dimension. Let Q(G, b) denote the probability that a randomly chosen b-tuple from Ω does not form a base for G. Let P denote the set of elements of prime order in G, and let x_{1}, …, x_{r} be a set of representatives for the G-conjugacy classes of elements of P. Let M be the stabilizer of a point in Ω (so that M is a maximal subgroup of G).

Note that, for a given x ∈ G, the probability that a randomly chosen point of Ω is fixed by x is rfix(x). Therefore the probability that a randomly chosen b-tuple of elements of Ω is fixed by x is rfix(x)^{b}. Now, if a b-tuple is not a base, then it is fixed by some element x ∈ G of prime order. This yields

Q(G, b) ≤ ∑_{x∈P} rfix(x)^{b} = ∑_{i=1}^{r} |x_{i}^{G}| · (|M ∩ x_{i}^{G}|/|x_{i}^{G}|)^{b} = ∑_{i=1}^{r} |M ∩ x_{i}^{G}|^{b}/|x_{i}^{G}|^{b−1}.

Since by assumption, (G, Ω) is not a subspace action, Theorem (⋆) gives

|M ∩ x_{i}^{G}| ≤ |x_{i}^{G}|^{1−ϵ} (1 ≤ i ≤ r).

Combining the above inequalities we find that

Q(G, b) ≤ ∑_{i=1}^{r} |x_{i}^{G}|^{b(1−ϵ)−(b−1)} = ∑_{i=1}^{r} |x_{i}^{G}|^{1−bϵ}.

Suppose b > ϵ^{−1}. Then 1 − bϵ < 0, and

Q(G, b) < r · |C|^{1−bϵ},

where C is a conjugacy class of minimal size in G. As observed in the proof of 1.1, we have |C| ≥ q^{n/2} (recall G ∈ Cl(n, q)). On the other hand, if l is the (untwisted) Lie rank of G, and k(G) is the number of conjugacy classes in G, then by [LPy, Theorem 1] we have

r ≤ k(G) ≤ (6q)^{l}|G : soc(G)|,

and this is less than q^{4n} (note that |G : soc(G)| ≤ |Out(soc(G))|).

Hence, letting b ≥ 11ϵ^{−1}, say, we have 1 − bϵ ≤ −10, so

Q(G, b) ≤ r|C|^{−10} ≤ q^{4n}q^{−5n} = q^{−n}.

Thus Q(G, b) → 0 as |G| → ∞. Hence, with this choice of b, almost all b-tuples form a base, and the Cameron-Kantor conjecture follows. Note that in [CK] this conjecture is already formulated in the probabilistic form established here.

Proof of Theorem 1.4. For d ≥ 5, let Γ_{d} denote the class of finite groups which do not involve A_{d}. Let G ∈ Γ_{d} be a primitive permutation group. We have to bound b(G) by a linear function of d. The proof in [GSSh] shows that it suffices to consider two cases:

(1) the case where G is almost simple, and

(2) the case where G = V H ≤ AGL(V) is of affine type and H is a primitive (irreducible) subgroup of GL(V).

Indeed, if the base size of G is bounded by f(d) in these two case, then [GSSh] shows that the base size of a general primitive group G in Γ_{d} will be at most 20 + 2 log d + f(d).

We first handle case (1). Suppose G ∈ Γ_{d} is almost simple. By Theorem 1.3, we may assume G is as in (i) or (ii) of 1.3, since otherwise the base size of G is bounded. It is shown in [GSSh] that if soc(G) is alternating, then b(G) is bounded by a linear function of d (this follows from known bounds on the maximal length of a chain of subgroups in G). Therefore we can assume that G is as in 1.3(ii), namely a subspace action of a classical group G ∈ Cl(n, q). Since G ∈ Γ_{d}, we have n = O(d), so it suffices to show that b(G) ≤ cn. This is done by explicit construction in [Li2, p. 14].

This completes the proof in the almost simple case.

Now consider the affine case (2). Here G = V H ≤ AGL(V) is of affine type, acting on the set of vectors in V, where H is a primitive subgroup of GL(V) = GL_{n}(q) (q = p^{a}). Observe that AGL(V) itself has a base of size n + 1; hence we may assume that n is large. In order to resolve this case we need some preparations.

Lemma 2.1. Let H be a primitive irreducible subgroup of GL(V) = GL_{n}(q) (with n large). Then one of the following holds:

(i) |H| < |V |^{3}; (ii) H stabilizes a tensor product decomposition V = V_{1} ⊗V_{2}: here H ≤ GL_{n_{1}}(q)∘

GL_{n_{2}}(q) with n = n_{1}n_{2} and n_{1}, n_{2} > 1; (iii) H lies between a quasisimple subgroup S and its normalizer in GL(V): either

S is an alternating group A_{k} and V is a minimal module for S (of dimension k − 1 or k − 2), or S is a classical group in Cl(\frac{n}{t}, q_{0}) for some t dividing n and some subfield 𝔽_{q_{0}} of 𝔽_{q^{t}}.

Proof. Choose t maximal such that H lies in a subgroup X = GL_{n/t}(q^{t}).t of GL_{n}(q) (in its natural embedding). Observe that (i) holds if n/t = 1; hence we may assume that n/t ≥ 2. Now choose a classical group Y = Cl_{n/t}(q_{0}) ≤ X (𝔽_{q_{0}} ⊆ 𝔽_{q^{t}}), minimal such that H ≤ N_{X}(Y).

We apply Aschbacher’s theorem [As] to the subgroup H of the classical group N_{X}(Y). According to this, either H contains Y, or H lies in a subgroup in one of the families C_{i} (1 ≤ i ≤ 8), or H is the normalizer of an irreducible quasisimple subgroup (we say H ∈ S in the latter case); see [KLi] for detailed descriptions of these families.

If H contains Y, then (iii) holds. If H ∈ S, then by [Li1, 4.1], either (i) holds, or (iii) holds with S = A_{k}.

Now suppose H ≤ M with M a subgroup in the family C_{i}. As H is primitive and irreducible, i ≠ 1, 2; by choice of X and Y, i ≠ 3, 5, 8. If i = 4, then M is a tensor product subgroup, and (ii) holds. If i = 6, then M ≤ (𝔽_{q^{t}}^{∗} ∘r^{1+2a}).Sp_{2a}(r).x, where n/t = r^{a}, r is prime and x divides n. This yields

|H| < q^{n}r^{3a}r^{2a^{2}}n ≤ q^{n}n^{3}n^{2 log n+1} < q^{3n},

provided n is large (as assumed). Finally, if H is contained in a member of C_{7}, then there are a, t > 1 with n = a^{t} and H ≤ (GL_{a}(q) ∘ … ∘ GL_{a}(q)).S_{t}; this yields

|H| < q^{a^{2}t}t! ≤ q^{3a^{t}} = q^{3n}.

Thus (i) holds. ♠

A sequence of vectors v_{1}, …, v_{k} will be called a strong base for H if the only elements of H which leave the subspaces ⟨v_{1}⟩, …, ⟨v_{k}⟩ invariant are scalars. Define b^{∗}(H) to be the minimal size of a strong base for H.

Lemma 2.2. There exists a constant c such that, if H ∈ Γ_{d} is a primitive subgroup of GL(V), then b^{∗}(H) ≤ cd.

Proof. It is shown in [GSSh, Theorem 5.3] that there is an absolute constant c_{1} such that if G = V H ≤ AGL(V), where H ∈ Γ_{d} is a primitive subgroup of GL(V), then in the action on V,

rfix(G) ≤ |V |^{−1/c_{1}d}.

This shows that, if h ∈ H is fixed and is not scalar, and v ∈ V is randomly chosen, then the probability P_{h} that h leaves ⟨v⟩ invariant is at most ∑_{λ∈𝔽_{q}^{∗}} rfix(λh) <

qrfix(G) ≤ q|V |^{−1/c_{1}d}.

Suppose V = (𝔽_{q})^{n}, and proceed by induction on n = dim V. Note that b^{∗}(GL(V)) = dim V + 1, so the result follows if n = O(d). We can therefore assume that n > 2c_{1}d, where c_{1} is as above. Hence q < |V |^{1/2c_{1}d}, so

P_{h} ≤ q|V |^{−1/c_{1}d} < |V |^{−1/2c_{1}d}.

Now choose at random v_{1}, …, v_{k} ∈ V, and let Q^{∗}(H, k) denote the probability that v_{1}, …, v_{k} do not form a strong base for H. Then

Q^{∗}(H, k) ≤ ∑_{h∈H\Z(H)} P_{h}^{k} < |H||V |^{−k/2c_{1}d}.

It follows that, if |H| < |V |^{3}, and k ≥ 6c_{1}d, then Q^{∗}(H, k) < 1, so b^{∗}(H) ≤ 6c_{1}d.

We now apply Lemma 2.1. If H satisfies 2.1(i), then the linear bound on b^{∗}(H) is already obtained.

Now suppose H satisfies 2.1(ii). Then we have n = n_{1}n_{2} for some n_{1}, n_{2} > 1 and H ≤ GL_{n_{1}}(q) ∘ GL_{n_{2}}(q). Let H_{i} be the projection of H to GL_{n_{i}}(q) (i = 1, 2). Then H_{i} ≤ GL(V_{i}), H_{i} ∈ Γ_{d} and H ≤ H_{1} ∘ H_{2}. By induction on dim V we have b^{∗}(H_{i}) ≤ cd (i = 1, 2).

We now claim that

b^{∗}(H_{1} ∘ H_{2}) ≤ max{b^{∗}(H_{1}), b^{∗}(H_{2})}

(where b^{∗}(H_{i}) refers to the minimal strong base size of H_{i} on V_{i}). To show this, let b = max{b^{∗}(H_{1}), b^{∗}(H_{2})} and let v_{ij} ∈ V_{i} (j = 1, …, b) be a strong base for H_{i} (i = 1, 2). Set v_{j} = v_{1j} ⊗v_{2j}. We assert that v_{1}, …, v_{b} is a strong base for H_{1} ⊗H_{2}. Indeed, let h = h_{1}h_{2} where h_{i} ∈ H_{i}, and suppose h keeps all the subspaces ⟨v_{j}⟩ invariant. Then

h(v_{j}) = h_{1}(v_{1j}) ⊗ h_{2}(v_{2j}) = λv_{1j} ⊗ v_{2j},

for some λ ∈ 𝔽_{q}. This implies h_{i}(v_{ij}) ∈ ⟨v_{ij}⟩ for all i, j. Thus h_{1}, h_{2} are scalars, and so is h. This establishes the claim.

Applying the claim we now obtain b^{∗}(H) ≤ cd as required.

Finally, consider H as in 2.1(iii). Suppose first that S = A_{k}. Then k < d and n ∈ {k − 1, k − 2}, so n ≤ d + 1. Therefore b^{∗}(H) ≤ d + 2 in this case.

To conclude, suppose S ∈ Cl(n/t, q_{0}), where t divides n and 𝔽_{q_{0}} is a subfield of 𝔽_{q^{t}}. From the proof of 2.1, we see that, viewing V as an n/t-dimensional space over 𝔽_{q^{t}}, V is a natural module for S. Therefore H admits a strong base of size at most (n/t) + 1 (the extra 1 to take care of field automorphisms). Since n/t = O(d), the result follows. ♠

Since a strong base for H is also a base for H, Theorem 1.4 follows from 2.2.

Proof of Theorem 1.5. Let G ∈ Cl(n, q), and suppose q → ∞. We can assume that n → ∞, since otherwise the conclusion follows from [GKS]. Let M be a set of representatives for the conjugacy classes of the maximal subgroups of G. As in the proof of [GKS, Theorem II] we have

1 − P^{−}(G) ≤ ∑_{M∈M} rfix(G, M).

Write M = M_{1} ∪ M_{2} ∪ M_{3} where M_{1} consists of subspace subgroups, M_{2} consists of the subgroups lying in the Aschbacher classes C_{i} (2 ≤ i ≤ 8), together with A_{k}, S_{k} in minimal representations, and M_{3} consists of the remaining subgroups in S.

For i = 1, 2, 3 write

E_{i} = ∑_{M∈M_{i}} rfix(G, M).

Then

1 − P^{−}(G) ≤ E_{1} + E_{2} + E_{3},

so it suffices to show that, for each i, E_{i} → 0 as q, n → ∞.

Let M ∈ M_{1} be the stabilizer of a k-dimensional subspace of the natural module V, where k ≤ n/2. It follows from results of Guralnick and Kantor [GK, §3] that

rfix(G, M) ≤ q^{−δk},

where δ > 0 is some absolute constant. Hence the contribution of these subgroups to E_{1} is at most

∑_{k≥1} 2q^{−δk} = 2q^{−δ}(1 − q^{−δ})^{−1},

which tends to 0 as q → ∞. This shows that E_{1} → 0, except possibly in the case where G is symplectic in characteristic 2. In this case there are two additional subgroups in M_{1}, namely O_{n}^{+}(q) and O_{n}^{−}(q). If M is one of these subgroups, then rfix(G, M) ≤ 4/3q by [LS], and so the contribution of these subgroups to E_{1} is at most 8/3q, which tends to 0 as q → ∞. Therefore E_{1} → 0 in any case.

Let M ∈ M_{2}. Then by Theorem 1.1 we have

rfix(G, M) ≤ q^{−ϵn}.

On the other hand we have

|M_{2}| ≤ cn log log q

by [GKS, 2.2]. Therefore

E_{2} ≤ cn log log q · q^{−ϵn} → 0

as n or q tend to infinity.

Let M ∈ M_{3}. By the proof of Lemma 4.1 below,

rfix(G, M) ≤ q^{−cn^{3/2}}.

On the other hand, as in [LiSh2, p. 89] we have

|M_{3}| ≤ 6n^{2}q^{6n} log q.

Therefore

E_{3} ≤ 6n^{2}q^{6n} log q · q^{−cn^{3/2}} → 0

as n → ∞.

The theorem is proved.

Proof of Theorem 1.6. We adopt the notation of the previous proof. Let G be a simple group in Cl(n, q). We can assume that n → ∞, since otherwise the conclusion follows from [Sh2].

We need some notation. Let Q_{c}(G) denote the probability that ⟨x, x^{y}⟩ ≠ G. Let {C_{i}}_{i∈I} be the conjugacy classes of G. Suppose C_{1} = {1} and let I^{#} = I \ {1}. For each i ∈ I fix a representative g_{i} ∈ C_{i}.

By [Sh2, p. 572] we have

Q_{c}(G) ≤ |G|^{−1} + ∑_{i∈I^{#},M∈M} \frac{|C_{i} ∩ M|^{2}}{|C_{i}||M|} = |G|^{−1} + ∑_{i∈I^{#},M∈M} \frac{|C_{i} ∩ M|}{|M|}rfix(g_{i}, M).

Let M_{1}, M_{2}, M_{3} be as in the preceding proof. For M ∈ M let rank(G, M) denote the rank of the corresponding permutation group. Fix M ∈ M_{1}. As in [Sh2, p. 574] we have

∑_{i∈I} \frac{|C_{i} ∩ M|}{|M|}rfix(g_{i}, M) = |G : M|^{−1} · \frac{1}{|M|} ∑_{i∈I} |C_{i} ∩ M|fix(g_{i}, M)

= |G : M|^{−1} · rank(G, M).

For M ∈ M_{2} ∪ M_{3} we use the inequality (see [Sh2, p. 573])

∑_{i∈I^{#}} \frac{|C_{i} ∩ M|}{|M|}rfix(g_{i}, M) ≤ rfix(G, M).

Define

D_{1} = ∑_{M∈M_{1}} rank(G, M)|G : M|^{−1},

and let E_{2}, E_{3} be as in the proof of Theorem 1.5. It then follows that

Q_{c}(G) ≤ |G|^{−1} + D_{1} + E_{2} + E_{3}.

In order to show that Q_{c}(G) → 0, we bound each of the partial sums D_{1}, E_{2}, E_{3} separately. First, since n → ∞, it follows from the previous proof that E_{2}, E_{3} → 0. So it remains to consider D_{1}. To bound this, we need the following result bounding the ranks of subspace actions.

Proposition 2.3. Let M be a subspace subgroup of the classical simple group G ∈ Cl(n, q).

(i) If M is the stabilizer of a totally singular subspace (any subspace if G = L_{n}(q)), then rank(G, M) < cn^{2}.

(ii) If M is the stabilizer of a non-degenerate k-space (k ≤ n/2, G ≠ L_{n}(q)), then

rank(G, M) < ck^{2}q^{k^{2}}, and also rank(G, M) < ck^{2}q^{k^{2}−k/2+3}. (iii) If M is the stabilizer of a nonsingular 1-space with G orthogonal and p = 2,

or if (G, M, p) = (Sp_{2m}(q), O_{2m}^{±}(q), 2), then rank(G, M) < cq. (iv) In all cases, rank(G, M)|G : M|^{−1} ≤ cn^{2}q^{−n/5}.

Proof. (i) In this case M is a parabolic subgroup of G; say M = P_{k}, the stabilizer of a k-space. It is well known (see [CIK]) that rank(G, P_{k}) is the same as rank(W, W_{k}), where W is the Weyl group of G and W_{k} the parabolic subgroup of W corresponding to P_{k}. If G = L_{n}(q), then W = S_{n}, W_{k} = S_{k} × S_{n−k} and the rank is k + 1. If G is symplectic, unitary or orthogonal in odd dimension or of type O^{−}, then W = 2^{l}.S_{l} (of type B_{l}) and W_{k} = S_{k} × 2^{l−k}.S_{l−k}. In this case consider W acting in the natural imprimitive action on {±1, …, ±n}, with W_{k} the stabilizer of {1 …, k}, to see that rank(W, W_{k}) < ck^{2} (in fact it is equal to (k + 1)(k + 2)/2). Finally, if G is orthogonal of type O^{+}, then W = 2^{l−1}.S_{l} of type D_{l} (index 2 in type B_{l}) and the same considerations as above give rank(W, W_{k}) < ck^{2}.

(ii) Let V be the natural module for G, and let G_{1} = N_{P GL(V)}(G) (so that |G_{1} : G| ≤ 8; see [KL, Chapter 2]). Observe that rank(G_{1}, M) is equal to the number of orbits of G_{1} on pairs (U, W) of non-degenerate k-spaces.

Suppose first that G is not an orthogonal group in characteristic 2. Let (U, W) be a pair of non-degenerate k-spaces. Let X = U∩W. The G_{1}-orbit of X is specified by dim X and dim(rad(X)). Say rad(x) = ⟨e_{1}, …, e_{r}⟩. Then X has a (standard) basis e_{1}, …, e_{r}, e_{r+1}, f_{r+1}, …, e_{s}, f_{s} (possibly with an additional nonsingular vector d if G is orthogonal), with inner products as given in [KL, §§2.4, 2.5]. Up to G_{1}-action, the number of possibilities for X is at most ck^{2} (as there are at most k choices for r and s). Extend the above basis of X to standard bases of U and W:

basis of U : e_{1}, …, e_{r}, e_{r+1}, f_{r+1}, …, e_{s}, f_{s}, f_{1}, …, f_{r}, e_{s+1}, f_{s+1}, …, (d, d_{1})
basis of W : e_{1}, …, e_{r}, e_{r+1}, f_{r+1}, …, e_{s}, f_{s}, f′_{1}, …, f′_{r}, e′_{s+1}, f′_{s+1}, …, (d, d′_{1})

where d, d_{1}, d′_{1} are non-singular vectors which may or may not be present. Now observe that by Witt’s theorem, the G_{1}-orbit of (U, W) is determined by the inner products of the above basis vectors of U with those of W. There are at most k^{2} such inner products, so it follows that

rank(G_{1}, M) < ck^{2}q^{k^{2}}.

Write e′_{j} = e_{j} for j ≤ s. We may choose the e′_{i}(i ≥ s + 1) so that (e_{1}, e′_{i}) = 0 for all but at most one value of i (take the e′_{i} to include a basis for the kernel of the map v → (e_{1}, v) from the space spanned by the e′_{i} to the field). Thus the G_{1}-orbit of (U, W) is specified by the above k^{2} inner products, but excluding the (e_{1}, e′_{i}) which equal zero. There are at least (k − 2)/2 such e′_{i}, so the orbit is specified by k^{2} − (k − 2)/2 − 1 inner products. The last part of (ii) follows.

When G is an orthogonal group in characteristic 2, the above proof goes through with minor changes. There are two possibilities for rad(X) of a given dimension r, namely ⟨e_{1}, …, e_{r}⟩ and ⟨e_{1} + f_{1}, e_{2}, …, e_{r}⟩ (the first being totally singular, the second not); and X/rad(X) may be of type O^{+} or O^{−}. There may also be up to 4 extra vectors d, d_{1}, … to add to the bases of U, W. Apart from these changes, the above proof goes through.

(iii) This follows from the proof of [LPS, Proposition 1].

(iv) This is immediate from the previous parts. ♠

Since |M_{1}| ≤ cn, Proposition 2.3(iv) gives

D_{1} ≤ cn · cn^{2}q^{−n/5} = c^{2}n^{3}q^{−n/5} → 0

as n or q tend to infinity.

Theorem 1.6 follows.

We note that the lower bounds on the various generation probabilities obtained in the proofs of 1.5 and 1.6 for classical groups in general are significantly better than the ones given in [Sh1], [Sh2] for G = L_{n}(q).

3. Proof of Theorem (⋆): preliminary lemmas

This section and the next are devoted to the proof of Theorem (⋆).

Let G be an almost simple group with socle G_{0}, a classical group with natural module V of dimension n over a finite field 𝔽 = 𝔽_{q^{u}}, where u = 2 if G_{0} is unitary and u = 1 otherwise. Let p be the characteristic of 𝔽.

We are required to produce a constant ϵ > 0 such that, for any element x ∈ G of prime order, and any maximal subgroup M of G which is not a subspace subgroup,

|x^{G} ∩ M| < |x^{G}|^{1−ϵ}.

Define

f(x, M) = \begin{matrix}log & |x^{G} ∩ M| \\ log & |x^{G}| \end{matrix}.

We have to show that f(x, M) < 1 − ϵ.

Let G, M and x be as above. Observe first that by [LS], |x^{G} ∩ M|/|x^{G}| < min{2/q^{1/2}, 3/4}, and hence Theorem (⋆) follows if the dimension n is bounded. Thus we may assume that n is unbounded.

By [As], the maximal subgroup M is either in one of the Aschbacher families C_{i} (1 ≤ i ≤ 8), or it lies in collection S of almost simple, irreducible subgroups (satisfying various other conditions); see [KLi] for descriptions of all these families.

Throughout the section, we adopt the following notation:

o(1) = o_{n}(1);

c, c′, … are positive constants;

δ, δ′, … are small positive constants.

For a finite group M, i_{2}(M) denotes the number of involutions in M.

Lemma 3.1. We have |M| < |G|^{\frac{1}{2} +o(1)}. Moreover, there exists δ > 0 such that if |M| > |G|^{\frac{1}{2} −δ}, then M is of one of the following types:

\begin{matrix}M ∈ C_{2} : & Cl_{n/2}(q) wr S_{2}, GL_{n/2}(q^{u}) (G_{0} ≠ L_{n}(q)) \\ M ∈ C_{3} : & Cl_{n/2}(q^{2}).2, GU_{n/2}(q) (G orthogonal or symplectic) \\ M ∈ C_{5} : & Cl_{n}(q^{1/2}), Sp_{n}(q) or SO_{n}(q) (G unitary) \\ M ∈ C_{8} : & Sp_{n}(q), SO_{n}(q) or SU_{n}(q^{1/2}) (G_{0} = L_{n}(q)). \end{matrix}

Proof. For M ∈ C this follows by inspection of [KLi, Chap. 4] (recall M is not a subspace subgroup). For M ∈ S it follows from [Li1]. ♠

In what follows we let (⋆) denote the conclusion of Theorem (⋆).

Lemma 3.2. If |C_{G}(x)| < |G|^{\frac{1}{2} −δ′}, then (⋆) holds.

Proof. The hypothesis implies that |x^{G}| > |G|^{\frac{1}{2} +δ′}, giving (⋆) by 3.1 (first assertion). ♠

Lemma 3.3. If x ∉ P GL(V), then (⋆) holds.

Proof. As x ∉ P GL(V) and has prime order, it is a field, graph or graph-field automorphism of G_{0} (in the sense of [GL, §7]).

If o(x) ≥ 3, then x is a field automorphism, and |C_{G}(x)| < |G|^{\frac{1}{3} +o(1)}, giving the result by 3.2.

Now assume o(x) = 2. Then |x^{G}| > |G|^{\frac{1}{2} −o(1)} (see [LiSh2, 4.4] for example). Hence the result is immediate unless |M| > |G|^{\frac{1}{2} −δ}, so assume the latter holds. Then M is given by 3.1. In each case we see using [LiSh2, 4.1, 5.4, 5.5] that i_{2}(M) < |M|^{\frac{1}{2} +o(1)}. Using 3.1 we obtain i_{2}(M) < |M|^{\frac{1}{2} +o(1)} < (|G|^{1/2+o(1)})^{1/2+o(1)} < |G|^{\frac{1}{4} +o(1)}. It follows that

|x^{G} ∩ M| ≤ i_{2}(M) ≤ |x^{G}|^{1/2+o(1)}.

♠

In view of 3.2 and 3.3, we assume from now on that x ∈ P GL(V) and |C_{G}(x)| > |G|^{\frac{1}{2} −o(1)}.

Let 𝔽̄ be the algebraic closure of 𝔽 = 𝔽_{q^{u}}, and let V̄ = V ⊗ 𝔽̄. Let x̂ be a preimage of x in GL(V). Define

ν(x) = ν_{V,𝔽̄}(x) = min{dim[V̄ , λx̂] : λ ∈ 𝔽̄^{∗}}.

Note that ν(x) > 0 if x ≠ 1. Take Ḡ to be one of the classical algebraic groups SL(V̄), Sp(V̄), SO(V̄), such that there is a Frobenius morphism σ of Ḡ satisfying G_{0} = Ḡ_{σ}/Z(Ḡ_{σ}).

Lemma 3.4. Suppose ν(x) = s. Then the following hold.

(i) If G_{0} = L_{n}^{ϵ}(q), we have

cq^{s(2n−s)} > |x^{G}| > c′ max(q^{2s(n−s)}, q^{ns}).

(ii) If G_{0} = P Sp_{n}(q) or P Ω_{n}^{ϵ}(q), then

cq^{s(2n−s+1)/2} > |x^{G}| > c′ max(q^{s(n−s)}, q^{ns/2}).

Proof. (i) Assume first that x is semisimple and ν(x) = s. Then CḠ(x̂) lies in a σ-stable subgroup ((GL_{n−s})^{k} × GL_{n−k(n−s)}) ∩ Ḡ for some k ≥ 1, and contains GL_{n−s}. Hence

c|GL_{n−s}^{ϵ}(q)| ≤ |C_{GL_{n}^{ϵ}(q)}(x̂)| ≤ c′|GL_{n−s}^{ϵ}(q) × GL_{s}^{ϵ}(q)|,

which yields cq^{s(2n−s)} > |x^{G}| > c′q^{2s(n−s)}. This also implies |x^{G}| > c′q^{ns} if s ≤ n/2; and if s > n/2, then |C_{GL_{n}^{ϵ}(q)}(x̂)| ≤ |GL_{n−s}^{ϵ}(q)|^{n/(n−s)} < cq^{n(n−s)}, giving |x^{G}| > cq^{ns}.

Now assume x is unipotent (of order p). For each i, let n_{i} be the number of Jordan blocks in x of size i, so that ∑ in_{i} = n, ∑ n_{i} = n − s. By [Wa, p. 34] we have

|x^{G}| ∼ q^{n^{2}−2 ∑_{i<j} in_{i}n_{j}−∑ in_{i}^{2}}.

Define

f = 2 ∑_{i<j} in_{i}n_{j} + ∑ in_{i}^{2}.

We claim

(1) f ≥ (n − s)^{2} + s;

(2) if s ≤ n/2, then f ≤ (n − s)^{2} + s^{2}; and

(3) if s > n/2, then f ≤ n(n − s). Conclusion (i) follows from these assertions.

For (1), observe that ∑(i − 1)n_{i} = s, so

f = (∑ n_{i})^{2} + ∑(i − 1)n_{i}^{2} + 2 ∑_{i<j}(i − 1)n_{i}n_{j}

≥ (∑ n_{i})^{2} + ∑(i − 1)n_{i} = (n − s)^{2} + s.

For (2), note that

s^{2} = ∑(i − 1)^{2}n_{i}^{2} + 2 ∑_{i<j}(i − 1)(j − 1)n_{i}n_{j} ≥ ∑(i − 1)n_{i}^{2} + 2 ∑_{i<j}(i − 1)n_{i}n_{j},

and hence f = (n − s)^{2} + ∑(i − 1)n_{i}^{2} + 2 ∑_{i<j}(i − 1)n_{i}n_{j} ≤ (n − s)^{2} + s^{2}. Finally, for (3), the fact that ∑ n_{i} = n − s, ∑(i − 1)n_{i} = s gives

s(n − s) = ∑(i − 1)n_{i}^{2} + ∑_{i<j}((i − 1) + (j − 1))n_{i}n_{j}

≥ ∑(i − 1)n_{i}^{2} + 2 ∑_{i<j}(i − 1)n_{i}n_{j} = f − (n − s)^{2}.

(ii) Assume first that G_{0} = P Sp_{n}(q) (with n even), and x is semisimple with ν(x) = s. Let V̄_{λ} be an eigenspace of x̂ of maximal dimension n − s, corresponding to eigenvalue λ. If λ = ±1, then V̄_{λ} is non-degenerate, and Sp_{n−s} ≤ CḠ(x̂) ≤ Sp_{n−s}×Sp_{s} (all σ-stable subgroups); otherwise, V̄_{λ} is totally singular and GL_{n−s} ≤ CḠ(x̂) ≤ (GL_{n−s})^{k} × Sp_{n−2k(n−s)} for some k ≥ 1. It follows that

|Sp_{n−s}(q)| ≤ |C_{Sp_{n}(q)}(x̂)| ≤ |Sp_{n−s}(q) × Sp_{s}(q)|,

whence

cq^{s(2n−s+1)/2} > |x^{G}| > c′q^{s(n−s)}.

This also gives |x^{G}| > c′q^{ns/2} unless s ≥ n/2, in which case, as above,

|x^{G}| > c|Sp_{n}(q)|/|Sp_{n−s}(q)|^{n/n−s} > c′q^{ns/2}.

Now suppose x is unipotent, of order p. Let n_{i} be the number of Jordan blocks of size i in x. Then ∑ in_{i} = n, ∑ n_{i} = n − s. Suppose p ≠ 2. Then by [Wa, p. 37], n_{i} is even if i is odd, and

|C_{Sp_{n}(q)}(x̂)| = q^{∑_{i<j} in_{i}n_{j}+∑(i−1)n_{i}^{2}/2} ∏_{i odd} |Sp_{n_{i}}(q)| ∏_{i even} q^{n_{i}/2}|O_{n_{i}}(q)|.

Hence

|x^{G}| ∼ q^{(n^{2}+n−2 ∑_{i<j} in_{i}n_{j}−∑ in_{i}^{2}−∑_{i odd} n_{i})/2}.

Define

g = 2 ∑_{i<j} in_{i}n_{j} + ∑ in_{i}^{2} + ∑_{i odd} n_{i}.

We claim that

(1) g ≥ (n − s)^{2} + n − s;

(2) if s ≤ n/2, then g ≤ (n − s)^{2} + s^{2} + n; and

(3) if s > n/2, then g ≤ (n − s)^{2} + s(n − s) + n. Conclusion (ii) (for p ≠ 2) follows from these assertions.

To see (1), observe

g = (∑ n_{i})^{2} + ∑(i − 1)n_{i}^{2} + 2 ∑_{i<j}(i − 1)n_{i}n_{j} + ∑_{i odd} n_{i}.

Hence g ≥ (n − s)^{2} + ∑_{i even} n_{i} + ∑_{i odd} n_{i} = (n − s)^{2} + n − s.

For (2), note that

s^{2} + n = (∑(i − 1)n_{i})^{2} + ∑ in_{i}

≥ ∑(i − 1)n_{i}^{2} + 2 ∑_{i<j}(i − 1)n_{i}n_{j} + ∑_{i odd} n_{i} = g − (n − s)^{2}.

And for (3),

s(n − s) + n = (∑(i − 1)n_{i})(∑ n_{i}) + ∑ in_{i}

≥ ∑(i − 1)n_{i}^{2} + 2 ∑_{i<j}(i − 1)n_{i}n_{j} + ∑_{i odd} n_{i} = g − (n − s)^{2}.

Finally, if p = 2, we see from [AS, §7] that, writing n = 2m,

cq^{m^{2}+(m−s)^{2}+m} > |C_{G}(x)| > c′q^{m^{2}+(m−s)^{2}+m−s},

giving cq^{s(n−s+1)} > |x^{G}| > c′q^{s(n−s)}. Since ν(x) ≤ n/2 in this case (as x is an involution), the conclusion follows. This completes the proof for G_{0} = P Sp_{n}(q).

The proof for G_{0} = P Ω_{n}(q) is entirely similar and is left to the reader. ♠

Lemma 3.5. If ν(x) > (\frac{1}{2} + δ)n (where δ is a small positive constant), then (⋆) holds.

Proof. The hypothesis implies by 3.4 that |x^{G}| > |G|^{\frac{1}{2} +δ}, giving (⋆) by 3.1. ♠

Assume from now on that ν(x) < (\frac{1}{2} + δ)n, where δ is a small positive constant. For a positive integer s, and a subgroup H of P GL(V), define

n_{s}(H) = |{h ∈ H : o(h) prime and ν(h) = s}|.

For a prime r, let k_{r}(H) be the number of conjugacy classes of elements of order r in H, and define

k_{pr}(H) = max{k_{r}(H) : r prime}.

Lemma 3.6. (i) If G_{0} = L_{n}^{ϵ}(q), then n_{s}(G) < cnq^{n+s(2n−s)} and k_{pr}(G) < cnq^{n}. Also, if s < (1/2 + δ)n, then n_{s}(G) < cnq^{s+s(2n−s)}.

(ii) If G_{0} is a symplectic or orthogonal group, then n_{s}(G) < cq^{(n+s(2n−s+1))/2} and k_{pr}(G) < cq^{n}. Also if s < (1/2 + δ)n, then n_{s}(G) < cq^{s(2n−s+5)/2}.

Proof. (i) Let k_{s,u} (resp. k_{s,s}) denote the number of conjugacy classes in P GL_{n}^{ϵ}(q) of unipotent (resp. semisimple) elements h of prime order such that ν(h) = s. Such a unipotent class is determined by a partition of n into n − s parts (each part being the size of a Jordan block). Subtracting 1 from each part gives a partition of s. Letting P (s) denote the number of partitions of s we obtain

k_{s,u} ≤ P (s) < 2^{s}.

A semisimple element h of prime order r is conjugate to the image (modulo scalars) of a matrix diag(A_{1}, …, A_{l}, I_{m}), where each A_{j} is an irreducible i × i block (and il + m = n, r divides q^{i} − 1). If ν(h) = s, then the largest eigenspace of h on V̄ (of dimension n − s) is either the 1-eigenspace of dimension m, or is the eigenspace of an eigenvalue of some A_{j}. In the first case, m = n − s; and in the second, l ≥ n − s and l ≤ n/i. Thus

k_{s,s} ≤ r^{s/i} + ∑_{n/i≥l≥n−s} r^{l} ≤ q^{s} + (n/i)(q^{i})^{n/i} < cnq^{n}.

It now follows from 3.4 that

n_{s}(P GL_{n}^{ϵ}(q)) < c(k_{s,u} + k_{s,s})q^{s(2n−s)} < c′nq^{n+s(2n−s)}.

Note that k_{pr}(P GL_{n}^{ϵ}(q)) ≤ ∑_{s≤n}(k_{s,u} + k_{s,s}), and from the above this is less than cnq^{n}. Finally, if s < n/2, then in the second case above, n/i ≥ n − s implies i = 1 and x̂ conjugate to the image of diag(I_{n−s}, λ_{1}, …, λ_{s}), whence k_{s,s} ≤ q^{s}. This gives n_{s}(P GL_{n}^{ϵ}(q)) < c′nq^{s+s(2n−s)}. And if n/2 ≤ s < (1/2 + δ)n, then either i = 1 as before, or i = 2, in which case we obtain k_{s,s} < c((q + 1)/2)^{n/2} (n/2 2-blocks, at most q + 1/2 choices for each A_{i} up to conjugacy), whence k_{s,s} < cq^{s} giving the result as before.

(ii) First consider k_{s,u} for G_{0} = P Sp_{n}(q). For p odd, by [Wa, p. 34], a unipotent class of elements h of order p with ν(h) = s is determined by a partition of n into n − s parts, and, for each even part size, a choice of one of two orthogonal forms. Since the number of even part sizes is less than \sqrt{s}, it follows that k_{s,u} < P (s)2^{\sqrt{s}} < 2^{s+\sqrt{s}}. If q ≥ 5, then this is less than q^{n}; and if q = 3, then ν(h) = s ≤ 2n/3 so 2^{s+\sqrt{s}} < q^{n}. Hence k_{s,u} < cq^{n} for all odd q; the same holds when p = 2, by [AS, §8].

Now consider k_{s,s} for G_{0} = P Sp_{n}(q). A semisimple element h of prime order r with ν(h) = s is conjugate to the image of either

diag(I_{n−s}, −I_{s}) or diag(I_{m}, A_{1}, A_{1}^{−T} , …, A_{l}, A_{l}^{−T}),

where each A_{j} is an irreducible i×i block (matrices relative to an obvious basis) and r divides q^{i} − 1. Arguing as above, we obtain k_{s,s} < cnq^{n/2} (and if s < (1/2 + δ)n, k_{s,s} < cq^{s}), giving the result as in (i).

The argument for G_{0} orthogonal is similar and left to the reader. ♠

The next lemma is taken from [HLS, Lemma 4.1]. As it appears there without proof (and there is some possibility of confusion over which field things are being taken over), we give a proof here.

Lemma 3.7. Let V_{a}, V_{b} be vector spaces of dimensions a, b over 𝔽_{q}, and let g = g_{1} ⊗ g_{2} ∈ GL(V_{a}) ⊗ GL(V_{b}) acting on V = V_{a} ⊗ V_{b}, with g of prime order. Let s_{1} = ν(g_{1})(= ν_{V_{a},𝔽̄}(g_{1})), and s_{2} = ν(g_{2}). Then

ν(g) = ν_{V,𝔽̄}(g) ≥ max(as_{2}, bs_{1}).

Proof. Suppose first that g is semisimple. Let g_{1} have eigenvalues λ_{1}, …, λ_{t} with multiplicities r_{1}, …, r_{t} respectively, and let g_{2} have eigenvalues μ_{1}, …, μ_{u} with multiplicities s_{1}, …, s_{u}, where r_{1} ≥ r_{2} ≥ … ≥ r_{t} and s_{1} ≥ … ≥ s_{u}. Then ν(g_{1}) = a − r_{1}, ν(g_{2}) = b − s_{1}.

Assume without loss that t ≥ u. Then the maximum dimension of an eigenspace for g = g_{1} ⊗ g_{2} is at most ∑_{1}^{t} r_{i}s_{i}. Therefore

ν(g) ≥ ab − ∑_{1}^{t} r_{i}s_{i} ≥ ab − r_{1} ∑_{1}^{t} s_{i} = ab − r_{1}b = bν(g_{1}),

and similarly ν(g) ≥ aν(g_{2}).

Now suppose g is unipotent of order p. In the Jordan canonical form, for 1 ≤ i ≤ p let the Jordan block J_{i} of size i × i occur with multiplicity r_{i} in g_{1}, and with multiplicity s_{i} in g_{2}.

For i ≤ j ≤ p, one checks that C_{V_{i}⊗V_{j}}(J_{i} ⊗ J_{j}) has dimension i. Hence

dim C_{V_{a}⊗V_{b}}(g_{1} ⊗ g_{2}) ≤ ∑_{i,j} ir_{i}s_{j},

and therefore ν(g_{1} ⊗ g_{2}) ≥ ab − ∑_{i,j} ir_{i}s_{j}. Consequently

aν(g_{2}) = a(b − ∑ s_{j}) ≤ ab − (∑ ir_{i})(∑ s_{j}) = ab − ∑_{i,j} ir_{i}s_{j} ≤ ν(g_{1} ⊗ g_{2}).

Similarly bν(g_{1}) ≤ ν(g_{1} ⊗ g_{2}). ♠

4. Completion of proof of Theorem (⋆)

Continue with the notation of the previous section. In this section we complete the proof of Theorem (⋆) by considering the possibilities for the maximal subgroup M of the classical group G. Recall once again, that M either lies in one of the Aschbacher families C_{i} (1 ≤ i ≤ 8), or M ∈ S; also M is not a subspace subgroup, and ν(x) < (\frac{1}{2} + δ)n, where δ is a small positive constant.

Lemma 4.1. If M ∈ C_{6} ∪ C_{7} ∪ S, then (⋆) holds.

Proof. If M ∈ C_{6} ∪ C_{7}, then M ∩ P GL(V) is primitive and tensor-indecomposable on V (since M is maximal, for instance), and hence by [HLS, Theorem 4(b)], ν(x) > \sqrt{n}/12. By [HLS, Theorem 4(a) and p. 452-3], the same conclusion holds for M ∈ S, excluding the case where M = A_{n+d} or S_{n+d} (d ≤ 2) and V is a constituent of the permutation module. Hence, excluding this case, by 3.4 we have

|x^{G}| > q^{cn^{3/2}}.

However, for M ∈ C_{6}, |M| < cr^{2a}|Sp_{2a}(r)| for some prime r, where n = r^{a}; hence |M| < cr^{2a^{2}+3a} < cn^{d log n}. For M ∈ C_{7}, |M| < |GL_{a}(q)|^{b}|S_{b}| with n = a^{b}, so |M| < cq^{a^{2}b}b! < c′q^{2n}. And for M ∈ S (excluding the above exception with M′ = A_{n+d}), we have |M| < q^{3n} by [Li1]. Thus in all these cases, we have |x^{G} ∩ M| < |M| < |x^{G}|^{δ}, giving (⋆).

Finally, suppose M′ = A_{n+d} with d ≤ 2, as in the case excluded above. In this case the proof of [LP, Lemma 8] supplies lower bounds for |x^{G}| and upper bounds for |x^{G} ∩ M|, from which the result follows easily. ♠

Lemma 4.2. If M ∈ C_{3}, then (⋆) holds.

Proof. Suppose M ∈ C_{3}. Then either

(1) M ∩ P GL(V) lies in the image modulo scalars of a group Cl_{n/k}(q^{k}).k, where k is prime (and G is of the same type Cl_{n}(q)), or

(2) M ∩P GL(V) lies in the image of GU_{n/2}(q) and G is symplectic or orthogonal. Consider case (1). Let B = Cl_{n/k}(q^{k}). For y ∈ B, let

ν_{0}(y) = min{dim[V̄_{n/k}, λy] : λ ∈ 𝔽̄^{∗}}

and let ν(y) be defined as above (relative to V = V_{n}).

We claim that for y ∈ B of prime order,

ν(y) ≥ kν_{0}(y).

If y is unipotent, this is clear, since ν(y) = n−dim C_{V_{n}}(y) = k(\frac{n}{k} −dim C_{V_{n/k}}(y)) = kν_{0}(y).

Now suppose y is semisimple. An element of GL_{n/k}(q^{k}) conjugate to

diag(λ_{1}, …, λ_{n/k}) ∈ GL_{n/k}(𝔽̄) (λ_{i} ∈ 𝔽̄^{∗})

becomes conjugate to

diag(λ_{1}, λ_{1}^{q}, …, λ_{1}^{q^{k−1}}, …, λ_{n/k}^{q^{k−1}}) ∈ GL_{n}(𝔽̄).

For an eigenvalue λ ∈ 𝔽̄ of y, let V_{λ} be the corresponding eigenspace in V_{n/k}, and define

a = max{dim V_{λ} : λ = λ^{q}}, b = max{dim V_{μ} : μ ≠ μ^{q}}.

Then ν_{0}(y) = min(\frac{n}{k} −a, \frac{n}{k} −b). The maximum multiplicity of an eigenvalue of y on V_{n} is at most max(ak, bk). If b ≥ a, then ν(y) ≥ n−bk and ν_{0}(y) ≤ \frac{n}{k} −b ≤ ν(y)/k, as required. And if b < a, then ν(y) ≥ n − ak and ν_{0}(y) ≤ \frac{n}{k} − a ≤ ν_{0}(y)/k. This establishes the claim.

Next, for y ∈ M − B of prime order k, y is B-conjugate to a field automorphism of B of order k (see [GL, 7.2]). Such an element acts as a permutation with n/k kcycles on a suitable basis of V_{n}, and hence ν(y) = n(k−1)/k; as ν(x) < (\frac{1}{2} +δ)n, this case arises only when k = 2, in which case |y^{G} ∩(M −B)| < c|Cl_{n/2}(q^{2}) : Cl_{n/2}(q)|.

Now let ν(x) = s, and assume that (k, s) ≠ (2, n/2). Define an integer d to be 1 if G_{0} = L_{n}^{ϵ}(q), and to be 2 otherwise. Then by the above and 3.6,

|x^{G} ∩ M| < n_{s}(B) < c ∑_{r≤s/k}(q^{k})^{r((2n/k)−r+5)/d} ≤ c\frac{s}{k} .q^{s(2n−s+5k)/kd}.

Therefore using 3.4, we have

f(x, M) ≤ \frac{log n + (s/2k)(2n − s + 5k)}{s(n − s)} = \frac{2n − s + 5k}{2k(n − s)} + o(1).

Denote the right hand side of the above equality by g(k, s). We claim that g(k, s) ≤ 3/4 + o(1). Indeed, for fixed k, the function g(k, s) is increasing when s ∈ [0, (1/2+δ)n], so its maximum is attained at the end point s = (1/2+δ)n. Therefore

g(k, s) ≤ \frac{(3/2 − δ)n + 5k}{2k(1/2 − δ)n} .

The expression on the right is maximal when k = 2, and so

g(k, s) ≤ \frac{(3/2 − δ)n + 10}{4(1/2 − δ)n} = 3/4 + δ′,

as required.

Finally, assume (k, s) = (2, n/2). Then

|x^{G} ∩ M| = |x^{G} ∩ B| + |x^{G} ∩ (M − B)|
< n_{s}(B) + c′|Cl_{n/2}(q^{2}) : Cl_{n/2}(q)| < 2n_{s}(B),

and the conclusion follows as before.

Now consider case (2). The argument here is similar. Let B = GU_{n/2}(q). As above, if b ∈ B, we have ν_{V_{n/2}}(b) ≤ s/2. By [LiSh2, 4.4], M − B has at most 3 B-classes of involutions y, and |C_{B}(y)| > c|B : O_{n/2}(q)| for each of these; moreover, ν(y) = n/2 (as each such involution interchanges a pair of maximal totally singular subspaces of V ⊗ 𝔽̄). Thus if s ≠ n/2, then by 3.6,

|x^{G} ∩ M| = |x^{G} ∩ B| ≤ n_{s}(B) < c ∑_{r≤s/2} q^{r(n−r+1)} < c(s/2)q^{(s/2)(n−(s/2)+1)},

and by 3.4,

|x^{G}| > cq^{s(n−s)},

whence f(x, M) < ((2n − s + 2) + log n)/(4(n − s)) < 3/4 + o(1) as above. And if s = n/2, then |x^{G} ∩ M| < n_{s}(B) + c|B : O_{n/2}(q)| < 2n_{s}(B), giving the result as above again. ♠

Lemma 4.3. If M ∈ C_{4}, then (⋆) holds.

Proof. Suppose M ∈ C_{4}, so M ∩ P GL(V) < Cl_{n_{1}}(q) ⊗ Cl_{n_{2}}(q) = Cl(V_{1}) ⊗ Cl(V_{2}), where V = V_{1} ⊗ V_{2}, n = n_{1}n_{2} and n_{i} ≥ 2. (The precise possibilities are listed in [KL, §4.3].) Write s = ν(x).

Let x = g_{1} ⊗ g_{2} ∈ M, and write s_{i} = ν(g_{i}). Then by 3.7, s = ν(x) ≥ max(n_{1}s_{2}, n_{2}s_{1}). As s < (\frac{1}{2} + δ)n, we have s_{1} < (\frac{1}{2} + δ)n_{1}, s_{2} < (\frac{1}{2} + δ)n_{2}.

By 3.6,

|x^{G} ∩ M| < max_{s_{1}≤s/b,s_{2}≤s/a}q^{(s_{1}/d)(2n_{1}−s_{1}+5)+(s_{2}/d)(2n_{2}−s_{2}+5)},

where d = 1 if G_{0} = L_{n}^{ϵ}(q) and d = 2 otherwise. The maximum above is attained when s_{1} = s/n_{2}, s_{2} = s/n_{1}. Therefore, using 3.4, we have

f(x, M) ≤ \frac{(s/n_{2})(2n_{1} − (s/n_{2}) + 5) + (s/n_{1})(2n_{2} − (s/n_{1}) + 5)}{2s(n − s)}.

Write a = n_{1}, b = n_{2}, and denote the expression on the right by g(a, b, s). We claim that g(a, b, s) ≤ 3/8 + o(1). To show this write s = αn, and note that

g(a, b, s) = \frac{αa(2a − αa + 5) + αb(2b − αb + 5)}{2αn(n − αn)}

= \frac{5α(a + b)n^{−2} + α(2 − α)(a^{2} + b^{2})n^{−2}}{2α(1 − α)} .

This yields

g(a, b, s) = \frac{5(a + b)n^{−2} + (2 − α)(a^{2} + b^{2})n^{−2}}{2(1 − α)} .

Note that (a + b)n^{−2} = o(1), and that (a^{2} + b^{2})n^{−2} ≤ 1/4 + o(1). Therefore

g(a, b, s) ≤ \frac{(2 − α)(1/4 + o(1))}{2(1 − α)}.

For α in the interval (0, 1/2 + δ], the expression on the right attains its maximum when α = 1/2 + δ, giving g(a, b, s) ≤ 3/8 + δ′, as claimed. ♠

Lemma 4.4. If M ∈ C_{5}, then (⋆) holds.

Proof. Suppose M ∈ C_{5}, so either

(1) M ∩ P GL(V) ≤ Cl_{n}(q_{0}), where q = q_{0}^{k} for some prime k, or

(2) G_{0} = U_{n}(q) and M ∩ P GL(V) ≤ P GSp_{n}(q) or P GO_{n}(q).

Consider case (1). Let s = ν(x). Then by 3.4, writing d = 1 if G_{0} = L_{n}^{ϵ}(q), d = 2 otherwise,

|x^{M}| ≤ cq_{0}^{(s/d)(2n−s+1)}.

Hence using 3.6, we have

|x^{G} ∩ M| < k_{pr}(M)|x^{M}| < cnq_{0}^{n+(s/d)(2n−s+1)}.

Consequently

f(x, M) ≤ \frac{2n + s(2n − s + 1) + log n}{2sk(n − s)}.

The expression on the right is increasing in s ∈ (0, (1/2+δ)n], and so the maximum is attained for s = (1/2 + δ)n. This yields

f(x, M) ≤ \frac{1}{2k} \frac{3/2 − δ}{1/2 − δ + o(1)} ≤ 3/4 + δ′.

Now consider case (2). Here, again using 3.4 and 3.6, we have

|x^{G} ∩ M| < k_{pr}(M)|x^{M}| < cq^{n+(s/2)(2n−s+1)},

and the result follows as before. ♠

Lemma 4.5. If M ∈ C_{2}, then (⋆) holds.

Proof. In this case, either

(1) M ∩ P GL(V) is contained in the image modulo scalars of a subgroup Cl_{m}(q) wr S_{k}, where n = km and k ≥ 2, or

(2) M ∩ P GL(V) is contained in the image of GL_{n/2}(q^{u}), and G_{0} is unitary, symplectic or orthogonal.

Consider case (1). Write B for the image of the base group (Cl_{m}(q))^{k}, fixing a decomposition V = V_{1} ⊕ … ⊕ V_{k} (where dim V_{i} = m for all i). Let s = ν(x). Suppose first that x^{G} ∩ M ⊆ B. If s_{i} = ν_{V_{i}}(x^{V_{i}}), then s_{1} + … + s_{k} ≤ s. Thus by 3.6, with the usual definition of the integer d,

|x^{G} ∩ M| ≤ n_{s}(B) < ∑_{s_{1}+...+s_{k}≤s,s_{i}≤m} ∏_{i}(cm)^{s_{i}}q^{(m+s_{i}(2m−s_{i}+1))/d}

≤ (cm)^{s}q^{n/d} ∏_{i} q^{s_{i}(2m−s_{i}+1)/d}.

The number of terms in the sum with ∑ s_{i} = t ≤ s is at most \binom{k+t−1}{k−1}, which is less than k^{t}. Let 0 ≤ s_{1}, …, s_{k} ≤ m with ∑ s_{i} = t ≤ s. Then ∑ s_{i}^{2} ≥ k(t/k)^{2} = t^{2}/k, and so

∑_{i=1}^{k} s_{i}(2m − s_{i} + 1) = (2m + 1)t − ∑ s_{i}^{2} ≤ (2m + 1)t − t^{2}/k.

Hence

n_{s}(B) < (cm)^{s}q^{n/d} ∑_{t=1}^{s} k^{t}q^{(t/d)(2m−t/k+1)} ≤ (cm)^{s}q^{n/d}sk^{s}q^{(s/d)(2m−s/k+1)}.

It follows by 3.4 that

f(x, M) ≤ \frac{s(2(n/k) − (s/k) + 1) + n + 2s(log k + log m + c′)}{2s(n − s)}

= \frac{2n − s}{2k(n − s)} + \frac{n}{2s(n − s)} + o(1).

If s > 1, then the expression on the right is maximal when s = (1/2 + δ)n and k = 2, giving f(x, M) < 3/4 + δ′. And if s = 1, then in fact, n_{s}(B) < cq^{3m/d}, giving f(x, M) < 3m/(2s(n − s)) + o(1) < 3/4 + o(1) again.

Now assume that x^{G} ∩ M ⊈ B. We may take x ∈ M − B; say x is the image of x̂ = (b_{1}, …, b_{k})π, where each b_{i} ∈ Cl_{m}(q) and 1 ≠ π ∈ S_{k}. Let r be the (prime) order of x, hence of π. For the purpose of estimating ν(x), we regard x̂ as an element of GL_{n}(𝔽̄), and each b_{i} as an element of GL_{m}(𝔽̄). We have x̂^{r} = λI for some scalar λ. Choose μ ∈ 𝔽̄ such that μ^{r} = λ^{−1}. Replacing x̂ by μx̂ (hence each b_{i} by μb_{i}), we then have x̂^{r} = I.

Let π consist of h r-cycles and f fixed points, so that k = hr + f. Say π induces the permutation ∏_{i=1}^{h}((i − 1)r + 1 … ir) on the coordinates. As x̂^{r} = I, we have

b_{1} … b_{r} = b_{r+1} … b_{2r} = … = b_{(h−1)r+1} … b_{hr} = 1.

Define

\begin{aligned}g = & (1, b_{1}, b_{1}b_{2}, b_{1}b_{2}b_{3}, …, b_{1} … b_{r−1}, …, \\ & 1, b_{(h−1)r+1}, b_{(h−1)r+1}b_{(h−1)r+2}, …, b_{(h−1)r+1} … b_{hr−1}, 1, …, 1). \end{aligned}

Then g^{−1}πg = (b_{1}, b_{2}, …, b_{hr}, 1, …, 1)π. Hence, if b = (1, …, 1, b_{hr+1}, …, b_{k}), then

g^{−1}bπg = (b_{1}, …, b_{k})π = x.

Thus x is conjugate (in GL_{n}(𝔽̄)) to bπ.

Suppose r ≠ p, and let ω ∈ 𝔽̄_{p} be an r^{th} root of unity. Let W = ∑_{1}^{hr} V_{i}. Then there is a scalar λ such that in its action on W, λπ has each of the eigenvalues ω^{i} (0 ≤ i ≤ r − 1) with multiplicity mh. Therefore

ν(x) = ν(bπ) ≥ mh(r − 1).

Similarly, if r = p, then C_{W} (π) has dimension mh, and the same conclusion follows.

Since ν(x) ≤ (\frac{1}{2} +δ)n = (\frac{1}{2} +δ)m(hr+f), it follows that h(r−1) < (1+δ′)(h+f), where 1 + δ′ = (1 + 2δ)/(1 − 2δ). By 3.4, we have

|x^{G}| > cq^{2mh(r−1)(n−mh(r−1))(1−δ′′)/d} = cq^{2m^{2}h(r−1)(h+f)(1−δ′′)/d}

(δ′′ a small positive constant, usual definition of d). Obviously,

|x^{G} ∩ M| < |M| ≤ |Cl_{m}(q)|^{k}k! < cq^{kc(m)}k!,

where c(m) = m^{2} if G_{0} = L_{n}^{ϵ}(q), c(m) = (m^{2} + m)/2 if G_{0} = P Sp_{n}(q), and c(m) = (m^{2} − m)/2 if G_{0} = P Ω_{n}(q). Hence

f(x, M) ≤ \frac{dkc(m) + dk log k}{2m^{2}h(r − 1)(h + f)(1 − δ′′)}. (†)

Now k = h(r − 1) + h + f, so

\frac{k}{h(r − 1)(h + f)} = \frac{1}{h(r − 1)} + \frac{1}{h + f} ≤ \frac{2}{h(r − 1)}.

Consequently

(1 − δ′′)f(x, M) ≤ \frac{dc(m)}{m^{2}h(r − 1)} + \frac{d log k}{m^{2}h(r − 1)} ≤ \frac{3}{2h(r − 1)} + \frac{2 log k}{m^{2}h(r − 1)}.

This yields (⋆) (with ϵ = 1/8 or so), unless one of the following holds:

(a) h = 1, r = 2;

(b) m^{2}h(r − 1) < 16 log k. Consider case (a). Here k = f + 2 and h + f = k − 1. Going back to (†) above, we find that

(1 − δ′′)f(x, M) ≤ \frac{dk(c(m) + log k)}{2m^{2}(k − 1)} ≤ \frac{k}{k − 1}(\frac{m^{2} + m + 2 log k}{2m^{2}} ).

This yields the conclusion (with ϵ = 1/8 or so) unless either (b) above holds, or k = 2.

For k = 2 we argue as follows. Since x ∈ M − B and x has prime order, x must be an involution. Hence |x^{G} ∩M| ≤ i_{2}(M). It is easy to see (by direct computation or using the proof of [LiSh2, 5.4]) that i_{2}(M) ≤ |M|^{1/2+o(1)} = q^{(1+o(1))m^{2}/d}. Our above-mentioned lower bound on |x^{G}| (with k = r = 2, h = 1, f = 0) yields

|x^{G}| > c′q^{2m^{2}(1−δ′′)/d}.

Hence

|x^{G} ∩ M| ≤ |i_{2}(M)| ≤ q^{(1+o(1))m^{2}/d} ≤ |x^{G}|^{1/2+δ′′′}

where as usual, δ′′′ is small.

Now consider case (b). Here in particular, m^{2} < 16 log k and h(r − 1) < 16 log k. The first inequality yields n^{2} = k^{2}m^{2} < 16k^{2} log k, and so k is as large as we want (since n is). Since h(r − 1) = (k − f)(r − 1)/r, the second inequality yields k − f < 16r log k/(r − 1) < 32 log k, whence f > k − 32 log k.

We may suppose that for all y ∈ x^{G} ∩ M, we have y = bϕ with b ∈ B and ϕ ∈ S_{k} having more than k−32 log k fixed points, since otherwise the above argument gives the conclusion. In other words,

x^{G} ∩ M ⊆ {Bϕ : ϕ ∈ S_{k}, | supp(ϕ)| ≤ 32 log k}.

Now |B| < q^{m^{2}k} < q^{16k log k}, and

|\{ϕ ∈ S_{k} : | supp(ϕ)| ≤ 32 log k\}| ≤ \binom{32 log k}{k}.(32 log k)! < n^{c′ log n} < |B|^{o(1)}.

Hence |x^{G} ∩ M| < |B|^{1+o(1)}.

For the purpose of proving (⋆) we may therefore assume that |x^{G}| < |B|^{2}. Then |x^{G}| < q^{32k log k}, whence by 3.4 we have ν(x) < 32 log k.

Now fix ϕ ∈ S_{k} with | supp(ϕ)| ≤ 32 log k. We next obtain an upper bound for the number of elements h of Bϕ such that ν(h) < 32 log k; this will then be an upper bound for |x^{G} ∩ Bϕ|. Let h = (b_{1}, …, b_{k})ϕ with dim C_{V} (h) > n − 32 log k, and say ϕ moves the points 1, …, t and fixes the rest, where t ≤ 32 log k. The number of possibilities for b_{1}, …, b_{f} is at most (q^{m^{2}})^{32 log k}, which is less than q^{512 log^{2} k}. Of the remaining b_{i}, at most 32 log k of them are not equal to I_{m}; hence the number of possibilities for b_{t+1}, …, b_{k} is at most k^{32 log k}.(q^{m^{2}})^{32 log k}. We conclude that

|x^{G} ∩ Bϕ| < q^{512 log^{2} k}.k^{32 log k}.(q^{m^{2}})^{32 log k} < q^{512 log^{2} k}.k^{32 log k}.q^{512 log^{2} k}.

Since the number of possibilities for ϕ is at most k^{32 log k}(32 log k)!, and k is large, it follows that

|x^{G} ∩ M| < (q^{k})^{o(1)} ≤ (q^{n})^{o(1)} ≤ |x^{G}|^{o(1)},

giving the result.

Finally, case (2) is handled in exactly the same way as case (2) in the proof of 4.2. ♠

Lemma 4.6. If M ∈ C_{8}, then (⋆) holds.

Proof. Recall we are excluding M = O_{n}(q) < Sp_{n}(q) with q even (as this is a subspace subgroup). Thus when M ∈ C_{8}, we have G_{0} = L_{n}(q) and M of type P Sp_{n}(q), O_{n}(q) or U_{n}(q^{1/2}). Let s = ν(x). Then by 3.6,

|x^{G} ∩ M| ≤ n_{s}(M) < cq^{(s/2)(2n−s+5)},

so by 3.4,

f(x, M) < \frac{(s/2)(2n − s + 5)}{2s(n − s)},

which (for 0 ≤ s < (1/2 + δ)n) is bounded above by 3/4 + δ′. ♠

Notice that Theorem (⋆) is now proved.

References

[As] M. Aschbacher, On the maximal subgroups of the finite classical groups, Invent. Math. 76 (1984), 469-514. MR 86a:20054

[AS] M. Aschbacher and G.M. Seitz, Involutions in Chevalley groups over finite fields of even order, Nagoya Math. J. 63 (1976), 1-91. MR 54:10391

[Ba] L. Babai, On the order of uniprimitive permutation groups, Annals of Math. 113 (1981), 553-568. MR 83j:20010

[Ca1] P.J. Cameron, Some open problems on permutation groups, in Groups, Combinatorics and Geometry (eds: M.W. Liebeck and J. Saxl), London Math. Soc. Lecture Note Series 165, Cambridge University Press, Cambridge, 1992, 340-350. MR 94c:20005

[Ca2] P.J. Cameron, Permutation groups, in Handbook of Combinatorics (eds: R.L. Graham et al.), Elsevier Science B.V., Amsterdam, 1995, 611-645. MR 97e:20002

[CK] P.J. Cameron and W.M. Kantor, Random permutations: some group-theoretic aspects, Combinatorics, Probability and Computing 2 (1993), 257-262. MR 95b:20006

[CIK] C.W. Curtis, N. Iwahori and R. Kilmoyer, Hecke algebras and characters of parabolic type of finite groups with BN-pairs, IHES Publ. Math. 40 (1972), 81-116. MR 50:494

[Di] J.D. Dixon, The probability of generating the symmetric group, Math. Z. 110 (1969), 199-205. MR 40:4985

[GSSh] D. Gluck, Á. Seress and A. Shalev, Bases for primitive permutation groups and a conjecture of Babai, J. Algebra 199 (1998), 367-378. CMP 98:06

[GL] D. Gorenstein and R. Lyons, The local structure of finite groups of characteristic 2 type, Memoirs Amer. Math. Soc. 42, No. 276 (1983). MR 84g:20025

[Gu] R.M. Guralnick, The genus of a permutation group, in Groups, Combinatorics and Geometry (eds: M.W. Liebeck and J. Saxl), London Math. Soc. Lecture Note Series 165 (1992), 351-363. MR 94a:20006

[GK] R.M. Guralnick and W.M. Kantor, Probabilistic generation of finite simple groups, J. Algebra, to appear.

[GKS] R.M. Guralnick, W.M. Kantor and J. Saxl, The probability of generating a classical group, Comm. in Algebra 22 (1994), 1395-1402. MR 95a:20030

[GLSS] R.M. Guralnick, M.W. Liebeck, J. Saxl and A. Shalev, Random generation of finite simple groups, to appear.

[GM] R.M. Guralnick and K. Magaard, On the minimal degree of a primitive permutation group, J. Algebra 207 (1998), 127-145. CMP 98:17 [GT] R.M. Guralnick and J.G. Thompson, Finite groups of genus zero, J. Alg. 131 (1990),

303-341. MR 91e:20006

[HLS] J. Hall, M.W. Liebeck and G.M. Seitz, Generators for finite simple groups, with applications to linear groups, Quart. J. Math. 43 (1992), 441-458. MR 93k:20030

[KL] W.M. Kantor and A. Lubotzky, The probability of generating a finite classical group, Geom. Ded. 36 (1990), 67-87. MR 91j:20041

[KLi] P.B. Kleidman and M.W. Liebeck, The Subgroup Structure of the Finite Classical Groups, London Math. Soc. Lecture Note Series 129, Cambridge University Press, 1990. MR 91g:20001

[Li1] M.W. Liebeck, On the orders of maximal subgroups of the finite classical groups, Proc. London Math. Soc. 50 (1985), 426-446. MR 87a:20046

[Li2] M.W. Liebeck, On minimal degrees and base sizes of primitive permutation groups, Arch. Math. 43 (1984), 11-15. MR 86d:20004

[LP] M.W. Liebeck and C.W. Purvis, On the genus of a finite classical group, Bull. London Math. Soc. 29 (1997), 159-164. MR 98h:20086

[LPy] M.W. Liebeck and L. Pyber, Upper bounds for the number of conjugacy classes of a finite group, J. Algebra 198 (1997), 538-562. CMP 98:06

[LS] M.W. Liebeck and J. Saxl, Minimal degrees of primitive permutation groups, with an application to monodromy groups of covers of Riemann surfaces, Proc. London Math. Soc. (3) 63 (1991), 266-314. MR 92f:20003

[LiSh1] M.W. Liebeck and A. Shalev, The probability of generating a finite simple group, Geom. Ded. 56 (1995), 103-113. MR 96h:20116

[LiSh2] M.W. Liebeck and A. Shalev, Classical groups, probabilistic methods, and the (2,3)- generation problem, Annals of Math. 144 (1996), 77-125. MR 97e:20106a

[LPS] M.W. Liebeck, C.E. Praeger and J. Saxl, On the 2-closures of primitive permutation groups, J. London Math. Soc. 37 (1988), 241-252. MR 89b:20009

[Ma] W. Magnus, Non-Euclidean Tesselations and Their Groups, Academic Press, New York – London, 1974. MR 50:4774

[Sh1] A. Shalev, A theorem on random matrices and some applications, J. Algebra 199 (1998), 124-141. CMP 98:06

[Sh2] A. Shalev, Random generation of simple groups by two conjugate elements, Bull. London Math. Soc. 29 (1997), 571-576. MR 98h:20122

[Shi] T. Shih, Bounds of Fixed Point Ratios of Permutation Representations of GL_{n}(q) and Groups of Genus Zero, Ph.D. Thesis, California Institute of Technology, Pasadena, 1990.

[Wa] G. E. Wall, On the conjugacy classes in the unitary, symplectic and orthogonal groups, J. Austral. Math. Soc. 3 (1965), 1-62. MR 27:212

Department of Mathematics, Imperial College, London SW7 2BZ, England

E-mail address: m.liebeck@ic.ac.uk

Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel

E-mail address: shalev@math.huji.il