Existential Theories of Rings Connected with Hilbert’s Tenth Problem

Karim Zahidi

• Hilbert’s Tenth Problem (HTP) In 1900, Hilbert asked for a general method (algorithm) to determine whether an arbitrary Diophantine equation (i.e. a polynomial equation in several variables with coefficients in ℤ) has a solution or not in ℤ. This problem, also known as Hilbert’s Tenth Problem (it was problem nr. 10 on his famous list of 23 problems), was resolved negatively by Y. Matijasevich, building on work of mainly M. Davis, H. Putnam and J. Robinson. They proved that no such algorithm could exist. Since the negative solution to Hilbert’s Tenth Problem, various authors have considered an 0 of Hilbert’s Tenth Problem for various other rings.

• Diophantine sets Let R be a commutative domain and let L be a language which extends the language of rings, L_{R} = {0, 1, +, ×}, by finitely many constant symbols. A set D ⊂ R^{m} is called an L-Diophantine set if there exists a system of polynomial S(x_{1}, ..., x_{n}, a_{1}, ..., a_{m}) : f_{1}(x_{1}, ..., x_{n}, a_{1}, ..., a_{m}) = ... = f_{r}(x_{1}, ..., x_{n}, ..., a_{m}) = 0 where each of the polynomials has coefficients which can be built up from the constants in the language L by repeated addition and multiplication , such that

(a_{1}, ..., a_{m}) ∈ D ↔ (∃(x_{1}, ..., x_{n}) ∈ R^{n})(S(x_{1}, ..., x_{n}, a_{1}, ..., a_{m})) .

From a geometric point of view a set D is a L-Diophantine set if there exists an affine variety V (which is defined over the ring which is generated by the constants in the language L ) , such that D is a projection of V onto some of the variables. HTP for any commutative domain can now be reformulated as follows: given an arbitrary L_{R}-Diophantine set D ∈^{m}, can we decide whether an arbitrary point (a_{1}, ..., a_{m}) ∈ R^{m} belongs to D or not. Equivalently we can ask: ”Is the positive-existential theory of R in the language L decidable or not?”

• In this talk we want to present some results which concern Hilbert’s Tenth Problem for various other rings and fields. Several undecidability results are known for fields and rings of algebraic functions. These results are relevant for Hilbert’s Tenth Problem over the field of rational numbers Q (in our opinion the most important open problem in this area). We will also discuss a recent conjecture by Mazur on the topology of rational points of varieties and its relevance to Hilbert’s Tenth Problem for Q.

Address: Department of Applied Mathematics and Computer Science, University of Ghent, Krijgslaan 281, B-9000 Gent, Belgium

E-mail: Karim.Zahidi@rug.ac.be