Bergman's diamond lemma

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 $k$-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 $k$ be a commutative associative ring with identity element 1, usually a field. Take an arbitrary set $X$ of variables. In the finite case one usually has $X=\{x_{1},x_{2},x_{3},\dots ,x_{n}\}$. Then $\langle X\rangle$ is the free semigroup with identity 1 on $X$. Finally, $k\langle X\rangle$ is the free associative $k$-algebra over $X$. Elements of $\langle X\rangle$ will be called words, since elements of $X$ can be seen as letters.

Monomial Ordering

Main article: Monomial order

The reductions below require a choice of ordering $<$ on the words i.e. monomials of $\langle X\rangle$. This has to be a total order and satisfy the following:

1. For all words $u,u',v$ and $w$, we have that if $w<v$ then $uwu'<uvu'$.
2. For each word $w$, the collection $\{v\in \langle X\rangle :v<w\}$ is finite.

We call such an order admissible. An important example is the degree lexicographic order, where $w<v$ if $w$ has smaller degree than $v$; or in the case where they have the same degree, we say $w<v$ if $w$ comes earlier in the lexicographic order than $v$. For example the degree lexicographic order on monomials of $k\langle x,y\rangle$ is given by first assuming $x<y$. Then the above rule implies that the monomials are ordered in the following way:

$1<x<y<x^{2}<xy<yx<y^{2}<x^{3}<x^{2}y<\dots$

Every element $h\in k\langle X\rangle$ has a leading word which is the largest word under the ordering $<$ which appears in $h$ with non-zero coefficient. In $k\langle x,y\rangle$ if $h=x^{2}+2x^{2}y-y^{2}x$, then the leading word of $h$ under degree lexicographic order is $y^{2}x$.

Reduction

Assume we have a set $\{g_{\sigma }\}_{\sigma \in S}\subseteq k\langle X\rangle$ which generates a 2-sided ideal $I$ of $k\langle X\rangle$. Then we may scale each $g_{\sigma }$ such that its leading word $w_{\sigma }$ has coefficient 1. Thus we can write $g_{\sigma }=w_{\sigma }-f_{\sigma }$, where $f_{\sigma }$ is a linear combination of words $v$ such that $v<w_{\sigma }$. A word $w$ is called reduced with respect to the relations $\{g_{\sigma }\}_{\sigma \in S}$ if it does not contain any of the leading words $w_{\sigma }$. Otherwise, $w=uw_{\sigma }v$ for some $u,v\in \langle X\rangle$ and some $\sigma \in S$. Then there is a reduction $r_{u\sigma v}:k\langle X\rangle \to k\langle X\rangle$, which is an endomorphism of $k\langle X\rangle$ that fixes all elements of $\langle X\rangle$ apart from $w=uw_{\sigma }v$ and sends this to $uf_{\sigma }v$. 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 $h\in k\langle X\rangle$ to a linear combination of reduced words.

Any element shares an equivalence class modulo $I$ with its reduced form. Thus the canonical images of the reduced words in $k\langle X\rangle /I$ form a $k$-spanning set. The idea of non-commutative Gröbner bases is to find a set of generators $g_{\sigma }$ of the ideal $I$ such that the images of the corresponding reduced words in $k\langle X\rangle /I$ are a $k$-basis. Bergman's Diamond Lemma lets us verify if a set of generators $g_{\sigma }$ 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 $h\in k\langle X\rangle$ is called reduction-unique if given two finite compositions of reductions $s_{1}$ and $s_{2}$ such that the images $s_{1}(h)$ and $s_{2}(h)$ are linear combinations of reduced words, then $s_{1}(h)=s_{2}(h)$. 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.

The series of reductions lead to a common expression. The diamond shape gives rise to the name.

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 $w=tvu$ for some non-empty words $t,v,u$ and assume that $w_{\sigma }=tv$ and $w_{\tau }=vu$ are leading words for some $\sigma ,\tau \in S$. This is called an overlap ambiguity, because there are two possible reductions, namely $r_{1\sigma u}$ and $r_{t\tau 1}$. This ambiguity is resolvable if $tr_{1\sigma u}$ and $r_{t\tau 1}u$ can be reduced to a common expression using compositions of reductions.

Secondly, one leading word may be contained in another i.e. $w_{\sigma }=t\omega _{\tau }u$ for some words $t,u$ and some indices $\sigma ,\tau \in S$. Then we have an inclusion ambiguity. Again, this ambiguity is resolvable if $s_{1}\circ r_{1\sigma 1}(w)=s_{2}\circ r_{t\tau u}(w)$, for some compositions of reductions $s_{1}$ and $s_{2}$.

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 $\{g_{\sigma }\}_{\sigma \in S}\subseteq k\langle X\rangle$ generate an ideal $I$ of $k\langle X\rangle$, where $g_{\sigma }=w_{\sigma }-f_{\sigma }$ with $w_{\sigma }$ the leading words under some fixed admissible ordering of $\langle X\rangle$. Then the following are equivalent:

1. All overlap and inclusion ambiguities among the $g_{\sigma }$ are resolvable.
2. All elements of $k\langle X\rangle$ are reduction-unique.
3. The images of the reduced words in $k\langle X\rangle /I$ form a $k$-basis.

Here the reductions are done with respect to the fixed set of generators $\{g_{\sigma }\}_{\sigma \in S}$ of $I$. When any of the above hold we say that $\{g_{\sigma }\}_{\sigma \in S}$ is a Gröbner basis for $I$. Given a set of generators, one usually checks the first or second condition to confirm that the set is a $k$-basis.

Examples

Resolving ambiguities

Take $A=k\langle x,y,z\rangle /(yx-pxy,zx-qxz,zy-ryz)$, which is the quantum polynomial ring in 3 variables, and assume $x<y<z$. Take $<$ to be degree lexicographic order, then the leading words of the defining relations are $yx$, $zx$ and $zy$. There is exactly one overlap ambiguity which is $zyx$ and no inclusion ambiguities. One may resolve via $yx=pxy$ or via $zy=ryz$ first. The first option gives us the following chain of reductions,

$zyx=pzxy=pqxzy=pqrxyz,$

whereas the second possibility gives,

$zyx=ryzx=rqyxz=rqpxyz.$

Since $p,q,r$ are commutative the above are equal. Thus the ambiguity resolves and the Lemma implies that $\{yx-pxy,zx-qxz,zy-ryz\}$ is a Gröbner basis of $I$.

Non-resolving ambiguities

Let $A=k\langle x,y,z\rangle /(z^{2}-xy-yx,zx-xz,zy-yz)$. Under the same ordering as in the previous example, the leading words of the generators of the ideal are $z^{2}$, $zx$ and $zy$. There are two overlap ambiguities, namely $z^{2}x$ and $z^{2}y$. Let us consider $z^{2}x$. If we resolve $z^{2}$ first we get,

$z^{2}x=(xy+yx)x=xyx+yx^{2},$

which contains no leading words and is therefore reduced. Resolving $zx$ first we obtain,

$z^{2}x=zxz=xz^{2}=x(xy+yx)=x^{2}y+xyx.$

Since both of the above are reduced but not equal we see that the ambiguity does not resolve. Hence $\{z^{2}-xy-yx,zx-xz,zy-yz\}$ is not a Gröbner basis for the ideal it generates.

Algorithm

The following short algorithm follows from the proof of Bergman's Diamond Lemma. It is based on adding new relations which resolve previously unresolvable ambiguities. Suppose that $w=w_{\sigma }u=tw_{\tau }$ is an overlap ambiguity which does not resolve. Then, for some compositions of reductions $s_{1}$ and $s_{2}$, we have that $h_{1}=s_{1}\circ r_{1\sigma u}(w)$ and $h_{2}=s_{2}\circ r_{t\tau 1}(w)$ are distinct linear combinations of reduced words. Therefore, we obtain a new non-zero relation $h_{1}-h_{2}\in I$. The leading word of this relation is necessarily different from the leading words of existing relations. Now scale this relation by a non-zero constant such that its leading word has coefficient 1 and add it to the generating set of $I$. The process is analogous for inclusion ambiguities.

Now, the previously unresolvable overlap ambiguity resolves by construction of the new relation. However, new ambiguities may arise. This process may terminate after a finite number of iterations producing a Gröbner basis for the ideal or never terminate. The infinite set of relations produced in the case where the algorithm never terminates is still a Gröbner basis, but it may not be useful unless a pattern in the new relations can be found.

Example

Let us continue with the example from above where $A=k\langle x,y,z\rangle /(z^{2}-xy-yx,zx-xz,zy-yz)$. We found that the overlap ambiguity $z^{2}x$ does not resolve. This gives us $h_{1}=xyx+yx^{2}$ and $h_{2}=x^{2}y+xyx$. The new relation is therefore $h_{1}-h_{2}=yx^{2}-x^{2}y\in I$ whose leading word is $yx^{2}$ with coefficient 1. Hence we do not need to scale it and can add it to our set of relations which is now $\{z^{2}-xy-yx,zx-xz,zy-yz,yx^{2}-x^{2}y\}$. The previous ambiguity now resolves to either $h_{1}$ or $h_{2}$. Adding the new relation did not add any ambiguities so we are left with the overlap ambiguity $z^{2}y$ we identified above. Let us try and resolve it with the relations we currently have. Again, resolving $z^{2}$ first we obtain,

$z^{2}y=(xy+yx)y=xy^{2}+yxy.$

On the other hand resolving $zy$ twice first and then $z^{2}$ we find,

$z^{2}y=zyz=yz^{2}=y(xy+yx)=yxy+y^{2}x.$

Thus we have $h_{3}=xy^{2}+yxy$ and $h_{4}=yxy+y^{2}x$ and the new relation is $h_{3}-h_{4}=xy^{2}-y^{2}x$ with leading word $y^{2}x$. Since the coefficient of the leading word is -1 we scale the relation and then add $y^{2}x-xy^{2}$ to the set of defining relations. Now all ambiguities resolve and Bergman's Diamond Lemma implies that

$\{z^{2}-xy-yx,zx-xz,zy-yz,yx^{2}-x^{2}y,y^{2}x-xy^{2}\}$ is a Gröbner basis for the ideal it defines.

Further generalisations

The importance of the diamond lemma can be seen by how many other mathematical structures it has been adapted for:

• For power series algebras.
• For certain quiver Hecke algebras.
• For category algebras.
• For small categories.
• For shuffle operads.

The lemma has been used to prove the Poincaré–Birkhoff–Witt theorem.