ON THE DIOPHANTINE EQUATION G_{n}(x) = G_{m}(P (x)): HIGHER ORDER RECURRENCES

CLEMENS FUCHS, ATTILA PETHŐ, AND ROBERT F. TICHY

Abstract. Let K be a field of characteristic 0 and let (G_{n}(x))_{n=0}^{∞} be a linear recurring sequence of degree d in K[x] defined by the initial terms G_{0}, …, G_{d−1} ∈ K[x] and by the difference equation

G_{n+d}(x) = A_{d−1}(x)G_{n+d−1}(x) + … + A_{0}(x)G_{n}(x), for n ≥ 0,

with A_{0}, …, A_{d−1} ∈ K[x]. Let finally P (x) be an element of K[x]. In this paper we are giving fairly general conditions depending only on G_{0}, …, G_{d−1}, on P, and on A_{0}, …, A_{d−1} under which the Diophantine equation

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

has only finitely many solutions (n, m) ∈ ℤ^{2}, n, m ≥ 0. Moreover, we are giving an upper bound for the number of solutions, which depends only on d. This paper is a continuation of the work of the authors on this equation in the case of second order linear recurring sequences (cf. [12]).

1. Introduction

Let K denote a field of characteristic 0. Without loss of generality we may assume that this field is algebraically closed. Let A_{0}, …, A_{d−1}, G_{0}, …, G_{d−1} ∈ K[x] and let the sequence of polynomials (G_{n}(x))_{n=0}^{∞} be defined by the d-th order linear recurring sequence

(1.1)  G_{n+d}(x) = A_{d−1}(x)G_{n+d−1}(x) + … + A_{0}(x)G_{n}(x), for n ≥ 0.

Let

Q(T) = T^{d} − A_{d−1}(x)T^{d−1} − … − A_{0}(x) ∈ K[x][T]

denote the characteristic polynomial of the sequence (G_{n}(x))_{n=0}^{∞} and D(x) be the discriminant of Q(T). It is clear that D(x) ∈ K[x]. Moreover, let α_{1}(x), …, α_{d}(x) denote the roots of the characteristic polynomial Q(T) in the splitting field K(x) of Q(T). The field K(x) is a finite extension of K(x) of degree at most d!.

Assuming that Q(T) has no multiple roots, i.e. D(x) ≠ 0, it is well known that (G_{n}(x))_{n=0}^{∞} has a nice “analytic” representation. More precisely, there exist elements g_{1}(x), …, g_{d}(x) ∈ K(x) such that

(1.2)  G_{n}(x) = g_{1}(x)α_{1}(x)^{n} + … + g_{d}(x)α_{d}(x)^{n},

holds for all n ≥ 0.

Date: September 10, 2002. 2000 Mathematics Subject Classification. Primary 11D45; Secondary 11D04, 11D61, 11B37. Key words and phrases. Diophantine equations, linear recurring sequences, S-unit equations. 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. 29330 and 38225.

(G_{n}(x))_{n=0}^{∞} is called nondegenerate, if no quotient α_{i}(x)/α_{j}(x), 1 ≤ i < j ≤ d is equal to a root of unity and it is called degenerate otherwise.

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

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

where s(x) ∈ K[x] is given. We denote by N(s(x)) the number of integers n for which (1.3) holds. From the Theorem of Skolem-Mahler-Lech [13] it follows that N(s(x)) is finite for every s(x) provided that the sequence is nondegenerate and that also α_{1}(x), …, α_{d}(x) are not equal to a root of unity. Evertse, Schlickewei and Schmidt [9] proved that

(1.4)  N(s(x)) ≤ e^{(6d)^{3d}}

under the same conditions as before. This is a direct consequence of the Main Theorem on S-unit equations over fields of characteristic 0 which we will state later on.

We mention that for d = 2, Schlickewei [17] had previously established an absolute bound for N(s(x)). His bound was substantially improved by Beukers and Schlickewei [3] who showed that N(s(x)) ≤ 61. Very recently, Schmidt [18] obtained the remarkable result that for arbitrary nondegenerate complex recurrence sequences of order d one has N(a) ≤ C(d), where a ∈ ℂ and C(d) depends only (and in fact triply exponentially) on d.

Recently, the authors used new developments on S-unit equations over fields of characteristic 0 due to Evertse, Schlickewei and Schmidt (cf. [9]) to handle the equation G_{n}(x) = G_{m}(P (x)) for second order linear recurring sequences (G_{n}(x))_{n=0}^{∞}. Our result was: Let p, q, G_{0}, G_{1}, P ∈ K[x], deg P ≥ 1 and (G_{n}(x))_{n=0}^{∞} be defined by the second order linear recurrence

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

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 e^{10^{18}} pairs of integers (n, m) with n, m ≥ 0, n ≠ m such that

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

holds. We showed a second result in our paper: Let Δ(x) = p(x)^{2} + 4q(x). 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 e^{10^{18}} pairs of integers (n, m) with n, m ≥ 0 such that

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

holds.

THE EQUATION G_{n}(x) = G_{m}(P (x)): HIGHER ORDER RECURRENCES 3

The motivation for this equation was the following observation which shows that the problem is non-trivial: 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).

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

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

This example shows that some further conditions are needed.

By using function field analogs of S-unit equations, we were also able to give an upper bound for the cardinality of the set

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

(Here c may vary with n, m). Under the same assumptions as above we showed: 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) = 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).

The first author gave suitable extensions of the above results for third order linear recurring sequences (cf. [10, 11]). He proved: Let a, b, c, G_{0}, G_{1}, G_{2}, P ∈ K[x], deg P ≥ 1 and (G_{n}(x))_{n=0}^{∞} be defined by the third order linear recurring sequence

(1.5)  G_{n+3}(x) = a(x)G_{n+2}(x) + b(x)G_{n+1}(x) + c(x)G_{n}(x), for n ≥ 0.

Assume that the following conditions are satisfied: 3 deg a > deg c ≥ 0, 2 deg a > deg b and deg a + deg c > 2 deg b. Moreover, assume

deg G_{2} > deg G_{1} + deg a ≥ 0, and
deg G_{1} > deg G_{0} + \frac{1}{2}(deg c − deg a).

Then there are at most e^{10^{24}} pairs of integers (n, m) with n, m ≥ 0, n ≠ m such that

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

holds.

Moreover, we have: Let a, b, c, G_{0}, G_{1}, G_{2}, P ∈ K[x] and (G_{n}(x))_{n=0}^{∞} be defined by (1.5). Assume that

(1) deg D ≠ 0, deg q ≠ 0

(2) deg P ≥ 2,
(3) gcd(c, D) = 1, gcd(p, q) = 1,
(4) gcd(G_{2} − \frac{2}{3}aG_{1} − \frac{2}{9}a^{2}G_{0} − bG_{0}, q) = 1,
gcd(G_{2}^{2} − \frac{4}{3}bG_{2}G_{0} − \frac{1}{3}bG_{1}^{2} + \frac{4}{9}b^{2}G_{0}^{2}, D) = 1 and
(5) gcd(a, 27c^{2} − 4b^{3}) > 1,

where p, q are the coefficients of the characteristic polynomial of (1.5) in reduced form and D is the discriminant. Then there are at most e^{10^{24}} pairs of integers (n, m) with n, m ≥ 0 such that

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

holds.

It is the aim of this paper to present extensions of the results for linear recurrences of arbitrary order.

2. General Results

To establish our first main result we need some preparations. By considering the initial terms of the recurrence we obtain the system of linear equations

(2.1)  G_{j}(x) = g_{1}(x)α_{1}(x)^{j} + ⋯ + g_{d}(x)α_{d}(x)^{j}, j = 0, …, d − 1

for the algebraic functions g_{1}(x), …, g_{d}(x). Let Δ(x) denote the determinant of this system. Then Δ(x) = ∏_{1≤i<j≤d}(α_{j}(x) − α_{i}(x)), hence D(x) = Δ(x)^{2}.

Define A⃗ = (A_{0}, …, A_{d−1}), G⃗ = (G_{0}, …, G_{d−1}) and α⃗_{j} = (1, α_{j}, …, α_{j}^{d−1})^{T} , j = 1, …, d. Applying Cramer’s rule for the system of equations (2.1) we obtain

Δ(x)g_{1}(x) = det(G⃗^{T} (x), α⃗_{2}(x), …, α⃗_{d}(x)).

It is easy to see by induction that

det(G⃗^{T} , α⃗_{2}, …, α⃗_{d}) = (∑_{i=0}^{d−1}(−1)^{d−1−i}G_{d−1−i}S_{i}(α_{2}, …, α_{d})) ∏_{2≤i<j≤d}(α_{j} − α_{i}),

where S_{i}(α_{2}, …, α_{d}), i = 0, …, d − 1 denotes the i-th elementary symmetrical polynomial. Using Vieta’s formulae we obtain

(2.2)  g_{1}(x)α_{1}(x) ∏_{i=2}^{d}(α_{i}(x) − α_{1}(x)) = ∑_{i=0}^{d−1} L_{i}(A⃗, G⃗)α_{1}^{i}(x),

with some polynomial L_{i}(A⃗, G⃗) ∈ ℚ[A⃗, G⃗], i = 0, …, d − 1. As (2.1) is symmetrical in α_{1}(x), …, α_{d}(x) the same relation holds if we replace the index 1 with another index 1 ≤ j ≤ d.

Let now

R = R_{d}(A⃗, G⃗) = ∏_{j=1}^{d} (∑_{i=0}^{d−1} L_{i}(A⃗, G⃗)α_{j}^{i}) .

By the theorem on symmetrical polynomials R(A⃗, G⃗) ∈ ℚ[A⃗, G⃗]. To have some impression how complicated R is we computed it for d = 3:

R_{3}(A⃗, G⃗) = −G_{2}^{3} + (−A_{1}G_{0} + 2A_{2}G_{1})G_{2}^{2} +
((A_{1} − A_{2}^{2})G_{1}^{2} + (−3A_{0} + A_{1}A_{2})G_{0}G_{1} − A_{0}G_{0}^{2}A_{2})G_{2}
+(−A_{0} − A_{1}A_{2})G_{1}^{3} + (A_{0}A_{2} + A_{1}^{2})G_{0}G_{1}^{2} − 2A_{0}G_{1}A_{1}G_{0}^{2} +
+A_{0}^{2}G_{0}^{3}.

Now we are in the position to state our first main result, which is a suitable analog of the theorems in [12] for the number of solutions of

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

where c ∈ K^{∗} = K\{0} is variable, for linear recurring sequence (G_{n}(x))_{n=0}^{∞} of arbitrary large order.

Theorem 2.1. Assume that the d-th order (d ≥ 2) linear recurring sequence (G_{n}(x))_{n=0}^{∞} and the polynomial P ∈ K[x] satisfy the following conditions:

(i) None of the roots and the quotients of distinct roots of the characteristic polynomial of (G_{n}(x))_{n=0}^{∞} is an element of K^{∗},

(ii) deg P ≥ 2 and deg D ≥ 1, (iii) gcd(D, A_{0}) = 1 and (iv) gcd(D, R(A⃗, G⃗)) = 1.

Then equation (2.3) has at most

C(d, A_{0}, D, P) := e^{(6d)^{4d}} (log (d^{2d^{2}} deg D(deg P + 1)))^{2d^{2}} (2ed)^{30d^{3}d!^{2} deg A_{0} deg P}

solutions (n, m) ∈ ℤ^{2} with n, m ≥ 0, n ≠ m.

Remark 2.2. Observe that the conditions in Theorem 2.1 are suitable generalizations of the conditions of Theorem 3 in [12]. Moreover, observe that the structure of the bound is similar to that in [12], especially the dependence on deg D and deg P.

It is also possible to get the conclusions from above for other kind of assumptions.

Theorem 2.3. Assume that the d-th order (d ≥ 2) linear recurring sequence (G_{n}(x))_{n=0}^{∞} and the polynomial P ∈ K[x] satisfy the following conditions:

(i) None of the roots and the quotients of distinct roots of the characteristic polynomial of (G_{n}(x))_{n=0}^{∞} is an element of K^{∗},

(ii) deg P ≥ 1, and deg D ≥ 1, (iii) deg A_{0} ≥ 1, R(A⃗, G⃗) ≠ 0, and (iv) the set of zeroes of A_{0} is not equal to that of A_{0}(P).

Then equation (2.3) has at most C(d, A_{0}, D, P) solutions (n, m) ∈ ℤ^{2} with n, m ≥ 0, n ≠ m.

The following proposition characterizes those polynomials A_{0}, P for which condition (iv) of the last theorem does not hold.

Proposition 2.4. Let A_{0} and P be non-constant elements in K[x]. Assume that A_{0} and A_{0}(P) have the same roots and let k be the number of different roots of A_{0}. Then there exist a, b, c ∈ K, a, c ≠ 0 such that: if k = 1 then

A_{0}(x) = a(x − b)^{deg A_{0}} and P (x) = c(x − b)^{deg P} + b;

if k ≥ 2 then either P (x) = x or P (x) = ax + b, a ≠ 1 and in this case

A_{0}(x) = c (x + \frac{b}{a − 1})^{s} ∏_{i=1}^{r} ∏_{j=0}^{ℓ−1} (x − a^{j}x_{i} − b\frac{a^{j} − 1}{a − 1}) ,

where x_{1}, … x_{r} ∈ K are all different and a is a root of unity of order ℓ.

For the special case of the equation

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

we can even show more.

Theorem 2.5. Assume that the d-th order (d ≥ 2) linear recurring sequence (G_{n}(x))_{n=0}^{∞} and the polynomial P ∈ K[x] satisfy the following conditions:

(i) None of the roots and the quotients of distinct roots of the characteristic polynomial of (G_{n}(x))_{n=0}^{∞} is a root of unity,

(ii) deg P ≥ 2 and deg D ≥ 1, (iii) gcd(D, A_{0}) = 1 and (iv) gcd(D, R(A⃗, G⃗)) = 1.

Then equation (2.4) has at most

e^{(12d)^{6d}},

solutions (n, m) ∈ ℤ^{2} with n, m ≥ 0, n ≠ m.

Remark 2.6. Observe that we can prove an upper bound for the number of solutions of (2.4) which does only depend on d.

Moreover, as an analog of Theorem 2.3, we get:

Theorem 2.7. Assume that the d-th order (d ≥ 2) linear recurring sequence (G_{n}(x))_{n=0}^{∞} and the polynomial P ∈ K[x] satisfy the following conditions:

(i) None of the roots and the quotients of distinct roots of the characteristic polynomial of (G_{n}(x))_{n=0}^{∞} is a root of unity,

(ii) deg P ≥ 1, and deg D ≥ 1, (iii) deg A_{0} ≥ 1, R(A⃗, G⃗) ≠ 0, and (iv) the set of zeroes of A_{0} is not equal to that of A_{0}(P).

Then equation (2.4) has at most

e^{(12d)^{6d}},

solutions (n, m) ∈ ℤ^{2} with n, m ≥ 0, n ≠ m.

Finally, we want to study a special instance of the above problem. Let (G_{n}(x))_{n=0}^{∞} be defined by (1.1) and let the initial polynomials be given by

G_{0}(x) = … = G_{d−2}(x) = 0, and G_{d−1}(x) = 1.

Then we have

G_{n}(x) = ∑_{i=1}^{d} \frac{α_{i}^{n}(x)}{Q′(α_{i}(x))},

where

Q(T) = T^{d} − A_{d−1}(x)T^{d−1} − … − A_{0}(x)

denotes the characteristic polynomial and ′ means differentiation with respect to T. Observe that the discriminant D(x) in this case is given by

D(x) = ∏_{i=1}^{d} Q′(α_{i}(x)) = ∏_{j=1}^{d} ∏_{{i=1 \atop i≠j}}^{d}(α_{i}(x) − α_{j}(x)).

Applying Theorem 2.1 we get the following consequence:

Corollary 2.8. Let (G_{n}(x))_{n=0}^{∞} be defined as above. Assume that (G_{n}(x))_{n=0}^{∞} and the polynomial P ∈ K[x] satisfy the following conditions:

(i) None of the roots and the quotients of distinct roots of the characteristic polynomial of (G_{n}(x))_{n=0}^{∞} is an element of K^{∗},

(ii) deg P ≥ 2 and deg D ≥ 1, and

(iii) gcd(D, A_{0}) = 1. Then we have:

(1) Equation (2.3) has at most

C(d, A_{0}, D, P) =

= e^{(6d)^{4d}} (log (d^{2d^{2}} deg D(deg P + 1)))^{2d^{2}} (2ed)^{30d^{3}d!^{2} deg A_{0} deg P}

solutions (n, m) ∈ ℤ^{2} with n, m ≥ 0, n ≠ m,

(2) Equation (2.4) has at most

min{e^{(12d)^{6d}}, C(d, A_{0}, D, P)}

solutions (n, m) ∈ ℤ^{2} with n, m ≥ 0, n ≠ m.

Observe that also Theorems 2.3 and 2.7 can be applied to this situation (but without any simplification of the assumption in general).

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

(3.1)  α_{1}x_{1} + ⋯ + α_{n}x_{n} = 1 in x_{1}, …, x_{n} ∈ Γ

is called non-degenerate if

(3.2)  ∑_{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 (3.1) has a degenerate solution then (3.1) has infinitely many degenerate solutions. For non-degenerate solutions we have the following result, which is due to Evertse, Schlickewei and Schmidt [9].

Theorem 3.1 (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

e^{(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 [6], Evertse [4] and van der Poorten and Schlickewei [14] on the finiteness of the number of non-degenerate solutions of (3.1). For a general survey on these equations and their applications we refer to Evertse, Győry, Stewart and Tijdeman

For the convenience of the reader, we state once more the consequence for the multiplicity of linear recurring sequences (see introduction, cf. [9]).

Theorem 3.2 (Evertse, Schlickewei and Schmidt). Let (u_{m})_{m∈ℤ} be a recurring sequence satisfying

u_{m} = g_{1}α_{1}^{m} + … + g_{n}α_{n}^{m} for m ∈ ℤ,

where α_{1}, …, α_{n} ∈ K^{∗} are distinct such that neither α_{1}, …, α_{n}, nor any of the quotients α_{i}/α_{j} (1, ≤ i < j ≤ n) is a root of unity and where g_{1}, …, g_{n} are nonzero elements of K. Then for every a ∈ K we have

N(a) ≤ e^{(6n)^{3n}}.

Next we will consider equation (3.1) 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 3.3 (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} (3.3) (3.4) 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 [2] for the heights of solutions of (3.3) is used. For n = 2 the theorem gives the upper bound

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

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

Theorem 3.4 (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.

We will use the results from above to prove the following proposition:

Proposition 3.5. Let F, K, S be as above. Let g be the genus of F/K, s the cardinality of S, n ≥ 2 an integer, and α_{1}, …, α_{n} ∈ F^{∗}. Moreover, let Γ_{i} ⊂ U_{S}, i = 1, …, n and U := Γ_{1} × … × Γ_{n}. We assume that any given pair (x_{i}, x_{j}) ∈ Γ_{i} × Γ_{j} with 1 ≤ i < j ≤ n gives rise to at most k solutions (x_{1}, …, x_{n}) of

α_{1}x_{1} + … + α_{n}x_{n} = 1 in (x_{1}, …, x_{n}) ∈ U, (3.5)

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

and that for arbitrary γ_{1}, γ_{2} ∈ F^{∗} there are at most k solutions (x_{1}, …, x_{n}) ∈ U such that there exist indices i ≠ j with γ_{1}x_{i}, γ_{2}x_{j} ∈ K^{∗}. Then the number of solutions of (3.5) with (3.6) can by bounded by

A(n, k) = k^{n}e^{n^{2}} (log(g + 2))^{n−2} (e(n + 1))^{(n−1)(n+1)(s+1)}.

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

Theorem 3.6 (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).

We mention that Castelnuovo’s Inequality is often sharp, and that in general it cannot be improved.

Moreover, we will use the Hurwitz Genus Formula (cf. [19], page 88).

Theorem 3.7 (Hurwitz Genus Formula). Let F/K be an algebraic function field of genus g and F′/F be a finite separable extension. Let K′ denote the constant field of F′ and g′ the genus of F′/K. Then we have

2g′ − 2 = \frac{[F′ : F]}{[K′ : K]}(2g − 2) + deg Diff(F′/F).

The Hurwitz Genus Formula is a powerful tool that allows determination of the genus of F/K in terms of the different of F/K(x) as any function field can be regarded as a finite extension of a rational function field.

Last we mention some basic fact about the valuation theory in function fields: 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 ν_{∞}. Let us mention that the valuations can equivalently described by the concepts of places and valuation rings (cf. [19]).

4. Proof of Proposition 2.4^{1}

The case when P is linear was treated in Remark 7 of our preceding paper [12]. This is exactly the second part of our assertion. Thus we assume in the sequel deg P ≥ 2.

Assume that

A_{0}(x) = a ∏_{i=1}^{k}(x − a_{i})^{n_{i}},

with pairwise different a_{1}, …, a_{k} and with positive n_{1}, …, n_{k}. As the roots of A_{0} and of A_{0}(P) are the same we have

A_{0}(P (x)) = a ∏_{i=1}^{k}(P (x) − a_{i})^{n_{i}} = a lc(P)^{deg A_{0}} ∏_{j=1}^{k}(x − a_{j})^{m_{j}}

with nonzero m_{1}, …, m_{k} and where lc(P) denotes the leading coefficient of P. From this we get

P (x) − a_{i} = lc(P) ∏_{j=1}^{k}(x − a_{j})^{m_{ij}},

for all i = 1, …, k, where the m_{ij} are non-negative integers. If we assume that there exist indices u ≠ v with m_{uj}, m_{vj} both > 0, then we get that a_{v} − a_{u} = const has a nontrivial divisor, namely x − a_{j}, contradicting the fact that a_{v} − a_{u} is constant and different from zero.

Now we proceed as follows: Assume that we have

P (x) − a_{1} = lc(P) ∏_{j=1}^{k}(x − a_{j})^{m_{1j}}.

There exists j_{1} such that m_{1j_{1}} > 0 since deg P > 0. From the discussion above this implies that m_{ij_{1}} = 0 for all i = 2, …, k. Now look at

P (x) − a_{2} = lc(P) ∏_{{j=1 \atop j≠j_{1}}}^{k} (x − a_{j})^{m_{2j}}.

Now there exists m_{2j_{2}} > 0 and we have m_{ij_{2}} = 0 for i = 1, 3, …, k, especially m_{1j_{2}} = 0. Continuing this we get, because there are k different roots, that there exists a permutation π of {1, …, k} such that

(4.1)  P (x) − a_{i} = lc(P)(x − a_{π(i)})^{deg P} , for i = 1, …, k.

If k = 1 then A_{0} = a(x − a_{1})^{deg A_{0}} and π(1) = 1, hence

P (x) = lc(P)(x − a_{1})^{deg P} + a_{1}

and we obtain the first assertion of the proposition.

1We thank Ákos Pintér for helping us in a former proof of this proposition. The final part of the present argument was suggested by the anonymous referee, whom we are also indebted.

It remains to prove that there are no more possibilities if the degree of P and the number of distinct zeros of A_{0} is at least 2. Indeed, if k ≥ 2 then (4.1) implies

\frac{a_{2} − a_{1}}{lc(P)} = (x − a_{π(1)})^{deg P} − (x − a_{π(2)})^{deg P} .

We introduce a new variable y = x − a_{π(2)} and put e = a_{π(2)} − a_{π(1)}, f = (a_{2} − a_{1})/lc(P), r = deg P. Then (y + e)^{r} − y^{r} = f, hence

∑_{k=0}^{r−1} \binom{r}{k}e^{r−k}y^{k} = f,

which implies r = 1, e = f. Consequently, deg P must be one. □

5. Proof of Proposition 3.5

We prove the assertion by induction on n. The case n = 2 follows easily from Theorem 3.3 for n = 2. Observe that by our assumptions there are at most k solutions with α_{1}x_{1}, α_{2}x_{2} both in K. Therefore, we have at most

log(g + 2)(3e)^{3s+2} + k ≤ A(2, k)

solutions (x_{1}, x_{2}) ∈ U.

Now suppose n > 2 and our claim to be shown for n′ < n. Again by Theorem 3.3, either α_{1}x_{1}, …, α_{n}x_{n} all belong to K^{∗}, which by our assumption is possible for at most k solutions (x_{1}, …, x_{n}), or (x_{1}, …, x_{n}) lies in one of at most

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

proper linear subspaces of F^{n}.

Let V be one of these subspaces, defined by an equation

γ_{1}x_{1} + … + γ_{n}x_{n} = 0

where γ_{i} ∈ F for i = 1, …, n. Observe that at least two of the coefficients are different from zero. Without loss of generality we may assume that γ_{1} ≠ 0 and that γ_{1} = 1, i.e.

x_{1} + γ_{2}x_{2} + … + γ_{n}x_{n} = 0.

Subtracting this equation from our S-unit equation (3.5) under consideration gives

(α_{2} − γ_{2}α_{1})x_{2} + … + (α_{n} − γ_{n}α_{1})x_{n} = 1.

This is again an S-unit equation but now with n − 1 variables. We write for the above equation

∑_{i∈I} δ_{i}x_{i} = 1

where I is a subset of {2, …, n} of cardinality |I| ≥ 1, because otherwise we would have

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

a contradiction to (3.5), and where δ_{i} ≠ 0 for i ∈ I. Let J be a non-empty subset of I and consider those solutions in U ∩ V for which

(5.1)  ∑_{i∈J} δ_{i}x_{i} = 0,

but no proper non-empty subsum of (5.1) vanishes. Thus 1 ≤ |J| ≤ n − 1. We have to distinguish two cases, depending on whether |J| = 1 or |J| ≥ 2.

Case 1.

Let J = {u} with 2 ≤ u ≤ n. In this case the above equation reduces to

(α_{u} − γ_{u}α_{1})x_{u} = 1,

with α_{u} ≠ γ_{u}α_{1}. Therefore, we get

x_{u} = (α_{u} − γ_{u}α_{1})^{−1},

and substituting this into (3.5) finally yields

(5.2)  ∑_{{i=1 \atop i≠u}}^{n} \frac{α_{i}}{(1 − (α_{u} − γ_{u}α_{1})^{−1}α_{u})}x_{i} = 1.

Observe that the denominator is different from 0, because otherwise we would have

∑_{{i=1 \atop i≠u}}^{n} α_{i}x_{i} = 0,

leading to a contradiction to assumption (3.6). Equation (5.2) is an S-unit equations with n − 1 variables. By induction, we can conclude that this equation has at most A(n − 1, k) solutions such that no non-trivial subsum vanishes, and since each of this solutions gives rise to at most k solutions of (3.5) we conclude that we get at most kA(n − 1, k) solutions (x_{1}, …, x_{n}) in this case. Observe that any vanishing subsum of equation of (5.2) would immediately lead to a vanishing subsum of our original equation, and thus we do not have to take them into account.

Case 2.

Now we can assume that |J| ≥ 2 and in this situation we can at once use the induction hypothesis. Thus we conclude that (5.1) has at most A(n−1, k) solution, where no subsum vanishes. Observe that the vanishing subsums of

∑_{i∈I} δ_{i}x_{i} = 1,

are taken into account by the different choices of J. Since we know by our assumptions that each of this solutions gives rise to at most k solutions of our original problem, we get at most kA(n − 1, k) solutions (x_{1}, …, x_{n}) also in this case.

By consideration of the possible subsets J of I, we see that each subspace V contains at most 2^{n}kA(n − 1, k) solutions. We still have to multiply this by the number of subspaces. In this way we obtain a bound

2^{n}kA(n − 1, k) log(g + 2)(e(n + 1))^{(n+1)s+2} + k.

This is

2^{n+1}kk^{n−1}e^{(n−1)^{2}} (log(g + 2))^{n−3} (en)^{(n−2)n(s+1)} · log(g + 2)(e(n + 1))^{(n+1)s+2} ≤

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

≤ A(n, k),

and therefore Proposition 3.5 follows. □

6. Preliminaries and properties of the field of definition

Let (P_{n}(x))_{n=0}^{∞} be defined by (1.1). Moreover, let α_{1}(x), …, α_{d}(x) as well as α_{1}(P (x)), …, α_{d}(P (x)) denote the roots of the characteristic polynomial of (G_{n}(x))_{n=0}^{∞} and (G_{n}(P (x))_{n=0}^{∞} respectively. We will always assume that D(x) ≠ 0 (which follows from condition (ii) in all theorems), thus α_{1}(x), …, α_{d}(x) are pairwise distinct. In the above argument we may replace x by any other element that is transcendental over K. So in particular, α_{1}(P (x)), …, α_{d}(P (x)) are pairwise distinct.

Let us define

F = K(x, α_{1}(x), …, α_{d}(x), α_{1}(P (x)), …, α_{d}(P (x))).

Then F is a finite extension of K(x), i.e. we have an algebraic function field in one variable over the constant field K. Denote as usual the multiplicative group of F by F^{∗}. Define Γ to be the subgroup of F^{∗} generated by

α_{1}(x), …, α_{d}(x), α_{1}(P (x)), …, α_{d}(P (x));

these are the characteristic roots of (G_{n}(x))_{n=0}^{∞} and (G_{n}(P (x)))_{n=0}^{∞}, respectively.

It is obvious that Γ can be seen as a finitely generated subgroup of ℂ^{∗}, because we can embed F^{∗} into ℂ^{∗} by choosing a maximal set of algebraically independent elements from x and the coefficients of A_{0}, …, A_{d−1}, G_{0}, …, G_{d−1}, and sending the elements of this set to algebraically independent elements of ℂ. Moreover, it is clear that the rank r of Γ is at most 2d.

F will be the field of definition for our problem, because we will reduce the equations under consideration to linear equations over F, where we look for solutions in Γ. First, we will deduce some more information about these sets and we will do this in the following lemmas.

First, we calculate the genus of the function field F/K.

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

g ≤ d^{2d^{2}} deg D(deg P + 1) − 2.

Proof. First observe that we have

F = K(x)(α_{1}(x), …, α_{d}(x)) · K(x)(α_{1}(P (x)), …, α_{d}(P (x))).

Let us denote

F_{1} = K(x, α_{1}(x), …, α_{d}(x)), F_{2} = K(x, α_{1}(P (x)), …, α_{d}(P (x))).

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

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

Next, we calculate bounds for g_{1}, g_{2}. Observe that

F_{1} = K(x, α_{1}(x)) · K(x, α_{2}(x)) ⋯ K(x, α_{d}(x)).

We apply the Hurwitz Genus Formula (Theorem 3.7) to K(x)/K and F̃/K(x), where F̃ = K(x, α_{i}(x)) for some i = 1, …, d. Observe that the constant field of F and therefore of all intermediate fields is K and that the genus of the rational function field K(x) is zero (cf. [19], page 22). Denote by g̃ the genus of F̃. Therefore, we get

2g̃ − 2 = −2[F̃ : K(x)] + deg Diff (F̃/K(x)).

We have to calculate the different:

Diff (F̃/K(x)) = ∑_{P ∈ℙ_{K(x)}} ∑_{P′|P} d(P′|P)P′,

where ℙ_{K(x)} denotes the set of places of K(x) and P′|P means that P′ ∈ ℙF̃ (the places of F̃) lies over P. The second sum is extended over all extensions of P. Because of char K = 0, we conclude by Dedekind’s Different Theorem (cf. [19], page 89) that

d(P′|P) = e(P′|P) − 1 ≤ e(P′|P),

for all places P of K(x) and for all places P′ in F̃ lying over P and where e(P′|P) denotes the ramification index. Moreover, for almost all P and P′ we have d(P′|P) = 0, i.e. e(P′|P) = 1. So, let us denote by S the set of places P ∈ ℙ_{K(x)} which ramify in F̃.

We have to calculate

deg Diff (F̃/K(x)) = ∑_{P ∈S} ∑_{P′|P} d(P′|P) deg P′ ≤ ∑_{P ∈S} ∑_{P′|P} e(P′|P) deg P′.

We use

deg P′ = [F̃_{P′} : K] = [F̃_{P′} : K(x)_{P}] · [K(x)_{P} : K] = f(P′|P) · deg P,

where F̃_{P′}, K(x)_{P} are the residue class fields of P′, P respectively and f(P′|P) is the relative degree of P′ over P. Thus

deg Diff (F̃/K(x)) ≤ ∑_{P ∈S} deg P ∑_{P′|P} e(P′|P)f(P′|P) = ∑_{P ∈S} deg P · [F̃ : K(x)],

where we have used Theorem III.1.11 in [19] to get the last equation. Finally, we use that since K is algebraically closed deg P = 1 for all P ∈ S (e.g. cf. Proposition I.2.1 in [19]) and that [F̃ : K(x)] ≤ d. This implies deg Diff (F̃/K(x)) ≤ d |S| and finally

g̃ ≤ \frac{|S| − 2}{2}d + 1 ≤ d(|S| − 1),

where |S| denotes as usual the cardinality of S and where we have assumed that d ≥ 2, |S| ≥ 2, which is no loss of generality.

We want to bound |S|. Observe that α_{1}(x), …, α_{d}(x) are integral over K[x] since they are the roots of a monic polynomial with coefficients in K[x] (namely the characteristic polynomial). Therefore there exists an - over K(x) - monic irreducible polynomial H(T) with coefficients in K[x] which generates F̃/K(x). For ξ ∈ K let P_{ξ} denote the place in K(x) corresponding to x − ξ. We have e(P |P_{ξ}) = 1 for almost all ξ ∈ K. Indeed, by a theorem of Kummer (cf. [19], page 80) only at the poles of the coefficients of the polynomial H(T) and at roots of the discriminant of H(T) ramifications may occur (and the coefficients are polynomials and thus do not have poles at finite places). Since H(T) divides Q(T) the discriminant of H(T) must divide D(x). Hence,

|S| ≤ deg D + 1

and therefore

g̃ ≤ d deg D.

Now we use Castelnuovo’s Inequality (Theorem 3.6) several times and conclude

g_{1} ≤ (… (((2d^{2} deg D + d^{2})d^{2} + d^{2} deg D + d^{3})d^{3} + d^{2} deg D + d^{4})d^{4} +

+ …)d^{d−1} + d^{2} deg D + d^{d} ≤
≤ d^{d^{2}}(deg D + 1).

In precisely the same way, we can conclude

g_{2} ≤ d^{d^{2}}(deg D deg P + 1).

Now using Castelnuovo’s Inequality (Theorem 3.6) once again we get

g ≤ d!d^{d^{2}}(deg D + 1) + d!d^{d^{2}}(deg D deg P + 1) + d!^{2} ≤
≤ d!d^{d^{2}}(deg D(deg P + 1) + 3) ≤ d^{2d^{2}} deg D(deg P + 1) − 2,

and therefore our proof is finished. □

Next, we prove the following lemma:

Lemma 6.2. We assume deg A_{0} ≥ 1 and deg P ≥ 1. Then there exists a finite subset S ⊂ M_{F} of valuations of the function field F such that Γ is contained in the group of S-units U_{S} and such that

|S| ≤ d!^{2}(deg A_{0}(deg P + 1) + 1) ≤ 6d!^{2} deg A_{0} deg P − 1.

Proof. Let S_{∞} be the set of infinite valuations of F and S_{0} the set of finite valuations of F. Note that for every ν ∈ S_{0} we have ν(α_{1}) ≥ 0, …, ν(α_{d}) ≥ 0, ν(α_{1}(P)) ≥ 0, …, ν(α_{d}(P)) ≥ 0 since these functions are integral over K[x]. Take

S = S_{∞} ∪ ⋃_{i=1}^{2d} S_{i},

where

S_{i} = {ν ∈ S_{0} | ν(α_{i}) > 0},
S_{d+i} = {ν ∈ S_{0} | ν(α_{i}(P)) > 0}

for i = 1, …, d. Then clearly Γ is a subgroup of U_{S}. Since [F : K(x)] ≤ d!^{2}, we have |S_{∞}| ≤ d!^{2}. Further,

α_{1}(x) ⋯ α_{d}(x) · α_{1}(P (x)) ⋯ α_{d}(P (x)) = A_{0}(x) · A_{0}(P (x)) =: Q(x).

Therefore,

⋃_{i=1}^{2d} S_{i} =: S̃ := {ν ∈ S_{0} | ν(Q) > 0}.

Each of the valuations in S̃ is an extension to F of some valuation ν_{ξ} on K(x) corresponding to a zero ξ of Q(x). The polynomial Q(x) has at most deg Q = deg A_{0}(deg P + 1) zeros, and for each of these zeros ξ, the valuation ν_{ξ} can be extended in at most d!^{2} ways to a valuation on F. Therefore, |S̃| ≤ d!^{2} deg A_{0}(deg P + 1). This implies

|S| ≤ d!^{2}(deg A_{0}(deg P + 1) + 1) ≤
≤ d!^{2}(2 deg A_{0} deg P + 1) ≤ 6d!^{2} deg A_{0} deg P − 1,

since deg A_{0} ≥ 1 and deg P ≥ 1, which was our assertion. □

Finally, we need the following properties:

Lemma 6.3. Assume that none of the roots and the quotient of distinct roots of the characteristic polynomial of (G_{n}(x))_{n=0}^{∞} is an element of K^{∗}. Let γ_{1}, γ_{2} be non-zero elements of F. Then there is at most one pair of integers n, m such that

(6.1)  γ_{1} \frac{α_{i}(x)^{n}}{α_{k}(P (x))^{m}} ∈ K^{∗} and γ_{2} \frac{α_{j}(x)^{n}}{α_{k}(P (x))^{m}} ∈ K^{∗}

or

(6.2)  γ_{1} \frac{α_{i}(x)^{n}}{α_{k}(P (x))^{m}} ∈ K^{∗} and γ_{2} \frac{α_{j}(P (x))^{m}}{α_{k}(P (x))^{m}} ∈ K^{∗}

respectively, where 1 ≤ i, j, k ≤ d are different integers.

Proof. First we prove equation (6.1). 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, by dividing the first equations (equ. (6.1) with n_{1}, m_{1}) by the second equations (equ. (6.1) with n_{2}, m_{2}) we get

(6.3)  \frac{α_{i}(x)^{n}}{α_{k}(P (x))^{m}} ∈ K^{∗} and \frac{α_{j}(x)^{n}}{α_{k}(P (x))^{m}} ∈ K^{∗},

hence α_{i}(x)^{n}/α_{j}(x)^{n} ∈ K^{∗}. But this can only hold if α_{i}(x)/α_{j}(x) ∈ K^{∗}, which contradicts our assumption, or if n = 0, whence n_{1} = n_{2} and so by (6.3) we get also m_{1} = m_{2}.

In the same way, if we assume that (6.2) holds for two such pairs, we conclude that

(6.4)  \frac{α_{i}(x)^{n}}{α_{k}(P (x))^{m}} ∈ K^{∗} and \frac{α_{j}(P (x))^{m}}{α_{k}(P (x))^{m}} ∈ K^{∗}.

But now we can conclude that m = 0 or m_{1} = m_{2} by using the second part of (6.4) and then by the first part of (6.4), we get also n_{1} = n_{2}. Observe that we have used our assumption twice to get this. □

In the next section, we will reduce the solvability of our equation (2.3) to the solvability of a system of critical exponential equations in n, m.

7. Reduction to a system of equations

First observe that by (2.2) we have g_{i}(x), g_{i}(P (x)) ∈ F for i = 1, …, d. The same equation and the definition of R implies

∏_{j=1}^{d} g_{j}(x)α_{j}(x) ∏_{{i=1 \atop i≠j}}^{d}(α_{i}(x) − α_{j}(x)) = R.

By condition (iv) of Theorems 2.1 and 2.5 or condition (iii) of Theorems 2.3 and 2.7, we have R ≠ 0. Hence g_{j}(x) ≠ 0 for j = 1, …, d. This ensures g_{j}(P (x)) ≠ 0 for j = 1, …, d.

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

(7.1)  ∑_{i=1}^{d} g_{i}(x)α_{i}(x)^{n} = c ∑_{i=1}^{d} g_{i}(P (x))α_{i}(P (x))^{m}.

We have already seen that g_{d}(P (x)) ≠ 0. We have A_{0} ≠ 0 by (ii) and (iii) in Theorems 2.1 and 2.5 and by (iii) in Theorems 2.3 and 2.7 respectively, hence α_{d}(P (x)) ≠ 0 holds too. Dividing by g_{d}(P (x))α_{i}(P (x))^{m} and sorting the summands we obtain the weighted equation

(7.2)  ∑_{i=1}^{d} \frac{g_{i}(x)}{g_{d}(P (x))}x_{i} − ∑_{i=1}^{d−1} \frac{g_{i}(P (x))}{g_{d}(P (x))}x_{d+i} = 1

in the unknowns

x_{j} = c^{−1} \frac{α_{j}(x)^{n}}{α_{d}(P (x))^{m}} for j = 1, …, d,

x_{d+j} = \frac{α_{j}(P (x))^{m}}{α_{d}(P (x))^{m}} for j = 1, …, d − 1.

Observe that x_{1}, …, x_{2d−1} are elements of the set U_{S} which exists by Lemma 6.2. This is because of the fact that Γ is contained in U_{S} and c ∈ K^{∗}. Lemma 6.3 implies that any given pair of elements (x_{i}, x_{j}) or (x_{i}, x_{d+j}) for 1 ≤ i < j ≤ d gives rise to at most one pair (n, m), especially any tuple (x_{1}, …, x_{2d−1}) induces at most one solution (n, m) of the equation in consideration. Because of the fact that α_{1}(x), …, α_{d}(x) are not in K^{∗} (and therefore also α_{1}(P (x)), …, α_{d}(P (x)) are not in K^{∗}) it follows that a given pair (x_{d+i}, x_{d+j}) (1 ≤ i < j ≤ d) induces at most one m. We will show that this in turn induces (via our equation G_{n}(x) = c G_{m}(P (x)) at most finitely many pairs (n, m).

We set

β_{i} = \frac{g_{i}(x)}{g_{d}(P (x))} and β_{d+i} = \frac{g_{i}(P (x))}{g_{d}(P (x))} for i = 1, …, d.

Now let us assume that we can bound the number of solutions of the equation

β_{1}x_{1} + … + β_{d}x_{d} + β_{d+1}x_{d+1} + … + β_{2d−1}x_{2d−1} = 1,

where no nontrivial subsum vanishes, by a constant W (2d − 1). More general we assume that the number of solutions of

(7.3)  γ_{1}y_{1} + … + γ_{n}y_{n} = 1,

with γ_{1}, …, γ_{n} ∈ F^{∗} and y_{i} = x_{j} or = x_{d+j} for some j, where no nontrivial subsum vanishes and which leads to a solution of our equation, can be bounded by W (n). This is of course true in the special case that c is always equal to 1 by the theorem of Evertse, Schlickewei and Schmidt (Theorem 3.1). In the more general case we will deduce this later (see Section 9) using Proposition 3.5.

Let J be a non-empty subset of {1, …, 2d−1} with 1 ≤ |J| ≤ 2d−2 and consider those solutions (x_{1}, …, x_{2d−1}) ∈ U_{S}^{2d−1} of the above equation (7.2) for which

(7.4)  ∑_{i∈J} β_{i}x_{i} = 1,

but no proper non-empty subsum of (7.4) vanishes. We have to distinguish three cases:

Case 1.

First we assume that |J| = 2d − 2. In this case we must have β_{j}x_{j} = 0 for the single j not belonging to J. But this cannot hold since β_{j} ≠ 0 for j = 1, …, d and 0 ∉ Γ ⊂ U_{S}.

Case 2.

The second case is that J ⊆ {d + 1, …, 2d − 1}. This case is special because the components of (7.4) now depend only on m. By Theorem 3.2 we obtain that (7.4) has at most

e^{(6(d−1))^{3(d−1)}}

solutions. This implies that we have at most that much possibilities for m. For fixed m the right hand side of

∑_{i=1}^{d} g_{i}(x)c^{−1}α_{i}(x)^{n} = ∑_{i=1}^{d} g_{i}(P (x))α_{i}(P (x))^{m}

is a fixed element, namely G_{m}(P (x)) of K[x]. If G_{m}(P (x)) = 0 then we obtain G_{n}(x) = 0 which can hold by Theorem 3.2 for at most

e^{(6d)^{3d}}

many n too. Otherwise dividing by G_{m}(P (x)) we get

∑_{i=1}^{d} \frac{g_{i}(x)}{G_{m}(P (x))}y_{i} = 1,

where

y_{i} = c^{−1}α_{i}(x)^{n} for i = 1, …, d.

This is again a weighted S-unit equation, whose number of solutions we can bound by W^{∗}(d), which we will again show later. Taking account of the possible subsets J, we see that we have at most

2^{d} max {W^{∗}(d), e^{(6d)^{3d}}}e^{(6(d−1))^{3(d−1)}}

pairs of solutions (n, m) in this case.

Case 3.

The remaining case is J ∩ {1, …, d} ≠ ∅. We consider two subcases: The first subcase is 1 < |J| ≤ 2d − 3. In this case we can bound the number of solutions (n, m) by W (2d − 3) since (7.4) is a weighted S-unit equation with 2d − 3 variables. The number of cases can be bounded by 4^{d}. Thus we have

4^{d}W (2d − 3)

possible solutions. The last subcase is |J| = 1. Since we have J ∩ {1, …, d} ≠ ∅, we conclude that β_{u}x_{u} = 1 for some 1 ≤ u ≤ d, i.e. we have

g_{u}(x)α_{u}(x)^{n} = c g_{d}(P (x))α_{d}(P (x))^{m}.

If this is true then the following equation

∑_{{i=1 \atop i≠u}}^{d} g_{i}(x)α_{i}(x)^{n} = c ∑_{{j=1 \atop j≠d}}^{d} g_{j}(P (x))α_{j}(P (x))^{m}

must simultaneously holds. But this is essentially the same equation as (7.1) with one summand less at both sides of the equation. Thus, we can continue this process and ultimately obtain: The equation (7.1) has at most

d · (W (2d − 1) + 2^{d} max {W^{∗}(d), e^{(6d)^{3d}}}e^{(6(d−1))^{3(d−1)}} + 4^{d}W (2d − 3))

solutions (n, m) ∈ ℤ^{2}, n, m ≥ 0, n ≠ m or it is a solution of a system of equations of the form

g_{u}(x)α_{u}(P (x))^{n} = c g_{π(u)}(P (x))α_{π(u)}(P (x))^{m}, u = 1, …, d,

where π is a permutation of the set {1, …, d}.

To handle this exceptional systems of equations, we will need most of the assumptions in our theorems. We will handle these cases in the next chapter.

8. Handling the exceptional cases

We start with the system of equations

(8.1)  g_{u}(x)α_{u}(P (x))^{n} = c g_{π(u)}(P (x))α_{π(u)}(P (x))^{m}, u = 1, …, d,

where π is a permutation of the set {1, …, d}. We will show that this system has only finitely many solutions (n, m).

First we assume the conditions of Theorems 2.1 and 2.5.

Indeed, in this case we have deg D(P) = deg D deg P > deg D ≥ 1, since deg P > 1 by assumption (ii). On the other hand we have

D(P (x)) = ∏_{j=1}^{d} Q(P)′(α_{j}(P (x))) and D(x) = ∏_{j=1}^{d} Q′(α_{j}(x)),

where ′ denotes differentiation with respect to the variable T. Hence there exists a pair (u, v) = (u, π(u)) and a finite valuation ν of F such that

ν(Q(P)′(α_{v}(P))) > ν(Q′(α_{u})) ≥ 0.

Before continuing we state the following useful lemma.

Lemma 8.1. Let A, B, P ∈ K[x]. Then

gcd(A, B) = 1 if and only if gcd(A(P), B(P)) = 1.

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

Now assumption (iii) of Theorem 2.1 together with Lemma 8.1 implies

ν(α_{v}(P)) = 0,

since ν(D(P)) > 0, while assumption (iv) implies that

ν (∑_{i=0}^{d−1} L_{i}(A⃗, G⃗)α_{v}(P)^{i}) = 0.

Hence (2.2) implies (with v instead of 1) that

ν(g_{v}(P)) = −ν (∏_{{i=1 \atop i≠v}}^{d}(α_{i}(P) − α_{v}(P))) = −ν(Q(P)′(α_{v}(P))).

Therefore (8.1) implies

(8.2)  ν(g_{u}) + nν(α_{u}) = −ν(Q(P)′(α_{v}(P))),

where we have used ν(c) = 0 since c ∈ K^{∗}. Observe that α_{1}(x), …, α_{d}(x) are integral over K[x], as they are zeros of the monic characteristic equation Q(T) = 0 with coefficients in K[x]. The integral closure of K[x] in F consists of those elements f such that ν(f) ≥ 0 for every finite valuation ν of F. So in particular, ν(α_{u}) ≥ 0.

Using (2.2) once again (with u instead of 1), we get

ν(g_{u}) + ν(α_{u}) + ν(Q′(α_{u})) = ν (∑_{i=0}^{d−1} L_{u}(A⃗, G⃗)α_{u}^{i}) ≥ 0,

by the remark from above and the fact that L_{u}(A⃗, G⃗)(x) ∈ ℚ[A⃗, G⃗] and the components of A⃗ and G⃗ are (as polynomials) integral elements. Therefore, we conclude

ν(g_{u}) + ν(α_{u}) ≥ −ν(Q′(α_{u})),

which yields together with (8.2)

nν(α_{u}) = −ν(Q(P)′(α_{v}(P))) − ν(g_{u}) ≤
≤ −ν(Q(P)′(α_{v}(P))) + ν(Q′(α_{u})) + ν(α_{u}) < ν(α_{u}).

Since ν(α_{u}) ≥ 0, we conclude n = 0. Thus, equation (8.1) induces only solutions of the kind (0, m) with m > 0.

Now we have to distinguish between the assumptions of Theorems 2.1 and 2.5. First let us assume (i) of Theorem 2.1. We investigate for n = 0

g_{u}(x) = c g_{v}(P (x))α_{v}(P (x))^{m}.

Assume that there are two solutions m_{1} and m_{2}. Then we have

c_{1}α_{v}(P (x))^{m_{1}} = c_{2}α_{v}(P (x))^{m_{2}}

(c ∈ K^{∗} depends on m) or

α_{v}(P (x))^{m_{1}−m_{2}} ∈ K^{∗},

which is a contradiction unless m_{1} = m_{2}. Therefore, we get for each system (8.1) at most one solution (n, m).

Now assume that we have assumption (i) of Theorem 2.5. By the arguments from above one has

α_{v}(P (x))^{m_{1}−m_{2}} = 1,

which implies m_{1} = m_{2}. So there is only one possible value for m and therefore at most one solution (n, m).

We consider now the assumptions of Theorems 2.3 and 2.7.

From condition (iv) (together with (ii) and (iii)) we get that there is a valuation ν of F with

ν(A_{0}) > 0 and ν(A_{0}(P)) = 0 or ν(A_{0}) = 0 and ν(A_{0}(P)) > 0.

From this we can conclude (observe that α_{1}(x), …, α_{d}(x) are integral over K[x]) that there exists an index u (1 ≤ u ≤ d) with either

ν(α_{u}) > 0 and ν(α_{i}(P)) = 0 for i = 1, …, d,

or

ν(α_{u}(P)) > 0 and ν(α_{i}) = 0 for i = 1, …, d.

In the first case we look at the equation

g_{u}(x)α_{u}(x)^{n} = c g_{π(u)}(P (x))α_{π(u)}(P (x))^{m}

of the system (8.1). We get

ν(g_{u}) + nν(α_{u}) = ν(g_{π(u)}).

But this can hold for at most one n, namely

n_{0} = \frac{ν(g_{π(u)}) − ν(g_{u})}{ν(α_{u})}.

In the second case we look at

g_{π^{−1}(u)}(x)α_{π^{−1}(u)}(x)^{n} = c g_{u}(P (x))α_{u}(P (x))^{m}.

Similar as above we get

ν(g_{π^{−1}(u)}) = ν(g_{u}(P)) + mν(α_{u}(P))

and this can only hold for at most one m, namely

m_{0} = \frac{ν(g_{π^{−1}(u)}) − ν(g_{u}(P))}{ν(α_{u}(P))}.

Let us first assume the conditions of Theorem 2.3. The case that there is at most one n = n_{0} implies as above that we have

c α_{π(u)}(P (x))^{m} = \frac{g_{u}(x)α_{u}(x)^{n_{0}}}{g_{π(u)}(P (x))} .

From this we can again conclude that there is at most one m too. The case that there is at most one m = m_{0} runs the same line and gives by

c^{−1}α_{π^{−1}(u)}(x)^{n} = \frac{g_{u}(P (x))α_{u}(P (x))^{m_{0}}}{g_{π^{−1}(u)}(x)}

and condition (i) that there is at most one n. So in this case each system (8.1) gives at most one solution (n, m).

Finally, we assume the hypotheses of Theorem 2.7. Again as above we get via the equations

α_{π(u)}(P (x))^{m_{1}−m_{2}} = 1 or α_{π^{−1}(u)}(x)^{n_{1}−n_{2}} = 1

that there is at most one possible solutions (n, m) in both cases.

To sum up we can bound the number of solutions (n, m) ∈ ℤ^{2}, n, m ≥ 0, n ≠ m which come from systems of equations (8.1) by

d!.

Using this bound and the other bound calculated in the previous chapter we will be able to complete our proof and we will do this for Theorems 2.1 and 2.3 and Theorems 2.5 and 2.7 in separate sections.

9. Calculation of the bounds for Theorems 2.1 and 2.3

It is left to show that the equation (cf. (7.3))

γ_{1}y_{1} + … + γ_{n}y_{n} = 1

with γ_{1}, …, γ_{n} ∈ F^{∗} and

y_{i} = c^{−1} \frac{α_{i}(x)^{n}}{α_{d}(P (x))^{m}} , or y_{i} = \frac{α_{i}(P (x))^{m}}{α_{d}(P (x))^{m}}

for some i, where no nontrivial subsum vanishes and which leads to a solution of G_{n}(x) = c G_{m}(P (x)) has at most W (n) solutions.

We first show this for the equation

∑_{i=1}^{d} \frac{g_{i}(x)}{g_{d}(P (x))}x_{i} − ∑_{i=1}^{d−1} \frac{g_{i}(P (x))}{g_{d}(P (x))}x_{d+i} = 1

where x_{1}, …, x_{2d−1} are elements of the set KΓ ⊂ U_{S}. Take U to be the subset of (KΓ)^{2d−1} consisting of elements (x_{1}, …, x_{2d−1}) of the form as above which lead to solutions of G_{n}(x) = c G_{m}(P (x))) where S is the set of absolute values of F from Lemma 6.2. We have to show that we have at most W (2d − 1) solutions where no nontrivial subsum vanishes and we do this by applying Proposition 3.5. Therefore, we first have to show that each pair (x_{i}, x_{j}) gives rise to at most k solutions of the above equation. Lemma 6.3 implies that any given pair of elements (x_{i}, x_{j}) or (x_{i}, x_{d+j}) for 1 ≤ i < j ≤ d gives rise to at most one pair (n, m). Because of the fact that α_{1}(x), …, α_{d}(x) are not in K^{∗} (and therefore also α_{1}(P (x)), …, α_{d}(P (x)) are not in K^{∗}) it follows that a given pair (x_{d+i}, x_{d+j}) (1 ≤ i < j ≤ d) induces at most one m. But this implies that we have to calculate the number of solutions n of G_{n}(x) = c G_{m}(P (x)). If G_{m}(P (x)) = 0 this equation reduces to G_{n}(x) = 0, which can happen by Theorem 3.2 for at most

e^{(6d)^{3d}}

many n. Now, if G_{m}(P (x)) is different from 0 we have to consider the equation

(9.1)  \frac{g_{1}(x)}{G_{m}(P (x))}z_{1} + … + \frac{g_{d}(x)}{G_{m}(P (x))}z_{d} = 1,

where

z_{1} = c^{−1}α_{1}(x)^{n}, …, z_{d} = c^{−1}α_{d}(x)^{n}.

But we can apply Proposition 3.5 (where we put U = {(c^{−1}α_{1}(x)^{n}, …, c^{−1}α_{d}(x)^{n})∈ (KΓ)^{n}}) to this equation once more: each pair (z_{i}, z_{j}) gives rise to at most one n, because otherwise we have α_{i}(x)/α_{j}(x) ∈ K^{∗}, which contradicts assumption (i) in Theorems 2.1 and 2.3; moreover, assume that we have

γc^{−1}α_{i}(x)^{n_{1}} ∈ K^{∗}, γc^{−1}α_{i}(x)^{n_{2}} ∈ K^{∗},

where γ ∈ F^{∗}, then we get a contradiction unless n_{1} = n_{2}. Thus we can bound the number of solutions of (9.1), where no subsum vanishes, by W^{∗}(d) := A(d, 1). Since all nontrivial subsums are of the same shape and there are at most 2^{d} subsums, we get that there are at most

2^{d}e^{d^{2}} (log(g + 2))^{d−2} (ed)^{(d−1)(d+1)(s+1)}

pairs (n, m) in this case. Altogether, we get at most

e^{d^{2}+(6d)^{3d}} (log(g + 2))^{d−2} (ed)^{(d−1)(d+1)(s+1)}

solutions (n, m) of (7.1).

Now let γ_{1}, γ_{2} ∈ F^{∗} be given. In exactly the same way as above, Lemma 6.3 implies that γ_{1}x_{i}, γ_{2}x_{j} ∈ K^{∗} or γ_{1}x_{i}, γ_{2}x_{d+j} ∈ K^{∗} for 1 ≤ i < j ≤ d gives rise to at most one pair (n, m). Because of the fact that α_{1}(x), …, α_{d}(x) are not in K^{∗} (and therefore also α_{1}(P (x)), …, α_{d}(P (x)) are not in K^{∗}) it follows that γ_{1}x_{d+i}, γ_{2}x_{d+j} ∈ K^{∗} (1 ≤ i < j ≤ d) induces at most one m and we can use the arguments from above to get an upper bound for the number of (n, m) with this property.

From this it follows that we may take

k = e^{d^{2}+(6d)^{3d}} (log(g + 2))^{d−2} (ed)^{(d−1)(d+1)(s+1)}.

Now Proposition 3.5 implies that equation (7.1) has at most

W (2d − 1) =

= e^{(d^{2}+(6d)^{3d})(2d−1)}e^{(2d−1)^{2}} (log(g + 2))^{(d−2)(2d−1)+2d−3} (2ed)^{(2d−2)2d(s+1)} ·

·(2ed)^{(d−1)(d+1)(2d−1)(s+1)} ≤
≤ e^{(d^{2}+2d−1+(6d)^{3d})(2d−1)} (log(g + 2))^{2d^{2}} (2ed)^{5d^{3}(s+1)}

solutions (n, m), where no subsum vanishes.

Observe that exactly the same arguments work for the more general equation (7.3) (because we just use the structure of the solutions and the fact that we want get solutions of G_{n}(x) = c G_{m}(P (x))) and that the bounds W (2d − 3), W^{∗}(d) we get, can trivially be estimated from above by W (2d − 1).

By using the bound for the genus g of F/K (Lemma 6.1), we get

(log(g + 2))^{2d^{2}} ≤ (log (d^{2d^{2}} deg D(deg P + 1)))^{2d^{2}} .

Combining this bound with the upper bounds calculated in Section 7 and Section 8, which add up to

d · (W (2d − 1) + 2^{d} max {W^{∗}(d), e^{(6d)^{3d}}}e^{(6(d−1))^{3(d−1)}} + 4^{d}W (2d − 3)) + d!

and using the bound for the cardinality of S (Lemma 6.2), we get the following bound

C(d, A_{0}, D, P) = e^{(6d)^{4d}} (log (d^{2d^{2}} deg D(deg P + 1)))^{2d^{2}} (2ed)^{30d^{3}d!^{2} deg A_{0} deg P}

for the number of pairs (n, m) of integers with n ≠ m such that G_{n}(x) = c G_{m}(P (x)).

10. Calculation of the bounds for Theorems 2.5 and 2.7

We first have to show that (7.1), which we have written shorter by

β_{1}x_{1} + … + β_{d}x_{d} + β_{d+1}x_{d+1} + … + β_{2d−1}x_{2d−1} = 1,

where x_{1}, …, x_{2d−1} ∈ Γ ⊂ U_{S} has at most W (2d − 1) nondegenerate solutions (n, m), i.e. solutions where no non-trivial subsum of the left hand side of (7.1) vanishes. This follows from the Main Theorem of S-unit equations over fields of characteristic zero due to Evertse, Schlickewei and Schmidt (Theorem 3.1). But instead of applying it directly to the group Γ^{n}, which would yield W (2d − 1) = e^{(6(2d−1))^{3(2d−1)}(2d+1)}, we apply it to the subgroup Γ̃ of (F^{∗})^{2d−1} generated by

(α_{1}(x), …, α_{d}(x), 1, …, 1) and

(α_{d}(P (x))^{−1}, …, α_{d}(P (x))^{−1}, \frac{α_{1}(P (x))}{α_{d}(P (x))}, …, \frac{α_{d−1}(P (x))}{α_{d}(P (x))}) .

Thus the rank of Γ̃ is at most 2. Therefore, we get

W (2d − 1) = e^{(6(2d−1))^{3(2d−1)}·3}

for the number of nondegenerate solutions of (7.1). In the same way we also obtain for the more general equations (7.3)

W (n) = e^{(6n)^{3n}·3}

and for W^{∗}(d) we can actually use Theorem 3.2 to get

W^{∗}(d) = e^{(6d)^{3d}}.

Combining these bounds with the upper bounds calculated in Section 7 and Section 8, yields

d · (W (2d − 1) + 2^{d} max {W^{∗}(d), e^{(6d)^{3d}}}e^{(6(d−1))^{3(d−1)}} + 4^{d}W (2d − 3)) + d!

and therefore we get the following bound

C(d) = e^{(12d)^{6d}}

for the number of pairs (n, m) of integers with n ≠ m such that G_{n}(x) = G_{m}(P (x)).

11. Acknowledgement

The authors are grateful to the referee for comments and suggestions improving a previous version of the paper.

References

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

2. W. D. Brownawell and D. W. Masser, Vanishing sums in function fields, Proc. Cambridge Philos. Soc. 100 (1986), 427–434.

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

4. J.H. Evertse, On sums of S-units and linear recurrences, Compositio Math. 53 (1984), 225–244.

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

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

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

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

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

10. C. Fuchs, Quantitative finiteness resluts for Diophantine equations, Ph.D. thesis, TU Graz 11. C. Fuchs, On the equation G_{n}(x) = G_{m}(P (x)) for third order linear recurring sequences,

Portugal. Math., to appear.

12. C. Fuchs, A. Pethő and R. F. Tichy, On the equation G_{n}(x) = G_{m}(P (x)), Monatsh. Math. 137 (2002), 173–196.

13. C. Lech, A note on recurring series, Ark. Math. 2 (1953), 417–421.

14. A. J. van der Poorten and H. P. Schlickewei, The growth conditions for recurrence sequences, Macquarie Univ. Math. Rep. 82–0041, North Ryde, Australia, 1982.

15. A. Schinzel, Reducibility of polynomials in several variables, Bull. Acad. Polon. Sci., Ser. Sci. Math. 11 (1963), 633–638.

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

17. H. P. Schlickewei, The multiplicity of binary recurrences, Invent. Math. 129 (1997), 11–36.

18. W. M. Schmidt, The zero multiplicity of linear recurrence sequences, Acta Math. 182 (1999), 243–282.

19. H. Stichtenoth, Algebraic Function Fields and Codes, Springer Verlag, Berlin, 1993.

Institut für Mathematik, Technische Universität Graz, Steyrergasse 30, 8010 Graz, Austria

   E-mail address: clemens.fuchs@tugraz.at

Institute for Mathematics and Informatics, University of Debrecen, H-4010 Debrecen, PO Box 12 Hungary

   E-mail address: pethoe@math.klte.hu

Institut für Mathematik, Technische Universität Graz, Steyrergasse 30, 8010 Graz, Austria

   E-mail address: tichy@tugraz.at