The F -triangle of the generalised cluster complex

C. Krattenthaler^{†‡}

Institut Camille Jordan, Université Claude Bernard Lyon-I, 21, avenue Claude Bernard, F-69622 Villeurbanne Cedex, France.

                  WWW: http://igd.univ-lyon1.fr/~kratt

Abstract. The F -triangle is a refined face count for the generalised cluster complex of Fomin and Reading. We compute the F -triangle explicitly for all irreducible finite root systems. Furthermore, we use these results to partially prove the “F = M Conjecture” of Armstrong which predicts a surprising relation between the F -triangle and the Möbius function of his m-divisible partition poset associated to a finite root system.

1. Introduction. Fomin and Zelevinsky created a new exciting research field when they invented cluster algebras in [11]. The classification of cluster algebras of finite type from [12] says that there is a one-to-one correspondence between finite-type cluster algebras and finite root systems. Furthermore, for each finite root system Φ, Fomin and Zelevinsky [13] defined a simplicial complex corresponding to the associated cluster algebra, the cluster complex Δ(Φ). This is a simplicial complex on a subset of the set of roots Φ. As they showed, this complex has many remarkable properties. In particular, the number of facets is given by the Catalan number for the root system Φ, and, moreover, all the face numbers are given by elegant product formulae. Further remarkable (originally, conjectural) properties have been discovered by Chapoton in [8]. In this paper, he refines the face enumeration to, what he calls, the “F -triangle.” He computed the F -triangle for all types (and revealed his findings partially in [8]) and observed a surprising relationship (see [8, Conjecture 1]) between the F -triangle and the Möbius function of the non-crossing partition lattice NC(Φ) associated to Φ, the latter being due to Bessis [4] and Brady and Watt [5]. This relationship, to which we shall refer in the sequel as the “F = M Conjecture,” has been recently proved by Athanasiadis [2]. For further fascinating properties of the F -triangle see [8].

2000 Mathematics Subject Classification. Primary 05E15; Secondary 05A05 05A10 05A15 05A19 06A07 20F55 33C05.

Key words and phrases. root systems, generalised cluster complex, face numbers, F -triangle, mdivisible non-crossing partitions, Möbius function, M-triangle, Chu–Vandermonde summation..

†Research partially supported by EC’s IHRP Programme, grant HPRN-CT-2001-00272, “Algebraic Combinatorics in Europe.”

‡Current address: Fakultät für Mathematik, Universität Wien, Nordbergstraße 15, A-1090 Vienna, Austria.

The subject of this paper is “m-generalisations” of the cluster complex Δ(Φ) and of the non-crossing partition lattice NC(Φ). More precisely, in [10], Fomin and Reading introduce the generalised cluster complex Δ^{m}(Φ), where m is some non-negative integer. This is, again, a simplicial complex, now on coloured roots, and for m = 1 it reduces to the (ordinary) cluster complex Δ(Φ). As they show, this generalised complex has again remarkable properties. In particular, the number of facets is given by the Fuss–Catalan number for the root system Φ, and, moreover, again, all the face numbers are given by elegant product formulae.

Going one step further, Sergey Fomin suggested to the author to investigate the “Chapoton-like” refinement of the face numbers of the generalised cluster complex Δ^{m}(Φ), that is to say, to study the “F -triangle” for Δ^{m}(Φ) (see Section 2 for the definition). This is what we do in this paper. We compute the F -triangle of Δ^{m}(Φ) for all types of irreducible root systems Φ, see Sections 4–7. We do this case-by-case. While a case-independent formula would certainly be desirable, certain features of our results (in particular, the appearance of the Kronecker delta in the formula in Theorem FD in Section 6 for type D_{n}) make it highly unlikely that such a case-independent formula exists. As an aside, we draw the reader’s attention to the unexpected outcome of our results that the refined face numbers are all polynomials in m with non-negative coefficients, a phenomenon for which we have no intrinsic explanation.

One may then ask if there is also an “F = M Conjecture” in this generalised context. This would, first of all, require an “m-extension” of the non-crossing partition lattice. Indeed, Armstrong [1] has recently introduced the “m-divisible non-crossing partition poset” NC^{m}(Φ), generalising an earlier construction of Edelman [9] in type A_{n}. He shows that this poset has also remarkable properties, resembling those of the non-crossing partition lattices. Moreover, he observed that there is also a rather straight-forward extension of the F = M Conjecture relating the F -triangle of the generalised cluster complex Δ^{m}(Φ) to the Möbius function of the corresponding m-divisible non-crossing partitions poset NC^{m}(Φ). We reproduce this conjecture in Section 8. (We refer the reader to [1, Sec. 4] and [21] for further fascinating properties of the F -triangle of Δ^{m}(Φ).)

With the explicit formulae for the F -triangle in hand, we are able to prove this “mversion” of the F = M Conjecture in types A_{n} and B_{n}, for the dihedral root systems I_{2}(a), for the hyperbolic root systems H_{3} and H_{4}, and for F_{4} and E_{6}, see Sections 9, 10, 13–17. In types A_{n} and B_{n}, the proofs depend crucially on results about rank selected chain enumeration in NC^{m}(A_{n}) and NC^{m}(B_{n}) due to Edelman [9] and Armstrong [1], respectively. Moreover, in Section 11, we provide a calculation in type D_{n} which will prove the conjecture also for this type once the corresponding rank selected chain enumeration result analogous to the ones by Edelman and Armstrong is available for NC^{m}(D_{n}). In view of the results of Athanasiadis and Reiner [3] on rank selected chain enumeration in NC^{1}(D_{n}) = NC(D_{n}), this argument does accomplish the proof for m = 1. As we explain in Section 12, the verification of the (generalised) F = M Conjecture in the exceptional types is a routine task which can, in principle, be carried out on a computer. To do this in practice for the root systems E_{7} or E_{8}, say, may however require additional simplifications of the proposed procedure.^{1}

1Using some additional ideas, this has been carried through in “The M-triangle of generalised non-

In the final Section 18, we prove Armstrong’s conjecture [1, Sec. 4] on the form of, what he calls, the dual F -triangle in a case-by-case fashion. For the exceptional root systems this is just a routine calculation, while for A_{n}, B_{n} and D_{n} this requires only the Chu–Vandermonde summation formula.

We conclude the introduction by saying a few words how the F -triangles for Δ^{m}(Φ) are found and the corresponding results are proved in this paper. The main tool in [8] for finding F -triangles for the (ordinary) cluster complex Δ(Φ) consists in two recurrence formulae (see [8, Prop. 3]). These recurrences carry over verbatim to the generalised cluster complex Δ^{m}(Φ), see Proposition F in Section 2. Indeed, in the exceptional types, the formula for the F -triangle for Δ^{m}(Φ) can be found in a routine fashion by using these recurrences, see Section 7. In types A_{n}, B_{n}, and D_{n}, however, the recurrences can only be used to compute the F -triangle for the corresponding generalised cluster complex for specific n. By doing this for sufficiently many n, we first worked out guesses for the F - triangle for generic n. (In types A_{n} and B_{n}, this has also been done independently by Tzanaki [21].) Subsequently, one tries to verify these guesses by checking the recurrences. As it turns out, this requires multivariate summation formulae due to Carlitz [7], which we restate here in Section 3 for the convenience of the reader. An interesting detail is the fact that Chapoton’s proofs in [8] for the F -triangle for Δ(A_{n}) and Δ(B_{n}), respectively, which also use Carlitz’s summation formulae, do not extend to Δ^{m}(A_{n}) and Δ^{m}(B_{n}), for the following reason. In order to do the above described verification using the recurrences, he has to evaluate a triple sum. He does this by first simplifying one sum by means of the Chu–Vandermonde summation, and by using subsequently one of Carlitz’s summation formulae to evaluate the remaining double sum. However, if m ≠ 1, the Chu–Vandermonde summation is not applicable to the triple sum that we encounter at the start. Remarkably, it is possible to apply Carlitz’s summation formula directly, in a different way than in [8]. The use of the Chu–Vandermonde summation is then not necessary anymore.

2. Preliminaries. Let Φ be a finite root system of rank n. (We refer the reader to [15] for all root system terminology.) For a non-negative integer m, the generalised cluster complex Δ^{m}(Φ) is a certain simplicial complex on a certain set of “coloured” roots, the roots being from Φ. The precise definition will not be important here, we refer the reader to [10, Sec. 2]. The only fact which is important here is that some of the coloured roots can be positive, others negative. Let f_{k,l}(Φ, m) denote the number of faces of Δ^{m}(Φ) which contain exactly k positive and l negative coloured roots. Define the F -triangle of Δ^{m}(Φ), denoted by F_{Φ}^{m}(x, y), as the two-variable polynomial

F_{Φ}^{m}(x, y) = ∑_{k,l≥0} f_{k,l}(Φ, m) x^{k}y^{l}.  (1)

It is called “triangle” because all faces have cardinality at most n and, thus, in the summation in (1) we can restrict the summation indices to the triangle k + l ≤ n, k, l ≥ 0.

Then, in this generalised context, the arguments from [8, Prop. 3] carry over verbatim to prove the following properties of the F -triangle of Δ^{m}(Φ).

crossing partitions for the types E_{7} and E_{8}” (preprint; arXiv:math.CO/0601676).

Proposition F. The F -triangle F_{Φ}^{m}(x, y) satisfies the following three properties:

(1) If Φ and Φ′ are two root systems, then

F_{Φ×Φ′}^{m}(x, y) = F_{Φ}^{m}(x, y)F_{Φ′}^{m}(x, y),  (2)

where Φ × Φ′ denotes the orthogonal product of the two root systems.

(2) If Φ = Φ(S) is an irreducible root system with simple roots S, then

\frac{∂}{∂y} F_{Φ(S)}^{m}(x, y) = ∑_{α∈S} F_{Φ(S\\{α\})}^{m}(x, y),  (3)

where Φ(S\{α}) denotes the root system generated by the simple roots S\{α}.

(3) The specialisation x = y is given by

F_{Φ}^{m}(x, x) = ∑_{k≥0} f_{k}(Φ, m) x^{k},  (4)

where the coefficients f_{k}(Φ, m) are the face numbers of the cluster complex Δ^{m}(Φ), summarised in [10, Theorem 7.5] for the irreducible root systems.

We remark that an equivalent statement of (3) is

l · f_{k,l}(Φ(S), m) = ∑_{α∈S} f_{k,l−1}(Φ(S\{α}), m), k, l ≥ 0.  (5)

Moreover, in view of the multiplicativity property (2), it suffices to compute the F -triangle for the irreducible root systems, which we do in Sections 4–7.

3. Carlitz’s summation formulae. Crucial in the proofs of our claims for the F - triangle in types A_{n}, B_{n} and D_{n} are the following two double sum evaluations due to Carlitz [7]. (He has in fact extensions for any number of summations, see [7, Sec. 6].) Let

A_{k,n}(α, β) = \frac{bkα + cnβ + αβ}{(ak + cn + α)(bk + dn + β)}\binom{ak + cn + α}{k}\binom{bk + dn + β}{n}.

Here, and in the sequel, for integers N and K the binomial coefficient \binom{N}{K} is understood according to the definition

\binom{N}{K} = \{ \begin{matrix}\frac{N(N−1)···(N−K+1)}{K!} & if K ≥ 0, \\ 0 & if K < 0. \end{matrix}  (6)

Then (see [7, (5.14)]),

∑_{k_{1},n_{1}≥0} A_{k_{1},n_{1}}(α, β)A_{k−k_{1},n−n_{1}}(α′, β′) = A_{k,n}(α + α′, β + β′).  (7)

Furthermore (see [7, (5.15); the minus sign in front of cn must be replaced by a plus sign there]),

∑_{k_{1},n_{1}≥0} \binom{ak_{1} + cn_{1} + α − 1}{k_{1}}\binom{bk_{1} + dn_{1} + β − 1}{n_{1}}A_{k−k_{1},n−n_{1}}(α′, β′)

= \binom{ak + cn + α + α′ − 1}{k}\binom{bk + dn + β + β′ − 1}{n}. (8)

4. The F -triangle for A_{n}. The theorem below gives an explicit expression for the refined face numbers f_{k,l}(A_{n}, m), and, thus, of the F -triangle in type A_{n}.

Theorem FA. For n ≥ 1, the face numbers f_{k,l}(A_{n}, m) are given by

f_{k,l}(A_{n}, m) = \frac{l + 1}{k + l + 1}\binom{n}{k + l}\binom{m(n + 1) + k − 1}{k}.

Proof. In view of Proposition F and (5) in Section 2, in order to prove this claim we have to show

l · f_{k,l}(A_{n}, m) = _{∑_{n_{1}+n_{2}=n−1} ; k_{1}+k_{2}=k ; l_{1}+l_{2}=l−1}f_{k_{1},l_{1}}(A_{n_{1}}, m) · f_{k_{2},l_{2}}(A_{n_{2}}, m)  (9)

and

∑_{k_{1}+l_{1}=k} f_{k_{1},l_{1}}(A_{n}, m) = \frac{1}{k + 1}\binom{n}{k}\binom{m(n + 1) + k + 1}{k}.  (10)

The triple sum on the right-hand side of (9) is

∑_{k_{1},l_{1},n_{1}≥0} \frac{l_{1} + 1}{k_{1} + l_{1} + 1}\binom{n_{1}}{k_{1} + l_{1}}\binom{m(n_{1} + 1) + k_{1} − 1}{k_{1}}

· \frac{l − l_{1}}{k − k_{1} + l − l_{1}} \binom{n − n_{1} − 1}{k − k_{1} + l − l_{1} − 1}\binom{m(n − n_{1}) + k − k_{1} − 1}{k − k_{1}}.

We replace n_{1} by n_{1} + k_{1} + l_{1} and rewrite the resulting expression in the form

∑_{k_{1},l_{1},n_{1}≥0} \frac{m(l_{1} + 1)}{m(k_{1} + l_{1} + n_{1} + 1) + k_{1}} \binom{n_{1} + k_{1} + l_{1} + 1}{n_{1}}\binom{m(n_{1} + k_{1} + l_{1} + 1) + k_{1}}{k_{1}}

· \frac{m(l − l_{1})}{m(n − n_{1} − k_{1} − l_{1}) + k − k_{1}} \binom{n − n_{1} − k_{1} − l_{1}}{n − k − l − n_{1}}

· \binom{m(n − n_{1} − k_{1} − l_{1}) + k − k_{1}}{k − k_{1}}. (11)

Forgetting the sum over l_{1}, this is now exactly in the form of the left-hand side of (7) with n replaced by n − k − l, a = m + 1, c = m, α = m(l_{1} + 1), α′ = m(l − l_{1}), b = d = 1, β = l_{1} + 1, and β′ = l − l_{1}. Substituting the right-hand side, we obtain

∑_{l_{1}=0}^{l−1} A_{k,n−k−l}(m(l + 1), l + 1)

for the sum in (11), or, equivalently,

l · \frac{m(l + 1)}{m(n + 1) + k} \binom{m(n + 1) + k}{k}\binom{n + 1}{n − k − l},

which is indeed equal to l · f_{k,l}(A_{n}, m). This proves (9).

Next we compute the sum on the left-hand side of (10),

∑_{k_{1}=0}^{k} \frac{k − k_{1} + 1}{k + 1}\binom{n}{k}\binom{m(n + 1) + k_{1} − 1}{k_{1}}

= ∑_{k_{1}=0}^{k} \binom{n}{k}\binom{m(n + 1) + k_{1} − 1}{k_{1}} − ∑_{k_{1}=0}^{k} \frac{m(n + 1)}{k + 1}\binom{n}{k}\binom{m(n + 1) + k_{1} − 1}{k_{1} − 1}

= \binom{n}{k}\binom{m(n + 1) + k}{m(n + 1)} − \frac{m(n + 1)}{k + 1}\binom{n}{k}\binom{m(n + 1) + k}{m(n + 1) + 1}

= \frac{1}{k + 1}\binom{n}{k}\binom{m(n + 1) + k + 1}{k},

the simplification of summations being due to the Chu–Vandermonde summation (see [14, Sec. 5.1, (5.27)] or [18, (1.7.7), Appendix (III.4)]). This completes the proof. □

5. The F -triangle for B_{n}. The theorem below gives an explicit expression for the refined face numbers f_{k,l}(B_{n}, m), and, thus, of the F -triangle in type B_{n}.

Theorem FB. For n ≥ 1, the face numbers f_{k,l}(B_{n}, m) are given by

f_{k,l}(B_{n}, m) = \binom{n}{k + l}\binom{mn + k − 1}{k}.

Here we identify B_{1} with A_{1}.

Proof. By inspection, the formula for f_{k,l}(B_{1}, m) given in the theorem agrees with the formula for f_{k,l}(A_{1}, m) in Theorem FA. Hence, in view of Proposition F and (5) in Section 2, in order to prove this claim we have to show

l · f_{k,l}(B_{n}, m) = _{∑_{n_{1}+n_{2}=n−1} ; k_{1}+k_{2}=k ; l_{1}+l_{2}=l−1}f_{k_{1},l_{1}}(B_{n_{1}}, m) · f_{k_{2},l_{2}}(A_{n_{2}}, m)  (12)

and

∑_{k_{1}+l_{1}=k} f_{k_{1},l_{1}}(B_{n}, m) = \binom{n}{k}\binom{mn + k}{k}.  (13)

The triple sum on the right-hand side of (12) is

∑_{k_{1},l_{1},n_{1}≥0} \binom{n_{1}}{k_{1} + l_{1}}\binom{mn_{1} + k_{1} − 1}{k_{1}}

· \frac{l − l_{1}}{k − k_{1} + l − l_{1}} \binom{n − n_{1} − 1}{k − k_{1} + l − l_{1} − 1}\binom{m(n − n_{1}) + k − k_{1} − 1}{k − k_{1}}.

We replace n_{1} by n_{1} + k_{1} + l_{1} and rewrite the resulting expression in the form

∑_{k_{1},l_{1},n_{1}≥0} \binom{n_{1} + k_{1} + l_{1}}{n_{1}}\binom{m(n_{1} + k_{1} + l_{1}) + k_{1} − 1}{k_{1}}

· \frac{m(l − l_{1})}{m(n − n_{1} − k_{1} − l_{1}) + k − k_{1}} \binom{n − n_{1} − k_{1} − l_{1}}{n − k − l − n_{1}}

· \binom{m(n − n_{1} − k_{1} − l_{1}) + k − k_{1}}{k − k_{1}}. (14)

Forgetting the sum over l_{1}, this is now in the form of the left-hand side of (8) with n replaced by n − k − l, a = m + 1, c = m, α = ml_{1}, α′ = m(l − l_{1}), b = d = 1, β = l_{1} + 1, β′ = l − l_{1}. Substituting the right-hand side, we obtain

∑_{l_{1}=0}^{l−1} \binom{mn + k − 1}{k}\binom{n}{n − k − l}

for the sum in (14), or, equivalently,

l · \binom{n}{k + l}\binom{mn + k − 1}{k},

which is indeed equal to l · f_{k,l}(B_{n}, m). This proves (12).

Next we compute the sum on the left-hand side of (13),

∑_{k_{1}=0}^{k} \binom{n}{k}\binom{mn + k_{1} − 1}{k_{1}} = \binom{n}{k}\binom{mn + k}{k},

the simplification of summation being due to the Chu–Vandermonde summation. This completes the proof. □

6. The F -triangle for D_{n}. The theorem below gives an explicit expression for the refined face numbers f_{k,l}(D_{n}, m), and, thus, of the F -triangle in type D_{n}.

Theorem FD. For n ≥ 2, the face numbers f_{k,l}(D_{n}, m) are given by

f_{k,l}(D_{n}, m) = \binom{n}{k + l}\binom{m(n − 1) + k − 1}{k} + m\binom{n − 1}{k + l − 1}\binom{m(n − 1) + k − 2}{k − 1}

− δ_{l,0} \frac{1}{n − 1}\binom{n − 1}{k − 1}\binom{m(n − 1) + k − 1}{k},

where δ_{l,0} is the Kronecker delta, that is, it is equal to 1 if l = 0, and it is equal to 0 otherwise. Here we identify D_{2} with A_{1}^{2}, and we identify D_{3} with A_{3}.

Proof. By inspection, for n = 2 the formula for f_{k,l}(D_{2}, m) given in the theorem yields for the F -triangle

F_{D_{2}}^{m}(x, y) = ∑_{k,l≥0} f_{k,l}(D_{2}, m) x^{k}y^{l} = m^{2}x^{2} + 2mxy + y^{2} + 2mx + 2y + 1 = (mx + y + 1)^{2},

which, according to Theorem FA, is indeed the F -triangle of A_{1}^{2}. Furthermore, again by inspection, the formula for f_{k,l}(B_{3}, m) given in the theorem agrees with the formula for f_{k,l}(A_{3}, m) in Theorem FA. Hence, in view of Proposition F and (5) in Section 2, in order to prove this claim we have to show

l · f_{k,l}(D_{n}, m) = _{∑_{n_{1}+n_{2}=n−1, n_{1}≥2} ; k_{1}+k_{2}=k ; l_{1}+l_{2}=l−1}f_{k_{1},l_{1}}(D_{n_{1}}, m) · f_{k_{2},l_{2}}(A_{n_{2}}, m) + 2 · f_{k,l−1}(A_{n−1}, m) (15)

and

∑_{k_{1}+l_{1}=k} f_{k_{1},l_{1}}(D_{n}, m) = \binom{n}{k}\binom{m(n − 1) + k}{k} + \binom{n − 2}{k − 2}\binom{m(n − 1) + k − 1}{k}. (16)

We start with the proof of (15). Clearly, it suffices to consider the case l ≥ 1 because (15) is trivially true for l = 0. We shall therefore assume l ≥ 1 from now on.

Using the rewriting

\frac{l + 1}{k + l + 1}\binom{n}{k + l}\binom{m(n + 1) + k − 1}{k} = \frac{m(l + 1)}{m(n + 1) + k} \binom{n + 1}{n − k − l}\binom{m(n + 1) + k}{k}

of the defining expression for f_{k,l}(A_{n}, m) in Theorem FA, the expression on the right-hand side of (15) is

∑_{l_{1}=0}^{l−1} ∑_{k_{1}=0}^{k} ∑_{n_{1}=2}^{n−1} \binom{n_{1}}{k_{1} + l_{1}}\binom{m(n_{1} − 1) + k_{1} − 1}{k_{1}}

· \frac{m(l − l_{1})}{m(n − n_{1}) + k − k_{1}} \binom{n − n_{1}}{n − n_{1} − k + k_{1} − l + l_{1}}\binom{m(n − n_{1}) + k − k_{1}}{k − k_{1}}

(17a)

+ m ∑_{l_{1}=0}^{l−1} ∑_{k_{1}=0}^{k} ∑_{n_{1}=2}^{n−1} \binom{n_{1} − 1}{k_{1} + l_{1} − 1}\binom{m(n_{1} − 1) + k_{1} − 2}{k_{1} − 1}

· \frac{m(l − l_{1})}{m(n − n_{1}) + k − k_{1}} \binom{n − n_{1}}{n − n_{1} − k + k_{1} − l + l_{1}}\binom{m(n − n_{1}) + k − k_{1}}{k − k_{1}}

(17b)

− ∑_{k_{1}=0}^{k} ∑_{n_{1}=2}^{n−1} \frac{1}{n_{1} − 1}\binom{n_{1} − 1}{k_{1} − 1}\binom{m(n_{1} − 1) + k_{1} − 1}{k_{1}}

· \frac{ml}{m(n − n_{1}) + k − k_{1}} \binom{n − n_{1}}{n − n_{1} − k + k_{1} − l}\binom{m(n − n_{1}) + k − k_{1}}{k − k_{1}}

(17c)

+ \frac{2l}{k + l} \binom{n − 1}{k + l − 1}\binom{mn + k − 1}{k}.  (17d)

We treat the three sums in (17) separately. We begin with the sum (17a). We extend the sum to all n_{1} ≥ 0. In order to do so, we must subtract the terms with n_{1} = 0 and n_{1} = 1. If n_{1} = 0, the summand is only non-zero for k_{1} = l_{1} = 0 because of the presence of the binomial \binom{n_{1}}{k_{1}+l_{1}}. If n_{1} = 1, then, because of the presence of the binomial coefficient \binom{m(n_{1}−1)+k_{1}−1}{k_{1}} = \binom{k_{1}−1}{k_{1}}, the summand can be non-zero only if k_{1} = 0. On the other hand, in that case, the summand can be only non-zero for l_{1} = 0 and l_{1} = 1, again because of the presence of the binomial \binom{n_{1}}{k_{1}+l_{1}} = \binom{1}{l_{1}}. In summary, the sum (17a) is equal to

∑_{l_{1}=0}^{l−1} ∑_{k_{1}=0}^{k} ∑_{n_{1}=0}^{n−1} (\binom{n_{1}}{k_{1} + l_{1}}\binom{m(n_{1} − 1) + k_{1} − 1}{k_{1}}

· \frac{m(l − l_{1})}{m(n − n_{1}) + k − k_{1}} \binom{n − n_{1}}{n − n_{1} − k + k_{1} − l + l_{1}}\binom{m(n − n_{1}) + k − k_{1}}{k − k_{1}})

− \frac{l}{k + l} \binom{n − 1}{k + l − 1}\binom{mn + k − 1}{k} − \frac{l}{k + l} \binom{n − 2}{k + l − 1}\binom{m(n − 1) + k − 1}{k}

− \frac{l − 1}{k + l − 1}\binom{n − 2}{k + l − 2}\binom{m(n − 1) + k − 1}{k},

where the second-to-last term corresponds to the summand for n_{1} = k_{1} = l_{1} = 0, the next-to-last term corresponds to the summand for n_{1} = 1, k_{1} = 0, l_{1} = 0, and the last term corresponds to the summand for n_{1} = 1, k_{1} = 0, l_{1} = 1. In the sum over n_{1}, k_{1}, l_{1}, we replace n_{1} by n_{1} + k_{1} + l_{1}. Forgetting the sum over l_{1}, we see that it is then in the form of the left-hand side of (8) with n replaced by n − k − l, a = m + 1, c = m, α = m(l_{1} − 1), α′ = m(l − l_{1}), b = d = 1, β = l_{1} + 1, β′ = l − l_{1}. Hence, if we substitute the right-hand side, the expression simplifies to

∑_{l_{1}=0}^{l−1} \binom{n}{k + l}\binom{m(n − 1) + k − 1}{k} − \frac{l}{k + l} \binom{n − 1}{k + l − 1}\binom{mn + k − 1}{k}

− \frac{l}{k + l} \binom{n − 2}{k + l − 1}\binom{m(n − 1) + k − 1}{k} − \frac{l − 1}{k + l − 1}\binom{n − 2}{k + l − 2}\binom{m(n − 1) + k − 1}{k}.

(18)

Clearly, the sum over l_{1} sums the same summand for each l_{1}, so that the result is that summand multiplied by l.

We next turn our attention to the sum (17b). The first observation is that for k_{1} = 0 the summand vanishes because of the presence of the binomial coefficient \binom{m(n_{1}−1)+k_{1}−2}{k_{1}−1}. We therefore replace k_{1} by k_{1} + 1 to obtain

m ∑_{l_{1}=0}^{l−1} ∑_{k_{1}=0}^{k−1} ∑_{n_{1}=2}^{n−1} \binom{n_{1} − 1}{k_{1} + l_{1}}\binom{m(n_{1} − 1) + k_{1} − 1}{k_{1}}

· \frac{m(l − l_{1})}{m(n − n_{1}) + k − k_{1} − 1}\binom{n − n_{1}}{n − n_{1} − k + k_{1} − l + l_{1} + 1}\binom{m(n − n_{1}) + k − k_{1} − 1}{k − k_{1} − 1}.

This time we extend the sum to n_{1} ≥ 1. In order to do so, we must subtract the terms with n_{1} = 1. In the latter case, because of the presence of the binomial coefficient \binom{n_{1}−1}{k_{1}+l_{1}}, the summand will vanish except if k_{1} = l_{1} = 0. Thus, we obtain

m ∑_{l_{1}=0}^{l−1} ∑_{k_{1}=0}^{k−1} ∑_{n_{1}=1}^{n−1} (\binom{n_{1} − 1}{k_{1} + l_{1}}\binom{m(n_{1} − 1) + k_{1} − 1}{k_{1}}

· \frac{m(l − l_{1})}{m(n − n_{1}) + k − k_{1} − 1}\binom{n − n_{1}}{n − n_{1} − k + k_{1} − l + l_{1} + 1}\binom{m(n − n_{1}) + k − k_{1} − 1}{k − k_{1} − 1})

− \frac{ml}{k + l − 1}\binom{n − 2}{k + l − 2}\binom{m(n − 1) + k − 2}{k − 1}

for (17b). In the triple sum, we replace n_{1} by n_{1} + k_{1} + l_{1} + 1. Forgetting the sum over l_{1}, we see that it is then in the form of the left-hand side of (8) with n replaced by n − k − l, a = m + 1, c = m, α = ml_{1}, α′ = m(l − l_{1}), b = d = 1, β = l_{1} + 1, β′ = l − l_{1}, and k replaced by k − 1. Hence, if we substitute the right-hand side, the expression simplifies to

m ∑_{l_{1}=0}^{l−1} \binom{n − 1}{k + l − 1}\binom{m(n − 1) + k − 2}{k − 1} − \frac{ml}{k + l − 1}\binom{n − 2}{k + l − 2}\binom{m(n − 1) + k − 2}{k − 1}.

(19)

Also here, the sum over l_{1} sums the same summand for each l_{1}, so that the result is that summand multiplied by l.

Finally we treat the sum (17c). Again, we want to extend the sum over n_{1} to n_{1} ≥ 0. In order to do so, we would have to subtract the terms for n_{1} = 1 and n_{1} = 0. However, it is somewhat unclear which values we should give the summand for these choices of n_{1}. To obtain a partial answer, we rewrite

\frac{1}{n_{1} − 1}\binom{n_{1} − 1}{k_{1} − 1}\binom{m(n_{1} − 1) + k_{1} − 1}{k_{1}} = \frac{m}{m(n_{1} − 1) + k_{1}} \binom{n_{1} − 1}{n_{1} − k_{1}}\binom{m(n_{1} − 1) + k_{1}}{k_{1}}.

(20)

(This rewriting is already in the spirit of the forth-coming application of Carlitz’s identity (7). We alert the reader that, according to our convention (6), the rewriting \binom{n_{1}−1}{k_{1}−1} = \binom{n_{1}−1}{n_{1}−k_{1}} is without problem as long as n_{1} ≥ 1, which is the case in (17c). However, it becomes wrong if 1 > n_{1} ≥ k_{1}, in which case \binom{n_{1}−1}{k_{1}−1} = 0 while \binom{n_{1}−1}{n_{1}−k_{1}} ≠ 0. In the following considerations, whenever we talk about cases where 1 > n_{1} ≥ k_{1}, we shall talk about the right-hand side in (20).) If n_{1} = 0, then, because of the presence of the binomial coefficient \binom{n_{1}−1}{n_{1}−k_{1}}, the summand is only non-zero if k_{1} = 0, in which case it equals

−\frac{ml}{mn + k} \binom{n}{n − k − l}\binom{mn + k}{k} = −\frac{l}{k + l} \binom{n − 1}{k + l − 1}\binom{mn + k − 1}{k}.

For n_{1} = 1, the above expression vanishes certainly if k_{1} > 1. If k_{1} = 1, it is equal to m. But if k_{1} = 0, it is still not clear which value to assign to it. Leaving this question open for the moment, the arguments so far show that the expression (17c) is equal to

− ∑_{k_{1}=0}^{k} ∑_{n_{1}=0}^{n−1} (\frac{m}{m(n_{1} − 1) + k_{1}} \binom{n_{1} − 1}{n_{1} − k_{1}}\binom{m(n_{1} − 1) + k_{1}}{k_{1}}

· \frac{ml}{m(n − n_{1}) + k − k_{1}} \binom{n − n_{1}}{n − n_{1} − k + k_{1} − l}\binom{m(n − n_{1}) + k − k_{1}}{k − k_{1}})

− \frac{l}{k + l} \binom{n − 1}{k + l − 1}\binom{mn + k − 1}{k} + \frac{ml}{k + l − 1}\binom{n − 2}{k + l − 2}\binom{m(n − 1) + k − 2}{k − 1}

+ (summand for n_{1} = 1, k_{1} = 0).

We now replace n_{1} by n_{1} + k_{1} in the double sum. This leads to the expression

− ∑_{n_{1},k_{1}≥0} (\frac{m}{m(n_{1} + k_{1} − 1) + k_{1}} \binom{n_{1} + k_{1} − 1}{n_{1}}\binom{m(n_{1} + k_{1} − 1) + k_{1}}{k_{1}}

· \frac{ml}{m(n − n_{1} − k_{1}) + k − k_{1}} \binom{n − n_{1} − k_{1}}{n − n_{1} − k − l}\binom{m(n − n_{1} − k_{1}) + k − k_{1}}{k − k_{1}})

− \frac{l}{k + l} \binom{n − 1}{k + l − 1}\binom{mn + k − 1}{k} + \frac{ml}{k + l − 1}\binom{n − 2}{k + l − 2}\binom{m(n − 1) + k − 2}{k − 1}

+ (summand for n_{1} = 1, k_{1} = 0).

The double sum is now exactly equal to the negative of the left-hand side of (7) with n replaced by n−k−l, a = m+1, c = m, α = −m, α′ = ml, b = d = 1, β = −1, β′ = l. From there, we can also determine the missing value of the summand for n_{1} = 1 and k_{1} = 0. Namely, we have

A_{0,1}(α, β) = β = −1.

Thus, if we substitute the right-hand side of (7), we obtain

\frac{l − 1}{k + l − 1}\binom{n − 2}{k + l − 2}\binom{m(n − 1) + k − 1}{k} − \frac{l}{k + l} \binom{n − 1}{k + l − 1}\binom{mn + k − 1}{k}

+ \frac{ml}{k + l − 1}\binom{n − 2}{k + l − 2}\binom{m(n − 1) + k − 2}{k − 1} + \frac{l}{k + l} \binom{n − 2}{k + l − 1}\binom{m(n − 1) + k − 1}{k}

(21)

for (17c).

Adding the expressions (18), (19), (21) and (17d), we obtain that the sum in (17) is equal to

l\binom{n}{k + l}\binom{m(n − 1) + k − 1}{k} + ml\binom{n − 1}{k + l − 1}\binom{m(n − 1) + k − 2}{k − 1},

which is indeed equal to l · f_{k,l}(D_{n}, m) if l ≥ 1. This proves (15).

Next we compute the sum on the left-hand side of (16),

∑_{k_{1}=0}^{k} \binom{n}{k}\binom{m(n − 1) + k_{1} − 1}{k_{1}} + m ∑_{k_{1}=0}^{k} \binom{n − 1}{k − 1}\binom{m(n − 1) + k_{1} − 2}{k_{1} − 1}

− \frac{1}{n − 1}\binom{n − 1}{k − 1}\binom{m(n − 1) + k − 1}{k}

= \binom{n}{k}\binom{m(n − 1) + k}{k} + m\binom{n − 1}{k − 1}\binom{m(n − 1) + k − 1}{k − 1}

− \frac{1}{n − 1}\binom{n − 1}{k − 1}\binom{m(n − 1) + k − 1}{k}

= \binom{n}{k}\binom{m(n − 1) + k}{k} + \binom{n − 2}{k − 2}\binom{m(n − 1) + k − 1}{k},

the simplification of summations being due to the Chu–Vandermonde summation. This completes the proof. □

7. The F -triangle in the exceptional cases. It is a routine matter to use Proposition F in Section 2 (and a computer algebra package) to find the F -triangles for the exceptional root systems. We list our findings below.

The F -triangle for I_{2}(a):

F_{I_{2}(a)}^{m}(x, y) = \frac{m(ma + a − 2)}{2}x^{2} + 2mxy + amx + y^{2} + 2y + 1.  (22)

The F -triangle for H_{3}:

F_{H_{3}}^{m}(x, y) = \frac{m(5m + 2)(5m + 4)}{3}x^{3} + m(5m + 2)x^{2}y

+ 5m(5m + 2)x^{2} + 3mxy^{2} + 10mxy + 15mx + y^{3} + 3y^{2} + 3y + 1. (23)

The F -triangle for H_{4}:

F_{H_{4}}^{m}(x, y) = \frac{m(3m + 1)(5m + 3)(15m + 14)}{4}x^{4} + m(3m + 1)(5m + 3)x^{3}y

+ 15m(3m + 1)(5m + 3)x^{3} + \frac{1}{2}m(17m + 5)x^{2}y^{2} + m(45m + 14)x^{2}y

+ \frac{1}{2}m(465m + 149)x^{2} + 4mxy^{3} + 17mxy^{2} + 31mxy + 60mx + y^{4} + 4y^{3} + 6y^{2} + 4y + 1. (24)

The F -triangle for F_{4}:

F_{F_{4}}^{m}(x, y) = \frac{m(2m + 1)(3m + 1)(6m + 5)}{2}x^{4} + 2m(2m + 1)(3m + 1)x^{3}y

+ 12m(2m + 1)(3m + 1)x^{3} + 2m(4m + 1)x^{2}y^{2} + 2m(18m + 5)x^{2}y + m(78m + 23)x^{2}

+ 4mxy^{3} + 16mxy^{2} + 26mxy + 24mx + y^{4} + 4y^{3} + 6y^{2} + 4y + 1. (25)

The F -triangle for E_{6}:

F_{E_{6}}^{m}(x, y) = \frac{1}{30}m(2m + 1)(3m + 1)(4m + 1)(6m + 5)(12m + 7)x^{6}

+ \frac{1}{5}m(2m + 1)(3m + 1)(4m + 1)(12m + 7)x^{5}y + \frac{6}{5}m(2m + 1)(3m + 1)(4m + 1)(12m + 7)x^{5}

+ \frac{1}{2}m(3m + 1)(4m + 1)(8m + 3)x^{4}y^{2} + 2m(3m + 1)(4m + 1)(12m + 5)x^{4}y

+ 2m(3m + 1)(4m + 1)(30m + 13)x^{4} + \frac{5}{3}m(4m + 1)(5m + 1)x^{3}y^{3}

+ m(4m + 1)(48m + 11)x^{3}y^{2} + m(4m + 1)(120m + 31)x^{3}y + 9m(4m + 1)(18m + 5)x^{3}

+ \frac{5}{2}m(7m + 1)x^{2}y^{4} + 5m(20m + 3)x^{2}y^{3} + m(242m + 39)x^{2}y^{2} + 3m(108m + 19)x^{2}y

+ 12m(21m + 4)x^{2} + 6mxy^{5} + 35mxy^{4} + 85mxy^{3} + 111mxy^{2} + 84mxy + 36mx + y^{6} + 6y^{5} + 15y^{4} + 20y^{3} + 15y^{2} + 6y + 1. (26)

The F -triangle for E_{7}:

F_{E_{7}}^{m}(x, y) = \frac{1}{280} m(3m + 1)(3m + 2)(9m + 2)(9m + 4)(9m + 5)(9m + 8)x^{7}

+ \frac{9}{40} m(3m + 1)(3m + 2)(9m + 2)(9m + 4)(9m + 5)x^{6} + \frac{1}{40} m(3m + 1)(3m + 2)(9m + 2)(9m + 4)(9m + 5)x^{6}y

+ \frac{3}{40} m(3m + 1)(7m + 3)(9m + 2)(9m + 4)x^{5}y^{2} + \frac{3}{20} m(3m + 1)(9m + 2)(9m + 4)(27m + 13)x^{5}y

+ \frac{3}{40} m(3m + 1)(9m + 2)(9m + 4)(207m + 103)x^{5} + \frac{1}{8} m(3m + 1)(9m + 2)(27m + 7)x^{4}y^{3}

+ \frac{3}{8} m(3m + 1)(9m + 2)(63m + 19)x^{4}y^{2} + \frac{3}{8} m(3m + 1)(9m + 2)(207m + 71)x^{4}y

+ \frac{21}{8} m(3m + 1)(9m + 2)(63m + 23)x^{4} + m(6m + 1)(9m + 2)x^{3}y^{4} + \frac{3}{2} m(9m + 2)(27m + 5)x^{3}y^{3}

+ \frac{3}{2} m(9m + 2)(81m + 17)x^{3}y^{2} + \frac{21}{2} m(9m + 2)(21m + 5)x^{3}y + \frac{21}{2} m(9m + 2)(27m + 7)x^{3} + 3m(8m + 1)x^{2}y^{5}

+3m(54m+7)x^{2}y^{4} + \frac{3}{2} m(315m+43)x^{2}y^{3} + \frac{21}{2} m(75m+11)x^{2}y^{2} + \frac{21}{2} m(81m+13)x^{2}y+ \frac{21}{2} m(63m+11)x^{2}

+ 7mxy^{6} + 48mxy^{5} + 141mxy^{4} + 231mxy^{3} + 231mxy^{2} + 147mxy + 63mx + y^{7} + 7y^{6} + 21y^{5} + 35y^{4} + 35y^{3} + 21y^{2} + 7y + 1. (27)

The F -triangle for E_{8}:

F_{E_{8}}^{m}(x, y) = \frac{m(3m + 1)(5m + 1)(5m + 2)(5m + 3)(15m + 8)(15m + 11)(15m + 14)x^{8}}{1344}

+ \frac{1}{168} m(3m + 1)(5m + 1)(5m + 2)(5m + 3)(15m + 8)(15m + 11)x^{7}y

+ \frac{5}{56} m(3m + 1)(5m + 1)(5m + 2)(5m + 3)(15m + 8)(15m + 11)x^{7}

+ \frac{1}{48} m(3m + 1)(5m + 1)(5m + 2)(15m + 7)(15m + 8)x^{6}y^{2}

+ \frac{5}{24} m(3m + 1)(5m + 1)(5m + 2)(15m + 8)^{2}x^{6}y + \frac{5}{48} m(3m + 1)(5m + 1)(5m + 2)(15m + 8)(195m + 107)x^{6}

+ \frac{1}{3} m(3m + 1)(5m + 1)(5m + 2)(10m + 3)x^{5}y^{3} + \frac{5}{8} m(3m + 1)(5m + 1)(5m + 2)(45m + 16)x^{5}y^{2}

+ \frac{25}{8} m(3m + 1)(5m + 1)(5m + 2)(39m + 16)x^{5}y + 15m(3m + 1)(5m + 1)(5m + 2)(30m + 13)x^{5}

+ \frac{1}{6} m(5m + 1)(10m + 3)(19m + 4)x^{4}y^{4} + m(5m + 1)(10m + 3)(25m + 6)x^{4}y^{3}

+ \frac{1}{4} m(5m + 1) (3675m^{2} + 2125m + 308) x^{4}y^{2} + m(5m + 1) (2250m^{2} + 1395m + 218) x^{4}y

+ \frac{1}{2} m(5m + 1) (10350m^{2} + 6675m + 1084) x^{4} + \frac{7}{3} m(5m + 1)(7m + 1)x^{3}y^{5}

+ \frac{1}{3} m(5m + 1)(380m + 59)x^{3}y^{4} + \frac{1}{3} m(5m + 1)(1315m + 226)x^{3}y^{3} + m(5m + 1)(915m + 178)x^{3}y^{2}

+ m(5m + 1)(1380m + 307)x^{3}y + 45m(5m + 1)(45m + 11)x^{3} + \frac{7}{2} m(9m + 1)x^{2}y^{6} + 7m(35m + 4)x^{2}y^{5}

+ \frac{1}{2} m(1675m + 199)x^{2}y^{4} + 4m(415m + 52)x^{2}y^{3} + \frac{1}{2} m(4295m + 579)x^{2}y^{2} + 75m(27m + 4)x^{2}y

+ \frac{35}{2} m(105m+17)x^{2} +8mxy^{7} +63mxy^{6} +217mxy^{5} +428mxy^{4} +532mxy^{3} +435mxy^{2} +245mxy +120mx

+ y^{8} + 8y^{7} + 28y^{6} + 56y^{5} + 70y^{4} + 56y^{3} + 28y^{2} + 8y + 1. (28)

8. The F = M Conjecture. In order to state the “F = M Conjecture” for generalised cluster complexes, we need to first introduce Armstrong’s [1] m-divisible non-crossing partition posets.

Given a root system Φ and an element α ∈ Φ, let t_{α} denote the corresponding reflection in the central hyperplane perpendicular to α. Let W = W (Φ) be the group generated by these reflections. By definition, any element w of W can be represented as a product w = t_{1}t_{2} ⋯ t_{ℓ}, where the t_{i}’s are reflections. We call the minimal number of reflections which is needed for such a product representation the absolute length of w, and we denote it by ℓ_{T} (w). We then define the absolute order on W, denoted by ≤_{T}, by

u ≤_{T} w if and only if ℓ_{T} (w) = ℓ_{T} (u) + ℓ_{T} (u^{−1}w).

It can be shown that this is equivalent to the statement that any shortest product representation of u by reflections occurs as an initial segment in some shortest product representation of w by reflections.

We can now define the non-crossing partition lattice NC(Φ). Let c be a Coxeter element in W, that is, the product of all reflections corresponding to the simple roots. Then NC(Φ) is defined to be the restriction of the partial order ≤_{T} to the set of all elements which are less than or equal to c in absolute order. This definition makes sense because, regardless of the chosen Coxeter element c, the resulting poset is always the same up to isomorphism. It can be shown that NC(Φ) is indeed a lattice. (See [6] for a uniform proof.) The term “non-crossing partition lattice” is used because NC(A_{n}) is isomorphic to the lattice of non-crossing partitions originally introduced by Kreweras [16], and because also NC(B_{n}) and NC(D_{n}) can be realized as lattices of non-crossing partitions (see [3, 17]).

The poset of m-divisible non-crossing partitions has as a groundset the following subset of (NC(Φ))^{m+1},

NC^{m}(Φ) = {(w_{0}; w_{1}, …, w_{m}) : w_{0}w_{1} ⋯ w_{m} = c and ℓ_{T} (w_{0}) + ℓ_{T} (w_{1}) + ⋯ + ℓ_{T} (w_{m}) = ℓ_{T} (c)}. (29)

The order relation is defined by

(u_{0}; u_{1}, …, u_{m}) ≤ (w_{0}; w_{1}, …, w_{m}) if and only if u_{i} ≥_{T} w_{i}, 1 ≤ i ≤ m.

We emphasize that, according to this definition, u_{0} and w_{0} need not be related in any way. The poset NC^{m}(Φ) is graded by the rank function

rk ((w_{0}; w_{1}, …, w_{m})) = ℓ_{T} (w_{0}).

Thus, there is a unique maximal element, namely (c; ε, …, ε), where ε stands for the identity element in W, but, if m > 1, there are many different minimal elements. In particular, there is no global minimum in NC^{m}(Φ) if m > 1 and, hence, NC^{m}(Φ) is not a lattice for m > 1. (It is, however, a graded join-semilattice, see [1, Theorem 2.2.7].) We remark that for NC^{m}(A_{n}) and NC^{m}(B_{n}) combinatorial realisations are available as subposets of non-crossing partitions in which each block has a size which is divisible by m. The corresponding translations are due to Armstrong [1, Sec. 3]. In type A_{n}, the resulting poset had been earlier studied by Edelman [9]. The analogous combinatorial realisation of NC^{m}(D_{n}), generalising the one of Athanasiadis and Reiner [3] for m = 1, has not yet been worked out.

Next, we define the “M-triangle” of NC^{m}(Φ) as

M_{Φ}^{m}(x, y) = ∑_{u,w∈NC^{m}(Φ)} μ(u, w) x^{rk u}y^{rk w},

where μ(u, w) is the Möbius function in NC^{m}(Φ).

The generalised version of Chapoton’s (ex-)conjecture [8, Conjecture 1], due to Armstrong [1, Sec. 4], is the following.

Conjecture FM. For any finite root system Φ of rank n, we have

F_{Φ}^{m}(x, y) = y^{n} M_{Φ}^{m} (\frac{1 + y}{y − x}, \frac{y − x}{y}) .

Equivalently,

(1 − xy)^{n}F_{Φ}^{m} (\frac{x(1 + y)}{1 − xy}, \frac{xy}{1 − xy} ) = ∑_{u,w∈(NC^{m}(Φ))^{∗}} μ^{∗}(u, w) (−x)^{rk^{∗} w}(−y)^{rk^{∗} u}, (30)

where (NC^{m}(Φ))^{∗} denotes the poset dual to NC^{m}(Φ) (i.e., the poset which arises from NC^{m}(Φ) by reversing all order relations), where μ^{∗} denotes the Möbius function in (NC^{m}(Φ))^{∗}, and where rk^{∗} denotes the rank function in (NC^{m}(Φ))^{∗}.

Since the Möbius function is multiplicative (see e.g. [19, Prop. 3.8.2]), the multiplicativity property (2) for the F -triangle holds also for the M-triangle. Therefore, it is enough to prove the conjecture for the irreducible root systems. In Sections 9–17, we provide proofs for the root systems of type A_{n}, B_{n}, I_{2}(a), H_{3}, H_{4}, F_{4}, and E_{6}, and a partial proof for the root system of type D_{n}.

9. Proof of the F = M Conjecture for A_{n}. In this section we prove Conjecture FM for the type A_{n}. In the spirit of this paper, we follow a computational approach. We first simplify the left-hand side of (30) by a double application of the Chu–Vandermonde summation. Subsequently, we compute the right-hand side of (30) by relying on a result on rank selected chain enumeration in the m-divisible non-crossing partition lattice in type A_{n} due to Edelman [9].

The link between chain enumeration and the Möbius function is the following. (The reader should consult [19, Sec. 3.11] for more information on this topic.) Given a poset P and two elements u and w, u ≤ w, in the poset, the zeta polynomial of the interval [u, w], denoted by Z(u, w; z), is the number of (multi)chains from u to w of length z. (It can be shown that this is indeed a polynomial in z.) Then the Möbius function of u and w is equal to μ(u, w) = Z(u, w; −1).

Proposition A. In type A_{n}, the left-hand side of (30) is equal to

∑_{r,s≥0} x^{s}y^{r} \frac{1}{s + 1}\binom{n}{s}\binom{m(n + 1)}{r}\binom{m(n + 1) + s − r − 1}{s − r}.  (31)

Proof. By definition of F_{A_{n}}^{m}(x, y), and by Theorem FA in Section 4, the left-hand side of (30) in type A_{n} is equal to

∑_{k,l,r,s≥0} \frac{l + 1}{k + l + 1}\binom{n}{k + l}\binom{m(n + 1) + k − 1}{k}\binom{k}{r}\binom{n − k − l}{s}(−1)^{s}x^{k+l+s}y^{l+r+s}.

Fixing L = s + l, we rewrite this as

∑_{k,L,r≥0} \frac{n! (m(n + 1) + k − 1)!}{(m(n + 1) − 1)! r! (k − r)! (n − k − L)! (k + L + 1)!}x^{k+L}y^{r+L}

· ∑_{s=0}^{L} (L − s + 1)(−1)^{s}\binom{k + L + 1}{s}.

We compute the sum over s by the Chu–Vandermonde summation. Thus, we arrive at

∑_{k,L,r≥0} \frac{n! (m(n + 1) + k − 1)!}{(m(n + 1) − 1)! r! (k − r)! (n − k − L)! (k + L + 1)!}x^{k+L}y^{r+L}(−1)^{L}\binom{k + L − 1}{L}.

We now write K = k + L and R = r + L. Subsequently, the sum over L can be computed using the Chu–Vandermonde summation. The result is

∑_{K,R≥0} \frac{n! (m(n + 1) + K − R − 1)! (m(n + 1))!}{(m(n + 1) − 1)! (m(n + 1) − R)! R! (K − R)! (n − K)! (K + 1)!}x^{K}y^{R}.

Aside from a parameter replacement, this is exactly the expression (31). □

For the computation of the right-hand side of (30) we require the following theorem due to Edelman [9].

Theorem NA. The number of chains in (NC^{m}(A_{n}))^{∗} with successive rank jumps s_{1}, s_{2}, …, s_{ℓ}, s_{1} + s_{2} + ⋯ + s_{ℓ} = n, is

\binom{m(n + 1)}{s_{1}} ⋯ \binom{m(n + 1)}{s_{ℓ−1}} \frac{1}{n + 1}\binom{n + 1}{s_{ℓ}}.  (32)

Proof of Conjecture FM in type A_{n}. We now compute the right-hand side of (30), that is,

∑_{u,w∈(NC^{m}(A_{n}))^{∗}} μ^{∗}(u, w)(−x)^{rk^{∗} w}(−y)^{rk^{∗} u}.

In order to compute the coefficient of x^{s}y^{r} in this expression,

(−1)^{r+s} _{∑_{u,w∈(NC^{m}(A_{n}))^{∗}} with rk^{∗} u=r and rk^{∗} w=s}μ^{∗}(u, w),

we compute the sum of all corresponding zeta polynomials (in the variable z), multiplied by (−1)^{r+s},

(−1)^{r+s} _{∑_{u,w∈(NC^{m}(A_{n}))^{∗}} with rk^{∗} u=r and rk^{∗} w=s}Z(u, w; z),

and then put z = −1.

For computing this sum of zeta polynomials, we must set ℓ = z + 2, s_{1} = r, n − s_{ℓ} = s, s_{2} + s_{3} + ⋯ + s_{ℓ−1} = s − r in (32), and then sum the resulting expression over all possible s_{2}, s_{3}, …, s_{ℓ−1}. By using the Chu–Vandermonde summation, one obtains

\frac{1}{n + 1}\binom{m(n + 1)}{r}\binom{zm(n + 1)}{s − r}\binom{n + 1}{n − s}.

If we put z = −1 in this expression and multiply it by (−1)^{r+s}, then we obtain exactly the coefficient of x^{s}y^{r} in (31). □

10. Proof of the F = M Conjecture for B_{n}. In this section we prove Conjecture FM for the type B_{n}, by following the same approach as the one for type A_{n} in the previous section.

Proposition B. In type B_{n}, the left-hand side of (30) is equal to

∑_{r,s≥0} x^{s}y^{r}\binom{n}{s}\binom{mn}{r}\binom{mn + s − r − 1}{s − r}.  (33)

Proof. By definition of F_{B_{n}}^{m}(x, y), and by Theorem FB in Section 5, the left-hand side of (30) in type B_{n} is equal to

∑_{k,l,r,s≥0} \binom{n}{k + l}\binom{mn + k − 1}{k}\binom{k}{r}\binom{n − k − l}{s}(−1)^{s}x^{k+l+s}y^{l+r+s}.

Fixing L = s + l, we rewrite this as

∑_{k,L,r≥0} \frac{n! (mn + k − 1)!}{(mn − 1)! r! (k − r)! (n − k − L)! (k + L)!}x^{k+L}y^{L+r} ∑_{s=0}^{L}(−1)^{s}\binom{k + L}{s}.

We compute the sum over s by the Chu–Vandermonde summation. Thus, we arrive at

∑_{k,L,r≥0} \frac{n! (mn + k − 1)!}{(mn − 1)! r! (k − r)! (n − k − L)! (k + L)!}x^{k+L}y^{L+r}(−1)^{L}\binom{k + L − 1}{L}.

We now write K = k + L and R = r + L. Subsequently, the sum over L can be computed using the Chu–Vandermonde summation. The result is

∑_{K,R≥0} \frac{n! (mn + K − R − 1)! (mn)!}{(mn − 1)! (mn − R)! R! (K − R)! (n − K)! K!}x^{K}y^{R}.

Aside from a parameter replacement, this is exactly the expression (33). □

For the computation of the right-hand side of (30) we require the following theorem due to Armstrong [1, Theorem 3.5.7].

Theorem NB. The number of chains in (NC^{m}(B_{n}))^{∗} with successive rank jumps s_{1}, s_{2}, …, s_{ℓ}, s_{1} + s_{2} + ⋯ + s_{ℓ} = n, is

\binom{mn}{s_{1}} ⋯ \binom{mn}{s_{ℓ−1}}\binom{n}{s_{ℓ}}.  (34)

Proof of Conjecture FM in type B_{n}. We now compute the right-hand side of (30), that is,

∑_{u,w∈(NC^{m}(B_{n}))^{∗}} μ^{∗}(u, w)(−x)^{rk^{∗} w}(−y)^{rk^{∗} u}.

In order to compute the coefficient of x^{s}y^{r} in this expression,

(−1)^{r+s} _{∑_{u,w∈(NC^{m}(B_{n}))^{∗}} with rk^{∗} u=r and rk^{∗} w=s}μ^{∗}(u, w),

we compute the sum of all corresponding zeta polynomials (in the variable z), multiplied by (−1)^{r+s},

(−1)^{r+s} _{∑_{u,w∈(NC^{m}(B_{n}))^{∗}} with rk^{∗} u=r and rk^{∗} w=s}Z(u, w; z),

and then put z = −1.

For computing this sum of zeta polynomials, we must set ℓ = z + 2, s_{1} = r, n − s_{ℓ} = s, s_{2} + s_{3} + ⋯ + s_{ℓ−1} = s − r in (34), and then sum the resulting expression over all possible s_{2}, s_{3}, …, s_{ℓ−1}. By using the Chu–Vandermonde summation, one obtains

\binom{mn}{r}\binom{zmn}{s − r}\binom{n}{n − s}.

If we put z = −1 in this expression and multiply it by (−1)^{r+s}, then we obtain exactly the coefficient of x^{s}y^{r} in (33). □

11. Towards a proof of the F = M Conjecture for D_{n}. This section exhibits how far the approach of the previous two sections of proving Conjecture FM in types A_{n} and B_{n} can take us in type D_{n}. The simplification of the left-hand side of (30) along the lines of the proofs of Propositions A and B goes through smoothly. The problem which we face in type D_{n} is that, up to this date, the rank selected chain enumeration result for NC^{m}(D_{n}) has not been found yet. Thus, we do not have the means to compute the M-triangle for NC^{m}(D_{n}). The only exception is for m = 1. Namely, for the (ordinary) non-crossing partition lattice NC(D_{n}) = NC^{1}(D_{n}), Athanasiadis and Reiner [3] have done the rank selected chain enumeration as we need it in our application. Hence, we are able to prove Conjecture FM in type D_{n} if m = 1.

Proposition D. In type D_{n}, the left-hand side of (30) is equal to

∑_{r,s≥0} x^{s}y^{r}(2\binom{n − 1}{s − 1}\binom{m(n − 1)}{r}\binom{m(n − 1) + s − r − 1}{s − r}

+ \binom{n − 2}{s}\binom{m(n − 1)}{r}\binom{m(n − 1) + s − r − 1}{s − r}

+ m\binom{n − 1}{s − 1}\binom{m(n − 1) − 1}{r − 2}\binom{m(n − 1) + s − r − 1}{s − r}

− m\binom{n − 1}{s − 1}\binom{m(n − 1)}{r}\binom{m(n − 1) + s − r − 2}{s − r − 2}). (35)

Proof. By definition of F_{D_{n}}^{m}(x, y), and by Theorem FD in Section 6, the left-hand side of (30) in type D_{n} is equal to

∑_{k,l,r,s≥0}\binom{n}{k + l}\binom{m(n − 1) + k − 1}{k}\binom{k}{r}\binom{n − k − l}{s}(−1)^{s}x^{k+l+s}y^{l+r+s}  (36a)

+ m ∑_{k,l,r,s≥0} \binom{n − 1}{k + l − 1}\binom{m(n − 1) + k − 2}{k − 1}\binom{k}{r}\binom{n − k − l}{s}(−1)^{s}x^{k+l+s}y^{l+r+s} (36b)

− \frac{1}{n − 1} ∑_{k,r,s≥0} \binom{n − 1}{k − 1}\binom{m(n − 1) + k − 1}{k}\binom{k}{r}\binom{n − k}{s}(−1)^{s}x^{k+s}y^{r+s}. (36c)

We treat the three sums in (36) separately. We begin with the sum (36a). Fixing L = s+l, we rewrite it as

∑_{k,L,r≥0} \frac{n! (m(n − 1) + k − 1)!}{(m(n − 1) − 1)! r! (k − r)! (n − k − L)! (k + L)!}x^{k+L}y^{L+r} ∑_{s=0}^{L}(−1)^{s}\binom{k + L}{s}.

We compute the sum over s by the Chu–Vandermonde summation. Thus, we arrive at

∑_{k,L,r≥0} \frac{n! (m(n − 1) + k − 1)!}{(m(n − 1) − 1)! r! (k − r)! (n − k − L)! (k + L)!}x^{k+L}y^{L+r}(−1)^{L}\binom{k + L − 1}{L}.

∑_{K,R≥0} \frac{n! (m(n − 1) + K − R − 1)! (m(n − 1))!}{(m(n − 1) − 1)! (m(n − 1) − R)! R! (K − R)! (n − K)! K!}x^{K}y^{R}.  (37)

Next we consider the sum (36b). Again fixing L = s + l, we rewrite it as

∑_{k,L,r≥0} \frac{mk (n − 1)! (m(n − 1) + k − 2)!}{(m(n − 1) − 1)! r! (k − r)! (n − k − L)! (k + L − 1)!}x^{k+L}y^{L+r}

· ∑_{s=0}^{L}(−1)^{s}\binom{k + L − 1}{s}.

We compute the sum over s by the Chu–Vandermonde summation. Thus, we arrive at

∑_{k,L,r≥0} \frac{mk (n − 1)! (m(n − 1) + k − 2)!}{(m(n − 1) − 1)! r! (k − r)! (n − k − L)! (k + L − 1)!}x^{k+L}y^{L+r}(−1)^{L}\binom{k + L − 2}{L}.

We now write K = k + L and R = r + L. Because of the presence of the factor k in the numerator, this makes a factor of K − L appear. We split the sum into two parts accordingly, and then, in both parts, the sum over L can be computed using the Chu– Vandermonde summation. The result is

∑_{K,R≥0} \frac{mK (n − 1)! (m(n − 1) + K − R − 2)! (m(n − 1))!}{(m(n − 1) − 1)! (m(n − 1) − R)! R! (K − R)! (n − K)! (K − 1)!}x^{K}y^{R}

− ∑_{K,R≥0} \frac{m(K − 2) (n − 1)! (m(n − 1) + K − R − 2)! (m(n − 1))!}{(m(n − 1) − 1)! (m(n − 1) − R + 1)! (R − 1)! (K − R)! (n − K)! (K − 1)!}x^{K}y^{R}. (38)

Finally, we turn to the sum (36c). We write K = k + s and R = r + s. Subsequently, the sum over s can be computed using the Chu–Vandermonde summation. The result is

− ∑_{K,R≥0} \frac{1}{n − 1} \frac{(n − 1)! (m(n − 1) + K − R − 1)! (m(n − 1))!}{(m(n − 1) − 1)! (m(n − 1) − R)! R! (K − R)! (n − K)! (K − 1)!}x^{K}y^{R}.

(39)

To complete the proof, we add the expressions (37), (38) and (39). Doing the parameter replacements K → s, R → r and minor rewriting, this leads to the expression

∑_{r,s≥0} x^{s}y^{r}(\binom{n}{s}\binom{m(n − 1)}{r}\binom{m(n − 1) + s − r − 1}{s − r}

+ \frac{ms}{s − r} \binom{n − 1}{s − 1}\binom{m(n − 1)}{r}\binom{m(n − 1) + s − r − 2}{s − r − 1}

+ \frac{m(s − 2)}{s − r}\binom{n − 1}{s − 1}\binom{m(n − 1)}{r − 1}\binom{m(n − 1) + s − r − 2}{s − r − 1}

− \frac{1}{n − 1}\binom{n − 1}{s − 1}\binom{m(n − 1)}{r}\binom{m(n − 1) + s − r − 1}{s − r}).

It is now a routine verification to show that an alternative way to write this is (35). □

For the computation of the right-hand side of (30) in the case that m = 1, we require the following result due to Athanasiadis and Reiner [3, Theorem 1.2(ii)].

Theorem ND. The number of chains in NC(D_{n}) with successive rank jumps s_{1}, s_{2}, …, s_{ℓ}, s_{1} + s_{2} + ⋯ + s_{ℓ} = n, is given by

2\binom{n − 1}{s_{1}} ⋯ \binom{n − 1}{s_{ℓ}} + ∑_{i=1}^{ℓ} \binom{n − 1}{s_{1}} ⋯ \binom{n − 2}{s_{i} − 2} ⋯ \binom{n − 1}{s_{ℓ}}.  (40)

Proof of Conjecture FM for m = 1 in type D_{n}. If m = 1, then NC^{m}(D_{n}) reduces to the ordinary non-crossing partition lattice NC(D_{n}), which is self-dual, that is, (NC(D_{n}))^{∗} = NC(D_{n}). Hence, the right-hand side of (30) with m = 1 in type D_{n} is equal to

∑_{u,w∈NC(D_{n})} μ(u, w)(−x)^{rk w}(−y)^{rk u}.

In order to compute the coefficient of x^{s}y^{r} in this expression,

(−1)^{r+s} _{∑_{u,w∈NC(D_{n})} with rk u=r and rk w=s}μ(u, w),

we compute the sum of all corresponding zeta polynomials (in the variable z), multiplied by (−1)^{r+s},

(−1)^{r+s} _{∑_{u,w∈NC(D_{n})} with rk u=r and rk w=s}Z(u, w; z),

and then put z = −1.

For computing this sum of zeta polynomials, we must set ℓ = z + 2, s_{1} = r, n − s_{ℓ} = s, s_{2} + s_{3} + ⋯ + s_{ℓ−1} = s − r in (40), and then sum the resulting expression over all possible s_{2}, s_{3}, …, s_{ℓ−1}. By using the Chu–Vandermonde summation again, one obtains

2\binom{n − 1}{r}\binom{z(n − 1)}{s − r}\binom{n − 1}{n − s} + \binom{n − 2}{r − 2}\binom{z(n − 1)}{s − r}\binom{n − 1}{n − s}

+ \binom{n − 1}{r}\binom{z(n − 1)}{s − r}\binom{n − 2}{n − s − 2} + z\binom{n − 1}{r}\binom{z(n − 1) − 1}{s − r − 2}\binom{n − 1}{n − s}.

If we put z = −1 in this expression and multiply it by (−1)^{r+s}, then we obtain exactly the coefficient of x^{s}y^{r} in (35) with m = 1. □

12. How to prove the F = M Conjecture in the exceptional cases. While, at first sight, for a given exceptional root system Φ, it seems that computing the Mtriangle (respectively the right-hand side of (30)) for arbitrary m is an infinite problem because we have to compute Möbius functions for NC^{m}(Φ) (respectively for (NC^{m}(Φ))^{∗}) for m = 1, 2, …, this is not really true. We should recall from (29) that an element of NC^{m}(Φ) has the form

(w_{0}; w_{1}, …, w_{m}), with w_{0}w_{1} ⋯ w_{m} = c and ℓ_{T} (w_{0}) + ℓ_{T} (w_{1}) + ⋯ + ℓ_{T} (w_{m}) = ℓ_{T} (c) = n, (41)

where n is the rank of the root system Φ. Now, n can be at most 8 for an exceptional root system (with equality only for Φ = E_{8}). This implies that only at most 8 of the w_{i}’s can be different from the identity element ε in W = W (Φ). Hence, a typical interval in (NC^{m}(Φ))^{∗} looks like [u, w], where

u = (u_{0}; u_{1}, …, u_{m}), w = (w_{0}; w_{1}, …, w_{m}),

u_{i} = w_{i} = ε for all but at most 8 indices i ≥ 1, and u_{i} ≤ w_{i} for these remaining indices. Let these latter indices be i_{1}, i_{2}, …, i_{d}, with d ≤ 8. Then, such an interval [u, w] is isomorphic to the “compressed” interval [u′, w′], where

u′ = (u_{0}; u_{i_{1}}, …, u_{i_{d}}), w′ = (w_{0}; w_{i_{1}}, …, w_{i_{d}}).

Note that “compressed” means that all of w_{i_{1}}, w_{i_{2}}, …, w_{i_{d}} are different from ε.

So, what we have to do is to determine all different compressed intervals [u′, w′]. The contribution of a compressed interval [u′, w′] to the right-hand side of (30) is then

\binom{m}{d} · μ^{∗}(u′, w′) x^{rk^{∗} w′}y^{rk^{∗} u′},  (42)

because there are \binom{m}{d} different ways to choose \{i_{1}, i_{2}, …, i_{d}\} out of \{1, 2, …, m\}. To obtain the M-triangle we “just” have to collect all these contributions and sum them over all possible compressed intervals. Note that this is now a finite problem because the number of compressed intervals is finite.

Rather than running through all compressed intervals, a more efficient way to implement this is as follows. We rewrite the right-hand side of (30) as

∑_{u,w∈(NC^{m}(Φ))^{∗}} μ^{∗}(u, w) (−x)^{rk^{∗} w}(−y)^{rk^{∗} u} = ∑_{w∈(NC^{m}(Φ))^{∗}}(−x)^{rk^{∗} w} · χ_{[ˆ0,w]}^{∗}(−y), (43)

where ˆ0 = (c; ε, …, ε) is the minimum in (NC^{m}(Φ))^{∗}, and where

χ_{[ˆ0,w]}^{∗}(y) = ∑_{u∈(NC^{m}(Φ))^{∗}} μ^{∗}(u, w) y^{rk^{∗} u}

is, essentially, the characteristic polynomial of the interval [ˆ0, w]. (To be precise, it is the characteristic polynomial of the interval [w, ˆ0] in NC^{m}(Φ), see [19, Sec. 3.10].) If w = (w_{0}; w_{1}, …, w_{m}) with w_{i_{1}}, w_{i_{2}}, …, w_{i_{d}} those among w_{1}, w_{2}, …, w_{m} which are different from the identity element ε, then

[ˆ0, w] ≅ [ε, w_{i_{1}}] × [ε, w_{i_{2}}] × ⋯ × [ε, w_{i_{d}}],

where each interval [ε, w_{i_{j}}] is an interval in NC(Φ). Since the characteristic polynomial is multiplicative, this implies

χ_{[ˆ0,w]}^{∗}(y) = χ_{[ε,w_{i_{1}} ]}^{∗}(y)χ_{[ε,w_{i_{2}} ]}^{∗}(y) ⋯ χ_{[ε,w_{i_{d}}]}^{∗}(y),

where χ_{[ε,w_{i_{j}}]}^{∗}(y) = ∑_{v∈NC(Φ)} μ(v, w_{i_{j}})y^{rk v}, with μ the Möbius function and rk the rank function in NC(Φ).

According to a result by Bessis [4, Lemma 1.4.3, Cor. 1.6.2], each element w_{i_{j}} is some parabolic Coxeter element (that is, a Coxeter element in some parabolic subgroup), and the interval [ε, w_{i_{j}}] is isomorphic to some NC(Ψ), where Ψ is the root system of this parabolic subgroup.

If we put all this together, then (43) becomes

∑_{d=0}^{n} ∑_{(T_{1},...,T_{d})}(−x)^{rk T_{1}+···+rk T_{d}} · N_{Φ}(T_{1}, T_{2}, …, T_{d})

· χ_{NC(T_{1})}^{∗}(−y)χ_{NC(T_{2})}^{∗}(−y) ⋯ χ_{NC(T_{d})}^{∗}(−y)\binom{m}{d}, (44)

where the inner sum is over all possible d-tuples (T_{1}, T_{2}, …, T_{d}) of types (not necessarily irreducible types), and where N_{Φ}(T_{1}, T_{2}, …, T_{d}) is the number of “minimal” products c_{1}c_{2} ⋯ c_{d} less than or equal to the Coxeter element c in absolute order, “minimal” meaning that all the c_{i}’s are different from ε and that ℓ_{T} (c_{1})+ℓ_{T} (c_{2})+⋯+ℓ_{T} (c_{d}) = ℓ_{T} (c_{1}c_{2} ⋯ c_{d}), such that the type of c_{i} as a parabolic Coxeter element is T_{i}, i = 1, 2, …, d. The notation NC(T) in (44) means NC(Ψ), where Ψ is a root system of type T, and rk T denotes the rank of Ψ. We point out that the appearance of the binomial coefficient \binom{m}{d} is explained by (42).

So, what we have to do to apply formula (44) to compute the right-hand side of (30) is, first, to determine all the “decomposition numbers” N_{Φ}(T_{1}, T_{2}, …, T_{d}). Since we shall refer to it later, we point out that these decomposition numbers have many relations between themselves. For example, the number N_{Φ}(T_{1}, T_{2}, …, T_{d}) is independent of the order of the types T_{1}, T_{2}, …, T_{d}, that is, we have

N_{Φ}(T_{σ(1)}, T_{σ(2)}, …, T_{σ(d)}) = N_{Φ}(T_{1}, T_{2}, …, T_{d})  (45)

for any permutation σ of {1, 2, …, d}. This follows from the (proof of the) Shifting Lemma (see [1, Lemma 1.3.1]). Furthermore, by the definition of these numbers, those of “lower rank” can be computed from those of “full rank.” To be precise, we have

N_{Φ}(T_{1}, T_{2}, …, T_{d}) = ∑_{T} N_{Φ}(T_{1}, T_{2}, …, T_{d}, T),  (46)

where the sum is over all types T of rank n−rk T_{1} −rk T_{2} −⋯−rk T_{d} (with n still denoting the rank of the fixed root system Φ).

Second, one needs a list of the characteristic polynomials χ_{NC(Ψ)}^{∗}(y) for all irreducible root systems Ψ. (By the multiplicativity of the characteristic polynomial, this then gives also formulae for the characteristic polynomials of all the reducible types.) In fact, the numbers N_{Ψ}(T_{1}, T_{2}, …, T_{d}) carry all the information which is necessary to do this recursively. Namely, by the definition of NC(Ψ) and of the decomposition numbers N_{Ψ}(T_{1}, T_{2}, …, T_{d}), we have

χ_{NC(Ψ)}^{∗}(y) = ∑_{T_{1},T_{2}} N_{Ψ}(T_{1}, T_{2}) μ_{NC(T_{2})}(ˆ0_{NC(T_{2})}, ˆ1_{NC(T_{2})}) y^{rk T_{1}},  (47)

where μ_{NC(T_{2})}(., .) denotes the Möbius function in NC(T_{2}), and where ˆ0_{NC(T_{2})} and ˆ1_{NC(T_{2})} are, respectively, the minimal and the maximal element in NC(T_{2}). Indeed, inductively, the Möbius functions μ_{NC(T_{2})}(ˆ0_{NC(T_{2})}, ˆ1_{NC(T_{2})}) are already known for all T_{2} of lower rank than the rank of Ψ. Hence, the only unknown in (47) is μ_{NC(Ψ)}(ˆ0_{NC(Ψ)}, ˆ1_{NC(Ψ)}). However, the latter can be computed by setting y = 1 in (47) and using the fact that χ_{NC(Ψ)}^{∗}(1) = 0 for all root systems Ψ of rank at least 1. (This fact is equivalent to the statement that ∑_{u∈NC(Ψ)} μ_{NC(Ψ)}(u, ˆ1_{NC(Ψ)}) = 0, which is nothing but a part of the definition of the Möbius function. Alternatively, one may use the uniform formula for the zeta polynomial of the non-crossing partition lattices, in which one specializes the variable to −1. See [8, Prop. 9]; the reader may be warned that a slightly different convention for the zeta polynomial is used there.)

We show in Sections 13–17 how to implement this procedure for the dihedral root system I_{2}(a), for the hyperbolic root systems H_{3} and H_{4}, and for F_{4} and E_{6}. We list the values of the characteristic polynomials of the irreducible root systems that we need below.

χ_{A_{1}}^{∗}(y) = y − 1,
χ_{A_{2}}^{∗}(y) = y^{2} − 3y + 2,
χ_{I_{2}(a)}^{∗}(y) = y^{2} − ay + a − 1,
χ_{A_{3}}^{∗}(y) = y^{3} − 6y^{2} + 10y − 5,
χ_{A_{4}}^{∗}(y) = y^{4} − 10y^{3} + 30y^{2} − 35y + 14,
χ_{A_{5}}^{∗}(y) = y^{5} − 15y^{4} + 70y^{3} − 140y^{2} + 126y − 42,
χ_{B_{3}}^{∗}(y) = y^{3} − 9y^{2} + 18y − 10,
χ_{D_{4}}^{∗}(y) = y^{4} − 12y^{3} + 39y^{2} − 48y + 20,
χ_{D_{5}}^{∗}(y) = y^{5} − 20y^{4} + 106y^{3} − 230y^{2} + 220y − 77,
χ_{H_{3}}^{∗}(y) = y^{3} − 15y^{2} + 35y − 21,
χ_{F_{4}}^{∗}(y) = y^{4} − 24y^{3} + 101y^{2} − 144y + 66,
χ_{H_{4}}^{∗}(y) = y^{4} − 60y^{3} + 307y^{2} − 480y + 232,
χ_{E_{6}}^{∗}(y) = y^{6} − 36y^{5} + 300y^{4} − 1035y^{3} + 1720y^{2} − 1368y + 418.  (48)

13. Proof of the F = M Conjecture for I_{2}(a). By (22), we have

(1 − xy)^{2}F_{I_{2}(a)}^{m} (\frac{x(1 + y)}{1 − xy}, \frac{xy}{1 − xy} ) = \frac{m(am − a + 2)}{2}x^{2}y^{2} + am^{2}x^{2}y

+ \frac{m(am + a − 2)}{2}x^{2} + amxy + amx + 1 (49)

for the left-hand side of (30).

We now compute the right-hand side of (30) following the proposed procedure in the previous section. We have N_{I_{2}(a)}(I_{2}(a)) = 1, N_{I_{2}(a)}(A_{1}, A_{1}) = a, N_{I_{2}(a)}(A_{1}) = a, N_{I_{2}(a)}(∅) = 1, all other numbers N_{I_{2}(a)}(T_{1}, …, T_{d}) being zero. Thus, according to (44) and (48), the right-hand side of (30) is equal to

(−x)^{2}(y^{2} + ay + a − 1)m + (−x)^{2}a(−y − 1)^{2}\binom{m}{2} + (−x)a(−y − 1)m + 1,

which agrees with (49). □

14. Proof of the F = M Conjecture for H_{3}. By (23), we have

(1 − xy)^{3}F_{H_{3}}^{m} (\frac{x(1 + y)}{1 − xy}, \frac{xy}{1 − xy} ) = \frac{m(5m − 4)(5m − 2)}{3}x^{3}y^{3} + 5m^{2}(5m − 2)x^{3}y^{2}

+ \frac{m(5m + 2)(5m + 4)}{3}x^{3} + 5m^{2}(5m + 2)x^{3}y + 5m(5m − 2)x^{2}y^{2}

+ 50m^{2}x^{2}y + 5m(5m + 2)x^{2} + 15mxy + 15mx + 1 (50)

for the left-hand side of (30).

We now compute the right-hand side of (30) following the proposed procedure in Section 12. The conclusions which we report here are based on Maple computations which we performed using Stembridge’s coxeter package [20].

We have N_{H_{3}}(H_{3}) = 1, N_{H_{3}}(A_{1}^{2}, A_{1}) = 5, N_{H_{3}}(A_{2}, A_{1}) = 5, N_{H_{3}}(I_{2}(5), A_{1}) = 5, N_{H_{3}}(A_{1}, A_{1}, A_{1}) = 50, plus the assignments implied by (45) and (46), all other numbers N_{H_{3}}(T_{1}, …, T_{d}) being zero. Thus, according to (44) and (48), the right-hand side of (30) is equal to

(−x)^{3}(−y^{3} − 15y^{2} − 35y − 21)m + 2 · (−x)^{3}5(−y − 1)^{3}\binom{m}{2}

+ 2 · (−x)^{3}5(y^{2} + 3y + 2)(−y − 1)\binom{m}{2} + 2 · (−x)^{3}5(y^{2} + 5y + 4)(−y − 1)\binom{m}{2}

+ (−x)^{3}50(−y − 1)^{3}\binom{m}{3} + (−x)^{2}5(−y − 1)^{2}m + (−x)^{2}5(y^{2} + 3y + 2)m

+ (−x)^{2}5(y^{2} + 5y + 4)m + (−x)^{2}50(−y − 1)^{2}\binom{m}{2} + (−x)15(−y − 1)m + 1,

which agrees with (50). □

15. Proof of the F = M Conjecture for H_{4}. By (24), we have

(1 − xy)^{4}F_{H_{4}}^{m} (\frac{x(1 + y)}{1 − xy}, \frac{xy}{1 − xy} ) = \frac{1}{4}m(3m − 1)(5m − 3)(15m − 14)x^{4}y^{4}

+ 15m^{2}(3m − 1)(5m − 3)x^{4}y^{3} + \frac{1}{2}m^{2} (675m^{2} − 61) x^{4}y^{2}

+ 15m^{2}(3m + 1)(5m + 3)x^{4}y + \frac{1}{4}m(3m + 1)(5m + 3)(15m + 14)x^{4}

+ 15m(3m − 1)(5m − 3)x^{3}y^{3} + 15m^{2}(45m − 14)x^{3}y^{2}
+ 15m^{2}(45m + 14)x^{3}y + 15m(3m + 1)(5m + 3)x^{3}

+ \frac{1}{2}m(465m − 149)x^{2}y^{2} + 465m^{2}x^{2}y + \frac{1}{2}m(465m + 149)x^{2} + 60mxy + 60mx + 1 (51)

for the left-hand side of (30).

We now compute the right-hand side of (30) following the proposed procedure in Section 12. The conclusions which we report here are based on Maple computations which we performed using Stembridge’s coxeter package [20].

We have N_{H_{4}}(H_{4}) = 1, N_{H_{4}}(A_{1} ∗ A_{2}, A_{1}) = 15, N_{H_{4}}(A_{3}, A_{1}) = 15, N_{H_{4}}(H_{3}, A_{1}) = 15, N_{H_{4}}(A_{1} ∗ I_{2}(5), A_{1}) = 15, N_{H_{4}}(A_{1}^{2}, A_{1}^{2}) = 30, N_{H_{4}}(A_{1}^{2}, A_{2}) = 30, N_{H_{4}}(A_{1}^{2}, I_{2}(5)) = 15, N_{H_{4}}(A_{2}, A_{2}) = 5, N_{H_{4}}(A_{2}, I_{2}(5)) = 15, N_{H_{4}}(I_{2}(5), I_{2}(5)) = 3, N_{H_{4}}(A_{1}^{2}, A_{1}, A_{1}) = 225, N_{H_{4}}(A_{2}, A_{1}, A_{1}) = 150, N_{H_{4}}(I_{2}(5), A_{1}, A_{1}) = 90, N_{H_{4}}(A_{1}, A_{1}, A_{1}, A_{1}) = 1350, plus the assignments implied by (45) and (46), all other numbers N_{H_{4}}(T_{1}, …, T_{d}) being zero. If one substitutes accordingly in (44), using the information from (48), then one obtains an expression which agrees with (51) after simplification. □

16. Proof of the F = M Conjecture for F_{4}. By (25), we have

(1 − xy)^{4}F_{F_{4}}^{m} (\frac{x(1 + y)}{1 − xy}, \frac{xy}{1 − xy} ) = \frac{1}{2}m(2m − 1)(3m − 1)(6m − 5)x^{4}y^{4}

+ 12m^{2}(2m − 1)(3m − 1)x^{4}y^{3} + m^{2} (108m^{2} − 7) x^{4}y^{2}

+ 12m^{2}(2m + 1)(3m + 1)x^{4}y + \frac{1}{2}m(2m + 1)(3m + 1)(6m + 5)x^{4}

+ 12m(2m − 1)(3m − 1)x^{3}y^{3} + 12m^{2}(18m − 5)x^{3}y^{2}

+ 12m^{2}(18m + 5)x^{3}y + 12m(2m + 1)(3m + 1)x^{3} + m(78m − 23)x^{2}y^{2}

+ 156m^{2}x^{2}y + m(78m + 23)x^{2} + 24mxy + 24mx + 1 (52)

for the left-hand side of (30).

We now compute the right-hand side of (30) following the proposed procedure in Section 12. The conclusions which we report here are based on Maple computations which we performed using Stembridge’s coxeter package [20].

We have N_{F_{4}}(F_{4}) = 1, N_{F_{4}}(A_{1} ∗ A_{2}, A_{1}) = 12, N_{F_{4}}(B_{3}, A_{1}) = 12, N_{F_{4}}(A_{1}^{2}, A_{1}^{2}) = 12, N_{F_{4}}(A_{1}^{2}, B_{2}) = 12, N_{F_{4}}(A_{2}, A_{2}) = 16, N_{F_{4}}(B_{2}, B_{2}) = 3, N_{F_{4}}(A_{1}^{2}, A_{1}, A_{1}) = 72, N_{F_{4}}(A_{2}, A_{1}, A_{1}) = 48, N_{F_{4}}(B_{2}, A_{1}, A_{1}) = 36, N_{F_{4}}(A_{1}, A_{1}, A_{1}, A_{1}) = 432, plus the assignments implied by (45) and (46), all other numbers N_{F_{4}}(T_{1}, …, T_{d}) being zero. If one substitutes accordingly in (44), using the information from (48), then one obtains an expression which agrees with (52) after simplification. □

17. Proof of the F = M Conjecture for E_{6}. By (26), we have

(1 − xy)^{6}F_{E_{6}}^{m} ( \frac{x(1 + y)}{1 − xy} , \frac{xy}{1 − xy} ) = \frac{1}{30} m(2m − 1)(3m − 1)(4m − 1)(6m − 5)(12m − 7)x^{6}y^{6}

+ \frac{6}{5} m^{2}(2m − 1)(3m − 1)(4m − 1)(12m − 7)x^{6}y^{5} + 2m^{2}(3m − 1)(4m − 1) (36m^{2} − 9m − 2) x^{6}y^{4}

+ 3m^{2}(4m − 1)(4m + 1) (24m^{2} − 1) x^{6}y^{3} + 2m^{2}(3m + 1)(4m + 1) (36m^{2} + 9m − 2) x^{6}y^{2}

+ \frac{6}{5} m^{2}(2m + 1)(3m + 1)(4m + 1)(12m + 7)x^{6}y + \frac{1}{30} m(2m + 1)(3m + 1)(4m + 1)(6m + 5)(12m + 7)x^{6}

+ \frac{6}{5} m(2m − 1)(3m − 1)(4m − 1)(12m − 7)x^{5}y^{5} + 12m^{2}(3m − 1)(4m − 1)(12m − 5)x^{5}y^{4}

+ 6m^{2}(4m − 1) (144m^{2} − 12m − 5) x^{5}y^{3} + 6m^{2}(4m + 1) (144m^{2} + 12m − 5) x^{5}y^{2}

+ 12m^{2}(3m + 1)(4m + 1)(12m + 5)x^{5}y + \frac{6}{5} m(2m + 1)(3m + 1)(4m + 1)(12m + 7)x^{5}

+ 2m(3m − 1)(4m − 1)(30m − 13)x^{4}y^{4} + 6m^{2}(4m − 1)(120m − 31)x^{4}y^{3} + 16m^{2} (270m^{2} − 7) x^{4}y^{2} + 6m^{2}(4m + 1)(120m + 31)x^{4}y + 2m(3m + 1)(4m + 1)(30m + 13)x^{4} + 9m(4m − 1)(18m − 5)x^{3}y^{3}

+ 18m^{2}(108m − 19)x^{3}y^{2} + 18m^{2}(108m + 19)x^{3}y + 9m(4m + 1)(18m + 5)x^{3} + 12m(21m − 4)x^{2}y^{2}
+ 504m^{2}x^{2}y + 12m(21m + 4)x^{2} + 36mxy + 36mx + 1

(53)

for the left-hand side of (30).

We now compute the right-hand side of (30) following the proposed procedure in Section 12. The conclusions which we report here are based on Maple computations which we performed using Stembridge’s coxeter package [20].

We have N_{E_{6}}(E_{6}) = 1, N_{E_{6}}(A_{1} ∗ A_{2}^{2}, A_{1}) = 6, N_{E_{6}}(A_{1} ∗ A_{4}, A_{1}) = 12, N_{E_{6}}(A_{5}, A_{1}) = 6, N_{E_{6}}(D_{5}, A_{1}) = 12, N_{E_{6}}(A_{1}^{2} ∗ A_{2}, A_{2}) = 36, N_{E_{6}}(A_{2}^{2}, A_{2}) = 8, N_{E_{6}}(A_{1} ∗ A_{3}, A_{2}) = 24, N_{E_{6}}(A_{4}, A_{2}) = 24, N_{E_{6}}(D_{4}, A_{2}) = 4, N_{E_{6}}(A_{1}^{2} ∗ A_{2}, A_{1}^{2}) = 18, N_{E_{6}}(A_{1} ∗ A_{3}, A_{1}^{2}) = 36, N_{E_{6}}(A_{4}, A_{1}^{2}) = 36, N_{E_{6}}(D_{4}, A_{1}^{2}) = 18, N_{E_{6}}(A_{1}^{3}, A_{1}^{3}) = 12, N_{E_{6}}(A_{1} ∗ A_{2}, A_{1}^{3}) = 24, N_{E_{6}}(A_{1} ∗ A_{2}, A_{1} ∗ A_{2}) = 48, N_{E_{6}}(A_{3}, A_{1}^{3}) = 36, N_{E_{6}}(A_{3}, A_{1} ∗ A_{2}) = 72, N_{E_{6}}(A_{3}, A_{3}) = 27, N_{E_{6}}(A_{1}^{2} ∗ A_{2}, A_{1}, A_{1}) = 144, N_{E_{6}}(A_{2}^{2}, A_{1}, A_{1}) = 24, N_{E_{6}}(A_{1} ∗ A_{3}, A_{1}, A_{1}) = 144, N_{E_{6}}(A_{4}, A_{1}, A_{1}) = 144, N_{E_{6}}(D_{4}, A_{1}, A_{1}) = 48, N_{E_{6}}(A_{1}^{3}, A_{1}^{2}, A_{1}) = 180, N_{E_{6}}(A_{1}^{3}, A_{2}, A_{1}) = 168, N_{E_{6}}(A_{1} ∗ A_{2}, A_{1}^{2}, A_{1}) = 360, N_{E_{6}}(A_{1} ∗ A_{2}, A_{2}, A_{1}) = 336, N_{E_{6}}(A_{3}, A_{1}^{2}, A_{1}) = 378, N_{E_{6}}(A_{3}, A_{2}, A_{1}) = 180, N_{E_{6}}(A_{1}^{2}, A_{1}^{2}, A_{1}^{2}) = 432, N_{E_{6}}(A_{2}, A_{1}^{2}, A_{1}^{2}) = 504, N_{E_{6}}(A_{2}, A_{2}, A_{1}^{2}) = 288, N_{E_{6}}(A_{2}, A_{2}, A_{2}) = 160, N_{E_{6}}(A_{1}^{2}, A_{1}^{2}, A_{1}, A_{1}) = 2376, N_{E_{6}}(A_{2}, A_{1}^{2}, A_{1}, A_{1}) = 1872, N_{E_{6}}(A_{2}, A_{2}, A_{1}, A_{1}) = 1056, N_{E_{6}}(A_{1}^{3}, A_{1}, A_{1}, A_{1}) = 864, N_{E_{6}}(A_{1} ∗ A_{2}, A_{1}, A_{1}, A_{1}) = 1728, N_{E_{6}}(A_{3}, A_{1}, A_{1}, A_{1}) = 1296, N_{E_{6}}(A_{1}^{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 10368, N_{E_{6}}(A_{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 6912, N_{E_{6}}(A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 41472, plus the assignments implied by (45) and (46), all other numbers N_{E_{6}}(T_{1}, …, T_{d}) being zero. If one substitutes accordingly in (44), using the information from (48), then one obtains an expression which agrees with (53) after simplification. □

18. The dual F -triangle. Armstrong [1, Sec. 4] defines the dual F -triangle, denoted here by F̃_{Φ}^{m}(x, y), as

F̃_{Φ}^{m}(x, y) = (−1)^{n}F_{Φ}^{m}(−1 − x, −1 − y),

where n is the rank of the root system Φ. He conjectures that the dual F -triangle can be expressed in form of a weighted bivariate generating function for the faces of Δ^{m}(Φ) involving the Fuss–Narayana numbers Nar^{m}(Φ, i), the latter enumerating all elements of rank i in the m-divisible non-crossing partition poset NC^{m}(Φ). For explicit formulae for the Fuss–Narayana numbers see [1, Theorem 2.3.6]. These numbers occur also as h-numbers in [10, Theorem 9.2]. (One has to reverse the ordering of the numbers to convert one sequence of numbers into the other.) In view of our proof below, Armstrong’s conjecture becomes the following theorem.

Theorem DF. For any finite root system Φ, we have

F̃_{Φ}^{m}(x, y) = ∑_{k,l≥0} \frac{Nar^{m}(Φ, k + l)}{Nar^{1}(Φ, k + l)}f_{k,l} x^{k}y^{l}.  (54)

Proof. Clearly, for the exceptional root systems one can verify (54) routinely by using the explicit formulae for the refined face numbers, as given through the formulae for the F -triangle in Section 7, and the formulae for the Fuss–Narayana numbers in [1, 10].

To verify (54) for the root systems A_{n}, B_{n} and D_{n}, some work has to be done. However, the verifications in these types are very similar to each other so that we give below only the proof in type A_{n}, leaving the proofs for B_{n} and D_{n} to the reader.

By Theorem FA, in type A_{n} the left-hand side of (54) is equal to

(−1)^{n} ∑_{k,l≥0} \frac{l + 1}{k + l + 1}\binom{n}{k + l}\binom{m(n + 1) + k − 1}{k}(−1 − x)^{k}(−1 − y)^{l}

= ∑_{k,l,r,s≥0} \frac{l + 1}{k + l + 1}\binom{n}{k + l}\binom{m(n + 1) + k − 1}{k}\binom{k}{r}\binom{l}{s}(−1)^{n+k+l}x^{r}y^{s}

= ∑_{k,r,s≥0} \frac{s + 1}{n + 1}\binom{n − s − 1}{n − k − s}\binom{m(n + 1) + k − 1}{k}\binom{k}{r}(−1)^{n+k+s}x^{r}y^{s}

= ∑_{k,r,s≥0} \frac{s + 1}{n + 1}\binom{n − s − 1}{n − k − s}\binom{m(n + 1) + k − 1}{k − r}\binom{m(n + 1) + r − 1}{r}(−1)^{n+k+s}x^{r}y^{s}

= ∑_{r,s≥0} \frac{s + 1}{n + 1}\binom{m(n + 1)}{n − s − r}\binom{m(n + 1) + r − 1}{r}x^{r}y^{s}.

As earlier, for the evaluation of the sums over l and k we used special instances of the Chu–Vandermonde summation.

On the other hand, by Theorem FA and by [1, Theorem 2.3.6], the right-hand side of (54) is equal to

∑_{k,l≥0} \begin{matrix}\frac{1}{n+1} & \binom{n+1}{k+l} & \binom{m(n+1)}{n−k−l} \\ \frac{1}{n+1} & \binom{n+1}{k+l} & \binom{n+1}{n−k−l} \end{matrix} \frac{l + 1}{k + l + 1}\binom{n}{k + l}\binom{m(n + 1) + k − 1}{k}x^{k}y^{l},

which is exactly the same expression. □

Acknowledgement. I am indebted to Sergey Fomin for suggesting to me to embark on this project and, thus, to the Institut Mittag–Leffler, Anders Björner and Richard Stanley for hosting both of us at the same time at the Institut during the “Algebraic Combinatorics” programme in Spring 2005. Moreover, I wish to thank Drew Armstrong, Christos Athanasiadis and Eleni Tzanaki for the many extremely helpful exchanges that I had with them on the subject matter, and for making drafts for [1], [2] and [21] available to me at an early stage. Last, but not least, I am indebted to the referee for an extremely careful reading of the manuscript.

References

1. D. Armstrong, Generalized noncrossing partitions and combinatorics of Coxeter groups, preprint.

2. C. A. Athanasiadis, On some enumerative aspects of generalized associahedra, preprint;

arXiv:math.CO/0508030.

3. C. A. Athanasiadis and V. Reiner, Noncrossing partitions for the group D_{n}, SIAM J. Discrete Math. 18 (2004), 397–417.

4. D. Bessis, The dual braid monoid, Ann. Sci. École Norm. Sup. (4) 36 (2003), 647–683.

5. T. Brady and C. Watt, K(π, 1)’s for Artin groups of finite type, Geom. Dedicata 94 (2002), 225–250.

6. T. Brady and C. Watt, Lattices in finite reflection groups, preprint; arXiv:math.CO/0501502.

7. L. Carlitz, Some expansion and convolution formulas related to MacMahon’s master theorem, SIAM J. Math. Anal. 8 (1977), 320–336.

8. F. Chapoton, Enumerative properties of generalized associahedra, Séminaire Lotharingien Combin. 51 (2004), Article B51b, 16 pp.

9. P. Edelman, Chain enumeration and noncrossing partitions, Discrete Math. 31 (1981), 171–180.

10. S. Fomin and N. Reading, Generalized cluster complexes and Coxeter combinatorics, Int. Math. Res. Notices 44, 2709–2757.

11. S. Fomin and A. Zelevinsky, Cluster algebras I: Foundations, J. Amer. Math. Soc. 15 (2002), 497–529.

12. S. Fomin and A. Zelevinsky, Cluster algebras II: Finite type classification, Invent. Math. 154 (2003), 63–121.

13. S. Fomin and A. Zelevinsky, Y -systems and generalized associahedra, Ann. of Math. (2) 158 (2003), 977–1018.

14. R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, Massachusetts, 1989.

15. J. E. Humphreys, Reflection groups and Coxeter groups, Cambridge University Press, Cambridge, 1990.

16. G. Kreweras, Sur les partitions non croisées d’un cycle, Discrete Math. 1 (1972), 333–350.

17. V. Reiner, Non-crossing partitions for classical reflection groups, Discrete Math. 177 (1997), 195–222.

18. L. J. Slater, Generalized hypergeometric functions, Cambridge University Press, Cambridge, 1966.

19. R. P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, California, 1986, reprinted by Cambridge University Press, Cambridge, 1998.

20. J. R. Stembridge, coxeter, Maple package for working with root systems and finite Coxeter groups;

available at http://www.math.lsa.umich.edu/~jrs.

21. E. Tzanaki, Combinatorics of generalized cluster complexes and hyperplane arrangements, Ph.D. thesis, University of Crete, Iraklio, in preparation.

Institut Camille Jordan, Université Claude Bernard Lyon-I, 21, avenue Claude Bernard, F-69622 Villeurbanne Cedex, France. WWW: http://igd.univ-lyon1.fr/~kratt