文摘
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.
