Vishnoi's Proof of Combinatorial Nullstellensatz

The question was already asked here: Question regarding a proof of the Combinatorial Nullstellensatz, but I am having trouble understanding the document in the comment, and so I was wondering if someone could actually explain the line in Vishnoi's proof of Combinatorial Nullstellensatz where he says: "It is easy to see, as in the expansion of $$h$$, each term must be of the type $$qg_i$$." .

Many thanks!

If $$m\in\mathbb{N}$$, then I will use the notation $$\left[ m\right]$$ for the $$m$$-element set $$\left\{ 1,2,\ldots,m\right\}$$.

Vishnoi has several confusing points in his proof; I wish someone would rewrite it in a more readable way. For example, when he says "there exists $$P_{1},P_{2}\in k\left[ x_{1},x_{2},\ldots,x_{n}\right]$$ such that $$P_{1}f+P_{2}M_{a}=1$$. Then $$\left( P_{1}f+P_{2}M_{a}\right) \left( a_{1},\cdots,a_{n}\right) =0\neq1$$", he means to say "there exist $$P_{1}\in k\left[ x_{1},x_{2},\ldots,x_{n}\right]$$ and $$P_{2}\in M_{a}$$ such that $$P_{1}f+P_2 =1$$. Then $$\left( P_{1}f+P_{2}\right) \left( a_{1} ,\cdots,a_{n}\right) =0\neq1$$". Another pitfall is the notation "$$p_{1}\left( x_{1}-a_{1}\right)$$", which means the product $$p_{1} \cdot\left( x_{1}-a_{1}\right)$$ whereas the similar-looking notation "$$g_{i}\left( x_{i}\right)$$" means the polynomial $$g_{i}$$ evaluated at $$x_{i}$$. I shall resolve this ambiguity by never omitting the $$\cdot$$ sign in products.

Now, what does Vishnoi mean by "the expansion of $$h$$" ? He writes $$h=\prod_{a\in\Omega}h_{a}$$, where $$h_{a}$$ is a polynomial of the form $$$$h_{a}=p_{1}\cdot\left( x_{1}-a_{1}\right) +p_{2}\cdot\left( x_{2} -a_{2}\right) +\cdots+p_{n}\cdot\left( x_{n}-a_{n}\right) \label{darij.eq.1} \tag{1}$$$$ for each $$a\in\Omega$$. Note, however, that the $$p_{1},p_{2},\ldots,p_{n}$$ depend on $$a$$, so that I shall denote them by $$p_{a,1},p_{a,2},\ldots,p_{a,n}$$ instead. Thus, \eqref{darij.eq.1} rewrites as $$$$h_{a}=p_{a,1}\cdot\left( x_{1}-a_{1}\right) +p_{a,2}\cdot\left( x_{2} -a_{2}\right) +\cdots+p_{a,n}\cdot\left( x_{n}-a_{n}\right) .$$$$ Multiplying these equalities over all $$a\in\Omega$$, we obtain \begin{align*} \prod_{a\in\Omega}h_{a} & =\prod_{a\in\Omega}\left( p_{a,1}\cdot\left( x_{1}-a_{1}\right) +p_{a,2}\cdot\left( x_{2}-a_{2}\right) +\cdots +p_{a,n}\cdot\left( x_{n}-a_{n}\right) \right) \\ & =\sum_{f:\Omega\rightarrow\left[ n\right] }\prod_{a\in\Omega}\left( p_{a,f\left( a\right) }\cdot\left( x_{f\left( a\right) }-a_{f\left( a\right) }\right) \right) \end{align*} (by the product rule). This is what Vishnoi means by "the expansion of $$h$$". Thus, his claim is that for each map $$f:\Omega\rightarrow\left[ n\right]$$, the term $$\prod_{a\in\Omega}\left( p_{a,f\left( a\right) }\cdot\left( x_{f\left( a\right) }-a_{f\left( a\right) }\right) \right)$$ is of type $$qg_{i}\left( x_{i}\right)$$ for some $$i\in\left[ n\right]$$ and some $$q\in k\left[ x_{1},x_{2},\ldots,x_{n}\right]$$. In other words, his claim is the following:

Claim 1. For each map $$f:\Omega\rightarrow\left[ n\right]$$, there exists some $$i \in \left[n\right]$$ such that the polynomial $$\prod_{a\in\Omega}\left( p_{a,f\left( a\right) }\cdot\left( x_{f\left( a\right) }-a_{f\left( a\right) }\right) \right)$$ is divisible by $$g_{i}\left( x_{i}\right)$$.

Let us prove this. Indeed, let $$f:\Omega\rightarrow\left[ n\right]$$ be a map. Given any $$i\in\left[ n\right]$$ and $$s\in S_{i}$$, we say that $$s$$ is $$i$$-breaking if there exists no $$a\in\Omega$$ satisfying $$f\left( a\right) =i$$ and $$a_{i}=s$$.

We claim that there exists some $$i\in\left[ n\right]$$ such that there exists no $$i$$-breaking $$s\in S_{i}$$.

[Proof: Assume the contrary. Thus, for each $$i\in\left[ n\right]$$, there exists some $$i$$-breaking $$s\in S_{i}$$. Fix such an $$s$$, and denote it by $$s^{\left( i\right) }$$.

Thus, $$s^{\left( i\right) }\in S_{i}$$ for each $$i\in\left[ n\right]$$. Hence, $$\left( s^{\left( 1\right) },s^{\left( 2\right) },\ldots ,s^{\left( n\right) }\right) \in S_{1}\times S_{2}\times\cdots\times S_{n}=\Omega$$. Thus, define $$b\in\Omega$$ by $$b=\left( s^{\left( 1\right) },s^{\left( 2\right) },\ldots,s^{\left( n\right) }\right)$$. Hence, $$b_{i}=s^{\left( i\right) }$$ for each $$i\in\left[ n\right]$$.

Now, let $$j=f\left( b\right) \in\left[ n\right]$$. Hence, $$f\left( b\right) =j$$ and $$b_{j}=s^{\left( j\right) }$$ (since $$b_{i}=s^{\left( i\right) }$$ for each $$i\in\left[ n\right]$$). Thus, there exists an $$a\in\Omega$$ satisfying $$f\left( a\right) =j$$ and $$a_{j}=s^{\left( j\right) }$$ (namely, $$a=b$$).

Observe that $$s^{\left( j\right) }\in S_{j}$$ is $$j$$-breaking (since $$s^{\left( i\right) }\in S_{i}$$ is $$i$$-breaking for each $$i\in\left[ n\right]$$). In other words, there exists no $$a\in\Omega$$ satisfying $$f\left( a\right) =j$$ and $$a_{j}=s^{\left( j\right) }$$ (by the definition of "$$j$$-breaking"). But this contradicts the fact that there exists an $$a\in\Omega$$ satisfying $$f\left( a\right) =j$$ and $$a_{j}=s^{\left( j\right) }$$. This contradiction shows that our assumption was wrong, qed.]

We thus have shown that there exists some $$i\in\left[ n\right]$$ such that there exists no $$i$$-breaking $$s\in S_{i}$$. Consider this $$i$$.

There exists no $$i$$-breaking $$s\in S_{i}$$. In other words, there exists no $$s\in S_{i}$$ such that there exists no $$a\in\Omega$$ satisfying $$f\left( a\right) =i$$ and $$a_{i}=s$$ (by the definition of "$$i$$-breaking"). In other words, for each $$s\in S_{i}$$, there exists some $$a\in\Omega$$ satisfying $$f\left( a\right) =i$$ and $$a_{i}=s$$. Fix such an $$a$$, and denote it by $$a^{\left( s\right) }$$. Thus, for each $$s\in S_{i}$$, the element $$a^{\left( s\right) }\in\Omega$$ satisfies $$f\left( a^{\left( s\right) }\right) =i$$ and $$\left( a^{\left( s\right) }\right) _{i}=s$$.

Thus, for each $$s\in S_{i}$$, the product $$\prod_{a\in\Omega}\left( x_{f\left( a\right) }-a_{f\left( a\right) }\right)$$ has the factor \begin{align*} x_{f\left( a^{\left( s\right) }\right) }-\left( a^{\left( s\right) }\right) _{f\left( a^{\left( s\right) }\right) } & =x_{i}-\left( a^{\left( s\right) }\right) _{i}\qquad\left( \text{since }f\left( a^{\left( s\right) }\right) =i\right) \\ & =x_{i}-s\qquad\left( \text{since }\left( a^{\left( s\right) }\right) _{i}=s\right) \end{align*} as one of its factors (because $$a^{\left( s\right) }\in\Omega$$). Hence, all the $$\left\vert S_{i}\right\vert$$ many factors $$x_{i}-s$$ for all $$s\in S_{i}$$ appear in the product $$\prod_{a\in\Omega}\left( x_{f\left( a\right) }-a_{f\left( a\right) }\right)$$. Therefore, the product $$\prod_{a\in \Omega}\left( x_{f\left( a\right) }-a_{f\left( a\right) }\right)$$ is divisible by the product $$\prod_{s\in S_{i}}\left( x_{i}-s\right)$$ of all these $$\left\vert S_{i}\right\vert$$ many factors (since all these factors are distinct). In other words, the product $$\prod_{a\in\Omega}\left( x_{f\left( a\right) }-a_{f\left( a\right) }\right)$$ is divisible by $$g_{i}\left( x_{i}\right)$$ (since $$g_{i}\left( x_{i}\right) =\prod_{s\in S_{i}}\left( x_{i}-s\right)$$). Therefore, the polynomial $$\prod_{a\in\Omega}\left( p_{a,f\left( a\right) }\cdot\left( x_{f\left( a\right) }-a_{f\left( a\right) }\right) \right)$$ is divisible by $$g_{i}\left( x_{i}\right)$$ as well (since $$$$\prod_{a\in\Omega}\left( p_{a,f\left( a\right) }\cdot\left( x_{f\left( a\right) }-a_{f\left( a\right) }\right) \right) =\left( \prod _{a\in\Omega}p_{a,f\left( a\right) }\right) \cdot\left( \prod_{a\in\Omega }\left( x_{f\left( a\right) }-a_{f\left( a\right) }\right) \right)$$$$ is divisible by $$\prod_{a\in\Omega}\left( x_{f\left( a\right) }-a_{f\left( a\right) }\right)$$). This proves Claim 1.

• This is a beautiful proof! Thank you very much. I am writing my undergraduate thesis on the Combinatorial Nullstellensatz, so I will include Vishnoi's proof, filling all the missing details. I will, of course, cite your answer. Thanks again! Nov 26 '18 at 21:40
• @owl: More importantly, please post your thesis somewhere once it's finished :) Nov 26 '18 at 22:44
• wesscholar.wesleyan.edu/etd_hon_theses/2246 May 26 '20 at 21:05
• @YuliaAlexandr: Thank you! (Is this the same version as mathymath.github.io/alexandr_yulia_2019_ba.pdf ?) May 26 '20 at 23:19
• Yes, it is! :-) Jun 12 '20 at 21:52