An Elementary Recursive Bound for Effective Positivstellensatz and Hilbert’s 17th problem

DOI10.1090/MEMO/1277zbMath1465.14001arXiv1404.2338OpenAlexW3009355061MaRDI QIDQ5108709

Henri Lombardi, Daniel Perrucci, Marie-Françoise Roy

Publication date: 6 May 2020

Published in: Memoirs of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1404.2338

zbMATH Keywords

quantifier eliminationconstructive mathematicsHilbert's 17th problemincompatibilitypositivstellensatzweak existencerealisabilityThom encodingreal nullstellensatzelementary recursive bounds on degreesweak inference

Mathematics Subject Classification ID

Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15) Research exposition (monographs, survey articles) pertaining to algebraic geometry (14-02) Other constructive mathematics (03F65) Real algebraic and real-analytic geometry (14P99) Real algebra (13J30)

Related Items (13)

Positivity certificates and polynomial optimization on non-compact semialgebraic sets ⋮ Sums of squares on the hypercube ⋮ Certifying the global optimality of quartic minimization over the sphere ⋮ Unnamed Item ⋮ Testing hyperbolicity of real polynomials ⋮ On the effective Putinar's Positivstellensatz and moment approximation ⋮ On the complexity of testing attainment of the optimal value in nonlinear optimization ⋮ Théories géométriques pour l’algèbre des nombres réels ⋮ On sum of squares certificates of non-negativity on a strip ⋮ Unnamed Item ⋮ On exact Reznick, Hilbert-Artin and Putinar's representations ⋮ On Łojasiewicz inequalities and the effective Putinar's Positivstellensatz ⋮ Absolute concentration robustness: algebra and geometry

Cites Work

• Sums of squares on the hypercube
• Elementary recursive quantifier elimination based on Thom encoding and sign determination
• Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets
• Solving systems of polynomial inequalities in subexponential time
• Real quantifier elimination is doubly exponential
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• Complexity of deciding Tarski algebra
• Effective Nullstellensatz for arbitrary ideals
• Local reality on algebraic varieties
• Anneaux preordonnes
• Zero-nonzero and real-nonreal sign determination
• A nullstellensatz for ordered fields
• A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
• On the effective Nullstellensatz
• A new decision method for elementary algebra
• Spécialisation de la suite de Sturm et sous-résultants (I)
• Local Diophantine Nullstellen Inequalities
• On the combinatorial and algebraic complexity of quantifier elimination
• Generalizing Cramer's Rule: Solving Uniformly Linear Systems of Equations
• Decision procedures for real and p‐adic fields
• Algorithms in real algebraic geometry
• Dynamical method in algebra: Effective Nullstellensätze
• Complexity of Null- and Positivstellensatz proofs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An Elementary Recursive Bound for Effective Positivstellensatz and Hilbert’s 17th problem