Wolfram Library Archive

All Collections Articles Books Conference Proceedings
Courseware Demos MathSource Technical Notes
Title Downloads

Revisiting strong Gröbner bases over Euclidean domains

Daniel Lichtblau
Organization: Wolfram Research, Inc.
Revision date


Manuscript from 2003, revised 2010

Buchberger and Kandri-Rody and Kapur defined a strong Gröbner basis for a polynomial ideal over a Euclidean domain in a way that gives rise to canonical reductions. This retains what is perhaps the most important property of Gröbner bases over fields. A difficulty is that these can be substantially harder to compute than their field counterparts. We extend their results for computing these bases to give an algorithm that is effective in practice. In particular we show how to use S-polynomials (rather than "critical pairs") so that the algorithm becomes quite similar to that for fields, and thus known strategies for the latter may be employed. We also show how Buchberger's important criteria for detection of unneeded S-polynomials can be extended to work over a Euclidean domain. We then provide simple examples as well as applications to solving equations in quotient rings, Hensel lifting, Hermite normal form computations, and reduction of univariate polynomial lattices. These serve to demonstrate why Gröbner basis computations over such rings are indeed worthy of consideration.

*Mathematics > Algebra > Field and Ring Theory
*Mathematics > Algebra > Polynomials

Groebner bases, Euclidean domains, strong Groebner bases, Euclidean rings, polynomial algebra
Downloads Download Wolfram CDF Player

integer_Groebner_bases.pdf (194.8 KB) - PDF Document
integer_Groebner_bases.nb (308.9 KB) - Mathematica Notebook