The Berlekamp-Massey algorithm and linear recurring sequences over a factorial domain (Q1894579)

The existence and effective computation of the minimal polynomial of a linear recurring sequence (lrs) with terms from a domain \(r\) is considered. Particular attention is given to the case when \(R=U\) is a factorial (unique factorization) domain. When \(U=K\), a field, the theory is well known and the Berlekamp-Massey (BM) algorithm computes the minimal polynomial. A more general approach is taken here to obtain information about lrs in domains such as \(\mathbb{Z}\) and \(K[X_1, X_2, \ldots, X_n ]\). The work is motivated by the desire to extend the theory of one variable codes and their decoding algorithms, such as BM and those based on the extended Euclidean algorithm (XE) to a multivariable theory. A generalization to XE and the polynomial remainder sequence (PRS) to \(R[X]\) is given. The extended algorithm (XRS) has certain invariance properties, similar to those of XE. XPRS is modified to an algorithm, BM/R, analogous to BM is given in section 3. Section 4 considers \(\text{lrs}(\alpha)= \alpha_0, \alpha_1, \ldots\) where \(\alpha_i\in U\). It is shown that the ideal of the characteristic polynomial of \((\alpha)\) is a principal ideal having a primitive polynomial generator. The factorial domains \(U\) for which the theory gives the strongest results are those for which \(U[[X]]\) are also factorial, called potential domains. This class includes all principal ideal domains and \(K[X_1, \ldots, X_n ]\). The final section contains algorithms for computing the characteristic polynomials of lrs's.