Sharp Degree Bounds for Putinar Certificates in Terms of the Positivity Margin via Analytic Sums of Squares

Abstract

We establish sharp degree bounds for Putinar sum-of-squares (SOS) certificates in terms of the positivity margin $\delta$. For any fixed Archimedean quadratic module with prescribed generators and any fixed degree bound on the objective, normalized polynomial objectives admit a uniform certificate-degree upper bound of $O(\delta^{-1/2}\log^2(2/\delta))$. The bound is sharp: we construct a matching lower-bound example in three variables. We further show that the number of inequality generators affects the optimal degree bound. For quadratic modules with at most two inequality generators, the bound improves to $O(\delta^{-1/2}\log(2/\delta))$, which is also sharp. This improvement is obtained by directly converting two-generator Stengle refutations into certificates for the original quadratic module. We also establish sharp degree bounds for trigonometric SOS certificates on tori. In particular, for the full torus without additional constraints, the optimal worst-case order improves to $\delta^{-1/4}$, whereas additional equality constraints can lead the order to $\delta^{-1/2}\log(2/\delta)$. These results also yield sharp worst-case convergence rates for the Lasserre hierarchy.