Linear Recurring Sequences over Finite Fields.
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 \textit{M. Hall} [Trans. Am. Math. Soc. 44, 196--218 (1938; Zbl 0019.19301)], \textit{M. Ward} [Trans. Am. Math. Soc. 33, 153--165 (1931; Zbl 0001.13901); 33, 166--190 (1931; Zbl 0001.14001)] and \textit{N. Zierler} [J. Soc. Ind. Appl. Math. 7, 31--48 (1959; Zbl 0096.33804)] can be obtained by using the following theorem of \textit{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.
- On interleaved sequences over finite fields
- Linear recurring sequences over modules
- Linear recurring sequences over rings and modules
- Linear recurrences over a finite field with exactly two periods
- Some basic results on finite linear recurring sequence subgroups
- Results on multiples of primitive polynomials and their products over GF(2)
- Non-standard linear recurring sequence subgroups in finite fields and automorphisms of cyclic codes. I
- Matrices and linear recurrences in finite fields
- scientific article; zbMATH DE number 25929 (Why is no real title available?)
- Linear recurrence sequences over commutative rings
- Values of linear recurring sequences of vectors over finite fields
- On the frequency distribution of multigrams in linear recurrent sequences over a residue-class ring
- scientific article; zbMATH DE number 746091 (Why is no real title available?)
- On conditionally defined Fibonacci and Lucas sequences and periodicity
- Linear recurrence sequences without zeros
- Semiconjugate factorizations of higher order linear difference equations in rings
- Linear cellular automata and recurring sequences in finite fields
This page was built for publication: Linear Recurring Sequences over Finite Fields.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5529496)
