Introduction
For a fixed integer c c c , Pillai’s equation asks for all pairs of representations
c = x − y = x 1 − y 1 , ( x , y ) ≠ ( x 1 , y 1 ) , c = x-y = x_1-y_1,\qquad(x,y)\ne(x_1,y_1), c = x − y = x 1 − y 1 , ( x , y ) = ( x 1 , y 1 ) ,
where x , x 1 x,x_1 x , x 1 range over one sequence and y , y 1 y,y_1 y , y 1 over another. The problem originates with Pillai’s 1936–1937 study [8 , 9 ] of a x − b y = c a^x-b^y=c a x − b y = c for fixed bases a , b a,b a , b . In the past few years, using the development of explicit lower bounds for linear forms in complex logarithms of algebraic numbers, the same question has been studied for many pairs of linear recurrence sequences in place of a x , b y a^x,b^y a x , b y : Fibonacci numbers against powers of 2 or 3, Tribonacci numbers against powers of 2 [3 ] , and Padovan numbers against Fibonacci numbers [10 ] .
This paper is about one such pair: the k k k -generalized Pell numbers P n ( k ) P_n^{(k)} P n ( k ) against the Tribonacci numbers T m T_m T m . Unlike the papers cited above, k k k is not fixed at the outset, and this is what makes the pair interesting. A first computation already shows something unusual which is that for every k ≥ 3 k \ge3 k ≥ 3 the integer c = 0 c=0 c = 0 has three representations,
0 = P 0 ( k ) − T 2 = P 1 ( k ) − T 3 = P 3 ( k ) − T 6 ( 1 = 1 , 2 = 2 , 13 = 13 ) , 0=P_0^{(k)}-T_2=P_1^{(k)}-T_3=P_3^{(k)}-T_6 \qquad(1=1,\ 2=2,\ 13=13), 0 = P 0 ( k ) − T 2 = P 1 ( k ) − T 3 = P 3 ( k ) − T 6 ( 1 = 1 , 2 = 2 , 13 = 13 ) ,
and they do not depend on k k k . For k = 2 k=2 k = 2 the third one disappears, since P 3 ( 2 ) = 12 P_3^{(2)}=12 P 3 ( 2 ) = 12 , and the same indices give instead c = − 1 = P 3 ( 2 ) − T 6 = P 0 ( 2 ) − T 3 c=-1=P_3^{(2)}-T_6=P_0^{(2)}-T_3 c = − 1 = P 3 ( 2 ) − T 6 = P 0 ( 2 ) − T 3 . The explanation is the identity
P n ( k ) = F 2 n + 1 , P_n^{(k)}=F_{2n+1}, P n ( k ) = F 2 n + 1 ,
for 0 ≤ n ≤ k 0\le n\le k 0 ≤ n ≤ k , valid for every k ≥ 2 k\ge2 k ≥ 2 , due to Kılıç [6 ] stating that the first k + 1 k+1 k + 1 terms of P n ( k ) P_n^{(k)} P n ( k ) are exactly the odd-indexed Fibonacci numbers. As long as n ≤ k n\le k n ≤ k , the problem does not see k k k at all, and the natural questions are how far this independence goes, and what happens once n > k n>k n > k . This splits Pillai’s equation between k k k -Pell and Tribonacci numbers into two ranges, treated in the two parts of this paper.
In Part 1, we solve the sub-problem restricted to n ≤ k n\le k n ≤ k : by the identity above this is, for every k k k at once, the same fixed Diophantine equation, Pillai’s equation between odd-indexed Fibonacci numbers and Tribonacci numbers, a pair that has not, to our ends_mid=1 knowledge, been treated previously. Matveev’s theorem gives an astronomically large bound, N < 9.24 × 10 48 N < 9.24 \times10^{48} N < 9.24 × 1 0 48 ; the reduction of Dujella and Pethő [4 ] brings it down to N ≤ 71 N \le71 N ≤ 71 , and a computer search leaves six solutions, all with N ≤ 7 N \le7 N ≤ 7 , as in Tiebekabe and Adonsou’s treatment [10 ] of the Padovan–Fibonacci case. The structure of the proof is summarized in Table 1.
In Part 2, we treat the complementary range n > k n > k n > k , where P n ( k ) ≠ F 2 n + 1 P_n^{(k)} \ne F_{2n+1} P n ( k ) = F 2 n + 1 . This is where the difficulty lies because the field Q ( γ ( k ) , α ) \mathbb{Q}(\gamma(k),\alpha) Q ( γ ( k ) , α ) has degree up to 3 k 3k 3 k , and the height of the coefficient f k ( γ ) f_k(\gamma) f k ( γ ) grows like log k \log k log k . For k = 2 k = 2 k = 2 and k = 3 k = 3 k = 3 all the algebraic numbers involved can be computed exactly, and the method of Part 1 goes through. For k ≥ 4 k \ge4 k ≥ 4 , Matveev’s theorem only gives a bound n < N ( k ) n < \mathcal{N}(k) n < N ( k ) which grows with k k k (Proposition 14.1 ), so the values of k k k cannot simply be treated one at a time. For large k k k we use the fact that the dominant root γ ( k ) \gamma(k) γ ( k ) is exponentially close to φ 2 \varphi^2 φ 2 : then P n ( k ) P_n^{(k)} P n ( k ) is extremely close to F 2 n + 1 F_{2n+1} F 2 n + 1 (Lemma 15.1 ), the linear forms live in the field Q ( 5 , α ) \mathbb{Q}(\sqrt{5},\alpha) Q ( 5 , α ) of degree 6, independent of k k k , and the reduction shows that k ≤ 414 k \le414 k ≤ 414 (Proposition 15.2 ). The values 4 ≤ k ≤ 414 4 \le k \le414 4 ≤ k ≤ 414 are then treated one by one. A second difficulty is that the argument used for k = 2 , 3 k = 2,3 k = 2 , 3 to show that the linear forms do not vanish, namely Q ( γ ) ∩ Q ( α ) = Q \mathbb{Q}(\gamma) \cap\mathbb{Q}(\alpha) = \mathbb{Q} Q ( γ ) ∩ Q ( α ) = Q , is not available for every k k k ; we replace it by an automorphism fixing α \alpha α and moving γ \gamma γ .
Since T 1 = T 2 = 1 T_1=T_2=1 T 1 = T 2 = 1 , every integer c = P n ( k ) − 1 c=P_n^{(k)}-1 c = P n ( k ) − 1 has the two trivial representations with m = 1 m=1 m = 1 and m = 2 m=2 m = 2 ; as usual, we exclude them by requiring m , m 1 ≥ 2 m,m_1\ge2 m , m 1 ≥ 2 .
Throughout, ( F N ) N ≥ 0 (F_N)_{N\ge0} ( F N ) N ≥ 0 is the ordinary Fibonacci sequence, F 0 = 0 F_0=0 F 0 = 0 , F 1 = 1 F_1=1 F 1 = 1 , F N = F N − 1 + F N − 2 F_N=F_{N-1}+F_{N-2} F N = F N − 1 + F N − 2 , and ( T m ) m ≥ 1 (T_m)_{m\ge1} ( T m ) m ≥ 1 is the Tribonacci sequence, T 1 = T 2 = 1 T_1=T_2=1 T 1 = T 2 = 1 , T 3 = 2 T_3=2 T 3 = 2 , T m = T m − 1 + T m − 2 + T m − 3 T_m=T_{m-1}+T_{m-2}+T_{m-3} T m = T m − 1 + T m − 2 + T m − 3 .
Definition 1.1. For an integer k ≥ 2 k\ge2 k ≥ 2 , the k k k -generalized Pell sequence ( P n ( k ) ) n ≥ − ( k − 1 ) (P_n^{(k)})_{n\ge-(k-1)} ( P n ( k ) ) n ≥ − ( k − 1 ) is defined by P − ( k − 1 ) ( k ) = ⋯ = P − 1 ( k ) = 0 P_{-(k-1)}^{(k)}=\cdots=P_{-1}^{(k)}=0 P − ( k − 1 ) ( k ) = ⋯ = P − 1 ( k ) = 0 , P 0 ( k ) = 1 P_0^{(k)}=1 P 0 ( k ) = 1 , and
P n ( k ) = 2 P n − 1 ( k ) + P n − 2 ( k ) + ⋯ + P n − k ( k ) ( n ≥ 1 ) . P_n^{(k)}=2P_{n-1}^{(k)}+P_{n-2}^{(k)}+\cdots+P_{n-k}^{(k)} \qquad(n\ge1). P n ( k ) = 2 P n − 1 ( k ) + P n − 2 ( k ) + ⋯ + P n − k ( k ) ( n ≥ 1 ) . For k = 2 k=2 k = 2 this is the classical Pell sequence 1 , 2 , 5 , 12 , 29 , … 1,2,5,12,29,\ldots 1 , 2 , 5 , 12 , 29 , … . Its characteristic polynomial is P k ( x ) = x k − 2 x k − 1 − x k − 2 − ⋯ − x − 1 P_k(x)=x^k-2x^{k-1}-x^{k-2}-\cdots-x-1 P k ( x ) = x k − 2 x k − 1 − x k − 2 − ⋯ − x − 1 .
With this indexing, P n ( k ) P_n^{(k)} P n ( k ) is the term denoted P n + 1 ( k ) P_{n+1}^{(k)} P n + 1 ( k ) in [1 , 6 ] . In all the statements below we write a solution of
c = P n ( k ) − T m = P n 1 ( k ) − T m 1 (1) c=P_n^{(k)}-T_m=P_{n_1}^{(k)}-T_{m_1} \tag*{(1)} c = P n ( k ) − T m = P n 1 ( k ) − T m 1 (1)
as ( n , m , n 1 , m 1 ; c ) (n,m,n_1,m_1;c) ( n , m , n 1 , m 1 ; c ) , normalized by n > n 1 ≥ 0 n>n_1\ge0 n > n 1 ≥ 0 and m > m 1 ≥ 2 m>m_1\ge2 m > m 1 ≥ 2 .
Theorem 1.2 (Main result, Part 1). Let k ≥ 2 k\ge2 k ≥ 2 . The solutions of (1) with n ≤ k n\le k n ≤ k are exactly
$(1,3,0,2;0), , \qquad , (2,4,1,2;1), , \qquad , (2,5,1,4;-2)$,
and, when k ≥ 3 k\ge3 k ≥ 3 , also
$(3,6,0,2;0), , \qquad , (3,6,1,3;0), , \qquad , (3,7,1,6;-11)$.
In particular the list does not depend on k k k once $k\ge3.
Theorem 1.2 is deduced (§ 2.6 ) from Kılıç’s identity (Lemmas 2.6 and 2.7 ) together with the following self-contained result about ordinary Fibonacci and Tribonacci numbers, which is the technical heart of Part 1.
Theorem 1.3 (Key tool, Part 1). Let N > N 1 ≥ 1 N>N_1\ge1 N > N 1 ≥ 1 be odd integers and m > m 1 ≥ 2 m>m_1\ge2 m > m 1 ≥ 2 be integers such that
F N − T m = F N 1 − T m 1 . (2) F_N-T_m=F_{N_1}-T_{m_1}. \tag*{(2)} F N − T m = F N 1 − T m 1 . (2)
Then ( N , m , N 1 , m 1 ) (N,m,N_1,m_1) ( N , m , N 1 , m 1 ) is one of ( 3 , 3 , 1 , 2 ) (3,3,1,2) ( 3 , 3 , 1 , 2 ) , ( 5 , 4 , 3 , 2 ) (5,4,3,2) ( 5 , 4 , 3 , 2 ) , ( 5 , 5 , 3 , 4 ) (5,5,3,4) ( 5 , 5 , 3 , 4 ) , ( 7 , 6 , 1 , 2 ) (7,6,1,2) ( 7 , 6 , 1 , 2 ) , ( 7 , 6 , 3 , 3 ) (7,6,3,3) ( 7 , 6 , 3 , 3 ) , ( 7 , 7 , 3 , 6 ) (7,7,3,6) ( 7 , 7 , 3 , 6 ) .
Theorem 1.4 (Part 2). For k = 2 k=2 k = 2 (classical Pell numbers), the solutions of (1) are exactly ( 1 , 3 , 0 , 2 ; 0 ) (1,3,0,2;0) ( 1 , 3 , 0 , 2 ; 0 ) , ( 2 , 4 , 1 , 2 ; 1 ) (2,4,1,2;1) ( 2 , 4 , 1 , 2 ; 1 ) , ( 2 , 5 , 1 , 4 ; − 2 ) (2,5,1,4;-2) ( 2 , 5 , 1 , 4 ; − 2 ) , ( 3 , 6 , 0 , 3 ; − 1 ) (3,6,0,3;-1) ( 3 , 6 , 0 , 3 ; − 1 ) , ( 3 , 7 , 0 , 6 ; − 12 ) (3,7,0,6;-12) ( 3 , 7 , 0 , 6 ; − 12 ) , ( 4 , 7 , 3 , 5 ; 5 ) (4,7,3,5;5) ( 4 , 7 , 3 , 5 ; 5 ) , ( 5 , 9 , 1 , 6 ; − 11 ) (5,9,1,6;-11) ( 5 , 9 , 1 , 6 ; − 11 ) , ( 5 , 10 , 1 , 9 ; − 79 ) (5,10,1,9;-79) ( 5 , 10 , 1 , 9 ; − 79 ) , ( 9 , 15 , 6 , 13 ; − 758 ) (9,15,6,13;-758) ( 9 , 15 , 6 , 13 ; − 758 ) .
Theorem 1.5 (Part 2). For k = 3 k=3 k = 3 , the solutions of (1) are exactly ( 1 , 3 , 0 , 2 ; 0 ) (1,3,0,2;0) ( 1 , 3 , 0 , 2 ; 0 ) , ( 2 , 4 , 1 , 2 ; 1 ) (2,4,1,2;1) ( 2 , 4 , 1 , 2 ; 1 ) , ( 2 , 5 , 1 , 4 ; − 2 ) (2,5,1,4;-2) ( 2 , 5 , 1 , 4 ; − 2 ) , ( 3 , 6 , 0 , 2 ; 0 ) (3,6,0,2;0) ( 3 , 6 , 0 , 2 ; 0 ) , ( 3 , 6 , 1 , 3 ; 0 ) (3,6,1,3;0) ( 3 , 6 , 1 , 3 ; 0 ) , ( 3 , 7 , 1 , 6 ; − 11 ) (3,7,1,6;-11) ( 3 , 7 , 1 , 6 ; − 11 ) , ( 4 , 8 , 1 , 6 ; − 11 ) (4,8,1,6;-11) ( 4 , 8 , 1 , 6 ; − 11 ) , ( 4 , 7 , 3 , 4 ; 9 ) (4,7,3,4;9) ( 4 , 7 , 3 , 4 ; 9 ) , ( 4 , 8 , 3 , 7 ; − 11 ) (4,8,3,7;-11) ( 4 , 8 , 3 , 7 ; − 11 ) , ( 5 , 9 , 2 , 3 ; 3 ) (5,9,2,3;3) ( 5 , 9 , 2 , 3 ; 3 ) .
Theorem 1.6 (Part 2). Let k ≥ 4 k \ge4 k ≥ 4 . The solutions of (1) with n > k n>k n > k are exactly ( 7 , 12 , 5 , 2 ; 87 ) (7,12,5,2;87) ( 7 , 12 , 5 , 2 ; 87 ) for k = 4 k=4 k = 4 , ( 6 , 11 , 1 , 8 ; − 42 ) (6,11,1,8;-42) ( 6 , 11 , 1 , 8 ; − 42 ) , ( 6 , 12 , 1 , 11 ; − 272 ) (6,12,1,11;-272) ( 6 , 12 , 1 , 11 ; − 272 ) for k = 5 k=5 k = 5 , ( 10 , 17 , 7 , 11 ; 336 ) (10,17,7,11;336) ( 10 , 17 , 7 , 11 ; 336 ) for k = 9 k=9 k = 9 , and there is no such solution for the other values of k ≥ 4 k \ge4 k ≥ 4 .
Theorems 1.4 and 1.5 are the complete lists for k = 2 k=2 k = 2 and k = 3 k=3 k = 3 : they contain the solutions with n ≤ k n \le k n ≤ k given by Theorem 1.2 (the first three solutions for k = 2 k=2 k = 2 , the first six for $k=3), and the solutions with n > k n>k n > k , which are the ones obtained in Part 2. For k ≥ 4 k \ge4 k ≥ 4 , Theorem 1.2 (range n ≤ k n \le k n ≤ k ) and Theorem 1.6 (range n > k n>k n > k ) together give all the solutions of (1).
Corollary 1.7. The integers c c c having at least two representations c = P n ( k ) − T m c=P_n^{(k)}-T_m c = P n ( k ) − T m with m ≥ 2 m \ge2 m ≥ 2 are
c ∈ { − 758 , − 79 , − 12 , − 11 , − 2 , − 1 , 0 , 1 , 5 } ( k = 2 ) , c ∈ { − 11 , − 2 , 0 , 1 , 3 , 9 } ( k = 3 ) . c \in\{-758,-79,-12,-11,-2,-1,0,1,5\}\ (k=2), \qquad c \in\{-11,-2,0,1,3,9\}\ (k=3). c ∈ { − 758 , − 79 , − 12 , − 11 , − 2 , − 1 , 0 , 1 , 5 } ( k = 2 ) , c ∈ { − 11 , − 2 , 0 , 1 , 3 , 9 } ( k = 3 ) .
For k = 2 k=2 k = 2 each of them has exactly two representations; for k = 3 k=3 k = 3 the integers c = 0 c=0 c = 0 and c = − 11 c=-11 c = − 11 have three representations and the others exactly two. For k ≥ 4 k \ge4 k ≥ 4 they are
c ∈ { − 11 , − 2 , 0 , 1 } ∪ E k , E 4 = { 87 } , E 5 = { − 272 , − 42 } , E 9 = { 336 } , c \in\{-11,-2,0,1\} \cup E_k, \qquad E_4=\{87\}, \qquad E_5=\{-272,-42\}, \qquad E_9=\{336\}, c ∈ { − 11 , − 2 , 0 , 1 } ∪ E k , E 4 = { 87 } , E 5 = { − 272 , − 42 } , E 9 = { 336 } ,
and E k = ∅ E_k=\varnothing E k = ∅ otherwise; here c = 0 c=0 c = 0 has three representations and the others exactly two.
The solutions with c = 0 c=0 c = 0 correspond to common values of the two sequences namely for 1 = P 0 ( k ) = T 2 1=P_0^{(k)}=T_2 1 = P 0 ( k ) = T 2 , 2 = P 1 ( k ) = T 3 2=P_1^{(k)}=T_3 2 = P 1 ( k ) = T 3 and, for k ≥ 3 k \ge3 k ≥ 3 , 13 = P 3 ( k ) = T 6 13=P_3^{(k)}=T_6 13 = P 3 ( k ) = T 6 .
This paper is organized as follows: Section 2 collects the preliminary properties shared by both parts, which are the Binet-type formulas for Fibonacci and Tribonacci numbers, Matveev’s theorem, the Dujella–Pethő reduction lemma, and Kılıç’s identity, from which Theorem 1.2 is deduced (Section 2.6). Part 1 (Sections 3–8) proves Theorem 1.3; its structure is shown in Table 1 . Part 2 treats the range n > k n>k n > k : k = 2 , 3 k=2,3 k = 2 , 3 in Sections 9–13, the uniform bound for k ≥ 4 k \ge4 k ≥ 4 in Section 14, large k k k in Section 15 and 4 ≤ k ≤ 414 4 \le k \le414 4 ≤ k ≤ 414 in Section 16. Appendix A gives all the details of the computations, which are checked by our two Python scripts.
Table 1. Structure of the proof of Theorem 1.3.
Preliminaries
Fibonacci numbers
Let φ = 1 + 5 2 \varphi=\frac{1+\sqrt{5}}{2} φ = 2 1 + 5 and ψ = 1 − 5 2 \psi=\frac{1-\sqrt{5}}{2} ψ = 2 1 − 5 be the two roots of x 2 − x − 1 x^2-x-1 x 2 − x − 1 , so ∣ ψ ∣ < 1 |\psi|<1 ∣ ψ ∣ < 1 . Binet’s formula gives
F N = φ N − ψ N 5 ( N ≥ 0 ) . F_N=\frac{\varphi^N-\psi^N}{\sqrt{5}}\qquad(N\ge0). F N = 5 φ N − ψ N ( N ≥ 0 ) .
and since ∣ ψ ∣ < 1 |\psi|<1 ∣ ψ ∣ < 1 ,
∣ F N − φ N 5 ∣ = ∣ ψ ∣ N 5 < 1 5 < 0.4473 ( N ≥ 0 ) . (3) \left|F_N-\frac{\varphi^N}{\sqrt{5}}\right|=\frac{|\psi|^N}{\sqrt{5}}<\frac{1}{\sqrt{5}}<0.4473\qquad(N\geq0). \tag*{(3)} F N − 5 φ N = 5 ∣ ψ ∣ N < 5 1 < 0.4473 ( N ≥ 0 ) . (3)
We recall two elementary consequences used repeatedly below.
Lemma 2.1. For every N ≥ 2 N\geq2 N ≥ 2 , F N < 0.618 φ N F_N<0.618\varphi^N F N < 0.618 φ N , and F 1 ≤ 0.6181 φ F_1\leq0.6181\varphi F 1 ≤ 0.6181 φ . For every N ≥ 2 N\geq2 N ≥ 2 , F N − 1 ≥ 0.3819 φ N − 1 F_{N-1}\geq0.3819\varphi^{N-1} F N − 1 ≥ 0.3819 φ N − 1 .
Proof. Since ψ = − φ − 1 \psi=-\varphi^{-1} ψ = − φ − 1 , Binet’s formula gives, for j ≥ 1 j\geq1 j ≥ 1 ,
F j φ j = 1 − ( − φ − 2 ) j 5 . \frac{F_j}{\varphi^j}=\frac{1-(-\varphi^{-2})^j}{\sqrt{5}}. φ j F j = 5 1 − ( − φ − 2 ) j .
For odd j j j this lies in ( 1 / 5 , ( 1 + φ − 2 j ) / 5 ] (1/\sqrt{5},(1+\varphi^{-2j})/\sqrt{5}] ( 1/ 5 , ( 1 + φ − 2 j ) / 5 ] , and for even j j j in [ ( 1 − φ − 2 j ) / 5 , 1 / 5 ) [(1-\varphi^{-2j})/\sqrt{5},1/\sqrt{5}) [( 1 − φ − 2 j ) / 5 , 1/ 5 ) . Hence, for j ≥ 2 j\geq2 j ≥ 2 ,
F j / φ j ≤ ( 1 + φ − 6 ) / 5 < 0.618 F_j/\varphi^j\leq(1+\varphi^{-6})/\sqrt{5}<0.618 F j / φ j ≤ ( 1 + φ − 6 ) / 5 < 0.618
which is attained at j = 3 j=3 j = 3 , while F 1 / φ = φ − 1 ≤ 0.6181 F_1/\varphi=\varphi^{-1}\leq0.6181 F 1 / φ = φ − 1 ≤ 0.6181 ; and for every j ≥ 1 j\geq1 j ≥ 1 , F j / φ j ≥ ( 1 − φ − 4 ) / 5 = 1 / φ 2 F_j/\varphi^j\geq(1-\varphi^{-4})/\sqrt{5}=1/\varphi^2 F j / φ j ≥ ( 1 − φ − 4 ) / 5 = 1/ φ 2 , attained at j = 2 j=2 j = 2 . Taking j = N j=N j = N , respectively j = N − 1 ≥ 1 j=N-1\geq1 j = N − 1 ≥ 1 , gives the statement. □
Lemma 2.2. For every n ≥ 1 n\geq1 n ≥ 1 ,
∑ i = 1 n F 2 i − 1 = F 2 n . \sum_{i=1}^{n}F_{2i-1}=F_{2n}. i = 1 ∑ n F 2 i − 1 = F 2 n .
Proof. The Fibonacci recurrence gives F 2 i − 1 = F 2 i − F 2 i − 2 F_{2i-1}=F_{2i}-F_{2i-2} F 2 i − 1 = F 2 i − F 2 i − 2 for every i ≥ 1 i\geq1 i ≥ 1 (with F 0 = 0 F_0=0 F 0 = 0 ). Summing this identity for i = 1 , … , n i=1,\ldots,n i = 1 , … , n gives
∑ i = 1 n F 2 i − 1 = ∑ i = 1 n ( F 2 i − F 2 i − 2 ) = F 2 n − F 0 = F 2 n . \sum_{i=1}^{n}F_{2i-1}=\sum_{i=1}^{n}(F_{2i}-F_{2i-2})=F_{2n}-F_0=F_{2n}. i = 1 ∑ n F 2 i − 1 = i = 1 ∑ n ( F 2 i − F 2 i − 2 ) = F 2 n − F 0 = F 2 n .
□
Tribonacci numbers
Let α \alpha α be the unique real root of x 3 − x 2 − x − 1 x^3-x^2-x-1 x 3 − x 2 − x − 1 of modulus greater than 1, and set
g ( α ) = α 3 α 2 − 2 α − 1 . g(\alpha)=\frac{\alpha}{3\alpha^2-2\alpha-1}. g ( α ) = 3 α 2 − 2 α − 1 α .
The following facts are standard in the literature on Tribonacci Diophantine equations (see e.g. [3 ] ):
T m = g ( α ) α m + e ( m ) , ∣ e ( m ) ∣ < 0.4 ( m ≥ 1 ) . (4) T_m=g(\alpha)\alpha^m+e(m),\qquad|e(m)|<0.4\qquad(m\geq1). \tag*{(4)} T m = g ( α ) α m + e ( m ) , ∣ e ( m ) ∣ < 0.4 ( m ≥ 1 ) . (4)
h ( α ) = log α 3 , h ( g ( α ) ) = log 44 3 . (5) h(\alpha)=\frac{\log\alpha}{3},\qquad h(g(\alpha))=\frac{\log44}{3}. \tag*{(5)} h ( α ) = 3 log α , h ( g ( α )) = 3 log 44 . (5)
The second value comes from the minimal polynomial 44 x 3 − 2 x − 1 44x^3-2x-1 44 x 3 − 2 x − 1 of g ( α ) g(\alpha) g ( α ) , whose three roots have modulus less than 1. Moreover,
T m < 0.5436 α m ( m ≥ 2 ) , T m ≥ 0.3214 α m ( m ≥ 3 ) . (6) T_m<0.5436\alpha^m\qquad(m\geq2),\qquad T_m\geq0.3214\alpha^m\qquad(m\geq3). \tag*{(6)} T m < 0.5436 α m ( m ≥ 2 ) , T m ≥ 0.3214 α m ( m ≥ 3 ) . (6)
Finally Q ( α ) ∩ Q ( 5 ) = Q \mathbb{Q}(\alpha)\cap\mathbb{Q}(\sqrt{5})=\mathbb{Q} Q ( α ) ∩ Q ( 5 ) = Q , the two fields having coprime degrees 3 and 2. We will use this result below to show that our linear forms do not vanish.
Matveev's theorem
Theorem 2.3 (Matveev [7 ] ). Let K K K be a number field of degree D D D over Q \mathbb{Q} Q , let η 1 , … , η t ∈ K ∗ \eta_1,\ldots,\eta_t \in K^* η 1 , … , η t ∈ K ∗ be positive real algebraic numbers, and let b 1 , … , b t b_1,\ldots,b_t b 1 , … , b t be nonzero rational integers. Put
Λ : = η 1 b 1 ⋯ η t b t − 1 ≠ 0. \Lambda:= \eta_1^{b_1}\cdots\eta_t^{b_t}-1 \ne0. Λ := η 1 b 1 ⋯ η t b t − 1 = 0. Let A 1 , … , A t A_1,\ldots,A_t A 1 , … , A t be real numbers with A i ≥ max { D h ( η i ) , ∣ log η i ∣ , 0.16 } A_i \ge\max\{Dh(\eta_i),|\log\eta_i|,0.16\} A i ≥ max { D h ( η i ) , ∣ log η i ∣ , 0.16 } for each i i i , and B ≥ max { ∣ b 1 ∣ , … , ∣ b t ∣ } B \ge\max\{|b_1|,\ldots,|b_t|\} B ≥ max { ∣ b 1 ∣ , … , ∣ b t ∣ } . Then
log ∣ Λ ∣ > − 1.4 ⋅ 30 t + 3 ⋅ t 4.5 ⋅ D 2 ( 1 + log D ) ( 1 + log B ) A 1 ⋯ A t . \log|\Lambda| > -1.4 \cdot30^{t+3}\cdot t^{4.5}\cdot D^2(1+\log D)(1+\log B)A_1\cdots A_t. log ∣Λ∣ > − 1.4 ⋅ 3 0 t + 3 ⋅ t 4.5 ⋅ D 2 ( 1 + log D ) ( 1 + log B ) A 1 ⋯ A t . The right-hand side increases with D D D , so the inequality remains true if D D D is replaced by an upper bound for [ K : Q ] [K:\mathbb{Q}] [ K : Q ] . For t = 3 t=3 t = 3 we write
C ( D ) : = 1.4 ⋅ 30 6 ⋅ 3 4.5 ⋅ D 2 ( 1 + log D ) . C(D):=1.4\cdot30^6\cdot3^{4.5}\cdot D^2(1+\log D). C ( D ) := 1.4 ⋅ 3 0 6 ⋅ 3 4.5 ⋅ D 2 ( 1 + log D ) .
The Dujella–Pethő reduction lemma
Lemma 2.4 (Dujella–Pethő [4 ] ). Let M M M be a positive integer, let θ \theta θ be an irrational real number with convergent p / q p/q p / q of its continued fraction expansion satisfying q > 6 M q>6M q > 6 M , and let A A A , B B B , μ \mu μ be real numbers with A > 0 A>0 A > 0 and B > 1 B>1 B > 1 . Put ε : = ∥ μ q ∥ − M ∥ θ q ∥ \varepsilon:=\lVert\mu q\rVert-M\lVert\theta q\rVert ε := ∥ μ q ∥ − M ∥ θ q ∥ , where ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ denotes the distance to the nearest integer. If ε > 0 \varepsilon>0 ε > 0 , then there is no solution of the inequality
0 < ∣ u θ − v + μ ∣ < A B − w 0<|u\theta-v+\mu|<AB^{-w} 0 < ∣ u θ − v + μ ∣ < A B − w in integers u , v , w u,v,w u , v , w with 1 ≤ u ≤ M 1\le u\le M 1 ≤ u ≤ M and w ≥ log ( A q / ε ) / log B w\ge\log(Aq/\varepsilon)/\log B w ≥ log ( A q / ε ) / log B .
Its proof works when w w w is a real number, which is how we use it. In all our applications ε > 0 \varepsilon>0 ε > 0 already holds for the first convergent with q > 6 M q>6M q > 6 M or for one of the next five convergents.
The universal prefix lemma
The identity proved in this subsection is due to Kılıç [6 ] . We include a short proof to keep the paper self-contained.
Definition 2.5. Let ( a n ) n ≥ 0 (a_n)_{n\ge0} ( a n ) n ≥ 0 be the sequence with a 0 = 1 a_0=1 a 0 = 1 and a n = 2 a n − 1 + a n − 2 + ⋯ + a 0 a_n=2a_{n-1}+a_{n-2}+\cdots+a_0 a n = 2 a n − 1 + a n − 2 + ⋯ + a 0 for n ≥ 1 n\ge1 n ≥ 1 .
Lemma 2.6 (Universal prefix). For every k ≥ 2 k\ge2 k ≥ 2 and every 0 ≤ n ≤ k 0\le n\le k 0 ≤ n ≤ k , P n ( k ) = a n P_n^{(k)}=a_n P n ( k ) = a n .
Proof. We induct on n n n . For n = 0 n=0 n = 0 both sides equal 1. Suppose 1 ≤ n ≤ k 1\le n\le k 1 ≤ n ≤ k and P j ( k ) = a j P_j^{(k)}=a_j P j ( k ) = a j for all 0 ≤ j < n 0\le j<n 0 ≤ j < n . By Definition 1.1,
P n ( k ) = 2 P n − 1 ( k ) + ∑ i = 2 k P n − i ( k ) . P_n^{(k)}=2P_{n-1}^{(k)}+\sum_{i=2}^{k}P_{n-i}^{(k)}. P n ( k ) = 2 P n − 1 ( k ) + i = 2 ∑ k P n − i ( k ) . For 1 ≤ i ≤ k 1\le i\le k 1 ≤ i ≤ k , either n − i ≥ 0 n-i\ge0 n − i ≥ 0 – in which case n − i < n ≤ k n-i<n\le k n − i < n ≤ k , so P n − i ( k ) = a n − i P_{n-i}^{(k)}=a_{n-i} P n − i ( k ) = a n − i by the induction hypothesis – or n − i < 0 n-i<0 n − i < 0 , in which case n − i ≥ n − k ≥ 1 − k = − ( k − 1 ) n-i\ge n-k\ge1-k=-(k-1) n − i ≥ n − k ≥ 1 − k = − ( k − 1 ) , so P n − i ( k ) = 0 P_{n-i}^{(k)}=0 P n − i ( k ) = 0 by Definition 1.1. Hence the sum collects exactly 2 a n − 1 + a n − 2 + ⋯ + a 0 2a_{n-1}+a_{n-2}+\cdots+a_0 2 a n − 1 + a n − 2 + ⋯ + a 0 , the defining recursion for a n a_n a n . Thus P n ( k ) = a n P_n^{(k)}=a_n P n ( k ) = a n . □
Lemma 2.7. For every n ≥ 0 n\ge0 n ≥ 0 , a n = F 2 n + 1 a_n=F_{2n+1} a n = F 2 n + 1 .
Proof. We show b n : = F 2 n + 1 b_n:=F_{2n+1} b n := F 2 n + 1 satisfies the same recursive definition as a n a_n a n ; since a sequence is uniquely determined by such a recursion together with its initial value, this gives a n = b n a_n=b_n a n = b n . First, b 0 = F 1 = 1 = a 0 b_0=F_1=1=a_0 b 0 = F 1 = 1 = a 0 . Fix n ≥ 1 n\ge1 n ≥ 1 ; we must show
F 2 n + 1 = 2 F 2 n − 1 + ∑ i = 1 n − 1 F 2 i − 1 . (7) F_{2n+1}=2F_{2n-1}+\sum_{i=1}^{n-1}F_{2i-1}. \tag*{(7)} F 2 n + 1 = 2 F 2 n − 1 + i = 1 ∑ n − 1 F 2 i − 1 . (7)
This sum is empty when n = 1 n=1 n = 1 . By Lemma 2.2 , ∑ i = 1 n − 1 F 2 i − 1 = F 2 n − 2 \sum_{i=1}^{n-1} F_{2i-1}=F_{2n-2} ∑ i = 1 n − 1 F 2 i − 1 = F 2 n − 2 . This gives also 0 0 0 when n = 1 n=1 n = 1 , consistently with F 0 = 0 F_0=0 F 0 = 0 . So (7) reduces to F 2 n + 1 = 2 F 2 n − 1 + F 2 n − 2 F_{2n+1}=2F_{2n-1}+F_{2n-2} F 2 n + 1 = 2 F 2 n − 1 + F 2 n − 2 , which holds by two applications of the Fibonacci recurrence,
F 2 n + 1 = F 2 n + F 2 n − 1 = ( F 2 n − 1 + F 2 n − 2 ) + F 2 n − 1 = 2 F 2 n − 1 + F 2 n − 2 . F_{2n+1}=F_{2n}+F_{2n-1}=(F_{2n-1}+F_{2n-2})+F_{2n-1}=2F_{2n-1}+F_{2n-2}. F 2 n + 1 = F 2 n + F 2 n − 1 = ( F 2 n − 1 + F 2 n − 2 ) + F 2 n − 1 = 2 F 2 n − 1 + F 2 n − 2 .
Combining Lemmas 2.6 and 2.7 gives, for every k ≥ 2 k\ge2 k ≥ 2 and every 0 ≤ n ≤ k 0\le n\le k 0 ≤ n ≤ k , the exact identity P n ( k ) = F 2 n + 1 P_n^{(k)}=F_{2n+1} P n ( k ) = F 2 n + 1 .
Proof of the main theorem 1.2
Suppose
c = P n ( k ) − T m = P n 1 ( k ) − T m 1 c=P_n^{(k)}-T_m=P_{n_1}^{(k)}-T_{m_1} c = P n ( k ) − T m = P n 1 ( k ) − T m 1
with n > n 1 ≥ 0 n>n_1\ge0 n > n 1 ≥ 0 , m > m 1 ≥ 2 m>m_1\ge2 m > m 1 ≥ 2 and n ≤ k n\le k n ≤ k (hence also n 1 ≤ k n_1\le k n 1 ≤ k ). By Lemmas 2.6 and 2.7 , P n ( k ) = F 2 n + 1 P_n^{(k)}=F_{2n+1} P n ( k ) = F 2 n + 1 and P n 1 ( k ) = F 2 n 1 + 1 P_{n_1}^{(k)}=F_{2n_1+1} P n 1 ( k ) = F 2 n 1 + 1 . Writing N : = 2 n + 1 N:=2n+1 N := 2 n + 1 , N 1 : = 2 n 1 + 1 N_1:=2n_1+1 N 1 := 2 n 1 + 1 , the hypothesis becomes c = F N − T m = F N 1 − T m 1 c=F_N-T_m=F_{N_1}-T_{m_1} c = F N − T m = F N 1 − T m 1 with N > N 1 ≥ 1 N>N_1\ge1 N > N 1 ≥ 1 odd and m > m 1 ≥ 2 m>m_1\ge2 m > m 1 ≥ 2 , exactly equation (2) . Conversely, every solution of (2) with ( N − 1 ) / 2 ≤ k (N-1)/2\le k ( N − 1 ) /2 ≤ k gives a solution of (1) with n ≤ k n\le k n ≤ k . By Theorem 1.3 , the solutions are the six listed there; writing n = ( N − 1 ) / 2 n=(N-1)/2 n = ( N − 1 ) /2 , n 1 = ( N 1 − 1 ) / 2 n_1=(N_1-1)/2 n 1 = ( N 1 − 1 ) /2 gives the list of Theorem 1.2 , the last three solutions having n = 3 n=3 n = 3 and thus requiring k ≥ 3 k\ge3 k ≥ 3 .
Part 1. The universal range n ≤ k n\le k n ≤ k
This part proves Theorem 1.3 , the self-contained statement about ordinary Fibonacci and Tribonacci numbers from which Theorem 1.2 was deduced above. The proof has five steps, summarized in Table 1.
Setup
Suppose
c = F N − T m = F N 1 − T m 1 , N , N 1 odd , m , m 1 ≥ 2 , ( N , m ) ≠ ( N 1 , m 1 ) . c=F_N-T_m=F_{N_1}-T_{m_1},\qquad N,N_1\ \text{odd},\ m,m_1\ge2,\ (N,m)\ne(N_1,m_1). c = F N − T m = F N 1 − T m 1 , N , N 1 odd , m , m 1 ≥ 2 , ( N , m ) = ( N 1 , m 1 ) .
If N = N 1 N=N_1 N = N 1 , then F N = F N 1 F_N=F_{N_1} F N = F N 1 forces T m = T m 1 T_m=T_{m_1} T m = T m 1 , hence m = m 1 m=m_1 m = m 1 (Tribonacci numbers are strictly increasing for m ≥ 2 m\ge2 m ≥ 2 ), contradicting ( N , m ) ≠ ( N 1 , m 1 ) (N,m)\ne(N_1,m_1) ( N , m ) = ( N 1 , m 1 ) . So N ≠ N 1 N\ne N_1 N = N 1 ; without loss of generality N > N 1 N>N_1 N > N 1 . Thus, since both are odd, N 1 ≤ N − 2 N_1\le N-2 N 1 ≤ N − 2 , and then F N − F N 1 = T m − T m 1 > 0 F_N-F_{N_1}=T_m-T_{m_1}>0 F N − F N 1 = T m − T m 1 > 0 forces T m > T m 1 T_m>T_{m_1} T m > T m 1 , i.e. m > m 1 m>m_1 m > m 1 . We write
γ N : = N − N 1 ≥ 2 , γ m : = m − m 1 ≥ 1 , \gamma_N:=N-N_1\ge2,\qquad\gamma_m:=m-m_1\ge1, γ N := N − N 1 ≥ 2 , γ m := m − m 1 ≥ 1 ,
so that
F N − F N 1 = T m − T m 1 . (8) F_N-F_{N_1}=T_m-T_{m_1}. \tag*{(8)} F N − F N 1 = T m − T m 1 . (8)
A direct computer search over all odd $N\le 1501 (Appendix § 4.9 ) gives exactly the six solutions listed in Theorem 1.3 , all with N ≤ 7 N\le7 N ≤ 7 . Hence we assume from now that N ≥ 15 N\ge15 N ≥ 15 .
By Lemma 4.1 below, this gives m ≥ 11 m \ge11 m ≥ 11 and m < N m < N m < N , so that B = N B = N B = N can be used in Matveev’s theorem.
Note that N 1 = 1 N_1 = 1 N 1 = 1 does occur, in ( 3 , 3 , 1 , 2 ) (3, 3, 1, 2) ( 3 , 3 , 1 , 2 ) and ( 7 , 6 , 1 , 2 ) (7, 6, 1, 2) ( 7 , 6 , 1 , 2 ) , so the case F N 1 = F 1 = 1 F_{N_1} = F_1 = 1 F N 1 = F 1 = 1 has to be covered by the estimates below; this is why Lemma 2.1 has a separate bound for F 1 F_1 F 1 .
Size-relation lemma
Lemma 4.1. For N ≥ 3 N \ge3 N ≥ 3 and m ≥ 3 m \ge3 m ≥ 3 satisfying (8): N < 1.2666 m + 1.7336 N < 1.2666m + 1.7336 N < 1.2666 m + 1.7336 ; if moreover m ≥ 5 m \ge5 m ≥ 5 , then m < 0.7897 N + 3.073 m < 0.7897N + 3.073 m < 0.7897 N + 3.073 . If N ≥ 15 N \ge15 N ≥ 15 , then m ≥ 11 m \ge11 m ≥ 11 and m < N m < N m < N .
Proof. Since N 1 ≤ N − 2 N_1 \le N - 2 N 1 ≤ N − 2 and Fibonacci numbers are increasing, F N − F N 1 ≥ F N − F N − 2 = F N − 1 ≥ 0.3819 φ N − 1 F_N - F_{N_1} \ge F_N - F_{N-2} = F_{N-1} \ge0.3819\,\varphi^{N-1} F N − F N 1 ≥ F N − F N − 2 = F N − 1 ≥ 0.3819 φ N − 1 by Lemma 2.1 . Again, F N − F N 1 < F N < 0.618 φ N F_N - F_{N_1} < F_N < 0.618\,\varphi^N F N − F N 1 < F N < 0.618 φ N . Similarly, since m 1 ≤ m − 1 m_1 \le m - 1 m 1 ≤ m − 1 and Tribonacci numbers are increasing, T m − T m 1 ≥ T m − T m − 1 = T m − 2 + T m − 3 ≥ T m − 2 ≥ 0.3214 α m − 2 T_m - T_{m_1} \ge T_m - T_{m-1} = T_{m-2} + T_{m-3} \ge T_{m-2} \ge0.3214\,\alpha^{m-2} T m − T m 1 ≥ T m − T m − 1 = T m − 2 + T m − 3 ≥ T m − 2 ≥ 0.3214 α m − 2 for m − 2 ≥ 3 m - 2 \ge3 m − 2 ≥ 3 , and T m < 0.5436 α m T_m < 0.5436\,\alpha^m T m < 0.5436 α m , both by (6). Combining the lower bound on one side of (8) with the upper bound on the other, in both directions, and taking logarithms, gives
N < 1 + log α log φ m + log ( 0.5436 / 0.3819 ) log φ < 1.26634 m + 1.73368 , N < 1 + \frac{\log\alpha}{\log\varphi}m + \frac{\log(0.5436/0.3819)}{\log\varphi} < 1.26634m + 1.73368, N < 1 + log φ log α m + log φ log ( 0.5436/0.3819 ) < 1.26634 m + 1.73368 , and
m < 2 + log φ log α N + log ( 0.618 / 0.3214 ) log α < 0.78968 N + 3.0730 , m < 2 + \frac{\log\varphi}{\log\alpha}N + \frac{\log(0.618/0.3214)}{\log\alpha} < 0.78968N + 3.0730, m < 2 + log α log φ N + log α log ( 0.618/0.3214 ) < 0.78968 N + 3.0730 , which implies the stated inequalities. If N ≥ 15 N \ge15 N ≥ 15 , the first one gives m > 11 m > 11 m > 11 , and the second one gives m < 0.7897 N + 3.073 ≤ N m < 0.7897N + 3.073 \le N m < 0.7897 N + 3.073 ≤ N . □
We also note that the first chain of inequalities gives (9)
φ N < φ ⋅ 0.5436 0.3819 α m < 2.304 α m . (9) \varphi^N < \varphi\cdot\frac{0.5436}{0.3819}\alpha^m < 2.304\,\alpha^m. \tag*{(9)} φ N < φ ⋅ 0.3819 0.5436 α m < 2.304 α m . (9)
First linear form and Matveev
Bounding ∣ c ∣ |c| ∣ c ∣ via the small representation, and using F N 1 ≤ 0.6181 φ N 1 F_{N_1} \le0.6181\,\varphi^{N_1} F N 1 ≤ 0.6181 φ N 1 and the Tribonacci analogue T m 1 < 0.5436 α m 1 T_{m_1} < 0.5436\,\alpha^{m_1} T m 1 < 0.5436 α m 1 , we get
∣ c ∣ < 0.7 max ( φ N 1 , α m 1 ) , |c| < 0.7\max(\varphi^{N_1}, \alpha^{m_1}), ∣ c ∣ < 0.7 max ( φ N 1 , α m 1 ) ,
using Binet’s formulas (3), (4) on the large representation c = F N − T m c = F_N - T_m c = F N − T m ,
∣ φ N 5 − g ( α ) α m ∣ < 0.7 max ( φ N 1 , α m 1 ) + 0.85 < 1.4 max ( φ N 1 , α m 1 ) . \left|\frac{\varphi^N}{\sqrt{5}} - g(\alpha)\alpha^m\right| < 0.7\max(\varphi^{N_1}, \alpha^{m_1}) + 0.85 < 1.4\max(\varphi^{N_1}, \alpha^{m_1}). 5 φ N − g ( α ) α m < 0.7 max ( φ N 1 , α m 1 ) + 0.85 < 1.4 max ( φ N 1 , α m 1 ) .
Dividing by g ( α ) α m g(\alpha)\alpha^m g ( α ) α m and setting Λ : = 1 5 g ( α ) φ N α − m − 1 \Lambda:= \frac{1}{\sqrt{5}g(\alpha)}\varphi^N\alpha^{-m} - 1 Λ := 5 g ( α ) 1 φ N α − m − 1 , and using (9) (10)
∣ Λ ∣ < 10 max ( φ − γ N , α − γ m ) . (10) |\Lambda| < 10\max\left(\varphi^{-\gamma N}, \alpha^{-\gamma m}\right). \tag*{(10)} ∣Λ∣ < 10 max ( φ − γ N , α − γ m ) . (10)
We have Λ ≠ 0 \Lambda\ne0 Λ = 0 because otherwise φ N / 5 = g ( α ) α m \varphi^N/\sqrt{5} = g(\alpha)\alpha^m φ N / 5 = g ( α ) α m would belong to Q ( 5 ) ∩ Q ( α ) = Q \mathbb{Q}(\sqrt{5}) \cap\mathbb{Q}(\alpha) = \mathbb{Q} Q ( 5 ) ∩ Q ( α ) = Q , whereas φ N / 5 = F N / 2 + L N / ( 2 5 ) \varphi^N/\sqrt{5} = F_N/2 + L_N/(2\sqrt{5}) φ N / 5 = F N /2 + L N / ( 2 5 ) is irrational, the Lucas number L N L_N L N being nonzero.
The data for Matveev’s Theorem 2.3 for this form and for the three forms of the next two sections are collected in Table 2 . For Λ \Lambda Λ , A 3 = D ( h ( 5 ) + h ( g ( α ) ) ) = 12.397 A_3 = D(h(\sqrt{5}) + h(g(\alpha))) = 12.397 A 3 = D ( h ( 5 ) + h ( g ( α ))) = 12.397 , and comparing with (10) we get:
Table 2. Data for Matveev’s theorem in Part 1: t = 3 t=3 t = 3 , K = Q ( 5 , α ) K=\mathbb{Q}(\sqrt{5},\alpha) K = Q ( 5 , α ) , D = 6 D=6 D = 6 , B = N B=N B = N , b 3 = 1 b_3=1 b 3 = 1 , A 1 = 3 log φ = 1.4436 A_1=3\log\varphi=1.4436 A 1 = 3 log φ = 1.4436 , A 2 = 2 log α = 1.2188 A_2=2\log\alpha=1.2188 A 2 = 2 log α = 1.2188 , and X : = 1 + log N X:=1+\log N X := 1 + log N .
Proposition 5.1. For every solution of (8) with N ≥ 15 N \ge15 N ≥ 15 ,
min { γ N log φ , γ m log α } < K 1 ( 1 + log N ) , K 1 = 3.139 × 10 14 . \min\{\gamma N\log\varphi, \gamma m\log\alpha\} < K_1(1 + \log N), \qquad K_1 = 3.139 \times10^{14}. min { γ N log φ , γ m log α } < K 1 ( 1 + log N ) , K 1 = 3.139 × 1 0 14 .
Here C ( 6 ) A 1 A 2 A 3 > 3.13879 × 10 14 C(6)A_1A_2A_3 > 3.13879 \times10^{14} C ( 6 ) A 1 A 2 A 3 > 3.13879 × 1 0 14 , and K 1 K_1 K 1 also absorbs the log 10 \log10 log 10 coming from (10).
Secondary linear forms: bounding both gaps
Case 1: Nm
Case 1: γ N log φ ≤ γ m log α \gamma_N\log\varphi\le\gamma_m\log\alpha γ N log φ ≤ γ m log α . By Proposition 5.1, γ N < K 1 ( 1 + log N ) / log φ \gamma_N<K_1(1+\log N)/\log\varphi γ N < K 1 ( 1 + log N ) / log φ . Factoring φ N 1 \varphi^{N_1} φ N 1 out of F N − F N 1 F_N-F_{N_1} F N − F N 1 via Binet,
F N − F N 1 = φ N 1 ( φ γ N − 1 ) 5 + δ 1 , ∣ δ 1 ∣ < 0.9 , F_N-F_{N_1}=\frac{\varphi^{N_1}(\varphi^{\gamma_N}-1)}{\sqrt{5}}+\delta_1,\qquad|\delta_1|<0.9, F N − F N 1 = 5 φ N 1 ( φ γ N − 1 ) + δ 1 , ∣ δ 1 ∣ < 0.9 ,
substituting T m = F N − F N 1 + T m 1 T_m=F_N-F_{N_1}+T_{m_1} T m = F N − F N 1 + T m 1 , dividing by g ( α ) α m g(\alpha)\alpha^m g ( α ) α m , and setting
Λ 1 : = φ γ N − 1 5 g ( α ) φ N 1 α − m − 1 , \Lambda_1:=\frac{\varphi^{\gamma_N}-1}{\sqrt{5}g(\alpha)}\varphi^{N_1}\alpha^{-m}-1, Λ 1 := 5 g ( α ) φ γ N − 1 φ N 1 α − m − 1 ,
we get
∣ Λ 1 ∣ < 5.5 α − γ m . (11) |\Lambda_1|<5.5\alpha^{-\gamma_m}. \tag*{(11)} ∣ Λ 1 ∣ < 5.5 α − γ m . (11)
We used the fact T m 1 < 0.5436 α m − γ m T_{m_1}<0.5436\alpha^{m-\gamma_m} T m 1 < 0.5436 α m − γ m . We have Λ 1 ≠ 0 \Lambda_1\ne0 Λ 1 = 0 , otherwise ( φ N − φ N 1 ) / 5 = g ( α ) α m (\varphi^N-\varphi^{N_1})/\sqrt{5}=g(\alpha)\alpha^m ( φ N − φ N 1 ) / 5 = g ( α ) α m would be rational, whereas ( φ N − φ N 1 ) / 5 = ( F N − F N 1 ) / 2 + ( L N − L N 1 ) / ( 2 5 ) (\varphi^N-\varphi^{N_1})/\sqrt{5}=(F_N-F_{N_1})/2+(L_N-L_{N_1})/(2\sqrt{5}) ( φ N − φ N 1 ) / 5 = ( F N − F N 1 ) /2 + ( L N − L N 1 ) / ( 2 5 ) and L N ≠ L N 1 L_N\ne L_{N_1} L N = L N 1 , since the Lucas numbers are strictly increasing for N ≥ 1 N\ge1 N ≥ 1 . Note that Λ 1 \Lambda_1 Λ 1 contains α − m \alpha^{-m} α − m . In fact, for the Tribonacci sequence, the gap γ m \gamma_m γ m appears only in the upper bound (11), and not in the form, so that b 2 = − m b_2=-m b 2 = − m in Table 2 . For the height of η 3 \eta_3 η 3 ,
D h ( η 3 ) ≤ D h ( φ ) γ N + D ( log 2 + h ( 5 ) + h ( g ( α ) ) ) < 3 γ N log φ + 16.56 < ( 3 K 1 + 16.56 ) ( 1 + log N ) \begin{aligned}
D h(\eta_3)\le D h(\varphi)\gamma_N+D\bigl(\log2+h(\sqrt{5})+h(g(\alpha))\bigr) \\
&<3\gamma_N\log\varphi+16.56<(3K_1+16.56)(1+\log N)
\end{aligned} D h ( η 3 ) ≤ D h ( φ ) γ N + D ( log 2 + h ( 5 ) + h ( g ( α )) ) < 3 γ N log φ + 16.56 < ( 3 K 1 + 16.56 ) ( 1 + log N )
by the Case-1 hypothesis on γ N \gamma_N γ N , and Matveev’s theorem (see the second row of Table 2). This gives
Proposition 6.1. In Case 1 , γ m log α < K 2 ( 1 + log N ) 2 \gamma_m\log\alpha<K_2(1+\log N)^2 γ m log α < K 2 ( 1 + log N ) 2 , with K 2 = 2.385 × 10 28 K_2=2.385\times10^{28} K 2 = 2.385 × 1 0 28 .
Case 2: mN
Case 2: γ m log α ≤ γ N log φ \gamma_m\log\alpha\le\gamma_N\log\varphi γ m log α ≤ γ N log φ . By the symmetric construction, factoring α m 1 \alpha^{m_1} α m 1 out of T m − T m 1 T_m-T_{m_1} T m − T m 1 and dividing by φ N / 5 \varphi^N/\sqrt{5} φ N / 5 , with
Λ 2 : = 5 g ( α ) ( α γ m − 1 ) α m 1 φ − N − 1 , \Lambda_2:=\sqrt{5}g(\alpha)(\alpha^{\gamma_m}-1)\alpha^{m_1}\varphi^{-N}-1, Λ 2 := 5 g ( α ) ( α γ m − 1 ) α m 1 φ − N − 1 ,
we have φ N / 5 − g ( α ) α m 1 ( α γ m − 1 ) = F N 1 + ψ N / 5 + e ( m ) − e ( m 1 ) \varphi^N/\sqrt{5}-g(\alpha)\alpha^{m_1}(\alpha^{\gamma_m}-1)=F_{N_1}+\psi^N/\sqrt{5}+e(m)-e(m_1) φ N / 5 − g ( α ) α m 1 ( α γ m − 1 ) = F N 1 + ψ N / 5 + e ( m ) − e ( m 1 ) , whose absolute value is less than 0.7 φ N 1 + 0.906 < 1.27 φ N 1 0.7\varphi^{N_1}+0.906<1.27\varphi^{N_1} 0.7 φ N 1 + 0.906 < 1.27 φ N 1 , hence
∣ Λ 2 ∣ < 3 φ − γ N . (12) |\Lambda_2|<3\varphi^{-\gamma_N}. \tag*{(12)} ∣ Λ 2 ∣ < 3 φ − γ N . (12)
As before Λ 2 ≠ 0 \Lambda_2\ne0 Λ 2 = 0 , since φ N / 5 \varphi^N/\sqrt{5} φ N / 5 is irrational. Since D h ( η 3 ) < 2 γ m log α + 16.56 < ( 2 K 1 + 16.56 ) ( 1 + log N ) D h(\eta_3)<2\gamma_m\log\alpha+16.56<(2K_1+16.56)(1+\log N) D h ( η 3 ) < 2 γ m log α + 16.56 < ( 2 K 1 + 16.56 ) ( 1 + log N ) , Matveev’s theorem (third row of Table 2) gives:
Proposition 6.2. In Case 2 , γ N log φ < K 3 ( 1 + log N ) 2 \gamma_N\log\varphi<K_3(1+\log N)^2 γ N log φ < K 3 ( 1 + log N ) 2 , with K 3 = 1.590 × 10 28 K_3=1.590\times10^{28} K 3 = 1.590 × 1 0 28 .
Since K 1 ( 1 + log N ) < K 3 ( 1 + log N ) 2 < K 2 ( 1 + log N ) 2 K_1(1+\log N)<K_3(1+\log N)^2<K_2(1+\log N)^2 K 1 ( 1 + log N ) < K 3 ( 1 + log N ) 2 < K 2 ( 1 + log N ) 2 , in both cases
γ N log φ < K 2 ( 1 + log N ) 2 , γ m log α < K 2 ( 1 + log N ) 2 . (13) \gamma_N\log\varphi<K_2(1+\log N)^2,\qquad\gamma_m\log\alpha<K_2(1+\log N)^2. \tag*{(13)} γ N log φ < K 2 ( 1 + log N ) 2 , γ m log α < K 2 ( 1 + log N ) 2 . (13)
A fourth linear form: an absolute bound on N N N
Substituting Binet’s formula into all four terms of F N − F N 1 = T m − T m 1 F_N-F_{N_1}=T_m-T_{m_1} F N − F N 1 = T m − T m 1 and factoring both gaps out,
∣ φ N 1 ( φ γ N − 1 ) 5 − g ( α ) α m 1 ( α γ m − 1 ) ∣ < 1.7. \left|\frac{\varphi^{N_1}(\varphi^{\gamma_N}-1)}{\sqrt{5}}-g(\alpha)\alpha^{m_1}(\alpha^{\gamma_m}-1)\right|<1.7. 5 φ N 1 ( φ γ N − 1 ) − g ( α ) α m 1 ( α γ m − 1 ) < 1.7.
Dividing by g ( α ) α m 1 ( α γ m − 1 ) ≥ g ( α ) ( α − 1 ) α m 1 g(\alpha)\alpha^{m_1}(\alpha^{\gamma_m}-1)\geq g(\alpha)(\alpha-1)\alpha^{m_1} g ( α ) α m 1 ( α γ m − 1 ) ≥ g ( α ) ( α − 1 ) α m 1 and setting
Λ 3 : = φ γ N − 1 5 g ( α ) ( α γ m − 1 ) φ N 1 α − m 1 − 1 , ∣ Λ 3 ∣ < 6.025 α − m 1 . \Lambda_3:=\frac{\varphi^{\gamma_N}-1}{\sqrt{5}g(\alpha)(\alpha^{\gamma_m}-1)}\varphi^{N_1}\alpha^{-m_1}-1,\qquad|\Lambda_3|<6.025\alpha^{-m_1}. Λ 3 := 5 g ( α ) ( α γ m − 1 ) φ γ N − 1 φ N 1 α − m 1 − 1 , ∣ Λ 3 ∣ < 6.025 α − m 1 .
Again Λ 3 ≠ 0 \Lambda_3\ne0 Λ 3 = 0 by the same argument given above for Λ 1 \Lambda_1 Λ 1 . The height of η 3 \eta_3 η 3 is bounded via (13) by
D h ( η 3 ) ≤ 3 γ N log φ + 2 γ m log α + D ( 2 log 2 + h ( 5 ) + h ( g ( α ) ) ) < ( 5 K 2 + 20.72 ) ( 1 + log N ) 2 , D h(\eta_3)\leq3\gamma_N\log\varphi+2\gamma_m\log\alpha+D(2\log2+h(\sqrt{5})+h(g(\alpha)))<(5K_2+20.72)(1+\log N)^2, D h ( η 3 ) ≤ 3 γ N log φ + 2 γ m log α + D ( 2 log 2 + h ( 5 ) + h ( g ( α ))) < ( 5 K 2 + 20.72 ) ( 1 + log N ) 2 ,
and Matveev’s theorem (last row of Table 2 ) gives
m 1 log α < K 4 ( 1 + log N ) 3 , K 4 = 3.020 × 10 42 . m_1\log\alpha<K_4(1+\log N)^3,\qquad K_4=3.020\times10^{42}. m 1 log α < K 4 ( 1 + log N ) 3 , K 4 = 3.020 × 1 0 42 .
Combined with the linear-in-N N N lower bound on m 1 = m − γ m m_1=m-\gamma_m m 1 = m − γ m coming from Lemma 4.1 and (13) ,
N − 1.7336 1.2666 log α < m log α < K 4 ( 1 + log N ) 3 + K 2 ( 1 + log N ) 2 . \frac{N-1.7336}{1.2666}\log\alpha<m\log\alpha<K_4(1+\log N)^3+K_2(1+\log N)^2. 1.2666 N − 1.7336 log α < m log α < K 4 ( 1 + log N ) 3 + K 2 ( 1 + log N ) 2 .
This gives the following upper bound
Proposition 7.1. Every solution of (8) satisfies N < 9.24 × 10 48 < 10 49 N<9.24\times10^{48}<10^{49} N < 9.24 × 1 0 48 < 1 0 49 .
Reduction
We now reduce the bound of Proposition 7.1 using the Baker–Davenport reduction algorithm. Put M : = 10 49 M:=10^{49} M := 1 0 49 ; by Proposition 7.1 and Lemma 4.1, N 1 < N < M N_1<N<M N 1 < N < M and m 1 < m < N < M m_1<m<N<M m 1 < m < N < M . Let θ : = log φ / log α \theta:=\log\varphi/\log\alpha θ := log φ / log α .
Step 1 (the first linear form). Put w : = min { γ N log φ , γ m log α } w:=\min\{\gamma_N\log\varphi,\gamma_m\log\alpha\} w := min { γ N log φ , γ m log α } . If w > log 20 w>\log20 w > log 20 , then ∣ Λ ∣ < 1 / 2 |\Lambda|<1/2 ∣Λ∣ < 1/2 by (10) , so Γ : = N log φ − m log α − log ( 5 g ( α ) ) = log ( 1 + Λ ) \Gamma:=N\log\varphi-m\log\alpha-\log(\sqrt{5}g(\alpha))=\log(1+\Lambda) Γ := N log φ − m log α − log ( 5 g ( α )) = log ( 1 + Λ ) satisfies ∣ Γ ∣ < 2 ∣ Λ ∣ < 20 e − w |\Gamma|<2|\Lambda|<20e^{-w} ∣Γ∣ < 2∣Λ∣ < 20 e − w . Dividing by log α \log\alpha log α gives
0 < ∣ N θ − m + μ 0 ∣ < 20 log α e − w , μ 0 : = − log ( 5 g ( α ) ) log α . 0<|N\theta-m+\mu_0|<\frac{20}{\log\alpha}e^{-w},\qquad\mu_0:=-\frac{\log(\sqrt{5}g(\alpha))}{\log\alpha}. 0 < ∣ N θ − m + μ 0 ∣ < log α 20 e − w , μ 0 := − log α log ( 5 g ( α )) .
Lemma 2.4 with u = N u=N u = N , A = 20 / log α A=20/\log\alpha A = 20/ log α , B = e B=e B = e gives w < 121.28 w<121.28 w < 121.28 . Hence γ N ≤ 252 \gamma_N\leq252 γ N ≤ 252 (Case 1) or γ m ≤ 199 \gamma_m\leq199 γ m ≤ 199 (Case 2).
Step 2 (the two gap forms). In Case 1, for each even γ N ∈ [ 2 , 252 ] \gamma_N\in[2,252] γ N ∈ [ 2 , 252 ] , (11) gives, for γ m ≥ 5 \gamma_m\geq5 γ m ≥ 5 ,
0 < ∣ N 1 θ − m + μ 1 ∣ < 11 log α α − γ m , μ 1 : = log ( ( φ γ N − 1 ) / ( 5 g ( α ) ) ) log α , 0<|N_1\theta-m+\mu_1|<\frac{11}{\log\alpha}\alpha^{-\gamma_m},\qquad\mu_1:=\frac{\log((\varphi^{\gamma_N}-1)/(\sqrt{5}g(\alpha)))}{\log\alpha}, 0 < ∣ N 1 θ − m + μ 1 ∣ < log α 11 α − γ m , μ 1 := log α log (( φ γ N − 1 ) / ( 5 g ( α ))) ,
and Lemma 2.4 (u = N 1 u=N_1 u = N 1 , B = α B=\alpha B = α ) bounds γ m \gamma_m γ m . In Case 2, for each γ m ∈ [ 1 , 199 ] \gamma_m\in[1,199] γ m ∈ [ 1 , 199 ] , (12) gives, for γ N ≥ 4 \gamma_N\geq4 γ N ≥ 4 ,
0 < ∣ m 1 θ ′ − N + μ 2 ∣ < 6 log φ φ − γ N , θ ′ : = log α log φ , μ 2 : = log ( 5 g ( α ) ( α γ m − 1 ) ) log φ , 0<|m_1\theta'-N+\mu_2|<\frac{6}{\log\varphi}\varphi^{-\gamma_N},\qquad\theta':=\frac{\log\alpha}{\log\varphi},\qquad\mu_2:=\frac{\log(\sqrt{5}g(\alpha)(\alpha^{\gamma_m}-1))}{\log\varphi}, 0 < ∣ m 1 θ ′ − N + μ 2 ∣ < log φ 6 φ − γ N , θ ′ := log φ log α , μ 2 := log φ log ( 5 g ( α ) ( α γ m − 1 )) ,
and Lemma 2.4 (u = m 1 u=m_1 u = m 1 , B = φ B=\varphi B = φ ) bounds γ N \gamma_N γ N . Together with Step 1, this bounds both gaps (Table 3 ). Note that the bound for γ m \gamma_m γ m comes from Case 1, where Step 1 gives no information on γ m \gamma_m γ m ; it can therefore be larger than the bound γ m ≤ 199 \gamma_m\leq199 γ m ≤ 199 of Step 1 in Case 2.
Table 3. Reduction for Part 1. The column “w < w< w < ” is the bound of Step 1; Step 2 bounds both gaps and Step 3 bounds m 1 m_1 m 1 ; then m ≤ m 1 + γ m m\le m_1+\gamma_m m ≤ m 1 + γ m , and N N N is bounded by Lemma 4.1.
Step 3 (the fourth linear form). For each pair ( γ N , γ m ) (\gamma_N,\gamma_m) ( γ N , γ m ) allowed by Step 2, the bound ∣ Λ 3 ∣ < 6.025 α − m 1 |\Lambda_3| < 6.025\alpha^{-m_1} ∣ Λ 3 ∣ < 6.025 α − m 1 of Section 7 gives, for m 1 ≥ 5 m_1 \ge5 m 1 ≥ 5 ,
0 < ∣ N 1 θ − m 1 + μ 3 ∣ < 12.05 log α α − m 1 , μ 3 : = log ( ( φ γ N − 1 ) / ( 5 g ( α ) ( α γ m − 1 ) ) ) log α , 0 < |N_1\theta-m_1+\mu_3| < \frac{12.05}{\log\alpha}\alpha^{-m_1}, \qquad\mu_3 := \frac{\log\left((\varphi^{\gamma_N}-1)/(\sqrt{5}g(\alpha)(\alpha^{\gamma_m}-1))\right)}{\log\alpha}, 0 < ∣ N 1 θ − m 1 + μ 3 ∣ < log α 12.05 α − m 1 , μ 3 := log α log ( ( φ γ N − 1 ) / ( 5 g ( α ) ( α γ m − 1 )) ) ,
and Lemma 2.4 (u = N 1 u=N_1 u = N 1 , B = α B=\alpha B = α ) bounds m 1 m_1 m 1 . Then m = m 1 + γ m m=m_1+\gamma_m m = m 1 + γ m is bounded, and so is N N N , by Lemma 4.1.
Second pass. We repeat Steps 1–3 with M M M equal to the bound for N N N obtained in the first pass. The results of both passes are given in Table 3 .
Search. Finally, a direct computer search of (8) over all odd N 1 < N ≤ 1501 N_1<N\le1501 N 1 < N ≤ 1501 and all m > m 1 ≥ 2 m>m_1\ge2 m > m 1 ≥ 2 gives exactly the six solutions listed in Theorem 1.3 .
This proves Theorem 1.3 , and with it, via § 2.6 , our main Theorem 1.2 .
Part 2. The k k k -dependent range n > k n>k n > k
More properties of the k k k -Pell sequence
Translating [1 Theorem 3.1 and Lemma 3.2] to the indexing of Definition 1.1, we have the following Binet-type formula for k-Pell
P n ( k ) = f k ( γ ) γ n + e k ( n ) , f k ( γ ) = γ g k ( γ ) = γ k − 1 P k ′ ( γ ) , ∣ e k ( n ) ∣ < 1 2 ( n ≥ 1 − k ) , (14) P_n^{(k)}=f_k(\gamma)\gamma^n+e_k(n), \qquad f_k(\gamma)=\gamma g_k(\gamma)=\frac{\gamma^{k-1}}{P_k'(\gamma)}, \qquad|e_k(n)|<\frac{1}{2}\quad(n\ge1-k), \tag*{(14)} P n ( k ) = f k ( γ ) γ n + e k ( n ) , f k ( γ ) = γ g k ( γ ) = P k ′ ( γ ) γ k − 1 , ∣ e k ( n ) ∣ < 2 1 ( n ≥ 1 − k ) , (14)
where
g k ( z ) = z − 1 ( k + 1 ) z 2 − 3 k z + k − 1 g_k(z)=\frac{z-1}{(k+1)z^2-3kz+k-1} g k ( z ) = ( k + 1 ) z 2 − 3 k z + k − 1 z − 1
and 0.276 < g k ( γ ) < 0.5 0.276<g_k(\gamma)<0.5 0.276 < g k ( γ ) < 0.5 , and
γ n − 1 ≤ P n ( k ) ≤ γ n ( n ≥ 0 ) . (15) \gamma^{n-1}\le P_n^{(k)}\le\gamma^n\quad(n\ge0). \tag*{(15)} γ n − 1 ≤ P n ( k ) ≤ γ n ( n ≥ 0 ) . (15)
We frist prove the following lemmas.
Lemma 9.1. For every k ≥ 2 k\ge2 k ≥ 2 , ( x − 1 ) P k ( x ) = x k + 1 − 3 x k + x k − 1 + 1 (x-1)P_k(x)=x^{k+1}-3x^k+x^{k-1}+1 ( x − 1 ) P k ( x ) = x k + 1 − 3 x k + x k − 1 + 1 .
Proof. ( x − 1 ) P k ( x ) = ( x − 1 ) ( x k − 2 x k − 1 − ∑ i = 0 k − 2 x i ) = x k + 1 − 2 x k − ∑ i = 1 k − 1 x i − x k + 2 x k − 1 + ∑ i = 0 k − 2 x i (x-1)P_k(x)=(x-1)\left(x^k-2x^{k-1}-\sum_{i=0}^{k-2}x^i\right)=x^{k+1}-2x^k-\sum_{i=1}^{k-1}x^i-x^k+2x^{k-1}+\sum_{i=0}^{k-2}x^i ( x − 1 ) P k ( x ) = ( x − 1 ) ( x k − 2 x k − 1 − ∑ i = 0 k − 2 x i ) = x k + 1 − 2 x k − ∑ i = 1 k − 1 x i − x k + 2 x k − 1 + ∑ i = 0 k − 2 x i . The x k x^k x k coefficient is − 3 -3 − 3 ; the x k − 1 x^{k-1} x k − 1 coefficient is 1; for 1 ≤ i ≤ k − 2 1\le i\le k-2 1 ≤ i ≤ k − 2 , the coefficient of x i x^i x i is 0; the constant term is 1. □
Lemma 9.2. D ( k ) : = [ Q ( γ ( k ) , α ) : Q ] ≤ 3 k D(k):=[\mathbb{Q}(\gamma(k),\alpha):\mathbb{Q}]\le3k D ( k ) := [ Q ( γ ( k ) , α ) : Q ] ≤ 3 k , with equality in particular when 3 ∤ k 3\nmid k 3 ∤ k .
Proof. [ Q ( γ ( k ) ) : Q ] = deg P k = k [\mathbb{Q}(\gamma(k)):\mathbb{Q}]=\deg P_k=k [ Q ( γ ( k )) : Q ] = deg P k = k and [ Q ( α ) : Q ] = 3 [\mathbb{Q}(\alpha):\mathbb{Q}]=3 [ Q ( α ) : Q ] = 3 , so D ( k ) ≤ 3 k D(k)\le3k D ( k ) ≤ 3 k , and D ( k ) D(k) D ( k ) is divisible by k k k and by 3, hence equals 3 k 3k 3 k when 3 ∤ k 3\nmid k 3 ∤ k . □
Lemma 9.3. h ( γ ( k ) ) = log γ ( k ) k < log φ 2 k h(\gamma(k))=\frac{\log\gamma(k)}{k}<\frac{\log\varphi^2}{k} h ( γ ( k )) = k l o g γ ( k ) < k l o g φ 2 for every k k k .
Proof. P k P_k P k is monic and irreducible, with exactly one root of modulus > 1 >1 > 1 , so
h ( γ ) = 1 k log M ( P k ) = 1 k log γ . h(\gamma)=\frac{1}{k}\log M(P_k)=\frac{1}{k}\log\gamma. h ( γ ) = k 1 log M ( P k ) = k 1 log γ .
□
For k ≥ 4 k \ge4 k ≥ 4 we use the following bounds from [2 Lemmas 3 and 6]
Lemma 9.4. For every k ≥ 2 k \ge2 k ≥ 2 , h ( g k ( γ ) ) < 4 log φ + log ( k + 1 ) h(g_k(\gamma)) < 4 \log\varphi+ \log(k+1) h ( g k ( γ )) < 4 log φ + log ( k + 1 ) , and ∣ g k ( γ ′ ) ∣ < 1 |g_k(\gamma')| < 1 ∣ g k ( γ ′ ) ∣ < 1 for every conjugate γ ′ ≠ γ \gamma' \ne\gamma γ ′ = γ of γ \gamma γ . Consequently h ( f k ( γ ) ) < 4 log φ + log ( k + 1 ) + log φ 2 k h(f_k(\gamma)) < 4 \log\varphi+ \log(k+1) + \frac{\log\varphi^2}{k} h ( f k ( γ )) < 4 log φ + log ( k + 1 ) + k l o g φ 2 and ∣ f k ( γ ′ ) ∣ < 1 |f_k(\gamma')| < 1 ∣ f k ( γ ′ ) ∣ < 1 .
Moreover, for k ≥ 4 k \ge4 k ≥ 4 we have [ Q ( γ , α ) : Q ( α ) ] ≥ k / 3 > 1 [\mathbb{Q}(\gamma,\alpha):\mathbb{Q}(\alpha)] \ge k/3 > 1 [ Q ( γ , α ) : Q ( α )] ≥ k /3 > 1 , so there is an automorphism σ \sigma σ of the Galois closure of Q ( γ , α ) \mathbb{Q}(\gamma,\alpha) Q ( γ , α ) with σ ( α ) = α \sigma(\alpha)=\alpha σ ( α ) = α and σ ( γ ) = γ ′ ≠ γ \sigma(\gamma)=\gamma' \ne\gamma σ ( γ ) = γ ′ = γ ; then ∣ γ ′ ∣ < 1 |\gamma'| < 1 ∣ γ ′ ∣ < 1 and ∣ f k ( γ ′ ) ∣ < 1 |f_k(\gamma')| < 1 ∣ f k ( γ ′ ) ∣ < 1 . This replaces, for k ≥ 4 k \ge4 k ≥ 4 , the condition Q ( γ ) ∩ Q ( α ) = Q \mathbb{Q}(\gamma) \cap\mathbb{Q}(\alpha)=\mathbb{Q} Q ( γ ) ∩ Q ( α ) = Q used below for k = 2 , 3 k=2,3 k = 2 , 3 in the proofs that the linear forms do not vanish.
In Sections 10–13, k ∈ { 2 , 3 } k \in\{2,3\} k ∈ { 2 , 3 } . For k = 2 k=2 k = 2 , γ = 1 + 2 \gamma=1+\sqrt{2} γ = 1 + 2 and D ( 2 ) = 6 D(2)=6 D ( 2 ) = 6 . For k = 3 k=3 k = 3 , γ > 2.546818 \gamma>2.546818 γ > 2.546818 , and D ( 3 ) ≤ 9 D(3)\le9 D ( 3 ) ≤ 9 ; moreover Q ( γ ( 3 ) ) ≠ Q ( α ) \mathbb{Q}(\gamma^{(3)}) \ne\mathbb{Q}(\alpha) Q ( γ ( 3 ) ) = Q ( α ) , since the discriminant of P 3 ( x ) = x 3 − 2 x 2 − x − 1 P_3(x)=x^3-2x^2-x-1 P 3 ( x ) = x 3 − 2 x 2 − x − 1 is − 87 -87 − 87 , which is squarefree, so that the cubic field Q ( γ ( 3 ) ) \mathbb{Q}(\gamma^{(3)}) Q ( γ ( 3 ) ) has discriminant − 87 -87 − 87 , while Q ( α ) \mathbb{Q}(\alpha) Q ( α ) has discriminant − 44 -44 − 44 ; therefore Q ( γ ( 3 ) ) ∩ Q ( α ) = Q \mathbb{Q}(\gamma^{(3)}) \cap\mathbb{Q}(\alpha)=\mathbb{Q} Q ( γ ( 3 ) ) ∩ Q ( α ) = Q . Likewise Q ( 2 ) ∩ Q ( α ) = Q \mathbb{Q}(\sqrt{2}) \cap\mathbb{Q}(\alpha)=\mathbb{Q} Q ( 2 ) ∩ Q ( α ) = Q . The conjugates of γ ( 3 ) \gamma^{(3)} γ ( 3 ) other than γ ( 3 ) \gamma^{(3)} γ ( 3 ) have modulus γ ( 3 ) − 1 / 2 > 0.6266 \gamma^{(3)-1/2}>0.6266 γ ( 3 ) − 1/2 > 0.6266 .
Lemma 9.5 (Exact heights for k = 2 , 3 k=2,3 k = 2 , 3 ). The number f 2 ( γ ) = 2 + 2 4 f_2(\gamma)=\frac{2+\sqrt{2}}{4} f 2 ( γ ) = 4 2 + 2 is a root of the irreducible polynomial 8 x 2 − 8 x + 1 8x^2-8x+1 8 x 2 − 8 x + 1 , and f 3 ( γ ) < 0.79 f_3(\gamma)<0.79 f 3 ( γ ) < 0.79 is a root of the irreducible polynomial 87 x 3 − 87 x 2 + 16 x − 1 87x^3-87x^2+16x-1 87 x 3 − 87 x 2 + 16 x − 1 . All the conjugates of f k ( γ ) f_k(\gamma) f k ( γ ) have modulus less than 1. Consequently
h ( f 2 ( γ ) ) = log 8 2 , h ( f 3 ( γ ) ) = log 87 3 . h(f_2(\gamma))=\frac{\log8}{2}, \qquad h(f_3(\gamma))=\frac{\log87}{3}. h ( f 2 ( γ )) = 2 log 8 , h ( f 3 ( γ )) = 3 log 87 .
Proof. For k = 3 k=3 k = 3 we computed f 3 ( γ ) = γ ( γ − 1 ) / ( 4 γ 2 − 9 γ + 2 ) f_3(\gamma)=\gamma(\gamma-1)/(4\gamma^2-9\gamma+2) f 3 ( γ ) = γ ( γ − 1 ) / ( 4 γ 2 − 9 γ + 2 ) as an element of Q ( γ ) = Q [ x ] / ( P 3 ) \mathbb{Q}(\gamma)=\mathbb{Q}[x]/(P_3) Q ( γ ) = Q [ x ] / ( P 3 ) and checked, in exact rational arithmetic, that it is a root of 87 x 3 − 87 x 2 + 16 x − 1 87x^3-87x^2+16x-1 87 x 3 − 87 x 2 + 16 x − 1 , which has no rational root, hence is irreducible. For k = 2 k=2 k = 2 the computation is immediate. The moduli of the conjugates follow from the numerical values of the roots of P k P_k P k .
We use Matveev’s theorem and the Dujella–Pethő reduction lemma exactly as in Section 2, with D = D ( k ) D=D(k) D = D ( k ) : D = 6 D=6 D = 6 for k = 2 k=2 k = 2 and D = 9 D=9 D = 9 for k = 3 k=3 k = 3 . We write f : = f k ( γ ) f:=f_k(\gamma) f := f k ( γ ) and e n : = e k ( n ) e_n:=e_k(n) e n := e k ( n ) .
Setup
Fix k ∈ { 2 , 3 } k \in\{2,3\} k ∈ { 2 , 3 } . Suppose c = P n ( k ) − T m = P n 1 ( k ) − T m 1 c=P_n^{(k)}-T_m=P_{n_1}^{(k)}-T_{m_1} c = P n ( k ) − T m = P n 1 ( k ) − T m 1 with ( n , m ) ≠ ( n 1 , m 1 ) (n,m)\ne(n_1,m_1) ( n , m ) = ( n 1 , m 1 ) , m , m 1 ≥ 2 m,m_1\ge2 m , m 1 ≥ 2 and max ( n , n 1 ) > k \max(n,n_1)>k max ( n , n 1 ) > k . As in Section 3, P n ( k ) P_n^{(k)} P n ( k ) is strictly increasing for n ≥ 0 n\ge0 n ≥ 0 , then n = n 1 n=n_1 n = n 1 forces m = m 1 m=m_1 m = m 1 , so n ≠ n 1 n\ne n_1 n = n 1 ; Write γ n : = n − n 1 ≥ 1 \gamma_n:=n-n_1\ge1 γ n := n − n 1 ≥ 1 , γ m : = m − m 1 ≥ 1 \gamma_m:=m-m_1\ge1 γ m := m − m 1 ≥ 1 , so
P n ( k ) − P n 1 ( k ) = T m − T m 1 . (16) P_n^{(k)}-P_{n_1}^{(k)}=T_m-T_{m_1}. \tag*{(16)} P n ( k ) − P n 1 ( k ) = T m − T m 1 . (16)
A direct computer search over n ≤ 398 n\le398 n ≤ 398 gives exactly the solutions with n > k n>k n > k listed in Theorems 1.4 and 1.5; together with Theorem 1.2 for the range n ≤ k n\le k n ≤ k , this gives the full lists. We assume from now on n ≥ 10 n\ge10 n ≥ 10 , and show that n ≤ 303 n\le303 n ≤ 303 (k = 2 k=2 k = 2 ), respectively n ≤ 285 n\le285 n ≤ 285 (k = 3 k=3 k = 3 ). The starting point n ≥ 10 n\ge10 n ≥ 10 is chosen so that m < 2 n m<2n m < 2 n (Section 11), which allows B = 2 n B=2n B = 2 n in Matveev’s theorem. The largest solution is ( 9 , 15 , 6 , 13 ; − 758 ) (9,15,6,13;-758) ( 9 , 15 , 6 , 13 ; − 758 ) for k = 2 k=2 k = 2 .
Size relation and first linear form
Using P n ( k ) − P n − 1 ( k ) ≥ P n − 1 ( k ) P_n^{(k)}-P_{n-1}^{(k)}\ge P_{n-1}^{(k)} P n ( k ) − P n − 1 ( k ) ≥ P n − 1 ( k ) in place of the exact Fibonacci identity, together with (15), (6) and T m ≤ α m − 1 T_m\le\alpha^{m-1} T m ≤ α m − 1 give
n < 1 + log α log γ m + log ( 2.1744 ) log γ , m < 2 + log γ log α n + log ( 4.667 ) log α . n<1+\frac{\log\alpha}{\log\gamma}m+\frac{\log(2.1744)}{\log\gamma}, \qquad m<2+\frac{\log\gamma}{\log\alpha}n+\frac{\log(4.667)}{\log\alpha}. n < 1 + log γ log α m + log γ log ( 2.1744 ) , m < 2 + log α log γ n + log α log ( 4.667 ) .
and also ( n − 2 ) log γ < ( m − 1 ) log α (n-2)\log\gamma< (m-1)\log\alpha ( n − 2 ) log γ < ( m − 1 ) log α , since γ n − 2 ≤ P n − 1 ( k ) ≤ P n ( k ) − P n 1 ( k ) < T m ≤ α m − 1 \gamma^{n-2} \le P_{n-1}^{(k)} \le P_n^{(k)}-P_{n_1}^{(k)} < T_m \le\alpha^{m-1} γ n − 2 ≤ P n − 1 ( k ) ≤ P n ( k ) − P n 1 ( k ) < T m ≤ α m − 1 . In particular m < 2 n m<2n m < 2 n for n ≥ 10 n\ge10 n ≥ 10 , so we may take B = 2 n B=2n B = 2 n below. Bounding ∣ c ∣ < max ( γ n 1 , α m 1 ) |c|<\max(\gamma^{n_1},\alpha^{m_1}) ∣ c ∣ < max ( γ n 1 , α m 1 ) as before and using (14) and (4) on the large representation, we get
∣ f γ n − g ( α ) α m ∣ < 1.9 max ( γ n 1 , α m 1 ) , |f\gamma^n-g(\alpha)\alpha^m|<1.9\max(\gamma^{n_1},\alpha^{m_1}), ∣ f γ n − g ( α ) α m ∣ < 1.9 max ( γ n 1 , α m 1 ) ,
dividing by g ( α ) α m g(\alpha)\alpha^m g ( α ) α m , with Λ : = f g ( α ) γ n α − m − 1 \Lambda:=\frac{f}{g(\alpha)}\gamma^n\alpha^{-m}-1 Λ := g ( α ) f γ n α − m − 1 and γ n α − m < 0.5436 γ 2 \gamma^n\alpha^{-m}<0.5436\gamma^2 γ n α − m < 0.5436 γ 2 , we get
∣ Λ ∣ < c 0 max ( γ − γ n , α − γ m ) , c 0 : = 1.9 ⋅ 0.5436 γ 2 g ( α ) < { 18 ( k = 2 ) , 20 ( k = 3 ) . |\Lambda|<c_0\max(\gamma^{-\gamma n},\alpha^{-\gamma m}),\qquad c_0:=\frac{1.9\cdot0.5436\gamma^2}{g(\alpha)}<\begin{cases}18 & (k=2),\\20 & (k=3).\end{cases} ∣Λ∣ < c 0 max ( γ − γ n , α − γ m ) , c 0 := g ( α ) 1.9 ⋅ 0.5436 γ 2 < { 18 20 ( k = 2 ) , ( k = 3 ) .
We have Λ ≠ 0 \Lambda\ne0 Λ = 0 since otherwise f γ n = g ( α ) α m f\gamma^n=g(\alpha)\alpha^m f γ n = g ( α ) α m would belong to Q ( γ ) ∩ Q ( α ) = Q \mathbb{Q}(\gamma)\cap\mathbb{Q}(\alpha)=\mathbb{Q} Q ( γ ) ∩ Q ( α ) = Q ; but applying to f γ n f\gamma^n f γ n an embedding of Q ( γ ) \mathbb{Q}(\gamma) Q ( γ ) sending γ \gamma γ to a conjugate γ ′ ≠ γ \gamma'\ne\gamma γ ′ = γ we would get f γ n = ∣ f ′ γ ′ n ∣ < 1 f\gamma^n=|f'\gamma'{}^n|<1 f γ n = ∣ f ′ γ ′ n ∣ < 1 (Lemma 9.5 and ∣ γ ′ ∣ < 1 |\gamma'|<1 ∣ γ ′ ∣ < 1 ), which is false for n ≥ 1 n\ge1 n ≥ 1 . Applying Matveev’s theorem with t = 3 t=3 t = 3 , η 1 = γ \eta_1=\gamma η 1 = γ , b 1 = n b_1=n b 1 = n ; η 2 = α \eta_2=\alpha η 2 = α , b 2 = − m b_2=-m b 2 = − m ; η 3 = f / g ( α ) \eta_3=f/g(\alpha) η 3 = f / g ( α ) , b 3 = 1 b_3=1 b 3 = 1 ; A 1 = D h ( γ ) = 3 log γ A_1=D h(\gamma)=3\log\gamma A 1 = D h ( γ ) = 3 log γ , A 2 = D h ( α ) = D 3 log α A_2=D h(\alpha)=\frac{D}{3}\log\alpha A 2 = D h ( α ) = 3 D log α , A 3 = D ( h ( f ) + h ( g ( α ) ) ) A_3=D(h(f)+h(g(\alpha))) A 3 = D ( h ( f ) + h ( g ( α ))) (by Lemmas 9.3 and 9.5) and B = 2 n B=2n B = 2 n , we get
Proposition 11.1. For k ∈ { 2 , 3 } k\in\{2,3\} k ∈ { 2 , 3 } , min { γ n log γ , γ m log α } < K 1 ( k ) ( 1 + log 2 n ) \min\{\gamma^n\log\gamma,\gamma^m\log\alpha\}<K_1(k)(1+\log2n) min { γ n log γ , γ m log α } < K 1 ( k ) ( 1 + log 2 n ) , with K 1 ( 2 ) = 6.403 × 10 14 K_1(2)=6.403\times10^{14} K 1 ( 2 ) = 6.403 × 1 0 14 and K 1 ( 3 ) = 4.706 × 10 15 K_1(3)=4.706\times10^{15} K 1 ( 3 ) = 4.706 × 1 0 15 .
Here ( A 1 , A 2 , A 3 ) = ( 2.6441 , 1.2188 , 13.8067 ) (A_1,A_2,A_3)=(2.6441,1.2188,13.8067) ( A 1 , A 2 , A 3 ) = ( 2.6441 , 1.2188 , 13.8067 ) for k = 2 k=2 k = 2 and ( 2.8045 , 1.8281 , 24.7503 ) (2.8045,1.8281,24.7503) ( 2.8045 , 1.8281 , 24.7503 ) for k = 3 k=3 k = 3 .
Secondary forms and the absolute bound
Exactly as in Sections 6–7, with γ , f \gamma,f γ , f in place of φ , 1 / 5 \varphi,1/\sqrt{5} φ , 1/ 5 , we have that
Case 1 ( γ n log γ ≤ γ m log α ) (\gamma^n\log\gamma\le\gamma^m\log\alpha) ( γ n log γ ≤ γ m log α ) . We put
Λ 1 : = f ( γ n − 1 ) g ( α ) γ n 1 α − m − 1 , ∣ Λ 1 ∣ < 2.85 α − γ m \Lambda_1:=\frac{f(\gamma^n-1)}{g(\alpha)}\gamma^{n_1}\alpha^{-m}-1,\qquad|\Lambda_1|<2.85\alpha^{-\gamma m} Λ 1 := g ( α ) f ( γ n − 1 ) γ n 1 α − m − 1 , ∣ Λ 1 ∣ < 2.85 α − γ m
(using ∣ e n ∣ + ∣ e n 1 ∣ + ∣ e ( m ) ∣ < 1.4 |e_n|+|e_{n_1}|+|e(m)|<1.4 ∣ e n ∣ + ∣ e n 1 ∣ + ∣ e ( m ) ∣ < 1.4 and T m 1 < 0.5436 α m 1 T_{m_1}<0.5436\alpha^{m_1} T m 1 < 0.5436 α m 1 , the numerator is less than ( 0.5436 + 1.4 α − m 1 ) α m 1 (0.5436+1.4\alpha^{-m_1})\alpha^{m_1} ( 0.5436 + 1.4 α − m 1 ) α m 1 , and ( 0.5436 + 1.4 α − 2 ) / g ( α ) < 2.85 (0.5436+1.4\alpha^{-2})/g(\alpha)<2.85 ( 0.5436 + 1.4 α − 2 ) / g ( α ) < 2.85 ), and D h ( f ( γ n − 1 ) / g ( α ) ) ≤ 3 γ n log γ + D ( h ( f ) + log 2 + h ( g ( α ) ) ) D h(f(\gamma^n-1)/g(\alpha))\le3\gamma^n\log\gamma+D(h(f)+\log2+h(g(\alpha))) D h ( f ( γ n − 1 ) / g ( α )) ≤ 3 γ n log γ + D ( h ( f ) + log 2 + h ( g ( α ))) . If n 1 = 0 n_1=0 n 1 = 0 the form has only two terms, and Matveev’s theorem with t = 2 t=2 t = 2 gives a smaller bound.
Case 2 ( γ m log α ≤ γ n log γ ) (\gamma^m\log\alpha\le\gamma^n\log\gamma) ( γ m log α ≤ γ n log γ ) . We put
Λ 2 : = g ( α ) ( α γ m − 1 ) f α m 1 γ − n − 1 , ∣ Λ 2 ∣ < 2.3 f γ − γ n < 3 γ − γ n , \Lambda_2:=\frac{g(\alpha)(\alpha^{\gamma m}-1)}{f}\alpha^{m_1}\gamma^{-n}-1,\qquad|\Lambda_2|<\frac{2.3}{f}\gamma^{-\gamma n}<3\gamma^{-\gamma n}, Λ 2 := f g ( α ) ( α γ m − 1 ) α m 1 γ − n − 1 , ∣ Λ 2 ∣ < f 2.3 γ − γ n < 3 γ − γ n ,
and D h ( g ( α ) ( α γ m − 1 ) / f ) ≤ D 3 γ m log α + D ( h ( f ) + log 2 + h ( g ( α ) ) ) D h(g(\alpha)(\alpha^{\gamma m}-1)/f)\le\frac{D}{3}\gamma^m\log\alpha+D(h(f)+\log2+h(g(\alpha))) D h ( g ( α ) ( α γ m − 1 ) / f ) ≤ 3 D γ m log α + D ( h ( f ) + log 2 + h ( g ( α ))) .
Fourth form. We put
Λ 3 : = f ( γ n − 1 ) g ( α ) ( α γ m − 1 ) γ n 1 α − m 1 − 1 , ∣ Λ 3 ∣ < 1.8 g ( α ) ( α − 1 ) α − m 1 < 6.38 α − m 1 . \Lambda_3:=\frac{f(\gamma^n-1)}{g(\alpha)(\alpha^{\gamma m}-1)}\gamma^{n_1}\alpha^{-m_1}-1,\qquad|\Lambda_3|<\frac{1.8}{g(\alpha)(\alpha-1)}\alpha^{-m_1}<6.38\alpha^{-m_1}. Λ 3 := g ( α ) ( α γ m − 1 ) f ( γ n − 1 ) γ n 1 α − m 1 − 1 , ∣ Λ 3 ∣ < g ( α ) ( α − 1 ) 1.8 α − m 1 < 6.38 α − m 1 .
The forms Λ 1 , Λ 2 , Λ 3 \Lambda_1,\Lambda_2,\Lambda_3 Λ 1 , Λ 2 , Λ 3 do not vanish because of the same reason as before. In fact we would have f ( γ n − γ n 1 ) f(\gamma^n-\gamma^{n_1}) f ( γ n − γ n 1 ) being rational, and an embedding as above would give f ( γ n − γ n 1 ) < 2 f(\gamma^n-\gamma^{n_1})<2 f ( γ n − γ n 1 ) < 2 , which is false since f ( γ n − γ n 1 ) ≥ f γ n − 1 ( γ − 1 ) > 2 f(\gamma^n-\gamma^{n_1})\ge f\gamma^{n-1}(\gamma-1)>2 f ( γ n − γ n 1 ) ≥ f γ n − 1 ( γ − 1 ) > 2 for n ≥ 10 n\ge10 n ≥ 10 . Similarly f γ n f\gamma^n f γ n is irrational for Λ 2 \Lambda_2 Λ 2 . Matveev’s theorem then gives, with X : = 1 + log 2 n X:=1+\log2n X := 1 + log 2 n ,
γ m log α < K 2 ( k ) X 2 (Case 1) , γ n log γ < K 3 ( k ) X 2 (Case 2) , m 1 log α < K 4 ( k ) X 3 , \gamma^m\log\alpha<K_2(k)X^2\quad\text{(Case 1)},\qquad
\gamma^n\log\gamma<K_3(k)X^2\quad\text{(Case 2)},\qquad
m_1\log\alpha<K_4(k)X^3, γ m log α < K 2 ( k ) X 2 (Case 1) , γ n log γ < K 3 ( k ) X 2 (Case 2) , m 1 log α < K 4 ( k ) X 3 ,
with
Table 1 (PDF p. 12).
Since ( n − 2 ) log γ < ( m − 1 ) log α < ( m 1 + γ m ) log α (n-2)\log\gamma< (m-1)\log\alpha< (m_1+\gamma_m)\log\alpha ( n − 2 ) log γ < ( m − 1 ) log α < ( m 1 + γ m ) log α , this gives an absolute bound:
n < 3.65 × 10 49 ( k = 2 ) , n < 5.79 × 10 51 ( k = 3 ) . n < 3.65 \times10^{49}\quad(k=2),\qquad n < 5.79 \times10^{51}\quad(k=3). n < 3.65 × 1 0 49 ( k = 2 ) , n < 5.79 × 1 0 51 ( k = 3 ) .
Reduction: k = 2 k=2 k = 2 and k = 3 k=3 k = 3
We run the three steps of § 3.6 , with θ k : = log γ / log α \theta_k := \log\gamma/\log\alpha θ k := log γ / log α and θ k ′ : = 1 / θ k \theta'_k := 1/\theta_k θ k ′ := 1/ θ k . Since u = m 1 u=m_1 u = m 1 in Step 2 (Case 2), the integer M M M of Lemma 2.4 must bound m 1 m_1 m 1 as well as n n n ; as m < 2 n m<2n m < 2 n , we take M M M larger than twice the bound for n n n in the first pass, and equal to the bound for m m m in the second pass. The inequalities below are used when their right-hand sides are less than 1, that is, for w > log ( 2 c 0 ) w>\log(2c_0) w > log ( 2 c 0 ) , γ m ≥ 3 \gamma_m\geq3 γ m ≥ 3 , γ n ≥ 2 \gamma_n\geq2 γ n ≥ 2 and m 1 ≥ 5 m_1\geq5 m 1 ≥ 5 . The other cases give smaller bounds.
Step 1: 0 < ∣ n θ k − m + μ 0 ∣ < 2 c 0 log α e − w 0<|n\theta_k-m+\mu_0|<\frac{2c_0}{\log\alpha}e^{-w} 0 < ∣ n θ k − m + μ 0 ∣ < l o g α 2 c 0 e − w , μ 0 = log ( f / g ( α ) ) log α \mu_0=\frac{\log(f/g(\alpha))}{\log\alpha} μ 0 = l o g α l o g ( f / g ( α )) , w = min { γ n log γ , γ m log α } w=\min\{\gamma_n\log\gamma,\gamma_m\log\alpha\} w = min { γ n log γ , γ m log α } ;
Step 2: in Case 1, for each γ n \gamma_n γ n , 0 < ∣ n 1 θ k − m + μ 1 ∣ < 5.7 log α γ − m 0<|n_1\theta_k-m+\mu_1|<\frac{5.7}{\log\alpha}\gamma^{-m} 0 < ∣ n 1 θ k − m + μ 1 ∣ < l o g α 5.7 γ − m (if n 1 = 0 n_1=0 n 1 = 0 , then n = γ n n=\gamma_n n = γ n is already bounded by Step 1). In Case 2, for each γ m \gamma_m γ m , 0 < ∣ m 1 θ k ′ − n + μ 2 ∣ < 4.6 f log γ γ − n 0<|m_1\theta'_k-n+\mu_2|<\frac{4.6}{f\log\gamma}\gamma^{-n} 0 < ∣ m 1 θ k ′ − n + μ 2 ∣ < f l o g γ 4.6 γ − n ;
Step 3: for each pair ( γ n , γ m ) (\gamma_n,\gamma_m) ( γ n , γ m ) , 0 < ∣ n 1 θ k − m 1 + μ 3 ∣ < 12.76 log α α − m 1 0<|n_1\theta_k-m_1+\mu_3|<\frac{12.76}{\log\alpha}\alpha^{-m_1} 0 < ∣ n 1 θ k − m 1 + μ 3 ∣ < l o g α 12.76 α − m 1 (if n 1 = 0 n_1=0 n 1 = 0 , then n = γ n n=\gamma_n n = γ n is bounded by Step 2),
where μ 1 , μ 2 , μ 3 \mu_1,\mu_2,\mu_3 μ 1 , μ 2 , μ 3 are the logarithms of the third numbers η 3 \eta_3 η 3 of § 4.4 divided by log α \log\alpha log α , log γ \log\gamma log γ , log α \log\alpha log α , respectively. In every case Lemma 2.4 applies. In the first pass, Step 1 gives γ n ≤ 139 \gamma_n\leq139 γ n ≤ 139 or γ m ≤ 202 \gamma_m\leq202 γ m ≤ 202 for k = 2 k=2 k = 2 , and γ n ≤ 136 \gamma_n\leq136 γ n ≤ 136 or γ m ≤ 209 \gamma_m\leq209 γ m ≤ 209 for k = 3 k=3 k = 3 . The other results are given in Table 4 .
Table 4. Reduction for k = 2 k=2 k = 2 and k = 3 k=3 k = 3 (same columns as Table 3 ; the bound for n n n follows from ( n − 2 ) log γ < ( m − 1 ) log α (n-2)\log\gamma< (m-1)\log\alpha ( n − 2 ) log γ < ( m − 1 ) log α ).
Proof of Theorems 1.4 and 1.5 . By Table 4 , every solution with n > k n>k n > k has n ≤ 39 n\leq39 n ≤ 39 (k = 2 k=2 k = 2 ), respectively n ≤ 37 n\leq37 n ≤ 37 (k = 3 k=3 k = 3 ), and the search of § 4.2 gives the solutions listed in the two theorems. □
Corollary 1.7 follows by grouping the solutions of Theorems 1.4 and 1.5 according to the value of c c c .
A bound for n n n uniform in k ≥ 4 k\geq4 k ≥ 4
Let k ≥ 4 k\geq4 k ≥ 4 and let ( n , m , n 1 , m 1 ) (n,m,n_1,m_1) ( n , m , n 1 , m 1 ) be a solution of (16) with n > k n>k n > k and n ≥ 10 n\geq10 n ≥ 10 . The solutions with n ≤ 9 n\leq9 n ≤ 9 are found by the search of Section 16. The arguments of § 4.3 and § 4.4 can be applied, with the following changes. The linear forms Λ , Λ 1 , Λ 2 , Λ 3 \Lambda,\Lambda_1,\Lambda_2,\Lambda_3 Λ , Λ 1 , Λ 2 , Λ 3 do not vanish by the same arguments, using the automorphism σ \sigma σ described after Lemma 9.4. In Matveev’s theorem we take D = 3 k D=3k D = 3 k (Lemma 9.2 ), A 1 = 3 log φ 2 ≥ 3 log γ A_1=3\log\varphi^2\geq3\log\gamma A 1 = 3 log φ 2 ≥ 3 log γ , A 2 = k log α A_2=k\log\alpha A 2 = k log α and, by Lemma 9.4,
h ( f ) + h ( g ( α ) ) < H ( k ) : = 4 log φ + log ( k + 1 ) + log φ 2 k + log 44 3 . h(f)+h(g(\alpha))<H(k):=4\log\varphi+\log(k+1)+\frac{\log\varphi^2}{k}+\frac{\log44}{3}. h ( f ) + h ( g ( α )) < H ( k ) := 4 log φ + log ( k + 1 ) + k log φ 2 + 3 log 44 .
Since γ < φ 2 \gamma<\varphi^2 γ < φ 2 and f = γ g k ( γ ) > 0.71 f=\gamma g_k(\gamma)>0.71 f = γ g k ( γ ) > 0.71 , the constants of § 4.3 –§ 4.4 become c 0 < 21.06 c_0<21.06 c 0 < 21.06 , c 1 < 2.85 c_1<2.85 c 1 < 2.85 , 2.3 / f < 3.22 2.3/f<3.22 2.3/ f < 3.22 and 6.38 6.38 6.38 . With C ( 3 k ) = 1.4 ⋅ 3 06 ⋅ 3 4.5 ⋅ 9 k 2 ( 1 + log 3 k ) C(3k)=1.4\cdot3^{06}\cdot3^{4.5}\cdot9k^2(1+\log3k) C ( 3 k ) = 1.4 ⋅ 3 06 ⋅ 3 4.5 ⋅ 9 k 2 ( 1 + log 3 k ) and A : = C ( 3 k ) A 1 A 2 A := C(3k)A_1A_2 A := C ( 3 k ) A 1 A 2 , we get min { γ n log γ , γ m log α } < K 1 ( k ) X \min\{\gamma_n\log\gamma,\gamma_m\log\alpha\}<K_1(k)X min { γ n log γ , γ m log α } < K 1 ( k ) X , γ m log α < K 2 ( k ) X 2 \gamma_m\log\alpha<K_2(k)X^2 γ m log α < K 2 ( k ) X 2 (Case 1), γ n log γ < K 3 ( k ) X 2 \gamma_n\log\gamma<K_3(k)X^2 γ n log γ < K 3 ( k ) X 2 (Case 2) and m 1 log α < K 4 ( k ) X 3 m_1\log\alpha<K_4(k)X^3 m 1 log α < K 4 ( k ) X 3 , where X = 1 + log 2 n X=1+\log2n X = 1 + log 2 n and
K 1 ( k ) = 3 k A H ( k ) + log 21.06 , K_1(k)=3kAH(k)+\log21.06, K 1 ( k ) = 3 k A H ( k ) + log 21.06 ,
K 2 ( k ) = A ( 3 K 1 ( k ) + 3 k ( H ( k ) + log 2 ) ) + log 2.85 , K_2(k)=A\bigl(3K_1(k)+3k(H(k)+\log2)\bigr)+\log2.85, K 2 ( k ) = A ( 3 K 1 ( k ) + 3 k ( H ( k ) + log 2 ) ) + log 2.85 ,
K 3 ( k ) = A ( k K 1 ( k ) + 3 k ( H ( k ) + log 2 ) ) + log 3.22 , K_3(k)=A\bigl(kK_1(k)+3k(H(k)+\log2)\bigr)+\log3.22, K 3 ( k ) = A ( k K 1 ( k ) + 3 k ( H ( k ) + log 2 ) ) + log 3.22 ,
K 4 ( k ) = A ( ( k + 3 ) max { K 2 ( k ) , K 3 ( k ) } + 3 k ( H ( k ) + 2 log 2 ) ) + log 6.38. K_4(k)=A\bigl((k+3)\max\{K_2(k),K_3(k)\}+3k(H(k)+2\log2)\bigr)+\log6.38. K 4 ( k ) = A ( ( k + 3 ) max { K 2 ( k ) , K 3 ( k )} + 3 k ( H ( k ) + 2 log 2 ) ) + log 6.38.
Since ( n − 2 ) log γ < ( m 1 + γ m ) log α (n-2)\log\gamma<(m_1+\gamma_m)\log\alpha ( n − 2 ) log γ < ( m 1 + γ m ) log α and γ ≥ γ ( 4 ) > 2.592 \gamma\ge\gamma(4)>2.592 γ ≥ γ ( 4 ) > 2.592 [1 Lemma 3.2] , we obtain:
Proposition 14.1. Let k ≥ 4 k\ge4 k ≥ 4 . Every solution of (16) with n > k n>k n > k and n ≥ 10 n\ge10 n ≥ 10 satisfies n < N ( k ) n<\mathcal{N}(k) n < N ( k ) , where N ( k ) \mathcal{N}(k) N ( k ) is the largest real solution of
x = 2 + K 4 ( k ) ( 1 + log 2 x ) 3 + max { K 2 ( k ) , K 3 ( k ) } ( 1 + log 2 x ) 2 log 2.592 x=2+\frac{K_4(k)(1+\log2x)^3+\max\{K_2(k),K_3(k)\}(1+\log2x)^2}{\log2.592} x = 2 + log 2.592 K 4 ( k ) ( 1 + log 2 x ) 3 + max { K 2 ( k ) , K 3 ( k )} ( 1 + log 2 x ) 2 The function N ( k ) \mathcal{N}(k) N ( k ) is increasing, and N ( 4 ) < 4.6 × 10 53 \mathcal{N}(4)<4.6\times10^{53} N ( 4 ) < 4.6 × 1 0 53 , N ( 414 ) < 3.0 × 10 79 \mathcal{N}(414)<3.0\times10^{79} N ( 414 ) < 3.0 × 1 0 79 . Numerically, N ( k ) < 3.6 × 10 46 k 12 ( log k ) 7 \mathcal{N}(k)<3.6\times10^{46}k^{12}(\log k)^7 N ( k ) < 3.6 × 1 0 46 k 12 ( log k ) 7 for 4 ≤ k ≤ 10 10 4\le k\le10^{10} 4 ≤ k ≤ 1 0 10 .
The last statement is obtained from Lemma 7 of [5 ] with r = 3 r=3 r = 3 . This is only given to show the order of magnitude; the proof below only uses N ( k ) \mathcal{N}(k) N ( k ) itself.
The bound N ( k ) \mathcal{N}(k) N ( k ) is large and grows with k k k . Comparing N ( 4 ) < 4.6 × 10 53 \mathcal{N}(4)<4.6\times10^{53} N ( 4 ) < 4.6 × 1 0 53 and N ( 414 ) < 3.0 × 10 79 \mathcal{N}(414)<3.0\times10^{79} N ( 414 ) < 3.0 × 1 0 79 we get n < 5.79 × 10 51 n<5.79\times10^{51} n < 5.79 × 1 0 51 for k = 3 k=3 k = 3 . The degree D = 3 k D=3k D = 3 k , which enters Matveev’s constant through D 2 ( 1 + log D ) D^2(1+\log D) D 2 ( 1 + log D ) , and the height H ( k ) H(k) H ( k ) , which grows like log k \log k log k are needed. We use D = 3 k D=3k D = 3 k for every k k k , although it is only an upper bound when 3 ∣ k 3\mid k 3 ∣ k ; this costs nothing, since the lower bound of Matveev’s theorem only becomes weaker when D D D is replaced by a larger number. Since N ( k ) → ∞ \mathcal{N}(k)\to\infty N ( k ) → ∞ , the reduction cannot be carried out for all k k k one value at a time; this is the reason for Section 15.
Large values of k k k
In this section k ≥ 30 k\ge30 k ≥ 30 . Then γ \gamma γ is extremely close to φ 2 \varphi^2 φ 2 , and P n ( k ) P_n^{(k)} P n ( k ) is extremely close to the odd-indexed Fibonacci number F 2 n + 1 ≈ φ 2 n + 1 / 5 F_{2n+1}\approx\varphi^{2n+1}/\sqrt{5} F 2 n + 1 ≈ φ 2 n + 1 / 5 .
Lemma 15.1. Let k ≥ 30 k\ge30 k ≥ 30 and n ≥ 0 n\ge0 n ≥ 0 . Then
P n ( k ) = φ 5 φ 2 n ( 1 + ζ n ) + e k ( n ) , ∣ e k ( n ) ∣ < 1 2 , ∣ ζ n ∣ ≤ ( 0.45 ( k + n ) + 1.6 ) φ − 2 k . P_n^{(k)}=\frac{\varphi}{\sqrt{5}}\varphi^{2n}(1+\zeta_n)+e_k(n),\qquad|e_k(n)|<\frac{1}{2},\qquad|\zeta_n|\le(0.45(k+n)+1.6)\varphi^{-2k}. P n ( k ) = 5 φ φ 2 n ( 1 + ζ n ) + e k ( n ) , ∣ e k ( n ) ∣ < 2 1 , ∣ ζ n ∣ ≤ ( 0.45 ( k + n ) + 1.6 ) φ − 2 k . Proof. Write γ = φ 2 − θ \gamma=\varphi^2-\theta γ = φ 2 − θ . By Lemma 9.1, γ 2 − 3 γ + 1 = − γ 1 − k \gamma^2-3\gamma+1=-\gamma^{1-k} γ 2 − 3 γ + 1 = − γ 1 − k , and γ 2 − 3 γ + 1 = ( γ − φ 2 ) ( γ − φ − 2 ) \gamma^2-3\gamma+1=(\gamma-\varphi^2)(\gamma-\varphi^{-2}) γ 2 − 3 γ + 1 = ( γ − φ 2 ) ( γ − φ − 2 ) ; hence θ = γ 1 − k / ( γ − φ − 2 ) \theta=\gamma^{1-k}/(\gamma-\varphi^{-2}) θ = γ 1 − k / ( γ − φ − 2 ) . Using γ > φ 2 ( 1 − φ − 2 k ) \gamma>\varphi^2(1-\varphi^{-2k}) γ > φ 2 ( 1 − φ − 2 k ) and φ 2 − φ − 2 = 5 \varphi^2-\varphi^{-2}=\sqrt{5} φ 2 − φ − 2 = 5 we get 0 < θ < 1.1711 φ − 2 k 0<\theta<1.1711\varphi^{-2k} 0 < θ < 1.1711 φ − 2 k . Since φ 4 − 3 φ 2 + 1 = 0 \varphi^4-3\varphi^2+1=0 φ 4 − 3 φ 2 + 1 = 0 , we have γ 2 − 3 γ + 1 = − θ ( γ + φ 2 − 3 ) \gamma^2-3\gamma+1=-\theta(\gamma+\varphi^2-3) γ 2 − 3 γ + 1 = − θ ( γ + φ 2 − 3 ) and γ 2 − 1 = φ 4 − 1 − θ ( γ + φ 2 ) \gamma^2-1=\varphi^4-1-\theta(\gamma+\varphi^2) γ 2 − 1 = φ 4 − 1 − θ ( γ + φ 2 ) , so that, with c : = 1 / ( φ 2 + 1 ) = ( φ 2 − 1 ) / ( φ 4 − 1 ) c:=1/(\varphi^2+1)=(\varphi^2-1)/(\varphi^4-1) c := 1/ ( φ 2 + 1 ) = ( φ 2 − 1 ) / ( φ 4 − 1 ) ,
g k ( γ ) c = 1 − θ / ( φ 2 − 1 ) 1 − θ w / ( φ 4 − 1 ) , w = ( γ + φ 2 ) + k ( γ + φ 2 − 3 ) < 5.3 + 2.24 k . \frac{g_k(\gamma)}{c}=\frac{1-\theta/(\varphi^2-1)}{1-\theta w/(\varphi^4-1)},\qquad w=(\gamma+\varphi^2)+k(\gamma+\varphi^2-3)<5.3+2.24k. c g k ( γ ) = 1 − θ w / ( φ 4 − 1 ) 1 − θ / ( φ 2 − 1 ) , w = ( γ + φ 2 ) + k ( γ + φ 2 − 3 ) < 5.3 + 2.24 k . Hence g k ( γ ) = c ( 1 + η ) g_k(\gamma)=c(1+\eta) g k ( γ ) = c ( 1 + η ) with ∣ η ∣ ≤ max { θ w / ( φ 4 − 1 ) , θ / ( φ 2 − 1 ) } / ( 1 − θ w / ( φ 4 − 1 ) ) ≤ ( 0.45 k + 1.07 ) φ − 2 k |\eta|\le\max\{\theta w/(\varphi^4-1),\theta/(\varphi^2-1)\}/(1-\theta w/(\varphi^4-1))\le(0.45k+1.07)\varphi^{-2k} ∣ η ∣ ≤ max { θ w / ( φ 4 − 1 ) , θ / ( φ 2 − 1 )} / ( 1 − θ w / ( φ 4 − 1 )) ≤ ( 0.45 k + 1.07 ) φ − 2 k . By (14), P n ( k ) = g k ( γ ) γ n + 1 + e k ( n ) P_n^{(k)}=g_k(\gamma)\gamma^{n+1}+e_k(n) P n ( k ) = g k ( γ ) γ n + 1 + e k ( n ) , and γ n + 1 = φ 2 n + 2 ( 1 − δ ) n + 1 \gamma^{n+1}=\varphi^{2n+2}(1-\delta)^{n+1} γ n + 1 = φ 2 n + 2 ( 1 − δ ) n + 1 with δ = θ / φ 2 < 0.4474 φ − 2 k \delta=\theta/\varphi^2<0.4474\varphi^{-2k} δ = θ / φ 2 < 0.4474 φ − 2 k . Since c φ 2 = φ / 5 c\varphi^2=\varphi/\sqrt{5} c φ 2 = φ / 5 , this gives the statement with ζ n = ( 1 + η ) ( 1 − δ ) n + 1 − 1 \zeta_n=(1+\eta)(1-\delta)^{n+1}-1 ζ n = ( 1 + η ) ( 1 − δ ) n + 1 − 1 , and ∣ ζ n ∣ ≤ ∣ η ∣ + ( n + 1 ) δ |\zeta_n|\le|\eta|+(n+1)\delta ∣ ζ n ∣ ≤ ∣ η ∣ + ( n + 1 ) δ . □
A numerical check of Lemma 15.1 is reported in Appendix A. Now let ( n , m , n 1 , m 1 ) (n,m,n_1,m_1) ( n , m , n 1 , m 1 ) be a solution of (16) with k ≥ 30 k\ge30 k ≥ 30 , n > k n>k n > k , n ≥ 10 n\ge10 n ≥ 10 , and put
N ~ : = 2 n + 1 , N ~ 1 : = 2 n 1 + 1 , γ N ~ : = N ~ − N ~ 1 , κ : = 2 k log φ − log ( n + 1 ) . \widetilde{N}:=2n+1,\qquad\widetilde{N}_1:=2n_1+1,\qquad\gamma_{\widetilde{N}}:=\widetilde{N}-\widetilde{N}_1,\qquad\kappa:=2k\log\varphi-\log(n+1). N := 2 n + 1 , N 1 := 2 n 1 + 1 , γ N := N − N 1 , κ := 2 k log φ − log ( n + 1 ) .
By Lemma 15.1, ∣ ζ n ′ ∣ ≤ e − κ |\zeta_{n'}| \le e^{-\kappa} ∣ ζ n ′ ∣ ≤ e − κ for every 0 ≤ n ′ ≤ n 0 \le n' \le n 0 ≤ n ′ ≤ n . We may assume e − κ ≤ 0.01 e^{-\kappa} \le0.01 e − κ ≤ 0.01 , since otherwise 2 k log φ < log 100 + log ( n + 1 ) 2k \log\varphi< \log100 + \log(n + 1) 2 k log φ < log 100 + log ( n + 1 ) , which gives a smaller bound for k k k than the one obtained below, so that the result holds.
The linear forms. Since e − κ ≤ 0.01 e^{-\kappa} \le0.01 e − κ ≤ 0.01 , we have P n − 1 ( k ) ≥ 0.7 φ 2 n − 2 P_{n-1}^{(k)} \ge0.7\varphi^{2n-2} P n − 1 ( k ) ≥ 0.7 φ 2 n − 2 , and exactly the same computations as in § 3.3 –§ 3.5 (with N ~ / 5 \widetilde{N}/\sqrt{5} N / 5 in place of F N F_N F N and the extra terms coming from the ζ \zeta ζ 's) give, for the four linear forms Λ , Λ 1 , Λ 2 , Λ 3 \Lambda,\Lambda_1,\Lambda_2,\Lambda_3 Λ , Λ 1 , Λ 2 , Λ 3 of Part 1 (with N ~ , N ~ 1 \widetilde{N},\widetilde{N}_1 N , N 1 in place of N , N 1 N,N_1 N , N 1 ),
∣ Λ ∣ < 16 max ( φ − γ N ~ , α − γ m , e − κ ) , ∣ Λ 1 ∣ < 12 max ( α − γ m , e − κ ) , ∣ Λ 2 ∣ < 4.2 max ( φ − γ N ~ , e − κ ) , ∣ Λ 3 ∣ < 12 max ( α − γ m 1 , e − κ ) . \begin{aligned}
|\Lambda| &< 16\max(\varphi^{-\gamma\widetilde{N}},\alpha^{-\gamma m},e^{-\kappa}), &
|\Lambda_1| &< 12\max(\alpha^{-\gamma m},e^{-\kappa}),\\
|\Lambda_2| &< 4.2\max(\varphi^{-\gamma\widetilde{N}},e^{-\kappa}), &
|\Lambda_3| &< 12\max(\alpha^{-\gamma m_1},e^{-\kappa}).
\end{aligned} ∣Λ∣ ∣ Λ 2 ∣ < 16 max ( φ − γ N , α − γ m , e − κ ) , < 4.2 max ( φ − γ N , e − κ ) , ∣ Λ 1 ∣ ∣ Λ 3 ∣ < 12 max ( α − γ m , e − κ ) , < 12 max ( α − γ m 1 , e − κ ) .
For Λ 3 \Lambda_3 Λ 3 the denominator g ( α ) α m 1 ( α γ m − 1 ) g(\alpha)\alpha^{m_1}(\alpha^{\gamma m}-1) g ( α ) α m 1 ( α γ m − 1 ) is bounded below by P n − 1 ( k ) − 0.8 ≥ 0.69 φ 2 n − 2 P_{n-1}^{(k)}-0.8 \ge0.69\varphi^{2n-2} P n − 1 ( k ) − 0.8 ≥ 0.69 φ 2 n − 2 .
These forms are the same algebraic expressions as in Part 1, so they do not vanish, and Matveev’s theorem applies with the same data ( D = 6 , B = N ~ ) (D=6, B=\widetilde{N}) ( D = 6 , B = N ) . The only difference is that every bound now holds for the minimum of the previous quantity and κ \kappa κ .
A first bound for k k k . We get either
2 k log φ < log ( n + 1 ) + K 4 ( 1 + log ( 2 n + 1 ) ) 3 , K 4 = 3.020 × 10 42 , 2k\log\varphi< \log(n+1)+K_4(1+\log(2n+1))^3,\qquad K_4=3.020\times10^{42}, 2 k log φ < log ( n + 1 ) + K 4 ( 1 + log ( 2 n + 1 ) ) 3 , K 4 = 3.020 × 1 0 42 ,
or n < 4.62 × 10 48 n<4.62\times10^{48} n < 4.62 × 1 0 48 (and then k < n k<n k < n ). Using n < N ( k ) n<\mathcal{N}(k) n < N ( k ) (Proposition 14.1 ), both cases give k < 1.212 × 10 52 k<1.212\times10^{52} k < 1.212 × 1 0 52 .
Reduction. Let K K K be a bound for k k k and M : = 2 N ( K ) + 2 M:=2\mathcal{N}(K)+2 M := 2 N ( K ) + 2 , which bounds N ~ , N ~ 1 , m \widetilde{N},\widetilde{N}_1,m N , N 1 , m and m 1 m_1 m 1 . We run Steps 1–3 of § 3.6 , now with w = min { γ N ~ log φ , γ m log α , κ } w=\min\{\gamma\widetilde{N}\log\varphi,\gamma m\log\alpha,\kappa\} w = min { γ N log φ , γ m log α , κ } in Step 1, w ′ = min { γ m log α , κ } w'=\min\{\gamma m\log\alpha,\kappa\} w ′ = min { γ m log α , κ } and w ′ ′ = min { γ N ~ log φ , κ } w''=\min\{\gamma\widetilde{N}\log\varphi,\kappa\} w ′′ = min { γ N log φ , κ } in Step 2, w ′ ′ ′ = min { m 1 log α , κ } w'''=\min\{m_1\log\alpha,\kappa\} w ′′′ = min { m 1 log α , κ } in Step 3, and A = 32 / log α , 24 / log α , 8.4 / log φ , 24 / log α A=32/\log\alpha,24/\log\alpha,8.4/\log\varphi,24/\log\alpha A = 32/ log α , 24/ log α , 8.4/ log φ , 24/ log α respectively (and B = e B=e B = e ).
If W W W denotes the largest of the bounds obtained, then either κ < W \kappa<W κ < W , that is 2 k log φ < W + log ( M / 2 + 1 ) 2k\log\varphi<W+\log(M/2+1) 2 k log φ < W + log ( M /2 + 1 ) , or all the gaps and m 1 m_1 m 1 are bounded, which bounds m m m and then n < n ∗ : = 1 + m log α / ( 2 log φ ) n<n^*:=1+m\log\alpha/(2\log\varphi) n < n ∗ := 1 + m log α / ( 2 log φ ) , so that k < n < n ∗ k<n<n^* k < n < n ∗ .
Each row uses the bound of the previous row as K K K , and the last row gives k ≤ 414 k\le414 k ≤ 414 .
Table 5. The four rounds of reduction for k ≥ 30 k\ge30 k ≥ 30 .
We have proved that
Proposition 15.2. If (16) has a solution with n > k ≥ 30 n>k\ge30 n > k ≥ 30 , then k ≤ 414 k\le414 k ≤ 414 .
The range 4 ≤ k ≤ 414 4\le k\le414 4 ≤ k ≤ 414
For each k k k with 4 ≤ k ≤ 414 4\le k\le414 4 ≤ k ≤ 414 we computed γ ( k ) \gamma(k) γ ( k ) and f k ( γ ) f_k(\gamma) f k ( γ ) to the required precision and ran the reduction of § 4.5 (with c 0 c_0 c 0 and 2.3 / f 2.3/f 2.3/ f computed from γ ( k ) \gamma(k) γ ( k ) ): a first step with M = 2 N ( k ) + 2 M=2\mathcal{N}(k)+2 M = 2 N ( k ) + 2 , where N ( k ) \mathcal{N}(k) N ( k ) is the bound of Proposition 14.1 , and a second step with M M M equal to the bound for m m m obtained in the first step.
For each k k k , the bound for m m m is the bound for m 1 m_1 m 1 plus the bound for γ m \gamma_m γ m , and the bound for n n n then follows from ( n − 2 ) log γ < ( m − 1 ) log α (n-2)\log\gamma<(m-1)\log\alpha ( n − 2 ) log γ < ( m − 1 ) log α (§ 4.3 ). Over all these k k k , the first step gives γ n ≤ 212 \gamma_n\le212 γ n ≤ 212 , γ m ≤ 325 \gamma_m\le325 γ m ≤ 325 , m 1 ≤ 342 m_1\le342 m 1 ≤ 342 , m ≤ 667 m\le667 m ≤ 667 and n ≤ 423 n\le423 n ≤ 423 (all attained at k = 383 k=383 k = 383 ), and the second step gives γ n ≤ 21 \gamma_n\le21 γ n ≤ 21 , γ m ≤ 30 \gamma_m\le30 γ m ≤ 30 , m 1 ≤ 39 m_1\le39 m 1 ≤ 39 , m ≤ 67 m\le67 m ≤ 67 and
where each maximum is attained is reported in Appendix § 4.9 .
More precisely, the bound for n n n of the second step is smaller than k + 1 k+1 k + 1 for every 34 ≤ k ≤ 414 34 \leq k \leq414 34 ≤ k ≤ 414 , so that there is no solution with n > k n>k n > k for these k k k . For 4 ≤ k ≤ 33 4 \leq k \leq33 4 ≤ k ≤ 33 and n ≤ 43 n \leq43 n ≤ 43 , the computer search over 4 ≤ k ≤ 100 4 \leq k \leq100 4 ≤ k ≤ 100 , n ≤ 250 n \leq250 n ≤ 250 reported below gives the solutions with n > k n>k n > k .
Proof of Theorem 1.6 . By Propositions 14.1 and 15.2 , a solution with n > k ≥ 4 n>k \geq4 n > k ≥ 4 has k ≤ 414 k \leq414 k ≤ 414 , and then, by the computations of this section, k ≤ 33 k \leq33 k ≤ 33 and n ≤ 43 n \leq43 n ≤ 43 . A computer search over 4 ≤ k ≤ 100 4 \leq k \leq100 4 ≤ k ≤ 100 and 0 ≤ n 1 < n ≤ 250 0 \leq n_1<n \leq250 0 ≤ n 1 < n ≤ 250 (and all m > m 1 ≥ 2 m>m_1 \geq2 m > m 1 ≥ 2 ) gives, in the range n > k n>k n > k , exactly the solutions
( 7 , 12 , 5 , 2 ; 87 ) ( k = 4 ) , ( 6 , 11 , 1 , 8 ; − 42 ) , ( 6 , 12 , 1 , 11 ; − 272 ) ( k = 5 ) , (7,12,5,2;87)\ (k=4),\qquad(6,11,1,8;-42),\qquad(6,12,1,11;-272)\ (k=5), ( 7 , 12 , 5 , 2 ; 87 ) ( k = 4 ) , ( 6 , 11 , 1 , 8 ; − 42 ) , ( 6 , 12 , 1 , 11 ; − 272 ) ( k = 5 ) ,
( 10 , 17 , 7 , 11 ; 336 ) ( k = 9 ) , (10,17,7,11;336)\ (k=9), ( 10 , 17 , 7 , 11 ; 336 ) ( k = 9 ) ,
while in the range n ≤ k n \leq k n ≤ k it gives exactly the solutions of Theorem 1.2 . □
Computational details
All computations were done in Python. The sequences are used with exact integer arithmetic, but the logarithms and continued fractions require precision. We worked with 260 significant digits in Part 1. Two scripts reproduce everything (see the data availability statement). The first runs in about three minutes and covers Part 1 and the cases k = 2 , 3 k=2,3 k = 2 , 3 . The second, heavier one takes about 15 minutes and covers § 4.6 –16.
For Part 1 (§ 3.6 ), here is how it goes. In Step 2, the worst case is γ N = 68 \gamma_N=68 γ N = 68 in Case 1 and γ m = 97 \gamma_m=97 γ m = 97 in Case 2. Step 3 treats the 26 650 pairs ( γ N , γ m ) (\gamma_N,\gamma_m) ( γ N , γ m ) with γ N ≤ 260 \gamma_N \leq260 γ N ≤ 260 even and γ m ≤ 205 \gamma_m \leq205 γ m ≤ 205 . The final search runs over all odd N 1 < N ≤ 1501 N_1<N \leq1501 N 1 < N ≤ 1501 and all m > m 1 ≥ 2 m>m_1 \geq2 m > m 1 ≥ 2 ; this range is deliberately chosen well above the bound N ≤ 533 N \leq533 N ≤ 533 from the first pass.
For k = 2 , 3 k=2,3 k = 2 , 3 (§ 4.5 ), the search goes up to n ≤ 398 n \leq398 n ≤ 398 , well beyond the bounds n ≤ 39 n \leq39 n ≤ 39 and n ≤ 37 n \leq37 n ≤ 37 from the second step.
The case of large k k k (§ 4.7 ) is more delicate. In the first round, Step 3 involves 4 267 824 pairs ( γ N ~ , γ m ) (\gamma_{\widetilde N},\gamma_m) ( γ N , γ m ) . In all rounds, Lemma 2.4 applied with one of the first nine convergents satisfying q > 6 M q>6M q > 6 M . We also checked Lemma 15.1 against the exact values of P n ( k ) P_n^{(k)} P n ( k ) for k = 30 , 31 , 40 , 60 , 100 , 200 , 400 , 700 k=30,31,40,60,100,200,400,700 k = 30 , 31 , 40 , 60 , 100 , 200 , 400 , 700 and k < n < 4 k k<n<4k k < n < 4 k .
Finally, the range 4 ≤ k ≤ 414 4 \leq k \leq414 4 ≤ k ≤ 414 (Section 16). This was in fact a very fast computation. In the first pass, all the maxima ( γ n ≤ 212 , γ m ≤ 325 , m 1 ≤ 342 , m ≤ 667 , n ≤ 423 ) (\gamma_n \leq212,\ \gamma_m \leq325,\ m_1 \leq342,\ m \leq667,\ n \leq423) ( γ n ≤ 212 , γ m ≤ 325 , m 1 ≤ 342 , m ≤ 667 , n ≤ 423 ) are attained at k = 383 k=383 k = 383 . In the second pass, however, the maxima of the different bounds occur at different values of k k k : m 1 ≤ 39 m_1 \leq39 m 1 ≤ 39 , m ≤ 67 m \leq67 m ≤ 67 and n ≤ 43 n \leq43 n ≤ 43 at k = 18 k=18 k = 18 (where γ m ≤ 28 \gamma_m \leq28 γ m ≤ 28 ), γ m ≤ 30 \gamma_m \leq30 γ m ≤ 30 at k = 4 k=4 k = 4 and k = 15 k=15 k = 15 , and γ n ≤ 21 \gamma_n \leq21 γ n ≤ 21 at k = 4 k=4 k = 4 . The final search was for the range 4 ≤ k ≤ 100 4 \leq k \leq100 4 ≤ k ≤ 100 , 0 ≤ n 1 < n ≤ 250 0 \leq n_1<n \leq250 0 ≤ n 1 < n ≤ 250 and all m > m 1 ≥ 2 m>m_1 \geq2 m > m 1 ≥ 2 .
Data availability: The data mentioned in the paper (computer codes) are available from the third author.
Use of AI Tools: Claude (Anthropic, Opus 5.5) was used to check the computations, write the corresponding verification code. We also used for language editing. The authors take full responsibility for the content. C. Deme, UFR SAT, Université Alioune Diop, Bambey, 30, Sénégal Email address: cherifbachir.deme@uadb.edu.sn
K. D. Fall, UFR SAT, Université Alioune Diop, Bambey, 30, Sénégal Email address: kancou.d.fall@aims-senegal.org
B. Faye, UFR SAT, Université Alioune Diop, Bambey, 30, Sénégal Email address: bernadette.faye@uadb.edu.sn