Séminaire Lotharingien de Combinatoire 54 (2006), Article B54l

The M-triangle of generalised non-crossing partitions for the types E_{7} and E_{8}

C. Krattenthaler^{†}

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

            WWW: http://www.mat.univie.ac.at/~kratt

Dédié à Xavier Viennot

Abstract. The M-triangle of a ranked locally finite poset P is the generating function ∑_{u,w∈P} μ(u, w) x^{rk u}y^{rk w}, where μ(., .) is the Möbius function of P. We compute the Mtriangle of Armstrong’s poset of m-divisible non-crossing partitions for the root systems of type E_{7} and E_{8}. For the other types except D_{n} this had been accomplished in the earlier paper “The F -triangle of the generalised cluster complex” [in: “Topics in Discrete Mathematics,” M. Klazar, J. Kratochvil, M. Loebl, J. Matoušek, R. Thomas and P. Valtr, eds., Springer– Verlag, Berlin, New York, 2006, pp. 93–126]. Altogether, this almost settles Armstrong’s F = M Conjecture, predicting a surprising relation between the M-triangle of the m-divisible partitions poset and the F -triangle (a certain refined face count) of the generalised cluster complex of Fomin and Reading, the only gap remaining in type D_{n}. Moreover, we prove a reciprocity result for this M-triangle, again with the possible exception of type D_{n}. Our results are based on the calculation of certain decomposition numbers for the reflection groups of types E_{7} and E_{8}, which carry in fact finer information than the M-triangle does. The decomposition numbers for the other exceptional reflection groups had been computed in the earlier paper. As an aside, we show that there is a closed form product formula for the type A_{n} decomposition numbers, leaving the problem of computing the type B_{n} and type D_{n} decomposition numbers open.

1. Introduction. The lattice of non-crossing partitions of Kreweras [18] is a now classical object of study in combinatorics with many fascinating properties (see [21]). In [12], Edelman generalised non-crossing partitions to m-divisible non-crossing partitions and showed that they, too, have many beautiful properties. Recently, Bessis [6] and Brady and Watt [8] gave a uniform definition of non-crossing partitions associated to root systems,

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

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

†Research partially supported by the Austrian Science Foundation FWF, grant S9607-N13, in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory,” and by the “Algebraic Combinatorics” Programme during Spring 2005 of the Institut Mittag–Leffler of the Royal Swedish Academy of Sciences.

which includes Kreweras non-crossing partitions as “type A_{n}” non-crossing partitions, as well as Reiner’s [20] “type B_{n}” non-crossing partitions. (As it turned out, Reiner did not have the “right” definition of “type D_{n}” non-crossing partitions). The question whether Edelman’s [12] m-divisible non-crossing partitions also allow for an extension to root systems was answered by Armstrong [2], who introduced m-divisible non-crossing partitions for all root systems uniformly. (He calls them also “generalised” non-crossing partitions for root systems.)

Extending an earlier conjecture of Chapoton [11] (which, in the meantime, has become a theorem due to Athanasiadis [3]), Armstrong predicted a relation between the “M-triangle” of his m-divisible non-crossing partitions poset and the “F -triangle” of the generalised cluster complex of Fomin and Reading [13]. (Roughly speaking, the M-triangle is a bivariate generating function involving the Möbius function, while the F -triangle is a refined face count. The reader is referred to Section 2 for the definition of the M-triangle, and to Section 8 for the definition of the F -triangle.) In the sequel, we shall refer to Armstrong’s conjecture as the “F = M Conjecture.”

In [17], the F -triangle of the generalised cluster complex was computed for all types, and the M-triangle of the m-divisible non-crossing partitions poset was computed for all types except for the types D_{n}, E_{7}, and E_{8}. Thus, the F = M Conjecture could be verified for all types except the afore-mentioned three. The purpose of this paper is to compute the M-triangle of the m-divisible non-crossing partitions poset for the exceptional types E_{7} and E_{8}. Thus, the F = M Conjecture remains open only for D_{n}. It should be noted, however, that a conjectural expression for the M-triangle of the m-divisible non-crossing partitions poset appears in [17, Sec. 11, Prop. D]. Moreover, since, in the case of type D_{n}, Section 11 of [17] contains a proof for m = 1 (independent from the one in [3]), the results from [17] together with the results of the present paper provide a case-by-case proof of the m = 1 case of the F = M Conjecture, that is, of Chapoton’s (ex-)conjecture.

In order to compute the M-triangle of the m-divisible partitions poset for E_{7} and E_{8}, we compute certain decomposition numbers in the corresponding reflection groups (see Section 3 for the definition). These decomposition numbers carry, in fact, finer information than the M-triangle. They are therefore of intrinsic interest. For the other reflection groups of exceptional type, they had been already computed in [17], but not for the types A_{n}, B_{n}, and D_{n}. In Section 10, we point out that, in fact, a result of Goulden and Jackson [15, Theorem 3.2] on the minimal factorization of a long cycle implies a closed form product formula for the type A_{n} decomposition numbers. We plan to address the problem of computing the type B_{n} and type D_{n} decomposition numbers in a future publication.

The M-triangle of generalised non-crossing partitions for the types E_{7} and E_{8} 3

Our paper is organised as follows. The next section contains the definition and basics of non-crossing partitions for root systems and the m-divisible non-crossing partitions. There, we define also the main object of this paper, the M-triangle of the m-divisible non-crossing partitions poset. Section 3 recalls the formula from [17] which expresses the M-triangle in terms of the afore-mentioned decomposition numbers and the characteristic polynomials of non-crossing partitions posets of lower rank. Section 4 explains our strategy of how to compute these decomposition numbers for the types E_{7} and E_{8}. (This strategy is actually applicable for any specific reflection group, except that the computational difficulties increase significantly with the rank of the reflection group.) The intermediate Section 5 recalls from [17] how these decomposition numbers can be used to compute the characteristic polynomial of the non-crossing partitions poset corresponding to the reflection group. The programme from Section 4 is then implemented in Section 6 to compute the M-triangle of the m-divisible non-crossing partitions poset of type E_{7} and in Section 7 to compute the M-triangle of the m-divisible non-crossing partitions poset of type E_{8}. The purpose of Section 8 is to briefly explain the F = M Conjecture, and why the results from Sections 6 and 7 together with results from [17] prove it for the types E_{7} and E_{8}. Section 9 presents a curious observation which results from our explicit expressions in this paper and in [17] for the M-triangle of the m-divisible non-crossing partitions poset: a reciprocity relation which sets the M-triangle with parameter m in relation with the Mtriangle with parameter −m. It would be interesting to find an intrinsic explanation of this phenomenon. We conclude the paper by addressing the type A_{n} decomposition numbers. Theorem 9 in Section 10 states the afore-mentioned result by Goulden and Jackson in the language of the present paper, and Theorem 10 gives the implied result on arbitrary type A_{n} decomposition numbers. An Appendix lists the decomposition numbers for the types A_{1}, A_{2}, A_{3}, A_{4}, A_{5}, A_{6}, A_{7}, D_{4}, D_{5}, D_{6}, D_{7}, E_{6}, which are needed in our calculations of Sections 6 and 7.

2. Generalised non-crossing partitions. In this section we recall the definition of Armstrong’s [2] m-divisible non-crossing partitions poset, and we define its M-triangle.

Let Φ be a finite root system of rank n. (We refer the reader to [16] for all root system terminology.) For an element α ∈ Φ, let t_{α} denote the 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 in fact a lattice (see [9] for a uniform proof), and moreover self-dual (this is obvious from the definition). Clearly, the minimal element in NC(Φ) is the identity element in W, which we denote by ε, and the maximal element in NC(Φ) is the chosen Coxeter element c. 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 [18] (see also [14]), and because also NC(B_{n}) and NC(D_{n}) can be realised as lattices of non-crossing partitions (see [4, 20]).

The poset of m-divisible non-crossing partitions has as a ground-set 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)}. (2.1)

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 several 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 [2, Theorem 3.4.4].)

The central object in the present paper is the “M-triangle” of NC^{m}(Φ), which is the polynomial defined by

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}(Φ). It is called “triangle” because the Möbius function μ(u, w) vanishes unless u ≤ w, and, thus, the only coefficients in the polynomial which may be non-zero are the coefficients of x^{k}y^{l} with 0 ≤ k ≤ l ≤ n.

An equivalent object is the dual M-triangle, which is defined by

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

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}(Φ))^{∗}. It is equivalent since, obviously, we have

(M_{Φ}^{m})^{∗}(x, y) = (xy)^{n}M_{Φ}^{m}(1/x, 1/y).  (2.2)

The dual M-triangle of NC^{m}(Φ) (and, thus, its M-triangle as well) was computed explicitly in [17] for all types, except for D_{n} (a conjectural expression appears, however, in [17, Sec. 11, Prop. D]), for E_{7}, and for E_{8}. In Sections 6 and 7 below, we fill this gap for E_{7} and E_{8}. Thus, it is only the case of D_{n} which remains open.

3. How to compute the M-triangle of the generalised non-crossing partitions for a specific root system. We follow the strategy outlined in [17, Sec. 12], which, however, has to be complemented by additional ideas. These additional ideas will be described in the next section.

Let us recall from [17] that the dual M-triangle (and, thus, the M-triangle as well) can be expressed in terms of certain decomposition numbers and characteristic polynomials of non-crossing partitions posets, which we define now. The decomposition number 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. (Here, the term “parabolic Coxeter element” means a Coxeter element in some parabolic subgroup. The reader must recall that it follows from [6, Lemma 1.4.3] that any element c_{i} is indeed a Coxeter element in a parabolic subgroup of W = W (Φ). By definition, the type of c_{i} is the type of this parabolic subgroup.) On the other hand, we denote by χ_{NC(Ψ)}^{∗}(y) the reciprocal polynomial of the characteristic polynomial of NC(Ψ), that is, using self-duality of NC(Ψ),

χ_{NC(Ψ)}^{∗}(y) = ∑_{u∈NC(Ψ)} μ(ˆ0_{NC(Ψ)}, u) y^{rk Ψ−rk u} = ∑_{u∈NC(Ψ)} μ(u, ˆ1_{NC(Ψ)}) y^{rk u},

where ˆ0_{NC(Ψ)} stands for the minimal element and ˆ1_{NC(Ψ)} stands for the maximal element in NC(Ψ). (The reader should recall from Section 2 that ˆ0_{NC(Ψ)} is the identity element in W (Ψ) and that ˆ1_{NC(Ψ)} is the chosen Coxeter element in W (Ψ).) Using this notation, a combination of Eqs. (12.3) and (12.4) from [17] reads as follows.

Proposition 1. For any finite root system Φ of rank n, we have

(M_{Φ}^{m})^{∗}(x, y) = ∑_{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}, (3.1)

where the inner sum is over all possible d-tuples (T_{1}, T_{2}, …, T_{d}) of types (not necessarily irreducible types). In (3.1), and in the sequel, the notation NC(T) means NC(Ψ), where Ψ is a root system of type T, and rk T denotes the rank of Ψ.

So, what we have to do to apply Formula (3.1) to compute the (dual) M-triangle is, first, to determine all the decomposition numbers N_{Φ}(T_{1}, T_{2}, …, T_{d}), and, taking advantage of the multiplicativity

χ_{NC(Ψ_{1}∗Ψ_{2})}^{∗}(y) = χ_{NC(Ψ_{1})×NC(Ψ_{2})}^{∗}(y) = χ_{NC(Ψ_{1})}^{∗}(y) · χ_{NC(Ψ_{2})}^{∗}(y)

of the characteristic polynomial (here, Ψ_{1} ∗ Ψ_{2} denotes the direct sum of the root systems Ψ_{1} and Ψ_{2}), second, one needs a list of the characteristic polynomials χ_{NC(Ψ)}^{∗}(y) for all irreducible root systems Ψ. We describe in the following section how we compute the decomposition numbers, and in the subsequent section how to use this knowledge to compute as well the characteristic polynomials that we need.

4. How to compute the decomposition numbers. Our strategy to compute the decomposition numbers N_{Φ}(T_{1}, T_{2}, …, T_{d}) for a fixed root system Φ is to find as many linear relations between them as possible, and eventually solve this system of linear equations. Indeed, the decomposition numbers have many relations between themselves, some of which have already been stated and used in [17]. We recall these here in Proposition 2 below. Equation (4.1) says that the order of the types T_{1}, T_{2}, …, T_{d} is not relevant. Equation (4.2) reduces the computation to the computation of the decomposition numbers N_{Φ}(T_{1}, T_{2}, …, T_{d}) with “full” rank, that is, with rk T_{1} + rk T_{2} + ⋯ + rk T_{d} = rk Φ.

In Equation (4.3) we add another family of relations. They involve the decomposition numbers N_{T} (T′_{1}, T′_{2}, …, T′_{e}) of “smaller” root systems than Φ, that is, decomposition numbers with rk T < rk Φ. (Similarly to Proposition 1, by abuse of notation, N_{T} (T′_{1}, T′_{2}, …, T′_{e}) stands for the decomposition number N_{Ψ}(T′_{1}, T′_{2}, …, T′_{e}), where Ψ is a root system of type T.) If we had already computed these beforehand, then the relations (4.3) are linear relations between full rank decomposition numbers N_{Φ}(T_{1}, T_{2}, …, T_{d}). Proposition 7 allows one to reduce these beforehand computations to irreducible root systems of smaller rank.

A further set of linear relations comes from an identity featuring the zeta polynomials of (ordinary and generalized) non-crossing partitions posets given in Proposition 3. Indeed, as we explain in Remark (2) after the proof of Proposition 3, all the zeta polynomials appearing in (4.7) are explicitly known, so that, by comparing coefficients of m^{i}z^{j} on both sides of (4.7), we obtain a set of linear relations between the decomposition numbers N_{Φ}(T_{1}, T_{2}, …, T_{d}).

While the number of equations which result from Propositions 2 and 3 exceeds the number of variables (that is, the number of decomposition numbers of full rank) by far, it turns out that they are not sufficient to determine them uniquely. To remedy this somewhat, we add Proposition 4 which provides the values for three special decomposition numbers, and we add Proposition 6 which, as we illustrate in the Remark after the statement of the proposition, allows one to compute all the (full rank) decomposition numbers N_{Φ}(T, A_{1}) with rk T = rk Φ − 1.

As we shall see in Sections 6 and 7, the system of linear equations resulting from Propositions 2, 3, 4 and 6 still does not yield a unique solution for the decomposition numbers for Φ = E_{7} and Φ = E_{8}. However, they allow one to come very close, so that, upon adding some arithmetic considerations and, in type E_{8}, a Maple calculation using Stembridge’s coxeter package [24], one eventually succeeds in finding all the decomposition numbers.

Proposition 2. Let Φ be a finite root system. Then, for any permutation σ of {1, 2, …, d}, we have

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

Furthermore,

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

where the sum is over all types T of rank rk Φ − rk T_{1} − rk T_{2} − ⋯ − rk T_{d}.

If rk T_{1} + rk T_{2} + ⋯ + rk T_{d} + rk T′_{1} + rk T′_{2} + ⋯ + rk T′_{e} = rk Φ, then

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

where the sum is over all types T of rank rk T′_{1} + rk T′_{2} + ⋯ + rk T′_{e}.

Finally, if one of T_{1}, T_{2}, …, T_{d} is not the type of a sub-diagram of the Dynkin diagram of Φ, then N_{Φ}(T_{1}, T_{2}, …, T_{d}) = 0.

Examples. An example of a relation of the form (4.2) is (7.11). To be precise, Equation (7.11) is the special case of (4.2) where Φ = E_{8}, d = 1, and T_{1} = D_{4}.

An example of a relation of the form (4.3) is (we make also use of (4.1))

N_{E_{7}}(A_{1} ∗ A_{3}, A_{1}^{2}, A_{1}) = N_{A_{1}^{5}}(A_{1} ∗ A_{3}, A_{1})N_{E_{7}}(A_{1}^{5}, A_{1}^{2})
+ N_{A_{1}^{3}∗A_{2}}(A_{1} ∗ A_{3}, A_{1})N_{E_{7}}(A_{1}^{3} ∗ A_{2}, A_{1}^{2})
+ N_{A_{1}∗A_{2}^{2}}(A_{1} ∗ A_{3}, A_{1})N_{E_{7}}(A_{1} ∗ A_{2}^{2}, A_{1}^{2})
+ N_{A_{1}^{2}∗A_{3}}(A_{1} ∗ A_{3}, A_{1})N_{E_{7}}(A_{1}^{2} ∗ A_{3}, A_{1}^{2})
+ N_{A_{2}∗A_{3}}(A_{1} ∗ A_{3}, A_{1})N_{E_{7}}(A_{2} ∗ A_{3}, A_{1}^{2})
+ N_{A_{1}∗A_{4}}(A_{1} ∗ A_{3}, A_{1})N_{E_{7}}(A_{1} ∗ A_{4}, A_{1}^{2})
+ N_{A_{1}∗D_{4}}(A_{1} ∗ A_{3}, A_{1})N_{E_{7}}(A_{1} ∗ D_{4}, A_{1}^{2})
+ N_{A_{5}}(A_{1} ∗ A_{3}, A_{1})N_{E_{7}}(A_{5}, A_{1}^{2})
+ N_{D_{5}}(A_{1} ∗ A_{3}, A_{1})N_{E_{7}}(D_{5}, A_{1}^{2})

= 2N_{E_{7}}(A_{1}^{2} ∗ A_{3}, A_{1}^{2}) + 3N_{E_{7}}(A_{2} ∗ A_{3}, A_{1}^{2}) + 5N_{E_{7}}(A_{1} ∗ A_{4}, A_{1}^{2})

+ 9N_{E_{7}}(A_{1} ∗ D_{4}, A_{1}^{2}) + 6N_{E_{7}}(A_{5}, A_{1}^{2}) + 4N_{E_{7}}(D_{5}, A_{1}^{2}).

To be precise, the above equation is the special case of (4.3) where Φ = E_{7}, d = 1, e = 2, T_{1} = A_{1}^{2}, T′_{1} = A_{1} ∗ A_{3} and T′_{2} = A_{1}. The decomposition numbers N_{Ψ}(…) with Ψ = A_{1}^{5}, A_{1}^{3} ∗ A_{2}, A_{1} ∗ A_{2}^{2}, A_{1}^{2} ∗ A_{3}, A_{2} ∗ A_{3}, A_{1} ∗ A_{4}, A_{1} ∗ D_{4}, A_{5}, D_{5} which are needed here are computed by using Proposition 7 and the decomposition numbers for the irreducible root systems A_{1}, A_{2}, A_{3}, A_{4}, A_{5}, D_{4}, D_{5} tabulated in the Appendix.

Proof of Proposition 2. Equation (4.1) is [17, Eq. (45)], while Equation (4.2) is [17, Eq. (46)].

In order to see (4.3), we recall that, by definition and by taking into account the rank assumption, the number N_{Φ}(T_{1}, T_{2}, …, T_{d}, T′_{1}, T′_{2}, …, T′_{e}) is the number of decompositions

c = c_{1}c_{2} ⋯ c_{d}c′_{1}c′_{2} ⋯ c′_{e},  (4.4)

with c_{i} of type T_{i} and c′_{i} of type T′_{i} for all i. The decompositions (4.4) can also be determined by first decomposing

c = c_{1}c_{2} ⋯ c_{d}c′,  (4.5)

with c_{i} of type T_{i} for all i, and subsequently

c′ = c′_{1}c′_{2} ⋯ c′_{e},  (4.6)

with c′_{i} of type T′_{i} for all i. If we fix the type of c′, T say, then the number of decompositions (4.5) is N_{Φ}(T_{1}, T_{2}, …, T_{d}, T). For determining the number of decompositions (4.6), we recall from [6, Cor. 1.6.2 and Def. 1.6.3] that c′ is a Coxeter element in a parabolic subgroup, denoted by W_{c′} in [6], and that the absolute order ≤_{T} on W = W (Φ) restricted to W_{c′} is identical with absolute order on W_{c′}. In other words, the decompositions (4.6) with c′_{i} ∈ W are identical with the decompositions (4.6) with c′_{i} ∈ W_{c′}. Hence, the number of decompositions (4.6) is the number N_{T} (T′_{1}, T′_{2}, …, T′_{e}). Finally, in order to get the total number N_{Φ}(T_{1}, T_{2}, …, T_{d}), we must sum the products

N_{T} (T′_{1}, T′_{2}, …, T′_{e})N_{Φ}(T_{1}, T_{2}, …, T_{d}, T)

over all possible types T, thus arriving at Equation (4.3).

The last assertion follows again from the fact [6, Lemma 1.4.3] that any element which is less than or equal to a Coxeter element c of W is the Coxeter element in some parabolic subgroup of W. Hence, its type must by a sub-type of Φ, the type of W. □

More equations come from the following proposition, featuring the zeta polynomial of the non-crossing partitions posets (ordinary and generalized). Recall that, given a poset P, its zeta polynomial Z_{P} (z) is the number of multichains x_{1} ≤ x_{2} ≤ ⋯ ≤ x_{z−1} in P. (It can be shown that this is indeed a polynomial in z. The reader should consult [23, Sec. 3.11] for more information on this topic.)

Proposition 3. For any finite root system Φ of rank n, we have

Z_{NC^{m}(Φ)}(z) = ∑_{d=0}^{n} ∑_{(T_{1},...,T_{d})} N_{Φ}(T_{1}, T_{2}, …, T_{d})

· Z_{NC(T_{1})}(z − 1)Z_{NC(T_{2})}(z − 1) ⋯ Z_{NC(T_{d})}(z − 1)\binom{m}{d}, (4.7)

where the inner sum is over all possible d-tuples (T_{1}, T_{2}, …, T_{d}) of types, and where N_{Φ}(T_{1}, T_{2}, …, T_{d}) is as before.

Proof. Let ˆ1_{NC^{m}(Φ)} denote the maximal element (c; ε, …, ε) in NC^{m}(Φ). If, given a multichain x_{1} ≤ x_{2} ≤ ⋯ ≤ x_{z−1} in NC^{m}(Φ), we remove the minimal element w = x_{1}, then a multichain remains which is by 1 shorter. Hence, by summing over all possible w’s, we obtain

Z_{NC^{m}(Φ)}(z) = ∑_{w∈NC^{m}(Φ)} Z_{[w,ˆ1_{NC^{m}(Φ)}]}(z − 1).  (4.8)

Now, by definition of NC^{m}(Φ), w is of 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. Moreover, as we already recalled in Section 3, it follows from [6, Lemma 1.4.3] that any element w_{j} is a Coxeter element in a parabolic subgroup of W = W (Φ) (or, in the language used earlier, a “parabolic Coxeter element”). On the other hand, we have

[w, ˆ1_{NC^{m}(Φ)}] ≅ [ε, w_{1}] × [ε, w_{2}] × ⋯ × [ε, w_{m}],  (4.9)

where each interval [ε, w_{j}] is an interval in NC(Φ). In fact, some of the w_{j}’s may be equal to the identity ε. If we denote by w_{i_{1}}, w_{i_{2}}, …, w_{i_{d}} those among the w_{j}’s which are not equal to ε, then (4.9) reduces to

[w, ˆ1_{NC^{m}(Φ)}] ≅ [ε, w_{i_{1}}] × [ε, w_{i_{2}}] × ⋯ × [ε, w_{i_{d}}].

More precisely, since each w_{i_{j}} is a parabolic Coxeter element, each interval [ε, w_{i_{j}}] is isomorphic to some non-crossing partition lattice NC(Ψ), where Ψ is the root system of this parabolic subgroup. The zeta polynomial being multiplicative, this implies

Z_{[w,ˆ1_{NC^{m}(Φ)}]}(z − 1) = Z_{[ε,w_{i_{1}} ]}(z − 1)Z_{[ε,w_{i_{2}} ]}(z − 1) ⋯ Z_{[ε,w_{i_{d}}]}(z − 1).

If we take into account that the number of possibilities to choose the indices {i_{1} < i_{2} < ⋯ < i_{d}\} out of \{1, 2, …, m\} is equal to \binom{m}{d} and combine this with the previous observations, then (4.8) turns into (4.7). □

Remarks. (1) It is striking to note the similarities between (3.1) and (4.7). It would be interesting to find an intrinsic explanation. Even in lack of such an explanation, the relations (3.1) and (4.7) underline the significance of the decomposition numbers N_{Φ}(T_{1}, T_{2}, …, T_{d}).

(2) The zeta polynomial of the non-crossing partition lattice NC(Φ), where Φ is a root system of rank n, has the elegant formula (see [11, Prop. 9])

Z_{NC(Φ)}(z) = ∏_{i=1}^{n} \frac{(z − 1)h + d_{i}}{d_{i}} ,  (4.10)

where h is the Coxeter number and the d_{i}’s are the degrees of W = W (Φ). (The reader should be warned that the convention chosen in [11] for the zeta polynomial is different from the one here.) This uniform formula was originally conjectured by Chapoton on the basis of the already known formulae in types A_{n}, B_{n} and D_{n}, and of calculations he did for some exceptional groups. The formula was finally confirmed for the large exceptional groups by Mathematica and MATLAB calculations done by Reiner.

On the basis of (4.10), Armstrong could also determine the zeta polynomial for all mdivisible non-crossing partitions posets. Again, there is a uniform formula, namely (see [2, Theorem 3.5.2]; we warn the reader that also in [2] this different convention for the zeta polynomial is used)

Z_{NC^{m}(Φ)}(z) = ∏_{i=1} \frac{(z − 1)mh + d_{i}}{d_{i}} .  (4.11)

If we use formulae (4.10) and (4.11) in (4.7), then, by comparing coefficients of m^{i}z^{j} on both sides of (4.7), we obtain (n + 1)^{2} linear equations for the decomposition numbers N_{Φ}(T_{1}, T_{2}, …, T_{d}). Although some of them turn out to be trivial (1 = 1 or 0 = 0), this is nevertheless a considerable number of linear relations.

Proposition 4. (1) For any finite root system Φ of type T we have N_{Φ}(T) = 1.

(2) The decomposition number N_{Φ}(A_{1}) is equal to the total number of reflections in W (Φ) or, equivalently, to the number of positive roots in Φ. These numbers are tabulated in [16, Table 2 on p. 80].

(3) The decomposition number N_{Φ}(A_{1}, A_{1}, …, A_{1}) (with n = rk Φ occurrences of A_{1}) is equal to n! h^{n}/|W (Φ)|, where h is the Coxeter number of W (Φ).

Proof. The claim (1) is trivial.

To see (2), we have to show that any reflection t is less than or equal to the Coxeter element c in absolute order. Indeed, we have c = t(tc), with ℓ_{T} (t) = 1 and ℓ_{T} (tc) = ℓ_{T} (c)±1, by general properties of the absolute length. Now, the maximal possible absolute length of an element in W (Φ) is rk Φ = ℓ_{T} (c) (cf. [6, Lemma 1.2.1(ii)]). Hence, we have ℓ_{T} (tc) = ℓ_{T} (c) − 1, and, thus, t ≤_{T} c.

Finally we prove claim (3). The number of decompositions c = t_{1}t_{2} ⋯ t_{n} is equal to the number of maximal chains ε < w_{1} < w_{2} < ⋯ < w_{n−1} < c in NC(Φ), because of the obvious bijection between decompositions and maximal chains defined by the identification w_{i} = t_{1}t_{2} … t_{i}, i = 1, 2, …, n − 1. It is a general fact (see [23, Prop. 3.11.1]) that the number of maximal chains in a poset is equal to the leading coefficient of its zeta polynomial multiplied by the factorial of the rank of the poset. The claim then follows from the explicit formula (4.10) for the zeta polynomial of NC(Φ). □

Our next goal is to determine the decomposition numbers N_{Φ}(T, A_{1}) with rk T = rk Φ− 1. Proposition 6 will provide the means to do that. For the proof of the proposition, we need an auxiliary lemma, Lemma 5 below. It is an extended version of Lemma 1.3.4 from [6]. The extension makes the theoretical assertion of [6, Lemma 1.3.4] concrete for each type. Actually, in the present paper, we shall need this “concretisation” only for the types D_{6} and E_{7}. However, as it may be useful in other situations, we work it out here for all types.

Lemma 5. Let Φ be an irreducible root systems of rank n. Furthermore, let

S = {s_{1}, s_{2}, …, s_{n}} = {s_{1}, …, s_{r}} ∪ {s_{r+1}, …, s_{n}}

be a choice of simple reflections with the property that s_{i} and s_{j} commute for all i, j with 1 ≤ i, j ≤ r, and for all i, j with r + 1 ≤ i, j ≤ n, r being chosen appropriately (cf. [16, Sec. 3.17]), and let c = s_{1}s_{2} ⋯ s_{n} be the corresponding Coxeter element. Then, for any reflection t, the cardinality of the orbit Ω(t) = {c^{k}tc^{−k} : k ∈ ℤ} of t under conjugation by c is

(1) h if |Ω(t) ∩ S| = 2,
(2) h/2 if |Ω(t) ∩ S| = 1,

where h is the Coxeter number of W = W (Φ) (cf. [16, Table 2 on p. 80]), and there are no other possibilities. Specifically, the cardinality of Ω(t) is

h  if Φ = A_{n} except if n is odd and tc is of type A_{(n−1)/2}^{2},
if Φ = D_{n}, n is odd, and tc is of type A_{n−1},
if Φ = E_{6} and tc is of type D_{5} or A_{1} ∗ A_{4},
h/2 otherwise.

Proof. The assertion on the cardinality of Ω(t) as it depends on the cardinality of the intersection Ω(t) ∩ S is [6, Lemma 1.3.4]. The concrete cardinality assertion for the type A_{n} can be worked out by using the well-known combinatorial realisation of W (A_{n}) as the symmetric group on n + 1 elements, while for the types B_{n} and D_{n} this can be worked out by using the combinatorial realisations of the corresponding reflection groups as subgroups of the symmetric group on 2n elements (see e.g. [7, Sections 8.1 and 8.2].) Since this does not contain any surprises, we leave the details to the reader.

• • • • • •_{1}  ^{2}_{3}  _{4}  _{5}  _{6}

Dynkin diagram of E_{6}

Figure 1

For the type E_{6} we argue as follows. Let s_{1}, s_{2}, s_{3}, s_{4}, s_{5}, s_{6} denote the simple reflections of E_{6}, with commutation relations coded by the Dynkin diagram of E_{6} as given by Figure 1. (The labelling of the nodes is the one which Stembridge’s coxeter package [24] chooses.) To prepare the following arguments, we note that if T is the type of the sub-diagram of the Dynkin diagram of E_{6} obtained by deleting the node corresponding to the simple reflection s_{i}, say, then, because of c = s_{1}s_{2}s_{3}s_{4}s_{5}s_{6} = t(s_{1} ⋯ s_{i−1}s_{i+1} ⋯ s_{6}) with t = (s_{1} ⋯ s_{i−1})s_{i}(s_{1} ⋯ s_{i−1})^{−1}, there is (at least) one orbit {c^{k}tc^{−k} : k ∈ ℤ} such that the type of tc is T. The types which occur as types of sub-diagrams of the Dynkin diagram of E_{6} obtained by deleting one node from it are D_{5}, A_{1} ∗ A_{4}, A_{5} and A_{1} ∗ A_{2}^{2}.

Maple computations using Stembridge’s package yield the following facts. There are four orbits of reflections under conjugation by c, two of size 12 = h, and two of size 6 = h/2. Hence, for each of the types D_{5}, A_{1} ∗ A_{4}, A_{5}, and A_{1} ∗ A_{2}^{2}, there corresponds exactly one orbit in the sense described above, that is, if T is one of these four types then there is exactly one orbit such that tc is of type T for each reflection t in the orbit.

The orbit of s_{1} has 12 elements, and it contains also s_{3}, s_{4}, s_{5}, s_{6}. From the fact that it contains s_{1}, we can conclude that tc is of type D_{5} for all reflections t in this orbit. The second orbit with 12 elements is the one of the reflection s_{2}s_{3}s_{4}s_{2}s_{3}. Since the order of s_{2}s_{3}s_{4}s_{2}s_{3}c is 10, we must necessarily have that its type is A_{1} ∗ A_{4}. (The other remaining sub-diagrams of the Dynkin diagram of E_{6} have types A_{5} and A_{1} ∗A_{2}^{2}. Coxeter elements of these types have the order 6.) The orbits with 6 elements are the ones of s_{2} and s_{4}s_{5}s_{6}s_{5}s_{4}, respectively. If t denotes any reflection in one of these two orbits, then the type of tc is necessarily either A_{5} or A_{1} ∗A_{2}^{2}, one type applying for all reflections in one orbit, the other type applying for all reflections in the other orbit. For our purpose it is not important which type is associated to which orbit, since both possibilities are in agreement with our claim.

In the case that Φ = I_{2}(a), there is just one orbit. For all other exceptional types, one can again do calculations using Stembridge’s coxeter package. The result is that in type H_{3} one obtains 3 orbits of 5 elements each, in type H_{4} one obtains 4 orbits of 15 elements each, in type F_{4} one obtains 4 orbits of 6 elements each, in type E_{7} one obtains 7 orbits of 9 elements each, and in type E_{8} one obtains 8 orbits of 15 elements each. All this is in accordance with our claim. □

Proposition 6. Let Φ be a finite irreducible root system, and let T be a type with rk T = rk Φ − 1. Then, if T is the type of a sub-diagram of the Dynkin diagram of Φ obtained by deleting one node from it, we have

\frac{N_{Φ}(T, A_{1})}{N(T ⊆ Φ)} = \frac{h}{2},  (4.12)

where N(T ⊆ Φ) denotes the number of times T arises as type of a sub-diagram of the Dynkin diagram of Φ, and where h is the Coxeter number of W = W (Φ). Otherwise, we have N_{Φ}(T, A_{1}) = 0.

Proof. We start with the following observation. By definition, the number N_{Φ}(T, A_{1}) counts the number of product decompositions c = wt, where w is a parabolic Coxeter element of type T and t is a reflection. Given w and t, we obtain another product decomposition by conjugation,

c = ccc^{−1} = cwtc^{−1} = (cwc^{−1})(ctc^{−1}),

where ctc^{−1} is also a reflection, and where the type of cwc^{−1} is still T. Hence, all the elements of the complete orbit {(c^{k}wc^{−k}, c^{k}tc^{−k}) : k ∈ ℤ} of (w, t) under conjugation by c provide product decompositions of c in a parabolic Coxeter element of type T and a reflection. Since the reflection t′ already determines its “companion” w′ in the decomposition c = w′t′ uniquely via w′ = ct′, we may as well concentrate on the orbit {c^{k}tc^{−k} : k ∈ ℤ} of t under conjugation by c.

In what follows, we assume the setup of Lemma 5, that is, we assume that

S = {s_{1}, s_{2}, …, s_{n}} = {s_{1}, …, s_{r}} ∪ {s_{r+1}, …, s_{n}}

is a choice of simple reflections with the property that s_{i} and s_{j} commute for all i, j with 1 ≤ i, j ≤ r, and for all i, j with r + 1 ≤ i, j ≤ n, r being chosen appropriately, and we let c = s_{1}s_{2} ⋯ s_{n} be the corresponding Coxeter element.

Now, let T be the type of the sub-diagram of the Dynkin diagram of Φ obtained by deleting the node corresponding to s_{i} from it. If 1 ≤ i ≤ r, we have

c = (s_{1} ⋯ s_{i−1}s_{i+1} ⋯ s_{r}(s_{i}s_{r+1}s_{i}) ⋯ (s_{i}s_{n}s_{i})) · s_{i}
= ((s_{i}s_{1}s_{i}) ⋯ (s_{i}s_{i−1}s_{i})(s_{i}s_{i+1}s_{i}) ⋯ (s_{i}s_{n}s_{i})) · s_{i},  (4.13)

and, if r + 1 ≤ i ≤ n, we have

c = (s_{1} ⋯ s_{i−1}s_{i+1} ⋯ s_{n}) · s_{i}.

In both cases, the type of cs_{i} is T, in the former case since the system

{(s_{i}s_{1}s_{i}), …, (s_{i}s_{i−1}s_{i})(s_{i}s_{i+1}s_{i}), …, (s_{i}s_{n}s_{i})}  (4.14)

is conjugate to {s_{1}, …, s_{i−1}, s_{i+1}, …, s_{n}}, the latter being a system of simple reflections of type T.

Next, let Ω_{1}, Ω_{2}, …, Ω_{a} and Ω̄_{1}, Ω̄_{2}, …, Ω̄_{b} be the orbits of reflections t under conjugation by c such that ct is of type T,^{1} the former those of cardinality h, the latter those of cardinality h/2. Lemma 5 says that there can be no others, while the argument involving (4.13) and (4.14) implies that there is at least one such orbit, namely the orbit of s_{i}. The last statement implies in particular that at least one of a and b is non-zero. We have

N(T, A_{1}) = ah + b\frac{h}{2}.  (4.15)

On the other hand, from Lemma 5 (1),(2) and the argument involving (4.13) and (4.14) we infer that

N(T ⊆ Φ) = 2a + b.  (4.16)

Dividing right-hand and left-hand sides, respectively, of (4.15) and (4.16) we obtain (4.12).

If T is a type which is not the type of a sub-diagram of the Dynkin diagram of Φ and N(T, A_{1}) ≠ 0, then we obtain a contradiction: let t be a reflection such that c = wt, where w is of type T. By Lemma 5, the orbit Ω(t) of t under conjugation by c contains a simple reflection, s_{i} say. Now the argument involving (4.13) and (4.14) yields that T is the type of a sub-diagram of the Dynkin diagram of Φ, which is absurd. □

The final proposition in this section reduces the computation of the decomposition numbers N_{Φ}(T_{1}, T_{2}, …, T_{d}) to irreducible root systems Φ. On the right-hand side of (4.18) below, we use an extended definition of decomposition numbers, where we allow some of the types T_{i} in the argument to be empty, which we denote by T_{i} = ∅: we set N_{Φ}(∅, T_{2}, …, T_{d}) = N_{Φ}(T_{2}, …, T_{d}), with analogous conventions if one or more of the other T_{i}’s should be empty.

Proposition 7. If

rk Φ_{1} + rk Φ_{2} = rk T_{1} + rk T_{2} + ⋯ + rk T_{d},  (4.17)

then

N_{Φ_{1}∗Φ_{2}}(T_{1}, T_{2}, …, T_{d}) = ∑_{T′_{1}∗T′′_{1}=T_{1},...,T′_{d}∗T′′_{d}=T_{d}} N_{Φ_{1}}(T′_{1}, T′_{2}, …, T′_{d}) · N_{Φ_{2}}(T′′_{1}, T′′_{2}, …, T′′_{d}),

(4.18)

where in the sum on the right-hand side any of T′_{1}, T′_{2}, …, T′_{d}, T′′_{1}, T′′_{2}, …, T′′_{d} could also be empty.

Remark. The reader should note that, in order to have a non-vanishing summand in the sum on the right-hand side of (4.18), we must necessarily have rk Φ_{1} = rk T′_{1} + rk T′_{2} + ⋯ + rk T′_{d} and rk Φ_{2} = rk T′′_{1} + rk T′′_{2} + ⋯ + rk T′′_{d}, because otherwise one of N_{Φ_{1}}(T′_{1}, T′_{2}, …, T′_{d}) or N_{Φ_{2}}(T′′_{1}, T′′_{2}, …, T′′_{d}) vanishes.

1A case-by-case analysis shows that there can be at most 2 such orbits, and 2 orbits only if Φ is of type D_{n}, n is even, and T = A_{n−1}. However, this is of no importance here.

Proof of Proposition 7. By definition of the decomposition numbers and by (4.17), the number N_{Φ_{1}∗Φ_{2}}(T_{1}, T_{2}, …, T_{d}) is equal to the number of products

c_{1}c_{2} ⋯ c_{d} = c,  (4.19)

where c denotes the fixed Coxeter element of type Φ_{1} ∗ Φ_{2}, such that ℓ_{T} (c_{1}) + ℓ_{T} (c_{2}) + ⋯ + ℓ_{T} (c_{d}) = ℓ_{T} (c), and such that the type of c_{i} as a parabolic Coxeter element is T_{i}, i = 1, 2, …, d. Each of c, c_{1}, c_{2}, …, c_{d} decomposes uniquely into a product of an element of W (Φ_{1}) and an element of W (Φ_{2}), say c = c′c′′, c_{1} = c′_{1}c′′_{1}, c_{2} = c′_{2}c′′_{2}, …, c_{d} = c′_{d}c′′_{d} where c′, c′_{1}, c′_{2}, …, c′_{d} ∈ W (Φ_{1}) and c′′, c′′_{1}, c′′_{2}, …, c′′_{d} ∈ W (Φ_{2}). Since elements of W (Φ_{1}) commute with elements of W (Φ_{2}) in W (Φ_{1} ∗ Φ_{2}) = W (Φ_{1}) × W (Φ_{2}), the relation (4.19) is equivalent to the two relations

c′_{1}c′_{2} ⋯ c′_{d} = c′,  (4.20a)
c′′_{1}c′′_{2} ⋯ c′′_{d} = c′′.  (4.20b)

Hence, we may compute N_{Φ_{1}∗Φ_{2}}(T_{1}, T_{2}, …, T_{d}) also by first determining the number of all possible products (4.20a) such that the type of c′_{i} is T′_{i} (where we cover the case that c′_{i} is the identity element in W (Φ_{1}) by declaring that in that case T′_{i} = ∅) and the number of all possible products (4.20b) such that the type of c′′_{i} is T′′_{i} (with the same convention concerning identity elements), taking their product, and summing the results over all possible T′_{1}, …, T′_{d}, T′′_{1}, …, T′′_{d} with T′_{1} ∗ T′′_{1} = T_{1}, …, T′_{d} ∗ T′′_{d} = T_{d}. This leads exactly to the right-hand side of (4.18). □

5. How to compute the characteristic polynomials. Aside from the decomposition numbers, the second ingredient which we need for applying (3.1) to compute the (dual) M-triangle of the m-divisible partitions posets NC^{m}(Φ) is a list of the characteristic polynomials χ_{NC(Ψ)}^{∗}(y) for all irreducible root systems Ψ of rank at most the rank of Φ. (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}},  (5.1)

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 (5.1) is μ_{NC(Ψ)}(ˆ0_{NC(Ψ)}, ˆ1_{NC(Ψ)}). However, the latter can be computed by setting y = 1 in (5.1) 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 (4.10) for the zeta polynomial of the non-crossing partition lattices, in which one specializes the variable to −1, cf. [23, Sec. 3.11].)

Below we list the values of the characteristic polynomials of the irreducible root systems that we need in Sections 6 and 7 (and also for the computations which are behind the numbers in the Appendix).

χ_{A_{1}}^{∗}(y) = y − 1,
χ_{A_{2}}^{∗}(y) = y^{2} − 3y + 2,
χ_{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,
χ_{A_{6}}^{∗}(y) = y^{6} − 21y^{5} + 140y^{4} − 420y^{3} + 630y^{2} − 462y + 132,
χ_{A_{7}}^{∗}(y) = y^{7} − 28y^{6} + 252y^{5} − 1050y^{4} + 2310y^{3} − 2772y^{2} + 1716y − 429,
χ_{D_{4}}^{∗}(y) = y^{4} − 12y^{3} + 39y^{2} − 48y + 20,
χ_{D_{5}}^{∗}(y) = y^{5} − 20y^{4} + 106y^{3} − 230y^{2} + 220y − 77,
χ_{D_{6}}^{∗}(y) = y^{6} − 30y^{5} + 235y^{4} − 780y^{3} + 1260y^{2} − 980y + 294,
χ_{D_{7}}^{∗}(y) = y^{7} − 42y^{6} + 456y^{5} − 2135y^{4} + 5110y^{3} − 6552y^{2} + 4284y − 1122,
χ_{E_{6}}^{∗}(y) = y^{6} − 36y^{5} + 300y^{4} − 1035y^{3} + 1720y^{2} − 1368y + 418,
χ_{E_{7}}^{∗}(y) = y^{7} − 63y^{6} + 777y^{5} − 3927y^{4} + 9933y^{3} − 13299y^{2} + 9009y − 2431,
χ_{E_{8}}^{∗}(y) = y^{8} − 120y^{7} + 2135y^{6} − 15120y^{5}
+ 54327y^{4} − 108360y^{3} + 121555y^{2} − 71760y + 17342. (5.2)

6. The M-triangle of generalised non-crossing partitions of type E_{7}. We now implement the programme outlined in Sections 4 and 5 to compute the decomposition numbers for E_{7} and, thus, via (3.1) and (5.2), the M-triangle of the m-divisible noncrossing partitions of type E_{7}.

To begin with, we have to compute the decomposition numbers for types of smaller ranks, that is, of ranks ≤ 6. The decomposition numbers for the irreducible types of rank ≤ 6 that we need, for A_{1}, A_{2}, A_{3}, A_{4}, A_{5}, A_{6}, D_{4}, D_{5}, D_{6}, and E_{6}, are given in the Appendix. Those for the reducible types of rank ≤ 6 then can be computed by using Proposition 7.^{2} Then we use (4.1) and (4.2) to express all the decomposition numbers in terms of full rank decomposition numbers N_{Φ}(T_{1}, T_{2}, …, T_{d}) (that is, those with rk Φ = rk T_{1} + rk T_{2} + ⋯ + rk T_{d}), in which the types T_{i} are ordered (for example, according to lexicographic order). Subsequently we produce the equations which one obtains from (4.3) (using the earlier computed decomposition numbers of smaller rank) and from comparing coefficients of m^{i}z^{j}, i, j ∈ {0, 1, …, 7}, on both sides of (4.7). Finally, we use Proposition 4 to determine N_{E_{7}}(E_{7}), N_{E_{7}}(A_{1}) and N_{E_{7}}(A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}), Proposition 6 to compute the numbers N_{E_{7}}(T, A_{1}) with rk T = 6, and we use the last assertion in Proposition 2 for the type A_{1}^{5} (which does not occur as the type of a sub-diagram of the Dynkin diagram of E_{7}). To wit, the latter leads to the following special values of decomposition numbers:

2Although theoretically totally sound, this is not the most convenient way to do it: the actual way we computed these was to take the setup for an irreducible root system of the same rank following the programme outlined in Section 4, to change the values of the special decomposition numbers given by Propositions 4 and 6, and to solve the new system of linear equations.

N_{E_{7}}(E_{7}) = 1,
N_{E_{7}}(A_{1}) = 63,
N_{E_{7}}(A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 1062882,

\begin{matrix}N_{E_{7}}(E_{6}, A_{1}) = N_{E_{7}}(D_{6}, A_{1}) = N_{E_{7}}(A_{6}, A_{1}) = N_{E_{7}}(A_{1} ∗ A_{5}, A_{1}) \\ = N_{E_{7}}(A_{1} ∗ D_{5}, A_{1}) = N_{E_{7}}(A_{2} ∗ A_{4}, A_{1}) = N_{E_{7}}(A_{1} ∗ A_{2} ∗ A_{3}, A_{1}) = 9, \end{matrix}

N_{E_{7}}(A_{2} ∗ D_{4}, A_{1}) = N_{E_{7}}(A_{3}^{2}, A_{1}) = N_{E_{7}}(A_{1}^{2} ∗ D_{4}, A_{1}) = N_{E_{7}}(A_{1}^{2} ∗ A_{4}, A_{1}) = N_{E_{7}}(A_{1}^{3} ∗ A_{3}, A_{1}) = N_{E_{7}}(A_{2}^{3}, A_{1}) = N_{E_{7}}(A_{1}^{2} ∗ A_{2}^{2}, A_{1}) = N_{E_{7}}(A_{1}^{4} ∗ A_{2}, A_{1})

= N_{E_{7}}(A_{1}^{6}, A_{1}) = N_{E_{7}}(A_{1}^{5}, A_{2}) = N_{E_{7}}(A_{1}^{5}, A_{1}^{2}) = N_{E_{7}}(A_{1}^{5}, A_{1}, A_{1}) = 0.

We now let Mathematica 5.2 solve the described system of linear equations for the full rank decomposition numbers.^{3} Although this is a system of more than 200 equations with 115 variables, the solution space is two-dimensional. Mathematica expresses all the variables in terms of X = N_{E_{7}}(A_{1}^{4}, A_{1}^{3}) and Y = N_{E_{7}}(A_{1}^{2} ∗ A_{2}, A_{1}^{3}). For the subsequent considerations, we work with the following selection of relations output by Mathematica:

N_{E_{7}}(A_{5}, A_{2}) = \frac{1272}{25} − \frac{58}{75}X − \frac{58}{225}Y,  (6.1)
N_{E_{7}}(A_{4}, A_{3}) = \frac{594}{25} + \frac{18}{25}X + \frac{11}{25}Y,  (6.2)
N_{E_{7}}(D_{4}, A_{3}) = \frac{126}{5} − \frac{2}{5}X − \frac{7}{30}Y,  (6.3)
N_{E_{7}}(A_{1}^{3} ∗ A_{2}, A_{1}^{2}) = \frac{423}{5} − \frac{14}{5}X − \frac{14}{15}Y,  (6.4)
N_{E_{7}}(A_{1}^{3} ∗ A_{2}, A_{2}) = − \frac{192}{5} + \frac{28}{15}X + \frac{28}{45}Y.  (6.5)

Relation (6.1) implies

X − 8Y ≡ 2 (mod 25),  (6.6)

Relation (6.2) implies

18X + 11Y ≡ 6 (mod 25),  (6.7)

and Relation (6.3) implies

Y ≡ 0 (mod 6).  (6.8)

3The Mathematica input is available at http://www.mat.univie.ac.at/~kratt/artikel/cluster2.html.

Solving (6.6), (6.7) and (6.8) for X and Y yields

X = 25x + 15y + 4,
Y = 30y − 6,

for some integers x and y with y > 0. If we substitute this in (6.4) and (6.5), then we obtain

N_{E_{7}}(A_{1}^{3} ∗ A_{2}, A_{1}^{2}) = 79 − 70(x + y),
N_{E_{7}}(A_{1}^{3} ∗ A_{2}, A_{2}) = \frac{4}{3}(35(x + y) − 26).

Since the decomposition numbers must be non-negative integers, we conclude that x + y = 1. Thus, we have X = 29−10y and Y = 30y−6, with y = 1 or y = 2. To decide which of the two values is the true value, we appeal to Lemma 5. Given a decomposition c = c_{1}c_{2}, where c_{1} is of type A_{1}^{4} and c_{2} is of type A_{1}^{3}, the entire orbit O = {(c^{k}c_{1}c^{−k}, c^{k}c_{2}c^{−k}) : k ∈ ℤ} consists of pairs (x, y) with c = xy, where x is of type A_{1}^{4} and y is of type A_{1}^{3}. Since Lemma 5 in the case of E_{7} says that the orbits of reflections have all size 9, the size of O must be a divisor of 9. We claim that it cannot be 1. For, in that case c_{1} and c_{2} commute with the Coxeter element c. By a result of Carter [10, Prop. 30], the centralizer of c is known to be the cyclic group (of order h = 18) generated by c. Hence, c_{1} and c_{2} would have to be powers of c. Since c_{1} is of type A_{1}^{4} and c_{2} is of type A_{1}^{3}, both c_{1} and c_{2} are of order 2. However, the only element of order 2 in the cyclic group generated by c is c^{9}, whence c^{9} = c_{1} = c_{2}, which is absurd. The conclusion is that 3 divides the orbit O. Thus, 3 must divide X = N_{E_{7}}(A_{1}^{4}, A_{1}^{3}). Out of the two possible values for y, we must therefore choose y = 2, and so X = 9 and Y = N_{E_{7}}(A_{1}^{2} ∗ A_{2}, A_{1}^{3}) = 54.

Now we substitute these values in the expressions in terms of X and Y found by Mathematica for the other full rank decomposition numbers. The result is that N_{E_{7}}(E_{7}) = 1, N_{E_{7}}(E_{6}, A_{1}) = 9, N_{E_{7}}(D_{6}, A_{1}) = 9, N_{E_{7}}(A_{6}, A_{1}) = 9, N_{E_{7}}(A_{1} ∗ D_{5}, A_{1}) = 9, N_{E_{7}}(A_{1} ∗ A_{5}, A_{1}) = 9, N_{E_{7}}(A_{2} ∗ D_{4}, A_{1}) = 0, N_{E_{7}}(A_{2} ∗ A_{4}, A_{1}) = 9, N_{E_{7}}(A_{1}^{2} ∗ D_{4}, A_{1}) = 0, N_{E_{7}}(A_{1}^{2} ∗ A_{4}, A_{1}) = 0, N_{E_{7}}(A_{3}^{2}, A_{1}) = 0, N_{E_{7}}(A_{1} ∗ A_{2} ∗ A_{3}, A_{1}) = 9, N_{E_{7}}(A_{1}^{3} ∗ A_{3}, A_{1}) = 0, N_{E_{7}}(A_{2}^{3}, A_{1}) = 0, N_{E_{7}}(A_{1}^{2} ∗ A_{2}^{2}, A_{1}) = 0, N_{E_{7}}(A_{1}^{4} ∗ A_{2}, A_{1}) = 0, N_{E_{7}}(A_{1}^{6}, A_{1}) = 0, N_{E_{7}}(D_{5}, A_{2}) = 18, N_{E_{7}}(A_{5}, A_{2}) = 30, N_{E_{7}}(A_{1} ∗ A_{4}, A_{2}) = 54, N_{E_{7}}(A_{1} ∗ D_{4}, A_{2}) = 9, N_{E_{7}}(A_{2} ∗A_{3}, A_{2}) = 36, N_{E_{7}}(A_{1}^{2} ∗A_{3}, A_{2}) = 36, N_{E_{7}}(A_{1} ∗A_{2}^{2}, A_{2}) = 36, N_{E_{7}}(A_{1}^{3} ∗A_{2}, A_{2}) = 12, N_{E_{7}}(A_{1}^{5}, A_{2}) = 0, N_{E_{7}}(D_{5}, A_{1}^{2}) = 54, N_{E_{7}}(A_{5}, A_{1}^{2}) = 63, N_{E_{7}}(A_{1} ∗ D_{4}, A_{1}^{2}) = 27, N_{E_{7}}(A_{1} ∗A_{4}, A_{1}^{2}) = 81, N_{E_{7}}(A_{2} ∗A_{3}, A_{1}^{2}) = 27, N_{E_{7}}(A_{1}^{2} ∗A_{3}, A_{1}^{2}) = 27, N_{E_{7}}(A_{1} ∗A_{2}^{2}, A_{1}^{2}) = 27, N_{E_{7}}(A_{1}^{3} ∗ A_{2}, A_{1}^{2}) = 9, N_{E_{7}}(A_{1}^{5}, A_{1}^{2}) = 0, N_{E_{7}}(D_{5}, A_{1}, A_{1}) = 162, N_{E_{7}}(A_{5}, A_{1}, A_{1}) = 216, N_{E_{7}}(A_{1} ∗ D_{4}, A_{1}, A_{1}) = 81, N_{E_{7}}(A_{1} ∗ A_{4}, A_{1}, A_{1}) = 324, N_{E_{7}}(A_{2} ∗ A_{3}, A_{1}, A_{1}) = 162, N_{E_{7}}(A_{1}^{2} ∗ A_{3}, A_{1}, A_{1}) = 162, N_{E_{7}}(A_{1} ∗ A_{2}^{2}, A_{1}, A_{1}) = 162, N_{E_{7}}(A_{1}^{3} ∗ A_{2}, A_{1}, A_{1}) = 54, N_{E_{7}}(A_{1}^{5}, A_{1}, A_{1}) = 0, N_{E_{7}}(D_{4}, A_{3}) = 9, N_{E_{7}}(A_{4}, A_{3}) = 54, N_{E_{7}}(A_{1} ∗ A_{3}, A_{3}) = 135, N_{E_{7}}(A_{2}^{2}, A_{3}) = 54, N_{E_{7}}(A_{1}^{2} ∗ A_{2}, A_{3}) = 162, N_{E_{7}}(A_{1}^{4}, A_{3}) = 27, N_{E_{7}}(D_{4}, A_{1} ∗ A_{2}) = 45, N_{E_{7}}(A_{4}, A_{1} ∗ A_{2}) = 162, N_{E_{7}}(A_{1} ∗ A_{3}, A_{1} ∗ A_{2}) = 243, N_{E_{7}}(A_{2}^{2}, A_{1} ∗ A_{2}) = 54, N_{E_{7}}(A_{1}^{2}∗A_{2}, A_{1}∗A_{2}) = 162, N_{E_{7}}(A_{1}^{4}, A_{1}∗A_{2}) = 27, N_{E_{7}}(D_{4}, A_{1}^{3}) = 30, N_{E_{7}}(A_{4}, A_{1}^{3}) = 99, N_{E_{7}}(A_{1} ∗ A_{3}, A_{1}^{3}) = 126, N_{E_{7}}(A_{2}^{2}, A_{1}^{3}) = 18, N_{E_{7}}(A_{1}^{2} ∗ A_{2}, A_{1}^{3}) = 54, N_{E_{7}}(A_{1}^{4}, A_{1}^{3}) = 9, N_{E_{7}}(D_{4}, A_{2}, A_{1}) = 81, N_{E_{7}}(A_{4}, A_{2}, A_{1}) = 378, N_{E_{7}}(A_{1} ∗ A_{3}, A_{2}, A_{1}) = 783, N_{E_{7}}(A_{2}^{2}, A_{2}, A_{1}) = 270, N_{E_{7}}(A_{1}^{2} ∗ A_{2}, A_{2}, A_{1}) = 810, N_{E_{7}}(A_{1}^{4}, A_{2}, A_{1}) = 135, N_{E_{7}}(D_{4}, A_{1}^{2}, A_{1}) = 243, N_{E_{7}}(A_{4}, A_{1}^{2}, A_{1}) = 891, N_{E_{7}}(A_{1} ∗ A_{3}, A_{1}^{2}, A_{1}) = 1377, N_{E_{7}}(A_{2}^{2}, A_{1}^{2}, A_{1}) = 324, N_{E_{7}}(A_{1}^{2} ∗ A_{2}, A_{1}^{2}, A_{1}) = 972, N_{E_{7}}(A_{1}^{4}, A_{1}^{2}, A_{1}) = 162, N_{E_{7}}(D_{4}, A_{1}, A_{1}, A_{1}) = 729, N_{E_{7}}(A_{4}, A_{1}, A_{1}, A_{1}) = 2916, N_{E_{7}}(A_{1} ∗ A_{3}, A_{1}, A_{1}, A_{1}) = 5103, N_{E_{7}}(A_{2}^{2}, A_{1}, A_{1}, A_{1}) = 1458, N_{E_{7}}(A_{1}^{2} ∗ A_{2}, A_{1}, A_{1}, A_{1}) = 4374, N_{E_{7}}(A_{1}^{4}, A_{1}, A_{1}, A_{1}) = 729, N_{E_{7}}(A_{3}, A_{3}, A_{1}) = 486, N_{E_{7}}(A_{3}, A_{1} ∗ A_{2}, A_{1}) = 1458, N_{E_{7}}(A_{3}, A_{1}^{3}, A_{1}) = 891, N_{E_{7}}(A_{1} ∗ A_{2}, A_{1} ∗ A_{2}, A_{1}) = 2430, N_{E_{7}}(A_{1} ∗ A_{2}, A_{1}^{3}, A_{1}) = 1215, N_{E_{7}}(A_{1}^{3}, A_{1}^{3}, A_{1}) = 540, N_{E_{7}}(A_{3}, A_{2}, A_{2}) = 432, N_{E_{7}}(A_{1} ∗ A_{2}, A_{2}, A_{2}) = 1188, N_{E_{7}}(A_{1}^{3}, A_{2}, A_{2}) = 711, N_{E_{7}}(A_{3}, A_{2}, A_{1}^{2}) = 1053, N_{E_{7}}(A_{1} ∗ A_{2}, A_{2}, A_{1}^{2}) = 2349, N_{E_{7}}(A_{1}^{3}, A_{2}, A_{1}^{2}) = 1323, N_{E_{7}}(A_{3}, A_{1}^{2}, A_{1}^{2}) = 2430, N_{E_{7}}(A_{1} ∗ A_{2}, A_{1}^{2}, A_{1}^{2}) = 3402, N_{E_{7}}(A_{1}^{3}, A_{1}^{2}, A_{1}^{2}) = 1539, N_{E_{7}}(A_{3}, A_{2}, A_{1}, A_{1}) = 3402, N_{E_{7}}(A_{1} ∗ A_{2}, A_{2}, A_{1}, A_{1}) = 8262, N_{E_{7}}(A_{1}^{3}, A_{2}, A_{1}, A_{1}) = 4779, N_{E_{7}}(A_{3}, A_{1}^{2}, A_{1}, A_{1}) = 8019, N_{E_{7}}(A_{1} ∗ A_{2}, A_{1}^{2}, A_{1}, A_{1}) = 13851, N_{E_{7}}(A_{1}^{3}, A_{1}^{2}, A_{1}, A_{1}) = 7047, N_{E_{7}}(A_{3}, A_{1}, A_{1}, A_{1}, A_{1}) = 26244, N_{E_{7}}(A_{1} ∗ A_{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 52488, N_{E_{7}}(A_{1}^{3}, A_{1}, A_{1}, A_{1}, A_{1}) = 28431, N_{E_{7}}(A_{2}, A_{2}, A_{2}, A_{1}) = 2916, N_{E_{7}}(A_{2}, A_{2}, A_{1}^{2}, A_{1}) = 6561, N_{E_{7}}(A_{2}, A_{1}^{2}, A_{1}^{2}, A_{1}) = 13122, N_{E_{7}}(A_{1}^{2}, A_{1}^{2}, A_{1}^{2}, A_{1}) = 19683, N_{E_{7}}(A_{2}, A_{2}, A_{1}, A_{1}, A_{1}) = 21870, N_{E_{7}}(A_{2}, A_{1}^{2}, A_{1}, A_{1}, A_{1}) = 45927, N_{E_{7}}(A_{1}^{2}, A_{1}^{2}, A_{1}, A_{1}, A_{1}) = 78732, N_{E_{7}}(A_{2}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 157464, N_{E_{7}}(A_{1}^{2}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 295245, N_{E_{7}}(A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 1062882, plus the assignments implied by (4.1) and (4.2), all other numbers N_{E_{7}}(T_{1}, …, T_{d}) being zero.

Finally, we substitute the values found for the decomposition numbers and the formulae for the characteristic polynomials from (5.2) in (3.1), and we obtain

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

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

+ \frac{3}{40} m^{2}(9m − 2)(9m − 4)(3m − 1)(243m^{2} − 81m − 14)x^{7}y^{5}

− \frac{3}{8} m^{2}(3m − 1)(9m − 2)(9m + 2)(81m^{2} − 9m − 4)x^{7}y^{4}

+ \frac{3}{8} m^{2}(9m − 2)(3m + 1)(9m + 2)(81m^{2} + 9m − 4)x^{7}y^{3}

− \frac{3}{40} m^{2}(3m + 1)(9m + 2)(9m + 4)(243m^{2} + 81m − 14)x^{7}y^{2}

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

− \frac{1}{280} m(3m + 1)(3m + 2)(9m + 2)(9m + 4)(9m + 5)(9m + 8)x^{7}

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

− \frac{27}{20} m^{2}(27m − 13)(9m − 2)(9m − 4)(3m − 1)x^{6}y^{5}

+ \frac{27}{8} m^{2}(3m − 1)(9m − 2)(243m^{2} − 45m − 10)x^{6}y^{4} − \frac{27}{2} m^{2}(9m − 2)(9m + 2)(27m^{2} − 1)x^{6}y^{3}

+ \frac{27}{8} m^{2}(3m + 1)(9m + 2)(243m^{2} + 45m − 10)x^{6}y^{2} − \frac{27}{20} m^{2}(3m + 1)(9m + 2)(9m + 4)(27m + 13)x^{6}y

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

− \frac{27}{8} m^{2}(207m − 71)(3m − 1)(9m − 2)x^{5}y^{4} + \frac{9}{4} m^{2}(9m − 2)(1863m^{2} − 144m − 55)x^{5}y^{3}

− \frac{9}{4} m^{2}(9m + 2)(1863m^{2} + 144m − 55)x^{5}y^{2} + \frac{27}{8} m^{2}(3m + 1)(9m + 2)(207m + 71)x^{5}y

− \frac{3}{40} m(3m + 1)(9m + 2)(9m + 4)(207m + 103)x^{5} + \frac{21}{8} m(63m − 23)(3m − 1)(9m − 2)x^{4}y^{4}

− \frac{189}{2} m^{2}(21m − 5)(9m − 2)x^{4}y^{3} + \frac{63}{4} m^{2}(1701m^{2} − 37)x^{4}y^{2} − \frac{189}{2} m^{2}(9m + 2)(21m + 5)x^{4}y

+ \frac{21}{8} m(3m + 1)(9m + 2)(63m + 23)x^{4} + \frac{21}{2} m(27m − 7)(9m − 2)x^{3}y^{3} − \frac{189}{2} m^{2}(81m − 13)x^{3}y^{2}

+ \frac{189}{2} m^{2}(81m + 13)x^{3}y − \frac{21}{2} m(9m + 2)(27m + 7)x^{3} + \frac{21}{2} m(63m − 11)x^{2}y^{2}

− 1323m^{2}x^{2}y + \frac{21}{2} m(63m + 11)x^{2} + 63mxy − 63mx + 1. (6.9)

7. The M-triangle of generalised non-crossing partitions of type E_{8}. In this section we implement the programme outlined in Sections 4 and 5 to compute the decomposition numbers for E_{8} and, thus, via (3.1) and (5.2), the M-triangle of the m-divisible non-crossing partitions of type E_{8}.

Again, to begin with, we have to compute the decomposition numbers for types of smaller ranks, that is, of ranks ≤ 7. The decomposition numbers for the irreducible types of rank ≤ 7 that we need, for A_{1}, A_{2}, A_{3}, A_{4}, A_{5}, A_{6}, A_{7}, D_{4}, D_{5}, D_{6}, D_{7}, E_{6}, and E_{7}, are given in the Appendix, respectively in Section 6. Those for the reducible types of rank ≤ 7 then can be computed by using Proposition 7.^{4} Then we use (4.1) and (4.2) to express all the decomposition numbers in terms of full rank decomposition numbers N_{Φ}(T_{1}, T_{2}, …, T_{d}) (that is, those with rk Φ = rk T_{1} +rk T_{1} +⋯+rk T_{d}), in which the types T_{i} are ordered (for example, according to lexicographic order). Subsequently we produce the equations which one obtains from (4.3) (using the earlier computed decomposition numbers of smaller rank) and from comparing coefficients of m^{i}z^{j}, i, j ∈ {0, 1, …, 8}, on both sides of (4.7). Finally, we use Proposition 4 to determine N_{E_{8}}(E_{8}), N_{E_{8}}(A_{1}) and N_{E_{8}}(A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}), Proposition 6 to compute the numbers N_{E_{8}}(T, A_{1}) with rk T = 7, and we use the last assertion in Proposition 2 for the types A_{1}^{6}, A_{1}^{5}, A_{1}^{3} ∗ A_{3}, A_{2}^{3} and A_{1}^{2} ∗ D_{4} (which do not occur as the type of a sub-diagram of the Dynkin diagram of E_{8}). To wit, the latter leads to the following special values of decomposition numbers:

N_{E_{8}}(E_{8}) = 1,
N_{E_{8}}(A_{1}) = 120,
N_{E_{8}}(A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 37968750,
N_{E_{8}}(E_{7}, A_{1}) = N_{E_{8}}(D_{7}, A_{1}) = N_{E_{8}}(A_{7}, A_{1}) = N_{E_{8}}(A_{1} ∗ E_{6}, A_{1})
= N_{E_{8}}(A_{1} ∗ A_{6}, A_{1}) = N_{E_{8}}(A_{2} ∗ D_{5}, A_{1})
= N_{E_{8}}(A_{3} ∗ A_{4}, A_{1}) = N_{E_{8}}(A_{1} ∗ A_{2} ∗ A_{4}, A_{1}) = 15,

4See Footnote 1.

N_{E_{8}}(A_{1} ∗ D_{6}, A_{1}) = N_{E_{8}}(A_{2} ∗ A_{5}, A_{1}) = N_{E_{8}}(A_{1}^{2} ∗ D_{5}, A_{1}) = N_{E_{8}}(A_{1}^{2} ∗ A_{5}, A_{1}) = N_{E_{8}}(A_{3} ∗ D_{4}, A_{1}) = N_{E_{8}}(A_{1} ∗ A_{2} ∗ D_{4}, A_{1}) = N_{E_{8}}(A_{1}^{3} ∗ D_{4}, A_{1}) = N_{E_{8}}(A_{1}^{3} ∗ A_{4}, A_{1}) = N_{E_{8}}(A_{1} ∗ A_{3}^{2}, A_{1}) = N_{E_{8}}(A_{2}^{2} ∗ A_{3}, A_{1}) = N_{E_{8}}(A_{1}^{2} ∗ A_{2} ∗ A_{3}, A_{1}) = N_{E_{8}}(A_{1}^{4} ∗ A_{3}, A_{1}) = N_{E_{8}}(A_{1} ∗ A_{2}^{3}, A_{1}) = N_{E_{8}}(A_{1}^{3} ∗ A_{2}^{2}, A_{1}) = N_{E_{8}}(A_{1}^{5} ∗ A_{2}, A_{1}) = N_{E_{8}}(A_{1}^{7}, A_{1}) = N_{E_{8}}(A_{1}^{6}, A_{2}) = N_{E_{8}}(A_{1}^{6}, A_{1}^{2}) = N_{E_{8}}(A_{1}^{6}, A_{1}, A_{1}) = N_{E_{8}}(A_{1}^{5}, A_{3}) = N_{E_{8}}(A_{1}^{5}, A_{1} ∗ A_{2}) = N_{E_{8}}(A_{1}^{5}, A_{1}^{3}) = N_{E_{8}}(A_{1}^{5}, A_{2}, A_{1}) = N_{E_{8}}(A_{1}^{5}, A_{1}^{2}, A_{1}) = N_{E_{8}}(A_{1}^{5}, A_{1}, A_{1}, A_{1}) = N_{E_{8}}(A_{1}^{3} ∗ A_{3}, A_{2}) = N_{E_{8}}(A_{1}^{3} ∗ A_{3}, A_{1}^{2}) = N_{E_{8}}(A_{1}^{3} ∗ A_{3}, A_{1}, A_{1}) = N_{E_{8}}(A_{2}^{3}, A_{2}) = N_{E_{8}}(A_{2}^{3}, A_{1}^{2}) = N_{E_{8}}(A_{1}^{4} ∗ A_{2}, A_{2}) = N_{E_{8}}(A_{1}^{4} ∗ A_{2}, A_{1}^{2}) = N_{E_{8}}(A_{1}^{2} ∗ D_{4}, A_{2}) = N_{E_{8}}(A_{1}^{2} ∗ D_{4}, A_{1}^{2}) = 0.

Again, we let Mathematica 5.2 solve the described system of linear equations for the full rank decomposition numbers.^{5} Although this is now a system of more than 600 equations with only about 250 variables, the situation here is even worse as the solution space is four-dimensional. Mathematica expresses all the variables in terms of X = N_{E_{8}}(A_{5}, A_{1} ∗ A_{2}), Y = N_{E_{8}}(D_{5}, A_{1} ∗ A_{2}), N_{E_{8}}(A_{4}, A_{1} ∗ A_{3}), and N_{E_{8}}(D_{4}, A_{4}). For the subsequent considerations, we work with the following selection of relations output by Mathematica:

N_{E_{8}}(A_{5}, A_{3}) = \frac{1}{4}(750 − X),  (7.1)
N_{E_{8}}(D_{5}, A_{3}) = \frac{1}{4}(375 − Y),  (7.2)
N_{E_{8}}(A_{5}, A_{1}^{3}) = \frac{5}{6}(750 − X),  (7.3)
N_{E_{8}}(D_{5}, A_{1}^{3}) = \frac{5}{6}(375 − Y),  (7.4)
N_{E_{8}}(A_{2} ∗ A_{3}, A_{1} ∗ A_{2}) = \frac{3}{25}(4125 − 8X + 16Y),  (7.5)
N_{E_{8}}(A_{2} ∗ A_{3}, A_{1}^{3}) = \frac{1}{5}(1125 + 4X − 8Y),  (7.6)
N_{E_{8}}(A_{1} ∗ D_{4}, A_{3}) = Y − 150,  (7.7)
N_{E_{8}}(A_{1}^{2} ∗ A_{3}, A_{1}^{3}) = \frac{1}{5}(49875 − 56X − 138Y),  (7.8)
N_{E_{8}}(A_{1} ∗ A_{4}, A_{1} ∗ A_{2}) = 2(2295 − 3X − 4Y),  (7.9)
N_{E_{8}}(A_{1}^{3} ∗ A_{2}, A_{1}^{3}) = \frac{1}{15}(112X + 226Y − 86625).  (7.10)

There is one further relation which we shall make use of,

N_{E_{8}}(D_{4}) = N_{E_{8}}(D_{4}, D_{4}) + N_{E_{8}}(D_{4}, A_{4}) + N_{E_{8}}(D_{4}, A_{3} ∗ A_{1})
+ N_{E_{8}}(D_{4}, A_{2}^{2}) + N_{E_{8}}(D_{4}, A_{2} ∗ A_{1}^{2}) + N_{E_{8}}(D_{4}, A_{1}^{4})  (7.11)

= \frac{27263}{168} − \frac{1}{40}N_{E_{8}}(A_{4}, A_{1} ∗ A_{3}) + \frac{1}{40}N_{E_{8}}(D_{4}, A_{4}) + \frac{283}{1500}X + \frac{7957}{15750}Y, (7.12)

5The Mathematica input is available at http://www.mat.univie.ac.at/~kratt/artikel/cluster2.html.

where the first line is an instance of (4.2), and where the second line follows from the first upon substituting the relations for the full rank decomposition numbers output by Mathematica.

Relations (7.1) and (7.3) imply

X ≡ 6 (mod 12),  (7.13)

and Relations (7.2) and (7.4) imply

Y ≡ 3 (mod 12).  (7.14)

Next, Relation (7.5) implies

X ≡ 2Y (mod 25).  (7.15)

Solving (7.13), (7.14) and (7.15) for X and Y yields

X = 300x + 24y + 6,  (7.16)
Y = 12y + 3,  (7.17)

for some integers x and y with y ≥ 0. If we substitute this in (7.1), (7.6)–(7.10), then we obtain

N_{E_{8}}(A_{5}, A_{3}) = 3(62 − 25x − 2y),  (7.18)
N_{E_{8}}(A_{2} ∗ A_{3}, A_{1}^{3}) = 225 + 240x,  (7.19)
N_{E_{8}}(A_{1} ∗ D_{4}, A_{3}) = 12y − 147,  (7.20)
N_{E_{8}}(A_{1}^{2} ∗ A_{3}, A_{1}^{3}) = 15(655 − 224x − 40y),  (7.21)
N_{E_{8}}(A_{1} ∗ A_{4}, A_{1} ∗ A_{2}) = 30(151 − 60x − 8y),  (7.22)
N_{E_{8}}(A_{1}^{3} ∗ A_{2}, A_{1}^{3}) = 5(448x + 72y − 1137).  (7.23)

From (7.18) we infer x ≤ 2, while (7.19) implies x ≥ 0. Furthermore, from (7.20) we infer y ≥ 13, while (7.21) implies y ≤ 16. If x ≥ 1, then (7.22) implies y ≤ 91/8 < 13, a contradiction. Hence, x = 0. In this case, Equation (7.23) implies y ≥ 1137/72 > 15, and so y = 16. Substituting this in (7.16) and (7.17), we obtain X = N_{E_{8}}(A_{5}, A_{1} ∗ A_{2}) = 390 and Y = N_{E_{8}}(D_{5}, A_{1} ∗ A_{2}) = 195.

Unfortunately, similar arithmetic and positivity considerations do not suffice to determine the remaining two “free variables,” the decomposition numbers N_{E_{8}}(A_{4}, A_{1} ∗ A_{3}) and N_{E_{8}}(D_{4}, A_{4}). Instead, by a 12 days Maple computation using Stembridge’s coxeter package, we found that N_{E_{8}}(D_{4}) = 325 and N_{E_{8}}(D_{4}, A_{4}) = 15. If we use these values, together with the already determined values for X and Y, in (7.12), we eventually find that N_{E_{8}}(A_{4}, A_{1} ∗ A_{3}) = 390.

We now substitute the above values for N_{E_{8}}(A_{5}, A_{1} ∗ A_{2}), N_{E_{8}}(D_{5}, A_{1} ∗ A_{2}), N_{E_{8}}(A_{4}, A_{1} ∗ A_{3}), and N_{E_{8}}(D_{4}, A_{4}) in the expressions found by Mathematica for the other full rank decomposition numbers. The result is that N_{E_{8}}(E_{8}) = 1, N_{E_{8}}(E_{7}, A_{1}) = 15, N_{E_{8}}(D_{7}, A_{1}) = 15, N_{E_{8}}(A_{7}, A_{1}) = 15, N_{E_{8}}(A_{1} ∗ E_{6}, A_{1}) = 15, N_{E_{8}}(A_{1} ∗ D_{6}, A_{1}) = 0, N_{E_{8}}(A_{1}∗A_{6}, A_{1}) = 15, N_{E_{8}}(A_{2}∗D_{5}, A_{1}) = 15, N_{E_{8}}(A_{2}∗A_{5}, A_{1}) = 0,N_{E_{8}}(A_{1}^{2}∗D_{5}, A_{1}) = 0, N_{E_{8}}(A_{1}^{2} ∗ A_{5}, A_{1}) = 0, N_{E_{8}}(A_{3} ∗ D_{4}, A_{1}) = 0, N_{E_{8}}(A_{3} ∗ A_{4}, A_{1}) = 15, N_{E_{8}}(A_{1} ∗ A_{2} ∗ D_{4}, A_{1}) = 0, N_{E_{8}}(A_{1} ∗ A_{2} ∗ A_{4}, A_{1}) = 15, N_{E_{8}}(A_{1}^{3} ∗ D_{4}, A_{1}) = 0, N_{E_{8}}(A_{1}^{3} ∗ A_{4}, A_{1}) = 0, N_{E_{8}}(A_{1} ∗ A_{3}^{2}, A_{1}) = 0, N_{E_{8}}(A_{2}^{2} ∗ A_{3}, A_{1}) = 0, N_{E_{8}}(A_{1}^{2} ∗ A_{2} ∗ A_{3}, A_{1}) = 0, N_{E_{8}}(A_{1}^{4} ∗ A_{3}, A_{1}) = 0, N_{E_{8}}(A_{1} ∗ A_{2}^{3}, A_{1}) = 0, N_{E_{8}}(A_{1}^{3} ∗ A_{2}^{2}, A_{1}) = 0, N_{E_{8}}(A_{1}^{5} ∗ A_{2}, A_{1}) = 0, N_{E_{8}}(A_{1}^{7}, A_{1}) = 0, N_{E_{8}}(E_{6}, A_{2}) = 20, N_{E_{8}}(D_{6}, A_{2}) = 15, N_{E_{8}}(A_{6}, A_{2}) = 60, N_{E_{8}}(A_{1} ∗ D_{5}, A_{2}) = 60, N_{E_{8}}(A_{1} ∗ A_{5}, A_{2}) = 60, N_{E_{8}}(A_{2} ∗ D_{4}, A_{2}) = 20, N_{E_{8}}(A_{2} ∗ A_{4}, A_{2}) = 90, N_{E_{8}}(A_{3}^{2}, A_{2}) = 45, N_{E_{8}}(A_{1}^{2} ∗ D_{4}, A_{2}) = 0, N_{E_{8}}(A_{1}^{2} ∗ A_{4}, A_{2}) = 90, N_{E_{8}}(A_{1} ∗ A_{2} ∗ A_{3}, A_{2}) = 90, N_{E_{8}}(A_{1}^{3} ∗ A_{3}, A_{2}) = 0, N_{E_{8}}(A_{2}^{3}, A_{2}) = 0, N_{E_{8}}(A_{1}^{2} ∗ A_{2}^{2}, A_{2}) = 45, N_{E_{8}}(A_{1}^{4} ∗ A_{2}, A_{2}) = 0, N_{E_{8}}(A_{1}^{6}, A_{2}) = 0, N_{E_{8}}(E_{6}, A_{1}^{2}) = 45, N_{E_{8}}(D_{6}, A_{1}^{2}) = 90, N_{E_{8}}(A_{6}, A_{1}^{2}) = 135, N_{E_{8}}(A_{1} ∗ D_{5}, A_{1}^{2}) = 135, N_{E_{8}}(A_{1} ∗ A_{5}, A_{1}^{2}) = 135, N_{E_{8}}(A_{2} ∗ D_{4}, A_{1}^{2}) = 45, N_{E_{8}}(A_{2} ∗ A_{4}, A_{1}^{2}) = 90, N_{E_{8}}(A_{3}^{2}, A_{1}^{2}) = 45, N_{E_{8}}(A_{1}^{2} ∗ D_{4}, A_{1}^{2}) = 0, N_{E_{8}}(A_{1}^{2} ∗ A_{4}, A_{1}^{2}) = 90, N_{E_{8}}(A_{1} ∗ A_{2} ∗ A_{3}, A_{1}^{2}) = 90, N_{E_{8}}(A_{1}^{3} ∗ A_{3}, A_{1}^{2}) = 0, N_{E_{8}}(A_{2}^{3}, A_{1}^{2}) = 0, N_{E_{8}}(A_{1}^{2} ∗ A_{2}^{2}, A_{1}^{2}) = 45, N_{E_{8}}(A_{1}^{4} ∗ A_{2}, A_{1}^{2}) = 0, N_{E_{8}}(A_{1}^{6}, A_{1}^{2}) = 0, N_{E_{8}}(E_{6}, A_{1}, A_{1}) = 150, N_{E_{8}}(D_{6}, A_{1}, A_{1}) = 225, N_{E_{8}}(A_{6}, A_{1}, A_{1}) = 450, N_{E_{8}}(A_{1} ∗ D_{5}, A_{1}, A_{1}) = 450, N_{E_{8}}(A_{1} ∗ A_{5}, A_{1}, A_{1}) = 450, N_{E_{8}}(A_{2}∗D_{4}, A_{1}, A_{1}) = 150, N_{E_{8}}(A_{2}∗A_{4}, A_{1}, A_{1}) = 450, N_{E_{8}}(A_{3}^{2}, A_{1}, A_{1}) = 225, N_{E_{8}}(A_{1}^{2}∗ D_{4}, A_{1}, A_{1}) = 0, N_{E_{8}}(A_{1}^{2} ∗ A_{4}, A_{1}, A_{1}) = 450, N_{E_{8}}(A_{1} ∗ A_{2} ∗ A_{3}, A_{1}, A_{1}) = 450, N_{E_{8}}(A_{1}^{3} ∗ A_{3}, A_{1}, A_{1}) = 0, N_{E_{8}}(A_{2}^{3}, A_{1}, A_{1}) = 0, N_{E_{8}}(A_{1}^{2} ∗A_{2}^{2}, A_{1}, A_{1}) = 225, N_{E_{8}}(A_{1}^{4} ∗A_{2}, A_{1}, A_{1}) = 0, N_{E_{8}}(A_{1}^{6}, A_{1}, A_{1}) = 0, N_{E_{8}}(D_{5}, A_{3}) = 45, N_{E_{8}}(A_{5}, A_{3}) = 90, N_{E_{8}}(A_{1} ∗ A_{4}, A_{3}) = 315, N_{E_{8}}(A_{1} ∗ D_{4}, A_{3}) = 45, N_{E_{8}}(A_{2} ∗ A_{3}, A_{3}) = 270, N_{E_{8}}(A_{1}^{2} ∗ A_{3}, A_{3}) = 270, N_{E_{8}}(A_{1} ∗ A_{2}^{2}, A_{3}) = 225, N_{E_{8}}(A_{1}^{3} ∗ A_{2}, A_{3}) = 225, N_{E_{8}}(A_{1}^{5}, A_{3}) = 0, N_{E_{8}}(D_{5}, A_{1} ∗ A_{2}) = 195, N_{E_{8}}(A_{5}, A_{1} ∗ A_{2}) = 390, N_{E_{8}}(A_{1} ∗ A_{4}, A_{1} ∗ A_{2}) = 690, N_{E_{8}}(A_{1} ∗ D_{4}, A_{1} ∗ A_{2}) = 195, N_{E_{8}}(A_{2} ∗ A_{3}, A_{1} ∗ A_{2}) = 495, N_{E_{8}}(A_{1}^{2} ∗ A_{3}, A_{1} ∗ A_{2}) = 495, N_{E_{8}}(A_{1} ∗ A_{2}^{2}, A_{1} ∗ A_{2}) = 300, N_{E_{8}}(A_{1}^{3} ∗ A_{2}, A_{1} ∗ A_{2}) = 300, N_{E_{8}}(A_{1}^{5}, A_{1} ∗ A_{2}) = 0, N_{E_{8}}(D_{5}, A_{1}^{3}) = 150, N_{E_{8}}(A_{5}, A_{1}^{3}) = 300, N_{E_{8}}(A_{1} ∗ A_{4}, A_{1}^{3}) = 375, N_{E_{8}}(A_{1} ∗ D_{4}, A_{1}^{3}) = 150, N_{E_{8}}(A_{2} ∗ A_{3}, A_{1}^{3}) = 225, N_{E_{8}}(A_{1}^{2} ∗ A_{3}, A_{1}^{3}) = 225, N_{E_{8}}(A_{1} ∗ A_{2}^{2}, A_{1}^{3}) = 75, N_{E_{8}}(A_{1}^{3} ∗ A_{2}, A_{1}^{3}) = 75, N_{E_{8}}(A_{1}^{5}, A_{1}^{3}) = 0, N_{E_{8}}(D_{5}, A_{2}, A_{1}) = 375, N_{E_{8}}(A_{5}, A_{2}, A_{1}) = 750, N_{E_{8}}(A_{1} ∗ A_{4}, A_{2}, A_{1}) = 1950, N_{E_{8}}(A_{1} ∗ D_{4}, A_{2}, A_{1}) = 375, N_{E_{8}}(A_{2} ∗ A_{3}, A_{2}, A_{1}) = 1575, N_{E_{8}}(A_{1}^{2} ∗ A_{3}, A_{2}, A_{1}) = 1575, N_{E_{8}}(A_{1} ∗ A_{2}^{2}, A_{2}, A_{1}) = 1200, N_{E_{8}}(A_{1}^{3}∗A_{2}, A_{2}, A_{1}) = 1200, N_{E_{8}}(A_{1}^{5}, A_{2}, A_{1}) = 0, N_{E_{8}}(D_{5}, A_{1}^{2}, A_{1}) = 1125, N_{E_{8}}(A_{5}, A_{1}^{2}, A_{1}) = 2250, N_{E_{8}}(A_{1} ∗A_{4}, A_{1}^{2}, A_{1}) = 3825, N_{E_{8}}(A_{1} ∗D_{4}, A_{1}^{2}, A_{1}) = 1125, N_{E_{8}}(A_{2} ∗ A_{3}, A_{1}^{2}, A_{1}) = 2700, N_{E_{8}}(A_{1}^{2} ∗ A_{3}, A_{1}^{2}, A_{1}) = 2700, N_{E_{8}}(A_{1} ∗ A_{2}^{2}, A_{1}^{2}, A_{1}) = 1575, N_{E_{8}}(A_{1}^{3} ∗ A_{2}, A_{1}^{2}, A_{1}) = 1575, N_{E_{8}}(A_{1}^{5}, A_{1}^{2}, A_{1}) = 0, N_{E_{8}}(D_{5}, A_{1}, A_{1}, A_{1}) = 3375, N_{E_{8}}(A_{5}, A_{1}, A_{1}, A_{1}) = 6750, N_{E_{8}}(A_{1}∗A_{4}, A_{1}, A_{1}, A_{1}) = 13500, N_{E_{8}}(A_{1}∗D_{4}, A_{1}, A_{1}, A_{1}) = 3375, N_{E_{8}}(A_{2} ∗ A_{3}, A_{1}, A_{1}, A_{1}) = 10125, N_{E_{8}}(A_{1}^{2} ∗ A_{3}, A_{1}, A_{1}, A_{1}) = 10125, N_{E_{8}}(A_{1} ∗ A_{2}^{2}, A_{1}, A_{1}, A_{1}) = 6750, N_{E_{8}}(A_{1}^{3} ∗ A_{2}, A_{1}, A_{1}, A_{1}) = 6750, N_{E_{8}}(A_{1}^{5}, A_{1}, A_{1}, A_{1}) = 0, N_{E_{8}}(D_{4}, D_{4}) = 5, N_{E_{8}}(D_{4}, A_{4}) = 15, N_{E_{8}}(A_{4}, A_{4}) = 138, N_{E_{8}}(D_{4}, A_{1} ∗ A_{3}) = 105, N_{E_{8}}(A_{4}, A_{1} ∗ A_{3}) = 390, N_{E_{8}}(A_{1} ∗ A_{3}, A_{1} ∗ A_{3}) = 1155, N_{E_{8}}(D_{4}, A_{2}^{2}) = 35, N_{E_{8}}(A_{4}, A_{2}^{2}) = 180, N_{E_{8}}(A_{1} ∗ A_{3}, A_{2}^{2}) = 360, N_{E_{8}}(A_{2}^{2}, A_{2}^{2}) = 95, N_{E_{8}}(D_{4}, A_{1}^{2} ∗ A_{2}) = 135, N_{E_{8}}(A_{4}, A_{1}^{2} ∗ A_{2}) = 630, N_{E_{8}}(A_{1} ∗A_{3}, A_{1}^{2} ∗A_{2}) = 1035, N_{E_{8}}(A_{2}^{2}, A_{1}^{2} ∗A_{2}) = 270, N_{E_{8}}(A_{1}^{2} ∗A_{2}, A_{1}^{2} ∗A_{2}) = 495, N_{E_{8}}(D_{4}, A_{1}^{4}) = 30, N_{E_{8}}(A_{4}, A_{1}^{4}) = 165, N_{E_{8}}(A_{1} ∗ A_{3}, A_{1}^{4}) = 255, N_{E_{8}}(A_{2}^{2}, A_{1}^{4}) = 60, N_{E_{8}}(A_{1}^{2} ∗ A_{2}, A_{1}^{4}) = 135, N_{E_{8}}(A_{1}^{4}, A_{1}^{4}) = 30, N_{E_{8}}(D_{4}, A_{3}, A_{1}) = 225, N_{E_{8}}(A_{4}, A_{3}, A_{1}) = 1215, N_{E_{8}}(A_{1} ∗A_{3}, A_{3}, A_{1}) = 4050, N_{E_{8}}(A_{2}^{2}, A_{3}, A_{1}) = 1575, N_{E_{8}}(A_{1}^{2} ∗A_{2}, A_{3}, A_{1}) = 5400, N_{E_{8}}(A_{1}^{4}, A_{3}, A_{1}) = 1350, N_{E_{8}}(D_{4}, A_{1} ∗ A_{2}, A_{1}) = 975, N_{E_{8}}(A_{4}, A_{1} ∗ A_{2}, A_{1}) = 4590, N_{E_{8}}(A_{1}∗A_{3}, A_{1}∗A_{2}, A_{1}) = 10800, N_{E_{8}}(A_{2}^{2}, A_{1}∗A_{2}, A_{1}) = 3450, N_{E_{8}}(A_{1}^{2}∗A_{2}, A_{1}∗A_{2}, A_{1}) = 9900, N_{E_{8}}(A_{1}^{4}, A_{1} ∗ A_{2}, A_{1}) = 2475, N_{E_{8}}(D_{4}, A_{1}^{3}, A_{1}) = 750, N_{E_{8}}(A_{4}, A_{1}^{3}, A_{1}) = 3375, N_{E_{8}}(A_{1} ∗ A_{3}, A_{1}^{3}, A_{1}) = 6750, N_{E_{8}}(A_{2}^{2}, A_{1}^{3}, A_{1}) = 1875, N_{E_{8}}(A_{1}^{2} ∗ A_{2}, A_{1}^{3}, A_{1}) = 4500, N_{E_{8}}(A_{1}^{4}, A_{1}^{3}, A_{1}) = 1125, N_{E_{8}}(D_{4}, A_{2}, A_{2}) = 175, N_{E_{8}}(A_{4}, A_{2}, A_{2}) = 1140, N_{E_{8}}(A_{1} ∗ A_{3}, A_{2}, A_{2}) = 3300, N_{E_{8}}(A_{2}^{2}, A_{2}, A_{2}) = 1300, N_{E_{8}}(A_{1}^{2} ∗A_{2}, A_{2}, A_{2}) = 4500, N_{E_{8}}(A_{1}^{4}, A_{2}, A_{2}) = 1125, N_{E_{8}}(D_{4}, A_{2}, A_{1}^{2}) = 675, N_{E_{8}}(A_{4}, A_{2}, A_{1}^{2}) = 3015, N_{E_{8}}(A_{1} ∗ A_{3}, A_{2}, A_{1}^{2}) = 8550, N_{E_{8}}(A_{2}^{2}, A_{2}, A_{1}^{2}) = 2925, N_{E_{8}}(A_{1}^{2} ∗ A_{2}, A_{2}, A_{1}^{2}) = 9000, N_{E_{8}}(A_{1}^{4}, A_{2}, A_{1}^{2}) = 2250, N_{E_{8}}(D_{4}, A_{1}^{2}, A_{1}^{2}) = 1800, N_{E_{8}}(A_{4}, A_{1}^{2}, A_{1}^{2}) = 8640, N_{E_{8}}(A_{1} ∗ A_{3}, A_{1}^{2}, A_{1}^{2}) = 17550, N_{E_{8}}(A_{2}^{2}, A_{1}^{2}, A_{1}^{2}) = 5175, N_{E_{8}}(A_{1}^{2} ∗ A_{2}, A_{1}^{2}, A_{1}^{2}) = 13500, N_{E_{8}}(A_{1}^{4}, A_{1}^{2}, A_{1}^{2}) = 3375, N_{E_{8}}(D_{4}, A_{2}, A_{1}, A_{1}) = 1875, N_{E_{8}}(A_{4}, A_{2}, A_{1}, A_{1}) = 9450, N_{E_{8}}(A_{1} ∗ A_{3}, A_{2}, A_{1}, A_{1}) = 27000, N_{E_{8}}(A_{2}^{2}, A_{2}, A_{1}, A_{1}) = 9750, N_{E_{8}}(A_{1}^{2} ∗ A_{2}, A_{2}, A_{1}, A_{1}) = 31500, N_{E_{8}}(A_{1}^{4}, A_{2}, A_{1}, A_{1}) = 7875, N_{E_{8}}(D_{4}, A_{1}^{2}, A_{1}, A_{1}) = 5625, N_{E_{8}}(A_{4}, A_{1}^{2}, A_{1}, A_{1}) = 26325, N_{E_{8}}(A_{1} ∗ A_{3}, A_{1}^{2}, A_{1}, A_{1}) = 60750, N_{E_{8}}(A_{2}^{2}, A_{1}^{2}, A_{1}, A_{1}) = 19125, N_{E_{8}}(A_{1}^{2} ∗ A_{2}, A_{1}^{2}, A_{1}, A_{1}) = 54000, N_{E_{8}}(A_{1}^{4}, A_{1}^{2}, A_{1}, A_{1}) = 13500, N_{E_{8}}(D_{4}, A_{1}, A_{1}, A_{1}, A_{1}) = 16875, N_{E_{8}}(A_{4}, A_{1}, A_{1}, A_{1}, A_{1}) = 81000, N_{E_{8}}(A_{1} ∗ A_{3}, A_{1}, A_{1}, A_{1}, A_{1}) = 202500, N_{E_{8}}(A_{2}^{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 67500, N_{E_{8}}(A_{1}^{2} ∗ A_{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 202500, N_{E_{8}}(A_{1}^{4}, A_{1}, A_{1}, A_{1}, A_{1}) = 50625, N_{E_{8}}(A_{3}, A_{3}, A_{2}) = 1350, N_{E_{8}}(A_{3}, A_{1} ∗ A_{2}, A_{2}) = 5175, N_{E_{8}}(A_{3}, A_{1}^{3}, A_{2}) = 3825, N_{E_{8}}(A_{1} ∗ A_{2}, A_{1} ∗ A_{2}, A_{2}) = 15000, N_{E_{8}}(A_{1} ∗ A_{2}, A_{1}^{3}, A_{2}) = 9825, N_{E_{8}}(A_{1}^{3}, A_{1}^{3}, A_{2}) = 6000, N_{E_{8}}(A_{3}, A_{3}, A_{1}^{2}) = 4050, N_{E_{8}}(A_{3}, A_{1} ∗ A_{2}, A_{1}^{2}) = 13500, N_{E_{8}}(A_{3}, A_{1}^{3}, A_{1}^{2}) = 9450, N_{E_{8}}(A_{1} ∗ A_{2}, A_{1} ∗ A_{2}, A_{1}^{2}) = 30825, N_{E_{8}}(A_{1} ∗ A_{2}, A_{1}^{3}, A_{1}^{2}) = 17325, N_{E_{8}}(A_{1}^{3}, A_{1}^{3}, A_{1}^{2}) = 7875, N_{E_{8}}(A_{3}, A_{3}, A_{1}, A_{1}) = 12150, N_{E_{8}}(A_{3}, A_{1} ∗ A_{2}, A_{1}, A_{1}) = 42525, N_{E_{8}}(A_{3}, A_{1}^{3}, A_{1}, A_{1}) = 30375, N_{E_{8}}(A_{1} ∗ A_{2}, A_{1} ∗ A_{2}, A_{1}, A_{1}) = 106650, N_{E_{8}}(A_{1} ∗ A_{2}, A_{1}^{3}, A_{1}, A_{1}) = 64125, N_{E_{8}}(A_{1}^{3}, A_{1}^{3}, A_{1}, A_{1}) = 33750, N_{E_{8}}(A_{3}, A_{2}, A_{2}, A_{1}) = 10575, N_{E_{8}}(A_{3}, A_{2}, A_{1}^{2}, A_{1}) = 29700, N_{E_{8}}(A_{3}, A_{1}^{2}, A_{1}^{2}, A_{1}) = 76950, N_{E_{8}}(A_{1} ∗ A_{2}, A_{2}, A_{2}, A_{1}) = 35700, N_{E_{8}}(A_{1} ∗ A_{2}, A_{2}, A_{1}^{2}, A_{1}) = 84825, N_{E_{8}}(A_{1} ∗ A_{2}, A_{1}^{2}, A_{1}^{2}, A_{1}) = 171450, N_{E_{8}}(A_{1}^{3}, A_{2}, A_{2}, A_{1}) = 25125, N_{E_{8}}(A_{1}^{3}, A_{2}, A_{1}^{2}, A_{1}) = 55125, N_{E_{8}}(A_{1}^{3}, A_{1}^{2}, A_{1}^{2}, A_{1}) = 94500, N_{E_{8}}(A_{3}, A_{2}, A_{1}, A_{1}, A_{1}) = 91125, N_{E_{8}}(A_{3}, A_{1}^{2}, A_{1}, A_{1}, A_{1}) = 243000, N_{E_{8}}(A_{1} ∗ A_{2}, A_{2}, A_{1}, A_{1}, A_{1}) = 276750, N_{E_{8}}(A_{1} ∗ A_{2}, A_{1}^{2}, A_{1}, A_{1}, A_{1}) = 597375, N_{E_{8}}(A_{1}^{3}, A_{2}, A_{1}, A_{1}, A_{1}) = 185625, N_{E_{8}}(A_{1}^{3}, A_{1}^{2}, A_{1}, A_{1}, A_{1}) = 354375, N_{E_{8}}(A_{3}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 759375, N_{E_{8}}(A_{1} ∗ A_{2}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 2025000, N_{E_{8}}(A_{1}^{3}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 1265625, N_{E_{8}}(A_{2}, A_{2}, A_{2}, A_{2}) = 9350, N_{E_{8}}(A_{2}, A_{2}, A_{2}, A_{1}^{2}) = 24975, N_{E_{8}}(A_{2}, A_{2}, A_{1}^{2}, A_{1}^{2}) = 64350, N_{E_{8}}(A_{2}, A_{1}^{2}, A_{1}^{2}, A_{1}^{2}) = 143100, N_{E_{8}}(A_{1}^{2}, A_{1}^{2}, A_{1}^{2}, A_{1}^{2}) = 261225, N_{E_{8}}(A_{2}, A_{2}, A_{2}, A_{1}, A_{1}) = 78000, N_{E_{8}}(A_{2}, A_{2}, A_{1}^{2}, A_{1}, A_{1}) = 203625, N_{E_{8}}(A_{2}, A_{1}^{2}, A_{1}^{2}, A_{1}, A_{1}) = 479250, N_{E_{8}}(A_{1}^{2}, A_{1}^{2}, A_{1}^{2}, A_{1}, A_{1}) = 951750, N_{E_{8}}(A_{2}, A_{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 641250, N_{E_{8}}(A_{2}, A_{1}^{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 1569375, N_{E_{8}}(A_{1}^{2}, A_{1}^{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 3341250, N_{E_{8}}(A_{2}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 5062500, N_{E_{8}}(A_{1}^{2}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 11390625, N_{E_{8}}(A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 37968750, plus the assignments implied by (4.1) and (4.2), all other numbers N_{E_{8}}(T_{1}, …, T_{d}) being zero.

Finally, we substitute the values found for the decomposition numbers and the formulae for the characteristic polynomials from (5.2) in (3.1), and we obtain

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

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

+ \frac{5}{48} m^{2}(15m − 8)(5m − 1)(3m − 1)(5m − 2)(225m^{2} − 90m − 13)x^{8}y^{6}

24 C. Krattenthaler

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

+ \frac{1}{32} m^{2}(5m + 1)(5m − 1)(84375m^{4} − 12375m^{2} + 436)x^{8}y^{4}

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

+ \frac{5}{48} m^{2}(3m + 1)(5m + 1)(5m + 2)(15m + 8)(225m^{2} + 90m − 13)x^{8}y^{2}

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

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

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

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

+ \frac{375}{8} m^{2}(5m − 1)(5m − 2)(3m − 1)(45m^{2} − 12m − 2)x^{7}y^{5}

− \frac{15}{8} m^{2}(5m + 1)(5m − 1)(5625m^{3} − 2250m^{2} − 75m + 74)x^{7}y^{4}

+ \frac{15}{8} m^{2}(5m − 1)(5m + 1)(5625m^{3} + 2250m^{2} − 75m − 74)x^{7}y^{3}

− \frac{375}{8} m^{2}(3m + 1)(5m + 1)(5m + 2)(45m^{2} + 12m − 2)x^{7}y^{2}

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

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

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

− \frac{375}{8} m^{2}(39m − 16)(5m − 1)(5m − 2)(3m − 1)x^{6}y^{5}

+ \frac{5}{16} m^{2}(5m − 1)(219375m^{3} − 103500m^{2} + 3675m + 2342)x^{6}y^{4}

− \frac{75}{4} m^{2}(5m − 1)(5m + 1)(975m^{2} − 32)x^{6}y^{3}

+ \frac{5}{16} m^{2}(5m + 1)(219375m^{3} + 103500m^{2} + 3675m − 2342)x^{6}y^{2}

− \frac{375}{8} m^{2}(3m + 1)(5m + 1)(5m + 2)(39m + 16)x^{6}y

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

− 15m^{2}(5m − 1)(2250m^{2} − 1395m + 218)x^{5}y^{4} + 75m^{2}(5m − 1)(900m^{2} − 66m − 23)x^{5}y^{3} − 75m^{2}(5m + 1)(900m^{2} + 66m − 23)x^{5}y^{2} + 15m^{2}(5m + 1)(2250m^{2} + 1395m + 218)x^{5}y

− 15m(3m + 1)(5m + 1)(5m + 2)(30m + 13)x^{5} + \frac{1}{2} m(5m − 1)(10350m^{2} − 6675m + 1084)x^{4}y^{4}

− 15m^{2}(1380m − 307)(5m − 1)x^{4}y^{3} + 5m^{2}(31050m^{2} − 577)x^{4}y^{2} − 15m^{2}(5m + 1)(1380m + 307)x^{4}y

+ \frac{1}{2} m(5m + 1)(10350m^{2} + 6675m + 1084)x^{4} + 45m(45m − 11)(5m − 1)x^{3}y^{3} − 1125m^{2}(27m − 4)x^{3}y^{2}

+ 1125m^{2}(27m + 4)x^{3}y − 45m(5m + 1)(45m + 11)x^{3} + \frac{35}{2} m(105m − 17)x^{2}y^{2} − 3675m^{2}x^{2}y

+ \frac{35}{2} m(105m + 17)x^{2} + 120mxy − 120mx + 1. (7.24)

8. The F = M Conjecture. In this section we describe briefly the F = M Conjecture of Armstrong [2] predicting a surprising relation between the M-triangle of the m-divisible partitions poset and the F -triangle of the generalised cluster complex of Fomin and Reading [13], we review the progress from [17], and we explain that our results from Sections 6 and 7 provide proofs of the F = M Conjecture for E_{7} and E_{8}. If we put this together with the results from [17], then it remains only the D_{n} case of the conjecture which is not completely proven.

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 [13, 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}.  (8.1)

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

The generalised version of Chapoton’s (ex-)conjecture [11, Conjecture 1], due to Armstrong [2, Conjecture 5.3.2], 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}) .  (8.2)

Equivalently,

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

It is easy to see (cf. [17, Sec. 8]) that it is enough to prove the conjecture for the irreducible root systems. In [17], this has been done for the root systems of type A_{n}, B_{n}, I_{2}(a), H_{3}, H_{4}, F_{4}, and E_{6}. The paper contains also a partial proof for the root system of type D_{n}. Given that we computed the M-triangle of the m-divisible non-crossing partitions poset for E_{7} and E_{8} and that the F -triangle of the generalised cluster complex has been computed in [17] for all irreducible root systems (thus, in particular, for E_{7} and E_{8}), the verification of (8.3) for E_{7} and E_{8} is pure routine on a computer algebra system.

If we combine these observations with the proof of the m = 1 case of the F = M Conjecture by Athanasiadis [3] (an alternative case-by-case proof is provided by the results in [17] and in the present paper), then we obtain the following theorem.

Theorem FM. Conjecture FM is true with the possible exception of root systems containing a copy of the root system D_{k} for some k. If m = 1, Conjecture FM is true unconditionally.

9. A reciprocity phenomenon. By staring at the explicit expressions for the Mtriangles of the m-divisible non-crossing partitions posets for the irreducible root systems which we computed in [17] and in the present paper (in the D_{n} case, this expression is only conjectural), one observes a curious reciprocity relation between the original Mtriangle and the M-triangle with m replaced by −m. From the outset, the M-triangle with −m in place of m has no combinatorial meaning since there is no meaning for “(−m)- divisible non-crossing partitions.” Nevertheless, it would be interesting to find an intrinsic explanation of the phenomenon given in the theorem below. In any case, examples of situations where combinatorial meaning was given to non-combinatorial parameters are not so uncommon; for example, there exist reciprocity theorems for P -partitions and the Ehrhart quasi-polynomial of polytopes (cf. [23, Theorems 4.5.7, 4.6.26, Cor. 4.5.15]), which have their explanation in Stanley’s reciprocity theorem for linear homogeneous diophantine equations [23, Theorem 4.6.14], and there exist reciprocity theorems for monomer-dimer coverings of rectangles (cf. [1, 19, 22]).

Theorem 8. For any finite root system of rank n, except possibly for those which contain a copy of D_{k} for some k, we have

y^{n}M_{Φ}^{−m}(xy, 1/y) = M_{Φ}^{m}(x, y).  (9.1)

If the (conjectural) expression for M_{D_{n}}^{m}(x, y) in [17, Sec. 11, Prop. D] is correct, then (9.1) is true without any exceptions. Phrased differently, if the F = M Conjecture is true, then (9.1) is true unconditionally.

Formula (9.1) contains a reciprocity between numbers of maximal simplices in the generalised cluster complex Δ^{m}(Φ), observed by Fomin and Reading [13, Eq. (11.2) and Prop. 11.4], and revealed as an instance of Ehrhart reciprocity by Athanasiadis and Tzanaki [5, Sec. 7], as a special case. (Again, for root systems containing a copy of D_{k} for some k, this is a conditional statement.) To see this, we first translate (9.1) into a reciprocity relation for the F -triangle F_{Φ}^{m}(x, y) via (8.2):

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

If we compare coefficients of x^{n}y^{0} on both sides of this equation, then we obtain the relation

f_{n,0}(Φ, m) = ∑_{k=0}^{n}(−1)^{k}f_{k}(Φ, −m),  (9.3)

where f_{k}(Φ, m) = ∑_{l=0}^{k} f_{l,k−l}(Φ, m) is the total number of faces in Δ^{m}(Φ) containing exactly k roots (positive or negative). In the notation of [5, 13], we have f_{n,0}(Φ, m) = N^{+}(Φ, m), and by [13, Eq. (10.2)] the sum on the right-hand side of (9.3) is equal to (−1)^{n}f_{n}(Φ, −m − 1) ((−1)^{n}N(Φ, −m − 1) in the notation of [13]). Thus, we arrive at the reciprocity relation

N^{+}(Φ, m) = (−1)^{n}N(Φ, −m − 1),

which is exactly [13, Eq. (11.2)].

The combinatorial significance of (9.2) in general is less clear. Comparison of coefficients of x^{k}y^{l} on both sides leads to the identity

f_{k,l}(Φ, m) = ∑_{r,s≥0}(−1)^{r+s+l}\binom{n − r − s}{k + l − r − s}\binom{s}{l}f_{r,s}(Φ, −m).  (9.4)

10. A formula for the A_{n} decomposition numbers. Since the decomposition numbers N_{Φ}(T_{1}, T_{2}, …, T_{d}) carry so much information on the enumerative structure of (ordinary and generalised) non-crossing partitions (see, for example, Propositions 1 and 3), it would be of intrinsic interest to compute these numbers also for the classical root systems. As a matter of fact, the type A_{n} decomposition numbers of full rank are known due to a result of Goulden and Jackson [15, Theorem 3.2] on the minimal factorization of a long cycle. (The condition on the sum l(α_{1}) + l(α_{2}) + ⋯ + l(α_{m}) is misstated throughout the latter paper. It should be replaced by l(α_{1}) + l(α_{2}) + ⋯ + l(α_{m}) = (m − 1)n + 1.) In the following theorem, we state this result in our language.

Theorem 9. Let Φ = A_{n}, and let T_{1}, T_{2}, …, T_{d} be types with rk T_{1}+rk T_{2}+⋯+rk T_{d} = n, where

T_{i} = A_{1}^{m_{1}^{(i)}} ∗ A_{2}^{m_{2}^{(i)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(i)}}, i = 1, 2, …, d.

Then

N_{A_{n}}(T_{1}, T_{2}, …, T_{d}) = (n + 1)^{d−1} ∏_{i=1}^{d} \frac{1}{n − rk T_{i} + 1}\binom{n − rk T_{i} + 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}},  (9.5)

where the multinomial coefficient is defined by

\binom{M}{m_{1}, m_{2}, …, m_{n}} = \frac{M!}{m_{1}! m_{2}! ⋯ m_{n}! (M − m_{1} − m_{2} − ⋯ − m_{n})!}.

This result allows one to derive a compact formula for all type A_{n} decomposition numbers.

Theorem 10. Let Φ = A_{n}, and let the types T_{1}, T_{2}, …, T_{d} be given, where

T_{i} = A_{1}^{m_{1}^{(i)}} ∗ A_{2}^{m_{2}^{(i)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(i)}}, i = 1, 2, …, d.

Then

N_{A_{n}}(T_{1}, T_{2}, …, T_{d}) = (n + 1)^{d−1}\binom{n + 1}{rk T_{1} + rk T_{2} + ⋯ + rk T_{d} + 1}

× ∏_{i=1}^{d} \frac{1}{n − rk T_{i} + 1}\binom{n − rk T_{i} + 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}. (9.6)

Proof. If we write r for n − rk T_{1} − rk T_{2} − ⋯ − rk T_{d}, then the relation (4.2) becomes

N_{A_{n}}(T_{1}, T_{2}, …, T_{d}) = ∑_{T:rk T =r}N_{A_{n}}(T_{1}, T_{2}, …, T_{d}, T).

Upon letting T = A_{1}^{m_{1}} ∗ A_{2}^{m_{2}} ∗ ⋯ ∗ A_{n}^{m_{n}}, substitution of (9.5) in the above equation yields

N_{A_{n}}(T_{1}, T_{2}, …, T_{d}) = ∑_{m_{1}+2m_{2}+···+nm_{n}=r}(n + 1)^{d} \frac{1}{n − r + 1}\binom{n − r + 1}{m_{1}, m_{2}, …, m_{n}}

· ∏_{i=1}^{d} \frac{1}{n − rk T_{i} + 1}\binom{n − rk T_{i} + 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}.

Now, by comparison of coefficients of z^{r} on both sides of

(1 + z + z^{2} + z^{3} + ⋯)^{M} = (1 − z)^{−M},

we infer

∑_{m_{1}+2m_{2}+···+rm_{r}=r} \binom{M}{m_{1}, m_{2}, …, m_{r}} = \binom{M + r − 1}{r}.

If we use this identity with M = n − r + 1, we obtain our claim after little simplification. □

The reader should note that formula (9.6) generalises Kreweras’ formula [18, Theorem 4] for the number of non-crossing partitions of n+1 with given block sizes, to which it reduces for d = 1.

Appendix: The decomposition numbers for types A_{n} and D_{n} for small n, and for E_{6}. In this appendix we list the full rank decomposition numbers, that is, the decomposition numbers N_{Φ}(T_{1}, T_{2}, …, T_{d}), where rk T_{1} + rk T_{2} + ⋯ + rk T_{d} = rk Φ, for Φ = A_{1}, A_{2}, A_{3}, A_{4}, A_{5}, A_{6}, A_{7}, D_{4}, D_{5}, D_{6}, D_{7}, E_{6}. These numbers are required for setting up the system of equations (4.3) in Sections 6 and 7. We do not list decomposition numbers which are zero. It was explained in Section 4 how to compute these numbers by setting up a system of linear equations for them. Whenever, aside from the listing of the numbers, there is no further comment, then the computation of the decomposition numbers is either trivial (for A_{1} and A_{2}), or the equations in Propositions 2 and 3, together with the assignments from Propositions 4 and 6 determine them already uniquely. If not, then we mention the additional assignments, respectively considerations, which are required for the computation.^{6} Clearly, the decomposition numbers for A_{n}, n = 1, 2, …, can be computed directly from Theorem 9.

The decomposition numbers for A_{1}. N_{A_{1}}(A_{1}) = 1.

The decomposition numbers for A_{2}. N_{A_{2}}(A_{2}) = 1, N_{A_{2}}(A_{1}, A_{1}) = 3.

6The Mathematica inputs for the computations are available at http://www.mat.univie.ac.at/~kratt/artikel/cluster2.html.

The M-triangle of generalised non-crossing partitions for the types E_{7} and E_{8} 29

The decomposition numbers for A_{3}. N_{A_{3}}(A_{3}) = 1, N_{A_{3}}(A_{2}, A_{1}) = 4, N_{A_{3}}(A_{1}^{2}, A_{1}) = 2, N_{A_{3}}(A_{1}, A_{1}, A_{1}) = 16.

The decomposition numbers for A_{4}. N_{A_{4}}(A_{4}) = 1, N_{A_{4}}(A_{3}, A_{1}) = 5, N_{A_{4}}(A_{1}∗A_{2}, A_{1}) = 5, N_{A_{4}}(A_{2}, A_{2}) = 5, N_{A_{4}}(A_{2}, A_{1}^{2}) = 5, N_{A_{4}}(A_{1}^{2}, A_{1}^{2}) = 5, N_{A_{4}}(A_{2}, A_{1}, A_{1}) = 25, N_{A_{4}}(A_{1}^{2}, A_{1}, A_{1}) = 25, N_{A_{4}}(A_{1}, A_{1}, A_{1}, A_{1}) = 125.

The decomposition numbers for A_{5}. N_{A_{5}}(A_{5}) = 1, N_{A_{5}}(A_{4}, A_{1}) = 6, N_{A_{5}}(A_{1}∗A_{3}, A_{1}) = 6, N_{A_{5}}(A_{2}^{2}, A_{1}) = 3, N_{A_{5}}(A_{3}, A_{2}) = 6, N_{A_{5}}(A_{1} ∗ A_{2}, A_{2}) = 12, N_{A_{5}}(A_{1}^{3}, A_{2}) = 2, N_{A_{5}}(A_{3}, A_{1}^{2}) = 9, N_{A_{5}}(A_{1} ∗ A_{2}, A_{1}^{2}) = 18, N_{A_{5}}(A_{1}^{3}, A_{1}^{2}) = 3, N_{A_{5}}(A_{3}, A_{1}, A_{1}) = 36, N_{A_{5}}(A_{1} ∗ A_{2}, A_{1}, A_{1}) = 72, N_{A_{5}}(A_{1}^{3}, A_{1}, A_{1}) = 12, N_{A_{5}}(A_{2}, A_{2}, A_{1}) = 36, N_{A_{5}}(A_{2}, A_{1}^{2}, A_{1}) = 54, N_{A_{5}}(A_{1}^{2}, A_{1}^{2}, A_{1}) = 81, N_{A_{5}}(A_{2}, A_{1}, A_{1}, A_{1}) = 216, N_{A_{5}}(A_{1}^{2}, A_{1}, A_{1}, A_{1}) = 324, N_{A_{5}}(A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 1296.

The decomposition numbers for A_{6}. N_{A_{6}}(A_{6}) = 1, N_{A_{6}}(A_{5}, A_{1}) = 7, N_{A_{6}}(A_{1}∗A_{4}, A_{1}) = 7, N_{A_{6}}(A_{2} ∗ A_{3}, A_{1}) = 7, N_{A_{6}}(A_{4}, A_{2}) = 7, N_{A_{6}}(A_{1} ∗ A_{3}, A_{2}) = 14, N_{A_{6}}(A_{2}^{2}, A_{2}) = 7, N_{A_{6}}(A_{1}^{2} ∗ A_{2}, A_{2}) = 7, N_{A_{6}}(A_{4}, A_{1}^{2}) = 14, N_{A_{6}}(A_{1} ∗ A_{3}, A_{1}^{2}) = 28, N_{A_{6}}(A_{2}^{2}, A_{1}^{2}) = 14, N_{A_{6}}(A_{1}^{2} ∗ A_{2}, A_{1}^{2}) = 14, N_{A_{6}}(A_{3}, A_{3}) = 7, N_{A_{6}}(A_{3}, A_{1} ∗ A_{2}) = 21, N_{A_{6}}(A_{3}, A_{1}^{3}) = 7, N_{A_{6}}(A_{1} ∗ A_{2}, A_{1} ∗ A_{2}) = 63, N_{A_{6}}(A_{1} ∗ A_{2}, A_{1}^{3}) = 21, N_{A_{6}}(A_{1}^{3}, A_{1}^{3}) = 7, N_{A_{6}}(A_{4}, A_{1}, A_{1}) = 49, N_{A_{6}}(A_{1} ∗ A_{3}, A_{1}, A_{1}) = 98, N_{A_{6}}(A_{2}^{2}, A_{1}, A_{1}) = 49, N_{A_{6}}(A_{1}^{2} ∗ A_{2}, A_{1}, A_{1}) = 49, N_{A_{6}}(A_{3}, A_{2}, A_{1}) = 49, N_{A_{6}}(A_{3}, A_{1}^{2}, A_{1}) = 98, N_{A_{6}}(A_{1} ∗ A_{2}, A_{2}, A_{1}) = 147, N_{A_{6}}(A_{1} ∗ A_{2}, A_{1}^{2}, A_{1}) = 294, N_{A_{6}}(A_{1}^{3}, A_{2}, A_{1}) = 49, N_{A_{6}}(A_{1}^{3}, A_{1}^{2}, A_{1}) = 98, N_{A_{6}}(A_{3}, A_{1}, A_{1}, A_{1}) = 343, N_{A_{6}}(A_{1} ∗ A_{2}, A_{1}, A_{1}, A_{1}) = 1029, N_{A_{6}}(A_{1}^{3}, A_{1}, A_{1}, A_{1}) = 343, N_{A_{6}}(A_{2}, A_{2}, A_{2}) = 49, N_{A_{6}}(A_{2}, A_{2}, A_{1}^{2}) = 98, N_{A_{6}}(A_{2}, A_{1}^{2}, A_{1}^{2}) = 196, N_{A_{6}}(A_{1}^{2}, A_{1}^{2}, A_{1}^{2}) = 392, N_{A_{6}}(A_{2}, A_{2}, A_{1}, A_{1}) = 343, N_{A_{6}}(A_{2}, A_{1}^{2}, A_{1}, A_{1}) = 686, N_{A_{6}}(A_{1}^{2}, A_{1}^{2}, A_{1}, A_{1}) = 1372, N_{A_{6}}(A_{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 2401, N_{A_{6}}(A_{1}^{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 4802, N_{A_{6}}(A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 16807.

The decomposition numbers for A_{7}. N_{A_{7}}(A_{7}) = 1, N_{A_{7}}(A_{6}, A_{1}) = 8, N_{A_{7}}(A_{1}∗A_{5}, A_{1}) = 8, N_{A_{7}}(A_{2} ∗ A_{4}, A_{1}) = 8, N_{A_{7}}(A_{3}^{2}, A_{1}) = 4, N_{A_{7}}(A_{5}, A_{2}) = 8, N_{A_{7}}(A_{1} ∗ A_{4}, A_{2}) = 16, N_{A_{7}}(A_{2} ∗ A_{3}, A_{2}) = 16, N_{A_{7}}(A_{1}^{2} ∗ A_{3}, A_{2}) = 8, N_{A_{7}}(A_{1} ∗ A_{2}^{2}, A_{2}) = 8, N_{A_{7}}(A_{5}, A_{1}^{2}) = 20, N_{A_{7}}(A_{1} ∗A_{4}, A_{1}^{2}) = 40, N_{A_{7}}(A_{2} ∗A_{3}, A_{1}^{2}) = 40, N_{A_{7}}(A_{1}^{2} ∗A_{3}, A_{1}^{2}) = 20, N_{A_{7}}(A_{1} ∗A_{2}^{2}, A_{1}^{2}) = 20, N_{A_{7}}(A_{5}, A_{1}, A_{1}) = 64, N_{A_{7}}(A_{1} ∗ A_{4}, A_{1}, A_{1}) = 128, N_{A_{7}}(A_{2} ∗ A_{3}, A_{1}, A_{1}) = 128, N_{A_{7}}(A_{1}^{2} ∗ A_{3}, A_{1}, A_{1}) = 64, N_{A_{7}}(A_{1} ∗ A_{2}^{2}, A_{1}, A_{1}) = 64, N_{A_{7}}(A_{4}, A_{3}) = 8, N_{A_{7}}(A_{1} ∗ A_{3}, A_{3}) = 24, N_{A_{7}}(A_{2}^{2}, A_{3}) = 12, N_{A_{7}}(A_{1}^{2} ∗ A_{2}, A_{3}) = 24, N_{A_{7}}(A_{1}^{4}, A_{3}) = 2, N_{A_{7}}(A_{4}, A_{1} ∗ A_{2}) = 32, N_{A_{7}}(A_{1} ∗ A_{3}, A_{1} ∗ A_{2}) = 96, N_{A_{7}}(A_{2}^{2}, A_{1} ∗ A_{2}) = 48, N_{A_{7}}(A_{1}^{2} ∗ A_{2}, A_{1} ∗ A_{2}) = 96, N_{A_{7}}(A_{1}^{4}, A_{1} ∗ A_{2}) = 8, N_{A_{7}}(A_{4}, A_{1}^{3}) = 16, N_{A_{7}}(A_{1} ∗ A_{3}, A_{1}^{3}) = 48, N_{A_{7}}(A_{2}^{2}, A_{1}^{3}) = 24, N_{A_{7}}(A_{1}^{2} ∗ A_{2}, A_{1}^{3}) = 48, N_{A_{7}}(A_{1}^{4}, A_{1}^{3}) = 4, N_{A_{7}}(A_{4}, A_{2}, A_{1}) = 64, N_{A_{7}}(A_{1} ∗ A_{3}, A_{2}, A_{1}) = 192, N_{A_{7}}(A_{2}^{2}, A_{2}, A_{1}) = 96, N_{A_{7}}(A_{1}^{2} ∗ A_{2}, A_{2}, A_{1}) = 192, N_{A_{7}}(A_{1}^{4}, A_{2}, A_{1}) = 16, N_{A_{7}}(A_{4}, A_{1}^{2}, A_{1}) = 160, N_{A_{7}}(A_{1}∗A_{3}, A_{1}^{2}, A_{1}) = 480, N_{A_{7}}(A_{2}^{2}, A_{1}^{2}, A_{1}) = 240, N_{A_{7}}(A_{1}^{2}∗A_{2}, A_{1}^{2}, A_{1}) = 480, N_{A_{7}}(A_{1}^{4}, A_{1}^{2}, A_{1}) = 40, N_{A_{7}}(A_{4}, A_{1}, A_{1}, A_{1}) = 512, N_{A_{7}}(A_{1} ∗ A_{3}, A_{1}, A_{1}, A_{1}) = 1536, N_{A_{7}}(A_{2}^{2}, A_{1}, A_{1}, A_{1}) = 768, N_{A_{7}}(A_{1}^{2} ∗ A_{2}, A_{1}, A_{1}, A_{1}) = 1536, N_{A_{7}}(A_{1}^{4}, A_{1}, A_{1}, A_{1}) = 128, N_{A_{7}}(A_{3}, A_{3}, A_{1}) = 64, N_{A_{7}}(A_{3}, A_{1} ∗ A_{2}, A_{1}) = 256, N_{A_{7}}(A_{3}, A_{1}^{3}, A_{1}) = 128, N_{A_{7}}(A_{1} ∗ A_{2}, A_{1} ∗ A_{2}, A_{1}) = 1024, N_{A_{7}}(A_{1} ∗ A_{2}, A_{1}^{3}, A_{1}) = 512, N_{A_{7}}(A_{1}^{3}, A_{1}^{3}, A_{1}) = 256, N_{A_{7}}(A_{3}, A_{2}, A_{2}) = 64, N_{A_{7}}(A_{3}, A_{2}, A_{1}^{2}) = 160, N_{A_{7}}(A_{3}, A_{1}^{2}, A_{1}^{2}) = 400, N_{A_{7}}(A_{1} ∗ A_{2}, A_{2}, A_{2}) = 256, N_{A_{7}}(A_{1} ∗ A_{2}, A_{2}, A_{1}^{2}) = 640, N_{A_{7}}(A_{1} ∗ A_{2}, A_{1}^{2}, A_{1}^{2}) = 1600, N_{A_{7}}(A_{1}^{3}, A_{2}, A_{2}) = 128, N_{A_{7}}(A_{1}^{3}, A_{2}, A_{1}^{2}) = 320, N_{A_{7}}(A_{1}^{3}, A_{1}^{2}, A_{1}^{2}) = 800, N_{A_{7}}(A_{3}, A_{2}, A_{1}, A_{1}) = 512, N_{A_{7}}(A_{3}, A_{1}^{2}, A_{1}, A_{1}) = 1280, N_{A_{7}}(A_{1} ∗ A_{2}, A_{2}, A_{1}, A_{1}) = 2048, N_{A_{7}}(A_{1} ∗ A_{2}, A_{1}^{2}, A_{1}, A_{1}) = 5120, N_{A_{7}}(A_{1}^{3}, A_{2}, A_{1}, A_{1}) = 1024, N_{A_{7}}(A_{1}^{3}, A_{1}^{2}, A_{1}, A_{1}) = 2560, N_{A_{7}}(A_{3}, A_{1}, A_{1}, A_{1}, A_{1}) = 4096, N_{A_{7}}(A_{1} ∗ A_{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 16384, N_{A_{7}}(A_{1}^{3}, A_{1}, A_{1}, A_{1}, A_{1}) = 8192, N_{A_{7}}(A_{2}, A_{2}, A_{2}, A_{1}) = 512, N_{A_{7}}(A_{2}, A_{2}, A_{1}^{2}, A_{1}) = 1280, N_{A_{7}}(A_{2}, A_{1}^{2}, A_{1}^{2}, A_{1}) = 3200, N_{A_{7}}(A_{1}^{2}, A_{1}^{2}, A_{1}^{2}, A_{1}) = 8000, N_{A_{7}}(A_{2}, A_{2}, A_{1}, A_{1}, A_{1}) = 4096, N_{A_{7}}(A_{2}, A_{1}^{2}, A_{1}, A_{1}, A_{1}) = 10240, N_{A_{7}}(A_{1}^{2}, A_{1}^{2}, A_{1}, A_{1}, A_{1}) = 25600, N_{A_{7}}(A_{2}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 32768, N_{A_{7}}(A_{1}^{2}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 81920, N_{A_{7}}(A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 262144.

The decomposition numbers for D_{4}. N_{D_{4}}(D_{4}) = 1, N_{D_{4}}(A_{3}, A_{1}) = 9, N_{D_{4}}(A_{1}^{3}, A_{1}) = 3, N_{D_{4}}(A_{2}, A_{2}) = 6, N_{D_{4}}(A_{2}, A_{1}^{2}) = 9, N_{D_{4}}(A_{2}, A_{1}, A_{1}) = 36, N_{D_{4}}(A_{1}^{2}, A_{1}, A_{1}) = 27, N_{D_{4}}(A_{1}, A_{1}, A_{1}, A_{1}) = 162.

The decomposition numbers for D_{5}. N_{D_{5}}(D_{5}) = 1, N_{D_{5}}(D_{4}, A_{1}) = 4, N_{D_{5}}(A_{4}, A_{1}) = 8, N_{D_{5}}(A_{1} ∗ A_{3}, A_{1}) = 4, N_{D_{5}}(A_{1}^{2} ∗ A_{2}, A_{1}) = 4, N_{D_{5}}(A_{3}, A_{2}) = 12, N_{D_{5}}(A_{1} ∗ A_{2}, A_{2}) = 16, N_{D_{5}}(A_{1}^{3}, A_{2}) = 8, N_{D_{5}}(A_{3}, A_{1}^{2}) = 22, N_{D_{5}}(A_{1} ∗ A_{2}, A_{1}^{2}) = 8, N_{D_{5}}(A_{1}^{3}, A_{1}^{2}) = 4, N_{D_{5}}(A_{3}, A_{1}, A_{1}) = 80, N_{D_{5}}(A_{1} ∗ A_{2}, A_{1}, A_{1}) = 64, N_{D_{5}}(A_{1}^{3}, A_{1}, A_{1}) = 32, N_{D_{5}}(A_{2}, A_{2}, A_{1}) = 64, N_{D_{5}}(A_{2}, A_{1}^{2}, A_{1}) = 96, N_{D_{5}}(A_{1}^{2}, A_{1}^{2}, A_{1}) = 80, N_{D_{5}}(A_{2}, A_{1}, A_{1}, A_{1}) = 384, N_{D_{5}}(A_{1}^{2}, A_{1}, A_{1}, A_{1}) = 448, N_{D_{5}}(A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 2048.

The decomposition numbers for D_{6}. Unfortunately, the solution space of the system of linear equations does not consist of a unique solution but is two-dimensional. Mathematica 5.2 expresses all the decomposition numbers in terms of X = N_{D_{6}}(A_{1}^{3}, A_{1}^{3}) and Y = N_{D_{6}}(A_{1}^{4}, A_{1}^{2}). In the sequel we make use of the two relations

N_{D_{6}}(A_{1}^{2} ∗ A_{2}, A_{1}^{2}) = 25 − \frac{27}{40}X − 3Y,
N_{D_{6}}(A_{3}, A_{3}) = 20 + \frac{9}{100}X.

They imply X ≡ 0 (mod 200), X ≤ 1000/27 < 200, Y ≡ 2 (mod 3), and Y ≤ 25/3 < 9. Hence, we have X = N_{D_{6}}(A_{1}^{3}, A_{1}^{3}) = 0, and the three possibilities Y = 2, 5, 8. To decide which of the three values is the true value, we argue as in Section 6 when we had to decide which of two possible values for N_{E_{7}}(A_{1}^{2} ∗ A_{2}, A_{1}^{3}) was the correct one (see the paragraph after (6.8)). Since Lemma 5 in the case of D_{6} says that the orbits of reflections have all size 5, here the conclusion is that 5 must divide Y = N_{D_{6}}(A_{1}^{4}, A_{1}^{2}). Thus, N_{D_{6}}(A_{1}^{4}, A_{1}^{2}) = 5. If we substitute this in the relations for the decomposition numbers found by Mathematica, then we obtain N_{D_{6}}(D_{6}) = 1, N_{D_{6}}(D_{5}, A_{1}) = 5, N_{D_{6}}(A_{5}, A_{1}) = 10, N_{D_{6}}(A_{1} ∗ D_{4}, A_{1}) = 5, N_{D_{6}}(A_{2} ∗ A_{3}, A_{1}) = 5, N_{D_{6}}(A_{1}^{2} ∗ A_{3}, A_{1}) = 5, N_{D_{6}}(D_{4}, A_{2}) = 5, N_{D_{6}}(A_{4}, A_{2}) = 10, N_{D_{6}}(A_{1} ∗ A_{3}, A_{2}) = 30, N_{D_{6}}(A_{2}^{2}, A_{2}) = 10, N_{D_{6}}(A_{1}^{2} ∗ A_{2}, A_{2}) = 10, N_{D_{6}}(A_{1}^{4}, A_{2}) = 5, N_{D_{6}}(D_{4}, A_{1}^{2}) = 5, N_{D_{6}}(A_{4}, A_{1}^{2}) = 35, N_{D_{6}}(A_{1} ∗ A_{3}, A_{1}^{2}) = 30, N_{D_{6}}(A_{2}^{2}, A_{1}^{2}) = 10, N_{D_{6}}(A_{1}^{2} ∗ A_{2}, A_{1}^{2}) = 10, N_{D_{6}}(A_{1}^{4}, A_{1}^{2}) = 5, N_{D_{6}}(A_{3}, A_{3}) = 20, N_{D_{6}}(A_{3}, A_{1} ∗ A_{2}) = 45, N_{D_{6}}(A_{3}, A_{1}^{3}) = 25, N_{D_{6}}(A_{1} ∗ A_{2}, A_{1} ∗ A_{2}) = 70, N_{D_{6}}(A_{1} ∗ A_{2}, A_{1}^{3}) = 25, N_{D_{6}}(D_{4}, A_{1}, A_{1}) = 25, N_{D_{6}}(A_{4}, A_{1}, A_{1}) = 100, N_{D_{6}}(A_{1} ∗ A_{3}, A_{1}, A_{1}) = 150, N_{D_{6}}(A_{2}^{2}, A_{1}, A_{1}) = 50, N_{D_{6}}(A_{1}^{2} ∗ A_{2}, A_{1}, A_{1}) = 50, N_{D_{6}}(A_{1}^{4}, A_{1}, A_{1}) = 25, N_{D_{6}}(A_{3}, A_{2}, A_{1}) = 125, N_{D_{6}}(A_{3}, A_{1}^{2}, A_{1}) = 250, N_{D_{6}}(A_{1} ∗A_{2}, A_{2}, A_{1}) = 250, N_{D_{6}}(A_{1} ∗A_{2}, A_{1}^{2}, A_{1}) = 375, N_{D_{6}}(A_{1}^{3}, A_{2}, A_{1}) = 125, N_{D_{6}}(A_{1}^{3}, A_{1}^{2}, A_{1}) = 125, N_{D_{6}}(A_{3}, A_{1}, A_{1}, A_{1}) = 875, N_{D_{6}}(A_{1} ∗ A_{2}, A_{1}, A_{1}, A_{1}) = 1500, N_{D_{6}}(A_{1}^{3}, A_{1}, A_{1}, A_{1}) = 625, N_{D_{6}}(A_{2}, A_{2}, A_{2}) = 100, N_{D_{6}}(A_{2}, A_{2}, A_{1}^{2}) = 225, N_{D_{6}}(A_{2}, A_{1}^{2}, A_{1}^{2}) = 350, N_{D_{6}}(A_{1}^{2}, A_{1}^{2}, A_{1}^{2}) = 475, N_{D_{6}}(A_{2}, A_{2}, A_{1}, A_{1}) = 750, N_{D_{6}}(A_{2}, A_{1}^{2}, A_{1}, A_{1}) = 1375, N_{D_{6}}(A_{1}^{2}, A_{1}^{2}, A_{1}, A_{1}) = 2000, N_{D_{6}}(A_{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 5000, N_{D_{6}}(A_{1}^{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 8125, N_{D_{6}}(A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 31250.

The decomposition numbers for D_{7}. In addition to the described equations and assignments, we use also the last assertion in Proposition 2 for the type A_{1}^{5}, that is, N_{D_{7}}(A_{1}^{5}, A_{2}) = N_{D_{7}}(A_{1}^{5}, A_{1}^{2}) = 0. Unfortunately, the solution space of the system of linear equations does not consist of a unique solution but is two-dimensional. Mathematica 5.2 expresses all the decomposition numbers in terms of X = N_{D_{7}}(A_{1}^{4}, A_{1}^{3}) and Y = N_{D_{7}}(A_{1}^{2} ∗ A_{2}, A_{1}^{3}). In the sequel we make use of the two relations

N_{D_{7}}(A_{1}^{4}, A_{1} ∗ A_{2}) = \frac{6}{5}(36 − X),  (A.1)
N_{D_{7}}(A_{1}^{2} ∗ A_{2}, A_{3}) = \frac{3}{10}(Y + 162),  (A.2)
N_{D_{7}}(A_{1} ∗ A_{3}, A_{1}^{3}) = 84 − \frac{1}{3}Y,  (A.3)
N_{D_{7}}(A_{1} ∗ A_{2}^{2}, A_{2}) = \frac{14}{15}(36 − 3X − Y),  (A.4)
N_{D_{7}}(A_{1} ∗ A_{2}^{2}, A_{1}^{2}) = \frac{7}{5}(3X + Y − 36).  (A.5)

Relation (A.1) implies X ≡ 1 (mod 5), while Relations (A.2) and (A.3) imply Y ≡ 18 (mod 30). Since decomposition numbers must be non-negative, Relations (A.4) and (A.5) force 3X + Y to be equal to 36. Hence, we must have X = N_{D_{7}}(A_{1}^{4}, A_{1}^{3}) = 6 and Y = N_{D_{7}}(A_{1}^{2}∗A_{2}, A_{1}^{3}) = 18. If we substitute this in the relations for the decomposition numbers found by Mathematica, then we obtain N_{D_{7}}(D_{7}) = 1, N_{D_{7}}(D_{6}, A_{1}) = 6, N_{D_{7}}(A_{6}, A_{1}) = 12, N_{D_{7}}(A_{1} ∗ D_{5}, A_{1}) = 6, N_{D_{7}}(A_{2} ∗ D_{4}, A_{1}) = 6, N_{D_{7}}(A_{1}^{2} ∗ A_{4}, A_{1}) = 6, N_{D_{7}}(A_{3}^{2}, A_{1}) = 6, N_{D_{7}}(D_{5}, A_{2}) = 6, N_{D_{7}}(A_{5}, A_{2}) = 12, N_{D_{7}}(A_{1} ∗ D_{4}, A_{2}) = 12, N_{D_{7}}(A_{1} ∗ A_{4}, A_{2}) = 24, N_{D_{7}}(A_{2} ∗ A_{3}, A_{2}) = 36, N_{D_{7}}(A_{1}^{2} ∗ A_{3}, A_{2}) = 18, N_{D_{7}}(A_{1}^{3} ∗ A_{2}, A_{2}) = 12, N_{D_{7}}(D_{5}, A_{1}^{2}) = 9, N_{D_{7}}(A_{5}, A_{1}^{2}) = 54, N_{D_{7}}(A_{1} ∗D_{4}, A_{1}^{2}) = 18, N_{D_{7}}(A_{1} ∗A_{4}, A_{1}^{2}) = 36, N_{D_{7}}(A_{2} ∗A_{3}, A_{1}^{2}) = 54, N_{D_{7}}(A_{1}^{2} ∗ A_{3}, A_{1}^{2}) = 27, N_{D_{7}}(A_{1}^{3} ∗ A_{2}, A_{1}^{2}) = 18, N_{D_{7}}(D_{5}, A_{1}, A_{1}) = 36, N_{D_{7}}(A_{5}, A_{1}, A_{1}) = 144, N_{D_{7}}(A_{1} ∗ D_{4}, A_{1}, A_{1}) = 72, N_{D_{7}}(A_{1} ∗ A_{4}, A_{1}, A_{1}) = 144, N_{D_{7}}(A_{2} ∗ A_{3}, A_{1}, A_{1}) = 216, N_{D_{7}}(A_{1}^{2} ∗ A_{3}, A_{1}, A_{1}) = 108, N_{D_{7}}(A_{1}^{3} ∗ A_{2}, A_{1}, A_{1}) = 72, N_{D_{7}}(D_{4}, A_{3}) = 6, N_{D_{7}}(A_{4}, A_{3}) = 18, N_{D_{7}}(A_{1} ∗ A_{3}, A_{3}) = 72, N_{D_{7}}(A_{2}^{2}, A_{3}) = 27, N_{D_{7}}(A_{1}^{2} ∗ A_{2}, A_{3}) = 54, N_{D_{7}}(A_{1}^{4}, A_{3}) = 18, N_{D_{7}}(D_{4}, A_{1} ∗A_{2}) = 12, N_{D_{7}}(A_{4}, A_{1} ∗A_{2}) = 72, N_{D_{7}}(A_{1} ∗A_{3}, A_{1} ∗A_{2}) = 180, N_{D_{7}}(A_{2}^{2}, A_{1} ∗ A_{2}) = 72, N_{D_{7}}(A_{1}^{2} ∗ A_{2}, A_{1} ∗ A_{2}) = 108, N_{D_{7}}(A_{1}^{4}, A_{1} ∗ A_{2}) = 36, N_{D_{7}}(D_{4}, A_{1}^{3}) = 2, N_{D_{7}}(A_{4}, A_{1}^{3}) = 60, N_{D_{7}}(A_{1} ∗ A_{3}, A_{1}^{3}) = 78, N_{D_{7}}(A_{2}^{2}, A_{1}^{3}) = 36, N_{D_{7}}(A_{1}^{2} ∗ A_{2}, A_{1}^{3}) = 18, N_{D_{7}}(A_{1}^{4}, A_{1}^{3}) = 6, N_{D_{7}}(D_{4}, A_{2}, A_{1}) = 36, N_{D_{7}}(D_{4}, A_{1}^{2}, A_{1}) = 54, N_{D_{7}}(A_{4}, A_{2}, A_{1}) = 144, N_{D_{7}}(A_{4}, A_{1}^{2}, A_{1}) = 432, N_{D_{7}}(A_{1} ∗ A_{3}, A_{2}, A_{1}) = 468, N_{D_{7}}(A_{1} ∗ A_{3}, A_{1}^{2}, A_{1}) = 918, N_{D_{7}}(A_{2}^{2}, A_{2}, A_{1}) = 180, N_{D_{7}}(A_{2}^{2}, A_{1}^{2}, A_{1}) = 378, N_{D_{7}}(A_{1}^{2} ∗ A_{2}, A_{2}, A_{1}) = 324, N_{D_{7}}(A_{1}^{2} ∗ A_{2}, A_{1}^{2}, A_{1}) = 486, N_{D_{7}}(A_{1}^{4}, A_{2}, A_{1}) = 108, N_{D_{7}}(A_{1}^{4}, A_{1}^{2}, A_{1}) = 162, N_{D_{7}}(D_{4}, A_{1}, A_{1}, A_{1}) = 216, N_{D_{7}}(A_{4}, A_{1}, A_{1}, A_{1}) = 1296, N_{D_{7}}(A_{1}∗A_{3}, A_{1}, A_{1}, A_{1}) = 3240, N_{D_{7}}(A_{2}^{2}, A_{1}, A_{1}, A_{1}) = 1296, N_{D_{7}}(A_{1}^{2} ∗ A_{2}, A_{1}, A_{1}, A_{1}) = 1944, N_{D_{7}}(A_{1}^{4}, A_{1}, A_{1}, A_{1}) = 648, N_{D_{7}}(A_{3}, A_{3}, A_{1}) = 216, N_{D_{7}}(A_{3}, A_{1} ∗ A_{2}, A_{1}) = 648, N_{D_{7}}(A_{3}, A_{1}^{3}, A_{1}) = 396, N_{D_{7}}(A_{1} ∗ A_{2}, A_{1} ∗ A_{2}, A_{1}) = 1728, N_{D_{7}}(A_{1} ∗ A_{2}, A_{1}^{3}, A_{1}) = 864, N_{D_{7}}(A_{1}^{3}, A_{1}^{3}, A_{1}) = 240, N_{D_{7}}(A_{3}, A_{2}, A_{2}) = 180, N_{D_{7}}(A_{1} ∗ A_{2}, A_{2}, A_{2}) = 576, N_{D_{7}}(A_{1}^{3}, A_{2}, A_{2}) = 384, N_{D_{7}}(A_{3}, A_{2}, A_{1}^{2}) = 486, N_{D_{7}}(A_{1} ∗ A_{2}, A_{2}, A_{1}^{2}) = 1296, N_{D_{7}}(A_{1}^{3}, A_{2}, A_{1}^{2}) = 648, N_{D_{7}}(A_{3}, A_{1}^{2}, A_{1}^{2}) = 1053, N_{D_{7}}(A_{1} ∗ A_{2}, A_{1}^{2}, A_{1}^{2}) = 2592, N_{D_{7}}(A_{1}^{3}, A_{1}^{2}, A_{1}^{2}) = 1080, N_{D_{7}}(A_{3}, A_{2}, A_{1}, A_{1}) = 1512, N_{D_{7}}(A_{3}, A_{1}^{2}, A_{1}, A_{1}) = 3564, N_{D_{7}}(A_{1} ∗ A_{2}, A_{2}, A_{1}, A_{1}) = 4320, N_{D_{7}}(A_{1} ∗ A_{2}, A_{1}^{2}, A_{1}, A_{1}) = 9072, N_{D_{7}}(A_{1}^{3}, A_{2}, A_{1}, A_{1}) = 2448, N_{D_{7}}(A_{1}^{3}, A_{1}^{2}, A_{1}, A_{1}) = 4104, N_{D_{7}}(A_{3}, A_{1}, A_{1}, A_{1}, A_{1}) = 11664, N_{D_{7}}(A_{1} ∗ A_{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 31104, N_{D_{7}}(A_{1}^{3}, A_{1}, A_{1}, A_{1}, A_{1}) = 15552, N_{D_{7}}(A_{2}, A_{2}, A_{2}, A_{1}) = 1296, N_{D_{7}}(A_{2}, A_{2}, A_{1}^{2}, A_{1}) = 3240, N_{D_{7}}(A_{2}, A_{1}^{2}, A_{1}^{2}, A_{1}) = 6804, N_{D_{7}}(A_{1}^{2}, A_{1}^{2}, A_{1}^{2}, A_{1}) = 13122, N_{D_{7}}(A_{2}, A_{2}, A_{1}, A_{1}, A_{1}) = 10368, N_{D_{7}}(A_{2}, A_{1}^{2}, A_{1}, A_{1}, A_{1}) = 23328, N_{D_{7}}(A_{1}^{2}, A_{1}^{2}, A_{1}, A_{1}, A_{1}) = 46656, N_{D_{7}}(A_{2}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 77760, N_{D_{7}}(A_{1}^{2}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 163296, N_{D_{7}}(A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 559872.

The decomposition numbers for E_{6}. These numbers have already been computed in [17, Sec. 17] using Stembridge’s coxeter package [24]. An alternative, independent way to do this is by following the method described in Section 4. Here, in addition to the equations and assignments described at the beginning of the Appendix, we use also the last assertion in Proposition 2 for the type A_{1}^{4}, that is, N_{E_{6}}(A_{1}^{4}, A_{2}) = N_{E_{6}}(A_{1}^{4}, A_{1}^{2}) = 0. Unfortunately, the solution space of the system of linear equations does not consist of a unique solution but is one-dimensional. Mathematica 5.2 expresses all the decomposition numbers in terms of X = N_{E_{6}}(A_{1}^{3}, A_{1}^{3}). In the sequel we make use of the two relations

N_{E_{6}}(A_{3}, A_{3}) = \frac{1}{100}(2592 + 9X),  (A.6)
N_{E_{6}}(A_{1}^{3}, A_{1}^{3}) = \frac{1}{5}(192 − 6X).  (A.7)

From (A.6) we infer that X ≡ 12 (mod 100), while (A.7) implies that X ≤ 32. Hence, we have X = N_{E_{6}}(A_{1}^{3}, A_{1}^{3}) = 12. If we substitute this in the relations for the decomposition numbers found by Mathematica, then we obtain N_{E_{6}}(E_{6}) = 1, N_{E_{6}}(D_{5}, A_{1}) = 12, N_{E_{6}}(A_{5}, A_{1}) = 6, N_{E_{6}}(A_{1} ∗ A_{4}, A_{1}) = 12, N_{E_{6}}(A_{1} ∗ A_{2}^{2}, A_{1}) = 6, N_{E_{6}}(A_{1}^{2} ∗ A_{2}, A_{2}) = 36, N_{E_{6}}(D_{4}, A_{2}) = 4, N_{E_{6}}(A_{4}, A_{2}) = 24, N_{E_{6}}(A_{1} ∗ A_{3}, A_{2}) = 24, N_{E_{6}}(A_{2}^{2}, A_{2}) = 8, N_{E_{6}}(D_{4}, A_{1}^{2}) = 18, N_{E_{6}}(A_{4}, A_{1}^{2}) = 36, N_{E_{6}}(A_{1} ∗ A_{3}, A_{1}^{2}) = 36, N_{E_{6}}(A_{1}^{2} ∗ A_{2}, A_{1}^{2}) = 18, N_{E_{6}}(A_{3}, A_{3}) = 27, N_{E_{6}}(A_{3}, A_{1} ∗ A_{2}) = 72, N_{E_{6}}(A_{3}, A_{1}^{3}) = 36, N_{E_{6}}(A_{1} ∗ A_{2}, A_{1} ∗ A_{2}) = 48, N_{E_{6}}(A_{1} ∗ A_{2}, A_{1}^{3}) = 24, N_{E_{6}}(A_{1}^{3}, A_{1}^{3}) = 12, N_{E_{6}}(D_{4}, A_{1}, A_{1}) = 48, N_{E_{6}}(A_{4}, A_{1}, A_{1}) = 144, N_{E_{6}}(A_{1} ∗ A_{3}, A_{1}, A_{1}) = 144, N_{E_{6}}(A_{2}^{2}, A_{1}, A_{1}) = 24, N_{E_{6}}(A_{1}^{2} ∗ A_{2}, A_{1}, A_{1}) = 144, N_{E_{6}}(A_{3}, A_{2}, A_{1}) = 180, N_{E_{6}}(A_{3}, A_{1}^{2}, A_{1}) = 378, N_{E_{6}}(A_{1} ∗ A_{2}, A_{2}, A_{1}) = 336, N_{E_{6}}(A_{1} ∗ A_{2}, A_{1}^{2}, A_{1}) = 360, N_{E_{6}}(A_{1}^{3}, A_{2}, A_{1}) = 168, N_{E_{6}}(A_{1}^{3}, A_{1}^{2}, A_{1}) = 180, N_{E_{6}}(A_{2}, A_{2}, A_{2}) = 160, N_{E_{6}}(A_{2}, A_{2}, A_{1}^{2}) = 288, N_{E_{6}}(A_{2}, A_{1}^{2}, A_{1}^{2}) = 504, N_{E_{6}}(A_{1}^{2}, A_{1}^{2}, A_{1}^{2}) = 432, N_{E_{6}}(A_{2}, A_{2}, A_{1}, A_{1}) = 1056, N_{E_{6}}(A_{2}, A_{1}^{2}, A_{1}, A_{1}) = 1872, N_{E_{6}}(A_{1}^{2}, A_{1}^{2}, A_{1}, A_{1}) = 2376, N_{E_{6}}(A_{3}, A_{1}, A_{1}, A_{1}) = 1296, N_{E_{6}}(A_{1} ∗A_{2}, A_{1}, A_{1}, A_{1}) = 1728, N_{E_{6}}(A_{1}^{3}, A_{1}, A_{1}, A_{1}) = 864, N_{E_{6}}(A_{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 6912, N_{E_{6}}(A_{1}^{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 10368, N_{E_{6}}(A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 41472.

Acknowledgment. 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 Christos Athanasiadis and Vic Reiner for some helpful exchanges that I had with him on the subject matter. Last, but not least, I thank the referee for an extremely careful reading of the manuscript, and for pointing out that Lemma 1.3.4 of [6] simplifies the proof of Proposition 6.

Notes. After the first version of this paper was distributed, Eleni Tzanaki found a uniform proof of Armstrong’s F = M Conjecture (presented here in Conjecture FM) in “Faces of generalized cluster complexes and noncrossing partitions,” arχiv:math.CO/0605785. Thus, our Theorem 8 becomes an unconditional theorem, that is to say, the reciprocity relation (9.1) holds for any finite root system Φ. Furthermore, the explicit form of the M-triangle in type D_{n} is given by [17, Prop. D] up to a simple substitution of variables.

The problem of computing the decomposition numbers for the type B_{n} is solved implicitly in “Enumeration of m-ary cacti” (Adv. Appl. Math. 24 (2000), 22–56) by Miklós Bóna, Michel Bousquet, Gilbert Labelle and Pierre Leroux. This is explained in detail in the article “Decomposition numbers for finite Coxeter groups and generalised non-crossing partitions” by Thomas Müller and the author, which also solves the problem for the remaining type D_{n}. In particular, the results in that paper, together with the results in the present paper and in [17], constitute an independent — case-by-case — proof of the F = M Conjecture.

References

1. N. Anzalone, J. Baldwin, I. Bronshtein and T. Kyle Petersen, A reciprocity theorem for monomer-dimer coverings, Discrete models for complex systems, DMCS ’03 (Lyon), Discrete Math. Theor. Comput. Sci. Proc., AB, 2003, pp. 179–193.

2. D. D. Armstrong, Generalized noncrossing partitions and combinatorics of Coxeter groups, Ph.D. thesis, Cornell University, 2006.

3. C. A. Athanasiadis, On some enumerative aspects of generalized associahedra, European J. Combin.

(to appear); arχiv:math.CO/0508030.

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

5. C. A. Athanasiadis and E. Tzanaki, On the enumeration of positive cells in generalized cluster complexes and Catalan hyperplane arrangements, J. Algebraic Combin. 23 (2006), 355–375.

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

7. A. Björner and F. Brenti, Combinatorics of Coxeter groups, Springer–Verlag, New York, 2005.

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

9. T. Brady and C. Watt, Lattices in finite real reflection groups, preprint; arχiv:math.CO/0501502.

10. R. W. Carter, Conjugacy classes in the Weyl group, Compositio Math. 25 (1972), 1–59.

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

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

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

14. S. Fomin and N. Reading, Root systems and generalized associahedra, Lecture notes for the IAS/Park City Graduate Summer School in Geometric Combinatorics, July 2004, available at

http://www.math.lsa.umich.edu/~fomin.

15. I. P. Goulden and D. M. Jackson, The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group, Europ. J. Combin. 13 (1992), 357–365.

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

17. C. Krattenthaler, The F -triangle of the generalised cluster complex, Topics in Discrete Mathematics, dedicated to Jarik Nešetřil on the occasion of his 60th birthday (M. Klazar, J. Kratochvil, M. Loebl, J. Matoušek, R. Thomas and P. Valtr, ed.), Springer-Verlag, Berlin, New York, 2006, pp. 93–126.

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

19. J. Propp, A reciprocity theorem for domino tilings, Electronic J. Combin. 8(1) (2001), Article #R18, 9 pp.

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

21. R. Simion, Noncrossing partitions, Discrete Math. 217 (2000), 367–409.

22. R. P. Stanley, On dimer coverings of rectangles of fixed width, Discrete Appl. Math. 12 (1985), 81–87.

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

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

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

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

WWW: http://www.mat.univie.ac.at/~kratt