Height Difference Bounds For Elliptic Curves over Number Fields

J. E. Cremona

School of Mathematical Sciences, University of Nottingham, University Park, Nottingham NG7 2RD, UK.

M. Prickett^{1}

School of Mathematical Sciences, University of Nottingham, University Park, Nottingham NG7 2RD, UK.

Samir Siksek^{2}

Department of Mathematics and Statistics, College of Science, Sultan Qaboos University, P.O. Box 36, Al-Khod 123, Oman

Abstract

Let E be an elliptic curve over a number field K. Let h be the logarithmic (or Weil) height on E and ĥ be the canonical height on E. Bounds for the difference h − ĥ are of tremendous theoretical and practical importance. It is possible to decompose h − ĥ as a weighted sum of continuous bounded functions Ψ_{υ} : E(K_{υ}) → ℝ over the set of places υ of K. A standard method for bounding h − ĥ, (due to Lang, and previously employed by Silverman) is to bound each function Ψ_{υ} and sum these local ‘contributions’.

In this paper we give simple formulae for the extreme values of Ψ_{υ} for nonarchimedean υ in terms of the Tamagawa index and Kodaira symbol of the curve at υ.

For real archimedean υ a method for sharply bounding Ψ_{υ} was previously given by Siksek (1990). We complement this by giving two methods for sharply bounding Ψ_{υ} for complex archimedean υ.

Key words: Elliptic curves, heights, canonical height, height bounds 1991 MSC: Primary 11G50, 11G05, Secondary 11G07, 14G05

Preprint submitted to Elsevier Science 13 February 2005

1 Introduction

Let K be a number field and let E be an elliptic curve defined over K. The canonical height ĥ is a quadratic form on E(K) ⊗ ℝ whose difference from the logarithmic height h is bounded on E(K). It is of tremendous importance both to the theoretical and to the explicit study of elliptic curves to have sharp bounds for the difference h − ĥ, particularly a small upper bound for this quantity. For example, explicit bounds on h − ĥ are essential for the effective proof of the Mordell-Weil Theorem. Good bounds for this difference are an important part of algorithms for determining Mordell-Weil bases of elliptic curves, and for determining integral points on elliptic curves.

Let M_{K} be the set of places of K. It is possible to decompose the difference h − ĥ as

h(P) − ĥ(P) = \frac{1}{[K : ℚ]} ∑_{υ∈M_{K}} n_{υ}Ψ_{υ}(P),  (1)

where the Ψ_{υ} are continuous bounded functions Ψ_{υ} : E(K_{υ}) → ℝ. For all but a finite set of places υ on K, the functions Ψ_{υ} vanish identically. A reasonable approach to bounding h − ĥ, suggested by Lang in [7], is to bound each of the functions Ψ_{υ} separately, and then to sum all of these local ‘contributions’ to obtain a bound for h − ĥ. This approach is adopted in Silverman’s paper [13], where he derives concise bounds for h − ĥ in terms of the coefficients and invariants of the curve. This Lang-Silverman approach is more conceptually attractive, and gives more precise bounds, than the earlier approach found in the papers (say) of Zimmer [17], and Demjanenko [4]; this earlier approach is based on estimating the difference 4h(P) − h(2P) and the use of Tate’s ‘telescoping’ series.

Given the importance of the problem, it is highly desirable to take the Lang-Silverman approach to its logical extreme: rather than asking for bounds for each function Ψ_{υ}, one should ask if the extrema of these real-valued functions can be determined. This idea first appears in a paper of Siksek [12], where he gives an algorithm - albeit a tedious one - for computing the suprema of the functions Ψ_{υ} for non-archimedean υ. For archimedean υ, the functions Ψ_{υ} are substantially more complicated and it seems hopeless to determine their extrema. It is however possible to write Ψ_{υ} = − ∑_{i=0}^{∞} 4^{−i−1} log Φ_{υ}(2^{i}P) for some (simpler, though still complicated) real-valued function Φ_{υ} : E(K_{υ}) → ℝ. Determining the extrema of Φ_{υ} gives sharp bounds for Ψ_{υ}. Siksek does this for

  Email addresses: John.Cremona@nottingham.ac.uk (J. E. Cremona),
martin.prickett@maths.nottingham.ac.uk (M. Prickett), siksek@squ.edu.om

(Samir Siksek). 1 Funded from 2000 to 2003 by a CASE studentship from the UK EPSRC 2 Funded by a grant from Sultan Qaboos University (IG/SCI/DOMS/02/06).

real archimedean υ, but gives a non-rigorous numerical method for estimating the extrema for complex archimedean υ.

In this paper, using an exhaustive analysis of possible reduction types of elliptic curves, we give simple formulae for the extreme values of Ψ_{υ} for nonarchimedean υ. These formulae depend only on the Kodaira symbol and Tamagawa index of the curve at υ. We complement Siksek’s determination of the extrema of Φ_{υ} for real archimedean υ by determining the extrema of this function for complex archimedean places υ: the locations of the extrema are given as simultaneous zeros of some pairs of real bivariate polynomials. Thus the extrema can be determined by solving these pairs of polynomials using Groebner bases. We also give a second, very fast algorithm, which is numerical but completely rigorous, for computing the extrema of Φ_{υ} to arbitrary desired accuracy (hence bounding Ψ_{υ} for complex υ).

The resulting bound for h − ĥ we obtain in this paper has all the virtues of the bound in [12], but none of the vices. To summarize, whilst the final bound for h − ĥ we give is numerically the same as that in [12], it has the following advantages

• better suited for theoretical investigations,

• (unlike [12]) entirely rigorous for number fields with complex embeddings,

• and almost trivial to implement/compute.

At the end of the paper we compute some examples and carry out a comparison between our bounds and those of Silverman.

The reader is warned at the outset that several normalizations of canonical and local heights appear in the literature; we say more on this in due course.

We are indebted to Professor Silverman for clarifying our ideas on local height normalizations and for useful comments on a previous version of this paper (including some of the history behind Proposition 5), to Professor Buchberger for useful discussions on numerical Groebner bases, and to Dr. Albaali for suggesting to us that the method of Lagrange multipliers might be useful in the proof of Lemma 12.

2 Statement of the Main Theorem

We fix once and for all the following notation.

K  a number field,
O_{K}  the ring of integers of K,
M_{K}  the set of all places of K,
M_{K}^{0}  the set of non-archimedean places of K,
M_{K}^{∞}  the set of archimedean places of K,
υ  a place of K,
K_{υ}  the completion of K at υ,
n_{υ}  the local degree [K_{υ} : ℚ_{υ}].

We will use the notation υ interchangeably for a place and for the associated normalized valuation. The following notation is relevant to places υ ∈ M_{K}^{0}.

k_{υ}  the residue field at υ,
O_{υ}  ring of integers in K_{υ},
q_{υ}  the cardinality of the residue field k_{υ}.

Let E be an elliptic curve given by the Weierstrass equation

E :  y^{2} + a_{1}xy + a_{3}y = x^{3} + a_{2}x^{2} + a_{4}x + a_{6},  (2)

where a_{1}, …, a_{6} ∈ O_{K}. For each place υ we denote by E_{0}(K_{υ}) the connected component of the identity in E(K_{υ}); for υ ∈ M_{K}^{0} this consists of the points of E(K_{υ}) with good reduction at υ. The Tamagawa index at υ, which is 1 for almost all υ including those where E has good reduction, is the index c_{υ} = [E(K_{υ}) : E_{0}(K_{υ})]. The finite quotient E(K_{υ})/E_{0}(K_{υ}) is called the component group of E at υ.

We define the usual associated constants (see [14, page 46]) as follows.

\begin{aligned}b_{2} & = a_{1}^{2} + 4a_{2}, \\ b_{4} & = 2a_{4} + a_{1}a_{3}, \\ b_{6} & = a_{3}^{2} + 4a_{6}, \\ b_{8} & = a_{1}^{2}a_{6} + 4a_{2}a_{6} − a_{1}a_{3}a_{4} + a_{2}a_{3}^{2} − a_{4}^{2}, \\ Δ & = −b_{2}^{2}b_{8} − 8b_{4}^{3} − 27b_{6}^{2} + 9b_{2}b_{4}b_{6}. \end{aligned}

Let

\begin{aligned}f(P) & = 4x(P)^{3} + b_{2}x(P)^{2} + 2b_{4}x(P) + b_{6}, \\ g(P) & = x(P)^{4} − b_{4}x(P)^{2} − 2b_{6}x(P) − b_{8}; \end{aligned}  (3)

Table 1 ; Values of α_{υ}

Kodaira type of E_{υ}^{min} at υ Tamagawa index c_{υ}  α_{υ}
any  1  0
I_{m}, m even  2 or m  m/4
I_{m}, m odd  m  (m^{2} − 1)/4m
III  2  1/2
IV  3  2/3
I_{0}^{∗}  2 or 4  1
I_{m}^{∗}  2  1
I_{m}^{∗}  4  (m + 4)/4
IV^{∗}  3  4/3
III^{∗}  2  3/2

so that x(2P) = g(P)/f(P). Define the function Φ_{υ} : E(K_{υ}) → ℝ by

Φ_{υ}(P) = \begin{cases}1 & if P = O, \\ \begin{matrix}max & \{|f(P)|_{υ}, |g(P)|_{υ}\} \\ max & \{1, |x(P)|_{υ}\} & 4 \end{matrix} & otherwise. \end{cases}  (4)

It is straightforward to see that Φ_{υ} is a continuous and hence bounded function on E(K_{υ}) (the boundedness follows immediately from the fact that E(K_{υ}) is compact with respect to the υ-adic topology). Define

ϵ_{υ}^{−1} = inf_{P ∈E(K_{υ})} Φ_{υ}(P),  δ_{υ}^{−1} = sup_{P ∈E(K_{υ})} Φ_{υ}(P),  (5)

where the exponents −1 have been chosen to simplify the formulae appearing later. In [12, Lemma 2.3] it shown that ϵ_{υ} exists (i.e. the infimum appearing in its definition is non-zero) and satisfies ϵ_{υ} ≥ 1.

For each valuation υ ∈ M_{K}^{0} let E_{υ}^{min} be a minimal model for E over K_{υ}, and let Δ_{υ}^{min} be the discriminant of E_{υ}^{min}. Thus we can take E_{υ}^{min} = E and Δ_{υ}^{min} = Δ for almost all υ ∈ M_{K}^{0}, and they are always equal if the model E is globally minimal. For υ ∈ M_{K}^{0} we define the constants α_{υ} according to the Kodaira type of E_{υ}^{min} and the Tamagawa index c_{υ} as in Table 1. We can now state our main theorem:

Theorem 1 For all P ∈ E(K),

\frac{1}{3[K : ℚ]} ∑_{υ∈M_{K}^{∞}} n_{υ} log δ_{υ} ≤ h(P) − ĥ(P) ≤ \frac{1}{3[K : ℚ]} ∑_{υ∈M_{K}^{∞}} n_{υ} log ϵ_{υ}

+ \frac{1}{[K : ℚ]} ∑_{υ∈M_{K}^{0}} (α_{υ} + \frac{1}{6} ord_{υ}(Δ/Δ_{υ}^{min})) log(q_{υ}).

The next theorem is a by-product of the proof of Theorem 1. In essence it says that the bounds are sharper if we restrict ourselves to points that have everywhere good reduction. Although this result is less general than Theorem 1, we suspect it may be useful for some applications.

Theorem 2 Suppose P ∈ E(K). If P ∈ E_{0}(K_{υ}) for all non-archimedean valuations υ then

\frac{1}{3[K : ℚ]} ∑_{υ∈M_{K}^{∞}} n_{υ} log δ_{υ} ≤ h(P) − ĥ(P) ≤ \frac{1}{3[K : ℚ]} ∑_{υ∈M_{K}^{∞}} n_{υ} log ϵ_{υ}

3 Definitions of Heights and Local Heights

In this section we review the definitions of logarithmic and canonical heights, as well as their decompositions into local components. If P ∈ E(K) then the naive heights of P and 2P are respectively given by

H_{K}(P) = ∏_{υ∈M_{K}} max {1, |x(P)|_{υ}}^{n_{υ}} , H_{K}(2P) = ∏_{υ∈M_{K}} max {|f(P)|_{υ}, |g(P)|_{υ}}^{n_{υ}} ,

where f, g are the polynomials defined in (3).

The logarithmic height is given by

h(P) = \frac{1}{[K : ℚ]} log H_{K}(P) = \frac{1}{[K : ℚ]} ∑_{υ∈M_{K}} n_{υ} log max \{1, |x(P)|_{υ}\} . (6)

It is then easy to see that for P ∈ E(K) we have

h(2P) − 4h(P) = \frac{1}{[K : ℚ]} ∑_{υ∈M_{K}} n_{υ} log Φ_{υ}(P),

where Φ_{υ} is defined in (4). Using the usual ‘telescoping’ series we see that

ĥ(P) = lim_{i→∞} \frac{1}{4^{i}} h(2^{i}P))
= h(P) + (\frac{1}{4}h(2P) − h(P)) + (\frac{1}{4^{2}} h(2^{2}P) − \frac{1}{4}h(2P)) + …
= \frac{1}{[K : ℚ]} ∑_{υ∈M_{k}} n_{υ} (log max \{1, |x(P)|_{υ}\} + ∑_{i=0}^{∞} \frac{1}{4^{i+1}} log Φ_{υ}(2^{i}P)) .

We define the local height λ_{υ} : E(K_{υ})\ {O} → ℝ by

λ_{υ}(P) = log max \{1, |x(P)|_{υ}\} + ∑_{i=0}^{∞} \frac{1}{4^{i+1}} log Φ_{υ}(2^{i}P).  (7)

The canonical and local heights are then related by the formula,

ĥ(P) = \frac{1}{[K : ℚ]} ∑_{υ∈M_{K}} n_{υ}λ_{υ}(P).  (8)

Let Ψ_{υ} : E(K_{υ}) → ℝ be given by

Ψ_{υ}(P) = \begin{cases}0 & if P = O, \\ log max \{1, |x(P)|_{υ}\} − λ_{υ}(P) & otherwise. \end{cases}  (9)

Combining (6) and (8) we deduce the validity of the decomposition of the height difference h − ĥ in (1).

Although the following proposition is not used later on, it is helpful to bear in mind and does motivate our approach to bounding h − ĥ.

Proposition 3 Suppose υ ∈ M_{K} (archimedean or non-archimedean). Ψ_{υ} is continuous bounded function on E(K_{υ}). Moreover, if υ ∈ M_{K}^{0} and E has good reduction at υ then Ψ_{υ} vanishes identically on E(K_{υ}).

Proof: By the explicit formula for the local height (7) the function Ψ_{υ} can be rewritten as

Ψ_{υ}(P) = − ∑_{i=0}^{∞} \frac{1}{4^{i+1}} log Φ_{υ}(2^{i}P).  (10)

We recall that log Φ_{υ} is continuous and bounded on E(K_{υ}). For this see the proof of [15, Lemma VI.1.2]. The continuity of Ψ_{υ} follows by the Weierstrass M-test, and its boundedness from the compactness of E(K_{υ}).

Suppose that υ ∈ M_{K}^{0}. If P has good reduction then its local height is simply given by λ_{υ}(P) = log max {1, |x(P)|_{υ}} (see for example [15, Theorem VI.4.1]). The proposition follows. □

4 An Important Warning about Canonical and Local Heights

It is crucial when comparing formulae for canonical heights and local heights to bear in mind the different normalizations of these quantities appearing in the literature.

We have chosen our normalization of the canonical height to agree with that taken in Cremona’s book [2]. This has the merit of being the most natural normalization for the conjectures of Birch and Swinnerton-Dyer (see [2, page 72]). Our canonical height is double that found in the papers and books of Silverman that we cite ([15], [16], [13]).

The situation with local heights is more complicated. Again our local heights agree with those in Cremona’s book. Moreover, if we denote by λ_{υ}^{SilP} the local height in Silverman’s paper [16], and by λ_{υ}^{SilB} the local height in Silverman’s book [15, Chapter IV], then these are related to our normalization by

λ_{υ} = 2λ_{υ}^{SilP} = 2λ_{υ}^{SilB} + \frac{1}{6} log|Δ_{υ}|.  (11)

The normalizations λ_{υ} and λ_{υ}^{SilP} are easier to use for explicit purposes. The normalizations λ_{υ}^{SilB} (and 2λ_{υ}^{SilB}) are better suited for theoretical purposes. In particular λ_{υ}^{SilB} has the advantage of being independent of the choice of Weierstrass model for the curve (see [15, Theorem VI.1.1]). We would like to record here the corresponding fact for our normalization, which can be readily deduced from the relationship expressed in (11).

Lemma 4 Suppose that E and E′ are different models for the same elliptic curve, and let λ_{υ} and λ′_{υ} be the corresponding local heights for valuation υ. Then

λ_{υ} = λ′_{υ} + \frac{1}{6} log|Δ/Δ′|_{υ},

where Δ and Δ′ are respectively the discriminants of the models E and E′.

5 The local height λ_{υ} for non-archimedean valuations

Throughout this section υ ∈ M_{K}^{0} is a non-archimedean valuation. Our aim in this section is to compile an exhaustive table of the values of local heights at the points of bad reduction. This is the most difficult step in the proof of Theorem 1. To do this we will need the following proposition, due to Silverman, which gives explicit formulae for non-archimedean local heights.

Proposition 5 (Silverman’s Explicit Formulae for Local Heights) Let υ ∈ M_{K}^{0}, and suppose that E is minimal at υ. Suppose that P ∈ E(K_{υ})\ {O}.

(a) The value of λ_{υ}(P) depends only on the image of P in E(K_{υ})/E_{0}(K_{υ}).

(b) If P ∈ E_{0}(K_{υ}) then

λ_{υ}(P) = log max {1, |x(P)|_{υ}} .

(c) Suppose E has Kodaira type I_{m} at υ. If P ∈ E(K_{υ})\E_{0}(K_{υ}) lies on the i-th component of E(K_{υ})/E_{0}(K_{υ}) then

λ_{υ}(P) = −\frac{i(m − i)}{m} \frac{log(q_{υ})}{n_{υ}}.

(d) If E has Kodaira type IV or IV^{∗} then

λ_{υ}(P) = −\frac{2}{3} ord_{υ}(2y(P) + a_{1}x(P) + a_{3})\frac{log(q_{υ})}{n_{υ}}

for all P ∉ E_{0}(K_{υ}).

(e) If E has Kodaira type III, III^{∗}, I_{0}^{∗}, or I_{m}^{∗} then

λ_{υ}(P) = −\frac{1}{4} ord_{υ}(3x(P)^{4} + b_{2}x(P)^{3} + 3b_{4}x(P)^{2} + 3b_{6}x(P) + b_{8})\frac{log(q_{υ})}{n_{υ}}

for all P ∉ E_{0}(K_{υ}).

Proof: See Silverman’s paper [16, pages 351–354]. Parts (a) and (b) are implicit in Néron’s original paper [10]; part (c) may have originally appeared in a letter from Tate to Serre, while parts (d) and (e) are essentially in Silverman’s thesis, subsequently published in [16]. □

Next we use the above explicit formulae to calculate an exhaustive table of values of local heights at points of bad reduction.

Proposition 6 Suppose that E is minimal at υ ∈ M_{K}^{0}, and that the Tamagawa index c_{υ} > 1. The values of λ_{υ}(P) as P ranges over E(K_{υ})\E_{0}(K_{υ}) (that is, the υ-adic points of bad reduction) are given by Table 2.

The remainder of this section is devoted to the proof of this proposition. In the next section we use it to deduce Theorem 1.

We need separate proofs for different Kodaira types and Tamagawa indices. In the course of the proof we will need to make unimodular changes of the Weierstrass model for E: these are standard changes of variable of the form x = x′ + r and y = y′ + sx′ + t where r, s, t are υ-adic integers. Note that

Table 2 ; Values of λ_{υ}

Kodaira type of E_{υ}^{min} at υ Tamagawa index c_{υ}  − (\frac{n_{υ}}{log q_{υ}} ) λ_{υ}
I_{m}, m even  m  i(m − i)/m i = 1, … m − 1
I_{m}, m even  2  m/4
I_{m}, m odd  m  i(m − i)/m i = 1, … m − 1
III  2  1/2
IV  3  2/3
I_{0}^{∗}  2 or 4  1
I_{m}^{∗}  2  1
I_{m}^{∗}  4  1, (m + 4)/4
IV^{∗}  3  4/3
III^{∗}  2  3/2

such changes do not affect the minimality of E nor its discriminant, and we deduce from Lemma 4 that the values of λ_{υ} are also unchanged by these model changes. In other words, for the purpose of proving the proposition, such changes are harmless.

Let π = π_{υ} be a uniformiser for υ; write ord for ord_{υ}. Recall our assumption that the Tamagawa index c_{υ} > 1.

Proof for Kodaira type I_{m}, m odd and c_{υ} = m: If the Kodaira type is I_{m} with m odd then there are in general two possibilities for the Tamagawa index c_{υ}: either c_{υ} = 1 or c_{υ} = m. Since we have excluded the former possibility, we may assume the latter holds. Then, from Proposition 5, we know that the possible values for λ_{υ} at the points of bad reduction are

−\frac{i(m − i)}{m} \frac{log(q_{υ})}{n_{υ}}

with i = 1, 2, …, m − 1 in agreement with the table. □

Proof for Kodaira type I_{m}, m even, c_{υ} = 2 or m: If the Kodaira type is I_{m} with m even then there are again two possibilities for the Tamagawa index c_{υ}; either c_{υ} = 2 or c_{υ} = m. For c_{υ} = m the proof is exactly as above.

Suppose now that c_{υ} = 2. Then the points with bad reduction have order 2 in E(K_{υ})/E_{0}(K_{υ}), and so lie in the m/2-th component. If P is a point of bad reduction then λ_{υ}(P) = −(m/4)(log q_{υ}/n_{υ}) as required.

Note that here we benefit from knowing that P ∈ E(K_{υ}) and not just E(\overline{K_{υ}}), which is cyclic of order m.

□

We will henceforth suppose that the reduction is additive and that c_{υ} > 1. We note from the table in [15, page 365] that the assumption c_{υ} > 1 excludes the possibility of Kodaira types II and II^{∗}.

Suppose that P ∈ E(K_{υ}) is a point of bad reduction. By making an appropriate translation we can suppose that P = (0, 0), and so a_{6} = 0. We will follow the steps of Tate’s algorithm as in [15, pages 366–369]. Since we have advanced beyond Kodaira types I_{0}, I_{m}, II, we see that

a_{6} = 0,  π | b_{2},  π^{2} | b_{6},  π^{2} | b_{8}.

As x(P) = y(P) = 0, Proposition 5 gives

λ_{υ}(P) = −\frac{2}{3} ord(a_{3})\frac{log(q_{υ})}{n_{υ}}

if the Kodaira type is IV or IV^{∗}, and

λ_{υ}(P) = −\frac{1}{4} ord(b_{8})\frac{log(q_{υ})}{n_{υ}}

if the Kodaira type is III, III^{∗}, I_{0}^{∗} or I_{m}^{∗}. For most of the remaining cases we content ourselves with evaluating ord(a_{3}) and ord(b_{8}), whichever is relevant, and leave the rest to the reader. We note that the assumption that c_{υ} > 1 forces c_{υ} = 2, 3, 3, 2 for Kodaira types III, IV, IV^{∗}, III^{∗} respectively. For Kodaira types I_{0}^{∗} and I_{m}^{∗}, if c_{υ} > 1 then c_{υ} = 2 or 4. We state this to demonstrate that we have covered all the possibilities in Table 2.

Proof of the Lemma for Kodaira type III and c_{υ} = 2: From Tate’s algorithm we know that π^{3} ∤ b_{8}. Hence ord(b_{8}) = 2. □

We resume following the steps of Tate’s algorithm. Thus suppose

a_{6} = 0,  π^{2} | b_{6},  π^{3} | b_{8}.

Proof for Kodaira type IV and c_{υ} = 3: From Tate’s algorithm we know that π^{3} ∤ b_{6}. But b_{6} = a_{3}^{2} + 4a_{6} = a_{3}^{2}. Thus ord_{υ}(a_{3}) = 1. □

Suppose now that π^{3} | b_{6}. Tate’s algorithm now (Step 6) requires us to make a certain change of variables, and since we have a_{6} = 0, it is sufficient to make a translation of the form y′ = y + αx (where α ∈ O_{υ} is the double root of Y^{2} + a_{1}Y − a_{2} ≡ 0 (mod π)). This translation does not move the point P = (0, 0), and we get

π | a_{1}, π | a_{2}, π^{2} | a_{3}, π^{2} | a_{4}, a_{6} = 0.

Next we must consider the factorization of the polynomial

P (T) = T^{3} + a_{2,1}T^{2} + a_{4,2}T,

modulo π, where by definition a_{i,r} := π^{−r}a_{i}.

Proof for Kodaira type I_{0}^{∗} with c_{υ} = 2 or 4: From Tate’s algorithm we know that the Kodaira type is I_{0}^{∗} if and only if P (T) has distinct roots modulo π. In particular π ∤ a_{4,2}, or equivalently ord(a_{4}) = 2. Since a_{6} = 0, we see that b_{8} = −a_{1}a_{3}a_{4} + a_{2}a_{3}^{2} − a_{4}^{2}. It follows from the assumptions so far that ord(b_{8}) = 4. □

Now if P (T) has a double root and a simple root modulo π then the Kodaira type is I_{m}^{∗}, and if it has a triple root modulo π then the Kodaira type is IV^{∗} or III^{∗}. The case I_{m}^{∗} is complicated and we will leave it to the end.

Thus suppose that P (T) has a triple root modulo π. This together with previous assumptions implies that

π | a_{1}, π^{2} | a_{2}, π^{2} | a_{3}, π^{3} | a_{4}, a_{6} = 0.

Proof for Kodaira type IV^{∗} and c_{υ} = 3: From Tate’s algorithm we know that this type occurs when Y^{2} + a_{3,2}Y has distinct roots modulo π. Thus ord(a_{3}) = 2. □

Now we suppose that Y^{2} + a_{3,2}Y has a double root modulo π; so π^{3} | a_{3}.

Proof for Kodaira type III^{∗} and c_{υ} = 2: From Tate’s algorithm, this case is equivalent to ord(a_{4}) = 3, which implies that ord(b_{8}) = 6. □

We are now left with proving the proposition for Kodaira type I_{m}^{∗}.

Proof for Kodaira type I_{m}^{∗}, m even, and c_{υ} = 2 or 4: We have already dealt with I_{0}^{∗}, so we may suppose that m ≥ 2. By step 7 of Tate’s algorithm in [15, pages 367–368] and its proof in [15, pages 373-374] we can make a translation such that

π | a_{1}, π || a_{2}, π^{\frac{m+4}{2}} | a_{3}, π^{\frac{m+4}{2}} | a_{4}, π^{m+3} | a_{6}.

(It is no longer convenient to maintain the assumption a_{6} = 0). Note that −a_{2,1} is a simple root, modulo π, of the polynomial X^{3} +a_{2,1}X^{2} +a_{4,2}X +a_{6,3}. Hence, by Hensel’s Lemma, this polynomial has a (unit) root α ∈ O_{υ}^{∗} such that α ≡ −a_{2,1} (mod π). Then P_{1} = (πα, 0) ∈ E(K_{υ}) has bad reduction.

We want to evaluate λ_{υ}(P_{1}) using the formula in Proposition 5. Now x(P_{1}) = πα ≡ −a_{2} (mod π^{2}). We also have π^{3} | b_{4}, π^{5} | b_{6} and π^{6} | b_{8}. Hence it follows for x = x(P_{1}) that

3x^{4} + b_{2}x^{3} + 3b_{4}x^{2} + 3b_{6}x + b_{8} ≡ (πα)^{3}(3πα + a_{1}^{2} + 4a_{2}) + 3b_{4}(πα)^{2}
≡ −(πα)^{4} (mod π^{5}),

which has valuation 4. Thus λ_{υ}(P_{1}) = − log(q_{υ})/n_{υ}, using Proposition 5.

Part (a) of Proposition 5 tells us that λ_{υ} factors through E(K_{υ})/E_{0}(K_{υ}). If c_{υ} = 2, then the only value λ_{υ} takes at points of bad reduction is − log(q_{υ})/n_{υ}. This proves the proposition when c_{υ} = 2 (and Kodaira type is I_{m}^{∗} with m even).

Suppose that c_{υ} = 4. There are now three nontrivial cosets of E_{0}(K_{υ}) in E(K_{υ}) to be considered, including the point P_{1} = (πα, 0) defined above. We make a further translation that simplifies our model for E, taking a point representing either of the two extra cosets to (0, 0). The special fiber of the Néron model in our case is defined by

a_{2,1}x_{μ}^{2} + a_{4,μ+1}x_{μ} + a_{6,2μ+1} ≡ 0 (mod π)

where m = 2μ − 2 and x_{μ} = xπ^{−μ} (see [15, page 374]). The fact that c_{υ} = 4 is equivalent to saying that the polynomial on the left has distinct roots modulo π, so these lift to roots in O_{υ}. The corresponding lifted values of x are the x-coordinates of the points representing the other two cosets in the component group.

Hence, making a suitable translation of x modulo π^{μ}, we may move either of these two roots to 0, so that P_{2} = (0, 0) is a new point of bad reduction. Note that this extra translation has not changed P_{1} essentially, since x(P_{1}) was only determined modulo π^{2}. After the extra translation, we have

π | a_{1}, π || a_{2}, π^{\frac{m+4}{2}} | a_{3}, π^{\frac{m+4}{2}} || a_{4}, a_{6} = 0.

It is straightforward to verify that ord(b_{8}) = m+4, so the corresponding value in our table is (m + 4)/4.

Since P_{1}, P_{2} are points of bad reduction that have differing local heights they must belong to different non-trivial cosets of E(K_{υ})/E_{0}(K_{υ}). Hence we know all of the values of λ_{υ} at the points of bad reduction. □

Proof for Kodaira type I_{m}^{∗}, m odd, and c_{υ} = 2 or 4: This case is similar to the previous case. We can make a translation such that

π | a_{1}, π || a_{2}, π^{\frac{m+3}{2}} | a_{3}, π^{\frac{m+5}{2}} | a_{4}, π^{m+3} | a_{6}.

Again we have a point P_{1} ∈ E(K_{υ}) (of order 2) such that P_{1} ≡ (−a_{2}, 0) (mod π^{2}) and again λ_{υ}(P_{1}) = − log(q_{υ})/n_{υ}. So if c_{υ} = 2 then we are finished.

Suppose that c_{υ} = 4. Now for m odd Tate’s algorithm tells us that the component group is cyclic (of order 4). Let P_{2} ∈ E(K_{υ}) represent the element of exact order 4 in E(K_{υ})/E_{0}(K_{υ}). Thankfully, Silverman has determined ([16, page 353]) that λ_{υ}(P_{2}) = −(m+4) log q_{υ}/4n_{υ}. The three non-trivial elements of the component group are represented by P_{1} and ±P_{2}. Since λ_{υ}(−P_{2}) = λ_{υ}(P_{2}), we see that the nonzero values for λ_{υ} are precisely

−\frac{log(q_{υ})}{n_{υ}}, −\frac{(m + 4)}{4} \frac{log(q_{υ})}{n_{υ}}.

This completes the proof of the proposition in this case. □

6 Proof of Theorem 1

In this section we deduce Theorem 1 from two propositions.

Proof of Theorem 1: Recall the decomposition of the height difference h−ĥ in (1) in terms of the functions Ψ_{υ}. Theorem 1 follows immediately from Propositions 7, 8 below. □

Proposition 7 Let υ ∈ M_{K} (archimedean or non-archimedean), and define ϵ_{υ} and δ_{υ} by (5). Then for all P ∈ E(K_{υ}) we have

\frac{log(δ_{υ})}{3} ≤ Ψ_{υ}(P) ≤ \frac{log(ϵ_{υ})}{3}.

Proof: The proposition follows immediately from the expansion of Ψ_{υ} in terms of Φ_{υ} given in (10) and the definitions of ϵ_{υ} and δ_{υ} in (5). □

Proposition 8 Suppose υ ∈ M_{K}^{0}. Then

inf_{P ∈E(K_{υ})} Ψ_{υ}(P) = 0,

and

sup_{P ∈E(K_{υ})} Ψ_{υ}(P) = (α_{υ} + \frac{1}{6} ord_{υ}(Δ/Δ_{υ}^{min})) \frac{log(q_{υ})}{n_{υ}}

= α_{υ} \frac{log(q_{υ})}{n_{υ}} − \frac{1}{6} log |Δ/Δ^{min}|_{υ} ,

where α_{υ} is given by Table 1, and Δ^{min} is the discriminant of a minimal model for E at υ.

Proof: First we make two claims.

Claim I.

Ψ_{υ}(P) = \{ \begin{matrix}0 & if P ∈ E_{0}(K_{υ}) \\ −λ_{υ}(P) & otherwise. \end{matrix}  (12)

To see this, recall that

λ_{υ}(P) = log max {1, |x(P)|_{υ}}

for all P ∈ E_{0}(K_{υ})\ {O}, by Proposition 5(a). It is then immediate from (9) that Ψ_{υ}(P) = 0 for all P ∈ E_{0}(K_{υ}). Suppose that P ∉ E_{0}(K_{υ}). Then |x(P)|_{υ} ≤ 1 (since all the points with |x(P)|_{υ} > 1 have good reduction). From the definition of Ψ_{υ} in (9) we deduce that Ψ_{υ}(P) = −λ_{υ}(P). This proves our claim.

Claim II. The proposition is true under the assumption that E is minimal at υ. In fact a little more is true: if E is minimal at non-archimedean place υ, then

inf_{P ∈E(K_{υ})} Ψ_{υ}(P) = 0,

with the infimum attained at all points P ∈ E_{0}(K_{υ}). Moreover,

sup_{P ∈E(K_{υ})} Ψ_{υ}(P) = α_{υ} \frac{log(q_{υ})}{n_{υ}},

where α_{υ} is given by Table 1, with the supremum attained at some point P ∈ E(K_{v}) of bad reduction.

To see this, recall that Proposition 6 gives us all the values of λ_{υ}(P) for points of bad reduction. From this and (12), we are able to write down for each Tamagawa index and reduction type a complete list of values of Ψ_{υ}(P) for P ∈ E(K_{υ}), and so verify the claimed infima and suprema. We leave the details to the reader. This proves our second claim.

Since we have already covered the minimal case, we may suppose that the model E is non-minimal. Thus there is a change of variable

x = u^{2}x′ + r, y = u^{3}y′ + sx′ + t,

with u, r, s, t ∈ O_{υ} and ord_{υ}(u) ≥ 1, such that the resulting model E^{min} is minimal. Denote by Ψ′_{υ} the function corresponding to Ψ_{υ} on E^{min}, and by Δ^{min} the discriminant of E^{min}, so that Δ = u^{12}Δ^{min}. Then, from Lemma 4 and the definition of Ψ_{υ} in (9),

Ψ_{υ}(P) = Ψ′_{υ}(P) + log (\frac{max\{1, |u^{2}x′(P) + r|_{υ}\}}{max\{1, |x′(P)|_{υ}\}}) − \frac{1}{6} log |Δ/Δ^{min}|_{υ} .

It is helpful to take a closer look at the middle term of the right-hand side of the above equation. It is a straightforward exercise to show that

inf_{P ∈E(K_{υ})} log (\frac{max\{1, |u^{2}x′(P) + r|_{υ}\}}{max\{1, |x′(P)|_{υ}\}}) = log|u^{2}|_{υ},

with the infimum attained for large x′(P), and also

sup_{P ∈E(K_{υ})} log (\frac{max\{1, |u^{2}x′(P) + r|_{υ}\}}{max\{1, |x′(P)|_{υ}\}}) = 0,

with the supremum attained whenever |x′(P)|_{υ} ≤ 1.

Now the infimum of Ψ′_{υ}, which is 0 by the case already proved, is attained for points with large |x′(P)|_{υ} (since these have good reduction); and the supremum of Ψ′_{υ}, which is α_{υ} log(q_{υ})/n_{υ}, is attained at some point P with |x′(P)|_{υ} ≤ 1. We deduce that

inf_{P ∈E(K_{υ})} Ψ_{υ}(P) = log|u^{2}|_{υ} − \frac{1}{6} log |Δ/Δ^{min}|_{υ}
= −\frac{1}{6} log |(u^{−12}Δ/Δ^{min})|_{υ} = 0,

and

sup_{P ∈E(K_{υ})} Ψ_{υ}(P) = α_{υ} \frac{log(q_{υ})}{n_{υ}} − \frac{1}{6} log |Δ/Δ^{min}|_{υ}

as required. □

7 The Real Contributions

To be able to compute the bounds in our Theorem 1 we need a method for determining δ_{υ} and ϵ_{υ} for archimedean places υ. In this section we give such a method for real places υ. Thus suppose that υ is a real place; in other words, there is an embedding σ : K ↪ ℝ such that |a|_{υ} = |σ(a)| for all a ∈ K. To ease the notation, we will henceforth identify K with its image in ℝ under σ, and thus view elements of K as real numbers.

Write

\begin{aligned}f(x) & = & 4x^{3} + b_{2}x^{2} + 2b_{4}x + b_{6}, \\ g(x) & = & x^{4} − b_{4}x^{2} − 2b_{6}x − b_{8}. \end{aligned}

and let

F (x) = x^{4}f(1/x), G(x) = x^{4}g(1/x).

Define

\begin{aligned}D & = & \{x ∈ [−1, 1] : f(x) ≥ 0\} , \\ D′ & = & \{x ∈ [−1, 1] : F (x) ≥ 0\} . \end{aligned}

The following lemma is elementary.

Lemma 9 Define constants e, e′ by

e = inf_{x∈D} max {|f(x)|, |g(x)|} ,
e′ = inf_{x∈D′} max {|F (x)|, |G(x)|} ,

and constants d, d′ by

d = sup_{x∈D} max {|f(x)|, |g(x)|} ,
d′ = sup_{x∈D′} max {|F (x)|, |G(x)|} .

Then ϵ_{υ} = min(e, e′)^{−1} and δ_{υ} = max(d, d′)^{−1}.

Proof: The lemma follows from the definitions of ϵ_{υ} and δ_{υ} made in (5) and the fact that (x, y) ∈ E(ℝ) if and only if f(x) = (2y + a_{1}x + a_{3})^{2}. □

It is clear that D, D′ are finite unions of closed intervals. Moreover the problem of determining δ_{υ} and ϵ_{υ} has been reduced to the problem of determining d, d′, e, e′. This is straightforward by the following lemma.

Lemma 10 If P, Q are continuous real functions and I ⊂ ℝ is a closed interval, then the extrema of the continuous function max {|P (X)|, |Q(X)|} over the interval I are attained at one of the following points:

(i) an end point of I; (ii) one of the roots of P + Q, P − Q in the interval I; (iii) a turning point of one of the functions P, Q.

Proof: We simply note that at any point in I not listed in (i) or (ii), the function max {|P (X)|, |Q(X)|} is equal to one of ±P, ±Q and its supremum or infimum must be a local supremum or infimum of P, or Q. □

It is easy to turn this lemma into an algorithm. To compute e, for example, let S be the set of zeros of f, g, f′, g′, and f ± g, together with {±1}. Then e is the minimum of max {|f(x)|, |g(x)|} over those x ∈ S for which |x| ≤ 1 and f(x) ≥ 0.

8 The Complex Contributions I. Groebner Approach

In this and the next section we consider the determination of δ_{υ} and ϵ_{υ} for complex archimedean places υ. As in the previous section, we regard all elements of K as lying in ℂ via a suitable embedding.

Let f, g, F, G be as in the previous section, and D = {z ∈ ℂ : |z| ≤ 1} be the unit disc. If P, Q are polynomials with complex coefficients, we define

α(P, Q) = inf_{z∈D} max {|P (z)|, |Q(z)|} ,
β(P, Q) = sup_{z∈D} max {|P (z)|, |Q(z)|} .

We note in passing that since D is compact, the infimum and supremum exist and are attained at some points of D.

The following lemma is elementary.

Lemma 11 With notation as above

ϵ_{υ} = min(α(f, g), α(F, G))^{−1}, δ_{υ} = max(β(f, g), β(F, G))^{−1}.

In this section we give a method for computing α(P, Q), β(P, Q) for polynomials P, Q with complex coefficients that do not vanish simultaneously (it is noted that this condition is satisfied by both of our pairs f, g and F, G). The method is based on real multivariate calculus and Groebner bases. In the next section we give an alternative method for computing the complex contributions using a fairly simple numerical method based on repeated quadrisection of the unit disc D (with fast convergence).

So let P, Q ∈ ℂ[z] be polynomials with complex coefficients that do not vanish simultaneously. Write z = x + iy and P = P_{1} + iP_{2}, Q = Q_{1} + iQ_{2} where P_{j}, Q_{j} are real polynomials in x, y.

Lemma 12 The supremum of the function max {|P (z)|, |Q(z)|} on the region D is attained at a point z_{0} = x_{0} + iy_{0} that satisfies one of the following pairs of simultaneous equations:

(i) y \frac{∂(P_{1}^{2} + P_{2}^{2})}{∂x} − x\frac{∂(P_{1}^{2} + P_{2}^{2})}{∂y} = 0, x^{2} + y^{2} = 1,

(ii) y \frac{∂(Q_{1}^{2} + Q_{2}^{2})}{∂x} − x\frac{∂(Q_{1}^{2} + Q_{2}^{2})}{∂y} = 0, x^{2} + y^{2} = 1.

The infimum of the function max {|P (z)|, |Q(z)|} on D is attained at a point z_{0} = x_{0} + iy_{0} such that one of the following holds:

(a) the point z_{0} satisfies one of the above pairs of simultaneous equations (i) or (ii),

(b) the point z_{0} satisfies the simultaneous equations

P_{1}^{2} + P_{2}^{2} = Q_{1}^{2} + Q_{2}^{2}, x^{2} + y^{2} = 1,

(c) the point z_{0} belongs to the interior x^{2} + y^{2} < 1 and satisfies these two simultaneous equations:

P_{1}^{2}+P_{2}^{2} = Q_{1}^{2}+Q_{2}^{2}, \frac{∂(P_{1}^{2} + P_{2}^{2})}{∂x} \frac{∂(Q_{1}^{2} + Q_{2}^{2})}{∂y}−\frac{∂(P_{1}^{2} + P_{2}^{2})}{∂y} \frac{∂(Q_{1}^{2} + Q_{2}^{2})}{∂x} = 0.

Proof: Note that

sup max {|P (z)|, |Q(z)|} = max {sup|P (z)|, sup|Q(z)|} ,

and, by the maximum modulus theorem [1, page 134], the suprema of |P (z)| and |Q(z)| are attained at the boundary x^{2} + y^{2} = 1. Suppose that the supremum is attained at some point z_{0} = x_{0} + iy_{0}. Then z_{0} must be a local supremum for either |P (z)| or |Q(z)| restricted to the unit circle. Let us suppose that it is a local supremum for |P (z)| restricted to the unit circle. Then (x_{0}, y_{0}) represents a local maximum for the function P_{1}^{2} + P_{2}^{2} on the (analytic) curve x^{2} + y^{2} = 1. By the method of Lagrange multipliers, the two vectors ∇(P_{1}^{2} + P_{2}^{2}), ∇(x^{2} + y^{2} − 1) must be linearly dependent when evaluated at (x_{0}, y_{0}). It is then easy to verify that (x_{0}, y_{0}) satisfies

y \frac{∂(P_{1}^{2} + P_{2}^{2})}{∂x} − x\frac{∂(P_{1}^{2} + P_{2}^{2})}{∂y} = 0.

Thus (x_{0}, y_{0}) satisfies (i). Similarly, if z_{0} is a local supremum for |Q(z)| restricted to the unit circle then (x_{0}, y_{0}) satisfies (ii). This proves the first part of the Lemma.

For the second part, again suppose that the infimum is attained at some point z_{0} = x_{0}+iy_{0}. Suppose first that z_{0} belongs to the boundary. If |P (z_{0})| = |Q(z_{0})| then (b) is satisfied. Suppose that |P (z_{0})| > |Q(z_{0})|. Then in some small neighbourhood of z_{0}, we see that max {|P (z)|, |Q(z)|} = |P (z)| and so z_{0} must be a local infimum of the function |P (z)| restricted to the unit circle. By a trivial modification of the above argument we show that z_{0} = x_{0} + iy_{0} satisfies (i). Similarly if |P (z_{0})|< |Q(z_{0})| then (ii) is satisfied. Thus either (a) or (b) is satisfied if z_{0} belongs to the boundary.

We are now left to consider the case where z_{0} belongs to the interior of D. We want to first show that |P (z_{0})| = |Q(z_{0})|. Suppose not; without loss of generality we may suppose that |P (z_{0})| > |Q(z_{0})|. Then for some small disc around z_{0} and contained in D we have |P (z)| > |Q(z)| implying max {|P (z)|, |Q(z)|} = |P (z)|. Thus the holomorphic function P attains a nonzero infimum that is in the interior of this small disc. Applying the maximum modulus theorem to P^{−1} immediately gives a contradiction.

Hence |P (z_{0})| = |Q(z_{0})|. Consider the (analytic) curve in ℝ^{2} defined by the equation P_{1}^{2} + P_{2}^{2} = Q_{1}^{2} + Q_{2}^{2}. Then we are saying that (x_{0}, y_{0}) is on this curve and moreover is a point where the infimum of the function

max {P_{1}^{2} + P_{2}^{2}, Q_{1}^{2} + Q_{2}^{2}} = P_{1}^{2} + P_{2}^{2}

is attained. The proof can now be completed using Lagrange multipliers as before. □

Thus from the lemma, to compute α(P, Q), β(P, Q), we need to solve a few pairs of polynomial equations in two variables. In theory these can be solved using elimination theory. There are two alternatives here:

(1) The first is to recall that our coefficients are contained in a number field and do the elimination using Groebner bases algorithms over this field, to obtain the points in some extension field, and then specialize using the complex embeddings. We have found this (exact arithmetic) approach extremely slow in practice. Note that while P, Q ∈ K[z], their real and imaginary parts P_{j}, Q_{j} are in general defined over a larger field K(i).

(2) The second approach is to use numerical (that is floating-point) Groebner basis packages available in some computer algebra systems. To the best of our knowledge, the theory behind these floating-point packages is not documented and they may not be entirely rigorous. Thus there is perhaps a risk of missing a solution.

Fortunately, there is now a rigorous numerical Groebner basis algorithm due to Aleksey Kondratyev [6] which could be used for our purpose.

9 The Complex Contributions II. The Repeated Quadrisection Approach

Recall that our objective is to compute log(ϵ_{υ}) and log(δ_{υ}) to a certain desired accuracy. Suppose μ > 0 is given. We give an algorithm to compute, for any pair of polynomials P, Q with complex coefficients that do not vanish simultaneously, constants α^{∗}(P, Q), β^{∗}(P, Q) such that

α^{∗}(P, Q)e^{−μ} ≤ α(P, Q) ≤ α^{∗}(P, Q).  (13)

and

β^{∗}(P, Q) ≤ β(P, Q) ≤ β^{∗}(P, Q)e^{μ}.  (14)

Thus if f, g, F, G are as before then

− log min(α^{∗}(f, g), α^{∗}(F, G)) ≤ log ϵ_{υ} ≤ − log min(α^{∗}(f, g), α^{∗}(F, G)) + μ,

and

− log max(β^{∗}(f, g), β^{∗}(F, G)) − μ ≤ log δ_{υ} ≤ − log max(β^{∗}(f, g), β^{∗}(F, G));

meaning that we can compute the contribution at complex places to arbitrary accuracy μ.

Now fix complex polynomials P, Q that do not vanish simultaneously. To ease notation, let

h(z) = max {|P (z)|, |Q(z)|} .

Thus

α(P, Q) = inf_{z∈D} h(z),  β(P, Q) = sup_{z∈D} h(z).  (15)

Given η > 0 we define

E(z, η) = max \{∑_{n=1}^{d_{1}} \frac{η^{n}}{n!} |P^{(n)}(z)|, ∑_{n=1}^{d_{2}} \frac{η^{n}}{n!} |Q^{(n)}(z)|\} ,

where d_{1}, d_{2} are the degrees of P, Q respectively.

We naturally identify ℝ^{2} and ℂ.

Lemma 13 Let S be the square S = [a, a + r] × [b, b + r]. Then

h(u) − E(u, η) ≤ h(z) ≤ h(u) + E(u, η),

for all z ∈ S, where either

• u is the centre of S and η = r/\sqrt{2}, or

• u is a corner of S and η = r\sqrt{2}.

Proof: This follows from Taylor’s Theorem applied to the polynomials P, Q. □

Now we give a method of computing α^{∗}(P, Q), β^{∗}(P, Q). Let H be the set

H = \{h (\frac{m + ni}{10}) : m, n ∈ ℤ, m^{2} + n^{2} ≤ 100\} .

We start with S = [−1, 1] × [−1, 1] and the initial values

α^{∗} = min H, β^{∗} = max H.

This gives (fairly crude) upper and lower bounds for α(P, Q) and β(P, Q); we repeatedly refine these until we obtain values α^{∗}(P, Q) and β^{∗}(P, Q) satisfying (13) and (14) respectively. To do this for α^{∗} we use the following recursive procedure, starting with S and α^{∗} as above. When the procedure returns (possibly after many recursive function calls), we will have a value of α^{∗} that we can take as α^{∗}(P, Q).

RefineAlphaBound(P, Q, μ, S, α^{∗})

INPUT: P, Q ∈ ℂ[z], μ > 0, square S = [a, a + r] × [b, b + r] ⊂ ℂ, α^{∗}

OUTPUT:  α^{∗} (possibly modified)
1.   BEGIN
2.   IF S ∩ D = ∅ THEN RETURN(α^{∗}); ENDIF;

3. IF a + r/2 + (b + r/2)i ∈ D THEN u = a + r/2 + (b + r/2)i AND η = r/\sqrt{2};

ELSE u is any corner of S in D AND η = r\sqrt{2}; ENDIF.
4.   IF h(u) − E(u, η) > α^{∗}e^{−μ} THEN RETURN(α^{∗}); ENDIF;

5. LET α^{∗} = min(α^{∗}, h(u));

6. LET S_{1} = [a, a + r/2] × [b, b + r/2], S_{2} = [a, a + r/2] × [b + r/2, b + r], S_{3} = [a + r/2, a + r] × [b, b + r/2], S_{4} = [a + r/2, a + r] × [b + r/2, b + r]; 7. LET α^{∗} = RefineAlphaBound(P, Q, μ, S_{1}, α^{∗});

8. LET α^{∗} = RefineAlphaBound(P, Q, μ, S_{2}, α^{∗});

9. LET α^{∗} = RefineAlphaBound(P, Q, μ, S_{3}, α^{∗});

10. LET α^{∗} = RefineAlphaBound(P, Q, μ, S_{4}, α^{∗});

11.   RETURN(α^{∗});
12.   END

The procedure for calculating β^{∗}(P, Q) is slightly different since by Lemma 12 the supremum of h(z) is attained on the boundary of D. Thus let ∂D be the boundary of D (that is the circle x^{2} + y^{2} = 1). To obtain β^{∗}(P, Q) apply the following procedure to the value of β^{∗} above with S = [−1, 1] × [−1, 1] again.

RefineBetaBound(P, Q, μ, S, β^{∗})

INPUT: P, Q ∈ ℂ[z], μ > 0, square S = [a, a + r] × [b, b + r] ⊂ ℂ, β^{∗}

OUTPUT:  β^{∗} (possibly modified)
1.   BEGIN
2.   IF S ∩ ∂D = ∅ THEN RETURN(β^{∗}); ENDIF;

3. IF a + r/2 + (b + r/2)i ∈ D THEN u = a + r/2 + (b + r/2)i AND η = r/\sqrt{2};

ELSE u is any corner of S in D AND η = r\sqrt{2}; ENDIF.
4.   IF h(u) − E(u, η) < β^{∗}e^{μ} THEN RETURN(β^{∗}); ENDIF;

5. LET β^{∗} = max(β^{∗}, h(u));

6. LET S_{1} = [a, a + r/2] × [b, b + r/2], S_{2} = [a, a + r/2] × [b + r/2, b + r], S_{3} = [a + r/2, a + r] × [b, b + r/2], S_{4} = [a + r/2, a + r] × [b + r/2, b + r];

7. LET β^{∗} = RefineBetaBound(P, Q, μ, S_{1}, β^{∗});

8. LET β^{∗} = RefineBetaBound(P, Q, μ, S_{2}, β^{∗});

9. LET β^{∗} = RefineBetaBound(P, Q, μ, S_{3}, β^{∗});

10. LET β^{∗} = RefineBetaBound(P, Q, μ, S_{4}, β^{∗});

11.   RETURN(β^{∗});
12.   END

Remark. For Step 2 in the procedure RefineAlphaBound we need a method of deciding if S ∩ D = ∅. Of course our initial square S is [−1, 1] × [−1, 1] for which we know that the intersection is not empty. All other squares S will be contained in one of the four quadrants, and then all we need to check is whether the corner closest to the origin is in D.

For Step 2 in the procedure RefineBetaBound, if S is a square contained in the four quadrants then S ∩ ∂D = ∅ if and only if all its corners are outside D, or all its corners are strictly inside D.

The reader might be surprised to find that we are using a two-dimensional method for estimating the infimum β, when we have shown that the infimum is attained on the boundary. It is true that the boundary x^{2} + y^{2} = 1 can be parametrized by trigonometric (or algebraic) functions of one parameter, and so it should be possible to find the infimum using repeated bisection of an interval rather than repeated quadrisection of the unit disc. But it is then much harder to obtain an error term E that is simultaneously rigorous and small. The reader will note that our error term E(z, η) (which follows from Taylor’s Theorem) is the maximum of finite sums; this is because all sufficiently high derivatives of the polynomials P, Q vanish. The same would not be true for trigonometric or rational functions.

Proposition 14 The above algorithms terminate giving values α^{∗}(P, Q) β^{∗}(P, Q) that satisfy the inequalities (13) and (14) respectively.

Proof: We prove the proposition for α^{∗}(P, Q); the proof for β^{∗}(P, Q) is similar. Recall that

α(P, Q) = inf_{z∈D} h(z).

We note that the initial value of α^{∗} is obtained by taking the minimum of values of h at some points in D, and throughout the algorithm α^{∗} is only changed in Step 5, where we replace α^{∗} with min(α^{∗}, h(u)) with u being some point in D. Clearly the resulting value of α^{∗}(P, Q) satisfies

α^{∗}(P, Q) ≥ inf_{z∈D} h(z) = α(P, Q).

Moreover, when we leave any square S without quadrisecting it, either it is outside D completely (and there is nothing to prove), or

h(u) − E(u, η) > α^{∗}e^{−μ}.

But for all z ∈ S ∩ D we know that h(z) ≥ h(u) − E(u, η). Moreover, the final value α^{∗}(P, Q) satisfies α^{∗}(P, Q) ≤ α^{∗}. Thus

h(z) > α^{∗}(P, Q)e^{−μ}

for all z belonging to S ∩ D. If the algorithm terminates then we will have covered D with squares S so that this inequality is satisfied for all points on the overlaps S ∩ D; thus this inequality is satisfied for all z ∈ D.

All that remains to prove now is that the algorithm terminates. Suppose otherwise; then there is a convergent sequence {u_{n}}_{n=1}^{∞} ⊂ D, and a sequence of real numbers {η_{n}} converging to zero, such that

h(u_{n}) − E(u_{n}, η_{n}) ≤ α_{n}^{∗}e^{−μ},

where

α_{n}^{∗} = min(h(u_{i}) : i = 1, …, n).

From the formula for E we see that lim E(u_{n}, η_{n}) = 0. Thus

lim α_{n}^{∗} ≤ lim h(u_{n}) ≤ lim α_{n}^{∗}e^{−μ}.

Since μ > 0 we deduce that lim α_{n}^{∗} = lim h(u_{n}) = 0. This is impossible since then P, Q will have a common zero. □

10 Silverman’s Archimedean Contributions

In [13, page 737] Silverman gives an estimate for the archimedean contributions that is proved using the complex parameterization of the curve. We give this here as it is occasionally better than our own archimedean estimates, and is indeed simpler to calculate for complex places.

Theorem 15 (Silverman) Let E/ℂ be an elliptic curve given by a Weierstrass equation (2), and let λ : E(ℂ)\ {O} → ℝ be the complex local height function. Then for all P ∈ E(ℂ),

− \frac{1}{6} log^{+}|Δ| − \frac{1}{6} log^{+}|j| − log^{+}|\frac{b_{2}}{12}| − log 2^{∗} − 2.14

≤ log max {1, x(P)} − λ(P)

≤ \frac{1}{6} log^{+}|Δ^{−1}| + \frac{1}{4} log^{+}|j| + log^{+}|\frac{b_{2}}{12}| + log 2^{∗} + 1.946,

where log^{+} x = log max {1, x} and

2^{∗} = \{ \begin{matrix}2 & if b_{2} ≠ 0, \\ 1 & if b_{2} = 0. \end{matrix}

11 Examples and Numerical Comparisons

In this section we give some examples based on our implementations of the height bound formula in Theorem 1. In the case K = ℚ we have implementations in PARI/GP (see [11]), MAGMA (see [8]) and C++, the latter being part of the first-named author’s package of elliptic curve programs including the 2-descent program mwrank. For general number fields, the algorithms were implemented in MAGMA by the second-named author, and by the thirdnamed author in Mathematica (see [9]), using the floating-point Groebner basis method which is implemented in that package for computation of the complex contributions.

Example 1. Consider the curve

E : y^{2} = x^{3} + (1 + 5i)x + (3 + i)

over the field K = ℚ(i). Using our Mathematica program we get the bound

−1.37727 ≤ Ψ_{∞} ≤ 0.114857

for the complex contribution. In comparison, Silverman’s theorem gives

−4.89012 ≤ Ψ_{∞} ≤ 3.96119.

We now complete the computation of the bound for h−ĥ using our Theorem 1. The discriminant of the curve is

1280 + 4448i = −i(1 + i)^{10}(40 + 139i)

where the last factor is prime. Since the discriminant is not divisible by any 12–th powers we see that the curve is globally minimal. The Tamagawa indices at the two bad primes are both 1. From Theorem 1 it follows that

−1.37727 ≤ h(P) − ĥ(P) ≤ 0.114857

for all P ∈ E(K). Silverman’s bounds for the same curve are

−4.89012 ≤ h(P) − ĥ(P) ≤ 5.75838.

We also programmed our repeated quadrisection method for computing the complex contributions in PARI/GP. Taking μ = 0.01 we find that

0.34456246612 . . . . . . ≤ log ϵ_{υ} ≤ 0.34556246612 …

Thus we know log(ϵ_{υ}) to three decimal places (the computation took 1.03 seconds). Thus the complex contribution

\frac{n_{υ}}{3[K : ℚ]} log ϵ_{υ} ≤ 0.1151.

Example 2. This example comes from the paper [5] of Halberstadt and Kraus. Let K = ℚ(θ) be the degree 5 number field generated by a root θ of the polynomial x^{5} +5x^{3} +5x−1. Let E be the curve defined over K with equation

y^{2} = x^{3} + (−30θ^{3} − 100θ + 30)x^{2} + (500θ^{4} − 600θ^{3} + 500θ^{2} − 1700θ + 300)x

+ (4000θ^{4} − 28000θ^{3} − 57000θ + 11000).

K has one real embedding and two (pairs of) complex embeddings. The associated values of ϵ_{υ} are (approximately) 2.21, 25.11 and 20.52 respectively, giving a total contribution of 0.8856 for the archimedean contribution to the upper bound. Similarly the values of δ_{υ} are 0.01808, 0.0000000358 and 0.000000167, giving a lower bound of −4.634.

There are three primes of bad reduction:

• one of norm 2, Kodaira type II, discriminant valuation 16 for the given model and 4 for the minimal model; this contributes \frac{2}{5} log(2) to the upper bound;

• one of norm 16, Kodaira type II, discriminant valuation 16 for the given model and 4 for the minimal model; this contributes \frac{8}{5} log(2) to the upper bound;

• one of norm 5, Kodaira type III*, discriminant valuation 45 for the given model and 9 for the minimal model; this contributes \frac{3}{2} log(5) to the upper bound;

giving a total contribution from the non-archimedean valuations of 3.800.

Putting these together we find that the height bounds for this curve are

−4.634 ≤ h(P) − ĥ(P) ≤ 4.686.

This computation took about 6 minutes, most of the time being spent computing the complex contributions to the bounds.

For the same curve, the Silverman bounds are

−11.01053 ≤ h(P) − ĥ(P) ≤ 11.42791.

Example 3.

As a comprehensive test of our bounds, we considered the 33355 isomorphism classes of elliptic curves defined over ℚ with conductors N in the range 20000 ≤ N ≤ 25000 (see [3]). For each curve we computed the height bounds given by our Theorem 1, and the height bounds given by Silverman’s paper [13]. Our average lower and upper bounds for the difference h − ĥ are −3.483 and 5.218, whereas the respective averages for Silverman bounds are −9.011 and 11.251. Indeed we found that both our upper and lower bounds are better than Silverman’s bounds for all curves in the given range except the following two:

• For the curve 20449G3 our bounds are −12.594 ≤ h − ĥ ≤ 17.251 whereas Silverman’s bounds are −14.214 ≤ h − ĥ ≤ 17.205.

• For the curve 23622G1 our bounds are −20.056 ≤ h − ĥ ≤ 23.525 whereas Silverman’s bounds are −19.811 ≤ h − ĥ ≤ 28.082.

Since our non-archimedean contributions are best possible (in the sense explained in the introduction), it is sensible to compare our archimedean contributions with those given by Silverman’s Theorem 15. For the curves in the above range our average archimedean contributions to the lower and upper bounds are respectively −3.483 and 1.029, whereas the corresponding average contributions to Silverman’s bounds are −9.011 and 5.048. Our archimedean contributions are better than Silverman’s for all except 28 curves in the above range.

Example 4.

It is reasonable to ask how our bounds compare with actual values of the difference h−ĥ on rational points. We recall that we have decomposed the difference h − ĥ as a weighted sum of continuous bounded functions Ψ_{υ}, with υ running over the set of places of M_{K}. For non-archimedean υ the value of Ψ_{υ} depends only on the image of the point in the component group E(K_{υ})/E_{0}(K_{υ}). Thus one does not expect our bounds to be sharp unless the map

E(K) → ∏_{υ∈M_{K}^{0}} E(K_{υ})/E_{0}(K_{υ})

is surjective. One the other hand, if the map is surjective, then the total nonarchimedean contribution is attained at some rational point, and the only discrepancy that can arise comes from the archimedean contributions which in general are rather small.

Consider for example the elliptic curve E/ℚ given by

E : y^{2} = x^{3} − 459x^{2} − 3478x + 169057.

Here all the component groups are trivial, and so we are trivially in the case where the above map is surjective. Our bounds give

−6.5319247238 … ≤ h(P) − ĥ(P) ≤ 0.4620981203 …

The elliptic curve E has rank 4; its Mordell-Weil group has basis

P_{1} = [16, −1], P_{2} = [−4, −419], P_{3} = [−22, −113], P_{4} = [566, −5699].

We computed that values of h(P)−ĥ(P) on points P = ∑ m_{i}P_{i} with |m_{i}| ≤ 3; the maximum and minimum values for h(P) − ĥ(P) for these points are as follows:

P = 2P_{1}, h(P) − ĥ(P) = 0.4620980788 …,
P = P_{1} − 3P_{2} + P_{3} + 3P_{4}, h(P) − ĥ(P) = −4.9001533427 ….

We leave it to the reader to draw his own conclusions.

References

[1] L. V. Ahlfors, Complex analysis, third edition, McGraw–Hill, 1979.

[2] J. E. Cremona, Algorithms for modular elliptic curves, second edition, Cambridge University Press, 1996.

[3] J. E. Cremona, Elliptic Curve Data, http://www.maths.nott.ac.uk/

   personal/jec/ftp/data/INDEX.html.

[4] V. A. Demjanenko, An estimate for the remainder term in Tate’s formula, Mat. Zametki 3 (1968), 271–278. (Russian)

[5] E. Halberstadt and A. Kraus, Une conjecture de V.A. Lebesgue, J. London Math. Soc. (2) 69 (2004), no. 2, 291–302.

[6] A. Kondratyev, Numerical computation of Groebner bases, Ph.D. thesis, University of Linz, Austria, 2003.

[7] S. Lang, Conjectured Diophantine estimates on elliptic curves, Progr. Math. 35 (1983), 155–171.

[8] MAGMA is described in W.Bosma, J.Cannon and C. Playoust: The Magma algebra system I: The user language, J. Symbolic Comput. 24, 235–265 (1997).

   (Also see the Magma home page at http://www.maths.usyd.edu.au:8000/u/
   magma/ .)

[9] Mathematica, Version 5.0, Wolfram Research, Inc., Champaign, IL (2003).

[10] A. Néron, Quasi-fonctions et hauteurs sur les variétés abéliennes, Ann. of Math. (2), 82 (1965), 249–331.

[11] PARI/GP, version 2.2.8, Bordeaux, 2004, http://pari.math.u-bordeaux.

   fr/.

[12] S. Siksek, Infinite descent on elliptic curves, Rocky Mountain Journal of Mathematics 25, number 4 (Fall 1990), 1501–1538.

[13] J. H. Silverman, The difference between the Weil height and the canonical height on elliptic curves, Math. Comp. 55 (1990), 723-743.

[14] J. H. Silverman, The arithmetic of elliptic curves, GTM 106, Springer-Verlag, 1986.

[15] J. H. Silverman, Advanced topics in the arithmetic of elliptic curves, GTM 151, Springer-Verlag, 1994.

[16] J. H. Silverman, Computing heights on elliptic curves, Math. Comp. 51 (1988), 339-358.

[17] H. G. Zimmer, On the difference between the Weil height and the Néron–Tate height, Math. Z. 174 (1976), 35–51.