11
$\begingroup$

Consider a prime $p$ and a sequence $(a_n)_{n\ge 0}$ in $\mathbb{F}_p$ satisfying $a_{n+2}=a_{n+1}+a_n$ for all $n\ge 0$.

Now, assume that each element of the sequence only really depends on the previous one. That is, assume there exists a function $f:\mathbb{F}_p\to\mathbb{F}_p$ such that $a_{n+1}=f(a_n)$ for all $n\ge 0$.

If $p\not\in\{2,5\}$ and $5$ is a quadratic residue mod $p$ there are the obvious sequences $$\left(c\left[\frac12+\frac12\sqrt5\right]^n\right)_{n\ge 0}\quad\text{and}\quad\left(c\left[\frac12-\frac12\sqrt5\right]^n\right)_{n\ge 0}$$ for $c\in\mathbb{F}_p$ any constant, but are there any others?

Computational results by @Servaes

Let's call two Fibonacci-like sequences modulo $p$ equivalent if they can be turned into each other through shifting and multiplication by units, then any sequence where each element is a function of the previous and and which is not equivalent to $$(0)_{n\ge 0},\quad (c^n)_{n\ge 0}$$ where $c^2=c+1$, is called strange.

@Servaes has shown through computation that the first few primes for which strange sequences exist are $$199, 211, 233, 281, 421, 461, 521, 557, 859, 911.$$

Own work

For any prime $p$ let $\pi(p)$ be the Pisano period mod $p$ (so this is not the prime counting function)

Claim: Let $p$ be a prime, $(a_n)_{n\ge 0}$ a strange sequence. Then it has period $\pi(p)$.

Proof: Let $A=\{a_n:n\ge 0\}$ be the set of attained values and $f:A\to A$ the function which makes this sequence strange, in the sense that $a_{n+1}=f(a_n)$ for all $n\ge 0$. Clearly, $f$ is a bijection.

It is easily proved that, for all $a\in A$ and $n\in\mathbb{Z}$, $$f^n(a)=F_{n-1}a+F_nf(a).$$ Let $m$ be the period of $(a_n)_{n\ge 0}$, then clearly $m$ is the smallest positive integer $n$ for which $f^n=\operatorname{id}_A$. Thus, for all $a\in A$, $$(1-F_{m-1})a=F_mf(a)$$ If $F_m\neq 0$ it follows that $f(a)=F_m^{-1}(1-F_{m-1})a$ and the sequence is equivalent to $\left(c^n\right)_{n\ge 0}$ where $c=F_m^{-1}(1-F_{m-1})$ satisfies $c^2=c+1$. This contradicts our assumption that the sequence is strange, so $F_m=0$.

Since the sequence is not the null sequence, we may take $a\in A$ non-zero and conclude that $F_{m-1}=1$. It follows that $\pi(p)\mid m$. Since $$f^{\pi(p)}(a)=F_{\pi(p)-1}a+F_{\pi(p)}f(a)=F_{-1}a+F_0F(a)=a,$$ the opposite division relation holds as well and we are done.

EDIT: I asked a slightly more general version of this question on Mathoverflow and linked to this question, but forgot to link the Mathoverflow question here.

$\endgroup$
  • 1
    $\begingroup$ For $p=5$ the sequence $(2,1,3,4,2,1,\ldots)$ works. And of course the zero sequence works for any $p$. There are no other sequences (up to shifting) for $p\leq5$. $\endgroup$ – Servaes Sep 15 at 22:33
  • 1
    $\begingroup$ Also, except the zero sequence, no sequence can contain a $0$. Nor can it have $a_{n+1}=a_n$ for any $n$. Moreover, if $(a_n)_{n\geq0}$ is such a sequence the so is $(ca_n)_{n\geq0}$ for any constant $c$. So without loss of generality $a_0=1$. This leaves $p-2$ initial values for $a_1$, for each $p$. $\endgroup$ – Servaes Sep 15 at 22:40
  • 2
    $\begingroup$ Some simple python code shows that the first primes for which there are not either $0$ or $2$ such sequences, up to multiplication by constants and shifting, are: $$5,\ 199,\ 211,\ 233,\ 281,\ 421,\ 461,\ 521,\ 557,\ 859,\ 911.$$ $\endgroup$ – Servaes Sep 15 at 23:09
  • 1
    $\begingroup$ I'm still cleaning up the proof, but I believe that the period of any sequence not of the 'standard' types must be the Pisano period mod p. $\endgroup$ – Mastrem Sep 15 at 23:25
  • 3
    $\begingroup$ Quite surprisingly, it seems that the number of values for $a_1$ that yields such a sequence is either $1+\left(\tfrac{5}{p}\right)$, except for the primes I just listed, in which case the number of values for $a_1$ is huge! $\endgroup$ – Servaes Sep 15 at 23:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.