An effective version of Schmüdgen's Positivstellensatz for the hypercube

Abstract

Let $S\subseteq {\mathbb{R}}^n$ be a compact semialgebraic set and let $f$ be a polynomial nonnegative on $S$. Schmüdgen's Positivstellensatz then states that for any $\eta >0$, the nonnegativity of $f+\eta$ on $S$ can be certified by expressing $f+\eta$ as a conic combination of products of the polynomials that occur in the inequalities defining $S$, where the coefficients are (globally nonnegative) sum-of-squares polynomials. It does not, however, provide explicit bounds on the degree of the polynomials required for such an expression. We show that in the special case where $S=[-1,1{]}^n$ is the hypercube, a Schmüdgen-type certificate of nonnegativity exists involving only polynomials of degree $O(1/\sqrt{\eta })$. This improves quadratically upon the previously best known estimate in $O(1/\eta )$. Our proof relies on an application of the polynomial kernel method, making use in particular of the Jackson kernel on the interval $[-1,1]$.

v2: implemented minor changes based on referee comments. 11 pages, 1 figure