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.

  • 2
    $\begingroup$ 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. $\endgroup$ – David Handelman Aug 15 '15 at 22:35
  • $\begingroup$ "Lifting the exponent" is also a result of this flavor (for $k=2$): s3.amazonaws.com/aops-cdn.artofproblemsolving.com/resources/… $\endgroup$ – Max Alekseyev Aug 15 '15 at 22:53
  • 2
    $\begingroup$ 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. $\endgroup$ – Vesselin Dimitrov Aug 16 '15 at 7:14
  • $\begingroup$ In general, diophantine approximations (Schmidt's theorem) yield a good, but ineffective upper bound on the $p$-adic valuation of $u_n$. $\endgroup$ – Vesselin Dimitrov Aug 16 '15 at 7:15
  • 1
    $\begingroup$ 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. $\endgroup$ – Vesselin Dimitrov 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$.

  • 3
    $\begingroup$ 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. $\endgroup$ – Vesselin Dimitrov Nov 1 '15 at 22:27
  • $\begingroup$ @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$? $\endgroup$ – Luc Guyot Sep 16 '16 at 19:02
  • 1
    $\begingroup$ @LucGuyot Yes, sorry, in both cases "infinitely many $n$" should be "infinitely many $p$", and ditto "almost all $n$" should be "almost all $p$". $\endgroup$ – Joe Silverman Sep 16 '16 at 19:39

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


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.