Optimal degree bounds for sum-of-squares representations
Abstract
The moment-sum-of-squares (SOS) hierarchy provides a sequence of bounds on the minimum of a polynomial over a basic closed semialgebraic set, i.e., a subset of ℝn defined by finitely many polynomial constraints. We establish optimal bounds on the error of the SOS hierarchy in the following settings: 1. If the constraints define an Archimedean quadratic module: the error of the Putinar-based hierarchy at level k is Θ((log k)4/k2) in the worst case. 2. If the constraints define a compact semialgebraic set: the error of the Schmüdgen-based hierarchy at level k is Θ((log k)2/k2) in the worst case. 3. If the constraints define an Archimedean quadratic module and satisfy linear independence constraint qualification conditions (LICQ): the error of the hierarchy at level k is Θ(1/k4) in the worst case. Here, the upper bound holds already for the Putinar-based hierarchy, while the lower bound holds even against the Schmüdgen-based hierarchy. Equivalently, these give best-possible effective versions of Putinar's and Schmüdgen's Positivstellensätze for these settings (in terms of their dependence on k).
Related
- Density Bounds in Hua's Theorem for Prime Squares
- A COVID-19 transmission model with optimal control integrating BERT with LHS and least-squares fitting for real-world consistency
- Quiver Bases of Cartan Squares of Minuscule Representations
- Bounds on the number of squares in recurrence sequences: y0=b2 (II)
- Axis-parallel square packing with an exact formula for optimal packing of seven squares
BibTeX
@misc{blomenhofer2026optimal,
title = {{Optimal degree bounds for sum-of-squares representations}},
author = {Alexander Taveira Blomenhofer and Sander Gribling and Didier Henrion and Milan Korda and Poornendu Kumar and Victor Magron and Lucas Slot and Luis Felipe Vargas and Juan Vera},
howpublished = {HAL},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.24638},
eprint = {2610.24638},
archivePrefix = {arXiv},
url = {https://laas.hal.science/hal-05825413v1},
}
RIS
TY - UNPB
TI - Optimal degree bounds for sum-of-squares representations
AU - Alexander Taveira Blomenhofer
AU - Sander Gribling
AU - Didier Henrion
AU - Milan Korda
AU - Poornendu Kumar
AU - Victor Magron
AU - Lucas Slot
AU - Luis Felipe Vargas
AU - Juan Vera
PY - 2026
DA - 2026/10/17
PB - HAL
DO - 10.48550/arxiv.2610.24638
UR - https://laas.hal.science/hal-05825413v1
AB - The moment-sum-of-squares (SOS) hierarchy provides a sequence of bounds on the minimum of a polynomial over a basic closed semialgebraic set, i.e., a subset of ℝ^n defined by finitely many polynomial constraints. We establish optimal bounds on the error of the SOS hierarchy in the following settings: 1. If the constraints define an Archimedean quadratic module: the error of the Putinar-based hierarchy at level k is Θ((log k)^4/k^2) in the worst case. 2. If the constraints define a compact semialgebraic set: the error of the Schmüdgen-based hierarchy at level k is Θ((log k)^2/k^2) in the worst case. 3. If the constraints define an Archimedean quadratic module and satisfy linear independence constraint qualification conditions (LICQ): the error of the hierarchy at level k is Θ(1/k^4) in the worst case. Here, the upper bound holds already for the Putinar-based hierarchy, while the lower bound holds even against the Schmüdgen-based hierarchy. Equivalently, these give best-possible effective versions of Putinar's and Schmüdgen's Positivstellensätze for these settings (in terms of their dependence on k).
ER -