GENERATORS AND IRREDUCIBLE POLYNOMIALS OVER FINITE FIELDS

Daqing Wan Department of Mathematics The Pennsylvania State University University Park, PA 16802 E-mail: wan@math.psu.edu

Abstract. Weil’s character sum estimate is used to study the problem of constructing generators for the multiplicative group of a finite field. An application to the distribution of irreducible polynomials is given, which confirms an asymptotic version of a conjecture of Hansen-Mullen

1. Introduction

Let F_{q} be a finite field of q elements with characteristic p. For a positive integer m > 1, let F_{q^{m}} be an extension field of F_{q} of degree m. One of the basic problems in computational finite field theory is to construct a set of generators for the multiplicative group F_{q^{m}}^{∗}. Ideally, one would like to have a primitive element of F_{q^{m}}^{∗}. However, the construction (even testing) of a primitive root is at present deterministically difficult. In this paper, we consider three weaker questions about generators of finite fields. The first one is as follows.

Question 1.1. For which pair (q, m), the multiplicative group F_{q^{m}}^{∗} is generated by the line F_{q} + α for every α with F_{q^{m}} = F_{q}(α).

This question also arises from several applications such as graph theory [Ch] and number theoretic algorithms [Le2]. For a given α with F_{q^{m}} = F_{q}(α), define the difference graph G(m, q, α) to be the graph whose vertices are the elements of the multiplicative group F_{q^{m}}^{∗}, where two elements β_{1} and β_{2} are connected if and only if β_{1}/β_{2} = (α +a) for some a in the ground field F_{q}. This is a regular graph of degree q, i.e., each vertex is connected to exactly q other vertices. The difference graph is studied in [Ch] and more generally in [Li]. It is clear that the graph G(m, q, α)

Typeset by AMS-TEX

Partially supported by NSF

1991 Mathematics Subject Classification Numbers: 11T24, 11T55

is connected if and only if F_{q^{m}}^{∗} is generated by the line F_{q} + α. Thus, the graph G(m, q, α) is connected for every α with F_{q^{m}} = F_{q}(α) if and only if Question 1.1 has a positive answer for the pair (q, m).

It is not hard to prove that if q > (m − 1)^{2}, then the answer of Question 1.1 is positive and thus the graph G(m, q, α) is connected, see [Ch]. If q^{m} − 1 (m > 1) is a (Mersenne) prime, the answer of Question 1.1 is clearly positive. Thus, we can assume that q^{m} − 1 is not a prime. It is unknown if the bound q > (m − 1)^{2} can be substantially weakened. In order to understand how close to the truth the bound q > (m−1)^{2} might be, here we investigate when Question 1.1 has a negative answer. We have

Theorem 1.2. If q^{m} − 1 has a divisor d > 1 such that

m ≥ 2(q log_{q} d + log_{q}(q + 1)),  (1.1)

then the multiplicative group F_{q^{m}}^{∗} is not generated by the line F_{q} + α for some α with F_{q^{m}} = F_{q}(α).

This result shows that in some sense the bound q > (m − 1)^{2} is not too far from being sharp, although we still do not know what would happen for those m in the interval

\sqrt{q} + 1 ≤ m < 2(q log_{q} d + log_{q}(q + 1)).

If q is odd, we can take d = 2 in Theorem 1.2. If q > 2, we can take d = (q − 1) > 1 and the bound in (1.1) essentially reduces to the bound m ≥ 2(q + 1) first observed by Lenstra. I owe entirely to Lenstra for suggesting to me the problem and the possibility of getting a better bound if q^{m} − 1 has a small divisor d. If q = 2, no obvious factor of 2^{m} − 1 is known unless m is a composite number. See section 3 for a complete result of Lenstra in the case q = 2 and m composite.

Our second question concerns the distribution of primitive normal elements. Even though the construction of a primitive element for F_{q^{m}}^{∗} is difficult, Shoup constructed a subset of small size which contains a primitive element of F_{q^{m}}^{∗}. More precisely, Shoup [Sh] showed that if α in F_{q^{m}} is of degree m over F_{q}, then there is a monic irreducible polynomial g(T) in F_{q}[T] of degree at most ⌈6 log_{q} m + C log_{q} log q⌉ such that g(α) is a primitive element of F_{q^{m}}^{∗}, where C is an absolute constant. If q is small, this result gives a polynomial size subset containing a primitive element and thus yields a polynomial time search algorithm in the sense of Shoup. A closely related result was obtained by Shparlinski [Shp, Theorem 2.4], see Corollary 4.3 for a unified description. A natural question is then to try to extend Shoup’s result to primitive normal elements. Namely, Question 1.3. Let α be a normal element of F_{q^{m}} over F_{q}. Is there an irreducible polynomial g(T) over F_{q} of small degree such that g(α) is a primitive normal element of F_{q^{m}} over F_{q}.

In this question, we assumed that the given α is already normal. If α is not normal, then the answer can be negative. For example, if the minimal polynomial of α is T^{m} − aT − b, Newton’s formula shows that for each 0 ≤ i ≤ m − 2, the power α^{i} has trace zero. This implies that if g(T) is a polynomial over F_{q} of degree less than m − 1, then g(α) is not normal. Thus, we should assume that α is normal. This is not a severe restriction because a normal element can always be constructed deterministically in polynomial time, see Lenstra [Le1] or Bach-Driscoll-Shallit [BDS]. Theorem 1.4. There are absolute positive constants C_{1} and C_{2} such that if

q ≥ C_{1}m log^{2} m  (1.2)

and if α is a normal element of F_{q^{m}} over F_{q}, then there is a primitive normal element of the form g(α), where g(T) is a monic irreducible polynomial over F_{q} of degree at most ⌈6 log_{q} m + C_{2} log_{q} log q⌉.

This result shows that Question 1.3 has a positive answer if q is suitable large compared to m. We do not know if the condition in (1.2) can be removed.

Our third question concerns the distribution of irreducible polynomials. Based on various tables, Hansen-Mullen [HM, Conjecture B] proposed the following conjecture about uniform distribution of irreducible polynomials. We assume that the degree is at least three as the linear and quadratic cases are easy. Conjecture 1.5 (Hansen-Mullen). Let m and n be positive integers with m ≥ 3 and m ≥ n ≥ 1. For any given element a ∈ F_{q} with a ≠ 0 if n = 1, there exists a monic irreducible polynomial over F_{q} of degree m such that the coefficient of T^{n−1} is the given element a.

Hansen-Mullen showed that their conjecture is true if n = 1 by a very simple argument: If α is a primitive element of F_{q^{m}}^{∗}, then the norm c = α^{(q^{m}−1)/(q−1)} is a primitive element of F_{q}^{∗} and thus one can write a = c^{k} for some k ≤ q − 2 if a ≠ 0. The element α^{k} is not in any proper subfield of F_{q^{m}} and has norm equal to a. Thus, the conjecture is true if n = 1. By a result of Cohen [Co] on primitive elements, the conjecture is also true if n = m. By a recent ressut of Han [Ha1-2] on primitive roots, the conjecture is true if m is large and n = m − 1. The following result confirms an asymptotic version of the Hansen-Mullen conjecture. Theorem 1.6. If either m ≥ 36 or q > 19, then there is a monic irreducible polynomial in F_{q}[T] of the form g(T) = T^{m}+a_{m−1}T^{m−1}+⋯+a_{n}T^{n}+a_{n−1}T^{n−1}+ ⋯ + a_{1}T + 1 with a_{n−1} = a, where m, n and a are as in the above conjecture.

Actually, the number of possible exceptions is much smaller. It should be quite realistic to completely settle Conjecture 1.5 by more detailed arguments with perhaps some computer calculations. In our proof here, we use only crude estimates in favor of their simplicity.

Acknowledgment. Portion of this paper (most of sections 2-3) is based on some unpublished notes of H. W. Lenstra Jr. on L-functions over finite fields. I would like to thank him for valuable discussions and for allowing me to include some of his unpublished notes here.

2. Estimates of character sums

In this section, we recall several forms of Weil’s character sums arising from Lfunctions on the affine line. Our exposition of this section was greatly influenced by Lenstra’s unpublished notes.

Let F_{q}[T] be the polynomial ring in one variable over F_{q}. A multiplicative character for F_{q}[T] is a pair (χ, f), where f ∈ F_{q}[T] is a monic polynomial and χ : (F_{q}[T]/fF_{q}[T])^{∗} ⟶ C^{∗} is a group homomorphism from the invertible elements of the residue class ring to the non-zero complex numbers. Though it is important to keep track of f, one often just refers to χ as the character. For g ∈ F_{q}[T], define

χ(g) = \{ \begin{matrix}χ(g mod f), & if gcd (g, f) = 1 \\ 0, & otherwise. \end{matrix}

This defines a multiplicative function of the polynomial ring F_{q}[T]. The L-function L(χ, t) associated to such a character is defined to be

L(χ, t) = ∑_{g} χ(g)t^{degg},  (2.1)

where the summation is over all monic polynomials in F_{q}[T]. The Euler product form of L(χ, t) is (by unique factorization)

L(χ, t) = ∏_{g irred.} \frac{1}{(1 − χ(g)t^{degg})}

= exp(∑_{d=1}^{∞} S_{d} \frac{(χ)}{d}t^{d}),

(2.2)

where S_{d}(χ) is the character sum

S_{d}(χ) = ∑_{k|d} k ∑_{deg(g)=k,g irred.} χ(g^{d/k}) = ∑_{deg(g)=d} Λ(g)χ(g)  (2.3)

and Λ(g) is the von Mangoldt function: Λ(g) is equal to deg(P) if g is a power of an irreducible polynomial P, and is otherwise equal to zero. In the case d = 1, we get the character sum

S_{1}(χ) = ∑_{a∈F_{q}} χ(T − a).  (2.4)

If χ ≠ 1, one checks that L(χ, t) is a polynomial of degree at most deg(f) − 1 with constant term 1. To see this, let n ≥ deg(f). For each h(mod f), there are exactly q^{n−deg(f)} monic polynomials g of degree n such that g ≡ h(mod f). Thus, for n ≥ deg(f),

∑_{degg=n} χ(g) = q^{n− degf} ∑_{h(modf)} χ(h) = 0.

This shows that for some positive integer r ≤ degf −1, one has L(χ, t) = ∏_{i=1}^{r}(1− ρ_{i}t), where the ρ_{i} are complex numbers. In terms of character sums, one sees that for all positive integers d ≥ 1,

S_{d}(χ) = −ρ_{1}^{d} − ρ_{2}^{d} − ⋯ − ρ_{r}^{d}.  (2.5)

Weil’s result on the Riemann hypothesis of L-functions gives (see [We] and [Le2])

Theorem 2.1 (Weil). (i). If χ ≠ 1, then

|S_{d}(χ)| ≤ (deg f − 1)q^{d/2}.  (2.6.1)

(ii). If χ ≠ 1 but χ(F_{q}^{∗}) = 1, then

|1 + S_{d}(χ)| ≤ (deg f − 2)q^{d/2}.  (2.6.2)

Note that in case (ii), the degree of f is automatically at least two since χ ≠ 1 but χ(F_{q}^{∗}) = 1. Now, we use (2.6.1) to derive several interesting consequences. The first one was conjectured by Katz [Ka], observed by Lenstra to be a consequence of Theorem 2.1 by restricting the following character χ to the cyclic subalgebra F_{q}[x] of A.

Corollary 2.2. Suppose that we are given an arbitrary finite n-dimensional commutative F_{q}-algebra A, an element x ∈ A, and a character χ of the multiplicative group A^{∗} (extended by zero to all of A) which is non-trivial on F_{q}[x]. Then,

| ∑_{a∈F_{q}} χ(a − x)| ≤ (n − 1)\sqrt{q}.  (2.7)

Corollary 2.3. Let f_{1}(T), …, f_{n}(T) be n monic pairwise prime polynomials in F_{q}[T] whose largest squarefree divisors have degrees d_{1}, …, d_{n}. Let χ_{1}, …, χ_{n} be multiplicative non-trivial characters of the finite field F_{q}. Assume that for some 1 ≤ i ≤ n, the polynomial f_{i}(T) is not of the form g(T)^{ord(χ_{i})} in F_{q}[T], where ord(χ) is the smallest positive integer d such that χ^{d} = 1. Then, we have the estimate

| ∑_{x∈F_{q}} χ_{1}(f_{1}(x)) ⋯ χ_{n}(f_{n}(x))| ≤ (∑_{i=1}^{n} d_{i} − 1)\sqrt{q}.  (2.8)

If χ_{i}^{d_{i}} = 1 for all i, then the right side of (2.8) can be improved to (∑_{i=1}^{n} d_{i} − 2)\sqrt{q} + 1. Proof. By factoring the f_{i}(T) if necessary, we may assume that the f_{i}(T) are distinct, monic and irreducible. Furthermore, there is at least one i such that χ_{i} is non-trivial. Let f(T) = f_{1}(T) ⋯ f_{n}(T). For each 1 ≤ i ≤ n, let ξ_{i} be a root of the irreducible polynomial f_{i}(T) in some extension field. Then, the residue class ring F_{q}[T]/(f) is isomorphic to the direct sum of the fields F_{q}[ξ_{i}], where T is mapped to the vector (ξ_{1}, …, ξ_{n}). Define a character χ of F_{q}[T]/(f) as follows: For g(T) ∈ F_{q}[T], define χ(g) to be the product ∏_{i=1}^{n} χ_{i}( Norm_{F_{q}[ξ_{i}]/F_{q}}(g(ξ_{i}))). Since the norm function from F_{q}[ξ_{i}] to F_{q} is surjective, the character χ_{f_{i}}(g) = χ_{i}( Norm(g(ξ_{i}))) is non-trivial on F_{q}[T] if χ_{i} is non-trivial on F_{q}. By the Chinese remainder theorem, the product character χ = ∏_{i} χ_{f_{i}} is a non-trivial character on (F_{q}[T]/(f))^{∗}. One computes that

χ(a − T) = χ_{1}(f_{1}(a)) ⋯ χ_{n}(f_{n}(a)),

where a ∈ F_{q}. Estimate (2.8) then follows from (2.7). If χ_{i}^{d_{i}} = 1 for all i, then χ(a) = ∏_{i} χ_{i}(a^{d_{i}}) = 1 for all a ∈ F_{q} and estimate (2.8) can be improved as stated.

Weil’s theorem can be used to give sharp estimates of certain types of incomplete character sums. Here we give the following example. Let f_{1}(T), …, f_{n}(T) be nonconstant polynomials defined over the extension field F_{q^{m}}. For 1 ≤ i ≤ n, let χ_{i} be multiplicative non-trivial characters of the extension field F_{q^{m}}. Define the following incomplete character sum

S(d; χ) = ∑_{a∈F_{q}} χ_{1}(f_{1}(a)) ⋯ χ_{n}(f_{n}(a)),  (2.9)

where the sum is over all a in the subfield F_{q}. Corollary 2.3 extends to this type of incomplete sums. Corollary 2.4. Let the f_{i}(T) for 1 ≤ i ≤ n be pairwise prime polynomials. Let D be the degree of the largest squarefree divisor of ∏_{i=1}^{n} f_{i}(t). Suppose that for some 1 ≤ i ≤ n, there is a root ξ_{i} of multiplicity m_{i} of f_{i}(T) such that the character χ_{i}^{m_{i}} is non-trivial on the set Norm_{F_{q^{m}} [ξ_{i}]/F_{q^{m}}} (F_{q}[ξ_{i}]). Then, we have the estimate

|S(d; χ)| ≤ (mD − 1)\sqrt{q}.  (2.10)

Proof. The proof is similar to the proof of Corollary 2.3. By factoring the f_{i}(T) if necessary, we may assume that the f_{i}(T) for 1 ≤ i ≤ n are distinct and monic irreducible over F_{q^{m}}. Furthermore, there is some 1 ≤ i ≤ n such that χ_{i} is nontrivial on the set Norm_{F_{q^{m}} [ξ_{i}]/F_{q^{m}}} (F_{q}[ξ_{i}]). Let F_{i}(T) be the product of all distinct conjugates of f_{i}(T) over F_{q}. Then, the F_{i}(T) are defined and irreducible over the ground field F_{q}. Let f(T) = F_{1}(T) ⋯ F_{n}(T). This is a squarefree polynomial of degree at most mD. Let ξ_{i} be a root of f_{i}(T). Define a multiplicative character χ_{f} on (F_{q}[t]/(F))^{∗} by χ_{f}(g) = ∏_{i=1}^{n} χ_{i}(Norm_{F_{q^{m}} [ξ_{i}]/F_{q^{m}}} (g(ξ_{i}))). One checks that χ_{f}(a − T) = ∏_{i=1}^{n} χ_{i}(f_{i}(a)). Using our assumption and the Chinese remainder theorem as in the proof of Corollary 2.3, we conclude that χ_{f} is non-trivial and the corollary follows from (2.7).

The following corollary gives a simple result on the number of subfield solutions of certain diophantine equations.

Corollary 2.5. Let f(T) be a polynomial in F_{q^{m}}[T] of degree D. Let d be a positive integer. Let N_{f} be the number of solutions of the equation y^{d} = f(x) in F_{q^{m}} such that x belongs to the subfield F_{q}. Assume that f(T) has a root ξ of multiplicity m_{0} such that (m_{0}, d) = 1 and Norm_{F_{q^{m}} [ξ]/F_{q^{m}}} (F_{q}[ξ]) = F_{q^{m}}. Then,

|N_{f} − q| ≤ (mD − 1)(d − 1)\sqrt{q}.  (2.11)

Proof. We use χ to denote a multiplicative character of the extension field F_{q^{m}}. Using Corollary 2.4, we deduce that

\begin{aligned}|N_{f} − q| & = |_{∑_{χ^{d}=1} ; χ≠1} ∑_{x∈F_{q}} χ(f(x)) | \\ & ≤ (mD − 1)(d − 1)\sqrt{q}. \end{aligned}

The corollary is proved.

Remark 2.6. As an example of Corollary 2.5, we may take f(T) to have a linear factor T − α of multiplicity one, where α has degree m over F_{q}. Another example is to take f(T) to have a monic irreducible factor g(T) over F_{q^{m}} of multiplicity one such that g(0) is a primitive element of F_{q^{m}}. We note that Corollary 2.5 can be false without the assumption on ξ. An easy counterexample is to take f(T) = βT, where β is a d-th power non-residue in F_{q^{m}} and (d, q − 1) = 1.

A similar result on subfield solutions holds for the Artin-Schreier equation.

Corollary 2.7. Let f(T) be a polynomial in F_{q^{m}}[T] of degree D. Let N_{f} be the number of solutions of the equation y^{p} − y = f(x) in F_{q^{m}} such that x belongs to the subfield F_{q}. Assume that tr(f(T)) is not of the form r(T)^{p} − r(T) + c in F̄_{q}(T), where tr is the trace from F_{q^{m}} to F_{q} and it acts trivially on T. Then,

|N_{f} − q| ≤ (D − 1)(p − 1)\sqrt{q}.  (2.12)

Proof. Let Ψ_{p} be a non-trivial additive character of F_{p}. Let g(T) be the polynomial tr(f(T)) of degree D defined over F_{q}. Then,

|N_{f} − q| ≤ | ∑_{a∈F_{p}^{∗}} ∑_{x∈F_{q}} Ψ_{p}(a · tr_{F_{q^{m}} /F_{p}}(f(x))) |

= | ∑_{a∈F_{p}^{∗}} ∑_{x∈F_{q}} Ψ_{p}(a · tr_{F_{q}/F_{p}}(g(x))) |

≤ (p − 1)(D − 1)\sqrt{q},

where the last inequality follows from Weil’s well known estimate for additive character sums.

For applications to the Hansen-Mullen conjecture, we give two estimates of character sums over irreducible polynomials. Let χ be a character of (F_{q}[T]/(f))^{∗}. For a positive integer d, define

S′_{d}(χ) = ∑_{deg(g)=d} χ(g),  (2.13)

where g runs over all monic irreducible polynomials of degree d over F_{q}.

Corollary 2.8. (i). If χ ≠ 1, then

|S′_{d}(χ)| < \frac{1}{d}(deg (f) + 1)q^{d/2}.  (2.14.1)

(ii). If χ ≠ 1 but χ(F_{q}^{∗}) = 1, then

|\frac{1}{d} + S′_{d}(χ)| < \frac{1}{d}deg (f)q^{d/2}.  (2.14.2)

Proof. Let π′_{d} be the number of elements which are in a proper subfield of F_{q^{d}}. Clearly,

π′_{d} ≤ (q^{d/2} + ∑_{k|d, k<d/2} q^{k}) < 2q^{d/2}.  (2.15)

If χ is non-trivial, then Weil’s estimate (2.6.1) shows that

|S′_{d}(χ)| ≤ \frac{1}{d}(|S_{d}(χ)| + π′_{d})

< \frac{1}{d}((deg (f) − 1)q^{d/2} + 2q^{d/2})

= \frac{1}{d}(deg (f) + 1)q^{d/2}.

This proves (2.14.1). The proof of (2.14.2) is the same except that we need to use (2.6.2).

A closely related character sum is to let g run over all irreducible polynomials with constant term 1 instead of monic irreducible polynomials. Thus, we define

S′′_{d}(χ) = ∑_{deg(g)=d} χ(g),  (2.16)

where g runs over all irreducible polynomials over F_{q} (not necessarily monic) of degree d with constant term 1.

Corollary 2.9. Let χ ≠ 1 but χ(F_{q}^{∗}) = 1. For all d > 1, we have

|\frac{1}{d} + S′′_{d}(χ)| < \frac{1}{d}deg(f)q^{d/2}.  (2.17)

Proof. Since χ(F_{q}^{∗}) = 1, we have

χ(g(T)) = χ(\frac{g(T)}{g(0)})

for all monic irreducible polynomials g(T) ≠ T. If g(T) is a monic irreducible polynomial of degree d > 1, then g(T)/g(0) is an irreducible polynomial of degree d with constant term 1 and vice versa. Thus,

S′_{d}(χ) = S′′_{d}(χ).

The proof is complete by (2.14.2).

3. Multiplicative groups generated by linear expressions

We now apply the character sum estimates of §2 to study Question 1.1. We have

Theorem 3.1. If q^{m} − 1 has a divisor d > 1 such that

m ≥ 2(q log_{q} d + log_{q}(q + 1)),

then the multiplicative group F_{q^{m}}^{∗} is not generated by the line F_{q} + α for some α with F_{q^{m}} = F_{q}(α).

Proof. Let d > 1 be a divisor of q^{m} − 1. Let N_{m}(d) be the number of α in F_{q^{m}} such that α has degree m over F_{q} and α+a is a d-th power in F_{q^{m}} for every a ∈ F_{q}. Let A_{m} be the subset consisting of α in F_{q^{m}} which lies in a proper subfield of F_{q^{m}}. To prove Theorem 3.1, it suffices to prove that N_{m}(d) > 0.

A standard character sum argument shows that

N_{m}(d) = \frac{1}{d^{q}} ∑_{α∈F_{q^{m}}} ∏_{a∈F_{q}}( ∑_{χ^{d}=1} χ(α + a)) − \frac{1}{d^{q}} ∑_{α∈A_{m}} ∏_{a∈F_{q}}( ∑_{χ^{d}=1} χ(α + a)), (3.1)

where χ(0) = 1 if χ is the trivial character. The second sum is at most 2q^{m/2} by (2.15). Corollary 2.3 then implies that

|N_{m}(d) − \frac{q^{m}}{d^{q}} | < \frac{d^{q} − 1}{d^{q}}(q − 1)q^{m/2} + 2q^{m/2}.  (3.2)

This shows that

d^{q}N_{m}(d) > q^{m} − (d^{q} − 1)(q − 1)q^{m/2} − 2d^{q}q^{m/2}
= q^{m} − (qd^{q} − q + 1 + d^{q})q^{m/2}
> q^{m} − d^{q}(q + 1)q^{m/2}.

The last number is non-negative if

q^{m/2} ≥ (q + 1)d^{q}, namely, m ≥ 2(q log_{q} d + log_{q}(q + 1)).

The theorem is proved.

In the case q = 2, no obvious factor of 2^{m} − 1 is known unless m is a composite number. If q = 2 and m is composite, the following complete result is due to Lenstra.

Theorem 3.2. If q = 2 and m is composite, then the multiplicative group F_{q^{m}}^{∗} is generated by the line F_{q} + α for every α with F_{q^{m}} = F_{q}(α) if and only if m = 4 or m = 6.

Proof. If q = 2, a detailed examination of the first sum in (3.1) gives a slightly better estimate:

|N_{m}(d) − \frac{2^{m}}{d^{2}} | < \frac{(d − 1)^{2}}{d^{2}} 2^{m/2} + 2q^{m/2}.  (3.3)

In order for Question 1.1 to have a negative answer, it suffices to have a proper divisor d of 2^{m} − 1 satisfying the inequality

2^{m} ≥ (d − 1)^{2}2^{m/2} + 2 · d^{2}2^{m/2}, namely, 2^{m/2} ≥ 3 · d^{2} − 2d + 1.  (3.4)

Since m is composite, let u be the smallest prime factor of m and write m = uk. Then d = 2^{u} − 1 is a proper divisor of 2^{m} − 1 and the second inequality in (3.4) becomes

2^{uk/2} ≥ 3(2^{u} − 1)^{2} − 2(2^{u} − 1) + 1 = 3 · 2^{2u} − 8 · 2^{u} + 6.  (3.5)

For u = 2, inequality (3.5) is satisfied whenever k ≥ 5. For u = 3, inequality (3.5) is satisfied whenever k ≥ 5. For u ≥ 5, inequality (3.5) is satisfied whenever k ≥ u ≥ 5. Since u is the smallest prime factor of m, we are left only with the following cases m = 4, 6, 8, 9.

Case m = 8. We take d = 3 (a factor of 2^{8} − 1) and use the method in the proof of Theorem 3.1. All proper subfields of F_{2^{8}} are contained in F_{2^{4}} and the last term of (3.3) can be improved to 2^{4}. By (3.3),

N_{8}(d) ≥ \frac{2^{8}}{3^{2}} − \frac{2^{2}}{3^{2}} 2^{4} − 2^{4} > 0.

This shows that the theorem is true for q = 2 and m = 8.

Case m = 9. All proper subfields of F_{2^{9}} are contained in F_{2^{3}}. Let β ∈ F_{2^{3}} − F_{2}. We claim that the polynomial g(T) = T^{3} + βT^{2} + (β + 1)T + 1 is irreducible over F_{2^{3}}. One checks that g(0) = g(1) = 1. This and the irreducibility of g(T) shows that if α is a root of g(T), then the norms of α and α + 1 from F_{2^{3}} to F_{2^{3}} are 1. Thus, the two elements α and α + 1 can not generate F_{2^{9}}. To prove the claim, it suffices to prove that the polynomial g(T) has no zeros in F_{2^{3}}. Clearly, g(T) has no zeros in F_{2}. If γ is an element of F_{2^{3}} − F_{2}, then γ satisfies either γ^{3} + γ + 1 = 0 or γ^{3} + γ^{2} + 1 = 0. In the first case, if g(γ) = 0, then β(γ^{2} + γ) = 0 and we have a contradiction. In the second case, if g(γ) = 0, then (β + 1)(γ^{2} + γ) = 0 and again we have a contradiction. The claim is proved.

Case m = 4. Since 2^{4} − 1 = 3 · 5, if α and α + 1 do not generate F_{2^{4}}^{∗}, both α and α + 1 must be primitive 5-th roots of unity. This means that both α and α + 1 satisfy the equation T^{4} + T^{3} + T^{2} + T + 1 = 0. This implies that α(α + 1) = 0 and we have a contradiction. Thus, the theorem is true for q = 2 and m = 4.

Case m = 6. Since 2^{6} − 1 = 7 · 9, if α is a 7-th power, then α has to be a primitive 9-th root of unity. Since all primitive 9-th roots have trace zero to F_{2^{2}}, α + 1 can not be a primitive 9-th root of unity. Thus, α can not be a 7-th power and the set {α, α + 1} generates the multiplicative group F_{2^{6}}^{∗}. By symmetry, if α + 1 is a 7-th power, the same argument works. If both α and α + 1 are a cubic power, then their norms to F_{2^{2}} are also a cubic power, which is necessarily 1. If g(T) = T^{3} + uT^{2} + vT + w is the irreducible polynomial of α over F_{2^{2}}. Then both g(0) and g(1) are 1. That gives w = 1 and u+v = 1. But then u^{3}+u·u^{2}+vu+1 = 0 (note that u, v ∈ F_{2^{2}} −F_{2}) shows that g(T) is still reducible. Thus, α and α+1 can not both be a cubic power. This implies that α and α+1 generate the multiplicative group of F_{2^{6}}. Thus, the theorem is true for q = 2 and m = 6. The theorem is proved.

To conclude this section, we include a more precise version of the bound q > (m−1)^{2} mentioned in the introduction. Let d(m, q) be the smallest positive integer d such that for all α with F_{q^{m}} = F_{q}(α), each element β in F_{q^{m}}^{∗} can be expressed as a product of at most d elements from F_{q} + α, that is, there are a_{i} ∈ F_{q} (1 ≤ i ≤ d) such that β = (α + a_{1}) ⋯ (α + a_{d}). If such a positive integer d does not exist, we define d(m, q) = ∞. The number d(m, q) is simply the maximal diameter of the family of difference graphs G(m, q, α) parametrized by α.

Theorem 3.3. Assume that q > (m − 1)^{2}. Then

d(m, q) ≤ ⌈2m + \frac{4m log(m − 1)}{log q − 2 log(m − 1)}⌉,

where ⌈x⌉ denotes the smallest integers ≥ x.

Proof. Let k be a positive integer. For β ∈ F_{q^{m}}^{∗}, let N_{k}(β, α) be the number of solutions of the equation β = (α + a_{1}) ⋯ (α + a_{k}), where the a_{i} take values in the ground field F_{q}. Then,

\begin{aligned}N_{k}(β, α) & = \frac{1}{q^{m} − 1} ∑_{a_{i}∈F_{q}} ∑_{χ} χ^{−1}(β)χ((α + a_{1}) ⋯ (α + a_{k})) \\ & = \frac{q^{k}}{q^{m} − 1} + \frac{1}{q^{m} − 1} ∑_{χ≠1} χ^{−1}(β)( ∑_{a∈F_{q}} χ(α + a))^{k}, \end{aligned}  (3.6)

where χ runs over all multiplicative characters of F_{q^{m}}^{∗}. By corollary 2.2, we deduce that

|N_{k}(β, α) − \frac{q^{k}}{q^{m} − 1}| < (m − 1)^{k}\sqrt{q}^{k}.  (3.7)

In order for N_{k}(β, α) > 0 for all β, it suffices to have the inequality

q^{k/2} ≥ q^{m}(m − 1)^{k}.

Solving this inequality, one gets

k ≥ 2m + \frac{4m log(m − 1)}{log q − 2 log(m − 1)}.

The theorem is proved.

Theorem 3.3 is essentially the same as Chung’s diameter bound

d(m, q) ≤ ⌈2m + \frac{4m log m}{log q − 2 log(m − 1)}⌉.

It is slightly better if q is very close to (m − 1)^{2}.

4. Primitive elements and primitive normal elements

An element α ∈ F_{q^{m}} is said to be normal over F_{q} if the set {α, α^{q}, …, α^{q^{m−1}}} forms a basis of F_{q^{m}} over F_{q}. The element α is said to be primitive if α generates the multiplicative group of F_{q^{m}}. The element α is said to be a primitive normal element if it is both primitive and normal. A primitive normal element always exists, see Lenstra and Schoof [LS]. An interesting question is then to construct primitive normal elements. Since the construction of primitive elements is difficult, the construction of primitive normal elements will certainly not be easier. Motivated by Shoup’s work on primitive elements, here we are interested in the following weaker question: Given a normal element α of degree m over F_{q}, we hope to have a polynomial g(T) of small degree such that g(α) is a primitive normal element of F_{q^{m}}. The following result is a more precise version of Theorem 1.4.

Theorem 4.1. Let Ω_{m} be the number of distinct prime factors of T^{m} − 1 over F_{q}. There are absolute positive constants C_{1} and C_{2} such that if

q ≥ C_{1}Ω_{m} log^{2} m

and if α is a normal element of F_{q^{m}} over F_{q}, then there is a primitive normal element of the form g(α), where g(T) is a monic irreducible polynomial over F_{q} of degree at most ⌈6 log_{q} m + C_{2} log_{q} log q⌉.

To prove this theorem, we need the following result of Shoup [Sh] on primitive elements of low degrees.

Lemma 4.2. Let ω_{m} be the number of distinct prime factors of q^{m} − 1. Let α be an element of F_{q^{m}} with degree m over F_{q}. For a positive integer k, let P_{k}(α) be the number of monic irreducible polynomials g(T) over F_{q} of degree k such that g(α) is primitive in F_{q^{m}}^{∗}. There are absolute positive constants C_{1} and C_{2} such that

P_{k}(α) ≥ C_{1} \frac{q^{k}}{(log ω_{m} + 1)^{2}} − C_{2}ω_{m}^{2}mq^{k/2}.  (4.1)

This result was proved by Shoup [Sh] for q = p using Weil’s character sum estimate together with Iwaniec’s shifted sieve. For general q, the proof is the same. Replacing q by q^{u}, Lemma 4.2 gives

Corollary 4.3. Let u be a positive integer. Let α be an element of F_{q^{um}} with degree m over F_{q^{u}}. For a positive integer k, let P_{k,u}(α) be the number of monic irreducible polynomials g(T) over F_{q^{u}} of degree k such that

Norm(g(α)) = g(α)^{(q^{um}−1)/(q^{m}−1)}

is primitive in F_{q^{m}}^{∗}. There are absolute positive constants C_{1} and C_{2} such that

P_{k,u}(α) ≥ C_{1} \frac{q^{uk}}{(log ω_{mu} + 1)^{2}} − C_{2}ω_{mu}^{2}mq^{uk/2}.

In fact, if g(α) is primitive in F_{q^{um}}, then Norm(g(α)) is primitive in F_{q^{m}}. Thus, Corollary 4.3 follows from Corollary 4.2. Taking k = 1, Corollary 4.3 reduces to Shparlinski’s result [Shp]. Taking u = 1, Corollary 4.3 reduces to Lemma 4.2.

Proof of Theorem 4.1. We can assume that m > 1. The idea is to remove those elements g(α) that are not normal and then apply Shoup’s lemma. Let σ be the Frobenius automorphism σ(β) = β^{q}. The additive group F_{q^{m}} is a cyclic F_{q}[T]-module under the action T (β) = σ(β). For an element β ∈ F_{q^{m}}, the order of β in F_{q}[T] is the monic polynomial r(T) of smallest degree such that r(T)β = 0. Such an order is a monic factor of T^{m} −1. An element β is normal if and only if the order of β is T^{m} − 1. Alternatively, an element β is not normal if and only if there is an irreducible factor s(T) of T^{m} − 1 (m > 1) over F_{q} such that (T^{m} − 1)/s(T) annihilates the element β.

Now, for a positive integer k, let M(k) be the set of elements of the form g(α), where g(T) is a monic polynomial in F_{q}[T] of degree k. We claim that M(k) contains at least q^{k} − Ω_{m}q^{k−1} normal elements. In fact, if s(T) is an irreducible factor of T^{m} − 1 and (a_{k−1}, ⋯, a_{2}, a_{0}) is a given (k − 1)-tuple of elements from F_{q}, then (T^{m} − 1)/s(T) annihilates at most one of the elements in the family α^{k} + a_{k−1}α^{k−1} + ⋯ + a_{1}α + a_{0} parametrized by a_{1}, because α is normal. Thus, the polynomial (T^{m} − 1)/s(T) annihilates at most q^{k−1} elements of M(k). Since T^{m} − 1 has Ω_{m} distinct irreducible factors, there are at most Ω_{m}q^{k−1} non-normal elements in M(k) and the claim follows.

Let N_{k}(α) be the number of normal elements in M(k). To prove the theorem, it suffices to prove that N_{k}(α) + P_{k}(α) > q^{k}. By the above claim and Shoup’s lemma, we are led to solve the inequality

(q^{k} − Ω_{m}q^{k−1}) + (C_{1} \frac{q^{k}}{(log ω_{m} + 1)^{2}} − C_{2}ω_{m}^{2}mq^{k/2}) > q^{k}.  (4.2)

Since ω_{m} = O(m log q), it suffices to solve

C′_{1} \frac{q^{k}}{(log m + log log q)^{2}} ≥ C′_{2}m^{3}(log^{2} q)q^{k/2} + Ω_{m}q^{k−1}.  (4.3)

Inequality (4.3) clearly holds if

\frac{1}{2}C′_{1} \frac{q^{k}}{(log m + log log q)^{2}} ≥ Ω_{m}q^{k−1}, \frac{1}{2}C′_{1} \frac{q^{k}}{(log m + log log q)^{2}} ≥ C′_{2}m^{3}(log^{2} q)q^{k/2}.

(4.4)

The first inequality in (4.4) gives q ≥ C′′_{1}Ω_{m} log^{2} m. This together with the second inequality in (4.4) gives k ≥ 6 log_{q} m + C′′_{2} log_{q} log q. Since k is an integer, the theorem is proved.

Corollary 4.4. There are absolute positive constants C_{1} and C_{2} such that if

q ≥ C_{1}m^{6} log^{C_{2}} m

and if α is a normal element of F_{q^{m}} over F_{q}, then there is a primitive normal element of F_{q^{m}} of the form α + a, where a ∈ F_{q}.

5. Distribution of irreducible polynomials

Let m ≥ n ≥ 1 be positive integers and let a be a given element in F_{q}. The Hansen-Mullen conjecture concerns the existence of irreducible polynomials over F_{q} of the form g(T) = T^{m} + a_{m−1}T^{m−1} + ⋯ + a_{1}T + a_{0} with a_{n−1} = a. If n is small compared to m, the conjecture follows immediately from the following well known theorem on primes in an arithmetic progression by taking f(T) = T^{n} and Φ(f) = q^{n−1}(q − 1). For a related result on primes in arithmetic progressions, see Effinger and Hayes [EH].

Theorem 5.1. Let f(T) be a polynomial of degree n in F_{q}[T]. Let m be a positive integer and let h be a polynomial in F_{q}[T] which is relatively prime to f. Let π_{m}(h) be the number of monic irreducible polynomials g in F_{q}[T] of degree m such that g ≡ h(modf). Then,

|π_{m}(h) − \frac{q^{m}}{mΦ(f)}| ≤ \frac{1}{m}(n + 1)q^{m/2},  (5.1)

where Φ(f) is the number of elements in (F_{q}[T]/(f))^{∗} (the Euler function in function fields).

Proof. For a character χ of (F_{q}[T]/(f))^{∗}, let χ̄ be its inverse or conjugate. Then, a standard character sum argument shows that

π_{m}(h) = \frac{1}{Φ(f)} ∑_{deg(g)=m, g monic irred.} ∑_{χ} χ(g)χ̄(h).  (5.2)

Let π_{m} be the number of monic irreducible polynomials over F_{q} of degree m. Separating the trivial character in (5.2) and applying estimate (2.14.1), we deduce

|π_{m}(h) − \frac{1}{Φ(f)}π_{m}| ≤ \frac{Φ(f) − 1}{mΦ(f)}(n + 1)q^{m/2}.

Using (2.15), we obtain

\begin{aligned}|π_{m}(h) − \frac{q^{m}}{mΦ(f)}| & ≤ \frac{1}{mΦ(f)}\{(Φ(f) − 1)(n + 1)q^{m/2} + 2 · q^{m/2}\} \\ & ≤ \frac{1}{m}(n + 1)q^{m/2}. \end{aligned}

The proof is complete.

The above theorem can be applied only when the degree n of f(T) is small. If the degree n is close to m/2, then (5.1) gives no information. For the purpose of Hansen-Mullen conjecture, the desired irreducible polynomial g(T) can be chosen flexibly from many residue classes modulo T^{n}. A suitable large subset of these residue classes can be given a nice structure. An exploitation of structures among these residue classes would then permit us to get useful information for larger n. We now carry out this idea. Recall that a polynomial h(T) over F_{q} is called primary if it is a power of an irreducible polynomial r(T) over F_{q}. The degree of r(T) is denoted by Λ(h), the von Mangoldt function. Working with primary polynomials instead of irreducible polynomials will result in simpler estimates.

We first assume that a ≠ 0.

Let H_{n−1} be the set of all monic primary polynomials over F_{q} of degree n − 1. Define the following weighted sum

w_{a}(m, n) = ∑_{h∈aH_{n−1}} Λ(h) ∑_{g≡h (mod T^{n})} 1,

where g denotes a monic irreducible polynomial over F_{q} of degree m and Λ(h) is defined to be 1 if h is a non-zero constant. For the purpose of the Hansen-Mullen conjecture, we want to have w_{a}(m, n) > 0. We now give an asymptotic formula for w_{a}(m, n). Recall that π_{m} denotes the number of monic irreducible polynomials over F_{q} of degree m.

Theorem 5.2. Let a ≠ 0. (i). If n > 1, then

|w_{a}(m, n) − \frac{π_{m}}{q − 1}| < \frac{1}{m}(n^{2} − 1)q^{(m+n−1)/2}.

(ii). If n = 1, then

|w_{a}(m, 1) − \frac{π_{m}}{q − 1}| ≤ \frac{1}{m}(\frac{q − 2}{q − 1})2q^{m/2}.

Proof. Let χ run over the q^{n−1}(q−1) characters of (F_{q}[T]/(T^{n}))^{∗}. Weil’s estimate (2.6.1) shows that if n > 1 and χ ≠ 1, then

| ∑_{h∈aH_{n−1}} Λ(h)χ(h)| = |χ(a) ∑_{h∈H_{n−1}} Λ(h)χ(h)| ≤ (n − 1)q^{(n−1)/2}.  (5.3)

If χ is trivial, then the above sum is simply q^{n−1} for n ≥ 1. By the definition of w_{a}(m, n) and a standard character sum argument, one deduces

\begin{aligned}w_{a}(m, n) & = ∑_{h∈aH_{n−1}} Λ(h) ∑_{g} \frac{1}{q^{n−1}(q − 1)} ∑_{χ} χ(g)χ̄(h) \\ & = \frac{1}{q^{n−1}(q − 1)} ∑_{χ}(∑_{g} χ(g))( ∑_{h∈aH_{n−1}} Λ(h)χ̄(h)), \end{aligned}  (5.4)

where g runs over all monic irreducible polynomials over F_{q} of degree m. By (2.14.1) and (5.3), we conclude that for n > 1,

\begin{aligned}|w_{a}(m, n) − \frac{π_{m}}{q − 1}| & < \frac{1}{m}(n + 1)q^{m/2}(n − 1)q^{(n−1)/2} \\ & = \frac{1}{m}(n^{2} − 1)q^{(m+n−1)/2}. \end{aligned}

If n = 1, there are (q − 2) non-trivial characters χ in (5.4) and the estimate in (5.3) becomes 1 instead of zero. The rest of the argument is the same. The proof is complete.

Corollary 5.3. Let a ∈ F_{q}^{∗}. Let m ≥ 3 and m ≥ n ≥ 1. If

q^{m−n+1} ≥ (q − 1)^{2}n^{4},

then there is a monic irreducible polynomial g(T) over F_{q} of degree m such that the coefficient of T^{n−1} is a.

Proof. If n = 1, the result is always true by the simple argument of Hansen-Mullen. One can also use the second estimate of Theorem 5.2. We now assume that n > 1. By Theorem 5.2 and (2.15),

|m(q−1)w_{a}(m, n)−q^{m}| < (q−1)(n^{2} −1)q^{(m+n−1)/2} +2q^{m/2} ≤ (q−1)n^{2}q^{(m+n−1)/2},

where the exceptional case n = q = 2 needs a little extra treatment using the middle term of (2.15). The corollary follows.

The above corollary implies that the Hansen-Mullen conjecture is true for a ≠ 0 if 1 ≤ n < m − 1 and q is large compared to m. One can use the above method to derive a similar estimate in the case a = 0. We shall not do so. Instead, we shall derive an estimate which handle the case when m − n is small and by symmetry this also includes the case a = 0. For this purpose, we need to consider irreducible polynomials of degree m whose constant term is always 1, namely, irreducible polynomials of the form 1 + a_{1}T + ⋯ + a_{m}T^{m} with a_{m} ≠ 0.

For n ≥ 2, let G_{n−2} be the set of primary polynomials over F_{q} of degree n − 2 with constant term 1. Thus, we are considering primary polynomials of the form 1+a_{1}T +⋯+a_{n−2}T^{n−2} with a_{n−2} ≠ 0. For simplicity of estimates, we include the constant 1 as a special element of G_{n−2} and define Λ(1) = 1. This special element corresponds to the monic primary polynomial T^{n−2}. For a fixed a ∈ F_{q}, define the following weighted sum

W_{a}(m, n) = ∑_{h∈G_{n−2}} Λ(h) ∑_{g≡h+aT^{n−1} (mod T^{n})} 1,

where g denotes an irreducible polynomial over F_{q} of degree m with constant term 1. In the application to the Hansen-Mullen conjecture, we want to have W_{a}(m, n) > 0. The following is an asymptotic formula for W_{a}(m, n).

Theorem 5.4. Let a ∈ F_{q}. (i). If n > 2, we have

|W_{a}(m, n) − \frac{π_{m}}{q} | < \frac{1}{m}(n − 1)^{2}q^{(m+n−2)/2}.

(ii). If n = 2, we have

|W_{a}(m, 2) − \frac{π_{m}}{q} | < \frac{2}{m}q^{m/2}.

Proof. Let U_{1} be the set of polynomials of the form 1+a_{1}T +⋯+a_{n−1}T^{n−1} over F_{q}. The set U_{1} is an abelian group of order q^{n−1} under multiplication modulo T^{n}. The direct product of U_{1} with F_{q}^{∗} gives the full group (F_{q}[T]/(T^{n}))^{∗}.

Let χ run over the q^{n−1} characters of the subgroup U_{1}, namely, the characters of (F_{q}[T]/(T^{n}))^{∗} which are trivial on F_{q}^{∗}. For h ∈ G_{n−2}, one checks that

h + aT^{n−1} ≡ h(1 + aT^{n−1}) (mod T^{n}).

Weil’s estimate (2.6.2) shows that if χ ≠ 1 and n > 2, then

| ∑_{h∈G_{n−2}} Λ(h)χ(h + aT^{n−1})| = |χ(1 + aT^{n−1}) ∑_{h∈G_{n−2}} Λ(h)χ(h)| ≤ (n − 2)q^{(n−2)/2},

(5.5)

where we used the fact that χ(F_{q}^{∗}) = 1 and our convention about the special element 1 of G_{n−2}. If χ is trivial, then the above sum is simply q^{n−2} for n ≥ 2.

By the definition of W_{a}(m, n) and a standard character sum argument, one deduces

\begin{aligned}W_{a}(m, n) & = ∑_{h∈G_{n−2}} Λ(h) ∑_{g} \frac{1}{q^{n−1}} ∑_{χ} χ(g)χ̄(h + aT^{n−1}) \\ & = \frac{1}{q^{n−1}} ∑_{χ}(∑_{g} χ(g))( ∑_{h∈G_{n−2}} Λ(h)χ̄(h + aT^{n−1})), \end{aligned}  (5.6)

where g runs over all irreducible polynomials over F_{q} of degree m with constant term 1. By (2.17) and (5.5), we conclude that if n > 2, then

\begin{aligned}|W_{a}(m, n) − \frac{π_{m}}{q} | & < \frac{1}{m}(nq^{m/2} + 1)(n − 2)q^{(n−2)/2} \\ & ≤ \frac{1}{m}(n − 1)^{2}q^{(m+n−2)/2}. \end{aligned}

If n = 2, then (2.17) and (5.6) show that

|W_{a}(m, 2) − \frac{π_{m}}{q} | < \frac{q − 1}{q} \frac{1}{m}(2q^{m/2} + 1) < \frac{2}{m}q^{m/2}.

The proof is complete.

Corollary 5.5. Let a ∈ F_{q}. Let m ≥ n ≥ 2 be positive integers. If

q^{m−n} ≥ n^{4},

then there is an irreducible polynomial g(T) over F_{q} of degree m with constant term 1 such that the coefficient of T^{n−1} is a.

Proof. By Theorem 5.4, one obtains that for n > 2,

|mqW_{a}(m, n)−q^{m}| < q(n−1)^{2}q^{(m+n−2)/2} +2q^{m/2} ≤ qn^{2}q^{(m+n−2)/2} = n^{2}q^{(m+n)/2}.

This proves that W_{a}(m, n) > 0 if q^{m−n} ≥ n^{4}. If n = 2, Theorem 5.4 gives

|mqW_{a}(m, 2) − q^{m}| < (2q + 2)q^{m/2} < q2^{2}q^{m/2}.

This inequality shows that W_{a}(m, 2) > 0 if q^{m−2} ≥ 2^{4}. The corollary is proved. Putting the above two corollaries together, we have

Corollary 5.6. Let m ≥ n ≥ 1 be positive integers with m ≥ 3. Let a be a given element in F_{q}. (i). Assume a ≠ 0. Then there exists a monic irreducible polynomial g(T) over F_{q} of degree m such that the coefficent of T^{n−1} in g(T) is equal to a if

either q^{m−n−1} ≥ n^{4} or q^{n−2} ≥ (m − n + 2)^{4}.  (5.7)

(ii). Assume a = 0 and n > 1. Then there exists a monic irreducible polynomial g(T) over F_{q} of degree m such that the coefficent of T^{n−1} in g(T) is equal to a if

either q^{m−n} ≥ n^{4} or q^{n−2} ≥ (m − n + 2)^{4}.  (5.8)

Proof. A monic polynomial of the form g(T) = T^{m} + a_{m−1}T^{m−1} + ⋯ + a_{n}T^{n} + ⋯ + a_{0} is irreducible of degree m (> 1) if and only if the reciprocal polynomial g^{∗}(T) = 1 + a_{m−1}T + ⋯ + a_{0}T^{m} is irreducible of degree m. The coefficient of T^{n−1} in g(T) corresponds to the coefficient of T^{m−n+1} in g^{∗}(T). Corollaries 3.3 and 3.5 imply the result for the case a ≠ 0. If a = 0, the transformation g(T) ⟶ g^{∗}(T)/g(0) shows that there is a monic irreducible polynomial of degree m with a_{n−1} = 0 if and only if there is a monic irreducible polynomial of degree m with a_{m−n+1} = 0. Corollary 3.5 then gives the result for the case a = 0. The proof is complete.

Corollary 5.7. Let m ≥ n ≥ 1 be positive integers with m ≥ 3. Let a be a given element in F_{q} with a ≠ 0 if n = 1. Then, there exists a monic irreducible polynomial g(T) over F_{q} of degree m such that the coefficent of T^{n−1} in f(T) is equal to a if

q^{m−3} ≥ (\frac{m + 2}{2})^{8}.  (5.9)

Proof. Multiplying the two inequalities in (5.7) and (5.8), one sees that it suffices to have

q^{m−3} ≥ n^{4}(m − n + 2)^{4}.

The worst case occurs when n = m − n + 2 = (m + 2)/2. The proof is complete.

Inequality (5.9) is satisfied for all prime powers q if m is large. It is also satisfied for all m > 3 if q is large. To prove that there are only finitely many cases left, there remains the case m = 3 and n > 1. This case can be easily excluded by a simple argument as follows. Let f(T) be a cubic monic polynomial over F_{q}. It is easy to see that there is a monic irreducible cubic polynomial over F_{q} in the family f(T) + t parametrized by t, if and only if f(T) is not a permutation polynomial over F_{q}. Actually, there are at least (q − 1)/3 irreducible cubic polynomials in the family f(T) + t if f(T) is not a permutation polynomial over F_{q}, see [Wa]. Thus, to have an irreducible polynomial of the form T^{3} + aT^{2} + bT + c with given a, we can just choose b ∈ F_{q} such that T^{2} + aT + b has a non-zero root. This can clearly be done. Similarly, to have an irreducible polynomial of the form T^{3} + bT^{2} + aT + c with given a, it suffices to choose b ∈ F_{q} such that T^{2} + bT + a has a non-zero root. Again, this can clearly be done.

Corollary 5.8. If either q > 19 or m ≥ 36, then the Hansen-Mullen conjecture is true.

Proof. If q = 2, Corollary 5.3 shows that the first inequality in (5.7) can be improved. The worse case occurs in (5.8). Thus, it suffices to have

2^{m−2} ≥ (\frac{m + 2}{2})^{8}.

This inequality is satisfied if m ≥ 36. If q ≥ 3, inequality (5.9) is satisfied for m ≥ 22.

Next we turn to proving the result for q > 19. We may assume that m ≥ 4. If m ≥ 7, inequality (5.9) is satisfied if q ≥ 21 and hence if q > 19 since q is a prime power. There remain the three cases 4 ≤ m ≤ 6. We will be implicitly using the transformations occuring in the proof of Corollary 5.6. Part (ii) of Theorem 5.2 and part (ii) of Theorem 5.4 show that the conjecture is true for all m ≥ 4 if n = 1 or if n = m. Corollary 5.6 covers the case n = 2 if q ≥ 16. The first estimate of Theorem 5.4 covers the case n = m − 1 if q ≥ 17. This takes care of all possibilities if m = 4 and q > 19. For m = 5, there remains the possibility that n = 3 and a ≠ 0. In this case, a direct estimate of (5.4) using the fact that there are (q^{5} −q)/5 monic irreducible polynomials of degree 5 gives the following better bound:

|w_{a}(5, 3) − \frac{q^{5} − q}{5(q − 1)}| ≤ \frac{1}{5}(2q^{5/2} + q)2q.

We need to have

q^{5} − q > (2q^{5/2} + q)2q(q − 1).

The last inequality is satisfied if q ≥ 18. For m = 6, there remain the two possibilities that n = 3 (a ≠ 0) and n = 4. For m = 6 and n = 3, Corollary 5.6 shows that the conjecture is true if q ≥ 9. For m = 6 and n = 4, Corollary 5.6 shows that the conjecture is true if q ≥ 16. The proof is complete.

References

[BDS] E. Bach, J. Driscoll and J. Shallit, Factor refinement, J. Algorithm, 15(1993), 199-222.

[Ch] F.R. Chung, Diameters and eigenvalues, J. Amer. Math. Soc., 2(1989), 187-196.

[Co] S.D. Cohen, Primitive elements and polynomials with arbitrary trace, Discr. Math.,

83(1990), 1-7.

[EH] G.W. Effinger and D.R. Hayes, Additive Number Theory of Polynomials over a Finite

Field, Oxford Science Publications, 1991.

[Ha1] W.B. Han, Some Applications of Character Sums in Finite Fields and Coding

Theory, Ph.D. Dissertation, Sichuan University, 1994.

[Ha2] W.B. Han, The coefficients of primitive polynomials over finite fields, Math. Comp.,

65(1996), no. 213, 331-340.

[HM] T. Hansen and G.L. Mullen, Primitive polynomials over finite fields, Math. Comp.,

59(1992), 639-643.

[Ka] N. M. Katz, An estimate for character sums, J. Amer. Math. Soc., 2(1989), 197-200.

[Le1] H.W. Lenstra Jr., Finding isomorphisms between finite fields, Math. Comp., 56(1991),

329-347.

[Le2] H.W. Lenstra Jr., Multiplicative groups generated by linear expressions, unpublished

notes.

[LS] H.W. Lenstra Jr. and R. Schoof, Primitive normal bases for finite fields, Math. Comp., 48(1987), 217-231.

[Li] W.C. Li, Character sums and abelian Ramanujan graphs, J. Number Theory, 41(1992),

199-217.

[Sh] V. Shoup, Searching for primitive roots in finite fields, Math. Comp., 58(1992), 369-380.

[Shp] I.E. Shparlinski, Computational and Algorithmic Problems in Finite Fields, Kluwer

Academic Publishers, 1992.

[Wa] D. Wan, A p-adic lifting lemma and its application to permutation polynomials,

in Finite Fields, Coding Theory and Advances in Communications and Computing, eds: G.L. Mullen and P.J.S. Shiue, Marcel Dekker, 1992, 209-216.

[We] A. Weil, Basic Number Theory, third edition, Springer-Verlag, 1974.