# Is there an example of how SOS can be used to show infeasibility of a set of multivariable equations?

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$?

• You are asking many different questions. The usual rule is one question per post. – Yuval Filmus Feb 29 '16 at 16:38
• 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? :/ – gradstudent Feb 29 '16 at 16:39
• 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. – D.W. Feb 29 '16 at 16:59

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.
• 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? – gradstudent Feb 29 '16 at 23:38
• (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? – gradstudent Feb 29 '16 at 23:42
• 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. – Yuval Filmus Mar 1 '16 at 14:59