# Positivstellensatz and sum of squares method

This question comes from many online resources that introduce Sum-of-Squares method, such as the survey of Barak and Steurer (http://arxiv.org/abs/1404.5236). Let me focus on Theorem 2.1 of this survey and the paragraph just before that.

Starting point is "Positivstellensatz" which says that any non-negative polynomial over reals can be written as a sum of squares of rational functions. Corollary of this is the following statement, which is central to sum of squares proofs:

Given multivariate polynomials $P_1,P_2\ldots P_m$ over reals, the system of equations $\{P_1=0,P_2=0\ldots P_m=0\}$ has no solution over reals if and only if there exist polynomials $Q_1,Q_2\ldots Q_m$ and a sum of squares of polynomials $S$ such that $-1=S+\sum_i P_iQ_i$.

My question is how does this Corollary follow from "Positivstellensatz". This important implication constantly appears in various lecture notes/videos, but as far as I have noticed, the proof is always skipped.

• This is Positivstellensatz: en.wikipedia.org/wiki/Stengle%27s_Positivstellensatz . Your statement (which is the real Nullstellensatz) is its special case. – Emil Jeřábek Apr 12 '16 at 8:15
• And indeed, as I just checked, this is exactly the Positivstellensatz referenced in the Barak and Steurer paper. You misunderstood the context. The Positivestellensatz is not Artin's theorem, though the two are related. – Emil Jeřábek Apr 12 '16 at 10:06
• @EmilJeřábek Do you know of a reference for the proof of this real Nullstellensatz? I haven't been able to locate any modern presentation of it except for the 1964 and 1974 papers referenced in the notes linked above! – Anirbit Apr 12 '16 at 14:51
• As in I haven't seen any recent course lecture notes or reviews which discuss this proof. No SOS hardness paper I have seen ever reviews this proof. – Anirbit Apr 12 '16 at 18:34
• One minor note: I believe the Positivstellensatz only applies to non-negative polynomials, not to arbitrary non-negative functions. – mhum Apr 13 '16 at 0:10

As already noted in the comments, the question is based on a misunderstanding; the actual Positivstellensatz is a stronger statement than Artin’s theorem on nonnegative polynomials, and the real Nullstellensatz as stated in the question is indeed its special case.

Other comments asked for lecture notes with a proof of the Positivstellensatz, and as I do not know of any, I can as well write it myself.

The overall strategy of the proof below is similar to the model-theoretic proof of Hilbert’s Nullstellensatz; I will use the facts that each ordered field embeds in a real-closed field, and the theory of real-closed fields has quantifier elimination.

First, some notation. Let $F$ be an ordered field, and $f_1,\dots,f_n\in F[x_1,\dots,x_m]$ polynomials.

• $I(f_1,\dots,f_n)$ denotes the ideal generated by $f_1,\dots,f_n$, i.e., polynomials of the form $f_1g_1+\dots+f_ng_n$ for some $g_1,\dots,g_n\in F[x_1,\dots,x_m]$.

• $\Sigma$ denotes the set of polynomials of the form $\sum_{i=1}^na_ig_i^2$, where $n\ge0$, $g_i\in F[x_1,\dots,x_m]$, and $a_i\in F^+$. (If every positive element is a sum of squares, such as for $F=\mathbb R$, then $\Sigma$ just consists of sums of squares of polynomials.)

• $C(f_1,\dots,f_n)$ is the set of polynomials of the form

$$\sum_{I\subseteq[n]}s_I\prod_{i\in I}f_i,$$

where $s_I\in\Sigma$. That is, $C(f_1,\dots,f_n)$ is the least set of polynomials that contains the $f_i$’s, squares, and positive constants, and is closed under $+$ and $\cdot$.

Theorem (Positivstellensatz): Let $F$ be an ordered field, $R\supseteq F$ a real-closed field, and $f_1,\dots,f_r,g_1,\dots,g_s,h_1,\dots,h_t\in F[x_1,\dots,x_m]$. The following are equivalent.

1. The system $\{f_i(\vec x)\ge0,g_j(\vec x)=0,h_k(\vec x)\ne0:i\in[r],j\in[s],k\in[t]\}$ has no solution $\vec a\in R^m$.

2. $-(h_1\cdots h_t)^{2n}\in C(f_1,\dots,f_r)+I(g_1,\dots,g_s)$ for some $n\in\omega$.

We could also accommodate strict inequalities $p_i(\vec x)>0$ by including $p_i$ among both the $f_i$’s and the $h_i$’s.

We will need

Lemma: Let $S$ be a commutative ring, $u\in S$, and $P\subseteq S$ be such that

• $P$ is closed under $+$, $\cdot$, and contains all squares;

• $S=P-P$;

• $-u^{2n}\notin P$ for all $n\in\omega$.

Then there is a homomorphism $\phi\colon S\to K$ to an ordered field $K$ such that $\phi(p)\ge0$ for all $p\in P$, and $\phi(u)\ne0$.

Proof of the Positivstellensatz:

$2\to1$: If $f_i(\vec a)\ge 0$ for $i=1,\dots,r$, then also $f(\vec a)\ge0$ for all $f\in C(f_1,\dots,f_r)$. Likewise, $g(\vec a)=0$ for all $g\in I(g_1,\dots,g_s)$. Thus, if $h=h_1\cdots h_t$ satisfies $-h^{2n}\in C(\vec f)+I(\vec g)$, then $0\le-h^{2n}(\vec a)\le0$, thus $h(\vec a)=0$, thus $h_i(\vec a)=0$ for some $i=1,\dots,t$.

$1\to2$: Assume 2 is false. Let $S=F[x_1,\dots,x_m]$, and $P=C(\vec f)+I(\vec g)\subseteq S$. Notice that every $s\in S$ is a difference of two squares, e.g., $s=\bigl(\tfrac12(s+1)\bigr)^2-\bigl(\tfrac12(s-1)\bigr)^2$. Since $-h^{2n}\notin P$ for all $n$, Lemma 1 gives a homomorphism $\phi\colon F\to K$, where $K$ is an ordered field, $\phi(P)\ge0$, and $\phi(h)\ne0$. We may assume $K$ is real closed. Since $P$ includes $F^+$, $\phi$ restricts to an ordered field embedding of $F$ in $K$; we may simply assume $F\subseteq K$. Then, putting $a_i=\phi(x_i)$, we have $f_i(\vec a)\ge0$, $g_i(\vec a)=0$, and $h_i(\vec a)\ne0$ in $K$. The existence of $\vec a$ with these properties can be expressed as a first-order formula with parameters from $F$; since this formula is true in $K$, quantifier elimination for real-closed fields implies it is also true in $R$.

Proof of the lemma:

Using Zorn’s lemma, let $Q\supseteq P$ be a maximal subset of $S$ closed under $+$ and $\cdot$ such that $-u^{2n}\notin Q$ for any $n\in\omega$.

Put $I=Q\cap(-Q)$. Since $Q$ is closed under $+$ and $\cdot$, $I$ is closed under $+$ and $-$, and we have $IQ\subseteq I$. Since $S=Q-Q$, this means $I$ is an ideal of $S$.

I claim that $S=Q\cup(-Q)$. Assume for contradiction that $a,-a\notin Q$ for some $a\in S$. As $a\notin Q$, $Q+aQ$ is a proper extension of $Q$ closed under $+$ and $\cdot$, thus by maximality of $Q$, we have $-u^{2n}=q+ar$ for some $n\in\omega$ and $q,r\in Q$. Likewise, $-a\notin Q$ gives $-u^{2m}=s-at$ for some $m$ and $s,t\in Q$. We have $-u^{2m}r\in-Q$, and $-u^{2m}r=sr-atr=sr+qt+u^{2n}t\in Q$, thus $u^{2m}r\in I$. It follows that $-u^{2(n+m)}=qu^{2m}+aru^{2m}\in Q+I\subseteq Q$, a contradiction.

I also claim that the ideal $I$ is prime. Assume for contradiction $ab\in I$, but $a,b\notin I$. Without loss of generality, $a,b\notin Q$. Thus, $-b\in Q$, and $-u^{2n}\in Q+aQ$ for some $n$, which implies $u^{2n}b\in-bQ-abQ\subseteq Q+I\subseteq Q$. Likewise, $-u^{2m}\in Q+bQ$ for some $m$, thus $-u^{2(n+m)}\in u^{2n}Q+u^{2n}bQ\subseteq Q$, a contradiction.

Thus, $S/I$ is an integral domain, and it is a (totally) ordered ring by making $Q/I$ its positive cone. Its fraction field $K$ is an ordered field, and the quotient map $\phi\colon S\to S/I\subseteq K$ has the required properties.