Linear recurring sequences over rings and modules (Q1915326): Difference between revisions

The monograph under review deals with the algebraic theory of linear recurring sequences over rings and modules. This general approach makes it possible to give a foundation for the theory of multidimensional linear recurrences and to study their properties. By applying the powerful framework of commutative algebra many classical results about one-dimensional recurrences are generalized to the multidimensional case. On the other hand commutative algebra makes a benefit to the new theory, too. Interesting consequences of the theory of recurrences in ring theory are shown, in particular, in the theory of quasi Frobenius modules and in Hopf algebras. The authors pay special attention to periodic sequences and to properties of linear recurring sequences over finite fields. Applications to coding theory are studied, too. The monograph is divided into six chapters and more or less independently into 31 sections. Chapter 1, ``General properties of linear recurring sequences over modules'', introduces basic definitions of one- and multidimensional recurrence sequences; of periodic sequences, ideals and polynomials; of cycle type of linear recurrence sequences; of decimation of sequences. Central roles are played by the concepts of linear recurrence sequence families, annihilator ideals and systems of generators of linear recurrence sequences and families of linear recurrence sequences. In section 4 it is pointed out that it is possible to construct a quasi Frobenius module over any Artinian commutative ring over a linear recurrence sequence family of some principal ideal ring. The main object of Chapter 2, ``Linear recurring sequences over finite fields'', is to find generating systems of annihilator ideals of linear recurrence sequence families. The Berlekamp-Massey algorithm and Hopf algebras play a central role here. In Chapter 3, ``Linear recurring sequences over Artinian and finite rings'', the classical method of localization is used to characterize canonical generator systems of monic ideals and families of linear recurrence sequences over principal ideal rings. These are the analogs of Groebner bases of polynomial ideals over a field and are used to describe the cycle types of finite reversible linear recurrence sequence families. Chapter 4, ``Representation of linear recurrence sequences'', deals with the properties of coordinate sequences. Here the authors examine only one-dimensional recurrence and the basic ring is a finite field or \(\mathbb{Z}_{p^n}\). Sharp estimates are found for sequences which have maximal period length. The distribution of elements within a period is important in applications, especially in the construction of random number generators. Such questions are discussed in Chapter 5, ``Statistical properties of linear recurring sequences''. Finally, in Chapter 6, ``Some applications in coding theory'', the possibility of application of linear recurring sequences in the construction of algebraic codes with good parameters, for example Kerdock codes, are studied. The bibliography includes 174 items, containing many references to less known Russian books and papers. Most of the relevant literature is cited; the only one which the referee found to be missing is the book of \textit{W. Narkiewicz}, Uniform distribution of sequences of integers in residue classes [Lect. Notes 1087 (1984; Zbl 0541.10001)] which contains the first systematic study of the topics of Chapter 5.