Existential Models of Z over Big Rings
In 2003 Poonen [32] proved the first result on Diophantine undecidability (unsolvability of HTP) over a big subring of Q.
Theorem 3.4 There exist recursive sets of primes T and T2, both of natural density zero and with an empty intersection, such that for any set S of primes containing T and avoiding T2, the following hold:
- • Z has a Diophantine model over Oq,s.
- • Hilbert’s Tenth Problem is undecidable over Oqs.
Poonen used elliptic curves to prove his result but the model he constructed was very different from the one envisioned by the old elliptic curve plan we described earlier. Poonen modeled integers by approximation. The construction of the model does start with an elliptic curve of rank one
selected so that for a set of primes S, except possibly for finitely many points, the only multiples of a generator P that have their affine coordinates in the ring RS are in the sequence [±ii ] P = (xti, ±yti) with | ytj — j | < 10-j. We remind the reader that we know how to define positive numbers using a variation on Lagrange’s theme (Proposition 3.6) and how to get rid of a finite set of undesirable values such as points of finite order (just say “=” as in Proposition 3.6 again). We claim that у : j —> yij is a Diophantine model of Z>0. In other words, setting D = j (Z), we claim that у is an injection, and D, as well as the following sets, is Diophantine over RS:
and
(Note that if D+ and D2 are Diophantine, then Dx = {(yei, ytj, yit) e D3 : k = ij, k, i, j e Z>0} is also Diophantine since xy = 1 ((x + y)2 — x2 — y2).) It is easy to show that
and with the help of Lagrange this makes D+ Diophantine. Similarly we have that
implying that D2 is Diophantine.
To restrict the number of solutions to the elliptic curve equation, Poonen’s construction relied to a large extent on the fact that the denominators of the coordinates of points on an elliptic curve which are multiples of a single point form a divisibility sequence: an integer sequence {an} is called a divisibility sequence if nm implies anam (see Chaps. 4 and 10 of [14] for a discussion of such sequences and seethe discussion of the formal group of an elliptic curve in Chap.4 of [61] for an explanation of why the denominators form a divisibility sequence).
Poonen’s method was further extended by Eisentrager and Everest [10], Perlega [29] and finally by Eisentrager et al. [11]. The theorem proved in [11] provides a “covering” of Q by big rings where HTP is undecidable.
Theorem 3.5 (Eisentrager, Everest, Shlapentokh) For any finite set of positive computable real numbers (i.e. real numbers that are limits of computable sequences of rational numbers) r1,...,rk such that r + --- + rk = 1 we can partition the set of all (rational) primes into sets Pi,..., Pk such that the natural density of each Pi is ri, each ring RPi has a Diophantine model of Z and therefore HTP is undecidable over each RPi.
The author also constructed a model of Z using Diophantine equivalence classes (a class model of Z) over a big ring using the old idea of trying to make multiplication of indices Diophantine in [60].
Theorem 3.6 Let E be an elliptic curve defined and of rank one over Q. Let P be a generator of E (Q) modulo the torsion subgroup, and fix an affine (Weierstrass) equation for E of the form y2 = x3 + ax + b, with a, b e Z. If (xn, yn) are the coordinates of [n] P with n = 0 derived from this (Weierstrass) equation, then there exists a set of primes W of natural density one, and a positive integer m0 such that the following set П c RlW is Diophantine over RW.
