Sharp Degree Bounds for Putinar Certificates in Terms of the Positivity Margin via Analytic Sums of Squares
We establish sharp degree bounds for Putinar sum-of-squares (SOS) certificates in terms of the positivity margin $δ$. 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(δ^{-1/2}\log^2(2/δ))$. 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(δ^{-1/2}\log(2/δ))$, which is also sharp. This improvement is obtained by directly converting...
| Authors | Yuxiang Zhao, Ting Gan |
|---|---|
| Primary category | cs.CL |
| Published | 18 October 2026 |
| Last updated at source | 22 October 2026 |
Popularity, last 3 days
0 now. Counts as reported by the source, snapshotted daily by Silytics.
Recent changes
- 23 Oct 2026 Description: We establish sharp degree bounds for Putinar sum-of-squares (SOS) certificates in terms of the positivity margin $δ$. For any fixed Archimedean quadratic module with prescribed generators and any fixed bound on the degree of the objective, → We establish sharp degree bounds for Putinar sum-of-squares (SOS) certificates in terms of the positivity margin $δ$. For any fixed Archimedean quadratic module with prescribed generators and any fixed degree bound on the objective, normali
Changes detected by Silytics between refreshes of the source.
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 23 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.