Proof of the Chevalley-Warning Theorem

The Chevalley-Warning theorem is a fundamental result in algebra with powerful combinatorial applications. It guarantees that systems of polynomial equations over finite fields with "few" variables have solutions, and that the number of solutions is divisible by the characteristic.

Statement

Theorem6.5Chevalley-Warning Theorem

Let $\mathbb{F}_q$ be a finite field of characteristic $p$ , and let $f_1, \ldots, f_m \in \mathbb{F}_q[x_1, \ldots, x_n]$ be polynomials with $\sum_{i=1}^m \deg(f_i) < n$ . Then the number of common zeros $N = |\{x \in \mathbb{F}_q^n : f_1(x) = \cdots = f_m(x) = 0\}|$ satisfies $N \equiv 0 \pmod{p}$ . In particular, if the system has the trivial solution $x = 0$ , it must have at least $p - 1$ other solutions.

Proof

We use the identity: for any $a \in \mathbb{F}_q$ , $1 - a^{q-1} = \begin{cases} 1 & \text{if } a = 0, \\ 0 & \text{if } a \neq 0. \end{cases}$

Define $g(x) = \prod_{i=1}^m (1 - f_i(x)^{q-1})$ . Then $g(x) = 1$ if $x$ is a common zero of $f_1, \ldots, f_m$ , and $g(x) = 0$ otherwise. Therefore: $N = \sum_{x \in \mathbb{F}_q^n} g(x) = \sum_{x \in \mathbb{F}_q^n} \prod_{i=1}^m (1 - f_i(x)^{q-1}).$

The degree of $g$ is at most $(q-1) \sum_{i=1}^m \deg(f_i) < (q-1)n$ .

Key lemma: For any monomial $x_1^{a_1} \cdots x_n^{a_n}$ with $\deg = a_1 + \cdots + a_n < (q-1)n$ : $\sum_{x \in \mathbb{F}_q^n} x_1^{a_1} \cdots x_n^{a_n} = 0 \text{ in } \mathbb{F}_q.$

This holds because if some $a_j < q - 1$ , then $\sum_{t \in \mathbb{F}_q} t^{a_j} = 0$ (since the sum is over all elements of $\mathbb{F}_q^*$ and $a_j$ is not a multiple of $q - 1$ ), and the full sum factors.

Since $\deg(g) < (q-1)n$ , every monomial of $g$ has degree less than $(q-1)n$ , so $\sum_{x \in \mathbb{F}_q^n} g(x) = 0$ in $\mathbb{F}_q$ . This means $N \equiv 0 \pmod{p}$ . $\square$

■

Combinatorial Applications

ExampleErdos-Ginzburg-Ziv Theorem

Among any $2n - 1$ integers, there exist $n$ whose sum is divisible by $n$ . This can be proved using Chevalley-Warning when $n = p$ is prime: consider $f(x_1, \ldots, x_{2p-1}) = \sum x_i$ and $g(x_1, \ldots, x_{2p-1}) = \sum x_i^{p-1}$ over $\mathbb{F}_p$ , where the $x_i$ are $0/1$ indicators.

RemarkStrengthenings

Ax's theorem strengthens Chevalley-Warning: with the same hypotheses, $N \equiv 0 \pmod{q}$ (not just $\pmod{p}$ ). This has further applications to coding theory, particularly to the weight distribution of Reed-Muller codes.

ExampleZero-Sum Sets

Let $A_1, \ldots, A_n$ be subsets of $\mathbb{F}_p$ each of size at least 2. Then there exist $a_i \in A_i$ not all zero with $a_1 + \cdots + a_n = 0$ . This follows from Chevalley-Warning applied to $f = x_1 + \cdots + x_n$ and $g_i = \prod_{a \notin A_i}(x_i - a)$ , where $\sum \deg \leq 1 + \sum(p - |A_i|) \leq 1 + n(p - 2) < n(p-1)$ for large enough $n$ .