Séminaire Lotharingien de Combinatoire 72 (2014), Article B72b

DUAL GARSIDE STRUCTURE OF BRAIDS AND FREE CUMULANTS OF PRODUCTS

PHILIPPE BIANE AND PATRICK DEHORNOY

Abstract. We count the n-strand braids whose normal decomposition has length at most 2 in the dual braid monoid B_{n}^{+∗} by reducing the question to a computation of free cumulants for a product of independent variables, for which we establish a general formula.

1. Introduction

A Garside structure on a group G consists of a generating family that gives rise to distinguished decompositions of a particular type, leading in good cases to an automatic structure on G and, from there, to solutions of the word and conjugacy problems of G [7]. In the case of the n-strand Artin braid group B_{n}, two Garside structures are known: the so-called classical Garside structure, in which the distinguished generating family (the “Garside base”) is a copy of the symmetric group 𝔖_{n} [9, Chapter 9], and the so-called dual Garside structure, in which the Garside base is a copy of the family NC(n) of all size n noncrossing partitions [1].

Whenever a finite Garside base S is given on a group G, natural counting problems arise, namely the problem of counting how many elements of the group G or of the submonoid generated by S have length (at most) ℓ with respect to S. Call S-normal the distinguished decompositions associated with a Garside base S; as S-normal sequences happen to be geodesic, the above question amounts to counting the Snormal sequences of length ℓ. Moreover, since S-normality is a purely local property, the central question is to determine S-normal sequences of length two, the general case then corresponding to taking the ℓth power of the incidence matrix associated with length two.

Initially motivated by the investigation of the logical strength of certain statements involving the standard braid ordering [5], the above mentioned counting questions in the case of the classical Garside structure of braids have been addressed in [6], leading to nontrivial results involving Solomon’s descent algebra and to natural conjectures, like the one established in [11] using the theory of quasi-symmetric functions.

2010 Mathematics Subject Classification. 20F36, 05A17, 46L54.

Key words and phrases. braid group; dual braid monoid; Garside normal form; generating function; free cumulants; independent random variables; noncrossing partitions.

The aim of this paper is to address similar questions in the case of the dual Garside structure of braids and to obtain an explicit determination of the generating function for the number of normal sequences of length two. In the statement of the corresponding result below, the symbol Cat_{n} denotes the nth Catalan number \frac{1}{n+1} \binom{2n}{n}.

Theorem 1.1. Let b_{n,2}^{∗} be the number of braids of length at most 2 in the dual braid monoid B_{n}^{+∗}. Then the function R(z) = 1 + ∑_{n⩾1} b_{n,2}^{∗}z^{n} is connected with M(z) = 1 + ∑_{n⩾1} Cat_{n}^{2}z^{n} by the equality

(1.1)  R(zM(z)) = M(z).

This formula, which inductively determines the numbers b_{n,2}^{∗}, will be deduced from a general formula for computing the free cumulants of a product of independent random variables.

Free cumulants were invented by Roland Speicher in order to perform computations with free random variables [14]. In particular, free cumulants give a simple way of computing the free additive convolution of two probability measures on the real line, namely the free cumulants of the sum of two free random variables are the sums of the free cumulants of the variables. Free cumulants also appear when one tries to compute the free cumulants of a product of free random variables, although in a more complicated way.

Here is the general formula we establish (the notations are standard and explained in Section 3):

Theorem 1.2. Let X_{1}, …, X_{k} be a family of commuting independent random variables, and let R_{n}^{(i)} be the free cumulants of X_{i}. Then the free cumulants of the product X_{1}X_{2} … X_{k} are given by

(1.2)  R_{n} = ∑_{π_{1}∨···∨π_{k}=1_{n}} ∏_{i} R_{π_{i}}^{(i)},

the sum being over all k-tuples of noncrossing partitions in NC(n) whose join is the largest partition.

Since this result is purely combinatorial, we give also another formulation, without reference to free probability.

Theorem 1.3. For i = 1, …, k, let R_{n}^{(i)} and M_{n}^{(i)} be families of commuting indeterminates, with generating functions

R^{(i)}(z) = 1 + ∑_{n⩾1} R_{n}^{(i)}z^{n} and M^{(i)}(z) = 1 + ∑_{n⩾1} M_{n}^{(i)}z^{n}

related by

R^{(i)}(zM^{(i)}(z)) = M^{(i)}(z).

Then the generating functions of

M_{n} = ∏_{i} M_{n}^{(i)} and R_{n} = ∑_{π_{1}∨···∨π_{k}=1_{n}} ∏_{i} R_{π_{i}}^{(i)},

the latter sum being over all k-tuples of noncrossing partitions in NC(n) whose join is the largest partition, are related by

R(zM(z)) = M(z).

Free cumulants are specifically designed to deal with highly noncommuting objects. Therefore it may come as a surprise that there is also a simple formula for computing free cumulants of a product of independent commuting random variables, in terms of the free cumulants of the factors. As a matter of fact, such a formula also holds, with appropriate modifications, for classical and Boolean cumulants.

The organization of the paper is as follows. In Section 2, we recall the description of the dual Garside structure of braid groups and raise the induced counting questions. In Section 3, we review basic definitions about free cumulants and establish Theorem 1.2. This part can be read independently of the rest of the paper. In Section 4, we apply the result of Section 3 to braids and conclude with further questions and one additional result about the determinant of the involved incidence matrix.

2. The dual Garside structure of braids

Braid groups. For n ⩾ 1, the n-strand braid group B_{n} is the group defined by the presentation

(2.1) B_{n} = ⟨σ_{1}, …, σ_{n−1} | \begin{matrix}σ_{i}σ_{j} = σ_{j}σ_{i} & for |i − j| ⩾ 2 \\ σ_{i}σ_{j}σ_{i} = σ_{j}σ_{i}σ_{j} & for |i − j| = 1 \end{matrix} ⟩ .

The group B_{n} is both the group of isotopy classes of n-strand geometric braids, the mapping class group of an n-punctured disk, and the fundamental group of the configuration space obtained by letting the symmetric group act on the complement of the diagonal hyperplanes in ℂ^{n} [3].

Garside structures. A Garside base in a group G is a subset S of G such that every element of G admits a decomposition of a certain syntactic form in terms of the elements of S, namely a symmetric S-normal decomposition in the following sense.

Definition 2.1 ([7]). Assume that G is a group and S is included in G.

(i) A finite S-sequence (s_{1}, …, s_{d}) is called S-normal if, for i < d, every element of S left-dividing s_{i}s_{i+1} left-divides s_{i}, where “f leftdivides g” means “f^{−1}g lies in the submonoid Ŝ of G generated by S”.

(ii) A pair of finite S-sequences ((s_{1}, …, s_{d}), (t_{1}, …, t_{e})) is called symmetric S-normal if (s_{1}, …, s_{d}) and (t_{1}, …, t_{e}) are S-normal and, in addition, the only element of S left-dividing s_{1} and t_{1} is 1.

(iii) A Garside base for G is a subfamily S of G such that every element g of G admits a symmetric S-normal decomposition, meaning that we have g = t_{e}^{−1} … t_{1}^{−1}s_{1} … s_{d} for some symmetric S-normal pair ((s_{1}, …, s_{d}), (t_{1}, …, t_{e})).

Every group G is trivially a Garside base in itself, and the notion is interesting only when S is small, typically when G is infinite and S is finite or, at least, is properly included in G. Under mild assumptions, the existence of a finite Garside base implies good properties for the group G such as the existence of an automatic structure or the decidability of the word and conjugacy problems.

Whenever S is a finite generating family in a group G, it is natural to consider the numbers

N_{d}^{S} = #{g ∈ G | ∥g∥_{S} = d},

where ∥g∥_{S} is the S-length of g, that is, the smallest ℓ such that g can be expressed as s_{1}^{e_{1}} … s_{ℓ}^{e_{ℓ}} with s_{1}, …, s_{ℓ} in S and e_{1}, …, e_{ℓ} in {±1}. In the case of a Garside base, symmetric S-normal decompositions are (essentially) unique, and they are geodesic. Therefore, N_{d}^{S} can be identified with the number of length d symmetric S-normal sequences. In such a context, the submonoid Ŝ of G generated by S is the family of all elements of G whose symmetric S-normal decomposition has an empty denominator, that is, of all elements that admit an S-normal decomposition. Thus, it is also natural to introduce the number

N_{d,+}^{S} = #{g ∈ Ŝ | ∥g∥_{S} = d},

which, by the above remark, is the number of S-normal sequences of length d. It then follows from the definition that a sequence (s_{1}, …, s_{d}) is S-normal if and only if every length two subsequence is S-normal, and the basic question is therefore to investigate the numbers

(2.2)  N_{2,+}^{S} = #{(s_{1}, s_{2}) ∈ S^{2} | (s_{1}, s_{2}) is S-normal}.

The classical Garside structure of B_{n}. In the case of the braid group B_{n}, two Garside structures are known. The first one, often called classical, involves permutations. By (2.1), mapping σ_{i} to the transposition (i, i+1) induces a surjective homomorphism pr_{n} : B_{n} → 𝔖_{n}. The positive braid diagrams in which any two strands cross at most once (“simple braids”) provide a set-theoretic section for pr_{n}, whose image is a copy S_{n} of 𝔖_{n} inside B_{n}. The family S_{n} is a Garside base in B_{n} [9, Chapter 9], the submonoid of B_{n} generated by S_{n} being the submonoid Bn^{+} generated by σ_{1}, …, σ_{n−1} [10]. The associated numbers N_{d,+}^{S_{n}} have been investigated in [6]. In particular, writing b_{n,d} for N_{d,+}^{S_{n}}, it is shown that the numbers b_{n,2} are determined by the recurrence

(2.3)  b_{n,2} = ∑_{i=0}^{n−1}(−1)^{n+i+1}\binom{n}{i}^{2}b_{i,2},

and that the double exponential series ∑ b_{n,2}z^{n}/(n!)^{2} is the inverse of the Bessel function J_{0}(\sqrt{z}).

The dual Garside structure of B_{n}. It is known since [4] that, for every n, there exists an alternative Garside structure on B_{n}, corresponding to the dual Garside base S_{n}^{∗}, whose elements are in one-to-one correspondence with the noncrossing partitions of {1, 2, …, n}. The question then naturally arises of determining the corresponding numbers N_{d}^{S_{n}^{∗}} and N_{d,+}^{S_{n}^{∗}}. Here we shall concentrate on the latter, hereafter denoted b_{n,d}^{∗}, and specifically on b_{n,2}^{∗}. By (2.2), we have (2.4) b_{n,d}^{∗} = #{(s_{1}, …, s_{d}) ∈ (S_{n}^{∗})^{d} | (s_{i}, s_{i+1}) is S_{n}^{∗}-normal for all i < n}.

In order to compute the numbers b_{n,d}^{∗}, we shall describe the correspondence between S_{n}^{∗} and noncrossing partitions and interpret the S_{n}^{∗}-normality condition in terms of the latter.

We recall that a set partition of the set {1, …, n} is called noncrossing if there is no quadruple 1 ⩽ i < j < k < l ⩽ n such that i and k belong to some block of the partition, whereas j and l belong to another block. The set of noncrossing partitions of {1, …, n}, denoted by NC(n), is a poset for the reverse refinement order: for two partitions π and π′ we have π ⩽ π′ if and only if each block of π is included in some block of π′. With this order, NC(n) is a lattice, with largest element 1_{n} — the partition with only one block — and smallest element 0_{n} — the partition into n singletons. We denote by π_{1} ∨ ⋯ ∨ π_{d} the join of the partitions π_{1}, …, π_{d}.

Definition 2.2 ([4]). For 1 ⩽ i < j, put

a_{i,j} = σ_{i} … σ_{j−2} σ_{j−1} σ_{j−2}^{−1} … σ_{i}^{−1}

in B_{n}. The dual braid monoid B_{n}^{+∗} is the submonoid of B_{n} generated by all elements a_{i,j}, and S_{n}^{∗} is the family of all left-divisors of Δ_{n}^{∗} in B_{n}^{+∗}, with Δ_{n}^{∗} = σ_{1}σ_{2} … σ_{n−1}.

Note that σ_{i} = a_{i,i+1} holds for every i, hence B_{n}^{+∗} includes Bn^{+}, a proper inclusion for n ⩾ 3.

Proposition 2.3 ([4]). The family S_{n}^{∗} is a Garside base for the group B_{n}.

It is convenient to associate with the n-strand braid a_{i,j} a graphical representation as the chord (i, j) in a disk with n marked vertices on the border as shown on the right. ^{1ij n}

Then the correspondence between the elements of S_{n}^{∗} and noncrossing partitions stems from the following observation.

Lemma 2.4 ([1]). For P a union of disjoint polygons in the n-marked disk, say P = P_{1} ∪ ⋯ ∪ P_{d}, let a_{P} = a_{P_{1}} … a_{P_{d}}, with

a_{P_{k}} = a_{i_{1},i_{2}}a_{i_{2},i_{3}} … a_{i_{n_{k}−1},i_{n_{k}}} ,

where (i_{1}, …, i_{n_{k}}) is a clockwise enumeration of the vertices of P_{k}. Then:

(i) The braid a_{P} only depends on P and not on the order of enumeration.

(ii) Mapping P to a_{P} establishes a bijection between unions of disjoint polygons in the n-marked disk and elements of S_{n}^{∗}.

It is standard to define a bijection between noncrossing partitions of the set {1, …, n} and unions of disjoint polygons in the n-marked disk, yielding the announced correspondence. Noncrossing partitions can be embedded into the symmetric group, using geodesics in the Cayley graph [2]: this amounts to mapping a union of polygons to the product of the cycles obtained by enumerating their vertices in clockwise order. Note that, although noncrossing partitions may be viewed as particular permutations, the associated braids need not coincide: for instance, the cycle (13), which corresponds to the partition {{1, 3}, {2}}, is associated in S_{3}^{∗} with the braid a_{1,3}, that is, σ_{1}σ_{2}σ_{1}^{−1}, whereas it is associated with σ_{1}σ_{2}σ_{1} in S_{3}.

For π a noncrossing partition of {1, …, n}, we denote by a_{π} the associated element of S_{n}^{∗}. For instance, for π = {{1}, {2, 8}, {3, 5, 6}, {4}, {7}}, we find a_{π} = a_{2,8}a_{3,5}a_{5,6}, as shown on the right.

1 2 3 4 5 6 7 8

Under the above correspondence, Δ_{n}^{∗} corresponds to the (unique) ngon in the n-marked disk, hence to the (noncrossing) partition 1_{n} with one block. Due to (2.4), the numbers b_{n,d}^{∗} are determined by

(2.5) b_{n,d}^{∗} = #{(π_{1}, …, π_{d}) ∈ NC(n)^{d} | (a_{π_{i}}, a_{π_{i+1}}) is S_{n}^{∗}-normal for all i < d},

and we have to recognize when the braids associated with two partitions make an S_{n}^{∗}-normal sequence.

By construction, the Garside base S_{n}^{∗} is what is called bounded by the element Δ_{n}^{∗}, that is, it exactly consists of the left-divisors of Δ_{n}^{∗} in B_{n}^{+∗}. In this case, the normality condition takes a simple form.

Lemma 2.5 ([7, Chapter VI]). Assume that S is a Garside base for a group G, and S is bounded by an element Δ. Then, for s, t in S, the pair (s, t) is S-normal if and only if the only common left-divisor of ∂s and t in the monoid Ŝ is 1, where ∂s is the element satisfying s · ∂s = Δ.

We are thus left with the question of recognizing, in terms of noncrossing partitions (or of the corresponding unions of polygons), when a braid a_{i,j} left-divides the braid a_{π}, and what the partition π′ satisfying a_{π′} = ∂a_{π} is.

Lemma 2.6 ([1]). Assume that π lies in NC(n). Then:

(i) For 1 ⩽ i < j ⩽ n, the braid a_{i,j} left-divides a_{π} in B_{n}^{+∗} if and only if the chord (i, j) lies inside the union of the convex hulls of the polygons associated with π.

(ii) We have ∂a_{π} = a\overline{π}, where \overline{π} is the Kreweras complement of π (as defined in [12]).

Putting pieces together, we obtain:

Proposition 2.7. For all n and d, the number b_{n,d}^{∗} of n-strand braids in B_{n}^{+∗} that have length at most d with respect to the Garside base S_{n}^{∗} is given by

(2.6) b_{n,d}^{∗} = #\{(π_{1}, …, π_{d}) ∈ NC(n)^{d} | \overline{π_{i}} ∧ π_{i+1} = 0_{n} for all i < d\}.

1 2 3 4 5 6 7 8 9 10 11 12  1 2 3 4 5 6 7 8 9 10 11 12  1 2 3 4 5 6 7 8 9 10 11 12

Figure 1. The polygons associated with a partition π and with its image under the complement map ∂ and ∂^{2}: the red partition is the Kreweras complement of π, and repeating the operation leads to the image of the initial partition under a rotation by 2π/n, corresponding to conjugating under Δ_{n}^{∗} in B_{n}^{+∗}.

Proof. By Lemma 2.6 (i), saying that 1 is the only common left-divisor of a_{π} and a_{π′} in B_{n}^{+∗} amounts to saying that the convex hulls of the polygons associated with π and π′ have no chord in common, hence are disjoint, so, in other words, that the meet of π and π′ in the lattice NC(n) is the minimal partition 0_{n}. By Lemma 2.6 (ii), this condition has to be applied to \overline{π_{i}} and π_{i+1} for every i. □

3. Free cumulants

In view of Proposition 2.7, we have to count sequences of noncrossing partitions satisfying lattice constraints involving adjacent entries. We shall derive partial results from a general formula expressing the free cumulants of a product of independent random variables.

3.1. Noncrossing partitions and free cumulants. We recall some basic facts. More details can be found in [14].

Given a sequence of indeterminates T_{1}, …, T_{l}, … and a noncrossing partition π in NC(n), we define

(3.1)  T_{π} = ∏_{p∈π} T_{|p|},

where the product ranges over all blocks p of π, and |p| is the number of elements of p in {1, …, n}.

Two sequences of indeterminates M_{1}, …, M_{l}, … and R_{1}, …, R_{l}, … are related by the moment-cumulant formula if, for every n, we have

(3.2)  M_{n} = ∑_{π∈NC(n)} R_{π}.

It is easy to see that this equation can be inverted, and the R_{l} can be expressed as polynomials in the M_{l}. In fact, introducing the generating functions

M(z) = 1 + ∑_{l=1}^{∞} z^{l}M_{l}, R(z) = 1 + ∑_{l=1}^{∞} z^{l}R_{l},

we can recast the relation (3.2) in the form

(3.3)  R(zM(z)) = M(z).

It follows from (3.3) and the Lagrange inversion formula that

(3.4) M_{n} is the coefficient of z^{n} in the expansion of \frac{1}{n + 1}R(z)^{n+1}.

If the M_{l} are the moments of a probability measure (or a random variable), then the quantities R_{l} are called the free cumulants of the probability measure (or random variable).

Recall that a semi-circular variable is a random variable with moments M_{2n+1} = 0, M_{2n} = Cat_{n}, and free cumulants R_{2} = 1, R_{n} = 0 for n ≠ 2. One can see that the square of a semi-circular variable has moments M_{n} = Cat_{n} and free cumulants R_{n} = 1.

Free cumulants of a product of independent random variables. Now we establish the general formula for free cumulants of products of independent random variables stated as Theorem 1.2 in the introduction.

Proof of Theorem 1.2. Let M_{n}^{(i)} be the moments of X_{i}. Let us write the moment-cumulant formula for each of the variables in the product X_{1}X_{2} … X_{k}. As the nth moment of X_{1}X_{2} … X_{k} is

M_{n} = M_{n}^{(1)} … M_{n}^{(k)},

we have

M_{n} = M_{n}^{(1)} … M_{n}^{(k)} = ∑_{π_{1},...,π_{k}∈NC(n)} ∏_{i=1}^{k} R_{π_{i}}^{(i)}.

Let us now decompose the sum on the right hand side according to the value of π = π_{1} ∨ ⋯ ∨ π_{k}. Since π_{i} ⩽ π holds, each block of π_{i} is included in some block of π. Let p be a block of π. The intersections π_{i,p} := π_{i} ∩ p form a partition of the set p. If we identify p with {1, …, |p|} by the only increasing bijection, then the sets π_{i,p} form a noncrossing partition of {1, …, |p|}. Furthermore we have

π_{1,p} ∨ ⋯ ∨ π_{n,p} = 1_{|p|},

whence

M_{n} = ∑_{π∈NC(n)} ∏_{p∈π} [ ∑_{π_{1,p}∨···∨π_{n,p}=1_{|p|}} ∏_{i} R_{π_{i,p}}^{(i)}] .

Defining the sequence Q_{n} by

Q_{n} = ∑_{π_{1}∨···∨π_{n}=1_{n}} ∏_{i} R_{π_{i}}^{(i)},

we obtain

M_{n} = ∑_{π∈NC(n)} ∏_{p∈π} Q_{|p|} = ∑_{π∈NC(n)} Q_{π}.

Then it follows from (3.2) that the quantities Q_{n} are the free cumulants of the sequence of moments M_{1}, …, M_{n}, …. □

The above argument is closely related to an argument in [17]. The first author would like to thank Roland Speicher for pointing out this reference.

Corollary 3.1. The number of k-tuples (π_{1}, …, π_{k}) in NC(n)^{k} satisfying π_{1} ∨⋯∨π_{k} = 1_{n} is the nth free cumulant of the variable X_{1}^{2} ⋯ X_{k}^{2}, where X_{1}, …, X_{k} are independent centered semi-circular variables of variance 1.

Proof. If we pick R_{m}^{(i)} = 1 for all i and m in Theorem 1.2, then R_{n} counts the k-tuples (π_{1}, …, π_{k}) in NC(n)^{k} satisfying π_{1} ∨⋯∨π_{k} = 1_{n}, and the corresponding moments M_{n}^{(i)} are the Catalan numbers (see the end of Section 3.1). □

Classical and Boolean cumulants. Cumulants can also be defined using the lattice of all set partitions of {1, …, n} (this is the classical case, studied by Rota, Schützenberger, …), or the lattice of interval partitions (these are the Boolean cumulants, see [16]). In both cases, it is immediate to check that the proof of Theorem 1.2 goes through and gives a formula for computing the corresponding cumulants of a product.

4. Back to braids

We now apply the result of Section 3 to braids.

Incidence matrices. For every n, there exists a binary relation on NC(n) that encodes S_{n}^{∗}-normality. We introduce the associated incidence matrix.

Definition 4.1. For n ⩾ 2, we let A_{n}^{∗} be the Cat_{n}×Cat_{n}-matrix whose entries are indexed by pairs of noncrossing partitions, and such that (A_{n}^{∗})_{π,π′} is 1 (respectively 0) if \overline{π} ∧ π′ = 0_{n} holds (respectively fails).

For instance, if the partitions of {1, 2, 3} are enumerated in the or-

der  ,  ,  ,  ,  , the matrix A_{3}^{∗} is ( \begin{matrix}1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \end{matrix} ). It

follows from the properties of 0_{n} and 1_{n} that the column of 0_{n} and the row of 1_{n} in A_{n}^{∗} contain only ones, whereas the row of 0_{n}, with the exception of its 0_{n}-entry, and the column of 1_{n}, with the exception of its 1_{n}-entry, contain only zeroes.

Proposition 4.2. For all n and d ⩾ 1, the number b_{n,d}^{∗} is the sum of all entries in the matrix (A_{n}^{∗})^{d−1}; in particular, b_{n,2}^{∗} is the number of positive entries in A_{n}^{∗}.

Proof. For π in NC(n) let b_{n,d}^{∗}(π) be the number of S_{n}^{∗}-normal sequences of length d whose last entry is π. By Proposition 2.6, a length d sequence (π_{1}, …, π_{d−1}, π) contributes to b_{n,d}^{∗}(π) if and only if (π_{1}, …, π_{d−1}) contributes to b_{n,d−1}^{∗}(π_{d−1}) and (π_{d−1}, π) contributes to b_{n,2}^{∗}(π), that is, (A_{n}^{∗})_{π_{d−1},π} = 1 holds. We deduce

b_{n,d}^{∗}(π) = ∑_{π′∈NC(n)} b_{n,d−1}^{∗}(π′) · (A_{n}^{∗})_{π′,π}.

From there, an obvious induction shows that b_{n,d}^{∗}(π) is the πth entry in (1, 1, …, 1) (A_{n}^{∗})^{d−1}, and the result follows by summing over all π. □

(Note that, for d = 1, Proposition 4.2 gives b_{n,1}^{∗} = Cat_{n}, which is indeed the sum of all entries in the size Cat_{n} identity-matrix.)

Using Theorem 1.2, we can now complete the proof of Theorem 1.1.

Proof of Theorem 1.1. By Proposition 4.2, b_{n,2}^{∗} is the number of positive entries in the matrix A_{n}^{∗}, that is, the number of pairs (π, π′) in NC(n)^{2} satisfying \overline{π} ∧ π′ = 0_{n}. As the Kreweras complement is bijective, this number is also the number of pairs (π, π′) in NC(n)^{2} satisfying π ∧π′ = 0_{n}. By complementation, the latter is also the number of pairs satisfying π ∨ π′ = 1_{n}. By Corollary 3.1, this number is the nth free cumulant of X_{1}^{2}X_{2}^{2}, where X_{1}, X_{2} are independent centered semi-circular variables of variance 1. The moments of the latter are the squares of the Catalan numbers, so (3.3) gives the expected result. □

Further questions. It is easy to compute the numbers b_{n,d}^{∗} for small values of n and d, see Table 1.

d  1  2  3  4  5  6  7
b_{1,d}^{∗} 1  1  1  1  1  1  1
b_{2,d}^{∗} 2  3  4  5  6  7  8
b_{3,d}^{∗} 5 15  83  177  367  749 1 515
b_{4,d}^{∗} 14 99  556  2 856  14 122  68 927 334 632
b_{5,d}^{∗} 42 773 11 124 147 855 1 917 046 24 672 817
b_{6,d}^{∗} 132 6 743 266 944 9 845 829 356 470 124

Table 1. The number b_{n,d}^{∗} of n-strand braids of length at most d in the dual braid monoid B_{n}^{+∗}: the first column (d = 1) contains the Catalan numbers, whereas the second column contains the sequence specified in Theorem 1.1, which is A168344 in [15].

It is natural to ask for a description of the columns in Table 1 beyond the first two ones. The characterization of Theorem 1.1 does not extend to d ⩾ 3. For instance, we have

b_{n,3}^{∗} = \{(π_{1}, π_{2}, π_{3}) ∈ NC(n)^{3} | \overline{π_{1}} ∧ π_{2} = 0_{n} and \overline{π_{2}} ∧ π_{3} = 0_{n}\}.

Replacement of ∧ and 0_{n} by ∨ and 1_{n} is easy, but the Kreweras complement cannot be forgotten in this case.

On the other hand, attempts to describe the rows in Table 1 lead to further natural questions. By Proposition 4.2, the generating function of the numbers b_{n,d}^{∗} is rational for every n, and b_{n,d}^{∗} can be expressed in terms of the dth powers of the eigenvalues of the matrix A_{n}^{∗}. For instance, we easily find b_{3,d}^{∗} = 6 · 2^{d} − 2d − 5 for every d, as well as b_{3,d}^{∗}(π) = 2^{d+1} − 1 for π ≠ 0_{n}, 1_{n} (as above, we write b_{n,d}^{∗}(π) for the number of braids with a normal form finishing with π). Very little is known for n ⩾ 4.

It would be of interest to compute, or at at least approximate, the spectral radius of the matrix A_{n}^{∗}. Here are the first values.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ ρ(A_{n}^{∗}) & 1 & 1 & 2 & 4.83 … & 12.83 … & 35.98 … & 104.87 … \end{matrix}

Table 2. Spectral radius of the incidence matrix A_{n}^{∗}

A determinant. Although we are not able to compute the eigenvalues of the matrix A_{n}^{∗} explicitly, we can give a closed formula for its determinant.

Theorem 4.3. For every n, we have

| det(A_{n}^{∗})| = ∏_{k=2}^{n} Cat\binom{2n−k−1}{n−1}_{k−1}.

Before proving this formula, we need an auxiliary result involving Möbius matrices, due to Lindström [13]. (Lindström’s theorem is in fact slightly more general as it applies to semilattices.) By definition, if X is a finite poset, the associated Möbius matrix μ is the inverse of the order matrix ζ indexed by the elements of X and given by

ζ(x, y) = \begin{cases}1 & for x ≤ y, \\ 0 & otherwise. \end{cases}

If the elements of X are ordered according to a linear extension of the partial order of X, then ζ is an upper triangular matrix, with ones on the diagonal. In particular, its determinant is 1. The same is true for μ.

Lemma 4.4 ([13]). Assume that X is a lattice, and φ is a complex valued function on X. Let Φ be the matrix defined by Φ(x, y) = φ(x∧y). Then we have

det(Φ) = ∏_{x∈X} φ̂(x),

where φ̂ is given by φ̂(x) = ∑_{y≤x} μ(y, x)φ(y).

Note that, under the above assumptions, we have φ(x) = ∑_{y≤x} φ̂(y) by definition of the Möbius matrix.

Proof of Theorem 4.3. We apply Lemma 4.4 to X = NC(n) and φ defined by φ(π) = 1 for π = 0_{n} and φ(π) = 0 for π ≠ 0_{n}. We obtain φ̂(π) = μ(0_{n}, π). It is known that the Möbius function for the lattice of noncrossing partitions is multiplicative: if π is made of p_{k} blocks of size k for k = 1, 2, …, then we have

μ(0_{n}, π) = ∏_{k}((−1)^{k−1}Cat_{k−1})^{p_{k}}.

The matrix A_{n}^{∗} coincides with the corresponding matrix Φ up to a permutation of the columns (given by taking the Kreweras complement). We deduce

| det(A_{n}^{∗})| = ∏_{k} Cat_{k−1}^{a_{n,k}},

with

a_{n,k} = ∑_{π∈NC(n)} p_{k}(π).

The numbers a_{n,k} have been computed in [8] (see item 4 on page 218), and we have a_{n,k} = \binom{2n−k−1}{n−1}. We are grateful to an anonymous referee for this reference. For the convenience of the reader we give a short selfcontained proof of this evaluation (our original proof has been greatly improved by a second anonymous referee, whom we also thank here).

Let us introduce the generating functions

f_{n,k}(y) = ∑_{π∈NC(n)} y^{p_{k}(π)} and f(z, y, k) = ∑_{n≥0} z^{n}f_{n,k}(y).

Then we have

a_{n,k} = f′_{n,k}(1).

By the moment-cumulant formula, f(z, y, k) is the moment generating function for the cumulant sequence R_{k} = y, R_{n} = 1, n ≠ k. Since

R(z) = \frac{1}{1 − z} + (y − 1)z^{k},

it follows from (3.4) that f_{n,k}(y) is equal to the coefficient of x^{n} in the expansion of

\frac{1}{n + 1} (\frac{1}{1 − x} + (y − 1)x^{k})^{n+1} .

Taking the derivative with respect to y, at y = 1 we deduce that f′_{n,k}(1) is the coefficient of x^{n} in \frac{x^{k}}{(1−x)^{n}}, which is a_{n,k} = \binom{2n−k−1}{n−1}, as expected. □

References

[1] D. Bessis, F. Digne, J. Michel, Springer theory in braid groups and the Birman– Ko–Lee monoid, Pacific J. Math 205 (2002) 287-309.

[2] P. Biane, Some properties of crossings and partitions, Discrete Math. 175 (1997) 41–53.

[3] J. Birman, Braids, Links, and Mapping Class Groups, Annals of Math. Studie, vol. 82, Princeton Univ. Press, Princeton, 1975.

[4] J. Birman, K.H. Ko & S.J. Lee, A new approach to the word problem in the braid groups, Adv. Math. 139 (1998) 322–353.

[5] L. Carlucci, P. Dehornoy & A. Weiermann, Unprovability statements involving braids, Proc. London Math. Soc. 102 (2011) 159–192.

[6] P. Dehornoy, Combinatorics of normal sequences of braids, J. Combin. Theory Ser. A 114 (2007) 389–409.

[7] P. Dehornoy, F. Digne, E. Godelle, D. Krammer & J. Michel, Foundations of Garside Theory, EMS Tracts in Mathematics, vol. 22 (2015);

    http://www.math.unicaen.fr/∼garside/Garside.pdf.

[8] N. Dershowitz & S. Zaks, Ordered trees and noncrossing partitions, Discrete Math. 62 (1986) 215–218.

[9] D. Epstein, J. Cannon, D. Holt, S. Levy & M. Paterson & W. Thurston, Word Processing in Groups, Jones & Bartlett Publ. (1992).

[10] F.A. Garside, The braid group and other groups, Quart. J. Math. Oxford 20-78 (1969) 235–254.

[11] F. Hivert & J.-C. Novelli, J.-Y. Thibon, Sur une conjecture de Dehornoy, Comptes Rendus Math. 346 (2008) 375–378.

[12] G. Kreweras, Sur les partitions non croisées d’un cycle, Discr. Math. 1 (1972) 333–350.

[13] B. Lindström, Determinants on semilattices, Proc. Amer. Math. Soc. 20 (1969) 207–208.

[14] A. Nica & R. Speicher, Lectures on the combinatorics of free probability, London Mathematical Society Lecture Note Series, vol. 335. Cambridge University Press, Cambridge, 2006.

[15] N.J.A. Sloane, On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[16] R. Speicher & R. Woroudi, Boolean convolution, Free probability theory, Fields Inst. Commun. 12 (1997) 267–279.

[17] R. Speicher, A conceptual proof of a basic result in the combinatorial approach to freeness, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 3 (2000) 213– 222.

Institut Gaspard-Monge, université Paris-Est Marne-la-Vallée, 5 Boulevard Descartes, Champs-sur-Marne, 77454, Marne-la-Vallée cedex 2, France

E-mail address: biane@univ-mlv.fr
URL: monge.univ-mlv.fr/~biane/

Laboratoire de Mathématiques Nicolas Oresme UMR 6139, Université de Caen, 14032 Caen, France

E-mail address: dehornoy@math.unicaen.fr
URL: www.math.unicaen.fr/~dehornoy