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!
 A: 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:

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
\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.
