DIOPHANTINE PROBLEMS WITH LINEAR RECURRENCES VIA THE SUBSPACE THEOREM

CLEMENS FUCHS^{∗}

Abstract. In this paper we give an overview over recent developments (initiated by P. Corvaja and U. Zannier in [3]) on Diophantine problems where linear recurring sequences are involved and which were solved by using W.M. Schmidt’s Subspace Theorem.

Moreover, as a new application, we show: let (G_{n}) and (H_{n}) be linear recurring sequences of integers defined by G_{n} = c_{1}α_{1}^{n} +c_{2}α_{2}^{n} +⋯+c_{t}α_{t}^{n} and H_{n} = d_{1}β_{1}^{n} + d_{2}β_{2}^{n} + ⋯ + d_{s}β_{s}^{n}, where t, s ≥ 2, c_{i}, d_{j} are non-zero rational numbers and where α_{1} > … α_{t} > 0, β_{1} > … > β_{s} > 0 are integers with α_{1}, α_{2} ⋯ α_{t}β_{1} ⋯ β_{s} coprime, and let ϵ > 0. Then, we have

G.C.D.(G_{n}, H_{n}) < exp(ϵn)

for all n large enough.

1. Introduction

Let A_{1}, A_{2}, …, A_{k} and G_{0}, G_{1}, …, G_{k−1} be integers 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, ….

It is well known that G_{n} admits an analytic representation, namely for n ≥ 0

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

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

(3)  X^{k} − A_{1}X^{k−1} − ⋯ − A_{k}

and 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: ℚ(α_{1}, …, α_{t}).

The recurring sequence (G_{n}) is called nondegenerate, if no quotient α_{i}/α_{j} for all 1 ≤ i < j ≤ t is equal to a root of unity.

For the sake of simplicity we shall often restrict ourselves to linear recurring sequences (G_{n}), where all roots of the characteristic polynomial of (G_{n}) are simple, which means that

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

Date: April 25, 2005.

∗This work was supported by the Austrian Science Foundation FWF, grants S8307-MAT and J2407-N12.

2000 Mathematics Subject Classification: 11D45,11D61.

for some c_{i}, α_{i} ∈ ℂ. In this case we refer to G_{n} as to a power sums. The α_{i} are called the roots and the c_{i} are called the coefficients of the power sums G_{n}. If we restrict the roots to come from a multiplicative semigroup A ⊂ ℂ, then we let E_{A} denote to ring of complex functions on ℕ of the form (4) where α_{i} ∈ A. Below, A will be usually ℤ; moreover in that case we define by E_{ℤ}^{+} the subring formed by those functions having only positive roots, i.e. by the semigroup ℕ. Working in this domain causes no loss of generality: this assumption may be achieved by written n = 2m + r and considering the cases r = 0, 1 separately.

We need some information about the structure of the ring of power sums E_{ℤ}^{+} introduced above. In fact, if e.g. two recurrences (G_{n}) and (H_{n}) are given they lie in a much smaller ring, namely in E_{A} where A is the multiplicative group generated by the roots of G_{n} and H_{n}. It is well known (see [25]) and in fact easy to prove that this ring is isomorphic to the ring

ℂ[T_{1}, …, T_{t}, T_{1}^{−1}, …, T_{t}^{−1}].

if A has rank t ≥ 1. We simply choose a basis γ_{1}, …, γ_{t} of A and associate the variable T_{i} the function n ↦ γ_{i}^{n}. Hence, it is easy to decide on arithmetic properties of power sums in the ring of power sums, e.g. whether (G_{n}) is some q-th power in E_{A} or whether (G_{n}) and (H_{n}) are coprime (as power sums). This will be important for the results stated below.

Diophantine problems involving linear recurrences (or power sums) have been widely investigated and have a long tradition. However, a new development was started in 1998 by P. Corvaja and U. Zannier, who used the celebrated Subspace Theorem due to W.M. Schmidt to obtain new results. The Subspace Theorem has long been known to be crucial in the investigation of recurrence sequences, but somewhat surprisingly the results collected in this paper have not appeared before that time.

It is the aim of the present paper to give an overview over these results and how they are deduced from the Subspace Theorem. This will be done by first stating an appropriate version of the result and afterward giving a brief sketch of the proof. Of course we will concentrate on the results where the author was involved (his work on it started with [12]). Moreover, we will also show a new result in this direction concerning the G.C.D. of two power sums both with arbitrarily large order.

Before we start with the results it is worth to spend a few more words on the Subspace Theorem: we begin with the most simple statement of the Subspace Theorem which was proved in 1972 and which is a generalisation to higher dimensions of Roth’s famous theorem, which says that for a real algebraic number α and for every δ > 0, the inequality

|α − \frac{p}{q}| < \frac{1}{q^{2+δ}} ,

has at most finitely many solutions in rational integers p, q.

Theorem 1 (Subspace Theorem, W.M. Schmidt). Suppose L_{1}(x), …, L_{n}(x) are linearly independent linear forms in x = (x_{1}, …, x_{n}) with algebraic coefficients. Given δ > 0, there are finitely many proper linear subspaces T_{1}, …, T_{w} of ℝ^{n} such that every integer point x ≠ 0 with

|L_{1}(x) ⋯ L_{n}(x)| < ∥x∥^{−δ},

where ∥x∥ := max{|x_{i}| : i = 1, …, n}, lies in one of these subspaces.

In 1989 Schmidt gave a quantification of this result by giving an explicit upper bound for the number of subspaces involved in the statement. Before we can state this result we introduce the notation of absolute values and heights in number fields.

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 embeddings σ, σ̄ : 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

(5)  ∏_{v∈M_{K}} |x|_{v} = 1 for x ∈ K\{0}.

We define the K-height of x ∈ K to be

H_{K}(x) = ∏_{v∈M_{K}} max{1, |x|_{v}}.

Observe that H_{ℚ}(x) = |x| (the usual absolute value) for x ∈ ℤ and that

H_{L}(x) = H_{K}(x)^{[L:K]},

for x ∈ K and for a finite extension L of 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} = max_{1≤i≤n} |x_{i}|_{v}.

Now define

H(x) = ∏_{v∈M_{K}} max{1, |x|_{v}}.

Again, in the special cases x ∈ ℤ^{n}, we have H(x) = ∥x∥. Moreover, we define another height H by taking Euclidean norms at the infinite places, namely

H(x) = ∏_{v∈M_{K}} |x|_{v,2},

where

|x|_{v,2} = ((∑_{i=1}^{n} |x_{i}|_{v}^{2})^{\frac{1}{2}} )^{d(v)} for v infinite,

|x|_{v,2} = |x|_{v} for v finite,

and where d(v) = \frac{1}{[K:ℚ]}, \frac{2}{[K:ℚ]} depending on whether v is real infinite or complex infinite, respectively.

Now Schmidt’s quantitative Subspace Theorem is as follows: consider the inequality

(6)  |L_{1}(x) ⋯ L_{n}(x)| < | det(L_{1}, …, L_{n})|∥x∥^{−δ},

where 0 < δ < 1 and where L_{1}, …, L_{n} are linearly independent linear forms with coefficients in the number field K. For the set of solutions with

x ∈ ℤ^{n}, ∥x∥ ≫ max{(n!)^{8/δ}, H(L_{1}), …, H(L_{n})},

where the height of a linear form is the height of its vector of coefficients, we have the conclusion of Theorem 1 with

w ≤ [(2d)^{2^{26n}δ^{−2}}] ,

where d = [K : ℚ].

Later on the Subspace Theorem (and also the quantification) was extended to p-adic numbers and number fields by H.P. Schlickewei. We also state one version of his result (which follows from Theorem 1D’ in [28], page 178).

Theorem 2 (Subspace Theorem, Schlickewei). Let K be an algebraic number field and let S ⊂ M_{K} be a finite set of absolute values which contains all the infinite ones. For v ∈ S, let L_{1,v}, …, L_{n,v} be n linearly independent linear forms in n variables with coefficients in K. Let δ > 0 be given. Then the solutions of the inequality

(7)  ∏_{v∈S} ∏_{i=1}^{n} |L_{i,v}(x)|_{v} < H(x)^{−δ}

with x ∈ (O_{K})^{n} and x ≠ 0 lie in finitely many proper subspaces of K^{n}.

Let us remark that the best version (concerning the dependancy on the parameters) of the quantitative Subspace Theorem is due to Evertse (cf. [8]). Recently, Evertse and Schlickewei proved a much more general result taking into account all algebraic numbers and not only those lying in a fixed number field (cf. [10, 9]).

Now we come back to Diophantine problems where linear recurrences are involved. The following results are well known and the most classical consequences of the Subspace Theorem (they are obtained by the fact that a recurrence is just a linear combination of a fixed number of S-units): let (G_{n}) be a non-degenerate linear recurrence and assume that also α_{1}, …, α_{t} are not roots of unity. Denote by N(a) for every complex number a the number of integers n with

G_{n} = a

(this number is called the a-multiplicity of (G_{n})). From the Theorem of Skolem-Mahler-Lech (cf. [20]) it follows that then N(a) is finite. Schlickewei [26] proved that if α_{1}, …, α_{t} and the coefficients of P_{1}, …, P_{t} generate an algebraic number field K of degree q, then for every a ∈ K we have

N(a) ≤ q^{6d^{2}}2^{2^{28d!}}.

Recently, Schmidt proved that for arbitrary non-degenerate linear recurrences of complex numbers we have

N(0) ≤ exp(exp(exp(20d)))

(cf. [29, 30]). Moreover, Evertse, Schlickewei and Schmidt [11] proved for power sums (i.e. simple linear recurrences), where the coefficients and roots are non-zero complex numbers and where neither α_{1}, …, α_{t}, nor any quotient α_{i}/α_{j} (1 ≤ i < j ≤ t) is a root of unity, we have

N(a) ≤ exp ((t + 2)(6t)^{4t})

for every a ∈ ℂ.

These results show that the Subspace Theorem is a major tool to consider Diophantine problems with linear recurrences.

The rest of the paper is organized as follows: in Section 2 we show how the Subspace Theorem can be used to solve the equation G_{n} = y^{q} and generalisations as f(G_{n}^{(1)}, …, G_{n}^{(d)}, y) = 0 for power sums. Moreover, we will consider generalisations of these results to the corresponding Diophantine inequalities. In Section 3 we will consider the equation H_{n} = yG_{n} and study upper bounds for the G.C.D. of two power sums (G_{n}) and (H_{n}). In Section 4 we present a new result on the G.C.D. of two power sums and we will give a complete proof of this result in Section 5.

2. The equation G_{n} = y^{q} and generalisations

First we deal with Diophantine equations, where linear recurring sequences are involved. Such equations were earlier investigated by several authors, e.g. in the special case

(8)  G_{n} = Ey^{q}, E ∈ ℤ\{0}

including the question of how many squares are in classical sequences as the Fibonacci sequence. A survey on this equation can be found in [22, 23] and in more general form in [13, 17]. The first results have been proved just by using elementary and algebraic tools. Later, the results were obtained with the applications of lower bounds for linear forms in logarithms of algebraic numbers.

We mention here also Pisot’s q-th root conjecture (cf. [24]), which states that if all the values of G_{n} are q-th powers in a given number field K, then G_{n} is identically a q-th power of a recurrence. This conjecture was finally verified by Zannier [32]. However, this result does not solve the question on the finiteness of the solutions of (8).

Corvaja and Zannier (cf. [3]) were able to attack this problem for power sums. They considered linear recurrences defined by

(9)  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 the Subspace Theorem to show that for every integer q ≥ 2 the equation

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

has only finitely many solutions (n, y) ∈ ℕ^{2} assuming that G_{n} is not identically a perfect qth power for all n in a suitable arithmetic progression. Observe that, as remarked in the Introduction, it is easy to decide effectively whether this is the case or not.

Tichy and the author [17] gave a quantitative version of the above result of Corvaja and Zannier by using the quantitative Subspace Theorem due to Evertse [8].

Theorem 3 (p. 12, [17]). Let (G_{n}) ∈ E_{ℤ}^{+} be a linear recurring sequence defined by (9) where t ≥ 2, c_{1}, c_{2}, …, c_{t} are nonzero rational numbers, α_{1} > α_{2} > ⋯ > α_{t} > 0 are integers and such that for given q ≥ 2 there is no r ∈ {0, …, q − 1} with G_{mq+r} a perfect qth power for all m ∈ ℕ. Then the number of solutions (n, y) ∈ ℕ^{2} of the equation

G_{n} = y^{q}

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

Sketch of the Proof: We approximate the quantity G_{n}^{1/q} by defining

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

where R ≥ 1 and where n = mq + r, n ∈ ℕ, r ∈ {0, …, q − 1}. This quantity is obtained by using the binomial series for expanding G_{n}^{1/q} after putting first out the dominant root α_{1} and by truncating this series at the index R. We write

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

where d_{i} ∈ ℚ ((c_{1}α_{1}^{r})^{1/q})^{∗}, e_{i}, b are integers, b > 0, and the e_{i}/b are nonzero distinct rational numbers. We have obtained an approximation for the solutions y_{mq+r} as linear combination of S-units for a finite set S of absolute values which we define in a second. From this we can construct a small linear form with respect to the usual infinite absolute value. This will always be our main strategy.

Define the linear forms L_{i,v} for v ∈ S = {∞ and primes dividing e_{i} or b} and i = 1, …, h as follows:

L_{0,∞} := X_{0} − ∑_{i=1}^{h} d_{i}X_{i} and L_{i,v} := X_{i}

for (i, v) ≠ (0, ∞). Applying the Subspace Theorem (Theorem 2) now yields the result by a standard argument (see also the end of the proof in Section 5). □

Later on, Corvaja and Zannier [4] generalized their result (in fact for power sums defined over ℚ this result was already contained in [3]). Let K be an algebraic number field and let (G_{n}) be a non-degenerate linear recurring sequence defined by (4) where t ≥ 2, c_{i} are non-zero elements of K for all i = 2, …, t and where α_{1}, …, α_{t} are elements of K with 1 ≠ |α_{1}| > |α_{j}| for all j = 2, …, t. Let f(x, y) ∈ K[x, y] be monic in y and suppose that there do not exist non-zero algebraic numbers d_{j}, β_{j} for j = 1, …, k such that

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

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

(12)  f(G_{n}, y) = 0

is finite. The author [13] gave a quantitative version of this result, which is a little bit more general in the assumptions.

Theorem 4 (p. 236, [13]). 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 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(x, y) ∈ K[x, y] be monic in y 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

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, y) ∈ ℕ × K of the equation

f(G_{n}, y) = 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.

Sketch of the Proof: We work only in the case |α_{1}| > 1 and consider the Puiseux expansion at x = ∞ of the solution y = y(x) of f(x, y) = 0.

Now by Puiseux’s Theorem we can conclude that

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

where

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

for j = 0, …, e_{i} − 1, i = 1, 2, …, r. Therefore for each solution (n, y_{n}) of (12) we get

(13)  y_{n} = ∑_{k=v}^{∞} β_{k}G_{n}^{− \frac{k}{e}} ,

for some v, e and β_{k}, which lie in a fixed finite extension of K.

We have the binomial expansion

G_{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}. Thus we can approximate y_{n} by a finite sum extracted from the Puiseux expansion (13), namely by

H_{n} := ∑_{k=v}^{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.

As before this leads to one small linear form with respect to the usual absolute value. All other linear forms are again the trivial projections. They are small because the expression above is again a linear combination of S-units. The result follows from the Subspace Theorem. □

Scremin [31] proved the following result which is related to what we consider here (in fact it is a consequence on his related result on the Diophantine inequality which we will mention below). Let f(x, y) ∈ \overline{ℚ}[x, y] be monic in y, absolutely irreducible and of degree d ≥ 2 in y; let g(n) ∈ ℤ[x] be a non constant polynomial; let G_{n} ∈ \overline{ℚ}E_{ℤ} not constant. Then the equation

f(G_{n}, y) = g(n)

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

Recently, Scremin and the author [15] generalised these results to the equation

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

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

G_{n}^{(0)} = a_{1}^{(0)}α_{1}^{(0)^{n}} + a_{2}^{(0)}α_{2}^{(0)^{n}} + … + a_{t^{(0)}}^{(0)}α_{t^{(0)}}^{(0)^{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 = 0, …, d.

Let f(x_{0}, …, x_{d}, y) = x_{0}y^{d} + … + x_{d−1}y + x_{d}. So the above equation becomes

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

We will show how to this equation another equation in some normal form can be associated. First, we set (for a positive real determination of the roots)

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

Moreover, let

y = \frac{α^{n}}{α_{1}^{(0)^{\frac{n}{d}}}} z.

Then consider

(15)  \frac{1}{α^{dn}} f(G_{n}^{(0)}, …, G_{n}^{(d)}, \frac{α^{n}}{α_{1}^{(0)^{\frac{n}{d}}}} z).

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

α, α_{1}^{(0)^{\frac{1}{d}}} and the roots of G_{n}^{(0)}, …, G_{n}^{(d)},

i.e. the coefficients of this polynomial are again power sums. Observe that all the roots which appear in these power sums are ≤ 1, because of our construction and that one of the roots which appears as coefficient of z^{d} is 1. Let γ_{1}, …, γ_{r} denote the different roots of these power sums (the coefficients of (15) as a polynomial in z), which are strictly less than 1. We identify the expressions γ_{i}^{n} in (15) by a new variable x_{i}. Therefore we get a polynomial (linear in x_{1}, …, x_{r}) g(x_{1}, …, x_{r}, z) ∈ \overline{ℚ}[x_{1}, …, x_{r}, z] such that

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

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

We are now able to formulate our next result, which states that the equation (14) has only finitely many solutions in integers, apart from “trivial” cases which can be classified and which come from functional identities in the ring of power sums.

Theorem 5 (p. 154, [15]). Let d ≥ 2 and let G_{n}^{(0)}, …, G_{n}^{(d)} ∈ \overline{ℚ}E_{ℤ}^{+}. Assume that

(16)  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}, and a finite set N of integers, such that for the set S of solutions (n, y) ∈ ℕ × ℤ 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

we have

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

where M is a finite set.

Sketch of the Proof: The solutions (n, y_{n}) of the equation give rise to solutions (n, z_{n}) of the equation g(γ_{1}^{n}, …, γ_{r}^{n}, z_{n}) = 0. We consider infinitely many solutions (n, z_{n}) where n ∈ Σ and Σ is a sequence of positive integers. From the construction of g it follows that the sequence (z_{n}) must be bounded and therefore lie in some neighbourhood of the solutions of

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

at least if n is large enough.

By a suitable version of the Implicit Function Theorem we conclude

z = z_{0} + ∑_{|i|>0} a_{i}x_{1}^{i_{1}} … x_{r}^{i_{r}}

where i = (i_{1}, …, i_{r}), |i| := |i_{1} + … + i_{r}| and with a_{i} ∈ \overline{ℚ}, where z_{0} satisfies g(0, …, 0, z_{0}) = 0.

Therefore for each solution (n, z_{n}) we get

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

for some z_{0} and coefficients a_{i}, and if n is large enough. Next we approximate z_{n} by

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

So, again we have an approximation for the solutions as a linear combination of S-units for a certain set S, which in turn leads to a small linear form. The result follows as before by applying the Subspace Theorem. □

Now we turn our interest to Diophantine inequalities. Corvaja and Zannier proved in their paper [3] in 1998 also the following result: let 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. Then 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 an immediate consequence, for every q ≥ 2 the equation G_{n} = y^{q} has only finitely many solutions, if we suppose that α_{1}, α_{2} are coprime. It is easy to see that the upper bound is best possible; if we remove ϵ then the conclusion is no longer true.

Scremin [31] 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 the following generalisation of the result of Corvaja and Zannier, namely 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.

Scremin and the author again went a step further and considered a generalisation of the equation (14) to the case of inequalities. They proved:

Theorem 6 (p. 168, [16]). Let d ≥ 2, G_{n}^{(1)}, …, G_{n}^{(d)} ∈ \overline{ℚ}E_{ℤ}^{+}. Let f(x_{1}, …, x_{d}, y) be monic in y. Assume that

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 but finitely many solutions (n, y) ∈ ℕ × ℤ of the Diophantine inequality

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

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.

Sketch of the Proof: Since D(G_{n}^{(1)}, …, G_{n}^{(d)}) ≠ 0, we conclude by the Implicit Function Theorem that

g(x_{1}, …, x_{r}, z) = (z − φ_{1}) · . . . · (z − φ_{d})

with

φ_{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}}

where a_{i,j} ∈ \overline{ℚ}, z_{i} := a_{0,i}, i = 1, …, d satisfy g(0, …, 0, z_{i}) = 0. For each solution (n, z) we get that

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

is small for some j = 1, …, d and if n is large enough. Here we need that |z| ≤ cα^{n} for some constant c. All solutions which do not satisfy this trivially fulfill our conclusion (see [16, Proposition 1]).

We consider the sets for j = 1, …, d

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

Without loss of generality, we assume (n, z) ∈ M_{1}. For (n, z) ∈ M_{1} we now consider

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

First we calculate the contribution of the “big” terms. We have

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

Now we consider the small term |z − φ_{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 (γ^{n}) .

We define

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

and use the Subspace Theorem to show

|z − φ_{1}| > C_{1}α^{−C_{2}n},

where C_{1}, C_{2} are certain constants, for all n outside of finitely many subspaces. From this the result follows in the usual way. □

Observe that in [16] we did not use the Subspace Theorem directly to get the last result. Instead we used a technical result by Corvaja and Zannier [5, Theorem 4] which is itself a consequence of the Subspace Theorem.

The main restriction in all these results is that we have to assume the existence of a simple dominant root. Of course we conjecture that the results are true without this assumption. This is the major open problem in this subject area.

3. The equation H_{n} = yG_{n} and the G.C.D. of G_{n}, H_{n}

At first sight this case seems to be much easier then the equations studied in the previous section. In fact it is possible to completely solve this equation. Also other more general questions, as on the G.C.D. of G_{n}, H_{n}, are of interest and can be answered (at least partially).

In order to motivate what is going on in this case we mention the so-called Hadamard Quotient theorem (proved by van der Poorten, cf. [25]), which says that if (G_{n}), (H_{n}) ∈ E_{ℤ}^{+}, then H_{n}/G_{n} ∈ ℤ for all n ∈ ℕ can only hold, if there is a recurring sequence (I_{n}) ∈ E_{ℤ}^{+} such that H_{n} = G_{n} · I_{n} for all n ∈ ℕ. Roughly speaking this means that the quotient may have values in ℤ for all n ∈ ℕ only when this is obvious, in the sense that it comes from an identical relation.

Corvaja and Zannier showed by using the Subspace Theorem a stronger result. They proved that if (G_{n}), (H_{n}) are as above and if H_{n} = yG_{n} has infinitely many solutions (n, y) ∈ ℕ × ℤ then there exists a recurring sequence (I_{n}) such that H_{n} = G_{n} · I_{n} for all n ∈ ℕ. Thus again, the infinitude of solutions can be explained by a function relation in the ring of power sums. This result can be found in [3].

Let us mention that in a very recent paper, Corvaja and Zannier solved this question in complete generality (i.e. for arbitrary linear recurrences (G_{n}) and (H_{n}); cf. [4]). They proved:

Theorem 7 (Corvaja and Zannier). Let (G_{n}), (H_{n}) be linear recurrences and let R be a finitely generated subring of ℂ. Assume that for infinitely many n ∈ ℕ, we have G_{n} ≠ 0 and H_{n}/G_{n} ∈ R. Then there exist a nonzero polynomial P (X) ∈ ℂ[X] and positive integers q, r such that both sequences n ↦ P (n)H_{qn+r}/G_{qn+r} and n ↦ G_{qn+r}/P (n) are linear recurrences.

The main problem in the proof was to get rid of the notorious dominant root condition and this was done by an ingenious application of the Subspace Theorem. They achieved this in the following way: first it is still possible to approximate H_{n}/G_{n} by using simultaneously all the roots with maximal absolute value; then they constructed several other small linear forms, out from the first one by multiplying the given small linear form by suitable powers of monomials in the dominant roots. We do not go more into details, since the proof of our original result in this paper follows essentially this line of proof, so we refer to Section 5.

Bugeaud, Corvaja and Zannier [1] used the Subspace Theorem to obtain more explicit results, bounding the cancellation in the fraction H_{n}/G_{n}, which is represented by the G.C.D. of G_{n} and H_{n}. In fact they showed that, if a, b are integers ≥ 2, and b is not a power of a, then, provided n is sufficiently large, we have

(17)  G.C.D.(a^{n} − 1, b^{n} − 1) ≪ a^{\frac{n}{2}} .

The number 1/2 in the exponent is best-possible, in view of the example a = c^{2}, b = c^{s}, for odd s.

In the case, when a and b are multiplicatively independent, they proved a sharper bound: Let ϵ > 0. Then, provided n is sufficiently large, we have

(18)  G.C.D.(a^{n} − 1, b^{n} − 1) < exp(ϵn).

This result is remarkable, especially because it was the first time that in the proof not only one but several small linear forms were used to which the Subspace Theorem was applied afterwords (see the sketch of the proof of Theorem 9).

Bugeaud, Corvaja and Zannier remarked that their method holds in a more general context. Taking this into account the author [14] proved the following result:

Theorem 8 (p. 23, [14]). Let (G_{n}) and (H_{n}) be linear recurring sequences of integers defined by G_{n} = c_{1}α_{1}^{n} +c_{2}α_{2}^{n} +⋯+c_{t}α_{t}^{n} and H_{n} = d_{1}β_{1}^{n} +d_{2}β_{2}^{n} + ⋯ + d_{s}β_{s}^{n}, where t, s ≥ 2, c_{i}, d_{j} are non-zero complex numbers and where α_{1} > ⋯ > α_{t} > 0, β_{1} > ⋯ > β_{s} > 0. Furthermore we assume that G_{n} does not divide H_{n} in the ring E_{ℤ}^{+}. Then, provided n > C_{1}, we have

G.C.D.(G_{n}, H_{n}) < |G_{n}|^{c},

for all n aside of a finite set of exceptions, which can be bounded by C_{2}, where C_{1}, C_{2} and c < 1 are effectively computable numbers depending on the c_{i}, d_{j}, α_{i} and β_{j}, i = 1, …, t, j = 1, …, s.

Sketch of the Proof: Write

z(n) = \frac{H_{n}}{G_{n}} = \frac{𝔠_{n}}{𝔡_{n}} ,

where 𝔠_{n}, 𝔡_{n} are nonzero integers. We show that

|𝔡_{n}| ≤ |G_{n}|^{1−c}

can hold for n > C_{1} only for a finite number of n, whose cardinality can be bounded by C_{2}. From this the result will follow.

We expand G_{n}^{−1} and approximate z(n) by the power sum

z̃(n) := H_{n} · \frac{1}{c_{1}α_{1}^{n}} ∑_{j=0}^{h}(−1)^{j} (∑_{i=2}^{t} \frac{c_{i}}{c_{1}} (\frac{α_{i}}{α_{1}} )^{n})^{j} ,

where h ≥ 1 is an integer. Now an application of the Subspace Theorem proves the result. □

Moreover, we get the following better result for “coprime” power sums (G_{n}) and (H_{n}) where (H_{n}) is of arbitrary large order:

Theorem 9 (p. 25, [14]). Let (G_{n}) and (H_{n}) be linear recurring sequences of integers defined by G_{n} = c_{1}α^{n} + c_{2} and H_{n} = d_{1}β_{1}^{n} + d_{2}β_{2}^{n} + ⋯ + d_{s}β_{s}^{n}, where s ≥ 2, c_{i}, d_{j} are non-zero complex numbers and where α > 1, β_{1} > ⋯ > β_{s} > 0 are integers with α, β_{1}β_{2} ⋯ β_{s} coprime. Furthermore, let ϵ > 0. Then, provided n > C_{1}, we have

G.C.D.(G_{n}, H_{n}) < |G_{n}|^{ϵ},

for all n aside of a finite set of exceptions, whose cardinality can be bounded by C_{2}, where C_{1}, C_{2} are effectively computable numbers depending on the c_{i}, d_{j}, α, β_{j}, i = 1, 2, j = 1, …, s and ϵ.

Sketch of the Proof: We fix a k and let

J = {j = (j_{1}, …, j_{s}) : j_{1} + … + j_{s} = k}

For every j ∈ J, we define

H_{j,n} = \underline{β}^{nj} (d_{1}β_{1}^{n} + d_{2}β_{2}^{n} + … + d_{s}β_{s}^{n}) .

We write

z_{j}(n) = \frac{H_{j,n}}{G_{n}} = \frac{𝔠_{j,n}}{𝔡_{n}} ,

where 𝔠_{j,n}, 𝔡_{n} are integers.

Now we define

ϕ_{j}(n) := z_{j}(n) − H_{j,n} · ∑_{i=1}^{h}(−1)^{i−1} \frac{c_{2}^{i−1}}{c_{1}^{i}} α^{−ni} =

= z_{j}(n) − β_{1}^{j_{1}n} ⋯ β_{s}^{j_{s}n} ∑_{i=1}^{h} ∑_{l=1}^{s}(−1)^{i−1}d_{l} \frac{c_{2}^{i−1}}{c_{1}^{i}} β_{l}^{n}α^{−ni},

for every index j = (j_{1}, …, j_{s}) with j_{1} +…+j_{s} = k. We apply the Subspace Theorem by considering several “small” linear forms coming from the above approximation of the values z_{j}(n) for all j ∈ J with k large enough (the above approximations were obtained by expanding G_{n}^{−1} in the definition of z_{j}(n) above).

Finally, this second parameter k can be chosen in such a way, that the theorem follows by an application of the Subspace Theorem. □

Let us mention some very recent generalisations of these type of results. Corvaja and Zannier proved (in [6]) that for every fixed ϵ > 0 the inequality

G.C.D.(u − 1, v − 1) < (max{|u|, |v|})^{ϵ}

holds for all pairs of multiplicatively independent S-units u, v ∈ ℤ for a finite set of absolute values including the infinite ones. We remark that this result was used to confirm a conjecture of Győry, Sárközy and Stewart from [19] (for further results in this direction see also [18, 2]). In [7] they generalised this statement for other pairs of rational functions then u − 1, v − 1 and gave a reformulation in the language of heights in order to get an extension to number fields. Their results imply that if p(x, y), q(x, y) ∈ \overline{ℚ}[x, y] are nonconstant coprime polynomials and suppose that not both of them vanish at (0, 0) and let a, b be multiplicatively independent integers. Then for every ϵ > 0 we have that

G.C.D.(p(a^{n}, b^{n}), q(a^{n}, b^{n})) < exp(ϵn)

for all n large enough.

In [21] Luca studied the G.C.D.(u − 1, v − 1) where u, v ∈ ℤ are “near” S-units. His result implies that if f(x), f_{1}(x), g(x), g_{1}(x) are non-zero polynomials with integer coefficients and a, b are multiplicatively independent integers as before, then for every ϵ > 0 the inequality

G.C.D.(f(n)a^{n} + g(n), f_{1}(n)b^{n} + g_{1}(n)) < exp(ϵn)

holds for all n large enough.

Both results were obtained by using the ideas from [1].

4. New result on the G.C.D.

The aim of this section is to present a new result which is a generalisation of Theorem 9 to the case where also G_{n} is a power sums of arbitrarily large order. The proof uses again the Subspace Theorem but in a more involved way with several nontrivial small linear forms (also with respect to different absolute values).

The main result is the following theorem:

Theorem 10. Let (G_{n}) and (H_{n}) be linear recurring sequences of integers defined by G_{n} = c_{1}α_{1}^{n} +c_{2}α_{2}^{n} +⋯+c_{t}α_{t}^{n} and H_{n} = d_{1}β_{1}^{n} +d_{2}β_{2}^{n} +⋯+d_{s}β_{s}^{n}, where t, s ≥ 2, c_{i}, d_{j} are non-zero rational numbers and where α_{1} > ⋯ > α_{t} > 0, β_{1} > ⋯ > β_{s} > 0 are integers with α_{1}, α_{2} ⋯ α_{t}β_{1} ⋯ β_{s} coprime. Furthermore, let ϵ > 0. Then, we have

G.C.D.(G_{n}, H_{n}) < exp(ϵn)

for all n large enough.

This theorem includes examples as

G.C.D.(2^{n} + 3^{n}, 5^{n} + 7^{n}) < exp(ϵn),

for all n large enough, which seem not to be covered by the previous results mentioned above.

Remark 1. The condition α_{1}, α_{2} ⋯ α_{t}β_{1} ⋯ β_{s} coprime assure that the sequences (G_{n}) and (H_{n}) are coprime as elements in the ring of power sums E_{ℤ}^{+}.

Remark 2. In the proof we use once again (as in the proof of [14, Theorem 2]) several small linear forms for the application of the Subspace Theorem. In fact the proof uses even more from the proof by Corvaja and Zannier of the main result in [4]. Moreover, we use nontrivial linear forms not only for one absolute value, but for several absolute values.

Remark 3. Of course it is possible, by using quantitative versions of the Subspace Theorem (e.g. due to Evertse [8]), to give the following more precise statement. There are explicitly computable positive constants C_{1}, C_{2} such that the claimed inequality is true for all n > C_{1} with finitely many exceptions whose cardinality can be bounded by C_{2}.

5. Proof of Theorem 10

For the reader’s convenience we state a version of the Subspace Theorem due to Schlickewei in a simplified version which is enough for our application:

Proposition 1 (Subspace Theorem). Let S be a finite set of absolute values of ℚ, including the infinite one and normalized in the usual way (i.e. |p|_{v} = p^{−1} if v|p). Extend each v ∈ S to \overline{ℚ} in some way. For v ∈ S let L_{1,v}, …, L_{N,v} be N linearly independent linear forms in N variables with algebraic coefficients and let δ > 0. Then the solutions x := (x_{1}, …, x_{N}) ∈ ℤ^{N} to the inequality

∏_{v∈S} ∏_{i=1}^{N} |L_{i,v}(x)|_{v} < ∥x∥^{−δ},

where ∥x∥ := max{|x_{i}| : i = 1, …, N}, are contained in finitely many proper subspaces of ℚ^{N}.

This theorem follows from [28, Theorem 1E, p. 178] (but a complete proof requires also [27]).

In the sequel let C_{1}, C_{2}, … denote positive numbers depending only on c_{i}, d_{j}, α_{i} and β_{j}, i = 1, …, t, j = 1, …, s and ϵ.

First observe that by [14, Lemma 2] it follows that G_{n} = 0 can only hold for finitely many n. So, we will exclude this case in the further considerations.

We now write

z_{n} = \frac{H_{n}}{G_{n}} = \frac{𝔠_{n}}{𝔡_{n}} ,

where 𝔠_{n}, 𝔡_{n} are nonzero integers. Thus we have

G.C.D.(G_{n}, H_{n}) · 𝔡_{n} = G_{n}.

We suppose that

(19)  𝔡_{n} ≤ α_{1}^{(1−ϵ)n}

for infinitely many n and we proceed to derive a contradiction which clearly proves

G.C.D.(G_{n}, H_{n}) ≤ C_{1}α_{1}^{ϵn}

from which our claim follows.

Now, let us denote by p_{1}, …, p_{r} the different prime divisors of α_{1}. By our assumption that α_{1} is coprime to α_{2} ⋯ α_{t}β_{1} ⋯ β_{s} it follows that

(20)  1 = |α_{2}|_{p_{i}} = … = |α_{t}|_{p_{i}} = |β_{1}|_{p_{i}} = … = |β_{s}|_{p_{i}} > |α_{1}|_{p_{i}}

for all i = 1, …, r.

We fix a positive integer f and write

(a_{2}α_{2}^{n} + … + a_{t}α_{t}^{n})^{f}

= (G_{n} − a_{1}α_{1}^{n})^{f} = G_{n} (∑_{i=0}^{f−1} \binom{f}{i}G_{n}^{f−1−i}(−1)^{i}a_{1}^{i}α_{1}^{in}) + (−1)^{f}a_{1}^{f}α_{1}^{fn}.

This implies

∏_{i=1}^{r} |(a_{2}α_{2}^{n} + … + a_{t}α_{t}^{n})^{f} z_{n} − H_{n} ∑_{i=0}^{f−1} \binom{f}{i}G_{n}^{f−1−i}(−1)^{i}a_{1}^{i}α_{1}^{in}|_{p_{i}} ≤ C_{2}α_{1}^{(1−f)n}.

Observe that it is clear that

∏_{i=1}^{r} |z_{n}|_{p_{i}} ≤ ∏_{i=1}^{r} |G_{n}|_{p_{i}}^{−1} ≤ |G_{n}| ≤ C_{1}α_{1}^{n},

since by the product formula we have

∏_{p∈ℙ}|x|_{p} · |x| = 1 ⟹ |x| = ∏_{p∈ℙ}|x|_{p}^{−1} ≥ ∏_{i=1}^{r} |x|_{p_{i}}^{−1}

for all rational integers x.

We now fix two other positive integers h, k; later on we shall impose that f, h, k satisfy suitable inequalities.

Let us denote by J = {j = (i_{2}, …, i_{t}, j_{1}, …, j_{s}) ∈ ℕ^{t−1+s} : i_{2}+…+i_{t} ≤ h, j_{1} +…+j_{s} ≤ k}. If we write j_{i} we mean the i-th vector in J with respect to the lexicographical ordering. The cardinality of J is given by

M := |J | = ( \begin{matrix}t − 1 + h \\ t − 1 \end{matrix} ) ( \begin{matrix}s + k \\ s \end{matrix} ) .

For every j ∈ J we consider the quantity

ϕ_{j}(n) := (a_{2}α_{2}^{n} + … + a_{t}α_{t}^{n})^{f} α_{2}^{i_{2}n} ⋯ α_{t}^{i_{t}n}β_{1}^{j_{1}n} ⋯ β_{s}^{j_{s}n}z_{n}

−α_{2}^{i_{2}n} ⋯ α_{t}^{i_{t}n}β_{1}^{j_{1}n} ⋯ β_{s}^{j_{s}n}H_{n} ∑_{i=0}^{f−1} \binom{f}{i}G_{n}^{f−1−i}(−1)^{i}a_{1}^{i}α_{1}^{in}.

By the above inequality and (20) we have

(21)  ∏_{i=1}^{r} |ϕ_{j}(n)|_{p_{i}} ≤ C_{2}α_{1}^{(1−f)n}

for all j ∈ J.

Now, let S be a set of absolute values of ℚ containing the infinite absolute value and all primes dividing α_{1} or α_{2} ⋯ α_{t}β_{1} ⋯ β_{s}. Especially, it contains the primes p_{1}, …, p_{r}. Moreover, we put

N_{1} := ( \begin{matrix}t − 1 + f + h \\ t − 1 \end{matrix} ) ( \begin{matrix}s + k \\ s \end{matrix} )

and

N_{2} := f ( \begin{matrix}t − 1 + f + h \\ t − 1 \end{matrix} ) ( \begin{matrix}s + k + 1 \\ s \end{matrix} ) .

Finally, set N := N_{1} + N_{2}. Observe that N_{1} denotes the number of possible quantities of the form

α_{2}^{i_{2}} ⋯ α_{t}^{i_{t}}β_{1}^{j_{1}} ⋯ β_{s}^{j_{s}}z_{n}

with i_{2} + … + i_{t} ≤ f + h and j_{1} + … + j_{s} ≤ k, whereas N_{2} denotes the number of possible different quantities of the form

α_{1}^{i_{1}}α_{2}^{i_{2}} ⋯ α_{t}^{i_{t}}β_{1}^{j_{1}} ⋯ β_{s}^{j_{s}}

with i_{1} < f, i_{2} + … + i_{t} ≤ f + h, j_{1} + … + j_{s} ≤ k + 1. In particular, we can write ϕ_{j}(n) as a linear combination of at most N nonzero terms of the mentioned types. Let us choose an ordering (in such a way that the first N_{1} terms are those quantities involving z_{n}) for the above quantities and denote the terms with x_{1}(n), …, x_{N_{1}}(n), x_{N_{1}+1} …, x_{N}(n). Thus we can write

ϕ_{j}(n) = A_{j,1}x_{1}(n) + … + A_{j,N}x_{N}(n)

for every j ∈ J.

We denote by

x_{n} = 𝔡_{n}(x_{1}(n), …, x_{N}(n)) ∈ ℤ^{N_{1}+N_{2}}

(remember that 𝔡_{n} was the denominator of z_{n}).

We define for every v ∈ S, N linearly independent linear forms in X = (X_{1}, …, X_{N}) as follows: for i ≤ M < N_{1} and for all j = 1, …, r put

L_{i,p_{j}}(X) = A_{j_{i},1}X_{1} + … + A_{j_{i},N}X_{N};

for all other pairs (j, v) ∈ {1, …, N} × S we set

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

We want to apply the Subspace Theorem with this choice of the linear forms. Observe that for fixed v ∈ S the linear forms L_{1,v}, …, L_{N,v} are linearly independent: this is clear for v ≠ p_{j}, j = 1, …, r and for v = p_{j} we have that

L_{i,p_{j}}(x_{1}(n), …, x_{N}(n)) = 𝔡_{n}ϕ_{j_{i}}(n)

for i ≤ M. In order to prove that L_{1,p_{j}}, …, L_{M,p_{j}}, X_{M+1}, …, X_{N} are linearly independent it suffices to show this for L_{1,p_{j}}(x_{1}(n), …, x_{N_{1}}(n), 0, …, 0), …, L_{M,p_{j}}(x_{1}(n), …, x_{N_{1}}(n), 0, …, 0). But in this case we have

L_{i,p_{j}}(x_{1}(n), …, x_{N_{1}}(n), 0, …, 0)
= (a_{2}α_{2}^{n} + … + a_{t}α_{t}^{n})^{f} α_{2}^{i_{2}n} ⋯ α_{t}^{i_{t}n}β_{1}^{j_{1}n} ⋯ β_{s}^{j_{s}n}𝔠_{n},

where j_{i} = (i_{2}, …, i_{t}, j_{1}, …, j_{s}) ∈ J. It is plain (again e.g. by [14, Lemma 2]) that a linear relation of such quantities holds for at most finitely many n.

We now consider the double product defined by the previously defined linear forms and vectors, namely

(22)  ∏_{v∈S} ∏_{i=1}^{N} |L_{i,v}(x_{n})|_{v} .

This product can be rewritten as

∏_{i=M+1}^{N} ∏_{v∈S} |L_{i,v}(x_{n})|_{v} · ∏_{i=1}^{M} ∏_{v∈S\{p_{1},...,p_{r}}} |L_{i,v}(x_{n})|_{v} · ∏_{i=1}^{M} ∏_{j=1}^{r} |L_{i,p_{j}}(x_{n})|_{p_{j}}.

We will first handle each of these double products separately.

First, we have for i > N_{1} that

∏_{v∈S} |L_{i,v}(x_{n})|_{v} = ∏_{v∈S} |𝔡_{n}α_{1}^{i_{1}n}α_{2}^{i_{2}n} ⋯ α_{t}^{i_{t}n}β_{1}^{j_{1}n} ⋯ β_{s}^{j_{s}n}|_{v} ≤ 𝔡_{n},

where i_{1}, i_{2}, …, i_{t}, j_{1}, …, j_{s} are suitable integers. Observe that we have used our choice of S and the product formula to obtain ∏_{v∈S} |α_{1}^{i_{1}n}α_{2}^{i_{2}n} ⋯ α_{t}^{i_{t}n}β_{1}^{j_{1}n} ⋯ β_{s}^{j_{s}n}|_{v} = 1. For M < i ≤ N_{1} we have

∏_{v∈S} |L_{i,v}(x_{n})|_{v} = ∏_{v∈S} |𝔠_{n}α_{2}^{i_{2}n} ⋯ α_{t}^{i_{t}n}β_{1}^{j_{1}n} ⋯ β_{s}^{j_{s}n}|_{v} ≤ 𝔠_{n} ≤ H_{n} ≤ C_{3}β_{1}^{n},

where we used the choice of S and the product formula once again. Further, for i ≤ M we have

∏_{v∈S\{p_{1},...,p_{r}}} |L_{i,v}(x_{n})|_{v} = ∏_{v∈S\{p_{1},...,p_{r}}} |𝔠_{n}|_{v} ≤ 𝔠_{n} ≤ H_{n} ≤ C_{3}β_{1}^{n},

where we have used that x_{i}(n) = 𝔡_{n}α_{2}^{i_{2}n} ⋯ α_{t}^{i_{t}n}β_{1}^{j_{1}n} ⋯ β_{s}^{j_{s}n}z_{n} and 𝔡_{n}z_{n} = 𝔠_{n} (as also just before).

Finally, in view of (21), we have for i ≤ M that

∏_{j=1}^{r} |L_{i,p_{j}}(x_{n})|_{p_{j}} = ∏_{j=1}^{r} |𝔡_{n}ϕ_{j_{i}}(n)|_{p_{j}} ≤ ∏_{j=1}^{r} |ϕ_{j_{i}}(n)|_{p_{j}} ≤ C_{2}α_{1}^{(1−f)n}.

Observe that

∏_{j=1}^{r} |𝔡_{n}|_{p_{j}} ≤ 1,

since 𝔡_{n} is an integer.

Plugging these estimates into (22), we finally obtain

∏_{v∈S} ∏_{i=1}^{N} |L_{i,v}(x_{n})|_{v} ≤ C_{4}𝔡_{n}^{N_{2}}β_{1}^{nN_{1}}α_{1}^{(1−f)Mn}.

Recall that we are assuming 𝔡_{n} ≤ α_{1}^{(1−ϵ)n}. Consequently,

(23)  ∏_{v∈S} ∏_{i=1}^{N} |L_{i,v}(x_{n})|_{v} ≤ C_{4} (α_{1}^{(1−ϵ)N_{2}+N_{1}C_{5}+(1−f)M})^{n} .

Now we choose k, f and at the end h to assure that the exponent of α_{1} in this equation is < 0. Observe that

(1 − ϵ)N_{2} + N_{1}C_{5} + (1 − f)M (24)

= (1 − ϵ)f ( \begin{matrix}t − 1 + f + h \\ t − 1 \end{matrix} ) ( \begin{matrix}s + k + 1 \\ s \end{matrix} )

−f ( \begin{matrix}t − 1 + h \\ t − 1 \end{matrix} ) ( \begin{matrix}s + k \\ s \end{matrix} )

+ [C_{5} ( \begin{matrix}t − 1 + f + h \\ t − 1 \end{matrix} ) + ( \begin{matrix}t − 1 + h \\ t − 1 \end{matrix} )] ( \begin{matrix}s + k \\ s \end{matrix} ) .

Since the function \binom{a+x}{a} is a polynomial in x of degree a, we consider first the above quantity as a polynomial in h. The leading coefficient is a polynomial in f whose leading coefficient is a constant multiple (where the positive constant is \frac{1}{(t−1)!} and therefore just depends on t) of

(25)  (1 − ϵ) ( \begin{matrix}s + k + 1 \\ s \end{matrix} ) − ( \begin{matrix}s + k \\ s \end{matrix} ) ,

which is smaller then zero if we choose

k > \frac{(1 − ϵ)s − ϵ}{ϵ}.

Afterwords we choose f so large that the coefficient of h^{t−1} in (24) is negative, and finally we choose h so large that (24) is negative as a whole.

Observe that (as in [4, p. 444]) this inequality is the crucial point of the method to work; it says that in the vector x_{n} the number of coordinates which are S-integral and not S-units, i.e. those involving z_{n}, is not too large.

Finally, we get that

(26)  ∏_{v∈S} ∏_{i=1}^{N} |L_{i,v}(x_{n})|_{v} ≤ C_{4}C_{6}^{n},

where C_{6} < 1 is a suitable positive constant independent of n, for infinitely many n.

In order to apply the Subspace Theorem we need an upper bound for ∥x_{n}∥ which is easily obtained by

∥x_{n}∥ ≤ C_{7}α_{1}^{(f+h)n}β_{1}^{(k+1)n} = C_{7}C_{8}^{n}.

The verification of the inequality in the Subspace Theorem (Proposition 1) follows now from

C_{4}C_{6}^{n} < (C_{7}C_{8}^{n})^{−δ} ,

which follows for small enough δ (such that C_{6}C_{8}^{δ} < 1) if n is large enough.

Now, from the Subspace Theorem (in the form of Proposition 1) it follows that there is a nontrivial linear relation of the form

A_{1}x_{1}(n) + … + A_{N}x_{N}(n) = 0

with A_{1}, …, A_{d} ∈ ℚ, not all zero, valid for infinitely many n. Thus we obtain a relation of the form z_{n}U_{n} = V_{n}, where

U_{n} = ∑_{j∈J} u_{j}α_{2}^{i_{2}n} ⋯ α_{t}^{i_{t}n}β_{1}^{j_{1}n} ⋯ β_{s}^{j_{s}n}

is a power sum with roots in the group generated by α_{2}, …, α_{t}, β_{1}, …, β_{s} and V_{n} is a power sum with roots in the group generated by α_{1}, …, α_{t}, β_{1}, …, β_{s}. Observe that (again by [14, Lemma 2]) U_{n} and V_{n} must be nontrivial power sums, because if all coefficients in V_{n} are equal to zero, then there are finitely many possibilities for n only, and the same is true if all coefficients in U_{n} are zero. Recall that by definition z_{n} = H_{n}/G_{n}, thus we have

H_{n}U_{n} = G_{n}V_{n}.

Since G_{n} and H_{n} are coprime (these follows from [14, Lemma 3]), we conclude that G_{n} divides U_{n} in the ring of power sums. This is a contradiction since in G_{n} there is a root (namely α_{1}) which is coprime to all roots of U_{n} and to all other roots of G_{n}. This contradiction completes our proof. □

References

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

[2] Y. Bugeaud and F. Luca, A quantitative lower bound for the greatest prime factor of (ab + 1)(bc + 1)(ca + 1), Acta Arith. 114 (2004), 275-294.

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

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

[5] P. Corvaja and U. Zannier, Finiteness of integral values for the ratio of two linear recurrences, Invent. Math. 149 (2002), 431-451.

[6] P. Corvaja and U. Zannier, On the greatest prime factor of (ab + 1)(ac + 1), Proc. Amer. Math. Soc. 131 (2003), 1705-1709.

[7] P. Corvaja and U. Zannier, A lower bound for the height of a rational function at S-unit points, Monatsh. Math. 144 (2005), 203-224.

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

[9] J.-H. Evertse and H.P. Schlickewei, The Absolute Subspace Theorem and linear equations with unknowns from a multiplicative group, Number Theory in Progress Vol. 1 (Zakopane-Kościelisko, 1997), 121-142, de Gruyter, Berlin, 1999.

[10] J.-H. Evertse and H.P. Schlickwei, A quantitative version of the absolute Subspace theorem, J. reine angew. Math. 548 (2002), 21-127.

[11] J.-H. Evertse, H.P. Schlickewei and W. M. Schmidt, Linear equations in variables which lie in a multiplicative group, Ann. Math. 155 (2002), 1-30.

[12] C. Fuchs, Quantitative finiteness results for Diophantine equations, PhD-thesis, TU Graz (2002).

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

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

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

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

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

[18] S. Hernández and F. Luca, On the greatest prime factor of (ab+1)(ac+1)(bc+1), Bol. Soc. Math. Mexicana 9 (2003), 235-244.

[19] K. Győry, A. Sárközy and C. L. Stewart, On the number of prime factors of integers of the form ab + 1, Acta Arith. 74 (1996), 365-385.

[20] C. Lech, A note on recurring series, Ark. Mat. 2 (1953), 417-421.

[21] F. Luca, On the greatest common divisor of u − 1 and v − 1 with u and v near S-units, Monats. Math., to appear.

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

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

[24] A. J. van der Poorten, Solution de la conjecture de Pisot sur le quotient de Hadamard de deux fractions rationnelles, C. R. Acad. Sci. Paris 306, Série I (1988), 97-102.

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

[26] H. P. Schlickewei, Multiplicities of recurrence sequences, Acta Math. 176 (1996), no. 2, 171-243.

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

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

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

[30] W. M. Schmidt, Zeros of linear recurrence sequences, Publ. Math. Debrecen 56 (2000), 609–630.

[31] A. Scremin, Diophantine inequalities with power sums, J. Théor. Nombres Bordeaux, to appear.

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

Clemens Fuchs Institut für Mathematik A Technische Universität Graz Steyrergasse 30/II 8010 Graz, Austria Current Adress: Mathematisch Instituut, Universiteit Leiden, Niels Bohrweg 1, Postbus 9512, 2300 RA Leiden, The Netherlands e-mail: fuchs@math.leidenuniv.nl, clemens.fuchs@tugraz.at