On the annihilator ideal of an inverse form (Q2397158): Difference between revisions

The paper under review extends and improves the results on finite sequences over a field obtained in [\textit{J. Althaler} and \textit{A. Dür}, Appl. Algebra Eng. Commun. Comput. 7, No. 5, 377--390 (1996; Zbl 0870.11009)]. The paper consists of three main parts. In the first part the author considers the ring of inverse polynomials \(k[x^{-1}, z^{-1}]\) over a field \(k\) as a graded \(k[x, z]\)-module, introduces the annihilator ideal \(\mathcal{I}_{F}\) of an inverse form \(F\in k[x^{-1}, z^{-1}]\) and describes some properties of this ideal. In particular, the author inductively constructs an ordered pair of forms in \(k[x, z]\) that generate \(\mathcal{I}_{F}\), gives an effective Hilbert Basis theorem for \(\mathcal{I}_{F}\) (the corresponding algorithm requires \(\sim m^{2}/2\) multiplications in \(k\)), and defines an analogue \(\lambda_{F}\) of the linear complexity of a finite sequence. The second part of the paper discusses Gröbner bases in the considered settings. Accumulating intermediate forms (if any) gives a row vector headed by an ordered pair of the above-mentioned type of length \(\lambda_{F}+1\). The author derives a syzygy for this pair and inductively applies Buchberger's Criterion to show that the form vector yields a minimal grlex Gröbner basis of \(\mathcal{I}_{F}\). It is also shown how to modify the obtained algorithm to compute a reduced Gröbner basis of \(\mathcal{I}_{F}\) and proven that the \(k\)-dimension of the cyclic \(k[x, z]\)-module \(k[x, z]/\mathcal{I}_{F}\) is \(\lambda_{F}(2-m-\lambda_{F})\). The last, third, part of the paper presents applications of the obtained results to finite sequences over \(k\). For every such a finite sequence \(s = s_{0},\dots, s_{n-1}\) with \(n\geq 1\), the author considers the corresponding inverse form \(F^{(s)} = \sum_{i=1-n}^{0}s_{-i}x^{i}z^{1-n-i}\in k[x^{-1}, z^{-1}]\) and uses properties of its annihilator ideal to obtain information about the sequence. In this part the author obtains a version of the Berlekamp-Massey algorithm and a solution of the LFSR synthesis problem via the corresponding algorithm for sequences.