Misplaced Pages

Krivine–Stengle Positivstellensatz

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Schmüdgen Positivstellensatz) Theorem of real algebraic geometry

In real algebraic geometry, Krivine–Stengle Positivstellensatz (German for "positive-locus-theorem") characterizes polynomials that are positive on a semialgebraic set, which is defined by systems of inequalities of polynomials with real coefficients, or more generally, coefficients from any real closed field.

It can be thought of as a real analogue of Hilbert's Nullstellensatz (which concern complex zeros of polynomial ideals), and this analogy is at the origin of its name. It was proved by French mathematician Jean-Louis Krivine [fr; de] and then rediscovered by the Canadian Gilbert Stengle [Wikidata].

Statement

This section may be confusing or unclear to readers. In particular, firstly, a set of polinomial is not a preordering; secondly, such a huge formula requires an explanation. Please help clarify the section. There might be a discussion about this on the talk page. (January 2024) (Learn how and when to remove this message)

Let R be a real closed field, and F = {f1, f2, ..., fm} and G = {g1, g2, ..., gr} finite sets of polynomials over R in n variables. Let W be the semialgebraic set

W = { x ∈ R n ∣ ∀ f ∈ F , f ( x ) ≥ 0 ; ∀ g ∈ G , g ( x ) = 0 } , {\displaystyle W=\{x\in R^{n}\mid \forall f\in F,\,f(x)\geq 0;\,\forall g\in G,\,g(x)=0\},}

and define the preorder associated with W as the set

P ( F , G ) = { ∑ α ∈ { 0 , 1 } m σ α f 1 α 1 ⋯ f m α m + ∑ ℓ = 1 r φ ℓ g ℓ : σ α ∈ Σ 2 [ X 1 , … , X n ] ;   φ ℓ ∈ R [ X 1 , … , X n ] } {\displaystyle P(F,G)=\left\{\sum _{\alpha \in \{0,1\}^{m}}\sigma _{\alpha }f_{1}^{\alpha _{1}}\cdots f_{m}^{\alpha _{m}}+\sum _{\ell =1}^{r}\varphi _{\ell }g_{\ell }:\sigma _{\alpha }\in \Sigma ^{2};\ \varphi _{\ell }\in R\right\}}

where Σ is the set of sum-of-squares polynomials. In other words, P(F, G) = C + I, where C is the cone generated by F (i.e., the subsemiring of R generated by F and arbitrary squares) and I is the ideal generated by G.

Let p ∈ R be a polynomial. Krivine–Stengle Positivstellensatz states that

(i) ∀ x ∈ W p ( x ) ≥ 0 {\displaystyle \forall x\in W\;p(x)\geq 0} if and only if ∃ q 1 , q 2 ∈ P ( F , G ) {\displaystyle \exists q_{1},q_{2}\in P(F,G)} and s ∈ Z {\displaystyle s\in \mathbb {Z} } such that q 1 p = p 2 s + q 2 {\displaystyle q_{1}p=p^{2s}+q_{2}} .
(ii) ∀ x ∈ W p ( x ) > 0 {\displaystyle \forall x\in W\;p(x)>0} if and only if ∃ q 1 , q 2 ∈ P ( F , G ) {\displaystyle \exists q_{1},q_{2}\in P(F,G)} such that q 1 p = 1 + q 2 {\displaystyle q_{1}p=1+q_{2}} .

The weak Positivstellensatz is the following variant of the Positivstellensatz. Let R be a real closed field, and F, G, and H finite subsets of R. Let C be the cone generated by F, and I the ideal generated by G. Then

{ x ∈ R n ∣ ∀ f ∈ F f ( x ) ≥ 0 ∧ ∀ g ∈ G g ( x ) = 0 ∧ ∀ h ∈ H h ( x ) ≠ 0 } = ∅ {\displaystyle \{x\in R^{n}\mid \forall f\in F\,f(x)\geq 0\land \forall g\in G\,g(x)=0\land \forall h\in H\,h(x)\neq 0\}=\emptyset }

if and only if

∃ f ∈ C , g ∈ I , n ∈ N f + g + ( ∏ H ) 2 n = 0. {\displaystyle \exists f\in C,g\in I,n\in \mathbb {N} \;f+g+\left(\prod H\right)^{\!2n}=0.}

(Unlike Nullstellensatz, the "weak" form actually includes the "strong" form as a special case, so the terminology is a misnomer.)

Variants

The Krivine–Stengle Positivstellensatz also has the following refinements under additional assumptions. It should be remarked that Schmüdgen's Positivstellensatz has a weaker assumption than Putinar's Positivstellensatz, but the conclusion is also weaker.

Schmüdgen's Positivstellensatz

Suppose that R = R {\displaystyle R=\mathbb {R} } . If the semialgebraic set W = { x ∈ R n ∣ ∀ f ∈ F , f ( x ) ≥ 0 } {\displaystyle W=\{x\in \mathbb {R} ^{n}\mid \forall f\in F,\,f(x)\geq 0\}} is compact, then each polynomial p ∈ R [ X 1 , … , X n ] {\displaystyle p\in \mathbb {R} } that is strictly positive on W {\displaystyle W} can be written as a polynomial in the defining functions of W {\displaystyle W} with sums-of-squares coefficients, i.e. p ∈ P ( F , ∅ ) {\displaystyle p\in P(F,\emptyset )} . Here P is said to be strictly positive on W {\displaystyle W} if p ( x ) > 0 {\displaystyle p(x)>0} for all x ∈ W {\displaystyle x\in W} . Note that Schmüdgen's Positivstellensatz is stated for R = R {\displaystyle R=\mathbb {R} } and does not hold for arbitrary real closed fields.

Putinar's Positivstellensatz

Define the quadratic module associated with W as the set

Q ( F , G ) = { σ 0 + ∑ j = 1 m σ j f j + ∑ ℓ = 1 r φ ℓ g ℓ : σ j ∈ Σ 2 [ X 1 , … , X n ] ;   φ ℓ ∈ R [ X 1 , … , X n ] } {\displaystyle Q(F,G)=\left\{\sigma _{0}+\sum _{j=1}^{m}\sigma _{j}f_{j}+\sum _{\ell =1}^{r}\varphi _{\ell }g_{\ell }:\sigma _{j}\in \Sigma ^{2};\ \varphi _{\ell }\in \mathbb {R} \right\}}

Assume there exists L > 0 such that the polynomial L − ∑ i = 1 n x i 2 ∈ Q ( F , G ) . {\displaystyle L-\sum _{i=1}^{n}x_{i}^{2}\in Q(F,G).} If p ( x ) > 0 {\displaystyle p(x)>0} for all x ∈ W {\displaystyle x\in W} , then p ∈ Q(F,G).

See also

Notes

  1. Schmüdgen, Konrad (1991). "The K-moment problem for compact semi-algebraic sets". Mathematische Annalen. 289 (1): 203–206. doi:10.1007/bf01446568. ISSN 0025-5831.
  2. Stengle, Gilbert (1996). "Complexity Estimates for the Schmüdgen Positivstellensatz". Journal of Complexity. 12 (2): 167–174. doi:10.1006/jcom.1996.0011.
  3. Putinar, Mihai (1993). "Positive Polynomials on Compact Semi-Algebraic Sets". Indiana University Mathematics Journal. 42 (3): 969–984. doi:10.1512/iumj.1993.42.42045.

References

Categories: