Quotients of the magmatic operad: lattice structures and convergent rewrite systems. (English) Zbl 1480.18018

Informally, a nonsymmetric operad in the category of sets is a family of sets \({\mathcal O} (n)\), \(n\geq 0\), whose elements should be thought of as functions \(X^n \to X\). The magmatic operad \(Mag\) consists of the sets \(Mag(n)\), each element of which is obtained by placing brackets in an expression consisting of \(n\)-fold executions of the binary operation \(*\). The paper is devoted to quotients of the magmatic operad.
A nonsymmetric operad (or simply operad) in the category of sets consists of a graded set \({\mathcal O}= \coprod_{n\geq 0} {\mathcal O}(n)\), a distinguished unit element \(1\in {\mathcal O}(1)\) , and partial composition mappings \(\circ_i: {\mathcal O}(n)\times {\mathcal O}(m)\to {\mathcal O}(n+m-1)\) for \(1\leq i\leq n\), \(m\geq 1\). Partial composition can be thought of as a mapping that associates to \(x: X^n\to X\) and \(y: X^m\to X\) a function defined as \[ (x\circ_i y) (t_1, \cdots, t_{n+m-1}) = x(t_1, \cdots, t_{i-1}, y(t_i, \cdots, t_{i+m-1}), t_{i+m}, \cdots, t_{n+m-1}). \] This brings us to the following three axioms for mappings \(\circ_i\) and for the unit element where \(x\in {\mathcal O}(n), y\in {\mathcal O}(m)\), and \(z\in {\mathcal O}\): \begin{gather*} (x\circ_i y)\circ_{i+j-1} z = x\circ_i (y\circ_j z ), \quad 1\leq i \leq n, \quad 1\leq j \leq m,\\ (x\circ_i y)\circ_{j+m-1} z = (x\circ_j z)\circ_i y, \quad 1\leq i < j \leq n, \\ 1\circ_1 x = x = x\circ_i 1, \quad 1\leq i \leq n. \end{gather*}
If all \({\mathcal O}(n)\) are finite, then the Hilbert series defined by \({\mathcal H}_{{\mathcal O}}(t):= \sum\limits_{n\geq 1}{\mathcal O}(n)t^n\).
The magmatic operad \(Mag\) can be considered as the graded set of all the binary trees where the set \(Mag(n)\) consists of all binary trees of arity \(n\geq 1\). \(Mag(1)\) has a single element, which is the unit. The number of elements of the set \(Mag(n)\) is equal to \((n-1)\)st Catalan number. Therefore, the Hilbert series for \(Mag\) operad is equal to the series \({\mathcal H}_{Mag}(t)= \sum\limits_{n\geq 1} \binom {2n-2}{n-1} \frac{1}{n} t^n\). (There was a typo in this formula in the article under review, and we have corrected it.)
For binary trees, rotations to the right [D.E. Knuth, The art of computer programming. Vol. 3: Sorting and searching. 2nd ed. Bonn: Addison-Wesley (1997; Zbl 0883.68015), Page 481] are defined. For any two binary trees \(t_1\), \(t_2\) having the same number of leaves \(n\), the order relation \(t_1 \leq t_2\) is defined if \(t_2\) can be obtained from \(t_1\) by a finite sequence of rotations to the right, or \(t_1=t_2\). This allows one to define the Tamari order relation on \(Mag(n)\) introduced by D. Tamari [The algebra of bracketings and their enumeration. Nieuw Arch. Wiskd., III. Ser. 10, 131–146 (1962; Zbl 0109.24502)].
From the text: “This work is intended to study and collect the possible links between the Tamari order and some quotients of the operad \(Mag\). In the long run, the goal is to study quotients \(Mag/_\equiv\) of \(Mag\) where \(\equiv\) is an operad congruence generated by equivalence classes of trees of a fixed degree (that is, a fixed number of internal nodes). In particular, we would like to know if the fact that \(\equiv\) is generated by equivalence classes of trees forming intervals of the Tamari order implies algebraic properties for \(Mag/_\equiv\) (like the description of orientations of its space of relations, of nice bases, and of Hilbert series). To explore this vast research area, we select to pursue in this paper the following directions. First, we consider the very general set of the quotients of Mag seen as an operad in the category of vector spaces. We show that this set of operads forms a lattice, wherein its partial order relation is defined from the existence of operad morphisms (Theorem 3.1.3). We also provide a Grassmann formula (see for instance [S. Lang, Algebra. 3rd revised ed. New York, NY: Springer (2002; Zbl 0984.00001), Chapter III, Excercise 1, Page 165]) analog relating the Hilbert series of the operads of the lattice together with their lower-bound and upper-bound (Theorem 3.2.1). Besides, we focus on a special kind of quotients of \(Mag\), denoted by \(CAs^{(\gamma)}\), defined by equating the left and right comb binary trees of a fixed degree \(\gamma\geq 1\). Observe that since \(CAs^{(2)}= As\), the operads \(CAs^{(\gamma)}\) can be seen as generalizations of \(As\). These operads are called comb associative operads. For instance, \(CAs^{(3)}\) is the operad describing the category of the algebras equipped with a binary product \(*\) subjected to the relation \[ ((x_1*x_2)*x_3)*x_4 = x_1*(x_2*(x_3*x_4)). \] We first provide general results about the operads \(CAs^{(\gamma)}\). In particular, we show that the set of these operads forms a lattice which embeds as a poset in the lattice of the quotients of Mag aforementioned (Theorems 4.2.8 and 4.2.9). We focus in particular on the study of \(CAs^{(3)}\). Observe that the congruence defining this operad is generated by an equivalence class of trees which is not an interval for the Tamari order. As preliminary computer experiments show, \(CAs^{(3)}\) has oscillating first dimensions (see (4.3.1-23)), what is rather unusual among all known operads. We provide a convergent orientation of the space of relations of \(CAs^{(3)}\) (Theorem 4.3.1), a description of a basis of the operad in terms of normal forms, and prove that its Hilbert series is rational. For all these, we use rewrite systems on trees [F. Baader and T. Nipkow, Term rewriting and all that. Cambridge: Cambridge University Press (1999; Zbl 0948.68098)] and the Buchberger algorithm for operads [V. Dotsenko and A. Khoroshkin, Gröbner bases for operads. Duke Math. J. 153, No. 2, 363–396 (2010; Zbl 1208.18007)]. We expose some experimental results obtained with the help of the computer for some operads \(CAs^{(\gamma)}\) with \(\gamma\geq 4\). All our computer programs are made from scratch in CAML and PYTHON. Finally, we continue the investigation of the quotients of \(Mag\) by regarding the quotients of \(Mag\) obtained by equating two trees of degree 3. This leads to ten quotient operads of \(Mag\). We provide for some of these combinatorial realizations, mostly in terms of integer compositions.”


18M65 Non-symmetric operads, multicategories, generalized multicategories
05C05 Trees
68Q42 Grammars and rewriting systems
55P48 Loop space machines and operads in algebraic topology


Python; Caml
Full Text: DOI arXiv


[1] Anick., D. J., On the Homology of Associative Algebras.”, Trans. Amer. Math. Soc., 296, 2, 641-659 (1986) · Zbl 0598.16028
[2] Adelson-Velsky, G. M.; Landis, E. M., An Algorithm for the Organization of Information, Sov. Math. Dokl., 3, 1259-1263 (1962)
[3] Baader, F.; Nipkow, T., Term Rewriting and All That (1998), Cambridge University Press
[4] Chenavier, C.; Cordero, C.; Giraudo, S., Generalizations of the Associative Operad and Convergent Rewrite Systems. Higher-Dimensional Rewriting and Algebra (2018)
[5] Chapoton, F., Sur le nombre d’intervalles dans les treillis de Tamari, Sém. Lothar. Combin, 55 (2006)
[6] Dotsenko, V.; Khoroshkin, A., Gröbner Bases for Operads.”, Duke Math. J., 153, 2, 363-396 · Zbl 1208.18007
[7] Gaussent, S.; Guiraud, Y.; Malbos., P., Coherent Presentations of Artin Monoids.”, Compos. Math., 151, 5, 957-998 (2015) · Zbl 1398.20069
[8] Giraudo, S., Operads from Posets and Koszul Duality.”, Eur. J. Combin., 56, 1-32 (2016) · Zbl 1354.18015
[9] Giraudo, S., Tree Series and Pattern Avoidance in Syntax Trees, Prepublication (2018)
[10] Ginzburg, V.; Kapranov, M. M., Koszul Duality for Operads.”, Duke Math. J., 76, 1, 203-272 (1994) · Zbl 0855.18006
[11] Hoffbeck, E., A Poincaré-Birkhoff-Witt Criterion for Koszul Operads.”, Manuscripta Math., 131, 1-2, 87-110 (2010) · Zbl 1207.18009
[12] Huang, S.; Tamari, D., Problems of Associativity: A Simple Proof for the Lattice Property of Systems Ordered by a Semi-Associative Law.”, J. Comb. Theory. A, 13, 7-13 (1972) · Zbl 0248.06003
[13] Knuth, D., The Art of Computer Programming, Sorting and Searching, 3 (1998), Addison Wesley Longman
[14] Khoroshkin, A.; Piontkovski, D., On Generating Series of Finitely Presented Operads.”, J. Algebra, 426, 377-429 (2015) · Zbl 1305.18034
[15] Lang, S., Algebra (2002), New York: Springer-Verlag, New York
[16] Loday, J.-L.; Ronco, M., On the Structure of Cofree Hopf Algebras, J. Reine Angew. Math, 592, 123-155 (2006) · Zbl 1096.16019
[17] Loday, J.-L.; Vallette, B., Grundlehren der mathematischen Wissenschaften,, 346, Algebraic Operads (2012), Heidelberg: Springer, Heidelberg
[18] Newman., M. H. A., On Theories with a Combinatorial Definition of “Equivalence.”, Ann. Math., 43, 2, 223-243 (1942) · Zbl 0060.12501
[19] Priddy., S. B., Koszul Resolutions.”, Trans. Amer. Math. Soc., 152, 39-60 (1970) · Zbl 0261.18016
[20] Rowland., E. S., Pattern Avoidance in Binary Trees.”, J. Comb. Theory A, 117, 6, 741-758 (2010) · Zbl 1221.05058
[21] Tamari, D., The Algebra of Bracketings and Their Enumeration, Nieuw Arch. Wisk, 10, 3-1962, 131-146 · Zbl 0109.24502
[22] Zinbiel, G. W., Operads and Universal Algebra, Volume 9 of Nankai Ser. Pure Appl. Math. Theoret. Phys.,, Encyclopedia of Types of Algebras 2010, 217-297 (2012), Hackensack, NJ: World Scientific Publishing, Hackensack, NJ
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.