# MREAK : Morphological Retina Keypoint Descriptor

Himanshu Vaghela  Department of Computer Engineering
D. J. Sanghvi College of Engineering
Mumbai, India
<EMAIL_ADDRESS>Manan Oza  Department of Computer Engineering
D. J. Sanghvi College of Engineering
Mumbai, India
<EMAIL_ADDRESS>Prof. Sudhir Bagul  Department of Computer
Engineering
D. J. Sanghvi College of Engineering
Mumbai, India
<EMAIL_ADDRESS>
###### Abstract

A variety of computer vision applications depend on the efficiency of image
matching algorithms used. Various descriptors are designed to detect and match
features in images. Deployment of this algorithms in mobile applications
creates a need for low computation time. Binary descriptors requires less
computation time than float-point based descriptors because of the intensity
comparison between pairs of sample points and comparing after creating a
binary string. In order to decrease time complexity, quality of keypoints
matched is often compromised. We propose a keypoint descriptor named
Morphological Retina Keypoint Descriptor (MREAK) inspired by the function of
human pupil which dilates and constricts responding to the amount of light. By
using morphological operators of opening and closing and modifying the retinal
sampling pattern accordingly, an increase in the number of accurately matched
keypoints is observed. Our results show that matched keypoints are more
efficient than FREAK descriptor and requires low computation time than various
descriptors like SIFT, BRISK and SURF.

###### Index Terms:

feature descriptor, human pupil, morphological operations, keypoint
descriptor, image matching

##  I Introduction

Feature detection is used eminently in image mosaicing, object recognition,
image classification and many other computer vision applications for improving
the precision of results. It has always been a challenge to identify feature
points more efficiently. A sufficient increase in number of efficient
keypoints leads to a better feature matching which in turn might improve
results in various applications.

Many descriptors have been developed in the last few years. Lowe’s SIFT [1]
and SURF [2] proposed by Bay $et\;al.$ are significant examples of the family
of Histograms of Oriented Gradients (HOG) based descriptors. SIFT [1] is
rotation and scale invariant, but it is mathematically complicated and
computationally heavy due to calculation of gradients of each pixel in the
patch which makes it less effective for low powered devices. SURF [2] is an
improvement on SIFT [1] as it uses a box filter approximation which makes it
faster in computation comparatively. These descriptors are conventional
methods which uses histograms for orientation and hence are irrational for
mobile devices due to high computation time.

(a) Original

(b) Opening

(c) Closing

Figure 1: Morphological operations on an image [10]

In recent times, necessity of applications with low computation time is
observed due to massive development in the field of mobile technology. To
improve performance, binary descriptors were introduced. By comparison of
intensity in images, most of the information of a patch is encoded as a binary
string. The hamming distance is used as a distance measure between two binary
strings which equals the sum of the XOR operation between the two binary
strings which reduces computational costs and memory requirements. The Binary
Robust Independent Elementary Feature (BRIEF) [3], the Oriented Fast and
Rotated BRIEF (ORB) [4], the Binary Robust Invariant Scalable Keypoints
(BRISK) [5] and the Fast retina keypoints (FREAK) [6] are good examples. In
the next section, we will briefly present these descriptors. In order to
decrease computation time in mobile applications, the accuracy of the
keypoints detected is ignored. In fact, keypoint detection and matching is an
important concept which plays a significant role in various applications.

In this paper, we propose an alternative binary descriptor named MREAK
(Morphological Retina Keypoint Descriptor) which is based on the FREAK
descriptor and inspired by the pupillary response that varies the size of the
pupil in human eye, by adjusting image pixel intensity to increase the number
of accurate keypoints and mimic the pupil of human eye. Morphological
operations [8] are used to mimic the function of human pupil which varies the
intensity of images in specific areas of an image. Results show that our
proposed method detects new feature points more accurately and feature
matching is improved due to slight changes in sampling pattern according to
required conditions.

##  II Related work

Several computer vision tasks require matching keypoints across several frames
or views. The keypoints need to be detected first. Harris and Stephen in [7]
proposed the Harris corner detector. This detector considers differential of
the corner score into account with reference to direction directly, and has
been proved to be accurate in distinguishing between edges and corners.

After keypoint detection, the descriptor is constructed. Float-point based
descriptor and binary descriptor are two general types of descriptor. Lowe
SIFT [1] is a state-of-the-art descriptor which belongs to float-point based
category and generates robust features which are scale and rotation invariant.
A grid is taken around the keypoint and histogram is generated. Finally, a
128-dimensional vector of gradients is taken into consideration. This simple
descriptor provides distinctive features, but requires high computational time
due to histogram generation. Another descriptor faster than SIFT [1] is The
Speeded up Robust Feature (SURF) by Bay $et\;al.$ [2]. SURF uses BLOB detector
based on Hessian matrix to detect keypoints. Gaussian weights are applied in
all directions for orientation similar as SIFT.

Float-point based descriptor with more accuracy requires heavy computation
time. Due to increasing demand of mobile applications, a demand of low
computation time is noted. Binary descriptors use haming distance and XOR
operation for matching keypoints and therefore requires less computation time
as compared to float-point descriptors. A sampling pattern is formed around
the keypoint and a binary string is computed by comparing intensity values of
sample points. BRIEF [3] is a binary descriptor in which there is no specific
sampling pattern or any method for orientation calculation. The sampling pairs
for forming binary strings are randomly selected. Therefore, BRIEF is less
accurate for minute changes in the size or alignment of an image.

ORB [4] is another example of binary descriptor which has a random sampling
pattern but uses a specific method for orientation. Thus, rotation invariance
is obtained by calculating moments of the window around keypoint and
considering the angle of resultant moment. Furthermore, trained sampling pairs
are used which makes it more robust method than BRIEF. BRISK [5] has a fixed
sampling pattern of concentric circles with increasing points away from the
centre. Pairs of points are divided in two parts. Long pairs are used for
orientation calculation while short pairs are used for forming sampling
pattern which makes it better than BRISK and ORB in terms of certain
photometric changes.

FREAK [6] is a binary descriptor whose sampling pattern is inspired by the
distribution of ganglion cells in human retina. The density of points
increases moving towards the centre which mimics the human retina. Predefined
pairs determine its orientation while sampling points uses coarse-to-fine
approach which selects pairs from outer rings followed by pairs from inner
rings. In many aspects, FREAK performs better than other binary descriptors.

The binary descriptors are computed on keypoints obtained. While in our
approach, more accurate keypoints are detected using morphological operations
and sampling pattern of FREAK is modified and implemented on keypoints
accordingly to get better matches.

##  III Human pupil

Figure 2: Human pupil [11]

###  III-A Function of pupil

The function of human pupil is to regulate the amount of light entering human
eye. Its shape changes according to the surrounding environment. In darkness,
the pupil dilates while it constricts in brightness. This phenomenon decides
the amount of light falling on retina as seen in fig. 2 which carries signals
to the brain through the optic nerve. By controlling the amount of light
entering the eye, improvement in its vision is experienced as the main motive
is to view objects clearly in extreme environments.

In computer vision, efforts have been made to mimic the human eye to improve
the precision of existing algorithms. In FREAK [6], the sampling pattern was
inspired from the distribution of ganglion cells over the retina of human eye,
which improved the quality of feature points in an image. Our approach is
motivated by this function of pupil of varying the intensity of light to
increase the number of accurate keypoints detected in an image.

###  III-B Opening and closing

Image restoration is used to improve numerous imperfections occurring
frequently in an image. Morphological image processing is used to extract
image components such as boundaries, skeletons, convex hull, etc. This
operation can be used in images which are unclear due to the extreme intensity
of a group of pixels in a specific part of the image. Dilation and erosion [8]
are operations which are used to expand and diminish brighter areas of an
image respectively. While opening and closing [8] are modifications over the
previous ones. An opening operation is erosion of an image followed by
dilation while closing operation is dilation of an image followed by erosion.

In our approach, opening and closing operations are performed on an image
before detecting the keypoints. This morphological operations are used in
binary images [9]. They can be used in grayscale images [8] which processes a
single-channel image. In order to use these operations in coloured image, they
are performed in each of the RGB channels. The structuring element or kernel
as mentioned in [8] is used to determine the extent of impact of these
operations. A $3\times 3$ rectangular structuring element is used in our
method. A simple example of opening and closing is shown in Fig. 1.

$Kernel=\left[{\begin{array}[]{ccc}1&1&1\\\ 1&1&1\\\ 1&1&1\\\
\end{array}}\right]$

##  IV The MREAK Descriptor

(a)

(b)

(c)

Figure 3: Sampling pattern of (a) FREAK [6] and proposed (b) Opening and (c)
Closing

###  IV-A Sampling pattern

Sampling pattern around the keypoint plays an important role in matching the
keypoints. BRIEF [3] does not have a specific sampling pattern while ORB [4]
has a random one. BRISK [5] was the first descriptor to use a specific pattern
to sample its points. FREAK [6] has a sampling pattern which uses gaussian
smoothing over the area around the points and is inspired by the design of
human retina.

Our sampling pattern is modification over FREAK by taking morphological
operations [8] like opening and closing into consideration. Fig. 3(a) shows
the sampling pattern of FREAK while Fig. 3(b) and Fig. 3(c) shows sampling
pattern of opening and closing respectively proposed by our method. Radius of
concentric circles and size of receptive fields are smaller than that of FREAK
as we move towards the centre in opening pattern and they are bigger in case
of closing pattern. After keypoints are detected in an image, sampling pattern
is applied according to the morphological operation used.

In opening of an image, bright objects are diminished. So, the opening
sampling pattern helps us to identify relevant information around the keypoint
which is more concentrated towards the centre. While closing of an image
expands the bright objects in an image. Therefore, closing sampling pattern
highlights relevant information which is concentrated slightly away from the
centre.

This change in sampling pattern improves keypoint detection and constructs a
descriptor which enhances the quality of features around the keypoint. Due to
increase in number of detected keypoints, image matching efficiency improves.

###  IV-B Orientation

The focus of our approach is to increase the number of keypoints which leads
to better matching. So, for orientation we use same 45 pairs of points as that
of FREAK [6]. This pairs requires less computational memory and time.
Orientation method is same as that of FREAK.

$O=\frac{1}{M}\sum_{P_{0}\in
G}(I(P_{0}^{r1})-I(P_{0}^{r2}))\frac{P_{0}^{r1}-P_{0}^{r2}}{||P_{0}^{r1}-P_{0}^{r2}||}$
(1)

Here, $M$ is the total number of pairs used where $G$ is local gradient and
$P_{0}^{i}$ is the 2D vector of the coordinates of the sample points.

Orientation of points is calculated separately for opened and closed images
followed by image matching. By doing this, a separate set of matched keypoints
are obtained for opened and closed images. The characteristics of orientation
are same as that of FREAK [6].

###  IV-C The Descriptor

We compare the intensity values between pairs of receptive fields of sample
points with their corresponding Gaussian kernel. A binary string $B$ for $N$
pairs is computed by considering one bit difference of intensities of
receptive fields denoted by $T(P_{a})$.

$B=\sum_{0\leq a<N}2^{a}T(P_{a})$ (2)

$P_{a}$ represents a pair of receptive fields whereas $I(P_{a}^{r1})$ and
$I(P_{a}^{r2})$ denotes intensities of two fields in one pair.

$T(P_{a})=\begin{cases}1\quad if(I(P_{a}^{r1})>I(P_{a}^{r2})),\\\ 0\quad
otherwise,\end{cases}$ (3)

In order to select pairs from many possible combinations, we use the same
algorithm used in FREAK. Following are the steps :

  1. 1.

A descriptor is constructed for each keypoint and it is arranged in form of a
matrix with rows representing key points and possible pairs represented by
columns. The mean of all columns is calculated.

  2. 2.

For a unique feature, high variance would be preferable and it is obtained by
mean of 0.5.

  3. 3.

The columns are arranged accordingly and best column is selected and rest
columns are considered according to their correlation with the selected
columns which is less.

Our methodology is same as FREAK [6] while only the sampling pattern being
different.

###  IV-D Algorithm

Figure 4: Flowchart

Our method performs following steps as mentioned in Fig. 4.

  1. 1.

Take images as input and implement morphological operations of opening and
closing separately with kernel size $3\times 3$.

  2. 2.

Detect the keypoints in this images.

  3. 3.

Apply the opening and closing sampling pattern around this keypoints.

  4. 4.

Match the keypoints obtained resulting in two different sets of matched
keypoints.

  5. 5.

Combine this keypoints in the original images as shown in results to get the
best set of matched keypoints.

By combining the two sets of keypoints, we get more number of keypoints in the
original set of images which in turn leads to better matching in many
applications of computer vision.

##  V Observed results

The required results are obtained by implementing it in python 3.5 in a
Desktop PC with an intel i3 1.9 GHz processor and 8 GB of RAM. Opening and
closing algorithms are implemented followed by description and matching using
our approach by modifying $xfeatures2d$ in OpenCV 3.3.1 using python 3.5. Then
FREAK algorithm is performed to compare results with our approach by
considering three pairs of images as examples for evaluating results. Our
approach is available on $https://github.com/himanshuvaghela/opencvcontrib$.

Table. I shows computation time of each of the algorithms. Computation time to
detect and match a keypoint in our approach is almost similar to that of
FREAK. The characteristics of FREAK are inherited by our approach due to
similar methodology but different sampling pattern.

Consider an example of two photos of Big Ben tower in London [12] and [13].
Fig. 5(a) shows 13 best matches of FREAK [6]. This best matches are determined
by ratio of distances of closest neighbour to second closest as mentioned in
Lowe’s SIFT [1]. In our case, ratio is greater than 7.5 which eliminates more
than 80 $\%$ of false matches. Fig. 5(b) shows 1498 total keypoint matches of
FREAK. Fig. 5(c) represents opening of two images and building descriptor
using opening sampling pattern where 6 best keypoints are detected. Fig. 5(d)
represents closing of two images and matching using closing sampling pattern
where 14 best keypoints matches are detected. In Fig. 5(e), both of the
opening and closing keypoints are combined and represented in original images
forming a total of 20 best keypoints. By comparing Fig. 5(a) and Fig. 5(e), we
can infer that extra keypoints are detected and better matching is done. There
are few best matched keypoints in Fig. 5(e) which are not there in total FREAK
keypoints in Fig. 5(b)

In second example, two images of Eiffel tower are considered [14] and [15].
Fig. 6(a) shows 21 best FREAK keypoint matches while Fig. 6(e) shows 31 total
best keypoints using our approach. In third example, two images of Colosseum
[16] and [17] are considered. Fig. 7(a) shows 8 best FREAK keypoint matches
while Fig. 7(e) shows 16 total best keypoints using our approach.

It is observed that performing morphological operations like opening and
closing on images increases the number of keypoints and a slight change in
sampling pattern over FREAK improves the quality of keypoint matching
providing a breakthrough in many computer vision applications. So, efficiency
of results increases as we mimic the structure of human eye. This was proved
earlier by FREAK and then by our approach where function of human pupil
implemented through morphological operations eventually improved overall
results.

TABLE I: Computation time for 3 pair of images where approximately 2000 keypoints are detected per image. Time per keypoint | SIFT | SURF | BRISK | FREAK | OUR
---|---|---|---|---|---
(ms) |  |  |  |  | METHOD
Description time | 0.0734 | 0.0631 | 0.0315 | 0.0280 | 0.0286
Matching time | 0.3716 | 0.3701 | 0.3788 | 0.1449 | 0.1164

(a) 13 best FREAK keypoint matches.

(b) 1498 total FREAK keypoints.

(c) 6 best keypoints by implementing opening sampling pattern in opened image.

(d) 14 best keypoints by implementing closing sampling pattern in closed
image.

(e) Combining total 20 best keypoints on original images.

Figure 5: Implementation on two images of Big Ben tower [12] and [13]

(a) 21 best FREAK keypoint matches.

(b) 3897 total FREAK keypoints.

(c) 11 best keypoints by implementing opening sampling pattern in opened
image.

(d) 20 best keypoints by implementing closing sampling pattern in closed
image.

(e) Combining total 31 best keypoints on original images.

Figure 6: Implementation on two images of Eiffel tower [14] and [15]

(a) 8 best FREAK keypoint matches.

(b) 2027 total FREAK keypoints.

(c) 6 best keypoints by implementing opening sampling pattern in opened image.

(d) 10 best keypoints by implementing closing sampling pattern in closed
image.

(e) Combining total 16 best keypoints on original images.

Figure 7: Implementation on two images of Colosseum [16] and [17]

##  VI Conclusion

In this paper, a binary descriptor inspired by FREAK sampling pattern and
function of human pupil is presented. The field of computer vision can be
further explored by mimicking human eye. The FREAK sampling pattern was
inspired by distribution of ganglion cells in human retina. Our approach is
inspired by the pupillary response of human eye. New keypoints were detected
using this property by implementing selected morphological operations and
accordingly improving the sampling pattern resulting in efficient matching of
keypoints. Moreover, this concept of using morphological operations for
improving the quality of images can be modified and used in many methods to
improve the accuracy of keypoint matching and try to reduce computation time
even further.

## References

  * [1] D. G. Lowe, ”Distinctive image features from scale invariant keypoints,” Int’l Journal of Computer Vision, vol. 60, issue 2, pp. 91-110, 2004.
  * [2] H. Bay, T. Tuytelaars, and L. Van Gool, “Surf: Speeded up robust features,” European Conf. Computer Vision, pages 404–417. Springer, 2006.
  * [3] M. Calonder, V. Lepetit, C. Strecha, and P. Fua., “Brief: Binary robust independent elementary features,” In European Conf. Comput. Vision, pp. 778–792, 2010.
  * [4] E. Rublee, V. Rabaud, K. Konolige, and G. Bradski., “Orb:an efficient alternative to sift or surf,” Int’l Conf Comput. Vision, pp. 2564–2571, 2011.
  * [5] S. Leutenegger, M. Chli, and R. Y. Siegwart., “Brisk:Binary robust invariant scalable keypoints,” Int’l Conf Com-put. Vision, pp. 2548–2555, 2011.
  * [6] A. Alahi, R. Ortiz, and P. Vandergheynst., “Freak: Fast retina keypoint,” Computer Vision and Pattern Recognition, pp.510–517, 2012.
  * [7] C. Harris and M. Stephens. A combined corner and edge detector. In Alvey vision conference, volume 15, page 50. Manchester, UK, 1988.
  * [8] J. Gil and R. Kimmel, “Efficient dilation, erosion, opening, and closing algorithms”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, no. 12, pp. 1606.1617, December 2002.
  * [9] Raid, A.M and Khedr, W.M and El-dosuky, Mohammed and Aoud, Mona. (2014). Image Restoration Based on Morphological Operations. International Journal of Computer Science, Engineering and Information Technology. 4. 9-21. 10.5121/ijcseit.2014.4302.
  * [10] flickr. [Online]. Available: $https://www.flickr.com/photos$
$/bibliodyssey/4981720918/$

  * [11] New York State Optometric Association. [Online]. Available: $https://$
$www.nysoa.org/uploads/images/$

  * [12] VISIT LONDON. [Online]. Available: $https://cdn.londonandpart$
$ners.com/visit/london-organisations/big-ben/$

  * [13] KampenOnline. [Online]. Available: $https://kampen.online/wp-content/uploads/$
  * [14] Behance. [Online]. Available: $https://mir-s3-cdn-cf.behance$
$.net/project_{m}odules/max_{1}200/$

  * [15] Non Stop Destination. [Online]. Available: $https://nonstop$
$destination.com/wp-content/uploads/2014/11/$

  * [16] Funky Stock. [Online]. Available: $https://funkystock.photos$
$helter.com/img/$

  * [17] Pinterest. [Online]. Available: $https://i.pinimg.com/originals/$
$da/13/7e/$


# On the exponential Diophantine equation …

Mahadi Ddamulira and Florian Luca  Mahadi Ddamulira
Institute of Analysis and Number Theory, Graz University of Technology,
Kopernikusgasse 24/II,
A-8010 Graz, Austria  Max Planck Institute for Mathematics
Bonn, Germany<EMAIL_ADDRESS><EMAIL_ADDRESS>Florian Luca
School of Mathematics, University of the Witwatersrand,
Johannesburg, South Africa  Research Group in Algebraic Structures and
Applications, King Abdulaziz University,
Jeddah, Saudi Arabia  Max Planck Institute for Mathematics
Bonn, Germany  Centro de Ciencias Matemáticas UNAM
Morelia, Mexico<EMAIL_ADDRESS>
# On the exponential Diophantine equation related to powers of two consecutive
terms of Lucas sequences

Mahadi Ddamulira and Florian Luca  Mahadi Ddamulira
Institute of Analysis and Number Theory, Graz University of Technology,
Kopernikusgasse 24/II,
A-8010 Graz, Austria  Max Planck Institute for Mathematics
Bonn, Germany<EMAIL_ADDRESS><EMAIL_ADDRESS>Florian Luca
School of Mathematics, University of the Witwatersrand,
Johannesburg, South Africa  Research Group in Algebraic Structures and
Applications, King Abdulaziz University,
Jeddah, Saudi Arabia  Max Planck Institute for Mathematics
Bonn, Germany  Centro de Ciencias Matemáticas UNAM
Morelia, Mexico<EMAIL_ADDRESS>
###### Abstract.

Let $r\geq 1$ be an integer and ${\bf U}:=(U_{n})_{n\geq 0}$ be the Lucas
sequence given by $U_{0}=0$, $U_{1}=1,$ and $U_{n+2}=rU_{n+1}+U_{n}$, for all
$n\geq 0$. In this paper, we show that there are no positive integers $r\geq
3,~{}x\neq 2,~{}n\geq 1$ such that $U_{n}^{x}+U_{n+1}^{x}$ is a member of
${\bf U}$.

###### Key words and phrases:

Lucas sequences, Linear forms in logarithms, Baker’s method

###### 2010 Mathematics Subject Classification:

11B39, 11D45, 11J86

##  1\. Introduction

Let $r\geq 1$ be an integer and ${\bf U}:=(U_{n})_{n\geq 0}$ be the Lucas
sequence given by $U_{0}=0,~{}U_{1}=1,$ and

$\displaystyle U_{n+2}=rU_{n+1}+U_{n}$ (1)

for all $n\geq 0$. When $r=1$ ${\bf U}$ coincides with the Fibonacci sequence
while when $r=2$ ${\bf U}$ coincides with the Pell sequence. It is well-known
that

$\displaystyle U_{n}^{2}+U_{n+1}^{2}=U_{2n+1}\quad\text{for all}\quad n\geq
0.$ (2)

In particular, the identity (2) tells us that the sum of the squares of two
consecutive terms of ${\bf U}$ is also a term of ${\bf U}$. When $r=1$, we
even have $U_{n}+U_{n+1}=U_{n+2}$ for all $n\geq 0$ since ${\bf U}$ is the
Fibonacci sequence. We thus consider the Diophantine equation

$\displaystyle U_{n}^{x}+U_{n+1}^{x}=U_{m}$ (3)

in nonnegative integers $(n,m,x)$ which by Eq. (2) has the parametric solution
$m=2n+1$ when $x=2$ for any $r\geq 1$ and even the parametric solution $m=n+2$
when $x=1$ if $r=1$. For $r=1$ Luca and Oyono [8] proved that Eq. (3) has no
positive integer solutions $(n,m,x)$ with $n\geq 2$ and $x\geq 3$. Rihane et
al. [11] studied Eq. (3) when $r=2$ and proved that there is no positive
integer solution $(n,m,x)$ of it with $x\neq 2$. In the same spirit, Gómez
Ruiz and Luca [4] studied Eq. (3) with ${\bf
U}=\\{F_{n}^{(k)}\\}_{n\geq-(k-2)}$, which is the $k-$generalized Fibonacci
sequence of recurrence

$\displaystyle
F_{n}^{(k)}=F_{n-1}^{(k)}+F_{n-2}^{(k)}+\cdots+F_{n-k}^{(k)}\quad\text{for
all}\quad n\geq 2$

with the initial conditions
$F_{-(k-2)}^{(k)}=F_{-(k-2)}^{(k)}=\cdots=F_{0}^{(k)}=0$ and $F_{1}^{(k)}=1$.
When $k=2$, this sequence coincides with the sequence of Fibonacci numbers.
They proved that Eq. (3) has no positive integer solution $(k,n,m,x)$ with
$k\geq 3$, $n\geq 2$, and $x\geq 1$. Another related result involving the
balancing numbers was studied by Rihane et al. in [10].

In this paper, we study Eq. (3) in nonnegative integers $(r,n,m,x)$ treating
$r$ as an integer parameter. We may assume that $r\geq 3$ since the cases
$r\in\\{1,2\\}$ have been treated already in [8] and [11], respectively. The
solution with $(n,m)=(0,1)$ (for any $r$ and $x$) is obvious so we omit it and
suppose that $n$ is positive. Our main result is the following.

######  Theorem 1.

There is no positive integer solution $(r,n,m,x)$ of Diophantine equation (3)
with $r\geq 3$ and $x\neq 2$.

##  2\. Preliminary Results

###  2.1. The Lucas sequence

Let

$(\alpha,\beta):=\left(\dfrac{r+\sqrt{r^{2}+4}}{2},\dfrac{r-\sqrt{r^{2}+4}}{2}\right),$

be the roots of the characteristic equation $x^{2}-rx-1=0$ of the Lucas
sequence ${\bf U}=(U_{n})_{n\geq 0}$. We put
$\Delta=r^{2}+4=(\alpha-\beta)^{2}$ for the discriminant of the above
quadratic equation. The Binet formula for the general term of ${\bf U}$ is
given by

$\displaystyle U_{n}:=\dfrac{\alpha^{n}-\beta^{n}}{\alpha-\beta}\quad\text{for
all}\quad n\geq 0.$ (4)

One may prove by induction that the inequality

$\displaystyle\alpha^{n-2}\leq U_{n}\leq\alpha^{n-1}$ (5)

holds for all positive integers $n$. It is also easy to show that the
inequality

$\displaystyle\dfrac{U_{n}}{U_{n+1}}<\dfrac{1}{r}$ (6)

holds for all $n\geq 2$. Indeed, it follows from
$U_{n+1}=rU_{n}+U_{n-1}>rU_{n}$ for $n\geq 2$. At one point of the argument we
will need the companion Lucas sequence ${\bf V}:=\\{V_{n}\\}_{n\geq 0}$ given
by $V_{0}=2,~{}V_{1}=r$, and $V_{n+2}=rV_{n+1}+V_{n}$ for all $n\geq 0$. Its
Binet formula is

$V_{n}=\alpha^{n}+\beta^{n}\quad{\text{\rm for~{}all}}\quad n\geq 0.$ (7)

There are many relations between members of ${\bf U}$ and ${\bf V}$ such as

$\displaystyle U_{2n}$ $\displaystyle=$ $\displaystyle U_{n}V_{n};$ (8)
$\displaystyle U_{n+1}^{2}-U_{n}U_{n+2}$ $\displaystyle=$
$\displaystyle(-1)^{n};$ (9) $\displaystyle V_{n}^{2}-\Delta U_{n}^{2}$
$\displaystyle=$ $\displaystyle 4(-1)^{n};$ (10) $\displaystyle 2U_{m+n}$
$\displaystyle=$ $\displaystyle U_{m}V_{n}+U_{n}V_{m};$ (11)
$\displaystyle\gcd(U_{n},U_{m})$ $\displaystyle=$ $\displaystyle
U_{\gcd(m,n)}.$ (12)

We record another one. All such identities follow easily from the Binet
formulas Eq. (4) and Eq. (7) of ${\bf U}$ and ${\bf V}$ respectively.

######  Lemma 1.

If $n$ is odd then

$U_{n}-1=\left\\{\begin{matrix}U_{(n-1)/2}V_{(n+1)/2}&{\text{if}}&n\equiv
1\pmod{4};\\\ U_{(n+1)/2}V_{(n-1)/2}&{\text{if}}&n\equiv
3\pmod{4}.\end{matrix}\right.$ (13)

Both sequences ${\bf U}$ and ${\bf V}$ can be extended to negative indices
either by allowing $n$ to be negative in the Binet formulas Eq. (4) and (7) or
simply by using the recurrence relation to extend ${\bf U}$ to negative
indices via $U_{-n}=-rU_{-(n-1)}+U_{-(n-2)}$ for all $n\geq 1$. The same
applies to ${\bf V}$. All the above formulas given in Eq. (8), (9), (10),
(11), and (13) hold when the indices are arbitrary integers, not necessarily
nonnegative.

The following lemma is useful. For further details we refer the reader to the
book of Koshy [6].

######  Lemma 2.

Let $\\{U_{n}(r)\\}_{n\geq 0}\subseteq{\bf Z}[r]$ be the sequence of
polynomials defined by $U_{0}(r)=0$, $U_{1}(r)=1$, and

$\displaystyle U_{n+2}(r)=rU_{n+1}(r)+U_{n}(r),\quad\text{for all }\quad n\geq
0.$

Then,

$\displaystyle U_{n}(r)=\sum_{\begin{subarray}{c}0\leq k\leq n\\\ k\not\equiv
n\pmod{2}\end{subarray}}\binom{\frac{n+k-1}{2}}{k}r^{k}.$ (14)

Note that the summation range above is only over these $k\in[0,n]$ which have
different parity than $n$. We record the following easy but useful consequence
of the formula Eq. (14).

######  Lemma 3.

We have $r\mid U_{n}$ if $n$ is even and $r\mid U_{n}-1$ if $n$ is odd.

###  2.2. Logarithmic height

Let $\eta$ be an algebraic number of degree $d$ with minimal primitive
polynomial over the integers

$a_{0}x^{d}+a_{1}x^{d-1}+\cdots+a_{d}=a_{0}\prod_{i=1}^{d}(x-\eta^{(i)}),$

where the leading coefficient $a_{0}$ is positive and the $\eta^{(i)}$’s are
the conjugates of $\eta$. The logarithmic height of $\eta$ is given by

$h(\eta):=\dfrac{1}{d}\left(\log
a_{0}+\sum_{i=1}^{d}\log\left(\max\\{|\eta^{(i)}|,1\\}\right)\right).$

In particular, if $\eta=p/q$ is a rational number with $\gcd(p,q)=1$ and
$q>0$, then $h(\eta)=\log\max\\{|p|,q\\}$. The following are some of the
properties of the logarithmic height function $h(\cdot)$, which will be used
in the next sections of this paper without reference:

$\displaystyle h(\eta\pm\gamma)$ $\displaystyle\leq h(\eta)+h(\gamma)+\log 2,$
(15) $\displaystyle h(\eta\gamma^{\pm 1})$ $\displaystyle\leq
h(\eta)+h(\gamma),$ $\displaystyle h(\eta^{s})$
$\displaystyle=|s|h(\eta)\quad(s\in\mathbb{Z}).$

###  2.3. Linear forms in logarithms and continued fractions

The following result on linear forms in three logarithms is due to Mignotte
[9]. The result is more general (i.e., the conditions on the parameters
involved are somewhat more general), but we will only quote it in the form
that we need.

######  Theorem 2.

Consider three algebraic numbers $\gamma_{1},\gamma_{2}$, and $\gamma_{3}$,
which are all real, greater than $1$ and multiplicatively independent. Put

$\displaystyle\mathcal{D}:=[\mathbb{Q}(\gamma_{1},\gamma_{2},\gamma_{3}):\mathbb{Q}].$

Let $b_{1},b_{2},b_{3}$ be coprime positive integers and consider

$\displaystyle\Gamma:=b_{2}\log\gamma_{2}-b_{1}\log\gamma_{1}-b_{3}\log\gamma_{3}.$

Put

$\displaystyle
d_{1}:=\gcd(b_{1},b_{2})=\frac{b_{1}}{b_{1}^{{}^{\prime}}}=\frac{b_{2}}{b_{2}^{{}^{\prime}}},\quad
d_{3}:=\gcd(b_{3},b_{2})=\frac{b_{2}}{b_{2}^{{}^{\prime\prime}}}=\frac{b_{3}}{b_{3}^{{}^{\prime\prime}}}.$

Let $A_{1},A_{2}$, and $A_{3}$ be real numbers such that

$\displaystyle
A_{i}\geq\max\\{4,~{}4.296\log\gamma_{i}+2\mathcal{D}h(\gamma_{i})\\},\quad
i=1,2,3,\quad\text{and}\quad\Omega:=A_{1}A_{2}A_{3}\geq 100.$

Put

$\displaystyle
b^{{}^{\prime}}:=\left(\dfrac{b_{1}^{{}^{\prime}}}{A_{2}}+\dfrac{b_{2}^{{}^{\prime}}}{A_{1}}\right)\left(\dfrac{b_{3}^{{}^{\prime\prime}}}{A_{2}}+\dfrac{b_{2}^{{}^{\prime\prime}}}{A_{3}}\right)\quad\text{and}\quad\log\mathcal{B}:=\max\left\\{0.882+\log
b^{{}^{\prime}},\frac{10}{\mathcal{D}}\right\\}.$

Then, either

$\displaystyle\log|\Gamma|>-790.95\Omega\mathcal{D}^{2}(\log\mathcal{B})^{2},$

or one of the following conditions holds:

  * (i)

there exist two positive integers $r_{0}$ and $s_{0}$ such that

$\displaystyle r_{0}b_{2}=s_{0}b_{1}$

with

$\displaystyle r_{0}\leq
5.61A_{2}(\mathcal{D}\log\mathcal{D})^{\frac{1}{3}}\quad\text{and}\quad
s_{0}\leq 5.61A_{1}(\mathcal{D}\log\mathcal{D})^{\frac{1}{3}};$

  * (ii)

there exist integers $r_{1},s_{1},t_{1},$ and $t_{2}$, with $r_{1}s_{1}\neq
0$, such that

$\displaystyle(t_{1}b_{1}+r_{1}b_{3})s_{1}=r_{1}b_{2}t_{2},\quad\gcd(r_{1},t_{1})=\gcd(s_{1},t_{2})=1$

which also satisfy

$\displaystyle|r_{1}s_{1}|\leq 5.61\delta
A_{3}(\mathcal{D}\log\mathcal{D})^{\frac{1}{3}},\quad|s_{1}t_{1}|\leq
5.61\delta
A_{1}(\mathcal{D}\log\mathcal{D})^{\frac{1}{3}},\quad|r_{1}t_{2}|\leq
5.61\delta A_{2}(\mathcal{D}\log\mathcal{D})^{\frac{1}{3}},$

where

$\displaystyle\delta:=\gcd(r_{1},s_{1}).$

Moreover, when $t_{1}=0$ we can take $r_{1}=1$, and when $t_{2}=0$ we can take
$s_{1}=1$.

At some point we will need to treat linear forms in two logarithms of
algebraic numbers. To set the stage, let $\gamma_{1}$ and $\gamma_{2}$ be real
algebraic numbers which are positive and let
${\mathcal{D}}:=[{\mathbb{Q}}(\gamma_{1},\gamma_{2}):{\mathbb{Q}}]$. Let
$b_{1}$, $b_{2}$ be nonzero integers, let $B_{1}$ and $B_{2}$ be real numbers
larger than $1$ such that

$\displaystyle\log
B_{i}\geq\max\left\\{h(\gamma_{i}),\dfrac{|\log\gamma_{i}|}{\mathcal{D}},\dfrac{1}{\mathcal{D}}\right\\},\qquad{\text{\rm
for}}\quad i=1,2,$

and put

$\displaystyle b^{\prime}=\dfrac{|b_{1}|}{{\mathcal{D}}\log
B_{2}}+\dfrac{|b_{2}|}{{\mathcal{D}}\log B_{1}}.$

Let

$\Gamma:=b_{1}\log\gamma_{1}+b_{2}\log\gamma_{2}.$ (16)

The following result of Laurent et al. is Corollary 2 in [7].

######  Theorem 3.

With the above notations assuming furthermore that $\gamma_{1}$ and
$\gamma_{2}$ are multiplicatively independent we have

$\displaystyle\log|\Gamma|>-24.34{\mathcal{D}}^{4}\left(\max\left\\{\log
b^{\prime}+0.14,\dfrac{21}{\mathcal{D}},\dfrac{1}{2}\right\\}\right)^{2}\log
B_{1}\log B_{2}.$ (17)

Note that the fact that $\Gamma\neq 0$ is already guaranteed by the condition
that $\gamma_{1}$ and $\gamma_{2}$ are multiplicatively independent together
with the fact that $b_{1},~{}b_{2}$ are nonzero integers.

During the calculations we get upper bounds on our variables which are too
large, thus we need to reduce them. To do so we use some results from the
theory of continued fractions.

For the treatment of linear forms homogeneous in two integer variables we use
a well-known classical result in the theory of Diophantine approximation due
to Legendre.

######  Lemma 4.

Let $\tau$ be an irrational number,
${p_{0}}/{q_{0}},{p_{1}}/{q_{1}},{p_{2}}/{q_{2}},\ldots$ be the sequence of
convergents of the continued fraction expansion of $\tau$ and $M$ be a
positive integer. Let $N$ be a nonnegative integer such that $q_{N}>M$.
Putting $a(M):=\max\\{a_{i}:i=0,1,2,\ldots,N\\}$ the inequality

$\displaystyle\left|\tau-\dfrac{u}{v}\right|>\dfrac{1}{(a(M)+2)v^{2}},$

holds for all pairs $(u,v)$ of positive integers with $0<v<M$. Furthermore, if

$\left|\tau-\frac{u}{v}\right|<\frac{1}{2v^{2}},$

then $u/v=p_{k}/q_{k}$ for some $k\geq 0$.

For a nonhomogeneous linear form in two integer variables we use a slight
variation of a result due to Dujella and Pethő (see [5], Lemma 5a). For a real
number $X$, we write $\|X\|:=\min\\{|X-n|:n\in\mathbb{Z}\\}$ for the distance
from $X$ to the nearest integer.

######  Lemma 5.

Let $M$ be a positive integer, ${p}/{q}$ be a convergent of the continued
fraction expansion of the irrational number $\tau$ such that $q>6M$, and
$A,B,\mu$ be some real numbers with $A>0$ and $B>1$. Furthermore, let
$\varepsilon:=\|\mu q\|-M\|\tau q\|$. If $\varepsilon>0$, then there is no
solution to the inequality

$0<|u\tau-v+\mu|<AB^{-w}$

in positive integers $u,v$, and $w$ with

$u\leq M\quad{\text{and}}\quad w\geq\dfrac{\log(Aq/\varepsilon)}{\log B}.$

##  3\. Proof of Theorem 1

###  3.1. The cases $n=1$ or $x=1$

We assume that $n\geq 1$, as the solution with $n=0$ is trivial. Since
$U_{n+1}<U_{n+1}+U_{n}<U_{n+2}$, it follows that the Diophantine equation Eq.
(3) has no solution with $x=1$. Let us assume that $n=1$. We then get that

$\displaystyle U_{m}=1+r^{x}.$ (18)

In particular, $U_{m}\equiv 1\pmod{r}$. Lemma 3 shows that $m\equiv 1\pmod{2}$
and now Lemma 1 shows that

$r^{x}=U_{m}-1=U_{(m-\delta)/2}V_{(m+\delta)/2}\quad\text{where}\quad\delta\in\\{\pm
1\\},\quad\delta\equiv m\pmod{4}.$

We now recall the Primitive Divisor Theorem of Carmichael [3] (see [1] for the
most general statement) for the sequence ${\bf U}$. It states that if
$\ell>12$, there is a prime factor $p$ of $U_{\ell}$ which is primitive in the
sense that $p\nmid U_{k}$ for any positive $k<\ell$. So, assume $m+\delta\geq
14$. Since $m+\delta$ is even we have
$U_{m+\delta}=U_{(m+\delta)/2}V_{(m+\delta)/2}$ by the formula Eq. (8). Since
$U_{m+\delta}$ has a primitive prime factor $p$, the primitive prime $p$ must
be a divisor of $V_{(m+\delta)/2}$, which in turn must divide $r=U_{2}$, a
contradiction. Thus, $m+\delta\leq 12$, therefore $m\leq 13$. It thus follows
that

$r^{x}=U_{m}-1<\alpha^{m-1}\leq\alpha^{12}<(r^{2}+4)^{6},$

so, if $x\geq 13$, then

$3^{x-12}\leq r^{x-12}<(1+4/r^{2})^{6}\leq(1+4/3^{2})^{6}<9.1,$

which gives $x\leq 14$. Thus, $m\leq 13,~{}x\leq 14$. For each choice of the
pair $(m,x)$ with the components in the above ranges, the equation
$U_{m}(r)-1-r^{x}=0$ is a polynomial equation in $r$. After a simple computer
search, we found no other solutions to equation Eq. (18) apart from the
solution $(n,m,x)=(1,3,2)$ which has $x=2$ so it is part of the parametric
family of solutions indicated at Eq. (2).

So, from now on we assume that $n\geq 2$ and $x\geq 3$.

###  3.2. Calculations when $n\in[2,100]$ and $x\in[3,100]$

Using the equation Eq. (3) and the inequality Eq. (5), we get

$\displaystyle\alpha^{(n-1)x}<U_{n+1}^{x}<U_{n}^{x}+U_{n+1}^{x}=U_{m}\leq\alpha^{m-1},$

and

$\displaystyle\alpha^{m-2}<U_{m}=U_{n}^{x}+U_{n+1}^{x}<(U_{n}+U_{n+1})^{x}<U_{n+2}^{x}<\alpha^{(n+1)x}.$

From the above inequalities, we get the following result which we record for
future reference.

######  Lemma 6.

The inequalities

$\displaystyle(n-1)x+1<m<(n+1)x+2$ (19)

hold for all $x\geq 3$ and $n\geq 2$.

We next consider Eq. (14) given in Lemma 2. We write Eq. (3) as

$\displaystyle\left(\sum_{\begin{subarray}{c}0\leq k\leq n\\\ k\not\equiv
n(\text{mod}~{}2)\end{subarray}}\binom{\frac{n+k-1}{2}}{k}r^{k}\right)^{x}+\left(\sum_{\begin{subarray}{c}0\leq
k\leq n+1\\\ k\not\equiv
n+1(\text{mod}~{}2)\end{subarray}}\binom{\frac{n+k}{2}}{k}r^{k}\right)^{x}=\sum_{\begin{subarray}{c}0\leq
k\leq m\\\ k\not\equiv
m(\text{mod}~{}2)\end{subarray}}\binom{\frac{m+k-1}{2}}{k}r^{k}.$ (20)

Assume first that $n$ is even. Then Eq. (20) becomes

$\displaystyle\left(\frac{n}{2}r+\binom{\frac{n+2}{2}}{3}r^{3}+\cdots\right)^{x}+\left(1+\binom{\frac{n+2}{2}}{2}r^{2}+\binom{\frac{n+4}{2}}{4}r^{4}+\cdots\right)^{x}=1+\binom{\frac{m+1}{2}}{2}r^{2}+\binom{\frac{m+3}{2}}{3}r^{4}+\cdots,$

which is equivalent to

$\displaystyle\binom{\frac{n+2}{2}}{2}r^{2}x+\binom{\frac{n+4}{2}}{4}r^{4}x+\cdots\equiv\binom{\frac{m+1}{2}}{2}r^{2}+\binom{\frac{m+3}{2}}{3}r^{4}+\cdots(\text{mod}~{}r^{x}).$
(21)

The above relation implies that

$\displaystyle
r^{\min\\{x,4\\}-2}\Big{|}\binom{\frac{m+1}{2}}{2}-x\binom{\frac{n+2}{2}}{2}.$
(22)

Similarly, when $n$ is odd, one is led to the analogous divisibility relation

$\displaystyle
r^{\min\\{x,4\\}-2}\Big{|}\binom{\frac{m+1}{2}}{2}-x\binom{\frac{n+1}{2}}{2}.$
(23)

So, fixing $n\in[2,100]$ and $x\in[3,100]$, inequalities Eq. (19) give some
range for $m$. For each $(n,x,m)$, divisibility relations Eq. (22) and Eq.
(23) (according to whether $n$ is even or odd) give us some possibilities for
$r\geq 3$ and now one checks whether relation Eq. (3) holds for this candidate
$(n,x,m,r)$. A computer search with Mathematica in this range for $n$ and $x$
which ran for a few hours found no solutions. For the search we didn’t
actually checked that formula Eq. (20) holds but we checked that Eq. (20) does
not hold modulo $T$, where $T$ is the product of the first $20$ primes. The
Mathematica function powermod allowed us to compute the powers of $r$ modulo
$T$ arising from the binomial formula rather quickly.

From now on, we assume that $n\geq 2,~{}x\geq 3$ and $\max\\{n,x\\}>100$.

###  3.3. A small linear form in three logs

We rewrite equation Eq. (3) as

$\displaystyle\dfrac{\alpha^{m}}{\alpha-\beta}-U_{n+1}^{x}=U_{n}^{x}+\dfrac{\beta^{m}}{\alpha-\beta}.$
(24)

Dividing both sides of the above equation by $U_{n+1}^{x}$ and using the
inequality Eq. (6), we obtain

$\displaystyle\left|\alpha^{m}(\alpha-\beta)^{-1}U_{n+1}^{-x}-1\right|=\left(\dfrac{U_{n}}{U_{n+1}}\right)^{x}+\dfrac{\beta^{m}}{(\alpha-\beta)U_{n+1}^{x}}<2\left(\dfrac{U_{n}}{U_{n+1}}\right)^{x}<\dfrac{2}{r^{x}}.$
(25)

Put

$\displaystyle\Lambda:=\alpha^{m}(\alpha-\beta)^{-1}U_{n+1}^{-x}-1\quad\text{and}\quad\Gamma:=m\log\alpha-\log(\alpha-\beta)-x\log
U_{n+1}.$ (26)

We observe that $\Lambda=e^{\Gamma}-1$, where $\Lambda$ and $\Gamma$ are given
by (26). Since $|\Lambda|\leq 2/27$, we have that $e^{|\Gamma|}\leq 27/25$ and
using the inequality (25) we obtain

$\displaystyle|\Gamma|=\left|m\log\alpha-\log(\sqrt{r^{2}+4})-x\log
U_{n+1}\right|\leq
e^{|\Gamma|}|e^{|\Gamma|}-1|\leq\frac{27|\Lambda|}{25}<\dfrac{2.2}{r^{x}}.$
(27)

We record the above inequality for future reference.

######  Lemma 7.

With $\Gamma$ given by formula Eq. (26), inequality Eq. (27) holds.

We want to apply Theorem 2 with the following data:

$\displaystyle\quad\gamma_{1}:=\alpha-\beta=\sqrt{r^{2}+4},\quad\gamma_{2}:=\alpha,\quad\gamma_{3}:=U_{n+1},\quad
b_{1}:=1,\quad b_{2}:=m,\quad b_{3}:=x.$

We need to check that $\gamma_{1}$, $\gamma_{2}$, and $\gamma_{3}$ are
multiplicatively independent. This we do in the next subsection.

###  3.4. Checking that $\gamma_{1},~{}\gamma_{2},~{}\gamma_{3}$ are
multiplicatively independent

Well, assume they are not and let $i,j,k$ be integers not all zero such that

$\gamma_{1}^{i}\gamma_{2}^{j}\gamma_{3}^{k}=1.$

Squaring and rearranging the above relation we get
$\gamma_{2}^{2j}=(\gamma_{1}^{2})^{-i}\gamma_{3}^{-2k}\in{\mathbb{Q}}$.
However, $\gamma_{2}^{2j}$ is also a unit, so an algebraic integer whose
reciprocal is also an algebraic integer, and it is also positive, so it must
be $1$. Thus, $j=0$. It now follows that $i$ and $k$ are both nonzero (since
if one of them is, so is the other one) and further
$\gamma_{3}=\gamma_{1}^{-i/k}$. In particular, all prime factors of $U_{n+1}$
are prime factors of $\Delta:=r^{2}+4$. But this is also contemplated by the
Primitive Divisor Theorem of Carmichael since primes dividing $\Delta$ are not
considered primitive. In particular, $U_{n+1}$ does not have primitive prime
factors so $n+1\leq 12$. In fact, Theorem C in [1] together with Table 1 there
show that either $n+1\in\\{2,3,4,6\\}$ or $n+1\in\\{5,12\\}$ but in this last
case, the only such Lucas sequence ${\bf U}$ for which either one of $U_{5}$
or $U_{12}$ does not have primitive prime factors is the sequence of Fibonacci
numbers, which is not our case. Thus, $n+1\in\\{2,3,6\\}$. Further, for each
prime $p$ let $z(p)$ be the index of appearance of $p$ in ${\bf U}$ defined as
the smallest positive integer $k$ such that $p\mid U_{k}$. This always exists
for our sequence ${\bf U}$ since $\alpha$ is a quadratic unit. It has the
additional property that if $\ell$ is a positive integer then $p\mid U_{\ell}$
if and only if $z(p)\mid\ell$. It is also well–known and easy to prove that if
$p\mid\Delta$, then $z(p)=p$. Since also $z(p)\mid n+1$ and
$n+1\in\\{2,3,6\\}$, it follows that the only possibilities for $p$ are
$p=2,3$. Hence, $r^{2}+4=2^{a}3^{b}$. However, $3$ cannot divide $r^{2}+4$ for
any positive integer $r$ (because $-4$ is not a quasartic residue modulo $3$),
so $b=0$ and $2^{a}=r^{2}+4$. Thus, $r=2r_{0}$ is even, $a\geq 3$ and the
equation simplifies to $2^{a-2}=r_{0}^{2}+1$. Hence, $r_{0}$ is odd, so
$r_{0}^{2}\equiv 1\pmod{8}$, therefore $2\|r_{0}^{2}+1$, which leads to
$a=3,~{}r_{0}=1$, which gives $r=2$, is not our case. Hence, indeed
$\gamma_{1},~{}\gamma_{2},~{}\gamma_{3}$ are multiplicatively independent.

###  3.5. Applying Theorem 2

Since $\gamma_{1},\gamma_{2},\gamma_{3}\in\mathbb{Q}(\alpha)$, we have
$\mathcal{D}=2$. We also have

$r<\alpha<{\sqrt{r^{2}+4}}<r+1.$

So, we bound the heights of $\alpha$ and ${\sqrt{r^{2}+4}}$ in terms or
$\log(r+1)$. Since

$h(\gamma_{1})=h(\alpha-\beta)=\dfrac{1}{2}\log(r^{2}+4)<\log(r+1),\quad
h(\gamma_{2})=\dfrac{1}{2}\log\alpha<\dfrac{1}{2}\log(r+1),$

and

$h(\gamma_{3})=\log U_{n+1}<\log\alpha^{n}=n\log\alpha<n\log(r+1),$

we can take

$A_{1}:=8.296\log(r+1),\quad A_{2}:=6.296\log(r+1),\quad
A_{3}:=8.296n\log(r+1).$

Thus $\Omega:=A_{1}A_{2}A_{3}>433n(\log(r+1))^{3}>100$ since $n\geq 2$ and
$r\geq 3$. Then,

$\displaystyle b^{{}^{\prime}}$ $\displaystyle=$
$\displaystyle\left(\dfrac{1}{6.296\log(r+1)}+\dfrac{m}{8.296\log(r+1)}\right)\left(\dfrac{x}{6.296\log(r+1)}+\dfrac{m}{8.296n\log(r+1)}\right)$
(28) $\displaystyle<$
$\displaystyle\dfrac{m}{(\log(r+1))^{2}}\left(\dfrac{1}{6.296}+\dfrac{1}{8.296}\right)\dfrac{x}{\log(r+1)}\left(\dfrac{1}{6.296}+\dfrac{2}{8.296}\right)$
$\displaystyle<$ $\displaystyle\dfrac{0.12mx}{(\log(r+1))^{2}}.$

In the above chain of inequalities, we used the fact that $m<(n+1)x+2<2nx$
(see inequality Eq. (19)) since $n\geq 2$ and $x\geq 3$. Further, putting

$\log\mathcal{B}:=\max\left\\{0.882+\log\left(\frac{0.12mx}{(\log(r+1))^{2}}\right),5\right\\},$

we have that either the inequality

$\log|\Gamma|>-790.95\times 434n(\log(r+1))^{3}\times
2^{2}\times(\log{\mathcal{B}})^{2}$ (29)

holds, or the other possibilities (i), (ii) from Theorem 2 hold. We treat (i)
and (ii) later and deal with the above inequality Eq. (29) at this stage. If
$\log\mathcal{B}=5$, then

$x<mx<\frac{e^{5-0.882}}{0.12}(\log(r+1))^{2}<512(\log(r+1))^{2}.$ (30)

On the other hand, if $\log\mathcal{B}>5$, then

$\log\mathcal{B}:=0.882+\log\left(\frac{0.12mx}{(\log(r+1))^{2}}\right)<\log\left(\frac{0.3mx}{(\log(r+1))^{2}}\right),$
(31)

where in the above inequality we used the fact that $e^{0.882}\times
0.12<0.3$. Thus, we get that

$\displaystyle\log|\Gamma|$ $\displaystyle>-790.95\times
434n(\log(r+1))^{3}\times
2^{2}\times\left(\log\left(\dfrac{0.3mx}{(\log(r+1))^{2}}\right)\right)^{2}$
$\displaystyle>-1.374\times
10^{6}n(\log(r+1))^{3}\left(\log\left(\dfrac{0.3mx}{(\log(r+1))^{2}}\right)\right)^{2}.$

Comparing this inequality with Eq. (27), we get that

$\displaystyle x\log r-\log 2.2<1.374\times
10^{6}n(\log(r+1))^{3}\left(\log\left(\dfrac{0.3mx}{(\log(r+1))^{2}}\right)\right)^{2},$

which implies, via the inequality

$\frac{\log(r+1)}{\log r}=1+\frac{\log(1+1/r)}{\log r}<1+\frac{1}{r\log r},$
(32)

that

$\displaystyle x$ $\displaystyle<$ $\displaystyle\frac{\log 2.2}{\log
r}+1.374\times 10^{6}n\left(\frac{\log(r+1)}{\log
r}\right)(\log(r+1))^{2}\left(\log\left(\dfrac{0.3mx}{(\log(r+1))^{2}}\right)\right)^{2}$
(33) $\displaystyle<$ $\displaystyle\frac{\log 2.2}{\log r}+1.374\times
10^{6}n\left(1+\frac{1}{r\log
r}\right)(\log(r+1))^{2}\left(\log\left(\dfrac{0.3mx}{3(\log(r+1))^{2}}\right)\right)^{2}$
$\displaystyle<$ $\displaystyle 1.38\times 10^{6}n\left(1+\frac{1}{r\log
r}\right)(\log(r+1))^{2}\left(\log\left(\dfrac{0.3mx}{(\log(r+1))^{2}}\right)\right)^{2}.$

Using the inequality Eq. (19), we know that $m<(n+1)x+2<(n+1)(x+1)$ (because
$n\geq 2$), and substituting this in (33) we get that

$\displaystyle x<1.38\times 10^{6}n\left(1+\frac{1}{r\log
r}\right)(\log(r+1))^{2}\left(\log\left(\dfrac{0.3(n+1)(x+1)^{2}}{(\log
r)^{2}}\right)\right)^{2}.$ (34)

We now turn our attention to the possibilities (i) and (ii). In case (i),
there are positive integers $r_{0},s_{0}$, which may be assumed to be coprime,
such that $r_{0}b_{2}=s_{0}b_{1}$. So, we get $r_{0}m=s_{0}$ and since
$r_{0},s_{0}$ are coprime, we take $r_{0}=1,s_{0}=m$, and we get

$\displaystyle m$ $\displaystyle=$ $\displaystyle
s_{0}<5.61A_{1}(\mathcal{D}\log\mathcal{D})^{1/3}<5.61\times 8.296\times(2\log
2)^{1/3}\log(r+1)$ $\displaystyle<$ $\displaystyle 5.61\times
8.296\times(2\log 2)^{1/3}\log(r+1)$ $\displaystyle<$ $\displaystyle
52\log(r+1).$

Since $m>(n-1)x+1>x$, this situation gives

$x<52\log(r+1).$ (35)

This was in situation (i). In situation (ii), we have integers
$r_{1},s_{1},t_{1},t_{2}$ with $r_{1}s_{1}\neq 0$ and

$(t_{1}b_{1}+r_{1}b_{3})s_{1}=r_{1}b_{2}t_{2},\qquad\gcd(r_{1},t_{1})=\gcd(s_{1},t_{2})=1.$

Thus, for us, we have

$(t_{1}+r_{1}x)s_{1}=r_{1}mt_{2},\qquad\gcd(r_{1},t_{1})=\gcd(s_{1},t_{2})=1.$

Reducing the above equation modulo $r_{1}$ we get $t_{1}s_{1}\equiv
0\pmod{r_{1}}$ and since $\gcd(t_{1},r_{1})=1$, we get that $r_{1}\mid s_{1}$.
So, we put $s_{1}=r_{1}s_{1}^{\prime}$ and simplify both sides of the above
equation by $r_{1}$ to get

$(t_{1}+r_{1}x)s_{1}^{\prime}=mt_{2}.$

Consequently, for us $\delta=\gcd(r_{1},s_{1})=r_{1}$. Hence,

$\displaystyle|t_{1}s_{1}^{\prime}|$ $\displaystyle<$ $\displaystyle
5.61A_{1}(\mathcal{D}\log\mathcal{D})^{1/3}<5.61\times
8.296\log(r+1)\times(2\log 2)^{1/3}<52\log(r+1);$ $\displaystyle|t_{2}|$
$\displaystyle<$ $\displaystyle
5.61A_{2}(\mathcal{D}\log\mathcal{D})^{1/3}<5.61\times 6.296(2\log
2)^{1/3}\log(r+1)<40\log(r+1);$ (36) $\displaystyle|r_{1}s_{1}^{\prime}|$
$\displaystyle<$ $\displaystyle
5.61A_{3}(\mathcal{D}\log\mathcal{D})^{1/3}<5.61\times 8.296(2\log
2)^{1/3}n\log(r+1)<52n\log(r+1).$

Assume first that $t_{2}=0$. Then

$x=|t_{1}|/|r_{1}|\leq|t_{1}|<52\log(r+1),$

which is the same as (35). Assume next that $t_{2}\neq 0$. We return to
inequality Eq. (27) and multiply both sides by $t_{2}$ and get

$\left|mt_{2}\log\gamma_{2}-t_{2}\log\gamma_{1}-xt_{2}\log\gamma_{3}\right|<\dfrac{2.2|t_{2}|}{r^{x}}.$

We substitute $mt_{2}$ by $t_{1}s_{1}^{\prime}+(r_{1}s_{1}^{\prime})x$ inside
the left–hand side above and then the left–hand side above becomes

$\left|\log\left(\frac{\gamma_{2}^{t_{1}s_{1}^{\prime}}}{\gamma_{1}^{t_{2}}}\right)+x\log\left(\frac{\gamma_{2}^{r_{1}s_{1}^{\prime}}}{\gamma_{3}^{t_{2}}}\right)\right|<\frac{2.2|t_{2}|}{r^{x}}.$
(37)

Inequality (37) is of the form

$|\Gamma_{1}|<\frac{2.2|t_{2}|}{r^{x}},\quad{\text{\rm
where}}\quad\Gamma_{1}:=\log\eta_{1}+x\log\eta_{2},$ (38)

and

$\eta_{1}:=\frac{\gamma_{2}^{t_{1}s_{1}^{\prime}}}{\gamma_{1}^{t_{2}}},\quad\eta_{2}:=\frac{\gamma_{2}^{r_{1}s_{1}^{\prime}}}{\gamma_{3}^{t_{2}}}.$

We check that $\eta_{1}$ and $\eta_{2}$ are multiplicatively independent. If
not, there are integers $i,j$ not both zero such that
$\eta_{1}^{i}\eta_{2}^{j}=1$. This gives

$\left(\frac{\gamma_{2}^{t_{1}s_{1}^{\prime}}}{\gamma_{1}^{t_{2}}}\right)^{i}\left(\frac{\gamma_{2}^{r_{1}s_{1}^{\prime}}}{\gamma_{3}^{t_{2}}}\right)^{j}=1.$

If $i\neq 0$, this gives a multiplicative dependence among
$\gamma_{1},\gamma_{2},\gamma_{3}$ with the exponent of $\gamma_{1}$ being the
nonzero integer $-t_{2}i$, a contradiction with the main result of Subsection
3.4. Thus, $i=0$, so $j\neq 0$, and we get again a multiplicative relation
among $\gamma_{2},\gamma_{3}$ (the exponent of $\gamma_{3}$ being the nonzero
integer $-t_{2}j$), which is the same contradiction. Thus, indeed $\eta_{1}$
and $\eta_{2}$ are multiplicatively independent and they are also positive.
So, we are in position to apply Theorem 3 to the left–hand side of inequality
Eq. (38). We compute $\log B_{i}$ for these choices. We have, by the
properties (15),

$\displaystyle h(\eta_{1})$ $\displaystyle\leq$
$\displaystyle|t_{1}s_{1}^{\prime}|h(\gamma_{2})+|t_{2}|h(\gamma_{1})\leq(52\log(r+1))(1/2\log(r+1))+(40\log(r+1))\log(r+1)$
$\displaystyle=$ $\displaystyle 66(\log(r+1))^{2};$ $\displaystyle
h(\eta_{2})$ $\displaystyle\leq$
$\displaystyle|r_{1}s_{1}^{\prime}|h(\gamma_{2})+|t_{2}|h(\gamma_{3})\leq
52n\log(r+1)(1/2\log(r+1))+(40\log(r+1))(n\log(r+1))$ $\displaystyle=$
$\displaystyle 66n(\log(r+1))^{2}.$

Since $|\log\gamma_{i}|/2\leq h(\gamma_{i})$ holds for $i=1,2,3$, it follows,
by the absolute value inequality, that the same inequalities are satisfied by
the numbers $|\log\eta_{i}|/2$ for $i=1,2$. Thus, since ${\mathcal{D}}=2$, we
can take

$\log{B}_{1}:=66(\log(r+1))^{2},\quad\log{B}_{2}:=66n(\log(r+1))^{2}.$

We bound

$\frac{1}{2\log B_{2}}+\frac{x}{2\log
B_{1}}=\frac{1}{132(\log(r+1))^{2}}\left(\frac{1}{n}+x\right)<\frac{x+1}{132(\log(r+1))^{2}}.$

Hence, we take

$b^{\prime}:=\frac{x+1}{132(\log(r+1))^{2}}.$

Now Theorem 3 gives

$\displaystyle\log|\Lambda|$ $\displaystyle>$ $\displaystyle-24.34\times
2^{4}(\max\\{\log
b^{\prime}+0.14,10.5\\})^{2}\times(66(\log(r+1))^{2})\times(66n(\log(r+1))^{2})$
(39) $\displaystyle>$ $\displaystyle-1.627\times 10^{6}n(\log(r+1))^{4}M^{2},$

where $M:=\max\\{\log b^{\prime}+0.4,10.5\\}$. In case $M=10.5$, we get

$b^{\prime}<e^{10.5-0.4}<24400,$

which gives

$x+1<24400\times 132(\log(r+1))^{2}<3.3\times 10^{6}(\log(r+1))^{2}.$ (40)

Finally, suppose that

$M=\log
b^{\prime}+0.4=\log(e^{0.4}b^{\prime})<\log(1.5b^{\prime})=\log\left(\frac{x+1}{88(\log(r+1))^{2}}\right).$

Comparing inequality (39) with inequality (38), we get

$x\log r-\log(2.2|t_{2}|)<1.627\times
10^{6}n(\log(r+1))^{4}\left(\log\left(\frac{x+1}{88(\log(r+1))^{2}}\right)\right)^{2}.$

Since $2.2|t_{2}|<88\log(r+1)$, we get that

$x<\frac{\log(88\log(r+1))}{\log r}+1.627\times
10^{6}\left(\frac{\log(r+1)}{\log
r}\right)(\log(r+1))^{3}\left(\log\left(\frac{x+1}{88(\log(r+1))^{2}}\right)\right)^{2}.$

The first summand in the right–hand side is $<5$ for all $r\geq 3$. Using
inequality Eq. (32), we get that

$x<1.63\times 10^{6}n\left(1+\frac{1}{r\log
r}\right)(\log(r+1))^{3}\left(\log\left(\frac{x+1}{88(\log(r+1))^{2}}\right)\right)^{2}.$
(41)

To summarise, either we are in the first situation of Theorem 2 and
$\log\mathcal{B}=5$, in which case inequality Eq. (30) holds, or
$\log\mathcal{B}>5$ in which case inequality Eq. (34) holds, or we are in the
exceptional case (i) for which inequality Eq. (35) holds, which is contained
in inequality Eq. (30), or we are in the exceptional situation (ii) in which
case either inequality Eq. (40) holds, or inequality Eq. (63) holds. Since
inequality Eq. (30) is contained in inequality Eq. (40), it follows, using the
inequality $1/88<0.12$, that we proved the following result.

######  Lemma 8.

One of the following inequalities holds:

$\displaystyle x$ $\displaystyle<$ $\displaystyle 3.3\times
10^{6}(\log(r+1))^{2};$ (42) $\displaystyle x$ $\displaystyle<$ $\displaystyle
1.38\times 10^{6}n\left(1+\frac{1}{r\log
r}\right)(\log(r+1))^{2}\left(\log\left(\dfrac{0.3(n+1)(x+1)^{2}}{(\log(r+1))^{2}}\right)\right)^{2};$
(43) $\displaystyle x$ $\displaystyle<$ $\displaystyle 1.63\times
10^{6}n\left(1+\frac{1}{r\log
r}\right)(\log(r+1))^{3}\left(\log\left(\frac{0.12(x+1)}{(\log(r+1))^{2}}\right)\right)^{2}.$
(44)

###  3.6. More inequalities in terms of $n$ and $x$

We put

$\kappa:=nx+1-m$ (45)

Later we shall show that $\kappa$ is positive except possibly if $r=3$. In
this section, assuming that it is positive, we show how it gives some lower
bounds for $x$ in terms of $n$.

######  Lemma 9.

The following holds:

  * (i)

$\kappa\neq 1$;

  * (ii)

If $\kappa=2$ and $n\geq 3$ then $x\geq r^{\max\\{2,n-3\\}}$;

  * (iii)

If $\kappa\geq 3$, then $\kappa\geq n/2$.

###### Proof.

(i). If $\kappa=1$, then $m=nx$. So the equation (3) becomes

$U_{n}^{x}+U_{n+1}^{x}=U_{nx}.$

If $p$ is prime dividing $U_{n}$ (which exists since $n>1$), then $p\mid
U_{n}^{x}$ and $p\mid U_{n}\mid U_{nx}$, so from the above equation we get
$p\mid U_{n+1}$, a contradiction since $\gcd(U_{n},U_{n+1})=U_{\gcd(n,n+1)}=1$
by relation (12).

(ii) In this case $m=nx-1$ so the equation (3) becomes

$U_{n}^{x}+U_{n+1}^{x}=U_{nx-1}.$

In particular, $U_{nx-1}-U_{n+1}^{x}\equiv 0\pmod{U_{n}^{2}}$. We study this
congruence. In what follows for three algebraic integers $a,b,c$, we write
$a\equiv b\pmod{c}$ if $(a-b)/c$ is an algebraic integer. Write

$U_{n}=\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta}\qquad{\text{\rm
as}}\qquad\alpha^{n}=\beta^{n}+{\sqrt{\Delta}}U_{n}.$

Then

$\alpha^{nx}=(\beta^{n}+{\sqrt{\Delta}}U_{n})^{x}\equiv\beta^{nx}+x\beta^{n(x-1)}{\sqrt{\Delta}}U_{n}\pmod{\Delta
U_{n}^{2}}.$

Thus,

$\displaystyle U_{nx-1}$ $\displaystyle=$
$\displaystyle\frac{\alpha^{nx}\alpha^{-1}-\beta^{nx-1}}{{\sqrt{\Delta}}}$
$\displaystyle\equiv$
$\displaystyle\frac{(\beta^{nx}+x\beta^{n(x-1)}{\sqrt{\Delta}}U_{n})\alpha^{-1}-\beta^{nx-1}}{\alpha-\beta}\pmod{{\sqrt{\Delta}}U_{n}^{2}}$
$\displaystyle\equiv$
$\displaystyle\frac{\beta^{nx}\alpha^{-1}-\beta^{nx}\beta^{-1}}{\alpha-\beta}+x\beta^{n(x-1)}\alpha^{-1}U_{n}\pmod{U_{n}^{2}}$
$\displaystyle\equiv$
$\displaystyle\beta^{nx}+x\beta^{n(x-1)}\alpha^{-1}U_{n}\pmod{U_{n}^{2}}.$

On the other hand,

$\displaystyle U_{n+1}^{x}$ $\displaystyle=$
$\displaystyle\left(\frac{\alpha^{n+1}-\beta^{n+1}}{{\sqrt{\Delta}}}\right)^{x}$
$\displaystyle\equiv$
$\displaystyle\left(\frac{(\beta^{n}+{\sqrt{\Delta}}U_{n})\alpha-\beta^{n+1}}{\sqrt{\Delta}}\right)^{x}\pmod{U_{n}^{2}}$
$\displaystyle\equiv$
$\displaystyle(\beta^{n}+U_{n}\alpha)^{x}\pmod{U_{n}^{2}}$
$\displaystyle\equiv$ $\displaystyle\beta^{nx}+x\beta^{n(x-1)}\alpha
U_{n}\pmod{U_{n}^{2}}.$

Thus,

$\displaystyle U_{nx-1}-U_{n+1}^{x}$ $\displaystyle\equiv$
$\displaystyle(\beta^{nx}+x\beta^{n(x-1)}\alpha^{-1}U_{n})-(\beta^{nx}+x\beta^{n(x-1)}\alpha
U_{n})\pmod{U_{n}^{2}}$ $\displaystyle\equiv$ $\displaystyle
x\beta^{n(x-1)}(\alpha^{-1}-\alpha)U_{n}\pmod{U_{n}^{2}}$
$\displaystyle\equiv$ $\displaystyle-x\beta^{n(x-1}rU_{n}\pmod{U_{n}^{2}}.$

In the last step above, we used the fact that
$\alpha^{-1}-\alpha=-\beta-\alpha=-r$. Since the expression
$U_{nx-1}-U_{n+1}^{x}$ is divisible by $U_{n}^{2}$, we get that
$U_{n}^{2}\mid\beta^{n(x-1)}xrU_{n}$. Since $\beta$ is a unit, we get that
$U_{n}\mid xr$. For $n=2$, this gives us nothing since $U_{2}=r$. For $n=3$,
$U_{3}=r^{2}+1$ is coprime to $r$, so $U_{3}\mid x$, which gives $x\geq
r^{2}+1>r^{2}$. For $n=4$, we have that $U_{4}=r(r^{2}+2)$ divides $rx$, so
$r^{2}+2\mid x$ giving $x\geq r^{2}+2>r^{2}$. Finally, for $n\geq 5$, we have
that $U_{n}>\alpha^{n-2}>r^{n-2}$ and so $x\geq U_{n}/r\geq r^{n-3}$. This
proves (ii).

(iii) We may assume that $n\geq 7$, otherwise the conclusion is trivial.
Recall that $V_{n}=\alpha^{n}+\beta^{n}$. Relations Eq. (9) and (10) are

$U_{n+1}^{2}-U_{n}U_{n+2}=(-1)^{n}\qquad{\text{\rm and}}\qquad
V_{n}^{2}-\Delta U_{n}^{2}=4(-1)^{n}.$

In particular, $U_{n+1}^{2}\equiv(-1)^{n}\pmod{U_{n}}$ and $V_{n}^{2}\equiv
4(-1)^{n}\pmod{U_{n}}$. We also use the fact that $U_{-m}=(-1)^{m-1}U_{m}$,
$V_{-m}=(-1)^{m}V_{m}$ and relation Eq. (11) which is

$2U_{m+n}=U_{m}V_{n}+U_{n}V_{m}.$

Armed with these facts, writing $m=nx-(\kappa-1)$ and

$U_{n}^{x}+U_{n+1}^{x}=U_{nx-(\kappa-1)},$

we multiply both sides of the above equation by $2$ and write

$2U_{n}^{x}+2U_{n+1}^{x}=2U_{nx-(\kappa-1)}=U_{nx}V_{-(\kappa-1)}+V_{nx}U_{-(\kappa-1)}.$

We square both sides of the above equation and reduce it modulo $U_{n}$ taking
into account that $U_{n}\mid U_{nx}$ and $V_{nx}^{2}\equiv
4(-1)^{nx}\pmod{U_{nx}}\equiv 4(-1)^{nx}\pmod{U_{n}}$, and get

$\displaystyle 4(-1)^{nx}$ $\displaystyle\equiv$ $\displaystyle
4(U_{n+1}^{2})^{x}\pmod{U_{n}}\equiv(U_{nx}V_{-(\kappa-1)}+V_{nx}U_{-(\kappa-1)})^{2}\pmod{U_{n}}$
$\displaystyle\equiv$ $\displaystyle
V_{nx}^{2}U_{-(\kappa-1)}^{2}\pmod{U_{n}}\equiv
V_{nx}^{2}U_{\kappa-1}^{2}\pmod{U_{n}}\equiv
4(-1)^{nx}U_{\kappa-1}^{2}\pmod{U_{n}}.$

Thus, $U_{n}\mid 4(U_{\kappa-1}^{2}-1)$. The right–hand side is nonzero since
$\kappa>2$. If $\kappa-1$ is odd, then

$4(U_{\kappa-1}^{2}-1)=4U_{\kappa-2}U_{\kappa}$

by relation Eq. (9) (with $n+1:=\kappa-1$). Since $n\geq 7$ and ${\bf U}$ is
not the Fibonacci sequence, it follows that $U_{n}$ has a primitive divisor
$p$, which must divide one of $U_{\kappa-2}$ or $U_{\kappa}$. Thus, $z(p)=n$
divides one of $\kappa-2$ or $\kappa$, so we get $\kappa\geq n$, which is a
better conclusion than the one desired. If $\kappa-1$ is even and $U_{n}\mid
2(U_{\kappa-1}^{2}-1)$, we then get

$\alpha^{n-2}<U_{n}<2U_{\kappa-1}^{2}<r(\alpha^{\kappa-1})^{2}<\alpha^{2\kappa-1},$

so $2\kappa-2\geq n-2$, therefore $\kappa\geq n/2$. The above argument was
based on the fact that $r\geq 2$. In particular, if $r\geq 4$, then the same
argument gives again that

$\alpha^{n-2}<U_{n}<4U_{\kappa-1}^{2}<r(\alpha^{\kappa-1})^{2}<\alpha^{2\kappa-1},$

so $\kappa\geq n/2$. So, the only case when the above arguments fail are when
$r=3$ and $4\mid U_{n}$. It then follows that $n$ is even (in fact, $n$ is a
multiple of $6$, but we shall not need that), so $r\mid U_{n}\mid
4(U_{\kappa-1}^{2}-1)$. But $U_{\kappa-1}$ is a multiple of $r$ (since
$\kappa-1$ is even), so $U_{\kappa-1}^{2}-1$ is coprime to $r$. Thus, $r\mid
4$, which is false. This finishes the proof of (iii). ∎

######  Corollary 4.

If $\kappa>0$, then $x>n/2$.

###### Proof.

By Lemma 9, if $\kappa=2$, then $x\geq r^{\min\\{2,n-3\\}}\geq
3^{\min\\{2,n-3\\}}>n/2$ for any $n\geq 2$. If $\kappa\geq 3$, then

$1+nx-m=\kappa\geq n/2,$

which leads to $1+nx-n/2\geq m$. Comparing this with the lower bound
$m>(n-1)x+1$ given by inequality Eq. (19), we get $x>n/2$. ∎

###  3.7. Another inequality among $r,n,m,x$

In this section, we return to inequality Eq. (27) and rewrite it in order to
deduce a good approximation of $\log r$ by a rational number whose denominator
is a multiple of $r^{2}$. Let’s get to work. We need approximations of
$\log\alpha$ and $\log{\sqrt{r^{2}+4}}$ in terms of $\log r$.

######  Lemma 10.

For $r\geq 3$, we have the following approximations:

$\displaystyle\log{\sqrt{r^{2}+4}}$ $\displaystyle=$ $\displaystyle\log
r+\frac{2}{r^{2}}+\zeta,\quad|\zeta|<\frac{5.81}{r^{4}};$ (46)
$\displaystyle\log\alpha$ $\displaystyle=$ $\displaystyle\log
r+\frac{1}{r^{2}}+\zeta^{\prime},\quad|\zeta^{\prime}|<\frac{3.64}{r^{4}}.$
(47)

###### Proof.

We have

$\log{\sqrt{r^{2}+4}}=\frac{1}{2}\log(r^{2}+4)=\log
r+\frac{1}{2}\log\left(1+\frac{4}{r^{2}}\right).$

With $z:=4/r^{2}$, we have $|z|\leq 4/9$ and

$\log(1+z)=z+\zeta_{1},\quad|\zeta_{1}|\leq\sum_{k\geq
2}\frac{z^{k}}{k}=\frac{z^{2}}{2}\left(1+(2/3)z+(2/4)z^{2}+\cdots\right).$

The expression in parenthesis above is smaller than

$c_{1}:=1+(2/3)(4/9)+(2/4)(4/9)^{2}+\cdots=(-4/9-\log(1-4/9))\times
2\times(9/4)^{2}.$

Hence,

$\log{\sqrt{r^{2}+4}}=\log r+\frac{2}{r^{2}}+\frac{\zeta_{1}}{2}:=\log
r+\frac{2}{r^{2}}+\zeta,\quad|\zeta|=\frac{|\zeta_{1}|}{2}<\left(\frac{c_{1}}{4}\right)z^{2}=\frac{4c_{1}}{r^{4}}<\frac{5.81}{r^{4}}.$

For $\alpha$, we write

$\log\alpha=\log
r+\log\left(\frac{1}{2}+{\sqrt{\frac{1}{4}+\frac{1}{r^{2}}}}\right)=\log
r+\log(1+z_{1}),\quad z_{1}:={\sqrt{\frac{1}{4}+\frac{z}{4}}}-\frac{1}{2}.$

Note that $|z_{1}|\leq 1/r^{2}$. Thus,

$\log(1+z_{1})=z_{1}+\zeta_{2},\quad|\zeta_{2}|\leq\frac{|z_{1}|^{2}}{2}(1+(2/3)|z_{1}|+\cdots)\leq\frac{c_{2}}{2r^{4}},$

where by the previous arguments,

$c_{2}=(-\lambda_{0}-\log(1-\lambda_{0}))\times
2\times\lambda_{0}^{-2},\quad{\text{\rm
with}}\quad\lambda_{0}:={\sqrt{\frac{1}{4}+\frac{1}{9}}}-\frac{1}{2}.$

It remains to expand $z_{1}$. For this, we have

$z_{1}=\frac{1}{2}({\sqrt{1+z}}-1)=\frac{1}{2}\left(\frac{z}{2}+\zeta_{3}\right),\quad|\zeta_{3}|\leq\sum_{k\geq
2}\left|\binom{k}{1/2}\right|z^{k}.$

Since $|\binom{k}{1/2}|\leq 1/4$ for all $k\geq 1$, it follows that

$|\zeta_{3}|\leq\frac{1}{4}\sum_{k\geq
2}z^{k}=\frac{z^{2}}{4(1-z)}\leq\frac{36}{5r^{4}}.$

Hence,

$\log\alpha=\log
r+\frac{z}{4}+\left(\zeta_{2}+\frac{\zeta_{3}}{2}\right)=:\log
r+\frac{1}{r^{2}}+\zeta^{\prime},\quad|\zeta^{\prime}|<\left(\frac{c_{2}}{2}+\frac{36}{10}\right)\frac{1}{r^{2}}<\frac{3.64}{r^{4}}.$

∎

The following estimate is the main result of this section.

######  Lemma 11.

If $r\geq 4$, then $\kappa>0$. Furthermore,

$x>\frac{\kappa r^{2}\log r+1}{1+5/r}.$ (48)

###### Proof.

We shall use the approximations given in Lemma 10 but we also need an
approximation of $\log U_{n+1}$. We have

$\log
U_{n+1}=\log\left(\frac{\alpha^{n+1}}{\alpha-\beta}\left(1-\left(\frac{\beta}{\alpha}\right)^{n+1}\right)\right)=(n+1)\log\alpha-\log({\sqrt{r^{2}+4}})+\zeta^{\prime\prime},$
(49)

where

$\zeta^{\prime\prime}=\log\left(1-\left(\frac{\beta}{\alpha}\right)^{n+1}\right).$

Since $\beta=-\alpha^{-1}$, it follows that $|\beta/\alpha|=1/\alpha^{2}$.
Thus,

$|\zeta^{\prime\prime}|\leq\frac{1}{\alpha^{2n+2}}\left(1+\sum_{k\geq
1}\frac{1}{k(\alpha^{2n+2})^{k}}\right)\leq\frac{1}{\alpha^{2n+2}}\left(1+\frac{1}{2(1-1/\alpha^{2n+2})}\right)<\frac{1.51}{\alpha^{2n+2}},$
(50)

where for the last inequality we used the fact that $\alpha>r\geq 3$ and
$n\geq 2$. Inserting estimates Eq. (46) and Eq. (47) together with Eq. (49)
into inequality Eq. (27), we get

$\displaystyle|\Gamma|$ $\displaystyle=$
$\displaystyle\left|m\log\alpha-\log({\sqrt{r^{2}+4}})-x((n+1)\log\alpha-\log({\sqrt{r^{2}+4}})+\zeta^{\prime\prime})\right|$
$\displaystyle=$
$\displaystyle\left|(m-x(n+1))\log\alpha+(x-1)\log({\sqrt{r^{2}+4}})-x\zeta^{\prime\prime}\right|$
$\displaystyle=$ $\displaystyle\left|(m-x(n+1))\left(\log
r+\frac{1}{r^{2}}+\zeta^{\prime}\right)+(x-1)\left(\log
r+\frac{2}{r^{2}}+\zeta\right)-x\zeta^{\prime\prime}\right|$ $\displaystyle=$
$\displaystyle\left|(m-nx-1)\log
r+\frac{(m-nx-1)+(x-1)}{r^{2}}+(m-x(n+1))\zeta^{\prime}+(x-1)\zeta+x\zeta^{\prime\prime}\right|.$

We recognise the coefficient of $\log r$ as the number we denoted $-\kappa$ in
(45). Using inequality Eq. (27), we get

$\left|-\kappa\log
r+\frac{-\kappa+(x-1)}{r^{2}}\right|<\frac{2.2}{r^{x}}+|m-x(n+1)||\zeta^{\prime}|+|x-1||\zeta|+x|\zeta^{\prime\prime}|.$

Inequality Eq. (19) shows that $m-x(n+1)\in[-2x+2,2]$. In particular,
$|m-x(n+1)|\leq 2(x-1)$. We thus get, by estimates Eq. (46) and Eq. (47)
together with Eq. (49), that

$\left|-\kappa\log
r+\frac{-\kappa+(x-1)}{r^{2}}\right|<\frac{4}{r^{x}}+\frac{7.28(x-1)}{r^{4}}+\frac{5.81(x-1)}{r^{4}}+\frac{{1.51x}}{r^{6}}.$

Since $x\geq 3$ and $r\geq 3$, we get that the last term satisfies

$\frac{1.51x}{r^{6}}\leq\left(\frac{1.51\times(3/2)}{3^{2}}\right)\frac{(x-1)}{r^{4}}<\frac{0.26(x-1)}{r^{4}}.$

Hence,

$\left|-\kappa\log
r+\frac{-\kappa+(x-1)}{r^{2}}\right|<\frac{2.2}{r^{x}}+\frac{13.35(x-1)}{r^{4}}.$
(51)

Assume that $\kappa\leq 0$. We then get that

$\frac{x-1}{r^{2}}\leq\frac{2.2}{r^{x}}+\frac{13.35(x-1)}{r^{4}},$

which implies that

$1\leq\frac{13.35}{r^{2}}+\frac{2.2}{r^{x-2}(x-1)}.$

If $r\geq 5$, the right hand side is

$\leq\frac{13.35}{25}+\frac{2.2}{5\times 4}=\frac{13.54}{16}<1,$

a contradiction. Similarly, if $r\geq 4$ and $x\geq 4$, then the right side is

$\leq\frac{13.25}{16}+\frac{2.2}{16\times 3}<\frac{14}{16}<1.$

Thus, if $r\geq 5$ or $r=4$ and $x\geq 4$, then $\kappa>0$ and now Lemma 9
applies. We will show at the end of this proof that $\kappa\geq 0$ for
$(r,x)=(4,3)$ as well. Multiplying both sides of estimate (51) by $r^{2}$, we
get

$|-\kappa(r^{2}\log
r+1)+(x-1)|<(x-1)\left(\frac{13.35}{r^{2}}+\frac{2.2}{r^{x-2}(x-1)}\right).$

Hence,

$\kappa(r^{2}\log
r+1)<(x-1)\left(1+\left(\frac{13.35}{r^{2}}+\frac{2.2}{r^{x-2}(x-1)}\right)\right)\leq(x-1)\left(1+\frac{5}{r}\right),$

which gives estimate Eq. (48). It remains to treat the case $(r,x)=(4,3)$. By
inequality (19), we have $m<3(n+1)+1=3n+4$ so $\kappa=3n+1-m\geq-2$. So, the
only instances in which $\kappa\leq 0$ is possible are when
$m=3n+3,~{}m=3n+2,~{}3n+1$. Well, let us show that this is not possible by
proving that

$U_{n}^{3}+U_{n+1}^{3}<U_{3n+1}.$

Using the Binet formula Eq. (4), this is implied by

$\alpha^{-1}\left(1+\frac{1}{\alpha^{6n}}\right)^{3}+\alpha^{2}\left(1+\frac{1}{\alpha^{6n+6}}\right)^{3}<\Delta\left(1-\frac{1}{\alpha^{6n+3}}\right),$

with $\alpha=2+{\sqrt{5}}$ and $\Delta=20$. The function of $n$ in the left is
decreasing and the function with $n$ in the right is increasing, and the
inequality holds at $n=1$ (the left–hand side there is $<18.5$ and the right
side is $>19.5$), so it holds for all $n\geq 1$. Thus, $\kappa\geq 2$ for
$r=4$ as well. ∎

###  3.8. The case $n\leq 100$

We first seek bounds on $r$. Having the bounds in $r$ and $n$, we get bounds
on $x$ using Lemma 8. Finally, for a fixed $r$ we use Baker-Davenport on
estimate Eq. (27) to lower $x$. The hope is that in all cases $x\leq 100$, a
case which has already been treated.

We prove the following result.

######  Lemma 12.

When $n\leq 100$, we have $r\leq 1.5\times 10^{6}$.

###### Proof.

We assume $r>10^{6}$. Then $x>\kappa r^{2}\log r/1.01\geq nr^{2}\log r/2.02$
by Lemma 9 and Lemma 11. We go through the three possibilities of Lemma 8. In
case (i), we get

$r^{2}\log r\leq 1.01\times 3.3\times 10^{6}(\log(r+1))^{2},$

which gives $r<5500$, a contradiction. Assume we are in case (ii). Then

$x+1<1.38\times 10^{6}\times
1.001(\log(r+1))^{2}\log\left(\frac{0.3(n+1)(x+1)^{2}}{(\log(r+1))^{2}}\right).$
(52)

The factor $1.001$ is an upper bound on the factor $1+1/(r\log r)$ which is
valid since $r$ is large. Now

$x+1>x>\frac{nr^{2}\log r}{2.02}>nr^{2}\log(r+1)\left(\frac{\log
r}{2.02\log(r+1)}\right)>\frac{nr^{2}\log(r+1)}{2.03},$

where the last inequality holds since $r>10^{6}$. Put
$y:=(x+1)/(n(\log(r+1))$. Then the above inequality is $y>r^{2}/2.03$.
Inequality Eq. (52) can be rewritten in terms of $y$ as

$y<1.38\times 10^{6}\log(r+1)\times
1.001\left(\log(0.3n^{2}(n+1)y^{2})\right)^{2}<1.39\times
10^{6}\log(r+1)(2\log y+\log(30030))^{2}.$

We look at the function

$f(y):=\frac{y}{(2\log y+\log(30030))^{2}}.$

Its derivative is

$\frac{2\log y+\log(30030)-4}{(2\log y+\log(30030))^{3}}>0,$

so our function $f(y)$ is increasing. Since $f(y)<1.39\times 10^{6}\log(r+1)$,
and $y>r^{2}/2.03$, it follows that $f(r^{2}/2.03)<1.39\times
10^{6}\log(r+1)$. This gives

$r^{2}<1.39\times 2.03\times
10^{6}(\log(r+1))(2\log(r^{2}/2.03)+\log(30030))^{2},$

which gives $r<370000$, a contradiction. Assume we are in case (iii). We use
the same substitution $y:=(x+1)/(n(\log(r+1))$. We then get

$y<1.64\times 10^{6}(\log(r+1))^{2}(\log(0.12n^{2}y^{2}))^{2}\leq 1.64\times
10^{6}(\log(r+1))^{2}(2\log y+\log(12))^{2}.$

The function $g(y):=y/(2\log y+\log(12))^{2}$ is also increasing, so we deduce
that

$r^{2}<2.03\times 1.64\times
10^{6}(\log(r+1))^{2}(2\log(r^{2}/2.03)+\log(12))^{2},$

and this gives $r<1.5\times 10^{6}$. ∎

Having bounds on $n$ and $r$, inequalities (i), (ii) and (iii) from Lemma 8
become

$\displaystyle x$ $\displaystyle<$ $\displaystyle 3.3\times
10^{6}(\log(1.5\times 10^{6}))^{2}<7\times 10^{8};$ $\displaystyle x$
$\displaystyle<$ $\displaystyle 1.39\times 10^{6}\times 100(\log(1.5\times
10^{6}))^{2}\left(\log(0.3\times 101(x+1)^{2})\right)^{2}<3.7\times
10^{10}\log(30.3(x+1))^{2},$ $\displaystyle x$ $\displaystyle<$ $\displaystyle
1.64\times 10^{6}\times 100\times(\log(1.5\times
10^{6}))^{3}\left(\log(0.12(x+1)\right)^{2}<6.5\times
10^{11}\log(0.12(x+1))^{2}.$

Any one of these inequalities implies that $x<3\times 10^{15}$. Now we do
Baker-Davenport on estimates Eq. (27) for $n\in[2,100]$, $r\in[3,1500000]$,
and $x<3\times 10^{15}$. This also gives $m<3\times 10^{17}$ via inequality
Eq. (19). We return to inequality (27) and rewrite it as follows.

$\displaystyle\left|x\dfrac{\log
U_{n+1}}{\log\alpha}-m+\dfrac{\log\left(\sqrt{r^{2}+4}\right)}{\log\alpha}\right|<\dfrac{2.2}{r^{x}\log\alpha}.$
(53)

Then, we apply Lemma 5 on Eq. (53) with the data:

$\displaystyle M:=3\times 10^{17},\quad\tau:=\dfrac{\log
U_{n+1}}{\log\alpha},\quad\mu:=\dfrac{\log\left(\sqrt{r^{2}+4}\right)}{\log\alpha},\quad
A:=\dfrac{2.2}{\log\alpha},\quad\text{and}\quad B:=r.$

A computer search in Mathematica reveals that $x\leq 81$, which is a
contradiction. This computation lasted 16 hours on a cluster of four 16 GB RAM
computers.

###  3.9. The case $n>100$

Estimate Eq. (27) together with estimate Eq. (49) give

$|\Gamma|=|m\log\alpha-\log({\sqrt{r^{2}+4}}-x((n+1)\log\alpha-\log({\sqrt{r^{2}+4}}+\zeta^{\prime\prime})|<\frac{2.2}{r^{x}},$

which implies, via estimate Eq. (50), that

$|(m-x(n+1))\log\alpha+(x-1)\log({\sqrt{r^{2}+4}})|<\frac{2.2}{r^{x}}+\frac{1.51x}{\alpha^{2n+2}}.$
(54)

If $r\geq 4$ then $\kappa>0$, so by Lemma 9, we have $\kappa\geq 2$. If
$\kappa\geq 3$, then

$x\geq\frac{\kappa(r^{2}\log r+1)}{1+5/r}>\frac{n4^{2}\log 4}{4.5}>2n+2.$

The same conclusion holds for $\kappa=2$ since then $x\geq
r^{\min\\{2,n-3\\}}\geq 4^{\min\\{2,n-3\\}}\geq 2n+2$ for all $n\geq 2$. We
thus get

$|(m-x(n+1))\log\alpha+(x-1)\log({\sqrt{r^{2}+4}})|<\frac{4}{r^{2n+2}}+\frac{1.51x}{\alpha^{2n+2}}<\frac{1.51x+2.2}{\alpha^{2n+2}}.$
(55)

We prove the following lemma.

######  Lemma 13.

For $n>100$, we have $r^{n-2}>x$.

Note that Lemmas 9 and 13 show that the case $\kappa=2$ cannot occur for
$r\geq 4$ provided that $n>100$.

###### Proof.

Assume $x\geq r^{n-2}$. We use the bounds given by Lemma 8 on $x$. In case
(i), we get

$r^{99}\leq r^{n-2}\leq 3.3\times 10^{6}(\log(r+1))^{2}.$

The function $y\mapsto y^{99}/(\log(y+1))^{2}$ is increasing for all $y\geq 3$
as one can check by computing its derivative. Thus, if the above inequality
holds for $r$, it should hold $r=3$ as well, which is false. In case (ii), we
have

$x<1.38\times 10^{6}n\left(1+\frac{1}{r\log
r}\right)(\log(r+1))^{2}\left(\log\left(\frac{0.3(n+1)(x+1)^{2}}{(\log(r+1))^{2}}\right)\right)^{2}.$

The expression $1+1/(r\log r)$ is smaller than $1.304$ at $r=3$. Since
$1.38\times 1.304<1.8$, we get

$x<1.8\times
10^{6}(\log(r+1))^{2}\left(\log\left(\frac{0.3(n+1)(x+1)^{2}}{(\log(r+1))^{2}}\right)\right)^{2}.$

If $x\leq n$, then we get $r^{n-2}\leq n$ for $r\geq 3$ and $n\geq 101$, which
is false. Thus, $n<x$, so we may use $0.3(n+1)<n<x+1$ to get

$\displaystyle x+1$ $\displaystyle<$ $\displaystyle 1.8\times
10^{6}n(\log(r+1))^{2}(\log((x+1)^{3}))^{2}$ $\displaystyle<$ $\displaystyle
1.8\times 3^{2}\times 10^{6}(\log(r+1))^{2}(\log(x+1))^{2}$ $\displaystyle<$
$\displaystyle 1.7\times 10^{7}(\log(r+1))^{2}(\log(x+1))^{3}.$

The function $(x+1)/(\log(x+1))^{3}$ is increasing for $x+1>e^{3}$, which is
the case for us since $x\geq r^{99}\geq 3^{99}$. Hence, the above inequality
should hold for $x+1$ replaced by $r^{n-2}$, and that gives

$r^{n-2}\leq 1.7\times 10^{7}(\log(r+1))^{2}(\log(r^{n-2}))^{2}<1.7\times
10^{7}n^{2}(\log(r+1))^{4}.$

Since $r^{n/3}\geq 3^{n/3}>n$ holds for $n>100$, we get that

$r^{n/3-2}<1.7\times 10^{7}(\log(r+1))^{4},$

so

$r^{95}\leq r^{n-6}<\left(1.7\times 10^{7}(\log(r+1))^{2}\right)^{3}<5\times
10^{21}(\log(r+1))^{12}.$

The function $y\mapsto y^{95}/(\log(y+1))^{6}$ is increasing for $y\geq 3$, so
the last inequality should hold also for $r$ replaced by $3$, which is false.
A similar argument works if $x$ is in case (iii) of Lemma 8. We don’t give
further details. ∎

From Lemma 13 we conclude that if $r\geq 4$, then inequality Eq. (55) leads to

$|(m-x(n+1))\log\alpha+(x-1)\log({\sqrt{r^{2}+4}})|<\frac{1}{r^{n}}.$ (56)

We put

$\displaystyle\Gamma_{2}:=(x-1)\log\left(\sqrt{r^{2}+4}\right)-((n+1)x-m)\log\alpha.$

We apply Theorem 3 to find a lower bound on $\log|\Gamma_{2}|$ with the data:

$\displaystyle
t:=2,\quad\gamma_{1}:=\sqrt{r^{2}+4},\quad\gamma_{2}:=\alpha,\quad
b_{1}:=x-1,\quad b_{2}:=m-(n+1)x.$ (57)

Since $\gamma_{1},\gamma_{2}\in\mathbb{Q}(\alpha)$, we take again
$\mathbb{K}:=\mathbb{Q}(\alpha)$ with degree ${\mathcal{D}}:=2$. The fact that
$\gamma_{1}$ and $\gamma_{2}$ are multiplicatively independent has already
been checked.

We take

$\displaystyle\max\left\\{h(\gamma_{1}),\dfrac{|\log\gamma_{1}|}{2},\dfrac{1}{2}\right\\}=\dfrac{1}{2}\log(r^{2}+4)<\log(r+1):=\log
B_{1},$

and

$\displaystyle\max\left\\{h(\gamma_{2}),\dfrac{|\log\gamma_{2}|}{2},\dfrac{1}{2}\right\\}=\dfrac{1}{2}\log\alpha<\frac{1}{2}\log(r+1):=\log
B_{2}.$

Thus,

$\displaystyle b^{\prime}:=\dfrac{|b_{1}|}{D\log B_{2}}+\dfrac{|b_{2}|}{D\log
B_{1}}=\dfrac{x-1}{2\log(r+1)}+\dfrac{|(n+1)x-m|}{\log(r+1)}<\frac{2.5x}{\log(r+1)},$

where we used the fact that $m-(n+1)x\in[-2x+2,2]$. By Theorem 3, we get that

$\log|\Gamma_{2}|>-195\left(\max\left\\{\log\left(\frac{2.5x}{\log
r}\right),10.5\right\\}\right)^{2}(\log(r+1))^{2}.$ (58)

We want an upper bound on $r$. So, assume $r\geq 10^{6}$. If
$\log({(2.5x)}/{\log(r+1)})<10.5$, then

$x<\frac{e^{10.5}\log(r+1)}{2.5}<15000\log(r+1).$

Since $x>nr^{2}\log r/(2+10/r)\geq 101r^{2}\log r/2.02=50r^{2}\log r$, we get

$50r^{2}\log r\leq x\leq 15000(\log(r+1)),$

so

$r^{2}<\left(\frac{15000}{50}\right)\left(\frac{\log(r+1)}{\log
r}\right)<300\times 1.01=303,$

so $r\leq 17$, a contradiction.

Assume next that $\log(2.5x/\log(r+1))>10.5$. We then get

$\log|\Gamma_{2}|>-195(\log(r+1))^{2}\left(\log\left(\frac{2.5x}{\log(r+1)}\right)\right)^{2}.$

Comparing the above inequality with estimate Eq. (56), we get

$n\log
r<195(\log(r+1))^{2}\left(\log\left(\frac{2.5x}{\log(r+1)}\right)\right)^{2},$

so

$\displaystyle n$ $\displaystyle<$ $\displaystyle
195\left(\frac{\log(r+1)}{\log
r}\right)\log(r+1)\left(\log\left(\frac{2.5x}{\log(r+1)}\right)\right)^{2}$
$\displaystyle<$ $\displaystyle
196\log(r+1)\left(\log\left(\frac{2.5x}{\log(r+1)}\right)\right)^{2},$

where we used the fact that $r\geq 10^{6}$ so $\log(r+1)/\log r<1.0001$.

We now use the bounds on $x$ given by Lemma 8. In case (i), we have

$50r^{2}\log r\leq x\leq 3.3\times 10^{6}(\log(r+1))^{2},$

so

$r^{2}<\left(\frac{3.3\times
10^{6}}{50}\right)\times\left(\frac{\log(r+1)}{\log
r}\right)\log(r+1)<6.7\times 10^{4}\log(r+1),$

so $r<670$, a contradiction. In case (ii), we have

$x+1<1.39\times
10^{6}n(\log(r+1))^{2}\left(\log\left(\frac{0.3(n+1)(x+1)^{2}}{(\log(r+1))^{2}}\right)\right)^{2}.$

In case $(x+1)/(\log(r+1))\leq n$, we have

$x+1<196(\log(r+1))^{2}\left(\frac{2.5x}{\log(r+1)}\right)^{2}.$

So, putting $y:=x/\log(r+1)$, we get $y<196\log(r+1)\log(2.5y)^{2}$. Note that

$y=\frac{(x+1)}{\log(r+1)}>\frac{nr^{2}\log
r}{2.01\log(r+1)}\geq\frac{101r^{2}}{2.01(\log(r+1)/\log
r)}>\frac{101r^{2}}{2.02}=50r^{2}.$

In the above inequalities we used the fact that $r\geq 10^{6}$. The function
$y\mapsto y/\log(2.5y)^{2}$ is increasing for $y>e^{2}/2.5$, which is our
case. Hence, the inequality $y<196\log(r+1)\log(2.5y)^{2}$ should hold with
$y$ replaced by $50r^{2}$, which yields $50r^{2}<196\log(r+1)\log(2.5\times
50r^{2})^{2}$ and gives $r<50$, a contradiction. Thus, $n<(x+1)/\log(r+1)$.
Since $0.3(n+1)<n$, we conclude that

$x+1<1.39\times
10^{6}(\log(r+1))^{2}\left(196\log(r+1)\left(\log\left(\frac{2.5x}{\log(r+1)}\right)\right)^{2}\right)\left(\log\left(\left(\frac{(x+1)}{\log(r+1)}\right)^{3}\right)\right)^{2}.$

Putting again $y:=(x+1)/\log(r+1)$, we get

$y<1.39\times 10^{6}\times 196\times(\log(r+1))^{2}\log(2.5y)^{2}(3\log
y)^{2}<2.46\times 10^{9}(\log(2.5y))^{4}.$

The function $y\mapsto y/(\log(2.5y)^{4}$ is increasing for our range for
$y>50r^{2}>50\times 10^{16}$, so we get that the above inequality should hold
by replacing $y$ by $50r^{2}$. Thus,

$50r^{2}<2.46\times 10^{9}(\log(r+1))^{2}(\log(2.5\times 50r^{2}))^{4},$

so $r<2.6\times 10^{8}$. A similar argument holds when $x$ is in case (iii).
In that case, we may again suppose that $n<(x+1)/\log(r+1)$. We get

$x+1<1.64\times
10^{6}(\log(r+1))^{3}\left(196\log(r+1)\left(\log\left(\frac{2.5x}{\log(r+1)}\right)\right)^{2}\right)\left(\log\left(\frac{0.12(x+1)}{(\log(r+1))^{2}}\right)\right)^{2},$

so

$y<3.3\times 10^{8}(\log(r+1))^{3}(\log(2.5y))^{2}(\log(0.12y))^{2}.$

Imposing that the above inequality holds for $y$ replaced by $50r^{2}$, we get

$50r^{2}<1.3\times 10^{9}(\log(r+1))^{3}(\log(2.5\times
50r^{2}))(\log(0.12\times 50r^{2}))^{2},$

so $r<4.3\times 10^{8}$.

To summarise, we have proved the following.

######  Lemma 14.

If $r\geq 4$, then $r<4.3\times 10^{8}$.

Having bounds for $r$ it is easy to find bounds for $x$. For example,

$n<195\log(r+1)(\log(2.5x))^{2}<195\log(4.3\times
10^{8})(\log(2.5x))^{2}<3900(\log(2.5x))^{2}.$

Next, if $x$ is in case (i), then

$x<3.3\times 10^{6}(\log(r+1))^{2}<3.3\times 10^{6}(\log(4.3\times
10^{8}))^{2}<1.4\times 10^{9}.$

If $x$ is in case (ii), then

$\displaystyle x$ $\displaystyle<$ $\displaystyle 1.39\times
10^{6}(\log(4.3\times 10^{8})^{2}(3900(\log(2.5x))^{2})(\log(0.3\times
3900(\log(2.5x))^{2}(x+1)^{2}))^{2}$ $\displaystyle<$ $\displaystyle 2.2\times
10^{12}(\log(2.5x))^{2}(\log(1200(x+1)^{2}\log(2.5x)))^{2},$

which gives $x<5\times 10^{19}$. Finally, if $x$ is as in case (iii), then

$\displaystyle x$ $\displaystyle<$ $\displaystyle 1.64\times
10^{6}(\log(4.3\times 10^{8})^{3}\times
3900(\log(2.5x))^{2}\times(\log(0.12(x+1)))^{2}$ $\displaystyle<$
$\displaystyle 5.1\times 10^{13}(\log(2.5x))^{2}(\log(0.12(x+1)))^{2},$

so $x<3\times 10^{20}$.

Thus, $r<4.3\times 10^{8}$ and $x<3\times 10^{20}$. Inequality Eq. (56) gives
that

$\displaystyle\left|\frac{\log{\sqrt{r^{2}+4}}}{\log\alpha}-\frac{x(n+1)-1}{x-1}\right|<\frac{1}{r^{n}(x-1)\log\alpha}<\frac{1}{16(x-1)^{2}},$
(59)

where for the last inequality we used that $r^{n}=r^{2}r^{n-2}\geq 16x$ by
Lemma 13. In particular, the ratio $(x(n+1)-1)/(x-1)$ is a convergent of
$\log{\sqrt{r^{2}+4}}/\log\alpha$. Since $x<3\times 10^{20}<F_{100}$, it
follows that $(x(n+1)-1)/(x-1)=p_{k}/q_{k}$ for some $k\in[0,99]$. So, we
apply Lemma 4 on Eq. (59) with the data:

$\displaystyle M:=3\times
10^{20},\quad\tau:=\frac{\log{\sqrt{r^{2}+4}}}{\log\alpha},\quad
u:=x(n+1)-1,\quad\text{and}\quad v:=x-1.$

With the help of a computer search in Mathematica, we checked all these
possibilities over all the values for $4\leq r\leq 4.3\times 10^{8}$ and found
that $n\leq 46$, which is a contradiction. This computation lasted 6 hours on
a cluster of four 16 GB RAM computers.

###  3.10. The case $r=3$

The case $r=3$ is special since there we don’t know that $\kappa>0$ so some of
the inequalities used for the case $r\geq 4$ do not apply. In the case $n\leq
100$, Lemma 8 gives

$x<3.3\times 10^{6}\times(\log 4)^{2}<6.4\times 10^{6},$

or

$\displaystyle x$ $\displaystyle<$ $\displaystyle 1.38\times 10^{8}\times
100\left(1+\frac{1}{3\log 3}\right)(\log 4)^{2}\left(\log\left(\frac{0.3\times
101(x+1)^{2}}{(\log 4)^{2}}\right)\right),$ $\displaystyle<$ $\displaystyle
3.5\times 10^{10}(\log(16(x+1)^{2}))^{2},$

which gives $x<1.7\times 10^{14}$, or

$\displaystyle x$ $\displaystyle<$ $\displaystyle 1.63\times 10^{6}\times
100\left(1+\frac{1}{3\log 3}\right)(\log
4)^{3}\left(\log\left(\frac{0.12(x+1)}{(\log 4)^{2}}\right)\right)^{2}$
$\displaystyle<$ $\displaystyle 5.7\times 10^{8}\left(0.07(x+1)\right)^{2},$

which gives $x<3.3\times 10^{11}$. Now we can do Baker-Davenport on estimate
Eq. (27) and get better bounds on $x$. In case $n>100$, estimate Eq. (54)
together with Lemma 13 hold and give

$|(m-x(n+1))\log\alpha+(x-1)\log({\sqrt{r^{2}+4}})|<\frac{2.2}{r^{x}}+\frac{1.51x}{\alpha^{2n+2}}<\frac{2.2}{r^{x}}+\frac{1.51}{r^{n+2}}<\frac{1}{3^{\min\\{n-1,x-1\\}}}.$
(60)

We keep the notation $r$ and $\alpha$ although this section only applies to
$r=3$ for which $\alpha=(3+{\sqrt{13}})/2$. Put $\ell:=\min\\{n-1,x-1\\}$. The
lower bound estimate Eq. (58) still applies and gives

$\ell\log 3<-\log|\Gamma_{2}|<195\left(\max\left\\{\log\left(\frac{2.5x}{\log
4}\right),10.5\right\\}\right)^{2}(\log 4)^{2}.$

When $\ell=n-1$, we get

$(n-1)\log 3<375\left(\max\left\\{\log\left(\frac{2.5x}{\log
4}\right),10.5\right\\}\right)^{2}.$

In case the maximum above is $10.5$ we get $x<16000$ and $n<40000$. If the
maximum above is not at $10.5$, we then get

$n<\frac{375}{\log 3}\left(\log\left(\frac{2.5x}{\log
4}\right)\right)^{2}+1<350(\log(2x))^{2}.$

Going via the possibilities (i), (ii), (iii), we get

$\displaystyle x$ $\displaystyle<$ $\displaystyle 3.3\times 10^{6}(\log
4)^{2}<7\times 10^{6};$ $\displaystyle x$ $\displaystyle<$ $\displaystyle
1.38\times 10^{6}\left(350(\log(2x))^{2}\right)\left(1+\frac{1}{3\log
3}\right)(\log 4)^{2}\left(\log\left(\frac{0.3\times 351(\log
2x)^{2}(x+1)^{2}}{(\log 4)^{2}}\right)\right)^{2}$ $\displaystyle<$
$\displaystyle 1.3\times 10^{9}(\log 2x))^{2}(\log(55(x+1)^{2}))^{2},$

which gives $x<2\times 10^{16}$, or finally

$\displaystyle x$ $\displaystyle<$ $\displaystyle 1.63\times
10^{6}(350(\log(2x))^{2})\left(1+\frac{1}{3\log 3}\right)(\log
4)^{3}\left(\log\left(\frac{0.12(x+1)}{(\log 4)^{2}}\right)\right)^{2}$
$\displaystyle<$ $\displaystyle 2\times
10^{9}(\log(2x))^{2}(\log(0.07(x+1)))^{2},$

which gives $x<3.1\times 10^{15}$. So, in all instances, $x<2\times 10^{16}$,
and now

$n<350(\log(2x))^{2}<6\times 10^{5}.$

Since Lemma 13 still applies, it follows that estimate Eq. (60) gives

$\left|\frac{\log{\sqrt{r^{2}+4}}}{\log\alpha}-\frac{x(n+1)-m}{x-1}\right|<\frac{1}{3^{n-1}(x-1)(\log
3)}<\frac{1}{3(x-1)^{2}},$

so again $(x(n+1)-m)/(x-1)=p_{k}/q_{k}$ is a convergent of
$\log{\sqrt{r^{2}+4}}/\log\alpha$ with $x<2\times 10^{16}<F_{80}$, so
$k\in[0,\ldots,16]$. So, everything works fine if $\ell=n-1$.

In case $\ell=x-1$, one gets

$(x-1)\log 3<375\left(\max\left\\{\log\left(\frac{2.5x}{\log
4}\right),10.5\right\\}\right)^{2},$

which gives $x<5\times 10^{4}$. And one wonders how one should finish it off.
We can expand another linear form in logarithms which is small, or we may
recall the following main theorem from [2].

######  Theorem 5.

Assume that $s\not\in\\{1,2,4\\}$ is minimal such that $U_{m}\mid
U_{n+1}^{s}-U_{n}^{s}$. Then $m<20000s^{2}$.

In our instance, since $U_{m}=U_{n}^{x}+U_{n+1}^{x}$, one checks that the
minimal $s$ is exactly $2x$. Thus, $m<80000x^{2}$, and since $m>(n-1)x$ by
estimate (19), we get $n\leq 80000x<4\times 10^{9}$. Thus, $n<4\times 10^{9}$
and $x<5\times 10^{4}$. It is still a large range and we need to reduce it.

We consider the element

$\displaystyle y:=\dfrac{x}{\alpha^{2n}}.$

Lemma 13 together with the fact that $\alpha>r$ implies that

$\displaystyle y<\dfrac{1}{\alpha^{n}},$ (61)

where the last inequality holds for all $n>100$. Now, we write

$\displaystyle
U_{n}^{x}=\dfrac{\alpha^{nx}}{(r^{2}+4)^{x/2}}\left(1-\dfrac{(-1)^{n}}{\alpha^{2n}}\right)^{x},$

and

$\displaystyle
U_{n+1}^{x}=\dfrac{\alpha^{(n+1)x}}{(r^{2}+4)^{x/2}}\left(1-\dfrac{(-1)^{n+1}}{\alpha^{2(n+1)}}\right)^{x}.$

If $n$ is odd, then

$\displaystyle
1<\left(1-\dfrac{(-1)^{n}}{\alpha^{2n}}\right)^{x}=\left(1+\dfrac{1}{\alpha^{2n}}\right)^{x}<e^{y}<1+2y,$

because $y$ is very small. On the other hand, if $n$ is even, then

$\displaystyle
1>\left(1-\dfrac{(-1)^{n}}{\alpha^{2n}}\right)^{x}=\exp\left(x\log\left(1-\dfrac{1}{\alpha^{2n}}\right)\right)^{x}>e^{-2y}>1-2y,$

because $y$ is very small. Thus, the following inequalities hold in both
cases,

$\displaystyle\left|U_{n}^{x}-\dfrac{\alpha^{nx}}{(r^{2}+4)^{x/2}}\right|<\dfrac{2y\alpha^{nx}}{(r^{2}+4)^{x/2}},$

and

$\displaystyle\left|U_{n+1}^{x}-\dfrac{\alpha^{(n+1)x}}{(r^{2}+4)^{x/2}}\right|<\dfrac{2y\alpha^{(n+1)x}}{(r^{2}+4)^{x/2}}.$

Now, we return to (3) and rewrite it as

$\displaystyle\dfrac{\alpha^{m}-\beta^{m}}{(r^{2}+4)^{1/2}}$
$\displaystyle=U_{m}=U_{n}^{x}+U_{n+1}^{x}$
$\displaystyle=\dfrac{\alpha^{nx}}{(r^{2}+4)^{x/2}}+\dfrac{\alpha^{(n+1)x}}{(r^{2}+4)^{x/2}}+\left(U_{n}^{2}-\dfrac{\alpha^{nx}}{(r^{2}+4)^{x/2}}\right)+\left(U_{n+1}^{x}-\dfrac{\alpha^{(n+1)x}}{(r^{2}+4)^{x/2}}\right),$

or

$\displaystyle\left|\dfrac{\alpha^{m}}{(r^{2}+4)^{1/2}}-\dfrac{\alpha^{nx}(1+\alpha^{x})}{(r^{2}+4)^{x/2}}\right|$
$\displaystyle=\left|\dfrac{\beta^{m}}{(r^{2}+4)^{1/2}}+\left(U_{n}^{x}-\dfrac{\alpha^{nx}}{(r^{2}+4)^{x/2}}\right)+\left(U_{n+1}^{x}-\dfrac{\alpha^{(n+1)x}}{(r^{2}+4)^{x/2}}\right)\right|$
$\displaystyle<\dfrac{1}{\alpha^{m}}+\left|U_{n}^{x}-\dfrac{\alpha^{nx}}{(r^{2}+4)^{x/2}}\right|+\left|U_{n+1}^{x}-\dfrac{\alpha^{(n+1)x}}{(r^{2}+4)^{x/2}}\right|$
$\displaystyle<\dfrac{1}{\alpha^{m}}+2y\left(\dfrac{\alpha^{nx}(1+\alpha^{x})}{(r^{2}+4)^{x/2}}\right).$

Multiplying both sides of the above inequality by
$\alpha^{-(n+1)x}(r^{2}+4)^{x/2}$, we obtain that

$\displaystyle\left|\alpha^{m-(n+1)x}(r^{2}+4)^{(x-1)/2}-(1+\alpha^{-x})\right|<\dfrac{(r^{2}+4)^{x/2}}{\alpha^{m+(n+1)x}}+2y(1+\alpha^{-x})<\dfrac{1}{2\alpha^{n}}+3y<\dfrac{3}{\alpha^{n}},$
(62)

so we may divide both sides of it by $1+\alpha^{-x}$ and get

$\left|\alpha^{m-(n+1)x}(r^{2}+4)^{(x-1)/2}(1+\alpha^{-x})^{-1}-1\right|<\frac{3}{\alpha^{n}}.$

Since $n>100$, the left–hand side is small (say smaller than $1/2$), so we can
pass to a logarithmic form and get

$|(m-(n+1)x)\log\alpha+(x-1)\log({\sqrt{r^{2}+4}})-\log(1+\alpha^{-x})|<\frac{6}{\alpha^{n}}.$
(63)

For us, the parameter $x$ is in $[3,50000]$. Given $x$, we have $m<2\times
10^{14}$. So, this is a suitable inequality to apply Baker-Davenport to. To do
so, we rewrite Eq. (63) as

$\displaystyle\left|((n+1)x-m)\dfrac{\log\alpha}{\log\left(\sqrt{r^{2}+4}\right)}-(x-1)+\dfrac{\log(1+\alpha^{-x})}{\log\left(\sqrt{r^{2}+4}\right)}\right|<\dfrac{6}{\alpha^{n}\log\left(\sqrt{r^{2}+4}\right)}.$
(64)

Then, we apply Lemma 5 on Eq. (64) with the data:

$\displaystyle M:=2\times
10^{14},\quad\tau:=\dfrac{\log\alpha}{\log\left(\sqrt{r^{2}+4}\right)},\quad\mu:=\dfrac{\log(1+\alpha^{-x})}{\log\left(\sqrt{r^{2}+4}\right)},\quad
A:=\dfrac{6}{\log\left(\sqrt{r^{2}+4}\right)},\quad B:=\alpha.$

A computer search in Mathematica reveals that $n\leq 94$, which is the final
contradiction. This computations lasted a few hours on a cluster four 16 GB
RAM computers. ∎

## acknowledgements

M. D. was supported by the Austrian Science Fund (FWF) grants: F5510-N26 –
Part of the special research program (SFB), “Quasi-Monte Carlo Methods: Theory
and Applications” and W1230 –“Doctoral Program Discrete Mathematics”. F. L.
was supported by grant RTNUM19 from CoEMaSS, Wits, South Africa. This paper
was written when both authors visited the Max Planck Institute for Mathematics
Bonn, in 2019. They thank this institution for the hospitality and the
fruitful working environment.

## References

  * [1] Yu. Bilu, G. Hanrot, and P. M. Voutier,  Eexistence of primitive divisors of Lucas and Lehmer numbers. With an appendix of M. Mignotte,]  J. Reine Angew. Math. 539 (2001), 75–122.
  * [2] Yu. Bilu, T. Komatsu, F. Luca, A Pizarro-Madariaga, and P. Stănică, On a divisibility relation for Lucas sequences, J. Number Theory 163 (2016), 1–18.
  * [3] R. D. Carmichael,  On the numerical factors of the arithmetic forms $\alpha^{n}\pm\beta^{n}$ Ann. of Math. (2) 15 (1913), 30–70.
  * [4] C. A. Gómez Ruíz and F. Luca, An exponential Diophantine equation related to the sum of powers of two consecutive $k$–generalized Fibonacci numbers,  Colloq. Math. 137 (2014), 171–188.
  * [5] A. Dujella and A. Pethő,  A generalization of a theorem of Baker and Davenport,  Quart. J. Math. Oxford Ser. (2), 49 (1998), 291–306.
  * [6] T. Koshy,  Fibonacci and Lucas Numbers with Applications,  A Wiley-Interscience Publication, 2001.
  * [7] M. Laurent, M. Mignotte, and Yu. Nesterenko,  Formes linéaires en deux logarithmes et déterminants d’interpolation,  J. Number Theory, 55 (1995), 285–321.
  * [8] F. Luca and R. Oyono, An exponential Diophantine equation related to powers of two consecutive Fibonacci numbers,  Proc. Japan Acad. 137 Ser. A (2014), 45–50.
  * [9] M. Mignotte,  A kit for linear forms in three logarithms,  Preprint 2008\.
  * [10] S. E. Rihane, B. Faye, F. Luca, and A. Togbé, An exponential Diophantine equation related to the difference between powers of two consecutive Balancing numbers,  Ann. Math. Inform. 50 (2019), 167–177.
  * [11] S. E. Rihane, B. Faye, F. Luca, and A. Togbé, On the exponential Diophantine equation $P_{n}^{x}+P_{n+1}^{x}=P_{m}$,  Turkish J. Math. 43 (2019), 1640–1649.