POLYNOMIAL–EXPONENTIAL EQUATIONS AND LINEAR RECURRENCES^{∗}

CLEMENS FUCHS

Abstract. Let K be an algebraic number field and let (G_{n}) be a linear recurring sequence defined by G_{n} = λ_{1}α_{1}^{n} + P_{2}(n)α_{2}^{n} + ⋯ + P_{t}(n)α_{t}^{n}, where λ_{1}, α_{1}, …, α_{t} are non-zero elements of K and where P_{i}(x) ∈ K[x] for i = 2, …, t. Furthermore let f(z, x) ∈ K[z, x] monic in x. In this paper we want to study the polynomial–exponential Diophantine equation f(G_{n}, x) = 0. We want to use a quantitative version of W. M. Schmidt’s Subspace Theorem (due to J.-H. Evertse [8]) to calculate an upper bound for the number of solutions (n, x) under some additional assumptions.

Address: Institut für Mathematik, Technische Universität Graz, Steyrergasse 30, 8010 Graz, Austria E-mail: clemens.fuchs@tugraz.at 2000 Mathematics Subject Classification: 11D45,11D61. Keywords: polynomial-exponential equations, linear recurrences, Subspace-Theorem

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

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

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

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

Then for n ≥ 0

(3)  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}). We shall be interested in linear recurring sequences (G_{n}), where G_{n} defined as in (3) for which P_{1}(n) is a non-zero constant, λ_{1} say. Thus

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

Date: February 3, 2003.

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

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 or identically zero on each of the d arithmetic progressions with 0 ≤ r < d. Therefore, restricting to nondegenerate recurring sequences causes no substantial loss of generality.

Let f(z, x) be a polynomial with algebraic coefficients, which is monic in x. In the present paper we deal with the Diophantine equation

(5)  f(G_{n}, x) = 0,

which was earlier investigated by several authors in the special case f(z, x) = Ex^{q} − z, E ∈ ℤ\{0}, which yields the Diophantine equation

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

A survey about this equation can be found in [9]. We cite here only those papers, which are of interest for us.

Let us mention that similar types of equations, namely

f(x, y, α^{x}) = 0 and f(x, y, α^{x}, β^{y}) = 0,

where f is a polynomial with complex coefficients and α, β are non-zero complex numbers, were studied by Schmidt [22] and Ahlgren [1, 2]. They showed that these equations can have solutions with arbitrarily large values of |x| only in the case when f and α, β are of a particularly simple form.

For a nondegenerate recurring sequence (G_{n}) of order 2 induced by a (rational) integral recurrence, it has been proved, independently, by Pethő [14] and Shorey and Stewart [24] that for the solutions x ∈ ℤ, |x| > 1 and q ≥ 2 of (6) max(|x|, q, n) is bounded by an effectively computable constant depending only on E and the sequence (G_{n}). Pethő [14] extended in fact 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, provided that the coefficients of the defining difference equation of G_{n} are coprime integers.

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

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

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 (6) can be bounded by an effectively computable constant which depends on E and the coefficients and initial values of the recurrence. Kiss [11] 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}).

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

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

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 (7) and assume

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

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. For second order recurrences (G_{n}) with |A_{2}| = 1 Nemes and Pethő [13] characterized all polynomials P for which the equation G_{n} = P (x) has infinitely many solutions (see also [16]). Kiss [11] and Shorey and Stewart [25] dealt with equation (8) for nondegenerate linear recurring sequences (G_{n}) of arbitrary order, under condition (9) and the additional assumptions that 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

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

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 [19], [21] to show that for every integer q ≥ 2 the equation

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

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. Tichy and the author [9] gave a quantitative version of the above result of Corvaja and Zannier.

Tichy and the author [9] also showed by combining their result with the previously mentioned result of Nemes and Pethő [12] that the following is true: Let (G_{n}) be a linear recurring sequence defined as above, 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.

Very recently, Pethő [17] used the above result of Corvaja and Zannier to show that there are only finitely many perfect powers in a third order linear recurring sequence (G_{n}), if we assume that the characteristic polynomial of (G_{n}) is irreducible and has a dominating root.

2. Results

Our main result is the generalization of the above quantitative result to the Diophantine equation f(G_{n}, x) = 0, where (G_{n}) is defined by (4). This will generalize and quantify a very recent result due to Corvaja and Zannier [5] (cf. Remark 1).

Theorem 1. Let K be an algebraic number field and let (G_{n}) be a nondegenerate linear recurring sequence defined by

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

where t ≥ 2, λ_{1} is a non-zero element of K, P_{i}(x) ∈ K[x] for all i = 2, …, t and where α_{1}, …, α_{t} are elements of K with 1 ≠ |α_{1}| > |α_{j}| for all j = 2, …, t. Let f(z, x) ∈ K[z, x] be monic in x and suppose that there do not exist non-zero algebraic numbers β_{j} and polynomials d_{j}(n) ∈ K̄[n] for j = 1, …, k such that

(11)  f(G_{n}, ∑_{j=1}^{k} d_{j}(n)β_{j}^{n}) = 0

for all n in an arithmetic progression. Then the number of solutions (n, x) ∈ ℕ × K of the equation

f(G_{n}, x) = 0

is finite and can be bounded by an explicitly computable number C depending on f and on the coefficients and the initial values of the recurrence.

Remark 1. Corvaja and Zannier showed in [5], under the restriction that the recurrence is simple, that the assumption of f(G_{n}, x) = 0 having infinitely many solutions implies that there exist d_{j}, β_{j} ∈ K̄\{0}, j = 1, …, k, and an arithmetic progression P such that

f(G_{n}, ∑_{j=1}^{k} d_{j}β_{j}^{n}) = 0, for n ∈ P.

Remark 2. Observe that one can effectively determine whether there do exist non-zero numbers β_{j} ∈ K̄ and polynomials d_{j}(n) ∈ K̄[n] for j = 1, …, k such that (11) holds for all n in an arithmetic progression or not (see [5]). The following example shows that this condition is necessary: let

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

and f(z, x) = x^{2} − z. The coefficients and roots have the desired properties, but

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

so f(G_{2k}, 18^{k} + 2^{k}) = 0 for all k ∈ ℕ. Another much simpler example is obtained by taking f(z, x) = x − z.

Remark 3. We want to note that the above assumption (11) also means (for k = 0) that f(z, 0) = 0 does not hold identically or equivalently x is not a divisor of f(z, x). For example f(z, x) = x − z · x, which yields solutions (n, 0) ∈ ℕ^{2} for all n ∈ ℕ, is excluded.

Remark 4. Let us mention that the condition on the dominant root α_{1} is crucial. The proof of the theorem heavily depends on that assumption.

Remark 5. For simplicity we have introduced the condition that f(z, x) is monic in x. There is no problem at all, if we assume that the leading coefficient of f with respect to x does not depend on z. Moreover, it is a well-known trick how to get rid of this assumption (with a corresponding modification of the theorem); namely we may replace f(z, x) with the polynomial a(z)^{d−1}f(z, x/a(z)), where a(z), d is the leading coefficient, the degree respectively of f with respect to x.

Next we want to state some conclusion concerning special cases of the above result.

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

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

where t ≥ 2, λ_{1} is a non-zero rational number, P_{i}(x) ∈ ℚ[x] for all i = 2, …, t and where α_{1}, …, α_{t} are rational numbers with 1 ≠ |α_{1}| > |α_{j}| for all j = 2, …, t. Let P (x) ∈ ℚ[x] be monic and suppose that there do not exist non-zero algebraic numbers β_{j} and polynomials d_{j}(n) ∈ ℚ̄[n] for j = 1, …, k such that

(12)  G_{n} = P ( ∑_{j=1}^{k} d_{j}(n)β_{j}^{n})

for all n in an arithmetic progression. Then the number of solutions (n, x) ∈ ℕ × ℚ of the equation

G_{n} = P (x)

is finite and can be bounded by an explicitly computable number C depending on P and on the coefficients and the initial values of the recurrence.

Remark 6. The above corollary is also true, if we assume P (x) ∈ ℚ(x), say P (x) = f(x)/g(x), where f(x) is a monic polynomial.

Remark 7. Also the classical case P (x) = x^{q}, concerning the number of perfect powers in the linear recurring sequence (G_{n}) is included. So we get a generalization of the results stated in [9]. Observe that from [4] it follows that condition (12) is equivalent to the assumption that G_{n} is not equal to a perfect qth power for all n in an arithmetic progression (cf. also [29]).

Last we want to discuss some families of Diophantine equations related to the above types of equations.

Corollary 2. Let (G_{n}) be an integral nondegenerate linear recurring sequence with (4), where t ≥ 2, λ_{1} is a non-zero element of K = ℚ(α_{1}, …, α_{t}), P_{i}(x) ∈ K[x] for all i = 2, …, t and where α_{1}, …, α_{t} are algebraic integers with 1 ≠ |α_{1}| > |α_{j}| for all j = 2, …, t. Furthermore, suppose that there do not exist non-zero numbers β_{j} ∈ K̄ and polynomials d_{j}(n) ∈ K̄[n] for j = 1, …, k such that

(13)  G_{n} = ( ∑_{j=1}^{k} d_{j}(n)β_{j}^{n})^{q}

for all n in an arithmetic progression and for given q ≥ 2. Then the number of solutions (n, x, q) ∈ ℕ^{3} with n, x, q > 1 of the equation

G_{n} = x^{q}

is finite and can be bounded by an explicitly computable number C depending only on the coefficients and the initial values of the recurrence.

Remark 8. Observe that condition (13) can be verified effectively, because under the other assumptions one can calculate an upper bound for q first. Then condition (13) must only be verified for q smaller than this bound.

Corollary 3. Let (G_{n}) be an integral nondegenerate linear recurring sequence with (4), where t ≥ 2, λ_{1} is a non-zero rational element of K = ℚ(α_{1}, …, α_{t}), P_{i}(x) ∈ K[x] for all i = 2, …, t and where α_{1}, …, α_{t} are algebraic integers with 1 ≠ |α_{1}| > |α_{2}| > |α_{j}| for all j = 3, …, t and α_{1}, α_{2} multiplicatively independent. Let α_{2} ≠ ±1 and let T (x) be a polynomial with integer coefficients and degree r; we take r = 0 if T (x) is the zero polynomial. Furthermore, suppose that there do not exist non-zero numbers β_{j} ∈ K̄ and polynomials d_{j}(n) ∈ K̄[n] for j = 1, …, k such that

(14)  G_{n} = ( ∑_{j=1}^{k} d_{j}(n)β_{j}^{n})^{q} + T ( ∑_{j=1}^{k} d_{j}(n)β_{j}^{n})

for all n in an arithmetic progression and for given q ≥ 2. Then there are only finitely many integers n, x and q with n ≥ 0, q ≥ 1 and |x| > 1 for which

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

holds.

3. Auxiliary Results

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

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 decomposition 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

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

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 [8]. The following notations are 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 2. (Quantitative Subspace Theorem, Evertse) Let 0 < δ < 1 and consider the inequality for x ∈ K^{n}.

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

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 (16) 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 (16) satisfying H(x) < H belongs to S_{1} ∪ ⋯ ∪ S_{t_{2}}.

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

Theorem 3. (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 by

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

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

Finally, we need some results from the theory of algebraic functions fields, which can be found in the monographs of Eichler [7] and Iwasawa [10], namely the theory of Puiseux expansions.

Let K be an algebraic number field, which is generated over the field of rational numbers ℚ. We assume that f(x, y) is an absolutely irreducible polynomial in x and y, with coefficients in the algebraic number field K, that is f is irreducible over the algebraic closure K̄ of K. We denote by F the field obtained by adjoining a root of f(x, y) to K̄(x), the field of rational functions in x with coefficients in the algebraic closure of K. Then F is an algebraic function field over the algebraically closed field K̄ of characteristic 0.

Theorem 4. (Puiseux’s Theorem) Let F be an algebraic functions field over an algebraically closed field K̄ of characteristic 0, given by f(x, y) = 0. For simplicity we suppose f(x, y) to be monic in y. Let us denote by n = [F : K̄(x)] the degree of F over K̄(x). Then with every element ξ ∈ K there are associated r = r(ξ) ≤ n natural number e_{i} = e_{i}(ξ) whose sum is

e_{1} + ⋯ + e_{r} = n;

similar numbers e_{i}(∞) are associated with the symbol ξ = ∞. These numbers have the following meaning: Setting

(17)  z_{ξ} = x − ξ, z_{∞} = 1/x,

the irreducible equation f(x, y) = 0 satisfied by an arbitrary function y of F over K̄ has for solutions the r = r(ξ) power series

(18)  y_{i} = ∑_{k=v_{i}}^{∞} a_{ik}( \sqrt[e_{i}(ξ)]{z_{ξ}})^{k}, a_{iv_{i}} ≠ 0, i = 1, 2, …, r(ξ).

With a primitive e_{i}th root of unity ζ form

(19)  y_{ij} = ∑_{k} a_{ik}ζ^{jk}( \sqrt[e_{i}(ξ)]{z_{ξ}})^{k}, j = 0, …, e_{i}(ξ) − 1;

then the left side of f(x, y) = 0 is identical with

(20)  f(x, y) = ∏_{j,i}(y − y_{ij}).

The coefficients a_{ik} are elements of a finite field extension K′ of K, and their images under isomorphisms of K′ give permutations of the y_{ij} in (20). The power series have respective radii of convergence ≠ 0.

Let us mention that the theory of Puiseux expansions is equivalent to the valuation theory. The numbers e_{i}(ξ), i = 1, …, r(ξ) are called ramifications indices related to the place generated by z_{ξ} = x − ξ, respectively z_{∞} = 1/x in the rational function field K̄(x).

We also want to state an explicit form of the last theorem, which enables us to derive estimates for the coefficients of the Puiseux expansions of an algebraic function and which is due to Coates (cf. [3]).

We introduce the following notation first. If α is an algebraic number, then deg α, δ(α), h(α) denote respectively the degree of α, the least positive rational integer such that δ(α)α is an algebraic integer, and the maximum of the absolute values of the conjugates of α, and we put σ(α) = max{deg α, δ(α), h(α)}. Let f(x, y) be as above and let the maximum of the absolute values of the conjugates of the coefficients of f(x, y) be at most f, where f ≥ 2, and let f(x, y) have degree m and n in x and y, respectively. Put N = max{n, m, 3}.

Theorem 5. (Explicit Puiseux’s Theorem, Coates) Let F be an algebraic functions field over an algebraically closed field K̄ of characteristic 0, given by f(x, y) = 0. Let ξ ∈ K and A_{i} (1 ≤ i ≤ r = r(ξ)) be the valuations of F extending the valuation of K̄(x) defined by x − ξ, and let e_{i} be the ramification index of A_{i}. We write

y = ∑_{k=0}^{∞} w_{ik}(x − ξ)^{k/e_{i}}

for the Puiseux expansion of y at A_{i}. Then the coefficients w_{ik} (1 ≤ i ≤ r, k = 0, 1, …) are algebraic numbers, and the number field K′ obtained by adjoining ξ and these coefficients to K has degree at most (N deg ξ)^{N} over K. Further, K′ is generated over K by ξ and w_{ik} (1 ≤ i ≤ r, 0 ≤ k ≤ 2N^{4}). Finally, there exists a positive rational integer Δ such that Δ^{k+1}w_{ik} (1 ≤ i ≤ r, k = 0, 1, …) is an algebraic integer with

(21)  max{Δ^{k+1}, Δ^{k+1}h(w_{ik})} ≤ Λ^{k+1},

where Λ = (fσ(ξ))^{μ}, μ = (N^{4}n deg ξ)^{3N^{4}}.

Let Q_{i} (1 ≤ i ≤ r(∞)) be the valuations of F extending the valuation of K̄(x) defined by 1/x. Let e_{i} be the ramification index of Q_{i}, and let

y = (\frac{1}{x})^{−m} ∑_{k=0}^{∞} w_{ik} (\frac{1}{x})^{k/e_{i}}

be the expansion of y at Q_{i}. Then the coefficients are algebraic numbers, and the number field K′ obtained by adjoining them to K has degree at most N^{N} over K. Further K′ is generated over K by the w_{ik} (1 ≤ i ≤ r, 0 ≤ k ≤ 2N^{4}). Finally, there exists a positive rational integer Δ such that Δ^{k+1}w_{ik} (1 ≤ i ≤ r, k = 0, 1, …) is an algebraic integer with

(22)  max{Δ^{k+1}, Δ^{k+1}h(w_{ik})} ≤ Λ^{k+1},

where Λ = f^{μ}, μ = (N^{4}n)^{3N^{4}}.

The value Λ is called the Eisenstein constant, due to Eisenstein who first proved the qualitative statement from above. Let us mention that improvements on the Eisenstein constant (at least in special cases) can be found in [20, 6].

We want to remark that the proof of the last theorem yields an algorithm for the actual determination of the coefficients of the Puiseux expansion of an algebraic function. In fact, for the proof one constructs polynomials p_{i}(w) with coefficients in the field obtained by adjoining the first i coefficients of the Puiseux expansion in question, such that the (i+1)st coefficient is a root of p_{i}(w). From this sequence of polynomials everything follows (see [3]).

4. Proof of the Main Theorem

First of all we can assume that f(z, x) = 0 depends on z and x, otherwise the assertion of our Theorem 1 would be trivially true. We can also suppose without loss of generality that f(z, x) is absolutely irreducible. Otherwise we can find a finite extension field L of K such that f(z, x) splits into a product of absolutely irreducible factors in L[z, x]. Then we can proceed with each of those factors as below and sum up the number of solutions to get the final result. So let us denote by F the functions field obtained by adjoining a root of f(z, x) = 0 to K̄(z), where K̄ denotes the algebraic closure of K.

Moreover, we may assume that α_{1}, …, α_{t} generate together a torsion-free multiplicative group. Because otherwise, if q is the order of the torsion in the multiplicative group generated by the roots, then for each r = 0, 1, …, q −1, the recurrences G_{nq+r} have roots generating a torsion-free group. Thus, we can proceed by considering each of these cases separately and sum up the resulting bounds. Observe that by the assumption that the characteristic roots are nondegenerate, the number of characteristic roots of G_{nq+r} is always ≥ 2.

We work only in the case |α_{1}| > 1 and consider the Puiseux expansion at z = ∞ of the solution x = x(z) of f(z, x) = 0. The arguments in the case |α_{1}| < 1 are completely analogous and use the expansion at z = 0.

In the sequel C_{1}, C_{2}, … will denote positive numbers depending only on f(z, x) and on λ_{1} and on the P_{i}, α_{i}.

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

C_{2} = A(t, a) = e^{(7t^{a})^{8t^{a}}} ,

where a = max{deg P_{i} | i = 2, …, t}. Observe that this follows from the fact that (G_{n}) is nondegenerate. Consequently, we can restrict ourselves to solutions of the form (n, x) ∈ ℕ×K with x ≠ 0. These solutions are denoted by (n, x_{n}) ∈ ℕ × K with n ∈ Σ, where Σ is a set of positive integers.

Now by Puiseux’s Theorem 4 we can conclude that

f(z, x) = ∏_{j,i}(x − x_{ij}),

where

x_{ij} = ∑_{k=v_{i}}^{∞} a_{ik}ζ^{jk}(\frac{1}{z})^{\frac{k}{e_{i}}} ,

for j = 0, …, e_{i} − 1, i = 1, 2, …, r and where e_{1}, …, e_{r} are the ramification indices of the valuations extending 1/z to the function field F. Furthermore by the Explicit Puiseux’s Theorem 5 we get that all coefficients lie in a fixed finite extension field K′ of K and we have

h(a_{ik}ζ^{jk}) ≤ Λ^{k−v_{i}+1},

for j = 0, …, e_{i} − 1, i = 1, 2, …, r and where Λ denotes the Eisenstein constant. Therefore for each solution (n, x_{n}) of (5) we get

(23)  x_{n} = ∑_{k=w}^{∞} β_{k}G_{n}^{− \frac{k}{e}} ,

for some w, e and β_{k} with

|β_{k}| ≤ Λ^{k−w+1}

for all k = 1, 2, …, which lie in a fixed finite extension of K. In what follows we will only consider those n, lying in a subsequence R ⊆ Σ, for which the same expansion occurs. The final number is just the sum of all numbers obtained by all those expansions.

Let us remark that for n > C_{3} (which will be specified later) the above series converges absolutely; this is because

|G_{n}| = |λ_{1}α_{1}^{n} + … + P_{t}(n)α_{t}^{n}| = |λ_{1}||α_{1}|^{n}|1 + ∑_{j=2}^{t} \frac{P_{j}(n)}{λ_{1}} (\frac{α_{j}}{α_{1}} )^{n} | ≥

≥ |λ_{1}||α_{1}|^{n}|1 − \underbrace{∑_{j=2}^{t} |\frac{P_{j}(n)}{λ_{1}} | |\frac{α_{j}}{α_{1}} |^{n}}_{≤1/2 for n>C_{3}} | ≥ \frac{|λ_{1}|}{2}|α_{1}|^{n} ⟶ ∞,

because |α_{1}| > 1. Thus

∑_{k=w}^{∞} |β_{k}||G_{n}|^{−k/e} ≤ ∑_{k=w}^{∞} Λ^{k−w+1} (\frac{|λ_{1}|}{2}|α_{1}|^{n})^{−k/e} =

= Λ^{−w+1} ∑_{k=w}^{∞} ( \underbrace{Λ (\frac{|λ_{1}|}{2}|α_{1}|^{n})^{−1/e}}_{≤1/2 for n>C_{3}} )^{k} < ∞,

converges, if n > C_{3} is satisfied.

Since |α_{1}| > |α_{i}| for i = 2, …, t, we have binomial expansions

G_{n}^{− \frac{k}{e}} = λ_{1}^{− \frac{k}{e}} α_{1}^{− \frac{kn}{e}} (1 + ∑_{i=2}^{t} \frac{P_{i}(n)}{λ_{1}} (\frac{α_{i}}{α_{1}} )^{n})^{− \frac{k}{e}} =

= λ_{1}^{− \frac{k}{e}} α_{1}^{− \frac{kn}{e}} ∑_{r=0}^{∞} \binom{−\frac{k}{e}}{r} (∑_{i=2}^{t} \frac{P_{i}(n)}{λ_{1}} (\frac{α_{i}}{α_{1}} )^{n})^{r} ,

for some choice of the eth roots of λ_{1} and α_{1}, which we may assume to be fixed for all n ∈ R. Because of the fact that

|∑_{i=2}^{t} \frac{P_{i}(n)}{λ_{1}} (\frac{α_{i}}{α_{1}} )^{n}| ≤ \frac{g}{|λ_{1}|}n^{a}c^{n} < 1,

where c := max{|α_{j}/α_{1}| | j = 2, …, t} and g is t times the maximum of the absolute values of the coefficients of the P_{i}, i = 2, …, t, if n > C_{3}, the expansion converges again absolutely for large n.

Next we are going to approximate x_{n} by a finite sum extracted from the Puiseux expansion (23). We define

H_{n} := ∑_{k=w}^{H} β_{k}λ_{1}^{− \frac{k}{e}} α_{1}^{− \frac{kn}{e}} ∑_{r=0}^{H} \binom{−\frac{k}{e}}{r} (∑_{i=2}^{t} \frac{P_{i}(n)}{λ_{1}} (\frac{α_{i}}{α_{1}} )^{n})^{r} ,

where H ≥ 1 is an integer to be chosen later. We may write

H_{n} = ∑_{j=1}^{h} τ_{j}(n)γ_{j}^{n}, n ∈ R,

where the τ_{j}(n) ∈ K̄[n] and the γ_{j} are distinct and lie in the multiplicative group generated by α_{1}^{1/e} and α_{2}, …, α_{t}. Clearly H_{n} is nondegenerate, in fact the roots γ_{j} again generate a torsion-free group. Moreover, we have

(24)  h ≤ C_{4}(H) := \binom{t + H}{H}(H + 1 − w),

where C_{4}(H) means that the constant depends also on H.

We enlarge K at once and assume that it contains all the α_{i}^{1/e} and all the coefficients β_{j} in the Puiseux series. In particular, we may assume that K contains all the coefficients of τ_{j} and the γ_{j}.

Next we estimate the approximation error we make, when we approximate x_{n} through H_{n}. We have

|x_{n} − H_{n}| = |x_{n} − ∑_{k=w}^{H} β_{k}λ_{1}^{− \frac{k}{e}} α_{1}^{− \frac{kn}{e}} ∑_{r=0}^{H} \binom{−\frac{k}{e}}{r} (∑_{i=2}^{t} \frac{P_{i}(n)}{λ_{1}} (\frac{α_{i}}{α_{1}} )^{n})^{r}| ≤

≤ |∑_{k=w}^{H} β_{k}λ_{1}^{− \frac{k}{e}} α_{1}^{− \frac{kn}{e}} ∑_{r=H+1}^{∞} \binom{−\frac{k}{e}}{r} (∑_{i=2}^{t} \frac{P_{i}(n)}{λ_{1}} (\frac{α_{i}}{α_{1}} )^{n})^{r}| +

+| ∑_{k=H+1}^{∞} β_{k} \underbrace{λ_{1}^{− \frac{k}{e}} α_{1}^{− \frac{kn}{e}} ∑_{r=0}^{∞} \binom{−\frac{k}{e}}{r} (∑_{i=2}^{t} \frac{P_{i}(n)}{λ_{1}} (\frac{α_{i}}{α_{1}} )^{n})^{r}}_{=G_{n}^{−k/e}} | ≤

≤ ∑_{k=w}^{H} Λ^{k−w+1}|λ_{1}|^{− \frac{k}{e}} |α_{1}|^{− \frac{wn}{e}} 2(H + 1)^{H+1} |∑_{i=2}^{t} \frac{P_{i}(n)}{λ_{1}} (\frac{α_{i}}{α_{1}} )^{n}|^{H+1} +

+ ∑_{k=H+1}^{∞} Λ^{k−w+1} (\frac{|λ_{1}|}{2}|α_{1}|^{n})^{−k/e} ≤

≤ ∑_{k=w}^{H} Λ^{k−w+1}|λ_{1}|^{− \frac{k}{e}} |α_{1}|^{− \frac{wn}{e}} 2(H + 1)^{H+1} (\frac{g}{|λ_{1}|}n^{a}c^{n})^{H+1} +

+Λ^{−w+1} \frac{(Λ (\frac{|λ_{1}|}{2}|α_{1}|^{n})^{−1/e} )^{H+1}}{1 − \underbrace{Λ (\frac{|λ_{1}|}{2}|α_{1}|^{n})^{−1/e}}_{≤1/2 for n>C_{3}}} ≤

≤ 2Λ^{H−w+1}λ̃(H + 1)^{H+1}g^{H+1}n^{a(H+1)}|α_{1}|^{− \frac{wn}{e}} c̃^{n(H+1)},

where

λ̃ := max \{1, |λ_{1}|^{− \frac{w}{e} −H−1}, |λ_{1}|^{− \frac{H}{e} −H−1}, |λ_{1}|^{− \frac{H+1}{e}} \}

and c̃ := max{c, |α_{1}|^{−1/e}}. Observe that we have c̃ < 1. Moreover, observe that we have used

| ∑_{r=H+1}^{∞} \binom{−\frac{k}{e}}{r}z^{r}| ≤

≤ ∑_{r=H+1}^{∞} \frac{|k|}{er} (1 + \frac{|k|}{e}) (1 + \frac{|k|}{2e}) ⋯ (1 + \frac{|k|}{(r − 1)e}) |z|^{r} ≤

≤ ∑_{r=H+1}^{∞} (1 + \frac{|k|}{e})^{r} |z|^{r} ≤ ∑_{r=H+1}^{∞}(H + 1)^{r}|z|^{r} ≤ \frac{(H + 1)^{H+1}|z|^{H+1}}{1 − (H + 1)|z|} ≤

≤ 2(H + 1)^{H+1}|z|^{H+1},

if H > −w (which implies |k| ≤ H) and if

|z| ≤ \frac{g}{|λ_{1}|}n^{a}c^{n} ≤ \frac{1}{2(H + 1)} ≤ \frac{1}{2},

which is possible if

n > C_{3} :=

= max \{2\begin{matrix}log & \frac{2(H+1)g}{|λ_{1}|} \\ log & \frac{1}{c} \end{matrix} + 2 max \{\frac{a}{log \frac{1}{c}} log \frac{a}{log \frac{1}{c}} , 15\} ,

\frac{e log 2Λ − log \frac{|λ_{1}|}{2}}{log |α_{1}|} \},

to estimate the tail of the above series. Observe that we have used a Lemma of Pethő and de Weger (cf. [18],[27, Appendix]) to obtain the first part of the above lower bound.

For later purposes we need an estimate of |x_{n}|. For n larger than the constant C_{3} we obtain in the same fashion as above

(25)  |x_{n}| = |∑_{k=w}^{∞} β_{k}G_{n}^{− \frac{k}{e}} | ≤ 2Λ^{−w+1}g̃^{\frac{|w|}{e}} |α_{1}|^{\frac{n|w|}{e}} ,

where g̃ := max{1, |λ_{1}|, g}.

We choose H so that

(26)  c̃^{H+1}|α_{1}|^{− \frac{wn}{e} + \frac{|w|n}{e}} < 1.

To get this, we must have

H > max \{1, \frac{2|w| log |α_{1}|}{e log \frac{1}{c̃}} − 1, −w\} .

Observe that from now on H is fixed and therefore also h, τ_{i}(n), γ_{i}, i = 1, …, h are fixed. Also, we choose a finite set S so that it contains all infinite absolute values of K. Moreover we require that all the α_{j}, λ_{1} and all coefficients of the P_{j}(n), all the nonzero coefficients of f(z, x) are S-units, which means that the | · |_{v} of those values = 1 for each v ∉ S. In particular, with this choice all γ_{j} are S-units. Also, the G_{n} are S-integers, that is |G_{n}|_{v} ≤ 1 for each v ∉ S, and f(z, x) is monic in x; therefore, the x_{n} too are S-integers, in view of the equations f(G_{n}, x_{n}) = 0. We denote by s the cardinality of S. Clearly, it is possible to choose s ≥ h.

Let us introduce a notation: for a ∈ K we write

\overline{h}_{s}(a) = max\{|a|_{v} | v ∈ S\},

for the S-height of a. Observe that we have

\overline{h}_{s}(a) ≤ ∏_{v∈M_{K}} max\{1, |a|_{v}\} ≤ H(1, a).

For a polynomial p with coefficients in K, \overline{h}_{s}(p) denotes the maximum of the S-heights of the coefficients. In the same fashion, we define \overline{h}_{s}(p_{1}, …, p_{h}).

We shall apply Theorem 2, so let us define, for every v ∈ S, h + 1 independent linear forms in X := (X_{0}, …, X_{h}) as follows: put

L_{0,∞}(X) = X_{0} + X_{1} + ⋯ + X_{h}

and for v ∈ S, 0 ≤ i ≤ h, (i, v) ≠ (0, ∞) put

L_{i,v}(X) = X_{i}.

Here ∞ denotes the infinite absolute value, which coincides with the complex absolute value in the embedding of K in ℂ. We have

H(L_{i,v}) ≤ \sqrt{h + 1}

for v ∈ S, i = 0, …, h. Furthermore K(L_{i,v}) = K and therefore

[K(L_{i,v}) : K] = 1 ∀v ∈ S, i = 0, …, h.

Moreover, we have

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

which yields

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

For n ∈ P define the vectors x_{n} = (−x_{n}, τ_{1}(n)γ_{1}^{n}, …, τ_{h}(n)γ_{h}^{n}) ∈ K^{h+1} and consider the double product

∏_{v∈S} ∏_{i=0}^{h} \frac{|L_{i,v}(x_{n})|_{v}}{|x_{n}|_{v}} .

By putting

σ = −x_{n} + τ_{1}(n)γ_{1}^{n} + … + τ_{h}(n)γ_{h}^{n} = L_{0,∞}(x_{n}),

we can rewrite the double product as

|σ|_{∞} · ( ∏_{v∈S\{∞}} |x_{n}|_{v}) (∏_{v∈S} ∏_{i=1}^{h} |τ_{i}(n)γ_{i}^{n}|_{v}) (∏_{v∈S} |x_{n}|_{v})^{−(h+1)} .

Observe that x_{n} is an S-integer and that, due to our choice of S, the γ_{i}^{n} are S-units for i ≥ 1. In particular, this implies (27)

(∏_{v∈S} ∏_{i=1}^{h} |τ_{i}(n)γ_{i}^{n}|_{v}) = ∏_{v∈S} ∏_{i=1}^{h} |τ_{i}(n)|_{v} ≤ (aH + 1)^{hs}\overline{h}_{s}^{hs}(τ_{1}, …, τ_{h})n^{aHhs}

and

(28)  ( ∏_{v∈S\{∞}} |x_{n}|_{v}) = ∏_{v∉S} |x_{n}|_{v} · |x_{n}|_{∞} ≤ |x_{n}|,

where we have used the product formula (15) and (25). We want to remark that the τ_{i}(n) have degree at most aH. Therefore we get using the bound for the approximation error, (27) and (28)

∏_{v∈S} ∏_{i=0}^{h} \frac{|L_{i,v}(x_{n})|_{v}}{|x_{n}|_{v}} ≤ C_{5}n^{C_{6}}C_{7}^{n}c̃^{n(H+1)} (∏_{v∈S} |x_{n}|_{v})^{−(h+1)} ,

where

C_{5} := 4Λ^{H−2w+2}(aH + 1)^{hs} ((H + 1)g)^{H+1} λ̃g̃^{\frac{|w|}{e}} \overline{h}_{s}^{hs}(τ_{1}, …, τ_{h}),
C_{6} := a(H + Hhs + 1),
C_{7} := |α_{1}|^{− \frac{w}{e} + \frac{|w|}{e}} ,

respectively.

Last we need an upper bound for H(x_{n}). We have

H(x_{n}) ≤ ∏_{v∈S} |x_{n}|_{v} ≤ \sqrt{h + 1} ∏_{v∈S} max\{|x_{n}|_{v}, |τ_{1}(n)γ_{1}^{n}|_{v}, …, |τ_{h}(n)γ_{h}^{n}|_{v}\},

where we have used again our choice of S and the fact that the two norms on K^{h+1} are equivalent. We need an estimate for |x_{n}|_{v} and we derive it from the equation f(G_{n}, x_{n}) = 0. Observe that we trivially have an estimate

|G_{n}|_{v} ≤ t\overline{h}_{s}(λ_{1}, P_{2}, …, P_{t})n^{a}\overline{h}_{s}(α_{1}, …, α_{t})^{n}.

On the other hand, we can estimate the absolute value of the roots of an equation in terms of the absolute value of the coefficients. We finally obtain

|x_{n}|_{v} ≤ N^{2}\overline{h}_{s}(f)t^{N} \overline{h}_{s}(λ_{1}, P_{2}, …, P_{t})^{N}n^{aN} \overline{h}_{s}(α_{1}, …, α_{t})^{nN},

where N denotes the total degree of f(z, x). Moreover we have

|τ_{i}(n)γ_{i}^{n}|_{v} ≤ (aH + 1)\overline{h}_{s}(τ_{1}, …, τ_{h})n^{aH+1}\overline{h}_{s}(γ_{1}, …, γ_{h})^{n},

for all i = 1, …, h. Consequently we get

(29)  H(x_{n}) ≤ C_{8}n^{C_{9}}C_{10}^{n},

where s denotes the cardinality of S. Let us point out that the constants

C_{8} := \sqrt{h + 1} max\{N^{2}\overline{h}_{s}(f)t^{N} \overline{h}_{s}(λ_{1}, P_{2}, …, P_{t})^{N},
(aH + 1)\overline{h}_{s}(τ_{1}, …, τ_{h})\}^{s},
C_{9} := max{aN, aH + 1}s,
C_{10} := max\{\overline{h}_{s}(α_{1}, …, α_{t})^{N}, \overline{h}_{s}(γ_{1}, …, γ_{h}\}^{s}

do not depend on n.

We now choose 0 < δ < 1 so that

(30)  c̃^{H+1}C_{7}C_{10}^{δ} < 1.

This will be possible for small δ in view of (26), namely for

δ < \frac{log (c̃^{H+1}C_{7})^{−1}}{log C_{10}} .

In view of the bound for the double product we derived and (29), the verification of (16) of the Quantitative Subspace Theorem 2 will follow from

C_{5}n^{C_{6}} (c̃^{H+1}C_{7})^{n} < (C_{8}n^{C_{9}}C_{10}^{n})^{−δ} ,

which is the same as

n^{C_{6}+δC_{9}} (c̃^{H+1}C_{7}C_{10}^{δ})^{n} < (C_{5}C_{8}^{δ})^{−1} .

However, this latter inequality follows from (30) for

n ≥ C_{11} := 2\frac{log (C_{5}C_{8}^{δ}) + (C_{6} + δC_{9}) (log (C_{6} + δC_{9}) + log (c̃^{H+1}C_{7}C_{10}^{δ}))}{log (c̃^{H+1}C_{7}C_{10}^{δ})^{−1}},

(for a = 0 the formula is true with log(0) = 0) which follows again by a Lemma of Pethő and de Weger (cf. [18],[27, Appendix]).

Therefore, by the Quantitative Subspace Theorem 2, there exist finitely many non-zero linear forms Λ_{1}(X), …, Λ_{g}(X) with coefficients in K̄ and with

g ≤ C_{12} := (2^{60(h+1)^{2}} · δ^{−7(h+1)})^{s}(3 + log log 2\sqrt{h + 1}),

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

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

∑_{i=1}^{h} u_{i}τ_{i}(n)γ_{i}^{n} = 0, u_{i} ∈ K̄, i = 1, …, h.

By Theorem 3 this can hold for at most a finite number of n. More precisely, we can conclude that the number of those solutions can be bounded by a constant

C_{13} := A(h, aH) = e^{(7h^{aH})^{8h^{aH}}} ,

since the γ_{i} are nondegenerate.

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

(31)  x_{n} = ∑_{i=1}^{h} v_{i}τ_{i}(n)γ_{i}^{n}, v_{i} ∈ K̄, i = 1, …, h.

Substituting this into f(z, x) = 0 we get

(32)  f(G_{n}, ∑_{i=1}^{h} v_{i}τ_{i}(n)γ_{i}^{n}) = 0.

Equation (32) cannot hold identically because of the assumption of the Theorem. Moreover, the series staying on the left hand side of (32) is a nondegenerate linear recurring sequence. Hence,

|{n|n satisfies (32)}| < C_{14} := A(C_{15}, C_{16}),

where

C_{15} := \binom{t + N}{N} · \binom{h + N}{N} and C_{16} := a(H + 1)N

also in this case, because the left hand side of (32) defines a nondegenerate linear recurring sequence and the conclusion follows again by Theorem 3. Observe that from the assumption that the α_{1}, …, α_{t} generate a torsion-free group, we conclude the nondegeneracy.

Then the number of solutions of (5) can be bounded by

C_{2} + ∑_{i=1}^{r} ∑_{j=0}^{e_{i}−1} [C_{12}(C_{13} + C_{14}) + max{C_{3}, C_{11}}] ,

where the constants in the sum clearly can depend on i, j. This completes the proof. □

5. Proof of the Corollaries

Proof of Corollary 2.

This follows readily from Theorem 1 in form of Corollary 1 and a result, mentioned in the introduction, which is due to Shorey and Stewart [25, Theorem 3]. Let us remark that by Eisenstein’s criterion for absolutely irreducibility the polynomials f(z, x) = x^{q} − z are absolutely irreducible for all q. Moreover, observe that G_{n}−λ_{1}α_{1}^{n} ≠ 0, because of our assumption t ≥ 2. □

Proof of Corollary 3.

Let d be the degree of α_{1} over ℚ. Using a result of Shorey and Stewart [25, Corollary 1], also mentioned in the introduction, we can conclude that the number of solutions n, x and q with n ≥ 0, |x| > 1, and

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

of the equation

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

is finite. It remains to show that the number of solutions n, x and q with n ≥ 0, |x| > 1 and

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

is also finite. But this follows now from our Theorem 1. Observe that only for the solutions with small q, an upper bound for the number of solutions can be given. □

References

[1] S. Ahlgren, Polynomial-exponential equations in two variables, J. Number Theory 62 (1997), no. 2, 428-438.

[2] S. Ahlgren, Equations F (x, y, α^{x}) = 0, Topics in number theory (University Park, PA, 1997), 85-100, Math. Appl. 467, Kluwer Acad. Publ., Dordrecht, 1999.

[3] J. Coates, Construction of rational functions on a curve, Proc. Camb. Phil. Soc. 68 (1970), 105-123.

[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] P. Corvaja and U. Zannier, Some new applications of the Subspace Theorem, Compos. Math. 131 (2002), no. 3, 319-340.

[6] B. M. Dwork and A. van der Poorten, The Eisenstein constant, Duke Math. J. 65 (1992) no. 1, 23-43, Corrections: Duke Math. J. 76 (1994), no. 2, 669-672.

[7] M. Eichler, Introduction to the theory of algebraic numbers and functions, Academic Press, New York and London, 1966.

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

[9] C. Fuchs and R. F. Tichy, Perfect powers in linear recurring sequences, Acta Arith., to appear.

[10] K. Iwasawa, Algebraic Functions, Translations of Mathematical Monographs Vol. 118, American Mathematical Society, Providence, Rhode Island, 1993.

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

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

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

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

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

[16] A. Pethő, On the solutions of the equation G_{n} = P (x), Fibonacci Numbers and Their Applications, D. Reidel Publ. Comp. 1986, 193-201.

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

[18] A. Pethő and B. M. M. de Weger, Product of Prime Powers in Binary Recurrence Sequences I., Math. Comp. 47 (1986), 713-727.

[19] W. M. Schmidt, “Diophantine Approximation”, Springer Verlag, LNM 785, 1980.

[20] W. M. Schmidt, Eisenstein’s theorem on powers series expansions of algebraic functions, Acta. Arith. 56 (1990), no. 2, 161-179.

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

[22] W. M. Schmidt, Equations α^{x} = R(x, y), J. Number Theory 47 (1994), 348-358.

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

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

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

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

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

[28] H. Stichtenoth, Algebraic Function Fields and Codes, Springer-Verlag, Berlin, Heidelberg, 1993.

[29] U. Zannier, A proof of Pisot’s dth root conjecture, Ann. of Math. (2) 151, no. 1 (2000), 375-383.