Combinatorial Nullstellensatz

Remarks

The result and its name are due to Alon. For part 1, reduce $f$ by replacing each power $x_i^{e}$ with $e \ge \abs{S_i}$ using $g_i(x_i) = 0$; the remainder has degree less than $\abs{S_i}$ in each $x_i$ and still vanishes on $S_1 \times \dots \times S_n$. A polynomial of that kind which vanishes on the whole grid is zero. This follows by induction on $n$, since a nonzero polynomial in one variable of degree $d$ has at most $d$ roots. Part 2 follows from part 1. If $f$ vanished on the grid, then $f = \sum_i h_i g_i$ with the stated degree bounds. Every monomial of top degree in $h_i g_i$ has $x_i$-degree at least $\abs{S_i} > t_i$, so $x_1^{t_1} \cdots x_n^{t_n}$ could not appear in $f$.

The size condition is needed: for $n = 1$, $f = x_1(x_1 - 1)$, $t_1 = 2$ and $S_1 = \set{0, 1}$, we have $\abs{S_1} = t_1$ and $f$ vanishes on $S_1$.

Example: the Cauchy–Davenport theorem follows from part 2. For a prime $p$ and nonempty $A, B \subseteq \Z/p\Z$ with $\abs{A} + \abs{B} - 1 \le p$, suppose the sumset $A + B$ lies in a set $C$ of size $\abs{A} + \abs{B} - 2$. Apply part 2 to $f(x, y) = \prod_{c \in C} (x + y - c)$ with $t_1 = \abs{A} - 1$ and $t_2 = \abs{B} - 1$: the coefficient of $x^{t_1} y^{t_2}$ is $\binom{t_1 + t_2}{t_1}$, which is nonzero modulo $p$, yet $f$ vanishes on $A \times B$, a contradiction.

Going deeper

For a student

The method is to encode a combinatorial property as the vanishing of a polynomial on a grid, then exhibit a nonzero top coefficient. It gives short proofs of results in additive number theory, such as Cauchy–Davenport, and of results on graph colouring and on hyperplane coverings of the cube. It is a sharp version, for grids, of the fact that a nonzero polynomial cannot vanish everywhere on $F^n$ when $F$ is infinite.