Concatenations with Binary Recurrent Sequences

William D. Banks Department of Mathematics University of Missouri Columbia, MO 65211 USA

               bbanks@math.missouri.edu

Florian Luca Instituto de Matemáticas Universidad Nacional Autónoma de México C.P. 58180 Morelia, Michoacán México

                 fluca@matmor.unam.mx

Abstract

Given positive integers A_{1}, …, A_{t} and b ≥ 2, we write \overline{A_{1} ⋯ A_{t}}_{(b)} for the integer whose base-b representation is the concatenation of the base-b representations of A_{1}, …, A_{t}. In this paper, we prove that if (u_{n})_{n≥0} is a binary recurrent sequence of integers satisfying some mild hypotheses, then for every fixed integer t ≥ 1, there are at most finitely many nonnegative integers n_{1}, …, n_{t} such that \overline{|u_{n_{1}}| ⋯ |u_{n_{t}}|}_{(b)} is a member of the sequence (|u_{n}|)_{n≥0}. In particular, we compute all such instances in the special case that b = 10, t = 2, and u_{n} = F_{n} is the sequence of Fibonacci numbers.

1 Introduction

A result of Senge and Straus [24, 25] asserts that if b_{1}, b_{2} ≥ 2 are multiplicatively independent integers, there are at most finitely many positive integers with the property that the sum of the digits in each of the two bases b_{1} and b_{2} lies below any prescribed bound. An effective version of this statement is due to Stewart [28], who gave a lower bound on the overall sum of the digits of n in base b_{1} and in base b_{2}. A somewhat more general version of Stewart’s result has been obtained by Luca [16].

A variety of arithmetical questions about integers whose base-b digits satisfy certain restrictions has been considered by many authors; see, for example, [1, 2, 3, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 16, 18, 19, 27] and the references contained therein. Here, we consider integers whose base-b digits are formed by concatenating (absolute values of) terms in a binary recurrent sequence.

Let (u_{n})_{n≥0} be a binary recurrent sequence of integers; i.e., a sequence of integers satisfying the recurrence relation

u_{n+2} = ru_{n+1} + su_{n}  (n ≥ 0),  (1)

where r and s are nonzero integers with r^{2} + 4s ≠ 0. It is well known that if α and β are the roots of the equation x^{2} − rx − s = 0, then u_{n} = cα^{n} + dβ^{n} holds for all n ≥ 0, where c and d are constants given by

c = \frac{−βu_{0} + u_{1}}{α − β} and d = \frac{αu_{0} − u_{1}}{α − β} .

Throughout the paper, we assume that (u_{n})_{n≥0} is nondegenerate (i.e., α/β is not a root of 1, and αβcd ≠ 0). Reordering the roots if necessary, we can further assume that |α| ≥ |β| and |α| > 1.

Let b ≥ 2 be a fixed integer base. Given positive integers A_{1}, …, A_{t}, we denote by \overline{A_{1} ⋯ A_{t}}_{(b)} the integer whose base-b representation is equal to the concatenation (in order) of the base-b representations of A_{1}, …, A_{t}. Thus, if l_{i} is the smallest positive integer such that A_{i} < b^{l_{i}}, we have

\overline{A_{1} ⋯ A_{t}}_{(b)} = b^{l_{2}+···+l_{t}}A_{1} + b^{l_{3}+···+l_{t}}A_{2} + ⋯ + b^{l_{t}}A_{t−1} + A_{t} .

We always assume that A_{1} ≠ 0, and in the special case that b = 10, we omit the subscript to simplify the notation.

In this paper, we study the set of positive integers |u_{n}|, where (u_{n})_{n≥0} is a binary recurrent sequence, that are the base-b concatenations of other numbers of the form |u_{n_{j}}|, j = 1, …, t. We show that if t ≥ 2 is fixed, then there are only finitely many instances of the equality

|u_{n}| = \overline{|u_{n_{1}}| ⋯ |u_{n_{t}}|}_{(b)}

provided that the sequence (u_{n})_{n≥0} satisfies certain mild hypotheses. Note that some assumptions are clearly needed in order to rule out certain obvious counterexamples; for instance, the result does not hold for the sequence u_{n} = b^{n} − 1, n ≥ 0, since the concatenation of any two or more terms produces another term of the same sequence.

Theorem 1. Let u_{n} = cα^{n} + dβ^{n} be a nondegenerate binary recurrent sequence of integers, and let b ≥ 2 be a fixed integer base. Assume that dim_{ℤ}⟨log α, log β, log b⟩ ≥ 2. Then for every fixed integer t ≥ 2, there are at most finitely many positive integers n for which the equality

|u_{n}| = \overline{|u_{n_{1}}| \underbrace{0 ⋯ 0}_{m_{1}} |u_{n_{2}}| \underbrace{0 ⋯ 0}_{m_{2}} ⋯ |u_{n_{t}}| \underbrace{0 ⋯ 0}_{m_{t}}} _{(b)}  (2)

holds for some nonnegative integers n_{1}, …, n_{t} and m_{1}, …, m_{t} with u_{n_{1}} ≠ 0.

Here, log(·) stands for any fixed determination of the natural logarithm function, and dim_{ℤ}⟨log α, log β, log b⟩ denotes the rank of (the free part of) the additive subgroup of ℂ generated by {log α, log β, log b}.

Although our proof of Theorem 1 is ineffective, this result can be seen as an extension of the aforementioned results of Senge and Straus [24, 25].

In some special cases, one can employ effective methods to completely determine all the solutions to an equation such as (2). Perhaps the best known example of a binary recurrent sequence is the Fibonacci sequence (F_{n})_{n≥0}, where F_{0} = 0 and F_{1} = 1, and (1) holds with r = s = 1. In this case, one has α = (1 + \sqrt{5})/2, β = −α^{−1}, c = 1/(α − β), and d = −c. For this special sequence, we obtain the following computational result:

Theorem 2. If (m, n, k) is an ordered triple of nonnegative integers with m > 0 and \overline{F_{m}F_{n}} = F_{k}, then F_{k} ∈ {13, 21, 55}.

Throughout the paper, we use the Vinogradov symbols ≪ and ≫, as well as the Landau symbol O, with the understanding that the implied constants are computable and depend at most on the given data.

2 Preliminaries

Let 𝕃 be an algebraic number field of degree D over ℚ. Denote by O_{𝕃} the ring of algebraic integers and by M_{𝕃} the set of places. For a fractional ideal I of 𝕃, let Nm_{𝕃}(I) be the usual norm; we recall that Nm_{𝕃}(I) = #(O_{𝕃}/I) if I is an ideal of O_{𝕃}, and the norm map is extended multiplicatively (using unique factorization) to all of the fractional ideals of 𝕃.

For a prime ideal P, we denote by ord_{P}(x) the order at which P appears in the ideal factorization of the principal ideal [x] generated by x in 𝕃.

For a place μ ∈ M_{𝕃} and a number x ∈ 𝕃, we define the absolute value |x|_{μ} as follows:

(i) |x|_{μ} = |σ(x)|^{1/D} if μ corresponds to a real embedding σ : 𝕃 → ℝ;

(ii) |x|_{μ} = |σ(x)|^{2/D} = |\overline{σ}(x)|^{2/D} if μ corresponds to some pair of complex conjugate embeddings σ, \overline{σ} : 𝕃 → ℂ;

(iii) |x|_{μ} = Nm_{𝕃}(P)^{−ord_{P}(x)/D} if μ corresponds to a nonzero prime ideal P of O_{𝕃}.

In the case (i) or (ii), we say that μ is real infinite or complex infinite, respectively; in the case (iii), we say that μ is finite.

The set of absolute values are well known to satisfy the following product formula:

∏_{μ∈M_{𝕃}} |x|_{μ} = 1,  for all x ∈ 𝕃^{∗}.  (3)

One of our principal tools is the following simplified version of a result of Schlickewei [22, 23], which is commonly known as the Subspace Theorem:

Theorem 3. Let 𝕃 be an algebraic number field of degree D. Let S be a finite set of places of 𝕃 containing all the infinite ones. Let {L_{1,μ}, …, L_{N,μ}} for μ ∈ S be linearly independent sets of linear forms in N variables with coefficients in 𝕃. Then, for every fixed 0 < ε < 1, the set of solutions x = (x_{1}, …, x_{N}) ∈ 𝕃^{N}\{0} to the inequality

∏_{μ∈S} ∏_{i=1}^{N} |L_{i,μ}(x)|_{μ} ≤ (max{|x_{i}| : i = 1, …, N})^{−ε}  (4)

is contained in finitely many proper linear subspaces of 𝕃^{N}.

Let S be a finite subset of M_{𝕃} containing all the infinite places. An element x ∈ 𝕃 is called a S-unit if |x|_{μ} = 1 for all μ ∉ S. An equation of the form

∑_{i=1}^{N} a_{i}x_{i} = 0,  (5)

where each a_{i} ∈ 𝕃^{∗}, is called an S-unit equation if each x_{i} is an S-unit; it is said to be nondegenerate if no proper subsum of the left hand side vanishes. It is clear that if x = (x_{1}, …, x_{N}) is a solution of the S-unit equation (5), and ρ is a S-unit in 𝕃^{∗}, then ρx = (ρx_{1}, …, ρx_{N}) is a also a solution of (5); in this case, the solutions x and ρx are said to be equivalent. We recall the following result of Schlickewei [21] (see also [8]) on S-unit equations:

Theorem 4. Let a_{1}, …, a_{N} be fixed numbers in 𝕃^{∗}. Then the S-unit equation (5) has only finitely many equivalence classes of nondegenerate solutions (x_{1}, …, x_{N}). Moreover, the number of such equivalence classes is bounded by a constant that depends only on N and the cardinality of S.

An immediate consequence of Theorem 4 is that if x = (x_{1}, …, x_{N}) is a solution of the S-unit equation (5), then the ratios x_{i}/x_{j} for 1 ≤ i < j ≤ N can assume only finitely many values.

We shall also need some estimates from the theory of lower bounds for linear forms in logarithms, both in the complex and the p-adic cases.

Let α_{1} and α_{2} be algebraic numbers. Put 𝕃 = ℚ[α_{1}, α_{2}], and let D be the degree of 𝕃 over ℚ. Let A_{1} and A_{2} be two positive integers such that

log A_{i} ≥ max \{h(α_{i}), \frac{| log α_{i}|}{D}, \frac{1}{D}\}  (i = 1, 2).  (6)

Here, for an algebraic number α whose minimal polynomial over ℤ has the form a ∏_{i=1}^{d}(X − α^{(i)}), we write h(α) for the logarithmic height of α, which is given by

h(α) = \frac{1}{d} (log |a| + ∑_{i=1}^{d} log (max\{1, |α^{(i)}|\})) .

Let b_{1} and b_{2} be positive integers, and put Λ = b_{2} log α_{2} − b_{1} log α_{1}. Finally, let

b′ = \frac{b_{1}}{D log A_{2}} + \frac{b_{2}}{D log A_{1}} .

The following result is Corollaire 2 on page 288 of [20], which gives an effective lower bound on the size of log |Λ|:

Theorem 5. Assume that α_{1} and α_{2} are real, positive, and multiplicatively independent. Then

log |Λ| ≥ −24.34D^{4} (max \{log b′ + 0.14, \frac{21}{D}, \frac{1}{2}\})^{2} log A_{1} log A_{2}.

We also need a p-adic lower bound on Λ, that is, an upper bound on the order at which a prime ideal P can appear in the factorization of the principal ideal generated by Λ_{1} = α_{1}^{b_{1}}−α_{2}^{b_{2}} inside O_{𝕃}. For this, let p be the prime number such that P | p (i.e., pℤ = P ∩ℤ), and let f be such that the finite field O_{𝕃}/P has p^{f} elements. Let g be the smallest positive integer such that P divides both α_{1}^{g} − 1 and α_{2}^{g} − 1. Assume further that A_{i} satisfies the inequality (6) as well as the inequality log A_{i} ≥ f(log p)/D, for i = 1, 2. The following result is an easy consequence of Corollaire 2 on page 315 of [4]:

Theorem 6. Assume that α_{1} and α_{2} are multiplicatively independent. Then

ord_{P} (Λ_{1}) ≤ \frac{24pgD^{5}}{f^{4}(p − 1)(log p)^{4}}
× (max \{log b′ + log log p + 0.4, \frac{10f log p}{D}, 10\})^{2} log A_{1} log A_{2}.

3 Proof of Theorem 1

Our proof of Theorem 1 also treats the (slightly more general) case in which we allow t = 1, but in this case we add the additional hypothesis that m_{1} ≥ 1 (clearly, this condition is needed to insure that the number of solutions to (2) is finite).

Since α/β is not a root of unity, at most one element of the sequence (u_{n})_{n≥0} is equal to 0. Hence, if u_{n_{i}} = 0 for some i in (2), then n_{i} is uniquely determined. Note that i ≠ 1. If this happens, then equation (2) can be viewed as an equation of the same form, but with t replaced by t − 1 (and with only 2t − 1 unknowns). Thus, to prove the theorem, it suffices to show that there at most finitely many solutions to (2) with u_{n_{i}} ≠ 0, i = 1, …, t.

Let 𝕃 = ℚ[α, β], and let S be the set of all infinite places of 𝕃 and all finite places that divide sb = −αβb. For a positive integer m, let ℓ_{b}(m) denote the number of the digits in the base-b representation of m.

Equation (2) is equivalent to

|u_{n}| = ∑_{i=1}^{t} |u_{n_{i}}|b^{s_{i}},  (7)

where

s_{i} = ∑_{j=i}^{t} m_{j} + ∑_{j=i+1}^{t} ℓ_{b}(|u_{n_{j}}|) (i = 1, …, t).

We remark that, if n = n_{i} for some i, it follows that t = 1 (since each u_{n_{i}} ≠ 0) and s_{1} = m_{1} = 0 (since b ≥ 2), which contradicts our assumption that m_{1} ≥ 1 when t = 1. Hence, n ≠ n_{i} for all i = 1, …, t. Now write (7) in the form

ε_{0}(cα^{n} + dβ^{n}) = ∑_{i=1}^{t} ε_{i} (cα^{n_{i}} + dβ^{n_{i}}) b^{s_{i}},  (8)

where ε_{i} ∈ {±1} for i = 0, …, t.

Suppose first that n_{i} > n − κ for some i ∈ {1, …, t}, where κ ≥ 0 is a constant to be specified later. From (7), we have that |u_{n}| ≥ |u_{n_{i}}|b^{s_{i}}. It is known that the estimate |u_{m}| = |α|^{m+O(log m)} holds for all positive integers m ≥ 2 (see Theorem 3.1 on page 64 in [26]). Moreover, if α is real, then |α| > |β|, and one has the estimate |u_{m}| = |α|^{m+O(1)}. Therefore, since |α| > 1, the following bound holds if n_{i} > n − κ:

max\{n_{i} − n, s_{i}\} ≪ \{ \begin{matrix}1, & if α ∈ ℝ; \\ log n, & if α ∉ ℝ (i.e., α = \overline{β}). \end{matrix}  (9)

Next, we show that if n_{i} ≤ n − κ for every i = 1, …, t, then there exists an index i ∈ {1, …, t} for which the following bound holds:

max{n − n_{i}, s_{i}} ≪ 1.  (10)

To do this, we first observe that (8) is an S-unit equation with N = 2t + 2 terms, coefficients (a_{1}, …, a_{N}) = (c, d, −c, −d, …, −c, −d), and the S-unit unknowns x = (x_{1}, …, x_{N}) = (ε_{0}α^{n}, ε_{0}β^{n}, ε_{1}α^{n_{1}}b^{s_{1}}, …, ε_{t}β^{n_{t}}b^{s_{t}}).

If the S-unit equation (8) is nondegenerate, then x_{1}/x_{2} = (α/β)^{n} can assume only finitely many values; since α/β is not a root of unity, it follows that n can take at most finitely many values.

On the other hand, if the S-unit equation (8) is degenerate, let E_{1} and E_{2} be two (not necessarily distinct) nondegenerate subequations of (8) that contain the unknowns x_{1} = ε_{0}α^{n} and x_{2} = ε_{0}β^{n}, respectively. Clearly, E_{1} and E_{2} can be chosen in at most finitely many ways. The preceding argument shows that n can assume only finitely many values if the unknowns x_{1} and x_{2} both lie in E_{1} or both lie in E_{2}. Therefore, we may assume that E_{1} does not contain x_{2}, and E_{2} does not contain x_{1}. We now distinguish the following cases:

(i) E_{1} contains an unknown of the form x_{2i+1} = ε_{i}α^{n_{i}}b^{s_{i}} for some i ≥ 1 and E_{2} contains an unknown of the form x_{2j} = ε_{j}β^{n_{j}}b^{s_{j}} for some j ≥ 2.

In this case, both x_{1}/x_{2i+1} = ±α^{n−n_{i}}b^{−s_{i}} and x_{2}/x_{2j} = ±β^{n−n_{j}}b^{−s_{j}} can assume only finitely many values. Since dim_{ℤ}⟨log α, log β, log b⟩ ≥ 2, it follows that either the pair (α, b) or the pair (β, b) is multiplicatively independent. Hence, either max{n−n_{i}, s_{i}} ≪ 1 or max{n − n_{j}, s_{j}} ≪ 1.

(ii) E_{1} contains only unknowns of the form x_{2i} = ε_{i}β^{n_{i}}b^{s_{i}} with i ≥ 2 (except for x_{1}) and E_{2} contains only unknowns of the form x_{2j+1} = ε_{j}α^{n_{j}}b^{s_{j}} with j ≥ 1 (except for x_{2}).

For each choice of the indices i and j, both x_{1}/x_{2i} = ±α^{n}β^{−n_{i}}b^{−s_{i}} and x_{2}/x_{2j+1} = ±β^{n}α^{−n_{j}}b^{−s_{j}} can have at most finitely many values. Since we may assume that n takes infinitely many values (otherwise, there is nothing to prove), it follows that there exist numbers n^{∗}, n_{i}^{∗}, n_{j}^{∗}, s_{i}^{∗}, and s_{j}^{∗} such that both relations

\begin{aligned}α^{n}β^{−n_{i}}b^{−s_{i}} & = α^{n^{∗}}β^{−n_{i}^{∗}}b^{−s_{i}^{∗}}, \\ β^{n}α^{−n_{j}}b^{−s_{j}} & = β^{n^{∗}}α^{−n_{j}^{∗}}b^{−s_{j}^{∗}}, \end{aligned}  (11)

hold for arbitrarily large values of n. Among all possible choices for the quintuple (n^{∗}, n_{i}^{∗}, n_{j}^{∗}, s_{i}^{∗}, s_{j}^{∗}) of such numbers, we fix one for which n_{i}^{∗} is as small as possible; thus, n_{i} ≥ n_{i}^{∗} whenever the relations (11) hold.

Since there are only finitely many possibilities for E_{1} and E_{2} and (once these are fixed) for the indices i and j, we obtain in this way a finite list of such quintuples (n^{∗}, n_{i}^{∗}, n_{j}^{∗}, s_{i}^{∗}, s_{j}^{∗}). Hence, the constant κ can be initially chosen such that the inequality κ > max{n^{∗} − n_{i}^{∗}, n^{∗} − n_{j}^{∗}} holds in all cases.

Now let E_{1}, E_{2}, i, and j be fixed, and suppose that the relations (11) hold with n > n^{∗}. Taking logarithms, we obtain that

(n − n^{∗}) log α = (n_{i} − n_{i}^{∗}) log β + (s_{i} − s_{i}^{∗}) log b,
(n − n^{∗}) log β = (n_{j} − n_{j}^{∗}) log α + (s_{j} − s_{j}^{∗}) log b.

Let v_{1} = (n_{i} − n_{i}^{∗})/(n − n^{∗}) and v_{2} = (n_{j} − n_{j}^{∗})/(n − n^{∗}), and note that both numbers are rational. Since we are assuming that n_{i} ≤ n − κ for i = 1, …, t, it follows that

n^{∗} − n_{i}^{∗} < κ ≤ n − n_{i},

which implies that v_{1} < 1. Similarly, v_{2} < 1. Since n_{i} ≥ n_{i}^{∗} by our choice of the quintuple (n^{∗}, n_{i}^{∗}, n_{j}^{∗}, s_{i}^{∗}, s_{j}^{∗}), we also see that v_{1} ≥ 0. These statements together imply that v_{1}v_{2} ≠ 1, which is all we need. From the preceding relations, we obtain that

log α = v_{1} log β + w_{1} log b = v_{1}(v_{2} log α + w_{2} log b) + w_{1} log b,

where w_{1} = (s_{i} − s_{i}^{∗})/(n − n^{∗}) and w_{2} = (s_{j} − s_{j}^{∗})/(n − n^{∗}) are rational numbers. Since v_{1}v_{2} ≠ 1, this implies that log α/ log b is rational. Similarly, we see that log β/ log b is rational. But these statements contradict our hypothesis that dim_{ℤ}⟨log α, log β, log b⟩ ≥ 2; therefore, n is bounded, and it follows that n_{i}, n_{j}, s_{i}, and s_{j} are bounded as well.

(iii) The remaining cases.

For the remaining cases, there are only two possibilities:

• E_{1} contains an unknown of the form x_{2i+1} = ε_{i}α^{n_{i}}b^{s_{i}} for some i ≥ 1 and E_{2} contains only unknowns of the form x_{2j+1} = ε_{j}α^{n_{j}}b^{s_{j}} with j ≥ 1 (except for x_{2}).

• E_{1} contains only unknowns of the form x_{2i} = ε_{i}β^{n_{i}}b^{s_{i}} with i ≥ 2 (except for x_{1})

and E_{2} contains an unknown of the form x_{2j} = ε_{j}β^{n_{j}}b^{s_{j}} for some j ≥ 2.

We treat only the first case, as the second case is similar.

We note that the ratio x_{1}/x_{2i+1} = ±α^{n−n_{i}}b^{−s_{i}} assumes only finitely many values. If α and b are multiplicatively independent, it follows that both n − n_{i} and s_{i} are bounded, and we are done. On the other hand, if n−n_{i} is not bounded, it follows that log α/ log b is rational. If j is such that x_{2j+1} ∈ E_{2}, then x_{2}/x_{2j+1} = ±β^{n}α^{−n_{j}}b^{−s_{j}} can take at most finitely many values. Since α and b are multiplicatively dependent, β and b must be multiplicatively independent, and it follows that n can take only finitely many values. But this is impossible if n − n_{i} is unbounded.

The analysis above completes our proof that (10) holds for some i in the case that n_{i} ≤ n − κ for all i = 1, …, t. Combining (9) and (10), we see that the bound

max\{|n − n_{i}|, s_{i}\} ≪ \{ \begin{matrix}1, & if α ∈ ℝ; \\ log n, & if α ∉ ℝ (i.e., α = \overline{β}) \end{matrix}  (12)

holds for some i ∈ {1, …, t} in every case.

We now select i such that (12) holds and rewrite (8) in the form

cα^{n} + dβ^{n} + Ab^{s_{i−1}} + c_{1}α^{n_{i}}b^{s_{i}} + d_{1}β^{n_{i}}b^{s_{i}} + B = 0,  (13)

where c_{1} = −ε_{i}ε_{0}c, d_{1} = −ε_{i}ε_{0}d,

A = − ∑_{j=1}^{i−1} ε_{j}ε_{0}u_{n_{j}}b^{s_{j}−s_{i−1}} and B = − ∑_{j=i+1}^{t} ε_{i}ε_{0}u_{n_{j}}b^{s_{j}}.

Since

b^{s_{i−1}} ≥ |u_{n_{i}}| ≥ |α|^{n_{i}+O(log n_{i})} = |α|^{n+O(log n)},

we see that A = exp(O(log n)). Similarly, since b^{s_{i}} ≥ B, it follows that B = exp(O(log n)).

Assume first that both n − n_{i} and s_{i} are bounded (this is the case, for instance, if 𝕃 is real). In this case, A and B are bounded as well; hence, we can assume that they are fixed. Here, (13) becomes

C_{1}α^{n} + D_{1}β^{n} + Ab^{s_{i−1}} + B = 0,  (14)

where C_{1} = c+c_{1}α^{n_{i}−n} and D_{1} = d+d_{1}β^{n_{i}−n} can also be regarded as fixed numbers. The case A = B = C_{1} = D_{1} = 0 leads to i = t = 1, α^{n−n_{i}} = −cc_{1}^{−1} = ±1 and β^{n−n_{i}} = −dd_{1}^{−1} = ±1; therefore, t = 1, n = n_{1}, and m_{1} = 0, which contradicts our assumption that m_{1} ≥ 1 when t = 1. Consequently, the equation (14) is nontrivial. If any two of the coefficients A, B, C_{1}, D_{1} are zero, then either n or s_{i−1} is bounded, and this leads to at most finitely many possibilities for n. A similar argument based on Theorem 4 can be used if one of the coefficients A, B, C_{1}, D_{1} is zero, or if ABC_{1}D_{1} ≠ 0, to show that there are at most finitely many possibilities for n.

Thus, from now on, we can suppose that either n − n_{i} or s_{i} is unbounded over the set of solutions to (13). In this case, α and β are complex conjugates.

Assume first that B ≠ 0 in equation (13). Suppose also that A ≠ 0. We apply Theorem 3 with N = 5, the linear forms L_{j,μ}(x) = x_{j} for each j = 1, …, 5, and μ ∈ S, except when j = 1 and μ is infinite, in which case we take L_{1,μ}(x) = cx_{1} + dx_{2} + x_{3} + c_{1}x_{4} + d_{1}x_{5} (note that, as 𝕃 is complex quadratic, there is only one infinite place). We evaluate the double product appearing in Theorem 3 for our system of forms and the points x = (α^{n}, β^{n}, Ab^{s_{i−1}}, α^{n_{i}}b^{s_{i}}, β^{n_{i}}b^{s_{i}}). Clearly,

∏_{μ∈S} |L_{j,μ}(x)| = 1  (15)

if j ∈ {2, 4, 5}, since x_{2}, x_{4} and x_{5} are S-units. Moreover,

∏_{μ∈S} |L_{3,μ}(x)| ≤ A = exp(O(log n)).  (16)

Finally, since x_{1} is an S-unit, it follows from the product formula (3) that

∏_{\begin{matrix}μ∈S \\ μ finite \end{matrix}} |L_{1,μ}(x)|_{μ} = \frac{1}{|Nm_{𝕃}(α^{n})|} ≤ \frac{1}{|α|^{n}} ,  (17)

while by equation (13), we have

∏_{μ∈S ; μ is infinite} |L_{1,μ}(x)|_{μ} = B^{2} ≤ exp(O(log n)).  (18)

Multiplying the estimates (15), (16), (17) and (18), we derive that

∏_{j=1}^{N} ∏_{μ∈S} |L_{j,μ}(x)| ≤ \frac{AB^{2}}{α^{n}} ≤ exp (−n log α + O(log n)) .  (19)

Since max{|x_{j}| : j = 1, …, N} = |α|^{n}, the inequality (19) together with Theorem 3 (for example, with ε = 1/2 and n > n_{ε}), imply that there exist finitely many proper subspaces of 𝕃^{N} containing all solutions x. Thus, the relation

C_{2}α^{n} + D_{2}β^{n} + C_{3}α^{n_{i}}b^{s_{i}} + D_{3}β^{n_{i}}b^{s_{i}} + EAb^{s_{i}−1} = 0  (20)

holds for some fixed coefficients C_{2}, D_{2}, C_{3}, D_{3} and E in 𝕃, which are not all equal to zero. If A = 0, then the same argument with N = 4 also yields an identity of the shape (20). Finally, if B = 0, then (13) is the same as (20) with C_{2} = c, D_{2} = d, C_{3} = c_{1}, D_{3} = d_{1}, and E = 1. Clearly, we may assume that C_{2} and D_{2} are conjugate (over 𝕃), that C_{3} and D_{3} are conjugate (over 𝕃), and that E ∈ ℤ (if not, we can conjugate (20) and subtract the result from (20) to obtain a “shorter” nontrivial equation of the same type with the desired properties).

If E = 0, then (20) is a S-unit equation. If it is nondegenerate, we see that α^{n}β^{−n} can take only finitely many values; since α/β is not a root of unity, there are at most finitely many possibilities for n. If the S-unit equation is degenerate, then either C_{2} = D_{2} = 0, in which case n_{i} can take only finitely many values (and since |n − n_{i}| ≪ log n, it follows that n is bounded as well), or C_{2}D_{2} ≠ 0 but C_{3} = D_{3} = 0, in which case n can again take only finitely many values, or C_{2}C_{3}D_{2}D_{3} ≠ 0. In the last case, either α^{n−n_{i}}b^{−s_{i}} and β^{n−n_{i}}b^{−s_{i}} can take only finitely many values, or α^{n}β^{−n_{i}}b^{−s_{i}} and β^{n}α^{−n_{i}}b^{−s_{i}} can take only finitely many values; but these are cases that have already been considered.

Finally, we are left with the possibility that E ≠ 0, in which case we can assume that E = 1. We now rewrite (20) in the form

C_{4}α^{n} + D_{4}β^{n} = −Ab^{s_{i−1}},  (21)

where C_{4} = C_{2} + C_{3}α^{n_{i}−n}b^{s_{i}} and D_{4} = D_{2} + D_{3}β^{n_{i}−n}b^{s_{i}}. Since C_{4} and D_{4} are conjugated in 𝕃, it follows that they are simultaneously zero or nonzero.

Assume first that C_{4} = D_{4} = 0. Then both relations

C_{2} = −C_{3}α^{n−n_{i}}b^{s_{i}}  and D_{2} = −D_{3}β^{n−n_{i}}b^{s_{i}}  (22)

hold. If C_{2} = 0 then C_{3} = 0 (by (22)), D_{2} = 0 (because C_{2} and D_{2} are conjugated), and therefore D_{3} = 0 (by (22)); together with equation (20), these lead to E = 0, which is a contradiction. Thus, C_{2} ≠ 0, and the preceding argument implies that C_{2}C_{3}D_{2}D_{3} ≠ 0. Now, equation (22) together with our hypothesis that dim_{ℚ}⟨log α, log β, log b⟩ ≥ 2 lead to the conclusion that both n − n_{i} and s_{i} are bounded, which is a case already treated.

We now assume that C_{4}D_{4} ≠ 0. Let ℓ = gcd(r^{2}, s), where r and s are the coefficients of the recurrence (1). Set α_{1} = α^{2}/ℓ, β_{1} = β^{2}/ℓ. Applying Lemma A.10 on page 20 in [26], we see that α_{1} and β_{1} are algebraic integers and that the principal ideals they generate in 𝕃 are coprime. Clearly, α_{1} and β_{1} are complex conjugates, and |α_{1}| > 1. Write n = 2m + δ, where δ ∈ {0, 1}. Put (C_{5}, D_{5}) = (C_{4}, D_{4}) if δ = 0 and (C_{5}, D_{5}) = (αC_{4}, βD_{4}) if δ = 1. Dividing both sides of equation (21) by ℓ^{m}, we see that the expression

C_{5}α_{1}^{m} + D_{5}β_{1}^{m}

is a rational number such that every prime factor of its numerator or denominator divides either Abαβ or one of the denominators of C_{2}, D_{2}, C_{3}, or D_{3}. Let P = {p_{1}, …, p_{v}} be the set consisting of all of these primes, and write

C_{5}α^{m} + D_{5}β^{m} = ∏_{i=1}^{v} p_{i}^{r_{i}}.

We now bound the order r_{i} of p_{i}. Let π_{i} be some prime ideal of 𝕃 lying above p_{i}. If π_{i}|α_{1}, then ord_{π_{i}}(α_{1}^{m}) ≥ m ≥ n/2 − 1. On the other hand, it is clear that

max{|ord_{π_{i}}(C_{5})|, |ord_{π_{i}}(D_{5})|} ≪ max{|n − n_{i}|, s_{i}} ≪ log n.

Thus, for large n, we get that

ord_{π_{i}}(C_{5}α_{1}^{m} + D_{5}β_{1}^{m}) = ord_{π_{i}}(D_{5}β_{1}^{m}) = ord_{π_{i}}(D_{5}) ≪ log n,  (23)

since α_{1} and β_{1} are coprime. A similar analysis can be used if π_{i}|β_{1}. Assume now that π_{i} does not divide α_{1}β_{1}. Then

r_{i} = ord_{π_{i}} (C_{5}α_{1}^{m} + D_{5}β_{1}^{m}) = ord_{π_{i}}(C_{5}β_{1}^{m}) + ord_{π_{1}} ((α_{1}/β_{1})^{m} − (−D_{5}/C_{5})) .

Certainly,

ord_{π_{i}}(C_{5}β_{1}^{m}) = ord_{π_{i}}(C_{5}) ≪ log n,

while from Theorem 6, we deduce that

ord_{π_{i}} ((α_{1}/β_{1})^{m} − (−D_{5}/C_{5})) ≪ (log n)^{2}| log |C_{5}|| ≪ (log n)^{3}.

Thus,

ord_{π_{i}}(C_{5}α_{1}^{m} + D_{5}β_{1}^{m}) ≪ (log n)^{3}  (24)

in this case. Comparing inequalities (23) and (24), we see that inequality (24) always holds. Since this is true for all i = 1, …, v, we conclude that

log |C_{5}α_{1}^{m} + D_{5}β_{1}^{m}| ≤ ∑_{i=1}^{v} r_{i} log p_{i} ≪ (log n)^{3}.  (25)

On the other hand, we have

log |C_{5}α_{1}^{m} + D_{5}β_{1}^{m}| = log |C_{5}| + m log |α_{1}| + log |1 + (D_{5}C_{5}^{−1}(β_{1}α_{1}^{−1})^{m}|.

Clearly,

log |C_{5}| ≫ − log n,  (26)

and using Theorem 5, we get that

log |1 + (D_{5}C_{5}^{−1})(β_{1}α_{1}^{−1})^{m}| ≫ −(log n)^{2}| log |C_{5}||.  (27)

Putting together inequalities (25), (26), (27), and using the fact that m ≫ n and |α_{1}| > 1, we obtain that

n ≪ (log n)^{3},

which shows that n can take only finitely many values.

This completes the proof of Theorem 1.

4 Proof of Theorem 2

Before proceeding to the proof of Theorem 2, we gather a few useful facts about the Fibonacci sequence.

We first recall the following special case of the Primitive Divisor Theorem, which is due to Carmichael [5]:

Lemma 7. For all n ≥ 13, there exists a prime factor p of F_{n} such that p does not divide F_{m} for any positive integer m < n. Furthermore, any such prime p satisfies p ≡ ±1 mod n.

Next, we record the following estimate for the function ℓ(n) = ℓ_{10}(F_{n}), which gives the number of digits in the decimal expansion of F_{n}:

Lemma 8. For all n ≥ 1, we have

\frac{(n − 2) log α}{log 10} < ℓ(n) ≤ \frac{(n − 1) log α}{log 10} + 1.

Proof. By induction on k, it is easy to see that α^{k−2} ≤ F_{k} ≤ α^{k−1} holds for all k ≥ 1. Since ℓ(k) is the unique integer for which 10^{ℓ(k)−1} ≤ F_{k} < 10^{ℓ(k)}, the result follows.

We keep the notation used in the proof of Theorem 1. In particular, 𝕃 = ℚ(\sqrt{5} ), O_{𝕃} = ℤ[α], and D = 2 is the degree of 𝕃 over ℚ. Notice that O_{𝕃} is a UFD. We also put ϖ = \sqrt{5} and P = [ϖ]; then [p] = [5] = P^{2}, and f = 1. We need the following elementary lemma:

Lemma 9. If r ≥ 2, we have

ord_{P}(α^{r} − 1) ≤ \frac{2 log(r/4)}{log 5} + 1.

The same inequality holds with α replaced by β.

Proof. The inequality for β follows from the one for α by conjugation. Note that the right hand side of the stated inequality is positive for all r ≥ 2. Since

α = \frac{1 + \sqrt{5}}{2} ≡ 2^{−1} (mod ϖ),

it follows that ord_{P}(α^{r} − 1) = 0 if 4 ∤ r; hence, it suffices to assume that 4 | r in what follows. Since

α^{4} − 1 = \frac{5 + 3\sqrt{5}}{2},

it follows that ord_{P}(α^{4} − 1) = 1. Thus, we may write α^{4} = 1 + ϖu, where u is coprime to ϖ. If s ≥ 1 is an integer and 5 ∤ s, then

α^{4s} − 1 = (α^{4} − 1) ∑_{j=0}^{s−1} α^{4j} = ϖu ∑_{j=0}^{s−1}(1 + ϖu)^{j} ≡ ϖus (mod ϖ),

which shows that ord_{P}(α^{4s} − 1) = 1 as well. One checks similarly that if s ≥ 1 and 5 ∤ s, then ord_{P}(α^{20s} − 1) = 3.

We now claim that, for all t ≥ 0 and s ≥ 1 such that 5 ∤ s, we have

ord_{P}(α^{4s·5^{t}} − 1) = 2t + 1.  (28)

To prove this, we use induction on the parameter t. Since the claim is true for t = 0 or 1, let us suppose that t ≥ 2. Then,

α^{4s·5^{t}} − 1 = (α^{4s·5^{t−1}} − 1) ∑_{j=0}^{4} α^{4sj·5^{t−1}}

= 5(α^{4s·5^{t−1}} − 1) + (α^{4s·5^{t−1}} − 1) ∑_{j=1}^{4}(α^{4sj·5^{t−1}} − 1).

By the induction hypothesis, we have

ord_{P} (5(α^{4s·5^{t−1}} − 1)) = 2 + (2(t − 1) + 1) = 2t + 1,

while

ord_{P} ((α^{4s·5^{t−1}} − 1) ∑_{j=1}^{4}(α^{4sj·5^{t−1}} − 1)) ≥ 2 (2(t − 1) + 1) = 4t − 2 > 2t + 1,

and (28) follows.

Finally, writing r in the form r = 4s · 5^{t}, where t ≥ 0, s ≥ 1, and 5 ∤ s, we have

ord_{P}(α^{r} − 1) = 2t + 1 = \frac{2 log(r/4s)}{log 5} + 1 ≤ \frac{2 log(r/4)}{log 5} + 1,

which finishes the proof.

Lemma 10. If (m, n, k) is an ordered triple of positive integers such that \overline{F_{m}F_{n}} = F_{k}, and (m, n, k) ≠ (1, 4, 7) or (2, 4, 7), then m ≥ 3 and k − n ≥ 4.

Proof. Suppose that n ≥ 13. First, suppose that m = 1 or m = 2. Then 10^{ℓ(n)} + F_{n} = F_{k}; hence, 2F_{n} ≤ F_{k} ≤ 11F_{n}, which (by simple estimates) implies that n + 2 ≤ k ≤ n + 5. Since n ≥ 13, we have that ℓ(n) ≥ 3, and thus,

F_{n} ≡ F_{k} (mod 8).

An analysis of the sequence of Fibonacci numbers modulo 8 shows that this congruence is not possible when k = n + 4 or k = n + 5; therefore, k = n + 2 or k = n + 3. If k = n + 2, then 10^{ℓ(n)} = F_{n+1}, while for k = n + 3, we have 10^{ℓ(n)} = 2F_{n+1}. However, by Lemma 7, there exists a prime p ≥ n dividing F_{n+1}, which is not possible in our cases. Consequently, if m ≤ 2, we must have n ≤ 12. Checking the remaining possibilities, the only solutions found are (1, 4, 7) and (2, 4, 7).

Assuming now that \overline{F_{m}F_{n}} = F_{k}, n ≥ 15, and k ≤ n + 3, we then have

F_{m} · 10^{ℓ(n)} = F_{k} − F_{n} = \{ \begin{matrix}F_{n−1}, & if k = n + 1; \\ F_{n+1}, & if k = n + 2; \\ 2F_{n+1}, & if k = n + 3. \end{matrix}  (29)

Moreover, m < n − 1, for otherwise

F_{k} = F_{m} · 10^{ℓ(n)} + F_{n} > 1000F_{n−1} > F_{n+3},

contradicting our assumption that k ≤ n + 3. Using Lemma 7 again, we see that there exist primes p | F_{n−1} and q | F_{n+1} with gcd(pq, F_{m}) = 1 and min{p, q} ≥ 13, which is not possible in view of (29). Hence, if k ≤ n + 3, we must have n ≤ 14, and thus k ≤ 17. Examining these possibilities reveals no solutions other than the two found in the previous case.

Lemma 11. If r ≥ 1 is even, then

\frac{α^{r} − 1}{β^{r} − 1} = −α^{r},

while if r ≥ 5 is odd, then the numbers (α^{r} − 1)/(β^{r} − 1) and α are multiplicatively independent.

Proof. The first statement is trivial since αβ = −1. For the second statement, we note that if r is odd then

\frac{α^{r} − 1}{β^{r} − 1} = −α^{r} (\frac{α^{r} − 1}{α^{r} + 1}) .

We now observe that if D is the common divisor in O_{𝕃} of α^{r}−1 and α^{r}+1, then D | 2. Since 2 is inert in O_{𝕃}, it follows that D ∈ {1, 2}. The above arguments show that if (α^{r} −1)/(β^{r} −1) and α are multiplicatively dependent, then so are (α^{r} − 1)/(α^{r} + 1) and α. Using the fact that O_{𝕃} is a UFD and the computation of D, it follows that α^{r} − 1 is either a unit, or it is an associate of 2. Hence, we get an equation of the form

α^{r} − 1 = ±2^{λ}α^{t}

with integers λ ∈ {0, 1} and t. Since r > 3, it follows that α^{r} − 1 > α^{3} − 1 > 2; hence, the sign in this equation is positive, and t ≥ 1. Clearly, t < r. Thus, α^{r} − 1 = 2^{λ}α^{t}. By conjugation, we also have β^{r} − 1 = 2^{λ}β^{t}. Subtracting these two equations and dividing the result by α − β, we obtain that F_{r} = 2^{λ}F_{t}. If r ≥ 13, this equation is impossible in view of Lemma 7. The fact that F_{r} = 2^{λ}F_{t} is also impossible for 5 ≤ r ≤ 13 can be checked by hand, and the result follows.

We are now ready to embark on the proof of Theorem 2. For this, let (m, n, k) be a fixed triple of nonnegative integers for which \overline{F_{m}F_{n}} = F_{k} holds. We note that n > 0, since for n = 0 we have 10F_{m} = F_{k}, which has no positive integer solutions (m, k) (by Lemma 7, for example). Put r = k − n, and assume that k > 10^{6}. By Lemma 10, we can further suppose that m ≥ 3 and r ≥ 4. Since β = −1/α, we have

F_{m} · 10^{ℓ(n)} = F_{k} − F_{n} = ϖ^{−1}(α^{k} − β^{k} − α^{n} + β^{n})
= ϖ^{−1}(α^{n}(α^{r} − 1) − β^{n}(β^{r} − 1))
= ϖ^{−1}α^{n}(β^{r} − 1) ((\frac{α^{r} − 1}{β^{r} − 1}) − (−α^{−2})^{n}) .

Consequently,

ord_{P}(F_{m}) + 2ℓ(n) = −1 + ord_{P}(β^{r} − 1) + ord_{P} ((\frac{α^{r} − 1}{β^{r} − 1}) − (−α^{−2})^{n}) .  (30)

Assume first that r is odd. We shall apply Theorem 6 with the choices α_{1} = (α^{r} − 1)/(β^{r} − 1), α_{2} = −α^{−2}, b_{1} = 1, and b_{2} = n. The condition that α_{1} and α_{2} are multiplicatively independent is satisfied by Lemma 11 because r ≥ 5. Furthermore, note that

h(α_{1}) ≤ \frac{1}{2} (log |(α^{r} − 1)(β^{r} − 1)| + log |α_{1}|) ≤ \frac{1}{2} log α^{2r} = r log α,

and h(α_{2}) = log α. Since r ≥ 5, we can choose A_{1} = α^{r} and A_{2} = ϖ; hence,

b′ = \frac{1}{log 5} + \frac{n}{2r log α} ≤ \frac{1}{2 log α} + \frac{n}{10 log α} ≤ \frac{3n}{4 log α}.

Finally, as α ≡ β (mod ϖ), and ord_{P}(α^{r} − 1) = ord_{P}(β^{r} − 1) = 0 (by Lemma 9), it follows that P divides α_{1} − 1. Moreover, noting that −α^{−2} ≡ 1 (mod ϖ), it follows that P also divides α_{2} − 1. Thus, we can take g = 1. By Theorem 6, we obtain the bound

ord_{P} ((\frac{α^{r} − 1}{β^{r} − 1}) − (−α^{−2})^{n})
≤ \frac{480r log α}{(log 5)^{3}} (max \{log n + log (\frac{3 log 5}{4 log α}) + 0.4, 10\})^{2}
≤ 56r (max {log n + 2, 10})^{2} .

Next, consider the case that r is even; then

\frac{α^{r} − 1}{β^{r} − 1} − (α^{−2})^{n} = −α^{r} − (−α^{2})^{n} = (−1)^{n+1}α^{−2n}(α^{k+n} ± 1),

and the last expression divides α^{2k+2n} − 1 in O_{𝕃}; hence, by Lemma 9, we obtain that

ord_{P} ((\frac{α^{r} − 1}{β^{r} − 1}) − (−α^{−2})^{n}) ≤ \frac{2 log((k + n)/2)}{log 5} + 1.

Substituting the estimates above into (30), and applying Lemmas 8 and 9, we derive that

2\frac{(n − 2) log α}{log 10} < ℓ(n) ≤ \frac{2 log(r/4)}{log 5} + 56r (max \{log n + 2, 10\})^{2} ,  (31)

if r is odd, and

2\frac{(n − 2) log α}{log 10} < ℓ(n) ≤ \frac{2 log(r/4)}{log 5} + \frac{2 log((k + n)/2)}{log 5} + 1,  (32)

if r is even.

From the equality \overline{F_{m}F_{n}} = F_{k}, we also see that

α^{m} · 10^{ℓ(n)} − α^{k} = β^{m} · 10^{ℓ(n)} − α^{n} + β^{n} − β^{k},  (33)

and, since 10^{ℓ(n)} < 10F_{n} and m ≥ 3, we have

\begin{aligned}|α^{m−k} · 10^{ℓ(n)} − 1| & = α^{−k}|β^{m} · 10^{ℓ(n)} − α^{n} + β^{n} − β^{k}| \\ & ≤ α^{−k}(10|β|^{3}F_{n} + α^{n} + 2) < 4α^{−r}. \end{aligned}  (34)

Since m ≥ 3, both sides of (33) are negative, and since r ≥ 4, we have 4α^{−r} < \frac{3}{5}; thus,

\frac{2}{5} < α^{m−k} · 10^{ℓ(n)} < 1.

It follows that

|α^{m−k} · 10^{ℓ(n)} − 1| > \frac{2}{5}|(k − m) log α − ℓ(n) log 10|.  (35)

We now apply Theorem 5 with the choices Λ = (k − m) log α − ℓ(n) log 10, α_{1} = 10, α_{2} = α, b_{1} = ℓ(n), and b_{2} = k − m. Here, h(α_{1}) = log 10 and h(α_{2}) = \frac{1}{2} log α; hence, we can choose A_{1} = 10, and A_{2} = α^{2}, and

b′ = \frac{ℓ(n)}{4 log α} + \frac{k − m}{20} < b′′ = \frac{ℓ(n)}{4 log α} + \frac{k}{20}.

Using Theorem 5, we get that

|(k − m) log α − ℓ(n) log 10| ≥ exp (−864 (max{log b′′ + 0.14, 10.5})^{2}) .

Combining the above estimates, we derive the bound

r < \frac{log 10}{log α} + \frac{864}{log α} (max\{log b′′ + 0.14, 10.5\})^{2} .  (36)

Now, if k > 2n, then, by Lemma 8, we have

b′′ = \frac{ℓ(n)}{4 log α} + \frac{k}{20} ≤ \frac{n − 1}{4 log 10} + \frac{1}{4 log α} + \frac{k}{20} < \frac{(k/2) − 1}{4 log 10} + \frac{1}{4 log α} + \frac{k}{20},

and r = k − n > k/2; hence, the inequality (36) is not possible for k > 500000. On the other hand, if k ≤ 2n, then

b′′ = \frac{ℓ(n)}{4 log α} + \frac{k}{20} ≤ \frac{n − 1}{4 log 10} + \frac{1}{4 log α} + \frac{n}{10}.

When r is even, estimate (32) gives

\frac{(n − 2) log α}{log 10} < \frac{log(n/4)}{log 5} + \frac{log(3n/2)}{log 5} + \frac{1}{2},

which implies that n < 20; hence, k < 40. When r is odd, by combining the inequalities (31), and (36), we obtain a contradiction unless n ≤ 1.1 × 10^{11} and k ≤ 2n ≤ 2.2 × 10^{11}.

Although the preceding argument shows that there are only finitely many solutions (m, n, k) to the equation \overline{F_{m}F_{n}} = F_{k}, it would be computationally infeasible to search for solutions over the entire range k ≤ 2.2 × 10^{11}. In order to reduce the range further, we use a standard technique involving the continued fraction expansion of (log 10)/(log α).

Suppose that n ≤ 1.1 × 10^{11} and r ≥ 56. By (34) and (35), we have

|\frac{log 10}{log α} − \frac{(k − m)}{ℓ(n)}| < \frac{10}{α^{r}ℓ(n)} ≤ \frac{1}{2ℓ(n)^{2}} .

Here, the last inequality is equivalent to 20ℓ(n) ≤ α^{r}, which holds (by Lemma 8) for this choice of parameters. By well known properties of continued fractions, it follows that (k − m)/ℓ(n) is a convergent of (log 10)/(log α). Writing (k − m)/ℓ(n) = p_{j}/q_{j} for some j ≥ 0, where p_{j}/q_{j} denotes the jth convergent to (log 10)/(log α), and using Lemma 8 again to bound ℓ(n) for n in our range, we see that q_{j} ≤ ℓ(n) ≤ 2.3 × 10^{10}, which implies that j ≤ 23. Noting that

10α^{−r} > |ℓ(n) log 10 − (k − m) log α| ≥ min_{1≤j≤23} |q_{j} log 10 − p_{j} log α| > 1.6 × 10^{−11},

we conclude that r ≤ 57. Substituting this estimate into (31), we derive the more tractable upper bound n ≤ 2.1 × 10^{6}.

At this point, we turn to the computer. Note that if n ≥ 74, one has ℓ(n) ≥ 15; therefore, if \overline{F_{m}F_{n}} = F_{k}, it follows that F_{n} ≡ F_{k} (mod 10^{15}). However, a computer search quickly reveals that there is no solution to this congruence with 74 ≤ n ≤ 2.1 × 10^{6} and k ≤ n+57. Thus, it remains only to search for solutions (m, n, k) with n ≤ 73 and k ≤ n+57, and one obtains only solutions with k = 7, 8 or 10; that is F_{k} ∈ {13, 21, 55}.

This completes the proof of Theorem 2.

5 Acknowledgements

This work was done during a visit by the second author to the University of Missouri, Columbia; the hospitality and support of this institution are gratefully acknowledged. During the preparation of this paper, W. B. was supported in part by NSF grant DMS-0070628, and F. L. was supported in part by grants SEP-CONACYT 37259-E and 37260-E.

References

[1] W. Banks, A. Conflitti and I. E. Shparlinski, Character sums over integers with restricted g-ary digits, Illinois J. Math. 46 (2002), 819–836.

[2] W. Banks, D. Hart and M. Sakata, Almost all palindromes are composite, Math. Res. Lett. 11 (2004), 853–868.

[3] W. Banks and I. E. Shparlinski, On the number of sparse RSA exponents, J. Number Theory 95 (2002), 340–350.

[4] Y. Bugeaud and M. Laurent, Minoration effective de la distance p-adique entre puissances de nombres algébriques, J. Number Theory 61 (1996), 311–342.

[5] R. D. Carmichael, On the numerical factors of the arithmetic forms α^{n}1β^{n}, Ann. of Math. (2) 15 (1913/14), 30–70.

[6] P. Erdős, C. Mauduit and A. Sárközy, On arithmetic properties of integers with missing digits, I, J. Number Theory 70 (1998), 99–120.

[7] P. Erdős, C. Mauduit and A. Sárközy, On arithmetic properties of integers with missing digits, II, Discrete Math. 200 (1999), 149–164.

[8] J.-H. Evertse, H. P. Schlickewei and W. M. Schmidt, Linear equations with variables which lie in a multiplicative group, Ann. of Math. (2) 155 (2002), 807–836.

[9] M. Filaseta and S. V. Konyagin, Squarefree values of polynomials all of whose coefficients are 0 and 1, Acta Arith. 74 (1996), 191–205.

[10] E. Fouvry and C. Mauduit, Methódes des crible et fonctions sommes des chiffres, Acta Arith. 77 (1996), 339–351.

[11] E. Fouvry and C. Mauduit, Sommes des chiffres et nombres presque premiers, Math. Ann. 305 (1996), 571–599.

[12] J. B. Friedlander and I. E. Shparlinski, On the distribution of Diffie–Hellman triples with sparse exponents, SIAM J. Discrete Math. 14 (2001), 162–169.

[13] A. O. Gel’fond, Sur les nombres qui ont des propriétés additives et multiplicatives données, Acta Arith. 13 (1968), 259–265.

[14] S. V. Konyagin, Arithmetic properties of integers with missing digits: distribution in residue classes, Period. Math. Hungar. 42 (2001), 145–162.

[15] S. V. Konyagin, C. Mauduit and A. Sárkőzy, On the number of prime factors of integers characterized by digit properties, Period. Math. Hungar. 40 (2000), 37–52.

[16] F. Luca, Distinct digits in base b expansions of linear recurrence sequences, Quaest. Math. 23 (2000), 389–404.

[17] F. Luca, Arithmetic properties of positive integers with fixed digit sum, to appear in Rev. Mat. Iberoamericana.

[18] C. Mauduit and A. Sárközy, On the arithmetic structure of sets characterized by sum of digits properties, J. Number Theory 61 (1996), 25–38.

[19] C. Mauduit and A. Sárközy, On the arithmetic structure of the integers whose sum of digits is fixed, Acta Arith. 81 (1997), 145–173.

[20] M. Laurent, M. Mignotte and Y. Nesterenko, Formes linéaires en deux logarithmes et déterminants d’interpolation, J. Number Theory 55 (1995), 285–321.

[21] H. P. Schlickewei, S-unit equations over number fields, Invent. Math. 102 (1990), 95– 107.

[22] W. M. Schmidt, Diophantine Approximations, Springer Verlag, LNM 785 (1980).

[23] W. M. Schmidt, Diophantine Approximations and Diophantine Equations, Springer Verlag, LNM 1467 (1991).

[24] H. G. Senge and E. G. Straus, PV-numbers and sets of multiplicity, in Proceedings of the Washington State Conference in Number Theory (Washington State Univ., Pullman, Wash., 1971), 55–67, Dept. Math. Washington State Univ., Pullman, Washington, 1971.

[25] H. G. Senge and E. G. Straus, PV-numbers and sets of multiplicity, in “Collection of articles dedicated to the memory of Alfréd Rényi, II”, Period. Math. Hungar. 3 (1973), 93–100.

[26] T. N. Shorey and R. Tijdeman, Exponential diophantine equations, Cambridge Univ. Press, 1986.

[27] I. E. Shparlinski, Prime divisors of sparse integers, Period. Math. Hungar. 46 (2003), 215–222.

[28] C. L. Stewart, On the representation of an integer in two different bases, J. Reine Angew. Math. 319 (1980), 63–72.