ON THE DIOPHANTINE EQUATION G_{n}(x) = G_{m}(P (x)) FOR THIRD ORDER LINEAR RECURRING SEQUENCES^{∗}

CLEMENS FUCHS

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

G_{n+3}(x) = a(x)G_{n+2}(x) + b(x)G_{n+1}(x) + c(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^{24}) 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. [8]). This paper is a continuation of the joint work of the author with A. Pethő and R. F. Tichy on this equation in the case of second order linear recurring sequences (cf. [9]).

2000 Mathematics Subject Classification: 11D45,11D04,11D61,11B37. Keywords: Diophantine equations, ternary linear recurring sequences, S-unit equations.

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 a, b, c, G_{0}, G_{1}, G_{2} ∈ K[x] and let the sequence of polynomials (G_{n}(x))_{n=0}^{∞} be defined by the third order linear recurring sequence

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

By α_{1}(x), α_{2}(x), α_{3}(x) we denote the roots of the corresponding characteristic polynomial

(2)  T^{3} − a(x)T^{2} − b(x)T − c(x).

Setting S = T − \frac{1}{3}a(x) the characteristic polynomial becomes

S^{3} − p(x)S − q(x),

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

MAT.

where

p(x) = \frac{1}{3}a(x)^{2} + b(x), q(x) = \frac{2}{27}a(x)^{3} + \frac{1}{3}a(x)b(x) + c(x).

Let

D(x) = (\frac{q(x)}{2})^{2} − (\frac{p(x)}{3})^{3} =

= \frac{1}{27}a(x)^{3}c(x) − \frac{1}{108}a(x)^{2}b(x)^{2} + \frac{1}{6}a(x)b(x)c(x) + \frac{1}{4}c(x)^{2} − \frac{1}{27}b(x)^{3}.

Moreover, let

u(x) = \sqrt[3]{\frac{q(x)}{2} + \sqrt{D(x)}}, v(x) = \sqrt[3]{\frac{q(x)}{2} − \sqrt{D(x)}}.

Then we have by Cardano’s formulae

α_{1}(x) = u(x) + v(x) + \frac{1}{3}a(x), (3)

α_{2}(x) = −\frac{u(x) + v(x)}{2} + i\sqrt{3}\frac{u(x) − v(x)}{2} + \frac{1}{3}a(x) and (4)

α_{3}(x) = −\frac{u(x) + v(x)}{2} − i\sqrt{3}\frac{u(x) − v(x)}{2} + \frac{1}{3}a(x). (5)

We will always assume that the sequence (G_{n}(x))_{n=0}^{∞} is simple which means D(x) ≠ 0. Then, for n ≥ 0

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

where

g_{1}(x), g_{2}(x), g_{3}(x) ∈ K(i\sqrt{3})(x, \sqrt{D(x)}, u(x), v(x)).

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

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

(7)  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 (7) holds. From the Theorem of Skolem-Mahler-Lech [10] it follows that N(s(x)) is finite for every s(x) provided that the sequence is nondegenerate and that also α_{1}(x), α_{2}(x), α_{3}(x) are not equal to a root of unity. Evertse, Schlickewei and Schmidt [8] proved that

N(s(x)) ≤ exp(18^{9})

THE EQUATION G_{n}(x) = G_{m}(P (x)) FOR THIRD ORDER RECURRENCES 3

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 can say even more for the zero multiplicity, i.e. the case s(x) = 0. Beukers and Schlickewei [2] showed that

(8)  N(0) ≤ 61.

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

Recently, Pethő, Tichy and the author used new developments on Sunit equations over fields of characteristic 0 due to Evertse, Schlickewei and Schmidt (cf. [8]) to handle the equation G_{n}(x) = G_{m}(P (x)) for sequences (G_{n}(x))_{n=0}^{∞} of polynomials satisfying a second order linear recurring sequence. Their 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 exp(10^{18}) pairs of integers (n, m) with n, m ≥ 0 with n ≠ m such that

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

holds. Furthermore, they showed a second result in their 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 exp(10^{18}) pairs of integers (n, m) with n, m ≥ 0 such that

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

holds.

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 at least some conditions are needed to exclude this case.

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

2. General Results

Our first main result is a suitable analog of Theorem 1 in [9] for the number of solutions of

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

for third order linear recurring sequence (G_{n}(x))_{n=0}^{∞}.

Theorem 1. Let a, b, c, G_{0}, G_{1}, G_{2}, P ∈ K[x], deg P ≥ 1 and (G_{n}(x))_{n=0}^{∞} be defined as above. 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 exp(10^{24}) pairs of integers (n, m) with n, m ≥ 0 with n ≠ m such that

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

holds.

Remark 1. We can also assume that

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

instead of the conditions concerning the initial polynomials of the recurrence in the above theorem.

The case a(x) = 0 is excluded by the conditions in Theorem 1. This special case is handled in the following theorem.

Theorem 2. Let b, c, G_{0}, G_{1}, G_{2}, P ∈ K[x], deg P ≥ 1 and (G_{n}(x))_{n=0}^{∞} be defined by

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

Assume that the following conditions are satisfied: 3 deg b > 2 deg c ≥ 0 and

deg G_{2} > deg G_{1} + 2 deg b ≥ 0, and
deg G_{1} > deg G_{0} + 2 deg b − deg c.

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

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

holds.

Remark 2. Observe that the conditions in this special case are quite similar to those for second order linear recurring sequences proved in [9] and mentioned in the introduction.

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

Theorem 3. Let a, b, c, G_{0}, G_{1}, G_{2}, P ∈ K[x] and (G_{n}(x))_{n=0}^{∞} be defined as above. 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. Then there are at most exp(10^{24}) pairs of integers (n, m) with n, m ≥ 0 such that

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

holds.

Remark 3. The reason for this different kind of assumptions lie in the fact that the infinite valuation in the rational function field K(x) leads to degree assumptions, whereas by looking at finite valuations one gets divisibility conditions as in the above theorem.

In this case a(x) = 0 is included in the above theorem. Let us mention it as a corollary.

Corollary 1. Let b, c, G_{0}, G_{1}, G_{2}, P ∈ K[x] and (G_{n}(x))_{n=0}^{∞} be defined by

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

Assume that (1) deg D ≠ 0, deg c ≠ 0

(2) deg P > 1,

(3) gcd(b, c) = 1,

(4) gcd(G_{2} − bG_{0}, c) = 1, and

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, where D(x) = (c(x)/2)^{2} − (b(x)/3)^{3}. Then there are at most exp(10^{24}) pairs of integers (n, m) with n, m ≥ 0 such that

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

holds.

Again we want to remark that this condition are quite similar to those obtained in the case of second order linear recurring sequences [9].

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^{∗} = K\{0} and Γ a finitely generated multiplicative subgroup of K^{∗}. A solution (x_{1}, …, x_{n}) of the so called weighted unit equation

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

is called nondegenerate if

(11)  ∑_{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 (10) has a degenerate solution then (10) has infinitely many degenerate solutions. For the nondegenerate solutions we have the following result, which is due to Evertse, Schlickewei and Schmidt [8]. First, we remark that Γ is called a finite type subgroup of ℂ^{∗} = ℂ\{0} if it has a free subgroup Γ_{0} of finite rank such that Γ/Γ_{0} is a torsion group; the rank of Γ is then defined as the rank of Γ_{0}. It is sufficient for us to state their result for finite type subgroups of ℂ^{∗} (cf. [8] and [7, Theorem 2] for the following version).

Theorem 4 (Evertse, Schlickewei and Schmidt). Let Γ be a finite type subgroup of ℂ^{∗} of rank r and α_{1}, …, α_{n} ∈ ℂ^{∗}. Then the number of nondegenerate solutions of the equation

α_{1}x_{1} + … + α_{n}x_{n} = 1 in x_{1}, …, x_{n} ∈ Γ

is at most

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

This theorem is the Main Theorem on S-unit equations over fields with characteristic 0. It is a generalization of an earlier results due to Evertse and Győry [5], Evertse [3] and van der Poorten and Schlickewei [11] on the finiteness of the number of nondegenerate solutions of (10). For a general survey on these equations and their applications we refer to Evertse, Győry, Stewart and Tijdeman [6].

In the special case n = 2 a much better result is known due to Baker [1] and to Beukers and Schlickewei (cf. [2] and [7, Theorem F]).

Theorem 5 (Beukers and Schlickewei). Let Γ be a finite type subgroup of ℂ^{∗} of rank r and a, b ∈ ℂ^{∗}. Then the equation

ax + by = 1 in x, y ∈ Γ

has at most

2^{16(r+1)}

solutions.

This result is comparable to Evertse’s upper bound 3 × 7^{4s} for the case Γ = O_{S}^{∗} the ring of S-integers, where S has cardinality s (cf. [4]).

Finally, we need some results from the theory of algebraic function fields, which can be found for example in the monograph of Stichtenoth [14].

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

4. Reduction to a system of equations

We start with a sequence of polynomials (P_{n}(x))_{n=0}^{∞} defined by (1). Then, in the sequel α_{1}(x), α_{2}(x), α_{3}(x), g_{1}(x), g_{2}(x), g_{3}(x), u(x), v(x), D(x) are always be given by (3), (4) and (5) (see introduction).

First we remark that in fact G_{n}(x) ∈ K[x] for all n ∈ ℕ where K is finitely generated over ℚ. We may take

K = ℚ(coefficients of a, b, c, G_{0}, G_{1}, G_{2}).

Let us define

F = K(x\sqrt{D(x}, \sqrt{P (x))}, u(x), u(P (x)), v(x), v(P (x))).

Clearly, F is a finitely generated extension field of ℚ. In fact F is an algebraic function field in one variable over the constant field K. Furthermore, we set

Γ = ⟨α_{1}(x), α_{2}(x), α_{3}(x), α_{1}(P (x)), α_{2}(P (x)), α_{3}(P (x))⟩_{(F^{∗},·)},

so Γ is the subgroup of the multiplicative group of F generated by the characteristic roots of (G_{n}(x))_{n=0}^{∞} and (G_{n}(P (x)))_{n=0}^{∞}.

It is obvious that Γ can be seen as a finitely generated subgroup of ℂ^{∗}, because we can embed K^{∗} into ℂ^{∗} by sending the transcendental elements which appear in the coefficients of a, b, c, G_{0}, G_{1}, G_{2} and the variable x to linearly independent transcendental elements of ℂ. Moreover, it is clear that the rank r of Γ is at most 6.

First we reduce the solvability of (9) to the solvability of seven types of systems of exponential equations in n, m.

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

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

This can be rewritten as

\frac{g_{1}(x)}{g_{3}(P (x))}x_{1} + \frac{g_{2}(x)}{g_{3}(P (x))}x_{2} + \frac{g_{3}(x)}{g_{3}(P (x))}x_{3} − \frac{g_{1}(P (x))}{g_{3}(P (x))}x_{4} − \frac{g_{2}(P (x))}{g_{3}(P (x))}x_{5} = 1

in x_{1}, …, x_{5} ∈ Γ.

According to the theorem of Evertse, Schlickewei and Schmidt (Theorem 4) we conclude that, if g_{1}(x), g_{2}(x), g_{3}(x) ≠ 0 and the following systems have only finitely many solutions (m, n) ∈ ℤ^{2} with n, m ≥ 0 which can be estimated by C say, then our original equation (9) has only finitely many solutions which can be bounded by

C + exp(30^{15} · 7).

The systems which correspond to the non-trivial vanishing subsums of the above weighted unit equation are:

\{ \begin{matrix}g_{1}(x)α_{1}(x)^{n} + g_{2}(x)α_{2}(x)^{n} + g_{3}(x)α_{3}(x)^{n} = g_{k}(P (x))α_{k}(P (x))^{m} \\ g_{i}(P (x))α_{i}(P (x))^{m} + g_{j}(P (x))α_{j}(P (x))^{m} = 0 \end{matrix} (12)

\{ \begin{matrix}g_{i}(x)α_{i}(x)^{n} + g_{j}(x)α_{j}(x)^{n} = 0 \\ g_{1}(P (x))α_{1}(P (x))^{m} + g_{2}(P (x))α_{2}(P (x))^{m}+ \\ +g_{3}(P (x))α_{3}(P (x))^{m} = g_{k}(x)α_{k}(x)^{n} \end{matrix} (13)

\{ \begin{matrix}g_{i}(x)α_{i}(x)^{n} = g_{j}(P (x))α_{j}(P (x))^{m} \\ g_{j}(x)α_{j}(x)^{n} + g_{k}(x)α_{k}(x)^{n} = g_{i}(P (x))α_{i}(P (x))^{m}+ \\ +g_{k}(P (x))α_{k}(P (x))^{m} \end{matrix} (14)

\{ \begin{matrix}g_{i}(x)α_{i}(x)^{n} = g_{i}(P (x))α_{i}(P (x))^{m} \\ g_{j}(x)α_{j}(x)^{n} + g_{k}(x)α_{k}(x)^{n} = g_{j}(P (x))α_{j}(P (x))^{m}+ \\ +g_{k}(P (x))α_{k}(P (x))^{m} \end{matrix} (15)

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

\{ \begin{matrix}g_{i}(x)α_{i}(x)^{n} + g_{j}(x)α_{j}(x)^{n} = g_{i}(P (x))α_{i}(P (x))^{m} \\ g_{j}(P (x))α_{j}(P (x))^{m} + g_{k}(P (x))α_{k}(P (x))^{m} = g_{k}(x)α_{k}(x)^{n} \end{matrix} (17)

\{ \begin{matrix}g_{i}(x)α_{i}(x)^{n} + g_{j}(x)α_{j}(x)^{n} = g_{k}(P (x))α_{k}(P (x))^{m} \\ g_{i}(P (x))α_{i}(P (x))^{m} + g_{j}(P (x))α_{j}(P (x))^{m} = g_{k}(x)α_{k}(x)^{n} \end{matrix} (18)

where i, j, k are always such that {i, j, k} = {1, 2, 3}. Now we have the following lemma.

Lemma 1. Let g_{1}(x), g_{2}(x), g_{3}(x), g_{1}(P (x)), g_{2}(P (x)), g_{3}(P (x)) ≠ 0 and assume that (G_{n}(x))_{n=0}^{∞} and (G_{n}(P (x)))_{n=0}^{∞} are nondegenerate. Then for every choice of {i, j, k} = {1, 2, 3} we have

(12) and (13) have at most 3 + exp(18^{9} · 4),

(16) has at most 3721,

(17) and (18) have at most 2^{64}

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

Proof. First observe that an equation of the type

(19)  h_{1}(x)α(x)^{n} + h_{2}(x)β(x)^{n} = 0

with h_{1}, h_{2}, α, β ∈ F^{∗} and α(x)/β(x) not equal to a root of unity has at most one solution in n ∈ ℤ. In particular, assume that we have two solutions n_{1}, n_{2}. Then we obtain

−\frac{h_{1}(x)}{h_{2}(x)} = (\frac{β(x)}{α(x)})^{n_{1}} = (\frac{β(x)}{α(x)})^{n_{2}} ,

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

Let us first look at (12) with some choice of {i, j, k} = {1, 2, 3}. The second equation is of the above type (19) and therefore it has at most one solution m ∈ ℕ. Now the first equation in this system becomes

b_{1}(x)α_{1}(x)^{n} + b_{2}(x)α_{2}(x)^{n} + b_{3}(x)α_{3}(x)^{n} = 1,

with

b_{i}(x) = \frac{g_{i}(x)}{g_{k}(P (x))α_{k}(P (x))^{m}} , i = 1, 2, 3,

which can be seen as a 3-dimensional weighted unit equation over the field F of characteristic 0 where we search for solutions in the finitely generated subgroup which is generated by α_{1}(x), α_{2}(x), α_{3}(x). By our assumptions we have b_{i}(x) ≠ 0 for i = 1, 2, 3. Moreover, each of the three non-trivial subsums vanishes for at most one n ∈ ℕ as this subsums are again of the type (19). By using Theorem 4 again, we can conclude that there are at most

3 + exp(18^{9} · 4)

pairs of solutions (n, m). The second system (13) is completely analogous.

Now for the equations in (16) we can calculate the number of solutions by using the bound for the zero multiplicity of nondegenerate third order linear recurring sequences (see introduction). Therefore the first equation has at most 61 solutions in n and the second at most 61 solutions in m. Consequently, there are at most 61 · 61 = 3721 pairs (n, m) for which (16) holds.

Each of the equations in the system (17) can be seen as a 2-dimensional weighted unit equations where we are interested in solutions which lie in the group generated by the three characteristic roots which are involved in the equation. Therefore by Theorem 5 we can conclude that the first and the second equation has at most 2^{16·4} solutions. Altogether the systems has at most 2^{16·4} solutions as claimed in the lemma. □

Lemma 2. Let g_{1}(x), g_{2}(x), g_{3}(x), g_{1}(P (x)), g_{2}(P (x)), g_{3}(P (x)) ≠ 0 and assume that (G_{n}(x))_{n=0}^{∞} and (G_{n}(P (x)))_{n=0}^{∞} are nondegenerate. Then (13) and (14) have at most

1 + exp(18^{9} · 7)

solutions (n, m) ∈ ℤ^{2} with n, m ≥ 0, n ≠ m respectively, provided that none of the following systems has a solution:

\{ \begin{matrix}g_{i}(x)α_{i}(x)^{n} = g_{i}(P (x))α_{i}(P (x))^{m} \\ g_{j}(x)α_{j}(x)^{n} = g_{j}(P (x))α_{j}(P (x))^{m} \\ g_{k}(x)α_{k}(x)^{n} = g_{k}(P (x))α_{k}(P (x))^{m} \end{matrix} (20)

\{ \begin{matrix}g_{i}(x)α_{i}(x)^{n} = g_{i}(P (x))α_{i}(P (x))^{m} \\ g_{j}(x)α_{j}(x)^{n} = g_{k}(P (x))α_{k}(P (x))^{m} \\ g_{k}(x)α_{k}(x)^{n} = g_{j}(P (x))α_{j}(P (x))^{m} \end{matrix} (21)

\{ \begin{matrix}g_{i}(x)α_{i}(x)^{n} = g_{j}(P (x))α_{j}(P (x))^{m} \\ g_{j}(x)α_{j}(x)^{n} = g_{k}(P (x))α_{k}(P (x))^{m} \\ g_{k}(x)α_{k}(x)^{n} = g_{i}(P (x))α_{i}(P (x))^{m} \end{matrix} (22)

where i, j, k are such that {i, j, k} = {1, 2, 3}.

Proof. We handle only the system (13) since (14) is completely analogous. Let {i, j, k} = {1, 2, 3} be fixed. The second equation in both systems can be seen as a 3-dimensional weighted unit equation

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

According to Theorem 4 this equation has at most

exp(18^{9} · 7)

solutions in Γ for which no non-trivial subsum vanishes. But the vanishing subsums are

\{ \begin{matrix}g_{j}(x)α_{j}(x)^{n} + g_{k}(x)α_{k}(x)^{n} = 0 \\ g_{i}(P (x))α_{i}(P (x))^{m} + g_{k}(P (x))α_{k}(P (x))^{m} = 0 \end{matrix}

which has at most one pair of solutions (n, m) by the proof of Lemma 1, and the first and the last system in our assumptions, which are assumed to have no solutions in (n, m) at all. Therefore we have proved the upper bound for the number of solutions (n, m) ∈ ℤ^{2} with n, m ≥ 0, n ≠ m as claimed in the lemma. □

From this discussion we see that it suffices to prove that g_{1}(x), g_{2}(x), g_{3}(x), g_{1}(P (x)), g_{2}(P (x)), g_{3}(P (x)) ≠ 0, that α_{i}(x)/α_{j}(x) and α_{i}(P (x))/α_{j}(P (x)) is not equal to a root of unity for 1 ≤ i < j ≤ 3 and that the systems (20), (21) and (22) do not have a solution (n, m) ∈ ℤ^{2} with n, m ≥ 0, n ≠ m. We will show this for each of our theorems separately in the following sections.

5. Proof of Theorem 1

In the next lemma we calculate the order of α_{1}(x), α_{2}(x) and α_{3}(x) respectively in the function field F/K, where F and K are defined as in the previous section. Then we have:

Lemma 3. Let (G_{n}(x))_{n=0}^{∞} be a sequence of polynomials defined by (1) and assume that 3 deg a > deg c, 2 deg a > deg b and deg a+deg c > 2 deg b. Then

ord(α_{1}) = deg a, (23)

(24) ord(α_{2}) = ord(α_{3}) = \frac{1}{2}(deg c − deg a) < deg a.

Proof. First of all, observe that we have

deg q = 3 deg a and deg p = 2 deg a.

Moreover, we have by our assumptions

deg D = 3 deg a + deg c.

Therefore, we trivially have

ord(u) = ord(v) = deg a

and the leading coefficients of the Puiseux expansions of u(x) and v(x) at the absolute value which corresponds to ord are equal to 1/3 times the leading coefficient of a(x). Consequently, we have ord(α_{1}) = deg a. Now it follows from (b) and from the following equation

u(x)^{3} − v(x)^{3} = 2\sqrt{D(x)}

that

ord(u^{3} − v^{3}) = \frac{1}{2}(3 deg a + deg c).

But using

u(x)^{3} − v(x)^{3} = (u(x) − v(x)) (u(x)^{2} + u(x)v(x) + v(x)^{2})

and the observation that ord(u^{2} + uv + v^{2}) = 2 deg a, which follows again from the fact that all the summands have the same leading coefficient in their Puiseux expansion, we get

ord(u − v) = \frac{1}{2}(deg c − deg a).

We want to remark that we have

(25)  α_{1}(x)α_{2}(x)α_{3}(x) = −c(x).

Now assume that ord(α_{2}) ≠ ord(α_{3}). Furthermore, we may assume without loss of generality that ord(α_{2}) > ord(α_{3}). But then we have using (d)

ord(α_{2}) = ord(α_{2} − α_{3}) = ord(u − v) = \frac{1}{2}(deg c − deg a)

which yields by (25)

ord(α_{3}) = \frac{1}{2}(deg c − deg a) = ord(α_{2}),

a contradiction. Therefore we conclude again using (25) that

ord(α_{2}) = ord(α_{3}) = \frac{1}{2}(deg c − deg a).

This means that the proof is finished. □

It is clear that

ord(α_{1} − α_{3}) = ord(α_{1} − α_{2}) = deg a,

ord(α_{2} − α_{3}) = ord (2i\sqrt{3}\frac{u − v}{2} ) = \frac{1}{2}(deg c − deg a).

To finish our proof, we want to calculate the order of g_{1}(x), g_{2}(x) and g_{3}(x). From the initial conditions

G_{0}(x) = g_{1}(x) + g_{2}(x) + g_{3}(x),
G_{1}(x) = g_{1}(x)α_{1}(x) + g_{2}(x)α_{2}(x) + g_{3}(x)α_{3}(x),
G_{2}(x) = g_{1}(x)α_{1}(x)^{2} + g_{2}(x)α_{2}(x)^{2} + g_{3}(x)α_{3}(x)^{2},

we get

g_{1}(x)Δ(x) = G_{2}(x) (α_{3}(x) − α_{2}(x)) + G_{1}(x) (α_{2}(x)^{2} − α_{3}(x)^{2}) + (26)

+G_{0}(x)α_{2}(x)α_{3}(x) (α_{3}(x) − α_{2}(x)) ,

g_{2}(x)Δ(x) = G_{2}(x)(α_{1}(x) − α_{3}(x)) + G_{1}(x) (α_{3}(x)^{2} − α_{1}(x)^{2}) + (27)

+G_{0}(x)α_{1}(x)α_{3}(x)(α_{1}(x) − α_{3}(x)),

g_{3}(x)Δ(x) = G_{2}(x)(α_{2}(x) − α_{1}(x)) + G_{1}(x) (α_{1}(x)^{2} − α_{2}(x)^{2}) + (28)

+G_{0}(x)α_{1}(x)α_{2}(x)(α_{2}(x) − α_{1}(x)),

where

Δ(x) = α_{1}(x)α_{2}(x)(α_{2}(x) − α_{1}(x)) + α_{1}(x)α_{3}(x)(α_{1}(x) − α_{3}(x)) +

+α_{2}(x)α_{3}(x)(α_{3}(x) − α_{2}(x)) =
= −6i\sqrt{3}\sqrt{D(x)}.

In the proof of Lemma 3 we have already seen that a(x)^{3}c(x) is the dominant term in D(x). Consequently, we have

ord(Δ) = \frac{1}{2}(3 deg a + deg c).

Therefore, we can conclude

ord(g_{1}) = ord(G_{2}) + \frac{1}{2}(deg c − deg a) − \frac{1}{2}(3 deg a + deg c) =

= deg G_{2} − 2 deg a,

ord(g_{2}) = ord(g_{3}) = deg G_{2} + deg a − \frac{1}{2}(3 deg a + deg c) =

= deg G_{2} − \frac{1}{2} deg a − \frac{1}{2} deg c.

Thus, we deduce that g_{1}(x), g_{2}(x), g_{3}(x) and therefore also g_{1}(P (x)), g_{2}(P (x)), g_{3}(P (x)) are different from zero.

Next we are intended to show that α_{i}(x)/α_{j}(x) is not equal to a root of unity for 1 ≤ i < j ≤ 3. First observe that

α_{1}(x) = ζα_{2}(x) or α_{1}(x) = ζα_{2}(x)

with ζ a root of unity is impossible because of the different order. Namely this would imply

ord(α_{1}) = ord(α_{2}) or ord(α_{1}) = ord(α_{3})

respectively, a contradiction. Now assume that we have

α_{2}(x) = ζα_{3}(x)

with ζ a root of unity. Observe that the leading coefficients in the Puiseux expansion of α_{2}(x), α_{3}(x) are conjugate complex numbers. This follows from the fact that

ord(α_{2}) = ord(α_{3}) = ord(u − v)

and u(x) − v(x) is one of the summands in the definition of those characteristic roots. Thus the only possibilities are ζ = 1 or −1 which both lead to a contradiction since

ord(α_{2} − α_{3}) = \frac{1}{2}(deg c − deg a)

and α_{2}(x) + α_{3}(x) = a(x) − α_{1}(x) ≠ 0.

The proof that the sequence (G_{n}(P (x)))_{n=0}^{∞} is nondegenerate is completely analogous to the above case since we are only considering the order

14 CLEMENS FUCHS

of the elements.

It remains to show the unsolvability of (20), (21) and (22). Because of

ord(α_{2}) = ord(α_{3}) and ord(g_{2}) = ord(g_{3})

it suffices to consider the following two cases:

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

\{ \begin{matrix}g_{1}(x)α_{1}(x)^{n} = g_{2}(P (x))α_{2}(P (x))^{m} \\ g_{2}(x)α_{2}(x)^{n} = g_{1}(P (x))α_{1}(P (x))^{m} \\ g_{3}(x)α_{3}(x)^{n} = g_{3}(P (x))α_{3}(P (x))^{m} \end{matrix} (30)

Calculating orders we get deg G_{2} − 2 deg a + n deg a = (deg G_{2} − 2 deg a)(deg P + m deg a deg P)

(deg G_{2} − \frac{deg a}{2} − \frac{deg c}{2}) (1 − deg P) = (m deg P − n)\frac{deg c − deg a}{2}

or

(deg G_{2} − 2 deg a)(1 − deg P) = (m deg P − n) deg a

(2 deg G_{2} − deg a − deg c)(1 − deg P) = (m deg P − n)(deg c − deg a) This yields

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

Substituting this into the first equation leads to

(deg G_{2} − deg a)(1 − deg P) = 0,

which implies deg P = 1 and therefore n = m or deg G_{2} = deg a and therefore deg G_{1} < 0, in both cases a contradiction.

The second system leads to

deg G_{2} − 2 deg a + n deg a = (deg G_{2} − \frac{1}{2} deg a − \frac{1}{2} deg c) deg P +

+m deg P \frac{1}{2}(deg c − deg a)

deg G_{2} − \frac{1}{2} deg c − \frac{1}{2} deg a + n\frac{1}{2}(deg c − deg a) =

= (deg G_{2} − \frac{1}{2} deg a − \frac{1}{2} deg c) deg P + m deg P \frac{1}{2}(deg c − deg a) deg G_{2} − \frac{1}{2} deg c − \frac{1}{2} deg a + n\frac{1}{2}(deg c − deg a) =

= (deg G_{2} − 2 deg a) deg P + m deg a deg P,

which yields 0 ≤ \frac{1}{2}(3 deg a − deg c) = −m\frac{1}{2}(deg a + deg c) < −m deg b < 0, a contradiction.

So the proof of Theorem 1 is finished. By Lemma 1 and Lemma 2 we get by counting how often each system can appear, the following bound:

exp (30^{15} · 7)+2·3·[3 + exp (18^{9} · 4)]+3721+9·2^{64} +9·(1 + exp (18^{9} · 7))

which can be estimated by

exp(10^{24}).

This was the claim of Theorem 1. □

6. Proof of Theorem 2

First we want to mention that a(x) = 0 means that we have

p(x) = b(x), q(x) = c(x) and D(x) = \frac{1}{4}c(x)^{2} − \frac{1}{27}b^{3}.

By our assumption that 3 deg b > 2 deg c we get

ord(u) = ord(v) = \frac{1}{2} deg b

and the leading coefficients of the relevant Puiseux expansions are equal to i\sqrt{3} and −i\sqrt{3} times the square root of the leading coefficient of b(x). Therefore we can conclude

ord(u − v) = \frac{1}{2} deg b and ord(u + v) = deg c − deg b.

Thus we get

ord(α_{1}) = deg c − deg b,

ord(α_{2}) = ord(α_{3}) = \frac{1}{2} deg b,

ord(α_{1} − α_{2}) = ord(α_{1} − α_{3}) = \frac{1}{2} deg b,

ord(α_{2} − α_{3}) = \frac{1}{2} deg b

ord(α_{1} + α_{2}) = ord(α_{1} + α_{3}) = deg c − deg b,

ord(α_{2} + α_{3}) = \frac{1}{2} deg b.

Using (26), (27) and (28) we get from our assumptions concerning the degrees of the initial polynomials

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

Therefore we can conclude that g_{1}(x), g_{2}(x), g_{3}(x), g_{1}(P (x)), g_{2}(P (x)), g_{3}(P (x)) are non-zero. The proof that (G_{n}(x))_{n=0}^{∞} and (G_{n}(P (x)))_{n=0}^{∞} are nondegenerate is analogous to the proof of this fact in Theorem 1.

As in the proof of Theorem 1 it suffices to prove the unsolvability of (29) and (30). By calculating orders we get

deg G_{2} − 2 deg b + n(deg c − deg b) = (deg G_{2} − 2 deg b) deg P +
+m deg P (deg c − deg b)

deg G_{2} − 2 deg b + n\frac{deg b}{2} = (deg G_{2} − 2 deg b) deg P + m deg P \frac{deg b}{2}

This yields n = m deg P and by substituting this into one of the equations above we get deg P = 1 which implies n = m or deg G_{2} = 2 deg b from which we get deg G_{1} < 0, in both cases a contradiction. The second system (29) can be handled analogously.

By Lemma 1 and 2 the theorem follows and the proof is finished. □

7. Proof of Theorem 3

We start our proof with some useful lemmas.

Lemma 4. Let A, B, P ∈ K[x]. Then gcd(A, B) = 1 if and only if gcd(A(P), B(P)) = 1.

Proof. Let us assume that gcd(A(P), B(P)) = 1 and that gcd(A, B) > 1. Then there exists a common root of A(x) and B(x) which we denote by ξ ∈ K (observe that K is algebraically closed). Now let ζ ∈ K be a root of the polynomial P (x) − ξ with coefficients in K. Thus we have A(P (ζ)) = B(P (ζ)) = 0, contradicting our assumption. The proof of the converse can be found in [9, Lemma 4]. □

We will use the same notations as introduced in the proof of Theorem 1.

First of all we have because of deg D ≠ 0 and gcd(c, D) = 1 that c(x) ≠ 0. Therefore, from

α_{1}(x)α_{2}(x)α_{3}(x) = −c(x),

it follows that α_{1}(x), α_{2}(x), α_{3}(x) ≠ 0. Next we show that α_{1}(x), α_{2}(x), α_{3}(x) are nondegenerate. We take ξ ∈ K such that a(ξ) = 27c(ξ)^{2} − 4b(ξ)^{3} = 0. This implies that D(ξ) = 0. From this we can conclude

u(ξ) = \sqrt[3]{\frac{q(ξ)}{2}} = \sqrt{\frac{p(ξ)}{2}} = \sqrt{\frac{b(ξ)}{3}} and v(ξ) = u(ξ).

Therefore we have

α_{1}(ξ) = 2\sqrt{\frac{b(ξ)}{3}}.

On the other hand we get

α_{2}(ξ) = α_{3}(ξ) = −\sqrt{\frac{b(ξ)}{3}},

which implies that α_{1}(x) differs from α_{2}(x) and α_{3}(x) by more than a root of unity, because b(ξ) ≠ 0 by condition (3) in the theorem.

Now assume that we have

α_{2}(x) = ζα_{3}(x), ζ ∈ K.

This yields

(1 + ζ)i\sqrt{3}\frac{u(x) − v(x)}{2} = \frac{1 − ζ}{2} (u(x) + v(x)) − \frac{1 − ζ}{3} a(x).

As above we derive a contradiction unless ζ = 1. But assuming ζ = 1 yields

2i\sqrt{3}\frac{u(x) − v(x)}{2} = 0,

contradicting the fact that u(x) = v(x) ⟺ D(x) = 0.

Because of Lemma 4 we can conclude in the same way as above that the same holds for α_{1}(P (x)), α_{2}(P (x)), α_{3}(P (x)).

Next we want to proof the g_{1}(x), g_{2}(x), g_{3}(x) ≠ 0 holds. Observe that they are given by (26), (27) and (28) respectively.

First observe that for ξ ∈ K we have: Δ(ξ) = 0 ⟺ α_{2}(ξ) = α_{3}(ξ) and Δ(ξ) = 0 ⇒ α_{1}(ξ) ≠ α_{2}(ξ), α_{3}(ξ). We will need

g_{1}(x) = \frac{α_{3}(x) − α_{2}(x)}{Δ(x)}(G_{2}(x) − G_{1}(x)[a(x) − α_{1}(x)] + G_{0}(x)α_{2}(x)α_{3}(x))

and

G_{2}(x) − G_{1}(x)[a(x) − α_{1}(x)] + G_{0}(x)α_{2}(x)α_{3}(x) =

= G_{2}(x) − a(x)G_{1}(x) + \frac{a(x)}{3}G_{1}(x) + G_{1}(x)[u(x) + v(x)] + G_{0}(x)[u(x)^{2}

+v(x)^{2}] − G_{0}(x)\frac{a(x)}{3}[u(x) + v(x)] + G_{0}(x)\frac{a(x)^{2}}{9} − G_{0}(x)u(x)v(x).

Observe that 3u(x)v(x) = p(x). Let ξ ∈ K with q(ξ) = 0. This implies

u(ξ) = \frac{i}{\sqrt{3}}\sqrt{p(ξ)} and v(ξ) = −\frac{i}{\sqrt{3}}\sqrt{p(ξ)}

and therefore u(ξ) + v(ξ) = 0. Because of the above equation and condition (4) from the theorem we get

g_{1}(ξ) ≠ 0.

To handle g_{2}(x), g_{3}(x) we prove the following lemma which will also enable us to calculate ν(g_{2}) and ν(g_{2}) where ν extends ν_{ξ} to F for some ξ ∈ K.

Lemma 5. Let (G_{n}(x))_{n=0}^{∞} be a sequence of polynomials defined by (1) and assume that 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. Let ξ ∈ K be a common root of a(x) and D(x) and let ν be an extension of ν_{ξ} to F. Then ν(g_{1}Δ) = ν(g_{2}Δ) = 0.

Proof. Since D(ξ) = 0 we have α_{2}(ξ) = α_{3}(ξ) and by equation (27) we have to show that

ν(G_{2} − G_{1}(a − α_{2}) + G_{0}α_{1}α_{3}) = 0.

Observe that it is clear that we have ≥ 0 since the α_{i}(x), i = 1, 2, 3 are integral over K[x] and the integral closure is a ring. Therefore it suffices to show that

(G_{2} − G_{1}(a − α_{2}) + G_{0}α_{1}α_{3})(ξ) ≠ 0,

but this follows from our condition: We have

(G_{2} + G_{1}α_{2} + G_{0}α_{1}α_{3})(ξ) = (G_{2} − \frac{1}{3}G_{1}\sqrt{3b} − \frac{2}{3}bG_{0}) (ξ).

Assume this value to be zero. Then

[(G_{2} − \frac{2}{3}bG_{0})^{2} − \frac{1}{3}bG_{1}^{2}](ξ) = 0,

contradicting the assumption in our Lemma.

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

We are intended to prove that the systems of equations (20), (21) and (22) are not solvable. Observe that each of this systems contain at least one equation of the form

(31)  g_{i}(x)α_{i}(x)^{n} = g_{k}(P (x))α_{k}(P (x))^{m}

with i, k ∈ {2, 3} not necessarily different. We will show that already this equation cannot have a solution.

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

ν_{ξ}(D(P)) > ν_{ξ}(D) ≥ 0

which is also a zero of a(P (x)) which means ν_{ξ}(a(P)) > 0. This implies that there is a finite valuation ν on F such that by Lemma 5

ν(g_{1}(P)) = ν(g_{2}(P)) = −ν(Δ(P)) = −\frac{1}{2}ν(D(P)).

Moreover, we can conclude that ν(α_{2}(P)) = ν(α_{3}(P)) = 0, because otherwise we would get a contradiction to condition (2) of our theorem.

Thus equation (31) implies

ν(g_{i}) + nν(α_{i}) = ν(g_{k}(P)),

which yields

nν(α_{i}) = ν(g_{k}(P)) − ν(g_{i}) ≤ −ν(Δ(P)) + ν(Δ) < 0,

hence (31) has no solution in n, if ν(α_{i}) ≥ 0 and at most one, if ν(α_{i}) < 0, which is impossible since α_{1}(x), α_{2}(x), α_{3}(x) are integral over K[x], as they are zeros of the monic equation T^{3} − a(x)T^{2} − b(x)T − c(x) = 0 with coefficients in K[x]. Therefore, we have ν(α_{i}) ≥ 0. Consequently (31) has no solution.

So, we have shown that (20), (21) and (22) have no solutions (n, m) ∈ ℤ^{2} with n, m ≥ 0, n ≠ m. It is clear that we get the same bound as in Theorem 1. □

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] J.H. Evertse, On sums of S-units and linear recurrences, Comp. Math. 53 (1984), 225-244.

[4] J.H. Evertse, On equations in S-units and the Thue-Mahler equation, Invent. Math. 75 (1984), 561-584.

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

[6] 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.

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

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

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

[10] C. Lech, A note on recurring series, Ark. Math. 2 (1953), 417-421.

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

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

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

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

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