Orbits of Second Order Linear Recurrences over Finite Fields

Abstract

Let $Q$ be the matrix $\left(\begin{array}{cc}a& b\\ 1& 0\end{array}\right)$ in $G{L}_2({\mathbb{F}}_q)$ where ${\mathbb{F}}_q$ is a finite field, and let $G$ be the finite cyclic group generated by $Q$. We consider the action of $G$ on the set ${\mathbb{F}}_q\times {\mathbb{F}}_q$. In particular, we study certain relationships between the lengths of the non-trivial orbits of $G$, and their frequency of occurrence. This is done in part by investigating the order of elements of a product in an abelian group when the product has prime power order. For $q$ a prime and $b=1$, the orbits correspond to Fibonacci type linear recurrences modulo $q$ for different initial conditions. We also derive certain conditions under which the roots of the characteristic polynomial of $Q$ are generators of ${\mathbb{F}}_q^{\times }$. Examples are included to illustrate the theory.

23 pages