next up previous contents
Next: A Gröbner Basis Theorem Up: Background on Ideals Previous: The Reduction Process

The Basis Algorithm

G is a a Gröbner Basis for an ideal I if G is a set of polynomials in I having the property that a polynomial f is in I if and only if 0 is a normal form of f with respect to G. This agrees with the definition in the commutative case, but in the commutative case, a finite Gröbner Basis exists for any ideal and can be obtained by the Buchberger Algorithm applied to any set of generators for the ideal. For ideals in a noncommutative polynomial ring, it need not be true that an ideal has a finite Gröbner Basis. An adaptation of Buchberger's Algorithm to the case of noncommutative polynomial rings is due to F. Mora [FMora].

We now discuss some of the particulars of the GBA given by [FMora]. Critical to a GBA is the construction of, from pairs of polynomials (f,g), common multiples for the leading terms of f and g. Now we recall the appropriate notion of common multiple.

Let S be the free semigroup generated by a finite alphabet A (i.e., the collection of words in the letters of A). Let tex2html_wrap_inline4810 be an ordered pair of elements of S. By a match of tex2html_wrap_inline4810 we mean a 4-tuple tex2html_wrap_inline6612 of elements of S which satisfy one of the following conditions:

(1) tex2html_wrap_inline6616 , tex2html_wrap_inline6618 . (2) tex2html_wrap_inline6620 , tex2html_wrap_inline6622 . (3) tex2html_wrap_inline6624 , tex2html_wrap_inline6626 , tex2html_wrap_inline6628 , there is a tex2html_wrap_inline6630 with tex2html_wrap_inline6632 , tex2html_wrap_inline6634 . (4) tex2html_wrap_inline6636 , tex2html_wrap_inline6638 , tex2html_wrap_inline6640 , there is a tex2html_wrap_inline6630 with tex2html_wrap_inline6644 , tex2html_wrap_inline6646 .

These conditions make tex2html_wrap_inline6648 . This is a common multiple of tex2html_wrap_inline4818 and tex2html_wrap_inline4820 which is minimal in some sense.

In the commutative case, the Basis Algorithm makes use of a kind of resolvent of two polynomials called the S-Polynomial. tex2html_wrap_inline6654 where tex2html_wrap_inline6656 and where tex2html_wrap_inline6658 is chosen so that tex2html_wrap_inline6660 is the least common multiple of tex2html_wrap_inline6662 and tex2html_wrap_inline6664 for i=1,2. In the noncommutative case, there are several such resolvents--one for each match. If M is a 6-tuple tex2html_wrap_inline6672 where tex2html_wrap_inline6612 is a match for tex2html_wrap_inline6676 and tex2html_wrap_inline6656 , then we set



Consider the polynomials


There are four matches for tex2html_wrap_inline6684 : 1. (aba,1,1,aba). In this case the S-Polynomial is


2. (ab,1,1,ba) In this case the S-polynomial is


3. (1,baa,aab,1) In this case the S-Polynomial is


4. (1,a,a,1) In this case the S-Polynomial is


The algorithm is iterative and starts with a finite set of polynomials tex2html_wrap_inline6702 . The k-th step has available to it a set tex2html_wrap_inline6706 such that the ideal generated by tex2html_wrap_inline6702 equals the ideal generated by tex2html_wrap_inline6706 . The k-th step of the algorithm creates a set tex2html_wrap_inline6714 by setting it equal to the union of tex2html_wrap_inline6706 and the set of all nonzero reductions of S-Polynomials for all pairs in tex2html_wrap_inline6706 . The process repeats as long as there are S-Polynomials with nonzero reductions. In other works, the process repeats until tex2html_wrap_inline6720 .

next up previous contents
Next: A Gröbner Basis Theorem Up: Background on Ideals Previous: The Reduction Process

Wed Jul 3 10:27:42 PDT 1996