# The p-adic valuation of a linear recurrence

Let $(u_n)_{n \geq 0}$ be an integer-valued linear recurrence of order $k \geq 1$. Precisely, $$u_n = a_1 u_{n-1} + \cdots + a_k u_{n - k} \quad \forall n \geq k ,$$ for some $a_1, \ldots, a_k \in \mathbb{Z}$.

Given a prime number $p$, I wonder: How much is known about the $p$-adic valuation $\upsilon_p(u_n)$? Are there some "explicit" formulas?

$\bullet$ For $k=1$, we have simply a geometric progression and clearly it holds $$\upsilon_p(u_n) = \upsilon_p(a_1)^n + \upsilon_p(u_0).$$

$\bullet$ For $k=2$, the problem was studied (in the more general setting of linear recurrences in the field of $p$-adic numbers) by Ward , who gave formulas for $\upsilon_p(u_n)$. However, those formulas rely on the computation of a $p$-adic number $v$ (see Theorem 10.1) which is essential as much as difficult as the computation of $\upsilon_p(u_n)$, so they do not seem to give really useful information on $\upsilon_p(u_n)$ (see Vesselin Dimitrov comments).

The particular case of the Fibonacci sequence $(F_n)_{n \geq 0}$ was also studied by Lengyel , who gave practical closed expressions for $\upsilon_p(F_n)$, in terms of $\upsilon_p(n)$, $z(p) := \min\{n > 0 : p \mid F_n\}$, and $e(p) := \upsilon_p(F_{z(p)})$.

$\bullet$ For $k\geq 3$ it seems to me that nothing general is known. I found only another article of Lengyel  about the $2$-adic valuation of the Tribonacci numbers $(T_n)_{n \geq 0}$.

Surely, without loss of generality, it can be assumed that: $(u_n)_{n \geq 0}$ is not degenerate; it has at least one zero modulo $p$ (and that can be effectively checked since $(u_n)_{n \geq 0}$ is periodic modulo $p$ and the period length is less than $p^k$); $u_0 \equiv 0 \bmod p$, eventually by shifting $(u_n)_{n \geq 0}$.

Thank you in advance for possible ideas and references!

 M. Ward. The linear p-adic recurrence of order two. Illinois J. Math. (6) 40--52, 1962.

 T. Lengyel. The order of the Fibonacci and Lucas numbers. The Fibonacci Quarterly, (33) 234--239, 1995.

 T. Lengyel. The 2-adic Order of the Tribonacci Numbers and the Equation $T_n = m!$. Journal of Integer Sequences Vol. 17, 2014.

• Surely this is susceptible to rewriting as $M^n u$ where $M$ is the companion matrix for $\lambda^k - \sum a_i \lambda^{k-i}$, and $u$ is any old start-up vector. The characteristic polynomial determines (modulo the start-up) the valuations (this takes some care), but can be done. Aug 15 '15 at 22:35
• "Lifting the exponent" is also a result of this flavor (for $k=2$): s3.amazonaws.com/aops-cdn.artofproblemsolving.com/resources/… Aug 15 '15 at 22:53
• I do not think that Ward's paper treats a general two-term recurrence. For example, there is no formula for the $3$-adic valuation of $5^n-2$. Proving that $3^n \nmid 5^n-2$ for all $n > 1$ was once a well known problem whose solution required the $3$-adic variant of Gelfond's estimates on linear forms in two logarithms. Aug 16 '15 at 7:14
• In general, diophantine approximations (Schmidt's theorem) yield a good, but ineffective upper bound on the $p$-adic valuation of $u_n$. Aug 16 '15 at 7:15
• This is correct. With the normalization $5 \cdot 5^n - 2 \cdot 1^n$, the example I gave falls into Theorem 10.1 in Ward. But this is just a reformulation of the essential problem, in terms of how well can the $3$-adic integer $\nu$ in that theorem be $3$-adically approximated by a rational integer $n$. This is a quintessential problem in diophantine approximations, solved by the Gelfond-Baker results of logarithmic linear forms. Aug 16 '15 at 9:48

Actually, the binary linear recurrence case is pretty precise, especially if $p\ge3$ and you're working over $\mathbb Q$, and not over a field where $p$ is ramified. Let $r(p)$ denote the rank of apparition, which is the smallest $r$ such that $p\mid a_r$. Then if $p\ge3$, we have $$\text{ord}_p(a_n) = \begin{cases} 0 &\text{if r(p)\nmid n,} \\ \text{ord}_p(a_{r(p)}) + \text{ord}_p(n/r(p)) &\text{if r(p)\mid n.} \\ \end{cases}$$ In the literature there are sources which state this as a theorem for all primes in all number fields, but it's not quite right for $p=2$ over $\mathbb Q$, nor for larger $p$ if $p$ is ramified. The best source that I know for the general result is:

Stange, Katherine E., Integral points on elliptic curves and explicit valuations of division polynomials. Canad. J. Math. 68 (2016), no. 5, 1120-1158. (MR3536930) http://arxiv.org/abs/1108.3051

The case of $p\ge3$ over $\mathbb Q$ is a fairly easy exercise once one understands that underlying these binary linear recurrences (and also underlying elliptic divisibility sequences) is a one-dimensional algebraic group, and the desired result follows from a calculation in the formal group.

On the other hand, it is a very hard (pretty much open) problem to determine if there are infinitely many $n$ such that $\text{ord}_p(a_{r(p)})\ge2$, or even that there are infinitely many $n$ such that $\text{ord}_p(a_{r(p)})=1$, although presumably the latter occurs for almost all $n$. Both problems are open even for $a_n=2^n-1$.

• Are you considering an arbitrary binary linear recurrence? This applies to $a_n = q^n - 1$, and if I understand correctly, a similar result holds for elliptic divisibility sequences. But take $p = 3$ and $a_n = 5^n - 2$. The rank of apparition is $n = 1$, with corresponding valuation $1$, but the $3$-adic valuation of $a_n$ is zero for all even $n$. Moreover, for $n = 5$ we have $3^2 \mid 5^5 - 2 = a_5$, and then for $n = 11$ we have $3^3 \mid 5^{11} - 2 = a_{11}$. So, in this example, the $3$-adic valuation is rather subtle; indeed it depends on the rational approximations to a $3$-adic log. Nov 1 '15 at 22:27
• @Joe Silverman: I am confused by your last paragraph because the (in)equalities have no dependency on $n$. Is it about an infinite number of primes $p$? Sep 16 '16 at 19:02
• @LucGuyot Yes, sorry, in both cases "infinitely many $n$" should be "infinitely many $p$", and ditto "almost all $n$" should be "almost all $p$". Sep 16 '16 at 19:39

Regarding $p$-adic valuation of Lucas sequences, a quite precise result is given in .

Theorem. Let $(u_n)_{n \geq 0}$ be a nondegenerate Lucas sequence with $u_0 = 0$, $u_1 = 1$, and $u_{n+2} = a u_{n+1} + b u_n$ for all $n \geq 0$, where $a$ and $b$ are two integers. Furthermore, let $p$ be a prime number not dividing $b$.

Then for any positive integer $n$ we have $$v_p(u_n) = \begin{cases} v_p(n) + v_p(u_p) - 1 & \text{ if } p \mid \Delta ,\; p \mid n, \\ 0 & \text{ if } p \mid \Delta ,\; p \nmid n, \\ v_p(n) + v_p(u_{p\tau(p)}) - 1 & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n ,\; p \mid n, \\ v_p(u_{\tau(p)}) & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n ,\; p \nmid n, \\ 0 & \text{ if } p \nmid \Delta ,\; \tau(p) \nmid n , \end{cases}$$ where $\Delta := a^2 + 4b$ and $\tau(p)$ is the rank of apparition of $p$ in $(u_n)_{n \geq 0}$, i.e., the least positive integer $m$ such that $p \mid u_m$. Moreover, if $p \geq 3$ then $$v_p(u_n) = \begin{cases} v_p(n) + v_p(u_p) - 1 & \text{ if } p \mid \Delta ,\; p \mid n, \\ 0 & \text{ if } p \mid \Delta ,\; p \nmid n, \\ v_p(n) + v_p(u_{\tau(p)}) & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n , \\ 0 & \text{ if } p \nmid \Delta ,\; \tau(p) \nmid n , \end{cases}$$ while if $p \geq 5$ then $$v_p(u_n) = \begin{cases} v_p(n) & \text{ if } p \mid \Delta , \\ v_p(n) + v_p(u_{\tau(p)}) & \text{ if } p \nmid \Delta ,\; \tau(p) \mid n , \\ 0 & \text{ if } p \nmid \Delta ,\; \tau(p) \nmid n . \end{cases}$$ Actually, in  the theorem is stated for $a$ and $b$ relatively prime. However, as explained in , the result holds even if $a$ and $b$ are not coprime.

 C. Sanna, The $p$-Adic Valuation of Lucas Sequences, Fibonacci Quart. 54 (2016), no. 2, 118–124. (Free preprint: https://www.researchgate.net/publication/304251918_The_p-adic_valuation_of_Lucas_sequences)

 N. Murru, C. Sanna, On the k-regularity of the k-adic valuation of Lucas sequences http://arxiv.org/abs/1603.09310