THE UNIFORM PRIMALITY CONJECTURE FOR THE TWISTED FERMAT CUBIC

GRAHAM EVEREST, OUAMPORN PHUKSUWAN AND SHAUN STEVENS

To Jupiter, bringer of joy.

Abstract. On the twisted Fermat cubic, an elliptic divisibility sequence arises as the sequence of denominators of the multiples of a single rational point. We prove that the number of prime terms in the sequence is uniformly bounded. When the rational point is the image of another rational point under a certain 3-isogeny, all terms beyond the first fail to be primes.

1. Introduction

There abides a deep fascination with the subject of prime terms in naturally occurring integer sequences. The fanfare which accompanies the discovery of each new Mersenne prime [2] bears testimony, as does the search for factorizations of the Fermat and Fibonacci numbers [3, 21]. Elliptic curves [4, 32, 34] give rise naturally to rapidly growing sequences of integers, called elliptic divisibility sequences, generated from some nontorsion point via the geometric addition law. The first systematic study of elliptic divisibility sequences was given majestically by Morgan Ward in [40]. Recent times have witnessed a great deal of activity (the following represents a sample) because of their intrinsic interest [14, 16, 18, 19, 35, 36, 37, 38, 39] as well as in applications to Logic [6, 10, 27, 28, 31] and Cryptography [22, 30]. The Chudnovsky brothers [5] first proposed studying primality in elliptic divisibility sequences arising from elliptic curves in Weierstrass form. This was continued in [7, 11, 15] with the following outcome: a heuristic argument, together with lots of computational evidence and proofs in some special cases, suggests that any elliptic divisibility sequence contains only finitely many prime terms. This has become known as the primality conjecture for elliptic curves in Weierstrass form. In [15, Theorem 4.1] the same conjecture was proved for curves in homogeneous form. It is with such curves that our business lies in this paper.

1991 Mathematics Subject Classification. 11G05, 11A41.

Key words and phrases. Elliptic curve, elliptic divisibility sequence, Fermat cubic, isogeny, prime, uniform primality conjecture.

The research of the second author was supported by a grant from the Thai government.

Let C denote an elliptic curve of the form

C : U^{3} + V^{3} = m,  (1)

where m is a nonzero integer. It is sometimes said that C is a twist of the Fermat cubic. The set of rational (or real) points form a group under the chord and tangent method: the (projective) point at infinity with homogeneous coordinates (1 : −1 : 0) is the identity, and inversion is given by reflection in the line U = V. Given a nontorsion point R ∈ C(ℚ), write, in lowest terms,

nR = (\frac{U_{n}}{W_{n}} , \frac{V_{n}}{W_{n}} ) .

The sequence (W_{n}) is a (strong) divisibility sequence, see Proposition 3.3. Our starting point is the result stated earlier, that only finitely many terms W_{n} are prime [15, Theorem 4.1]. A related result [13, Theorem 1.2] states that W_{n} has a primitive divisor for all n > 1: results from [13] will be employed in the proofs of our theorems. To focus now upon the question we study: a stronger form of the primality conjecture has been proposed, assuming that the Weierstrass equation is in minimal form, predicting that the number of prime terms in an elliptic divisibility sequence is uniformly bounded (independently of both the curve and the point). Unsurprisingly, this conjecture is known as the uniform primality conjecture for curves in Weierstrass form. A conditional proof is known, under Lang’s Conjecture, assuming the generating point is the image of a rational point under a nontrivial isogeny [12, Theorem 1.4]. This raises the natural question as to whether a uniform primality result holds for curves in homogeneous form and it is this question we address. The first of our two results is an unconditional result to that effect, and will be stated now. The proof will appear to be quite short although, in fact, it relies upon two substantial results from [13] and [17].

Theorem 1.1. Assuming m ∈ ℤ is cube-free, the number of prime (power) terms W_{n} is uniformly bounded. Moreover, assuming the ABC conjecture holds in ℤ, there is a uniform upper bound on the index n such that W_{n} is a prime power.

The assumption about m being cube-free is necessary given the homogeneous nature of the curve C, since one could scale any given elliptic divisibility sequence to obtain as many prime terms as desired. This will be explained in detail in subsection 3.3. It is also probable that a uniform bound on the index n would follow from the Hall-Lang conjecture, as in recent work of Mahé [24]. Our second theorem relies upon the existence of a rational isogeny in line with work for curves in Weierstrass form [11, 15]. There is a 3-isogeny, detailed in [8], τ : C′ → C from the elliptic curve

C′ : U′V′(U′ + V′) = m.  (2)

Theorem 1.2. Suppose m ∈ ℤ is cube-free and R ∈ C(ℚ) is the image of a point in C′(ℚ) under τ. Then W_{n} is not a prime power, for all n > 1. Further, the number of terms W_{n} with at most two distinct prime divisors is uniformly bounded.

The conclusion is clearly best possible and what is remarkable is the small size of the bound 1; this is certainly much stronger than any corresponding result for elliptic curves in Weierstrass form. The proofs of the two theorems rely upon the same principle, which will be articulated in section 3 below. This is preceded by a section discussing possible improvements to our results and is followed by proofs of the theorems in order. We thank Tony Flatters and Valéry Mahé for their excellent comments and suggestions on a preliminary version of this paper. In particular, the latter pointed out that a (conditional) bound on the index could be obtained in Theorem 1.1.

2. Better-best?

2.1. With isogeny. Taking our two theorems in reverse over, Theorem 1.2 cannot be improved. But to how large a class of examples does it apply? If R is 3 times another rational point then it will be such an image [8]. A short analysis is included to shed light in greater generality. In truth, throughout the paper, we will not work explicitly with the isogeny mentioned in the statement of Theorem 1.2. Instead, our work relies upon a bi-rational map between C and the Mordell curve

E : Y^{2} = X^{3} − 432m^{2},  (3)

where P = (X, Y) corresponds to R = (U, V) under the bi-rational transformation given by

\begin{matrix}X = \frac{2^{2}3m}{U + V} , & Y = \frac{2^{2}3^{2}m(U − V)}{U + V}, \\ U = \frac{2^{2}3^{2}m + Y}{6X} , & V = \frac{2^{2}3^{2}m − Y}{6X} . \end{matrix}  (4)

There is a 3-isogeny σ : E′ → E onto the curve E from the elliptic curve

E′ : y^{2} = x^{3} + 16m^{2},

given by

σ(x, y) = (X, Y) = (x + \frac{64m^{2}}{x^{2}} , \frac{y(y + 12m)(y − 12m)}{(y + 4m)(y − 4m)}) .  (5)

It is with this isogeny that we work. The isogeny condition stated in Theorem 1.2 is equivalent to the point P ∈ E(ℚ) being equal to σ(P′) for some point P′ ∈ E′(ℚ). Table 1 shows the 22 values m < 100 when this occurs for a point P which is a generator for the group E(ℚ). (Thus all points in E(ℚ) are in the image of the isogeny.) In total, there are 42 rank one curves with m < 100. We conclude that, at least for small values of m, the hypothesis of Theorem 1.2 is not infrequently met.

Table 1. Rank 1 curves satisfying Theorem 1.2 with m < 100

m  P  P′
6  [28, 80]  [-8, 8]
12  [52, 280]  [-12, 24]
15  [49, 143]  [-15, 15]
20  [84, 648]  [-16, 48]
22  [553/9, 4085/27]  [33, 209]
33  [97, 665]  [-24, 60]
34  [273, 4455]  [-16, 120]
42  [172, 2080]  [-24, 120]
50  [2716/9, 138736/27]  [24, 232]
51  [5473/36, 333935/216]  [144, 1740]
58  [3148/9, 173600/27]  [-24, 200]
68  [55156/225, 12043304/3375 ]  [240, 3728]
69  [553, 12925]  [-23, 253]
70  [156, 1296]  [-40, 120]
75  [601, 14651]  [-24, 276]
78  [217, 2755]  [-39, 195]
84  [148, 440]  [-48, 48]
85  [18361/9, 2487509/27]  [-15, 335]
87 [1029841/1225, 1042214111/42875] [840, 24348]
90  [364, 6688]  [-36, 288]
92  [2548/9, 117800/27]  [48, 496]
94 [62511752209/2480625,
15629405421521177/3906984375] [25200, 4000376]

2.2. Without isogeny. Turning now to Theorem 1.1, we will draw upon a result of Ingram [17] bounding the number of integral multiples of a given integral point. In its most general form, this involves a non-explicit constant. In his paper, he gives a very strong (actually best possible) explicit constant in the case of congruent number curves. It seems a good bet that his analysis could be re-worked in our context to obtain an explicit (perhaps even best possible) form of Theorem 1.1. This analysis was done in certain cases by the second author in her thesis [26]: a special case of [26, Theorem 1.0.4] is recorded here.

Theorem 2.1. Assume m ≡ ±1, ±3, ±4 mod 9 is cube-free. Assuming P ∈ E(ℚ) has gcd(x(P), m) = 1 and 2P and 3P are not integral then at most one value of n > 1 yields a prime power term W_{n}.

Of course the most desirable goal is to be to be able to compute all of the prime power terms in a given sequence, as permitted by Theorem 1.2. It is not clear whether Theorem 1.1 could be improved to allow that as an outcome. However, as part of the proof of Theorem 1.2, we do prove the following unconditional result:

Lemma 2.2. Suppose m ∈ ℤ is cube-free. Then W_{n} is not a prime power, for 2 < n ≤ 22.

2.3. Daylight. There will always be daylight between out theorems as our final remark demonstrates. It seems likely that without the isogeny hypothesis, there are infinitely many values of m and generating points R yielding a prime term W_{2}. For, suppose R = [u, v] ∈ C(ℚ) is an integral point of infinite order. The point 2R can be expressed in the form

2R = (\frac{−2vu^{3} − v^{4}}{u^{3} − v^{3}} , \frac{u^{4} + 2v^{3}u}{u^{3} − v^{3}}) .

Suppose u − v = 1. Then

u^{3} − v^{3} = (u − v)(u^{2} + uv + v^{2}) = 3u^{2} − 3u + 1.

Applying the Bateman-Horn conjecture [1] to the polynomial

f(u) := 3u^{2} − 3u + 1

implies that f(u) is prime for infinitely many positive integers u. By a result of Erdõs [9], the corresponding value of m = u^{3} + (u − 1)^{3} will be cube-free for infinitely many of these values. To show that the prime so constructed does not cancel with the numerator, compute the resultants of the two polynomials u^{2} +uv +v^{2} and 2u^{3} +v^{3} in each variable: they are 9u^{6} and 9v^{6} so the only non-trivial common division is by a divisor of 9. But 3u^{2} − 3u + 1 is coprime to 3 so there can be no cancellation. This style of argument will be used repeatedly in the proof of Theorem 1.2.

3. Proving the Primality Conjecture

This section is elementary although quite technical because of the case-by-case nature of the proofs. It is the statements of the results which provide important input for sections 4 and 5, rather than their proofs. Readers whose taste is not excited by the details could take note of Lemma 3.1, Proposition 3.3 and subsection 3.3 then skip directly to sections 4 and 5.

3.1. Constraints to cancellation. From the bi-rational transformation (4), we have

\frac{U_{n}}{W_{n}} = \frac{2^{2}3^{2}mB_{n}^{3} + C_{n}}{6A_{n}B_{n}} ,  (6)

and

\frac{V_{n}}{W_{n}} = \frac{2^{2}3^{2}mB_{n}^{3} − C_{n}}{6A_{n}B_{n}} ,  (7)

where

nR = (\frac{U_{n}}{W_{n}} , \frac{V_{n}}{W_{n}} ) and nP = (\frac{A_{n}}{B_{n}^{2}} , \frac{C_{n}}{B_{n}^{3}} )

are written in lowest terms.

Lemma 3.1. Any cancellation in the fractions (6) and (7) comes from the term 6A_{n} and divides 72m.

Since A_{n} and B_{n} are coprime, the following important principle arises as a consequence of Lemma 3.1:

We can be certain that W_{n} possesses at least two coprime factors if two conditions are met. The first is that B_{n} > 1 and the second is that the term 6A_{n} is not completely cancelled.

Proof of Lemma 3.1. Consider the fraction on the right-hand side of (6). Let d = p^{r} be a common factor of (2^{2}3^{2}mB_{n}^{3} + C_{n}) and 6A_{n}B_{n} with p a prime number and r ∈ ℕ the highest order of p dividing both terms. If d′ := gcd(d, B_{n}) ≠ 1, then d′ | d | (2^{2}3^{2}mB_{n}^{3} + C_{n}) implies d′ | C_{n} , which contradicts the fact that B_{n} and C_{n} are coprime. Thus gcd(d, B_{n}) = 1, so that d comes from the term 6A_{n}. Notice, moreover, that any cancellation in the right-hand side of (6) and (7) is the same in each term. This is because both terms have the same denominators as their cubes sum to an integer. Hence d has to divide both (2^{2}3^{2}mB_{n}^{3}+C_{n}) and (2^{2}3^{2}mB_{n}^{3}−C_{n}), so that d | 72m. Thus any cancellation of the fractions (6) and (7) divides 72m. □

We will need to be even be more precise about the cancellation that occurs. Write d_{n} for the cancellation in the fraction (7).

Corollary 3.2. We have

ord_{p}(d_{n}) = \begin{cases}ord_{p}(m) & if p | A_{n}, p > 3; \\ ord_{p}(A_{n}) + 1 & if p | A_{n}, p ≤ 3; \\ 0 & if p ∤ A_{n}. \end{cases}

Note in particular that if p ≤ 3 and p | A_{n} then p is completely cancelled. Thus for primes p ≤ 3, we have p | W_{n} if and only if p ∤ A_{n}. For primes greater than 3, the cancellation is exactly as large as allowed by Lemma 3.1; therefore, whenever p > 3 divides A_{n}, we have

ord_{p}(W_{n}) = ord_{p}(A_{n}) − ord_{p}(m).  (8)

Proof. Suppose first that p ∤ A_{n}. By Lemma 3.1, we have ord_{p}(d_{n}) = 0 except possibly if p ≤ 3 so suppose we are in this situation. The defining equation (3) yields

C_{n}^{2} = A_{n}^{3} − 432m^{2}B_{n}^{6},  (9)

whence p ∤ C_{n} so p cannot cancel in (7).

Now suppose p | A_{n} and p ≥ 3. From (9) we find

ord_{p}(A_{n}) ≥ ord_{p}(C_{n}) = ord_{p}(m),

since p | A_{n}, and it follows that ord_{p}(d_{n}) = ord_{p}(m). Finally, suppose p | A_{n} and p ≤ 3, and put δ = ord_{p}(gcd(p, m)). The arguments are fiddly but elementary so we only sketch them, beginning with the slightly simpler case p = 3. If ord_{3}(A_{n}) > 1 + δ then, comparing 3-adic valuations, we see that equation (9) is impossible to solve. Hence 1 ≤ ord_{3}(A_{n}) ≤ 2 and we also find that ord_{3}(C_{n}) ≥ ord_{3}(A_{n}) + 1. Thus the numerator of (7) has 3-adic order at least ord_{3}(A_{n}) + 1 whereas the 3-adic order of the denominator is exactly ord_{3}(A_{n}) + 1, giving ord_{3}(d_{n}) = ord_{3}(A_{n}) + 1.

Now assume that p = 2. If ord_{2}(A_{n}) > 2 + δ then, dividing (9) through by 2^{4}3^{2}m^{2} yields a congruence x^{2} ≡ −1 (mod 4), which is impossible. Moreover, ord_{2}(A_{n}) = 1 is impossible by comparing 2-adic valuations in (9). If ord_{2}(A_{n}) = 2 + δ then ord_{2}(C_{n}) = 2 + ord_{2}(m) so the numerator of (7) is 2^{2+ord_{2}(m)} times the sum of two odd numbers. Thus the 2-adic order of the numerator is at least 3 + ord_{2}(m) while that of the denominator is exactly 3 + δ so ord_{2}(d_{n}) = ord_{2}(A_{n}) + 1. This leaves the case ord_{2}(A_{n}) = 2 with 2 | m. Here ord_{2}(C_{n}) > 2 so the 2adic order of the numerator of (7) is at least 3, while that of the denominator is exactly 3, again giving ord_{2}(d_{n}) = ord_{2}(A_{n}) + 1. □

3.2. W is a divisibility sequence. The aim of this subsection is a proof of the following:

Proposition 3.3. The sequence (W_{n}) is a strong divisibility sequence: in other words, for all r, n ∈ ℕ,

gcd(W_{r}, W_{n}) = W_{gcd(r,n)}.

In particular, W_{n} | W_{nk}, for all n, k ∈ ℕ.

The divisibility property will be used repeatedly in this paper but we cannot find it proved explicitly in the literature. The strong divisibility property will be used only in subsection 3.3. However, it is a natural property and is proved with little more effort. We admit that the proof we give lacks elegance. This is due to the evil influence of the primes 2 and 3 and, to a lesser extent, those dividing m. However, the proof is completely self-contained and uses only elementary methods. A more sophisticated proof of Proposition 3.3 uses formal groups [32, Chapter IV]. Writing w = U/V and z = 1/V in (1) yields the equation

w^{3} = mz^{3} − 1.

Now the binomial theorem yields a power series

w = ∑_{n=0}^{∞} a_{n}z^{3n} with a_{n} ∈ ℚ,

which converges p-adically for all primes p with p | z (only the case p = 3 is at all tricky). Applying the geometric group law on the points (z_{1}, w_{1}) and (z_{2}, w_{2}) now yields a power series F (z_{1}, z_{2}) – the formal group of our elliptic curve. The proof of Proposition 3.3 follows from the standard properties of formal groups [32, Chapters IV,VII]: in particular, the filtration into subgroups C_{r}, r ∈ ℕ, defined by |U|_{p} ≥ p^{r}. However arguing as above requires quite a lot of explanation and checking and it would not shorten the paper. For example, the statement of Proposition 3.3 per se does not appear in [32]. Instead, the filtration referred to yields directly the relation (10) below.

Proof of Proposition 3.3. The divisibility property follows from the following relation: for any prime p and k ∈ ℕ, if p | W_{n} then

ord_{p}(W_{nk}) = ord_{p}(W_{n}) + ord_{p}(k).  (10)

Much of the spade work here is supplied by the following two relations. Firstly, from [13, Lemma 3.2], for p > 3, if ord_{p}(A_{n}) > 0 and 3 ∤ k then

ord_{p}(A_{nk}) = ord_{p}(A_{n}) + ord_{p}(k).  (11)

Secondly, for all primes p, if ord_{p}(B_{n}) > 0 and k ∈ ℤ then

ord_{p}(B_{nk}) = ord_{p}(B_{n}) + ord_{p}(k).  (12)

The second relation arises from a local analysis using the formal group for the Weierstrass equation and follows from [32, Chapter VII]. A much more general proof, valid over a Dedekind domain, is given in [19, Proposition 1]. Note that (12) implies that B = (B_{n}) is a strong divisibility sequence. Further work is needed to take us from (10) to the same conclusion for the sequence W = (W_{n}): this will be supplied at the end. Assume p denotes a prime with p | W_{n}. We will show (10) for all k ∈ ℕ. There are three cases in total:

(a) p | B_{n},

(b) p ∤ B_{n}, p > 3,

(c) p ∤ B_{n}, p ≤ 3.

Case (a) No cancellation occurs in (7) so ord_{p}(W_{n}) = ord_{p}(B_{n}) if p ∤ 6 or 1 + ord_{p}(B_{n}) if p | 6. Then (10) follows from (12), the corresponding result for the sequence B = (B_{n}).

Case (b) Since p | W_{n}, the two conditions given imply p | A_{n}. When 3 ∤ k, we have p | A_{nk} by (11) so we can apply (8) with nk replacing n. Then

ord_{p}(W_{nk}) = ord_{p}(A_{nk}) − ord_{p}(m)  by (8),
= ord_{p}(A_{n}) + ord_{p}(k) − ord_{p}(m)  by (11),
= ord_{p}(W_{n}) + ord_{p}(k)  by (8).

When 3 | k, we use the triplication law [13, (8)], repeated here for convenience:

x(3Q) = \frac{x^{9}(Q) + 2^{9}3^{4}x^{6}(Q)m^{2} + 2^{12}3^{7}x^{3}(Q)m^{4} − 2^{18}3^{9}m^{6}}{9x^{2}(Q)(x^{3}(Q) − 2^{6}3^{3}m^{2})^{2}} .  (13)

It follows from (13) and (8) that

ord_{p}(B_{3n}) = ord_{p}(A_{n}) − ord_{p}(m) = ord_{p}(W_{n}).  (14)

Since 3n | nk we deduce from (12) that p | B_{nk}. Therefore

ord_{p}(W_{nk}) = ord_{p}(B_{nk})  since p > 3,
= ord_{p}(B_{3n}) + ord_{p}(k/3)  since p | B_{3n},
= ord_{p}(B_{3n}) + ord_{p}(k)  since p > 3,
= ord_{p}(W_{n}) + ord_{p}(k)  by (14).

Case (c) Since p | W_{n} and p ≤ 3, we have p ∤ A_{n} and, as there is no cancellation, ord_{p}(W_{n}) = 1. Also, since p ∤ A_{n} it follows that p ∤ A_{nk} for all k ∈ ℕ: this is because the point nP has good reduction at p so nkP has good reduction mod p as the set of points with good reduction form a group and it follows that nkP cannot reduce mod p to a point with zero x-coordinate. Thus there is no cancellation in (7) when n is replaced by nk. Moreover, as p ∤ B_{n} also, the reduction of nP is a non-identity point and, since E has additive reduction modulo p, the point nkP reduces to the identity if and only if p | k. (Note that we are reducing the curve E, not its minimal form.) There are now two possibilities: If p ∤ k then p ∤ B_{nk}, in which case ord_{p}(W_{nk}) = 1 = ord_{p}(W_{n}) + ord_{p}(k). Otherwise p | k and p | B_{nk}; it is easily checked by an explicit calculation with the doubling and tripling formulae (see (13) for the latter) that ord_{p}(B_{np}) = 1 so we get

ord_{p}(W_{nk}) = ord_{p}(B_{nk}) + 1
= ord_{p}(B_{np}) + ord_{p}(k/p) + 1  by (12),
= 1 + ord_{p}(k)
= ord_{p}(W_{n}) + ord_{p}(k).

Now we have proved (10), the strong divisibility property comes from the following claim: Claim If a prime p divides gcd(W_{r}, W_{n}) then p | W_{gcd(r,n)}.

To see that this suffices, let d = gcd(r, n) and suppose r = dk, n = dl. For any prime p, one of ord_{p}(k) and ord_{p}(l) is 0 because k and l are coprime. From (10), the exact power of p dividing gcd(W_{dk}, W_{dl}) is ord_{p}(W_{d}) as desired.

It remains to prove the claim. First let p be a prime not dividing 6m. Note that p | W_{n} if and only if p | A_{n}B_{n} in this case (since no cancellation can occur), which is equivalent to nP reducing mod p to an element of the subgroup G of E(\overline{𝔽}_{p}) generated by a 3-torsion point T with x(T) = 0. If rP and nP both reduce to an element of G then so does any integer linear combination; in particular, so does gcd(r, n)P and we deduce that p | W_{gcd(r,n)}. Now suppose p > 3 is a prime dividing m such that p | gcd(W_{r}, W_{n}). There are three possibilities, and in each case we will show that p | W_{gcd(r,n)}:

(i) p | B_{r} and p | B_{n}, in which case p | B_{gcd(r,n)}, since B is a strong divisibility sequence. Thus p | W_{gcd(r,n)}, since there is no cancellation.

(ii) p | B_{r} and p | A_{n}, in which case nP is a point of bad reduction, and P is also. Thus p | A_{1} and, from the analysis in case (b) above, we see that 3 | r, 3 ∤ n. Then, from (14), we have p | B_{3n} so, from strong divisibility, p | B_{gcd(r,3n)} = B_{3 gcd(r,n)}. Moreover, since 3 ∤ gcd(r, n), we have p | A_{gcd(r,n)} so, from (14) again,

ord_{p}(W_{gcd(r,n)}) = ord_{p}(B_{3 gcd(r,n)}) > 0.

(iii) p | A_{r} and p | A_{n}, in which case P is again a point of bad reduction, 3 ∤ r, 3 ∤ n, so p | A_{gcd(r,n)}. From (14), we have p | gcd(B_{3r}, B_{3n}) = B_{3 gcd(r,n)} so that ord_{p}(W_{gcd(r,n)}) = ord_{p}(B_{3 gcd(r,n)}) > 0.

Finally, suppose p ≤ 3. Since p | W_{n} we have p ∤ A_{n} so nP is a point of good reduction modulo p. The same is true of rP and so also of gcd(r, n)P. Thus p ∤ A_{gcd(r,n)} and we deduce from Corollary 3.2 that p | W_{gcd(r,n)}. This completes the proof of the claim, and of Proposition 3.3. □

3.3. Cube-free m. We conclude with a remark justifying the assumption in both our theorems that m is cube-free. The key remark needed follows from Proposition 3.3: if gcd(m, n) = 1 then gcd(W_{m}, W_{n}) = 1. From [13, Theorem 1.2], the terms W_{n} with n > 1 all see a primitive prime divisor: in other words, a prime p | W_{n} which has not appeared in an earlier term. Let S denote a finite set of primes. For each l ∈ S, write W_{l} = w_{l}p_{l}^{e_{l}} with w_{l}, e_{l} ∈ ℕ and p_{l} ∤ w_{l} equal to a primitive prime divisor. Now write

M = ∏_{l∈S} w_{l}

and rescale equation (1) by multiplication with M^{3}. If W′_{l} = W_{l}/ gcd(W_{l}, M) denotes the resulting denominator then W′_{l} is a prime power by the starting remark. Therefore, by expanding S arbitrarily, we see that, at the cost only of multiplying m by a cube, we may produce elliptic divisibility sequences with arbitrarily large numbers of prime power terms.

4. Proof of Theorem 1.1

Proof of Theorem 1.1. We will prove firstly that, for n > 12, the term A_{n} in the denominator is not completely cancelled. From [13, Theorem 2.3], all terms A_{n} with n > 12 possess a primitive prime divisor p_{n}. Then p_{n} ∤ A_{1}, because p_{n} is a primitive prime divisor, so it follows that P is a point of good reduction for p_{n}. Thus all multiples of P, in particular nP, are points of good reduction. However, for primes dividing 6m, the point on the reduced curve with x-coordinate zero is a point of bad reduction so it follows that p_{n} ∤ 6m. In particular, p_{n} is not cancelled because any cancellation divides 72m. Secondly, from [17, Theorem 1], with the notation used there, there is a uniform constant C such that n > CM(P)^{16} forces B_{n} > 1, except for at most one value of n. The quantity M(P) is related to the Tamagawa number. Since the Mordell curve E has integral j-invariant, along the same lines as in [17], E always has M(P) ≤ 6. It follows that the number of prime power terms W_{n} is bounded by C6^{16} + 1, a uniform constant. Finally, assume the ABC conjecture holds for ℤ. As above we always get a prime factor from A_{n}, for n > 12, so we need only show that B_{n} > 1 for all n greater than some uniform bound. For this we will use the theory of heights, which will also be essential for the explicit bound in Theorem 1.2. Recall that the (naïve) Weil height of the point P is

h(P) = h(x(P)) = log max {|A_{1}|, B_{1}^{2}} .

On the other hand the canonical height ĥ(P) is given by

ĥ(P) = lim_{n→∞} \frac{h (2^{n}P)}{4^{n}}.

Silverman gives explicit upper and lower bounds for the difference between the Weil height and the canonical height for curves in short Weierstrass form. Note that our heights are twice those in [33] so the inequalities are multiplied by 2.

Theorem 4.1 ([33, Remark 1.2]). Given an elliptic curve in short Weierstrass form,

E/ℚ : y^{2} = x^{3} + ax + b,

and Q ∈ E(ℚ), we have

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

where Δ = −16(4a^{3} + 27b^{2}) and j = −48a^{3}/Δ.

We return to the proof of the final assertion in Theorem 1.1. From (3), we have

C_{n}^{2} = A_{n}^{3} − 432m^{2}B_{n}^{6}.

Suppose first that |A_{n}| > B_{n}^{2}. Since gcd(A_{n}, C_{n}) | 432m^{2}, for any ε > 0, the ABC conjecture gives

|A_{n}^{3}| ≪ |mA_{n}B_{n}C_{n}|^{1+ε}

and, since |C_{n}| < |A_{n}|^{3/2}, we get

|A_{n}|^{1/2−ε} ≪ mB_{n}.

Thus, taking ε = 1/4 and writing |A_{n}| = h(nP), we have

log B_{n} > \frac{1}{4}h(nP) − K_{1} log m,  (16)

for some constant K_{1} > 0. On the other hand, if |A_{n}| < B_{n}^{2} then (16) is trivially satisfied, since h(nP) = B_{n}^{2}. Finally, from Theorem 4.1 we have

h(nP) > ĥ(nP) − K_{2} log m = n^{2}ĥ(P) − K_{2} log m,

for some constant K_{2} > 0. Moreover, ĥ(P) > K_{3} log m, for some constant K_{3} > 0, by [20, Proposition 1]. Putting these together with (16), we get

log B_{n} > (K_{4}n^{2} − K_{5}) log m,

for constants K_{4}, K_{5} > 0. In particular, this bounds, independently of m and P, the index n for which we may have B_{n} = 1. □

5. Proof of Theorem 1.2

The idea of the proof of Theorem 1.2 is to use heights on the Weierstrass elliptic curve (3) to show that, for n > 22, we are guaranteed to get a prime divisor of W_{n} coming from the term B_{n}; that is, we use the isogeny to make explicit the constants in the argument above using the ABC conjecture. As we have seen, we also get a prime divisor coming from A_{n} in this case, so that W_{n} is not a prime power. The remaining values 2 ≤ n ≤ 22 are treated case-by-case, using the explicit form of the point nR as a rational function in the coordinates (u, v) of R ∈ C(ℚ).

Lemma 5.1. Let E be defined as in (3) and suppose P ∈ E(ℚ) is the image of a point in E′(ℚ) under the isogeny σ as in (5). Then, with B_{n} as in (7),

B_{n} > 1

for all n > 22.

Proof. Let P ∈ E(ℚ) such that σ(P′) = P, for some P′ ∈ E′(ℚ). Write

x_{n} := x(nP′) = \frac{a_{n}}{b_{n}^{2}} ,

with gcd(a_{n}, b_{n}) = 1. From (5),

\frac{A_{n}}{B_{n}^{2}} = X(nP) = x_{n} + \frac{64m^{2}}{x_{n}^{2}} = \frac{a_{n}^{3} + 64m^{2}b_{n}^{6}}{a_{n}^{2}b_{n}^{2}} .  (17)

Claim: B_{n} > 1, provided max{|a_{n}|, b_{n}^{2}} > 8m. Before this claim can be settled, we must examine the fraction on the righthand side of (17) for possible cancellation. Let d = p^{r} be a common factor of (a_{n}^{3} +64m^{2}b_{n}^{6}) and a_{n}^{2}b_{n}^{2}, where p is a prime and r ∈ ℕ is the highest order of p dividing both terms. Since gcd(a_{n}, b_{n}) = 1, either d | a_{n}^{2} or d | b_{n}^{2}. If the latter occurs, then d | (a_{n}^{3} + 64m^{2}b_{n}^{6}) implies d | a_{n}^{3}, which is impossible as a_{n} and b_{n} are coprime. Thus d can only come from the term a_{n}^{2}, so that d | a_{n}^{3}. We have now that

d | (a_{n}^{3} + 64m^{2}b_{n}^{6}), d | a_{n}^{3}, and d ∤ b_{n}^{6},

so p^{r} = d | 64m^{2}. Hence the greatest common divisor of numerator and denominator of the fraction on the right-hand side of (17), say g, has to divide 64m^{2} as well. To turn to the claim, if |a_{n}| > 8m, then

B_{n}^{2} = \frac{a_{n}^{2}b_{n}^{2}}{g} ≥ \frac{a_{n}^{2}}{g} ≥ \frac{a_{n}^{2}}{64m^{2}} > \frac{64m^{2}}{64m^{2}} = 1.

On the other hand, if b_{n}^{2} > 8m, then g | a_{n}^{2} implies

B_{n}^{2} = \frac{a_{n}^{2}b_{n}^{2}}{g} ≥ b_{n}^{2} > 8m > 1.

Thus we need to ensure that max{|a_{n}|, b_{n}^{2}} > 8m, for our purposes and to that end we turn. Note that the logarithm of the expression on the left is the Weil height h(nP′) of nP′ which we know, from Theorem 4.1, is close to the canonical height ĥ(nP′). Write h = ĥ(P) and h′ = ĥ(P′); then

h = ĥ(P) = ĥ(σ(P′)) = 3ĥ(P′) = 3h′

as σ is a 3-isogeny. Applying the inequality (15) to the curve E′ with Q = nP′, j = 0 and Δ = −16^{3}3^{3}m^{4}, we obtain

log max \{|a_{n}|, b_{n}^{2}\} = h(nP′) > h′n^{2} − \frac{2}{3} log m − \frac{1}{2} log 48 − 2.14. (18)

The height bound [13, (14)] gives

h′ = \frac{h}{3} > \frac{1}{81} log m − 0.039  (19)

for all m ≥ 1. Then (18) becomes

log max \{|a_{n}|, b_{n}^{2}\} > (\frac{1}{81} log m − 0.039) n^{2} − \frac{2}{3} log m − \frac{1}{2} log 48 − 2.14.

Then we can ensure max{|a_{n}|, b_{n}^{2}} > 8m provided that

(\frac{1}{81} log m − 0.039) n^{2} − \frac{2}{3} log m − \frac{1}{2} log 48 − 2.14 > log(8m).  (20)

With a manipulation, (20) will be guaranteed for n > 12 but only for all sufficiently large m. However the amount of checking for smaller values of m is infeasible. More realistically, if m > 353 then (20) is true provided n > 22. Thus it can be concluded that for all m > 353, we have B_{n} > 1 if n > 22. The proof for values m ≤ 353 follows in an appendix, see section 6. □

We are now in a position to prove Theorem 1.2 using Lemma 5.1.

Proof of Theorem 1.2. When n > 12, the term A_{n} is not completely cancelled from the denominator of (7), exactly as before. Also, it follows directly from Lemma 5.1 that B_{n} > 1 for all n > 22. Therefore, the term W_{n} possesses at least two coprime factors for all n > 22. We will go on to prove the same for every 2 ≤ n ≤ 22 case by case. Before this, we give a proof of the second claim in Theorem 1.2. Under the isogeny hypothesis, it follows from [12, Theorem 1.4] that the number of prime power terms B_{n} is uniformly bounded. Combining this with our knowledge that A_{n} has a primitive prime divisor for n > 12 means that the number of terms W_{n} which have at most two distinct prime divisors is uniformly bounded. With sleeves rolled up, we will now show that every term W_{n} fails to be a prime power when 2 < n ≤ 22. We will not invoke the isogeny hypothesis so these results apply in complete generality; that is, we are giving a proof of Lemma 2.2. Finally we will deal with the case when n = 2 assuming the isogeny hypothesis.

Proof of Lemma 2.2. Since (W_{n}) is a divisibility sequence, it suffices to consider W_{n} when n is an odd prime less than 22 or n = 4. We begin with the case when R = (u, v) is an integral point; at the end of the proof we will explain how the general case follows. Case n = 4 We deal firstly with the case when n = 4. Write

4R = (\frac{U_{4}}{W_{4}} , \frac{V_{4}}{W_{4}} ) = (\frac{f_{4}(u, v)}{g_{4}(u, v)}, \frac{f′_{4}(u, v)}{g_{4}(u, v)}) ,

where

\frac{f_{4}(u, v)}{g_{4}(u, v)} = \frac{−u^{16} + 8v^{3}u^{13} + 32v^{6}u^{10} + 28v^{9}u^{7} + 10v^{12}u^{4} + 4v^{15}u}{−u^{15} − 13v^{3}u^{12} − 10v^{6}u^{9} + 10v^{9}u^{6} + 13v^{12}u^{3} + v^{15}},

and

\frac{f′_{4}(u, v)}{g_{4}(u, v)} = \frac{v^{16} − 8u^{3}v^{13} − 32u^{6}v^{10} − 28u^{9}v^{7} − 10u^{12}v^{4} − 4u^{15}v}{−u^{15} − 13v^{3}u^{12} − 10v^{6}u^{9} + 10v^{9}u^{6} + 13v^{12}u^{3} + v^{15}} .

We may consider the second coordinate, and factorize g_{4}(u, v) as a product of four terms:

g_{4,1}(u, v) := v − u
g_{4,2}(u, v) := u^{2} + uv + v^{2} ≡ (v − u)^{2} (mod 3)
g_{4,3}(u, v) := u^{4} + 2u^{3}v + 2uv^{3} + v^{4} ≡ (v − u)^{4} (mod 3)
g_{4,4}(u, v) := u^{8} − 2u^{7}v + 4u^{6}v^{2} + 4u^{5}v^{3} − 5u^{4}v^{4}
+4u^{3}v^{5} + 4u^{2}v^{6} − 2uv^{7} + v^{8}
≡ (v − u)^{8} (mod 3)

We claim that at least two of these factors can avoid being cancelled by the numerator f′_{4}(u, v). Choosing to consider g_{4,3} and g_{4,4}, we can see that the resultants between them and f′_{4} with respect to u and v are

R_{u}(f′_{4}, g_{4,3}) = 3^{16}v^{64} and R_{v}(f′_{4}, g_{4,3}) = 3^{16}u^{64},

respectively, and also

R_{u}(f′_{4}, g_{4,4}) = 3^{32}v^{128} and R_{v}(f′_{4}, g_{4,4}) = 3^{32}u^{128}.

As u and v are coprime,

gcd(f′_{4}(u, v), g_{4,3}(u, v)) | 3^{16} and gcd(f′_{4}(u, v), g_{4,4}(u, v)) | 3^{32}.

Next we will show that both g_{4,3}(u, v) and g_{4,4}(u, v) are not equal, up to a sign, to any power of 3. Suppose, for a contradiction, that g_{4,3}(u, v) = ±3^{k}, for some k > 1. Then

(v − u)^{4} ≡ g_{4,3}(u, v) ≡ 0 (mod 3).

Hence u ≡ v (mod 3), so u^{3} ≡ v^{3} (mod 3^{2}). Replacing this in the expression of g_{4,3}(u, v), we get

0 ≡ u^{4} + 2u^{3}v + 2u^{4} + u^{3}v ≡ 3u^{3}(u + v) (mod 3^{2}).

Then 3 | u or 3 | (u + v). Since u ≡ v (mod 3), the former implies 3 | v, and the latter implies 3 | u and 3 | v which is a contradiction as gcd(u, v) = 1. Thus the possibilities for k such that g_{4,3}(u, v) = ±3^{k} are only 0 and 1. Calculating with PARI-GP [25], without assuming the GRH, shows that the only solutions (u, v) of the equation g_{4,3}(u, v) = ±1 are [0, ±1], [±1, 0] and there are no solutions to g_{4,3}(u, v) = ±3. A similar argument will be applied for the second factor g_{4,4}(u, v). Suppose g_{4,4}(u, v) = ±3^{k} for some k > 2. As (v − u)^{8} ≡ g_{4,4}(u, v) ≡ 0 (mod 3), we have u ≡ v (mod 3), so that

u^{3} ≡ v^{3} (mod 3^{3}), 10u^{3} ≡ v^{3} (mod 3^{3}), or 19u^{3} ≡ v^{3} (mod 3^{3}).

Replacing each of these in the expression of g_{4,4}, we find that there are no solutions to g_{4,4}(u, v) = ±3^{k} when k > 2. Thus it remains to solve the equations g_{4,4}(u, v) = ±3^{k} when 0 ≤ k ≤ 2. The only solutions to

g_{4,4}(u, v) = ±1 are [±1, 0], [0, ±1], [−1, 1], [1, −1].

However these correspond to values of m (±1 or 0) which yield rank zero (or singular) curves. Finally, GP says there are no solutions at all to g_{4,4}(u, v) = ±3^{k} when k = 1, 2. We will prove moreover that the multiple g_{4,3}(u, v)g_{4,4}(u, v) cannot be a prime power. As above, g_{4,3} and g_{4,4} are not powers of 3, so write

g_{4,3}(u, v) = ±3^{m}p_{1}^{m_{1}} ⋯ p_{r}^{m_{r}} and g_{4,4}(u, v) = ±3^{n}q_{1}^{n_{1}} ⋯ q_{s}^{n_{s}},

where the p_{i} and q_{j} are primes other than 3. Considering the resultant between g_{4,3} and g_{4,4}, we get gcd(g_{4,3}(u, v), g_{4,4}(u, v)) | 3^{10}. Thus there is at least one prime p_{i} which is not equal to any prime q_{j}. This implies W_{4} is not a prime power. Case n = 3 The expression for 3R can be written as

3R = (\frac{u^{9} + 6u^{6}v^{3} + 3u^{3}v^{6} − v^{9}}{3uv(u^{6} + u^{3}v^{3} + v^{6})} , \frac{−u^{9} + 3u^{6}v^{3} + 6u^{3}v^{6} + v^{9}}{3uv(u^{6} + u^{3}v^{3} + v^{6})} ) .

For convenience, let

f_{3}(u, v) = −u^{9} + 3u^{6}v^{3} + 6u^{3}v^{6} + v^{9} and g_{3}(u, v) = u^{6} + u^{3}v^{3} + v^{6}.

By the theory of resultants, we obtain

gcd(f_{3}(u, v), g_{3}(u, v)) | 3^{9}.

Since at least one of u, v is not a unit, to complete the proof in this case we have to prove that the denominator g_{3}(u, v) is not (up to sign) a power of 3. Suppose g_{3}(u, v) = ±3^{k} for some k > 1. Then (u − v)^{6} ≡ g_{3}(u, v) ≡ 0 (mod 3). Thus u^{3} ≡ v^{3} (mod 3^{2}), and hence

0 ≡ u^{6} + u^{3}v^{3} + v^{6} ≡ 3u^{6} (mod 3^{2}),

so 3 | u. This implies 3 | v which is impossible. For the remaining values, when k = 1 the solutions are [1, 1] and [−1, −1] and when k = 0, the only solutions are given by

(u, v) = [±1, 0], [0, ±1], [1, −1], [−1, 1].

As before, these all correspond to impossible values of m (0, ±1, ±2). Since gcd(u, v) = 1 and u and v are coprime to both f_{3}(u, v) and g_{3}(u, v) but are not both units (as m ≠ 0, ±2), W_{3} possesses at least two coprime divisors. Case n ≡ 1 (mod 3) The proof in this case proceeds exactly in the same way as in the case n = 4, by the following steps.

(i) Write

nR = (\frac{U_{n}}{W_{n}} , \frac{V_{n}}{W_{n}} ) = (\frac{f_{n}(u, v)}{g_{n}(u, v)}, \frac{f′_{n}(u, v)}{g_{n}(u, v)}) ,

and factor the denominator g_{n}(u, v) as g_{n,1}(u, v), g_{n,2}(u, v), ..., g_{n,k}(u, v), all of which are homogeneous in u and v. By the theory of resultants, we have found fortunately that for each n, gcd(f′_{n}(u, v), g_{n,i}(u, v)) divides a power of 3 for every i = 1, ..., k.

(ii) Pick two factors of g_{n}, say g_{n,i}(u, v) and g_{n,j}(u, v). It can be proved that both of them cannot be a power of 3 (up to sign) by using the following facts:

g_{n,i}(u, v) ≡ (u − v)^{deg(g_{n,i})} (mod 3),
g_{n,j}(u, v) ≡ (u − v)^{deg(g_{n,j})} (mod 3).

(iii) Show that the multiple g_{n,i}g_{n,j} is not a prime power, for which it is sufficient to prove that the resultant of g_{n,i} and g_{n,j} is a power of 3.

Case n ≡ 2 (mod 3) In this case, the situation is more complicated. For all n, f′_{n}(u, v) and g_{n}(u, v) also behave as in the previous case in steps (i) and (iii). However, matters are slightly different in step (ii). We need to employ some facts about Newton polygons over 3-adic fields to know about the 3-adic valuation of g_{n,i}. We will show how to do this for n = 5 (for other n, the proofs will proceed in the same way). We have

g_{5,1}(u, v) = u^{8} − 2u^{7}v − 2u^{6}v^{2} + u^{5}v^{3} − 5u^{4}v^{4} + u^{3}v^{5} − 2u^{2}v^{6} − 2uv^{7} + v^{8},

and

g_{5,2}(u, v) = u^{16} + 2u^{15}v + 6u^{14}v^{2} − 2u^{13}v^{3} + 11u^{12}v^{4}
+21u^{11}v^{5} − 11u^{10}v^{6} − u^{9}v^{7} + 27u^{8}v^{8} − u^{7}v^{9} − 11u^{6}v^{10}
+21u^{5}v^{11} + 11u^{4}v^{12} − 2u^{3}v^{13} + 6u^{2}v^{14} + 2uv^{15} + v^{16}.

We will explore their roots of the polynomials h_{5,i}(X) = g_{5,i}(1+X, 1), where we find

h_{5,1}(X) = X^{8} + 6X^{7} + 12X^{6} + 3X^{5} − 30X^{4} − 63X^{3} − 63X^{2} − 36X − 9,

and

h_{5,2}(X) = X^{16} + 18X^{15} + 156X^{14} + 852X^{13} + 3261X^{12} + 9279X^{11}
+20394X^{10} + 35496X^{9} + 49617X^{8} + 55971X^{7} + 50814X^{6}
+36774X^{5} + 20871X^{4} + 9072X^{3} + 2916X^{2} + 648X + 81.

The Newton polygons for h_{5,1} and h_{5,2} with p = 3, as shown in Figures 1 and 2, reveal that the slope of the only segment of each polygon is −\frac{1}{4}. By the standard facts about Newton Polygons, all roots of h_{5,i}(X) (and all roots of h_{11,i}(X) and h_{17,i}(X)) have 3-adic absolute values 3^{− \frac{1}{4}} . If α is a root of h_{5,i}(X) then, since |u/v − 1|_{3} ≠ |α|_{3},

|\frac{u}{v} − (1 + α)|_{3} ≥ |α|_{3} = 3^{− \frac{1}{4}} .

Thus, since |u|_{3} = |v|_{3} = 1,

|g_{5,i}(u, v)|_{3} = |h_{5,i} (\frac{u}{v} − 1)|_{3} = ∏_{α} |\frac{u}{v} − (1 + α)|_{3} ≥ (3^{− \frac{1}{4}} )^{deg(g_{5,i})},

where α ranges over all roots of h_{5,i}(X); that is, the 3-adic valuation of g_{5,i}(u, v) is at most deg(g_{5,i})/4. It remains only to solve the equations

Figure 1. Newton polygon of h_{5,1}(X)

g_{5,i}(u, v) = ±3^{k}, with 0 ≤ k ≤ deg(g_{5,i})/4. We find that the only solutions to g_{5,1}(u, v) = ±3^{0} are [0, ±1], [±1, 0] and there are no solutions to g_{5,1}(u, v) = ±3^{k} for other k. Similarly, the only solutions for g_{5,2} arise for g_{5,2}(u, v) = 3^{0}, with [±1, 0], [0, ±1], [−1, 1], [1, −1], and for g_{5,2}(u, v) = 3^{4}, with [1, 1] and [−1, −1]. As before, these correspond to inadmissible values of m.

Figure 2. Newton polygon of h_{5,2}(X)

This concludes the proof of Lemma 2.2 when we consider integral points. In the case of rational points, write

R = (\frac{u_{0}}{w_{0}} , \frac{v_{0}}{w_{0}} ) ∈ C(ℚ)

in lowest terms. The condition that m is cube-free implies u_{0} and v_{0} are coprime. Replacing u and v in the expressions of nR in previous cases by u_{0}/w_{0} and v_{0}/w_{0} respectively, we obtain

nR = (\frac{f_{n}(u_{0}, v_{0})}{w_{0}g_{n}(u_{0}, v_{0})}, \frac{f′_{n}(u_{0}, v_{0})}{w_{0}g_{n}(u_{0}, v_{0})}) .

Now proceed with the proof working with f_{n}(u_{0}, v_{0}) and g_{n}(u_{0}, v_{0}): the conclusion follows as before. Thus we have proved Lemma 2.2. □

Case n = 2 To complete the proof of Theorem 1.2 it remains only to treat the case n = 2; the salient details follow. Here we begin with the curve C′ in (2). In a change of notation, we write (u, v) ∈ C′(ℚ) for a point which maps to R under the isogeny τ. For now we assume it is integral, noting that this implies gcd(u, v) = 1 since m is cube-free. We write

2R = (\frac{f_{2}(u, v)}{g_{2}(u, v)}, \frac{f′_{2}(u, v)}{g_{2}(u, v)}) ,

where

g_{2}(u, v) = −3(u − v)(u + 2v)(2u + v)(u^{2} + uv + v^{2})
(u^{6} + 3u^{5}v + 60u^{4}v^{2} + 115u^{3}v^{3} + 60u^{2}v^{4} + 3uv^{5} + v^{6}).

Write g_{2,1}(u, v) for the product of the linear factors and g_{2,2}(u, v) for the degree 6 factor. Firstly, we claim that the factor g_{2,1}(u, v) does not completely cancel with the numerator f_{2}(u, v). This is easy to check: compute the resultant of each of the linear factors in g_{2,1}(u, v) with f_{2}(u, v). Every time you obtain a power of 3. If g_{2,1}(u, v) cancels then each of the linear factors is a power of 3 (possibly 3^{0}). This cannot happen since

(2u + v) − (u + 2v) = u − v

and the equation 3^{a} + 3^{b} = 3^{c} has no solutions. Similarly, the factor g_{2,2}(u, v) is not cancelled by f_{2}(u, v). Checking resultants shows any common division is a power of 3. Now g_{2,2}(u, v) ≡ 0 (mod 3^{6}) forces u ≡ v ≡ 0 (mod 3) so we only need to consider

g_{2,2}(u, v) = ±3^{r} with gcd(u, v) = 1 and r = 0, …, 5.

The only solutions occur when g_{2,2}(u, v) = 1 and g_{2,2}(u, v) = 3^{5}. In the first case, they are

[1, 0], [−1, 0], [1, −1], [0, −1], [−1, 1], [0, 1],

each giving the inadmissible value m = 0. In the second case, they are

[1, −2], [2, −1], [−1, −1], [−2, 1], [1, 1], [−1, 2],

giving the inadmissible values m = ±2.

Finally, the only common divisor of g_{1,2}(u, v) and g_{2,2}(u, v) is a power of 3 so we must obtain one non-trivial factor of W_{2} from the first term and a coprime factor from the second, which proves that W_{2} is not a prime power. When (u, v) is not integral, things are slightly different from the situation for 2 < n ≤ 22 above, because u and v might have different denominators. Write u = a/hb and v = c/hd with gcd(a, b) = gcd(c, d) = gcd(b, d) = 1. Then also gcd(a, c) = 1 (as m is cube-free). Writing u_{0} = ad and v_{0} = bc, which are coprime, we obtain

2R = (\frac{f_{2}(u_{0}, v_{0})}{bdhg_{2}(u_{0}, v_{0})}, \frac{f′_{2}(u_{0}, v_{0})}{bdhg_{2}(u_{0}, v_{0})})

so we can proceed as before. □

6. Appendix

In order to complete the proof of Lemma 5.1, it remains to check the statement (20) for all cube-free integers m up to 353, as mentioned at the end of the proof. In this part, we deal with the particular computations to find a uniform bound, N_{0}, on the indices n for such m. Ranks and generators of E : Y^{2} = X^{3} − 432m^{2} were computed using MAGMA [23]. Note that when m = 337, we were unable to find the generator and rank using MAGMA. This was found instead using SAGE [29]. For rank-1 curves, we tested the elliptic divisibility sequence (B_{n}) arising from the generator for n = 1, ..., 22. A special argument is required for the curves of rank 2, with two parts needed to find the bound N_{0}. Firstly find the finite set of pairs (i, j), i, j ∈ ℤ, such that the canonical height of each point iP + jQ is less than 40, where P and Q represent the generators. Then compute the elliptic divisibility sequence (B_{n}) arising from each point iP + jQ, for n = 1, ..., 22. Now we get a bound, say N′_{0}, for the indices n from the points of canonical height less than 40. To treat all cases, when h > 40, we return to the proof of Lemma 5.1 again, replacing the estimate (19) by

h′ > \frac{h}{3} > \frac{40}{3}.

This leads to

\frac{40}{3}n^{2} − \frac{2}{3} log m − \frac{1}{2} log 48 − 2.14 > log(8m).

Taking specific values for m such that E has rank-2 gives another bound, say N′′_{0}, for the indices n. Comparing N′_{0} and N′′_{0}, let

N_{0} = min{N′_{0}, N′′_{0}}.

In no case did N_{0} exceed 1 for curves of rank 1 and 2. There are no curves of higher rank appearing in that range.

References

[1] P. T. Bateman and R. A. Horn, A heuristic asymptotic formula concerning the distribution of prime numbers, Math. Comp. 16 (1962), 363–367.

[2] C. Caldwell, www.primes.utm.edu/mersenne/
[3] C. Caldwell, www.primes.utm.edu/glossary/xpage/FibonacciPrime.html

[4] J. W. S. Cassels, Lectures on Elliptic Curves London Mathematical Society Student Texts, 24, Cambridge University Press, Cambridge, 1991

[5] D. V. Chudnovsky and G. V. Chudnovsky, Sequences of numbers generated by addition in formal groups and new primality and factorization tests, Adv. in Appl. Math. 7 (1986), 385–434.

[6] G. Cornelissen and K. Zahidi, Elliptic divisibility sequences and undecidable problems about rational points, J. Reine Angew. Math. 613 (2007), 1–33.

[7] M. Einsiedler, G. Everest and T. Ward, Primes in elliptic divisibility sequences, LMS J. Comput. Math. 4 (2001), 1–13.

[8] N. D. Elkies and N. F. Rogers, Elliptic Curves x^{3} + y^{3} = k of high rank, Lecture Notes in Computer Science 3076 (ANTS-VI, 2004; D. Buell, ed.), 184–193.

[9] P. Erdõs, Arithmetical properties of polynomials, J. London Math. Soc. 28 (1953), 416–425.

[10] G. Everest and K. Eistenträger, Descent on elliptic curves and Hilbert’s tenth problem, Proc. Amer. Math. Soc. 137 (2009), 1951–1959.

[11] G. Everest and H. King, Prime powers in elliptic divisibility sequences, Math. Comp. 74 (2005), 2061–2071.

[12] G. Everest, P. Ingram, V. Mahé, and S. Stevens, The uniform primality conjecture for elliptic curves, Acta Arith., 134 (2008), 157–181.

[13] G. Everest, P. Ingram, and S. Stevens, Primitive divisors on twists of the Fermat cubic, LMS J. Comput. Math. 12 (2009), 54–81.

[14] G. Everest, G. McLaren, and T. Ward, Primitive divisors of elliptic divisibility sequences, J. Number Theory 118 (2006), 71–89.

[15] G. Everest, V. Miller and N. Stephens, Primes generated by elliptic curves, Proc. Amer. Math. Soc. 132 (2004), 955–963.

[16] P. Ingram, Elliptic divisibility sequences over certain curves, J. Number Theory 123 (2007), 473–486.

[17] P. Ingram, Multiples of integral points on elliptic curves, J. Number Theory 129 (2009), 182–208.

[18] P. Ingram, A quantitative primitive divisor result for elliptic divisibility sequences, J. Théor. Nombres Bordeaux, to appear.

[19] P. Ingram and J. H. Silverman, Uniform estimates for primitive divisors in elliptic divisibility sequences, to appear in a forthcoming memorial volume for Serge Lang, published by Springer-Verlag.

[20] T. Jedrzejak, Height estimates on cubic twists of the Fermat elliptic curve, Bull. Austral. Math. Soc. 72 (2005), 177–186.

[21] W. Keller, Prime factors of Fermat numbers, www.prothsearch.net/fermat.html [22] K. E. Lauter and K. Stange, The elliptic curve discrete logarithm problem and equiv-

alent hard problems for elliptic divisibility sequences, arxiv.org/abs/0803.0728

[23] MAGMA, www.magma.maths.usyd.edu.au/magma/index.html

[24] V. Mahé, Prime power terms in elliptic divisibility sequences,

arxiv.org/abs/1002.4202
[25] PARI-GP, www.parigp-home.de

[26] O. Phuksuwan, On the Primality Conjecture for Certain Elliptic Divisibility Sequences, PhD Thesis, University of East Anglia, 2010.

[27] B. Poonen, Hilbert’s Tenth Problem and Mazur’s Conjecture for large subrings of ℚ, J. Amer. Math. Soc. 16 (2003), 981–990.

[28] B. Poonen and A. Shlapentokh, Diophantine Definability of Infinite Discrete non-Archimedean Sets and Diophantine Models for Large Subrings of Number Fields, J. Reine Angew. Math. 588 (2005) 27–47.

[29] SAGE, www.sagemath.org

[30] R. Shipsey, Elliptic divisibility sequences, PhD thesis, University of London, 2000.

[31] A. Shlapentokh, Hilbert’s Tenth Problem: Diophantine Classes and Other Extensions to Global Fields, Cambridge University Press, 2006.

[32] J. H. Silverman, The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics 106, Springer-Verlag, New York, 1986.

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

[34] J. H. Silverman, Advanced Topics in the Arithmetic of Elliptic Curves, Graduate Texts in Mathematics 151, Springer-Verlag, New York, 1994.

[35] J. H. Silverman, Common divisors of elliptic divisibility sequences over function fields, Manuscripta Math. 114 (2004), 431–446.

[36] J. H. Silverman, p-adic properties of division polynomials and elliptic divisibility sequences, Math. Ann. 332 (2005), 443–471.

[37] J. H. Silverman and K. E. Stange, Terms in elliptic divisibility sequences divisible by

    their indices, arxiv.org/abs/1001.5303

[38] J. H. Silverman and N. Stephens, The sign of an elliptic divisibility sequence, J. Ramanujan Math. Soc. 21 (2006), 1–17.

[39] M. Streng, Divisibility sequences for elliptic curves with complex multiplication, Algebra Number Theory 2 (2008), 183–208.

[40] M. Ward, Memoir on elliptic divisibility sequences, Amer. J. Math. 70 (1948), 31–74.

School of Mathematics, University of East Anglia, Norwich NR4 7TJ, UK

E-mail address: g.everest@uea.ac.uk
E-mail address: o.phuksuwan@uea.ac.uk
E-mail address: s.stevens@uea.ac.uk