Vishnoi's Proof of Combinatorial Nullstellensatz












1














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!










share|cite|improve this question





























    1














    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!










    share|cite|improve this question



























      1












      1








      1


      2





      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!










      share|cite|improve this question















      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!







      combinatorics commutative-algebra algebraic-combinatorics






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Nov 24 at 19:27









      mrtaurho

      3,1131930




      3,1131930










      asked Nov 24 at 19:25









      owl

      596




      596






















          1 Answer
          1






          active

          oldest

          votes


















          2














          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] $, 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.






          share|cite|improve this answer





















          • 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!
            – owl
            Nov 26 at 21:40






          • 1




            @owl: More importantly, please post your thesis somewhere once it's finished :)
            – darij grinberg
            Nov 26 at 22:44













          Your Answer





          StackExchange.ifUsing("editor", function () {
          return StackExchange.using("mathjaxEditing", function () {
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          });
          });
          }, "mathjax-editing");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "69"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: true,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });














          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3011972%2fvishnois-proof-of-combinatorial-nullstellensatz%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          1 Answer
          1






          active

          oldest

          votes








          1 Answer
          1






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          2














          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] $, 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.






          share|cite|improve this answer





















          • 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!
            – owl
            Nov 26 at 21:40






          • 1




            @owl: More importantly, please post your thesis somewhere once it's finished :)
            – darij grinberg
            Nov 26 at 22:44


















          2














          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] $, 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.






          share|cite|improve this answer





















          • 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!
            – owl
            Nov 26 at 21:40






          • 1




            @owl: More importantly, please post your thesis somewhere once it's finished :)
            – darij grinberg
            Nov 26 at 22:44
















          2












          2








          2






          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] $, 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.






          share|cite|improve this answer












          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] $, 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.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Nov 26 at 4:12









          darij grinberg

          10.2k33061




          10.2k33061












          • 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!
            – owl
            Nov 26 at 21:40






          • 1




            @owl: More importantly, please post your thesis somewhere once it's finished :)
            – darij grinberg
            Nov 26 at 22:44




















          • 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!
            – owl
            Nov 26 at 21:40






          • 1




            @owl: More importantly, please post your thesis somewhere once it's finished :)
            – darij grinberg
            Nov 26 at 22:44


















          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!
          – owl
          Nov 26 at 21:40




          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!
          – owl
          Nov 26 at 21:40




          1




          1




          @owl: More importantly, please post your thesis somewhere once it's finished :)
          – darij grinberg
          Nov 26 at 22:44






          @owl: More importantly, please post your thesis somewhere once it's finished :)
          – darij grinberg
          Nov 26 at 22:44




















          draft saved

          draft discarded




















































          Thanks for contributing an answer to Mathematics Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.





          Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


          Please pay close attention to the following guidance:


          • Please be sure to answer the question. Provide details and share your research!

          But avoid



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3011972%2fvishnois-proof-of-combinatorial-nullstellensatz%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          Ellipse (mathématiques)

          Quarter-circle Tiles

          Mont Emei