Lifting canonical algorithms from a ring R to the ring R[x] (Q1121016): Difference between revisions

Methods of computation in polynomial rings are of central importance in computer algebra and have received a corresponding amount of attention. Among the problems of interest are (i) the choice of suitable bases for ideals, (ii) the choice of representatives of cosets and the reduction of a given polynomial to its equivalent representative, and (iii) the construction of a basis for the set of syzygies of a given ideal. The present paper addresses these problems by lifting from a ring R to R[x]. Let S be a set of polynomials generating an ideal J in R[x]. Let \(M_ k,...,M_ n\) be a partition of S such that for \(j=k,...,n\), the set \(M_ j\) consists of the polynomials of degree j; let \(LC_ j\) denote the set of leading coefficients of \(M_ j\). The sequence \(M_ k,...,M_ n\) is called a Szekeres sequence for J if for each i, \(LC_ i\) spans the ideal of leading coefficients of polynomials of degree i in J and k is the minimal degree of non-zero polynomials in J; it is a Szekeres basis if in addition the span of \(LC_{i-1}\) is properly contained in that of \(LC_ i\). The author gives an algorithm for constructing Szekeres bases and shows how such a basis may be used to lift canonical form algorithms from a ring R to R[x].