Zoran Skoda diamond lemma

Širšov-Bergman diamond lemma in Bergman form

• George M. Bergman, The diamond lemma for ring theory, Adv. in Math. 29 (1978), no. 2, 178–218, MR81b:16001, doi

Suppose we are given the following data

• $k$ – associative ring
• $X$ – any set,
• $\{X\}$ – free semigroup with $1$ on $X$
• $k\{X\}$ – semigroup algebra of $\{X\}$

Let $S$ be a set of pairs of the form $\sigma = (W_\sigma, f_\sigma)$ where $W_\sigma \in \{X\}$ , $f_\sigma \in k\{X\}$.

For any $\sigma \in S$ and $A,B \in \{X\}$, let $r_{A\sigma B}$ denote the $k$-module endomorphism of $k\{X\}$ that fixes all elements of $\{X\}$ other than $AW_\sigma B$, and that sends this basis element to $Af_\sigma B$. We shall call the given set $S$ a reduction system and the maps $r_{A\sigma B} : k\{X\} \rightarrow k\{X\}$ reductions.

We shall say that a reduction $r_{A\sigma B}$ acts trivially on an element $a \in k\{X\}$ if the coefficient of $AW_\sigma B$ in $a$ is zero, and we shall call $a$ irreducible (under $S$) if every reduction is trivial on $a$, i.e. if $a$ involves none of the monomials $AW_\sigma B$. The $k$-submodule of all irreducible elements of $k\{X\}$ will be denoted $k\{X\}_{\mathrm{irr}}$. A finite sequence of reductions $r_1, \ldots , r_n$ $(r_i = r_{A_i\sigma_i B_i})$ will be said to be final on $a \in k\{X\}$ if $r_n \cdots r_1(a) \in \{X\}_{\mathrm{irr}}$.

An element $a \in k\{X\}$ will be called reduction-finite if for every infinite sequence $r_1, r_2, \ldots$ of reductions, $r_i$ acts trivially on $r_{i-1} \cdots r_1(a)$ for all sufficiently large $i$. If $a$ is reduction-finite, then any minimal sequence of reductions $r_i$, such that each $r_i$ acts nontrivially on $r_{i-1} \cdots r_1(a)$ will be finite, and hence a final sequence. It follows from their definition that the reduction-finite elements form a $k$-submodule of $k\{X\}$.

We shall call an element $a \in k\{X\}$ reduction-unique if it is reduction-finite, and if its image under all final sequences of reductions are the same. This common value will be denoted $r_S(a)$.

Lemma. (i) The set of reduction-unique elements of $k\{X\}$ forms a $k$-submodule, and $r_S$ is a $k$-linear map of this submodule into $k\{X\}_{\mathrm{irr}}$.

(ii) Suppose $a,b,c \in k\{X\}$ are such that for all monomials $A,B,C$ occurring with nonzero coefficient in $a,b,c$ respectively, the product $ABC$ is reduction-unique. (In particular this implies that $abc$ is reduction-unique.) Let $r$ be a finite composition of reductions. Then $ar(b)c$ is reduction-unique, and $r_S(ar(b)c) = r_S(abc)$.

Proof. (i) Say $a,b \in k\{X\}$ are reduction-unique, and $\alpha \in k$. We know $\alpha a + b$ is reduction-finite. Let $r$ be any composition of reductions final on this element. Since $a$ is reduction-unique, we can find a composition of reductions $r'$ such that $r'r(a) = r_S(a)$, and similarly there is a composition of reductions $r''$ such that $r'' r' r(b) = r_S(b)$. As $r(\alpha a + b)$ is irreducible, we have

$$r(\alpha a + b) = r'' r' r(\alpha a + b) = \alpha r'' r' r(a) + r'' r' r(b) = \alpha r_S(a) + r_S(b),$$

from which our assertions follow.

(ii) By (i) and the way (ii) is formulated, it clearly suffices to prove (ii) in the case where $a,b,c$ are monomials $A,B,C,$ and $r$ is a single reduction $r_{D \sigma E}$. But in that case,

$$Ar_{D \sigma E}(B)C = r_{AD\sigma E C}(ABC),$$

which is the image of $ABC$ under a reduction, hence is reduction-unique if $ABC$ is, with the same reduced form. $\Box$

Let us call a $5$-tuple $(\sigma, \tau, A,B,C)$ with $\sigma, \tau \in S$ and $A,B,C \in \{X\} - \{ 1\},$ such that $W_\sigma = AB,$ $W_\tau = BC,$ an overlap ambiguity of $S$. We shall say the overlap ambiguity $(\sigma,\tau, A,B,C)$ is resolvable if there exist compositions of reductions, $r$ and $r'$, such that $r(f_\sigma C) = r'(Af_\tau)$ (the confluence condition on the results of the two indicated ways of reducing $ABC$).

Similarly, a 5-tuple $(\sigma,\tau, A,B,C)$ with $\sigma \neq \tau \in S$ and $A,B,C \in k\{X\}$ will be called an inclusion ambiguity if $W_\sigma = B,$ $W_\tau = ABC;$ and such an ambiguity will be called resolvable if $Af_\sigma C$ and $f_\tau$ can be reduced to a common expression.

By a semigroup partial ordering on $k\{X\}$ we shall mean a partial order $''\leq''$ such that $B \lt B' \Rightarrow ABC \lt AB'C$ ($A,B,B',C \in \{X\}$), and it will be called compatible with $S$ if for all $\sigma \in S$, $f_\sigma$ is a linear combination of monomials $\lt W_\sigma$.

Let $I$ denote the two-sided ideal of $k\{X\}$ generated by the elements $W_\sigma - f_\sigma$ ($\sigma in S$). As a $k$-module, $I$ is spanned by the products $A(W_\sigma - f_\sigma)B$.

If $\leq$ is a partial order on $k\{X\}$ compatible with the reduction system $S$, and $A$ is any element of $\{X\}$, let $I_A$ denote the submodule of $k\{X\}$ spanned by all elements $B(W_\sigma - f_\sigma)C$ such that $BW_\sigma C\lt A$. We shall say that an ambiguity $(\sigma, \tau, A,B,C)$ is resolvable relative to $\leq$ if $f_\sigma C - Af_\tau \in I_{ABC}$ (or for inclusion ambiguities, if $Af_\sigma B - f_\tau \in I_{ABC}$). Any resolvable ambiguity is resolvable relative to $\leq$.

Theorem. Let $S$ be a reduction system for a free associative algebra $k\{X\}$ (a subset of $\{X\} \times k\{X\}$), and $\leq$ a semigroup ordering on $\{X\}$, compatible with $S$, and having descending chain condition. Then the following conditions are equivalent:

(a) All ambiguities of $S$ are resolvable.

(b) All ambiguities of $S$ are resolvable relative to $\leq$.

(c) All elements of $k\{X\}$ are reduction-unique under $S$.

Corollary. Let $k\{X\}$ be a free associative algebra, and $''\leq''$ a semigroup partial ordering of $\{X\}$ with descending chain condition.

If $S$ is a reduction system on $k\{X\}$ compatible with $\leq$ and having no ambiguities, then the set of $k$-algebra relations $W_\sigma = f_\sigma$ ($\sigma \in S$) is independent.

More generally, if $S_1 \subset S_2$ are reduction systems, such that $S_1$ is compatible with $\leq$ and all its ambiguities are resolvable, and if $S_2$ contains some $\sigma$ such that $W_\sigma$ is irreducible with respect to $S_1$, then the inclusion of ideals associated with these systems, $I_1 \subset I_2$, is strict.

(Most of the above exposition is adapted from Appendix E in Zoran Škoda’s 2002 thesis.)

Other literature

Related topics include Groebner bases? and rewriting systems.

• Vladimir Dotsenko, Pedro Tamaroff, Tangent complexes and the Diamond Lemma, arxiv/2010.14792

The celebrated Diamond Lemma of Bergman gives an effectively verifiable criterion of uniqueness of normal forms for term rewriting in associative algebras. We present a new way to interpret and prove this result from the viewpoint of homotopical algebra. Our main result states that every multiplicative free resolution of an algebra with monomial relations gives rise to its own Diamond Lemma, so that Bergman’s condition of “resolvable ambiguities” becomes the first non-trivial component of the Maurer–Cartan equation in the corresponding tangent complex. The same approach works for many other algebraic structures, emphasizing the relevance of computing multiplicative free resolutions of algebras with monomial relations.

An adaptation to semigroup-filtered algebras

• Lars Hellström, The diamond lemma for power series algebras, Doktorsavhandling nr. 23 (2002) Matematiska institutionen, Umea 2002 pdf