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 be an ordered pair of elements of S. By a match of we mean a 4-tuple of elements of S which satisfy one of the following conditions:

(1) , . (2) , . (3) , , , there is a with , . (4) , , , there is a with , .

These conditions make . This is a common multiple of and 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. where and where is chosen so that is the least common multiple of and for i=1,2. In the noncommutative case, there are several such resolvents--one for each match. If M is a 6-tuple where is a match for and , then we set

Example:

Consider the polynomials

There are four matches for : 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 . The k-th step has available to it a set such that the ideal generated by equals the ideal generated by . The k-th step of the algorithm creates a set by setting it equal to the union of and the set of all nonzero reductions of S-Polynomials for all pairs in . The process repeats as long as there are S-Polynomials with nonzero reductions. In other works, the process repeats until .

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

Helton
Wed Jul 3 10:27:42 PDT 1996