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\}$


  • 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?
  • 1
    $\begingroup$ 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$). $\endgroup$ – YCor Sep 17 '20 at 8:43
  • 1
    $\begingroup$ (sorry, I meant $(-2)^n(a+bn)$; $-2$ being the double root of $x^2-x-1$ in char. 5) $\endgroup$ – 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<p^4$), 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.

  • $\begingroup$ 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?$ $\endgroup$ – Mastrem Sep 17 '20 at 17:12
  • $\begingroup$ @Mastrem: Oh, right! I was too fast... will try to correct now. Thanks! $\endgroup$ – Ilya Bogdanov Sep 18 '20 at 13:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.