Mahadi Ddamulira
email: mddamulira@tugraz.at

Florian Luca
email: florian.luca@wits.ac.za

ON THE EXPONENTIAL DIOPHANTINE EQUATION RELATED TO POWERS OF TWO CONSECUTIVE TERMS OF LUCAS SEQUENCES

Keywords: 2010 Mathematics Subject Classification. 11B39, 11J86 Lucas sequences, Linear forms in logarithms, Baker's method

Let r ≥ 1 be an integer and U := (Un) n≥0 be the Lucas sequence given by U 0 = 0, U 1 = 1, and U n+2 = rU n+1 + Un, for all n ≥ 0. In this paper, we show that there are no positive integers r ≥ 3, x = 2, n ≥ 1 such that U x n + U x n+1 is a member of U.

Introduction

Let r ≥ 1 be an integer and U := (U n ) n≥0 be the Lucas sequence given by U 0 = 0, U 1 = 1, and

U n+2 = rU n+1 + U n (1)
for all n ≥ 0. When r = 1 U coincides with the Fibonacci sequence while when r = 2 U coincides with the Pell sequence. It is well-known that

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

U x n + U x n+1 = 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 ≥ 1 and even the parametric solution m = n + 2 when x = 1 if r = 1. For r = 1 Luca and Oyono [START_REF] Luca | An exponential Diophantine equation related to powers of two consecutive Fibonacci numbers[END_REF] proved that Eq. ( 3) has no positive integer solutions (n, m, x) with n ≥ 2 and x ≥ 3. Rihane et al. [START_REF] Rihane | On the exponential Diophantine equation P x n + P x n+1 = Pm[END_REF] studied Eq. (3) when r = 2 and proved that there is no positive integer solution (n, m, x) of it with x = 2. In the same spirit, Gómez Ruiz and Luca [START_REF] Gómez Ruíz | An exponential Diophantine equation related to the sum of powers of two consecutive k-generalized Fibonacci numbers[END_REF] studied Eq. ( 3) with

U = {F (k) n } n≥-(k-2)
, which is the k-generalized Fibonacci sequence of recurrence

F (k) n = F (k) n-1 + F (k) n-2 + • • • + F (k) n-k
for all n ≥ 2 with the initial conditions

F (k) -(k-2) = F (k) -(k-2) = • • • = F (k) 0 = 0 and F (k) 1
= 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 ≥ 3, n ≥ 2, and x ≥ 1. Another related result involving the balancing numbers was studied by Rihane et al. in [START_REF] Rihane | An exponential Diophantine equation related to the difference between powers of two consecutive Balancing numbers[END_REF].

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 ≥ 3 since the cases r ∈ {1, 2} have been treated already in [START_REF] Luca | An exponential Diophantine equation related to powers of two consecutive Fibonacci numbers[END_REF] and [START_REF] Rihane | On the exponential Diophantine equation P x n + P x n+1 = Pm[END_REF], 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 ≥ 3 and x = 2.

Preliminary Results

2.1. The Lucas sequence. Let (α, β)

:= r + √ r 2 + 4 2 , r - √ r 2 + 4 2 ,
be the roots of the characteristic equation x 2 -rx -1 = 0 of the Lucas sequence U = (U n ) n≥0 . We put ∆ = r 2 + 4 = (α -β) 2 for the discriminant of the above quadratic equation. The Binet formula for the general term of U is given by

U n := α n -β n α -β for all n ≥ 0. ( 4
)
One may prove by induction that the inequality

α n-2 ≤ U n ≤ α n-1 (5)
holds for all positive integers n. It is also easy to show that the inequality

U n U n+1 < 1 r (6)
holds for all n ≥ 2. Indeed, it follows from U n+1 = rU n + U n-1 > rU n for n ≥ 2. At one point of the argument we will need the companion Lucas sequence V := {V n } n≥0 given by V 0 = 2, V 1 = r, and V n+2 = rV n+1 + V n for all n ≥ 0. Its Binet formula is

V n = α n + β n for all n ≥ 0. ( 7
)
There are many relations between members of U and V such as

U 2n = U n V n ; (8)
U 2 n+1 -U n U n+2 = (-1) n ; (9) V 2 n -∆U 2 n = 4(-1) n ; (10)
2U m+n = U m V n + U n V m ; (11) gcd(U n , U m ) = U gcd(m,n) . (12)
We record another one. All such identities follow easily from the Binet formulas Eq. ( 4) and Eq. ( 7) of U and V respectively.

Lemma 1. If n is odd then

U n -1 = U (n-1)/2 V (n+1)/2 if n ≡ 1 (mod 4); U (n+1)/2 V (n-1)/2 if n ≡ 3 (mod 4). ( 13
)
Both sequences U and V can be extended to negative indices either by allowing n to be negative in the Binet formulas Eq. ( 4) and [START_REF] Bravo | Powers of two in generalized Fibonacci sequences[END_REF] or simply by using the recurrence relation to extend U to negative indices via U -n = -rU -(n-1) + U -(n-2) for all n ≥ 1. The same applies to V. All the above formulas given in Eq. ( 8), [START_REF] Gómez Ruíz | An exponential Diophantine equation related to the sum of powers of two consecutive k-generalized Fibonacci numbers[END_REF], [START_REF] Dujella | A generalization of a theorem of Baker and Davenport[END_REF], [START_REF] Sánchez | Linear combinations of factorials and s-units in a binary recurrence sequence[END_REF], and [START_REF] Laurent | Formes linéaires en deux logarithmes et déterminants d'interpolation[END_REF] 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 [START_REF] Koshy | Fibonacci and Lucas Numbers with Applications[END_REF].

Lemma 2. Let {U n (r)} n≥0 ⊆ Z[r] be the sequence of polynomials defined by U 0 (r) = 0, U 1 (r) = 1, and

U n+2 (r) = rU n+1 (r) + U n (r), for all n ≥ 0.
Then,

U n (r) = 0≤k≤n k ≡n (mod 2) n+k-1 2 k r k . ( 14
)
Note that the summation range above is only over these k ∈ [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 | U n if n is even and r | U n -1 if n is odd.
2.2. Logarithmic height. Let η be an algebraic number of degree d with minimal primitive polynomial over the integers

a 0 x d + a 1 x d-1 + • • • + a d = a 0 d i=1 (x -η (i) ),
where the leading coefficient a 0 is positive and the η (i) 's are the conjugates of η. The logarithmic height of η is given by

h(η) := 1 d log a 0 + d i=1 log max{|η (i) |, 1} .
In particular, if η = p/q is a rational number with gcd(p, q) = 1 and q > 0, then h(η) = log max{|p|, q}.

The following are some of the properties of the logarithmic height function h(•), which will be used in the next sections of this paper without reference:

h(η ± γ) ≤ h(η) + h(γ) + log 2, h(ηγ ±1 ) ≤ h(η) + h(γ), h(η s ) = |s|h(η) (s ∈ Z). (15)
2.3. Linear forms in logarithms and continued fractions. The following result on linear forms in three logarithms is due to Mignotte [START_REF] Mignotte | A kit for linear forms in three logarithms[END_REF]. 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 γ 1 , γ 2 , and γ 3 , which are all real, greater than 1 and multiplicatively independent. Put

D := [Q(γ 1 , γ 2 , γ 3 ) : Q].
Let b 1 , b 2 , b 3 be coprime positive integers and consider

Γ := b 2 log γ 2 -b 1 log γ 1 -b 3 log γ 3 .
Put

d 1 := gcd(b 1 , b 2 ) = b 1 b 1 = b 2 b 2 , d 3 := gcd(b 3 , b 2 ) = b 2 b 2 = b 3 b 3 .
Let A 1 , A 2 , and A 3 be real numbers such that

A i ≥ max{4, 4.296 log γ i + 2Dh(γ i )}, i = 1, 2, 3, and
Ω := A 1 A 2 A 3 ≥ 100. Put b := b 1 A 2 + b 2 A 1 b 3 A 2 + b 2 A 3
and log B := max 0.882 + log b , 10 D .

Then, either

log |Γ| > -790.95ΩD 2 (log B) 2 ,
or one of the following conditions holds: (i) there exist two positive integers r 0 and s 0 such that

r 0 b 2 = s 0 b 1 with r 0 ≤ 5.61A 2 (D log D) 1 3
and

s 0 ≤ 5.61A 1 (D log D) 1 3 ;
(ii) there exist integers r 1 , s 1 , t 1 , and t 2 , with r 1 s 1 = 0, such that

(t 1 b 1 + r 1 b 3 )s 1 = r 1 b 2 t 2 , gcd(r 1 , t 1 ) = gcd(s 1 , t 2 ) = 1
which also satisfy

|r 1 s 1 | ≤ 5.61δA 3 (D log D) 1 3 , |s 1 t 1 | ≤ 5.61δA 1 (D log D) 1 3 , |r 1 t 2 | ≤ 5.61δA 2 (D log D) 1 3
, where δ := 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 γ 1 and γ 2 be real algebraic numbers which are positive and let

D := [Q(γ 1 , γ 2 ) : Q]. Let b 1 ,
b 2 be nonzero integers, let B 1 and B 2 be real numbers larger than 1 such that

log B i ≥ max h(γ i ), | log γ i | D , 1 D , for i = 1, 2,
and put

b = |b 1 | D log B 2 + |b 2 | D log B 1 . Let Γ := b 1 log γ 1 + b 2 log γ 2 . ( 16
)
The following result of Laurent, Mignotte, and Nesterenko is Corollary 2 in [START_REF] Laurent | Formes linéaires en deux logarithmes et déterminants d'interpolation[END_REF].

Theorem 3. With the above notations assuming furthermore that γ 1 and γ 2 are multiplicatively independent we have

log |Γ| > -24.34D 4 max log b + 0.14, 21 D , 1 2
2 log B 1 log B 2 . ( 17
)
Note that the fact that Γ = 0 is already guaranteed by the condition that γ 1 and γ 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 τ be an irrational number, p 0 /q 0 , p 1 /q 1 , p 2 /q 2 , . . . be the sequence of convergents of the continued fraction expansion of τ 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, . . . , N } the inequality

τ - u v > 1 (a(M ) + 2)v 2 ,
holds for all pairs (u, v) of positive integers with 0 < v < M . Furthermore, if

τ - u v < 1 2v 2 , then u/v = p k /q k for some k ≥ 0.
For a nonhomogeneous linear form in two integer variables we use a slight variation of a result due to Dujella and Pethő (see [START_REF] Dujella | A generalization of a theorem of Baker and Davenport[END_REF], Lemma 5a). For a real number X, we write X := min{|X -n| : n ∈ 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 τ such that q > 6M , and A, B, µ be some real numbers with A > 0 and B > 1. Furthermore, let ε := µq -M τ q . If ε > 0, then there is no solution to the inequality

0 < |uτ -v + µ| < AB -w
in positive integers u, v, and w with u ≤ M and w ≥ log(Aq/ε) log B .

Proof of Theorem 1

3.1. The cases n = 1 or x = 1. We assume that n ≥ 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

U m = 1 + r x . (18)
In particular, U m ≡ 1 (mod r). Lemma 3 shows that m ≡ 1 (mod 2) and now Lemma 1 shows that

r x = U m -1 = U (m-δ)/2 V (m+δ)/2
where δ ∈ {±1}, δ ≡ m (mod 4).

We now recall the Primitive Divisor Theorem of Carmichael [START_REF] Carmichael | On the numerical factors of the arithmetic forms α n ± β n Ann[END_REF] (see [START_REF] Yu | Eexistence of primitive divisors of Lucas and Lehmer numbers. With an appendix of M. Mignotte[END_REF] for the most general statement) for the sequence U. It states that if > 12, there is a prime factor p of U which is primitive in the sense that p U k for any positive k < . So, assume m + δ ≥ 14. Since m + δ is even we have U m+δ = U (m+δ)/2 V (m+δ)/2 by the formula Eq. ( 8). Since U m+δ has a primitive prime factor p, the primitive prime p must be a divisor of V (m+δ)/2 , which in turn must divide r = U 2 , a contradiction. Thus, m + δ ≤ 12, therefore m ≤ 13. It thus follows that

r x = U m -1 < α m-1 ≤ α 12 < (r 2 + 4) 6 ,
so, if x ≥ 13, then 3 x-12 ≤ r x-12 < (1 + 4/r 2 ) 6 ≤ (1 + 4/3 2 ) 6 < 9.1, which gives x ≤ 14. Thus, m ≤ 13, x ≤ 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. [START_REF] Rihane | On the exponential Diophantine equation P x n + P x n+1 = Pm[END_REF] 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 ≥ 2 and x ≥ 3.

3.2.

Calculations when n ∈ [2, 100] and x ∈ [START_REF] Yu | Eexistence of primitive divisors of Lucas and Lehmer numbers. With an appendix of M. Mignotte[END_REF]100]. Using the equation Eq. ( 3) and the inequality Eq. ( 5), we get

α (n-1)x < U x n+1 < U x n + U x n+1 = U m ≤ α m-1 ,
and

α m-2 < U m = U x n + U x n+1 < (U n + U n+1 ) x < U x n+2 < α (n+1)x .
From the above inequalities, we get the following result which we record for future reference.

Lemma 6. The inequalities

(n -1)x + 1 < m < (n + 1)x + 2 (19)
hold for all x ≥ 3 and n ≥ 2.

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

    0≤k≤n k ≡n(mod 2) n+k-1 2 k r k     x +     0≤k≤n+1 k ≡n+1(mod 2) n+k 2 k r k     x = 0≤k≤m k ≡m(mod 2) m+k-1 2 k r k . ( 20
)
Assume first that n is even. Then Eq. (20) becomes

n 2 r + n+2 2 3 r 3 + • • • x + 1 + n+2 2 2 r 2 + n+4 2 4 r 4 + • • • x = 1 + m+1 2 2 r 2 + m+3 2 3 r 4 + • • • , which is equivalent to n+2 2 2 r 2 x + n+4 2 4 r 4 x + • • • ≡ m+1 2 2 r 2 + m+3 2 3 r 4 + • • • (mod r x ). ( 21
)
The above relation implies that

r min{x,4}-2 m+1 2 2 -x n+2 2 2 . (22)
Similarly, when n is odd, one is led to the analogous divisibility relation

r min{x,4}-2 m+1 2 2 -x n+1 2 2 . ( 23
)
So, fixing n ∈ [2, 100] and x ∈ [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 ≥ 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 ≥ 2, x ≥ 3 and max{n, x} > 100.

3.3.

A small linear form in three logs. We rewrite equation Eq. ( 3) as

α m α -β -U x n+1 = U x n + β m α -β . ( 24
)
Dividing both sides of the above equation by U x n+1 and using the inequality Eq. ( 6), we obtain

α m (α -β) -1 U -x n+1 -1 = U n U n+1 x + β m (α -β)U x n+1 < 2 U n U n+1 x < 2 r x . (25)
Put

Λ := α m (α -β) -1 U -x n+1 -1 and Γ := m log α -log(α -β) -x log U n+1 . (26)
We observe that Λ = e Γ -1, where Λ and Γ are given by (26). Since |Λ| ≤ 2/27, we have that e |Γ| ≤ 27/25 and using the inequality (25) we obtain

|Γ| = m log α -log( r 2 + 4) -x log U n+1 ≤ e |Γ| |e |Γ| -1| ≤ 27|Λ| 25 < 2.2 r x . ( 27
)
We record the above inequality for future reference.

Lemma 7. With Γ given by formula Eq. (26), inequality Eq. ( 27) holds.

We want to apply Theorem 2 with the following data:

γ 1 := α -β = r 2 + 4, γ 2 := α, γ 3 := U n+1 , b 1 := 1, b 2 := m, b 3 := x.
We need to check that γ 1 , γ 2 , and γ 3 are multiplicatively independent. This we do in the next subsection.

3.4.

Checking that γ 1 , γ 2 , γ 3 are multiplicatively independent. Well, assume they are not and let i, j, k be integers not all zero such that

γ i 1 γ j 2 γ k 3 = 1.

Squaring and rearranging the above relation we get

γ 2j 2 = (γ 2 1 ) -i γ -2k 3 ∈ Q. However, γ 2j
2 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 γ 3 = γ -i/k 1 . In particular, all prime factors of U n+1 are prime factors of ∆ := r 2 +4. But this is also contemplated by the Primitive Divisor Theorem of Carmichael since primes dividing ∆ are not considered primitive. In particular, U n+1 does not have primitive prime factors so n + 1 ≤ 12. In fact, Theorem C in [START_REF] Yu | Eexistence of primitive divisors of Lucas and Lehmer numbers. With an appendix of M. Mignotte[END_REF] together with Table 1 there show that either n + 1 ∈ {2, 3, 4, 6} or n + 1 ∈ {5, 12} but in this last case, the only such Lucas sequence 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 ∈ {2, 3, 6}. Further, for each prime p let z(p) be the index of appearance of p in U defined as the smallest positive integer k such that p | U k . This always exists for our sequence U since α is a quadratic unit. It has the additional property that if is a positive integer then p | U if and only if z(p) | . It is also well-known and easy to prove that if p | ∆, then z(p) = p. Since also z(p) | n + 1 and n + 1 ∈ {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 ≥ 3 and the equation simplifies to 2 a-2 = r 2 0 + 1. Hence, r 0 is odd, so r 2 0 ≡ 1 (mod 8), therefore 2 r 2 0 + 1, which leads to a = 3, r 0 = 1, which gives r = 2, is not our case. Hence, indeed γ 1 , γ 2 , γ 3 are multiplicatively independent.

3.5. Applying Theorem 2. Since γ 1 , γ 2 , γ 3 ∈ Q(α), we have D = 2. We also have

r < α < r 2 + 4 < r + 1.
So, we bound the heights of α and √ r 2 + 4 in terms or log(r + 1). Since

h(γ 1 ) = h(α -β) = 1 2 log(r 2 + 4) < log(r + 1), h(γ 2 ) = 1 2 log α < 1 2 log(r + 1), and
h(γ 3 ) = log U n+1 < log α n = n log α < n log(r + 1),
we can take A 1 := 8.296 log(r + 1), A 2 := 6.296 log(r + 1), A 3 := 8.296n log(r + 1).

Thus Ω := A 1 A 2 A 3 > 433n(log(r + 1)) (28)

In the above chain of inequalities, we used the fact that m < (n + 1)x + 2 < 2nx (see inequality Eq. ( 19)) since n ≥ 2 and x ≥ 3. Further, putting log B := max 0.882 + log 0.12mx (log(r + 1)) 2 , 5 , we have that either the inequality log |Γ| > -790.95 × 434n(log(r + 1)) 3 × 2 2 × (log 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 B = 5, then

x < mx < e 5-0.882 0.12 (log(r + 1)) 2 < 512(log(r + 1)) 2 .

(30)

On the other hand, if log B > 5, then

log B := 0.882 + log 0.12mx (log(r + 1)) 2 < log 0.3mx (log(r + 1)) 2 , ( 31
)
where in the above inequality we used the fact that e 0.882 × 0.12 < 0.3. Thus, we get that log |Γ| > -790.95 × 434n(log(r + 1)

) 3 × 2 2 × log 0.3mx (log(r + 1)) 2 2 > -1.374 × 10 6 n(log(r + 1)) 3 log 0.3mx (log(r + 1)) 2 2 .
Comparing this inequality with Eq. ( 27), we get that x log r -log 2.2 < 1.374 × 10 6 n(log(r + 1)) 3 log 0.3mx (log(r + 1)) (33)

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

x < 1.38 × 10 6 n 1 + 1 r log r (log(r + 1)) 2 log 0.3(n + 1)(x + 1) 2 (log r) 2 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

m = s 0 < 5.61A 1 (D log D) 1/3 < 5.61 × 8.296 × (2 log 2) 1/3 log(r + 1) < 5.61 × 8.296 × (2 log 2) 1/3 log(r + 1)
< 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 = 0 and

(t 1 b 1 + r 1 b 3 )s 1 = r 1 b 2 t 2 , 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 , gcd(r 1 , t 1 ) = gcd(s 1 , t 2 ) = 1.
Reducing the above equation modulo r 1 we get t 1 s 1 ≡ 0 (mod r 1 ) and since gcd(t 1 , r 1 ) = 1, we get that r 1 | s 1 . So, we put s 1 = r 1 s 1 and simplify both sides of the above equation by r 1 to get

(t 1 + r 1 x)s 1 = mt 2 .
Consequently, for us δ = gcd(r 1 , s 1 ) = r 1 . Hence,

|t 1 s 1 | < 5.61A 1 (D log D)
|r 1 s 1 | < 5.61A 3 (D log D) 1/3 < 5.61 × 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 | ≤ |t 1 | < 52 log(r + 1),
which is the same as (35). Assume next that t 2 = 0. We return to inequality Eq. ( 27) and multiply both sides by t 2 and get

|mt 2 log γ 2 -t 2 log γ 1 -xt 2 log γ 3 | < 2.2|t 2 | r
x . We substitute mt 2 by t 1 s 1 + (r 1 s 1 )x inside the left-hand side above and then the left-hand side above becomes log γ

t1s 1 2 γ t2 1 + x log γ r1s 1 2 γ t2 3 < 2.2|t 2 | r x . (37)
Inequality ( 37) is of the form

|Γ 1 | < 2.2|t 2 | r x , where Γ 1 := log η 1 + x log η 2 , (38)
and

η 1 := γ t1s 1 2 γ t2 1 , η 2 := γ r1s 1 2 γ t2 3 .
We check that η 1 and η 2 are multiplicatively independent. If not, there are integers i, j not both zero such that η i 1 η j 2 = 1. This gives γ

t1s 1 2 γ t2 1 i γ r1s 1 2 γ t2 3 j = 1.
If i = 0, this gives a multiplicative dependence among γ 1 , γ 2 , γ 3 with the exponent of γ 1 being the nonzero integer -t 2 i, a contradiction with the main result of Subsection 3.4. Thus, i = 0, so j = 0, and we get again a multiplicative relation among γ 2 , γ 3 (the exponent of γ 3 being the nonzero integer -t 2 j), which is the same contradiction. Thus, indeed η 1 and η 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 [START_REF] Matveev | An explicit lower bound for a homogeneous rational linear form in the logarithms of algebraic numbers II[END_REF], Since | log γ i |/2 ≤ h(γ i ) holds for i = 1, 2, 3, it follows, by the absolute value inequality, that the same inequalities are satisfied by the numbers | log η i |/2 for i = 1, 2. Thus, since D = 2, we can take log B 1 := 66(log(r + 1)) 2 , log B 2 := 66n(log(r + 1)) 2 .

h
We bound

1 2 log B 2 + x 2 log B 1 = 1 132(log(r + 1)) 2 1 n + x < x + 1 132(log(r + 1)) 2 .
Hence, we take b :=

x + 1 132(log(r + 1)) 2 . Now Theorem 3 gives log |Λ| > -24.34 × 2 4 (max{log b + 0.14, 10.5}) 2 × (66(log(r + 1)) 2 ) × (66n(log(r + 1)) 2 )

> -1.627 × 10 6 n(log(r + 1)) 4 M 2 , ( 39
)
where x + 1 88(log(r + 1)) 2 .

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

x log r -log(2.2|t 2 |) < 1.627 × 10 6 n(log(r + 1)) 4 log
x + 1 88(log(r + 1)) The first summand in the right-hand side is < 5 for all r ≥ 3. Using inequality Eq. (32), we get that

x < 1.63 × 10 6 n 1 + 1 r log r (log(r + 1)) 3 log x + 1 88(log(r + 1)) 2 2 . ( 41
)
To summarise, either we are in the first situation of Theorem 2 and log B = 5, in which case inequality Eq. (30) holds, or log 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:

x < 3.3 × 10 6 (log(r + 1)) 2 ;

(42)

x < 1.38 × 10 6 n 1 + 1 r log r (log(r + 1)) 2 log 0.3(n + 1)(x + 1) 2 (log(r + 1)) 2 2 ;

(43)

x < 1.63 × 10 6 n 1 + 1 r log r (log(r + 1)) 3 log 0.12(x + 1) (log(r + 1)) 2 2 .

(44) 3.6. More inequalities in terms of n and x. We put

κ := nx + 1 -m (45)
Later we shall show that κ 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) κ = 1; (ii) If κ = 2 and n ≥ 3 then x ≥ r max{2,n-3} ; (iii) If κ ≥ 3, then κ ≥ n/2.
Proof. (i). If κ = 1, then m = nx. So the equation (3) becomes

U x n + U x n+1 = U nx . If p is prime dividing U n (which exists since n > 1), then p | U x
n and p | U n | U nx , so from the above equation we get p | U n+1 , a contradiction since gcd(U n , U n+1 ) = U gcd(n,n+1) = 1 by relation [START_REF] Koshy | Fibonacci and Lucas Numbers with Applications[END_REF].

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

U x n + U x n+1 = U nx-1 . In particular, U nx-1 -U x n+1 ≡ 0 (mod U 2 n ).
We study this congruence. In what follows for three algebraic integers a, b, c, we write a ≡ b (mod c) if (a -b)/c is an algebraic integer. Write

U n = α n -β n α -β as α n = β n + √ ∆U n .
Then

α nx = (β n + √ ∆U n ) x ≡ β nx + xβ n(x-1) √ ∆U n (mod ∆U 2 n ). Thus, U nx-1 = α nx α -1 -β nx-1 √ ∆ ≡ (β nx + xβ n(x-1) √ ∆U n )α -1 -β nx-1 α -β (mod √ ∆U 2 n ) ≡ β nx α -1 -β nx β -1 α -β + xβ n(x-1) α -1 U n (mod U 2 n ) ≡ β nx + xβ n(x-1) α -1 U n (mod U 2 n ). On the other hand, U x n+1 = α n+1 -β n+1 √ ∆ x ≡ (β n + √ ∆U n )α -β n+1 √ ∆ x (mod U 2 n ) ≡ (β n + U n α) x (mod U 2 n ) ≡ β nx + xβ n(x-1) αU n (mod U 2 n ). Thus, U nx-1 -U x n+1 ≡ (β nx + xβ n(x-1) α -1 U n ) -(β nx + xβ n(x-1) αU n ) (mod U 2 n ) ≡ xβ n(x-1) (α -1 -α)U n (mod U 2 n ) ≡ -xβ n(x-1 rU n (mod U 2 n ).
In the last step above, we used the fact that α

-1 -α = -β -α = -r. Since the expression U nx-1 -U x n+1 is divisible by U 2 n , we get that U 2 n | β n(x-1) xrU n . Since β is a unit, we get that U n | 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 | x, which gives x ≥ r 2 + 1 > r 2 . For n = 4, we have that U 4 = r(r 2 + 2) divides rx, so r 2 + 2 | x giving x ≥ r 2 + 2 > r 2 .
Finally, for n ≥ 5, we have that U n > α n-2 > r n-2 and so x ≥ U n /r ≥ r n-3 . This proves (ii).

(iii) We may assume that n ≥ 7, otherwise the conclusion is trivial. Recall that V n = α n + β n . Relations Eq. ( 9) and ( 10) are

U 2 n+1 -U n U n+2 = (-1) n and V 2 n -∆U 2 n = 4(-1) n . In particular, U 2 n+1 ≡ (-1) n (mod U n ) and V 2 n ≡ 4(-1) n (mod U n ).
We also use the fact that U -m = (-1) m-1 U m , V -m = (-1) m V m and relation Eq. [START_REF] Sánchez | Linear combinations of factorials and s-units in a binary recurrence sequence[END_REF] which is

2U m+n = U m V n + U n V m .
Armed with these facts, writing m = nx -(κ -1) and

U x n + U x n+1 = U nx-(κ-1)
, we multiply both sides of the above equation by 2 and write

2U x n + 2U x n+1 = 2U nx-(κ-1) = U nx V -(κ-1) + V nx U -(κ-1)
. We square both sides of the above equation and reduce it modulo U n taking into account that U n | U nx and V 2 nx ≡ 4(-1) nx (mod U nx ) ≡ 4(-1) nx (mod U n ), and get 4(-1 9) (with n + 1 := κ -1). Since n ≥ 7 and U is not the Fibonacci sequence, it follows that U n has a primitive divisor p, which must divide one of U κ-2 or U κ . Thus, z(p) = n divides one of κ -2 or κ, so we get κ ≥ n, which is a better conclusion than the one desired. If κ -1 is even and

) nx ≡ 4(U 2 n+1 ) x (mod U n ) ≡ (U nx V -(κ-1) + V nx U -(κ-1) ) 2 (mod U n ) ≡ V 2 nx U 2 -(κ-1) (mod U n ) ≡ V 2 nx U 2 κ-1 (mod U n ) ≡ 4(-1) nx U 2 κ-1 (mod U n ). Thus, U n | 4(U 2 κ-1 -1). The right-hand side is nonzero since κ > 2. If κ -1 is odd, then 4(U 2 κ-1 -1) = 4U κ-2 U κ by relation Eq. (
U n | 2(U 2 κ-1 -1), we then get α n-2 < U n < 2U 2 κ-1 < r(α κ-1 ) 2 < α 2κ-1 , so 2κ -2 ≥ n -2, therefore κ ≥ n/2.
The above argument was based on the fact that r ≥ 2. In particular, if r ≥ 4, then the same argument gives again that α n-2 < U n < 4U 2 κ-1 < r(α κ-1 ) 2 < α 2κ-1 , so κ ≥ n/2. So, the only case when the above arguments fail are when r = 3 and 4 | 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 | U n | 4(U 2 κ-1 -1). But U κ-1 is a multiple of r (since κ -1 is even), so U 2 κ-1 -1 is coprime to r. Thus, r | 4, which is false. This finishes the proof of (iii).

Corollary 4. If κ > 0, then x > n/2. Proof. By Lemma 9, if κ = 2, then x ≥ r min{2,n-3} ≥ 3 min{2,n-3} > n/2 for any n ≥ 2. If κ ≥ 3, then 1 + nx -m = κ ≥ n/2, which leads to 1 + nx -n/2 ≥ 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 α and log √ r 2 + 4 in terms of log r. With z := 4/r 2 , we have |z| ≤ 4/9 and log(1

+ z) = z + ζ 1 , |ζ 1 | ≤ k≥2 z k k = z 2 2 1 + (2/3)z + (2/4)z 2 + • • • .
The expression in parenthesis above is smaller than

c 1 := 1 + (2/3)(4/9) + (2/4)(4/9) 2 + • • • = (-4/9 -log(1 -4/9)) × 2 × (9/4) 2 .
Hence,

log r 2 + 4 = log r + 2 r 2 + ζ 1 2 := log r + 2 r 2 + ζ, |ζ| = |ζ 1 | 2 < c 1 4 z 2 = 4c 1 r 4 < 5.81 r 4 . For α, we write log α = log r + log 1 2 + 1 4 + 1 r 2 = log r + log(1 + z 1 ), z 1 := 1 4 + z 4 - 1 2 . Note that |z 1 | ≤ 1/r 2 . Thus, log(1 + z 1 ) = z 1 + ζ 2 , |ζ 2 | ≤ |z 1 | 2 2 (1 + (2/3)|z 1 | + • • • ) ≤ c 2 2r 4
, where by the previous arguments,

c 2 = (-λ 0 -log(1 -λ 0 )) × 2 × λ -2 0 , with λ 0 := 1 4 + 1 9 - 1 2 .
It remains to expand z 1 . For this, we have

z 1 = 1 2 ( √ 1 + z -1) = 1 2 z 2 + ζ 3 , |ζ 3 | ≤ k≥2 k 1/2 z k . Since | k 1/2 | ≤ 1/4 for all k ≥ 1, it follows that |ζ 3 | ≤ 1 4 k≥2 z k = z 2 4(1 -z) ≤ 36 5r 4 .
Hence,

log α = log r + z 4 + ζ 2 + ζ 3 2 =: log r + 1 r 2 + ζ , |ζ | < c 2 2 + 36 10 1 r 2 < 3.64 r 4 .
The following estimate is the main result of this section.

Lemma 11. If r ≥ 4, then κ > 0. Furthermore,

x > κ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 α n+1 α -β 1 - β α n+1 = (n + 1) log α -log( r 2 + 4) + ζ , (49)
where

ζ = log 1 - β α n+1 . Since β = -α -1 , it follows that |β/α| = 1/α 2 . Thus, |ζ | ≤ 1 α 2n+2   1 + k≥1 1 k(α 2n+2 ) k   ≤ 1 α 2n+2 1 + 1 2(1 -1/α 2n+2 ) < 1.51 α 2n+2 , ( 50
)
where for the last inequality we used the fact that α > r ≥ 3 and n ≥ 2. Inserting estimates Eq. ( 46) and Eq. ( 47) together with Eq. ( 49) into inequality Eq. ( 27), we get

|Γ| = m log α -log( r 2 + 4) -x((n + 1) log α -log( r 2 + 4) + ζ ) = (m -x(n + 1)) log α + (x -1) log( r 2 + 4) -xζ = (m -x(n + 1)) log r + 1 r 2 + ζ + (x -1) log r + 2 r 2 + ζ -xζ = (m -nx -1) log r + (m -nx -1) + (x -1) r 2 + (m -x(n + 1))ζ + (x -1)ζ + xζ .
We recognise the coefficient of log r as the number we denoted -κ in (45). Using inequality Eq. ( 27), we get

-κ log r + -κ + (x -1) r 2 < 2.2 r x + |m -x(n + 1)||ζ | + |x -1||ζ| + x|ζ |. Inequality Eq. (19) shows that m -x(n + 1) ∈ [-2x + 2, 2]. In particular, |m -x(n + 1)| ≤ 2(x -1).
We thus get, by estimates Eq. ( 46) and Eq. ( 47) together with Eq. ( 49), that

-κ log r + -κ + (x -1) r 2 < 4 r x + 7.28(x -1) r 4 + 5.81(x -1) r 4 + 1.51x r 6 .
Since x ≥ 3 and r ≥ 3, we get that the last term satisfies

1.51x r 6 ≤ 1.51 × (3/2) 3 2 (x -1) r 4 < 0.26(x -1) r 4 .
Hence,

-κ log r + -κ + (x -1) r 2 < 2.2 r x + 13.35(x -1) r 4 . ( 51
)
Assume that κ ≤ 0. We then get that Thus, if r ≥ 5 or r = 4 and x ≥ 4, then κ > 0 and now Lemma 9 applies. We will show at the end of this proof that κ ≥ 0 for (r, x) = (4, 3) as well. Multiplying both sides of estimate (51) by r 2 , we get

x -1 r 2 ≤
| -κ(r 2 log r + 1) + (x -1)| < (x -1) 13.35 r 2 + 2.2 r x-2 (x -1)
.

Hence,

κ(r 2 log r + 1) < (x -1) 1 + 13.35 r 2 + 2.2 r x-2 (x -1) ≤ (x -1) 1 + 5 r ,
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 κ = 3n + 1 -m ≥ -2. So, the only instances in which κ ≤ 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 3 n + U 3 n+1 < U 3n+1 .
Using the Binet formula Eq. ( 4), this is implied by

α -1 1 + 1 α 6n 3 + α 2 1 + 1 α 6n+6 3 < ∆ 1 - 1 α 6n+3 , with α = 2 +
√ 5 and ∆ = 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 ≥ 1. Thus, κ ≥ 2 for r = 4 as well.

3.8. The case n ≤ 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 ≤ 100, a case which has already been treated.

We prove the following result.

Lemma 12. When n ≤ 100, we have r ≤ 1.5 × 10 6 .

Proof. We assume r > 10 6 . Then x > κr 2 log r/1.01 ≥ 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 ≤ 1.01 × 3.3 × 10 6 (log(r + 1)) 2 ,
which gives r < 5500, a contradiction. Assume we are in case (ii). Then

x + 1 < 1.38 × 10 6 × 1.001(log(r + 1)) 2 log 0.3(n + 1)(x + 1) 2 (log(r + 1)) 2 . ( 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 > nr 2 log r 2.02 > nr 2 log(r + 1) log r 2.02 log(r + 1) > 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 × 10 6 log(r + 1) × 1.001 log(0.3n 2 (n + 1)y 2 ) 2 < 1.39 × 10 6 log(r + 1)(2 log y + log(30030)) 2 .

We look at the function f (y) := y (2 log y + log(30030)) 2 . Its derivative is 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 × 10 6 log(r + 1), and y > r 2 /2.03, it follows that f (r 2 /2.03) < 1.39 × 10 6 log(r + 1). This gives r 2 < 1.39 × 2.03 × 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 × 10 6 (log(r + 1)) 2 (log(0.12n 2 y 2 )) 2 ≤ 1.64 × 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 × 1.64 × 10 6 (log(r + 1)) 2 (2 log(r 2 /2.03) + log( 12)) 2 , and this gives r < 1.5 × 10 6 .

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

x < 3.3 × 10 6 (log(1.5 × 10 6 )) 2 < 7 × 10 8 ; x < 1.39 × 10 6 × 100(log(1.5 × 10 6 )) 2 log(0.3 × 101(x + 1) 2 ) 2 < 3.7 × 10 10 log(30.3(x + 1)) 2 ,
x < 1.64 × 10 6 × 100 × (log(1.5 × 10 6 )) 3 (log(0.12(x + 1)) 2 < 6.5 × 10 11 log(0.12(x + 1)) 2 .

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

x log U n+1 log α -m + log √ r 2 + 4 log α < 2.2 r x log α . (53)
Then, we apply Lemma 5 on Eq. ( 53) with the data:

M := 3 × 10 17 , τ := log U n+1 log α , µ := log √ r 2 + 4 log α , A := 2.2 log α
, and B := r.

A computer search in Mathematica reveals that x ≤ 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

|Γ| = |m log α -log( r 2 + 4 -x((n + 1) log α -log( r 2 + 4 + ζ )| < 2.2 r x , which implies, via estimate Eq. (50), that |(m -x(n + 1)) log α + (x -1) log( r 2 + 4)| < 2.2 r x + 1.51x α 2n+2 . (54)
If r ≥ 4 then κ > 0, so by Lemma 9, we have κ ≥ 2. If κ ≥ 3, then

x ≥ κ(r 2 log r + 1) 1 + 5/r > n4 2 log 4 4.5 > 2n + 2.
The same conclusion holds for κ = 2 since then x ≥ r min{2,n-3} ≥ 4 min{2,n-3} ≥ 2n + 2 for all n ≥ 2. We thus get

|(m -x(n + 1)) log α + (x -1) log( r 2 + 4)| < 4 r 2n+2 + 1.51x α 2n+2 < 1.51x + 2.2 α 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 κ = 2 cannot occur for r ≥ 4 provided that n > 100.

Proof. Assume x ≥ r n-2 . We use the bounds given by Lemma 8 on x. In case (i), we get

r 99 ≤ r n-2 ≤ 3.3 × 10 6 (log(r + 1)) 2 .
The function y → y 99 /(log(y + 1)) 2 is increasing for all y ≥ 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 × 10 6 n 1 + 1 r log r (log(r + 1)) 2 log 0.3(n + 1)(x + 1) 2 (log(r + 1)) 2

2

.

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

x < 1.8 × 10 6 (log(r + 1)) 2 log 0.3(n + 1)(x + 1) 2 (log(r + 1)) 2

2

.

If x ≤ n, then we get r n-2 ≤ n for r ≥ 3 and n ≥ 101, which is false. Thus, n < x, so we may use 0.3(n + 1) < n < x + 1 to get

x + 1 < 1.8 × 10 6 n(log(r + 1)) 2 (log((x + 1) 3 )) 2

< 1.8 × 3 2 × 10 6 (log(r + 1)) 2 (log(x + 1)) 2 < 1.7 × 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 ≥ r 99 ≥ 3 99 . Hence, the above inequality should hold for x + 1 replaced by r n-2 , and that gives r n-2 ≤ 1.7 × 10 7 (log(r + 1)) 2 (log(r n-2 )) 2 < 1.7 × 10 7 n 2 (log(r + 1)) 4 .

Since r n/3 ≥ 3 n/3 > n holds for n > 100, we get that r n/3-2 < 1.7 × 10 7 (log(r + 1)) 4 , so r 95 ≤ r n-6 < 1.7 × 10 7 (log(r + 1)) 2 3 < 5 × 10 21 (log(r + 1)) 12 .

The function y → y 95 /(log(y + 1)) 6 is increasing for y ≥ 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 ≥ 4, then inequality Eq. (55) leads to

|(m -x(n + 1)) log α + (x -1) log( r 2 + 4)| < 1 r n . ( 56
)
We put Γ 2 := (x -1) log r 2 + 4 -((n + 1)x -m) log α.

We apply Theorem 3 to find a lower bound on log |Γ 2 | with the data:

t := 2, γ 1 := r 2 + 4, γ 2 := α, b 1 := x -1, b 2 := m -(n + 1)x. ( 57
)
Since γ 1 , γ 2 ∈ Q(α), we take again K := Q(α) with degree D := 2. The fact that γ 1 and γ 2 are multiplicatively independent has already been checked. We take max h(γ 1 ),

| log γ 1 | 2 , 1 2 = 1 2 log(r 2 + 4) < log(r + 1) := log B 1 ,
and

max h(γ 2 ), | log γ 2 | 2 , 1 2 = 1 2 log α < 1 2 log(r + 1) := log B 2 .
Thus,

b := |b 1 | D log B 2 + |b 2 | D log B 1 = x -1 2 log(r + 1) + |(n + 1)x -m| log(r + 1) < 2.5x log(r + 1)
,

where we used the fact that m -(n +

) 58
We want an upper bound on r. So, assume r ≥ 10 6 . If log((2.5x)/log(r + 1)) < 10.5, then

x < e 10.5 log(r + 1) 2.5 < 15000 log(r + 1). where we used the fact that r ≥ 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 ≤ x ≤ 3.3 × 10 6 (log(r + 1)) In the above inequalities we used the fact that r ≥ 10 .

Putting again y := (x + 1)/ log(r + 1), we get y < 1.39 × 10 6 × 196 × (log(r + 1)) 2 log(2.5y) 2 (3 log y) 2 < 2.46 × 10 9 (log(2.5y)) 4 .

The function y → y/(log(2.5y) 4 is increasing for our range for y > 50r 2 > 50 × 10 16 , so we get that the above inequality should hold by replacing y by 50r 2 . Thus, 50r 2 < 2.46 × 10 9 (log(r + 1)) 2 (log(2.5 × 50r 2 )) 4 , so r < 2.6 × 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 × 10 6 (log(r + 1)) 3 196 log(r + 1) log 2.5x log(r + 1) 2 log 0.12(x + 1) (log(r + 1)) 2 2 , so y < 3.3 × 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 × 10 9 (log(r + 1)) 3 (log(2.5 × 50r 2 ))(log(0.12 × 50r 2 )) 2 , so r < 4.3 × 10 8 .

To summarise, we have proved the following. Having bounds for r it is easy to find bounds for x. For example, n < 195 log(r + 1)(log(2.5x))

√ r 2 + 4 log α - x(n + 1) -1 x -1 < 1 r n (x -1) log α < 1 16(x -1) 2 , (59)
where for the last inequality we used that r n = r 2 r n-2 ≥ 16x by Lemma 13. In particular, the ratio (x(n + 1) -1)/(x -1) is a convergent of log √ r 2 + 4/ log α. Since x < 3 × 10 20 < F 100 , it follows that (x(n + 1) -1)/(x -1) = p k /q k for some k ∈ [0, 99]. So, we apply Lemma 4 on Eq. ( 59) with the data:

M := 3 × 10 20 , τ := log √ r 2 + 4 log α , u := x(n + 1) -1, and v := x -1.
With the help of a computer search in Mathematica, we checked all these possibilities over all the values for 4 ≤ r ≤ 4.3 × 10 8 and found that n ≤ 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 κ > 0 so some of the inequalities used for the case r ≥ 4 do not apply. In the case n ≤ 100, Lemma 8 gives

x < 3.3 × 10 6 × (log 4) 2 < 6.4 × 10

|(m -x(n + 1)) log α + (x -1) log( r 2 + 4)| < 2.2 r x + 1.51x α 2n+2 < 2.2 r x + 1.51 r n+2 < 1 3 min{n-1,x-1} . (60)
We keep the notation r and α although this section only applies to r = 3 for which α = (3 + √ 13)/2. Put := min{n - m x -1 < 1 3 n-1 (x -1)(log 3) < 1 3(x -1) 2 , so again (x(n + 1) -m)/(x -1) = p k /q k is a convergent of log √ r 2 + 4/ log α with x < 2 × 10 16 < F 80 , so k ∈ [0, . . . , 16]. So, everything works fine if = n -1.

In case = x -1, one gets (x -1) log 3 < 375 max log 2.5x log 4 , 10.5 2 , which gives x < 5 × 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 [START_REF] Yu | On a divisibility relation for Lucas sequences[END_REF].

Theorem 5. Assume that s ∈ {1, 2, 4} is minimal such that U m | U s n+1 -U s n . Then m < 20000s 2 . In our instance, since U m = U x n + U x n+1 , 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 ≤ 80000x < 4 × 10 9 . Thus, n < 4 × 10 9 and x < 5 × 10 4 . It is still a large range and we need to reduce it.

We consider the element y := x α 2n . Lemma 13 together with the fact that α > r implies that

y < 1 α n , (61)
where the last inequality holds for all n > 100. Now, we write x < e y < 1 + 2y, because y is very small. On the other hand, if n is even, then

U x n = α nx (r 2 + 4) x/
1 > 1 - (-1) n α 2n x = exp x log 1 - 1 α 2n
x > e -2y > 1 -2y, because y is very small. Thus, the following inequalities hold in both cases,

U x n -
α nx (r 2 + 4) x/2 < 2yα nx (r 2 + 4) x/2 , and U x n+1 -α (n+1)x (r 2 + 4) x/2 < 2yα (n+1)x (r 2 + 4) x/2 . Now, we return to (3) and rewrite it as α m -β m (r 2 + 4) 1/2 = U m = U x n + U x n+1 = α nx (r 2 + 4) x/2 + α (n+1)x (r 2 + 4) x/2 + U 2 n -α nx (r 2 + 4) x/2 + U x n+1 -α (n+1)x (r 2 + 4) x/2 , or α m (r 2 + 4) 1/2 -α nx (1 + α x ) (r 2 + 4) x/2 = β m (r 2 + 4) 1/2 + U x n -α nx (r 2 + 4) x/2 + U x n+1 -α (n+1)x (r 2 + 4) x/2 < 1 α m + U x n -α nx (r 2 + 4) x/2 + U x n+1 -α (n+1)x (r 2 + 4) x/2 < 1 α m + 2y

α nx (1 + α x ) (r 2 + 4) x/2 .
Multiplying both sides of the above inequality by α -(n+1)x (r 2 + 4) x/2 , we obtain that α m-(n+1)x (r 2 + 4) (x-1)/2 -(1 + α -x ) < (r 2 + 4) x/2 α m+(n+1)x + 2y(1 + α -x ) <

1 2α n + 3y < 3 α n , (62)
so we may divide both sides of it by 1 + α -x and get α m-(n+1)x (r 2 + 4) (x-1)/2 (1 + α -x ) -1 -1 < 3 α 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 α + (x -1) log( r 2 + 4) -log(1 + α

-x )| < 6 α n . ( 63
)
For us, the parameter x is in [START_REF] Yu | Eexistence of primitive divisors of Lucas and Lehmer numbers. With an appendix of M. Mignotte[END_REF]50000]. Given x, we have m < 2 × 10 14 . So, this is a suitable inequality to apply Baker-Davenport to. To do so, we rewrite Eq. ( 63 A computer search in Mathematica reveals that n ≤ 94, which is the final contradiction. This computations lasted a few hours on a cluster four 16 GB RAM computers.

(η 1 )

 1 ≤ |t 1 s 1 |h(γ 2 ) + |t 2 |h(γ 1 ) ≤ (52 log(r + 1))(1/2 log(r + 1)) + (40 log(r + 1)) log(r + 1) = 66(log(r + 1)) 2 ; h(η 2 ) ≤ |r 1 s 1 |h(γ 2 ) + |t 2 |h(γ 3 ) ≤ 52n log(r + 1)(1/2 log(r + 1)) + (40 log(r + 1))(n log(r + 1)) = 66n(log(r + 1)) 2 .

  M := max{log b + 0.4, 10.5}. In case M = 10.5, we get b < e 10.5-0.4 < 24400, which gives x + 1 < 24400 × 132(log(r + 1)) 2 < 3.3 × 10 6 (log(r + 1)) 2 . (40) Finally, suppose that M = log b + 0.4 = log(e 0.4 b ) < log(1.5b ) = log

Lemma 10 .

 10 For r ≥ 3, we have the following approximations:log r 2 + 4 = log r + 2 r 2 + ζ, |ζ| < α = log r + 1 r 2 + ζ , |ζ | <

Lemma 14 .

 14 If r ≥ 4, then r < 4.3 × 10 8 .

  3 > 100 since n ≥ 2 and r ≥ 3. Then,

	b =	1 6.296 log(r + 1)	+	m 8.296 log(r + 1)	x 6.296 log(r + 1)	+	m 8.296n log(r + 1)
	<	m (log(r + 1)) 2	1 6.296	+	1 8.296	x log(r + 1)	1 6.296	+	2 8.296
	<	0.12mx (log(r + 1)) 2 .

  Since x > nr 2 log r/(2 + 10/r) ≥ 101r 2 log r/2.02 = 50r 2 log r, we get

		50r 2 log r ≤ x ≤ 15000(log(r + 1)),
	so
	r 2 <	15000 50	log(r + 1) log r	< 300 × 1.01 = 303,
	so r ≤ 17, a contradiction.
	Assume next that log(2.5x/ log(r + 1)) > 10.5. We then get
	log |Γ 2 | > -195(log(r + 1)) 2 log	2.5x log(r + 1)	2	.
	Comparing the above inequality with estimate Eq. (56), we get
	n log r < 195(log(r + 1)) 2 log	2.5x log(r + 1)	2	,
	so
	n < 195	log(r + 1) log r	log(r + 1) log	log(r + 1) 2.5x	2
	< 196 log(r + 1) log	2.5x log(r + 1)

2

,

  6 . The function y → 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 × 50r 2 ) 2 and gives r < 50, a contradiction.

	1) log	2.5x log(r + 1)	2	log	log(r + 1) (x + 1)	3	2

Thus, n < (x + 1)/ log(r + 1). Since 0.3(n + 1) < n, we conclude that x + 1 < 1.39 × 10 6 (log(r + 1)) 2 196 log(r +

  2 < 195 log(4.3 × 10 8 )(log(2.5x)) 2 < 3900(log(2.5x)) 2 . × 10 20 . Thus, r < 4.3 × 10 8 and x < 3 × 10 20 . Inequality Eq. (56) gives that log

	If x is in case (ii), then
	x < 1.39 × 10 6 (log(4.3 × 10 8 ) 2 (3900(log(2.5x)) 2 )(log(0.3 × 3900(log(2.5x)) 2 (x + 1) 2 )) 2
	< 2.2 × 10 12 (log(2.5x)) 2 (log(1200(x + 1) 2 log(2.5x))) 2 ,
	which gives x < 5 × 10 19 . Finally, if x is as in case (iii), then
	x < 1.64 × 10 6 (log(4.3 × 10 8 ) 3 × 3900(log(2.5x)) 2 × (log(0.12(x + 1))) 2
	< 5.1 × 10 13 (log(2.5x)) 2 (log(0.12(x + 1))) 2 ,
	so x < 3
	Next, if x is in case (i), then

x < 3.3 × 10 6 (log(r + 1)) 2 < 3.3 × 10 6 (log(4.3 × 10 8 )) 2 < 1.4 × 10 9 .

  × 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

						6 ,
	or
	x < 1.38 × 10 8 × 100 1 +	1 3 log 3	(log 4) 2 log	0.3 × 101(x + 1) 2 (log 4) 2	,
	< 3.5 × 10 10 (log(16(x + 1) 2 )) 2 ,
	which gives x < 1.7 × 10 14 , or
	x < 1.63 × 10 6 × 100 1 +	1 3 log 3	(log 4) 3 log	(log 4) 2 0.12(x + 1)	2
	< 5.7 × 10 8 (0.07(x + 1))	2 ,
	which gives x < 3.3

  1, x -1}. The lower bound estimate Eq. (58) still applies and gives log 3 < -log |Γ 2 | < 195 max logIn 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 Going via the possibilities (i), (ii), (iii), we get x < 3.3 × 10 6 (log 4) 2 < 7 × 10 6 ; × 10 9 (log 2x)) 2 (log(55(x + 1) 2 )) 2 , which gives x < 2 × 10 16 , or finally x < 1.63 × 10 6 (350(log(2x))

	When = n -1, we get
		(n -1) log 3 < 375 max log	2.5x log 4	, 10.5
		n <	375 log 3	log	2.5x log 4	2	+ 1 < 350(log(2x)) 2 .
	x < 1.38 × 10 6 350(log(2x)) 2 1 +	1 3 log 3	(log 4) 2 log	(log 4) 2 0.3 × 351(log 2x) 2 (x + 1) 2	2
	< 1.3 2 ) 1 +	1 3 log 3	(log 4) 3 log	0.12(x + 1) (log 4) 2
	Since Lemma 13 still applies, it follows that estimate Eq. (60) gives
	log	√ log α r 2 + 4	-	x(n + 1) -
							2.5x log 4	, 10.5	2	(log 4) 2 .

2 . 2 < 2 × 10 9 (log(2x)) 2 (log(0.07(x + 1))) 2 , which gives x < 3.1 × 10 15 . So, in all instances, x < 2 × 10 16 , and now n < 350(log(2x)) 2 < 6 × 10 5 .

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.


Jean-Christophe Filliâtre

Léon Gondelman

Cláudio Lourenço

Andrei Paskevich

Mário Pereira

Simão Melo De Sousa

Aymeric Walch

A Toolchain to Produce Veried OCaml Libraries

In this paper, we present a methodology to produce veried OCaml libraries, using the GOSPEL specication language and the Why3 program verication tool. First, a formal behavioral specication of the library is written in OCaml/GOSPEL, in the form of an OCaml module signature extended with type invariants and function contracts. Second, an implementation is written in WhyML, the programming language of Why3, and then veried with respect to the GOSPEL specication. Finally, WhyML code is automatically translated into OCaml source code by Why3. Our methodology is illustrated with two examples: rst, a small binary search function; then, a union-nd data structure that is part of a larger OCaml veried library.

Introduction

Development of formally veried programs can be done in various ways. Perhaps, the most widespread approach consists in augmenting an existing mainstream programming language with specication annotations (contracts, invariants, etc.) and proving the conformance of the code to the specication, possibly passing through an intermediate language. Examples include VeriFast [START_REF] Jacobs | VeriFast: A powerful, sound, predictable, fast verier for C and Java[END_REF] and KeY [START_REF]Deductive Software Verication -The KeY Book -From Theory to Practice[END_REF] for Java, Frama-C [START_REF] Kirchner | Frama-c: A software analysis perspective[END_REF] and VCC (via Boogie) [START_REF] Dahlweid | VCC: Contract-based modular verication of concurrent C[END_REF][START_REF] Barnett | Boogie: A Modular Reusable Verier for Object-Oriented Programs[END_REF] for C, GNATprove (via Why3) for Ada/SPARK [START_REF] Carré | SPARKan annotated Ada subset for safety-critical programming[END_REF][START_REF] Filliâtre | Why3 where programs meet provers[END_REF]. This approach can end up being quite challenging, since real-life programming languages, not designed with verication in mind, have to be encoded into a suitable program logic. Such an encoding is a non-trivial task, and it may result in rather complex verication conditions, that are dicult to discharge by both automated and interactive provers.

Alternatively, one can proceed in the opposite direction: develop formally veried code in a dedicated verication language/environment and then translate it to an existing programming language, producing a correct-by-construction program. One can cite PVS [START_REF] Owre | PVS: A prototype verication system[END_REF], Coq [START_REF] Coq | The Coq Proof Assistant Reference Manual Version V8.9[END_REF], B [START_REF] Abrial | The B-Book, assigning programs to meaning[END_REF], F [START_REF] Swamy | Dependent types and multi-monadic eects in F*[END_REF], Dafny [START_REF] Rustan | Dafny: An automatic program verier for functional correctness[END_REF], and Why3 [START_REF] Filliâtre | Why3 where programs meet provers[END_REF] as examples of this approach. It works well for self-contained programs, such as

This research was partly supported by the French National Research Organization (project VOCAL ANR-15-CE25-008). CompCert [START_REF] Leroy | A formally veried compiler back-end[END_REF], but is less suitable when the veried code is supposed to be integrated into a larger development. We cannot expect the original source code, developed in a specic verication framework, to be accessible to a common programmer and the automatically generated code is typically a clobbered mess.

In this paper, we propose a way to reconcile the two approaches, avoiding both of the aforementioned disadvantages. Our work takes place in the setting of a larger project, named VOCaL (for Veried OCaml Library) [START_REF] Charguéraud | VOCAL A Veried OCaml Library[END_REF], whose ambition is to provide a mechanically veried library of ecient general-purpose data structures and algorithms, written in the OCaml language. One of the main lines of work in the VOCaL project is the design of GOSPEL [START_REF] Charguéraud | GOSPEL providing OCaml with a formal specication language[END_REF], a behavioral specication language for OCaml, similar to what JML is for Java [START_REF] Burdy | An overview of JML tools and applications[END_REF], or ACSL for C [START_REF] Baudin | ACSL: ANSI/ISO C Specication Language, version 1.4[END_REF]. The VOCaL project also combines the use of three verication tools, namely Coq, CFML [START_REF] Charguéraud | Characteristic formulae for the verication of imperative programs[END_REF], and Why3. This paper focuses on the last.

Our approach to producing veried OCaml code consists in splitting the verication and implementation process into several steps. The workow is given in In the following sections, we explain this workow in detail using the examples of a binary search function (Sec. 2 and 3) and of a union-nd library (Sec. 4). Section 5 gives an overview of the other OCaml modules veried with Why3 in the VOCaL project. Source les for all the OCaml modules mentioned in this paper are available from https://vocal.lri.fr/.

Why3 and WhyML

Why3 is a tool for deductive program verication [START_REF] Filliâtre | Why3 where programs meet provers[END_REF]. It uses its own programming and specication language, called WhyML, which is largely inspired by OCaml syntax. The theoretical foundation of Why3 is the weakest-precondition calculus and a custom type system with regions to handle mutable heap-allocated data [START_REF] Filliâtre | A pragmatic type system for deductive verication[END_REF]. As a programming language, WhyML can be seen as a subset of OCaml with support for exceptions, algebraic types, type polymorphism, and restricted higher-order (side-eect-free functional arguments). The program annotations (function contracts, loop invariants, assertions, etc.) are written in a rich logical language that reuses the data types of programs and features pattern matching, recursive and inductive denitions, as well as higher-order functions. An important feature of WhyML is so-called ghost code which is a part of program code that serves exclusively to facilitate specication and proof, and cannot inuence the actual computations [START_REF] Filliâtre | The spirit of ghost code[END_REF]. For example, complex data structures in WhyML would often feature ghost elds that contain the logical model of the structure.

This allows us to specify the program functions that manipulate such a data type in terms of a simple mathematical model, without referring to the details of the implementation.

Let us illustrate the use of Why3 on the simple example of a binary search function. It can be specied and implemented in WhyML as follows:

let rec binary_search (cmp: 'a -> 'a -> int63) (a: array 'a) (lo hi: int63) (v: 'a) : int63 requires { is_pre_order cmp } requires { 0 <= lo <= hi <= length a } requires { forall i j. lo <= i <= j < hi -> cmp a

[i] a[j] <= 0 } ensures { lo <= result < hi /\ cmp a[result] v = 0 } raises { Not_found -> forall i. lo <= i < hi -> cmp a[i] v <> 0 } variant { hi -lo } = if lo >= hi then raise Not_found; let mid = lo + (hi -lo) / 2 in let c = cmp a[mid] v in if c < 0 then binary_search cmp a (mid + 1) hi v else if c > 0 then binary_search cmp a lo mid v else mid
The rst two lines show the type signature of the function binary_search. The functional parameter cmp must be a total stateless and eect-free function, so that we can use it in specication annotations. Type int63 denotes the 63-bit signed integers and is distinguished from type int that represents unbounded mathematical integers. The values of range types like int63 are implicitly coerced to int inside specication annotations.

After the type signature comes the function contract. The clauses requires correspond to the preconditions: the functional parameter cmp is required to implement a total pre-order (the sign of the return value indicates the result of the comparison); the range lo..hi must lie inside the array bounds; the array must be ordered within that range. The clause ensures describes the postcondition associated to a normal (i.e., non-exceptional) termination: the return value of type int63, named result, must be a valid array index where the sought value v is stored. The clause raises describes the exceptional postcondition: if binary_search raises exception Not_found, then v does not occur in the array between lo and hi. Finally, the last clause, variant, is not part of the contract, but helps Why3 to prove the termination: with each recursive call, the value of the variant must strictly decrease with respect to some well-founded order.

The code of binary_search is a rather idiomatic OCaml code. When we run Why3 on this program, verication conditions are generated to prove the following properties: all function calls respect the preconditions of the callee (this includes showing that all operations over bounded integers do not produce overows and that all array accesses are made within bounds); all recursive function calls make the value of the variant decrease; the postconditions are met both for normal and exceptional termination.

Why3 uses multiple automated and interactive provers (including Alt-Ergo, CVC4, Z3, E, Coq, and Isabelle) to discharge the proof obligations. Moreover, the user can apply various transformations, such as goal splitting, case analysis, and denition unfolding, during a Why3 interactive verication session in order to simplify proof tasks before sending them to the background provers. For example, the above implementation of binary search is proved automatically by CVC4 in a matter of seconds after one application of goal splitting.

Why3 supports automated translation of WhyML code to OCaml. An important part of this translation is removal of ghost code and ghost data. Once ghost code and specication annotations are eliminated, Why3 produces an OCaml source le. The program symbols and types which are not implemented inside WhyML code (and are axiomatized instead) are translated to their OCaml counterparts via a so-called driver: a text le that maps WhyML symbols to fragments of OCaml code. Drivers are part of the trusted base of Why3: an incorrect translation would result in a program whose behaviour is dierent from that of the veried WhyML code and will not necessarily respect the contract. In the example above, the types int63 and array, as well as standard operations over them, are mapped to the corresponding OCaml types and operations. The resulting OCaml code is practically identical to the WhyML source.

GOSPEL and its Translation to WhyML

The specication language GOSPEL [START_REF] Charguéraud | GOSPEL providing OCaml with a formal specication language[END_REF] was developed in the context of the VO-CaL project. It extends the syntax of OCaml .mli interface les with behavioral specications, written as specially formatted OCaml comments. GOSPEL is not tied to any particular verication tool. Instead, the methodology of VOCaL considers GOSPEL as a common frontend specication language for dierent verication tools, that either verify OCaml code directly (e.g., CFML) or can produce correct-by-construction OCaml code (e.g., Why3 or Coq).

Here is the GOSPEL specication for our binary_search function: A notable dierence with the WhyML specication from the previous section is clause checks, which describes a precondition that is expected to be checked during execution. When such a precondition is violated, the OCaml implementation must raise the OCaml built-in exception Invalid_argument. Contrary to JML or SPARK, GOSPEL annotations are not meant to be executable: they may contain unbounded quantiers, abstract logical functions, etc. It is up to the veried OCaml implementation to fulll the provided contract, including the runtime checks.

Although the semantics of GOSPEL is given in terms of Separation Logic [START_REF] Charguéraud | GOSPEL providing OCaml with a formal specication language[END_REF],

the specication language itself is kept simple, without explicit Separation Logic operators. Instead, GOSPEL adopts a number of reasonable conventions, such as separation of function parameters and return values, and full ownership transmission from the caller to the callee and back. This is done intentionally, in order to make the language accessible to a larger audience of OCaml programmers.

Incidentally, this also simplies translation from GOSPEL to WhyML, which adheres to the same conventions [START_REF] Filliâtre | A pragmatic type system for deductive verication[END_REF].

We have extended Why3 with a new input format for GOSPEL. The type and function declarations are translated to corresponding WhyML declarations.

A special treatment is provided for checks clauses: for each function foo whose contract contains a clause checks φ, Why3 produces the declarations of two WhyML functions, foo and unsafe_foo, where the former contains an exceptional postcondition raises { Invalid_argument -> ¬φ } and the latter contains a precondition requires { φ }. The latter function is deemed unsafe because it trusts the caller to respect the precondition φ, whereas the former implements a defensive runtime check. A similar practice already exists in OCaml, e.g., Array.unsafe_get. Unsafe functions are perfectly safe when called from veried code, since precondition must be satised, and provide a better performance.

Why3 can generate proof obligations to establish that a given WhyML implementation conforms to a given WhyML specication translated from GOSPEL.

In our case, we can show that our implementation of binary search from Sec. 2 corresponds to the declaration of function unsafe_binary_search (where the checks clause is translated as a WhyML precondition).

Example: Union-Find

We now describe a more complex example, taken from the VOCaL library. This is an OCaml module implementing a union-nd data structure, with the following API (borrowed from [START_REF] Charguéraud | Verifying the correctness and amortized complexity of a union-nd implementation in separation logic with time credits[END_REF]):

type 'a elem (* type of the elements *) val make: 'a -> 'a elem (* a singleton class *) val find: 'a elem -> 'a elem (* the representative *) val eq: 'a elem -> 'a elem -> bool (* in the same class? *) val union: 'a elem -> 'a elem -> unit (* merge two classes *)

In this API, a value of type 'a is attached to each equivalence class. Our actual implementation includes the access and update functions to manipulate this value. For the sake of brevity, we do not discuss this functionality in the paper.

Specication. We start with a GOSPEL specication. In order to give a specication to the functions above, we need a logical representation of the global state of the union-nd data structure. This logical representation takes the form of a set of all elements, together with a function selecting a canonical element in each equivalence class:

(*@ type 'a uf mutable model dom: 'a elem set mutable model rep: 'a elem -> 'a elem invariant forall x. mem x dom -> rep (rep x) = rep x invariant forall x. mem x dom -> mem (rep x) dom *)

Notice that type uf is declared inside a GOSPEL annotation and not as an OCaml type. Consequently, it will only be available for specication or as a type of ghost parameters. The elds dom and rep are declared mutable to reect the possible changes in the state of the union-nd structure. The two invariants ensure that the set dom is indeed partitioned by the relation to have the same canonical representative given by rep.

We are now in position to provide a specication to each OCaml function above. Let us use make and find as examples.

val make: 'a -> 'a elem (*@ e = make These examples involve many aspects not described in this paper, due to lack of space. We describe some of them, briey:

One module, PriorityQueue, implements mutable priority queues on top of another module, Vector, which implements resizable arrays. The proof is performed in a modular way: the Why3 proof of PriorityQueue only makes use of the GOSPEL specication for Vector, but not of its implementation.

Modules PriorityQueue and PairingHeap are OCaml functors, i.e., modules parameterized by a module. This is the idiomatic way in OCaml to provide types and functions as parameters (here, a type of elements equipped with a comparison function). From GOSPEL's point of view, there is no dierence between the specication of a parameter module and that of a toplevel module. From Why3's point of view, there is no dierence between verifying a module B that uses another module A or that is parameterized with a module A. The main dierence lies in the translation from Why3 to OCaml, which must produce an actual OCaml functor.

The veried module PriorityQueue has been integrated into Why3 source code. It is not used in the trusted part of Why3, but only in some heuristic algorithm that matches former proof attempts with new verication conditions. In this way, there is no circularity in the proof of PriorityQueue.

Two of the modules involve arithmetic computations for which it is not obvious to prove the absence of arithmetic overow (the rank in UnionFind and a list length in ZipperList). We use a Why3 library providing a protected integer type with a restricted set of operations to solve that issue [START_REF] Clochard | How to avoid proving the absence of integer overows[END_REF].

The GOSPEL specication, OCaml code, and Why3 proof for all these modules is available from https://vocal.lri.fr/. The CFML tool [START_REF] Charguéraud | Characteristic formulae for the verication of imperative programs[END_REF] implements another approach to the verication of OCaml programs using Coq. It goes the other way around, turning an OCaml program into a characteristic formula, that is an expression of its semantics into a higherorder separation logic embedded in Coq. CFML provides Coq tactics to help the user carry out proofs eciently. Examples of recent applications of CFML include a veried implementation of hash tables [START_REF] Pottier | Verifying a hash table and its iterators in higher-order separation logic[END_REF] and verication of the correctness and amortized complexity of a union-nd library [START_REF] Charguéraud | Verifying the correctness and amortized complexity of a union-nd implementation in separation logic with time credits[END_REF]. Contrary to the CFML proof, ours is fully automatic but we only treat functional correctness and not the complexity bounds.

Surprisingly, program verication has seldom been applied to libraries of signicant size. A remarkable exception is the verication of the EielBase2 containers library [START_REF] Polikarpova | A fully veried container library[END_REF], performed with the AutoProof system [START_REF] Tschannen | Autoproof: Auto-active functional verication of object-oriented programs[END_REF]. It is our purpose to continue using and improving our methodology to grow our veried library to a size comparable to that of EielBase2. However, we do not focus specically on the verication of containers, but also on general-purpose algorithms, e.g., our union-nd implementation.

Conclusion. We proposed a new workow to produce correct-by-construction

OCaml programs. It builds upon the existing tool Why3, with the addition of the following contributions: a specication language for OCaml, called GOSPEL;

a tool to translate it to WhyML; a technique to build memory models for mutable recursive OCaml types; an enhanced extraction mechanism for Why3, with support for OCaml functors; a practical validation with the proof of nine non-trivial OCaml modules.

Fig. 1 .

 1 Fig. 1. The workow.

Fig. 1 :

 1 Fig. 1: solid rectangles represent user-written les, and dashed rectangles represent automatically generated les. First, we start with a GOSPEL specication le: an OCaml .mli interface le where OCaml declarations are augmented with specication annotations, such as function contracts (pre-and postconditions) and type invariants. GOSPEL annotations are written as OCaml comments, and thus ignored by the OCaml compiler. Our framework parses and type checks this le and automatically generates a corresponding Why3 input le, in which allannotations are translated into WhyML, the specication and programming language of Why3. Second, we provide a veried WhyML implementation of the declared operations. This means that, in addition to implementing and verifying a WhyML program, we also establish its correctness with respect to the speci-

  val binary_search: ('a -> 'a -> int) -> 'a array -> int -> int -> 'a -> int (** Search for value [v] in array [a], between indices [lo] inclusive and [hi] exclusive, using comparison function [cmp]. Returns an index where [v] occurs, or raises [Not_found] if no such index exists. *) (*@ result = binary_search cmp a lo hi v requires is_pre_order cmp checks 0 <= lo <= hi <= Array.length a requires forall i j. lo <= i <= j < hi -> cmp a.(i) a.(j) <= 0 ensures lo <= result < hi && cmp a.(result) v = 0 raises Not_found -> forall i. lo <= i < hi -> cmp a.(i) v <> 0 *) The le begins with a standard OCaml function declaration, together with an informal ocamldoc comment. Then follows the formal specication, enclosed in a special comment starting with `(*@'. The rst line of the specication gives names to the function parameters and to its return value. Wherever possible, GOSPEL uses OCaml syntax for primitive operations (e.g., Boolean connectives and array access).

  [uf: 'a uf] v modifies uf ensures not (mem e (dom (old uf))) ensures dom uf = add e (dom (old uf)) ensures rep uf = (rep (old uf))[e <-e] *) val find: 'a elem -> 'a elem (*@ r = find [uf: 'a uf] e requires mem e (dom uf) modifies uf ensures dom uf = dom (old uf) ensures rep uf = rep (old uf) ensures r = rep uf e *) For the purpose of the specication, make and find receive an extra parameter uf of type 'a uf. Square brackets identify it as a ghost parameter. The modifies clause in the function contract accounts for the modication of the union-nd data structure (caused by path compression in the case of find). The term old uf refers to the state of the structure at the beginning of the function call. Veried Implementation. The next step is to implement and verify the union-nd data structure. The OCaml implementation we target is based on the following data types: type 'a content = Link of 'a elem | Root of int * 'a and 'a elem = 'a content ref Each element is a mutable reference which can be in one of two states: either it is a canonical element (Root), with a rank of type int and a value of type 'a; or it points (Link) to another element in the same equivalence class. This type denition cannot be used as is in WhyML, which does not support recursive mutable types. The solution in Why3 is to resort to an explicit memory model, that is a set of types and operations to model the heap, pointers, allocation, and memory access. We translate the OCaml types above into the following WhyML types type loc_ref 'a type content 'a = Link (elem 'a) | Root int63 'a with elem 'a = loc_ref (content 'a) where loc_ref 'a is an abstract immutable type to represent locations of OCaml's heap-allocated references of type ref. The contents of the heap is modeled with another WhyML type type mem_ref 'b = private {mutable refs: loc_ref 'b -> option 'b} where non-allocated locations are mapped to None, and each allocated location is mapped to Some c for some value c of type 'b. Instead of modeling a single global heap, we adopt an approach of small heaps, i.e., local chunks of memory, which are passed as ghost arguments to heap-manipulating functions [23, Chapter 5]. For instance, a reference is updated using the following function: val set_ref (ghost mem: mem_ref 'b) (l: loc_ref 'b) (c: 'b): unit requires { mem.refs l <> None } writes { mem } ensures { mem.refs = (old mem.refs)[l <-Some c] } Once this memory model is built, we can implement and verify the unionnd data structure. In particular, we have to implement the data type uf. It is a record data type that contains, in addition to the elds dom and rep, the contents of the memory: type uf 'a = { memo: mem_ref (content 'a); ... } As declared in the interface, all union-nd functions receive a ghost parameter of type uf and then exploit it to perform read/write operations on memory: let rec find (ghost uf: uf 'a) (x: elem 'a) : elem 'a = match get_ref uf.memo x with | Root _ _ -> x | Link y -> let rx = find uf y in set_ref uf.memo x (Link rx); rx endHere, the call to set_ref accounts for path compression. Once we have implemented all operations, we prove that they conform to the GOSPEL specication written in the .mli le and translated to WhyML by our tool.

Fig. 2 .

 2 Fig. 2. For each OCaml module, column spec shows the number of lines in the .mli le and column code shows the number of lines in the WhyML implementation and proof. Column #VCs shows the total number of verication conditions. All of them were discharged automatically using the combined eort of Alt-Ergo, CVC4, and Z3.

  Translation to OCaml. The last step consists in translating WhyML to OCaml.

		module	spec code #VCs
		UnionFind	71 176	92 union-nd
		Vector	142 285	63 resizable arrays
		PriorityQueue 56 290 219 mutable priority queues
		PairingHeap	43 244	66 persistent priority queues
		ZipperList	65 150	54 zipper data structure for lists
		Arrays	43 126 104 e.g., binary search, binary sort
		Mjrty	11 35	37 Boyer&Moore's majority
		RingBuffer	44 94	61 circular arrays
		CountingSort	19 80 128 array counting sort
			Fig. 2. Veried OCaml Modules.
	5	The VOCaL Project: The State of the Library
	We have used our approach to verify several other OCaml modules, listed in
	We extend the standard driver of Why3 with a custom driver le for our memory
	model, as follows:
	module UnionFind.Mem
		syntax type loc_ref "%1 ref"
		syntax val set_ref "%1 := %2"
		...
	We do not provide a translation for type mem_ref, since it is only used for ghost
	parameters. For the same reason, function set_ref only receives two parameters
	in the translated code. Such a le must be written with care, as it is clearly part
	of the trusted base. In particular, we trust OCaml references to have the same
	semantics as the one described in our memory model.

  The veried C compiler CompCert[START_REF] Leroy | A formally veried compiler back-end[END_REF] and the static analyzer Verasco[START_REF] Jourdan | A formally-veried C static analyzer[END_REF] are two notable large-scale examples of veried OCaml programs.Both are implemented in the Coq proof assistant and translated to OCaml afterwards using Coq extraction mechanism[START_REF] Sozeau | Coq coq correct! verication of type checking and erasure for coq, in coq[END_REF]. It is worth pointing out that Coq has a mechanism to replace certain symbols by OCaml code at extraction time, in a way very similar to our driver substitution mechanism.

	6	Related Work and Conclusion
	Related Work.

Acknowledgments. We are grateful to the anonymous reviewers of a previous submission for their helpful comments and suggestions. We also thank all the members of the VOCaL project for fruitful discussions.