Using elliptic curves of rank one towards the undecidability of Hilbert’s Tenth Problem over

rings of algebraic integers

Bjorn Poonen^{⋆}

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

                         poonen@math.berkeley.edu

Abstract. Let F ⊆ K be number fields, and let O_{F} and O_{K} be their rings of integers. If there exists an elliptic curve E over F such that rk E(F) = rk E(K) = 1, then there exists a diophantine definition of O_{F} over O_{K}.

1 Introduction

D. Hilbert asked, as Problem 10 of his famous list of 23 problems posed to the mathematical community in 1900, for an algorithm to decide, given a polynomial equation f(x_{1}, …, x_{n}) = 0 with coefficients in the ring Z of integers, whether there exists a solution with x_{1}, …, x_{n} ∈ Z. In Hilbert’s time, there was no formal definition of algorithm, but presumably what he had in mind was a mechanical procedure that a human could in principle carry out, given sufficient paper, pencils, erasers, and time, following a set of strict rules requiring no insight or ingenuity on the part of the human. In the 1930s, several rigorous models of computation were proposed as a substitute for the informal notion of “mechanical procedure” as above (the λ-definable functions of A. Church and S. Kleene, the recursive functions of K. Gödel and J. Herbrand, and the logical computing machines of A. Turing). These models, as well as others developed later, were shown to be equivalent; this gave credence to the Church-Turing thesis, which is the belief that every mechanical procedure can be carried out by a Turing machine. Therefore, the modern interpretation of Hilbert’s Tenth Problem is that it asks whether a Turing machine can decide the existence of solutions.

J. Matijasevič [Mat70], building on earlier work by M. Davis, H. Putnam, and J. Robinson [DPR61] showed that there is no such Turing machine. To describe their work in more detail, we need a few definitions. A subset S of Z^{n} is called listable or recursively enumerable if there is an algorithm (Turing machine) such that S is exactly the set of a ∈ Z^{n} that are eventually printed by the algorithm. A subset S of Z^{n} is said to be diophantine, or to admit a diophantine definition,

⋆ This research was supported by NSF grant DMS-9801104, and a Packard Fellowship. This article will appear in the Proceedings of the Algorithmic Number Theory Symposium V, in the Springer Lecture Notes in Computer Science series, accessible elec-

  tronically at http://www.springer.de/comp/lncs/index.html \begin{matrix}c \\ ◯ \end{matrix}Springer-Verlag.

if there is a polynomial p(a_{1}, …, a_{n}, x_{1}, …, x_{m}) ∈ Z[a_{1}, …, a_{n}, x_{1}, …, x_{m}] such that

S = { a ∈ Z^{n} : (∃x_{1}, …, x_{m} ∈ Z) p(a_{1}, …, a_{n}, x_{1}, …, x_{m}) = 0 }.

For example, the subset Z_{≥0} := {0, 1, 2, … } of Z is diophantine, since for a ∈ Z, we have

a ∈ Z_{≥0} ⟺ (∃x_{1}, x_{2}, x_{3}, x_{4} ∈ Z) x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + x_{4}^{2} = a.

One can show using “diagonal arguments” that there exists a listable subset L of Z whose complement is not listable. It follows that for this L, there is no algorithm that takes as input an integer a and decides in a finite amount of time whether a belongs to L; in other words, membership in L is undecidable.

Diophantine subsets of Z^{n} are listable: given p, one can write a computer program with an outer loop with B running through 1, 2, …, and an inner loop in which one tests the finitely many (a_{1}, …, a_{n}, x_{1}, …, x_{m}) ∈ Z^{n+m} satisfying |a_{i}|, |x_{j}| ≤ B for all i and j, and prints (a_{1}, …, a_{n}) if p(a_{1}, …, a_{n}, x_{1}, …, x_{m}) = 0. Davis [Dav53] conjectured conversely that all listable subsets of Z^{n} were diophantine, and this is what Matijasevič eventually proved. In particular, the set L is diophantine. Hence a positive answer to Hilbert’s Tenth Problem would imply that membership in L is decidable. But membership in L is undecidable, so Hilbert’s Tenth Problem is undecidable too; that is, there is no algorithm that takes as input a polynomial p ∈ Z[x_{1}, …, x_{n}], and decides whether p(x_{1}, …, x_{n}) = 0 has a solution in integers.

More generally, if R is any commutative ring with 1, one can define what it means for a subset of R^{n} to be diophantine over R, by replacing Z by R everywhere. Similarly one can speak of Hilbert’s Tenth Problem over R provided that one has fixed some encoding of elements of R as finite strings of symbols from a finite alphabet, so that polynomials over R can be the input to a Turing machine. For some rings R (for example, uncountable rings) such an encoding may not be possible. In this case one should modify the problem, by specifying a countable subset P of the set of all polynomials over R and an encoding of elements of P as finite strings of symbols, and then asking whether there exists a Turing machine that takes as input a polynomial p ∈ P and decides whether p(x_{1}, …, x_{n}) = 0 has a solution over R. For example, K. Kim and F. Roush [KR92] proved that Hilbert’s Tenth Problem over the purely transcendental function field C(t_{1}, t_{2}) is undecidable when one takes P to be the set of polynomials with coefficients in Z[t_{1}, t_{2}]. Usually it is not necessary to specify exactly how the elements of P are encoded, since usually given any two reasonable encodings, a Turing machine can convert between the two.

Perhaps the most important unsolved question in this area is Hilbert’s Tenth Problem over the field Q of rational numbers. The majority view seems to be that it should be undecidable. To prove this, it would suffice to show that the subset Z of Q is diophantine over Q. On the other hand, B. Mazur has suggested that perhaps for any variety X over Q, the topological closure of X(Q) in X(R) has at most finitely many connected components; if this is true, no such diophantine definition of Z over Q exists. See [Maz94] and the more recent articles [CZ00] and [Phe00] for further discussion.

The function field analogue, namely Hilbert’s Tenth Problem over the function field k of a curve over a finite field, is known to be undecidable. The first result of this type is due to T. Pheidas [Phe91], who proved this for k = F_{q}(t) with q odd. His argument was adapted and generalized by C. Videla [Vid94] for k = F_{q}(t) with q even, by A. Shlapentokh [Shl92] for other function fields of odd characteristic, and finally by K. Eisenträger [Eis] for the remaining function fields of characteristic 2. Analogues are known also for many function fields over infinite fields of positive characteristic: see [Shl00a] and [Eis].

For more results concerning Hilbert’s Tenth Problem, see the book [DLPVG00], and especially the survey articles [PZ00] and [Shl00b] therein. Since the publication of that book, undecidability of Hilbert’s Tenth Problem has been proved also for function fields of curves X over formally real fields k_{0} with X(k_{0}) nonempty [MB] (in fact this is just one application of his results), and for function fields of surfaces over real closed or algebraically closed fields of characteristic zero [Eis].

2 Hilbert’s Tenth Problem over rings of integers

In this article, our goal is to prove a result towards Hilbert’s Tenth Problem over rings of integers. If F is a number field, let O_{F} denote the integral closure of Z in F. There is a known diophantine definition of Z over O_{F} for the following number fields:

1. F is totally real [Den80].

2. F is a quadratic extension of a totally real number field [DL78].

3. F has exactly one conjugate pair of nonreal embeddings [Phe88], [Shl89].

In particular, Hilbert’s Tenth Problem over O_{F} is undecidable for such fields F.

It is conjectured [DL78] that for every number field F, there is a diophantine definition of Z over O_{F}. Our main theorem gives evidence for this conjecture, by reducing it to a plausible conjecture about the existence of certain elliptic curves.

Before stating our theorem, let us recall the Mordell-Weil Theorem, which states that if E is an elliptic curve over a number field F, then the abelian group E(F) is finitely generated. Let rk E(F) denote the rank of E(F).

Theorem 1. Let F ⊆ K be number fields, and let O_{F} and O_{K} be their rings of integers. Suppose that there exists an elliptic curve E over F such that rk E(F) = rk E(K) = 1. Then there exists a diophantine definition of O_{F} over O_{K}.

Most of the rest of this paper is devoted to the proof of Theorem 1. But for now, we mention its application to Hilbert’s Tenth Problem.

Corollary 2. Under the hypotheses of Theorem 1, if in addition F is of one of the types of number fields listed above for which a diophantine definition of Z over O_{F} is known, then Hilbert’s Tenth Problem over O_{K} is undecidable.

Proof. Theorem 1 reduces the undecidability over O_{K} to the undecidability over O_{F}. ⊓ ⊔

J. Denef, at the end of [Den80], sketches a simple proof of Theorem 1 in the case where K is totally real and F = Q. In fact, he is also able to treat some totally real algebraic extensions K of infinite degree over Q. But his proof technique does not seem to generalize easily to fields that are not totally real.

Our proof of Theorem 1 is similar to that of an older result, the theorem of [DL78], which uses a 1-dimensional torus (a Pell equation) in place of the elliptic curve. We have been inspired also by the exposition of the “weak version of the vertical method” in [Shl00b] and by the ideas in [Phe00].

2.1 Preliminaries on diophantine sets over O_{K}

The subset O_{K} − {0} of O_{K} is diophantine over O_{K}: see Proposition 1(c) of [DL78]. We have a surjective map O_{K} × (O_{K} − {0}) → K taking (a, b) to a/b. If S ⊆ K^{n} is diophantine over K, then the inverse image of S under (O_{K} × (O_{K} − {0}))^{n} → K^{n} is diophantine over O_{K}. In this case, we will also say that S is diophantine over O_{K}. It follows that in constructing diophantine definitions over O_{K}, there is no harm in using equations with some variables taking values in O_{K} and other variables taking values in K.

Given t ∈ K^{×}, define the denominator ideal den(t) = { b ∈ O_{K} : bt ∈ O_{K} } and the numerator ideal num(t) = den(t^{−1}). Also define num(0) to be the zero ideal. These ideals behave in the obvious way upon extension of the field.

Lemma 3.

1. For fixed m, n ∈ Z_{≥0}, the set of (x_{1}, …, x_{m}, y_{1}, …, y_{n}) in K^{m+n} such that the fractional ideal (x_{1}, …, x_{m}) divides the fractional ideal (y_{1}, …, y_{n}) is diophantine over O_{K}.

2. The set of (t, u) ∈ K^{×} × K^{×} such that den(t) | den(u) is diophantine over O_{K}.

3. The set of (t, u) ∈ K^{×} × K such that den(t) | num(u) is diophantine over O_{K}.

4. The set of (t, u) ∈ O_{K} × K^{×} such that t | den(u) is diophantine over O_{K}.

Proof. Statement 1 is clear, since the condition is that there exist c_{ij} ∈ O_{K} such that y_{j} = ∑_{i} c_{ij}x_{i} for each j. Statement 2 follows from statement 1, since den(t) | den(u) if and only if the fractional ideal (u, 1) divides (t, 1). Statements 3 and 4 follow from statement 2: namely,

den(t) | num(u) ⟺ u = 0 or (∃v)(uv = 1 and den(t) | den(v)),
t | den(u) ⟺ (∃v)(tv = 1 and den(v) | den(u)).
⊓ ⊔

2.2 Bounds from divisibility in O_{K}

Let n = [K : Q] and s = [K : F]. Fix α ∈ O_{K} such that {1, α, …, α^{s−1}} is a basis for K over F. Let D ∈ O_{F} denote the discriminant of this basis. If I is an ideal in O_{K}, let N_{K/Q}(I) ∈ Z_{≥0} denote its norm.

Lemma 4. There is a positive integer c > 0 depending only on F, K, and α such that the following holds. Let I ⊂ O_{K} be a nonzero nonunit ideal, and let μ ∈ O_{K}. Write μ = ∑_{i=0}^{s−1} a_{i}α^{i} with a_{i} ∈ F. Suppose that μ(μ + 1) ⋯ (μ + n) | I. Then N_{K/Q}(Da_{i}) ≤ N_{K/Q}(I)^{c}.

Proof. This is essentially Section 1.2 of [Shl00b]. The only differences are that we have specialized by taking l_{i} = −i, and we have generalized by replacing the element y by an ideal I: this does not affect the proof. ⊓ ⊔

The following is similar to Lemma 2.5 in [Shl00b].

Lemma 5. There exists a constant c′ > 0 depending only on F and K such that the following holds: Let I be a nonzero ideal of O_{F}. Suppose μ ∈ O_{K} and w ∈ O_{F}. Write μ = ∑_{i=0}^{s−1} a_{i}α^{i} with a_{i} ∈ F. Suppose N_{K/Q}(Da_{i}) < c′N_{K/Q}(I) for all i, and μ ≡ w (mod IO_{K}). Then μ ∈ O_{F}.

Proof. Choose ideals J_{1}, …, J_{h} ⊆ O_{F} representing the elements of the class group of F, and choose c′ > 0 such that c′N_{K/Q}(J_{j}) < 1 for all j. Choose j such that J_{j}I^{−1} is principal, generated by z ∈ F^{×}, say. Since μ ≡ w (mod IO_{K}), we have

z(μ − w) = z(a_{0} − w) + (za_{1})α + ⋯ + (za_{s−1})α^{s−1} ∈ O_{K}.

By Lemma 4.1 of [Shl00b] (an elementary lemma about discriminants), Dza_{i} ∈ O_{F} for i = 1, 2, …, s − 1. On the other hand,

|N_{K/Q}(Dza_{i})| = |N_{K/Q}(Da_{i})N_{K/Q}(z)| < c′N_{K/Q}(I)\frac{N_{K/Q}(J_{j})}{N_{K/Q}(I)} < 1,

by definition of c′, so Dza_{i} = 0. Thus a_{i} = 0 for i = 1, 2, …, s − 1. Hence μ ∈ O_{F}. ⊓ ⊔

2.3 Denominators of x-coordinates of points on an elliptic curve

We assume that an elliptic curve E as in Theorem 1 exists. Thus E is defined over F, and rk E(F) = rk E(K) = 1. Hence E has a Weierstrass model of the form y^{2} = x^{3} + ax + b and we may assume a, b ∈ O_{F}. Let O denote the point at infinity on E, which is the identity of E(F).

For each nonarchimedean place 𝔭 of K, let K_{𝔭} denote the completion of K at 𝔭. and let F_{𝔭} denote the residue field. Reducing coefficients modulo 𝔭 yields a possibly singular curve

E_{𝔭} := Proj \frac{F_{𝔭}[X, Y, Z]}{(Y^{2}Z − X^{3} − āXZ^{2} − b̄Z^{3})}

over F_{𝔭}. Let E_{𝔭}^{smooth} denote the smooth part of E_{𝔭}. Let E_{0}(K_{𝔭}) be the set of points in E(K_{𝔭}) whose reduction mod 𝔭 lies in E_{𝔭}^{smooth}(F_{𝔭}).

Lemma 6.

1. E_{0}(K_{𝔭}) is a subgroup of E(K_{𝔭}).

2. E_{𝔭}^{smooth}(F_{𝔭}) is an abelian group under the usual chord-tangent law.

3. Reduction modulo 𝔭 gives a surjective group homomorphism red_{𝔭} : E_{0}(K_{𝔭}) → E_{𝔭}^{smooth}(F_{𝔭}).

4. Both E_{0}(K_{𝔭}) and E_{1}(K_{𝔭}) := ker(red_{𝔭}) are of finite index in E(K_{𝔭}).

Proof. For the first three statements, see Proposition VII.2.1 in [Sil92]. We have not assumed that our Weierstrass model is minimal at 𝔭, so our definition of E_{0} is different from the standard one in [Sil92], but this does not matter in the proofs. To prove statement 4, observe that E_{0}(K_{𝔭}) and E_{1}(K_{𝔭}) are open subgroups of the compact group E(K_{𝔭}) in the 𝔭-adic topology. ⊓ ⊔

From now on, r ∈ Z_{≥1} is assumed to be a multiple of #E(K)_{tors}, of the index (E(K) : E(F)), and of the index (E(K_{𝔭}) : E_{0}(K_{𝔭})) for each bad nonarchimedean place 𝔭. Then rE(K) is a subgroup of E(F) that is free of rank 1, and rE(K) is contained in E_{0}(K_{𝔭}) for every 𝔭.

We will need a diophantine approximation result. First we define the norm ∥ ∥_{v} : K → R_{≥0} for each place v of K; it will be characterized by its values on a ∈ O_{K}. If v is nonarchimedean and a ∈ O_{K} − {0}, then ∥a∥_{v} := q^{−v(a)} where q is the size of the residue field, and the discrete valuation v is normalized to take values in Z. If v is real, then ∥a∥_{v} is the standard absolute value of the image of a under K → R. If v is complex, then ∥a∥_{v} is the square of the standard absolute value of the image of a under K → C. Define the naive logarithmic height of a ∈ K by

h(a) := ∑_{places v of K} log max{∥a∥_{v}, 1}.

If one sums over only the nonarchimedean places v, one obtains log N_{K/Q} den(a).

Proposition 7. Let X be a smooth, projective, geometrically integral curve over K of genus ≥ 1. Fix a place v of K. Let ϕ be a nonconstant rational function on X. Let P_{1}, P_{2}, … be a sequence of distinct points in X(K). For sufficiently large m, P_{m} is not a pole of ϕ, so z_{m} := ϕ(P_{m}) belongs to K. Then

lim_{m→∞} \frac{log ∥z_{m}∥_{v}}{h(z_{m})} = 0.

Proof. See Section 7.4 of [Ser97]. ⊓ ⊔

Lemma 8. The following holds if r is sufficiently large: If P ∈ rE(K) − {O} and m ∈ Z − {−1, 0, 1}, then

log N_{K/Q} den(x(mP)) ≥ \frac{9}{10}m^{2} log N_{K/Q} den(x(P)) > 0;

in particular den(x(mP)) ≠ den(x(P)) and den(x(P)) ≠ (1).

Proof. Let P_{1} be a generator of rE(K). The theory of the canonical height in Chapter 8, Section 9 of [Sil92] implies that there is a real number ĥ(P_{1}) > 0 (namely, the canonical height of P_{1}, suitably normalized) such that h(x(mP_{1})) = m^{2}ĥ(P_{1}) + O(1), where the implied constant is independent of m ∈ Z. Proposition 7 applied to each archimedean v, with X = E and ϕ = x, shows that if we forget to include the (finitely many) archimedean places in the sum defining h, we obtain

log N_{K/Q} den(x(mP_{1})) = (1 − o(1))h(x(mP_{1})) = (1 − o(1))m^{2}ĥ(P_{1})

as |m| → ∞. The results follow for large r. ⊓ ⊔

Of course, there is nothing special about 9/10; any real number in the interval (1/4, 1) would have done just as well.

2.4 Divisibility of denominators

From now on, we suppose that r is large enough that Lemma 8 holds.

Lemma 9. Let P, P′ ∈ rE(K) − {O}. Then den(x(P)) | den(x(P′)) if and only if P′ is an integral multiple of P.

Proof. We first show that for any ideal I ⊆ O_{K}, the set

G_{I} := { Q ∈ rE(K) : I | den(x(Q)) }

is a subgroup of rE(K). (By convention, we consider O to be an element of G_{I}.) Since an intersection of subgroups is a subgroup, it suffices to prove this when I = 𝔭^{n} for some prime 𝔭 and some n ∈ Z_{≥1}. Let O_{𝔭} be the completion of O_{K} at 𝔭. Let F ∈ O_{K}[[z_{1}, z_{2}]] denote the formal group of E with respect to the parameter z := −x/y, as in Chapter 4 of [Sil92]. Then there is an isomorphism F(𝔭O_{𝔭}) ≃ E_{1}(K_{𝔭}), given by z ↦ (x(z), y(z)) where x(z) = z^{−2} + … and y(z) = −z^{−3} +… are Laurent series with coefficients in O_{K}. It follows that G_{𝔭^{n}} is the set of points in rE(K) lying in the image of F(𝔭^{⌈n/2⌉}O_{𝔭}). In particular G_{𝔭^{n}} is a subgroup of rE(K).

The “if” part of the lemma follows from the preceding paragraph. Now we prove the “only if” part. Let G = G_{den(x(P))}. Then G is a subgroup of rE(K) ≃ Z, so G is free of rank 1. Let Q be a generator of G. By definition of G, we have P ∈ G, so P is a multiple of Q. By the “if” part already proved, den(x(Q)) | den(x(P)). On the other hand, Q ∈ G, so den(x(P)) | den(x(Q)) by definition of G. Thus den(x(Q)) = den(x(P)). By Lemma 8, Q = ±P. If den(x(P)) | den(x(P′)), then P′ ∈ G = ZQ = ZP. ⊓ ⊔

Lemma 10. If I ⊆ O_{K} is a nonzero ideal, then there exists P ∈ rE(K) − {O} such that I | den(x(P)).

Proof. We use the notation of the previous proof. It suffices to show that G_{𝔭^{n}} is nontrivial. This holds since the image of F(𝔭^{⌈n/2⌉}O_{𝔭}) under F(𝔭O_{𝔭}) ≃ E_{1}(K_{𝔭}) is an open subgroup of E(K_{𝔭}), hence of finite index. ⊓ ⊔ Lemma 11. Suppose P ∈ rE(K) − {O} and m ∈ Z − {0}. Let t = x(P) and t′ = x(mP). Then den(t) | num((t/t′ − m^{2})^{2}).

Proof. Suppose that 𝔭 is a prime dividing den(t). Let v_{𝔭} : K_{𝔭} → Z ∪ {∞} denote the discrete valuation associated to 𝔭. Then n := v_{𝔭}(z(P)) is positive. Since x = z^{−2} + … is a Laurent series with coefficients in O_{K}, we have x(P) ∈ z(P)^{−2}(1+𝔭^{n}O_{𝔭}). Using the formal group, we see that z(mP) ∈ mz(P)+𝔭^{2n}O_{𝔭}; in particular v_{𝔭}(z(mP)) ≥ n, so x(mP) ∈ z(mP)^{−2}(1 + 𝔭^{n}O_{𝔭}). Thus

\frac{t}{t′} = \frac{x(P)}{x(mP)} ∈ (\frac{z(mP)}{z(P)})^{2} (1 + 𝔭^{n}O_{𝔭}) .

But \frac{z(mP)}{z(P)} ∈ m + 𝔭^{n}O_{𝔭}, so t/t′ ∈ m^{2} + 𝔭^{n}O_{𝔭}, so 𝔭^{n} | num(t/t′ − m^{2}). On the other hand, 𝔭^{2n} is the exact power of 𝔭 dividing den(t). Applying this argument to every 𝔭 proves den(t) | num((t/t′ − m^{2})^{2}). ⊓ ⊔

2.5 Diophantine definition of O_{F} over O_{K}

Lemma 12. With hypotheses as in Theorem 1, there exists a subset S ⊆ O_{K} such that S is diophantine over O_{K} and { m^{2} : m ∈ Z_{≥1} } ⊆ S ⊆ O_{F}.

Proof. Let c and c′ be the constants of Lemmas 4 and 5, respectively. By Lemma 8, if ℓ ∈ Z_{≥1} is sufficiently large, then

c′N_{K/Q}den(x(ℓP_{0}))^{1/2} > N_{K/Q}den(x(P_{0})^{c})

for all P_{0} ∈ rE(K) − {O}. Fix such an ℓ.

Let S be the set of μ ∈ O_{K} such that there exist P_{0}, P′, P′ ∈ rE(K) − {O} and t_{0}, t, t′ ∈ F such that

1. P = ℓP_{0}

2. t_{0} = x(P_{0}), t = x(P), t′ = x(P′)

3. (μ + 1)(μ + 2) … (μ + n) | den(t_{0})

4. den(t) | den(t′)

5. den(t) | num((t/t′ − μ)^{2})

It follows from Lemma 3 that S is diophantine over O_{K}.

Suppose m ∈ Z_{≥1}. We wish to show that μ := m^{2} belongs to S. By Lemma 10, there exists P_{0} ∈ rE(K) − {O} such that (μ + 1)(μ + 2) … (μ + n) | den(x(P_{0})). Let P = ℓP_{0} and P′ = mP. Let t_{0} = x(P_{0}), t = x(P), and t′ = x(P′). Then conditions (1), (2), and (3) in the definition of S are satisfied, and (4) and (5) follow from Lemmas 9 and 11, respectively. Hence m^{2} ∈ S.

Now suppose that μ ∈ S. We wish to show that μ ∈ O_{F}. Fix P_{0}, P, P′, t_{0}, t, t′ satisfying (1) through (5). By (4) and Lemma 9, P′ = mP for some nonzero m ∈ Z. By Lemma 11, den(t) | num((t/t′ − m^{2})^{2}). On the other hand, (5) says that den(t) | num((t/t′ − μ)^{2}). Therefore den(t)^{1/2} | num(μ − m^{2}) = (μ − m^{2}). (Note that each prime of O_{F} or of O_{K} that appears in den(t) must occur to an even power, since t is the x-coordinate of a point on y^{2} = x^{3} + ax + b. Hence den(t)^{1/2} is a well-defined ideal.) Write μ = ∑_{i=0}^{s−1} a_{i}α^{i} with a_{i} ∈ F. By (3) and Lemma 4, N_{K/Q}(Da_{i}) ≤ N_{K/Q}(den(t_{0}))^{c}. By definition of ℓ, we have N_{K/Q}(den(t_{0}))^{c} < c′N_{K/Q}den(t)^{1/2}. Combining these shows that the hypotheses of Lemma 5 hold for w = m^{2} and I = den(t)^{1/2} (as an ideal in O_{F}). Thus μ ∈ O_{F}. ⊓ ⊔

Proof of Theorem 1. Let S be the set given by Lemma 12. Then S_{1} := { s − s′ : s, s′ ∈ S } contains all odd integers at least 3, because of the identity (m + 1)^{2} − m^{2} = 2m + 1. Next, S_{2} := S_{1} ∪ { 4 − s : s ∈ S_{1} } contains all odd integers, and S_{3} := S_{2} ∪ { s + 1 : s ∈ S_{2} } contains Z. Let β_{1}, …, β_{b} be a Z-basis for O_{F}. Then S_{4} := { a_{1}β_{1} + ⋯ + a_{b}β_{b} : a_{1}, …, a_{b} ∈ S_{3} } contains O_{F}.

But S ⊆ O_{F}, so S_{i} ⊆ O_{F} for i = 1, 2, 3, 4. In particular, S_{4} = O_{F}. Also, S is diophantine over O_{K}, so each S_{i} is diophantine over O_{K}. In particular, O_{F} = S_{4} is diophantine over O_{K}. ⊓ ⊔

2.6 Questions

1. Is it true that for every number field K, there exists an elliptic curve E over Q such that rk E(Q) = rk E(K) = 1? The author would conjecture so. If so, then Hilbert’s Tenth Problem over O_{K} is undecidable for every number field K.

2. Can one weaken the hypotheses of Theorem 1 and give a diophantine definition of O_{F} over O_{K} using any elliptic curve E over K with rk E(K) = 1, not necessarily defined over F? Such elliptic curves may be easier to find. But our proof of Theorem 1 seems to require the fact that E is defined over F and has rk E(F) = 1, since Lemma 5 fails if the ideal I of O_{F} is instead assumed to be an ideal of O_{K}.

3. Can one prove an analogue of Theorem 1 in which the elliptic curve is replaced by an abelian variety?

References

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

[Dav53] Martin Davis, Arithmetical problems and recursively enumerable predicates, J. Symbolic Logic 18 (1953), 33–41.

[Den80] J. Denef, Diophantine sets over algebraic integer rings. II, Trans. Amer. Math. Soc. 257 (1980), no. 1, 227–236.

[DL78] J. Denef and L. Lipshitz, Diophantine sets over some rings of algebraic integers, J. London Math. Soc. (2) 18 (1978), no. 3, 385–391.

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

[Eis] Kirsten Eisenträger, Ph. D. thesis, University of California, Berkeley, in preparation.

[KR92] K. H. Kim and F. W. Roush, Diophantine undecidability of C(t_{1}, t_{2}), J. Algebra 150 (1992), no. 1, 35–44.

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

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

[MB] Laurent Moret-Bailly, paper in preparation, extending results presented in a lecture 18 June 2001 at a conference in honor of Michel Raynaud in Orsay, France.

[Phe88] Thanases Pheidas, Hilbert’s tenth problem for a class of rings of algebraic integers, Proc. Amer. Math. Soc. 104 (1988), no. 2, 611–620.

[Phe91] Thanases Pheidas, Hilbert’s tenth problem for fields of rational functions over finite fields, Invent. Math. 103 (1991), no. 1, 1–8.

[Phe00] Thanases Pheidas, An effort to prove that the existential theory of Q is undecidable, Hilbert’s tenth problem: relations with arithmetic and algebraic geometry (Ghent, 1999), Amer. Math. Soc., Providence, RI, 2000, pp. 237–252.

[PZ00] Thanases Pheidas and Karim Zahidi, Undecidability of existential theories of rings and fields: a survey, Hilbert’s tenth problem: relations with arithmetic and algebraic geometry (Ghent, 1999), Amer. Math. Soc., Providence, RI, 2000, pp. 49–105.

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

[Shl89] Alexandra Shlapentokh, Extension of Hilbert’s tenth problem to some algebraic number fields, Comm. Pure Appl. Math. 42 (1989), no. 7, 939– 962.

[Shl92] Alexandra Shlapentokh, Hilbert’s tenth problem for rings of algebraic functions in one variable over fields of constants of positive characteristic, Trans. Amer. Math. Soc. 333 (1992), no. 1, 275–298.

[Shl00a] Alexandra Shlapentokh, Hilbert’s tenth problem for algebraic function fields over infinite fields of constants of positive characteristic, Pacific J. Math. 193 (2000), no. 2, 463–500.

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

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

[Vid94] Carlos R. Videla, Hilbert’s tenth problem for rational function fields in characteristic 2, Proc. Amer. Math. Soc. 120 (1994), no. 1, 249–253.