<p>As already noted in the comments, the question is based on a misunderstanding; the actual <a href="https://en.wikipedia.org/wiki/Stengle%27s_Positivstellensatz">Positivstellensatz</a> 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.</p>

<p>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.</p>

<p>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.</p>

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

<ul>
<li><p>$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]$.</p></li>
<li><p>$\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.)</p></li>
<li><p>$C(f_1,\dots,f_n)$ is the set of polynomials of the form</p>

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

<p>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$.</p></li>
</ul>

<blockquote>
  <p><strong>Theorem (Positivstellensatz):</strong> 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.</p>
  
  <ol>
  <li><p>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$.</p></li>
  <li><p>$-(h_1\cdots h_t)^{2n}\in C(f_1,\dots,f_r)+I(g_1,\dots,g_s)$ for some $n\in\omega$.</p></li>
  </ol>
</blockquote>

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

<p>We will need</p>

<blockquote>
  <p><strong>Lemma:</strong> Let $S$ be a commutative ring, $u\in S$, and $P\subseteq S$ be such that</p>
  
  <ul>
  <li><p>$P$ is closed under $+$, $\cdot$, and contains all squares;</p></li>
  <li><p>$S=P-P$;</p></li>
  <li><p>$-u^{2n}\notin P$ for all $n\in\omega$.</p></li>
  </ul>
  
  <p>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$.</p>
</blockquote>

<p><strong>Proof of the Positivstellensatz:</strong></p>

<p>$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$.</p>

<p>$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$.</p>

<p><strong>Proof of the lemma:</strong></p>

<p>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$.</p>

<p>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$.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2016-04-16T11:29:55.107Z
2016-04-16T11:39:06.747Z
2016-04-16T11:39:06.747Z
Emil Jeřábek
<p>This question comes from many online resources that introduce Sum-of-Squares method, such as the survey of Barak and Steurer (<a href="http://arxiv.org/abs/1404.5236">http://arxiv.org/abs/1404.5236</a>). Let me focus on Theorem 2.1 of this survey and the paragraph just before that.  </p>

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

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

<p>My question is how does this <em>Corollary</em> 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.     </p>

CC BY-SA 3.0
2016-04-12T08:15:43.500Z
This is Positivstellensatz: https://en.wikipedia.org/wiki/Stengle%27s_Positivstellensatz . Your statement (which is the real Nullstellensatz) is its special case.
Emil Jeřábek
CC BY-SA 3.0
2016-04-12T10:06:33.087Z
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
CC BY-SA 3.0
2016-04-12T14:51:01.927Z
@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!
Student
CC BY-SA 3.0
2016-04-12T15:47:48.693Z
I don’t see anything non-modern about Stengle’s paper. A standard reference appears to be Bochnak, Coste, Roy: Real algebraic geometry.
Emil Jeřábek
CC BY-SA 3.0
2016-04-12T18:34:11.213Z
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.
Student
CC BY-SA 3.0
2016-04-13T00:10:59.393Z
One minor note: I believe the Positivstellensatz only applies to non-negative polynomials, not to arbitrary non-negative functions.
mhum
CC BY-SA 3.0
2016-04-13T13:30:41.443Z
@mhum - Thanks. I have edited.
EmilJeřábek - I see. It makes more sense in that way. Thanks.
anurag anshu
<optimization><semidefinite-programming><sum-of-squares>
Positivstellensatz and sum of squares method
anurag anshu
# Positivstellensatz and sum of squares method

(Asked by: username_0 on 2016-04-12)

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.

**Tags:** optimization, semidefinite-programming, sum-of-squares

> **Comments:**
> **username_1**: This is Positivstellensatz: https://en.wikipedia.org/wiki/Stengle%27s_Positivstellensatz . Your statement (which is the real Nullstellensatz) is its special case.  
> **username_1**: 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.  
> **username_2**: @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!  
> **username_1**: I don’t see anything non-modern about Stengle’s paper. A standard reference appears to be Bochnak, Coste, Roy: Real algebraic geometry.  
> **username_2**: 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.  
> **username_3**: One minor note: I believe the Positivstellensatz only applies to non-negative polynomials, not to arbitrary non-negative functions.  
> **username_0**: @username_3 - Thanks. I have edited. EmilJeřábek - I see. It makes more sense in that way. Thanks.  

---

## 1 answers

### Answer by username_1 on 2016-04-16. Score: 9 | Accepted answer

As already noted in the comments, the question is based on a misunderstanding; the actual [Positivstellensatz](https://en.wikipedia.org/wiki/Stengle%27s_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.


---

