pith. sign in

arxiv: 2605.18980 · v1 · pith:IO4UEAQOnew · submitted 2026-05-18 · 💻 cs.SC · math.AC

Computing Certificates in Archimedean Univariate Saturated Quadratic Modules

Jose Abel Castellanos-Joo , Deepak Kapur This is my paper

Pith reviewed 2026-05-20 00:24 UTC · model grok-4.3

classification 💻 cs.SC math.AC
keywords sums of squaresquadratic modulesArchimedeansaturatedcertificatesunivariate polynomialssymbolic computationBasic Lemma
0
0 comments X

The pith

A symbolic algorithm computes sums-of-squares certificates for non-negative univariate polynomials belonging to saturated Archimedean quadratic modules by rewriting them against natural generators.

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

The paper presents a new symbolic method to produce explicit sums-of-squares multipliers that witness membership of a non-negative univariate polynomial in a given quadratic module. The method first works with the natural generators of the module, which are directly readable from the semialgebraic set when the module is Archimedean and saturated. It then translates those certificates back to the original generators by applying the Basic Lemma repeatedly and performing a case analysis on the types of factors that appear. An implementation in Maple is shown to succeed on examples where the existing tool RealCertify returns no certificate.

Core claim

For an Archimedean saturated quadratic module in one variable, every non-negative polynomial that belongs to the module admits a representation as a sum of squares times the natural generators; these representations are computed first relative to the natural generators and then converted, via the Basic Lemma splitting, into sums of squares times the original generators of the module.

What carries the argument

The Basic Lemma of Kuhlmann, Marshall and Schwartz, which splits each non-negative factor of a generator so that certificates of products of natural generators can be assembled by exhaustive case analysis on generator types.

If this is right

  • Certificates are obtained directly from the description of the semialgebraic set without invoking semidefinite programming solvers.
  • In the univariate case the quadratic module is automatically a preordering, so the same certificate works for both structures after the translation step.
  • The method supplies explicit multipliers even when general-purpose real-algebraic tools fail to terminate or exceed memory limits.

Where Pith is reading between the lines

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

  • The same natural-generator route might be feasible in a few multivariate cases once analogous generators are identified.
  • The degree of the resulting multipliers could be bounded in terms of the degrees of the input generators.
  • Systematic testing on parametric families of univariate polynomials would reveal whether the case analysis remains tractable as the number of generators grows.

Load-bearing premise

The input quadratic module must be both Archimedean and saturated so that its natural generators can be read off directly and the Basic Lemma applies without extra obstructions.

What would settle it

A univariate polynomial that is non-negative on the semialgebraic set yet for which the algorithm cannot produce the required sums-of-squares multipliers after any finite number of Basic-Lemma splittings.

read the original abstract

A new symbolic algorithm to compute sums of squares multipliers (certificates) to witness the membership of non-negative univariate polynomials in a saturated univariate quadratic module is presented. Certificates are first computed in terms of natural generators introduced by Kuhlmann and Marshall for an Archimedean saturated quadratic module; natural generators can be easily read-off from a semialgebraic set. In the univariate case, an Archimedean quadratic module is also a preordering since it is closed under multiplication; certificates have different representations when a polynomial is viewed as a member in a quadratic module versus in a preordering An algorithm is given to compute certificates of natural generators in terms of the original generators; it uses a construction introduced by Kuhlmann, Marshall, and Schwartz known as the ``Basic Lemma'', which splits the non-negative factors of generators. To compute a quadratic module certificate, certificates of products of natural generators are computed using a detailed case analysis based on the types of natural generators. An implementation of the algorithms proposed in Maple is also discussed. The certificates obtained using this implementation are compared with those generated by RealCertify. We discuss examples where RealCertify is unable to find certificates while the proposed method is successful.

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 / 3 minor

Summary. The paper presents a symbolic algorithm for computing sums of squares multipliers that certify membership of non-negative univariate polynomials in an Archimedean saturated quadratic module. Certificates are first obtained with respect to the natural generators of Kuhlmann and Marshall (readable directly from the semialgebraic set), then converted to the original generators via the Basic Lemma of Kuhlmann-Marshall-Schwartz and a detailed case analysis on generator types. A Maple implementation is described and shown to produce certificates on examples where RealCertify fails.

Significance. If the case analysis is exhaustive and the implementation free of gaps, the work supplies a practical, structured procedure for certificate computation in the univariate setting. It explicitly exploits the fact that an Archimedean quadratic module is a preordering and contrasts quadratic-module versus preordering representations. The concrete comparison with RealCertify and the use of standard results (natural generators, Basic Lemma) constitute reproducible strengths that could benefit positivstellensatz-based methods and polynomial optimization.

major comments (1)
  1. [case analysis section] The central algorithmic claim rests on the completeness of the case analysis for products of natural generators (described after the Basic Lemma application). Without an explicit enumeration or proof that every combination of generator types arising in the univariate saturated case is covered, it is not possible to confirm that the conversion from natural-generator certificates to original-generator certificates is always successful.
minor comments (3)
  1. The distinction between quadratic-module and preordering certificates is stated but would benefit from a short illustrative example immediately after the definition of natural generators.
  2. [implementation section] The Maple implementation section would be strengthened by reporting the degrees and number of generators for the examples where RealCertify fails, allowing readers to gauge the practical scope.
  3. A few sentences clarifying how the Archimedean and saturated hypotheses are checked or assumed for input instances would improve accessibility.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript and the constructive comment on the case analysis. We address the major comment below and will strengthen the presentation accordingly.

read point-by-point responses

  1. Referee: [case analysis section] The central algorithmic claim rests on the completeness of the case analysis for products of natural generators (described after the Basic Lemma application). Without an explicit enumeration or proof that every combination of generator types arising in the univariate saturated case is covered, it is not possible to confirm that the conversion from natural-generator certificates to original-generator certificates is always successful.

    Authors: We thank the referee for this observation, which correctly identifies a point where the manuscript could be made more transparent. In the univariate saturated Archimedean setting the natural generators are linear factors corresponding to the finite boundary points of the semialgebraic set together with, when the set is unbounded, a single generator that encodes the direction at infinity. Consequently the possible products involve at most two distinct linear factors (or repeated factors of the same linear polynomial). Our case analysis proceeds by distinguishing these situations and applying the Basic Lemma to each. To remove any ambiguity we will add an explicit enumeration of the finitely many type combinations together with a short paragraph arguing that they exhaust the univariate saturated case. The revised manuscript will therefore contain both the enumeration and the completeness argument. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents an independent algorithmic construction for computing SOS multipliers in the restricted univariate Archimedean saturated case. It directly invokes the Kuhlmann-Marshall natural generators and the Basic Lemma of Kuhlmann-Marshall-Schwartz as external, established results in real algebraic geometry; these are not self-citations by the present authors and are not used to derive the target result by definition. The new contribution consists of a concrete case-analysis procedure that converts certificates for natural generators into certificates for the original generators, together with a Maple implementation. No equation or step reduces to a fitted parameter, a self-definitional loop, or a load-bearing self-citation chain; the derivation remains self-contained once the standard external theorems are granted.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard properties of quadratic modules and preorderings in real algebraic geometry together with the Basic Lemma from prior literature; no new free parameters or invented entities are introduced.

axioms (2)
  • domain assumption An Archimedean saturated quadratic module in the univariate case is closed under multiplication and therefore coincides with a preordering.
    Invoked in the abstract to justify that certificates have different representations in the module versus the preordering.
  • domain assumption Natural generators introduced by Kuhlmann and Marshall can be read off from the semialgebraic set description.
    Used as the starting point for the certificate computation.

pith-pipeline@v0.9.0 · 5744 in / 1487 out tokens · 36860 ms · 2026-05-20T00:24:47.426375+00:00 · methodology

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

17 extracted references · 17 canonical work pages

  1. [1]

    Ab- handlungen aus dem Mathematischen Seminar der Universität Hamburg 5, 100–115

    Über die zerlegung definiter funktionen in quadrate. Ab- handlungen aus dem Mathematischen Seminar der Universität Hamburg 5, 100–115. URL:http://dx.doi.org/10.1007/BF02952513, doi:10.1007/ bf02952513. Augustin, D.,

    work page doi:10.1007/bf02952513

  2. [2]

    Constructive proofs of some positivstellensätze for compact semialgebraic subsets of Źd. J. Optim. Theory Appl. 158, 410–418. URL:https://doi.org/10.1007/s10957-012-0261-9, doi:10. 1007/s10957-012-0261-9. Baldi, L., Krick, T., Mourrain, B.,

    work page doi:10.1007/s10957-012-0261-9

  3. [3]

    Mathematical Programming 200, 71–103

    On the effective putinar’s positivstellensatz and moment approximation. Mathematical Programming 200, 71–103. URL:http://dx.doi.org/10.1007/s10107-022-01877-6, doi:10.1007/ s10107-022-01877-6. Baldi, L., Slot, L.,

    work page doi:10.1007/s10107-022-01877-6

  4. [4]

    Proof certificates for algebra and their application to automatic geometry theorem proving, in: Automated Deduction in Geometry: 7th International Workshop, ADG 2008, Shang- hai, China, September 22-24,

    work page 2008

  5. [5]

    Relu- plex: An efficient smt solver for verifying deep neural networks, in: Com- puter Aided Verification: 29th International Conference, CAV 2017, Hei- delberg, Germany, July 24-28, 2017, Proceedings, Part I 30, Springer. pp. 97–117. Kuhlmann, S., Marshall, M.,

    work page 2017

  6. [6]

    URL:https://doi.org/10.1090/s0002-9947-02-03075-1, doi:10.1090/s0002-9947-02-03075-1

    Positivity, sums of squares and the multi-dimensional moment problem 354, 4285–4301. URL:https://doi.org/10.1090/s0002-9947-02-03075-1, doi:10.1090/s0002-9947-02-03075-1. Kuhlmann, S., Marshall, M., Schwartz, N.,

    work page doi:10.1090/s0002-9947-02-03075-1

  7. [7]

    URL:https: 39 //doi.org/10.1515/advg.2005.5.4.583, doi:10.1515/advg.2005.5.4

    Positivity, sums of squares and the multi-dimensional moment problem II 5, 583–606. URL:https: 39 //doi.org/10.1515/advg.2005.5.4.583, doi:10.1515/advg.2005.5.4

    work page doi:10.1515/advg.2005.5.4.583 2005

  8. [8]

    Proceedings of the American Mathematical Soci- ety 24, 803–807

    Computable fields and arithmetically definable ordered fields. Proceedings of the American Mathematical Soci- ety 24, 803–807. URL:http://www.jstor.org/stable/2037328. Magron, V., Din, M.S.E.,

    work page arXiv

  9. [9]

    ACM Commun

    Realcertify: a maple package for certifying non-negativity. ACM Commun. Comput. Algebra 52, 34–37. URL:https: //doi.org/10.1145/3282678.3282681, doi:10.1145/3282678.3282681. Magron, V., Safey El Din, M.,

    work page doi:10.1145/3282678.3282681

  10. [10]

    Journal of Symbolic Computation 107, 221–250

    On exact reznick, hilbert-artin and putinar’s representations. Journal of Symbolic Computation 107, 221–250. URL:https://www.sciencedirect.com/science/article/ pii/S0747717121000249, doi:https://doi.org/10.1016/j.jsc.2021. 03.005. Magron, V., Safey El Din, M., Schweighofer, M., Vu, T.H.,

    work page doi:10.1016/j.jsc.2021 2021

  11. [11]

    Exact sohs decompositions of trigonometric univariate polynomials with gaus- sian coefficients, in: Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, Association for Computing Machin- ery, New York, NY, USA. p. 325–332. URL:https://doi.org/10.1145/ 3476446.3535480, doi:10.1145/3476446.3535480. Marshall, M., 2008a. Posi...

    work page doi:10.1145/3476446.3535480 2022

  12. [12]

    On the complexity of putinar’s positivstel- lensatz. J. Complex. 23, 135–150. URL:https://doi.org/10.1016/j. jco.2006.07.002, doi:10.1016/j.jco.2006.07.002. Putinar, M.,

    work page doi:10.1016/j 2006

  13. [13]

    Indiana University Mathematics Journal 42, 969–984

    Positive polynomials on compact semi-algebraic sets. Indiana University Mathematics Journal 42, 969–984. URL:http://www. jstor.org/stable/24897130. 40 Scheiderer, C.,

    work page arXiv

  14. [14]

    Journal of Algebra 289, 558–573

    Distinguished representations of non-negative poly- nomials. Journal of Algebra 289, 558–573. URL:http://dx.doi.org/ 10.1016/j.jalgebra.2005.01.043, doi:10.1016/j.jalgebra.2005.01

    work page doi:10.1016/j.jalgebra.2005.01.043 2005

  15. [15]

    Mathematische Annalen 289, 203–206

    The k-moment problem for compact semi-algebraic sets. Mathematische Annalen 289, 203–206. URL:http://dx.doi.org/ 10.1007/BF01446568, doi:10.1007/bf01446568. Schweighofer, M.,

    work page doi:10.1007/bf01446568

  16. [16]

    Singh, G., Gehr, T., Mirman, M., Püschel, M., Vechev, M.,

    URL:https://www.sciencedirect.com/science/article/pii/ S002240490100041X, doi:https://doi.org/10.1016/S0022-4049(01) 00041-X. Singh, G., Gehr, T., Mirman, M., Püschel, M., Vechev, M.,

    work page doi:10.1016/s0022-4049(01

  17. [17]

    The ertificates for σ, τandστinQM(G fix)are computed using the algorithmCertificatefrom Weifeng et al

    (C.4) Additionally,στis also strictly positive overS(G fix). The ertificates for σ, τandστinQM(G fix)are computed using the algorithmCertificatefrom Weifeng et al. (2025). We multiplyτ gnat on both sides of equation(C.4)to obtainτ g nat =g 2 nat · στ+τ 2 ·q, for which the certificates are given explicitly. Multiplying both sides of equation(C.4)byg nat we...

    work page 2025