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.”

MSC:

 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: