Finite linear recurring sequences and homogeneous ideals
type: Item
instance of: scholarly article
title: Finite linear recurring sequences and homogeneous ideals
zbMATH Open document ID: 0870.11009
author: Arne Dür
author: Joachim Althaler
published in: Applicable Algebra in Engineering, Communication and Computing
publication date: 1997-07-29T00:00:00Z
review text: Let \(K\) be a finite field and \(s\) a finite sequence over \(K\). A linear recurrence relation of order \(L\) for \(s\) is a finite sequence \(a\) over \(K\) of length \(L\) such that \[ s_{j+L}= \sum_{i=0}^{L-1} a_is_{i+j} \text{for} j=0,1,...,n-1-L, \] \noindent where \(n\) is the length of \(s\) (\(a\) is satisfied by \(s\)). Given a set \(\Sigma\) of finite sequences over \(K\), the synthesis problem is to find a linear recurrence relation \(a\) of least order such that \(a\) is satisfied by \(s\) for all \(s\) in \(\Sigma\). In section 2 and section 3 the authors study the space of linear recurrence relations satisfied by a set \(\Sigma\) of finite sequences by a homogeneous ideal in the polynomial ring in two variables over \(K\) (the annihilator ideal Ann\((\Sigma)\)). They prove that the class of Ann\((\Sigma)\) for nontrivial finite \(\Sigma\) coincides with the class of homogeneous primary ideals \(I\) in \(K[x,y]\) whose associated prime is the irrelevant maximal ideal. Furthermore, given \(I\), using Gröbner basis techniques, an explicit formula for the minimal cardinality of a finite \(\Sigma\) such that Ann\((\Sigma)=I\) is derived. In section 4 it is shown how the Berlekamp-Massey algorithm, a tool which solves the synthesis problem for a single finite sequence \(s\), can be used to compute a minimal Gröbner basis (with respect to graded-lexicographic order with \(X > Y\)) of Ann\((s)\). A sufficient condition for this basis to be reduced is given. Moreover, for an arbitrary finite set \(\Sigma\) one can determine Ann\((s)\) for each \(s \in \Sigma\) with the above algorithm and Ann\((\Sigma)\) can be obtained by using Gröbner basis methods for the intersection of ideals. The latter is made precise in theorem 4, which constitutes an explicit description of the solution set of the synthesis problem in terms of characteristic polynomials corresponding to linear recurrence relations. The paper is an important contribution to Algebraic Systems Theory. I…
reviewed by: Dirk Hachenberger
Mathematics Subject Classification ID: 11B37
Mathematics Subject Classification ID: 13P10
Mathematics Subject Classification ID: 94A55
zbMATH DE Number: 936996
zbMATH Keywords: linear recurrence relation
zbMATH Keywords: finite sequence
zbMATH Keywords: synthesis problem
zbMATH Keywords: annihilator ideal
zbMATH Keywords: homogeneous primary ideals
zbMATH Keywords: minimal cardinality
zbMATH Keywords: Berlekamp-Massey-algorithm
zbMATH Keywords: minimal Gröbner basis
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 936996