CYCLIC SIEVING FOR GENERALISED NON-CROSSING PARTITIONS ASSOCIATED WITH COMPLEX REFLECTION GROUPS OF EXCEPTIONAL TYPE

Christian Krattenthaler^{†} and Thomas W. Müller^{‡}

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

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

‡ School of Mathematical Sciences, Queen Mary & Westfield College, University of London, Mile End Road, London E1 4NS, United Kingdom.

                       WWW: http://www.maths.qmw.ac.uk/~twm/

Dedicated to the memory of Herb Wilf

Abstract. We prove that the generalised non-crossing partitions associated with well-generated complex reflection groups of exceptional type obey two different cyclic sieving phenomena, as conjectured by Armstrong, and by Bessis and Reiner. The computational details are provided in the manuscript “Cyclic sieving for generalised non-crossing partitions associated with complex reflection groups of exceptional type — the details” [arχiv:1001.0030].

1. Introduction

In his memoir [3], Armstrong introduced generalised non-crossing partitions associated with finite (real) reflection groups, thereby embedding Kreweras’ non-crossing partitions [22], Edelman’s m-divisible non-crossing partitions [12], the non-crossing partitions associated with reflection groups due to Bessis [7] and Brady and Watt [11] into one uniform framework. Bessis and Reiner [10] observed that Armstrong’s definition can be straightforwardly extended to well-generated complex reflection groups (see Section 2 for the precise definition). These generalised non-crossing partitions possess a wealth of beautiful properties, and they display deep and surprising relations to other combinatorial objects defined for reflection groups (such as the generalised cluster complex of Fomin and Reading [13], or the extended Shi arrangement and the geometric multichains of filters of Athanasiadis [5, 6]); see Armstrong’s memoir [3] and the references given therein.

2000 Mathematics Subject Classification. Primary 05E15; Secondary 05A10 05A15 05A18 06A07 20F55.

Key words and phrases. complex reflection groups, unitary reflection groups, m-divisible noncrossing partitions, generalised non-crossing partitions, Fuß–Catalan numbers, cyclic sieving.

†Research partially supported by the Austrian Science Foundation FWF, grants Z130-N13 and S9607-N13, the latter in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory.”

‡Research supported by the Austrian Science Foundation FWF, Lise Meitner grant M1201-N13.

On the other hand, cyclic sieving is a phenomenon brought to light by Reiner, Stanton and White [29]. It extends the so-called “(−1)-phenomenon” of Stembridge [35, 36]. Cyclic sieving can be defined in three equivalent ways (cf. [29, Prop. 2.1]). The one which gives the name can be described as follows: given a set S of combinatorial objects, an action on S of a cyclic group G = ⟨g⟩ with generator g of order n, and a polynomial P (q) in q with non-negative integer coefficients, we say that the triple (S, P, G) exhibits the cyclic sieving phenomenon, if the number of elements of S fixed by g^{k} equals P (e^{2πik/n}). In [29] it is shown that this phenomenon occurs in surprisingly many contexts, and several further instances have been discovered since then, see the recent survey [32].

In [3, Conj. 5.4.7] (also appearing in [10, Conj. 6.4]) and [10, Conj. 6.5], Armstrong, respectively Bessis and Reiner, conjecture that generalised non-crossing partitions for irreducible well-generated complex reflection groups exhibit two different cyclic sieving phenomena (see Sections 3 and 7 for the precise statements).

According to the classification of these groups due to Shephard and Todd [33], there are two infinite families of irreducible well-generated complex reflection groups, namely the groups G(d, 1, n) and G(e, e, n), where n, d, e are positive integers, and there are 26 exceptional groups. For the infinite families of types G(d, 1, n) and G(e, e, n), the two cyclic sieving conjectures follow from the results in [19].

The purpose of the present article is to present a proof of the cyclic sieving conjectures of Armstrong, and of Bessis and Reiner, for the 26 exceptional types, thus completing the proof of these conjectures. Since the generalised non-crossing partitions feature a parameter m, from the outset this is not a finite problem. Consequently, we first need several auxiliary results to reduce the conjectures for each of the 26 exceptional types to a finite problem. Subsequently, we use Stembridge’s Maple package coxeter [37] and the GAP package CHEVIE [14, 27] to carry out the remaining finite computations. The details of these computations are provided in [21]. In the present paper, we content ourselves with exemplifying the necessary computations by going through some representative cases. It is interesting to observe that, for the verification of the type E_{8} case, it is essential to use the decomposition numbers in the sense of [17, 18, 20] because, otherwise, the necessary computations would not be feasible in reasonable time with the currently available computer facilities. We point out that, for the special case where the aforementioned parameter m is equal to 1, the first cyclic sieving conjecture has been proven in a uniform fashion by Bessis and Reiner in [10]. The crucial result on which this proof is based is (5.5) below, and it plays an important role in our reduction of the conjectures for the 26 exceptional groups to a finite problem. A — non-uniform — proof of cyclic sieving for non-crossing partitions associated with real reflection groups under the action of the so-called Kreweras map — a special case of the second cyclic sieving phenomenon discussed in the present paper — is given by Armstrong, Stump and Thomas in [4]. Just recently, Rhoades proposed a uniform approach to prove the first cyclic sieving conjecture for real reflection groups (but for generic m), see [30, Theorem 3.7].

Our paper is organised as follows. In the next section, we recall the definition of generalised non-crossing partitions for well-generated complex reflection groups and of decomposition numbers in the sense of [17, 18, 20], and we review some basic facts. The first cyclic sieving conjecture is subsequently stated in Section 3. In Section 4, we outline an elementary proof that the q-Fuß–Catalan number, which is the polynomial P in the cyclic sieving phenomena concerning the generalised non-crossing partitions for well-generated complex reflection groups, is always a polynomial with non-negative integer coefficients, as required by the definition of cyclic sieving. (Full details can be found in [21, Sec. 4]. The reader is referred to the first paragraph of Section 4 for comments on other approaches for establishing polynomiality with non-negative coefficients.) Section 5 contains the announced auxiliary results which, for the 26 exceptional types, allow a reduction of the conjecture to a finite problem. In Section 6, we discuss a few cases which, in a representative manner, demonstrate how to perform the remaining case-by-case verification of the conjecture. For full details, we refer the reader to [21, Sec. 6]. The second cyclic sieving conjecture is stated in Section 7. Section 8 contains the auxiliary results which, for the 26 exceptional types, allow a reduction of the conjecture to a finite problem, while in Section 9 we discuss some representative cases of the remaining case-by-case verification of the conjecture. Again, for full details we refer the reader to [21, Sec. 9].

2. Preliminaries

A complex reflection group is a group generated by (complex) reflections in ℂ^{n}. (Here, a reflection is a non-trivial element of GL_{n}(ℂ) which fixes a hyperplane pointwise and which has finite order.) We refer to [24] for an in-depth exposition of the theory complex reflection groups.

Shephard and Todd provided a complete classification of all finite complex reflection groups in [33] (see also [24, Ch. 8]). According to this classification, an arbitrary complex reflection group W decomposes into a direct product of irreducible complex reflection groups, acting on mutually orthogonal subspaces of the complex vector space on which W is acting. Moreover, the list of irreducible complex reflection groups consists of the infinite family of groups G(m, p, n), where m, p, n are positive integers, and 34 exceptional groups, denoted G_{4}, G_{5}, …, G_{37} by Shephard and Todd.

In this paper, we are only interested in finite complex reflection groups which are well-generated. A complex reflection group of rank n is called well-generated if it is generated by n reflections.^{1} Well-generation can be equivalently characterised by a duality property due to Orlik and Solomon [28]. Namely, a complex reflection group of rank n has two sets of distinguished integers d_{1} ≤ d_{2} ≤ ⋯ ≤ d_{n} and d_{1}^{∗} ≥ d_{2}^{∗} ≥ ⋯ ≥ d_{n}^{∗}, called its degrees and codegrees, respectively (see [24, p. 51 and Def. 10.27]). Orlik and Solomon observed, using case-by-case checking, that an irreducible complex reflection group W of rank n is well-generated if and only if its degrees and codegrees satisfy

d_{i} + d_{i}^{∗} = d_{n}

for all i = 1, 2, …, n. The reader is referred to [24, App. D.2] for a table of the degrees and codegrees of all irreducible complex reflection groups. Together with the classification of Shephard and Todd [33], this constitutes a classification of well-generated complex reflection groups: the irreducible well-generated complex reflection groups are — the two infinite families G(d, 1, n) and G(e, e, n), where d, e, n are positive inte-

1We refer to [24, Def. 1.29] for the precise definition of “rank.” Roughly speaking, the rank of a complex reflection group W is the minimal n such that W can be realized as reflection group on ℂ^{n}.

gers,

— the exceptional groups G_{4}, G_{5}, G_{6}, G_{8}, G_{9}, G_{10}, G_{14}, G_{16}, G_{17}, G_{18}, G_{20}, G_{21} of rank 2,

— the exceptional groups G_{23} = H_{3}, G_{24}, G_{25}, G_{26}, G_{27} of rank 3,

— the exceptional groups G_{28} = F_{4}, G_{29}, G_{30} = H_{4}, G_{32} of rank 4,

— the exceptional group G_{33} of rank 5,

— the exceptional groups G_{34}, G_{35} = E_{6} of rank 6,

— the exceptional group G_{36} = E_{7} of rank 7,

— and the exceptional group G_{37} = E_{8} of rank 8. In this list, we have made visible the groups H_{3}, F_{4}, H_{4}, E_{6}, E_{7}, E_{8} which appear as exceptional groups in the classification of all irreducible real reflection groups (cf. [16]).

Let W be a well-generated complex reflection group of rank n, and let T ⊆ W denote the set of all (complex) reflections in the group. Let ℓ_{T} : W → ℤ denote the word length in terms of the generators T. This word length is called absolute length or reflection length. Furthermore, we define a partial order ≤_{T} on W by

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

This partial order is called absolute order or reflection order. As is well-known and easy to see, the equation in (2.1) is equivalent to the statement that every shortest representation of u by reflections occurs as an initial segment in some shortest product representation of w by reflections.

Now fix a (generalised) Coxeter element^{2} c ∈ W and a positive integer m. The m-divisible non-crossing partitions NC^{m}(W) are defined as the set

NC^{m}(W) = {(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)}.

A partial order is defined on this set by

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

We have suppressed the dependence on c, since we understand this definition up to isomorphism of posets. To be more precise, it can be shown that any two Coxeter elements are related to each other by conjugation and (possibly) an automorphism on the field of complex numbers (see [34, Theorem 4.2] or [24, Cor. 11.25]), and hence the resulting posets NC^{m}(W) are isomorphic to each other. If m = 1, then NC^{1}(W) can be identified with the set NC(W) of non-crossing partitions for the (complex) reflection group W as defined by Bessis and Corran (cf. [9] and [8, Sec. 13]; their definition extends the earlier definition by Bessis [7] and Brady and Watt [11] for real reflection groups).

2An element of an irreducible well-generated complex reflection group W of rank n is called a Coxeter element if it is regular in the sense of Springer [34] (see also [24, Def. 11.21]) and of order d_{n}.

An element of W is called regular if it has an eigenvector which lies in no reflecting hyperplane of a reflection of W. It follows from an observation of Lehrer and Springer, proved uniformly by Lehrer and Michel [23] (see [24, Theorem 11.28]), that there is always a regular element of order d_{n} in an irreducible well-generated complex reflection group W of rank n. More generally, if a well-generated complex reflection group W decomposes as W ≅ W_{1} × W_{2} × ⋯ × W_{k}, where the W_{i}’s are irreducible, then a Coxeter element of W is an element of the form c = c_{1}c_{2} ⋯ c_{k}, where c_{i} is a Coxeter element of W_{i}, i = 1, 2, …, k. If W is a real reflection group, that is, if all generators in T have order 2, then the notion of generalised Coxeter element given above reduces to that of a Coxeter element in the classical sense (cf. [16, Sec. 3.16]).

The following result has been proved by a collaborative effort of several authors (see [8, Prop. 13.1]).

Theorem 1. Let W be an irreducible well-generated complex reflection group, and let d_{1} ≤ d_{2} ≤ ⋯ ≤ d_{n} be its degrees and h := d_{n} its Coxeter number. Then

|NC^{m}(W)| = ∏_{i=1}^{n} \frac{mh + d_{i}}{d_{i}} .  (2.2)

Remark 1. (1) The number in (2.2) is called the Fuß–Catalan number for the reflection group W.

(2) If c is a Coxeter element of a well-generated complex reflection group W of rank n, then ℓ_{T} (c) = n. (This follows from [8, Sec. 7].)

We conclude this section by recalling the definition of decomposition numbers from [17, 18, 20]. Although we need them here only for (very small) real reflection groups, and although, strictly speaking, they have been only defined for real reflection groups in [17, 18, 20], this definition can be extended to well-generated complex reflection groups without any extra effort, which we do now.

Given a well-generated complex reflection group W of rank n, types T_{1}, T_{2}, …, T_{d} (in the sense of the classification of well-generated complex reflection groups) such that the sum of the ranks of the T_{i}’s equals n, and a Coxeter element c, the decomposition number N_{W} (T_{1}, T_{2}, …, T_{d}) is defined as the number of “minimal” factorisations c = c_{1}c_{2} ⋯ c_{d}, “minimal” meaning that ℓ_{T} (c_{1}) + ℓ_{T} (c_{2}) + ⋯ + ℓ_{T} (c_{d}) = ℓ_{T} (c) = n, such that, for i = 1, 2, …, d, the type of c_{i} as a parabolic Coxeter element is T_{i}. (Here, the term “parabolic Coxeter element” means a Coxeter element in some parabolic subgroup. It follows from [31, Prop.6.3] that any element c_{i} is indeed a Coxeter element in a unique parabolic subgroup of W.^{3} By definition, the type of c_{i} is the type of this parabolic subgroup.) Since any two Coxeter elements are related to each other by conjugation plus field automorphism, the decomposition numbers are independent of the choice of the Coxeter element c.

The decomposition numbers for real reflection groups have been computed in [17, 18, 20]. To compute the decomposition numbers for well-generated complex reflection groups is a task that remains to be done.

3. Cyclic sieving I

In this section we present the first cyclic sieving conjecture due to Armstrong [3, Conj. 5.4.7], and to Bessis and Reiner [10, Conj. 6.4].

Let ϕ : NC^{m}(W) → NC^{m}(W) be the map defined by

(w_{0}; w_{1}, …, w_{m}) ↦ ((cw_{m}c^{−1})w_{0}(cw_{m}c^{−1})^{−1}; cw_{m}c^{−1}, w_{1}, w_{2}, …, w_{m−1}).  (3.1)

3The uniqueness can be argued as follows: suppose that c_{i} were a Coxeter element in two parabolic subgroups of W, say U_{1} and U_{2}. Then it must also be a Coxeter element in the intersection U_{1} ∩ U_{2}.

On the other hand, the absolute length of a Coxeter element of a complex reflection group U is always equal to rk(U), the rank of U. (This follows from the fact that, for each element u of U, we have ℓ_{T} (u) = codim(ker(u − id)), with id denoting the identity element in U; see e.g. [31, Prop. 1.3]). We conclude that ℓ_{T} (c_{i}) = rk(U_{1}) = rk(U_{2}) = rk(U_{1} ∩ U_{2}), This implies that U_{1} = U_{2}.

It is indeed not difficult to see that, if the (m + 1)-tuple on the left-hand side is an element of NC^{m}(W), then so is the (m + 1)-tuple on the right-hand side. For m = 1, this action reduces to conjugation by the Coxeter element c (applied to w_{1}). Cyclic sieving arising from conjugation by c has been the subject of [10].

It is easy to see that ϕ^{mh} acts as the identity, where h is the Coxeter number of W (see (5.1) and Lemma 12 below). By slight abuse of notation, let C_{1} be the cyclic group of order mh generated by ϕ. (The slight abuse consists in the fact that we insist on C_{1} to be a cyclic group of order mh, while it may happen that the order of the action of ϕ given in (3.1) is actually a proper divisor of mh.)

Given these definitions, we are now in the position to state the first cyclic sieving conjecture of Armstrong, respectively of Bessis and Reiner. By the results of [19] and of this paper, it becomes the following theorem.

Theorem 2. For an irreducible well-generated complex reflection group W and any m ≥ 1, the triple (NC^{m}(W), Cat^{m}(W; q), C_{1}), where Cat^{m}(W; q) is the q-analogue of the Fuß–Catalan number defined by

Cat^{m}(W; q) := ∏_{i=1}^{n} \frac{[mh + d_{i}]_{q}}{[d_{i}]_{q}} ,  (3.2)

exhibits the cyclic sieving phenomenon in the sense of Reiner, Stanton and White [29]. Here, n is the rank of W, d_{1}, d_{2}, …, d_{n} are the degrees of W, h is the Coxeter number of W, and [α]_{q} := (1 − q^{α})/(1 − q).

Remark 2. We write Cat^{m}(W) for Cat^{m}(W; 1).

By definition of the cyclic sieving phenomenon, we have to prove that Cat^{m}(W; q) is a polynomial in q with non-negative integer coefficients, and that

| Fix_{NC^{m}(W)}(ϕ^{p})| = Cat^{m}(W; q)|_{q=e^{2πip/mh}},  (3.3)

for all p in the range 0 ≤ p < mh. The first fact is established in the next section, while the proof of the second is achieved by making use of several auxiliary results, given in Section 5, to reduce the proof to a finite problem, and a subsequent case-by-case analysis. All details of this analysis can be found in [21, Sec. 6]. In the present paper, we content ourselves with discussing the cases where W = G_{24} and where W = G_{37} = E_{8}, since these suffice to convey the flavour of the necessary computations.

4. The q-Fusz–Catalan numbers Cat^{m}(W; q)

The purpose of this section is to provide an elementary and (essentially) self-contained proof of the fact that, for all irreducible complex reflection groups W, the q-Fuß–Catalan number Cat^{m}(W; q) is a polynomial in q with non-negative integer coefficients. For most of the groups, this is a known property. However, aside from the fact that, for many of the known cases, the proof is very indirect and uses deep algebraic results on rational Cherednik algebras, there still remained some cases where this property had not been formally established. The reader is referred to the Theorem in Section 1.6 of [15], which says that, under the assumption of a certain rank condition ([15, Hypothesis 2.4]), the q-Fuß–Catalan number Cat^{m}(W; q) is a Hilbert series of a finite-dimensional quotient of the ring of invariants of W and also the graded character of a finite-dimensional irreducible representation of a spherical rational Cherednik algebra associated with W. At present, this rank condition has been proven for all irreducible well-generated complex reflection groups apart from G_{17}, G_{18}, G_{29}, G_{33}, G_{34}; see [25, Tables 8 and 9, column “rank”] and the recent paper [26], which establishes the result in the case of G_{32}.

In the sequel, aside from the standard notation [α]_{q} = (1 − q^{α})/(1 − q) for q-integers, we shall also use the q-binomial coefficient, which is defined by

[\begin{matrix}n \\ k \end{matrix}]_{q} := \begin{cases}1, & if k = 0, \\ \frac{[n]_{q} [n−1]_{q}···[n−k+1]_{q}}{[k]_{q} [k−1]_{q}···[1]_{q}} , & if k > 0. \end{cases}

We begin with several auxiliary results. The first of these (Proposition 3) is wellknown (and follows, for example, from [1, eqs. (3.3.3) and (3.3.4)], or from [1, Theorem 3.1]). The second (Proposition 4) follows by replacing n by mn + 1 and j by n in Theorem 2 of [2].

Proposition 3. For all non-negative integers n and k, the q-binomial coefficient [ \begin{matrix}n \\ k \end{matrix}]_{q} is a polynomial in q with non-negative integer coefficients.

Proposition 4. For all non-negative integers m and n, the q-Fuß–Catalan number of type A_{n},

\frac{1}{[(m + 1)n + 1]_{q}} [\begin{matrix}(m + 1)n + 1 \\ n \end{matrix}]_{q} ,

is a polynomial in q with non-negative integer coefficients.

The purpose of the next lemma is to lay the basis for the proof of the positivity of coefficients in the polynomial in Corollary 6.

Lemma 5. If a and b are coprime positive integers, then

\frac{[ab]_{q}}{[a]_{q} [b]_{q}}  (4.1)

is a polynomial in q of degree (a − 1)(b − 1), all of whose coefficients are in {0, 1, −1}. Moreover, if one disregards the coefficients which are 0, then +1’s and (−1)’s alternate, and the constant coefficient as well as the leading coefficient of the polynomial equal +1.

Proof. Let Φ_{n}(q) denote the n-th cyclotomic polynomial in q. Using the classical formula

1 − q^{n} = ∏_{d|n} Φ_{d}(q),

we see that

\frac{(1 − q)(1 − q^{ab})}{(1 − q^{a})(1 − q^{b})} = _{∏_{d_{1}|a, d_{1}≠1} ; d_{2}|a, d_{2}≠1}Φ_{d_{1}d_{2}}(q),

so that, manifestly, the expression in (4.1) is a polynomial in q. The claim concerning the degree of this polynomial is obvious.

In order to establish the claim on the coefficients, we start with a sub-expression of (4.1),

\frac{(1 − q^{ab})}{(1 − q^{a})(1 − q^{b})} = ( ∑_{i=0}^{b−1} q^{ia})( ∑_{j=0}^{∞} q^{jb}) = ∑_{k=0}^{∞} C_{k}q^{k},  (4.2)

say. The assumption that a and b are coprime implies that 0 ≤ C_{k} ≤ 1 for k ≤ (a − 1)(b − 1). Multiplying both sides of (4.2) by 1 − q, we obtain the equation

\frac{[ab]_{q}}{[a]_{q} [b]_{q}} = (1 − q) ∑_{k=0}^{(a−1)(b−1)} C_{k}q^{k} + (1 − q) ∑_{k=(a−1)(b−1)+1}^{∞} C_{k}q^{k}.  (4.3)

By our previous observation on the coefficients C_{k} with k ≤ (a − 1)(b − 1), it is obvious that the coefficients of the first expression on the right-hand side of (4.3) are alternately +1 and −1, when 0’s are disregarded. Since we already know that the left-hand side is a polynomial in q of degree (a − 1)(b − 1), we may ignore the second expression.

The proof is concluded by observing that the claims on the constant and leading coefficients are obvious. □

Corollary 6. Let a and b be coprime positive integers, and let γ be an integer with γ ≥ (a − 1)(b − 1). Then the expression

\frac{[γ]_{q} [ab]_{q}}{[a]_{q} [b]_{q}}

is a polynomial in q with non-negative integer coefficients.

Proof. Let

\frac{[ab]_{q}}{[a]_{q} [b]_{q}} = ∑_{k=0}^{(a−1)(b−1)} D_{k}q^{k}.

We then have

\frac{[γ]_{q} [ab]_{q}}{[a]_{q} [b]_{q}} = ∑_{N=0}^{(a−1)(b−1)+γ−1} q^{N} ∑_{k=max\{0,N−γ+1\}}^{N} D_{k}.  (4.4)

If N ≤ γ − 1, then, by Lemma 5, the sum over k on the right-hand side of (4.4) equals 1 − 1 + 1 − 1 + ⋯, which is manifestly non-negative. On the other hand, if N > γ − 1, then we may rewrite the sum over k on the right-hand side of (4.4) as

∑_{k=max{0,N−γ+1}}^{N} D_{k} = ∑_{k=N−γ+1}^{(a−1)(b−1)} D_{k} = ∑_{k=0}^{(a−1)(b−1)+γ−1−N} D_{(a−1)(b−1)−k}.

Again, by Lemma 5, this sum equals 1 − 1 + 1 − 1 + ⋯, which is manifestly nonnegative. □

The next lemma collects positivity results for coefficients in polynomials given by rational function expressions of special form.

Lemma 7. Let α and β be positive integers. The following expressions are polynomials in q with non-negative integer coefficients:

(a) [α]_{q^{3}} [β]_{q^{4}} \begin{matrix}[72] & _{q} & [3] & _{q} & [4] & _{q} \\ [8] & _{q} & [9] & _{q} & [12] & _{q} \end{matrix} for α ≥ 6 and β ≥ 8;

(b) [α]_{q} [β]_{q^{4}} \begin{matrix}[15] & _{q} \\ [3] & _{q} & [5] & _{q} \end{matrix} \begin{matrix}[72] & _{q} & [3] & _{q} & [4] & _{q} \\ [8] & _{q} & [9] & _{q} & [12] & _{q} \end{matrix} for α ≥ 26 and β ≥ 8;

(c) [α]_{q^{3}} [β]_{q^{4}} \begin{matrix}[90] & _{q} & [3] & _{q} & [4] & _{q} \\ [5] & _{q} & [6] & _{q} & [9] & _{q} \end{matrix} for α ≥ 18 and β ≥ 3;

(d) [α]_{q} [β]_{q^{3}} \begin{matrix}[90] & _{q} & [3] & _{q} \\ [5] & _{q} & [6] & _{q} & [9] & _{q} \end{matrix} for α ≥ 20 and β ≥ 18;

(e) [α]_{q} \begin{matrix}[15] & _{q} \\ [3] & _{q} & [5] & _{q} \end{matrix} \begin{matrix}[12] & _{q^{3}} \\ [3] & _{q^{3}} & [4] & _{q^{3}} \end{matrix} for α ≥ 26;

(f) [α]_{q} \begin{matrix}[15] & _{q} \\ [3] & _{q} & [5] & _{q} \end{matrix} \begin{matrix}[6] & _{q^{3}} \\ [2] & _{q^{3}} & [3] & _{q^{3}} \end{matrix} for α ≥ 14;

(g) [α]_{q} [β]_{q^{2}} \begin{matrix}[84] & _{q} & [2] & _{q} \\ [4] & _{q} & [6] & _{q} & [7] & _{q} \end{matrix} for α ≥ 30 and β ≥ 20;

(h) [α]_{q} [β]_{q} \begin{matrix}[105] & _{q} \\ [3] & _{q} & [5] & _{q} & [7] & _{q} \end{matrix} for α ≥ 24 and β ≥ 68;

(i) [α]_{q} [β]_{q} \begin{matrix}[70] & _{q} \\ [2] & _{q} & [5] & _{q} & [7] & _{q} \end{matrix} for α ≥ 24 and β ≥ 34;

(j) [α]_{q^{2}} [β]_{q^{5}} \begin{matrix}[30] & _{q} & [2] & _{q} & [3] & _{q} & [5] & _{q} \\ [6] & _{q} & [10] & _{q} & [15] & _{q} \end{matrix} for α ≥ 4 and β ≥ 2;

(k) [α]_{q} [β]_{q^{5}} \begin{matrix}[14] & _{q} \\ [2] & _{q} & [7] & _{q} \end{matrix} \begin{matrix}[30] & _{q} & [2] & _{q} & [3] & _{q} & [5] & _{q} \\ [6] & _{q} & [10] & _{q} & [15] & _{q} \end{matrix} for α ≥ 14 and β ≥ 2;

(l) [α]_{q} [β]_{q^{2}} \begin{matrix}[35] & _{q} \\ [5] & _{q} & [7] & _{q} \end{matrix} \begin{matrix}[30] & _{q} & [2] & _{q} & [3] & _{q} & [5] & _{q} \\ [6] & _{q} & [10] & _{q} & [15] & _{q} \end{matrix} for α ≥ 32 and β ≥ 12;

(m) [α]_{q^{2}} [β]_{q^{5}} \begin{matrix}[60] & _{q} & [2] & _{q} & [3] & _{q} & [5] & _{q} \\ [10] & _{q} & [12] & _{q} & [15] & _{q} \end{matrix} for α ≥ 16 and β ≥ 2;

(n) [α]_{q} [β]_{q^{2}} \begin{matrix}[35] & _{q} \\ [5] & _{q} & [7] & _{q} \end{matrix} \begin{matrix}[60] & _{q} & [2] & _{q} & [3] & _{q} & [5] & _{q} \\ [10] & _{q} & [12] & _{q} & [15] & _{q} \end{matrix} for α ≥ 56 and β ≥ 4;

(o) [α]_{q} [β]_{q^{5}} \begin{matrix}[14] & _{q} \\ [2] & _{q} & [7] & _{q} \end{matrix} \begin{matrix}[60] & _{q} & [2] & _{q} & [3] & _{q} & [5] & _{q} \\ [10] & _{q} & [12] & _{q} & [15] & _{q} \end{matrix} for α ≥ 38 and β ≥ 2;

(p) [α]_{q} [β]_{q^{3}} \begin{matrix}[126] & _{q} & [3] & _{q} \\ [6] & _{q} & [7] & _{q} & [9] & _{q} \end{matrix} for α ≥ 30 and β ≥ 26;

(q) [α]_{q} [β]_{q^{3}} \begin{matrix}[252] & _{q} & [3] & _{q} \\ [7] & _{q} & [9] & _{q} & [12] & _{q} \end{matrix} for α ≥ 66 and β ≥ 54;

(r) [α]_{q} [β]_{q^{2}} \begin{matrix}[140] & _{q} & [2] & _{q} \\ [4] & _{q} & [7] & _{q} & [10] & _{q} \end{matrix} for α ≥ 54 and β ≥ 34.

Proof. All these assertions have a very similar flavour, and so do their proofs. In order to avoid repetition, proof details are only provided for items (a) and (j); the proofs of items (b)–(i) and (p)–(r) follow the pattern exhibited in the proof of item (a), while the proofs of items (k)–(o) follow that of the proof of item (j). Full details are found in [21, Sec. 4].

In order to establish item (a), we start with the factorisation

\begin{matrix}[72] & q & [3] & q & [4] & q \\ [8] & q & [9] & q & [12] & q \end{matrix}

= (1 − q^{3} + q^{9} − q^{15} + q^{18})(1 − q^{4} + q^{8} − q^{12} + q^{16} − q^{20} + q^{24} − q^{28} + q^{32}).

It should be observed that both factors on the right-hand side have the property that coefficients are in {0, 1, −1} and that (+1)’s and (−1)’s alternate, if one disregards the coefficients which are 0. If we now apply the same idea as in the proof of Corollary 6, then we see that [α]_{q^{3}} times the first factor is a polynomial in q with non-negative integer coefficients, as is [β]_{q^{4}} times the second factor. Taken together, this establishes the claim.

Now we turn to item (j). We have

\begin{matrix}[30] & q & [2] & q & [3] & q & [5] & q \\ [6] & q & [10] & q & [15] & q \end{matrix} = 1 + q − q^{3} − q^{4} − q^{5} + q^{7} + q^{8}.

If we multiply this expression by [α]_{q^{2}}, then, for α = 4 we obtain

1 + q + q^{2} − q^{5} − q^{9} + q^{12} + q^{13} + q^{14},

for α = 5 we obtain

1 + q + q^{2} − q^{5} + q^{8} − q^{11} + q^{14} + q^{15} + q^{16},

and, for α ≥ 6, we obtain

1 + q + q^{2} − q^{5} + q^{8} + q^{10} + p_{1}(q) + q^{2α−4} + q^{2α−2} − q^{2α+1} + q^{2α+4} + q^{2α+5} + q^{2α+6},

where p_{1}(q) is a polynomial in q with non-negative coefficients of order at least 11 and degree at most 2α − 5. In all cases it is obvious that the product of the result and [β]_{q^{5}}, with β ≥ 2, is a polynomial in q with non-negative coefficients. □

We are now ready for the proof of the main result of this section.

Theorem 8. For all irreducible well-generated complex reflection groups and positive integers m, the q-Fuß–Catalan number Cat^{m}(W; q) is a polynomial in q with non-negative integer coefficients.

Proof. First, let W = A_{n}. In this case, the degrees are 2, 3, …, n + 1, and hence

Cat^{m}(A_{n}; q) = \frac{1}{[(m + 1)n + 1]_{q}} [\begin{matrix}(m + 1)n + 1 \\ n \end{matrix}]_{q} ,

which, by Proposition 4, is a polynomial in q with non-negative integer coefficients. Next, let W = G(d, 1, n). In this case, the degrees are d, 2d, …, nd, and hence

Cat^{m}(G(d, 1, n); q) = [\begin{matrix}(m + 1)n \\ n \end{matrix}]_{q^{d}} ,

which, by Proposition 3, is a polynomial in q with non-negative integer coefficients. Now, let W = G(e, e, n). In this case, the degrees are e, 2e, …, (n − 1)e, n, and hence

Cat^{m}(G(e, e, n); q) = \frac{[m(n − 1)e + n]_{q}}{[n]_{q}} ∏_{i=1}^{n−1} \frac{[m(n − 1)e + ie]_{q}}{[ie]_{q}}

= [\begin{matrix}(m + 1)(n − 1) \\ n − 1 \end{matrix}]_{q^{e}} + q^{n}[e]_{q^{n}} [\begin{matrix}(m + 1)(n − 1) \\ n \end{matrix}]_{q^{e}} ,

which, by Proposition 3, is a polynomial in q with non-negative integer coefficients.

It remains to verify the claim for the exceptional groups.

For the groups W = G_{6}, G_{9}, G_{14}, G_{17}, G_{21}, and partially for the groups W = G_{20}, G_{23}, G_{28}, G_{30}, G_{33}, G_{35}, G_{36}, G_{37} (depending on congruence properties of the parameter m), polynomiality and non-negativity of coefficients of the corresponding q-Fuß–Catalan number can be directly read off by a proper rearrangement of the terms in the defining expression; for example, for W = G_{21} (with degrees given by 12, 60) we have

Cat^{m}(G_{21}; q) = \frac{[60m + 12]_{q} [60m + 60]_{q}}{[12]_{q} [60]_{q}} = [5m + 1]_{q^{12}} [m + 1]_{q^{60}},

which is manifestly a polynomial in q with non-negative integer coefficients.

For the groups G_{5}, G_{10}, G_{18}, G_{26}, G_{27}, G_{29}, G_{34}, the terms in the defining expression of the corresponding q-Fuß–Catalan number can be arranged in a manner so that a q-binomial coefficient appears; polynomiality and non-negativity of coefficients then follow from Proposition 3. For example, for W = G_{34} (with degrees given by 6, 12, 18, 24, 30, 42) we have

Cat^{m}(G_{34}; q) = \frac{[42m + 6]_{q} [42m + 12]_{q} [42m + 18]_{q} [42m + 24]_{q} [42m + 30]_{q} [42m + 42]_{q}}{[6]_{q} [12]_{q} [18]_{q} [24]_{q} [30]_{q} [42]_{q}}

= [m + 1]_{q^{42}} [\begin{matrix}7m + 5 \\ 5 \end{matrix}]_{q^{6}} ,

which, written in this form, is obviously a polynomial in q with non-negative integer coefficients.

On the other hand, for the groups G_{4}, G_{8}, G_{16}, G_{25}, G_{32}, the terms in the defining expression of the corresponding q-Fuß–Catalan number can be arranged in a manner so that a q-Fuß–Catalan number of type A appears and Proposition 4 applies; for example, for W = G_{32} (with degrees given by 12, 18, 24, 30) we have

Cat^{m}(G_{32}; q) = \frac{[30m + 12]_{q} [30m + 18]_{q} [30m + 24]_{q} [30m + 30]_{q}}{[12]_{q} [18]_{q} [24]_{q} [30]_{q}}

= \frac{1}{[5m + 6]_{q^{6}}} [\begin{matrix}5m + 6 \\ 5 \end{matrix}]_{q^{6}} ,

which indeed fits into the framework of Proposition 4 and, hence, is a polynomial in q with non-negative integer coefficients.

In the other cases, the more “specialised” auxiliary results given in Corollary 6 and Lemma 7 have to be applied. For the sake of illustration, and in order for the reader to get a feeling for the utility of Corollary 6 and the 18 assertions in Lemma 7, we exhibit one example of application for each of them below, with full details being provided in [21, Sec. 4]. In general, the idea is that, given a rational expression consisting of cyclotomic factors, as in the definition of the q-Fuß–Catalan numbers, one tries to place denominator factors below appropriate numerator factors so that one can divide out the denominator factor completely. For example, if we were to encounter the expression

\frac{[30m + 12]_{q} · (other terms)}{[12]_{q} · (other terms)}

and know that m is even, then we would simplify this to

[\frac{5m+2}{2}]_{q^{12}} · \frac{(other terms)}{(other terms)},

where [\frac{5m+2}{2}]_{q^{12}} is manifestly a polynomial in q with non-negative integer coefficients. On the other hand, in a situation where two denominator factors “want” to divide a single numerator factor, we “extract” as much as we can from the numerator factor and compensate by additional “fudge” factors. To be more concrete, if we encounter the expression

\frac{[14m + 14]_{q} · (other terms)}{[6]_{q} [14]_{q} · (other terms)}

and we know that m ≡ 2 (mod 3), then we would try the rewriting

[\frac{m+1}{3}]_{q^{42}} \frac{[21]_{q^{2}}}{[3]_{q^{2}} [7]_{q^{2}} [2]_{q}} · \frac{(other terms)}{(other terms)},

with the idea that we might find somewhere else a term [2α]_{q}, which could be combined with the term [2]_{q} in the denominator into [2α]_{q}/[2]_{q} = [α]_{q^{2}}, and then apply Corollary 6 to see that

[α]_{q^{2}} \frac{[21]_{q^{2}}}{[3]_{q^{2}} [7]_{q^{2}}}

is a polynomial in q with non-negative integer coefficients (provided α is at least 12), with [\frac{m+1}{3}]_{q^{42}} being such a polynomial in any case.

In situations where three denominator factors “want” to divide a single numerator factor, one has to perform more complicated rearrangements, in order to be able to apply one of the assertions from Lemma 7.

For example, for W = G_{24}, the degrees are 4, 6, 14, and hence

Cat^{m}(G_{24}; q) = \frac{[14m + 4]_{q} [14m + 6]_{q} [14m + 14]_{q}}{[4]_{q} [6]_{q} [14]_{q}} .

We have

Cat^{m}(G_{24}; q) = \begin{cases}[\frac{7m}{2} + 1]_{q^{4}} [\frac{14m}{6} + 1]_{q^{6}} [m + 1]_{q^{14}} , & if m ≡ 0 (mod 6), \\ [\frac{7m+2}{3}]_{q^{6}} [\frac{7m+3}{2}]_{q^{4}} [m + 1]_{q^{14}} , & if m ≡ 1 (mod 6), \\ [\frac{7m}{2} + 1]_{q^{4}} [7m + 3]_{q^{2}} [\frac{m+1}{3}]_{q^{42}} \frac{[21]_{q^{2}}}{[3]_{q^{2}}[7]_{q^{2}}} , & if m ≡ 2 (mod 6), \\ [7m + 2]_{q^{2}} [\frac{7m}{3} + 1]_{q^{6}} [\frac{m+1}{2}]_{q^{28}} \frac{[14]_{q^{2}}}{[2]_{q^{2}}[7]_{q^{2}}} , & if m ≡ 3 (mod 6), \\ [\frac{7m+2}{6}]_{q^{12}} \frac{[6]_{q^{2}}}{[2]_{q^{2}}[3]_{q^{2}}} [7m + 3]_{q^{2}} [m + 1]_{q^{14}} , & if m ≡ 4 (mod 6), \\ [7m + 2]_{q^{2}} [\frac{7m+3}{2}]_{q^{4}} [\frac{m+1}{3}]_{q^{42}} \frac{[21]_{q^{2}}}{[3]_{q^{2}}[7]_{q^{2}}} , & if m ≡ 5 (mod 6), \end{cases}

which, by Corollary 6, are polynomials in q with non-negative integer coefficients in all cases.

For W = G_{30} = H_{4}, the degrees are 2, 12, 20, 30, and hence

Cat^{m}(H_{4}; q) = \frac{[30m + 2]_{q} [30m + 12]_{q} [30m + 20]_{q} [30m + 30]_{q}}{[2]_{q} [12]_{q} [20]_{q} [30]_{q}} .

If m is odd, then we may write

Cat^{m}(H_{4}; q) = [\frac{15m+1}{2}]_{q^{4}} [5m + 2]_{q^{6}} [3m + 2]_{q^{10}} [\frac{m+1}{2}]_{q^{60}} \frac{[30]_{q^{2}} [2]_{q^{2}} [3]_{q^{2}} [5]_{q^{2}}}{[6]_{q^{6}} [10]_{q^{2}} [15]_{q^{2}}} ,

which, by Lemma 7.(j), is a polynomial in q with non-negative integer coefficients.

For W = G_{35} = E_{6}, the degrees are 2, 5, 6, 8, 9, 12, and hence

Cat^{m}(E_{6}; q) = \frac{[12m + 2]_{q} [12m + 5]_{q} [12m + 6]_{q} [12m + 8]_{q} [12m + 9]_{q} [12m + 12]_{q}}{[2]_{q} [5]_{q} [6]_{q} [8]_{q} [9]_{q} [12]_{q}} .

If m ≡ 5 (mod 30), then we have

Cat^{m}(E_{6}; q) = [6m + 1]_{q^{2}}[\frac{12m+5}{5}]_{q^{5}}[2m + 1]_{q^{6}}

× [3m + 2]_{q^{4}}[4m + 3]_{q^{3}}[\frac{m+1}{6}]_{q^{72}} \begin{matrix}[72] & q & [3] & q & [4] & q \\ [8] & q & [9] & q & [12] & q \end{matrix} ,

which, by Lemma 7.(a), is a polynomial in q with non-negative integer coefficients.

If m ≡ 7 (mod 30), then we have

Cat^{m}(E_{6}; q) = [\frac{6m+1}{2}]_{q^{4}}[12m + 5]_{q}[\frac{2m+1}{15}]_{q^{90}}

× \begin{matrix}[90] & q & [3] & q & [4] & q \\ [5] & q & [6] & q & [9] & q \end{matrix} [3m + 2]_{q^{4}}[4m + 3]_{q^{3}}[\frac{m+1}{2}]_{q^{24}} \frac{[6]_{q^{4}}}{[2]_{q^{4}} [3]_{q^{4}}} ,

which, by Corollary 6 and Lemma 7.(c), is a polynomial in q with non-negative integer coefficients.

If m ≡ 8 (mod 30), then we have

Cat^{m}(E_{6}; q) = [6m + 1]_{q^{2}}[12m + 5]_{q}[2m + 1]_{q^{6}}[\frac{3m+2}{2}]_{q^{8}}

× [\frac{4m+3}{5}]_{q^{15}} \frac{[15]_{q}}{[3]_{q} [5]_{q}} [\frac{m+1}{3}]_{q^{36}} \begin{matrix}[12] & q_{3} \\ [3]_{q^{3}} & [4]_{q^{3}} \end{matrix} ,

which, by Lemma 7.(e), is a polynomial in q with non-negative integer coefficients. If m ≡ 13 (mod 30), then we have

Cat^{m}(E_{6}; q) = [6m + 1]_{q^{2}}[12m + 5]_{q}[\frac{2m+1}{3}]_{q^{18}} \begin{matrix}[6] & q_{3} \\ [2]_{q^{3}} & [3]_{q^{3}} \end{matrix}

× [3m + 2]_{q^{4}}[\frac{4m+3}{5}]_{q^{15}} \frac{[15]_{q}}{[3]_{q} [5]_{q}} [\frac{m+1}{2}]_{q^{24}} \begin{matrix}[6] & q_{4} \\ [2]_{q^{4}} & [3]_{q^{4}} \end{matrix} ,

which, by Lemma 7.(f), is a polynomial in q with non-negative integer coefficients. If m ≡ 22 (mod 30), then we have

Cat^{m}(E_{6}; q) = [6m + 1]_{q^{2}}[12m + 5]_{q}[\frac{2m+1}{15}]_{q^{90}} \begin{matrix}[90]_{q} & [3]_{q} \\ [5]_{q} & [6]_{q} & [9]_{q} \end{matrix}

× [\frac{3m+2}{2}]_{q^{8}}[4m + 3]_{q^{3}}[m + 1]_{q^{12}},

which, by Lemma 7.(d), is a polynomial in q with non-negative integer coefficients. If m ≡ 23 (mod 30), then we have

Cat^{m}(E_{6}; q) = [6m + 1]_{q^{2}}[12m + 5]_{q}[2m + 1]_{q^{6}}

× [3m + 2]_{q^{4}}[\frac{4m+3}{5}]_{q^{15}} \frac{[15]_{q}}{[3]_{q} [5]_{q}} [\frac{m+1}{6}]_{q^{72}} \begin{matrix}[72] & q & [3] & q & [4] & q \\ [8] & q & [9] & q & [12] & q \end{matrix} ,

which, by Lemma 7.(b), is a polynomial in q with non-negative integer coefficients. For W = G_{36} = E_{7}, the degrees are 2, 6, 8, 10, 12, 14, 18, and hence

Cat^{m}(E_{7}; q) = \frac{[18m + 2]_{q} [18m + 6]_{q} [18m + 8]_{q} [18m + 10]_{q}}{[2]_{q} [6]_{q} [8]_{q} [10]_{q}}

× \frac{[18m + 12]_{q} [18m + 14]_{q} [18m + 18]_{q}}{[12]_{q} [14]_{q} [18]_{q}} .

If m ≡ 18 (mod 140), then we have

Cat^{m}(E_{7}; q) = [9m + 1]_{q^{2}}[\frac{3m+1}{5}]_{q^{30}} \frac{[15]_{q^{2}}}{[3]_{q^{2}} [5]_{q^{2}}}

× [\frac{9m+4}{2}]_{q^{4}}[9m + 5]_{q^{2}}[\frac{3m+2}{28}]_{q^{168}} \frac{[84]_{q^{2}} [2]_{q^{2}}}{[4]_{q^{2}} [6]_{q^{2}} [7]_{q^{2}}} [9m + 7]_{q^{2}}[m + 1]_{q^{18}},

which, by Corollary 6 and Lemma 7.(g), is a polynomial in q with non-negative integer coefficients.

If m ≡ 23 (mod 140), then we have

Cat^{m}(E_{7}; q) = [\frac{9m+1}{4}]_{q^{8}}[\frac{3m+1}{35}]_{q^{210}} \begin{matrix}[105] & q_{2} \\ [3]_{q^{2}} & [5]_{q^{2}} & [7]_{q^{2}} \end{matrix} [9m + 4]_{q^{2}}[9m + 5]_{q^{2}}

× [3m + 2]_{q^{6}}[9m + 7]_{q^{2}}[\frac{m+1}{2}]_{q^{36}} \begin{matrix}[6] & q_{6} \\ [2]_{q^{6}} & [3]_{q^{6}} \end{matrix} ,

which, by Corollary 6 and Lemma 7.(h), is a polynomial in q with non-negative integer coefficients.

If m ≡ 54 (mod 140), then we have

Cat^{m}(E_{7}; q) = [9m + 1]_{q^{2}}[3m + 1]_{q^{6}}[\frac{9m+4}{70}]_{q^{140}} \begin{matrix}[70] & q_{2} \\ [2]_{q^{2}} & [5]_{q^{2}} & [7]_{q^{2}} \end{matrix} [9m + 5]_{q^{2}}

× [\frac{3m+2}{4}]_{q^{24}} \begin{matrix}[6] & q_{4} \\ [2]_{q^{4}} & [3]_{q^{4}} \end{matrix} [9m + 7]_{q^{2}}[m + 1]_{q^{18}}.

If one decomposes [9m+7]_{q^{2}} as [\frac{9m}{2} +4]_{q^{4}}+q^{2}[\frac{9m}{2} +3]_{q^{4}}, then one sees that, by Corollary 6 and Lemma 7.(i), this is a polynomial in q with non-negative integer coefficients.

For W = G_{37} = E_{8}, the degrees are 2, 8, 12, 14, 18, 20, 24, 30, and hence

Cat^{m}(E_{7}; q) = \frac{[30m + 2]_{q} [30m + 8]_{q} [30m + 12]_{q} [30m + 14]_{q}}{[2]_{q} [8]_{q} [12]_{q} [14]_{q}}

× \frac{[30m + 18]_{q} [30m + 20]_{q} [30m + 24]_{q} [30m + 30]_{q}}{[18]_{q} [20]_{q} [24]_{q} [30]_{q}} .

If m ≡ 3 (mod 84), then we have

Cat^{m}(E_{8}; q) = [\frac{15m+1}{2}]_{q^{4}}[\frac{15m+4}{7}]_{q^{14}}[5m + 2]_{q^{6}}[\frac{15m+7}{4}]_{q^{8}}[\frac{5m+3}{6}]_{q^{36}} \frac{[6]_{q^{6}}}{[2]_{q^{6}} [3]_{q^{6}}}

× [3m + 2]_{q^{10}}[5m + 4]_{q^{6}}[\frac{m+1}{4}]_{q^{120}} \frac{[60]_{q^{2}} [2]_{q^{2}} [3]_{q^{2}} [5]_{q^{2}}}{[10]_{q^{2}} [12]_{q^{2}} [15]_{q^{2}}} ,

which, by Corollary 6 and Lemma 7.(m), is a polynomial in q with non-negative integer coefficients.

If m ≡ 8 (mod 84), then we have

Cat^{m}(E_{8}; q) = [15m + 1]_{q^{2}}[\frac{15m+4}{4}]_{q^{8}}[\frac{5m+2}{42}]_{q^{252}} \begin{matrix}[126]_{q^{2}} & [3]_{q^{2}} \\ [6]_{q^{2}} & [7]_{q^{2}} & [9]_{q^{2}} \end{matrix} [15m + 7]_{q^{2}}[5m + 3]_{q^{6}}

× [\frac{3m+2}{2}]_{q^{20}}[\frac{5m+4}{4}]_{q^{24}}[m + 1]_{q^{30}},

which, by Lemma 7.(p), is a polynomial in q with non-negative integer coefficients. If m ≡ 11 (mod 84), then we have

Cat^{m}(E_{8}; q) = [\frac{15m+1}{2}]_{q^{4}}[15m + 4]_{q^{2}}[\frac{5m+2}{3}]_{q^{18}}[\frac{15m+7}{4}]_{q^{8}}[\frac{5m+3}{2}]_{q^{12}}

× [\frac{3m+2}{7}]_{q^{70}} \frac{[35]_{q^{2}}}{[5]_{q^{2}} [7]_{q^{2}}} [5m + 4]_{q^{6}}[\frac{m+1}{4}]_{q^{120}} \frac{[60]_{q^{2}} [2]_{q^{2}} [3]_{q^{2}} [5]_{q^{2}}}{[10]_{q^{2}} [12]_{q^{2}} [15]_{q^{2}}} ,

which, by Corollary 6 and Lemma 7.(n), is a polynomial in q with non-negative integer coefficients.

If m ≡ 16 (mod 84), then we have

Cat^{m}(E_{8}; q) = [15m + 1]_{q^{2}}[\frac{15m+4}{4}]_{q^{8}}[\frac{5m+2}{2}]_{q^{12}}[15m + 7]_{q^{2}}[5m + 3]_{q^{6}}

× [\frac{3m+2}{2}]_{q^{20}}[\frac{5m+4}{84}]_{q^{504}} \frac{[252]_{q^{2}} [3]_{q^{2}}}{[7]_{q^{2}} [9]_{q^{2}} [12]_{q^{2}}} [m + 1]_{q^{30}},

which, by Lemma 7.(q), is a polynomial in q with non-negative integer coefficients. If m ≡ 18 (mod 84), then we have

Cat^{m}(E_{8}; q) = [15m + 1]_{q^{2}}[\frac{15m+4}{2}]_{q^{4}}[\frac{5m+2}{4}]_{q^{24}}[15m + 7]_{q^{2}}[\frac{5m+3}{3}]_{q^{18}}

[\frac{3m+2}{28}]_{q^{280}} \begin{matrix}[140]_{q^{2}} & [2]_{q^{2}} \\ [4]_{q^{2}} & [7]_{q^{2}} & [10]_{q^{2}} \end{matrix} [\frac{5m+4}{2}]_{q^{12}}[m + 1]_{q^{30}},

which, by Lemma 7.(r), is a polynomial in q with non-negative integer coefficients. If m ≡ 21 (mod 84), then we have

Cat^{m}(E_{8}; q) = [\frac{15m+1}{4}]_{q^{8}}[15m + 4]_{q^{2}}[5m + 2]_{q^{6}}[\frac{15m+7}{14}]_{q^{28}} \frac{[14]_{q^{2}}}{[2]_{q^{2}} [7]_{q^{2}}} [\frac{5m+3}{12}]_{q^{72}} \frac{[12]_{q^{6}}}{[3]_{q^{6}} [4]_{q^{6}}}

× [3m + 2]_{q^{10}}[5m + 4]_{q^{6}}[\frac{m+1}{2}]_{q^{60}} \begin{matrix}[30]_{q^{2}} & [2]_{q^{2}} & [3]_{q^{2}} & [5]_{q^{2}} \\ [6]_{q^{2}} & [10]_{q^{2}} & [15]_{q^{2}} \end{matrix} ,

which, by Corollary 6 and Lemma 7.(k), is a polynomial in q with non-negative integer coefficients.

If m ≡ 25 (mod 84), then we have

Cat^{m}(E_{8}; q) = [\frac{15m+1}{4}]_{q^{8}}[15m + 4]_{q^{2}}[5m + 2]_{q^{6}}[\frac{15m+7}{2}]_{q^{4}}[\frac{5m+3}{4}]_{q^{24}}

× [\frac{3m+2}{7}]_{q^{70}} \frac{[35]_{q^{2}}}{[5]_{q^{2}} [7]_{q^{2}}} [\frac{5m+4}{3}]_{q^{18}}[\frac{m+1}{2}]_{q^{60}} \begin{matrix}[30]_{q^{2}} & [2]_{q^{2}} & [3]_{q^{2}} & [5]_{q^{2}} \\ [6]_{q^{2}} & [10]_{q^{2}} & [15]_{q^{2}} \end{matrix} ,

which, by Lemma 7.(l), is a polynomial in q with non-negative integer coefficients.

If m ≡ 27 (mod 84), then we have

Cat^{m}(E_{8}; q) = [\frac{15m+1}{14}]_{q^{28}} \frac{[14]_{q^{2}}}{[2]_{q^{2}} [7]_{q^{2}}} [15m + 4]_{q^{2}}[5m + 2]_{q^{6}}[\frac{15m+7}{4}]_{q^{8}}[\frac{5m+3}{6}]_{q^{36}} \frac{[6]_{q^{6}}}{[2]_{q^{6}} [3]_{q^{6}}}

× [3m + 2]_{q^{10}}[5m + 4]_{q^{6}}[\frac{m+1}{4}]_{q^{120}} \frac{[60]_{q^{2}} [2]_{q^{2}} [3]_{q^{2}} [5]_{q^{2}}}{[10]_{q^{2}} [12]_{q^{2}} [15]_{q^{2}}} ,

which, by Corollary 6 and Lemma 7.(o), is a polynomial in q with non-negative integer coefficients.

All other cases are disposed of in a similar fashion. □

5. Auxiliary results I

This section collects several auxiliary results which allow us to reduce the problem of proving Theorem 2, or the equivalent statement (3.3), for the 26 exceptional groups listed in Section 2 to a finite problem. While Lemmas 10 and 11 cover special choices of the parameters, Lemmas 9 and 13 afford an inductive procedure. More precisely, if we assume that we have already verified Theorem 2 for all groups of smaller rank, then Lemmas 9 and 13, together with Lemmas 10 and 14, reduce the verification of Theorem 2 for the group that we are currently considering to a finite problem; see Remark 3. The final lemma of this section, Lemma 15, disposes of complex reflection groups with a special property satisfied by their degrees.

Let p = am + b, 0 ≤ b < m. We have

ϕ^{p}((w_{0}; w_{1}, …, w_{m}))

= (∗; c^{a+1}w_{m−b+1}c^{−a−1}, c^{a+1}w_{m−b+2}c^{−a−1}, …, c^{a+1}w_{m}c^{−a−1},
c^{a}w_{1}c^{−a}, …, c^{a}w_{m−b}c^{−a}), (5.1)

where ∗ stands for the element of W which is needed to complete the product of the components to c.

Lemma 9. It suffices to check (3.3) for p a divisor of mh. More precisely, let p be a divisor of mh, and let k be another positive integer with gcd(k, mh/p) = 1, then we have

Cat^{m}(W; q)|_{q=e^{2πip/mh}} = Cat^{m}(W; q)|_{q=e^{2πikp/mh}}  (5.2)

and

| Fix_{NC^{m}(W)}(ϕ^{p})| = | Fix_{NC^{m}(W)}(ϕ^{kp})|.  (5.3)

Proof. For (5.2), this follows immediately from

lim_{q→ζ} \frac{[α]_{q}}{[β]_{q}} = \begin{cases}\frac{α}{β} & if α ≡ β ≡ 0 (mod d), \\ 1 & otherwise, \end{cases}  (5.4)

where ζ is a primitive d-th root of unity and α, β are non-negative integers such that α ≡ β (mod d).

In order to establish (5.3), suppose that x ∈ Fix_{NC^{m}(W)}(ϕ^{p}), that is, x ∈ NC^{m}(W) and ϕ^{p}(x) = x. It obviously follows that ϕ^{kp}(x) = x, so that x ∈ Fix_{NC^{m}(W)}(ϕ^{kp}). To establish the converse, note that, if gcd(k, mh/p) = 1, then there exists k′ with k′k ≡ 1 (mod \frac{mh}{p}). It follows that, if x ∈ Fix_{NC^{m}(W)}(ϕ^{kp}), that is, if x ∈ NC^{m}(W) and ϕ^{kp}(x) = x, then x = ϕ^{k′kp}(x) = ϕ^{p}(x), whence x ∈ Fix_{NC^{m}(W)}(ϕ^{p}). □

Lemma 10. Let p be a divisor of mh. If p is divisible by m, then (3.3) is true.

Proof. According to (5.1), the action of ϕ^{p} on NC^{m}(W) is described by

ϕ^{p}((w_{0}; w_{1}, …, w_{m})) = (∗; c^{p/m}w_{1}c^{−p/m}, …, c^{p/m}w_{m}c^{−p/m}).

Hence, if (w_{0}; w_{1}, …, w_{m}) is fixed by ϕ^{p}, then each individual w_{i} must be fixed under conjugation by c^{p/m}.

Using the notation W′ = Cent_{W} (c^{p/m}), the previous observation means that w_{i} ∈ W′, i = 1, 2, …, m. Springer [34, Theorem 4.2] (see also [24, Theorem 11.24(iii)]) proved that W′ is a well-generated complex reflection group whose degrees coincide with those degrees of W that are divisible by mh/p. It was furthermore shown in [10, Lemma 3.3] that

NC(W) ∩ W′ = NC(W′).  (5.5)

Hence, the tuples (w_{0}; w_{1}, …, w_{m}) fixed by ϕ^{p} are in fact identical with the elements of NC^{m}(W′), which implies that

| Fix_{NC^{m}(W)}(ϕ^{p})| = |NC^{m}(W′)|.  (5.6)

Application of Theorem 1 with W replaced by W′ and of the “limit rule” (5.4) then yields that

|NC^{m}(W′)| = _{∏_{1≤i≤n} ; \frac{mh}{p} |d_{i}} \frac{mh + d_{i}}{d_{i}} = Cat^{m}(W; q)|_{q=e^{2πip/mh}}.  (5.7)

Combining (5.6) and (5.7), we obtain (3.3). This finishes the proof of the lemma. □

Lemma 11. Equation (3.3) holds for all divisors p of m.

Proof. Using (5.4) and the fact that the degrees of irreducible well-generated complex reflection groups satisfy d_{i} < h for all i < n, we see that

Cat^{m}(W; q)|_{q=e^{2πip/mh}} = \begin{cases}m + 1 & if m = p, \\ 1 & if m ≠ p. \end{cases}

On the other hand, if (w_{0}; w_{1}, …, w_{m}) is fixed by ϕ^{p}, then, because of the action (5.1), we must have w_{1} = w_{p+1} = ⋯ = w_{m−p+1} and w_{1} = cw_{m−p+1}c^{−1}. In particular, w_{1} ∈ Cent_{W} (c). By the theorem of Springer cited in the proof of Lemma 10, the subgroup Cent_{W} (c) is itself a complex reflection group whose degrees are those degrees of W that are divisible by h. The only such degree is h itself, hence Cent_{W} (c) is the cyclic group generated by c. Moreover, by (5.5), we obtain that w_{1} = ε, the identity element of W, or w_{1} = c. Therefore, for m = p the set Fix_{NC^{m}(W)}(ϕ^{p}) consists of the m + 1 elements (w_{0}; w_{1}, …, w_{m}) obtained by choosing w_{i} = c for a particular i between 0 and m, all other w_{j}’s being equal to ε, while, for m ≠ p, we have

Fix_{NC^{m}(W)}(ϕ^{p}) = {(c; ε, …, ε)},

whence the result. □

Lemma 12. Let W be an irreducible well-generated complex reflection group all of whose degrees are divisible by d. Then each element of W is fixed under conjugation by c^{h/d}.

Proof. By the theorem of Springer cited in the proof of Lemma 10, the subgroup W′ = Cent_{W} (c^{h/d}) is itself a complex reflection group whose degrees are those degrees of W that are divisible by d. Thus, by our assumption, the degrees of W′ coincide with the degrees of W, and hence W′ must be equal to W. Phrased differently, each element of W is fixed under conjugation by c^{h/d}, as claimed. □

Lemma 13. Let W be an irreducible well-generated complex reflection group of rank n, and let p = m_{1}h_{1} be a divisor of mh, where m = m_{1}m_{2} and h = h_{1}h_{2}. Without loss of generality, we assume that gcd(h_{1}, m_{2}) = 1. Suppose that Theorem 2 has already been verified for all irreducible well-generated complex reflection groups with rank < n. If h_{2} does not divide all degrees d_{i}, then Equation (3.3) is satisfied.

Proof. Let us write h_{1} = am_{2} + b, with 0 ≤ b < m_{2}. The condition gcd(h_{1}, m_{2}) = 1 translates into gcd(b, m_{2}) = 1. From (5.1), we infer that

ϕ^{p}((w_{0}; w_{1}, …, w_{m}))

= (∗; c^{a+1}w_{m−m_{1}b+1}c^{−a−1}, c^{a+1}w_{m−m_{1}b+2}c^{−a−1}, …, c^{a+1}w_{m}c^{−a−1},
c^{a}w_{1}c^{−a}, …, c^{a}w_{m−m_{1}b}c^{−a}). (5.8)

Supposing that (w_{0}; w_{1}, …, w_{m}) is fixed by ϕ^{p}, we obtain the system of equations

w_{i} = c^{a+1}w_{i+m−m_{1}b}c^{−a−1}, i = 1, 2, …, m_{1}b,
w_{i} = c^{a}w_{i−m_{1}b}c^{−a}, i = m_{1}b + 1, m_{1}b + 2, …, m,

which, after iteration, implies in particular that

w_{i} = c^{b(a+1)+(m_{2}−b)a}w_{i}c^{−b(a+1)−(m_{2}−b)a} = c^{h_{1}}w_{i}c^{−h_{1}}, i = 1, 2, …, m.

It is at this point where we need gcd(b, m_{2}) = 1. The last equation shows that each w_{i}, i = 1, 2, …, m, and thus also w_{0}, lies in Cent_{W} (c^{h_{1}}). By the theorem of Springer cited in the proof of Lemma 10, this centraliser subgroup is itself a complex reflection group, W′ say, whose degrees are those degrees of W that are divisible by h/h_{1} = h_{2}. Since, by assumption, h_{2} does not divide all degrees, W′ has rank strictly less than n. Again by assumption, we know that Theorem 2 is true for W′, so that in particular,

| Fix_{NC^{m}(W′)}(ϕ^{p})| = Cat^{m}(W′; q)|_{q=e^{2πip/mh}}.

The arguments above together with (5.5) show that Fix_{NC^{m}(W)}(ϕ^{p}) = Fix_{NC^{m}(W′)}(ϕ^{p}). On the other hand, using (5.4) it is straightforward to see that

Cat^{m}(W; q)|_{q=e^{2πip/mh}} = Cat^{m}(W′; q)|_{q=e^{2πip/mh}}.

This proves (3.3) for our particular p, as required. □

Lemma 14. Let W be an irreducible well-generated complex reflection group of rank n, and let p = m_{1}h_{1} be a divisor of mh, where m = m_{1}m_{2} and h = h_{1}h_{2}. We assume that gcd(h_{1}, m_{2}) = 1. If m_{2} > n then

Fix_{NC^{m}(W)}(ϕ^{p}) = {(c; ε, …, ε)}.

Proof. Let us suppose that (w_{0}; w_{1}, …, w_{m}) ∈ Fix_{NC^{m}(W)}(ϕ^{p}) and that there exists a j ≥ 1 such that w_{j} ≠ ε. By (5.8), it then follows for such a j that also w_{k} ≠ ε for all k ≡ j − lm_{1}b (mod m), where, as before, b is defined as the unique integer with h_{1} = am_{2} + b and 0 ≤ b < m_{2}. Since, by assumption, gcd(b, m_{2}) = 1, there are exactly m_{2} such k’s which are distinct mod m. However, this implies that the sum of the absolute lengths of the w_{i}’s, 0 ≤ i ≤ m, is at least m_{2} > n, a contradiction to Remark 1.(2). □

Remark 3. (1) If we put ourselves in the situation of the assumptions of Lemma 13, then we may conclude that equation (3.3) only needs to be checked for pairs (m_{2}, h_{2}) subject to the following restrictions:

m_{2} ≥ 2, gcd(h_{1}, m_{2}) = 1, and h_{2} divides all degrees of W .  (5.9)

Indeed, Lemmas 10 and 13 together imply that equation (3.3) is always satisfied in all other cases.

(2) Still putting ourselves in the situation of Lemma 13, if m_{2} > n and m_{2}h_{2} does not divide any of the degrees of W, then equation (3.3) is satisfied. Indeed, Lemma 14 says that in this case the left-hand side of (3.3) equals 1, while a straightforward computation using (5.4) shows that in this case the right-hand side of (3.3) equals 1 as well.

(3) It should be observed that this leaves a finite number of choices for m_{2} to consider, whence a finite number of choices for (m_{1}, m_{2}, h_{1}, h_{2}). Altogether, there remains a finite number of choices for p = h_{1}m_{1} to be checked.

Lemma 15. Let W be an irreducible well-generated complex reflection group of rank n with the property that d_{i} | h for i = 1, 2, …, n. Then Theorem 2 is true for this group W.

Proof. By Lemma 9, we may restrict ourselves to divisors p of mh.

Suppose that e^{2πip/mh} is a d_{i}-th root of unity for some i. In other words, mh/p divides d_{i}. Since d_{i} is a divisor of h by assumption, the integer mh/p also divides h. But this is equivalent to saying that m divides p, and equation (3.3) holds by Lemma 10.

Now assume that mh/p does not divide any of the d_{i}’s. Then, by (5.4), the righthand side of (3.3) equals 1. On the other hand, (c; ε, …, ε) is always an element of Fix_{NC^{m}(W)}(ϕ^{p}). To see that there are no others, we make appeal to the classification of all irreducible well-generated complex reflection groups, which we recalled in Section 2. Inspection reveals that all groups satisfying the hypotheses of the lemma have rank n ≤ 2. Except for the groups contained in the infinite series G(d, 1, n) and G(e, e, n) for which Theorem 2 has been established in [19], these are the groups G_{5}, G_{6}, G_{9}, G_{10}, G_{14}, G_{17}, G_{18}, G_{21}. We now discuss these groups case by case, keeping the notation of Lemma 13. In order to simplify the argument, we note that Lemma 14 implies that equation (3.3) holds if m_{2} > 2, so that in the following arguments we always may assume that m_{2} = 2.

Case G_{5}. The degrees are 6, 12, and therefore Remark 3.(1) implies that equation (3.3) is always satisfied.

Case G_{6}. The degrees are 4, 12, and therefore, according to Remark 3.(1), we need only consider the case where h_{2} = 4 and m_{2} = 2, that is, p = 3m/2. Then (5.8) becomes

ϕ^{p}((w_{0}; w_{1}, …, w_{m})) = (∗; c^{2}w_{\frac{m}{2} +1}c^{−2}, c^{2}w_{\frac{m}{2} +2}c^{−2}, …, c^{2}w_{m}c^{−2}, cw_{1}c^{−1}, …, cw\frac{m}{2} c^{−1}). (5.10)

If (w_{0}; w_{1}, …, w_{m}) is fixed by ϕ^{p} and not equal to (c; ε, …, ε), there must exist an i with 1 ≤ i ≤ \frac{m}{2} such that ℓ_{T} (w_{i}) = ℓ_{T} (w_{\frac{m}{2} +i}) = 1, w_{\frac{m}{2} +i} = cw_{i}c^{−1}, w_{i}w_{\frac{m}{2} +i} = w_{i}cw_{i}c^{−1} = c, and all w_{j}, with j ≠ i, \frac{m}{2} + i, equal ε. However, with the help of the GAP package CHEVIE [14, 27], one verifies that there is no w_{i} in G_{6} such that

ℓ_{T} (w_{i}) = 1 and w_{i}cw_{i}c^{−1} = c

are simultaneously satisfied. Hence, the left-hand side of (3.3) is equal to 1, as required.

Case G_{9}. The degrees are 8, 24, and therefore, according to Remark 3.(1), we need only consider the case where h_{2} = 8 and m_{2} = 2, that is, p = 3m/2. This is the same p as for G_{6}. Again, CHEVIE finds no solution. Hence, the left-hand side of (3.3) is equal to 1, as required.

Case G_{10}. The degrees are 12, 24, and therefore Remark 3.(1) implies that equation (3.3) is always satisfied.

Case G_{14}. The degrees are 6, 24, and therefore Remark 3.(1) implies that equation (3.3) is always satisfied.

Case G_{17}. The degrees are 20, 60, and therefore, according to Remark 3.(1), we need only consider the cases where h_{2} = 20 or h_{2} = 4. In the first case, p = 3m/2, which is the same p as for G_{6}. Again, CHEVIE finds no solution. In the second case, p = 15m/2. Then (5.8) becomes

ϕ^{p}((w_{0}; w_{1}, …, w_{m}))

= (∗; c^{8}w_{\frac{m}{2} +1}c^{−8}, c^{8}w_{\frac{m}{2} +2}c^{−8}, …, c^{8}w_{m}c^{−8}, c^{7}w_{1}c^{−7}, …, c^{7}w\frac{m}{2} c^{−7}). (5.11)

By Lemma 12, every element of NC(W) is fixed under conjugation by c^{3}, and, thus, on elements fixed by ϕ^{p}, the above action of ϕ^{p} reduces to the one in (5.10). This action was already discussed in the first case. Hence, in both cases, the left-hand side of (3.3) is equal to 1, as required.

Case G_{18}. The degrees are 30, 60, and therefore Remark 3.(1) implies that equation (3.3) is always satisfied.

Case G_{21}. The degrees are 12, 60, and therefore, according to Remark 3.(1), we need only consider the cases where h_{2} = 12 or h_{2} = 4. In the first case, p = 5m/2, so that (5.8) becomes

ϕ^{p}((w_{0}; w_{1}, …, w_{m}))

= (∗; c^{3}w_{\frac{m}{2} +1}c^{−3}, c^{3}w_{\frac{m}{2} +2}c^{−3}, …, c^{3}w_{m}c^{−3}, c^{2}w_{1}c^{−2}, …, c^{2}w\frac{m}{2} c^{−2}). (5.12)

If (w_{0}; w_{1}, …, w_{m}) is fixed by ϕ^{p} and not equal to (c; ε, …, ε), there must exist an i with 1 ≤ i ≤ \frac{m}{2} such that ℓ_{T} (w_{i}) = 1 and w_{i}c^{2}w_{i}c^{−2} = c. However, with the help of the GAP package CHEVIE [14, 27], one verifies that there is no such solution to this equation. In the second case, p = 15m/2. Then (5.8) becomes the action in (5.11). By Lemma 12, every element of NC(W) is fixed under conjugation by c^{5}, and, thus, on elements fixed by ϕ^{p}, the action of ϕ^{p} in (5.11) reduces to the one in the first case. Hence, in both cases, the left-hand side of (3.3) is equal to 1, as required.

This completes the proof of the lemma. □

6. Exemplification of case-by-case verification of Theorem 2

It remains to verify Theorem 2 for the groups G_{4}, G_{8}, G_{16}, G_{20}, G_{23} = H_{3}, G_{24}, G_{25}, G_{26}, G_{27}, G_{28} = F_{4}, G_{29}, G_{30} = H_{4}, G_{32}, G_{33}, G_{34}, G_{35} = E_{6}, G_{36} = E_{7}, G_{37} = E_{8}. All details can be found in [21, Sec. 6]. We content ourselves with illustrating the type of computation that is needed here by going through the case of the group G_{24}, and by discussing some of the arguments needed for the group G_{37} = E_{8}.

In the sequel we write ζ_{d} for a primitive d-th root of unity.

Case G_{24}. The degrees are 4, 6, 14, and hence we have

Cat^{m}(G_{24}; q) = \frac{[14m + 14]_{q} [14m + 6]_{q} [14m + 4]_{q}}{[14]_{q} [6]_{q} [4]_{q}} .

Let ζ be a 14m-th root of unity. In what follows, we abbreviate the assertion that “ζ is a primitive d-th root of unity” as “ζ = ζ_{d}.” The following cases on the right-hand side of (3.3) occur:

lim_{q→ζ} Cat^{m}(G_{24}; q) = m + 1, if ζ = ζ_{14}, ζ_{7},  (6.1a)
lim_{q→ζ} Cat^{m}(G_{24}; q) = \frac{7m+3}{3}, if ζ = ζ_{6}, ζ_{3}, 3 | m,  (6.1b)
lim_{q→ζ} Cat^{m}(G_{24}; q) = \frac{7m+2}{2}, if ζ = ζ_{4}, 2 | m,  (6.1c)
lim_{q→ζ} Cat^{m}(G_{24}; q) = Cat^{m}(G_{24}), if ζ = −1 or ζ = 1,  (6.1d)
lim_{q→ζ} Cat^{m}(G_{24}; q) = 1, otherwise.  (6.1e)

We must now prove that the left-hand side of (3.3) in each case agrees with the values exhibited in (6.1). The only cases not covered by Lemma 10 are the ones in (6.1b), (6.1c), and (6.1e). (In both (6.1a) and (6.1d) we have d | h.)

We first consider (6.1b). By Lemma 9, we are free to choose p = 7m/3 if ζ = ζ_{6}, respectively p = 14m/3 if ζ = ζ_{3}. In both cases, m must be divisible by 3.

We start with the case that p = 7m/3. From (5.1), we infer

ϕ^{p}((w_{0}; w_{1}, …, w_{m}))

= (∗; c^{3}w_{\frac{2m}{3} +1}c^{−3}, c^{3}w_{\frac{2m}{3} +2}c^{−3}, …, c^{3}w_{m}c^{−3}, c^{2}w_{1}c^{−2}, …, c^{2}w_{\frac{2m}{3}} c^{−2}).

Supposing that (w_{0}; w_{1}, …, w_{m}) is fixed by ϕ^{p}, we obtain the system of equations

w_{i} = c^{3}w_{\frac{2m}{3} +i}c^{−3}, i = 1, 2, …, \frac{m}{3},  (6.2a)
w_{i} = c^{2}w_{i− \frac{m}{3}} c^{−2}, i = \frac{m}{3} + 1, \frac{m}{3} + 2, …, m.  (6.2b)

There are two distinct possibilities for choosing the w_{i}’s, 1 ≤ i ≤ m: either all the w_{i}’s are equal to ε, or there is an i with 1 ≤ i ≤ \frac{m}{3} such that

ℓ_{T} (w_{i}) = ℓ_{T} (w_{i+ \frac{m}{3}} ) = ℓ_{T} (w_{i+ \frac{2m}{3}} ) = 1.

Writing t_{1}, t_{2}, t_{3} for w_{i}, w_{i+ \frac{m}{3}} , w_{i+ \frac{2m}{3}} , respectively, the equations (6.2) reduce to

t_{1} = c^{3}t_{3}c^{−3},  (6.3a)
t_{2} = c^{2}t_{1}c^{−2},  (6.3b)
t_{3} = c^{2}t_{2}c^{−2}.  (6.3c)

One of these equations is in fact superfluous: if we substitute (6.3b) and (6.3c) in (6.3a), then we obtain t_{1} = c^{7}t_{1}c^{−7} which is automatically satisfied due to Lemma 12 with d = 2.

Since (w_{0}; w_{1}, …, w_{m}) ∈ NC^{m}(G_{24}), we must have t_{1}t_{2}t_{3} = c. Combining this with (6.3), we infer that

t_{1}(c^{2}t_{1}c^{−2})(c^{4}t_{1}c^{−4}) = c.  (6.4)

With the help of CHEVIE, one obtains 7 solutions for t_{1} in this equation, each of them giving rise to m/3 elements of Fix_{NC^{m}(G_{24})}(ϕ^{p}) since i (in w_{i}) ranges from 1 to m/3.

In total, we obtain 1 + 7\frac{m}{3} = \frac{7m+3}{3} elements in Fix_{NC^{m}(G_{24})}(ϕ^{p}), which agrees with the limit in (6.1b).

The case where p = 14m/3 can be treated in a similar fashion. In the end, it turns out that we have to solve the same enumeration problem as for p = 7m/3, and, consequently, the number of elements of Fix_{NC^{m}(G_{24})}(ϕ^{p}) is the same, namely \frac{7m+3}{3}, as required.

Our next case is (6.1c). Proceeding in a similar manner as before, we see that there is again the trivial possibility (c; ε, …, ε), and otherwise we have to find t_{1} with ℓ_{T} (t_{1}) = 1 satisfying the inequality

t_{1}(c^{3}t_{1}c^{−3}) ≤_{T} c.  (6.5)

With the help of CHEVIE, one obtains 7 solutions for t_{1} in this relation, each of them giving rise to m/2 elements of Fix_{NC^{m}(G_{24})}(ϕ^{p}) since i (in w_{i}) ranges from 1 to m/2.

In total, we obtain 1 + 7\frac{m}{2} = \frac{7m+2}{2} elements in Fix_{NC^{m}(G_{24})}(ϕ^{p}), which agrees with the limit in (6.1c).

Finally, we turn to (6.1e). By Remark 3, the only choices for h_{2} and m_{2} to be considered are h_{2} = 1 and m_{2} = 3, h_{2} = m_{2} = 2, and h_{2} = 2 and m_{2} = 3. These correspond to the choices p = 14m/3, p = 7m/2, respectively p = 7m/3, all of which have already been discussed as they do not belong to (6.1e). Hence, (3.3) must necessarily hold, as required.

Case G_{37} = E_{8}. The degrees are 2, 8, 12, 14, 18, 20, 24, 30, and hence we have

Cat^{m}(E_{8}; q) = \frac{[30m + 30]_{q} [30m + 24]_{q} [30m + 20]_{q} [30m + 18]_{q}}{[30]_{q} [24]_{q} [20]_{q} [18]_{q}}

× \frac{[30m + 14]_{q} [30m + 12]_{q} [30m + 8]_{q} [30m + 2]_{q}}{[14]_{q} [12]_{q} [8]_{q} [2]_{q}} .

Let ζ be a 30m-th root of unity. The cases occurring on the right-hand side of (3.3) not covered by Lemma 10 are:

lim_{q→ζ} Cat^{m}(E_{8}; q) = \frac{5m+4}{4}, if ζ = ζ_{24}, 4 | m,  (6.6a)
lim_{q→ζ} Cat^{m}(E_{8}; q) = \frac{3m+2}{2}, if ζ = ζ_{20}, 2 | m,  (6.6b)
lim_{q→ζ} Cat^{m}(E_{8}; q) = \frac{5m+3}{3}, if ζ = ζ_{18}, ζ_{9}, 3 | m,  (6.6c)
lim_{q→ζ} Cat^{m}(E_{8}; q) = \frac{15m+7}{7}, if ζ = ζ_{14}, ζ_{7}, 7 | m,  (6.6d)
lim_{q→ζ} Cat^{m}(E_{8}; q) = \frac{(5m+4)(5m+2)}{8}, if ζ = ζ_{12}, 2 | m,  (6.6e)

lim_{q→ζ} Cat^{m}(E_{8}; q) = \frac{(5m + 4)(15m + 4)}{16}, if ζ = ζ_{8}, 4 | m,  (6.6f)
lim_{q→ζ} Cat^{m}(E_{8}; q) = \frac{(5m + 4)(3m + 2)(5m + 2)(15m + 4)}{64}, if ζ = ζ_{4}, 2 | m, (6.6g)
lim_{q→ζ} Cat^{m}(E_{8}; q) = Cat^{m}(E_{8}), if ζ = −1 or ζ = 1,  (6.6h)
lim_{q→ζ} Cat^{m}(E_{8}; q) = 1, otherwise.  (6.6i)

We now have to prove that the left-hand side of (3.3) in each case agrees with the values exhibited in (6.6). Since the corresponding computations in the various cases are very similar, we concentrate here only on the cases (6.6f) and (6.6g), these two being representative of the types of arguments arising. As before, we refer the reader to [21, Sec. 6] for full details.

Let us consider the case in (6.6f) first. By Lemma 9, we are free to choose p = 15m/4. In particular, m must be divisible by 4. From (5.1), we infer

ϕ^{p}((w_{0}; w_{1}, …, w_{m}))

= (∗; c^{4}w_{\frac{m}{4} +1}c^{−4}, c^{4}w_{\frac{m}{4} +2}c^{−4}, …, c^{4}w_{m}c^{−4}, c^{3}w_{1}c^{−3}, …, c^{3}w\frac{m}{4} c^{−3}).

Supposing that (w_{0}; w_{1}, …, w_{m}) is fixed by ϕ^{p}, we obtain the system of equations

w_{i} = c^{4}w_{\frac{m}{4} +i}c^{−4}, i = 1, 2, …, \frac{3m}{4},  (6.7a)
w_{i} = c^{3}w_{i− \frac{3m}{4}} c^{−3}, i = \frac{3m}{4} + 1, \frac{3m}{4} + 2, …, m.  (6.7b)

There are several distinct possibilities for choosing the w_{i}’s, 1 ≤ i ≤ m, which we summarise as follows:

(i) all the w_{i}’s are equal to ε (and w_{0} = c), (ii) there is an i with 1 ≤ i ≤ \frac{m}{4} such that

1 ≤ ℓ_{T} (w_{i}) = ℓ_{T} (w_{i+ \frac{m}{4}} ) = ℓ_{T} (w_{i+ \frac{2m}{4}} ) = ℓ_{T} (w_{i+ \frac{3m}{4}} ) ≤ 2,  (6.8a)

and the other w_{j}’s, 1 ≤ j ≤ m, are equal to ε, (iii) there are i_{1} and i_{2} with 1 ≤ i_{1} < i_{2} ≤ \frac{m}{4} such that

ℓ_{T} (w_{i_{1}}) = ℓ_{T} (w_{i_{2}}) = ℓ_{T} (w_{i_{1}+ \frac{m}{4}} ) = ℓ_{T} (w_{i_{2}+ \frac{m}{4}} ) = ℓ_{T} (w_{i_{1}+ \frac{2m}{4}} ) = ℓ_{T} (w_{i_{2}+ \frac{2m}{4}} ) = ℓ_{T} (w_{i_{1}+ \frac{3m}{4}} ) = ℓ_{T} (w_{i_{2}+ \frac{3m}{4}} ) = 1, (6.8b)

and all other w_{j} are equal to ε. Moreover, since (w_{0}; w_{1}, …, w_{m}) ∈ NC^{m}(E_{8}), we must have

w_{i}w_{i+ \frac{m}{4}} w_{i+ \frac{2m}{4}} w_{i+ \frac{3m}{4}} ≤_{T} c,

or

w_{i_{1}}w_{i_{2}}w_{i_{1}+ \frac{m}{4}} w_{i_{2}+ \frac{m}{4}} w_{i_{1}+ \frac{2m}{4}} w_{i_{2}+ \frac{2m}{4}} w_{i_{1}+ \frac{3m}{4}} w_{i_{2}+ \frac{3m}{4}} = c.

Together with equations (6.7)–(6.8), this implies that

w_{i} = c^{15}w_{i}c^{−15} and w_{i}(c^{11}w_{i}c^{−11})(c^{7}w_{i}c^{−7})(c^{3}w_{i}c^{−3}) ≤_{T} c,  (6.9)

or that

w_{i_{1}} = c^{15}w_{i_{1}}c^{−15}, w_{i_{1}} = c^{15}w_{i_{2}}c^{−15},

and w_{i_{1}}w_{i_{2}}(c^{11}w_{i_{1}}c^{−11})(c^{11}w_{i_{2}}c^{−11})(c^{7}w_{i_{1}}c^{−7})(c^{7}w_{i_{2}}c^{−7})(c^{3}w_{i_{1}}c^{−3})(c^{3}w_{i_{2}}c^{−3}) = c. (6.10)

Here, the first equation in (6.9) and the first two equations in (6.10) are automatically satisfied due to Lemma 12 with d = 2.

With the help of Stembridge’s Maple package coxeter [37], one obtains 30 solutions for w_{i} in (6.9) with ℓ_{T} (w_{i}) = 1, 45 solutions for w_{i} with ℓ_{T} (w_{i}) = 2 and w_{i} of type A_{1}^{2} (as a parabolic Coxeter element; see the end of Section 2), and 20 solutions for w_{i} with ℓ_{T} (w_{i}) = 2 and w_{i} of type A_{2}. Each of them gives rise to m/4 elements of Fix_{NC^{m}(E_{8})}(ϕ^{p}) since i ranges from 1 to m/4.

The number of solutions in Case (iii) can be computed from our knowledge of the solutions in Case (ii) according to type, using some elementary counting arguments. Namely, the number of solutions of (6.10) is equal to

45 · 2 + 20 · 3 = 150,

since an element of type A_{1}^{2} can be decomposed in two ways into a product of two elements of absolute length 1, while for an element of type A_{2} this can be done in 3 ways.

In total, we obtain 1 + (30 + 45 + 20)\frac{m}{4} + 150\binom{m/4}{2} = \frac{(5m+4)(15m+4)}{16} elements in Fix_{NC^{m}(E_{8})}(ϕ^{p}), which agrees with the limit in (6.6f).

Next, we discuss the case in (6.6g). By Lemma 9, we are free to choose p = 15m/2. In particular, m must be divisible by 2. From (5.1), we infer

ϕ^{p}((w_{0}; w_{1}, …, w_{m}))

= (∗; c^{8}w_{\frac{m}{2} +1}c^{−8}, c^{8}w_{\frac{m}{2} +2}c^{−8}, …, c^{8}w_{m}c^{−8}, c^{7}w_{1}c^{−7}, …, c^{7}w\frac{m}{2} c^{−7}).

Supposing that (w_{0}; w_{1}, …, w_{m}) is fixed by ϕ^{p}, we obtain the system of equations

w_{i} = c^{8}w_{\frac{m}{2} +i}c^{−8}, i = 1, 2, …, \frac{m}{2},  (6.11a)
w_{i} = c^{7}w_{i− \frac{m}{2}} c^{−7}, i = \frac{m}{2} + 1, \frac{m}{2} + 2, …, m.  (6.11b)

There are several distinct possibilities for choosing the w_{i}’s, 1 ≤ i ≤ m:

(i) all the w_{i}’s are equal to ε (and w_{0} = c), (ii) there is an i with 1 ≤ i ≤ \frac{m}{2} such that

1 ≤ ℓ_{T} (w_{i}) = ℓ_{T} (w_{i+ \frac{m}{2}} ) ≤ 4,  (6.12a)

and the other w_{j}’s, 1 ≤ j ≤ m, are equal to ε, (iii) there are i_{1} and i_{2} with 1 ≤ i_{1} < i_{2} ≤ \frac{m}{2} such that

ℓ_{1} := ℓ_{T} (w_{i_{1}}) = ℓ_{T} (w_{i_{1}+ \frac{m}{2}} ) ≥ 1, ℓ_{2} := ℓ_{T} (w_{i_{2}}) = ℓ_{T} (w_{i_{2}+ \frac{m}{2}} ) ≥ 1, and ℓ_{1} + ℓ_{2} ≤ 4,

(6.12b)

and the other w_{j}’s, 1 ≤ j ≤ m, are equal to ε, (iv) there are i_{1}, i_{2}, i_{3} with 1 ≤ i_{1} < i_{2} < i_{3} ≤ \frac{m}{2} such that

ℓ_{1} := ℓ_{T} (w_{i_{1}}) = ℓ_{T} (w_{i_{1}+ \frac{m}{2}} ) ≥ 1, ℓ_{2} := ℓ_{T} (w_{i_{2}}) = ℓ_{T} (w_{i_{2}+ \frac{m}{2}} ) ≥ 1, ℓ_{3} := ℓ_{T} (w_{i_{3}}) = ℓ_{T} (w_{i_{3}+ \frac{m}{2}} ) ≥ 1, and ℓ_{1} + ℓ_{2} + ℓ_{3} ≤ 4, (6.12c)

and the other w_{j}’s, 1 ≤ j ≤ m, are equal to ε,

(v) there are i_{1}, i_{2}, i_{3}, i_{4} with 1 ≤ i_{1} < i_{2} < i_{3} < i_{4} ≤ \frac{m}{2} such that

ℓ_{T} (w_{i_{1}}) = ℓ_{T} (w_{i_{2}}) = ℓ_{T} (w_{i_{3}}) = ℓ_{T} (w_{i_{4}})

= ℓ_{T} (w_{i_{1}+ \frac{m}{2}} ) = ℓ_{T} (w_{i_{2}+ \frac{m}{2}} ) = ℓ_{T} (w_{i_{3}+ \frac{m}{2}} ) = ℓ_{T} (w_{i_{4}+ \frac{m}{2}} ) = 1, (6.12d)

and all other w_{j}’s are equal to ε. Moreover, since (w_{0}; w_{1}, …, w_{m}) ∈ NC^{m}(E_{8}), we must have w_{i}w_{i+ \frac{m}{2}} ≤_{T} c, respec-

tively w_{i_{1}}w_{i_{2}}w_{i_{1}+ \frac{m}{2}} w_{i_{2}+ \frac{m}{2}} ≤_{T} c, respectively

w_{i_{1}}w_{i_{2}}w_{i_{3}}w_{i_{1}+ \frac{m}{2}} w_{i_{2}+ \frac{m}{2}} w_{i_{3}+ \frac{m}{2}} ≤_{T} c,

respectively

w_{i_{1}}w_{i_{2}}w_{i_{3}}w_{i_{4}}w_{i_{1}+ \frac{m}{2}} w_{i_{2}+ \frac{m}{2}} w_{i_{3}+ \frac{m}{2}} w_{i_{4}+ \frac{m}{2}} = c.

Together with equations (6.11)–(6.12), this implies that

w_{i} = c^{15}w_{i}c^{−15} and w_{i}(c^{7}w_{i}c^{−7}) ≤_{T} c,  (6.13)

respectively that

w_{i_{1}} = c^{15}w_{i_{1}}c^{−15}, w_{i_{2}} = c^{15}w_{i_{2}}c^{−15}, and w_{i_{1}}w_{i_{2}}(c^{7}w_{i_{1}}c^{−7})(c^{7}w_{i_{2}}c^{−7}) ≤_{T} c, (6.14)

respectively that

w_{i_{1}} = c^{15}w_{i_{1}}c^{−15}, w_{i_{2}} = c^{15}w_{i_{2}}c^{−15}, w_{i_{3}} = c^{15}w_{i_{3}}c^{−15},

and w_{i_{1}}w_{i_{2}}w_{i_{3}}(c^{7}w_{i_{1}}c^{−7})(c^{7}w_{i_{2}}c^{−7})(c^{7}w_{i_{3}}c^{−7}) ≤_{T} c, (6.15)

respectively that

w_{i_{1}} = c^{15}w_{i_{1}}c^{−15}, w_{i_{2}} = c^{15}w_{i_{2}}c^{−15}, w_{i_{3}} = c^{15}w_{i_{3}}c^{−15}, w_{i_{4}} = c^{15}w_{i_{4}}c^{−15},

and w_{i_{1}}w_{i_{2}}w_{i_{3}}w_{i_{4}}(c^{7}w_{i_{1}}c^{−7})(c^{7}w_{i_{2}}c^{−7})(c^{7}w_{i_{3}}c^{−7})(c^{7}w_{i_{4}}c^{−7}) = c. (6.16)

Here, the first equation in (6.13), the first two in (6.14), the first three in (6.15), and the first four in (6.16), are all automatically satisfied due to Lemma 12 with d = 2.

With the help of Stembridge’s Maple package coxeter [37], one obtains

— 45 solutions for w_{i} in (6.13) with ℓ_{T} (w_{i}) = 1,

— 150 solutions for w_{i} in (6.13) with ℓ_{T} (w_{i}) = 2 and w_{i} of type A_{1}^{2},

— 100 solutions for w_{i} in (6.13) with ℓ_{T} (w_{i}) = 2 and w_{i} of type A_{2},

— 75 solutions for w_{i} in (6.13) with ℓ_{T} (w_{i}) = 3 and w_{i} of type A_{1}^{3},

— 165 solutions for w_{i} in (6.13) with ℓ_{T} (w_{i}) = 3 and w_{i} of type A_{1} ∗ A_{2},

— 90 solutions for w_{i} in (6.13) with ℓ_{T} (w_{i}) = 3 and w_{i} of type A_{3},

— 15 solutions for w_{i} in (6.13) with ℓ_{T} (w_{i}) = 4 and w_{i} of type A_{1}^{2} ∗ A_{2},

— 45 solutions for w_{i} in (6.13) with ℓ_{T} (w_{i}) = 4 and w_{i} of type A_{1} ∗ A_{3};

— 5 solutions for w_{i} in (6.13) with ℓ_{T} (w_{i}) = 4 and w_{i} of type A_{2}^{2},

— 18 solutions for w_{i} in (6.13) with ℓ_{T} (w_{i}) = 4 and w_{i} of type A_{4},

— 5 solutions for w_{i} in (6.13) with ℓ_{T} (w_{i}) = 4 and w_{i} of type D_{4}. Each of them gives rise to m/2 elements of Fix_{NC^{m}(E_{8})}(ϕ^{p}) since i ranges from 1 to m/2. There are no solutions for w_{i} in (6.13) with w_{i} of type A_{1}^{4}.

Letting the computer find all solutions in cases (iii)–(v) would take years. However, the number of these solutions can be computed from our knowledge of the solutions in Case (ii) according to type, if this information is combined with the decomposition numbers in the sense of [17, 18, 20] (see the end of Section 2) and some elementary (multiset) permutation counting. The decomposition numbers for A_{2}, A_{3}, A_{4}, and D_{4} of which we make use can be found in the appendix of [18].

To begin with, the number of solutions of (6.14) with ℓ_{1} = ℓ_{2} = 1 is equal to

n_{1,1} := 150 · 2 + 100 · N_{A_{2}}(A_{1}, A_{1}) = 600,

since an element of type A_{1}^{2} can be decomposed in two ways into a product of two elements of absolute length 1, while for an element of type A_{2} this can be done in N_{A_{2}}(A_{1}, A_{1}) = 3 ways. Similarly, the number of solutions of (6.14) with ℓ_{1} = 2 and ℓ_{2} = 1 is equal to

n_{2,1} := 75 · 3 + 165 · (1 + N_{A_{2}}(A_{1}, A_{1})) + 90 · N_{A_{3}}(A_{2}, A_{1}) = 1425,

the number of solutions of (6.14) with ℓ_{1} = 3 and ℓ_{2} = 1 is equal to

n_{3,1} := 15 · (2 + N_{A_{2}}(A_{1}, A_{1})) + 45 · (1 + N_{A_{3}}(A_{2}, A_{1})) + 5 · (2N_{A_{2}}(A_{1}, A_{1}))

+ 18 · (N_{A_{4}}(A_{3}, A_{1}) + N_{A_{4}}(A_{1} ∗ A_{2}, A_{1})) + 5 · (N_{D_{4}}(A_{3}, A_{1}) + N_{D_{4}}(A_{1}^{3}, A_{1})) = 660,

the number of solutions of (6.14) with ℓ_{1} = ℓ_{2} = 2 is equal to

n_{2,2} := 15 · (2 + 2N_{A_{2}}(A_{1}, A_{1})) + 45 · (2N_{A_{3}}(A_{2}, A_{1})) + 5 · (2 + N_{A_{2}}(A_{1}, A_{1})^{2})

+ 18 · (N_{A_{4}}(A_{2}, A_{2}) + N_{A_{4}}(A_{1}^{2}, A_{1}^{2}) + 2N_{A_{4}}(A_{2}, A_{1}^{2}))

+ 5 · (N_{D_{4}}(A_{2}, A_{2}) + 2N_{D_{4}}(A_{2}, A_{1}^{2})) = 1195,

the number of solutions of (6.15) with ℓ_{1} = ℓ_{2} = ℓ_{3} = 1 is equal to

n_{1,1,1} := 75 · 3! + 165 · (3N_{A_{2}}(A_{1}, A_{1})) + 90N_{A_{3}}(A_{1}, A_{1}, A_{1}) = 3375,

the number of solutions of (6.15) with ℓ_{1} = 2 and ℓ_{2} = ℓ_{3} = 1 is equal to

n_{2,1,1} := 15·(2+N_{A_{2}}(A_{1}, A_{1})+2·2·N_{A_{2}}(A_{1}, A_{1}))+45·(2N_{A_{3}}(A_{2}, A_{1})+N_{A_{3}}(A_{1}, A_{1}, A_{1}))

+ 5 · (2N_{A_{2}}(A_{1}, A_{1}) + 2N_{A_{2}}(A_{1}, A_{1})^{2}) + 18 · (N_{A_{4}}(A_{2}, A_{1}, A_{1}) + N_{A_{4}}(A_{1}^{2}, A_{1}, A_{1}))

+ 5 · (N_{D_{4}}(A_{2}, A_{1}, A_{1}) + N_{D_{4}}(A_{1}^{2}, A_{1}, A_{1})) = 2850,

and the number of solutions of (6.16) is equal to

n_{1,1,1,1} := 15 · (12N_{A_{2}}(A_{1}, A_{1})) + 45 · (4N_{A_{3}}(A_{1}, A_{1}, A_{1})) + 5 · (6N_{A_{2}}(A_{1}, A_{1})^{2}) + 18 · N_{A_{4}}(A_{1}, A_{1}, A_{1}, A_{1}) + 5 · N_{D_{4}}(A_{1}, A_{1}, A_{1}, A_{1}) = 6750.

In total, we obtain

1+(45+150+100+75+165+90+15+45+5+18+5)\frac{m}{2}+(n_{1,1}+2n_{2,1}+2n_{3,1}+n_{2,2})\binom{m/2}{2}

+ (n_{1,1,1} + 3n_{2,1,1})\binom{m/2}{3} + n_{1,1,1,1}\binom{m/2}{4} = \frac{(5m + 4)(3m + 2)(5m + 2)(15m + 4)}{64}

elements in Fix_{NC^{m}(E_{8})}(ϕ^{p}), which agrees with the limit in (6.6g).

7. Cyclic sieving II

In this section we present the second cyclic sieving conjecture due to Bessis and Reiner [10, Conj. 6.5].

Let ψ : NC^{m}(W) → NC^{m}(W) be the map defined by

(w_{0}; w_{1}, …, w_{m}) ↦ (cw_{m}c^{−1}; w_{0}, w_{1}, …, w_{m−1}).  (7.1)

For m = 1, we have w_{0} = cw_{1}^{−1}, so that this action reduces to the inverse of the Kreweras complement K_{id}^{c} as defined by Armstrong [3, Def. 2.5.3].

It is easy to see that ψ^{(m+1)h} acts as the identity, where h is the Coxeter number of W (see (8.1) below). By slight abuse of notation as before, let C_{2} be the cyclic group of order (m + 1)h generated by ψ.

Given these definitions, we are now in the position to state the second cyclic sieving conjecture of Bessis and Reiner. By the results of [19] and of this paper, it becomes the following theorem.

Theorem 16. For an irreducible well-generated complex reflection group W and any m ≥ 1, the triple (NC^{m}(W), Cat^{m}(W; q), C_{2}), where Cat^{m}(W; q) is the q-analogue of the Fuß–Catalan number defined in (3.2), exhibits the cyclic sieving phenomenon.

By definition of the cyclic sieving phenomenon, we have to prove that

| Fix_{NC^{m}(W)}(ψ^{p})| = Cat^{m}(W; q)|_{q=e^{2πip/(m+1)h}},  (7.2)

for all p in the range 0 ≤ p < (m + 1)h.

8. Auxiliary results II

This section collects several auxiliary results which allow us to reduce the problem of proving Theorem 16, respectively the equivalent statement (7.2), for the 26 exceptional groups listed in Section 2 to a finite problem. The corresponding lemmas, Lemmas 17– 22, are analogues of Lemmas 9–11 and 13–15 in Section 5.

Let p = a(m + 1) + b, 0 ≤ b < m + 1. We have

ψ^{p}((w_{0}; w_{1}, …, w_{m}))

= (c^{a+1}w_{m−b+1}c^{−a−1}; c^{a+1}w_{m−b+2}c^{−a−1}, …, c^{a+1}w_{m}c^{−a−1},
c^{a}w_{0}c^{−a}, …, c^{a}w_{m−b}c^{−a}). (8.1)

Lemma 17. It suffices to check (7.2) for p a divisor of (m+1)h. More precisely, let p be a divisor of (m + 1)h, and let k be another positive integer with gcd(k, (m + 1)h/p) = 1, then we have

Cat^{m}(W; q)|_{q=e^{2πip/(m+1)h}} = Cat^{m}(W; q)|_{q=e^{2πikp/(m+1)h}}  (8.2)

and

| Fix_{NC^{m}(W)}(ψ^{p})| = | Fix_{NC^{m}(W)}(ψ^{kp})|.  (8.3)

Proof. For (8.3), this follows in the same way as (5.3) in Lemma 9.

For (8.2), we must argue differently than in Lemma 9. Let us write ζ = e^{2πip/(m+1)h}. For a given group W, we write S_{1}(W) for the set of all indices i such that ζ^{d_{i}−h} = 1, and we write S_{2}(W) for the set of all indices i such that ζ^{d_{i}} = 1. By the rule of de l’Hospital, we have

Cat^{m}(W; q)|_{q=e^{2πip/(m+1)h}} = \begin{cases}0 & if |S_{1}(W)| > |S_{2}(W)|, \\ \frac{∏_{i∈S_{1}(W)}(mh+d_{i})}{∏_{i∈S_{2}(W)} d_{i}} \frac{∏_{i∉S_{1}(W)}(1−ζ^{d_{i}−h})}{∏_{i∉S_{2}(W)}(1−ζ^{d_{i}})}, & if |S_{1}(W)| = |S_{2}(W)|. \end{cases}

(8.4)

Since, by Theorem 8, Cat^{m}(W; q) is a polynomial in q, the case |S_{1}(W)| < |S_{2}(W)| cannot occur.

We claim that, for the case where |S_{1}(W)| = |S_{2}(W)|, the factors in the quotient of products

\frac{∏_{i∉S_{1}(W)}(1 − ζ^{d_{i}−h})}{∏_{i∉S_{2}(W)}(1 − ζ^{d_{i}})}

cancel pairwise. If we assume the correctness of the claim, it is obvious that we get the same result if we replace ζ by ζ^{k}, where gcd(k, (m + 1)h/p) = 1, hence establishing (8.2).

In order to see that our claim is indeed valid, we proceed in a case-by-case fashion, making appeal to the classification of irreducible well-generated complex reflection groups, which we recalled in Section 2. First of all, since d_{n} = h, the set S_{1}(W) is always non-empty as it contains the element n. Hence, if we want to have |S_{1}(W)| = |S_{2}(W)|, the set S_{2}(W) must be non-empty as well. In other words, the integer (m + 1)h/p must divide at least one of the degrees d_{1}, d_{2}, …, d_{n}. In particular, this implies that, for each fixed reflection group W of exceptional type, only a finite number of values of (m + 1)h/p has to be checked. Writing M for (m + 1)h/p, what needs to be checked is whether the multisets (that is, multiplicities of elements must be taken into account)

{(d_{i} − h) mod M : i ∉ S_{1}(W)} and {d_{i} mod M : i ∉ S_{2}(W)}

are the same. Since, for a fixed irreducible well-generated complex reflection group, there is only a finite number of possibilities for M, this amounts to a routine verification.

□

Lemma 18. Let p be a divisor of (m + 1)h. If p is divisible by m + 1, then (7.2) is true.

We leave the proof to the reader as it is completely analogous to the proof of Lemma 10.

Lemma 19. Equation (7.2) holds for all divisors p of m + 1.

Proof. We have

Cat^{m}(W; q)|_{q=e^{2πip/(m+1)h}} = \begin{cases}0 & if p < m + 1, \\ m + 1 & if p = m + 1. \end{cases}

Here, the first case follows from (8.4) and the fact that we have S_{1}(W) ⊇ {n} and S_{2}(W) = ∅ if p | (m + 1) and p < m + 1.

On the other hand, if (w_{0}; w_{1}, …, w_{m}) is fixed by ψ^{p}, then one can apply an argument similar to that in Lemma 11 with any w_{i} taking the role of w_{1}, 0 ≤ i ≤ m. It follows that if p = m+1, the set Fix_{NC^{m}(W)}(ψ^{p}) consists of the m+1 elements (w_{0}; w_{1}, …, w_{m}) obtained by choosing w_{i} = c for a particular i between 0 and m, all other w_{j}’s being equal to ε. If p < m + 1, then there is no element in Fix_{NC^{m}(W)}(ψ^{p}). □

Lemma 20. Let W be an irreducible well-generated complex reflection group of rank n, and let p = m_{1}h_{1} be a divisor of (m + 1)h, where m + 1 = m_{1}m_{2} and h = h_{1}h_{2}. We assume that gcd(h_{1}, m_{2}) = 1. Suppose that Theorem 16 has already been verified for all irreducible well-generated complex reflection groups with rank < n. If h_{2} does not divide all degrees d_{i}, then equation (7.2) is satisfied.

We leave the proof to the reader as it is completely analogous to the proof of Lemma 13.

Lemma 21. Let W be an irreducible well-generated complex reflection group of rank n, and let p = m_{1}h_{1} be a divisor of (m + 1)h, where m + 1 = m_{1}m_{2} and h = h_{1}h_{2}. We assume that gcd(h_{1}, m_{2}) = 1. If m_{2} > n then

Fix_{NC^{m}(W)}(ψ^{p}) = ∅.

We leave the proof to the reader as it is analogous to the proof of Lemma 14.

Remark 4. By applying the same reasoning as in Remark 3 with Lemmas 13 and 14 replaced by Lemmas 20 and 21, respectively, it follows that we only need to check (7.2) for pairs (m_{2}, h_{2}) satisfying (5.9) and m_{2} ≤ n. This reduces the problem to a finite number of choices.

Lemma 22. Let W be an irreducible well-generated complex reflection group of rank n with the property that d_{i} | h for i = 1, 2, …, n. Then Theorem 16 is true for this group W.

Proof. Proceeding in a fashion analogous to the beginning of the proof of Lemma 15, we may restrict to the case where p | (m+1)h and (m+1)h/p does not divide any of the d_{i}’s. In this case, it follows from (8.4) and the fact that we have S_{1}(W) ⊇ {n} and S_{2}(W) = ∅ that the right-hand side of (7.2) equals 0. Inspection of the classification of all irreducible well-generated complex reflection groups, which we recalled in Section 2, reveals that all groups satisfying the hypotheses of the lemma have rank n ≤ 2. Except for the groups contained in the infinite series G(d, 1, n) and G(e, e, n) for which Theorem 2 has been established in [19], these are the groups G_{5}, G_{6}, G_{9}, G_{10}, G_{14}, G_{17}, G_{18}, G_{21}. The verification of (7.2) can be done in a similar fashion as in the proof of Lemma 15. We illustrate this by going through the case of the group G_{6}. In analogy with the earlier situation, we note that Lemma 21 implies that equation (7.2) holds if m_{2} > 2, so that in the following arguments we may assume that m_{2} = 2.

Case G_{6}. The degrees are 4, 12, and therefore, according to Remark 4, we need only consider the case where h_{2} = 4 and m_{2} = 2, that is, p = 3(m + 1)/2. Then the action of ψ^{p} is given by

ψ^{p}((w_{0}; w_{1}, …, w_{m})) = (c^{2}w_{\frac{m+1}{2}} c^{−2}; c^{2}w_{\frac{m+3}{2}} c^{−2}, …, c^{2}w_{m}c^{−2}, cw_{0}c^{−1}, …, cw_{\frac{m−1}{2}} c^{−1}).

(8.5)

If (w_{0}; w_{1}, …, w_{m}) is fixed by ψ^{p}, there must exist an i with 0 ≤ i ≤ \frac{m−1}{2} such that ℓ_{T} (w_{i}) = 1, w_{i}cw_{i}c^{−1} = c, and all w_{j}, j ≠ i, \frac{m+1}{2} + i, equal ε. However, with the help of CHEVIE, one verifies that there is no such solution to this equation. Hence, the left-hand side of (7.2) is equal to 0, as required.

This completes the proof of the lemma. □

9. Exemplification of case-by-case verification of Theorem 16

It remains to verify Theorem 16 for the groups G_{4}, G_{8}, G_{16}, G_{20}, G_{23} = H_{3}, G_{24}, G_{25}, G_{26}, G_{27}, G_{28} = F_{4}, G_{29}, G_{30} = H_{4}, G_{32}, G_{33}, G_{34}, G_{35} = E_{6}, G_{36} = E_{7}, G_{37} = E_{8}. All details can be found in [21, Sec. 9]. We content ourselves with discussing the case of the group G_{24}, as this suffices to convey the flavour of the necessary computations.

In order to simplify our considerations, it should be observed that the action of ψ (given in (7.1)) is exactly the same as the action of ϕ (given in (3.1)) with m replaced by m + 1 on the components w_{1}, w_{2}, …, w_{m+1}, that is, if we disregard the 0-th component of the elements of the generalised non-crossing partitions involved. The only difference which arises is that, while the (m + 1)-tuples (w_{0}; w_{1}, …, w_{m}) in (7.1) must satisfy w_{0}w_{1} ⋯ w_{m} = c, for w_{1}, w_{2}, …, w_{m+1} in (3.1) we only must have w_{1}w_{2} ⋯ w_{m+1} ≤_{T} c. Consequently, we may use the counting results from Section 6, except that we have to restrict our attention to those elements (w_{0}; w_{1}, …, w_{m}, w_{m+1}) ∈ NC^{m+1}(W) for which w_{1}w_{2} ⋯ w_{m+1} = c, or, equivalently, w_{0} = ε.

Case G_{24}. The degrees are 4, 6, 14, and hence we have

Cat^{m}(G_{24}; q) = \frac{[14m + 14]_{q} [14m + 6]_{q} [14m + 4]_{q}}{[14]_{q} [6]_{q} [4]_{q}} .

Let ζ be a 14(m + 1)-th root of unity. The following cases on the right-hand side of (7.2) occur:

lim_{q→ζ} Cat^{m}(G_{24}; q) = m + 1, if ζ = ζ_{14}, ζ_{7},  (9.1a)
lim_{q→ζ} Cat^{m}(G_{24}; q) = \frac{7m+7}{3}, if ζ = ζ_{6}, ζ_{3}, 3 | (m + 1),  (9.1b)
lim_{q→ζ} Cat^{m}(G_{24}; q) = Cat^{m}(G_{24}), if ζ = −1 or ζ = 1,  (9.1c)
lim_{q→ζ} Cat^{m}(G_{24}; q) = 0, otherwise.  (9.1d)

We must now prove that the left-hand side of (7.2) in each case agrees with the values exhibited in (9.1). The only cases not covered by Lemma 18 are the ones in (9.1b) and (9.1d). On the other hand, the only cases left to consider according to Remark 4 are the cases where h_{2} = 1 and m_{2} = 3, h_{2} = 2 and m_{2} = 3, and h_{2} = m_{2} = 2. These correspond to the choices p = 14(m+1)/3, p = 7(m+1)/3, respectively p = 7(m+1)/2. The first two cases belong to (9.1b), while p = 7(m + 1)/2 belongs to (9.1d).

In the case that p = 7(m + 1)/3, the action of ψ^{p} is given by

ψ^{p}((w_{0}; w_{1}, …, w_{m}))

= (c^{3}w_{\frac{2m+2}{3}} c^{−3}; c^{3}w_{\frac{2m+5}{3}} c^{−3}, …, c^{3}w_{m}c^{−3}, c^{2}w_{0}c^{−2}, …, c^{2}w_{\frac{2m−1}{3}} c^{−2}).

Hence, for an i with 0 ≤ i ≤ \frac{m−2}{3}, we must find an element w_{i} = t_{1}, where t_{1} satisfies (6.4), so that we can set w_{i+ \frac{m+1}{3}} = c^{2}t_{1}c^{−2}, w_{i+ \frac{2m+2}{3}} = c^{4}t_{1}c^{−4}, and all other w_{j}’s equal to ε. We have found seven solutions to the counting problem (6.4), and each of them gives rise to (m + 1)/3 elements in Fix_{NC^{m}(G_{24})}(ψ^{p}) since the index i ranges from 0 to (m − 2)/3.

On the other hand, if p = 14(m + 1)/3, then the action of ψ^{p} is given by

ψ^{p}((w_{0}; w_{1}, …, w_{m}))

= (c^{5}w_{\frac{m+1}{3}} c^{−5}; c^{5}w_{\frac{m+4}{3}} c^{−5}, …, c^{5}w_{m}c^{−5}, c^{4}w_{0}c^{−4}, …, c^{4}w_{\frac{m−2}{3}} c^{−4}).

By Lemma 12, every element of NC(W) is fixed under conjugation by c^{7}, and, thus, the equations for t_{1} in this case are the same as in the previous one where p = 7(m + 1)/3.

Hence, in either case, we obtain 7\frac{m+1}{3} = \frac{7m+7}{3} elements in Fix_{NC^{m}(G_{24})}(ψ^{p}), which agrees with the limit in (9.1b).

If p = 7(m + 1)/2, the relevant counting problem is (6.5). However, no element (w_{0}; w_{1}, …, w_{m}) ∈ Fix_{NC^{m}(G_{24})}(ψ^{p}) can be produced in this way since the counting problem imposes the restriction that ℓ_{T} (w_{0}) + ℓ_{T} (w_{1}) + ⋯ + ℓ_{T} (w_{m}) be even, which contradicts the fact that ℓ_{T} (c) = n = 3. This is in agreement with the limit in (9.1d).

Acknowledgements

The authors thank an anonymous referee for a very careful reading of the original manuscript, and for numerous pertinent suggestions which have helped to considerably improve the original manuscript.

References

[1] G. E. Andrews, The Theory of Partitions, Encyclopedia of Math. and its Applications, vol. 2, Addison–Wesley, Reading, 1976.

[2] G. E. Andrews, The Friedman–Joichi–Stanton monotonicity conjecture at primes, in: Unusual Applications of Number Theory (M. Nathanson, ed.), DIMACS Ser. Discrete Math. Theor. Comp. Sci., vol. 64, Amer. Math. Soc., Providence, R.I., 2004, pp. 9–15.

[3] D. Armstrong, Generalized noncrossing partitions and combinatorics of Coxeter groups, Mem. Amer. Math. Soc., vol. 202, no. 949, Amer. Math. Soc., Providence, R.I., 2009.

[4] D. Armstrong, C. Stump and H. Thomas, A uniform bijection between nonnesting and noncrossing partitions, Trans. Amer. Math. Soc. (to appear).

[5] C. A. Athanasiadis, Generalized Catalan numbers, Weyl groups and arrangements of hyperplanes, Bull. London Math. Soc. 36 (2004), 294–302.

[6] C. A. Athanasiadis, On a refinement of the generalized Catalan numbers for Weyl groups, Trans. Amer. Math. Soc. 357 (2005), 179–196.

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

[8] D. Bessis, Finite complex reflection groups are K(π, 1), preprint, arχiv:math/0610777.

[9] D. Bessis and R. Corran, Non-crossing partitions of type (e, e, r), Adv. Math. 202 (2006), 1–49.

[10] D. Bessis and V. Reiner, Cyclic sieving and noncrossing partitions for complex reflection groups, Ann. Comb. 15 (2011), 197–222.

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

[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] M. Geck, G. Hiss, F. Lübeck, G. Malle and G. Pfeiffer, CHEVIE — a system for computing and processing generic character tables for finite groups of Lie type, Appl. Algebra Engrg. Comm. Comput. 7 (1996), 175–210.

[15] I. Gordon and S. Griffeth, Catalan numbers for complex reflection groups, Amer. J. Math. (to appear).

[16] J. E. Humphreys, Reflection groups and Coxeter groups, Cambridge University Press, Cambridge, [17] C. Krattenthaler, The F -triangle of the generalised cluster complex, in: Topics in Discrete Mathe-

matics, 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, eds.), Springer–Verlag, Berlin, New York, 2006, pp. 93–126.

[18] C. Krattenthaler, The M-triangle of generalised non-crossing partitions for the types E_{7} and E_{8}, Séminaire Lotharingien Combin. 54 (2006), Article B54l, 34 pages.

[19] C. Krattenthaler, Non-crossing partitions on an annulus, in preparation.

[20] C. Krattenthaler and T. W. Müller, Decomposition numbers for finite Coxeter groups and generalised non-crossing partitions, Trans. Amer. Math. Soc. 362 (2010), 2723–2787.

[21] C. Krattenthaler and T. W. Müller, Cyclic sieving for generalised non-crossing partitions associated with complex reflection groups of exceptional type — the details, manuscript;

    arχiv:1001.0030.

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

[23] G. I. Lehrer and J. Michel, Invariant theory and eigenspaces for unitary reflection groups, C. R. Math. Acad. Sci. Paris 336 (2003), 795–800.

[24] G. I. Lehrer and D. E. Taylor, Unitary reflection groups, Cambridge University Press, Cambridge, 2009.

[25] G. Malle and J. Michel, Constructing representations of Hecke algebras for complex reflection groups, LMS J. Comput. Math. 13 (2010), 426–450.

[26] I. Marin, The cubic Hecke algebra on at most 5 strands, J. Pure Appl. Algebra 216 (2012), 2754–2782.

[27] J. Michel, The GAP-part of the CHEVIE system, GAP 3-package available for download from

    http://people.math.jussieu.fr/jmichel/chevie/chevie.html.

[28] P. Orlik and L. Solomon, Unitary reflection groups and cohomology, Invent. Math. 59 (1980), 77–94.

[29] V. Reiner, D. Stanton and D. White, The cyclic sieving phenomenon, J. Combin. Theory Ser. A 108 (2004), 17–50.

[30] B. Rhoades, Parking structures: Fuss analogs, preprint, arχiv:1205.4293.

[31] V. Ripoll, Orbites d’Hurwitz des factorisations primitives d’un élément de Coxeter, J. Algebra 323 (2010), 1432–1453.

[32] B. E. Sagan, The cyclic sieving phenomenon: a survey, Surveys in combinatorics 2011, London Math. Soc. Lecture Note Ser., vol. 392, Cambridge Univ. Press, Cambridge, 2011, pp. 183–233.

[33] G. C. Shephard and J. A. Todd, Finite unitary reflection groups, Canad. J. Math. 6 (1954), 274–304.

[34] T. A. Springer, Regular elements of finite reflection groups, Invent. Math. 25 (1974), 159–198.

[35] J. R. Stembridge, Some hidden relations involving the ten symmetry classes of plane partitions, J. Combin. Theory Ser. A 68 (1994), 372–409.

[36] J. R. Stembridge, Canonical bases and self-evacuating tableaux, Duke Math. J. 82 (1996). 585–606,

[37] 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.

School of Mathematical Sciences, Queen Mary & Westfield College, University of London, Mile End Road, London E1 4NS, United Kingdom.

http://www.maths.qmw.ac.uk/~twm/.