Algorithms for Testing Membership in Univariate Quadratic Modules over the Reals

Quadratic modules in real algebraic geometry are akin to polynomial ideals in algebraic geometry, and have been found useful in the theory of Positivstellensatz to study Hilbert's 17th problem. Algorithms are presented in this paper for testing membership in univariate finitely generated quadratic modules over the reals and inclusion of two finitely generated quadratic modules. For a univariate unbounded quadratic module, an explicit upper bound on the degrees of sums of squares to construct any given polynomial is proved and then used to design an algorithm for testing membership in such a quadratic module. For a bounded quadratic module, a unique signature is associated with it based on the real values on which its finite basis is non-negative, and the signatures are used to furnish a criterion for inclusion of two finitely generated quadratic modules and a corresponding algorithm which solves the membership problem as a special case. It is also shown that a bounded quadratic module can be transformed to an equivalent one with two generators with an algorithm for performing this transformation. All the presented algorithms have been implemented.