On the annihilator ideal of an inverse form

Abstract: Let

K

be a field. We simplify and extend work of Althaler & D"ur on finite sequences over

K

by regarding

K [x^{- 1}, z^{- 1}]

as a

K [x, z]

module, and studying forms in

K [x^{- 1}, z^{- 1}]

from first principles. Then we apply our results to finite sequences. First we define the annihilator ideal

I_{F}

of a non-zero form

F i n K [x^{- 1}, z^{- 1}]

, a homogeneous ideal. We inductively construct an ordered pair (

f_{1}

,,,

f_{2}

) of forms which generate

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 - | F |

, where

| F |

is the total degree of

F

. We show that

f_{1}, f_{2}

is a maximal regular sequence for

I_{F}

, so that the height of

I_{F}

is 2. The corresponding algorithm is

s i m | F |^{2} / 2

. The row vector obtained by accumulating intermediate forms of the construction gives a minimal grlex Gr"obner basis for

I_{F}

for no extra computational cost other than storage and apply this to determining

d i m_{K} (K [x, z] / 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"obner basis for

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 which does not use the last 'length change' of Massey. We compute the intersection of two annihilator ideals using syzygies in

K [x, z]^{5}

. This improves a result of Althaler & D"ur. Finally, dehomogenisation induces a one-to-one correspondence (

f_{1}

,,

f_{2}

)

m a p s t o

(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.

Review text

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.

Recommendations

Cites work

Cited in

(8)

Describes a project that uses

Uses Software

CoCoA

This page was built for publication: On the annihilator ideal of an inverse form

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397158)