[Submitted on 18 Oct 2026 (v1), last revised 22 Oct 2026 (this version, v2)]
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.
Submission history
From: Yuxiang Zhao [view email]
[v1] Sun, 18 Oct 2026 23:10:30 UTC (34 KB)
[v2] Thu, 22 Oct 2026 17:36:31 UTC (63 KB)
