POLYNOMIAL-EXPONENTIAL EQUATIONS INVOLVING MULTI-RECURRENCES

CLEMENS FUCHS^{∗}

Abstract. In this paper we consider polynomial-exponential Diophantine equations of the form

G_{n}^{(0)}y^{d} + G_{n}^{(1)}y^{d−1} + … + G_{n}^{(d−1)}y + G_{n}^{(d)} = 0

where G_{n}^{(i)} are multi-recurrences, i.e. polynomial-exponential functions in n = (n_{1}, …, n_{k}) variables. Under suitable (but restrictive) conditions we prove that there are finitely many multi-recurrences H_{n}^{(1)}, …, H_{n}^{(s)} such that for all solutions (n_{1}, …, n_{k}, y) ∈ ℕ^{k} × ℤ we either have

H_{n}^{(i)} = 0 or y = H_{n}^{(j)}

for certain 1 ≤ i, j ≤ s, respectively. This generalizes earlier results of this type on such equations. The proof uses a recent result by Corvaja and Zannier.

2000 Mathematics Subject Classification: 11D72,11D61,11B37. Key words and phrases: polynomial-exponential Diophantine equations, multi-recurrences, Subspace Theorem

1. Introduction

Let k ∈ ℕ be arbitrary and let V_{k} be the vector space of functions ℤ^{k} → ℂ. Its elements will be called multi-sequences. When G ∈ V_{k}, its value at n ∈ ℤ^{k} will be denoted G_{n}. Moreover, let R_{k} be the ring ℂ[Z_{1}, …, Z_{k}, Z_{1}^{−1}, …, Z_{k}^{−1}] in variables Z_{1}, …, Z_{k} (the elements are called generalized polynomials). R_{k} acts on V_{k} in the following way: given

P(Z) = ∑_{k} c_{k}Z^{k} ∈ R_{k}

and G ∈ V_{k}, we let PG be the multi-sequence with

(PG)_{n} = ∑_{k} c_{k}G_{n+k}.

Clearly, R_{k} is a vector space over ℂ and PG is bilinear in the spaces R_{k} and V_{k}.

Date: July 9, 2007.

∗This paper was supported by the Austrian Science Foundation FWF, grants J2407-N12 and NFN S9611.

Now, an element G ∈ V_{k} is called a multi-recurrence sequence if R_{k}/I, where I denotes the ideal of R_{k} made up by all P with PG = 0, is of finite dimension. This dimension is called the order of G.

It is well known that every multi-recurrence G is represented by a function of polynomial-exponential type, that is a function f : ℤ^{k} → ℂ of the form

(1)  f(n) = f(n_{1}, …, n_{k}) = ∑_{i=1}^{q} P_{i}(n)α_{i}^{n}

where P_{i} ∈ ℂ[X_{1}, …, X_{k}] and

α_{i}^{n} = α_{i1}^{n_{1}} ⋯ α_{ik}^{n_{k}}

with nonzero α_{ij} for 1 ≤ i ≤ q, 1 ≤ j ≤ k, i.e. for every multi-recurrence G ∈ V_{k} there is a function of polynomial-exponential type f with G_{n} = f(n). We call the α_{i} the roots and the P_{i} the coefficients of the recurrence G_{n}.

We remark that for k = 1 we get the usual notion of linear recurring sequences. Many useful facts on multi-recurrences can be found in [38] (for linear recurrences see the exposition [32]).

Especially, we remark that there is a factorization theory for multirecurrences which is essentially due to Ritt and Everest and van der Poorten (see [37, Chapter 4] and [8]). Namely, when G_{n} = f(n) with (1) is given, then we consider it as a function ℂ^{k} → ℂ given by

f(ξ) = ∑_{i=1}^{q} P_{i}(ξ)e(φ_{i}ξ)

where e(ξ) = exp(2πiξ) and φ_{i}ξ denotes an inner product φ_{i1}ξ_{1} + … + φ_{ik}ξ_{k}. The restriction of f to ℤ^{k} gives the function above with α_{i} = (e(φ_{i1}), …, e(φ_{ik})). Then we have that every nonzero polynomialexponential function of this form may be factored into a function

∏_{j=1}^{t}(e(φ_{j}ξ) − c_{j})

and a product of irreducible elements, some of which may be ordinary polynomials, and some may be genuinely of polynomial-exponential type.

It is natural to consider Diophantine equations involving recurrences. For example we can ask, whether or not the equation

G_{n} = ∑_{i=1}^{q} P_{i}(n)α_{i}^{n} = 0

has only finitely many solutions. Laurent (cf. [38, Theorem 7.1]) proved (even in a more general way) that if G_{n} is non-degenerate, i.e. there is no n ≠ 0 such that α_{i}^{n} = α_{j}^{n} for every 1 ≤ i < j ≤ q, then there are indeed only finitely many n ∈ ℤ^{k} with G_{n} = 0.

Today much more is known on Diophantine equations where recurrences are involved. One major question was to find or to characterize all perfect powers in a given recurrence. First results were obtained for dimension k = 1, i.e. for usual linear recurrences G_{n}, especially for well-known sequences as the Lucas or Fibonacci sequence. We mention that it was only recently that Bugeaud, Mignotte and Siksek were able to calculate all perfect powers in the Lucas and Fibonacci sequence (cf. [3]). Later, the results were obtained with the applications of lower bounds for linear forms in logarithms of algebraic numbers (e.g. cf. [39, 40, 41, 30, 31, 15]). In 2000, Zannier [44] solved Pisot’s d-th root conjecture that states that if a recurrence G_{n} is a d-th power in a fixed number field for all n, then it is identically equal to the d-th power of a linear recurring sequence. This also solves the general case, since Rumely and van der Poorten [35] showed how it can be reduced to the number field case.

Recently, a new development was started by Corvaja and Zannier (in [4, 6], see also [14, 10] for quantifications). They used the Subspace Theorem of W.M. Schmidt [36, 37] to obtain several new and surprising results. (For these results we refer to two recent surveys in [45, 11].) For example in [12] we characterized the solutions (n, y) ∈ ℕ × ℤ of polynomial-exponential equation of the form

(2)  G_{n}^{(0)}y^{d} + … + G_{n}^{(d−1)}y + G_{n}^{(d)} = 0,

where

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

⋮ (3)

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

with a_{i}^{(j)} algebraic and α_{i}^{(j)} positive integers such that α_{1}^{(j)} > α_{2}^{(j)} > … > α_{t^{(j)}}^{(j)} for all i = 1, …, t^{(j)} and j = 0, …, d. Let

(4)  α = max_{i=1,...,d} \{( \frac{α_{1}^{(i)}}{α_{1}^{(0)} ^{\frac{d−i}{d}}} )^{\frac{1}{i}} \} .

This is the “dominant” root after a suitable variable transformation (see below) of the left hand side of (2). Under the additional assumption that the discriminant of the transformed equation does not vanish (cf. [12, p. 154]), it can be proved that there are finitely many linear recurrences H_{n}^{(1)}, …, H_{n}^{(s)} such that for all solutions (n, y) ∈ ℕ × ℤ of (2) we either have

H_{n}^{(i)} = 0 or y = H_{n}^{(j)}

for 1 ≤ i, j ≤ s. Moreover, the set of n’s lie in the union of finitely many arithmetic progressions. Later in [13] we generalized this result to the corresponding inequality.

All these results involved only one polynomial and one exponential variable. The next natural step is to consider more than one exponential variable and therefore to consider such equations involving multi-recurrences. Special equations in two or three exponential variables where considered by several authors, e.g. in [33, 34, 27, 28, 29, 43, 24, 25, 23].

Special attention was given to the question of determining perfect powers in a product of (usual) linear recurrences with respect to different variables. In [16, 2, 42, 17] Kiss, Brindza, Liptai and Szalay (for generalisations of these results see also [18, 20, 19, 26]) showed that, under some restrictions, if the product G_{n_{1}}^{(1)} ⋯ G_{n_{k}}^{(k)} = y^{d} where G_{n}^{(i)} are linear recurrences with a single dominant root, then the exponent d of the power is bounded above by an effectively computable constant (the proof used Baker’s method). The main new restriction to handle the several exponential variables was that min{n_{1}, …, n_{k}} > γ · max{n_{1}, …, n_{k}} for some fixed 0 < γ < 1. We will see that this condition appears also in our results below.

Corvaja and Zannier used their approach (which we already have mentioned above) to attack the problem for polynomial-exponential equations of the form f(a^{n}, y) = b^{m}, where a, b > 1 are integers and f(x, y) ∈ ℚ[x, y] is a polynomial that is monic in y. Under the assumption that the discriminant of f(x, y) with respect to y at x = 0 does not vanish and a, b are not relatively prime they proved that infinite families of solutions must come from polynomial identities of the form f(x^{h}, p(x)) = cx^{k}. Moreover, they also gave a functional counterpart of this result, where they proved that all these identities can be found effectively.

The aim of the present paper is to find a suitable generalization of the above result to a Diophantine equation where multi-recurrences are involved, especially in the spirit of the results in [12]. Let f(x_{0}, …, x_{d}, y) ∈ \overline{ℚ}[x_{0}, …, x_{d}, y] (where \overline{ℚ} denotes an algebraic closure of ℚ) and let G_{n}^{(0)}, …, G_{n}^{(d)} sequences of integers which are multi-recurrences, then we will consider the Diophantine equation

f (G_{n}^{(0)}, …, G_{n}^{(d)}, y) = 0.

From our general results we will also derive results for perfect powers of products of linear recurrences with respect to different variables.

2. Notations and results

Let K be an algebraic number field. Denote its collection of places by M_{K} and let S be a finite set of absolute values of K containing the archimedean ones. For every place v of K we denote by | · |_{v} a continuation of it to \overline{ℚ} and normalize it “with respect to K”: according to this normalization, for x ∈ K\{0} the absolute logarithmic Weil height is

h(x) = ∑_{v∈M_{K}} log max{1, |x|_{v}}

and the Product formula

(5)  ∏_{v∈M_{K}} |x|_{v} = 1

holds. We note that these conditions uniquely determine our normalizations. We fix a ν ∈ M_{K} for the rest of the paper. Moreover, we set

|x|_{ν} := ∏_{i=1}^{k} |x_{i}|_{ν}

for every vector x = (x_{1}, …, x_{k}) ∈ K^{k}\{0} and k ≥ 1. Finally, the set O_{S} of S-integers is defined as the set of elements x ∈ K with |x|_{v} ≤ 1 for all v ∉ S.

Let d ≥ 2 be an integer and let G_{n}^{(0)}, …, G_{n}^{(d)} be multi-recurrences of integers defined by

G_{n}^{(0)} = a_{1}^{(0)} (α_{1}^{(0)})^{n} + ∑_{i=2}^{t^{(0)}} P_{i}^{(0)}(n) (α_{i}^{(0)})^{n}

⋮ (6)

G_{n}^{(d)} = a_{1}^{(d)} (α_{1}^{(d)})^{n} + ∑_{i=2}^{t^{(d)}} P_{i}^{(d)}(n) (α_{i}^{(d)})^{n} ,

where a_{1}^{(j)} ∈ K\{0}, P_{i}^{(j)}(x_{1}, …, x_{k}) ∈ K[x_{1}, …, x_{k}] and α_{i}^{(j)} ∈ K^{k} satisfy a dominant root condition with respect to ν, i.e.

(7)  |α_{1}^{(j)}|_{ν} > |α_{i}^{(j)}|_{ν} , for all i = 2, …, t^{(j)}, j = 0, …, d.

Now we consider the Diophantine equation

(8)  G_{n}^{(0)}y^{d} + … + G_{n}^{(d−1)}y + G_{n}^{(d)} = 0.

Let f(x_{0}, …, x_{d}, y) := x_{0}y^{d} + … + x_{d−1}y + x_{d} be fixed for the rest of the paper. So the above equation becomes

f (G_{n}^{(0)}, …, G_{n}^{(d)}, y) = 0.

Let α_{1}^{(j)} = (α_{1}^{(j)}, …, α_{k}^{(j)}) and A be the set of all elements γ of the form

γ = ((\frac{α_{1}^{(j)}}{(α_{1}^{(0)})^{\frac{d−j}{d}}} )^{\frac{1}{j}} , …, (\frac{α_{k}^{(j)}}{(α_{k}^{(0)})^{\frac{d−j}{d}}} )^{\frac{1}{j}} )

for j = 1, …, d, where for the l-th roots we always take the main value, i.e. the usual positive real l-th root of the absolute value and the l-th fraction of the argument from [0, 2π]. We enlarge K at once such that it contains all the components of these vectors, as well as the d-th roots of the components of α_{1}^{(0)}. Now let α ∈ A so that |α|_{ν} = max{|γ|_{ν} : γ ∈ A}. Moreover, we assume that

(9)  there is exactly one such α ∈ A.

Finally, we consider the variable transformation

y = \begin{matrix}α & n \\ ((α_{1}^{(0)})^{\frac{1}{d}} ) & n \end{matrix} z

where (α_{1}^{(0)})^{\frac{1}{d}} = ((α_{1}^{(0)})^{\frac{1}{d}} , …, (α_{k}^{(0)})^{\frac{1}{d}} ) . Then consider

(10)  \frac{1}{α^{dn}} f (G_{n}^{(0)}, …, G_{n}^{(d)}, \begin{matrix}α & n \\ ((α_{1}^{(0)})^{\frac{1}{d}} ) & n \end{matrix} z) .

This is a polynomial in z whose coefficients are again multi-recurrences. We denote by γ_{1}, …, γ_{r} the different roots of these multi-recurrences that are different from (1, …, 1)^{n} = 1. By identifying the expressions γ_{i}^{n} in (10) by a new variable x_{n+i}, we get a polynomial (linear in x_{n+1}, …, x_{n+r}) g(x, x_{n+1}, …, x_{n+r}, z) ∈ K[x, x_{n+1}, …, x_{n+r}, z] such that

g(n, γ_{1}^{n}, …, γ_{r}^{n}, z) = \frac{1}{α^{dn}} f (G_{n}^{(0)}, …, G_{n}^{(d)}, \begin{matrix}α & n \\ ((α_{1}^{(0)})^{\frac{1}{d}} ) & n \end{matrix} z) .

We denote the discriminant of g with respect to z evaluated at (0, …, 0) by

D (G_{n}^{(0)}, …, G_{n}^{(d)}) := disc_{z}(g)(0, …, 0).

We are now in the position to formulate our main result. Our aim is to prove that all solutions of (8) can be parametrized by finitely many multi-recurrences (in concrete terms this means that there are only finitely many solutions, apart from “trivial” cases).

Theorem 1. Let d ≥ 2 and let G_{n}^{(0)}, …, G_{n}^{(d)} be defined as in (6). Moreover, we assume (7) and (9) and that

(11)  D (G_{n}^{(0)}, …, G_{n}^{(d)}) ≠ 0.

Then there exist finitely many recurrences H_{n}^{(1)}, …, H_{n}^{(s)} with algebraic coefficients and algebraic roots and an effectively computable constant C < 1 such that for every fixed C < γ < 1 and for all solutions (n_{1}, …, n_{k}, y) ∈ ℕ^{k} × ℤ of the equation

f (G_{n}^{(0)}, …, G_{n}^{(d)}, y) = G_{n}^{(0)}y^{d} + … + G_{n}^{(d−1)}y + G_{n}^{(d)} = 0

with min{n_{1}, …, n_{k}} ≥ γ · max{n_{1}, …, n_{k}} we either have

H_{n}^{(i)} = 0 or y = H_{n}^{(j)}

for certain 1 ≤ i, j ≤ s, respectively.

This result is a generalisation of the main result in [12] to the case of multi-recurrences defined over a number field. Observe that in the case k = 1 and G_{n}^{(i)} a power sum with integral roots, conditions (7) and (9) are automatically satisfied. Some more remarks are in order.

Remark 1. We remark that this result is only a partial generalisation of the main result in [5]. The restriction comes from the condition that we only consider those solutions with min{n_{1}, …, n_{k}} ≥ γ · max{n_{1}, …, n_{k}} for a certain γ < 1. E.g. for the equation y^{2} = 1 + 2^{n} + 4^{m} the theorem can be applied (with ν = 2) but gives the conclusion only for all (m, n) with min\{m, n\} > \frac{1}{2} max\{m, n\}. Let us mention here that the equation y^{2} = 1 + 2^{n} + 2^{m} was completely solved by Szalay [43].

The most critical open example to be solved completely is y^{2} = 1+3^{n}+2^{m}. Here our theorem gives the result (with ν = ∞) only for all (m, n) with min\{m, n\} > \frac{log 2}{log 3} max\{m, n\} (compare with the remark in [7, p. 79]).

Remark 2. We mention that the assumption of (9) as well as min{n_{1}, …, n_{k}} ≥ γ · max{n_{1}, …, n_{k}} assure in some sense that we have a domiant root, namely that we do not have two different exponential terms which have the same absolute value ν for all (n_{1}, …, n_{k}). In this sense they are not new restrictions, but suitable generalisations of the old.

In fact Theorem 1 is obtained by using the following result which is interesting on its own.

Theorem 2. Let d ≥ 2 and g(x_{1}, …, x_{d}, z) ∈ K[x_{1}, …, x_{d}, z] such that deg_{z} g = deg g(0, …, 0, z) = d. Assume further that

\frac{∂g}{∂z} (0, …, 0, z_{i}) ≠ 0,

where z_{i} are the roots of g(0, …, 0, z) for i = 1 …, d. Let G_{n}^{(1)}, …, G_{n}^{(d)} be multi-recurrences with coefficients and roots in K and assume that |α|_{ν} < 1 for every root α. Then there exist finitely many recurrences H_{n}^{(1)}, …, H_{n}^{(s)} with algebraic coefficients and algebraic roots and an effectively computable constant C < 1 such that for every fixed C < γ < 1 and for all solutions (n_{1}, …, n_{k}, z) ∈ ℕ^{k} × O_{S} of the equation

g (G_{n}^{(1)}, …, G_{n}^{(d)}, z) = 0

with min{n_{1}, …, n_{k}} ≥ γ · max{n_{1}, …, n_{k}} we either have

H_{n}^{(i)} = 0 or z = H_{n}^{(j)}

for certain 1 ≤ i, j ≤ s, respectively.

Some more remarks are in order.

Remark 3. We give an impression what C in Theorem 2 looks like. For α = (α_{1}, …, α_{k}) ∈ K^{k} let S(α) be the set of all indices such that |α_{i}|_{ν} < 1 and L(α) all indices with |α_{i}|_{ν} ≥ 1. Then

C := max \{\frac{∑_{i∈L(α)} log |α_{i}|_{ν}}{∑_{i∈S(α)} log |α_{i}|_{ν}^{−1}} : α root of one of the G_{n}^{(i)}, i = 0, …, d\} .

This choice assures that |α^{n}|_{ν} → 0 with min{n} → ∞. Observe that if additionally |α_{i}|_{ν} ≤ 1 for every i = 1, …, k, then C = 0 and thus every 0 < γ < 1 can be taken.

Remark 4. For the proof we use a recent very powerful result by Corvaja and Zannier [7] which is itself a consequence of the Subspace Theorem by W.M. Schmidt (cf. [36, 37]). We remark that by using quantitative versions of the Subspace Theorem (e.g. due to Evertse [9]) it is possible to give an explicit upper bound for the number of recurrences H_{n} in the statement above.

Remark 5. By assuming non-degeneracy conditions for the roots of the multi-recurrences G_{n}^{(i)} we could get rid of the first conclusion and get a finite set of possible solutions instead. We also remark that we cannot say anything on the set of n’s in the second part of the conclusion as in the linear case not even in simple cases (compare with [38, Conjecture 11.6]).

Remark 6. In fact all the solutions of the form y = H_{n} in the theorem above come from a polynomial solution h(x_{1}, …, x_{d}) ∈ K[x_{1}, …, x_{d}] of the equation g(x_{1}, …, x_{d}, y) = 0, hence

g(x_{1}, …, x_{d}, h(x_{1}, …, x_{d})) = 0

as functions in K[uH] for a coset uH ⊂ G_{m}^{d}(K). This reduces the problem of finding these infinite families of solutions and deciding whether they exist at all to a question of polynomial functions in G_{m}^{d}(K).

We now turn to a special case which will follow immediately from Theorem 2 and which was considered earlier in the literature.

Corollary 1. Let d ≥ 2 and G_{n_{1}}^{(1)}, …, G_{n_{k}}^{(k)} be linear recurrences defined as in (6) with (7). Let 0 < γ < 1 be fixed. Then there exist finitely many recurrences H_{n}^{(1)}, …, H_{n}^{(s)} with algebraic coefficients and algebraic roots such that for all solutions (n, y) = (n_{1}, …, n_{k}, y) ∈ ℕ^{k} × ℤ of the equation

G_{n_{1}}^{(1)}G_{n_{2}}^{(2)} ⋯ G_{n_{k}}^{(k)} = y^{d}

with min{n_{1}, …, n_{k}} ≥ γ · max{n_{1}, …, n_{k}} we either have

H_{n}^{(i)} = 0 or y = H_{n}^{(j)}

for certain 1 ≤ i, j ≤ s, respectively.

At the end we consider the case of two exponential variables, i.e. k = 2. Here we prove the following generalisation of the main result in [12].

Corollary 2. Let d ≥ 2 and G_{n}^{(0)}, G_{n}^{(1)}, …, G_{n}^{(d)} be linear recurrences as defined in (3) and let G_{n}^{(0)} = 1. Let α be given by (4). Moreover, let H_{m} = b_{1}β^{m} + b_{2}β_{2}^{m} + … + b_{s}β_{s}^{m} with algebraic b_{1}, …, b_{s} and integers β > β_{2} > … > β_{s}. Assume that

D (G_{n}^{(0)}, …, G_{n}^{(d)}) ≠ 0.

Then there exist finitely many multi-recurrences H_{(m,n)}^{(1)}, …, H_{(m,n)}^{(s)} with algebraic coefficients and algebraic roots such that for all solutions (m, n, y) ∈ ℕ^{2} × ℤ of the equation

y^{d} + G_{n}^{(1)}y^{d−1} + … + G_{n}^{(d)} = H_{m},

with \frac{m log β}{nd log α} ↛ 1 we either have

H_{(m,n)}^{(i)} = 0 or y = H_{(m,n)}^{(j)}

for certain 1 ≤ i, j ≤ s, respectively.

Observe that this does not follow just by an application of Theorem 2, since it would only hold for min\{m, n\} > \frac{d log α}{log β} max\{m, n\} or \frac{log β}{d log α} max\{m, n\} depending on α^{d} < β, α^{d} > β, respectively. For the proof we use Theorem 2 as well as the main result in [13]. We remark that this strategy is similar to that of the proof of the result in [5].

The major open problems in all the results of course are to remove the condition min{n_{1}, …, n_{k}} ≥ γ ·max{n_{1}, …, n_{k}} and the assumption on the existence of a single dominant root.

3. Proof of Theorem 1

We will reduce the assertion to the statement of Theorem 2. To do so we only have to show that under our assumptions the quantities γ_{1}, …, γ_{r} defined by (10) have |γ_{i}|_{ν} < 1. Then by applying Theorem 2 the statement follows. Observe that since we have assumed that all dominant roots in (6) are simple it follows that powers of n only appear together with some γ_{i}^{n} and therefore Theorem 2 is really applicable.

We assume that

α = ((\frac{α_{1}^{(l)}}{(α_{1}^{(0)})^{\frac{d−l}{d}}} )^{\frac{1}{l}} , …, (\frac{α_{k}^{(l)}}{(α_{k}^{(0)})^{\frac{d−l}{d}}} )^{\frac{1}{l}} )

for some 1 ≤ l ≤ d. Observe that by assumption (9) this is the only element in A with this property. Thus we have

|α|_{ν} = ∏_{i=1}^{k} |(\frac{α_{i}^{(l)}}{(α_{i}^{(0)})^{\frac{d−l}{d}}} )^{\frac{1}{l}} |_{ν} ≥ ∏_{i=1}^{k} |(\frac{α_{i}^{(j)}}{(α_{i}^{(0)})^{\frac{d−j}{d}}} )^{\frac{1}{j}} |_{ν}

for every 1 ≤ j ≤ d. It is clear that we only have to investigate how the dominant roots transform by using our variable transformation. The dominant root in the coefficient of z^{d} (that is a multi-recurrence) is clearly α^{d} (here and below the exponentiation is meant coordinatewise). The dominant root in the coefficient of z^{d−j} is

\begin{matrix}α & (d−j)n \\ (α_{1}^{(0)}) & \frac{d−j}{d} n \end{matrix} (α_{1}^{(j)})^{n} = (\frac{α_{i}^{(j)}}{(α_{i}^{(0)})^{\frac{d−j}{d}}} \begin{matrix}(α_{i}^{(l)}) & \frac{d−j}{l} \\ (α_{i}^{(0)}) & \frac{(d−l)(d−j)}{ld} \end{matrix} : i = 1, …, k)^{n} .

Thus for its valuation we have

∏_{i=1}^{k} |\frac{α_{i}^{(j)}}{(α_{i}^{(0)})^{\frac{d−j}{d}}} \begin{matrix}(α_{i}^{(l)}) & \frac{d−j}{l} \\ (α_{i}^{(0)}) & \frac{(d−l)(d−j)}{ld} \end{matrix} |_{ν} ≤ ∏_{i=1}^{k} |\begin{matrix}(α_{i}^{(l)}) & \frac{j}{l} \\ (α_{i}^{(0)}) & \frac{(d−l)j}{ld} \end{matrix} \begin{matrix}(α_{i}^{(l)}) & \frac{d−j}{l} \\ (α_{i}^{(0)}) & \frac{(d−l)(d−j)}{ld} \end{matrix} |_{ν}

= ∏_{i=1}^{k} |\begin{matrix}(α_{i}^{(l)}) & \frac{1}{l} \\ (α_{i}^{(0)}) & \frac{d−l}{ld} \end{matrix} |_{ν}^{d} = |α^{d}|_{ν}.

It follows that the valuation is at most that of α^{d} and equality can only appear if the root is equal to α^{d} by what we have said above (using condition (9)). Thus it follows that in (10) we indeed have - for all roots appearing in the multi-recurrences that are the coefficients of the polynomial in z and which are different from (1, …, 1)^{n} = 1, which we have denoted by γ_{1}, …, γ_{r}, - that

|γ_{i}|_{ν} < 1,

for all i = 1, …, r. Therefore the result follows once we have established Theorem 2. Observe that z is an S-integer since

y = \begin{matrix}α & n \\ ((α_{1}^{(0)})^{\frac{1}{d}} ) & n \end{matrix} z ∈ ℤ,

if S is chosen such that all components of (α_{1}^{(0)})^{\frac{1}{d}} and α are S-units. □

4. Proof of Theorem 2

In the sequel C_{1}, C_{2}, … will denote positive numbers depending only on g and on the coefficients and roots of G_{n}^{(1)}, …, G_{n}^{(d)}.

We start by mentioning that the solutions of the form (n, 0) are given by

H_{n} := g(G_{n}^{(1)}, …, G_{n}^{(d)}, 0) = 0.

Moreover, the equation is satisfied for every z ∈ O_{S} if

G_{n}^{(1)} = … = G_{n}^{(d)} = 0.

Therefore, we may restrict to solutions (n, z) ∈ ℕ^{k} × O_{S} where neither of these two possiblities occur. From now on we will look at a subsequence of all remaining solutions, which we will denote by (n, z_{n}) ∈ ℕ^{k} × O_{S} with n ∈ Σ ⊆ ℕ^{k}. We also remark that if min{n} = min{n_{1}, …, n_{k}} is bounded, then we proceed as follows: by considering several cases independently by fixing the finitely many choices of the variables n_{i} with n_{i} = min{n}, we can reduce the problem to a lower dimensional problem involving fewer variables, where for the remaining variables we have that the minimum goes to infinity. Thus we may at once assume that min{n} → ∞.

Without loss of generality we may also assume that

G_{n}^{(i)} = n^{a_{i}}γ_{i}^{n}

where a_{i} = (a_{1i}, …, a_{ki}) ∈ ℕ^{k} and γ_{i} ∈ K^{k} with |γ_{i}|_{ν} < 1 for i = 1, …, d. This can be achieved by using a suitable polynomial g̃ with additional variables instead of g which satisfies the same conditions as g.

Next we show that |γ_{i}|_{ν} < 1 implies that

|n^{a_{i}}γ_{i}^{n}|_{ν} ⟶ 0 for min{n} → ∞

(compare with Remark 2). For γ_{i} = (γ_{1i}, …, γ_{ki}) ∈ K^{k} let S(γ_{i}) be the set of all indices such that |γ_{ji}|_{ν} < 1 and L(γ_{i}) all indices with |γ_{ji}|_{ν} ≥ 1. Then

|γ_{i}^{n}|_{ν} ≤ ∏_{j∈S(γ_{i})} |γ_{ji}|_{ν}^{min{n}} ∏_{j∈L(γ_{i})} |γ_{ji}|_{ν}^{max{n}}

(12)  ≤ ( ∏_{j∈S(γ_{i})} |γ_{ji}|_{ν} ∏_{j∈L(γ_{i})} |γ_{ji}|ν^{\frac{1}{γ}} )^{min\{n\}} = C_{1}^{min\{n\}},

where C_{1} < 1. This is true for

γ > \frac{∑_{j∈L(γ_{i})} log |γ_{ji}|_{ν}}{∑_{j∈S(γ_{i})} log |γ_{ji}|_{ν}^{−1}}

where the number on the right hand side is < 1 since |γ_{i}|_{ν} < 1. From this we conclude that

|n^{a_{i}}γ_{i}^{n}|_{ν} ⟶ 0

if

γ > C := max \{\frac{∑_{j∈L(γ_{i})} log |γ_{ji}|_{ν}}{∑_{j∈S(γ_{i})} log |γ_{ji}|_{ν}^{−1}} : i = 0, …, d\} .

Observe that from here it is trivial that if we additionally have |γ_{ji}|_{ν} ≤ 1 for all j = 1, …, k, then C = 0 and the above conclusion is trivially true.

The sequence (z_{n})_{n∈Σ} must be bounded with respect to ν. This follows e.g. by the same argument as in [12, p. 162] since

g (n^{a_{1}}γ_{1}^{n}, …, n^{a_{d}}γ_{d}^{n}, z_{n}) = 0

and therefore all solutions (n, z_{n}) lie in the union of arbitrarily small neighborhoods of the solutions of

g(0, …, 0, z) = 0

at least if min{n} is large enough. Here we use that the leading coefficient of g with respect to z does not go to 0 in K_{ν} as min{n} → ∞.

Now we apply a suitable version of the implicit function theorem. The basic form of the implicit function theorem is the assertion that a function in d + 1 variables, of sufficient smoothness, satisfying an appropriate nondegeneracy condition, can be used to define one of the variables as a function of the other d variables. Here we will consider the implicit function theorem over a field of characteristic zero and with respect to the absolute value ν.

Theorem 3 (Implicit Function Theorem). Let g(X, Z) ∈ K[X, Z] be a polynomial. Suppose that

\frac{∂g}{∂Z} (0, z_{0}) ≠ 0,

where z_{0} ∈ K is a zero of g(0, Z) = 0. Then there exists a power series F (X) ∈ K[[X]] with F (0) = 0 and with a positive radius of convergence R with respect to the absolute value ν, i.e. F (x) converges for all x = (x_{1}, …, x_{d}) ∈ K^{d} with max{|x_{i}|_{ν} : i = 1, …, d} ≤ R, such that

g (X, z_{0} + F (X)) = 0.

Proof: First put h(X, Z) := g(X, Z+z_{0}) where z_{0} is a zero of g(0, Z) = 0. Now h is a polynomial in Z with coefficients in the number field K. Since

\frac{∂h}{∂Z} (0, 0) = \frac{∂g}{∂Z} (0, z_{0}) ≠ 0,

it follows by the implicit function theorem for formal power series (cf. [21, 22]) that there exists a unique power series \overline{F} (X) ∈ K[[X]] such that

h(X, \overline{F} (X)) = g(X, z_{0} + \overline{F} (X)) = 0

and \overline{F} (0) = 0. But now we can use Artin’s formal-to-analytic descent, namely [1, Theorem (1.2)], to conclude that there is a power series F (X) ∈ K[[X]], which has a non zero radius of convergence with respect to the valuation ν, which again satisfies

g(X, z_{0} + F (X)) = 0.

Moreover, all terms, up to some fixed but arbitrary index, of F and \overline{F} coincide. This proves what we have claimed. □

Using this theorem we get that each solution (n, z_{n}) with n sufficiently large (in terms of min{n}), say n ∈ R ⊆ ℕ^{k}, satisfies

(13)  z_{n} = z_{0} + ∑_{k∈ℕ^{d}\{0}}a_{k}n^{b_{k}}γ_{k}^{n}

for some z_{0} with g(0, …, 0, z_{0}) = 0 and where a_{k} ∈ K and

b_{k} = ∑_{i=1}^{d} k_{i}a_{i}, γ_{k} = ∏_{i=1}^{d} γ_{i}^{k_{i}}

where k = (k_{1}, …, k_{d}) ∈ ℕ^{d}. This is true at least if min{n} is large enough.

Now we use results from Diophantine approximation to get to our conclusion. Especially we will use a recent result from [7, Theorem 1]. Before we can state it we need some more notations.

We denote by ℂ_{ν} a completion of an algebraic closure of K_{ν}. We also define the S-height of a non zero element x ∈ K to be

h_{S}(x) = ∑_{v∉S} max{0, log |x|_{v}}.

For S-integers this height vanishes. For a vector x = (x_{1}, …, x_{k}) ∈ K^{k}\{0}, we define h(x) as the usual projective logarithmic height. We also denote by ĥ(x) := ∑_{i=1}^{k} h(x_{i}). In the following we will view points x with non zero coordinates in K as points of G_{m}^{k}(K), so operations are to be understood coordinatewise.

In the following statement we use the symbols “little o” and “big O” in the usual way.

Theorem 4 (Corvaja and Zannier). Let F (X) = ∑_{i} a_{i}X^{i} be a power series with algebraic coefficients in ℂ_{ν} converging in a neighborhood of the origin in ℂ_{ν}. Let S be a finite set of absolute values of K containing the archimedean ones. Let x_{h} = (x_{h1}, …, x_{hk}), h = 1, 2, …, be a sequence in (K\{0})^{k}, tending to zero in K_{ν}^{k} and such that F (x_{h}) is defined and belongs to K. Suppose that:

(i) For i = 1, …, k, we have h_{S}(x_{hi}) + h_{S}(x_{hi}^{−1}) = o(h(x_{hi})) as h → ∞. (ii) ĥ(x_{h}) = O(− log(max_{i} |x_{hi}|_{ν})). (iii) h_{S}(F (x_{h})) = o(h(x_{h})). (iv) h(F (x_{h})) = O(h(x_{h})).

Then there exist a finite number of cosets u_{1}H_{1}, …, u_{r}H_{r} ⊂ G_{m}^{k} such that {x_{h}}_{h∈ℕ} ⊂ ⋃_{i=1}^{r} u_{i}H_{i} and such that, for i = 1, …, r, the restriction of F (X) to u_{i}H_{i} coincides with a polynomial in K[X].

Proof: This is Theorem 1 in [7, p. 78]. □

We will apply the last theorem to the power series expansion given in (13). Therefore we denote by

x_{n} = (n^{a_{1}}γ_{1}^{n}, …, n^{a_{d}}γ_{d}^{n}) .

We have to verify (i)-(iv) in the theorem above. We enlarge S such that all components of γ_{i} for i = 1, …, k are S-units. Automatically, ν ∈ S.

We start with (i). Since n^{a_{i}} ∈ ℕ and the γ_{i}^{n} are S-units for all i = 1, …, d and n ∈ ℕ^{k} we immediately get

h_{S}(n^{a_{i}}γ_{i}^{n}) = 0, h_{S} ((n^{a_{i}}γ_{i}^{n})^{−1}) ≤ ∑_{j=1}^{k} a_{ji} log n_{j},

and also

h(n^{a_{i}}γ_{i}^{n}) ≥ ∑_{j=1}^{k} a_{ji} log n_{j} + min{n}C_{4}

and therefore (i).

Now we come to condition (ii), which in fact is the most crucial part and where we need our assumption on the dominant root. First we get

ĥ(x_{n}) = ∑_{i=1}^{d} h(n^{a_{i}}γ_{i}^{n}) ≤ C_{5} log max{n} + C_{6} max{n} ≤ C_{7} max{n}.

On the other side, since

max_{i}{|n^{a_{i}}γ_{i}^{n}|_{ν}} ≤ max{n}^{C_{8}}C_{9}^{min{n}}

by using (12) with C_{9} < 1, we get

− log(max_{i} |n^{a_{i}}γ_{i}^{n}|_{ν}) ≥ log C_{9}^{−1} min{n} − C_{8} log max{n} ≥ C_{10} min{n}.

Since we assume that max{n} · γ ≤ min{n} we immediately get

ĥ(x_{n}) ≤ C_{7} max\{n\} ≤ \frac{C_{7}}{γ} min\{n\} ≤ \frac{C_{7}}{γC_{10}} (− log(max_{i} |n^{a_{i}}γ_{i}^{n}|_{ν})) ,

and therefore (ii).

Condition (iii) is trivially true since z_{n} ∈ O_{S} by assumption, hence h_{S}(z_{n}) = 0. Therefore, we turn to (iv). It clearly follows that

h(z_{n}) ≤ C_{2} max_{i}{h(n^{a_{i}}γ_{i}^{n})} ≤ C_{3}h(n^{a_{1}}γ_{1}^{n}, …, n^{a_{d}}γ_{d}^{n})

since the height of the solution of a polynomial equation is bounded by the heights of the coefficients and we have min{n} ≥ γ · max{n}. This is the required upper bound for h(z_{n}).

From the theorem it therefore follows that there are finitely many polynomial h_{1}(x), …, h_{s}(x) ∈ K[x] such that for every n ∈ R there is an index 1 ≤ i ≤ s such that

z_{n} = h_{i}(x_{n}) = h_{i}(n^{a_{1}}γ_{1}^{n}, …, n^{a_{d}}γ_{d}^{n}).

Hence there exist finitely many multi-recurrences defined by

H_{n}^{(i)} := h_{i}(n^{a_{1}}γ_{1}^{n}, …, n^{a_{d}}γ_{d}^{n})

such that z_{n} = H_{n}^{(i)}. This is the claim of our theorem. □

5. Proof of the Corollaries

Proof of Corollary 1: Let us denote by α_{1,i} the dominant roots of G_{n}^{(i)} with respect to the absolute value ν for i = 1, …, k, respectively. Then it is clear that

α_{1} = (α_{1,1}, …, α_{1,k})

is the dominant root of the multi-recurrence given by G_{n_{1}}^{(1)} ⋯ G_{n_{k}}^{(k)}. We have to take

α = (α1,1^{\frac{1}{d}}, …, α1,k^{\frac{1}{d}}) .

Thus if we consider

\frac{1}{α^{(n_{1},...,n_{k})}} G_{n_{1}}^{(1)} ⋯ G_{n_{k}}^{(k)} = z^{d},

then for all roots γ of the multi-recurrence on the left hand side with γ ≠ (1, …, 1) we have |γ|_{ν} < 1 and in fact every component of γ is ≤ 1 with respect to the absolute value ν. Therefore, we can choose C = 0 by Remark 2. Moreover, condition (11) is clearly fulfilled. Consequently, the result follows by applying Theorem 2. □

Proof of Corollary 2: Let us assume that (m, n, y_{m,n}) is a sequence of solutions of the equation under consideration and that min{m, n} → ∞ (otherwise m or n is bounded on a subsequence of the sequence of solutions and the result follows from [12, Theorem 1, p. 154]). Since we assume that

\frac{m}{n} ↛ \frac{d log α}{log β} =: μ,

it means that we may choose 0 < ϵ < 1 small enough such that there is no solution with (1 − ϵ)μ < \frac{m}{n} < (1 + ϵ)μ. Observe that we may also assume μ ≠ 0 (since otherwise the left hand side of our equation is just a polynomial in y and this case is easy to handle). We have that α is given by

α = max_{i=1,...,d} \{(α_{1}^{(i)})^{\frac{1}{i}} \}

(observe that we are assuming that the polynomial in y is monic, i.e. G_{n}^{(0)} = 1). We will consider cases depending on whether

\frac{m}{n} ≤ ϵ, ϵ ≤ \frac{m}{n} ≤ (1 − ϵ)\frac{d log α}{log β}, (1 + ϵ)\frac{d log α}{log β} ≤ \frac{m}{n} ≤ \frac{1}{ϵ}, \frac{1}{ϵ} ≤ \frac{m}{n}.

Let us start with the first case. Here we have m ≤ ϵn. Therefore, we have β^{m} ≤ β^{ϵn}. Thus

|H_{m}| ≤ β^{ϵ′n} < α^{(d−1−δ)n}

for some ϵ′ > ϵ (to absorb the constant) and for

δ < \frac{(d − 1) log α − ϵ′ log β}{log α} .

Now the assertion follows by applying the main result in [13, Theorem 1, p. 168], where we considered inequalities of the form

|y^{d} + G_{n}^{(1)}y^{d−1} + … + G_{n}^{(d)}| < α^{(d−1−δ)n},

and proved that all such solutions have y parametrized by one of finitely many power sums (that are linear recurrences whose characteristic roots are all simple).

Next we consider the second case. It follows that ϵn ≤ m ≤ (1 − ϵ)μn. Therefore, we have

\frac{β^{m}}{α^{dn}} ≤ ( \underbrace{\frac{β^{(1−ϵ)μ}}{α^{d}}}_{=:ρ} )^{n}

where ρ < 1 since

(1 − ϵ)μ\frac{log β}{d log α} = 1 − ϵ < 1.

Thus, we use the variable substitution y = αz. Here the discriminant of the transformed equation is equal to D(G_{n}^{(1)}, …, G_{n}^{(d)}) ≠ 0. Hence, we can apply Theorem 2 (where we will have C = 0). Observe that for all \frac{m}{n} we have max{m, n} · γ ≤ min{m, n} with γ = ϵ if μ ≤ 1 and with γ^{−1} = max{ϵ^{−1}, (1 − ϵ)μ} if μ > 1 (and ϵ small enough such that (1 − ϵ)μ > 1) and therefore we get the conclusion in this case.

Now let us consider the third case. Here we have (1 + ϵ)μn ≤ m ≤ \frac{1}{ϵ}n and thus

\frac{α^{dn}}{β^{m}} ≤ ( \underbrace{\frac{α^{\frac{d}{(1+ϵ)μ}}}{β}}_{=:ρ} )^{m}

where ρ < 1 since

\frac{d}{(1 + ϵ)μ} \frac{log α}{log β} = \frac{1}{1 + ϵ} < 1.

This time we therefore use the variable substitution y = β^{\frac{m}{d}} z. We denote the transformed equation by g. Since g(0, …, 0, z) = z^{d} − b_{1} it follows that we can apply Theorem 2 again (once more we will have C = 0) and thus we get the conclusion in the same way as above.

Finally, we consider the last case. Here we have n ≤ ϵm. It is immediate that

\frac{α^{dn}}{β^{m}} ≤ ( \underbrace{\frac{α^{ϵd}}{β}}_{=:ρ} )^{m},

where ρ < 1. We use again the variable transformation y = β^{\frac{m}{d}} z. Let g be the resulting polynomial. Now we can use the Implicit Function Theorem 4 and Theorem 4 as we did in the proof of Theorem 2. Observe that the only places where we needed the condition max{m, n} · γ ≤ min{m, n} were to get that the γ_{i}^{(m,n)} converge to zero and to verify condition (ii) in Theorem 4. The first condition is trivially satisfied because of n ≤ ϵm. The second condition is also trivial here because of the fact that everything is bounded in terms of m only. Therefore, Theorem 4 together with the strategy of proof of Theorem 2 gives the result also in this final case. □

References

[1] M. Artin, ‘On the solutions of analytic equations’, Invent. Math. 5 (1968), 277-291.

[2] B. Brindza, K. Liptai and L. Szalay, ‘On products of the terms of linear recurrences’, Number Theory (eds. Győry, Pethő, Sós; Walter de Gruyter, Berlin - New York, 1998), 101-106.

[3] Y. Bugeaud, M. Mignotte and S. Siksek, ‘Classical and modular approaches to exponential Diophantine equations. I. Fibonacci and Lucas perfect powers’, Ann. of Math. (2) 163 (2006), 969-1018.

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

[5] P. Corvaja and U. Zannier, ‘On the diophantine equation f(a^{m}, y) = b^{n}’, Acta Arith. 94 (2002), 25-40.

[6] P. Corvaja and U. Zannier, ‘Some new applications of the Subspace Theorem’, Compos. Math. 131 (2002), no. 3, 319-340.

[7] P. Corvaja and U. Zannier, ‘S-unit points on analytic hypersurfaces’, Ann. Sci. École Norm. Sup. (4) 38 (2005), 76-92.

[8] G. R. Everest and A. J. van der Poorten, ‘Factorisation in the ring of exponential polynomials’, Proc. Amer. Math. Soc. 125 (1997), 1293-1298.

[9] J.-H. Evertse, ‘An improvement of the Quantitative Subspace Theorem’, Compos. Math. 101 (3) (1996), 225-311.

[10] C. Fuchs, ‘Exponential-polynomial equations and linear recurring sequences’, Glas. Mat. Ser. III 38 (58) (2003), 233-252.

[11] C. Fuchs, ‘Diophantine problems with linear recurrences via the Subspace Theorem’, Integers 5 (2005), #A8, 26pp.

[12] C. Fuchs and A. Scremin, ‘Polynomial-exponential equations involving several linear recurrences’, Publ. Math. Debrecen 65 (2004), 149-172.

[13] C. Fuchs and A. Scremin, ‘Diophantine inequalities involving several power sums’, Manuscripta Math. 115 (2004), 163-178.

[14] C. Fuchs and R. F. Tichy, ‘Perfect powers in linear recurring sequences’, Acta Arith. 107.1 (2003), 9-25.

[15] P. Kiss, ‘Differences of the terms of linear recurrences’, Studia Sci. Math. Hungar. 20 (1985), 285-293.

[16] P. Kiss, ‘Pure powers and power classes in the recurrence sequence’, Math. Slovaca 44 (1994), 525-529.

[17] P. Kiss, ‘Results concerning products and sums of terms of linear recurrences’, Acta Acad. Agriensis, Sectio Mathematica 27 (2000), 1-7.

[18] P. Kiss and F. Mátyás, ‘On products and sums of the terms of linear recurrences’, Acta Acad. Paed. Agriensis, Sectio Mathematicae 28 (2001), 3-11.

[19] P. Kiss and F. Mátyás, ‘Perfect powers from the sums of terms of linear recurrences’, Period. Math. Hungar. 42 (2001), 163-168.

[20] P. Kiss and F. Mátyás, ‘Products of the terms of linear recurrences’, Studia Sci. Math. Hungar. 37 (2001), 355-362.

[21] S. G. Krantz and H. R. Parks, A Primer of Real Analytic Functions (Second Ed., Birkhäuser, Boston, 2002).

[22] S. G. Krantz and H. R. Parks, The Implicit Function Theorem: History, Theory, and Applications (Birkhäuser, Boston, 2002).

[23] K. Liptai and L. Szalay, ‘Power classes of recurrence sequences’, Publ. Math. Hungar. 65 (2004), 421-428.

[24] F. Luca, ‘On the Diophantine equation x^{2} = 4q^{m} −4q^{n} +1’, Proc. Amer. Math. Soc. 131 (2003), 1339-1345.

[25] F. Luca, ‘The Diophantine equation x^{2} = p^{a} ± p^{b} + 1’, Acta Arith. 112 (2004), 87-101.

[26] F. Mátyás, ‘On the difference of perfect powers and sums of terms of linear recurrences’, Riv. Mat. Univ. Parma 3 (2000), 77-85.

[27] W. L. McDaniel and P. Ribenboim, ‘Square classes of Lucas sequences’, Portugal. Math. 48 (1991), 469-473.

[28] W. L. McDaniel and P. Ribenboim, ‘The square classes in Lucas sequences with odd parameter’, C. R. Math. Rep. Acad. Sci. Canada 18 (1996), 223-227.

[29] W. L. McDaniel and P. Ribenboim, ‘Square-classes in Lucas sequences having odd parameters’, J. Number Theory 73 (1998), 14-27.

[30] A. Pethő, ‘Diophantine properties of linear recursive sequences I’, Bergum, G. E. (ed.) et al., Applications of Fibonacci numbers. Volume 7: Proceedings of the 7th international research conference on Fibonacci numbers and their applications, Graz, Austria, July 15-19, 1996 (Kluwer Academic Publ., Dordrecht, 1998), 295-309.

[31] A. Pethő, ‘Diophantine properties of linear recursive sequences II’, Acta Math. Acad. Paed. Nyiregyháziensis 17 (2001), 81-96.

[32] A. J. van der Poorten, Some facts that should be better known, especially about rational functions, Number Theory and Applications (Banff, AB, 1988; Kluwer Acad. Publ., Dordrecht, 1989), 497-528.

[33] P. Ribenboim, ‘Square classes of Fibonacci and Lucas numbers’, Portugal. Math. 46 (1989), 159-175.

[34] P. Ribenboim, ‘Square classes of (a^{n} −1)/(a−1) and a^{n} +1’, Sichuan Daxue Xuebao 26 (1989), 196-199.

[35] R. S. Rumely and A. J. van der Poorten, ‘A note on the Hadamard kth root of a rational function’, J. Austral. Math. Soc. (Ser. A) 43 (1987), 314-327.

[36] W. M. Schmidt, Diophantine Approximation (Springer Verlag, LN 785, 1980).

[37] W. M. Schmidt, Diophantine Approximations and Diophantine Equations (Springer Verlag, LN 1467, 1991).

[38] W. M. Schmidt, ‘Linear Recurrence Sequences and Polynomial-Exponential Equations’, in: Diophantine Approximation (F. Amoroso, U. Zannier eds.), Proc. of the C.I.M.E. Conference, Cetraro (Italy) 2000 (Springer-Verlag, LN 1819, 2003).

[39] 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.

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

[41] T. N. Shorey and R. Tijdeman, Exponential Diophantine Equations (Cambridge University Press, Cambridge, 1986).

[42] L. Szalay, ‘A note on the products of the terms of linear recurrences’, Acta Acad. Paed. Agriensis 24 (1997), 47-53.

[43] L. Szalay, ‘The equations 2^{n}±2^{m}±2^{l} = z^{2}’, Indag. Math. (N.S.) 13 (2002), 131-142.

[44] U. Zannier, ‘A proof of Pisot’s dth root conjecture’, Ann. of Math. (2) 251 (2000), 375-383.

[45] U. Zannier, ‘Diophantine equations with linear recurrences. An overview of some recent progress’, J. Théor. Nombres Bordeaux 17 (2005), 423-435.

Department of Mathematics ETH Zurich Raemistrasse 101, HG G 13 CH-8092 Zurich, Switzerland E-mail: clemens.fuchs@math.ethz.ch