1
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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! $\endgroup$ Nov 26 '18 at 21:40
  • 1
    $\begingroup$ @owl: More importantly, please post your thesis somewhere once it's finished :) $\endgroup$ Nov 26 '18 at 22:44
  • 1
    $\begingroup$ wesscholar.wesleyan.edu/etd_hon_theses/2246 $\endgroup$ May 26 '20 at 21:05
  • $\begingroup$ @YuliaAlexandr: Thank you! (Is this the same version as mathymath.github.io/alexandr_yulia_2019_ba.pdf ?) $\endgroup$ May 26 '20 at 23:19
  • $\begingroup$ Yes, it is! :-) $\endgroup$ Jun 12 '20 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.