Department of Mathematics & Computer Science | ||||
First we note that the relation between the two kinds of presentation is
given by the following variation of a result of [8].
Proposition
Let be a field and let be a semigroup with presentation
.
Then the algebra is isomorphic to the factor algebra
where is the basis
.
Proof
Define
by
for
,
.
Define a homomorphism
by
.
It is injective since
if and only if
(using
the definitions
).
It is also surjective. Let . Then
for some
,
. Since is presented by
there exist
such
that
for
. Therefore let
. Clearly
and also
. Hence is an
isomorphism.
Now we give our main result.
Theorem
Let
be a semigroup presentation, let be a field
and let
be the -algebra presentation with
.
Then the Knuth-Bendix completion algorithm for the rewrite system
corresponds step-by-step to the noncommutative Buchberger algorithm for
finding a Gröbner basis for the ideal generated by .
Proof
Both the Knuth-Bendix algorithm for and the Buchberger algorithm for
begin by specifying a monomial ordering on which we
denote .
The correspondence between terminology in the two cases is
rewrite system | basis | |||
rule | two-term polynomial | |||
string | monomial | |||
reduction | reduction | |||
left hand side | leading monomial | |||
substring | submonomial | |||
right hand side | remainder | |||
overlap | match | |||
critical pair | S-polynomial | |||
This key part of the correspondence (viii) and (ix) is illustrated diagrammatically in the next section
| ||||
resolve | reduce to zero | |||
reduced critical pair | reduced S-polynomial | |||
complete rewrite system | Gröbner basis |
In terms of rewriting we consider the rewrite system
which consists of a set of rules of the form
orientated so that .
A string
may be reduced
with
respect to if it contains the left hand side of a
rule as a substring i.e. if for some
.
To reduce using the rule we replace by the
right hand side of the rule, and write
.
The Knuth-Bendix algorithm looks for overlaps between rules.
Given a pair of rules , there are four possible
ways
in which an overlap can occur:
,
,
and
. The critical pair
resulting from an overlap is the pair of strings resulting from applying
each rule to the smallest string on which the overlap occurs. The critical
pairs resulting from each of the four overlaps are:
,
,
and
respectively
(see diagram).
In one pass the completion procedure finds all the critical pairs
resulting from overlaps of rules of . Both sides of each of the
critical pairs are reduced as far as possible with respect to to
obtain a reduced critical pair . The original
pair
is said to resolve if . The reduced pairs that
have
not resolved are orientated, so that , and added to forming
. The procedure is then repeated for the rewrite system , to
obtain and so on. When all the critical pairs of a system
resolve (i.e.
) then is a complete rewrite
system.
In terms of Gröbner basis theory applied to this special case we
consider the basis
which consists of a set of two-term polynomials of the
form
multiplied by so that .
A monomial
may be reduced
with respect to if it contains the leading monomial
of a polynomial as a submonomial i.e. if for
some
.
To reduce using the polynomial we replace by the
remainder of the polynomial, and write
.
The Buchberger algorithm looks for matches between polynomials.
Given a pair of polynomials , there are four
possible ways in which an match can occur:
,
,
and
. The S-
polynomial resulting from a match is the difference between the
pair of monomials resulting from applying each two-term polynomial to
the smallest monomial on which the match occurs. The S-polynomials
resulting from each of the four matches are:
,
,
and
respectively
(see diagram).
In one pass the completion procedure finds all the S-polynomials
resulting from matches of polynomials of . The S-polynomials are
reduced as far as possible with respect to to obtain a
reduced
S-polynomial . Note that reduction can only replace one
term with another so the reduced S-ploynomial will have two terms unless
the two terms reduce to the same thing in which case the
original S-polynomial is said to reduce to zero. The
reduced
S-polynomials that have not been reduced to zero are multiplied by , so that , and added to forming . The procedure is
then repeated for the basis , to obtain and so on. When all
the S-polynomials of a basis reduce to zero (i.e.
)
then is a Gröbner basis.
A critical pair in will occur if and only if a corresponding S-polynomial occurs in . Reduction of the pair by is equivalent to reduction of the S-polynomial by . Therefore at any stage any new rules correspond to the new two-term polynomials and . Therefore the completion procedures as applied to and correspond to each other at every step.
Author: A. Heyworth, tel: +44 (0)116 252 3884
Last updated: 2001-05-08
MCS Web Maintainer
This document has been approved by the Head of Department.
© University of Leicester.