# Growth function for a class of monoids

Marie Albenque¹ and Philippe Nadeau²

¹LIAFA, CNRS-Université Paris Diderot - Paris 7, case 7014, 75205 Paris Cedex 13, France.

²Fakultät für Mathematik, University of Vienna, Nordbergstrasse 15, 1090 Vienna, Austria.

**Abstract.** In this article we study a class of monoids that includes Garside monoids, and give a simple combinatorial proof of a formula for the formal sum of all elements of the monoid. This leads to a formula for the growth function of the monoid in the homogeneous case, and can also be lifted to a resolution of the monoid algebra. These results are then applied to known monoids related to Coxeter systems: we give the growth function of the Artin-Tits monoids, and do the same for the dual braid monoids. In this last case we show that the monoid algebras of the dual braid monoids of type A and B are Koszul algebras.

**Résumé.** Nous étudions une classe de monoïdes incluant les monoïdes de Garside, et donnons une preuve combina-toire simple d'une formule pour la somme formelle de leurs éléments. Cela mène à une formule pour la fonction de croissance du monoïde dans le cas homogène, et peut être aussi relevé en une résolution de l'algèbre de monoïdes. Ces résultats sont ensuite appliqués aux monoïdes liés aux systèmes de Coxeter: nous donnons la fonction de crois-sance des monoïdes d'Artin-Tits ainsi que des monoïdes duaux; pour ces derniers nous montrons que leur algèbre de monoïde en types A et B est une algèbre de Koszul.

**Keywords:** monoid, growth function, Garside group, resolution, Koszul algebra

## Introduction

We consider left cancellative monoids $M$ that are generated by their atoms $S$, and such that if a subset of $S$ admits a common right multiple, then it actually admits a least common multiple.

These monoids include trace monoids, for which there exists a nice combinatorial theory due to Viennot [23]. Our first result (Theorem 2) generalizes one of the proofs of Viennot for the formal sum of elements a monoid. When the monoid is homogeneous with respect to its set of atoms $S$, then we have immediately that the growth function of the monoid (i.e. the generating function according to the length of elements as words in $S$) is the inverse of a polynomial. We will apply this formula to Artin-Tits monoids, and more generally it applies to all Garside monoids [9].

The combinatorial proof, which is a actually a sign reversing involution, has an interpretation as a resolution of $\mathbb{Z}$ as a $\mathbb{Z}M$-module, where $\mathbb{Z}M$ stands for the monoid algebra of $M$. Another resolution can be deduced from this one, and in turn this new resolution gives another formula for the growth generating function of the monoid. We use this reduced resolution in the case of the *dual braid monoids* defined by Bessis in the types *A* and *B*; for a particular choice of the reduced resolution in these cases, we will show that the monoid algebras $\mathbb{Z}M$ are *Koszul algebras* [19, 11].
We now give an outline of the paper. In Section 1 we define the class of monoids we study, give formulas for the formal sum of their elements (Theorem 2) and the growth functions of such monoids, and give interpretations of these results as resolutions of the corresponding monoid algebras. In Section 2, we explain how these results apply to both trace monoids and Garside monoids. The following two sections apply the results of Section 1 to two families of Garside monoids related to irreducible finite Coxeter groups. In Section 3 we give the growth functions of the corresponding Artin-Tits monoids. In Section 4, we also give the corresponding growth functions for the dual braid monoids, and show that in type A and B the corresponding monoid algebras are Koszul algebras.

# 1 Growth function and exact resolution

## 1.1 Monoids

A monoid $(M, \cdot)$ is a set $M$ together with an internal law $\cdot$ that is associative and such that there exists an identity element 1. A subset $S \subset M$ is a generating set if every element of $M$ can be written as a product of elements of $S$.

Let $S$ be a set, and $R$ a collection of pairs $(w, w')$ (called relations), where $w$ and $w'$ are words in $S$. We say that $\langle S | R \rangle$ is a presentation of the monoid $M$ if $M$ is isomorphic to $S^*/\langle R \rangle$, where $\langle R \rangle$ is the congruence generated by $R$. The presentation is said to be homogeneous if all relations of $R$ are composed of two words of equal length. Given a generating set $S$ of $M$, the length of an element $m \in M$ is the smallest number of generators needed to write it. We will write $|m|_S$ for this length, and we note that this length is additive if $M$ admits a homogeneous presentation.

An element $a$ is an atom of $M$ if $a \neq 1$, and if $a = bc$ implies $b = 1$ or $c = 1$; a monoid is atomic if it is generated by its set of atoms, and if in addition every element $m$ possesses a finite number of different decompositions as a product of atoms. It is easy to see that an atomic monoid has the property that $a \neq 1$ and $b \neq 1$ imply that $ab \neq 1$.

We note $\mathbb{Z}M$ the monoid algebra of $M$, whose elements are formal linear combinations of elements of $M$ with coefficients in $\mathbb{Z}$; we note also $\mathbb{Z}\langle\langle M \rangle\rangle$ the algebra of formal infinite such linear combinations. The product of $\sum_m c_m m$ and $\sum_m d_m m$ is in both cases given by $\sum_m e_m m$ where $e_m = \sum_{ab=m} c_a d_b$; the product is well defined if the sum is finite, which is the case when $M$ is atomic.

## 1.2 Main result

In all this work, we consider monoids $\mathbb{M}$ with a finite generating set $\mathcal{S}$ satisfying the following properties: $\mathbb{M}$ is atomic, left-cancellative (if $a, u, v \in \mathbb{M}$ are such that $au = av$, then $u = v$) and verifies that if a subset of $\mathcal{S}$ has a right common multiple, then it has a least right common multiple.

**Lemma 1.** For such a monoid, if $J \subset S$ is such that $J$ has a common multiple, then a least common multiple (lcm) exists and is unique.

We will call cliques the subsets of $\mathcal{S}$ having a common multiple, and let $\mathcal{J}$ be the set of all cliques; if $J$ is a clique, we note $M_J$ its unique least common multiple, and let $m_J$ be the length of $M_J$. Then we have our first result:

**Theorem 2.** Let $M, S$ be as above. Then the following identity holds in $\mathbb{Z}\langle\langle M \rangle\rangle$:

$$ \left( \sum_{J \in \mathcal{J}} (-1)^{|J|} M_J \right) \cdot \left( \sum_{m' \in M} m' \right) = 1_M \qquad (1.1) $$
As an important corollary, we get the following:

**Corollary 3** (Bronfman '01). Given $M, S$ as in the above theorem, suppose also that $M$ admits a homogeneous presentation $\langle S | \mathcal{R} \rangle$. Then its growth function is equal to :

$$G_M(t) = \sum_{m \in M} t^{|m|s} = \left[ \sum_{J \in \mathcal{J}} (-1)^{|J|} t^{m_J} \right]^{-1} \quad (1.2)$$

of Corollary 3. Admitting a homogeneous presentation is equivalent to the fact that the length according to $S$ is additive, which means that the application $\sum_m c_m m \mapsto \sum_m c_m t^{|m|s}$ is a homomorphism from $\mathbb{Z}\langle\langle M \rangle\rangle$ to $\mathbb{Z}[t]$, the ring of power series with integer coefficients. It is indeed well defined because there is a finite number of elements of $M$ of a given length. We can apply this homomorphism to both sides of the above theorem, which finishes the proof. $\square$

of Theorem 2. For every element $m \in M$, let us define $\mathcal{J}(m) \subseteq \mathcal{J}$ to be the subsets $J$ of $S$ such that every element $s$ of $J$ divides $m$; by the lcm property of $M$, we have that there exists a subset $J_m \subseteq S$, such that $\mathcal{J}(m)$ consists exactly of the subsets of $J_m$.

From now on we fix a total order $<$ on the set of generators $S$. Let us fix any $m \neq 1$. Clearly $J_m$ is not empty in this case, and so we can define $s(m)$ as the maximal (for the order $<$) element of $J_m$. Define the involution $\Phi_m$ on $\mathcal{J}(m)$ as follows: $\Phi_m(J) = J \Delta \{s(m)\}$ where $\Delta$ denotes the symmetric difference $A \Delta B = (A \cup B) \setminus (A \cap B)$. The application $\Phi_m$ is simply the classical involution on the subsets of $J_m$; since $\Phi_m$ changes the parity of $|J|$, we have obviously

$$\sum_{J \subseteq J_m} (-1)^{|J|} = 0. \quad (1.3)$$

Note that this sum is 1 if we take $m = 1$, since there is only one term corresponding to the empty set. Now $J \in \mathcal{J}(m)$ means precisely that $M_J$ divides $m$, that is there exists $m'$ such that $M_J m' = m$: such an element $m'$ is uniquely determined by the cancellability property. Therefore Equation (1.3) can be rewritten equivalently as

$$\sum_{\substack{(J, m') \in \mathcal{J} \times M \\ M_J m' = m}} (-1)^{|J|} = \begin{cases} 0 & \text{if } m \neq 1; \\ 1 & \text{if } m = 1. \end{cases} \quad (1.4)$$

But this quantity is precisely the coefficient $c_m$ of $m$ in the left term of Equation (1.1) written in the form $\sum_m c_m m$, and so this proves Theorem 2. $\square$

## 1.3 Posets

We refer to [22, ch. 3] for standard notions about posets. Given a locally finite poset $(P, \leq)$ (i.e all intervals have a finite number of elements), the Möbius function can be defined inductively on all pairs $x \leq z$ by

$$\mu(x, x) = 1, \quad \mu(x, z) = \sum_{x \leq y < z} \mu(x, y) \quad \text{for } x < z \quad (1.5)$$

Now consider a monoid $M$ (as in Paragraph 1.2 with the divisibility relation $\leq$. It forms a locally finite poset $P_M$ as is readily checked, so it has a Möbius function; it has also a smallest element 1, and we write
$\mu(m) = \mu(1, m)$. In this poset, atoms of the monoids become atoms of the poset (i.e. elements that cover 1), and lcms become joins. We will use this in Section 4 to compute the growth functions of dual braid monoids of type A and B in particular, since the interval $[1, M_S]$ in $P_M$ for these monoids are noncrossing partitions.

Note that one can identify the algebra $\mathbb{Z}\langle\langle M \rangle\rangle$ with the incidence algebra $I(P_M)$. From this we know that $\zeta_M = \sum_{m \in M} m \in \mathbb{Z}\langle\langle M \rangle\rangle$ has for inverse in $\mathbb{Z}\langle\langle M \rangle\rangle$ the function $\sum_m \mu(m)m$, so that Theorem 2 is actually a manner of computing the Möbius function of this poset, related to the crosscut theorem of Rota [21].

## 1.4 An exact resolution

In this paragraph we give resolutions that generalize the one in [14] which concerned trace monoids: let $M, S$ be as at the beginning of Paragraph 1.2, $A = \mathbb{Z}M$ be the monoid algebra of $M$. Let $B = \mathbb{Z}\mathcal{J}$ be the free module with basis $\mathcal{J}$, and $B_n$ be the submodule with basis $\mathcal{J}_n$ the cliques of cardinal $n$. Consider then $C_n = B_n \otimes_{\mathbb{Z}} A$ the free (right) $\mathcal{J}$-module with basis $\mathcal{J}_n$. Now we fix a total order $<$ on $S$, and we write cliques as words $s_1 \dots s_n$ where $s_i < s_{i+1}$ for all $i$. For two cliques $J \subset J'$, we also let $\delta_J^{J'\setminus J}$ be the element of $M$ such that $M_J \delta_J^{J'\setminus J} = M_{J'}$; it is well defined thanks to the cancellability property. We define an $\mathcal{J}$-module homomorphism $d_n : C_n \to C_{n-1}$ by

$$d_n(s_1 \dots s_n \otimes 1) = \sum_{i=1}^{n} (-1)^{n-i} s_1 \dots \hat{s_i} \dots s_n \otimes \delta_{s_1 \dots \hat{s_i} \dots s_n}^{s_i} \quad (1.6)$$

We define also $\epsilon: A \to \mathbb{Z}$ by $\epsilon(m) = 0$ if $m \neq 1$ and $\epsilon(1) = 1$, so that we have the following sequence of $\mathcal{J}$-modules and $\mathcal{J}$-homomorphism (where we let $k = |S|$):

$$0 \to C_k \xrightarrow{d_k} C_{k-1} \xrightarrow{d_{k-1}} \dots \xrightarrow{d_2} C_1 \xrightarrow{d_1} C_0 = A \xrightarrow{\epsilon} \mathbb{Z} \quad (1.7)$$

**Theorem 4.** *The complex (1.7) is a resolution of $\mathbb{Z}$ as an $\mathcal{J}$-module.*

We recall that this means that the sequence is exact, i.e. we have to check that $\mathrm{Im}(d_n) = \mathrm{Ker}(d_{n-1})$ for all $n$.

*Proof.* Let $J = s_1 \dots s_n$ be a clique, then one checks first that $d_{n-1} \circ d_n = 0$ for any $n$. Indeed the computation gives $d_{n-1} \circ d_n(J \otimes 1) = \sum_{i<j} (-1)^{i+j-1} J_{i,j} \otimes (\delta_{J_{i,j}}^{s_j} \delta_{J_i}^{s_i} - \delta_{J_{j,i}}^{s_i} \delta_{J_j}^{s_j})$, where we let $J_{i_1, \dots, i_t}$ be the clique obtained by removing the generators $s_{i_1}, \dots, s_{i_t}$ from $J$. Now the difference in the second term is 0 since both terms are equal to $\delta_{J_{i,j}}^{s_i, s_j}$.

So we have $\mathrm{Im}(d_n) \subseteq \mathrm{Ker}(d_{n-1})$, and to check the reverse inclusion, we define a $\mathbb{Z}$-homomorphism $i_{n+1} : C_n \to C_{n+1}$ in the following way: let $J \otimes m \in C_n$, with $J = s_1 \dots s_n$, and consider the subset of $S$ consisting of divisors of $M_J m$ that are greater than $s_n$; call this set $\mathcal{E}(J, m)$. If $\mathcal{E}(J, m)$ is empty, set $i_{n+1}(J \otimes m) := 0$; otherwise, let $s_{n+1}$ be the maximum element of $\mathcal{E}(J, m)$ for the order $<$, and define $m_1$ by $\delta_J^{s_{n+1}} m_1 = m$; then set $i_{n+1}(s_1 \dots s_n \otimes m) := s_1 \dots s_n s_{n+1} \otimes m_1$. One can then check that $i_{n-1} \circ d_{n-1} + d_n \circ i_n = 1$ for all $n$ in a similar manner to [14], where 1 is the identity on $C_{n-1}$. This shows that $\mathrm{Ker}(d_{n-1}) \subseteq \mathrm{Im}(d_n)$ and concludes the proof. $\square$

Now we show how this resolution gives a proof of Theorem 2:
of Theorem 2. Define the $\mathbb{Z}$-module $C(m) = \oplus_n C_{n,m}$ by letting the basis of $C_{n,m}$ be the elements $J \otimes m_1$ such that $|J| = n$ and $M_J m_1 = m$ in $M$. Then the functions $d_n$ and $i_{n+1}$ map $C(m)$ to itself as is immediately checked, so we obtain for every $m \in M$ an exact sequence of free $\mathbb{Z}$-modules:

$$0 \to C_{k,m} \xrightarrow{d_k} C_{k-1,m} \xrightarrow{d_{k-1}} \dots \xrightarrow{d_2} C_{1,m} \xrightarrow{d_1} C_{0,m} \xrightarrow{\epsilon} \mathbb{Z}_m \quad (1.8)$$

We have that $dim_{\mathbb{Z}} C_{n,m}$ is the number of pairs $(J, m_1) \in \mathcal{J} \times M$ such that $|J| = n$ and $M_J m_1 = m$; furthermore, $dim_{\mathbb{Z}} \mathbb{Z}_m$ is equal to 1 if $m = 1$ and 0 otherwise. Taking the Euler-Poincaré characteristic of the resolution (1.8) gives us then Equation (1.4), which has been shown to be equivalent to Theorem 2. $\square$

**Reduced resolution:** Given a total order on $S$ as above, introduce now the set $\mathcal{J}_< \subseteq \mathcal{J}$ of order compatible cliques: these are the cliques $s_1 \dots s_n$ such that for all $i$ we have that $s_i$ is the largest divisor of $M_{s_1, \dots, s_i}$ for the order $<$. We will write OC for order compatible.

**Lemma 5.** A clique $J = s_1 \dots s_n$ is OC if and only if for all $t \le n$ and all sequences of indices $1 \le i_1 < \dots < i_t \le n$ we have that $s_{i_t}$ is the maximal divisor of $M_{s_{i_1}, \dots, s_{i_t}}$.

*Proof.* The condition is clearly sufficient; now if $J = s_1 \dots s_n$ is OC and $1 \le i_1 < \dots < i_t \le n$, we have the inequalities $s_{i_t} \le \maxdiv(M_{s_{i_1}, \dots, s_{i_t}}) \le \maxdiv(M_{s_1, s_2, \dots, s_{i_t}}) = s_{i_t}$. So all inequalities are in fact equalities and the lemma is proved. $\square$

**Corollary 6.** If $J$ is an OC clique then every subset of $J$ is also an OC clique.

Now let $\tilde{C}_i$ be the A-submodule of $C_i$ with basis the OC cliques of size $i$. By the last corollary, the derivations $d_i$ are well defined when restricted to these submodules, so we have a complex:

$$0 \to \tilde{C}_k \xrightarrow{d_k} \tilde{C}_{k-1} \xrightarrow{d_{k-1}} \dots \xrightarrow{d_2} \tilde{C}_1 \xrightarrow{d_1} \tilde{C}_0 = A \xrightarrow{\epsilon} \mathbb{Z} \quad (1.9)$$

**Proposition 7.** The complex (1.9) is an exact resolution of $\mathbb{Z}$ by A-modules.

*Proof.* We check that the homotopy $i_{n+1}$ is still well defined when restricted to the $\mathbb{Z}$-module $\tilde{C}_n$, which will prove the proposition. Suppose $J = s_1 \dots s_n$ is an OC clique, $m \in M$, and that the maximal element $s_{n+1}$ among the divisors of $M_J m$ is greater than $s_n$. Then, if $s$ divides $M_{s_1, \dots, s_{n+1}}$, it divides also $M_J m$, and thus the greatest of these divisors is $s_{n+1}$; this shows that $s_1 \dots s_{n+1}$ is an OC clique, and thus that the function $i_{n+1}$ is well defined. So now the same proof as the one of Theorem 4 can be applied, and the result follows. $\square$

These modules were already considered in [8][Section 4], but with a different resolution.

**Proposition 8.** Theorem 2 and its corollary hold if the sum is restricted to $\mathcal{J}_<$ (for any given total order $<$ on $S$.)

The proof mimics the alternative proof of Theorem 2 above. We will use this proposition and the resolution in Section 4.

## 2 Application to some classes of monoids

We give in this section some examples of monoids that satisfy the conditions of Theorem 2.
## 2.1 Trace monoids

Trace monoids (also called heaps of pieces monoids, Cartier-Foata monoids or free partially commutative monoids) are defined by the presentation $M = \langle S | ab = ba \mid (a, b) \in I \rangle$, where $S$ is a finite set of generators and $I$ is a symmetric and antireflexive relation on $S \times S$ called the commutation relation. In [23], elements of $M$ are interpreted as heaps of pieces

At the very beginning, the aim of the work presented here was to generalize the results of [23]. It is indeed a special case of our Theorem 2: in trace monoids, for a subset $J$ of $S$, only two disjoint cases can occur: either all elements of $J$ commute, and their product is clearly their least common multiple; or there exist two elements of $J$ which do not commute, and $J$ does not admit a common multiple.

The first case corresponds to what is called cliques in the trace monoid literature, from which we borrowed our terminology in our more general setting. It is then straightforward that the set of all least common multiples of cliques corresponds exactly to the set of heaps of pieces of height at most one.

This work applies too to divisibility monoids which are a natural generalization of trace monoids, studied in [10, 16].

## 2.2 Artin-Tits monoids

The Artin-Tits monoids are a generalization of both trace monoids and braid monoids (which are extensively studied in Section 3). Given a finite set $S$ and a symmetric matrix $M = (m_{s,t})_{s,t \in S}$ such that $m_{s,t} \in \mathbb{N} \cup \{\infty\}$ and $m_{s,s} = 1$, the Artin-Tits monoid $M$ associated to $S$ and $M$ has the following presentation:

$$ M = \langle s \in S \mid \underbrace{\text{sts...}}_{m_{s,t} \text{ terms}} = \underbrace{\text{tst...}}_{m_{s,t} \text{ terms}} \text{ if } m_{s,t} \neq \infty \rangle \quad (2.1) $$

An Artin-Tits monoid is clearly homogeneous, has the left and right cancellation property (see Michel, Proposition 2.4 of [17]) and has the least common multiple property (see Brieskorn and Saito, Proposition 4.1 of [7]). So in this case also our main Theorem and its corollary apply.

The Coxeter group associated to an Artin-Tits monoid is defined as the quotient of the latter by the relations $s^2 = 1$ for any $s \in S$. In other words, the Coxeter Group $W$ is defined by the following presentation:

$$ W = \langle s \in S \mid s^2 = 1 \text{ and } \underbrace{\text{sts...}}_{m_{s,t} \text{ terms}} = \underbrace{\text{tst...}}_{m_{s,t} \text{ terms}} \text{ if } m_{s,t} \neq \infty \rangle. $$

An Artin-Tits monoids is called spherical if and only if its Coxeter group is finite. For example, the only trace monoids that are spherical are the ones whose every elements commute. More generally, every subset of generators of a spherical Artin-Tits monoid admit a lcm. In this case the set $J$ of Theorem 2 and of Corollary 3 is naturally the set of all subsets of $S$.

## 2.3 Garside monoids

In [9], Dehornoy and Paris generalize spherical Artin-Tits groups as follows:

**Definition 9.** A Garside monoid is an atomic left cancellative monoid $M$, such that any two elements have left and right lcm. We require besides that $M$ admits a Garside element $\Delta$: this means an element whose sets of left and right divisors coincide, and such that this set is finite and generates $M$.
A Garside monoid fitted with the set S of its atoms satisfies the conditions of the main theorem. Furthermore, as for spherical Artin-Tits monoids, all subsets of atoms of a Garside monoids have a lcm and so the set J is the set of every subsets of S.

# 3 Spherical Artin-Tits monoids

We study in this section the combinatorics of the classical braid monoid introduced by Artin and of some of its generalizations, namely the classical braid monoids of types B and D. All these monoids are spherical Artin-Tits monoids and hence some Garside monoids.

## 3.1 Coxeter groups

Before going further, let us just mention some points about finite Coxeter groups. A Coxeter group is said to be irreducible if there does not exist two disjoint subsets $S_1$ and $S_2$ of S such that $S = S_1 \cup S_2$ and such that any $s_1 \in S_1$ commutes with any $s_2 \in S_2$. The irreducible finite Coxeter groups are completely classified (see [13]). This section is devoted to the three infinite families $A_n$, $B_n$ and $D_n$ and more precisely to the corresponding Artin monoids. We compute their growth functions by applying Theorem 2; this boils down to describing how to compute lcms in such monoids.

For $X = A_n, B_n, D_n$, we write the corresponding growth function of the Artin-Tits monoid $G_X(t) = \frac{1}{H_X(t)}$, where $H_X$ is the polynomial $\sum_J (-1)^{|J|}t^{m_J}$, in which the sum is over all subsets $J$ of generators and $m_J$ is the length of the lcm $M_J$ of $J$. We describe in the following such lcms.

## 3.2 Type A

The Artin monoid $\mathcal{A}(A_n)$ is in fact the classical braid monoid on $n+1$ strands. Hence, it admits the following presentation:

$$ \mathcal{A}(A_n) = \langle \sigma_1, \dots, \sigma_n \mid \sigma_i \sigma_{i+1} \sigma_i = \sigma_{i+1} \sigma_i \sigma_{i+1} \text{ and } \sigma_i \sigma_j = \sigma_j \sigma_i \text{ if } |i-j| \le 2 \rangle. $$

We denote $\Sigma_n = \{\sigma_1, \dots, \sigma_n\}$ the set of Artin generators. To compute the lcm of a subset $J$ of $\Sigma_n$, let us consider a partition $J = J_1 \cup \dots \cup J_p$ such that any $\sigma_i$ and $\sigma_j$ in $J$ belong to the same block of this partition if and only if $j = i \pm 1$.

We set $\Delta_{\{\sigma_j, \sigma_{j+1}, \dots, \sigma_{j+i}\}} = (\sigma_j)(\sigma_{j+1}\sigma_j)\dots(\sigma_{j+i}\dots\sigma_{j+1}\sigma_j)$, then $M_J$ is equal to $\Delta_{J_1} \dots \Delta_{J_p}$ and $m_J = \sum_{i=1}^p (|J_i|(|J_i|+1)/2)$.

In this case, no explicit formula is known for $H_{A_n}$ but the form of the lcms leads easily to the following recurrence relation:

$$ H_{A_n}(t) = \sum_{i=1}^{n} (-1)^{i+1} t^{i(\frac{i-1}{2})} H_{A_{n-i}}(t) + (-1)^n t^{\frac{n(n+1)}{2}}. $$

## 3.3 Type B

The Artin monoid $\mathcal{A}(B_n)$ of type B is the monoid whose set of generators is $\Sigma_n = \{\sigma_1, \dots, \sigma_n\}$ and which is submitted to the following relations:

$$ \sigma_1\sigma_2\sigma_1\sigma_2 = \sigma_2\sigma_1\sigma_2\sigma_1, \quad \sigma_i\sigma_{i+1}\sigma_i = \sigma_{i+1}\sigma_i\sigma_{i+1}, \text{ for } i \ge 2 \text{ and } \sigma_i\sigma_j = \sigma_j\sigma_i \text{ if } |i-j| \le 2. $$
The elements of this monoid are classically represented as positive braids whose second strand is not
braided.

Similarly to Paragraph 3.2, for $J \subset \{\sigma_1, \dots, \sigma_n\}$, we write $J = J_1 \cup \dots \cup J_p$, where the properties satisfied by this partition are the same as those given above. Because of the particular role of $\sigma_1$, three different cases have to be considered to compute the lcm of $J$. Either $\sigma_1 \notin J$ or $\sigma_1 \in J$ and $\sigma_2 \notin J$ and in these cases $M_J = \Delta_{J_1} \dots \Delta_{J_p}$ just as before. Now if $\sigma_1, \sigma_2 \in J$, without loss of generality we assume that $\sigma_1 \in J_1$, then $M_J = \tilde{\Delta}_{J_1} \Delta_{J_2} \dots \Delta_{J_p}$, where $\tilde{\Delta}_{J_1} = (\sigma_1 \sigma_2 \dots \sigma_m)^{|J_1|}$ with $\sigma_m$ the maximal element of $J_1$ for the classical ordering $\sigma_1 < \sigma_2 < \dots < \sigma_n$ of $\Sigma_n$.

The expression of lcms enable to obtain the following recurrence relation for $H_{B_n}$, for $n \ge 1$ (with the
convention $H_{B_0}(t) = 1$):

$$
H_{B_n}(t) = \sum_{i=1}^{n} (-1)^{i+1} t^{i(i-1)/2} H_{B_{n-i}}(t) + (-1)^n t^{(n)^2}.
$$

3.4 Type D

The Artin monoid $\mathcal{A}(D_n)$ of type $D$ is the monoid whose set of generators is $\Sigma_n = \{\tau, \sigma_1, \dots, \sigma_{n-1}\}$ and submitted to the following relations:

$$
\tau \sigma_2 \tau = \sigma_2 \tau \sigma_2, \qquad \sigma_i \sigma_{i+1} \sigma_i = \sigma_{i+1} \sigma_i \sigma_{i+1} \text{ for } i \ge 2, \quad (3.1)
$$

$$
\tau \sigma_i = \sigma_i \tau \text{ for } i \neq 2 \quad \text{and} \quad \sigma_i \sigma_j = \sigma_j \sigma_i \text{ if } |i-j| \le 2. \quad (3.2)
$$

In [1], Allcock introduced a representation in terms of braids on some orbifolds of the elements of this
monoid.

Let $J \subset \Sigma_n$, because of the symmetric role of $\tau$ and $\sigma_1$ we have to study two cases depending on either at most one of them belongs to $J$ or both of them. Without loss of generality, we assume that only $\sigma_1$ belongs to $J$, then $M_J = \Delta_{J_1} \dots \Delta_{J_p}$, where the $J_i$ as defined in Paragraph 3.2 (it suffices to replace each occurrence of $\sigma_1$ in $M_J$ by $\tau$ to deal with the symmetric case). If $\tau$ and $\sigma_1$ belong both to $J$, we moreover assume that $\sigma_1 \in J_1$, then $M_J = \tilde{\Delta}_{J_1} \Delta_{J_2} \dots \Delta_{J_p}$, where $\tilde{\Delta}_{J_1} = (\tau \sigma_1 \sigma_2 \dots \sigma_m)^{|J_1|}$ with $\sigma_m$ the maximal element of $J_1$ for the classical ordering $\sigma_1 < \sigma_2 < \dots < \sigma_n$ of $\Sigma_n$.

Once again, this leads to the following recurrence relation for the denominator of the generating func-
tion of $\mathcal{A}(D_n)$, for $n \ge 2$ (by convention $H_{B_0}(t) = 1$ and $H_{B_1}(t) = 1$):

$$
H_{D_n}(t) = \sum_{i=1}^{n-1} (-1)^{i+1} t^{i(i-1)/2} H_{D_{n-i}}(t) + (-1)^{n-1} 2t^{(n)(n-1)/2} + (-1)^n t^{(n)(n-1)}.
$$

4 Dual braid monoids

4.1 *Definition*

We defined Coxeter systems in paragraph 2.2. Let $T$ be the set of reflections of $W$, i.e. the set $T = \{wsw^{-1}, s \in S\}$; $T$ is obviously a generating set for $W$, and we let $\ell_T(w) = k$ where $k$ is the minimal number of reflections $t_i \in T$ such that $w = t_1 \cdot t_k$; the function $\ell_T$ is then invariant under conjugation, that is we have $\ell_T(w) = \ell_T(zwz^{-1})$ for any two elements $w, z \in W$. Then one defines a partial order on $W$ by setting $w \le_T z$ if $\ell_T(w) + \ell_T(w^{-1}z) = \ell_T(z)$. A Coxeter element is an element $c$ of $W$ which
is the product of the Coxeter generators $S$ in any order; one can show that any two Coxeter elements are conjugate in $W$. Given a Coxeter element $c \in W$, one defines a poset $NC(W, c) = [1, c]$ with respect to the partial order $\leq_T$. Since $l_T$ is invariant under conjugation and any two Coxeter elements are conjugate, we have that the isomorphism type of $NC(W, c)$ does not depend on the particular $c$ chosen, and we will just write $NC(W)$. We refer to [2] and the references therein for more information about this topic.

Bessis [5] showed that one can define a certain dual braid monoid for every poset, with generating set in bijection with $T$, which is a Garside monoid such that the lattice of elements dividing the Garside element is isomorphic to the lattice $NC(W)$. As shown in Section 1.3, we need only this lattice to compute the growth function of the monoid. We refer the reader to [5] for the general definition of the monoid, and to [18] for explicit presentations in classical types.

Note that the values $\sum_{rk(x)=k} \mu(x)$ of the Möbius functions of the posets $NC(W)$ have already been computed in general, so by the results of Subsection 1.3, all growth functions of the dual braid monoids can be obtained. What we will do here is to find first a combinatorial proof of this result in type A and B, and then verify that the resolution (1.9) we obtain shows that the corresponding algebras of the corresponding dual braid monoids are in fact Koszul algebras (Paragraph 4.5). The combinatorial objects that we will deal with are noncrossing alternating forests, which we now study.

## 4.2 Noncrossing alternating forests and unary binary trees

Consider $n$ points aligned horizontally, labeled 1, 2, ..., $n$ from left to right. We identify pairs $(i, j)$, $i < j$, with arcs joining $i$ and $j$ above the horizontal line. Two arcs $(i, j)$ and $(k, l)$ are crossing if $i < k < j < l$ or $k < i < l < j$.

**Definition 10.** A noncrossing alternating forest on $n$ points is a set of noncrossing arcs on $[[1, n]]$ such that at every vertex $i$, all the arcs are going in the same direction (to the right or to the left).

It is easily seen that these conditions determine forests in the graph-theoretical sense, that is the arcs cannot form a cycle. We define $NCAF(n, k)$ as the set of noncrossing alternating forests on $n$ points with $k$ arcs, and in this subsection we will determine bijectively their cardinality denoted $NCAF(n, k)$.

We will actually define a bijection with unary binary trees, by which we mean rooted plane trees all of whose vertices have 0, 1 or 2 sons. It is well known that such trees with $m$ vertices are counted by the Motzkin number $M_{m-1}$ (cf. [22]) and that they are in bijection with Motzkin paths with $m-1$ steps: these are paths in $\mathbb{N}^2$ from (0, 0) to $(m-1, 0)$, with allowed steps (1, 1), (1, 0) and $(1, -1)$. The bijection consists of a prefix traversal of the tree, as shown by the dotted line around the tree on the left of Figure 1; for every left son (respectively right son, resp. single son) encountered for the first time, we draw an up step (resp. a down step, resp. a horizontal step). Under this bijection, unary vertices correspond to horizontal steps; by the cyclic lemma, it is then easy to show that:

**Proposition 11.** The number of unary binary trees with $m$ vertices and $p$ binary vertices is given by

$$ \frac{1}{m} \binom{m}{m-2p-1, p, p+1} = \frac{(m-1)!}{(m-2p-1)!p!(p+1)!} $$

Suppose we have just one connected component in a noncrossing alternating forest, i.e $k = n-1$: we obtain the noncrossing alternating trees introduced in [12], where a bijection with binary trees with $n$ leaves was given. We recall this bijection: given a noncrossing alternating tree on $n \geq 2$ points, there is necessarily an edge between 1 and $n$. Destroying that arc, we get two smaller noncrossing alternating
<figure><img src="image_1.png" /><figcaption>Fig. 1: A unary binary tree and the corresponding Motzkin path.</figcaption></figure>

trees, on $i$ and $n - i$ points say. By induction, we can attach a binary tree to each of these smaller trees; let $T_1$ and $T_2$ be these two trees respectively, and create a new root (corresponding to the deleted arc) with left subtree $T_1$ and right subtree $T_2$. The inverse bijection is immediate.

We can generalize this bijection as follows:

**Theorem 12.** There is a bijection between unary binary trees with $n+k-1$ vertices and $k$ binary vertices, and noncrossing alternating forests on $n$ points with $k$ arcs.

*Proof.* Let us be given a noncrossing alternating forest on $n$ points with $k$ arcs; for each of the $n-k$ components, we apply the bijection for noncrossing trees described above, keeping the labels on the leaves. So we have a collection $C$ of binary trees, such that each integer $\llbracket 1, n \rrbracket$ appears exactly once as the label of a leaf. Let $T$ be the tree containing the label 1, and let $m$ be such that $1, \dots, m$ label leaves of $T$, but $m+1$ does not; let $T'$ be the tree containing the label $m+1$. We then form a new tree $T_1$ by transforming the leaf labeled $m$ in a unary vertex (still labeled $m$), whose attached subtree is $T'$. We now remove $T$ and $T'$ from $C$ and replace them by $T_1$; we can now repeat the same operation, and we do it until $C$ has just one element, which is a unary binary tree with $n-k-1$ unary vertices.

Conversely, given a unary binary tree with $k-1$ unary vertices and $n$ leaves, we make a prefix traversal of the tree, and we label only unary vertices and leaves (thus leaving binary vertices unlabeled). Then we cut every edge stemming from a unary vertex, which gives us a forest of $k$ binary trees labeled on leaves: we apply to each of them the bijection for noncrossing trees (using as point set the labels of the leaves), thereby obtaining the desired noncrossing forest. $\square$

The bijection is illustrated on Figure 2, in which $n = 10$ and $k = 5$. From Proposition 11, we have the immediate corollary:

**Corollary 13.** The number of noncrossing alternating forests on $n$ points with $k$ arcs is given by

$$NCAF(n, k) = \frac{(n-1+k)!}{(n-1-k)!k!(k+1)!}$$

## 4.3 Type A

In type A, the poset $NC(W)$ is isomorphic to the noncrossing partition lattice $NC^A(n)$, which we describe. A set partition of $[n]$ is noncrossing if it does not have two blocks $B, B'$ and elements $i, j \in B$ and $k, l \in B'$ such that $i < k < j < l$. Let $NC^A(n)$ be the poset of noncrossing partitions of size $n$ ordered by refinement.
<figure><img src="image_2.png" /><figcaption>Fig. 2: Bijection between unary binary trees and noncrossing alternating forests</figcaption></figure>

We now need to compute joins of cliques in this poset; we will use here a certain order on atoms to restrict to certain order compatible cliques (see Section 1). The atoms of $NC^A(n)$ are the partitions with one block of size 2 and all other blocks are singletons, and we identify these atoms with arcs $(i, j)$ between the points labeled $i$ and $j$ if $n$ points horizontally aligned and labelled from 1 to $n$ are given. Now we define the following order on atoms: $(i, j) < (k, l)$ if $l - k > j - i$, or if $l - k = j - i$ and $i < k$; the important point is that if an arc contains another arc, then it is bigger.

Consider a clique of size two $\{(i, j), (k, l)\}$. If $i < k \le j < l$, then the join of these elements is the partition with one non-singleton block $\{i, j, k, l\}$; but $(i, l)$ is smaller in the poset than this partition, and bigger than both $(i, j)$ and $(k, l)$ for the order $<$, so the clique cannot be OC. Now it can be shown that all other size 2 cliques are OC, and that OC cliques of size $k$ are precisely the elements of $\mathcal{NCAF}(n, k)$; the join of such an OC-clique is simply the partition whose blocks are the labels of each tree in the forest. For the element of $\mathcal{NCAF}(10, 2)$ on the left of Figure 2, the noncrossing partition has blocks $\{1, 3, 6, 7\}, \{2\}, \{4, 5\}, \{8, 10\}$ and $\{9\}$.

From this, Proposition 11 and 11 we have that the growth function of the dual braid monoid of type A is given by

$$G_A(t) = \left( \sum_{k=0}^{n} (-1)^k \frac{(n-1+k)!}{(n-1-k)!k!(k+1)!} \right)^{-1}$$

This answers a conjecture of Krammer [15, Exercise 17.37].

## 4.4 Type B

Here the poset $NC(W)$ is isomorphic to the type B noncrossing partitions $NC^B(n)$, which is defined as the subposet of $NC^A(2n)$ formed by partitions of $\{1, 2, \dots, n, -1, -2, \dots, -n\}$ that are invariant under the bijection $i \mapsto -i$. We note $((i_1, \dots, i_t))$ the partition with non singleton blocks $\{i_1, \dots, i_t\}$ and $\{-i_1, \dots, -i_t\}$. There are $n^2$ atoms in the poset $NC^B(n)$: $n$ with exactly one non singleton block $[i] := \{i, -i\}$, and $n(n-1)$ of the type $((i, j))$ and $((i, -j))$ where $1 \le i < j \le n$. Consider now as before $n$ labeled points aligned horizontally: we identify the atoms $[i]$ with the points, and $((i, j))$ and $((i, -j))$ with arcs between $i$ and $j$ to which we assign respectively a positive and a negative sign.

Now we consider any linear order that extends the following partial order defined by Blass and Sagan [6]: an atom-identified with a positive or negative arc, or a negative vertex- is bigger than another if it strictly contains it, and a positive arc is bigger than the same arc with negative sign. By extending the
analysis of [6] which focused on the top element $\{1, 2, \dots, n, -1, -2, \dots, -n\}$, we can show that the OC cliques of size $k$ can be constructed in two ways:

* Pick an element of $\mathcal{NCAF}(n, k)$; then either choose any of the $k$ arcs and assign a negative sign to this arc and all arcs above it, or assign all arcs positive signs.

* Pick an element of $\mathcal{NCAF}(n, k-1)$, either choose any of the $k-1$ arcs and assign both a positive and a negative sign to it, or choose any of the $n$ points and mark it negatively. In both cases, assign a negative sign to all arcs that contain the chosen arc or point and assign a positive sign to all other arcs.

In both cases one checks that the corresponding join of atoms is of rank $k$ exactly in the poset. From their description above one has immediately that there are $(k+1)\mathcal{NCAF}(n, k)+(n+k-1)\mathcal{NCAF}(n, k-1)$ OC-cliques of size $k$, so we get that the growth function $G_B(t)$ for the dual braid monoid of type B is given by

$$G_B(t) = \left( \sum_{k=0}^{n} (-1)^k \binom{n}{k} \binom{n+k-1}{k} t^k \right)^{-1}$$

*Remark:* for W of type $D_n$, the poset $NC(W)$ is isomorphic to the type D noncrossing partitions $NC^D(n)$ defined in [4]; we did not find a similar order on atoms as described in types A and B in order to compute the growth function. Note that the order described in [6] cannot be used, since it is applied to a certain poset of [20] that has been since shown to be different from the poset $NC(D_n)$.

## 4.5 Koszul algebras

Let A be a finitely generated graded algebra $A = \oplus_{i \ge 0} A_i$, of the form $A = \mathbb{Z} < x_1, \dots, x_k > / I$ for an homogeneous ideal $I$, $\cdot$ A is said to be a *Koszul algebra* if $\mathbb{Z}$ admits a free resolution of A-modules, such that the matrices of all linear maps in the resolution have coefficients in $A_1$ (the resolution is then called *linear*) [19, 11].

Now, given a homogeneous monoid $M$ with atoms $S$ verifying the conditions of Section 1, the algebra $\mathbb{Z}M$ is graded. In the resolutions (1.7) and (1.9), the entries of the matrices are (up to sign) the elements $\delta_{J_i}^{s_i}$, which are the elements $x$ in $M$ such that $M_{J-\{s_i\}}x = M_J$, and the component $A_1$ of the algebra is $\mathbb{Z}S$. For the orders on atoms defined for dual monoids in type A and B, our analysis of OC cliques $J$ show that $\delta_{J_i}^{s_i} = s_i$: indeed we showed that such cliques have joins of rank $k$ in the poset, which means that in the monoid the $\text{lcm}$ is of length $|J|$ precisely. The resolution (1.9) is thus linear, and we have:

**Theorem 14.** *The monoid algebras of the dual braid monoids of type A and type B are Koszul algebras.*

By the general theory of Koszul algebras, they possess graded dual algebras called *Koszul duals*, whose homogeneous components have the dimensions of the modules $\tilde{C}_i$ in a linear resolution; in type A for instance, we have that this dual algebra is finite dimensional, and has a basis given by noncrossing alternating forests, the number of arcs determining the grading. It would be interesting to investigate the structure of these algebras, and generalize this to all finite Coxeter groups.

A promising way is certainly to investigate the descending chains for the EL-labeling of $NC(W)$ defined in [3] and relate them to the OC cliques we described in type A and B: we can prove for instance that they are identical in type A, but differ in type B.

**Acknowledgment.** The authors thank Vic Reiner for pointing out the link between Theorem 2 and Koszul algebras.
References

[1] Daniel Allcock. Braid pictures for Artin groups. *Trans. Amer. Math. Soc.*, 354(9):3455–3474 (electronic), 2002.

[2] Drew Armstrong. *Generalized noncrossing partitions and combinatorics of Coxeter groups*. PhD thesis, Cornell University, 2006. arXiv:math/0611106v2, to appear in *Memoirs of the AMS*.

[3] Christos A. Athanasiadis, Thomas Brady, Jon McCammond, and Colum Watt. *h-vectors of generalized associahedra and noncrossing partitions*. *Int. Math. Res. Not.*, pages Art. ID 69705, 28, 2006.

[4] Christos A. Athanasiadis and Victor Reiner. Noncrossing partitions for the group $D_n$. *SIAM J. Discrete Math.*, 18(2):397–417 (electronic), 2004.

[5] David Bessis. The dual braid monoid. *Ann. Sci. École Norm. Sup. (4)*, 36(5):647–683, 2003.

[6] Andreas Blass and Bruce E. Sagan. Möbius functions of lattices. *Adv. Math.*, 127(1):94–123, 1997.

[7] Egbert Brieskorn and Kyoji Saito. Artin-Gruppen und Coxeter-Gruppen. *Invent. Math.*, 17:245–271, 1972.

[8] P. Dehornoy and Y. Lafont. Homology of Gaussian groups. *Ann. Inst. Fourier (Grenoble)*, 53(2):489–540, 2003.

[9] Patrick Dehornoy and Luis Paris. Gaussian groups and Garside groups, two generalisations of Artin groups. *Proc. London Math. Soc.* (3), 79(3):569–604, 1999.

[10] Manfred Droste and Dietrich Kuske. On recognizable languages in divisibility monoids. In *Fundamentals of computation theory (Iaşi, 1999)*, volume 1684 of *Lecture Notes in Comput. Sci.*, pages 246–257. Springer, Berlin, 1999.

[11] R. Fröberg. Koszul algebras. In *Advances in commutative ring theory* (Fez, 1997), volume 205 of *Lecture Notes in Pure and Appl. Math.*, pages 337–350. Dekker, New York, 1999.

[12] Israel M. Gelfand, Mark I. Graev, and Alexander Postnikov. Combinatorics of hypergeometric functions associated with positive roots. In *The Arnold-Gelfand mathematical seminars*, pages 205–221. Birkhäuser Boston, Boston, MA, 1997.

[13] James E. Humphreys. *Reflection groups and Coxeter groups*, volume 29 of *Cambridge Studies in Advanced Mathematics*. Cambridge University Press, Cambridge, 1990.

[14] Yuji Kobayashi. Partial commutation, homology, and the Möbius inversion formula. In *Words, languages and combinatorics (Kyoto, 1990)*, pages 288–298. World Sci. Publ., River Edge, NJ, 1992.

[15] Daan Krammer. Braid groups. http://www.warwick.ac.uk/~masbal/MA4F2Braids/braids.pdf, 2005.
[16] Dietrich Kuske. Divisibility monoids: presentation, word problem, and rational languages. In *Fundamentals of computation theory (Riga, 2001)*, volume 2138 of *Lecture Notes in Comput. Sci.*, pages 227–239. Springer, Berlin, 2001.

[17] Jean Michel. A note on words in braid monoids. *J. Algebra*, 215(1):366–377, 1999.

[18] Matthieu Picantin. Explicit presentations for the dual braid monoids. *C. R. Math. Acad. Sci. Paris*, 334(10):843–848, 2002.

[19] Stewart B. Priddy. Koszul resolutions. *Trans. Amer. Math. Soc.*, 152:39–60, 1970.

[20] Victor Reiner. Non-crossing partitions for classical reflection groups. *Discrete Math.*, 177(1-3):195–222, 1997.

[21] Gian-Carlo Rota. On the foundations of combinatorial theory. I. Theory of Möbius functions. *Z. Wahrscheinlichkeitstheorie und Verw. Gebiete*, 2:340–368 (1964), 1964.

[22] Richard P. Stanley. *Enumerative combinatorics. Vol. 2*, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.

[23] Gérard Xavier Viennot. Heaps of pieces. I. Basic definitions and combinatorial lemmas. In *Combinatoire énumérative (Montreal, Que., 1985/Quebec, Que., 1985)*, volume 1234 of *Lecture Notes in Math.*, pages 321–350. Springer, Berlin, 1986.