= Solution
The coefficient form of the <Combinatorial Nullstellensatz> is the following. Let $f\in F[x_1,\ldots,x_n]$ have total degree at most $d_1+\cdots+d_n$, and suppose
$$
[x_1^{d_1}\cdots x_n^{d_n}]f\ne0.
$$
For arbitrary subsets $S_i\subseteq F$ with $|S_i|=d_i+1$, there is an $x\in S_1\times\cdots\times S_n$ such that $f(x)\ne0$.
For the proof, define
$$
\phi_i'(a)=\prod_{b\in S_i\setminus\{a\}}(a-b).
$$
Successive <Lagrange interpolation polynomial>[Lagrange interpolation] in the variables gives the <Alon-Tarsi lemma>
$$
[x_1^{d_1}\cdots x_n^{d_n}]f
=\sum_{a_i\in S_i}
\frac{f(a_1,\ldots,a_n)}{\prod_i\phi_i'(a_i)}.
$$
Every denominator is nonzero because the elements of $S_i$ are distinct. If $f$ vanished throughout the product grid, the right side and hence the assumed nonzero coefficient would vanish. This contradiction proves the theorem.
Back to article page
