Combinatorial proofs of freeness of
some P-algebras

Vincent Vong†

LIGM, 5 Bd Descartes, Champs-sur-Marne 77454 Marne la Vallée cedex 2, France

**Abstract.** We present new combinatorial methods for solving algebraic problems such as computing the Hilbert series of a free $P$-algebra over one generator, or proving the freeness of a $P$-algebra. In particular, we apply these methods to the cases of dendriform algebras, quadrialgebras and tridendriform algebras, which leads us to prove a conjecture of Aguiar and Loday about the freeness of the quadrialgebra generated by the permutation 12.

**Résumé.** Nous présentons de nouvelles méthodes combinatoires permettant de résoudre des problèmes algébriques concernant les $P$-algèbres, comme déterminer la série de Hilbert de la $P$-algèbre libre sur un générateur, ou de prouver qu'une $P$-algèbre est libre. Nous les appliquons aux cas des algèbres dendriformes, des quadrialgèbres, et des algèbres tridendriformes. Cette approche nous permet en particulier de résoudre une conjecture de Aguiar et Loday à propos de la liberté de la quadrialgèbre engendrée par la permutation 12.

**Keywords:** Free $P$-algebras, dendriform algebras, quadrialgebras, evaluation trees.

# 1 Introduction

Recently, new types of algebras have arisen from the theory of operads ([LV12]), for example, the dendriform and the tridendriform algebras, and the quadrialgebras. For an encyclopedia of different types of algebra, one can read [Zin]. The types of $P$-algebras, which are vector spaces equipped with products satisfying some relations, give rise to two natural questions: the first one is to find the Hilbert series of the free $P$-algebra over one generator of degree one, and the second one is to prove the freeness (or the non-freeness) of a given $P$-algebra $A$.

Dendriform algebras were defined by Loday in [Lod01]. He proved that the Hilbert series of the free dendriform algebra over one generator is equal to the series of Catalan numbers. One example was found by Loday and Ronco in [LR98]. Hivert, Novelli and Thibon gave some combinatorial properties of this algebra in [HNT05]. Another fundamental example of dendriform algebras is the algebra of Malvenuto and Reutenauer FQSym ([MR95], [DHT02]) obtained by splitting the shuffle product into two parts. Foissy in [Foi07], by algebraic methods, proved the freeness of FQSym as a dendriform algebra. Tridendriform algebras were introduced in [LR04] by splitting an associative law into three parts. An example is given

<footnote>†Email: vincent.vong@u-pem.fr.</footnote>
by WQSym ([NT06]). The freeness of this algebra was proved in [BR10]. Quadrialgebras were defined in [AL04]. An example is given by splitting an associative law into four parts. Vallette in [Val08], proved that the Hilbert series of the free quadrialgebra over one generator in degree one is equal to the generating function of the non-crossing connected graphs ([FN99]). But the freeness of the quadrialgebra generated by the permutation 12 remained open ([AL04]).

The aim of this article is to give combinatorial methods to prove the freeness of $\mathcal{P}$-algebras through some examples, the dendriform algebras, the quadrialgebras and the tridendriform algebras. Although the formalism of operads enlightens different aspects of the method we do not use this language. But despite this fact, the proofs are independent of the general theory of operads.

In Section 2, we recall some background about evaluation trees. Section 3 deals with the case of dendriform algebras. In particular, by adapting the proof of the freeness of PBT as a dendriform algebra, we deduce that FQSym is a free dendriform algebra. In the same way, we prove the freeness of the quadrialgebra generated by 12 in Section 4.

# 2 Background

## 2.1 General definitions

**Definition 1.** A pair $A = (A, \mathcal{P})$ is called a $\mathcal{P}$-algebra if $A$ is a graded vector space ($A = \bigoplus_{n \in \mathbb{N}} A_n$) with $A_0$ isomorphic to $\mathbb{K}$, $\mathcal{P}$ is a finite set of bilinear maps from $A$ to $A$ such that for each $B$ in $\mathcal{P}$, $y_n$ in $A_n$ and $y_m$ in $A_m$, the element $B(y_n, y_m)$ is in $A_{n+m}$, and the element of $A_0$ identified to $1_{\mathbb{K}}$ is the neutral element of $B$. We set $A^+ := \bigoplus_{n \ge 1} A_n$. If $\dim(A_n)$ is finite for each $n$, the Hilbert series of $A$ is the series $\sum_{n \ge 0} \dim(A_n)t^n$.

**Definition 2.** A decorated complete binary tree is defined by induction as follows:

* the empty set $\emptyset$ is a decorated complete binary tree,

* the triple $(a, \emptyset, \emptyset)$ is a decorated complete binary tree, where $a$ is an element of a certain set,

* the triple $(a, T_1, T_2)$ is a decorated complete binary tree if $T_1$ and $T_2$ are non-empty complete binary trees, and $a$ is an element.

We denote by CBT $(\mathcal{P}, \mathcal{B})$ the set of decorated complete binary trees where the leaves are decorated by elements of $\mathcal{B}$ and the internal nodes are decorated by the elements of $\mathcal{P}$.

**Definition 3.** Let $(\mathcal{A}, \mathcal{P})$ be a $\mathcal{P}$-algebra, and $\mathcal{B}$ a basis of $\mathcal{A}^+$. The vector space of evaluation trees over $\mathcal{A}$ denoted by $\mathcal{E}\mathcal{T}(\mathcal{A})$ is the vector space freely spanned by CBT $(\mathcal{P}, \mathcal{B})$.

**Example 1.** If $\mathcal{A} = (A, \{\times, \otimes, \odot\})$, and $a, a', b, b'$, and $c$ are in $\mathcal{A}$, the tree represented Figure 1 corresponds to the element $(a \otimes a') \times (b' \odot (b \times c))$ of $\mathcal{E}\mathcal{T}(\mathcal{A})$.

**Definition 4.** Let $(\mathcal{A}, \mathcal{P})$ be a $\mathcal{P}$-algebra. The evaluation map $\mathcal{E}v$ is a linear map from $\mathcal{E}\mathcal{T}(\mathcal{A})$ to $\mathcal{A}$ defined on trees by:

$$ \begin{align} \mathcal{E}v(\emptyset) &= 1_{\mathbb{K}} \notag \\ \mathcal{E}v((x, \emptyset, \emptyset)) &= x \tag{1} \\ \mathcal{E}v((B, T_1, T_2)) &= B(\mathcal{E}v(T_1), \mathcal{E}v(T_2)). \notag \end{align} $$

**Example 2.** For $\mathcal{A} = (\mathbb{K}\langle A \rangle, m)$, where $\mathbb{K}\langle A \rangle$ is the associative algebra of noncommutative polynomials over the alphabet $\mathcal{A}$ equipped with the concatenation product $m$, the vector space $\mathcal{E}\mathcal{T}(\mathcal{A})$ is spanned
<figure><img src="image_1.png" /><figcaption>Fig. 1: Evaluation tree of $(a \circled{a'}) \times (b' \odot (b \times c))$.</figcaption></figure>

by CBT($\{m\}, A^*$), where $A^*$ is the set of words over the alphabet $A$. Let us determine the kernel $K$ of the map $\mathcal{E}v$ and a vector space $S$ isomorphic to $K\langle A\rangle$ with $S \cap K = \{0\}$. Since the law $m$ is associative, for all words $u, v, w$ in $A^*$, we have:

$$m(m(u \otimes v) \otimes w) = m(u \otimes m(v \otimes w)). \qquad (2)$$

In other words,

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

where $\equiv$ is the relation “having the same image by the map $\mathcal{E}v$”. In order to find a vector space $S$, we consider the set $\mathcal{L}C(\{m\}, A)$ defined by induction as follows:

* the empty set $\emptyset$ is in $\mathcal{L}C(\{m\}, A)$,

* the leaves $(a, \emptyset, \emptyset)$ where $a$ is in $A$ are elements of $\mathcal{L}C(\{m\}, A)$,

* the trees of the form $(m, T_1, T_2)$ where $T_1$ is in $\mathcal{L}C(\{m\}, A)$ and $T_2$ is a leaf and in $\mathcal{L}C(\{m\}, A)$ are elements of $\mathcal{L}C(\{m\}, A)$.

Then, the word $w = a_1 \cdots a_n$ is the image of a tree $T(w)$ by $\mathcal{E}v$ built as follows:

* if $w = a_1$, then $T(w) = (a_1, \emptyset, \emptyset)$;

* otherwise, $T(w) = (m, T(w_1 \cdots w_{n-1}), w_n)$.

Thus, each tree in CBT($\{m\}, A^*$) is equivalent to an element of $\mathcal{L}C(m, A)$ for the relation $\equiv$. Since the evaluation map restricted to $\mathcal{L}C(m, A)$ is a bijection from $\mathcal{L}C(m, A)$ to the set $A^*$, it follows that a vector space $S$ is given by $\text{vect}(\mathcal{L}C(m, A))$, and a basis of the kernel $K$ by the set

$$\{T' - T | T' \in \mathcal{L}C(m, A), T \in \text{CBT}(\{m\}, A^*), T \neq T', T \equiv T'\}. \qquad (3)$$

In the general case, for a free associative graded algebra $(A, m)$, there exists a family $\mathcal{F}$ of $A$ such that the map $\mathcal{E}v$ is an isomorphism between $\text{vect}(\mathcal{L}C(m, \mathcal{F}))$ and $A$.

Conversely, let $(A, m)$ be a graded associative algebra and $\mathcal{F}$ a family of $A$ such that the map $\mathcal{E}v$ is an isomorphism between $\text{vect}(\mathcal{L}C(m, \mathcal{F}))$ and $A$. Let us prove that $A$ is free and generated by $\mathcal{F}$. Since the map $\mathcal{E}v$ restricted to $\text{vect}(\mathcal{L}C(m, \mathcal{F}))$ is surjective, we deduce that the algebra $A$ is generated by the family $\mathcal{F}$. Let $P$ be a polynomial in the variables $f_i$ elements of $\mathcal{F}$ such that

$$P(f_1, \cdots, f_n, \cdots) = 0. \qquad (4)$$
By isomorphism, we deduce that $P(f_1, \cdots, f_n, \cdots)$ is the image by $\mathcal{E}v$ of a linear combination of trees in $\mathcal{LC}(m, \mathcal{F})$. But this family of trees is linearly independent and the kernel of the restriction of $\mathcal{E}v$ to $\mathcal{LC}(m, \mathcal{F})$ is reduced to $\{0\}$. So by taking the image by $\mathcal{E}v$, we deduce that the polynomial $P$ is the zero polynomial.

*Remark 1.* Thanks to the formalism of evaluation trees, we see that an algebraic problem such as the freeness of an associative algebra can be seen as a problem of linear algebra in a family of trees.

If a free family $\mathcal{F}$ generates an algebra $\mathcal{A}$, by induction, it is possible to choose the family $\mathcal{F}$ homogeneous. In other words, each element $f$ in $\mathcal{F}$ is in an $\mathcal{A}_n$.

## 2.2 Some combinatorial methods for $\mathcal{P}$-algebra problems

In the theory of $\mathcal{P}$-algebras, one of the first question is to compute the Hilbert series of the free $\mathcal{P}$-algebra over one generator of degree one. In the case of the associative algebra, this Hilbert series is given by $\frac{1}{1-t}$, which is also the generating function of the combinatorial class $\mathcal{LC}(\{m\}, \{a\})$, filtered by the number of $a$. The freeness (or non-freeness) of a $\mathcal{P}$-algebra $\mathcal{A}$ is another natural question.

### 2.2.1 The Hilbert series of a $\mathcal{P}$-algebra over one generator of degree one

Let us consider $\mathcal{A}$, the free $\mathcal{P}$-algebra over one generator $x$ of degree one. The elements can be represented as linear combinations of elements of $CBT(\mathcal{P}, \{x\})$. Since there may be some relations between elements of $\mathcal{P}$, the set $CBT(\mathcal{P}, \{x\})$ may not be a basis of $\mathcal{A}$. More generally, for each subset $S$ of $CBT(\mathcal{P}, \{x\})$ such that $S$ is a generating family of $\mathcal{A}$, the dimension of $\mathcal{A}_n$ is lower than the dimension of $vect(S)_n$.

On the other hand, given a $\mathcal{P}$-algebra $\mathcal{A}'$ built from one generator of degree one, the $\mathcal{P}$-algebra $\mathcal{A}'$ may have other relations. Therefore, we have $\dim(\mathcal{A}'_n) \le \dim(\mathcal{A}_n)$.

One way to find the Hilbert series of $\mathcal{A}$ is to find a subset $S$ of $CBT(\mathcal{P}, \{x\})$ which generates $\mathcal{A}$, and such that the family $\mathcal{F}$ obtained by evaluation of the set $S$ in the algebra $\mathcal{A}'$ is linearly independent. Since the subset $S$ generates the algebra $\mathcal{A}$, we deduce that $\dim(\mathcal{A}_n) \le \dim(vect(S)_n)$. Since $\mathcal{F}$ is linearly independent in $\mathcal{A}'$, we deduce that $\dim(vect(S)_n) \le \dim(\mathcal{A}'_n) \le \dim(\mathcal{A}_n)$. It follows from previous inequalities that $\dim(\mathcal{A}_n) = \dim(\mathcal{A}'_n) = \dim(vect(S)_n)$. Thus, by computing the Hilbert series of $vect(S)$, we deduce the Hilbert series of $\mathcal{A}$.

### 2.2.2 The freeness of a $\mathcal{P}$-algebra

Assume that we have found a basis of the free $\mathcal{P}$-algebra over one generator $x$ of degree one, represented by a subset $S$ of $CBT(\mathcal{P}, \{x\})$. It follows that the free $\mathcal{P}$-algebra over the family $\mathcal{F}$ has a basis represented by $S_{\mathcal{F}}$ which is the set of trees of $S$ whose leaves are replaced by elements of $\mathcal{F}$. Thus, in order to prove that a $\mathcal{P}$-algebra $\mathcal{A}$ is free, it is sufficient to find a homogeneous family $\mathcal{F}$ of $\mathcal{A}$ such that the evaluation map $\mathcal{E}v$ restricted to $vect(S_{\mathcal{F}})$ is an isomorphism between $vect(S_{\mathcal{F}})$ and $\mathcal{A}$.

In the next sections, we consider different families of $\mathcal{P}$-algebras and apply these methods to some problems about $\mathcal{P}$-algebra.
# 3 The case of dendriform algebras

## 3.1 General properties

### 3.1.1 Background

**Definition 5.** A dendriform algebra $(\mathcal{A}, \succ, \prec)$ is a vector space $\mathcal{A}$ equipped with two bilinear maps $\succ$ and $\prec$ such that for each elements $a, b, c$ in $\mathcal{A}$, we have:

$$ \left\{ \begin{array}{lcl} (a \prec b) \prec c & = & a \prec ((b \prec c) + (b \succ c)) \quad = \quad a \prec (b \prec + \succ c) \\ a \succ (b \succ c) & = & (a \prec + \succ b) \succ c \\ (a \succ b) \prec c & = & a \succ (b \prec c). \end{array} \right. \qquad (5) $$

*Remark 2.* Since the equality is satisfied for all element in the algebra, it is convenient to omit the entries. For example, the equality

$$ (a \prec b) \prec c = a \prec (b \prec + \succ c), $$

becomes

$$ (\prec) \prec = \prec (\prec + \succ). $$

We can also represent it with evaluation trees:

$$ \begin{tikzpicture} \draw (-1,0) -- (1,0); \node at (-0.5,0) {\prec}; \node at (0.5,0) {\succ}; \node at (0,0.5) {=}; \node at (0,-0.5) {\prec}; \node at (1,0.5) {\prec}; \node at (1,-0.5) {\succ}; \node at (0.5,-0.7) {+}; \node at (0.5,0.7) {\succ}; \node at (1.5,0) {\succ}; \node at (-1.5,0) {\prec}; \end{tikzpicture} \qquad (6) $$

**Definition 6.** Let $u$ and $v$ be two words respectively of size $n$ and $m$. The *shuffle product* is defined by induction as follows:

* $u \sqcup v = v \sqcup u = v$ if $n = 0$,

* $u \sqcup v = v \sqcup u = u$ if $m = 0$,

* $u \sqcup v = (u_1 \cdots u_{n-1} \sqcup v)u_n + (u \sqcup v_1 \cdots v_{m-1})v_m$ otherwise.

If $u$ is a word over the alphabet $\mathbb{N}$, then $u[k]$ is the word $(u_1 + k)(u_2 + k) \cdots (u_i + k) \cdots (u_n + k)$. For $u$ and $v$ two words over the alphabet $\mathbb{N}$, the *shifted shuffle* of $u$ and $v$, denoted by $u \bar{\sqcup} v$ is the shuffle product $u \sqcup v[k]$, where $k$ is the greatest letter in $u$.

**Example 3.** If $\sigma = 11$ and $\tau = 12$, we have:

* $\sigma \sqcup \tau = 1112 + 1112 + 1112 + 1121 + 1121 + 1211,$

* $\sigma \bar{\sqcup} \tau = 1123 + 1213 + 2113 + 1231 + 2131 + 2311.$

**Example 4.** Let us denote by $\mathfrak{S} = \cup_{n \in \mathbb{N}} \mathfrak{S}_n$ the set of permutations. We consider the algebra **FQSym** = *vect*($\mathbf{F}_\sigma$) equipped with two products $\succ$ and $\prec$ defined as follows. Let $\sigma$ and $\tau$ be two permutations of respective size $n$ and $m$. Let us set:

$$ \mathbf{F}_{\sigma} \prec \mathbf{F}_{\tau} := \sum_{\substack{\gamma \in \sigma \bar{\sqcup} \tau \\ \gamma_{n+m} = \sigma_n}} \mathbf{F}_{\gamma}, \qquad (7) $$

and

$$ \mathbf{F}_{\sigma} \succ \mathbf{F}_{\tau} := \sum_{\substack{\gamma \in \sigma \bar{\sqcup} \tau \\ \gamma_{n+m} = \tau_m[n]}} \mathbf{F}_{\gamma}. \qquad (8) $$

Then (**FQSym**, $\succ$, $\prec$) is a dendriform algebra ([LR98]).
**Proposition 2.** The generating series $F$ of $\mathcal{T}\mathcal{D}(\{\prec, \succ\}, \{x\})$ is equal to $\sum_{n \ge 1} C_n t^n$, where $C_n$ is the $n$-th Catalan number.

**Proposition 3.** The evaluation map $\mathcal{E}v$ from $\mathcal{T}\mathcal{D}(\{\prec, \succ\}, \{x\})$ to $\mathbf{FQSym}$ is an injective map.

*Proof.* Let us begin with Proposition 2. We have: $F = t + F_{\prec} + F_{\succ}$ where $F_{\odot}$ is the generating function of trees of $\mathcal{T}\mathcal{D}(\{\prec, \succ\}, \{x\})$ where the root is decorated by $\odot$. Since trees of $\mathcal{T}\mathcal{D}(\{\prec, \succ\}, \{x\})$ avoids the patterns (9), we deduce that $F_{\prec}$ is equal to $tF$ and $F_{\succ}$ is equal to $F(t + F_{\prec})$. So $F$ satisfies the equation $F = t + 2tF + tF^2$ which is a functional equation satisfied by $\sum_{n \ge 1} C_n t^n$. By uniqueness of the solution, we deduce that $F = \sum_{n \ge 1} C_n t^n$.

Let us prove Proposition 3. We consider a tree $T$ of $\mathcal{T}\mathcal{D}(\{\prec, \succ\}, \{x\})$. By replacing $x$ by $\mathbf{F}_1$ and evaluating $T$ in $\mathbf{FQSym}$, we see that an element $\mathbf{F}_{\sigma}$ appears only in one and only one evaluation. Thus, the set of evaluations of elements of $\mathcal{T}\mathcal{D}(\{\prec, \succ\}, \{x\})$ is linearly independent. $\square$

Thus, thanks to Propositions 1, 2, 3 we deduce the following corollary:

**Corollary 1.** A basis of the free dendriform algebra $\mathcal{A}$ over one generator of degree one $x$ is represented by the set $\{\emptyset\} \cup \mathcal{T}\mathcal{D}(\{\prec, \succ\}, \{x\})$, and the Hilbert series of $\mathcal{A}^+$ is equal to $\sum_{n \ge 1} C_n t^n$.

*Remark 3.* The plan of proofs given for Propositions 1, 2, 3 are adaptable for other $\mathcal{P}$-algebras. Moreover by slightly modifying the proofs, we deduce that dendriform algebra $\mathcal{A}$ is free if and only if there exists a family $\mathcal{F}$ of elements of $\mathcal{A}$ such that the set of evaluations of the trees of $\mathcal{T}\mathcal{D}(\{\succ, \prec\}, \mathcal{F})$ is a basis of $\mathcal{A}^+$.

## 3.2 The dendriform algebra FQSym

As we have seen in Example 4, $\mathbf{FQSym}$ is a dendriform algebra. So a natural question is whether it is free or not. By Remark 3, it is sufficient to find a family $\mathcal{F}$ such that the set of evaluations of elements of $\mathcal{T}\mathcal{D}(\{\succ, \prec\}, \mathcal{F})$ is a basis of $\mathbf{FQSym}^+$. In order to do this, we establish a factorization theorem on permutations which is essentially equivalent to the freeness of $\mathbf{FQSym}$.

### 3.2.1 A factorization theorem

**Proposition 4.** Let us consider the lexicographic order over permutations. Let $I$ and $J$ be two subsets of $\mathfrak{S}$, $\sigma$ and $\tau$ be the smallest element of respectively $I$ and $J$, and $n$ be the size of $\sigma$. Then:

* the smallest element of $I \succ J$ is the permutation $\sigma\tau[n]$,

* the smallest element of $I \prec J$ is the permutation $\sigma_1 \cdots \sigma_{n-1}\tau[n]\sigma_n$.

Hence, for $\sigma$ and $\tau$ two permutations of respective size $n$ and $m$, we define two reduced products as follows: $\sigma \succ' \tau := \sigma\tau[n]$ and $\sigma \prec' \tau := \sigma_1 \cdots \sigma_{n-1}\tau[n]\sigma_n$.

**Example 6.** For $\sigma = 31452$ and $\tau = 2431$, we have $\sigma \prec' \tau = 314579862$, and $\sigma \succ' \tau = 314527986$.

**Definition 7.** Let $E$ be a subset of $\{\succ', \prec'\}$. A permutation $\sigma$ is said to be $E$-connected if for all $\star'$ in $E$,

$$ (\sigma = u \star' v) \implies (u = \sigma \text{ or } v = \sigma). \qquad (10) $$

A permutation is called *indecomposable* if it is $\{\succ', \prec'\}$-connected. We denote by $\mathcal{I}_p$ the set of indecomposable permutations.
**Example 7.** The permutation 3412 is indecomposable, 2341 is {$\succ$}'-connected but not {$\prec$}'-connected.

**Theorem 1.** Let $\sigma$ be a permutation of positive size. Then $\sigma$ satisfies one and only one of these possibilities:

* $\sigma$ is indecomposable,

* $\sigma = u \succ' v$ with $v \{\succ'\}$-connected,

* $\sigma = u \prec' v$ with $u$ indecomposable.

*Proof.* Let $u, u', v, v'$ four permutations of respective size $n, n', m, m'$. Assume that we have:

$\sigma = u \succ' v = u' \prec' v'$, where $v$ is {$\succ'$}-connected, and $u'$ is indecomposable. If $m > m'$, we have $n < n'$. Then $u'$ would have $u$ as a prefix which is a permutation. Therefore, $u'$ could be factorized as $u \succ w$ and would not be indecomposable. If $n \ge n'$, by comparing the last values, we have $v'[n] > n \ge n' \ge u_{n'}$, which is a contradiction.

If $\sigma = u \succ' v = u' \succ' v'$, we have $uv[n] = u'v'[n']$. The {$\succ'$} connectedness of $v$ (resp. $v'$) would be contradicted if $n < n'$ (resp. $n > n'$). Therefore, necessarily, $u = u'$ and $v = v'$.

If $\sigma = u \prec' v = u' \prec' v'$, and $n > n'$, then $u$ would not be indecomposable, since we would have $u = u' \prec \alpha$, where $u = u_1 \cdots u_{n'-1}\alpha[n']u_{n'}$. By symmetry, the result follows for $n < n'$. $\square$

**Example 8.** We have $143652 = 1 \succ' (1 \prec' ((1 \prec' 1) \succ' (1 \prec' 1)))$.

**Corollary 2.** The evaluation map from $\mathcal{TD}(\{\prec', \succ'\}, \mathcal{I}p)$ to permutations of positive size is bijective.

*Proof.* The fact that the map is surjective comes from the existence of a factorization from Theorem 1, and the fact that is injective comes from the uniqueness of this factorization. $\square$

### 3.2.2 The freeness of the dendriform algebra FQSym

In [Foi07], Foissy gives an algebraic proof of the freeness of **FQSym** as a particular case of a structure theorem: he proves that bidendriform connected algebras are free dendriform algebras over totally primitive elements. Since **FQSym** has a natural bidendriform structure, the result follows. In the sequel, we present a combinatorial proof which only use the dendriform structure of **FQSym**.

**Theorem 2.** The set $S := \{\mathcal{E}v(T) | T \in \mathcal{TD}(\{\prec, \succ\}, \mathcal{I}p)\}$ is a basis of $\mathbf{FQSym}^+$. Therefore, $\mathbf{FQSym}$ is a free dendriform algebra generated by the family $(\mathbf{F}_{\sigma})_{\sigma \in \mathcal{I}p}$.

*Proof.* Thanks to Corollary 2, we deduce that for each element $\mathcal{E}v(T)$ of $S$ there exists a unique permutation $\sigma$ such that $ev(T) = \mathbf{F}_{\sigma} + \sum_{\tau >_{lex} \sigma} a_{\tau} \mathbf{F}_{\tau}$, and $\sigma$ is only minimal in the evaluation of $T$. Therefore, $S$ is a basis of $\mathbf{FQSym}^+$, thus $\mathbf{FQSym}$ is a free dendriform algebra generated by the family $(\mathbf{F}_{\sigma})_{\sigma \in \mathcal{I}p}$. $\square$

**Remark 4.** We can deduce Proposition 3 from the first part of Theorem 2. Then, the second part of this theorem follows thanks to Proposition 3.

## 4 The case of quadrialgebras

In [AL04], Aguiar and Loday introduced quadrialgebras, motivated by some natural generalizations of dendriform algebras. At the end of their article, four conjectures about this type of algebras are enunciated. The first three are proved by Vallette in [Val08] with algebraic methods. The last one seems to remain open. By the combinatorial methods used in Section 3, we give new proofs for the first and last ones.
# 4.1 General properties

## 4.1.1 Background

**Definition 8.** ([AL04]) Let $V$ be a $\mathbb{K}$ vector space equipped with four internal bilinear maps $[\tilde{\gamma}]$, $[\tilde{\gamma}']$, $[\tilde{\gamma}']'$ and $[\tilde{\gamma}]'$. We call $(V, [\tilde{\gamma}], [\tilde{\gamma}], [\tilde{\gamma}], [\tilde{\gamma}])$ a quadrialgebra if the four bilinear maps satisfy the following relations:

$$ 
\begin{align} 
([\tilde{\gamma}]) [\tilde{\gamma}] &= [\tilde{\gamma}] ([\star]) & ([\tilde{\gamma}]) [\tilde{\gamma}] &= [\tilde{\gamma}] ([\star]) & ([\tilde{\gamma}')] [\tilde{\gamma}] &= [\tilde{\gamma}] ([\star]) \nonumber \\ 
([\tilde{\gamma}]) [\tilde{\gamma}] &= [\tilde{\gamma}] ([\star')] & ([\tilde{\gamma}]) [\tilde{\gamma}] &= [\tilde{\gamma}] ([\star')] & ([\tilde{\gamma}')] [\tilde{\gamma}] &= [\tilde{\gamma}] ([\star]), \tag{11} \\ 
([\star]) [\tilde{\gamma}] &= [\tilde{\gamma}] ([\star')] & ([\star]) [\tilde{\gamma}] &= [\tilde{\gamma}] ([\star')] & ([\star]) [\tilde{\gamma}] &= [\tilde{\gamma}] ([\star]) \nonumber 
\end{align} 
$$

where $[\star] = [\tilde{\gamma}] + [\tilde{\gamma}']$ and $[\star] = [\tilde{\gamma}] + [\tilde{\gamma}']$ with $\alpha$ in $\{\star, \prec, \succ\}$.

**Definition 9.** Let $k$ be a positive integer. A 2-permutation of size $2k$ is a word $w$ such that all letters from 1 to $k$ are repeated exactly twice in $w$. The set of 2-permutations is denoted by $\mathfrak{S}^{(2)}$.

Let us consider the vector space $V(\mathfrak{S}^{(2)})$ generated by $\mathfrak{S}^{(2)}$. Let us define the four following bilinear maps, for $u = u_1 \cdots u_{2n}$ and $v = v_1 \cdots v_{2m}$ two 2-permutations:

$$ 
\begin{align} 
u_1 \cdots u_{2n} [\tilde{\gamma}] v_1 \cdots v_{2m} &= v_1 (u \bar{\wedge} v_2 \cdots v_{2m-1}) v_{2m} \nonumber \\ 
u_1 \cdots u_{2n} [\tilde{\gamma}] v_1 \cdots v_{2m} &= v_1 (u_1 \cdots u_{2n-1} \bar{\wedge} v_2 \cdots v_{2m}) u_{2n} \nonumber \\ 
u_1 \cdots u_{2n} [\tilde{\gamma}] v_1 \cdots v_{2m} &= u_1 (u_2 \cdots u_{2n} \bar{\wedge} v_1 \cdots v_{2m-1}) v_{2m} \nonumber \\ 
u_1 \cdots u_{2n} [\tilde{\gamma}] v_1 \cdots v_{2m} &= u_1 (u_2 \cdots u_{2n-1} \bar{\wedge} v) u_{2n} \nonumber 
\end{align} 
$$

It is straightforward that $(V(\mathfrak{S}^{(2)}), [\tilde{\gamma}], [\tilde{\gamma}], [\tilde{\gamma}], [\tilde{\gamma}])$ is a quadrialgebra ([AL04]).

## 4.1.2 A generating family of the free quadrialgebra over one generator

In the same way as free dendriform algebra, we represent the element of the free quadrialgebra over one generator $x$ as linear combination of complete binary trees such that the leaves are decorated by $x$, and the internal node are decorated by elements of the set $E := \{[\tilde{\gamma}], [\tilde{\gamma}], [\tilde{\gamma}], [\tilde{\gamma}]\}$.

We denote by $\mathcal{TQ}(E, \mathcal{F})$ the set of non-empty decorated complete binary trees whose internal nodes are decorated by elements of $E$, whose leaves are decorated by elements of $\mathcal{F}$ and avoiding the following patterns:

$$ a \substack{[\tilde{\gamma}] \\ ,} b, \substack{[\tilde{\gamma}] \\ [\tilde{\gamma}],} [\tilde{\gamma}], \substack{[\tilde{\gamma}] \\ [\tilde{\gamma}],} [\tilde{\gamma}], \substack{[\tilde{\gamma}] \\ [\tilde{\gamma}],} [\tilde{\gamma}], \tag{13} $$

where $a \in \{[\tilde{\gamma}], [\tilde{\gamma}], [\tilde{\gamma}], [\tilde{\gamma}]\}$, and $b \in \{[\tilde{\gamma}], [\tilde{\gamma}], [\tilde{\gamma}], [\tilde{\gamma}]\}$.

**Proposition 5.** The set of $\mathcal{TQ}(E, \{x\})$ generates the free quadrialgebra over $x$.
**Proposition 6.** The generating function $F$ of $\mathcal{TQ}(E, \{x\})$ satisfies the following equation:

$$t(F + 1)^3 + (F + 1)^2 - 3(F + 1) + 2 = 0. \qquad (14)$$

In particular, $F$ is the generating series of the non-crossing connected graph ([FN99]).

**Remark 5.** We prove Proposition 5 by induction as Proposition 1, and Proposition 6 using the same method as Proposition 2.

From Proposition 5, we cannot conclude that $\mathcal{TQ}(E, \{x\})$ is a basis, but just a generating family.

## 4.2 The quadrialgebra of 2-permutations

### 4.2.1 A factorization theorem

**Proposition 7.** Let us consider the lexicographic order on 2-permutations. Let $I$ and $J$ be two subsets of $\mathfrak{S}^{(2)}$, $\sigma$ and $\tau$ be respectively the smallest element of $I$ and $J$, $2n$ be the size of $\sigma$ and $2m$ the size of $\tau$. Then:

* the smallest element of $I[\tilde{\sigma}]$ $J$ is the permutation $\tau_1[n]\sigma\tau_2[n]\cdots\tau_{2m}[n]$,

* the smallest element of $I[\tilde{\sigma}]$ $J$ is the permutation $\tau_1[n]\sigma_1\cdots\sigma_{2n-1}\tau_2[n]\cdots\tau_{2m}[n]\sigma_{2n}$,

* the smallest element of $I[\tilde{\sigma}]$ $J$ is the permutation $\sigma\tau[n]$,

* the smallest element of $I[\tilde{\sigma}]$ $J$ is the permutation $\sigma_1\cdots\sigma_{2n-1}\tau[n]\sigma_{2n}$.

Hence, for $\sigma$ and $\tau$ two 2-permutations respectively of size $2n$ and $2m$, we define four reduced products as follows:

* $\sigma[\tilde{\sigma}]'\tau := \tau_1[n]\sigma\tau_2[n]\cdots\tau_{2m}[n]$,

* $\sigma[\tilde{\sigma}]'\tau := \tau_1[n]\sigma_1\cdots\sigma_{2n-1}\tau_2[n]\cdots\tau_{2m}[n]\sigma_{2n}$.

* $\sigma[\tilde{\sigma}]'\tau := \sigma\tau[n]$,

* $\sigma[\tilde{\sigma}]'\tau := \sigma_1\cdots\sigma_{2n-1}\tau[n]\sigma_{2n}$.

**Example 9.** For $\sigma = 211323$ and $\tau = 312213$, we have: $\sigma[\tilde{\sigma}]'\tau = 621132345546$, $\sigma[\tilde{\sigma}]'\tau = 621132455463$, $\sigma[\tilde{\sigma}]'\tau = 213236455464$, $\sigma[\tilde{\sigma}]'\tau = 211326455463$.

**Definition 10.** Let $E$ be a subset of $\{[\tilde{\sigma}]', [\tilde{\sigma}]', [\tilde{\sigma}]', [\tilde{\sigma}]'\}$. A 2-permutation $\sigma$ is said to be $E$-connected if for all $\star'$ in $E$,

$$(\sigma = u \star' v) \implies (u = \sigma \text{ or } v = \sigma). \qquad (15)$$

A 2-permutation is called *indecomposable* if it is $\{[\tilde{\sigma}]', [\tilde{\sigma}]', [\tilde{\sigma}]', [\tilde{\sigma}]'\}$-connected. We denote by $\mathcal{IP}$ the set of indecomposable 2-permutations.

**Example 10.** The 2-permutation 213213 is indecomposable, the 2-permutation 211323 is not $[\tilde{\sigma}]'$ connected ($211323 = 11[\tilde{\sigma}]'1212$) but is $\{[\tilde{\sigma}]', [\tilde{\sigma}]', [\tilde{\sigma}]'\}$-connected.

**Theorem 3.** Let $\sigma$ be a 2-permutation. Then:

* $\sigma$ is indecomposable,
* otherwise $\sigma = u[\prec]v$, with $u$ indecomposable,

* otherwise $\sigma = u[\succ]v$, with $v[\prec]'$-connected,

* otherwise $\sigma = u[\succ]v$, with $v[\succ]'$-connected,

* otherwise $\sigma = u[\succ]v$, with $v([\succ]'), [\prec]'), [\succ]''$-connected,

$u$ and $v$ being unique if they exist.

*Proof.* Assume there exists two pairs $(u, v)$ and $(u', v')$, two laws $\star'$ and $\odot'$ of $E$ such that $\sigma = u \star' v = u' \odot' v'$ with $(u, v)$ and $(u', v')$ satisfying the conditions of Theorem 3. By analyzing the two members, if $\star'$ and $\odot'$ are different, we have a contradiction. And by analyzing the case of $\star' = \odot'$, we obtain, necessarily, $u = u'$, and $v = v'$. $\square$

**Corollary 3.** Let $\mathcal{TQ}(E', IP)$ be the set of trees obtained by replacing labels $\star$ of internal nodes of $\mathcal{TQ}(E, IP)$ by their analogous $\star'$. Then the map $\mathcal{E}v$ is a bijection between $\mathcal{TQ}(E', IP)$ and the set of non-empty 2-permutations.

*Proof.* By applying Theorem 3 by induction, we deduce this corollary. $\square$

### 4.2.2 The free quadrialgebra of 2-permutations

**Corollary 4.** The family $\mathcal{TQ}(E, \{x\})$ is a basis of $Q^+$, where $Q$ is the free quadrialgebra over one generator $x$.

**Corollary 5.** (Conjecture in [AL04]) The quadrialgebra generated by the permutation 12 is free.

**Corollary 6.** The Hilbert series of the free quadrialgebra over one generator of degree one is equal to the generating series of the non-crossing connected graphs.

*Proof.* Let $S$ be the set of evaluations of trees of $\mathcal{TQ}(E, 11)$. Thanks to Corollary 2 and Proposition 7, we deduce that the set $S$ is linearly independent. Therefore, the family $\mathcal{TQ}(E, \{x\})$ is a basis of the free quadrialgebra over the generator $x$. We deduce immediately that the quadrialgebra generated by 11 is free by comparing the dimensions of homogeneous components, and so for the quadrialgebra generated by 12 since it is isomorphic to the quadrialgebra generated by 11 by standardization.

Since the generating series of the set $\mathcal{TQ}(E, \{x\})$ is equal to the generating series of the non-crossing connected graphs, Corollary 6 follows. $\square$

**Theorem 4.** The quadrialgebra $(V(\mathfrak{S}^{(2)}), [\prec], [\succ], [\prec], [\succ])$ is free and generated by the set $IP$.

*Proof.* Let $Q$ be the free quadrialgebra over the family $IP$. Thanks to Corollary 4, we deduce that the set $\mathcal{TQ}(E, IP)$ is a basis of $Q^+$. From Theorem 3 and Proposition 7, it follows that the image of $\mathcal{TQ}(E, IP)$ is a basis of $V(\mathfrak{S}^{(2)})^+$. Since the evaluation map $\mathcal{E}v$ is a morphism of quadrialgebras, we deduce that this map is in fact an isomorphism, which proves the theorem. $\square$

## 5 The case of tridendriform algebras

For tridendriform algebra we also can apply the same method in order to find the Hilbert series $\mathcal{H}$ of the tridendriform algebra over one generator and to prove that **WQSym** a tridendriform algebra defined in [NT06] is free.
# Acknowledgements

I am grateful to Samuele Giraudo for interesting discussions and ideas about operads.

## References

[AL04] M. Aguiar and J.-L. Loday. Quadri-algebras. *Journal of Pure and Applied Algebra*, 191(3):205-221, 2004.

[BR10] E. Burgunder and M. Ronco. Tridendriform structure on combinatorial Hopf algebras. *Journal of Algebra*, 324(10):2860-2883, 2010.

[DHT02] G. Duchamp, F. Hivert, and J.-Y. Thibon. Noncommutative Symmetric Functions VI: Free Quasi-Symmetric Functions and Related Algebras. *International Journal of Algebra and Computation*, 12(5):671-717, 2002.

[FN99] P. Flajolet and M. Noy. Analytic combinatorics of non-crossing configurations. *Discrete Mathematics*, 204(1):203-229, 1999.

[Foi07] L. Foissy. Bidendriform bialgebras, trees, and free quasi-symmetric functions. *Journal of Pure and Applied Algebra*, 209(2):439-459, 2007.

[HNT05] F. Hivert, J.-C. Novelli, and J.-Y. Thibon. The algebra of binary search trees. *Theor. Comput. Sci.*, 339(1):129-165, 2005.

[Lod01] J.-L. Loday. Dialgebras. *Lect. Notes Math.*, 1763:7-66, 2001.

[LR98] J.-L. Loday and M.-O. Ronco. Hopf Algebra of the Planar Binary Trees. *Advances in Mathematics*, 139(2):293-309, 1998.

[LR04] J.-L. Loday and M. Ronco. Trialgebras and families of polytopes. *Contemporary Mathematics AMS*, 346:369-398, 2004.

[LV12] J.-L. Loday and B. Vallette. *Algebraic operads*, volume 346. Springer, 2012.

[MR95] C. Malvenuto and C. Reutenauer. Duality between quasi-symmetrical functions and the Solomon descent algebra. *Journal of Algebra*, 177(3):967-982, 1995.

[Nov14] J.-C. Novelli. m-dendriform algebras. *arXiv preprint arXiv:1406.1616*, 2014.

[NT06] J.-C. Novelli and J.-Y. Thibon. Polynomial realizations of some trialgebras. *arXiv preprint math/0605061*, 2006.

[Val08] B. Vallette. Manin products, Koszul duality, Loday algebras and Deligne conjecture. *J. Reine Angew. Math.*, 620:105-164, 2008.

[Zin] GW Zinbiel. Encyclopedia of types of algebras 2010.