Polynomials in many variables

Let 𝔽_{p} = ℤ/pℤ denote the field of integers modulo p. We are interested in polynomials f(x) ∈ 𝔽_{p}[x], and in the maps f : 𝔽_{p} → 𝔽_{p} that they define. In Corollary 2.27 we found that distinct polynomials of degree < p define distinct maps, and also in Theorem 2.28 that any map from 𝔽_{p} to 𝔽_{p} can be obtained by constructing an appropriate polynomial. Indeed, by Fermat’s congruence we see that

(1)  1 − a^{p−1} ≡ \{ \begin{matrix}1 & if a ≡ 0 (mod p) \\ 0 & otherwise. \end{matrix}

Hence if c_{1}, c_{2}, …, c_{p} are given residue classes, and we want f(i) ≡ c_{i} (mod p) for 1 ≤ i ≤ p, then it suffices to take

f(x) = ∑_{i=1}^{p} c_{i}(1 − (x − i)^{p−1}) .

Our first object is to generalize these observations to several variables. To facilitate our discussion, we make the following

Definition. A polynomial f(x) ∈ 𝔽_{p}[x_{1}, …, x_{n}] is said to be reduced if deg_{x_{i}} f < p for 1 ≤ i ≤ n. Two polynomials f(x) and g(x) in 𝔽_{p}[x_{1}, …, x_{n}] are said to be equivalent, and we write f ∼ g, if f(x) ≡ g(x) (mod p) for all x ∈ 𝔽_{p}^{n}.

Theorem 1. Every polynomial f ∈ 𝔽_{p}[x_{1}, …, x_{n}] is equivalent to exactly one reduced polynomial.

Proof. Let f ∈ 𝔽_{p}[x_{1}, …, x_{n}] be given. We show that there is a reduced polynomial equivalent to f. If f is not reduced, then in f there is a monomial term cx_{1}^{k_{1}}x_{2}^{k_{2}} ⋯ x_{n}^{k_{n}} and an i such that k_{i} ≥ p. Replace x_{i}^{k_{i}} by x_{i}^{k_{i}−p+1}. Since x^{k_{i}} ≡ x^{k_{i}−p+1} (mod p) for all x, it follows that the new polynomial is equivalent to f. Repeat this operation until a reduced polynomial is obtained.

If two reduced polynomials are equivalent, then their difference, call it f, is a reduced polynomial with the property that f(x) ≡ 0 (mod p) for all x ∈ 𝔽_{p}^{n}. We show that in this case every coefficient of f is 0 (mod p). To do this, we argue by induction on n. The basis of the induction is the case n = 1 which has already been treated. Write

f(x) = ∑_{i=0}^{p−1} f_{i}(x_{1}, …, x_{n−1})x_{n}^{i} .

If we think of x_{1}, …, x_{n−1} as being fixed residue classes (mod p), then the above is a polynomial in the single variable x_{n}. Since the above is 0 (mod p) for every choice of x_{n}, it follows by the case of one variable that all the coefficients are 0 (mod p). That is, f_{i}(x_{1}, …, x_{n−1}) ≡ 0 (mod p). By the inductive hypothesis, it follows that each coefficient of f_{i} is 0 (mod p). Hence all coefficients of f are 0 (mod p).

To appreciate the above from an algebraic standpoint, in 𝔽_{p}[x_{1}, …, x_{n}] let ℐ_{1} denote the ideal consisting of those polynomials f such that f(x) ≡ 0 (mod p) for all x ∈ 𝔽_{p}^{n}, and let ℐ_{2} = (x_{1}^{p} − x_{1}, x_{2}^{p} − x_{2}, …, x_{n}^{p} − x_{n}), which is to say that ℐ_{2} is the ideal consisting of all polynomials that can be expressed in the form

∑_{i=1}^{n} f_{i}(x)(x_{i}^{p} − x_{i})

where f_{i} ∈ 𝔽_{p}[x_{1}, …, x_{n}]. Clearly ℐ_{2} ⊆ ℐ_{1}. What Theorem 1 expresses is that ℐ_{1} = ℐ_{2}.

We note that there are exactly p^{(p^{n})} maps from 𝔽_{p}^{n} to 𝔽_{p}, and also that there are exactly p^{(p^{n})} reduced polynomials in 𝔽_{p}[x_{1}, …, x_{n}]. Since distinct reduced polynomials define distinct maps, it follows by the pigeonhole principle that each map is defined by a unique reduced polynomial. More explicitly, if for each a ∈ 𝔽_{p}^{n} a residue class c(a) ∈ 𝔽_{p} is given, then we put

(2)  f(x) = ∑_{a∈𝔽_{p}^{n}} c(a) ∏_{i=1}^{n} (1 − (x_{i} − a_{i})^{p−1}).

Thus f is a reduced polynomial with the property that f(a) ≡ c(a) (mod p) for all a.

Theorem 2. (Chevalley) Suppose that P (x) is a polynomial of degree d in n variables, with integral coefficients. If n > d, and if P (0) ≡ 0 (mod p), then there is an x, not all of whose coordinates are divisible by p, such that P (x) ≡ 0 (mod p).

By applying the above to the polynomial P (x + a) − P (a) we see that any value (mod p) taken by P (x) is taken at least twice, if n > d.

Proof. From (1) we see that if P (x) ≡ 0 (mod p) precisely when x_{i} ≡ 0 (mod p) for all i, then

1 − P (x)^{p−1} ≡ \{ \begin{matrix}1 & (x_{i} ≡ 0 (mod p) for all i), \\ 0 & (otherwise.) \end{matrix}

By taking c(0) = 1 and all other c(a) = 0 in (2), we deduce that

1 − P (x)^{p−1} ≡ ∏_{i=1}^{n} (1 − x_{i}^{p−1}) (mod p)

for all choices of the variables x_{i}. The polynomial on the right hand side above is reduced, but the left hand side is not necessarily reduced. Let Q(x) be a reduced polynomial equivalent to the left hand side above. Hence

Q(x) ≡ ∏_{i=1}^{n} (1 − x_{i}^{p−1}) (mod p)

for all choices of the variables x_{i}. By Theorem 1, it follows that all coefficients of

∏_{i=1}^{n} (1 − x_{i}^{p−1}) − Q(x)

are divisible by p. But the monomial x_{1}^{p−1} ⋯ x_{n}^{p−1} has coefficient (−1)^{n} in the product, and coefficient 0 in Q, since deg Q ≤ d(p − 1) < n(p − 1). This is a contradiction, so the proof is complete.

We now lay the foundation for a stronger result.

Lemma 1. For non-negative integers k, let S_{k}(p) = ∑_{a=1}^{p} a^{k}. Then

S_{k}(p) ≡ \{ \begin{matrix}−1 (mod p) & if k ≡ 0 (mod p − 1) and k > 0, \\ 0 (mod p) & otherwise. \end{matrix}

Note: We take a^{0} = 1 for all a, including a = 0.

Proof. Clearly S_{0}(p) = p ≡ 0 (mod p). S(0) = p ≡ 0 (mod p). Also, if k > 0 and (p − 1)|k, then by Fermat’s congruence

S_{k}(p) ≡ ∑_{a=1}^{p−1} 1 ≡ −1 (mod p).

Finally, suppose that k > 0 and that k ≢ 0 (mod p − 1). Recall that if (c, p) = 1, then the numbers ca form a complete residue system as a runs through a complete residue system (Theorem 2.6). Hence c^{k}S_{k}(p) ≡ S_{k}(p) (mod p). That is, S_{k}(p)(c^{k} − 1) ≡ 0 (mod p). But since k ≢ 0 (mod p − 1), there is a c such that c^{k} ≢ 1 (mod p). Indeed, a primitive root will do. Hence S_{k}(p) ≡ 0 (mod p), and the proof is complete.

Theorem 3. (Warning) Suppose that P (x) is a polynomial of degree d in n variables, with integral coefficients. If n > d, then the number of solutions of the congruence P (x) ≡ 0 (mod p) is divisible by p.

Proof. By (1) we see that the number of solutions of this congruence is congruent (mod p) to

∑_{x_{1}=1}^{p} ∑_{x_{2}=1}^{p} ⋯ ∑_{x_{n}=1}^{p} 1 − P (x)^{p−1}.

Let cx_{1}^{k_{1}}x_{2}^{k_{2}} ⋯ x_{n}^{k_{n}} be one of the monomial terms that make up the polynomial 1−P (x)^{p−1}. The contribution made to the above sum by this monomial term is

c ∏_{i=1}^{n} ( ∑_{x_{i}=1}^{p} x_{i}^{k_{i}}).

Since P has degree d, we know that ∑_{i=1}^{n} k_{i} ≤ d(p − 1). But n > d, so the inequality k_{i} < p − 1 holds for at least one i. By Lemma 1, this value of i contributes a factor ≡ 0 (mod p) to the above product.

If P (x) is a form (i.e., a homogeneous polynomial) of degree d > 0, then P (0) = 0, so it follows from either Theorem 2 or Theorem 3 that the congruence P (x) ≡ 0 (mod p) must also have at least one non-trivial solution. For example, the congruence x^{2} + y^{2} + z^{2} ≡ 0 (mod p) always has a solution with not all variables divisible by p.

Exercises

1. Let f ∈ 𝔽_{p}[x_{1}, …, x_{n}] have degree d < n. Show that

∑_{\begin{matrix}x∈𝔽_{p}^{n} \\ f(x)≡0 (mod p) \end{matrix}} x_{i}^{k} ≡ 0 (mod p)

for 1 ≤ i ≤ n, 0 ≤ k < p − 1.

2. For 1 ≤ j ≤ m let f_{j} ∈ 𝔽_{p}[x_{1}, …, x_{n}], and put d_{j} = deg f_{j}. Show that if ∑ d_{j} < n, then the system of simultaneous congruences

f_{j}() ≡ 0 (mod p) (1 ≤ j ≤ m)

has at least two solutions, if it has one.

3. Show that in the situation of the preceding exercise, that the number of solutions is a multiple of p.

4. (a) Let S_{k}(p) be defined as in Lemma 1. Use the binomial theorem to show that

∑_{k=0}^{n−1} ({n \atop k})S_{k}(p) ≡ 0 (mod p) .

(b) Deduce that

∑_{\begin{matrix}0<k<n \\ (p−1)|k \end{matrix}} ({n \atop k}) ≡ 0 (mod p) .