HILBERT’S TENTH PROBLEM AND MAZUR’S CONJECTURE FOR LARGE SUBRINGS OF ℚ

BJORN POONEN

Abstract. We give the first examples of infinite sets of primes S such that Hilbert’s Tenth Problem over ℤ[S^{−1}] has a negative answer. In fact, we can take S to be a density 1 set of primes. We show also that for some such S there is a punctured elliptic curve E′ over ℤ[S^{−1}] such that the topological closure of E′(ℤ[S^{−1}]) in E′(ℝ) has infinitely many connected components.

1. Introduction

Hilbert’s Tenth Problem, in modern terms, was to find an algorithm (Turing machine) to decide, given a polynomial equation f(x_{1}, …, x_{n}) = 0 with coefficients in ℤ, whether it has a solution with x_{1}, …, x_{n} ∈ ℤ. Y. Matijasevič [Mat70], building on earlier work of M. Davis, H. Putnam, and J. Robinson [DPR61], showed that no such algorithm exists. If one replaces ℤ in both places by a different commutative ring R (let us assume its elements can be and have been encoded for input into a Turing machine), one obtains a different question, called Hilbert’s Tenth Problem over R, whose answer depends on R. These problems are discussed in detail in [DLPVG00].

In particular, the answer for R = ℚ is unknown. Hilbert’s Tenth Problem over ℚ is equivalent to the general problem of deciding whether a variety over ℚ has a rational point. One approach to proving that Hilbert’s Tenth Problem over ℚ has a negative answer would be to deduce this from Matijasevič’s theorem for ℤ, by showing that ℤ is diophantine over ℚ in the following sense:

Definition 1.1. Let R is a ring, and A ⊆ R^{m}. Then A is diophantine over R if and only if there exists a polynomial f in m + n variables with coefficients in R such that

A = { a ∈ R^{m} | ∃x ∈ R^{n} such that f(a, x) = 0 }.

On the other hand, Mazur conjectures that if X is a variety over ℚ, then the topological closure of X(ℚ) in X(ℝ) has only finitely many components [Maz92],[Maz95]. This would imply that ℤ is not diophantine over ℚ. More generally, Cornelissen and Zahidi [CZ00] have shown that Mazur’s Conjecture implies that there is no diophantine model of ℤ over ℚ.

Definition 1.2. A diophantine model of ℤ over ℚ is a set A ⊆ ℚ^{n} that is diophantine over ℚ with a bijection ℤ → A under which the graphs of addition and multiplication on ℤ correspond to subsets of A^{3} ⊆ ℚ^{3n} that are diophantine over ℚ.

Date: June 14, 2003.

2000 Mathematics Subject Classification. Primary 11U05; Secondary 11G05.

Key words and phrases. Hilbert’s Tenth Problem, elliptic curve, Mazur’s Conjecture, diophantine definition.

This research was supported by NSF grant DMS-0301280, and a Packard Fellowship.

This is important, because the existence of such a diophantine model, together with Matijasevič’s Theorem, would imply a negative answer for Hilbert’s Tenth Problem over ℚ.

This paper studies Hilbert’s Tenth Problem over rings between ℤ and ℚ. Such rings are in bijection with subsets of the set P of prime numbers. Namely, given S ⊆ P, one has the ring ℤ[S^{−1}], and conversely, given a subring R between ℤ and ℚ, one has R = ℤ[S^{−1}] where S = P ∩ R^{×}.

Using quadratic forms as in J. Robinson’s work, one can show that for any prime p the ring ℤ_{(p)} of rational numbers with denominators prime to p is diophantine over ℚ [KR92, Proposition 3.1]. A short argument using this shows that for finite S, Hilbert’s Tenth Problem over ℤ[S^{−1}] has a negative answer.

In this paper, we give the first examples of infinite subsets S of P for which Hilbert’s Tenth Problem over ℤ[S^{−1}] has a negative answer. In fact, we show that there exist such S of natural density 1, so in one sense, we are approaching a negative answer for ℚ. (See Section 6 for the definition of natural density.) Previously, Shlapentokh proved that if K is a totally real number field or a totally complex degree-2 extension of a totally real number field, then there exists a set of places S of K of Dirichlet density arbitrarily close to 1 − [K : ℚ]^{−1} such that if O_{K,S} is the subring of elements of K that are integral at all places outside S, then Hilbert’s Tenth Problem over O_{K,S} has a negative answer [Shl97],[Shl00],[Shl02]. But for K = ℚ, this gives nothing beyond Matijasevič’s Theorem.

More generally, we prove the following:

Theorem 1.3. There exist disjoint recursive sets of primes T_{1} and T_{2}, both of natural density 0, such that for any set S of primes containing T_{1} and disjoint from T_{2}, the following hold:

(1) There exists an affine curve E′ over ℤ[S^{−1}] such that the topological closure of E′(ℤ[S^{−1}]) in E′(ℝ) is an infinite discrete set.

(2) The set of positive integers with addition and multiplication admits a diophantine model over ℤ[S^{−1}].

(3) Hilbert’s Tenth Problem over ℤ[S^{−1}] has a negative answer.

Remark 1.4.

(i) Arguably (3) is the most important of the three parts. We have listed the parts in the order they will be proved.

(ii) A subset T ⊆ ℤ is recursive if and only if there exists an algorithm (Turing machine)

that takes as input an integer t and outputs YES or NO according to whether t ∈ T. (iii) We use natural density instead of Dirichlet density in order to have a slightly stronger

statement. See [Ser73, VI.4.5] for the definition of Dirichlet density and its relation to natural density.

Previously, Shlapentokh [Shl03] used norm equations to prove that there exist sets S ⊆ P of Dirichlet density arbitrarily close to 1 for which there exists an affine variety X over ℤ[S^{−1}] such that the closure of X(ℤ[S^{−1}]) in X(ℝ) has infinitely many connected components. (She also proved an analogous result for localizations of the ring of integers of totally real number fields and totally complex degree-2 extensions of totally real number fields. For number fields with exactly one conjugate pair of nonreal embeddings, she obtained an analogous result, but with density only 1/2.)

Question 4.1 of [Shl03] asked whether over ℚ one could do the same for some S ⊆ P of Dirichlet density exactly 1. Part (1) of our Theorem 1.3 gives an affirmative answer (take S = P − T_{2}). In fact, it was the attempt to answer Shlapentokh’s Question 4.1 that inspired this paper, so the author thanks her for asking the right question.

The rest of this paper is devoted to proving Theorem 1.3. The strategy is to take an elliptic curve E over ℚ such that E(ℚ) is generated by one point P of infinite order, and to construct T_{1} (resp. T_{2}) so that certain prime multiples (resp. at most finitely many other integer multiples) of P have coordinates in ℤ[S^{−1}]. Using Vinogradov’s result on the equidistribution of the prime multiples of an irrational number modulo 1, we can prescribe the approximate locations of the prime multiples of P in E(ℝ). If we prescribe them so that their y-coordinates approximate the set of positive integers sufficiently well, then approximate addition and approximate squaring on the set A of these y-coordinates make A into a diophantine model of the positive integers.

Shlapentokh and the author plan eventually to write a joint paper generalizing Theorem 1.3 to other number fields, and to places other than the real place.

2. Elliptic curve setup

Let E be an elliptic curve over ℚ of rank 1. To simplify the arguments, we will assume moreover that E(ℚ) ≃ ℤ, that E(ℝ) is connected, and that E does not have complex multiplication. For example, these conditions hold for the smooth projective model of y^{2} = x^{3} + x + 1. Let P be a generator of E(ℚ). Fix a Weierstrass equation y^{2} = x^{3} + ax + b for E, where a, b ∈ ℤ.

Let E′ = Spec ℤ[S_{bad}^{−1}][x, y]/(y^{2} − (x^{3} + ax + b)), where S_{bad} is a finite set of primes such that E′ is smooth over ℤ[S_{bad}^{−1}]. In particular, 2 ∈ S_{bad}. Enlarge S_{bad} if necessary so that P ∈ E′(ℤ[S_{bad}^{−1}]).

3. Denominators of x-coordinates

For nonzero n ∈ ℤ, let d_{n} ∈ ℤ_{>0} be the prime-to-S_{bad} part of the denominator of x(nP); that is, d_{n} is the product one obtains if one takes the prime factorization of the denominator of x(nP) and omits the powers of primes in S_{bad}. Define d_{0} = 0. The notation m | n means n ∈ mℤ.

Lemma 3.1.

(a) For any r ∈ ℤ, the set { n ∈ ℤ : r | d_{n} } is a subgroup of ℤ.

(b) There exists c ∈ ℝ_{>0} such that log d_{n} = (c−o(1))n^{2} as n → ∞ (cf. [Sil88, Lemma 8]).

Proof. (a) We may reduce to the case where r = p^{e} for some prime p ∉ S_{bad} and e ∈ ℤ_{>0}. Thus it suffices to show that the set E_{e} := { Q ∈ E(ℚ_{p}) : v_{p}(x(Q)) ≤ −e } ∪ {O} is a subgroup of E(ℚ_{p}), where v_{p}: ℚ_{p}^{∗} → ℤ is the p-adic valuation. The set E_{1} is the kernel of the reduction map E(ℚ_{p}) → E(𝔽_{p}) (extend E to a smooth proper curve over ℤ_{p} to make sense of this). Since p > 2, the formal logarithm λ: E_{1} → pℤ_{p} is an isomorphism [Sil92, IV.6.4]. By [Sil92, IV.5.5, IV.6.3], v_{p}(λ(Q)) = v_{p}(z(Q)) for all Q ∈ E_{1}, where z = −x/y is the standard parameter for the formal group. By [Sil92, pp. 113–114], x = −2z^{−2}+⋯ ∈ ℤ_{p}((z)), so v_{p}(x(Q)) = −2v_{p}(z(Q)) = −2v_{p}(λ(Q)). Thus G_{e} corresponds under λ to p^{⌈e/2⌉}ℤ_{p}, and is hence a subgroup.

(b) The number log d_{n} is the logarithmic height h(nP), except that in the sum defining the height, the terms corresponding to places in S_{bad} ∪ {∞} have been omitted. A standard diophantine approximation result (see Section 7.4 of [Ser97]) implies that each such term contributes at most a fraction o(1) of the height, as n → ∞. If ĥ is the canonical height, then h(nP) = ĥ(nP) + O(1) = ĥ(P)n^{2} + O(1). Take c = ĥ(P), which is positive, since P is not torsion. □

Remark 3.2. The bottom of p. 306 in [Aya92] relates the denominators of x(nP) in lowest terms to the sequence of values of division polynomials evaluated at P. The study of divisibility properties of the latter sequence is very old: results were claimed in the 19^{th} century by Lucas (but apparently not published), and proofs were given in [War48].

For n ∈ ℤ, let S_{n} be the set of prime factors of d_{n}. If m, n ∈ ℤ, then (m, n) denotes their greatest common divisor.

Corollary 3.3. If m, n ∈ ℤ, then S_{(m,n)} = S_{m} ∩ S_{n}. In particular, if (m, n) = 1, then S_{m} and S_{n} are disjoint.

Proof. Lemma 3.1(a) implies the first statement. Since P ∈ E′(ℤ[S_{bad}^{−1}]), we have S_{1} = ∅, and the second statement follows. □

Lemma 3.4. If ℓ and m are primes, and max{ℓ, m} is sufficiently large, then S_{ℓm}−(S_{ℓ}∪S_{m}) is nonempty.

Proof. If p | d_{m}, or equivalently v_{p}(x(mP)) < 0, then using the formal logarithm λ as in the proof of Lemma 3.1(a) we obtain

v_{p}(d_{ℓm}) = −v_{p}(x(ℓmP)) = 2v_{p}(λ(ℓmP)) = 2v_{p}(ℓλ(mP)) = v_{p}(ℓ^{2}d_{m}).

If S_{ℓm} − (S_{ℓ} ∪ S_{m}) were empty, then for each p | d_{ℓm} we could apply either this result or the analogue with ℓ and m interchanged, and hence deduce d_{ℓm} | ℓ^{2}m^{2}d_{ℓ}d_{m}. This contradicts Lemma 3.1(b) if max{ℓ, m} is sufficiently large. □

Remark 3.5. Our Lemma 3.4 is a special case of Lemma 9 of [Sil88] (except for the minor differences that [Sil88] requires E to be in minimal Weierstrass form and considers the full denominator instead of its prime-to-S_{bad} part). The method of proof is the same. These results may viewed as elliptic analogues of Zsigmondy’s Theorem: see [Eve02].

4. Definition of T_{1} and T_{2}

For each prime number ℓ, let a_{ℓ} be the smallest a ∈ ℤ_{>0} such that d_{ℓ^{a}} > 1. By Lemma 3.1(b), a_{ℓ} exists, and a_{ℓ} = 1 for all ℓ outside a finite set L of primes. Baker’s method [Ser97, Chapter 8] lets us compute the finite set E′(ℤ[S_{bad}^{−1}]), so the set L and the values a_{ℓ} for ℓ ∈ L are computable.

Let p_{ℓ} = max S_{ℓ^{a}} where a = a_{ℓ}. For primes ℓ and m (possibly equal), Lemma 3.4 lets us define p_{ℓm} = max (S_{ℓm} − (S_{ℓ} ∪ S_{m})) when max{ℓ, m} is sufficiently large. Let ℓ_{1} < ℓ_{2} < … be a sequence of primes outside L. (The ℓ_{i} will be constructed in Section 7 with certain properties, but for now these properties are not relevant.) The plan will be to force ℓ_{i}P ∈ E′(ℤ[S^{−1}]) for all i, by requiring each S_{ℓ_{i}} to be contained in S. On the other hand, we must require other primes to lie outside S to make sure that not too many other multiples of P end up in E′(ℤ[S^{−1}]).

Let T_{1} = S_{bad} ∪ ⋃_{i≥1} S_{ℓ_{i}}. Let T_{2}^{a} be the set of p_{ℓ} for all primes ℓ ∉ {ℓ_{1}, ℓ_{2}, … }. If ℓ_{1} is sufficiently large, we may define T_{2}^{b} = { p_{ℓ_{i}ℓ_{j}} : 1 ≤ j ≤ i } and T_{2}^{c} = { p_{ℓℓ_{i}} : ℓ ∈ L, i ≥ 1 }. Finally, let T_{2} = T_{2}^{a} ∪ T_{2}^{b} ∪ T_{2}^{c}.

5. Properties of T_{1} and T_{2}

Proposition 5.1. The sets T_{1} and T_{2} are disjoint.

Proof. By definition of p_{ℓ} and p_{ℓm}, S_{bad} ∩T_{2} = ∅. If ℓ ≠ ℓ_{i}, then (ℓ^{a_{ℓ}}, ℓ_{i}) = 1, so Corollary 3.3 implies p_{ℓ} ∉ S_{ℓ_{i}}. Thus T_{1} ∩ T_{2}^{a} = ∅. If i ∉ {j, k}, then Corollary 3.3 implies p_{ℓ_{j}ℓ_{k}} ∉ S_{ℓ_{i}}, while if i ∈ {j, k} then p_{ℓ_{j}ℓ_{k}} ∉ S_{ℓ_{i}} by definition of p_{ℓ_{j}ℓ_{k}}. Thus T_{1} ∩ T_{2}^{b} = ∅. If i ≠ j, then Corollary 3.3 implies p_{ℓℓ_{j}} ∉ S_{ℓ_{i}}, while if i = j, then p_{ℓℓ_{i}} ∉ S_{ℓ_{i}} by definition of p_{ℓ_{j}ℓ_{k}}. Thus T_{1} ∩ T_{2}^{c} = ∅. □

Proposition 5.2. If S contains T_{1} and is disjoint from T_{2}, then E′(ℤ[S^{−1}]) is the union of { ±ℓ_{i}P : i ≥ 1 } and some subset of the finite set { rP : r | ∏_{ℓ∈L} ℓ^{a_{ℓ}−1} }.

Proof. Because the equation of E relates the x- and y-coordinates, a point nP belongs to E′(ℤ[S^{−1}]) if and only if S_{n} ⊆ S. In particular, S_{ℓ_{i}} ⊆ T_{1} ⊆ S, so ±ℓ_{i}P ∈ E′(ℤ[S^{−1}]).

Any point outside

{ ±ℓ_{i}P : i ≥ 1 } ∪ { rP : r | ∏_{ℓ∈L} ℓ^{a_{ℓ}−1} }

is nP for some n divisible by one of the following:

• ℓ^{a_{ℓ}} for some ℓ not in the sequence ℓ_{1}, ℓ_{2}, …,

• ℓ_{i}ℓ_{j} for some 1 ≤ j ≤ i, or
• ℓℓ_{i} for some ℓ ∈ L and i ≥ 1.

Lemma 3.1(a) implies then that S_{n} contains a prime of T_{2}^{a}, T_{2}^{b}, or T_{2}^{c}, respectively, so S_{n} ⊈ S. □

6. Natural density

The natural density of a subset T ⊆ P is defined as

lim_{X→∞} \frac{#\{p ∈ T : p ≤ X\}}{#\{p ∈ P : p ≤ X\}},

if the limit exists. One defines upper natural density similarly, using lim sup instead of lim.

Lemma 6.1. If α ∈ ℝ − ℚ, then { ℓα mod 1 : ℓ is prime } is equidistributed in [0, 1]. That is, for any interval I ⊆ [0, 1], the set of primes ℓ for which (ℓα mod 1) belongs to I has natural density equal to the length of I.

Proof. See p. 180 of [Vin54]. □

Let y(ℓP) ∈ ℚ denote the y-coordinate of ℓP ∈ E(ℚ).

Corollary 6.2. If I ⊆ ℝ is an interval with nonempty interior, then the set of primes ℓ for which y(ℓP) ∈ I has positive natural density.

Proof. Since E(ℝ) is a connected compact 1-dimensional Lie group over ℝ, we can choose an isomorphism E(ℝ) → ℝ/ℤ as topological groups. Since P is of infinite order, its image in ℝ/ℤ is represented by an irrational number. The subset of E(ℝ) having y-coordinate in I corresponds to a nontrivial interval in ℝ/ℤ. Now apply Lemma 6.1. □

7. Construction of the ℓ_{i}

For prime ℓ, define

μ_{ℓ} = sup_{X∈ℤ_{≥2}} \frac{#\{p ∈ S_{ℓ} : p ≤ X\}}{#\{p ∈ P : p ≤ X\}}.

The supremum is attained for some X ≤ max S_{ℓ}, so μ_{ℓ} is computable for each ℓ.

Lemma 7.1. For any ϵ > 0, the natural density of { ℓ : μ_{ℓ} > ϵ } is 0.

Proof. For X ∈ ℝ, let π(X) := #{p ∈ P : p ≤ X}. If ℓ is a prime and μ_{ℓ} > ϵ, then we can choose X_{ℓ} ∈ ℤ_{≥2} such that

\frac{#\{p ∈ S_{ℓ} : p ≤ X_{ℓ}\}}{π(X_{ℓ})} > ϵ.

For M ∈ ℤ_{≥2}, let U_{M} be the set of primes ℓ such that μ_{ℓ} > ϵ and X_{ℓ} ∈ [M, 2M). If ℓ ∈ U_{M}, then

#{p ∈ S_{ℓ} : p ≤ 2M} ≥ #{p ∈ S_{ℓ} : p ≤ X_{ℓ}} > ϵπ(X_{ℓ}) ≥ ϵπ(M).

But the S_{ℓ} are disjoint by Corollary 3.3, so

π(2M) ≥ ∑_{ℓ∈U_{M}} #{p ∈ S_{ℓ} : p ≤ 2M} ≥ ϵπ(M)#U_{M}.

Thus by the Prime Number Theorem, #U_{M} = O(1) as M → ∞. If 2^{k−1} ≤ N < 2^{k}, then

#{ ℓ : μ_{ℓ} > ϵ and X_{ℓ} ≤ N } ≤ #U_{2} + #U_{4} + #U_{8} + ⋯ + #U_{2^{k}} = O(k) = O(log N)

as N → ∞. If μ_{ℓ} > ϵ then by definition of X_{ℓ},

π(X_{ℓ}) < \frac{#S_{ℓ}}{ϵ} ≤ \frac{log_{2} d_{ℓ}}{ϵ} = O(ℓ^{2})

as ℓ → ∞ by Lemma 3.1(b), so X_{ℓ} = O(ℓ^{2} log ℓ) by the Prime Number Theorem. Combining the previous two sentences shows that

#{ ℓ ≤ Y : μ_{ℓ} > ϵ } = #{ ℓ ≤ Y : μ_{ℓ} > ϵ and X_{ℓ} ≤ O(Y^{2} log Y) }
= O(log O(Y^{2} log Y)),

which is o(π(Y)) as Y → ∞. □

Define the ℓ_{i} inductively as follows. Given ℓ_{1}, …, ℓ_{i−1}, let ℓ_{i} be the smallest prime outside L such that all of the following hold:

(1) ℓ_{i} > ℓ_{j} for all j < i,

(2) μ_{ℓ_{i}} ≤ 2^{−i},

(3) p_{ℓ_{i}ℓ_{j}} > 2^{i} for all j ≤ i,

(4) p_{ℓℓ_{i}} > 2^{i} for all ℓ ∈ L, and

(5) |y(ℓ_{i}P) − i| ≤ 1/(10i).

Proposition 7.2. The sequence ℓ_{1}, ℓ_{2}, … is well-defined and computable.

Proof. By induction, we need only show that for each i, there exists ℓ_{i} as above. By Corollary 6.2, the set of primes satisfying (5) has positive natural density. By Lemma 7.1, (2) fails for a set of natural density 0. Therefore it will suffice to show that (1), (3), and (4) are satisfied by all sufficiently large ℓ_{i}.

For fixed j ≤ i, the primes p_{ℓ_{i}ℓ_{j}} for varying values of ℓ_{i} are distinct by Corollary 3.3, so eventually they are greater than 2^{i}. The same holds for p_{ℓℓ_{i}} for fixed ℓ ∈ L. Thus by taking ℓ_{i} sufficiently large, we can make all the p_{ℓ_{i}ℓ_{j}} and p_{ℓℓ_{i}} greater than 2^{i}.

Each ℓ_{i} can be computed by searching primes in increasing order until one is found satisfying the conditions. □

8. Recursiveness of T_{1} and T_{2}

The set {ℓ_{1}, ℓ_{2}, … } is recursive, since it is a strictly increasing sequence whose terms can be computed in order. This is needed for the proofs in this section.

Proposition 8.1. The set T_{1} is recursive.

Proof. Since S_{bad} is finite, it suffices to give an algorithm for deciding whether a prime p ∉ S_{bad} belongs to ⋃_{i≥1} S_{ℓ_{i}}. We have p ∈ ⋃_{i≥1} S_{ℓ_{i}} if and only if p | d_{ℓ_{i}} for some i, which holds if and only if the order n_{p} of the image of P in E(𝔽_{p}) divides ℓ_{i} for some i. The order n_{p} can be computed, and n_{p} ≠ 1, since P ∈ E′(ℤ[S_{bad}^{−1}]). So we simply check whether n_{p} ∈ {ℓ_{1}, ℓ_{2}, … }. □

Lemma 8.2. If ℓ is prime, then ℓ | #E(𝔽_{p_{ℓ}}).

Proof. By definition of p_{ℓ}, the point ℓ^{a_{ℓ}}P reduces to 0 in E(𝔽_{p_{ℓ}}) but ℓ^{a_{ℓ}−1}P does not. □

Proposition 8.3. The set T_{2}^{a} is recursive.

Proof. If p ∈ T_{2}^{a}, then p = p_{ℓ} for some ℓ ∉ {ℓ_{1}, ℓ_{2}, … }, and then ℓ | #E(𝔽_{p}) by Lemma 8.2. Therefore to test whether a prime p ∉ S_{bad} belongs to T_{2}^{a}, compute #E(𝔽_{p}) and its prime factors: one has p ∈ T_{2}^{a} if and only if there is a prime factor ℓ such that ℓ ∉ {ℓ_{1}, ℓ_{2}, … } and p_{ℓ} = p. □

Proposition 8.4. The sets T_{2}^{b} and T_{2}^{c} are recursive.

Proof. By condition (3) in the definition of ℓ_{i}, if a prime p belongs to T_{2}^{b}, it must equal p_{ℓ_{i}ℓ_{j}} for some 1 ≤ j ≤ i with 2^{i} < p. Thus to test whether a prime p belongs to T_{2}^{b}, simply compute p_{ℓ_{i}ℓ_{j}} for 1 ≤ j ≤ i < log_{2} p.

The proof that T_{2}^{c} is recursive is similar, using condition (4). □

Thus T_{1} and T_{2} are recursive.

9. The densities of T_{1} and T_{2}

Proposition 9.1. The set T_{1} has natural density 0.

Proof. For fixed r ∈ ℤ_{>0}, the set ⋃_{i>r} S_{ℓ_{i}} differs from T_{1} in only finitely many primes, so it suffices to show that the former has upper natural density tending to 0 as r → ∞. By definition of μ_{ℓ_{i}}, the upper natural density is bounded by ∑_{i>r} μ_{ℓ_{i}} ≤ ∑_{i>r} 2^{−i} = 2^{−r}, which tends to 0 as r → ∞. □

Proposition 9.2. The sets T_{2}^{b} and T_{2}^{c} have natural density 0.

Proof. Suppose 2^{m} ≤ X < 2^{m+1}. By condition (3) defining ℓ_{i}, the only primes of the form p_{ℓ_{i}ℓ_{j}} that might be ≤ X are those with 1 ≤ j ≤ i ≤ m. There are at most O(m^{2}) = O((log X)^{2}) of these, which is negligible compared to π(X). Thus T_{2}^{b} has natural density 0. The proof for T_{2}^{c} is similar. □

The rest of this section is devoted to the proof that T_{2}^{a} has natural density 0. Recall that T_{2}^{a} consists of primes of the form p_{ℓ}. If the sequence of p_{ℓ} grew faster than the sequence of primes ℓ, then T_{2}^{a} would have density 0. But Lemma 8.2 implies only that p_{ℓ} is at least about the size of ℓ. The strategy for strengthening this bound will be to show that numbers of the form #E(𝔽_{p}) are typically divisible by many primes. For n ∈ ℤ_{>0}, let ω(n) be the number of distinct prime factors of n.

Lemma 9.3. For any t ≥ 1, the natural density of { p : ω(#E(𝔽_{p})) < t } is 0.

Proof. For a prime ℓ, let E[ℓ] denote the group of points of order dividing ℓ on E. Then ℓ | #E(𝔽_{p}) if and only if the image of the Frobenius element at p under Gal(\overline{ℚ}/ℚ) → Aut E[ℓ] has a nonzero fixed vector. Since E does not have complex multiplication, the image of Gal(\overline{ℚ}/ℚ) in ∏_{ℓ} Aut E[ℓ] is open. (This follows from [Ser72].) Thus Gal(\overline{ℚ}/ℚ) → ∏_{ℓ∉L′} Aut E[ℓ] is surjective for some finite L′ ⊆ P. A calculation shows that the fraction of elements of Aut E[ℓ] ≃ GL_{2}(𝔽_{ℓ}) having a nonzero fixed vector is

\frac{ℓ^{3} − 2ℓ}{(ℓ^{2} − 1)(ℓ^{2} − ℓ)} = \frac{1}{ℓ} + O (\frac{1}{ℓ^{2}} ) .

The sum of this over ℓ diverges, so as C → ∞, the fraction of elements of ∏_{ℓ<C,ℓ∉L′} Aut E[ℓ] having fewer than t components with a nonzero fixed vector tends to 0. Applying the Chebotarev Density Theorem (see Théorème 1 of [Ser81] for a version using natural density) and letting C → ∞, we obtain the result. □

Proposition 9.4. The set T_{2}^{a} has natural density 0.

Proof. Because of Lemma 9.3, it suffices to show that the upper natural density of

T_{2}^{a,t} := { p ∈ T_{2}^{a} : ω(#E(𝔽_{p})) ≥ t }

tends to 0 as t → ∞.

Suppose p = p_{ℓ} ∈ T_{2}^{a,t}. By Lemma 8.2, ℓ | #E(𝔽_{p}). By definition of T_{2}^{a,t}, the integer #E(𝔽_{p}) is divisible by at least t − 1 other primes, so 2^{t−1}ℓ ≤ #E(𝔽_{p}). There exists a degree-2 map E → ℙ^{1} over 𝔽_{p}, so #E(𝔽_{p}) ≤ 2(p + 1) ≤ 4p. Combining the previous two sentences yields ℓ ≤ 2^{3−t}p. Since every element of T_{2}^{a,t} is p_{ℓ} for some ℓ, we have

#{ p ∈ T_{2}^{a,t} : p ≤ X } ≤ π(2^{3−t}X) = (2^{3−t} + o(1)) π(X)

as X → ∞. Thus by definition, the upper natural density of T_{2}^{a,t} is at most 2^{3−t}. This goes to 0 as t → ∞. □

Thus T_{1} and T_{2} have natural density 0.

10. Proof of Theorem 1.3

By Proposition 5.2, E′(ℤ[S^{−1}]) differs from { ±ℓ_{i}P : i ≥ 1 } by at most a finite set. Since y(±ℓ_{i}P) is within 1/10 of ±i, any bounded subset of ℝ^{2} contains at most finitely many points of E′(ℤ[S^{−1}]). Part (1) of Theorem 1.3 follows.

We next construct a diophantine model A of the positive integers over ℤ[S^{−1}]. The set of nonzero elements of ℤ[S^{−1}] is diophantine (see Theorem 4.2 of [Shl94]), and we can represent elements of ℚ as fractions of elements of ℤ[S^{−1}] with nonzero denominator. Therefore equations over ℚ can be rewritten as systems of equations over ℤ[S^{−1}], and there is no harm in using them in our diophantine definitions. In particular, we may use the predicate x ≥ y, since it can be encoded as (∃z_{1}, z_{2}, z_{3}, z_{4} ∈ ℚ)(x = y + z_{1}^{2} + z_{2}^{2} + z_{3}^{2} + z_{4}^{2}).

For i ∈ ℤ_{>0}, define y_{i} := y(ℓ_{i}P). Let A = {y_{1}, y_{2}, … }. Then A is diophantine over ℤ[S^{−1}], because it consists of the nonnegative elements of the set of y-coordinates of E′(ℤ[S^{−1}]) minus a finite set. We have a bijection ℤ_{>0} → A taking i to y_{i}.

It remains to show that the graphs of addition and multiplication on ℤ_{>0} correspond to diophantine subsets of A^{3}. We know |y_{i}−i| ≤ 1/(10i) ≤ 1/10, so the idea is that the addition on ℤ_{>0} should correspond to the operation of adding elements of A and then rounding to the nearest element of A. A similar idea will work for squaring, and we will get multiplication from addition and squaring.

Lemma 10.1. Let m, n, q ∈ ℤ_{>0}. Then (1) m + n = q if and only if |y_{m} + y_{n} − y_{q}| ≤ 3/10.

(2) m^{2} = n if and only if |y_{m}^{2} − y_{n}| ≤ 4/10.

Proof.

(1) The quantity y_{m}+y_{n}−y_{q} differs from the integer m+n−q by at most 1/10+1/10+1/10.

(2) The quantity y_{m}^{2} − y_{n} differs from the integer m^{2} − n by at most

|y_{m}^{2} − m^{2}| + |y_{n} − n| ≤ |(m + \frac{1}{10m})^{2} − m^{2}| + \frac{1}{10}

≤ \frac{4}{10}.  □

Lemma 10.1 shows that the two predicates m + n = q and m^{2} = n on ℤ_{>0} correspond to diophantine predicates on A. Building with these, we can show the same for mn = q, since

mn = q ⟺ (m + n)^{2} = m^{2} + n^{2} + q + q.

This completes the proof of part (2) of Theorem 1.3. Part (3) follows from (2) and Matijasevič’s Theorem.

Acknowledgements

I thank Thanases Pheidas and the referee for helpful comments, in particular for simplifying the diophantine definition of multiplication at the end. I thank also Gunther Cornelissen and Graham Everest for suggesting references for Section 3, and Alexandra Shlapentokh for suggesting some improvements in the exposition.

References

[Aya92] Mohamed Ayad, Points S-entiers des courbes elliptiques, Manuscripta Math. 76 (1992), no. 3-4, 305–324.

[CZ00] Gunther Cornelissen and Karim Zahidi, Topology of Diophantine sets: remarks on Mazur’s conjectures, Hilbert’s tenth problem: relations with arithmetic and algebraic geometry (Ghent, 1999), Amer. Math. Soc., Providence, RI, 2000, pp. 253–260.

[DLPVG00] Jan Denef, Leonard Lipshitz, Thanases Pheidas, and Jan Van Geel (eds.), Hilbert’s tenth problem: relations with arithmetic and algebraic geometry, American Mathematical Society, Providence, RI, 2000, Papers from the workshop held at Ghent University, Ghent, November 2–5, 1999.

[DPR61] Martin Davis, Hilary Putnam, and Julia Robinson, The decision problem for exponential diophantine equations, Ann. of Math. (2) 74 (1961), 425–436.

[Eve02] Graham Everest, Zsigmondy’s theorem for elliptic curves, preprint, 11 October 2002.

[KR92] Ki Hang Kim and Fred W. Roush, An approach to rational Diophantine undecidability, Proceedings of Asian Mathematical Conference, 1990 (Hong Kong, 1990) (River Edge, NJ), World Sci. Publishing, 1992, pp. 242–248.

[Mat70] Yuri V. Matijasevič, The Diophantineness of enumerable sets, Dokl. Akad. Nauk SSSR 191 (1970), 279–282.

[Maz92] Barry Mazur, The topology of rational points, Experiment. Math. 1 (1992), no. 1, 35–45.

[Maz95] Barry Mazur, Speculations about the topology of rational points: an update, Astérisque (1995), no. 228, 4, 165–182, Columbia University Number Theory Seminar (New York, 1992).

[Ser72] Jean-Pierre Serre, Propriétés galoisiennes des points d’ordre fini des courbes elliptiques, Invent. Math. 15 (1972), no. 4, 259–331.

[Ser73] Jean-Pierre Serre, A course in arithmetic, Springer-Verlag, New York, 1973, Translated from the French, Graduate Texts in Mathematics, No. 7.

[Ser81] Jean-Pierre Serre, Quelques applications du théorème de densité de Chebotarev, Inst. Hautes Études Sci. Publ. Math. (1981), no. 54, 323–401.

[Ser97] Jean-Pierre Serre, Lectures on the Mordell-Weil theorem, third ed., Friedr. Vieweg & Sohn, Braunschweig, 1997, Translated from the French and edited by Martin Brown from notes by Michel Waldschmidt, With a foreword by Brown and Serre.

[Shl94] Alexandra Shlapentokh, Diophantine classes of holomorphy rings of global fields, J. Algebra 169 (1994), no. 1, 139–175.

[Shl97] Alexandra Shlapentokh, Diophantine definability over some rings of algebraic numbers with infinite number of primes allowed in the denominator, Invent. Math. 129 (1997), no. 3, 489– 507.

[Shl00] Alexandra Shlapentokh, Defining integrality at prime sets of high density in number fields, Duke Math. J. 101 (2000), no. 1, 117–134.

[Shl02] Alexandra Shlapentokh, Diophantine definability and decidability in large subrings of totally real number fields and their totally complex extensions of degree 2, J. Number Theory 95 (2002), no. 2, 227–252.

[Shl03] Alexandra Shlapentokh, A ring version of Mazur’s conjecture on topology of rational points, Internat. Math. Res. Notices (2003), no. 7, 411–422.

[Sil88] Joseph H. Silverman, Wieferich’s criterion and the abc-conjecture, J. Number Theory 30 (1988), no. 2, 226–237.

[Sil92] Joseph H. Silverman, The arithmetic of elliptic curves, Springer-Verlag, New York, 1992, Corrected reprint of the 1986 original.

[Vin54] I. M. Vinogradov, The method of trigonometrical sums in the theory of numbers, Interscience Publishers, London and New York., 1954, Translated, revised and annotated by K. F. Roth and Anne Davenport.

[War48] Morgan Ward, Memoir on elliptic divisibility sequences, Amer. J. Math. 70 (1948), 31–74.

Department of Mathematics, University of California, Berkeley, CA 94720-3840, USA

E-mail address: poonen@math.berkeley.edu