Mfrhtyj

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 $minmathbb{N}$, then I will use the notation $left[ mright] $ for the
$m$-element set $left{ 1,2,ldots,mright} $.

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 kleft[ 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) =0neq1$", he means to say "there exist $P_{1}in
kleft[ 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) =0neq1$". Another pitfall is the notation
"$p_{1}left( x_{1}-a_{1}right) $", which means the product $p_{1}
cdotleft( 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_{ainOmega}h_{a}$, where $h_{a}$ is a polynomial of the form
begin{equation}
h_{a}=p_{1}cdotleft( x_{1}-a_{1}right) +p_{2}cdotleft( x_{2}
-a_{2}right) +cdots+p_{n}cdotleft( x_{n}-a_{n}right)
label{darij.eq.1}
tag{1}
end{equation}
for each $ainOmega$. 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}cdotleft( x_{1}-a_{1}right) +p_{a,2}cdotleft( x_{2}
-a_{2}right) +cdots+p_{a,n}cdotleft( x_{n}-a_{n}right) .
end{equation}
Multiplying these equalities over all $ainOmega$, we obtain
begin{align*}
prod_{ainOmega}h_{a} & =prod_{ainOmega}left( p_{a,1}cdotleft(
x_{1}-a_{1}right) +p_{a,2}cdotleft( x_{2}-a_{2}right) +cdots
+p_{a,n}cdotleft( x_{n}-a_{n}right) right) \
& =sum_{f:Omegarightarrowleft[ nright] }prod_{ainOmega}left(
p_{a,fleft( aright) }cdotleft( x_{fleft( aright) }-a_{fleft(
aright) }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:Omegarightarrowleft[ nright] $,
the term $prod_{ainOmega}left( p_{a,fleft( aright) }cdotleft(
x_{fleft( aright) }-a_{fleft( aright) }right) right) $ is of type
$qg_{i}left( x_{i}right) $ for some $iinleft[ nright] $ and some
$qin kleft[ x_{1},x_{2},ldots,x_{n}right] $. In other words, his claim
is the following:

Claim 1. For each map $f:Omegarightarrowleft[ nright] $, there exists some $i in left[nright]$ such that the polynomial
$prod_{ainOmega}left( p_{a,fleft( aright) }cdotleft( x_{fleft(
aright) }-a_{fleft( aright) }right) right) $ is divisible by
$g_{i}left( x_{i}right) $.

Let us prove this. Indeed, let $f:Omegarightarrowleft[ nright] $ be a
map. Given any $iinleft[ nright] $ and $sin S_{i}$, we say that $s$ is
$i$-breaking if there exists no $ainOmega$ satisfying $fleft( aright)
=i$ and $a_{i}=s$.

We claim that there exists some $iinleft[ nright] $ such that there
exists no $i$-breaking $sin S_{i}$.

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

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

Now, let $j=fleft( bright) inleft[ nright] $. Hence, $fleft(
bright) =j$ and $b_{j}=s^{left( jright) }$ (since $b_{i}=s^{left(
iright) }$ for each $iinleft[ nright] $). Thus, there exists an
$ainOmega$ satisfying $fleft( aright) =j$ and $a_{j}=s^{left(
jright) }$ (namely, $a=b$).

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

We thus have shown that there exists some $iinleft[ nright] $ such that
there exists no $i$-breaking $sin S_{i}$. Consider this $i$.

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

Thus, for each $sin S_{i}$, the product $prod_{ainOmega}left(
x_{fleft( aright) }-a_{fleft( aright) }right) $ has the factor
begin{align*}
x_{fleft( a^{left( sright) }right) }-left( a^{left( sright)
}right) _{fleft( a^{left( sright) }right) } & =x_{i}-left(
a^{left( sright) }right) _{i}qquadleft( text{since }fleft(
a^{left( sright) }right) =iright) \
& =x_{i}-sqquadleft( text{since }left( a^{left( sright) }right)
_{i}=sright)
end{align*}
as one of its factors (because $a^{left( sright) }inOmega$).
Hence, all the
$leftvert S_{i}rightvert $ many factors $x_{i}-s$ for all $sin S_{i}$
appear in the product $prod_{ainOmega}left( x_{fleft( aright)
}-a_{fleft( aright) }right) $.
Therefore, the product $prod_{ain
Omega}left( x_{fleft( aright) }-a_{fleft( aright) }right) $ is
divisible by the product $prod_{sin S_{i}}left( x_{i}-sright) $ of all
these $leftvert S_{i}rightvert $ many factors
(since all these factors are distinct).
In other words, the product
$prod_{ainOmega}left( x_{fleft( aright) }-a_{fleft( aright)
}right) $ is divisible by $g_{i}left( x_{i}right) $ (since $g_{i}left(
x_{i}right) =prod_{sin S_{i}}left( x_{i}-sright) $). Therefore, the
polynomial $prod_{ainOmega}left( p_{a,fleft( aright) }cdotleft(
x_{fleft( aright) }-a_{fleft( aright) }right) right) $ is
divisible by $g_{i}left( x_{i}right) $ as well (since
begin{equation}
prod_{ainOmega}left( p_{a,fleft( aright) }cdotleft( x_{fleft(
aright) }-a_{fleft( aright) }right) right) =left( prod
_{ainOmega}p_{a,fleft( aright) }right) cdotleft( prod_{ainOmega
}left( x_{fleft( aright) }-a_{fleft( aright) }right) right)
end{equation}
is divisible by $prod_{ainOmega}left( x_{fleft( aright) }-a_{fleft(
aright) }right) $). This proves Claim 1.