On the annihilator ideal of an inverse form

详细信息    查看全文

• 作者：Graham H. Norton
• 关键词：Annihilator ideal ; Berlekamp–Massey algorithm ; Grlex monomial order ; Gröbner basis ; Linear complexity ; Minimal polynomial ; Inverse form ; S polynomial ; Syzygy
• 刊名：Applicable Algebra in Engineering, Communication and Computing
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：28
• 期：1
• 页码：31-78
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Symbolic and Algebraic Manipulation; Computer Hardware; Theory of Computation; Artificial Intelligence (incl. Robotics);
• 出版者：Springer Berlin Heidelberg
• ISSN：1432-0622
• 卷排序：28

文摘

Let \(\mathbbm {k}\) be a field. We simplify and extend work of Althaler and Dür on finite sequences over \(\mathbbm {k}\) by regarding \(\mathbbm {k}[x^{-1},z^{-1}]\) as a \(\mathbbm {k}[x,z]\) module and studying forms in \(\mathbbm {k}[x^{-1},z^{-1}]\) from first principles. Then we apply our results to finite sequences. First we define the annihilator ideal \(\mathcal {I}_F\) of a form \(F\in \mathbbm {k}[x^{-1},z^{-1}]\) of total degree \(m\le 0\). This is a homogeneous ideal. We inductively construct an ordered pair (\(f_1\), \(f_2\)) of forms in \(\mathbbm {k}[x,z]\) which generate \(\mathcal {I}_F\) ; our generators are special in that z does not divide the leading grlex monomial of \(f_1\) but z divides \(f_2\), and the sum of their total degrees is always \(2-m\). The corresponding algorithm is \(\sim m^2/2\). We prove that the row vector obtained by accumulating intermediate forms of the construction gives a minimal grlex Gröbner basis for \(\mathcal {I}_F\) for no extra computational cost other than storage (this is based on a closed-form description of a ’form vector’ for F, an associated vector of total degrees and a syzygy triple derived from the construction. These imply that the remainder of the S polynomial of \(f_1,f_2\) is zero. Then we inductively apply Buchberger’s Criterion to show that the form vector yields a minimal Gb for \(\mathcal {I}_F\)). We apply this to determining \(\dim _\mathbbm {k}(\mathbbm {k}[x,z] /\mathcal {I}_F)\). We show that either the form vector is reduced or a monomial of \(f_1\) can be reduced by \(f_2\). This enables us to efficiently construct the unique reduced Gröbner basis for \(\mathcal {I}_F\) from the vector extension of our algorithm. Then we specialise to the inverse form of a finite sequence, obtaining generator forms for its annihilator ideal and a corresponding algorithm. We compute the intersection of two annihilator ideals using syzygies in \(\mathbbm {k}[x,z]^5\). This improves a result of Althaler and Dür. Finally we show that dehomogenisation induces a one-to-one correspondence (\(f_1\),\(f_2\)) \(\mapsto \) (minimal polynomial, auxiliary polynomial), the output of the author’s variant of the Berlekamp–Massey algorithm. So we can also solve the LFSR synthesis problem via the corresponding algorithm for sequences.