DIOPHANTINE INEQUALITIES INVOLVING SEVERAL POWER SUMS

CLEMENS FUCHS^{∗} AND AMEDEO SCREMIN^{‡}

Abstract. Let E_{A} denote the ring of power sums, i.e. complex functions of the form

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

for some a_{i} ∈ ℂ and α_{i} ∈ A, where A ⊆ ℂ is a multiplicative semigroup. Moreover, let F (n, y) ∈ E_{A}[y]. We consider Diophantine inequalities of the form

|F (n, y)| < α^{n(d−1−ϵ)},

where α > 1 is a quantity depending on the dominant roots of the power sums appearing as coefficients in F (n, y), and show that all its solutions (n, y) ∈ ℕ × ℤ have y parametrized by some power sums from a finite set.

This is a continuation of the work of Corvaja and Zannier [4, 5, 6] and of the authors [10, 18] on such problems.

2000 Mathematics Subject Classification: 11D45,11D61. Keywords: polynomial-exponential Diophantine equations, linear recurring sequences, Subspace Theorem, power sums

1. Introduction

Let E_{A} denote the ring of power sums, i.e. complex functions on ℕ of the form

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

for some a_{i} ∈ ℂ and α_{i} ∈ A, where A ⊆ ℂ is a multiplicative semigroup. If K ⊆ ℂ is a field we define KE_{A} by the same formulas, but allowing a_{i} ∈ K. The a_{i} are called the coefficients of G_{n} and the α_{i} are called the roots.

It is well known that such a power sum G_{n} satisfies a certain linear recurring equation (see [10]). Namely, set

(1)  ∏_{i=1}^{t}(X − α_{i}) = X^{t} − A_{1}X^{t−1} − … − A_{t}

Date: June 30, 2004. ∗The first author was supported by the Austrian Science Foundation FWF, grant

S8307-MAT.

‡The second author was supported by Istituto Nazionale di Alta Matematica “Francesco Severi”, grant for abroad Ph.D.

for A_{1}, A_{2}, …, A_{t} ∈ ℂ. Then the sequence (G_{n}) satisfies the t-th order linear recurring relation

G_{n} = A_{1}G_{n−1} + … + A_{k}G_{n−k} for n = k, k + 1, …,

with initial values G_{0}, G_{1}, …, G_{k−1} ∈ K. We remark that the general solution of such a linear recurring relation is a “generalized” power sum being of the same form as above, but allowing the a_{i} to be polynomials in n and the c_{i} ∈ ℂ. Thus, we are considering linear recurring sequences (G_{n}), where all roots of the corresponding characteristic polynomial are simple.

Below, A will be usually ℤ; in that case we define E_{ℤ}^{+} the subring formed by those power sums having only positive roots, i.e. the roots belong to the semigroup ℕ. Working in this domain causes no loss of generality: this assumption may be achieved by writing n = 2m + r and considering the cases r = 0, 1 separately.

The power sum G_{n} is called nondegenerate, if no quotient α_{i}/α_{j} for 1 ≤ i < j ≤ t is equal to a root of unity. Observe that restricting to nondegenerate recurring sequences causes no substantial loss of generality.

In the present paper we are dealing with Diophantine problems, where power sums are involved. E.g. many Diophantine equations involving linear recurring sequences were studied earlier, for instance in the special case

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

A survey about this equation can be found in [14, 15] and in more general form in [8, 11, 10].

Also Diophantine inequalities were studied previously, we just mention a result due to Shorey and Stewart [19], who proved that for any fixed ϵ > 0 the inequality

|Ex^{q} − G_{n}| > |α_{1}|^{n(1−ϵ)},

where G_{n} ∈ E\overline{ℚ} (where \overline{ℚ} denotes the algebraic closure of ℚ) is nondegenerate, holds for all nonzero integers E, x, for n > 0, and for every nonzero integer q > q_{0}(G_{n}, P), where P is the greatest prime factor of E, assuming that Ex^{q} ≠ c_{1}α_{q}^{n} and that in G_{n} there is a root with largest absolute value. This result was obtained by the application of lower bounds for linear forms in logarithms of algebraic numbers due to Baker [1].

In 1998, a new development was started by Corvaja and Zannier [4]. They considered power sums defined by

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

where t ≥ 2, c_{1}, c_{2}, …, c_{t} are non-zero rational numbers, α_{1} > α_{2} > ⋯ > α_{t} > 0 are integers. They used Schmidt’s Subspace Theorem [16], [17] to show that for fixed ϵ > 0 and every integer q ≥ 2 there exist power sums H_{n}^{(1)}, …, H_{n}^{(s)} ∈ \overline{ℚ}E\overline{ℚ} such that all solutions (n, y) ∈ ℕ × ℤ of the Diophantine inequality

|y^{q} − G_{n}| ≪ |G_{n}|^{1− \frac{1}{d} −ϵ}

apart from finitely many, satisfy y = H_{n}^{(i)} for a certain i = 1, …, s. As a consequence, for every q ≥ 2 the equation G_{n} = x^{q} has only finitely many solutions, if we suppose that α_{1}, α_{2} are coprime.

From this point on two developments started. On the one hand more general Diophantine equations, where power sums (or linear recurring sequences) are involved were studied (e.g. cf. [5, 6]). Also quantitative aspects were handled in view of the existence of quantitative version of the Subspace Theorem (e.g. due to Evertse [7]) (cf. [11, 8]). On the other hand new results for Diophantine inequalities were obtained (e.g. [2, 9]).

Recently, the second author studied lower bounds for the quantity |F (G_{n}, y)|, where F (x, y) ∈ \overline{ℚ}[x, y] is absolutely irreducible, monic and of degree d ≥ 2 in y. He proved that for G_{n} ∈ \overline{ℚ}E_{ℤ} and for fixed ϵ > 0 there exists a finite set of power sums H_{n}^{(1)}, …, H_{n}^{(s)} ∈ E_{ℤ}^{+} such that every solution (n, y) ∈ ℕ × ℤ, apart from finitely many, of the Diophantine inequality

|F (G_{n}, y)| < |\frac{∂F}{∂y} (G_{n}, y)| · |G_{n}|^{−ϵ}

satisfies y = H_{n}^{(i)} for a certain i = 1, …, s.

Very recently, the authors considered Diophantine equations, where more than one power sum is involved [10]. The aim of the present paper is to generalize this result to Diophantine inequalities, where also more than one power sum G_{n} is involved.

First we need some notation. Let d ≥ 2 be an integer and let G_{n}^{(1)}, …, G_{n}^{(d)} ∈ \overline{ℚ}E_{ℤ}^{+}, i.e. we have

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

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

We are studying lower bounds for the quantity

|F (n, y)|,

where F ∈ E_{ℤ}^{+}[y]. This is equivalent to study bounds for

|y^{d} + G_{n}^{(1)}y^{d−1} + … + G_{n}^{(d)}|.

Now, we set (for a positive real determination of the roots)

α := max \{α_{1}^{(d)^{\frac{1}{d}}} , (α_{1}^{(d−1)})^{\frac{1}{d−1}} , (α_{1}^{(d−2)})^{\frac{1}{d−2}} , …, α_{1}^{(1)}\} = max_{i=1,...,d} (α_{1}^{(i)})^{\frac{1}{i}} .

Moreover, let

y = α^{n}z.

Then consider

(2)  \frac{1}{α^{dn}} ((α^{n}z)^{d} + G_{n}^{(1)}(α^{n}z)^{d−1} + … + G_{n}^{(d)}).

This is a polynomial in z with coefficients in \overline{ℚ}E_{A}, where A is the multiplicative group generated by

α and the roots of G_{n}^{(1)}, …, G_{n}^{(d)}.

Observe that all the roots which appear in the coefficients are ≤ 1, because of our construction and that the coefficient of z^{d} is 1 (cf. Lemma 2 in [10]). Let γ_{1}, …, γ_{r} denote the different roots of these power sums, which are strictly less than 1. Identifying the expressions γ_{i}^{n} in (2) by new variables x_{i}, we get a polynomial (linear in x_{1}, …, x_{r}) g(x_{1}, …, x_{r}, z) ∈ \overline{ℚ}[x_{1}, …, x_{r}, z] such that

(3) g(γ_{1}^{n}, …, γ_{r}^{n}, z) = \frac{1}{α^{dn}} ((α^{n}z)^{d} + G_{n}^{(1)}(α^{n}z)^{d−1} + … + G_{n}^{(d)}).

This polynomial is some kind of normal form for our problem. We denote by D(G_{n}^{(1)}, …, G_{n}^{(d)}) the discriminant of g with respect to z evaluated at (0, …, 0), i.e.

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

The main result of the authors in [10] was: Let d ≥ 2 and let G_{n}^{(1)}, …, G_{n}^{(d)} ∈ \overline{ℚ}E_{ℤ}^{+}. Assume that

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

Then there exist finitely many recurrences H_{n}^{(1)}, …, H_{n}^{(s)} with algebraic coefficients and algebraic roots, arithmetic progressions P_{1}, …, P_{s} such that for the set S of solutions (n, y) ∈ ℕ × ℤ of the equation

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

we have

S = ⋃_{i=1}^{s}{(n, H_{n}^{(i)}) : n ∈ P_{i}} ∪ M,

where M is a finite set. In fact, they also allowed the coefficient of y^{d} in the equation above to be a power sum G_{n}^{(0)}, which leads to another possible “trivial” infinite family of solutions, but for simplicity we will always assume the above situation in this paper.

2. Results

From the discussion above we are searching for an exponential lower bound for the quantity

(5)  |y^{d} + G_{n}^{(1)}y^{d−1} + … + G_{n}^{(d)}|

(in terms of α to some power k). In the following we divide ℕ × ℤ in two regions depending on whether |y| is above or below the curve cα^{n}, where

(6)  c := ∑_{i=1}^{d} |a_{1}^{(i)}| + 1.

In fact the behavior of (5) depends on the region where we are looking for solutions. First it is easy to get the following statement.

Proposition 1. Let d ≥ 2, G_{n}^{(1)}, …, G_{n}^{(d)} ∈ \overline{ℚ}E_{ℤ}^{+}. Let

U = {(n, y) ∈ N × ℤ : |y| > cα^{n}} .

Then the Diophantine inequality

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

has only finitely many solutions (n, y) ∈ U.

Remark 1. We mention that the result is not true if the exponent on the right hand side increases, i.e. the exponent is best possible. Let us consider, for a given ϵ > 0, the Diophantine inequality

|y^{3} − a^{n}| < α^{3n(1+ϵ)},

where α = a^{\frac{1}{3}} , a > 1. We have c = 2. Putting

y_{n} = ⌊2a^{\frac{n}{3}} + 1⌋ ,

we have

|y_{n}^{3} − a^{n}| < 8a^{n} < a^{n(1+ϵ)}

for large n.

In the lower part of the plane, i.e. in L = {(n, y) ∈ ℕ × ℤ : |y| ≤ cα^{n}}, we cannot expect to get just finitely many solutions, in view of the results (cf. [10]) on the equation

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

which can have a functional solution.

Our main result is the following characterization of the solutions:

Theorem 1. Let d ≥ 2, G_{n}^{(1)}, …, G_{n}^{(d)} ∈ \overline{ℚ}E_{ℤ}^{+}. Assume that

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

Finally, let ϵ > 0. Then there exist finitely many recurrences H_{n}^{(1)}, …, H_{n}^{(s)} ∈ \overline{ℚ}E\overline{ℚ} such that all the solutions (n, y) ∈ ℕ × ℤ of the Diophantine inequality

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

except finitely many, have y = H_{n}^{(i)} for some i = 1, …, s. Moreover, the set of natural numbers n such that (n, y) is a solution of the inequality is the union of a finite set and a finite number of arithmetic progressions.

Remark 2. Observe that for G_{n}^{(1)} = … = G_{n}^{(d−1)} = 0 and G_{n}^{(d)} = −G_{n} ∈ E_{ℤ}^{+} we get the conclusion for the inequality

|y^{d} − G_{n}| < α^{n(d−1−ϵ)} = α_{1}^{n(1− \frac{1}{d} −ϵ′)},

where α_{1} is the dominant root of G_{n}, i.e. the result of Corvaja and Zannier [4]. This also shows (cf. Remark 2, page 321 in [4]) that the exponent d − 1 − ϵ in Theorem 1 is best possible.

Remark 3. Consider

G_{n}^{(1)} = p_{1}(G_{n}), G_{n}^{(2)} = p_{2}(G_{n}), …, G_{n}^{(d)} = p_{d}(G_{n}),

where p_{j}(x) ∈ \overline{ℚ}[x] are polynomials of degree i_{j} for j = 1, …, d and where G_{n} ∈ \overline{ℚ}E_{ℤ}. Let α_{1} denote the dominant root of G_{n}. Then,

α = max \{α1^{\frac{i_{d}}{d}} , α1^{\frac{i_{d−1}}{d−1}} , …, α_{1}^{i_{1}}\} ≥ α1^{\frac{1}{d}} .

We get our conclusion for the inequality

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

In comparison the result in [18] implies the same conclusion only for

|y^{d} + G_{n}^{(1)}y^{d−1} + … + G_{n}^{(d)}| < α_{1}^{n(1− \frac{1}{d} −ϵ)}.

This means that although the exponent in the result in [18] is best possible, the upper bound is not (and this is clear, because it does not take care of the special structure of the polynomials p_{1}, …, p_{d}). Therefore, Theorem 1 above is an improvement of this result. Observe that the upper bounds are equal only in the case

G_{n}^{(1)} = a_{1}, …, G_{n}^{(d−1)} = a_{d}, a_{1}, …, a_{d} ∈ \overline{ℚ}

which is more or less the case from Remark 2 above.

Remark 4. As we use the Implicit Function Theorem as our driving tool, it is clear that condition (4) is equivalent to

(4) ⟺ g(0, …, 0, z) has only simple roots ⟺

⟺ \frac{∂g}{∂z} (0, …, 0, z_{i}) ≠ 0, i = 1, …, d,

where z_{i} are the roots of g(0, …, 0, z). Note that a similar condition already appeared in the main result in [5].

Remark 5. Observe that it is easy to verify whether the inequality has infinitely many solutions or not (cf. [18, Remark 5.1] and [10, Remark 2]).

As in [18] we get as a simple application of our main theorem the following result, which generalizes the result in [10]:

Corollary 1. Let d ≥ 2, G_{n}^{(1)}, …, G_{n}^{(d)} ∈ \overline{ℚ}E_{ℤ}^{+} not all constant. Moreover, let f(x) ∈ ℤ[x] be a non constant polynomial. Assume that

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

Then the Diophantine equation

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

has only finitely many solutions (n, y) ∈ ℕ × ℤ.

Moreover, we get the following result, which looks quite interesting: Let N_{y}(n) denote the number of solutions of the Diophantine inequality

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

for fixed n. Obviously, we have N_{y}(n) < ∞ for all n ∈ ℕ, because the left hand side of the above inequality goes to ∞ as |y| becomes large. Surprisingly, the above result implies that there exists a uniform upper bound not depending on n.

Corollary 2.

N_{y}(n) ≤ C,

where C is a constant which does not depend on n.

Remark 6. Moreover, observe that the constant C is effectively computable in view of the existence of quantitative versions of the Subspace Theorem, e.g. due to Evertse [7].

3. Auxiliary results

The proof of our theorem depends on a technical result due to Corvaja and Zannier [6, Theorem 4], which is derived as a consequence from the famous Subspace Theorem of W. Schmidt (cf. [16, 17]).

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 note by | · |_{v} a continuation of it to \overline{ℚ} and normalize it “with respect to K”: according to this normalization, for x ∈ K^{∗} the absolute logarithmic Weil height is

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

and the Product formula

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

holds. We note that these conditions uniquely determine our normalizations. We also define the S-height of a non zero element x ∈ K^{∗} to be

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

For S-integers this height vanishes, so it measures ”how far” x is from being an S-integer.

For a vector x = (x_{0}, x_{1}, …, x_{n}) ∈ K^{n+1}\{0}, (n ≥ 1), we define h(x) as the usual projective logarithmic height. Also, we denote by ĥ(x), the sum of the h(x_{i}), 0 ≤ i ≤ n. Moreover, we put, for an absolute value v,

∥x∥_{v} := max_{1≤i≤n}{|x_{i}|_{v}}.

We use H, H_{S} and Ĥ for the exponential heights.

Theorem 2 (Corvaja and Zannier). Let K be a number field, S a finite set of absolute values of K containing all the archimedean ones, v be an absolute value from S, ϵ be a positive real number, N ≥ 0 an integer. Finally, let c_{0}, …, c_{N} ∈ \overline{K}^{∗}. For δ > (N +2)ϵ, there are only finitely many (N +1)-tuples w = (w_{0}, …, w_{N}) ∈ (K^{∗})^{N+1} such that the inequalities

(i)  h_{S}(w_{i}) + h_{S}(w_{i}^{−1}) ≤ ϵh(w_{i}), for i = 1, …, N
(ii)  |c_{0}w_{0} + c_{1}w_{1} + … + c_{N}w_{N}|_{v} < (H(w_{0})H_{S}(w_{0})^{N+1})^{−1} Ĥ(w)^{−δ}

hold and no subsum of the c_{i}w_{i} involving c_{0}w_{0} vanishes.

Our second tool is the Implicit Function Theorem. The basic form of the Implicit Function Theorem is the assertion that a function in n variables, of sufficient smoothness, satisfying an appropriate nondegeneracy condition, can be used to define one of the variables as a function of the other n − 1 variables. Here we will consider the implicit function theorem in the real analytic category (see [12], page 35 and [13]). We will use the following notation: a multiindex α is an element of ℕ^{m}. Set

|α| = |α_{1} + … + α_{m}|.

We will write 0 to mean the multiindex (0, …, 0).

Theorem 3 (Implicit Function Theorem). Suppose the power series

F (x_{1}, …, x_{r}, y) = ∑_{|α|≥0,k≥0} a_{α,k}x_{1}^{α_{1}} ⋯ x_{r}^{α_{r}}y^{k}

is absolutely convergent for |x_{1}| + … + |x_{r}| ≤ R_{1}, |y| ≤ R_{2}. If

a_{0,0} = 0 and a_{0,1} ≠ 0

then there exist r_{0} > 0 and a power series

(10)  f(x_{1}, …, x_{r}) = ∑_{|α|>0} c_{α}x_{1}^{α_{1}} ⋯ x_{r}^{α_{r}}

such that (10) is absolutely convergent for |x_{1}| + … + |x_{r}| ≤ r_{0} and

F (x_{1}, …, x_{r}, f(x_{1}, …, x_{r})) = 0.

Moreover: if the coefficients of F are algebraic, then the coefficients of f are also algebraic.

We mention once again the lemma from [10] that assures that the construction leading to the polynomial g appearing in (3) has the properties we have claimed.

Lemma 1. Let G_{n}^{(1)}, …, G_{n}^{(d)} and α be as in the Introduction. Then the dominant root in

(α^{n}z)^{d} + G_{n}^{(1)}(α^{n}z)^{d−1} + … + G_{n}^{(d)}

is α^{d} and it appears as coefficient of z^{d} and as coefficient of z^{d−k} for all indices k with

α = α_{1}^{(k)^{\frac{1}{k}}} ,

i.e. for all indices where the maximum in the definition of α appears.

This is Lemma 2 in [10]. The additional statement can be found as a remark at the end of the proof in [10].

4. Proof of Proposition 1

We will prove the statement by contradiction. Let us assume that the inequality

|y^{d} + G_{n}^{(1)}y^{d−1} + … + G_{n}^{(d)}| ≤ α^{nd}

has infinitely many solutions (n, y_{n}) ∈ U with n ∈ Σ, where Σ is a sequence of positive integers. By setting

y_{n} = α^{n}z_{n}

and by dividing through by α^{nd} we get

|g(γ_{1}^{n}, …, γ_{r}^{n}, z_{n})| ≤ 1,

with the polynomial g defined in (3).

First, we show by another indirect argument that the sequence (z_{n})_{n∈Σ}, for the corresponding sequence (n, z_{n}) ∈ ℕ × K with n ∈ Σ, is bounded by c as defined in (6). Suppose that |z_{n}| > c > 1 for some n ∈ Σ. We can write (see Lemma 1)

g(x_{1}, …, x_{r}, z) = z^{d} + p_{1}(x_{1}, …, x_{r})z^{d−1} + … + p_{d}(x_{1}, …, x_{r})

with polynomials p_{i}(x_{1}, …, x_{r}). Dividing by |z_{n}^{d−1}|, we get

|z_{n} + p_{1}(γ_{1}^{n}, …, γ_{r}^{n}) + … + p_{d}(γ_{1}^{n}, …, γ_{r}^{n})z_{n}^{−d+1}| ≤ |z_{n}^{−d+1}| ≤ 1 − ϵ,

for some ϵ > 0. By Lemma 1 we have

lim_{n→∞} p_{i}(γ_{1}^{n}, …, γ_{r}^{n}) = a_{1}^{(i)}

for all i = 1, …, d and thus by reminding the definition of c we get

|p_{1}(γ_{1}^{n}, …, γ_{r}^{n}) + … + p_{d}(γ_{1}^{n}, …, γ_{r}^{n})z_{n}^{−d+1}| ≤ c − 1 + ϵ,

which holds if n is large enough. Consequently,

|z_{n}| ≤ |p_{1}(γ_{1}^{n}, …, γ_{r}^{n}) + … + p_{d}(γ_{1}^{n}, …, γ_{r}^{n})z_{n}^{−d+1}| + |z_{n}^{−d+1}| ≤ c,

which is a contradiction, that proves that the sequence (z_{n})_{n∈Σ} is bounded.

We got that |z_{n}| ≤ c, which in turn implies

|y_{n}| = α^{n}|z_{n}| ≤ cα^{n}.

This means that our solutions do not lie in U, which is a contradiction proving that there are at most finitely many n for which a solution (n, y) ∈ U exists. Since the inequality under consideration has clearly finitely many solutions y for any fixed n, we can conclude that it has only finitely many solutions (n, y) ∈ U. □

5. Proof of Theorem 1

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

First we consider solutions of the form (n, 0), n ∈ ℕ. In this case the inequality reduces to

|G_{n}^{(d)}| < α^{n(d−1−ϵ)}.

But in this case we trivially have finitely many solutions, if the dominant root of G_{n}^{(d)} is > α^{d−1−ϵ}. In the case that α_{1}^{(d)} < α^{d−1−ϵ} the inequality is satisfied for all n large enough, i.e. for all n with finitely many exceptions. The last case is that

α_{1}^{(d)} = α^{d−1−ϵ}.

Clearly, if |a_{1}^{(d)}| > 1 we have only finitely many solutions and if |a_{1}^{(d)}| < 1 we have solutions for all n large. If |a_{1}^{(d)}| = 1 we look at

G_{n}^{(d)} − a_{1}^{(d)}α_{1}^{(d)^{n}}.

If n is large enough this is either always positive or negative and less than a_{1}^{(d)}α_{1}^{(d)^{n}}. Therefore, depending on whether the sign of a_{1}^{(d)} and a_{2}^{(d)} are equal or not, we get, as before, that we have only finitely many solutions or solutions for all n with finitely many exceptions. Consequently, we can restrict ourselves to solutions of the form (n, y) ∈ ℕ × ℤ with y ≠ 0. Moreover, by Proposition 1, we can assume that |y| ≤ cα^{n}, i.e. that (n, y) ∈ L.

Thus, in the following, we consider only solutions (n, z) ∈ ℕ × K of

(11)  |g(γ_{1}^{n}, …, γ_{r}^{n}, z)| < α^{−n(1+ϵ)}

with the polynomial g defined in (3) and with 0 < |z| ≤ c as defined in (6), where K is the number field generated by the coefficients of G_{n}^{(1)}, …, G_{n}^{(d)}, and by α.

Now since D(G_{n}^{(1)}, …, G_{n}^{(d)}) ≠ 0, by the Implicit Function Theorem 3 we can conclude that

(12) g(x_{1}, …, x_{r}, z) = (z− ∑_{|i|≥0} a_{i,1}x_{1}^{i_{1}} ⋯ x_{r}^{i_{r}})·. . .·(z− ∑_{|i|≥0} a_{i,d}x_{1}^{i_{1}} ⋯ x_{r}^{i_{r}})

with a_{i,j} ∈ \overline{ℚ}, where z_{i} := a_{0,i}, i = 1, …, d satisfy g(0, …, 0, z_{i}) = 0. The series

φ_{1}(x_{1}, …, x_{r}) = ∑_{|i|≥0} a_{i,1}x_{1}^{i_{1}} ⋯ x_{r}^{i_{r}}, …, φ_{d}(x_{1}, …, x_{r}) = ∑_{|i|≥0} a_{i,d}x_{1}^{i_{1}} ⋯ x_{r}^{i_{r}}

converge around the point (x_{1}, …, x_{r}) = (0, …, 0). Observe that for n large enough each solution (n, z) of (11) gives rise to a point (γ_{1}^{n}, …, γ_{r}^{n}) lying in the region of convergency of φ_{j} for some j = 1, …, d, i.e. we get that

z − φ_{j}(γ_{1}^{n}, …, γ_{r}^{n}) = z − ∑_{|i|≥0} a_{i,j}γ_{1}^{i_{1}n} ⋯ γ_{r}^{i_{r}n}

becomes arbitrarily small for some j = 1, …, d and if n is large enough. We remark that here we need that (n, y) ∈ L, which implies that the sequence of z is bounded.

From the assumption D(G_{n}^{(1)}, …, G_{n}^{(d)}) ≠ 0 it follows that the z_{i} are distinct, because they are the roots of g(0, …, 0, z) = 0. This means that g is regular in the sense of the Definition in [18]. We consider now the sets

M_{j} = {(n, z) : |z − φ_{j}| = min_{i=1,...,d}{|z − φ_{i}|}}, j = 1, …, d.

Here we have used the notation φ_{i} short for φ_{i}(γ_{1}^{n}, …, γ_{r}^{n}). We will go on using this notation below. Without loss of generality we restrict ourselves to the case that (n, z) ∈ M_{1} and show the conclusion of the theorem only in this case.

By considering (n, z) ∈ M_{1} we get from (12) that

|g(γ_{1}^{n}, …, γ_{r}^{n}, z)| = |z − φ_{1}| |z − φ_{2}| ⋯ |z − φ_{d}|.

On the right hand side we have one “small” factor and all other factors are “big”. We now want to calculate lower bounds for the quantities |z − φ_{i}|, i = 2, …, d.

We calculate the contribution of the “big” terms: for every i ≥ 2 we have

|z − φ_{i}| ≥ \frac{1}{2}|φ_{i} − φ_{1}| ≥ \frac{1}{3}|z_{i} − z_{1}|,

for n large enough (recall that we are considering only those (n, z) which lie in M_{1}, i.e. we have |z − φ_{1}| ≤ |z − φ_{i}|). Therefore, we conclude

|z − φ_{2}| ⋯ |z − φ_{d}| ≥ (\frac{1}{3} min_{i=2,...,d}\{|z_{i} − z_{1}|\})^{d−1} =: C_{1}^{−1}.

We remark that this lower bound does not depend on n.

Thus, we get from (11) an upper bound for the “small” term |z − φ_{1}|, namely

C_{1}^{−1}|z − φ_{1}| < α^{−n(1+ϵ)}

and therefore

(13)  |z − φ_{1}| < C_{1}α^{−n(1+ϵ)}.

We are going to approximate z by a finite sum extracted from

φ_{1} = z_{0} + ∑_{|i|>0} a_{i,1}γ_{1}^{i_{1}n} ⋯ γ_{r}^{i_{r}n} =

= z_{0} + ∑_{0<|i|≤H} a_{i,1}γ_{1}^{i_{1}n} ⋯ γ_{r}^{i_{r}n} + O (max{γ_{1}, …, γ_{r}}^{n(H+1)}) .

We define

V_{n} := z_{0} + ∑_{0<|i|≤H} a_{i,1}γ_{1}^{i_{1}n} ⋯ γ_{r}^{i_{r}n},

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

V_{n} = z_{0} + ∑_{i=1}^{h} e_{i}β_{i}^{n},

where e_{i} ∈ \overline{ℚ} and with 1 > β_{1} > … > β_{h} > 0 and with h ≤ H^{r}. We enlarge K at once and assume that it contains all the coefficients e_{i}. Observe that we have

(14)  |φ_{1} − V_{n}| ≤ C_{2} max{γ_{1}, …, γ_{r}}^{n(H+1)} = C_{2}C_{3}^{n(H+1)},

with C_{3} := max{γ_{1}, …, γ_{r}} < 1.

We need an estimate for H(z) for later purposes. We have

(15)  H(z) = H (\frac{y}{α^{n}} ) ≤ max\{H(y), H(α^{n})\} ≤ cα^{n},

where we have used that H(y) = |y| ≤ cα^{n} (since y ∈ ℤ) and that H(α^{n}) ≤ α^{n} too (since α to some power is an integer).

We choose H so that

(16)  C_{3}^{H+1}α^{2} < 1.

This is possible since C_{3} < 1 and from now on H is fixed and therefore also h, e_{i}, β_{i} for i = 1, …, h are fixed. Moreover, we choose a finite set S of absolute values of K so that it contains all infinite absolute values and we require that all α_{i}^{(j)}, i = 1, …, t^{(j)}, j = 1, …, d are S-units. In particular, with this choice all the β_{i} are S-units and the z are S-integers, the last fact following from the relation y = α^{n}z and the fact that the y are integers.

Last we need an upper bound for Ĥ((−z, 1, β_{1}^{n}, …, β_{h}^{n})). First it is easy to see that we have

H(γ_{i}) ≤ α^{d},

since we have

γ_{i} = \frac{α_{k}^{(j)}}{α^{d−j}}

for certain j and k. Therefore, we get

H(β_{i}) ≤ α^{dH} for all i = 1, …, h.

Finally, we conclude

Ĥ((−z, 1, β_{1}^{n}, …, β_{h}^{n})) = H(z)H(β_{1})^{n} ⋯ H(β_{h})^{n} ≤ cα^{n(1+dHh)},

where we have used (15).

Now we are ready to apply Theorem 2 with c_{0} = −1, c_{1} = z_{0}, c_{i} = e_{i−1} for i = 2, …, h + 1. We put w_{0} = z, w_{1} = 1 and w_{i} = β_{i−1}^{n} for i = 2, …, h + 1. Since w_{i} are S-units for i ≥ 1, assumption (i) of Theorem 2 is verified for any choice of ϵ′ > 0.

We proceed to verify assumption (ii) for all large n, provided we choose a small enough ϵ′, which we will fix later, and put δ = (h + 4)ϵ′. We have by (13) and (14)

|c_{0}w_{0} + c_{1}w_{1} + … + c_{h+1}w_{h+1}| =

= |z − V_{n}| ≤ |z − φ_{1}| + |φ_{1} − V_{n}| ≤ C_{1}α^{−n(1+ϵ)} + C_{2}C_{3}^{n(H+1)} ≤

≤ C_{1}α^{−n(1+ϵ)} + C_{2}α^{−2n} ≤ C_{4}α^{−n(1+ϵ)},

where C_{3}^{H+1} < α^{−2} holds by (16).

To compare this estimate with the right side of (ii) in Theorem 2, we first observe that H_{S}(w_{0}) = 1, since w_{0} = z is an S-integer. Therefore we get

(H(w_{0})H_{S}(w_{0})^{h+1})^{−1} Ĥ(w)^{−δ} > c^{−(1+δ)}α^{−n(1+δ(1+dHh))}

where we have used

H(w_{0}) = H(z) < cα^{n},
Ĥ(w) = Ĥ((−z, 1, β_{1}^{n}, …, β_{h}^{n})) ≤ cα^{n(1+dHh)}.

The verification of (ii) will follow from

C_{4}α^{−n(1+ϵ)} < c^{−(1+δ)}α^{−n(1+δ(1+dHh))},

which is clearly true by choosing

δ = (h + 4)ϵ′ < \frac{ϵ}{(1 + dHh)}

and n large enough.

Now from Theorem 2 it follows that either there are finitely many possibilities for w = (−z, 1, β_{1}^{n}, …, β_{h}^{n}) and therefore finitely many pairs (n, z) of solutions of (11), or we have a vanishing subsum of

c_{0}w_{0} + c_{1}w_{1} + … + c_{h+1}w_{h+1} = −z + z_{0} + ∑_{i=1}^{h} e_{i}β_{i}^{n}

involving c_{0}w_{0} = −z, i.e. we have

(17)  z = v_{0} + ∑_{i=1}^{h} v_{i}β_{i}^{n}, v_{i} ∈ \overline{ℚ}, i = 0, …, h,

with v_{0} ∈ {0, z_{0}} and v_{i} ∈ {0, e_{i}}, i = 1, …, h. Substituting this into |g(x_{1}, …, x_{r}, z)| we get

|g (γ_{1}^{n}, …, γ_{r}^{n}, v_{0} + ∑_{i=1}^{h} v_{i}β_{i}^{n})| < α^{−n(1+ϵ)}

and we consequently see that this can either hold for all n in a suitable arithmetic progression P or holds only for finitely many n. The first case leads to the power sum

H_{n} = v_{0}α^{n} + ∑_{i=1}^{h} v_{i} (β_{i}α)^{n} ,

having the property that (n, H_{n}) is a solution of (8) for all n in the above arithmetic progression. The second case leads again to finitely many solutions.

Finally, we get that all solutions of

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

can be parametrized by finitely many power sums. Moreover, if we have infinitely many solutions then n lies in the union of a finite set and a finite number of arithmetic progressions. This proves the theorem. □

6. Proof of the Corollaries

The proof of Corollary 1 runs along the same lines as the proof of Corollary 3.3 in [18]. □

Corollary 2 is an immediate consequence of Theorem 1. □

7. Acknowledgements

The first author was supported by the Austrian Science Foundation FWF, grant S8307-MAT. The second author was supported by Istituto Nazionale di Alta Matematica “Francesco Severi”, grant for abroad Ph.D. Both authors are most grateful to an anonymous referee for careful reading of the text and for several useful remarks improving previous versions of the paper.

References

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

[2] Y. Bugeaud, P. Corvaja and U. Zannier, An upper bound for the G.C.D. of a^{n} − 1 and b^{n} − 1, Math. Zeitschrift 243 (2003), 79-84.

[3] J. Cel, The Newton-Puiseux theorem for several variables, Bull. Soc. Sci. Let. Łódź 40 (1990), no. 11-20, 53-61.

[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, 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] J.-H. Evertse, An improvement of the Quantitative Subspace Theorem, Compos. Math. 101 (3) (1996), 225-311.

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

[9] C. Fuchs, An upper bound for the G.C.D. of two linear recurring sequences, Math. Slovaca 53 (2003), No. 1, 21-42.

[10] C. Fuchs and A. Scremin, Polynomial-exponential equations involving several linear recurrences, to appear in Publ. Math. Debrecen (Preprint: http://finanz.math.tugraz.ac.at/∼fuchs/eisr2.pdf).

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

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

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

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

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

[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] A. Scremin, Diophantine inequalities with power sums, J. Théor. Nombres Bordeaux, to appear.

[19] T. N. Shorey and C. L. Stewart, Pure powers in recurrence sequences and some related Diophantine equations, J. Number Theory 27 (1987), 324-352.