DIOPHANTINE DEFINABILITY OF INFINITE DISCRETE NONARCHIMEDEAN SETS AND DIOPHANTINE MODELS OVER

LARGE SUBRINGS OF NUMBER FIELDS

BJORN POONEN AND ALEXANDRA SHLAPENTOKH

Abstract. We prove that some infinite 𝔭-adically discrete sets have Diophantine definitions in large subrings of number fields. First, if K is a totally real number field or a totally complex degree-2 extension of a totally real number field, then for every prime 𝔭 of K there exists a set of K-primes S of density arbitrarily close to 1 such that there is an infinite 𝔭-adically discrete set that is Diophantine over the ring O_{K,S} of S-integers in K. Second, if K is a number field over which there exists an elliptic curve of rank 1, then there exists a set of K-primes S of density 1 and an infinite Diophantine subset of O_{K,S} that is v-adically discrete for every place v of K. Third, if K is a number field over which there exists an elliptic curve of rank 1, then there exists a set of K-primes S of density 1 such that there exists a Diophantine model of ℤ over O_{K,S}. This line of research is motivated by a question of Mazur concerning the distribution of rational points on varieties in a nonarchimedean topology and questions concerning extensions of Hilbert’s Tenth Problem to subrings of number fields.

1. Introduction

Matijasevič (following work of Davis, Putnam, and Robinson) proved that Hilbert’s Tenth Problem could not be solved: that is, there does not exist an algorithm, that given an arbitrary multivariable polynomial equation f(x_{1}, …, x_{n}) = 0 with coefficients in ℤ, decides whether or not a solution in ℤ^{n} exists. It is not known whether an analogous algorithm exists, however, if in the problem one replaces ℤ by ℚ in both places. One natural approach to proving a negative answer for ℚ is to show that ℤ admits a Diophantine definition over ℚ, or more generally that there is a Diophantine model of the ring ℤ over ℚ; the meaning of these statements is given in Definitions 1.1 and 1.3 below. (See [DLPVG00] for an introduction to the subject.)

Definition 1.1. Let R be a (commutative) ring. Suppose A ⊆ R^{k} for some k ∈ ℕ. Then we say that A has a Diophantine definition over R if there exists a polynomial

f(t_{1}, …, t_{k}, x_{1}, …, x_{n}) ∈ R[t_{1}, …, t_{k}, , x_{1}, …, x_{n}]

Date: June 5, 2005. 2000 Mathematics Subject Classification. Primary 11U05; Secondary 11G05. Key words and phrases. Hilbert’s Tenth Problem, elliptic curve, Mazur’s Conjecture, Diophantine defini-

tion, norm equation.

B.P. was partially supported by a Packard Fellowship and by NSF grants DMS-9801104 and DMS-0301280. A.S. was partially supported by NSF grants DMS-9988620 and DMS-0354907, and by ECU Faculty Senate Summer 2003 Grant. The final version of this article is to appear in Journal für die reine und angewandte Mathematik, published by Walter de Gruyter.

such that for any (t_{1}, …, t_{k}) ∈ R^{k},

(t_{1}, …, t_{k}) ∈ A ⟺ ∃x_{1}, …, x_{n} ∈ R, f(t_{1}, …, t_{k}, x_{1}, ..., x_{n}) = 0.

In this case we also say that A is a Diophantine subset of R^{k}, or that A is Diophantine over R.

Remark 1.2. Suppose that R is a domain whose quotient field is not algebraically closed. Then

(a) Relaxing Definition 1.1 to allow an arbitrary finite conjunction of equations in place of the single equation on the right hand side does not enlarge the collection of Diophantine sets.

(b) Finite unions and finite intersections of Diophantine sets are Diophantine. See the introduction in [Phe94] for details.

Definition 1.3. A Diophantine model of ℤ over a ring R is a Diophantine subset A ⊆ R^{k} for some k together with a bijection ϕ: ℤ → A such that the graphs of addition and multiplication (subsets of ℤ^{3}) correspond under ϕ to Diophantine subsets of A^{3} ⊆ R^{3k}.

Mazur formulated a conjecture that would imply that a Diophantine definition of ℤ over ℚ does not exist, and later in [CZ00] it was found that his conjecture also ruled out the existence of a Diophantine model of ℤ over ℚ. One form of Mazur’s conjecture was that for a variety X over ℚ, the closure of X(ℚ) in the topological space X(ℝ) should have at most finitely many connected components. See [Maz92], [Maz94], [Maz95], [Maz98], [CTSSD97], [CZ00], [Poo03], and [Shl03] for more about the conjecture and its consequences.

Mazur also formulated an analogue applying to both archimedean and nonarchimedean completions of arbitrary number fields. Specifically, on page 257 of [Maz98] he asked:

Question 1.4. Let V be any variety defined over a number field K. Let S be a finite set of places of K, and consider K_{S} = ∏_{v∈S} K_{v} viewed as locally compact topological ring. Let V (K_{S}) denote the topological space of K_{S}-rational points. For every point p ∈ V (K_{S}) define W (p) ⊂ V to be the subvariety defined over K that is the intersection of Zariski closures of the subsets V (K) ∩ U, where U ranges through all open neighborhoods of p in V (K_{S}). As p ranges through the points of V (K_{S}), are there only a finite number of distinct subvarieties W (p)?

In Question 1.4, it does not matter whether we require V to be irreducible. (We will not.)

Proposition 1.5. Fix a number field K and a place 𝔭. If Question 1.4 has a positive answer for K and S := {𝔭}, then there does not exist an infinite, 𝔭-adically discrete, Diophantine subset of K.

Proof. Suppose there exists a subset A of K that is infinite, 𝔭-adically discrete, and Diophantine over K. The Diophantine definition of A corresponds to an affine algebraic set V such that the projection π : V → 𝔸^{1} onto the first coordinate satisfies π(V (K)) = A.

Suppose a ∈ A. Since A is 𝔭-adically discrete, there exists an open neighborhood N of a in K_{𝔭} such that A ∩ N = {a}. Pick p ∈ V (K) with π(p) = a. Then U := π^{−1}(N) is an open neighborhood of p, and π maps V (K) ∩ U into A ∩ N = {a}, so W (p) ⊆ π^{−1}(a).

By choosing one p above each a ∈ A, we get infinitely many disjoint subvarieties W (p), contradicting the positive answer to Question 1.4. □

In view of the proposition above, constructing a Diophantine definition of an infinite discrete 𝔭-adic set over a number field K would be one way to answer Question 1.4 (negatively) for K. Unfortunately, at the moment such a construction seems out of reach. Thus instead we consider analogues in which K is replaced by some of its large integrally closed subrings.

Definition 1.6. If K is a number field, let P_{K} be the set of finite primes of K. For S ⊆ P_{K}, define the ring of S-integers

O_{K,S} = { x ∈ K | ord_{𝔭} x ≥ 0 for all 𝔭 ∉ S }.

(Elsewhere the term S-integers often presupposes that S is finite, but we will use this term for infinite S also.)

If S = ∅, then O_{K,S} equals the ring O_{K} of algebraic integers of K. If S = P_{K}, then O_{K,S} = K. In general, O_{K,S} lies somewhere between O_{K} and K, and the density of S (if it exists) may be used as a measure of the “size” of O_{K,S}. Throughout this paper, “density” means natural density, which is defined as follows.

Definition 1.7. Let S ⊆ P_{K}. The density of S is defined to be the limit

lim_{X→∞} \frac{#\{𝔭 ∈ S : N𝔭 ≤ X\}}{#\{all 𝔭 : N𝔭 ≤ X\}}

if it exists. If the density of S does not exist, we can replace the limit in Definition 1.7 by lim sup or lim inf and hence define the upper or lower densities of S. (See [Lan94, VIII, §4] for more about density.)

The study of Diophantine definability and the archimedean conjecture of Mazur over rings of S-integers has produced Diophantine definitions of ℤ and discrete archimedean sets over large subrings of some number fields (see [Shl97], [Shl00a], [Shl02], [Shl04] and [Shl03]). Recently in [Poo03], the first author constructed an infinite discrete Diophantine set (in the archimedean topology) and a Diophantine model of ℤ over a subring of ℚ corresponding to a set of primes of density 1. Thus he showed that the analogue of Hilbert’s Tenth Problem is undecidable over such a ring.

In this paper we consider Diophantine definability of infinite discrete 𝔭-adic sets over some rings of S-integers. Our results will come from two sources: norm equations (as in [Shl03]) and elliptic curves (as in [Poo03]). Our main results are stated below. When we say that a subset of O_{K,S} is Diophantine, we mean that it is Diophantine over O_{K,S}. A subset S of P_{K} is recursive if there exists an algorithm that takes as input an element of K (given by its coordinates with respect to some fixed ℚ-basis) and decides whether it belongs to O_{K,S}.

Theorem 1.8. Let K be a totally real number field or a totally complex degree-2 extension of a totally real number field. Let 𝔭 be any prime of K and let p_{ℚ} be the rational prime below it. Then for any ε > 0 there exists a recursive set of K-primes S ∋ 𝔭 of density > 1 − ε such that there exists an infinite Diophantine subset of O_{K,S} that is discrete and closed when viewed as a subset of the completion K_{𝔭}. In fact, such a subset can be found inside ℤ[1/p_{ℚ}].

Theorem 1.9. Let K be any number field for which there exists an elliptic curve E such that rank E(K) = 1. Then

(1) There exist recursive subsets T_{1}, T_{2} ⊆ P_{K} of density 0 such that for any S with T_{1} ⊆ S ⊆ P_{K} − T_{2}, there exists an infinite Diophantine subset A of O_{K,S} such that for all places v of K, the set A is discrete when viewed as a subset of the completion K_{v}.

(2) There exist recursive subsets T′_{1}, T′_{2} ⊆ P_{K} of density 0 such that for any S with T′_{1} ⊆ S ⊆ P_{K} − T′_{2}, there exists a Diophantine model of the ring ℤ over O_{K,S}.

Sections 2 and 3, which lead to Theorems 1.8 and 1.9, respectively, can be read independently.

2. Using norm equations

In this section we use norm equations to construct infinite Diophantine 𝔭-adically discrete sets, in order to prove Theorem 1.8.

2.1. Preliminary results.

Proposition 2.1. Let K be a number field and let S ⊆ P_{K}. Then O_{K,S} −{0} is Diophantine over O_{K,S}.

Proof. See Proposition 2.6 on page 113 of [Shl00b]. (Note: there is a typo in the statement in [Shl00b]: the last K should be O_{K,W}.) □

The importance of Proposition 2.1 is that equations with variables intended to range over K can now be interpreted in the arithmetic of O_{K,S}, since elements of K can be represented as fractions of elements of O_{K,S} with nonzero denominator.

Proposition 2.2. Let K be a number field, and let 𝔭 ∈ P_{K}. Then the discrete valuation ring O_{K,P_{K}−{𝔭}} = { x ∈ K : ord_{𝔭} x ≥ 0 } is Diophantine over K.

Proof. See Lemma 3.22 in [Shl94]. □

Corollary 2.3. Let K be a number field, and let 𝔭 ∈ P_{K}. Then the sets { x ∈ K : ord_{𝔭} x > 0 }, { (x, y) ∈ K^{2} : ord_{𝔭} x ≥ ord_{𝔭} y }, and { (x, y) ∈ K^{2} : ord_{𝔭} x = ord_{𝔭} y } are Diophantine over K.

Proof. Fix a ∈ K with ord_{𝔭} a = 1. Then

ord_{𝔭} x > 0 ⟺ ord_{𝔭}(x/a) ≥ 0,
ord_{𝔭} x ≥ ord_{𝔭} y ⟺ (∃r)(x = ry and ord_{𝔭} r ≥ 0),
ord_{𝔭} x = ord_{𝔭} y ⟺ (ord_{𝔭} x ≥ ord_{𝔭} y) and (ord_{𝔭} y ≥ ord_{𝔭} x).
□

Propositions 2.1 and 2.2 together imply the following generalization of Proposition 2.2 (cf. Theorem 4.4 in [Shl94]):

Proposition 2.4. Let K be a number field. If S ⊆ S′ ⊆ P_{K} and S′ − S is finite, then O_{K,S} is Diophantine over O_{K,S′}.

Lemma 2.5. Let F be a number field. Let {ω_{1}, …, ω_{s}} be a ℤ-basis for O_{F}. Let a_{1}, …, a_{s} ∈ ℚ, and let x = ∑_{i=1}^{s} a_{i}ω_{i}. Let p be a prime of ℚ that does not ramify in F. Then

min_{i} ord_{p} a_{i} = min_{𝔓}ord_{𝔓} x,

where 𝔓 ranges over F -primes above p.

Proof. Since p is unramified in F, the ideal pO_{F} factors as the product of the 𝔓. Thus we have an equality p^{m}O_{F} = ∏_{𝔓} 𝔓^{m} for any m ∈ ℤ. The two minimums in the statement equal the largest m for which x belongs to this fractional ideal, since p^{m}ω_{1}, …, p^{m}ω_{s} form a ℤ-basis for p^{m}O_{F}. □

Lemma 2.6. For any integer m ≥ 1 and any rational prime q, there exists a degree-m cyclic extension E/ℚ in which q splits completely. If moreover m is odd, then any such E is totally real.

Proof. Choose a rational prime ℓ splitting completely in ℚ(e^{2πi/m}, q^{1/m}). Then ℓ ≡ 1 (mod m) and the image of q in (ℤ/ℓℤ)^{∗} ≃ Gal(ℚ(e^{2πi/ℓ})/ℚ) is an m-th power. Equivalently, the Frobenius automorphism Frob_{q} ∈ Gal(ℚ(e^{2πi/ℓ})/ℚ) belongs to the index-m subgroup H of the cyclic group Gal(ℚ(e^{2πi/ℓ})/ℚ). Let E be the subfield of Gal(ℚ(e^{2πi/ℓ})/ℚ) fixed by H. Then the image of Frob_{q} in Gal(E/ℚ) is trivial, so q splits completely in E. Odd-degree Galois extensions of ℚ are totally real. □

2.2. Discrete Diophantine subsets of large subrings of ℚ. In this section we will use the following notation and assumptions.

• Let p_{ℚ}, p be primes of ℚ.

• Let E be a totally real cyclic extension of ℚ such that [E : ℚ] = p and p_{ℚ} splits completely in E. (This exists by Lemma 2.6.)

• Let L be an imaginary degree-2 extension of ℚ in which p_{ℚ} splits completely. (For instance, let b < 0 be an integer that is a nonzero square mod p_{ℚ} and let L = ℚ(\sqrt{b}).)

• Let V_{ℚ} be a set of rational primes that are inert in E/ℚ.

• Let W_{ℚ} = V_{ℚ} ∪ {p_{ℚ}}.

(By changing V_{ℚ}, we can make W_{ℚ} any set between {p_{ℚ}} and a particular set of natural density 1 − \frac{1}{p}.)

• Let W_{EL} be the set of EL-primes above W_{ℚ}.

• Let σ_{L}, σ_{E} be generators of Gal(L/ℚ), Gal(E/ℚ) respectively.

• Let 𝔭_{EL} be a prime above p_{ℚ} in EL.

• Let Ω = {ω_{1}, …, ω_{2p}} be a ℤ-basis for O_{EL} and note that Ω is also an O_{ℚ,W_{ℚ}}-basis for O_{EL,W_{EL}}.

The following proposition provides the foundation for our construction.

Proposition 2.7. Let x ∈ O_{EL,W_{EL}} be a solution to the system

(1)  \{ \begin{matrix}N_{EL/L}(x) = 1, \\ N_{EL/E}(x) = 1. \end{matrix}

such that

(2) x is a unit at all primes of EL above p_{ℚ} except possibly for 𝔭_{EL}, σ_{E}(𝔭_{EL}), σ_{L}(𝔭_{EL}), and σ_{E}σ_{L}(𝔭_{EL}) = σ_{L}σ_{E}(𝔭_{EL}); and

(3)  ord_{𝔭_{EL}} x > 0 and ord_{σ_{E}σ_{L}(𝔭_{EL})} x > 0.

Then the divisor of x equals

(4)  (\frac{𝔭_{EL} σ_{E}σ_{L}(𝔭_{EL})}{σ_{E}(𝔭_{EL}) σ_{L}(𝔭_{EL})})^{k}

for some k ∈ ℤ_{>0}. Furthermore, the set of solutions to (1) satisfying (2) and (3) is nonempty and closed under multiplication. (If x_{1} and x_{2} are solutions to (1), then x_{1}/x_{2} is again a solution to (1), but x_{1}/x_{2} will not necessarily satisfy (2) and (3) even if x_{1} and x_{2} do.) Proof. Since p_{ℚ} splits completely in E and in L, it splits completely in EL. Now apply Section 3.3.2 on page 131 of [Shl00b].

□

Corollary 2.8. Let A be the set of (a_{1}, …, a_{2p}) in (O_{ℚ,W_{ℚ}})^{2p} such that the element x = ∑_{i=1}^{2p} a_{i}ω_{i} of O_{EL,W_{EL}} satisfies (1), (2), and (3). Let B be the set of b ∈ O_{ℚ,W_{ℚ}} such that for some (a_{1}, …, a_{2p}) ∈ A,

(i) The element b equals one of the a_{i}, and (ii) ord_{p_{ℚ}} b = min{ord_{p_{ℚ}} a_{1}, …, ord_{p_{ℚ}} a_{2p}}.

(Thus B is the set of “p_{ℚ}-adically largest coordinates” of elements of A.) For r ∈ ℤ, let B_{r} = { b ∈ B : ord_{p_{ℚ}} b = r }. Then

(a) A and B are Diophantine over O_{ℚ,W_{ℚ}}.

(b) B ⊂ ℤ[1/p_{ℚ}].

(c) There exists M ∈ ℤ_{>0} such that B = ⋃_{m=1}^{∞} B_{−Mm} and each B_{−Mm} in the union is a nonempty finite set.

Proof.

(a) By writing each norm in (1) as a product of conjugates, we find that the equations (1) are equivalent to polynomial equations in the a_{i}. By Corollary 2.3 together with the “Going up and then down” method (see Section 2.2 on pages 110–111 of [Shl00b]), conditions (2) and (3) are Diophantine. Thus A is Diophantine.

Condition (i) is ∏_{i=1}^{2p}(b−a_{i}) = 0, and condition (ii) is Diophantine by Corollary 2.3, so B is Diophantine too.

(b) This follows from (4) above.

(c) If b ∈ B is associated to (a_{1}, …, a_{2p}) ∈ A and k is the positive integer in (4) for the element x = ∑_{i=1}^{2p} a_{i}ω_{i}, then ord_{p_{ℚ}} b = −k by Lemma 2.5. Thus the set of r for which B_{r} ≠ ∅ equals the set of possibilities for −k in (4) as x varies over all solutions to (1) satisfying (2) and (3). Let M be the smallest positive integer such that −M is a possible value of −k. Proposition 2.7 implies that the set of possibilities for −k is then {−M, −2M, … }. Thus B_{r} ≠ ∅ if and only if r ∈ {−M, −2M, … }.

It remains to prove that each B_{r} is finite. Fix r ∈ ℤ. The finiteness of B_{r} follows once we show that the set of x satisfying (1), (2), and (3) and having k = −r in (4) is finite. Suppose x_{1} and x_{2} are two such values of x, so by (4) the divisor of x_{1}/x_{2} is trivial. Then x_{1}/x_{2} ∈ O_{EL}^{∗} and N_{EL/E}(x_{1}/x_{2}) = 1. But EL/E is a totally complex degree-2 extension of a totally real field, so these conditions imply that x_{1}/x_{2} is a root of unity. Finally, there are only finitely many roots of unity in EL.

□

Corollary 2.9. There exists an infinite Diophantine subset B ⊂ O_{ℚ,W_{ℚ}} that is p_{ℚ}-adically discrete and closed. In fact, such a subset can be found inside ℤ[1/p_{ℚ}]. Proof. The Diophantine set B of Corollary 2.8 is infinite, because it is an infinite disjoint union of nonempty sets. It is p_{ℚ}-adically discrete and closed, because for each r < 0, the set of b ∈ B with ord_{p_{ℚ}} b ≥ r is finite. □

2.3. Notation and assumptions. Our next task is to extend the result above to some number fields. To accomplish this we will need additional notation and assumptions. We view all number fields as being subfields of a fixed algebraic closure \overline{ℚ}, so that compositums are well-defined.

• Let K be the number field given in Theorem 1.8. Thus K is totally real, or K is a totally complex degree-2 extension of a totally real field.

• Let n = [K : ℚ].

• Let 𝔭 be the prime of K in Theorem 1.8.

We take p_{ℚ} in the preceding section to be the rational prime under 𝔭.

• Let p = p_{0} < p_{1} < ⋯ < p_{n} be a sequence of odd primes such that p_{i} > n and 1/p_{i} < ε/(n + 1) for all i. (Here p is the same as in the preceding section.)

• Let E_{0} = E, E_{1}, …, E_{n} be a sequence of totally real cyclic extensions of ℚ such that [E_{i} : ℚ] = p_{i}. (Here E is the same field as above.)

• Let U_{ℚ} be the set of rational primes that are inert in all of the extensions E_{i}/ℚ for 0 ≤ i ≤ n. (Note that U_{ℚ} satisfies the requirements for V_{ℚ} of the preceding section.) Let W_{ℚ} = U_{ℚ} ∪ {p_{ℚ}}.

• Let W_{K} be the set of K-primes above W_{ℚ}.

2.4. Discrete Diophantine subsets of large subrings of K.

Proposition 2.10. Let U be a set of K-primes remaining prime in E_{i}K/K for i = 0, …, n. Then there exists a set of K-primes Ū such that the set difference (U − Ū) ∪ (Ū − U) is finite and O_{K,Ū} ∩ ℚ has a Diophantine definition over O_{K,Ū}.

Proof. See Corollary 2.3 and Theorem 3.8 of [Shl02]. (The application of Corollary 2.3 requires that p_{i} does not divide the absolute degree of the Galois closure of K/ℚ; this holds since p_{i} > n.) □

Clearly Proposition 2.10 implies the slightly stronger version in which the hypothesis on U is weakened to the hypothesis that all but finitely many primes of U are inert in all the E_{i}K/K. We now show that we can also insist that the new set of primes contains the original set:

Proposition 2.11. Let U be a set of K-primes such that all but finitely many of them are inert in E_{i}K/K for i = 0, …, n. Then there exists a set of K-primes U′ containing U such that U′ − U is finite and O_{K,U′} ∩ ℚ is Diophantine over O_{K,U′}.

Proof. Let Ū be the set given by (the slightly stronger version of) Proposition 2.10, and let U′ = U ∪ Ū. Thus U′ − U is finite.

By choice of Ū, the set R := O_{K,Ū} ∩ ℚ is Diophantine over O_{K,Ū}, which is Diophantine over O_{K,U′} by Proposition 2.4. Thus R is a Diophantine subset of O_{K,U′}. The desired subset O_{K,U′} ∩ ℚ can now be defined as the set of elements of O_{K,U′} equal to a ratio of elements of R with nonzero denominator (here we use Proposition 2.1 for R). □

Proof of Theorem 1.8. We will apply Proposition 2.11 to the set W_{K} defined in Section 2.3. By assumption, the cyclic extension E_{i}/ℚ has prime degree p_{i} > n. Thus [E_{i}K : K] = p_{i}, and moreover, a K-prime is inert in E_{i}K/K if and only if the ℚ-prime below it is inert in E_{i}/ℚ. All primes of W_{ℚ} but p_{ℚ} are inert in all the E_{i}/ℚ, so all primes of W_{K} but finitely many are inert in all the E_{i}K/K. Thus we may apply Proposition 2.11 to find a set of K-primes W′_{K} such that W′_{K} − W_{K} is finite and such that the set O_{ℚ,W′_{ℚ}} is Diophantine over O_{K,W′_{K}}, where W′_{ℚ} is the set of ℚ-primes q such that all K-primes above q lie in W′_{K}.

Since W′_{K} − W_{K} is finite, W′_{ℚ} − W_{ℚ} is finite. Now the infinite set B of Corollary 2.9 is Diophantine over O_{ℚ,W_{ℚ}}, which by Proposition 2.4

is Diophantine over O_{ℚ,W′_{ℚ}}, which is Diophantine over O_{K,W′_{K}}. Thus B is Diophantine over O_{K,W′_{K}}. Since 𝔭 lies above p_{ℚ}, the set B is 𝔭-adically discrete and closed. To fulfill the requirements of Theorem 1.8, we take S = W′_{K}. This is recursive, since up to a finite set, its primes are characterized by splitting behavior in a finite list of extension fields.

It remains to show that W′_{K} has density greater than 1−ε. Up to finitely many primes, W′_{K} is defined by the splitting behavior in finitely many extensions of K (namely, the E_{i}K/K). Thus, by the Chebotarev Density Theorem (see Théorème 1 of [Ser81] for a version using natural density), W′_{K} has a density. The density of the set of K-primes that fail to be inert in E_{i}K/K is 1/p_{i}, so the density of W′_{K} is at least

1 − ∑_{i=0}^{n} \frac{1}{p_{i}} > 1 − ∑_{i=0}^{n} \frac{ε}{n + 1} = 1 − ε.

□

3. Using elliptic curves

3.1. Notation.

• Whenever k is a perfect field, let \overline{k} be an algebraic closure, and let G_{k} = Gal(\overline{k}/k).

• K is a number field.

• E is an elliptic curve of rank 1 over K. (In particular, we assume that K is such that such an E exists).

• We fix a Weierstrass equation y^{2} = x^{3} + ax + b for E with coefficients in the ring of integers of K.

• E(K)_{tors} is the torsion subgroup of E(K).

• r is an even multiple of #E(K)_{tors}.

• Q ∈ E(K) is such that Q generates E(K)/E(K)_{tors}.

• P := rQ.

• P_{ℚ} = {2, 3, 5, … } is the set of rational primes.

• P_{K} is the set of all finite primes of K.

• Let S_{bad} ⊆ P_{K} consist of the primes that ramify in K/ℚ, the primes for which the reduction of the chosen Weierstrass model is singular (this includes all primes above 2), and the primes at which the coordinates of P are not integral. We occasionally view E as the scheme over O_{K,S_{bad}} defined by the homogenization of the Weierstrass equation.

• E′ is the smooth affine curve y^{2} = x^{3} + ax + b over O_{K,S_{bad}}. Thus E′ is E with the zero section removed.

• M_{K} is the set of all normalized absolute values of K.

• M_{K,∞} ⊂ M_{K} is the set of all archimedean absolute values of K.

• For 𝔭 ∈ P_{K}, let (1) K_{𝔭} be the completion of K at 𝔭.

(2) R_{𝔭} be the valuation ring of K_{𝔭}

(3) 𝔽_{𝔭} be the residue field of R_{𝔭},

(4) N𝔭 = #𝔽_{𝔭} be the absolute norm of 𝔭

• For n ≠ 0, write nP = (x_{n}, y_{n}) where x_{n}, y_{n} ∈ K.

• Let the divisor of x_{n} be of the form

\frac{𝔞_{n}}{𝔡_{n}} 𝔟_{n},

where

– 𝔡_{n} = ∏_{𝔮} 𝔮^{−a_{𝔮}}, where the product is taken over all primes 𝔮 of K not in S_{bad} such

that a_{𝔮} = ord_{𝔮} x_{n} < 0,

– 𝔞_{n} = ∏_{𝔮} 𝔮^{a_{𝔮}}, where the product is taken over all primes 𝔮 of K not in S_{bad} such

that a_{𝔮} = ord_{𝔮} x_{n} > 0.

– 𝔟_{n} = ∏_{𝔮} 𝔮^{a_{𝔮}}, where the product is taken over all primes 𝔮 ∈ S_{bad} and a_{𝔮} =

ord_{𝔮} x_{n}.

We use the convention that 𝔡_{0} is the zero ideal.

• For n as above, let S_{n} = {𝔭 ∈ P_{K} : 𝔭|𝔡_{n}}. By definition of S_{bad}, we have S_{1} = ∅.

• For n as above, let d_{n} = N𝔡_{n} ∈ ℤ_{≥1}.

• For u ∈ K^{∗} and v a place of K lying above the place p of ℚ (possibly p = ∞), define the (unnormalized) local height h_{v}(u) = log max{∥u∥_{v}, 1} where ∥u∥_{v} = |N_{K_{v}/ℚ_{p}}(u)|_{p} and K_{v} and ℚ_{p} denote completions.

• For u ∈ K^{∗}, define the global height h(u) = ∑_{v∈M_{K}} h_{v}(u).

• For ℓ ∈ P_{ℚ}, define a_{ℓ} to be the smallest positive number such that S_{ℓ^{a_{ℓ}}} ≠ ∅. (By Siegel’s Theorem, a_{ℓ} = 1 for all but finitely many ℓ.)

• Let L = {ℓ ∈ P_{ℚ} : a_{ℓ} > 1} and L = ∏_{ℓ∈L} ℓ^{a_{ℓ}−1}.

• Let 𝔭_{ℓ} be a prime of largest norm in S_{ℓ^{a_{ℓ}}}.

• For ℓ, m ∈ P_{ℚ}, let 𝔭_{ℓm} be a prime of largest norm in S_{ℓm} − (S_{ℓ} ∪ S_{m}), if this set is nonempty (see Proposition 3.5).

• E[m] denotes \{ T ∈ E(\overline{K}) : mT = 0 \}.

• If λ is an ideal in the endomorphism ring of E, then

E[λ] := \{ T ∈ E(\overline{K}) : aQ = 0 for all a ∈ λ \}.

3.2. Divisibility of denominators of x-coordinates. The next lemma is the number field analogue to Lemma 3.1(a) of [Poo03], where it was proved for ℚ. Lemma 3.1. Let 𝔯 be an integral divisor of K prime to S_{bad}. Then { n ∈ ℤ : 𝔯 | 𝔡_{n} } is a subgroup of ℤ.

Proof. It is enough to prove the lemma when 𝔯 is a prime power 𝔭^{m}. Let Ê be the formal group over R_{𝔭} defined by the chosen Weierstrass model of E. Let Ê(𝔭R_{𝔭}) be the group of points associated to Ê. There exist Laurent series x(z) = z^{−2} + ⋯ and y(z) = z^{−3} + ⋯ with coefficients in R_{𝔭} giving an injective homomorphism Ê(𝔭R_{𝔭}) → E(K_{𝔭}) whose image is the set E_{1}(K_{𝔭}) of (x, y) ∈ E(K_{𝔭}) with ord_{𝔭}(x) < 0 (together with O): this follows from Proposition VII.2.2 of [Sil92] when the Weierstrass equation is minimal, but the proof there does not use the minimality. Since ord_{𝔭} x(z) = −2 ord_{𝔭} z whenever z ∈ 𝔭R_{𝔭}, the set of (x, y) ∈ E(K_{𝔭}) with ord_{𝔭}(x) ≤ −m (together with O) corresponds under this homomorphism to a subgroup 𝔭^{⌈m/2⌉}R_{𝔭} of 𝔭R_{𝔭}, and hence is a subgroup of E(K_{𝔭}). □ Corollary 3.2. Let m, n ∈ ℤ − {0}, and let (m, n) be their gcd. Then S_{m} ∩ S_{n} = S_{(m,n)}. In particular, if (m, n) = 1 then S_{m} ∩ S_{n} = ∅.

3.3. New primes in denominators of x-coordinates.

Lemma 3.3. Let n ∈ ℤ_{≥1}. Suppose that 𝔱 ∈ P_{K} divides 𝔡_{n}, and p ≥ 3 is a rational prime. (1) If 𝔱 | p, then ord_{𝔱} 𝔡_{pn} = ord_{𝔱} 𝔡_{n} + 2.

(2) If 𝔱 ∤ p, then ord_{𝔱} 𝔡_{pn} = ord_{𝔱} 𝔡_{n}.

Proof. We will use the notation of Lemma 3.1. Since 𝔱 | 𝔡_{n}, by assumption 𝔱 ∉ S_{bad}. In particular 𝔱 is not ramified over ℚ. Furthermore, ord_{𝔱} x_{n} < 0, so nP ∈ E_{1}(K_{𝔱}). Let z be the corresponding element in the group of points Ê(𝔱R_{𝔱}) of the formal group. We have [p]z = pf(z) + g(z^{p}), by Proposition 2.3, page 116 and Corollary 4.4, page 120 of [Sil92], where [p] is the multiplication-by-p in the formal group and f(T), g(T) ∈ R_{𝔱}[[T]] satisfy g(0) = 0 and f(T) = T + higher order terms. Thus ord_{𝔱}([p]z) equals (ord_{𝔱} z) + 1 or ord_{𝔱} z, depending on whether 𝔱 | p. Since x = z^{−2} + ⋯, we find that ord_{𝔱} x_{pn} equals (ord_{𝔱} x_{n}) − 2 or ord_{𝔱} x_{n}, depending on whether 𝔱 | p. □

Lemma 3.4. There exists c ∈ ℝ_{>0} such that log d_{n} = (c − o(1))n^{2} as n ⟶ ∞.

Proof. Let ĥ be the canonical height on E(K). Then ĥ(nP)/n^{2} is a positive constant independent of n. The Weil height differs from ĥ by O(1), so h(x_{n})/n^{2} tends to a positive limit as n → ∞. By definition, h(x_{n}) differs from log d_{n} by the sum of h_{v}(x_{n}) over archimedean v and v ∈ S_{bad}. By the theorem on page 101 of [Ser97], h_{v}(x_{n})/h(x_{n}) → 0 as n → ∞ for each v, so (log d_{n})/h(x_{n}) tends to 1 as n → ∞. Thus (log d_{n})/n^{2} tends to a positive limit as n → ∞. □

The next proposition is a number field version of Lemma 3.4 of [Poo03].

Proposition 3.5. If ℓ, m ∈ P_{ℚ} and max(ℓ, m) is sufficiently large, then S_{ℓm} −(S_{ℓ} ∪S_{m}) ≠ ∅.

Proof. Suppose S_{ℓm} − (S_{ℓ} ∪ S_{m}) = ∅. We claim that 𝔡_{ℓm} | ℓ^{2}m^{2}𝔡_{ℓ}𝔡_{m}. To check this, we compare orders of both sides at a prime 𝔱 dividing 𝔡_{ℓm}. By assumption, 𝔱 divides either 𝔡_{ℓ} or 𝔡_{m}. Without loss of generality, assume 𝔱 | 𝔡_{ℓ}. Then Lemma 3.3 implies ord_{𝔱} 𝔡_{ℓm} ≤ ord_{𝔱}(m^{2}𝔡_{ℓ}), which proves the claim.

Taking norms, we obtain d_{ℓm} | (ℓm)^{2[K:ℚ]}d_{ℓ}d_{m}. Taking logs and applying Lemma 3.4, we deduce

(c − o(1))ℓ^{2}m^{2} ≤ 2[K : ℚ](log ℓ + log m) + (c − o(1))ℓ^{2} + (c − o(1))m^{2}
≤ (c + o(1))(ℓ^{2} + m^{2}),

which is a contradiction once max(ℓ, m) is sufficiently large. □

3.4. Density of prime multiples.

Lemma 3.6. Let α⃗ ∈ ℝ^{n}, let I be an open neighborhood of 0 in ℝ^{n}/ℤ^{n}, and let d ∈ ℤ_{≥1}. Then the set of primes ℓ ≡ 1 (mod d) such that (ℓ − 1)α⃗ mod 1 is in I has positive lower density.

Proof. Let α⃗ = (α_{1}, …, α_{n}). We first reduce to the case that 1, α_{1}, …, α_{n} are ℤ-independent. Choose m ∈ ℤ_{≥1} and β_{1}, …, β_{r} such that 1/m, β_{1}, …, β_{r} form a ℤ-basis for the subgroup of ℝ generated by 1, α_{1}, …, α_{n}. Replacing d by a positive integer multiple only reduces the density, so we may assume m | d. For fixed i, if α_{i} = \frac{c_{0}}{m} + ∑_{j=1}^{r} c_{j}β_{j}, then for ℓ ≡ 1 (mod d) we have

(ℓ − 1)α_{i} ≡ ∑_{j=1}^{r} c_{j}(ℓ − 1)β_{j} (mod 1),

so it suffices to prove positivity of the lower density of ℓ ≡ 1 (mod d) for which (ℓ − 1)β_{j} is sufficiently close mod 1 to 0 for all j.

In fact, we will prove the stronger result that the points (ℓ − 1)β⃗ ∈ (ℝ/ℤ)^{r} for prime ℓ ≡ 1 (mod d) are equidistributed. By Weyl’s equidistribution criterion [Wey16, Satz 3], we reduce to proving that for any s ∈ ℝ − ℚ,

∑_{\begin{matrix}ℓ≤x \\ ℓ≡1 (mod d) \end{matrix}} e^{2πiℓs} = o(π(x))

as x → ∞. This is a consequence of Vinogradov’s work on exponential sums over primes: see [Mon94, p. 34], for instance. □

Remark 3.7. With a slightly more involved argument, one could prove that the density of the set in Lemma 3.6 exists, though we will not need this.

3.5. Denominators of x-coordinates having many small prime factors. We next prove an analogue of Lemma 7.1 of [Poo03] showing that it is rare that S_{ℓ} has a large fraction of the small primes. For prime ℓ, define

μ_{ℓ} = sup_{X∈ℤ_{≥2}} \frac{#\{𝔭 ∈ S_{ℓ} : N𝔭 ≤ X\}}{#\{𝔭 ∈ P_{K} : N𝔭 ≤ X\}}.

Lemma 3.8. For any ε > 0, the density of { ℓ : μ_{ℓ} > ε } is 0.

Proof. The proof can be copied from that of Lemma 7.1 of [Poo03], using “the primes 𝔭 ∈ P_{K} with N𝔭 ≤ X” everywhere in place of the “the primes p up to X”: it requires only the facts

(1) The function π_{K}(X) := #{𝔭 ∈ P_{K} : N𝔭 ≤ X} is (1 + o(1))X/ log X as X → ∞ (Theorem 3 on page 213 of [CF86]).

(2) #S_{ℓ} ≤ log_{2} d_{ℓ} (clear, since each prime has norm at least 2)

(3) log_{2} d_{ℓ} = O(ℓ^{2}) as ℓ → ∞ (follows from Lemma 3.4).

□

3.6. Construction of the ℓ_{i}. By [Sil92, Corollary VI.5.1.1] and [Sil94, Corollary V.2.3.1], there is an isomorphism of real Lie groups ∏_{v∈M_{K,∞}} E(K_{v}) ≃ (ℝ/ℤ)^{N} × (ℤ/2ℤ)^{N′} for some N ≥ 1 and N′ ≥ 0. Fix such an isomorphism, and embed E(K) diagonally in ∏_{v∈M_{K,∞}} E(K_{v}). Since P = rQ with r even, the point P maps to an element α⃗ ∈ (ℝ/ℤ)^{N}.

Define a sequence of primes ℓ_{i} inductively as follows. Given ℓ_{1}, …, ℓ_{i−1}, let ℓ_{i} be the smallest prime outside L and exceeding the bound implicit in Proposition 3.5 such that all of the following hold:

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

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

(3) N𝔭_{ℓ_{i}ℓ_{j}} > 2^{i} for all j < i,

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

(5) ℓ_{i} ≡ 1 (mod i!), and

(6) |x_{ℓ_{i}−1}|_{v} > i for all v ∈ M_{K,∞}.

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

Proof. Condition (6) is equivalent to the requirement that (ℓ − 1)α⃗ lie in a certain open neighborhood of 0 in (ℝ/ℤ)^{N}, since the Lie group isomorphism maps neighborhoods of O to neighborhoods of 0. Thus by Lemma 3.6, the set of primes satisfying (5) and (6) has positive lower density. By Lemma 3.8, (2) fails for a set of 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 𝔭_{ℓ_{i}ℓ_{j}} for varying values of ℓ_{i} are distinct by Corollary 3.2, so eventually their norms are greater than 2^{i}. The same holds for 𝔭_{ℓℓ_{i}} for fixed ℓ ∈ L. Thus by taking ℓ_{i} sufficiently large, we can make all the 𝔭_{ℓ_{i}ℓ_{j}} and 𝔭_{ℓℓ_{i}} have norm greater than 2^{i}. Thus the sequence is well-defined.

Each ℓ_{i} can be computed by searching primes in increasing order until one is found satisfying the conditions: condition (6) can be tested effectively, since |x_{ℓ_{i}−1}|_{v} is an algebraic real number. □

As in Section 4 of [Poo03], we define the following subsets of P_{K}:

• T_{1} = S_{bad} ∪ ⋃_{i≥1} S_{ℓ_{i}},

• T_{2}^{a} is the set of 𝔭_{ℓ} for ℓ ∉ {ℓ_{1}, ℓ_{2}, … },

• T_{2}^{b} = { 𝔭_{ℓ_{i}ℓ_{j}} : 1 ≤ j ≤ i },

• T_{2}^{c} = { 𝔭_{ℓℓ_{i}} : ℓ ∈ L, i ≥ 1 }, and

• T_{2} = T_{2}^{a} ∪ T_{2}^{b} ∪ T_{2}^{c}. As in Section 5 of [Poo03], we prove that

Lemma 3.10. The sets T_{1} and T_{2} are disjoint. If the subset S ⊂ P_{K} contains T_{1} and is disjoint from T_{2}, then E := E′(O_{K,S}) ∩ rE(K) is the union of { ±ℓ_{i}P : i ≥ 1 } and some subset of the finite set { sP : s | ∏_{ℓ∈L} ℓ^{a_{ℓ}−1} }.

Proof. Once we note that rE(K) = ℤP, the proofs proceed as in Section 5 of [Poo03]. □

The recursiveness of T_{1} and T_{2} follows as in Section 8 of [Poo03], using the following:

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

Proof. For 𝔭 ∉ S_{bad}, a multiple nP reduces to 0 in E(𝔽_{𝔭}) if and only if 𝔭 divides 𝔡_{n}. Hence, by definition of 𝔭_{ℓ}, the point ℓ^{a_{ℓ}}P reduces to 0 in E(𝔽_{𝔭_{ℓ}}) but ℓ^{a_{ℓ}−1}P does not. □

3.7. Density of T_{1} and T_{2}. The proofs that T_{1}, T_{2}^{b}, and T_{2}^{c} have density 0 are identical to the proofs in Section 9 of [Poo03]. The remainder of this section is devoted to proving that T_{2}^{a} has density 0. Again, we follow [Poo03], but more work is necessary because we no longer assume that E has no CM.

For n ∈ ℤ_{>0}, let ω(n) be the number of distinct prime factors of n.

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

Proof. If E does not have CM (i.e., End E\overline{K} = ℤ), then the proof given for K = ℚ in Lemma 9.3 of [Poo03] generalizes easily to arbitrary K. The first step in this proof, which we will also use for the CM case, is to relate divisibility to Galois representations: namely, for a prime 𝔭 of good reduction not above ℓ, the condition ℓ | #E(𝔽_{𝔭}) is equivalent to the existence of an ℓ-torsion point in E(\overline{𝔽}_{𝔭}) fixed by the Frobenius element of Gal(\overline{𝔽}_{𝔭}/𝔽_{𝔭}), which in turn is equivalent to the condition that the the image of a Frobenius element at 𝔭 under G_{K} → Aut E[ℓ] = GL_{2}(ℤ/ℓℤ) has a nontrivial fixed vector in (ℤ/ℓℤ)^{2}.

We assume from now on that E has CM, say by an order O in a quadratic imaginary field F. Using the action of O on Lie E (the tangent space of E at O), we may view O (and hence also F) as a subring of \overline{K}.

All the endomorphisms are defined over the compositum KF [Sil94, II.2.2(b)].

Let Λ be the set of primes ℓ of ℤ such that ℓ ∤ disc(O) and (ℓ) factors into distinct prime ideals λ and λ̄ of O. (Later we will delete finitely many primes from Λ.)

For ℓ ∈ Λ,

E[ℓ] = E[λ] ⊕ E[λ̄].

The summands on the right are free modules over O/λ and O/λ̄, respectively, and we choose generators for each in order to obtain identifications

E[ℓ] ≃ O/λ ⊕ O/λ̄ ≃ (ℤ/ℓℤ)^{2},

and hence Aut E[ℓ] ≃ GL_{2}(ℤ/ℓℤ). The action of G_{KF} commutes with the O-action, so the

image of G_{KF} in GL_{2}(ℤ/ℓℤ) lies in the subgroup (\begin{matrix}∗ \\ & ∗ \end{matrix}) of diagonal matrices. On the other

hand, if τ ∈ G_{K} − G_{KF}, then τ interchanges λ and λ̄, and its image in GL_{2}(ℤ/ℓℤ) lies in

the coset (\begin{matrix}& ∗ \\ ∗ \end{matrix}).

Define subgroups

D = (\begin{matrix}∗ \\ & ∗ \end{matrix})
H = (\begin{matrix}∗ \\ & ∗ \end{matrix}) ∪ (\begin{matrix}& ∗ \\ ∗ \end{matrix})

of GL_{2} (∏_{ℓ∈Λ} ℤ/ℓℤ). Thus the image of ρ: G_{K} → GL_{2} (∏_{ℓ∈Λ} ℤ/ℓℤ) lies in H. It is a classical fact that ρ(G_{KF}) is open in D (see for example, the Corollaire on page 302 of [Ser72]), so ρ(G_{K}) is open in H. By deleting a few primes from Λ, we may assume that ρ(G_{K}) contains D, and hence equals D or H, depending on whether F ⊆ K or not.

Let π_{ℓ} be the probability that a random element of the subgroup (\begin{matrix}∗ \\ & ∗ \end{matrix}) ⊆ GL_{2}(ℤ/ℓℤ) has

a nontrivial fixed vector. A calculation shows that π_{ℓ} = 2/ℓ + O(1/ℓ^{2}). Since Λ has density 1/2, the series ∑_{ℓ∈Λ} 1/ℓ diverges. Thus ∑_{ℓ∈Λ} π_{ℓ} diverges. Elementary probability shows that if X_{1}, X_{2}, … are independent events, and the sum of their probabilities diverges, then as C → ∞, the probability that fewer than t of the first C events occur tends to 0. Therefore as C → ∞, if σ is chosen uniformly at random from the image of D in ∏_{ℓ∈Λ,ℓ<C} GL_{2}(ℤ/ℓℤ), then the probability that σ has fewer than t components with a nontrivial fixed vector tends to 0.

Similarly, a random element of the coset (\begin{matrix}& ∗ \\ ∗ \end{matrix}) ⊆ GL_{2}(ℤ/ℓℤ) has a nontrivial fixed

vector with probability 1/ℓ+O(1/ℓ^{2}). Thus the probability that a random σ from the image of H − D in ∏_{ℓ∈Λ,ℓ<C} GL_{2}(ℤ/ℓℤ) has fewer than t components with a nontrivial fixed vector tends to 0.

Combining the previous two paragraphs shows that the same holds for a random element of the image I_{C} of G_{K} → ∏_{ℓ∈Λ,ℓ<C} GL_{2}(ℤ/ℓℤ). But the Chebotarev Density Theorem implies that the images of the Frobenius elements Frob_{𝔭} in I_{C} are equidistributed in I_{C}. Finally we apply the “key first step” mentioned at the beginning of this proof to get the desired result. □

Using the preceding lemma, the proof that T_{2}^{a} has density 0 follows exactly the proof of Proposition 9.4 in [Poo03], using N𝔭 in place of p in the inequalities.

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

Remark 3.13. It follows that the set of all p_{ℓ} has density 0, since by definition T_{1}∪T_{2} contains all but finitely many of the p_{ℓ}.

3.8. Convergence and discreteness.

Lemma 3.14. For each v ∈ M_{K}, the sequence ℓ_{1}P, ℓ_{2}P, … converges in E(K_{v}) to P.

Proof. It suffices to show that (ℓ_{i} − 1)P → O in E(K_{v}) as i → ∞. If v is archimedean, this holds by condition (6) in the construction of the ℓ_{i}. Now suppose v is nonarchimedean. Then the topological group E(K_{v}) has a basis consisting of open finite-index subgroups U, namely the groups in the filtration appearing in the proof of [Sil92, VII.6.3]. So it suffices to show, given U, that (ℓ_{i} − 1)P ∈ U for sufficiently large i. Let j be the index of U in E(K_{v}). If i ≥ j, then j | i! | ℓ_{i} − 1, by condition (5) in the construction of the ℓ_{i}, so (ℓ_{i} − 1)P ∈ U.

□

Proposition 3.15. Let S be as in Lemma 3.10. Let A := {x_{ℓ_{1}}, x_{ℓ_{2}}, … }. Then A is a Diophantine subset of O_{K,S}. For any v ∈ M_{K}, the set A is discrete when viewed as a subset of K_{v}.

Proof. By Lemma 3.10, x(E) is the union of the set A := {x_{ℓ_{1}}, x_{ℓ_{2}}, … } and a finite set. Since E is Diophantine over O_{K,S}, so is A.

By Lemma 3.14, the elements of A form a convergent sequence in K_{v}, and the limit x_{1} of the sequence is not in A, so A is discrete. □

This completes the proof of part (1) of Theorem 1.9.

3.9. A Diophantine model of ℤ. We next show how to find a Diophantine model of the ring ℤ over certain rings O_{K,S}.

Lemma 3.16. Let B = { 2^{n} + n^{2} : n ∈ ℤ_{≥1} }. Multiplication admits a positive existential definition in the structure Z := (ℤ_{≥1}, 1, +, B). (Here B is considered as a unary predicate.)

Proof. We can define > by

x > y ⟺ (∃z) x = y + z

and for fixed a ∈ ℤ, we have

x ≠ a ⟺ (x > a) ∨ (a > x),

so this predicate is positive existential in Z. For fixed c ∈ ℤ_{≥1}, the function x ↦ cx is positive existential, since it can be obtained by repeated addition.

Call x, y consecutive if there exists n ∈ ℤ_{≥1} such that x = 2^{n} + n^{2} and y = 2^{n+1} + (n + 1)^{2}. The set of such (x, y) is positive existential in Z since it equals

{ (x, y) ∈ B^{2} : x < y < 3x }.

Next

{ ((2y − z) − (2x − y), 2x − y) : x, y are consecutive and y, z are consecutive }

equals the set T := { (2n − 1, n^{2} − 2n − 1) : n ∈ ℤ_{≥1} }. We have

(u = v^{2}) ∧ (v > 0) ⟺ (2v − 1, u − 2v − 1) ∈ T.

Call this relation P (u, v). Then

u = v^{2} ⟺ P (u, v) ∨ P (u, −v) ∨ ((u = 0) ∧ (v = 0)),
u = vw ⟺ (v + w)^{2} = v^{2} + w^{2} + 2u,

so we can construct a positive existential definition of multiplication. □

Remark 3.17. Y. Matijasevič (private communication) independently discovered a recursive set B such that multiplication admits a positive existential definition in (ℤ_{≥1}, 1, +, B). Any such B could be used in place of ours in the construction of the Diophantine model of ℤ over O_{K,S} below.

Corollary 3.18. The structure (ℤ, 0, 1, +, ·) admits a positive existential model in the structure Z.

Because of Corollary 3.18, instead of finding a Diophantine model of the ring ℤ over O_{K,S}, it will suffice to find a Diophantine model of Z.

Now we redo the construction in Section 3.6, but change some of the conditions defining the sequence of primes ℓ_{i}. Fix 𝔭, 𝔮 ∈ P_{K} − S_{bad} of degree 1 such that neither 𝔭 nor 𝔮 divides y_{1} = y(P), and such that the underlying primes p, q ∈ P_{ℚ} are distinct and odd. Let M = pq#E(𝔽_{𝔭})#E(𝔽_{𝔮}). Keep conditions (1) through (4), but replace conditions (5) and (6) by the following:

(5′) ℓ_{i} ≡ 1 (mod M),

(6′) the highest power of p dividing (ℓ_{i} − 1)/M is p^{i}, and (7′) q divides (ℓ_{i} − 1)/M if and only if i ∈ B.

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

Proof. The proof is the same as that of Proposition 3.9 except that instead of Lemma 3.6, we will use just Dirichlet’s theorem on primes in arithmetic progressions to show that conditions (5′) through (7′) are satisfied by a positive density of primes ℓ_{i}.

The conditions amount to congruences modulo p^{i+1}qM, so it suffices to show that one of the congruence classes is of the form a (mod p^{i+1}qM) with (a, p^{i+1}qM) = 1. Define

a = \begin{cases}1 + p^{i}qM & if i ∈ B \\ 1 + (p^{i}q + p^{i+1})M & if i ∉ B. \end{cases}

Then a is congruent to 1 modulo p, modulo q, and modulo M, so (a, p^{i+1}qM) = 1. Any prime in the residue class a (mod p^{i+1}qM) satisfies (5′) through (7′). □

Lemma 3.20. If m ∈ ℤ_{≥1}, then

ord_{𝔭}(x_{mM+1} − x_{1}) = ord_{𝔭}(x_{M+1} − x_{1}) + ord_{p} m.

Proof. Let R be the valuation ring R_{𝔭} defined in Section 3.1. Because y_{1} ∈ R^{∗} and 𝔭 ∤ 2, for any r ≥ 1, the restriction of the x-coordinate map E(R/𝔭^{r}) → ℙ^{1}(R/𝔭^{r}) to the subset of points of E(R/𝔭^{r}) with the same image in E(R/𝔭) as P is injective (the y-coordinate can be recovered from the the x-coordinate as the square root of an element of R^{∗}: its sign is determined by the fact that the point is in the residue class of P). Thus for r ≥ 1, the ideal 𝔭^{r} divides x_{mM+1} − x_{1} if and only if (mM + 1)P and P have the same image in E(R/𝔭^{r}), or equivalently if (mM)P maps to O in E(R/𝔭^{r}). Let z ∈ Ê(𝔭R) be the point of the formal group corresponding to MP. Then the condition that (mM)P maps to O in E(R/𝔭^{r}) is equivalent to [m](z) ∈ 𝔭^{r}, where [m] denotes the multiplication-by-m map in the formal group.

It remains to prove that ord_{𝔭}[m](z) = ord_{𝔭} z + ord_{p} m. By induction on m, it suffices to prove this when m is prime. Then, in the proof of Lemma 3.3, we have [m](z) = mf(z) + g(z^{m}) where f(T), g(T) ∈ R[[T]] satisfy g(0) = 0 and f(T) = T +higher order terms. Finally ord_{𝔭} m = ord_{p} m is 1 or 0 according to whether m = p or not, so the result follows. □

Proposition 3.21. Let S be as in Lemma 3.10. Let A := {x_{ℓ_{1}}, x_{ℓ_{2}}, … }. Then A is a Diophantine model of Z over O_{K,S}, via the bijection ϕ: ℤ_{≥1} → A taking i to x_{ℓ_{i}}.

Proof. The set A is Diophantine over O_{K,S} by the argument in the proof of Proposition 3.15. We have

i ∈ B ⟺ q divides (ℓ_{i} − 1)/M  (by condition (7′))
⟺ ord_{𝔮}(x_{ℓ_{i}} − x_{1}) > ord_{𝔮}(x_{M+1} − x_{1}),

by Lemma 3.20 (with 𝔮 in place of 𝔭). The latter inequality is a Diophantine condition on x_{ℓ_{i}}, by Corollary 2.3 (in which we represent elements of K as ratios of elements of O_{K,S}). Thus the subset ϕ(B) of A is Diophantine over O_{K,S}.

Finally, for i ∈ ℤ_{≥1}, Lemma 3.20 and condition (6′) imply ord_{𝔭}(x_{ℓ_{i}} − x_{1}) = c + i, where the integer c = ord_{𝔭}(x_{M+1} − x_{1}) is independent of i. Therefore, for i, j, k ∈ ℤ_{≥1}, we have

i + j = k ⟺ ord_{𝔭}(x_{ℓ_{i}} − x_{1}) + ord_{𝔭}(x_{ℓ_{j}} − x_{1}) = ord_{𝔭}(x_{ℓ_{k}} − x_{1}) + c.

It follows that the graph of + corresponds under ϕ to a subset of A^{3} that is Diophantine over O_{K,S}.

Thus A is a Diophantine model of Z over O_{K,S}. □

As already remarked, Corollary 3.18 and Proposition 3.21 together imply part (2) of Theorem 1.9.

Acknowledgements

We thank Ernie Croot for a discussion regarding Lemma 3.6, and the referee for a helpful report.

References

[CF86] J. W. S. Cassels and A. Fröhlich (eds.), Algebraic number theory, London, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], 1986, Reprint of the 1967 original.

[CTSSD97] J.-L. Colliot-Thélène, A. N. Skorobogatov, and Peter Swinnerton-Dyer, Double fibres and double covers: paucity of rational points, Acta Arith. 79 (1997), no. 2, 113–135.

[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.

[Lan94] Serge Lang, Algebraic number theory, second ed., Springer-Verlag, New York, 1994.

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

[Maz94] Barry Mazur, Questions of decidability and undecidability in number theory, J. Symbolic Logic 59 (1994), no. 2, 353–371.

[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).

[Maz98] B. Mazur, Open problems regarding rational points on curves and varieties, Galois representations in arithmetic algebraic geometry (Durham, 1996), London Math. Soc. Lecture Note Ser., vol. 254, Cambridge Univ. Press, Cambridge, 1998, pp. 239–265.

[Mon94] Hugh L. Montgomery, Ten lectures on the interface between analytic number theory and harmonic analysis, CBMS Regional Conference Series in Mathematics, vol. 84, Published for the Conference Board of the Mathematical Sciences, Washington, DC, 1994.

[Phe94] Thanases Pheidas, Extensions of Hilbert’s tenth problem, J. Symbolic Logic 59 (1994), no. 2, 372–397.

[Poo03] Bjorn Poonen, Hilbert’s tenth problem and Mazur’s conjecture for large subrings of ℚ, J. Amer. Math. Soc. 16 (2003), no. 4, 981–990.

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

[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.

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

[Shl00b] Alexandra Shlapentokh, Hilbert’s tenth problem over number fields, a survey, Hilbert’s tenth problem: relations with arithmetic and algebraic geometry (Ghent, 1999), Amer. Math. Soc., Providence, RI, 2000, pp. 107–137.

[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.

[Shl04] Alexandra Shlapentokh, On diophantine definability and decidability in some infinite totally real extensions of ℚ, Trans. Amer. Math. Soc., 356 (2004), no. 8, 3189–3207.

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

[Sil94] Joseph H. Silverman, Advanced topics in the arithmetic of elliptic curves, Springer-Verlag, New York, 1994.

[Wey16] Hermann Weyl, Über die Gleichverteilung von Zahlen mod. Eins, Math. Ann. 77 (1916), 313– 352.

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

E-mail address: poonen@math.berkeley.edu
URL: http://math.berkeley.edu/~poonen

Department of Mathematics, East Carolina University, Greenville, NC 27858, USA

E-mail address: shlapentokha@mail.ecu.edu
URL: http://www.personal.ecu.edu/shlapentokha