AN UPPER BOUND FOR THE G.C.D. OF TWO LINEAR RECURRING SEQUENCES^{∗}

CLEMENS FUCHS

Abstract. 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 G_{n} does not divide H_{n} in the ring of power sums. 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, whose cardinality 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. This quantifies a very recent result of Bugeaud, Corvaja and Zannier [1].

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, ….

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

We shall be interested in linear recurring sequences (G_{n}), where all roots of the characteristic polynomial of (G_{n}) are pairwisely different, which means that

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

for some c_{i}, α_{i} ∈ ℂ. 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.

Date: September 25, 2002.

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

2000 Mathematics Subject Classification: 11D45,11D61.

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.

The arithmetic properties of such recurring sequences have been widely investigated. We may mention the so-called Hadamard Quotient theorem (proved by van der Poorten, cf. [5]), 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 deep tools from Diophantine Approximation a stronger result. They showed that if (G_{n}), (H_{n}) are as above and if H_{n}/G_{n} ∈ ℤ for infinitely many n then there exists a recurring sequence (I_{n}) such that H_{n} = G_{n} · I_{n} for all n ∈ ℕ. This result can be found in [2].

The above diophantine problems arise of investigating the finiteness of the set of natural numbers n such that H_{n}/G_{n} is an integer. 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. [3]).

Recently, Bugeaud, Corvaja and Zannier [1] proved that the same techniques can be used 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

(5)  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

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

They remarked that due to the ineffectiveness of Schmidt’s Subspace Theorem, which is needed in the proof, the method does not allow to compute an integer n_{0} = n_{0}(a, b, ϵ) such that the above inequality holds for n > n_{0}.

The aim of the present paper is to remark that one can get at least some information about such an index n_{0}.

2. Results

We will use a quantitative version of Schmidt’s Subspace Theorem, which is due to Evertse [4], to show that one can calculate an index n_{0} such that the above inequalities are true for all n > n_{0} aside from a finite set of exceptions whose cardinality can also be bounded effectively.

Moreover, we will formulate the result of equation (5) for arbitrary linear recurring sequences in E_{ℤ}^{+} instead of (a^{n} − 1) and (b^{n} − 1) (see also [1], Remark 4).

Theorem 1. 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.

Remark 1. Let us mention that by G.C.D. we denote here the uniquely determined positive greatest common divisor of two integers.

Remark 2. The condition that G_{n} does not divide H_{n} in the ring E_{ℤ}^{+} is clearly needed and can be verified explicitly (see [2] and Lemma 3 below). A sufficient, but rather strong condition is that the roots α_{1}, …, α_{t}, β_{1}, …, β_{s} are multiplicatively independent.

Remark 3. In fact, c can be chosen arbitrarily within the range

\frac{\binom{t+h−1}{h}s}{\binom{t+h−1}{h}s + 1} < c < 1,

where h is an arbitrary integer with

h > max \{1, \frac{log β_{1}}{log α_{1} − log α_{2}} − 1\}

and t, s are as in Theorem 1.

In the case α_{2} = 1, i.e. t = 2, which means that we have

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

a stronger result on the constant c can be shown.

Corollary 1. 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 and let ϵ > 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}|^{1− \frac{1}{s} +ϵ},

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 ϵ.

Remark 4. Observe that this result includes the result of Bugeaud, Corvaja and Zannier [1] mentioned in the introduction, who showed that

(7)  G.C.D.(a^{n} − 1, b^{n} − 1) < (a^{n} − 1)^{\frac{1}{2} +ϵ} ,

provided that b is not a power of a, which is equivalent to the assumption that a^{n} −1 does not divide b^{n} −1 in the ring E_{ℤ}^{+} (which is just an elementary algebraic fact), and n is sufficiently large.

Remark 5. The number 1−1/s+ϵ in the exponent is best-possible, in view of the following example. Let c be an integer ≥ 2 and s ≥ 2 be arbitrary. Set G_{n} = c^{sn} − 1 and H_{n} = c^{(s−1)n} + … + c^{n} + 1. Then we have

G.C.D.(c^{sn} − 1, c^{(s−1)n} + … + c^{n} + 1) =
= c^{(s−1)n} + … + c^{n} + 1 ≫ c^{(s−1)n} = (c^{sn})^{1− \frac{1}{s}} .

In the most simplest case, when G_{n} = a^{n} − 1, H_{n} = b^{n} − 1 and a, b are multiplicatively independent integers ≥ 2, Bugeaud, Corvaja and Zannier [1] obtained a considerably better bound.

If we consider (as in the Theorem above) recurrences of the form

G_{n} = c_{1}α^{n} + c_{2}, and H_{n} = d_{1}β_{1}^{n} + d_{2}β_{2}^{n} + ⋯ + d_{s}β_{s}^{n},

then it is no longer sufficient to assume that α and β_{1} are multiplicatively independent, e.g. we have

\frac{6^{n} − 3^{n} + 2^{n} − 1}{2^{n} − 1} = 3^{n} − 1,

but the dominant roots are multiplicatively independent. Therefore we use a stronger condition to prove a similar result to that of Bugeaud, Corvaja and Zannier with recurrences (H_{n}) of arbitrary large order.

Theorem 2. 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 ϵ.

Remark 6. Observe that for other classes of linear recurrences even better upper bounds can be obtained. For example, let c ≥ 2 be an integer and let s > r ≥ 2 with G.C.D.(r, s) = 1. Then we have

G.C.D.(c^{(r−1)n} + … + c^{n} + 1, c^{(s−1)n} + … + c^{n} + 1) < C_{3},

for all n, where C_{3} is a constant independent of n. This follows from the fact that the polynomials (X^{r} − 1)/(X − 1) and (X^{s} − 1)/(X − 1) are relatively prime.

3. Auxiliary Results

The proofs of our theorems depend on a quantitative version of the Subspace Theorem due to J.-H. Evertse [4].

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

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

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

(8)  ∏_{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 [4]. 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 3. (Quantitative Subspace Theorem, Evertse) Let 0 < δ < 1 and consider the inequality for x ∈ K^{n}.

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

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

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

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

This is well known from combinatorics.

Next, we need an estimate for the number of 0’s occuring in a linear recurring sequence (this number is called the zero multiplicity of the recurrence).

Lemma 2. Let (G_{n}) be linear recurring sequence defined by G_{n} = c_{1}α_{1}^{n} + c_{2}α_{2}^{n} +⋯+c_{t}α_{t}^{n} where t ≥ 2, c_{i} are non-zero complex and α_{1} > ⋯ > α_{t} > 0 real numbers. Then the number of solutions of the equation

G_{n} = 0

is at most t.

Proof. We proof our assertion by induction on t. The case t = 1 is trivial. Now consider the function of one real variable

g(x) = c_{1} exp(x log(α_{1}/α_{t})) + ⋯ + c_{t−1} exp(x log(α_{t}/α_{t−1})) + c_{t}.

Clearly, the zeros of g at positive integral points are exactly the zeros of G_{n}. Now, g(x) is a differentiable function of the real variable x. So, between any two zeros of g one can find a zero of the derivative g′ of g. Since the derivative is a function of the same type, with t − 1 terms, the inductive hypothesis can be applied and the desired conclusion follows. □

Let us mention the remarkable result that there exists an upper bound (which does only depend on the order t, but in fact triply exponentially) for the zero multiplicity of arbitrary nondegenerate linear recurring sequences of complex numbers due to W.M. Schmidt [9].

Last but not least, we need some information about the structure of the ring of recurrences E_{ℤ}^{+} considered here. In fact, if 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 [5]) 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}. Now it is easy to show:

Lemma 3. Let (G_{n}), (H_{n}) ∈ E_{ℤ}^{+}. If α_{1} ⋯ α_{t} and β_{1} ⋯ β_{s} are coprime, then (G_{n}) and (H_{n}) are coprime in the ring E_{ℤ}^{+}.

Proof. Let 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 are integers. We denote by A the multiplicative group generated by α_{1}, …, α_{t}, β_{1}, …, β_{s} and we choose a basis γ_{1}, …, γ_{r} for A.

By the correspondance mentioned above we may write

G_{n} = g(γ_{1}^{n}, …, γ_{r}^{n}) and H_{n} = h(γ_{1}^{n}, …, γ_{r}^{n}),

with g, h ∈ ℂ[T_{1}, …, T_{r}] since the roots are integers. By the assumption that α_{1} ⋯ α_{t} and β_{1} ⋯ β_{s} are coprime it follows that g and h consist of different variables. But from this it is clear that the polynomials g and h are coprime and consequently the conclusion follows. □

4. Proof of Theorem 1

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

According to Lemma 2 the number of n such that G_{n} = 0 is at most t. In this case we have

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

and therefore these n must be excluded. Consequently, we can restrict ourselves to numbers n for which G_{n} ≠ 0. We write

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

where 𝔠_{n}, 𝔡_{n} are nonzero integers. Observe that we only consider those n for which G_{n} ≠ 0. Thus we have

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

We now assume that

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

for all n in a set Σ of natural numbers and for some c, which will be specified later. We will show that, provided n > C_{1} is large enough, that (11) can only hold for a finite number of n and we give an upper bound C_{2} for |Σ|. Then we can conclude that, provided n > C_{1}, we have

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

for all n ∉ Σ and using (10) we conclude

G.C.D.(G_{n}, H_{n}) = |G_{n}| · |𝔡_{n}|^{−1} < |G_{n}|^{c},

for all n ∉ Σ with |Σ| < C_{2}. Thus the assertion of our theorem will follow from this.

Fix an integer h > 0 and observe the following expansion

\frac{1}{G_{n}} = \frac{1}{c_{1}α_{1}^{n}} · ∑_{j=0}^{∞}(−1)^{j} (∑_{i=2}^{t} \frac{c_{i}}{c_{1}} (\frac{α_{i}}{α_{1}} )^{n})^{j} =

= \frac{1}{c_{1}α_{1}^{n}} · ∑_{j=0}^{h}(−1)^{j} (∑_{i=2}^{t} \frac{c_{i}}{c_{1}} (\frac{α_{i}}{α_{1}} )^{n})^{j} +

+\frac{1}{c_{1}α_{1}^{n}} · ∑_{j=h+1}^{∞}(−1)^{j} (∑_{i=2}^{t} \frac{c_{i}}{c_{1}} (\frac{α_{i}}{α_{1}} )^{n})^{j} =

= \frac{1}{c_{1}α_{1}^{n}} · ∑_{j=0}^{h}(−1)^{j} (∑_{i=2}^{t} \frac{c_{i}}{c_{1}} (\frac{α_{i}}{α_{1}} )^{n})^{j} +

+\frac{1}{c_{1}α_{1}^{n}} · \frac{(−1)^{h+1} (∑_{i=2}^{t} \frac{c_{i}}{c_{1}} (\frac{α_{i}}{α_{1}} )^{n})^{h+1}}{1 + ∑_{i=2}^{t} \frac{c_{i}}{c_{1}} (\frac{α_{i}}{α_{1}} )^{n}} .

Let us remark that for

n > C_{4} := \frac{log(2c̄)}{log α_{1} − log α_{2}}

we have

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

≥ |c_{1}||α_{1}|^{n}|1 − \underbrace{∑_{j=2}^{t} |\frac{c_{j}}{c_{1}} | |\frac{α_{j}}{α_{1}} |^{n}}_{≤c̄(α_{2}/α_{1})^{n}≤1/2 for n>C_{4}} | ≥ \frac{|c_{1}|}{2}α_{1}^{n},

where

c̄:= max \{1, |\frac{c_{2}}{c_{1}} | …, |\frac{c_{t}}{c_{1}} |\} .

Next we are going to approximate z(n) = H_{n}/G_{n} by a finite sum extracted from the above expansion. We define

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 to be chosen later. We may write

z̃(n) = ∑_{j=1}^{N} e_{j} (\frac{f_{j}}{b} )^{n} , n ∈ ±,

where the e_{j} ∈ ℚ^{∗} and the f_{j}, b are integers, b > 0, and the f_{j}/b are nonzero distinct rational numbers. Clearly z̃(n) is nondegenerate. In fact, we take

b = α_{1}^{h+1}.

Moreover, by Lemma 1 we have

(12)  N ≤ \binom{h + t − 1}{h}s =: C_{5}.

Now we estimate the approximation error we make, when we approximate z(n) through z̃(n). We have

|z(n) − z̃(n)| = (13)

= |H_{n} · \frac{1}{c_{1}α_{1}^{n}} · \frac{(−1)^{h+1} (∑_{i=0}^{t} \frac{c_{i}}{c_{1}} (\frac{α_{i}}{α_{1}} )^{n})^{h+1}}{1 + ∑_{i=2}^{t} \frac{c_{i}}{c_{1}} (\frac{α_{i}}{α_{1}} )^{n}} | =

= |H_{n} · \frac{(−1)^{h+1} (∑_{i=0}^{t} \frac{c_{i}}{c_{1}} (\frac{α_{i}}{α_{1}} )^{n})^{h+1}}{G_{n}} | ≤

≤ |H_{n}| · \frac{2}{|c_{1}|}α_{1}^{−n} (c̄\frac{α_{2}}{α_{1}} )^{n(h+1)} ≤ \frac{2d̃c̄^{h+1}}{|c_{1}|} β_{1}^{n}α_{1}^{−n} (\frac{α_{2}}{α_{1}} )^{n(h+1)} ,

where

d̃:= max {1, |d_{1}|, …, |d_{s}|} .

We choose the integer h so that

(14)  (\frac{α_{2}}{α_{1}} )^{h+1} β_{1} < 1.

To get this, we must have

h > max \{1, \frac{log β_{1}}{log α_{1} − log α_{2}} − 1\} .

Observe that from now on h is fixed and therefore also N, e_{j}, f_{j}, b are fixed. Now let S be the set of absolute values of ℚ consisting of ∞ and all primes dividing some of the f_{j} or b and therefore α_{1} ⋯ α_{t}β_{1} ⋯ β_{s}. Thus,

|S| ≤ ω(α_{1} ⋯ α_{t}β_{1} ⋯ β_{s}) := 1 + ∑_{p|α_{1}···α_{t}β_{1}···β_{s}} 1.

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

L_{0,∞}(X) = X_{0} − e_{1}X_{1} − ⋯ − e_{N}X_{N}

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

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

Observe that for each v ∈ S, the linear forms L_{0,v}, …, L_{N,v} are indeed linearly independent. We have

H(L_{i,v}) ≤ C_{7} := max{1, C_{6}H},

where

H := ∏_{v∈M_{ℚ}} max_{\begin{matrix}j = 1, …, s \\ 0 ≤ i_{2}, …, i_{t} ≤ h \\ 0 ≤ i_{2} + … + i_{t} ≤ h \end{matrix}} \{|d_{j} · \frac{c_{2}^{i_{2}} · . . . · c_{t}^{i_{t}}}{c_{1}^{i_{2}+...+i_{t}+1}} |_{v}\} ,

for v ∈ S, i = 0, …, h and where C_{6} = \sqrt{C_{5} + 1}. Furthermore ℚ(L_{i,v}) = ℚ which means that the coefficients just lie in ℚ and therefore

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

Moreover, we have

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

which yields

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

For n ∈ Σ define the vectors x_{n} = 𝔡_{n}(b^{n}z(n), f_{1}^{n}, …, f_{N}^{n}) ∈ ℤ^{N+1} and consider the double product

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

By putting

L_{0,∞}(x_{n}) = 𝔡_{n}b^{n} (z(n) − e_{1} (\frac{f_{1}}{b} )^{n} − … − e_{N} (\frac{f_{N}}{b} )^{n}) =
= 𝔡_{n}b^{n}(z(n) − z̃(n)),

we can rewrite the double product as

|L_{0,∞}(x_{n})|_{∞} · ( ∏_{v∈S\{∞}} |𝔠_{n}b^{n}|_{v}) (∏_{v∈S} ∏_{j=1}^{N} |𝔡_{n}f_{j}^{n}|_{v}) (∏_{v∈S} |x_{n}|_{v})^{−(N+1)} .

Observe that, due to our choice of S, the f_{j}^{n} are S-units for j ≥ 1. In particular, this implies

(∏_{v∈S} ∏_{j=1}^{N} |f_{j}^{n}|_{v}) = 1

and therefore

(15)  (∏_{v∈S} ∏_{j=1}^{N} |𝔡_{n}f_{j}^{n}|_{v}) ≤ |𝔡_{n}|^{N},

12 CLEMENS FUCHS

and

(16) ( ∏_{v∈S\{∞}} |𝔠_{n}b^{n}|_{v}) ≤ ∏_{v∈S\{∞}} |b^{n}|_{v} = b^{−n} = α_{1}^{−n(h+1)},

where we have use the product formula (8). Therefore we get using (13),

(15) and (16)

∏_{v∈S} ∏_{i=0}^{N} \frac{|L_{i,v}(x_{n})|_{v}}{|x_{n}|_{v}} ≤ |𝔡_{n}|^{N+1} \frac{2d̃c̄^{h+1}}{|c_{1}|} β_{1}^{n}α_{1}^{−n} (\frac{α_{2}}{α_{1}} )^{n(h+1)} (∏_{v∈S} |x_{n}|_{v})^{−(N+1)} .

Recall that we are assuming n ∈ Σ, i.e.

|𝔡_{n}| ≤ |G_{n}|^{1−c} ≤ c̃α_{1}^{n(1−c)},

where

c̃:= max{1, |c_{1}|c̄}.

Hence, we get

∏_{v∈S} ∏_{i=0}^{N} \frac{|L_{i,v}(x_{n})|_{v}}{|x_{n}|_{v}} ≤ C_{8} (β_{1}α_{1}^{(N+1)(1−c)−1} (\frac{α_{2}}{α_{1}} )^{h+1})^{n} (∏_{v∈S} |x_{n}|_{v})^{−(N+1)} ,

where

C_{8} := \frac{2c̃^{(C_{5}+1)}d̃c̄^{h+1}}{|c_{1}|} .

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

(17)  H(x_{n}) ≤ |x_{n}|_{∞} = |𝔡_{n}| max{|b^{n}z(n)|, |f_{1}^{n}|, …, |f_{N}^{n}|},

where we have used the choice of S. By using the fact that

1 ≤ |b^{n}𝔠_{n}| ≤ |b^{n}H_{n}| ≤ d̃α_{1}^{n(h+1)}β_{1}^{n}

and |f_{j}^{n}| ≤ α_{1}^{hn} for j = 1, …, N we get

(18)  H(x_{n}) ≤ c̃d̃(α_{1}^{(h+1)}β_{1})^{n} .

Let us point out that the constant does not depend on n.

We now choose 0 < δ < 1 so that

(19)  (α_{2}α_{1}^{−1})^{h+1}β_{1} (α_{1}^{(h+1)}β_{1})^{δ} < 1.

This will be fulfilled for

0 < δ < \frac{(h + 1)[log α_{1} − log α_{2}] − log β_{1}}{(h + 1) log α_{1} + log β_{1}} ,

which is possible in view of (14).

In view of the bound for the double product we derived and (18), the verification of (9) of the Quantitative Subspace Theorem 3 will follow from

C_{8} (β_{1}α_{1}^{(N+1)(1−c)−1}(α_{2}α_{1}^{−1})^{h+1})^{n} < (c̃d̃(α_{1}^{(h+1)}β_{1})^{n})^{−δ} ,

which is the same as

(α_{1}^{(N+1)(1−c)−1}(α_{2}α_{1}^{−1})^{h+1}β_{1} (α_{1}^{(h+1)}β_{1})^{δ})^{n} < (C_{8}(c̃d̃)^{δ})^{−1} .

However, this latter inequality follows from (19) for

n > C_{9} := \begin{matrix}log & (C_{8}(c̃d̃)^{δ}) \\ log & (α_{1}^{(C_{5}+1)(c−1)+1+(h+1)(1−δ)}α_{2}^{−(h+1)}β_{1}^{−(1+δ)}) \end{matrix},

whenever we have

\frac{C_{5}}{C_{5} + 1} < c < 1,

which implies that

(N + 1)(1 − c) − 1 ≤ (C_{5} + 1)(1 − c) − 1 < 0.

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

g ≤ C_{10} := (2^{60C_{5}^{2}}δ^{−7C_{5}})^{ω(α_{1}···β_{s})} (2 + log log 2C_{7}),

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}^{N} u_{i} (\frac{f_{i}}{b} )^{n} = 0, u_{i} ∈ ℚ, i = 1, …, N.

By Lemma 2 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

N ≤ C_{5},

which follows from Lemma 2.

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

(20)  z(n) = ∑_{i=1}^{N} v_{i} (\frac{f_{i}}{b} )^{n} , v_{i} ∈ ℚ, i = 1, …, N.

Let us assume that this equality holds for infinitely many n. In that case we would get a relation of the form

b^{n}H_{n} = G_{n}R_{n},

where R_{n} is a power sum with positive roots, valid for infinitely many n. This in turn implies the validity of the same relation for all n, which is excluded by the hypothesis. An upper bound follows now from the fact that the left hand side of

(21)  H_{n} − G_{n} · ∑_{i=1}^{N} v_{i} (\frac{f_{i}}{b} )^{n} = 0

is a nontrivial recurring sequence with positive roots and therefore equation (21) can hold for at most C_{5} · t + s many n by Lemma 2.

The the number of exceptions |Σ| can be bounded by

C_{2} := t + (2^{60C_{5}^{2}}δ^{−7C_{5}})^{ω(α_{1}···β_{s})} (2 + log log 2C_{7}) (C_{5}(t + 1) + s)

and C_{1} := max{C_{4}, C_{9}}. This completes the proof. □

5. Proof of Corollary 1

The proof is essentially the same as the proof of Theorem 1. We use the same notations as in the proof before and mention only the part that must be modified.

In this case we approximate z(n) by:

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

which we may write as

z̃(n) = ∑_{j=1}^{N} e_{j} (\frac{f_{j}}{b} )^{n} , n ∈ ±,

where the e_{j} ∈ ℚ^{∗} and the f_{j}, b are integers, b > 0, and the f_{j}/b are nonzero distinct rational numbers. Consequently, we have the estimate

(22)  N ≤ (h + 1)s.

The approximation error is

|z(n) − z̃(n)| ≤ \frac{2d̃c̄^{h+1}}{|c_{1}|} β_{1}^{n}α_{1}^{−n} (α_{1}^{−n})^{h+1} ,

where the constants are defined as before.

Now, if we set

c = 1 − \frac{1}{s} + ϵ,

we have

α_{1}^{s(1−c)−1} < 1

and we therefore can choose h such that

(23)  (α_{1}^{s(1−c)−1})^{h+1} β_{1} < 1.

We choose linear forms as above and get

∏_{v∈S} ∏_{i=0}^{N} \frac{|L_{i,v}(x_{n})|_{v}}{|x_{n}|_{v}} ≤ C_{8} (β_{1}α_{1}^{(N+1)(1−c)−1−(h+1)})^{n} (∏_{v∈S} |x_{n}|_{v})^{−(N+1)} =

= C_{8} (β_{1}α_{1}^{(h+1)(s(1−c)−1)−c})^{n} (∏_{v∈S} |x_{n}|_{v})^{−(N+1)} .

As above we have

H(x_{n}) ≤ |x_{n}|_{∞} = |𝔡_{n}| max{|b^{n}z(n)|, |f_{1}^{n}|, …, |f_{N}^{n}|} ≤ c̃d̃(α_{1}^{(h+1)}β_{1})^{n} ,

and we choose 0 < δ < 1 so that

(α_{1}^{(s(1−c)−1)})^{h+1} β_{1} (α_{1}^{(h+1)}β_{1})^{δ} < 1.

This is possible in view of (23). With this, condition (9) of the Quantitative Subspace Theorem 3 is valid if n > C_{9}.

The rest of the arguments are as above, the assertion follows and so the proof is finished. □

6. Proof of Theorem 2

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

First observe that the only zero of G_{n} can be

n = \frac{log (−c_{2}/c_{1})}{log α}.

We fix a positive integer k. Let us denote by J = {j = (j_{1}, …, j_{s}) ∈ ℕ^{s} : 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 | = \binom{s + k − 1}{k}.

For every j ∈ J, we define

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

where we have abbreviated \underline{β}^{(j_{1},...,j_{s})} = β_{1}^{j_{1}} ⋯ β_{s}^{j_{s}}. Moreover, we write

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

where 𝔠_{j,n}, 𝔡_{n} are integers. Since G_{n} divides H_{j,n} for all j and all positive integers n we may choose 𝔡_{n} to be the denominator of H_{n}/G_{n}.

We now assume that ϵ > 0 is given and that

(24)  𝔡_{n} ≤ |G_{n}|^{(1−ϵ)}

for all n in a set Σ of natural numbers. We will again show that, provided n > C_{1} is large enough, that (24) can only hold for a at most C_{2} many numbers n. Then we conclude

G.C.D.(G_{n}, H_{n}) = |G_{n}| · |𝔡_{n}|^{−1} < |G_{n}|^{ϵ},

provided that n > C_{1}, for all n ∉ Σ with |Σ| ≤ C_{2}. This will conclude our proof.

For a fixed integer h > 1 we consider the expansion

\frac{1}{G_{n}} = \frac{1}{c_{1}α^{n}} ∑_{i=0}^{∞}(−1)^{i} (\frac{c_{2}}{c_{1}} )^{i} α^{−ni} =

= ∑_{i=1}^{h}(−1)^{i−1} \frac{c_{2}^{i−1}}{c_{1}^{i}} α^{−ni} + \frac{(−1)^{h}(\frac{c_{2}}{c_{1}} )^{h}α^{−nh}}{G_{n}} .

For

n > \frac{log (2 |c_{2}/c_{1}|)}{log α} =: C_{4}

we have

|G_{n}| = |c_{1}α^{n} + c_{2}| ≥ \frac{|c_{1}|}{2}α^{n}.

For a given index j ∈ J we thus obtain, on multiplying by H_{j,n},

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

≤ |H_{j,n}| · \frac{2|c_{2}|^{h}}{|c_{1}|^{h+1}} α^{−n(h+1)} ≤ \frac{2d̃|c_{2}|^{h}}{|c_{1}|^{h+1}} β_{1}^{(k+1)n}α^{−n(h+1)}.

Let us write C_{10} for the constant appearing in the last expression. We want to apply now the Subspace Theorem, viewing the left side of (25) as a “small” linear form. We shall consider several such linear forms, corresponding to values of j ∈ J with k large enough. The idea of choosing this linear forms is similar to that used in [3].

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.

Now, let S consist of ∞ and all primes dividing α or one of the β_{i}, i = 1, …, s. Second, we put

N = \binom{s + k − 1}{k} + h\binom{s + k}{k + 1}.

Observe that the first summand is equal to the cardinality of J and the second summand is an upper bound for the number of nonzero terms in the double sum above. For convenience we shall denote vectors in ℤ^{N} by writing

x = (x_{1}, …, x_{N}) = (z_{1}, …, z_{M}, y_{1}, …, y_{N−M}).

We define for every s ∈ S, N independent linear forms in X = (X_{1}, …, X_{N}) as follows. For j = 1, …, M let j ∈ J be the j-th vector with respect to the lexicographical ordering and put

L_{j,∞}(X) = Z_{j} − ∑_{i=1}^{h} ∑_{l=1}^{s}(−1)^{i−1}d_{l} \frac{c_{2}^{i−1}}{c_{1}^{i}} Y_{i,l,j},

while, for (i, v) ∉ {(1, ∞), …, (M, ∞)} we put

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

Observe that for each s ∈ S, the linear forms L_{1,v}, …, L_{N,v} are indeed linearly independent. We have

H(L_{i,v}) ≤ C_{11} := \sqrt{N + 1} ∏_{v∈M_{ℚ}} max_{j} \{|d_{j} \frac{c_{2}^{h}}{c_{1}^{h}} |_{v} , 1\} .

for v ∈ S, i = 1, …, N. Furthermore ℚ(L_{i,v}) = ℚ and therefore

[ℚ(L_{i,v}) : ℚ] = 1 ∀v ∈ S, i = 1, …, N.

Moreover, we have

det(L_{1,v}, …, L_{N,v}) = 1,

which yields

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

For n ∈ Σ define the vectors x_{n} by

𝔡_{n}α^{hn}(z_{j_{1}}(n), …, z_{j_{M}} (n), …, β_{1}^{j_{1}n}β_{2}^{j_{2}n} ⋯ β_{s}^{j_{s}n}β_{l}^{n}α^{−in}, …),

where the indices vary lexicographically over all tuples j ∈ J, l = 1, …, s and i = 1, …, h. Note that x_{n} ∈ ℤ^{N} and that we have

L_{i,∞}(x_{n}) = ϕ_{j_{i}}(n), i = 1, …, M

and consider the double product

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

First observe that we have for i > M

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

where j_{1}, …, j_{s}, l and i are suitable integers. Observe that we have used our choice of S again and the product formula to obtain ∏_{v∈S} |β_{1}^{j_{1}n} ⋯ β_{s}^{j_{s}n}β_{l}^{n}α^{(h−i)n}|_{v} = 1.

Further, for i ≤ M we have x_{i} = 𝔡_{n}α^{hn}z_{j_{i}}(n) = 𝔠_{j_{i},n}α^{hn}, whence

∏_{v∈S\{∞}} |L_{i,v}(x_{n})|_{v} ≤ α^{−hn}.

Also, in view of (25), we have, again for i ≤ M,

|L_{i,∞}(x_{n})| ≤ C_{12}|𝔡_{n}|β_{1}^{(k+1)n}α^{−n}.

Plugging these estimates into (26), we finally obtain

∏_{v∈S} ∏_{i=1}^{N} |L_{i,v}(x_{n})|_{v} ≤ |𝔡_{n}|^{N−M} ∏_{v∈S} ∏_{i=1}^{M} |L_{i,v}(x_{n})|_{v} ≤

≤ C_{12}|𝔡_{n}|^{M}β_{1}^{(k+1)Mn}α^{−Mn}|𝔡_{n}|^{N−M}α^{−hMn} =
= C_{12}|𝔡_{n}|^{N}α^{−(h+1)Mn}β_{1}^{(k+1)Mn}.

Recall that we are assuming n ∈ Σ, i.e.

|𝔡_{n}| ≤ |G_{n}|^{1−ϵ} ≤ c̃α^{(1−ϵ)n}.

Hence we have (27)

∏_{v∈S} ∏_{i=1}^{N} \frac{|L_{i,v}(x_{n})|_{v}}{|x_{n}|_{v}} ≤ C_{12}c̃^{N}α^{(1−ϵ)Nn}α^{−(h+1)Mn}β_{1}^{(k+1)Mn} (∏_{v∈S} |x_{n}|_{v})^{−N} .

Let us point out here that the constant does not depend on n. We now choose the integer k such that

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

This implies that

α^{(1−ϵ)N−(h+1)M} ≤ α^{((1−ϵ) \frac{s+k}{k+1} −1)Mh} < 1.

AN UPPER BOUND FOR THE G.C.D. 19

We choose the integer h so that

(28)  α^{((1−ϵ) \frac{s+k}{k+1} −1)Mh}β_{1}^{(k+1)M} < 1,

i.e. we have

h > \frac{(k + 1) log β_{1}}{((1 − ϵ)\frac{s+k}{k+1} − 1) log α}.

This is possible because of our choice of k.

On the other side, since in any case |𝔡_{n}| < |G_{n}|, we get

H(x_{n}) ≤ ∏_{v∈S} |x_{n}|_{v} ≤ max_{i=1,...,N}{|x_{i}|},

where we have used our choice of S, the fact that two norms on ℚ^{N} are equivalent and that the x_{i} are integers. Now we have

|𝔠_{j_{i},n}α^{hn}| ≤ |H_{j_{i},n}α^{hn}| ≤ d̃β_{1}^{(k+1)n}α^{hn}

and

|β_{1}^{j_{1}} ⋯ β_{s}^{j_{s}}β_{l}^{n}α^{(h−i)n}𝔡_{n}| ≤ c̃β_{1}^{(k+1)n}α^{(h−1)n}α^{(1−ϵ)n} ≤ c̃β_{1}^{(k+1)n}α^{hn}.

Thus we can conclude

(29)  H(x_{n}) ≤ C_{13}β_{1}^{(k+1)n}α^{hn},

where the constant C_{13} := max{c̃, d̃} does not depend on n.

We now choose 0 < δ < 1 so that

(30)  α^{((1−ϵ) \frac{s+k}{k+1} −1)Mh}β_{1}^{(k+1)M} (β_{1}^{k+1}α^{h})^{δ} < 1.

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

δ < \begin{matrix}log & (α^{((1−ϵ) \frac{s+k}{k+1} −1)Mh}β_{1}^{(k+1)M}) \\ log & (β_{1}^{k+1}α^{h}) \end{matrix}.

The verification of (9) of the Quantitative Subspace Theorem 3 will follow from

C_{12}c̃^{N}α^{((1−ϵ) \frac{s+k}{k+1} −1)Mhn}β_{1}^{(k+1)Mn} < (C_{13}α^{hn}β_{1}^{(k+1)n})^{−δ} ,

in view of (27) and (29). This is the same as

(α^{((1−ϵ) \frac{s+k}{k+1} −1)Mhn}β_{1}^{(k+1)Mn} (β_{1}^{k+1}α^{h})^{δ})^{n} < (C_{12}c̃^{N}C_{13}^{δ})^{−1} . This inequality follows from (30) for

n > C_{14} := \begin{matrix}log & (C_{12}c̃^{N}C_{13}^{δ}) \\ log & (α^{((1−ϵ) \frac{s+k}{k+1} −1)Mh}β_{1}^{(k+1)M} (β_{1}^{k+1}α^{h})^{δ}) \end{matrix}.

By the Quantitative Subspace Theorem 3 we can conclude, that there exist finitely many non-zero linear forms Λ_{1}(X), …, Λ_{g}(X) with coefficients in ℚ and with

g ≤ C_{15} := (2^{60N^{2}}δ^{−7N})^{ω(αβ_{1}···β_{s})} (2 + log log 2C_{11}),

such that each vector x_{n} is a zero of some Λ_{j}. Let us consider a hyperplane given by

Λ(X) = u_{1}Z_{1} + … + u_{M}Z_{M} + ∑_{i=1}^{N−M} v_{i}Y_{i} = 0,

where the coefficients are rational numbers, not all zero. Substituting from the definition of x_{n}, we get the equation

(31)  α^{hn}H_{n} ∑_{j∈J} u_{j}β_{1}^{j_{1}} ⋯ β_{s}^{j_{s}} = G_{n} · ∑_{i,l,j} v_{i,l,j}β_{1}^{j_{1}} ⋯ β_{s}^{j_{s}}β_{l}^{n}α^{(h−i)n},

where the sum runs lexicographically over j = (j_{1}, …, j_{s}) ∈ J , l = 1, …, s and i = 1, …, h and is valid for some integers n ∈ Σ. But this equation can only hold identically, which means for all n ∈ ℕ, or it has a finite number of solutions n ∈ ℕ. Therefore, we first assume that all u_{j} are equal to zero then we have

∑_{i,l,j} v_{i,l,j}β_{1}^{j_{1}} ⋯ β_{s}^{j_{s}}β_{l}^{n}α^{(h−i)n} = 0,

and at least one of the v_{i,l,j} is different from zero. This can hold for at most N − M many n by Lemma 2. Second, we assume that all v_{i,l,j} are equal to zero than we have

α^{hn}H_{n} · ∑_{j∈J} u_{j}β_{1}^{j_{1}} ⋯ β_{s}^{j_{s}} = 0,

which can hold for at most s + M many n by Lemma 2. If there is at least one non-zero coefficient at both sides of (31) than we can conclude (observe that by Lemma 3 G_{n} and H_{n} are coprime) that G_{n} divides

∑_{j∈J} u_{j}β_{1}^{j_{1}} ⋯ β_{s}^{j_{s}}

in the ring E_{ℤ}^{+} which is impossible by Lemma 3, since α and β_{1} ⋯ β_{s} are coprime, or (31) holds for at most N many n.

Finally the number of exceptions can be bounded by

C_{2} := 1 + C_{15} (s + 2N)

and C_{1} can be choose as C_{1} := max{C_{4}, C_{14}}. So, the proof is finished. □

7. Acknowledgement

The author would like to thank Prof. P. Corvaja for suggestions improving the paper. Especially he is grateful for his help choosing appropriate linear forms in the proof of Theorem 2.

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, to appear.

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

[3] P. Corvaja and U. Zannier, Finiteness of integral values for the ratio of two linear recurrences, manuscript.

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

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

[6] 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 (1998), 97-102.

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

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

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

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