Derangements in non-Frobenius groups
Daniele Garzoni




Daniele Garzoni, Department of Mathematics, University of Southern California, Los Angeles, CA 90089-2532,
	USA
garzoni@usc.edu





§ ABSTRACT 
We prove that if G is a transitive permutation group of sufficiently large degree n, then either G is primitive and Frobenius, or the proportion of derangements in G is larger than 1/(2n^1/2). This is sharp, generalizes substantially bounds of Cameron–Cohen and Guralnick–Wan, and settles a conjecture of Guralnick–Tiep in large degree. We also give an application to coverings of varieties over finite fields.



Derangements in non-Frobenius groups
    Daniele Garzoni
    
====================================





§ INTRODUCTION



Given a finite transitive permutation group G on a set Ω of size n≥ 2, an element g∈ G is called a derangement if it acts without fixed points on Ω. 

Chebotarev density theorem establishes a direct link between derangements and rational points of varieties over finite fields. In particular, derangements arise naturally in arithmetic geometry and were apparent already in the work of Frobenius in the nineteenth century. Derangements have other applications, for example to problems of random generation (see <cit.>) and to the structure of Brauer groups (see <cit.>).

Denote by δ(G,Ω), or simply δ(G), the proportion of derangements of G on Ω. A lemma going back to Jordan asserts that δ(G)>0, and giving lower bounds for δ(G) has been a central problem in group theory in the past three decades;
see <Ref>, <Ref> and <cit.> for context related to this problem.


Answering a question of Lenstra motivated by the number field sieve (see <cit.>), Cameron–Cohen <cit.> showed that δ(G)≥ 1/n; more precisely, if n≥ 3 then one of the following holds:

	 
  (i) G is a Frobenius group of order n(n-1) and δ(G)=1/n.
    
  (ii) δ(G)>1/n.

The proof of this result is very short and elementary (see also <cit.>, which further simplifies the proof). See below for the definition of a Frobenius group. Later, Guralnick–Wan <cit.> showed that if n≥ 7 then one of the following holds:

	
  (i) G is a Frobenius group of order n(n-1)/a and δ(G)=a/n, where a∈{1,2}.
    
  (ii) δ(G)>2/n.

The proof of this result is much harder than that of <cit.> – it requires, besides some nontrivial elementary arguments,  the Classification of Finite Simple Groups. 


The groups attaining the bounds δ(G)=1/n and 2/n are very special: they are primitive Frobenius groups.  We recall that a transitive permutation group G is called Frobenius if some nontrivial element fixes a point, and only the identity fixes at least two points. A classical result of Frobenius, based on character theory, states that G contains a regular normal subgroup, which is furthermore nilpotent by a result of Thompson. 


If G is Frobenius, then |G|=n(n-1)/a for a divisor a of n-1, and δ(G)=a/n. There are infinitely many examples attaining this bound; for instance, for every prime power n and every divisor a of n-1, consider G=_n ⋊ G_0 where G_0≤_n^× has order (n-1)/a. 
In particular, we find infinitely many examples with

    δ(G)=1/n,2/n, 3/n, 4/n…

Given the exceptionality of Frobenius groups, it is natural to ask whether a considerably stronger lower bound holds in the other cases. 
The purpose of this paper is to answer this question in large degree, by showing that a bound of approximately 1/(2n^1/2) holds. What is more, it is sufficient to exclude groups that are both primitive and Frobenius in order to get this improvement.
Let

    g(n):=n^1/2+1/2n∼1/2n^1/2.




Let G be a finite transitive permutation group of sufficiently large degree n. Then one of the following holds:

    
  * G is primitive and Frobenius.
    
  * δ(G)≥ g(n).


There are primitive non-Frobenius groups attaining equality in (2); take 
 G=_n⋊ G_0, where n is a square, G_0=_1(n)⋊σ and σ is the n^1/2-th power map (see <Ref>).
 

<Ref> generalizes substantially the aforementioned bounds of <cit.>. What is more, in <cit.>, Guralnick–Tiep conjectured that δ(G)≥ 1/n^1/2 if G is primitive affine and non-Frobenius. <Ref>, in particular, confirms (up to a necessary minor amendment) this conjecture in large degree. 


We stress at once that the case of primitive affine groups is the crux of this paper; see <Ref> and <Ref> for details.



We state a consequence of <Ref> that highlights the aforementioned connection between derangements and arithmetic (see <cit.>).

 

 Let π X → Y be a separable morphism of sufficiently large degree n between integral normal quasi-projective varieties of dimension d over a finite field _ℓ. Assume that the Galois closure of π is geometrically integral, and that the monodromy group of π is not primitive and Frobenius. Then,
 
    |π(X(_ℓ))| ≤(1- g(n)) ℓ^d + O_π(ℓ^d-1/2).

    

  If π is defined by a polynomial f(x)∈_ℓ(Y)[x],  then the condition that the monodromy group is primitive and Frobenius can be phrased field theoretically as follows: _ℓ(X)/_ℓ(Y) is minimal, and the Galois closure of _ℓ(X)/_ℓ(Y) is not _ℓ(X), and is generated by any two roots of f. Therefore the bound in <Ref> applies whenever this (very restrictive) condition does not hold.

    If the Galois closure of π (namely, the normalization of X in the Galois closure of _ℓ(X)/_ℓ(Y)) is not geometrically integral, then one must more generally count derangements in a coset (indeed this is one of the motivations of <cit.>, which addresses the case of curves).
    
  With regard to <Ref>, it seems worth noting that one gets almost the same bound (approximately 1/(60n^1/2)) just by excluding primitive Frobenius subgroups of _1(n), as opposed to all primitive Frobenius groups. Let
  
    f(n):= n^1/2+1/60n∼1/60n^1/2.



	
	Let G be a finite transitive permutation group of sufficiently large degree n. Then one of the following holds:
	
		
  * G is a primitive Frobenius subgroup of _1(n).
		
  * δ(G)≥ f(n).
	

There are primitive (Frobenius) groups that do not lie in (1) and that attain equality in (2), of the form G=_n^2⋊ G_0, where  _2(5)⊴ G_0; see <Ref>. 

   

 §.§ About the proof
 
    
    We prove  an elementary reduction of <Ref> to primitive groups, see <Ref>.
    
Luczak–Pyber <cit.> and Fulman–Guralnick 
<cit.> proved the so-called Boston–Shalev conjecture, asserting that if G is a finite simple transitive permutation group of degree n, then δ(G)≥ϵ for an absolute constant ϵ>0. See also <cit.> for a conjugacy-class version. A consequence of this result is the following (see <cit.>):


(Luczak–Pyber, Fulman–Guralnick)

Let G be a primitive non-affine permutation group of degree n. Then δ(G)≥ϵ/log(n) for an absolute constant ϵ>0.     


Of course, if n is sufficiently large then /log(n) > g(n), and so in view of <Ref> and <Ref>, it remains to prove <Ref> in the case where G is primitive affine, so G=V⋊ G_0 where V is elementary abelian and G_0≤(V) is irreducible. 

In this case, there is an amusing  phenomenon – G has many elements fixing no point of V=Ω if and only if G_0 has many elements fixing a point of V{0} (see <Ref>).



In particular, denoting by α(G_0,V), or simply α(G_0), the proportion of elements of G_0 having eigenvalue 1 on V, our task is to lower bound α(G_0). This is a well-studied problem, especially for quasisimple groups; see for example <cit.> and the references therein. Much work has been devoted to the study of representations where every element has eigenvalue 1, which is to say, α(G_0)=1.

The following theorem about irreducible linear groups implies <Ref> for primitive affine groups. We work over any finite field, not necessarily of prime order. Let

    h(n):=n^1/2+2/2(n-1)∼1/2n^1/2.





Let d be a positive integer and q be a prime power, with qd sufficiently large. Let V≅_q^d and G≤_d(q) be irreducible, and r be maximal so that G≤_d/r(q^r). Then one of the following holds:

    
  * d=r and G acts semiregularly on V{0}.
    
  * G acts semiregularly on V{0}, and α(G)≥ 1/(60(q^d/2-1)) and δ(V⋊ G)≥ f(q^d).
    
  * α(G)≥ h(q^d) and δ(V⋊ G) ≥ g(q^d).


(In (2) and (3), δ(V⋊ G)=δ(V⋊ G,V) refers to the affine action on V.) We already remarked that the equalities in the bounds for δ(V⋊ G) can be attained. The same is true for the bounds for α(G), see <Ref>.

In most cases (e.g., for d/r≥ 3) we will prove the bound for α(G), and the required bound for δ(V⋊ G) will follow immediately.


In order to prove <Ref>, we will reduce the problem to the case of primitive linear groups and exploit the powerful structure theory of these groups, see <Ref>. The reduction is elementary (<Ref>), so assume G is primitive. At this point, after some further reductions, we will focus on the generalized Fitting subgroup L (whose index in G is relatively small), and we will count elements with eigenvalue 1 in L. Assuming for simplicity that L acts absolutely irreducibly, we have L=G_1∘⋯∘ G_t, where G_i is either central or extraspecial or a power of a quasisimple group, and V=V_1⊗⋯⊗ V_t. This will essentially reduce the problem to lower bounding α(H) when H≤_1(q) (<Ref>), or H≤_2(q) (<Ref>), or H  extraspecial or quasisimple (<Ref>). 

A nice feature of the proof is that we will be able to prove <Ref> only by working with large extraspecial or quasisimple groups (and in many cases, bounds much stronger than we need hold). Note, however, that in the central product L=G_1∘⋯∘ G_t, there may certainly be factors that have small order, and to which our bounds do not apply. In order to handle this issue, we will group together all the factors of small order (thereby paying a constant); what we gain in the factors of large order will be enough to compensate.

We wonder whether, in the notation of <Ref>,  the bound α(G)≫ 1/q^r holds. There are many examples where a matching upper bound holds, and the lower bound holds if d/r≤ 2 (by <Ref>) and for many quasisimple groups in defining characteristic, see <Ref> and also <cit.>. This problem could be considered as an analogue of the Boston–Shalev conjecture for affine groups over fields of bounded size.



 §.§ Notation
 We write f=O(g) or f≪ g if there exists a positive absolute constant C such that f≤ Cg.




 §.§ Acknowledgements
 I thank Bob Guralnick for suggesting the proof of <Ref> and for  interesting discussions, and Michael Larsen for an explanation on the Lang–Weyl estimate for Suzuki and Ree groups.











    




§ REDUCTION TO PRIMITIVE GROUPS






    Assume that <Ref> holds for primitive groups. Then, δ(G)>g(n) for every imprimitive permutation group G  of sufficiently large degree n.

In fact, the proof will show that if G is imprimitive then δ(G)>1/(1.5n^1/2).




 Let Ω= Ω_1∪⋯∪Ω_t be a maximal system of imprimitivity, with |Ω_i|=m≥ 2 and t≥ 2, let Δ={Ω_1, …, Ω_t} and ρ G →(Δ)≅ S_t.  Then, G^ρ is primitive.

By <cit.>, we have δ(G,Ω)≥δ(G^ρ,Δ)≥ 1/t. If t is bounded this is ≫ 1 and we are done, so suppose that t is large.

Case 1: G^ρ is not Frobenius. Then, by <Ref> δ(G,Ω)≥δ(G^ρ,Δ) ≥ g(t). Since n=mt≥ 2t, we have g(t) > g(n) and we are done. 

Case 2: G^ρ is Frobenius. We have |G^ρ|= t(t-1)/a for a divisor a of t-1, and δ(G^ρ, Δ) = a/t.


Assume first t/a < 1.5n^1/2. Then a/t > 1/(1.5n^1/2) > g(n) and we are done. Assume then t/a ≥ 1.5n^1/2, i.e., t≥ 2.25ma^2. For each i=1, …, t, let H_i=Stab_G(Ω_i), so H_i acts transitively on Ω_i. Since G^ρ is Frobenius, a nontrivial element of G^ρ fixes at most one point. In particular,

    δ(G,Ω) ≥∑_i=1^t ( δ(H_i, Ω_i)/|G:H_i| - 1/|G^ρ|) = δ(H_1, Ω_1)- a/t-1.

Now fix 0< < 1-1/1.1 ≤ 1-1/(1.1a) (e.g., =0.09) and take t large so that (t-1)/t> 1-. By <cit.>, we have δ(H_1, Ω_1)≥ 1/m, and the assumption t≥ 2.2ma^2 implies 

    1/m - a/t-1   > 1/m - a/(1-)t≥1/m( 1 - 1/(1-)2.2a) 
          > 1/2m
            > 1.4/2n^1/2
              > g(n),

which concludes the proof.    






§ AFFINE GROUPS: PRELIMINARIES



Let G be a finite group and let V be an _qG-module of dimension d<∞. Denote by π the permutation character of G acting on V, and define η(G)=η(G,V) as the inverse of the harmonic mean of π, i.e.,

    η(G)=1/|G|∑_g∈ G1/π(g).




δ(V⋊ G)=1-η(G).



Let gv∈ V⋊ G. We have u^gv= ug+v, so u^gv=u if and only if v=u-ug. It follows that gv is a derangement if and only if v∉ [g,V]. Let c(g):=(_V(g)), so π(g)=q^c(g). Since [g,V] is a subspace of V of dimension d-c(g), and counting derangements  by summing over all g∈ G and all v∉[g,V], we have

    δ(V⋊ G) = 1/|G|∑_g∈ Gq^d - q^d-c(g)/q^d = 1- η(G)

as wanted.


Recall that α(G) denotes the proportion of elements of G with eigenvalue 1 on V. 



 
    (1-1/q)α(G) ≤δ(V⋊ G)≤α(G).




Writing α=α(G) and η=η(G), note that

    1/|G|(1-α)|G|≤η≤1/|G|( α|G|/q+(1-α)|G|) = 1-(1-1/q)α.

Now just apply Lemma <ref>.



In particular, as already noticed in the introduction, in most cases in order to prove <Ref> it will be sufficient to bound α(G). 





§ PROOF OF <REF> MODULO PRELIMINARY RESULTS



Here we reduce the proof of <Ref> to the following three results, that we will prove in <Ref>.




<Ref> holds if d=r, i.e., G≤_1(q^d).




<Ref> holds if G is primitive and d/r=2, i.e., G≤_2(q^d/2).






   There exists an absolute constant C>0 such that if d≥ 3,  G≤_d(q) is an absolutely irreducible quasisimple or extraspecial group of order at least C, and Z≤_q^×, then  α(ZG)> 2|O|log(q)q^-d/2, where  O=(G) if G is quasisimple and O=_2r(s) if G is extraspecial of order s^2r+1.
   


The factor 2 in the inequality in <Ref> will be useful in the proof of <Ref> for technical reasons. 

In <Ref>, we do not assume that G is primitive because it will be convenient to quote the result in that form. In every case, let us show that the imprimitive case follows from the primitive one.


	
If <Ref> holds when G is a primitive linear group, then it holds when G is an imprimitive linear group.



Let G≤_m(q)≀ S_t  preserve the decomposition V=V_1⊕⋯⊕ V_t, with t≥ 2, permuting transitively the factors, and assume the stabilizer H of V_1 acts primitively on V_1. Note α(G,V)≥α(H,V_1)/t.
	If H does not induce a semiregular group on V_1{0}, then α(H,V_1)≥ h(q^m) > 1/(2q^m/2) and so α(G,V)> 1/(2tq^m/2)≫ 1/q^d/3. Assume then that H induces a semiregular group on V_1{0}; then 
	s:=|H^V_1|≤ q^m-1 and α(H,V_1)=1/s, and so α(G,V)≥ 1/(t(q^m-1)). If m≤ d/3 this is ≫ q^d/3, so assume m=d/2. 
	
	For i=1,2, let N_i be the subgroup of H acting trivially on V_i. We have  |G|=2|N_1|s. The elements of H with eigenvalue 1 are those of N_1∪ N_2,
	so
	
    α(G,V)≥2|N_1|-1/2|N_1|s≥1/2s≥1/2(q^d/2-1).

	Moreover, δ(V⋊ G,V)≥ 1/(4(q^d/2-1))>f(q^d) by <Ref>, so the case where G is semiregular on V{0} is done. Assume then G is not semiregular on V{0}. If |N_1|≥ 2, then we can improve the second inequality in (<ref>) and get α(G,V)≥ 3/(4(q^d/2-1)) > h(q^d). What is more, the nontrivial elements of N_1∪ N_2 fix q^d/2 vectors, so an easy modification of the proof of <Ref> gives δ(V⋊ G,V)≥ 3/(4(q^d/2-1))·(1-1/q^d/2)> g(q^d)
 and we are done. Assume finally N_1=1, so |G|=2s. If G contains at least three elements with eigenvalue 1, then
	
    α(G,V)≥3/|G| = 3/2s≥3/2(q^d/2-1),

and so by <Ref> δ(V⋊ G,V)≥ 3/(4(q^d/2-1)) and we are done. Assume then G contains a unique nontrivial element x with eigenvalue 1; then |x|=2, and α(G,V) = 2/|G| ≥ 1/(q^d/2-1). We have x∈ G H,
so write x=(x_1,x_2)τ where 1≠τ∈ S_2 and x_i∈_d/2(q). Since |x|=2, we have x_1x_2=1, from which x fixes q^d/2 vectors and so as above δ(V⋊ G,V)≥ 1/(q^d/2-1)·(1-1/q^d/2)>g(q^d) and we are done.
	

We now prove <Ref> assuming <Ref>.


Let G≤_d(q) be irreducible. In view of <Ref>, we may assume  G is primitive. From now, for convenience we change notation and replace d/r by d and q^r by q. In particular, G≤_dr(q^1/r) is primitive and d is minimal so that G≤_d(q).



Let H:=G∩_d(q). By Clifford's theorem, each characteristic subgroup L of H acts homogeneously. Let V_1 be an _q L-component, whose dimension we denote by a. By Schur's lemma, __q L(V_1) is a field extension of _q, say of degree b. By <cit.>, __d(q)(L)≅_d/b(q^b), and since G normalizes L, we get G≤_d/b(q^b). By the minimality of d, we deduce b=1, which is to say, V_1 is absolutely irreducible.


Choose now L=F^*(H). We have L=(H) R, where R= G_1 ∘⋯∘ G_t and the following holds. 
There exists 0≤ r ≤ t such that for 1≤ i≤ r, G_i is an extraspecial p_i-group of order p_i^2r_i+1, of exponent p_i if p_i is odd; and possibly replacing G_i by ZG_i where Z≤_q^× has order 4,
we have H/_H(G_i)≤  p_i^2r_i._2r_i(p_i). 
For r+1≤ i≤ t, G_i is a central product of ℓ_i copies of a quasisimple group S_i, and H/_H(G_i) ≤(G_i)=Aut(S_i)≀ S_ℓ_i.

Recall now that (L)=_H(L). We have

    H/_H(L)=H/⋂_i _H(G_i) ≤∏_i=1^t H/_H(G_i)

and therefore

    |H|/|L|≤∏_i=1^r |O_i|

where for i≤ r, O_i := _2r_i(p_i), and for i≥ r+1, O_i:=
Out(S_i)≀ S_ℓ_i.

Assume first that L acts (absolutely) irreducibly on V. If d≤ 2, we have G≤_1(q) or _2(q) and we conclude by <Ref>. Assume then d≥ 3. We will prove that 

    α(L,V)> 2log(q)|H:L|q^-d/2,

which implies α(G, V) > 2/q^d/2  since |G:L|≤log(q)|H:L|, and so δ(V⋊ G,V)> 1/q^d/2 by <Ref>. This will conclude the proof.


Since L is absolutely irreducible and L=(H)R,  R is also absolutely irreducible. Then, by <cit.> we deduce that W=W_1⊗⋯⊗ W_t, where W_i is an absolutely irreducible _qG_i-module of dimension d_i. In particular, for 1 ≤ i ≤ r, W_i is faithful and d_i=p_i^r_i. For r+1≤ i≤ t, W_i = M_i_1⊗⋯⊗ M_iℓ_i where M_i_j≅ M_i is a faithful absolutely irreducible _qS_i-module of dimension m_i (again by <cit.>). (In other words, W_i is a tensor product of ℓ_i copies of M_i, but it will sometimes be useful to make use of the indices i_j.) We may take it that if S_i≅ S_j with i≠ j then M_i≇M_j. 


Let now C>0 satisfy the following conditions:

    
  ♢ C satisfies the conclusion of <Ref>.
    
  ♢ If q is a power of s, s(s^2-1)≥ C, and either ℓ≥ 3 or ℓ≥ 1 and s<q, then 

    2log(q)(2slog(s))^ℓℓ! < q^2^ℓ-1.
.

  ♢ If q(q^2-1)≥ C and a≥ 2 then

    2log(q)(24qlog^2(q))^a/2(1+δ· qlog(q)) < q^2^a-1,

where δ=0 if a=2, and δ=1 if a≥ 3.

Let us also record the following inequality, which holds for d≥ 3, ℓ≥ 1, and q a prime power:

    ℓ! q^dℓ/2≤ q^d^ℓ/2.






Now that we fixed C, let g(C) be so that for every ℓ≥ g(C) and every m≥ 2, 

    2C^Cℓℓ!q^mℓlog(q) < q^m^ℓ/2

(It is easily seen that g(C) exists.) For later use, note that if G is a finite group of order at most C, then (crudely) |(G)|≤ C^C.


Let now f(C) be equal to 1, plus the product of all the following quantities: For every extraspecial group of order s^2f+1≤ C, s^2f+1|_2f(s)|; For every quasisimple group L of order at most C and for every ℓ≤ g(C), (|(L)|^ℓℓ!)^|L|. (For a later use, note that |L| is an upper bound for the number of equivalence classes of absolutely irreducible _q L-representations.)




Now let

    
  ♢ Ω_1 be the set of indices 1≤ i ≤ t such that either i≤ r and |G_i|≤ C, or i≥ r+1 and |S_i|≤ C and ℓ_i ≤ g(C). 


  ♢ Ω_2 be the set of indices r+1≤ i ≤ t such that |S_i|≤ C and ℓ_i > g(C). 


  ♢ Ω_3 be the set of indices r+1≤ i ≤ t not belonging to ∪_j≤ 2Ω_j and such that m_i=(M_i)=2, ℓ_i≤ 2 and S_i≅_2(q).

  ♢  Ω_4 be the set of indices r+1≤ i ≤ t not belonging to ∪_j≤ 2Ω_j and such that m_i=(M_i)=2, and ℓ_i ≥ 3 or S_i≅_2(q_i) with q_i<q.


  ♢ Ω_5 be the set of remaining indices. 


For j=1, …, 5, denote d(α_j):=∏_i∈Ω_id_i.  Since n is sufficiently large, we may assume that ∪_i>1Ω_i ≠∅. Now choose any j∈∪_i>1Ω_i. If j≤ r replace G_j by (H)G_j; if j≥ r+1 replace S_j_1 by (H)S_j_1. From now on we will not specify this in the notation. In particular, L=G_1∘⋯∘ G_t.


We make use of the following easy observation: If g_i∈ G_i has eigenvalue 1 on W_i, then the image of (g_1, …,g_t) in L has eigenvalue 1 on V. We deduce that

    α(L, V)≥∏_1≤ i ≤ 5α_i

where α_i = ∏_j∈Ω_iα(G_j, W_j). 



Observe that by definition of f(C),

    α_1/∏_i∈Ω_1|O_i|≥1/∏_i∈Ω_1|G_i||O_i| > 1/f(C).

Moreover, by <cit.> and Lemma <ref>, for i∈Ω_2, α(S_i,M_i)≥δ(M_i⋊ S_i,M_i)≥ 1/q^m_i, therefore by <Ref>, noting that d_i=m_i^t_i, we get that if Ω_2≠∅ then

    α_2/∏_i∈Ω_2|O_i|≥∏_i∈Ω_21/C^Cℓ_iℓ_i! q^m_iℓ_i > 2log(q) ∏_i∈Ω_21/q^d_i/2≥2log(q)/q^d(α_2)/2.

(Note that the assumption that Ω_2≠∅ is only needed to allow the factor 2log(q). The same will hold for Ω_4 and Ω_5, below.)

By <Ref>, by the definition C and by (<ref>), we have that if Ω_5≠∅ then
 
    α_5/∏_i∈Ω_5|O_i|  > 2log(q) ∏_1≤ i≤ r 
     i∈Ω_51/q^d_i/2∏_r+1≤ i≤ t 
     i∈Ω_51/ℓ_i! q^m_iℓ_i/2≥2log(q)/q^d(α_5)/2.


Note now that for i∈Ω_3∪Ω_4, S_i=_2(q_i) or (H)_2(q_i), where q is a power of q_i and M_i is either the natural module or the dual. (And there is at most one i_j for which S_i_j≠_2(q_i).) We have 
α(S_i,M_i)≥ 1/q_i (see <Ref>).
Using |O_i|≤ 2log(q_i) and
 (<ref>) (applied with s=q_i) we deduce that if Ω_4≠∅ then

    α_4/∏_i∈Ω_4|O_i|≥∏_i∈Ω_41/(2log(q_i)q_i)^ℓ_iℓ_i!  > 2log(q)/q^d(α_4)/2



Now, let us address Ω_3. If a:=log(d(α_3)) = ∑_i∈Ω_3ℓ_i is even, we choose an arbitrary matching of the factors S_i_j,
 i∈Ω_3, 1≤ j≤ℓ_i.  If a is odd, we do the same by leaving out an arbitrary factor. If S_ν and S_η are matched, we readily see that α(S_ν∘ S_η,M_ν⊗ M_η)≥ 1/(3q).
(Indeed, choose an element of S_ν having eigenvalues in _q^× – for q≥ 7 the proportion of choices is at least (q-3)/(2(q-1))≥ 1/3 –
and choose an element of S_η having eigenvalue λ^-1, where λ is an eigenvalue of the first element – the proportion of choices is at least 1/q, see <Ref>.) Using that |O_i|≤ 2log(q), we get

    α_3/∏_i∈Ω_3|O_i|≥1/qlog(q)1/(24qlog^2(q))^a/2

where the first factor 1/(qlog(q)) appears only if a is odd.



Is is now easy to deduce the desired conclusion (<ref>), using the assumption d≥ 3. Indeed, if a≥ 2 then by <Ref>, the right-hand side of (<ref>) is at least 2log(q)/q^d(α_3)/2, and for a=1 it is equal to 1/(qlog(q)). In particular, if a=0 or a≥ 2 then we get from <Ref>

    α(L,V)/|H:L|> 2log(q)/f(C)q^(d(α_2)+d(α_3)+ d(α_4)+ d(α_5))/2

which for sufficiently large qd is at least 2log(q)q^-d/2, giving (<ref>) as desired. If a=1, then the assumption d≥ 3 implies that Ω_1∪Ω_2∪Ω_4∪Ω_5≠∅, and one concludes similarly, using that d(α_i)=1 or ≥ 3 for i=2,4,5.


Assume now L is not irreducible. Letting V' be a component, we have α(L,V')=α(L,V) and |V'|≤ |V|^1/2, so if d':=(V')≥ 3 then the conclusion follows immediately from <Ref> (and in fact, we can simply use |V'|≤ |V|). If d'=2,
then d≥ 4 and  by <Ref>, α(L,V')≫ 1/q. Since |H:L|≪ 1
we have α(L,V)≫ 1/q ≥ 2log(q) |H:L|q^-d/2 for qd large.

This concludes the proof of <Ref> assuming <Ref>.














§ _1(Q)



In this section we prove <Ref> in the case where d=r (that is, <Ref>). The bulk of the proof boils down to elementary number theory.


We will work with any subgroup of _1(q^d) (with no irreducibility assumption); for convenience, we replace q^d by q in the notation, so G≤_1(q) is not semiregular on V{0}. 



    Let G≤_1(q) be such that G is not semiregular on V{0}. If q is sufficiently large then α(G,V)≥  h(q) and δ(V⋊ G,V)≥ g(q).





Let us now fix some notation. Write q=p^f, where G≤_1(q)⋊Gal(_q/_p) and G projects onto Gal(_q/_p) (so in this section p need not be prime). Since G is not semiregular on V{0}, we have f>1.


Denote H:=G∩_1(q) and t:=|H|, and write G=H,z, with z=τ x, τ is the p-th power map and x∈_1(q). Let x:=xH∈_1(q)/H and m:=|x|, so m | (q-1)/(p-1) and m| (q-1)/t. We denote by A the set of nontrivial elements of G fixing a nonzero vector, and by (a,b) the greatest common divisor of the positive integers a and b.

Fix a coset z^ℓ H, with ℓ a proper divisor of f.





We have that A∩ z^ℓ H≠∅ if and only if x^(p^ℓ-1)/(p-1) is a (p^ℓ-1)-th power. Moreover, if this is the case, 

    |A∩ z^ℓ H|=(q-1/p^ℓ-1, t).




Write y:=x^(p^ℓ-1)/(p-1), so z^ℓ=τ^ℓ y. For 0≠ v∈_q and h∈ H we have vz^ℓ h = v^p^ℓyh, and this is equal to v if and only if yh = v^1-p^ℓ. In particular, there exist h and v≠ 0 such that vz^ℓ h=v if and only if y is a (p^ℓ-1)-th power modulo H.

Assume now that yh=v^1-p^ℓ. Then A ∩ z^ℓ H is the set of elements obtained by multiplying z^ℓ h by a (p^ℓ-1)-th power of _1(q) contained in H. The number of these elements is ((q-1)/(p^ℓ-1),t), and this concludes the proof.





We introduce further notation. For a prime number r and a positive integer a, we let γ_r(a) be the integer i such that r^i is the r-part of a. Moreover, we let γ_r(a):=γ_r((p^a-1)/(p-1)). Finally, we write m=(q-1)/(tC) for a positive integer C.

We will often be concerned with several primes r_1, …, r_b. In this case, for convenience we will write γ^i(a)=γ_r_i(a), and similarly γ^i(a)=γ_r_i(a).


Let r_1, …, r_b be the distinct prime divisors of (f,p-1) (possibly b=0), and let ℓ<f be a divisor of f. Then, A ∩ z^ℓ H≠∅ if and only if, for every i=1, …, b, one of the following holds:

    
  (i) γ^i(m)≤γ^i(ℓ).
    
  (ii) γ^i(p^ℓ-1) ≤γ^i(C) + γ^i(ℓ), i.e., γ^i(p-1) ≤γ^i(C).




By <Ref>, A∩ z^ℓ H≠∅ if and only if x^(p^ℓ-1)/(p-1) is a (p^ℓ-1)-th power. Note that x^(p^ℓ - 1)/(p-1) is a (p^ℓ -1)-th power if and only if

    m/(m,(p^ℓ-1)/(p-1))|(p^f-1)/t/((p^f-1)/t, p^ℓ-1).

Using that Cm=(p^f-1)/t, we see that this is equivalent to 

    (Cm, p^ℓ-1) | C· (m,(p^ℓ-1)/(p-1)).

This is equivalent to saying that, for every prime number r,

    min{γ_r(C) + γ_r(m),γ_r(p^ℓ-1)}≤γ_r(C) + min{γ_r(m), γ_r(ℓ)}.

We need to show that (<ref>) holds for every r if and only, for every i=1,…, b, (i) or (ii) in the statement holds.

We first claim that (<ref>) holds for r=r_i if and only if (i) or (ii) holds for i. This is a straightforward check; let us show, for instance, that (i) or (ii) in the statement for i implies (<ref>) for r=r_i. Assume (i). Then the RHS of (<ref>) for r=r_i is γ^i(C) + γ^i(m). But this term appears in the minimum of the LHS, so (<ref>) holds. Assume, now, (ii), and assume that (i) does not hold (otherwise we are in the previous case). Then γ^i(m)> γ^i(ℓ), so by (ii) the LHS is γ^i(p^ℓ-1); moreover the RHS is γ^i(C) + γ^i(ℓ), hence (<ref>) holds by (ii).

The converse implication for r=r_i is proved similarly: Assume that (<ref>) holds for r=r_i, and assume that (i) does not hold for i; then deduce easily that (ii) must hold.

In order to conclude the proof, it is sufficient to show that (<ref>) always holds for every prime r not dividing (f,p-1). In order to check this, we may assume γ_r(m)≥ 1, otherwise (<ref>) holds easily. So assume that γ_r(m)≥ 1 and that r does not divide (f,p-1).

If r does not divide p-1, then γ_r(p^ℓ-1) = γ_r(ℓ). Now, if γ_r(m)≤γ_r(ℓ), then by the same argument as above (<ref>) holds. If, instead, γ_r(m)≥γ_r(ℓ), then the RHS is γ_r(C) + γ_r(ℓ) = γ_r(C) + γ_r(p^ℓ-1), and γ_r(p^ℓ-1) appears in the minimum in the LHS, hence (<ref>) holds.

Therefore, in order to conclude the proof, it is sufficient to show that, if γ_r(m)≥ 1 and r does not divide (f,p-1), then r does not divide p-1. Assume the contrary. We have r| m| (p^f-1)/(p-1), hence r| (p^f-1)/(p-1) - (p-1) = 2+p^2+⋯ + p^f-1. But r divides also p^2-1; hence r divides 2+p^2+⋯ + p^f-1- (p^2-1) = 3+p^3+⋯ +p^f-1. Going on in this way, we see that r divides f, hence it divides (f,p-1), which is a contradiction. This concludes the proof.




The previous lemma reduces the problem to elementary number theory.
We need a few more lemmas. 



Let r be a prime, and assume γ_r(p-1)≥ 1 and  r ∤ j. Then γ_r(p^j-1)=γ_r(p-1).


Note that (p^j-1)/(p-1) = 1+p+⋯ + p^j-1≡ j ≢0 r.




Let r be a prime and assume i≥ 1 and (r,i)≠ (2,1). If γ_r(p-1)=i, then γ_r(p^r-1)=i+1.



Assume p-1=ar^i, with (a,r)=1, so p≡ ar^i +1 r^i+2. Then p^r ≡ (ar^i+1)^r ≡ a^rr^ir + rar^i + 1 r^i+2. If (r,i)≠ (2,1), then this is ≡ ar^i+1 + 1r^i+2, whence the statement holds.


Note that for (r,i)= (2,1) <Ref> does not hold. Indeed, if γ_2(p-1)=1, then γ_2(p^2-1)≥ 3.



Let r be an odd prime, let i≥ 1 and assume γ_r(p-1)≥ 1. Then γ_r((p^r^i-1)/(p-1))=i. In particular, γ_r((q-1)/(p-1))=γ_r(f).



By <Ref>, γ_r(p^r-1) = γ_r(p-1)+1, hence the first assertion of the statement holds for i=1; then use induction. The last assertion (“In particular...”) follows from this and Lemma <ref>.

The case r=2 is different.



Let i≥ 1 and assume γ_2(p+1) = j, with j≥ 1. Then γ_2((p^2^i-1)/(p-1))=i+j-1. In particular, γ_2((q-1)/(p-1))=γ_2(f)+j-1.



By induction on i. The case i=1 is the hypothesis. For i≥ 2 write p^2^i - 1 = (p^2^i-1 +1)(p^2^i-1 -1). We have p^2^i-1+1 ≡ 2  4 (since 2^i-1 is even), hence γ_2(p^2^i-1)= γ_2(p^2^i-1-1) + 1, whence  the statement follows by induction and <Ref>.



We are now ready to prove <Ref>.

 We need to show that if G is not semiregular on V{0}, then α(G)≥ g(q) and δ(V⋊ G)≥ h(q),  where  g and h are defined in (<ref>) and (<ref>). 
	
Assume first there exists ℓ| f, ℓ < f/2, such that A∩ z^ℓ H≠∅.  By <Ref>,
    
    α(G)> ((q-1)/(p^ℓ-1),t)/tf≥1/(p^ℓ-1,t)f > 1/fp^ℓ.

(In the second inequality we used that (a,bc) ≤ (a,b)(a,c).) 
For ℓ≤ f/3 we have fp^ℓ≪ q^1/3, hence this case is done.

Assume now that f is even and A⊆ z^f/2H. We will in fact prove the desired bound for every q. We start with the bound to α(G); the bound to δ(V⋊ G) will follow easily at the end.


Write (t,p^f/2-1) = (p^f/2-1)/B. Then

    m|p^f-1/t| B(p^f/2+1).

Let r_1, …, r_b denote the distinct prime divisors of (f,p-1) (possibly b=0). By Lemma <ref>, for every i=1,…, b, one of the following holds:

    
  * γ^i(m) ≤γ^i(f/2).
    
  * γ^i(p-1) ≤γ^i(C).



Let s be a prime divisor or f. Note that, for every i such that s≠ r_i, by Lemma <ref> we have γ^i(f/s)=γ^i(f). In particular, since m|(p^f-1)/(p-1),  certainly γ^i(m) ≤γ^i(f) = γ^i(f/s). If s is odd then by assumption A∩ z^f/sH=∅. We deduce from Lemma <ref> that

    
  (a) For any odd prime s dividing f, we have that s|(p-1).


Let now i∈{1, …, s} be such that r_i is odd (if it exists). By the same reasoning as above (with s=r_i), since A∩ z^f/r_iH=∅, by Lemma <ref> we must have γ^i(m) > γ^i(f/r_i) and γ^i(p-1) > γ^i(C).


Moreover, by Lemma <ref>, γ^i(f/r_i) = γ^i(f)-1. Recall, now, that (1) or (2) holds. But (2) cannot hold, because it would contradict the final inequality of the previous paragraph; so (1) holds. We have, therefore, γ^i(f/r_i) < γ^i(m) ≤γ^i(f/2) = γ^i(f/r_i) + 1 = γ^i(f)=γ^i(f) (the last equality follows from  <Ref>), so it must be γ^i(m) = γ^i(f)=γ^i(f). 
We summarize this:


  (b) For any i such that r_i is odd, γ^i(m) =γ^i(f)= γ^i(f).


Then, we claim that


    
  (c) Either p is odd, or f≡ 2  4.

Indeed, assume, by contradiction, that p is even and f≡ 0  4. Then, for every i, r_i is odd
and γ^i(f/2) = γ^i(f/4)=γ^i(f), hence A∩ z^f/2H≠∅ if and only if A∩ z^f/4H≠∅, which contradicts our assumption. This proves (c).










Now, by <Ref> we have

    α(G) = (t,p^f/2+1)/tf + 1/tf≥1/f(t,p^f/2-1) +1/tf= B/f(p^f/2-1) +1/tf.

By (a) and (b), we have f/2^γ_2(f)| m, so by <Ref> 

    tf |  2^γ_2(f)(p^f-1).

By (<ref>), f/2^γ_2(f)| m| B(p^f/2+1), and  for i such that r_i is odd, r_i ∤ p^f/2+1, so that 

    f| 2^γ_2(f)m | 2^γ_2(f)B.
.
If γ_2(f)=1, then by (<ref>), (<ref>) and (<ref>) we get 

    α(G)≥B/f(p^f/2-1) +1/tf≥1/2(p^f/2-1) + 1/2(p^f-1)= h(q),

as wanted.


From now, therefore, we assume N:=γ_2(f) ≥ 2. By (c), we have p odd. If t is odd, then γ_2(B) = γ_2(p^f/2-1). 
By Lemma <ref>, γ_2(p^f/2-1)≥ N+j-1 ≥ N, where j:=γ_2(p+1)≥ 1.
Hence γ_2(B)≥γ_2(f), so by (<ref>) f| B and by (<ref>)

    α(G) > B/f(p^f/2-1)≥1/p^f/2-1

and we are done. Assume now that N≥ 2 and t is even. If γ_2(t)=γ_2(p^f-1), then m|p^f-1/t is odd, so γ_2(m)=0≤γ_2(f/4), therefore  A∩ z^f/4H≠∅, contradiction. 

Assume finally that N≥ 2, t is even and γ_2(t)<γ_2(p^f-1). In particular, γ_2(t) ≤max{γ_2(p^f/2-1), γ_2(p^f/2+1)}. Also, clearly min{γ_2(p^f/2-1), γ_2(p^f/2+1)}=1. It is easy, then, to deduce

    α(G) = (t,p^f/2+1)/tf +1/tf= 2/f(t,p^f/2-1) +1/tf= 2B/f(p^f/2-1) +1/tf.

Now, if r_i is odd,  by the validity of (1) or (2) we deduce that either γ^i(m)≤γ^i(f/4) or γ^i(p-1)≤γ^i(C). Since A∩ z^f/4H=∅, it follows from <Ref> that (2) does not hold,
and so γ_2(m)≤γ_2(f/2), and also γ_2(m)> γ_2(f/4). 
It follows  γ_2(m) = γ_2(f/2) = N+j-2≥ N-1, so by <Ref> f| 2m, and by (<ref>) ft| 2(p^f-1). Since by (<ref>) m| B(p^f/2+1), we deduce γ_2(B) ≥ N+ j - 3 ≥ N-2, and so by (<ref>) and (<ref>) we get

    α(G) = 2B/f(p^f/2-1)  + 1/tf≥1/2(p^f/2-1) + 1/2(p^f-1) = h(q).

The lower bound to α(G) is proved. For the lower bound to δ(V⋊ G), note that every element of A fixes exactly p^f/2 vectors,
and so by <Ref> and some reorganization we get

    δ(V⋊ G) = q^1/2-1/q(α(G) + 1/|G|q^1/2).

From inspection of this proof, we have either |G|≤ 2(q-1), or α(G)≥ 1/(q^1/2-1), in which case we are done. Therefore we may assume |G|≤ 2(q-1), and using α(G)≥ h(q), we get δ(V⋊ G)≥ g(q) by some reorganization.










Let q=p^f with f even and G=_1(q)⋊σ, where σ is the q^1/2-th power map. By  <Ref>, the proportion of elements in G_1(q) fixing a nonzero vector is 

    (q^1/2+1,t)/2t = 1/2(q^1/2-1)

(with t=q-1). Counting the identity, we have

    α(G) = 1/2(q^1/2-1) + 1/2(q-1) = h(q)

and so equality can be attained in <Ref>(3). What is more, by the same calculation as at the end of the previous proof, we get δ(V⋊ G)=g(q), and so equality can be attained in <Ref>(2).











§ _2(Q)
 

In this section we prove <Ref>. For convenience, we replace q^d/2 by q in the notation.  The cases to consider are when G normalizes _2(5), Q_8, or _2(q_0) with q a power of q_0≥ 4. We consider each case in turn. In the first two cases, in some sense we will argue by reducing the problem to _1(q), and so will use several times <Ref>, which we proved in <Ref>. 








 §.§ _2(5)
 Assume q≡± 1 10
and let L:=_2(5),  L≤ G ≤__2(q)(L)=LZ⋊τ,
 where Z=_q^×, q=p^f, p prime, and τ is the p-th power map. Recall that f(n) was defined in (<ref>).


    For q sufficiently large we have α(G) ≥ 1/(60(q-1)) and δ(V⋊ G) ≥ f(q^2). If moreover G is not semiregular on V{0}, then α(G)≥ 31/(60(q-1)) and δ(V⋊ G) > 31/(60(q-1))· (1-1/q).



In this proof, whenever we write “semiregular”, we mean “semiregular on V{0}”. Set A:=G∩ (Z τ), and note that |G:A|≤ 60.

Assume first that G is semiregular. Then A is semiregular and so |A|≤ q-1, from which

    α(G, V)≥α(A,V)/60≥1/60(q-1).

Note also that the set of derangements of G is V{0}, and so

    δ(V⋊ G,V)=q^2-1/|G|q^2≥q^2-1/60(q-1)q^2 = f(q^2),

as wanted.


Assume now that G is not semiregular; we will show that α(G,V)≥ 31/(60(q-1)), and we will deduce the bound to δ(V⋊ G,V) at the end. If A is not semiregular, by <Ref> we have α(A,V)≥ h(q) > 1/2q^1/2, 
and so

    α(G, V)≥α(A,V)/60 > 1/120q^1/2

and we are done. Assume then A is semiregular, so |A|≤ q-1. Assume first that H:=G∩_2(q) is semiregular, and let 1≠ g=xσ∈ G fix a nonzero vector, where x∈_2(q) and σ is a power of τ. Since H is semiregular, |g|=|σ|, and so by <cit.> there exists y∈_2(q) such that g^y=zσ, where z∈ Z. Replacing G by G^y, we are reduced to the case where A is not semiregular, and so this case is done.

Assume finally that A is semiregular and H is not semiregular.  Note that in L there are 30 elements of order 4, 20 elements of order 3, 20 elements of order 6, 24 elements of order 5, 24 elements of order 10, and 2 central elements. 

Let H=LZ' where Z'≤ Z. If 3∤ q, then a nontrivial element of H with eigenvalue 1 is of the form gz, where g∈ L, 1≠ z∈ Z', and g has eigenvalue z^-1. It is easy to see that α(G,V)≥ 31/(60(q-1)) (attained when q≡ 1 mod 4, q≡ -1 mod 3, q≡ -1 mod 5, and Z'=Z).
Assume finally that 3| q, so element of order 3 have eigenvalue 1. Since q≡± 1  5, we also have  q≡ 1  8.
In particular, we may assume that 4∤ |Z'|, for otherwise we have α(G,V)≥ 51/(60(q-1)). We can also assume that |G|=60(q-1) and |A|=q-1, otherwise α(G,V)≥ 21/(30(q-1)). Now, take g∈ L of order 4 such that τ normalizes g; up to conjugation we may take it that J:=A,g acts diagonally on V.  
Let W be the space generated by the first basis vector, and let J be the group induced by J on W; since 4∤ |Z'|, note that |J| = |J|.
If J is not semiregular on W{0} then by <Ref> α(J,W)=α(J, W)>1/(2q^1/2) and so α(G,V)≥α(J,W)/30>1/(60q^1/2) and we are done.
 Therefore we assume that J is semiregular  on W{0}, from which |J|≤ q-1 and so |G|≤ 30(q-1), contradicting our assumption. This proves the lower bound to α(G,V). For the lower bound to δ(V⋊ G,V), note that every bound to α(G,V) in the proof is given by counting elements of H=G∩_2(q) (or otherwise α(G,V)≫ 1/q^1/2). In particular, every such nontrivial element fixes q vectors, and so the bound follows easily from <Ref>.



	
	Assume q≡ -160 and let G=ZL where Z=_q^×. Then G acts semiregularly on V{0} and so α(G)=1/(60(q-1)) and δ(V⋊ G)=(q+1)/(60q^2)=f(q^2). In particular, the bounds in <Ref>(2) (and <Ref>(2)) are sharp.




 §.§ Q_8
 Let q be odd and Q_8≤ G≤__2(q)(Q_8)=KZ⋊τ,
where K is a double cover of S_4, Z=_q^×, q=p^f, p prime, and τ is the p-th power map. We set Ŝ_̂4̂:=_2(3) and we denote by S_4 the other double cover of S_4, so K∈{Ŝ_̂4̂, S_4}.


    For q sufficiently large we have α(G) ≥ 1/(24(q-1)). If moreover G is not semiregular on V{0}, then α(G)≥ 13/(24(q-1)) and δ(V⋊ G)≥ 13/(24(q-1))· (1-1/q).



As in the proof of <Ref>, we set A:=G∩ Zτ and when we write “semiregular” we mean “semiregular on V{0}”. 

Since |G:A|≤ 24, if G is semiregular we have

    α(G,V)≥α(A,V)/24≥1/24(q-1).

Assume then G is not semiregular; we want to show α(G,V)≥ 13/(24(q-1)), and we will deduce the bound to δ(V⋊ G, V) at the end of the proof. Setting H:=G∩_2(q), exactly as in the proof of <Ref>, we reduce to the case where A is semiregular and H is not semiregular. We assume (as we may) that if p≡± 3  8 then K=Ŝ_̂4̂.

Write G=N,g_1z_1,g_2z_2σ, where N:=G∩ K, g_1,g_2∈ K, z_1,z_2∈ Z, σ is a power of τ, and H=N,g_1z_1.
If |N|=16, or 48, or 24 with K= Ŝ_̂4̂, define β:=|N|. If |N|=8,  define β:=24. Assume finally |N|=24 with K=S_4. If q≡ -1 8, or q≡ 1 8 and |z_1|_2=8 and g_1∉N, define β:=48; in the other cases, define β:=24.

We will now show that either α(G,V)≫ 1/q^1/2 (in which case the proof is complete) or |G|≤β(q-1)/2. Note that this is immediate if β=48, so for now we may assume β<48, and in particular |N|<48.


Let J:=-1, g_1z_1,g_2z_2σ. If we show that |J|≤ q-1, then |G|≤ |N|(q-1)/2, which is enough in all cases since β≥ |N|. We will accomplish this stronger bound in some cases.

If we may take g_1=g_2=1 then J≤ A has order at most q-1 as desired, so assume this is not the case. Since g_1 and g_2 normalize N,
if |N|=16 then we may take g_1=g_2=1 and so these cases are excluded.
If |N|=24, then  we may take g_1 or g_2 is equal to 1, and the other, call it g, is of 2-power order. We may assume g∉N as explained in this paragraph.

Since we are assuming β<48, we have either K=Ŝ_̂4̂ or q≡ 1 8. In particular, g is diagonalizable over _q, and we may take it diagonal, of order 2 if K=Ŝ_̂4̂, and of order 8 if K=S_4.
Assume first g=g_2. 
Let W be the space generated by the first basis vector and let J be the group induced by J on W; note |J|=|J|.  
If J is semiregular then |J|≤ q-1 as desired. If J is not semiregular, then  by <Ref> we have α(J,V)> 1/(2q^1/2), and so α(G,V)≥α(J,V)/24> 1/(48q^1/2) and we are done. 
Assume now g=g_1 and K=S_4. Then p≠ 3 and since β<48, we have q≡ 1 8 and |z_1|_2≠ 8=|g|.
This easily implies that |J|=|J|,
and we reduce to |J|≤ q-1 in the same way as above.
Assume now g=g_1 and  K=Ŝ_̂4̂, so |g|=2. Assume g centralizes the space W generated by the first basis vector. Set J_1:=-1,z_1, z_2σ, and note that |J|=|J_1|,
and so either |J|≤ q-1, as desired, or J_1 is not semiregular on W. But note that each element of J_1 fixing a nonzero vector of W gives rise 
to an element of J fixing a nonzero vector of V, and so α(J,V)> 1/(2q^1/2) and we are done. 


Assume finally |N|=8. If g_1∈ N or g_2∈ N, then |G|≤ 12(q-1) as desired.
 If g_1 and g_2 are not in N, then we may take |g_1|=3 
 and g_2 of 2-power order. It follows that K=Ŝ_̂4̂ or q≡ 1 8. (Indeed, if K=S_4 and q≡ -1 8, we have q=p^f with f odd,
 in which case by choosing g_2∈_2(p), we have that g_2z_2' is a power of g_2z_2σ for some z_2'∈ Z, which is impossible.)
 In particular, we can pass to a subgroup B of index 3; the same argument as in the previous paragraph then gives |B| ≤ 4(q-1) and so |G|≤ 12(q-1), as desired.
Therefore we may assume |G|≤β(q-1)/2 in all cases, as claimed.





Recall we are assuming H is not semiregular; let 1≠ y∈ H with eigenvalue 1. Assume y=nxz, where n∈ N, x∈ K, z∈ Z, and xz a power of g_1z_1 not belonging to N{1}. 
Let c:=nx, so y=cz, and note that |c|=2,3,4,6 or 8. If |c|=2 then x=1 and y=n.
If |c|= 6 or 8 then we replace y by y^2 and assume |c|=3 or 4. Now note that, in all cases with |c|=2,3 or 4, if c'∈ Nx is such that |c'|=|c|, then c'z has eigenvalue 1.
Moreover, if |c|=3 and xz≠ 1, then c^2 has eigenvalue 1, and the number of elements of order 3 in Nxz is equal to the number of elements of order 3 in N(xz)^2.
There is one case where we need to improve slightly the counting.
If K=S_4, |N|=24, |z_1|_2=8 and g_1∉ N, then we can  take |g_1|=8, and up to replacing z_1 by -z_1, a power g_1z_1 of the form g_1z_1' has eigenvalue 1.
Furthermore, for every _2(q)-conjugate a of g_1 in Ng_1 (there are 6 such conjugates),
az'_1 has eigenvalue 1, and finally we find other 6 nontrivial elements with eigenvalue 1 in N(g_1z'_1)^2 = Nz_1'^2. We counted 12 elements, which is also the number of elements of order 4 in K N. 



Let now C be a coset of N in K normalizing N and let t∈{3,4}. If N=Q_8, C⊆ P N where P∈Syl_3(K), and t=3, we let F_C(t)=8 (namely, the number of elements of P of order 3). 
If p≠ 3, |N|=48 or |N|=24, and t=3, we let F_C(t)=16 (namely, twice the number of elements of K of order 3).   
In all other cases, we let F_C(t) be the number of elements that are either in C and have order t, or are in N(N) and have order 2. We finally let f_C(t):=(F_C(t)+1)/β.


It follows from the above discussion that there exists a coset C of N in K normalizing N
and t∈{3,4}, such that if |N|=24, K=S_4, |z_1|_2=8 and |g_1|∉N, then C=K N and t=4;
if |N|=24 and q≡ -1 8 (so p≠ 3), then t=3; 
and such that moreover f(t)>1/β and 

    α(G,V)≥F_C(t)/|G| + 1/|G|≥2f_C(t)/(q-1).

(In the second inequality we used |G|≤β(q-1)/2. )
It is straightforward to check that if f(t)>1/β then f(t)≥ 13/48 (attained for example by K=N=Ŝ_̂4̂, q≡ 3 8 and q≡ 2 3, and t=3 or 4). 

This gives α(G,V)≥ 13/(24(q-1)) as required. The lower bound to δ(V⋊ G,V) follows as at the end of the proof of <Ref>.











    




 §.§ _2(q_0)
 


We begin by recording  a simple estimate for the proportion of elements in a coset of _2(q) having a given eigenvalue in _q. 



    Let g∈_2(q) and let λ∈_q^×. The proportion of elements of  _2(q)g having eigenvalue λ is at least 1/q.



    If λ^2≠(g), the proportion of (semisimple) elements of _2(q)g having eigenvalue λ is 1/(q-1). If λ^2= (g), the proportion of λ-potent elements is 1/q.


We turn then to the general case. Let q=q_0^r with q_0≥ 4, 
r≥ 1,  and _2(q_0) ≤ G ≤__2(q)(_2(q_0))=_2(q_0)Z⋊τ,
where Z=_q^×, q=p^f, p prime, and τ is the p-th power map. This is the only case where the bound for δ(V⋊ G) will require somewhat more work than the bound for α(G). 





    We have α(G)> 3/(4q) and δ(V⋊ G)> 9/(16q).


 
	Let H:=G∩ (_2(q_0)⋊τ), so |G:H| ≤ (q-1)/(q_0-1). 
	Let W=_q_0^2; we now count the elements of H fixing a vector in W{0}. Assume that H projects onto (_q/_r), let N:=H∩_2(q_0), 
	and consider any coset Ng with g∈ H. Assume that g projects onto (_q/_r^i), and set s(i):=|_q_0∩_r^i|. By Shintani descent (see <cit.>)
	 and <Ref>, the proportion of elements of Ng that fix a nonzero vector of W is at least 1/s(i)≥ 1/q_0. Therefore, α(H,W)≥ 1/q_0.
	Since |G:H|≤ (q-1)/(q_0-1), we have α(G,V) ≥ (q_0-1)/(q_0(q-1)) ≥ 3/(4(q-1)) (since q_0≥ 4), as desired.
	
	Next we prove the lower bound to δ(V⋊ G,V). Assume q=r^m. Note that in a coset Ng where g∈ H projects onto (_q/_r^i), each element fixing a nonzero vector fixes at least r^i vectors. Since in such coset we produced at least |N|/s(i) elements fixing a nonzero vector, we deduce
	
    η(G,V)≤1/|G|(∑_i| mφ(m/i)|N|/s(i) r^i+ |G|-∑_i| mφ(m/i)|N|/s(i)),

		where φ is Euler's totient function,
	and so by <Ref>
	
    δ(V⋊ G,V)≥|N|/|G|∑_i| mφ(m/i)(r^i-1)/s(i)r^i≥q_0-1/(q-1)m∑_i| mφ(m/i)(r^i-1)/s(i)r^i,

	where in the last inequality we used |G|≤ (q-1)m|N|/(q_0-1). 	  Using ∑_i| mφ(m/i)=m, (r^i-1)/r^i≥ (r-1)/r, and s(i)≤ q_0, we see that the right-hand side of (<ref>) is at least (q_0-1)(r-1)/(q_0(q-1)r). In particular, for r>2 (and q_0≥ 4) this is at least 9/(16(q-1)), which is enough.
	Assume then r=2. Using that s(1)=2, that for i>1 we have (2^i-1)/2^i≥ 3/4 and s(i)≤ q_0,
	 we get
	
    1/m∑_i| mφ(m/i)(2^i-1)/s(i)2^i   ≥φ(m)/4m + 3(m-φ(m))/4mq_0
       = 3/4q_0+ φ(m)/m(1/4 - 3/4q_0) >3/4q_0.

	In particular, we get from (<ref>) that δ(V⋊ G,V)> 3(q_0-1)/(4q_0(q-1)) ≥ 9/(16(q-1)) also in this case.






Let G≤_2(q^d/2) be such that G≤_d(q) is irreducible and primitive. Let H:=G∩_2(q^d/2) and L:=F^*(H). By Clifford's theorem, V is homogeneous as an _q^d/2L-module. If a component is one-dimensional, we have L≤(H) and _H(L)=H. But (L)=_H(L), from which H=L consists of scalars, and since |G:H|≤ d/2, G cannot be irreducible, false. 
Therefore, L is irreducible on V, and so it is absolutely irreducible.
If the layer E of L is nontrivial, then E=_2(5) or E=_2(q_0) with q_0≥ 4. Since G normalizes E, these cases have been handled in <Ref>. If E=1, then L=ZQ_8 with Z≤_q^d/2^×. Then in fact G normalizes Q_8,
and so has been handled in <Ref>.






§ EXTRASPECIAL GROUPS


<Ref> for extraspecial groups 
is immediate.



    Let G≤_d(q) be extraspecial of order r^2s+1 and absolutely irreducible. Then α(G)>|_2s(r)|/q^o(d) as |G|→∞.



    We have d=r^s, and we simply use that the identity has eigenvalue 1; then 
    
    α(G)/|_2s(r)|>1/|G||_2s(r)| > 1/r^2s+1r^4s^2 > 1/2^o(d)≥1/q^o(d)

as d→∞.




    The assumption that G is sufficiently large is convenient here. For example, if G=2_-^11 and q=3 then |_10^-(2)|/(α(G)|V|^1/2) is larger than 2 millions. (Note that the nontrivial elements of 2_±^2s+1 with eigenvalue 1 are precisely the noncentral involutions, whose number is seen to be 4^s± 2^s-2.) This says that counting elements of G with eigenvalue 1 is far from enough to handle all subgroups of N:=__d(3)(G)=G._10^-(2).
    
    The argument for subgroups of N can be amended with some more care. However, this
    issue would add (seemingly technical) complications to the arguments of <Ref>, where we were able to essentially ignore all extraspecial and quasisimple groups of small order and reduce the problem to the generalized Fitting subgroup.








§ QUASISIMPLE GROUPS


In this section, d≥ 3, V≅_q^d,  G is a quasisimple group with S:=G/(G), and G≤_d(q) is absolutely irreducible. 




 §.§ Alternating groups and groups of Lie type in non-defining characteristic
  We first isolate the case of the fully deleted permutation module for alternating groups.



Let G=A_m with m≥ 5, and let V denote the fully deleted permutation module. Then, α(G,V)≥ 1- 2(1+log(m))/m.



Let g∈ G. It is easy to see that if g has at least three cycles, then g fixes a nonzero vector of V. Let us then count these elements.

The proportion of elements of G with at most two cycles is

    2m odd/m  + 2m even(∑_1≤ i<m/21/i(m-i) + 2/m^2),

where - denotes the indicator function.
 Note that 

    ∑_1≤ i<m/21/i(m-i) + 2/m^2   = 1/m∑_1≤ i<m/2(1/i + 1/m-i) + 2/m^2
       = 1/m∑_1≤ i≤ m-11/i
       ≤1+log(m)/m,

where in the last inequality we used a standard upper bound for the partial sum of the harmonic series. The lemma follows then from this estimate and (<ref>).


Assume in the following lemma that either S=A_m with m≥ 5, or S is a group of Lie type of (untwisted) Lie rank r, defined over _s, with (q,s)=1. In these cases, as we shall recall in the proof, we have that d→∞ as |S|→∞.




We have α(G,V) > |(S)|/q^o(d) as |S|→∞.



 Assume first S=A_m. By <Ref>, we may assume that V is not the fully deleted permutation module. Then <cit.> gives d ≥ (m^2-5m+2)/2. Therefore, for m sufficiently large, counting only the identity in G, we get
 
    α(G,V)≥1/m! > |(S)|/2^o(d)

as wanted.

Assume now S is of Lie type; note that |G|≤ s^O(r^2) and |(S)|≪ rlog(s).
By <cit.>, we see that d≥ s^cr for some positive absolute constant c, so

    α(G,V)≥1/|G|≥|(S)|/2^o(d)

also in this case.







 §.§ Groups of Lie type in defining characteristic
 

Assume now S is a group of Lie type of untwisted rank r defined over _s, and assume (q,r)≠ 1. Assume q is a power of the prime p. 

If |S| is sufficiently large, then G=X_σ /Z, where X is a simple linear algebraic group of simply connected type over K:=_q, σ is a Steinberg endomorphism of X, and Z is a central subgroup of X_σ:={x∈ X | x^σ=x} (see e.g. <cit.>). 

The irreducible representations of X_σ over K are restriction of representations of X, and are described by the theory of highest weights. We refer to <cit.> or <cit.> for the basic aspects of this theory (which, for our purposes, are sufficient).



Denote by u(-) be the proportion of p-elements. 




u(X_σ)=u(G)/|Z|.


 Since (|Z|,p)=1, each p-element of G lifts to a unique p-element of X_σ.




Next, we recall a result of Steinberg (see <cit.>). 
We define the level s_0 of a Steinberg endomorphism σ of X as the absolute value of the eigenvalues of σ on Γ⊗_𝐙𝐂, where Γ is the character group; see <cit.>. If X_σ is a Suzuki or Ree group then s_0 is not an integer and s_0^2 is an integer. In all other cases, s_0 is an integer.

This also gives an interpretation of the sentence “S is defined over _s”, appearing in the first paragraph of this section – this holds if and only if either s_0=s, or X_σ is a Suzuki or Ree group and s=s_0^2. 

 (Steinberg)

Assume that X has rank r, and let σ be a Steinberg endomorphism of X of level s_0. Then, the proportion of regular unipotent elements of X_σ is 1/s_0^r.






Let λ_1, …, λ_r be the fundamental dominant weights of X, corresponding to the simple roots α_1, …, α_r. A character of the form ∑_i=1^r c_iλ_i, with c_i∈𝐙, is called p-restricted if 0≤ c_i≤ p-1 for every i. An irreducible KX-representation V=V(λ) is called p-restricted if λ is p-restricted (here λ denotes the highest dominant weight of V).

If X_σ is a Suzuki or Ree group, then the irreducible KX_σ-modules are the V(λ), where λ = ∑_i=1^r c_i λ_i, 0≤ c_i < s_0^2, and λ is supported on short roots, namely, c_i=0 if α_i is long. Moreover, these s_0^r representations are pairwise non-equivalent (see <cit.>).  In this case we will also say that V is supported on short roots.

We now record a lemma concerning field of definition of p-restricted representations.
 



Let σ be a Steinberg endomorphism of X of level s_0, and let d be the order of the permutation induced by σ on the Dynkin diagram. Let V be an irreducible p-restricted KX_σ-representation, supported on short roots if X_σ is Suzuki or Ree, and assume the minimal field of definition for V is _p^f. Then p^f = s_0 or p^f = s_0^d. 



Write s_0=p^e. Assume first X_σ is not Suzuki or Ree.
By <cit.> (note that “q” in this reference corresponds to “s” here), 
we have f | ed, so we only need to show that f≥ e. Write V=V(λ) where λ= ∑_i c_iλ_i is the highest dominant weight of V, so 0≤ c_i≤ p-1 for every i. As X_σ-modules, we have V(λ) ≅ V(λ)^(f)≅ V(p^fλ). We have p^fλ = ∑_i p^fc_iλ_i, and since V(λ) and V(p^fλ) are X_σ-equivalent, by <cit.>, there must exist c_j with c_jp^f ≥ p^e; so

    p^e ≤ c_jp^f ≤ (p-1)p^f,
 
from which f≥ e, as desired. If X_σ is Suzuki or Ree, then <cit.> and the same calculation as above gives f=2e.





The following is well-known.



    Assume that V has weight zero. Then every element of X has eigenvalue 1.



	Let T be a maximal torus of V, so by assumption _V(T)≠ 0. Now let g∈ X, and write g=su, with s semisimple, u unipotent, and su=us. Up to conjugation, we may assume s∈ T. Since u is a unipotent element normalizing W:=_V(s), we have 0≠_W(u)≤_V(g), which concludes the proof.


I am grateful to Bob Guralnick for suggesting the proof of the following lemma. See <cit.> for similar results for algebraic groups and for semisimple elements, which however are not sufficient here. 


    Let σ be a Steinberg endomorphism of X of level s_0, and let V be an irreducible KX-representation. Assume that there exists a weight χ such that χσ∈𝐙χ. Then, α(X_σ, V)≥ 1/s_0 + O_X,χ(s_0^-3/2).



Note that {(x-1)=0} is a subvariety of X of codimension at most 1. If it is equal to X then we are clearly done; assume then this is not the case. We will show that there exists a σ-stable irreducible component Y of {(x-1)=0} of codimension 1 in X. The Lang–Weyl estimates (which hold for every σ; see <cit.> and the references therein for the case of Suzuki or Ree groups) will then imply |Y_σ|/|X_σ| = s_0^-1 + O(s_0^-3/2), where the implied constant depends on Y. We will see that Y depends on X and χ, so the proof will be concluded.

Let T be a σ-stable maximal torus, such that χ T →_m, and let S:=(χ). By <Ref>, χ≠ 0 and so S is a closed subgroup of T of codimension 1. Note that, since χσ∈𝐙χ, S is σ-stable. Denote by ℛ the set of regular semisimple elements of X, which is σ-stable. It is known that ℛ is open (and dense) in X.  

    Assume first that U:=S^∘∩ℛ≠∅, so U is open and dense in S^∘. Now consider the morphism f X× S^∘→ X given by f(g,s) = s^g. Then Im(f) is σ-stable, and consists of elements having eigenvalue 1. Next, note that there is a dense subset D of Im(f)  consisting of elements whose fiber has dimension (T)=(S)+1. (For example, we can take  D=ℛ∩Im(f), and we use that T has finite index in _X(T).)
     In particular, (Im(f))=(X)-1.
  Setting Y:=Im(f), and noting that Y depends on X and χ, proves the lemma in this case.

    Assume finally that S^∘∩ℛ=∅. Then L:=_X(S^∘) is a reductive group which is not a torus.
    Then, there exists a regular unipotent element u∈ L_0:= [L^∘,L^∘]. 
    Consider then the morphism f X× S^∘→ X given by f(g,s) = (su)^g. As in the previous case, we see that Im(f) has codimension 1 in X.
    (In this case, we can choose D⊆Im(f) as the set of elements conjugate to su where s∈ S^∘ is such that _X(s)=L; we recall that L has finite index in _X(L), see <cit.>.)
     In particular, letting Y be the closure of the set of elements conjugate to su' where s∈ S^∘ and u'∈ L_0 unipotent, we have that Y⊇Im(f) has codimension 1, is σ-stable, and depends only on X and χ, so we are done.




 §.§ Natural module for classical groups
 

In this subsection V is the natural module for a classical group G. 
For orthogonal groups we assume n even, since for n odd every element of _n(q) has eigenvalue 1.

For G=_n(s), _n(s), _2n(s), ^±_2n(s), Neumann–Praeger <cit.> gave estimates for the proportion of elements of G having a given eigenvalue, and showed that its limit as n→∞ with s fixed exists (and, for example, in non-orthogonal groups it is  1/s+O(1/s^2)). See also <cit.> for recent related results.


We prove an easy result that holds in each coset of [G,G] in G. Our result and proof are similar to <cit.>, and in particular are an application of the inequality

    | ⋃_g∈ G H^g | ≤|G|/|_G(H):H|

for H≤ G. In <cit.>, in fact, the authors are interested in semisimple elements with eigenvalue 1, and  nontrivial estimates for the proportion of semisimple elements of G are required. Here we do not need to focus on semisimple elements, which makes the analysis easier and in some cases allows to handle some more value of s (for s≥ 3 the bounds below are meaningful). We give exact bounds (rather than asymptotic), as the proof offers them naturally and they might be useful.



    
        
  * If 
        _n(s) ≤ G≤_n(s) with n≥ 2 then
        
    1 - 1/s-1/s-1≤α(G,V) ≤1/s-1.

        
  * If G=_2n(s) with n≥ 2 then
        
    1 - 1/s-1/s≤α(G,V) ≤1/s-1.
 
        
  * If  _n(s)≤ G≤_n(s) with n≥ 3 then
        
    1 - s/s^2-1/s+1≤α(G,V) ≤s/s^2-1.

        
  * If G=Ω^±_2n(s) with n≥ 4 and s odd then
        
    s(1 - 2s/s^2-1)/s^2-1≤α(G,V) ≤2s/s^2-1.

    





	
All proofs are similar; we first prove the upper bound, and deduce the lower bound. The upper bounds in (1)–(3) are contained in <cit.>. (This is an easy calculation using (<ref>), applied to the centralizer H of a 1-space, singular or nondegenerate; in (1) and (3) the bounds are stated only for _n(s) and _n(s) but the  same proof works for any G as in the statement.)
For the upper bound in (4), note that if an element g of Ω^±_2n(s), s odd, has eigenvalue 1, then it fixes either a singular vector, or it centralizes a nondegenerate 2-space of minus type. (In order to see this, assume that vg=v with v nonsingular. Letting W= v^⊥, since (W) is odd and (g)=1, there exists 0≠ w∈ W with wg=w. If w is singular we are done; otherwise v,w is nondegenerate. If it is of minus type we are done again, and otherwise it contains a singular vector, done for the third and final time.) 
The  contributions of the two subgroups in (<ref>) are, respectively, 1/(s-1) and 1/(2(s+1)); bounding 1/(2(s+1)) < 1/(s+1) and summing the two contributions we get the desired inequality.


Now let us prove the lower bounds. In (1), for n=2 we have α(G,V)≥ 1/s,
so assume n≥ 3. We count elements that centralize a vector v, stabilize a complement and act without eigenvalue 1 there. Each such element acts without eigenvalue 1 on exactly one hyperplane (namely [V,g]), hence there are no repetitions. Using the upper bound that we just proved, the statement follows from an easy calculation.

The bounds in (2), (3) and (4) are proved in the same way. In (2), we count elements that are regular unipotent on a nondegenerate 2-space and act without eigenvalue 1 on the perpendicular complement. (The proportion of regular unipotent elements of _2(s) is 1/s.) In (3) we count elements that fix a nondegenerate vector and act without eigenvalue 1 on the perpendicular complement. In (4) we count elements acting trivially on a nondegenerate 2-space (of any type) and without eigenvalue 1 on the orthogonal complement. 


The previous result is empty for linear and symplectic groups when s=2, and does not address orthogonal groups in even characteristic. (This latter exclusion depends on the fact that the centralizer H of a nonsingular vector is a maximal subgroup, and so (<ref>) is useless.) For these cases, we record estimates that can be extracted from <cit.>.




    
  * For G=_n(2) and _2n(2) we have α(G,V)> 0.5.
    
  * For G=Ω^±_2n(s), s even, n≥ 4, we have α(G,V)> 1/s - 1/s^2 - 1/s^16. 
   





(1) Let us start from G=_n(2). By <cit.> we get that
    
    |1-α(G,V)-G(2,1)|≤ c(2) · 2^-6,

   where G(2,1) and c(2) are defined in that paper. We have c(2)<3.5 by <cit.>, and so the error term is at most 0.06. Moreover, G(2,1) is estimated in <cit.>. Looking at the proof, we see that
   
    log(G(2,1)) = -1 - ∑_k≥ 2(∑_j≥ 2; j| k1/j) 2^-k.

   In order to upper bound log(G(2,1)), we lower bound the sum considering only the term k=2
   and get log(G(2,1))< -1 - 1/8, so G(2,1) < e^-1-1/8 <0.33 and therefore 1-α(G,V) < 0.39. 
The case of _2n(2), as well as (2), are very similar, and we skip the details.




 §.§ <Ref> in defining characteristic



We can now prove <Ref> for quasisimple groups G≤_d(q) in defining characteristic, which is the remaining case. We will do this in two lemmas: <Ref>. In <Ref>, we will prove a slightly stronger bound in most cases. Recall that d≥ 3. 



 We have α(G, V)≫ q^-d/3, and moreover either α(G, V)≫ q|(S)|log(q) q^-d/3, or G and d appear in <Ref>.





Case 1: q≥ s. 
Recall that by Steinberg's twisted tensor product theorem, if V is not p-restricted then

    d≥ d_0^2

where d_0 is the dimension of some p-restricted module. 


Assume first the rank r is at least 100.  We have q|(S)|log(q)≤ q^4.
By <Ref>, the proportion of unipotent elements in G is at least 1/s_0^r ≥ 1/q^r, where s_0=s, or G is Suzuki or Ree and s_0=s^1/2. Since unipotent elements have eigenvalue 1, we are done if d/3-4≥ r, which is to say, d≥ 3r+12. Assume then this is not the case; by <cit.>, V is (a Frobenius twist or the dual of) the natural module. Note that α(G,V) is unchanged by taking duals or Frobenius twists,
so we may assume V is the natural module. Then from <Ref>, α(G,V)≫ 1/s ≫ 1/q and we are done.

Assume then r< 100, so we may assume q is large and therefore q|(S)|log(q) ≤ q^1.1. In particular, counting regular unipotent elements we are done if d/3-1.1≥ r, which is to say,

    d ≥ 3r+3.3.

For the cases in <Ref>, we are done provided

    d ≥ 3r.



Assume first that G is exceptional. If G= G_2(s)
and d≥ 10, we are done by <Ref>. Otherwise, by <cit.> and (<ref>),
if G= G_2(s) then d=6 or 7. If d=7 then s is odd and the representation has weight zero (see <cit.>, or just note that G_2(s) embeds into _7(s)), so we are done by <Ref>. Assume then s is even, so d=6. The case s=q appears in <Ref>, and <Ref> holds. In the case s<q, by <Ref> we have α(G,V) ≫ 1/s ≫ 1/q^2-1.1 and we are done.

Assume now G is exceptional and not G_2(s). If G is not ^3D_4(s), ^2B_2(s), then <Ref> follows from <cit.>. If G=^2B_2(s) and d=4, note that q≥ s=s_0^2 and so 1/s_0^2 > q^-4/3, which proves the first bound. Moreover this case appears in  <Ref>.
If G=^2B_2(s) and d>4 then d≥ 16 
and we are done. If G= ^3D_4(s), then by <cit.> either V≅ V^τ_0 and d≥ 24, so <Ref> holds, or q≥ s^3 and d≥ 8,
which is also enough.

Assume now G is classical, and denote by n the dimension of the natural module. We start from the case X_σ=A_r(s) or ^2A_r(s), so n=r+1. Note that in this case <Ref> is equivalent to

    d>3n.

Assume V is (a Frobenius twist or the dual of) the natural module, the alternating square, or the symmetric square. Note that for ^2A_r(s) we have q≥ s^2, unless r=3 and V is the alternating square, in which case q≥ s.
 We now claim that α(G,V)≫_r 1/s, and one readily checks that this is enough. (Note that some cases appear <Ref>, namely the ones in the third, fourth, sixth and seventh lines, and the case d=3 for A_1(s).) 
The case of the natural module follows from <Ref>. For the symmetric square, we simply count elements with eigenvalue 1 on the natural module. For the alternating square, we count elements acting as diag(λ, λ^-1) on a 2-space (nondegenerate for unitary groups) and fixing no 1-space on a complement, and the claim is proved. (For A_r(s) we could also apply <Ref>.)


Assume then V is not among these, so d≥ n^2/2 by <cit.>. Then, <Ref> holds provided n>6. Assume then n≤ 6. Since we are excluding natural module, alternating square and symmetric square, we see by <cit.> and (<ref>) 
that in all the remaining cases either d>3n, or n=2 and d=4,5,6,
or n=3 and d=7,8.
For n=3 and d=7,8, the highest dominant weight is stable under the graph automorphism, so by <Ref> α(G,V)≫ 1/s and this is enough. For n=2 and d=5, every element of G has eigenvalue 1 and we are done.
The cases n=2 and d=4,6 appear in <Ref> and we simply count unipotent elements.


The other cases are similar, and easier; let us handle for example X_σ = C_r(q), so n=2r. If d ≥ n^2/2 then <Ref> holds for n≥ 6, so we may assume n=4 or d<n^2/2. If n=4 then <Ref> holds if d≥ 10, and so by <cit.> we have d=4 or 5. If d<n^2/2, then by <cit.> we are reduced to a finite list of possibilities for V, and we can apply <Ref>. The cases C_r(s), r=2,3 and d=2r appear in <Ref>; the case C_2(s)≅ B_2(s) and d=5 does not appear as every element has eigenvalue 1.






 Case 2: q<s=:p^e. Assume first G is untwisted. Let _p^f be the minimal field of definition for V, so p^f≤ q.


By <cit.>, V⊗ K is a tensor product of m≥ e/f Frobenius twists of a module M. By assuming that m is maximal, we have that the minimal field of definition for M is _s,
and in particular

    |V|≥ p^df= p^(M)^mf≥ p^e·(M)^2/2 = s^(M)^2/2.


Moreover, α(G,V)≥α(G,M).
Then, if M does not appear in <Ref> and (M)≥ 3, by Case 1 we readily get α(G,V)≥ q|(S)|log(q)q^-d/3 = q|(S)|log(q)|V|^-1/3.
Assume then that (M)=2 or that M appears in <Ref>; then by the same calculation we are done unless X_σ=A_1(s) and d=4.
This case appears in <Ref> (note that the value d=4 was also found in Case 1). 

The case where G is twisted is similar, using again <cit.>.



 
    
        
  (i) In <Ref>, we did not describe explicitly the representations, and we did not list the precise conditions on q for which the examples are indeed exceptions to the stronger bound α(G,V)≫ q|(S)|log(q)q^-d/3 in <Ref>. This can be done straightforwardly, and is not relevant for us. Note that we reported the case where q is uniquely determined (e.g. in the first row, we have q=s, or the stronger bound holds), and in the other cases, usually the stronger bound holds unless q assumes a couple of values (namely s and s^2, or s^2 and s^4).
     
     
  (ii) In the fifth row, for A_1(s), we have either q≥ s, or q≥ s^1/2 and V=W⊗ W^(s^1/2) where W is the natural module. What is more, in the seventh row, V is the alternating square, which can be realized over _s also for ^2A_3(s).
        
 


 
 
     Assume V appears in <Ref> and let G≤ T ≤__d(q)(G). If G is sufficiently large then α(T,V) >2 log(q)|(S)|
     q^-d/2.
 

 
Since |(S)|≪log(s)≪log(q), it is enough to show that α(T, V) ≥ 1/q^d/2-ε for some ϵ >0. Moreover, since N≤ (ZG).(S), with Z=_q^×, we have |T:T∩ ZG|≪log(q) and so we may also assume G≤ T≤ ZG. 

Assume first q<s, so by <Ref>(ii), q=s':=s^1/2, G=A_1(s), d=4 and V=W⊗ W^(s') where W is the natural module. Write T=GZ', where Z'≤ Z, and work in every coset z'G with z'∈ Z'; counting elements of G that have eigenvalue λ with λ^s'+1=z^-1, we deduce that α(T,V)≫ 1/s' ≫ 1/q^4/2-. 

Assume then q≥ s. Let u=2 if G=^2A_r(s) with d≠ 6, and let u=1 otherwise. Then, q is a power of s^u. We have T≤ ZG, and let H:=G∩_d(s^u), so |T/H| ≤ (q-1)/(s^u-1) and α(G,V)≫α(H,V)s^u/q. In particular, whenever we show α(H,V)≫ 1/s^u we are done.


For C_r(s) and r=2,3, we see that α(H,V)≫ 1/s. This follows from the fact that for every λ∈_s, the proportion of elements of _2r(s) (r=2,3) with eigenvalue λ is ≫ 1/s.
For A_r(s) and V the natural module, we have  α(H,V)≫ 1/s from <Ref>. 
For ^2A_r(s) and V the natural module, setting K:=H∩_d(s), we deduce from <Ref> that α(K,V)≫ 1/s and so α(H,V)≫ 1/s^2=1/s^u.
For A_3(s) or ^2A_3(s) and d=6, the module is the alternating square; we count elements of H acting as diag(λ,λ^-1), with λ∈_s, on a 2-space  (nondegenerate for ^2A_3(q)) and fixing no 1-space on a  complement, and get α(H,V)≫ 1/s.
For A_1(s), if an element has eigenvalue 1 on the natural module then it has eigenvalue 1 on V,
 α(H,V)≫ 1/s. For A_2(s) and d=6 the module is the symmetric square and we obtain the same bound. 

The remaining cases are G=G_2(s) or ^2B_2(s). Write H=GZ' where Z'≤_s^×. Fix a coset zG with z∈ Z'. Assuming |z|>6 in the case G=G_2(s), there exists a regular semisimple class C in G with eigenvalue z^-1.
Then |C|/|G|≍ 1/s_0^2 and elements of zC have eigenvalue 1, so going through all such cosets we get α(H,V)≫ 1/s_0^2 ≫ 1/s^d/2-ϵ, which is enough. 
 

  This follows immediately from <Ref>.     
 



 §.§ Summarizing the proof of <Ref>


 The proofs of <Ref>, are now complete. For the reader's convenience, we summarize them here.


<Ref> reduces <Ref> to primitive groups G. If G is non-affine we apply <Ref>, so assume G is affine. It is clear that <Ref> implies <Ref> in the affine case, so it suffices to prove <Ref>. In <Ref>, we showed that <Ref> follows from <Ref>. We proved <Ref> in <Ref>, <Ref> in <Ref>, and we summarized the proof of <Ref> right at the end of <Ref>.





 
 
alpha



