Solutions that come in multiples of p

In the integers modulo 5, the equation $x^2 + y^2 + z^2 = 0$ has 25 solutions among the 125 triples. Modulo 7 it has 49 of 343, modulo 11 it has 121, modulo 13 it has 169. Every time the count is a multiple of the prime — in fact the square of it — and one of the solutions is always $(0, 0, 0)$.

That the count is a multiple of the prime is not a coincidence of this equation. Whenever a system of polynomial equations over a finite field has more variables than the sum of its degrees, the number of its solutions is divisible by the field’s characteristic. Chevalley and Warning proved it in 1935. The consequence that gets used is the one the figure makes plain: a count divisible by 5 that includes the solution at zero cannot be 1, so there is another.

The proof is short, and it turns on a single fact about finite fields that the essay on every element being a power of one of them supplies.

A count that has to be a multiple #

The statement is worth having exactly. Take a finite field with $q$ elements, of characteristic $p$, and polynomials $f_1, \dots, f_r$ in $n$ variables with coefficients in the field. If the degrees add to less than $n$, then the number of points of $F^n$ at which every $f_i$ vanishes is a multiple of $p$.

For one quadratic in three variables the degrees add to 2 and there are 3 variables, so the theorem applies; the count 25 is a multiple of 5. For $x^3 + y^3 + z^3 + w^3$, a cubic in four variables, the counts modulo 3, 5, 7, 11 and 13 are 27, 125, 595, 1331 and 3133, and each divides by its prime. For one quadratic in two variables the degrees add to 2 and there are 2 variables, so the theorem says nothing, and the figure’s second panel shows why it has to say nothing.

The theorem was the answer to a question of Artin’s. He had conjectured that a finite field is quasi-algebraically closed: any polynomial with no constant term, in more variables than its degree, has a zero other than the obvious one. Chevalley proved it, and Warning in the same year strengthened it to the statement about counts. The counting version is the more useful, because a count carries information a bare existence statement does not.

The sum that vanishes #

The one fact needed is a sum over all the elements of the field.

Add up $x^k$ as $x$ runs over every element of a field with $q$ elements. At $k = 0$ every term is 1 and there are $q$ of them, and $q$ is zero in a field of characteristic $p$. For larger $k$ the zero element contributes nothing, and the rest are the powers $g^0, g^1, \dots, g^{q-2}$ of a primitive element $g$. Their $k$-th powers are $1, g^k, g^{2k}, \dots$, a geometric series in $g^k$.

If $g^k$ is not 1, that series is $(g^{k(q-1)} - 1)/(g^k - 1)$, and $g^{k(q-1)}$ is 1, so the sum is 0. If $g^k$ is 1 — exactly when $q - 1$ divides $k$ — every term is 1, there are $q - 1$ of them, and $q - 1$ is $-1$. So summing a power over the whole field gives nothing unless the power is a positive multiple of $q - 1$.

It is the same vanishing that makes the corners of a regular polygon add to nothing, and the same geometric series, carried out inside a finite field instead of the complex plane. The roots-of-unity filter used that vanishing to pick out coefficients; here it will pick out solutions.

Turning an equation into a sum #

The second ingredient converts a question about solutions into a question about a sum.

For any element $z$ of the field, $z^{q-1}$ is 1 if $z$ is non-zero and 0 if $z$ is zero — Fermat’s little theorem, in the form every finite field satisfies. So $1 - f(x)^{q-1}$ is 1 at the points where $f$ vanishes and 0 everywhere else. It is an indicator, written as a polynomial.

Adding the indicator over every point of $F^n$ counts the solutions — not as a whole number, but as that whole number reduced into the field, which is to say modulo $p$. For several equations the product of the indicators, $\prod_i (1 - f_i^{\,q-1})$, is 1 exactly at the common solutions. So the number of solutions, modulo $p$, is the sum over every point of a single polynomial.

That polynomial has degree $(q - 1)$ times the sum of the degrees of the $f_i$, and that number is the whole of the argument.

Why the degree has to be small #

Expand the indicator into monomials $x_1^{e_1} x_2^{e_2} \cdots x_n^{e_n}$. Summing a monomial over every point of $F^n$ splits into a product: the sum of $x_1^{e_1}$ over the field, times the sum of $x_2^{e_2}$, and so on. By the vanishing sum, that product is zero unless every exponent $e_i$ is a positive multiple of $q - 1$.

A monomial whose exponents are all positive multiples of $q - 1$ has degree at least $n(q - 1)$. The indicator’s degree is $(q - 1)$ times the sum of the degrees, and that sum is less than $n$, so the indicator’s degree is less than $n(q - 1)$. No monomial in it can have every exponent large enough to survive, every monomial sums to zero, and so the number of solutions is zero modulo $p$.

For $x^2 + y^2 + z^2$ over the field with three elements, the indicator is $1 - x^4 - y^4 - z^4 + x^2y^2 + x^2z^2 + y^2z^2$. Its degree is 4, less than $3 \times 2$, and every one of its seven monomials leaves some variable out entirely — raised to the power 0, whose sum over the field is $3$, which is $0$. The equation has 9 solutions, and 9 is a multiple of 3.

Where it stops #

The figure’s second panel is the edge of the theorem. The equation $x^2 + y^2 = 0$ over the integers modulo 7 has two variables and degree two, so the indicator has degree $2 \times 6 = 12$, which is exactly $n(q-1)$, and the monomial $x^6y^6$ is allowed to survive. It does, and the count comes out as 1: only $(0, 0)$.

The reason is arithmetic, and it is a fact met elsewhere. A non-zero solution would make $x^2 = -y^2$, so $-1$ would be the square $(x/y)^2$, and modulo 7 it is not: the squares are 1, 2 and 4. Modulo a prime, $-1$ is a square exactly when the prime is one more than a multiple of four — a fact proved by counting, as so much here is — which is the same condition that decides whether the prime is a sum of two squares. Modulo 5 or 13 the equation has $2p - 1$ solutions, 9 and 25, and modulo 3, 7 or 11 it has 1.

So the hypothesis is sharp. With as many variables as the degree, some fields admit only the trivial solution, and the count, 1, is not a multiple of anything. One variable fewer than needed is enough to lose the theorem entirely.

A consequence that follows on the other side of the edge is worth stating. Every quadratic form in three or more variables over a finite field has a non-zero solution, whatever its coefficients. Over the real numbers $x^2 + y^2 + z^2$ vanishes only at the origin, and over the rational numbers so do many forms. Over a finite field no form in three variables can avoid zero, because its solutions come in multiples of $p$ and zero is one of them.

One solution, and a line through it finds the rest #

Chevalley and Warning say the count is a multiple of $p$. For a quadratic form in three variables the figure shows more — exactly $p^2$ — and the reason is a construction that the divisibility makes possible.

Treat the solutions up to scaling. If $(x, y, z)$ is a non-zero solution then so is every multiple of it, and the $p - 1$ non-zero multiples are the same point of the projective plane over the field. So the non-zero solutions of $x^2 + y^2 + z^2 = 0$ fall into groups of $p - 1$, and each group is a point of a conic drawn in the finite projective plane.

Chevalley’s theorem supplies one such point. The rest are found the way every Pythagorean triple is found from one point of the circle: draw every line through the known point. A line meets a conic in two points, one of which is the point already known, so each line through it picks up exactly one more — except the tangent line, which touches only there. The plane over a field with $p$ elements has $p + 1$ lines through any point, so the conic has exactly $p + 1$ points.

That gives the count exactly. Each of the $p + 1$ points is $p - 1$ non-zero solutions, and the zero solution is one more, so the total is $(p + 1)(p - 1) + 1 = p^2$ — 25 when $p = 5$, 49 when $p = 7$. The divisibility found one point, and the geometry of lines found all the others, which is a division of labour worth recognising: counting modulo $p$ is often the only way to show that a first solution exists, and once one exists, a construction usually counts the rest exactly.

More than one factor of p #

Chevalley and Warning promise one factor of $p$. Sometimes the counts carry more.

Counting every tuple, the sums of squares show a pattern Warning’s argument does not explain. A sum of four squares is divisible by $p$ and no more — 33 is $3 \times 11$. A sum of six squares is divisible by $p^2$ at every prime drawn: $225 = 9 \times 25$, $3225 = 25 \times 129$, $16513 = 49 \times 337$.

Ax proved in 1964, and Katz sharpened it for systems in 1971, that the number of solutions is divisible not just by $p$ but by $q^{b}$, where $b = \lceil n/d \rceil - 1$ for a single equation of degree $d$ in $n$ variables. For quadratics that is $\lceil n/2 \rceil - 1$: one factor for three or four variables, two factors for five or six. The sums of six squares meet that exactly, which shows the Ax–Katz bound cannot be improved in general. The sums of five squares, which are divisible by $p^4$, show that a particular equation can do better still.

Asking how many times $p$ divides a count, rather than whether it does, is a different kind of question, and it has a precedent that needs no field at all: how many times a prime divides a binomial coefficient is the number of carries in an addition written in base $p$. Ax’s theorem is a counting of factors of $p$ of the same exact kind, applied to a count of solutions instead of a count of subsets.

The proof is harder than Chevalley and Warning’s. It needs sums over the field weighted by characters rather than plain sums of powers, and a careful count of how many factors of $p$ each such sum carries; the elementary argument above sees only whether a sum is zero, not how divisible it is.

Five numbers out of any nine #

The theorem’s best-known use has no field in its statement at all.

Among any nine whole numbers, some five have a sum divisible by five. Eight numbers are not enough: four that leave remainder 0 and four that leave remainder 1 contain no five with a sum divisible by five, since any five of them sum to between one and four. That is the Erdős–Ginzburg–Ziv theorem of 1961, and it holds for every $n$ in the form “among any $2n - 1$ numbers, some $n$ have a sum divisible by $n$”.

For a prime $n = p$ it is Chevalley–Warning applied to two polynomials in $2p - 1$ variables over the integers modulo $p$:

$$\sum_{i} a_i\, x_i^{\,p-1} = 0, \qquad \sum_{i} x_i^{\,p-1} = 0.$$

Each has degree $p - 1$, so their degrees add to $2p - 2$, less than the $2p - 1$ variables. The all-zero point is a common solution, so there is another. In it, $x_i^{\,p-1}$ is 1 for the non-zero $x_i$ and 0 for the rest, so the second equation says the number of non-zero $x_i$ is a multiple of $p$ — and since there are at most $2p - 1$ of them and at least one, exactly $p$. The first equation then says the $a_i$ at those $p$ positions add to a multiple of $p$. The equations had no subsets in them; the subset appears as the set of variables a solution does not set to zero.

The general case follows from the prime case, and the step is a small counting argument of its own. Suppose the statement holds for $a$ and for $b$, and take $2ab - 1$ numbers. As long as at least $2b - 1$ numbers remain, some $b$ of them have a sum divisible by $b$; remove them and repeat. After $2a - 2$ removals, $2ab - 1 - (2a - 2)b = 2b - 1$ numbers are still left, so a removal is possible $2a - 1$ times in all. Each removed group’s sum is $b$ times a whole number, and among those $2a - 1$ whole numbers some $a$ add to a multiple of $a$. Those $a$ groups hold $ab$ numbers, and their sum is $b$ times a multiple of $a$.

So the theorem for every $n$ comes down to the theorem for primes, and for primes it comes down to a sum over a finite field. The search in the figure checks the whole statement for $n = 3$ and $n = 5$ without any of that argument, by trying every collection, and it shows the bound of $2n - 1$ cannot be lowered: with one number fewer, more numbers than remainders no longer forces anything, and collections that avoid every sum divisible by $n$ appear at once.

What the counts cannot show #

Every field drawn is small. The zeros are listed over fields of three to eleven elements, and the Ax–Katz table stops at six variables and the prime 7. The theorem is about every finite field and every system satisfying the degree condition; the tables are evidence that the statement and its sharpness are as claimed, not a proof of either.

The indicator is expanded only over the field with three elements. Over larger fields the same polynomial has dozens of monomials, and the argument that each of them sums to zero is the one given in words above, not one drawn.

And the theorem says how many solutions there are modulo $p$, not how many there are. It forces 25 over five elements to be a multiple of 5; it does not say 25 rather than 5 or 120. That the count is exactly $p^2$ for a non-degenerate quadratic form in three variables is a separate and more precise theorem, and precise counts are a subject of their own.

The question it leaves: how many solutions, not only how many modulo p #

Chevalley and Warning decide a count up to multiples of $p$, which settles existence and says nothing about size. For an equation in two variables with the degree too large for their theorem, the natural expectation is a count close to $p$ — one solution for every value of $x$, on average — and the interesting question is how far a real count can stray from that.

For the cubic curves $y^2 = x^3 + ax + b$ the answer is exact and old: never by more than twice the square root of $p$, a bound Hasse proved in 1933, with every count the bound allows achieved by some curve. That is where counting modulo $p$ gives way to counting.

A divisibility that comes from a vanishing sum #

The theorem looks like number theory and its engine is the structure of a finite field. The non-zero elements form one cycle, so powers summed over the whole field vanish unless they complete the cycle; an equation becomes an indicator polynomial by Fermat’s theorem; and a polynomial of low enough degree cannot contain a monomial that survives the sum.

When a count needs to be shown divisible, try writing it as a sum of a polynomial over a structure whose power sums vanish — the count modulo the characteristic is then read off from the degree, without finding a single solution.