On Gröbner Bases in Monoid and Group Rings

Abstract

Following Buchberger’s approach to computing a Gröbner basis of a polynomial ideal in polynomial rings, a completion procedure for finitely generated right ideals in Z[H] is given, where H is an ordered monoid presented by a finite, convergent semi-Thue system (Σ,T). Taking a finite set F ⊆ Z[H] we get a (possibly infinite) basis of the right ideal generated by F, such that using this basis we have unique normal forms for all p ∈ Z[H] (especially the normal form is 0 in case p is an element of the right ideal generated by F). As the ordering and multiplication on H need not be compatible, reduction has to be defined carefully in order to make it Noetherian. Further we no longer have p . x —>p 0 for p ∈ Z[H]‚ x ∈ H. Similar to Buchberger’s s-polynomials, confluence criteria are developed and a completion procedure is given. In case T = ∅ or (Σ, T) is a convergent, 2-monadic presentation of a group providing inverses of length 1 for the generators or (Σ, T) is a convergent presentation of a commutative monoid, termination can be shown. So in this cases finitely generated right ideals admit finite Gröbner bases. The connection to the subgroup problem is discussed.