Bounds For Fixed Point Free Elements In A Transitive Group and Applications to Curves over Finite Fields

Robert Guralnick^{†} Department of Mathematics University of Southern California Los Angeles,CA 90089 guralnic@mtha.usc.edu

Daqing Wan^{†} Department of Mathematics Pennsylvania State University University Park, PA 16802 wan@math.psu.edu

We investigate V_{f}, the cardinality of the value set of a polynomial f of degree n over a finite field of cardinality q. It has been shown that if f is not bijective, then V_{f} ≤ q − (q − 1)/n. Polynomials do exist which essentially achieve that bound. We do prove that if the degree of f is prime to the characteristic and f is not bijective, then asymptotically V_{f} ≤ (5/6)q. We consider related problems for curves and higher dimensional varieties. This problem is related to the number of fixed point free elements in finite groups, and we prove some results in that setting as well.

1. Introduction

We begin with an arithmetic question which motivated our interest in the group theoretic problem of estimating the number of fixed point free elements in a transitive group.

Let F_{q} be a finite field of q elements with characteristic p and let f(T) be a polynomial of degree n (n > 1) in F_{q}[T] which is not a polynomial in T^{p}. The arithmetic question raised by Chowla [Ch] is to estimate the number V_{f} of distinct values taken by f(T) as T runs over F_{q}. Birch and Swinnerton-Dyer [BS] showed that if the Galois group of f(T) − t = 0 over F̄_{q}(t) is the symmetric group S_{n}, then

V_{f} = (∑_{k=1}^{n} \frac{(−1)^{k−1}}{k!} )q + O(\sqrt{q}),  (1.0)

where the constant in the error term depends only on n. The above formula was conjectured by Chowla and others.

In this paper, we are interested in upper bounds for V_{f}. It is clear that V_{f} ≤ q with equality holding if and only if f(T) is a permutation polynomial over F_{q}. If V_{f} < q, then

† both authors partially supported by the NSF we have the following elementary upper bound for V_{f} as conjectured in [Mu] and proved in [Wa]:

V_{f} ≤ q − (q − 1)/n,  (1.1)

Simple proofs of (1.1) have been given by Turnwald [Tu] and Lenstra (personal communication). We would like to know if the bound in (1.1) is reasonably good asymptotically when q is large compared to n. This would depend on the polynomial f(T) in consideration.

It is well known that there is an asymptotic formula for V_{f} in terms of certain Galois groups (cf. [Co]). More precisely, let G be the Galois group of f(T) − t = 0 over F_{q}(t) and let N be the Galois group of f(T)−t = 0 over F̄_{q}(t), where F̄_{q} is an algebraic closure of F_{q}. Both groups act transitively on the n roots of f(T) − t = 0. The geometric monodromy group N is a normal subgroup of the arithmetic monodromy group G. The quotient G/N is a cyclic group (possibly trivial). Let xN be the coset which is the Frobenius generator of the cyclic group G/N. The Cebotarev density theorem for function fields yields the following asymptotic formula:

V_{f} = (1 − \frac{|S_{0}|}{|N|})q + O(\sqrt{q}),  (1.2)

where S_{0} is the set of group elements in the coset xN which fix no roots of f(T) − t = 0. Note that the constant in the above error term depends only on n, not on q. Thus, to understand the asymptotic behavior of V_{f}, it suffices to understand the quotient

s_{0} = \frac{|S_{0}|}{|N|}.

It is clear that s_{0} ≥ 0 with equality holding if and only if f(T) is an exceptional polynomial over F_{q} (see [FGS] for a classification of the possible monodromy groups for exceptional polynomials). Lenstra recently observed that if s_{0} > 0, then s_{0} ≥ 1/n with equality holding if and only if G = N is a Frobenius group of order n(n − 1) with n a prime power. Our purpose here is to find the next possible value for s_{0} assuming s_{0} > 1/n. We have

Theorem 1.1. Let f(T) be a polynomial over F_{q} of degree n > 6 which is not a polynomial in T^{p}. If s_{0} > 1/n, then s_{0} ≥ 2/n with equality holding if and only if G = N is a Frobenius group of order n(n − 1)/2 with n a prime power. In particular, V_{f} ≤ (1 − 2/n)q + O_{n}(\sqrt{q}) unless f is exceptional or G = N is a Frobenius group of order n(n − 1).

As it will be seen in the next section, our proof of the Theorem above is significantly harder than the proof of the bound s_{0} ≥ 1/n for s_{0} ≠ 0. In fact, in addition to some non-trivial elementary arguments, we also have to use the classification of finite simple groups. We do not know an elementary proof of Theorem 1.1. It was suggested by Lenstra that if the polynomial f(T) is tame (i.e. all ramifications of the corresponding cover of ℙ^{1} to ℙ^{1} are tame), then it should be possible to have an absolute lower bound s_{0} > c for some absolute positive constant c. We show that this is indeed the case. Indeed, we only need to assume that there is tame ramification at ∞ (or equivalently the degree is prime to the characteristic).

Theorem 1.2. Let f(T) be a polynomial over F_{q} of degree n > 1 with n not divisible by the characteristic of F_{q}. Then we have s_{0} > 1/6 whenever s_{0} > 0. In particular, either f is bijective or V_{f} ≤ (5/6)q + O_{n}(\sqrt{q}).

No attempt is made here to optimize the constant 1/6. If n is not a multiple of p, there will be polynomials whose monodromy groups are S_{n} or the dihedral group of order 2n. This shows that 1/6 cannot be improved to any better than 1/e (symmetric groups) or more easily 1/2 (dihedral groups) even for f indecomposable and n large. If we assume that all ramification is tame, then we show that s_{0} > 0 implies that s_{0} ≥ 16/63 and that the bound is best possible (see Corollary 4.8).

If we drop the assumption that n is prime to p, then the result is false. The Frobenius group of order p^{a}(p^{a} − 1) can be identified with the group of upper triangular matrices in P GL_{2}(p^{a}) and so acts on ℙ^{1}. Moreover, it fixes ∞. Thus, there is a polynomial f of degree p^{a} whose geometric monodromy group is Frobenius of order p^{a}(p^{a} − 1). It can be written down explicitly – it satisfies f(x^{p^{a}−1}) = (x^{p^{a}} − x)^{p^{a}−1} and thus f(x) = x(x − 1)^{p^{a}−1}. If p^{a} − 1 divides q − 1, then the arithmetic monodromy group is equal to the geometric monodromy group. Thus, s_{0} = 1/p^{a} = 1/n.

In terms of the value set, one can compute directly that V_{f} = qd/(d + 1), where d = (p^{a} − 1, q − 1) (this has been considered by Müller, Flynn and Cusick ). In particular, the elementary bound in (1.1) is attained for this polynomial f(x) of degree n = p^{a} if F_{q} contains F_{p^{a}} as a subfield.

Again, our proof of Theorem 1.2 depends on the classification of finite simple groups. In terms of our motivating question on value sets, this shows that if the degree n is not divisible by p and if V_{f} < q, then

V_{f} ≤ \frac{5}{6}q + O(\sqrt{q}).  (1.3)

This is a vast improvement of (1.1) if q is large compared to n and n is not divisible by p.

Some of the above results can be generalized to coverings of non-singular curves and even to coverings of higher dimensional varieties. See sections 3-5. The higher dimensional value set problem was first considered by Serre [S2] in connection with Hilbert’s irreducibility theorem and the inverse Galois problem. Let f : Y ⟶ Z be a finite morphism of degree n between two absolutely irreducible m-dimensional (m > 0) quasi-projective varieties defined over F_{q}. Let V_{f} be the cardinality of the value set f(Y (F_{q})). Assume that f is not exceptional over F_{q}, i.e., the fiber product Y ×_{Z} Y with its diagonal removed contains some absolutely irreducible component of dimension m defined over F. Then, we have the bound

V_{f} ≤ (1 − \frac{1}{n})q^{m} + O(q^{m−1/2}).  (1.4)

The weaker estimate

V_{f} ≤ (1 − \frac{1}{n!})q^{m} + O(q^{m−1/2}).  (1.5)

was given in [S2, Theorem 3.6.2]. The higher dimensional bound in (1.4) holds because there is a similar Cebotarev density theorem for higher dimensional varieties, see Fried [Fr2, section 4]. More higher dimensional results are given in section 5, as well as a direct geometric proof avoiding the Cebotarev density theorem.

In the special case that G = N, the above group theoretic question about s_{0} also arises naturally in other context. Let G be a transitive permutation group acting on a set X of n letters with n > 2. Let S_{0} be the set of elements of G which fix no letters of X. A classical simple result of Jordan [Jo] says that |S_{0}| > 0. Motivated by number theoretic and algorithmic applications such as the number field sieve [BLP, Section 9], Lenstra (1990) asked the question of finding a good lower bound for the quotient

s_{0}(G) = \frac{|S_{0}|}{|G|},

see the paper by Boston et al [Bo]. Soon afterwards, Cameron and Cohen [CC] showed that s_{0}(G) ≥ 1/n with equality holding if and only if G is a Frobenius group of order n(n − 1), where n is a prime power. A simpler proof of the Cameron-Cohen result is given in [Bo] where the value s_{0}(G) is calculated for several classes of groups. A natural open problem as posed in [Bo, p. 3274] is to find the next possible bound if s_{0} > 1/n and classify the optimal groups. This problem is solved here.

Theorem 1.3. Let G be a transitive permutation group of degree n. One of the following holds:

(a) G is a Frobenius group of order n(n − 1) with n a prime power and s_{0}(G) = 1/n;

(b) G is a Frobenius group of order n(n−1)/2 with n an odd prime power and s_{0}(G) = 2/n;

(c) G = S_{4}(n = 4, s_{0} = 3/8), S_{5}(n = 5, s_{0} = 11/30), A_{5}(n = 5, 6, s_{0} = 2/n), Z/2(n = 2, s_{0} = 1/2) or Z/3Z(n = 3, s_{0} = 2/3); or

(d) s_{0}(G) > 2/n.

Acknowledgment. The second author would like to thank H. W. Lenstra, Jr for valuable discussions on the above problem about s_{0}. We would also like to thank Peter Müller and Michael Zieve for comments on an earlier version of the paper and Michael Fried for discussions on the Cebatorev density theorem.

2. The Case G = N

In this section, we prove the group theoretic Theorem 1.3. Let G be a transitive permutation group acting on a set X of n letters. To prove the theorem, we first derive some elementary bounds which relate the number s_{0} to the minimal degree μ of the group G. Recall that μ is the minimal number of elements moved by a non-identity element of G. A detailed investigation of the minimal degree is given in Liebeck-Saxl [LS].

We digress slightly for a brief discussion of Frobenius groups. See [Pa] for more details. G is said to be regular on X if no nontrivial element fixes a point. G is called a Frobenius group on X if G is not regular on X but no nontrivial element fixes more than 1 point. If G is Frobenius, it follows by character theory that G contains a normal subgroup A acting regularly (and in particular transitively) on X. Thus, |A| = n and we can identify X with A. If G is regular or Frobenius, it follows that |G| = nd where d|(n − 1). Thus, s_{0} = (n − 1)/dn.

We consider 2 special cases. If d = n − 1, it follows that any two nonidentity elements of A are conjugate in G, whence A is an elementary abelian p-group for some prime p (and so n is a power of p). If d = (n−1)/2, there are two conjugacy classes (in G) of nonidentity elements in A each of size d. It is an easy exercise to prove that this again implies that A is an elementary abelian p-group for some prime p (necessarily odd) and n is a power of p.

More generally, it follows by a result of Thompson that for any Frobenius group the normal subgroup A is nilpotent.

For 0 ≤ i ≤ n, let S_{i} be the set of elements of G which fix exactly i letters of X. Define s_{i} = s_{i}(G) = |S_{i}|/|G|. It follows from the definition that s_{n} = 1/|G| and s_{n−1} = ⋯ = s_{n−μ+1} = 0, where μ is the minimal degree of G. We want to estimate s_{0}. Trivially, we have the relation

s_{0} + s_{1} + s_{2} + ⋯ + s_{n} = 1.  (2.1)

To derive more relations among the numbers s_{i}, we define X_{j} (1 ≤ j ≤ n) to be the j-fold Cartesian product with all diagonals removed. Namely, the set X_{j} consists of all j-tuples from X with all coordinates distinct. Let r_{j} be the number of orbits of X_{j} under the coordinate-wise action of G. Since G is transitive, we have r_{1} = 1. We may apply Burnside’s formula (or use elementary character theory) to the action of G on X_{j} and deduce the following relations:

∑_{i=j}^{n} \binom{i}{j}s_{i} = \frac{r_{j}}{j!} , 1 ≤ j ≤ n.  (2.2)

To estimate s_{0}, we try to eliminate some of the numbers s_{i} from the above relations. Subtract (2.1) from the first equation of (2.2), one sees that

s_{0} = \frac{r_{1}}{1!} − (1 − s_{0}) = ∑_{i=2}^{n} \binom{i − 1}{1}s_{i}.  (2.3)

Multiply equation (2.3) by n/2 and subtract the second equation of (2.2), one checks that

\frac{ns_{0}}{2} − \frac{r_{2}}{2} = ∑_{i=2}^{n−μ} \frac{(n − i)(i − 1)}{2}s_{i} ≥ 0.  (2.4)

This immediately gives the previously known bound s_{0} ≥ r_{2}/n (≥ 1/n) with equality holding if and only if all s_{i} = 0 for 2 ≤ i < n, namely, G is a Frobenius group of order n(n − 1) or ℤ/2 (for n = 2).

To obtain finer bounds, we need to make use of r_{3}. Multiply the second equation of (2.2) by (n − 2)/3 and subtract the third equation of (2.2), we deduce that

\frac{(n − 2)r_{2} − r_{3}}{3!} = ∑_{i=2}^{n−μ} \frac{(n − i)i(i − 1)}{3!}s_{i} ≥ 0.  (2.5)

Now, we eliminate s_{n−μ} from (2.4) and (2.5). Multiply (2.4) by (n − μ)/3 and subtract (2.5), it follows that

\frac{n − μ}{3}(\frac{ns_{0}}{2} − \frac{r_{2}}{2} ) − \frac{(n − 2)r_{2} − r_{3}}{3!} = ∑_{i=2}^{n−μ−1} \frac{(n − i)(n − μ − i)(i − 1)}{3!}s_{i} ≥ 0.

Solving this inequality, we derive the bound

s_{0} ≥ \frac{r_{2}}{n} + \frac{(n − 2)r_{2} − r_{3}}{n(n − μ)} .  (2.6)

Note that the last term in (2.6) is always nonnegative in view of (2.5). It is strictly positive unless G is a Frobenius group (i.e., s_{2} = ⋯ = s_{n−1} = 0). If G is a Frobenius group, then s_{0} = (n − 1)/|G| and so s_{0} > 2/n unless |G| = n(n − 1) or n(n − 1)/2. Since the one point stabilizer G_{x} acts as fixed point free automorphisms of the regular normal subgroup N of G, it follows easily that n = |N| is a prime power.

If n ≤ 6, Theorem 1.3 follows by inspection of the various primitive groups. To prove the theorem, we may therefore assume that n > 6, r_{2} = 1 and 1 < r_{3} < n − 2; namely, G is 2-transitive but neither 3-transitive nor sharply 2-transitive (since n > 6). We shall assume this condition throughout the remainder of this section. Thus, the bound in (2.6) reduces to

s_{0} ≥ \frac{1}{n} + \frac{n − (r_{3} + 2)}{n(n − μ)}.  (2.7)

We want to prove that s_{0} > 2/n. Note that the number (r_{3} +2) in (2.7) is just the number of orbits of the stabilizer of two letters acting on X since G is doubly transitive. By (2.7), we have

Lemma 2.1. If (r_{3} + 2) < μ, then s_{0} > 2/n.

We now derive a simple bound for r_{3} + 2 in terms of μ. Multiply the second equation of (2.2) by (n − μ − 2)/3 and subtract the third equation of (2.2), one computes that

\frac{(n − μ − 2) − r_{3}}{3!} ≥ −\frac{n(n − 1)μ}{3!|G|}.  (2.8)

Namely,

(r_{3} + 2) ≤ n − μ + [n(n − 1)μ/|G|],  (2.9)

where [x] denotes the integral part of x.

As a trivial application of (2.9), we have r_{3} + 2 ≤ n − \frac{μ}{2} since |G| ≥ n(n − 1)2 for G 2-transitive but not sharply. The equality (r_{3} + 2) = n − \frac{μ}{2} holds only if |G| = n(n − 1)2. This can also be proved directly: the number (r_{3} + 2) of orbits of the stabilizer of two letters is the sum of the number (≤ n − μ) of orbits of length one and the number (≤ μ/2) of orbits of length greater than one.

By (2.7) and the remark above, we have:

Lemma 2.2. (a) If μ > 2n/3, then s_{0} > 2/n;

(b) If μ = 2n/3, then s_{0} > 2/n unless G_{xy} is a subgroup of order 2.

Remark. Manning’s (cf. [Wi] ) classical bound μ > n/3 + O(\sqrt{n}) together with (2.9) easily gives the weaker inequality s_{0} > (\frac{5}{4} − ϵ)/n if s_{0} > 1/n. But this is a little far from the optimal 2/n.

We still assume G is 2-transitive and neither sharply 2-transitive nor 3-transitive. We first consider the affine case. So G is a 2-transitive subgroup of AΓL_{d}(q), the

group of affine semilinear transformations of a d-dimensional space V of F_{q} with n = q^{d}. Note that we can identify V as a subgroup of G (acting via translation) and G = V G_{0}, where G_{0} is the stabilizer of 0. So G_{0} is a subgroup of ΓL_{d}(q), the group of semilinear transformations.

Lemma 2.3. (a) If d > 1, then μ ≥ (q − 1)n/q.

(b) If d = 1 and q is prime, then μ = q − 1.

(c) If d = 1 and q = q_{0}^{e} with e prime and minimal, then μ ≥ q − q_{0}.

Proof. Let 1 ≠ g ∈ G fixing 0 which moves the fewest points. We may assume that g has prime order. If g is linear, then its fixed points form a proper subspace and so g moves at least q^{d} − q^{d−1} points. Otherwise, g is conjugate to a field automorphism (this follows by Lang’s theorem). It follows that the number of fixed points is q_{0}^{d} where q = q_{0}^{e}. If d > 1, the linear case is worst possible. If d = 1 and q is prime, then only the linear case occurs.

Combining Lemma 2.2 and Lemma 2.3 yields that s_{0} > 2/n unless q ≤ 3 or d = 1 and q = 4 or 9. If d = 1 and q = 4 or 9, then the result follows easily by inspection.

Moreover, if q = 3, the result follows from Lemma 2.2(b) unless μ = 2n/3 and G_{0v} has order 2. Let 1 ≠ g ∈ G_{0v}. If d = 1 or 2, the result follows by inspection. Let g ≠ h be a conjugate of g in G_{0} (since G_{0} is transitive on the nonzero vectors in V, such h exists). Then g and h are trivial on some d − 2 dimensional space and so are both contained in G_{0w} for some w. This contradicts the fact that G_{0w} has order 2.

So we may assume that q = 2. If d ≤ 2, the result follows by inspection. If G_{0} does not contain any transvections (i.e. unipotent elements fixing a hyperplane), then μ ≥ 3n/4. Lemma 2.2 gives s_{0} > 2/n. Thus, G_{0} is a transitive subgroup on V − {0} of GL_{d}(2) containing transvections. It follows by McLaughlin [Mc] that G_{0} = SL_{d}(2) or Sp_{d}(2) (with d ≥ 4 even in the last case). In the first case, G_{0} is 2-transitive on V − {0} and so G is 3-transitive. In the latter case, G_{0v} has 3 orbits on nonzero vectors (depending upon the inner product with v) and so r_{3} + 2 = 4. Since μ = n/2 and n ≥ 16, the result holds here by Lemma 2.1.

In fact, one does not need to use McLaughlin’s result here. If d ≤ 3, this is obvious. For d > 3, we can find three transvections which act irreducibly on a 3-dimensional space. If d > 3, this group is contained in G_{0w} for some w. Then r_{3} + 2 ≤ n/4 and μ = n/2. The result holds here by Lemma 2.1.

This completes the proof for the bound s_{0} > 2/n for G in the affine case (note that this also completes the proof for the general result if G is solvable).

We now assume that G does not preserve an affine structure on the set. We are still assuming that G is 2-transitive but not 3-transitive. It follows easily that G contains a simple nonabelian normal subgroup L with L ⊆ G ⊆ Aut(L) (cf. [Wi, Ex. 12.4]). The following table lists all such 2-transitive groups aside from the cases where L is alternating or a Mathieu group (in which case L is 3-transitive – note that M_{11} has a multiply transitive representations of degree 11 and 12).

The table lists the simple group L, the permutation degree n, an upper bound for n − μ and an upper bound for r_{3} + 2.

Unfortunately the table depends upon the classification of finite simple groups (see Kantor [Ka]):

Table 1: 2-transitive Almost Simple Groups

L  n  n − μ  r_{3} + 2
L_{2}(q), 4 < q, q not prime q + 1  q^{1/2} + 1  4
L_{2}(p), 4 < p, p prime  p + 1  2  4
Sz(q), q = 2^{2e+1} ≥ 8  q^{2} + 1  q^{2/3} + 1  q + 3
2G_{2}(q), q = 3^{2e+1} ≥ 27  q^{3} + 1  q + 1  q^{2} + q + 4
U_{3}(q), q > 2 and nonsquare q^{3} + 1  q + 1  3q + 2
U_{3}(q), q square  q^{3} + 1  q^{3/2} + 1  3q + 2
L_{d}(q), d ≥ 3  (q^{d} − 1)/(q − 1) (q^{d−1} − 1)/(q − 1) 4
Sp_{2d}(2), d ≥ 3  2^{2d−1} ± 2^{d−1}  2^{2d−2}  4
A_{7}  15  7  4
L_{2}(11)  11  3  4
L_{2}(8)  28  4  16
HS  176  16  5
Co_{3}  276  36  4

A few comments are in order about the table. In all cases except L = L_{2}(8), L itself is 2-transitive. The information for the last five cases can be read off from [ATLAS]. If L = L_{d}(q), the action is on the 1-spaces (or hyperplanes) of a d-dimensional vector space over F_{q} and all quantities are easy to compute. If L = U_{3}(q), the action is on singular 1-spaces (singular with respect to a hermitian form) in a three dimensional space over F_{q^{2}} and the estimates are quite easy to obtain.

If L = Sz(q) or ^{2}G_{2}(q), these estimates follow easily from well known properties of the groups (cf. [HB, 10.3.10, 11.13.2]).

Finally, if L = Sp_{2d}(2), then G = L and the point stabilizers are O_{2d}^{±}(2) and the action on the nontrivial orbit is just the natural action of the orthogonal group on singular vectors. This easily gives r_{3}+2 = 4. The maximum number of fixed points for a nonidentity element is bounded by 1 + k where k is the number of singular vectors in a hyperplane.

In all cases, it follows that r_{3} + 2 < μ (except L = L_{2}(p) ≅ A_{5} with p = 5 and n = 6 – in that case, it follows that s_{0} = 1/3 = 2/n if G = L and s_{0} > 2/n for G = P GL_{2}(5)). The proof of Theorem 1.3 is complete.

To conclude this section, we note that for those groups G with r_{2} = 1 and r_{3} ≤ 2, an absolute positive lower bound for s_{0} can be obtained. In fact, by an inclusion-exclusion argument, one sees that the alternating sum of equation (2.1) with the first three equations of (2.2) gives that for n > 3,

s_{0} > ∑_{i=0}^{n}(\binom{i}{0} − \binom{i}{1} + \binom{i}{2} − \binom{i}{3})s_{i}

= 1 − \frac{r_{1}}{1} + \frac{r_{2}}{2!} − \frac{r_{3}}{3!}

= \frac{r_{2}}{2} − \frac{r_{3}}{6} .  (2.10)

This can also be checked directly from the the following inclusion-exclusion inequality

\binom{i}{0} − \binom{i}{1} + \binom{i}{2} − \binom{i}{3} \{ \begin{matrix}= 1, & if i = 0, \\ = 0, & if i = 1, 2, 3, \\ < 0, & if i > 3. \end{matrix}

and the fact that s_{n} = 1/|G| > 0. In particular, we have

Corollary 2.4. Let n > 3. If r_{3} = 1, then s_{0} > 1/3. If r_{2} = 1 and r_{3} = 2, then s_{0} > 1/6.

A similar inclusion-exclusion argument shows that for n > 2,

s_{0} < ∑_{i=0}^{n}(\binom{i}{0} − \binom{i}{1} + \binom{i}{2})s_{i}

= 1 − \frac{r_{1}}{1} + \frac{r_{2}}{2!}

= \frac{r_{2}}{2} .  (2.11)

Thus, we have

Corollary 2.5. Let n > 2. If r_{2} = 1, then s_{0} < 1/2.

3. The General Case

In this section, we study the general case when G may not be equal to N. Let G be a group with a normal subgroup N with G/N cyclic. Let x denote a generator for G/N. We generalize the notions discussed earlier. We have a complete generalization of Theorem 1.3 only for those pair (G, N) which comes from a covering of connected smooth projective curves with a totally ramified F_{q}-rational point. First we note the following easy result (which is essentially proved in [FGS, §13]). We give a different proof suggested by Müller.

Lemma 3.1. Let G act on a finite set X. Let ϕ denote the following permutation character: ϕ(g) = |X^{g}|. Let r = r(X) be the number of common G, N orbits on X. Then

(1/|N|) ∑_{g∈xN} ϕ(g) = r.

Proof. Clearly, we may assume that G is transitive on X. Note that N is also transitive on X if and only if xg has a fixed point for some g ∈ N. So, N is not transitive if and only if both sides of the equation are 0. So assume that G and N are both transitive (so r = 1).

Set

Y = {(xg, ω) ∈ xN × X|xg(ω) = ω}.

Let G_{ω} be the point stabilizer in G of ω (and similarly for N). On one hand, |Y | = ∑_{g∈xN} ϕ(g). On the other hand, if ω ∈ X and xg fixes ω, then G_{ω} ∩ xN = xgN_{ω}. In particular, there are |N_{ω}| elements in G_{ω} ∩ xN. Thus, |Y | = |X||N_{ω}| = |N| as desired.

Now assume that G and N are both transitive on X. We will denote the cardinality of X by n. By passing to a quotient, we may always reduce to the case that G is faithful on X. We assume that from now on.

Let S_{i} be the set of elements in the coset xN which fix exactly i elements of X. Let s_{i} = |S_{i}|/|N|. Let r_{i} be the number of common G, N orbits on the i-fold cartesian product of X with the diagonals removed (so all coordinates are distinct).

We first note that:

Lemma 3.2. The following are equivalent:

(a) r_{2} = 0;

(b) s_{0} = 0;

(c) Every element in the coset xN fixes a unique point;

(d) Every element in the coset xN fixes at most one point;

(e) Every element in the coset xN fixes at least one point.

Proof. The equivalence of (c)-(e) follows from Lemma 3.1 (see also [FGS, 13.1]). Clearly (b) and (e) are equivalent. Note G(a, b) = N(a, b) if and only if some element in xN fixes (a, b). So r_{2} ≠ 0 is equivalent to some element in xN fixing at least two points. Thus, (a) is equivalent to (d).

The triple (G, N, X) is called exceptional if it satisfies the above conditions. If G is the arithmetic monodromy group of a branched covering (always separable) of connected smooth projective curves over a finite field and N is the geometric monodromy group, then these triples correspond to exceptional coverings (see [FGS]).

Lemma 3.3. Let H be a point stabilizer of some point of X. Let K be a subgroup of G containing H. Let Y be the coset space G/K and Z the coset space K/H.

(a) s_{0}(G, N, X) ≥ s_{0}(G, N, Y);

(b) if (G, N, Y) is exceptional, then s_{0}(G, N, X) = s_{0}(K, N ∩ K, Z); and

(c) (G, N, X) is exceptional if and only if (G, N, Y) and (K, N ∩ K, Z) are exceptional.

Proof. Since N is transitive, it follows that G = HN = KN and so x(N ∩ K) generates K/(N ∩ K). If x fixes no point in Y, then clearly it fixes no point in X, whence (a).

Assume that (G, N, Y) is exceptional. Let K_{y} denote the stabilizer of a point y ∈ Y. Then xN is a disjoint union of the xN ∩K_{y}, y ∈ Y (since each element of xN fixes a unique point of Y). The number of fixed point free elements in each intersection is independent of y (since these sets are all conjugate). Thus, the number of fixed point free elements on X is |Y |S_{0}(K, K ∩ N, Z) and (b) holds.

If X is exceptional, then (a) implies Y is. On the other hand, if Y is exceptional, then (b) implies that X is exceptional if and only if Z is. This proves (c), which can also be easily deduced from Lemma 3.2.

In [FGS], it was proved that if (G, N, X) is an exceptional triple with G primitive on X which corresponds to an exceptional covering of connected smooth projective curves over a finite field with a rational point that is totally ramified (e.g., if f is an exceptional polynomial), then G was shown to be either a solvable group of prime degree or an affine group of degree a power of the characteristic or one additional infinite family in characteristic 2 or 3. Moreover, the previous lemma shows that any exceptional covering is a composition of primitive exceptional coverings (see [FGS]).

Now assume that r_{2} ≥ 1. Arguing exactly as in section 2, we obtain:

s_{0} ≥ \frac{r_{2}}{n} + \frac{(n − 2)r_{2} − r_{3}}{n(n − μ)} .  (3.1)

Moreover, the last term on the right is strictly positive unless for each (a, b) with G(a, b) = N(a, b), G_{a,b} = 1. Since G = NG_{a,b}, this implies that G = N and G is a Frobenius group. This case has already been handled. Lemmas 2.1-2.2 are also valid in the present more general case.

Thus, we have shown:

Lemma 3.4. (a) If r_{2} > 0, then either s_{0} > r_{2}/n or G = N is a Frobenius group (or regular group) on X.

(b) If G = N is a Frobenius group (or regular group) on X, then s_{0} = r_{2}/n.

(c) If r_{2} > 1, then s_{0} ≥ 2/n with equality holding if and only if either G = N is a Frobenius group of order n(n − 1)/2 with n an odd prime power or G = N is cyclic of order 3.

(d) If r_{2} = 1, then s_{0} ≥ 1/n with equality if and only if G = N is a Frobenius group of order n(n − 1) with n a prime power or G = N is cyclic of order 2.

If G is a Frobenius group and G ≠ N, then every element in xN has at most one fixed point, whence exactly one and so G is exceptional.

Lemma 3.5. If G is not primitive on X, then one of the following holds:

(a) s_{0} > 2/n;

(b) (G, N, X) is exceptional; or

(c) n = 4, G has order 8, N has order 4 and s_{0} = 2/n.

Proof. If r_{2} = 0, then the triple is exceptional. If r_{2} > 1, then s_{0} > 2/n unless G is Frobenius of order n(n − 1)/2 and so is primitive.

So we may assume that r_{2} = 1. If G = N, then G is 2-transitive and primitive.

First consider the case that n = 4. It follows that G is a 2-group (otherwise G is 2transitive). If it has order 4, then G acts regularly, whence s_{0} ≥ 3/n. Otherwise, G is dihedral of order 8. If G = N, s_{0} = 5/8. If G ≠ N, then N has order 4 and since every nonidentity element has either 0 or 2 fixed points, s_{0} = 1/2.

Suppose G is not primitive on X. Let H be the stabilizer of a point in X and let H < K < G. Set Y = G/K. If (G, N, Y) is not exceptional, then s_{0}(Y) ≥ 1/m where m = [G : K]. Clearly, s_{0}(Y) ≥ s_{0} ( by Lemma 3.2). Thus, s_{0}(Y) ≥ 2/n with equality possible only if n = 2m and G acting on Y is a Frobenius group order m(m−1). If g ∈ xN has no fixed points on Y, then clearly this is also true on X. The number of such elements is |S_{0}(Y)| ≥ (2/n)|N|. If m > 2, then some element in xN acts nontrivially on Y but with fixed points. We may then assume that x ∈ K. Since K ∩ N ≠ H ∩ N (as G = HN = KN and K > H), we may also assume that x ∉ H. Then x has a unique fixed point on Y. Thus, the only possible fixed points for x on X are gH with g ∈ K. Since x ∉ H, x fixes no such point and so has none on X. Hence s_{0} > s_{0}(Y) ≥ 2/n. If m = 2, then n = 4 and (c) holds.

If (G, N, Y) is exceptional, then (K, N ∩ K, Z) is not (where Z = K/H). Then each element in xN fixes a unique coset of K, whence (Lemma 3.2) s_{0} = s_{0}(K, N ∩K, Z) ≥ 1/m where m = [K : H]. Since degree 2 permutation representations are not exceptional, m > 2. Hence s_{0} ≥ 3/n.

One can use induction and the previous result to show that if X = G/H and there is a chain of subgroups H = H_{0} < H_{1} < … < H_{d} < G, then either X is exceptional or s_{0} ≥ 2^{d−1}/n.

We would like to classify all triples with s_{0} ≤ 2/n. By the previous lemmas, it suffices to consider the primitive case.

We will not classify all possibilities, but we assume that G is the arithmetic monodromy group of a branched covering of connected smooth projective curves defined over a finite field and N is the geometric monodromy group. Moreover, we will further assume that there is a totally ramified F_{q}-rational point (e.g., a polynomial map from ℙ^{1} to ℙ^{1} - so ∞ is the totally ramified point). Without loss of generality by Lemma 3.5, we also assume that the covering is indecomposable of degree n. Thus, G is a primitive (faithful) permutation group of degree n.

As noted above, exceptional groups (corresponding to monodromy groups of exceptional covers with a totally ramified rational point) were essentially classified in [FGS] (exactly which affine groups are possible was left open). In [GS], a list of possibilities for G (and the permutation action) were determined.

Theorem 3.6. Let α : X → Y be a separable branched covering of degree n with X, Y, α defined over F_{q}. Assume moreover that one of the branch points is totally ramified and is F_{q}-rational. Let p be the characteristic of F. Let G be the arithmetic monodromy group of the covering and N the geometric monodromy group. Then one of the following holds:

(a) r_{2} = 0 and the covering is exceptional;

(b) r_{2} = 1 , s_{0} = 1/n and G = N is Frobenius of order n(n − 1) with n a prime or p^{a};

(c) r_{2} = 2, s_{0} = 2/n and G = N is Frobenius of order n(n − 1)/2 with n an odd prime or p^{a} (with p > 2);

(d) s_{0} > 2/n; or

(e) n ≤ 6, G = N and 1/n ≤ s_{0} ≤ 2/n or n = 4, |G/N| = 2 and s_{0} = 2/4.

Proof. By Lemma 3.5, we may assume that the cover is indecomposable (over F_{q}). By the preceding remarks, we may assume that r_{2} = 1.

First assume that G is affine and n = r^{a} for some prime power r. By Lemmas 2.2 and 2.3, it follows that s_{0} > 2/n unless n = 4 or 9 or r ≤ 3. We identify X with a vector space V of over the field of r elements. Then G_{0}, the stabilizer of 0, is a group of semilinear transformations on V.

If n = r = 4, then G = A_{4} or S_{4}. If G = A_{4} and N has order 4, then G is exceptional. If G = N = A_{4}, then G is Frobenius.

If n = 9, then by inspection it follows that either G = N is Frobenius, G is exceptional, or s_{0} ≥ 1/3.

Next assume q = 3, n = 3^{a} > 9 and r_{2} = 1. It follows from Lemmas 2.2 and 2.3 that either G is Frobenius, s_{0} > 2/n or we may assume that x is a reflection and G_{0,v} has order 2 for any v ≠ 0 fixed by x. If w is fixed by x, then G(0, w) = N(0, w). Since r_{2} = 1, it follows that the nonzero elements of the fixed hyperplane W of x is contained in a single G_{0}-orbit. Let u be a vector in the −1 eigenspace of x. Since G_{0,v} = ⟨x⟩, the centralizer of x is transitive on the nonzero elements in W. Moreover, since G_{0} is irreducible on V (by primitivity), it follows that G_{0}u = G_{0}v. Thus, some reflection x′ centralizes u. Since a > 2, x and x′ both fix some nonzero vector w in W. Then G_{0,w} has order greater than 2. Since v and w are in the same G_{0}-orbit, the same is true for G_{0,v}, a contradiction.

Now assume r = 2, n = 2^{a} > 4, and r_{2} = 1. We may assume that x fixes 0. If xN_{0} does not contain a transvection, then the minimal degree of an element in xN is (3/4)n and s_{0} > 2/n (by the argument of Lemma 2.2). So we may assume that x is a transvection. Let W be the fixed hyperplane of x. Since N(0, w) = G(0, w) for any nonzero element of W and r_{2} = 1, G(0, w) = G(0, v) and all nonzero vectors of W are in the same G_{0}-orbit.

Let H be the subgroup of G_{0} generated by transvections. Since all nonzero vectors in W are in the same G_{0}-orbit, for each 0 ≠ w ∈ W, there is a transvection τ_{w} centered on w. This implies that the only possible nontrivial invariant subspace is W. Since H is normal in G_{0}, this would imply that G_{0} would leave W invariant, a contradiction. It follows by [Mc] that the only irreducible subgroups of GL(V)) for which a single orbit contains all nonzero vectors in a hyperplane are SL(V) or Sp(V). Now argue as above.

It follows by [GS] that in the affine case n = p^{a}, n is prime or n = 4.

So we may assume that G is not affine. Now using [GS], we have the following cases to consider:

(i) F^{∗}(G) = L is simple and is given [GS, 3.1]; (ii) F^{∗}(G) = L × L with L simple and n = 4p^{2a}, p odd given in [GS, 4.2]; (iii) F^{∗}(G) = P Ω_{4}^{+}(q), n = q(q^{2} − 1)/(2, q − 1) with q ≥ 4; (iv) n = p^{a}; or

We first note that if G is 2-transitive (in particular, if G = N and r_{2} = 1), then we argue precisely as above in the 2-transitive case. If G is a rank 3 permutation group (i.e. G_{a} has three orbits), then r_{2} = 0 or r_{2} = 2 and we are done.

Consider (i). The following are immediate consequences of [GS, 3.1]. If L is a sporadic simple group, then r_{2} > 1 or G is 2-transitive. If L is an alternating group (which is not a classical group), then G is either 2-transitive or rank 3. Moreover, L is not an exceptional Chevalley group. Thus, the remaining case is L classical.

In case B(i) of [GS, 3.1], L is an even dimensional unitary group (at least 4 dimensional) or an orthogonal group (of dimension at least 3 and + type in even dimension) and the point stabilizer (in L) may be taken to be the stabilizer of a nonsingular 1-space (of − type if L is an odd dimensional orthogonal group). Note that case (iii) above also is of the same type (except that L is not simple). In the unitary case, it follows that r_{2} > 1 (the pairs of 1-spaces represented by (u, v) with (u, v)/(u, u) either 0 or 1 correspond to L-orbits which are Aut(L)-orbits). Similarly, r_{2} > 1 for orthogonal groups in dimension at least 4 for fields of odd characteristic and even dimensional orthogonal groups in even characteristic.

Next consider the three dimensional orthogonal groups. In this case, L = Ω_{3}(q) = L_{2}(q). We may assume that q ≥ 4. If q = 4, G is 2-transitive and if q = 5, G is rank 3, so we may assume that q > 5. We can identify X with the set of orbits of size 2 on ℙ^{1} of the field automorphism σ defined by a ↦ a^{q}.

We claim that any nonidentity element fixes at most (4/q)n points. It suffices to consider elements of prime order. If g has odd prime order, then it fixes an orbit of size 2 of σ only if it fixes each point. If g ∈ P GL_{2}(q), then g fixes at most 2 points in ℙ^{1}, whence g fixes at most 1 point in X. Otherwise g is conjugate to an element inducing a field automorphism, whence g fixes at most (q^{2/3} − q^{1/3})/2 points on X and the claim holds. If g is an involution and g ∈ P GL_{2}(q), then g fixes at most (2q +4)n/(q^{2} −q) points and the claim holds. Finally, if g is an involution conjugate to a field automorphism, then g will fix at most (q_{0} + 1)n/(q + 1)q_{0} points on X, where q_{0}^{2} = q (note q is a square in this case). In particular, μ > (2/3)n for q ≥ 11. It follows by Lemma 2.2 that either G is exceptional or that s_{0} > 2/n. If q = 8, G = N and r_{2} = 3 or G is exceptional. If q = 9, one checks directly that r_{2} > 1.

If q = 7, then either G = N and r_{2} = 6 or |G/N| = 2. In the latter case, we compute that r_{2} = 1 and s_{0} = 1/3.

It follows by [FGS] that G is exceptional only if G = Aut(L) with q = r^{a} for r = 2, 3 and a odd (and L ≤ N ≤ M where M/L is the Frattini subgroup of G/L).

Next consider L = Ω_{2m+1}(2^{a}) = Sp_{2m}(2^{a}). Then Aut(L) has order a. It follows that μ > (2/3)n (cf. [LS]) for a > 1 and we can apply Lemma 2.2. If a = 1, then G is 2-transitive.

The only remaining cases with L classical are given in [GS, Table B]. We may eliminate the cases where G = N - in particular, those cases where N = Aut(L). This leaves 4 cases to consider, (L, L_{a}) = (L_{4}(2), GL_{2}(4).2), (L_{5}(2), P_{2}), (Ω_{8}^{+}(2), A_{9}) and (P Ω_{8}^{+}(3), Ω_{8}^{+}(2)). In all cases, it is verified that r_{2} > 1.

Next consider the case that E = F^{∗}(G) = L_{1} × … × L_{t} with L_{i} ≅ L a nonabelian simple group and E_{a} = K_{1} × … × K_{t} with K_{i} nontrivial. Let ℓ = [L_{i} : K_{i}] and n = ℓ^{t} with t > 1. Moreover, we assume that the L_{i} and K_{i} are all conjugate in G. Since G/N is cyclic, it follows that E ≤ N. We further assume that K_{1} acting on L_{1}/K_{1} has a nontrivial unique orbit of maximal size. If N is transitive on the L_{i}, then it is easy to see that r_{2} > 1. Thus, it follows that no element of the coset xN can normalize each L_{i}.

As we observed, we may assume that no element in xN normalizes each L_{i}. This implies that any element of xN fixes at most (n/ℓ) ≤ n/5 points. We can apply a version of (2.7) above (with μ replaced by the minimal degree of an element in the coset xN) to obtain s_{0} > (2/n).

By [GS, 4.1 and 4.2], it now follows that s_{0} > (2/n) in cases (ii) and (iv) above.

Remark. There should be a version of the previous result without the assumption that we are dealing with monodromy groups of polynomials (or more generally coverings with a totally ramified rational point). If r_{2} ≠ 1, it follows from the earlier discussion. This suggests that a proof may require a classification of the possibilities with r_{2} = 1. A proof along the lines of [FGS] might be feasible. Note that we already had to deal with one case with r_{2} = 1 (but the group was not 2-transitive) in the proof of the previous result. We do prove a weaker version of the previous theorem in section 5.

We conclude this section with a simple lower bound on V_{f}, which is proved in the same way as Corollary 2.5.

Proposition 3.7. Let α : X → Y be a separable covering of degree n with X, Y, α defined over F_{q}. Assume that the fiber product X ×_{Y} X has exactly one absolutely irreducible component defined over F_{q} other than the diagonal. Then V_{f} > q/2 + O(q^{1/2}).

Note that r_{2} + 1 is the number of absolutely irreducible components of the fiber product above. So the assumption in the previous proposition is equivalent to r_{2} = 1. The asymptotic result means that we let q → ∞ in such a way that the hypothesis is still satisfied (this just amounts to taking extensions relatively prime to the degree of the smallest field over which every irreducible component over an algebraic closure of F_{q} of the fiber product is defined). See [U] for a similar result.

4. Coverings with a totally ramified point

In this section, we show that for coverings of degree prime to the characteristic with a totally ramified point, an absolute positive lower bound for s_{0} can be obtained. We note that Corollary 2.4 (with an identical proof) is also valid for the more general (G, N) case.

Theorem 4.1. Let f : X → Y be an indecomposable separable covering of degree n defined over a finite field F_{q} of characteristic p. Assume that f has a totally and tamely ramified F_{q}-point (so p does not divide n). Let N be the geometric monodromy group of f and G its arithmetic monodromy group. Then one of the following holds:

(a) G is a Frobenius or regular group of degree n a prime and either (i) G ≠ N and the cover is exceptional; or (ii) G = N has order nd for some d|(n − 1) and s_{0} = (n − 1)/dn; or

(b) G and N are 3-transitive of degree n, r_{2} = r_{3} = 1 and s_{0} > 1/3; or

(c) G and N are 2-transitive of degree n, r_{2} = 1, r_{3} = 2 and s_{0} > 1/6.

Proof. Since f is indecomposable, it follows that G is primitive. Since there is a totally ramified point (and p does not divide n), N contains an n-cycle. It follows (cf. [Wi]) that G is 2-transitive or n is a prime and G′′ = 1. In the latter case, G is a Frobenius or cyclic group of order nd for some d|(n − 1). The fixed point free elements in G are precisely the n − 1 elements of order n, whence (a) holds.

So we may assume that G is 2-transitive and G′′ ≠ 1. Any 2-transitive group is either almost simple or affine. The only affine group with G′′ ≠ 1 containing an n-cycle is S_{4} (with n = 4) which is 3-transitive. If G = S_{4}, then since N contains an 4-cycle and G/N is cyclic, it follows that G = N. More generally, it follows by inspection of the 3-transitive almost simple groups that N would also be 3-transitive. Corollary 2.4 yields s_{0} > 1/3 in this case.

So finally consider the case that G is almost simple and is 2-transitive but not 3transitive containing an n-cycle. It follows by inspection (see Table 1) that r_{3} = 2 in this case. Corollary 2.4 yields s_{0} > 1/6.

We consider in some detail the case G = N is a Frobenius group of order nd with n prime or cyclic of order n with n prime. We will show that under suitable conditions that if the genus is small, then so is d. The next results are quite easy if we assume that all ramification is tame.

We first review the Riemann-Hurwitz formula. See [Ha] and [S1]. Let f : X → Y be a separable branched covering of connected smooth projective curves X and Y of degree n. Let B be the finite set of branch points (i.e. those points that ramify). Let L = F (X) and K = F (Y) be the function fields of the curves. Let g(X) and g(Y) denote the genus of X and Y. If x ∈ X, define a(x) = v(D_{x}), where D_{x} is the different of the extension L_{x}/K_{f(x)} and v is the corresponding discrete valuation on L_{x}. Let e = e(x) denote the degree of ramification. We note the following (cf. [Ha, p. 301] or [S1]):

(a) if there is no ramification, then a(x) = 0;

(b) if there is tame ramification of degree e, then a(x) = e − 1;

(c) if there is wild ramification (i.e. p|e), then a(x) ≥ e.

Set λ(y) = ∑_{x∈f^{−1}(y)} a(x). Then (cf. [Ha, p. 301])

2(g(X) − 1) = 2n(g(Y) − 1) + ∑_{y∈B} λ(y).

Let G denote the monodromy group of the cover. Let I_{y} denote an inertia group of a point over y. If there is only tame ramification over y, then I_{y} = ⟨g_{y}⟩ and λ(y) is ind(g_{y}) := n − orb(g_{y}), where orb(g) is the number of orbits of g in the associated permutation representation of degree n.

Moreover, if all points are tamely ramified (in particular, if the order of the monodromy group is not a multiple of the characteristic), then, by a result of Grothendieck (see [Gr] or [Fu]), we may order the branch points y_{1}, …, y_{r} and choose g_{i}, a generator for I_{y_{i}} such that G = ⟨g_{1}, …, g_{r}⟩ and g_{1} ⋯ g_{r} = 1. In any case, if I_{y} has orbits of size of n_{1}, …, n_{t}, then λ(y) ≥ ∑ n′_{i}, where n′_{i} = n_{i} for p|n_{i} and n′_{i} = n_{i} − 1 otherwise.

Now, in particular, assume that p ≠ n is prime and G is a Frobenius group of order nd (if d = 1, then G is cyclic) as above. Thus, every nonidentity element has at most one fixed point. So either g is an n-cycle or a product of (n − 1)/b cycles each of length b. Thus if w is a point of Y, one of the following holds:

(d) w is totally ramified and λ(w) = n − 1;

(e) w is tamely but not totally ramified and λ(w) = (b − 1)(n − 1)/b where the inertia group of a point over w has order b; or (f) w is wildly ramified and λ(w) ≥ n − 1.

In particular, if w is ramified, then λ(w) ≥ (n − 1)/2.

We will show below (Theorem 4.5) that these conditions force d small compared to g(X). In particular, if g(X) = 0, then it is quite easy to see (and follows from Proposition 4.4) that d ≤ 2 (see also [Fr1]). Indeed, the proof shows that the Galois closure also has genus zero. We state this result separately.

Lemma 4.2. Let f be a polynomial of prime degree n with n ≠ p. If the geometric monodromy group N of f is a Frobenius group, then N is either cyclic or dihedral. Moreover, the Galois closure of the cover f : ℙ^{1} → ℙ^{1} has genus zero and one of the following holds:

(a) N is cyclic and there are 2 branch points;

(b) N is dihedral, p ≠ 2 and there are 3 branch points; or

(c) N is dihedral, p = 2 and there are 2 branch points exactly one of which is wildly ramified.

Corollary 4.3. Assume that f : ℙ^{1} → ℙ^{1} is a polynomial over F_{q} of degree n with n prime to the characteristic p. If s_{0} > 0, then s_{0} > 1/6.

Proof. Since (p, n) = 1, the cover defined by f is automatically separable. Without loss of generality, we may assume that f is indecomposable over F_{q}. By Theorem 4.1, it suffices to assume that G = N is Frobenius or regular and n is prime. By Lemma 4.2, this implies that |G| = n or 2n. Then s_{0} = (n − 1)/nd ≥ (n − 1)/2n > 1/6.

In order to obtain an analog of Corollary 4.3 for curves of higher genus, we need to consider coverings with Frobenius monodromy group with a totally and tamely ramified point.

We separate out the case of two branch points since the argument is entirely different.

Lemma 4.4. Let X be a curve of genus g over an algebraically closed field F of characteristic p ≥ 0. Suppose f : X → ℙ^{1} is a separable indecomposable branched covering of prime degree n ≠ p with at most two branch points. Let g denote the genus of X. Assume that there is a branch point that is totally ramified and that the monodromy group is Frobenius of order nd (so d|(n − 1)). Then d ≤ 2g + 2 (if p ≠ 2, d ≤ g + 2).

Proof. Let C be the normal subgroup of G of order n. Let B denote a subgroup of order d. Let W denote the curve corresponding to the Galois closure of the covering. Let V denote the curve corresponding to the fixed field of C. Thus, V/ℙ^{1} is a cyclic cover of degree d. We assume that B corresponds to X in the Galois correspondence.

Of course, there are no unramified coverings of ℙ^{1}, so that there must be at least one branch point. If there is a single branch point, then p > 0 and G is generated by its Sylow p-subgroups. Since y is totally ramified, this implies that n = p, whence G has order p and d = 1.

So we assume that there are precisely two branch points and d > 1 (since there is nothing to prove if d = 1).

If both branch points are tamely ramified, then G = ⟨s, t⟩ where s and t generate inertia groups over the branch points and st = 1. Thus, G is cyclic and d = 1.

Assume y is totally ramified. Then the inertia group of a point over y is cyclic of order n, whence λ(y) = n − 1. Thus, y is tamely ramified and is not a branch point in the cover V/ℙ^{1}. It follows that V/ℙ^{1} is a cyclic cover of degree d and has single branch point z, whence d = p^{a} for some a. Moreover, the inertia group of a point in W over y is C and the inertia group of a point in W over z is conjugate to B. Let w denote the unique point of W with inertia group B (w lies over z and since B is its own normalizer, there is only one point in W with inertia group B).

Let v ∈ V and x ∈ X be the points under w (and so over z). If we complete at w, then F (W)_{w} = F (V)_{v} and F (X)_{x} = F (ℙ^{1})_{z}. We identify B with the monodromy group of the cover V/ℙ^{1}. Thus, the higher ramification groups B_{i} of v (for V/ℙ^{1}) and w (for the cover W/X) agree. Moreover, V/ℙ^{1} and W/X each are ramified at a single point (z and x respectively) and these points are totally ramified. Using the Riemann-Hurwitz formula (see also [S1, p. 64]) to compute the genus (with respect to these two Galois covers), we see that if g(V) and g(W) are the genus of V and W, then

\begin{matrix}2(g(W) − 1) = & 2d(g − 1) + ∑_{i=0}^{∞}(|B_{i}| − 1), and \\ 2(g(V) − 1) = & − 2d + ∑_{i=0}^{∞}(|B_{i}| − 1). \end{matrix}

Thus, g(W) = g(V) + dg. On the other hand, W/V is a cyclic cover of degree n with precisely d branch points each tamely ramified with inertia group C (the points over y – since the point in V over z is unramified to W). Thus,

2(g(W) − 1) = 2n(g(V) − 1) + d(n − 1), and

2dg = (2n − 2)(g(V) − 1) + d(n − 1).

Hence 2g ≥ (d − 2)(n − 1)/d ≥ d − 2 and d ≤ 2g + 2. More generally, if we factor n − 1 = p^{b}m where p does not divide m, we see that d ≤ (2/m)g + 2.

Theorem 4.5. Let f : X → Y be a branched covering of prime degree n ≠ p which is tamely and totally ramified at some point y ∈ Y. Assume that the geometric monodromy group of f is Frobenius of order nd. Let g be the genus of X and h the genus of Y. Then one of the following occurs:

(a) h > 0 and g > g − h > d/2;

(b) h = 0 = g, d ≤ 2 and the Galois closure of the cover has genus zero; or

(c) d ≤ 4g.

Proof. Note the inertia group of a point over y acts transitively (because of the total ramification). Let B denote the set of branch points. We use the observations (d)-(g) above.

If h > 0, then 2(g − h) > λ(y) = n − 1 ≥ d and (a) holds. So assume that h = 0. The Riemann-Hurwitz formula in this case is:

2(n + g − 1) = ∑_{z∈B} λ(z).

If |B| ≤ 2, the result follows from the previous lemma (since 4g ≥ 2g + 2 for g > 0). So assume that |B| ≥ 3. Note that λ(w) ≥ (n − 1)/2 for every w ∈ B. If some point

z is wildly ramified, its contribution to the Riemann-Hurwitz formula is at least n − 1, whence 2g ≥ (n − 1)/2 ≥ d/2. Thus, d ≤ 4g.

Similarly, if |B| ≥ 4, it follows that ∑ λ(w) ≥ 3(n − 1)/2 + (n − 1). Hence, the Riemann-Hurwitz formula yields 2g ≥ (n − 1)/2 ≥ d/2. and again we obtain d ≤ 4g.

So we may assume that there are three branch points and no wild ramification. Let y = y_{1}, y_{2}, y_{3} denote the branch points. Thus, G = ⟨g_{1}, g_{2}, g_{3}⟩ where g_{1}g_{2}g_{3} = 1 with g_{i} a generator of an inertia group over y_{i}. Since g_{1} has order n, it generates the normal subgroup C of G. Thus, G/C is generated by the image of g_{2} and g_{3} maps to its inverse. Hence g_{2} and g_{3} each have order d. Thus λ(y_{1}) = n − 1 and λ(y_{2}) = λ(y_{3}) = (d − 1)(n − 1)/d. It follows that 2g = 2(d − 1)(n − 1)/d − (n − 1) = (n − 1)(d − 2)/d ≥ d − 2. Thus, d ≤ 2g + 2.

In particular, if g = 0, it follows that d ≤ 2. Another application of the Riemann-Hurwitz formula shows that the Galois closure has genus 0.

Corollary 4.6. Let f : X → Y be a branched covering of degree n > 1 with n prime to p which is totally ramified at some F_{q}-rational point y. Let g denote the genus of X. If s_{0} > 0, then s_{0} > 1/6 for g ≤ 1 and s_{0} ≥ 3/14g for g > 1.

Proof. Since s_{0} ≥ 1/n, we may assume that n ≥ 7. Without loss of generality, we may assume that f is indecomposable. By Theorem 4.1, we may further assume that G = N is a Frobenius group of order nd or cyclic group of n (i.e. d = 1) with n prime and so s_{0} = (n − 1)/dn. If g = 0, then d ≤ 2 by Theorem 4.5, whence the result. If g ≥ 1, again by Theorem 4.5, d ≤ 4g. Then s_{0} ≥ (n − 1)/4gn ≥ 3/14g. If g = 1, this is larger than 1/6.

Remarks. We do not know if the bound in the previous result is best possible. It is straightforward to see that if p does not divide n(n − 1) with n > 2 prime, then we may realize the Frobenius group of order n(n − 1) and degree n as a group of automorphisms of a curve of genus g = (n − 3)/2, whence s_{0} = 1/n is approximately 1/2g.

As we have seen, if we do not assume that n is prime to the characteristic, then the result is false. There should be some version of the previous result where for example the bound depends only the power of p dividing n. An analysis of the possible monodromy groups for polynomials will be required (see [GS]).

We can improve Corollary 4.3 slightly if we assume that all ramification is tame (not just ramification over ∞). This essentially follows from the Feit-Müller classification of monodromy groups of indecomposable polynomials in characteristic zero and Grothendieck’s theorem (that a tamely ramified cover has a branch cycle description as in the characteristic zero case).

Theorem 4.7. Let f : ℙ^{1} → ℙ^{1} be an indecomposable polynomial of degree n defined over a finite field F_{q} of characteristic p. Assume that all ramification is tame (in particular, p does not divide n). Let N be the geometric monodromy group of f and G its arithmetic monodromy group. Then one of the following holds:

(a) n ≤ 23 and N is triply transitive;

(b) n is prime, G = N is cyclic of order n and s_{0} = (n − 1)/n;

(c) n is prime, G = N is dihedral of order 2n and s_{0} = (n − 1)/2n;

(d) n is prime, N is cyclic of order n or dihedral of order 2n, N ≠ G and f is exceptional;

(e) G = N and (i) n = 11 and G = L_{2}(11); (ii) n = 13 and G = P GL_{3}(3); (iii) n = 15 and G = A_{8}; (iv) n = 21 and G = P ΓL_{3}(4);

(v) n = 31 and G = L_{5}(2);or

(f) A_{n} ⊆ N ⊆ G ⊆ S_{n}.

Proof. By Grothendieck [Gr], we have that N will occur as the monodromy group of an indecomposable polynomial cover over ℂ. All such possibilities have been classified in [Mü] (see also [Fe]).

Corollary 4.8. Let f : X → Y be a polynomial covering of degree n defined over a finite field F_{q} of characteristic p. Assume that all ramification is tame (in particular, p does not divide n). Then either s_{0} = 0 or s_{0} ≥ 16/63.

Proof. As usual, we may assume that f is indecomposable. We apply the previous result. If N is 3-transitive, then s_{0} ≥ 1/3. The bound clearly holds for N cyclic or dihedral. So we are left only to verify the bound in (e) above. This is an easy calculation using [ATLAS].

Note that 16/63 occurs when n = 21 and G = N = P ΓL_{3}(4). Thus, the bound is best possible in the previous result.

5. Higher dimensional varieties

In this section, we briefly discuss some generalizations of the previous curve results to higher dimensional varieties in the setting of [Se2, Theorem 3.6.2].

Let Y and Z be two m-dimensional absolutely irreducible (quasi-projective) varieties defined over F_{q}. Let f : Y ⟶ Z be a generically surjective and separable morphism of degree n defined over F_{q}, where n is a positive integer. The map f is actually a finite map if we remove suitable co-dimension 1 subvarieties from Y and Z. Let D be the (quasiprojective) variety defined by the fiber product Y ×_{Z} Y with its diagonal removed. The variety D over F_{q} is also at most m-dimensional if f is finite. The set D(F_{q}) consists of the pairs (P_{1}, P_{2}) of F_{q}-rational points in Y (F_{q}) such that P_{1} ≠ P_{2} and f(P_{1}) = f(P_{2}). Let V_{f} be the cardinality of the value set f(Y (F_{q})).

Theorem 5.1. If f is a finite map, then we have the inequality

V_{f} ≤ |Y (F_{q})| − \frac{|D(F_{q})|}{n}.  (5.1)

Proof. Since f is a finite map of degree n, for each point P ∈ Z, the inverse image f^{−1}(P) has cardinality at most n. For 0 ≤ i ≤ n, let s_{i} be the number of F_{q}-rational points P ∈ Z(F_{q}) such that f^{−1}(P) ∩ Y (F_{q}) has cardinality i. By this definition, one then checks directly that

(2 − 1)s_{2} + (3 − 1)s_{3} + ⋯ + (n − 1)s_{n} = |Y (F_{q})| − V_{f}.  (5.2)

and

2(2 − 1)s_{2} + 3(3 − 1)s_{3} + ⋯ + n(n − 1)s_{n} = |D(F_{q})|.  (5.3)

Multiply equation (5.2) by n and subtract (5.3), we deduce that

n(|Y (F_{q})| − V_{f}) − |D(F_{q})| = ∑_{j=2}^{n−1}(n − j)(j − 1)s_{j} ≥ 0.  (5.4)

This immediately gives (5.1). The proof is complete.

Definition 5.2. A finite and separable morphism f : Y ⟶ Z is called exceptional over F_{q} if the variety D as above has no absolutely irreducible components of (top) dimension m defined over F_{q}. A generically surjective and separable morphism f : Y ⟶ Z as above is called exceptional if its restriction to some dense open set is a finite and exceptional map.

Theorem 5.3. Let f : Y ⟶ Z be a generically surjective and separable morphism of degree n, where Y and Z are absolutely irreducible m-dimensional F_{q}-varieties. (i). If f is not exceptional over F_{q}, then

V_{f} ≤ (1 − \frac{1}{n})q^{m} + O(q^{m−1/2}).  (5.5)

(ii). If f is exceptional over F_{q}, then

|D(F_{q})| = O(q^{m−1}), V_{f} = q^{m} + O(q^{m−1/2}).  (5.6)

Proof. Since any variety of dimension m−1 over F_{q} has at most O(q^{m−1}) rational points over F_{q}, by restricting to suitable dense open subsets of Y and Z, we may assume that f is a finite map. Thus, we may assume that the variety D has dimension at most m.

In case (i), the non-exceptionality of f shows that the variety D has at least one absolutely irreducible component of dimension m defined over F_{q}. The Lang-Weil estimate (a special case of Lemma 5.5 below) shows that

|Y (F_{q})| = q^{m} + O(q^{m−1/2}), |D(F_{q})| ≥ q^{m} + O(q^{m−1/2}).

Combining with (5.1), we deduce (5.5).

In case (ii), the exceptionality of f shows that the variety D has no absolutely irreducible components of top dimension m defined over F_{q}. Thus, each F_{q}-rational point on D (except those on some co-dimension 1 subvariety of D) is contained in an intersection of two distinct geometric components of D. Such an intersection has dimension at most m − 1. Thus, the set D(F_{q}) of all F_{q}-rational points on D is contained in the set of F_{q}-rational points of some variety of dimension at most m − 1. The Lang-Weil estimate shows that

|D(F_{q})| = O(q^{m−1}).

This is the first equation of (5.6). Combining with equation (5.3) , one deduces that s_{i} = O(q^{m−1}) for all 2 ≤ i ≤ n. By (5.4), we then conclude that

V_{f} = |Y (F_{q})| + O(q^{m−1}) = q^{m} + O(q^{m−1/2}).  (5.7)

Remarks. If f is exceptional over F_{q}, the crude estimate |D(F_{q})| = O(q^{m−1}) in (5.6) can be greatly improved in some cases. For example, if Y and Z are absolutely irreducible nonsingular projective curves over F_{q} and f : Y ⟶ Z is exceptional over F_{q} (automatically finite in this case), it is shown in [Le] (already in [FGS] if Z = ℙ^{1}) that |D(F_{q})| = 0. More general, it is shown in [Le] that |D(F_{q})| = 0 for exceptional f if one assumes some natural conditions such as that the map f is finite and that the varieties Y and Z are normal. See also [Fr3] for earlier results of this nature.

Similarly, the second estimate in (5.6) can also be improved in some cases. For instance, using Lenstra’s result as above and Deligne’s theorem on Riemann hypothesis, one derives immediately that

V_{f} = \frac{q^{m+1} − 1}{q − 1} + O(q^{m/2}),

if f is an exceptional finite map, Y is a smooth projective complete intersection and Z is normal.

A similar inclusion-exclusion argument as in (2.11) and the Lang-Weil estimate shows that Proposition 3.7 carries over to higher dimensional case. We state this generalization here.

Proposition 5.4. Let f : Y ⟶ Z be a generically surjective and separable map between two absolutely irreducible varieties over F_{q}. Assume that the variety D has exactly one absolutely irreducible component of dimension m, then

V_{f} > \frac{1}{2}q^{m} + O(q^{m−1/2}).

To extend other curve results stated in the introduction, we shall need to use group theory. This can be done exactly as the curve case because of the following asymptotic formula, which is an immediate consequence of the higher dimensional Cebotarev density theorem [Fr2].

Lemma 5.5. Let f : Y ⟶ Z be a generically surjective and separable morphism between absolutely irreducible m-dimensional varieties Y and Z defined over F_{q}. Let G (resp. N) be the arithmetic (resp. geometric) monodromy group of the map f. Let xN be the coset which is the Frobenius generator of the cyclic group G/N. Then, we have the formula for the value set cardinality V_{f} = |f(Y (F_{q}))|:

V_{f} = (1 − s_{0})q^{m} + O(q^{m−1/2}),

where s_{0} = |S_{0}|/|N| and S_{0} is the set of fixed point free elements in xN as before.

In the special case Y = Z and f is the identity map (thus s_{0} = 0), the above lemma reduces to the well known Lang-Weil estimate. By Theorem 1.3, we obtain

Corollary 5.6. Let f : Y ⟶ Z be a generically surjective and separable map of degree n between two m-dimensional absolutely irreducible varieties over F_{q}. Assume that the covering is not exceptional and that the Galois closure of the covering is regular (G = N). Assume further that the monodromy group is not a Frobenius group of order n(n − 1). Then for n > 6, we have

V_{f} ≤ (1 − \frac{2}{n})q^{m} + O(q^{m−1/2}),

with equality holding (asymptotically) if and only if G = N is a Frobenius group of order n(n − 1)/2.

Clearly, stronger results such as Theorem 1.2 can also be extended to some higher dimensional cases for regular coverings with suitable total and tame ramification assumptions. We can prove a slightly weaker version of Theorem 1.1 that applies to higher dimensional varieties and to curves without assuming the existence of a totally ramified point. We are certain that 5/4 can be replaced by 2 in the next result.

Corollary 5.7. Let f : Y ⟶ Z be a generically surjective and separable map of degree n between two m-dimensional absolutely irreducible varieties over F_{q}. Assume that the covering is not exceptional and that the monodromy group is not Frobenius of order n(n− 1). Then for n > 6,

V_{f} ≤ (1 − \frac{5}{4n})q^{m} + O(q^{m−1/2}).

Proof. We argue as in the proof of Theorem 3.6. We may assume that f is indecomposable as a cover. Let G and N be the corresponding monodromy groups acting transitively on the corresponding set X. By Lemma 5.5, it suffices to prove that s_{0} ≥ 5/4n.

By [LS], it follows that μ > n/3 unless E := F^{∗}(G) = L_{1} × … × L_{t}, where each L_{i} ≅ A_{ℓ}, the alternating group of degree ℓ (with ℓ ≥ 5). Moreover, we may assume that in the latter case that the stabilizer in E of a point is the product of stabilizers of k-sets for some k with 1 ≤ k < ℓ/2.

If μ > n/3, then arguing as in section 2, we deduce that s_{0} ≥ 5/4n (use the analog of 2.9).

Consider the remaining situation. If N not transitive on the set of L_{i} (by conjugation), then any element of xN (where xN generates G/N) will not normalize each L_{i}. It follows that any element of xN fixes at most n/5 points, and we can argue as in the previous paragraph (because we only need to know the minimal degree for elements in the coset xN).

If N is transitive on the L_{i}, then it is straightforward to compute that r_{2} ≥ 2 unless t = 1 = k. Then, N is 3-transitive and s_{0} ≥ 1/6.

References

[ATLAS] An Atlas of Finite Groups, J. Conway, R. Curtis, S. Norton, R. Parker and R. Wilson,

Oxford U. Press, Oxford, 1985.

[BS] B.J. Birch and H.P.F. Swinnerton-Dyer, Note on a problem of Chowla, Acta Arith., V(1959), 417-423.

[Bo] N. Boston, W. Dabrowski, T. Foguel, P.J. Gies, J. Leavitt, D.T. Ose, and D.A. Jackson, The proportion of fixed-point-free elements of a transitive permutation group, Comm. in Algebra, 21(9), 3259-3275(1993).

[BLP] J.P. Buhler, H. W. Lenstra, Jr. and C. Pomerance, Factoring integers with the number field sieve, in “The Development of The Number Field Sieve”, Lecture Notes in Math., 1554.

[CC] P. J. Cameron and A. M. Cohen, On the number of fixed point free elements in a permutation group, Annals of Discrete Math. 106/107 (1992), 135-138.

[Ch] S. Chowla, The Riemann zeta and allied functions, Bull. Amer. Math. Soc., 58(1952), 287-303.

[Co] S.D. Cohen: The distribution of polynomials over finite fields, Acta Arith. 17 (1970), 255-271.

[Fe] W. Feit, On symmetric balanced incomplete block designs with doubly transitive automorphism groups, J. Comb. Theory Ser. A 14 (1973), 221-247.

[Fr1] M. Fried, On a conjecture of Schur, Mich. Math. J. 17 (1970), 41-55.

[Fr2] M. Fried, On Hilbert’s irreduciblity theorem, J. Number Theory, 6(1974), 211-232.

[Fr3] M. Fried, On a theorem of MacCluer, Acta Arith. 25 (1973/74), 121-126.

[FGS] M. Fried, R. Guralnick and J. Saxl, Schur covers and Carlitz’s conjecture, Israel J.

Math. 82 (1993), 157-225.

[Fu] W. Fulton, Hurwitz schemes and irreducibility of moduli of algebraic curves, Annals of Math. 90 (1969), 542-575.

[Gr] A. Grothendieck, Revêtement étales et groupe fondamental (SGA1), Lecture Notes in Math. # 224, Springer-Verlag, New York-Heidelberg, Berlin, 1971.

[GS] R. Guralnick and J. Saxl, Monodromy groups of polynomials, in Groups of Lie Type and their Geometries, W. Kantor and L. Di Martino, eds, Cambridge University Press, Cambridge, 1995, 125-150.

[Ha] R. Hartshorne, Algebraic Geometry, Springer-Verlag, New York-Heidelberg-Berlin, 1977.

[HB] B. Huppert and N. Blackburn, Finite Groups III, Springer-Verlag, New York-Heidelberg-Berlin, 1982.

[Jo] C. Jordan, Recherches sur les substitutions, J. Liouville, 17(1872), 351-367 (Oeuvres, I, no.52).

[Ka] W. Kantor, Homogeneous designs and geometric lattices, J. Combinatorial Theory, Series A 38 (1985), 66-74.

[Le] H.W. Lenstra Jr., personal communication.

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

[Mc] J. McLaughlin, Some subgroups of SL_{n}(F_{2}) generated by transvections, Illinois J. Math. 13 (1969), 108-115.

[Mu] G.L. Mullen, Permutation polynomials over finite fields, in “Finite Fields, Coding Theory and Advances in Communications and Computing”, edited by G.L. Mullen and P.J.S. Shiue, Marcel Dekker, 1993, 131-151.

[Mü] P. Müller, Primitive monodromy groups of polynomials, Recent Developments in the inverse Galois problem (Seattle, WA 1993), 385-401, Contemp. Math. 186, Amer. Math. Soc., Providence, RI, 1995.

[Pa] D. Passman, Permutation Groups, W. A. Benjamin, Inc., New York, Amsterdam, 1968.

[S1] J-P. Serre, Local Fields, GTM 67, Springer-Verlag, 1979.

[S2] J-P. Serre, Topics in Galois Theory, Jones and Bartlett Publishers, 1992.

[Tu] G. Turnwald, A new criterion for permutation polynomials, Finite Fields Appl. 1 (1995), 64-82.

[U] S. Uchiyama, Sur le nombre des valeurs distinctes d’un polynôme a coefficients dans un corps fini, Proc. Japan Academy 30 (1954), 930-933.

[Wa] D. Wan, A p-adic lifting lemma and its application to permutation polynomials, in “Finite Fields, Coding Theory and Advances in Communications and Computing”, edited by G.L. Mullen and P.J.S. Shiue, Marcel Dekker, 1993, 209-216.

[Wi] H. Wielandt, Finite Permutation Groups, Academic Press, New York, 1964.