pith. sign in

arxiv: 2605.15821 · v2 · pith:7FCEBJ54new · submitted 2026-05-15 · 🧮 math.OC

Degree Bounds for Positivstellens\"atze of general semialgebraic sets

Olga Heijmans-Kuryatnikova , Juan C. Vera , Luis F. Zuluaga This is my paper

Pith reviewed 2026-05-21 07:55 UTC · model grok-4.3

classification 🧮 math.OC
keywords positivstellensatzdegree boundssemialgebraic setssums of squarespolynomial optimizationconvex hierarchies
0
0 comments X

The pith

Explicit degree bounds are established for multiple Positivstellensatz hierarchies that approximate polynomial minima over arbitrary compact semialgebraic sets.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper derives concrete upper bounds on the degrees required for certificates in Putinar's, Schmüdgen's, Krivine-Stengle's, and extended-Handelman's Positivstellensätze to certify that a polynomial is positive on a general compact semialgebraic set S to within a prescribed tolerance. These bounds make it possible to size the underlying optimization problems in advance rather than depending solely on eventual convergence. The work treats both sums-of-squares and linear-programming based hierarchies in a uniform way, reducing the separation between results known for the hypercube and those available for more complicated domains.

Core claim

Using a lift-and-project construction that introduces auxiliary variables to algebraically encode the distance from a point to the set S via Łojasiewicz's inequality, positivity of a polynomial f on S is lifted to positivity of a related polynomial F on a higher-dimensional hypercube; nonnegativity certificates for F on the hypercube then project back to certificates for f on S, yielding explicit degree bounds for each of the four Positivstellensatz variants.

What carries the argument

Lift-and-project construction that adds variables to create an algebraic representation of the distance to S via Łojasiewicz's inequality, transferring positivity certification from the hypercube back to S.

If this is right

  • A priori estimates become available for the size of semidefinite programs in sums-of-squares hierarchies over general compact sets.
  • The first explicit degree bounds are obtained for linear-optimization hierarchies based on Krivine-Stengle and extended-Handelman representations.
  • A single methodology produces degree estimates simultaneously for several distinct Positivstellensatz variants.
  • Quantifiable convergence rates can now be stated for polynomial minimization over any compact semialgebraic set.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same distance-representation technique could be tested on noncompact sets by first imposing a large artificial bounding box.
  • The explicit bounds may guide adaptive degree-increment strategies inside numerical solvers for polynomial optimization.
  • The reduction to hypercube certificates suggests possible links to existing degree-bound results for the hypercube itself.

Load-bearing premise

The lift-and-project step assumes that Łojasiewicz's inequality yields an algebraic distance representation whose positivity certificates on the hypercube project to valid certificates on the original set S.

What would settle it

Explicit computation of a low-degree polynomial whose minimum on a simple compact semialgebraic set such as the unit ball requires a certificate degree exceeding the paper's stated bound would falsify the claim.

read the original abstract

Let $p_{\min}$ denote the minimum of a polynomial $p$ over a (general) compact semialgebraic set $S \subseteq \mathbb{R}^n$. A standard way to approximate $p_{\min}$ is via hierarchies built from Positivstellens\"atze, which certify nonnegativity of polynomials on $S$ using sums of squares or other classes of globally nonnegative polynomials. As the degree of the certificate grows, the values generated by these hierarchies converge asymptotically to $p_{\min}$. A natural question is, then, to determine explicit bounds on the certificate's degree needed to obtain a prescribed $\varepsilon$-approximation to $p_{\min}$, or equivalently certify the positivity of $f:=p - p_{\min} + \varepsilon$ on $S$. We improve the current best degree bounds for Putinar's and Schm\"udgen's SOS-Positivstellensatz over $S$. Also, we obtain degree bounds for Krivine--Stengle's and the recently introduced extended-Handelman's $\mathbb{R}_+$-Positivstellens\"atze over $S$; providing the first explicit degree bounds for linear optimization-based hierarchies over general compact semialgebraic sets. Our approach is based on a lift-and-project construction in which we add new variables to construct an algebraic representation of the distance to the set $S$ using {\L}ojasiewicz's inequality. This lets us lift the problem of certifying the positivity of $f$ on the (complex) set $S$ to the problem of certifying the positivity of a related polynomial $F$ on a higher-dimensional hypercube. By projecting out the added variables, non-negativity certificates for $F$ on the hypercube become non-negativity certificates for $f$ on $S$. Our approach offers a unified methodology to obtain degree bounds for several Positivstellensatz-based hierarchies over general compact sets, narrowing the gap between results for the hypercube (or other simple sets) and more general semialgebraic sets.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript develops a lift-and-project construction that invokes Łojasiewicz's inequality to produce an algebraic representation of the distance to a general compact semialgebraic set S. This reduces positivity certification of a polynomial f on S to positivity certification of a lifted polynomial F on a hypercube, from which degree bounds for Putinar, Schmüdgen, Krivine-Stengle, and extended-Handelman Positivstellensätze are extracted by projection. The central claims are improved degree bounds for the SOS-based certificates and the first explicit bounds for the linear-optimization-based hierarchies over arbitrary compact semialgebraic sets.

Significance. If the derived bounds are effective and computable from the input data, the unified methodology would meaningfully narrow the gap between degree-bound results available for simple sets (hypercube, simplex) and those for general compact semialgebraic sets, with direct consequences for convergence analysis of polynomial optimization hierarchies. The lift-and-project idea is technically clean and offers a reusable template.

major comments (1)
  1. [§4 and Theorem 5.1] §4 (lift-and-project construction) and the statement of the main degree bound (Theorem 5.1): the explicit degree expressions contain a multiplicative factor that depends on the Łojasiewicz exponent α of the distance function to S. For a general compact semialgebraic set defined by polynomials of given degrees, no computable upper bound on α is known; the resulting expressions are therefore not effective from the input data alone. This directly affects the claim that the paper supplies the first explicit degree bounds for the R_+-Positivstellensatz hierarchies, since those hierarchies are constructive only when the required degree is computable a priori.
minor comments (2)
  1. The definition of the extended Handelman cone R_+ is introduced only in the statement of the main theorem; an earlier, self-contained definition would improve readability.
  2. [§3] Notation for the auxiliary variables introduced in the lift step is not always consistent between the construction and the projection argument; a short table of symbols would help.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and for identifying an important point about the effectiveness of the degree bounds. We respond to the major comment below and will incorporate revisions accordingly.

read point-by-point responses

  1. Referee: [§4 and Theorem 5.1] §4 (lift-and-project construction) and the statement of the main degree bound (Theorem 5.1): the explicit degree expressions contain a multiplicative factor that depends on the Łojasiewicz exponent α of the distance function to S. For a general compact semialgebraic set defined by polynomials of given degrees, no computable upper bound on α is known; the resulting expressions are therefore not effective from the input data alone. This directly affects the claim that the paper supplies the first explicit degree bounds for the R_+-Positivstellensatz hierarchies, since those hierarchies are constructive only when the required degree is computable a priori.

    Authors: We agree with the referee that the Łojasiewicz exponent α is a geometric quantity associated to S for which no general computable upper bound is known in terms of the degrees of the defining polynomials alone. Consequently, while the degree expressions in Theorem 5.1 are explicit (closed-form) once α is fixed, they are not a priori effective or computable from the input data for an arbitrary compact semialgebraic set. This is a valid observation that limits immediate constructivity of the hierarchies for completely general S. In the revised version we will add a clarifying paragraph in §4 and a remark immediately following Theorem 5.1 that explicitly states the dependence on α, notes the absence of a uniform bound on α, and indicates that the bounds become effective for any concrete S once an upper bound on α is available through additional analysis. We maintain that the contribution remains the first explicit (parametric) degree bounds for the R_+-Positivstellensatz hierarchies over general compact semialgebraic sets; the lift-and-project template can be instantiated whenever α is known or bounded for a given family of sets, thereby narrowing the gap with results available for simple sets such as the hypercube. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation uses external Łojasiewicz inequality and projects from hypercube

full rationale

The paper derives degree bounds for several Positivstellensätze via a lift-and-project method that invokes the standard Łojasiewicz inequality to algebraically represent distance to S and transfers positivity certificates from the hypercube. This step relies on a known external theorem rather than any self-definition, fitted parameter renamed as prediction, or load-bearing self-citation. No equations or claims in the abstract reduce the output bounds to the inputs by construction; the central construction remains independent of the target result and is self-contained against external mathematical benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on compactness of S and on Łojasiewicz's inequality to enable the algebraic distance representation; no free parameters or new entities are introduced in the abstract.

axioms (2)
  • standard math Łojasiewicz's inequality
    Invoked to construct an algebraic representation of the distance to S for the lift step.
  • domain assumption S is a compact semialgebraic set
    Required for the minimum to exist and for the Positivstellensätze to apply.

pith-pipeline@v0.9.0 · 5927 in / 1391 out tokens · 56518 ms · 2026-05-21T07:55:55.193227+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages

  1. [1]

    Balas, E., Ceria, S., and Cornu´ ejols, G. (1993a). A lift-and-project cutting plane algorithm for mixed 0–1 programs.Mathematical Programming, 58:295–324

    work page

  2. [2]

    Balas, E., Ceria, S., and Cornu´ ejols, G. (1993b). A lift-and-project cutting plane algorithm for mixed 0–1 programs.Mathematical Programming, 58(1):295–324

    work page

  3. [3]

    and Mourrain, B

    Baldi, L. and Mourrain, B. (2023). On the effective Putinar’s Positivstellensatz and moment approximation. Mathematical Programming, 200(1):71–103

    work page 2023

  4. [4]

    Baldi, L., Mourrain, B., and Parusi´ nski, A. (2025). On Lojasiewicz inequalities and the effective Putinar’s Positivstellensatz.Journal of Algebra, 662:741–767

    work page 2025

  5. [5]

    and Slot, L

    Baldi, L. and Slot, L. (2024). Degree bounds for Putinar’s Positivstellensatz on the hypercube.SIAM Journal on Applied Algebra and Geometry, 8(1):1–25

    work page 2024

  6. [6]

    and Nemirovski, A

    Ben-Tal, A. and Nemirovski, A. (2001).Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, volume 2 ofMPS-SIAM Series on Optimization. SIAM, Philadelphia

    work page 2001

  7. [7]

    Bomze, I. M. (2009). Copositive Optimization. In Floudas, C. A. and Pardalos, P. M., editors,Encyclopedia of Optimization, Second Edition, pages 561–564. Springer

    work page 2009

  8. [8]

    and Laurent, M

    de Klerk, E. and Laurent, M. (2010). Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube.SIAM Journal on Optimization, 20:3104–3124

    work page 2010

  9. [9]

    and Vera, J

    de Klerk, E. and Vera, J. (2026). The link between 1-norm approximation and effective Positivstellensatze for the hypercube.Numerical Algebra Control and Optimization, 16:84–104

    work page 2026

  10. [10]

    and Fawzi, H

    Fang, K. and Fawzi, H. (2021). The sum-of-squares hierarchy on the sphere and applications in quantum information theory.Mathematical Programming, 190(1):331–360

    work page 2021

  11. [11]

    Gribling, S., de Klerk, E., and Vera, J. (2026). Revisiting the convergence rate of the lasserre hierarchy for polynomial optimization over the hypercube.Optimization, pages 1–28

    work page 2026

  12. [12]

    (1988).Geometric Algorithms and Combinatorial Optimization, volume 2 ofAlgorithms and Combinatorics

    Gr¨ otschel, M., Lov´ asz, L., and Schrijver, A. (1988).Geometric Algorithms and Combinatorial Optimization, volume 2 ofAlgorithms and Combinatorics. Springer, Berlin

    work page 1988

  13. [13]

    and De Klerk, E

    Kirschner, F. and De Klerk, E. (2022). Convergence rates of RLT and Lasserre-type hierarchies for the generalized moment problem over the simplex and the sphere.Optimization Letters, 16(8):2191–2208

    work page 2022

  14. [14]

    and R´ ev´ esz, S

    Kro´ o, A. and R´ ev´ esz, S. (1999). On Bernstein and Markov-type inequalities for multivariate polynomials on convex bodies.Journal of Approximation Theory, 99(1):134–152. 17

    work page 1999

  15. [15]

    C., and Zuluaga, L

    Kuryatnikova, O., Vera, J. C., and Zuluaga, L. F. (2024). Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets.SIAM Journal on Optimization, 34(2):1970–2006

    work page 2024

  16. [16]

    Lasserre, J. B. (2002). An explicit equivalent positive semidefinite program for nonlinear 0-1 programs.SIAM Journal on Optimization, 12(3):756–769

    work page 2002

  17. [17]

    Lasserre, J. B. (2013). A Lagrangian relaxation view of linear and semidefinite hierarchies.SIAM Journal on optimization, 23(3):1742–1756

    work page 2013

  18. [18]

    Lasserre, J. B. (2015).An introduction to polynomial and semi-algebraic optimization, volume 52. Cambridge University Press

    work page 2015

  19. [19]

    Laurent, M. (2009). Sums of squares, moment matrices and optimization over polynomials. InEmerging applications of algebraic geometry, pages 157–270. Springer

    work page 2009

  20. [20]

    and Slot, L

    Laurent, M. and Slot, L. (2023a). An effective version of Schm¨ udgen’s Positivstellensatz for the hypercube. Optimization Letters, 17(3):515–530

    work page

  21. [21]

    and Slot, L

    Laurent, M. and Slot, L. (2023b). An overview of convergence rates for sum of squares hierarchies in polynomial optimization. InInternational Congress on Industrial and Applied Mathematics, pages 149–176. Springer

    work page

  22. [22]

    Lojasiewicz, S. (1959). Sur le probleme de la division.Studia Mathematica, 18(1):87–136

    work page 1959

  23. [23]

    Magron, V. (2015). Error bounds for polynomial optimization over the hypercube using Putinar type represen- tations.Optimization Letters, 9(5):887–895

    work page 2015

  24. [24]

    Magron, V. (2025). Convergence rates for polynomial optimization on set products.arXiv preprint arXiv:2505.18580

    work page arXiv 2025

  25. [25]

    and Wang, J

    Magron, V. and Wang, J. (2023).Sparse polynomial optimization: theory and practice. World Scientific

    work page 2023

  26. [26]

    (2008).Positive polynomials and sums of squares

    Marshall, M. (2008).Positive polynomials and sums of squares. Number 146. American Mathematical Society

    work page 2008

  27. [27]

    (2023).Moment and polynomial optimization

    Nie, J. (2023).Moment and polynomial optimization. SIAM

    work page 2023

  28. [28]

    and Schweighofer, M

    Nie, J. and Schweighofer, M. (2007). On the complexity of Putinar’s Positivstellensatz.Journal of Complexity, 23(1):135–150

    work page 2007

  29. [29]

    Pe˜ na, J., Vera, J., and Zuluaga, L. (2007). Computing the stability number of a graph via linear and semidefinite programming.SIAM Journal on Optimization, 18(1):87–105

    work page 2007

  30. [30]

    Putinar, M. (1993). Positive polynomials on compact semi-algebraic sets.Indiana University Mathematics Journal, 42(3):969–984

    work page 1993

  31. [31]

    M., Vera, J

    Roebers, L. M., Vera, J. C., and Zuluaga, L. F. (2021). Sparse non-SOS Putinar-type Positivstellens¨ atze.arXiv preprint arXiv:2110.10079

    work page arXiv 2021

  32. [32]

    Schm¨ udgen, K. (1991). TheK-moment problem for compact semi-algebraic sets.Mathematische Annalen, 289(1):203–206

    work page 1991

  33. [33]

    (1986).Theory of Linear and Integer Programming

    Schrijver, A. (1986).Theory of Linear and Integer Programming. John Wiley & Sons, Chichester

    work page 1986

  34. [34]

    Schweighofer, M. (2004). On the complexity of Schm¨ udgen’s Positivstellensatz.Journal of Complexity, 20(4):529 – 543

    work page 2004

  35. [35]

    Sherali, H. D. and Adams, W. P. (2013).A reformulation-linearization technique for solving discrete and con- tinuous nonconvex problems, volume 31. Springer Science & Business Media

    work page 2013

  36. [36]

    (2022a).Asymptotic analysis of semidefinite bounds for polynomial optimization and independent sets in geometric hypergraphs

    Slot, L. (2022a).Asymptotic analysis of semidefinite bounds for polynomial optimization and independent sets in geometric hypergraphs. PhD thesis, Tilburg University. Available athttps://research.tilburguniversity. edu/en/publications/asymptotic-analysis-of-semidefinite-bounds-for-polynomial-optimiz/

    work page

  37. [37]

    Slot, L. (2022b). Sum-of-squares hierarchies for polynomial optimization and the Christoffel–Darboux kernel. SIAM Journal on Optimization, 32(4):2612–2635

    work page

  38. [38]

    and Laurent, M

    Slot, L. and Laurent, M. (2023). Sum-of-squares hierarchies for binary polynomial optimization.Mathematical Programming, 197(2):621–660. 18

    work page 2023