Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 161 / 3

The coefficient form of the Combinatorial Nullstellensatz is the following. Let $f\in F[x_1,\dots ,x_n]$ have total degree at most $d_1+\cdots +d_n$, and supposeFor 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)\ne 0$.

For the proof, defineSuccessive Lagrange interpolation in the variables gives the Alon-Tarsi lemmaEvery 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.

Consider the degree-$n$ polynomialTo form the square-free monomial $x_1\cdots x_n$, one must choose each variable exactly once from the $n$ factors. Such choices are indexed by permutations, soThis coefficient is nonzero by hypothesis. Apply the Combinatorial Nullstellensatz with every $d_i=1$ and the given two-element sets $S_i$. It supplies $x\in {\prod }_i{S}_i$ with $f(x)\ne 0$. Every factor is then nonzero, sofor all $i$. This is coordinate avoidance from a nonzero permanent.