The Gröbner basis of the ideal of vanishing polynomials

We construct an explicit minimal strong Gröbner basis of the ideal of vanishing polynomials in the polynomial ring over Z / m for m ≥ 2 . The proof is done in a purely combinatorial way. It is a remarkable fact that the constructed Gröbner basis is independent of the monomial order and that the set...

Full description

Saved in:
Bibliographic Details
Published in:Journal of symbolic computation 2011-05, Vol.46 (5), p.561-570
Main Authors: Greuel, Gert-Martin, Seelisch, Frank, Wienand, Oliver
Format: Article
Language:English
Subjects:
Gröbner bases
Polynomial rings and ideals
Polynomials over commutative rings
Vanishing ideal
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We construct an explicit minimal strong Gröbner basis of the ideal of vanishing polynomials in the polynomial ring over Z / m for m ≥ 2 . The proof is done in a purely combinatorial way. It is a remarkable fact that the constructed Gröbner basis is independent of the monomial order and that the set of leading terms of the constructed Gröbner basis is unique, up to multiplication by units. We also present a fast algorithm to compute reduced normal forms, and furthermore, we give a recursive algorithm for building a Gröbner basis in Z / m [ x 1 , x 2 , … , x n ] along the prime factorization of m . The obtained results are not only of mathematical interest but have immediate applications in formal verification of data paths for microelectronic systems-on-chip.
ISSN:0747-7171
1095-855X
DOI:10.1016/j.jsc.2010.10.006