Back to Search
Start Over
On the Annihilator Ideal of an Inverse Form
- Source :
- J. AAECC (2017) 28: 31-78
- Publication Year :
- 2017
-
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\in 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 $\sim |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 $\dim_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$) $\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.<br />Comment: We have improved the proof of the main construction, made minor improvements to the presentation and corrected some typos. We have also moved Subsection 4.5 on the maximal regular sequence to ArXiv 1805.03995
- Subjects :
- Computer Science - Symbolic Computation
I.1
Subjects
Details
- Database :
- arXiv
- Journal :
- J. AAECC (2017) 28: 31-78
- Publication Type :
- Report
- Accession number :
- edsarx.1710.07731
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1007/s00200-016-0295-6