1
$\begingroup$

Lets say one is given a set of $m$ real polynomial equations in $n$ variables, $P_1 = P_2 = P_2 .. = P_m =0$. I understand that there is some theorem which says that if there is no solution to these simultaneous equations then one necessarily will be able to find polynomials $Q_1,Q_2,..,Q_m, R_1, R_2,..,R_k$ such that $deg(P_iQ_i)$ and $deg(R_i^2)$ are all $\leq d$ for some $k$ and $d$ such that, $\sum_{i=1}^m Q_iP_i + \sum_{j=1}^k R_j^2 = -1$

  • Can someone kindly reference this theorem and its proof?

Now lets say one is looking at a $d$ which is not sufficiently large. Then one will be looking at the set of all polynomials of the form $S = \sum_{i=1}^m Q_iP_i + \sum_{j=1}^k R_j^2$ such that $deg(P_iQ_i)$ and $deg(R_i^2)$ are all $\leq d$ for various $k$. But this is a convex set in the set of polynomials? And $-1 \not \in S$. Then there will exist a separating hyperplane between S and $-1$ and the normal to that plane gives a degree-d pseudo-distribution on S.

  • Does someone have a concrete example of the above phenomenon?

  • Why is this pseudo-distribution indistinguishable from an actual distribution on $S$ if one is only looking at moments $\leq d$?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ You are asking many different questions. The usual rule is one question per post. $\endgroup$ – Yuval Filmus Feb 29 '16 at 16:38
  • $\begingroup$ I thought I just split a question into small parts for making it easier to communicate! :) Won't it be more confusing to have this spread over multiple questions? :/ $\endgroup$ – gradstudent Feb 29 '16 at 16:39
  • $\begingroup$ Usually, the site format works better when you have one question per post. Consider what will happen if someone posts an answer to one of your questions but not the others. Then how will you choose which answer to accept? How can anyone evaluate whether the answer is correct? Also that will make it hard to realize that part of the questions haven't been answered. Moreover, when you find the answer to your first question and do a bit more research based on that, you might be able to answer your subsequent questions yourself. For these reasons, it is generally better to post them separately. $\endgroup$ – D.W.♦ Feb 29 '16 at 16:59
1
$\begingroup$

The theorem you are referring to is known as the Positivstellensatz, but you are citing it incorrectly; given only polynomial equations, the relevant theorem would be the Nullstellensatz. See also lecture notes of Laurent and blog posts of Amir Ali Ahmadi.

Regarding pseudodistributions, Barak defines them as linear operators for low-degree monomials which satisfy the crucial property $E[P^2] \geq 0$ for low-degree $P$. These are all the properties you need when looking at low-degree moments.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks! (1) If I have only equations then can't I use Theorem 2 (the Stengle one) with only $s_o$? That would have the same form as I need. right? Also i don't understand why the uniform degree upperbound is not enforced in Stengle's statement. Can you kindly clarify that? $\endgroup$ – gradstudent Feb 29 '16 at 23:38
  • $\begingroup$ (2) My second question was probably not clear. Say you are given a degree-d pseudo distribution on the hypercube and you are looking at the cone $S$ of polynomials which are SOS of polynomials of degree at most d/2. Now I guess this gives rise to an infinite number of moments upto order d which look like $\tilde{\mathbb{E}}_D [f_1f_2..f_k]$ for $1\leq k \leq d$ and $f_i \in S$ Now is the claim that given these infinite number of upto order d moments there necessarily exists an actual distribution (not "pseudo"!) on the hypercube which would match these infinite numbers? Is that the meaning? $\endgroup$ – gradstudent Feb 29 '16 at 23:42
  • $\begingroup$ Pseudodistributions don't necessarily extend to distributions. That's the entire point. They look like ones only from the point of view of low degree polynomials. $\endgroup$ – Yuval Filmus Mar 1 '16 at 6:24
  • $\begingroup$ What you are saying is true - but my question is different! I wrote down above what I feel is the structure of the infinite number of the moments of the pseudo-distributon upto order d. Now isn't the claim that if one only wants to reproduce these moments upto order "d" then one can always choose an actual distribution which does that? (maybe it will differ with the pseudo-moments of order greater than d) $\endgroup$ – gradstudent Mar 1 '16 at 14:55
  • $\begingroup$ There are no pseudomoments of order greater than $d$. I believe that pseudodistributions don't necessarily extend to distributions at all. Otherwise you could extend them in your mind and so, at least non-algorithmically, they would be indistinguishable from degree $d+1$ pseudodistributions, for example. $\endgroup$ – Yuval Filmus Mar 1 '16 at 14:59

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.