In mathematics, specifically the field of abstract algebra, Bergman's Diamond Lemma (after George Bergman) is a method for confirming whether a given set of monomials of an algebra forms a -basis. It is an extension of Gröbner bases to non-commutative rings. The proof of the lemma gives rise to an algorithm for obtaining a non-commutative Gröbner basis of the algebra from its defining relations. However, in contrast to Buchberger's algorithm, in the non-commutative case, this algorithm may not terminate.
Preliminaries
Let be a commutative associative ring with identity element 1, usually a field. Take an arbitrary set of variables. In the finite case one usually has . Then is the free semigroup with identity 1 on . Finally, is the free associative -algebra over . Elements of will be called words, since elements of can be seen as letters.
Monomial Ordering
The reductions below require a choice of ordering on the words i.e. monomials of . This has to be a total order and satisfy the following:
For all words and , we have that if then . For each word , the collection is finite.
We call such an order admissible. An important example is the degree lexicographic order, where if has smaller degree than ; or in the case where they have the same degree, we say if comes earlier in the lexicographic order than . For example the degree lexicographic order on monomials of is given by first assuming . Then the above rule implies that the monomials are ordered in the following way:
Every element has a leading word which is the largest word under the ordering which appears in with non-zero coefficient. In if , then the leading word of under degree lexicographic order is .
Reduction
Assume we have a set which generates a 2-sided ideal of . Then we may scale each such that its leading word has coefficient 1. Thus we can write , where is a linear combination of words such that . A word is called reduced with respect to the relations if it does not contain any of the leading words . Otherwise, for some and some . Then there is a reduction , which is an endomorphism of that fixes all elements of apart from and sends this to . By the choice of ordering there are only finitely many words less than any given word, hence a finite composition of reductions will send any to a linear combination of reduced words.
Any element shares an equivalence class modulo with its reduced form. Thus the canonical images of the reduced words in form a -spanning set. The idea of non-commutative Gröbner bases is to find a set of generators of the ideal such that the images of the corresponding reduced words in are a -basis. Bergman's Diamond Lemma lets us verify if a set of generators has this property. Moreover, in the case where it does not have this property, the proof of Bergman's Diamond Lemma leads to an algorithm for extending the set of generators to one that does.
An element is called reduction-unique if given two finite compositions of reductions and such that the images and are linear combinations of reduced words, then . In other words, if we apply reductions to transform an element into a linear combination of reduced words in two different ways, we obtain the same result.
Ambiguities
When performing reductions there might not always be an obvious choice for which reduction to do. This is called an ambiguity and there are two types which may arise. Firstly, suppose we have a word for some non-empty words and assume that and are leading words for some . This is called an overlap ambiguity, because there are two possible reductions, namely and . This ambiguity is resolvable if and can be reduced to a common expression using compositions of reductions.
Secondly, one leading word may be contained in another i.e. for some words and some indices . Then we have an inclusion ambiguity. Again, this ambiguity is resolvable if , for some compositions of reductions and .
Statement of the Lemma
The statement of the lemma is simple but involves the terminology defined above. This lemma is applicable as long as the underlying ring is associative.
Let generate an ideal of , where with the leading words under some fixed admissible ordering of . Then the following are equivalent:
All overlap and inclusion ambiguities among the are resolvable. All elements of are reduction-unique. The images of the reduced words in form a -basis.
Here the reductions are done with respect to the fixed set of generators of . When any of the above hold we say that is a Gröbner basis for . Given a set of generators, one usually checks the first or second condition to confirm that the set is a -basis.