ON THE DIOPHANTINE EQUATION G_{n}(x) = G_{m}(y) WITH Q(x, y) = 0

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

Dedicated to Wolfgang Schmidt on his 70th birthday.

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]. Finally, let Q(X, Y) ∈ K[X, Y]. In this paper we are giving conditions depending only on G_{0}, …, G_{d−1}, on Q, and on A_{0}, …, A_{d−1} under which the Diophantine equation

G_{n}(x) = G_{m}(y) with Q(x, y) = 0

has only finitely many solutions (n, m) ∈ ℤ^{2}. This paper is a continuation of the work of the authors on this equation in the special case of Q(X, Y) = Y − P (X) (cf. [8, 6, 9]) and of a recent result due to U. Zannier [15].

2000 Mathematical Subject Classification: Primary 11D45; Secondary 11D04, 11D61, 11B37.

Key words and phrases. Diophantine equations, linear recurring sequences, S-unit equations

1. Introduction

Let K denote an algebraically closed field of characteristic 0, and let A_{0}, …, A_{d−1}, G_{0}, …, G_{d−1} ∈ K[X] and (G_{n}(X))_{n=0}^{∞} be a sequence of polynomials defined by the d-th order linear recurring relation

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

Furthermore, let P (X) ∈ K[X], deg P ≥ 1. Recently, the authors investigated the question, what can be said about the number of solutions of the

∗Address: Institut für Mathematik A, TU Graz, Steyrergasse 30/II, 8010 Graz, Austria. E-mail addresses: clemens.fuchs@tugraz.at and tichy@tugraz.at.

‡Address: Institute of Informatics, University of Debrecen, PO Box 12, 4010 Debrecen, Hungary. E-mail address: pethoe@inf.unideb.hu.

This work was supported by the Austrian Science Foundation FWF, grants S8307-MAT and J2407-N12.

The second author was supported by the Hungarian National Foundation for Scientific Research Grant No. 38225 and 42985.

Diophantine equation

(2)  G_{n}(X) = G_{m}(P (X)).

The problem was motivated by properties of families of orthogonal polynomials. For example, the Chebyshev polynomials of the first kind , which are defined by

T_{n}(X) = cos(n arccos X),

have the well known property that

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

for all integers n. Let us mention that all orthogonal polynomials satisfy a second order linear recurring sequence, e.g. for the Chebyshev polynomials we have T_{0}(X) = 1, T_{1}(X) = X and T_{n+2}(X) = 2XT_{n+1}(X) − T_{n}(X), n = 0, 1, 2, . . ..

Recently, the authors [8] were able to formulate conditions for sequences of polynomials satisfying a second order linear recurrence under which they could conclude that (2) has only finitely many solutions m, n ∈ ℤ, m, n ≥ 0, m ≠ n. For the proof they used the Main Theorem on S-unit equations over finitely generated fields of characteristic zero [3, 5]. Furthermore, they were able to quantify their results by transforming their problem in the function field generated by the characteristic root of the recurrence over the rational function field K(x).

The first author gave suitable extensions of the above results for third order linear recurring sequences (cf. [6]). Later on, the authors generalized their results to linear recurring sequences G_{n}(X) of arbitrary large order [9]. The conditions are somehow complicated to state, essentially, they ensure that there exist valuations in the underlying function field, which have special properties. Let

G(X, 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 G(X, T). We let α_{1}, …, α_{r} denote the distinct roots of the characteristic polynomial G(X, T) in the splitting field L of G(X, T). It is well known that (G_{n}(X))_{n=0}^{∞} has a nice “analytic” representation. More precisely, there exist polynomials C_{1}(T), …, C_{r}(T) ∈ L[T] such that

(3)  G_{n}(X) = C_{1}(n)α_{1}^{n} + … + C_{r}(n)α_{r}^{n},

holds for all n ≥ 0. Assuming that G(X, T) has no multiple roots, i.e. D(X) ≠ 0, we have that the C_{i}(T) = c_{i} are all constant for all i = 1, …, r = d. Assume now 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^{∗},

THE EQUATION G_{n}(x) = G_{m}(y) WITH Q(x, y) = 0 3

(ii) deg P ≥ 2 and deg D ≥ 1, (iii) gcd(D, A_{0}) = 1 and (iv) gcd(D, R(A_{0}, …, A_{d}, G_{0}, …, G_{d})) = 1,

for some polynomial R(A_{0}, …, A_{d}, G_{0}, …, G_{d}) ∈ ℚ[A_{0}, …, A_{d}, G_{0}, …, G_{d}] (for details we refer to [9]). Then equation

(4)  G_{n}(X) = c G_{m}(P (X)),

where c ∈ K^{∗} = K\{0} is variable, 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. We also obtained the result under 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_{0}, …, A_{d}, G_{0}, …, G_{d}) ≠ 0, and (iv) the set of zeroes of A_{0} is not equal to that of A_{0}(P).

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

For the special case of the equation

(5)  G_{n}(X) = G_{m}(P (X))

we could even show more. Namely, assuming the conditions from above with

(i’) None of the roots and the quotients of distinct roots of the charac-

teristic polynomial of (G_{n}(X))_{n=0}^{∞} is a root of unity, instead of (i), respectively, we proved that equation (5) has at most

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

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

Very recently, U. Zannier used elementary method from the theory of function fields to improve on these results. In fact, he was able to completely describe the matter: suppose that deg P ≥ 2 and that the recurring sequence G_{n}(X) is simple with characteristic roots α_{1}, …, α_{d} satisfying that no ratio α_{i}/α_{j}, i ≠ j, lies in K. Then if there are only finitely many solutions m, n of

G_{n}(X) = c G_{m}(P (X)), m, n ∈ ℕ,

where c = c(m, n) ∈ K^{∗} may depend on m, n, their number is at most 8d^{6}. If there are infinitely many solutions then for suitable r, s ∈ ℕ we have an identity

G_{sn+v_{0}}(P (X)) = ηξ^{n}G_{rn+u_{0}}(X), n ∈ ℕ, |r| = |s|degP > 0,

for suitable ξ, η ∈ K^{∗}, and two cases may occur, which he calls the “cyclic” (which denotes essentially the case G_{n}(X) = X^{n}, P (X) = X^{p}) and the “Chebyshev” case (which is essentially the example from the motivation, i.e. G_{n}(X) = T_{n}(X), P (X) = T_{p}(X)). More precisely we have: Cyclic case: P is of the form λ′ ∘ X^{p} ∘ λ for suitable λ, λ′ ∈ PGL_{2}(K). Also,

the α_{i} are in K(X), of the form c_{i}X^{δ_{i}} ∘ λ, for integers δ_{i} and c_{i} ∈ K, Chebyshev case: P (X) = λ′ ∘ T_{p} ∘ λ, λ, λ′ as above. The α_{i} are quadratic

over K(X) and of the form c_{i}(X ± \sqrt{X^{2} − 1})^{δ_{i}} ∘ λ.

Our aim is to generalize this result to the equation

(6)  G_{n}(x) = c G_{m}(y),

where c = c(m, n) ∈ K^{∗} may vary with m, n and where x, y are algebraically dependent, i.e. a relation Q(x, y) = 0 holds for some polynomial Q(X, Y) ∈ K[X, Y]. Moreover, we want to consider arbitrary linear recurring sequences (G_{n}(X))_{n=0}^{∞} (and not only simple linear recurrences as before). This equation can be understood as an identity in K[X, Y]/(Q(X, Y)), which denotes the residue class ring of the curve Q(x, y) = 0. Using the ideas introduced in [15], we want to give necessary conditions under which the more general problem has at most finitely many solutions.

Observe that we may assume without loss of generality that Q(X, Y) is absolutely irreducible and we will assume this for the rest of the paper.

2. Results

Before we state our results, let us start with a small discussion about the polynomial Q(X, Y), which is assumed to be absolutely irreducible. We can also assume that the leading coefficient of Y in Q(X, Y) belongs to K^{∗}, or equivalently that y is integral over K(x). Otherwise, there exists a valuation ν in the function field K(x, y), which is a pole of y. But this implies by our equation G_{n}(x) = c G_{m}(y) that

0 ≤ ν(G_{n}(x)) = ν(G_{m}(y)) ≤ ν(y) < 0,

which is a contradiction. This argument is only true if G_{n}(x) ∉ K, which we may assume if m, n are large enough (cf. [7, Corollary 3]). Observe that clearly the G_{n}(x) are integral (they are polynomials). Because of symmetry, we can also assume that x is integral over K(y) and therefore that the leading coefficient of X in Q(X, Y) does not depend on Y. Therefore, we have

Q(X, Y) = Y^{deg Q_{Y}} + q_{1}(X)Y^{deg Q_{Y} −1} + … + q′_{r}X^{deg Q_{X}} + q_{r}(X),

with q′_{r} ∈ K^{∗}, q_{i}(X) ∈ K[X], i = 1, …, r and deg q_{r}(X) < deg Q_{X} =: r.

We do not immediately start with our special case: first we study the general situation of intersections of two linear recurrences defined over a function field. The following proposition is a generalization of [15, Corollary 2] to the case of arbitrary (also non-simple) linear recurring sequences G_{n} and H_{n} given by

G_{n} = C_{1}(n)α_{1}^{n} + C_{2}(n)α_{2}^{n} + … + C_{p}(n)α_{p}^{n},
H_{n} = D_{1}(n)β_{1}^{n} + D_{2}(n)β_{2}^{n} + … + D_{q}(n)β_{q}^{n},

where α_{i}, β_{j} ∈ L^{∗} and 0 ≠ C_{i}, D_{i} ∈ L[X] and L is a function field in one variable over K, and which is therefore of interest on its own.

Theorem 1. Assume that no α_{i} or β_{j} and no ratio α_{i}/α_{j} or β_{i}/β_{j}, i ≠ j lies in K^{∗}. Then the equation G_{n} = c H_{m}, c = c(n, m) ∈ K^{∗} has at most

C(ord G_{n}, ord H_{n}) := 9d^{4}(3d^{2} + e^{e^{e^{20d}}} + rd^{2})

solutions (m, n) ∈ ℤ^{2}, where d = max{ord G_{n}, ord H_{n}} and r is the rank of the multiplicative group generated by the α_{i} and β_{j}, unless there are integers n_{0}, m_{0}, r, s, with rs ≠ 0, elements ξ, η ∈ K^{∗} and polynomials 0 ≠ P, Q ∈ K[X] such that the identity

G_{n_{0}+rm} = \frac{P (m)}{Q(m)}ηξ^{m}H_{m_{0}+sm}

holds for m ∈ ℤ.

Moreover, in this case we have that there exist S_{1}, …, S_{p} ∈ L[X] such that

C_{i}(n_{0} + rX) = ηα_{i}^{−n_{0}}P (X)S_{i}(X) and D_{π(i)}(m_{0} + sX) = β_{π(i)}^{−m_{0}}Q(X)S_{i}(X),

and for the corresponding roots α_{i}^{r}/β_{π(i)}^{s} ∈ K for i = 1, …, p = q and where π is a permutation of the set {1, …, p}.

The proof of this result follows the line of proof from [15, Corollary 2] and uses a result due to Shorey and Tijdeman (see [13, pp. 84-85] and [4, Lemma 3]). Some more remarks are in order.

Remark 1. First of all, it is quite clear that there can exist infinitely many solutions and that the statement about the polynomials P, Q is necessary. Because, if we assume that

G_{n} = P (n)S_{n}, H_{n} = Q(n)S_{n},

where P, Q ∈ K[X] and (S_{n})_{n=0}^{∞} is a linear recurring sequences defined over L, then we have G_{n} = c H_{n} with c = \frac{P (n)}{Q(n)} for all n ∈ ℤ.

Remark 2. We want to mention that such a conclusion also appears in a similar context about arbitrary (non-simple) linear recurring sequences. Namely in [2], Corvaja and Zannier proved that if G_{n}/H_{n} is an integer for infinitely many n, then there exists a polynomial P such that P (n)G_{n}/H_{n} is a linear recurring sequence for all n in an arithmetic progression.

Remark 3. If we are interested in solutions of the equation G_{n} = H_{m}, then infinitely many solutions can come only from an identity of the form G_{n_{0}+rm} = H_{m_{0}+sm} for all m ∈ ℤ, which means that

C_{i}(n_{0} + rX)α_{i}^{n_{0}} = ηD_{π(i)}(m_{0} + sX)β_{π(i)}^{m_{0}}, η ∈ K and α_{i}^{r}/β_{π(i)}^{s} ∈ K

for i = 1, …, p = q and where π is permutation of {1, …, p}.

Remark 4. We mention that the largest part of the upper bound C (the last two summands in the brackets) comes from the fact that the problem reduces to estimate the number of zeroes of a linear recurring sequence of the form P (n) = α^{n}Q(n), where α ∈ K and P (X), Q(X) ∈ K[X]. Of course this bound can be considerably improved if K = ℝ or if K is an algebraic number field (in this case the upper bound will also depend on the degree of the number field). In the general case however, no better upper bound than the general one (cf. [11, 12]) is known to the authors.

Now, we are ready to come to our special case, where G_{n} = G_{n}(x) and H_{n} = G_{n}(y). From the above Theorem it follows at once that either equation (6) has at most C(ord G_{n}, ord G_{n}) many solutions or an identity of the above type must hold. We investigate the latter case in this more special situation and we prove the following theorem.

Theorem 2. Assume that the d-th order (d ≥ 1) linear recurring sequence (G_{n}(X))_{n=0}^{∞} and the irreducible polynomial Q(X, Y) ∈ K[X, Y] satisfy the following conditions:

(i) None of the α_{i} and the ratios α_{i}/α_{j}, i ≠ j is an element of K^{∗}, (ii) deg C_{i} + 1 is equal to the multiplicity of α_{i} for all i = 1, …, r, and (iii) the set of zeros of the polynomial A_{0}(X) is not equal to that of

Res_{Y} (A_{0}(Y), Q(X, Y)).

Then there are at most C̃(ord G_{n}) pairs (m, n) ∈ ℤ^{2} for which equation (6) holds, where

C̃(d) := 9d^{4}(3d^{2} + e^{e^{e^{20d}}} + rd^{2})

and where r is the rank of the multiplicative group generated by the α_{i}.

As usual Res_{Y} (f, g) denotes the resultant of the two polynomials f, g with respect to Y.

The question now is the following: do there occur infinite families of solutions other then those in the cyclic and Chebyschev case from above, when we consider curves Q(x, y) = 0, which are not of the form y = P (x)?

Remark 5. First of all, it is clear that additional infinite families of solutions may appear. For example we have for

Q(x, y) = acx^{m} − ay^{m} − b(1 − c) = 0

with a, b, c ∈ K, m ≥ 3 and P (X) = aX^{m}+b that P (y) = c P (x). Therefore, we get for G_{n}(x) = P (x)^{n}, n ∈ ℤ that

G_{n}(y) = P (y)^{n} = (cP (x))^{n} = c^{n}P (x)^{n} = c^{n}G_{n}(x)

for all n ∈ ℤ. By [14, VI.3.3. Example, page 197] the genus of Q(x, y) = 0 is g = \frac{(m−1)(m−2)}{2} > 0. This example shows that at least in the case of positive genus also other infinite families may occur.

Remark 6. Observe that condition (ii) is not too restricitive. It just means that the recurrence uses its “full” power and can be assured by assuming that d is the minimal length of a recurrence with is satisfied by (G_{n}(X))_{n=0}^{∞}.

Remark 7. We may mention that condition (iii) also naturally appears in the context of the conditions given in our previous papers (see [8, 6, 9]). Namely, it is easy to see that we have

Res_{Y} (A_{0}(Y), Q(X, Y)) = (lcA_{0})^{deg Q_{Y}} X^{deg Q_{X}+deg A_{0}} + …,

where lcA_{0} denotes the leading coefficient of A_{0}. If we additionally assume that deg_{X} Q ≥ 2, we therefore have a valuation ν with ν(D(y)) > ν(D(x)), which was the main point in our previous considerations.

We mention that from the proof we see that we must exclude that A_{0}^{r}(y) = cA_{0}(x)^{s} for some r, s ∈ ℕ, c ∈ K^{∗}. Whenever, we can find

Q(X, Y) | A_{0}(Y)^{r} − cA_{0}(X)^{s},

we have other infinite families as described above (observe that the example before was constructed with the trivial case Q(X, Y) = A_{0}(Y)−cA_{0}(X)^{s}). It follows by Schinzel (see [10, page 58]) that if A_{0}(X) is indecomposable over K, which means that if A_{0}(X) = F_{1}(F_{2}(X)), F_{1}, F_{2} ∈ K[X] then deg F_{1} = 1 or deg F_{2} = 1, and deg A_{0} > 31, then A_{0}(Y)−cA_{0}(X)^{s} is irreducible over K. We conjecture that F (X, Y) = A_{0}(Y) − cA_{0}(X)^{s} with A_{0} indecomposable (and it is clear that this is needed) and A_{0}(y) ≠ B(y)^{t} or −4B(y)^{4} is always irreducible. Schinzel mentioned to us that this conjecture - if true - lies deeper than Capelli’s theorem (e.g. see [10, Theorem 19, page 92]), since it depends on the characteristic of K while Capelli’s theorem does not.

Remark 8. The motivation to look at this generalisation is the following: if it would be possible to prove that G_{n}(x) = c G_{m}(y) with Q(x, y) = 0 has no solution unless we have a trivial infinite family, then it would be possible to handle the Diophantine equation G_{n}(X) = G_{m}(Y) in integers X, Y by the method of Bilu and Tichy [1].

3. Proof of Theorem 1

We start by rewriting our equation G_{n} = c H_{m} as

G_{n} − c H_{m} = ∑_{i=1}^{p} C_{i}(n)α_{i}^{n}1^{m} − ∑_{i=1}^{q} cD_{i}(n)1^{n}β_{i}^{m} = 0.

We define vectors A_{i} = (α_{i}, 1) ∈ (L^{∗})^{2} for i = 1, …, p, A_{p+i} = (1, β_{i}) ∈ (L^{∗})^{2} for i = 1, …, q and polynomials P_{i} = C_{i}, i = 1, …, p, P_{p+i} = D_{i}, i = 1, …, q, respectively.

Now we apply the following theorem due to Zannier (see [15, Theorem 1] and also [15, Definition 1]):

Lemma 3. Let A_{1}, …, A_{h} ∈ (L^{∗})^{r} and let P_{1}, …, P_{h} ∈ L[X_{1}, …, X_{r}] = L[X] satisfy deg P_{i} ≤ d_{i}. Then the set

S = {m ∈ ℤ^{r} : P_{i}(m)A_{i}^{m}, i = 1, …, h are linearly independent over K},

(here for A = (α_{1}, …, α_{r}) we define A^{m} = α_{1}^{m_{1}} ⋯ α_{r}^{m_{r}}) may be expressed as a union of no more than

(d_{1} + … + d_{h} + \binom{h}{2})^{r}

classes, where we say that S ⊂ ℤ^{r} is a class relative to a nonempty subset B of {1, …, h}, if

(i) for every m ∈ S the elements P_{i}(m)A_{i}^{m}, i ∈ B are linearly independent over K and

(ii) for some m_{0} ∈ S the set S is made up by all m satisfying (i) and such that for i, j ∈ B we have (A_{i}A_{j}^{−1})^{m−m_{0}} ∈ K^{∗}.

Now, we get by applying Lemma 3 that all solutions (m, n) ∈ ℤ^{2} of our equation are contained in at most

(ord G_{n} + ord H_{n} + \binom{p + q}{2})^{2} ≤ (3 max\{ord G_{n}, ord H_{n}\}^{2})^{2}

classes (for a definition of classes see Lemma 3 or [15, Definition 2]).

We are going to estimate the number of solutions in each class Ω, corresponding to the subset B = B_{Ω} ⊂ {1, …, p + q}. As in the proof of [15, Corollary 2] it is easy to see by [15, Corollary 1(b)] that there are at most max\{ord G_{n}, ord H_{n}\} + \binom{p+q}{2} solutions in every class containing distinct integers i, j in [1, p] or [p + 1, p + q], respectively, having C_{1}(n) ⋯ C_{p}(n) ≠ 0 or D_{1}(n) ⋯ D_{q}(n) ≠ 0, respectively. Since these cases appear for at most max{ord G_{n}, ord H_{n}} many n, we get that the number of solutions is bounded by

2 max\{ord G_{n}, ord H_{n}\} + \binom{p + q}{2} ≤ 3 max\{ord G_{n}, ord H_{n}\}^{2}.

In the case that B contains integers i_{0}, j_{0} + p with 1 ≤ i_{0} ≤ p, 1, ≤ j_{0} ≤ q it is also plain (by the proof of [15, Corollary 2]) that the solutions in the class Ω correspond to integers m such that

(7)  G_{n_{0}+rm} = c H_{m_{0}+sm}

with integers n_{0}, m_{0}, r, s, rs ≠ 0.

In this case we first group together in a single γ^{m} two exponentials α_{i}^{rm} and β_{j}^{sm}, which are linearly dependent over K. Namely, if α_{i}^{r} = γ_{(i,j)}, β_{j}^{s} = δ_{(i,j)}γ_{(i,j)} with δ_{(i,j)} ∈ K^{∗} we have

(8)  C_{i}(n_{0} + rm)α_{i}^{n_{0}}γ_{(i,j)}^{m} − cD_{j}(m_{0} + sm)β_{j}^{m_{0}}δ_{(i,j)}^{m}γ_{(i,j)}^{m}.

Now, we write

C_{i}(n_{0} + rX)α_{i}^{n_{0}} = ∑_{l=1}^{u} ρ_{l}Q_{il}(X),

D_{j}(m_{0} + sX)β_{j}^{m_{0}} = ∑_{l=1}^{u} ρ_{l}Q̃_{jl}(X),

where the ρ_{l} ∈ L^{∗}, l = 1, …, u are linearly independent over K and the Q_{il}, Q̃_{jl} lie in K[X] for each i, j, l. Clearly this is possible for some u with,

u ≤ (p + q) max{deg C_{1}, …, deg C_{p}, deg D_{1}, …, deg D_{q}}.

Thus, (8) becomes

∑_{l=1}^{u} (Q_{il}(m) − cδ_{(i,j)}^{m}Q̃_{jl}(m)) ρ_{l}γ_{(i,j)}^{m}.

Up to now we have rewritten (7) as a K-linear combination of expressions of the from ρ_{l}γ_{i}^{m}, where all these expressions are linearly independent and where γ_{i} = γ_{(i,j)} or α_{i}, β_{j}, respectively, depending on whether they could be paired with some other term in (7) or not. We have two possible cases: those m for which all coefficients vanish and those for which not all coefficients vanish. In the latter case the elements ρ_{l}γ_{i}^{m} are linearly dependent over K, which can happen (by [15, Lemma 2]) for at most \binom{2(ord G_{n}+ord H_{n})−1}{2} many m.

In the first case all terms in G_{n_{0}+rm} must be paired with the terms in H_{m_{0}+sm}, so we have p = q and u ≤ 2ord G_{n}. Moreover, there exists a permutation π of the set {1, …, p} which pairs each α_{i} with some β_{j} = β_{π(i)} such that (7) can be rewritten as

∑_{i=1}^{p} ∑_{l=1}^{u} (Q_{il}(m) − cδ_{i}^{m}Q̃_{π(i)l}(m)) ρ_{l}γ_{i}^{m} = 0.

For simplicity we have written here γ_{i}, δ_{i} instead of γ_{(i,π(i))}, δ_{(i,π(i))}, respectively. Observe that there are at most max{ord G_{n}, ord H_{n}} many m for which C_{i}(n_{0} + rm) or D_{j}(m_{0} + sm) = 0. For all other m we have

\frac{Q_{il}(m)}{Q̃_{π(i)l}(m)}δ_{i}^{−m} = c

(recall that c here may depend on m) for all i, l or

(9)  \frac{Q_{il}(m)}{Q̃_{π(i)l}(m)} \frac{Q̃_{π(j)r}(m)}{Q_{jr}(m)} (\frac{δ_{j}}{δ_{i}} )^{m} = 1

for all i, l, j, r.

Now, we pause for a moment to cite the following result from [4, page 148].

Lemma 4. Let P ∈ \overline{ℚ}(X) be a rational function with no poles outside the disc \{z ∈ ℂ : |z| ≤ A\} and let α ∈ \overline{ℚ}. If there are infinitely many pairs of integers m, n with

m > n ≥ A, P (m)α^{m} = P (n)α^{n},

then P is constant and α is a root of unity.

We use a specialization argument to reduce our case to the above lemma. For this let U ⊂ K be a finite set consisting of all transcendental elements from the Q_{il}, Q̃_{π(i)l} and δ_{i} for all i, l, together with all possible differences and all multiplicative inverses of these elements. Then by [5, Lemma 3.1] there exists a ring homomorphism φ : \overline{ℚ}[U] ⟶ \overline{ℚ} whose restriction to \overline{ℚ} is the identity. Applying this map to (9) leads to

(10)  \frac{φ(Q_{ij}(m))}{φ(Q̃_{π(i)j}(m))} \frac{φ(Q̃_{π(j)r}(m))}{φ(Q_{jr}(m))} (\frac{φ(δ_{j})}{φ(δ_{i})})^{m} = 1.

Now, if there are infinitely many such m, then there are infinitely many m, n such that

\frac{φ(Q_{ij}(m))}{φ(Q̃_{π(i)j}(m))} \frac{φ(Q̃_{π(j)r}(m))}{φ(Q_{jr}(m))} (\frac{φ(δ_{j})}{φ(δ_{i})})^{m} =

\frac{φ(Q_{ij}(n))}{φ(Q̃_{π(i)j}(n))} \frac{φ(Q̃_{π(j)r}(n))}{φ(Q_{jr}(n))} (\frac{φ(δ_{j})}{φ(δ_{i})})^{n} .

Therefore, max{m, n} ⟶ ∞ and the above lemma implies that φ(δ_{j}/δ_{i}) and therefore also δ_{j}/δ_{i} is a root of unity. Moreover,

\frac{Q_{il}(X)}{Q̃_{π(i)l}(X)} = \frac{Q_{ir}(X)}{Q̃_{π(i)r}(X)} and \frac{Q_{jl}(X)}{Q̃_{π(j)l}(X)} = \frac{Q_{jr}(X)}{Q̃_{π(j)r}(X)}

differ just by a constant (in fact again a root of unity) for all i ≠ j, l ≠ r (observe that the equalities follow from (10) at once). It follows that there exist polynomials P, Q ∈ K[X] such that

P (X)S′_{il}(X) = η_{i}Q_{il}(X), Q(X)S′_{il}(X) = η̃_{π(i)}Q̃_{π(i)l}(X)

for all i, l with η_{i}, η̃_{π(i)} ∈ K (independent of l) and for some polynomials S′_{il}(X). From this discussion it follows that this case can only hold for all m in the intersection of certain arithmetic progressions, which is either empty or again an arithmetic progression. Moreover, we see that in this case we have η̃_{π(i)}/η_{i} = η with η a suitable root of unity. Therefore, also the second part of the conclusion of Theorem 1 follows from this.

Further, equation (10) can have finitely many solutions in the following two cases: either φ(δ_{j})/φ(δ_{i}) is a root of unity or not. In the second case the number of m satisfying (10) can be bounded by the zero multiplicity of the underlying linear recurring sequence, hence by

exp(exp(exp(20(ord G_{n} + ord H_{n})))

by [11, 12], since the degrees of the polynomials are bounded by the order of the recurrences. On the other hand, if φ(δ_{j})/φ(δ_{i}) is a root of unity of order ℓ say, then in the ℓ arithmetic progressions m = kℓ + r, 0 ≤ r ≤ ℓ − 1, we can bound the number of m’s by the degrees of Q_{il}(X)Q̃_{jr}(X) and Q̃_{il}(X)Q_{jr}(X), respectively. Therefore, we can bound the number of solutions coming from this case by the rank of the multiplicative group generated by α_{1}, …, α_{p}, β_{1}, …, β_{p}, which is an upper bound for ℓ, times ord G_{n} + ord H_{n}.

Altogether, we see that there are at most C(ord G_{n}, ord H_{n}) solutions, which do not come from a trivial relation, which finishes the proof. □

4. Proof of Theorem 2

We already know that we have to study the equation

(11)  G_{n_{0}+mr}(x) = \frac{P (m)}{Q(m)}ηξ^{m}G_{m_{0}+ms}(y)

with ξ, η ∈ K^{∗}, P (X), Q(X) ∈ K[X] and with integers n_{0}, m_{0}, r, s, rs ≠ 0, which is an identity in the function field K(x, y). Moreover, we have

G_{n}(x) = C_{1}(n)α_{1}^{n} + … + C_{p}(n)α_{p}^{n},
G_{n}(y) = D_{1}(n)β_{1}^{n} + … + D_{p}(n)β_{p}^{n},

where α_{i} are the zeros of G(x, T) and β_{j} are the zeros of G(y, T), respectively. Obviously, the field L_{0} := K(x, α_{1}, …, α_{p}) and L_{1} := K(y, β_{1}, …, β_{p}) are isomorphic over K and we denote the isomorphism (which sends x ↦ y and α_{i} ↦ β_{i}) by ψ : L_{0} → L_{1}.

From Theorem 1 we know that there are polynomials S_{1}(X), …, S_{p}(X) and a permutation π of {1, …, p} such that C_{i}(n_{0}+rX) = ηα_{i}^{−n_{0}}P (X)S_{i}(X), D_{π(i)}(m_{0} +sX) = β_{π(i)}^{−m_{0}}Q(X)S_{i}(X) and α_{i}^{r}/β_{π(i)}^{s} ∈ K for i = 1, …, p. Since by the above isomorphism ψ, we have that α_{i} and β_{i} have the same multiplicity and therefore we have deg C_{i} = deg D_{i} for all i = 1, …, p, it follows that

deg S_{π(i)} = deg S_{i} + deg Q − deg P

for all i = 1, …, p. This implies

deg S_{π^{k}(i)} = deg S_{i} + k(deg Q − deg P)

for every k ∈ ℕ, where π^{k} denotes as usual the k-th iterate of the map π. Let ℓ be the order of π. Then, we get deg S_{i} = deg S_{i} + ℓ(deg Q − deg P) and therefore deg Q = deg P. This means that deg C_{i} = deg D_{π(i)} and by condition (ii) that α_{i} and β_{π(i)} have the same multiplicity as roots of the characteristic polynomial G(x, T) and G(y, T), respectively.

The proof of Theorem 2 now follows easily from what we have proved up to now. Namely, by assuming that our equation has infinitely many solutions we have that the characteristic roots of G_{n}(x) and G_{n}(y) satisfy

α_{i}^{r} = cβ_{π(i)}^{s},

where π is a permutation of the set {1, …, p} and c ∈ K^{∗} (here c may depend on i). Moreover, the multiplicities of α_{i} and β_{π(i)} are the same. By multiplying all these relations according the multiplicities, we therefore get

A_{0}(x)^{r} = ∏_{i=1}^{p} ∏_{j=1}^{deg C_{i}+1} α_{i}^{r} = ∏_{i=1}^{p} ∏_{j=1}^{deg C_{i}+1} cβ_{π(i)}^{s}

= c̃(∏_{i=1}^{p} ∏_{j=1}^{deg D_{π(i)}} β_{π(i)})^{s} = c̃A_{0}(y)^{s},

where A_{0} is the constant polynomial in the linear recurring equation. But now, condition (iii) of our assumptions excludes that this equation can hold. Therefore, we obtain a contradiction, which shows the finiteness of the number of solutions in this case. □

References

1. Yu. Bilu and R. F. Tichy, The Diophantine equation f(x) = g(y), Acta Arith. 95 (2000), 261–288.

2. P. Corvaja and U. Zannier, Finiteness of integral values for the ratio of two linear recurrences, Invent. Math. 149 (2002), 431–451.

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

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

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

6. C. Fuchs, On the equation G_{n}(x) = G_{m}(P (x)) for third order linear recurring sequences, Port. Math. (N.S.) 61 (2004), 1–24.

7. C. Fuchs and A. Pethő, Effective bounds for the zeros of linear recurrences in function fields, J. Théor. Nombres Bordeaux, to appear (Preprint: http://finanz.math.tugraz.ac.at/∼fuchs/eblrff3.pdf).

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

9. C. Fuchs, A. Pethő and R. F. Tichy, On the Diophantine equation G_{n}(x) = G_{m}(P (x)): Higher-order recurrences, Trans. Amer. Math. Soc. 355 (2003), 4657-4681.

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

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

12. W. M. Schmidt, Zeros of linear recurrence sequences, Publ. Math. Debrecen 56 (2000), 609–630.

13. T. N. Shorey and R. Tijdeman, Exponential Diophantine Equations, Cambridge, Univ. Press, 1986.

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

15. U. Zannier, On the integer solutions of exponential equations in function fields, Ann. Inst. Fourier (Grenoble), to appear.