\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{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{anysize}
\DeclareMathOperator{\sign}{sgn}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\Large\bf
On Arithmetic Progressions in Lucas Sequences
}
\vskip 1cm
Lajos Hajdu\footnote{The author was supported by the NKFIH grant 115479.}\\
Institute of Mathematics\\ University of Debrecen\\ P. O. Box 400\\ H-4002 Debrecen\\ Hungary\\
\href{mailto:hajdul@science.unideb.hu}{\tt hajdul@science.unideb.hu}\\
\ \\
M\'arton Szikszai\footnote{The author was supported by the Hungarian Academy of Sciences.}\\
Institute of Mathematics, University of Debrecen\\ and\\ MTA-DE Research Group Equations Functions and Curves\\
Hungarian Academy of Sciences and University of Debrecen\\ P. O. Box 400\\ H-4002 Debrecen\\ Hungary\\
\href{mailto:szikszai.marton@science.unideb.hu}{\tt szikszai.marton@science.unideb.hu}\\
\ \\
Volker Ziegler\footnote{The author was supported by the Austrian Research Foundation (FWF), Project P24801-N26.}\\
Institute of Mathematics\\ University of Salzburg\\ Hellbrunnerstrasse 34/I\\ A-5020 Salzburg\\ Austria\\
\href{mailto:volker.ziegler@sbg.ac.at}{\tt volker.ziegler@sbg.ac.at}\\
\end{center}
\vskip .2 in
\begin{abstract}
In this paper, we consider arithmetic progressions contained in Lucas
sequences of the first and second kind. We prove that for almost all
Lucas sequences, there are only finitely many arithmetic three term
progressions and their number can be effectively bounded. We also show
that there are only a few Lucas sequences which contain infinitely many
arithmetic three term progressions and one can explicitly list both the
sequences and the progressions in them. A more precise statement is
given for sequences with dominant zero.
\end{abstract}
\section{Introduction}
The study of additive structures in certain sets of integers has a long history.
In particular, the description of arithmetic progressions has attracted the attention of many researchers
and is still an actively studied topic with a
vast literature. Without trying to be exhaustive and going into details we only
mention a few interesting directions.
Bremner \cite{bremner} found infinitely many elliptic curves such that among the
first coordinates of rational points one can find an eight term arithmetic
progression. Campbell \cite{campbell}, modifying ideas of Bremner, gave the
first example of a progression of length twelve which was later improved to
fourteen by MacLeod \cite{macleod}. For more details on the various
generalizations to other families of curves and recent progress we refer to the
paper of Ciss and Moody \cite{cissmoody} and the references given there.
The study of arithmetic progressions in solution sets of Pellian equations is another interesting direction.
Dujella, Peth\H{o}, and Tadi\'c \cite{dujellapethotadic} showed that for every four term arithmetic progression $(y_1,y_2,y_3,y_4)\neq (0,1,2,3)$ there exist infinitely many pairs $(d,m)$ such that the equation $x^2-dy^2=m$ admits solutions with $y=y_i$ for $i=1,2,3,4$.
On the other hand, Peth\H{o} and Ziegler \cite{pethoziegler} proved that for five term
arithmetic progressions only a finite number of such equations are possible. For
further progress we refer to the papers of Aguirre, Dujella, and Peral
\cite{aguirredujellaperal} and Gonz\'alez-Jim\'enez \cite{gonzalezjimenez}.
In this paper, we connect to the field by considering arithmetic progressions in
Lucas sequences. Let $A$ and $B$ be non-zero integers such that the zeros
$\alpha$ and $\beta$ of the polynomial
\begin{equation}
\label{charpoly}
x^2-Ax-B
\end{equation}
satisfy that $\alpha/\beta$ is not a root of unity. Define the sequences
$u=(u_n)_{n=0}^\infty$ and $v=(v_n)_{n=0}^\infty$ via the binary recurrence
relations
\begin{equation}
\label{recurrence}
u_{n+2}=Au_{n+1}+Bu_n\qquad \mathrm{and} \qquad v_{n+2}=Av_{n+1}+Bv_n \qquad (n\geq 0)
\end{equation}
with initial values $u_0=0,\ u_1=1$ and $v_0=2,\ v_1=A$. We call $u$ and $v$ the
Lucas sequences of the first and second kind corresponding to the pair $(A,B)$,
respectively.
\begin{remark}
The classical definition of $u$ and $v$ requires $\gcd(A,B)=1$ which is needed for
certain arithmetic properties to hold. Hence our definition is more relaxed.
\end{remark}
\begin{remark}
The assumption on the zeros of the companion polynomial \eqref{charpoly}
coincides with the non-degeneracy property. The study of all linear recurrences
can effectively be reduced to such sequences, see
\cite{everestpoortenshparlinskiward}.
\end{remark}
The investigation of arithmetic progressions in linear recurrences is not an entirely new topic.
Pint\'er and Ziegler \cite{pinterziegler} gave a criterion
for linear recurrences of general order to contain infinitely many three term
arithmetic progressions. Note that the study of three term arithmetic
progressions is the first non-trivial problem and is the most general.
Further, they proved that the
sequence of Fibonacci and Jacobsthal numbers are the only increasing Lucas
sequences having infinitely many three term progressions.
In this paper, we connect to the results of Pint\'er and Ziegler. On one hand,
we give an upper bound for the number of three term arithmetic progressions provided
that there are only finitely many. On the other hand, we explicitly list all those sequences which
contain infinitely many three term arithmetic progressions. Finally, by restricting
ourselves to sequences with companion polynomials having a dominant zero, we
find all sequences which contain a three term arithmetic progression and give a
complete list of the occurrences.
Our main result is as follows:
\begin{theorem}
\label{theorem1}
Let $u=(u_n)_{n=0}^\infty$ and $v=(v_n)_{n=0}^\infty$ be the Lucas sequences of
first and second kind, respectively, corresponding to the pair $(A,B)$. Then $u$
and $v$ admit at most $6.45\cdot 10^{2340}$ triples $(k,l,m)$ such that $u_k0$. Then $u$ and $v$ admit no three term
arithmetic progression, except the cases listed in Tables \ref{table1} and
\ref{table2}, respectively.
\end{theorem}
\begin{table}[ht]
\centering
\begin{tabular}{|c|c|}
\hline
$(A,B)$ & $(k,l,m)$\\
\hline
$(1,1)$ & $(0,1,3),\ (2,3,4),\ (t,t+2,t+3),\ t\geq 0$\\
\hline
$(-1,1)$ & $(1,0,2),\ (t,t+1,t+3),\ t\geq 0$\\
\hline
$(1,2)$ & $(1,2t+1,2t+2),\ (2,2t+1,2t+2),\ t\geq 1$\\
\hline
$(-1,2)$ & $(t+2,t,t+1),\ t\geq 0$\\
\hline
$(2,B),\ B\geq 1$ & $(0,1,2)$\\
\hline
$(1,B),\ B\geq 3$ & $(1,3,4),\ (2,3,4)$\\
\hline
$(-1,B),\ B\geq 3$ & $(1,0,2)$\\
\hline
\end{tabular}
\caption{Triples $(k,l,m)$ s.t. $(u_k,u_l,u_m)$ is a three term AP.}
\label{table1}
\end{table}
\begin{table}[ht]
\centering
\begin{tabular}{|c|c|}
\hline
$(A,B)$ & $(k,l,m)$\\
\hline
$(1,1)$ & $(1,0,2),\ (t,t+2,t+3),\ t\geq 0$\\
\hline
$(-1,1)$ & $(t,t+1,t+3),\ t\geq 0$\\
\hline
$(-1,2)$ & $(t,t-1,t+1),\ t\geq 1$\\
\hline
$(-2,1)$ & $(1,0,2)$\\
\hline
$(1,3)$ & $(1,4,5)$\\
\hline
$(-3,-1)$ & $(1,0,2)$\\
\hline
\end{tabular}
\caption{Triples $(k,l,m)$ s.t. $(v_k,v_l,v_m)$ is a three term AP.}
\label{table2}
\end{table}
As an immediate consequence of Theorem \ref{theorem2} we have the following:
\begin{corollary}
\label{cor}
Let $u=(u_n)_{n=0}^\infty$ (resp.\ $v=(v_n)_{n=0}^\infty$) be the Lucas sequence
of the first (resp.\ second) kind corresponding to the pair $(A,B)$. Assume that
$A^2+4B>0$. If $u$ (resp.\ $v$) contains more than two (resp.\ one)
three term arithmetic progressions, then $u$ (resp.\ $v$) contains infinitely
many three term arithmetic progressions.
\end{corollary}
The ineffective methods we use in the proof of Theorem \ref{theorem1} do not
give such sharp bounds as in Corollary \ref{cor}. However, it would be
interesting to find optimal bounds also in the general case, i.e., if we drop the
condition $A^2+4B>0$ in Corollary \ref{cor}.
In the next section, we prove Theorem \ref{theorem2}. The main idea is to show
that under a testable condition, the growth of the sequence would contradict the
existence of any three term arithmetic progression. Further, this condition leaves only
finitely many explicitly given possibilities for $(A,B)$ which we treat one by
one, usually in an
elementary way. The proof of Theorem \ref{theorem1} in Section \ref{Sec:imag} is
based on the theory of $S$-unit equations.
\section{The dominant zero case}\label{Sec:real}
This section is devoted to the case, where $A^2+4B>0$, that is, the zeros of the
companion polynomial \eqref{charpoly} are real. First, we remark that in any linear recurrence,
the terms can be represented as polynomial-exponential sums depending on the
zeros of the companion polynomial. In our situation, this leads to the
well-known formulas
\[
u_n=\dfrac{\alpha^n-\beta^n}{\alpha-\beta} \qquad \mathrm{and} \qquad
v_n=\alpha^n+\beta^n \qquad (n\geq 0).
\]
We will regularly use this interpretation of Lucas sequences
instead of the recurrence relation \eqref{recurrence}.
The following lemma concerns equations satisfied by three term arithmetic
progressions.
\begin{lemma}
\label{lemmatech}
Let $u=(u_n)_{n=0}^\infty$ be any sequence. Suppose that for some $n_0$ we
have $|u_n/u_{n'}|>3$ for every $n>n_0$ and every $n'n_0$, then
neither of the
equations
\begin{equation}
\label{equation:klm}
u_k-2u_l+u_m=0, \qquad u_l-2u_k+u_m=0,\qquad u_k-2u_m+u_l=0
\end{equation}
has a solution $(k,l,m)$ with $kn_0$.
\end{lemma}
\begin{proof}
Assuming that $n_03|u_l|-3|u_l|=0.
\]
Thus the first equation of \eqref{equation:klm} has no solution with $k0$. Assume that $n>n'$. Then $|u_n/u_{n'}|>3$ if $n$ is odd
or $n\geq 8$, unless
\begin{itemize}
\item $B<0$ and $|A|\leq 6$ or
\item $|A|=1$ and $0**6$ or $|B|>9$, then we have
$|\alpha|>3$ and may write
\[
\left|\dfrac{u_n}{u_{n-1}}\right|=\left|\dfrac{\dfrac{\alpha^n-\beta^n}{
\alpha-\beta}}{\dfrac{\alpha^{n-1}-\beta^{n-1}}{\alpha-\beta}}
\right|=\left|\dfrac{\alpha^n}{\alpha^{n-1}}\dfrac{1-\left(\frac{\beta}{\alpha}
\right)^{n}}{1-\left(\frac{\beta}{\alpha}\right)^{n-1}}
\right|=|\alpha|\left|\dfrac{1-\theta^n}{1-\theta^{n-1}}\right|>3\left|\dfrac{
1-\theta^n}{1-\theta^{n-1}}\right|
\]
with $\theta=\beta/\alpha$. It suffices to prove that
\[
\left|\dfrac{
1-\theta^n}{1-\theta^{n-1}}\right|>1.
\]
Observe that there are trivial cases. These include $\theta>0$ and also
$\theta<0$ when $n$ is odd. What remains to consider is the case when $\theta<0$
and $n$ is even.
Next, we show that the quotients $|u_{2n+2}/u_{2n+1}|$ increase with
$n$, that is, they satisfy the inequality
\[
\left|\dfrac{u_{2n+2}}{u_{2n+1}}\right|>\left|\dfrac{u_{2n}}{u_{2n-1}}\right|.
\]
Equivalently, we may write
\[
|\alpha|\left|\dfrac{1-\theta^{2n+2}}{1-\theta^{2n+1}}
\right|>|\alpha|\left|\dfrac{1-\theta^{2n}}{1-\theta^{2n-1}}\right|.
\]
Since $0<|\theta|<1$, it reduces to
\[
\dfrac{1-\theta^{2n+2}}{1-\theta^{2n+1}}>\dfrac{1-\theta^{2n}}{1-\theta^{2n-1}}
\]
giving us
\[
1-\theta^{2n-1}-\theta^{2n+2}+\theta^{4n+1}>1-\theta^{2n+1}-\theta^{2n}+\theta^{
4n+1}.
\]
Collecting the terms on the left hand side and dividing both sides of the
inequality by $-\theta^{2n-1}>0$ we obtain
\[
\theta^3-\theta^2-\theta+1=(\theta-1)^2(\theta+1)>0,
\]
which is obviously true for any $\theta$ with $0<|\theta|<1$. Since
$|u_2/u_1|=|A|\geq 1$, we have, in particular, that $|u_{n}/u_{n-1}|>1$ for all
$n\geq 0$. This proves the lemma for all odd $n$ and all $n>2n_0$ with
$|u_{2n_0}/u_{2n_0-1}|>3$. Thus we need to show that $|u_{8}/u_{7}|>3$ under our
hypotheses.
We distinguish between the cases where $B>0$ and $B<0$. Let us start with $B<0$.
We have
\[
|\theta|=\left|\frac{\beta}{\alpha}\right|=\frac{|A|-\sqrt{A^2+4B}}{|A|+\sqrt{
A^2+4B}}\leq \frac{|A|-1}{|A|+1}=1-\frac{2}{|A|+1}.
\]
Note that in this case we also have that $|\alpha|>\frac{|A|+1}2$. Write $x=\frac{|A|+1}2$.
We show that
\[
\left|\dfrac{u_{8}}{u_{7}}\right|\geq x \frac{1-\left(1-\dfrac
1x\right)^{8}}{1+\left(1-\dfrac 1x\right)^{7}}>3.
\]
Solving this inequality for $x$ shows that the second inequality holds unless
$x<3.55$, i.e., $|A|<6.1$.
When $B>0$, we have
\[
|\theta|=\left|\frac{\beta}{\alpha}\right|=\frac{\sqrt{A^2+4B}-|A|}{\sqrt{A^2+4B
}+|A|}=1-\frac{2|A|}{\sqrt{A^2+4B}+|A|}
\]
and with $|A|\geq 3$ we obtain
\[
|\theta|\geq 1+\frac{6}{\sqrt{9+4B}+3}
\]
and
\[
|\alpha|>\dfrac{\sqrt{9+4B}+3}2=:y.
\]
We need to show that
\[
\left|\dfrac{u_{8}}{u_{7}}\right|\geq y \frac{1-\left(1-\dfrac
3y\right)^{8}}{1+\left(1-\dfrac 3y\right)^{7}}>3.
\]
The inequality holds unless $y\leq 3$. However, $y\leq 3$ is impossible, since
it would imply $B\leq 0$ which we excluded.
Similar arguments for the cases $|A|=2$ and $|A|=1$ yield that
$\left|\dfrac{u_{8}}{u_{7}}\right|>3$ provided that $B>9$ and $B>3$,
respectively.
\end{proof}
A similar argument for Lucas sequences of the second kind reveals the following.
\begin{lemma}
\label{lem:growth_comp}
Let $v=(v_n)_{n=0}^\infty$ be the Lucas sequence of the second kind corresponding to the pair
$(A,B)$, with $A^2+4B>0$. Assume that $n>n'$. Then $|u_n/u_{n'}|>3$ if $n$ is
even or $n\geq 7$, unless
\begin{itemize}
\item $B<0$ and $|A|\leq 7$ or
\item $|A|=1$ and $0****6$.
\end{proof}
Now we apply Lemma \ref{lemmatech} in combination with Lemma
\ref{lem:growth_Lucas} and find that if $u$ admits a three term
arithmetic progression, then one of the equations in \eqref{equation:klm} must
have a solution with even $m\leq 6$. Writing the terms of $u$ as polynomials in
$A$ and $B$ we have to deal with finitely many equations. We only present the main
ideas through one example for each different type of possible equations, we treat the rest in a similar manner.
\textbf{Case $m=2$.} Since $u_0=0,\ u_1=1$ and $u_2=A$, we only get trivial
equations like $A-2=0$.
\textbf{Case $m=4$.} The corresponding equations are linear in $B$. For
example, the triple $(k,l,m)=(1,2,4)$ substituted into the second equation of
\eqref{equation:klm} gives us
\[
A^3+2AB+A-2=0
\]
implying
\[
B=\dfrac{-A^3-A+2}{2A}.
\]
Hence $A\mid 2$, i.e., $A=\pm1,\pm2$. However,
we see that one of the conditions $AB\neq 0$ and $A^2+4B>0$ fails in all cases. One can handle the other equations similarly.
\textbf{Case $m=6$.} The corresponding equations are quadratic in $B$. Our
general strategy is to push the discriminant of each equation between two squares and solve the
parametric equation for each square between these lower and upper bounds. For
example, the triple $(k,l,m)=(0,3,6)$ and the third equation of
\eqref{equation:klm} gives
\[
-6AB^2+(-8A^3+1)B-2A^5+A^2=0.
\]
The discriminant is $D=16A^6+8A^3+1=(4A^3+1)^2$. However, solving this for $B$
we get the pair $(A,B)=(A,-A^2)$ and $A^2+4B>0$ fails to hold.
Let us consider another example. For instance, take the triple
$(k,l,m)=(0,2,6)$. Then we obtain $D=A^6+6A^2-3A$. But
$$A^63$ and we deduce that $D$
is never a square if $|A|>3$.
For those with $|A|\leq 3$ and $A\neq 0$ we obtain that $D$ is a square if
and only if $A=1$. In this case, $B=0$ which contradicts our assumption.
The same approach for each triple gives the complete list of three term arithmetic
progressions.
We are left with the finite number of sequences satisfying
\begin{itemize}
\item $B<0$ and $|A|\leq 6$ or
\item $|A|=1$ and $0****l+1>k+1$. Then
\[
|\alpha|^m-2|\alpha|^{m-2}-|\alpha|^{m-3}
<|\alpha^k+\alpha^m-2\alpha^l|=|\beta^k+\beta^m-2\beta^m|<4|\beta|^k.
\]
Plugging in the concrete values of $\alpha$ and $\beta$ we immediately get
\[
(1+\sqrt{2})^{m-3}\left((1+\sqrt{2})^3-2(1+\sqrt{2})-1\right)=(4+3\sqrt
2)(1+\sqrt{2})^{m-3}<4
\]
which yields a contradiction unless $m<3$. Now it is easy to find all three term
arithmetic progressions in this case. Note that in the case of $l>m$ or $k>m$ we may draw similar conclusions.
Hence we can assume that $m=l+1>k+1$. Then
\[
|\alpha|^m-2|\alpha|^{m-1}<|\alpha|^{k}+4|\beta|^k
\]
and inserting the concrete values of $\alpha$ and $\beta$ we get
\[
(1+\sqrt 2)^{m-2}<(1+\sqrt 2)^{k}+4.
\]
Assuming $k\leq m-3$ yields
\[
\sqrt{2}(1+\sqrt 2)^{m-3}<4,
\]
whence $m\leq 4$ and we easily find all three term arithmetic progressions
listed in Table \ref{table1} for this case. Finally, we have to consider the
case when $m=l+1=k+2$. Here we get the inequality
\[
\left|\alpha^m-2\alpha^{m-1}-\alpha^{m-2}\right|<4|\beta|^k
\]
which yields
\[
2(1+\sqrt 2)^{m-2}<4,
\]
that is, $m\leq 3$ and we find no additional three term arithmetic progressions.
Similar arguments for different orderings of $u_k,u_l,u_m$ reveal no further
solutions. Thus the case $A=2$ and $B=1$ is completely solved.
\section{The case $A^2+4B<0$}\label{Sec:imag}
Unfortunately, we found no effective method to resolve this case completely. The
reason has its roots in the use of the theory of $S$-unit equations. Indeed, the
indices $k,l,m$ corresponding to a non-trivial arithmetic progression
$u_k|\beta|$ and that $\left|\dfrac{u_n}{u_{n-1}}\right|\simeq |\alpha|$ as $n\rightarrow \infty$.
If $A^2+4B<0$, then this is no longer true and we have to apply
the deep theory of $S$-unit equations.
In order to determine an upper bound for the number of solutions we prove a
series
of Lemmas which culminate in a proof for Theorem \ref{theorem1}.
Before we start with the first lemma, let us note that both $\alpha$ and $\beta$
are algebraic integers. Moreover, due to Theorem \ref{theorem2}, which was proved in
the previous section, we may assume that $\alpha$ and $\beta$ are conjugate
imaginary quadratic integers. Hence we can suppose that $\alpha$ and
$\beta$ are not units, otherwise $\alpha/\beta$ would be a root of unity. Thus
we may suppose that $|B|\geq 2$. Write $K=\Q(\alpha)=\Q(\beta)$ and denote by
$\sigma$ the unique, nontrivial $\Q$-automorphism of $K$, i.e.,
$\mathrm{Gal}(K/\Q)=\{\mathrm{id},\sigma\}$. Since $K$ is an imaginary quadratic
field, we also have that $\sigma(\epsilon)=\epsilon^{-1}$, where $\epsilon$ is
any unit in $K$.
For fixed $\alpha$ and $\beta$ we denote by $C_1$ and $C_2$ the number of
non-trivial three term arithmetic progressions of $(u_n)_{n=0}^{\infty}$ and
$(v_n)_{n=0}^{\infty}$, respectively and write $C=\max\{C_1,C_2\}$. Actually,
our upper bounds for $C_1$ and $C_2$ coincide in each instance and hence we use
only the quantity $C$.
Let $\Gamma=\langle\alpha,\beta\rangle\leq \bar\Q^*$ be the
multiplicative group generated by $\alpha$ and $\beta$. We denote by
$A=A(a_0,\dots,a_r)$ the number of non-degenerate, projective solutions
$\lbrack x_0:\dots:x_r \rbrack\in\mathbb{P}^r(\Gamma)$ of the weighted, homogeneous $S$-unit
equation
\begin{equation}\label{eq:S-unit}
a_0u_0+\dots+a_ru_r=0.
\end{equation}
with $a_0,\dots,a_r\in \mathbb{C}$, in unknowns $u_0,\dots,u_r\in\Gamma$. By a non-degenerate solution we mean a solution to equation \eqref{eq:S-unit} such that no subsum on the left hand side
of equation \eqref{eq:S-unit} vanishes. Upper bounds $A(a_0,\dots,a_r)\leq
A(r,s)$, where $s$ denotes the rank of $\Gamma$, have been found most prominently
by Evertse, Schlickewei, and Schmidt \cite{Evertse:2002} and Amoroso and Viada
\cite{Amoroso:2009} in the most general case. In particular, we use the bounds
due to Schlickewei and Schmidt \cite{Schlickewei:2000} which in our case yield better
results, although they depend on $d=\lbrack K:\Q \rbrack$ as well.
As we already noted above, three term arithmetic progressions in the Lucas
sequences $(u_n)_{n=0}^\infty$ and $(v_n)_{n=0}^\infty$ yield solutions to
\eqref{eq:AP}. Thus we study the weighted $S$-unit equation
\begin{equation}\label{eq:S-unit2}
x_1+x_2-2x_3=\pm(y_1+y_2-2y_3),
\end{equation}
where $x_1,x_2,x_3,y_1,y_2,y_3\in \Gamma=\langle\alpha,\beta\rangle$ and, in
particular, where $x_1=\alpha^k,x_2=\alpha^m,x_3=\alpha^l,
y_1=\beta^k,y_2=\beta^m,y_3=\beta^l$.
Before we start investigating $S$-unit equations of type \eqref{eq:S-unit2} we state a theorem due to Beukers~\cite[Theorem 2]{Beukers:1980}
and draw some simple conclusions from it.
\begin{lemma}[Beukers~\cite{Beukers:1980}]
Let the non-degenerate recurrence sequence of rational integers $(u_n)_{n=0}^\infty$ be given by $u_0\geq 0$, $\gcd(u_0, u_1)=1$,
$u_n = Au_{n-1} - Bu_{n-2}$, with $A, B\in\Z$ and $A\geq 0$. Assume that $A^2 - 4B < 0$. If $u_m =\pm u_0$ has
more than three solutions $m$, then one of the following cases holds:
\begin{align*}
A=1, B=2,& u_0=u_1=1& \text{when\ \ }& \ m=0,1,2,4,12;\\
A=1, B=2,& u_0=1, u_1=-1& \text{when\ \ }& \ m=0,1,3,11;\\
A=3, B=4,& u_0=u_1=1& \text{when\ \ }& \ m=0,1,2,6;\\
A=2, B=3,& u_0=u_1=1& \text{when\ \ }& \ m=0,1,2,5.
\end{align*}
\end{lemma}
From this Lemma we can easily conclude the following statement.
\begin{lemma}\label{lem:multiplicity}
Let $(u_n)_{n=0}^\infty$ be a Lucas sequence of the first or second kind. Then for a fixed integer $\lambda$ the equation
$\lambda=u_m$ has at most $3$ solutions $m$.
\end{lemma}
\begin{proof}
Let $m_0$ be the smallest solution to $\lambda=u_m$. Consider instead of the original sequence the sequence $a_k=u_{m_0+k}/g(-1)^{k\delta}$,
where $g=\sign(u_{m_0})\gcd(u_{m_0},u_{m_0+1})$ and $\delta=\frac{1-\sign(A)}2$ (see also the remarks following Theorem 2 in \cite{Beukers:1980}).
Therefore we conclude that an equation of the form $\lambda=|u_m|$ has more than three solutions if for the smallest solution $m_0$, also $m_0+1$ is a solution and $(A,B)=(\pm 1,-2),(\pm 3,-4)$ or $(\pm 2,-3)$.
However, the equation $|u_{m_0}|=|u_{m_0+1}|$ is equivalent to the equation
$$\frac{\alpha \pm 1}{\beta \pm 1}=\left(\frac \beta \alpha\right)^{m_0}$$
in case that $(u_n)_{n=0}^\infty$ is a Lucas sequence of first kind and
$$\frac{\alpha \pm 1}{\beta \pm 1}=- \left(\frac \beta \alpha\right)^{m_0}$$
in case that $(u_n)_{n=0}^\infty$ is a Lucas sequence of second kind.
For all pairs of $(\alpha,\beta)$ we solve these equations and find for instance, that $m_0\leq 2$ (if a solution exists at all). By computing the
values of all possible further solutions we find that indeed no equation of the form $\lambda=u_m$ has more than three solutions.
\end{proof}
\begin{remark}
Beukers \cite[Corollary on page 267]{Beukers:1980} already showed this result in case of Lucas sequences of the first kind. In fact, he proved more and
listed all the cases when there can be three solutions. To the authors knowledge the case of Lucas sequences of the second kind
has not been treated since then.
\end{remark}
Let us start by investigating the number of non-degenerate solutions to the $S$-unit equation \eqref{eq:AP}:
\begin{lemma}\label{lem:nondeg}
There are at most $A(5,2)$ three term arithmetic progressions contained in a
Lucas sequence $(u_n)_{n=0}^\infty$ of the first kind that yield non-degenerate solutions to \eqref{eq:AP}.
The same statement also holds for Lucas sequence $(v_n)_{n=0}^\infty$ of the second kind.
\end{lemma}
\begin{proof}
Consider the weighted $S$-unit equation
\begin{equation}\label{eq:S-unit2-special}
x_1+x_2-2x_3=y_1+y_2-2y_3
\end{equation}
with unknowns $x_1,x_2,x_3,y_1,y_2,y_3\in\Gamma$. This has at most
$A(5,2)$ non-degenerate, projective solutions. Thus there exists a set
$\mathcal C$, with $|\mathcal C|\leq A(5,2)$, of sextuples
$(1,c_2,c_3,c_4,c_5,c_6)$ such that for any solution we have
$x_2/x_1=c_2$, $x_3/x_1=c_3$, $y_1/x_1=c_4$, $y_2/x_1=c_5$ and
$y_3/x_1=c_6$. Assume now that a solution comes from an arithmetic
progression $u_k0$. Let $\mathfrak p_2$ be a prime ideal lying above
$(2)$ and suppose that $m>k$. We consider the equation $x_1+x_2=-2y_3$ from a
$\mathfrak p$-adic point of view. Write $v_{\mathfrak p}(\alpha)=\xi_{\mathfrak p}$ and
$v_{\mathfrak p}(\beta)=\eta_{\mathfrak p}$. Since the two smallest $\mathfrak
p$-adic valuations of the summands have to coincide, we have $v_{\mathfrak
p}(x_2)=k\xi_{\mathfrak p}=l\eta_{\mathfrak p}=v_{\mathfrak p}(2y_3)$.
Considering $\mathfrak p_2$-adic valuations we obtain $k\xi_{\mathfrak
p_2}=l\eta_{\mathfrak p_2}+\delta$, where $\delta=1,2$ depending on whether
$(2)$ is ramified or not. We get the following system of linear equations
\begin{align*}
k\xi_{\mathfrak p_2}-l\eta_{\mathfrak p_2}&=\delta\\
k\xi_{\mathfrak p}-l\eta_{\mathfrak p}&=0
\end{align*}
which has either no solution or at most one solution. Note that by assumption $\xi_{\mathfrak p}>0$.
Thus in this case, equations of type III yield at most one pair $(k,l)$ that extends to a triple $(k,l,m)$
such that $u_k0$, then we take the equation $-2x_3=y_1+y_2$ instead and
draw the same conclusions.
In view of the paragraph above, we may assume that the only prime ideals
dividing $(\alpha)$ and $(\beta)$ are lying above $(2)$. We distinguish now
whether $(2)$ splits, ramifies or is inert above $K$.
We start with the case when $(2)$ is inert, i.e., $(2)$ is a prime in $K$. Then
$(\alpha) = (2)^x$
and $(\beta) = (2)^y$ with some non-negative integers $x,y$. Since
$\alpha$ and
$\beta$ are conjugate, we get $x=y$. Hence $\alpha/\beta$ is a unit.
However,
recalling that $\alpha,\beta$ are from a quadratic imaginary field, this
yields that
$\alpha/\beta$ is a root of unity, which is a contradiction.
One may prove the case where $(2)$ ramifies by similar means as the
inert case. In this
case,we have $(2)=\mathfrak{p}^2$ with some prime ideal $\mathfrak{p}$.
Note that $\mathfrak p$ need not be principal although $\mathfrak p^2$ is principal.
Thus $(\alpha)=\mathfrak{p}^x$
and
$(\beta) = \mathfrak{p}^y$ with some non-negative integers $x,y$. Taking norm, we
get $x=y$,
and similarly as above we obtain that $\alpha/\beta$ is a root of unity,
which is impossible.
Finally, let us consider the case when $(2)$ splits, that is, we can write
$(2)=\mathfrak p_1\mathfrak p_2$. Assume that $(\alpha)=\mathfrak
p_1^{\xi}\mathfrak p_2^{\eta}$, then $(\beta)=\mathfrak p_1^{\eta}\mathfrak
p_2^{\xi}$. Considering the equation $x_1+x_2=-2y_3$ from a $\mathfrak p_1$-adic
and a $\mathfrak p_2$-adic viewpoint, respectively we get the following system
of linear equations under the assumption that $m>k$:
\begin{equation}\label{eq:valuations}
\begin{split}
v_{\mathfrak p_1}(x_2)=k\xi &= l\eta +1= v_{\mathfrak p_1}(2y_3),\\
v_{\mathfrak p_2}(x_2)=k\eta &= l\xi +1= v_{\mathfrak p_2}(2y_3).
\end{split}
\end{equation}
Note that we obtained this system due to the fact that the smallest
$\mathfrak{p}$-adic valuations must coincide. Solving the linear system
\eqref{eq:valuations} yields $k(\xi^2-\eta^2)=(\xi-\eta)$. Therefore either
$\xi=\eta$ or $k(\xi+\eta)=1$. The first case yields $\alpha=2^\xi\epsilon$ and
$\beta=2^\xi\epsilon^{-1}$ for some unit $\epsilon$ which yields that
$\alpha/\beta=\epsilon^2$ is a root of unity, a contradiction. When
$k(\xi+\eta)=1$ we have $k=1$ and $(\xi,\eta)=(0,1),(1,0)$. In any case, we
obtain from the linear system \eqref{eq:valuations} that $l=-1$, a contradiction
to our assumption that $k,l,m$ are nonnegative integers.
\end{proof}
So we are left with the problem which quadratic polynomials divide
$X^k-2X^l+X^m$. In particular, we may assume that the companion polynomial is
irreducible, otherwise $\alpha$ and $\beta$ would be rational integers which
case is covered by Theorem \ref{theorem2}. We need to find all quadratic factors
of polynomials of the type:
\begin{itemize}
\item $X^a-2X^b+1$ or
\item $X^a+X^b-2$ or
\item $2X^a-X^b-1$.
\end{itemize}
Since all zeros of the first polynomial are units, and all the zeros of the
third polynomial are either non-integral algebraic numbers or units, it is enough to
study polynomials of the form $X^a+X^b-2$ only.
We state the following result due to Pint\'{e}r and Ziegler \cite[Lemma
3]{pinterziegler}.
\begin{lemma}\label{lem:Pinter}
Let $a>b>0\in\mathbb{Z}$ and let $f(X)=X^a+X^b-2$ be a
polynomial. Then $f(X)=h(X)g(X)$ factors into the
monic polynomials $h(X)$ and $g(X)$ over $\mathbb{Z}$, where the only zeros of
$h(X)$ are roots of unity and $g(X)$ is irreducible. Further,
$h(X)|X^{\gcd(a,b)}\pm 1$.
\end{lemma}
We are interested in finding the quadratic factors of $X^{a}+X^{b}-2$. By Lemma
\ref{lem:Pinter} we only have to consider the cases $(a,b)=(3,2),(3,1),(2,1)$ or
$(4,2)$. Thus the companion polynomial is either $X^2+2X+2$ or $X^2+X+2$ or
$X^2+2$.
Since $X^2+X+2$ is the only polynomial with negative discriminant which is also a companion polynomial of a
non-degenerate binary recurrence, we obtain that either $(A,B)=(-1,-2)$ or there
are at most $A(5,2)$ three term arithmetic progressions coming from
non-degenerate solutions to \eqref{eq:AP} (cf. Lemma \ref{lem:nondeg}),
$3A(3,2)+30$ three term arithmetic progressions coming form two term vanishing
subsums of \eqref{eq:AP} (cf. Lemma \ref{lem:two-vanish}) and $18A(2,2)+9$
three term arithmetic progressions coming form three term vanishing subsums of
\eqref{eq:AP} (cf. Lemma \ref{lem:three-vanish}). We summarize these results.
\begin{proposition}
\label{prop:exact}
Let $u=(u_n)_{n=0}^\infty$ and $v=(v_n)_{n=0}^\infty$ be Lucas sequences of
the first and second kind corresponding to the pair $(A,B)$ with $A^2+4B<0$. Then
$u$ and $v$ admit at most
\[
C=A(5,2)+3A(3,2)+18A(2,2)+39
\]
three term arithmetic progressions unless $u$ or $v$ correspond to
$(A,B)=(-1,-2)$ respectively. In case of $(A,B)=(-1,-2)$, the recurrences $u$
and $v$ admit infinitely many three term arithmetic progressions.
\end{proposition}
\begin{remark}
Since $X^2+X+2|X^3+X-2$, we get that $u_k**