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 \begin{equation} 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} \end{equation} 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 \begin{equation} 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) . \end{equation} 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:
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 \begin{equation} \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) \end{equation} is divisible by $\prod_{a\in\Omega}\left( x_{f\left( a\right) }-a_{f\left( a\right) }\right) $). This proves Claim 1.