×

Linear recurring sequences over finite fields. (English) Zbl 0151.01502

The author considers the linear recurrence
\[ \sum_{j=0}^n c_ja_{i-j}=0 \qquad (i=n, n+1,\ldots;\ c_0=1,\ c_n\ne 0) \tag{*} \]
where all elements are taken from the finite field \(\mathrm{GF}(q)\). If \((a_i) = a_0, a_1, a_2, \ldots\) is periodic, the (shortest) period is denoted by \(\operatorname{per}(a_i)\). If \(f(x)\) is a polynomial and \(r\) is the least positive integer such that \(f(x)\mid x^r - 1\), \(r = \operatorname{per}f(x)\) is called the period of \(f(x)\).
In the first part of the paper the author shows how results due to M. Hall [Trans. Am. Math. Soc. 44, 196–218 (1938; Zbl 0019.19301)], M. Ward [Trans. Am. Math. Soc. 33, 153–165 (1931; Zbl 0001.13901); 33, 166–190 (1931; Zbl 0001.14001)] and N. Zierler [J. Soc. Ind. Appl. Math. 7, 31–48 (1959; Zbl 0096.33804)] can be obtained by using the following theorem of W. W. Peterson [IRE Trans. Inform. Theory 6, 459–470 (1960; Zbl 0171.17501)]:
Let \(f(x) = c_0x^n + \ldots + c_n\) with \(\operatorname{per} f(x) = r\) and \(f^*x) = (x^r - 1)1/f(x)\). Then \(r\) is the shortest common period of the solutions of (*). Moreover the solutions considered as polynomials by means of the isomorphism
\[ (a_i) = a_0, a_1, a_2, \ldots a(x) = a_0x^{r-1} + \ldots + a_{r-1} \]
constitute the ideal generated by \(\{f^*(x)\}\) in the polynomial ring modulo \(x^r - 1\).
The second part of the paper is concerned with multigrams. Given
\[ 0 \le n_1 < n_2 < \ldots < n_m < n_1 + \operatorname{per}f(x), \]
the multigram of order \(m\), corresponding to \(n_1, n_2, \ldots, n_m\) of a linear recurrence relation with characteristic polynomial \(f(x)\) of degree \(m\) is a certain family of vectors \(M_f(n_1, n_2,\ldots, n_m)\) with elements in \(\mathrm{GF}(q)\). A multigram is skew if it contains less than \(q^m\) vectors. A criterion for skewness is proved. Also a formula for the number of multigrams satisfying certain conditions is obtained.

MSC:

11B37 Recurrences
11T99 Finite fields and commutative rings (number-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI EuDML