\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{amsthm}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf Concatenations with\break Binary Recurrent Sequences}
\vskip 1cm
\large
William D.~Banks \\
Department of Mathematics \\
University of Missouri \\
Columbia, MO 65211\\
USA \\
\href{mailto:bbanks@math.missouri.edu}{\tt bbanks@math.missouri.edu} \\
\ \\
Florian~Luca\\
Instituto de Matem{\'a}ticas\\
Universidad Nacional Aut\'onoma de M{\'e}xico\\
C.P.~58180 \\
Morelia, Michoac{\'a}n \\
M{\'e}xico\\
\href{mailto:fluca@matmor.unam.mx}{\tt fluca@matmor.unam.mx}\\
\end{center}

\vskip .2 in

\begin{abstract}
If $A_1,\ldots,A_t$ are positive integers written in base $b\ge 2$,
we write $\overline{A_1\cdots A_t}_{\,(b)}$ for the positive integer
obtained by concatenating the base-$b$ digits of
$A_1,A_2,\ldots,A_t$. We prove that if $(u_n)_{n\ge 0}$ is
a binary recurrent sequence of integers satisfying certain mild
hypotheses, then for every fixed integer $t\ge 1$, 
there exist at most finitely many nonnegative integers $n_1,\ldots,n_t$ 
such that ${\overline{|u_{n_1}|\cdots |u_{n_t}|}}_{\,(b)}$ is
a member of the sequence $(|u_n|)_{n\ge 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. 
\end{abstract}

%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{proposition}{Proposition}[section]
%\newtheorem{corollary}{Corollary}[section]
%\newtheorem{lemma}{Lemma}[section] 

%\documentclass[12pt]{article}
%\usepackage{amsmath,amssymb,amsbsy,amsfonts,amsthm,
%             latexsym,amsopn,amstext,amsxtra,euscript,amscd}

\renewcommand{\theequation}{\arabic{equation}}

%\begin{document}

\newtheorem{prop}{Proposition}
\newtheorem{lemma}[prop]{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{corollary}[cor]{Corollary}
\newtheorem{conj}[prop]{Conjecture}
\newtheorem{defi}[prop]{Definition}
\newtheorem{theorem}[prop]{Theorem}
\newtheorem{fac}[prop]{Fact}
\newtheorem{facs}[prop]{Facts}
\newtheorem{com}[prop]{Comments}
\newtheorem{prob}{Problem}
\newtheorem{problem}[prob]{Problem}
\newtheorem{ques}{Question}
\newtheorem{question}[ques]{Question}
\newtheorem{remark}[prop]{Remark}

%% DEFINITIONS

\def\ord{{\mathrm{ord}}}
\def\scr{\scriptstyle}
\def\\{\cr}
\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}
\def\<{\langle}
\def\>{\rangle}
\def\fl#1{\left\lfloor#1\right\rfloor}
\def\rf#1{\left\lceil#1\right\rceil}
\def\lcm{{\rm lcm\/}}

\def\C{\mathbb C}
\def\R{\mathbb R}
\def\Q{{\mathbb Q}}
\def\F{{\mathbb F}}
\def\Z{{\mathbb Z}}
\def\cO{{\mathcal O}}

\def\ord{{\mathrm{ord}}}
\def\Nm{{\mathrm{Nm}}}
\def\L{{\mathbb L}}

\def\xxx{\vskip5pt\hrule\vskip5pt}
\def\yyy{\vskip5pt\hrule\vskip2pt\hrule\vskip5pt}

%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  TITLE AND ABSTRACT  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%
%%  PAPER BEGINS  %%
%%%%%%%%%%%%%%%%%%%%

\newpage

\section{Introduction}

A result of Senge and Straus~\cite{SS1, SS2} 
asserts that if $b_1,b_2\ge 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~\cite{Stew}, 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~\cite{Lu}.

A variety of arithmetical questions about integers whose base-$b$
digits satisfy certain restrictions been considered by many authors;
see, for example, \cite{BaCoSh,BaHaSa,BaSh,EMS1,EMS2,FilKon,FoMa1,
FoMa2,FrSh,Gel,Kon,KoMaSa,Luca,Lu,MaSa1,MaSa2,Shp}
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\ge 0}$ be a {\it binary recurrent sequence\/} of integers,
i.e., a sequence of integers satisfying the recurrence relation
\begin{equation}
\label{eq:recurrence}
u_{n+2}=ru_{n+1}+su_n\qquad\qquad(n\ge 0),
\end{equation}
where $r$ and $s$ are nonzero integers with $r^2+4s=0$.
It is well known that if $\alpha$ and $\beta$ are the
roots of the equation $x^2-rx-s=0$, then $u_n=c\alpha^n+d\beta^n$
holds for all $n\ge 0$, where $c$ and $d$ are the constants given by
$$
c=\frac{-\beta u_0+u_1}{\alpha-\beta}\qquad\text{and}\qquad
d=\frac{\alpha u_0-u_1}{\alpha-\beta}.
$$
Throughout the paper, we assume that $(u_n)_{n\ge 0}$ is
{\it nondegenerate\/} (i.e., $\alpha/\beta$ is not a root of $1$,
and $\alpha\beta cd\ne 0$).  Reordering the roots if necessary,
we can further assume that $|\alpha|\ge|\beta|$.

Let $b\ge 2$ be an integer base. If $A_1,\ldots,A_t$ are
positive integers, expressed in the base $b$, we denote by 
${\overline{A_1\cdots A_t}}_{\,(b)}$ the positive integer
that is obtained by concatenating (in order) the base-$b$ digits
of $A_1,A_2,\ldots,A_t$.  We always assume that $A_1\ne 0$, and
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\ge 0}$ is a binary recurrent sequence,
that are the base-$b$ concatenations of other numbers of the form 
$|u_{n_j}|$, $j=1,\ldots,t$.  We show that if $t\ge 2$ is fixed,
then there are only finitely many instances of the equality
$$
|u_n|=\overline{|u_{n_1}|\cdots|u_{n_t}|}_{\,(b)}
$$
provided that the sequence $(u_n)_{n\ge 0}$ satisfies
certain mild hypotheses.  Note that some assumptions are clearly
needed in order to rule out some obvious counterexamples, such as the
sequence $u_n=b^n-1$, $n\ge 0$, for which the concatenation of any two
or more terms yields another term of the same sequence.

\begin{theorem}
\label{thm:1}
Let $u_n=c\alpha^n+d\beta^n$ be a nondegenerate binary recurrent\break
sequence of integers, and let $b\ge 2$ be a fixed integer base. 
Assume that $\dim_{\Z}\langle\log\alpha,~\log\beta,~\log b\rangle\ge 2$. 
Then for every fixed integer $t\ge 2$, there are at most finitely 
many positive integers $n$ such that the equality
\begin{equation}
\label{eq:concatenation1}
|u_n|={\overline{|u_{n_1}|
\mathop{\underbrace{0\cdots0}}\limits_{m_1}|u_{n_2}|
\mathop{\underbrace{0\cdots0}}\limits_{m_2}\cdots|u_{n_t}|
\mathop{\underbrace{0\cdots0}}\limits_{m_t}}}\vphantom{0}_{~(b)}
\end{equation}
holds for some nonnegative integers $n_1,\ldots,n_t$ and
$m_1,\ldots,m_t$ with $u_{n_1}\ne 0$.
\end{theorem}

Here, $\dim_{\Z}\langle\log\alpha,~\log\beta,~\log b\rangle$
denotes the rank of (the free part of) the additive subgroup of
$\C$ generated by $\{\log\alpha,~\log\beta,~\log b\}$.

Though our proof of Theorem~\ref{thm:1} is ineffective, this result 
can be seen as an extension of the aforementioned results of Senge
and Straus~\cite{SS1,SS2}.

In some special cases, one can employ effective methods to 
completely determine all the solutions to an equation such as 
\eqref{eq:concatenation1}.
Perhaps the best known example of a binary recurrent sequence
is the {\it Fibonacci sequence\/} $(F_n)_{n\ge 0}$, where
$F_0=0$ and $F_1=1$, and~\eqref{eq:recurrence} holds
with $r=s=1$. In this case, one has $\alpha=(1+{\sqrt {5}})/2$,
$\beta=-\alpha^{-1}$, $c=1/(\alpha-\beta)$, and $d=-c$.
For this special sequence, we obtain the
following computational result:

\begin{theorem}
\label{thm:2}
If $(m,n,k)$ is an ordered triple of nonnegative integers
with $m>0$ and such that $\overline{F_mF_n}=F_k$, then
$F_k\in\big\{13,21,55\}$.
\end{theorem}

Throughout the paper, we use the Vinogradov symbols $\ll$ and $\gg$,
as well as the Landau symbol $O$, with the understanding that the
implied constants are computable and depend at most on the given data.
We also use $\log(\cdot)$ to denote the natural logarithm.

{\bf 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.

\section{Preliminaries}
\label{sec:prel}

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

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

For a place $\mu\in{\cal M}_{\L}$ and a number $x\in\L$, we
define the absolute value $|x|_{\mu}$ as follows:
\begin{itemize}
\item[$(i)$] $|x|_{\mu}=|\sigma(x)|^{1/D}$
if $\mu$ corresponds to an embedding $\sigma:\L\to\R$;

\item[$(ii)$] $|x|_{\mu}=|\sigma(x)|^{2/D}=|{\overline{\sigma}}(x)|^{2/D}$
if $\mu$ corresponds to some pair of complex
conjugate embeddings $\sigma,{\overline{\sigma}}:\L\to \C$;

\item[$(iii)$] $|x|_{\mu}=\Nm_{\L}({\cal P})^{-\ord_{\cal P}(x)}$ 
if $\mu$ corresponds
to a nonzero prime ideal ${\cal P}$ of ${\cal O}_{\L}$.
\end{itemize}
In the case $(i)$ or $(ii)$, we say that $\mu$ is {\it real infinite\/} or
{\it complex infinite\/}, respectively; in the case $(iii)$,
we say that $\mu$ is {\it finite\/}.

The set of absolute values are well known to satisfy
the following {\it product formula\/}:
\begin{equation}
\label{eq:product}
\prod_{\mu\in {\cal M}_{\L}} |x|_\mu=1,\qquad\text{~for all~}x\in\L^*.
\end{equation}

One of our principal tools is the following simplified version 
of a result of Schlickewei~\cite{Schm1,Schm2}, 
which is commonly known as the {\it Subspace Theorem\/}:

\begin{theorem}
\label{lem:S-unit}
Let $\L$ be an algebraic number field of degree $D$. 
Let ${\cal S}$ be a finite set of places of $\L$ containing all
the infinite ones. Let $\{L_{1,\mu},\ldots,L_{N,\mu}\}$ for
$\mu\in{\cal S}$ be linearly  independent sets of
linear forms in $N$ variables with coefficients in $\L$.
Then, for every fixed $0<\varepsilon<1$, the set
of solutions ${\bf x}=(x_1,\ldots,x_N)\in\L^N\backslash\{{\bf 0}\}$
to the inequality
\begin{equation}
\label{eq:fundineq}
\prod_{\mu\in {\cal S}}\prod_{i=1}^N
|L_{i,\mu}({\bf x})|_{\mu}\le
{\rm max}\{|x_i|:i=1,\ldots,N\}^{-\varepsilon}
\end{equation}
is contained in finitely many proper linear subspaces of $\L^N$. 
\end{theorem}

Let ${\cal S}$ be a finite subset of ${\cal M}_{\L}$ containing all the 
infinite places. An element $x\in \L$ is called a {\it ${\cal S}$-unit\/}
if $|x|_\mu=1$ for all $\mu\not\in{\cal S}$.  An equation of the form
\begin{equation}
\label{eq:Suniteq}
\sum_{i=1}^N a_i x_i=0,
\end{equation}
where each $a_i\in \L^*$, is called an
{\it ${\cal S}$-unit equation} if each $x_i$ is an ${\cal S}$-unit;
it is said to be {\it nondegenerate\/}
if no proper subsum of the left hand side vanishes.
It is clear that if ${\bf x}=(x_1,\ldots,x_N)$ 
is a solution of the ${\cal S}$-unit equation~\eqref{eq:Suniteq}, and 
$\rho$ is a ${\cal S}$-unit in $\L^*$, then 
$\rho{\bf x}=(\rho x_1,\ldots,\rho x_N)$ is a also a solution 
of~\eqref{eq:Suniteq}; in this case, the solutions ${\bf x}$ and
$\rho{\bf x}$ are said to be {\it equivalent}. 
We recall the following result of Evertse, Schlickewei
and Schmidt~\cite{ESS} on ${\cal S}$-unit equations:

\begin{theorem}
\label{thm:evSS}
Let $a_1,\ldots,a_N$ be fixed numbers in $\L^*$.
Then the ${\cal S}$-unit equation~\eqref{eq:Suniteq} 
has only finitely many equivalence classes of nondegenerate
solutions $(x_1,\ldots,x_N)$. Moreover, the number of such
equivalence classes is bounded by a constant that depends only on
$N$ and the cardinality of ${\cal S}$.
\end{theorem}

An immediate consequence of Theorem \ref{thm:evSS} is that if 
${\bf x}=(x_1,\ldots,x_N)$ is a solution of the ${\cal S}$-unit equation 
\eqref{eq:Suniteq}, then the ratios $x_i/x_j$ for $1\le i<j\le 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 $\alpha_1$ and $\alpha_2$ be algebraic numbers.  Put
$\L=\Q[\alpha_1,\alpha_2]$, and let $D$ be the degree of $\L$ over $\Q$.
Let $A_1$ and $A_2$ be two positive integers such that
\begin{equation}
\label{eq:A_i}
\log A_i\ge \max\left\{h(\alpha_i),\frac{|\log \alpha_i|}{D},
\frac{1}{D}\right\}
\qquad\qquad (i=1,2).
\end{equation}
Here, for an algebraic number $\alpha$ whose minimal polynomial over 
$\Z$ has the form $a\prod_{i=1}^d(X-\alpha^{(i)})$, we write 
$h(\alpha)$ for the logarithmic height of $\alpha$, which is given by 
$$
h(\alpha)=\frac{1}{d}\left(\log|a|+
\sum_{i=1}^d\log\(\max\{1,|\alpha^{(i)}|\}\)\right).
$$ 
Let $b_1$ and $b_2$ be positive integers, and put 
$\Lambda=b_2\log \alpha_2-b_1\log \alpha_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~\cite{LMN},
which gives an effective lower bound on the size of $\log|\Lambda|$:

\begin{theorem}
\label{thm:LMN}
Assume that $\alpha_1$ and $\alpha_2$ are real, positive, and 
multiplicatively independent. Then
$$
\log|\Lambda|\ge -24.34 D^4\(\max\left\{\log b'+0.14,\frac{21}{D},\frac{1}{2}
\right\}\)^2
\log A_1\log A_2.
$$
\end{theorem}

We also need a $p$-adic lower bound on $\Lambda$, that is,
an upper bound on the order at which a prime ideal ${\cal P}$ can
appear in the factorization of the principal ideal generated by
$\Lambda_1=\alpha_1^{b_1}-\alpha_2^{b_2}$ 
inside ${\cal O}_{\L}$.  For this, let $p$ be the prime number such that
${\cal P}\,|\,p$ (i.e., $p\Z={\cal P}\cap\Z$), and let $f$ be such that
the finite field ${\cal O}_{\L}/{\cal P}$ has $p^f$ elements.
Let $g$ be the smallest positive integer such that ${\cal P}$ divides
both $\alpha_1^g-1$ and $\alpha_2^g-1$.  Assume further 
that $A_i$ satisfies the inequality~\eqref{eq:A_i} as well 
as the inequality $\log A_i\ge f(\log p)/D$, for $i=1,2$.
The following result is an easy consequence of
Corollaire~2 on page~315 of~\cite{BL}:

\begin{theorem}
\label{thm:BL}
Assume that $\alpha_1$ and $\alpha_2$ are
multiplicatively independent. Then
\begin{eqnarray*}
\ord_{\cal P}\(\Lambda_1\) &\le& 
\frac{24pgD^5}{f^4(p-1)(\log p)^4}\\
&\times&\(\max\left\{\log b'+\log\log p+0.4,
\frac{10f\log p}{D},10\right\}\)^2\log A_1\log A_2.
\end{eqnarray*}
\end{theorem}

\section{Proof of Theorem~\ref{thm:1}}

Our proof of Theorem~\ref{thm: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\ge 1$ (clearly, this condition
is needed to insure that the number of solutions
to~\eqref{eq:concatenation1} is finite).

Since $\alpha/\beta$ is not a root of unity, at most one element of
the sequence $(u_n)_{n\ge 0}$ is equal to $0$.  Hence, if $u_{n_i}=0$
for some $i$ in~\eqref{eq:concatenation1}, then $n_i$ is
uniquely determined. Note that $i\ne 1$.  If this happens, then
equation~\eqref{eq:concatenation1} 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~\eqref{eq:concatenation1}
with $u_{n_i}\ne 0$, $i=1,\ldots,t$.

Let $\L=\Q[\alpha,\beta]$, and let ${\cal S}$ be the set of all 
infinite places of $\L$ and all finite places that divide $sb=-\alpha\beta b$. 
For a positive integer $m$, let $\ell_b(m)$ denote the number of
the digits in the base-$b$ representation of $m$.

The equation~\eqref{eq:concatenation1} is equivalent to
\begin{equation}
\label{eq:nonmainSuniteq}
|u_n|=\sum_{i=1}^t|u_{n_i}|b^{s_i},
\end{equation}
where
$$
s_i=\sum_{j=i}^t m_j+\sum_{j=i+1}^t\ell_b(|u_{n_j}|)
\qquad\qquad(i=1,\ldots,t).
$$
If $n=n_i$ for some $i$, it follows that $t=1$ (since each $u_{n_i}\ne 0$)
and $s_1=m_1=0$ (since $b\ge 2$), which contradicts our assumption
that $m_1\ge 1$ when $t=1$.  Hence, $n\ne n_i$ for all $i=1,\ldots,t$.
Now write~\eqref{eq:nonmainSuniteq} in the form
\begin{equation}
\label{eq:mainSuniteq}
\varepsilon_0(c\alpha^{n}+d\beta^n)=
\sum_{i=1}^t\varepsilon_i\(c\alpha^{n_i}+d\beta^{n_i}\)b^{s_i},
\end{equation}
where $\varepsilon_i\in \{\pm 1\}$ for $i=0,\ldots,t$.

Suppose first that $n_i>n$ for some $i\in\{1,\ldots,t\}$.
{From} \eqref{eq:nonmainSuniteq} we have that $|u_n|\le|u_{n_i}|b^{s_i}$,
and it is known that the estimate $|u_m|=|\alpha|^{m+O(\log m)}$
holds for all positive integers $m\ge 2$ (see
Theorem~3.1 on page~64 in~\cite{ST}).  Moreover,
if $\alpha$ is real, then $|\alpha|>|\beta|$, and one has
the estimate $|u_m|=|\alpha|^{m+O(1)}$.  Therefore, the following
bound holds if $n_i>n$:
\begin{equation}
\label{eq:maxlogbound}
\max\{n_i-n,s_i\}\ll\left\{\begin{array}{ll}
1,&\quad\text{if $\alpha\in\R$};\\
\log n,&\quad\text{if $\alpha\not\in\R$~~
(i.e., $\alpha=\overline\beta\,)$}.\end{array}\right.
\end{equation}

Next, suppose that $n_i<n$ for $i=1,\ldots,t$.  We will prove 
that there exists an index $i\in\{1,\ldots,t\}$ for which the
following bound holds:
\begin{equation}
\label{eq:maxlogbound2}
\max\{n-n_i,s_i\}\ll 1.
\end{equation}

Indeed, we first observe that~\eqref{eq:mainSuniteq} is
an ${\cal S}$-unit equation with $N=2t+2$ terms,
coefficients $(a_1,\ldots,a_N)=(c,d, -c,-d,\ldots,-c,-d)$,
and the \hbox{${\cal S}$-unit} unknowns ${\bf x}=(x_1,\ldots,x_N)=
(\varepsilon_0\alpha^n,\varepsilon_0\beta^n,\varepsilon_1 
\alpha^{n_1}b^{s_1},\ldots,\varepsilon_t\beta^{n_t}b^{s_t}).$

If the ${\cal S}$-unit equation \eqref{eq:mainSuniteq} is nondegenerate, 
then $x_1/x_2=\alpha^n\beta^{-n}$ can assume only finitely many
values; since $\alpha/\beta$ is not a root of unity, it follows that $n$
can take at most finitely many values.

On the other hand, if ${\cal S}$-unit equation~\eqref{eq:mainSuniteq}
is degenerate, let $E_1$ and $E_2$ be two (not necessarily distinct)
nondegenerate subequations of~\eqref{eq:mainSuniteq}
that contain the unknowns $x_1=\varepsilon_0\alpha^n$
and $x_2=\varepsilon_0\beta^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:
\begin{itemize}
\item[$(i)$]
{\it $E_1$ contains an unknown of the form 
$x_{2i+1}=\varepsilon_i \alpha^{n_i}b^{s_i}$ 
for some $i\ge 1$ and $E_2$ contains an unknown of the form 
$x_{2j}=\varepsilon_j \beta^{n_j}b^{s_j}$ for some $j\ge 1$\/}.

In this case, both $x_1/x_{2i+1}=\pm \alpha^{n-n_i}b^{-s_i}$ and 
$x_2/x_{2j}=\pm \beta^{n-n_j}b^{-s_j}$ can assume only finitely many values.
Since $\dim_{\Z}\langle \log \alpha,\log \beta, \log b\rangle\ge 2$, it 
follows that either the pair $(\alpha,b)$ or the pair $(\beta,b)$
is multiplicatively independent. Hence, either $\max\{n-n_i,s_i\}\ll 1$
or $\max\{n-n_j,s_j\}\ll 1$.

\item[$(ii)$]
{\it $E_1$ contains only unknowns of the form 
$x_{2i}=\varepsilon_i \beta^{n_i}b^{s_i}$ with $i\ge 1$ 
(except for $x_1$)  and $E_2$ contains only unknowns of the form 
$x_{2j+1}=\varepsilon_j \alpha^{n_j}b^{s_j}$ with $j\ge 1$
(except for $x_2$)\/}.

Let $i$ and $j$ be fixed. In this case, both 
$x_1/x_{2i}=\pm \alpha^{n}\beta^{-n_i}b^{-s_i}$ and $x_2/x_{2j+1}=\pm 
\beta^n\alpha^{-n_j}b^{-s_j}$ can have at most finitely many values. 
If we assume that $n$ takes infinitely many values (otherwise,
there is nothing to prove), it follows that there exist fixed numbers 
$n^*,~n_i^*,~n_j^*,~s_i^*$ and $s_j^*$ such that both relations 
\begin{eqnarray*}
\alpha^{n}\beta^{-n_i}b^{-s_i}&=&\alpha^{n^*}\beta^{-n^*_i} b^{-s^*_i},\\
\beta^n\alpha^{-n_j}b^{-s_j}&=&\beta^{n^*}\alpha^{-n^*_j}b^{-s^*_j},
\end{eqnarray*}
hold for an arbitrarily large value of $n$. Taking logarithms, we get 
\begin{eqnarray*}
(n-n^*)\log \alpha & = & (n_i-n_i^*)\log \beta+(s_i-s_i^*)\log b,\\
(n-n^*)\log \beta & = &(n_j-n_j^*)\log \alpha+
(s_j-s_j^*)\log b.
\end{eqnarray*}
Since $n$ can be taken as large as we wish, and $\max\{n_i,n_j\}<n$,
we can assume that the rational numbers $v_1=(n_i-n_i^*)/(n-n^*)$ 
and $v_2=(n_j-n_j^*)/(n-n^*)$ are positive and smaller than $1$. 
{From} the above equations, we get that 
$$
\log \alpha=v_1\log \beta+w_1\log b=v_1(v_2\log \alpha+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_1v_2<1$, this shows that
$\log\alpha/\log b$ is rational.  By a similar argument, one
shows that $\log\beta/\log b$ is also rational.  But this contradicts 
our assumption $\dim_{\Z}\langle\log\alpha,\log\beta,\log b\rangle\ge 2$.
Therefore, $n$, $n_i$ and $n_j$ are bounded, and it follows that
$s_i$ and $s_j$ are bounded as well.

\item[$(iii)$] {\it The remaining cases\/}.

For the remaining cases, there are only two possibilities:

\begin{itemize}
\item[$\bullet$] {\it $E_1$ contains
an unknown of the form $x_{2i+1}=\varepsilon_i \alpha^{n_i}b^{s_i}$ 
for some $i\ge 1$ and $E_2$ contains only unknowns of the form 
$x_{2j+1}=\varepsilon_j \alpha^{n_j}b^{s_j}$ with $j\ge 1$ (except 
for $x_2$)\/}.

\item[$\bullet$] {\it $E_1$ contains only unknowns of the form 
$x_{2i}=\varepsilon_i \beta^{n_i}b^{s_i}$ with $i\ge 1$ (except for 
$x_1$) and $E_2$ contains an unknown of the form $x_{2j}=\varepsilon_j 
\beta^{n_j}b^{s_j}$ for some $j\ge 1$\/}. 
\end{itemize}

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

We note that the ratio $x_1/x_{2i+1}=\pm \alpha^{n-n_i}b^{-s_i}$
assumes only finitely many values. If $\alpha$ 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 \alpha/\log b$ is rational.
Then if $j$ is such that $x_{2j+1}\in E_2$, it follows that
$x_2/x_{2j+1}=\pm\beta^{n}\alpha^{-n_j}b^{-s_j}$ can take at most
finitely many values. Since $\alpha$ and $b$ are multiplicatively
dependent, $\beta$ 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.

\end{itemize}

The analysis above completes our proof that~\eqref{eq:maxlogbound2}
holds for some $i$ in the case that
$n>n_i$ for all $i=1,\ldots,t$.  Combining~\eqref{eq:maxlogbound}
and~\eqref{eq:maxlogbound2}, we see that the bound
\begin{equation}
\label{eq:maxlogbound3}
\max\{|n-n_i|,s_i\}\ll\left\{\begin{array}{ll}
1,&\quad\text{if $\alpha\in\R$};\\
\log n,&\quad\text{if $\alpha\not\in\R$~~
(i.e., $\alpha=\overline\beta\,)$};\end{array}\right.
\end{equation}
holds for some $i\in\{1,\ldots,t\}$ in every case.

We now select $i$ such that~\eqref{eq:maxlogbound3} holds
and rewrite~\eqref{eq:mainSuniteq} in the form 
\begin{equation}
\label{eq:intermediaryeq}
c\alpha^n+d\beta^n+Ab^{s_{i-1}}
+c_1\alpha^{n_i}b^{s_i}+d_1\beta^{n_i}b^{s_i}+B=0,
\end{equation}
where $c_1=-\varepsilon_i\varepsilon_0 c$,
$d_1=-\varepsilon_i\varepsilon_0 d$,
$$
A=-\sum_{j=1}^{i-1}\varepsilon_j\varepsilon_0 u_{n_j}b^{s_j-s_{i-1}}
\qquad\text{and}\qquad
B=-\sum_{j=i+1}^t \varepsilon_i\varepsilon_0 u_{n_j} b^{s_j}.
$$
Since 
$$
b^{s_{i-1}}\ge |u_{n_i}|\ge |\alpha|^{n_i+O(\log n_i)}
=|\alpha|^{n+O(\log n)},
$$
we see that $A=\exp(O(\log n))$. Similarly, since $b^{s_i}\ge 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 $\L$ is real).   In this case, $A$ and $B$ are bounded
as well; hence, we can assume that they are fixed.
Here,~\eqref{eq:intermediaryeq} becomes 
\begin{equation}
\label{eq:someequation}
C_1\alpha^n+D_1\beta^n+Ab^{s_{i-1}}+B=0,
\end{equation}
where $C_1=c+c_1\alpha^{n_i-n}$ and $D_1=d+d_1\beta^{n_i-n}$ can also
be regarded as fixed numbers. 
The case $A=B=C_1=D_1=0$ leads to $i=t=1$,
$\alpha^{n-n_i}=-cc_1^{-1}=\pm 1$ 
and $\beta^{n-n_i}=-dd_1^{-1}=\pm 1$; therefore, $t=1$, $n=n_1$,
and $m_1=0$, which contradicts our assumption that $m_1\ge 1$
when $t=1$.  Consequently, the equation~\eqref{eq:someequation}
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~\ref{thm:evSS} can be used if one of the 
coefficients $A,B,C_1,D_1$ is zero, or if $ABC_1D_1\ne 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~\eqref{eq:intermediaryeq}.
In this case, $\alpha$ and $\beta$ are complex conjugates.

Assume first that $B\ne 0$ in equation \eqref{eq:intermediaryeq}. 
Suppose also that $A\ne 0$. 
We apply Theorem \ref{lem:S-unit} with $N=5$, the linear
forms $L_{j,\mu}({\bf x})=x_j$ for each $j=1,\ldots,5$ 
and $\mu\in {\cal S}$, except when $j=1$ and $\mu$ is infinite,
in which case we take $L_{1,\mu}({\bf x})=cx_1+dx_2+x_3+c_1x_4+d_1x_5$ 
(note that, as $\L$ is complex quadratic, there is 
only one infinite place). We evaluate the 
double product appearing in Theorem~\ref{lem:S-unit} for our
system of forms and the points
${\bf x}=(\alpha^n,\beta^n,Ab^{s_{i-1}},\alpha^{n_i}b^{s_i},
\beta^{n_i}b^{s_i})$. Clearly,
\begin{equation}
\label{eq:part1}
\prod_{\mu\in {\cal S}}|L_{j,\mu}({\bf x})|=1
\end{equation}
if $j\in\{2,4,5\}$ since $x_2$, $x_4$ and $x_5$ are ${\cal S}$-units.
Moreover, 
\begin{equation}
\label{eq:part2}
\prod_{\mu\in {\cal S}}|L_{3,\mu}({\bf x})|\le A=\exp(O(\log n)).
\end{equation}
Finally, since $x_1$ is an ${\cal S}$-unit, it follows from
the product formula \eqref{eq:product} that 
\begin{equation}
\label{eq:part3}
\prod_{\substack{\mu\in {\cal S}\\\mu<\infty}}
|L_{1,\mu}({\bf x})|_{\mu}=
\frac{1}{|\Nm_\L(\alpha^n)|}\le \frac{1}{|\alpha|^n},
\end{equation}
while by equation \eqref{eq:intermediaryeq}, we have
\begin{equation}
\label{eq:part4}
\prod_{\substack{\mu\in {\cal S}\\\mu~{\rm is~infinite}}}
|L_{1,\mu}({\bf x})|_{\mu}=B^D=B^2\le \exp(O(\log n)).
\end{equation}
Multiplying the estimates \eqref{eq:part1},
\eqref{eq:part2}, \eqref{eq:part3} and 
\eqref{eq:part4}, we derive that 
\begin{equation}
\label{eq:ineqdouble}
\prod_{j=1}^N\prod_{\mu\in {\cal S}}|L_{j,\mu}({\bf x})|
\le \frac{AB^2}{\alpha^{n}}\le 
\exp\(-n\log \alpha+O(\log n)\).
\end{equation}
Since $\max\{|x_j|:j=1,\ldots,N\}=|\alpha|^n$, the inequality 
\eqref{eq:ineqdouble} together with Theorem~\ref{lem:S-unit}
(for example, with $\varepsilon=1/2$ and $n>n_{\varepsilon}$)
imply that there exist finitely many proper subspaces of $\L^N$
containing all solutions ${\bf x}$. Thus, the relation
\begin{equation}
\label{eq:intermediaryeq1}
C_2\alpha^n+D_2\beta^n+C_3\alpha^{n_i}b^{s_i}+D_3\beta^{n_i}b^{s_i}+
EAb^{s_i-1}=0
\end{equation}
holds for some fixed coefficients $C_2$, $D_2$, $C_3$, $D_3$ and $E$
in $\L$, which are not all equal to zero. If $A=0$, 
one may apply the same argument with $N=4$ to reach the same conclusion. 
Finally, if $B=0$, then~\eqref{eq:intermediaryeq} is the same as 
\eqref{eq:intermediaryeq1} 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 $\L$), that $C_3$ and $D_3$ are conjugate (over $\L$), and that
$E\in \Z$ (if not, we can conjugate \eqref{eq:intermediaryeq1} and
subtract the result from \eqref{eq:intermediaryeq1} to obtain a
``shorter'' nontrivial equation of the same type and with the
desired properties).

If $E=0$, then \eqref{eq:intermediaryeq1} is a ${\cal S}$-unit equation. 
If it is nondegenerate, we see that $\alpha^n\beta^{-n}$ can take only 
finitely many values; since $\alpha/\beta$ is not a root of unity,
there are at most finitely many possibilities for $n$.
If the ${\cal 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|\ll \log n$, it follows that $n$ is bounded as well),
or $C_2D_2\ne 0$ but $C_3=D_3=0$, in which case $n$ can again take
only finitely many values, or $C_2C_3D_2D_3\ne 0$.  In the last case,
either $\alpha^{n-n_i}b^{-s_i}$ and $\beta^{n-n_i}b^{-s_i}$ can take
only finitely many values, or $\alpha^n \beta^{-n_i}b^{-s_i}$ and 
$\beta^n\alpha^{-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\ne 0$, in which case
we can assume that $E=1$.  We now rewrite \eqref{eq:intermediaryeq1}
in the form
\begin{equation}
\label{eq:lastone}
C_4\alpha^n+D_4\beta^n=-Ab^{s_{i-1}},
\end{equation}
where $C_4=C_2+C_3\alpha^{n_i-n}b^{s_i}$ and 
$D_4=D_2+D_3\beta^{n_i-n}b^{s_i}$. Clearly, 
$C_4$ and $D_4$ are conjugates in $\L^*$. Moreover, $C_4$ 
and $D_4$ are algebraic numbers divisible only by primes from
a fixed finite set, namely the set of prime factors of the 
denominators of $C_2$, $C_3$, $D_2$ and $D_3$ together with
the set of prime factors of $(\alpha-\beta)^2$ and $-\alpha\beta$.
A classical argument based on lower bounds for linear forms
in complex and $p$-adic logarithms (see, for example, 
Theorem 3.6 in~\cite{ST}, or~\cite{YuLing})
shows that if $n$ is sufficiently large, then the largest prime factor
in the denominator of the rational number $C_4\alpha^n+D_4\beta^n$
exceeds $n^c$, for any positive constant $c$ 
smaller than $1/(D+1)=1/3$.  It follows that
the diophantine equation \eqref{eq:lastone} admits at most
finitely many solutions $n$.

The proof of Theorem \ref{thm:1} is complete.

\section{Proof of Theorem~\ref{thm:2}}

Before proceeding to the proof of Theorem \ref{thm:2}, we gather 
a few useful facts about the Fibonacci sequence.

We first recall the following special case of the {\it Primitive
Divisor Theorem\/}, which is due to Carmichael~\cite{Carm}:

\begin{lemma}
\label{lem:prim_div}
For all $n\ge 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\equiv \pm 1 \mod n$.
\end{lemma}

Next, we record the following elementary estimate for
$\ell(n)=\ell_{10}(n)$:

\begin{lemma}
\label{lem:length}
For all $n\ge 1$, we have
$$
\frac{(n-2)\log\alpha}{\log 10}<\ell(n)
\le\frac{(n-1)\log\alpha}{\log 10}+1.
$$
\end{lemma}

\begin{proof}
By induction on $k$, it is easy to see that 
$\alpha^{k-2}\le F_k\le\alpha^{k-1}$ holds for all $k\ge 1$.
Since $\ell(k)$ is the unique integer for which
$10^{\ell(k)-1}\le F_k<10^{\ell(k)}$, the result follows.
\end{proof}

We keep the notation used in the proof of Theorem~\ref{thm:1}.
In particular, $\L=\Q(\sqrt{5}\,)$, ${\cal O}_{\L}=\Z[\alpha]$,
and $D=2$ is the degree of $\L$ over $\Q$.  Notice that 
${\cal O}_{\L}$ is a UFD. We also put $\varpi={\sqrt {5}}$ and
${\cal P}=[\varpi]$; then $[p]=[5]={\cal P}^2$,
and $f=1$. We need the following elementary lemma:

\begin{lemma}
\label{lem:valuation}
If $r\ge 2$, we have
$$
\ord_{\cal P}(\alpha^r-1)\le\frac{2\log(r/4)}{\log 5}+1.
$$
The same inequality holds with $\alpha$ replaced by $\beta$.
\end{lemma}

\begin{proof}
The inequality for $\beta$ follows from the one for $\alpha$ by 
conjugation. Note that the right hand side of the stated inequality 
is positive for all $r\ge 2$. Since
$$
\alpha=\frac{1+\sqrt{5}}{2}\equiv 2^{-1}\pmod\varpi,
$$
it follows that ${\ord}_{\cal P}(\alpha^r-1)=0$ 
if $4\nmid r$; hence, it suffices
to assume that $4\,|\,r$ in what follows.  Since
$$
\alpha^4-1=\frac{5+3\sqrt{5}}{2},
$$
it follows that ${\ord}_{\cal P}(\alpha^4-1)=1$. Thus, we may write
$\alpha^4=1+\varpi u$, where $u$ is coprime to $\varpi$. 
If $s\ge 1$ is an integer and $5\nmid s$, then
$$
\alpha^{4s}-1=(\alpha^4-1)\sum_{j=0}^{s-1}\alpha^{4j}
=\varpi u\sum_{j=0}^{s-1}(1+\varpi u)^j
\equiv\varpi us\pmod \varpi,
$$
which shows that $\ord_{\cal P}(\alpha^{4s}-1)=1$ as well. 
One checks similarly that if $s\ge 1$ and $5\nmid s$, 
then $\ord_{\cal P}(\alpha^{20s}-1)=3$.

We now claim that, for all $t\ge 0$ and $s\ge 1$ such that $5\nmid s$, 
we have 
\begin{equation}
\label{eq:claim}
\ord_{\cal P}(\alpha^{4s\cdot 5^t}-1)=2t+1.
\end{equation}
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\ge 2$.  Then,
\begin{eqnarray*}
\alpha^{4s\cdot 5^t}-1
&=&(\alpha^{4s\cdot 5^{t-1}}-1)
\sum_{j=0}^4\alpha^{4sj\cdot 5^{t-1}}\\
&=&5(\alpha^{4s\cdot 5^{t-1}}-1)+
(\alpha^{4s\cdot 5^{t-1}}-1)
\sum_{j=1}^4(\alpha^{4sj\cdot 5^{t-1}}-1).
\end{eqnarray*}
By the induction hypothesis, we have
$$
\ord_{\cal P}\(5(\alpha^{4s\cdot 5^{t-1}}-1)\)=2+\(2(t-1)+1\)=2t+1,
$$
while
$$
\ord_{\cal P}\((\alpha^{4s\cdot 5^{t-1}}-1)
\sum_{j=1}^4(\alpha^{4sj\cdot 5^{t-1}}-1)\)
\ge 2\(2(t-1)+1\)=4t-2>2t+1,
$$
and~\eqref{eq:claim} follows.

Finally, writing $r$ in the form
$r=4s\cdot 5^t$, where $t\ge 0$, $s\ge 1$, and $5\nmid s$,
we have
$$
\ord_{\cal P}(\alpha^r-1)=2t+1=\frac{2\log(r/4s)}{\log 5}+1
\le\frac{2\log(r/4)}{\log 5}+1,
$$
which finishes the proof.
\end{proof}

\begin{lemma}
\label{lem:m_r bounds}
If $(m,n,k)$ is an ordered triple of positive integers such
that $\overline{F_mF_n}=F_k$, and $(m,n,k)\ne(1,4,7)$ or $(2,4,7)$,
then $m\ge 3$ and $k-n\ge 4$.
\end{lemma}

\begin{proof} Suppose that $n\ge 13$.
First, suppose that $m=1$ or $m=2$. Then
$10^{\ell(n)}+F_n=F_k$; hence
$2F_n\ge F_k\le 11F_n$, which (by simple estimates)
implies that $n+2\le k\le n+5$.  Since $n\ge 13$, we have that 
$\ell(n)\ge 3$, and thus,
$$
F_n\equiv F_k\pmod 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^{\ell(n)}=F_{n+1}$, while for $k=n+3$, we have $10^{\ell(n)}=2F_{n+1}$.
However, by Lemma~\ref{lem:prim_div}, there
exists a prime $p\ge n$ dividing $F_{n+1}$, which is not
possible in our cases.  Consequently, if $m\le 2$, we must have $n\le 12$.
Checking the remaining possibilities, the only solutions found 
are $(1,4,7)$ and $(2,4,7)$.

Assuming now that 
$\overline{F_mF_n}=F_k$, $n\ge 15$, and $k\le n+3$, we then have
\begin{equation}
\label{eq:cases}
F_m\cdot 10^{\ell(n)}=F_k-F_n=\left\{\begin{array}{ll}
F_{n-1},&\quad\text{if $k=n+1$};\\
F_{n+1},&\quad\text{if $k=n+2$};\\
2F_{n+1},&\quad\text{if $k=n+3$}.\end{array}\right.
\end{equation}
Moreover, $m<n-1$, for otherwise
$$
F_k=F_m\cdot 10^{\ell(n)}+F_n>1000F_{n-1}>F_{n+3},
$$
contradicting our assumption that $k\le n+3$.
Using Lemma~\ref{lem:prim_div} 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\}\ge 13$, which is not possible in view of~\eqref{eq:cases}.
Hence, if $k\le n+3$, we must have $n\le 14$, and thus $k\le 17$.
Examining these possibilities reveals no solutions other than
the two found in the previous case.
\end{proof}

\begin{lemma}
\label{lem:mult_indep}
If $r\ge 1$ is even, then
$$
\frac{\alpha^r-1}{\beta^r-1}=-\alpha^r,
$$
while if $r\ge 5$ is odd, then the numbers $(\alpha^r-1)/(\beta^r-1)$
and $\alpha$ are multiplicatively independent.
\end{lemma}

\begin{proof}
The first statement is trivial since $\alpha\beta=-1$. For the second 
statement, we note that if $r$ is odd then 
$$
\frac{\alpha^r-1}{\beta^r-1}=-\alpha^r\left(\frac{\alpha^r-1}{\alpha^r+1}
\right).
$$
We now observe that if ${\cal D}$ is the common divisor in ${\cal O}_{\L}$ 
of $\alpha^r-1$ and $\alpha^r+1$, then ${\cal D}~|~2$. Since $2$ is inert 
in ${\cal O}_{\L}$, it follows that ${\cal D}\in \{1,2\}$. The above arguments
show that if $(\alpha^r-1)/(\beta^r-1)$ and $\alpha$ are multiplicatively 
dependent, then so are $(\alpha^r-1)/(\alpha^r+1)$ and $\alpha$.
Using the fact that ${\cal O}_{\L}$ is a UFD
and the computation of ${\cal D}$, 
it follows that $\alpha^r-1$ is either a unit, or it is an associate
of~$2$. Hence, we get an equation of the form
$$
\alpha^r-1=\pm 2^{\lambda}\alpha^t
$$ 
with integers $\lambda\in \{0,1\}$ and $t$. Since $r>3$, it follows
that $\alpha^r-1>\alpha^3-1>2$; hence, the sign in this equation
is positive, and $t\ge 1$.  Clearly, $t<r$. 
Thus, $\alpha^r-1=2^{\lambda} \alpha^t$.  By conjugation, we also have 
$\beta^r-1=2^{\lambda} \beta^t$.  Subtracting
these two equations and dividing the result by $\alpha-\beta$,
we obtain that $F_r=2^{\lambda}F_t$. If $r\ge 13$, 
this equation is impossible in view of Lemma~\ref{lem:prim_div}.
The fact that $F_r=2^{\lambda}F_t$ is also impossible for
$5\le r\le 13$ can be checked by hand, and the result follows. 
\end{proof}

We are now ready to embark on the proof of Theorem \ref{thm:2}.
For this, let $(m,n,k)$ be a fixed triple of nonnegative integers
for which $\overline{F_mF_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~\ref{lem:prim_div}, for example). Put $r=k-n$, and
assume that $k>10^6$. By Lemma~\ref{lem:m_r bounds}, we can
further suppose that $m\ge 3$ and $r\ge 4$.
Since $\beta=-1/\alpha$, we have
\begin{eqnarray*}
F_m\cdot 10^{\ell(n)}=F_k-F_n
&=&\varpi^{-1}(\alpha^k-\beta^k-\alpha^n+\beta^n)\\
&=&\varpi^{-1}(\alpha^n(\alpha^r-1)-\beta^n(\beta^r-1))\\
&=&\varpi^{-1}\alpha^n(\beta^r-1)
\(\(\frac{\alpha^r-1}{\beta^r-1}\)-(-\alpha^{-2})^n\).
\end{eqnarray*}
Consequently,
\begin{equation}
\label{eq:v relation}
\ord_{\cal P}(F_m)+2\ell(n)=-1+\ord_{\cal P}(\beta^r-1)
+\ord_{\cal P}\(\(\frac{\alpha^r-1}{\beta^r-1}\)-(-\alpha^{-2})^n\).
\end{equation}
Assume first that $r$ is odd. We shall apply Theorem \ref{thm:BL} with 
the choices
$\alpha_1=(\alpha^r-1)/(\beta^r-1)$,
$\alpha_2=-\alpha^{-2}$, $b_1=1$, and $b_2=n$. The condition 
that $\alpha_1$
and $\alpha_2$ are multiplicatively independent is satisfied 
by Lemma~\ref{lem:mult_indep} because $r\ge 5$. 
Furthermore, note that 
$$
h(\alpha_1)
\le\tfrac{1}{2}\(\log|(\alpha^r-1)(\beta^r-1)|+\log|\alpha_1|\)
\le\tfrac{1}{2}\log\alpha^{2r}=r\log\alpha,
$$
and $h(\alpha_2)=\log\alpha$. Since $r\ge 5$,
we can choose $A_1=\alpha^r$ and $A_2=\varpi$; hence,
$$
b'=\frac{1}{\log 5}+\frac{n}{2r\log\alpha}
\le \frac{1}{2\log\alpha}+\frac{n}{10\log\alpha}
\le\frac{3n}{4\log\alpha}.
$$
Finally, as $\alpha\equiv\beta\pmod\varpi$, and
$\ord_{\cal P}(\alpha^r-1)=\ord_{\cal P}(\beta^r-1)=0$ 
(by Lemma~\ref{lem:valuation}),
it follows that ${\cal P}$ divides $\alpha_1-1$. Moreover, 
noting that $-\alpha^{-2}\equiv 
1\pmod \varpi$, it follows that ${\cal P}$ also divides $\alpha_2-1$.
Thus, we can take $g=1$. By Theorem~\ref{thm:BL}, 
we obtain the bound
\begin{eqnarray*}
\lefteqn{\ord_{\cal P}
\(\(\frac{\alpha^r-1}{\beta^r-1}\)-(-\alpha^{-2})^n\)}\\
&&\qquad\qquad\le \frac{480r\log\alpha}{(\log 5)^3}
\(\max\left\{\log n+\log\(\frac{3\log 5}{4\log\alpha}\)
+0.4,10\right\}\)^2\\
&&\qquad\qquad\le 56r\(\max\left\{\log n+2,10\right\}\)^2.
\end{eqnarray*}
Next, consider the case that $r$ is even; then 
$$
\frac{\alpha^r-1}{\beta^r-1}-(\alpha^{-2})^n
=-\alpha^r-(-\alpha^2)^n=(-1)^{n+1}\alpha^{-2n}
(\alpha^{k+n}\pm 1),
$$
and the last expression divides $\alpha^{2k+2n}-1$ in ${\cal O}_{\L}$; 
hence, by Lemma \ref{lem:valuation}, we obtain that 
$$
\ord_{\cal P}\(\(\frac{\alpha^r-1}{\beta^r-1}\)-(-\alpha^{-2})^n\)
\le \frac{2\log((k+n)/2)}{\log 5}+1.
$$

Substituting the estimates above into~\eqref{eq:v relation}, and
applying Lemmas~\ref{lem:length} and~\ref{lem:valuation},
we derive that
\begin{equation}
\label{eq:1st est}
2\frac{(n-2)\log\alpha}{\log 10}<\ell(n)
\le\frac{2\log(r/4)}{\log 5}+
56r\(\max\left\{\log n+2,10\right\}\)^2
\end{equation}
if $r$ is odd, and 
\begin{equation}
\label{eq:1st est2}
2\frac{(n-2)\log\alpha}{\log 10}<\ell(n)
\le\frac{2\log(r/4)}{\log 5}+\frac{2\log((k+n)/2)}{\log 5}+1
\end{equation}
if $r$ is even.

{From} the equality $\overline{F_mF_n}=F_k$, we also see that
\begin{equation}
\label{eq:ident}
\alpha^m\cdot 10^{\ell(n)}-\alpha^k
=\beta^m\cdot 10^{\ell(n)}-\alpha^n+\beta^n-\beta^k,
\end{equation}
and, since $10^{\ell(n)}<10F_n$ and $m\ge 3$, we have
\begin{equation}
\label{eq:xx}
\begin{split}
|\alpha^{m-k}\cdot 10^{\ell(n)}-1|
&=\alpha^{-k}|
\beta^m\cdot 10^{\ell(n)}-\alpha^n+\beta^n-\beta^k|\\
&\le\alpha^{-k}(10|\beta|^3F_n+\alpha^n+2)
<4\alpha^{-r}.
\end{split}
\end{equation}
Since $m\ge 3$, both sides of~\eqref{eq:ident} are {\it negative\/},
and since $r\ge 4$, we have $4\alpha^{-r}<\tfrac{3}{5}$; thus,
$$
\tfrac{2}{5}<\alpha^{m-k}\cdot 10^{\ell(n)}<1.
$$
It follows that
\begin{equation}
\label{eq:yy}
|\alpha^{m-k}\cdot 10^{\ell(n)}-1|
>\tfrac{2}{5}|(k-m)\log\alpha-\ell(n)\log 10|.
\end{equation}
We now apply Theorem \ref{thm:LMN} with the choices
$\Lambda=(k-m)\log\alpha-\ell(n)\log 10$, 
$\alpha_1=10$, $\alpha_2=\alpha$, $b_1=\ell(n)$, and
$b_2=k-m$. Here, 
$h(\alpha_1)=\log 10$ and $h(\alpha_2)=\tfrac{1}{2}\log\alpha$; hence,
we can choose $A_1=10$, and $A_2=\alpha^2$, and
$$
b'=\frac{\ell(n)}{4\log\alpha}+\frac{k-m}{20}
<b''=\frac{\ell(n)}{4\log\alpha}+\frac{k}{20}.
$$
Using Theorem \ref{thm:LMN}, we get that 
$$
|(k-m)\log\alpha-\ell(n)\log 10|\ge
\exp\(-864(\max\{\log b''+0.14,10.5\})^2\).
$$
Combining the above estimates, we derive the bound
\begin{equation}
\label{eq:2nd est}
r<\frac{\log 10}{\log\alpha}+\frac{864}{\log\alpha}
(\max\{\log b''+0.14,10.5\})^2.
\end{equation}

Now, if $k>2n$, then, by Lemma~\ref{lem:length}, we have
$$
b''=\frac{\ell(n)}{4\log\alpha}+\frac{k}{20}
\le\frac{n-1}{4\log 10}+\frac{1}{4\log\alpha}+\frac{k}{20}
<\frac{(k/2)-1}{4\log 10}+\frac{1}{4\log\alpha}+\frac{k}{20},
$$
and $r=k-n>k/2$; hence, the inequality~\eqref{eq:2nd est} is
not possible for $k>500000$.  On the other hand, if $k\le 2n$, then
$$
b''=\frac{\ell(n)}{4\log\alpha}+\frac{k}{20}
\le\frac{n-1}{4\log 10}+\frac{1}{4\log\alpha}+\frac{n}{10}.
$$
When $r$ is even, estimate ~\eqref{eq:1st est2} gives
$$
\frac{(n-2)\log \alpha}{\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~\eqref{eq:1st est}, and~\eqref{eq:2nd est},
we obtain a contradiction unless $n\le 1.1\times 10^{11}$ and
$k\le 2n\le 2.2\times 10^{11}$.

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

Suppose that $n\le 1.1\times 10^{11}$ and $r\ge 56$.
By~\eqref{eq:xx} and~\eqref{eq:yy}, we have
$$
\left|\frac{\log 10}{\log\alpha}-\frac{(k-m)}{\ell(n)}\right|
<\frac{10}{\alpha^r\ell(n)}\le\frac{1}{2\ell(n)^2}.
$$
Here, the last inequality is equivalent to $20\ell(n)\le\alpha^r$,
which holds (by Lemma~\ref{lem:length}) for this choice of parameters.
By well known properties of continued fractions, it follows that 
$(k-m)/\ell(n)$ is a convergent of $(\log 10)/(\log\alpha)$. 
Writing $(k-m)/\ell(n)=p_j/q_j$ for some $j\ge 0$, where 
$p_j/q_j$ denotes the $j$th convergent to $(\log 10)/(\log \alpha)$, 
and using Lemma~\ref{lem:length} again to bound $\ell(n)$ 
for $n$ in our range, we see that
$q_j\le\ell(n)\le 2.3\times 10^{10}$, which implies that $j\le 23$.
Noting that
$$
10\alpha^{-r}>|\ell(n)\log 10-(k-m)\log\alpha|
\ge\min_{1\le j\le 23}|q_j\log 10-p_j\log\alpha|>1.6\times 10^{-11},
$$
we conclude that $r\le 57$.  Substituting this estimate
into~\eqref{eq:1st est}, we derive the more tractable upper bound
$n\le 2.1\times 10^6$.

At this point, we turn to the computer.  Note that if $n\ge 74$,
one has $\ell(n)\ge 15$; therefore, if $\overline{F_mF_n}=F_k$,
it follows that $F_n\equiv F_k\pmod{10^{15}}$.  However, a computer
search quickly reveals that there is no solution to this congruence
with $74\le n\le 2.1\times 10^6$ and $k\le n+57$.  Thus, 
it remains only to search for solutions $(m,n,k)$ with $n\le 73$
and $k\le n+57$, and one obtains only solutions with $k=7$, $8$ or $10$;
that is $F_k\in\{13,21,55\}$.

This completes the proof of Theorem~\ref{thm:2}.

\begin{thebibliography}{99}

\bibitem{BaCoSh} W.~Banks, A.~Conflitti and I.E.~Shparlinski,
Character sums over integers with restricted $g$-ary digits,
{\it Illinois J.\ Math.\/} {\bf 46} (2002), 819--836.

\bibitem{BaHaSa} W.~Banks, D.~Hart and M.~Sakata,
Almost all palindromes are composite,
to appear in {\it Math.\ Res.\ Lett.\/}.

\bibitem{BaSh} W.~Banks and I.E.~Shparlinski,
On the number of sparse RSA exponents,
{\it J.\ Number Theory\/} {\bf 95} (2002), 340--350.

\bibitem{BL} Y.~Bugeaud and M.~Laurent,
Minoration effective de la distance \hbox{$p$-adique} entre puissances
de nombres alg\'ebriques,
{\it J.\ Number Theory\/} {\bf 61} (1996), 311--342.

\bibitem{Carm} R.~D.~Carmichael,
On the numerical factors of the arithmetic forms
$\alpha\sp n1\beta\sp n$,
{\it Ann.\ of Math.\ (2)\/} {\bf 15} (1913/14), 30--70.

\bibitem{EMS1} P.~Erd{\H o}s, C.~Mauduit and A.~S{\'a}rk{\"o}zy,
On arithmetic properties of integers with missing digits, I,
{\it J.\ Number Theory\/} {\bf 70} (1998), 99--120.

\bibitem{EMS2} P.~Erd{\H o}s, C.~Mauduit and A.~S{\'a}rk{\"o}zy,
On arithmetic properties of integers with missing digits, II,
{\it Discrete Math.\/} {\bf 200} (1999), 149--164.

\bibitem{ESS} J.-H.~Evertse, H.P.~Schlickewei and W.M.~Schmidt, 
Linear equations with variables which lie in a multiplicative group, 
{\it Ann.\ of Math.\ (2)} {\bf 155} (2002), 807--836.

\bibitem{FilKon} M.~Filaseta and S.V.~Konyagin,
Squarefree values of polynomials all of whose coefficients are
$0$ and $1$,
{\it Acta Arith.\/} {\bf 74} (1996), 191--205.

\bibitem{FoMa1} E.~Fouvry and C.~Mauduit,
Meth\'odes des crible et fonctions sommes des chiffres,
{\it Acta Arith.\/} {\bf 77} (1996), 339--351.

\bibitem{FoMa2} E.~Fouvry and C.~Mauduit,
Sommes des chiffres et nombres presque premiers,
{\it Math.\ Ann.\/} {\bf 305} (1996), 571--599.

\bibitem{FrSh} J.B.~Friedlander and I.E.~Shparlinski,
On the distribution of Diffie--Hellman triples
with sparse exponents,
{\it  SIAM J.\ Discrete Math.\/} {\bf 14} (2001), 162--169.

\bibitem{Gel} A.O.~Gel'fond,
Sur les nombres qui ont des propri\'et\'es additives
et multiplicatives donn\'ees,
{\it Acta Arith.\/} {\bf 13} (1968), 259--265.

\bibitem{Kon} S.V.~Konyagin,
Arithmetic properties of integers with missing digits:
distribution in residue classes,
{\it Period.\ Math.\ Hungar.\/} {\bf 42} (2001), 145--162.

\bibitem{KoMaSa} S.V.~Konyagin, C.~Mauduit and A.~S\'ark\H ozy,
On the number of prime factors of integers
characterized by digit properties,
{\it Period.\ Math.\ Hungar.\/} {\bf 40} (2000), 37--52.

\bibitem{Lu} F.~Luca,
Distinct digits in base $b$ expansions of linear 
recurrence sequences,
{\it Quaest.\ Math.\/} {\bf 23} (2000), 389--404.

\bibitem{Luca} F.~Luca,
Arithmetic properties of positive integers with fixed digit sum,
to appear in {\it Rev.\ Mat.\ Iberoamericana}.

\bibitem{MaSa1} C.~Mauduit and A.~S{\'a}rk{\"o}zy,
On the arithmetic structure of sets characterized
by sum of digits properties,
{\it J.\ Number Theory\/} {\bf 61} (1996), 25--38.

\bibitem{MaSa2} C.~Mauduit and A.~S{\'a}rk{\"o}zy,
On the arithmetic structure of the integers whose
sum of digits is fixed,
{\it Acta Arith.\/} {\bf 81} (1997), 145--173.

\bibitem{LMN}
M.~Laurent, M.~Mignotte and Y.~Nesterenko,
Formes lin\'eaires en deux logarithmes et
d\'eterminants d'interpolation,
{\it J.\ Number Theory\/} {\bf 55} (1995), 285--321.

\bibitem{Schm1} W.M.~Schmidt,
{\it Diophantine Approximations\/},
Springer Verlag, LNM {\bf 785} (1980).

\bibitem{Schm2} W.M.~Schmidt,
{\it Diophantine Approximations and Diophantine Equations\/},
Springer Verlag, LNM {\bf 1467} (1991).

\bibitem{SS1} H.G.~Senge and E.G.~Straus, 
${\rm PV}$-numbers and sets of multiplicity, in
{\it 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.

\bibitem{SS2} H.G.~Senge and E.G.~Straus, 
${\rm PV}$-numbers and sets of multiplicity',
in ``Collection of articles dedicated to the memory
of Alfr\'ed R\'enyi, II'',
{\it Period.\ Math.\ Hungar.\/} {\bf 3} (1973), 93--100.

\bibitem{ST} T.N.~Shorey and R.~Tijdeman,
{\it Exponential diophantine equations\/},
Cambridge Univ.\ Press, 1986.

\bibitem{Shp} I.E.~Shparlinski,
Prime divisors of sparse integers,
{\it Period.\ Math.\ Hungar.\/} {\bf 46} (2003), 215--222.

\bibitem{Stew} C.L.~Stewart,
On the representation of an integer in two different bases,
{\it J.\ Reine Angew.\ Math.\/} {\bf 319} (1980), 63--72.

\bibitem{YuLing} K.R.~Yu and L.K.~Hung,
On binary recurrence sequences,
{\it Indag.\ Math.\ (N.S.)\/} {\bf 6} (1995), 341--354.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary ; Secondary .

\noindent \emph{Keywords: xxx}

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A0xxxxx}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received 
revised version received  
Published in {\it Journal of Integer Sequences},

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in


\end{document}