PERFECT POWERS IN LINEAR RECURRING SEQUENCES^{∗}

CLEMENS FUCHS AND ROBERT F. TICHY

Abstract. P. Corvaja and U. Zannier [4] showed for linear recurring sequences defined by G_{n} = a_{1}α_{1}^{n} + … + a_{t}α_{t}^{n} (t ≥ 2) with non-zero rational numbers a_{i} and integral characteristic roots α_{1} > … > α_{t} > 0 (α_{1}, α_{2} coprime) that the equation G_{n} = x^{q} (for q ≥ 2) has only finitely many solutions (n, x) ∈ ℕ^{2}. In this paper we want to use a quantitative version of W. M. Schmidt’s Subspace Theorem (due to J.- H. Evertse [5]) to calculate an upper bound for the number of solutions (n, x). Combining this with an earlier result of I. Nemes and A. Pethő [11] we establish also an upper bound for the number of solutions (n, x, q).

1. Introduction

Let A_{1}, A_{2}, …, A_{k} and G_{0}, G_{1}, …, G_{k−1} be algebraic numbers over the rationals and let (G_{n}) be a k-th order linear recurring sequence given by

G_{n} = A_{1}G_{n−1} + ⋯ + A_{k}G_{n−k} for n = k, k + 1, …. (1)

Let α_{1}, α_{2}, …, α_{t} be the distinct roots of the corresponding characteristic polynomial

X^{k} − A_{1}X^{k−1} − ⋯ − A_{k}. (2)

Then for n ≥ 0

G_{n} = P_{1}(n)α_{1}^{n} + P_{2}(n)α_{2}^{n} + ⋯ + P_{t}(n)α_{t}^{n},

where P_{i}(n) is a polynomial with degree less than the multiplicity of α_{i}; the coefficients of P_{i}(n) are elements of the field: ℚ(G_{0}, …, G_{k−1}, A_{1}, …, A_{k}, α_{1}, …, α_{t}).

The recurring sequence is called simple, if all characteristic roots are simple. (G_{n}) is called nondegenerate, if no quotient α_{i}/α_{j} for all 1 ≤ i < j ≤ t is equal to a root of unity and degenerate otherwise. Observe that, even if (G_{n}) is degenerate, there exists a positive integer d such that, (G_{r+md}) is nondegenerate on each of the d arithmetic progressions with 0 ≤ r < d. Therefore, restricting to nondegenerate recurring sequences causes no substantial loss of generality.

Date: December 4, 2001.

∗This work was supported by the Austrian Science Foundation FWF, grant S8307-MAT.

2000 Mathematics Subject Classification: 11D45.

In the present paper we deal with the Diophantine equation

G_{n} = Ex^{q}, E ∈ ℤ\{0} (3)

which was earlier investigated by several authors (e.g. cf. [21]).

For the Fibonacci sequence (F_{n}), Cohn [2] and Wyler [28], independently, proved that F_{n} is a square only if n = 0, 1, 2 and 13. Cohn [3] and Steiner [24] solved the equations F_{n} = 2x^{2} and F_{n} = 3x^{2}. They also proved the corresponding results for the Lucas sequence (L_{n}). London and Finkelstein [10] determined all cubes in the Fibonacci sequence; Lagarias and Weisser [9] gave another proof. Steiner [23] derived some partial results for higher powers. The proofs of these results do not depend on estimates for linear forms in logarithms. Pethő [14], [15] used the theory of linear forms in logarithms and computer calculations to determine all the cubes and fifth powers in the Fibonacci sequence.

For a nondegenerate recurring sequence (G_{n}) of order 2 induced by a (rational) integral recurrence, it has been proved, independently, by Pethő [13] and Shorey and Stewart [19] that for the solutions x ∈ ℤ, |x| > 1 and q ≥ 2 of (3) max(|x|, q, n) is bounded by an effectively computable constant depending only on E and the sequence (G_{n}). In fact, Pethő proved that max(|x|, q, n) is bounded by an effectively computable number depending only on the greatest prime divisor of E and on the coefficients and initial values of (G_{n}) (provided that the coefficients are coprime integers). Pethő extended this result to the equation G_{n} = bx^{q} with b ∈ S, where S is a set of integers composed solely of a finite number of primes.

Shorey and Stewart [19] proved the above finiteness result for certain recurring sequences of order > 2. Let (G_{n}) be a nondegenerate linear recurring sequence given by

G_{n} = λ_{1}α_{1}^{n} + P_{2}(n)α_{2}^{n} + ⋯ + P_{t}(n)α_{t}^{n}, (4)

where λ_{1} is a non-zero constant, |α_{1}| > |α_{j}| for j = 2, …, t, and G_{n}−λ_{1}α_{1}^{n} ≠ 0. Then assuming x, q > 1 the solutions q of (3) can be bounded by an effectively computable constant which depends on the coefficients and initial values of the recurrence. Kiss [8] proved that, in fact, q is less than a number which is effectively computable in terms of the greatest prime divisor of E and the coefficients and the initial values of the sequence (G_{n}).

Shorey and Stewart [20] considered recurring sequences (G_{n}) satisfying (4). Assuming that P_{2}(n) is a non-zero constant, t = 3 and |α_{1}| = |α_{2}| = |α_{3}| they showed, that (3) has only finitely many integral solutions E, x, q and n with the greatest prime divisor of E bounded by a given positive integer P, and |x| > 1, q > 2 and n ≥ 0.

Finkelstein [6], Williams [27] and Steiner [24] proved that 1, 2 and 5 are the only Fibonacci numbers of the form x^{2} + 1. Finkelstein [7] established a similar result for Lucas numbers. Stewart [25] and Shorey and Stewart [20] investigated the equation

G_{n} = x^{q} + c, (5)

where c ∈ ℤ and (G_{n}) is a simple, nondegenerate second order recurring sequence of rational integers. Assuming |A_{2}| = 1, they showed for the integral solutions of (5) that the maximum of n ≥ 0, |x| > 1 and q ≥ 3 is less than an effectively computable constant depending on c, the coefficients and the initial values of the recurrence. In the case q = 2 they obtained a similar result under additional technical conditions. Furthermore, Shorey and Stewart [20] proved, that if α and β are multiplicatively independent with one root inside the unit circle, then (5) has only finitely many solutions in integers n, x and q with n ≥ 0, |x| > 1 and q > 2.

Nemes and Pethő [11], [12] studied the more general equation

G_{n} = Ex^{q} + T (x), (6)

where T (x) is a polynomial of degree r and of height H with integral coefficients. For fixed E ∈ ℤ and T they established bounds for the integral solutions n, q, x with |x|, q > 1. Let (G_{n}) be defined as in (4) and assume

|α_{1}| > |α_{2}| > |α_{j}|, for j = 3, …, t, (7)

with α_{2} ≠ ±1. Nemes and Pethő showed that q < C_{1} provided that n > C_{2} and r < C_{3}q, where C_{1}, C_{2} and C_{3} are suitable positive numbers which are effectively computable in terms of E, H and the coefficients and initial values of the recurrence. Nemes and Pethő were also able to show that if q is a fixed integer larger than one and (6) has infinitely many integral solutions n and x, then T (x) can be characterized in terms of the Chebyshev polynomials. Kiss [8] and Shorey and Stewart [20] dealt with equation (6) for nondegenerate linear recurring sequences (G_{n}) of arbitrary order, under condition (7) and the additional assumptions that E = 1 and d is the degree of α_{1} over ℚ, α_{1} and α_{2} are multiplicatively independent and α_{2} ≠ ±1. Then they showed that there are only finitely many integers n, x and q with n ≥ 0, |x| > 1 and

q > max (\frac{d log |α_{1}|}{log(|α_{1}|/ max(1, |α_{2}|))}, d + r)

for which (6) holds.

Recently Corvaja and Zannier [4] considered linear recurrences defined by

G_{n} = a_{1}α_{1}^{n} + a_{2}α_{2}^{n} + ⋯ + a_{t}α_{t}^{n},

where t ≥ 2, a_{1}, a_{2}, …, a_{t} are non-zero rational numbers, α_{1} > α_{2} > ⋯ > α_{t} > 0 are integers. They used Schmidt’s Subspace Theorem [16], [17] to show that for every integer q ≥ 2 the equation

G_{n} = x^{q} (8)

has only finitely many solutions (n, x) ∈ ℕ^{2} assuming that G_{n} is not identically a perfect qth power for any n in a suitable arithmetic progression.

2. Results

Our first main result gives a quantitative version of the above result of Corvaja and Zannier [4].

Theorem 1. Let (G_{n}) be a linear recurring sequence defined by

G_{n} = a_{1}α_{1}^{n} + a_{2}α_{2}^{n} + ⋯ + a_{t}α_{t}^{n}, (9)

where t ≥ 2, a_{1}, a_{2}, …, a_{t} are non-zero rational numbers, α_{1} > α_{2} > ⋯ > α_{t} > 0 are integers and such that for given q ≥ 2 there is no r ∈ {0, …, q − 1} with G_{mq+r} a perfect qth power for all m ∈ ℕ. Then the number of solutions (n, x) ∈ ℕ^{2} of the equation

G_{n} = x^{q}

is finite and can be bounded above by an explicitly computable number depending on q, a_{1}, a_{2}, …, a_{t}, α_{1}, …, α_{t}.

Remark 1. Corvaja and Zannier [4] showed that (9) is the qth power of an integer for infinitely many n ∈ ℕ, if and only if there exist integers r ∈ {0, …, q − 1}, b ≥ 1 and

H_{n} = c_{1}β_{1}^{n} + … + c_{s}β_{s}^{n},

where c_{1}, …, c_{s} are non-zero rational numbers and β_{1} > … > β_{s} > 0 are integers as above, such that

G_{n} = b^{n−r}H_{n}^{q}.

In particular, at least one of the functions m ↦ G_{mq+r}, (r = 0, …, q − 1) is a qth power in the ring of complex functions (with pointwise multiplication) of the form (9), or G_{n} is a perfect qth power for any n in a suitable arithmetic progression.

Remark 2. Observe that one can effectively determine whether G_{mq+r} is a perfect qth power or not (see again [4]). A sufficient condition is that α_{1}, α_{2} are coprime.

Remark 3. The example

G_{n} = 18^{n} + 2 · 6^{n} + 2^{n}

shows that the condition in Theorem 1 that G_{mq+r} not be a perfect qth power for every m can not be removed. Indeed, in this example the coefficients and roots of G_{n} satisfy the conditions of Theorem 1, but

G_{2m} = (18^{m} + 2^{m})^{2},

so G_{2m} is a perfect square for all m ∈ ℕ.

Remark 4. The assumption α_{1} > α_{2} > ⋯ > α_{t} > 0 guarantees that the recurring sequence (G_{n}) is nondegenerate.

Remark 5. We want to mention that the proof of Theorem 1 should also work in the case when (G_{n}) is a linear recurring sequence with algebraic characteristic roots α_{1}, …, α_{t}, which are multiplicatively independent and satisfy

|α_{1}| > |α_{i}|, ∀i = 2, …, t,

and with a_{i} ∈ ℚ(α_{1}, …, α_{t}) for all i = 1, …, t.

Our second main result extends Theorem 1 to the situation when also q is considered to be variable.

Theorem 2. Let (G_{n}) be a linear recurring sequence defined by

G_{n} = a_{1}α_{1}^{n} + a_{2}α_{2}^{n} + ⋯ + a_{t}α_{t}^{n},

where a_{1}, …, a_{t} (t ≥ 3) are non-zero rational numbers, α_{1} > … > α_{t} > 0 are integers and such that (for fixed q ≥ 2) there is no r ∈ {0, …, q − 1} with G_{mq+r} a perfect qth power for all m ∈ ℕ. Then the equation

G_{n} = x^{q}

has only finitely many integral solutions n, x > 1, q. The number of solutions can be bounded by an explicitly computable constant C depending only on the recurrence.

Remark 6. The assumption t ≥ 3 means no loss of generality, because for t = 2 this theorem is already well known (see [13], [19]).

Remark 7. Our proof of Theorem 2 depends on an application of the result of Nemes and Pethő [11] which was mentioned in the introduction in detail.

Remark 8. By Remark 5 and the theorem in [11] it should also be possible to obtain the following finiteness result: Let G_{n} be the nth term of a linear recurrence sequence defined by (9), where t ≥ 3, α_{1} …, α_{t} are multiplicatively independent algebraic numbers with

|α_{1}| > |α_{2}| > |α_{i}|, ∀i = 3, …, t,

and a_{i} ∈ ℚ(α_{1}, …, α_{t}) for all i = 1 …, t. Assuming that for fixed q ≥ 2 there is no r ∈ {0, …, q − 1} with G_{mq+r} a perfect qth power for all m ∈ ℕ, the equation

G_{n} = x^{q}

has only finitely many integral solutions n, x > 1, q.

3. Auxiliary Results

Our proof of Theorem 1 depends on a quantitative version of the Subspace Theorem due to J.-H. Evertse [5].

Let K be an algebraic number field. Denote its ring of integers by O_{K} and its collection of places by M_{K}. For v ∈ M_{K}, x ∈ K, we define the absolute value |x|_{v} by

(i) |x|_{v} = |σ(x)|^{1/[K:ℚ]} if v corresponds to the embedding σ : K ↪ ℝ; (ii) |x|_{v} = |σ(x)|^{2/[K:ℚ]} = |σ̄(x)|^{2/[K:ℚ]} if v corresponds to the pair of conju-

gate complex embedding σ, σ̄ : K ↪ ℂ; (iii) |x|_{v} = (N℘)^{−ord_{℘}(x)/[K:ℚ]} if v corresponds to the prime ideal ℘ of O_{K}. Here N℘ = #(O_{K}/℘) is the norm of ℘ and ord_{℘}(x) the exponent of ℘ in the prime ideal composition of (x), with ord_{℘}(0) := ∞. In case (i) or (ii) we call v real infinite or complex infinite, respectively; in case (iii) we call v finite. These absolute values satisfy the Product formula

∏_{v∈M_{K}} |x|_{v} = 1 for x ∈ K^{∗}. (10)

The height of x = (x_{1}, …, x_{n}) ∈ K^{n} with x ≠ 0 is defined as follows: for v ∈ M_{K} put

|x|_{v} = (∑_{i=1}^{n} |x_{i}|_{v}^{2[K:ℚ]})^{1/(2[K:ℚ])} if v is real infinite,
|x|_{v} = (∑_{i=1}^{n} |x_{i}|_{v}^{[K:ℚ]})^{1/[K:ℚ]}  if v is complex infinite,
|x|_{v} = max(|x_{1}|_{v}, …, |x_{n}|_{v})  if v is finite

(note that for infinite places v, | · |_{v} is a power of the Euclidean norm). Now define

H(x) = H(x_{1}, …, x_{n}) = ∏_{v} |x|_{v}.

For a linear form l(X) = a_{1}X_{1} + ⋯ + a_{n}X_{n} with algebraic coefficients we define H(l) := H(a), where a = (a_{1}, …, a_{n}) and if a ∈ K^{n} then we put |l|_{v} = |a|_{v} for v ∈ M_{K}. Further we define the number field K(l) := K(a_{1}/a_{j}, …, a_{n}/a_{j}) for any j with a_{j} ≠ 0; this is independent of the choice of j.

We are now ready to state Evertse’s result [5]. The following notation is used:

- S is a finite set of places on K of cardinality s containing all infinite places;

- {l_{1v}, …, l_{nv}}, v ∈ S are linearly independent sets of linear forms in n variables with algebraic coefficients such that

H(l_{iv}) ≤ H, [K(l_{iv}) : K] ≤ D for v ∈ S, i = 1, …, n.

We choose for every place v ∈ M_{K} a continuation of | · |_{v} to the algebraic closure of K and denote this also by | · |_{v}.

Theorem 3. (Quantitative Subspace Theorem, Evertse) Let 0 < δ < 1 and consider the inequality for x ∈ K^{n}

∏_{v∈S} ∏_{i=1}^{n} \frac{|l_{iv}(x)|_{v}}{|x|_{v}} < (∏_{v∈S} | det(l_{1v}, …, l_{nv})|_{v}) · H(x)^{−n−δ} . (11)

Then the following assertions hold:

(i) There are proper linear subspaces T_{1}, …, T_{t_{1}} of K^{n}, with

t_{1} ≤ (2^{60n^{2}} · δ^{−7n})^{s} log 4D · log log 4D

such that every solution x ∈ K^{n} of (11) satisfying H(x) ≥ H belongs to T_{1} ∪ ⋯ ∪ T_{t_{1}}. (ii) There are proper linear subspaces S_{1}, …, S_{t_{2}} of K^{n}, with

t_{2} ≤ (150n^{4} · δ^{−1})^{ns+1}(2 + log log 2H)

such that every solution x ∈ K^{n} of (11) satisfying H(x) < H belongs to S_{1} ∪ ⋯ ∪ S_{t_{2}}.

We also need the following theorem of W. M. Schmidt [18] concerning the zero multiplicity of a nondegenerate recurring sequence.

Theorem 4. (W. M. Schmidt) Suppose that (G_{n})_{n∈ℤ} is a nondegenerate linear recurring sequence of complex numbers, whose characteristic polynomial has k distinct roots of multiplicity ≤ a. Then the number of solutions n ∈ ℤ of the equation

G_{n} = 0,

can be bounded above by

c(k, a) = e^{(7k^{a})^{8k^{a}}}.

(This number of solutions is called the zero multiplicity of the recurrence.)

In the proof of Theorem 2 we also apply the following result due to A. Baker [1]. Let us first recall the definition of the absolute logarithmic Weil height: For an algebraic number β let P_{β}(x) = x^{k}+a_{k−1}x^{k−1}+⋯+a_{0} ∈ ℤ[x] denote the minimal polynomial of β. Further let β_{1} = β, β_{2}, …, β_{k} denote the conjugates of β. Then we call

h(β) = \frac{1}{k} log (∏_{i=1}^{k} max\{1, |β_{i}|\})

the absolute logarithmic Weil height of β.

Theorem 5. (A. Baker) Let α_{1}, …, α_{k} be algebraic numbers, different from 0 or 1, K = ℚ(α_{1}, …, α_{k}) and d let be the degree [K : ℚ]. For i = 1, …, k set

h_{i} = max \{h(α_{i}), \frac{e | log α_{i}|}{d}, \frac{1}{d}\} .

Let b_{1}, …, b_{k} ∈ ℤ, b_{k} > 0, Λ = b_{1} log α_{1} + ⋯ + b_{k} log α_{k} ≠ 0 and B = max{2, |b_{1}|, …, |b_{k−1}|}. Then we have

(12) log |Λ| > −C(k)d^{k+2}h_{1} ⋯ h_{k} log (C(k)d^{k+2}h_{1} ⋯ h_{k−1}) log b_{k} − \frac{B}{b_{k}} ,

where

C(k) = 2^{26k}k^{3k}.

A proof of this theorem with the given explicit constants can be found in the monograph of Waldschmidt [26], page 309, Corollary 9.24.

Below we have collected some simple lemmas which are needed in our proofs.

Lemma 1. Let N_{j,k} denote the number of formal summands of (a_{1} + ⋯ + a_{k})^{j}, where a_{1}, …, a_{k} denote formal commuting variables. Then

N_{j,k} = \binom{k + j − 1}{j}.

This is well known from combinatorics.

Lemma 2. Let d be a positive integer. Then for the complex function f(z) = (1 + z)^{1/d} we have

|f(z) − ∑_{k=0}^{n} \binom{1/d}{k}z^{k}| ≤ \frac{1}{d(n + 1)(1 − |z|)} · |z|^{n+1}

for z ∈ ℂ, |z| < 1, where we have chosen the branch of (1 + z)^{1/d} which is holomorphic on ℂ\(−∞, −1] and which is equal to the positive d-th root of (1 + z) for z ∈ ℝ, z > −1.

Proof. It is well-known that for z ∈ ℂ, |z| < 1 we have

f(z) = ∑_{k=0}^{∞} \binom{1/d}{k}z^{k}.

Because of

(n + 1) |\binom{1/d}{n + 1}| = \frac{\frac{1}{d} · (1 − \frac{1}{d}) · . . . · (n − \frac{1}{d})}{1 · . . . · n} < \frac{1}{d} < 1

we obtain

|f(z) − ∑_{k=0}^{n} \binom{1/d}{k}z^{k}| ≤ ∑_{k=n+1}^{∞} |\binom{1/d}{k}| · |z|^{k} ≤

≤ \frac{1}{d(n + 1)} ∑_{k=n+1}^{∞} |z|^{k} =

= \frac{1}{d(n + 1)(1 − |z|)} · |z|^{n+1},

and therefore the proof is complete. □

Lemma 3. Let a, b ≥ 0 and let x ∈ ℝ be the largest solution of x = a + b log x. If b > e^{2} then

x < 2 (a + b log b) .

This lemma is due to A. Pethő and B.M.M. de Weger [22].

4. Proof of Theorem 1

According to Theorem 4 the number of solutions of (8) of the form (n, 0), n ∈ ℕ can be estimated by

c_{1}(t) ≤ e^{(7t)^{8t}}.

Therefore we can restrict ourselves to solutions of the form (n, x) ∈ ℕ^{2} with x ≠ 0. These solutions are denoted by (n, x_{n}) ∈ ℕ^{2} with n ∈ Σ, where Σ is a set of positive integers.

Let us now consider the expansion of the function f(z) = (1+z)^{1/q} around the origin

(1 + z)^{1/q} = ∑_{j=0}^{∞} \binom{1/q}{j}z^{j}, with |z| ≤ 1, z ≠ −1.

We approximate G_{n}^{1/q} by defining

H_{m} := (a_{1}α_{1}^{r})^{1/q} · α_{1}^{m} [1 + ∑_{j=1}^{R} \binom{1/q}{j} · (∑_{i=2}^{t} \frac{a_{i}α_{i}^{mq+r}}{a_{1}α_{1}^{mq+r}} )^{j}] ,

where R ≥ 1 is an integer to be chosen later and where we have set n = mq + r with n ∈ ℕ, r ∈ {0, …, q − 1}. We write

H_{m} = ∑_{i=1}^{h} d_{i} (\frac{e_{i}}{b} )^{m} ,

where d_{i} ∈ ℚ ((a_{1}α_{1}^{r})^{1/q})^{∗}, e_{i}, b are integers, b > 0, and the e_{i}/b are non-zero distinct rational numbers. Clearly, H_{m} is nondegenerate (the roots are all positive) and we have

[ℚ ((a_{1}α_{1}^{r})^{1/q}) : ℚ] ≤ q.

By Lemma 1 we obtain

h ≤ \binom{R + t − 1}{R}.

On the other hand, we have

|∑_{i=2}^{t} \frac{a_{i}α_{i}^{mq+r}}{a_{1}α_{1}^{mq+r}} | ≤ (t − 1)c (\frac{α_{2}}{α_{1}} )^{mq+r} ≤ \frac{1}{2} < 1

where

c := max \{|\frac{a_{i}}{a_{1}} | | i = 2, …, t\} ,

PERFECT POWERS IN RECURRENCES 11

if

m ≥ \frac{log 2(t − 1)c}{q log \frac{α_{1}}{α_{2}}}. (13)

Therefore, by Lemma 2 for m we get for m large enough |H_{m} − x_{mq+r}| = |G_{mq+r}^{1/q} − H_{m}| ≤

≤ |a_{1}^{1/q}| · α_{1}^{r/q} · α_{1}^{m} · \frac{1}{q(R + 1) (1 − |∑_{i=2}^{t} \frac{a_{i}α_{i}^{mq+r}}{a_{1}α_{1}^{mq+r}} |)} |∑_{i=2}^{t} \frac{a_{i}α_{i}^{mq+r}}{a_{1}α_{1}^{mq+r}} |^{R+1} ≤

≤ |a_{1}^{1/q}| · α_{1} · α_{1}^{m} · \frac{2}{q(R + 1)} [(t − 1)c (\frac{α_{2}}{α_{1}} )^{r} (\frac{α_{2}}{α_{1}} )^{mq}]^{R+1} ≤
≤ |a_{1}^{1/q}| · α_{1}^{r/q} · [(t − 1)c]^{R+1} · α_{1}^{m} · (\frac{α_{2}}{α_{1}} )^{mq(R+1)} .

Thus we derive |H_{m} − x_{mq+r}| ≤ c_{2}(R) · l_{1}^{m} (14) where we have set

l_{1} := α_{1} · (\frac{α_{2}}{α_{1}} )^{q(R+1)}

and

c_{2}(R) := |a_{1}^{1/q}| · α_{1} · [(t − 1)c]^{R+1} .

Now choose

(15) R > max \{1, \frac{1}{q} \frac{log α_{1}}{log \frac{α_{1}}{α_{2}}} − 1\} .

Then 0 < l_{1} < 1. Put

l := \frac{l_{1} + 1}{2}.

Then for m large enough, to be more precise, for

m > \frac{log c_{2}(R)}{log \frac{l}{l_{1}}} (16)

we have

c_{2}(R) · l_{1}^{m} = c_{2}(R) (\frac{l_{1}}{l} )^{m} · l^{m} < l^{m}.

Consequently we obtain

|H_{m} − x_{mq+r}| < l^{m} with 0 < l < 1, (17)

provided that R satisfies (15) and m satisfies (13) and (16).

Now let S be the set of places of ℚ consisting of ∞ and all primes dividing some of the e_{i} or b. Extend each place in S to K := ℚ ((a_{1}α_{1}^{r})^{1/q}) in some way, the infinite place being extended such that it coincides with the complex absolute value in the given embedding of K in ℂ. Define the linear forms L_{i,v} for v ∈ S and i = 1, …, h as follows: L_{0,∞} := L := X_{0} − ∑_{i=1}^{h} d_{i}X_{i}, L_{i,∞} := X_{i} for i = 1, …, h, while for v ∈ S, v ≠ ∞, put L_{i,v} := X_{i} for i = 1, …, h. Then {L_{0,v}, …, L_{h,v}}, v ∈ S are linearly independent sets of linear forms in h + 1 variables with coefficients in K. Furthermore we have

H(L_{i,v}) = \{ \begin{matrix}H(1, −d_{1}, …, −d_{h}) =: H̃ & for i = 0, v = ∞ \\ H(0, …, 0, 1, 0, …, 0) = 1 & else. \end{matrix}

We set H := max{1, H̃} then it follows H(L_{i,v}) ≤ H, for v ∈ S, i = 0, …, h. Then ℚ(L_{i,v}) = ℚ, for v ≠ ∞, [ℚ(L_{0,∞}) : ℚ] ≤ q and therefore

[ℚ(L_{i,v}) : ℚ] ≤ q ∀v ∈ S, i = 0, …, h.

For n ∈ Σ define the vector x_{m} = (b^{m}x_{mq+r}, e_{1}^{m}, …, e_{h}^{m}) ∈ ℤ^{h+1}.

From (17) we obtain |L_{0,∞}(x_{m})| ≤ (bl)^{m}. Recall that S includes all primes dividing b and that the x_{mq+r} are integers. Thus by the product formula (10),

∏_{v∈S\{∞}} |L_{0,v}(x_{m})|_{v} = ∏_{v∈S\{∞}} |b^{m}x_{mq+r}|_{v} ≤ ∏_{v∈S\{∞}} |b^{m}|_{v} = b^{−m}.

Moreover, since S includes also the primes dividing the numbers e_{i} the product formula (10) gives

∏_{v∈S} ∏_{i=1}^{h} |L_{i,v}(x_{m})|_{v} = ∏_{v∈S} ∏_{i=1}^{h} |e_{i}^{m}|_{v} = 1.

Thus we obtain

∏_{v∈S} ∏_{i=0}^{h} \frac{|L_{i,v}(x_{m})|_{v}}{|x_{m}|_{v}} ≤ (∏_{v∈S} |x_{m}|_{v})^{−h−1} · l^{m}.

Since the coordinates of the vectors x_{m} are integers we have |x_{m}|_{v} ≤ 1 for v ∈ M_{ℚ}\{∞}. Further, we have

|x_{m}|_{∞} ≤ A^{m}

PERFECT POWERS IN RECURRENCES 13

for some real A independent of m. Indeed, we have

|x_{mq+r}| ≤ |x_{mq+r} − H_{m}| + |H_{m}| ≤ l^{m} + h · c̃ · a^{m} ≤ 1 + h · c̃ · a^{m} ≤ ã^{m}, with

c̃ := max{|d_{i}| | i = 1, …, h},
a := max \{|\frac{e_{i}}{b} | | i = 1, …, h\} ,

and ã := (1 + h · c̃)(1 + a). Hence

|x_{m}|_{∞} = (|b^{m}x_{mq+r}|^{2} + ∑_{i=1}^{h} |e_{i}|^{2})^{1/2} ≤
≤ ((bã)^{2m} + h(ba)^{2m})^{1/2} ≤ A^{m}

with A := (h + 1)ãb. It follows that

H(x_{m}) = ∏_{v∈M_{ℚ}} |x_{m}|_{v} ≤ ∏_{v∈S} |x_{m}|_{v} ≤ |x_{m}|_{∞} ≤ A^{m}.

Lastly we have

det(L_{0,v}, …, L_{h,v}) = | \begin{matrix}1 & 0 & 0 & ⋯ & 0 \\ ∗ & 1 & 0 & ⋯ & 0 \\ ∗ & 0 & 1 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & & ⋮ \\ ∗ & 0 & 0 & ⋯ & 1 \end{matrix} | = 1,

which yields

| det(L_{0,v}, …, L_{h,v})|_{v} = 1 ∀v ∈ S.

Combining our estimates we get

∏_{v∈S} ∏_{i=0}^{h} \frac{|L_{i,v}(x_{m})|_{v}}{|x_{m}|_{v}} < (∏_{v∈S} | det(L_{0,v}, …, L_{h,v})|_{v}) · H(x_{m})^{−h−1−δ}

for all m with (16), provided that δ < log(1/l)/ log A. By Theorem 3 there exist finitely many non-zero rational linear forms Λ_{1}(X_{0}, …, X_{h}), …, Λ_{g}(X_{0}, …, X_{h}) with

g ≤ (2^{60(h+1)^{2}} · δ^{−7(h+1)})^{s} log 4q · log log 4q+

+(150(h + 1)^{4} · δ^{−1})^{(h+1)s+1}(2 + log log 2H),

such that each vector x_{m} is a zero of some Λ_{j}.

Suppose first Λ_{j} does not depend on X_{0}. Then, if Λ_{j}(x_{m}) = 0, we have a nontrivial relation

∑_{i=1}^{h} u_{i} (\frac{e_{i}}{b} )^{m} = 0, u_{i} ∈ ℚ, i = 1, …, h.

By Theorem 4 this can hold for at most a finite number of m. More precisely, the number of solutions m can be estimated by

c_{1}(h) = e^{(7h)^{8h}},

since (H_{m}) is nondegenerate.

Suppose that Λ_{j} depends on X_{0} and that Λ_{j}(x_{m}) = 0. Then we have

∑_{i=1}^{h} v_{i} (\frac{e_{i}}{b} )^{m} = x_{mq+r}, v_{i} ∈ ℚ, i = 1, …, h. (18)

Set

U_{m} := ∑_{i=1}^{h} v_{i} (\frac{e_{i}}{b} )^{m} ,

then U_{m} is a nondegenerate, simple recurring sequence and we obtain

U_{m}^{q} = x_{mq+r}^{q} = G_{mq+r}.

Hence

V_{m} := (∑_{i=1}^{h} v_{i} (\frac{e_{i}}{b} )^{m})^{q} − ∑_{i=1}^{t} a_{i}α_{i}^{r}(α_{i}^{q})^{m},

has the form

V_{m} = ∑_{i=1}^{p} b_{i}β_{i}^{m}

with b_{i} ∈ ℚ, β_{i} ∈ ℚ^{+}, i = 1, …, p. Therefore V_{m} is a nondegenerate, simple recurring sequence, and we conclude by Lemma 1

p ≤ t + \binom{h + q − 1}{q} ≤ t + \binom{\binom{R+t−1}{t} + q − 1}{q}.

Observe that by our assumptions V_{m} = 0 does not hold for every m hence an i with b_{i} ≠ 0 exists. Again by Theorem 4 we can bound the number of solutions of (18) by

c_{1}(p) = e^{(7p)^{8p}}.

PERFECT POWERS IN RECURRENCES 15

Therefore the number of solutions of (8) can be estimated by C̃(q) :=

= e^{(7t)^{8t}} + \frac{log 2(t − 1)c}{log \frac{α_{1}}{α_{2}}} + q · [\{(2^{60(h̃+1)^{2}} · δ^{−7(h̃+1)})^{s} ·

· log 4q · log log 4q + (150(h̃ + 1)^{4} · δ^{−1})^{(h̃+1)s+1} · (2 + log log 2H)} ·

· \{e^{(7h̃)^{8h̃}} + e^{(7p̃)^{8p̃}}\} + \frac{log c_{2}(R)}{log \frac{l}{l_{1}}}],

where

h̃ = \binom{R + t − 1}{R}, p̃ = \binom{h̃ + q − 1}{q} + t

H = max{1, H(1, −d_{1}, …, −d_{h})}

s = |S|,

c_{2}(R) = |a_{1}^{1/q}| · α_{1} · [(t − 1)c]^{R+1} ,

δ < log(1/l)/ log A,

and l is as in (17). □

5. Proof of Theorem 2

Assume that n, x > 1, q ≥ 2 is a solution of (8) and write

x^{q} = G_{n} = a_{1}α_{1}^{n} + B(n).

We distinguish two cases: Case 1: B(n) = 0. Here we get

|B(n)| = |a_{2}α_{2}^{n} (1 + ∑_{i=3}^{t} \frac{a_{i}}{a_{2}} (\frac{α_{i}}{α_{2}} )^{n})| ≥ |a_{2}|α_{2}^{n} |1 − |∑_{i=3}^{t} \frac{a_{i}}{a_{2}} (\frac{α_{i}}{α_{2}} )^{n}|| > 0,

since

|∑_{i=3}^{t} \frac{a_{i}}{a_{2}} (\frac{α_{i}}{α_{2}} )^{n}| ≤

≤ max \{|\frac{a_{i}}{a_{2}} | | i = 3, …, t\} · (t − 2) · (\frac{α_{3}}{α_{2}} )^{n} ≤
≤ tc|a_{2}|^{−1} (\frac{α_{3}}{α_{2}} )^{n} < 1,

where c = max{|a_{i}| | i = 1, …, t}, whenever

n > \frac{log(tc|a_{2}|^{−1})}{log \frac{α_{2}}{α_{3}}} =: n_{1}.

Therefore n ≤ n_{1} must hold and we obtain from a_{1}α_{1}^{n} = x^{q} and x ≥ 2

q = \frac{log(|a_{1}|α_{1}^{n})}{log x} ≤ \frac{log(cα_{1}^{n_{1}})}{log 2}.

Case 2: B(n) ≠ 0. In this case we first set

δ := \frac{1}{2} (1 − \frac{log α_{2}}{log α_{1}} ) .

Then we get

|B(n)| ≤ tcα_{2}^{n} < \frac{1}{2}α_{1}^{n(1−δ)},

if

n > \frac{2 log(2ct)}{log \frac{α_{1}}{α_{2}}} =: n_{2}.

Further

\frac{x^{q}}{a_{1}α_{1}^{n}} = 1 + \frac{B(n)}{a_{1}α_{1}^{n}}, (19)

so

1 − (|a_{1}|α_{1}^{δn})^{−1} ≤ |a_{1}|^{−1}α_{1}^{−n}x^{q} ≤ 1 + (|a_{1}|α_{1}^{δn})^{−1}, (20)

where we have used that (|a_{1}|α_{1}^{δn})^{−1} < \frac{1}{2}, if

n > \frac{log(2|a_{1}|^{−1})}{δ log α_{1}} =: n_{3}.

Taking logarithms and using the inequalities | log(1 + x)| ≤ x and | log(1 − x)| ≤ 2x for 0 ≤ x < \frac{1}{2}, we derive by (20)

−2|a_{1}|^{−1}α_{1}^{−δn} ≤ − log |a_{1}| − n log α_{1} + q log x ≤ 2|a_{1}|^{−1}α_{1}^{−δn}.

Thus

(21) | − log |a_{1}| − n log α_{1} + q log x| ≤ 2|a_{1}|^{−1}α_{1}^{−δn}.

Put Λ = − log |a_{1}|−n log α_{1}+q log x. From (19) and the fact that B(n) ≠ 0, we get Λ ≠ 0. Thus we can employ Theorem 5 and obtain for n ≥ 2

(22) |Λ| > exp \{−C(3)h_{1}h_{2} log (C(3)h_{1}h_{2}) e log x log q − \frac{n}{q}\} ,

PERFECT POWERS IN RECURRENCES 17

where C(3) = 2^{78}3^{9} and

h_{1} = max{h(|a_{1}|^{−1}), e | log |a_{1}||, 1},
h_{2} = max{h(α_{1}), e log α_{1}, 1} = e log α_{1}.

Set

c_{3} := C(3)h_{1}h_{2} log (C(3)h_{1}h_{2}) e.

A comparison of (21) and (22) reveals that

(23) −c_{3} log q log x − \frac{n}{q} < log(2|a_{1}|^{−1}) − nδ log α_{1}.

However, for n > max{n_{1}, n_{2}},

\frac{1}{2}|a_{1}|α_{1}^{n} ≤ |a_{1}|α_{1}^{n} − |B(n)| ≤ x^{q} ≤ |a_{1}|α_{1}^{n} + |B(n)| ≤ ctα_{1}^{n}.

Thus, for

n > max \{\frac{log ct}{log α_{1}} , \frac{2 log(2|a_{1}|^{−1})}{log α_{1}}\} =: n_{4}

we obtain

\frac{log α_{1}}{2} n < q log x < 2 log α_{1}n.

Writing this as

\frac{n}{q} < \frac{2 log x}{log α_{1}}, \frac{log x}{2 log α_{1}} q < n,

(23) can be reformulated as

q < \frac{2 log(\frac{1}{2}|a_{1}|^{−1})}{δ log 2} + \frac{4}{δ log α_{1}} + \frac{2c_{3}}{δ} log q.

Thus by Lemma 3

q < 2 (\frac{2 log(\frac{1}{2}|a_{1}|^{−1})}{δ log 2} + \frac{4}{δ log α_{1}} + \frac{2c_{3}}{δ} log (\frac{2c_{3}}{δ} )) =: C_{1},

if n > max{2, n_{2}, n_{3}, n_{4}} =: n_{5}. Otherwise, we have

q ≤ \frac{log (ctα_{1}^{n_{5}})}{log 2}.

Altogether we derive

q ≤ max \{\frac{log (ctαc̄ ; 1)}{log 2}, C_{1}(q)\} =: C,

where c̄:= max{2, n_{1}, n_{2}, n_{3}, n_{4}}. For the number of solutions n, x > 1, q ≥ 2 of (8) we finally obtain the upper bound

∑_{q=2}^{C} C̃(q),

and therefore the proof is finished. □

6. Acknowledgement

The authors are most grateful to Prof. U. Zannier for several helpful remarks on a previous draft of the present paper. In particular, they are pleased to thank him for the help handling some exceptional hyperplanes in the proof of Theorem 1. Furthermore, the authors express their thanks to an anonymous referee for various suggestions improving the paper.

References

[1] A. Baker, A sharpening of the bounds for linear forms in logarithms II, Acta Arith. 24 (1973), 33-36.

[2] J. H. E. Cohn, On square Fibonacci numbers, J. Lond. Math. Soc. 39 (1964), 537-540.

[3] J. H. E. Cohn, Lucas and Fibonacci numbers and some diophantine equations, Proc. Glasgow Math. Assoc. 7 (1965), 24-28.

[4] P. Corvaja and U. Zannier, Diophantine equations with power sums and universal Hilbert sets, Indag. Math., New Ser. 9 (3) (1998), 317-332.

[5] J.H. Evertse, An improvement of the quantitative subspace theorem, Compos. Math. 101 (3) (1996), 225-311.

[6] R. Finkelstein, On Fibonacci numbers which are one more than a square, J. reine angew. Math. 262/263 (1973), 171-178.

[7] R. Finkelstein, On Lucas numbers which are one more than a square, Fibonacci Quart. 13 (1975), 340-342.

[8] P. Kiss, Differences of the terms of linear recurrences, Studia Sci. Math. Hung. 20 (1985), 285-293.

[9] J. C. Lagarias and D. P. Weisser, Fibonacci and Luacs cubes, Fibonacci Quart. 19 (1981), 39-43.

[10] H. London and R. Finkelstein, On Fibonacci and Lucas numbers which are perfect powers, Fibonacci Quart. 7 (1969), 476-481, 487. Corr. 8 (1970), 248.

[11] I. Nemes and A. Pethő, Polynomial values in linear recurrences, Publ. Math. 31 (1984), 229-233.

[12] I. Nemes and A. Pethő, Polynomial values in linear recurrences II, J. Number Theory 24 (1986), 47-53.

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

[14] A. Pethő, Perfect powers in second order recurrences, Topics in classical number theory, Vol.I,II, Proceedings of the Conference in Budapest 1981, Colloq. Soc. János Bolyai 34, North-Holland, Amsterdam, 1217-1227.

[15] A. Pethő, Full cubes in the Fibonacci sequence, Publ. Math. Debrecen 30 (1983), 117-127.

[16] W. M. Schmidt, “Diophantine Approximation”, Springer Verlag, LN 785, 1980.

[17] W. M. Schmidt, “Diophantine Approximations and Diophantine Equations”, Springer Verlag, LN 1467, 1991.

[18] W. M. Schmidt, The zero multiplicity of linear recurrence sequences, Acta Math. 182 (1999), 243-282.

[19] T. N. Shorey and C. L. Stewart, On the Diophantine equation ax^{2t} + bx^{t}y + cy^{2} = d and pure powers in recurrence sequences, Math. Scand. 52 (1983), 24-36.

[20] T. N. Shorey and C. L. Stewart, Pure Powers in Recurrence Sequences and Some Related Diophantine Equations, J. Number Theory 27 (1987), 324-352.

[21] T. N. Shorey and R. Tijdeman, “Exponential Diophantine Equations”, Cambrdige University Press, Cambridge, 1986.

[22] N. P. Smart, “The Algorithmic Resolution of Diophantine Equations”, Cambridge University Press, Cambridge, 1998.

[23] R. Steiner, On nth powers in the Lucas and Fibonacci series, Fibonacci Quart. 16 (1978), 451-458.

[24] R. Steiner, On Fibonacci numbers of the form x^{2} + 1, A Collection of Manuscripts related to the Fibonacci Sequence (1980), Fibonacci Associoation, Santa Clara, California, 208-210.

[25] C. L. Stewart, “On Some Diophantine Equations and Related Linear Recurrence Sequences”, Sém. de Théorie des Nombres, Paris, 1980-1981, Birkhauser, Boston, 1982.

[26] M. Waldschmidt, “Diophantine Approximation On Linear Algebraic Groups”, Springer-Verlag, Berlin, 2000.

[27] H. C. Williams, On Fibonacci numbers of the form k^{2} + 1, Fibonacci Quart. 13 (1975), 213-214.

[28] O. Wyler, Squares in the Fibonacci series, Am. Math. Monthly 71 (1964), 220-222.

Clemens Fuchs Institut für Mathematik TU Graz Steyrergasse 30 A-8010 Graz, Austria e-mail: clemens.fuchs@tugraz.at.

Robert F. Tichy Institut für Mathematik TU Graz Steyrergasse 30 A-8010 Graz, Austria e-mail: tichy@tugraz.at.