A new proof for the existence of degree bounds for Putinar's Positivstellensatz

Abstract

Putinar's Positivstellensatz is a central theorem in real algebraic geometry. It states the following: If you have a set $S=\{x\in R^n|g_1(x)\ge 0,...,g_m(x)\ge 0\}$ described by some real polynomials $g_i$, then every real polynomial $f$ that is positive on $S$ can be written as a sum of squares weighted by the $g_i$ and $1$. Consider such an identity $f={\sum }_{i=1}^m{g}_i{s}_i+s_0$. For the applications in polynomial optimization, especially semidefinite programming, the following is important: There exists a bound $N$ for the degrees of the $s_i$ which depends only on the $g_i$, $n$, the degree of $f$, an upper bound for $||f||$ and a lower bound for $\min f(S)$. Two proofs from Prestel and Heß resp. Schweighofer and Nie ([Pr], [He] resp. [Sw], [NS]) for the existence of these degree bounds are known (also for the matrix version of Putinar's Positivstellensatz by Helton and Nie [HN]). Prestel uses valuation and model theory for his approach while Schweighofer gives a constructive solution by using a theorem of Pólya. In this paper we will give a new elementary, short but non-constructive proof.

6 pages