Combinatorial Nullstellensatz

A powerful algebraic tool in combinatorics. Proof below could be found elsewhere.

We say a polynomial $f$ in $n$ variables $x_1,\dots,x_n$ over field $F$ has a leading term $x_1^{d_1}\dots x_n^{d_n}$ if $[x_1^{d_1}\dots x_n^{d_n}]f\ne0$ and $\deg f=d_1+\dots+d_n$.

Combinatorial Nullstellensatz

If $f$ has a leading term $x_1^{d_1}\dots x_n^{d_n}$ and

for every $i\in[n]$, $S_i\subseteq F$ has size $d_i+1$, then there exists $$t=(t_1,\ldots,t_n)\in S\equiv\prod_{i\in[n]}S_i$$ s.t. $f(t)\ne0$.

Proof:

Suppose that $f(t)=0,\forall t\in S$. We prove by induction on $n$ that $x_1^{d_1}\dots x_n^{d_n}$ is not a leading term of $f$. 

For $n=1$ this is trivial. For $n>1$, we write $$f(x_1,\ldots,x_n)=g_1(x_1,\ldots,x_n)\prod_{s_{1,i}\in S_1}(x_1-s_{1,i})+p_{d_1}(x_2,\ldots,x_n)x_1^{d_1}+\ldots+p_1(x_2,\ldots,x_n)x_1+p_0(x_2,\ldots,x_n).$$

The second part of $f$ vanishes for $d_1+1$ distinct values of $x_1$ while $x_2,\dots,x_n$ are fixed, so $p_{d_1}$, and others that are not importnat, are $0$ for every $$(x_2,\dots,x_n)\in\prod_{2\le i\le n}S_i.$$

By inductive hypothesis, $x_2^{d_2}\dots x_n^{d_n}$ is not a leading term of $p_{d_1}$ and:

(i) If $\deg p_{d_1}>d_2+\dots+d_n$, then $\deg f>d_1+\dots+d_n.$

(ii) If $[x_2^{d_2}\dots x_n^{d_n}]p_{d_1}=0$, then $x_1^{d_1}\dots x_n^{d_n}$ can only come from the first part of $f$, which meanwhile also provides a nonzero term $x_1^{d_1+1}x_2^{d_2}\dots x_n^{d_n}$ not to be eliminated anywhere in $f$.

In any case, $f$ does not have a leading term $x_1^{d_1}\dots x_n^{d_n}$.