Characters, Jacobi Sums, and Gauss Sums:

Counting solutions to diagonal equations in finite field towers

Alexander Russell Perlis

The following detailed account of Weil’s counting technique is separate from the preceding expository account of Weil’s paper. There is nothing here that does not appear in the first 9 pages of Weil’s paper; however, my presentation includes more details in some places and my notation is slightly different. There is nothing here that does not appear in chapters 8–11 of the book by Ireland–Rosen; however, my presentation sticks to the point and thus is closer in length to Weil’s own account. Corrections and comments are appreciated; send them to aprl@math.arizona.edu.

The equations to be considered here are those of the form

⟨1⟩  a_{0}x_{0}^{n_{0}} + a_{1}x_{1}^{n_{1}} + ⋯ + a_{r}x_{r}^{n_{r}} = b.

Such an equation might be termed diagonal to draw attention to the fact that there are no cross-terms (such as x_{1}x_{3}^{2}) and that each variable appears once (as opposed to x_{1} + x_{1}^{2}).

Fix a finite field F_{q} and fix an equation ⟨1⟩. The coefficients a_{i} are nonzero elements of F_{q}, the constant b is an arbitrary element of F_{q}, and the exponents n_{i} are positive integers. The goal is to count solutions to ⟨1⟩ simultaneously over each finite extension F_{q^{ν}} of F_{q}. The last point is important: although knowing how to count solutions over F_{q} certainly implies knowing how to do the same over an extension of F_{q}—after all, q is arbitrary— there is no guarantee that the formulas involved should bear a useful resemblance to each other. The goal here, however, is to find a single formula, which depends on ⟨1⟩, on q, and on ν (the degree of the extension F_{q^{ν}} /F_{q}), that expresses the number of solutions to ⟨1⟩ over F_{q^{ν}}.

Here is a brief description of the approach: The number of solutions to ⟨1⟩ over F_{q} will be expressed in various ways, first in terms of character sums, then in terms of Jacobi sums, but ultimately in terms of Gauss sums. Since q was arbitrary, replacing q with q^{ν} gives us the number of solutions to ⟨1⟩ over F_{q^{ν}} in terms of Gauss sums over F_{q^{ν}}. Finally, the Hasse–Davenport theorem expresses Gauss sums over F_{q^{ν}} in terms of Gauss sums over F_{q}; thus we end up with a single formula.

Let us get started. For quite a while, our work will concentrate over F_{q}. Recall that the multiplicative group F_{q}^{×} is cyclic of order q − 1; throughout, let w denote a generator of this group. (The notation remains consistent throughout; a reference table of notation appears at the end.) For u ∈ F_{q}, let N(x^{n} = u) denote the number of solutions to x^{n} = u over F_{q}. If u = 0, then x = 0 is the unique solution. For u ≠ 0, there are solutions if and only if u ∈ F_{q}^{×n}, i.e., if and only if u is an nth power; in this case, the number of solutions is the same as the number of distinct roots of unity of order dividing n. (Adjusting a solution by such a root of unity certainly gives another solution, and any two solutions must differ by such a root of unity.) Since the order of any root of unity in F_{q}^{×} must divide q − 1 (the order of the group), the roots of unity of order dividing n are precisely those of order dividing d = gcd(n, q − 1). In fact, F_{q}^{×} contains precisely d such roots of unity, namely the first d powers of the element w^{(q−1)/d}, which compose the unique cyclic subgroup of F_{q}^{×} of order d. As a consequence, one sees that N(x^{n} = u) = N(x^{d} = u). This may be explained separately by observing that the map x ↦ x^{n/d}, although not an automorphism of the group F_{q}^{×} (since n/d is not necessarily coprime to q − 1), is an automorphism of the group F_{q}^{×d} onto the group F_{q}^{×n}. In summary,

N(x^{n} = u) = N(x^{d} = u) = \{ \begin{matrix}1, & if u = 0; \\ d, & if u ≠ 0 and u ∈ F_{q}^{×n} = F_{q}^{×d}; \\ 0, & if u ≠ 0 and u ∉ F_{q}^{×n} = F_{q}^{×d}. \end{matrix}

From a computational standpoint, this result is useful only if one may easily determine whether a given nonzero u is a dth power. In terms of our generator w, this is easy: the dth powers are precisely those powers of w whose exponents are multiples of d. (Observe that this statement relies on the fact d | q − 1; certainly the nth powers are in general not just those powers of w whose exponents are multiples of n.) Thus, if we write u = w^{k}, and then use the division algorithm to write k = td + r, where 0 ≤ r < d, then the number N(x^{d} = w^{k}) = N(x^{d} = w^{td+r}) is d when r = 0, and 0 otherwise.

Now we will express N(x^{n} = u) in terms of character sums. A (multiplicative) character is a group homomorphism χ: F_{q}^{×} → C^{×}. Such a map χ is completely determined by its behavior on w (our generator of F_{q}^{×}), and the image of w must be some element of C^{×} of order dividing q − 1. Let ζ ∈ C^{×} denote a primitive root of unity, i.e., an element of order q − 1; there are many choices for ζ, but for computation purposes one might as well set ζ = e^{2πi/(q−1)}. There are precisely q − 1 characters, namely the maps determined by w ↦ ζ^{k}, for 0 ≤ k < q − 1. The product of two characters is defined by (χ_{1}χ_{2})(x) = χ_{1}(x)χ_{2}(x), and under this operation the characters are seen to form a cyclic group, generated by ω: w ↦ ζ. The identity element of this group is the trivial character ε: w ↦ 1. Since χ^{−1}(u) = \overline{χ(u)}, the bar denoting complex conjugation, the inverse of a character χ is often denoted \overline{χ}. As in any cyclic group, there is a unique subgroup of every order dividing the order of the group. Thus if d | q − 1, then there are precisely d characters of order dividing d, and they are easy to write down: they are the first d powers of the character ω_{d}: w ↦ ζ^{(q−1)/d}. In this notation, for d | q − 1, subscripts may be converted to superscripts as follows: ω_{d} = ω^{(q−1)/d}; in particular, ω_{1} is the same as ε, and ω_{q−1} is the same as ω.

The following simple fact is used repeatedly, and now is a good time to state it:

⟨2⟩  u ≠ 1 ⟹ ∑_{χ} χ(u) = 0.

To see this, let T denote the sum; if you choose an arbitrary character χ and write out χ(u)T, then you discover, after a change-of-variable (or change-of-character!), that you get back T; in short, χ(u)T = T for all χ. In particular, choosing χ = ω, we have χ(u) ≠ 1, forcing T = 0. A similar argument shows that χ ≠ ε ⟹ ∑_{u} χ(u) = 0; this time the character is held fixed while its argument ranges across F_{q}^{×}.

For any multiplicative character χ, extend its domain of definition to all of F_{q} by defining χ(0) = 0 for nontrivial characters, and ε(0) = 1 for the trivial character. Warning: if the product of two nontrivial characters is trivial, say χ_{1}χ_{2} = ε, then (χ_{1}χ_{2})(0) ≠ χ_{1}(0)χ_{2}(0). Here is the first interesting result:

⟨3⟩  N(x^{n} = u) = N(x^{d} = u) = ∑_{0≤k<d}ω_{d}^{k}(u).

The sum is taken across all characters of order dividing d, i.e., across the character subgroup of order d. The result clearly holds for u = 0. For u ≠ 0, we must consider, as before, whether u is a dth power. We saw earlier that by writing u = w^{td+r}, with 0 ≤ r < d, then u is a dth power precisely when r = 0. In terms of characters, this may be stated as follows: u is a dth power precisely when each character of order dividing d assigns 1 to u, or more simply, when ω_{d}(u) = 1. After all, if r = 0, then ω_{d}(w^{td}) = ω_{d}(w^{t})^{d} = 1, while if r ≠ 0, then ω_{d}(w^{td+r}) = ω_{d}(w^{r}) = ζ^{r(q−1)/d}, which is not 1 since the exponent is not a multiple of q −1. Now back to the displayed result: if u is a dth power, then each term is 1, giving the desired sum of d. For the remaining case, letting T denote the sum in ⟨3⟩, an argument similar to that used for ⟨2⟩ shows ω_{d}(u)T = T, and since u is not a dth power, ω_{d}(u) ≠ 1, forcing T = 0.

From what we know thus far, we can count the solutions to the original equation ⟨1⟩ over F_{q} as follows. Let N denote the number of solutions. Then, putting d_{i} = gcd(n_{i}, q − 1), we have

N = N(a_{0}x_{0}^{n_{0}} + a_{1}x_{0}^{n_{1}} + ⋯ + a_{r}x_{r}^{n_{r}} = b)

= ∑_{Σa_{i}u_{i}=b} N(x^{n_{0}} = u_{0})N(x^{n_{1}} = u_{1}) ⋯ N(x^{n_{r}} = u_{r})

= ∑_{Σa_{i}u_{i}=b} ∑_{0≤k_{0}<d_{0}} ω_{d_{0}}^{k_{0}}(u_{0}) ∑_{0≤k_{1}<d_{1}} ω_{d_{1}}^{k_{1}}(u_{1}) ⋯ ∑_{0≤k_{r}<d_{r}} ω_{d_{r}}^{k_{r}}(u_{r})

= ∑_{0≤k_{i}<d_{i}} ∑_{Σa_{i}u_{i}=b} ω_{d_{0}}^{k_{0}}(u_{0})ω_{d_{1}}^{k_{1}}(u_{1}) ⋯ ω_{d_{r}}^{k_{r}}(u_{r}).

When each index k_{i} is 0, the rightmost character product is trivially equal to 1. The inner sum runs over q^{r} distinct tuples of the u_{i}: having assigned arbitrary values to u_{1}, …, u_{r}, the value of u_{0} is uniquely determined. Thus, in the case that each index k_{i} is 0, the sum is q^{r}.

I now claim that when some indices are 0, but other indices are not 0, then the sum is 0. In fact, consider the case that k_{0} = 0 but k_{1} ≠ 0; I wish to show ∑_{Σa_{i}u_{i}=b} ε(u_{0})ω_{d_{1}}^{k_{1}}(u_{1}) ⋯ ω_{d_{r}}^{k_{r}}(u_{r}) = 0. Arbitrary assignment of u_{1}, …, u_{r} forces the value of u_{0}, but each term of the sum is independent of u_{0}, and thus our sum is simply ∑_{u_{1},...,u_{r}} ω_{d_{1}}^{k_{1}}(u_{1}) ⋯ ω_{d_{r}}^{k_{r}}(u_{r}), where each u_{i} freely runs over F_{q}. This sum is now seen to be 0, as we can pull out the factor ∑_{u_{1}} ω_{d_{1}}^{k_{1}}(u_{1}), which is 0 by ⟨2⟩. Summary: the presence of at least one trivial character allowed us to free the sum, and the presence of at least one nontrivial character forced the resulting free sum to be 0.

Going back to the displayed expression for N, we can separate the case when each index k_{i} is 0, and ignore the case when some indices are 0 while others are not, to obtain

N = q^{r} + ∑_{0<k_{i}<d_{i}} ∑_{Σa_{i}u_{i}=b} ω_{d_{0}}^{k_{0}}(u_{0})ω_{d_{1}}^{k_{1}}(u_{1}) ⋯ ω_{d_{r}}^{k_{r}}(u_{r}).

If b = 0, introduce the change-of-variables v_{i} = a_{i}u_{i}, while if b ≠ 0, introduce the change-of-variables v_{i} = a_{i}u_{i}/b, to obtain

\begin{aligned}N_{b=0} & = q^{r} + ∑_{0<k_{i}<d_{i}} ω_{d_{0}}^{−k_{0}}(a_{0})ω_{d_{1}}^{−k_{1}}(a_{1}) ⋯ ω_{d_{r}}^{−k_{r}}(a_{r}) \overbrace{∑_{Σv_{i}=0} ω_{d_{0}}^{k_{0}}(v_{0})ω_{d_{1}}^{k_{1}}(v_{1}) ⋯ ω_{d_{r}}^{k_{r}}(v_{r})}^{J_{0}}, \\ N_{b≠0} & = q^{r} + ∑_{0<k_{i}<d_{i}} ω_{d_{0}}^{−k_{0}}(a_{0})ω_{d_{1}}^{−k_{1}}(a_{1}) ⋯ ω_{d_{r}}^{−k_{r}}(a_{r})ω_{d_{0}}^{k_{0}}ω_{d_{1}}^{k_{1}} ⋯ ω_{d_{r}}^{k_{r}}(b) \underbrace{∑_{Σv_{i}=1} ω_{d_{0}}^{k_{0}}(v_{0})ω_{d_{1}}^{k_{1}}(v_{1}) ⋯ ω_{d_{r}}^{k_{r}}(v_{r})}_{J} . \end{aligned}

Here I have denoted certain sums using J_{0} and J. In general, for a collection of characters χ_{0}, …, χ_{r}, define the sums

\begin{aligned}J_{0}(χ_{0}, …, χ_{r}) & = ∑_{Σv_{i}=0} χ_{0}(v_{0})χ_{1}(v_{1}) ⋯ χ_{r}(v_{r}), \\ J(χ_{0}, …, χ_{r}) & = ∑_{Σv_{i}=1} χ_{0}(v_{0})χ_{1}(v_{1}) ⋯ χ_{r}(v_{r}). \end{aligned}

The latter sum is known as a Jacobi sum. I now show, in the case that all characters are nontrivial, how to rewrite J_{0} in terms of J; thus, even when b = 0, the number of solutions to our original equation ⟨1⟩ can always be written in terms of Jacobi sums. The crucial fact is

⟨4⟩  χ_{i} ≠ ε, χ_{0}χ_{1} ⋯ χ_{r} ≠ ε ⟹ J_{0}(χ_{0}, …, χ_{r}) = 0,
⟨5⟩  χ_{i} ≠ ε, χ_{0}χ_{1} ⋯ χ_{r} = ε ⟹ J_{0}(χ_{0}, …, χ_{r}) = (q − 1)\overbrace{χ_{1} ⋯ χ_{r}(−1)}^{χ_{0}(−1)}J(χ_{1}, …, χ_{r}).

Observe that in the interesting case χ_{0}χ_{1} ⋯ χ_{r} = ε, in the process of rewriting J_{0} in terms of a Jacobi sum, one character (it doesn’t matter which) disappears. Let me now establish the claim. Start with

J_{0} = ∑_{v_{0}} χ_{0}(v_{0}) ∑_{v_{1}+···+v_{r}=−v_{0}} χ_{1}(v_{1}) ⋯ χ_{r}(v_{r}).

Since χ_{0} ≠ ε, we have χ_{0}(0) = 0. Introducing the change-of-variables u_{i} = −v_{i}/v_{0}, we obtain

J_{0} = ∑_{v_{0}≠0} χ_{0}(v_{0}) ∑_{u_{1}+···+u_{r}=1} χ_{1}(−u_{1}v_{0}) ⋯ χ_{r}(−u_{r}v_{0})

= ∑_{v_{0}≠0} χ_{1} ⋯ χ_{r}(−1)χ_{0}χ_{1} ⋯ χ_{r}(v_{0})\overbrace{∑_{u_{1}+···+u_{r}=1} χ_{1}(u_{1}) ⋯ χ_{r}(u_{r})}^{J(χ_{1},...,χ_{r})}

= χ_{1} ⋯ χ_{r}(−1)J(χ_{1}, …, χ_{r}) ∑_{v_{0}≠0} χ_{0}χ_{1} ⋯ χ_{r}(v_{0}).

The inner sum is either q − 1 or 0; the former occurs when χ_{0}χ_{1} ⋯ χ_{r} is trivial. This establishes ⟨4⟩ and ⟨5⟩.

Going back to our expression for N_{b=0}, in which J_{0} occurred, we now ask for which tuples of indices k_{i} do we have ω_{d_{0}}^{k_{0}}ω_{d_{1}}^{k_{1}} ⋯ ω_{d_{r}}^{k_{r}} = ε? The character in question is ω^{k_{0}(q−1)/d_{0}+k_{1}(q−1)/d_{1}+···+k_{r}(q−1)/d_{r}}, and this is trivial precisely when the exponent is a multiple of q − 1, which happens precisely when ∑ k_{i}/d_{i} is an integer. Hence we obtain

⟨6⟩  N_{b=0} = q^{r} + (q − 1) ∑_{{0<k_{i}<d_{i} \atop Σk_{i}/d_{i}∈Z}} ω_{d_{0}}^{−k_{0}}(a_{0})ω_{d_{1}}^{−k_{1}}(a_{1}) ⋯ ω_{d_{r}}^{−k_{r}}(a_{r})ω_{d_{1}}^{k_{1}} ⋯ ω_{d_{r}}^{k_{r}}(−1)J(ω_{d_{1}}^{k_{1}}, …, ω_{d_{r}}^{k_{r}}),

⟨7⟩  N_{b≠0} = q^{r} + ∑_{0<k_{i}<d_{i}} ω_{d_{0}}^{−k_{0}}(a_{0})ω_{d_{1}}^{−k_{1}}(a_{1}) ⋯ ω_{d_{r}}^{−k_{r}}(a_{r})ω_{d_{0}}^{k_{0}}ω_{d_{1}}^{k_{1}} ⋯ ω_{d_{r}}^{k_{r}}(b)J(ω_{d_{0}}^{k_{0}}, ω_{d_{1}}^{k_{1}}, …, ω_{d_{r}}^{k_{r}}).

There is a different Jacobi sum for each collection of characters—computing N using the formulas above can be quite tedious! On the other hand, associated to each single character is a Gauss sum, to be defined below. Thus there are precisely q − 1 Gauss sums. Even better, Jacobi sums can be expressed in terms of Gauss sums. Thus, having computed the Gauss sums once and for all, Jacobi sums are easily computed as they arise.

Choose, once and for all, a nontrivial additive character ψ: F_{q}^{+} → C^{×}; for example, fix ξ = e^{2πi/p}, and set ψ(u) = ξ^{trace(u)}, where trace: F_{q}^{+} → F_{p}^{+} = (Z/pZ)^{+} is the trace map, defined by trace(u) = u^{p} + u^{p^{2}} + ⋯ + u^{q}. For any multiplicative character χ, define the Gauss sum

g(χ) = ∑_{u∈F_{q}} χ(u)ψ(u).

The result g(ε) = 0 is immediately established using the argument from ⟨2⟩. For nontrivial χ, we have:

⟨8⟩  χ ≠ ε ⟹ g(χ)\overline{g(χ)} = |g(χ)|^{2} = q,
⟨9⟩  χ ≠ ε ⟹ g(χ)g(\overline{χ}) = qχ(−1).

These results are established by calculation:

g(χ)\overline{g(χ)} = ∑_{u≠0} χ(u)ψ(u) ∑_{v≠0} \overline{χ}(v)\overline{ψ}(v) = ∑_{u≠0} χ(u)ψ(u) ∑_{v≠0} \overline{χ}(uv)\overline{ψ}(uv) = ∑_{u≠0} ∑_{v≠0} \overline{χ}(v)ψ(u − uv)

= ∑_{v≠0} \underbrace{\overline{χ}(v) ∑_{u≠0} ψ(u(1 − v))}_{q−1 when v=1} = q − 1 + ∑_{v≠0,1} \overline{χ}(v) \underbrace{∑_{u≠0} ψ(u)}_{−1} = q − 1 − \underbrace{∑_{v≠0,1} \overline{χ}(v)}_{−1} = q.

g(χ)\overline{g(χ)} = g(χ) ∑_{u} \overline{χ}(u)\overline{ψ}(u) = g(χ) ∑_{u} \overline{χ}(−u)\overline{ψ}(−u) = g(χ) ∑_{u} \overline{χ}(u)\overline{χ}(−1)ψ(u) = g(χ)\overline{χ}(−1) \overbrace{∑_{u} \overline{χ}(u)ψ(u)}^{g(\overline{χ})} .

Gauss sums have been fun thus far by themselves, but we are really interested in writing our Jacobi sums in terms of Gauss sums. We only need to do this when all characters are nontrivial, and the result is

⟨10⟩  χ_{i} ≠ ε, χ_{0}χ_{1} ⋯ χ_{r} ≠ ε ⟹ J(χ_{0}, χ_{1}, …, χ_{r}) = \frac{g(χ_{0})g(χ_{1}) ⋯ g(χ_{r})}{g(χ_{0}χ_{1} ⋯ χ_{r})},
⟨11⟩  χ_{i} ≠ ε, χ_{0}χ_{1} ⋯ χ_{r} = ε ⟹ J(χ_{0}, χ_{1}, …, χ_{r}) = −χ_{0}(−1)J(χ_{1}, …, χ_{r})

= −χ_{0}(−1)\frac{g(χ_{1}) ⋯ g(χ_{r})}{g(χ_{1} ⋯ χ_{r})}.

To see this, start with

g(χ_{0})g(χ_{1}) ⋯ g(χ_{r}) = ∑_{u_{0}} χ_{0}(u_{0})ψ(u_{0}) ∑_{u_{1}} χ_{1}(u_{1})ψ(u_{1}) ⋯ ∑_{u_{r}} χ_{r}(u_{r})ψ(u_{r})

= ∑_{u_{i}} χ_{0}(u_{0})χ_{1}(u_{1}) ⋯ χ_{r}(u_{r})ψ(\underbrace{u_{0} + u_{1} + ⋯ + u_{r}}_{t}) = ∑_{t} ψ(t) \underbrace{∑_{Σu_{i}=t} χ_{0}(u_{0})χ_{1}(u_{1}) ⋯ χ_{r}(u_{r})}_{J_{0} when t=0}

= J_{0}(χ_{0}, …, χ_{r}) + ∑_{t≠0} ψ(t) ∑_{Σu_{i}=t} χ_{0}(u_{0})χ_{1}(u_{1}) ⋯ χ_{r}(u_{r})

= J_{0}(χ_{0}, …, χ_{r}) + ∑_{t≠0} ψ(t) ∑_{Σv_{i}=1} χ_{0}(tv_{0})χ_{1}(tv_{1}) ⋯ χ_{r}(tv_{r}) (here v_{i} = u_{i}/t)

= J_{0}(χ_{0}, …, χ_{r}) + \underbrace{∑_{t≠0} ψ(t)χ_{0}(t)χ_{1}(t) ⋯ χ_{r}(t)}_{T} \underbrace{∑_{Σv_{i}=1} χ_{0}(v_{0})χ_{1}(v_{1}) ⋯ χ_{r}(v_{r})}_{J(χ_{0},...,χ_{r})} .

In the case χ_{0}χ_{1} ⋯ χ_{r} ≠ ε, the earlier result ⟨4⟩ gives J_{0} = 0, while the sum T above is just g(χ_{0}, χ_{1}, …, χ_{r}), thus establishing ⟨10⟩. Consider now the case χ_{0}χ_{1} ⋯ χ_{r} = ε. Result ⟨5⟩ gives J_{0} = (q − 1)χ_{0}(−1)J(χ_{1}, …, χ_{r}), while the sum T, being one trivial term short of a trivial Gauss sum, is −1. Now we work on the product of Gauss sums on the left side. Temporary removal of one character allows application of ⟨10⟩ to obtain

\begin{aligned}g(χ_{1}) ⋯ g(χ_{r}) & = g(χ_{1} ⋯ χ_{r})J(χ_{1}, …, χ_{r}), \\ g(χ_{0})g(χ_{1}) ⋯ g(χ_{r}) & = \underbrace{g(χ_{0})g(\overline{χ}_{0})}_{qχ_{0}(−1)} J(χ_{1}, …, χ_{r}). \end{aligned}

Substituting the pieces into our work above gives

qχ_{0}(−1)J(χ_{1}, …, χ_{r}) = (q − 1)χ_{0}(−1)J(χ_{1}, …, χ_{r}) − J(χ_{0}, χ_{1}, …, χ_{r}),

which is the same as ⟨11⟩.

Looking back at ⟨6⟩ and ⟨7⟩, the Jacobi sums are now easily computed in terms of Gauss sums, and so ⟨6⟩ and ⟨7⟩ provide useful formulas for computing N_{b=0} and N_{b≠0}. Since q was arbitrary, the same results apply in F_{q^{ν}}, keeping in mind that the Gauss sums and Jacobi sums must be defined using characters on F_{q^{ν}}. It turns out that Gauss sums and Jacobi sums defined over F_{q^{ν}} can be calculated in terms of Gauss sums and Jacobi sums defined over F_{q}. I shall now describe how this goes.

As usual, the trace and norm maps compute the sum and product of all conjugates (with multiplicities):

trace: F_{q^{ν}}^{+} → F_{q}^{+},  u ↦ u^{p} + u^{p^{2}} + ⋯ + u^{q},
norm: F_{q^{ν}}^{×} → F_{q}^{×},  u ↦ u^{p+p^{2}+···+q}.

The important fact in finite fields is that each map is surjective. Therefore, if ψ is a nontrivial additive character on F_{q}, then ψ′: u ↦ ψ(trace(u)) is a nontrivial additive character on F_{q^{ν}}. Similarly, given a multiplicative character χ on F_{q}, one defines a multiplicative character χ′: u ↦ χ(norm(u)). This sets up a one-to-one correspondence between characters of a given order on F_{q} and characters of the same order on F_{q^{ν}}. Let g′ and J′ denote the Gauss and Jacobi sums over F_{q^{ν}}. The Hasse–Davenport theorem asserts

⟨12⟩  −g′(χ′) = (−g(χ))^{ν}.

An elegant proof of this result appears in the book by Ireland–Rosen. Since the proof gives no insight into counting solutions to equations over finite fields, I have not included it here. As a consequence of ⟨12⟩, a careful counting of signs shows that the separate results ⟨10⟩ and ⟨11⟩ become the single result†

⟨13⟩  χ_{i} ≠ ε ⟹ J′(χ′_{0}, χ′_{1}, …, χ′_{r}) = (−1)^{r(ν+1)}J(χ_{0}, χ_{1}, …, χ_{r})^{ν}.

We should now be in a position to modify formulas ⟨6⟩ and ⟨7⟩ to hold over F_{q^{ν}}, but there is one remaining obstacle. Those formulas involve d_{i} = gcd(n_{i}, q −1), and it is not immediately clear how to calculate gcd(n_{i}, q^{ν} −1) in terms of d_{i}. So we cheat: let us restrict attention to the case that each n_{i} | q − 1. Then d_{i} = n_{i}, and our problem is solved. Letting N_{ν} denote the number of solutions to ⟨1⟩ over F_{q^{ν}}, applying ⟨13⟩ to results ⟨6⟩ and ⟨7⟩ gives:

b = 0, n_{i} | q − 1 ⟹ ⟨14⟩

N_{ν} = q^{νr} + (q^{ν} − 1)(−1)^{(r−1)(ν+1)} ∑_{{0<k_{i}<n_{i} \atop Σk_{i}/n_{i}∈Z}} \{ω_{d_{0}}^{−k_{0}}(a_{0})ω_{d_{1}}^{−k_{1}}(a_{1}) ⋯ ω_{d_{r}}^{−k_{r}}(a_{r})ω_{d_{1}}^{k_{1}} ⋯ ω_{d_{r}}^{k_{r}}(−1)J(ω_{d_{1}}^{k_{1}}, …, ω_{d_{1}}^{k_{r}})\}^{ν},

b ≠ 0, n_{i} | q − 1 ⟹ ⟨15⟩

N_{ν} = q^{νr} + (−1)^{r(ν+1)} ∑_{0<k_{i}<n_{i}}{ω_{d_{0}}^{−k_{0}}(a_{0})ω_{d_{1}}^{−k_{1}}(a_{1}) ⋯ ω_{d_{r}}^{−k_{r}}(a_{r})ω_{d_{0}}^{k_{0}}ω_{d_{1}}^{k_{1}} ⋯ ω_{d_{r}}^{k_{r}}(b)J(ω_{d_{0}}^{k_{0}}, ω_{d_{1}}^{k_{1}}, …, ω_{d_{r}}^{k_{r}})}^{ν}.

Finally, if instead of counting the precise number of solutions one merely wishes a good estimate, then this can be obtained as follows. Applying the measurement in ⟨8⟩ to results ⟨10⟩ and ⟨11⟩ gives

\begin{aligned}χ_{i} ≠ ε, χ_{0}χ_{1} ⋯ χ_{r} ≠ ε ⟹ |J(χ_{0}, χ_{1}, …, χ_{r})|^{2} & = q^{r}, \\ χ_{i} ≠ ε, χ_{0}χ_{1} ⋯ χ_{r} = ε ⟹ |J(χ_{0}, χ_{1}, …, χ_{r})|^{2} & = q^{r−1}. \end{aligned}

† I have not seen this elegant fact stated elsewhere.

Applying this measurement to ⟨14⟩ gives

|N_{ν,b=0} − q^{νr}| ≤ Mq^{ν(r−1)/2},

where M is the number of tuples of k_{i} satisfying 0 < k_{i} < d_{i}, ∑ k_{i}/d_{i} ∈ Z, and where d_{i} = gcd(n_{i}, q^{ν} − 1). Since M is bounded (by ∏ n_{i}, for example), this result shows that N_{ν} doesn’t deviate from q^{νr} too much as ν → ∞; in particular, there are always solutions if ν is taken sufficiently large. (Observe also that the restriction n_{i} | q − 1, important in ⟨14⟩, is not required here.)

Applying the Jacobi sum measurement to ⟨15⟩ gives

|N_{ν,b≠0} − q^{νr}| ≤ M_{ε}q^{ν(r−1)/2} + (M − M_{ε})q^{νr/2},

where M is the total number of tuples of k_{i} satisfying 0 < k_{i} < d_{i}, and M_{ε} is the number of those tuples that furthermore satisfy ∑ k_{i}/d_{i} ∈ Z. As before, these quantities are bounded, and we always get solutions if ν is taken sufficiently large.

TABLE OF NOTATION

Symbol  Explanation
p  Fixed prime number
q  Some power of p
F_{q}  Finite field of q elements
F_{q^{ν}}  Degree ν extension of F_{q}
N(eqn)  Number of solutions over F_{q} of the given equation
χ  Arbitrary multiplicative character F_{q}^{×} → C^{×}
w  Fixed generator of multiplicative group F_{q}^{×}
ζ  Fixed primitive root of unity of order q − 1
ω  Multiplicative character w ↦ ζ of order q − 1
d  Some divisor of q − 1
ω_{d}  Multiplicative character w ↦ ζ^{(q−1)/d} of order d
ε  Trivial multiplicative character w ↦ 1
ξ  Primitive root of unity of order p
ψ  Fixed nontrivial additive character F_{q}^{+} → C^{×}
g(χ)  Gauss sum associated to a multiplicative character
J(χ, …)  Jacobi sum associated to multiplicative characters
J_{0}(χ, …)  Variant of Jacobi sum