 ## Z Is Probably Not Existentially Definable over Q

In 1992 Barry Mazur formulated a series of conjectures which were to play an important role in the development of the subject (see [23-25]). One of the conjectures on the list was refuted in  but others are still open. Before we state two of the conjectures on the list, we need a definition.

Definition 3.4 (Affine Algebraic Sets and Varieties.) If {p1 (x1,...,xm),..., pk (x1,..., xm)} is a finite set of polynomial equations over some field K, then the set of common zeros of these polynomials in Km, where K is an algebraically closed field containing K, is called an algebraic set. An algebraic set which is irreducible, i.e. is not a union of non-empty distinct algebraic sets, is called a variety. Given a variety V defined over K and a subfield K0 of K we often consider V (K0) = V П K0.

Mazur’s conjectures on the topology of rational points are stated below:

Conjecture 3.1 (Topology of Rational Points) LetV be any variety over Q. Then the topological closure of V (Q) in V (R) possesses at most a finite number of connected components.

This conjecture had an unpleasant consequence.

Conjecture 3.2 There is no Diophantine definition of Z over Q.

Mazur’s conjecture also refers to projective varieties, but it is the affine variety case which has the most consequences for HTP over Q. We should also note that one can replace “variety” by “algebraic set” without changing the scope of the conjecture. (See Remark 11.1.2 of .) As a matter of fact, if Conjecture 3.1 is true, no infinite and discrete (in the Archimedean topology) set has a Diophantine definition over Q.

Quite a few years later Konigsmann  used different reasons to make a case that there is probably no Diophantine definition of Z over Q.

Since the plan to construct a Diophantine definition of Z over Q ran into substantial difficulties, alternative ways were considered for showing that HTP had no solution over Q. One of the alternative methods required construction of a Diophantine model of Z.

Definition 3.5 (Diophantine Model of Z) Let R be a recursive ring whose fraction field is not algebraically closed and let p : Z —> Rk be a recursive injection mapping Diophantine sets of Z to Diophantine sets of Rk. Then p is called a Diophantine model of Z over R.

Remark 3.1 (An Alternative Terminology from Model Theory) Model theorist have an alternative terminology for a map described above. They would translate the statement that R has a Diophantine model of Z as Z being existentially deflnably interpretable in R. (See Chap. 1, Sect. 3 of .)

It is not hard to see that sending Diophantine sets to Diophantine sets makes the map automatically recursive. The recursiveness of the map follows from the fact that the p-image of the graph of addition is Diophantine and therefore is recursively enumerable (by the same argument as over Z). Thus, we have an effective listing of the set Assume we have computed p(r — 1) for some positive integer r. Now start listing D+ until we come across a triple whose first two entries are p(r — 1) and p(1). The third element of the triple must be (p(r). We can simplify the requirements for the map further.

Proposition 3.4 If R is a recursive ring and p : Z —> Rk is injective for some k e Z>0, then p is a Diophantine model if and only if the images of the graphs of Z-addition and Z-multiplication are Diophantine over R.

This proposition can be proved by a straightforward induction argument which we do not reproduce here.

It quite easy to see that the following proposition holds.

Proposition 3.5 If R is a recursive ring with a Diophantine model of Z, then HTP has no solution over R.

Proof If R has a Diophantine model of Z, then R has undecidable Diophantine sets, and the existence of undecidable Diophantine sets over R leads us to the undecidability of HTP over R in the same way as it happened over Z. To show that R has undecidable Diophantine sets, let A c Z be an undecidable Diophantine set and suppose we want to determine whether an integer n e A. Instead of answering this question directly we can ask whether p(n) e p(A). By assumption p(n) is algorithmically computable. So if p(A) is a computable subset of R, we have a contradiction.

?