7
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This is Positivstellensatz: en.wikipedia.org/wiki/Stengle%27s_Positivstellensatz . Your statement (which is the real Nullstellensatz) is its special case. $\endgroup$ – Emil Jeřábek Apr 12 '16 at 8:15
  • 2
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Apr 12 '16 at 10:06
  • 3
    $\begingroup$ @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! $\endgroup$ – Anirbit Apr 12 '16 at 14:51
  • 2
    $\begingroup$ 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. $\endgroup$ – Anirbit Apr 12 '16 at 18:34
  • 2
    $\begingroup$ One minor note: I believe the Positivstellensatz only applies to non-negative polynomials, not to arbitrary non-negative functions. $\endgroup$ – mhum Apr 13 '16 at 0:10
9
$\begingroup$

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.

$\endgroup$

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.