The p-adic valuation of a linear recurrence

Question

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 [1], 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 [2], 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 [3] 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!

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

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

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

Answer 1

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$.

Answer 2

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

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 [1] the theorem is stated for $a$ and $b$ relatively prime. However, as explained in [2], the result holds even if $a$ and $b$ are not coprime.

[1] 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)

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