DAVENPORT PAIRS OVER FINITE FIELDS

WAYNE AITKEN, MICHAEL D. FRIED^{∗}, LINDA M. HOLT

Abstract. A pair of polynomials f, g ∈ 𝔽_{q}[T] is called a Davenport pair (DP) if their value sets are equal, V_{f} (𝔽_{q^{t}}) = V_{g}(𝔽_{q^{t}}), for infinitely many extensions of 𝔽_{q}. If they are equal for all extensions of 𝔽_{q}, i.e., for all t ≥ 1, then we say that (f, g) is a strong Davenport pair (SDP). One may consider exceptional polynomials and SDP’s as special cases of DP’s. Exceptional polynomials and SDP’s have been successfully studied using monodromy/Galois-theoretic methods. We use these methods to study DP’s in general, and analogous situations for inclusions of value sets.

For example, if (f, g) is a SDP, then f(T) − g(S) ∈ 𝔽_{q}[T, S] is known to be reducible. This has interesting consequences. We extend this to DP’s (that are not pairs of exceptional polynomials) and use reducibility to study the relationship between DP’s and SDP’s when f is indecomposable. Additionally, we show that if (f, g) is a DP, then (deg f, q^{t} − 1) = (deg g, q^{t} − 1) for all sufficiently large q^{t} with V_{f} (𝔽_{q^{t}}) = V_{g}(𝔽_{q^{t}}). This extends Lenstra’s theorem (Carlitz-Wan conjecture) concerning exceptional polynomials.

1. Introduction

Let 𝔽_{q} be a finite field with q elements, and let p denote its characteristic. For any f ∈ 𝔽_{q}[T] and finite extension 𝔽_{q^{t}} of 𝔽_{q}, define the value set V_{f}(𝔽_{q^{t}}) to be {f(a) | a ∈ 𝔽_{q^{t}}}. Call (f, g) a Davenport pair over 𝔽_{q} if V_{f}(𝔽_{q^{t}}) = V_{g}(𝔽_{q^{t}}) for infinitely many values of t. For brevity, we use the acronym DP. We will see that (f, g) is automatically a Davenport pair (DP) if V_{f}(𝔽_{q^{t}}) = V_{g}(𝔽_{q^{t}}) for one sufficiently large value of t. Call (f, g) a strong Davenport pair (SDP) over 𝔽_{q} if V_{f}(𝔽_{q^{t}}) = V_{g}(𝔽_{q^{t}}) for all t ≥ 1.

Davenport pairs are named in honor of H. Davenport, who, in the 1960’s, was interested in a characteristic zero analogue of what we call SDP’s. He asked which pairs (f, g) ∈ ℚ[T] have value sets mod l which are equal for almost all primes l. (See Section 3.2 below for more details.)

Call f ∈ 𝔽_{q}[T] an exceptional polynomial if V_{f}(𝔽_{q^{t}}) = 𝔽_{q^{t}} for infinitely many values of t. So f is exceptional if and only if (f, T) is a DP. Thus both SDP’s and exceptional polynomials are special types of Davenport pairs. We are interested in the relationship between Davenport pairs on the one hand, and strong Davenport pairs and exceptional polynomials on the other.

For example, if (f, g) is a SDP and (h_{1}, h_{2}) is a pair of exceptional polynomials, then (f ∘ h_{1}, g ∘ h_{2}) is a DP. Such DP’s have equal value sets over the base field 𝔽_{q}, a property not possessed by all DP’s. However, consider the following.

Question 1.1. Suppose (f, g) is a DP over 𝔽_{q} where

Date: November 9, 2001.

Key words and phrases. Davenport pairs, Strong Davenport pairs, Monodromy groups, value sets, permutation representations.

∗ #DMS-9970676 and a senior research Alexander von Humboldt award.

(1.1) q is sufficiently large and V_{f}(𝔽_{q}) = V_{g}(𝔽_{q}). When is there a pair of exceptional polynomials (h_{1}, h_{2}) and a SDP (f′, g′) such that f = f′ ∘ h_{1} and g = g′ ∘ h_{2}?

Remark 1.2. In the above question, sufficiently large means that q is larger than a bound depending on the degrees of f and g. Later we introduce the set D_{f,g} which allows us to replace (1.1) above with the more natural hypothesis 1 ∈ D_{f,g} (making the question meaningful even for small q).

We now describe the main results of this paper and their relationships to the decomposition hypothesis, the heuristic principle that all DP’s satisfying (1.1) have the decomposition described in the above question, or at least behave as if they did.

If (f, g) is a SDP with deg f > 1, then f(T) − g(S) ∈ 𝔽_{q}[S, T] is reducible. It follows that f ∘ h_{1}(T) − g ∘ h_{2}(S) ∈ 𝔽_{q}[S, T] is also reducible for any pair (h_{1}, h_{2}). So the decomposition hypothesis suggests the following result (Theorem 4.8 and Corollary 4.12). If (f, g) is a DP satisfing (1.1), and f is not an exceptional polynomial, then f(T) − g(S) ∈ 𝔽_{q}[S, T] reducible over 𝔽_{q}.

As another example, consider the following theorem of Lenstra [CF95], conjectured by Carlitz and Wan. If f ∈ 𝔽_{q}[T] is exceptional, then gcd(deg f, q − 1) = 1. It is also known that if (f, g) is a SDP, and if the degrees of f and g are prime to the characteristic p, then deg f = deg g. Thus if f = f′ ∘ h_{1} and g = g′ ∘ h_{2} where (f′, g′) is a SDP, (h_{1}, h_{2}) is a pair of exceptional polynomials, and deg f and deg g are prime to p, then gcd(deg f, q − 1) = gcd(deg g, q − 1). The decomposition hypothesis suggests that this holds for all DP’s satisfying (1.1). This turns out to be true; it is a consequence of our Theorem 5.4 (which is stronger since it makes no assumption on the degrees of f and g).

Finally, consider our Theorem 8.1, a result consistent with the decomposition hypothesis. Suppose that (f, g) is a DP, and that f is indecomposable. Suppose also that f has degree prime to the characteristic p, and is neither an exceptional polynomial nor linearly related to a cyclic polynomial. Then g = g′∘h for some SDP (f, g′).

We end this introduction with more questions related to DP’s.

Question 1.3. If (h_{1}, h_{2}) is a pair of polynomials such that (f ∘ h_{1}, g ∘ h_{2}) is a DP for all SDP’s (f, g), must h_{1} and h_{2} be exceptional polynomials?

Other questions involve multiplicities of values. Call (f, g) a DP with multiplicity if there are an infinite number of values of t such that f and g not only have the same value sets over 𝔽_{q^{t}}, but the values occur with the same multiplicities. In other words, f(T) − b and g(T) − b have the same number of roots in 𝔽_{q^{t}} for each b ∈ 𝔽_{q^{t}}. Similarly, call (f, g) a SDP with multiplicity if the multiplicity condition occurs for all values of t.

Question 1.4. Are there SDP’s which are not SDP’s with multiplicity? Are there DP’s which are not DP’s with multiplicity?

The characteristic zero analogue of the first part of this question has been considered. In [Mül98, Conjecture 5.2], Muller conjectures a negative answer (pairs of Kronecker conjugate polynomials are conjectured to be arithmetically equivalent).

The first author would like to thank M. Zieve and R. Guralnick for helpful discussions, and MSRI and UCI for their support and hospitality.

1.1. The Broader Context. A polynomial f ∈ 𝔽_{q}[T] gives an algebraic map f : 𝔸^{1} → 𝔸^{1}, or, by adding points at infinity, an algebraic map f : ℙ^{1} → ℙ^{1}. Our approach, via the arithmetic and geometric monodromy groups associated with the map f, or pairs of maps (f, g), extends considerably to include maps between algebraic curves defined over 𝔽_{q}, and even to finite maps between higherdimensional varieties. However, we concentrate on polynomial maps. More can be proven for such maps since they have a totally ramified point, infinity, and the maps are between curves of genus zero. Also, limiting the exposition to polynomials contributes to its clarity. However, the reader should be aware of the possibilities, and the challenges of extending beyond polynomial maps.

Some readers may also be interested in the link between Davenport pairs and such topics as Weil vectors, Galois stratification, and Chow motives. Here, a Weil vector is the sequence of coefficients of a Poincaré series associated to a numbertheoretic counting problem. For example, if V is a projective variety over 𝔽_{q}, we get the familiar Weil vector N = (N_{1}, N_{2}, …) where N_{t} is the number of 𝔽_{q^{t}}- rational points of V. The associated Poincaré series is P_{V} (X) = ∑_{t=1}^{∞} N_{t}X^{t}, and the associated zeta function is Z_{V} (X) = exp (∑_{t=1}^{∞} N_{t}X^{t}/t).

Weil vectors also arise from other counting problems. For example, let V be a scheme (reduced, separated) of finite type over ℤ. Consider the Weil vector N = (N_{1}, N_{2}, …) where N_{t} is the number of ℤ/p^{t}-rational points which lift to ℤ_{p}- rational points. The rationality of the associated Poincaré series was established by Denef [Den84].

Galois stratification is a tool for producing Weil vectors in a wide variety of counting problems (see [FS76] and [FJ86]). Denef and Loeser ([DL]) have recently shown that there is a vital link between Galois stratification and Chow motives. Given two Weil vectors N = (N_{1}, N_{2}, …) and N′ = (N′_{1}, N′_{2}, …), the characteristic set χ(N , N′) is {t ∈ ℕ^{+}|N_{t} = N′_{t}}. Such characteristic sets, when the Weil vectors arise from Galois stratification, form Frobenius progressions (Definition 4.5).

To consider the link between DP’s and these topics, consider your favorite equation Φ(T, U) = 0 where Φ ∈ 𝔽_{q}[T, U] and U = (U_{1}, …, U_{s}). Consider also the Weil vector N (Φ) = (N_{1}(Φ), N_{2}(Φ), …) where N_{t}(Φ) is the number of solutions over 𝔽_{q^{t}}. You often substitute a polynomial or rational function f(T) for T to get the related equation Φ(f(T), U) = 0. Write Φ_{f} for Φ(f(T), U). Let (f, g) be a pair of polynomials, and let χ(f, g) be the set of t with the property that V_{f}(𝔽_{q^{t}}) and V_{g}(𝔽_{q^{t}}) are equal, and every value occurs with the same multiplicity. We assume χ(f, g) is infinite. In other words, (f, g) is a DP with multiplicity. Observe that χ(f, g) ⊆ χ(N (Φ_{f}), N (Φ_{g})).

This gives us a procedure for generating non-trivial (i.e., non-finite) characteristic sets relating many different pairs of Weil vectors. The resulting characteristic sets must contain a common Frobenius progression χ(f, g) regardless of your choice of favorite equation. This suggests the importance of the the study of Frobenius progressions of the form χ(f, g) from the more general Weil vector viewpoint.

To study the collection of such sets χ(f, g), one might wish to generate infinite subsets of the same form using, say, exceptional polynomials. If h ∈ 𝔽_{q}[T] is exceptional, let E_{h} be the set of t where h : 𝔽_{q^{t}} → 𝔽_{q^{t}} is bijective (E_{h} = χ(h, T) where T is the identity polynomial). Suppose (f, g) is a DP and h_{1} and h_{2} are exceptional. Then, χ(f ∘ h_{1}, g ∘ h_{2}) contains E_{h_{1}} ∩ E_{h_{2}} ∩ χ(f, g). You must know something about E_{h_{1}}, E_{h_{2}}, χ(f, g) to say their intersection is infinite. We see later that E_{h_{1}} ∩E_{h_{2}} ∩χ(f, g) is automatically infinite if f and g are indecomposable with degree prime to p and not linearly related to cyclic polynomials (Theorem 8.1).

2. Notations and conventions

We note that (f(T), f(T^{p})) is a SDP (as above, f ∈ 𝔽_{q}[T], and p is the characteristic of 𝔽_{q}). So, for value set problems, it is harmless to replace any polynomial of the form f(T^{p}) by f(T). By repeating this process starting with a given polynomial, we obtain a polynomial whose derivative is not the zero polynomial, and whose value set, in all finite extensions, is the same as the original polynomial. This justifies the following convention: all polynomials appearing in this paper will be assumed to have non-zero derivatives.

Let F be a field. We are most interested in F = 𝔽_{q} especially when we are considering value sets, but many of our results hold for more general F. Fix an algebraic closure \overline{F (z)} of F (z) where z is a fixed transcendental element over F, and regard \overline{F} as a subfield of \overline{F (z)}. We use the letter T (as above) for a general transcendental element not in \overline{F (z)}. We use S and T when we need two independent transcendental elements (neither in \overline{F (z)}).

For any f ∈ F [T], let Ω_{f} ⊆ \overline{F (z)} be the splitting field of f(T)−z. Since f(T) − z has z-degree 1, it is irreducible in F (z)[T]. It is also separable (the derivative f′ is assumed not to be the zero polynomial). Call Ĝ_{f} = Gal(Ω_{f}/F (z)) the arithmetic monodromy group of f. Let F̂_{f} = Ω_{f} ∩ \overline{F}. Call G_{f} = Gal(Ω_{f}/F̂_{f}(z)) ⊆ Ĝ_{f} the geometric monodromy group. Let n = deg(f), and let {x_{1}, x_{2}, …, x_{n}} be the roots of f(T) − z in Ω_{f}. If H is Ĝ_{f} or a subgroup, denote the elements of H which fix x_{i} by H(x_{i}). For example, Ĝ_{f}(x_{i}) = Gal(Ω_{f}/F (x_{i})).

Think of f ∈ F [T] as an algebraic map f : 𝔸^{1} → 𝔸^{1}. By adding a point at infinity, also regard a polynomial (or rational function) as an algebraic covering map f : ℙ^{1} → ℙ^{1}.

Now consider the case F = 𝔽_{q}. Here we abuse notation and write 𝔽̂_{f} for F̂_{f}. The quotient Ĝ_{f}/G_{f} is isomorphic to the cyclic group Gal(𝔽_{q^{d}}/𝔽_{q}) where d = [𝔽̂_{f} : 𝔽_{q}]. Not only is Gal(𝔽_{q^{d}}/𝔽_{q}) cyclic, but it is canonically isomorphic to ℤ/d by the map sending the Frobenius automorphism a ↦ a^{q} to 1. Let Ĝ_{f,t} be the G_{f}-coset of elements σ ∈ Ĝ_{f} for which σ|𝔽̂_{f} is the map a ↦ a^{q^{t}}. So Ĝ_{f,t} consists of elements

of Ĝ_{f} whose image in ℤ/d is congruent to t. Thus Ĝ_{f,t} depends only on t modulo d.

Now consider analogous definitions for pairs of polynomials (f, g), first for a general field F. Let Ω_{f,g} = Ω_{f} · Ω_{g} ⊆ \overline{F (z)} be the splitting field of the product (f(T) − z)(g(T) − z). Let F̂_{f,g} = Ω_{f,g} ∩ \overline{F}. Define the arithmetic monodromy group of the pair as Ĝ_{f,g} = Gal(Ω_{f,g}/F (z)) and the geometric monodromy group as G_{f,g} = Gal(Ω_{f,g}/F̂_{f,g}(z)).

Let {x_{1}, x_{2}, …, x_{n}} be the roots of f(T) − z, and {y_{1}, y_{2}, …, y_{m}} be the roots of g(T) − z. Then Ĝ_{f,g} acts on {x_{i}}, {y_{j}}, and the cartesian product {x_{i}} × {y_{j}}. For H equal to Ĝ_{f,g} or a subgroup, H(x_{i}), H(y_{j}), and H(x_{i}, y_{j}) have the usual meanings as stabilizer subgroups.

Note that Ĝ_{f,g} is the fiber product of Ĝ_{f} and Ĝ_{g} over the common quotient group Gal(Ω_{f} ∩ Ω_{g}/F (z)).

Now consider the case F = 𝔽_{q}. We abuse notation and write 𝔽̂_{f,g} for F̂_{f,g}. As before, we have the exact sequence

1 → G_{f,g} → Ĝ_{f,g} → ℤ/d → 1

where d = [𝔽̂_{f,g} : 𝔽_{q}]. Define Ĝ_{f,g,t} as the elements of Ĝ_{f,g} mapping to t mod d. So Ĝ_{f,g,t} is the G_{f,g}-coset of all σ whose restriction to 𝔽_{q^{d}} is the automorphism x ↦ x^{q^{t}}.

We again consider a general field F. Call f ∈ F [T] decomposable over F if f = f_{1} ∘f_{2} with f_{1}, f_{2} ∈ F [T], deg(f_{i}) > 1, i = 1, 2. Otherwise, f is indecomposable over F.

If f, l_{1}, l_{2} ∈ F [T] are polynomials with deg l_{1} = deg l_{2} = 1, then we say f and l_{1} ∘ f ∘ l_{2} are linearly related over F. Linearly related polynomials have isomorphic monodromy groups and equivalent actions of their monodromy groups on their respective root sets.

When comparing value sets, we are interested in a special type of linearly related polynomial pairs. If f, l ∈ F [T] are polynomials such that deg l = 1, then we say that f and f ∘ l are linearly related on the inside over F. For example, a pair of polynomials f, g ∈ 𝔽_{q}[T] linearly related on the inside over 𝔽_{q} clearly forms a SDP. We call such SDP’s trivial. As explained in the next section, there are examples of nontrivial SDP’s.

If n is a positive integer then we consider the statement n is prime to the characteristic of F to be vacuously true if F has characteristic zero.

3. Review of Earlier Results

We summarize some of what is known concerning value sets, exceptional polynomials, SDP’s, and DP’s.

3.1. Value Sets from the Monodromy Point of View. Consider a polynomial map as a covering map f : ℙ^{1} → ℙ^{1}. Suppose b ∈ 𝔽_{q^{t}} = 𝔸^{1}(𝔽_{q^{t}}) is not a branch point for this map. Then b ∈ V_{f}(𝔽_{q^{t}}) if and only if the associated Frobenius element Frob_{t}(b) ∈ Ĝ_{f} fixes at least one root of f(T) − z. Further, the number of a ∈ 𝔽_{q^{t}} satisfying f(a) = b is equal to the number of fixed points of Frob_{t}(b) acting on the roots {x_{i}}. We call this fact the Frobenius Principle, and note that it follows from an early result of Artin ([Art23], Section 2).

Here Frob_{t}(b) is i (\frac{Ω_{f} ·𝔽_{q^{t}} /𝔽_{q^{t}} (z)}{P_{b}}) where P_{b} is the place of 𝔽_{q^{t}}(z) associated to

b ∈ 𝔸^{1}(𝔽_{q^{t}}), (\frac{L/K}{P} ) is the Artin symbol, and i : Gal(Ω_{f} · 𝔽_{q^{t}}/𝔽_{q^{t}}(z)) → Ĝ_{f} is the natural inclusion induced by restriction. The Artin symbol is defined up to conjugacy, so the number of fixed points of Frob_{t}(b) is well-defined.

Observe that Frob_{t}(b) ∈ Ĝ_{f,t}. Conversely, the Chebotarev Density Theorem implies that the proportion of b ∈ 𝔽_{q^{t}} with Frob_{t}(b) in a given conjugacy class C ⊆ Ĝ_{f,t} is approximately proportional to the size of C. More precisely, if p(C) is the proportion of b ∈ 𝔽_{q^{t}} with Frob_{t}(b) ∈ C, b not a branch point, then

|p(C) − \frac{|C|}{|Ĝ_{f,t}|}| < B|C|q^{−t/2}.

The best B depends on f, but we can find a B depending only on n = deg f. For example, the bound of Proposition 5.16 of [FJ86], specialized to the current situation, gives B = 4(g + 2) where g is the genus of Ω_{f}. There is a bound in n for this genus g, and hence B. (By Riemann-Hurwitz, bounding g is related to bounding the different divisor for Ω_{f}/𝔽̂_{f}(z), which in turn is related to bounding the sizes of higher ramification groups. Use the corollary to Proposition 4, Chapter IV, §1, of [Ser79], together with obvious bounds on different divisor for 𝔽̂_{f}(x_{i})/𝔽̂_{f}(z), to bound the number of non-trivial higher ramification groups in the geometric monodromy group G_{f}.)

For σ ∈ Ĝ_{f,t}, let N(σ) be the number elements of {x_{1}, …, x_{n}} fixed by σ. Then

∑_{σ∈Ĝ_{f,t}} N(σ) = |Ĝ_{f,t}| . (3.1)

Although this is a corollary of the the Chebotarev Density Theorem (by considering t′ ≡ t mod d, where d = [𝔽̂_{f} : 𝔽_{q}] and t′ is large), one can also view it as a consequence of the following group-theoretical lemma (see, e.g., [GW97], Lemma 3.1) taking H = G_{f}, C = Ĝ_{f,t}, G ⊆ Ĝ_{f} the group generated by G_{f} and Ĝ_{f,t}, and r = 1.

Lemma 3.1. Let G be a finite group acting on a finite set S. Let H be a normal subgroup of G such that G/H is cyclic. Finally, let C be a coset whose image generates G/H. Then

\frac{1}{|C|} ∑_{σ∈C} N(σ) = r

where r is the number of H-orbits in S which are also G-orbits, and where N(σ) is the number of S-fixed points of σ ∈ G.

From (3.1), the following are equivalent:

(3.2) Every element of Ĝ_{f,t} fixes at least one element of {x_{i}}.

(3.3) Every element of Ĝ_{f,t} fixes at most one element of {x_{i}}.

(3.4) Every element of Ĝ_{f,t} fixes exactly one element of {x_{i}}.

Remark 3.2. If any of the above conditions hold, then for all non-branch points b ∈ 𝔽_{q^{t}} exactly one root is fixed by Frob_{t}(b). So, by the Frobenius Principle, f : 𝔽_{q^{t}} → 𝔽_{q^{t}} is bijective, at least on the set of points mapping to non-branch points.

When b ∈ 𝔽_{q^{t}} is a branch point, one has a Frobenius coset instead of a Frobenius element. To determine the number of a ∈ 𝔽_{q^{t}} satisfying f(a) = b, consider the action of the associated decomposition group D and inertia group I on the roots {x_{i}}. It is well-known that one counts I-orbits which are also D-orbits ([vdW35]). Using Lemma 3.1 above with G = D, H = I, and C the Frobenius coset, we see that the number of a ∈ 𝔽_{q^{t}} mapping to b is the average number of {x_{i}} fixed by σ as σ varies over the Frobenius coset. We call this fact the Strong Frobenius Principle. In particular, (3.4) implies bijectivity even when we allow points above branch points. (Note: in the Frobenius Principle or the Strong Frobenius Principle, we can replace Ĝ_{f} with the Galois group of any normal extension of 𝔽_{q}(z) containing Ω_{f}).

Definition 3.3. Let 0 ≤ ϵ ≤ 1. The polynomial map f : 𝔽_{q^{t}} → 𝔽_{q^{t}} is said to be ϵ-almost injective if the proportion of points b ∈ 𝔽_{q^{t}} which either have at most one a ∈ 𝔽_{q^{t}} satisfying f(a) = b or are branch points is at least 1 − ϵ. Similarly, f : 𝔽_{q^{t}} → 𝔽_{q^{t}} is said to be ϵ-almost surjective if the proportion of points b ∈ 𝔽_{q^{t}} which are either in the value set V_{f}(𝔽_{q^{t}}) or are branch points is at least 1 − ϵ.

The above considerations lead easily to the following theorem.

Theorem 3.4. Let 0 ≤ ϵ < 1/|Ĝ_{f,t}|, and let δ = 1/|Ĝ_{f,t}| − ϵ. If q^{t} ≥ (B/δ)^{2} where B is the constant in the Chebotarev Density Theorem, then the following are equivalent.

(3.5) f : 𝔽_{q^{t}} → 𝔽_{q^{t}} is ϵ-almost surjective.

(3.6) f : 𝔽_{q^{t}} → 𝔽_{q^{t}} is ϵ-almost injective.

(3.7) f : 𝔽_{q^{t}} → 𝔽_{q^{t}} is bijective.

(3.8) Every element of Ĝ_{f,t} fixes exactly one root of f(T) − z. For general q^{t}, large or small, (3.8) implies (3.7).

Remark 3.5. See [Fri74, Lemma 2 and Theorem 1] for a generalization to multivariable polynomial maps 𝔸^{n} → 𝔸^{n}. This theorem has also been generalized [FGS93, p. 186] to covering maps X → Y between absolutely irreducible curves over 𝔽_{q}. (The statement in [FGS93] is essentially the case where ϵ = 0, but the methods clearly work for small ϵ > 0.)

The upper bound for ϵ in the implication (3.5) ⇒ (3.8) can be replaced by \frac{1}{deg f}. With a priori restrictions on the monodromy groups involved, one can often do better (see [GW97]).

Corollary 3.6. A polynomial f ∈ 𝔽_{q}[T] is exceptional if and only if any of the equivalent conditions (3.2) to (3.7) hold for a suitable value of t and ϵ.

If (3.7) holds for t, then it holds for any divisor of t. This yields the following.

Corollary 3.7. If f ∈ 𝔽_{q}[T] is an exceptional polynomial satisfying any of the equivalent conditions (3.2) to (3.4) for t = t_{0}, then these conditions hold for any t satisfying gcd(t, d)| gcd(t_{0}, d) where d = [𝔽̂_{f} : 𝔽_{q}].

A similar analysis gives a monodromy interpretation for V_{f}(𝔽_{q^{t}}) = V_{g}(𝔽_{q^{t}}).

Theorem 3.8. Let f, g ∈ 𝔽_{q}[T]. Suppose that for some t,

(3.9) every σ ∈ Ĝ_{f,g,t} fixes an element of {x_{i}} if and only if it fixes an element of {y_{j}} (as usual, {x_{i}} are the roots of f(T) − z and {y_{j}} are the roots of g(T) − z).

Then V_{f}(𝔽_{q^{t}}) = V_{g}(𝔽_{q^{t}}). Conversely, if V_{f}(𝔽_{q^{t}}) = V_{g}(𝔽_{q^{t}}) for t sufficiently large, then (3.9) holds.

Remark 3.9. The converse above, which can be proved with the Chebotarev Density Theorem together with the Frobenius Principle, can be strengthened by replacing the hypothesis V_{f}(𝔽_{q^{t}}) = V_{g}(𝔽_{q^{t}}) with an ϵ-almost equality (analogous to Theorem 3.4).

To prove that (3.9) implies V_{f}(𝔽_{q^{t}}) = V_{g}(𝔽_{q^{t}}) one can use the Strong Frobenius Principle (as in Remark 3.2) to cover both branch points and non-branch points. Alternatively, one can use the following argument, a straightforward adaptation to the current situation of the second part of the proof of Lemma 19.27 of [FJ86]. Let b ∈ V_{f}(𝔽_{q^{t}}), and let a ∈ 𝔽_{q^{t}} be a root of f(T) − b. Consider the homomorphism 𝔽_{q}[x_{1}] → 𝔽_{q^{t}} with x_{1} ↦ a (and so z ↦ b). Extend this to a homomorphism φ : R → \overline{𝔽_{q}} where R is the integral closure of 𝔽_{q}[z] in Ω_{f,g}. Let D(φ) ⊆ Ĝ_{f,g}(x_{1}) be the decomposition group associated to φ (i.e., the subgroup fixing ker φ). A general fact about decomposition groups is that the homomorphism D(φ) → Gal(𝔽_{q^{s}}/𝔽_{q}(a)) associated to the residue maps is surjective where 𝔽_{q^{s}} is the image of φ. Thus there is an element τ ∈ D(φ) whose image in Gal(𝔽_{q^{s}}/𝔽_{q}(a)) is the q^{t}-power Frobenius map u ↦ u^{q^{t}}. Note that τ fixes x_{1}, and that τ ∈ Ĝ_{f,g,t}. It follows from (3.9) that τ fixes some y_{j}. Let c = φ(y_{j}). The image of τ acting on 𝔽_{q^{s}} fixes c. Thus, c ∈ 𝔽_{q^{t}}. Since, g(c) = b, conclude b ∈ V_{g}(𝔽_{q^{t}}).

For inclusions of value sets we have the following:

Theorem 3.10. Let f, g, ∈ 𝔽_{q}[T]. Suppose that for some t,

(3.10) every σ ∈ Ĝ_{f,g,t} which fixes an element of {x_{i}} also fixes an element

of {y_{j}}. Then V_{f}(𝔽_{q^{t}}) ⊆ V_{g}(𝔽_{q^{t}}).

Conversely, if V_{f}(𝔽_{q^{t}}) ⊆ V_{g}(𝔽_{q^{t}}) for t sufficiently large, then (3.10) holds.

Remark 3.11. We can replace (3.10) with the following.

(3.11) Every σ ∈ Ĝ_{f,g,t}(x_{1}) fixes an element of {y_{j}}.

3.2. Strong Davenport Pairs. A good reference for SDP’s is [Fri99] which uses the following Galois theoretic characterization (a corollary of Theorem 3.8 above).

Corollary 3.12. The pair (f, g) of polynomials in 𝔽_{q}[T] is a SDP if and only if

(3.12) for every σ ∈ Ĝ_{f,g}, σ fixes an element of {x_{i}} if and only if σ fixes an element of {y_{j}}.

An analogous result holds for polynomials over number fields ([FJ86, Lemma 19.27] or [Mül98, Theorem 2.3]). In that case, Condition 3.12 is equivalent to to f and g being Kronecker conjugate over a number field K, i.e., their value sets are equal modulo all but a finite number of nonzero prime ideals of K.

The following well-known result ([Fri73, Proposition 3], [FJ86, Lemma 19.31], and [Fri99]) will be generalized to DP’s below (Corollary 4.12).

Theorem 3.13. Let f, g ∈ 𝔽_{q}[T]. If (f, g) is a SDP where deg f > 1, then f(T) − g(S) ∈ 𝔽_{q}[S, T] is reducible.

This gives several immediate corollaries. For example, if f and g have relatively prime degrees, then (f, g) is not a SDP. As another example, if (f, g) is a SDP with each degree at most 3, then (f, g) is a trivial SDP. To see this, just note that reducibility implies the existence of a linear factor, which implies that f and g are linearly related on the inside.

Deeper corollaries exist. For example, when f : ℙ^{1} → ℙ^{1} and g : ℙ^{1} → ℙ^{1} are tamely ramified, the results in [Fri73] in characteristic 0 are relevant, implying major restriction on the pair (f, g). We will now review these results.

Let K be a number field, and let f, g ∈ K[T]. If f and g are Kronecker conjugate and deg f > 1 then the analogue of Theorem 3.13 holds: f(T) − g(S) is reducible. This highly restricts f and g, especially in the case where f is indecomposable. The reducibility of f(T) − g(S) together with the indecomposibility of f forces the geometric monodromy group of f to be one of a small list, and it forces deg f to be one of 7, 11, 13, 15, 21, and 31. The fact that (f, g) are Kronecker conjugate also forces deg f = deg g. This together with the Grothendieck Lifting Theorem gives the following theorem in positive characteristic.

Theorem 3.14. Consider a SDP (f, g) over 𝔽_{q} with the following properties:

(3.13) f : ℙ^{1} → ℙ^{1} is tamely ramified. (3.14) f is indecomposable. Then deg f = deg g, and both deg f and G_{f} are restricted as above.

The case where f : ℙ^{1} → ℙ^{1} has wild ramification does not result in an upper bound on the degree of f. In fact, we have the following.

Theorem 3.15 ([Fri99], Thm 5.7). Over any field 𝔽_{q} there are infinitely many n prime to p for which nontrivial SDP’s (f, g) exist with n = deg f = deg g and f indecomposable.

The monodromy groups appearing in these examples are subgroups of the projective linear groups over finite fields of characteristic p.

Note that if (f, g) is a SDP, then (h∘f, h∘g) is also a SDP for all h ∈ 𝔽_{q}[T]. More surprisingly, there are pairs (f, g) which are not SDP’s, and h ∈ 𝔽_{q}[T] of positive degree such that (h ∘ f, h ∘ g) is a SDP. Müller [Mül98, §4] gave examples of this over number fields and they apply over suitable 𝔽_{q}. So, there are many non-trivial SDP’s. Müller points out (in [Mül98, §5]) that his examples give polynomials with equivalent permutation characters, so they yield SDP’s with multiplicity.

Finally we mention what is known concerning Davenport’s original question. If K = ℚ there are no nontrivial Kronecker conjugate polynomials ([Fri73]) with f indecomposable, or with f and g each compositions of two indecomposable polynomials of degree at least 2 ([Mül98]). However, f(T) = T^{8} and g(T) = 16T^{8} are Kronecker conjugate polynomials which are the composition of three indecomposable polynomials. See [Mül98] for more information.

3.3. Work Related to Davenport Pairs. Earlier work related to DP’s (which are not assumed a priori to be SDP’s or exceptional polynomials) are not concerned with DP’s per se, but study pairs with equal value sets over the ground field 𝔽_{q}. However, when q is large, such pairs are DP’s (Corollary 4.2). For example, [Coh81] studies pairs of rational functions f, g ∈ 𝔽_{q}(T) satisfying V_{f}(𝔽_{q}) ⊆ V_{g}(𝔽_{q}). The main result is a classification of such f and g with deg g ≤ 4, where the characteristic is greater than 3 and q assumed large (with bounds depending on deg f). There has also been other, much earlier work, by McCann and Williams (value set equalities for polynomials of degree 3), Mordell (also for degree 3), and Carlitz (value set inclusions with g(T) = T^{m}).

Finally, [Ait98] studies the overlap between V_{f}(𝔽_{q}) and V_{g}(𝔽_{q}) when the two sets are not equal, which, for large q, yields a criterion for whether or not two polynomials form a DP.

4. Basic Results Concerning Davenport Pairs

Let f, g ∈ 𝔽_{q}[T], and let d = [𝔽̂_{f,g} : 𝔽_{q}]. Below are corollaries of Theorem 3.8.

Corollary 4.1. (f, g) is a DP if and only if, for some t, (3.9) holds.

Corollary 4.2. (f, g) is a DP if and only if for a sufficiently large t, V_{f}(𝔽_{q^{t}}) = V_{g}(𝔽_{q^{t}}).

Here, sufficiently large means that q^{t} is greater than a bound which can be chosen to depend only on the maximum of the degrees of f and g.

Condition (3.9) depends only on t mod d. Thus, if (3.9) holds for one t, it holds for infinitely many t; the set of such t forms a union of arithmetic progressions. For any integer t, denote its image in ℤ/d by t̄.

Definition 4.3. Let D_{f,g} = {t̄∈ ℤ/d | (3.9) holds for t}. So (f, g) is a DP if and only if D_{f,g} is not empty, and (f, g) is a SDP if and only if D_{f,g} = ℤ/d.

Corollary 4.4. For t sufficiently large, V_{f}(𝔽_{q^{t}}) = V_{g}(𝔽_{q^{t}}) if and only if t̄ ∈ D_{f,g}. For all t, large or small, t̄∈ D_{f,g} implies V_{f}(𝔽_{q^{t}}) = V_{g}(𝔽_{q^{t}}).

The set D_{f,g} is an example of a Frobenius set:

Definition 4.5. A Frobenius set (mod d) is a subset S of ℤ/d with the following property. If a ∈ S, then so is ua where u is a unit in ℤ/d. Equivalently, if a, b have the same order in ℤ/d, then a ∈ S if and only if b ∈ S. So S is completely determined by the data (d, D), where D is the set of divisors of d representing the orders in ℤ/d of the elements in S.

Call a subset A of ℕ^{+} (or ℕ or ℤ) a pure Frobenius progression if there exists a Frobenius set S ⊆ ℤ/d so that a ∈ A if and only if ā ∈ S. Finally, call a subset A of ℕ^{+} a Frobenius progression if it differs from a pure Frobenius progression by only a finite number of elements.

Remark 4.6. If (f, g) is a pair of polynomials, then D_{f,g} is a Frobenius set. The set of t satisfying (3.9) forms a pure Frobenius progression. Finally, the set of t where V_{f}(𝔽_{q^{t}}) = V_{g}(𝔽_{q^{t}}) is a Frobenius progression (containing the associated pure Frobenius progression).

For exceptional polynomials, the associated Frobenius set has additional structure: if d_{1} ∈ D where D is the set of divisors characterizing the Frobenius set, and k is a positive integer such that kd_{1}|d, then kd_{1} ∈ D. This follows from Corollary 3.7. One consequence is that D_{f,T} contains (ℤ/d)^{∗}. In particular, 1 ∈ D_{f,T}.

When we require V_{f}(𝔽_{q^{t}}) = V_{g}(𝔽_{q^{t}}) with multiplicity, we also get Frobenius progressions. Later we discuss Frobenius progressions in the context of the reducibility of f(T) − g(S).

To prove reducibility, we use the following lemma, a basic application of the Riemann Hypothesis.

Lemma 4.7. Suppose Φ(S, T) ∈ 𝔽_{q}[S, T] has A_{t} irreducible factors over 𝔽_{q^{t}}[S, T], of which N_{t} are absolutely irreducible. Then M_{t}, the number of 𝔽_{q^{t}}-points in the algebraic set Φ(S, T) = 0, is approximately N_{t}·q^{t}. More precisely, |\frac{M_{t}}{q^{t}} − N_{t}| < cq^{−t/2} for some constant c which depends only on the total degree of Φ.

Proof. Factor Φ over 𝔽_{q^{t}}[S, T] as Φ_{1} ⋯ Φ_{A_{t}}. Rearrange the factors so Φ_{1}, …, Φ_{N_{t}} are absolutely irreducible. Let M_{i} be the number of 𝔽_{q^{t}}-points of the variety Φ_{i} = 0. Bezout’s Theorem bounds |M_{t} − ΣM_{i}|. For i > N_{t}, |M_{i}| is bounded (one can use Bezout’s Theorem here as well). For i ≤ N_{t} let X̃_{i} be the non-singular projective curve corresponding to the affine curve Φ_{i} = 0. Let M̃_{i} be the number of 𝔽_{q^{t}}-points on X̃_{i}. Then |M_{i} − M̃_{i}| is bounded. All of these bounds depend on the total degree of Φ, and not q^{t}. Finally, the Riemann Hypothesis bounds |M̃_{i} − q^{t}|, giving the desired bound for |M_{t} − N_{t} · q^{t}|.

Theorem 4.8. Suppose V_{f}(𝔽_{q^{t}}) = V_{g}(𝔽_{q^{t}}) for sufficiently large t. Let N_{t} be the number of absolutely irreducible factors of f(T) − g(S) ∈ 𝔽_{q}[S, T] defined over 𝔽_{q^{t}}. Then N_{t} ≥ 1. Furthermore, N_{t} = 1 if and only if V_{f}(𝔽_{q^{t}}) = 𝔽_{q^{t}} = V_{g}(𝔽_{q^{t}}). (So N_{t} = 1 implies f and g are both exceptional polynomials.)

Here, t sufficiently large means that q^{t} is larger than an effectively computable bound which depends only on deg f and deg g.

Proof. Let M_{t} be the number of 𝔽_{q^{t}}-points in the algebraic set f(T) − g(S) = 0. V_{f}(𝔽_{q^{t}}) = V_{g}(𝔽_{q^{t}}) implies that M_{t} ≥ q^{t}. Thus N_{t} ≥ 1 by Lemma 4.7. If V_{f}(𝔽_{q^{t}}) = 𝔽_{q^{t}}, then M_{t} = q^{t}, so N_{t} = 1.

Now suppose V_{f}(𝔽_{q^{t}}) ≠ 𝔽_{q^{t}}. By Theorem 3.4 there is an A > 0 (independent of t) with at least A · q^{t} elements of V_{f}(𝔽_{q^{t}}) having at least two elements of 𝔽_{q^{t}} mapping to it under f. This implies M_{t} ≥ q^{t} · (A + 1). Thus N_{t} > 1.

Remark 4.9. Let f, g ∈ F [T]. Gauss’ Lemma implies that the factorization of f(T) − g(S) into irreducibles in F [S, T] gives a factorization of f(T) − g(y_{j}) into irreducibles in F (y_{j})[T] (with all factors having positive T -degree). By basic Galois theory, these irreducible factors of f(T)−g(y_{j}) over 𝔽_{q}(y_{j}) correspond to the orbits of {x_{i}} under the action of Ĝ_{f,g}(y_{j}).

Conclude that the F -irreducible factors of f(T)−g(S) correspond to the orbits of {x_{i}} under the action of Ĝ_{f,g}(y_{j}). Further, if Φ is a factor associated with an orbit O then |O| = deg_{T} Φ. Similar statements apply for the Ĝ_{f,g}(x_{i})-action on {y_{j}}.

Remark 4.10. In the case f, g ∈ 𝔽_{q}[T], let G_{t} be the subgroup of Ĝ_{f,g} generated by elements of Ĝ_{f,g,t} ∪ G_{f,g}. In other words, it is the subgroup generated by G_{f,g} and an element lifting the q^{t}-power Frobenius automorphism. Since G_{t} is canonically isomorphic to the Galois group of Ω_{f,g}𝔽_{q^{t}} over 𝔽_{q^{t}}(z), Remark 4.9 gives a natural correspondence between divisors Φ ∈ 𝔽_{q^{t}}[S, T] of f(T) − g(S) (up to multiplication by constants in 𝔽_{q^{t}}^{×}) and subsets B ⊆ {y_{j}} on which G_{t}(x_{i}) acts. Also, the divisor Φ is absolutely irreducible if and only if the corresponding subset B is an orbit under the action of G_{f,g}(x_{i}). A similar statement applies when reversing the roles of {y_{j}} vs. {x_{j}} and S vs. T.

Remark 4.11. Suppose Φ ∈ 𝔽_{q^{t}}[S, T] is a divisor of f(T) − g(S). Since G_{t} = G_{d′} with d′ = gcd(d, t), the above shows that, up to multiplication by a non-zero constant, Φ ∈ 𝔽_{q^{d′}} [S, T].

The above theorem and the above remarks give the following:

Corollary 4.12. If (f, g) is a DP, and f is not exceptional, then f(T) − g(S) is reducible over \overline{𝔽}_{q}. In fact, if t̄∈ D_{f,g}, then f(T) − g(S) is reducible over 𝔽_{q^{t}}.

Proof. The first statement is clear. The second statement is clear for t sufficiently large, but the above remarks show that reducibility is not actually a property of t, large or small, but a property of t mod d.

Remark 4.13. The t such that f(T) − g(S) is reducible over 𝔽_{q^{t}} form a pure Frobenius progression, with associated Frobenius set a subgroup of ℤ/d. Let (d, D) be the data defining this Frobenius set, where D is a set of divisors of d. Then, in contrast with the Frobenius set of an exceptional polynomial, if d_{1}|d_{2} are divisors of d, and d_{2} ∈ D, then d_{1} ∈ D.

Now we consider the analogous situation for inclusions V_{f}(𝔽_{q^{t}}) ⊆ V_{g}(𝔽_{q^{t}}).

Proposition 4.14. Let V_{f}(𝔽_{q^{t}}) ⊆ V_{g}(𝔽_{q^{t}}) for t sufficiently large, and let N_{t} be the number of absolutely irreducible factors of f(T) − g(S) defined over 𝔽_{q^{t}}. Then N_{t} ≥ 1. Furthermore, N_{t} = 1 if and only if g is bijective over V_{f}(𝔽_{q^{t}}) in the sense that every non-branch point b ∈ V_{f}(q^{t}) has exactly one a ∈ 𝔽_{q^{t}} mapping to it under g.

Proof. Let G_{t} be as in Remark 4.10. Also from this remark, the number N_{t} of absolutely irreducible factors of f(T) − G(S) defined over 𝔽_{q^{t}} equals the number of G_{t}(x_{1})-orbits which are also G_{f,g}(x_{1})-orbits.

Use Lemma 3.1 to count such orbits. Conclude that N_{t} = r where r is the average number of elements of {y_{j}} fixed by σ, as σ varies in Ĝ_{f,g,t}(x_{1}). By Theorem 3.10, r ≥ 1, and r = 1 if and only if every σ ∈ Ĝ_{f,g,t} fixing x_{1} fixes exactly one element of {y_{j}}. So, by the Frobenius Principle and the Chebotarev Density Theorem, r = 1 is equivalent to every non-branch point b ∈ V_{f}(𝔽_{q^{t}}) being the image of exactly one a ∈ 𝔽_{q^{t}} under the map induced by g.

Remark 4.15. The above generalizes Theorem 4.8 since, if V_{f}(𝔽_{q^{t}}) = V_{g}(𝔽_{q^{t}}), bijectivity of f over V_{f}(𝔽_{q^{t}}) is equivalent to V_{f}(𝔽_{q^{t}}) = 𝔽_{q^{t}} (use Theorem 3.4). In fact, we may view the above proof as an alternate proof of Theorem 4.8.

We end with a generalization of Theorem 3.13.

Proposition 4.16. If V_{f}(𝔽_{q^{t}}) ⊆ V_{g}(𝔽_{q^{t}}) for all t, and deg g > 1, then f(T)−g(S) is reducible over 𝔽_{q}.

Proof. By Remark 4.9, the number of factors of f(T) − g(S) is the number of Ĝ_{f,g}(x_{1})-orbits of {y_{j}}. By (3.10), each element of Ĝ_{f,g}(x_{1}) fixes at least one element of {y_{j}}. If {y_{j}} has only one Ĝ_{f,g}(x_{1})-orbit, then Ĝ_{f,g}(x_{1}, y_{j}), as y_{j} varies, are conjugate subgroups of Ĝ_{f,g}(x_{1}). The conjugates, however, of a proper subgroup of a finite group cannot cover the group.

Remark 4.17. The topic of reducibility will be continued in Section 7.

5. Behavior at Infinity

Many results above generalize to non-polynomial maps. However, polynomial maps have special properties that yield stronger results. For example, polynomial maps f : ℙ^{1} → ℙ^{1} are totally ramified above at least one place of ℙ^{1}, namely the place at infinity. In this section we study the consequences of total ramification.

We begin with a lemma concerning the special case of tame ramification. It is similar to results in the literature (for example [Mül98, Section 2.2]). However, due to the absence of a convenient reference in the needed generality and for the convenience of the reader, we give a proof.

Lemma 5.1. Let K be a field with discrete valuation v and associated residue field k. Let L be a degree n separable extension of K with valuation w extending v to L. Let M be the normal closure of L over K, and let ω be a valuation of M extending w with residue field k(ω). Let G = Gal(M/K) and H = Gal(M/L). Suppose (L, w) is tamely and totally ramified over (K, v). Then

(5.1) (M, ω) is tamely ramified over (K, v) and unramified over (L, w).

(5.2) The inertia group I_{ω} ⊆ G is cyclic and acts transitively and effectively

on G/H, and any generator of I_{ω} corresponds to an n-cycle in Perm(G/H). (5.3) k(ω) = k(ζ_{n}) where ζ_{n} is a primitive nth root of unity. (5.4) The decomposition group G_{ω} ⊆ G is isomorphic to the semidirect prod-

uct μ_{n} ⋊_{φ} G̃ where μ_{n} ⊆ k(ω)^{×} is the group of nth roots of unity, G̃ is Gal(k(ω)/k), and φ : G̃ → Aut(μ_{n}) is the natural Galois action on the nth roots of unity.

(5.5) The isomorphism G_{ω} → μ_{n} ⋊_{φ} G̃ can be chosen so that the inertia group I_{ω} corresponds to μ_{n}, and H ∩ G_{ω} corresponds to G̃.

Proof. Let π = π_{L} be a uniformizer for (L, w), and let h_{1} ∈ K[T] be its minimal, monic polynomial. This polynomial is Eisenstein of degree n (its non-leading coefficients have positive valuation, and its constant term is a uniformizer for (K, v)).

Since (L, w) is totally ramified over (K, v), I_{ω} acts transitively on G/H. The action is effective (G acts effectively on G/H). The property of tame ramification behaves well under composita, and (L, w) is tamely ramified over (K, v). Thus (M, ω) is also tamely ramified over (K, v). So I_{ω} is cyclic. It acts transitively and effectively on G/H, so its generator acts as an n-cycle. In particular |I_{ω}| = |G/H| = n, forcing (M, ω) to be unramified over (L, w).

Let K_{v}, L_{w}, and M_{ω} be the completions associated with (K, v), (L, w), and (M, ω). So G_{ω} is canonically isomorphic to Gal(M_{ω}/K_{v}). Since h_{1} remains irreducible over K_{v}, L_{w} = K_{v}(π) and M_{ω} is the splitting field of h_{1} over K_{v}. Let h_{2}(T) = T^{n} − π_{K} where π_{K} = −h_{1}(0). Note that π_{K} is a uniformizer for K_{v}. Let M′ be the splitting field of h_{2} over K_{v}. We show that M_{ω} = M′.

Let β ∈ M′ be a root of h_{2}, and ζ ∈ M′ a primitive nth root of unity. Note that h_{3}(T) =^{def} h_{1}(βT)/π_{K} is a monic polynomial in M′ with coefficients of non-negative valuation. By Hensel’s lemma, all the roots r_{1}, …, r_{n} of h_{3} are in M′. Thus {r_{i}β}, the roots of h_{1}, are in M′. Conclude M_{ω} ⊆ M′.

The roots of h_{1} correspond to the roots of h_{2} as follows. If α is a root of h_{1}, then expand α in M′ in terms of the uniformizer β as α = ζ^{i}β +higher order terms. The correspondence sends α to ζ^{i}β. This correspondence is compatible with the Gal(M′/K_{v}) action. Conclude that M_{ω} = M′.

Clearly I_{ω} = Gal(M_{ω}/K_{v}(ζ)), and so Gal(K_{v}(ζ)/K_{v}) is canonically isomorphic to G̃ = Gal(k(ω)/k). Conclude that k(ω) = k(ζ_{n}).

Replace β by βζ^{i}, if necessary, so that π corresponds to β. So H_{ω} = H ∩G_{ω} is the subgroup of G_{ω} fixing β, and L_{w} = K_{v}(β). Clearly H_{ω} ∩ I_{ω} = 1, and |H_{ω}| = |G̃|. So, restricting the natural homomorphism G_{ω} → G̃ gives an isomorphism H_{ω} → G̃. The inverse isomorphism splits the exact sequence

1 → I_{ω} → G_{ω} → G̃ → 1.

Thus G_{ω} is isomorphic to a semi-direct product I_{ω} ⋊ G̃ with an isomorphism which sends H_{ω} to G̃.

The rule γ ↦ \overline{γ(β)/β} defines a natural isomorphism I_{ω} → μ_{n} ([Frö67, Section 8]), where a ↦ ā is the residue map. If γ ↦ ζ_{n}^{i}, then clearly σγσ^{−1} ↦ σ̃(ζ_{n}^{i}) where σ̃ is the image of σ in G̃. The result follows.

Example 5.2. Let f ∈ F [T] be a polynomial of degree prime to the characteristic of F. Then the hypotheses of Lemma 5.1 are satisfied in the following situation.

K = F (z) with v = ∞_{z}, the place at infinity. (So k = F).

L = F (x_{1}) with w = ∞_{x_{1}}. (Here, x_{1} is a fixed root of f(T) − z).

M = Ω_{f} with ω any place above ∞_{x_{1}}.

G = Ĝ_{f}, and H is the subgroup fixing x_{1}.

Note that we can identify the roots {x_{1}, …, x_{n}} with G/H where a given root x_{j} corresponds to the coset of elements sending x_{1} to x_{j}.

Applying the Lemma 5.1 to the above example gives the following.

Corollary 5.3. Suppose n = deg f is prime to the characteristic of F. Let ζ_{n} ∈ F be a primitive nth root of unity, and μ_{n} ∈ F^{×} the group of all nth roots of unity.

1. The geometric monodromy group G_{f} contains an element which acts on {x_{i}} as an n-cycle.

2. The field F̂_{f} is a subfield of F (ζ_{n}). In particular, if F = 𝔽_{q} and q ≡ 1 mod n, then 𝔽̂_{f} = 𝔽_{q} and Ĝ_{f} = G_{f}.

3. The arithmetic monodromy group Ĝ_{f} contains a subgroup isomorphic to μ_{n} ⋊ Gal(F (μ_{n})/F), and the geometric monodromy group G_{f} contains a subgroup isomorphic to μ_{n} ⋊ Gal(F (μ_{n})/F̂_{f}).

We now give the main theorem of this section. Here D_{f,g} ⊆ ℤ/d is as in Definition 4.3 and d = [𝔽̂_{f,g} : 𝔽_{q}].

Theorem 5.4. Let f, g ∈ 𝔽_{q}[T] with n = deg f and m = deg g. If (f, g) is a DP, then gcd(n, q^{t} − 1) = gcd(m, q^{t} − 1) for all positive t with t̄∈ D_{f,g}.

Proof. Let t be a positive integer with t̄ ∈ D_{f,g}. Write n = n_{0}p^{u} and m = m_{0}p^{v} where n_{0} and m_{0} are prime to p, the characteristic of 𝔽_{q}. We need to show that gcd(n_{0}, q^{t} − 1) = gcd(m_{0}, q^{t} − 1).

Let ∞_{z} be the infinite place of 𝔽_{q}(z), and let K be the completion. Fix a place ω of Ω_{f,g} above ∞_{z}. Let Ĝ_{ω} ⊆ Ĝ_{f,g} be the decomposition group associated to ω, and I ⊆ Ĝ_{ω} the inertia group. Thus Ĝ_{ω} is canonically isomorphic to Gal(Ω_{ω}/K) where Ω_{ω} is the completion of Ω_{f,g} at ω. Choose an element ϕ_{t} ∈ Ĝ_{ω} which induces the automorphism x ↦ x^{q^{t}} of the residue field. Since 𝔽_{q}(x_{1}) is totally ramified over 𝔽_{q}(z) at ∞_{z}, the group I acts transitively on {x_{i}}. So, after replacing ϕ_{t} by σϕ_{t} for a suitable σ ∈ I, we can assume that ϕ_{t} fixes x_{1}. Note: ϕ_{t} ∈ Ĝ_{f,g,t}(x_{1}), so ϕ_{t} must also fix an element of {y_{j}}.

Let I_{1} ⊆ I be the first higher ramification group. Thus I_{1} is a normal p-Sylow subgroup of I with cyclic quotient. Let γ ∈ I be an element whose image in I/I_{1} is a generator.

Let R_{x} be Ĝ_{ω}/I_{1}Ĝ_{ω}(x_{1}), and consider the map {x_{i}} → R_{x} sending x_{i} to the coset σI_{1}Ĝ_{ω}(x_{1}) where σ ∈ Ĝ_{ω} is chosen so that σ(x_{1}) = x_{i}. The fibers of this map are exactly the I_{1} orbits of {x_{i}}. Since I_{1} is normal in I and I acts transitively on {x_{i}}, the I_{1} orbits all have the same size, that size is a power of p, and the number of I_{1} orbits is prime to p. Since n = |{x_{i}}| is the product of |R_{x}| and the fiber size, it follows that R_{x} has n_{0} elements, and the fibers have size p^{u}. Likewise, let R_{y} be Ĝ_{ω}/I_{1}Ĝ_{ω}(y_{1}), and consider the corresponding map {y_{j}} → R_{y}. Conclude that |R_{y}| = m_{0} and that the fibers have size p^{v}.

Let L_{x} ⊆ Ω_{ω} be the fixed field of I_{1}Ĝ_{ω}(x_{1}), and L_{y} the fixed field of I_{1}Ĝ_{ω}(y_{1}). Let M_{x} ⊆ Ω_{ω} be the normal closure of L_{x} over K, and M_{y} the normal closure of L_{y} over K. We can identify R_{x} with Gal(M_{x}/K)/Gal(M_{x}/L_{x}). Conclude that [L_{x} : K] = n_{0}. Since I acts transitively on R_{x}, L_{x}/K is totally and tamely ramified. A similar conclusion holds for L_{y}/K.

Apply Lemma 5.1 to L_{x}/K and L_{y}/K. For example, we can identify R_{x} with ℤ/n_{0} so that ϕ_{t} fixes 0 ∈ ℤ/n_{0} and γ acts as the map c ↦ c + 1. Consequently, γ^{b}ϕ_{t} acts on ℤ/n_{0} as the map c ↦ q^{t}c + b. Identify R_{y} with ℤ/m_{0} in a similar manner.

Now suppose a = gcd(q^{t} − 1, n_{0}) is not a multiple of gcd(q^{t} − 1, m_{0}). Then γ^{a}ϕ_{t}, viewed as c ↦ q^{t}c + a modulo n_{0}, clearly fixes an element of R_{x}. However, γ^{a}ϕ_{t}, viewed as c ↦ q^{t}c+a modulo m_{0}, fixes no element of R_{y}. Let ρ ∈ R_{x} be an element fixed by γ^{a}ϕ_{t}, and let x_{i_{0}} be an element of the fiber of {x_{i}} → R_{x}. Since fibers of this map are I_{1} orbits, there is a τ ∈ I_{1} such that τγ^{a}ϕ_{t} fixes x_{i_{0}}. However, τγ^{a}ϕ_{t} and γ^{a}ϕ_{t} act on R_{y} in the same way. So neither has a fixed point in R_{y}. Thus, τγ^{a}ϕ_{t} fixes no element of {y_{j}}, contradicting t̄ ∈ D_{f,g}. Conclude that a is a multiple of gcd(q^{t} − 1, m).

Similarly, conclude that gcd(q^{t}−1, m_{0}) is a multiple of gcd(q^{t}−1, n_{0}). Therefore, gcd(q^{t} − 1, m_{0}) = gcd(q^{t} − 1, n_{0}).

Remark 5.5. Although we have adopted the convention that polynomials in this paper have non-zero derivatives, the above theorem (and its corollaries) remain valid for polynomials with zero derivatives.

A corollary is Lenstra’s theorem [CF95]:

Corollary 5.6. Let f ∈ 𝔽_{q}[T] with n = deg f. If f is an exceptional polynomial, then gcd(n, q − 1) = 1.

Proof. Apply the theorem to (f, g) where g(T) = T. Take t = 1 and recall that \overline{1} ∈ D_{f,g} since f is exceptional.

Corollary 5.7. Let f, g ∈ 𝔽_{q}[T] where deg f = n_{0}p^{u} and deg g = m_{0}p^{v} with n_{0} and m_{0} prime to the characteristic p. If (f, g) is a SDP then n_{0} = m_{0}.

Proof. Let t be the order of q modulo n_{0}m_{0}. Thus n_{0}m_{0} | q^{t} − 1. By Theorem 5.4,

n_{0} = gcd(q^{t} − 1, deg f) = gcd(q^{t} − 1, deg g) = m_{0}.

The above Theorem and Corollary easily generalize to the case of value set inclusions:

Proposition 5.8. Let f, g ∈ 𝔽_{q}[T] where deg f = n and deg g = m. For all t such that (3.10) holds, gcd(q^{t} − 1, m) divides gcd(q^{t} − 1, n).

Proposition 5.9. Let f, g ∈ 𝔽_{q}[T] where deg f = n_{0}p^{u} and deg g = m_{0}p^{v} with n_{0} and m_{0} prime to the characteristic p. If V_{f}(𝔽_{q^{t}}) ⊆ V_{g}(𝔽_{q^{t}}) for all t, then m_{0} divides n_{0}.

6. Induced Decompositions

In this section we review properties of induced decompositions. Most of the results are found in or are extensions of results in [Fri73].

Lemma 6.1. Let f, g ∈ F [T] be a pair of polynomials. There is a decomposition f = f_{1} ∘ f_{2} with f_{1}, f_{2} ∈ F [T] having the following properties:

(6.1) F (x_{i}) ∩ Ω_{g} = F (f_{2}(x_{i})) for all x_{i} in {x_{1}, …, x_{n}}.

(6.2) deg f_{2} = 1 if and only if Ω_{f} ⊆ Ω_{g}.

(6.3) For all x_{i}, f_{2}(T) − f_{2}(x_{i}) is an irreducible polynomial over Ω_{g}. Furthermore, the above properties characterize f_{1} and f_{2} up to composition with linear polynomials (actually (6.1) suffices). More specifically, if f = f_{1} ∘f_{2} = f′_{1} ∘f′_{2} are two such decompositions, then f′_{1} = f_{1} ∘ l^{−1} and f′_{2} = l ∘ f_{2} where l ∈ F [T] is a linear polynomial.

Call this decomposition and the analogous decomposition of g the induced decompositions associated to the pair (f, g).

Proof. Fix a particular root x_{i}. By Lüroth’s Theorem, F (x_{i})∩Ω_{g} = F (w_{i}) for some w_{i} ∈ F (x_{i}). Adjust the choice of w_{i} by a suitable linear fractional transformation so that w_{i} = f_{2}(x_{i}) and z = f_{1}(w_{i}) for some f_{1}, f_{2} ∈ F [T]. Thus f = f_{1} ∘ f_{2}. Any other choice w′_{i} has the form aw_{i} + b where a, b ∈ F, a ≠ 0. So f_{1} and f_{2} are unique up to composition with a linear polynomial. Now let x_{j} be any element of {x_{1}, …, x_{n}} and let σ ∈ Ĝ_{f,g} send x_{i} to x_{j}. Then F (x_{j}) ∩ Ω_{g} = F (σ(x_{i})) ∩ Ω_{g} = F (f_{2}(σ(x_{i}))) = F (f_{2}(x_{j})). So (6.1) holds.

To see (6.2), note that deg f_{2} = 1 implies F (x_{i})∩Ω_{g} = F (x_{i}). Thus F (x_{i}) ⊆ Ω_{g}, so Ω_{f} ⊆ Ω_{g}. The converse is clear.

To see (6.3), consider f_{2}(T) − f_{2}(x_{i}). By (6.1), this polynomial is defined over Ω_{g}. We will show it is irreducible by showing that Gal(\overline{Ω}_{g}/Ω_{g}) acts transitively on its roots. Any root equals some x_{j} satisfying f_{2}(x_{i}) = f_{2}(x_{j}). Let σ ∈ Gal (\overline{F (z)}/F (z)) satisfy σ(x_{i}) = x_{j}. Let σ̃ be the restriction of σ to Ω_{g}. Clearly, σ̃(f_{2}(x_{i})) = f_{2}(x_{i}), so σ̃ ∈ Gal(Ω_{g}/Ω_{g} ∩ F (x_{i})). The restriction map

Gal (F (x_{i}) · Ω_{g}/F (x_{i})) → Gal (Ω_{g}/Ω_{g} ∩ F (x_{i}))

is an isomorphism. Use this to lift σ̃ to F (x_{i}) · Ω_{g}, and then to \overline{Ω}_{g} so the lifting τ fixes x_{i}. Then σ ∘ τ^{−1} ∈ Gal(\overline{Ω}_{g}/Ω_{g}) and σ ∘ τ^{−1}(x_{i}) = σ(x_{i}) = x_{j}.

An important feature of these induced decompositions is that they respect the factorization of f(T) − g(S).

Lemma 6.2. Suppose f(T) − g(S) is reducible over F, and let f = f_{1} ∘ f_{2} be the induced decomposition. Then f_{1}(T) − g(S) is reducible over F. Moreover, substituting f_{2}(T) for T into the factorization of f_{1}(T) − g(S) gives the factorization of f(T) − g(S). In particular, deg f_{1} > 1.

Proof. Fix x_{i}. As in Remark 4.9, factoring g(S) − f(T) over F [S, T] corresponds to finding the orbits of \{y_{j}\} under the action of G_{x_{i}} =^{def} Gal (\overline{F (z)}/F (x_{i})). Similarly, factoring g(S) − f_{1}(T) over F [S, T] corresponds to finding the orbits of {y_{j}} under the action of G_{f_{2}(x_{i})} =^{def} Gal (\overline{F (z)}/F (f_{2}(x_{i}))).

Decompose {y_{j}} into orbits with both groups. Clearly the G_{f_{2}(x_{i})}-orbits contain the G_{x_{i}}-orbits. We show, in fact, they are equal. Let σ ∈ G_{f_{2}(x_{i})} send y_{j} to y_{k}. If σ sends x_{i} to x_{l}, then x_{i} and x_{l} are both roots of f_{2}(T) − f_{2}(x_{i}). By (6.3), there is a τ ∈ Gal (\overline{F (z)}/Ω_{g}) sending x_{i} to x_{l}. Thus τ^{−1} ∘ σ ∈ G_{x_{i}} sends y_{j} to y_{k}.

Let O ⊆ {y_{j}} be such an orbit, Φ(S, T) the corresponding irreducible factor of g(S) − f_{1}(T), and Φ′(S, T) the corresponding irreducible factor of g(S) − f(T). The correspondence of Remark 4.9 yields the equation

∏_{y_{j}∈O}(S − y_{j}) = c Φ(S, x_{i}) = c′ Φ′(S, f_{2}(x_{i}))

for some c, c′ ∈ F. Thus c Φ(S, T) = c′ Φ′(S, f_{2}(T)).

Corollary 6.3 ([Fri73], Lemma 7). Suppose f(T)−g(S) is reducible over F. Then there are decompositions f = f′ ∘ f′′ and g = g′ ∘ g′′ with f′, f′′, g′, g′′ ∈ F [T] such that (i) f′(T) − g′(S) is reducible, (ii) Ω_{f′} = Ω_{g′}, and (iii) substituting f′′(T) for T and g′′(S) for S into the factorization of f′(T) − g′(S) gives the the factorization of f(T) − g(S).

Furthermore, if either deg f′ or deg g′ is prime to p, then deg f′ = deg g′.

Proof. To prove this, repeatedly use the previous lemma applied to induced decompositions of f and g. (Replace f and g with the outer composites as you go along). Eventually you will obtain f_{2} and g_{2} of degree 1 which implies that Ω_{f} = Ω_{g}.

Now if deg f′ or deg g′ is prime to p, then the place at infinity is tamely ramified in Ω_{f′} = Ω_{g′}. Conclude that both deg f′ and deg g′ give the order of the inertia group at infinity, so they are equal. (See Lemma 5.1 above).

Now we show that induced decompositions behave well in certain types of value set situations. Since we are dealing with value sets, we restrict to F = 𝔽_{q} for the remainder of this section.

Proposition 6.4. Suppose V_{f}(𝔽_{q^{t}}) ⊆ V_{g}(𝔽_{q^{t}}) for all t. Let f = f_{1} ∘ f_{2} be the induced decomposition associated to the pair (f, g) and let g = g_{1} ∘ g_{2} be any decomposition (for example, the induced decomposition). Then V_{f_{1}}(𝔽_{q^{t}}) ⊆ V_{g_{1}}(𝔽_{q^{t}}) for all t.

Proof. All roots of f_{1}(T) − z have the form f_{2}(x_{i}). By Theorem 3.10, we can show V_{f_{1}}(𝔽_{q^{t}}) ⊆ V_{g}(𝔽_{q^{t}}) for all t by showing that any σ ∈ Gal(\overline{𝔽_{q}(z)}/𝔽_{q}(z)) which fixes f_{2}(x_{i}) must also fix some y_{j}. If σ ∈ Gal(\overline{𝔽_{q}(z)}/𝔽_{q}(z)) fixes f_{2}(x_{i}), then x_{l} = σ(x_{i}) is a root of f_{2}(T) − f_{2}(x_{i}). By (6.3), there is a τ ∈ Gal (\overline{𝔽_{q}(z)}/Ω_{g}) sending x_{l} to x_{i}. So τ ∘ σ fixes x_{i}, and by hypothesis and Theorem 3.10, it must fix some y_{j}. Since τ fixes y_{j}, conclude σ also fixes y_{j}.

Clearly, V_{g}(𝔽_{q^{t}}) ⊆ V_{g_{1}}(𝔽_{q^{t}}).

Corollary 6.5. Suppose (f, g) is a SDP with deg g > 1, so (as in Proposition 4.16) f(T) − g(S) is reducible. Then the decompositions of Corollary 6.3 can be chosen so that (f′, g′) is a SDP.

Suppose, instead, V_{f}(𝔽_{q^{t}}) ⊆ V_{g}(𝔽_{q^{t}}) for all t. Then the decompositions of Corollary 6.3 can be chosen so that V_{f′}(𝔽_{q^{t}}) ⊆ V_{g′}(𝔽_{q^{t}}) for all t.

Proposition 6.6. Suppose (f, g) is a SDP with n = deg f and m = deg g prime to p. Then Ω_{f} = Ω_{g}.

Proof. By Corollary 5.9, n = m. Let f = f_{1} ∘ f_{2} be the induced decomposition associated to the pair (f, g). By Proposition 6.4, (f_{1}, g) is also a SDP. By Corollary 5.9 again, deg f_{1} = m. Hence, deg f_{2} = 1. Thus, by (6.2), Ω_{f} ⊆ Ω_{g}. A similar argument gives the other inclusion.

Finally, we show that in some circumstances the induced decompositions behave well for DP’s.

Proposition 6.7. Suppose (f, g) is a DP with 𝔽̂_{f,g} = 𝔽̂_{g}. Let f = f_{1} ∘ f_{2} be the induced decomposition associated to the pair (f, g). Then (f_{1}, g) is a DP. Furthermore, D_{f,g} ⊆ D_{f_{1},g}, both being subsets of ℤ/d where d = [𝔽̂_{g} : 𝔽_{q}].

Proof. We need to verify (3.9) with (f_{1}, g) for all t such that t̄ ∈ D_{f,g} (Definition 4.3). So, let σ ∈ Ĝ_{f_{1},g,t} where t̄ ∈ D_{f,g}, and let σ̃ ∈ Ĝ_{f,g,t} be a element restricting to σ. Note that the roots of f_{1}(T) − z have the form f_{2}(x_{i}).

First, suppose σ fixes y_{j}. So σ̃ fixes y_{j}, and, by property (3.9), σ̃ fixes some x_{i}. Thus σ̃, and hence σ, fix f_{2}(x_{i}).

Now suppose σ fixes f_{2}(x_{i}). Let x_{l} = σ̃(x_{i}) (so x_{l} is a root of f_{2}(T) − f_{2}(x_{i})). By (6.3) there is a τ ∈ Gal(Ω_{f,g}/Ω_{g}) sending x_{i} to x_{l}. Since τ fixes Ω_{g}, it also fixes 𝔽̂_{g} = 𝔽̂_{f,g}. Hence τ^{−1} ∘ σ̃ ∈ Ĝ_{f,g,t}(x_{i}). Since t̄ ∈ D_{f,g}, property (3.9) applies, and τ^{−1} ∘ σ̃ must fix some y_{j}. Since τ fixes y_{j} ∈ Ω_{g}, conclude σ also fixes y_{j}.

Remark 6.8. An analogous result holds for inclusions.

7. Reducibility and Representations

This section links the reducibility of f(T) − g(S) to the behaviour of the associated Galois representations. It builds on the characteristic zero results of [Fri73] and the positive characteristic results of [Fri99].

7.1. Group Theory Lemmas. Let G be a finite group acting on a finite set S = {s_{i}} with N elements. This permutation action of G has an associated linear action of G on a complex vector space V_{S} as follows. Let V_{S} be an N-dimensional complex vector space with a chosen basis (s_{i}). Have σ ∈ G act on V_{S} by the unique linear transformation that sends s_{i_{1}} to s_{i_{2}} if and only if σ (acting on S) sends s_{i_{1}} to s_{i_{2}}.

Let χ_{S} be the character of the action of G on V_{S}. The following lemma, a special case of Lemma 3.1, is easy and well-known.

Lemma 7.1. For all σ ∈ G, the value of the character χ_{S}(σ) is the number of elements of S fixed by σ. Furthermore,

< χ_{S}, 1 > = \frac{1}{|G|} ∑_{σ∈G} χ_{S}(σ) = number of orbits in S.

Here we use the standard Hermitian inner product on the vector space ℂ^{|G|} of functions from G to ℂ:

< f_{1}, f_{2} > =^{def} \frac{1}{|G|} ∑_{σ∈G} f_{1}(σ)\overline{f_{2}(σ)}.

The irreducible characters form an orthogonal basis.

The ℂ[G]-module V_{S} decomposes as 111_{S} ⊕ V′_{S} where 111_{S} is the submodule generated by ∑_{i} s_{i} and where V′_{S} is the kernel of the augmentation map η : V_{S} → ℂ, ∑_{i} λ_{i}s_{i} ↦ ∑ λ_{i}. Let χ′_{S} be the character associated to V′_{S}. In particular, χ_{S} = 1 + χ′_{S}.

Lemma 7.2. If G acts transitively on S, then 111_{S} consists of all elements of V_{S} fixed by G. Furthermore < 1, χ′_{S} >= 0, and so < χ′_{S}, χ′_{S} > = < χ_{S}, χ_{S} > − 1.

Proof. The identity character appears exactly once in the permutation representation of each orbit of G acting on S. So, transitivity means that 111 doesn’t appear in χ′_{S}. Apply the inner product of 111 + χ′_{S} to itself to get the given relation.

Remark 7.3. In general, < χ′_{S}, χ′_{S} > = < χ_{S}, χ_{S} > − (2r − 1) where r is the number of orbits in S.

Now let the finite group G act transitively on two finite sets A and B. Consider also the associated G-action on A × B. The following easy lemma is the starting point for our analysis of reducibility.

Lemma 7.4. The number of orbits of the product A × B under the action of G is equal to < χ_{A}, χ_{B} >.

Proof. The character χ_{A×B} associated to the action of G on A × B is just χ_{A} · χ_{B}. By Lemma 7.1, the number of orbits in A × B is

\frac{1}{|G|} ∑_{σ∈G} χ_{A×B}(σ) = \frac{1}{|G|} ∑_{σ∈G} χ_{A}(σ)χ_{B}(σ) = < χ_{A}, χ_{B} > .

(Note: this proof does not require the transitivity assumption).

The following well-known characterization of double transitivity is an immediate consequence of the above results.

Corollary 7.5. Suppose the action of G on S is transitive where |S| ≥ 2. Then the following are equivalent:

(7.1) The action of G on S is doubly transitive.

(7.2) There are exactly two orbits in S × S under the action of G.

(7.3) < χ_{S}, χ_{S} >= 2.

(7.4) < χ′_{S}, χ′_{S} >= 1.

(7.5) V′_{S} is an irreducible ℂ[G]-module.

Remark 7.6. In this corollary, we can replace they hypothesis that G acts transitively on S with the alternate hypothesis |S| > 2.

The following is also an easy consequence of Lemma 7.4.

Lemma 7.7. If G acts doubly transitively on A and |A| ≥ 2, then the multiplicity of V′_{A} in the decomposition of V′_{B} is one less than the number of G-orbits of A × B.

Corollary 7.8. Suppose |A| ≥ 2 and G acts doubly transitively on A. Suppose also that |A| = |B|. Then the following are equivalent:

(7.6) χ_{A} = χ_{B}.

(7.7) A × B has more than one orbit.

(7.8) A × B has exactly two orbits.

(7.9) V_{A} and V_{B} are isomorphic as ℂ[G]-modules.

Remark 7.9. Note that if (7.6) (or its equivalents) hold, then G must act doubly transitively on B as well (by Corollary 7.5).

We refine (7.9) above by explicitly constructing a natural isomorphism from V_{A} to V_{B} when (i) G acts doubly transitively on A, (ii) |A| = |B|, and (iii) A × B has more than one orbit. We first define natural maps V_{A} → V_{B} without using these three hypotheses, and then show that when the hypotheses hold, one gets an isomorphism.

First choose a G-invariant subset Γ of A × B, for example a G-orbit. For convenience, label elements: A = {a_{i}}, B = {b_{j}}. Consider the matrix E = [ϵ_{i,j}] where ϵ_{i,j} is 1 if (a_{i}, b_{j}) ∈ Γ, and 0 otherwise. Consider the linear map ψ : V_{A} → V_{B} defined by the matrix E:

ψ(a_{i}) =^{def} ∑_{j} ϵ_{i,j}b_{j}, so ψ (∑_{i} λ_{i}a_{i}) = ∑_{j} (∑_{i} λ_{i}ϵ_{i,j}) b_{j}.

Here and below, (a_{i}) is the basis of V_{A} associated to A = {a_{i}}, and (b_{j}) is the basis of V_{B} associated to B = {b_{j}}.

The following lemma follows directly from the definition (and does not depend on transitivity).

Lemma 7.10. The map ψ : V_{A} → V_{B} is a ℂ[G]-module morphism.

Now we investigate some of the consequences of transitivity.

Lemma 7.11. If Γ is nonempty, then restricting ψ to 111_{A} gives an isomorphism 111_{A} → 111_{B} of ℂ[G]-modules.

Proof. Check that ψ sends ∑_{i} a_{i} to C ∑_{j} b_{j} where, for each b_{j}, C = C_{j} is the number of a_{i} ∈ A with the property that (a_{i}, b_{j}) ∈ Γ. (C_{j} is independent of j by transitivity).

Lemma 7.12. Restricting ψ to V′_{A} gives a ℂ[G]-module morphism ψ′ : V′_{A} → V′_{B}.

Proof. Check that η_{B} ∘ ψ = D · η_{A} where η_{A} and η_{B} are the augmentation maps, and, for each a_{i}, D = D_{i} is the number of b_{j} ∈ B with the property that (a_{i}, b_{j}) ∈ Γ. (D_{i} is independent of i by transitivity).

Lemma 7.13. If Γ ⊆ A × B is not empty, nor all of A × B, then ψ′ : V′_{A} → V′_{B} (defined above) has non-trivial image.

Proof. Fix a basis vector a_{i} of V_{A}. Since Γ is non-empty, ϵ_{i,j_{1}} = 1 for some j_{1}. Since Γ is a proper subset of A × B, ϵ_{i,j_{2}} = 0 for some j_{2}. Let σ ∈ G be an element such that σ(b_{j_{1}}) = b_{j_{2}}. Then ψ′(σ(a_{i}) − a_{i}) ≠ 0.

Lemma 7.14. Suppose that G acts doubly transitively on A, and that Γ is not empty nor all of A × B. Then ψ : V_{A} → V_{B} is injective.

Proof. By Corollary 7.5, V′_{A} is irreducible, and by the previous lemma, the map ψ′ : V′_{A} → V′_{B} is not trivial. Thus ψ′ is injective. By Lemma 7.11, the map 111_{A} → 111_{B} induced by ψ is an isomorphism. Thus ψ : 111_{A} ⊕ V′_{A} → 111_{B} ⊕ V′_{B} is injective.

Proposition 7.15. Suppose that (i) G acts doubly transitively on A, (ii) |A| = |B|, and (iii) Γ is a non-empty proper subset of A × B invariant under the action of G. Then ψ : V_{A} → V_{B} is an isomorphism.

Proof. By the previous lemma, ψ is injective. Since V_{A} and V_{B} have the same dimension, ψ is an isomorphism.

Also of interest is the following ([Fri73, Lemma 2]).

Lemma 7.16. Suppose G acts doubly transitively on A, and |A| = |B| ≥ 2. Suppose also that, for all σ ∈ G, χ_{A}(σ) > 0 if and only if χ_{B}(σ) > 0. Then χ_{A} = χ_{B}.

Proof. Recall χ′_{A} = χ_{A} − 1 and χ′_{B} = χ_{B} − 1. By hypothesis, for all σ ∈ G, χ′_{A}(σ) < 0 if and only if χ′_{B}(σ) < 0. If σ = 1 then χ′_{A}(σ) > 0 and χ′_{B}(σ) > 0. Thus

< χ_{A}, χ_{B} > = < χ′_{A}, χ′_{B} > + 1 ≥ 2.

The result follows from Lemma 7.4 and Corollary 7.8.

Remark 7.17. This shows that if (f, g) is a SDP and if Ĝ_{f} acts doubly transitively on {x_{i}}, then (f, g) is actually a SDP with multiplicity. (This can also be seen as a corollary of Proposition 7.26 and Theorem 3.13).

Remark 7.18. In the above lemma, we can replace the hypothesis that for all σ ∈ G, χ_{A}(σ) > 0 if and only if χ_{B}(σ) > 0 with the hypothesis that for all σ ∈ G, χ_{A}(σ) ≤ 1 if and only if χ_{B}(σ) ≤ 1.

Finally, we describe one more consequence of double transitivity which will be useful later.

Lemma 7.19. Let Γ be an orbit of A×B where, as above, G acts transitively on A and B. Suppose also that G acts doubly transitively on A where |A| ≥ 2. Then

|A||B|(|A| − 1) | |Γ|(|Γ| − |B|).

Proof. For b ∈ B, let Γ_{b} =^{def} {a|(a, b) ∈ Γ}. Note, k =^{def} |Γ_{b}| is independent of b ∈ B since G acts transitively on B.

Now consider the set

Γ′ = {(a, a′, b) | (a, b), (a′, b) ∈ Γ, and a ≠ a′ }.

For distinct elements a, a′ of A, let Γ′_{a,a′} =^{def} {b|(a, a′, b) ∈ Γ′}. Note, l =^{def} |Γ′_{a,a′}| is independent of a and a′ since G acts doubly transitively on A.

We count the number of element of Γ′ in two ways:

|Γ′| = |A|(|A| − 1)l = |B|k(k − 1)

Now multiply both sides by |B| and use the equation k|B| = |Γ|.

7.2. Reducibility. In this section, unless otherwise stated, F is a general field and f, g ∈ F [T]. Remark 4.9 describes the factorization of f(T) − g(S) in F [S, T] in terms of Ĝ_{f,g}(y_{j})-orbits of {x_{i}}. However, there is another natural description of the factorization of f(T) − g(S) in F [S, T] whose validity follows immediately from Remark 4.9:

Proposition 7.20. Consider the action of Ĝ_{f,g} on {x_{i}} × {y_{j}} induced by the natural actions of Ĝ_{f,g} on {x_{i}} and {y_{j}}. The irreducible factors of f(T) − g(S) in F [S, T] naturally correspond to the orbits of {x_{i}}×{y_{j}}. This correspondence sends an irreducible factor Φ of f(T) − g(S) to the orbit consisting of all pairs (x_{i}, y_{j}) satisfying Φ(x_{i}, y_{j}) = 0 in Ω_{f,g}.

Let O ⊆ {x_{i}} × {y_{j}} be such an orbit, and let Φ ∈ F [S, T] be the corresponding factor of f(T) − g(S). Then

|O| = deg f · deg_{S} Φ = deg g · deg_{T} Φ.

Corollary 7.21. The number of irreducible factors of f(T) − g(S) in F [S, T] is bounded by w = gcd(deg f, deg g). In fact, the T -degree of any irreducible factor of f(T) − g(S) is a multiple of (deg f)/w, and the S-degree of any such factor is a multiple of (deg g)/w.

Remark 7.22. The above corollary generalizes the well-known result of Ehrenfeucht that gcd(deg f, deg g) = 1 implies f(T) − g(S) is irreducible.

Corollary 7.23. Let Φ be an irreducible divisor of f(T)−g(S) in the ring F [S, T]. If deg f = deg g, then

deg Φ = deg_{T} Φ = deg_{S} Φ

where the first of these is is the total degree of Φ.

Now consider the special case F = 𝔽_{q}. Factoring f(T)−g(S) over 𝔽_{q} amounts to describing the orbits of {x_{i}} × {y_{j}} under the action of the arithmetic monodromy group Ĝ_{f,g}, and factoring f(T) − g(S) over \overline{𝔽}_{q} amounts to describing the orbits of {x_{i}} × {y_{j}} under the action of the geometric mondromy group G_{f,g} (to see the latter, use the canonical isomorphism between Gal (Ω_{f,g}\overline{𝔽}_{q}/\overline{𝔽}_{q}(T)) and G_{f,g}, and then apply Proposition 7.20 with F = \overline{𝔽}_{q}).

In what follows, let d = [𝔽̂_{f,g} : 𝔽_{q}].

Proposition 7.24. Let Φ be an irreducible factor of f(T)−g(S) over \overline{𝔽}_{q}[S, T], and let (x_{i_{0}}, y_{j_{0}}) be in the corresponding orbit under G_{f,g}. Then a non-zero constant multiple of Φ is defined over 𝔽_{q^{t}} if and only if t̄ is in the subgroup of ℤ/d generated by the image of Ĝ_{f,g}(x_{i_{0}}, y_{j_{0}}) under Ĝ_{f,g} → ℤ/d.

Proof. Let G_{t} consist of the elements in Ĝ_{f,g} whose image in ℤ/d is in the subgroup generated by t̄. Note: G_{t} is isomorphic to Gal (𝔽_{q^{t}}Ω_{f,g}/𝔽_{q^{t}}(T)) and the action on {x_{i}} and {y_{j}} are preserved by this isomorphism. Thus, by Proposition 7.20, irreducible factors of f(T)−g(S) in 𝔽_{q^{t}}[S, T] correspond to G_{t}-orbits of {x_{i}}×{y_{j}}.

Let Φ′ ∈ 𝔽_{q^{t}}[S, T] be the irreducible factor corresponding to the G_{t}-orbit containing (x_{i_{0}}, y_{j_{0}}). The nature of the correspondence in Proposition 7.20 implies that Φ divides Φ′ in \overline{𝔽}_{q}[S, T]. The degrees of Φ and Φ′ are determined by the sizes of the associated orbits, so Φ′ is a non-zero constant multiple of Φ if and only if these orbits are the same size. This in turn is equivalent to the following:

\frac{|G_{t}|}{|G_{t}(x_{i_{0}}, y_{j_{0}})|} = \frac{|G_{f,g}|}{|G_{f,g}(x_{i_{0}}, y_{j_{0}})|}, or equivalently \frac{d}{a} = \frac{|G_{t}|}{|G_{f,g}|} = \frac{|G_{t}(x_{i_{0}}, y_{j_{0}})|}{|G_{f,g}(x_{i_{0}}, y_{j_{0}})|}

where a = gcd(d, t). The ratio |G_{t}(x_{i_{0}}, y_{j_{0}})|/|G_{f,g}(x_{i_{0}}, y_{j_{0}})| determines the image of G_{t}(x_{i_{0}}, y_{j_{0}}) in ℤ/d, and the above equation holds if and only if this image is the subgroup generated by t̄. Finally, this occurs if and only if the image of Ĝ_{f,g}(x_{i_{0}}, y_{j_{0}}) in ℤ/d contains t̄.

We return to the case of general field F. Let V_{f} and V_{g} be the ℂ[Ĝ_{f,g}]-modules associated to the action of Ĝ_{f,g} on {x_{i}} and {y_{j}} respectively. Let χ_{f} and χ_{g} be the associated characters. Lemma 7.4 and Proposition 7.20 give the following.

Proposition 7.25. The number of irreducible factors of f(T) − g(S) in F [S, T] is equal to < χ_{f}, χ_{g} >.

Corollary 7.8 and Proposition 7.20 give the following.

Proposition 7.26. Suppose that the degrees of f and g are equal and greater than one, and that the action of Ĝ_{f,g} on {x_{i}} is doubly transitive. Then the following are equivalent. (7.10) χ_{f} = χ_{g}. (7.11) f(T) − g(S) is reducible in F [S, T]. (7.12) f(T) − g(S) factors into exactly two irreducible factors in F [S, T]. (7.13) V_{f} and V_{g} are isomorphic as ℂ[Ĝ_{f,g}]-modules.

We note that if F = 𝔽_{q} and χ_{f} = χ_{g}, then Corollary 3.12 (together with the observation in Lemma 7.1) implies that (f, g) is a SDP. Thus we get the following.

Corollary 7.27. Let F = 𝔽_{q}. Suppose (i) the degrees of f and g are equal, (ii) the action of Ĝ_{f,g} on {x_{i}} is doubly transitive, and (iii) f(T) − g(S) is reducible in 𝔽_{q}[S, T]. Then (f, g) is a SDP with multiplicity.

We can also use Proposition 7.26 to prove the following:

Lemma 7.28. Suppose f, g ∈ F [T] are polynomials of degree at least three which are linearly related on the inside over the separable closure F^{sep}. Suppose also that the action of Ĝ_{f,g} on {x_{i}} is doubly transitive. Then f and g are linearly related on the inside over F.

Proof. Let E be a finite Galois extension of F over which f and g are linearly related on the inside. This implies that f(T) − g(S) has a linear factor defined over E. Proposition 7.26 implies f(T) − g(S) has exactly two factors defined over E, one of which is linear and so the other must be of total degree greater than 1. Hence the factors are invariant under the natural Gal(E/F) action. Since f(T) − g(S) has a linear factor defined over F, the polynomials f and g are linearly related on the inside over F.

Lemma 7.19 gives the following.

Proposition 7.29. Let Φ be a factor of f(T) − g(S) of total degree k > 1 which is irreducible in F [S, T]. Suppose that the degrees of f and g are both equal to n > 1. Suppose also that the action of Ĝ_{f,g} on {x_{i}} is doubly transitive. Then

n − 1 | k(k − 1).

Proof. Let O be the orbit corresponding to Φ via the correspondence of Proposition 7.20. Note that deg_{S} Φ = deg Φ = k by Corollary 7.23. Apply Lemma 7.19 with A = {x_{i}}, B = {y_{j}} and Γ = O. By Proposition 7.20, |O| = nk.

Corollary 7.30. Suppose the degrees of f and g are both equal to n > 2, the action of Ĝ_{f,g} on {x_{i}} is doubly transitive, and f(T) − g(S) is reducible over F. Then the two irreducible factors of f(T) − g(S) have non-equal degrees.

Proof. There are exactly two factors by Proposition 7.26. Suppose they both have degree k, i.e., n = 2k. Then n − 1 = 2k − 1 is prime to k and k − 1. Thus n − 1 cannot divide k(k − 1), contradicting the previous proposition.

7.3. Polynomials With Doubly Transitive Monodromy Groups. Many of the above results (Proposition 7.26 to Corollary 7.30) depend on the double transitivity of monodromy groups. The classification of polynomials with doubly transitive geometric monodromy groups is well-known, at least when the degree is prime to the characteristic. We describe this classification. Throughout this section, let f ∈ F [T] have degree n at least 2, and let V_{f} be the associated ℂ[G_{f}] module with character χ_{f}.

Lemma 7.31. Suppose the arithmetic monodromy group Ĝ_{f} acts doubly transitively on {x_{i}}. Then f is indecomposable over F.

Proof. Suppose that f = f_{1} ∘ f_{2} with f_{1}, f_{2} ∈ F [T] of degrees at least two. Then

f(T) − f(S) = (T − S) Φ_{1}(f_{2}(S), f_{2}(T)) Φ_{2}(S, T)

where

Φ_{i}(S, T) =^{def} \frac{f_{i}(T) − f_{i}(S)}{T − S}.

Thus f(T) − f(S) has at least 3 irreducible factors, contradicting Proposition 7.26.

The following gives a partial converse.

Lemma 7.32. Suppose f ∈ F [T] is indecomposable over F with n = deg f composite and prime to the characteristic of F. Then the arithmetic and geometric mondromy groups of f act doubly transitively on {x_{i}}.

Proof. A theorem of Fried and MacRae implies that, since n is prime to the characteristic of F, f is indecomposable over \overline{F}. Thus G_{f} acts primitively on \{x_{i}\}. By Corollary 5.3, there is an element of G_{f} which acts as an n-cycle on {x_{i}}. Schur proved that a finite group G acting on a set with N elements acts doubly transitively if (i) the action is primitive, (iii) G contains an element acting as an N-cycle, and (iii) N is composite.

The above lemmas allow us to concentrate on the case n a prime. In the case n = 2 the action is trivially doubly transitive, thus we can restrict deg f = n to odd primes (different from the characteristic of F). Before finishing the classification, we describe important families of polynomials whose geometric monodromy groups do not act doubly transitively on {x_{i}}.

Consider the cyclic polynomials f(T) = T^{n}. Here G_{f} is a cyclic group of order n with generator acting on the roots {x_{i}} as an n-cycle. Furthermore, < χ_{f}, χ_{f} >= n and f(T) − g(S) factors into n linear factors. So when n > 2, the action of G_{f} on {x_{i}} is not doubly transitive.

The other main family of examples are the Chebyshev polynomials:

Definition 7.33. The Chebyshev polynomial τ_{n} of degree n is defined to be the polynomial in F [T] satisfying

τ_{n} (T + \frac{1}{T} ) = T^{n} + \frac{1}{T^{n}} .

The following well-known result is easily verified (the recursion can be used to prove existence).

Lemma 7.34. For every n ≥ 1 the nth Chebyshev polynomial τ_{n} exists and is unique (for any given characteristic). It is monic,

τ_{1}(T) = T,
τ_{2}(T) = T^{2} − 2, and
τ_{n+2}(T) = T · τ_{n+1}(T) − τ_{n}(T) for all n ≥ 1.

Remark 7.35. When F = ℚ we get τ_{n} ∈ ℤ[T]. Such Chebyshev polynomials arise from the trigonometric identity 2 cos(nT) = τ_{n}(2 cos(T)).

The following is well-known, and the second part is easily verified.

Lemma 7.36. Let n be an odd prime which is prime to the characteristic of F. Then the nth Chebyshev polynomial τ_{n} ∈ F [T] has a dihederal geometric monodromy group of order 2n, and this group acts on {x_{i}} via the standard dihederal action.

In particular, τ_{n}(T) − τ_{n}(S) has <χ_{τ_{n}}, χ_{τ_{n}}> = (n + 1)/2 irreducible factors. All are quadratic, except for the linear factor T − S. So the action of the geometric monodromy group on {x_{i}} is doubly transitive only for n = 3.

The following result of Burnside is an important piece in the classification.

Lemma 7.37. Suppose G acts effectively and transitively, but not doubly transitivly, on a set S of prime order l. Then G is isomorphic to a subgroup of the affine group 𝔽_{l} ⋊ 𝔽_{l}^{×}.

The last piece is provided by the following.

Lemma 7.38. Let f ∈ F [T] be a polynomial whose degree is a prime distinct from the characteristic of F. If the geometric monodromy group G_{f} is solvable, then f is linearly related, over \overline{F}, to either a cyclic polynomial or a Chebyshev polynomial.

Proof. This was first proved for the case f : ℙ^{1} → ℙ^{1} a tame cover ([Fri70]). For the general case see [Mül97]. Here we give the barest sketch of the proof.

If G_{f} is solvable, then by analyzing and comparing the possible ramification associated to Ω_{f}/F (x_{i}) and Ω_{f}/F (z), and by using the Riemann-Hurwitz formula, conclude that the cover f : ℙ^{1} → ℙ^{1} is totally ramified above one or two points. If it is totally ramified above two points, then G_{f} is cyclic, and a simple affine change of coordinates shows f is linearly related to the cyclic polynomial T^{n}. If the cover is totally ramified above only one point, G_{f} is dihedral of order 2n, and f can be shown to be linearly related to a Chebyshev polynomial.

Putting all this together gives the following classification.

Proposition 7.39. Suppose f ∈ F [T] has degree prime to the characteristic of F. Then the geometric monodromy group acts doubly transitively on the roots {x_{i}} if and only if one of the following hold. (7.14) f is indecomposable of composite degree. (7.15) f has degree 2. (7.16) f has degree 3 and is not linearly related to the cyclic polynomial T^{3}. (7.17) f has prime degree n > 3 and is not linearly related over \overline{F} to either the

cyclic polynomial or the Chebyshev polynomial of degree n.

Remark 7.40. Suppose that f ∈ F [T] has degree prime to the characteristic of F. It is easy to show that if f is linearly related over \overline{F} to a cyclic polynomial, then f is linearly related over F to a cyclic polynomial.

For Chebychev polynomials, the situation is more complicated. For any a ∈ F, and positive integer n define the Dickson Polynomial D_{n}(a, T) to be the cyclic polynomial if a = 0, or D_{n}(a, T) = a^{n/2}τ_{n}(a^{−1/2}T) if a ≠ 0. One can show that D_{n}(a, T) is in F [T] for all a ∈ F. Observe that any non-cyclic Dickson polynomial is linearly related over a quadratic extension of F to a Chebyshev polynomial.

From [Turn95, Lemma 1.9], it follows that if f is linearly equivalent over \overline{F} to a Chebyshev polynomial, then it is linearly equivalent over F to a Dickson polynomial.

7.4. A Special Class of Davenport Pairs. Recall that one way to construct a DP (f, g) is to set f = f′ ∘ h_{1} and g = g′ ∘ h_{2} where (f′, g′) is a SDP and h_{1}, h_{2} ∈ 𝔽_{q}[T] are exceptional. Such DP’s have the property that 1 ∈ D_{f,g}.

How does one construct DP’s (f, g) with 1 ∉ D_{f,g}? One strategy is to consider f, g ∈ 𝔽_{q}[T] with g = f ∘ l for some linear polynomial l ∈ \overline{𝔽}_{q}[T] not in 𝔽_{q}[T]. We show that the only examples of this type, when f is indecomposable of degree prime to the characteristic of 𝔽_{q}, are essentially of the form (T^{n}, aT^{n}) where a ∈ 𝔽_{q} is not an nth power in 𝔽_{q} (Corollary 7.43); in this case f(T) = T^{n} and l(T) = a^{1/n}T.

Lemma 7.41. Let f ∈ F [T] be linearly related over \overline{F} to a Chebyshev polynomial of odd degree prime to the characteristic of F. Suppose that f(αT + β) ∈ F [T] for some α, β ∈ \overline{F}, α ≠ 0. Then α, β ∈ F.

Proof. This follows from [Turn95, Lemma 1.9]. (Our τ_{n}(T) is equal to Turnwald’s D_{n}(1, T)).

Proposition 7.42. Let f, g ∈ F [T] be indecomposable polynomials of degree n prime to the characteristic of F. Suppose F is a perfect field. If f and g are linearly related on the inside over \overline{F} then either (i) f and g are linearly related on the inside over F, or (ii) f and g are both linearly related over F to the cyclic polynomial of degree n. In either case, f and g are linearly related over F.

Proof. Observe that n < 3 is trivial. If G_{f,g} acts doubly transitively on {x_{i}}, use Lemma 7.28. If G_{f,g} does not act doubly transitively, use Proposition 7.39 to reduce to the Chebyshev or cyclic case. In the case where f and g are linearly related over \overline{F} to the Chebyshev polynomial and n is an odd prime, use the previous lemma. Finally, in the cyclic case, Remark 7.40 says that f and g are linearly related to T^{n} over the base field F.

Corollary 7.43. Suppose that f ∈ F [T] is indecomposable of degree n prime to the characteristic of F where F is a perfect field. If g ∈ F [T] is linearly related to f on the inside over \overline{F}, but not over F, then there are linear l_{1}, l_{2}, l_{3} ∈ F [T] such that l_{1} ∘ f ∘ l_{2} = T^{n} and l_{1} ∘ g ∘ l_{3} = aT^{n} with a ∈ F not an nth power in F.

8. Main Results Concerning Indecomposability

The following results concern the case where one of the polynomials (f, say) of the pair (f, g) is indecomposable with degree prime to the characteristic. There are essentially two cases, depending on whether or not f is linearly related to a cyclic polynomial. Recall f is linearly related to a cyclic polynomial over 𝔽_{q} if and only if it is linearly related to a cyclic polynomial over \overline{𝔽}_{q}.

Theorem 8.1. Let f ∈ 𝔽_{q}[T] be indecomposable over 𝔽_{q}, non-exceptional, and of degree prime to the charactersitic of 𝔽_{q}. Let g ∈ 𝔽_{q}[T] be any polynomial where (f, g) forms a Davenport Pair, and let g = g_{1} ∘ g_{2} be the induced decomposition over 𝔽_{q} associated to (f, g).

If f is not linearly related to a cyclic polynomial then (f, g_{1}) is a SDP. In fact, it is a SDP with multiplicity: the associated characters χ_{f}, χ_{g_{1}} are equal.

If f is linearly related to a cyclic polynomial, then g = f ∘ h for some h ∈ E[T] where E is a finite extension of 𝔽_{q}. Furthermore, g = l∘f ∘h′ for some l, h′ ∈ 𝔽_{q}[T] with l linear, and f and l ∘ f are linearly related on the inside over \overline{𝔽}_{q}.

Remark 8.2. Throughout this paper we have adopted the convention that polynomials have non-zero derivatives. However, the above theorem (and the following theorem) remain valid for g with zero derivative (with a suitable definition of induced decomposition).

Proof. Let g = h_{1} ∘ h_{2} be the induced decomposition over \overline{𝔽}_{q} associated with the pair (f, g). (It turns out, at least in the non-cyclic cases, that the two induced decompositions, g = g_{1} ∘ g_{2} and g = h_{1} ∘ h_{2}, are equivalent).

Since (f, g) is a DP and f is non-exceptional, f(T)−g(S) is reducible in \overline{𝔽}_{q}[S, T] (Corollary 4.12). So f(T) − h_{1}(S) is also reducible in \overline{𝔽}_{q}[S, T] (Lemma 6.2). Since f is indecomposable over 𝔽_{q}, f is indecomposable over \overline{𝔽}_{q} (Theorem 3.5 of [FM69]). Thus the induced decompositions of both f and h_{1}, associated to the pair (f, h_{1}) over \overline{𝔽}_{q}, are trivial. Lemma 6.1, especially property (6.2), implies \overline{𝔽}_{q}Ω_{f} = \overline{𝔽}_{q}Ω_{h_{1}} and G_{f} = G_{h_{1}} = G_{f,h_{1}}. Finally, deg f = deg h_{1} (Corollary 6.3).

Now we show, under the assumption that f(T) − g(S) is reducible over 𝔽_{q}, that we can take h_{i} to be g_{i} for i = 1, 2. Note: the above argument that shows deg f = deg h_{1} can be modified to show that deg f = deg g_{1} under this reducibility assumption. Now, by Lemma 6.1,

𝔽_{q}(y_{1}) ∩ Ω_{f} = 𝔽_{q}(g_{2}(y_{1})) and \overline{𝔽}_{q}(y_{1}) ∩ (\overline{𝔽}_{q}Ω_{f}) = \overline{𝔽}_{q}(h_{2}(y_{1})).

Since \overline{𝔽}_{q}(𝔽_{q}(y_{1}) ∩ Ω_{f}) ⊆ \overline{𝔽}_{q}(y_{1}) ∩ (\overline{𝔽}_{q}Ω_{f}),

\overline{𝔽}_{q}(g_{2}(y_{1})) ⊆ \overline{𝔽}_{q}(h_{2}(y_{1})).

In particular, g_{2} = h′ ∘ h_{2} for some polynomial h′ ∈ \overline{𝔽}_{q}. Observe that deg h′ = 1 since deg h_{1} = deg g_{1}, so, after adjusting h_{1} and h_{2} by a linear map, h_{i} = g_{i}, for i = 1, 2.

We divide the remainder of the proof into three cases, using Proposition 7.39.

Case 1: G_{f} acts doubly transitively on the roots {x_{i}} and deg f > 2. By Proposition 7.26 and Corollary 7.30, f(T) − h_{1}(S) has exactly two irreducible factors over \overline{𝔽}_{q}, and these factors have non-equal degrees. By Lemma 6.2, the factorization of f(T) − g(S) is recovered by substituting h_{2}(S) for S in the factorization of f(T) − h_{1}(S). So the two irreducible factors of f(T) − g(S) have non-equal T -degrees, and must then be fixed under the action of Gal(\overline{𝔽}_{q}/𝔽_{q}). Thus the factorization of f(T) − g(S) is defined over 𝔽_{q}. As discussed above, this means we can take h_{1} = g_{1}. The result follows from Proposition 7.26 and Corollary 7.27.

Case 2: f is linearly related over \overline{𝔽}_{q} to a Chebyshev polynomial and n = deg f is an odd prime. Let G = G_{f} = G_{h_{1}}. By Lemma 7.36, G is isomorphic to a dihedral group of order 2n. Note: G acts transitively on both {x_{i}} and on the roots {u_{j}} of h_{1}(T) − z. Clearly, any two transitive actions of such a dihederal group on sets of order n are equivalent as permutation representations. Thus G(x_{1}) is G(u_{j}) for some j. Use the description of factorization of Remark 4.9 applied to G(u_{j}) = G(x_{1}) acting on {x_{i}}, to conclude that the factorization of f(T) − h_{1}(S) has exactly one linear factor Φ and (n − 1)/2 irreducible quadratic factors in \overline{𝔽}_{q}[S, T].

The factorization of f(T) − g(S) can be recovered by substituting h_{2}(S) for S in the factorization of f(T) − h_{1}(S) (Lemma 6.2). Since Φ(T, h_{2}(S)) is the unique irreducible factor of f(T) − g(S) of T -degree one, it is fixed under the action of Gal(\overline{𝔽}_{q}/𝔽_{q}). So f(T) − g(S) is reducible in 𝔽_{q}[S, T]. As discussed above, we can conclude that h_{1} = g_{1}. Also, Φ, the only linear factor of f(T) − g_{1}(S), must be defined over 𝔽_{q}. The existence of Φ implies that f and g_{1} are linearly related on the inside over 𝔽_{q}. Thus (f, g_{1}) forms a trivial SDP.

Case 3: f is linearly related over \overline{𝔽}_{q} to a cyclic polynomial. (This automatically includes the case deg f = 2). Let G = G_{f} = G_{h_{1}}. So G is isomorphic to a cyclic group of order n acting transitively on both {x_{i}} and on roots {u_{j}} of h_{1}(T) − z. Clearly, any two transitive actions of G on sets of order n are equivalent as permutation representations. Thus G(x_{1}) is G(u_{j}) for some j. Use Remark 4.9 to conclude that f(T) − h_{1}(S) factors over \overline{𝔽}_{q} as the product of n linear factors. This implies that h_{1} = f ∘ l_{0} for some l_{0} ∈ \overline{𝔽}_{q}[T] of degree 1. So g = f ∘ h where h = l_{0} ∘ h_{2}.

Using [FGS93, Lemma 4.1] and the fact that deg f is prime to p, we get a linear polynomial l′ ∈ \overline{𝔽}_{q}[T] such that f′ = f ∘ l′ and h′ = (l′)^{−1} ∘ h are in 𝔽_{q}[T], giving a decomposition g = f′ ∘ h′ over 𝔽_{q}. By Proposition 7.42, f′ = l ∘ f ∘ l′′ for some linear l, l′′ ∈ 𝔽_{q}[T]. By replacing h′ with l′′ ∘ h′, we obtain the decomposition g = l ∘ f ∘ h′.

Remark 8.3. We can get a variant of the above theorem by replacing the hypotheses (f, g) is a DP and f is not exceptional with the alternate hypothesis f(T) − g(S) reducible over \overline{𝔽}_{q} (keeping all the other hypotheses as they are).

Theorem 8.4. Let f, g ∈ 𝔽_{q}[T] be two polynomials such that V_{g}(𝔽_{q^{t}}) ⊆ V_{f}(𝔽_{q^{t}}) for all t. Suppose that f is indecomposable over 𝔽_{q} and has degree prime to the characteristic of 𝔽_{q}. Then there are polynomials g_{1}, g_{2} ∈ 𝔽_{q}[T] such that g = g_{1} ∘g_{2} and (f, g_{1}) is a SDP with multiplicity.

Proof. Consider Remark 8.3 together with Proposition 4.16. The case where f is not linearly related to a cyclic polynomial follows immediately.

In the cyclic case, consider the decomposition g = l ∘ f ∘ h′ of Theorem 8.1, and let f′ = l ∘ f. We know that f and f′ are linearly related on the inside over \overline{𝔽}_{q}; we claim that they are in fact linearly related on the inside over 𝔽_{q}, and so we can take g_{1} = f. Suppose otherwise and use Corollary 7.43 to reduce to the case f = T^{n} and f′ = aT^{n} where a ∈ 𝔽_{q} is not an nth power. Let t be such that q^{t} > deg h′ but that a is not an nth power in 𝔽_{q^{t}}. Then V_{f}(𝔽_{q^{t}}) contains only nth powers, but if c ∈ 𝔽_{q^{t}} not a root of h′ then g(c) is not an nth power, a contradiction.

Remark 8.5. In the above theorems, there are many cases where we can conclude that (f, g_{1}) is actually a trivial SDP. In other words, we can choose the decomposition g = g_{1} ∘ g_{2} in such a way that g_{1} = f itself.

For example, in case 2 of the above proof we concluded that (f, g_{1}) is a trivial SDP if n = deg f is an odd prime, and f is linearly related to a Chebyshev polynomial. In this case G_{f} is dihedral. In fact, there is no hope of having (f, g_{1}) be a non-trivial SDP unless G_{f} has two non-equivalent permutation representations on a set of n elements whose associated characters are equal (this follows from Proposition 7.42). This excludes most G_{f}.

The classification of finite simple groups, in the form of the classification of doubly transitive representations ([CKS76]), can be used to classify groups G with two non-equivalent faithful permutation representations acting on a set with n elements such that (i) the characters of the two actions are equal, (ii) the actions are doubly transitive, (iii) there is an element of G which acts as an n-cycle under the two actions. The conclusion is that

G = PSL_{2}(𝔽_{11}) and n = 11,

or

PSL_{k}(𝔽_{s}) ⊆ G ⊆ PΓL_{k}(𝔽_{s}) and n = (s^{k} − 1)/(s − 1) for some k ≥ 3.

(This result was conjectured in [Fri73]; see Theorem 2.7 and Section 9 of [Fri99] for more details, including historical information.) The field 𝔽_{s} appearing in the above list is called the characteristic field of the Chevalley group G.

This result allows us to strengthen the above theorems: if G = G_{f} and n are not of the above form, then the conclusion (f, g_{1}) is a SDP, can be replaced by the stronger conclusion g = f ∘ h for some h ∈ 𝔽_{q}[T].

However, not all the above groups are expected to occur as geometric monodromy groups of polynomials (for a given 𝔽_{q}). In fact, Guralnick has conjectured the following: the finite simple groups appearing as composition factors of geometric monodromy groups G_{f} as f varies over all polynomials, or even all rational functions, are, with finitely many exceptions (depending on the characteristic), the cyclic groups, the alternating groups, and the Chevalley groups with characteristic field containing 𝔽_{p}. Thus, we can expect among f ∈ 𝔽_{q}[T] with 𝔽_{q} of fixed characteristic p, that the fields 𝔽_{s} appearing as G_{f} as in the above classification should, with a finite number of exceptions depending on p, also be of characteristic p.

By way of contrast, in the case where 𝔽_{q} and 𝔽_{s} have the same characteristic, examples abound. Theorem 5.2 of [Fri99] (dependent on [Abh97]) states that, for any finite field 𝔽_{q}, any s a power of the characteristic of 𝔽_{q}, and any k ≥ 3, there is a non-trivial SDP (f, g) with χ_{f} = χ_{g} whose geometric monodromy group is G_{f} = G_{g} = PSL_{k}(𝔽_{s}).

References

[Abh97] S.S. Abhyankar, Projective polynomials, Proc AMS 125 (1997), 1643–1650.

[Ait98] W. Aitken, On value sets of polynomials over a finite field, Finite Fields Appl. 4 (1998), 441–449.

[Art23] E. Artin, Über die Zetafuncktionen gewisser algebraischer Zahlkörper, Math. Ann. 89 (1923), 147–156.

[Coh81] S.D. Cohen, Value sets of functions over finite fields, Acta Arith. XXXIX (1981), 339–359.

[CF95] S.D. Cohen and M.D. Fried, Lenstra’s proof of the Carlitz-Wan conjecture on exceptional polynomials: an elementary version, Finite Fields Appl. 1 (1995), 372–375.

[CKS76] C.W. Curtis, W.M. Kantor and G.M. Seitz, The 2-transitive permutation representations of the finite Chevalley groups, TAMS 218 (1976), 1–59.

[Den84] J. Denef, The rationality of the Poincaré series associated to the p-adic points on a variety, Invent. Math. 77 (1984), 1–23.

[DL] J. Denef and F. Loeser, Definable sets, motives and p-adic integrals, preprint.

[Fri70] M.D. Fried, On a conjecture of Schur, Mich. Math. J. 17 (1970), 41–45.

[Fri73] M.D. Fried, The field of definition of function fields and a problem in the reducibility of polynomials in two variables, Ill. J. of Math. 17 (1973), 128–146.

[Fri74] M.D. Fried, On a theorem of MacCluer, Acta Arith. XXV (1974), 122–127.

[Fri99] M.D. Fried, Separated variables polynomials and moduli spaces, Number Theory in Progress (Berlin-New York) (ed. J. Urbanowicz K. Gyory, H. Iwaniec, ed.), Walter de Gruyter, 1999, Proceedings of the Schinzel Festschrift, Summer 1997: Available from http://www.math.uci.edu/˜ mfried/#math, pp. 169–228.

[FGS93] M.D. Fried, R. Guralnick and J. Saxl, Schur covers and Carlitz’s conjecture, Israel J. 82 (1993), 157–225.

[FJ86] M.D. Fried and M. Jarden, Field arithmetic, Ergebnisse der Mathematik III, vol. 11, Springer-Verlag, 1986.

[FS76] M.D. Fried and G. Sacerdote, Solving diophantine problems over all residue class fields of a number field and all finite fields, Ann. of Math. 100 (1976), 203–233.

[FM69] M.D. Fried and R. E. MacRae, On the invariance of chains of fields, Ill. J. of Math. 13 (1969), 165–171.

[Frö67] A. Frölich, Local Fields, Algebraic Number Theory (ed. J. W. S. Cassels, A. Fröhlich),

Academic Press, London, 1967, pp. 1–41.

[GW97] R. Guralnick and D. Wan, Bounds for fixed point free elements in a transitive group and applications to curves over finite fields, Israel J. 101 (1997), 255–287.

[Mül97] P. Müller, A Weil-bound free proof of Schur’s conjecture, Finite Fields Appl. 3 (1997),

25 – 32.

[Mül98] P. Müller, Kronecker conjugacy of polynomials, TAMS 350 (1998), 1823–1850.

[Ser79] J.-P. Serre, Local Fields, Graduate Texts in Mathematics, vol. 67, Springer-Verlag, 1979.

[Turn95] G. Turnwald, On Schur’s conjecture, J. Austral. Math Soc. Ser. A 58 (1995), 312–357.

[vdW35] B. L. van der Waerden, Die Zerlegungs- und Träheitsgruppe als Permutationsgruppen, Math. Ann. 111 (1935), 731–733.

Cal. State, San Marcos, CA 92096, USA

   E-mail address: waitken@csusm.edu

UC Irvine, Irvine, CA 92697, USA

   E-mail address: mfried@math.uci.edu

30 W. AITKEN, M. FRIED, L. HOLT

Cal. State, San Marcos, CA 92096, USA

E-mail address: lholt@csusm.edu