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)
Full Text: