Proofs of the Chevalley-Warning Theorem

Question

A well known proof of the Chevally-Warning Theorem is the one listed on wikipedia: http://en.wikipedia.org/wiki/Chevalley%E2%80%93Warning_theorem

Are there any other proofs of this, or generalizations of it?

Answer 1

I am working on a book-length manusript, Around the Chevalley–Warning Theorem. A complete answer to your question is estimated at about 150 pages!

In terms of what exists at the moment, here are two papers. Both of them make connections between the classical results of Chevalley and Warning and modern polynomial methods. The first concerns a generalization of the (unjustly almost forgotten) Warning's Second Theorem to restricted variables. The second explains the connection between Chevalley's Theorem and Alon's Combinatorial Nullstellensatz. I take the perspective that the Combinatorial Nullstellensatz is in fact a very direct generalization of Chevalley's proof of Chevalley's Theorem. (I don't mean "very direct" as a slight against Alon: I am certainly a fan. Rather it is meant to indicate a useful — at least for a number theorist — way of thinking about these results.)

I'm afraid the above seems overly self-promotional. Let me also give what I think are the most important papers in this area, with an emphasis on relatively elementary work. [So I will not list e.g. work of Esnault, though I agree with Daniel Loughran's suggestion that it is, at least in some sense, the most important result of Chevalley–Warning type.]

J. Ax, Zeroes of polynomials over finite fields. Amer. J. Math. 86 (1964), 255–261.

C. Chevalley, Démonstration d’une hypothèse de M. Artin. Abh. Math. Sem. Univ. Hamburg 11 (1935), 73–75.

D.R. Heath-Brown, On Chevalley–Warning theorems. (Russian. Russian summary) Uspekhi Mat. Nauk 66 (2011), no. 2(398), 223–232; translation in Russian Math. Surveys 66 (2011), no. 2, 427–436.

D.J. Katz, Point count divisibility for algebraic sets over $\mathbb{Z} / p^{ \ell } \mathbb{Z}$ and other finite principal rings. Proc. Amer. Math. Soc. 137 (2009), 4065–4075.

N.M. Katz, On a theorem of Ax. Amer. J. Math. 93 (1971), 485–499.

M. Marshall and G. Ramage, Zeros of polynomials over finite principal ideal rings. Proc. Amer. Math. Soc. 49 (1975), 35–38.

O. Moreno and C.J. Moreno, Improvements of the Chevalley–Warning and the Ax–Katz theorems. Amer. J. Math. 117 (1995), 241–244.

S.H. Schanuel, An extension of Chevalley's theorem to congruences modulo prime powers. J. Number Theory 6 (1974), 284–290.

G. Terjanian, Sur les corps finis. C. R. Acad. Sci. Paris S'er. A-B 262 (1966), A167–A169.

D.Q. Wan, An elementary proof of a theorem of Katz. Amer. J. Math. 111 (1989), 1–8.

E. Warning, Bemerkung zur vorstehenden Arbeit von Herrn Chevalley. Abh. Math. Sem. Hamburg 11 (1935), 76–83.

Less than a year ago I thought there were about ten papers which generalize and refine the Chevalley-Warning Theorem. I now think I was off by a full order of magnitude, and indeed my current bibliography contains about 100 references. (I will admit that at this point, the radius of the circle referred to in Around the Chevalley–Warning Theorem is rather large. It includes for instance material on Davenport constants and on polynomial interpolation.)

Added: To answer the question more directly: Chevalley's proof critically uses the observation that if $P_1,\ldots,P_r$ are polynomials in $n$ variables over $\mathbb{F}_q$, then the function

$x \in \mathbb{F}_q^n \mapsto \chi(x_1,\ldots,x_n) = \prod_{i=1}^r(1-P_i(x_1,\ldots,x_n)^{q-1})$

is the characteristic function of the set

$Z = \{ (x_1,\ldots,x_n) \in \mathbb{F}_q^n \mid P_1(x_1,\ldots,x_n) = \ldots = P_r(x_1,\ldots,x_n) = 0\}$.

Every other proof of Chevalley's Theorem I know uses this observation. The subsequent proofs of Chevalley's Theorem other than Ax's proof look (to me) essentially the same as Chevalley's. Ax's proof uses (only!) Chevalley's observation and Ax's Lemma: if $\operatorname{deg} P < (q-1)n$, then $\sum_{x \in \mathbb{F}_q^n} P(x) = 0$. Ax's Lemma is impressively easy to prove: it would be a fair question on many undergraduate algebra midterms. I think I saw somewhere the claim that it goes back to V. Lebesgue. I still cannot quite see Ax's argument as a recasting of Chevalley's. So after all this I suppose I would say that there are "really two proofs".

Answer 2

One of the best results in this vein which I know of is due to Hélène Esnault, and appears in the paper:

Varieties over a finite field with trivial Chow group of 0-cycles have a rational point, Invent. math. 151 (2003), 187-191.

One particularly nice result in this paper is Corollary 1.3, which states that any Fano variety over a finite field, or more generally any chain rationally connected variety, admits a rational point. The proof naturally uses the full force of étale cohomology.

It is not quite clear to me that this recovers the original Chevalley–Warning theorem in its full generality, as she assumes that her varieties are smooth and projective. But this certainly recovers the special case of the Chevalley–Warning theorem when the variety in question is smooth and projective.

Answer 3

Regarding the "weak" form of Chevalley-Warning - namely that the number of solutions is not exactly one, rather than being necessarily divisible by the characteristic - there is a combinatorial proof using Alon's "combinatorial nullstellensatz", as was already noted in Alon's original paper. But the nullstellensatz is significantly more general than Chevalley-Warning and has a large number of applications in combinatorics.

Answer 4

For Chevalley's theorem, i.e., number of common zeroes not being one, any new proof of the following Lemma would give a 'new' proof.

Lemma Let $P \in \mathbb{F}_q[x_1, \ldots, x_n]$ such that $P(a) \neq 0$ for some fixed $a = (a_1, \ldots, a_n) \in \mathbb{F}_q^n$ but $P(x) = 0$ for all $x \in \mathbb{F}_q^n \setminus \{a\}$. Then $\deg P \geq n(q-1)$.

For given $P_1, \ldots, P_r$ in $\mathbb{F}_q[x_1, \ldots, x_n]$ with $\sum \deg P_i < n$, the trick is to define $P = \prod (1 - P_i^{q-1})$ as mentioned in Peter Clark's answer. If the set of common zeroes is a singleton then we have a contradiction to the Lemma above, hence proving the Chevalley's theorem.

So, let's discuss some possible proofs of the Lemma. Define $Q := \prod_{i = 1}^n (1 - ( x_i - a_i)^{q-1})$ and let $P(a) = \lambda \neq 0$. Note that $\deg Q = n(q-1)$, $Q(a) = 1$ and $Q(x) = 0$ for all $x \in \mathbb{F}_q^n \setminus \{a\}$. We'll use $Q$ in Proof 1 and 2.

Proof 1. If $\deg P < n(q-1)$, then $\lambda Q - P$ is a non-zero polynomial of degree $n(q-1)$ that vanishes on the grid $\mathbb{F}_q^n$ but has a non-zero coefficient of the term $\prod x_i^{q-1}$, contradicting Alon's combinatorial nullstellensatz.

Proof 2. It can be shown that for every polynomial $P$ there exists a unique polynomial $\widehat P$ such that $P - \widehat P \in I = \langle x_1^q - x_1, \ldots, x_n^q - x_n \rangle$ ($I$ is the ideal of polynomials vanishing everywhere on $\mathbb{F}_q^n$) and $\deg_{x_i} \widehat P \leq q-1$ for all $i$. Moreover, $\deg P \geq \deg \widehat P$. Now, since $\widehat P - \lambda Q$ vanishes everywhere it must be the zero polynomial (degree in each variable is at most $q-1$). Therefore $\widehat P = \lambda Q$ and $\deg P \geq \deg \widehat P = \deg Q = n(q-1)$.

Proof 3. For each $r \in \mathbb{F} \setminus \{a_1\}$ the polynomial $\widehat P(r, x_2, \ldots, x_n)$ is the zero polynomial, and hence $x_1 - r$ divides $\widehat P$. This can be done for every $i$ and every $r \in \mathbb{F}_q \setminus \{a_i\}$. Therefore, $\deg P \geq \deg \widehat P \geq n(q-1)$.

Proof 4. There is a bijection between functions from $\mathbb{F}_q^n$ to $\mathbb{F}_q$ and polynomials with degree in each variable at most $q-1$. For any $b \in \mathbb{F}_q^n$ define the polynomial $P_b = \widehat P (x - (b-a))$. Since each $P_b$ vanishes everywhere except at $b$, by Lagrange interpolation, $P_b$'s span the whole space of polynomials/functions. In particular, the monomial $\prod x_i^{q-1}$ must be a linear combination of $P_b$'s. This means that the coefficient of $\prod x_i^{q-1}$ in $\widehat P$, which is the same as its coefficient in every $P_b$, must be non-zero.

Proof 5 Use Ax's lemma, i.e., if $\deg P < n(q-1)$ then $\sum_{x \in \mathbb{F}_q^n} P(x) = 0$. But we know that this sum is equal to $P(a) \neq 0$.

Proof 6 WLOG let $a = (0, \ldots, 0)$ and let $\alpha \in \mathbb{F}_q^\times$. Then by division over $\mathbb{F}_q[x_2, \ldots, x_n][x_1]$ we can write $P = (x_1 - \alpha)Q_\alpha + R_\alpha$. It is easy to see that $R_\alpha = P(\alpha, x_2, \ldots, x_n) \in \mathbb{F}_q[x_2, \ldots, x_n]$. By substituting $x_1 = \alpha$ in the equation above, we see that $R_\alpha(x) = 0$ for all $x \in \mathbb{F}_q^{n-1}$ and hence, $R_\alpha \in \langle x_2^q - x_2, \ldots, x_n^q - x_n \rangle \subseteq I$. Moreover, $\deg P \geq \deg R_\alpha$.

We can repeat this for the polynomial $Q_\alpha$, by picking some $\beta \neq \alpha$ in $\mathbb{F}_q^\times$. We could do this for every non-zero element in $\mathbb{F}_q^\times$ and every variable to finally get $$P = \left(\prod_i (x_i^{q-1} - 1)\right)Q + R$$ where $R \in I$, $\deg P \geq \deg R$ and $Q \neq 0$. Therefore, $\deg P \geq n(q-1)\deg Q \geq n(q-1)$.

Proof 7 Use the Alon-F\"uredi theorem to show that for every polynomial $P$ of degree less than $n(q-1)$ there are at least two points where $P$ does not vanish.

Proof 8 Use the coefficient formula which says that if a polynomial $P \in \mathbb{F}[x_1, \dots, x_n]$ has degree at most $c_1 + \cdots + c_n$ for some positive integers $c_i$'s, then the coefficient of $\prod x_i^{c_i}$ in $P$ is equal to $$\sum_{(a_1, \dots, a_n) \in A_1 \times \cdots \times A_n} \frac{P(a_1, \dots, a_n)}{\varphi_1'(a_1)\cdots\varphi_n'(a_n)}$$ where $A_i$ is an arbitrary finite subset of $\mathbb{F}$ of cardinality $c_i + 1$ and $\varphi_i(x_i) = \prod_{\alpha \in A_i}(x_i - \alpha)$.

(I'll keep adding more proofs as I discover them)

Answer 5

The result was strengthened by Ax, which was then generalized by Katz, which was then strengthened by Cao and Sun...

These strengthenings focus on proving better p-adic congruences for the number of solutions.

Answer 6

Whether the following proof is different from the other ones already mentioned could be debated, but to me it feels different enough to be worth mentioning separately. As noted in Gjergji Zaimi's answer to another MO question, it appears in Christos Papadimitriou's paper, On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and System Sciences 48 (1994), 498–532.

Following Papadimitriou, I will give the proof in the case $\mathbb{F}_2$, since this case mostly clearly demonstrates the graph-theoretic of the proof, but the proof generalizes readily to $\mathbb{F}_p$. As mentioned in Pete Clark's answer, we note that the polynomial $$ Q(x_1,\ldots,x_n) := \prod_{i=1}^r (1 - P_i(x_1,\ldots,x_n))$$ equals 1 if and only if $(x_1,\ldots,x_n)$ is a common zero of the $P_i$. We form a bipartite graph. One part, which we call $A$, has one vertex for each of the $2^n$ possible assignments to the variables $x_1,\ldots, x_n$. The other part, which we call $B$, has one node for each monomial that appears when we fully multiply out $Q$. There is an edge between $a\in A$ and $b\in B$ if and only if the monomial corresponding to $b$ evaluates to 1 with the assignment $a$.

The crucial observation is that by the hypothesis of the theorem, each monomial in $Q$ is missing at least one variable. Therefore each node in $B$ is adjacent to an even number of nodes in $A$ (just toggle the assigned value of a missing variable). On the other hand, a node $(x_1,\ldots,x_n)$ in $A$ is adjacent to an odd number of nodes in $B$ if and only if $Q(x_1,\ldots,x_n) = 1$. So the "handshaking lemma" of graph theory tells us that the number of such nodes must be even. Q.E.D.

This connection to the handshaking lemma is more than just an amusing conceit. Notice that the proof does not yield an efficient way of finding a common zero of the $P_i$, thus illustrating the phrase "inefficient proofs of existence" in Papadimitriou's title. There are several complexity classes associated with existence proofs that do not yield a polynomial time algorithm. In the paper, On the Complexity of Modulo-$q$ Arguments and the Chevalley–Warning Theorem, the authors show that the search problem associated with the Chevalley–Warning theorem is complete for a complexity class called $\mathsf{PPA}_p$, and argue that it is the most natural known complete problem for that class.

Answer 7

It is worth to mention that in his original paper, E. Warning also finds a lower bound for the number of solutions:

Satz 3. Wenn das Polynom $f(X)$ (mit $g < n$) überhaupt eine Nullstelle hat, so ist die Anzahl aller (verschiedenen) Nullstellen von $f(X)$ mindestens $q^{n - g}$.

Apart from the references provided in other answers here, an excellent survey about Chevalley–Warning theorem, its history and applications and related problems about solving polynomial equations over finite fields, written by Jean-René Joly, is accessible from

Équations et variétés algébriques sur un corps fini (L'Enseignement Mathématique (1973))