Application of Gauss sums to calculate the exact values of the number of appearances of elements on cycles of linear recurrences

M. M. Glukhov ; O. V. Kamlovskii

Prikladnaâ diskretnaâ matematika, no. 2 (2017), pp. 25-50

Résumé

Using Gauss sums, we solve the problem of obtaining the formulas for the exact values $N(z,u)$ of appearances of $z$ among the elements $u(0),u(1),\dots,u(T-1)$ of a linear recurrence sequence (LRS) $u$ generated by an irreducible polynomial of a degree $m$ over a field $P=\operatorname{GF}(q)$ in the case, when the period of $u$ is equal to $T=(q^m-1)/d$, where $d|(p^j+1)$ for some natural number $j$ and $p=\operatorname{char}P$, that is, $p$ is a semiprimitive number modulo $d$. Such a sequence $u$ is obtained from a LRS of the maximal period $q^m-1$ by regular sampling with step $d$. The results of the article generalize the formulas for $N(z,u)$ which are well-known in the case of prime $q$ or $z=0$. In fact, we give some formulas for $N(z,u)$ in the following cases: 1) $d=2$; 2) $d>2$ and $z=0$; 3) $d>2$, $z\neq0$, and $d=d_1$ or $d_1=1$, where $d_1=((q^m-1)/(q-1), d)$; 4) $d>2$, $z\neq0$, $d_1=2$, and $d/2$ is odd or $(p^{l_1}+1)/(d/2)$ is even, where $l_1$ is the least positive integer such that $(d/2)\mid(p^{l_1}+1)$. Thus, as a corollary, we have a complete solution of the problem in the situation when $d$ is a prime number.

Détail

Keywords: linear recurrent sequences
Mots-clés : Gauss sum.