EFFECTIVE BOUNDS FOR THE ZEROS OF LINEAR RECURRENCES IN FUNCTION FIELDS

CLEMENS FUCHS^{∗} AND ATTILA PETHŐ^{‡}

Abstract. In this paper we use the generalisation of Mason’s inequality due to Brownawell and Masser (cf. [8]) to prove effective upper bounds for the zeros of a linear recurring sequence defined over a field of functions in one variable.

Moreover, we study similar problems in this context as the equation G_{n}(x) = G_{m}(P (x)), (m, n) ∈ ℕ^{2}, where (G_{n}(x)) is a linear recurring sequence of polynomials and P (x) is a fixed polynomial. This problem was studied earlier in [14, 15, 16, 17, 32].

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

Key words and phrases. linear dependence, Diophantine equations, linear recurring sequences, effective finiteness results

1. Introduction

Let K be an algebraically closed field of zero characteristic and K be a function field in one variable over K.

Let A_{0}, …, A_{d−1}, G_{0}, …, G_{d−1} ∈ K and (G_{n})_{n=0}^{∞} be a sequence defined by the d-th order linear recurring relation

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

Denote by

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

the characteristic polynomial of the sequence (G_{n})_{n=0}^{∞} and by D the discriminant of G(T). We let α_{1}, …, α_{r} denote the distinct roots of the characteristic polynomial G(T) in the splitting field L of G(T). So, L is a finite algebraic extension of K and therefore again a function field over K of genus g, say. It is well known that (G_{n})_{n=0}^{∞} has a nice “analytic” representation. More precisely, there exist polynomials P_{1}(T), …, P_{r}(T) ∈ L[T] such that

(2)  G_{n} = P_{1}(n)α_{1}^{n} + … + P_{r}(n)α_{r}^{n},

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.

holds for all n ≥ 0. Assuming that G(T) has no multiple roots, i.e. D ≠ 0, we have that the functions P_{i}(T) = π_{i} are all constant for i = 1, …, r = d. Then (G_{n})_{n=0}^{∞} is called a simple recurring sequence.

Many diophantine equations involving the recurrence (G_{n})_{n=0}^{∞} were studied previously. One of the most well-known problems is to estimate the number of zeros appearing in such a sequence or more generally to estimate the number of solutions of the following exponential-polynomial equation

(3)  G_{n} = a,

where a ∈ L is given. We denote by N(a) the number of integers n for which (3) holds (this number is called the a-multiplicity of (G_{n})). This problem has been widely investigated (not only in the classical case of number fields as base field) (cf. [2, 4, 7, 11, 3, 12, 26, 22, 23, 25, 27, 29]). For recurrences over function fields similar results are available (see [5, 28]).

Recently, Zannier [32] considered exponential-polynomial equations in several variables and he obtained upper bounds which substantially improve the known estimates over number fields. His results imply that for a linear recurrence sequence (G_{n}) for which no ratio α_{i}/α_{j}, i ≠ j lies in K^{∗} we have that there are at most

deg P_{1} + … + deg P_{r} + \binom{r}{2}

integers n such that G_{n} = 0 with P_{1}(n) ⋯ P_{r}(n) ≠ 0. So, altogether we have

N(0) ≤ 2(deg P_{1} + … + deg P_{r}) + \binom{r}{2}.

If we additionally assume that α_{1}, …, α_{r} are not in K^{∗}, then the same bound holds for N(a) for every a ∈ L. Moreover, for simple linear recurrences (G_{n}), (H_{m}) Zannier proved a good upper bound for the number of solutions of G_{n} = H_{m} and G_{n} = c H_{m}, c = c(n, m) ∈ K^{∗} and he classified all possible solutions. Furthermore generalising earlier results due to the authors and Tichy [14, 15, 16], Zannier gave a good upper bound for the integer solutions (m, n) of G_{n}(x) = c G_{m}(P (x)), c = c(n, m) ∈ K^{∗}, where (G_{n}(x)) is a linear recurring sequence of polynomials and P is a fixed polynomial.

However, for equations which are “truly” defined over functions fields other tools seem to give even more. In this paper we will use the Brownawell-Masser inequality to give effective upper bounds for the solutions themselves, which seems to be impossible for the classical number field case. Such results were already obtained earlier (see [20, 21]), where other problems from number theory were successfully transferred to the function field case.

The paper is organized as follows: in the next section we state and discuss our main result which will deal with K-linear dependence of certain expressions in a function field. This can be compared with the main result (Theorem 1) in [32]. In Section 3 we will discuss applications to equation (3) and we will give effective upper bounds for the solutions n of this equation. In Section 4 we will discuss applications to intersections of linear recurring sequences and we will give effective results in this case also. Section 5 is devoted to our main tool which is the Brownawell-Masser inequality. In the last three sections we will give the proofs of our results.

2. Main Result

As mentioned in the Introduction it is more convenient to deal with linear dependence of certain elements in a function field first rather than dealing directly with equations as (3).

We denote by H the usual projective height on ℙ_{n−1}(K). For a repetition of valuations ν and the height H we refer to the first paragraph of Section 5. Then, our main result is the following theorem:

Theorem 1. Let α_{1}^{(1)}, …, α_{d_{1}}^{(1)}, …, α_{1}^{(k)}, …, α_{d_{k}}^{(k)} ∈ L^{∗}, d_{1}, …, d_{k} ≥ 1 be

such that α_{i}^{(j)}/α_{l}^{(j)} ∉ K^{∗} for each j ∈ {1, …, k} with d_{j} ≥ 2 and each pair of subscripts i, l with 1 ≤ i < l ≤ d_{j}. Moreover, for every i = 1, …, d_{j}, j = 1, …, k let π_{i1}^{(j)}, …, π_{ir_{i}}^{(j)} ∈ L be r_{i} linearly independent elements over K. Put

d = ∑_{j=1}^{k} ∑_{i=1}^{d_{j}} r_{i}.

Then for every (n_{1}, …, n_{k}) ∈ ℕ^{k} such that

{π_{il}^{(j)} α_{i}^{(j)}^{n_{j}} : l = 1, …, r_{i}, i = 1, …, d_{j}, j = 1, …, k}

is linearly dependent over K, but no proper subset of this set is linearly dependent over K, we have

n_{j} ≤ C^{(j)} := C (d, g, π_{il}^{(j)}, α_{i}^{(j)}; l = 1, …, r_{i}, i = 1, …, d_{j}) ,

for all j ∈ {1, …, k} with d_{j} ≥ 2, where

C^{(j)} := max \{0, max_{\begin{matrix}(i, l) ≠ (u, v) \\ 1 ≤ i, u ≤ d_{j} \\ 1 ≤ l, v ≤ r_{i} \end{matrix}}  max_{\begin{matrix}ν with \\ ν(α_{i}^{(j)}) < ν(α_{u}^{(j)}) \end{matrix}} (\frac{−ν(π_{il}^{(j)}) + ν(π_{uv}^{(j)})}{ν(α_{i}^{(j)}) − ν(α_{u}^{(j)})}) ,

\frac{1}{max_{\begin{matrix}i ≠ u \\ 1 ≤ i, u ≤ d_{j} \end{matrix}} H (α_{i}^{(j)}, α_{u}^{(j)})} · [\frac{(d − 1)(d − 2)}{2} (( ∑_{\begin{matrix}ν with \\ ν(α_{i}^{(j)}) ≠ 0 or \\ ν(π_{il}^{(j)}) ≠ 0 \end{matrix}} 1) + 2g − 2) +

+ max_{\begin{matrix}(i, l) ≠ (u, v) \\ 1 ≤ i, u ≤ d_{j} \\ 1 ≤ l, v ≤ r_{i} \end{matrix}}  ∑_{\begin{matrix}ν with \\ ν(α_{i}^{(j)}) < ν(α_{u}^{(j)}) \end{matrix}} ν (\frac{π_{il}^{(j)}}{π_{uv}^{(j)}} )]\} ,

where the maximum is/the sums are taken over all absolute values ν of the function field L/K, respectively.

The upper bound in the theorem is quite involved. Some remarks are in order.

Remark 1. Let us remark that the above upper bound is sharp. For example, it is clear that two elements π_{1}α_{1}^{n}, π_{2}α_{2}^{n} with π_{1}, π_{2}, α_{1}, α_{2} ∈ L^{∗} and α_{1}/α_{2} ∉ K^{∗} are linearly dependent for at most one n. This n is given by

n = \frac{−ν(π_{1}) + ν(π_{2})}{ν(α_{1}) − ν(α_{2})},

for every absolute value ν where the denominator is not zero. But this value is exactly C(d, g, π_{1}, π_{2}, α_{1}, α_{2}) from Theorem 1.

Remark 2. The constants C^{(j)} (j = 1, …, k, d_{j} ≥ 2) are well-defined. Indeed, for each j under consideration there are pairs of subscripts i, l with 1 ≤ i < l ≤ d_{j}, and for each such pair we have

H (α_{i}^{(j)}, α_{l}^{(j)}) = H (\frac{α_{i}^{(j)}}{α_{l}^{(j)}} ) > 0

since α_{i}^{(j)}/α_{l}^{(j)} does not lie in K^{∗}.

Remark 3. In the special situation when the π_{il}^{(j)} are all equal to 1 the upper bound becomes much easier. Assume that d_{1}, …, d_{k} ≥ 2. In this situation we can show that if for (n_{1}, …, n_{k}) ∈ ℕ^{k} the set

{α_{1}^{(1)}^{n_{1}} , …, α_{d_{1}}^{(1)}^{n_{1}} , …, α_{1}^{(k)}^{n_{k}} , …, α_{d_{k}}^{(k)}^{n_{k}}}

is linearly dependent over K, but no proper subset is linearly dependent over K, then

max\{n_{1}, …, n_{k}\} ≤ \frac{\frac{(d − 1)(d − 2)}{2}(s + 2g − 2)}{max_{j=1,...,k} H (α_{i}^{(j)} : i = 1, …, d_{j})},

where s is the number of zeros and poles of the α_{i}^{(j)} and

d = ∑_{i=1}^{k} d_{i}.

In fact we can prove the following upper bound, which of course is no longer sharp:

Corollary 1. Let d_{1}, …, d_{k} ≥ 2. Then, in the situation of Theorem 1 we have:

max{n_{1}, …, n_{k}} ≤ C̃ :=

H (π_{il}^{(j)} : l = 1, …, r_{i}, i = 1, …, d_{j}, j = 1, …, k) +

max \{\frac{(d − 1)(d − 2)}{2}(s + 2g − 2), 0\} ,

where s is the number of zeros and poles of the π_{il}^{(j)}, α_{i}^{(j)} for l = 1, …, r_{i}, i = 1, …, d_{j}, j = 1, …, k and

d = ∑_{j=1}^{k} ∑_{i=1}^{d_{j}} r_{i}.

We also want to mention that the dependency on the coefficients π_{il}^{(j)} clearly cannot be removed as the following example shows: in the function field ℂ(x) the set

{1, x^{n}}

is linearly dependent over ℂ only for n = 0, whereas the set

{1, x^{−n_{0}}x^{n}}

for an arbitrary integer n_{0} ∈ ℕ is linearly dependent over ℂ only for n = n_{0}. This shows that depending on the coefficient the size of the (only) solution can be arbitrarily large.

Now we turn our discussion to the case of linear recurring sequences in function fields.

3. Applications to the multiplicity of linear recurring sequences

In this section we want to give effective upper bounds for the solutions of the equation G_{n} = 0 and G_{n} ∈ K, where G_{n} is a linear recurring sequence in a function field. The big unanswered question of course is whether this is possible for linear recurring sequences in number fields.

Corollary 2. Let α_{1}, …, α_{r} ∈ L^{∗} and P_{1}, …, P_{r} ∈ L[T]. Assume that for all i ≠ j no ratio α_{i}/α_{j} lies in K^{∗}. Then there exists an effectively computable constant C_{1} such that for all n ∈ ℕ with

G_{n} = P_{1}(n)α_{1}^{n} + … + P_{r}(n)α_{r}^{n} = 0

we have

n ≤ C_{1}.

Of course this upper bound depends on all data which is given. Especially, it also depends on L (for instance one has to consider those n for which P_{1}(n), …, P_{r}(n) are all 0). For the effectivity to make sense the field L must therefore be defined in such a way that each element of L can be represented by a finite string of integers. This applies also to the effective bounds appearing in the corollaries below.

Moreover, in the same way as at the end of the last section it is easy to give examples which show that the upper bound clearly depends on the polynomials P_{1}, …, P_{r}, e.g. look at

G_{n} = x^{n} − 1 = 0 and G_{n} = x^{−n_{0}}x^{n} − 1 = 0

with n_{0} ∈ ℕ.

Remark 4. In special cases it is possible to give quite a simple explicit formula for the bound C_{1}. For example assume that (G_{n}) is a simple recurring sequence of polynomials (where A_{1}, …, A_{d}, G_{0}, …, G_{d−1} ∈ K[x]) and let R = R_{d}(A_{1}, …, A_{d}, G_{0}, …, G_{d−1}) ∈ ℚ[A_{1}, …, A_{d}, G_{0}, …, G_{d−1}] be as introduced in [16, p. 4660], which was

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

Moreover, we assume that gcd(R, D) = 1, then G_{n} = 0 implies

n ≤ H(π_{1}, …, π_{d}) + d^{3d^{2}}(deg R + deg A_{0} + 1)

where D is the discriminant of G[T]. This immediately follows from Corollary 1, together with the same ideas from the proofs of [16, Lemma 6.1] and [16, Lemma 6.2].

The method of proof even gives more. The following result is also a corollary of Theorem 1.

Corollary 3. Let α_{1}, …, α_{r} ∈ L^{∗} and P_{1}, …, P_{r} ∈ L[T]. Assume that no α_{i} and no ratio α_{i}/α_{j}, i ≠ j lies in K^{∗}. Then there exists an effectively computable constant C_{2} such that for all n ∈ ℕ with

G_{n} = P_{1}(n)α_{1}^{n} + … + P_{r}(n)α_{r}^{n} ∈ K

we have

n ≤ C_{2}.

This corollary gives an effective upper bound for the solutions of the equation G_{n} = a for given a ∈ K, which is independent of a. Let us mention that we can also give effective upper bounds for the solutions of G_{n} = a for every a ∈ L by applying Corollary 2 with α_{r+1} = 1, P_{r+1}(T) = −a.

4. Intersection of linear recurring sequences

In this section we come to equations of the type G_{n} = H_{m}, where (G_{n}), (H_{m}) are linear recurring sequences in the function field L. We will always assume that the recurring sequences are simple, i.e.

G_{n} = a_{1}α_{1}^{n} + … + a_{p}α_{p}^{n},
H_{m} = b_{1}β_{1}^{m} + … + b_{q}β_{q}^{m},

with p, q ≥ 1 and a_{i}, b_{j}, α_{i}, β_{j} ∈ L^{∗} for i = 1, …, p, j = 1, …, q.

In the classical number field case such equations were investigated by Laurent [18, 19] and Schlickewei and Schmidt [24]. Quantitative results for function fields were already obtained by Zannier in [32]. He proved that there are at most \binom{p+q}{2}^{3} solutions (m, n) ∈ ℤ^{2} with G_{n} = H_{m} or G_{n} = c H_{m}, c = c(n, m) ∈ K^{∗}, unless there are infinitely many solutions coming from a trivial identity. We will give effective analogues of these results.

Corollary 4. Assume that no α_{i} or β_{j} and no ratio α_{i}/α_{j} or β_{i}/β_{j}, i ≠ j lies in K^{∗}. Then there exists an effectively computable constant C_{3} such that for all (n, m) ∈ ℕ^{2} with G_{n} = H_{m} we have

max{n, m} ≤ C_{3},

unless there are integers n_{0}, m_{0}, r, s with rs ≠ 0 such that the pairs (a_{i}α_{i}^{n_{0}}, α_{i}^{r}) coincide in some order with the pairs (b_{i}β_{i}^{m_{0}}, β_{i}^{s}). In this case we have infinitely many solutions.

It would be interesting to generalize this result to the equation

(4)  G_{n_{1}}^{(1)} + G_{n_{2}}^{(2)} + … + G_{n_{k}}^{(k)} = 0,

where G_{n}^{(1)}, …, G_{n}^{(k)} are simple linear recurring sequences in the function field L. This is interesting in view of a conjecture due to Cerlienco, Mignotte and Piras [7], which says that (in the classical number field case) there are a k and linear recurring sequences as above such that the algorithmic (i.e. effective) solvability of equation (4) in integers (n_{1}, …, n_{k}) ∈ ℕ^{k} is undecidable. The above corollary disproves this conjecture for two simple linear recurring sequences in a function field.

The next corollary is an effective version of [32, Corollary 2(b)]. We will apply it to a more special problem below.

Corollary 5. Assume that no α_{i} or β_{j} and no ratio α_{i}/α_{j} or β_{i}/β_{j}, i ≠ j lies in K^{∗}. Then there exists an effectively computable constant C_{4} such that for all (n, m) ∈ ℕ^{2} with G_{n} = c H_{m}, c = c(n, m) ∈ K^{∗} we have

max{n, m} ≤ C_{4},

unless there are integers n_{0}, m_{0}, r, s with rs ≠ 0 and elements ξ, η ∈ K^{∗} such that the pairs (a_{i}α_{i}^{n_{0}}, α_{i}^{r}) coincide in some order with the pairs (ηb_{i}β_{i}^{m_{0}}, ξβ_{i}^{s}). In this case we have infinitely many solutions.

As announced above we will apply this to a problem investigated earlier in [14, 15, 16, 32]. Let A_{0}(x), …, A_{d}(x) ∈ K[x] and let (G_{n}(x)) be a linear recurring sequence of polynomials defined by

G_{n+d}(x) = A_{d}(x)G_{n+d−1}(x) + … + A_{0}(x)G_{n}(x), n ∈ ℕ.

Assuming the corresponding characteristic polynomial has only simple roots we get

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

where a_{i} ∈ L and L is the splitting field of G(T). Furthermore, let P (x) ∈ K[x]. We study the intersection of the sequences G_{n}(x) and G_{n}(P (x)). This problem is motivated e.g. by the Chebyshev polynomials (T_{n}(x)) given by T_{n}(x) = cos(n arccos x) and which satisfy

T_{np}(x) = T_{n}(T_{p}(x)).

We have the following result which is an effective analogue of [32, Corollary 4].

Corollary 6. Suppose that deg P ≥ 2 and that no α_{i} and no ratio α_{i}/α_{j}, i ≠ j lies in K. Then there is an effectively computable constant C_{5} such that, if there are only finitely many solutions (n, m) ∈ ℕ^{2} for

G_{n}(x) = c G_{m}(P (x)), c = c(n, m) ∈ K^{∗},

then

max{n, m} ≤ C_{5}.

We remark that since this follows immediately from Corollary 5 the characterisation of the cases when the equation has infinitely many solutions stays as it was obtained by Zannier in [32]. Such solutions come from a trivial identity which essentially can appear only when either G_{n}(x) = T_{n}(x) and P (x) = T_{p}(x) (as already mentioned above; the so-called Chebyshev case) or G_{n}(x) = x^{n} and P (x) = x^{p} (the cyclic case). For details we refer to [32, pp. 4-5].

5. The Brownawell-Masser inequality

Let us begin by recalling the definitions of the discrete valuations on the field 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). These are all discrete valuations on K(x). Now let L be a finite extension of K(x). Each of the valuations ν_{ξ}, ν_{∞} can be extended in at most [L : K(x)] =: d ways to a discrete valuation on L and in this way one obtains all discrete valuations on L (normalized so that ν(L^{∗}) = ℤ). A valuation on L is called finite if it extends ν_{ξ} for some ξ ∈ K and infinite if it extends ν_{∞}.

We need the following generalization of the degree from K[x] to L. We define the projective height of u_{1}, …, u_{n} ∈ L, n ≥ 2 not all zero, as usual by

H(u_{1}, …, u_{n}) := − ∑_{ν} min{ν(u_{1}), …, ν(u_{n})},

where ν runs over all places of L/K. Observe that by the product formula this is really a height on ℙ_{n−1}(K). For a single element f ∈ L we define

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

where the sum is taken over all valuations on L; thus for f ∈ K(x) the height H(f) is just the number of poles of f counted according to multiplicity. We note that if f lies in K[x] then H(f) = d deg f. Moreover, it is easy to see that we have

H(u_{1}, …, u_{n}, 1) ≥ max_{i=1,...,n}{H(u_{i})}.

Let S be a set of absolute values of L containing all infinite ones. Then f ∈ L is called an S-unit, if ν(f) = 0 for all ν ∉ S.

Now we are able to state the following theorem, which gives an effective finiteness result for the solutions of a so-called S-unit equation over function fields, which is a generalisation of a result due to Mason (see [20, 21]) and which was proved by Brownawell and Masser in [8]. Let us remark that the same result was independently obtained (but not stated explicitly) by Voloch in [30]. We mention that Mason [20] used his result to solve effectively certain classical Diophantine equations over function fields.

Theorem 2 (Brownawell and Masser). Let u_{1}, …, u_{n} ∈ L (n ≥ 3) be such that u_{1} + … + u_{n} = 0 but no proper nonempty subset of the u_{i}’s is made of elements linearly dependent over K. Then

H(u_{1}, …, u_{n}) ≤ \frac{(n − 1)(n − 2)}{2}(#S + 2g − 2),

where S is the set of places of L where some u_{i} is not a unit.

Let us note that this bound varies only as a linear function in #S and g and as a quadratic function in n in contrast with the exponential bounds for the classical case obtained by Bugeaud and Győry [6] for n = 2. Moreover, for n > 2 no effective results for the S-unit equation over number fields is known. The best results concern the number of solutions of such an equation (cf. [11]). The most recent result in this context is due to Evertse, Schlickewei and Schmidt [12] and it generalises earlier results (see [11]) to arbitrary fields of characteristic zero. This shows that the fundamental inequality due to Brownawell and Masser which is the function field analog of Baker’s method of linear forms in logarithms (cf. [1]) is very sharp.

We mention that there exist results for the number of subspaces in which all solutions (which do not contain K-linearly dependent subsets) of an Sunit equation over function fields lie: earlier results can be found in [9, 10], but these results were very recently significantly improved by Evertse and Zannier [13].

Let us mention that a further sharpening of the Brownawell-Masser inequality was obtained by Zannier in [31]. In this paper we will use the result from above.

6. Proof of the Main Theorem and Corollary 1

First we give the proof of the main theorem. So, let us assume that the set

V := {π_{il}^{(j)} α_{i}^{(j)}^{n_{j}} : l = 1, …, r_{i}, i = 1, …, d_{j}, j = 1, …, k}

is linearly dependent over K. In this case we have an equation

∑_{j=1}^{k} ∑_{i=1}^{d_{j}} ∑_{l=1}^{r_{i}} c_{jil}π_{il}^{(j)} α_{i}^{(j)}^{n_{j}} = 0,

for some c_{jil} ∈ K, not all of them equal to zero. Now we apply the Brownawell-Masser inequality (Theorem 2) to this equation. Observe that we cannot apply it in the case k = 1 and d_{1} = 2, r_{1} = r_{2} = 1. But this case is trivially included in the argumentation below. Namely, in this case we have at most one n, which is given by

n_{1} = \frac{−ν (π_{11}^{(1)}) − ν (π_{21}^{(1)})}{ν (α_{1}^{(1)}) − ν (α_{2}^{(1)})}

for every ν for which the denominator is not zero.

Therefore, we get that for every (n_{1}, …, n_{k}) ∈ ℕ^{k} for which the above equation holds, but no proper subset of V is linearly dependent over K, we have

H (V) ≤ \frac{(d − 1)(d − 2)}{2} (( ∑_{\begin{matrix}ν with \\ ν(α_{i}^{(j)}) ≠ 0 or \\ ν(π_{il}^{(j)}) ≠ 0 \end{matrix}} 1) + 2g − 2) ,

where

d = ∑_{j=1}^{k} ∑_{i=1}^{d_{j}} r_{i}.

On the other side we trivially have that

H (V) ≥ max_{\begin{matrix}(i, l) ≠ (u, v) \\ 1 ≤ i, u ≤ d_{j} \\ 1 ≤ l, v ≤ r_{i} \end{matrix}} \{H (\frac{π_{il}^{(j)} α_{i}^{(j)}^{n_{j}}}{π_{uv}^{(j)} α_{u}^{(j)}^{n_{j}}} )\}

for every j ∈ {1, …, k} with d_{j} ≥ 2.

For fixed (i, l) ≠ (u, v), i, u ∈ {1, …, d_{j}}, l, v ∈ {1, …, r_{i}} we consider

H (\frac{π_{il}^{(j)} α_{i}^{(j)}^{n_{j}}}{π_{uv}^{(j)} α_{u}^{(j)}^{n_{j}}} ) = H (\frac{π_{il}^{(j)}}{π_{uv}^{(j)}} (\frac{α_{i}^{(j)}}{α_{u}^{(j)}} )^{n_{j}}) =

= − ∑_{ν} min \{0, ν (\frac{π_{il}^{(j)}}{π_{uv}^{(j)}} (\frac{α_{i}^{(j)}}{α_{u}^{(j)}} )^{n_{j}})\} =

− ∑_{\begin{matrix}ν with \\ ν (α_{i}^{(j)}) = ν (α_{u}^{(j)}) \end{matrix}} min \{0, ν (\frac{π_{il}^{(j)}}{π_{uv}^{(j)}} )\}

− n_{j} ∑_{\begin{matrix}ν with \\ ν (α_{i}^{(j)}) < ν (α_{u}^{(j)}) \end{matrix}} ν (\frac{α_{i}^{(j)}}{α_{u}^{(j)}} )

− ∑_{\begin{matrix}ν with \\ ν (α_{i}^{(j)}) < ν (α_{u}^{(j)}) \end{matrix}} ν (\frac{π_{il}^{(j)}}{π_{uv}^{(j)}} )

= n_{j}H (α_{i}^{(j)}, α_{u}^{(j)}) + C,

which is true if n_{j} is large enough, because in this case the minimum with 0 is either always the second element or 0, to be more precise the above equation holds for

n_{j} ≥ − \frac{ν (π_{il}^{(j)}) − ν (π_{uv}^{(j)})}{ν (α_{i}^{(j)}) − ν (α_{u}^{(j)})}

which is equivalent to

ν (\frac{π_{il}^{(j)}}{π_{uv}^{(j)}} (\frac{α_{i}^{(j)}}{α_{u}^{(j)}} )^{n_{j}}) \{ \begin{matrix}≥ 0 & if ν (α_{i}^{(j)}) > ν (α_{u}^{(j)}) , \\ ≤ 0 & if ν (α_{i}^{(j)}) < ν (α_{u}^{(j)}) , \end{matrix}

and where the constant C from above is given by

C :=

− ∑_{\begin{matrix}ν with \\ ν (α_{i}^{(j)}) = ν (α_{u}^{(j)}) \end{matrix}} min \{0, ν (\frac{π_{il}^{(j)}}{π_{uv}^{(j)}} )\} − ∑_{\begin{matrix}ν with \\ ν (α_{i}^{(j)}) < ν (α_{u}^{(j)}) \end{matrix}} ν (\frac{π_{il}^{(j)}}{π_{uv}^{(j)}} )

≥ − ∑_{\begin{matrix}ν with \\ ν (α_{i}^{(j)}) < ν (α_{u}^{(j)}) \end{matrix}} ν (\frac{π_{il}^{(j)}}{π_{uv}^{(j)}} ) .

Observe that for fixed j (with d_{j} ≥ 2) there are valuations ν for which

ν (α_{i}^{(j)}) ≠ ν (α_{u}^{(j)}) ⟺ ν (\frac{α_{i}^{(j)}}{α_{u}^{(j)}} ) ≠ 0,

since we have assumed that these quotients are not in K^{∗}.

Now by taking the maximum over all pairs (i, l), (u, v) we get the upper bound

n_{j} ≤ C^{(j)}

for every j ∈ {1, …, k} with d_{j} ≥ 2 as claimed in our theorem. □

Let us mention that in the case that

π_{il}^{(j)} = 1 for all l = 1, …, r_{i}, i = 1, …, d_{j}, j = 1, …, k

by applying the Brownawell-Masser inequality we immediately get

H (V) ≥ H (α_{1}^{(j)}^{n_{j}} , …, α_{d_{j}}^{(j)}^{n_{j}})

= − ∑_{ν} min {ν (α_{1}^{(j)}^{n_{j}}) , …, ν (α_{d_{j}}^{(j)}^{n_{j}})} = n_{j}H (α_{1}^{(j)}, …, α_{d_{j}}^{(j)}) .

By taking the maximum over j = 1, …, k, we get the better upper bound mentioned in Remark 3.

Proof of Corollary 1.

Now, we give the easy proof of Corollary 1. First of all it is plain that

H (α_{i}^{(j)}, α_{u}^{(j)}) ≥ 0

and that its value is always an integer. Since by our assumptions α_{i}^{(j)}/α_{u}^{(j)} ∉ K^{∗} for fixed j, we conclude that

H (α_{i}^{(j)}, α_{u}^{(j)}) ≥ 1

for all i, u, j with i ≠ u. Moreover, we have the following estimate

max_{\begin{matrix}(i, l) ≠ (u, v) \\ 1 ≤ i, u ≤ d_{j} \\ 1 ≤ l, v ≤ r_{i} \end{matrix}}  max_{\begin{matrix}ν with \\ ν (α_{i}^{(j)}) < ν (α_{u}^{(j)}) \end{matrix}} (\frac{ν (π_{il}^{(j)}) − ν (π_{uv}^{(j)})}{ν (α_{u}^{(j)}) − ν (α_{i}^{(j)})}) ≤

max_{\begin{matrix}(i, l) ≠ (u, v) \\ 1 ≤ i, u ≤ d_{j} \\ 1 ≤ l, v ≤ r_{i} \end{matrix}} \underbrace{∑_{ν} max \{0, ν (\frac{π_{il}^{(j)}}{π_{uv}^{(j)}} )\}}_{=H(π_{il}^{(j)},π_{uv}^{(j)})} ≤ H (p) ,

where

p = (π_{il}^{(j)} : 1 ≤ j ≤ k, 1 ≤ i ≤ d_{j}, 1 ≤ l ≤ r_{i}) .

Now plugging this into the upper bound obtained in Theorem 1, we get what we have claimed in the corollary. □

7. Proof of Corollaries 2 and 3.

Proof of Corollary 2.

First we handle Corollary 2. We write

P_{i}(x) = ∑_{l=1}^{u_{i}} π_{il}Q_{il}(x),

where for fixed i, the π_{il} ∈ L^{∗}, l = 1, …, u_{i} are linearly independent over K and the Q_{il}(x) ∈ K[x]. It is clear that we have deg Q_{il} = u_{i} ≤ deg P_{i}, for every i = 1, …, r. Now, if for n ∈ ℕ

(5)  P_{1}(n)α_{1}^{n} + … + P_{r}(n)α_{r}^{n} = 0

holds, we have an identity of the form

∑_{i=1}^{r} ∑_{l=1}^{u_{i}} Q_{il}(n)π_{il}α_{i}^{n} = 0

This means that the set

V := {π_{11}α_{1}^{n}, …, π_{1u_{1}}α_{1}^{n}, …, π_{r1}α_{r}^{n}, …, π_{ru_{r}}α_{r}^{n}}

is linearly dependent over K. First, we mention that there are at most finitely many n for which all the P_{i}(n) = 0. Of course the zeros of P_{1}(n) ⋯ P_{r}(n) = 0 can be effectively bounded in terms of the coefficients and the degrees of the polynomials P_{i}, i = 1, …, r. Therefore, we may assume that not all the P_{i}(n) vanish. Consequently, not all the Q_{il}(n) vanish either. We may assume that r ≥ 2, since for r = 1 no additional solutions can appear.

For a given subset W ⊆ V, we consider the set Σ_{W} of those n ∈ ℕ for which the elements in W are linearly dependent, but no proper subset is linearly dependent over K. Observe that the sets Σ_{W}, Σ_{W′} for different subsets W, W′ of V are not necessarily disjoint. Moreover, we remark that for any singleton W we have Σ_{W} = ∅ since a single element from L cannot be linearly dependent and for sets W consisting of precisely two elements of course no subset can be linearly dependent. Furthermore, a set W cannot contain only elements of the form πα_{i}^{n} for one and the same i, because the elements π_{i1}, …, π_{iu_{i}} are linearly independent over K. For the elements in Σ_{W}, we can therefore give an effectively computable number C_{W} with n ≤ C_{W} by Theorem 1. Since there are most 2^{d} subset of V, where d = ∑_{i=1}^{r} u_{i}, we get an upper bound for all n satisfying (5) just by taking the maximum of the bounds obtained in this way. From this the corollary follows. □

Proof of Corollary 3.

In Corollary 3 we have to consider those n ∈ ℕ for which

P_{1}(n)α_{1}^{n} + … + P_{r}(n)α_{r}^{n} ∈ K.

As above this is equivalent to the equation

∑_{i=1}^{r} ∑_{l=1}^{u_{i}} Q_{il}(n)π_{il}α_{i}^{n} − c · 1^{n} = 0, c = c(n) ∈ K.

Since we will apply Theorem 1 and since the “coefficients” from K do not play any role the same arguments as above lead to an effectively computable upper bound for those n. Therefore, the assertion follows. □

8. Proof of Corollaries 4, 5 and 6.

Proof of Corollaries 4 and 5.

As in the proof of Corollaries 2 and 3 we consider the set

V := {a_{1}α_{1}^{n}, …, a_{p}α_{p}^{n}, b_{1}β_{1}^{m}, …, b_{q}β_{q}^{m}}.

A solution (n, m) ∈ ℕ of the equation

G_{n} = H_{m} or G_{n} = c H_{m}, c = c(n, m) ∈ K^{∗}

implies that the set V is linearly dependent over K. We consider for each partition V = W_{1} ∪ … ∪ W_{r} the set of solutions (m, n) of the above mentioned equations such that for i = 1, …, r, the elements of W_{i} are linearly dependent over K, whereas each proper subset of W_{i} is linearly independent over K. Assuming this set of solutions is non-empty, we have that each set W_{i} contains at least two elements, since no single element of V vanishes.

Suppose first there is a set W ∈ {W_{1}, …, W_{r}} containing two distinct elements a_{i}α_{i}^{n}, a_{j}α_{j}^{n}. Applying Theorem 1 to the set W implies an upper bound C_{1,W} for n. It may happen that W contains at most one element of the form b_{l}β_{l}^{m}; then Theorem 1 does not provide an upper bound for m. To estimate m from above we consider for every n_{0} ≤ C_{1,W} the equations

H_{m} = G_{n_{0}} or H_{m} = c^{−1}G_{n_{0}}, c = c(n_{0}, m) ∈ K^{∗},

respectively. By Corollary 2 we get an effectively computable number C_{2,W} such that m ≤ C_{2,W} for every solution of these equations. Observe that the varying constant c may be disregarded in an application of the corollary. The same arguments works if W contains two distinct elements b_{i}β_{i}^{m}, b_{j}β_{j}^{m}.

Suppose now that each set among W_{1}, …, W_{r} contains precisely two elements a_{i}α_{i}^{n}, b_{j}β_{j}^{m}. Then p = q and there exists a permutation ρ of the set {1, …, p} such that V = W_{1} ∪ … ∪ W_{r} with W_{i} = {a_{i}α_{i}^{n}, b_{ρ(i)}β_{ρ(i)}^{m}} for all i = 1, …, p.

In this case, we have equations of the form

(6)  c_{1}a_{i}α_{i}^{n} = c_{2}b_{j}β_{j}^{m}

with c_{1}, c_{2} ∈ K^{∗}. This equation can only hold for one pair (n_{0}, m_{0}) ∈ ℕ unless the set of zeros and poles of α_{i} and β_{j} coincide. Let ν be one of these zeros and poles. Then (6) implies that n = rm + s for the integers

r = \frac{ν(β_{j})}{ν(α_{i})}, s = \frac{ν(b_{j}) − ν(a_{i})}{ν(α_{i})}.

Putting this into (6) we get

−\frac{c_{1}a_{i}}{c_{2}b_{j}} = (\frac{β_{j}}{α_{i}^{r}} )^{m} .

This equation holds for one m = m_{0} only, unless β_{j}/α_{i}^{r} is a root of unity and c_{1}a_{i}/(c_{2}b_{j}) is also a root of unity. Then the equation holds for all m in an arithmetic progression.

Thus, we conclude that the equation holds just for one (n_{0}, m_{0}) ∈ ℕ^{2}, unless we have p = q and there exist integers n_{0}, m_{0}, r, s, rs ≠ 0 such that we have to consider

G_{n_{0}+rm} = H_{m_{0}+sm} or G_{n_{0}+rm} = c H_{m_{0}+sm}, c = c(m) ∈ K^{∗},

respectively and there exists a permutation ρ such that α_{i}^{r}/β_{ρ(i)}^{s} = δ_{i} is a root of unity. Therefore the equation from above can be rewritten as

∑_{i=1}^{p} (a_{i}α_{i}^{n_{0}} − b_{ρ(i)}β_{ρ(i)}^{m_{0}}δ_{i}^{m}) β_{ρ(i)}^{sm} = 0

or

∑_{i=1}^{p} (a_{i}α_{i}^{n_{0}} − cb_{ρ(i)}β_{ρ(i)}^{m_{0}}δ_{i}^{m}) β_{ρ(i)}^{sm} = 0,

respectively.

Now, we get by Theorem 1 an effectively computable upper bound for m in both cases unless all coefficients vanish. In the first case this can happen only for one m (which can be computed explicitly), unless a_{i}α_{i}^{n_{0}}/(b_{j}β_{j}^{m_{0}}) is also a root of unity and in this case the coefficient vanishes in an arithmetic progression. Since the intersection of these arithmetic progressions (for varying i = 1, …, p) is either empty or again an arithmetic progression, the conclusion follows. In the second case (Corollary 5) the situation is a little bit more involved since c = c(m) may depend on m. Here we see that the vanishing of all coefficients implies that

c = \frac{a_{i}α_{i}^{n_{0}}}{b_{ρ(i)}β_{ρ(i)}^{m_{0}}δ_{i}^{m}}

for all i = 1, …, p. Therefore, the ratios on the right hand side are independent of i. This gives

\frac{a_{i}α_{i}^{n_{0}}b_{ρ(1)}β_{ρ(1)}^{m_{0}}}{b_{ρ(i)}β_{ρ(i)}^{m_{0}}a_{1}α_{1}^{n_{0}}} = (\frac{δ_{i}}{δ_{1}} )^{m}

for i = 2, …, p. As above, this may hold either for at most a single m, which can be calculated explicitly, or in a whole arithmetic progression. In both cases we have the conclusion as claimed in the corollary. □

Proof of Corollary 6.

Corollary 6 is an immediate consequence of Corollary 5. □

9. Acknowledgements

This paper was written during a visit of the first author at the University of Debrecen in the frame of a joint Austrian-Hungarian project granted by the Austrian Exchange Service (Nr. A-27/2003) and the Hungarian TéT foundation. The first author is grateful to Attila Pethő for his hospitality.

References

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

2. F. Beukers, The multiplicity of binary recurrences, Compositio Math. 40 (1980), 251-267.

3. F. Beukers, The zero-multiplicity of ternary recurrences, Compositio Math. 77 (1991), 165-177.

4. F. Beukers and R. Tijdeman, On the multiplicities of binary complex recurrences, Compositio Math. 51 (1984), 193-213.

5. E. Bombieri, J. Müller and U. Zannier, Equations in one variable over function fields, Acta Arith. 99 (2001), 27-39.

6. Y. Bugeaud and K. Győry, Bounds for the solutions of unit equations, Acta Arith. 74 (1996), 67–80.

7. L. Cerlience, M. Mignotte and F. Piras, Suites récurrentes linéaires: propriétés algébriques et arithmétiques, Enseign. Math. (2) 33 (1987), 67–108.

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

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

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

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

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

13. J.H. Evertse and U. Zannier, Linear equations with unknowns from a multiplicative group in a function field, Preprint (http://www.math.leidenuniv.nl/∼evertse/04functionfields.ps).

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

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

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

17. C. Fuchs, A. Pethő and R. F. Tichy, On the Diophantine equation G_{n}(x) = G_{m}(y) with Q(x, y) = 0, Preprint (http://finanz.math.tu-graz.ac.at/∼fuchs/oegngmad2.ps).

18. M. Laurent, Équations exponentielles polynômes et suites récurrentes linéares, Astérisque 147-148 (1987), 121-139.

19. M. Laurent, Équations exponentielles-polynômes et suites récurrentes linéaires, II, J. Number Theory 31 (1989), 24-53.

20. R. C. Mason, Equations over Function Fields, Lecture Notes in Math. 1068 (1984), Springer, Berlin, 149–157.

21. R. C. Mason, Norm form equations I, J. Number Theory 22 (1986), 190-207.

22. H. P. Schlickewei, Multiplicities of recurrence sequences, Acta Math. 176 (1996), 171-243

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

24. H. P. Schlickewei and W. M. Schmidt, The intersection of recurrence sequences, Acta Arith. 72 (1995), 1-44.

25. H. P. Schlickewei and W. M. Schmidt, The number of solutions of polynomialexponential equations, Compositio Math. 120 (2000), 193-225.

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

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

28. W. M. Schmidt, Linear Recurrence Sequences and Polynomial-Exponential Equations, in: Diophantine Approximation (F. Amoroso, U. Zannier eds.), Proc. of the C.I.M.E. Conference, Cetraro (Italy) 2000, Springer-Verlag LNM 1819, 2003.

29. T. N. Shorey and R. Tijdeman, Exponential Diophantine Equations, Cambridge, Univ. Press, 1986. Verlag, Berlin, 1993.

30. J. F. Voloch, Diagonal equations over function fields, Bol. Soc. Brasil. Mat. 16 (1985), 29-39.

31. U. Zannier, Some remarks on the S-unit equation in function fields, Acta Arith. 64 (1993), 87-98.

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

Clemens Fuchs Institut für Mathematik Technische Universität Graz Steyrergasse 30 8010 Graz, Austria Current Adress: Mathematisch Instituut, Universiteit Leiden, Niels Bohrweg 1, Postbus 9512, 2300 RA Leiden, The Netherlands e-mail: fuchs@math.leidenuniv.nl

Attila Pethő Institute of Informatics University of Debrecen, Debrecen Pf. 12 4010 Debrecen, Hungary e-mail: pethoe@inf.unideb.hu