Finite linear recurring sequences and homogeneous ideals (Q1924549)

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. It is well written and contains various examples illustrating the algorithmic part of the work.