Laurent Moret-Bailly

Alexandra Shlapentokh

DIOPHANTINE UNDECIDABILITY OF HOLOMORPHY RINGS OF FUNCTION FIELDS OF CHARACTERISTIC 0

Keywords: Mathematics Subject Classification. Primary 11U05; Secondary 03D35, 11G05 Hilbert's Tenth Problem, elliptic curves, Diophantine definability

Let K be a one-variable function field over a field of constants of characteristic 0. Let R be a holomorphy subring of K, not equal to K. We prove the following undecidability results for R: If K is recursive, then Hilbert's Tenth Problem is undecidable in R. In general, there exist x 1 , . . . , x n ∈ R such that there is no algorithm to tell whether a polynomial equation with coefficients in Q(x 1 , . . . , x n ) has solutions in R.

Introduction

The interest in the questions of existential definability and decidability over rings goes back to a question that was posed by Hilbert: given an arbitrary polynomial equation in several variables over Z, is there a uniform algorithm to determine whether such an equation has solutions in Z? This question, otherwise known as Hilbert's Tenth Problem ("HTP" in the future), has been answered negatively in the work of M. Davis, H. Putnam, J. Robinson and Yu. Matijasevich. (See [START_REF] Davis | Hilbert's tenth problem is unsolvable[END_REF], [START_REF] Davis | Hilbert's tenth problem. Diophantine equations: Positive aspects of a negative solution[END_REF] or [START_REF] Matiyasevich | Hilbert's Tenth Problem[END_REF] for the details of the solution of the original problem.) Since the time when this result was obtained, similar questions have been raised for other fields and rings. In other words, let R be a ring. Then, given an arbitrary polynomial equation in several variables over a recursive subring R 0 of R, is there a uniform algorithm to determine whether such an equation has solutions in R? (If R is countable and recursive then we can set R 0 = R.)

Depending on the nature of the ring the difficulty of answering the question can vary widely. By now, a lot of work has been done to solve the problem over some subrings of number fields and function fields, including the fields themselves in the case of function fields. However there remain quite a few open questions which at the moment seem intractable. Chief among these questions are arguably the Diophantine status of Q (and number fields in general), the rings of integers of an arbitrary number field, and an arbitrary function field of characteristic 0.

More details on the Diophantine problem over number fields and related issues can be found in [START_REF] Colliot-Thélène | Double fibres and double covers: Paucity of rational points[END_REF], [START_REF] Cornelissen | Division-ample sets and diophantine problem for rings of integers[END_REF], [START_REF] Cornelissen | Topology of diophantine sets: Remarks on Mazur's conjectures[END_REF], [START_REF] Denef | Hilbert's tenth problem for quadratic rings[END_REF], [START_REF] Denef | Diophantine sets of algebraic integers[END_REF], [START_REF] Denef | Diophantine sets over some rings of algebraic integers[END_REF], [START_REF] Mazur | The topology of rational points[END_REF], [START_REF] Mazur | Questions of decidability and undecidability in number theory[END_REF], [START_REF] Mazur | Speculation about the topology of rational points: An up-date[END_REF], [START_REF] Mazur | Open problems regarding rational points on curves and varieties[END_REF], [START_REF] Pheidas | Hilbert's tenth problem for a class of rings of algebraic integers[END_REF], [START_REF] Poonen | Hilbert's Tenth Problem and Mazur's conjecture for large subrings of Q[END_REF], [START_REF] Poonen | Diophantine definability of infinite discrete non-archimedean sets and diophantine models for large subrings of number fields[END_REF], [START_REF] Shapiro | Diophantine relations between algebraic number fields[END_REF], [START_REF] Shlapentokh | Extension of Hilbert's tenth problem to some algebraic number fields[END_REF], [START_REF] Shlapentokh | Diophantine classes of holomorphy rings of global fields[END_REF], [START_REF] Shlapentokh | Diophantine undecidability in some rings of algebraic numbers of totally real infinite extensions of Q[END_REF], [START_REF] Shlapentokh | Diophantine definability over some rings of algebraic numbers with infinite number of primes allowed in the denominator[END_REF], [START_REF] Shlapentokh | On diophantine definability and decidability in large subrings of totally real number fields and their totally complex extensions of degree 2[END_REF], [START_REF] Shlapentokh | A ring version of Mazur's conjecture on topology of rational points[END_REF], and [START_REF] Shlapentokh | On diophantine definability and decidability in some infinite totally real extensions of Q[END_REF]. Results concerning function fields of positive characteristic can be found in [START_REF] Denef | The diophantine problem for polynomial rings of positive characteristic[END_REF], [START_REF] Eisenträger | Hilbert's tenth problem for algebraic function fields of characteristic 2[END_REF], [START_REF] Pheidas | Hilbert's tenth problem for fields of rational functions over finite fields[END_REF], [START_REF] Pheidas | Endomorphisms of elliptic curves and undecidability in function fields of positive characteristic[END_REF], [START_REF] Shlapentokh | Diophantine undecidability for some function fields of infinite transcendence degree and positive characteristic[END_REF], [START_REF] Shlapentokh | Diophantine undecidability of algebraic function fields over finite fields of constants[END_REF], [START_REF] Shlapentokh | Diophantine undecidability of function fields of characteristic greater than 2 finitely generated over a field algebraic over a finite field[END_REF], and [START_REF] Videla | Hilbert's tenth problem for rational function fields in characteristic 2[END_REF]. Also, for a general reference on the subject we suggest [START_REF] Denef | Hilbert's tenth problem: relations with arithmetic and algebraic geometry[END_REF] and [START_REF] Shlapentokh | Hilbert's Tenth Problem: Diophantine Classes and Extensions to Global Fields[END_REF].

It turned out that solving HTP over function fields of characteristic 0 was more difficult than over function fields of positive characteristic. However we do know that HTP is undecidable over many function fields and rings of characteristic 0. In particular, we know that HTP is undecidable over fields of functions of finite transcendence degree over constant fields that are formally real or are subfields of finite extensions of Q p for some odd rational prime p. (These constant fields include number fields.) Further, we also know that HTP is undecidable over function fields of transcendence degree at least 2 whose field of constants is C. (See [START_REF] Denef | The diophantine problem for polynomial rings and fields of rational functions[END_REF], [START_REF] Eisenträger | Hilbert's tenth problem for function fields of varieties over C[END_REF], [START_REF] Eisenträger | Hilbert's Tenth Problem for function fields of varieties over number fields and p-adic fields[END_REF], [START_REF] Kim | Diophantine undecidability of C(t 1 , t 2 )[END_REF], [START_REF] Kim | Diophantine unsolvability over p-adic function fields[END_REF], [START_REF] Moret-Bailly | Elliptic curves and Hilbert's Tenth Problem for algebraic function fields over real and p-adic fields[END_REF], [START_REF] Zahidi | The existential theory of real hyperelliptic fields[END_REF] for more details on these field results). We also have a few ring results: for rings of S -integers and semi-local rings over any field of constants, and some results for rings "in the middle". (See [START_REF] Moret-Bailly | Elliptic curves and Hilbert's Tenth Problem for algebraic function fields over real and p-adic fields[END_REF], [START_REF] Shlapentokh | Diophantine undecidability for some holomorphy rings of algebraic functions of characteristic 0[END_REF], [START_REF] Shlapentokh | On diophantine decidability and definability in some rings of algebraic functions of characteristic 0[END_REF], [START_REF] Zahidi | Hilbert's tenth problem for rings of rational functions[END_REF] for more details on ring results.)

One of the problems which was solved over global fields was the construction of an existential definition of order. In other words there exists an existential definition in the language of rings of the set of elements of a given global field whose order at a fixed non-archimedean valuation is non-negative. Over function fields of characteristic 0 this was done successfully over a limited class of fields and the success depended heavily on the nature of the field of constants. As it turned out, an existential definition of order was one of the two ingredients used for showing the Diophantine undecidability of one variable function fields of characteristic 0. The other ingredient was an elliptic curve of rank 1. This plan was first implemented by Denef for the formally real rational function fields in [START_REF] Denef | The diophantine problem for polynomial rings and fields of rational functions[END_REF]. As will be described below, the issue of finding the right elliptic curve has been solved in the greatest possible generality by the first author in [START_REF] Moret-Bailly | Elliptic curves and Hilbert's Tenth Problem for algebraic function fields over real and p-adic fields[END_REF], but the issue of defining the order remains a stumbling block. So we can solve HTP precisely over those function fields in one variable where we can define the order. (See Corollary 10.3.3 of [START_REF] Moret-Bailly | Elliptic curves and Hilbert's Tenth Problem for algebraic function fields over real and p-adic fields[END_REF].)

To make the matters even more vexing, it is not hard to see that a definition of order together with the Diophantine undecidability of any semilocal subring of a field implies Diophantine undecidability of any ring "in the middle", i.e. any holomorphy ring, pretty much in the same fashion as the Diophantine undecidability of a domain follows from the Diophantine undecidability of its field of fractions. (Both cases also require being able to define the set of non-zero elements. Fortunately, we know how to do it in all cases of interest to us.) And thus the absence of a definition of order in a manner of speaking is responsible for the subject of this paper: the Diophantine undecidability of arbitrary holomorphy rings of characteristic 0 not equal to a field. The main results of this paper are stated below. Theorem 1. Let K be a countable recursive one variable function field of characteristic 0. Then Hilbert's Tenth Problem is not solvable over any holomorphy ring of K not equal to the whole field. Theorem 2. Let K be a one variable function field of characteristic 0 over a field of constants C. Then for any holomorphy ring of K not equal to the whole field, there exist elements x 1 , . . . , x n ∈ K \ C such that there is no algorithm to tell whether a polynomial equation with coefficients in Q(x 1 , . . . , x n ) has solutions in the ring. Remark 1. The reason for two separate statements has to do with the possibility that the function field K is not countable. That possibility forces us to examine more carefully what we can allow as coefficients of our polynomial equations. In the case of a countable field it is possible to allow every element of the field as a coefficient, but in the case the field is not countable we have to restrict the set of possible coefficients to a countable set. In our case this set will depend on the ring.

Remark 2. The case of holomorphy rings which are actually rings of S -integers, i.e. rings where only finitely many primes of the field are allowed in the pole divisors of the ring elements, has been treated by the second author in [START_REF] Shlapentokh | Hilbert's tenth problem for rings of algebraic functions of characteristic 0[END_REF]. While it is not explicitly discussed in the paper, the statement of the Theorem 2 follows from the construction of the equations. We should also like to note that the aforementioned paper of the second author, just as the present one, was a generalization of ideas of Denef from [START_REF] Denef | The diophantine problem for polynomial rings and fields of rational functions[END_REF]. In this paper Denef used a Pell equation to construct a model of integers instead of an elliptic curve. In view of this result we will always assume that the set of primes allowed in the pole divisors is infinite.

In some cases we will be able to prove a stronger result giving an existential definition of Z over an arbitrary holomorphy subring of the field not equal to the whole field. More specifically the following theorem holds. Theorem 3. Let K be any function field of characteristic 0 over a field of constants C. Assume there exists a subset C 0 of C such that C 0 contains Z and has a Diophantine definition over K. Then Z is existentially definable over any holomorphy ring of K not equal to the whole field. Remark 3. We know of many function fields of characteristic 0 where constants are existentially definable. They include function fields over ample fields of constants and other large fields, including fields which are algebraically closed. (See [START_REF] Koenigsmann | Defining transcendentals in function fields[END_REF], [START_REF] Pop | Elementary equivalence versus isomorphism[END_REF], and [START_REF] Shlapentokh | First-order definitions of rational functions and S -integers over holomorphy rings of algebraic functions of characteristic 0[END_REF] for various examples.)

The main idea behind the proofs of Theorems 1 -3 is rather simple. In a ring, where not all primes are inverted, there is a natural way to define the order using divisibility. So even if we cannot do it over a field, we can define the order over a ring (or come pretty close). We are now ready to proceed with the technical details.

Basic Diophantine Facts.

We start with giving precise definitions to the objects we are going to study, beginning with Diophantine sets.

Definition 2.1. Let R 0 ⊂ R be rings and let A ⊂ R m . A Diophantine definition of A over R, with coefficients in R 0 , is a finite collection of polynomials {f i,j (t 1 , . . . , t m , x 1 , . . . , x n ), i = 1, . . . , r, j = 1, . . . , s} ⊂ R 0 [t 1 , . . . , t m , x 1 , . . . , x n ] such that for any (t 1 , . . . , t m ) ∈ R m , we have the equivalence (t 1 , . . . , t m ) ∈ A ⇐⇒ ∃x 1 , . . . , x n ∈ R, s j=1 r i=1 f i,j (t 1 , . . . , t m , x 1 , . . . , x n ) = 0.
We say that A is Diophantine over R w.r.t. R 0 if it has such a Diophantine definition.

Remark 2.2. In general R 0 plays an auxiliary role and is often omitted, the default value being of course R. If R is a domain (which is generally the case in applications), then A has a Diophantine definition "with s = 1", i.e. consisting of a system of polynomial equations, without the disjunction operation.

If, moreover, the fraction field of R is not algebraically closed, we can even take r = s = 1; in other words, A has Diophantine definition consisting of one equation. Most authors take this as the definition of a Diophantine set. (See [START_REF] Davis | Hilbert's tenth problem. Diophantine equations: Positive aspects of a negative solution[END_REF] or [START_REF] Shlapentokh | Hilbert's Tenth Problem: Diophantine Classes and Extensions to Global Fields[END_REF], Chapter I for more details.)

We will be able to construct such a definition of Z over holomorphy subrings of our function field K provided a subset of the constant field containing Z has a Diophantine definition over K.

Definition 2.4. Let R be a ring and let R 0 be a recursive subring of R. We say that Hilbert's tenth problem is solvable in R, with coefficients in R 0 , if there is an algorithm taking as input a finite set of polynomials in R 0 [X 1 , . . . , X m ] (for some arbitrary m > 0) and telling whether they have a common zero in R m . We write H10(R, R 0 ) for this property. If R is recursive we take H10(R) to mean H10(R, R).

Remark 2.5. Assume H10(R, R 0 ) holds, and let A ⊂ R m be Diophantine w.r.t. R 0 , with given Diophantine definition (f i,j ) 1≤i≤r,1≤j≤s . Then A is a finite union of projections of sets A j (1 ≤ j ≤ s) defined by polynomial systems (with some extra variables). Since A = ∅ if and only if each A j is empty, there is an algorithm (taking (f i,j ) as input) telling whether A is empty or not. This of course could be taken as a definition for the H10 property.

With the same assumptions, let t be a point in R m 0 ⊂ R m . Then {t} is Diophantine w.r.t. R 0 , and we have that t ∈ A if and only if {t} ∩ A = ∅. Hence, the above discussion shows that there is an algorithm telling whether t belongs to A.

Remark 2.6. Just as in Remark 2.3, if R is a domain with non-algebraically closed fraction field, it suffices to check H10 for systems consisting of one polynomial: this is the traditional definition of the H10 property.

Proposition 2.7. Let R 1 ⊂ R 2 ⊂ R 3 be rings, with R 1 , R 2 and the inclusion R 1 ⊂ R 2 recursive.
Let I be an ideal of R 3 with the following properties:

• I is generated by finitely many elements of R 2 (in particular, it is Diophantine w

.r.t. R 2 ). • R 1 ∩ I = {0}. • The set R 1 + I ⊂ R 3 is Diophantine w.r.t. R 2 . Then H10(R 3 , R 2 ) implies H10(R 1 ). Proof. Assume H10(R 3 , R 2 ). Let D ⊂ R m 1 be defined by D := t ∈ R m 1 | ∀i ∈ {1, .
. . , r}, f i (t) = 0 where the f i 's are polynomials with coefficients in R 1 . We are looking for an algorithm telling whether D is empty.

Put ∆ := R 1 + I, which is Diophantine in R 3 by assumption, and define

B ⊂ R m 3 by B := t ∈ ∆ m | ∀i ∈ {1, . . . , r}, f i (t) ∈ I .
Clearly, B is Diophantine w.r.t. R 2 since ∆ and I are. Hence, by H10(R 3 , R 2 ), there is an algorithm telling whether B is empty, so it suffices to prove that D = ∅ if and only if B = ∅. The "if" part is trivial since D ⊂ B. Conversely, assume there exists some t ∈ B. By definition of ∆, there exists t 1 ∈ R m 1 which is congruent (coordinatewise) to t mod I. Then for each i we still have f i (t 1 ) ∈ I, but also

f i (t 1 ) ∈ R 1 since f i has coefficients in R 1 . Hence f i (t 1 ) = 0, which means that t 1 ∈ D, hence D = ∅. (In fact it is easy to see that B = D + IR m 3 and D = R m 1 ∩ B.)
We will also use the following standard trick:

Proposition 2.8. Let R 0 ⊂ R ⊂ R ′ be rings, with R 0 recursive. Assume that, as an Rmodule, R ′ has a finite basis B = {b 1 , . . . , b m } such that R 0 contains the following elements:

• the coordinates of 1 in B,

• the entries of the matrix of multiplication by b i in R ′ , for each i ∈ {1, . . . , m}. We identify R ′ with R m using B. Let D ⊂ R ′d be Diophantine over R ′ w.r.t. R 0 . Then:

(1) D (as a subset of R md ) is Diophantine over R (w.r.t. R 0 ).

(

) D ∩ R d ⊂ R d is Diophantine over R (w.r.t. R 0 ). 2
Proof. (1) is immediate from the assumptions. The first assumption also implies that the inclusion R ⊂ R ′ ∼ = R m identifies R with a Diophantine subset of R m w.r.t. R 0 , so the same property holds for the inclusion

R d ⊂ R ′ d ∼ = R md . Assertion (2) follows.
3. Basic Facts on Function Fields and Holomorphy Rings.

Definition 3.1. Let C be a field. Then a (one-variable) function field K over C is is a finite extension of the rational function field C(t). (Equivalently, it is a finitely generated extension of C of transcendence degree 1). For such a function field K, a prime of K is a nontrivial discrete valuation of K which is trivial on C. We denote by P K the set of such primes (abusingly omitting C from the notation). For p ∈ P K we adopt the traditional notation ord p for the corresponding normalized valuation and we denote by O(p) the associated valuation ring. If W is a non-empty subset of P K , we put

O K,W = p ∈W O(p) = h ∈ K | ∀p ∈ W we have that ord p h ≥ 0 .
O K,W is called a holomorphy ring of K.

Note that, with the above notations, taking W = ∅ would lead to the intersection of all rings O(p) (p ∈ P K ). This ring is the algebraic closure C ′ of C in K, a finite extension of C, and K is a function field over C ′ with the same set P K and rings O K,W as over C. Therefore, for the purposes of this paper we can always replace C by C ′ , i.e. assume C algebraically closed in K. (In other words, K is a regular extension of C).

If W = P K , then O K,W = K. Otherwise, O K,W is a Dedekind domain with fraction field K; its maximal ideals correspond bijectively to elements of P K \ W , via the map

p -→ I p := h ∈ O K,W | ord p h > 0 .
We shall derive Theorems 1, 2 and 3 from the following result: Theorem 3.2. Let K and W be as above, with ∅ = W = P K and char K = 0. Let p ∈ W be a prime of K, and let I p be the corresponding maximal ideal of O K,W . Then Z

+ I p is Diophantine in O K,W .
Proof of Theorems 1, 2 and 3 (from 3.2): For Theorems 1 and 2 we simply apply Proposition 2.7 with R 1 = Z and R 3 = O K,W . We take for R 2 the subring of R 3 generated by a finite subset containing a generating set for I p and all elements occurring in a Diophantine definition of Z+I p . The condition I p ∩Z = {0} is obvious since nonzero integers are invertible in C ⊂ O K,W .

For Theorem 3, we have Z ⊂ (Z + I p ) ∩ C 0 ⊂ (Z + I p ) ∩ C = Z (the last equality follows from C ∩ I p = {0}). Hence Z = (Z + I p ) ∩ C 0 is Diophantine.

From now on, we assume that C is algebraically closed in K, and that the characteristic is zero. If Ĉ is a finite extension of C, then K := Ĉ ⊗ C K is a finite extension of K, and a function field over Ĉ. Moreover, for W as above, the following three subrings of K are equal:

• Ĉ ⊗ C O K,W , • the integral closure of O K,W in K,
• the holomorphy ring O K, Ŵ where Ŵ is the set of primes of K inducing primes in W . The first description shows in particular that O K, Ŵ is a free module over O K,W , of rank [ Ĉ : C].

In addition, let p ∈ W be a prime of K. Then there exists a prime p ∈ Ŵ of K extending p, and the corresponding ideals

I p ⊂ O K,W and I p ⊂ O K, Ŵ satisfy I p = O K,W ∩ I p. It follows that Z + I p = O K,W ∩ (Z + I p). By Proposition 2.8 (2) we see that if Z + I p is Diophantine in O K, Ŵ , then Z + I p is Diophantine in O K,W .
In particular, to prove Theorem 3.2 for K, W , p, we may replace these data by K, Ŵ , p, respectively.

We shall use this remark as follows: take for Ĉ the residue field of p. We have a surjective morphism O K,W → Ĉ of C-algebras, hence (tensoring with Ĉ) a surjective Ĉ-morphism O K, Ŵ → Ĉ. Its kernel defines a prime p of K above p, which has degree one in the sense that its residue field is the constant field Ĉ of K. To summarize, we can always assume that the prime p of Theorem 3.2 has degree one.

As we have already mentioned above, our paper has two main inputs. The first one is contained in a paper of Denef (see [START_REF] Denef | The diophantine problem for polynomial rings and fields of rational functions[END_REF]) which constructs a rank one elliptic curve over any rational function field of characteristic 0 together with a way of generating integers. The second input is a result of the first author that allows the elliptic curve constructed by Denef to retain its nice properties under finite extensions. More specifically we will use the following result which is a consequence of Theorem 1.8 (ii) and Proposition 2.3.1 of [START_REF] Moret-Bailly | Elliptic curves and Hilbert's Tenth Problem for algebraic function fields over real and p-adic fields[END_REF].

Theorem 3.3. Let K be a function field of characteristic 0 over a field of constants C. Let p be a degree one prime of K. Let D be a divisor of K such that ord q D ∈ {0, 1} for any prime q of K, ord p D = 0, and the degree of D is at least 2g K + 2, where g K is the genus of K. Let F (T ) be a nonsingular cubic polynomial over Q such that the elliptic curve Y 2 = F (X) has no complex multiplication. Then there exists an x ∈ K such that its pole divisor is D, ord p x > 0, and the elliptic curve E x defined by the equation

(3.1) F 1 x Y 2 = F (X) has the property that E x (C(x)) = E x (K). Also E x (C(x)
) is of rank 1 generated by the point with affine coordinates ( 1 x , 1) ∈ E(C(x)) \ E(C) modulo 2-torsion. Proof. We need a slight refinement of Proposition 2.3.1 of [START_REF] Moret-Bailly | Elliptic curves and Hilbert's Tenth Problem for algebraic function fields over real and p-adic fields[END_REF]: Lemma 3.4. With the assumptions of Theorem 3.3, there exists a nonzero g ∈ K with the following properties:

• the divisor of zeros of g is D,

• g has only simple poles, and p is one of them, • g has simple ramification (i.e. in the extension K/C(g) no prime has ramification degree greater than 2).

Proof. The argument is classical and entirely similar to [START_REF] Moret-Bailly | Elliptic curves and Hilbert's Tenth Problem for algebraic function fields over real and p-adic fields[END_REF], 2.3.1. Put d := deg D. The linear system |D| is a projective space of dimension dg, and we identify D with a (Crational) point in it. Inside |D| we consider the following subvarieties, where Q (resp. ∆) denotes a variable point (resp. effective divisor):

• H = {divisors of the form p + ∆},

• Z 1 = {divisors of the form 2p + ∆},

• Z 2 = {divisors of the form p + 2Q + ∆}.

• Z 3 = {divisors of the form 3Q + ∆}, Clearly, none of these contains D, and H is a hyperplane because p has degree 1. It is proved in [START_REF] Moret-Bailly | Elliptic curves and Hilbert's Tenth Problem for algebraic function fields over real and p-adic fields[END_REF] that Z 3 has codimension ≥ 2 in |D|, and similar arguments easily show that the same holds for Z 1 and Z 2 . Hence we can find a line in |D| through the point D, defined over C and disjoint from Z 1 ∪ Z 2 ∪ Z 3 . This line meets H at a point D ′ . There is an element g of K with divisor D -D ′ , and this g has the required properties.

Let us return to the proof of Theorem 3.3. Clearly, by multiplying g by some nonzero constant c (in Q, if we wish) we may also choose g with branch locus disjoint from the inverse roots of F . This makes g admissible for D in the sense of [START_REF] Moret-Bailly | Elliptic curves and Hilbert's Tenth Problem for algebraic function fields over real and p-adic fields[END_REF], Definition 1.5.2. Further, it follows from Theorem 1.8 (ii) of [START_REF] Moret-Bailly | Elliptic curves and Hilbert's Tenth Problem for algebraic function fields over real and p-adic fields[END_REF] that by choosing c appropriately we may assume in addition that g is good, i.e. E g -1 (C(g)) = E g -1 (K). Now let x = g -1 : we now have that E x (C(x)) = E x (K), and the rest of the theorem follows from the assumption on F and from [START_REF] Denef | The diophantine problem for polynomial rings and fields of rational functions[END_REF] which describes E x (C(x)).

Diophantine Undecidability of Holomorphy Rings.

Notation and Assumptions 4.1. We start with a first notation set.

• Let K be a function field of characteristic 0 over a field of constants C.

• Let P K be the set of all primes of K.

• Let ∅ = W ⊂ P, W = P.

• Let p ∈ P \ W be a prime of degree 1. (By assumption, P \ W is not empty, and as explained in the previous section we may assume that it contains a prime of degree 1 by extending K). • Let g K be the genus of K.

• Assume that W contains infinitely many primes (in fact the present proof works whenever q∈W deg q ≥ 2g K + 2). As noted in Remark 2 of the introduction, the case where W is finite is settled in [START_REF] Shlapentokh | Hilbert's tenth problem for rings of algebraic functions of characteristic 0[END_REF]; more precisely, in that case, Z is Diophantine in O K,W (Theorem 3.1 of [START_REF] Shlapentokh | Hilbert's tenth problem for rings of algebraic functions of characteristic 0[END_REF]), hence our Theorem 3.2 also holds. • Let D = {q 1 , . . . , q 2g K +2 } be a set of distinct elements of W . (We only need the total degree of D to be at least 2g K + 2, in order to apply Theorem 3.3.) • Let x ∈ K be such that its pole divisor is i q i , ord p x > 0, and

E(K) = E(C(x)),
where E = E x is the elliptic curve defined in (3.1). (Such an x exists by Theorem 3.3).

Observe that x ∈ O K,W and therefore O K,W contains the polynomial ring C[x]. Moreover, the condition ord p x > 0 means that p lies above the ideal (x) of C[x]. In other words, for any z ∈ C(x) we have (4.2) ord p z = (ord p x)(ord 0 z)

where, in the right-hand side, z is viewed as a rational function of x.

Two elements a, b ∈ O K,W will be called coprime if they generate the unit ideal, i.e. there exist A, B ∈ O K,W such that (4.3) Aa + Bb = 1.

Note that we have "Gauss' Lemma": if a and b are coprime and a divides bc in O K,W , then a divides c.

Proposition 4.2. The set h ∈ O K,W | h = 0 is Diophantine over O K,W .
Proof. The proof is essentially a consequence of the Strong Approximation Theorem and can be found in [START_REF] Shlapentokh | Diophantine classes of holomorphy rings of global fields[END_REF].

Notation and Assumptions 4.3. We now add the following notation and assumptions to our list.

• Let P ∈ E(K) be the point whose affine coordinates derived from (3.1) are ( 1x , 1). • For nonzero n ∈ Z, let (x n , y n ) be the affine coordinates of [n]P derived from (3.1).

Since P ∈ E(C(x)) we have that x n and y n are rational functions of x. The following lemma shows how we will generate integers to show undecidability. Its proof can be found in Lemma 3.2 of [START_REF] Denef | The diophantine problem for polynomial rings and fields of rational functions[END_REF]. Proof. To prove (4.4) we note that a n β n = b n α n , hence (by Gauss' lemma) a n and α n divide each other in O K,W . In other words, ε := a n /α n is a unit.

To prove (4.5) and (4.6) we may and will assume, in view of (4.4), that a n = α n and b n = β n . Let w ∈ K be defined by ( 4 Let us now prove (4.6). Since a nn b n vanishes at 0 it follows that if b n vanishes at 0, so does a n . Since they are relatively prime polynomials, this cannot happen.

We also have a converse of sorts to (4.5) above. This clearly implies the result since both E and I are Diophantine (the former by 4.7, and the latter because it is a finitely generated ideal).

First, assume [START_REF] Colliot-Thélène | Double fibres and double covers: Paucity of rational points[END_REF]. If ξ ∈ I we are done. Otherwise, we may assume that ξ =: n is a nonzero integer since both (1) and ( 2) are invariant under adding an element of I to ξ. We construct a solution of (4.7) as follows. First, choose u, v, w, z so that u v = x n , z w = y n (first relation). Put a = α n and b = β n (as defined in 4.3): the second relation is satisified and we can find A and B satisfying the third. Finally by (4.5) the fourth relation holds since x ∈ I. Now assume that (2) holds. As before, (1) is trivial if ξ ∈ I. Otherwise, fix a solution (u, v, w, z, a, b, A, B) of (4.7). By definition of E there is a nonzero integer n such that x n = u v and y n = z w . We can then apply Lemmas 4.5 and 4.6 with a n = a, b n = b and c = ξ to conclude that ord p (ξn) > 0. In other words, ξ ∈ Z + I.

Remark 2 . 3 .

 23 Consider a Diophantine set A as in Definition 2.1.

Lemma 4 . 4 .Lemma 4 . 5 .

 4445 For any n ∈ Z >0 we have that ord p x xn ynn > 0. Using Lemma 4.4 and the definition of being coprime, one easily deduces the following lemma. Let n be a nonzero integer. Assume that xx n y n = a n b n where a n , b n ∈ O K,W are coprime. Then: a n = εα n and b n = εβ n for some ε ∈ O × K,W , (4.4) a nn b n = xw for some w ∈ O K,W , (4.5) ord p (b n ) = 0. (4.6)

  .5). Let us prove that w ∈ C[x]. Since a n and b n are in C[x] it suffices to prove that a nn b n (as a polynomial in x) vanishes at 0, which by (4.2) is equivalent to ord p (a nn b n ) > 0. This is clear from Lemma 4.4 since a nn b n = b n (x xn ynn) and b n ∈ C[x].

Lemma 4 . 6 .

 46 With the assumptions of 4.5, suppose for some c ∈ K we have that ord p (a nb n c) > 0. Then ord p (cn) > 0. Proof. The equation a nb n c = xw implies that ord p (a nb n c) > 0 as ord p x > 0 and p ∈ W . Since ord p (a nb n n) > 0 by Lemma 4.5, we conclude that ord p (b n (cn)) > 0. This proves the result by (4.6).Next we prove an easy lemma.

Lemma 4 . 7 . 1 x 8 K= 1 a

 47181 The setE = (u, v, w, z) ∈ (O K,W ) 4 vw = 0, ∃n ∈ Z \ {0} : x n = u v , y n = z w is Diophantine.Proof. Since we know how to define non-zero elements over any holomorphy ring and all the points of E(K) are in fact of the form [n]P + T where T is a 2-torsion point, we can easily define the setE even = (u ′ , v ′ , w ′ , z ′ ) ∈ (O K,W ) 4 ∃k ∈ Z \ {0} : x 2k = u ′ v ′ , y 2k = z ′ w ′ using Theorem 3.3. Then (u, v, w, z) ∈ E if and only if either (u, v, w, z) ∈ E even or u v , z w = u ′ v ′ , z ′ w ′ + E , 1 , where (u ′ , v ′ , w ′ , z ′ ) ∈ E even . Proof of Theorem 3.2: Put I = I p = {t ∈ O K,W | ord p (t) > 0},and let us prove thatZ + I is Diophantine in O K,W .Let ξ be an element of O K,W . We claim that the following are equivalent:(1) ξ ∈ Z + I, (2) either ξ ∈ I, or the following system has a solution (u, v, w, z, a, b, A, B) in Obξ ∈ I.

  • Since [n]P is not a torsion point, we have y n = 0 and we can write

	xx n y n	=	α n β n	,
	where α

n , β n ∈ C[x] are relatively prime polynomials in x (in particular, since they satisfy relation (4.3) in C[x] ⊂ O K,W , they are also coprime in O K,W ).

The second author has been partially supported by NSF grants DMS-0354907 and DMS-0650927.

1