ON PERFECT POWERS IN LUCAS SEQUENCES

YANN BUGEAUD, FLORIAN LUCA, MAURICE MIGNOTTE, SAMIR SIKSEK

Abstract. Let (u_{n})_{n≥0} be the binary recurrent sequence of integers given by u_{0} = 0, u_{1} = 1 and u_{n+2} = 2(u_{n+1} + u_{n}). We show that the only positive perfect powers in this sequence are u_{1} = 1 and u_{4} = 16.

We also discuss the problem of determining perfect powers in Lucas sequences in general.

1. Introduction and Results

Recently, Bugeaud, Mignotte and Siksek [7] showed that if (F_{n})_{n≥0} is the Fibonacci sequence given by F_{0} = 0, F_{1} = 1 and F_{n+2} = F_{n+1} + F_{n} for n ≥ 0, then F_{n} is a perfect power only for n = 0, 1, 2, 6 and 12; equivalently F_{n} ∈ {0, 1, 8, 144}. Their method combines the classical approach to Diophantine equations via linear forms in logarithms with the modular approach via Frey curves. This method applies to a large class of Diophantine problems including the determination of all the perfect powers in the set of values taken by quadratic polynomials (see [8], for example).

The five main steps used in [7] to solve the equation

F_{n} = y^{p}, n > 2, p > 3,

are the following (we simplify a little):

Step 1. Using some (new) lower bounds for linear forms in three logarithms one gets an upper bound on the (prime) exponent p, say

p < 2 × 10^{8};

Step 2. The modular method is used for all p < 2 × 10^{8} to prove the congruence

n ≡ ±1 (mod p),

(the computer time was around 50 hours);

Step 3. The previous condition allows us to view the initial linear form in three logarithms as a linear form in two logarithms, which leads to the important progress

p ≤ 733;

Step 4. A detailed study of the family of Thue equations corresponding to the range 5 ≤ p ≤ 733 leads to the condition

n < 10^{9000},

(recall that n is an index!);

Step 5. Using once more the modular method one proves that there is no solution for 5 ≤ p ≤ 733 (the computer time was less than 100 hours). The proof is complete since the solutions for p = 2 and p = 3 were known for many years.

Date: May 24, 2005.

The principal goal of this note is to show that this method works—at least in principle—for a larger family of equations, namely that it can be applied to determine the complete list of perfect powers in a wide class of Lucas sequences.

Definition. A Lucas pair is a pair (α, β) of algebraic integers such that α + β and αβ are non-zero rational integers and α/β is not a root of unity. For a given Lucas pair (α, β), one defines the corresponding Lucas sequence by

u_{n} = u_{n}(α, β) = \frac{α^{n} − β^{n}}{α − β} (n = 0, 1, 2, …).

The Fibonacci sequence is clearly the Lucas sequence corresponding to the Lucas pair ((1 + \sqrt{5})/2, (1 − \sqrt{5})/2). We study the equation

u_{n} = y^{p},

in integers n ≥ 0, y and prime exponent p ≥ 2. For any p, it has the trivial solution u_{1} = 1^{p}, and also sometimes the trivial solution u_{−1} = ±1^{p} (exactly when αβ = ±1). The existence of solutions for any p makes its complete resolution very difficult, since one can no longer hope to solve it by only using congruences to suitable moduli. One important step is to prove, for large n, that

n ≡ 1 (mod p) or n ≡ ±1 (mod p),

respectively. This was a difficult part of the proof for the Fibonacci case, which corresponds to Steps 1 and 2 above. Here, we present an example where this part is rather easy. Moreover, for this example we try to minimize the time of computer verification.

Theorem 1. Let (u_{n})_{n≥0} be the binary recurrent sequence defined by the initial values u_{0} = 0, u_{1} = 1 and the recurrence u_{n+2} = 2(u_{n+1} + u_{n}). The only positive perfect powers in the sequence (u_{n})_{n≥0} are u_{1} = 1 and u_{4} = 16.

The sequence (u_{n}) appearing in Theorem 1 is in fact the Lucas sequence corresponding to the Lucas pair (1 + \sqrt{3}, 1 − \sqrt{3}). As shown by the proof of Theorem 1, the method used in [7] can be simplified for many Lucas sequences (u_{n})_{n≥0}. Roughly speaking, for a certain class of Lucas sequences, one can skip or significantly simplify the first two steps of the above proof-scheme and begin directly with the study of a linear form in two logarithms, which leads of course to rather good upper bounds for the exponent p in the equation u_{n} = y^{p}. This is precisely the case for the sequence considered in Theorem 1. This is also the case with the Nagell–Ljunggren equation

\frac{x^{n} − 1}{x − 1} = y^{p}

(see the survey [6]).

We postpone to Section 8 more information on the class of Lucas sequences (u_{n})_{n≥0} for which it is possible to avoid or significantly simplify the first two steps of the above proof-scheme. Some related open problems are briefly evoked in Section 9. Sections 2 to 7 are devoted to the proof of Theorem 1. More precisely, Sections 2 and 3 (resp. Section 4, Section 5, Sections 6 to 7) correspond to Steps 1 and 2 (resp. Step 3, Step 4, Step 5) of the above scheme of proof.

Throughout this paper, for a prime number p and a positive integer m we write ord_{p}(m) for the order at which p appears in the factorization of m. For a positive real number x, we write ⌊x⌋ for the largest positive integer smaller than or equal to x, the ‘floor’ function, whereas ⌈x⌉ is the ‘ceiling’ function, that is the smallest positive integer greater than or equal to x.

Throughout Sections 2 to 7, we let (u_{n})_{n≥0} be the binary recurrent sequence given by u_{0} = 0, u_{1} = 1 and u_{n+2} = 2(u_{n+1} + u_{n}) for n ≥ 0.

Acknowledgments. This paper was initiated during a visit of the second author at the Université Louis Pasteur, Strasbourg, in September 2004. He warmly thanks the Mathematical Department for its hospitality. The first three authors were supported in part by the joint Project France-Mexico ANUIES-ECOS M01-M02.

The authors warmly thank the referee for several useful comments.

2. Preliminary Results

We start with the following elementary result.

Lemma 2.1. If n ≥ 1, then

(1)  ord_{2}(u_{n}) = ⌊n/2⌋ + ord_{2}(n) + δ_{n},

where δ_{n} = 0 if n is odd or if 4 divides n, and δ_{n} = −1 otherwise.

Proof. The characteristic equation of the sequence (u_{n})_{n≥0} is

x^{2} − 2x − 2 = 0.

Its roots are α = 1 + \sqrt{3} and β = 1 − \sqrt{3}, thus the general term of the sequence (u_{n})_{n≥0} is given by

(2)  u_{n} = \frac{α^{n} − β^{n}}{α − β} = \frac{1}{2\sqrt{3}} (α^{n} − β^{n}) .

Setting α_{1} = α/\sqrt{2} and β_{1} = β/\sqrt{2}, we get

u_{n} = \frac{2^{n/2}}{2\sqrt{3}} (α_{1}^{n} − β_{1}^{n}) .

Note that α_{1} and β_{1} are algebraic integers which are biquadratic units. Assume first that n is odd. Then

u_{n} = 2^{⌊n/2⌋} (\frac{α_{1}^{n} − β_{1}^{n}}{α_{1} − β_{1}} ) .

One checks easily that the numbers

ũ_{k} = \frac{α_{1}^{2k+1} − β_{1}^{2k+1}}{α_{1} − β_{1}} = \frac{α · (2 + \sqrt{3})^{k} − β · (2 − \sqrt{3})^{k}}{α − β}

are all odd integers for k = 0, 1, … In fact, ũ_{0} = 1, ũ_{1} = 3 are both odd and the recurrence

ũ_{k+2} = 4ũ_{k+1} − ũ_{k}

holds for all k ≥ 0 (notice that 2±\sqrt{3} are the roots of the polynomial X^{2} −4X +1). Clearly, ũ_{k+2} ≡ ũ_{k} (mod 2), and by induction on the parameter k, we get that indeed ũ_{k} is odd for all k ≥ 0. Hence, formula (1) holds for odd values of n.

From now on, we assume that n = 2k is even. Let α_{2} = α_{1}^{2} = 2 + \sqrt{3} and β_{2} = β_{1}^{2} = 2 − \sqrt{3}. Then

u_{2k} = 2^{k} (\frac{α_{2}^{k} − β_{2}^{k}}{α_{2} − β_{2}} ) = 2^{n/2}w_{k}, where w_{k} = \frac{α_{2}^{k} − β_{2}^{k}}{α_{2} − β_{2}} .

It remains to show that ord_{2}(w_{k}) = ord_{2}(n) + δ_{n} = ord_{2}(k) + δ_{2k} + 1. We first prove that this is the case when k = 2^{s} for some integer s ≥ 0, and we shall treat the general case later. For s ≥ 0, we let z_{s} = α_{2}^{2^{s}} + β_{2}^{2^{s}}. It is clear that z_{s} is an integer. Note that w_{2^{0}} = w_{1} = 1, w_{2^{1}} = z_{0} = α_{2} + β_{2} = 4, and

w_{2^{s}} = ∏_{0≤k≤s−1} z_{k}

for all s ≥ 1. Furthermore, if s ≥ 1, then

z_{s} = α_{2}^{2^{s}} + β_{2}^{2^{s}} = (α_{2}^{2^{s−1}} + β_{2}^{2^{s−1}})^{2} − 2(α_{2}β_{2})^{2^{s−1}} = z_{s−1}^{2} − 2.

Reducing the above relation modulo 4, since z_{0} = 4, we get, by induction on s ≥ 1, that ord_{2}(z_{s}) = 1 for all s ≥ 1. Hence, ord_{2}(w_{2^{s}}) = s + 1 if s ≥ 1 and is 0 if s = 0. Thus, formula (1) holds when n = 2k and k = 2^{s} for some s ≥ 0. In now suffices to prove it when n = 2k and k = 2^{s}m, where m ≥ 3 is some odd integer. In this case,

u_{2k} = 2^{k}w_{k} = 2^{k}w_{2^{s}} (\frac{w_{2^{s}m}}{w_{2^{s}}} ) .

It suffices to show that the quotient in the right-hand side is an odd integer. However,

\frac{w_{2^{s}m}}{w_{2^{s}}} = \frac{α_{2}^{2^{s}m} − β_{2}^{2^{s}m}}{α_{2}^{2^{s}} − β_{2}^{2^{s}}} = ∑_{t=0}^{m−1} α_{2}^{2^{s}t}β_{2}^{2^{s}(m−t−1)}.

Clearly,

α_{2}^{2^{s}t} = (z_{s} − β_{2}^{2^{s}})^{t} ≡ (−1)^{t}β_{2}^{2^{s}t} (mod 2)

(here, we say that two algebraic integers λ and μ are congruent modulo 2 if (λ−μ)/2 is also an algebraic integer). Thus,

∑_{t=0}^{m−1} α_{2}^{2^{s}t}β_{2}^{2^{s}(m−1−t)} ≡ ∑_{t=0}^{m−1}(−1)^{t}β_{2}^{2^{s}(m−1)} ≡ mβ_{2}^{2^{s}(m−1)} ≡ β_{2}^{2^{s}(m−1)} (mod 2),

as m is odd. Since β_{2} is a unit, it follows that the integer w_{2^{s}m}/w_{2^{s}} is odd. The lemma is therefore proved. □

Classically, we introduce the (Lucas) companion sequence to (u_{n})_{n≥0}, that is the sequence (v_{n})_{n≥0} defined by

v_{n} = α^{n} + β^{n}, (n ≥ 0),

so that

v_{0} = 2, v_{1} = 2, v_{n+2} = 2(v_{n+1} + v_{n}) for n ≥ 0.

Then, one checks easily that

(3)  12 u_{n}^{2} − v_{n}^{2} = −(−2)^{n+2},

and that

(4)  u_{2n} = u_{n}v_{n}

hold for any n ≥ 0.

Corollary 2.2. The sequence v_{n} = α^{n} + β^{n}, where α = 1 + \sqrt{3} and β = 1 − \sqrt{3}, satisfies

ord_{2}(v_{n}) = \begin{cases}⌈n/2⌉, & if n is odd, \\ 2 + n/2, & if 2 || n, \\ 1 + n/2, & if 4 | n. \end{cases}

Proof. We use the relation 12u_{n}^{2} − v_{n}^{2} = ±2^{n+2} and the above Lemma 2.1.

If n is odd, then 2^{n+1} || 12u_{n}^{2}, and we get easily that 2^{n+1} || v_{n}^{2}; hence, the result in this case.

If 2 || n, then 2^{n+2} || 12u_{n}^{2} and

v_{n}^{2} = 12u_{n}^{2} + 2^{n+2} ≡ 2^{n+4} (mod 2^{n+5}),

and we see that 2^{2+n/2} || v_{n}.

If n is a multiple of 4, then 2^{n+4} divides 12u_{n}^{2} and

v_{n}^{2} = 12u_{n}^{2} + 2^{n+2} ≡ 2^{n+2} (mod 2^{n+4}),

and the asserted result follows. □

3. Reductions

In this section, we prove the following result.

Proposition 3.1. Let (u_{n})_{n≥0} be the binary recurrent sequence given by u_{0} = 0, u_{1} = 1 and u_{n+2} = 2(u_{n+1} + u_{n}).

The only squares in this sequence are u_{0} = 0, u_{1} = 1 and u_{4} = 16.

The equation

u_{n} = y^{p}, for p prime ≥ 3,

has only the solution n = 0 for n even. If n is odd and greater than 1, then n > 100 and p ≥ 41, and if such a solution exists, then there exists at least one solution with n prime.

Proof. Firstly, we determine the squares among the sequence (u_{n})_{n≥0}. Suppose that u_{n} is a square, say u_{n} = z^{2}. Then the relation (3) implies

12z^{4} − v_{n}^{2} = −(−2)^{n+2}.

If n is odd, then ord_{2}(u_{n}^{2}) = n − 1 and ord_{2}(v_{n}^{2}) = n + 1. Thus, we get a relation of the form

3X^{4} = Y^{2} + 2.

Working in the imaginary quadratic field ℚ(\sqrt{−2}), we easily see that this relation leads to the Thue equation

a^{4} + 4a^{3}b − 12a^{2}b^{2} − 8ab^{3} + 4b^{4} = ±1.

Using PARI, in less than 0.1 second we get that the only solutions are the trivial ones, namely (a, b) = (±1, 0). This implies that u_{n} = 2^{(n−1)/2}. Considering the rate of growth of u_{n} that is immediate from equation (2), we deduce that n = 1.

If n is even then, using Lemma 2.1, we see that ν := ord_{2}(n) must be even and the relation (3) implies now

3 · 2^{n+2ν+2} · X^{4} − 2^{n+2}Y^{2} = −2^{n+2},

where X and Y are odd integers. After simplification, we get a relation of the form

3Z^{4} − Y^{2} = −1.

This kind of equation has been studied by Ljunggren [18], who proved that it cannot have more than two solutions in positive integers. Since (Z, Y) = (1, 2) and (2, 7) are two positive solutions, there are no other ones. Consequently, the only positive squares in the sequence (u_{n})_{n≥0} are u_{1} = 1 and u_{4} = 16.

Suppose now that u_{n} = y^{p} where p is prime and n = 2m is even. Then, by the two above formulas (3) for the index n and (4), there are positive odd numbers X and Y such that

u_{m} = 2^{r}X^{p}, v_{m} = 2^{s}Y^{p}

for some non negative integers r and s, and (3) — now for the index m — gives

12 · 2^{2r}X^{2p} − 2^{2s}Y^{2p} = −(−2)^{m+2}.

If m is odd, by Lemma 2.1 and Corollary 2.2, the previous relation becomes

3 X^{2p} − Y^{2p} = 2.

By a result of Bennett [2] this implies X^{2} = Y^{2} = 1, which gives no solutions for u_{n} = y^{p} in this case (that is, when ord_{2}(n) = 1).

If ord_{2}(m) = 1, then equation (3), for the index m, gives after simplification

3 X^{2p} − 4Y^{2p} = −1.

By another result of Bennett [1], this implies again X = Y = 1, which gives again no solutions for u_{n} = y^{p} in this case (that is when ord_{2}(n) = 2).

If 4 | m, then, putting γ = ord_{2}(m) so that γ ≥ 2, we get

3 · 2^{2γ}X^{2p} − Y^{2p} = −1.

By Theorem 1.5 of Bennett and Skinner [3], this equation has no nontrivial solution if p ≥ 7 and γ ≥ 3. But in this case, we can also proceed as follows. Put m = 2k. Then v_{k} = 2^{t}Z^{p}, where Z is some positive odd integer and

v_{k}^{2} = v_{m} + 2^{k+1}.

If 2 || k (that is, if γ = 2), then, after simplification, we get

8Z^{2p} = Y^{p} + 1,

where v_{k} = 2^{t}Z^{p} for some positive integers t and Z with Z odd, and Theorem 1.2 of Bennett and Skinner [3] says that this equation has no nontrivial solution if p ≥ 7. If 4 | k, then the simplification gives

2Z^{2p} = Y^{p} + 1,

and a theorem of Darmon and Merel [11] implies that there is no nontrivial solution (that is with |Y Z| > 1) for p ≥ 3. To summarize, the only remaining cases (for n even) correspond to the solutions of the Diophantine equation

8Z^{2p} − Y^{p} = 1, p < 7.

It is easy to see that this equation has no nontrivial solution for p = 3 [use the factorization 8Z^{3} − Y^{6} = (2Z − Y^{2})(4Z^{2} + 2ZY^{2} + Y^{4})], and a direct application of PARI (to the Thue equation 8X^{p} − Y^{p} = 1), for p = 5 proves that there is no solutions for u_{n} = y^{p} (with 8 | n) for p = 5.

Moreover, a short and easy computation (a few seconds with PARI) shows that for a prime p ≥ 3,

u_{n} = y^{p} ⟹ n ≤ 4 or n > 100.

Finally, when n > 1 is odd, considering the Thue equations associated to the equations u_{n} = y^{p} for p ∈ {3, 5, …, , 37}, using PARI (the time of computation being around 30 minutes), we see that there is no solution for these exponents. We are very grateful to Guillaume Hanrot who wrote an extension of PARI, Version 2.2.8 (development CHANGES-1.1035), which contains a new treatment of Thue equations based on his paper [12]. In this paper, he showed that the knowledge of a subgroup of finite index in the full group of units is actually sufficient to solve a Thue equation (one bottleneck of the classical algorithm is the computation of the unit group of the field). With this new software, we can solve Thue equations of rather large degree in a reasonable time and get a guaranteed result (the older version used GRH to give a fast non-guaranteed result and the algorithm without assuming GRH was terribly slow for medium size examples).

Applying also an argument found independently by Pethő [24] and Robbins [26] (see also the proof of Proposition 6.2 of [7]), we can prove that if there is a solution of u_{n} = y^{p} for n > 1 odd, then there is also such a solution with n > 1 and prime. This completes the proof of the proposition. □

To prove Theorem 1, we need some estimates from the theory of lower bounds for linear forms in logarithms of algebraic numbers.

Let α_{1} and α_{2} be algebraic numbers. Write IL = ℚ[α_{1}, α_{2}] and D for the degree of IL over ℚ. We write A_{1} and A_{2} for positive integers such that

(5)  log A_{i} ≥ max \{h(α_{i}), \frac{|log α_{i}|}{D}, \frac{1}{D} \}  (i = 1, 2).

Here, for an algebraic number α whose minimal polynomial over ℤ is of the form P (X) = a ∏_{i=1}^{d}(X − α^{(i)}), we write h(α) for its logarithmic height given by

h(α) = \frac{1}{d} (log|a| + ∑_{i=1}^{d} log (max\{1, |α^{(i)}|\})) .

In other words,

h(α) = \frac{1}{d} log M(α),

where M(α) := M(P) is the Mahler measure of the minimal polynomial of α over the rational integers.

Let b_{1} and b_{2} be positive integers and put

Λ = b_{2} log α_{2} − b_{1} log α_{1}

and

b′ = \frac{b_{1}}{D log A_{2}} + \frac{b_{2}}{D log A_{1}} .

The next result is Corollaire 2 on page 288 in [16] and gives a lower bound for log|Λ|.

Theorem 2. Assume that α_{1} and α_{2} are real, positive, and multiplicatively independent. Then

log|Λ| > −24.34 D^{4} (max \{log b′ + 0.14, \frac{21}{D}, \frac{1}{2}\})^{2} log A_{1} log A_{2}.

We point out that in the next section we do not use the Theorem 2 as given above but a sharper (and technically more involved) version of it for which we will refer the reader to [16].

In the sequel, we will use the following (equivalent) definition of h(α), due to André Weil. Let α ∈ 𝕂 where 𝕂 is a number field of degree D over the rationals. Then one defines the archimedean (normalized) valuations of 𝕂 as follows; if Σ is the set of different embeddings

σ : 𝕂 → ℂ

of 𝕂 into the field of complex numbers, then one puts

|α|_{σ} = \begin{cases}|σα|, & if σ𝕂 ⊂ ℝ, \\ |σα|^{2}, & otherwise, \end{cases}

where |·| is the usual absolute value in ℂ.

Any finite valuation of 𝕂 corresponds to a prime ideal 𝔩 of 𝕂, which is over a prime rational integer ℓ. If e and f are the index of ramification and the residual degree of 𝔩, respectively, then one puts |α|_{𝔩} = 0 is α = 0, and for α ≠ 0,

|α|_{𝔩} = ℓ^{−ford_{𝔩}(α)/e},

where ord_{𝔩}(α) is the integer ν defined by the conditions

α ∈ 𝔩^{ν}, α ∉ 𝔩^{ν+1}.

Then, the other definition of h(α) is

h(α) = \frac{1}{d} (∑_{σ} log^{+}|α|_{σ} + ∑_{𝔩} log^{+}|α|_{𝔩}) ,

where

log^{+} x = log max{1, x}, for x > 0.

4. A bound for p

The main result of this section is the following.

Proposition 4.1. Let (u_{n})_{n≥0} be the sequence appearing in Proposition 3.1. If u_{n} = y^{p}, where p > 2 is prime and n > 1 is odd, then p < 200.

We shall first give a complete argument based on Theorem 2 which shows that p ≤ 257. The proof of the above proposition is achieved in the same way by appealing to the main theorem of [16] instead of Theorem 2.

Consider the equation u_{n} = y^{p}. By Proposition 3.1, we can assume that n is odd and > 100, and also that p ≥ 41. Set m := ord_{2}(y) and put

y = 2^{m}z.

Thus, z is odd. Then the order at which 2 divides the right hand side of the above equation is mp, while the order at which 2 divides the left-hand side of the above equation is, by Lemma 2.1, equal to (n − 1)/2. Thus we have

n = 2mp + 1.

In other words, in this simple case we have proved in an elementary way that

n ≡ 1 mod p.

This corresponds to the congruence n ≡ ±1 mod p proved in [7] for the case of Fibonacci numbers (notice that both results are best possible since u_{1} = 1, u_{−1} = 1/2, whereas F_{1} = F_{−1} = 1).

With α = 1 + \sqrt{3} and β = 1 − \sqrt{3} as in Section 2, we rewrite the given equation u_{n} = y^{p} as

α^{n} − 2\sqrt{3}y^{p} = β^{n},

or

(\frac{α^{2m}}{y} )^{p} − \frac{2\sqrt{3}}{α} = \frac{1}{α} \frac{β^{n}}{y^{p}} ,

which implies that

|(\frac{α^{2m}}{y} )^{p} − \frac{2\sqrt{3}}{α}| = \frac{2\sqrt{3}}{α} \frac{|β|^{n}}{α^{n} − β^{n}} < 1.27 (2/α^{2})^{n}.

Now we put

Λ = p log(α^{2m}/y) − log(2\sqrt{3}/α).

This is a linear form in two logarithms. Forgetting our initial notation and using the notation of Theorem 2 we have

b_{1} = p, α_{1} = α^{2m}/y = (2 + \sqrt{3})^{m}/z, b_{2} = 1, α_{2} = 2\sqrt{3}/α.

We have

n = 2mp + 1,

and

1.26 < (\frac{α^{2m}}{y} )^{p} < 1.28,

hence

0 < log (\frac{α^{2m}}{y} ) < \frac{0.25}{p}.

By the definition of the Weil logarithmic height,

2 h(α^{2m}/y) = 2 h((2 + \sqrt{3})^{m}/z) = log^{+}(α^{2m}/y) + log^{+}(|β|^{2m}/y) + 2 log z,

(notice that the algebraic number 2 + \sqrt{3} is a unit so it has a trivial valuation for any finite place), so that

h(α^{2m}/y) = \frac{1}{2} log^{+}(α^{2m}/y) + log z < \frac{0.13}{p} + log z.

Concerning α_{2}, we obtain

α_{2} = \frac{2\sqrt{3}}{1 + \sqrt{3}} = \sqrt{3}(\sqrt{3} − 1) = 3 − \sqrt{3},

which shows that the minimal polynomial of α_{2} over ℤ is X^{2} − 6X + 6 and that

h(α_{2}) = \frac{1}{2} M(X^{2} − 6X + 6) = \frac{log 6}{2}.

Moreover

log α_{2} = log(3 − \sqrt{3}).

Finally, it is easy to see that, for n > 10,

|log α_{1}| ≤ \frac{1}{p} (0.01 + |log α_{2}|).

It follows that we can take here

log A_{1} = \frac{0.13}{p} + log z,

and

log A_{2} = \frac{log 6}{2}.

Thus,

b′ ≤ \frac{2p}{log 6} + \frac{1}{2 log z} .

Notice also that

\frac{α^{n−1}}{1.27} < u_{n} = 2^{(n−1)/2}z^{p} = y^{p} < \frac{α^{n−1}}{1.26} .

Since

\frac{log z}{log y} = 1 − \frac{(n − 1) log 2}{2p log y},

it follows that

1 − \frac{log 2}{2 log α} < \frac{log z}{log y} < 1 − \frac{log y − (log 1.27)/p}{2 log α log y} log 2 < 1 + \frac{0.09}{p log y} − \frac{log 2}{2 log α},

and, for p ≥ 199 we get

1 − \frac{log 2}{2 log α} < \frac{log z}{log y} < 1.001 − \frac{log 2}{2 log α},

and

0.6551 log y < log z < 0.6553 log y,

where indeed the first inequality is true for all n > 0 and all p.

By (3), Lemma 2.1 and Corollary 2.2, we get the relation

x^{2} + 2 = 3z^{2p},

where x := 2^{−(n+1)/2}v_{n} is an integer. This shows that −2 is a quadratic residue for any prime divisor q of z. Hence, q ≡ 1 or 3 mod 8.

One may also notice that

z < (α/\sqrt{2})^{2m}.

Moreover, since n is prime, for any prime divisor q of z, the period of the zeros of the recursive sequence (u_{n})_{n≥0} modulo q is equal to n. Since this period is a divisor of q ± 1, this implies

z ≥ q ≥ 2n − 1 = 4mp + 1.

It is easy to see that the two previous inequalities imply m ≥ 6 for p ≥ 209, hence

z ≥ 24p + 1 and y ≥ 2^{6} (24p + 1) for p ≥ 209.

With the above corollary of [16], we get p < 19232.

But it is much more efficient to use the main theorem of [16]. We assume

p ≥ 263, then y ≥ e^{12.9}.

In this case, we apply this theorem with the choices

L = 8, R_{1} = 1, S_{1} = 8, R_{2} = 19, S_{2} = 75,

and

m = 0.0766857, ρ = 22,

and we get a contradiction. Thus,

p ≤ 257.

In the same way, we can prove that:

• p ≤ 251 if y ≥ e^{20},

• p ≤ 211 if y ≥ e^{50},

• p ≤ 199 if y ≥ e^{90}.

To prove a better lower bound on m (for 2 < p < 1000), we proceed as follows. From the relation

u_{n} = \frac{α^{n} − β^{n}}{2\sqrt{3}} = y^{p} = 2^{mp}z^{p}

(recall that n = 2mp + 1), we get

z > (\frac{α^{2}}{2} )^{m} (\frac{α}{2\sqrt{3}})^{1/p} ,

and

z < (\frac{α^{2}}{2} )^{m} (\frac{α + (2/α^{2})^{2mp}}{2\sqrt{3}} )^{1/p} < (\frac{α^{2}}{2} )^{m} (\frac{α}{2\sqrt{3}})^{1/p} (1 + (2/α^{2})^{mp}) .

Hence,

|z − (\frac{α^{2}}{2} )^{m} (\frac{α}{2\sqrt{3}})^{1/p}| < (\frac{2}{α^{2}} )^{m(p−1)} < 10^{−50},

using only the fact that n > 100.

We have tested this inequality for 2 < p < 1000 and 1 ≤ m ≤ 100, with 10^{−50} replaced by 10^{−5} — using a real precision of 1000 decimal digits — and we found no solution (after a few seconds of computation with PARI). Thus, for p > 2 we have

m > 100,

which implies

log y > 200 (log α) − 1 > 200.

We now apply [16] with the choices

L = 8, R_{1} = 1, S_{1} = 8, R_{2} = 17, S_{2} = 992,

and

m = 0.057046, ρ = 23,

and we get

p ≤ 199.

5. Bounds for n in terms of p

Here, we follow the same strategy as in § 9 of [7].

Our objective is to obtain bounds for n (for n odd) in terms of p for the solutions of the equation

u_{n} = y^{p}.

We obtain the following result, in which C_{𝕂}(·) is as in Lemma 9.1 from [7].

Proposition 5.1. Suppose p ≥ 11 is prime. Let θ be any root of the polynomial

(6)  P (X) := ∑_{k=0}^{p} (−2)^{⌊(p−k)/2⌋} \binom{p}{k} X^{k},

and let 𝕂 = ℚ(θ). Let

Θ = 5 · 30^{p+3} p^{13/2} (p − 1)^{p+1} ((p − 1)!)^{2} (3p + 2) (1 + log(p(p − 1))) C_{𝕂}(10^{p−1}p^{p}).

If (n, y, p) satisfies the equation u_{n} = y^{p} with n odd, then n < M_{p} where M_{p} = 1.5 p Θ log Θ.

Observe that the numerical result is very similar to Proposition 9.2 from [7], the only changes being 5 instead of 3.9 in the definition of Θ and 1.5 instead of 2. in that of M_{p}. Clearly, the present upper bound for n is only slightly smaller than the one obtained in Proposition 9.2 from [7] in the case of the Fibonacci sequence.

In the sequel, we only point out the (small) changes with the proof of Proposition 9.2 from [7].

By (3), Lemma 2.1 and Corollary 2.2, a solution to u_{n} = y^{q} with n odd yields a solution in positive integers x and y to the superelliptic equation

x^{2} + 2 = 3y^{2p}.

Set ω = \sqrt{−2}. Factorizing the left-hand side of the above equation over ℤ[ω], we deduce the existence of rational integers a and b with a^{2} + 2b^{2} = y^{2} (notice that y being odd, the same holds for a; hence, b must be even). Using the relation 3 = (1 + ω)(1 − ω), we see that

(x + ω)(x − ω) = (1 + ω)(1 − ω)(a + ωb)^{p}(a − ωb)^{p}.

We thus obtain

(7)  ±2ω = (1 + ω)(a + ωb)^{p} − (1 − ω)(a − ωb)^{p}.

Dividing by 2ω, we get

\begin{aligned}±1 = & ∑_{k=0}^{⌊p/2⌋} \binom{p}{2k} a^{2k} (−2)^{(p−2k−1)/2} b^{p−2k} \\ & + ∑_{k=0}^{⌊p/2⌋} \binom{p}{2k + 1} a^{2k+1} (−2)^{(p−2k−1)/2} b^{p−2k−1}. \end{aligned}

Consequently, (a, b) is an integer solution of the Thue equation

(8)  ∑_{k=0}^{p} (−2)^{⌊(p−k)/2⌋} \binom{p}{k} X^{k} Y^{p−k} = ±1.

Remark. Our above computation works for the more general equation

x^{2} + D = Cy^{2p},

where C and D are positive rational integers, with D squarefree.

To bound the size of the solutions of (8), we follow the general scheme of [5]. Let P (X) and θ and 𝕂 be as in Proposition 5.1; we note that P (X) is the polynomial naturally associated to the Thue equation (8). We first need information on the number field 𝕂 and its Galois closure.

Lemma 5.2. The field 𝕂 = ℚ(θ) is totally real and its Galois closure 𝕃 has degree p(p − 1) over ℚ. Furthermore, for p ≥ 11, the absolute value of the discriminant of 𝕂 is bounded by 10^{p−1}p^{p}.

Proof. Observe that any root of the polynomial

Q(X) := \frac{1}{2ω} · ((1 + ω)(X + ω)^{p} − (1 − ω)(X − ω)^{p}) = X^{p}P (1/X).

satisfies |X + ω| = |X − ω|, and so must be real. Hence, 𝕂 is a totally real field. (Observe that this argument uses only the fact that ω is purely imaginary.) Furthermore, 𝕃(ω)/ℚ(ω) is a Kummer extension obtained by adjoining the p-th roots of unity and the p-th roots of (1 + ω)/(1 − ω). Hence, this extension has degree p(p − 1), and this is the same for 𝕃/ℚ.

Observe now that 𝕂(ω) is generated over ℚ(ω) by any root of either of the following two monic polynomials with coefficients in ℤ[ω]: namely, Y^{p} −(1+ω)(1− ω)^{p−1}, and Y^{p} − (1 − ω)(1 + ω)^{p−1}. Since the discriminant D_{1} (viewed as an algebraic integer in ℤ[ω] and not as an ideal) of the extension 𝕂(ω)/ℚ(ω) divides the discriminant of each of these polynomials, D_{1} divides p^{p}3^{p−1}(1 + ω)^{(p−1)(p−2)} and p^{p}3^{p−1}(1 − ω)^{(p−1)(p−2)}. As 1 + ω and 1 − ω are relatively prime, D_{1} divides 3^{p−1}p^{p}. Furthermore, estimating the discriminant of 𝕂(ω)/ℚ in two different ways thanks to Lemma 9.7 from [7] gives

(9)  |D_{𝕂(ω)}| = 8^{p}D_{1}^{2} = |D_{𝕂}|^{2} · |N_{𝕂/ℚ}(D_{𝕂(ω)/𝕂})|.

Consequently, |D_{𝕂}| divides 3^{p−1}(2\sqrt{2}p)^{p}, therefore |D_{𝕂}| is less than 10^{p−1}p^{p}, since p ≥ 11. □

The above lemma provides the same upper bound for the discriminant of the associated number field as in the Fibonacci case. We now keep the notation from Proposition 9.2 of [7]. We have to estimate the modified height of the quotient (α_{2} −α_{1})/(α_{3} −α_{1}), where α_{1}, α_{2} and α_{3} are roots of P (X). We proceed as follows. Let M(P) denote the Mahler measure of P (X) and ∥P ∥_{2} denotes its quadratic norm, that is, if P (X) = ∑_{k≥0} a_{k}X^{k}, then ∥P ∥_{2} = (∑|a_{k}|^{2})^{1/2}. It is then well-known that

M(P) ≤ ∥P ∥_{2},

(this is just Landau’s inequality from [14]; see also [21]). In the present case, we have

∥P ∥_{2}^{2} < ∑_{k=0}^{p} 2^{p−k}\binom{p}{k}^{2} ≤ ∑_{k=0}^{p} 2^{2p−k}\binom{p}{k} = 6^{p},

whence

M(P) < 6^{p/2} and h(θ) ≤ \frac{log M(P)}{p} < \frac{1}{2} log 6.

Hence, with the modified height h′ related to the field 𝕃 defined in Lemma 5.2, we have

h′(\frac{α_{2} − α_{1}}{α_{3} − α_{1}} ) ≤ 5 p(p − 1).

This explains the constant 5 instead of 3.9 in the definition of Θ.

Finally, we observe that if u_{n} is a p-th power for some odd n, then there are integers X and Y such that (X, Y) is a solution of the Thue equation (8) and u_{n}^{2/p} = 2^{(n−1)/p}(X^{2} + 2Y^{2}). Since |X| ≤ 1 + 3^{p}|Y | and u_{n} ≥ 2.5^{n} (for n ≥ 100), we derive, exactly as in [7], that n < 1.1 p log|Y |. It then follows that (very roughly!)

n < 1.5 p Θ log Θ,

with

Θ = 5 · 30^{p+3} p^{13/2} (p − 1)^{p+1} (3p + 2) ((p − 1)!)^{2} (1 + log(p(p − 1))) C_{𝕂}(10^{p−1}p^{p}).

This proves Proposition 5.1.

6. Level-lowering

Recall our earlier notation α = 1 + \sqrt{3}, β = 1 − \sqrt{3}. It is convenient to define

U_{k} = \frac{α^{2k+1} − β^{2k+1}}{2^{k+1} \sqrt{3}} ,  V_{k} = \frac{α^{2k+1} + β^{2k+1}}{2^{k+1}} ,  (k ≥ 0).

Note that if n = 2k + 1 then u_{n} = 2^{k}U_{k}. If u_{n} = y^{p} with n = 2k + 1 odd, then we have shown that p | k. So, we also know that

(10)  U_{k} = y′^{p},

and therefore that

(11)  V_{k}^{2} + 2 = 3y′^{2p}.

Our task is to prove that k = 0, which we do in this and the next section using the modular approach and the information obtained thus far by classical methods. In particular we assume that 41 ≤ p ≤ 199. Our first step is to associate a putative solution to equation (10) to the Frey curve

E_{k} : Y^{2} = X^{3} + 2V_{k}X^{2} − 2X.

In this, we follow the recipe given by the paper of Bennet and Skinner [3]. From the result of Sections 2, 3 of that paper we deduce the following Lemma.

Lemma 6.1. Let E^{1}, …, E^{8} be the elliptic curve 384A1, 384B1, …, 384H1 (in Cremona’s tables [10]). Suppose (k, y, p) is a solution to equation (10). With notation as above, the Galois representation on the p-torsion of E_{k} is isomorphic to the Galois representation on the p-torsion of one of the elliptic curve E^{1}, …, E^{8}, in which case, for any prime l ≠ 2, 3,

(i) a_{l}(E_{k}) ≡ a_{l}(E^{i}) (mod p) if l ∤ y.

(ii) l + 1 ≡ ±a_{l}(E^{i}) (mod p) if l | y.

Proof. The results of [3] show that the Galois representation on the p-torsion of E_{k} arises from a newform of weight 2 and level 384. Using the computer algebra system MAGMA we compute the newforms at level 384 and find that these are all rational and correspond to the elliptic curves 384A1, 384B1, …, 384H1 in Cremona’s tables [10]. □

Our first task is to eliminate all of E^{1}, …, E^{8} except for one.

Lemma 6.2. Suppose l ≠ 2, 3 is a prime. The residue class of V_{k} modulo l depends only on the residue class of k modulo K_{l}, where

(12)  K_{l} = \begin{cases}l − 1 & if l ≡ ±1 (mod 12), \\ l + 1 & otherwise. \end{cases}

Proof. The condition l ≡ ±1 (mod 12) is equivalent to the condition that 3 is a quadratic residue modulo l. If 3 is a quadratic residue modulo l, then the Lemma follows from Fermat’s Little Theorem. Thus, suppose that 3 is a quadratic nonresidue modulo l, and write K_{l} = l + 1. It is sufficient to show that

\frac{α^{2K_{l}}}{2^{K_{l}}} ≡ 1 (mod l), \frac{β^{2K_{l}}}{2^{K_{l}}} ≡ 1 (mod l).

Now the Frobenius automorphism generates the Galois group of the algebraic closure of 𝔽_{l}, and so α^{l} ≡ β (mod l). Hence, since K_{l} = l + 1, we see that

\frac{α^{2K_{l}}}{2^{K_{l}}} ≡ \frac{α^{2}β^{2}}{2^{2}} ≡ 1 (mod l),

and similarly for β instead of α. □

6.1. Eliminating Newforms. Lemma 6.1 relates the Galois representation of E_{k} to too many Galois representations. We now eliminate all but one of them.

Fix a prime 41 ≤ p ≤ 199. Suppose l ≠ 2, 3 is a prime. Let K_{l} be given by (12). Recall that (Lemma 6.2) the residue class of V_{k} modulo l, and hence the Frey curve E_{k} modulo l, depends only on the residue class of k modulo K_{l}. We see that the following definitions make sense: let N_{p}(l, E^{i}) to be the subset of κ ∈ ℤ/K_{l} such that

• either V_{κ}^{2} + 2 ≢ 0 (mod l), and a_{l}(E_{κ}) ≡ a_{l}(E^{i}) (mod p),
• or V_{κ}^{2} + 2 ≡ 0 (mod l) and l + 1 ≡ ±a_{l}(E^{i}) (mod p).

Lemma 6.3. Suppose (k, y, p) is a solution to equation (10), where 41 ≤ p ≤ 199 is prime. Suppose that the Galois representation on the p-torsion of E_{k} is isomorphic to the corresponding representation for E^{i}. If l ≠ 2, 3 is a prime then the reduction of k modulo K_{l} belongs to N_{p}(l, E^{i}).

Proof. The Lemma follows from Lemma 6.1. □

Given two positive integers K_{1}, K_{2}, and two sets N_{1} ⊂ ℤ/K_{1} and N_{2} ⊂ ℤ/K_{2} we loosely define their ‘intersection’ N_{1} ∩ N_{2} to be the set of all elements of ℤ/lcm(K_{1}, K_{2}) whose reduction modulo K_{1} and K_{2} is respectively in N_{1} and N_{2}.

Lemma 6.4. Suppose (k, y, p) is a solution to equation (10), where 41 ≤ p ≤ 199 is prime. Let

(13)  E : Y^{2} = X^{3} − X^{2} − 3X + 3.

(This is the elliptic curve 384D1 in the notation of [10].) Then the Galois representation on the p-torsion of E_{k} is isomorphic to the Galois representation on the p-torsion of E.

Proof. Suppose otherwise. We then know that the Galois representation on the p-torsion of E_{k} is isomorphic to the Galois representation on E^{i} for some i ≠ 4 (note that E^{4} is 384D1). Now fix a prime 41 ≤ p ≤ 199 and fix i ≠ 4 and we explain how to derive a contradiction.

Recall that k ≡ 0 (mod p). In other words, the reduction of k modulo p belongs to the set

N′ = \{\overline{0} ∈ ℤ/p\} .

Moreover, for any prime l ≠ 2, 3, we know that the reduction of k modulo K_{l} belongs to N_{p}(l, E^{i}). To derive a contradiction, it is sufficient to produce a set S of primes l ≠ 2, 3, such that

N′ ∩ ⋂_{l∈S} N_{p}(l, E^{i}) = ∅.

We used a short pari/gp script which for each i ≠ 4 and for each prime 41 ≤ p ≤ 199 produces such set S. For example, to eliminate E^{1}, p = 41, our program found it sufficient to take

S = {5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 53, 83, 163} .

The computational part of the proof took just a few minutes. □

7. The Modular Sieve

In this section, we complete the proof that the only positive perfect powers in the sequence u_{n} are u_{1} and u_{4}. We continue with the notation of the previous section. We have shown that if u_{n} = y^{p} then n = 2k + 1 is odd and that 41 ≤ p ≤ 199. Recall that our solution to u_{n} = y^{p} with n = 2k + 1 gives a solution (k, y′, p) to equation (10). Our task is to show that k = 0. Furthermore, Proposition 5.1 gives a bound for the index n in terms of the exponent p, say n ≤ M_{p}.

We continue to denote by E the elliptic curve 384D1 given by (13).

Lemma 7.1. Let 41 ≤ p ≤ 199 be prime. Let M_{p} be as given by Proposition 5.1. Suppose that S is a set of primes l ≠ 2, 3, and write

K_{S} = lcm_{l∈S}K_{l}, N_{p}(S, E) = ⋂_{l∈S} N_{p}(l, E) ⊂ ℤ/K_{S}.

Suppose that the following conditions are satisfied.

• N_{p}(S, E) = \{\overline{0} ∈ ℤ/K_{S}\}.

• K_{S} > M_{p}.

Then the only solution to the equation u_{n} = y^{p} is n = 1.

Proof. Since n = 2k + 1 we need to prove that k = 0. It follows from Lemmas 6.3, 6.4 that the reduction of k modulo K_{S} belongs to N_{p}(S, E). If the conditions are satisfied, then K_{S} divides k and since 0 ≤ k < n ≤ M_{p} the Lemma follows. □

7.1. Completion of the the Proof of Theorem 1. Fix the prime exponent 41 ≤ p ≤ 199. All we need to do is to find a set S satisfying the conditions of Lemma 7.1. For this, we wrote a pari/gp program, and we now describe the strategy of our program taking p = 41 for concreteness. Here, Proposition 5.1 shows that

k < n ≤ M_{41} ≈ 5.5 × 10^{321}.

Let

K = 6983776800 = 2^{5} × 3^{3} × 5^{2} × 7 × 11 × ⋯ × 19.

We start with S = {5}. We go through the set of primes l ≥ 5 in order, and we pickout those that that satisfy K_{l} | K. If such a prime is found then we append it to S and compute N_{p}(S, E). The reader will no doubt expect that since most of our K_{l} are highly composite and have lots of common factors, the set N_{p}(S, E) will be a small set of congruences modulo a large modulus. After a few seconds we found that K_{S} = K and N_{p}(S, E) = \{\overline{0} ∈ ℤ/K\}, where S is the set of the first 48 primes l ≠ 2, 3, satisfying K_{l} | K. Finding such a set of primes S proves that K divides k.

We now let K′ = K. We look for primes l such that 23 | K_{l} and K_{l} | K′. We append them to our set S and continue in computing N_{p}(S, E) until we have shown that K′ | k, etc.

The entire computation for p = 41 took just over a minute; at the end S had 353 elements and satisfied the conditions of Lemma 7.1 with

K_{S} = 2^{5} × 3^{3} × 5^{2} × 7 × 11 × ⋯ × 769 ≈ 6.96 × 10^{323}.

The entire computation for 41 ≤ p ≤ 199 took about 9 hours on a 2.2 Mhz Intel Pentium.

There is an important optimization, worth mentioning, that was missed in [7]. Suppose we want to compute N_{p}(S, E)∩N_{p}(l, E), where we have already determined N_{p}(S, E). Suppose also that, in some previous step, we have shown that L | k for some integer L (here L will be some divisor of K_{S}). To compute N_{p}(S, E)∩N_{p}(l, E), we need not determine N_{p}(l, E). We merely have to decide which elements κ ∈ ℤ/K_{l} satisfying κ ≡ 0 (mod lcm(L, K_{l})) belong to N_{p}(l, E).

8. Discussion

In the sequel, we denote by (α, β) a given Lucas pair of complex numbers.

First, we consider the case when α and β are real. Without any loss of generality, we assume that we have |α| > |β|. Furthermore, since

\frac{α^{n} − β^{n}}{α − β} = ±\frac{(−α)^{n} − (−β)^{n}}{(−α) − (−β)} ,

we may further assume that β is positive. We consider the equation

(14)  u_{n} := \frac{α^{n} − β^{n}}{α − β} = y^{p},

in integers n, y, p with p prime. We observe that (n, y, p) = (1, 1, p) is a solution of (14) for any p. Furthermore, if αβ = ±1, then either (−1, 1, p), or (−1, −1, p) is also a solution. The existence of solutions for any p makes the complete resolution of (14) very difficult, since one can no longer hope to solve it by only using congruences to suitable moduli.

We now restrict our attention to solutions (n, y, p) of (14) with |y| ≥ 2. Our first aim is to obtain a good upper bound for p. The existence of such an effective bound is due to Pethő [23] and, independently, to Shorey and Stewart [28].

Without any further assumption, we derive that

0 ≠ |(α − β)y^{p}α^{−n} − 1| = |α/β|^{−n}.

Using estimates for linear forms in three logarithms, we then get an upper bound for p, depending (of course!) on α and β.

However, we can do better in three situations, for which linear forms in two logarithms can be applied.

A first one is (trivially) when α and β differ by 1. In this case, both are integers, and, setting x := α = β + 1, our equation can be rewritten as

x^{n} − (x − 1)^{n} = y^{p}.

Then, an immediate application of estimates for linear forms in two logarithms yields a sharp upper bound for p.

A second one is when β = 1. In this case, α is an integer and, setting x := α, our equation reduces to the Nagell–Ljunggren equation

(15)  \frac{x^{n} − 1}{x − 1} = y^{p},

for which the following alternative approach has been developed (see [4] and the survey [6]). Rewrite (15) under the form

x^{n} = (x − 1)y^{p} + 1,

We then take a prime divisor ℓ of x, and use estimates for linear forms in two ℓ-adic logarithms to get an upper bound for the ℓ-adic valuation ord_{ℓ}(x^{n}) of (x − 1)y^{p} + 1. Basically, this yields the estimate ord_{ℓ}(x^{n}) ≪ (log y)(log p). On the other hand, we have trivially

ord_{ℓ}(x^{n}) ≥ n ≫ p log y,

where, here and above, the numerical constant implied in ≪ depends only on ℓ. Hence, we get an upper bound for p, which is considerably better that what can be obtained using linear forms in three Archimedean logarithms.

A third one is described in the present Note. It is applicable, under some further assumption, when α + β and αβ are not coprime.

Let a ≥ 1, b and t ≥ 2 be integers such that t divides no power of b and a^{2}t^{2} + 4bt is positive and not a perfect square. Consider the sequence defined by u_{0} = 0, u_{1} = 1 and

u_{n+2} = atu_{n+1} + btu_{n}.

An easy induction shows that, for any positive integer m, the integers u_{2m} and u_{2m+1} are divisible by t^{m} and that u_{2m+1} is congruent to b^{m}t^{m} modulo t^{m+1}. Consequently, when we consider the equation u_{n} = y^{p} with n odd, denoting by ℓ the greatest integer for which t^{ℓ} divides y, we get that (n − 1)/2 = ℓp; hence, that n is congruent to 1 modulo p. We then get an upper bound for p by using linear forms in two logarithms, exactly as in Theorem 1.

As we have seen in Sections 2 and 3, the case of even index yields further difficulties and requires a more precise analysis.

If one does not manage to get rid of linear forms in three logarithms, then the strategy is essentially the same as developed for the Fibonacci sequence. We try to use a sieve to prove that any solution to our equation u_{n} = y^{p} must satisfy n ≡ ±1 (mod p). Then, with ν such that n = νp ± 1, we see that

|(α − β)y^{p}(α^{−ν})^{p}α^{±1} − 1| = |(α^{±1}(α − β)) × (α^{−ν}y)^{p} − 1| = |α/β|^{−n},

where the use of linear forms in two logarithms gives a very good upper bound for p.

Consequently, we can now assume that we have a reasonable upper bound for p. Obviously, it depends on the data, but, when α + β and αβ are not too large, we get that p is less than a few hundreds. However, much work is still needed to achieve the resolution of the equation.

We continue the discussion by considering first, specifically, the case when β = 1, that is, equation (15).

A remarkable result of Bennett [1] asserts that for any given positive integers a, b and m, with a > b and m ≥ 3, the Diophantine equation

|aX^{m} − bY^{m}| = 1

has at most one solution in positive integers X and Y. This implies immediately that the Nagell–Ljunggren equation (15) has no solution (n, y, p) with y ≥ 2 and n ≡ 1 (mod p). For a fixed value of p, using an elementary sieve, it is then possible to prove that this equation has also no solution with n ≢ 1 (mod p) (see [6]). Note that (15) has been solved for any value of x between −10^{4} and 10^{6}.

We return to the quadratic case. We introduce the companion sequence of (u_{n})_{n≥0}, namely the sequence (v_{n})_{n≥0} defined by

v_{n} = α^{n} + β^{n}, (n ≥ 0).

We observe that both sequences are related, for every n ≥ 0, by

(α − β)^{2}u_{n}^{2} = v_{n}^{2} − 4(αβ)^{n}.

Assume first that α is a unit, that is, that αβ = ±1. With our assumptions on α and β, we see that α and β are roots of a polynomial

X^{2} − tX + ε,

for some ε = ±1 and a positive integer t with t ≥ 3 if ε = 1. Then, assuming that u_{n} is a p-th power and that ε = −1, we get the hyperelliptic equation

(16)  X^{2} ± 4 = (t^{2} + 4) Y^{2p}.

We then proceed as in [7] to derive a Thue equation, from which we get an upper bound for X and Y; hence, for n. We mention that to any solution to (16) it corresponds a solution to the equation

(t + 2i)W^{p} − (t − 2i)Z^{p} = ±4i,

to be solved in Gaussian integers W and Z. It has the trivial solutions (W, Z) = (1, 1) and (−1, −1). It would be very nice to have an extension of Bennett’s above result to the Gaussian field!

If ε = 1, we then get the hyperelliptic equation

X^{2} ± 4 = (t^{2} − 4) Y^{2p} = (t + 2)(t − 2) Y^{2p}.

If α is not a unit, then the situation is not very clear, and we see no general method unless (αβ)^{n} divides u_{n}^{2} and v_{n}^{2}.

To conclude, we briefly discuss the case when α and β are complex conjugates. Thus, we consider the binary recurrence

u_{0} = 0,  u_{1} = 1,  u_{n+2} = au_{n+1} + bu_{n},

with (a, b) ≠ (1, −1) (otherwise, α and β would be roots of unity) and a^{2} + 4b < 0.

We can no longer use estimates for linear forms in complex logarithms in order to bound the exponent p.

Assume that there is a prime ℓ such that ℓ divides b but does not divide a. Then, there is an ideal 𝔩 in ℚ(β) such that v_{𝔩}(β) > 0 and v_{𝔩}(α) = 0. Writing then

−(β/α)^{n} = (α − β)α^{−n}y^{p} − 1,

we derive from known estimates for linear forms in three non-Archimedean logarithms (see e.g. [32]) an upper bound for p in terms of a and b.

We may then try to prove that n must be congruent to 1 modulo p in order to be able to apply estimates for linear forms in only two logarithms. However, there may be some additional difficulties. Consider for instance the recurrence given by (a, b) = (1, −2). An easy calculation shows that, starting with u_{0}, we have the values

0, 1, 1, −1, −3, −1, 5, 7, −3, …

Consequently, u_{2}, u_{3} and u_{5} are perfect p-th powers for any odd prime number p.

9. Related equations and open problems

The equations considered in the present paper are a particular class of the exponential Diophantine equation

u_{n} = y^{q}, in n, y, q ≥ 2 integers with |y| ≥ 2,

where (u_{n})_{n≥0} is a given non-degenerated linear recurrent sequence of integers.

It is a well-known fact that, if the characteristic polynomial of the recurrence has only simple roots and has a dominant root, then the theory of linear forms in logarithms yields an effective upper bound for the exponent q (see, e.g. [25]). Under the same assumption, Pethő [25] applied results from Corvaja and Zannier [9] to get that the above equation has finitely many solutions for any fixed q ≥ 2. Since the proof ultimately depend on the Schmidt Subspace Theorem, we have no algorithm to compute the set of perfect powers in (u_{n}).

Take for instance the Tribonacci sequence defined by the initial terms T_{0} = T_{1} = 0, T_{2} = 1 and by the recursion T_{n+3} = T_{n+2} + T_{n+1} + T_{n}, for any n ≥ 0. Since the above assumptions are clearly satisfied, we get that only finitely many Tribonacci numbers are perfect powers. However, we still do not know whether the only Tribonacci squares are T_{0} = T_{1} = 0, T_{2} = T_{3} = 1, T_{5} = 4, T_{10} = 81, T_{16} = 3136 = 56^{2} and T_{18} = 10609 = 103^{2}.

Let define the integers T_{−n} for n ≥ 1 in such a way that the recursion formula holds for any integer. It is still an open question to decide whether there are only finitely perfect powers among the integers T_{−n}, n ≥ 1.

References

[1] M. A. Bennett, Rational approximation to algebraic number of small height: The Diophantine equation | ax^{n} − by^{n} |= 1, J. reine angew. Math. 535 (2001), 1–49.

[2] M. A. Bennett, Personal communication.

[3] M. A. Bennett and C. M. Skinner, Ternary Diophantine equations via Galois representations and modular forms, Canad. J. Math. 56 (2004), no. 1, 23–54.

[4] Y. Bugeaud, Linear forms in p-adic logarithms and the Diophantine equation (x^{n} −1)/(x− 1) = y^{p}, Math. Proc. Cambridge Phil. Soc. 127 (1999), 373–381.

[5] Y. Bugeaud and K. Győry, Bounds for the solutions of Thue-Mahler equations and norm form equations, Acta. Arith. 74 (1996), 273–292.

[6] Y. Bugeaud and M. Mignotte, L’équation de Nagell–Ljunggren (x^{n} − 1)/(x − 1) = y^{p}, Enseign. Math. 48 (2002), 147–168.

[7] Y. Bugeaud, M. Mignotte and S. Siksek, Classical and modular approaches to exponential Diophantine equations I. Fibonacci and Lucas powers, Annals of Math., to appear.

[8] Y. Bugeaud, M. Mignotte and S. Siksek, Classical and modular approaches to exponential Diophantine equations II. The Lebesque-Nagell equation, Compositio Math., to appear.

[9] P. Corvaja and U. Zannier, Some new applications of the subspace theorem, Compositio Math. 131 (2002), 319–340.

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

[11] H. Darmon and L. Merel, Winding quotients and some variants of Fermat’s Last Theorem J. reine angew. Math. 490 (1997), 81–100.

[12] G. Hanrot, Solving Thue equations without the full unit group Math. of Comp. 69, no. 229, (1997), 3951–405.

[13] G. Hardy, J.E. Littlewood, and G. Polya, Inequalities, Cambridge University Press, Cambridge, 1934.

[14] E. Landau, Sur quelques théorèmes de M. Petkovic̀ relatifs aux zéros des fonctions analytiques, Bull. Soc. Math. France 33 (1905), 251–261.

[15] E. Landau, Verallgemeinerung eines Pólyaschen Satzes auf algebraische Zahlkörper, Nachr. Kgl. Ges. Wiss. Göttingen, Math.-Phys. Kl. (1918), 478–488.

[16] M. Laurent, M. Mignotte and Y. Nesterenko, ‘Formes linéaires en deux logarithmes et déterminants d’interpolation,’ J. Number Theory 55 (1995), 285–321.

[17] H. W. Lenstra, Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc. 26 (1992), 211-244.

[18] W. Ljunggren, Über die Gleichung x^{2} = Dy^{4} + 1, Archiv. Math. Naturv. 45 (1942), Nr. 5.

[19] E. M. Matveev, An explicit lower bound for a homogeneous rational linear form in logarithms of algebraic numbers. II, Izv. Ross. Akad. Nauk Ser. Mat. 64 (2000), 125–180. English transl. in Izv. Math. 64 (2000), 1217–1269.

[20] M. Mignotte, Entiers algébriques dont les conjugués sont proches du cercle unité, Séminaire Delange–Pisot–Poitou, 19e année: 1977/78, Théorie des nombres, Fasc. 2, Exp. No. 39, 6 pp., Secrétariat Math., Paris, 1978.

[21] M. Mignotte, Mathematics for Computer Algebra, Springer-Verlag, New York, 1992.

[22] W. Narkiewicz, Elementary and Analytic Theory of Algebraic Numbers, Springer-Verlag, Berlin, 1990.

[23] A. Pethő, Perfect powers in second order linear recurrences, J. Number Theory 15 (1982), no. 1, 5–13.

[24] A. Pethő, Full cubes in the Fibonacci sequence, Publ. Math. Debrecen 30 (1983), no. 1, 117–127.

[25] A. Pethő, Diophantine properties of linear recursive sequences II, Acta Math. Paedagogicae Nyíregyháziensis 17 (2001), 81–96.

[26] N. Robbins, On Fibonacci numbers which are powers. II. Fibonacci Quart. 21 (1983), no. 3, 215–218.

[27] A. Schinzel, On the product of the conjugates outside of the unit circle of an algebraic number, Acta Arith. 24 (1973), 385–399; Addendum 26 (1975), 329–331.

[28] T. N. Shorey and C. L. Stewart, On the Diophantine equation ax^{2t} + bx^{t}y + cy^{2} = d and pure powers in second order linear recurrences, Math. Scand. 52 (1983), 24–36.

[29] T. N. Shorey and R. Tijdeman, Exponential Diophantine equations, Cambridge Tracts in Mathematics 87, Cambridge University Press, Cambridge, 1986.

[30] C. L. Siegel, Abschätzung von Einheiten, Nachr. Akad. Wiss. Göttingen II, Math.-Phys. Kl., Nr. 9, (1969), 71–86.

[31] P. M. Voutier, An effective lower bound for the height of algebraic numbers, Acta Arith. 74 (1996), 81–95.

[32] Yu Kunrui, p-adic logarithmic forms and group varieties. II., Acta Arith. 89 (1999), 337– 378.

Yann Bugeaud, Université Louis Pasteur, U. F. R. de mathématiques, 7, rue René Descartes, 67084 Strasbourg Cedex, France

E-mail address: bugeaud@math.u-strasbg.fr

Florian Luca, Instituto de Matemáticas, Universidad Nacional Autónoma de México, C.P. 58089, Morelia, Michoacán, México

E-mail address: fluca@matmor.unam.mx

Maurice Mignotte, Université Louis Pasteur, U. F. R. de mathématiques, 7, rue René Descartes, 67084 Strasbourg Cedex, France

E-mail address: mignotte@math.u-strasbg.fr

Samir Siksek, Mathematics Institute, University of Warwick, Coventry, CV4 7AL, United Kingdom

E-mail address: siksek@maths.warwick.ac.uk