We present some new and recent algorithmic results concerning polynomial system solving over various rings. In particular, we present some of the best recent bounds on: (a) the complexity of calculating the complex dimension of an algebraic set, (b) the height of the zero-dimensional part of an algebraic set over C, and (c) the number of connected components of a semi-algebraic set. We also present some results which significantly lower the complexity of deciding the emptiness of hypersurface intersections over C and Q, given the truth of the Generalized Riemann Hypothesis. Furthermore, we state some recent progress on the decidability of the prefixes and , quantified over the positive integers. As an application, we conclude with a result connecting Hilbert's Tenth Problem in three variables and height bounds for integral points on algebraic curves. This paper is based on three lectures presented at the conference corresponding to this proceedings volume. The titles of the lectures were Some Speed-Ups in Computational Algebraic Geometry,'' Diophantine Problems Nearly in the Polynomial Hierarchy,'' and Curves, Surfaces, and the Frontier to Undecidability.''
As for more general relations between @math and its analogue over @math , it is easy to see that the decidability of @math implies the decidability of its analogue over @math . Unfortunately, the converse is currently unknown. Via Lagrange's Theorem (that any positive integer can be written as a sum of four squares) one can easily show that the un decidability of @math implies the un decidability of the analogue of @math over @math . More recently, Zhi-Wei Sun has shown that the @math can be replaced by @math @cite_12 .
@cite_12
2159229515
Let ∃n denote the set of all formulas ∃x1…∃xn[P(x1, …,xn) = 0], where P is a polynomial with integer coefficients. We prove a new relation-combining theorem from which it follows that if ∃n is undecidable over N, then ∃2n+2 is undecidable over Z.