POLYNOMIAL-EXPONENTIAL EQUATIONS INVOLVING SEVERAL LINEAR RECURRENCES

CLEMENS FUCHS^{∗} AND AMEDEO SCREMIN^{‡}

Abstract. Let E_{A} denote the ring of complex functions on ℕ of the form

G_{n} = c_{1}α_{1}^{n} + c_{2}α_{2}^{n} + ⋯ + c_{t}α_{t}^{n},

for some c_{i} ∈ ℂ and α_{i} ∈ A, where A ⊆ ℂ is multiplicative semigroup. Moreover, let F (n, y) ∈ E_{A}[y]. We consider polynomial-exponential Diophantine equations of the form

F (n, y) = G_{n}^{(0)}y^{d} + G_{n}^{(1)}y^{d−1} + … + G_{n}^{(d−1)}y + G_{n}^{(d)} = 0

and show that this equation has only finitely many solutions under certain conditions. This generalizes earlier results due to Corvaja and Zannier (cf. [4], [6]) on such equations.

2000 Mathematics Subject Classification: 11D45,11D61. Keywords: polynomial-exponential Diophantine equations, linear recurring sequences, Subspace Theorem

1. Introduction

Let A_{1}, A_{2}, …, A_{k} and G_{0}, G_{1}, …, G_{k−1} be integers and let (G_{n}) be a k-th order linear recurring sequence given by

(1)  G_{n} = A_{1}G_{n−1} + ⋯ + A_{k}G_{n−k} for n = k, k + 1, ….

Let α_{1}, α_{2}, …, α_{t} be the distinct roots of the corresponding characteristic polynomial

(2)  X^{k} − A_{1}X^{k−1} − ⋯ − A_{k}.

Then for n ≥ 0

(3)  G_{n} = P_{1}(n)α_{1}^{n} + P_{2}(n)α_{2}^{n} + ⋯ + P_{t}(n)α_{t}^{n},

where P_{i}(n) is a polynomial with degree less than the multiplicity of α_{i}; the coefficients of P_{i}(n) are elements of the field: ℚ(α_{1}, …, α_{t}).

We shall be interested in linear recurring sequences (G_{n}), where all roots of the characteristic polynomial of (G_{n}) are simple, which means that

(4)  G_{n} = c_{1}α_{1}^{n} + c_{2}α_{2}^{n} + ⋯ + c_{k}α_{k}^{n},

Date: August 7, 2003.

∗The first author was supported by the Austrian Science Foundation FWF, grant S8307-MAT.

‡The second author was supported by Istituto Nazionale di Alta Matematica “Francesco Severi”, grant for abroad Ph.D.

for some c_{i}, α_{i} ∈ ℂ. If we restrict the roots to come from a multiplicative semigroup A ⊆ ℂ, then we let E_{A} denote the ring of complex functions on ℕ of the form (4) where α_{i} ∈ A. If K ⊆ ℂ is a field we define KE_{A} by the same formulas, but allowing c_{i} ∈ K.

Below, A will be usually ℤ; moreover in that case we define by E_{ℤ}^{+} the subring formed by those functions having only positive roots, i.e. by the semigroup ℕ. Working in this domain causes no loss of generality: this assumption may be achieved by writing n = 2m + r and considering the cases r = 0, 1 separately.

The recurring sequence (G_{n}) is called nondegenerate, if no quotient α_{i}/α_{j} for 1 ≤ i < j ≤ t is equal to a root of unity. Observe that restricting to nondegenerate recurring sequences causes no substantial loss of generality.

In the present paper we deal with Diophantine equations, where linear recurring sequences are involved. Such equations were earlier investigated by several authors, e.g. in the special case

(5)  G_{n} = Ex^{q}, E ∈ ℤ\{0}.

A survey about this equation can be found in [13, 14] and in more general form in [8, 10].

The first results have been proved just by using elementary and algebraic tools. Later, the results were obtained with the applications of lower bounds for linear forms in logarithms of algebraic numbers.

In 1998, a new development was started by Corvaja and Zannier [4]. They considered linear recurrences defined by

G_{n} = c_{1}α_{1}^{n} + c_{2}α_{2}^{n} + ⋯ + c_{t}α_{t}^{n},

where t ≥ 2, c_{1}, c_{2}, …, c_{t} are non-zero rational numbers, α_{1} > α_{2} > ⋯ > α_{t} > 0 are integers. They used Schmidt’s Subspace Theorem [16], [17] to show that for every integer q ≥ 2 the equation

(6)  G_{n} = x^{q}

has only finitely many solutions (n, x) ∈ ℕ^{2} assuming that G_{n} is not identically a perfect qth power for all n in a suitable arithmetic progression. Tichy and the first author [10] gave a quantitative version of the above result of Corvaja and Zannier by using a quantitative version of the Subspace Theorem due to Evertse [7].

Recently, Corvaja and Zannier [6] generalized their result. Let K be an algebraic number field and let (G_{n}) be a nondegenerate linear recurring sequence defined by (4) where t ≥ 2, c_{i} are non-zero elements of K for all i = 2, …, t and where α_{1}, …, α_{t} are elements of K with 1 ≠ |α_{1}| > |α_{j}| for all j = 2, …, t. Let f(z, x) ∈ K[z, x] be monic in x and suppose that there do not exist non-zero algebraic numbers d_{j}, β_{j} for j = 1, …, k such that

(7)  f(G_{n}, ∑_{j=1}^{k} d_{j}β_{j}^{n}) = 0

for all n in an arithmetic progression. Then the number of solutions (n, x) ∈ ℕ × K of the equation

f(G_{n}, x) = 0

is finite. The first author [8] gave a quantitative version of this result, which is a little bit more general in the assumptions.

The aim of the present paper is the generalization of the above result to a Diophantine equation where more than one linear recurring sequence is involved. Let f(x_{1}, …, x_{d}, y) ∈ \overline{ℚ}[x_{1}, …, x_{d}, y] (where \overline{ℚ} denotes the algebraic closure of ℚ) and let G_{n}^{(1)}, …, G_{n}^{(d)} ∈ \overline{ℚ}E_{ℤ}^{+}, then we want to consider the Diophantine equation

f(G_{n}^{(1)}, …, G_{n}^{(d)}, y) = 0.

This is equivalent to saying that we consider equations of the form

(8)  G_{n}^{(0)}y^{d} + … + G_{n}^{(d−1)}y + G_{n}^{(d)} = 0,

where G_{n}^{(0)}, …, G_{n}^{(d)} ∈ \overline{ℚ}E_{ℤ}^{+}, i.e. to consider polynomials in y with coefficients in the ring \overline{ℚ}E_{ℤ}^{+}.

Let us mention that similar types of equations, namely

f(x, y, α^{x}) = 0 and f(x, y, α^{x}, β^{y}) = 0,

where f is a polynomial with complex coefficients and α, β are non-zero complex numbers, were studied by Schmidt [18] and Ahlgren [1, 2]. They showed that this equations can have solutions with arbitrarily large values of |x| only in the case when f and α, β are of a particularly simple form.

The second author [20] showed another result which is related to what we consider here. Let f(x, y) ∈ \overline{ℚ}[x, y] be monic in y, absolutely irreducible and of degree d ≥ 2 in y; let g(n) ∈ ℤ[x] be a non constant polynomial; let G_{n} ∈ \overline{ℚ}E_{ℤ} not constant. Then the equation

f(G_{n}, y) = g(n)

has only finitely many solutions (n, y) ∈ ℕ × ℤ.

2. Results

In this section we will state our general results. First we need some notation. Let d ≥ 2 be an integer and let G_{n}^{(0)}, …, G_{n}^{(d)} ∈ \overline{ℚ}E_{ℤ}^{+}, i.e. we have

G_{n}^{(0)} = a_{1}^{(0)}α_{1}^{(0)^{n}} + a_{2}^{(0)}α_{2}^{(0)^{n}} + … + a_{t^{(0)}}^{(0)}α_{t^{(0)}}^{(0)^{n}},
⋮
G_{n}^{(d)} = a_{1}^{(d)}α_{1}^{(d)^{n}} + a_{2}^{(d)}α_{2}^{(d)^{n}} + … + a_{t^{(d)}}^{(d)}α_{t^{(d)}}^{(d)^{n}},

where a_{i}^{(j)} are algebraic and α_{i}^{(j)} are positive integers such that α_{1}^{(j)} > α_{2}^{(j)} > … > α_{t^{(j)}}^{(j)} for all i = 1, … t^{(j)} and j = 0, …, d. Now we consider the Diophantine equation

G_{n}^{(0)}y^{d} + … + G_{n}^{(d−1)}y + G_{n}^{(d)} = 0.

Let f(x_{0}, …, x_{d}, y) = x_{0}y^{d} + … + x_{d−1}y + x_{d} be fixed for the rest of the paper. So the above equation becomes

f(G_{n}^{(0)}, …, G_{n}^{(d)}, y) = 0.

We will show how to this equation another equation in some normal form can be associated. First, we set (for a positive real determination of the roots)

α := max \{α_{1}^{(d)^{\frac{1}{d}}} , (\frac{α_{1}^{(d−1)}}{α_{1}^{(0)^{\frac{1}{d}}}} )^{\frac{1}{d−1}} , (\frac{α_{1}^{(d−2)}}{α_{1}^{(0)^{\frac{2}{d}}}} )^{\frac{1}{d−2}} , …, \frac{α_{1}^{(1)}}{α_{1}^{(0)^{\frac{d−1}{d}}}} \}

= max_{i=1,...,d} (\frac{α_{1}^{(i)}}{α_{1}^{(0)^{\frac{d−i}{d}}}} )^{\frac{1}{i}} .

Moreover, let

y = \frac{α^{n}}{α_{1}^{(0)^{\frac{n}{d}}}} z.

Then consider

(9)  \frac{1}{α^{dn}} f(G_{n}^{(0)}, …, G_{n}^{(d)}, \frac{α^{n}}{α_{1}^{(0)^{\frac{n}{d}}}} z).

This is a polynomial in z with coefficients in \overline{ℚ}E_{A}, where A is the multiplicative group generated by

α, α_{1}^{(0)^{\frac{1}{d}}} and the roots of G_{n}^{(0)}, …, G_{n}^{(d)},

i.e. the coefficients of this polynomial are again power sums. Observe that all the roots which appear in these power sums are ≤ 1, because of our construction and that one of the roots which appear as coefficient of z^{d} is 1 (this will be proved in Lemma 2 below). Let γ_{1}, …, γ_{r} denote the different roots of these power sums (the coefficients of (9) as a polynomial in z), which are strictly less than 1. We identify the expressions γ_{i}^{n} in (9) by a new variable x_{i}. Therefore we get a polynomial (linear in x_{1}, …, x_{r}) g_{f}(x_{1}, …, x_{r}, z) ∈ \overline{ℚ}[x_{1}, …, x_{r}, z] such that

g_{f}(γ_{1}^{n}, …, γ_{r}^{n}, z) = \frac{1}{α^{dn}} f(G_{n}^{(0)}, …, G_{n}^{(d)}, \frac{α^{n}}{α_{1}^{(0)^{\frac{n}{d}}}} z).

This polynomial is some kind of normal form for our equation under consideration. We denote by D_{g_{f} ,z}(x_{1}, …, x_{r}) the discriminant of g_{f} with respect to z and we set D_{g_{f} ,z} := D_{g_{f} ,z}(0, …, 0).

We are now in the position to formulate our main result. Our aim is to prove that the equation has only finitely many solutions in integers, apart from “trivial” cases which can be classified. We achieve this goal under a suitable technical hypothesis in the Main Theorem below.

Theorem 1. Let d ≥ 2 and let G_{n}^{(0)}, …, G_{n}^{(d)} ∈ \overline{ℚ}E_{ℤ}^{+}. Assume that

(10)  D_{g_{f} ,z} ≠ 0.

Then there exist finitely many recurrences H_{n}^{(1)}, …, H_{n}^{(s)} with algebraic coefficients and algebraic roots, arithmetic progressions P_{1}, …, P_{s}, and a finite set N of integers, such that for the set S of solutions (n, y) ∈ ℕ × ℤ of the equation

f(G_{n}^{(0)}, …, G_{n}^{(d)}, y) = G_{n}^{(0)}y^{d} + … + G_{n}^{(d−1)}y + G_{n}^{(d)} = 0

we have

S = ⋃_{i=1}^{s}{(n, H_{n}^{(i)}) : n ∈ P_{i}} ∪ {(n, y) : n ∈ N , y ∈ ℤ} ∪ M,

where M is a finite set.

Remark 1. In contrast to [6, 8], where Puiseux series are used, the main tool in our proof is the fact that we can use some suitable version of the Implicit Function Theorem to express z in g_{f} as a power sum of the other variables which converges locally around the origin. In the version of Puiseux’s theorem for several variables (cf. [3]) known to the authors, a similar condition to (10) appears, namely that the discriminant does not vanish in a certain region.

Remark 2. As we use the Implicit Function Theorem as our driving tool, it is clear that condition (10) is equivalent to

(10) ⟺ g_{f}(0, …, 0, z) has only simple roots ⟺

⟺ \frac{∂g_{f}}{∂z} (0, …, 0, z_{i}) ≠ 0, i = 1, …, d,

where z_{i} are the roots of g_{f}(0, …, 0, z). Note that a similar condition already appeared in the main result in [5].

Let us point out what the construction of α means for the equation

G_{n} = a_{1}α_{1}^{n} + … + a_{t}α_{t}^{n} = y^{d}.

We get

g_{f}(x_{1}, …, x_{t−1}, z) = z^{d} − (a_{1} + a_{2}x_{1} + … + a_{t}x_{t−1}),

such that

g_{f}(\frac{α_{2}^{n}}{α_{1}^{n}} , …, \frac{α_{t}^{n}}{α_{1}^{n}} , z) = 0.

Observe that condition (10) is satisfied and therefore we get once again the result of Corvaja and Zannier [4]. In fact the construction is exactly the same as the idea of their proof.

Remark 3. Note that the progressions can be chosen in such a way that along the progression P_{i} we have

H_{n}^{(i)} ∈ E_{ℤ}^{+}.

We will show this at the end of the proof of Theorem 1.

Remark 4. Observe that the first type of infinite families of solutions may appear. For example the equation

y^{2} + (2^{n} + 3^{n})y + 6^{n} = 0

has solutions (n, −2^{n}) and (n, −3^{n}) for all n ∈ ℕ. Moreover, observe that

g_{f}(x_{1}, x_{2}, z) = z^{2} + (1 + x_{1})z + x_{1}

and therefore

D_{g_{f} ,z} = 1 ≠ 0.

These solutions are “trivial” infinite families of solutions in the sense that the equation has already solutions in the ring of power sums (cf. also the result due to Corvaja and Zannier [4, 6]).

Remark 5. In fact it is easy to decide whether such infinite families of solutions appear or not. This follows from the fact that the ring E_{A}, where A is the multiplicative group generated by the roots of a recurrence G_{n}, is easily understood. It is well known (see [15]) that this ring is isomorphic to the ring

ℂ[T_{1}, …, T_{t}, T_{1}^{−1}, …, T_{t}^{−1}]

if A has rank t ≥ 1 and has no torsion. We simply choose a basis γ_{1}, …, γ_{t} of A and associate the variable T_{i} to the function n ↦ γ_{i}^{n}.

Remark 6. It is easy to see that some further infinite families can appear. For example consider the equation

(2^{n} − 2)y^{2} + 3^{n} − 3 = 0.

Obviously, this equation has infinitely many solutions, namely (1, y) with y ∈ ℤ arbitrary. We have

g_{f}(x_{1}, x_{2}, z) = (1 − 2x_{1})z^{2} + 1 − 3x_{2},

therefore D_{g_{f} ,z} = −4 ≠ 0. Let us notice that the assumption that the polynomial f is monic excludes the existence of “trivial” families of solutions of this type.

We state some corollaries, which follow from the proof of our main theorem.

Corollary 1. Let d ≥ 2 and let G_{n}^{(1)}, …, G_{n}^{(d)} ∈ \overline{ℚ}E_{ℤ}^{+}. Assume that there does not exist H_{n} ∈ \overline{ℚ}E\overline{ℚ} such that

H_{n}^{d} + G_{n}^{(1)}H_{n}^{d−1} + … + G_{n}^{(d)} = 0

for all n in a certain arithmetic progression. Moreover, assume that

(11)  α_{1}^{(d−1)} > α_{1}^{(j)^{d−1}} for all j = 0, …, d − 2, d.

Then the Diophantine equation

y^{d} + G_{n}^{(1)}y^{d−1} + … + G_{n}^{(d−1)}y + G_{n}^{(d)} = 0

has only finitely many solutions (n, y) ∈ ℕ × ℤ.

The next corollaries handle equations of the form under consideration of degree 3.

Corollary 2. Let G_{n}^{(1)}, G_{n}^{(2)} ∈ \overline{ℚ}E_{ℤ}^{+}. Assume that there does not exist H_{n} ∈ \overline{ℚ}E\overline{ℚ} such that

H_{n}^{3} + G_{n}^{(1)}H_{n} + G_{n}^{(2)} = 0

for all n in a certain arithmetic progression. Moreover, assume that

(α_{1}^{(1)})^{3} ≠ (α_{1}^{(2)})^{2} or 4(a_{1}^{(1)})^{3} + 27(a_{2}^{(2)})^{2} ≠ 0.

Then the equation

y^{3} + G_{n}^{(1)}y + G_{n}^{(2)} = 0

has only finitely many solutions (n, y) ∈ ℕ × ℤ.

Corollary 3. Let 0 ≠ a, b ∈ \overline{ℚ} and α, β positive integers. Then the equation

y^{3} + aα^{n}y + bβ^{n} = 0

has for α^{3} ≠ β^{2} only finitely many solutions (n, y) ∈ ℕ × ℤ, and for α^{3} = β^{2} the set of solutions (n, y) ∈ ℕ × ℤ is contained in the following

set consisting of infinite families

\{(n, cβ^{\frac{n}{3}} ) : n ∈ ℕ, c^{3} + ac + b = 0\}.

Although we work only in E_{ℤ}, similar results should hold more generally for functions with algebraic roots, with the restriction that we have dominating roots and the recurrences are nondegenerate. Also, the results should hold by allowing the coefficients to be polynomials in n with the restriction that the coefficient of the dominating root is constant.

Moreover, it is clear that the results can be quantified by using quantitative versions of the Subspace Theorem, e.g. due to Evertse [7].

3. Auxiliary Results

The proof of our theorem depends on a version of the Subspace Theorem due to Schlickewei (the following version can be found in [17, 16]).

Let K be an algebraic number field. Denote its ring of integers by O_{K} and its collection of places by M_{K}. For v ∈ M_{K}, x ∈ K, we define the absolute value |x|_{v} by

(i) |x|_{v} = |σ(x)|^{1/[K:ℚ]} if v corresponds to the embedding σ : K ↪ ℝ; (ii) |x|_{v} = |σ(x)|^{2/[K:ℚ]} = |σ̄(x)|^{2/[K:ℚ]} if v corresponds to the pair of conju-

gate complex embeddings σ, σ̄ : K ↪ ℂ; (iii) |x|_{v} = (N℘)^{−ord_{℘}(x)/[K:ℚ]} if v corresponds to the prime ideal ℘ of O_{K}. Here N℘ = #(O_{K}/℘) is the norm of ℘ and ord_{℘}(x) the exponent of ℘ in the prime ideal decomposition of (x), with ord_{℘}(0) := ∞. In case (i) or (ii) we call v real infinite or complex infinite, respectively; in case (iii) we call v finite. These absolute values satisfy the Product formula

(12)  ∏_{v∈M_{K}} |x|_{v} = 1 for x ∈ K\{0}.

We define the K-height of x ∈ K to be

H_{K}(x) = ∏_{v∈M_{K}} max{1, |x|_{v}}.

Observe that H_{ℚ}(x) = |x| (the usual absolute value) for x ∈ ℤ and that

H_{L}(x) = H_{K}(x)^{[L:K]},

for x ∈ K and for a finite extension L of K.

The height of x = (x_{1}, …, x_{n}) ∈ K^{n} with x ≠ 0 is defined as follows: for v ∈ M_{K} put

|x|_{v} = max_{1≤i≤n} |x_{i}|_{v}.

Now define

H(x) = ∏_{v∈M_{K}} max{1, |x|_{v}}.

Theorem 2. (Subspace Theorem, Schlickewei) Let K be an algebraic number field and let S ⊂ M_{K} be a finite set of absolute values which contains all the infinite ones. For v ∈ S, let L_{1,v}, …, L_{n,v} be n linearly independent linear forms in n variables with coefficients in K. Let δ > 0 be given. Then the solutions of the inequality

(13)  ∏_{v∈S} ∏_{i=1}^{n} |L_{i,v}(x)|_{v} < H(x)^{−δ}

with x ∈ (O_{K})^{n} and x ≠ 0 lie in finitely many proper subspaces of K^{n}.

This follows from Theorem 1D’ in [17], page 178.

Below we have collected two simple lemmas which are needed in our proofs. Namely, we need an estimate for the number of zeros occurring in a linear recurring sequence (this number is called the zero multiplicity of the recurrence). The proof is easy and therefore we give it (cf. [9]).

Lemma 1. Let (G_{n}) be a linear recurring sequence defined by G_{n} = c_{1}α_{1}^{n} + c_{2}α_{2}^{n} +⋯+c_{t}α_{t}^{n} where t ≥ 1, c_{i} are non-zero complex and α_{1} > ⋯ > α_{t} > 0 are real numbers. Then the number of solutions of the equation

G_{n} = 0

is at most t − 1.

Proof. We prove our assertion by induction on t. The case t = 1 is trivial. Now consider the function of one real variable

g(x) = c_{1} exp(x log(α_{1}/α_{t})) + ⋯ + c_{t−1} exp(x log(α_{t−1}/α_{t})) + c_{t}.

Observe that by separating real and imaginary parts we can assume that the c_{i} are real. Clearly, the zeros of g at positive integral points are exactly the zeros of G_{n}. Now, g(x) is a differentiable function of the real variable x. So, between any two zeros of g one can find a zero of the derivative g′ of g. Since the derivative is a function of the same type, with t − 1 terms, the inductive hypothesis can be applied and the desired conclusion follows. □

Let us mention the remarkable result that there exists an upper bound (which does only depend on the order t, but in fact triply exponentially) for the zero multiplicity of arbitrary nondegenerate linear recurring sequences of complex numbers due to W.M. Schmidt [19].

As a second lemma we prove that the construction leading to the polynomial g_{f} has the properties we have claimed.

Lemma 2. Let f, G_{n}^{(0)}, …, G_{n}^{(d)} and α be as at the beginning of Section 2. Then the dominant root in

f (G_{n}^{(0)}, …, G_{n}^{(d)}, \frac{α^{n}}{α_{1}^{(0)^{\frac{n}{d}}}} z)

is α^{d} and it appears as the coefficient of z^{d}.

Proof. Let us assume that

α = \frac{α_{1}^{(k)^{\frac{1}{k}}}}{α_{1}^{(0)^{\frac{d−k}{dk}}}} .

Thus, we have

(14)  α ≥ \frac{α_{1}^{(i)^{\frac{1}{i}}}}{α_{1}^{(0)^{\frac{d−i}{di}}}} for all i = 1, …, d.

It is clear that it is enough to investigate how the dominant roots transform under the substitution

y = \frac{α^{n}}{α_{1}^{(0)^{\frac{n}{d}}}} z.

The dominant root in the coefficient of z^{d} is

α_{1}^{(0)} \frac{α^{d}}{α_{1}^{(0)}} = \frac{α_{1}^{(k)^{\frac{d}{k}}}}{α_{1}^{(0)^{\frac{d−k}{k}}}} .

Moreover, the dominant root in the coefficient of z^{d−i} for i = 1, …, d is

α_{1}^{(i)} \frac{α^{d−i}}{α_{1}^{(0)^{\frac{d−i}{d}}}} = \frac{α_{1}^{(i)}}{α_{1}^{(0)^{\frac{d−i}{d}}}} \frac{α_{1}^{(k)^{\frac{d−i}{k}}}}{α_{1}^{(0)^{\frac{(d−k)(d−i)}{dk}}}} ≤ \frac{α_{1}^{(k)^{\frac{i}{k}}}}{α_{1}^{(0)^{\frac{(d−k)i}{dk}}}} \frac{α_{1}^{(k)^{\frac{d−i}{k}}}}{α_{1}^{(0)^{\frac{(d−k)(d−i)}{dk}}}} = \frac{α_{1}^{(k)^{\frac{d}{k}}}}{α_{1}^{(0)^{\frac{d−k}{k}}}} ,

where we have used the definition of α (especially (14)) and the upper bound is the dominant root of the coefficient of z^{d}. Observe that for the coefficient of z^{d−k} we get

α_{1}^{(k)} \frac{α^{d−k}}{α_{1}^{(0)^{\frac{d−k}{d}}}} = \frac{α_{1}^{(k)^{\frac{k}{k}}}}{α_{1}^{(0)^{\frac{d−k}{d}}}} \frac{α_{1}^{(k)^{\frac{d−k}{k}}}}{α_{1}^{(0)^{\frac{(d−k)(d−k)}{dk}}}} = \frac{α_{1}^{(k)^{\frac{d}{k}}}}{α_{1}^{(0)^{\frac{d−k}{k}}}} ,

and therefore the dominant root also appears in the power sum which appears as coefficient of z^{d−k}. □

Our last tool is the Implicit Function Theorem. The basic form of the Implicit Function Theorem is the assertion that a function in n variables, of sufficient smoothness, satisfying an appropriate nondegeneracy condition, can be used to define one of the variables as a function of the other n − 1 variables. Here we will consider the implicit function theorem in the real analytic category (see [11], page 35 and [12]). We will use the following notation: a multiindex α is an element of ℕ^{m}. Set

|α| = |α_{1} + … + α_{m}|.

We will write 0 to mean the multiindex (0, …, 0).

Theorem 3. (Implicit Function Theorem) Suppose the power series

F (x_{1}, …, x_{r}, y) = ∑_{|α|≥0,k≥0} a_{α,k}x_{1}^{α_{1}} ⋯ x_{r}^{α_{r}}y^{k}

is absolutely convergent for |x_{1}| + … + |x_{r}| ≤ R_{1}, |y| ≤ R_{2}. If

a_{0,0} = 0 and a_{0,1} ≠ 0

then there exist r_{0} > 0 and a power series

(15)  f(x_{1}, …, x_{r}) = ∑_{|α|>0} c_{α}x_{1}^{α_{1}} ⋯ x_{r}^{α_{r}}

such that (15) is absolutely convergent for |x_{1}| + … + |x_{r}| ≤ r_{0} and

F (x_{1}, …, x_{r}, f(x_{1}, …, x_{r})) = 0.

Moreover: if the coefficients of F are algebraic, then the coefficients of f are also algebraic.

Observe that it is clear that the same holds in a more general form. Suppose that F (x_{1}, …, x_{r}, y) converges absolutely for |x_{1}| + … + |x_{r}| ≤ R_{1} and that |y −y_{0}| ≤ R_{2} for some y_{0} ∈ \overline{ℚ} with F (0, …, 0, y_{0}) = 0. Then under the assumption that

\frac{∂F}{∂y} (0, …, 0, y_{0}) ≠ 0.

the conclusion is that there exists a power series

f(x_{1}, …, x_{r}) = ∑_{|α|≥0} c_{α}x_{1}^{α_{1}} ⋯ x_{r}^{α_{r}}

for which the same as above holds.

4. Proof of the Main Theorem

In the sequel C_{1}, C_{2}, … will denote positive numbers depending only on the coefficients and roots of G_{n}^{(0)}, …, G_{n}^{(d)}.

According to Lemma 1 the number of solutions of our equation

G_{n}^{(0)}y^{d} + … + G_{n}^{(d)} = 0

of the form (n, 0), n ∈ ℕ can be estimated by

t^{(d)}.

Moreover, the set N of solutions of

G_{n}^{(0)} = G_{n}^{(1)} = … = G_{n}^{(d)} = 0

leads trivially to finitely many families of solutions of the form (n, y), with n ∈ N , y ∈ ℤ. Consequently, we can restrict ourselves to solutions of the form (n, y) ∈ ℕ × ℤ with n ∉ N and y ≠ 0, i.e. to solutions (n, z) ∈ (ℕ\N) × K of

(16)  g_{f}(γ_{1}^{n}, …, γ_{r}^{n}, z) = 0

with z ≠ 0, where K is the number field generated by the coefficients of G_{n}^{(0)}, …, G_{n}^{(d)}, and by

α, α_{1}^{(0)^{\frac{1}{d}}} .

From now on we will look at a subsequence of such solutions, which we will denote by (n, y_{n}) ∈ ℕ × ℤ (respectively (n, z_{n}) ∈ ℕ × K) with n ∈ Σ, where Σ is a set of positive integers.

First, we show that the sequence (z_{n})_{n∈Σ} must be bounded. Assume that this is not the case. We can write (see Lemma 2)

g_{f}(x_{1}, …, x_{r}, z) = (1 + p_{0}(x_{1}, …, x_{r}))z^{d} + … + p_{d}(x_{1}, …, x_{r})

with polynomials p_{i}(x_{1}, …, x_{r}) for which p_{0}(0, …, 0) = 0 holds. Dividing by z_{n}^{d−1}, we get

(1 + p_{0}(γ_{1}^{n}, …, γ_{r}^{n}))z_{n} = = −p_{1}(γ_{1}^{n}, …, γ_{r}^{n}) − p_{2}(γ_{1}^{n}, …, γ_{r}^{n})z_{n}^{−1} − … − p_{d}(γ_{1}^{n}, …, γ_{r}^{n})z_{n}^{−d+1}.

From this it follows that there exist constants d_{1}, d_{2} such that we have

d_{1} ≤ |(1 + p_{0}(γ_{1}^{n}, …, γ_{r}^{n}))z_{n}| ≤ d_{2}.

Since

1 + p_{0}(γ_{1}^{n}, …, γ_{r}^{n}) ⟶ 1, for n ⟶ ∞,

we conclude that z_{n} is bounded, which is a contradiction.

From this discussion it follows that all solutions (n, z_{n}) lie in the union of arbitrarily small neighborhoods of the solutions of

g_{f}(0, …, 0, z) = 0,

at least if n is large enough. In what follows we will only consider those n, lying in a subsequence R ⊆ Σ, for which z_{n} converges.

Now by (10), Remark 2 and the Implicit Function Theorem 3 we can conclude that

z = z_{0} + ∑_{|i|>0} a_{i}x_{1}^{i_{1}} … x_{r}^{i_{r}}

with a_{i} ∈ \overline{ℚ}, where z_{0} satisfies g_{f}(0, …, 0, z_{0}) = 0. This series converges around the point (x_{1}, …, x_{r}) = (0, …, 0). Therefore for each solution (n, z_{n}) of (16) with n ∈ R sufficiently large, we get

z_{n} = z_{0} + ∑_{|i|>0} a_{i}γ_{1}^{i_{1}n} … γ_{r}^{i_{r}n},

for some z_{0} and coefficients a_{i}, and if n is large enough.

Next we are going to approximate z_{n} by a finite sum extracted from the above expansion. We define

V_{n} := z_{0} + ∑_{0<|i|<H} a_{i}γ_{1}^{i_{1}n} … γ_{r}^{i_{r}n},

where H ≥ 1 is an integer to be chosen later. We may write

V_{n} = z_{0} + ∑_{j=1}^{h−1} c_{j}β_{j}^{n}, n ∈ R,

where c_{j} ∈ \overline{ℚ} and the β_{j} are distinct, less than 1, and lie in the multiplicative group A. Clearly V_{n} is nondegenerate. Moreover, we have

h ≤ H^{r}.

We enlarge K at once and assume that it contains all the coefficients c_{j}.

Observe that we can approximate the error we make by approximating z_{n} by V_{n}. We have

|z_{n} − V_{n}| ≤ C_{1} max{γ_{1}, …, γ_{r}}^{Hn} = C_{1}C_{2}^{Hn},

because we have

z − z_{0} − ∑_{0<|i|<H} a_{i}x_{1}^{i_{1}} … x_{r}^{i_{r}} = O (max{x_{1}, …, x_{r}}^{H}) .

We want to point out that C_{2} := max{γ_{1}, …, γ_{r}} < 1.

For later purpose we need an estimate of the K-height of z_{n}. We derive first an estimate for H_{K}(y_{n}). Observe that we have

|y_{n}| ≤ C_{3} \frac{α^{n}}{α_{1}^{(0)^{\frac{n}{d}}}} ,

since |z_{n}| is bounded. Therefore, we get

H_{K}(y_{n}) = H_{ℚ}(y_{n})^{[K:ℚ]} = |y_{n}|^{[K:ℚ]} ≤ C_{4}C_{5}^{n}.

By our relation

z_{n} = \frac{α_{1}^{(0)^{\frac{n}{d}}}}{α^{n}} y_{n}

and the fact that the height of a product can be bounded by the product of the heights we conclude

H_{K}(z_{n}) ≤ C_{4}H_{K}(\frac{α_{1}^{(0)^{\frac{1}{d}}}}{α} )^{n}C_{5}^{n} = C_{6}C_{7}^{n}.

Observe that we need here that y_{n} ∈ ℤ.

We choose H so that

(17)  C_{2}^{H}C_{7} < 1.

From now on H is fixed and therefore also h, c_{i}, β_{i} for i = 1, …, h are fixed. We choose a finite set S of absolute values of K so that it contains all infinite absolute values. Moreover we require that all α_{i}^{(j)}, i = 1, …, t^{(j)}, j = 0, …, d are S-units. In particular, with this choice all the β_{j} are S-units. Also, the z_{n} are S-units, in view of the relation

y_{n} = \frac{α^{n}}{α_{1}^{(0)^{\frac{n}{d}}}} z_{n}

and the fact that the y_{n} are integers.

We shall apply the Subspace Theorem 2, so let us define, for every v ∈ S, h + 1 independent linear forms in X := (X_{0}, …, X_{h}) as follows: put

L_{0,∞}(X) = −X_{0} + X_{1} + c_{1}X_{2} … + c_{h−1}X_{h},

and for v ∈ S, 0 ≤ i ≤ h, (i, v) ≠ (0, ∞) put

L_{i,v}(X) = X_{i}.

Here ∞ denotes the infinite absolute value, which coincides with the complex absolute value in the embedding of K in ℂ. For n ∈ R define the vectors

x_{n} = (−z_{n}, 1, β_{1}^{n}, …, β_{h−1}^{n}) ∈ (O_{K})^{h+1}

and consider the double product

∏_{v∈S} ∏_{i=0}^{h} |L_{i,v}(x_{n})|_{v}.

By putting

σ = −z_{n} + z_{0} + c_{1}β_{1}^{n} + … + c_{h−1}β_{h−1}^{n} = L_{0,∞}(x_{n}),

we can rewrite the double product as

|σ|_{∞} ( ∏_{v∈S\{∞}} | − z_{n}|_{v}) (∏_{v∈S} ∏_{i=1}^{h−1} |β_{i}|_{v}) .

Observe that the β_{i} are S-units for i ≥ 1. In particular, this implies by the Product formula (12)

(∏_{v∈S} ∏_{i=1}^{h−1} |β_{i}^{n}|_{v}) = 1.

Moreover, we get

( ∏_{v∈S\{∞}} | − z_{n}|_{v}) ≤ H_{K}(z_{n}) ≤ C_{6}C_{7}^{n}.

Therefore we have

∏_{v∈S} ∏_{i=0}^{h} |L_{i,v}(x_{n})|_{v} ≤ C_{1}C_{6} (C_{2}^{H}C_{7})^{n} ,

where we have used the bound for the approximation error.

Last we need an upper bound for H(x_{n}). We have

(18)  H(x_{n}) ≤ H_{K}(z_{n})H_{K}(β_{1})^{n} … H_{K}(β_{h−1})^{n} ≤ C_{8}C_{9}^{n}.

Note that the constants do not depend on n.

We now choose δ so that

(19)  C_{2}^{H}C_{7}C_{9}^{δ} < 1.

This will be possible for small δ in view of (17).

In view of the bound for the double product we derived and (18), the verification of (13) of the Subspace Theorem 2 will follow from

C_{1}C_{6} (C_{2}^{H}C_{7})^{n} < (C_{8}C_{9}^{n})^{−δ} ,

which is the same as

(C_{2}^{H}C_{7}C_{9}^{δ})^{n} < (C_{1}C_{6}C_{8}^{δ})^{−1} .

However, this inequality follows from (19) for n large enough.

Therefore, by the Subspace Theorem 2, there exist finitely many non-zero linear forms Λ_{1}(X), …, Λ_{g}(X) with coefficients in \overline{ℚ} such that each vector x_{n} is a zero of some Λ_{j}.

Now we have to consider two different cases depending on whether Λ_{j} depends on X_{0} or not. Since the arguments are analogous, it is enough to consider Λ := Λ_{1}.

Suppose first Λ does not depend on X_{0}. Then, if Λ(x_{n}) = 0, we have a nontrivial relation

u_{0} + ∑_{i=1}^{h−1} u_{i}β_{i}^{n} = 0, u_{i} ∈ \overline{ℚ}, i = 0, …, h − 1.

By Lemma 1 this can hold for at most a finite number of n.

Suppose that Λ depends on X_{0} and that Λ(x_{n}) = 0. Then we have

(20)  z_{n} = v_{0} + ∑_{i=1}^{h−1} v_{i}β_{i}^{n}, v_{i} ∈ \overline{ℚ}, i = 0, …, h − 1.

Substituting this into g_{f}(x_{1}, …, x_{r}, z) = 0 we get

g_{f} (γ_{1}^{n}, …, γ_{r}^{n}, v_{0} + ∑_{i=1}^{h−1} v_{i}β_{i}^{n}) = 0

and consequently

f (G_{n}^{(0)}, …, G_{n}^{(d)}, v_{0} \frac{α^{n}}{α_{1}^{(0)^{\frac{n}{d}}}} + ∑_{i=1}^{h−1} v_{i} (\frac{β_{i}α}{α_{1}^{(0)^{\frac{1}{d}}}} )^{n}) = 0.

This equation can either hold for infinitely many n (and in this case by the theorem of Skolem-Mahler-Lech for all n in a suitable arithmetic progression P) or does not hold as an identity. The first case leads to the power sum

H_{n} = v_{0} \frac{α^{n}}{α_{1}^{(0)^{\frac{n}{d}}}} + ∑_{i=1}^{h−1} v_{i} (\frac{β_{i}α}{α_{1}^{(0)^{\frac{1}{d}}}} )^{n} ,

having the property that (n, H_{n}) is a solution for all n in the above arithmetic progression. Observe that H_{n} is in \overline{ℚ}E_{A}. But in the intersection of the arithmetic progressions {m(di) + k : m ∈ ℕ} ∩ P =: P_{k} for 0 ≤ k < di (where i is the index for which the maximum in the definition of α is obtained), the power sum H_{n} has positive rational roots. By taking conjugates, we immediately see that in fact the coefficients must be rationals too. But now by Lemma 1, page 322 in [4] it follows, since H_{n} ∈ ℤ for all n in the above intersection of arithmetic progressions, which is again an arithmetic progression, that

H̃_{n} := H_{n∈P_{k}} ∈ E_{ℤ}^{+}.

The second case can only hold for finitely many n again by Lemma 1. Therefore the proof is finished. □

5. Proof of the Corollaries

Let us notice that the assumption that the polynomial f is monic excludes the existence of families of solutions of the type (n, y) with arbitrary y (the second “trivial” infinite family in Theorem 1).

Proof of Corollary 1 In this case it is clear that we have

α = α_{1}^{(d−1)^{\frac{1}{d−1}}} ,

as dominating root in the equation

y^{d} + G_{n}^{(1)}y^{d−1} + … + G_{n}^{(d)} = 0.

We therefore substitute

y = α^{n}z.

Then all the roots of

\frac{1}{α^{dn}} f(1, G_{n}^{(1)}, …, G_{n}^{(d)}, α^{n}z)

are ≤ 1, and the only roots = 1 appear as coefficients of y^{d} and y. Let γ_{1}, …, γ_{r} be all different roots < 1. Then we get

g_{f}(0, …, 0, z) = z^{d} + a_{1}^{(d−1)}z = z(z^{d−1} + a_{1}^{(d−1)}),

which has only simple roots, and thus we can apply Theorem 1. From this the conclusion follows. □

Proof of Corollary 2 Our intention is to reduce the equation

y^{3} + G_{n}^{(1)}y + G_{n}^{(2)} = 0

to equations for which Theorem 1 can be applied and from this we get the conclusion. For short we denote the dominating roots of G_{n}^{(1)}, G_{n}^{(2)} by α, β, respectively. There are three cases to consider: α^{3} < β^{2}, α^{3} > β^{2} or α^{3} = β^{2}.

Assume that α^{3} > β^{2}. We substitute

y = α^{\frac{n}{2}} z.

Thus, we get

α^{\frac{3n}{2}} z^{3} + [a_{1}^{(1)}α^{\frac{3n}{2}} + ⋯] z + a_{1}^{(2)}β^{n} + … = 0,

where the roots in the dotted part are all

< α^{\frac{3n}{2}} .

Dividing through by this number implies

z^{3} + [a_{1}^{(1)} + …]z + a_{1}^{(2)} (\frac{β}{α^{\frac{3}{2}}} )^{n} + … = 0.

Thus

g_{f}(0, 0, z) = z(z^{2} + a_{1}^{(1)}),

which has only simple roots and consequently Theorem 1 can be applied to this situation.

Now assume that β^{2} ≥ α^{3} holds. We substitute

y = β^{\frac{n}{3}} z

and therefore get

β^{n}z^{3} + [a_{1}^{(1)}α^{n}β^{\frac{n}{3}} + …] z + a_{1}^{(2)}β^{n} + … = 0.

Dividing through by β^{n} gives

z^{3} + [a_{1}^{(1)} (\frac{α}{β^{\frac{2}{3}}} )^{n} + …] z + a_{1}^{(2)} + … = 0,

where again in the part not written down only roots < 1 appear. Now we have to consider the cases β^{2} > α^{3} and β^{2} = α^{3} separately.

If β^{2} > α^{3} then we get

g_{f}(0, …, 0, z) = z^{3} + a_{1}^{(1)}z,

which has only simple roots and therefore Theorem 1 can be applied.

If β^{2} = α^{3} we get

g_{f}(0, …, 0, z) = z^{3} + a_{1}^{(1)}z + a_{1}^{(2)},

and this cubic polynomial has only simple roots when

4a_{1}^{(1)^{3}} + 27a_{1}^{(2)^{2}} ≠ 0

holds. Therefore the proof is finished. □

Proof of Corollary 3 First we have to consider, whether there exists H_{n} ∈ \overline{ℚ}E\overline{ℚ} with

H_{n}^{3} + aα^{n}H_{n} + bβ^{n} = 0

for all n in an arithmetic progression. Let H_{n} be a power sums with this property. Then it follows

H_{n}(H_{n}^{2} + aα^{n}) = −bβ^{n}

and therefore H_{n} divides bβ^{n} in the ring \overline{ℚ}E\overline{ℚ}. Since the units of this ring are of the form cγ^{n} we can conclude (since H_{n} divides a unit) that

H_{n} = cγ^{n}

with c, γ ∈ \overline{ℚ}. In fact we have that γ is in the multiplicative group generated by α, β. Hence, we have to consider

c^{3}γ^{3n} + ac(αγ)^{n} + bβ^{n} = 0.

This equations has infinitely many solutions only in the case when γ^{3} = β, γ^{2} = α and α^{3} = β^{2}, because otherwise at least two elements of the set {γ^{3}, αγ, β} would be different and therefore the equation would have finitely many solutions by Lemma 1. In this case the equation becomes

(c^{3} + ac + b)β^{n} = 0,

which either has no solution or is true identically if c^{3} + ac + b = 0.

Thus, by Corollary 2, for α^{3} ≠ β^{2} the conclusion follows. In the case α^{3} = β^{2} our equation reduces via the transformation

y = β^{\frac{n}{3}} z

and diving through by β^{n} to

z^{3} + az + b = 0.

This in turn means that there are at most 3 possible values for z and each of them induces as above the (simple) power sums

β^{\frac{n}{3}} z_{0}.

Therefore, the proof is finished. □

6. Acknowledgement

The authors are grateful to Prof. P. Corvaja for bringing this problem to their attention and for valuable comments and remarks.

References

[1] S. Ahlgren, Polynomial-exponential equations in two variables, J. Number Theory 62 (1997), no. 2, 428-438.

[2] S. Ahlgren, Equations F (x, y, α^{x}) = 0, Topics in number theory (University Park, PA, 1997), 85-100, Math. Appl. 467, Kluwer Acad. Publ., Dordrecht, 1999.

[3] J. Cel, The Newton-Puiseux theorem for several variables, Bull. Soc. Sci. Let. Łódź 40 (1990), no. 11-20, 53-61.

[4] P. Corvaja and U. Zannier, Diophantine equations with power sums and universal Hilbert sets, Indag. Math., New Ser. 9 (3) (1998), 317-332.

[5] P. Corvaja and U. Zannier, On the diophantine equation f(a^{m}, y) = b^{n}, Acta Arith. 94 (2002), 25-40.

[6] P. Corvaja and U. Zannier, Some new applications of the Subspace Theorem, Compos. Math. 131 (2002), no. 3, 319-340.

[7] J.-H. Evertse, An improvement of the Quantitative Subspace Theorem, Compos. Math. 101 (3) (1996), 225-311.

[8] C. Fuchs, Exponential-polynomial equations and linear recurring sequences, PhDthesis, TU Graz (2002), 34-54; Glas. Mat. Ser. III, to appear.

[9] C. Fuchs, An upper bound for the G.C.D. of two linear recurring sequences, Math. Slovaca 53 (2003), No. 1, 21-42.

[10] C. Fuchs and R. F. Tichy, Perfect powers in linear recurring sequences, Acta Arith. 107.1 (2003), 9-25.

[11] S. G. Krantz and H. R. Parks, “A Primer of Real Analytic Functions”, Second Ed., Birkhäuser, Boston, 2002.

[12] S. G. Krantz and H. R. Parks, “The Implicit Function Theorem: History, Theory, and Applications”, Birkhäuser, Boston, 2002.

[13] A. Pethő, Diophantine properties of linear recursive sequences I, Bergum, G. E. (ed.) et al., Applications of Fibonacci numbers. Volume 7: Proceedings of the 7th international research conference on Fibonacci numbers and their applications, Graz, Austria, July 15-19, 1996, Kluwer Academic Publ., Dordrecht (1998), 295-309.

[14] A. Pethő, Diophantine properties of linear recursive sequences II, Acta Math. Acad. Paed. Nyiregyháziensis 17 (2001), 81-96.

[15] A. J. van der Poorten, Some facts that should be better known, especially about rational functions, Number Theory and Applications (Banff, AB, 1988), 497-528, Kluwer Acad. Publ., Dordrecht, 1989.

[16] W. M. Schmidt, “Diophantine Approximation”, Springer Verlag, LN 785, 1980.

[17] W. M. Schmidt, “Diophantine Approximations and Diophantine Equations”, Springer Verlag, LN 1467, 1991.

[18] W. M. Schmidt, Equations α^{x} = R(x, y), J. Number Theory 47 (1994), 348-358.

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

[20] A. Scremin, Diophantine inequalities with power sums, J. Théor. Nombres Bordeaux, to appear.

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

Amedeo Scremin Institut für Mathematik TU Graz Steyrergasse 30 A-8010 Graz, Austria e-mail: scremin@finanz.math.tu-graz.ac.at