# Growth function for a class of monoids.

IntroductionWe 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 Z as a ZM-module, where ZM 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 ZM 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, *) is a set M together with an internal law * 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 (S | R} is a presentation of the monoid M if M is isomorphic to [S.sup.*] / << R >>, where << R >> 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 [member of] 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 an homogeneous presentation.

An element a is an atom of M if a [not equal to] 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 [not equal to] 1 and b [not equal to] 1 imply that ab [not equal to] 1.

We note ZM the monoid algebra of M, whose elements are formal linear combinations of elements of M with coefficients in Z; we note also Z<< M >> the algebra of formal infinite such linear combinations. The product of [[summation].sub.m] [c.sub.m] m and [[summation].sub.m] [d.sub.m] m is in both cases given by [[summation].sub.m] [e.sub.m] m where [e.sub.m] = [[summation].sub.ab=m] [c.sub.a] [d.sub.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 M with a finite generating set S satisfying the following properties: M is atomic, left-cancellative (if a, u, v [member of] M are such that au = av, then u = v) and verifies that if a subset of 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 S having a common multiple, and let J be the set of all cliques; if J is a clique, we note [M.sub.J] its unique least common multiple, and let [m.sub.J] be the length of [M.sub.J]. Then we have our first result:

Theorem 2. Let M, S be as above. Then the following identity holds in Z<< M >>:

([summation over (J [member of] J)] [(-1).sup.[absolute value of J]] [M.sub.J]) x ([summation over (m' [member of] M) m') = [1.sub.M] (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 <S|R>. Then its growth function is equal to :

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

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 [[summation].sub.m] [c.sub.m] m [??] [[summation].sub.m] [t.sup.[absolute value of m]s] is a homomorphism from Z << M >> to 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. ?

of Theorem 2. For every element m [member of] M, let us define J(m) [subset or equal to] 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.sub.m] [subset or equal to] S, such that J(m) consists exactly of the subsets of [J.sub.m].

From now on we fix a total order < on the set of generators S. Let us fix any m [not equal to] 1. Clearly [J.sub.m] is not empty in this case, and so we can define s(m) as the maximal (for the order <) element of [J.sub.m]. Define the involution [[PHI].sub.m] on J(m) as follows: [[PHI].sub.m] (J) = J[DELTA](m)} where [DELTA] denotes the symmetric difference A[DELTA]B = (A [union] B) \ (A [intersection] B). The application [[PHI].sub.m] is simply the classical involution on the subsets of [J.sub.m]; since [[PHI].sub.m] changes the parity of [absolute value of J], we have obviously

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (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 [member of] J(m) means precisely that [M.sub.J] divides m, that is there exists m' such that [M.sub.J]m' = m: such an element m' is uniquely determined by the cancellability property. Therefore Equation (1.3) can be rewritten equivalently as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1.4)

But this quantity is precisely the coefficient [c.sub.m] of m in the left term of Equation (1.1) written in the form [[summation].sub.m] [c.sub.m]m, and so this proves Theorem 2.

1.3 Posets

We refer to [22, ch. 3] for standard notions about posets. Given a locally finite poset (P, [less than or equal to]) (i.e all intervals have a finite number of elements), the Mobius function can be defined inductively on all pairs x [less than or equal to] z by

[mu](x, x) = 1, [mu](x, z) = [summation over (x [less than or equal to] y < z)] [mu](x, y) for x < z (1.5)

Now consider a monoid M (as in Paragraph 1.2 with the divisibility relation [less than or equal to]. It forms a locally finite poset [P.sub.M] as is readily checked, so it has a Mobius 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.sub.S]] in PM for these monoids are noncrossing partitions.

Note that one can identify the algebra Z<< M >> with the incidence algebra I([P.sub.M]). From this we know that [[zeta].sub.M] = [[summation].sub.m [member of] M] m [member of] Z<< M >> has for inverse in Z<< M >> the function [[summation].sub.m] [mu](m)m, so that Theorem 2 is actually a manner of computing the Mobius 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 = ZM be the monoid algebra of M. Let B = ZJ be the free module with basis J, and [B.sub.n] be the submodule with basis [J.sub.n] the cliques of cardinal n. Consider then [C.sub.n] = [B.sub.n] [[cross product].sub.Z] A the free (right) A-module with basis [J.sub.n]. Now we fix a total order < on S, and we write cliques as words [s.sub.1] ... [s.sub.n] where [s.sub.i] < [s.sub.i + 1] for all i. For two cliques J [subset] J', we also let [[delta].sup.J'\J.sub.J] be the element of M such that [M.sub.J] [[delta].sup.J'\J.sub.J] = [M.sub.J']; it is well defined thanks to the cancellability property. We define an A-module homomorphism [d.sub.n] : [C.sub.n] [right arrow] [C.sub.n-1] by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.6)

We define also [epsilon] : A [right arrow] Z by [epsilon](m) = 0 if m [not equal to] 1 and [epsilon](1) = 1, so that we have the following sequence of A-modules and A-homomorphism (where we let k = [absolute value of S]):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.7)

Theorem 4. The complex (1.7) is a resolution of Z as an A-module.

We recall that this means that the sequence is exact, i.e. we have to check that Im([d.sub.n]) = K er([d.sub.n-1]) for all n.

Proof. Let J = [s.sub.1] ... [s.sub.n] be a clique, then one checks first that [d.sub.n-1] [omicron] [d.sub.n] = 0 for any n. Indeed the computation gives [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where we let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the clique obtained by removing the generators [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from J. Now the difference in the second term is 0 since both terms are equal to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

So we have Im([d.sub.n]) [subset or equal to] K er([d.sub.n-1]), and to check the reverse inclusion, we define a Z-homomorphism [i.sub.n+1] : [C.sub.n] [right arrow] [C.sub.n+1] in the following way: let J [cross product] m [member of] [C.sub.n], with J = [s.sub.1] ... [s.sub.n], and consider the subset of S consisting of divisors of [M.sub.J] m that are greater than [s.sub.n]; call this set [epsilon](J, m). If [epsilon](J, m) is empty, set [i.sub.n+1](J [cross product] m) := 0; otherwise, let [s.sub.n+1] be the maximum element of [epsilon](J, m) for the order <, and define [m.sub.1] by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; then set [i.sub.n+1] ([s.sub.1] ... [s.sub.n] [cross product] m) := [s.sub.1] ... [s.sub.n] [s.sub.n+1] [cross product] [m.sub.1]. One can then check that [i.sub.n-1] [omicron] [d.sub.n-1] + [d.sub.n] [omicron] [i.sub.n] = 1 for all n in a similar manner to [14], where 1 is the identity on Cn-1. This shows that Ker(dn-1) C Im(dn) and concludes the proof. ?

Now we show how this resolution gives a proof of Theorem 2:

of Theorem 2. Define the Z-module C (m) = [[cross product].sub.n][C.sub.n,m] by letting the basis of [C.sub.n,m] be the elements J [cross product] [m.sub.1] such that [absolute value of J] = n and [M.sub.J][m.sub.1] = m in M. Then the functions [d.sub.n] and [i.sub.n+1] map C(m) to itself as is immediately checked, so we obtain for every m [member of] M an exact sequence of free Z-modules:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.8)

We have that [dim.sub.Z][C.sub.n,m] is the number of pairs (J, [m.sub.1]) [member of] J x M such that [absolute value of J] = n and [M.sub.J][m.sub.1] = m; furthermore, [dim.sub.Z][Z.sub.m] is equal to 1 if m = 1 and 0 otherwise. Taking the Euler-Poincare characteristic of the resolution (1.8) gives us then Equation (1.4), which has been shown to be equivalent to Theorem 2.

Reduced resolution: Given a total order on S as above, introduce now the set [J.sub.<] [subset or equal to] J of order compatible cliques: these are the cliques [s.sub.1] ... [s.sub.n] such that for all i we have that [s.sub.i] is the largest divisor of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for the order <. We will write OC for order compatible.

Lemma 5. A clique J = [s.sub.1] ... [s.sub.n] is OC if and only if for all t [less than or equal to] n and all sequences of indices 1 [less than or equal to] [i.sub.1] < ... < [i.sub.t] [less than or equal to] n we have that sit is the maximal divisor of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof. The condition is clearly sufficient; now if J = [s.sub.1] ... [s.sub.n] is OC and 1 [less than or equal to] [i.sub.1] < ... < [i.sub.t] [less than or equal to] n, we have the inequalities [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. So all inequalities are in fact equalities and the lemma is proved. ?

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

Now let [[??].sub.i] be the A-submodule of [C.sub.i] with basis the OC cliques of size i. By the last corollary, the derivations di are well defined when restricted to these submodules, so we have a complex:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.9)

Proposition 7. The complex (1.9) is an exact resolution of Z by A-modules.

Proof. We check that the homotopy [i.sub.n+1] is still well defined when restricted to the Z-module [[??].sub.n], which will prove the proposition. Suppose J = [s.sub.1] ... [s.sub.n] is an OC clique, m [member of] M, and that the maximal element [s.sub.n+1] among the divisors of [M.sub.J]m is greater than [s.sub.n]. Then, if s divides [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], it divides also [M.sub.J]m, and thus the greatest of these divisors is [s.sub.n+1]; this shows that [s.sub.1] ... [s.sub.n+1] is an OC clique, and thus that the function [i.sub.n+1] is well defined. So now the same proof as the one of Theorem 4 can be applied, and the result follows.

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 [J.sub.<] (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 = <S | ab = ba if (a, b) [member of] I>, where S is a finite set of generators and I is a symmetric and antireflexive relation on S x 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.sub.s,t]).sub.s,t, [member of]S]] such that [m.sub.s,t] [member of] N [union] {[infinity]} and [m.sub.s,s] = 1, the Artin-Tits monoid M associated to S and M has the following presentation:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (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.sup.2] = 1 for any s [member of] S. In other words, the Coxeter Group W is defined by the following presentation :

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

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.sub.1] and [S.sub.2] of S such that S = [S.sub.1] [union] [S.sub.2] and such that any [s.sub.1] [member of] [S.sub.1] commutes with any [s.sub.2] [member of] [S.sub.2]. The irreducible finite Coxeter groups are completely classified (see [13]). This section is devoted to the three infinite families [A.sub.n], [B.sub.n] and [D.sub.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.sub.n], [B.sub.n], [D.sub.n], we write the corresponding growth function of the Artin- Tits monoid [G.sub.X](t) = 1/[H.sub.x](t)], where [H.sub.X] is the polynomial [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], in which the sum is over all subsets J of generators and [m.sub.J] is the length of the lcm [M.sub.J] of J. We describe in the following such lcms.

3.2 Type A

The Artin monoid A([A.sub.n]) is in fact the classical braid monoid on n +1 strands. Hence, it admits the following presentation:

A([A.sub.n]) = <[[sigma].sub.1], ..., [[sigma].sub.n] | [[sigma].sub.i] [[sigma].sub.i+1] [[sigma].sub.i] = [[sigma].sub.i+1] [[sigma].sub.i] [[sigma].sub.i+1] and [[sigma].sub.i] [[sigma].sub.j] = [[sigma].sub.j] [[sigma].sub.i] if [absolute value of i - j] [less than or equal to] 2).

We denote [[summation].sub.n] = {[[sigma].sub.1], ..., [[sigma].sub.n]} the set of Artin generators. To compute the lcm of a subset J of [[summation].sub.n], let us consider a partition J = [J.sub.1] [union] ... [union] [J.sub.p] such that any [[sigma].sub.i] and [[sigma].sub.j] in J belong to the same block of this partition if and only if j = i [+ or -] 1.

We set [[DELTA].sub.{[[sigma].sub.j],[[sigma].sub.j+1], ..., [[sigma].sub.j+i] = ([[sigma].sub.j]) ([[sigma].sub.j+1] + [[sigma].sub.j]) ... ([[sigma].sub.j+i] ... [[sigma].sub.j+1] [[sigma].sub.j]), then [M.sub.J] is equal to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [m.sub.J] = [[summation].sup.p.sub.i=1]([absolute value of [J.sub.i]]( [absolute value of [J.sub.i]] + 1)/2).

In this case, no explicit formula is known for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] but the form of the lcms leads easily to the following recurrence relation:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

3.3 Type B

The Artin monoid A([B.sub.n]) of type B is the monoid whose set of generators is [[summation].sub.n] = {[[sigma].sub.1], ..., [[sigma].sub.n]} and which is submitted to the following relations:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

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].sub.1], ..., [[sigma].sub.n]}, we write J = [J.sub.1] [union] ... [union] [J.sub.p], where the properties satisfied by this partition are the same as those given above. Because of the particular role of [[sigma].sub.1], three different cases have to be considered to compute the lcm of J. Either [[sigma].sub.1] [not member of] J or [[sigma].sub.1] [member of] J and [[sigma].sub.2] [not member of] J and in these cases [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] just as before. Now if [[sigma].sub.1], [[sigma].sub.2] [member of] J, without loss of generality we assume that [[sigma].sub.1] [member of] [J.sub.1], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with [[sigma].sub.m] the maximal element of [J.sub.1] for the classical ordering [[sigma].sub.1] < [[sigma].sub.2] < ... < [[sigma].sub.n] of [[summation].sub.n].

The expression of lcms enable to obtain the following recurrence relation for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], for n [greater than or equal to] 1 (with the convention [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (t) = 1):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

3.4 Type D

The Artin monoid A([D.sub.n]) of type D is the monoid whose set of generators is [[summation].sub.n] = {[tau], [[sigma].sub.1], ..., [[sigma].sub.n-1]} and submitted to the following relations:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (3.1)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3.2)

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

Let J [subset] [[summation].sub.n], because of the symmetric role of [tau] and [[sigma].sub.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].sub.1] belongs to J, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where the [J.sub.i] as defined in Paragraph 3.2 (it suffices to replace each occurrence of [[sigma].sub.1] in [M.sub.J] by [tau] to deal with the symmetric case). If [tau] and [[sigma].sub.1] belong both to J, we moreover assume that [[sigma].sub.1] [member of] [J.sub.1], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with [[sigma].sub.m] the maximal element of [J.sub.1] for the classical ordering [[sigma].sub.1] < [[sigma].sub.2] < ... < [[sigma].sub.n] of [[summation].sub.n].

Once again, this leads to the following recurrence relation for the denominator of the generating function of A([D.sub.n]), for n [greater than or equal to] 2 (by convention [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

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.sup.-1], s [member of] S}; T is obviously a generating set for W, and we let [l.sub.T](w) = k where k is the minimal number of reflections [t.sub.i] [member of] T such that w = [t.sub.1] * [t.sub.k]; the function [l.sub.T] is then invariant under conjugation, that is we have [l.sub.T](w) = [l.sub.T]([zwz.sup.-1]) for any two elements w, z [member of] W. Then one defines a partial order on W by setting w [[less than or equal to].sub.T] z if [l.sub.T] (w) + [l.sub.T] ([w.sup.-1] z) = [l.sub.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 [member of] W, one defines a poset NC(W, c) = [1, c] with respect to the partial order [[less than or equal to].sub.T]. Since [l.sub.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 [[summation].sub.rk(x)=k] [mu](x) of the Mobius 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 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.sub.m-1] (cf. [22]) and that they are in bijection with Motzkin paths with m - 1 steps: these are paths in [N.sup.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

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

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 [greater than or equal to] 2 points, there is necessarily an edge between 1 and n. Destroying that arc, we get two smaller noncrossing alternating trees, on i and n - i points say. By induction, we can attach a binary tree to each of these smaller trees; let [T.sub.1] and [T.sub.2] be these two trees respectively, and create a new root (corresponding to the deleted arc) with left subtree [T.sub.1] and right subtree [T.sub.2]. The inverse bijection is immediate.

[FIGURE 1 OMITTED]

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 [1, n] 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,..., 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 T1 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.sub.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.

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) = (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.sup.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 [member of] B and k, l [member of] B' such that i < k < j < l. Let [NC.sup.A](n) be the poset of noncrossing partitions of size n ordered by refinement.

[FIGURE 2 OMITTED]

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.sup.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 [less than or equal to] 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 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 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

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

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.sup.B] (n), which is defined as the subposet of [NC.sup.A] (2n) formed by partitions of {1,2, ..., n, -1, -2, ..., -n} that are invariant under the bijection i [??] -i. We note (([i.sub.1], ..., [i.sub.t])) the partition with non singleton blocks {[i.sub.1], ..., [i.sub.t]} and {-[i.sub.1], ..., -[i.sub.t]}. There are [n.sup.2] atoms in the poset [NC.sup.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 [less than or equal to] i < j [less than or equal to] 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, ..., n, -1 , -2, ..., -n}, we can show that the OC cliques of size k can be constructed in two ways:

* Pick an element of 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 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)NCAF(n, k)+(n+k -1)NCAF(n, k-1) OC-cliques of size k, so we get that the growth function GB (t) for the dual braid monoid of type B is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Remark: for W of type [D.sub.n], the poset NC(W) is isomorphic to the type D noncrossing partitions [NC.sup.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.sub.n]).

4.5 Koszul algebras

Let A be a finitely generated graded algebra A = [[product].sub.i] [greater than or equal to]0][A.sub.i],of the form A = Z < [x.sub.1], ..., [x.sub.k] >/I for an homogeneous ideal I,. A is said to be a Koszul algebra if Z admits a free resolution of A-modules, such that the matrices of all linear maps in the resolution have coefficients in A1 (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 ZM is graded. In the resolutions (1.7) and (1.9), the entries of the matrices are (up to sign) the elements [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which are the elements x in M such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and the component [A.sub.1] of the algebra is ZS. For the orders on atoms defined for dual monoids in type A and B, our analysis of OC cliques J show that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]: indeed we showed that such cliques have joins of rank k in the poset, which means that in the monoid the lcm is of length [absolute value of 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 C 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 Dn. SIAM J. Discrete Math., 18(2):397-U7 (electronic), 2004.

[5] David Bessis. The dual braid monoid. Ann. Sci. Ecole Norm. Sup. (4), 36(5):647-683, 2003.

[6] Andreas Blass and Bruce E. Sagan. Mobius 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 (Iasi, 1999), volume 1684 of Lecture Notes in Comput. Sci., pages 246-257. Springer, Berlin, 1999.

[11] R. Froberg. Koszul algebras. In Advances in commutative ring theory (Fez, 1997), volume 205 of Lecture Notes in Pure andAppl. 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. Birkhauser 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 Mobius 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 Mobius 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] G6rard Xavier Viennot. Heaps of pieces. I. Basic definitions and combinatorial lemmas. In Combinatoire enumerative (Montreal, Que., 1985/Quebec, Que., 1985), volume 1234 of Lecture Notes in Math., pages 321-350. Springer, Berlin, 1986.

Marie Albenque (1) and Philippe Nadeau (2)

(1) LIAFA, CNRS-Universite Paris Diderot - Paris 7, case 7014, 75205 Paris Cedex 13, France.

(2) Fakultat fur Mathematik, University of Vienna, Nordbergstrasse 15, 1090 Vienna, Austria.

Printer friendly Cite/link Email Feedback | |

Author: | Albenque, Marie; Nadeau, Philippe |
---|---|

Publication: | DMTCS Proceedings |

Article Type: | Report |

Geographic Code: | 4EUFR |

Date: | Jan 1, 2009 |

Words: | 7621 |

Previous Article: | Unital versions of the higher order peak algebras. |

Next Article: | Universal cycles for permutation classes. |

Topics: |