Efficient Gröbner bases computation over principal ideal rings (Q2211184)

In the paper under review, the authors present new techniques for improving the computation of strong Gröbner bases over a principal ideal ring. Let \(R\) be a principal ideal ring; i.e. a unital commutative ring such that every ideal of \(R\) is principal. Let \(P=R[x_1,\ldots ,x_n]\) be the polynomial ring in \(n\) variables over \(R\). Let us fix a monomial ordering \(\prec\) on \(P\). For any polynomial \(f\in P\), we can define the leading term of \(f\), denoted by \(lt(f)\), as the greatest term (including the coefficient) appearing in \(f\). For a given ideal \(I\subset R\), a finite set \(G\subset I\) is called a strong Gröbner basis of \(I\) if for any polynomial \(0\ne f\in I\), there exists \(g\in G\) such that \(lt(f)\mid lt(g)\). In order to compute strong Gröbner bases, in addition to S-polynomials proposed by Buchberger, on needs to consider GCD-polynomials and A-polynomials. Based on this discussion, we can describe a variant of Buchberger's algorithm to construct strong Gröbner bases. To compute a strong Gröbner basis for an ideal of \(I\subset P\), the authors apply a kind of modular method by passing to quotient rings. More precisely, they choose an element \(n\in R\), construct a Gröbner basis of the ideal \(\bar{I}\subset (R/nR)[x]\) and from this basis a Gröbner basis for the ideal \(I\) is reconstructed. This algorithm has been implemented in the Julia package for the special case of \(R=\mathbb{Z}\). Running standard benchmarks shows the efficiency of the algorithm.