Uniform bounds for the number of rational points of families of curves of genus 2^{⋆}

P. Gaudry^{1}, L. Kulesz^{2}, G. Matera^{2}, É. Schost^{3}

1 LIX, École Polytechnique, F-91128 Palaiseau Cedex, France,

                 gaudry@lix.polytechnique.fr.

2 Instituto de Desarrollo Humano Universidad Nacional de General Sarmiento

Campus Universitario, José M. Gutiérrez entre José L. Suárez y Verdi

(1613) Los Polvorines, Pcia. de Buenos Aires, Argentina

                {lkulesz,gmatera}@ungs.edu.ar.

3 Laboratoire GAGE, École Polytechnique, F-91128 Palaiseau cedex, France,

                schost@gage.polytechnique.fr.

Abstract We construct an infinite family {C_{a,b}}_{a,b∈ℚ} of curves of genus 2 defined over ℚ, with two independent morphisms to a family of elliptic curves {E_{a,b}}_{a,b∈ℚ}. When any of these elliptic curves E_{a,b} has rank 1 over ℚ, we obtain (modulo a conjecture of S. Lang, proved for special cases) a uniform bound for the number of rational points of the curve C_{a,b}, and an algorithm which finds all the rational points of the curve C_{a,b}.

1 Introduction

Diophantine geometry is mainly concerned with the search for integer or rational solutions of multivariate polynomial equation systems

f_{1}(X_{1}, …, X_{n}) = 0, …, f_{r}(X_{1}, …, X_{n}) = 0,  (1)

where f_{1}, …, f_{r} are polynomials in ℤ[X_{1}, …, X_{n}].

Typical problems of diophantine geometry are the following decision problems:

(i) Does there exist a solution (x_{1}, …, x_{n}) ∈ ℤ^{n} of the system (1)? (ii) Does there exist a solution (x_{1}, …, x_{n}) ∈ ℚ^{n} of the system (1)?

As the set of points

V := {x ∈ ℂ^{n} : f_{1}(x) = 0, …, f_{n}(x) = 0}

defines a ℚ–definable algebraic variety, we may rephrase the problems above in the following way:

⋆ Research was partially supported by the following Argentinian and French grants : UBA–CYT X198, PIP CONICET 4571, ECOS A99E06.

(i) Does there exist a point (x_{1}, …, x_{n}) ∈ ℤ^{n} in the variety V? (ii) Does there exist a point (x_{1}, …, x_{n}) ∈ ℚ^{n} in the variety V?

A point (x_{1}, …, x_{n}) ∈ ℚ^{n} ∩ V is called a rational point (or ℚ–rational point) of the variety V.

Problem (i) is the so–called Hilbert’s 10th Problem over ℤ and was proved to be undecidable by Y. Matiyasevich [Mat70]. On the other hand, it is not known whether there exists an algorithm which solves Problem (ii), known as Hilbert’s 10th Problem over ℚ (see [Poo01]). Let us finally remark that the first order theory over ℚ is also undecidable [Rob49].

Furthermore, it is not even known whether there exists an algorithm solving Problem (ii) in the case of algebraic plane curves, i.e., an algorithm answering the following question:

(ii′) Given a polynomial f ∈ ℚ[X, Y], does there exist a ℚ–rational point in the algebraic plane curve C := {(x, y) ∈ ℂ^{2} : f(x, y) = 0}?

Nevertheless, in the case of Problem (ii′) we have qualitative results such as Faltings’ Theorem [Fal83], which roughly asserts that the set of ℚ–rational points of a ℚ–definable smooth curve of genus at least 2 is finite. The genus of a curve C is a geometric invariant which measures how complicated are the singularities of the curve C. Curves of genus 0 are isomorphic to a conic, and curves of genus 1 with a rational point are elliptic curves (see Section 2).

Problem (i) and (ii) are related to the use of arithmetic circuits as data structures in computer science. Arithmetic circuits have been extensively used to modelize algebraic computations (see e.g. [Par95] or [BCS97]). In particular, the use of arithmetic circuits as data structures has been proved to be very useful for the design of efficient algorithms for the solution of multivariate parametric polynomial equation systems (see e.g. [KP96], [GHM^{+}98], [GHH^{+}97], [HKP^{+}00]).

The general context of parametric polynomial equation solving can be described as follows:

Let Γ (T, X) be a system of polynomial equations in the variables X := (X_{1}, …, X_{n}), depending on parameters T := (T_{1}, …, T_{m}). Thus any parameter point t ∈ ℂ^{m} determines a specific problem instance Γ (t, X). Let us assume that any such problem instance admits a finite, nonempty set of solutions belonging to ℂ^{n}. Let Y be a new variable. The output of a typical algorithm which “solves” the system is a (parametric) arithmetic circuit β(T, Y) of length L, which represents a univariate polynomial F (T, Y) describing the projection of the solution set of the parametric system Γ (T, X) on a suitable straight–line. We are interested in minimizing the length L of the circuit representation of the polynomial F (T, Y). This leads us to the following problem:

Let f ∈ ℚ[Y] be a given univariate polynomial. Find a short circuit with rational parameters which evaluates the polynomial f.

It is well–known that the vector of coefficients of a univariate polynomial f ∈ ℚ[Y] of degree d represented by an arithmetic circuit of lenght L belongs to a ℚ– definable algebraic variety of ℂ^{L^{O(1)}} (see e.g. [BCS97]). Therefore, our problem can be easily restated as the search for a rational solution of a suitable algebraic variety of ℂ^{L^{O(1)}}. The existence of an arithmetic circuit of length L representing the given polynomial f is then equivalent to the existence of a rational solution of a suitable instance of Problem (ii).

In connection with Problems (i) and (ii) and Faltings’ Theorem, we have the following conjecture of S. Lang [Lan86]:

Conjecture A. Let V a variety of general type defined over a number field 𝕂. Then, the set V (𝕂) of 𝕂-rational points of V is contained in a subvariety of V of codimension greater than 1.

Conjecture A in its full generality is very difficult to attack and we do not know of any attempt in this direction. On the other hand, L. Caporaso, J. Harris and B. Mazur showed the following consequence of this conjecture in the case of algebraic curves (see [CHM95], [CHM97]):

Theorem 1. If Conjecture A is true, then for any number field 𝕂 and any integer g ≥ 2, there exists an integer B(𝕂, g) such that any non–singular 𝕂– definable curve of genus g has at most B(𝕂, g) 𝕂-rational points.

This (conjectural) result generalizes Mordell’s Conjecture, now Faltings’ Theorem, which asserts that the set of 𝕂–rational points of any 𝕂–definable curve of genus ≥ 2 is finite.

We know very few results in the direction of Theorem 1. In [Kul99], the author constructs an infinite family of ℚ–definable curves of genus 2 which covers the elliptic curve E_{a} : Y^{2} = X^{3}−a^{2}X and obtains a uniform bound for the cardinality of the set of rational points of any member of this family.

In this article we obtain this kind of estimates for more general families of curves of genus two. Let us also remark that such estimates also implies the existence of an algorithm computing the set of rational points of any member of the families under consideration by exhaustive search. In order to simplify the exposition we will restrict ourselves to the analysis of ℚ–rational points of ℚ–definable curves, but proofs also hold for any number field 𝕂.

2 Generalities

In this section we recall some notions and results about elliptic curves, heights and morphisms. Details can be found in [Kna92] and [Sil86].

2.1 Elliptic Curves

A nonsingular homogeneous cubic polynomial F (X_{0}, X_{1}, X_{2}) of ℚ[X_{0}, X_{1}, X_{2}] defines a (projective) elliptic curve if it vanishes on at least one rational point. It can be shown that any elliptic curve E over ℚ is isomorphic to the projective closure of an affine curve of equation Y^{2} = X^{3} + AX + B for some A, B ∈ ℤ with 4A^{3} + 27B^{2} ≠ 0.

We denote by Δ(E) and j(E) the discriminant and the j–invariant of the elliptic curve E defined as follows:

Δ(E) = 16(4A^{3} − 27B^{2}), j(E) = 1728\frac{(4A)^{3}}{Δ(E)} .

Elliptic curves with the same j-invariant are isomorphic.

In 1922, L.J. Mordell proved the following theorem, conjectured by H. Poincaré:

Theorem 2. Let E be an elliptic curve over ℚ. Then E(ℚ) is a finitely generated abelian group.

We denote the torsion subgroup of E(ℚ) and the rank of the free part of E(ℚ) by E(ℚ)_{tors} and r_{ℚ}(E) respectively. In 1976, B. Mazur proved the following result, conjecture of Beppo Levi in 1908 [Maz78]:

Theorem 3. For any elliptic curve E defined over ℚ, the torsion subgroup E(ℚ)_{tors} is isomorphic to one of the following groups: ℤ/mℤ for m ≤ 10 or 12, or ℤ/2ℤ × ℤ/mℤ for m ≤ 4.

Let n ∈ ℤ \ {0} and P ∈ E. We denote by [n] the morphism of multiplication by n in E, namely:

\begin{aligned}[n] : & E & → & E \\ & P & ↦ & \underbrace{P + ⋯ + P}_{n times} . \end{aligned}

The degree of this morphism is n^{2}.

2.2 Heights

Let x be a rational number. Let us write x = \frac{x_{1}}{x_{2}} with x_{1} ∈ ℤ, x_{2} ∈ ℕ^{∗} and

gcd(x_{1}, x_{2}) = 1. We define the (naive) height of x, h(x), as the quantity h(x) := log(max{|x_{1}|, |x_{2}|}).

Let C be a ℚ–definable algebraic curve of 𝔸^{2} and P = (x, y) be a rational point of C(ℚ). We define the (naive) height of P, h(P), as h(P) = h(x).

Suppose now that the curve C has genus two. Then it has been shown that C is defined by an equation of the form Y^{2} = p(X), where p(X) is a polynomial of ℚ[X] of degree 6. If we assume further that there exists a ℚ–definable morphism mapping the curve C to a ℚ–definable elliptic curve E, then it can be shown that C is defined by an equation of the form Y^{2} = aX^{6} + bX^{4} + cX^{2} + d, where a, b, c, d ∈ ℚ (see [CaFl96]).

In this work we are going to consider the family of curves {C_{a,b}}_{a,b∈ℚ} defined by the equation Y^{2} = aX^{6} + bX^{4} + bX^{2} + a. Let us denote by E_{a,b} the elliptic curve defined by the equation Y^{2} = aX^{3} + bX^{2} + bX + a. Let ϕ_{1}, ϕ_{2} : ℂ^{2} → ℂ^{2} be the morphisms ϕ_{1}(X, Y) = (X^{2}, Y) and ϕ_{2}(X, Y) = (\frac{1}{X^{2}} , \frac{Y}{X^{3}} ). Then that for any (a, b) ∈ ℚ^{2} the morphisms ϕ_{1}, ϕ_{2} map the curve C_{a,b} to the elliptic curve E_{a,b}.

Let us observe that, from the definition of the (naive) height of a rational point of an algebraic curve, we easily deduce that, for any (a, b) ∈ ℚ^{2} and any P ∈ C_{a,b}, the following identity holds:

h(ϕ_{1}(P)) = h(ϕ_{2}(P)).  (2)

On the other hand, we have the notion of a canonical height of rational point of an elliptic curve E defined over ℚ. Let E be an elliptic curve defined over ℚ and let P be a rational point in E(ℚ). We define the canonical height of P, ĥ(P), by the formula ĥ(P) = lim_{n→∞} 4^{−n}h([2^{n}]P). The canonical height ĥ(P) satisfies the following properties:

Theorem 4. (i) ĥ(P) = h(P) + O(1). (ii) ĥ(mP) = m^{2}ĥ(P) for any m ∈ ℤ. (iii) < P, Q >= \frac{1}{2}(ĥ(P + Q) − ĥ(P) − ĥ(Q)) is bi–additive. (iv) Given n points P_{1}, …, P_{n} ∈ E(ℚ), P_{1}, …, P_{n} are independent if and only

if the n × n matrix with entries < P_{i}, P_{j} > is invertible.

In this paper we will make use of the following conjecture, due to S. Lang:

Conjecture B: There exists a constant c such that for any elliptic curve E defined over ℚ of discriminant Δ and any rational point P ∈ E(ℚ) of infinite order, the estimate ĥ(P) > ch(Δ) holds.

Let us remark that Lang’s Conjecture B has been proved to be true for elliptic curves with complex multiplication (see [Sil94]).

Theorem 4(i) asserts that for any point P ∈ E(ℚ) of an elliptic curve E defined over ℚ, the difference ĥ(P)−h(P) can be bounded by a constant depending only on the elliptic curve E. J. Silverman found the following explicit estimates for the difference ĥ(P) − h(P) in terms of the discriminant Δ and the j-invariant j of the elliptic curve E under consideration [Sil90]:

Theorem 5. If E is a ℚ-definable elliptic curve, then for any point P of E(ℚ) we have the estimates:

−\frac{1}{4}h(j) − \frac{1}{6}h(Δ) − 1.946 ≤ ĥ(P) − h(P) ≤ \frac{1}{6}h(Δ) + \frac{1}{6}h(j) + 2.14. (3)

2.3 Independent Morphisms

Let C be a nonsingular ℚ–definable curve of ℙ^{2}, let E be a ℚ–definable elliptic curve and let us assume that there exist l ℚ–definable morphisms ϕ_{1}, …, ϕ_{l} mapping C to E. These morphisms may be considered as elements of the ring k(C)^{2}, where k(C) denotes the field of rational functions of the curve C).

Definition 1. We say that the morphisms ϕ_{1}, …, ϕ_{l} are independent if the

relation ∑_{i=1}^{l} n_{i}ϕ_{i} = P ∈ E(ℚ) (i.e., ∑_{i=1}^{l} n_{i}ϕ_{i} is a constant in k(C)^{2}) implies

n_{i} = 0 for 1 ≤ i ≤ l.

In 1967, J.W. Cassels found a very useful characterization of the independence of morphisms [Cas68]:

Lemma 1. Let ϕ_{1}, …, ϕ_{l} be morphisms mapping a curve C to an elliptic curve E. Let D be the (l × l)–matrix whose (i, j)–entry is given by the expression:

\frac{1}{2}(d(ϕ_{i} + ϕ_{j}) − d(ϕ_{i}) − d(ϕ_{j}))

for 1 ≤ i, j ≤ l, where d(ψ) denotes the degree of the morphism ψ : ℂ → ℂ). Then the morphisms ϕ_{1}, …, ϕ_{l} are independent over ℚ if and only if det(D) ≠ 0 holds.

In the context of the curves C_{a,b}, a direct computation shows that (ϕ_{1}+ϕ_{2})(X, Y) = (f_{+}(X), Y g_{+}(X)) and (ϕ_{1} − ϕ_{2})(X, Y) = (f_{−}(X), Y g_{−}(X)) where

f_{+}(X) = \frac{−2aX^{3} − 3aX^{2} − 2aX + bX^{2}}{a(X^{4} + 2X^{3} + 2X^{2} + 2X + 1)},
f_{−}(X) = \frac{2aX^{3} − 3aX^{2} + 2aX + bX^{2}}{a(X^{4} − 2X^{3} + 2X^{2} − 2X + 1)}.

This shows that the degrees of the maps ϕ_{1}, ϕ_{2}, ϕ_{1} ± ϕ_{2} are respectively 2, 2, 4. By Lemma 1 we easily deduce that ϕ_{1} and ϕ_{2} are independent over ℚ.

3 Our Results

3.1 Dem’janenko–Manin’s Method

As expressed in Introduction, we know that a curve of genus ≥ 2 has at most finitely many rational points. Unfortunately, there remains unsolved the very difficult problem of the explicit computation of the set of rational points of a given curve. Up to now, there are two methods which allow us to compute this set:

1) The Chabauty’s method [Cha41], made effective by Coleman [Col85].

2) The Dem’janenko’s method [Dem68], generalized by Manin [Man69].

These methods apply to particular cases. More precisely, Chabauty’s method applies to curves of genus g whose Jacobian has rank < g over ℚ, and Dem’janenko– Manin’s method applies to curves that admit l independent morphisms to an elliptic curve of rank < l over ℚ.

Dem’janenko–Manin’s method relies on the following result (see [Dem68], [Cas68], [Ser89]):

Theorem 6. If ϕ_{1}, ..., ϕ_{l} are independent morphisms over ℚ and l > r_{ℚ}(E) holds, then C(ℚ) is a finite set, and all its elements can be effectively computed.

Let us consider the family of curves {C_{a,b}}_{a,b∈ℚ} defined in Section 2.2. We have shown that there exist two independent morphisms of degree two mapping the curve C_{a,b} to the elliptic curve E_{a,b}, namely, ϕ_{1}(X, Y) = (X^{2}, Y) and ϕ_{2}(X, Y) = (\frac{1}{X^{2}} , \frac{Y}{X^{3}} ). Let us assume that E_{a,b} has rank one over ℚ.

Now we sketch the proof of Theorem 6 for the family of curves {C_{a,b}}_{a,b∈ℚ}. Let us remark that the proof of Theorem 6 also provides an algorithm which finds all the rational points on any curve of the family {C_{a,b}}_{a,b∈ℚ}.

Let R be a generator of the free part of E_{a,b}(ℚ). For any point P in C_{a,b}(ℚ), there exist integers n, m and points T_{1}, T_{2} ∈ E_{a,b}(ℚ)_{tors} satisfying the following identities:

\begin{aligned}ϕ_{1}(P) & = & [n]R + T_{1} \\ ϕ_{2}(P) & = & [m]R + T_{2}. \end{aligned}

On the other hand, from Theorem 3 we deduce that the choice u = 8 · 9 · 7 · 5 implies the relation [u]T = 0 for any T ∈ E_{a,b}(ℚ)_{tors}. Then, we have

\begin{aligned}[u]ϕ_{1}(P) & = & [un]R, \\ [u]ϕ_{2}(P) & = & [um]R. \end{aligned}

Therefore,

\begin{aligned}ĥ(ϕ_{1}(P)) & = & n^{2}ĥ(R), \\ ĥ(ϕ_{2}(P)) & = & m^{2}ĥ(R). \end{aligned}  (4)

Let us observe that the following estimate holds:

\begin{aligned}|ĥ(ϕ_{1}(P)) − ĥ(ϕ_{2}(P))| & ≤ & |ĥ(ϕ_{1}(P)) − h(ϕ_{1}(P))| + |ĥ(ϕ_{2}(P)) − h(ϕ_{2}(P))|+ \\ & & +|h(ϕ_{1}(P)) − h(ϕ_{2}(P))|. \end{aligned}(5)

If ϕ_{1}(P)±ϕ_{2}(P) ∉ E_{a,b}(ℚ)_{tors}, Equations (2), (3), (4) and (5) imply the existence of a constant k (depending only on E_{a,b}, ϕ_{1} and ϕ_{2}) such that |m^{2} − n^{2}| < k. This implies the estimate

min(|n|, |m|) < \frac{k}{2} .  (6)

Therefore, we can compute all the ℚ–rational points of C satisfying the condition ϕ_{1}(P) ± ϕ_{2}(P) ∉ E(ℚ)_{tors}.

Now suppose ϕ_{1}(P) ± ϕ_{2}(P) ∈ E_{a,b}(ℚ)_{tors}. Taking into account that the morphisms ϕ_{1} and ϕ_{2} are independent over ℚ we conclude that there exists only a finite set of rational points P such that the condition ϕ_{1}(P)±ϕ_{2}(P) ∈ E_{a,b}(ℚ)_{tors} holds. These points can be determined by a direct computation. Then in this case we also obtain effectively all the ℚ–rational points of the curve C_{a,b}.

3.2 A Uniform Bound

Taking into account the identity h(ϕ_{1}(x, y)) = h(ϕ_{2}(x, y)) = h(x^{2}), from estimates (3), (5) and Theorem 5 we deduce the following estimates for any point P ∈ C_{a,b}(ℚ):

\begin{aligned}|ĥ(ϕ_{1}(P)) − ĥ(ϕ_{2}(P))| & ≤ & |ĥ(ϕ_{1}(P)) − h(ϕ_{1}(P))| + |ĥ(ϕ_{2}(P)) − h(ϕ_{2}(P))| \\ & ≤ & \frac{1}{2}h(j) + \frac{1}{3}h(Δ) + 4.28, \end{aligned} (7)

where j and Δ denote the invariant and the discriminant of the curve E_{a,b}.

Let us suppose that the rank of the elliptic curve E_{a,b}(ℚ) is 1. Let R be a generator of the free part of the group E_{a,b}(ℚ). Then, for any point P of C_{a,b}(ℚ), there exist integers n, m and points T_{1}, T_{2} ∈ E_{a,b}(ℚ)_{tors} such that the following estimates hold:

\begin{aligned}ϕ_{1}(P) & = & [n]R + T_{1}, \\ ϕ_{2}(P) & = & [m]R + T_{2}. \end{aligned}

Suppose now that n ≠ ±m holds. Then estimate (7) implies (n^{2} − m^{2})ĥ(R) ≤ \frac{1}{2}h(j) + \frac{1}{3}h(Δ) + 4.28. Therefore, from estimate (6) we deduce the following inequality:

min(|n|, |m|) < \frac{\frac{1}{2}h(j) + \frac{1}{3}h(Δ) + 4.28}{2ĥ(R)}.

On the other hand, if n = ±m, we have ϕ_{1}(P)±ϕ_{2}(P) ∈ E_{a,b}(ℚ)_{tors}. Taking into account that #(E_{a,b}(ℚ)_{tors}) ≤ 16 (see Theorem 3), d(ϕ_{1} ± ϕ_{2}) = 4 and that for any x-coordinate we have two y-coordinates, we deduce that there are at most 4 · 16 · 2 · 2 = 256 points P ∈ C_{a,b}(ℚ) such that ϕ_{1}(P) ± ϕ_{2}(P) ∈ E_{a,b}(ℚ)_{tors}. In conclusion, we obtain the following result:

Theorem 7. If the rank of the elliptic curve E_{a,b}(ℚ) is 1, the following estimate holds:

#(C_{a,b}(ℚ)) ≤ 64\frac{(\frac{1}{2}h(j) + \frac{1}{3}h(Δ) + 4.28)}{ĥ(R)} + 256.

Corollary 1. Under the assumption of the validity of Lang’s Conjecture B, we have the estimate:

#(C_{a,b}(ℚ)) ≤ 64\frac{(\frac{1}{2}h(j) + \frac{1}{3}h(Δ) + 4.28}{ch(Δ)} + 256 ≤ k_{1}h(j) + k_{2},

where k_{1} and k_{2} are universal constants independent of the curve C_{a,b}(ℚ).

Furthermore, if h(Δ) ≥ h(j), then we have

#(C_{a,b}(ℚ)) ≤ k_{3},

where k_{3} are a universal constant independent of the curve C_{a,b}(ℚ).

Let us remark that Corollary 1 generalizes the results of [Kul99]. In that work, the author considers the family of elliptic curves {E_{a}}_{a∈ℚ} defined by the equation Y^{2} = X^{3} − a^{2}X. The curve E_{a} has complex multiplication (hence Conjecture B holds), and its j–invariant is 1728 for any a ∈ ℚ.

By making the replacement X := −2/3 aX + 1/3 a, we see that the curve E_{a} is isomorphic to the curve of equation Y^{2} = −6 aX^{3} + 9aX^{2} + 9aX − 6 a and then, by Corollary 1, we obtain for any a ∈ ℚ a uniform bound for all the rational points of the genus 2–curve of equation Y^{2} = −2/3 aX^{6} + aX^{4} + aX^{2} − 2/3 a.

References

[BCS97] P. Bürgisser, M. Clausen, and M.A. Shokrollahi. Algebraic Complexity Theory, volume 315 of Grundlehren der mathematischen Wissenschaften. Springer, Berlin Heidelberg New York, 1997.

[CHM97] L. Caporaso, J. Harris, and B. Mazur. Uniformity of rational points. Journal of the AMS, 10(1): 1–35, 1997.

[CHM95] L. Caporaso, J. Harris, and B. Mazur. How many rational points can a curve have? In R.H. Dijkgraaf et al., editors, The moduli space of curves. Proceedings of the conference held on Texel Island, Netherlands, volume 129 of Progress in Mathematics, pages 13–31, Basel, 1995. Birkhäuser.

[Cas68] J.W.S. Cassels. On a theorem of Dem’janenko. J. London Math. Soc., 43:61–66, 1968.

[CaFl96] J.W.S. Cassels and E.V. Flynn. Prolegomena to a Middlebrow arithmetic of curves of genus 2, volume 230 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 1996.

[Cha41] C. Chabauty. Sur les points rationnels des variétés algébriques dont l’irrégularité est supérieure à la dimension. Comptes Rendus de l’Académie des Sciences de Paris, 212:1022–1024, 1941.

[Col85] R.F. Coleman. Effective Chabauty. Duke Math. Journal, 52:765–770, 1985.

[Dem68] V. Dem’janenko. Rational points of a class of algebraic curves. Trans. of the AMS, 66:246–272, 1968.

[Fal83] G. Faltings. Finiteness theorems for abelian varieties over number fields. Inventiones Math., 73(3):349–366, 1983.

[GHH^{+}97] M. Giusti, K. Hägele, J. Heintz, J.E. Morais, J.L. Montaña, and L.M. Pardo. Lower bounds for diophantine approximation. Journal of Pure and Applied Algebra, 117,118:277–317, 1997.

[GHM^{+}98] M. Giusti, J. Heintz, J.E. Morais, J. Morgenstern, and L.M. Pardo. Straight–line programs in geometric elimination theory. Journal of Pure and Applied Algebra, 124:101–146, 1998.

[HKP^{+}00] J. Heintz, T. Krick, S. Puddu, J. Sabia, and A. Waissbein. Deformation techniques for efficient polynomial equation solving. Journal of Complexity, 16(1):70–109, 2000.

[Kna92] A. Knapp. Elliptic Curves, volume 40 of Mathematical Notes. Princeton University Press, Princeton, NJ, 1992.

[KP96] T. Krick and L.M. Pardo. A computational method for diophantine approximation. In L. González-Vega and T. Recio, editors, Algorithms in Algebraic Geometry and Applications, Proceedings of MEGA’94, volume 143 of Progress in Mathematics, pages 193–254, Basel, 1996. Birkhäuser.

[Kul99] L. Kulesz. Application de la méthode de Dem’janenko–Manin à certaines familles de courbes de genre 2 et 3. Journal of Number Theory, 76(1):130– 146, 1999.

[Lan86] S. Lang. Hyperbolic and diophantine analysis, Bulletin of the AMS, 14(2): 159–205, 1986.

[Man69] Y. Manin. The p–torsion of elliptic curves is uniformly bounded (in russian). Izv. Akad. Nauk SSSR, 33:459–465, 1969.

[Mat70] Y. Matiyasevich. The Diophantineness of enumerable sets. (Russian) Dokl. Akad. Nauk SSSR, 191:279–282, 1970.

[Maz78] B. Mazur. Rational isogenies of prime degree. Inventiones Math., 44:129– 169, 1978.

[Par95] L.M. Pardo. How lower and upper complexity bounds meet in elimination theory. In G. Cohen, M. Giusti, and T. Mora, editors, Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings of AAECC– 11, volume 948 of Lecture Notes in Computer Science, pages 33–69, Berlin Heidelberg New York, 1995. Springer.

[Poo01] B. Poonen. Computing rational points on curves. To appear in Proceedings of the Millennial Conference on Number Theory, May 21–26, 2000.

[Rob49] J. Robinson. Definability and decision problems in arithmetic. Journal of Symbolic Logic, 14:98–114, 1949.

[Ser89] J.-P. Serre. Lectures on Mordell–Weil Theorem, volume E 15 of Aspects of Mathematics. Fried. Vieweg & Sohn, Braunschweig/Wiesbaden, 1989.

[Sil86] J.H. Silverman. The arithmetic of elliptic curves, volume 106 of Graduate Texts in Mathematics. Springer, Berlin Heidelberg New York, 1986.

[Sil90] J.H. Silverman. The difference between the Weil height and the canonical height on elliptic curves. Mathematics of Computation, 55(192):723–743, 1990.

[Sil94] J.H. Silverman. Advanced topics in the arithmetic of elliptic curves, volume 151 of Graduate Texts in Mathematics. Springer, Berlin Heidelberg New York, 1994.