ON THE DIOPHANTINE EQUATION G_{n}(x) = G_{m}(P (x))

CLEMENS FUCHS^{∗}, ATTILA PETHŐ^{†} AND ROBERT F. TICHY^{∗}

Dedicated to Edmund Hlawka to the occasion of his 85th birthday

Abstract. Let K be a field of characteristic 0 and let p, q, G_{0}, G_{1}, P ∈ K[x], deg P ≥ 1. Further let the sequence of polynomials (G_{n}(x))_{n=0}^{∞} be defined by the second order linear recurring sequence

G_{n+2}(x) = p(x)G_{n+1}(x) + q(x)G_{n}(x), for n ≥ 0.

In this paper we give conditions under which the diophantine equation G_{n}(x) = G_{m}(P (x)) has at most exp(10^{18}) many solutions (n, m) ∈ ℤ^{2}, n, m ≥ 0. The proof uses a very recent result on S-unit equations over fields of characteristic 0 due to J.-H. Evertse, H. P. Schlickewei and W. M. Schmidt (cf. [14]). Under the same conditions we present also bounds for the cardinality of the set

{(m, n) ∈ ℕ | m ≠ n, ∃ c ∈ K\{0} such that G_{n}(x) = c G_{m}(P (x))}.

In the last part we specialize our results to certain families of orthogonal polynomials.

1. Introduction

Let K denote a field of characteristic 0. There is no loss of generality in assuming that this field is algebraically closed and we will assume this for the rest of the paper. Let p, q, G_{0}, G_{1} ∈ K[x] and let the sequence of polynomials (G_{n}(x))_{n=0}^{∞} be defined by the second order linear recurring sequence

G_{n+2}(x) = p(x)G_{n+1}(x) + q(x)G_{n}(x), for n ≥ 0. (1)

By α(x), \overline{α}(x) we denote the roots of the corresponding characteristic polynomial

T^{2} − p(x)T − q(x). (2)

Let Δ(x) = p(x)^{2}+4q(x) be the discriminant of the characteristic polynomial of the recurring sequence (G_{n}(x))_{n=0}^{∞}. Then we have

α(x) = \frac{p(x) + \sqrt{Δ(x)}}{2}, \overline{α}(x) = \frac{p(x) − \sqrt{Δ(x)}}{2}.

Date: July 29, 2002. ∗This work was supported by the Austrian Science Foundation FWF, grant S8307-

MAT.

† The second author was supported by the Hungarian National Foundation for Scientific Research Grants No 16741 and 38225.

We will always assume that the recurring sequence is simple, which means that Δ(x) ≠ 0. Then for n ≥ 0

G_{n}(x) = g_{1}(x)α(x)^{n} + g_{2}(x)\overline{α}(x)^{n}, (3)

where

g_{1}(x) = \frac{G_{1}(x) − G_{0}(x)\overline{α}(x)}{α(x) − \overline{α}(x)} and g_{2}(x) = \frac{G_{1}(x) − G_{0}(x)α(x)}{α(x) − \overline{α}(x)}. (4)

Notice that

g_{1}, g_{2} ∈ K(x, \sqrt{p(x)^{2} + 4q(x)}) = K(x, \sqrt{Δ(x)}).

Therefore, we have

G_{n}(x) = \frac{G_{1}(x) − G_{0}(x)\overline{α}(x)}{α(x) − \overline{α}(x)}α(x)^{n} + \frac{G_{1}(x) − G_{0}(x)α(x)}{α(x) − \overline{α}(x)}\overline{α}(x)^{n}.

(G_{n}(x))_{n=0}^{∞} is called nondegenerate, if the quotient \overline{α}(x)/α(x) is not a root of unity.

Many diophantine equations involving the recurrence (G_{n}(x))_{n=0}^{∞} were studied previously. For example let us consider the equation

G_{n}(x) = s(x), (5)

where s(x) ∈ K[x] is given. We denote by N(s(x)) the number of integers n for which (5) holds. Schlickewei [19] established an absolute bound for N(s(x)), provided that the sequence is nondegenerate and that also α, \overline{α} are not equal to a root of unity. His bound was substantially improved by Beukers and Schlickewei [2] who showed that

N(s(x)) ≤ 61.

In the particular case that not all algebraic functions g_{1}(x)/s(x), g_{2}(x)/s(x), α(x), \overline{α}(x) are constants (which will always be the case in our paper), Beukers and Tijdeman (cf. Theorem 2 on p. 206 in [3]) showed that

N(s(x)) ≤ 3.

Very recently, Schmidt [20] obtained the remarkable result that for arbitrary nondegenerate complex recurring sequences of order q one has N(a) ≤ C(q), where a ∈ ℂ and C(q) depends only (and in fact triply exponentially) on q.

Another kind of result is due to Glass, Loxton and van der Poorten [15]. They showed that, if (G_{n}(x))_{n=0}^{∞} is nonperiodic and nondegenerate, then there are only finitely many pairs of integers m, n with m > n ≥ 0 and

G_{n}(x) = G_{m}(x). (6)

ON THE EQUATION G_{n}(x) = G_{m}(P (x)) 3

In a recent paper Dujella and Tichy [8] showed for linear recurring sequences G_{n+1}(x) = xG_{n}(x) + BG_{n−1}(x), G_{0}(x) = 0, G_{1}(x) = 1 of polynomials with B ∈ ℤ\{0} that there does not exist a polynomial P (x) ∈ ℂ[x] satisfying

G_{n}(x) = G_{m}(P (x)) (7)

(for all m, n ≥ 3, m ≠ n). Applying a general theorem of Bilu and Tichy [4], this result was used to show that the diophantine equation G_{n}(x) = G_{m}(y) has only finitely many solutions in integers n, m, x, y, with n ≠ m.

It is the aim of this paper to present suitable extensions of the results (5) and (7).

2. General Results

Our first main result is a generalization of (6) to the diophantine equation

G_{n}(x) = G_{m}(P (x)), (8)

where P ∈ K[x] is an arbitrary polynomial of degree ≥ 1. We show that under certain hypotheses, the number of pairs (n, m) with (8) is bounded above by an absolute constant.

Theorem 1. Let p, q, G_{0}, G_{1}, P ∈ K[x], deg P ≥ 1 and (G_{n}(x))_{n=0}^{∞} be defined as above. Assume that the following conditions are satisfied: 2 deg p > deg q ≥ 0 and

deg G_{1} > deg G_{0} + deg p ≥ 0, or
deg G_{1} < deg G_{0} + deg q − deg p.

Then there are at most min{exp(18^{10}), C(p, q, P)} pairs of integers (n, m) with n, m ≥ 0, n ≠ m such that

G_{n}(x) = G_{m}(P (x))

holds. We have

C(p, q, P) = 10^{28} · log(2C_{1} deg p) · (4e)^{8C_{1} deg q} · 7^{4C_{1} deg q},

where C_{1} = 2(deg P + 1).

Remark 1. If deg P = 1 then Theorem 1 does not remain valid if we allow m = n.

Remark 2. This example shows that also in the polynomial case the condition 2 deg p > deg q is needed. Assume that

G_{0}(x) = 1, G_{1}(x) = x,

G_{n+2}(x) = \frac{x}{2}G_{n+1}(x) + \frac{x^{2}}{2} G_{n}(x).

Here we have

2 deg p = deg q = 2 and deg G_{0} = 0, deg G_{1} = 1.

It follows that

G_{n}(x) = x^{n} ∀n.

In this case the following equation holds

G_{2n}(x) = G_{n}(x^{2})

for all integers n.

Remark 3. Let us consider the Chebyshev polynomials of the first kind, which are defined by

T_{n}(x) = cos(n arccos x).

It is well known that they satisfy the following second order recurring relation:

T_{0}(x) = 1, T_{1}(x) = x,
T_{n+2}(x) = 2xT_{n+1}(x) − T_{n}(x).

In this case we have

2 deg p > deg q and deg T_{1} = deg T_{0} + deg p = 1.

It is also well known and in fact easy to prove that

T_{2n}(x) = T_{n}(2x^{2} − 1)

holds for all integers n. This example shows that also the second assumption in Theorem 1 is needed.

Actually, it is also possible to give an upper bound for the number of pairs (m, n) with G_{n}(x) = c G_{m}(P (x)), c ∈ K^{∗} = K\{0} variable. This means that we can give an upper bound for the cardinality of the set

{(m, n) ∈ ℕ | m ≠ n, ∃ c ∈ K^{∗} such that G_{n}(x) = c G_{m}(P (x))}.

(Here c may vary with m, n). In fact, the second part of the upper bound in the last theorem, which depends on the degrees of the polynomials involved, follows from this more general theorem.

Theorem 2. Let p, q, G_{0}, G_{1}, P ∈ K[x], deg P ≥ 1 and (G_{n}(x))_{n=0}^{∞} be defined as above. Assume that the following conditions are satisfied: 2 deg p > deg q ≥ 0 and

deg G_{1} > deg G_{0} + deg p ≥ 0, or
deg G_{1} < deg G_{0} + deg q − deg p.

Then the number of pairs of integers (n, m) with n, m ≥ 0, n ≠ m for which there exists c ∈ K^{∗} with

G_{n}(x) = c G_{m}(P (x))

is at most C(p, q, P). We have

C(p, q, P) = 10^{28} · log(2C_{1} deg p) · (4e)^{8C_{1} deg q} · 7^{4C_{1} deg q},

where C_{1} = 2(deg P + 1).

It is also possible to replace the conditions concerning the degree by algebraic conditions.

Theorem 3. Let p, q, G_{0}, G_{1}, P ∈ K[x] and (G_{n}(x))_{n=0}^{∞} be defined as above. Assume that

(1) deg Δ ≠ 0,

(2) deg P ≥ 2,

(3) gcd(p, q) = 1 and

(4) gcd(2G_{1} − G_{0}p, Δ) = 1. Then there are at most min{exp(10^{18}), C̃(p, q, P)} pairs of integers (n, m) with n, m ≥ 0 such that

G_{n}(x) = G_{m}(P (x))

holds. We have

C̃(p, q, P) = 10^{28} · log(C_{1} max{2 deg p, deg q}) · (4e)^{8C_{1} deg q} · 7^{4C_{1} deg q},

where C_{1} = 2(deg P + 1).

Remark 4. The degree assumptions from Theorems 1 and 2 arise from considering the infinite valuation in the rational function field K(x), whereas by looking at the finite valuations one obtains the divisiblity conditions from Theorem 3.

Remark 5. It is obvious that for deg P = 1 Theorem 3 cannot hold in full generality. For example: if G_{n}(x) is a polynomial in x^{2} for all n we get

G_{n}(x) = G_{n}(−x)

for all n.

Remark 6. By looking at the proof, it is clear that Theorem 3 also holds, if we assume instead of (2) (2′) There is no c ∈ K such that Δ(P (x)) = cΔ(x) holds. To our knowledge this is the weakest condition under which our proof works. It is clear that (2′) holds if deg P ≥ 2 or if P is a constant. If P (x) = x then Δ(P (x)) = cΔ(x) holds with c = 1. Suppose that P (x) = ax + b with a, b ∈ K and a ≠ 0, (a, b) ≠ (1, 0). Denote by P^{(k)} the k-th iterate of P. Let Δ_{0} be the leading coefficient of Δ(x). It is left to the reader to show that Δ(P (x)) = cΔ(x) for some c ∈ K^{∗} if and only if a^{deg Δ} = c, a is a root of unity of order k > 1 and

Δ(x) = Δ_{0}(x + \frac{b}{a − 1})^{s} ∏_{i=1}^{r} ∏_{j=0}^{k−1}(x − P^{(j)}(x_{i})),

where r, s are non-negative integers with rk+s = deg Δ and −\frac{b}{a−1}, x_{1}, …, x_{r} are distinct elements of K.

The second part of the bound of Theorem 3 follows from Theorem 4 below, which deals with the case G_{n}(x) = c G_{m}(P (x)) with c ∈ K^{∗} variable.

Theorem 4. Let p, q, G_{0}, G_{1}, P ∈ K[x] and (G_{n}(x))_{n=0}^{∞} be defined as above. Assume that the conditions (1)-(4) of Theorem 3 are satisfied. Then the number of pairs of integers (n, m) with n, m ≥ 0 for which there exists c ∈ K^{∗} with

G_{n}(x) = c G_{m}(P (x))

is at most C̃(p, q, P). We have

C̃(p, q, P) = 10^{28} · log(C_{1} max{2 deg p, deg q}) · (4e)^{8C_{1} deg q} · 7^{4C_{1} deg q},

where C_{1} = 2(deg P + 1).

3. Results for Families of Orthogonal Polynomials

We will turn now our discussion to sequences of certain orthogonal polynomials satisfying (1). The following results can be found in the monograph of Borwein and Erdélyi [5, Chapter 2.3], Chihara [7, Chapter I and II] or Szegő [22, Chapter III]. Let (μ_{n})_{n=0}^{∞} be a sequence of complex numbers and let L : ℂ[x] ⟶ ℂ be a linear functional defined by

L[x^{n}] = μ_{n}, n = 0, 1, 2, ….

Then L is called the moment functional determined by the formal moment sequence (μ_{n}). The number μ_{n} is called the moment of order n. A sequence of polynomials (P_{n}(x))_{n=0}^{∞} with complex coefficients is called an orthogonal polynomial sequence (OPS) with respect to a moment functional L provided that for all nonnegative integers m and n the following conditions are satisfied:

(i) deg P_{n}(x) = n, (ii) L[P_{m}(x)P_{n}(x)] = 0 for m ≠ n, (iii) L[P_{n}^{2}(x)] ≠ 0. If there exists an OPS for L, then each P_{n}(x) is uniquely determined up to an arbitrary non-zero factor. An OPS in which each P_{n}(x) is monic will be referred to as a monic OPS; it is indeed unique.

It is well known that a necessary and sufficient condition for the existence of an OPS for a moment functional L with moment sequence (μ_{n}) is that for the determinants defined by

Δ_{n} = det(μ_{i+j})_{i,j=0}^{n} = | \begin{matrix}μ_{0} & μ_{1} & … & μ_{n} \\ μ_{1} & μ_{2} & … & μ_{n+1} \\ ⋮ & ⋮ & ... & ⋮ \\ μ_{n} & μ_{n+1} & … & μ_{2n} \end{matrix} |

the following conditions hold

Δ_{n} ≠ 0, n = 0, 1, 2, ….

In this case L is called quasi-definite.

A moment functional L is called positive-definite if L[π(x)] > 0 for every π(x) ∈ ℂ[x] that is not identically zero and which satisfies π(x) ≥ 0 for all real x. The following holds: L is positive-definite if and only if its moments are all real and Δ_{n} > 0 for all n ≥ 0. Furthermore, using the Gram-Schmidt process, a corresponding OPS consisting of real polynomials exists. Moreover, L is positive-definite if and only if a bounded, non-decreasing function ψ exists, whose moments

μ_{n} = ∫_{−∞}^{∞} x^{n}dψ(x), n = 0, 1, 2, …,

are all finite and for which the set

𝔖(ψ) = {x | ψ(x + δ) − ψ(x − δ) > 0 for all δ > 0}

is infinite. Further for the function ψ

∫_{−∞}^{∞} x^{n}dψ(x) = μ_{n} = L[x^{n}], n = 0, 1, 2, …

is valid. This is known as the representation theorem for positive-definite moment functionals or as the solution to the Hamburger moment problem.

Thus, an OPS with respect to a positive-definite moment functional L induces an inner product defined by

⟨p, q⟩ = L[p(x)\overline{q(x)}], p, q ∈ ℂ[x],

where \overline{q(x)} is obtained by taking the complex conjugates of the coefficients of q(x), on the linear space of polynomials with complex coefficients. In particular, we have ⟨P_{m}, P_{n}⟩ = L[P_{m}(x)\overline{P_{n}(x)}] = 0, m ≠ n. Thus, our definition of orthogonality for the OPS is consistent with the usual definition of orthogonality in an inner product space.

One of the most important characteristics of an OPS is the fact that any three consecutive polynomials are connected by a very simply relation: Let L be a quasi-definite moment functional and let (P_{n}(x))_{n=0}^{∞} be the corresponding monic OPS. Then there exist constants c_{n} and λ_{n} ≠ 0 such that

P_{n}(x) = (x − c_{n})P_{n−1}(x) − λ_{n}P_{n−2}(x), n = 1, 2, 3, …, (9)

where we define P_{−1}(x) = 0. Moreover, if L is positive-definite, then c_{n} is real and λ_{n+1} > 0 for n ≥ 1 (λ_{1} is arbitrary).

The converse is also true and it is referred to as Favard’s theorem: Let (c_{n})_{n=0}^{∞} and (λ_{n})_{n=0}^{∞} be arbitrary sequences of complex numbers and let (P_{n}(x))_{n=0}^{∞} be defined by the recurring formula

P_{n}(x) = (x − c_{n})P_{n−1}(x) − λ_{n}P_{n−2}(x), n = 1, 2, 3, …, (10) P_{−1}(x) = 0, P_{0}(x) = 1. (11)

Then there is a unique moment functional L such that

L[1] = λ_{1}, L[P_{m}(x)P_{n}(x)] = 0 for m ≠ n, m, n = 0, 1, 2, ….

L is quasi-definite and (P_{n}(x))_{n=0}^{∞} is the corresponding monic OPS if and only if λ_{n} ≠ 0 for all n ≥ 1, while L is positive-definite if and only if c_{n} is real and λ_{n} > 0 for all n ≥ 1.

More generally, let (P_{n}(x))_{n=0}^{∞} be a sequence of polynomials in ℂ[x] satisfying

P_{n}(x) = (A_{n}x + B_{n})P_{n−1}(x) + D_{n}P_{n−2}(x) (n ≥ 1)
P_{−1}(x) = 0, P_{0}(x) = g ≠ 0,

where A_{n}, B_{n}, D_{n} are complex numbers with A_{n} ≠ 0, D_{n} ≠ 0 for every n ≥ 1. It follows easily by induction on n that P_{n} has degree n and that P_{n} has leading coefficient k_{n} = gA_{1} ⋯ A_{n} for n ≥ 0. Let k_{−1} := 1. For n ≥ −1 write P_{n}(x) = k_{n}P̂_{n}(x). Thus P̂_{n}(x) is monic for n ≥ 0. Further, P̂_{−1}(x) = 0, P̂_{1}(x) = 1 and the sequence (P̂_{n}(x))_{n=0}^{∞} satisfies (8) with c_{n} = −B_{n}k_{n−1}/k_{n} = −B_{n}/A_{n}, λ_{1} arbitrary and λ_{n} = −D_{n}k_{n−2}/k_{n} = −D_{n}/A_{n−1}A_{n} for n ≥ 2. So by Favard’s Theorem, (P̂_{n}(x))_{n=0}^{∞} is a monic OPS and therefore, (P_{n}(x))_{n=0}^{∞} is an OPS for some quasi-definite moment functional L. Moreover, L is positive definite if B_{n}/A_{n} ∈ ℝ and D_{n}/A_{n−1}A_{n} < 0 for n ≥ 2.

We now consider the special case that A_{1} = e/g, B_{1} = f/g, D_{1} = 0 where g ≠ 0 and A_{n} = a, B_{n} = b, D_{n} = d do not depend on n for n ≥ 2, that is, we consider the sequence of polynomials (P_{n}(x))_{n=0}^{∞} with P_{n}(x) ∈ ℂ[x] given by

P_{n+1}(x) = (ax + b)P_{n}(x) + dP_{n−1}(x), n ≥ 1, (12) P_{0}(x) = g, P_{1}(x) = ex + f, (13)

where a, b, d, e, f, g are complex numbers with adeg ≠ 0. By the comments just made this sequence is an OPS for some quasi-definite moment functional L.

In the view of Remark 2 it is clear that Theorem 1 and Theorem 2 cannot hold for all OPS (P_{n}(x))_{n=0}^{∞}, because the Chebyshev polynomials of the first kind are orthogonal with respect to the positive-definite moment functional

L[π(x)] = ∫_{−1}^{1} π(x)(1 − x^{2})^{−1/2}dx.

Using the same methods as above we will prove the following analogues of Theorems 1 and 2.

Theorem 5. Let a, b, d, e, f, g ∈ ℂ with adeg ≠ 0 and let (P_{n}(x))_{n=0}^{∞} be a sequence of polynomials in ℂ[x] defined by (12) and (13). Let S(x) ∈ ℂ[x], deg S ≥ 1. If we assume that e = ag, then there are at most min{exp(18^{10}), C(S)} pairs of integers (n, m) with n, m ≥ 0, n ≠ m such that

P_{n}(x) = P_{m}(S(x))

holds. We have

C(S) = 10^{28} · log(4(deg S + 1)).

Again we can prove the following result concerning the more general equation P_{n}(x) = c P_{m}(S(x)) with some c ∈ ℂ^{∗} variable and again the second part of the last theorem follows from this theorem.

Theorem 6. Let a, b, d, e, f, g ∈ ℂ with adeg ≠ 0 and let (P_{n}(x))_{n=0}^{∞} be defined by (12) and (13). Let S(x) ∈ ℂ[x], deg S ≥ 1 and e = ag. Then the number of pairs of integers (n, m) with n ≠ m for which there exists c ∈ ℂ^{∗} with

P_{n}(x) = c P_{m}(S(x))

is at most C(S). We have

C(S) = 10^{28} · log(4(deg S + 1)).

Remark 7. We want to mention that Theorem 3 and therefore also Theorem 4 can be applied to this situation. The conditions (1) and (3) are trivially satisfied in this case. Condition (4) holds, if Δ(x) = p(x)^{2} + 4q(x) = (ax + b)^{2}+4d and 2P_{1}(x)−P_{0}(x)p(x) = 2(ex+f)−g(ax+b) = (2e−ag)x+2f −bg have no common roots. This means that, if 2e = ag, 2f = bg does not hold or if

x = \frac{bg − 2f}{2e − ag}

is not a root of Δ(x), then we get our assertion for all S(x) ∈ ℂ[x], deg S ≥ 2.

This is satisfied for example if we consider sequences P_{n}(x) ∈ ℂ[x] defined by

P_{n+1}(x) = (ax + b)P_{n}(x) + dP_{n−1}(x), n ≥ 1,
P_{−1}(x) = 0, P_{0}(x) = g ≠ 0,

where a, b, d, g are complex numbers with adg ≠ 0.

4. Auxiliary Results

In this section we collect some important theorems which we will need in our proofs.

Let K be an algebraically closed field of characteristic 0, n ≥ 1 an integer, α_{1}, …, α_{n} elements of K^{∗} and Γ a finitely generated multiplicative subgroup of K^{∗}. A solution (x_{1}, …, x_{n}) of the so called weighted unit equation

α_{1}x_{1} + ⋯ + α_{n}x_{n} = 1 in x_{1}, …, x_{n} ∈ Γ (14) is called non-degenerate if

(15)  ∑_{j∈J} α_{j}x_{j} ≠ 0 for each non-empty subset J of {1, …, n}

and degenerate otherwise. It is clear that if Γ is infinite and if (14) has a degenerate solution then (14) has infinitely many degenerate solutions. For non-degenerate solutions we have the following result, which is due to Evertse, Schlickewei and Schmidt [14].

Theorem 7 (Evertse, Schlickewei and Schmidt). Let K be a field of characteristic 0, let α_{1}, …, α_{n} be non-zero elements of K and let Γ be a multiplicative subgroup of (K^{∗})^{n} of rank r. Then the equation

α_{1}x_{1} + … + α_{n}x_{n} = 1

has at most

exp((6n)^{3n}(r + 1))

non-degenerate solutions (x_{1}, …, x_{n}) ∈ Γ.

This theorem is the Main Theorem on S-unit equations over fields of characteristic 0. It is a generalization and refinement of earlier results due to Evertse and Győry [11], Evertse [9] and van der Poorten and Schlickewei [16] on the finiteness of the number of non-degenerate solutions of (14). For a general survey on these equations and their applications we refer to Evertse, Győry, Stewart and Tijdeman [12].

Next we will consider equation (14) also over function fields. Let F be an algebraic function field in one variable with algebraically closed constant field K of characteristic 0. Thus F is a finite extension of K(t), where t is a transcendental element of F over K. The field F can be endowed with a set M_{F} of additive valuations with value group ℤ for which

K = {0} ∪ {z ∈ F | ν(z) = 0 for each ν in M_{F} }

holds. Let S be a finite subset of M_{F}. An element z of F is called an S-unit if ν(z) = 0 for all ν ∈ M_{F} \S. The S- units form a multiplicative group which is denoted by U_{S}. The group U_{S} contains K^{∗} as a subgroup and U_{S}/K^{∗} is finitely generated. For function fields we have the following result:

Theorem 8 (Evertse and Győry). Let F, K, S be as above. Let g be the genus of F/K, s the cardinality of S, and n ≥ 2 an integer. Then for every α_{1}, …, α_{n} ∈ F^{∗}, the set of solutions of

α_{1}x_{1} + … + α_{n}x_{n} = 1 in x_{1}, …, x_{n} ∈ U_{S} (16)

(17) with α_{1}x_{1}, …, α_{n}x_{n} not all in K

is contained in the union of at most

log(g + 2) · (e(n + 1))^{(n+1)s+2}

(n − 1)-dimensional linear subspaces of F^{n}.

For deriving this upper bound an effective upper bound of Brownawell and Masser [6] for the heights of solutions of (16) is used. For n = 2 the theorem gives the upper bound

log(g + 2)(3e)^{3s+2}

for the number of solution of (16). We note that for the case n = 2 Evertse [10] established an upper bound, which is better and independent of g.

Theorem 9 (Evertse). Let F, K, S be as above. For each pair λ, μ in F^{∗}, the equation

λx + μy = 1 in x, y ∈ U_{S}

has at most 2 · 7^{2s} solutions with λx/μy ∉ K. As above, s denotes the cardinality of S.

Finally, we need some results from the theory of algebraic function fields, which can be found for example in the monograph of Stichtenoth [21]. We will need the following estimates for the genus of a function field F/K (cf. [21], page 130 and 131).

Theorem 10 (Castelnuovo’s Inequality). Let F/K be a function field with constant field K. Suppose there are given two subfields F_{1}/K and F_{2}/K of F/K satisfying

(1) F = F_{1}F_{2} is the compositum of F_{1} and F_{2},

(2) [F : F_{i}] = n_{i}, and F_{i}/K has genus g_{i} (i = 1, 2). Then the genus g of F/K is bounded by

g ≤ n_{1}g_{1} + n_{2}g_{2} + (n_{1} − 1)(n_{2} − 1).

In the special case F_{1} = K(x) and F_{2} = K(y), Castelnuovo’s Inequality yields:

Theorem 11 (Riemann’s Inequality). Let φ be a non-constant irreducible polynomial in two variables with coefficients in K and suppose that F = K(x, y) with φ(x, y) = 0. Then we have the following estimate for the genus g of F/K:

g ≤ ([F : K(x)] − 1) · ([F : K(y)] − 1).

We mention that Riemann’s Inequality (and therefore also Castelnuovo’s Inequality) is often sharp, and that in general it cannot be improved.

Let K be an algebraically closed field of characteristic 0. Let K be a finite extension of K(x) where x is transcendental over K. For ξ ∈ K define the valuation ν_{ξ} such that for Q ∈ K(x) we have Q(x) = (x − ξ)^{ν_{ξ}(Q)}A(x)/B(x) where A, B are polynomials with A(ξ)B(ξ) ≠ 0. Further, for Q = A/B with A, B ∈ K[x] we put deg Q := deg A − deg B; thus ν_{∞} := − deg is a discrete valuation on K(x). Each of the valuations ν_{ξ}, ν_{∞} can be extended in at most [K : K(x)] ways to a discrete valuation on K and in this way one obtains all discrete valuations on K. A valuation on K is called finite if it extends ν_{ξ} for some ξ ∈ K and infinite if it extends ν_{∞}. We choose one of the extensions of ν_{∞} to K and denote this by −ord. Thus ord is a function from K to ℚ having the properties

(a) ord(Q) = deg Q for Q ∈ K[x],
(b) ord(AB) = ord(A) + ord(B) for A, B ∈ K,
(c) ord(A + B) ≤ max{ord(A), ord(B)} for A, B ∈ K,
(d) ord(A + B) = max{ord(A), ord(B)} for A, B ∈ K

with ord(A) ≠ ord(B).

5. Proof of Theorem 1

First we reduce the solvability of (8) to the solvability of three systems of exponential equations in n, m. We start with a sequence of polynomials (P_{n}(x))_{n=0}^{∞} defined by (1). Then, in the sequel α(x), \overline{α}(x), g_{1}(x), g_{2}(x) are always be given by (3).

Lemma 1. Let (G_{n}(x))_{n=0}^{∞} be a sequence of polynomials defined by (1) and let P ∈ K[x], deg P ≥ 1. Assume that g_{1}(x)g_{2}(x) ≠ 0. Then (8) has at most exp(18^{9} · 3) solutions m, n ∈ ℤ, m ≠ n, which do not satisfy any of the systems:

\{ \begin{matrix}g_{1}(x)α(x)^{n} + g_{2}(x)\overline{α}(x)^{n} = 0 \\ g_{1}(P (x))α(P (x))^{m} + g_{2}(P (x))\overline{α}(P (x))^{m} = 0 \end{matrix} (18)

\{ \begin{matrix}g_{1}(x)α(x)^{n} = g_{1}(P (x))α(P (x))^{m} \\ g_{2}(x)\overline{α}(x)^{n} = g_{2}(P (x))\overline{α}(P (x))^{m} \end{matrix} (19)

\{ \begin{matrix}g_{2}(x)\overline{α}(x)^{n} = g_{1}(P (x))α(P (x))^{m} \\ g_{1}(x)α(x)^{n} = g_{2}(P (x))\overline{α}(P (x))^{m} \end{matrix} (20)

Proof. First we define

K = K(x, \sqrt{p(x)^{2} + 4q(x)}, \sqrt{p(P (x))^{2} + 4q(P (x))}).

Clearly, K is finitely generated extension field of ℚ. Furthermore, let Γ be the multiplicative subgroup of (K^{∗})^{3} generated by

(α(x), \overline{α}(x), 1) and (\overline{α}(P (x))^{−1}, \overline{α}(P (x))^{−1}, α(P (x))/\overline{α}(P (x))).

We consider now for n ≠ m the equation G_{n}(x) = G_{m}(P (x)) and obtain

g_{1}(x)α(x)^{n} + g_{2}(x)\overline{α}(x)^{n} − g_{1}(P (x))α(P (x))^{m} − g_{2}(P (x))\overline{α}(P (x))^{m} = 0.

This yields

\frac{g_{1}(x)}{g_{2}(P (x))} \frac{α(x)^{n}}{\overline{α}(P (x))^{m}} + \frac{g_{2}(x)}{g_{2}(P (x))} \frac{\overline{α}(x)^{n}}{\overline{α}(P (x))^{m}} − \frac{g_{1}(P (x))}{g_{2}(P (x))} \frac{α(P (x))^{m}}{\overline{α}(P (x))^{m}} = 1. (21)

Now we consider the weighted unit equation

\frac{g_{1}(x)}{g_{2}(P (x))}x_{1} + \frac{g_{2}(x)}{g_{2}(P (x))}x_{2} − \frac{g_{1}(P (x))}{g_{2}(P (x))}x_{3} = 1 in (x_{1}, x_{2}, x_{3}) ∈ Γ. (22)

According to Theorem 7, equation (22) has at most exp(18^{9} · 3) solutions if no non-trivial subsum vanishes. By observing that g_{1}(x), g_{2}(x) ≠ 0 this means that (21) has at most exp(18^{9} · 3) solutions m, n not satisfying (18),

(19) and (20). □

In the next lemma we calculate the order of α(x) and \overline{α}(x) respectively in the function field K/K, where K is defined as in the previous proof. We will assume that

ord(α) ≥ ord(\overline{α}).

If this is not satisfied we can achieve this by interchanging α(x) and \overline{α}(x). Then we have:

Lemma 2. Let (G_{n}(x))_{n=0}^{∞} be a sequence of polynomials defined by (1) and assume that 2 deg p > deg q ≥ 0. Then

ord(α) = deg p, (23)

(24) ord(\overline{α}) = deg q − deg p < deg p.

Proof. First assume ord(α) = ord(\overline{α}). Then by (a), (c), (b) we have

deg p = ord(α + \overline{α}) ≤ ord(α) = \frac{1}{2} deg q

which is against our assumption. Therefore, ord(α) > ord(\overline{α}). Now it follows from (a), (d) that deg p = ord(α + \overline{α}) = ord(α). Using (a), (b) and α(x)\overline{α}(x) = −q(x) we then obtain

ord(\overline{α}) = deg q − deg p < deg p.

Therefore the proof is finished. □

Next we prove the following lemma.

Lemma 3. Let (G_{n}(x))_{n=0}^{∞} be a sequence of polynomials defined by (1) and let P ∈ K[x], deg P ≥ 1. Assume that neither α(x)/\overline{α}(x), nor α(P (x))/\overline{α}(P (x)) is a root of unity. We consider the systems of equations

\{ \begin{matrix}g_{1}(x)α(x)^{n} + g_{2}(x)\overline{α}(x)^{n} = 0 \\ g_{1}(P (x))α(P (x))^{m} + g_{2}(P (x))\overline{α}(P (x))^{m} = 0 \end{matrix}

The first equation has at most one solution in n, and the second one at most one solution in m.

Proof. This follows from the fact that neither α(x)/\overline{α}(x), nor α(P (x))/\overline{α}(P (x)) are roots of unity. In particular, assume that we have two solutions n_{1}, n_{2}. Then we obtain

−\frac{g_{1}(x)}{g_{2}(x)} = (\frac{\overline{α}(x)}{α(x)})^{n_{1}} = (\frac{\overline{α}(x)}{α(x)})^{n_{2}} ,

which implies that n_{1} = n_{2}. □

Proof of Theorem 1.

First, it is clear that we have

ord(α − \overline{α}) = deg p.

Moreover, the following relations hold

ord(α(P)) = deg p deg P,
ord(\overline{α}(P)) = (deg q − deg p) deg P,
ord(α(P) − \overline{α}(P)) = deg p deg P.

The important relations

g_{1}(x)(α(x) − \overline{α}(x)) = G_{1}(x) − G_{0}(x)\overline{α}(x), (25) g_{2}(x)(\overline{α}(x) − α(x)) = G_{1}(x) − G_{0}(x)α(x) (26)

are consequences of (4). Observe that under the condition 2 deg p > deg q ≥ 0 our sequence (G_{n}(x))_{n=0}^{∞} is nondegenerate. This follows from the fact that α(x)^{n} = \overline{α}(x)^{n} implies ord(α)=ord(\overline{α}), which by Lemma 2 yields a contradiction. The same is true for the quotient α(P (x))/\overline{α}(P (x)).

In order to finish our proof, we want to show that g_{1}(x), g_{2}(x) ≠ 0 and that (19) and (20) have no solutions.

Case 1. deg G_{1} > deg G_{0} + deg p. In this case we have

ord(G_{1} − G_{0}\overline{α}) = deg G_{1},
ord(G_{1} − G_{0}α) = deg G_{1}.

This implies

ord(G_{1}(P) − G_{0}(P)\overline{α}(P)) = deg G_{1} deg P,
ord(G_{1}(P) − G_{0}(P)α(P)) = deg G_{1} deg P.

Therefore we get

ord(g_{1}) = deg G_{1} − deg p,
ord(g_{2}) = deg G_{1} − deg p.

Observe that from this we can conclude that g_{1}(x), g_{2}(x) ≠ 0. Now assume that m, n is a solution of (19). Then we obtain by calculating the order of both sides of the equations and by using Lemma 2

(27) (deg G_{1} − deg p) + n deg p = (deg G_{1} − deg p) deg P + m deg p deg P,

(28) (deg G_{1} − deg p) + n(deg q − deg p) = (deg G_{1} − deg p) deg P + +m(deg q − deg p) deg P.

Subtraction yields

n(2 deg p − deg q) = m(2 deg p − deg q) deg P.

By our assumption 2 deg p > deg q we derive

n = m deg P , (29) and substituting this in (27) implies

(deg G_{1} − deg p) = (deg G_{1} − deg p) deg P.

But this yields deg P = 1, which by (29) gives m = n, or deg G_{1} = deg p, leading to a contradiction.

In the same way we conclude that a solution m, n of (20) implies

(deg G_{1} − deg p) + n deg p = (deg G_{1} − deg p) deg P +
+m(deg q − deg p) deg P,
(deg G_{1} − deg p) + n(deg q − deg p) = (deg G_{1} − deg p) deg P +
+m deg p deg P.

Again subtraction yields

n(2 deg p − deg q) = m(deg q − 2 deg p) deg P ,

and therefore we get n = −m deg P, which contradicts deg P ≠ 0.

Case 2. deg G_{1} < deg G_{0} + deg q − deg p. Here we have

ord(G_{1} − G_{0}\overline{α}) = deg G_{0} + deg q − deg p,
ord(G_{1} − G_{0}α) = deg G_{0} + deg p.

Thus

ord(g_{1}) = deg G_{0} + deg q − 2 deg p,
ord(g_{2}) = deg G_{0}.

¿From this we derive g_{1}(x), g_{2}(x) ≠ 0. Again by Lemma 2, for any solution (n, m) of (19) we must have

(30) (deg G_{0} + deg q − 2 deg p) + n deg p = (deg G_{0} + deg q − −2 deg p) deg P + m deg p deg P,

(31) deg G_{0} + n(deg q − deg p) = deg G_{0} deg P + m(deg q − deg p) deg P.

Subtraction yields

(n − 1)(2 deg p − deg q) = (m − 1) deg P (2 deg p − deg q)

and therefore

(n − 1) = (m − 1) deg P.

By (30) we obtain

(deg G_{0} + deg q − deg p)(1 − deg P) = 0.

This yields deg P = 1, which again implies n = m, or deg G_{0}+deg q−deg p = 0, which gives deg G_{1} < 0, in both cases a contradiction.

Again we get from (20)

(deg G_{0} + deg q − 2 deg p) + n deg p = deg G_{0} deg P +
+m(deg q − deg p) deg P,
deg G_{0} + n(deg q − deg p) = (deg G_{0} + deg q − 2 deg p) deg P +
+m deg p deg P.

Subtraction gives

(n − 1) = −(m − 1) deg P,

which implies deg P = 0, a contradiction.

Now by Lemma 1 we get that (8) has at most

1 + exp(18^{9} · 3) ≤ exp(18^{10})

solutions n, m ∈ ℤ, n, m ≥ 0 with m ≠ n. The second part of our upper bound will follow from the proof of Theorem 2 where a different method of proof is used and thus the proof is finished. □

6. Proof of Theorem 5

Here (P_{n}(x))_{n=0}^{∞} is an OPS and we have in the sense of (12) and (13)

p(x) = ax + b, q(x) = d.

Again we want to apply Lemma 1 to show that the equation

P_{n}(x) = P_{m}(S(x)), (32)

where S(x) ∈ ℂ[x], deg S ≥ 1, has only finitely many solutions m, n ∈ ℤ, m ≠ n. Let α(x), \overline{α}(x), g_{1}(x), g_{2}(x) be given by (3).

As above we may assume without loss of generality that ord(α) ≥ ord(\overline{α}). By observing 2 deg p = 2 > 0 = deg q, we get by Lemma 2 that

ord(α) = 1 and ord(\overline{α}) = −1.

This yields

ord(α − \overline{α}) = 1,
ord(P_{1} − P_{0}\overline{α}) = 1.

We have to calculate ord(P_{1} − P_{0}α). Using that P_{0}(x) = g, P_{1}(x) = ex + f and the assumption that e = ag we get

(P_{1}(x) − P_{0}(x)α(x))(P_{1}(x) − P_{0}(x)\overline{α}(x)) =
= P_{1}(x)^{2} − P_{0}(x)P_{1}(x)p(x) − P_{0}(x)^{2}q(x) =

= (ex + f)^{2} − g(ex + f)(ax + b) − g^{2}d = sx + t

for certain s, t ∈ ℂ. By invoking (a), (b) we then obtain

ord(P_{1} − P_{0}α) =: w ≤ 1 − ord(P_{1} − P_{0}\overline{α}) = 0.

Observe that Lemma 3 can be sharpened in this case. Because of the fact that deg P_{n} = n the number of solutions of (18) is zero. Furthermore it is clear that g_{1}(x), g_{2}(x) cannot be zero in this case, because the following relations hold

ord(g_{1}) = 0,
ord(g_{2}) = w − 1 < 0.

Now assume that m, n ∈ ℤ, m ≠ n is a solution of (19). Then we get

n = m deg S,
(w − 1) − n = [(w − 1) − m] deg S.

Consequently deg S = 1, and therefore m = n, a contradiction.

In the same way we get for a solution of (20), that

(w − 1) − n = m deg S,
n = [(w − 1) − m] deg S.

Adding the two equations gives deg S = 1, and thus n = (w − 1) − m, a contradiction because the left side of the equation is positive and the right side negative.

By Lemma 1 the first part of the theorem follows and the proof is finished as the second part of the bound will follow from Theorem 6. □

7. Proof of Theorem 3

We start our proof with some useful lemmas.

Lemma 4. Let A, B, P ∈ K[x]. If gcd(A, B) = 1 then gcd(A(P), B(P)) = 1.

This lemma is a special case of a lemma in the monograph of Schinzel [18], page 16. It was originally proved in [17].

We will use the same notations as introduced in the proof of Theorem 1. There we calculated the order which was defined as the negative value of some valuation extending 1/x from K(x) to the function field

K = K(x)(\sqrt{Δ(x)}, \sqrt{Δ(P (x))})

of the elements g_{1}(x), g_{2}(x) by using the equations (25) and (26). Here we want to calculate the valuations ν(g_{1}) and ν(g_{2}) where ν extends ν_{ξ} to K for some ξ ∈ K.

Lemma 5. Let (G_{n}(x))_{n=0}^{∞} be a sequence of polynomials defined by (1) and assume that gcd(2G_{1} − G_{0}p, Δ) = 1. If ν is a finite valuation on K with ν(Δ) > 0 then ν(g_{1}\sqrt{Δ}) = ν(g_{2}\sqrt{Δ}) = 0.

Proof. We have equation (25)

g_{1}(x)(α(x) − \overline{α}(x)) = G_{1}(x) − G_{0}(x)\overline{α}(x),

which we may rewrite in the form

2g_{1}(x)\sqrt{Δ(x)} = 2G_{1}(x) − G_{0}(x)p(x) + G_{0}(x)\sqrt{Δ(x)}.

By our assumption that gcd(2G_{1} − G_{0}p, Δ) = 1 we have that

ν(2G_{1} − G_{0}p) = 0.

Because of the fact that

ν(G_{0}\sqrt{Δ}) = ν(G_{0}) + \frac{1}{2}ν(Δ) > 0

we get that

ν(g_{1}\sqrt{Δ}) = ν(2g_{1}\sqrt{Δ}) = min\{ν(2G_{1} − G_{0}p), ν(G_{0}\sqrt{Δ})\} = 0

which was our assertion.

The same holds for g_{2}(x) and therefore the proof is finished. □

Assumption (4) of Theorem 3 together with Lemma 4 imply

gcd(2G_{1}(P) − G_{0}(P)p(P), Δ(P)) = 1.

As

2g_{1}(P (x))\sqrt{Δ(P (x))} =
= 2G_{1}(P (x)) − G_{0}(P (x))p(P (x)) + G_{0}(P (x))\sqrt{Δ(P (x))}

we have again, as in the proof of the previous lemma, that for a finite valuation ν on K with ν(Δ(P)) > 0 we have ν(g_{1}\sqrt{Δ(P)}) = ν(g_{2}\sqrt{Δ(P)}) = 0.

Proof of Theorem 3.

Our intention is to prove that the systems of equations (19) and (20) are not solvable.

Consider for example the equation

g_{1}(x)α(x)^{n} = g_{1}(P (x))α(P (x))^{m}. (33)

The other equations can be handled analogously.

We have deg Δ(P) = deg Δ deg P > deg Δ > 0, as deg P > 1 by assumption (2). Hence Δ(P) has a zero ξ such that

ν_{ξ}(Δ(P)) > ν_{ξ}(Δ) ≥ 0.

This implies that there is a finite valuation ν on K such that

ν(g_{1}(P)) = −ν(Δ(P)).

Next we want to show that ν(α(P)) = 0. Indeed, as ν(Δ(P)) > 0 and

α(P (x)) = \frac{p(P (x)) + \sqrt{Δ(P (x))}}{2}

we have

ν (α(P) − \frac{1}{2}p(P)) > 0. (34)

By assumption (3) of Theorem 3 and Lemma 4 we have gcd(p(P), q(P)) = 1 which implies min{ν(p(P)), ν(q(P))} = 0. If ν(p(P)) > 0 then from

ν(Δ(P)) = ν(p(P)^{2} + 4q(P)) > 0

it follows that then also ν(q(P)) > 0 which is impossible. Therefore, ν(p(P)) = 0. Consequently we have ν(α(P)) = 0. In a similar fashion it follows that ν(\overline{α}(P)) = 0.

Thus equation (33) implies

ν(g_{1}) + nν(α) = ν(g_{1}(P)),

which yields

nν(α) = ν(g_{1}(P)) − ν(g_{1}) < 0,

hence (33) has no solution in n, if ν(α) ≥ 0 and at most one, if ν(α) < 0.

Studying the second equation of (19) we may conclude in the same way that this equation has no solution in n, if ν(\overline{α}) ≥ 0 and at most one if ν(\overline{α}) < 0. Thus the system of equations (19) may have a solution only if ν(α), ν(\overline{α}) < 0. Observe that this is impossible since α(x), \overline{α}(x) are integral over K[x], as they are zeros of the monic equation T^{2} − p(x)T − q(x) = 0 with coefficients in K[x]. The integral closure of K[x] in K consists of those elements f such that ν(f) ≥ 0 for every finite valuation ν of K. So in particular, ν(α) ≥ 0, ν(\overline{α}) ≥ 0. Hence (19) has no solution.

The proof of the unsolvability of (20) is analogous. It is clear that g_{1}(x), g_{2}(x) ≠ 0 holds, because from assumption (1) we can conclude that there is a zero ζ of Δ(x), for which we can derive using Lemma 5 that ν(g_{1}) < 0 and ν(g_{2}) < 0, where ν is a finite valuation extending ν_{ζ} to K. Consequently they must be different from zero. Since Lemma 3 is true also in this case, (because α(x)/\overline{α}(x) and α(P (x))/\overline{α}(P (x)) are not roots of unity), we get the first part of the assertion of Theorem 3 by Lemma 1. The second part of the bound will follow from Theorem 4. □

8. Proof of the Theorems 2, 4 and 6

We keep using the notation introduced before. Especially, let K/K be the algebraic function field in one variable defined by

K = K(x, \sqrt{p(x)^{2} + 4q(x)}, \sqrt{p(P (x))^{2} + 4q(P (x))}).

Now we have the following lemma.

Lemma 6. There exists a finite subset S ⊂ M_{K} of valuations of the function field K such that α(x), \overline{α}(x), α(P (x), \overline{α}(P (x)) ∈ U_{S} and such that

|S| ≤ 4 deg q(deg P + 1) + 4.

Proof. Let S_{∞} be the set of infinite valuations of K and S_{0} the set of finite valuations of K. Note that for every ν ∈ S_{0} we have ν(α) ≥ 0, ν(\overline{α}) ≥ 0, ν(α(P)) ≥ 0, ν(\overline{α}(P)) ≥ 0 since these functions are integral over K[x]. Take S = S_{∞} ∪ S_{1} ∪ S_{2} ∪ S_{3} ∪ S_{4}, where

S_{1} = {ν ∈ S_{0}| ν(α) > 0},
S_{2} = \{ν ∈ S_{0}| ν(\overline{α}) > 0\},
S_{3} = {ν ∈ S_{0}| ν(α(P)) > 0},
S_{4} = \{ν ∈ S_{0}| ν(\overline{α}(P)) > 0\}.

Then clearly α(x), \overline{α}(x), α(P (x), \overline{α}(P (x)) are contained in U_{S}. Since [K : K(x)] ≤ 4, we have |S_{∞}| ≤ 4. Further, α(x) · \overline{α}(x) · α(P (x)) · \overline{α}(P (x)) = q(x) · q(P (x)) =: Q(x). Therefore, S_{1} ∪ S_{2} ∪ S_{3} ∪ S_{4} =: S_{5} := {ν ∈ S_{0} : ν(Q) > 0}. Each of the valuations in S_{5} is an extension to K of some valuation ν_{ξ} on K(x) corresponding to a zero ξ of Q(x). The polynomial Q(x) has at most deg Q = deg q(deg P +1) zeros, and for each of these zeros ξ, the valuation ν_{ξ} can be extended in at most four ways to a valuation on K. Therefore, |S_{5}| ≤ 4 deg q(deg P + 1). This implies Lemma 6. □

Next we want to estimate the genus of the function field K/K. This can be done using Castelnuovo’s Inequality (Theorem 10).

Lemma 7. We denote by g the genus of the function field K/K. Then we have

g ≤ 2 max{2 deg p, deg q}(deg P + 1) − 3.

Proof. First observe that we have

F = K(x, \sqrt{Δ(x)}, \sqrt{Δ(P (x))}) = K(x, \sqrt{Δ(x)}) · K(x, \sqrt{Δ(P (x))}).

Let us denote F_{1} = K(x, \sqrt{Δ(x)}), F_{2} = K(x, \sqrt{Δ(P (x))}). Thus we have

F_{1} = K(x, y), φ_{1}(x, y) = y^{2} − Δ(x) = 0

and

F_{2} = K(x, y), φ_{2}(x, y) = y^{2} − Δ(P (x)) = 0.

Furthermore we denote by g_{i} the genus of F_{i}/K (i = 1, 2). We have

n_{1} = [F : F_{1}] ≤ 2 and n_{2} = [F : F_{2}] ≤ 2.

By Riemann’s Inequality (Theorem 11) we get the following estimates:

g_{1} ≤ ([F_{1} : K(x)] − 1) · ([F_{1} : K(y)] − 1) ≤ deg Δ − 1,
g_{2} ≤ ([F_{2} : K(x)] − 1) · ([F_{2} : K(y)] − 1) ≤ deg Δ deg P − 1.

Since Δ(x) = p(x)^{2} +4q(x) we have deg Δ ≤ max{2 deg p, deg q}. Now using Castelnuovo’s Inequality (Theorem 10) we get

g ≤ 2(deg Δ − 1) + 2(deg Δ deg P − 1) + 1 = 2 deg Δ(deg P + 1) − 3,

and therefore our proof is finished. □

Finally, we need the following lemma.

Lemma 8. Assume 2 deg p > deg q ≥ 0 or gcd(p, q) = 1 and p, q not both in K. Let γ_{1}, γ_{2} be non-zero elements of K. Then there is at most one pair of integers n, m such that

γ_{1} \frac{α(x)^{n}}{\overline{α}(P (x))^{m}} ∈ K^{∗} and γ_{2} \frac{\overline{α}(x)^{n}}{\overline{α}(P (x))^{m}} ∈ K^{∗} (35)

or

γ_{1} \frac{α(x)^{n}}{\overline{α}(P (x))^{m}} ∈ K^{∗} and γ_{2} \frac{α(P (x))^{m}}{\overline{α}(P (x))^{m}} ∈ K^{∗} (36)

or

γ_{1} \frac{\overline{α}(x)^{n}}{\overline{α}(P (x))^{m}} ∈ K^{∗} and γ_{2} \frac{α(P (x))^{m}}{\overline{α}(P (x))^{m}} ∈ K^{∗}, (37)

respectively.

Proof. First we prove equation (35). Suppose there are two such pairs (n_{1}, m_{1}), (n_{2}, m_{2}). Let n = n_{1} − n_{2}, m = m_{1} − m_{2}. Then (γ_{1}/γ_{2})(α(x)/\overline{α}(x))^{n_{i}} ∈ K^{∗} for i = 1, 2, hence (α(x)/\overline{α}(x))^{n} ∈ K^{∗}. Suppose n ≠ 0. Then α(x)/\overline{α}(x) ∈ K^{∗}. Using p(x) = α(x) + \overline{α}(x), q(x) = α(x) · \overline{α}(x) it follows that p(x) = c_{1}α(x), q(x) = c_{2}α(x)^{2} with c_{1}, c_{2} ∈ K^{∗} and so p(x)^{2} = c_{3}q(x) with c_{3} ∈ K^{∗}. But this contradicts both 2 deg p > deg q ≥ 0 and gcd(p, q) = 1. It follows that n = 0, whence n_{1} = n_{2} and so (n_{1}, m_{1}) = (n_{2}, m_{2}). This proves the first part of the lemma.

Now we consider equation (36). As above we assume that there are two such pairs. Hence we get (α(P (x))/\overline{α}(P (x)))^{m} ∈ K^{∗}. This implies that either α(P (x))/\overline{α}(P (x)) ∈ K^{∗} which is impossible by the same arguments as above or m = 0. But now, using the other expression in (36) we get that also n = 0 must hold. Consequently we have (n_{1}, m_{1}) = (n_{2}, m_{2}). Thus we proved the second part of our lemma.

The arguments for (37) are the same as for (36). This proves the lemma also in the third case. □

Assume that n, m are integers satisfying G_{n}(x) = c G_{m}(P (x)) for some c ∈ K^{∗}. It follows that

β_{1}x_{1} + β_{2}x_{2} + β_{3}x_{3} = 1

where

β_{1} := \frac{g_{1}(x)}{g_{2}(P (x))}, β_{2} := \frac{g_{2}(x)}{g_{2}(P (x))}, β_{3} := −\frac{g_{1}(P (x))}{g_{2}(P (x))}, (38)

x_{1} = c^{−1} \frac{α(x)^{n}}{\overline{α}(P (x))^{m}} , x_{2} = c^{−1} \frac{\overline{α}(x)^{n}}{\overline{α}(P (x))^{m}} , x_{3} = \frac{α(P (x))^{m}}{\overline{α}(P (x))^{m}} .

¿From the choice of S in Lemma 6 and from the fact that c ∈ K^{∗}, K^{∗} ⊂ U_{S}, it follows that x_{1}, x_{2}, x_{3} ∈ U_{S}. Lemma 8 implies that any given pair of elements (x_{i}, x_{j}) gives rise to at most one pair (n, m), especially any triple (x_{1}, x_{2}, x_{3}) induces at most one solution (n, m) of the equation in consideration.

By Theorem 8, either β_{1}x_{1}, β_{2}x_{2}, β_{3}x_{3} all belong to K^{∗}, which by Lemma 8 is possible for at most one pair (n, m), or (x_{1}, x_{2}, x_{3}) lies in one of at most log(g + 2) · (4e)^{4s+2} proper linear subspaces of K^{3}, where s denotes the cardinality of the set of valuations S introduced by Lemma 6. That is, (x_{1}, x_{2}, x_{3}) satisfies one of at most log(g + 2)(4e)^{4s+2} relations of the shape

γ_{1}x_{1} + γ_{2}x_{2} + γ_{3}x_{3} = 0 (39)

with (γ_{1}, γ_{2}, γ_{3}) a non-zero triple in K^{3}. Assume for the moment that γ_{i} ≠ 0 for i = 1, 2, 3 and write Δ_{ij} = γ_{j}^{−1}(β_{i}γ_{j} −β_{j}γ_{i}). Assume for the moment also that all Δ_{ij} are non-zero. Then we have

Δ_{13}x_{1} + Δ_{23}x_{2} = 1, Δ_{12}x_{1} + Δ_{32}x_{3} = 1, Δ_{21}x_{2} + Δ_{31}x_{3} = 1.

In fact it suffices to consider one of these equations for example the first one

Δ_{13}x_{1} + Δ_{23}x_{2} = 1.

Lemma 8 implies that there is at most one pair (n, m) such that both quantities Δ_{13}x_{1} and Δ_{23}x_{2} belong to K. Theorem 9 implies that there are at most 2 · 7^{2s} pairs (x_{1}, x_{2}) such that at least one of these quantities does not belong to K. It follows that there are at most 1 + 2 · 7^{2s} pairs (n, m) for which γ_{1}x_{1} + γ_{2}x_{2} + γ_{3}x_{3} = 0.

Next, we handle the case that one of the Δ_{ij}, where (i, j) = (1, 3) or (2, 3), is zero. We assume that all γ_{i} ≠ 0 for i = 1, 2, 3. It is clear that Δ_{ij} = 0 implies also Δ_{ji} = 0. Moreover, we remark that if Δ_{ij} = 0 then neither Δ_{ik} = 0 nor Δ_{jk} = 0 where {i, j, k} = {1, 2, 3} can hold. Because assume that Δ_{ij} = 0 and Δ_{ik} = 0. This implies that also Δ_{jk} = 0 which means that all the quantities Δ_{13}, …, Δ_{31} are zero. Hence we would get

β_{1}x_{1} + β_{2}x_{2} + β_{3}x_{3} = (γ_{1}x_{1} + γ_{2}x_{2} + γ_{3}x_{3}) (\frac{β_{3}}{γ_{3}} ) = 1,

which is a contradiction to equation (39). ¿From this discussion it follows that Δ_{ij} = 0 for (i, j) = (1, 3) or (2, 3) implies that we have

Δ_{ik}x_{i} + Δ_{jk}x_{j} = 1,

with non-zero Δ_{ik}, Δ_{jk} and {i, j, k} = {1, 2, 3}. As above, Theorem 9 implies that there are at most 2 · 7^{2s} pairs (x_{i}, x_{j}) such that at least one of these quantities does not belong to K which can happen for at most one pair (n, m) by Lemma 8.

Finally, we handle the case that γ_{i} = 0 for some i = 1, 2, 3. Observe that at most one of the γ_{i} can be zero. Now we assume that γ_{1} = 0. Then (39) becomes

γ_{2}x_{2} + γ_{3}x_{3} = 0.

Therefore we have

β_{1}x_{1} + (β_{3} − \frac{γ_{3}}{γ_{2}} β_{2}) x_{3} = 1.

This implies, under the condition β_{3} − (γ_{3}/γ_{2})β_{2} ≠ 0, that there are at most 1 + 2 · 7^{2s} pairs of solutions (n, m). If this condition is not satisfied then we have

β_{1}x_{1} = 1 and β_{2}x_{2} + β_{3}x_{3} = 0

which means that (38) has a vanishing subsum. The cases γ_{2} = 0 and γ_{3} = 0 are totally analogous. We get in both cases that there are at most 1 + 2 · 7^{2s} pairs of solutions (n, m), if we assume that (38) has no vanishing subsum.

The cases for vanishing subsums of equation (38) can be rewritten in the following form:

\{ \begin{matrix}g_{1}(x)α(x)^{n} = c g_{2}(P (x))\overline{α}(P (x))^{m} \\ g_{2}(x)\overline{α}(x)^{n} = c g_{1}(P (x))α(P (x))^{m} \end{matrix}
\{ \begin{matrix}g_{2}(x)\overline{α}(x)^{n} = c g_{2}(P (x))\overline{α}(P (x))^{m} \\ g_{1}(x)α(x)^{n} = c g_{1}(P (x))α(P (x))^{m} \end{matrix}
\{ \begin{matrix}g_{1}(x)α(x)^{n} + g_{2}(x)\overline{α}(x)^{n} = 0 \\ g_{1}(P (x))α(P (x))^{m} + g_{2}(P (x))\overline{α}(P (x))^{m} = 0 \end{matrix}

But the first two systems of equations are, up to the constant c, the same as (20), (19), respectively, while the third system is (18). In the proof of Theorems 1, 3 and 5 we showed that (20), (19) are unsolvable by calculating the values of certain infinite or finite valuations. Since for any of these valuations ν we have ν(c) = 0, the same argument applies to the first two systems above and we conclude that these systems are unsolvable. Further it has been proved that (18) has at most one solution (n, m), therefore the third system above has at most one solution (n, m).

Altogether, we get for the number of pairs (n, m) of integers with n ≠ m satisfying G_{n}(x) = c G_{m}(P (x)) for some c ∈ K^{∗} the upper bound

1 + log(g + 2)(4e)^{4s+2} · [7 + 12 · 7^{2s}] ≤ log(g + 2)(4e)^{4s+2}7^{2s+2}.

Now using the estimation for the genus of our function field (Lemma 7) and the estimate for the cardinality of the set S (Lemma 6) we get that the number of solutions can be bounded by

C(p, q, P) = C̃(p, q, P) = log(2 max{2 deg p, deg q}(deg P + 1)) ·
·(4e)^{16 deg q(deg P +1)+18}7^{8 deg q(deg P +1)+10}.

Last observe that in Theorem 2 we have assumed that 2 deg p > deg q and in Theorem 6 we have

p(x) = ax + b and q(x) = d,

i.e., deg q = 0 and deg p = 1. This proves the bounds as claimed. □

9. Acknowledgment

The authors are most grateful to an anonymous referee for various suggestions improving an earlier draft of the paper. Especially, the observation that we can handle the more general equation G_{n}(x) = c G_{m}(P (x)) (c variable) with our method was suggested by him.

References

[1] A. Baker, New advances in transcendence theory, Cambridge Univ. Press, Cambridge, 1988.

[2] F. Beukers and H. P. Schlickewei, The equations x + y = 1 in finitely generated groups, Acta Arith. 78 (1996), 189-199.

[3] F. Beukers and R. Tijdeman, On the multiplicities of binary complex recurrences, Compos. Math. 51 (1984), 193-213.

[4] Y. Bilu and R. F. Tichy, The diophantine equation f(x) = g(y), Acta Arith. 95 (2000), no. 3, 261-288.

[5] P. Borwein and T. Erdélyi, Polynomials and Polynomial Inequalities, Springer Verlag, Berlin, 1995.

[6] W. D. Brownawell and D. W. Masser, Vanishing sums in function fields, Proc. Cambridge Philos. Soc. 100 (1986), 427-434.

[7] T. S. Chihara, An Introduction to Orthogonal Polynomials, Gordon and Breach Science Publishers, New York - London - Paris, 1978.

[8] A. Dujella and R.F. Tichy, Diophantine equations for second order recursive sequences of polynomials, Quarterly Journal of Mathematics (Oxford) 52 (2001), no. 2, 161-169.

[9] J.H. Evertse, On sums of S-units and linear recurrences, Comp. Math. 53 (1984), 225-244.

[10] J.H. Evertse, On equations in two S-units over function fields of characteristic 0, Acta Arith. 47 (1986), 233 -253.

[11] J.H. Evertse and K. Győry, On the number of solutions of weighted unit equations, Compositio Math. 66 (1988), 329-354.

[12] J.H. Evertse, K. Győry, C. L. Stewart and R. Tijdeman, S-unit equations and their applications. In: New advances in transcendence theory (ed. by A. Baker), 110-174, Cambridge Univ. Press, Cambridge, 1988.

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

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

[15] J. P. Glass, J. H. Loxton and A. J. van der Poorten, Identifying a rational function, C. R. Math. Rep. Acad. Sci. Canada 3 (1981), 279-284. Corr. 4 (1982), 309-314.

[16] J. van der Poorten and H. P. Schlickewei, The growth conditions for recurrence sequences, Macquarie Univ. Math. Rep. 82-0041, North Ryde, Australia, 1982.

[17] A. Schinzel, Reducibility of polynomials in several variables, Bull. Acad. Polon. Sci., Ser. Sci. Math. 11 (1963), 633-638.

[18] A. Schinzel, Polynomials with special regard to reducibility, Cambridge University Press, Cambridge - New York, 2000.

[19] H. P. Schlickewei, The multiplicity of binary recurrences, Invent. Math. 129 (1997), 11-36.

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

[21] H. Stichtenoth, Algebraic Function Fields and Codes, Springer Verlag, Berlin, 1993.

[22] G. Szegő, Orthogonal Polynomials, American Mathematical Society Colloquium Publications Vol. 23, Providence, Rhode Island, 1939.

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

Attila Pethő Institute for Mathematics and Informatics University of Debrecen Debrecen Pf. 12 H-4010 Debrecen, Hungary e-mail: pethoe@math.klte.hu

Robert F. Tichy Institut für Mathematik TU Graz Steyrergasse 30 A-8010 Graz, Austria e-mail: tichy@tugraz.at