Get 20M+ Full-Text Papers For Less Than $1.50/day. Subscribe now for You or Your Team.

Learn More →

On prime powers in linear recurrence sequences

On prime powers in linear recurrence sequences In this paper we consider the Diophantine equation U = p where U is a linear recurrence n n sequence, p is a prime number, and x is a positive integer. Under some technical hypotheses on U , we show that, for any p outside of an effectively computable finite set of prime numbers, there exists at most one solution (n, x ) to that Diophantine equation. We compute this exceptional set for the Tribonacci sequence and for the Lucas sequence plus one. Keywords Diophantine equations · Linear recurrence sequences · Exponential Diophantine equations Mathematics Subject Classification 11D45 · 11B37 · 11D61 Résumé Nous considérons dans cet article l’équation U = p ,où U est une suite récurrente linéaire, n n p un nombre premier, et x un entier positif. Sous des hypothèses techniques, nous montrons que, pour tout p en dehors d’un ensemble fini calculable de nombres premiers, cette équation admet au plus une solution (n, x ). Nous déterminons cet ensemble exceptionnel pour la suite de Tribonacci et pour la suite de Lucas plus un. 1 Introduction Let U = (U ) be a sequence of integers satisfying a recurrence relation n n≥0 U = s U + ··· + s U , n ≥ 0. n+d d−1 n+d−1 0 n Volker Ziegler was supported by the Austrian Science Fund (FWF) under the project I4406. The first discussion on this project was possible when Japhet Odjoumani was at University of Graz under the support of Coimbra group. B Volker Ziegler volker.ziegler@sbg.ac.at Japhet Odjoumani japhet.odjoumani@imsp-uac.org Institut de Mathématiques et de Sciences Physiques, Université d’Abomey-Calavi, Dangbo, Benin University of Salzburg, Hellbrunnerstrasse 34/I, 5020 Salzburg, Austria 123 J. Odjoumani, V. Ziegler Let us assume that this linear recurrence is of order d,thatis U does not satisfy a recurrence relation for a smaller d.Wedenoteby d d−1 m p (X ) = X − s X − ··· − s = (X − α ) U d−1 0 i i =1 its characteristic polynomial. In case that all multiplicities m are equal to 1 we call U a simple recurrence relation. If U is a simple recurrence sequence of order d we can write n n n U = a α + a α + ··· + a α n 1 2 d 1 2 d with a ,..., a ∈ C\{0}. If the characteristic roots also satisfy 1 d |α | > |α | ≥ ··· ≥ |α | 1 2 d we say that U satisfies a dominant root condition. If we even have |α | > |α | > |α | ≥ ··· ≥ |α | 1 2 3 d we say that U satisfies a strong dominant root condition. We say that U satisfies the multi- plicative independence condition if the numbers a and α are multiplicatively independent, 1 1 that is that the only integral solution to a α = 1is (x , y) = (0, 0). 1 1 A sequence of special interest in this paper will be the Tribonacci sequence T = (T ) n n≥0 which is a linear recurrence sequence of order 3 given by T = T + T + T , n ≥ 0 n+3 n+2 n+1 n and T = 0, T = 1and T = 1. We will also have a closer look on the linear recurrence 0 1 2 sequence L = (L ) also of order 3 given by n n≥0 L = 2L − L , n ≥ 0 n+3 n+2 n and L = 3, L = 2and L = 4. Note that this recurrence sequence is the classical Lucas 0 1 2 ˜ ˜ ˜ sequence L = (L ) added by 1, where L is given by n n≥0 ˜ ˜ ˜ L = L + L , n ≥ 0 n+2 n+1 n ˜ ˜ ˜ and L = 2and L = 1. In particular, we have L = L + 1 and will therefore call L the 0 1 n n added by one Lucas sequence. There is a rich literature on Diophantine equations involving linear recurrence sequences and we refer to [7] for an overview. In this paper we will focus on Diophantine equations of the form U = y .Inthe casethat U is a binary recurrence sequence Petho[ ˝ 11] and, n n independently, Shorey and Stewart [12](seealso[13, Chapter 9]) showed that such equations have only finitely many solutions (n, m, y) ∈ N × Z with y, m > 1. In the case of higher order recurrence sequences Shorey and Stewart [12] showed that under a dominant root assumption a solution (n, y, m) to U = y with y, m > 1 satisfies m < C,where C is an effectively computable constant. Moreover, a recent result due to Bugeaud and Kaneko [6] implies that the equation U = y with y, m > 1 has at most finitely many solutions and their number can be explicitly determined. However, for a given binary sequence U it is a very hard task to find all solutions to U = y . In the case of the Fibonacci and the Lucas sequence this task was finally resolved by Bugeaud, Mignotte and Siksek [5]. In the case of recurrence sequences of higher order (satisfying a dominant root condition) the methods fail to find all solutions (n, y, m) to U = y with y, m > 1 and results similar to those of Petho, ˝ Shorey and Stewart for the binary case have not been proved yet. 123 On prime powers in linear recurrence sequences In this paper we are interested in the following problem. Let U = (U ) beafixed n n≥0 sequence and P ={p ,..., p } a finite set of primes. How many solutions (n, x ,..., x ), 1 t 1 t with n, x ,..., x non-negative integers does the equation 1 t x x 1 t U =±p ··· p n t have? Of course the theory of S-unit equations yields a bound for the number of solutions depending only on t. These bounds are usually far from the optimal bound and do not reflect what can be expected from numerical experiments. In this paper we resolve the case that t = 1. That is we consider Diophantine equations of the form U = p for a fixed sequence U = (U ) and arbitrary, but fixed prime p. By Baker’s method using lower bounds n n≥0 for linear forms in logarithms this equation can be solved easily for particular values for p. However, in this paper we show that up to a finite effective computable set of primes S = S(U ) the Diophantine equation U = p has at most one solution. More precisely we show: Theorem 1 Let U = (U ) be a simple, linear recurrence sequence of order at least n n≥0 two, satisfying the dominant root condition. Further we assume that U satisfies one of the following conditions – U satisfies the strong dominant root condition; – U satisfies the multiplicative independence condition. Then there exists an effective computable set of primes S such that the equation U =±p has at most one solution (n, x ) ∈ N with x = 0 unless p ∈ S. Remark 1 Let us note that the assumption that U is simple can be dropped. To avoid technical difficulties we refrain from this extension. The set S in Theorem 1 is not only effective computable, but we can also provide an efficient algorithm to compute the set S and find all exceptional primes. We demonstrate the method by applying it to the Tribonacci sequence T and the sequence L and prove the following two theorems: Theorem 2 The Diophantine equation T = p has at most one solution (n, x ) with x = 0 unless p = 2. In the case that p = 2 there exist two solutions, namely T = 2 and T = 4. 3 4 Theorem 3 The Diophantine equation L = p has at most one solution (n, x ) with x = 0 unless p = 2. In the case that p = 2 there exist three solutions, namely L = 2,L = 4 and 1 2 L = 8. It is easy to see that the Tribonacci sequence T is indeed of order three, is simple and satisfies the dominant root condition but not the strong dominant root condition. However, the Tribonacci sequence satisfies the multiplicative independence condition (see also Sect. 2). On the other hand it is easy to see that the Lucas sequence added by 1, i.e. the sequence L, is simple and of order three and satisfies the strong dominant root condition, but does not satisfy the multiplicative independence condition. Moreover let us note that a result of Shorey and Stewart [12, Theorem 4] implies that the Diophantine equation L = y has only finitely many solutions (n, y, m) with y, m > 1and n even. This implies even a stronger result than stated in Theorem 3, considering only even indices n. But to our knowledge no such result is known for odd indices n and thus our result (Theorem 3) indeed complements the result due to Shorey and Stewart. 123 J. Odjoumani, V. Ziegler Finally let us note that Theorem 1 can be easily proved in the case that U is a Lucas– Lehmer sequence, by applying the Primitive Divisor Theorem proved by Bilu, Hanrot, and Voutier [4]. Therefore we choose the sequences T and L to avoid cases that could easily be solved by the Primitive Divisor Theorem. We also want to note that the result of Theorem 2 can easily be deduced by a result due to Gomez and Luca [8] who found all multiplicatively dependent pairs of k-generalized Fibonacci numbers. However, let us note that our proof of Theorem 2 yields an alternative approach. In the next section we provide some useful lemmas and inequalities. In Sect. 3 we will use Baker’s method to obtain upper bounds for n in the case that p is arbitrary but fixed and will therefore reprove a theorem due to Shorey and Tijdeman [12, Theorem 3]. The heart of the proof is in Sect. 4, where we show that the existence of two solutions (n , x ) and 1 1 (n , x ) implies an effectively computable upper bound for n . This allows us to finally prove 2 2 1 Theorem 1. Unfortunately the absolute upper bounds are too large to successfully perform a computer search. However, in the case of the Tribonacci sequence and the Lucas sequence added by one the bound for n is small enough to find small lists of possible candidates of x x primes p such that the Diophantine equations T = p and L = p may have two solutions. n n Using the upper bounds found in Sect. 3 together with the Baker–Davenport reduction (see Lemma 6) and using lower bounds for approximations by continued fractions (see Lemma 5) we find all primes p that admit more than one solution. These reduction procedures are discussed in the final Sect. 5. Throughout the paper we will denote by C , C ,... positive and effectively computable 1 2 constants. 2 Auxiliary results To ease the notation let us write a = a and α = α .Since U is defined over the integers all 1 1 n roots of the characteristic polynomial are algebraic integers. Since U is simple, of order at least two and satisfies a dominant root condition we conclude that |α| > 1 and furthermore n n+1 that a and α are real. Replacing U by (−1) U or (−1) U or −U we may also assume n n n n that both α and a are positive. With these assumptions and notations in force there exist effective computable constants C , C , C > 0 such that 1 2 3 n x n C aα < U = p < C aα (1) 1 n 2 which implies n log α + log (aC ) n log α + log(aC ) 1 2 < x < . (2) log p log p We also have n n U − aα < C |α | , (3) n 3 2 n log α thus we have x  . In case that U satisfies also a strong dominant root condition we log p obtain a lower bound n n C |α | < U − aα . (4) 4 2 n Finally let us note that there exists N such that |U | is strictly increasing for n ≥ N . 0 n 0 In the case of the Tribonacci sequence we can make these computations explicit. In particular, we have that n n n ¯ ¯ T = aα + bβ + bβ . 123 On prime powers in linear recurrence sequences 3 2 where α, β und β are the roots of the characteristic Polynomial X − X − X − 1, that is we have α ∼ 1.83929,β ∼−0.419643 + 0.606291i , 2 2 5α − 3α − 4 5β − 3β − 4 a = ∼ 0.336228, b = ∼−0.168114 − 0.198324i . 22 22 Note that a, b und b are computed from solving the linear system 0 0 0 aα + bβ + bβ = 0, 1 1 1 ¯ ¯ aα + bβ + bβ = 1, 2 2 2 ¯ ¯ aα + bβ + bβ = 1. −1/2 ¯ ¯ Moreover, let us note that αββ =−1 and therefore |β|=|β|=|α| .Fromthese estimations for α and β it is clear that T ∼ aα . In particular we have that n x n 0.999aα < T = p < 1.001aα (5) n log α provided that n > 8. Note that (5) implies that x < . Finally, let us note that the log p Tribonacci sequence T is strictly increasing for n ≥ 2. In the case of the sequence L we find the explicit formula n n n L = γ + 1 + δ , where √ √ 1 + 5 1 − 5 γ = and δ = . 2 2 −1 Note that γδ =−1 and therefore |δ|=|γ | . Obviously L satisfies the strong dominant root condition but not the multiplicative independence relation. However, under the assumption that n > 10 we obtain the estimates n x n γ < L = p < 1.009γ (6) which imply n log γ n log γ + 0.01 < x < . (7) log p log p We also have the inequality 0.99 < L − γ < 1.01. (8) Finally let us note that L is strictly increasing for n ≥ 1. In this paper we will make extensive use of lower bounds for linear forms of logarithms of complex numbers. In particular we will use a result due to Matveev [10]. Let η = 0bean algebraic number of degree d and let a (X − η ) ··· (X − η ) ∈ Z[X ] 1 d be the minimal polynomial of η. Then the absolute logarithmic Weil height is defined by h(η) = log |a|+ max{0, log |η |} . i =1 In the case that η is a rational number, say η = P/Q ∈ Q with P, Q integers such that gcd(P, Q) = 1, we have h(P/Q) = max{log |P|, log |Q|}. With this basic notation we 123 J. Odjoumani, V. Ziegler have the following result on lower bounds for linear forms in logarithms due to Matveev [10]. Lemma 1 Denote by η ,...,η algebraic numbers, neither 0 nor 1,by log η , ..., log η 1 m 1 m determinations of their logarithms, by D the degree over Q of the number field K = Q(η ,...,η ), and by b ,..., b rational integers. Furthermore let κ = 1 if K is real 1 m 1 m and κ = 2 otherwise. Choose A ≥ max {Dh (η ) , | log η |} (1 ≤ i ≤ m) i i i and B = max 1, max |b |A /A : 1 ≤ j ≤ m . j j m Assume that b = 0 and log η ,..., log η are linearly independent over Z.Then m 1 m log |b log η + ··· + b log η |≥−C (m)C W D Ω, 1 1 m m 0 0 with Ω = A ··· A , 1 m 16 1 m m+1 C (m) = C (m,κ) = e (2m + 1 + 2κ) (m + 2) (4(m + 1)) em , m!κ 2 4.4m+7 5.5 2 C = log e m D log(eD) , W = log (1.5eB D log(eD)) . 0 0 However, in the case that the number of logarithms is m = 2 we have numerically rather good results due to Laurent [9]. In particular, we will use the following result: Lemma 2 Suppose that the numbers η , η , log η , log η are real and positive and that η 1 2 1 2 1 and η are multiplicatively independent. Then for positive integers b und b we have 2 1 2 log |b log η − b log η | 1 1 2 2 > −17.9D max log b + 0.38, 30/D, 1 log A log A , 1 2 where D =[Q(η ,η ) : Q], 1 2 A ≥ max{h(η), log η/D, 1/D} for i = 1, 2 and b b 1 2 b = + . D log A D log A 2 1 In order to apply the results of Matveev and Laurent we have to know the heights of the relevant quantities and also have to ensure that they are multiplicatively independent. In the case of the Tribonacci sequence and the Lucas sequence added by one we can use Sage [14] to compute the heights of the relevant quantities and obtain h(α) = h(β) = h(β) = 0.20312595447866 ··· < 0.20313, (9) h(a) = h(b) = h(b) = 1.2613965446394 ··· < 1.2614, h(γ ) = h(δ) = 0.2406059125298 ··· < 0.2407. To ensure the multiplicative independence of α, a and p in the case of the Tribonacci sequence and the Lucas sequence added by one the following lemma is helpful: 123 On prime powers in linear recurrence sequences Lemma 3 Let p be a prime, then α, a and p are multiplicatively independent and also γ and p are multiplicatively independent. Proof Since α and γ are units and p is a prime it is obvious that α and p respectively γ and p are multiplicatively independent. Thus it remains to show that α, a and p are multiplicatively independent. Let us note that the splitting field K = Q(α, β, β) of the characteristic polynomial X − X − X − 1 has class number 1. Moreover, 1/a is an algebraic integer with absolute Norm 4 2 N (1/a) = 2 · 11 . That is unless p = 2or p = 11 the lemma is proved. K /Q However, using Sage [14] we compute the following prime ideal factorizations (2) = p 2 2 2 (11) = q q q 1 2 3 (1/a) = p q q 1 2 which show that α, a, 2 and 11 are multiplicatively independent and thus proving the lemma. Also let us note the following helpful fact that can easily be proved using elementary calculus: Lemma 4 If |x − 1| < 1/2,then | log(x )| < 3|x − 1|/2 and if |y| < 1/2,then log(1 + y) = y + θ y for some |θ|≤ 1. Proof Replace x by 1 + y then the first statement is equivalent to the statement that |y| < 1/2 implies | log(1 + y)| < 3|y|/2. Thus assuming that |y| < 1/2wehave | log(1 + y)|= y − ± ... |y| ≤|y|+ 1 +|y|+|y| + ... |y| 1 =|y| 1 + · . 2 1 −|y| From this inequality we easily deduce both statements. In order to reduce the huge bounds coming from the applications of the results due to Matveev and Laurent we use continued fractions. In particular, we use the following two results: Lemma 5 Assume that μ is real and irrational and has the continued fraction expansion μ =[a ; a , a ,... ].Let be an integer and set A = max {a } and let p /q be the 0 1 2 1≤ j ≤ -th convergent to μ,then 1 p < μ − (2 + A)q for any rational fraction p/q with q ≤ q . Proof This follows from the inequality given in [2, page 47] combined with the best approx- imation property of continued fractions. 123 J. Odjoumani, V. Ziegler The second method is due to Baker and Davenport [3] for which we state a variant of this reduction method: Lemma 6 Given a Diophantine inequality of the form |nμ + τ − x | < c exp(−c n), (10) 1 2 with positive constants c , c and real numbers μ and τ . Assume that n < N and that there 1 2 is a real number κ> 1 such that there exists a convergent p/qto μ with 1 1 qμ < and qτ > , 2κ N κ where · denotes the distance to the nearest integer. Then we have log(2κqc ) n ≤ . Proof We consider inequality (10) and multiply it by q. Then under our assumptions we obtain c q exp (−c n) > |qx + nqμ + qτ|≥ | qτ − Nqμ | 1 2 (11) | | = qτ − N qμ > . 2κ 1 1 Note that the equality in (11) holds since by assumption N qμ < < and therefore 2κ 2 N qμ = Nqμ . Solving Inequality (11)for n yields the lemma. 3 A first upper bound In this section we will find absolute upper bounds for x and upper bounds for n in terms of p for solutions (n, x ) to the Diophantine equations U = p , n ≥ N (12) n 0 and T = p , n ≥ 2 (13) and L = p , n ≥ 1. (14) For a fixed prime p we can find such a bound by the standard procedure following the ideas of Shorey and Stewart [12] using Baker’s method. 3.1 General method Let us assume that that (n, x ) is a solution to (12). Then Eq. (12) yields :=C aα C |α | C α 3  2 − 1 ≤ ≤   . x x p p |C a| α Taking logarithms yields 3C α 5  2 Λ = |n log α − x log p + log a| <   (15) 2 α 123 On prime powers in linear recurrence sequences Let us note that in the case that α and a are multiplicatively dependent we have integers z and −z log α z z 1 1 2 z such that α a = 1. Since |α| > 1wehavethat z = 0 and therefore log a = . 2 2 Thus we obtain in this case the inequality 3z C α 2 5  2 | | (nz − z ) log α − xz log p <   . (16) 2 1 2 2 α We apply Matveev’s result depending on the multiplicative dependence of α and a to (15) with m = 3orto(16) with m = 2. Therefore let us note that the heights of α and a are effective computable and that the height of p is log p and therefore (in the case that m = 3) we have that A , A are bounded by an absolute effective computable constant and A = D log p, 1 2 3 with D =[Q(a,α) : Q]. Note that in the case that m = 2wehave that A is bounded by an effective computable constant and that A = D log p. Thus we have in any case B = max 1, max |b |A /A : 1 ≤ j ≤ m ≤ C . j j m 6 log p Let S be the set of primes that divide the norm of α, or divide the denominator of a,or divide the norm of a. Obviously the set S is finite and for all primes p ∈ / S we have that 0 0 α, a and p are multiplicatively independent. Therefore let us assume that p is not a member of S , hence we obtain together with (15) the inequality 3C α n log − n log > log |Λ| > −C log p log 2 α log p which yields n n < C log (17) log p log p provided that p ∈ / S . Note that in the case that m = 2 similar considerations lead to the same conclusion and in particular to Inequality (17). Lemma 7 Assume that (n, x ) is a solution to (12) and that p ∈ / S , then there exist effective computable constants C and C such that 8 9 n < C log p, and x < C . 8 9 Proof Inequality (17) implies an absolute upper bound for . Since inequality (2)wehave log p log |α| x  n and this immediately yields an absolute bound for x and also the bound for n log p stated in the lemma. Remark 2 In Lemma 7 we basically reproved a result of Shorey and Stewart [12, Theorem 3]. But instead of using a result of Baker [1] on lower bounds for linear forms in logarithms we use the more explicit and easier to apply result due to Matveev [10]. Remark 3 Let us note that in the case that log α and log a are linearly dependent over Q we may apply Laurent’s result (Lemma 2) and would obtain in concrete examples smaller numerical n n values for C but the log factor in Inequality (17) would turn into a log factor log p log p (see Sect. 3.3). 123 J. Odjoumani, V. Ziegler 3.2 Results for the Tribonacci sequence Let us assume that (n, x ) is a solution to (13) and in view of (5) we assume that n ≥ 10. Then (13) implies n n aα 2|b||β| −3n/2 − 1 ≤ ≤ 1.55 α . x x p p Taking logarithms on both sides yields −3n/2 |n log α − x log p + log a| < 2.33 α (18) We proceed to apply Matveev’s result. We set D = 3, κ = 1and m = 3. η = a,η = α, η = p, 1 2 3 b = 71, b = n, b = x . 1 2 3 With this choice we have A = 3h(a)< 3.79, A = 3h(α) = 3log α< 0.61, A = 3log p. 1 2 3 Furthermore we note that x n n p = T < 1.001aα <α . (19) Thus b |A | < 3n log α and therefore i i log α log α B = max 1, max |b |A /A : 1 ≤ j ≤ m < max 1, n = n . j j m log p log p Finally we compute the quantities C (3) and C numerically, put everything together and obtain 2 12 C (3)C W D Ω< 1.174 · 10 log p log(25.671B). 0 0 We apply the bound found above to inequality (18) and we obtain 3n log α log(2.33) 1.174 · 10 log(25.671B)> · + . 2 log p log p Let us write B = 25.671B, then we obtain the inequality ˜ ˜ 3.06 · 10 log B < B. 11 11 Thus we obtain B < 8.411 · 10 , which yields n < 1.62 · 10 log p. Therefore we have the following lemma. Lemma 8 Let (n, x ) be a solution to Diophantine Equation (13). Then we have n < 1.62 · 11 10 10 log p and x < 9.88 · 10 . n log α Proof Only the bound for x is left to prove. However, since x < due to Inequality (19) log p the bound for x follows immediately. Remark 4 For a fixed prime p it is easy to find explicit upper bounds for n using Lemma 8. Applying Baker–Davenport reduction to Inequality (18) we will find rather small explicit upper bounds for n, which are small enough to perform an explicit computer search for all solutions. This will be discussed in detail in Sect. 5. 123 On prime powers in linear recurrence sequences 3.3 Results for the added by one Lucas sequence Now, we will consider Diophantine Equation (14). In view of (6) we assume that n > 10. In this case Diophantine Equation (14) can be written as n n x γ + 1 + δ = p and we obtain due to (6) the inequality γ 1.009 −n − 1 < < 1.009 γ . x  x p p Taking logarithms yields −n |n log γ − x log p| < 1.52 γ . (20) We apply Laurent’s result to this inequality. Therefore we note that with K = Q(γ , p) we have D =[K : Q]= 2. Let us set η = γ, η = p, b = n, b = x . 1 2 1 2 Accordingto(9) we choose A = 0.2407 and A = log p. With this choice we obtain 1 2 n x n b = + < 2A 2A log p 2 1 due to inequality (7). If we assume that log b ≤ 14.62 we obtain n < 2.24 · 10 log p and due to (7) we also obtain x < 1.08 · 10 . Therefore we will assume that log b > 14.62 and Lemma 2 yields n log γ − log(1.52)< 68.94 log p log 1.5b . 1.5n If we set b = 1.5b = we obtain the inequality log p ˜ ˜ b < 143.3(log b) . Therefore we obtain that b < 12822 but this yields a contradiction to our assumption that log b > 14.62. Therefore we have: Lemma 9 Let (n, x ) be a solution to Diophantine Equation (14). Then we have n < 2.24 · 6 6 10 log p and x < 1.08 · 10 . 4 Finding absolute upper bounds 4.1 The multiplicative independence condition Let us consider the Diophantine equation U = p , with n ≥ N and p ∈ / S . Assume n 0 0 that U satisfies the multiplicative independence condition, i.e. log a and log α are linearly independent over Q. And in view of Theorem 1 we assume that there exist at least two solutions (n , x ) and (n , x ) with n < n .From(15) we obtain a system of inequalities: 1 1 2 2 1 2 3 α |n log α − x log p + log a| < C , 1 1 5 2 α 3 α 2 |n log α − x log p + log a| < C   . 2 2 5 2 α 123 J. Odjoumani, V. Ziegler We eliminate log p from this system by multiplying the first inequality by x and the second by x and subtracting them from each other. Then we obtain due to Lemma 7 n n n 1 2 1 3 α 3 α α 2   2   2 |Δ log α + Δ log a| < x C + x C < C (21) 1 2 5 1 5 10 2 α 2 α α with Δ = n x −n x and Δ = x −x .Notethat(21) implies that there exists an effectively 1 2 2 1 1 2 1 computable constant N such that for all n ≥ N we have 1 1 1 |Δ log α + Δ log a| < 1. Let us assume for the sake of the argument that max{N , N }≤ n < n . First we note that 0 1 1 2 Δ = 0 since otherwise we would obtain x = x and therefore also n = n and the two 1 1 2 1 2 solutions would be identical. Note that we assume that N ≤ n < n and that U is strictly 0 1 2 n increasing for n ≥ N . Let us assume for the moment that Δ = 0. If Δ = 0 we obtain α 1 | log a| < C which implies n ≤ C . 1 11 Now, let us consider the case that Δ = 0. Note that Δ < C due to Lemma 7. Therefore 1 9 inequality (21) yields α 1 Δ | log a|+ C 1 10 |Δ|≤ < C . | log α| We may apply Matveev’s result (Lemma 1) or Laurent’s result (Lemma 2) to the linear form Λ = Δ log α + Δ log a and obtain that −C < log |Δ log α + Δ log a| < −n C , 13 1 1 14 i.e. that n < C . Note that the last inequality holds for some Constant C since we assume 1 15 14 that N ≤ n < n . Therefore we have proved: 1 1 2 Proposition 1 Assume that U satisfies the multiplicative independence condition and that the Diophantine equation U = p , with n > max{N , N } and p ∈ / S has at least two n 0 1 0 solution (n , x ) and (n , x ) with max{N , N }≤ n < n and x , x = 0. Then there 1 1 2 2 0 1 1 2 1 2 exists an effective computable constant C such that n < C . 15 1 15 Let S(U ) be the set of primes p such that U is a power of p for some index n with 0 ≤ n ≤ C together with the set of primes coming from the set S . Note that the set S(U ) is 15 0 finite and because C is effectively computable the set S(U ) is indeed effectively computable (at least in principal). With this notation we immediately deduce that the Diophantine equation U = p has at most one solution with x = 0if p ∈ / S(U ). Thus we have proved Theorem 1 in this case. Let us note that for a concrete given sequence U one can apply results from the theory of continued fractions (e.g. Lemma 5) to deduce from inequality (21) rather small upper bound for n . This method will be applied in the next subsection, when we deal with the Tribonacci sequence. 123 On prime powers in linear recurrence sequences 4.2 Results for the Tribonacci sequence We consider the Diophantine equation T = p . And in view of Theorem 2 we assume that there exist at least two solutions (n , x ) and (n , x ). If we can show that two such solutions 1 1 2 2 with 4 ≤ n < n do not exist we have proved Theorem 2. In view of Inequality (18)we 1 2 assume that 9 ≤ n < n . With these assumptions Inequality (18) holds and we obtain a 1 2 system of inequalities: −3n /2 |n log α − x log p + log a| < 2.33 α 1 1 −3n /2 |n log α − x log p + log a| < 2.33 α . 2 2 Multiplying the first inequality by x and the second by x and eliminating the log p term 1 2 we obtain −3n /2 −3n /2 1 2 |Δ log α + Δ log a| < x 2.33 α + x 2.33α 1 2 1 −3n /2 < 2.33 x α (1 + 1/α) (22) −3n /2 < 3.6 x α with Δ = n x −n x and Δ = x − x .First,wenotethat Δ = 0 since otherwise x = x 1 2 2 1 1 2 1 1 1 2 and therefore also n = n and the two solutions would be identical. 1 2 Let us assume for the moment that Δ = 0. In this case we obtain −3n /2 | log a| < 3.6 x α . Together with Lemma 8 we obtain in this case n ≤ 30.3. Therefore we assume for the rest of this subsection that Δ = 0and n > 30. Using the upper bound for x from Lemma 8 together with the assumption that n ≥ 31 yields 2 1 −3n /2 Δ | log a|+ 3.6x α 1 2 Δ ≤ < 1.77 · 10 . log α And therefore we obtain log α Δ x 1 2 −3n /2 11 −3n /2 1 1 − < 3.6 α < 3.27 · 10 α . − log a Δ −|Δ| log a Since continued fractions are the best approximations we compute the continued fractions log α of μ = and notice that the 32-nd convergent p /q = is the first 32 32 − log a 217306873051 convergent such that its denominator is larger than 1.77·10 . Moreover, we compute A = 15 and therefore we obtain by Lemma 5 the inequality 1 log α Δ −24 11 −3n /2 1.24 · 10 < < − < 3.27 · 10 α − log a Δ (A + 2)q which yields n ≤ 89.7. If we factor the first 89 Tribonacci numbers and only take those into account which are primes or prime powers we obtain Proposition 2 If the Diophantine equation T = p has at least two solutions (n , x ) and n 1 1 (n , x ) with 0 ≤ n < n and x = 0,then 2 2 1 2 (n , x , p) = (3, 1, 2), (4, 2, 2), (5, 1, 7), (6, 1, 13), (9, 4, 3), (10, 1, 149), 1 1 (17, 2, 103)(86, 1, 19341322569415713958901), if a second solution exists at all. 123 J. Odjoumani, V. Ziegler Remark 5 The proof of Theorem 2 is complete, if we can show that the Diophantine equation T = p , with n ≥ 3 has at most one solution if p = 3, 7, 13, 103, 149 or p = 19341322569415713958901 and at most two solutions if p = 2. As already mentioned this can be done by using the Baker–Davenport reduction which will be discussed in Sect. 5. 4.3 The strong dominant root case Since the case that a and α are multiplicatively independent has been resolved, we may assume that a and α are multiplicatively dependent, that is we fix integers z and z such that 1 2 z z 1 2 α a = 1and (z , z ) = (0, 0).Thatis 1 2 z n − z 2 1 n log α + log a = log α. Let us also note that since we assume a strong dominant root condition we have instead of (15) the inequality n n n α α α 2   2   2 C < |n ˜ log α − xz log p| < 2C z = C , 16 2 5 2 17 α α α with n ˜ = z n − z . 2 1 Before we proceed with the proof of Theorem 1 in the strong dominant root case we prove the following lemma. Lemma 10 There exists an effective computable constant N such that C and C can be 1 16 17 C α chosen such that <  , provided that n ≥ N . C α 16 2 Proof Since p = U there is a positive constant A such that n 3 x n n n p = aα + a α + θ A |α | 2 3 3 for some |θ|≤ 1. With these notations we compute Λ =|x log p − n log α − log a|= log aα n n a α A |α | 2 3 3 ≤ log 1 + + . n n aα aα Now, we find an explicit upper bound for Λ, provided that n is chosen large enough such that a α 2 A |α | 1 2 3 3 + < holds. According to Lemma 4 we have n n aα aα 2 n n n n 2 a α A α a α A α 2 3 2 3 2 3 2 3 Λ ≤ + + + n   n   n   n aα aα aα aα n n n n 2 2n a α A α a α A α A α 2 3 2 3 2 3 2 3 3 3 = · 1 + + + 2 + n      n n n n n aα a α aα aα a aα α 2 2 2 2 n    2 a α A a A A α α 2 3  2  3    2  3 2 3 < · 1 + + + 2 + max , aα a a a aa  α α 2 2 2 Similarly we obtain n    2    n a α A a A A α α 3  2  3    2  3 2 3 Λ> · 1 − +   + 2 +   max   , aα a a a aa α α 2 2 2 123 On prime powers in linear recurrence sequences Under the assumption that n ≥ N we can choose C and C such that 16 17 C 1 +˜cΓ ≤ (23) C 1 −˜cΓ α α A a A 2 3 3 2 3 3 where we write Γ = max , and c˜ = + + 2 + . Since the right α α a a a  aa 2 2 2 hand side of (23)converges to 1as N →∞ we obtain the content of the lemma. Let us assume that U = p has two solutions (n , x ) and (n , x ) with x , x > 0and n 1 1 2 2 1 2 N ≤ n < n . This yields the following system of inequalities: 0 1 2 n n α 1 α 1 2   2 C < |n ˜ log α − x z log p| < C 16 1 1 2 17 α α n n 2 2 α α 2   2 C < |n ˜ log α − x z log p| < C . 16 2 2 2 17 α α Eliminating log p yields similar as in the case that a and α are multiplicatively independent the inequality n n n α 1 α 2 α 1 2   2   2 C x   − C x   < |Δ log α| < C   , 16 2 17 1 18 α α α with Δ =˜n x −˜n x . Let us note that if we assume that n ≥ N where N is the bound 1 2 2 1 1 1 1 from Lemma 10 we obtain α 1 n −n 2 2 1 C x C α α 17 1 17 < < ≤ = , α 2 C x C α α 16 2 16 2 2 which implies n n 1 2 α α 2   2 C x − C x > 0. 16 2 17 1 α α Therefore we deduce that Δ =˜n x −˜n x = 0, provided that n ≥ N . Therefore we obtain 1 2 2 1 1 α 1 | log α| < C which yields n < C and we obtain: 1 19 Proposition 3 Assume that U satisfies the strong dominant root condition and that the Diophantine equation U = p with n > N and p ∈ / S has at least two solutions (n , x ) n 0 0 1 1 and (n , x ) with n < n and x , x = 0. Then there exists an effective computable constant 2 2 1 2 1 2 C such that n < C . 19 1 19 As in the case that the multiplicative independence condition holds we deduce now The- orem 1 in this case. Thus Theorem 1 is completely proved. 4.4 Results for the added by one Lucas sequence Let us assume that the Diophantine equation L = p has at least two solutions (n , x ) n 1 1 and (n , x ). We follow the arguments of the strong dominant root case where log α and 2 2 log a are linearly dependent. First we compute a lower bound N for which Lemma 10 holds. Therefore let us note that we have a = a = 1 and that we can choose A = 1. Thus we 2 3 123 J. Odjoumani, V. Ziegler √ √ 1+ 5 1− 5 have c˜ = 5. Moreover, we have α = , α = 1and α = and we can choose 2 3 2 2 −1+ 5 −1 Γ = = γ in (23). Therefore we have to find a bound N such that −n 1 + 5 1 + 5γ −n 2 1 − 5γ for all n ≥ N . By an explicit computation we obtain that N = 7 is sufficient. 1 1 Now we consider the following system of inequalities under the assumption that n > 7. −n |n log γ − x log p| < 1.52γ 1 1 −n |n log γ − x log p| < 1.52γ . 2 2 By eliminating log p we obtain −n −n 6 −n 1 2 1 |Δ log γ | < 1.52x γ + 1.52x γ < 3.29 · 10 γ . 2 1 Since the computations of the previous subsection we may assume that Δ = 0 and obtain n 6 γ < 6.83 · 10 and therefore we have n < 32.71. If we factor the first 32 members of the sequence L and only consider those which are primes or prime powers we obtain Proposition 4 If the Diophantine equation L = p has at least two solutions (n , x ) and n 1 1 (n , x ) with 0 ≤ n < n and x = 0,then 2 2 1 2 (n , x , p) = (0, 1, 3), (1, 1, 2), (2, 2, 2), (3, 1, 5), (4, 3, 2), (6, 1, 19), (18, 1, 5779), 1 1 if a second solution exists at all. 5 Reduction of the upper bounds for a fixed prime The purpose of this last section is to prove Theorems 2 and 3 . 5.1 Application of the Baker–Davenport reduction method We consider the Diophantine equation T = p with x = 0and p ∈ P ={2, 3, 7, 13, 103, 149, p } with p = 19341322569415713958901 and n < 1.62 · 10 log p. In particular we consider Inequality (18) and divide it through log p and obtain log α log a 2.33 3log α n + − x < exp − n . log p log p log p 2 Thus we apply Lemma 6 with log α log a 2.33 3log α μ = ,τ = , c = , c = , N = 1.62 · 10 log p 1 2 log p log p log p 2 for each p ∈ P. In each case we obtain a new bound for n.InTable 1 we indicate for which prime p the -th convergent yields a new upper bound B for n. 123 On prime powers in linear recurrence sequences Table 1 New bounds n ≤ B after Bp the Baker–Davenport reduction 220 33.18 103 33 31.8 321 35.65 149 24 33.07 723 28.44 p 58 89.27 13 34 32.12 Table 2 Bounds for n after the pA Bp A application of Lemma 5 211 15 71.53 19 26 12 72.14 349 16 71.87 5779 2780 5 84.88 520 13 66.97 Thus we conclude that if T = p has two solutions (n , x ) and (n , x ) with x , x = 0 n 1 1 2 2 1 2 and n < n ,then n ≤ 89. However a quick computer search among the first 89 Tribonacci 1 2 2 numbers shows that only in the case that p = 2 we have two solutions namely T = 2and T = 4. Thus the proof of Theorem 2 is complete. 5.2 Using continued fractions Now we consider the Diophantine equation L = p with x = 0and p ∈ P = {2, 3, 5, 19, 5779} and x < 1.08 · 10 . In particular we consider the inequality n log p −n − < 3.54γ x log γ log p which we deduce from (20). We apply Lemma 5 to this inequality with μ = and the log γ smallest convergent p /q to μ such that q > 1.08 · 10 . For the continued fraction to μ we compute according to Lemma 5 the quantity A and obtain 1 n log p −n < − < 3.54γ x log γ (2 + A)q and therefore we obtain log 3.54(2 + A)q n < B = . log γ If we compute all the quantities for all p ∈ P we obtain new bounds for n.InTable 2 we give the relevant quantities for each prime p ∈ P. This implies that in any case n ≤ 84. Thus we compute the first 84 members of L and check whether they are a power of any of the primes p ∈ P. A quick computer search yields that the only case for which more than one solution exists is p = 2. In this case we have the three solutions L = 2, L = 4and L = 8. Thus Theorem 3 is proved. 1 2 4 Acknowledgements We want to thank the anonymous referee for his/her careful reading and valuable sug- gestions. Funding Open access funding provided by Paris Lodron University of Salzburg. 123 J. Odjoumani, V. Ziegler Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References 1. Baker, A.: A sharpening of the bounds for linear forms in logarithms. II. Acta Arith. 24, 33–36 (1973) (errata insert) 2. Baker, A.: A Concise Introduction to the Theory of Numbers. Cambridge University Press, Cambridge (1984) 2 2 2 2 3. Baker, A., Davenport, H.: The equations 3x − 2 = y and 8x − 7 = z .Q.J.Math.Oxf.Ser. 2(20), 129–137 (1969) 4. Bilu, Y., Hanrot, G., Voutier, P.M.: Existence of primitive divisors of Lucas and Lehmer numbers. J. Reine Angew. Math. 539, 75–122 (2001). With an appendix by M. Mignotte 5. Bugeaud, Y., Mignotte, M., Siksek, S.: Classical and modular approaches to exponential Diophantine equations. I. Fibonacci and Lucas perfect powers. Ann. Math. (2) 163(3), 969–1018 (2006) 6. Bugeaud, Y., Kaneko, H.: On perfect powers in linear recurrence sequences of integers. Kyushu J. Math. 73(2), 221–227 (2019) 7. Everest, G., van der Poorten, A., Shparlinski, I., Ward, T.: Recurrence Sequences. Mathematical Surveys and Monographs, vol. 104. American Mathematical Society, Providence (2003) 8. Gómez Ruiz, C.A., Luca, F.: Multiplicative independence in k-generalized Fibonacci sequences. Lith. Math. J. 56(4), 503–517 (2016) 9. Laurent, M.: Linear forms in two logarithms and interpolation determinants. II. Acta Arith. 133(4), 325– 348 (2008) 10. Matveev, E.M.: An explicit lower bound for a homogeneous rational linear form in logarithms of algebraic numbers. II. Izv. Ross. Akad. Nauk Ser. Mat. 64(6), 125–180 (2000) 11. Petho, ˝ A.: On the solution of the Diophantine equation G = p . In: EUROCAL ’85, vol. 2 (Linz, 1985), Lecture Notes in Computer Science, vol. 204. Springer, Berlin, pp. 503–512 (1985) 2t t 2 12. Shorey, T.N., Stewart, C.L.: On the Diophantine equation ax + bx y + cy = d and pure powers in recurrence sequences. Math. Scand. 52(1), 24–36 (1983) 13. Shorey, T.N., Tijdeman, R.: Exponential Diophantine equations. Cambridge Tracts in Mathematics, vol. 87. Cambridge University Press, Cambridge (1986) 14. The Sage Developers. SageMath, the Sage Mathematics Software System (Version 8.8). https://www. sagemath.org (2019) Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Annales mathématiques du Québec Springer Journals

On prime powers in linear recurrence sequences

Loading next page...
 
/lp/springer-journals/on-prime-powers-in-linear-recurrence-sequences-90z1MvT03U

References (20)

Publisher
Springer Journals
Copyright
Copyright © The Author(s) 2021
ISSN
2195-4755
eISSN
2195-4763
DOI
10.1007/s40316-021-00163-9
Publisher site
See Article on Publisher Site

Abstract

In this paper we consider the Diophantine equation U = p where U is a linear recurrence n n sequence, p is a prime number, and x is a positive integer. Under some technical hypotheses on U , we show that, for any p outside of an effectively computable finite set of prime numbers, there exists at most one solution (n, x ) to that Diophantine equation. We compute this exceptional set for the Tribonacci sequence and for the Lucas sequence plus one. Keywords Diophantine equations · Linear recurrence sequences · Exponential Diophantine equations Mathematics Subject Classification 11D45 · 11B37 · 11D61 Résumé Nous considérons dans cet article l’équation U = p ,où U est une suite récurrente linéaire, n n p un nombre premier, et x un entier positif. Sous des hypothèses techniques, nous montrons que, pour tout p en dehors d’un ensemble fini calculable de nombres premiers, cette équation admet au plus une solution (n, x ). Nous déterminons cet ensemble exceptionnel pour la suite de Tribonacci et pour la suite de Lucas plus un. 1 Introduction Let U = (U ) be a sequence of integers satisfying a recurrence relation n n≥0 U = s U + ··· + s U , n ≥ 0. n+d d−1 n+d−1 0 n Volker Ziegler was supported by the Austrian Science Fund (FWF) under the project I4406. The first discussion on this project was possible when Japhet Odjoumani was at University of Graz under the support of Coimbra group. B Volker Ziegler volker.ziegler@sbg.ac.at Japhet Odjoumani japhet.odjoumani@imsp-uac.org Institut de Mathématiques et de Sciences Physiques, Université d’Abomey-Calavi, Dangbo, Benin University of Salzburg, Hellbrunnerstrasse 34/I, 5020 Salzburg, Austria 123 J. Odjoumani, V. Ziegler Let us assume that this linear recurrence is of order d,thatis U does not satisfy a recurrence relation for a smaller d.Wedenoteby d d−1 m p (X ) = X − s X − ··· − s = (X − α ) U d−1 0 i i =1 its characteristic polynomial. In case that all multiplicities m are equal to 1 we call U a simple recurrence relation. If U is a simple recurrence sequence of order d we can write n n n U = a α + a α + ··· + a α n 1 2 d 1 2 d with a ,..., a ∈ C\{0}. If the characteristic roots also satisfy 1 d |α | > |α | ≥ ··· ≥ |α | 1 2 d we say that U satisfies a dominant root condition. If we even have |α | > |α | > |α | ≥ ··· ≥ |α | 1 2 3 d we say that U satisfies a strong dominant root condition. We say that U satisfies the multi- plicative independence condition if the numbers a and α are multiplicatively independent, 1 1 that is that the only integral solution to a α = 1is (x , y) = (0, 0). 1 1 A sequence of special interest in this paper will be the Tribonacci sequence T = (T ) n n≥0 which is a linear recurrence sequence of order 3 given by T = T + T + T , n ≥ 0 n+3 n+2 n+1 n and T = 0, T = 1and T = 1. We will also have a closer look on the linear recurrence 0 1 2 sequence L = (L ) also of order 3 given by n n≥0 L = 2L − L , n ≥ 0 n+3 n+2 n and L = 3, L = 2and L = 4. Note that this recurrence sequence is the classical Lucas 0 1 2 ˜ ˜ ˜ sequence L = (L ) added by 1, where L is given by n n≥0 ˜ ˜ ˜ L = L + L , n ≥ 0 n+2 n+1 n ˜ ˜ ˜ and L = 2and L = 1. In particular, we have L = L + 1 and will therefore call L the 0 1 n n added by one Lucas sequence. There is a rich literature on Diophantine equations involving linear recurrence sequences and we refer to [7] for an overview. In this paper we will focus on Diophantine equations of the form U = y .Inthe casethat U is a binary recurrence sequence Petho[ ˝ 11] and, n n independently, Shorey and Stewart [12](seealso[13, Chapter 9]) showed that such equations have only finitely many solutions (n, m, y) ∈ N × Z with y, m > 1. In the case of higher order recurrence sequences Shorey and Stewart [12] showed that under a dominant root assumption a solution (n, y, m) to U = y with y, m > 1 satisfies m < C,where C is an effectively computable constant. Moreover, a recent result due to Bugeaud and Kaneko [6] implies that the equation U = y with y, m > 1 has at most finitely many solutions and their number can be explicitly determined. However, for a given binary sequence U it is a very hard task to find all solutions to U = y . In the case of the Fibonacci and the Lucas sequence this task was finally resolved by Bugeaud, Mignotte and Siksek [5]. In the case of recurrence sequences of higher order (satisfying a dominant root condition) the methods fail to find all solutions (n, y, m) to U = y with y, m > 1 and results similar to those of Petho, ˝ Shorey and Stewart for the binary case have not been proved yet. 123 On prime powers in linear recurrence sequences In this paper we are interested in the following problem. Let U = (U ) beafixed n n≥0 sequence and P ={p ,..., p } a finite set of primes. How many solutions (n, x ,..., x ), 1 t 1 t with n, x ,..., x non-negative integers does the equation 1 t x x 1 t U =±p ··· p n t have? Of course the theory of S-unit equations yields a bound for the number of solutions depending only on t. These bounds are usually far from the optimal bound and do not reflect what can be expected from numerical experiments. In this paper we resolve the case that t = 1. That is we consider Diophantine equations of the form U = p for a fixed sequence U = (U ) and arbitrary, but fixed prime p. By Baker’s method using lower bounds n n≥0 for linear forms in logarithms this equation can be solved easily for particular values for p. However, in this paper we show that up to a finite effective computable set of primes S = S(U ) the Diophantine equation U = p has at most one solution. More precisely we show: Theorem 1 Let U = (U ) be a simple, linear recurrence sequence of order at least n n≥0 two, satisfying the dominant root condition. Further we assume that U satisfies one of the following conditions – U satisfies the strong dominant root condition; – U satisfies the multiplicative independence condition. Then there exists an effective computable set of primes S such that the equation U =±p has at most one solution (n, x ) ∈ N with x = 0 unless p ∈ S. Remark 1 Let us note that the assumption that U is simple can be dropped. To avoid technical difficulties we refrain from this extension. The set S in Theorem 1 is not only effective computable, but we can also provide an efficient algorithm to compute the set S and find all exceptional primes. We demonstrate the method by applying it to the Tribonacci sequence T and the sequence L and prove the following two theorems: Theorem 2 The Diophantine equation T = p has at most one solution (n, x ) with x = 0 unless p = 2. In the case that p = 2 there exist two solutions, namely T = 2 and T = 4. 3 4 Theorem 3 The Diophantine equation L = p has at most one solution (n, x ) with x = 0 unless p = 2. In the case that p = 2 there exist three solutions, namely L = 2,L = 4 and 1 2 L = 8. It is easy to see that the Tribonacci sequence T is indeed of order three, is simple and satisfies the dominant root condition but not the strong dominant root condition. However, the Tribonacci sequence satisfies the multiplicative independence condition (see also Sect. 2). On the other hand it is easy to see that the Lucas sequence added by 1, i.e. the sequence L, is simple and of order three and satisfies the strong dominant root condition, but does not satisfy the multiplicative independence condition. Moreover let us note that a result of Shorey and Stewart [12, Theorem 4] implies that the Diophantine equation L = y has only finitely many solutions (n, y, m) with y, m > 1and n even. This implies even a stronger result than stated in Theorem 3, considering only even indices n. But to our knowledge no such result is known for odd indices n and thus our result (Theorem 3) indeed complements the result due to Shorey and Stewart. 123 J. Odjoumani, V. Ziegler Finally let us note that Theorem 1 can be easily proved in the case that U is a Lucas– Lehmer sequence, by applying the Primitive Divisor Theorem proved by Bilu, Hanrot, and Voutier [4]. Therefore we choose the sequences T and L to avoid cases that could easily be solved by the Primitive Divisor Theorem. We also want to note that the result of Theorem 2 can easily be deduced by a result due to Gomez and Luca [8] who found all multiplicatively dependent pairs of k-generalized Fibonacci numbers. However, let us note that our proof of Theorem 2 yields an alternative approach. In the next section we provide some useful lemmas and inequalities. In Sect. 3 we will use Baker’s method to obtain upper bounds for n in the case that p is arbitrary but fixed and will therefore reprove a theorem due to Shorey and Tijdeman [12, Theorem 3]. The heart of the proof is in Sect. 4, where we show that the existence of two solutions (n , x ) and 1 1 (n , x ) implies an effectively computable upper bound for n . This allows us to finally prove 2 2 1 Theorem 1. Unfortunately the absolute upper bounds are too large to successfully perform a computer search. However, in the case of the Tribonacci sequence and the Lucas sequence added by one the bound for n is small enough to find small lists of possible candidates of x x primes p such that the Diophantine equations T = p and L = p may have two solutions. n n Using the upper bounds found in Sect. 3 together with the Baker–Davenport reduction (see Lemma 6) and using lower bounds for approximations by continued fractions (see Lemma 5) we find all primes p that admit more than one solution. These reduction procedures are discussed in the final Sect. 5. Throughout the paper we will denote by C , C ,... positive and effectively computable 1 2 constants. 2 Auxiliary results To ease the notation let us write a = a and α = α .Since U is defined over the integers all 1 1 n roots of the characteristic polynomial are algebraic integers. Since U is simple, of order at least two and satisfies a dominant root condition we conclude that |α| > 1 and furthermore n n+1 that a and α are real. Replacing U by (−1) U or (−1) U or −U we may also assume n n n n that both α and a are positive. With these assumptions and notations in force there exist effective computable constants C , C , C > 0 such that 1 2 3 n x n C aα < U = p < C aα (1) 1 n 2 which implies n log α + log (aC ) n log α + log(aC ) 1 2 < x < . (2) log p log p We also have n n U − aα < C |α | , (3) n 3 2 n log α thus we have x  . In case that U satisfies also a strong dominant root condition we log p obtain a lower bound n n C |α | < U − aα . (4) 4 2 n Finally let us note that there exists N such that |U | is strictly increasing for n ≥ N . 0 n 0 In the case of the Tribonacci sequence we can make these computations explicit. In particular, we have that n n n ¯ ¯ T = aα + bβ + bβ . 123 On prime powers in linear recurrence sequences 3 2 where α, β und β are the roots of the characteristic Polynomial X − X − X − 1, that is we have α ∼ 1.83929,β ∼−0.419643 + 0.606291i , 2 2 5α − 3α − 4 5β − 3β − 4 a = ∼ 0.336228, b = ∼−0.168114 − 0.198324i . 22 22 Note that a, b und b are computed from solving the linear system 0 0 0 aα + bβ + bβ = 0, 1 1 1 ¯ ¯ aα + bβ + bβ = 1, 2 2 2 ¯ ¯ aα + bβ + bβ = 1. −1/2 ¯ ¯ Moreover, let us note that αββ =−1 and therefore |β|=|β|=|α| .Fromthese estimations for α and β it is clear that T ∼ aα . In particular we have that n x n 0.999aα < T = p < 1.001aα (5) n log α provided that n > 8. Note that (5) implies that x < . Finally, let us note that the log p Tribonacci sequence T is strictly increasing for n ≥ 2. In the case of the sequence L we find the explicit formula n n n L = γ + 1 + δ , where √ √ 1 + 5 1 − 5 γ = and δ = . 2 2 −1 Note that γδ =−1 and therefore |δ|=|γ | . Obviously L satisfies the strong dominant root condition but not the multiplicative independence relation. However, under the assumption that n > 10 we obtain the estimates n x n γ < L = p < 1.009γ (6) which imply n log γ n log γ + 0.01 < x < . (7) log p log p We also have the inequality 0.99 < L − γ < 1.01. (8) Finally let us note that L is strictly increasing for n ≥ 1. In this paper we will make extensive use of lower bounds for linear forms of logarithms of complex numbers. In particular we will use a result due to Matveev [10]. Let η = 0bean algebraic number of degree d and let a (X − η ) ··· (X − η ) ∈ Z[X ] 1 d be the minimal polynomial of η. Then the absolute logarithmic Weil height is defined by h(η) = log |a|+ max{0, log |η |} . i =1 In the case that η is a rational number, say η = P/Q ∈ Q with P, Q integers such that gcd(P, Q) = 1, we have h(P/Q) = max{log |P|, log |Q|}. With this basic notation we 123 J. Odjoumani, V. Ziegler have the following result on lower bounds for linear forms in logarithms due to Matveev [10]. Lemma 1 Denote by η ,...,η algebraic numbers, neither 0 nor 1,by log η , ..., log η 1 m 1 m determinations of their logarithms, by D the degree over Q of the number field K = Q(η ,...,η ), and by b ,..., b rational integers. Furthermore let κ = 1 if K is real 1 m 1 m and κ = 2 otherwise. Choose A ≥ max {Dh (η ) , | log η |} (1 ≤ i ≤ m) i i i and B = max 1, max |b |A /A : 1 ≤ j ≤ m . j j m Assume that b = 0 and log η ,..., log η are linearly independent over Z.Then m 1 m log |b log η + ··· + b log η |≥−C (m)C W D Ω, 1 1 m m 0 0 with Ω = A ··· A , 1 m 16 1 m m+1 C (m) = C (m,κ) = e (2m + 1 + 2κ) (m + 2) (4(m + 1)) em , m!κ 2 4.4m+7 5.5 2 C = log e m D log(eD) , W = log (1.5eB D log(eD)) . 0 0 However, in the case that the number of logarithms is m = 2 we have numerically rather good results due to Laurent [9]. In particular, we will use the following result: Lemma 2 Suppose that the numbers η , η , log η , log η are real and positive and that η 1 2 1 2 1 and η are multiplicatively independent. Then for positive integers b und b we have 2 1 2 log |b log η − b log η | 1 1 2 2 > −17.9D max log b + 0.38, 30/D, 1 log A log A , 1 2 where D =[Q(η ,η ) : Q], 1 2 A ≥ max{h(η), log η/D, 1/D} for i = 1, 2 and b b 1 2 b = + . D log A D log A 2 1 In order to apply the results of Matveev and Laurent we have to know the heights of the relevant quantities and also have to ensure that they are multiplicatively independent. In the case of the Tribonacci sequence and the Lucas sequence added by one we can use Sage [14] to compute the heights of the relevant quantities and obtain h(α) = h(β) = h(β) = 0.20312595447866 ··· < 0.20313, (9) h(a) = h(b) = h(b) = 1.2613965446394 ··· < 1.2614, h(γ ) = h(δ) = 0.2406059125298 ··· < 0.2407. To ensure the multiplicative independence of α, a and p in the case of the Tribonacci sequence and the Lucas sequence added by one the following lemma is helpful: 123 On prime powers in linear recurrence sequences Lemma 3 Let p be a prime, then α, a and p are multiplicatively independent and also γ and p are multiplicatively independent. Proof Since α and γ are units and p is a prime it is obvious that α and p respectively γ and p are multiplicatively independent. Thus it remains to show that α, a and p are multiplicatively independent. Let us note that the splitting field K = Q(α, β, β) of the characteristic polynomial X − X − X − 1 has class number 1. Moreover, 1/a is an algebraic integer with absolute Norm 4 2 N (1/a) = 2 · 11 . That is unless p = 2or p = 11 the lemma is proved. K /Q However, using Sage [14] we compute the following prime ideal factorizations (2) = p 2 2 2 (11) = q q q 1 2 3 (1/a) = p q q 1 2 which show that α, a, 2 and 11 are multiplicatively independent and thus proving the lemma. Also let us note the following helpful fact that can easily be proved using elementary calculus: Lemma 4 If |x − 1| < 1/2,then | log(x )| < 3|x − 1|/2 and if |y| < 1/2,then log(1 + y) = y + θ y for some |θ|≤ 1. Proof Replace x by 1 + y then the first statement is equivalent to the statement that |y| < 1/2 implies | log(1 + y)| < 3|y|/2. Thus assuming that |y| < 1/2wehave | log(1 + y)|= y − ± ... |y| ≤|y|+ 1 +|y|+|y| + ... |y| 1 =|y| 1 + · . 2 1 −|y| From this inequality we easily deduce both statements. In order to reduce the huge bounds coming from the applications of the results due to Matveev and Laurent we use continued fractions. In particular, we use the following two results: Lemma 5 Assume that μ is real and irrational and has the continued fraction expansion μ =[a ; a , a ,... ].Let be an integer and set A = max {a } and let p /q be the 0 1 2 1≤ j ≤ -th convergent to μ,then 1 p < μ − (2 + A)q for any rational fraction p/q with q ≤ q . Proof This follows from the inequality given in [2, page 47] combined with the best approx- imation property of continued fractions. 123 J. Odjoumani, V. Ziegler The second method is due to Baker and Davenport [3] for which we state a variant of this reduction method: Lemma 6 Given a Diophantine inequality of the form |nμ + τ − x | < c exp(−c n), (10) 1 2 with positive constants c , c and real numbers μ and τ . Assume that n < N and that there 1 2 is a real number κ> 1 such that there exists a convergent p/qto μ with 1 1 qμ < and qτ > , 2κ N κ where · denotes the distance to the nearest integer. Then we have log(2κqc ) n ≤ . Proof We consider inequality (10) and multiply it by q. Then under our assumptions we obtain c q exp (−c n) > |qx + nqμ + qτ|≥ | qτ − Nqμ | 1 2 (11) | | = qτ − N qμ > . 2κ 1 1 Note that the equality in (11) holds since by assumption N qμ < < and therefore 2κ 2 N qμ = Nqμ . Solving Inequality (11)for n yields the lemma. 3 A first upper bound In this section we will find absolute upper bounds for x and upper bounds for n in terms of p for solutions (n, x ) to the Diophantine equations U = p , n ≥ N (12) n 0 and T = p , n ≥ 2 (13) and L = p , n ≥ 1. (14) For a fixed prime p we can find such a bound by the standard procedure following the ideas of Shorey and Stewart [12] using Baker’s method. 3.1 General method Let us assume that that (n, x ) is a solution to (12). Then Eq. (12) yields :=C aα C |α | C α 3  2 − 1 ≤ ≤   . x x p p |C a| α Taking logarithms yields 3C α 5  2 Λ = |n log α − x log p + log a| <   (15) 2 α 123 On prime powers in linear recurrence sequences Let us note that in the case that α and a are multiplicatively dependent we have integers z and −z log α z z 1 1 2 z such that α a = 1. Since |α| > 1wehavethat z = 0 and therefore log a = . 2 2 Thus we obtain in this case the inequality 3z C α 2 5  2 | | (nz − z ) log α − xz log p <   . (16) 2 1 2 2 α We apply Matveev’s result depending on the multiplicative dependence of α and a to (15) with m = 3orto(16) with m = 2. Therefore let us note that the heights of α and a are effective computable and that the height of p is log p and therefore (in the case that m = 3) we have that A , A are bounded by an absolute effective computable constant and A = D log p, 1 2 3 with D =[Q(a,α) : Q]. Note that in the case that m = 2wehave that A is bounded by an effective computable constant and that A = D log p. Thus we have in any case B = max 1, max |b |A /A : 1 ≤ j ≤ m ≤ C . j j m 6 log p Let S be the set of primes that divide the norm of α, or divide the denominator of a,or divide the norm of a. Obviously the set S is finite and for all primes p ∈ / S we have that 0 0 α, a and p are multiplicatively independent. Therefore let us assume that p is not a member of S , hence we obtain together with (15) the inequality 3C α n log − n log > log |Λ| > −C log p log 2 α log p which yields n n < C log (17) log p log p provided that p ∈ / S . Note that in the case that m = 2 similar considerations lead to the same conclusion and in particular to Inequality (17). Lemma 7 Assume that (n, x ) is a solution to (12) and that p ∈ / S , then there exist effective computable constants C and C such that 8 9 n < C log p, and x < C . 8 9 Proof Inequality (17) implies an absolute upper bound for . Since inequality (2)wehave log p log |α| x  n and this immediately yields an absolute bound for x and also the bound for n log p stated in the lemma. Remark 2 In Lemma 7 we basically reproved a result of Shorey and Stewart [12, Theorem 3]. But instead of using a result of Baker [1] on lower bounds for linear forms in logarithms we use the more explicit and easier to apply result due to Matveev [10]. Remark 3 Let us note that in the case that log α and log a are linearly dependent over Q we may apply Laurent’s result (Lemma 2) and would obtain in concrete examples smaller numerical n n values for C but the log factor in Inequality (17) would turn into a log factor log p log p (see Sect. 3.3). 123 J. Odjoumani, V. Ziegler 3.2 Results for the Tribonacci sequence Let us assume that (n, x ) is a solution to (13) and in view of (5) we assume that n ≥ 10. Then (13) implies n n aα 2|b||β| −3n/2 − 1 ≤ ≤ 1.55 α . x x p p Taking logarithms on both sides yields −3n/2 |n log α − x log p + log a| < 2.33 α (18) We proceed to apply Matveev’s result. We set D = 3, κ = 1and m = 3. η = a,η = α, η = p, 1 2 3 b = 71, b = n, b = x . 1 2 3 With this choice we have A = 3h(a)< 3.79, A = 3h(α) = 3log α< 0.61, A = 3log p. 1 2 3 Furthermore we note that x n n p = T < 1.001aα <α . (19) Thus b |A | < 3n log α and therefore i i log α log α B = max 1, max |b |A /A : 1 ≤ j ≤ m < max 1, n = n . j j m log p log p Finally we compute the quantities C (3) and C numerically, put everything together and obtain 2 12 C (3)C W D Ω< 1.174 · 10 log p log(25.671B). 0 0 We apply the bound found above to inequality (18) and we obtain 3n log α log(2.33) 1.174 · 10 log(25.671B)> · + . 2 log p log p Let us write B = 25.671B, then we obtain the inequality ˜ ˜ 3.06 · 10 log B < B. 11 11 Thus we obtain B < 8.411 · 10 , which yields n < 1.62 · 10 log p. Therefore we have the following lemma. Lemma 8 Let (n, x ) be a solution to Diophantine Equation (13). Then we have n < 1.62 · 11 10 10 log p and x < 9.88 · 10 . n log α Proof Only the bound for x is left to prove. However, since x < due to Inequality (19) log p the bound for x follows immediately. Remark 4 For a fixed prime p it is easy to find explicit upper bounds for n using Lemma 8. Applying Baker–Davenport reduction to Inequality (18) we will find rather small explicit upper bounds for n, which are small enough to perform an explicit computer search for all solutions. This will be discussed in detail in Sect. 5. 123 On prime powers in linear recurrence sequences 3.3 Results for the added by one Lucas sequence Now, we will consider Diophantine Equation (14). In view of (6) we assume that n > 10. In this case Diophantine Equation (14) can be written as n n x γ + 1 + δ = p and we obtain due to (6) the inequality γ 1.009 −n − 1 < < 1.009 γ . x  x p p Taking logarithms yields −n |n log γ − x log p| < 1.52 γ . (20) We apply Laurent’s result to this inequality. Therefore we note that with K = Q(γ , p) we have D =[K : Q]= 2. Let us set η = γ, η = p, b = n, b = x . 1 2 1 2 Accordingto(9) we choose A = 0.2407 and A = log p. With this choice we obtain 1 2 n x n b = + < 2A 2A log p 2 1 due to inequality (7). If we assume that log b ≤ 14.62 we obtain n < 2.24 · 10 log p and due to (7) we also obtain x < 1.08 · 10 . Therefore we will assume that log b > 14.62 and Lemma 2 yields n log γ − log(1.52)< 68.94 log p log 1.5b . 1.5n If we set b = 1.5b = we obtain the inequality log p ˜ ˜ b < 143.3(log b) . Therefore we obtain that b < 12822 but this yields a contradiction to our assumption that log b > 14.62. Therefore we have: Lemma 9 Let (n, x ) be a solution to Diophantine Equation (14). Then we have n < 2.24 · 6 6 10 log p and x < 1.08 · 10 . 4 Finding absolute upper bounds 4.1 The multiplicative independence condition Let us consider the Diophantine equation U = p , with n ≥ N and p ∈ / S . Assume n 0 0 that U satisfies the multiplicative independence condition, i.e. log a and log α are linearly independent over Q. And in view of Theorem 1 we assume that there exist at least two solutions (n , x ) and (n , x ) with n < n .From(15) we obtain a system of inequalities: 1 1 2 2 1 2 3 α |n log α − x log p + log a| < C , 1 1 5 2 α 3 α 2 |n log α − x log p + log a| < C   . 2 2 5 2 α 123 J. Odjoumani, V. Ziegler We eliminate log p from this system by multiplying the first inequality by x and the second by x and subtracting them from each other. Then we obtain due to Lemma 7 n n n 1 2 1 3 α 3 α α 2   2   2 |Δ log α + Δ log a| < x C + x C < C (21) 1 2 5 1 5 10 2 α 2 α α with Δ = n x −n x and Δ = x −x .Notethat(21) implies that there exists an effectively 1 2 2 1 1 2 1 computable constant N such that for all n ≥ N we have 1 1 1 |Δ log α + Δ log a| < 1. Let us assume for the sake of the argument that max{N , N }≤ n < n . First we note that 0 1 1 2 Δ = 0 since otherwise we would obtain x = x and therefore also n = n and the two 1 1 2 1 2 solutions would be identical. Note that we assume that N ≤ n < n and that U is strictly 0 1 2 n increasing for n ≥ N . Let us assume for the moment that Δ = 0. If Δ = 0 we obtain α 1 | log a| < C which implies n ≤ C . 1 11 Now, let us consider the case that Δ = 0. Note that Δ < C due to Lemma 7. Therefore 1 9 inequality (21) yields α 1 Δ | log a|+ C 1 10 |Δ|≤ < C . | log α| We may apply Matveev’s result (Lemma 1) or Laurent’s result (Lemma 2) to the linear form Λ = Δ log α + Δ log a and obtain that −C < log |Δ log α + Δ log a| < −n C , 13 1 1 14 i.e. that n < C . Note that the last inequality holds for some Constant C since we assume 1 15 14 that N ≤ n < n . Therefore we have proved: 1 1 2 Proposition 1 Assume that U satisfies the multiplicative independence condition and that the Diophantine equation U = p , with n > max{N , N } and p ∈ / S has at least two n 0 1 0 solution (n , x ) and (n , x ) with max{N , N }≤ n < n and x , x = 0. Then there 1 1 2 2 0 1 1 2 1 2 exists an effective computable constant C such that n < C . 15 1 15 Let S(U ) be the set of primes p such that U is a power of p for some index n with 0 ≤ n ≤ C together with the set of primes coming from the set S . Note that the set S(U ) is 15 0 finite and because C is effectively computable the set S(U ) is indeed effectively computable (at least in principal). With this notation we immediately deduce that the Diophantine equation U = p has at most one solution with x = 0if p ∈ / S(U ). Thus we have proved Theorem 1 in this case. Let us note that for a concrete given sequence U one can apply results from the theory of continued fractions (e.g. Lemma 5) to deduce from inequality (21) rather small upper bound for n . This method will be applied in the next subsection, when we deal with the Tribonacci sequence. 123 On prime powers in linear recurrence sequences 4.2 Results for the Tribonacci sequence We consider the Diophantine equation T = p . And in view of Theorem 2 we assume that there exist at least two solutions (n , x ) and (n , x ). If we can show that two such solutions 1 1 2 2 with 4 ≤ n < n do not exist we have proved Theorem 2. In view of Inequality (18)we 1 2 assume that 9 ≤ n < n . With these assumptions Inequality (18) holds and we obtain a 1 2 system of inequalities: −3n /2 |n log α − x log p + log a| < 2.33 α 1 1 −3n /2 |n log α − x log p + log a| < 2.33 α . 2 2 Multiplying the first inequality by x and the second by x and eliminating the log p term 1 2 we obtain −3n /2 −3n /2 1 2 |Δ log α + Δ log a| < x 2.33 α + x 2.33α 1 2 1 −3n /2 < 2.33 x α (1 + 1/α) (22) −3n /2 < 3.6 x α with Δ = n x −n x and Δ = x − x .First,wenotethat Δ = 0 since otherwise x = x 1 2 2 1 1 2 1 1 1 2 and therefore also n = n and the two solutions would be identical. 1 2 Let us assume for the moment that Δ = 0. In this case we obtain −3n /2 | log a| < 3.6 x α . Together with Lemma 8 we obtain in this case n ≤ 30.3. Therefore we assume for the rest of this subsection that Δ = 0and n > 30. Using the upper bound for x from Lemma 8 together with the assumption that n ≥ 31 yields 2 1 −3n /2 Δ | log a|+ 3.6x α 1 2 Δ ≤ < 1.77 · 10 . log α And therefore we obtain log α Δ x 1 2 −3n /2 11 −3n /2 1 1 − < 3.6 α < 3.27 · 10 α . − log a Δ −|Δ| log a Since continued fractions are the best approximations we compute the continued fractions log α of μ = and notice that the 32-nd convergent p /q = is the first 32 32 − log a 217306873051 convergent such that its denominator is larger than 1.77·10 . Moreover, we compute A = 15 and therefore we obtain by Lemma 5 the inequality 1 log α Δ −24 11 −3n /2 1.24 · 10 < < − < 3.27 · 10 α − log a Δ (A + 2)q which yields n ≤ 89.7. If we factor the first 89 Tribonacci numbers and only take those into account which are primes or prime powers we obtain Proposition 2 If the Diophantine equation T = p has at least two solutions (n , x ) and n 1 1 (n , x ) with 0 ≤ n < n and x = 0,then 2 2 1 2 (n , x , p) = (3, 1, 2), (4, 2, 2), (5, 1, 7), (6, 1, 13), (9, 4, 3), (10, 1, 149), 1 1 (17, 2, 103)(86, 1, 19341322569415713958901), if a second solution exists at all. 123 J. Odjoumani, V. Ziegler Remark 5 The proof of Theorem 2 is complete, if we can show that the Diophantine equation T = p , with n ≥ 3 has at most one solution if p = 3, 7, 13, 103, 149 or p = 19341322569415713958901 and at most two solutions if p = 2. As already mentioned this can be done by using the Baker–Davenport reduction which will be discussed in Sect. 5. 4.3 The strong dominant root case Since the case that a and α are multiplicatively independent has been resolved, we may assume that a and α are multiplicatively dependent, that is we fix integers z and z such that 1 2 z z 1 2 α a = 1and (z , z ) = (0, 0).Thatis 1 2 z n − z 2 1 n log α + log a = log α. Let us also note that since we assume a strong dominant root condition we have instead of (15) the inequality n n n α α α 2   2   2 C < |n ˜ log α − xz log p| < 2C z = C , 16 2 5 2 17 α α α with n ˜ = z n − z . 2 1 Before we proceed with the proof of Theorem 1 in the strong dominant root case we prove the following lemma. Lemma 10 There exists an effective computable constant N such that C and C can be 1 16 17 C α chosen such that <  , provided that n ≥ N . C α 16 2 Proof Since p = U there is a positive constant A such that n 3 x n n n p = aα + a α + θ A |α | 2 3 3 for some |θ|≤ 1. With these notations we compute Λ =|x log p − n log α − log a|= log aα n n a α A |α | 2 3 3 ≤ log 1 + + . n n aα aα Now, we find an explicit upper bound for Λ, provided that n is chosen large enough such that a α 2 A |α | 1 2 3 3 + < holds. According to Lemma 4 we have n n aα aα 2 n n n n 2 a α A α a α A α 2 3 2 3 2 3 2 3 Λ ≤ + + + n   n   n   n aα aα aα aα n n n n 2 2n a α A α a α A α A α 2 3 2 3 2 3 2 3 3 3 = · 1 + + + 2 + n      n n n n n aα a α aα aα a aα α 2 2 2 2 n    2 a α A a A A α α 2 3  2  3    2  3 2 3 < · 1 + + + 2 + max , aα a a a aa  α α 2 2 2 Similarly we obtain n    2    n a α A a A A α α 3  2  3    2  3 2 3 Λ> · 1 − +   + 2 +   max   , aα a a a aa α α 2 2 2 123 On prime powers in linear recurrence sequences Under the assumption that n ≥ N we can choose C and C such that 16 17 C 1 +˜cΓ ≤ (23) C 1 −˜cΓ α α A a A 2 3 3 2 3 3 where we write Γ = max , and c˜ = + + 2 + . Since the right α α a a a  aa 2 2 2 hand side of (23)converges to 1as N →∞ we obtain the content of the lemma. Let us assume that U = p has two solutions (n , x ) and (n , x ) with x , x > 0and n 1 1 2 2 1 2 N ≤ n < n . This yields the following system of inequalities: 0 1 2 n n α 1 α 1 2   2 C < |n ˜ log α − x z log p| < C 16 1 1 2 17 α α n n 2 2 α α 2   2 C < |n ˜ log α − x z log p| < C . 16 2 2 2 17 α α Eliminating log p yields similar as in the case that a and α are multiplicatively independent the inequality n n n α 1 α 2 α 1 2   2   2 C x   − C x   < |Δ log α| < C   , 16 2 17 1 18 α α α with Δ =˜n x −˜n x . Let us note that if we assume that n ≥ N where N is the bound 1 2 2 1 1 1 1 from Lemma 10 we obtain α 1 n −n 2 2 1 C x C α α 17 1 17 < < ≤ = , α 2 C x C α α 16 2 16 2 2 which implies n n 1 2 α α 2   2 C x − C x > 0. 16 2 17 1 α α Therefore we deduce that Δ =˜n x −˜n x = 0, provided that n ≥ N . Therefore we obtain 1 2 2 1 1 α 1 | log α| < C which yields n < C and we obtain: 1 19 Proposition 3 Assume that U satisfies the strong dominant root condition and that the Diophantine equation U = p with n > N and p ∈ / S has at least two solutions (n , x ) n 0 0 1 1 and (n , x ) with n < n and x , x = 0. Then there exists an effective computable constant 2 2 1 2 1 2 C such that n < C . 19 1 19 As in the case that the multiplicative independence condition holds we deduce now The- orem 1 in this case. Thus Theorem 1 is completely proved. 4.4 Results for the added by one Lucas sequence Let us assume that the Diophantine equation L = p has at least two solutions (n , x ) n 1 1 and (n , x ). We follow the arguments of the strong dominant root case where log α and 2 2 log a are linearly dependent. First we compute a lower bound N for which Lemma 10 holds. Therefore let us note that we have a = a = 1 and that we can choose A = 1. Thus we 2 3 123 J. Odjoumani, V. Ziegler √ √ 1+ 5 1− 5 have c˜ = 5. Moreover, we have α = , α = 1and α = and we can choose 2 3 2 2 −1+ 5 −1 Γ = = γ in (23). Therefore we have to find a bound N such that −n 1 + 5 1 + 5γ −n 2 1 − 5γ for all n ≥ N . By an explicit computation we obtain that N = 7 is sufficient. 1 1 Now we consider the following system of inequalities under the assumption that n > 7. −n |n log γ − x log p| < 1.52γ 1 1 −n |n log γ − x log p| < 1.52γ . 2 2 By eliminating log p we obtain −n −n 6 −n 1 2 1 |Δ log γ | < 1.52x γ + 1.52x γ < 3.29 · 10 γ . 2 1 Since the computations of the previous subsection we may assume that Δ = 0 and obtain n 6 γ < 6.83 · 10 and therefore we have n < 32.71. If we factor the first 32 members of the sequence L and only consider those which are primes or prime powers we obtain Proposition 4 If the Diophantine equation L = p has at least two solutions (n , x ) and n 1 1 (n , x ) with 0 ≤ n < n and x = 0,then 2 2 1 2 (n , x , p) = (0, 1, 3), (1, 1, 2), (2, 2, 2), (3, 1, 5), (4, 3, 2), (6, 1, 19), (18, 1, 5779), 1 1 if a second solution exists at all. 5 Reduction of the upper bounds for a fixed prime The purpose of this last section is to prove Theorems 2 and 3 . 5.1 Application of the Baker–Davenport reduction method We consider the Diophantine equation T = p with x = 0and p ∈ P ={2, 3, 7, 13, 103, 149, p } with p = 19341322569415713958901 and n < 1.62 · 10 log p. In particular we consider Inequality (18) and divide it through log p and obtain log α log a 2.33 3log α n + − x < exp − n . log p log p log p 2 Thus we apply Lemma 6 with log α log a 2.33 3log α μ = ,τ = , c = , c = , N = 1.62 · 10 log p 1 2 log p log p log p 2 for each p ∈ P. In each case we obtain a new bound for n.InTable 1 we indicate for which prime p the -th convergent yields a new upper bound B for n. 123 On prime powers in linear recurrence sequences Table 1 New bounds n ≤ B after Bp the Baker–Davenport reduction 220 33.18 103 33 31.8 321 35.65 149 24 33.07 723 28.44 p 58 89.27 13 34 32.12 Table 2 Bounds for n after the pA Bp A application of Lemma 5 211 15 71.53 19 26 12 72.14 349 16 71.87 5779 2780 5 84.88 520 13 66.97 Thus we conclude that if T = p has two solutions (n , x ) and (n , x ) with x , x = 0 n 1 1 2 2 1 2 and n < n ,then n ≤ 89. However a quick computer search among the first 89 Tribonacci 1 2 2 numbers shows that only in the case that p = 2 we have two solutions namely T = 2and T = 4. Thus the proof of Theorem 2 is complete. 5.2 Using continued fractions Now we consider the Diophantine equation L = p with x = 0and p ∈ P = {2, 3, 5, 19, 5779} and x < 1.08 · 10 . In particular we consider the inequality n log p −n − < 3.54γ x log γ log p which we deduce from (20). We apply Lemma 5 to this inequality with μ = and the log γ smallest convergent p /q to μ such that q > 1.08 · 10 . For the continued fraction to μ we compute according to Lemma 5 the quantity A and obtain 1 n log p −n < − < 3.54γ x log γ (2 + A)q and therefore we obtain log 3.54(2 + A)q n < B = . log γ If we compute all the quantities for all p ∈ P we obtain new bounds for n.InTable 2 we give the relevant quantities for each prime p ∈ P. This implies that in any case n ≤ 84. Thus we compute the first 84 members of L and check whether they are a power of any of the primes p ∈ P. A quick computer search yields that the only case for which more than one solution exists is p = 2. In this case we have the three solutions L = 2, L = 4and L = 8. Thus Theorem 3 is proved. 1 2 4 Acknowledgements We want to thank the anonymous referee for his/her careful reading and valuable sug- gestions. Funding Open access funding provided by Paris Lodron University of Salzburg. 123 J. Odjoumani, V. Ziegler Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References 1. Baker, A.: A sharpening of the bounds for linear forms in logarithms. II. Acta Arith. 24, 33–36 (1973) (errata insert) 2. Baker, A.: A Concise Introduction to the Theory of Numbers. Cambridge University Press, Cambridge (1984) 2 2 2 2 3. Baker, A., Davenport, H.: The equations 3x − 2 = y and 8x − 7 = z .Q.J.Math.Oxf.Ser. 2(20), 129–137 (1969) 4. Bilu, Y., Hanrot, G., Voutier, P.M.: Existence of primitive divisors of Lucas and Lehmer numbers. J. Reine Angew. Math. 539, 75–122 (2001). With an appendix by M. Mignotte 5. Bugeaud, Y., Mignotte, M., Siksek, S.: Classical and modular approaches to exponential Diophantine equations. I. Fibonacci and Lucas perfect powers. Ann. Math. (2) 163(3), 969–1018 (2006) 6. Bugeaud, Y., Kaneko, H.: On perfect powers in linear recurrence sequences of integers. Kyushu J. Math. 73(2), 221–227 (2019) 7. Everest, G., van der Poorten, A., Shparlinski, I., Ward, T.: Recurrence Sequences. Mathematical Surveys and Monographs, vol. 104. American Mathematical Society, Providence (2003) 8. Gómez Ruiz, C.A., Luca, F.: Multiplicative independence in k-generalized Fibonacci sequences. Lith. Math. J. 56(4), 503–517 (2016) 9. Laurent, M.: Linear forms in two logarithms and interpolation determinants. II. Acta Arith. 133(4), 325– 348 (2008) 10. Matveev, E.M.: An explicit lower bound for a homogeneous rational linear form in logarithms of algebraic numbers. II. Izv. Ross. Akad. Nauk Ser. Mat. 64(6), 125–180 (2000) 11. Petho, ˝ A.: On the solution of the Diophantine equation G = p . In: EUROCAL ’85, vol. 2 (Linz, 1985), Lecture Notes in Computer Science, vol. 204. Springer, Berlin, pp. 503–512 (1985) 2t t 2 12. Shorey, T.N., Stewart, C.L.: On the Diophantine equation ax + bx y + cy = d and pure powers in recurrence sequences. Math. Scand. 52(1), 24–36 (1983) 13. Shorey, T.N., Tijdeman, R.: Exponential Diophantine equations. Cambridge Tracts in Mathematics, vol. 87. Cambridge University Press, Cambridge (1986) 14. The Sage Developers. SageMath, the Sage Mathematics Software System (Version 8.8). https://www. sagemath.org (2019) Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Journal

Annales mathématiques du QuébecSpringer Journals

Published: Oct 1, 2023

Keywords: Diophantine equations; Linear recurrence sequences; Exponential Diophantine equations; 11D45; 11B37; 11D61

There are no references for this article.