Properties of Diophantine Sets
Over many rings Diophantine sets have several simple but useful properties. First of all, over any domain a union of finitely many Diophantine sets is Diophantine. (A product of finitely many Diophantine definitions is a Diophantine definition of a union.) With a little bit of effort one can also show that as long as the fraction field of the domain in question is not algebraically closed, an intersection of finitely many Diophantine sets is Diophantine. Let h(T) = a0 + a1 T + ???+ anTn be a polynomial without roots in the fraction field, and let f (t, x), g(t, x) be Diophan- tine definitions of some subsets of the ring. In this case, it is not hard to see that the polynomial Xn=0 aif'gn-' has roots in the fraction field if and only if f (t, x) and g(t, x) have common roots in the field. The intersection of Diophantine sets being Diophantine is related to another important aspect of Diophantine equations over domains with fraction fields not algebraically closed: a finite system of equations is always equivalent to a single equation in the sense that both the system and the equation have the same solutions over the domain in question and in the sense that given a finite system of equations, the equivalent equation can be constructed effectively. We can use this property of finite systems to give more latitude to our
Diophantine definitions, i.e. we can let the Diophantine definitions over rings whose fraction fields are not algebraically closed consist of several polynomials without changing the nature of the relation.
Over Z (and many other rings) we have additional methods for writing Diophan- tine definitions. One surprisingly useful tool for writing Diophantine definitions has to do with an elementary property of GCD’s (greatest common divisors).
Proposition 3.1 If a, b e Z=0 with (a, b) = 1 then there exist x, y e Z such that ax + by = 1.
The GCD’s can be used to show that the set of non-zero integers is Diophantine and thus allow us to require that values of variables are not equal, as well as to perform “division” as will be shown later. On a more theoretical level we can say that the positive existential theory of Z is the same as the existential theory of Z.
Proposition 3.2 The set of non-zero integers has the following Diophantine definition over Z:
Proof If t = 0, then either 2u — 1 = 0 or 3v — 1 = 0 has a solution in Z, which is impossible. Suppose now t = 0. Write t = t2t3, where t2 is odd and t3 ф 0 mod 3. Since (t2, 2) = 1 and (t3, 3) = 1, by a property of GCD there exist u, xu, v, xv e Z such that
Thus (2u — 1)(3v — 1) = t2xut3xv = t(xuxv). ?
Another important Diophantine definition allows us to convert inequalities into equations.
Lemma 3.1 (Diophantine definition of the set of non-negative integers) From Lagrange’s Theorem we get the following representation of non-negative integers:
Before we proceed further with our discussion of HTP over Q we would like to point out that it is not hard to see that decidability of HTP over Z would imply decidability of HTP for Q. Indeed, suppose we knew how to determine whether solutions exist over Z. If Q(x,..., xk) is a polynomial with integer coefficients, then
where we remind the reader we can rewrite z1. ..zk = 0 as a polynomial equation and convert the resulting finite system of equations into a single one. So if we can determine whether the resulting equation had solutions over Z, we can determine whether the original equation had solutions over Q.
Unfortunately, the reverse implication does not work: we don’t know of any easy way to derive the undecidability of HTP over Q from the analogous result over integers.
The fact that we can rewrite equations over Q as equations over Z is a specific instance of a more general phenomenon playing an important part in a discussion below.
Proposition 3.3 If the set of non-zero elements of an integral domain R has a Dio- phantine definition over R, A is a Diophantine subset of F, the fraction field of R, and F is not algebraically closed, then A n R has a Diophantine definition over R.
Proof We sketch the main idea of a proof. Rewrite the variables ranging over F as ratios of variables ranging over R with a proviso that the denominator variables are not 0. Then clear all the denominators. ? 18.104.22.168 Using a Diophantine Definition of Z to Show Undecidability
One of the earliest methods suggested for showing that HTP was undecidable over Q used Diophantine definitions. This idea can be summarized in the following lemma where the setting is somewhat more general. First we formally define recursive rings.
Definition 3.3 A countable ring is said to be recursive (or computable) if there exists a bijection j : R —> Z^0 such that the j -images of the graphs of R-addition and R-multiplication are recursive subsets of Z^0.
Lemma 3.2 Let R be a recursive ring of characteristic 0 (or in other words, a ring containing Z as a subring) with a fraction field not algebraically closed. If Z has a Diophantine definition p(T, X) over R, then HTP is not decidable over R.
Proof Let h (Ti, ...,Tl) be a polynomial with rational integer coefficients and consider the following system of equations.
It is easy to see that h(T1, ) = 0 has solutions in Z if and only if system (3.1)
has solutions in R. Thus if HTP is decidable over R, it is decidable over Z. ?
Unfortunately, the Diophantine definition plan for Q quickly ran into problems.