Given a prime power $q$, consider all sequences $(a_n)_{n\in\mathbb{Z}}$ in $\mathbb{F}_q$ for which $a_{n+1}=a_n+a_{n-1}$ for all $n\in\mathbb{Z}$. Call such a sequence simple if there exists a function $f:\mathbb{F}_q\to\mathbb{F}_q$ such that $a_{n+1}=f(a_n)$ for all $n\in\mathbb{Z}$.
There are some trivial simple sequences. The null sequence is simple, as is $(cr^n)_{n\in\mathbb{Z}}$ for $c\in\mathbb{F}_q^*$ and $r$ a root of $X^2-X-1$. My questions are about nontrivial simple sequences.
I've asked a more specific version of this question on Math.Stackexchange. There, computations by the user @Servaes show that nontrivial simple sequences exist in $\mathbb{F}_p$ for $p\in\{199,211,233,281,421,461,521,557,859,911\}$
Questions:
- Are there 'easy' conditions on primes $p$ such that no nontrivial simple sequences exist in $\mathbb{F}_p$ when $p$ satisfies these conditions? (and there are a large number of primes satisfying these conditions)
- Are there infinitely many primes $p$ such that nontrivial simple sequences exist in $\mathbb{F}_p$?
- Given a prime $p$, does there always exist a positive integer $n$ such that nontrivial simple sequences exist in $\mathbb{F}_{p^n}$?
- In case the answer to the previous question is affirmative, let $n(p)$ be the smallest such positive integer. Is $n(p)$ bounded? If not, do there exist integers $m$ such that $n(p)=m$ for infinitely many primes?