Standard bases concordant with the norm and computations in ideals and polylinear recurring sequences

E. V. Gorbatov

Fundamentalʹnaâ i prikladnaâ matematika, Tome 10 (2004) no. 3, pp. 23-71

Résumé

Standard bases of ideals of the polynomial ring $R[X]=R[x_1,\dots,x_k]$ over a commutative Artinian chain ring $R$ that are concordant with the norm on $R$ have been investigated by D. A. Mikhailov, A. A. Nechaev, and the author. In this paper we continue this investigation. We introduce a new order on terms and a new reduction algorithm, using the coordinate decomposition of elements from $R$. We prove that any ideal has a unique reduced (in terms of this algorithm) standard basis. We solve some classical computational problems: the construction of a set of coset representatives, the finding of a set of generators of the syzygy module, the evaluation of ideal quotients and intersections, and the elimination problem. We construct an algorithm testing the cyclicity of an LRS-family $L_R(I)$, which is a generalization of known results to the multivariate case. We present new conditions determining whether a Ferre diagram $\mathcal F$ and a full system of $\mathcal F$-monic polynomials form a shift register. On the basis of these results, we construct an algorithm for lifting a reduced Gröbner basis of a monic ideal to a standard basis with the same cardinality.