Finite Linear Recurring Sequences and Homogeneous Ideals

Joachim Althaler, Arne Dür

Research output: Contribution to journalArticle

9 Citations (Scopus)

Abstract

The linear recurrence relations satisfied by finitely many sequences of finite length over a ground field are described by homogeneous ideals in the polynomial ring in two variables by using Macaulay's theory of inverse systems. The class of these ideals is shown to be precisely the class of homogeneous primary ideals the associated prime of which is the irrelevant maximal ideal. In the case of a single sequence, the classical Berlekamp-Massey algorithm for linear feedback shift register synthesis can be applied to obtain a minimal Gröbner basis of the ideal. The case of multiple sequences is reduced to the case of single sequences by ideal intersection, and the set of all linear recurrence relations of minimal order for the given sequences is generated by the low degree polynomials of the Gröbner basis.

Original languageEnglish
Pages (from-to)377-390
Number of pages14
JournalApplicable Algebra in Engineering, Communication and Computing 7
Volume7
Issue number5
DOIs
Publication statusPublished - Aug 1996

Keywords

  • Annihilator Ideal
  • Berlekamp-Massey Algorithm
  • Inverse System
  • Linear Recurrence Relation
  • Shift Register Synthesis Problem

Fingerprint

Dive into the research topics of 'Finite Linear Recurring Sequences and Homogeneous Ideals'. Together they form a unique fingerprint.

Cite this