A POLYNOMIAL VARIANT OF A PROBLEM OF DIOPHANTUS FOR PURE POWERS

ANDREJ DUJELLA^{∗}, CLEMENS FUCHS^{‡} AND FLORIAN LUCA

Abstract. In this paper, we prove that there does not exist a set of 11 polynomials with coefficients in a field of characteristic 0 with the property that the product of any two distinct elements plus 1 is a perfect square. Moreover, we prove that there does not exist a set of 5 polynomials with the property that the product of any two distinct elements plus 1 is a perfect kth power with k ≥ 7. Combining these results, we get an absolute upper bound for the size of a set with the property that the product of any two elements plus 1 is a pure power.

2000 Mathematics Subject Classification: 11D99, 11C08, 05D10. Keywords: diophantine m-tuples, Mason’s inequality, function fields, Ramsey theory.

1. Introduction

Diophantus of Alexandria [6] was interested in finding sets with the property that the product of any two of its distinct elements increased by one is a perfect square. Such a set consisting of m elements is therefore called a Diophantine m-tuple. He gave the example \{\frac{1}{16}, \frac{33}{16}, \frac{17}{4}, \frac{105}{16}\}. The first Diophantine quadruple consisting of positive integers was found by Fermat and it was the set {1, 3, 8, 120}. The folklore conjecture is that there does not exist a quintuple consisting of positive integers and having the property of Diophantus. In 1969, Baker and Davenport [1] proved that the Fermat’s set cannot be extended to a Diophantine quintuple in ℤ. Recently, the first author proved that there does not exist a Diophantine sextuple, and there are only finitely many Diophantine quintuples over the integers (see [8]).

Many generalizations of this problem were considered since then, for example by adding a fixed integer n instead of 1 (which was first considered in [2], cf. also [7, 9] for bounds for general n and [14] for a recent absolute upper bound for the size of such a set for n prime), kth powers instead of squares (see [3]), or considering the problem over other domains than ℤ or ℚ. So we define:

∗The first author was supported by the Ministry of Science, Education and Sports, Republic of Croatia, grant 0037110.

‡The second author was supported by the Austrian Science Foundation FWF, grant NFN S9611.

This paper was partly written during a visit of the second author at the Department of Mathematics of the University of Zagreb within a joint Austrian-Croatian project granted by the Croatian Ministry of Science, Education and Sport and the Austrian Exchange Service (No. 23/2006).

Definition 1. Let m ≥ 2, k ≥ 2 and R be a commutative ring with 1. A kth power Diophantine m-tuple in R is a set {a_{1}, …, a_{m}} consisting of m different nonzero elements from R such that a_{i}a_{j} + 1 is a kth power of an element of R for 1 ≤ i < j ≤ m. Moreover, a set {a_{1}, …, a_{m}} of m different nonzero elements from R is called a pure power Diophantine mtuple if a_{i}a_{j} + 1 is a kth power of an element of R for some k ≥ 2 and all 1 ≤ i < j ≤ m.

We have already seen that for k = 2 and R = ℤ we have m ≤ 5. For larger values of k and R = ℤ, Bugeaud and Dujella [3] proved that

m ≤ 7 for k = 3,
m ≤ 5 for k = 4,
m ≤ 4 for 5 ≤ k ≤ 176,
m ≤ 3 for k ≥ 177.

Recently, Luca [21] proved that if {a_{1}, …, a_{m}} ⊆ {1, …, N} is a pure power Diophantine m-tuple in ℤ, then

m ≤ c (\frac{log N}{log log N} )^{\frac{3}{2}}

for all sufficiently large values of N and an effectively computable constant c. This improves earlier results by several authors (cf. [17, 18, 4]). Moreover, he proved that under the ABC-conjecture the size of a pure power Diophantine m-tuple in ℤ is bounded by an absolute constant (see [21, Theorem 1.4, p. 14]). This improves a result from [5].

Besides the cases R = ℚ and R = ℤ, also polynomial variants of the above problem have been considered. The first such variant was studied by Jones [19], [20], and it was for the case R = ℤ[X] and k = 2. Other results for this case can be found in [11], where the authors proved that for every Diophantine quadruple {a, b, c, d} in ℤ[X], where not all the polynomials are constant, we have (a+b−c−d)^{2} = 4(ab+1)(cd+1). This implies that every Diophantine triple in ℤ[X] can be extended to a Diophantine quadruple in an essentially unique way.

In [10], Dujella and Fuchs proved that there does not exist a set of four polynomials in ℤ[X] with the property that the product of any two is one greater than a perfect square in ℤ[X]. Dujella and Fuchs jointly with Tichy [12] and Walsh [13] considered generalizations of the problem to sets where the product of any two plus a linear polynomial n = aX + b is a perfect square. In this case, they proved best possible upper bounds for sets where all polynomials have the same degree. Moreover, they showed that there does not exist a set with more than 12 polynomials in ℤ[X] with the property that the product of any two plus a linear polynomial is a perfect square.

Dujella and Luca considered the case k ≥ 3 and R = 𝕂[X], where 𝕂 is an algebraically closed field of characteristic zero. Let us mention that in this case we have to assume that not all the polynomials in a kth power Diophantine m-tuple {a_{1}, …, a_{m}} are constant since any m-tuple of constant polynomials is a kth Diophantine m-tuple for any k ≥ 2. We will also assume this for the rest of the paper.

From this assumption, it follows that at most one of the polynomials a_{i} for i = 1, …, m is constant (this is Lemma 1 in [15]). We mention that the same conclusion is true (with very little modification of the proof) for pure power Diophantine m-tuples in 𝕂[X].

Now the main result from [15] was: if {a_{1}, …, a_{m}} is a kth power Diophantine m-tuple in 𝕂[X], then

m ≤ 5 for k = 3,
m ≤ 4 for k = 4,
m ≤ 3 for k ≥ 5,
m ≤ 2 for k ≥ 5 and k even.

Observe that the result for k = 2 is missing. The first aim of this paper is to close that gap by proving an upper bound for the size of a 2nd power Diophantine m-tuple in 𝕂[X]. We have the following theorem:

Theorem 1. There does not exist a 2nd power Diophantine 11-tuple in 𝕂[X], i.e.

m ≤ 10 for k = 2.

We remind the reader that in the case 𝕂 = ℤ, we already know that there does not exist a Diophantine 5-tuple (which is a consequence of the main result from [8]).

This result is derived by considering a gap principle together with an upper bound for the degrees of the elements of such a Diophantine m-tuple, which is obtained by reducing the problem to a system of Pellian equations and by studying the solutions to these Pellian equations which lie in finitely many binary linear recursive sequences. Here, we will use auxiliary results which are contained in the paper by Dujella and Luca [15].

As a second result, we prove an analogue of the conditional result for pure power Diophantine m-tuples which was obtained by Luca in [21] and which was mentioned above. We prove:

Theorem 2. There does not exist a pure power Diophantine quintuple where all perfect powers which appear are ≥ 7. In more details: there does not exist a set of five polynomials in 𝕂[X], not all of them constant, with the property that the product of any two distinct elements plus 1 is a perfect kth power with k ≥ 7.

As a consequence, we get the following result, which can be obtained as a combination of the previous results for fixed exponent and Ramsey theory [16] (this is the reason why the upper bound explodes compared to the results above). We mention that this strategy was first introduced in this context by Gyarmati, Sárközy and Stewart [18] and was later also used in [4, 5, 21].

Theorem 3. If {a_{1}, …, a_{m}} is a pure power Diophantine m-tuple in 𝕂[X], then m ≤ 2 · 10^{9}.

In fact, one can choose the Ramsey number R(11, 6, 4, 5; 2) as an upper bound (for a definition of Ramsey numbers we refer to Section 3). The parameters in this Ramsey number come from the cases of k = 2, 3, 5 and from Theorem 2. So, improving the above results on kth power Diophantine m-tuples will also reduce this bound. This is the case e.g. for pure power Diophantine m-tuples in ℤ[X], as mentioned above, where we get m ≤ R(5, 6, 4, 5; 2) ≤ 7362115 ≤ 8 · 10^{5}. By slightly changing the arguments in the proof of Theorem 2, it is possible to prove that there does not exist a pure power Diophantine quadruple in 𝕂[X] with all powers ≥ 8, but this would lead to m ≤ R(11, 6, 4, 4, 4; 2) ≤ 6 · 10^{10}.

The proofs of the last two theorems essentially run along the same line as the proof given by Luca in [21] (for the proof of Theorem 2 compare also with Lemma 2 and 3 in [15]). It is well known that the polynomial variant of the ABC-conjecture is solved, namely it appears as special case of the fundamental inequality obtained first by Mason (see [22] and also [24]), which is the function field analog of Baker’s method for linear forms in logarithms of algebraic numbers.

In Section 2, we will consider the case of k = 2 and R = 𝕂[X]. There we will give a proof of Theorem 1. In Section 3, we turn to the case of pure power Diophantine m-tuples and give proofs of Theorems 2 and 3.

2. Proof of Theorem 1

We start by proving a gap principle, which is well known in the classical case and which was also used in the results for ℤ[X].

We will say polynomial Diophantine m-tuple instead of 2nd power Diophantine m-tuple in 𝕂[X] for brevity.

Lemma 1. Let {a, b, c} be a polynomial Diophantine triple and ab + 1 = r^{2}. Let α, β, γ be degrees of a, b, c, respectively, and assume that α ≤ β ≤ γ. Then c = a + b ± 2r or γ ≥ α + β.

Proof. Let ac + 1 = s^{2} and bc + 1 = t^{2}. Consider the polynomials

d_{1} = a + b + c + 2abc + 2rst,
d_{2} = a + b + c + 2abc − 2rst.

We have

d_{1} · d_{2} = a^{2} + b^{2} + c^{2} − 2ab − 2ac − 2bc − 4.

Therefore, deg(d_{1}) + deg(d_{2}) ≤ 2γ. Since at most one of the elements of a polynomial Diophantine m-tuple is constant, we have that deg(d_{1}) ≠ deg(d_{2}). Let d_{−} be the polynomial with smaller degree among d_{1} and d_{2}. Then deg(d_{−}) < γ. It holds

ad_{−} + 1 = (at ± rs)^{2} = R^{2}, bd_{−} + 1 = (bs ± rt)^{2} = S^{2}.

Denote

c_{1} = a + b + d_{−} + 2abd_{−} + 2rRS,
c_{2} = a + b + d_{−} + 2abd_{−} − 2rRS.

Then ac_{1} + 1 = (aS + rR)^{2} = (abs ± art + art ± abs ± s)^{2} and ac_{2} + 1 = (aS − rR)^{2} = (abs ± art − art ∓ abs ∓ s)^{2}. Hence, there exist i ∈ {1, 2} such that ac_{i} + 1 = s^{2} = ac + 1, which implies c = c_{i}. Let c′ = c_{j}, where j ∈ {1, 2}, j ≠ i. Since c · c′ = c_{1}c_{2} = a^{2} + b^{2} + d_{−}^{2} − 2ab − 2ad_{−} − 2bd_{−} − 4, we have deg(c) + deg(c′) ≤ 2γ. Hence, deg(c) ≥ deg(c′).

Now we have two possibilities:

1) If d_{−} = 0, then R = ±1, S = ±1 and c = a + b ± 2r.

2) If d_{−} ≠ 0, then γ ≥ deg(abd_{−}) ≥ α + β. □

As a consequence of Lemma 1, we can prove the following gap principle for a polynomial Diophantine quadruple.

Lemma 2. If {a, b, c, d} is a polynomial Diophantine quadruple with 0 < α ≤ β ≤ γ ≤ δ, then δ ≥ β + γ.

Proof. Assume that δ < β + γ. Then, by Lemma 1, we have δ = γ. Consider the Diophantine triples {a, c, d} and {b, c, d}. Lemma 1 implies that d = a + c + 2s = b + c + 2t. This relation implies a − b = 2(t − s). Multiplying by t + s we obtain t + s = −2c, which clearly implies β = γ. But now we may apply Lemma 1 to the triple {a, b, d} and obtain

d = a + b + 2r = a + c + 2s = b + c + 2t.

From 2t − 2s = a − b and 2t + 2s = −4c, it follows 4t = a − b − 4c. Similarly, from 2t − 2r = a − c and 2t + 2r = −4b, it follows 4t = a − c − 4b. Hence, we obtained b = c, a contradiction. □

Before we can prove an upper bound for the degrees of the elements contained in a polynomial Diophantine quadruple, we will recall the method of reducing the problem of extending a Diophantine triple to a quadruple to the resolution of a system of Pellian equations.

Let ab + 1 = r^{2}, ac + 1 = s^{2}, bc + 1 = t^{2}, ad + 1 = x^{2}, bd + 1 = y^{2}, cd + 1 = z^{2}. Then

(1)  az^{2} − cx^{2} = a − c,
(2)  bz^{2} − cy^{2} = b − c.

By [15, Lemma 4], there exist a nonnegative integer m_{0} and a solution (Z_{0}, X_{0}) of (1) such that deg(Z_{0}) ≤ \frac{3γ−α}{4}, deg(X_{0}) ≤ \frac{α+γ}{4} and

z\sqrt{a} + x\sqrt{c} = (Z_{0}\sqrt{a} + X_{0}\sqrt{c})(s + \sqrt{ac})^{m_{0}},

and there exist a nonnegative integer n_{0} and a solution (Z_{1}, Y_{0}) of (2) such that deg(Z_{1}) ≤ \frac{3γ−β}{4} , deg(Y_{1}) ≤ \frac{β+γ}{4} and

z\sqrt{b} + y\sqrt{c} = (Z_{1}\sqrt{b} + Y_{1}\sqrt{c})(t + \sqrt{bc})^{n_{0}}.

Hence, z = V_{m_{0}} = W_{n_{0}}, where the sequences (V_{m})_{m≥0} and (U_{n})_{n≥0} are defined by

V_{0} = Z_{0}, V_{1} = sZ_{0} + cX_{0}, V_{m+2} = 2sV_{m+1} − V_{m}, (3) W_{0} = Z_{1}, W_{1} = tZ_{1} + cY_{1}, W_{n+2} = 2tW_{n+1} − W_{n}. (4)

The sequences satisfy the following congruence relations.

Lemma 3. We have

V_{2m} ≡ Z_{0} (mod c), V_{2m+1} ≡ sZ_{0} (mod c),
W_{2n} ≡ Z_{1} (mod c), W_{2n+1} ≡ tZ_{1} (mod c),

and

V_{2m} ≡ Z_{0} + 2c(aZ_{0}m^{2} + sX_{0}m) (mod c^{2}),
V_{2m+1} ≡ sZ_{0} + c(2asZ_{0}m(m + 1) + X_{0}(2m + 1)) (mod c^{2}),
W_{2n} ≡ Z_{1} + 2c(bZ_{1}n^{2} + tY_{1}n) (mod c^{2}),
W_{2n+1} ≡ tZ_{1} + c(2btZ_{1}n(n + 1) + Y_{1}(2n + 1)) (mod c^{2}).

Proof. This follows from (3) and (4) by induction. □

In the next lemma, we give relations between the initial terms Z_{0}, Z_{1}, X_{0}, Y_{1}.

Lemma 4.

1) If V_{2m} = W_{2n}, then Z_{0} = Z_{1}.

2) If V_{2m+1} = W_{2n}, then (Z_{0}, Z_{1}) = (±1, ±s), or (Z_{0}, Z_{1}) = (±s, ±1),

or Z_{1} = sZ_{0} + cX_{0} or Z_{1} = sZ_{0} − cX_{0}.

3) If V_{2m} = W_{2n+1}, then (Z_{0}, Z_{1}) = (±t, ±1), or Z_{0} = tZ_{1} + cY_{1}, or

Z_{0} = tZ_{1} − cY_{1}.

4) If V_{2m+1} = W_{2n+1}, then sZ_{0} + cX_{0} = tZ_{1} ± cY_{1}, or sZ_{0} − cX_{0} =

tZ_{1} ± cY_{1}.

Proof.

1) From Lemma 3, we have Z_{0} ≡ Z_{1} (mod c), and since deg(Z_{0}) < γ, deg(Z_{1}) < γ, we conclude that Z_{0} = Z_{1}.

2) We have Z_{1} ≡ sZ_{0} (mod c). If Z_{0} = ±1, then Z_{1} = ±s. If Z_{0} ≠ ±1, then deg(Z_{0}) ≥ \frac{γ}{2} , deg(X_{0}) ≥ \frac{α}{2} [15, Lemma 5]. If α = 0 and X_{0} is constant, then (Z_{0}, Z_{1}) = (±s, ±1). Indeed, assume that X_{0} is constant and put e = (X_{0}^{2} − 1)/a. Then {a, e, c} is a Diophantine triple, and now [15, Lemma 1] implies a = e, X_{0}^{2} = a^{2} + 1 and Z_{0}^{2} = s^{2}. Furthermore, Z_{1} ≡ sZ_{0} ≡ ±1 (mod c). Assume now that X_{0} is not constant. Since

(cX_{0} + sZ_{0})(cX_{0} − sZ_{0}) = c^{2} − ac − Z_{0}^{2},

we conclude that one of the polynomials cX_{0} + sZ_{0}, cX_{0} − sZ_{0} has degree less that γ, and they are both congruent to Z_{1} modulo c. Hence, one of these polynomials is equal to Z_{1}.

3) This case in completely analogous to case 2), except that β cannot be equal to zero.

4) We have sZ_{0} ≡ tZ_{1} (mod c). If X_{0} and Y_{1} are not constant then, as above, we conclude that one of the polynomials cX_{0}+sZ_{0}, cX_{0}−sZ_{0} and one of the polynomials cY_{1}+tZ_{1}, cY_{1}−tZ_{1} have degrees less than γ, and these two polynomials are congruent modulo c, thus, they have to be equal. If Z_{0} = ±1, then Z_{1} ≡ ±st (mod c). Since (±st − cr)(±st + cr) = ac + bc + 1 − c^{2}, one of the polynomials ±st−cr, ±st+cr has degree less then γ, and therefore it has to be equal to Z_{1}. But deg(Z_{1}) ≤ \frac{3γ−β}{4} , while deg(±st±cr) ≥ 2γ−(γ+ \frac{α+β}{2} ), a contradiction.

We have shown in 2) that if X_{0} is constant and Z_{0} ≠ ±1, then Z_{0} = ±s. Now from tZ_{1} ≡ ±1 (mod c), it follows Z_{1} = ±t and Y_{1}^{2} = b^{2} + 1, a contradiction. Finally, if Z_{1} = 1, then Z_{0} ≡ ±st (mod c) and Z_{0} has to be equal to ±st−cr or ±st+cr. But, as above, deg(Z_{0}) < deg(±st±cr).□

Now we are ready to prove the above mentioned upper bound.

Proposition 1. Let {a, b, c, d} be a polynomial Diophantine quadruple. Denote by α, β, γ, δ degrees of a,b,c,d, respectively. Assume that β > α and γ > 4β − α. Then δ < 3γ.

Proof. We will consider three cases, depending on parities of m_{0} and n_{0}.

Case 1. m_{0} = 2m, n_{0} = 2n.

From Lemmas 3 and 4, we have

aZ_{0}m^{2} + sX_{0}m ≡ bZ_{0}n^{2} + tY_{1}n (mod c). (5)

Both sides of (5) have degrees ≤ β + \frac{3γ−β}{4} < γ. Therefore, we can replace ≡ by = in (5):

aZ_{0}m^{2} + sX_{0}m = bZ_{0}n^{2} + tY_{1}n. (6)

Since α < β, we may assume that Z_{0} ≠ ±1. Furthermore, (6) implies that

(7)  deg(bZ_{0}n^{2} + tY_{1}n) < max(deg(bZ_{0}), deg(tY_{1})).

We have

(bZ_{0} + tY_{1})(bZ_{0} − tY_{1}) = b^{2} − bc − Y_{1}^{2},

which implies that deg(bZ_{0}) = deg(tY_{1}) and that one of the polynomials bZ_{0} + tY_{1}, bZ_{0} − tY_{1} has degree less than deg(bZ_{0}). But now (7) implies that n = 0 or n = 1.

Case 2. m_{0} = 2m + 1, n_{0} = 2n.

By Lemma 4, we have to consider three cases.

a) (Z_{0}, Z_{1}) = (±1, ±s).

Lemma 3 implies

(8)  ±2asm(m + 1) ± (2m + 1) ≡ ±2bsn^{2} ± 2rtn (mod c).

Both sides of (8) have degrees ≤ β + \frac{α+γ}{2} < γ. Hence, we have equality in (8). From (bs − rt)(bs + rt) = b^{2} − ab − bc − 1, we conclude that one of the polynomials bs − rt, bs + rt has degree less that deg(bs). Since the polynomial bsn^{2} ± rtn also has degree less that deg(bs), we conclude that n = 0 or n = 1.

b) (Z_{0}, Z_{1}) = (±s, ±1).

Now Lemma 3 implies

(9)  ±a ± 2am(m + 1) + X_{0}(2m + 1) ≡ ±2bn^{2} ± 2tn (mod c).

Since the degree of left-hand side is ≤ \frac{α+γ}{4} , and the degree of right-hand side is = \frac{β+γ}{2} < γ, we obtained a contradiction (unless n = 0).

c) Z_{1} = sZ_{0} ± cX_{0}.

Now Lemma 3 gives

(10) 2aZ_{1}m(m + 1) + X_{0}(2m + 1 ∓ 1) ≡ 2bZ_{1}n^{2} + 2tY_{1}n (mod c).

As in 1), we replace ≡ by =, and by examining the degree of right-hand side obtain a contradiction (unless n ≤ 1).

Case 3. m_{0} = 2m, n_{0} = 2n + 1.

We have to consider two cases.

a) (Z_{0}, Z_{1}) = (±t, ±1).

We obtain the following congruence

(11)  ±2atm^{2} ± 2rsm ≡ ±2btn(n + 1) ± (2n + 1) (mod c).

Since the degree of right-hand side of (11) is greater than the degree of left-hand side and less than γ, we obtain a contradiction as before (unless n = 0).

b) Z_{0} = tZ_{1} ± cY_{1}.

Now we have the congruence

(12) 2aZ_{0}m^{2} + 2sX_{0}m ≡ 2bZ_{0}n(n + 1) + Y_{1}(2n + 1 ± 1) (mod c),

and again the degree of right-hand side of (12) is greater than the degree of left-hand side and ≤ β + \frac{3γ−α}{4} < γ, which yields a contradiction (for n ≠ 0).

Case 4. m_{0} = 2m + 1, n_{0} = 2n + 1.

Now Lemma 3 gives (13) 2asZ_{0}m(m+1)+X_{0}(2m+1±1) ≡ 2btZ_{1}n(n+1)+Y_{1}(2n+1∓1) (mod c).

Noticing that tZ_{1} ≡ sZ_{0} (mod c) and multiplying (13) by s, we obtain (14) 2aZ_{0}m(m+1)+sX_{0}(2m+1±1) ≡ 2bZ_{0}n(n+1)+sY_{1}(2n+1±1) (mod c).

Among the four polynomials in (14), the largest degree has the polynomial 2bZ_{0}n(n + 1), and its degree is less than γ. This leads to a contradiction (unless n = 0).

Up to now, we proved that if n_{0} = 2n, then n = 0 or n = 1, and if n_{0} = 2n + 1, then n = 0. Therefore, we actually proved that

n_{0} ≤ 2.

Now, we have

cd + 1 = z^{2} = W_{n}^{2} ≤ W_{2}^{2}.

From

W_{2} = Z_{1} + 2c(bZ_{1} + tY_{1}),

we obtain

deg(W_{2}) ≤ γ + β + \frac{3γ − β}{4} = \frac{7γ + 3β}{4}

and

δ ≤ \frac{7γ + 3β}{2} − γ = \frac{5γ + 3β}{2} < 3γ.

□

Now we are ready to proof our first theorem. This will be done by combining the gap principle with the upper bound from the last proposition.

Proof of Theorem 1.

Assume that {a_{1}, a_{2}, …, a_{11}} is a polynomial Diophantine 11-tuple. Denote the degree of a_{i} by α_{i}, for i = 1, 2, …, 11. Let α_{1} ≤ α_{2} ≤ … ≤ α_{11}.

We will show that the triple {a_{1}, a_{4}, a_{8}} satisfies conditions on the triple {a, b, c} in Proposition 1. By Lemma 2, we have α_{4} > α_{1} and

α_{8} ≥ α_{7} + α_{6} ≥ 2α_{6} + α_{5} ≥ 3α_{5} + 2α_{4} ≥ 5α_{4}.

Therefore, we may apply Proposition 1. We obtain that

α_{11} < 3α_{8}.

On the other hand, Lemma 2 implies

α_{11} ≥ α_{10} + α_{9} ≥ 2α_{9} + α_{8} > 3α_{8},

a contradiction. □

3. Proofs of Theorems 2 and 3

Let us recall the definitions of the discrete valuations on the field 𝕂(X), where X is transcendental over the field 𝕂. For ξ ∈ 𝕂 define the valuation ν_{ξ} such that for f ∈ 𝕂(X) we have f(X) = (X − ξ)^{ν_{ξ}(Q)}a(X)/b(X) where a, b are polynomials with a(ξ)b(ξ) ≠ 0. Further, for f = a/b with a, b ∈ 𝕂[X], we put deg f := deg a − deg b; thus ν_{∞} := − deg is a discrete valuation on 𝕂(X). These are all discrete valuations on 𝕂(X).

We need the following generalization of the degree from 𝕂[X] to 𝕂(X). We define the height of f by

H(f) = − ∑_{ν} min{0, ν(f)}

where the sum is taken over all valuations on 𝕂(X); thus the height H(f) is just the number of poles of f counted according to multiplicity. We note that if f lies in 𝕂[X], then H(f) = deg f.

Now we state the following theorem on the solutions of two-dimensional unit equations over an algebraic function field, which is usually referred to as Mason’s inequality and which can be seen as an analog of Baker’s theorem concerning lower bounds for linear forms in logarithms of algebraic numbers. A proof of this theorem can be found in the monograph of Mason (cf. [22, Lemma 2]).

Theorem 4. (R.C. Mason) Let γ_{1}, γ_{2} and γ_{3} be non-zero elements of 𝕂(X) with γ_{1} + γ_{2} + γ_{3} = 0, and such that ν(γ_{1}) = ν(γ_{2}) = ν(γ_{3}) for each valuation ν not in the finite set V. Then

H(γ_{1}/γ_{2}) ≤ max{0, |V| − 2},

where |V| denotes the number of elements of V.

Now we are ready to prove our theorems. We start by obtaining a gap principle which gives an inequality between the degrees of the elements in a pure power Diophantine triple.

Lemma 5. Assume that a, b, c ∈ 𝕂[X] satisfy ac + 1 = u^{k} and bc + 1 = v^{ℓ} with u, v ∈ 𝕂[X] and k, ℓ ≥ k_{0} ≥ 3. Let α, β, γ be the degree of a, b, c, respectively, and assume that α ≤ β ≤ γ. Then

γ ≤ \frac{k_{0} + 2}{k_{0} − 2}β.

Proof. By eliminating c from the equations ac + 1 = u^{k}, bc + 1 = v^{ℓ} we get

bu^{k} − av^{ℓ} = b − a.

Applying Mason’s inequality (cf. Theorem 4) to this unit equation we get

H(bu^{k}/(b − a)) ≤ |V| − 2,

where V = {∞} ∪ {z ∈ 𝕂 : u(z) = 0, v(z) = 0, a(z) = 0, b(z) = 0, b(z) − a(z) = 0}. Observe that some of the zeros of a, b and b − a may coincide. The cardinality of this set can be bounded by

|V| ≤ 1 + \frac{1}{k} α + \frac{1}{k} γ + \frac{1}{ℓ}β + \frac{1}{ℓ}γ + β + α + ∑_{z∈𝕂}max\{0, ν_{z}(b − a) − ν_{z}(bu^{k})\},

since k deg u = deg ac = α + γ and ℓ deg v = deg bc = β + γ. Of course, this upper bound is not sharp in general. On the other hand, calculating the height under consideration, we get

H(bu^{k}/(b − a))

= − min{deg(b − a) − deg(bu^{k}), 0} − ∑_{z∈𝕂}min{0, ν_{z}(bu^{k}) − ν_{z}(b − a)}
= deg(bu^{k}) − deg(b − a) + ∑_{z∈𝕂}max{0, ν_{z}(b − a) − ν_{z}(bu^{k})}
≥ γ + α + ∑_{z∈𝕂}max{0, ν_{z}(b − a) − ν_{z}(bu^{k})}.

Observe that deg(bu^{k}) − deg(b − a) ≥ deg(u^{k}) = deg(ac) = γ + α ≥ 0. It follows that

γ ≤ (\frac{1}{k} + \frac{1}{ℓ} + 1) β + (\frac{1}{k} + \frac{1}{ℓ}) γ ≤ (\frac{2}{k_{0}} + 1) β + \frac{2}{k_{0}} γ

and therefore the bound in the lemma. □

By using Mason’s inequality once again, we prove an upper bound for the degree of the first element in a pure power Diophantine quadruple in terms of the degrees of the other three elements. We have:

Lemma 6. Assume that a_{1}, a_{2}, a_{3}, a_{4} ∈ 𝕂[X] are four different polynomials that satisfy a_{1}a_{2} +1 = x_{1}^{p_{1}}, a_{2}a_{3} +1 = x_{2}^{p_{2}}, a_{3}a_{4} +1 = x_{3}^{p_{3}}, a_{4}a_{1} +1 = x_{4}^{p_{4}} with x_{1}, x_{2}, x_{3}, x_{4} ∈ 𝕂[X] and p_{1}, p_{2}, p_{3}, p_{4} ≥ k_{0} ≥ 2 and let α_{1}, α_{2}, α_{3}, α_{4} denote the degree of a_{1}, a_{2}, a_{3}, a_{4}, respectively. Assume that α_{1} ≤ α_{2} ≤ α_{3} ≤ α_{4}. Then

α_{1} ≤ \frac{1}{k_{0} − 1}(α_{2} + α_{3} + α_{4}).

Proof. We have a_{1}a_{2}a_{3}a_{4} = (x_{1}^{p_{1}} − 1)(x_{3}^{p_{3}} − 1) = (x_{2}^{p_{2}} − 1)(x_{4}^{p_{4}} − 1) and using this identity we get

x_{1}^{p_{1}}x_{3}^{p_{3}} − x_{2}^{p_{2}}x_{4}^{p_{4}} = x_{1}^{p_{1}} + x_{3}^{p_{3}} − x_{2}^{p_{2}} − x_{4}^{p_{4}} = (a_{1} − a_{3})(a_{2} − a_{4}).

Observe that this expression is different from 0 since we assume that the polynomials are different. Now we apply Mason’s inequality (cf. Theorem 4) to the unit equation

x_{1}^{p_{1}}x_{3}^{p_{3}} − x_{2}^{p_{2}}x_{4}^{p_{4}} = (a_{1} − a_{3})(a_{2} − a_{4}).

Let V be the set of distinct zeros of x_{1}x_{2}x_{3}x_{4}(a_{1} −a_{3})(a_{2} −a_{4}) in 𝕂 together with ∞. Observe that some of the zeros of x_{1}x_{2}x_{3}x_{4} and (a_{1} − a_{3})(a_{2} − a_{4}) may coincide. Therefore the cardinality of V can be estimated by

|V| ≤ 1 + \frac{1}{p_{1}} (α_{1} + α_{2}) + \frac{1}{p_{3}} (α_{3} + α_{4}) + \frac{1}{p_{2}} (α_{2} + α_{3}) + \frac{1}{p_{4}} (α_{1} + α_{4})

+ ∑_{z∈𝕂}max{0, ν_{z}((a_{1} − a_{3})(a_{2} − a_{4})) − ν_{z}(x_{1}^{p_{1}}x_{3}^{p_{3}})}.

We mention that the upper bound is not sharp in general, since we counted the roots of x_{1}x_{2}x_{3}x_{4} by multiplicity and just used a partial correction in the term involving (a_{1} − a_{3})(a_{2} − a_{4}), but this will be enough to get our desired bound. First we get

H(x_{1}^{p_{1}}x_{3}^{p_{3}}/((a_{1} − a_{3})(a_{2} − a_{4})) ≤ |V| − 2,

and by calculating the height directly we obtain

H(x_{1}^{p_{1}}x_{3}^{p_{3}}/((a_{1} − a_{3})(a_{2} − a_{4})) = − min{0, deg((a_{1} − a_{3})(a_{2} − a_{4})) − (α_{1} + α_{2} + α_{3} + α_{4})}

− ∑_{z∈𝕂}min{0, ν_{z}(x_{1}^{p_{1}}x_{3}^{p_{3}}) − ν_{z}((a_{1} − a_{3})(a_{2} − a_{4}))}

≥ α_{1} + α_{2} + ∑_{z∈𝕂}max{0, ν_{z}((a_{1} − a_{2})(a_{3} − a_{4})) − ν_{z}(x_{1}^{p_{1}}x_{3}^{p_{3}})}.

By comparing upper and lower bound we get

2α_{1} ≤ α_{1} + α_{2} ≤ \frac{1}{p_{1}} (α_{1} + α_{2}) + \frac{1}{p_{3}} (α_{3} + α_{4}) + \frac{1}{p_{2}} (α_{2} + α_{3}) + \frac{1}{p_{4}} (α_{1} + α_{4})
≤ \frac{2}{k_{0}} (α_{1} + α_{2} + α_{3} + α_{4})

and thus

(1 − \frac{1}{k_{0}} ) α_{1} ≤ \frac{1}{k_{0}} (α_{2} + α_{3} + α_{4}).

From this, the claim follows. □

Now we are ready the give the proof of Theorem 2, which is obtained by comparing the upper and lower bound from Lemma 5 and 6.

Proof of Theorem 2.

Let {a_{1}, a_{2}, a_{3}, a_{4}, a_{5}} be a pure power Diophantine quintuple in 𝕂[X] such that the product of any two distinct elements plus 1 is a perfect kth power for some k ≥ k_{0} ≥ 3. We denote the degrees by α_{1}, α_{2}, α_{3}, α_{4}, α_{5}, respectively. Since at most one element in a pure power Diophantine mtuple is constant, it follows that α_{2} ≥ 1.

By Lemma 6, we get that

α_{2} ≤ \frac{1}{k_{0} − 1}(α_{3} + α_{4} + α_{5}).

Now, by using Lemma 5 several times (applied to {a_{1}, a_{2}, a_{3}}, {a_{1}, a_{2}, a_{4}} and {a_{1}, a_{2}, a_{5}}, respectively), it follows that

α_{2} ≤ \frac{1}{k_{0} − 1} [\frac{k_{0} + 2}{k_{0} − 2} + \frac{k_{0} + 2}{k_{0} − 2} + \frac{k_{0} + 2}{k_{0} − 2}] α_{2} = \frac{3(k_{0} + 2)}{(k_{0} − 1)(k_{0} − 2)}α_{2}.

Observe again that α_{2} ≥ 1. It follows

\frac{3(k_{0} + 2)}{(k_{0} − 1)(k_{0} − 2)} ≥ 1.

This inequality leads to a contradiction if k_{0} ≥ 7 (the left-hand side is a rational function in k_{0} which tends to 0 for k_{0} to infinity). This proves the theorem. □

Proof of Theorem 3.

We first note that we already know that there is no quintuple such that the product of any two plus one is a kth power with k ≥ 7 by Theorem 2. It remains to take only the possibilities with smaller exponents into account. Clearly, we can restrict to prime exponents and thus assume that the exponent k belongs to the list P = {2, 3, 5} of primes below 7.

Now let G be the graph whose vertices are the elements of the pure power Diophantine m-tuple. We color the edge of G with the 4 colors P ∪ {∞} in the following way: if a_{i}a_{j} + 1 = x^{k}, then the edge from a_{i} to a_{j} is colored with p if p is the smallest prime from P dividing k and with ∞ if there is no such p ∈ P.

Now it is clear that m ≤ R(11, 6, 4, 5; 2). Recall that the Ramsey number R(n_{s_{1}}, n_{s_{2}}, …, n_{s_{t}}; 2) is the smallest positive integer R such that no matter how we color the edges of the complete graph with R vertices with the colors s_{1}, s_{2}, …, s_{t}, there exist i and a complete monochromatic subgraph with n_{i} vertices colored with color i. The numbers n_{i} in our upper bound follow from our Theorem 1 (namely, n_{2} = 11), the bounds proved in [15] (namely, n_{3} = 6 and n_{5} = 4) and the bound from Theorem 2 (namely, n_{∞} = 5).

To simplify the upper bound we use the recurrence

R(n_{s_{1}}, n_{s_{2}}, …, n_{s_{t}}; 2)

≤ t − 2 + ∑_{i=1}^{t} R(n_{s_{1}}, …, n_{s_{i−1}}, n_{s_{i}} − 1, n_{s_{i+1}}, …, n_{s_{t}}; 2),

together with the facts that Ramsey numbers are symmetric with respect to the n_{i}, i.e.

R(n_{s_{1}}, n_{s_{2}}, …, n_{s_{t}}; 2) = R(n_{σ(s_{1})}, n_{σ(s_{2})}, …, n_{σ(s_{t})}; 2)

for a permutation σ of the set {s_{1}, …, s_{t}}, and that we have

R(2, n_{s_{1}}, n_{s_{2}}, …, n_{s_{t−1}}; 2) = R(n_{s_{1}}, n_{s_{2}}, …, n_{s_{t−1}}; 2),
R(n; 2) = n.

A list of upper bounds for small Ramsey numbers can be found in [23], e.g. we have R(3, 3; 2) = 6, R(3, 3, 3; 2) = 17 and R(3, 3, 3, 3; 2) ≤ 62. For all these results, we refer to the survey paper [23]. By using all the bounds there together with the general recurrence formula from above, it is easy to show that m ≤ 180952390 ≤ 2 · 10^{9}. This finishes the proof. □

References

[1] A. Baker and H. Davenport, The equations 3x^{2} −2 = y^{2} and 8x^{2} −7 = z^{2}, Quart. J. Math. Oxford Ser. (2) 20 (1969), 129–137.

[2] E. Brown, Sets in which xy +k is always a square, Math. Comp. 45 (1985), 613–620.

[3] Y. Bugeaud and A. Dujella, On a problem of Diophantus for higher powers, Math. Proc. Cambridge Philos. Soc. 135 (2003), 1-10.

[4] Y. Bugeaud and K. Gyarmati, On generalizations of a problem of Diophantus, Illinios J. Math. 48 (2004), 1105-1115.

[5] R. Dietmann, C. Elsholtz, K. Gyarmati, and M. Simonovits, Shifted products that are coprime pure powers, J. Comb. Theor. A 111 (2005), 24-36.

[6] Diophantus of Alexandria, Arithmetics and the Book of Polygonal Numbers, (I. G. Bashmakova, Ed.) (Nauka, 1974) (in Russian), 85–86, 215–217.

[7] A. Dujella, On the size of Diophantine m-tuples, Math. Proc. Cambridge Philos. Soc. 132 (2002), 23–33.

[8] A. Dujella, There are only finitely many Diophantine quintuples, J. Reine Angew. Math. 566 (2004), 183-214.

[9] A. Dujella, Bounds for the size of sets with the property D(n), Glas. Mat. Ser. III 39 (2004), 199-205.

[10] A. Dujella and C. Fuchs, A polynomial variant of a problem of Diophantus and Euler, Rocky Mountain J. Math. 33 (2003), 797-811.

[11] A. Dujella and C. Fuchs, Complete solution of the polynomial version of a problem of Diophantus, J. Number Theory 106 (2004), 326-344.

[12] A. Dujella, C. Fuchs, and R. F. Tichy, Diophantine m-tuples for linear polynomials, Period. Math. Hungar. 45 (2002), 21-33.

[13] A. Dujella, C. Fuchs, and G. Walsh, Diophantine m-tuples for linear polynomials. II. Equal degrees, J. Number Theory, to appear.

[14] A. Dujella and F. Luca, Diophantine m-tuples for primes, Intern. Math. Research Notices 47 (2005), 2913-2940.

[15] A. Dujella and F. Luca, On a problem of Diophantus with polynomials, Rocky Mountain J. Math., to appear (Preprint: http://www.math.hr/∼duje/dvi/dluca.dvi).

[16] R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey Theory, John Wiley & Sons, 1980.

[17] K. Gyarmati, On a problem of Diophantus, Acta Arith. 97 (2001), 53-65.

[18] K. Gyarmati, A. Sárközy, and C. L. Stewart, On shifted products which are powers, Mathematika 49 (2002), 227-230.

[19] B. W. Jones, A variation of a problem of Davenport and Diophantus, Quart. J. Math. Oxford Ser.(2) 27 (1976), 349–353.

[20] B. W. Jones, A second variation of a problem of Davenport and Diophantus, Fibonacci Quart. 15 (1977), 323–330.

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

[22] R. C. Mason, Diophantine equations over function fields, London Mathematical Society Lecture Notes Series, vol. 96, Cambridge University Press, Cambridge, 1984.

[23] S. P. Radziszowski, Small Ramsey numbers, Electronic J. Compu. Dynamical Survey DS1 (2004), 1-42.

[24] M. Rosen, Diophantine Equations over Function Fields, Cambridge Univ. Press, Cambridge, 2002.

Andrej Dujella Department of Mathematics University of Zagreb Bijenička cesta 30 10000 Zagreb Croatia E-mail: duje@math.hr

Clemens Fuchs Institut für Analysis und Computational Number Theory (Math A) TU Graz Steyrergasse 30/II A-8010 Graz Austria E-mail: clemens.fuchs@tugraz.at

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