# Fibonacci-like sequences in $\mathbb{F}_q$ where each element only depends on the previous one

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?
• I'm not sure there's a specific reason to stick to finite fields. If the characteristic of the field $F$ is $5$, the sequence $n\mapsto 2^n(a+bn)$ is non-trivial as soon as $a,b$ are nonzero with $b/a\notin\mathbf{F}_5$ (so exists as soon as $|F|> 5$).
– YCor
Sep 17 '20 at 8:43
• (sorry, I meant $(-2)^n(a+bn)$; $-2$ being the double root of $x^2-x-1$ in char. 5)
– YCor
Sep 17 '20 at 11:00

$$\def\ord{\mathop{\mathrm{ord}}}$$Let $$q=p^s$$ for a prime $$p$$.

Let $$\phi$$ and $$\psi$$ be the roots of $$X^2-X-1$$; they may lie either in $$\mathbb F_p$$ (when $$\left(\frac p5\right)=1$$, call this case simple) or in $$\mathbb F_{p^2}$$. The case $$\phi=\psi$$, i.e. $$p=5$$, is covered by @YCor in the comments (1 2), so let us assume $$\psi\neq \phi$$. Notice that $$\phi\psi=-1$$.

The general form of a linear recurrence is then $$a_n=a\phi^n+b\psi^n$$; where $$a,b\in\mathbb F_q$$ if $$\sqrt5\in\mathbb F_q$$, and $$a$$ and $$b$$ are two conjugate elements in $$K=\mathbb F_q[\sqrt5]$$, otherwise (here, conjugate means that they are swapped by the nontrivial automorphism of $$K$$ over $$\mathbb F_q$$). Surely, this sequence is periodic with period $$T=\ord \phi=\ord\psi$$ (where $$\ord$$ means the multiplicative order in $$\mathbb F_{p^2}$$ which does not depend on $$s$$); so we need the terms $$a_1,a_2,\dotsc,a_T$$ to be distinct, while $$a$$ and $$b$$ are nonzero.

If two such terms are equal, we have $$a\phi^n+b\psi=a\phi^{n+k}+b\psi^{n+k} \iff a\phi^n(\phi^k-1)=b\psi^n(\psi^k-1) \iff \frac ba=\phi^{2n}(-1)^n\frac{\phi^k-1}{\psi^k-1}.$$ For every prime $$p$$, the right-hand part attains finitely many values ($$\leq T^2), so, say, for $$s=6$$ there exist $$a$$ and $$b$$ which violate all equalities above and thus fit. This answers the third question.

Moreover, if the order $$T$$ of $$\phi$$ is relatively small comparative to $$p$$ (say, $$T\leq \sqrt p$$), then the required $$a$$ and $$b$$ will be found even in $$\mathbb F_p$$. But I am not sure whether this is a good condition to answer the second question.

A few more words on the fraction under consideration $$\phi^{2n}\frac{\phi^k-1}{\psi^k-1}.$$ If, say, $$\sqrt5\in\mathbb F_p$$, and we want to have no desired sequence, we want this expression to take all values in $$\mathbb F_p^*$$. If $$k$$ is even, the expression is $$-\phi^{k+2n}$$, but for odd $$k$$ it is more complicated. If, say, $$\phi$$ is a generator of $$\mathbb F_p^*$$, then the whole $$\mathbb F_p^*$$ will be covered. Again, this is a condition for question 1, but it is too strong.

• If $k$ is even, don't we have $\psi^k=(-\phi^{-1})^k = \phi^{-k}$ and $\frac{\phi^k-1}{\psi^k-1}=\frac{\phi^k-1}{\phi^{-k}-1}=\phi^k\cdot \frac{\phi^k-1}{1-\phi^k}=-\phi^k?$ Sep 17 '20 at 17:12
• @Mastrem: Oh, right! I was too fast... will try to correct now. Thanks! Sep 18 '20 at 13:24