Diophantine problems related to recurrence sequences

Szabolcs Tengely
Number Theory and its Applications
An International Conference
Dedicated toKálmán Győry, Attila Pethő,János Pintz, András Sárközy

October 5, 2010

Research problem
 x
Fn =,5where Fn is the Fibonacci sequence: 0, 1, 1, 2, 3, 5, . . .
Research supported by OTKA PD75264 andJános Bolyai Research Scholarshipof the Hungarian Academy of Sciences
I would like to thank Prof. Michael Stoll for organising the workshop
on ”Rational Points 3” and for the discussions related to the present
topic during the workshop on the arithmetic of genus 2 curves andMordell-Weil sieve.
2 of 15

Some related resultsKálmán Győry: On the Diophantine equations
Mat. Lapok 14 (1963) 322-329.

n2= al andn3= al ,

It was proved that for n > 2 and l > 1 the equation n= a2l
2
has no solution. Also some results on the unsolvability of the equation n= ap3
were discussed, where p is an odd prime.

3 of 15

Kálmán Győry: On the Diophantine equation
Acta Arith. 80 (1997) 289-295.
nknk

= xl,In 1951, Erdős proved that the equation= x l has no integral
solution with x > 1, l > 1, k ≥ 4 and n ≥ 2k.
Kálmán Győry resolved the remaining cases with k = 2, 3. He showedthat the only solution is (where (k, l) 6= (2, 2))
 
50= 1402 .
34 of 15

Attila Pethő: The Pell sequence contains only trivial perfect powers,Sets, graphs and numbers (Budapest, 1991), 561568.
Colloq. Math. Soc. János Bolyai, 60, North-Holland, Amsterdam,
1992.
By extending a result of Ljunggren, Attila Pethő proved that the only
nontrivial solution of the equation
Rn = x q
in integers n, x, q with |x| > 1 and q ≥ 2 is(n, x, q) = (7, 13, 2).
Here Rn is defined by R0 = 0, R1 = 1 and Rn+2 = 2Rn+1 + Rn forn ≥ 0.
5 of 15

Clemens Fuchs, Attila Pethő and Robert Tichy: On the Diophantine
equation Gn (x) = Gm (P(x)) : higher-order recurrences,
Trans. Amer. Math. Soc. 355 (2003) 4657-4681.

(Gn (x))∞n=0degree d linear recurring sequence defined by

Gn+d (x) = Ad−1 (x)Gn+d−1 (x) + . . . + A0 (x)Gn (x),for n ≥ 0.

General finiteness conditions depending only on G0 , . . . , Gd−1 ∈ K[x],on P ∈ K[x] and on A0 , . . . , Ad−1 ∈ K[x] related to the equation
Gn (x) = Gm (P(x)).

6 of 15

Enrico Bombieri, Andrew Granville and János Pintz: Squares inarithmetic progressions
Duke Math. J. 66 (1992) 369-385.
Q(N; q, a) : number of squares in the arithmetic progression
qn + a (n = 1, 2, . . . , N)
Q(N) = max Q(N; q, a).
a,q≥1

It was conjectured by Erdős and proved by Szemerédi, that
Q(N) = o(N).
Enrico Bombieri, Andrew Granville and János Pintz proved that
Q(N) = O(N 2/3 (log N)A ).

7 of 15

András Sárközy: On multiplicative arithmetic functions satisfying alinear recursion
Studia Sci. Math. Hungar. 13 (1978) 79104.
Multiplicative arithmetic function: f (mn) = f (m)f (n), gcd(m, n) = 1.
Determine all multiplicative arithmetic function which satisfy a linear
recursion of finite order:
a0 f (n) + a1 f (n + 1) + . . . + ak f (n + k) = 0,n = 1, 2, . . .

András Sárközy showed that f (n)/nh is periodic for some integerh ≥ 0.
Moreover if f (n) 6≡ 0 and f (n) = o(n), then f (n) is a character
modulo m.

8 of 15

Un = AUn−1 + BUn−2 : binary recurrence sequence.
Determine n, x such that
Un = P(x),where P is a polynomial.
Many results are in the literature, finiteness results, completeresolution in special cases(Alfred, Bilu, Bugeaud, Cohn, Fuchs, Győry, Hajdu, Kovács, Luca,McDaniel, Mignotte, Ming, Nemes, Pethő, Pintér, Rakaczki, Schinzel,Shorey, Siksek, Stewart, Szalay, Tichy, Tijdeman)

9 of 15

2007, workshop in Leiden, Evertse and Tijdeman composed a list ofopen problems posed by the participants. Florian Luca posed thefollowing problem:
mshow that the equation Fn = k has only finitely many integersolutions (n, m, k) with 2 ≤ k ≤ m/2.
Let k = 5.
 xFn =,5where Fn is the Fibonacci sequence: 0, 1, 1, 2, 3, 5, . . .
By using the identity L2n − 5Fn2 = 4(−1)n we get
C +,− :

10 of 15y 2 = x 2 (x + 15)2 (x + 20) ± 36000000.

Following the paper by Bugeaud, Mignotte, Siksek, Stoll and Tengely:
upper bound for the integral solutions by Baker’s method (Matveev’sbound)lower bound for the integral solutions by Mordell-Weil sieve(implemented by Bruin and Stoll).
C− :y 2 = x 2 (x + 15)2 (x + 20) − 36000000 = f (x).

Using MAGMA procedures based on Stoll’s papers we obtain thatrankJ(Q) = 2 and(25, 3000) − ∞ √√−5 −15−75, −1500 −15 + 1500 +D2 =2 √
√
5 −15−75, 1500 −15 + 1500 − 2∞
2D1 =are generators of the Mordell-Weil group.
11 of 15

Representatives of J(Q)/2J(Q) are 0, D1 , D2 , D1 + D2 ,f (α) = 0.
We havex − α = κ
By Baker’s theory we have the following bounds:repr.
κbound for log x019.28 × 10279
D125 − α4.53 × 10599
D21500 + 75α + α2 eliminated in Q2
D1 + D2 3900 − 81α + α2 eliminated in Q3
By Mordell-Weil sieve we obtain that(C (Q)) ⊆ W + BJ(Q)
where W is the image of the known points {(25, ±3000), ∞} andB = 22 · 52 · 7 · 11 · 13 · 17 · 29.
12 of 15

To obtain B we used the Mordell-Weil sieve with the following primes:
27 , 52 , 7, 11, 13, 17, 29, 47, 73,101, 139, 151, 163, 179, 211, 257, 347,509, 523, 617, 631, 769, 829, 877, 971,1327, 1567, 1667, 1747, 1877, 2099, 2273,2287, 2347, 2521, 2591, 2707, 2953, 3067,3119, 3229, 3259, 4441, 4651, 4663, 5387,6277, 6991, 9859, 10781, 10847, 11447, 12071,14653, 14831, 15973, 17359, 19207.

13 of 15

φ : Z2 → J(Q)φ(a1 , a2 ) = a1 D1 + a2 D2 ,and (C (Q)) ⊆ W + φ(BZ2 ).
BZ2 = L0 ! L1 ! L2 . . . ! Lk
such that (C (Q)) ⊆ W + φ(Lj ).
Lower bound obtained this way: 0.69 × 10617 .

14 of 15

Hanna Tengely
2nd October 2010
3.15 kg, 51 cm

15 of 15