DIOPHANTINE TRIPLES WITH VALUES IN BINARY RECURRENCES

CLEMENS FUCHS, FLORIAN LUCA, AND LASZLO SZALAY

Abstract. In this paper, we study triples a, b and c of distinct positive integers such that ab + 1, ac + 1 and bc + 1 are all three members of the same binary recurrence sequence.

2000 Mathematical Subject Classification: 11D72, 11D61, 11B37

1. Introduction

A Diophantine m-tuple is a set {a_{1}, …, a_{m}} of positive integers such that a_{i}a_{j} + 1 is a perfect square (i.e. a square of a number in ZZ) for all 1 ≤ i < j ≤ m. Finding such sets was already investigated by Diophantus and he found the rational quadruple {1/16, 33/16, 68/16, 105/16}. The first quadruple in integers, the set {1, 3, 8, 120}, was found by Fermat. Infinitely many Diophantine quadruples are known and it is conjectured that there is no Diophantine quintuple. This was almost proved by Dujella [7], who showed that there can be at most finitely many Diophantine quintuples and all of them are, at least in theory, effectively computable. Several variants of this problem have been studied in the past. For example, Bugeaud and Dujella [2], proved upper bounds for the size m of sets of positive integers with the property that the product of any two distinct elements plus one is a perfect k-th power for fixed k, namely m is bounded by 7 for k = 3, by 5 for k = 4, by 4 for 5 ≤ k ≤ 176, and by 3 for k ≥ 177. Another variant studied previously is concerned with perfect powers instead of squares or k-th powers for fixed k. The second author proved that the abc-conjecture implies that the size of such sets is bounded by an absolute constant, whereas unconditionally there are bounds depending on the largest element in the set (see [13] and the papers cited therein). For further results on Diophantine m-tuples and its variants, we refer to [8].

In this paper, we treat another variant of this problem. Let r and s be nonzero integers such that Δ = r^{2} + 4s ≠ 0. Let (u_{n})_{n≥0} be a binary recurrence sequence of integers satisfying the recurrence

Date: January 9, 2008.

u_{n+2} = ru_{n+1} + su_{n} for all n ≥ 0.

It is well-known that if we write α and β for the two roots in C of the characteristic equation x^{2} − rx − s = 0, then there exist constants γ, δ ∈ IK = Q[α] such that

(1)  u_{n} = γα^{n} + δβ^{n}

holds for all n ≥ 0. We shall assume in what follows that the sequence (u_{n})_{n≥0} is nondegenerate, which means that γδ ≠ 0 and α/β is not root of unity. We shall also make the convention that |α| ≥ |β|. Note that |α| > 1.

Here, we look for Diophantine triples with values in the set U = {u_{n} : n ≥ 0}, namely sets of three distinct positive integers {a, b, c}, such that ab+1, ac+1, bc+1 are all in U. Clearly, there are always such pairs as e.g. {1, u_{n}−1}. Note that if u_{n} = 2^{n}+1 for all n ≥ 0, then there are infinitely many such triples (namely, take a, b, c to be any distinct powers of two); in this situation, we can even get arbitrarily large sets {a_{1}, …, a_{m}} with the property that a_{i}a_{j} +1 ∈ U for all 1 ≤ i < j ≤ m. Our main result is that the above example is representative for the sequences (u_{n})_{n≥0} with real roots for which there exist infinitely many Diophantine triples with values in U. More precisely we prove the following.

Theorem 1. Assume that (u_{n})_{n≥0} is a nondegenerate binary recurrence sequence with Δ > 0 such that there exist infinitely many sextuples of nonnegative integers (a, b, c; x, y, z) with 1 ≤ a < b < c such that

(2)  ab + 1 = u_{x},  ac + 1 = u_{y},  bc + 1 = u_{z}.

Then β ∈ {±1}, δ ∈ {±1}, α, γ ∈ ZZ. Furthermore, for all but finitely many of the sextuples (a, b, c; x, y, z) as above one has δβ^{z} = δβ^{y} = 1 and one of the following holds:

(i) δβ^{x} = 1. In this case, one of γ or γα is a perfect square; (ii) δβ^{x} = −1. In this case, x ∈ {0, 1}.

Theorem 1, of course, implies that there are only finitely many triples of positive integers such that the product of any two plus one is in U, except in the cases described (and these cases really occur as we saw above). We mention that the problem can be reformulated as a Diophantine equation of polynomial-exponential type with three independent exponential variables and three additional polynomial variables, namely

(ab + 1 − u_{x})^{2} + (ac + 1 − u_{y})^{2} + (bc + 1 − u_{z})^{2} = 0.

It is well-known that the Subspace theorem is a powerful tool for such problems, e.g. it was also used to classify the solutions to the equation Au_{x} +Bu_{y} +Cu_{z} = 0 for fixed A, B, C ∈ ZZ in [17] (see [18] for a survey on such equations). A new development in applying the Subspace theorem was startet by Corvaja and Zannier (see [22, 23, 10]), and their techniques will also be used in our proof (especially we use [6, 11] and [5]). We could not prove any finiteness result for the case when Δ < 0, the reason being that in this case there is no dominant root in the polynomial-exponential Diophantine equation, which is the main restriction in applying the Subspace theorem with these techniques at present.

For example, it follows for the particular case of the Fibonacci sequence (F_{n})_{n≥0}, given by (r, s) = (1, 1), F_{0} = 0 and F_{1} = 1, that there are at most finitely many triples of positive integers such the product of any two plus one is a Fibonacci number F_{n}. In the subsequent paper [16] the second and third author show that there is in fact no triple of distinct positive integers a, b and c such that ab + 1, ac + 1 and bc + 1 are all three Fibonacci numbers.

2. A bird’s-eye-view of the proof

For the convenience of the reader we will give an overview of the proof of the theorem, since the proof is rather long and becomes more and more technical towards the end. We mention that throughout the paper the symbols o, O, ∼, ≪, ≫, ≍, are used with their usual meaning.

Since Δ > 0, it follows that |α| > |β|. We shall show that one may assume that both α and γ are positive. We assume that we have infinitely many solutions (a, b, c; x, y, z) to equation (2). Then z → ∞, x < y < z if z is sufficiently large, and c | gcd(u_{y} − 1, u_{z} − 1). The case δβ^{z} = 1 is not hard to handle. When δβ^{z} ≠ 1, results from Diophantine approximations relying on the Subspace Theorem, as the finiteness of the number of solutions of nondegenerate unit equations with variables in a finitely generated multiplicative group and bounds for the greatest common divisors of values of rational functions at units points in the number fields setting, allow us to reduce the problem to elementary considerations concerning polynomials. By using unit equations, we first conclude that log b and log c have the same orders of magnitude, therefore x ≍ y ≍ z. Then we show that a is also large which will come in handy lateron. These preliminaries can be found in the next two sections (see Section 3 and 4). Next, since the multi-recurrence ((u_{x} − 1)(u_{y} − 1)(u_{z} − 1))_{x<y<z} has a dominant root and comparable positive integer subscripts, a result of the first author from [11] tells us that for infinitely many of our solutions, the positive integer abc is a linear combination of finitely many of the monomials in α^{x}, β^{x}, α^{y}, β^{y}, α^{z}, β^{z} appearing in the formal Puiseux expansion of \sqrt{(u_{x} − 1)(u_{y} − 1)(u_{z} − 1)}. Hence, the relation (abc)^{2} = (u_{x} − 1)(u_{y} − 1)(u_{z} − 1), may now be regarded as a unit equation with unknowns in the multiplicative group generated by α and β, and it remains to deal with it (equivalently, it can be viewed as the problem of calculating the zeroes of a multi-recurrence; this is not an easy task, see e.g. Remark 5 in [11]). The proof now falls in two distinct cases: the case when α and β are multiplicatively independent or multiplicatively dependent. In case α and β are multiplicatively independent (which together with the considerations outlined above is handled in Section 5), listing the first few dominant units in both sides of the equation and identifying them, one gets a few linear relations among the exponents x, y and z. It turns out that if one goes back to the original equations, these few linear relations are enough to get a contradiction in this case. In case when α and β are multiplicatively dependent (see Section 6), we argue without going back to the before mentioned multi-recurrence. Instead, we show first in an elementary way (using just the pigeon hole principle), that there are only finitely many lines in ZZ^{3} the union of which contain all possible triples (x, y, z) leading to a solution of our problem. Since we have infinitely many solutions, we may assume that for infinitely many of them we have x = d_{1}t + e_{1}, y = d_{2}t + e_{2}, z = d_{3}t + e_{3}, where d_{1}, d_{2}, d_{3}, e_{1}, e_{2}, e_{3} are fixed integers with the first three positive and t is some positive integer variable. But in this case, since α and β are also multiplicatively dependent, it follows that u_{x} − 1, u_{y} − 1, u_{z} − 1 are all polynomials in ρ^{t}, where ρ is some number such that α = ρ^{i} and β = ±ρ^{j} for some integers i and j. Since any two of these numbers have large greatest common divisors, it follows that these three polynomials have common roots any two of them and their product is the square of some other polynomial. The proof ends by a careful analysis of how these polynomials might share their roots with a view of getting a contradiction.

3. Preparations

Let IL be any algebraic number field and S be a finitely generated multiplicative subgroup of IL. Given N ≥ 1, a unit equation is an equation of the form

(3)  ∑_{i=1}^{N} a_{i}x_{i} = 1,

where a_{1}, …, a_{N} ∈ IL are fixed nonzero coefficients and x_{1}, …, x_{N} ∈ S. A solution (x_{1}, …, x_{N}) of the above unit equation is called nondegenerate if ∑_{i∈I} a_{i}x_{i} ≠ 0 for all proper subsets I ∈ {1, …, N}. In such a case, we will call the unit equation (3) itself nondegenerate. We record the following result about unit equations.

Lemma 2. There are only finitely many nondegenerate solutions x = (x_{1}, …, x_{N}) ∈ S^{N} to the unit equation (3).

We will use Lemma 2 several times in what follows. In our case (and for the rest of the paper), S is the multiplicative group generated by α and β inside IK; i.e., S = {α^{n}β^{m} : n, m ∈ ZZ}. In this special case (3) can be rewritten as

(4)  ∑_{i=1}^{N} a_{i}α^{n_{i}}β^{m_{i}} = 1

to be solved in integers n_{1}, …, n_{N}, m_{1}, …, m_{N}. Lemma 2 tells us that there are only finitely many (n_{1}, …, n_{N}, m_{1}, …, m_{N}) ∈ ZZ^{2N} such that no subsum on the left of (4) vanishes. In the case when the right hand side of (4) is 0, then Lemma 2 implies that the differences n_{i} − n_{j}, m_{i} − m_{j} are bounded for all 1 ≤ i < j ≤ N and for all n_{1}, …, n_{N}, m_{1}, …, m_{N} such that no subsum on the left vanishes. We mention that the set of all IK-linear combinations of elements in S is easily understood: it is isomorphic to IK[X^{±1}, Y^{±1}] in the case when α and β are multiplicatively independent and isomorphic to IK[X^{±1}] otherwise.

We will also need the following lemma. Assume that (u_{n})_{n≥0} is the nondegenerate binary recurrent sequence whose general term is given by the formula (1). Assume further that Δ > 0, therefore that |α| > |β|. We have the following result.

Lemma 3. There exists constants κ_{0} ∈ (0, 1) and z_{0} such that if y and z are positive integers with z > max{y, z_{0}}, δβ^{z} ≠ 1 and u_{y} ≠ 1, then

gcd(u_{y} − 1, u_{z} − 1) < |α|^{κ_{0}z}.

Proof. Clearly, |u_{y} − 1| ≪ |u_{y}| ≪ |α|^{y}. Thus, if for some small ε > 0 but fixed we have y < (1 − ε)z, then we can take κ_{0} = 1 − ε/2 and the desired inequality holds for large z. From now on, we shall assume that the inequalities (1 − ε)z < y < z hold with some small ε > 0 to be fixed later. Put λ = z − y ∈ (0, εz). Let D = gcd(u_{y} − 1, u_{z} − 1). Then

(5)  D | γα^{y} + δβ^{y} − 1 and D | γα^{y+λ} + δβ^{y+λ} − 1.

Multiplying the first divisibility relation above (5) by the algebraic integer α^{λ}, we also have that D | γα^{y+λ} + δβ^{y}α^{λ} − α^{λ}. From this and the second relation (5), we get

(6)  D | δβ^{y}(α^{λ} − β^{λ}) − (α^{λ} − 1).

Let us first assume that the algebraic integer appearing in the right hand side above is zero. We then get

(7)  1 = α^{λ} + δβ^{z} − δβ^{y}α^{λ}.

This is a unit equation in four terms. If it is nondegenerate, then it has only finitely many solutions. Thus, taking z_{0} sufficiently large, it follows that if equation (7) holds, then it must be degenerate. In this case, one of α^{λ}, δβ^{z}, or −δβ^{y}α^{λ} equals 1. The case δβ^{z} = 1 is excluded by hypothesis. The case α^{λ} = 1 leads to λ = 0, which is impossible. Finally, the case −δβ^{y}α^{λ} = 1 leads to δβ^{z} + α^{λ} = 0, or |α|^{λ} = |δ||β|^{z}. If |β| ≠ 1, we then get that z log |β| + log |δ| = λ log |α|. Since λ < εz, it follows that the above relation is impossible for large z if we choose ε < log |β|/(2 log |α|). Thus, if z > z_{0}, then we must have |β| = 1, therefore |α|^{λ} = |δ|. Now the relation −δβ^{y}α^{λ} = 1 leads to |α|^{λ} = |δ|^{−1}. Thus, |α|^{λ} = |δ| = |δ|^{−1}, leading to |δ| = 1. We next get |α|^{λ} = 1, therefore λ = 0, which is a contradiction.

From now on, we may assume that z is sufficiently large, and therefore that relation (7) does not hold.

Assume first that IK = Q. Then the nonzero integer appearing in the right hand side of (6) is of size

|δβ^{y}(α^{λ} − β^{λ}) − (α^{λ} − 1)| ≪ exp(y log |β| + λ log |α|)
≤ exp (z (log |β| + ε log |α|)) < |α|^{κ_{0}z},

for a certain κ_{0} < 1 (depending on ε) provided that we first choose ε < (log |α| − log |β|)/ log |α|, and then we let z be sufficiently large. This finishes the proof of the lemma in this case.

Assume now that IK is quadratic. Conjugating (6) by the nontrivial Galois automorphism of IK over Q, we get

(8)  D | γα^{y}(β^{λ} − α^{λ}) − (β^{λ} − 1).

Multiplying relations (6) and (8), we get

D^{2} | (δβ^{y}(α^{λ} − β^{λ}) − (α^{λ} − 1)) (γα^{y}(β^{λ} − α^{λ}) − (β^{λ} − 1)) ,

and the right hand side above is a nonzero integer. Hence,

D^{2} ≪ exp (y log |αβ|) + 2λ log |α|) ≤ exp ((log |αβ| + 2ε log |α|)z) .

Choosing ε < (log |α| − log |β|)/(2 log |α|), one checks easily that the last inequality above leads to the conclusion that D ≤ |α|^{κ_{0}z} for a certain κ_{0} ∈ (0, 1) (depending on ε) provided that z is sufficiently large. This completes the proof of Lemma 3. ⊓ ⊔

We mention that Bugeaud, Corvaja and Zannier (see [1]), showed by using the Subspace theorem that if a > b > 1 are multiplicatively independent integers, then for all ε > 0 there exists n_{ε} such that gcd(a^{n} − 1, b^{n} − 1) < exp(εn) if n > n_{ε}. Afterwards, this result was extended in various ways by various authors (see [5], [9], [14] and [20] for a sample of such extensions). The last lemma is a weak form of such a result, which is enough for our purpose, and admits an easier proof. Furthermore, we point out that a generalisation of these results to the number-field setting can be found in [5], which will also be used later.

4. Further Preliminaries and the case δβ^{z} = 1

In this section, we will prove some useful information on the solutions of our problem. Especially, we will handle the case when δβ^{z} = 1, which gives the exceptional solutions in the theorem.

4.1. Both z and y are large. Assume that 1 ≤ a < b < c and that ab + 1 = u_{x}, ac + 1 = u_{y} and bc + 1 = u_{z}. We may assume that there are infinitely many such triples, therefore that c → ∞. Since |α| > |β|, we have

|u_{n}| = |γ||α|^{n}|1 − dc^{−1}(β/α)^{n}|,

and (β/α)^{n} tends to zero as n → ∞. This shows that if n > n_{0} is sufficiently large, then |u_{n}| < |u_{m}| means n < m. Since

u_{z} = bc + 1 > max{u_{x}, u_{y}} = max{|u_{x}|, |u_{y}|},

we get that z > max{x, y}. Further, since c is arbitrarily large and u_{y} = ac + 1 > c, it follows that y is arbitrarily large. Since u_{y} = ac+1 > ab+1 = u_{x}, it follows that if c is sufficiently large, then y > x. Thus, we may assume that x < y < z. Clearly, z tends to infinity. We shall assume that z > z_{0}, where z_{0} is a sufficiently large number, not necessarily the same at each occurrence. Note that

u_{z} = |γ||α|^{z}|1 − dc^{−1}(β/α)^{z}| = bc + 1 ∈ [c, c^{2}],

showing that

(9)  log c ≤ z log |α| + O(1) ≤ 2 log c.

Since

u_{y} = |γ||α^{y}||1 − dc^{−1}(β/α)^{y}| = ac + 1 > c,

we get that

(10)  log c ≤ y log |α| + O(1).

Estimates (9) and (10) show that z ≤ 2y + O(1).

4.2. The case when δβ^{z} = 1. Since z is large, the above relation implies β = ±1, therefore δ = ±1. Hence, α ∈ ZZ. Furthermore, since γ = u_{0} − δ = u_{0} ± 1, we get that γ ∈ ZZ. Moreover, δβ^{y} and δβ^{x} are both in {±1}. If δβ^{y} = −1, we then have

bc = γα^{z} and ac = γα^{y} − 2.

It is easy to see that for large z we have gcd(γα^{z}, γα^{y} − 2) = O(1). This shows that c = O(1), therefore that z = O(1). This leads to only finitely many solutions. Thus, if z is sufficiently large, then δβ^{y} = 1. If also δβ^{x} = 1, then

ab = γα^{x},  ac = γα^{y},  bc = γα^{z},

therefore (abc)^{2} = γ^{3}α^{x+y+z}, implying that either γ or γα is a perfect square, according to whether x + y + z is even or odd, respectively. Assume now that δβ^{x} = −1. Then

ab = γα^{x} − 2,  ac = γα^{y},  bc = γα^{z}.

Furthermore, since δβ^{y} = δβ^{z} = 1 but δβ^{x} = −1, it follows that β = −1, y and z have the same parity, and x has opposite parity. Since abc^{2} = γ^{2}α^{y+z} and y and z have the same parity, it follows that ab is a perfect square. Assume now that x ≥ 2. Then

(11)  ab + 2 = γα^{x}.

But since a and b divide γα^{y} and γα^{z}, respectively, it follows that all primes dividing ab divide γα. The last relation above (11) shows now that the only prime factor of ab is 2. Hence, ab is a power of 2 and since it is a square, it is ≥ 4. Thus, 2∥ab + 2 (i.e. 2|ab + 2, but 4 does not), therefore 2∥γα^{x}, and since x ≥ 2, we get that 2∥γ and α is odd. Now the relations ac = γα^{y} and bc = γα^{z} together with the fact that ab is a power of 2, show that a ∈ {1, 2} and b ∈ {1, 2}, therefore ab ∈ {1, 2, 4}. This is impossible since 1 ≤ a < b and ab must be a perfect square. Thus, if δβ^{x} = −1, then x ∈ {0, 1}. This takes care of the exceptions (i) and (ii) appearing in the text of Theorem 1.

4.3. All three x, y and z are large. From now on, we assume that δβ^{z} ≠ 1. Note that u_{y} = ac + 1 > 1. Lemma 3 shows that there exists a positive constant κ_{0} < 1 such that the inequality

gcd(u_{z} − 1, u_{y} − 1) < |α|^{κ_{0}z}

holds provided that z is sufficiently large. Thus, the fact that c divides gcd(ac, bc) = gcd(u_{z} − 1, u_{y} − 1) shows that c < |α|^{κ_{0}z}, leading to

b = \frac{u_{z} − 1}{c} ≫ |α|^{(1−κ_{0})z}.

Since |α|^{x} ≫ u_{x} = ab + 1 > b ≫ |α|^{(1−κ_{0})z}, it follows that x ≥ (1 − κ_{0})z + O(1). Thus, x tends to infinity with c also and, in fact,

(12)  x ≍ y ≍ z.

This will be essential when applying the Subspace theorem.

4.4. Signs of γ and α. Here, we comment on the signs of α and γ. Assume that α > 0. Then the sign of u_{n} is the same as the sign of γ once n > n_{0} is sufficiently large. Thus, if γ < 0, then there are only finitely many n such that u_{n} is positive, and we obtain a contradiction. Hence, γ > 0 when α > 0.

Assume now that α < 0. Then for large n, the sign of u_{n} alternates; namely, the sign of u_{n} is the sign of γ(−1)^{n}. Thus, if γ > 0, then for large c the three numbers x, y, z are even, while if γ < 0, then for large c the three numbers x, y, z are odd. Thus, we may replace the pair of roots (α, β) by the pair (α^{2}, β^{2}), and keep the pair of coefficients (γ, δ) (if γ > 0), or replace it by (γα, δβ) (if γ < 0), and consequently suppose again that both α and γ are positive. From now on, we work under this assumption, namely that α and γ are positive.

4.5. a is large. Here, we shall prove a fact that will turn out to be useful later.

Lemma 4. We have a → ∞ as z → ∞ through integer values such that δβ^{z} ≠ 1. Furthermore, in case α and β are multiplicatively independent, there exists a positive constant κ_{1} such that a > |α|^{κ_{1}z} when z > z_{0}.

Proof. We start by assuming that for each ε > 0 there are infinitely many solutions with a < |α|^{εz}. We will see that this condition with a sufficiently small ε > 0 and a sufficiently large z entails that a = O(1) when α and β are multiplicatively independent. Then we shall show that this last condition leads to a contradiction without any assumption on α and β with regard to their multiplicative independence.

The equation

(13)  a^{2} = \frac{(u_{x} − 1)(u_{y} − 1)}{(u_{z} − 1)}

implies

(14)  |a^{2}α^{z} − γα^{x+y}| ≪ a^{2} max{|α|^{y}|β|^{x}, |α|^{y}, |β|^{z}}.

By estimate (12), it follows easily that there exists a constant κ_{2} ∈ (0, 1) such that if ε > 0 is sufficiently small, then

(15)  |a^{2}α^{z} − γα^{x+y}| < |α|^{κ_{2} max{x+y,z}}.

Indeed, putting κ_{3} for a positive constant such that min{x/z, x/(x + y)} > κ_{3}, a little calculation shows that the estimate (15) is implied by the estimate (14) for large z when

ε < 2^{−1}κ_{3} min{log |α|, log |α/β|}

with some constant κ_{2} (depending on ε) provided that z > z_{0} (here, z_{0} also depends on ε). Assume that x + y ≥ z since the other case can be dealt with similarly. Then

(16)  |a^{2}α^{z−x−y} − γ| < \frac{1}{|α|^{(1−κ_{2})(x+y)}} .

This shows that z − x − y = O(εz). Our next aim is to deduce for z > z_{0} that the left hand side of (16) has to be zero. Indeed, if IK = Q, and the left hand side is not zero, then its naïve height is exp(O(εz)). By the Liouville principle, if ε is sufficiently small and z is large, then inequality (16) cannot hold. If IK is quadratic, and the right hand side is not zero, then its conjugate is a^{2}β^{z−x−y} − δ. Thus, the height of this number is again exp(O(εz)). By the Liouville principle again, we arrive at a contradiction in inequality (16) for small ε > 0, assuming that its left hand side is nonzero.

Hence, for z > z_{0}, it follows that a = ±γ^{1/2}α^{(x+y−z)/2}. Now equation (13) is

a^{2}δβ^{z} − a^{2} = γδ(α^{x}β^{y} + α^{y}β^{x}) + δ^{2}β^{x+y} − γα^{x}
(17)  − γα^{y} − δβ^{x} − δβ^{y} + 1,

with a = ±γ^{1/2}α^{(x+y−z)/2}. This is a unit equation. Let E be some nondegenerate subequation containing the variable 1. Then any unit in E can take only finitely many values. If α and β are multiplicatively independent, it then follows that either E contains a^{2} = α^{x+y−z}, or one of the other units. In the first case, x+y−z = O(1), so a = O(1). In the second case, one checks using the fact that α and β are multiplicatively independent, that x = O(1); hence, only finitely many possibilities.

From now on, we assume that a is bounded for infinitely many solutions. Thus, infinitely many of these solutions will therefore have the same value for a. Now rewrite equation (13) (keeping in mind again that a^{2}γα^{z} = γ^{2}α^{x+y} as we did for (17)), as

a^{2} + 1 = a^{2}δβ^{z} + δβ^{x} + δβ^{y} − δ^{2}β^{x+y}
(18)  + γα^{x} + γα^{y} − γδα^{x}β^{y} − γδα^{y}β^{x}.

This is again a unit equation. In order to discuss its degeneracies, we distinguish several cases.

Assume first that α and β are multiplicatively independent. Then there must be a nondegenerate subequation containing the left side (a^{2} + 1 ≠ 0) and some member from the right hand side. There are only finitely many such subequations, and each one of them has only finitely many solutions. In each one of the cases, we get that x = O(1); hence, only finitely many possibilities.

Assume now that α and β are multiplicatively dependent. In this case, there exists ρ > 1 and coprime integers i > j such that α = ρ^{i} and β = ±ρ^{j}.

If j > 0, then again there must be some non-degenerate subequation of equation (18) containing the fixed nonzero number a^{2} + 1 from the left hand side and some variable from the right hand side. This leads to x = O(1); hence, only finitely many possibilities.

If j = 0, then β = ±1, α > 1 and γ, δ are all integers. We may also assume that the class of (x, y, z) in (ZZ/2ZZ)^{3} is fixed. Thus, the three numbers δβ^{x}, δβ^{y} and δβ^{z} are fixed in {±δ}. We rewrite equation (18) as

a^{2} + 1 − a^{2}δβ^{z} − δβ^{x} − δβ^{y} + δ^{2}β^{x+y}
= γ(1 − δβ^{y})α^{x} + γ(1 − δβ^{x})α^{y}.

The left hand side as well as the coefficients γ(1 − δβ^{y}) and γ(1 − δβ^{x}) from the right hand side of α^{x} and α^{y}, respectively, are fixed. Assume first that these coefficients are zero. Then δβ^{x} = δβ^{y} = 1 and the left hand side must also be zero. This leads to a^{2}(1 − δβ^{z}) = 0, therefore δβ^{z} = 1, which is not allowed. Thus, at least one of the two coefficients γ(1 − δβ^{y}) and γ(1 − δβ^{x}) from the right hand side is nonzero. Note that the left hand side is a fixed integer. Thus, if the left hand side is nonzero, then equation (18) is a unit equation with N = 1 or 2 according to whether one or none of the coefficients of α^{x} and α^{y} from the right hand side vanishes. This leads again to x = O(1); hence, only finitely many possibilities. Assume now that the right hand side is zero. Then

α^{y−x} = −\frac{1 − δβ^{y}}{1 − δβ^{x}} , a^{2} = −\frac{(1 − δβ^{x})(1 − δβ^{y})}{1 − δβ^{z}}.

Since α > 1, it follows from the first of the above two equations that the cases β = 1, or β = −1 and x ≡ y (mod 2) are impossible. Thus, up to replacing δ by −δ if needed, we may assume that

α^{y−x} = −\frac{(1 − δ)}{(1 + δ)}.

Since y > x and α is an integer, we get that 1 + δ | 1 − δ. Thus, 1 + δ | 2 leading to 1 + δ = −2, −1, 1, 2. The cases δ = 1 + δ = 1, 2 lead to δ = 0, which is not allowed, and α = 0, which is not allowed either. The cases 1 + δ = −2, −1 give α^{y−x} = 2, 3, respectively. Thus, α = 2, 3, respectively, and y = x + 1. Now

a^{2} = −\frac{(1 − δβ^{x})(1 − δβ^{y})}{(1 − δβ^{z})} = −\frac{1 − δ^{2}}{1 ± δ} ∈ \{−4, −3, 2, 1\},

so the only possibility is that a = 1. This happens if δ = −2 and a^{2} = −(1 + δ), therefore 1 − δβ^{z} = 1 − δ, so z is even. On the other hand, 1 = a = γ^{1/2}α^{(x+y−z)/2} and γ and α are positive integers, therefore γ = 1 and z = x + y = 2x + 1 is odd. This contradiction shows that it is not possible that the left hand side of equation (18) is zero and not both of the coefficients γ(1 − δβ^{y}) and γ(1 − δβ^{x}) of α^{y} and α^{x}, respectively, from its right hand side be zero. Hence, if j = 0, then there are only finitely many possibilities for x, y and z.

Finally, assume that j < 0. Then j = −1, i = 1, so β = ±α^{−1}. Rewrite equation (18) as

a^{2} + 1 − a^{2}δβ^{z} − δβ^{x} − δβ^{y} + δ^{2}β^{x+y} + γδ(α^{x}β^{y} + α^{y}β^{x})
= γ(α^{x} + α^{y}).

Its right hand side is ≫ α^{y}. Its left hand side is in absolute value ≪ α^{y−x}, since β = ±α^{−1}. Thus, α^{y−x} ≫ α^{y}, leading to α^{x} ≪ 1, therefore x = O(1); hence, finitely many possibilities.

Having analyzed all the possible scenarios and having arrived to only finitely many possibilities in each case, we conclude that a = O(1) leads to only finitely many possibilities. Thus, it must be the case that a → ∞ as z → ∞. Furthermore, in case α and β are multiplicatively independent, we have a > |α|^{κ_{1}z} when z > z_{0}, where κ_{1} > 0 is some constant. ⊓ ⊔

We saw that δβ^{z} ≠ 1. For future use, we also record that δβ^{y} ≠ 1 and δβ^{x} ≠ 1. Indeed, if say δβ^{x} = 1, then β = ±1 and a | gcd(γα^{z} + (δβ^{z} − 1), γα^{x}). Since δβ^{z} − 1 = O(1) is nonzero, it follows easily that a is bounded, which is a contradiction. The similar contradiction that b = O(1) is obtained if one assumes that δβ^{y} = 1.

5. The case α and β multiplicatively independent

In this section we will finish the proof of the theorem in the case when α and β are multiplicatively independent. This will be done by applying Theorem 1 of [11], which follows from the general result from [6] (see also [3], [4], [10], or [12]). We will indicate the proof to see that we get an additional piece of information which is not stated explicitly, although well-known, in [11, Theorem 1]. Then we show that the assumption of α and β being multiplicatively independent leads to a contradiction. As a first independent step we show that min{y − x, y − 2x, z − 2x} = O(1) in this case. Afterwards, the contradiction is derived.

5.1. An application of the Subspace theorem. The three relations (2) yield

(19)  (u_{x} − 1)(u_{y} − 1)(u_{z} − 1) = (abc)^{2}.

Note that

(u_{x} − 1)(u_{y} − 1)(u_{z} − 1) = γ^{3}α^{x+y+z}(1 + η),

where

η = ∏_{t∈\{x,y,z\}} (γ_{1} (\frac{β}{α})^{t} + δ_{1} (\frac{1}{α})^{t}) ,

with γ_{1} = δ/γ and δ_{1} = −1/γ. Thus,

abc = γ^{3/2}α^{(x+y+z)/2}(1 + η)^{1/2} = γ^{3/2}α^{(x+y+z)/2} ∑_{k≥0} \binom{1/2}{k}η^{k}.

Furthermore, using the binomial formulae, for each k we have

η^{k} = ∑_{(i,j)∈Γ_{k}} c_{(i,j)}α^{−i_{1}x−i_{2}y−i_{3}z}β^{j_{1}x+j_{2}y+j_{3}z},

where Γ_{k} is the set of all sextuples (i, j) with i = (i_{1}, i_{2}, i_{3}), j = (j_{1}, j_{2}, j_{3}) fulfilling i_{1} + i_{2} + i_{3} = k, and 0 ≤ j_{ℓ} ≤ i_{ℓ} for all ℓ = 1, 2, 3, while c_{(i,j)} are certain coefficients in IK indexed over the members of Γ_{k}.

Since x, y and z have the same order of magnitude, the arguments from [11] show that there exists a finite set Λ of sextuples (i, j) (note that if (i, j) is given, then k is the sum of the entries in i), and nonzero coefficients d_{(i,j)} ∈ \overline{Q} for (i, j) ∈ Λ, such that infinitely many of the solutions (a, b, c; x, y, z) have the property that

(20)  abc = α^{(x+y+z)/2} ∑_{(i,j)∈Λ} d_{(i,j)}α^{−i_{1}x−i_{2}y−i_{3}z}β^{j_{1}x+j_{2}y+j_{3}z}.

From now on, we work only with such solutions. We insert abc given by formula (20) into formula (19) and we end up with (21)

(u_{x}−1)(u_{y}−1)(u_{z}−1) = α^{x+y+z} ( ∑_{(i,j)∈Λ} d_{(i,j)}α^{−i_{1}x−i_{2}y−i_{3}z}β^{j_{1}x+j_{2}y+j_{3}z})^{2}

which upon expansion of both sides above leads to an S-unit equation with infinitely many solutions. We now study this equation.

5.2. min{y − x, y − 2x, z − 2x} = O(1) when α and β are multiplicatively independent. We order the units appearing on the left had side of the unit equation (21) according to their sizes of their absolute values.

5.2.1. The case |β| > 1. It is then easy to see that

(u_{x} − 1)(u_{y} − 1)(u_{z} − 1) = γ^{3}α^{x+y+z} + γ^{2}δα^{z+y}β^{x} + γ^{2}δα^{z+x}β^{y}
(22)  + γ^{2}δα^{x+y}β^{z} + γδ^{2}α^{z}β^{x+y} + smaller units.

We claim that for large z, we have

α^{z+y}|β|^{x} > α^{z+x}|β|^{y} > α^{x+y}|β|^{z} > α^{z}|β|^{x+y}.

Indeed, the ratios of any two consecutive expressions above are

(\frac{α}{|β|})^{y−x} , (\frac{α}{|β|})^{z−y} , (\frac{α}{|β|})^{x+y−z} .

The first two expressions are certainly > 1 and they remain bounded only when y − x = O(1) and z − y = O(1), and the fact that the third one tends to infinity as z → ∞ is a consequence of Lemma 4 and of the fact that α^{x+y−z} ≫ a^{2} ≥ α^{κ_{1}z}.

We now insert the right hand side of (22) in (21) and use Lemma 2 (see also the remarks made below Lemma 2). We may assume that α^{x+y+z} cancels from both sides of equation (21). Indeed, if not, then (0, 0) ∉ Λ, and the largest unit present in the right hand side is ≤ α^{y+z−x}|β|^{2x}. Let E be some nondegenerate subequation containing α^{x+y+z}. If E contains some unit from the right hand side of (21), we deduce that the ratio of α^{x+y+z} to α^{y+z−x}|β|^{2x} is bounded; hence, (α/|β|)^{2x} = O(1), leading to x = O(1); thus, only finitely many possibilities. If on the other hand E contains some other unit from the left hand side of equation (21), then the ratio of α^{x+y+z} to α^{y+z}|β|^{x} is bounded. Thus, again (α/|β|)^{x} = O(1), which leads to only finitely many possibilities. From now on, we assume that α^{x+y+z} cancels from both sides of equation (21), so in particular that (0, 0) ∈ Λ.

Let E be some nondegenerate subequation containing α^{z+y}β^{x}.

If E contains either α^{z}β^{x+y} or one of the smaller units, then the ratio of α^{z+y}β^{x} to α^{z}β^{z+y} stays bounded. This gives (α/|β|)^{y} = O(1), therefore y = O(1); thus, only finitely many possibilities.

If E contains either α^{z+x}β^{y}, or α^{x+y}β^{z}, we then get that (α/|β|)^{y−x} = O(1), which is what we are after.

If E does not contain any unit from the left hand side of (21), then it must contain one from the right hand side. Hence, the ratio of

α^{y+z}β^{x} to α^{x+y+z} \frac{β^{j_{1}x+j_{2}y+j_{3}z}}{α^{i_{1}x+i_{2}y+i_{3}z}}

is bounded for some (i, j) ∈ Λ with i_{1} + i_{1} + i_{3} = k ≠ 0. Thus,

(23)  α^{(i_{1}−1)x+i_{2}y+i_{3}z} ≪ |β|^{(j_{1}−1)x+j_{2}y+j_{3}z}.

Since j_{ℓ} ≤ i_{ℓ} for ℓ = 1, 2, 3, it follows that (α/|β|)^{(i_{1}−1)x+i_{2}y+i_{3}z} ≪ 1. If i_{2} + i_{3} > 0, we then get y − x ≪ 1, which is what we want. Thus, i_{2} = i_{3} = 0, and since k > 0, we get that i_{1} ≥ 1. If i_{1} ≥ 2, we then get x = O(1), so we get only finitely many possibilities. Thus, infinitely many of the solutions will have i_{0} = (1, 0, 0). If j_{1} = 0, then estimate (23) shows that |β|^{x} ≍ 1, therefore again x = O(1). Hence, j_{1} = 1 for infinitely many solutions. This shows that for i_{0} = (1, 0, 0) and j_{0} = (1, 0, 0) we have that (i_{0}, j_{0}) ∈ Λ. In particular, α^{x+y+z}(β/α)^{2x} appears in the formula for (abc)^{2}. Let F be some nondegenerate equation that contains this variable.

If F contains a unit from the left hand side equal to α^{z}β^{x+y} or smaller, we then get that the ratio of

α^{x+y+z} (\frac{β}{α})^{2x} to α^{z}β^{x+y}

is O(1). This implies that (α/|β|)^{y−x} ≪ 1, or y − x = O(1), which is what we want.

If F contains a unit from the left hand side which is in

{α^{y+z}β^{x}, α^{z+x}β^{y}, α^{x+y}β^{z}},

we then get that the ratio of α^{y+z−x}β^{2x} to one of these three units belongs to a fixed finite set of numbers. Thus, one of

(\frac{α}{β})^{x} , (\frac{α}{β})^{y−2x} , (\frac{α}{β})^{z−2x}

belongs to a fixed finite set of numbers. The first possibility gives x = O(1), so only finitely many possibilities. The second and third show that y − 2x = O(1), or z − 2x = O(1), which is what we wanted.

Assume now that F does not contain any unit from the left hand side of equation (21). Then it must contain some unit from the right hand side. Thus, there must exist (i_{1}, j_{1}) ≠ (2i_{0}, 2j_{0}) such that the ratio of (β/α)^{2x} to β^{j′_{1}x+j′_{2}y+j′_{3}z}/α^{i′_{1}x+i′_{2}y+i′_{3}z} belongs to a finite set of numbers. Here, i_{1} = (i′_{1}, i′_{2}, i′_{3}) and j_{1} = (j′_{1}, j′_{2}, j′_{3}). Put k = i′_{1} + i′_{2} + i′_{3}. If k ≥ 3, then

\frac{|β|^{j′_{1}x+j′_{2}y+j′_{3}z}}{α^{i′_{1}x+i′_{2}y+i′_{3}z}} ≪ (\frac{|β|}{α})^{3x} ,

and so we get that (α/|β|)^{x} ≪ 1, showing that x = O(1); hence, again only finitely many possibilities. If k = 2, then it is easy to see that units of this shape of maximal absolute value not equal to (β/α)^{2x} have maximal value at most (|β|/α)^{x+y}. So, the ratio of (β/α)^{2x} to such a unit is ≫ (α/|β|)^{y−x}. Hence, (α/|β|)^{y−x} ≪ 1, showing that y − x = O(1), which is what we want.

The only elements in F with k = 1 are

\frac{1}{α^{x}} , \frac{1}{α^{y}} , \frac{1}{α^{z}} , (\frac{β}{α})^{x} , (\frac{β}{α})^{y} , (\frac{β}{α})^{z} .

Thus, the ratio of (β/α)^{2x} to one of the above six units belongs to some finite set of numbers. If one of these six units is one of the first four, then we get that one of β^{2x}α^{−x}, β^{2x}α^{y−x}, β^{2x}α^{z−x}, or (β/α)^{x} belongs to a finite list of numbers. Since α and β are multiplicatively independent, we get that x = O(1); hence, there are only finitely many possibilities. Finally, if one of these six units is one of the last two, we then get that one of (β/α)^{2x−y} or (β/α)^{2x−z} belongs to a fixed finite set of numbers. Thus, y − 2x = O(1) or z − 2x = O(1), as we wanted.

This finishes the case when |β| > 1.

5.2.2. The case |β| < 1. Here, we just sketch the main steps since the argument is very similar to the previous one. Instead of (22), we have

(u_{x} − 1)(u_{y} − 1)(u_{z} − 1) = γ^{3}α^{x+y+z} − γ^{2}α^{z+y} − γ^{2}α^{z+x}
(24)  − γ^{2}α^{x+y} + γα^{z} + smaller units.

The main roots are, in decreasing order of their absolute values,

α^{x+y+z}, α^{y+z}, α^{z+x}, α^{x+y}, α^{z},

and the ratios between any two consecutive ones is

α^{x}, α^{y−x}, α^{z−y}, α^{x+y−z},

respectively. The last one tends to infinity with z by Lemma 4. The same argument as the one used at the case |β| > 1 shows that one may assume that the unit α^{x+y+z} cancels from both sides of the unit equation (21), for otherwise we get x = O(1); hence, only finitely many possibilities. Thus, (0, 0) ∈ Λ.

Let E be again some nondegenerate subequation of (21) containing α^{y+z} in the left hand side. If it contains some other unit from the left hand side which is α^{z} or smaller in absolute value, we get that α^{y} = (α^{y+z})/α^{z} = O(1). Thus, we have only finitely many possibilities. If E contains one of the units α^{z+x} or α^{x+y} from the left hand side, we then get α^{y−x} = O(1), which is what we want. Suppose now E contains some unit from the left hand side, say of the form

α^{x+y+z} \frac{β^{j_{1}x+j_{2}y+j_{3}z}}{α^{i_{1}x+i_{2}y+i_{3}z}} ,

where k = i_{1} + i_{2} + i_{3} > 0. Then

α^{(i_{1}−1)x+i_{2}y+i_{3}z} ≪ β^{j_{1}x+j_{2}y+j_{3}z}.

Since |β| < 1, the above inequality leads easily to the conclusion that x = O(1), unless i_{0} = (i_{1}, i_{2}, i_{3}) = (1, 0, 0) and j_{0} = (j_{1}, j_{2}, j_{3}) = (0, 0, 0). Thus, (i_{0}, j_{0}) ∈ Λ, which shows that its square appears in the right hand side of equation (21). Let F be some subequation containing α^{y+z−x} appearing on the right hand side of (21). Assume that F contains some unit from the left hand side of (21). If this is α^{z} or some unit of a smaller absolute value, we get that α^{y−x} ≪ O(1). Thus, y − x = O(1), which is what we want. If it contains one of α^{y+z}, α^{x+z}, or α^{x+y}, then one of the numbers α^{x}, α^{y−2x} or α^{z−2x} belongs to a finite list. Thus, either x = O(1), which happens for only finitely many possibilities, or min{y − 2x, z − 2x} = O(1), which is what we want.

Finally, assume that F contains some other unit from the right hand side of equation (21) of the form α^{x+y+z}β^{j′_{1}x+j′_{2}y+j′_{3}z}/α^{i′_{1}x+i′_{2}y+i′_{3}z}. We scale everything by α^{x+y+z}. If k ≥ 3, then the largest such unit in absolute value is 1/α^{3x}. The ratio of 1/α^{2x} to this unit is ≫ α^{x}, so if this ratio is in a finite set of numbers, we then get x = O(1); hence, only finitely many possibilities. If k = 2, then the largest such unit in absolute value which is not 1/α^{2x} is ≤ 1/α^{x+y}. The ratio of 1/α^{2x} to such a unit is ≫ α^{y−x}. So, if this ratio is in a finite set, we get y − x = O(1), as desired. Finally, the only possibilities when k = 1 are

\frac{1}{α^{x}} , \frac{1}{α^{y}} , \frac{1}{α^{z}} , (\frac{β}{α})^{x} , (\frac{β}{α})^{y} , (\frac{β}{α})^{z} .

If F contains one of these units, we then get that one of

α^{x}, α^{y−x}, α^{z−x}, (αβ)^{x}, α^{y−2x}β^{−y}, α^{z−2x}β^{−z}

belongs to a finite list. In the first case, we get x = O(1). In the next two, we get y − x = O(1), as desired. Finally, since α and β are multiplicatively independent, in the last three cases we get x = O(1); hence, finitely many possibilities also.

In conclusion, we proved that both when |β| > 1 and |β| < 1, assuming that α and β are multiplicatively independent, infinitely many of the solutions will have one of y − x, y − 2x, or z − 2x bounded.

5.3. Proof of the theorem for α and β multiplicatively independent. Suppose first that y − x = λ is a fixed number for infinitely many of our solutions. Then

a | γα^{x} + δβ^{x} − 1 and a | γα^{x+λ} + δβ^{x+λ} − 1.

Multiplying the first equation relation above by α^{λ} and subtracting them, we get that

(25)  a | δβ^{x}(α^{λ} − β^{λ}) − (α^{λ} − 1),

and, as in the proof of Lemma 3, the right hand side above is nonzero for z > z_{0}. Note further that α^{λ} − β^{λ} ≠ 0 because λ ≠ 0 and α/β is not a root of 1. Put ζ = δ^{−1}(α^{λ} − 1)/(α^{λ} − β^{λ}). Note that ζ ≠ 0. Relation (25) shows that

a | κ_{4}(β^{x} − ζ),

where we can take κ_{4} to be some fixed positive integer which is divisible by the norm of |α^{λ} − β^{λ}| with respect to IK. The same argument (interchanging α with β) shows that

a | κ_{4}(α^{x} − η),

where η = γ^{−1}(β^{λ} − 1)/(β^{λ} − α^{λ}). The fact that η ≠ 0 follows because β ≠ ±1 and λ ≠ 0. Furthermore, both α^{x} − η and β^{x} − ζ are nonzero. Hence,

a ≪ N_{IK} (gcd(α^{x} − η, β^{x} − ζ)) ,

where the last expression is to be interpreted as the norm of the ideal greatest common divisor of the two algebraic numbers in IK (see also [20]). Since α and β are multiplicatively independent, the Main Theorem from [5, p. 205] shows that a = exp(o(x)) as x → ∞. This contradicts Lemma 4 for large values of x.

Suppose now that y − 2x = λ for some fixed value of λ. We will get the contradiction by a similar argument as in the first case. It follows

a | γα^{x} + (δβ^{x} − 1) | (γα^{x})^{2} − (δβ^{x} − 1)^{2}.

Thus,

a | γ^{2}α^{2x} − δ^{2}β^{2x} + 2δβ^{x} − 1 and a | γα^{2x+λ} + δβ^{2x+λ} − 1.

Multiplying the first relation above by α^{λ}, the second by γ, and subtracting them, we get

a | β^{2x}δ(γβ^{λ} + δα^{λ}) − 2δα^{λ}β^{x} + α^{λ} − γ.

The last expression above is nonzero for large x. Indeed, this expression is a polynomial of degree at most 2 in β^{x}. If it were zero, then it must happen that all three coefficients δ(γβ^{λ} + δα^{λ}), −2δα^{λ} and α^{λ} − γ are zero, which is not the case since δα ≠ 0. Thus,

a | κ_{4}P (β^{x}),

where P (β^{x}) is a nonzero monic polynomial of degree at most 2. Interchanging β to α in the previous argument, we get that

a | κ_{4}Q(α^{x}),

where Q(X) ∈ IK[X] is some nonzero polynomial of degree at most 2. Hence, at the level of ideals,

a | κ_{4} ∏_{\begin{matrix}ζ,η \\ P (ζ)=0, Q(η)=0 \end{matrix}} N_{IL} (gcd(β^{x} − ζ, α^{x} − η)) ,

where IL is the splitting field over IK of P (X)Q(X) and where the roots ζ and η of P (X) and Q(X) in IL, respectively, are counted with their multiplicities. If ζη ≠ 0, then N_{IK}(gcd(β^{x} − ζ, α^{x} − η)) = |α|^{o(x)} as x → ∞ by [6, Main Theorem, p. 205]. It remains to deal with the case when one of ζ or η is zero. Assume say that ζ = 0. Let π be any prime ideal dividing β in IK. All we need to understand is an upper bound for μ_{π}(a), where for a number ω ∈ IK we use μ_{π}(ω) for the exponent of π in the factorization of ω in prime ideals inside IK. If π divides also α, then π does not divide u_{x} − 1 for large x. Thus, μ_{π}(a) = 0 in this case. If π does not divide α, then

μ_{π}(u_{x} − 1) = μ_{π}(γα^{x} + δβ^{x} − 1) ≤ min{x, μ_{π}(γα^{x} − 1)}.

By linear forms in π-adic logarithms (see, for example, [21]),

μ_{π}(γα^{x} − 1) ≪ log x.

Thus, for large x, μ_{π}(a) ≤ μ_{π}(u_{x} − 1) ≪ log x. A similar argument applies to the ideals dividing α. This argument shows that the roots ζη = 0 contribute a factor of size |α|^{O(log x)} = |α|^{o(x)} as x → ∞ in a. Consequently,

a ≤ |α|^{o(x)}

holds as x → ∞, contradicting again Lemma 4.

The same argument works also in the case z − 2x = O(1), the role of a being played by b. We give no further details.

6. The case α and β multiplicatively dependent

We begin with some remarks about the case when α and β are multiplicatively dependent. Since they are also either rational or quadratic integers, there exist ρ > 1, coprime integers i > 0 and j, and η ∈ {±1}, such that α = ρ^{i} and β = ηρ^{j}. If j ≥ 0, then ρ is a rational integer. Otherwise, i = 1, j = −1, and ρ is a quadratic unit.

Observe now that if j ≥ 0, then

u_{n} − 1 = γ(ρ^{n})^{i} + η^{n}δ(ρ^{n})^{j} − 1

is a polynomial in ρ^{n} when η = 1, and one of two polynomials when η = −1 according to whether n is even or odd. When j = −1, then

u_{n} = ρ^{−n}(γ(ρ^{n})^{2} − ρ^{n} + η^{n}δ)

is associated (because ρ^{−n} is a unit) to one (if η = 1), or one of the two (if η = −1) polynomials of degree 2 in ρ^{n} with coefficients in IK. The following result is very important in what follows.

Lemma 5. All solutions (x, y, z) of equation (2) are contained in the union of finitely many lines in ZZ^{3}.

Proof. We let b_{1} and c_{1} be the largest divisors of b and c, respectively, which are free of primes dividing ρ. Note that both b/b_{1} and c/c_{1} are O(1). Indeed, if j > 0, then ρ > 1 ∈ ZZ and u_{n} − 1 is coprime to ρ for all n sufficiently large. If j < 0, then ρ is a unit, so b_{1} = b and c_{1} = c. Finally, if j = 0, then, since δβ^{z} ≠ 1 and δβ^{y} ≠ 1, we get that δβ^{z} − 1 = O(1) and δβ^{y} − 1 = O(1) are both nonzero.

This justifies that b/b_{1} = O(1) and c/c_{1} = O(1).

We now fix the class of (x, y, z) modulo (ZZ/2ZZ)^{3}. For j ≥ 0, we may write

bc = u_{z} − 1 = γP (ρ^{z}) = γ ∏_{i=1}^{ℓ}(ρ^{z} − μ_{i})^{σ_{i}},

ac = u_{y} − 1 = γQ(ρ^{y}) = γ ∏_{j=1}^{ℓ′}(ρ^{y} − μ′_{j})^{σ′_{ℓ}}.

In the above formulae, μ_{1}, …, μ_{ℓ} are all the distinct roots of P (X) having multiplicities σ_{1}, …, σ_{ℓ}, respectively. Similarly, μ_{1}, …, μ_{ℓ′} are the distinct roots of Q(X) of multiplicities σ′_{1}, …, σ′_{ℓ′}, respectively. Note that μ_{1}, …, μ_{ℓ}, μ′_{1}, …, μ′_{ℓ′} are all nonzero. Note also that P (X) and Q(X) have degrees i. When j < 0, then we write

bc = u_{z} − 1 = γρ^{−z}P (ρ^{z}), and ac = u_{y} − 1 = γρ^{−y}Q(ρ^{y}),

where now P (X) and Q(X) are quadratic polynomials. We keep the notations μ_{i}, σ_{i} and μ′_{j}, σ′_{j} with 1 ≤ i ≤ ℓ, 1 ≤ j ≤ ℓ′ for the distinct roots with their corresponding multiplicities of P (X) and Q(X), respectively.

In all cases, we put d for the common degree of P (X) and Q(X). We now write σ = max{σ_{i}, σ′_{j} : 1 ≤ i ≤ ℓ, 1 ≤ j ≤ ℓ′}, IL for

the splitting field of P (X)Q(X) over IK, and κ_{5} for a positive integer divisible by the denominators of γ, μ_{i} and μ′_{j} for all 1 ≤ i ≤ ℓ and 1 ≤ j ≤ ℓ′. We then get that

c_{1} | gcd(u_{z} − 1, u_{y} − 1) | gcd(γP (ρ^{z}), γQ(ρ^{y}))
(26)  | κ_{5}^{d^{3}+1}γ ∏_{\begin{matrix}1≤i≤s \\ 1≤j≤t \end{matrix}} gcd (ρ^{z} − μ_{i}, ρ^{y} − μ′_{j})^{σ} .

The last product above is to be interpreted as a product of ideals in IL.

Now let T > 2 be a large positive integer. Consider the set of numbers T = {pz + qy : 1 ≤ p ≤ T, 1 ≤ q ≤ T }. Clearly, all numbers in T are ≤ 2zT for large z. Since there are T^{2} pairs of positive integers (p, q) ∈ [1, T]^{2}, it follows, by the pigeon hole principle, that there there exist (p, q) ≠ (p′, q′) such that |pz + qy − (p′z + q′y)| ≤ 2T z/(T^{2} − 1) < 3z/T. Write u = p − p′ and v = q − q′ and assume that uz + vy ≥ 0 (otherwise, we replace the pair (u, v) by the pair (−u, −v)). For 1 ≤ i ≤ ℓ and 1 ≤ j ≤ ℓ′, put c_{1,i,j} for the ideal gcd(c_{1}, ρ^{z} − μ_{i}, ρ^{y} − μ′_{j}) in IL. Since

ρ^{z} ≡ μ_{i} (mod c_{1,i,j}) and ρ^{y} ≡ μ′_{j} (mod c_{1,i,j}),

and ρ is invertible modulo c_{1}, we get that ρ^{uz+vy} ≡ μ_{i}^{u}μ_{j}^{′v} (mod c_{1,i,j}). We thus get, using relation (26), that

(27)  c_{1} | κ_{5}^{T (d^{3}+1)}γ ∏_{\begin{matrix}1≤i≤ℓ \\ 1≤j≤ℓ′ \end{matrix}} (ρ^{uz+vy} − μ_{i}^{u}μ_{j}^{′v}) .

Assume that the right hand side above is nonzero. Then, taking norms in IL and using the fact that 0 ≤ uz + vy ≪ z/T, we get that

c_{1} ≤ exp(O(z/T + T)).

The constant implied by the above O depends on the sequence (u_{n})_{n≥0}. Since c_{1} ≫ c ≫ α^{z/2}, we get that

α^{z/2} ≤ exp(O(z/T + T)),

therefore z ≪ z/T + T. This inequality is false if we first choose T > 2κ_{6}^{−1}, where κ_{6} is the constant implied by the above O, and then make z large. The contradiction comes from the fact that we have assumed that the right hand side of (27) is nonzero for T = ⌊κ_{6}^{−1}⌋ + 1 once z is large. If the right hand side of (27) is zero with this value for T, then ρ^{uz+vy} = μ_{i}^{u}μ_{j}^{′v} for some i, j, u, v, and since ρ is not a root of 1, we get that uz + vy is uniquely determined once i, j, u, v have been fixed.

We now repeat the argument but with x instead of y and with b instead of c. The similar argument leads to the conclusion that unless some equality of the form ρ^{u′z+v′y} = μ_{i}^{u′}μ_{j}^{′′v′} holds with some integers u′, v′ of absolute values at most T′ and not both zero, then b ≤ exp(O(z/T′ + T′)). Here, μ′′_{1}, …, μ′′_{ℓ′′} are the roots of the polynomial R(X) such that u_{x} − 1 is associated to γR(ρ^{x}) in the same way as u_{z} − 1 and u_{y} − 1 were associated to γP (ρ^{z}) and γQ(ρ^{y}), respectively. Since b ≫ α^{(1−κ_{0})z} for some constant κ_{0} ∈ (0, 1), we get again that z ≪ z/T′ + T′, which is a contradiction if T′ is first chosen to be sufficiently large, and then z is allowed to be large. In conclusion, there must exist a relation of the form ρ^{u′z+v′x} = μ_{i}^{u′}μ_{j}^{′′v′}, with exponents u′, v′ of sizes O(1), which are not both zero, leading again to the fact that u′z + v′x = O(1). Since we also have uz + vy = O(1), we get that (x, y, z) belongs to one of finitely many effectively computable lines in ZZ^{3}. ⊓ ⊔

Since we have infinitely many solutions (x, y, z) and only finitely many possibilities for the lines in ZZ^{3} on which they might lie, it follows that infinitely many of the x, y and z are of the form

x = d_{1}t + e_{1},  y = d_{2}t + e_{2},  z = d_{3}t + e_{3},

where d_{1}, d_{2}, d_{3}, e_{1}, e_{2}, e_{3} are fixed integers with the first three positive and t is a positive integer which may be arbitrarily large. Note that d_{3} ≥ d_{2} ≥ d_{1} > 0. We may also fix the parity of t, therefore the signs of β^{x}, β^{y}, β^{z} are all determined by η and the parities of e_{1}, e_{2} and e_{3}. We now distinguish the following cases.

6.1. The case j > 0. This is the easiest case. We have

ab = u_{x} − 1 = (γα^{ie_{1}})(ρ^{t})^{id_{1}} + ζ_{1}(δρ^{je_{1}})(ρ^{t})^{jd_{1}} − 1,
ac = u_{y} − 1 = (γα^{ie_{2}})(ρ^{t})^{id_{2}} + ζ_{2}(δρ^{je_{2}})(ρ^{t})^{jd_{2}} − 1,
bc = u_{z} − 1 = (γα^{ie_{3}})(ρ^{t})^{id_{3}} + ζ_{3}(δρ^{je_{3}})(ρ^{t})^{jd_{3}} − 1,

where ζ_{i} = η^{e_{i}} ∈ {±1} for i = 1, 2, 3. Multiplying the three relations above we get a polynomial with rational coefficients in ρ^{t} which is a perfect square for infinitely many values of t. Since 0 is not a root of this polynomial (in fact, its constant term is −1), it follows easily that this polynomial must be the perfect square of a polynomial with rational coefficients (see, for example, [15, Criterion 1]). However, this is impossible because its constant term is −1, which is not a perfect square.

6.2. The case j = 0. In this case, i = 1 and we have

ab = u_{x} − 1 = γ_{1}(ρ^{t})^{d_{1}} + δ_{1},
ac = u_{y} − 1 = γ_{2}(ρ^{t})^{d_{2}} + δ_{2},
bc = u_{z} − 1 = γ_{3}(ρ^{t})^{d_{3}} + δ_{3},

where δ_{1}, δ_{2}, δ_{3} ∈ {−δ−1, δ−1} are nonzero and γ_{i} = γρ^{e_{i}} for i = 1, 2, 3. Let us put P_{i}(X) = γ_{i}X^{d_{i}} + δ_{i}. Then

a | gcd(P_{1}(ρ^{t}), P_{2}(ρ^{t})), b | gcd(P_{1}(ρ^{t}), P_{3}(ρ^{t})), c | gcd(P_{2}(ρ^{t}), P_{3}(ρ^{t})).

We now look at gcd(P_{i}(X), P_{j}(X)) for i ≠ j. The roots of P_{i}(X) in C are e^{2πiμ/d_{i}}η_{i}, for μ = 0, 1, …, d_{i}−1, where η_{i} is any fixed determination of (−δ_{i}/γ_{i})^{1/d_{i}}. It now follows easily that gcd(P_{i}(X), P_{j}(X)) is a polynomial of degree at most gcd(d_{i}, d_{j}). In particular, gcd(P_{3}(X), P_{1}(X))· gcd(P_{3}(X), P_{2}(X)) is a polynomial of degree at most gcd(d_{3}, d_{3}) + gcd(d_{3}, d_{2}). Since

P_{3}(ρ^{t}) = bc | gcd(P_{1}(ρ^{t}), P_{3}(ρ^{t})) gcd(P_{2}(ρ^{t}), P_{3}(ρ^{t}))

holds for infinitely many positive integers t, we get that d_{3} ≤ gcd(d_{3}, d_{1}) + gcd(d_{3}, d_{2}). Since d_{1} ≤ d_{2} ≤ d_{3}, the above inequality shows that either d_{3} = d_{2}, or d_{1} = d_{2} = d_{3}/2. We treat only the case d_{1} = d_{2}, since the case when d_{2} = d_{3} is similar. Since d_{1} = d_{2} and y > x, we get that e_{2} > e_{1}. Putting d = d_{1}, we get that P_{1}(X) is associated to X^{d} + δ_{1}/γ_{1} and P_{2}(X) is associated to X^{d} + δ_{2}/γ_{2}. They have a common root if and only if δ_{1}/γ_{1} = δ_{2}/γ_{2}. This leads to ρ^{e_{2}−e_{1}} = δ_{2}/δ_{1}. If δ_{2} = δ_{1}, then e_{2} = e_{1}, therefore x = y, which is a contradiction. This shows that δ_{2} ≠ δ_{1}, therefore δ_{2}/δ_{1} equals either (δ − 1)/(−δ − 1), or (−δ − 1)/(δ − 1). Changing δ to −δ, if necessary, we may assume that

ρ^{e_{2}−e_{1}} = −\frac{δ − 1}{δ + 1}.

Since ρ is an integer, we get that 1 + δ | δ − 1, therefore 1 + δ | 2. Thus, 1 + δ = −2, −1, 1, 2. The cases 1 + δ = −2, −1, 2 give ρ^{e_{2}−e_{1}} = −2, −3, 0, respectively, which are impossible because ρ is positive, while the case 1 + δ = 1 gives δ = 0, which is not allowed. This completes the analysis of the case when j = 0.

6.3. The case j = −1. This is by far the most technical one. In this case, we have that

u_{x} − 1 = γρ^{x+e_{1}}((ρ^{t})^{2d_{1}} − γ_{1}(ρ^{t})^{d_{1}} + δ_{1}),
u_{y} − 1 = γρ^{y+e_{2}}((ρ^{t})^{2d_{2}} − γ_{2}(ρ^{t})^{d_{2}} + δ_{2}),
u_{z} − 1 = γρ^{z+e_{3}}((ρ^{t})^{2d_{3}} − γ_{3}(ρ^{t})^{d_{3}} + δ_{3}),

where γ_{i} = γ^{−1}ρ^{−e_{i}}, δ_{i} = η_{i}δγ^{−1}ρ^{−2e_{i}} and η_{i} = η^{e_{i}} ∈ {±1} for i = 1, 2, 3. We put

P_{i}(X) = X^{2d_{i}} − γ_{i}X^{d_{i}} + δ_{i} = Q_{i}(X^{d_{i}}) for all i = 1, 2, 3,

where Q_{i}(X) = X^{2} − γ_{i}X + δ_{i} for i = 1, 2, 3. Note that P (ρ^{t}) = ∏_{i=1}^{3} P_{i}(ρ^{t}) is associated to a perfect square in IK for infinitely many t. Since P (X) = ∏_{i=1}^{t} P_{i}(X) does not have zero as a root, it follows, again by [15, Criterion 1], that P (X) is a square of a polynomial in IK[X]. In particular, all roots of P (X) have even multiplicities.

We now fix i ∈ {1, 2, 3} and take a closer look at P_{i}(X). Let z_{i,1} and z_{i,2} be the roots of Q_{i}(X). Since P_{i}(X) = Q_{i}(X^{d_{i}}), it follows that all roots of P_{i}(X) are e^{2πiℓ/d_{i}}z_{i,j}^{1/d_{i}} for ℓ = 0, 1, …, d_{i}−1 and j = 1, 2, where z_{i,1}^{1/d_{i}} and z_{i,2}^{1/d_{i}} are two fixed determinations of these complex nonzero numbers. Thus, if P_{i}(X) has a double root, then it must be the case that e^{2πiℓ/d_{i}}z_{i,1}^{1/d_{i}} = e^{2πiℓ′/d_{i}}z_{i,2}^{1/d_{i}} for some ℓ, ℓ′ ∈ {0, 1, …, d_{i} − 1}. Upon exponentiating this last relation to the power d_{i}, we get z_{i,1} = z_{i,2}. Thus, Q_{i}(X) has a double root. This happens if and only if γ_{i}^{2}−4δ_{i} = 0, which leads to η^{e_{i}}γδ = 1/4. Furthermore, if this is the case, then z_{i,1} = z_{i,2} = γ_{i}/2 is an algebraic integer and P_{i}(X) = (X^{d_{i}} − γ_{i}/2)^{2} is the square of a polynomial whose coefficients are algebraic integers in IK.

6.3.1. The case of double roots. Assume that P_{i}(X) has a double root for some i ∈ {1, 2, 3}. Then writing {1, 2, 3} = {i, j, k}, we get, from the fact that P (X) and P_{i}(X) are both squares of other polynomials with coefficients in IK, that P_{j}(X)P_{ℓ}(X) is a square of a polynomial with coefficients in IK. If P_{j}(X) has a double root, then again z_{j,1} = z_{j,2} = γ_{j}/2 and P_{j}(X) = (X^{d_{j}} − γ_{j}/2)^{2}. This leads to the fact that P_{ℓ}(X) is also the square of a polynomial with coefficients in IK, therefore P_{ℓ}(X) = (X^{d_{ℓ}} − γ_{ℓ}/2)^{2}.

Put R(X) = ∏_{i=1}^{3}(X^{d_{i}} − γ_{i}/2). Thus, R(X) is monic and P (X) = R^{2}(X). For a fixed t even, we have that abc is associated in IK to γ^{1/2}R(ρ^{t}), where γ′ = γ^{1/2}. Indeed, note that abc = γ^{3}ρ^{x+y+z+e_{1}+e_{2}+e_{3}}· R^{2}(ρ^{t}), and

x + y + z + e_{1} + e_{2} + e_{3} = t(d_{1} + d_{2} + d_{3}) + 2(e_{1} + e_{2} + e_{3})

is even, therefore γ′ must be a member of IK. Since bc is associated to γ^{2}P_{3}(ρ^{t}) = γ^{2}((ρ^{t})^{d_{3}} − γ_{3}/2)^{2}, we have that a is associated to H(ρ^{t}), where

H(X) = γ′γ^{−2} \frac{(X^{d_{1}} − γ_{1}/2)(X^{d_{2}} − γ_{2}/2)}{(X^{d_{3}} − γ_{3}/2)}.

We now show that H(X) is a polynomial. Assume that this is not so and let H(X) = F (X)/G(X), where G(X) is of positive degree and F (X) and G(X) are coprime. Then the algebraic integer G(ρ^{t}) in IK divides the resultant Res_{X}(F (X), G(X)) evaluated at X = ρ^{t}, which is a nonzero algebraic integer in IK. Thus, G(ρ^{t}) is associated to some element from a finite list in IK. However, since G(X) is of positive degree and does not have zero as a root, this resulting Diophantine equation has only finitely many positive integer solutions t. In fact, by the classical theory of Diophantine equations (see [19], for example), this Diophantine equation can be immediately reduced to a unit equation in three terms in IK[(γ_{3}/2)^{1/d_{3}}]. This contradiction shows that H(X) is a polynomial, therefore that X^{d_{3}} − γ_{3}/2 divides (X^{d_{1}} − γ_{1}/2)(X^{d_{2}} − γ_{2}/2). The polynomials X^{d_{3}} − γ_{3}/2 and X^{d_{i}} − γ_{i}/2 can have at most gcd(d_{3}, d_{i}) roots in common for i = 1, 2. Thus, d_{3} ≤ gcd(d_{3}, d_{1}) + gcd(d_{3}, d_{1}). Since d_{3} ≥ d_{2} ≥ d_{1}, it follows that either d_{3} = d_{2}, or d_{1} = d_{2} = d_{3}/2. If d_{3} = d_{2}, then by putting d = d_{3} and using the fact that X^{d} − γ_{3}/2 and X^{d} − γ_{2}/2 have a root in common, we also get γ_{3} = γ_{2}, therefore ρ^{e_{2}} = ρ^{e_{3}}. Thus, z = y which is not allowed. Finally, if d_{1} = d_{2}, then using the fact that also X^{d_{1}} − γ_{1}/2 and X^{d_{2}} − γ_{2}/2 have a root in common (because a becomes arbitrarily large), we get that γ_{1} = γ_{2}, therefore e_{1} = e_{2}, leading to x = y, which is again not allowed.

We now return to the situation where P_{i}(X) = (X^{d_{i}} − γ_{i}/2)^{2} but P_{j}(X) does not have a double root. Then P_{ℓ}(X) does not have a double root either, and since P_{j}(X)P_{ℓ}(X) is a square, we get that P_{j}(X) = P_{ℓ}(X). By identifying degrees and coefficients, we get d_{j} = d_{ℓ} and γ_{j} = γ_{ℓ}. The last equation implies that ρ^{e_{j}} = ρ^{e_{ℓ}}; hence, e_{j} = e_{j}. Since (d_{j}, e_{j}) = (d_{ℓ}, e_{ℓ}), we get again that the two of the three variables {x, y, z} corresponding to j and ℓ are equal, which is impossible.

6.3.2. Bounding the number of common roots. From now on, we can assume that all three polynomials P_{1}(X), P_{2}(X) and P_{3}(X) have only simple roots. We look at

P_{3}(X) = (X^{d_{3}} − z_{3,1})(X^{d_{3}} − z_{3,2}),

and count the number of common roots that P_{3}(X) can have with P_{i}(X) for some i = 1, 2. Let

P_{i}(X) = (X^{d_{i}} − z_{i,1})(X^{d_{i}} − z_{i,2}).

Note that both P_{3}(X) and P_{i}(X) are product of two binomial polynomials. Our aim is to show that P_{3}(X) has ≤ 2 gcd(d_{3}, d_{1}) roots in common with each of P_{i}(X) for i = 1, 2.

Assume say that z_{3,1}/z_{3,2} is not a root of 1. Suppose that z_{i,1}/z_{i,2} is not a root of 1 either. Then, since all roots of X^{d_{3}} −z_{3,1} differ one from another multiplicatively by roots of unity, it follows that if X^{d_{3}} − z_{3,1} has a root in common with X^{d_{i}} − z_{i,j}, then it will not have a root in common with X^{d_{i}} − z_{i,ℓ}, where {j, ℓ} = {1, 2}. Thus, in this case there exists at most one j ∈ {1, 2} such that X^{d_{3}} − z_{3,1} has a common root with X^{d_{i}} − z_{i,j}, and clearly the number of such roots is ≤ gcd(d_{3}, d_{i}). Hence, X^{d_{3}} − z_{3,1} has at most gcd(d_{3}, d_{i}) common roots with P_{i}(X). The same is true for X^{d_{3}} − z_{3,2}. Hence, in this case the number of common roots of P_{3}(X) and P_{i}(X) is ≤ 2 gcd(d_{3}, d_{i}).

Assume now that still z_{3,1}/z_{3,2} is not a root of 1, but that z_{i,1}/z_{i,2} is a root of 1. If each of X^{d_{3}} − z_{3,i} for i = 1, 2 has common roots with at most one of the two binomials X^{d_{i}} − z_{i,j} for j = 1, 2, then the above argument shows again that the number of common roots of P_{3}(X) and P_{i}(X) is at most 2 gcd(d_{3}, d_{i}). If say X^{d_{3}} − z_{3,1} has common roots with both X^{d_{i}} − z_{i,1} and X^{d_{i}} − z_{i,2}, then it has at most gcd(d_{3}, d_{i}) common roots with each one of them, while X^{d_{3}} − z_{3,2} does not have common roots neither with X^{d_{i}}−z_{i,1}, nor with X^{d_{i}}−d_{i,2}, since otherwise z_{3,1}/z_{3,2} will end up being a root of 1, which is not the case. Hence, again P_{3}(X) and P_{i}(X) have at most 2 gcd(d_{3}, d_{i}) roots in common.

Assume next that z_{3,1}/z_{3,2} is a root of 1, but that z_{i,1}/z_{i,2} is not. If both X^{d_{3}} − z_{3,1} and X^{d_{3}} − z_{3,2} have common roots with P_{i}(X), then these common roots will be roots of X^{d_{i}} − z_{i,j} for the same value of j. Thus, each of X^{d_{3}} − z_{3,1} and X^{d_{3}} − z_{3,2} will have at most gcd(d_{3}, d_{i}) common roots with X^{d_{i}} −z_{i,j} (and none common with X^{d_{i}} −z_{i,ℓ}, where ℓ is such that {j, ℓ} = {1, 2}), so again P_{3}(X) and P_{i}(X) have at most 2 gcd(d_{3}, d_{i}) roots in common. Of course, if only one of X^{d_{3}} − z_{3,j} for j = 1, 2 has common roots with P_{i}(X), then again it will have common roots with only one of X^{d_{i}} − z_{i,ℓ} for ℓ = 1, 2, and the number of such is ≤ gcd(d_{3}, d_{i}), so in this case P_{3}(X) and P_{i}(X) have at most gcd(d_{3}, d_{i}) < 2 gcd(d_{3}, d_{i}) common roots.

So far, we have always obtained that P_{3}(X) and P_{i}(X) have at most 2 gcd(d_{i}, d_{3}) roots in common.

Assume now finally that both z_{3,1}/z_{3,2} and z_{i,1}/z_{i,2} are roots of 1.

Note that (z_{i,1}γρ^{e_{i}}, z_{i,2}γρ^{e_{i}}) are the roots of X^{2} − X + η^{e_{i}}γδ, and γδ ∈ Q^{∗} because γ and δ are conjugates in IK. Thus, while z_{i,1}, z_{i,2} might belong to a quadratic field over IK (hence, a field of degree 4 over Q), their ratio belongs to a quadratic field. Thus, if z_{i,1}/z_{i,2} ≠ 1 is a root of 1, then its order is one of 2, 3, 4, or 6. Note next that the order cannot be 2 (i.e., z_{i,1} = −z_{i,2}), because the coefficient of X in the quadratic polynomial X^{2} − X + η^{e_{i}}γδ is not zero. Hence, z_{i,1}/z_{i,2} is a root of unity of order 3, 4, or 6. One checks easily that z_{i,1}/z_{i,2} is a root of 1 of orders 3, 4, 6, respectively, if and only if η^{e_{i}}γδ = 1, 1/2, or 1/3, respectively. Since we are discussing the case when both z_{3,1}/z_{3,2} and z_{i,1}/z_{i,2} are roots on unity, we deduct that either η = 1, or η = −1 and e_{i} ≡ e_{3} (mod 2), and in any case these two roots of unity have the same order. Let this order be k ∈ {3, 4, 6}, and put ε = e^{2πi/k}.

If each of X^{d_{3}} − z_{3,1} and X^{d_{3}} − z_{3,2} has common roots with at most one of two polynomials X^{d_{i}} − z_{i,1} and X^{d_{i}} − z_{i,2}, then the previous argument shows that P_{3}(X) and P_{i}(X) have at most 2 gcd(d_{3}, d_{i}) roots in common. Further, if at most one of the two polynomials X^{d_{3}} − z_{3,1} and X^{d_{3}} − z_{3,2} has common roots with P_{i}(X), then again the previous argument shows that the number of common roots of P_{3}(X) and P_{i}(X) is at most 2 gcd(d_{3}, d_{i}).

We now look at the remaining cases. Here, we shall show that the number of common roots of P_{3}(X) and P_{i}(X) is < d_{3}.

We start by noting that up to relabeling the roots of P_{i}(X), we may assume that z_{i,1} = z_{i}, that z_{i,2} = z_{i}ε, and that X^{d_{3}} −z_{3,1} has a root η in common with X^{d_{i}} − z_{i}, and another root η′ in common with X^{d_{i}} − z_{i}ε. Certainly, z_{3,2} = z_{3,1}ε^{±1}, and X^{d_{3}} − z_{3,2} has a root in common with at least one of X^{d_{i}} − z_{i} or X^{d_{i}} − z_{i}ε.

Since X^{d_{3}} − z_{3,1} has a root in common with X^{d_{i}} − z_{i}, we get that there is a number ν such that ν^{d_{3}} = z_{3,1} and ν^{d_{i}} = z_{i}. Thus,

P_{i}(X) = (X^{d_{i}} − ν^{d_{i}})(X^{d_{i}} − ν^{d_{i}}ε).

Since X^{d_{3}} − ν^{d_{3}} has also a root in common with X^{d_{i}} − ν^{d_{i}}ε, it follows that for some integers j and ℓ we have

νe^{2πij/d_{3}} = νe^{2πi/(kd_{i})+2πiℓ/d_{i}}.

Thus,

\frac{1}{kd_{i}} ∈ \frac{ℓ}{d_{i}} − \frac{j}{d_{3}} + ZZ,

implying that lcm[d_{3}, d_{i}] is a multiple of kd_{i}. Thus, kd_{i} ≤ lcm[d_{3}, d_{i}] = d_{3}d_{i}/ gcd(d_{3}, d_{i}), giving gcd(d_{3}, d_{i}) ≤ d_{3}/k.

Suppose first that X^{d_{3}} − z_{3,2} does not have a common root with both of X^{d_{i}} − z_{i} and X^{d_{i}} − z_{i}ε. Then P_{3}(X) and P_{i}(X) have at most 3 gcd(d_{3}, d_{i}) ≤ 3d_{3}/k roots in common. Note that 3d_{3}/k ≤ d_{3}. Thus, P_{3}(X) and P_{i}(X) have at most d_{3} roots in common. Let us show that in fact the inequality is strict. From the above arguments, the inequality is strict unless k = 3 and gcd(d_{3}, d_{i}) = d_{3}/3. Put gcd(d_{3}, d_{i}) = λ. Then d_{3} = 3λ and d_{i} ∈ {λ, 2λ}. If d_{i} = λ, then P_{i}(X) has a totality of 2λ < d_{3} roots, and we obtain a contradiction. Thus, d_{i} = 2λ. Hence,

P_{3}(X) = (X^{3λ}−ν^{3λ})(X^{3λ}−ν^{3λ}ε^{±1}), P_{i}(X) = (X^{2λ}−ν^{2λ})(X^{2λ}−ν^{2λ}ε).

However, it is now easy to see that X^{3λ}−ν^{3λ}ε^{±1} cannot have a common root with P_{i}(X). Indeed, any such common root x will satisfy x^{3λ} = ν^{3λ}ε^{±1} and either x^{2λ} = ν^{2λ} (leading to ν^{6λ}ε^{±2} = x^{6λ} = ν^{6λ}, which is false since ε^{±2} ≠ 1), or x^{2λ} = ν^{2λ}ε (leading to ν^{6λ}ε^{±2} = x^{6λ} = ν^{6λ}ε^{3}, which is again false since ε^{3} = 1 and ε^{±2} ≠ 1).

So, it remains to treat the case when also X^{d_{3}} − z_{1,3}ε^{±1} has a root in common with both X^{d_{i}} −z_{i} and X^{d_{i}} −z_{i}ε. With the previous notations, since X^{d_{3}} − ν^{d_{3}}ε^{±1} and X^{d_{i}} − ν^{d_{i}} have a root in common, we get that for some integers j and ℓ we have νe^{±2πi/(kd_{3})+2πij/d_{3}} = νe^{2πiℓ/d_{i}}. This leads to

±\frac{1}{kd_{3}} ∈ \frac{ℓ}{d_{i}} − \frac{j}{d_{3}} + ZZ,

so lcm[d_{3}, d_{i}] is a multiple of kd_{3}. Thus, kd_{3} ≤ lcm[d_{3}, d_{i}], leading to gcd(d_{3}, d_{i}) ≤ d_{i}/k. In particular, d_{i} ≠ d_{3}. Write λ = gcd(d_{3}, d_{i}). Then d_{i} ≥ kλ, therefore d_{3} ≥ (k + 1)λ. Thus, λ ≤ d_{3}/(k + 1). Since P_{3}(X) and P_{i}(X) have at most 4λ roots in common anyway, we get that the number of common roots of these two polynomials is ≤ 4d_{3}/(k + 1) ≤ d_{3}. Equality is obtained if and only if k = 3 and d_{3} = 4λ. Clearly, d_{i} cannot be λ (otherwise P_{i}(X) and P_{3}(X) will have at most 2d_{i} ≤ 2λ < d_{3} roots in common), and d_{i} ≠ 2λ, for otherwise λ = gcd(d_{3}, d_{i}) = 2λ, which is a contradiction. So, it must be the case that d_{i} = 3λ. Hence,

P_{3}(X) = (X^{4λ}−ν^{4λ})(X^{4λ}−ν^{4λ}ε^{±1}), P_{i}(X) = (X^{3λ}−ν^{3λ})(X^{3λ}−ν^{3λ}ε).

Note now that the second factor of P_{i}(X) above cannot have a common root x with the first factor of P_{3}(X) above, for if not, we would have ν^{12λ} = x^{12λ} = ν^{12λ}ε^{4}, therefore ε^{4} = 1, which is false.

Having covered all the possibilities, we get that P_{3}(X) has < d_{3} common roots with P_{i}(X). If this is true for both i, j ∈ {1, 2}, it follows that there is a root of P_{3}(X) which is not a root of P_{1}(X)P_{2}(X), and this is a contradiction because P_{1}(X)P_{2}(X)P_{3}(X) has the property that all its roots are double.

So, there could be at most one i ∈ {1, 2} such that P_{3}(X) has common < d_{3} common roots with P_{i}(X), and for j ∉ {i, 3}, P_{3}(X) and P_{j}(X) have at most 2 gcd(d_{3}, d_{j}) roots in common. If gcd(d_{3}, d_{j}) ≠ d_{3}, it follows that gcd(d_{3}, d_{j}) ≤ d_{3}/2, so P_{3}(X) has < 2d_{3} roots in common with P_{1}(X)P_{2}(X), which is false. So, it must be the case that gcd(d_{3}, d_{j}) = d_{3}, so d_{j} = d_{3}. Write d = d_{3}. Thus,

P_{3}(X) = (X^{d} − z_{3,1})(X^{d} − z_{3,2}), P_{j}(X) = (X^{d} − z_{j,1})(X^{d} − z_{j,2}).

But it is clear that if the above polynomials have more than d roots in common, then they will have all roots in common so they will coincide. In particular, d_{3} = d_{j} and γ_{3} = γ_{j}, leading to e_{3} = e_{j}, so we get again the contradiction that two of the positive integer unknowns x, y and z are equal. Hence, P_{3}(X) and P_{j}(X) have at most d_{3} roots in common, therefore P_{3}(X) and P_{1}(X)P_{2}(X) have less than 2d_{3} roots in common, which is false.

In conclusion, it must be the case that P_{3}(X) has ≤ 2 gcd(d_{3}, d_{i}) roots in common with each of P_{i}(X) for i = 1, 2. Thus, 2d_{3} ≤ 2 gcd(d_{3}, d_{1}) + 2 gcd(d_{3}, d_{2}), therefore either d_{2} = d_{3}, or d_{1} = d_{2} = d_{3}/2. Assume that d_{1} = d_{2} = d_{3}/2. Then P_{3}(X) has at most d_{3} roots in common with each of P_{1}(X) and P_{2}(X). Since all its roots are common to either P_{1}(X) or P_{2}(X), we get that P_{3}(X) and P_{1}(X)P_{2}(X) are monic and have the same roots which are all simple for each of these two polynomials. Hence, P_{3}(X) = P_{1}(X)P_{2}(X). Evaluating this in X = ρ^{t} with large t, we get that a = O(1), which is a contradiction.

6.3.3. The case d_{1} < d_{2} = d_{3}. Let d = d_{2} = d_{3}. Then the two polynomials

P_{3}(X) = (X^{d} − z_{3,1})(X^{d} − z_{3,2}), P_{2}(X) = (X^{d} − z_{2,1})(X^{d} − z_{2,3})

cannot have more than d root in common, for otherwise, by an argument already used before, we would get that they coincide, therefore z = y, which is a contradiction. Thus, P_{3}(X) and P_{2}(X) have exactly d roots in common, therefore P_{3}(X) and P_{1}(X) also have d roots in common. Since the number of such roots is ≤ 2 gcd(d_{3}, d_{1}), we get that either d_{1} = d, or d_{1} = d/2. Assume that d_{1} = d/2. Then P_{1}(X) divides P_{3}(X). Furthermore, up to relabeling the roots of Q_{2}(X), it follows that we may assume that gcd(P_{3}(X), P_{2}(X)) = X^{d} − z_{2,1}. Then P_{1}(X)P_{2}(X)P_{3}(X) = P_{1}(X)^{2}(X^{d} − z_{2,1})^{2}(X^{d} − z_{2,2}), and since this must be the square of a polynomial with coefficients in IK, we get that X^{d} − z_{2,2} is a square of a polynomial with coefficients in IK, and this is false again.

6.3.4. The case d = d_{1} = d_{2} = d_{3}. It now follows immediately that Q_{1}(X)Q_{2}(X)Q_{3}(X) must be a perfect square of a polynomial of degree 3 with coefficients in IK[X]. Furthermore, Q_{i}(X) and Q_{j}(X) have precisely one root in common for all i ≠ j ∈ {1, 2, 3}. We now analyze this last situation.

Assume first that either η = 1, or η = −1 but that e_{1}, e_{2}, e_{3} are all congruent modulo 2. Let us write u and v for the roots of X^{2} − X + η^{e}γδ, where the value of e modulo 2 is congruent to e_{i} (i = 1, 2, 3) in case η = −1. It then follows that Q_{i}(X) has roots uγ^{−1}ρ^{−e_{i}} and vγ^{−1}ρ^{−e_{i}}. Note that since Q_{i}(X) ∈ IK[X] for all i ∈ {1, 2, 3}, and any two of them have precisely one root in common, it follows that u, v ∈ IK. Furthermore, since u/v ≠ ±1, and IK is real, it follows, up to interchanging u and v, that we may assume |u| > |v|. Since the root uγ^{−1}ρ^{−e_{i}} is also a root of Q_{j}(X) for some j ∈ {1, 2, 3}\{i}, we get that either uγ^{−1}ρ^{−e_{i}} = uγ^{−1}ρ^{−e_{j}}, leading to e_{i} = e_{j}, therefore two of the positive integer unknowns x, y and z are equal, which is impossible, or for each i there is j ≠ i such that uγ^{−1}ρ^{−e_{i}} = vγ^{−1}ρ^{−e_{j}}. Thus, u/v = ρ^{e_{i}−e_{j}}, and since |u| > |v| and ρ > 1, we get that e_{i} > e_{j}. Thus, for each i ∈ {1, 2, 3}, there is j ≠ i in the same set such that e_{i} > e_{j}. This is of course impossible because there must be some index i such that e_{i} = min{e_{j} : j ∈ {1, 2, 3}}.

Finally, we assume that η = −1 and that not all e_{i} are congruent modulo 2 for i = 1, 2, 3. Thus, there are two of them, say i and j such that e_{i} ≡ e_{j} (mod 2), and the third one ℓ is such that e_{ℓ} ≢ e_{i} (mod 2). Let e ≡ e_{i} (mod 2), and we assume that u and v are the roots of X^{2} − X + (−1)^{e}γδ, and that u_{1} and v_{1} are the roots of X^{2} − X − (−1)^{e}γδ. An argument used previously shows that u, v, u_{1}, v_{1} are all in IK. In particular, they are real. Then the pairs of roots of Q_{i}(X), Q_{j}(X) and Q_{ℓ}(X) are (uγ^{−1}ρ^{−e_{i}}, vγ^{−1}ρ^{−e_{i}}), (uγ^{−1}ρ^{−e_{j}}, vγ^{−1}ρ^{−e_{j}}), and (u_{1}γ^{−1}ρ^{−e_{ℓ}}, v_{1}γ^{−1}ρ^{−e_{ℓ}}), respectively. Up to interchanging u and v, we may assume that uγ^{−1}ρ^{−e_{i}} is also a root of Q_{j}(X). If uγ^{−1}ρ^{−e_{i}} = uγ^{−1}ρ^{−e_{j}}, we then get again e_{i} = e_{j}, which leads again to the conclusion that two of the three positive integer unknowns x, y and z coincide, which is false. Thus, uγ^{−1}ρ^{−e_{i}} = vγ^{−1}ρ^{−e_{j}}, so u/v = ρ^{e_{i}−e_{j}}. In particular, (−1)^{e}δγ = uv = v^{2}(u/v) = v^{2}ρ^{e_{i}−e_{j}} is a positive number. Now each of the roots of Q_{ℓ}(X) is also a root of Q_{i}(X) or Q_{j}(X). In particular, u_{1}γ^{−1}ρ^{−e_{ℓ}} = w_{1}γ^{−1}ρ^{−e_{m}} and v_{1}γ^{−1}ρ^{−e_{ℓ}} = w_{2}γ^{−1}ρ^{−e_{n}}, where w_{1}, w_{2} ∈ {u, v}, and m, n ∈ {i, j}. Hence, (−1)^{e+1}δγ = u_{1}v_{1} = w_{1}w_{2}ρ^{2e_{ℓ}−e_{m}−e_{n}}, but this last number is positive since ρ > 1 and w_{1}w_{2} ∈ {u^{2}, v^{2}, uv}. This contradicts the fact that (−1)^{e}γδ > 0, and completes the proof of Theorem 1.

References

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

[2] Y. Bugeaud – A. Dujella, On a problem of Diophantus for higher powers, Math. Proc. Cambridge Philos. Soc. 135 (2005), 1–10.

[3] Y. Bugeaud – F. Luca, On the period of the continued fraction expansion of square root of 2^{2n+1} + 1, Indag. Math., NS 16 (2005), 21–35.

[4] P. Corvaja – U. Zannier, Diophantine equations with power sums and Universal Hilbert Sets, Indag. Math., NS 9 (1998), 317-332.

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

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

[7] A. Dujella, There are only finitely many Diophantine quintuples, J. reine angew. Math. 566 (2004), 183–214.

[8] A. Dujella, Diophantine m-tuples, webpage available under http:// web.math.hr/∼duje/dtuples.html

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

[10] C. Fuchs, Diophantine problems with linear recurrences via the Subspace Theorem, Integers: Electronic Journal of Combinatorial Number Theory 5 (2005), #A08.

[11] C. Fuchs, Polynomial-exponential equations involving multirecurrences, Studia Sci. Math. Hungar., to appear.

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

[13] F. Luca, On shifted products which are powers, Glas. Mat. Ser. III 40 (2005), 13–20.

[14] F. Luca, On the greatest common divisor of u−1 and v −1 with u and v near S-units, Monatsh. Math. 146 (2005), 239–256.

[15] F. Luca – T. N. Shorey, Diophantine equations with products of consecutive terms in Lucas sequences, II, Acta Arith., to appear.

[16] F. Luca – L. Szalay, Fibonacci Diophantine triples, Preprint, 2007.

[17] H. P. Schlickewei – W. M. Schmidt, Linear equations in members of recurrence sequences, Ann. Scuola Norm. Sup. Pisa Cl. Sci. (4) 20 (1993), 219–246.

[18] W. M. Schmidt, Linear Recurrence Sequences and Polynomial-Exponential Equations, In: “Diophantine Approximation, Proc. of the C.I.M.E. Conference, Cetraro (Italy) 2000”, F. Amoroso – U. Zannier (eds.), Springer-Verlag, LN 1819, 2003, pp. 171–247.

[19] T. N. Shorey – R. Tijdeman, “Exponential Diophantine Equations”, Cambridge Univ. Press, Cambridge, 1986.

[20] J. Silverman, Generalized greatest common divisors, divisibility sequences, and Vojta’s conjecture for blowups, Monats. Math. 145 (2005), 333–350.

[21] K. R. Yu, p-adic logarithmic forms and group varieties, II, Acta Arith. 89 (1999), 337–378.

[22] U. Zannier, “Some applications of Diophantine Approximation to Diophantine Equations (with special emphasis on the Schmidt Subspace Theorem)”, Forum, Udine, 2003.

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

Clemens Fuchs Department of Mathematics, ETH Zürich, Rämistrasse 101, 8092 Zürich, Switzerland E-mail: clemens.fuchs@math.ethz.ch

Florian Luca Instituto de Matemáticas, Universidad Nacional Autónoma de México, C.P. 58180, Morelia, Michoacán, México E-mail: fluca@matmor.unam.mx

Laszlo Szalay Department of Mathematics and Statistics, University of West Hungary, 9400, Sopron, Bajcsi-Zs. út 4, Hungary E-mail: laszalay@ktk.nyme.hu