Combinatorial Nullstellensatz

The theorem of Combinatorial Nullstellensatz is an extremely powerful statement regarding the points where a multivariate polynomial is allowed to vanish. This is useful in combinatorics as for example one may have a property holds over a large set of objects, which can be modeled by a polynomial equalling zero. Before we discuss this theorem, we need to build some machinery up first.

Note that if $P(x) = a_nx^n + ... + a_0 \in \mathbb{C}[x]$ (i.e. $P$ is a polynomial with complex coefficients), then it has at most $n$ zeros if $P \neq 0$. An alternative phrasing of this is if $S \subseteq \mathbb{C}$ and $|S| > n$ then $P$ cannot vanish on every point in $S$. More generally, we have the following statement regarding multivariate polynomials:

Theorem 1: Let $P$ be a polynomial with complex coefficents in terms of $x_1, ..., x_n$. Assume that $\deg x_j(P) = t_j$ and let $S_1, S_2, ..., S_n \subseteq \mathbb{C}$ with $|S_j| \ge t_j + 1$. Then if $P$ is nonzero, then $P$ cannot vanish on $S_1 \times ... \times S_n$.

Let's digest this statement first. By $\deg x_j(P) = t_j$ we mean the highest degree of $x_j$ which appears in $P$ is $t_j$. Then we are simply generalizing our previous statement by taking a set for each variable. What does it mean for $P$ to vanish on $S_1 \times ... \times S_n$ though? This simply means if we pick any $s_1 \in S_1, ..., s_n \in S_n$, then $P(s_1, ..., s_n) = 0$.

This is not a very good generalization, as it is very difficult to use. To prove this is a fairly straightforward application of induction and proof by contradiction and not terribly relevant to the topic at hand. There is a stronger generalization by Noga Alon named the Combinatorial Nullstellensatz:

Theorem 2: Let $P = \sum c_{i_1,...,i_n} x_1^{i_1}...x_n^{i_n}$. Let $\deg P = t_1 + t_2 + ... + t_n$ for some set of $t_i$ such that $c_{t_1...t_n} \neq 0$. Assume that $S_1, ..., S_n \subseteq \mathbb{C}$ such that $|S_i| \ge t_i + 1$. Then $P$ vanishes on some element of $S_1 \times ... \times S_n$.

Let's think about why this statement is more general. Note that this only requires one coefficient to be nonzero for the result to apply, while our previous theorem required the highest degree of $x_i$ to be very specific numbers. So for example if we had $P(x) = x_2^3 + x_3^3 + x_1x_2x_3$, Theorem 2 could be used to show $P$ does not vanish in a $2 \times 2 \times 2$ cube while Theorem 1 can not unless we add an $x_1^3$ term. So in some sense, Theorem 1 requires the presence of many more nonzero coefficients for the same result.

In my experience, this theorem looks extremely scary to those new to the subject due to the heavy notation required to describe it. Fortunately, with lots of practice the statement becomes very natural. After doing a few practice problems it becomes clearer in what situations this can be applied and how to set-up your polynomials, making it an extremely useful tool for solving future problems.

Here is a fairly short proof of this result. To prove this theorem, first we need a result related to Hilbert's Nullstellensatz, but we will prove a weaker analogue of it which suffices for Combinatorial Nullstellensatz.

Theorem 3: Let $f \in \mathbb{C}[x_1, ..., x_n]$ (a polynomial with complex coefficients in terms of $x_1, ..., x_n$). Denote $g_i(x_i) = \prod_{t \in S_i} (x_i - t)$ for some sets $S_1, ..., S_n \subseteq \mathbb{C}$. Assume that $f$ vanishes on $S_1 \times ... \times S_n$. Then there exist $h_i$ with $\deg h_i \le \deg f - \deg g_i$ such that:

$$f = \sum_{i=1}^n g_ih_i$$

To prove this, let $f = \sum c_{i_1,...,i_n} x_1^{i_1}...x_n^{i_n}$. Assume that for some $m \ge |S_i|$ we have a term of $x_i^m$. Then: $$g_i(x_i) = \prod_{t \in S_i} (x_i - t) = x^{|S_i|} - \sum_{j \le |S_i|} q_{ij}x_i^j$$ where $q_{ij}$ are some various coefficients. Clearly $g_i$ vanishes on $S_1 \times ... \times S_n$, so by subtracting appropriate multiples of $g_i$ from $f$ we can kill off any terms with exponents of $x_i$ which are $|S_i|$ or greater by performing polynomial long division without disturbing the fact that $f$ vanishes on $S_1 \times ... \times S_n$. Then by using an inductive argument, we can continue this process until the degree of $x_i$ of $f$ is at most $|S_i| - 1$ for all $i$. It follows by the crude generalization above that $f$ is zero once this degree condition is established so we are done.

Equipped with this, we can now prove the main result:

Proof of Theorem 2: Assume that $P$ vanishes on $S_1 \times ... \times S_n$. Then by the above, we can write $P$ as:

$$P = \sum_{i=1}^n g_ih_i$$

where $g_i, h_i$ follow the conditions of the above theorem. Note that in any $g_ih_i$, we have the coefficient of $x_1^{t_1}...x_{n}^{t_n}$ is always $0$ due to $|S_i| > t_i$, so we have a contradiction. Therefore we are done.

This finishes up the proof. For those with a little algebra knowledge, it is not hard to see the above proof generalizes to arbitrary fields (so for example the integers modulo $p$, which is why this is applicable to the Cauchy-Davenport Theorem).

(EGZ Theorem) Let $n$ be a positive integer. Prove that among $2n-1$ integers, we can find $n$ of them whose sum is divisible by $n$.

Let $p$ be a prime. Consider a $p \times p$ grid of points labelled $(x,y)$ for $0 \le x,y \le p-1$. Consider the $p^2 + p$ ``lines'' which are sets of points of the form $x=c$ for some $c$ or $y \equiv ax + b \pmod{p}$ for some $a,b$. So for example when $p=2$, the lines are $y=0, y=1, x=1, x=2, x=y$ and $y = 1-x$. Let $A$ be a set of points which contains at least one point on every line. Show that $A$ has at least $2p - 1$ elements.

(2007 IMO Problem 6) Let $n$ be a positive integer. Consider $$S = \left\{ (x,y,z) \mid x,y,z \in \{ 0, 1, \ldots, n\}, x + y +z > 0 \right \}$$ as a set of $(n + 1)^{3} - 1$ points in the three-dimensional space. Determine the smallest possible number of planes, the union of which contains $S$ but does not include $(0,0,0)$.