Skip to main content

The p-adic order of a linear recurrence

Posted in
Yuri Bilu
Université Bordeaux 1/MPIM
Wed, 16/03/2022 - 14:30 - 15:30
Parent event: 
Number theory lunch seminar

Let $p$ be a prime number and $(u_n)$ a linear recurrent sequence of integers. We are interested in the the following question: what one can say about the $p$-adic order $\nu_p(u_n)$?

When $(u_n)$ is a Lucas sequence (that is, a non-degenerate linear recurrence of order $2$ starting from $0,1$), then, using arch-classical tools going back to Fermat and Euler, it is not hard to obtain a simple formula for $\nu_p(u_n)$. Say, when ${p=2}$ and ${u_n=F_n}$ is the sequence of Fibonacci numbers, we have ${\nu_2(F_n)= \nu_2(n)+2}$ if ${n\equiv 0 \bmod 12}$ and ${\nu_2(F_n)\le 3}$ otherwise. A similar result holds for all $p$ and all Lucas sequences (Sanna, 2016).

The situation turns out to be much more complicated for recurrences of higher order.
Marques and Lengyel (2014) obtained a similar "nice'' formula for the $2$-adic order of the "Tribonacci'' numbers $T_n$ (those starting from $0,0,1$ and satisfying ${T_{n+3}=T_{n+2}+T_{n+1}+T_n}$). They optimistically conjectured that a similar formula holds true for every prime $p$.

In this talk, we will see that their conjecture was indeed far too optimistic; in particular, it fails for all but seven primes below $600$. We will also get some (perhaps too vague) idea when one may expect a "nice'' formula to hold, and when not.

This work is a part of a joint project, currently in progress, with Florian Luca and the members of Joël Ouaknine's group at MPI SWS (Saarbrücken). Since it is a project in progress, some statements may look vague, and the whole thing may appear messy to the audience, so I apologize in advance.


© MPI f. Mathematik, Bonn Impressum & Datenschutz
-A A +A