Zoran Skoda diamond lemma

Other literature

Š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

  • kk – associative ring
  • XX – any set,
  • {X}\{X\} – free semigroup with 11 on XX
  • k{X}k\{X\} – semigroup algebra of {X}\{X\}

Let SS be a set of pairs of the form σ=(W σ,f σ)\sigma = (W_\sigma, f_\sigma) where W σ{X}W_\sigma \in \{X\} , f σk{X}f_\sigma \in k\{X\}.

For any σS\sigma \in S and A,B{X}A,B \in \{X\}, let r AσBr_{A\sigma B} denote the kk-module endomorphism of k{X}k\{X\} that fixes all elements of {X}\{X\} other than AW σBAW_\sigma B, and that sends this basis element to Af σBAf_\sigma B. We shall call the given set SS a reduction system and the maps r AσB:k{X}k{X}r_{A\sigma B} : k\{X\} \rightarrow k\{X\} reductions.

We shall say that a reduction r AσBr_{A\sigma B} acts trivially on an element ak{X}a \in k\{X\} if the coefficient of AW σBAW_\sigma B in aa is zero, and we shall call aa irreducible (under SS) if every reduction is trivial on aa, i.e. if aa involves none of the monomials AW σBAW_\sigma B. The kk-submodule of all irreducible elements of k{X}k\{X\} will be denoted k{X} irrk\{X\}_{\mathrm{irr}}. A finite sequence of reductions r 1,,r nr_1, \ldots , r_n (r i=r A iσ iB i)(r_i = r_{A_i\sigma_i B_i}) will be said to be final on ak{X}a \in k\{X\} if r nr 1(a){X} irrr_n \cdots r_1(a) \in \{X\}_{\mathrm{irr}}.

An element ak{X}a \in k\{X\} will be called reduction-finite if for every infinite sequence r 1,r 2,r_1, r_2, \ldots of reductions, r ir_i acts trivially on r i1r 1(a)r_{i-1} \cdots r_1(a) for all sufficiently large ii. If aa is reduction-finite, then any minimal sequence of reductions r ir_i, such that each r ir_i acts nontrivially on r i1r 1(a)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 kk-submodule of k{X}k\{X\}.

We shall call an element ak{X}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)r_S(a).

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

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

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

r(αa+b)=rrr(αa+b)=αrrr(a)+rrr(b)=αr S(a)+r S(b), 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,ca,b,c are monomials A,B,C,A,B,C, and rr is a single reduction r DσEr_{D \sigma E}. But in that case,

Ar DσE(B)C=r ADσEC(ABC), Ar_{D \sigma E}(B)C = r_{AD\sigma E C}(ABC),

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

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

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

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

Let II denote the two-sided ideal of k{X}k\{X\} generated by the elements W σf σW_\sigma - f_\sigma (σinS\sigma in S). As a kk-module, II is spanned by the products A(W σf σ)BA(W_\sigma - f_\sigma)B.

If \leq is a partial order on k{X}k\{X\} compatible with the reduction system SS, and AA is any element of {X}\{X\}, let I AI_A denote the submodule of k{X}k\{X\} spanned by all elements B(W σf σ)CB(W_\sigma - f_\sigma)C such that BW σC<ABW_\sigma C\lt A. We shall say that an ambiguity (σ,τ,A,B,C)(\sigma, \tau, A,B,C) is resolvable relative to \leq if f σCAf τI ABCf_\sigma C - Af_\tau \in I_{ABC} (or for inclusion ambiguities, if Af σBf τI ABCAf_\sigma B - f_\tau \in I_{ABC}). Any resolvable ambiguity is resolvable relative to \leq.

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

(a) All ambiguities of SS are resolvable.

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

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

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

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

More generally, if S 1S 2S_1 \subset S_2 are reduction systems, such that S 1S_1 is compatible with \leq and all its ambiguities are resolvable, and if S 2S_2 contains some σ\sigma such that W σW_\sigma is irreducible with respect to S 1S_1, then the inclusion of ideals associated with these systems, I 1I 2I_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

Last revised on October 11, 2022 at 06:22:34. See the history of this page for a list of all contributions to it.