# Tangent complexes and the Diamond Lemma

Vladimir Dotsenko, Pedro Tamaroff

► To cite this version:

Vladimir Dotsenko, Pedro Tamaroff. Tangent complexes and the Diamond Lemma. Bulletin of Mathematical Sciences, 2023, pp.2350013. 10.1142/s1664360723500133. hal-03353621

HAL Id: hal-03353621

https://hal.science/hal-03353621v1

Submitted on 19 Sep 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Tangent complexes and the Diamond Lemma

Vladimir Dotsenko

Institut de Recherche Mathématique Avancée, UMR 7501
Université de Strasbourg et CNRS, 7 rue René-Descartes
67000 Strasbourg, France
vdotsenko@unistra.fr

Pedro Tamaroff

Institut für Mathematik, Johann von Neumann-Haus
Humboldt-Universität zu Berlin, Rudower Chaussee 25
12489 Berlin, Germany
tamarofp@hu-berlin.de

Received 6 November 2020

Revised 19 September 2023

Accepted 6 October 2023

Published 31 October 2023

Communicated by Efim Zelmanov

The celebrated Diamond Lemma of Bergman gives an effectively verifiable criterion of uniqueness of normal forms for term rewriting in associative algebras. We revisit that result in the context of deformation theory and homotopical algebra; this leads to a new proof using multiplicative free resolutions. Specifically, our main result states that every such resolution of an algebra with monomial relations gives rise to its own Diamond Lemma, where Bergman’s condition of “resolvable ambiguities” is precisely the first nontrivial 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 resolutions of algebras with monomial relations.

**Keywords:** Deformation theory; Diamond Lemma; Gröbner basis; multiplicative free resolution; rewriting system; tangent complex.

Mathematics Subject Classification 2020: Primary: 16Z10; Secondary: 13P10, 16E05, 17A61, 18N40
# 0. Introduction

## 0.1. *Context of our work*

When studying algebras presented by generators and relations, the central general result is the statement known as the Diamond Lemma. Historically, one would say that it was already implicit in Shirshov’s work [84] who proved an analogous but technically more involved result, the Composition Lemma, in the case of Lie algebras. In the decade that followed, various versions of the same result were established, highlighting the multitude of its applications: the Buchberger algorithm for commutative associative algebras [22] leading to the establishment of Gröbner bases as a key tool in symbolic computation, the Knuth–Bendix algorithm for attacking the word problem in universal algebra [49], and most importantly for our purposes, two equivalent results for associative algebras obtained independently in early 1970s, the Composition Lemma of Bokut [12], and the Diamond Lemma of Bergman [11], who proposed the catchy name to in order to emphasize the analogy with the classical result of Newman [70]. Paraphrasing the opening phrase of [11], the main results of our paper are doubly trivial: Bergman’s Diamond Lemma is, in his own words, trivial, and our main goal is to explain a new trivial proof of this trivial statement, as well as some other trivial statements, from the point of view of homotopical algebra. However, we believe that this work will be advantageous for readers of all backgrounds. For non-experts, it can serve as a gentle introduction to several topics at the crossroads of term rewriting and deformation theory. For the readers whose intuition comes from homotopical algebra, our work will hopefully feel like a conceptual explanation of useful but seemingly technical criteria of “resolvable ambiguities” for uniqueness of normal forms. Finally, for the readers with a background in Gröbner–Shirshov bases or term rewriting, our proof will offer intuition behind both the Diamond Lemma and its important optimization, known as the Chain Criterion in the commutative case [21, 28, 50] and as the Triangle Lemma in the case of non-commutative associative algebras [20, 56, 88], as well as precise guidance on how to generalize those for other algebraic structures. In a nutshell, our work means that explicit computation of resolutions for algebras with monomial relations helps both to state the relevant Diamond Lemmas and to optimize them.

## 0.2. *From Gröbner bases to deformation theory and back*

The idea of using Gröbner bases for computing homological invariants of associative algebras is well known. The seemingly earliest instance appears in the work of Priddy [72] who constructed resolutions for the ground field, viewed as the trivial module, for algebras presented by quadratic-linear relations; this was later generalized by Anick [3] to arbitrary presentations. Existence of such resolutions is not at all surprising for the following reason. Defining relations of an associative algebra A form a Gröbner basis if the same monomials give a vector space basis for both
algebras $A$ and $A_{\text{mon}}$; the latter is the algebra with monomial relations given by the leading monomials of the relations of $A$ with respect to a suitable ordering. The trivial module for $A_{\text{mon}}$ admits a combinatorially defined free resolution, implicit in the work [4] of Backelin, and explicitly determined by Green, Happel and Zacharia in [33]. Such resolution can be obtained as a contraction of the bar resolution; incorporating the lower terms of relations from a Gröbner basis can be obtained from such a contraction by homological perturbation techniques, see, for example, the approaches of [10, 35, 36, 55]. In fact, the one-sided module resolution of Anick can be generalized to a bimodule resolution, as established by Bardzell [5, 6], leading to a computational method for determining the Hochschild (co)homology of an algebra, and thus for studying deformations of a given algebra. This construction works under a weaker assumption of a convergent rewriting system instead of a Gröbner basis, as shown by Chouhy and Solotar in [23]; we invite the reader to consult [7] for a cornucopia of applications of that resolution in deformation theory.

Our main wish, motivated by interest in generalizing these methods to algebraic structures other than associative algebras, is to go in the opposite direction and re-discover effective criteria for reduction systems with unique normal forms from the deformation theory viewpoint. Since in those situations the multiplication table of an algebra $A$ is obtained from the simple combinatorial multiplication table of $A_{\text{mon}}$ by incorporating appropriate lower terms, we naturally find ourselves in the framework of deformation theory. In fact, very recently the bimodule resolutions mentioned above have been used to study deformations of algebras with monomial relations by Barmeier and Wang in their work on deformation theory of quiver algebras [7] and by Redondo and Bertone in [77], using the following idea. A free bimodule resolution

$$A_{\text{mon}} \otimes C_{\bullet} \otimes A_{\text{mon}} \simeq A_{\text{mon}}$$

leads to the representative $\text{Hom}(C_{\bullet}, A_{\text{mon}})$ of the deformation complex, and one can use a strong deformation retract relating it to the Hochschild complex to compute explicitly its $L_{\infty}$-algebra structure using the homotopy transfer theorem. Studying deformations of $A_{\text{mon}}$ may be accomplished via studying solutions to the Maurer–Cartan equation in that $L_{\infty}$-algebra, and one may obtain various results in this way. However, if one adopts this viewpoint, the Diamond Lemma criterion of “resolvable ambiguities” cannot be recovered instantly: it involves a calculation in the free associative algebra which cannot be reproduced directly since the target space of the deformation complex is the monomial algebra $A_{\text{mon}}$. The two deformation complexes are homotopy equivalent, so the necessary result can be proved in principle. However, recovering the classical Diamond Lemma will require some translation, in the spirit of Anick’s slogan “the perturbative construction of the second differential of the resolution is precisely the procedure of resolving ambiguities”, see [3, Sec. 2]. We also refer the reader to a discussion of this phenomenon in the survey of Ufnarovski [88, Sec. 3.8] where one also finds the Triangle Lemma as a way to optimize the algorithm.
### 0.3. Deformations via tangent complexes

It turns out that a natural way to remedy the situation is to move from homology to homotopy, and study deformations of algebras in terms of homotopical algebra. This means working with multiplicative free resolutions, that is resolutions which are free as algebras rather than as bimodules. In this case, the homotopy class of the deformation complex of an algebra can be represented by its tangent complex, that is, the differential graded Lie algebra of derivations of its free resolution. Historically, this approach to deformations first emerged in the case of commutative associative algebras. In this context, it makes sense to note that some of the pioneering works both in the theory of Gröbner bases and in the deformation theory appeared in the algebro-geometric context: the former in the solution of the resolution of singularities problem in characteristic zero by Hironaka [40, 41], and the latter in Palamodov's work on deformation of analytic spaces [71], where the tangent complex approach is attributed to unpublished work of Tyurina (who tragically died in a kayaking accident at the age of 32). However, the standard bases of Hironaka were just one of many tools in a paper of more than two hundred pages, and the power of this method in algebraic geometry and commutative algebra became apparent only after the work of Buchberger [22] who highlighted their algorithmic nature. The tangent complex approach to deformation theory of algebras became widely known from the famous paper [80] by Schlessinger and Stasheff. We would like to also remark that a seemingly completely independent path to multiplicative resolutions which however stays away from deformation theory questions emerges in higher-categorical rewriting theory. Original work of Squier [54, 82] on homological finiteness conditions for monoids admitting a convergent presentation first received a higher-categorical flavor in works of Lafont [52] and Citterio [25]; corresponding multiplicative resolutions appear in work of Lafont and Métayer [53] and Guetta [34] relying on theory of resolutions of categories by polygraphs developed by Métayer [69]. This formalism was recently extended to the $k$-linear context by Guiraud et al. [38], who in particular explained how to construct a polygraphic resolution of an associative algebra by techniques similar to the perturbative construction of $A_\infty$-structures [37] and free resolutions of algebras [44].

### 0.4. Structure of the paper

For us, it is crucial that working with free resolutions means that recovering Bergman's criterion of resolvable ambiguities stands a chance, at least in principle, since our deformation complexes of algebras with monomial relations have free associative algebras as target spaces. Our approach blends ideas and methods from several different areas, and we tried to offer enough detail when recalling the necessary background information. Our first homotopical re-formulation of uniqueness of normal forms is a general criterion in terms of perturbations of free resolutions (Theorem 4.1). Using that result, we prove another general criterion in terms of approximate solutions to the Maurer–Cartan equation in the tangent
complex (Theorem 5.1). Using this latter result, we establish the main result of this paper (Theorem 5.2): every model extending the Shafarevich complex of the given relations gives rise to its own Diamond Lemma, where the resolvable ambiguities condition of the Diamond Lemma is precisely the first nontrivial component of the Maurer-Cartan equation in the tangent complex of the model. Applying that latter result to some specific combinatorial models, we recover the classical Diamond Lemma in the case of the inclusion-exclusion model of the first author and Khoroshkin [26] and the Triangle Lemma in the case of the minimal model of the second author [85]. We discuss some analogues and possible generalizations of our results for other types of algebras towards the end of the paper. Already in the case of operads with monomial relations, explicit formulas for minimal models are not known in general, and only a much weaker version of the Triangle Lemma is available [20]; we hope that our work will attract due attention to this question.

## 0.5. Precursors: Evgeny Solomonovich Golod and Victor Nikolaevich Latyshev

To conclude the introduction, we would like to mention two crucial sources of inspiration for our work. The first of them is the work of Golod who discovered a proof of the Diamond Lemma [30] using the non-commutative analogue of the Koszul complex, the Shafarevich complex associated to a system of elements in the free algebra originally introduced in [32]. That complex is a differential graded algebra whose homotopy type depends on the presentation of the original algebra. Our homotopy invariant free resolutions are obtained from the Shafarevich complex at the cost of adding extra generators of higher degrees; we believe that the benefit of the resulting clarity outweighs the cost. Our second inspiration comes from the work of Latyshev who used normal forms to resolve some particular cases [60, 61] of the celebrated Specht problem on identities of associative algebras [81], and advocated general importance of normal forms and standard bases [57-59]. Both Golod and Latyshev passed away relatively recently (in July 2018 and April 2020, respectively). We would like to dedicate this work to their memory.

## 1. Conventions

Unless otherwise indicated, all objects in this paper are defined over an arbitrary ground field $k$. By a *graded* vector space we mean a vector space $V$ of the form

$$V = \bigoplus_{n \in \mathbb{Z}} V_n,$$

where we write $|v| = n$ for $v \in V_n$, and refer to $n$ as the *homological degree* of an element $v$. The adjective “homological” means that these degrees create “Koszul signs” arising from exchanging factors in tensor products. Recall that one defines
the tensor product of two graded vector spaces by the formula

$$ (V \otimes W)_n := \bigoplus_{i+j=k} V_i \otimes W_j $$

summarized in words by “degrees add under tensor products”, and homological degrees enter the formula for the symmetry isomorphism

$$ \tau_{V,W} : V \otimes W \to W \otimes V $$

given by $\tau(v \otimes w) = (-1)^{|v||w|}w \otimes v$. (This, for a trained eye, creates signs in a lot of places; for example, if one applies the tensor product of linear maps to a tensor product of two vectors, the formula $(\phi \otimes \psi)(v \otimes w) = (-1)^{|\psi||v|}\phi(v) \otimes \psi(w)$ has to be used.) Occasionally, our graded vector spaces will have extra gradings which do not create any extra signs in formulas; in such cases, we shall use the word “grade” for such degrees.

## 2. Term Rewriting

Classically, the theory of term rewriting developed as an abstraction of many situations where one deals with “simplifications of terms”: there is a set of rewriting rules that allow one to replace some terms defined within a certain theory by some other terms. One of the earliest examples which is associated with the notion of term rewriting goes back to the work of Church and Rosser [24] on normal forms in $\lambda$-calculus. For the purpose of this paper, it is fair to say that one of the central results in term rewriting is Newman’s Diamond Lemma [70]. An algebraic viewpoint of that result which is very close to our immediate topics of interest is due to Knuth, and is widely known as the Knuth–Bendix algorithm [49]. However, our goal is to discuss term rewriting in the linear context, where a term may be rewritten as a linear combination of other terms, and this section is intended for reminding the reader of all the relevant definitions. Mathematically, this goes back to [11]; terminologically, we choose to follow the recent literature on rewriting systems, see, for example, [38] and references therein.

### 2.1. Rewriting systems

Let us fix once and for all a finite set $X$; we shall denote by $\langle X \rangle$ the free monoid generated by $X$, so that the linear span $\mathbb{k}\langle X \rangle$ is the free associative $\mathbb{k}$-algebra generated by $X$. For an element $g \in \mathbb{k}\langle X \rangle$ we shall denote by $\text{supp}(g)$ the set of all elements of $\langle X \rangle$ that appear in $g$ with a nonzero coefficient.

**Definition (Rewriting system).** A rewriting system on $\mathbb{k}\langle X \rangle$ is a triple $(X, W, f)$, where $W \subset \langle X \rangle$, and $f$ is a function on $W$ with values in $\mathbb{k}\langle X \rangle$.

The right way to think of a rewriting system is as of a collection of rules that allow to replace each monomial $w \in W$ by the corresponding element $f(w) \in \mathbb{k}\langle X \rangle$.
In this way, each rewriting system $\Sigma$ naturally gives rise to an associative algebra
$A_\Sigma$ with relations $R = \{w - f(w) : w \in W\}$:

$$
A_{\Sigma} = \mathbb{k}\langle X \mid R \rangle.
$$

Each rewriting rule of $\Sigma$ becomes a way to replace monomials divisible by elements of $W$ by other representatives of the same coset in $A_\Sigma$. Since we work with free associative algebras, a monomial $m$ can have several divisors equal to the same element $w$, so one has to be careful and specify the concrete occurrence of $w$ in $m$, which we shall do by indicating a triple $(a, w, b)$ with $awb = m$.

**Definition (Reduction).** Suppose that $w \in W$, and $a, b \in \langle X \rangle$. A *basic reduction* associated to the triple $(a, w, b)$ is the $\mathbb{k}$-linear endomorphism $\rho$ of $\mathbb{k}\langle X \rangle$ such that for each $m \in \langle X \rangle$ we have

$$
\rho(m) = \begin{cases} af(w)b & \text{if } m = awb, \\ m & \text{otherwise.} \end{cases}
$$

A finite sequence of basic reductions is called a *reduction*; it defines a $\mathbb{k}$-linear endomorphism of $\mathbb{k}\langle X \rangle$ by composing, in the given order, the basic reductions appearing in it.

Using reductions is intended to “simplify” representatives of cosets. This is
formalized by the notion of a normal form.

**Definition (Normal form).** An element $g \in \mathbb{k}\langle X \rangle$ is called *irreducible* if $\rho(g) = g$ for every basic reduction $\rho$. A *normal form* of an element $g \in \mathbb{k}\langle X \rangle$ is an irreducible element $\bar{g}$ such that the cosets of $g$ and $\bar{g}$ are equal in $A_\Sigma$.

In principle, it is possible that one can perform basic reductions infinitely many
times. We shall only work with rewriting systems for which it does not happen. To
formalize that, we give the following definition.

**Definition (Terminating rewriting system).** A *pseudo-reduction* is an infinite
sequence

$$
\rho = (\rho_1, \rho_2, \rho_3, \dots)
$$

of basic reductions. To every pseudo-reduction $\rho$ and every $g \in \mathbb{k}\langle X \rangle$ we can asso-
ciate the sequence

$$
\rho(g) = (\rho_1(g), \rho_2\rho_1(g), \rho_3\rho_2\rho_1(g), \dots)
$$

of elements in $\mathbb{k}\langle X \rangle$. We say that an element $g \in \mathbb{k}\langle X \rangle$ is *reduction finite* if for every pseudo-reduction $\rho$, the associated sequence $\rho(g)$ is eventually constant. A rewriting system $\Sigma$ is *terminating* if all elements $g \in \mathbb{k}\langle X \rangle$ are reduction finite.

Note that if an element $g$ is reduction finite, there exists a reduction that sends
this element to an irreducible one, for otherwise we could easily find a pseudo-
reduction $\rho$ for which $\rho(g)$ is not eventually constant. Thus, for a terminating
rewriting system, each element has at least one normal form. All rewriting systems considered in this paper are assumed to be terminating. We shall now recall how to recast termination in terms of partial orderings.

**Definition (Compatible rewriting ordering).** For a given rewriting system $\Sigma$, we say that a partial order $\le$ on $\langle X \rangle$ is a rewriting ordering compatible with $\Sigma$ if the following conditions hold:

(1) *multiplicativity*: if $m < m'$ for two elements $m, m'$, then $amb < am'b$ for any $a, b \in \langle X \rangle$;

(2) *well-ordering*: every non-empty set of monomials has a minimal element;

(3) *compatibility with $\Sigma$*: for all $w \in W$ and all $w' \in \text{supp}(f(w))$, we have $w' < w$.

Among rewriting orderings compatible with $\Sigma$ (if they exist at all), there exists the weakest possible one obtained as follows. We first define $<_{\Sigma}$ as the smallest transitive binary relation that is multiplicative and compatible with $\Sigma$. If $<_{\Sigma}$ is a well-ordering, the reflexive closure $\le_{\Sigma}$ is a rewriting ordering compatible with $\Sigma$, and each other rewriting ordering compatible with $\Sigma$ obviously refines the ordering $\le_{\Sigma}$. According to [11, 23], the rewriting system $\Sigma$ is terminating if and only if $<_{\Sigma}$ is a well-ordering.

For a terminating rewriting system, the associative algebra

$$A_{\Sigma_0} = \mathfrak{k}\langle X | W \rangle$$

obtained from the rewriting system $\Sigma_0 = (W, 0)$ and called the *monomial algebra associated to $\Sigma$* is a relevant object of study. Indeed, an element $g \in \mathfrak{k}\langle X \rangle$ is irreducible if and only if no monomial $m \in \text{supp}(g)$ is divisible by elements of $W$, so irreducible monomials form a basis of the algebra $A_{\Sigma_0}$. However, since the same element may have several different normal forms, the cosets of irreducible monomials might not be linearly independent in the algebra $A_{\Sigma}$.

**Definition (Convergent rewriting system).** A (terminating) rewriting system is convergent if each element $g \in \mathfrak{k}\langle X \rangle$ has exactly one normal form.

Among the rewriting systems, the best known class is given by *Gröbner bases*: those are rewriting systems where there is a total order $\le$ on $\langle X \rangle$ satisfying the above three conditions. Let us recall an example [20, 38] showing that sometimes using a partial order is really advantageous. For that, we consider the algebra $A = \mathfrak{k}\langle x, y, z | x^3 + y^3 + z^3 - xyz \rangle$. Note that for a total multiplicative order, we always have $xyz < \max(x^3, y^3, z^3)$, and one can check that for such an order the corresponding rewriting system is not convergent, so one needs to extend it by further rewriting rules. However, one can consider the rewriting system $\Sigma = (X, W, f)$ with $X = \{x, y, z\}$, $W = \{xyz\}$ and $f(xyz) = x^3 + y^3 + z^3$ which does not arise from a total multiplicative order. Let us explain why this rewriting system is terminating. For that, we define, for each monomial $m$, $\Phi(m) = 3A(m) + B(m)$, where $A(m)$ is the number of divisors of $m$ equal to $xyz$ and $B(m)$ is the number of divisors of $m$ equal to $y$. Then one can check that any application of our rewriting rule
replaces a monomial by a linear combination of terms for which the parameter $\Phi$ is strictly smaller, which guarantees the termination. Later we shall see that this rewriting system is convergent, showing that in this case there is an advantage over the theory of Gröbner bases.

Bergman's Diamond Lemma [11] establishes a criterion of convergence in terms of the so-called "resolvable ambiguities". If this were a paper on rewriting systems, at this point we would formulate and prove that result. However, our goal is to explain how such criterion can be found, so that one can determine its analogues for other algebraic structures. It is easy to see that a rewriting system $\Sigma$ is convergent if and only if the corresponding irreducible monomials are linearly independent. In other words, $\Sigma$ is convergent if and only if the linear map $A_{\Sigma_0} \to A_{\Sigma}$ sending each element of the standard monomial basis of $A_{\Sigma_0}$ to its coset in $A_{\Sigma}$ is an isomorphism of vector spaces. This suggests that convergent rewriting systems may be studied from the viewpoint of deformation theory of associative algebras. In general, the notion of a *deformation* implies that we *deform* the structure by adding lower terms with respect to a suitable filtration. For example, for the classical deformation theory set-up [67] defined over an Artinian local ring containing $\mathfrak{k}$, the filtration may be defined by powers of the maximal ideal $\mathfrak{m}$ of that ring. In our case, the filtration is defined out of the partial ordering $<_{\Sigma}$, or better to say, out of any order that extends it to a total well-ordering. The multiplication table in the algebra $A_{\Sigma_0}$ is very simple: the product of two basis elements is either a basis element or zero. For a convergent rewriting system, the product of two basis elements in the algebra $A_{\Sigma}$ is either a basis element or the linear combination of smaller basis elements obtained by term rewriting. Thus, saying that $\Sigma$ is convergent is equivalent to saying that the algebra $A_{\Sigma}$ is a deformation of the algebra $A_{\Sigma_0}$ with respect to the corresponding filtration. This suggests that using deformation theory of algebras might shed light on convergence of rewriting systems. The main part of this paper uses this viewpoint extensively.

### 3. Homotopy Theory of Associative Algebras

Deformation theory of algebras borrows a lot of intuition from algebraic topology: one may say that algebraic tools for studying continuous deformations of spaces are very much amenable to the case of deformations of algebras. In algebraic topology, an important invariant of a space is its cohomology algebra. However, that algebra itself does not capture many important homotopy invariants. It turns out that in order to remedy this, one should either consider cohomology together with certain higher structures, or work with a bigger algebra of the same homotopy type, for example the differential graded algebra of singular cochains. This led Quillen to the general philosophy of homotopical algebra [75] suggesting that one should extend categories of algebras to better behaved "model categories" with a notion of weak equivalence, an abstraction of homotopy equivalence, and consider the homotopy category formed by equivalence classes. Alternatively, one may say that instead
of studying an algebra it is often beneficial to study its model, which is a better behaved algebra of the same homotopy type in the model category. This section gives a recollection of the corresponding definitions to make the rest of the paper more readable to experts in Gröbner bases and rewriting.

**3.1. Differential graded associative algebras**

A sufficiently general recipe to define model categories is to consider simplicial algebras of the given type. However, in the case of associative algebras, it turns out to be possible to do homotopy theory in a slightly more hands-on way, using differential graded algebras.

**Definition (Differential graded associative algebra).** A *differential graded associative algebra*, is a pair $(A, d)$, where $A$ is a graded associative algebra, that is, a graded vector space equipped with the associative degree zero map $A \otimes A \to A$, and $d : A \to A$ is a degree $-1$ map satisfying the condition $d^2 = 0$ as well as the graded derivation property $d(a_1a_2) = d(a_1)a_2 + (-1)^{|a_1|}a_1d(a_2)$.

We denote by DGA the category whose objects are differential graded associative algebras and whose morphisms from $(A, d_A)$ to $(B, d_B)$ are (degree zero) algebra homomorphisms $f : A \to B$ that are chain maps, that is satisfy $f \circ d_A = d_B \circ f$. Such a morphism $f$ induces a morphism $f_\bullet : H_\bullet(\Lambda, d_\Lambda) \to H_\bullet(B, d_B)$ of graded associative algebras obtained by computing homology. We say that $f$ is a *quasi-isomorphism* if the induced homology morphism $f_\bullet$ is an isomorphism.

**3.2. Models of algebras**

As indicated above, our general plan is to replace an associative algebra with a better behaved differential graded algebra of the same homotopy type. A mathematically precise meaning of the words “better behaved” is given by the notion of a cofibrant object in a closed model category. A motivated reader is invited to consult [42, 75] for foundations of the general theory of model categories. According to Hinich [39, Theorem 4.1.1], the category DGA admits a closed model category structure for which weak equivalences are quasi-isomorphisms, and the fibrations are surjections. In fact, Hinich works in the general framework of algebras over operads, and in the only case relevant for this paper, that of differential graded algebras concentrated in non-negative homological degrees, the same result is established by Jardine [46]. To describe cofibrant objects, we need one more definition.

**Definition (Triangulated quasi-free algebra).** A *quasi-free algebra* is a differential graded algebra $(B, d_B)$ for which the underlying graded associative algebra is free, that is $B \cong T(V)$ for some graded vector space $V$. Such algebra is said to be *triangulated* if its space of generators admits an extra decomposition into a direct
sum (of graded vector spaces)

$$V \cong \bigoplus_{j \ge 1} V^{(j)}$$

for which the differential of an element $v \in V^{(j+1)}$ belongs to the subalgebra generated by $\bigoplus_{1 \le k \le j} V^{(k)}$ for all $j \ge 0$.

The cofibrant objects for Hinich's model category structure on DGA are exactly the retracts of triangulated quasi-free algebras. We remark that it is useful to think that triangulated algebras are an abstraction of the construction of “killing cycles” of Tate [47, 86]. The relevance of triangulated differential graded commutative algebras in homotopy theory became apparent after the seminal paper of Sullivan [83]; for this reason, they are frequently called Sullivan algebras.

**Definition (Model of an algebra).** A model of a differential graded algebra $(A, d_A)$ is a triangulated quasi-free algebra $(T(V), d)$ equipped with a surjective quasi-isomorphism $f$ to $(A, d_A)$. Such a model is said to be minimal if its differential is decomposable, that is for each $v \in V$, the element $d(v)$ is a combination of products of length at least two in the tensor algebra.

While minimal models of algebras are unique up to isomorphism, their existence is a much more subtle matter; see, for example, the unpublished note of Keller [48]. However, the target algebras $(A, d_A)$ of interest for us are in fact non-graded and non-differential, in other words, $A_n = 0$ for $n \ne 0$ and $d_A = 0$. Since we work over a field, minimal models for such algebras exist under very mild assumptions (see, for example, [8, 44]) which hold in all cases that are of interest to us.

### 3.3. Shafarevich complexes

We shall now recall the notion of a Shafarevich complex of a system of elements in an algebra. Those complexes are very rarely models themselves, but they offer a good starting point for constructing a model, which will be one of the guiding principles for our main results.

**Definition (Shafarevich complex).** Let $A$ be an associative (non-differential non-graded) algebra. The Shafarevich complex of a subset $S \subset A$ is the differential graded algebra

$$\mathrm{III}(S, A) = (A * T(U), d).$$

Here $A * T(U)$ is the free product of $A$ and the tensor algebra, the degree of elements of $A$ in the free product is defined to be equal to zero, $U$ is the graded vector space whose only nonzero component is $U_1 = \mathbb{K}\{e_s : s \in S\}$, and $d$ is the unique derivation of degree $-1$ satisfying $d(a) = 0$ for $a \in A$ and $d(e_s) = s \in A$ for each basis element $e_s \in U_1$.

It is an immediate consequence of the definition that the degree zero homology of $\mathrm{III}(S, A)$ is isomorphic to the quotient $\cong A/(S)$. In this paper, we shall only
consider the Shafarevich complexes $\text{III}(S, \mathbb{k}\langle X \rangle)$ for the free algebra $A = \mathbb{k}\langle X \rangle$; it is precisely those that were first defined in work of Golod and Shafarevich [32] and later called the Shafarevich complexes by Golod in [30]. In this particular case, the degree zero homology is the algebra $\mathbb{k}\langle X | S \rangle$. Of course, $\text{III}(S, \mathbb{k}\langle X \rangle) = (T(V), d)$, where $V$ is the graded vector space whose only nonzero components are $V_0 = \mathbb{k}X$ and $V_1 \cong \mathbb{k}S$, and $d$ is the unique graded derivation satisfying $d(x) = 0$ for $x \in X$ and $d(e_s) = s \in \mathbb{k}\langle X \rangle \cong T(V_0)$ for each basis element $s \in V_1$. Thus, $\text{III}(S, \mathbb{k}\langle X \rangle)$ is a triangulated quasi-free algebra whose space of generators is concentrated in homological degrees zero and one corresponding to killing certain cycles in $T(V_0)$. In that capacity, it was rediscovered by Lemaire [62], and used by Anick in his work on Hilbert series of associative algebras [1, 2].

In general, the positive degree homology of $\text{III}(S, \mathbb{k}\langle X \rangle)$ does not vanish, so that differential graded algebra is not a model of $\mathbb{k}\langle X | S \rangle$. In fact, it is known that the homology of $\text{III}(S, \mathbb{k}\langle X \rangle)$ is generated by elements of homological degrees zero and one [31], but this remarkable result will not be immediately useful for us. We however will be mainly interested in models that extend Shafarevich complexes.

**Definition (Acyclic extension of the Shafarevich complex).** Let $A \cong \mathbb{k}\langle X | S \rangle$ be an associative algebra presented by generators and relations. We say that a model of the algebra $A$ is an *acyclic extension of the Shafarevich complex* $\text{III}(S, \mathbb{k}\langle X \rangle)$ if it is concentrated in non-negative homological degrees, and in homological degrees zero and one is isomorphic to the Shafarevich complex $\text{III}(S, \mathbb{k}\langle X \rangle)$.

## 4. Rewriting Systems and Perturbation of Models

Since any model of an associative algebra is quasi-free, it is not particularly interesting as an algebra: all the complexity is hidden in the differential. Thus, if we replace an algebra by a model, it is reasonable to expect that studying deformation theory is done via studying perturbations of the differential. The main result of this section confirms this expectation: essentially, it says that once we fix a filtration, deforming a monomial algebra with respect to that filtration is equivalent to perturbing the differential of its model.

**Definition (Word-homogeneous algebra).** Let us call a differential associative graded algebra $(B, d)$ *word-homogeneous* if it has an extra grading by the free monoid $\langle X \rangle$, that is we have a decomposition into a direct sum of chain subcomplexes

$$ (B, d) = \bigoplus_{u \in \langle X \rangle} (B_u, d), $$

such that $B_{u_1}B_{u_2} \subseteq B_{u_1u_2}$ for all $u_1, u_2 \in \langle X \rangle$. For an element $b \in B_u$, we say the element $b$ is *word-homogeneous* of *grade* $u$.

As above, let us consider a rewriting system $\Sigma = (X, W, f)$. Clearly, the non-differential non-graded algebra $(A_{\Sigma_0}, 0)$ is word-homogeneous. It is easy to
establish that its minimal model is word-homogeneous; while we shall consider models that are not necessarily non-minimal, we shall restrict ourselves to word-homogeneous models when considering monomial algebras. Moreover, since the algebra $A_{\Sigma_0}$ is concentrated in homological degree zero, it is enough to work with word-homogeneous models concentrated in non-negative homological degrees. For such a model $(T(V), d)$, the differential graded subalgebra $(T(V_0), 0)$ surjects onto $A_{\Sigma_0}$; in other words, the image of the vector space $V_0$ generates the algebra $A_{\Sigma_0}$. In the context of studying the rewriting system $\Sigma$, we are working with a distinguished set of generators $X$, so it makes sense to focus on models with $V_0 \cong kX$. Moreover, since $H_\bullet(T(V), d) \cong A_{\Sigma_0}$, the image of $V_1$ under $d$ generates the two-sided ideal of $T(V_0) \cong k\langle X\rangle$ generated by $W$; it makes sense to focus on models with $V_1 \cong kW$. Using the terminology we recalled earlier, this means that we work with word-homogeneous acyclic extensions of the Shafarevich complex $\Pi(W, k\langle X\rangle)$. Finally, we make one slightly less trivial assumption: similar to many situations in rational homotopy theory, we shall consider models of finite type, that is require that $\dim V_n < \infty$ for all $n \ge 0$. This is true for the minimal model of a monomial algebra with finitely many relations, as established by the second author in [85], and for some other models of interest.

The following result is a mild generalization of [85, Theorem 5.1], which mimics [26, Theorem 4.1], and is an adaptation to our case of the argument of Anick [3, Theorem 1.4]. We say that a linear endomorphism of a word-homogeneous algebra is $\Sigma$-filtered if it sends every element of grade $u \in \langle X\rangle$ to a combination of elements of grades strictly less than $u$ with respect to the ordering $<_\Sigma$.

**Theorem 4.1.** Suppose that $(T(V), d)$ is a word-homogeneous acyclic extension of finite type of the Shafarevich complex $\Pi(W, k\langle X\rangle)$. The rewriting system $\Sigma$ is convergent if and only if there exists a model of the algebra $A_\Sigma = k\langle X | R\rangle$ that is an acyclic extension $(T(V), d+d')$ of the Shafarevich complex $\Pi(R, k\langle X\rangle)$ with a $\Sigma$-filtered perturbation $d'$.

Note that being an acyclic extension of the Shafarevich complex $\Pi(R, k\langle X\rangle)$ means in particular that $d'|_{V_0} = 0$ and that for each basis element $e_w \subset V_1$, we have

$$d'(e_w) = -f(w),$$

so $d'$ is indeed $\Sigma$-filtered on elements of degree one.

**Proof.** Suppose first that such a model exists. Extend the partial ordering $<_\Sigma$ to a total well ordering arbitrarily, and consider the filtration of the graded vector space $T(V)$ associated to that ordering. Since we are dealing with a countable well-order that is not necessarily isomorphic to $\mathbb{N}$, one has to be careful, and either consider a sequence of spectral sequences, or consider generalized spectral sequences of countably filtered modules, such as the transfinite spectral sequences of Hu [43] or spectral sequences of transfinite filtered modules of Rahmati [76]; either strategy works in our case, and allows one to construct a spectral sequence converging to
$H_\bullet(T(V), d+d')$ with the zeroth term $E^0$ given by $(T(V), d)$. This forces our spectral sequence to collapse on the following page, since the homology $H_\bullet(T(V), d)$ is concentrated in homological degree zero. Examining the individual word-homogeneous components, we conclude that cosets of the monomial basis of $A_{\Sigma_0}$ form a basis of the vector space $A_\Sigma$, and therefore $\Sigma$ is convergent.

Suppose now that $\Sigma$ is convergent. If we ignore the differential, there exist surjective homomorphisms from the algebra $T(V)$ to both the monomial algebra $A_{\Sigma_0}$ and the algebra $A_\Sigma$: one may project it onto its part $T(V_0) \cong \mathbb{k}\langle X\rangle$ of homological degree 0, and the latter admits obvious projection maps to its respective quotients. Let us choose splittings for those projections; this amounts to exhibiting two idempotent endomorphisms $\pi$ and $\pi'$ of $T(V)$ such that both of them annihilate all elements of positive homological degree, the former annihilates the ideal of $T(V_0) \cong \mathbb{k}\langle X\rangle$ generated by $W$, and the latter annihilates the ideal of $T(V_0) \cong \mathbb{k}\langle X\rangle$ generated by $R$. Since the model $T(V)$ is of finite type, there exists a word-homogeneous map $h: T(V) \to T(V)$ such that $[d, h] = 1 - \pi$.

We are going to define a derivation $d': T(V) \to T(V)$ of homological degree $-1$ satisfying the requested conditions; since $d'$ is a derivation, it is enough to define it on the generators. We shall also define a map

$$h' : \ker(d+d') \to T(V)$$

of homological degree 1 such that

$$(d+d')(h+h')|_{\ker(d+d')} = 1 - \pi.$$

This latter condition instantly implies that $(T(V), d+d')$ is a model of $A_\Sigma$.

We shall construct the maps and prove their properties inductively. More specifically, we shall prove by induction on $k \ge 0$ that one can define the values of the perturbation $d'$ on generators of homological degree $k+1$ and the values of $h'$ on elements of $\ker(d+d')$ of homological degree $k$ so that the following conditions hold:

- perturbation: both maps $d'$ (on generators of homological degree $k+1$) and $h'$ (on elements of $\ker(d+d')$ of homological degree $k$) are $\Sigma$-filtered,

- square-zero: we have $(d+d')^2 = 0$ on generators of homological degree $k+1$,

- homotopy: we have $(d+d')(h+h') = 1 - \pi$ on elements of $\ker(d+d')$ of homological degree $k$; of course, according to the definition of the map $\pi$, this condition reads $(d+d')(h+h') = 1$ on elements of positive homological degree.

As a basis of induction, we recall that the formula $d'(e_w) = -f(w)$ indicated in the statement of the theorem is $\Sigma$-filtered, and the square-zero condition is satisfied for degree reasons, as there are no elements of negative homological degree. Suppose that $x$ is a degree zero element of grade $u$. We define

$$h'(x) = \begin{cases} 0 & \text{if } x \notin (W), \\ -(h+h')( (1-\pi)(x) - (d+d')h(x) ) & \text{if } x \in (W). \end{cases}$$
Since the map $h$ is word-homogeneous and since we already know that $d'$ is $\Sigma$-filtered on elements of homological degree 1, the map $d'h$ is $\Sigma$-filtered. Also, the map $(1 - \pi) - dh = (1 - \pi) - (1 - \bar{\pi}) = (\bar{\pi} - \pi)$ is $\Sigma$-filtered simply by definition of $\langle\Sigma\rangle$. By induction with respect to the well-ordering $\langle\Sigma\rangle$, we may assume the $\Sigma$-filtered condition for the map $h'$ evaluated on sum of those elements, and the perturbation condition for $h'$ evaluated on $x$ follows. Finally, to show the homotopy property evaluated on elements of homological degree zero, we note that on elements $x \notin (W)$ this becomes $0 = 0$, and otherwise we have

$$(d+d')(h+h')(x) = (d+d')(h(x) - (d+d')(h+h'))((1-\pi)(x) - (d+d')h(x)),$$

which, by induction on the well-ordering $\langle\Sigma\rangle$ is equal to

$$ \begin{aligned} & (d+d')h(x) - (1-\pi)((1-\pi)(x) - (d+d')h(x)) \\ & = (1-\pi)^2(x) - (1-\pi)(d+d')h(x) = (1-\pi)(x), \end{aligned} $$

since $\pi$ vanishes on the image of $d+d'$, which is equal to $(R)$ and $1-\pi$ is a projector.

To make the step of induction, we proceed in a similar way. To define $d'(x)$ for a word-homogeneous generator $x$ of homological degree $k+1 > 1$, we put

$$d'(x) = -(h+h')(d+d')d(x).$$

The $\Sigma$-filtered property for $d'$ now easily follows by induction. For the square-zero property, we note that

$$ \begin{aligned} (d+d')^2(x) &= (d+d')(d(x) - (h+h')(d+d')d(x)) \\ &= (d+d')d(x) - (d+d')(h+h')((d+d')d(x)) \\ &= (d+d')d(x) - (1-\pi)(d+d')d(x) = \pi((d+d')d(x)) = 0, \end{aligned} $$

since $(d+d')d(x) \in \ker(d+d')$, and since $\pi$ vanishes on the image of $d+d'$. Suppose that $x$ is word-homogeneous of grade $u$. Note that whenever $x \in \ker(d+d')$, we have $x - (d+d')h(x) \in \ker(d+d')$ as well. Since $\bar{\pi}$ vanishes on elements of positive homological degree, we have $dh(x) = (1-\bar{\pi})(x) = x$, and so, using the perturbation condition for $d'$, we see that $x - (d+d')h(x)$ is a combination of elements of grades strictly less than $u$ with respect to the ordering $\langle\Sigma\rangle$. Consequently, we may define $h'$ on elements of $\ker(d+d')$ of homological degree $k > 0$ by the same inductive argument: we put

$$h'(x) = (h+h')(x - (d+d')h(x)).$$

Once again, a simple inductive argument shows that the $\Sigma$-filtered property for the map $h'$ and the homotopy condition are satisfied.

We conclude that $(T(V), d+d')$ a differential graded algebra, with the homology $H_\bullet(T(V), d+d')$ isomorphic to $A_\Sigma$, and a $\Sigma$-filtered map $d'$, as required. It remains to check that it is triangulated. For that, we first decompose the space of generators $V$ according to the homological degree, and then for the fixed homological degree $n$, decompose $V_n$ into word-homogeneous components. Since we work with
a model of finite type, there are finitely many word-homogeneous components in each homological degree, and so once we linearly order them extending the ordering $<_{\Sigma}$, the total order on thus obtained components is either finite or isomorphic to $\mathbb{N}$. This total order gives a triangulation: by construction, the differential of each component is made of products of elements from the previous components. This completes the proof of the theorem. $\square$

# 5. Differential Graded Lie Algebras and the Diamond Lemma

In this section, we present a deformation-theoretic version of the Diamond Lemma. This corresponds to the heuristics of deformation theory going back to Deligne, Drinfeld, and Feigin (and later formalized by Lurie [65, 66] and Pridham [73]) that, infinitesimally, any moduli space of deformations in characteristic zero is controlled by a Maurer–Cartan equation in a suitable differential graded Lie algebra. We remark that while using this heuristics requires to restrict ourselves to a ground field $\mathbb{k}$ of characteristic zero, one can easily see that replacing, in Theorem 5.1, the Maurer–Cartan equation $[d+F, d+F] = 0$ by the square-zero condition $(d+F)^2 = 0$ leads to a result that is valid without any assumption on the ground field.

## 5.1. Differential graded Lie algebras

We begin with a brief recollection of differential graded Lie algebras and their Maurer–Cartan elements.

**Definition (Differential graded Lie algebra).** A differential graded Lie algebra is a pair $(L, d)$, where $L$ is a graded Lie algebra, that is a graded vector space equipped with a degree zero operation $L \otimes L \to L$, $a \otimes b \mapsto [a, b]$, called the Lie bracket, which satisfies the graded skew-symmetry property $[a, b] = -(-1)^{|a||b|}[b, a]$ for homogeneous elements $a, b \in L$ and the graded Jacobi identity

$$[a, [b, c]] = [[a, b], c] + (-1)^{|a||b|}[b, [a, c]]$$

for homogeneous elements $a, b, c \in L$, and $d: L \to L$ is a degree $-1$ map satisfying the condition $d^2 = 0$ as well as the graded derivation property

$$d[a, b] = [d(a), b] + (-1)^{|a|}[a, d(b)].$$

From the homotopical algebra point of view, one of the protagonist in the homotopy theory for differential graded Lie algebras is the set of Maurer–Cartan elements of such algebra.

**Definition.** Let $(L, d)$ be a differential graded Lie algebra over a field $\mathbb{k}$ of characteristic different from two. The condition

$$d(x) + \frac{1}{2}[x, x] = 0$$
is called the *Maurer-Cartan equation of L*, and any solution $x \in L_{-1}$ is called a *Maurer-Cartan element*.

Let L be a graded Lie algebra. Note that for an element $x \in L$ of degree $-1$ and any $a \in L$, the Jacobi identity implies

$$[x, [x, a]] = [[x, x], a] + (-1)^{|x||x|} [x, [x, a]] = [[x, x], a] - [x, [x, a]]$$

and therefore

$$[x, [x, a]] = \frac{1}{2} [[x, x], a].$$

Thus, if we suppose that $x$ satisfies the condition $[x, x] = 0$ (note that for elements of odd degree the graded antisymmetry property is actually symmetry, so this condition is non-empty), the degree $-1$ endomorphism $[x, -]$ squares to zero; the Jacobi identity implies that it also satisfies the derivation property. Thus, $(L, [x, -])$ is a differential graded Lie algebra.

## 5.2. Tangent complexes and deformations

Our Lie algebras of interest arise as Lie algebras of derivations of models of associative algebras. Suppose that $A$ is an associative algebra, and that $(B, d)$ is a model of $A$. The graded vector space $\text{Der}(B)$ of all derivations of the graded associative algebra $B$ has a natural structure of a graded Lie algebra: the graded bracket

$$[D_1, D_2] = D_1 D_2 - (-1)^{|D_1||D_2|} D_2 D_1$$

of two derivations is again a derivation. Clearly, $d \in \text{Der}(B)$ and

$$[d, d] = dd - (-1)^{|d||d|} dd = 2d^2 = 0;$$

as we saw above, the map $[d, -] : \text{Der}(B) \to \text{Der}(B)$ makes $\text{Der}(B)$ a differential graded Lie algebra. We note that in the previous section, $d$ denoted the differential of the Lie algebra, and now our context forces us to consider differential graded Lie algebras whose differentials are of the form $[d, -]$ with $d$ being an element of the algebra, the differential of the model; we hope that this does not lead to a confusion. This algebra is called the *tangent complex* associated to the model $B$. Using the work [79] of Schlessinger and Stasheff as an inspiration, Hinich showed in [39] that the homotopy type of this Lie algebra does not depend on the choice of a model.

In our context, the Maurer-Cartan heuristics of deformation theory acquires very precise meaning. Since the differential of the tangent complex of a model is of the form $[d, -]$, the Maurer-Cartan equation in that differential graded Lie algebra is equivalent to the equation $[d + x, d + x] = 0$, which in turn is equivalent to the square-zero condition for the derivation $d + x$. Thus, the Maurer-Cartan equation for the differential graded Lie algebra $(\text{Der}(B), [d, -])$ describes perturbations of the differential of $B$.
### 5.3. Perturbing solutions to the Maurer–Cartan equation

In this section, we shall prove what is essentially the Diamond Lemma in disguise. It claims that having the Maurer–Cartan equation satisfied on generators of homological degree at most two of a model is sufficient to ensure existence of a perturbation. As above, we consider a rewriting system $\Sigma = (X, W, f)$.

**Theorem 5.1.** Suppose that $(T(V), d)$ is a word-homogeneous acyclic extension of finite type of the Shafarevich complex $\mathrm{III}(W, \mathbb{k}\langle X \rangle)$. The rewriting system $\Sigma$ is convergent if and only if there exists an degree $-1$ element $F \in \mathrm{Der}(T(V))$ such that

* for each $e_w \in V_1$, we have $F(e_w) = -f(w)$,

* $F|_{V_2}$ is $\Sigma$-filtered,

* the Maurer–Cartan equation for the element $F$ holds when evaluated on generators of homological degree at most two.

**Proof.** In view of Theorem 4.1, we have to prove that finding a perturbation that only satisfies the Maurer–Cartan equation on generators of homological degree at most two is enough to ensure that there exists a perturbation that is a Maurer–Cartan element. We shall show by induction on $k$ that we can find a $\Sigma$-filtered derivation $F$ for which the Maurer–Cartan equation holds on generators of homological degree at most $k$, the basis of induction being $k = 2$.

Note that $[d + F, d + F]$ is the Lie bracket of derivations, thus itself a derivation, so since it vanishes on generators of homological degree at most $k$, it vanishes on all elements of $T(V)$ of homological degree at most $k$. Let us consider a word-homogeneous element $c \in V_{k+1}$. We note that the element

$$ \nabla(c) = \left( \partial(F) + \frac{1}{2}[F, F] \right) (c) = d(F(c)) + F(d(c)) + F(F(c)) \in T(V) $$

is in the kernel of $d + F$. Indeed, we have

$$ d(\nabla(c)) = d(d(F(c)) + F(d(c)) + F(F(c))) = (dF)((d + F)(c)) $$

and since the element $(d + F)(c)$ is of homological degree at most $k$, the Maurer–Cartan equation for $F$ holds when evaluated on that element. This means that

$$ \begin{aligned} d(\nabla(c)) &= -(Fd + F^2)((d + F)(c)) \\ &= -F(d(F(c))) - F(F(d(c))) - F(F(F(c))) = -F(\nabla(c)), \end{aligned} $$

as required. The element $\nabla(c)$ is of homological degree $k + 1 - 2 = k - 1$, and we know that the Maurer–Cartan equation means that the derivation $d + F$ squares to zero on elements of degree at most $k$. Thus, it is not unreasonable to ask whether $\nabla(c)$ is in the image of $d + F$. Let us show that it is indeed the case. We write $\nabla(c) = x + y$, where $x$ is the word-homogeneous component of maximal grade $u$.
Since the differential $d$ is word-homogeneous, and the derivation $F$ is $\Sigma$-filtered on elements of degree at most $k$, it follows that

$$ \begin{cases} d(x) = 0, \\ d(y) + F(x + y) = 0. \end{cases} $$

Since $|x| = |\nabla(c)| = k-1 \ge 1$ and the model $(T(V), d)$ is acyclic in positive degrees, it follows that we can write $x = da$ for some $a \in T(V)$. The element

$$ y - F(a) = \nabla(c) - (d + F)(a) $$

represents the same homology class for $d+F$, but its component of grade $u$ has been replaced by a combination of elements of grades strictly less than $u$ with respect to the ordering $<_{\Sigma}$. By induction with respect to the well-ordering $<_{\Sigma}$, we see that $\nabla(c)$ is a boundary of $d+F$, so we can write $\nabla(c) = (d+F)(b)$. Let us now consider a new derivation $F'$ which coincides with $F$ on elements of homological degree at most $k$, but satisfies

$$ F'(c) = F(c) - b. $$

We note that since $\nabla$ is $\Sigma$-filtered, each element $a$ above (and hence the resulting element $b$) is a linear combination of elements of grades strictly less than the grade of $c$ with respect to the ordering $<_{\Sigma}$, so $F'$ is still $\Sigma$-filtered. Moreover, since the elements $d(c)$ and $F'(c)$ are of homological degree $k$, we have

$$ \begin{aligned} & d(F'(c)) + F'(d(c)) + F'(F'(c)) \\ & = d(F(c) - b) + F(d(c)) + F(F(c) - b) = \nabla(c) - d(b) - F(b) = 0. \end{aligned} $$

Making such adjustments for all elements of homological degree $k+1$, we obtain a perturbation that satisfies the Maurer–Cartan equation up to degree $k+1$, which allows us to proceed by induction. Since the correction does not change values of $F$ on generators of low homological degrees, we may consider the limiting value of $F$; it is a bona fide Maurer–Cartan element extending the original perturbation of the differential. $\square$

### 5.4. Maurer–Cartan equation and the Diamond Lemma

In this section, we are finally rewarded for going through all the previous arguments involving models and the Maurer–Cartan equation; the reward is a general result stating that each word-homogeneous acyclic extension of $\mathrm{III}(W, \mathbb{k}\langle X\rangle)$ leads to its own Diamond Lemma criterion for convergence of $\Sigma$. At the core of such result is the following definition of an S-polynomial associated to a generator of homological degree two of such model.

**Definition (Obstruction).** Let $(T(V), d)$ be a word-homogeneous acyclic extension of the Shafarevich complex $\mathrm{III}(W, \mathbb{k}\langle X\rangle)$. For each element $c \in V_2$, the element
$d(c)$ is of degree 1, and therefore is of the form

$$d(c) = \sum_{i} a_i e_{w_i} b_i \in T(V_0) \otimes V_1 \otimes T(V_0).$$

We define the obstruction $S_c \in k\langle X\rangle$ associated to the element $c$ by the formula

$$S_c = \sum_{i} a_i f(w_i) b_i.$$

We remark that our usage of the term “obstruction” is different from that of Anick in [3]: for us, as it will become apparent below, $S_c$ is an actual obstruction to convergence of $\Sigma$.

We are now ready to state and prove our model-specific Diamond Lemma. As above, we consider a rewriting system $\Sigma = (X, W, f)$.

**Theorem 5.2.** Suppose that $(T(V), d)$ is a word-homogeneous acyclic extension of finite type of the Shafarevich complex $\Pi(W, k\langle X\rangle)$. The rewriting system $\Sigma$ is convergent if and only if for each word-homogeneous element $c \in V_2$, the corresponding obstruction $S_c$ is mapped to zero by some reduction with respect to $\Sigma$.

**Proof.** According to Theorem 5.1, $\Sigma$ is convergent if and only if there exists a degree $-1$ element $F \in \text{Der}(T(V))$ such that

* for each $e_w \subset V_1$, we have $(d + F)(e_w) = w - f(w)$,

* $F|_{V_2}$ is $\Sigma$-filtered,

* the Maurer–Cartan condition $[d + F, d + F] = 0$ for the element $F$ holds when evaluated on generators of homological degree at most two.

Since the Maurer–Cartan equation evaluated on an element of homological degree $k$ is an element of homological degree $k - 2$, we may replace “at most two” by “exactly two” without changing the statement.

Suppose $c \in V_2$ is word-homogeneous of grade $u$. We note that the formula

$$S_c = \sum_{i} a_i f(w_i) b_i$$

for the obstruction $S_c$ means that $S_c$ is a combination of terms of grade less than $u$, so existence of its reduction equal to zero is clearly equivalent to existence of a representation of $S_c$ as a two-sided linear combination

$$S_c = \sum_{i} a'_i(w'_i - f(w'_i))b'_i,$$

where all the terms in that sum are of grade less than $u$. Indeed, a sequence of basic reductions produces such a combination, and *vice versa*, the existence of each such combination immediately suggests a sequence of basic reductions.
Recall that the Maurer–Cartan equation for $F$ is exactly the square-zero condition for $d + F$. Let us evaluate it on an element $c \in V_2$ of grade $u$. We obtain

$$d(d(c)) + F(d(c)) + d(F(c)) + F(F(c)) = 0.$$

We already remarked that the element $d(c) \in T(V)$ is of homological degree one, and therefore can be written as

$$d(c) = \sum_{i} a_{i}e_{w_{i}}b_{i} \in T(V_{0}) \otimes V_{1} \otimes T(V_{0}).$$

The first term in the square-zero condition vanishes, while the second is

$$F(d(c)) = F\left(\sum_{i} a_{i}e_{w_{i}}b_{i}\right) = \sum_{i} a_{i}F(e_{w_{i}})b_{i} = -\sum_{i} a_{i}f(w_{i})b_{i} = -S_{c}.$$

The remaining terms in the square-zero condition are

$$d(F(c)) + F(F(c)) = (d + F)(F(c)).$$

Since $F|_{V_2}$ is $\Sigma$-filtered, the element $F(c)$ is of the form $\sum_{i} a'_{i}e_{w'_{i}}b'_{i}$, where all the terms in the sum are of grades less than $u$. Finally, we obtain

$$d(F(c)) + F(F(c)) = (d + F)\left(\sum_{i} a'_{i}e_{w'_{i}}b'_{i}\right) = \sum_{i} a'_{i}(w'_{i} - f(w'_{i}))b'_{i}.$$

We conclude that the validity of the Maurer–Cartan equation on $c \in V_2$ of grade $u$ is equivalent to the equation

$$S_c = \sum_{i} a'_{i}(w'_{i} - f(w'_{i}))b'_{i},$$

where all the terms in that sum are of grade less than $u$, which, according to our observation above, completes the proof. □

# 6. Examples: Specific Cases of Models and Their Diamond Lemmas

In this section, we discuss two particular examples of models of monomial algebras that allow us to recover the Diamond Lemma and the Triangle Lemma for classical term rewriting.

## 6.1. The inclusion-exclusion model

In [26], the first author and Khoroshkin constructed a combinatorial (usually non-minimal) model for a shuffle operad with monomial relations; specializing to shuffle operads generated by elements of parity 1, one obtains a model for an associative algebra with monomial relations. For the benefit of the reader who does not wish to go through the operad construction, we describe that model here. As above, we denote $A_{\Sigma_0} = \mathbb{k}\langle X | W \rangle$.
Let $u \in \langle X \rangle$. Suppose that there are exactly $m$ different occurrences of elements of $W$ in the word $u$ (as above, we refer to such occurrences as divisors). We introduce formal symbols $D_{u,1}, \dots, D_{u,m}$ in one-to-one correspondence with those divisors, and denote by $A_u$ the Grassmann algebra $\Lambda(D_{u,1}, \dots, D_{u,m})$. The direct sum

$$A_W := \bigoplus_{u \in \langle X \rangle} A_u$$

has an associative algebra structure defined as follows. For an element $u' \in \langle X \rangle$ which is a divisor of $u$, there is a natural inclusion $A_{u'} \hookrightarrow A_u$ sending each generator $D_{u',i}$ to the corresponding $D_{u,j}$, where $j$ is the position of the $i$th divisor of $u'$ (viewed now as a divisor of $u$) in the list of divisors of $u$. The product of two elements $a_1 \in A_{u_1}$ and $a_2 \in A_{u_2}$ is the product in $A_{u_1 u_2}$ of their images with respect to the inclusions $A_{u_1}, A_{u_2} \hookrightarrow A_{u_1 u_2}$. If we set the homological degree of each $D_{u,i}$ to be equal to one, the algebra $A_W$ is graded. Moreover, it has a differential graded algebra structure, where the differential $d$, when restricted to each Grassmann algebra $A_u$, is the unique derivation of that algebra sending all generators $D_{u,i}$ to $1$.

Let us call a Grassmann monomial $D_{u,i_1} \wedge \dots \wedge D_{u,i_k} \in A_u$ indecomposable if there does not exist a factorization $u = u_1 u_2$ into a product of two non-empty monomials $u_1$ and $u_2$ for which each of the divisors of $u$ corresponding to $S_{u,i_p}$ is either a divisor of $u_1$ or a divisor of $u_2$. It is easy to see that as an associative algebra, the algebra $A_W$ is freely generated by its indecomposable elements. Moreover, according to [26, Theorem 2.2], the differential graded algebra $(A_W, d)$ is a model of the algebra $A_{\Sigma_0}$. We call this model the inclusion-exclusion model. It is immediately seen to be a word-homogeneous acyclic extension of finite type of the Shafarevich complex III($W$, $\mathbb{k}\langle X \rangle$). Moreover, all homological degree two word-homogeneous generators $c$ of that model of grade $u \in \langle X \rangle$ are of two possible forms:

* inclusion: $c = S_{u,i} \wedge S_{u,j}$, where the $i$th divisor of $u$ is its proper divisor $u'$ and the $j$th divisor of $u$ is equal to $u$,

* overlap: $c = S_{u,i} \wedge S_{u,j}$, where the $i$th divisor of $u$ is a left divisor $u'$ of $u$, the $j$th divisor of $u$ is a right divisor $u''$ of $u$, and these two subwords have a nontrivial common divisor.

For each generator of the first type, we have $u = au'b$ for some $a, b \in \langle X \rangle$, therefore such generators are in one-to-one correspondence with the inclusion ambiguities of [11]. We note that for such generator, we have

$$d(c) = e_u - ae_{u'}b$$

and the obstruction associated to this generator is the basic reduction associated to the triple $(a, u', b)$ applied to the relation $u - f(u)$. Similarly, for each generator of the second type, we have $u = u'a = bu''$ for some $a, b \in \langle X \rangle$, therefore such generators are in one-to-one correspondence with the overlap ambiguities of op. cit.
Moreover, for such generator, we have

$$d(c) = be_{u''} - e_{u'}a$$

and the obstruction associated to this generators is the element usually called the S-polynomial corresponding to the overlap of $u'$ and $u''$ [20] (the term “composition” of Shirshov [84] and Bokut [12] is a bit too ambiguous in many situations, and we choose to avoid it). This proves the following result.

**Proposition 6.1 (Bergman’s Diamond Lemma [11, Theorem 1.2]).** The rewriting system $\Sigma$ is convergent if and only if each basic reduction of each relation from $R$ and each S-polynomial between two relations from $R$ is mapped to zero by some reduction with respect to $\Sigma$.

As an immediate consequence, we see that the rewriting system

$$xyz \mapsto x^3 + y^3 + z^3$$

on $\mathbb{K}\langle x, y, z \rangle$ discussed in Sec. 2 is convergent, since we already established its termination, and the word $xyz$ does not have self-overlaps.

## 6.2. The minimal model

In [85], the second author constructed, for each monomial algebra $A_{\Sigma_0} = \mathbb{K}\langle X | W \rangle$, the minimal model which we shall now recall and use. We shall assume the rewriting system $\Sigma$ minimal: $W$ contains no words of length one and no words from $W$ divide one another. We begin with recalling the definition of (right) *Anick chains*, a notion that was to some extent present implicitly in work of Backelin [4], then used by Green et al. [33], and became known to a wider community from the work of Anick [3].

**Definition (Anick chain).** We say that a 0-chain is an element $x \in X$, and define the tail of such element to be equal to it. For $n > 0$, we say that an $n$-chain is a monomial $c \in \langle X \rangle$ such that

(1) we can write $c = c't$, where $c'$ is an $(n-1)$-chain,

(2) if $t'$ is the tail of $c'$, then $t't$ has a right divisor which is a relation from $W$,

(3) no proper left divisor of $c$ satisfies the first two conditions.

The tail of $c$ is the element $t_c := t$.

In particular, the 1-chains are the defining relations $W$, with the tail of each monomial relation given by the monomial obtained by deleting its first letter, and the 2-chains are precisely the monomials $c \in \langle X \rangle$ which can be written as $c = u'a = bu''$ for two relations $u', u'' \in W$, and which do not have other divisors from $W$.

It is shown in [3] that a monomial $c$ admits at most one structure of a chain: if $c$ is an $n$-chain with tail $t_c$, then both $n$ and $t_c$ are uniquely determined. We define the homological degree of an $n$-chain $c$ to be equal to $n$, and consider the graded
associative algebra $B$ freely generated by Anick chains. This algebra has a unique derivation $d$ whose value $d(c)$ on an $n$-chain $c$ is the sum over all ways to represent $c$, viewed as a monomial, as a concatenation of an $n_1$-chains $c_1, \dots, n_k$-chain $c_k$ with $n_1 + \dots + n_k = n - 1$, of the terms

$$ -(1)^{\binom{n+1}{2}+n_1} c_1 \otimes \dots \otimes c_k. $$

The main theorem of [85] states that for a minimal rewriting system $\Sigma$, the quasi-free algebra $(B, d)$ is the minimal model of $A_{\Sigma_0}$. It is a word-homogeneous acyclic extension of finite type of the Shafarevich complex $\text{III}(W, \mathbb{k}\langle X\rangle)$.

The description of Anick 2-chains mentioned above indicates that they are among the overlaps from the previous section; in fact, they are minimal overlaps that have only two divisors from $W$. For the differential of the model, we have $d(c) = be_{u''} - e_{u'}a$, as before. This proves the following result.

**Proposition 6.2 (Triangle Lemma [20, Sec. 2.4.3]).** A minimal rewriting system $\Sigma$ is convergent if and only if each S-polynomial corresponding to a minimal overlap is mapped to zero by some reduction with respect to $\Sigma$.

For example, for the rewriting system $x^3 \mapsto xyz - y^3 - z^3$ arising in the example discussed in Sec. 2 for a total multiplicative ordering, the monomial $x^3$ has two self-overlaps, $x^4 = x^3 \cdot x = x \cdot x^3$ and $x^5 = x^3 \cdot x^2 = x^2 \cdot x^3$. Only the first of them is minimal. This means that there is no need to consider the S-polynomial corresponding to the overlap $x^5$ when checking the Diamond Lemma criterion. That said, in this case already the S-polynomial corresponding to the overlap $x^4$ cannot be reduced to zero, so the rewriting system is not convergent, as we indicated when discussing that example.

# 7. Analogues and Generalizations

In words of Kontsevich and Soibelman [51], “the deformation theory of associative algebras is a guide for developing the deformation theory of many algebraic structures; conversely, all the concepts of what should be the “deformation theory of everything” must be tested in the case of associative algebras”. We believe that our work constitutes a successful test of putting the Diamond Lemma in the homotopical context, and it is natural to conclude this paper with a discussion of analogues and possible generalizations of our results.

## 7.1. Multiplicative algebraic structures

We begin with outlining a context in which an immediate generalization of our approach is available.

**Definition (Multiplicative algebraic structure).** We say that an algebraic structure $P$ is multiplicative if it is described by a colored operad obtained as a $\mathbb{k}$-linear span of a set-theoretic operad. In classical terms, we require that the free
k-linear P-algebra generated by a vector space V is equal to the k-linear span of
the free P-algebra in the category of sets generated by a basis of V.

The key consequence of this definition is that free k-linear P-algebras are naturally equipped with monomial bases, so one can talk about rewriting systems and orderings of monomials, and most of our results apply *mutatis mutandis* if one can talk about models of algebras in the same way as above. Work of Hinich [39] mentioned earlier allows one to verify that condition easily enough.

Some remarks are in order. First, talking about colored operads means that this formalism includes, for instance, quotients of path algebras, since the latter are obtained as k-linear spans of small categories and are not just algebras in a very classical sense. Second, there are situations where the deviation from the set-theoretic property is “moderate”, i.e. the value of any structure operation on basis elements is a basis element up to a nonzero constant; it is easy to extend our work to such algebras. Finally, it is also possible to include algebras that are complete in a suitable sense; we already indicated in the introduction that complete commutative associative algebras were one of the central examples at the moment of inception of both topics discussed in this paper, through the theory of standard bases of Hironaka [41, Sec. III.1] and the deformation theory of analytic spaces of Palamodov [71].

### 7.1.1. *Commutative associative algebras*

The free commutative associative algebra coincides with the linear span of the free commutative monoid, and the homotopy theory for commutative associative algebras suggests that our results work over a field of characteristic zero. An analogue of the inclusion-exclusion model exists, and generators of homological degree at most two of the minimal model of a given monomial algebra can be determined directly (for further information, we refer the reader to [9]). If the partial order $<_{\Sigma}$ comes from a total multiplicative order of monomials, the result corresponding to the inclusion-exclusion model is the Buchberger criterion [22], and the result corresponding to the minimal model is known as the Chain Criterion [21, 50].

### 7.1.2. *Non-associative algebras*

If one considers free non-associative algebras, better known as magmatic algebras for one binary operation and as absolutely free algebras in the more general case, the free algebra is the linear span of the free set-theoretic magma (consisting of appropriate decorated planar trees), and models are surprisingly manageable. In particular, the inclusion-exclusion model of a given monomial algebra is readily available, and the minimal model for a monomial algebra whose set of generators and relations are already chosen minimal is simply the non-associative Shafarevich complex, since there are no non-associative overlaps. As a consequence, for a general rewriting system convergence is equivalent to the fact that all basic reductions
between the relations $R$ are mapped to zero by some reduction with respect to $\Sigma$, and in particular, a rewriting system where pairwise reductions are impossible is convergent. This result goes back to [89], see also [18, Appendix 3] and a more recent paper [29].

### 7.1.3. Shuffle algebras

Shuffle algebras [27, 78], known also as permutads [64], are associative algebras for the monoidal category of non-symmetric sequences with respect to the monoidal structure given by Cauchy tensor product. The corresponding definition is also available for sets; elements of the free monoid are decorated permutations and their suitable generalizations. All results of this paper, including a generalization of the inclusion-exclusion model and the second author's minimal model, can be adapted; the corresponding results are the Diamond Lemma for shuffle algebras [20, Theorem 4.5.1.4] and the Triangle Lemma for shuffle algebras [20, Proposition 4.5.3.2].

### 7.1.4. Non-symmetric operads and shuffle operads

When one considers operads, whether non-symmetric or shuffle ones, each free operad is the linear span of the corresponding free set operad consisting of appropriate decorated planar trees. It is important to note that the algebraic structure on the space of decorated trees in this case is much richer than the one considered in the case of magmatic algebras above, so the corresponding Diamond Lemmas (and especially their applications) are sufficiently nontrivial. Models are once again available under relatively mild assumptions [68]. In particular, the inclusion-exclusion model can be defined for every shuffle operad with monomial relations [26, Sec. 2]. This way one obtains the Diamond Lemma for non-symmetric operads and for shuffle operads [20].

Finding an explicit description of the minimal model of the given operad with monomial relations is an open problem. Partial results in the spirit of the Triangle Lemma are available for operads [20], but even in homological degree two, the computation of the spaces of generators of minimal models of monomial operads still has to be completed in full generality. One calculation hinting at the noticeable complexity of this question was made by Sköldberg several years ago (unpublished), and we shall now describe the result of that calculation; another discussion of that phenomenon can be found in the recent preprint of Iyudu and Vlassopoulos [45].

The minimal model of a monomial operad is homogeneous: one can separate generators according to their underlying tree monomials. In the case of associative algebras, minimal models of monomial algebras satisfy the homological purity condition: for each monomial, the corresponding component of the space of generators is concentrated in one homological degree. Somewhat surprisingly, it turns out that in the case of operads, this homological purity condition does not hold for some underlying tree monomials. The simplest possible example arises in the case of the
free non-symmetric operad generated by one binary operation, and the set of monomial relations $W$ consisting of all tree monomials of arity four in that operad. Then for the tree monomial

<figure><img src="image_2.png" /></figure>

of arity seven, as well as the monomials obtained from it by reflections at internal vertices, the corresponding component of the space generators of the minimal model is two-dimensional, with one generator in degree three and one generator in degree four. This example is a particular case of the remarkable construction from the very recent preprint of Qi et al. [74, Sec. 5]: it is the “operadization” of the algebra $\mathbb{k}\langle x, y \rangle/m^2$. We remark that this exhibits a rather interesting feature of the operadization: it converts a Koszul monomial algebra to an operad whose homotopy invariants are highly nontrivial. For that reason, we feel that explicitly computing minimal models for monomial operads obtained by that construction is likely to exhibit some of the most interesting phenomena behind minimal models of general monomial operads.

## 7.2. Non-multiplicative algebraic structures

For an algebraic structure that is not multiplicative, our approach does not adapt immediately. Upon examining the existing literature on Gröbner–Shirshov bases, see, for example, [13–15] and references therein, we feel that the most obvious way to deal with a non-multiplicative algebraic structure is to embed it into a bigger multiplicative one. For example, Lie algebras can be embedded in their universal envelopes, and so one can work with a rewriting system within a multiplicative algebraic structure. Equivalence of the associative algebra methods applied to the universal envelopes and the Lie-algebraic methods of Shirshov was established by Bokut and Malcolmson [19]. Alternatively, a Lie algebra can be regarded as an anti-commutative magmatic algebra; the corresponding study of Gröbner–Shirshov bases was undertaken in [17]. Recent papers on Gröbner–Shirshov bases for pre-Lie algebras [16], Novikov algebras [87], and Sabinin algebras [63] follow the same logic. This raises a question of computing not only models of monomial algebras for multiplicative algebraic structures, but also models of meaningful classes of algebras obtained when extending non-multiplicative structures to multiplicative ones. We hope to address this in more detail elsewhere.

## Acknowledgments

The authors thank Leonid Arkadievich Bokut, Eric Hoffbeck, Anton Khoroshkin and Muriel Livernet for useful discussions. The first author also thanks Dmitri
Piontkovski who introduced him to Shafarevich complexes many years ago, and Emil Sköldberg for sharing some computations of minimal models of monomial operads in low homological degrees. The idea of this paper emerged during the workshop “Homotopy meets homology” at Hamilton Mathematics Institute (Trinity College Dublin) in May 2019, and was primarily guided by our wish to unveil homotopical algebra behind the work [77] presented at that workshop by María Julia Redondo; we are grateful to the Science Foundation Ireland and the Simons Foundation for allocating funding that made that workshop possible. Part of this work was done during the second author’s visits to Strasbourg funded by IRMA (Institut de Recherche Mathématique Avancée), he is thankful for both the financial support of those visits and the excellent working conditions.

ORCID

Vladimir Dotsenko https://orcid.org/0000-0002-6949-5166

Pedro Tamaroff https://orcid.org/0000-0002-2047-5615

References

[1] D. J. Anick, A counterexample to a conjecture of Serre, *Ann. of Math.* (2) **115**(1) (1982) 1–33.

[2] D. J. Anick, Noncommutative graded algebras and their Hilbert series, *J. Algebra* **78**(1) (1982) 120–140.

[3] D. J. Anick, On the homology of associative algebras, *Trans. Amer. Math. Soc.* **296**(2) (1986) 641–659.

[4] J. Backelin, La série de Poincaré-Betti d'une algèbre graduée de type fini à une relation est rationnelle, *C. R. Acad. Sci. Paris Sér. A-B* **287**(13) (1978) A843–A846.

[5] M. J. Bardzell, Resolutions and cohomology of finite dimensional algebras, Ph.D. thesis, Virginia Polytechnic Institute and State University (1996), iv+65 pp.

[6] M. J. Bardzell, Noncommutative Gröbner bases and Hochschild cohomology, in *Sym- bolic Computation: Solving Equations in Algebra, Geometry, and Engineering (South Hadley, MA, 2000)*, Contemporary Mathematics, Vol. 286 (American Mathematical Society, Providence, RI, 2001), pp. 227–240.

[7] S. Barmeier and Z. Wang, Deformations of path algebras of quivers with relations, preprint (2020), arXiv:2002.10001.

[8] H. J. Baues and J.-M. Lemaire, Minimal models in homotopy theory, *Math. Ann.* **225**(3) (1977) 219–242.

[9] A. Berglund, Poincaré series of monomial rings, *J. Algebra* **295**(1) (2006) 211–230.

[10] A. Berglund, Homological perturbation theory for algebras over operads, *Algebr. Geom. Topol.* **14**(5) (2014) 2511–2548.

[11] G. M. Bergman, The diamond lemma for ring theory, *Adv. Math.* **29**(2) (1978) 178–218.

[12] L. A. Bokut, Imbeddings into simple associative algebras, *Algebra Logika* **15**(2) (1976) 117–142, 245.

[13] L. A. Bokut and Y. Chen, Gröbner-Shirshov bases for Lie algebras: After A. I. Shir- shov, *Southeast Asian Bull. Math.* **31**(6) (2007) 1057–1076.

[14] L. A. Bokut and Y. Chen, Gröbner-Shirshov bases and their calculation, *Bull. Math. Sci.* **4**(3) (2014) 325–395.
[15] L. A. Bokut and Y. Chen, Gröbner-Shirshov bases for universal algebras, *J. South China Normal Univ. Natur. Sci. Ed.* **46**(6) (2014) 1–9.

[16] L. A. Bokut, Y. Chen and Y. Li, Gröbner-Shirshov bases Vinberg-Koszul-Gerstenhaber for right-symmetric algebras, *Fundam. Prikl. Mat.* **14**(8) (2008) 55–67.

[17] L. A. Bokut, Y. Chen and Y. Li, Anti-commutative Gröbner-Shirshov basis of a free Lie algebra, *Sci. China Ser. A* **52**(2) (2009) 244–253.

[18] L. A. Bokut and G. P. Kukin, *Algorithmic and Combinatorial Algebra*, Mathematics and its Applications, Vol. 255 (Kluwer Academic Publishers Group, Dordrecht, 1994).

[19] L. A. Bokut and P. Malcolmson, Gröbner-Shirshov bases for relations of a Lie algebra and its enveloping algebra, in *Algebras and Combinatorics (Hong Kong, 1997)* (Springer, Singapore, 1999), pp. 47–54.

[20] M. R. Bremner and V. Dotsenko, *Algebraic Operads: An Algorithmic Companion* (CRC Press, Boca Raton, FL, 2016).

[21] B. Buchberger, A criterion for detecting unnecessary reductions in the construction of Gröbner-bases, in *Symbolic and Algebraic Computation (EUROSAM '79, Int. Symp., Marseille, 1979)*, Lecture Notes in Computer Science, Vol. 72 (Springer, Berlin, 1979), pp. 3–21.

[22] B. Buchberger, An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal, *J. Symb. Comput.* **41**(3–4) (2006) 475–511, Translated from the 1965 German original by Michael P. Abramson.

[23] S. Chouhy and A. Solotar, Projective resolutions of associative algebras and ambiguities, *J. Algebra* **432**(2015) 22–61.

[24] A. Church and J. B. Rosser, Some properties of conversion, *Trans. Amer. Math. Soc.* **39**(3) (1936) 472–482.

[25] M. G. Citterio, Classifying spaces of categories and term rewriting, *Theory Appl. Categ.* **9** (2001/2002) 92–105.

[26] V. Dotsenko and A. Khoroshkin, Quillen homology for operads via Gröbner bases, *Doc. Math.* **18** (2013) 707–747.

[27] V. Dotsenko and A. Khoroshkin, Shuffle algebras, homology, and consecutive pattern avoidance, *Algebra Number Theory* **7**(3) (2013) 673–700.

[28] C. Eder, Predicting zero reductions in gröbner basis computations, in *Proc. 2014 Symp. Symbolic-Numeric Computation* (Association for Computing Machinery, New York, 2014), pp. 109–110.

[29] L. Gerritzen, Tree polynomials and non-associative Gröbner bases, *J. Symb. Comput.* **41**(3–4) (2006) 297–316.

[30] E. S. Golod, Standard bases and homology, in *Algebra — Some Current Trends (Varna, 1986)*, Lecture Notes in Mathematics, Vol. 1352 (Springer, Berlin, 1988), pp. 88–95.

[31] E. S. Golod, On the homology algebra of the Shafarevich complex of a free algebra, *Fundam. Prikl. Mat.* **5**(1) (1999) 97–100.

[32] E. S. Golod and I. R. Šafarevič, On the class field tower, *Izv. Akad. Nauk SSSR Ser. Mat.* **28** (1964) 261–272.

[33] E. L. Green, D. Happel and D. Zacharia, Projective resolutions over Artin algebras with zero relations, *Illinois J. Math.* **29**(1) (1985) 180–190.

[34] L. Guetta, Homology of categories via polygraphic resolutions, preprint (2020), arXiv:2003.10734.

[35] V. K. A. M. Gugenheim and L. A. Lambe, Perturbation theory in differential homological algebra. I, *Illinois J. Math.* **33**(4) (1989) 566–582.

[36] V. K. A. M. Gugenheim, L. A. Lambe and J. D. Stasheff, Perturbation theory in differential homological algebra. II, *Illinois J. Math.* **35**(3) (1991) 357–373.
[37] V. K. A. M. Gugenheim and J. D. Stasheff, On perturbations and $A_\infty$-structures, *Bull. Soc. Math. Belg. Sér. A* **38** (1986) 237–246.

[38] Y. Guiraud, E. Hoffbeck and P. Malbos, Convergent presentations and polygraphic resolutions of associative algebras, *Math. Z.* **293**(1–2) (2019) 113–179.

[39] V. Hinich, Homological algebra of homotopy algebras, *Commun. Algebra* **25**(10) (1997) 3291–3323.

[40] H. Hironaka, On resolution of singularities (characteristic zero), in *Proc. Int. Congr. Mathematicians (Stockholm, 1962)* (Institut Mittag-Leffler, Djursholm, 1963), pp. 507–521.

[41] H. Hironaka, Resolution of singularities of an algebraic variety over a field of characteristic zero. I, II, *Ann. of Math.* (2) **79** (1964) 109–203; ibid. (2), **79** (1964) 205–326.

[42] M. Hovey, *Model Categories*, Mathematical Surveys and Monographs, Vol. 63 (American Mathematical Society, Providence, RI, 1999).

[43] P. Hu, Transfinite spectral sequences, in *Homotopy Invariant Algebraic Structures (Baltimore, MD, 1998)*, Contemporary Mathematics, Vol. 239 (American Mathematical Society, Providence, RI, 1999), pp. 197–216.

[44] J. Huebschmann and T. Kadeishvili, Small models for chain algebras, *Math. Z.* **207**(2) (1991) 245–280.

[45] N. Iyudu and I. Vlassopoulos, Homologies of monomial operads and algebras, preprint (2020), arXiv:2008.00985.

[46] J. F. Jardine, A closed model structure for differential graded algebras, in *Cyclic Cohomology and Noncommutative Geometry (Waterloo, ON, 1995)*, Fields Institute Communications, Vol. 17 (American Mathematical Society, Providence, RI, 1997), pp. 55–58.

[47] T. Józefiak, Tate resolutions for commutative graded algebras, *Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys.* **17** (1969) 617–621.

[48] B. Keller, Notes on minimal models (2003), https://webusers.imj-prg.fr/~bernhard.keller/publ/minmod.pdf.

[49] D. E. Knuth and P. B. Bendix, Simple word problems in universal algebras, in *Computational Problems in Abstract Algebra* (Proc. Conf., Oxford, 1967) (Pergamon, Oxford, 1970), pp. 263–297.

[50] C. Kollreider and B. Buchberger, An improved algorithmic construction of Gröbner-bases for polynomial ideals, *SIGSAM Bull.* **12**(2) (1978) 27–36.

[51] M. Kontsevich and Y. Soibelman, Deformations of algebras over operads and the Deligne conjecture, in *Conf. Moshé Flato 1999, Vol. I (Dijon)*, Mathematical Physics Studies, Vol. 21 (Kluwer Academic Publishers, Dordrecht, 2000), pp. 255–307.

[52] Y. Lafont, A new finiteness condition for monoids presented by complete rewriting systems (after Craig C. Squier), *J. Pure Appl. Algebra* **98**(3) (1995) 229–244.

[53] Y. Lafont and F. Métayer, Polygraphic resolutions and homology of monoids, *J. Pure Appl. Algebra* **213**(6) (2009) 947–968.

[54] Y. Lafont and A. Prouté, Church-Rosser property and homology of monoids, *Math. Struct. Comput. Sci.* **1**(3) (1991) 297–326.

[55] L. A. Lambe, Homological perturbation theory, Hochschild homology, and formal groups, in *Deformation Theory and Quantum Groups with Applications to Mathematical Physics* (Amherst, MA, 1990), Contemporary Mathematics, Vol. 134 (American Mathematical Society, Providence, RI, 1992), pp. 183–218.

[56] V. N. Latyshev, *Combinatorial Ring Theory, Standard Bases* (Izdatel'stvo Moskovskogo Gosudarstvennogo Universiteta, 1988).

[57] V. N. Latyshev, General version of standard bases in linear structures, in *Algebra (Moscow, 1998)*, (de Gruyter, Berlin, 2000), pp. 215–226.
[58] V. N. Latyshev, A general version of standard basis and its application to T-ideals, *Acta Appl. Math.* **85**(1-3) (2005) 219-223.

[59] V. N. Latyshev, A general version of a standard basis in associative algebras and their derivative constructions, *Fundam. Prikl. Mat.* **15**(3) (2009) 183-203.

[60] V. N. Latyšev, Algebras with identical relations, *Dokl. Akad. Nauk SSSR* **146** (1962) 1003-1006.

[61] V. N. Latyšev, On the choice of basis in a T-ideal, *Sibirsk. Mat. Zh.* **4** (1963) 1122-1127.

[62] J.-M. Lemaire, “Autopsie d’un meurtre” dans l’homologie d’une algèbre de chaînes, *Ann. Sci. Éc. Norm. Supér.* **(4)** **11**(1) (1978) 93-100.

[63] Y. Li, Q. Mo and L. A. Bokut, Generalized anti-commutative Gröbner-Shirshov basis theory and free Sabinin algebras, *Commun. Algebra* **48**(12) (2020) 5086-5109.

[64] J.-L. Loday and M. Ronco, Permutads, *J. Comb. Theory Ser. A* **120**(2) (2013) 340-365.

[65] J. Lurie, Moduli problems for ring spectra, in *Proc. Int. Congr. Mathematicians. Volume II* (Hindustan Book Agency, New Delhi, 2010), pp. 1099-1125.

[66] J. Lurie, Derived algebraic geometry X: Formal moduli problems (2011), https://www.math.ias.edu/~lurie/papers/DAG-X.pdf.

[67] M. Manetti, Differential graded Lie algebras and formal deformation theory, in *Algebraic Geometry — Seattle 2005. Part 2*, Proceedings of Symposia in Pure Mathematics, Vol. 80 (American Mathematical Society, Providence, RI, 2009), pp. 785-810.

[68] M. Markl, Models for operads, *Commun. Algebra* **24**(4) (1996) 1471-1500.

[69] F. Métayer, Resolutions by polygraphs, *Theory Appl. Categ.* **11**(7) (2003) 148-184.

[70] M. H. A. Newman, On theories with a combinatorial definition of “equivalence”, *Ann. of Math.* **(2)** **43** (1942) 223-243.

[71] V. P. Palamodov, Deformations of complex spaces, *Uspehi Mat. Nauk* **31**(3) (1976) 129-194.

[72] S. B. Priddy, Koszul resolutions, *Trans. Amer. Math. Soc.* **152** (1970) 39-60.

[73] J. P. Pridham, Unifying derived deformation theories, *Adv. Math.* **224**(3) (2010) 772-826.

[74] Z. Qi, Y. Xu, J. J. Zhang and X. Zhao, Growth of nonsymmetric operads, preprint (2020), arXiv:2010.12172.

[75] D. G. Quillen, *Homotopical Algebra*, Lecture Notes in Mathematics, Vol. 43 (Springer-Verlag, Berlin, 1967).

[76] S. Rahmati, Theory of spectral sequences of exact couples: Applications to countably and transfinitely filtered modules, Ph.D thesis, University of Alberta (Canada) (2013), xi+209 pp.

[77] M. J. Redondo and F. R. Bertone, $L_\infty$-structure on Bardzell's complex for monomial algebras, preprint (2020), arXiv:2008.08122.

[78] M. Ronco, Shuffle bialgebras, *Ann. Inst. Fourier (Grenoble)* **61**(3) (2011) 799-850.

[79] M. Schlessinger and J. Stasheff, The Lie algebra structure of tangent cohomology and deformation theory, *J. Pure Appl. Algebra* **38**(2-3) (1985) 313-322.

[80] M. Schlessinger and J. Stasheff, Deformation theory and rational homotopy type, preprint (2012), arXiv:1211.1647.

[81] W. Specht, Gesetze in Ringen. I, *Math. Z.* **52** (1950) 557-589.

[82] C. C. Squier, Word problems and a homological finiteness condition for monoids, *J. Pure Appl. Algebra* **49**(1-2) (1987) 201-217.

[83] D. Sullivan, Infinitesimal computations in topology, *Publ. Math. Inst. Hautes Études Sci.* **47** (1978) 269-331.
V. Dotsenko & P. Tamaroff

[84] A. I. Širšov, Some algorithm problems for Lie algebras, *Sibirsk. Mat. Zh.* **3** (1962) 292–296.

[85] P. Tamaroff, Minimal models for monomial algebras, to appear in *Homology Homotopy Appl.* **23**(1) (2021) 341–366.

[86] J. Tate, Homology of Noetherian rings and local rings, *Illinois J. Math.* **1** (1957) 14–27.

[87] R. Tuniyaz, L. A. Bokut, M. Xiryazidin and A. Obul, Gröbner-Shirshov bases for free Gelfand-Dorfman-Novokov algebras and for right ideals of free right Leibniz algebras, *Commun. Algebra* **46**(10) (2018) 4392–4402.

[88] V. A. Ufnarovskij, Combinatorial and asymptotic methods in algebra, in *Algebra, VI, Encyclopaedia of Mathematical Sciences*, Vol. 57 (Springer, Berlin, 1995), pp. 1–196.

[89] A. I. Žukov, Reduced systems of defining relations in non-associative algebras, *Mat. Sb. (N.S.)* **27**(69) (1950) 267–280.