Ideal Theory and Gröbner Bases (New) [HB 50]

Magma now provides facilities for computing with Gröbner bases of ideals of polynomial rings over Euclidean rings (including the important case of the integer ring $\mbox{\bf Z}$). Such Gröbner bases are computed in Magma by an extension, due to Allan Steel, of Jean-Charles Faugère's F₄ algorithm which uses sparse linear algebra.

The valid Euclidean rings in Magma supported are: the integer ring $\mbox{\bf Z}$, the integer residue class rings $\mbox{\bf Z}_m$, the univariate polynomial rings K[x] over any field K, Galois rings, and valuation rings.

The extension of Faugère's algorithm depends on an algorithm for computing a unique echelon form of a sparse matrix over a general Euclidean ring. Based on this new sparse matrix algorithm and some other techniques, Magma ensures that a Gröbner basis over a Euclidean ring is reduced, and unique (see the Handbook for details). Uniqueness is even ensured for rings with zero divisors!

Many of the standard functions based on Grobner bases over fields also carry over to ideals defined over Euclidean rings. One can even effectively compute with more general rings which are not Euclidean (see the Handbook examples).

New features:

• Ideals may be defined over general Euclidean rings, and Gröbner bases of such ideals may be computed.