Geodesic
Application of Gauss sums to calculate the exact values of the number of appearances of elements on cycles of linear recurrences
Prikladnaâ diskretnaâ matematika, no. 2 (2017), pp. 25-50
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: linear recurrent sequences
Mots-clés : Gauss sum. 
@article{PDM_2017_2_a2,
     author = {M. M. Glukhov and O. V. Kamlovskii},
     title = {Application of {Gauss} sums to calculate the exact values of the number of appearances of elements on cycles of linear recurrences},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {25--50},
     year = {2017},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2017_2_a2/}
}
TY  - JOUR
AU  - M. M. Glukhov
AU  - O. V. Kamlovskii
TI  - Application of Gauss sums to calculate the exact values of the number of appearances of elements on cycles of linear recurrences
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2017
SP  - 25
EP  - 50
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/PDM_2017_2_a2/
LA  - ru
ID  - PDM_2017_2_a2
ER  - 
%0 Journal Article
%A M. M. Glukhov
%A O. V. Kamlovskii
%T Application of Gauss sums to calculate the exact values of the number of appearances of elements on cycles of linear recurrences
%J Prikladnaâ diskretnaâ matematika
%D 2017
%P 25-50
%N 2
%U http://geodesic.mathdoc.fr/item/PDM_2017_2_a2/
%G ru
%F PDM_2017_2_a2
M. M. Glukhov; O. V. Kamlovskii. Application of Gauss sums to calculate the exact values of the number of appearances of elements on cycles of linear recurrences. Prikladnaâ diskretnaâ matematika, no. 2 (2017), pp. 25-50. http://geodesic.mathdoc.fr/item/PDM_2017_2_a2/

[1] Glukhov M. M., Elizarov V. P., Nechaev A. A., Algebra, v. 2, Gelios ARV Publ., Moscow, 2003, 416 pp. (in Russian)

[2] Lidl R., Niederreiter H., Finite Fields, Addison-Wesley Publ., 1983 | MR | MR | Zbl

[3] McEliece R. J., “Irreducible cyclic codes and Gauss sums”, Combinatorics, 1975, 185–202 | DOI

[4] Tsirler N., “Linear recurrence sequences”, Kiberneticheskiy Sbornik, 1963, no. 6, 55–79 (in Russian)

[5] Laksov D., “Linear recurring sequences over finite fields”, Matematika. Sbornik perevodov, 11:6 (1967), 145–158 (in Russian)

[6] Baumert L. D., McEliece R. J., “Weights of irreducible cyclic codes”, Information and Control, 20 (1972), 158–175 | DOI | MR | Zbl

[7] Nelubin A. S., “Distribution of elements on cycles of linear recurrences over Galois fields”, Formal Power Series and Algebraic Combinatorics, 12-th Intern. Conf. FPSAC, Moscow, 2000, 534–542 | DOI | MR | Zbl