ARTIN’S CONJECTURE FOR POLYNOMIALS OVER FINITE FIELDS Erik Jensen and M. Ram Murty^{∗}

1. Introduction

A classical conjecture of E. Artin[Ar] predicts that any integer a ≠ ±1 or a perfect square is a primitive root (mod p) for infinitely many primes p. This conjecture is still open. In 1967, Hooley[H] proved the conjecture assuming the (as yet) unresolved generalized Riemann hypothesis for Dedekind zeta functions of certain number fields.

In 1983, R. Gupta and M. R. Murty[GM] made the first breakthrough by showing the following: given three prime numbers a, b, c, then at least one of the thirteen numbers

{ac^{2}, a^{3}b^{2}, a^{2}b, b^{3}c, b^{2}c, a^{2}c^{3}, ab^{3}, a^{3}bc^{c}, bc^{3}, a^{2}b^{3}c, a^{3}c, ab^{2}c^{3}, abc}

is a primitive root (mod p) for infinitely many primes p. This result has been further refined by R. Gupta, M. R. Murty, and V. K. Murty[GMM] to establish that at least one of the seven numbers

{a, b, c, a^{2}b, ab^{2}, a^{2}c, ac^{2}}

is a primitive root (mod p) for infinitely many primes p. Finally, Heath–Brown[HB] used the Chen–Iwaniec switching and a celebrated 1986 theorem of Bombieri, Friedlander, and Iwaniec[BFI] to derive the further refinement that at least one of {a, b, c} is a primitive root for infinitely many primes p. The paper by Murty[M1] contains an overview of Artin’s conjecture and its analogues for elliptic curves. (See also [M2]).

Although any undergraduate student can easily understand Artin’s conjecture, to understand Hooley’s results requires a strong background in both analytic and algebraic number theory, and thus is only possible at the senior or graduate level. The results of Gupta, M. R. Murty, V. K. Murty, and Heath–Brown require an even more formidable background in advanced sieve theory that is available only to the doctoral student or to the expert working in the field.

The purpose of this paper is twofold. Our first goal is to show that the sieve approach can be understood, at least conceptually, by the undergraduate student. Indeed, it was this kind of conceptual reasoning that led to the original breakthrough. Once our reasoning is in place, it is then just a matter of technical expertise to fine tune the argument to get a refined result.

Our second goal is to study the analogue of Artin’s conjecture for polynomials mod p. More precisely, fix a prime p and let a(x) be a non–constant polynomial which is not equal to the square of a polynomial mod p. Are there infinitely many irreducible polynomials p(x) such that a(x) generates the residue classes of (F_{p}[x]/(p(x)))^{∗}?

In 1937, Bilharz[B], a student of E. Artin, answered this in the affirmative, by assuming the truth of the so–called Riemann hypothesis for curves. Then, in 1948, A. Weil proved the Riemann hypothesis for curves as a consequence of his rigorous treatment of algebraic

∗ The first author, an undergraduate, would like to thank the second author for giving him the opportunity of being a part of this research project. Research of the second author was partially supported by NSERC. geometry(see [L] for a proof). Thus, as it stands, even this “function field analogue” is not accessible to the undergraduate student.

In this paper, we will show that for a(x) = x^{m} + c, Artin’s conjecture for F_{p}[x] can be established very easily and almost from first principles. The fact that the junior author co–authored this paper is proof enough that it is accessible to the undergraduate.

2. Sieve Theory and Artin’s Conjecture

Understanding this section requires a familiarity with quadratic residues. We direct the reader to chapter 5, section 1 of Ireland and Rosen[IR].

Suppose that we want to prove that 2 is a primitive root (mod p) for infinitely many primes p. First, observe that if (p−1) = 4q, with q an odd prime, then 2 is a primitive root (mod p). To see this, suppose that 2 has order r. Then r|(p − 1). Hence, r|4q. Therefore, r ∈ {1, 2, 4, q, 2q, 4q}. Let’s examine the separate cases. Clearly the case r = 1 is not possible. If r = 2, we have that p|(2^{2} − 1), which implies that p = 3. However, p = 4q + 1, which is clearly ≥ 13. So, we see that r ≠ 2. Similarly, if r = 4 we have that p|(2^{4} − 1), which implies that p = 3 or p = 5. However, we have seen that p ≥ 13, so it is clear that r ≠ 4. If r = q or r = 2q, then

2^{\frac{p−1}{2}} ≡ 1 (mod p).

Hence, 2 is a quadratic residue (mod p). Therefore,

p ≡ ±1 (mod 8).

However, it is easily seen that

p = 4q + 1 = 4(2k + 1) + 1 = 8k + 5 ≡ 5 (mod 8).

Hence, r = 4q = (p−1). It is at present unknown whether there are infinitely many primes p such that (p − 1) = 4q, with q prime. Heuristic reasoning[IR, ch. 2, §4] suggests that the number of such primes p ≤ x is asymptotic to \frac{cx}{log^{2} x} as x → ∞, for some constant c > 0. So, our attempt at a proof stalls here. However, if we continue along this line of thought, and use the ideas of sieve theory, we can prove that one of 2, 3, 5 is a primitive root for infinitely many primes p. First, though, we will pause to prove a lemma which will be useful later on. Lemma. A natural number n cannot have more than \frac{log n}{log 2} prime factors. Proof. Let n = p_{1}^{α_{1}}p_{2}^{α_{2}} ⋯ p_{l}^{α_{l}}, with p_{1}, …, p_{l} distinct primes. Then we see that

log n = ∑_{i=1}^{l} α_{i} log p_{i} ≥ l log 2

and so clearly we have that

l ≤ \frac{log n}{log 2}

and the lemma is proved.

Ramanujan[R] observed that this estimate can be refined to

l = O (\frac{log n}{log log n})

in the following way: first, note that

log n ≥ ∑_{i=1}^{l} log p_{i} ≥ ∑_{i=1}^{l} log q_{i}

where 2 = q_{1} < q_{2} < ⋯ is the sequence of primes. Then, by the elementary Tchebychef theorem(see [IR, p. 25]), we obtain

log n ≥ cl log l

for some constant c > 0. If l ≤ \frac{log n}{log log n}, then we are done, so assume that l > \frac{log n}{log log n}. Then,

log l > log log n − log log log n

which gives log n ≫ l log log n

as desired.

The seminal idea of Gupta and Murty was to use sieve theory to produce primes p such that (p − 1) has very few prime factors, thereby restricting the possibility for 2 to have order < (p − 1) mod p. Indeed, sieve theory provides at least

\frac{cx}{log^{2} x}, c > 0

primes p ≤ x such that (p − 1) = 2q or (p − 1) = 2q_{1}q_{2}, with q, q_{1}, q_{2} prime and (2/p) = (3/p) = (5/p) = −1. Moreover, one can arrange

q_{2} > x^{\frac{1}{2} −δ} > q_{1} > x^{0.26} for some δ > 0.

If (p − 1) = 2q, then as (2/p) = −1, we use the same reasoning as before and easily see that 2 has order (p − 1) mod p in this case. If (p − 1) = 2q_{1}q_{2}, then the order of 2 (mod p) is either 2q_{1}, 2q_{2}, or 2q_{1}q_{2}. If the order of 2 (mod p) is 2q_{1}, then p|(2^{2q_{1}} − 1) and hence

(1)  p | ∏_{a<2x^{\frac{1}{2} −δ}}(2^{a} − 1).

Using Lemma 1, we see that the number of primes p ≤ x satisfying (1) cannot exceed

∑_{a<2x^{\frac{1}{2} −δ}} a ≤ 4x^{1−2δ}.

Therefore, we have at least

\frac{cx}{log^{2} x} − 4x^{1−2δ}

primes p ≤ x such that (p − 1) = 2q or (p − 1) = 2q_{1}q_{2} where the order of 2 (mod p) is either 2q_{2} or (p − 1).

Among these primes, let us consider the order of 3 (mod p). If the order is 2q_{1}, then, as above, we have that

p | ∏_{a<2x^{\frac{1}{2} −δ}}(3^{a} − 1).

and the number of such primes cannot exceed

∑_{a<2x^{\frac{1}{2} −δ}} (\frac{log 3}{log 2}) a ≤ (\frac{log 3}{log 2}) 4x^{1−2δ}.

Similarly, the number of primes p for which the order of 5 (mod p) is 2q_{1} cannot exceed

∑_{a<2x^{\frac{1}{2} −δ}} (\frac{log 5}{log 2}) a ≤ (\frac{log 5}{log 2}) 4x^{1−2δ}.

Therefore, we have at least

\frac{cx}{log^{2} x} − O(x^{1−2δ})

primes p ≤ x such that the order of 2, 3, and 5 (mod p) is one of 2q_{2} or (p − 1).

We now show that there are infinitely many primes p such that one of 2, 3, 5 is a primitive root mod p. If not, then 2, 3, and 5 generate a subgroup of order 2q_{2} (mod p). Observe that

2q_{2} = \frac{p − 1}{q_{1}} < \frac{x}{x^{0.26}} = x^{0.74} = z.

Notice that if the numbers in the set

{2^{a}3^{b}5^{c}, 0 ≤ a, b, c ≤ x^{α}}, α = 0.247

are all distinct, they generate a subgroup of size x^{3α}. This is clearly a contradiction, since 3α = 0.741 ⇒ x^{3α} > z. Hence, for some a, b, c and a′, b′, c′, we have that

2^{a}3^{b}5^{c} ≡ 2^{a′}3^{b′}5^{c′} (mod p)

which implies that

2^{a−a′}3^{b−b′}5^{c−c′} ≡ 1 (mod p).

Thus, p divides the numerator of

(2)  ∏_{0≤|a|,|b|,|c|≤2x^{α}}(2^{a}3^{b}5^{c} − 1).

Observe that if e_{i}, 1 ≤ i ≤ r are integers then the numerator of

∏_{i=1}^{r} p_{i}^{e_{i}} − 1

is

∏_{e_{i}>0} p_{i}^{e_{i}} − ∏_{e_{i}<0} p_{i}^{−e_{i}}.

Thus, for a given triple a, b, c in the product from (2), the numerator can have at most O(x^{α}) prime factors.

The number of such primes is O(x^{4α}), which is o(\frac{x}{log^{2} x}), since 4α < 1. Hence, one of 2, 3, or 5 is a primitive root (mod p) for these primes.

3. Sifting Function for Primitive Roots

In this section, we will use the Ramanujan sum and Theorem 272 from Hardy and Wright[HW, p. 238]. The Ramanujan sum is defined as:

c_{d}(j) = ∑_{{1≤k≤d \atop (k,d)=1}} e^{\frac{2πikj}{d}} .

Theorem 272 states that

c_{d}(j) = \frac{μ(\frac{d}{a})ϕ(d)}{ϕ(\frac{d}{a})}, where a = (d, j).

With these tools at our disposal, we will prove the following lemma: Lemma. Let G be a cyclic group of order n. Let

f(g) = \frac{ϕ(n)}{n} \{1 + ∑_{{d|n \atop d>1}} \frac{μ(d)}{ϕ(d)} ∑_{ord χ=d} χ(g)\}

where the inner sum runs over characters χ of G which are of order d. Then

f(g) = \{ \begin{matrix}1, & if g generates G \\ 0, & otherwise. \end{matrix}

Proof. Let ε be a generator of G. Let g = ε^{j}. Then g generates G if and only if (j, n) = 1. Notice that if Ψ(ε) = e^{\frac{2πi}{n}}, then Ψ^{\frac{n}{d}} is a character of order d. In fact, all of the characters of order d are given by Ψ^{\frac{n}{d} k}, where (k, d) = 1 and 1 ≤ k ≤ d. Then

f(g) = \frac{ϕ(n)}{n} \{1 + ∑_{{d|n \atop d>1}} \frac{μ(d)}{ϕ(d)} ∑_{ord χ=d} χ(g)\}

= \frac{ϕ(n)}{n} \{1 + ∑_{{d|n \atop d>1}} \frac{μ(d)}{ϕ(d)} ∑_{{1≤k≤d \atop (k,d)=1}} Ψ^{\frac{n}{d} k}(ε^{j})\}

= \frac{ϕ(n)}{n} \{1 + ∑_{{d|n \atop d>1}} \frac{μ(d)}{ϕ(d)} ∑_{{1≤k≤d \atop (k,d)=1}} Ψ(ε)^{\frac{nkj}{d}} \}

= \frac{ϕ(n)}{n} \{1 + ∑_{{d|n \atop d>1}} \frac{μ(d)}{ϕ(d)} ∑_{{1≤k≤d \atop (k,d)=1}} e^{\frac{2πikj}{d}} \}

= \frac{ϕ(n)}{n} \{1 + ∑_{{d|n \atop d>1}} \frac{μ(d)}{ϕ(d)}c_{d}(j)\}

Notice that

\frac{μ(1)}{ϕ(1)}c_{1}(j) = 1.

We can use this fact to rewrite f(g) more elegantly as

\frac{ϕ(n)}{n} \{∑_{d|n} \frac{μ(d)}{ϕ(d)}c_{d}(j)\} .

Now, we apply Theorem 272 to see that

\begin{aligned}f(g) & = \frac{ϕ(n)}{n} \{∑_{d|n} \frac{μ(d)}{ϕ(d)} \frac{μ(\frac{d}{(d,j)})ϕ(d)}{ϕ(\frac{d}{(d,j)})}\} \\ & = \frac{ϕ(n)}{n} \{∑_{d|n} \frac{μ(d)μ(\frac{d}{(d,j)})}{ϕ(\frac{d}{(d,j)})}\} \end{aligned}

Notice that

g = ε^{j} generates G ⟹ (j, n) = 1 ⟹ (j, d) = 1 ∀ d|n.

So, let g generate G. We now have that

f(g) = \frac{ϕ(n)}{n} ∑_{d|n} \frac{μ^{2}(d)}{ϕ(d)}.

Since both μ and ϕ are multiplicative functions, then \frac{μ^{2}}{ϕ} is also a multiplicative function. So, when g generates G, we have

f(g) = \frac{ϕ(n)}{n} (∏_{p|n}(1 + \frac{1}{p − 1}))

= \frac{ϕ(n)}{n} (∏_{p|n} \frac{p}{p − 1})

= (∏_{p|n} (1 − \frac{1}{p})) (∏_{p|n} \frac{p}{p − 1})

= (∏_{p|n} \frac{p − 1}{p}) (∏_{p|n} \frac{p}{p − 1})

= 1

So, when g generates G, f(g) = 1.

Now, let’s consider the case when g does not generate G. So, let (j, n) = δ, δ > 1. Then n = δt. Observe also that (j, t) = 1 and (δ, t) = 1, since δ|j. We look at

\frac{ϕ(n)}{n} \{∑_{d|n} \frac{μ(d)μ(\frac{d}{(d,j)})}{ϕ(\frac{d}{(d,j)})}\}

Since (δ, t) = 1 and d|n, we have that d = (d, δ)(d, t). Let (d, δ) = d_{1} and (d, t) = d_{2} so that d = d_{1}d_{2}. Now, we can rewrite the above expression as

\frac{ϕ(n)}{n} \{∑_{{d_{1}|δ \atop d_{2}|t}} \frac{μ(d_{1}d_{2})μ(\frac{d_{1}d_{2}}{(d_{1}d_{2},j)})}{ϕ(\frac{d_{1}d_{2}}{(d_{1}d_{2},j)})}\}

Observe that since (j, t) = 1 and (d, t) = d_{2}, then (d_{2}, j) = 1, which implies that (d_{1}d_{2}, j) = (d_{1}, j). So, we can again rewrite the expression for f(g) as

\frac{ϕ(n)}{n} \{∑_{{d_{1}|δ \atop d_{2}|t}} \frac{μ(d_{1}d_{2})μ(\frac{d_{1}d_{2}}{(d_{1},j)})}{ϕ(\frac{d_{1}d_{2}}{(d_{1},j)})}\}

Using the facts that μ and ϕ are multiplicative, and that (d_{1}, d_{2}) = 1, we obtain

f(g) = \frac{ϕ(n)}{n} \{∑_{{d_{1}|δ \atop d_{2}|t}} \frac{μ(d_{1})μ(d_{2})μ(\frac{d_{1}}{(d_{1},j)})μ(d_{2})}{ϕ(\frac{d_{1}}{(d_{1},j)})ϕ(d_{2})}\}

= \frac{ϕ(n)}{n} (∑_{d_{1}|δ} \frac{μ(d_{1})μ(\frac{d_{1}}{(d_{1},j)})}{ϕ(\frac{d_{1}}{(d_{1},j)})}) (∑_{d_{2}|t} \frac{μ^{2}(d_{2})}{ϕ(d_{2})})

= \frac{ϕ(n)}{n} (∑_{d_{1}|δ} \frac{μ(d_{1})μ(\frac{d_{1}}{(d_{1},j)})}{ϕ(\frac{d_{1}}{(d_{1},j)})}) (\frac{t}{ϕ(t)})

But since (j, n) = δ, and (d, δ) = d_{1}, then (d_{1}, j) = d_{1}. So we have

f(g) = \frac{ϕ(n)}{n} (∑_{d_{1}|δ} μ(d_{1})) \frac{t}{ϕ(t)}

= 0, since δ > 1. (See [IR, p. 19])

So, we have shown that

f(g) = \{ \begin{matrix}1, & if g generates G \\ 0, & otherwise. \end{matrix}

4. Reformulation and Solution of the Problem

Let F_{q} be a finite field with q = p^{n} elements. Consider the polynomial ring F_{p}[x]. Let a(x) be a polynomial in F_{p}[x]. We would like to know the number of irreducible polynomials p(x) ∈ F_{p}[x] such that a(x) generates (F_{p}[x]/(p(x)))^{∗}. Recall that if deg p(x) = n then

F_{p}[x]/(p(x)) ≃ F_{p^{n}}

Moreover, F_{p^{n}}^{∗} is cyclic of order p^{n}−1. Also recall that the isomorphism F_{p}[x]/(p(x)) ≃ F_{p^{n}} is given explicitly as follows: for g(x) ∈ F_{p}[x], we write

g(x) = p(x)q(x) + r(x), with r(x) = 0 or 0 ≤ deg r < deg p = n.

Let θ ∈ F_{p^{n}} be a root of p(x). Then

g(θ) = r(θ) = a_{0} + a_{1}θ + ⋯ + a_{n−1}θ^{n−1}, a_{i} ∈ F_{p}

describes all the elements of F_{p^{n}}. Thus, a(x) generating (F_{p}[x]/(p(x)))^{∗} is equivalent to a(θ) generating F_{p^{n}}^{∗}.

Hence, to count the number of irreducible p(x) of degree n for which a(x) is a generator is tantamount to counting the number of θ of degree n for which a(θ) generates F_{p^{n}}^{∗}. Indeed, since each p(x) has n roots, we find

#{p(x) ∈ F_{p}[x] : p(x) irreducible, deg p = n, a(x) generates (F_{p}[x]/(p(x)))^{∗}}
= \frac{1}{n}#\{θ ∈ F_{p^{n}} : deg θ = n, a(θ) generates F_{p^{n}}^{∗}\}

We now apply the lemma of section 3 to see that the number in question is:

\frac{1}{n} ∑_{{θ∈F_{p^{n}} \atop deg θ=n}} f(a(θ)) = \frac{1}{n} ∑_{{θ∈F_{p^{n}} \atop deg θ=n}} (\frac{ϕ(p^{n} − 1)}{p^{n} − 1} (1 + ∑_{{d|p^{n}−1 \atop d>1}} \frac{μ(d)}{ϕ(d)} ∑_{ord χ=d} χ(a(θ))))

= \frac{1}{n} ∑_{{θ∈F_{p^{n}} \atop deg θ=n}} (\frac{ϕ(p^{n} − 1)}{p^{n} − 1} + \frac{ϕ(p^{n} − 1)}{p^{n} − 1} ∑_{{d|p^{n}−1 \atop d>1}} \frac{μ(d)}{ϕ(d)} ∑_{ord χ=d} χ(a(θ)))

= \frac{1}{n} ∑_{{θ∈F_{p^{n}} \atop deg θ=n}} \frac{ϕ(p^{n} − 1)}{p^{n} − 1} + \frac{1}{n} ∑_{{θ∈F_{p^{n}} \atop deg θ=n}} \frac{ϕ(p^{n} − 1)}{p^{n} − 1} ∑_{{d|p^{n}−1 \atop d>1}} \frac{μ(d)}{ϕ(d)} ∑_{ord χ=d} χ(a(θ))

So, the contribution from the main term (the first term in the expression above) is

\frac{p^{n} − p^{n−1}}{n} · \frac{ϕ(p^{n} − 1)}{p^{n} − 1}.

and the error term is

\frac{ϕ(p^{n} − 1)}{n(p^{n} − 1)} ∑_{{d|p^{n}−1 \atop d>1}} \frac{μ(d)}{ϕ(d)} ∑_{ord χ=d} ∑_{{θ∈F_{p^{n}} \atop deg θ=n}} χ(a(θ)).

We will show in the following sections that when d > 1, and a(x) is of the form x^{m} + c, the sum

(3)  | ∑_{{θ∈F_{p^{n}} \atop deg θ=n}} χ(a(θ))| ≤ mp^{\frac{n}{2}}

Hence, the contribution from the error term is O(p^{\frac{n}{2}} δ(p^{n} − 1)), where δ(u) is the number of divisors of u.

The estimate in (3) is a consequence of A. Weil’s celebrated work proving the analogue of the Riemann hypothesis for zeta functions over finite fields. However, one can also obtain this estimate in a more elementary manner using Gauss sums. In section 5, we recount some of the theory of Gauss sums over finite fields. Then, in section 6, we use that theory to obtain the estimate in (3).

Once we justify this estimate, it is clear that we have proven the function field analogue of Artin’s conjecture in the special case where a(x) = x^{m} + c. To see this, notice that in our expression for the number of irreducible p(x) of degree n such that a(x) generates (F_{p}[x]/(p(x)))^{∗}, the contribution from the main term far outweighs the contribution from the error term.

5. Gauss Sums over Finite Fields

In this section, we review some basic properties of Gauss sums over finite fields. All of this can be found in Davenport[D].

Let p be prime and consider the finite field F_{p^{n}}. Let

e(α) = exp (\frac{2πi}{p}Tr_{F_{p^{n}} /F_{p}}(α)) , for α ∈ F_{p^{n}}.

Let χ be a character of F_{p^{n}}^{∗}. The Gauss sum is defined as

τ(χ) = ∑_{α∈F_{p^{n}}^{∗}} χ(α)e(α)

Observe that for any η ≠ 0,

χ(η)τ(\overline{χ}) = ∑_{α∈F_{p^{n}}^{∗}} \overline{χ}(α)χ(η)e(α)

If we make the change of variables α = ηβ, we have that

χ(η)τ(\overline{χ}) = ∑_{β∈F_{p^{n}}^{∗}} χ(β)e(ηβ)

since \overline{χ}(η)χ(η) = |χ(η)|^{2} = 1 and as β ranges over elements of F_{p^{n}}^{∗}, so does ηβ. Theorem. |τ(χ)| = p^{n/2}, for all non–trivial characters χ. Proof. If χ ≠ χ_{0} (the principal character), then

|τ(χ)|^{2} = ∑_{α,β∈F_{p^{n}}^{∗}} χ(α)\overline{χ}(β)e(α − β)

We set α = βγ. Then we have that

|τ(χ)|^{2} = ∑_{γ,β∈F_{p^{n}}^{∗}} χ(γ)e(β(γ − 1)).

Notice that if w_{1}, …, w_{n} is an F_{p}–basis of F_{p^{n}}, then

\begin{aligned}∑_{β∈F_{p^{n}}} e(β) & = ∑_{a_{1},...,a_{n}∈F_{p}} e(a_{1}w_{1} + ⋯ + a_{n}w_{n}) \\ & = ∏_{j=1}^{n} ( ∑_{a_{j}∈F_{p}} e(a_{j}w_{j})) . \end{aligned}

Since

∑_{a_{j}∈F_{p}} e(a_{j}w_{j}) = ∑_{a_{j}=0}^{p−1} exp (\frac{2πia_{j}Tr_{F_{p^{n}} /F_{p}}(w_{j})}{p})

= \{ \begin{matrix}p, & if Tr_{F_{p^{n}} /F_{p}}(w_{j}) = 0 \\ 0, & otherwise. \end{matrix}

we have that

∑_{β∈F_{p^{n}}} e(β) = \{ \begin{matrix}p^{n}, & if Tr_{F_{p^{n}} /F_{p}}(w_{1}) = ⋯ = Tr_{F_{p^{n}} /F_{p}}(w_{n}) = 0 \\ 0, & otherwise. \end{matrix}

In the first case, we deduce that

Tr_{F_{p^{n}} /F_{p}}(η) = 0 ∀η ∈ F_{p^{n}}.

In particular, if 1, θ, θ^{2}, …, θ^{n−1} is a basis, we find that

\begin{aligned}0 = a_{ij} & = Tr_{F_{p^{n}} /F_{p}}(θ^{i+j}) \\ & = ∑_{k=1}^{n} θ^{(k)i}θ^{(k)j} \end{aligned}

and θ^{(1)}, …, θ^{(n)} are the conjugates of θ. The above equation can be rewritten as ΩΩ^{T} = 0, where Ω = (θ^{(j)i}) is a Vandermonde matrix. However, this is a contradiction since θ^{(1)}, …, θ^{(n)} are all distinct, which implies that det Ω ≠ 0.

So, we have that

∑_{β∈F_{p^{n}}} e(β) = 0.

Now, if γ ≠ 1, then

∑_{β∈F_{p^{n}}^{∗}} e(β(γ − 1)) = −1.

If γ = 1, then

∑_{β∈F_{p^{n}}^{∗}} e(β(γ − 1)) = p^{n} − 1.

Thus we have that

|τ(χ)|^{2} = p^{n} − 1 + (−1) ∑_{{γ≠1 \atop γ∈F{∗ \atop p^{n}}}} χ(γ)
= (p^{n} − 1) + (−1)(−1), since χ is non–trivial
= p^{n}

So we have shown that |τ(χ)| = p^{\frac{n}{2}} , for all non–trivial characters χ.

6. Estimation

We will estimate

∑_{θ∈F_{p^{n}}} χ(a(θ))

when a(x) = x^{m} + c. For this purpose, we can rewrite the above as

∑_{θ∈F_{p^{n}}} χ(θ^{m} + c).

If (m, p^{n} − 1) = 1, then θ ↦ θ^{m} is an isomorphism, and the sum becomes

∑_{θ∈F_{p^{n}}} χ(θ + c) = 0.

If (m, p^{n} −1) = t > 1, then write m = ts. Then, (s, p^{n} −1) = 1, and by the same reasoning,

(4)  ∑_{θ∈F_{p^{n}}} χ(θ^{m} + c) = ∑_{θ∈F_{p^{n}}} χ(θ^{t} + c).

Since t|(p^{n} − 1), let Ψ be a character of F_{p^{n}}^{∗} of order t. Then

\frac{1}{t} ∑_{i=0}^{t−1} Ψ^{i}(α) = \{ \begin{matrix}1, & if α = θ^{t} for some θ \\ 0, & otherwise. \end{matrix}

Putting this in expression (4) gives

\begin{aligned}∑_{θ∈F_{p^{n}}} χ(θ^{t} + c) & = t ∑_{α∈F_{p^{n}}} χ(α + c) \frac{1}{t} ∑_{i=0}^{t−1} Ψ^{i}(α) \\ & = ∑_{i=0}^{t−1} ∑_{α∈F_{p^{n}}} χ(α + c)Ψ^{i}(α) \end{aligned}

Now, we use Gauss sums to replace χ(α + c) as follows:

χ(α + c) = \frac{1}{τ(\overline{χ})} ∑_{β∈F_{p^{n}}^{∗}} \overline{χ}(β)e(β(α + c)).

Thus interpreting χ(0) as zero, we have

∑_{α∈F_{p^{n}}} Ψ^{i}(α)χ(α + c) = \frac{1}{τ(\overline{χ})} ∑_{α∈F_{p^{n}}} Ψ^{i}(α) ∑_{β∈F_{p^{n}}} \overline{χ}(β)e(β(α + c))

= \frac{1}{τ(\overline{χ})} ∑_{β∈F_{p^{n}}} \overline{χ}(β)e(βc) \overbrace{∑_{α∈F_{p^{n}}} Ψ^{i}(α)e(βα)}^{also a Gauss sum}

= \frac{1}{τ(\overline{χ})} ∑_{β∈F_{p^{n}}} \overline{χ}(β)e(βc)\overline{Ψ}^{i}(β)τ(Ψ^{i})

= \frac{τ(Ψ^{i})}{τ(\overline{χ})} ∑_{β∈F_{p^{n}}} \overline{χ}(β)\overline{Ψ}^{i}(β)e(βc)

Observe that

τ(\overline{χ})χ(n) = ∑_{α∈F_{p^{n}}} \overline{χ}(α)e(αn).

So we have that

∑_{α∈F_{p^{n}}} Ψ^{i}(α)χ(α + c) = \frac{τ(Ψ^{i})}{τ(\overline{χ})}τ(\overline{χΨ^{i}})χ(c).

Now, since χ, \overline{χ}, Ψ^{i}, \overline{Ψ}^{i} are non–trivial characters, we apply the theorem of section 5 to see that

| ∑_{α∈F_{p^{n}}} Ψ^{i}(α)χ(α + c)| = p^{n/2}.

Now, we conclude by showing that when (m, p^{n} − 1) = t > 1

| ∑_{θ∈F_{p^{n}}} χ(θ^{m} + c)| = | ∑_{θ∈F_{p^{n}}} χ(θ^{t} + c)|

= | ∑_{i=0}^{t−1} ∑_{α∈F_{p^{n}}} Ψ^{i}(α)χ(α + c)|

≤ ∑_{i=0}^{t−1} | ∑_{α∈F_{p^{n}}} Ψ^{i}(α)χ(α + c)|

≤ ∑_{i=0}^{t−1} p^{\frac{n}{2}}

≤ mp^{\frac{n}{2}} .

Thus, for all m and c, we have that

| ∑_{θ∈F_{p^{n}}} χ(θ^{m} + c)| ≤ mp^{\frac{n}{2}} .

References

[Ar] E. Artin: Collected Papers. Addison–Wesley, 1965.

[B] H. Bilharz: Primdivisoren mit vorgeberger Primitivwurzel. Math. Annalen 114 (1937), 476–492.

[BFI] E. Bombieri, J. Friedlander, and H. Iwaniec: Primes in arithmetic progressions to large moduli. Acta Math. 370 (1986), 203–251.

[D] H. Davenport: On Primitive Roots in Finite Fields. Quart. J. Math. (2) 8 (1937), 308–312. (See also Collected Papers, Vol. 4, p. 1557–1561.)

[GM] R. Gupta and M. Ram Murty: A remark on Artin’s conjecture. Invent. Math. 101 (1990), 225–235.

[GMM] R. Gupta, M. Ram Murty, and V. Kumar Murty: The Euclidean algorithm for S–integers. In Number Theory, 189–201 (H. Kisilevsky and J. Labute, eds.). (Canadian Mathematical Society Conference Proceedings 7) (1987).

[H] C. Hooley: On Artin’s conjecture. J. Reine. Angew. Math. 225 (1967), 209–220.

[HB] D. R. Heath–Brown: Artin’s conjecture for primitive roots. Quart. J. Math. Oxford (2) 37 (1986), 27–38.

[HW] G. H. Hardy and E. M. Wright: An Introduction to the Theory of Numbers, 5th ed. Oxford University Press, 1979.

[IR] K. Ireland and M. Rosen: A Classical Introduction to Modern Number Theory. Springer–Verlag, 1982.

[L] D. Lorenzini: An Invitation to Arithmetic Geometry, Vol. 9. Graduate Studies in Mathematics, American Math Society, 1996, pp. 354–360.

[M1] M. Ram Murty: Artin’s conjecture and elliptic analogues. In Sieve Methods, Exponential Sums, and their Applications in Number Theory, 325–344. (G. R. H. Greaves, G. Harman, and M. N. Huxley, eds.). Cambridge University Press, 1996.

[M2] M. Ram Murty: Artin’s conjecture for primitive roots. Math. Intelligencer 10 (1988) 59–67.

Department of Mathematics, Queen’s University, Kingston, Ontario, K7L 3N6, Canada murty@mast.queensu.ca