Factorization problems in complex reflection groups
Joel Brewster Lewis Alejandro H. Morales





Factorization problems in complex reflection groups
    Joel Brewster Lewis and Alejandro H. Morales
    
===================================================





  Dedicated to David M. Jackson in recognition of his 75th birthday




We enumerate factorizations of a Coxeter element in a well generated complex reflection group into arbitrary factors, keeping track of the fixed space dimension of each factor.  In the infinite families of generalized permutations, our approach is fully combinatorial.  It gives results analogous to those of Jackson in the symmetric group and can be refined to encode a notion of cycle type.  As one application of our results, we give a previously overlooked characterization of the poset of W-noncrossing partitions.







§ INTRODUCTION


The motivation for this paper is the following formula of
Chapuy and Stump for the generating function for the number of factorizations of a fixed
Coxeter element by reflections in a complex reflection
group. 



Let W be an irreducible well generated complex reflection group of
rank n. Let c be a Coxeter element in W, let R and R^* be
the set of all reflections and all reflecting hyperplanes in W, and
for ℓ≥ 1 let N_ℓ(W) := #{
(τ_1,…,τ_ℓ) ∈ R^ℓτ_1⋯τ_ℓ =  c } be the number of factorizations of c as a
product of ℓ reflections in R. Then

    ∑_ℓ≥ 0 N_ℓ(W)t^ℓ/ℓ!  = 1/|W|( e^t|R|/n
      - e^-t |R^*|/n)^n.



Near t=0, the generating function recovers the fact <cit.> that the number of minimum-length reflection factorizations of a Coxeter element is n! h^n/|W|, where h is the Coxeter number of W. When W is the symmetric group _n, Theorem <ref> reduces
to a result of Jackson <cit.> counting factorizations of
the n-cycle (12⋯ n) into transpositions.  Chapuy and Stump prove their result
by an algebraic approach with irreducible
characters that dates back to Frobenius. 


A natural question is whether there are extensions to complex
reflection groups of other factorization results in the symmetric
group. In the same paper <cit.>, Jackson gave formulas for the
generating polynomial of factorizations of an n-cycle as a
product of a fixed number of factors, keeping track of the number of
cycles of each factor. We state the result for two and k factors, as
reformulated by Schaeffer–Vassilieva.




Let  be a fixed n-cycle in _n, and for integers r_1,…,r_k
let a_r_1,…,r_k be the number of factorizations of  as a
product of k permutations in _n such that π_i has r_i cycles for i=1,…,k. Then

    1/n!·∑_r, s ≥ 1 a_r, s x^r y^s = ∑_p,q
      ≥ 1n-1p-1; q-1; n - p - q + 1(x)_p/p!(y)_q/q!,

where (x)_p denotes the falling factorial (x)_p := x(x - 1)⋯ (x - p + 1).  More generally,

    1/(n!)^k-1·∑_r_1,…,r_k ≥ 1 a_r_1,
      …, r_k x_1^r_1⋯ x_k^r_k = ∑_p_1,…,p_k ≥
      1  M^n-1_p_1-1,…,p_k-1(x_1)_p_1/p_1!⋯(x_k)_p_k/p_k!,

where the coefficient M^n_p_1,…,p_k is defined in (<ref>).


In this paper we give analogues of these results for two infinite families of complex reflection
groups:  the group G(d,1,n) of n × n monomial matrices whose
nonzero entries are all dth roots of unity (i.e., the wreath
product (/d)  ≀𝔖_n; at d = 2, the Coxeter
group of type B_n) and its subgroup G(d,d,n) of matrices whose nonzero
  entries multiply to 1 (at d = 2, the Coxeter group of type D_n).  
The analogue of an n-cycle in a complex reflection group is a Coxeter element. 
The analogue of number of cycles of a group element is the fixed space dimension.  Our results for G(d, 1, n) are in terms of the polynomials

    (x - 1)_k^(d) := (x - 1)(x-1-d)(x-1-2d)⋯ (x-1-(k-1)d) = ∏_i = 1^k (x - e^*_i).

Here the roots e^*_i are the coexponents of this group, one
of the fundamental sets of invariants associated to every complex
reflection group. (All these terms are defined in Section <ref>.) 

 
For d > 1, let G = G(d, 1, n) and let a^(d)_r_1,…,r_k be the number of factorizations of a fixed Coxeter element c in G as a product of k elements of G with fixed space dimensions r_1,…,r_k,
respectively. Then

    1/|G|·∑_r,s ≥ 0 a^(d)_r,s x^r y^s     = ∑_p,q ≥ 0np; q; n - p - q(x - 1)^(d)_p/d^pp!(y - 1)^(d)_q/d^qq!,
    and more generally1/|G|^k-1·∑_r_1,…,r_k ≥ 0
    a^(d)_r_1,…,r_k x_1^r_1⋯ x_k^r_k   = 
     ∑_p_1,…,p_k ≥ 0
    M^n_p_1,…,p_k(x_1 - 1)^(d)_p_1/d^p_1p_1!⋯(x_k - 1)^(d)_p_k/d^p_kp_k!,

where M^n_p_1,…,p_k is defined in (<ref>).


In Section <ref>, we give a combinatorial proof of the
result for k factors by reducing it to
  the case of the symmetric group for k factors. The latter case has a
  combinatorial proof <cit.>. Our proof works directly with the
group elements and permutations. However, the proof could also be
written in terms of maps (e.g., see <cit.>) through a
coloring argument as done in <cit.> for the
case of factorizations with two factors and in <cit.> for the
case of factorizations with k factors. 

Our main results for the subgroup G(d,d,n) of G(d,1,n) count transitive factorizations (for the natural action on a set of size dn) of a Coxeter element. They are written in terms of the polynomials

    kdx := (x - (k - 1)(d - 1)) · (x - 1)^(d)_k - 1 = ∏_i = 1^k (x - e^*_i),

where again the e^*_i are the coexponents of the
group. 

 
For d > 1, let G = G(d, d, n) and let 
 b^(d)_r_1,…,r_k be the number of transitive factorizations of a Coxeter element c_(d, d, n) in G as a product of k
elements of G with fixed space dimensions r_1,…,r_k, respectively. 
Then

    n/(n - 1) · |G|·∑_r,s ≥ 0 b^(d)_r,s x^r y^s    = ∑_p,q ≥ 1n-2p-1; q-1; n -p - qpdx/d^p-1 p!qdx/d^q-1 q!,
    and more generallyn^k/|G|^k-1·∑_r_1,…,r_k
      ≥ 0 b^(d)_r_1,…,r_k x_1^r_1⋯ x_k^r_k   = ∑_p_1,…,p_k ≥ 1
     M^n_p_1,…,p_kp_1dx_1/d^p_1-1 (p_1-1)!⋯p_kdx_k/d^p_k-1 (p_k-1)!,

 where M^n_p_1,…,p_k is defined in (<ref>).
 

In Section <ref>, we give a combinatorial proof of these results.  The proof relies on an enumeration of transitive factorizations of an (n - 1)-cycle in _n into k factors that appears to be new – its proof may be found in Section <ref>.

In the remainder of the paper, we consider a variety of extensions and
applications of these results.  In Section <ref>, we
explore the same question in the exceptional complex reflection
groups, using an algebraic approach.  This produces results that are
strikingly similar to the results from the infinite families in many cases, but
ultimately no uniform formula along the lines of Theorem <ref>.
The question of whether a uniform theorem exists is raised in Section <ref>.

In Section <ref>, we show how to derive the
Chapuy–Stump result from our main results, giving a fully
combinatorial proof in the case of G(d, 1, n).  We also consider the special case of genus-0 factorizations, which are extremal with respect to a natural subadditivity of fixed space.  As a consequence, we derive a characterization of the poset of W-noncrossing partitions that has (surprisingly) been overlooked before now.

In Section <ref>, we refine the result for G(d, 1, n) by
the group orbit of the fixed space, or equivalently by an appropriate
notion of cycle type.  The proof is again fully combinatorial.  In the
genus-0 case, this result gives an analogue of the Goulden–Jackson cactus
formula <cit.> and specializes to a result of Krattenthaler–Müller in type B <cit.>. 
Finally, in Section <ref>, we end with a number of remarks and open questions, including constructions of maps associated to factorizations in G(d, 1, n).

An extended abstract of this work appeared in <cit.>.




 §.§ Acknowledgements

We are indebted to Drew Armstrong, Olivier Bernardi, Theo
Douvropoulos, John Irving, Vic Reiner, Gilles Schaeffer,  Christian
Stump, and the anonymous referees whose comments, questions, and suggestions led to significant
improvements in the paper.  JBL was partially supported by a grant from the Simons Foundation (634530) and by an ORAU Powe award.  AHM was partially supported by the NSF grant DMS-1855536.




§ BACKGROUND





 §.§ Known factorization results in 𝔖_n


We begin by discussing in more detail the background behind Theorem <ref>.  Let  be a fixed n-cycle in _n, and for integers
r_1,…,r_k let a_r_1,…,r_k be the number of k-tuples
(π_1,…,π_k) of elements in _n such that π_i has r_i
cycles for i=1,…,k and π_1 ⋯π_k =.
Theorem <ref> is a corollary of a result obtained by Jackson <cit.>; our formulation follows Schaeffer and Vassilieva <cit.>.  The coefficients on the RHS of (<ref>) are defined as follows.  Given a positive integer k and nonnegative integers n and p_1,…,p_k, let

    M^n_p_1,…,p_k := ∑_t=0^min(p_i) (-1)^t nt∏_i=1^k n-tp_i-t = [x_1^p_1⋯ x_k^p_k] (
      (1+x_1)⋯ (1+x_k) - x_1⋯ x_k)^n,

where the square brackets in the third expression represent coefficient extraction.  This number counts n-tuples (S_1,…,S_n) of proper subsets of [k] := {1, …, k} such that exactly p_j of the sets contain j. It is easy to see that the
 M^n_  satisfy the following recurrence.

 
One has
M^n_
=∑_S ⊊ [k] M^n-1_ -  _S
 = ∑_∅≠ T⊆ [k] M^n-1_ -  1 + _T
where _S denotes the indicator vector for the set S and 1 := _[k] is the all-ones vector. 


Also, from the enumerative interpretation of M^n_ one has that M^n_p_1,p_2 is given by the
multinomial coefficient np_1; p_2; n-p_1-p_2, and that M^n_ = 0 whenever p_1 + … + p_k > n(k - 1). For
k ≥ 3, the M^n_ are not given by a multinomial coefficient
or other product formula, except for the following extremal case.

 
If p_1+… +p_k = n(k-1) then M^n_p_1, …, p_k =
nn-p_1; ⋯; n-p_k.



Suppose that p_1+ … + p_k = n(k-1) and that (S_1,…,S_n) is an 
n-tuple of proper subsets of [k] counted
by M^n_p_1,…,p_k.  Let c_i:= |S_i|
for i=1,…,n. Since c_i ≤ k-1 and c_1+ … + c_n =
p_1+ … +p_k = n(k - 1), it must be the case that c_i = k-1 for i=1,…,n. Thus S_i = [k]
∖{a_i} for some a_i ∈ [k].  Then the correspondence (S_1, …, S_n) ⟷  (a_1,…,a_n) is a bijection between
the n-tuples of sets counted by M^n_ and n-tuples of elements of
[k] such that j appears n-p_j times for j = 1, …, k. The latter set is obviously counted by the desired multinomial coefficient, and the result follows.


Jackson's proof of Theorem <ref> uses an algebraic approach based on work of Frobenius from the late 19th century; these methods are described in Section <ref> below, after which we apply them to give a similar result for the (n - 1)-cycle in _n. Bijective proofs of the case k=2 were given by Schaeffer–Vassilieva <cit.>, Chapuy–Féray–Fusy <cit.>, and
Bernardi <cit.>.  Bernardi and Morales <cit.> extended Bernardi's approach to give a combinatorial proof of Jackson's formula for all k in terms of maps. These combinatorial proofs use an interpretation of the change of basis in (<ref>) that we describe now. 

Let ^⟨ n⟩_p_1,…,p_k be the set of factorizations in
𝔖_n of the fixed n-cycle  as a product π_1⋯π_k such that for each i, the cycles of π_i are colored
with p_i colors with each of the colors being used at least once to
color a cycle of π_i.  (In particular, once the factorization is
fixed, this means that the colorings of the cycles in the different
factors are completely independent of each other.) Let
  C^⟨ n ⟩_p_1,…,p_k = |^⟨
    n⟩_p_1,…,p_k| be the number of such colored
  factorizations. 

 
Note that the number C^⟨ n ⟩_p_1,…,p_k of
colored factorizations does not depend on the set of
  p_i colors used to color the cycles of
  u_i. In an abuse of notation, depending on context, we will use
  the same symbols ^⟨ n⟩_p_1,…,p_k and
  C^⟨ n⟩_p_1,…,p_k to denote the set and the
  number of colored factorizations where for each π_i we use color set [p_i], or
  {0,1,…,p_i-1}, or a p_i-subset of a larger set.




With a_r_1, …, r_k and C^⟨ n ⟩_p_1, …, p_k as above, one has

    ∑_r_1,…,r_k ≥ 1 a_r_1,
      …, r_k x_1^r_1⋯ x_k^r_k = ∑_p_1,…,p_k ≥
      1 C^⟨ n ⟩_p_1,…,p_kx_1p_1⋯x_kp_k.




Let each x_i be a nonnegative integer. The LHS of (<ref>) counts  
factorizations of the cycle = (12⋯ n) as a product
  = π_1⋯π_k, where
for i=1,…,k, each cycle of π_i is colored with a
  color in [x_i].
These colored factorizations are also counted by the RHS of (<ref>): for
p_1,…,p_k ∈ℕ and i=1,…,k, choose p_i
colors from x_i colors available and a colored factorization in
^⟨ n⟩_p_1,…,p_k where exactly those p_i colors are used in
the factor π_i.  Finally, since (<ref>) is valid for all nonnegative integer values of the x_i, it is valid as a polynomial identity.


The following corollary is an immediate consequence of Theorem <ref> and Proposition <ref>.



The number of colored factorizations of an n-cycle in _n is C^⟨ n ⟩_p_1,…,p_k  =  (n!)^k-1 M^n-1_p_1-1,…,p_k-1.





 §.§ Complex reflection groups
 

In this section, we give an account of the complex reflection groups,
paying particular attention to the “combinatorial” groups G(d, 1,
n) and G(d, d, n).  For more thorough background, see
<cit.>.  



  §.§.§ Basic definitions


Given a complex vector space V of dimension n, a linear transformation r on V is called a reflection if the dimension of the fixed space of r (i.e., the set of vectors v such that r(v) = v) is n - 1, that is, if r fixes a hyperplane.  A complex reflection group is a finite subgroup of (V) generated by its subset of reflections.  A complex reflection group is irreducible if it does not stabilize any nontrivial subspace of V, and every complex reflection group decomposes uniquely as a direct product of irreducibles.  A complex reflection group is well-generated if it acts irreducibly on a space of dimension m and has a generating set consisting of m reflections.



  §.§.§ Key examples


The most common examples of complex reflection groups are the finite
Coxeter groups, including the dihedral groups, the symmetric group
_n (type A_n - 1), and the hyperoctahedral group of signed
permutations (type B_n) and its index-2 subgroup of “even-signed
permutations” (type D_n), whose elements have an even number
of negative entries.  All real reflection groups are well-generated.  (For _n, the space on which it acts irreducibly has dimension m = n - 1; for the signed and even-signed permutations, m = n.)  

There are two infinite families of well generated irreducible complex
reflection groups.  The groups in the first family are the wreath products G(d, 1, n) = (/d) ≀_n of the symmetric group by a cyclic group of order d.  Concretely, the elements of this group may be realized as generalized permutation matrices with one nonzero entry in each row and column, each of which is a complex dth root of unity – see Figure <ref>.  Thus G(2, 1, n) is the hyperoctahedral group of signed permutations.  More compactly, elements of G(d, 1, n) may be identified with pairs [π; a] where π is a permutation in _n and a = (a_1, …, a_n) is a tuple of elements of /d.  We say that a_i is the weight of i in [π; a] and that π is the underlying permutation.  In this notation, the product of two group elements is given by

    [π; a] · [σ; b] = [πσ; σ(a) + b]

where σ(a) := (a_σ(1), …, a_σ(n)).  The
underlying permutation π is the image of [π; a] under the
natural projection map G(d, 1, n) ↠_n.
A cycle in [π; a] ∈ G(d, 1, n) means a cycle in π.
The weight of a cycle is the sum in
  ℤ/dℤ of the weights of the elements in the cycle.



When d > 1, there are two “flavors” of reflections in G(d, 1, n): the diagonal reflections, which have the identity as underlying permutation and a single diagonal entry of nonzero weight, and the transposition-like reflections, whose underlying permutation is a transposition and whose cycles all have weight 0 – see Figure <ref>.
The second infinite family of well generated complex reflection groups contains, for each d > 1 and n ≥ 2, the subgroup of G(d, 1, n) generated by the transposition-like reflections; it is denoted G(d, d, n).  Equivalently, G(d, d, n) contains those elements of G(d,1, n) of weight 0 (i.e., generalized permutation matrices in which the product of the nonzero entries is 1).  In the case d = 2, it is exactly the Coxeter group of type D_n, and in the case n = 2, it is the dihedral group of order 2d.  The group G(d, d, n) is always well generated, and it is irreducible except when d = n = 2.



In addition to the infinite families of irreducible complex reflection groups, there are 34 exceptional groups.  Of these, 26 are well generated, including the six exceptional Coxeter groups (of types H_3, F_4, H_4, E_6, E_7, and E_8).  These are not the main focus of this paper, but they are discussed further in Section <ref>.



  §.§.§ Fixed space dimension


It is easy to see that conjugacy classes in G(d, 1, n) are uniquely determined by the cycle type of the underlying permutation together with the multiset of weights of the cycles of each length.  Equivalently, for each weight j = 0, …, d - 1, we have a partition (possibly empty) recording the lengths of the cycles of weight j.  Thus, conjugacy classes in G(d, 1, n) are unambiguously indexed by tuples (λ^(0), …, λ^(d - 1)) of partitions of total size n. The following proposition is straightforward.


The fixed space dimension of an element w in G(d, 1, n) whose conjugacy class is indexed by (λ^(0), …, λ^(d - 1)) is equal to ℓ(λ^(0)), the number of cycles of weight 0 in w.

Since G(d, d, n) ⊂ G(d, 1, n), the same combinatorial formula gives the fixed space dimension for elements of the smaller group.  For the symmetric group _n acting on ^n, the fixed space dimension of w is exactly the number of cycles of w.




  §.§.§ Coxeter elements



An element w in a complex reflection group G is regular if it has an eigenvector that does not lie on the fixed plane of any reflection in the group.  Since w is of finite order, the associated eigenvalue is a root of unity; if it is a primitive root of order k, then we say that the integer k is regular as well.  The Coxeter number h of G is the largest regular integer, and a Coxeter element of G is a regular element of order h (but see Remark <ref> below).  In the case of the symmetric group _n, the regular elements are the n-cycles, the (n - 1)-cycles, and their powers, the Coxeter number is h = n, and the Coxeter elements are exactly the n-cycles.  For d > 1, one can make the following concrete choice of Coxeter elements in the infinite families, illustrated in Figure <ref>: in G(d, 1, n), take

    c := [(12⋯ n); (0, 0, …, 0, 1)],

while in G(d, d, n), take

    c_(d,d,n) := [(12⋯(n - 1))(n); (0, …, 0, 1, -1)].




At least two nonequivalent definitions of Coxeter elements have
appeared in the literature (compare, e.g., the definitions in <cit.> and <cit.>): under the more restrictive definition, every Coxeter element in G(d, 1, n) (respectively, G(d, d, n)) is conjugate to the element c (respectively, c_(d, d, n)) selected above.  Since conjugacy descends to a bijection between factorizations that preserves the fixed space dimension of each factor, it follows that all Coxeter elements (under the restrictive definition) have the same enumerations, and it is enough to consider just one.

Under the more general definition, one should also allow in G(d, 1, n) the possibility of replacing the weight 1 in c with any cyclic generator of /d (and then taking conjugates), and similarly for G(d, d, n).  The resulting elements are not all conjugate in the group G(d, 1, n), so it is not a priori clear that different Coxeter elements yield the same enumeration.  This difficulty may be resolved in two different ways.  One resolution is to examine the actual proofs presented in Sections <ref> and <ref> below.  Because of the combinatorial nature of these proofs, it is not difficult to see that they work equally well if the weights 1 and -1 are replaced by a and -a for any nonzero element a in /d, so all Coxeter elements in the more general sense (and even some elements that are not Coxeter elements under any definition) have the same enumeration.

An alternative, and more conceptual, resolution is based on the work
of Reiner–Ripoll–Stump <cit.> that we describe now.  Given a
complex reflection group G of rank n, understood to be represented
by a concrete choice of matrices in _n(), define the
field of definition K_G to be the subfield of  generated
by the traces of elements of G.  One can show that G can be
represented over _n(K_G), i.e., that the representing matrices
can be taken to have entries in K_G.  The Galois group Γ =
Gal(K_G / ) acts on _n(K_G) entrywise, and so
each member γ of Γ gives an isomorphism between G and
some, possibly different, representation of G over K_G.  By
<cit.>, the group γ(G) is conjugate in
_n() to G, i.e., there is some g ∈_n() such that
G = g ·γ(G) · g^-1.  Both γ and conjugation
by g preserve fixed-space dimension, so the combined automorphism w
↦ g ·γ(w) · g^-1 does as well.  It is part of
the main result of <cit.> that these reflection
  automorphisms (called Galois automorphisms in
<cit.>) act transitively on the Coxeter elements of G
under the more general definition.  These automorphisms descend to
bijections between factorizations that preserve fixed space dimension.  Consequently, the answers to the questions we consider are the same for all Coxeter elements, and it suffices to compute with a single, fixed Coxeter element.




  §.§.§ Degrees and coexponents



To each complex reflection group there are associated fundamental invariants of several kinds, two of which will appear below (particularly in Section <ref>).  We define them now.

Much interest in complex reflection groups relates to their role in
invariant theory: the complex reflection groups of rank n are
exactly the groups G whose invariant ring [x_1, …, x_n]^G
is again a polynomial ring [f_1, …, f_n], generated by n
algebraically independent homogeneous polynomials. (For example, the invariant ring [x_1,
…, x_n]^S_n of the symmetric group is the ring of symmetric
polynomials in n variables, generated over  by the elementary
symmetric polynomials {e_1, …, e_n}.) The basic
invariants f_1, …, f_n are not uniquely determined, but their
degrees d_1 ≤ d_2 ≤…≤ d_n are, and we call these the
degrees of G.   For a well generated group, it is always the
case that d_n is equal to the Coxeter number h mentioned above.
For G(d, 1, n), the degrees are given by d_i = d · i, while for G(d, d, n) they are given by {d_1, …, d_n} = {d, 2d, …, (n - 1)d}∪{n}.  For any complex reflection group G, one has d_1 ⋯ d_n = |G| and, more generally <cit.>,

    ∑_w ∈ G x^(w) = ∏_i = 1^n (x - 1 + d_i).


A second sequence of invariants, the coexponents of G, will
also appear below.  These may be equivalently defined in several ways:
in terms of invariant theory, they are degrees of generators appearing in the covariant space ([V] ⊗ V)^G; for a definition in terms of the hyperplane arrangement associated to G, see Remark <ref>.  
Perhaps the simplest definition is that the coexponents e^*_1 ≤
e^*_2 ≤…≤ e^*_n are the positive integers that satisfy
the identity <cit.>

    ∑_w ∈ G(w) · x^(w) = ∏_i = 1^n (x - e^*_i).

One consequence of this formula is that the sum ∑_i = 1^n e^*_i is equal to the number |R^*| of reflecting hyperplanes of reflections in G.
For G(d, 1, n), the coexponents are given by e^*_i = 1 + d· (i - 1), while for G(d, d, n) they are given by {e^*_1, …, e^*_n} = {1, d + 1, …, (n - 2)d + 1}∪{(n - 1)(d - 1)}.



 §.§ Counting factorizations with representation theory



The character-theory approach to counting factorizations is based on the following lemma, expositions of which appear in numerous sources, e.g., <cit.>.



Let G be a finite group, g an element of G, and A_1, …, A_k subsets of G that are closed under conjugacy by G.  Then the number of factorizations of g as a product g = u_1 ⋯ u_k such that for each i the factor u_i is required to lie in the set A_i is equal to

    1/|G|∑_λ∈(G)(λ) χ_λ(g^-1) _λ(_1) ⋯_λ(_k),

where (G) is the set of irreducible complex representations of
G, (λ) is the dimension of the representation λ,
χ_λ is the character associated to λ extended
linearly from the group to the group algebra, _λ = χ_λ/(λ) is the normalized character associated to λ, and for i = 1, …, k, _i is the formal sum in the group algebra of elements in A_i.


Thus, counting factorizations with no transitivity conditions can be reduced to
  a problem of being able to compute enough of the
  character table of the group under consideration.  This is precisely
  the approach followed by Jackson and by Chapuy–Stump, using
  respectively the character theory of the symmetric group and of complex reflection
  groups. We also consider factorizations with a transitivity condition. 
  Their counts can be written as a difference of two numbers of factorizations without
  transitivity conditions, where the character approach can be
  used. We make use of this character approach in the next subsection,
  as well as in the case of the exceptional complex reflection groups
  (Section <ref>). 



 §.§ Factoring an (n - 1)-cycle in 𝔖_n




If one factors an (n - 1)-cycle  in _n as a product of
other permutations, there are two possibilities: either every factor
shares a fixed point with , or not.  The factorizations in the
former case are in natural bijection with factorizations of an
(n-1)-cycle in _n - 1.  The factorizations in the latter
case have a more elegant description: they are exactly the
factorizations in which the factors act transitively on the set
[n]. The study of transitive
factorizations is present already in the work of Hurwitz <cit.>
from the late 19th century and plays an important role in the study of permutation
factorizations; see <cit.> for a recent survey.  
Our first result is to enumerate transitive factorizations of the (n - 1)-cycle.




Let  be a fixed (n-1)-cycle in 𝔖_n. For integers
r_1,…,r_k, let b_r_1,…,r_k be the number of k-tuples
(π_1,…,π_k) of elements in _n such that π_i has r_i
cycles for i=1,…,k, π_1 ⋯π_k =, and the tuple is a transitive factorization. Then 

    ∑_r_1,…,r_k ≥ 1 b_r_1,
      …, r_k x_1^r_1⋯ x_k^r_k   = (n!)^k - 1/n^k∑_p_1,…,p_k ≥
      1  M^n_p_1,…,p_k(x_1)_p_1/(p_1-1)!⋯(x_k)_p_k/(p_k-1)!,

where M^n_p_1,…,p_k is defined in (<ref>).



We were surprised not to find this statement in the literature. We
give an algebraic proof.  In Section <ref>, we give
a combinatorial proof in the case of k = 2 factors; it would be
of interest to find a combinatorial proof for all k.




Theorem <ref> can be interpreted as
a statement about colored factorizations: the LHS counts
transitive factorizations of  in which the cycles of factor i
are colored with any of x_i colors, and the coefficient C^⟨
  n - 1, 1 ⟩_p_1, …, p_k := (n!)^k - 1p_1 ⋯
  p_k/n^k M^n_p_1, …, p_k of x_1p_1⋯x_kp_k on the RHS is the number of these factorizations in which a
prescribed set of p_i colors is used in the ith factor. 


In the proof of Theorem <ref>, we assume a familiarity with symmetric
functions as in <cit.>.  Let p_λ, s_λ and m_λ denote
the power sum, Schur and monomial symmetric
functions in the variables = {x_1, x_2, …}. We will use the stable principal
  specializations ↦ 1^x of these functions, setting x of the variables {x_i} equal to 1 and all others equal to 0.  One has

    p_λ(1^x) = x^ℓ(λ),      s_λ(1^x) =
       ∏_(i,j) ∈λx+j-i/h(i,j),     and     m_λ(1^x)
     = xℓ(λ)ℓ(λ)!/(λ),

where h(i,j) :=λ_i -i
     +λ'_j-j+1 is the hook length of the cell (i,j) in
     the Young diagram of
     λ and (λ):=n_1!n_2!⋯ for λ=⟨ 1^n_1,2^n_2,…⟩.  The middle specialization is the hook content formula.

 
Let  be the fixed (n-1)-cycle (1,2,…,n-1)(n) and
let d_r_1,…,r_k be the number of k-tuples
(π_1,…,π_k) of elements in
𝔖_n such that π_i has r_i cycles for i=1,…,k
 and π_1…π_k =. As mentioned above, the difference c_r_1,…,r_k:=d_r_1,…,r_k-b_r_1,…,r_k is the number of k-tuples (π_1,…,π_k) of
elements in 𝔖_n such that π_i has r_i cycles,
π_1⋯π_k =, and n is a fixed point of each π_i. Thus
c_r_1,…,r_k = a_r_1-1,…,r_k-1 is the number of
factorizations of an (n-1)-cycle _(n-1) as a product of k permutations in
𝔖_n-1 such that the ith factor has r_i - 1 cycles. 

Since the set of permutations with prescribed number of cycles is closed
under conjugation, we apply the Frobenius formula  (Lemma <ref>) to compute
both d_r_1,…,r_k and c_r_1,…,r_k:

    d_r_1,…,r_k   = 1/n!∑_λ∈(𝔖_n)(λ)
                         χ_λ(^-1) _λ(_r_1)
                         ⋯_λ(_r_k),
    
    c_r_1,…,r_k   = 1/(n-1)!∑_λ∈(𝔖_n-1)(λ)
                         χ_λ(_(n-1)^-1) _λ(_r_1-1)
                         ⋯_λ(_r_k-1),

where _r is the formal sum in the group algebra of the symmetric
group (of size n or size n-1 depending on the context) of all elements with r
cycles. Thus the generating functions G( x):= 
∑_r_1,…,r_k d_r_1,…,r_k x_1^r_1⋯ x_k^r_k
and G'( x) := ∑_r_1,…,r_k c_r_1,…,r_k
x_1^r_1⋯ x_k^r_k are given by

    G( x)    = 1/n!∑_λ∈(𝔖_n)(λ)
                         χ_λ(^-1) g_λ(x_1)⋯
      g_λ(x_k),  
    
    G'( x)    = x_1⋯ x_k/(n-1)!∑_λ∈(𝔖_n-1)(λ)
                         χ_λ(_(n-1)^-1) g_λ(x_1)
      ⋯ g_λ(x_k) ,

where 

    g_λ(x) := ∑_k=1^n _λ(_k) x^k.

By the Murnaghan–Nakayama rule <cit.>, one has 
χ_λ(^-1)=0  unless λ equals ⟨ n⟩, ⟨ 1^n⟩,
or one of the near hooks ⟨ n-m-1,2,1^m-1⟩. These representations
have dimensions (λ)=1, 1, and (n-2-m)m/(n-1)!n-2m  and character values χ_λ(^-1) = 1,
(-1)^n, and (-1)^m, respectively.
Similarly,
χ_λ(_(n-1)^-1)=0 unless λ equals a hook
⟨ n-1-m,1^m⟩. These representations have dimension (λ)=n-2m
and character values χ_λ(^-1_(n-1))=(-1)^m. Thus
(<ref>) and (<ref>) become

    G( x)    =
                                                                         1/n!(
                                                                         g_⟨ n⟩(x_1)⋯ 
      g_⟨ n⟩(x_k) + (-1)^n g_⟨ 1^n⟩(x_1)⋯ g_⟨ 1^n⟩(x_k) 
        + ∑_m=1^n-3(n-2-m)m/n-1nm+1 (-1)^m g_⟨ n - m - 1,2,
       1^m-1⟩(x_1)⋯  g_⟨ n - m - 1,2,
       1^m-1⟩(x_k) ), 
    
    G'( x)    = x_1⋯ x_k/(n-1)!∑_m=0^n-2 (-1)^m n-2m g_⟨ n-m-1,1^m⟩(x_1)⋯
                g_⟨ n-m-1,1^m⟩(x_k).

The next lemma evaluates the g_λ(x) when λ is a hook or near hook.

 
We have that

    g_mn(x)    = (x-m)(x-m+1)⋯ (x-m+n-1) 
         = n! ∑_k=m+1^n n-1-mk-1-m·xk, 
    
    g_⟨ n-m-1,2,1^m-1⟩(x)     = x · g_mn-1(x) .




By the stable principal specialization (<ref>) of p_λ, the expansion of a Schur function into
power sum symmetric functions, and the hook length formula for (λ), we have that g_λ(x) equals a stable
principal specialization of a Schur function scaled by the product H_λ of
the hook lengths of λ. That is,

    g_λ(x) = ∑_μn!/z_μ·_λ(μ)· 
    p_μ(1^x) = H_λ· s_λ(1^x).

The first equality of (<ref>) then follows by
applying the stable principal specialization (<ref>) of Schur functions for λ=mn. 
The second equality of (<ref>) is
obtained by using the Chu–Vandermonde identity.[Alternatively, one is expanding H_mn· s_mn into the monomial
basis and doing a stable principle specialization.]
Next we consider (<ref>). By (<ref>) we have that g_⟨ n-m-1,2,1^m-1⟩(x)
is the stable principal specialization of H_⟨ n-m-1,2,1^m-1⟩·
s_⟨ n-m-1,2,1^m-1⟩.  By the hook-content formula and the first
equality of (<ref>) we obtain 

    g_⟨ n-m-1,2,1^m-1⟩(x)    =  H_⟨ n-m-1,2,1^m-1⟩·
    s_⟨ n-m-1,2,1^m-1⟩(1^x) 
       = x · (x-m)(x-m+1)⋯
                                           (x-m+n-2)
       = x · g_mn-1(x).




We continue with the proof of Theorem <ref>. Let G(
  x) := ∑_r_1,…,r_k
  b_r_1,…,r_k x_1^r_1⋯ x_k^r_k. Since
  G( x) is the difference of G( x) and
  G'( x), using (<ref>), (<ref>)  with
  (<ref>) 
  gives

    G( x) 
      =   G( x) - G'( x) 
    = 1/n!( g_⟨ n⟩(x_1)⋯ 
      g_⟨ n⟩(x_k) + (-1)^n g_⟨ 1^n⟩(x_1)⋯ g_⟨ 1^n⟩(x_k) 
    
      - x_1⋯ x_k∑_m=0^n-2nm+1(-1)^m g_⟨ n - m - 1, 1^m⟩(x_1)⋯  g_⟨ n - m - 1, 1^m⟩(x_k) ).

We rewrite the expression in terms of the basis (x_1)_p_1⋯ (x_k)_p_k.  In the case 
p_1=⋯=p_k=n, we see directly from the definition of b_ that b_n,n,…,n=0, and so

    [(x_1)_n/n!⋯(x_k)_n/n!]
        G( x)   =   0.

For any other tuple p_1,…,p_k≥ 1 we use
(<ref>) 
and obtain

    [(x_1)_p_1/p_1!⋯(x_k)_p_k/p_k!]
        G( x)  = 
     (n!)^k-1n-1p_1-1⋯n-1p_k-1 + 
    (n-1)!^k/n!   p_1⋯ p_k∑_m=0^n-2
                                            (-1)^m+1nm+1n-1-mp_1-1-m⋯n-1-mp_k-1-m.

The first term on the RHS corresponds to the term m=-1 in
the sum. We absorb this term to the sum and reindex it using t=m+1
to obtain

    [(x_1)_p_1/p_1!⋯(x_k)_p_k/p_k!]
        G( x)     =
    (n-1)!^k/n!   p_1⋯ p_k∑_t=0^n-1
                                            (-1)^tntn-tp_1-t⋯n-tp_k-t
        = (n-1)!^k/n!   p_1⋯ p_k M^n_p_1,…,p_k,
 
where M^n_p_1,…,p_k is 
defined in (<ref>). This yields the desired result.









§ FACTORIZATION RESULTS FOR THE GROUP G(D,1,N)



We recall the statement our main enumerative theorem  for G(d, 1, n).



For d > 1, let G = G(d, 1, n), let c be a fixed Coxeter element in G, and let a^(d)_r_1,…,r_k be the number of factorizations of c as a product of k elements of G with fixed space dimensions r_1,…,r_k,
respectively.  Then

    ∑_r_1,…,r_k
    a^(d)_r_1,…,r_k x_1^r_1⋯ x_k^r_k = 
    |G|^k-1·∑_p_1,…,p_k ≥ 0
    M^n_p_1,…,p_k(x_1 - 1)^(d)_p_1/d^p_1p_1!⋯(x_k - 1)^(d)_p_k/d^p_kp_k!,

where the polynomial (x - 1)^(d)_p is defined in (<ref>) and M^n_p_1,…,p_k is defined in (<ref>).


The case of two factors (in Theorem <ref>) follows immediately as a corollary, taking k = 2 in Theorem <ref> and using the fact that  M^n_p_1,p_2 = np_1; p_2; n-p_1-p_2.

The main step in the proof of Theorem <ref> is a lemma involving certain cycle-colored factorizations of the element c, which we now describe.  (The remainder of the proof, which is in the spirit of Proposition <ref>, follows the proof of the lemma.)


Given a nonnegative integer x and an element u in G(d, 1, n), let χ denote the color set χ = {0, 1, 2, …, xd}.  Within the color set χ, a d-strip is any of the following collections of d consecutive colors: {1,…,d}, {d+1,…,2d}, …, {(x-1)d+1,…,xd}.  Thus, there are exactly x disjoint d-strips in χ, and the color 0 does not belong to any d-strip.

A cycle-coloring of u is an assignment of a color in χ to each cycle of u so that cycles of nonzero weight receive color 0.  Given nonnegative integers x_1, …, x_k, a colored factorization of an element g of G(d, 1, n) is a factorization g = u_1 ⋯ u_k together with a cycle-coloring of u_i by color set χ_i = {0, 1, …, x_i d} for i = 1, …, k.

Given nonnegative integers p_1, …, p_k, let ^(d, 1, n)_p_1,…,p_k be the set of colored factorizations of the Coxeter element c in G(d, 1, n) with color sets χ_i = {0, …, p_i d} so that at least one color from each d-strip in χ_i is actually used to color a cycle in u_i.  Let C^(d, 1, n)_ = |^(d, 1, n)_|. 



Observe that for factorizations in ^(d, 1, n)_, the coloring of cycles of different factors is completely independent: the requirement in the definition that each strip be used is factor-by-factor, so whether a color from the strip {1, 2, …, d} (for example) is used to color a cycle in u_1 has no bearing on the requirement that a color from that strip be used to color a cycle in u_2 (if p_2 ≥ 1).


The first part of the proof of Theorem <ref> is a formula for C^(d, 1, n)_ in terms of the counts C^⟨ n ⟩_ q of colored factorizations of the n-cycle in _n introduced just before Proposition <ref>.



For any = (p_1, …, p_k) in ^k, we have

    C^(d, 1, n)_ = d^(k-1)n∑_∅≠ S⊆ [k]
    C^⟨ n ⟩_ + _S

where _S is the indicator vector for S.



Given a colored factorization c = u_1 ⋯ u_k of the Coxeter
element c for G(d, 1, n), we associate to it
a colored factorization = π_1 ⋯π_k of the n-cycle  in _n, as follows: π_i is the projection of u_i in _n; if a cycle of u_i is colored with a color in the d-strip {(a - 1)d + 1, …, ad}, then the corresponding cycle of π_i is colored with color a; if a cycle of u_i is colored with color 0, then the corresponding cycle of π_i is colored with color 0.  Thus, in the resulting colored factorization of , the ith factor is colored in either p_i or p_i + 1 colors, with every color appearing.  Let S ⊆ [k] denote the set of indices i such that π_i is colored in p_i + 1 colors (rather than p_i); equivalently, it is the set of indices i such that some cycle of u_i is colored with 0.

First, we observe that S ≠∅: the product c = u_1 ⋯ u_k has nonzero total weight, so at least one of the factors u_i has
nonzero weight, and this factor must have a cycle with nonzero weight. Such a cycle is colored with
the special color 0, and so at least for this value of i we have i ∈ S, as claimed. 
Thus the image of the set ^(d, 1, n)_ of colored factorizations of the Coxeter element c under projection is contained in the disjoint union of pieces
_S^⟨ n⟩_ + _S for nonempty
sets S⊆ [k], where each piece ^⟨
  n⟩_ + _S consists of colored factorizations of the
n-cycle  with the appropriate set of colors used in each
factor (see Remark <ref>).  

Second, we consider how many preimages each factorization in
^⟨ n⟩_ + _S has under this map.  To choose a
preimage, we must assign weights (a_i, 1, …, a_i, n) to the entries of each factor π_i
in such a way that the product of the resulting factors u_i really
is the Coxeter element c, and so that in each u_i, any
cycle of nonzero weight was originally colored by the color 0;
and we must choose one of d colors from a d-strip for each of the
cycles in u_i that corresponds to a cycle in π_i of nonzero
color.

In order to do this, we consider a too-large set of colored factorizations in G(d, 1, n), initially disregarding the requirement that the factored element be c.  Given a colored factorization = π_1 ⋯π_k in ^⟨ n⟩_ + _S with S nonempty, choose a total order on the set {(i, m)  i ∈ [k], m ∈ [n]} of indices of weights to be assigned, in such a way that the last index in the total order belongs to a cycle of color 0 in some factor.  (Such cycles must exist, since S ≠∅.)  Then we assign values to the weights one-by-one according to the chosen order, choosing the weights arbitrarily except in two cases: if an element belongs to a cycle of nonzero color and is the last element (in the given total order) in its cycle, we assign it the unique weight so that the total weight of its cycle is 0; and we choose the weight of the specially selected final element so that the total weight of all elements is 1.  (These two exceptions never conflict because the special element was chosen in a cycle of color 0.)  The number of ways to perform these choices is d^nk - #(colored cycles) - 1.  Finally, for each cycle of π_i that is colored some nonzero color, there are d choices for the color in the associated d-strip of the corresponding cycle of the lift u_i of π_i; this contributes a factor of d^#(colored cycles), for a total of d^nk- 1 lifts of the fixed _n-factorization.

Each lift is a colored factorization u_1 ⋯ u_k in G(d, 1, n) of some element c^* of weight 1 whose underlying permutation is the n-cycle , and every colored factorization of such a c^* with the correct collection of colors is produced by such a lift.  The number of such c^* is d^n - 1; they are exactly the elements conjugate to c by some diagonal matrix a in G(d, 1, n). Moreover, since a is a diagonal matrix, conjugating any w ∈ G(d, 1, n) by a preserves the weight of every cycle of w.  Consequently, conjugation by a extends to a bijection between factorizations of c and factorizations of c^* that respects the underlying permutation of each factor and the weight of each cycle of each factor.  Thus, it gives in particular a bijection between the lifts of π_1 ⋯π_k that factor c and those that factor c^*.  Hence, of the total d^nk - 1 lifts, exactly 1/d^n - 1· d^nk - 1 = d^n(k - 1) of them are factorizations of c.  Since this holds for every nonempty S ⊆ [k] and every factorization in ^⟨ n⟩_ + _S, the lemma is proved.





For any nonnegative integer p, we have ((xd + 1) - 1)^(d)_p = d^p p! ·xp.  
Therefore, the desired statement is equivalent to the equality

    ∑_r_1,…,r_k a^(d)_r_1,…,r_k (x_1d+1)^r_1⋯
    (x_kd+1)^r_k = d^(k - 1)n(n!)^k-1∑_p_1,…,p_k M^n_p_1,…,p_kx_1p_1⋯x_kp_k.

Consider the case that each x_i is a nonnegative integer.
In this case, the LHS of (<ref>) exactly counts the colored factorizations c = u_1 ⋯ u_k of the Coxeter element c in which the cycles of factor u_i are colored with color set χ_i = {0, 1, …, x_id} so that cycles of nonzero weight receive color 0.  Now, we count those factorizations by the number of d-strips that are actually used: for nonnegative integers p_1, …, p_k, there are x_1p_1⋯x_kp_k ways to choose p_i d-strips to use in the ith factor, and C^(d, 1, n)_p_1,…,p_k colored factorizations using exactly these strips.  Thus

    ∑_r_1,…,r_k a^(d)_r_1,…,r_k (x_1d+1)^r_1⋯
    (x_kd+1)^r_k = ∑_p_1,…,p_k C^(d, 1, n)_p_1,…,p_kx_1p_1⋯x_kp_k.

By Lemma <ref>, 

    C^(d, 1, n)_ = d^(k-1)n∑_∅≠ S⊆ [k]
    C^⟨ n ⟩_ + _S.

By Corollary <ref>, we can rewrite this as

    C^(d, 1, n)_ = d^(k-1)n(n!)^k - 1∑_∅≠ S⊆ [k] M^n-1_ - 1 + _S

where 1 is the all-ones vector.  Then the desired equality follows by Proposition <ref>.  Finally, since this identity is valid for all nonnegative integer values of the x_i, it is valid as a polynomial identity, as well.  This completes the proof.







§ FACTORIZATION RESULTS FOR THE SUBGROUP G(D,D,N)



As in the case of the (n - 1)-cycle in _n, factorizations of
a Coxeter element in G(d, d, n) can be separated into two classes
based on a transitivity property that we describe now.  The wreath
product G(d, 1, n) carries a natural permutation action: it acts on
d copies of [n] indexed by dth roots of unity, or equivalently,
on the set {z^i e_j  0 ≤ i < d, 1 ≤ j ≤ n} where
z is a primitive dth root of unity and e_j are the standard
basis vectors for ^n.  The Coxeter elements for G(d, 1, n) act
transitively on this set, and consequently every factorization of a
Coxeter element in G(d, 1, n) is a transitive factorization.
However, the same is not true for the subgroup G(d, d, n), where the
underlying permutations of the Coxeter elements are (n - 1)-cycles.  The action of the Coxeter element c_(d, d, n) divides {z^i e_j  0 ≤ i < d, 1 ≤ j ≤ n} into two orbits, {z^i e_j  0 ≤ i < d, 1 ≤ j < n} and {z^i e_n  0 ≤ i < d}.  Thus, a factorization of c_(d, d, n) will be transitive if and only if some factor sends an element of the second orbit to an element of the first, or equivalently if the underlying factorization in _n is transitive. In enumerating factorizations of c_(d, d, n), we handle the transitive and nontransitive factorizations separately.



 §.§ Transitive factorizations


As mentioned in the introduction, our generating function in this case is in terms of the polynomials kdx defined by 
0dx = 1, 1dx = x, and for k > 1

    kdx :=  ∏_i = 1^k (x - e^*_i) = (x - (k - 1)(d - 1)) · (x - 1)^(d)_k - 1  = (x-1)^(d)_k + k(x-1)^(d)_k-1

where the e^*_i are the coexponents of the group G(d, d, k).  Next, we recall the statement to be proved.

 
For d > 1, let G = G(d, d, n) and let
 b^(d)_r_1,…,r_k be the number of transitive factorizations of a Coxeter element c_(d, d, n) in G as a product of k
elements of G with fixed space dimensions r_1,…,r_k, respectively. 
Then

    ∑_r_1,…,r_k
      ≥ 0 b^(d)_r_1,…,r_k x_1^r_1⋯ x_k^r_k
     = |G|^k-1/n^k∑_p_1,…,p_k ≥ 1
     M^n_p_1,…,p_kp_1dx_1/d^p_1-1 (p_1-1)!⋯p_kdx_k/d^p_k-1 (p_k-1)!,

where M^n_p_1,…,p_k is as defined in (<ref>).
 

The case of two factors (in Theorem <ref>) follows immediately as a corollary, taking k = 2 in Theorem <ref> and using the fact that M^n_p,q = np; q; n-p-q = n(n - 1)/pqn - 2p - 1; q - 1; n - p - q.

As in Section <ref>, we split the proof into two parts.  The first concerns colored factorizations of the kind defined in Definition <ref>.  Fix the standard (n - 1)-cycle  in _n and Coxeter element c_(d, d, n) = [; (0, …, 0, 1, -1)] in G(d, d, n).  Given nonnegative integers p_1, …, p_k, let C^(d, d, n)_p_1,…,p_k be the number of colored transitive factorizations c_(d, d, n) = u_1 ⋯ u_k in G(d, d, n) with color sets χ_i = {0, 1, …, p_id} so that at least one color from each d-strip in χ_i is actually used to color a cycle in u_i.



We have

    C^(d, d, n)_p_1,…,p_k = ∑_S⊆ [k] d^(k-1)n-|S|+1 C^⟨ n - 1, 1 ⟩_ + _S,

where _S is the indicator vector for S and C^⟨ n - 1, 1 ⟩_ =
(n!)^k - 1p_1 ⋯ p_k/n^k· M^n_ is
the coefficient of x_1p_1⋯x_kp_k in the
RHS of (<ref>). 


As in the proof of Lemma <ref>, we use the natural projection from colored factorizations of this sort to colored factorizations of the (n - 1)-cycle  in _n, where under projection a cycle that is colored by a color in the d-strip {(a - 1)d + 1, …, ad} gets sent to a cycle colored a, while a cycle colored by color 0 gets sent to a cycle of color 0.  If the original factorization is colored with colors , the projected factorization is colored with colors + _S for some subset S ⊆ [k].  

Fix a subset S ⊆ [k] and fix a colored transitive factorization π_1 ⋯π_n = using + _S colors.  We count preimages of this factorization under the projection.  As before, we consider a too-large set of colored factorizations, initially disregarding the requirement that the factored element be c_(d, d, n).   We start by describing a total order on the nk-element set {(i, m)  i ∈ [k], m ∈ [n]} of indices of weights to be chosen; we will then see that the elements may be assigned weights in /d in this order in such a way that the number of valid choices of weights for each entry does not depend on earlier selections.

First, consider the k indices T = {(k,n), (k - 1, π_k(n)), (k - 2, π_k-1π_k(n)), …, (1, π_2⋯π_k(n))}.  These are the coordinates on the “thread” connecting n to n in the braid diagram of the factorization – see Figure <ref>.  Say that the pair (i, π_i + 1⋯π_k(n)) is problematic if the number π_i + 1⋯π_k(n) is a fixed point of π_i; extend the adjective “problematic” to the 1-cycle (π_i + 1⋯π_k(n)) of π_i.  Since we started with a transitive factorization of , not all values in T can be problematic.  The k values in T will form the first k values in our linear order; moreover, we choose a nonproblematic value to be the last among these k.



For any i and any nonproblematic cycle of π_i, there is an index (i, m) corresponding to an entry of this cycle that is not among those already selected: at most one entry was selected from each cycle, and the only 1-cycles from which an entry was selected are the problematic ones, by definition.  Therefore, for each i, we may select from every nonproblematic cycle of π_i an index pair (i, m) that was not already selected in the previous step.  These values form the last values in our linear order.  Moreover, for each i such that the color 0 is used in a nonproblematic cycle in π_i, we arrange our order so that the index from one such cycle is last among the indices coming from that factor π_i.

All the remaining indices go in the middle, in any order.

Now we assign weights one-by-one, according to the selected total order.  We choose these arbitrarily, with the following exceptions:


  * among the first k - 1 indices, a problematic index is assigned weight 0 if its cycle has nonzero color, or if its cycle has color 0 and this is the only cycle of color 0 in its factor;

  * the kth entry is assigned the unique value so that the sum of the first k weights assigned (those that appear in the special thread connecting n to n) is -1;

  * an index that is the last (in the total order) in its cycle, and this cycle has nonzero color, is assigned the unique weight so that its cycle has weight 0; and

  * an index (i, m) that is the last (in the total order) in its factor π_i, and π_i has a nonproblematic cycle of color 0, is assigned the unique weight so that the weights assigned to π_i sum to 0.

One can check that such an assignment of weights is always well defined (i.e., the different cases are disjoint); that the resulting product u_1 ⋯ u_k is equal to an element c^*_(d, d, n) that is conjugate to c_(d, d, n) by a diagonal matrix; and moreover that every transitive factorization of every such element c^*_(d, d, n) arises from this construction.

Now we turn this into a counting argument.  By splitting the first bullet above into two cases, we see that each of the nk indices has exactly d choices of weight, with the following exceptions:


  * the (unique) values in problematic cycles with nonzero color;

  * the (unique) values in problematic cycles with color 0 for which there are no other cycles of color 0 in the permutation;

  * the kth value;

  * the last value in each nonproblematic cycle of nonzero color; and

  * the last value in each permutation that has a nonproblematic cycle of color 0.

Observe that the number of values in (1) and (4) together is exactly
the number of cycles with nonzero color, while the number of values in
(2) and (5) together is exactly the number of factors that have cycles
of color 0.  Therefore, the total contribution from the weighting is 

    d^nk - #(nonzero colored cycles) - #(factors with cycle
        colored 0) - 1.

 

In addition, each colored cycle gets assigned one of d colors from its strip, hence we must multiply by d^#nonzero colored cycles.  Since the number of factors with a cycle colored 0 is exactly |S|, we have by Remark <ref> that the total number of factorizations produced in this way is

    ∑_S ⊆ [k] d^nk - |S| - 1 C^⟨ n - 1, 1 ⟩_ + _S.

Finally, we must account for the fact that we have counted not merely factorizations of the Coxeter element c_(d, d, n), but also factorizations of all of its conjugates by diagonal matrices.  The number of these is precisely d^n - 2, and as in the case of G(d, 1, n), conjugation by a diagonal matrix is a bijection from factorizations to factorizations that preserves weights of all cycles, so they all have the same numbers of colored factorizations.  Consequently

    C^(d, d, n)_ = ∑_S ⊆ [k] d^n(k - 1) - |S| + 1 C^⟨ n - 1, 1 ⟩_ + _S,

as claimed.










First consider the RHS of the equation to be proved.  Make the substitution x_i ↦ x_id + 1 for each i.
From (<ref>) we have that 

    rdxd+1/d^r-1 r! =  dxr + xr-1.

Therefore, we have

    |G|^k - 1/n^k∑_p_1,…,p_k M^n_p_1,…,p_k∏_i = 1^k p_idx_id + 1/d^p_i-1 (p_i - 1)!
    
    
    
    
        = d^(n - 1)(k - 1)∑_p_1,…,p_k C^⟨ n - 1, 1⟩_p_1, …, p_k∏_i = 1^k p_idx_id + 1/d^p_i-1 p_i!
    
        = d^(n - 1)(k - 1)∑_p_1,…,p_k C^⟨ n - 1, 1⟩_p_1, …, p_k∏_i = 1^k (dx_ip_i + x_ip_i-1) 
    
        = d^(n - 1)(k - 1)∑_p_1, …, p_k(∑_S ⊆ [k] d^k - |S| C^⟨ n - 1, 1⟩_ + _S) x_1p_1⋯x_kp_k,

where in the first step we use Remark <ref> and in
the last step _S is the indicator vector for the set
S, as usual.  Collecting the power of d and applying
Lemma <ref>, this becomes

    |G|^k - 1/n^k∑_p_1,…,p_k M^n_p_1,…,p_k∏_i p_idx_id + 1/d^p_i-1 (p_i - 1)!
    =
    ∑_p_1,…,p_k C^(d, d, n)_p_1,…,p_kx_1p_1⋯x_kp_k.


Now consider the LHS of the equation to be proved.  Again make the substitution x_i ↦ x_id + 1, and think of x_i as representing a nonnegative integer.  Then the LHS is the number of colored transitive factorizations of c_(d, d, n).  The number of ways to choose p_i d-strips that are actually used in the ith factor is x_ip_i, and the number of colored factorizations in this case is exactly C^(d, d, n)_p_1,…,p_k.  Thus

    ∑_r_1,…,r_k
      ≥ 0 b^(d)_r_1,…,r_k (x_1d+1)^r_1⋯ (x_kd+1)^r_k =
    ∑_p_1,…,p_k C^(d, d, n)_p_1,…,p_kx_1p_1⋯x_kp_k,

exactly the expression (<ref>) we found for the RHS.  Since the
two sides are equal for nonnegative integers x_i, their equality is
valid as a polynomial identity, as well.  This completes the proof.









 §.§ Nontransitive factorizations


In the case of nontransitive factorizations of the Coxeter element c_(d, d, n) in G(d, d, n), we are again able to give a combinatorial formula for the number of colored factorizations, and thereby produce a generating function for factorization counts.  However, the lemma is more complicated than those in the preceding cases, and does not seem to yield a “nice” formula in a single basis, as in Theorems <ref> and <ref>.

We consider cycle-colored factorizations of the kind defined in Definition <ref>.  Given nonnegative integers p_1, …, p_k, let B^(d, d, n)_p_1,…,p_k be the number of nontransitive factorizations c_(d, d, n) = u_1 ⋯ u_k in G(d, d, n) such that, for i = 1,…, k, the weight-0 cycles of u_i are colored with colors from color set χ_i = {0, 1, …, p_id} so that at least one color from each d-strip in χ_i is actually used to color a cycle.



For integers n, d ≥ 2, with B^(d, d, n)_p_1, …, p_k defined above, we have

    B^(d, d, n)_p_1,…,p_k = d^n(k - 1) + 1∑_S, T, U ⊆ [k]: 
     S ∩ T ≠∅
     S ∩ U = ∅
    d^- |S ∪ T|·∏_i ∉S p_i ·
    C^⟨ n - 1 ⟩_ + _T - _U,

where _S is the indicator vector for S and C^⟨ n - 1 ⟩_ =
((n - 1)!)^k - 1· M^n - 2_ -  1 is the count of colored factorizations of the (n - 1)-cycle in _n - 1 introduced just before Proposition <ref>.



We use the same projection as in the previous two cases.  Consider a colored nontransitive factorization u_1 ⋯ u_k of the Coxeter element c_(d, d, n) in G(d, d, n), in which factor u_i uses a color set of size dp_i + 1 and every d-strip is used at least once.  Since the factorization is nontransitive, n is a fixed point in each π_i, i.e., (n) is a cycle.  Let S be the subset of [k] recording factors in which the cycle (n) has color 0, and let T be the subset of [k] recording factors in which there is a cycle of color 0 that is not the cycle (n).  Then the image under projection is a colored nontransitive factorization of  in _n using + _S ∪ T colors.

We have two calculations to make: computing the number of preimages of each of these _n-factorizations under projection, and counting the total number of _n-factorizations in the image.  We begin by some basic observations about the possibilities for S and T.

First, S must be nonempty: the standard basis vector e_n  is an eigenvector for all of u_1, …, u_k and c_(d, d, n), and its eigenvalue for c_(d, d, n) is not 1; therefore its eigenvalue cannot be 1 for all of the u_i.  Thus there must be at least one i for which the singleton cycle (n) has nonzero weight in u_i, and consequently has color 0.  Thus for this i we have i ∈ S.  In fact, we can say more: since u_i ∈ G(d, d, n), the remaining cycles of u_i have weights that sum to something nonzero, so at least one of them must have nonzero weight and hence color 0, as well, and thus i ∈ S ∩ T.

Now suppose that S, T are subsets of [k] with nonempty
intersection and π_1 ⋯π_k is a colored factorization of
the form just described.  That is, it is a colored nontransitive
factorization of the (n - 1)-cycle  in which the cycles of
factor π_i are colored with color set {1, …, p_i} if i
∉S ∪ T or with color set {0, 1, …, p_i} if i ∈
S ∪ T, every color being used at least once, and moreover in the latter case the cycle (n) is colored with color 0 if and only if i ∈ S, and some other cycle is colored with color 0 if and only if i ∈ T. 

We proceed as in the previous arguments, aiming first to give a
factorization of any element c^* that is a conjugate of c_(d, d,
  n) by a diagonal matrix.  Choose a fixed index i in S ∩ T.
Order the nk weights to be assigned as follows: first the weights for
every u_j with j ∉S∪ T; then the weights for every
u_j with j ∈ (S ∪ T) ∖{i}; then the weights
for u_i, arranged so that the last weight is in a cycle of color 0
that is not the fixed point.  (Such a choice is possible by the
definition of S and T.)  In this order, every weight can be chosen
freely in /d (giving d choices), with the following exceptions:


  * if j ∉S ∪ T, every cycle is colored with a nonzero color, so has weight 0; so the last element (in the total order) in each cycle is chosen with the unique weight that works;

  * if j ∈ (S ∪ T) ∖{i} and the weight being chosen is the last element (in the total order) in a cycle of nonzero color, it is assigned the unique value that gives its cycle weight 0;

  * if j ∈ (S ∪ T) ∖{i} and the weight being chosen is the last element (in the total order) among those that appear in cycles of color 0, it is assigned the unique value so that the weight of u_j is 0;

  * if j = i and the weight being chosen is the weight of the fixed point, it is assigned the unique value so that the weight of the fixed point in the product u_1 ⋯ u_k is -1;

  * if j = i and the weight being chosen is the last element (in the total order) in a cycle of nonzero color, it is assigned the unique value that gives its cycle weight 0; and

  * if j = i and the weight being chosen is the very last element
  in the total order, it is assigned the unique value that gives u_j weight 0.

The number of values in (1), (2), and (5) together is exactly the number of cycles with nonzero color, while the number of values in (3), (4), and(6) together is exactly |S ∪ T| + 1. 
Therefore, the total contribution from the weighting is 
d^nk - #nonzero colored cycles - |S ∪ T| - 1.  In addition, each cycle with nonzero color gets assigned one of d colors from its strip, hence we must multiply by d^#nonzero colored cycles.  Finally, the number of conjugates of c_(d, d, n) by diagonal matrices is d^n - 2.  Thus, the number of preimages of a factorization with the given pair (S, T) is exactly 

    d^nk - #(nonzero colored cycles) - |S ∪ T|  - 1· d^#nonzero colored cycles· d^2 - n
    = d^n(k - 1) - |S ∪ T| + 1.


Now we must compute the actual size of the image, that is, how many _n-factorizations are in the projection of G(d, d, n)-factorizations (with the sets S, T fixed).  To do this, we further project factorizations of  in _n to factorizations of the (n - 1)-cycle _n - 1 in _n - 1, by removing the fixed point.  In this projection, there will be some subset U ⊆ [k] ∖ S of indices in which the (necessarily nonzero) color used to color the fixed point (n) is the unique appearance of that color; thus, the image of this projection belongs to ^⟨ n - 1 ⟩_ + _T - _U.  Moreover, the number of preimages of each factorization is easily seen to be ∏_i ∈ [k] ∖ S p_i, since we must choose which of the original nonzero colors was attached to the fixed point (whether that involves choosing an existing color or adding a new color and possibly relabeling).

Combining these two projections, we have that for fixed S, T, the number of nontransitive colored factorizations in G(d, d, n) is

    d^n(k - 1) + 1∑_S, T, U ⊆ [k]: 
     S ∩ T ≠∅
     S ∩ U = ∅
    d^- |S ∪ T|·∏_i ∉S p_i ·
    C^⟨ n - 1 ⟩_ + _T - _U,

as claimed.


 
As in Section <ref>, we have that Lemma <ref> gives the coefficient for the polynomial
counting nontransitive factorizations of the Coxeter element when
expressed in the basis (x - 1)^(d)_p/d^p p!.  Obviously,
though, these coefficients are much messier (involving a triple sum
over subsets) than those of earlier sections.  In principle, it is
possible to express this polynomial in other bases; however, all
expressions we have produced in a single basis seem inherently
complicated.  Using the algebraic approach (with
Lemma <ref>, building on the arguments in
<cit.>), we have been able to produce the expression

    |G|^k-1/n^k-1∑_p_1,…,p_k ≥ 1
     M^n-2_p_1-1,…,p_k-1(  ∑_S⊆ [k]((d-1)^k-|S| - (-1)^k-|S|) ∏_i∈ Sx_i
      p_idx_i/d^p_i p_i!∏_i∈S(x_i-1)_p_i-1^(d)/d^p_i (p_i-1) !)

for the generating function for all nontransitive factorizations. This
expression can be rewritten in many ways, for instance as

    |G|^k-1/n^k-1∑_p_1,…,p_k ≥ 1
     M^n-2_p_1-1,…,p_k-1( ∏_i = 1^k Q_p_i(x_i)
    -
     ∏_i = 1^k Q'_p_i(x_i) ),

where
Q_p(x) := (x^2 - (d - 1)(p - 1)x + p(d - 1)) (x - 1)^(d)_p - 1/d^p p! and
Q'_p(x) := (x^2 - (d - 1)(p - 1)x - p) (x - 1)^(d)_p - 1/d^p p!. 
Frustratingly, however, we have not been able to derive this formula directly from Lemma <ref>.







§ EXCEPTIONAL COMPLEX REFLECTION GROUPS



In this section, we record some tantalizing data that suggests that Theorems <ref> and <ref> could be particular cases of a more general, uniform statement, along the lines of the Chapuy–Stump result (Theorem <ref>).  

In all sections below, we use the following fixed notations: G represents an irreducible well generated complex reflection group; k represents a positive integer; = (r_1, …, r_k) and = (p_1, …, p_k) represent tuples in {0, 1, …, n}^k, where n is the rank of G; a_ represents the number of factorizations of a fixed Coxeter element c in G as a product u_1 ⋯ u_k = c where u_i = r_i; and

    F_G(x_1, …, x_k) := ∑_ a_· x_1^r_1⋯ x_k^r_k.




 §.§ Rank two

There are two infinite families of irreducible rank-2 well generated complex reflection groups, the wreath products (/d) ≀_2 (of type G(d, 1, 2)) and the dihedral groups (of type G(d, d, 2)), as well as twelve exceptional groups (Shephard–Todd classes G_4, G_5, G_6, G_8, G_9, G_10, G_14, G_16, G_17, G_18, G_20, and G_21).  For each such group, define the polynomials

    P_2(x) = (x - e^*_1)(x - e^*_2)/|G|,     
    P_1(x) = x - 1/d_1,     
    P_0(x) = 1.

In this basis, we have the following result, which should be compared with Theorem <ref>.


Let G be an irreducible well generated complex reflection group of rank 2, and let a_, F_G, and P_i be defined as above.  Then one has

    F_G(x_1, …, x_k) = |G|^k- 1∑_
     M^2_· P_p_1(x_1) ⋯ P_p_k(x_k).

In the case k = 2, this may be written in the form

    F_G(x, y) = (x - 1)(x - e^*_2) + N(x - 1)(y - 1) + (y - 1)(y - e^*_2) + 2h(x - 1) + 2h(y - 1) + |G|

where h = d_2 is the Coxeter number of G and N = 2h/d_1 is the number of reflections that can appear in a shortest reflection factorization of c.


We handle the two infinite families and the exceptional cases
separately:



  §.§.§ The infinite family G(d, 1, 2)
 For this group this is exactly the statement of Theorem <ref>.  



  §.§.§ The infinite family G(d,d,2)
 For G(d, d, 2), the basis {P_2(x), P_1(x), P_0(x)} here is related to the basis {2dx, 1dx, 0dx} of Theorem <ref> by the equations
2dx/d^1 · 1! = 
2 · P_2(x), 1dx = 
2P_1(x) + P_0(x), and 0dx = P_0(x).  So from
Theorem <ref>, the contribution to F_G of the transitive
factorizations is

    |G|^k - 1/2^k∑_ : p_i ≥ 1 M^2_∏_i : p_i = 2 2 P_2(x_i) ∏_i: p_i = 1 (2P_1(x_i) + P_0(x_i)).

If  is a permutation of the multiset { 2^a, 1^b, 0^c}, then the coefficient of ∏_i P_r_i(x_i) in this polynomial is |G|^k - 1/2^k· 2^a · 2^b · 1^c M^2_2^a, 1^b + c = |G|^k - 1/2^cM^2_2^a, 1^b + c.  

For the contribution to F_G from the nontransitive factorizations, we use the expression in (<ref>). The only contribution we
get is for the tuple p= 1, where M^0_ 0 = 1.  We obtain

    |G|^k-1/2^k-1(∏_i=1^k Q_1(x_i) - ∏_i=1^k Q'_1(x_i)),

where Q_1(x) = x^2+d-1/d =
2P_2(x) + 2P_1(x)+1 and Q'_1(x) =  x^2-1/d = 2P_2(x) +
2P_1(x). If   is a permutation of the multiset {2^a,1^b, 0^c}, then the coefficient
of ∏_i P_r_i(x_i) in this polynomial is d^k-1 2^a+b= 2 ·|G|^k - 1/2^c if
c>0 and 0 otherwise.

Finally, we sum these two contributions: when c = 0, the transitive case contributes exactly the desired |G|^k - 1 M^2_ while the nontransitive case contributes 0.  From the explicit formula (<ref>) for M^n_ we can see that when c > 0, M^2_2^a, 1^b + c = 2^b + c - 2 = 2^c M^2_ - 2, so in this case the transitive case contributes |G|^k - 1 M^2_ - 2 |G|^k - 1/2^c while the nontransitive case contributes the missing 2 ·|G|^k - 1/2^c.



  §.§.§ Exceptional rank 2 cases
 In each of the exceptional
cases, we use the algebraic technique outlined in
Section <ref> together with character tables for the
exceptional groups available in  Sage <cit.> via its interface with the GAP <cit.> package Chevie, as follows: for each group G and each irreducible character χ for G such that χ(c^-1) ≠ 0, we compute the character polynomial

    f_χ(x) := ∑_g ∈ G(g) · x^(g),

where = χ/χ(1) is the normalized character.  (Tables of these polynomials are collected in Appendix <ref>.) Then by Lemma <ref> we have that

    F_G(x_1, …, x_k)    = ∑_1/|G|∑_λ∈(G)(λ) χ_λ(c^-1) ∏_i = 1^k (x_i^r_i∑_g (g) = r_i_λ(g) ) 
        = 1/|G|∑_λ∈(G)(λ) χ_λ(c^-1) ∏_i = 1^k f_χ_λ(x_i).

Next we express each character polynomial in the P_is and extract the coefficient.

For example, in the group G_6 (see Table <ref>), with coexponents 1, 9, degrees 4, 12, and order |G_6| = 4 · 12 = 48, there are 12 characters χ for which χ(c^-1) ≠ 0, but only four different character polynomials:



x^2 + 14x + 33        (associated only to the trivial representation), 

x^2 -10x + 9        (associated to two 1-dimensional representations), 

x^2 - 4x + 3        (associated to two 2-dimensional representations), and 

x^2 + 2x - 3         (associated to three 1-dimensional and four 2-dimensional representations).



In terms of the basis P_2(x) = (x - 1)(x - 9)/4 · 12, P_1(x) = x - 1/4, P_0(x) = 1, these can be rewritten respectively as

    48(P_2 + 2P_1 + P_0),      48 P_2,      24(2P_2 + P_1),      and      48(P_2 + P_1).

The respective character values χ(c^-1) that appear with these
polynomials are {1}; {exp(2π i / 6), exp(5π i/3)}; {± i}; and {-1, exp(2π i/3), exp(2 π i · 2/3)} (for
the 1-dimensional representations) and {exp(2
π i / 12), exp(2 π i · 5/12), exp(2 π i · 7/12),
exp(2 π i · 11/12)} (for the 2-dimensional representations).  Plugging these in to (<ref>) yields

    F_G_6(x_1, …, x_k)     = 1/|G_6|(
    1 · 1 ·∏_i = 1^k 48(P_2(x_i) + 2P_1(x_i) + P_0(x_i)) + 
    1 · 1 ·∏_i = 1^k 48P_2(x_i) + . 
       . 2 · 0 ·∏_i = 1^k 24(2P_2(x_i) + P_1(x_i)) +
    (1 · (-2) + 2 · 0) ·∏_i = 1^k 48(P_2(x_i) + P_1(x_i))
    ) 
        = |G_6|^k - 1(∏_i = 1^k (P_2(x_i) + 2P_1(x_i) + P_0(x_i)) - 2∏_i = 1^k (P_2(x_i) + P_1(x_i)) + ∏_i = 1^k P_2(x_i)).

Finally, the coefficient of ∏_i = 1^k P_r_i(x_i) in the expansion of this expression is (up to the power of |G_6|) the same as the coefficient of ∏_i = 1^k x_i^r_i in the polynomial 

    ∏_i = 1^k (x_i^2 + 2x_i + 1) - 2∏_i = 1^k (x_i^2 + x_i) + ∏_i = 1^k x_i^2 = ( ∏_i = 1^k (x_i + 1) - ∏_x = 1^k x_i )^2,

and comparing the last expression with the definition of M^n_ in (<ref>) gives the result.  

The calculations in the other eleven cases are analogous.




 §.§ Rank three



There are two infinite families of well generated irreducible complex
reflection groups of rank 3 (the wreath product (/d) ≀_3 of type G(d, 1, 3) and its weight-zero subgroup G(d, d,
3)) and five exceptional groups (Shephard–Todd classes G_23
(also the Coxeter group of type H_3), G_24, G_25, G_26,
and G_27).  Our next result covers all of these groups
except G_25. The choice of polynomial basis assigned to
each group is discussed further in Remark <ref>.

 
For G of type G(d, 1, 3) or G_23 or G_26, define for i=0,1,2,3 the polynomials

    P^G_i(x) = ∏_j = 1^i x - e^*_j/d_j.

For G of type G(d, d, 3), define

    P^G(d, d, 3)_0(x) = 1,    P^G(d, d, 3)_1(x) = (d + 1)(x
      - 1)/3d(= d + 1/d·x - 1/d_1 for 
    d≥ 3), 
     P^G(d, d, 3)_2(x) = (x - 1)(x - d)/3d,     and     P^G(d, d, 3)_3(x) = (x - 1)(x - d - 1)(x - 2d + 2)/6d^2 = ∏_i = 1^3 x - e^*_i/d_i.

For G of type G_24, define

    P^G_24_0(x) = 1,      P^G_24_1(x) = x - 1/3 = 4/3·x - 1/d_1,      P^G_24_2(x) = (x - 1)(x - 7)/24 = (x - 1)(x - 7)/d_1d_2, 
    and     P^G_24_3(x) = (x - 1)(x - 9)(x - 11)/336 = ∏_i = 1^3 x - e^*_i/d_i.

For G of type G_27, define

    P^G_27_0(x) = 1,      P^G_27_1(x) = 2(x - 1)/9 = 4/3·x - 1/d_1,      P^G_27_2(x) = (x - 1)(x - 15)/72 = (x - 1)(x - 15)/d_1d_2, 
    and     P^G_27_3(x) = (x - 1)(x - 19)(x - 25)/2160 = ∏_i = 1^3 x - e^*_i/d_i.








If G is of type G(d, 1, 3), G(d,d,3), G_23, G_24 , G_26 or G_27, then

    F_G(x_1, …, x_k) = |G|^k - 1∑_ M^3_· P^G_p_1(x_1) ⋯ P^G_p_k(x_k).





We again proceed case-by-case.



  §.§.§ The infinite family G(d, 1, 3)
 
For this group this is exactly the statement of Theorem <ref>. 



  §.§.§ The infinite family G(d, d, 3)


Write P_i for the polynomial P^G(d, d, 3)_i of Definition <ref>.  We begin with the contribution from the transitive factorizations.  The formulas 3dx/2d^2 = 3 P_3(x), 2dx/d = 3P_2(x) + 3/d + 1 P_1(x), and 1dx = 3d/d + 1P_1(x) + P_0(x) express the basis of Theorem <ref> in terms of this basis. 
Thus, for a sequence  that is a rearrangement of {3^a, 2^b, 1^c, 0^e} with a + b + c + e = k, the coefficient of ∏_i P_r_i(x_i) in

    |G|^k-1/3^k∑_p_1,…,p_k ≥ 1
     M^3_p_1,…,p_kp_1dx_1/d^p_1-1 (p_1-1)!⋯p_kdx_k/d^p_k-1 (p_k-1)!

is

    T()     := |G|^k-1/3^k· 3^a · 3^b ·∑_S ⊆ [c] M^3_(1^c, 3^a, 2^b, 1^e) + _S(3/d + 1)^|S|(3d/d + 1)^c - |S|
       = |G|^k-1/3^k·3^a + b + c/(d + 1)^c∑_S ⊂ [c] M^3_(1^c, 3^a, 2^b, 1^e) + _S d^c - |S|.

Next, we simplify using the formula 

    M^3_3^a,2^b,1^c,0^e = 
    3^b+c    if  e>0
    
    3^b+c-3· 2^b     if  e=0, c>0
    
    3^b-3· 2^b+3     if  c = e=0, b>0
    
    0     if  b = c = e = 0

for M^3_ derived from the explicit definition (<ref>) to obtain 

    T() = |G|^k-1·
      3^b+c - 3^1-e· 2^b ·(d+2/d+1)^c     if  e >0 
    
      3^b + c - 3 · 2^b ·(d + 2/d + 1)^c + 3/( d+ 1)^c    if  e = 0, c>0
    
     3^b -3· 2^b +3    if  c = e = 0, b>0
    
     0     if  b = c = e = 0.


Now we calculate the nontransitive contribution using the expression in (<ref>). From this expression we get a
contribution for the tuples ∈{1, 2}^k other than 2 = (2, …, 2), and for each such tuple we have M^1_ -  1=1. Thus we obtain the generating function

    |G|^k-1/3^k-1∑_≠ 2, p_i ∈{1,2}(∏_i=1^k Q_p_i(x_i) - ∏_i=1^k Q'_p_i(x_i)).

We have the change of basis formulas

    Q_1(x)     = 3P_2(x) + 3P_1(x)+1,    
    Q'_1(x)     =  x^2-1/d = 3P_2(x) + 3P_1(x), 
    
    Q_2(x)    = (x^2-dx+x+2 d-2)(x-1)/(2d^2)     
    Q'_2(x)    = (x^2-dx+x-2)(x-1)/(2d^2) 
        =3P_3(x)+3P_2(x)+3/d+1P_1(x),        =3P_3(x)+3P_2(x).

For a sequence  that is a rearrangement of {3^a, 2^b, 1^c,
0^e} with a + b + c + e = k, let N() denote the coefficient
of ∏_i P_r_i(x_i) in (<ref>). Using the
change of basis formulas above, after some calculations we obtain the
following formula for N( r):

    N()  = |G|^k-1·
      2^b · 3^1-e·(d + 2/d + 1)^c       if  e >0,
    
     3· 2^b (d+2/d+1)^c - 3· 2^b + 3/(d + 1)^c    if  e =0, c>0,
    
     0     otherwise.

Combining this with (<ref>), it is easy to see that T()+N() equals |G|^k-1 M^3_ in each of the cases.



 


  §.§.§ Exceptional rank 3 cases

In the four exceptional cases, we use exactly the same approach as in the proof of Theorem <ref>.  In place of (<ref>), one ends up in all four cases with the expression 

    |G|^k- 1( ∏_i (P_3(x_i) + 3P_2(x_i) + 3P_1(x_i) + 1) - 3∏_i (P_3(x_i) + 2P_2(x_i) + P_1(x_i)) + . 
    .  + 3∏_i (P_3(x_i) + P_2(x_i)) - ∏_i P_3(x_i) ),

from which the result follows.





The choice of basis polynomials P_i, especially for G_24 and G_27, appears somewhat mysterious, and indeed they were initially discovered experimentally.  However, the roots that appear are not arbitrary.  Given a complex reflection group G acting on a space V, consider the intersection lattice L of the reflecting hyperplanes of G, ordered by reverse-inclusion.  Let χ(L, x) := ∑_X ∈ Lμ(V, X) x^ X be the characteristic polynomial of L (where μ is the poset-theoretic Möbius function).  In <cit.>, Orlik and Solomon show that χ(L, x) factors as ∏_i (x - e^*_i).  But, in fact, they show more: if X ∈ L is any particular intersection of reflecting hyperplanes, then the upper interval L^X := [X, {0}] in L (which is isomorphic to the lattice of the arrangement of intersections of the reflecting hyperplanes with X) satisfies χ(L^X, x) = ∏_i = 1^ X (x - b^X_i) for some positive integers b^X_i.  (Tables of these Orlik–Solomon coexponents are collected in <cit.>.)  For the group G(d, 1, n), when X is a subspace of dimension m, Orlik and Solomon show that (b^X_i)_1 ≤ i ≤ m = (1, 1 + d, …, 1 + (m - 1)d) depends only on the dimension of X.  Similarly, in the other irreducible groups of rank 2 and 3 (both exceptional and G(d, d, n)), the tuple of integers (b^X_i) depends only on X.  In fact, in all of these groups except G(d, d, 3), G_24, and G_27, these Orlik–Solomon coexponents are a prefix of the sequence (e^*_i) of coexponents.  In G_24, the coexponents are (1, 9, 11) and the Orlik–Solomon coexponents in dimension 2 are (1, 7); in G_27, the coexponents are (1, 19, 25) and the Orlik–Solomon coexponents in dimension 2 are (1, 15); and in G(d, d, n), the coexponents are (1, d + 1, 2d - 2) and the Orlik–Solomon coexponents in dimension 2 are (1, d).  One immediately notes the relationship to the polynomials in Definition <ref>.  (We do not have an explanation (or even an “explanation”) for the factors 4/3 and d + 1/d that appear there.)



For the group G_25, one can show that there are no polynomials P_i
of degree i for i=0,1,2,3 such that 

    F_G_25(x_1, …, x_k) = |G|^k - 1∑_ M^3_· P_p_1(x_1) ⋯ P_p_k(x_k).

Nevertheless, one can use the character tables to compute a formula for F_G_25: the group has coexponents (e^*_1, e^*_2, e^*_3) = (1, 4, 7) and degrees (d_1, d_2, d_3) = (6, 9, 12).  Taking P_i(x) = ∏_j = 1^i x - e^*_i/d_i, one has

    F_25(x_1, ⋯, x_k)/|G_25|^k - 1 = ∏_i = 1^k(P_3(x_i) + 3P_2(x_i) + 3P_1(x_i) + 1) 
    - 3 ·∏_i = 1^k(P_3(x_i) + 2P_2(x_i) + P_1(x_i) )  
     - 3 ·∏_i = 1^k(P_3(x_i) + P_2(x_i)  )
    - ∏_i = 1^k P_3(x_i)
    - 3 ·∏_i = 1^k(P_3(x_i) + P_2(x_i) + P_1(x_i) /3)    
    + 9 ·∏_i = 1^k(P_3(x_i) + P_2(x_i) + P_1(x_i) /9),

and so the coefficients that appear in this expansion in place of the M^3_ are the same as the coefficients in the expansion of the polynomial

    ∏_i = 1^k(x_i + 1)^3 - 3 ·∏_i = 1^k x_i (x_i + 1)^2  - 3 ·∏_i = 1^k x_i^2(x_i + 1  )  - ∏_i = 1^k x_i^3 - 3 ·∏_i = 1^k(x_i^3 + x_i^2 + x_i /3)   + 9 ·∏_i = 1^k(x_i^3 + x_i^2 + x_i /9) .






 §.§ Higher ranks



There are ten exceptional complex reflection groups of rank 4 or
larger, of which all but one (the rank-4 group G_31) are well
generated.  Of these, only G_32 has the property that the sequence
of Orlik–Solomon coexponents (b^X_i)_i is a function of the dimension of X alone <cit.>.  For this group, one sees from Table <ref> that the terms that one would predict (based on Theorems <ref> and <ref> and Proposition <ref>) survive, but that other terms are present as well (as for G_25 above).  Moreover, for the eight other relevant groups, one sees in each case that there is not enough cancellation to give a result in the form of those just mentioned.  Section <ref> offers some open questions in this direction.






§ APPLICATIONS



In this section, we discuss a number of corollaries of our results.
First, we show how to derive the result of Chapuy and Stump
(Theorem <ref>) for the groups G(d, 1, n) and G(d, d, n)
from Theorems <ref>
and <ref>.  In the case of G(d, 1, n),
this makes the proof fully elementary (that is, with no use of
representation theory); in the case of G(d, d, n), it reduces this
question to an elementary proof of a result in the symmetric group: 
Theorem <ref> (see Question <ref>).  

Second, we use our results to extract highest-degree coefficients.
These count the so-called genus 0 factorizations, or
equivalently they count chains in the lattice of G-noncrossing
  partitions.  For the group G(d, d, n), this includes a new
result, extending work of Athanasiadis–Reiner and Bessis–Corran
<cit.>.  As a corollary, we give a
variant characterization of the G-noncrossing partition lattice that
seems not to have appeared in the literature.




 §.§ Rederiving the Chapuy–Stump formula


Suppose that, for a well generated complex reflection group G, one
has computed (in some form) the generating functions F_G(x_1, …,
x_ℓ) = ∑_ a_· x_1^r_1⋯ x_ℓ^r_ℓ
for the number of factorizations of a Coxeter element in G by
fixed space dimension r_i for each of the factors.  From this series, it is straightforward to extract the number of length-ℓ reflection factorizations of a Coxeter element in G: it is exactly the coefficient [x_1^n - 1⋯ x_ℓ^n - 1]F_G.  In particular, suppose that the expression for F_G is in terms of a basis P_0, …, P_n of polynomials with (P_i) = i, so that

    F_G(x_1, …, x_ℓ) = ∑_ A_· P_p_1(x_1) ⋯ P_p_ℓ(x_ℓ),

and suppose that the degree-(n - 1) coefficients of P_n and P_n - 1 are a and b, respectively.  From general considerations (either the algebraic formula, or, that the Hurwitz action of the braid group provides explicit bijections), one has that the coefficient A_ depends only on the multiset of values of the p_i, not on their order.
Therefore, the number N_ℓ of length-ℓ reflection factorizations of c is

    N_ℓ = [x_1^n - 1⋯ x_ℓ^n - 1]F_G = ∑_k = 0^ℓℓk A_ n - 1, …, n - 1_ k,   n, …, n_ℓ - k a^ℓ - k b^k.

From this general framework, we now derive the main theorem of Chapuy
and Stump in many cases.

Suppose that G is G(d, 1, n) or is one of the irreducible well generated groups of rank 2 or 3, other than G_25; then by Theorem <ref>, Theorem <ref>, and Proposition <ref> we have that 

    A_  = |G|^ℓ - 1 M^n_,     
    a = -1/|G|∑ e^*_i = -|R^*|/|G|,      and     
     b  = 1/d_1 ⋯ d_n - 1 = h/|G|.

Moreover, from (<ref>) we have M^n_n, …, n = 0 and M^n_n - 1, …, n - 1, n, …, n
= ∑_j = 0^n - 1 (-1)^j nj (n - j)^k,
and so for these groups

    ∑_ℓ = 0^∞ N_ℓt^ℓ/ℓ!
    
    
        = 1/|G|∑_j = 0^n - 1 (-1)^j nj∑_ℓ = 0^∞t^ℓ/ℓ!∑_k = 1^ℓℓk  (n - j)^k (-|R^*|)^ℓ - k h^k
        = 1/|G|∑_j = 0^n - 1 (-1)^j nj∑_ℓ = 0^∞t^ℓ/ℓ!( ((n - j)h - |R^*|)^ℓ - (-|R^*|)^ℓ) 
        = 1/|G|∑_j = 0^n - 1 (-1)^j nj( exp(((n - j)h - |R^*|)t) - exp(-|R^*|t)) 
    
    
    
        = 1/|G|( exp((nh - |R^*|)t/n) - exp(- |R^*|t/n) )^n.

Finally, using the general fact that |R^*| +  |R| = nh, we recover
Theorem <ref> for these groups.  In particular, in the case of
G(d, 1, n), this gives a fully elementary proof of the
theorem.


In the case of G(d, d, n) for n > 3, the calculation in the preceding remark does not apply.  Nevertheless, since every reflection factorization of a Coxeter element in G(d, d, n) is transitive, it is possible to recover the Chapuy–Stump formula for this group from Theorem <ref>.  Following the notation above, we have for this polynomial that A_ = |G|^k - 1/n^k M^n_, a = -1/d^n - 1(n - 1)!∑ e^*_i =  - n|R^*|/|G|, and b = 1/d^n- 2(n - 2)! = n(n - 1)d/|G| = nh/|G|, and so the calculation goes through in the same way after the cancellation of the ns.  The resulting argument is elementary except for the proof of Theorem <ref> (see Question <ref>).





 §.§ Genus 0 factorizations: chains in the poset of noncrossing partitions


For any two linear transformations U, T on a finite-dimensional vector space V, one has (UT) ≤(U) + (T).  If G is a well generated complex reflection group of rank n and c is a Coxeter element in G, it follows that in order for there to be a factorization c = u_1 ⋯ u_k of c where u_i has fixed space dimension r_k, one must have (n - r_1) + … + (n - r_k) ≥ n, or equivalently r_1 + … + r_k ≤ n(k - 1).  Consequently, the polynomial F_G(x_1, …, x_k) counting factorizations of c is of degree n(k - 1), with top-degree coefficients counting factorizations u_1 ⋯ u_k = c such that (u_1) + … + (u_k) = (c) (= n).  Such factorizations are often said to have genus 0 – see Section <ref> for a discussion of this topological terminology.  They also arise in the context of the G-noncrossing partition lattice, which is the subject of the rest of this section.

A subadditive function on a group G such as[In particular,
  one needs that the function takes nonnegative values and that f(x)
  = 0 if and only if x is the identity.] (-) gives
rise to a partial order ≤ on G, as follows: one defines x ≤
y if (x) + (x^-1y) = (y).  With
this definition, one has that for each fixed g ∈ G, genus-0
factorizations u_1 ⋯ u_k of g are in bijection with (multi)chains 1 ≤ g_1 ≤…≤ g_k = g in the interval [1, g]_≤ via the map g_i := u_1 ⋯ u_i.  Thus, the top-degree coefficient a_r_1, …, r_k in F_G(x_1, …, x_k) also counts multichains in the interval [1, c]_≤ whose successive rank-jumps are n - r_1, …, n - r_k.  We now compute these numbers for G(d, 1, n) and G(d, d, n), as well as the zeta polynomial Z([1, c]_≤, k) that counts all multichains in [1, c]_≤ k of length k.  The result for G(d, 1, n) is known.

 
For d > 1, let G = G(d, 1, n), and let c be a Coxeter element in G.  Given nonnegative integers s_1, …, s_k with sum n, the number of chains in [1, c]_≤ having rank-jumps s_1, …, s_k is 

    a^(d)_n - s_1, …, n - s_k = ns_1⋯ns_k,

with zeta polynomial 

    Z([1, c]_≤, k) = nkn.



Set r_i := n - s_i for i = 1, …, k.  
Since M^n_p_1, …, p_k = 0 if p_1 + … + p_k > n(k - 1) and the change of basis in Theorem <ref> is triangular, the equation a^(d)_ = [x_1^r_1⋯ x_k^r_k] F_G =  [x_1^r_1⋯ x_k^r_k] (|G|^k - 1∑_ M^n_∏_i (x - 1)^(d)_r_i/d^r_i r_i!) simplifies to 

    a^(d)_ = |G|^k - 1 M^n_∏_i = 1^k 1/d^r_i r_i!.

 By Proposition <ref>, we have in this case that
 M^n_ = n!/(n - r_1)! ⋯ (n - r_k)!, and
 consequently a^(d)_ = nr_1⋯nr_k =
 ns_1⋯ns_k, as claimed.  Summing a^(d)_ over all nonnegative integer solutions to s_1 + … + s_k = n gives the zeta polynomial.


The second result, for G(d, d, n), is new when d > 2 (but see Remark <ref>); when d = 2 (type D_n), it is <cit.>.  



For d > 1, let G = G(d, d, n), and let c_(d, d, n) be a Coxeter element in G.  Given nonnegative integers s_1, …, s_k with sum n, the number of chains in [1, c_(d, d, n)]_≤ having rank-jumps s_1, …, s_k is 

    n - 1s_1⋯n - 1s_k(d + ∑_i = 1^k n - 2s_i - 2/n - 1s_i),

with zeta polynomial

    Z([1, c_(d, d, n)]_≤, k) = d(n - 1)kn + k (n - 1)k - 1n - 2 = n + d(n - 1)(k - 1)/n(n - 1)kn - 1.



Let r_i = n - s_i.  Since M^n_p_1, …, p_k = 0 if p_1 +
… + p_k > n(k - 1) and the change of basis is triangular, when we
extract the coefficient of x_1^r_1⋯ x_k^r_k from
Theorem <ref> and
  Proposition <ref> we get

    b^(d)_r_1,…,r_k    = |G|^k-1/n^k M^n_r_1,…,r_k1/d^r_1-1 (r_1-1)!⋯1/d^r_k-1 (r_k-1)!
        = d^(n - 1)(k - 1) (n!)^k - 1/n^k·n!/(n - r_1)! ⋯ (n - r_k)!·1/d^n(k - 1) - k· (r_1 - 1)! ⋯ (r_k - 1)!
        = d ·n - 1r_1 - 1⋯n - 1r_k - 1.


The analysis of the nontransitive case is slightly more delicate: by Lemma <ref>, we have that the desired coefficient is

    d^n(k - 1) + 1∑_S, T, U ⊆ [k]: 
     S ∩ T ≠∅
     S ∩ U = ∅ d^- |S ∪ T|·∏_i ∉S r_i · 
    C^⟨ n - 1 ⟩_ + _T - _U·1/d^r_1r_1! ⋯ d^r_kr_k!
    = 
    d/ r_1! ⋯ r_k!∑_S, T, U ⊆ [k]: 
     S ∩ T ≠∅
     S ∩ U = ∅ d^- |S ∪ T|·∏_i ∉S r_i · 
    ((n - 1)!)^k - 1· M^n - 2_ + _T - _U -  1.

The coefficient M^n - 2_ + _T - _U -  1 is equal to 0 whenever the sum of the lower indices is larger than (n - 2)(k - 1). This sum is 

    (∑ r_i) + |T| - |U| - k = n(k - 1) + |T| - |U| - k ≥ n(k - 1) + 1 - (n - 1) - k = (n - 2)(k - 1),

with equality if and only if S = T = {i} and U = [k]
∖{i} for some i ∈ [k].  In this case, by
  Proposition <ref> we have that the coefficient is M^n - 2_ + _T - _U -  1 = (n - 2)! · (n - r_i)!/(n - r_1)! ⋯ (n - r_k)! · (n - r_i - 2)!, and so the number of nontransitive genus-0 factorizations is

    d/ r_1! ⋯ r_k!∑_i = 1^k d^-1·∏_j ≠ i r_j · ((n - 1)!)^k - 1·(n - 2)! · (n - r_i)!/(n - r_1)! ⋯ (n - r_k)! · (n - r_i - 2)! =  
     = ((n - 1)!)^k/(r_1 - 1)! ⋯ (r_k - 1)! · (n - r_1)! ⋯ (n - r_k)! ∑_i = 1^k  (r_i - 1)! · (n - 2)! ·  (n - r_i)! /(n - 1)! · r_i! · (n - r_i - 2)! =  
     =  n - 1r_1 - 1⋯n - 1r_m - 1∑_i = 1^k n - 2r_i/n - 1r_i - 1.

Substituting r_i = n - s_i gives the first result, and summing over all (s_i) of sum n gives the zeta polynomial.




In the literature on the poset of noncrossing partitions, they are typically introduced in the following way (e.g., see <cit.> or <cit.>): in place of the function (-), one defines the reflection length (-) by (g) = min{k ∃ (t_1, …, t_k) ∈ R^k, t_1 ⋯ t_k = g}.  Reflection length is clearly subadditive, and one defines a partial order ≤_R on G by x ≤_R y if (x) + (x^-1y) = (y).  Then the lattice NC(G, c) of G-noncrossing partitions is defined to be the interval [1, c]_≤_R.  (All such intervals are isomorphic, for the same sort of reasons as discussed in Remark <ref>.)

For any element g of any subgroup G of (V) generated by reflections (not necessarily finite; over an arbitrary field), it is easy to see that (g) ≤(g).  If G is a finite real reflection group, Carter proved <cit.> that in fact (g) = (g), and consequently the two orders ≤ and ≤_R coincide in this case.  The same is true in the wreath product G(d, 1, n) <cit.>, and in a variety of other settings <cit.>.  However, equality does not hold in any other irreducible complex reflection group <cit.>.


In several places in the literature (e.g., in
<cit.>), one finds versions the following
deduction: from the inequality (g) ≥(g) for all g ∈ G, the equality (c) = (c), and the subadditivity of (-), it follows that if g ∈ NC(G, c) then (g) = (g) and so g ∈ [1, c]_≤, with the same rank.  However, we were unable to find the following question addressed in the literature: is there a complex reflection group G and an element g of G such that g ∈ [1, c]_≤ but g ∉NC(G, c)?

In <cit.>, Bessis and Corran prove that the
zeta polynomial for the lattice NC(G(d, d, n), c_(d, d, n)) is
equal to n + d(n - 1)(k - 1)/n∏_i = 1^n - 1i
  + (n - 1)(k - 1)/i = n + d(n - 1)(k - 1)/n(n-
  1)kn - 1; that is, it agrees with the zeta polynomial for the
interval [1, c_(d, d, n)]_≤ from Corollary <ref>.
In particular, taking k = 2, the two intervals have the same size,
and so in fact they must have the same set of elements.


This coincidence holds in a strong form for all well generated complex reflection groups.



If G is an irreducible well generated complex reflection group and c is a Coxeter element, then the interval [1, c]_≤ in the (-)-order ≤ is identical to the G-noncrossing partition lattice NC(G, c).


The situation in the case that G is real or is in the infinite families G(d, 1, n), G(d, d, n) for d > 1 is described in Remark <ref>.  For G of rank 2, the conditions 1 < g < c and 1 <_R g <_R c are both equivalent to the statement that g and g^-1c are reflections. For the remaining exceptional groups (G_24, G_25, G_26, G_27, G_29, G_32, G_33, G_34), we checked by a brute-force calculation in Sage <cit.> that the number of elements in [1, c]_≤ is the same as the G-Catalan number[The precise attribution of this equality is complicated.  Already in the real case, it was first handled independently in several cases – see <cit.> for a summary.  The proofs for G(d, 1, n) and G(d, d, n) may be found in <cit.> and <cit.>, and the proof for exceptional groups follows from <cit.>.]
|NC(G, c)| = ∏_i h + d_i/d_i.  (In the very large group
G_34, our computation make use of the fact that the interval [1,
c]_≤ has symmetric rank sizes: the map g ↦ g^-1c is easily seen to be a rank-reversing bijection from [1, c]_≤ to itself.)  Thus the underlying sets of the two intervals are equal.  Since (w) = (w) and (w^-1c) = (w^-1c) for every w ∈ NC(W, c), the two intervals are equal as posets.


There does not seem to be an obvious reason for the inclusion [1,
c]_≤⊆ NC(G, c) to hold.  Nevertheless, we are very
surprised not to find it remarked upon in the literature!  For open questions along these lines, see Section <ref>.






§ MORE REFINED COUNTING: CYCLE TYPE FOR G(D, 1, N)


In <cit.>, the Chapuy–Stump result (Theorem <ref>) was
refined as follows: rather than lumping all reflections together, they
were divided into classes according to the orbit of their fixed space
under the action of the group.  For example, in G(d, 1, n), this
separates the reflections into two classes: the transposition-like
reflections (which form a conjugacy class) and the diagonal reflections
(which are not all conjugate if d > 2, but whose fixed spaces
{ (x_1, …, x_n)  x_i = 0} form one orbit under the
action of the group).  This refinement makes perfect sense in our 
setting: one could ask to count arbitrary factorizations of a
Coxeter element, tracking the orbit of the fixed space of each factor.
In this section, we consider this question for the group G(d, 1, n), refining our main theorem (Theorem <ref>) in this case.


In the case of the symmetric group, fixed-space orbits correspond exactly to
cycle types (i.e., conjugacy classes). Beginning with the work <cit.> of Goulden–Jackson for the genus-0 case, 
numerous authors have tackled this problem, using a mix of algebraic and combinatorial
techniques, counting the factorizations directly
<cit.> or counting colored factorizations <cit.> (as in our approach).  
These works culminated in the following theorem of Bernardi–Morales, 
where the generating polynomial is
written in terms of the power sum p_λ and monomial symmetric
functions m_μ in k distinct sets of variables
_i=(y_1^(i),y_2^(i),…).
 
 

For λ^(1),…,λ^(k) partitions of n, let
a_λ^(1),…,λ^(k) be the number of k-tuples
(π_1,…,π_k) of elements in 𝔖_n such that
π_i has cycle type λ^(i) for i=1,…,k, and
π_1⋯π_k =.  We have

    ∑_λ^(1),…,λ^(k)
    a_λ^(1),…,λ^(k) p_λ^(1)(_1)⋯
    p_λ^(k)(_k) =
    (n!)^k-1∑_μ^(1),…,μ^(k)M^n-1_ℓ(μ^(1))-1,…,ℓ(μ^(k))-1/n-1ℓ(μ^(i)-1⋯n-1ℓ(μ^(k)-1 m_μ^(1)(_1)⋯
    m_μ^(k)(_k),

where both sums are over partitions of n.


In G = G(d, 1, n) for d > 1, two elements u and w have fixed spaces in the same G-orbit if and only if they have the same number of k-cycles of weight 0 for each k.  Thus, orbits of fixed spaces are indexed by the partition λ_0 of
Proposition <ref>. In this section, we
refine Theorem <ref> by keeping track of this partition
λ_0 for each of the factors in a factorization of a
Coxeter element. 

 
For d > 1, let G = G(d, 1, n), let c be a fixed Coxeter element
in G, and let a^(d)_λ^(1),…,λ^(k) be the
number of factorizations of c as a product of k elements of G
with weight-0 cycle type λ^(1),…,λ^(k),
respectively.  Then

    ∑_λ^(1),…,λ^(k) a_λ^(1),…,λ^(k)^(d)∏_i=1^k p_λ^(i)(1, y^(i)_1, …,
      y^(i)_1_d,  y^(i)_2, …, y^(i)_2_d,
    …)   = 
    
    =
    |G|^k-1∑_μ^(1),…,μ^(k)M^n-1_q_1-1,…,q_k-1/∏_i=1^k
      n-1q_i-1
    m_μ^(1)(_1)⋯ m_μ^(k)(_k),

where the sum on the RHS is over partitions μ^(i) of size at most n such that not all are of size n,
and q_j := ℓ(μ^(j))     if  |μ^(j)| = n 
ℓ(μ^(j))+1     otherwise.


The rest of this section is devoted to the proof of this result. 


 
Given compositions α^(1),…,α^(k) of n, let 𝒞^⟨ n⟩_α^(1),…,α^(k) be the    set of
factorizations in 𝔖_n of the fixed n-cycle  as a
product π_1⋯π_k such that for each i, the cycles of
π_i are colored with ℓ(α^(i)) colors and for j=1,…,ℓ(α^(i))
the sum of the lengths of the cycles colored with the jth color is
α^(i)_j. We say that such factorizations have type
α^(1),…,α^(k).  Let
C^⟨ n⟩_α^(1),…,α^(k) := |𝒞^⟨ n⟩_α^(1),…,α^(k)| be the number of colored
factorizations of type α^(1),…,α^(k). 



By relabelling colors, one has C^⟨
  n⟩_α^(1),…,α^(k) = C^⟨ n⟩_μ^(1),…,μ^(k) where μ^(i) is the
underlying partition of α^(i) for i=1,…,k.  Furthermore, one has C^⟨ n⟩_p_1,…,p_k =
∑_α^(i)
C^⟨ n⟩_α^(1),…,α^(k) where the sum is over
compositions α^(i) of n with p_i parts for
i=1,…,k  (see Remark <ref> about the
independence of choice of sets of colors).   As in Proposition <ref>, a
change of basis in the generating polynomial for a_λ^(1),…,λ^(k) may be interpreted in terms of the enumeration of
colored factorizations. 



With a_λ^(1),…,λ^(k) and
C^⟨ n⟩_μ^(1),…,μ^(k) as defined above, one
has

    ∑_λ^(1),…,λ^(k)
    a_λ^(1),…,λ^(k) p_λ^(1)(_1)⋯
    p_λ^(k)(_k)  = 
    ∑_μ^(1),…,μ^(k)
    C^⟨ n⟩_μ^(1),…, μ^(k) m_μ^(1)(_1) ⋯  m_μ^(k)(_k),

where the sums on both sides are over partitions of n.


The following corollary is an immediate consequence of Theorem <ref>
and Proposition <ref>. 

 
Given compositions α^(1),…,α^(k) of n, with p_i=ℓ(α^(i)) for
i=1,…,k, 
the number of colored factorizations of type 
α^(1),…,α^(k) of an n-cycle in 𝔖_n
 is 

    C^⟨ n⟩_α^(1),…,α^(k) = (n!)^k-1M^n-1_p_1-1,…,p_k-1/n-1p_1-1⋯n-1p_k-1.
 


In order to prove Theorem <ref>, we follow the same approach involving projections of cycle-colorings as in
Theorem <ref>. Given compositions
α^(1),…,α^(k) of size at most n with
p_i:=ℓ(α^(i)), let
𝒞^(d,1,n)_α^(1),…,α^(k) be the set of
colored factorizations in 𝒞^(d,1,n)_p_1,…,p_k
such that for i=1,…,k and j=1,…,p_i,   α^(i)_j is the sum of the lengths of the cycles colored with colors in the
strip {(j-1)d+1,…,jd}. Let
C_α^(1),…,α^(k)^(d,1,n) =
|𝒞_α^(1),…,α^(k)^(d,1,n)|. By permuting the colors we have that

    C_α^(1),…,α^(k)^(d,1,n)=C_μ^(1),…,μ^(k)^(d,1,n),

where μ^(i) is the underlying partition of the composition
α^(i) for i=1,…,k.
 
The first part of the proof of the theorem is a formula for
C^(d,1,n)_α in terms of the counts C^⟨ n⟩_γ of colored factorizations of the n-cycle in
𝔖_n reviewed above.

 
Fix compositions α^(1),…,α^(k) of size at most n. If |α^(i)| = n for all i = 1, …, k then C^(d,1,n)_α^(1),…,α^(k) = 0.  Otherwise, 
we have 

    C^(d,1,n)_α^(1),…,α^(k) = d^(k-1)n· C^⟨ n⟩_γ^(1),…,γ^(k),

where γ^(i) := α^(i)    if  |α^(i)| = n 
(n-|α^(i)|) ⊕α^(i)    otherwise, and ⊕ denotes concatenation.



Since c has nonzero weight, in any colored factorization c = u_1 ⋯ u_k there is some factor u_i of nonzero weight, and this factor has a cycle of nonzero weight.  Consequently, the composition α^(i) associated to this factor has size strictly less than n.  Therefore, given compositions α^(1),…,α^(k) with |α^(i)| = n for all i, the set 𝒞^(d,1,n)_α^(1),…,α^(k) is empty.  This completes the first part of the lemma.

Now suppose |α^(i)| < n for some i.  Given a colored factorization c = u_1 ⋯ u_k in 𝒞^(d,1,n)_α^(1),…,α^(k) of the Coxeter
element c for G(d, 1, n), we associate to it
a colored factorization = π_1 ⋯π_k of the n-cycle
 in _n with the same projection as in the proof of Lemma <ref>. Thus, in the resulting colored factorization of ,
the ith factor π_i is colored in either ℓ(α^(i)) or ℓ(α^(i))+1 colors depending on whether or not  π_i has a cycle
colored 0, with every color appearing. 
Moreover, for t=1,…,ℓ(α^(i)), the sum of the lengths of the cycles colored
t is α^(i)_t, and the sum of the
lengths of the cycles colored 0 is n-|α^(i)|. Therefore, the resulting colored factorization =
π_1 ⋯π_k is in
𝒞^⟨ n⟩_γ^(1),…,γ^(k) where
γ^(i) is as defined in the statement of the lemma.  

Second, we must consider how many preimages each factorization in
𝒞^⟨ n⟩_γ^(1),…,γ^(k) has under this
projection map. By the same
  argument as in Lemma <ref> the number of preimages is
  d^n(k-1).



Let u be an element of G(d,1,n) and consider a cycle of u of size m. The symmetric
function 

    p_m(1,  y_1, …, y_1_ d,
     y_2, …, y_2_ d, …) = d ·
    p_m(y_1,y_2,…) + 1
 
is the generating function for coloring such a cycle with color set _≥ 0, where the
exponent of the variable y_j records how many elements of [n] belong to a cycle that is colored from the jth d-strip {(j-1)d+1, …, jd}.
Thus the LHS of (<ref>) is the generating function of colored factorizations
c=u_1⋯ u_k of the Coxeter element c in which the cycles of
factor u_i are colored with the color set _≥ 0, where
the elements colored in the d-strip {(j-1)d+1,…,jd} are
encoded with the variable y^(i)_j. To count these
factorizations by the total number of elements in the cycles colored  in
each d-strip, we change basis to monomials (^(i))^α^(i), yielding

    ∑_λ^(1),…,λ^(k) a_λ^(1),…,λ^(k)^(d)∏_i=1^k p_λ^(i)(1, y^(i)_1, …,
      y^(i)_1_d,  y^(i)_2, …, y^(i)_2_d,
    …) =
    ∑_α^(1),…,α^(k)
    C^(d,1,n)_α^(1),…,α^(k) (^(1))^α^(1)⋯ (^(k))^α^(k),

where the sum on the right is over weak compositions α^(i) of numbers no larger than n.
By Lemma <ref> and Corollary <ref> we have that 

    C^(d,1,n)_α^(1),…,α^(k) = d^(k-1)n (n!)^k-1M^n-1_q_1-1,…,q_k-1/∏_i=1^k
      n-1q_i-1,

where q_i = ℓ(α^(i))     if  |α^(i)| =n
ℓ(α^(i))+1     otherwise for i=1,…,k. Finally, by (<ref>) we
can combine monomials (^(i))^α^(i)  with the same
underlying partition μ^(i) to rewrite the RHS in the basis
m_μ^(i), as desired. 



Theorem <ref> can be recovered from
Theorem <ref> as
follows. We do a
stable
principal specialization _i = 1^x_i for i=1,…,k (see
(<ref>)) in (<ref>). One has

    p_λ(1, y_1, …,
      y_1_d,  y_2, …, y_2_d,
    …)   |_ = 1^x   =   (xd+1)^ℓ(λ).

This gives 

    ∑_r_1,…,r_k(∑_λ^(i)ℓ(λ^(i))=r_i
      a^(d)_λ^(1),…,λ^(k))
    (x_1d+1)^r_1⋯ (x_kd+1)^r_k = 
    
    = |G|^k-1∑_p_1,…,p_kx_1p_1⋯x_kp_k∑_α^(i)ℓ(α^(i))=p_iM^n-1_q_1-1,…,q_k-1/n-1q_1-1⋯n-1q_k-1,

where the sum on the RHS is over compositions α^(i) of size at most
n with p_i parts, with not all compositions of size n. 
Grouping tuples of compositions according to the subset of indices i
with |α^(i)| < n, one counts the compositions in each case to
cancel the binomials, applies Proposition <ref>, and does a substitution (x_id+1) ↦ x_i to finish. 





 §.§ The genus-0 case


The leading terms in the LHS of the equation in Theorem <ref>, 
of degree ∑_i ℓ(λ^(i)) = n(k-1)+1,
count genus-0 factorizations for 𝔖_n by the cycle type of the factors. 
Goulden and Jackson <cit.> used Lagrange inversion to give a formula for such factorizations, called the cactus formula:

    a_μ^(1),…,μ^(k) =  n^k-1·∏_i=1^k 
    (ℓ(μ^(i))-1)!/(μ^(i)).

Krattenthaler and Müller <cit.> gave formulas counting genus-0 factorizations by cycle type for signed permutations (type B_n) and even-signed permutations (type D_n), also using Lagrange inversion. As an application of Theorem <ref>, we obtain a formula for the genus-0 factorizations for G=G(d,1,n) by their weight-0 cycle type that is independent of d and coincides with the type B_n formulas in <cit.>. Since ℓ(λ_0(w)) = (w), the genus-0 factorizations are those counted by a^(d)_λ^(1), …, λ^(k) such that ∑_i ℓ(λ^(i)) = n(k - 1). 

 
For d>1, let G=G(d,1,n), and let c be a Coxeter element in
G. Given partitions λ^(1),…,λ^(k) of size at most
n with ∑_i=1^k ℓ(λ^(i)) = n(k-1), we have that
a^(d)_λ is nonzero if and only if there is a unique j such that |λ^(j)| < n, and in this case 

    a^(d)_λ^(1),…,λ^(k) = n^k-1·ℓ(λ^(j)) ·∏_i=1^k 
    (ℓ(λ^(i))-1)!/(λ^(i)).




Let F denote the generating function in (<ref>) and let ⟨· ,·⟩ denote the
usual Hall inner product of symmetric functions, for which 
⟨ p_λ, p_μ⟩ = δ_λμ z_λ. Fix a tuple of partitions (λ^(i)) with ∑_i=1^k
ℓ(λ^(i)) = n(k-1).  On one hand, thinking about the LHS
formula for F in (<ref>), we have

    a^(d)_λ^(1),…,λ^(k) = ⟨∏_i p_λ^(i)(_i)/d^ℓ(λ^(i)) z_λ^(i), F⟩,

since the top-degree term of p_λ(1, y_1, …, y_1, y_2, …, y_2, …) is d^ℓ(λ) p_λ(_i).
On the other hand, thinking about the RHS formula for
F in (<ref>), we have that

    ⟨∏_i p_λ^(i)(_i), F⟩ = |G|^k-1∑_μ^(1),…,μ^(k)M^n-1_q_1-1,…,q_k-1/∏_i=1^k
      n-1q_i-1∏⟨ p_λ^(i)(_i), m_μ^(i)(_i)⟩.

In order for ⟨ p_λ^(i), m_μ^(i)⟩ not to be zero, we must have that μ^(i) is a refinement of λ^(i), and so in particular ℓ(μ^(i)) ≥ℓ(λ^(i)) for each i.  It follows that, in order for a term to contribute, it must be the case that

    ∑_i (q_i - 1)     = ∑_i ℓ(μ^(i)) - #{i  |μ^(i)| = n}
       ≥∑_i ℓ(λ^(i)) - #{i  |μ^(i)| = n}
        = n(k - 1) - #{i  |μ^(i)| = n}
       ≥ (n - 1)(k - 1),

where in the penultimate step we use the fact that no terms appear on the RHS with all μs of size n.  On the other hand, in order for M^n - 1_q_1 - 1, …, q_k - 1 to be nonzero, it must be the case that ∑ (q_i - 1) ≤ (n - 1)(k - 1).  Thus, the (μ^(i)) term on the right contributes if and only if μ^(i) = λ^(i) for all i and also exactly k - 1 of the λ^(i) have size n.  That is, if there is any nonzero contribution at all, it comes from the single term when μ^(i) = λ^(i) for all i, and in this case we have

    ⟨∏_i p_λ^(i)(_i), F⟩    = |G|^k-1M^n-1_q_1-1,…,q_k-1/∏_i=1^k
      n-1q_i-1∏_i=1^k ⟨ p_λ^(i), m_λ^(i)⟩
        = |G|^k - 1n - 1n - q_1; … ; n - q_k/∏_i=1^k
      n-1q_i-1∏_i=1^k z_λ^(i)/(λ^(i))

and therefore

    a^(d)_λ^(1),…,λ^(k)  =  |G|^k - 1/d^∑ℓ(λ^(i))n - 1n - q_1; … ; n - q_k/∏_i=1^k
      n-1q_i-1∏_i=1^k 1/(λ^(i))
    =
    n^k - 1∏_i=1^k (q_i-1)!/(λ^(i)),

and the result follows immediately.










§ REMARKS AND OPEN PROBLEMS






 §.§ A uniform formula?



In light of the beautiful Chapuy–Stump formula (Theorem <ref>), the main question raised by our work is the following one. 


Is there a uniform answer that incorporates the various formulas that appear in Theorems <ref> and <ref> and Proposition <ref>?


As mentioned in Remark <ref> and
Section <ref>, one obstruction is that
for the cases not covered by these theorems (and in particular,
for G(d, d, n) when n > 3), there are more than one set of
Orlik–Solomon coexponents, and so there is no obvious choice of basis
in which to write the factorization polynomial.  


Our work on G(d, d,
n) suggests another approach towards a uniform statement, namely
studying factorizations with a transitivity condition. This leads to the
next question.



Can one give a definition of transitive factorization, valid for all well generated complex reflection groups, generalizing the definition for G(d, d, n) of Section <ref>?


One would hope that such a definition would yield a uniform generalization of Theorem <ref> and the aforementioned results.  

Another approach might start with the work of Douvropoulos <cit.>.  He uses a natural grouping on the irreducible characters of an arbitrary well generated complex reflection group to give an elegant, uniform proof of the Chapuy–Stump formula, as well as a weighted generalization.  The grouping exhibits cancellation similar to what we observe in the proof of Theorem <ref>.





 §.§ Maps and constellations


In the symmetric group, combinatorial proofs of the formulas
counting factorizations of the long cycle into two or more factors are phrased in terms of maps or constellations, that is, certain graphs embedded in surfaces (e.g., see <cit.>).
We briefly discuss two possible variants of maps for encoding
factorizations of a Coxeter element into two factors of the complex reflection group G(d,1,n). 

The first version of maps is to encode the underlying factorization in the
symmetric group with the usual rooted unicellular bipartite map
<cit.> <cit.> <cit.> and add the
cyclic group weights on the edges, as follows.
Given a factorization u· v of the Coxeter element c in G(d,1,n), we assign to this factorization a map, with the following conventions (see Figure <ref>):


  * the map has n edges labelled 1,2,…,n;

  * each cycle of u corresponds to a black vertex and each cycle of v corresponds to a white vertex;

  * the labels of the edges incident to a black vertex are the entries in the corresponding cycle of u, and appear in clockwise order around the vertex; 
and similarly for white vertices and v; and

  * the edge labelled i has additional labels corresponding to the weight of the ith column of u and ith row of v.

The fact that u· v = c means that if we start at the rooted black vertex
and traverse the map, recording the labels on the edges when we go from a black to a white vertex, then we see the edges in the order 1, 2, …, n given by the long cycle . 





Let u=[(1532)(4); (1, 2,2,0,1)] and v=[(134)(25); (1, 2,0,2, 2)] be the following elements in G(3,1,5):

    u = [     z^2            ;         z^2    ;                   z;               1    ;   z                 ],    
    v = [             z^2    ;             z^2;   z                ;           1        ;     z^2             ],    u· v = [         z; 1        ;   1      ;     1    ;       1   ] = c.
 
The corresponding weighted map is shown in Figure <ref>.



In the case of genus-0 factorizations with two factors, there are known
combinatorial objects that correspond to the factors: in _n,
the number of elements that can appear in a
genus-0 factorization of the long cycle  is the Catalan number C_n, and they are in natural correspondence with noncrossing partitions on n points.  In G(d, 1, n) for d > 1, there are 2nn (the type B Catalan number) elements that can appear in a genus-0 factorization of the Coxeter element c, and they are in natural correspondence with noncrossing partitions on dn points having d-fold rotational symmetry <cit.> – see Figure <ref>.

Thus, one might hope that the map objects corresponding to
factorizations in G(d, 1, n) should also have a d-fold symmetry.
This gives rise to a second version of maps on surfaces, in which one
“unfolds” a weighted map into an object with d copies of each vertex and edge, where an edge of weight m that connected vertices A and B unfolds to edges connecting copies A_i and B_i + m (with indices in /d) – see Figure <ref>.

Unfortunately, neither map correspondence seems completely
satisfactory: the topological genus of the map is controlled by the total number of cycles in the factors, rather than the number of weight-0 cycles. (For example, in the first variant, the genus of the map is exactly the genus of the underlying factorization in _n.)  Is there a better correspondence between factorizations in G(d, 1, n) and some kind of maps?  



 §.§ Better combinatorial proofs in the symmetric group?


Our work suggests (at least) two natural questions purely in the context of the symmetric group.  The first concerns the (n - 1)-cycle.


Can one give a combinatorial proof of Theorem <ref>, counting transitive factorizations of an (n -
1)-cycle in _n into k factors? 


For example, one might try to explain why 
n^k-1 (n-1)^k C^⟨ n-1,1⟩_ p  = p_1⋯ p_k C^⟨ n ⟩_ p+1. 
We are able to give a combinatorial proof for the case of k=2
factors. However, it does not seem to extend easily to general
k. We state this proof in terms of permutations but it could equivalently
be phrased in terms of maps using a contraction of a digon.





We give an (n - 1)-to-1 map from transitive factorizations of a fixed (n - 1)-cycle in _n to factorizations of a fixed (n - 1)-cycle in _n - 1.

Without loss of generality, let = (1 ⋯ (n - 1))(n).  Thus for any factorization u · v = in _n, we have v(n) = u^-1(n) =: t.  This factorization is transitive if and only if the common value t belongs to [n - 1], and equivalently the value n belongs to a cycle of length longer than 1 in both u and v.  Then u' := u · (t  n) and v' := (t  n) · v are the permutations that result from deleting n from its cycle in u and v, respectively; we view them as permutations in _n - 1 (rather than as permutations in _n that fix n).  Moreover, u' and v' have the same number of cycles as u and v, respectively.

On the other hand, for any factorization u' · v' = (1 ⋯ (n - 1)) in _n - 1 and any t ∈ [n - 1], we may think of u' and v' as elements of _n that fix n; then u := u' · (t  n) and v := (t   n) · v' are two permutations in _n such that u · v = is a transitive factorization, and u and v have the same number of cycles as u' and v', respectively.

It follows that the number b_r, s of transitive factorizations of  using factors with r and s cycles is equal to n - 1 times the number a^(n - 1)_r, s of factorizations of an (n - 1)-cycle in _n - 1 using factors with r and s cycles.  By Theorem <ref>, one has

    ∑_r, s b_r, s x^r y^s     = (n - 1) ·∑_r, s a^(n - 1)_r, s x^r y^s 
        = (n - 1) · (n - 1)! ·∑_p,qn-2p-1; q-1; n - p - q(x)_p/p!(y)_q/q!
        = n!/n^2·∑_p, qnp; q; n - p - q(x)_p/(p - 1)!(y)_q/(q - 1)!.

When k = 2, M^n_p, q = np; q; n - p - q, and so this completes the proof.




The correspondence used in the proof also behaves well with colored factorizations with k = 2 factors.

The existing combinatorial proofs of Theorem <ref> in the
case of k factors use involved arguments with
maps or constellations (as in Section <ref>), the BEST theorem, the matrix-tree theorem, and
sign-reversing involutions; see <cit.>. The second question concerns the possibility of “nicer” combinatorial proofs for the n-cycle.  

Proposition <ref> and Corollary <ref> imply the recurrence relation

    C^⟨ n ⟩_p_1,…,p_k = n^k-1∑_S ⊊ [k] C^⟨ n-1⟩_-_S

for counts of colored factorizations of long cycles.  Is there a
direct combinatorial proof of this relation, perhaps in terms of
Bernardi's  tree-rooted maps (see <cit.>)?






 §.§ More refined counting: tracking cycles by weights


While tracking the number of cycles of weight 0 is natural from the
geometric perspective, from the combinatorial point of view it makes
just as much sense to ask for the full distribution of cycle weights.
Building on the work of Chapuy–Stump <cit.>,
we were able to prove the
following result using the character-theory approach.
In contrast to the rest of the paper, the statement of this result does depends on the weight of the Coxeter element chosen.


For d > 1, let G = G(d, 1, n) and let c be a Coxeter element in
G of weight 1.  For i = 1, …, k, let _i = (r_i, 0,
…, r_i, d - 1) be a tuple of nonnegative integers, and let
a^(d)__1, …, _k be the number of factorizations c =
u_1 ⋯ u_k of c as a product of k factors such that u_i has
exactly r_i, j cycles of weight j for each j = 0, …, d -
1.  Let _i denote the variable set {x_i, 0, …, x_i, d
  - 1}.  Then
 
    ∑__1, …, _k a^(d)__1, …, _k_1^_1⋯_k^_k
    =
    |G|^k - 1∑_t^d = 1∑_ M^n - 1_p_1 - 1, …, p_k - 1∏_i (x_i, 0 + t x_i, 1 + … + t^d - 1 x_i, d - 1)/dp_i.
 


By setting x_i, 0 = x_i and x_i, j = 1 for j = 1, …, d - 1, one immediately recovers on the LHS the polynomial of Theorem <ref>; to make the RHS match requires a computation using Proposition <ref>. 



The RHS in Theorem <ref> is, up to the power of d, the result of substituting x_i ↦ (x_i, 0 + t x_i, 1 + … + t^d - 1 x_i, d - 1)/d into the RHS of (<ref>), then extracting powers of t modulo t^d - 1.  This raises the question of whether the same substitution has combinatorial meaning when factoring other elements.  Unfortunately, the answer seems to be negative: the factorization polynomial for the identity into two factors in _2 is x^2y^2 + xy, and substituting x = (x_0 + t x_1)/2 and y = (y_0 + ty_1)/2 and summing over t = ±1 yields 

    x_0^2y_0^2 + x_1^2 y_0^2 + x_0^2y_1^2 + x_1^2y_1^2 + 4x_0x_1y_0y_1 + 4x_0y_0 + 4x_1y_1/8,

with fractional coefficients.  
For comparison, the polynomials counting two-factor factorizations of diagonal matrices in the signed permutation group G(2, 1, 2) are



x_0^2y_0^2 + 2x_0x_1y_0y_1 + x_1^2y_1^2 + 2x_0y_0 + 2x_1y_1        (the identity), 

x_0^2y_0y_1 + x_0x_1y_0^2 + x_0x_1y_1^2 + x_1^2y_0y_1 + 2x_0y_1 + 2x_1y_0        (the two reflections), and 

x_0^2y_1^2 + 2x_0x_1y_0y_1 + x_1^2y_0^2 + 2x_0y_0 + 2x_1y_1        (the negative of the identity).
 
 





Is there a better expression for the polynomial that appears in Theorem <ref>, for example, in terms of a natural basis of polynomials?  Does it have a combinatorial proof?











 §.§ Refinement by fixed space orbit


As discussed in Section <ref>, the cycle type result there makes sense for any complex reflection group G, where one refines by the G-orbit of fixed space of the factors.  


Does Theorem <ref> generalize?  What about its genus-0 special case?

A natural test-case would be transitive
factorizations of a Coxeter element in G(d,d,n), refining
Theorem <ref>.  The first obvious obstruction to be overcome is the choice of a “good” basis of polynomials in which to express the generating function. 



 §.§ Intervals in two posets



It would be desirable to have a uniform proof of Corollary <ref>, that the G-noncrossing partition lattice may be equivalently defined as an interval when G is ordered by the reflection-length order ≤_R or the codim-fix order ≤, even though the larger posets are not the same.

In light of Corollary <ref>, it is natural to ask under what conditions the interval [1, w]_≤ in the codim-fix order is equal to the interval [1, w]_≤_R in the reflection-length order; for example, does equality always hold when (w) = (w)?  The next example shows that the answer to this question is negative.

In G(7, 7, 6), consider the elements w = [123456; (1, 2, 3, 4, 5, 6)], u = [123456; (1, 2, 0, 4, 0, 0)] and v = [123456; (0, 0, 3, 0, 5, 6)].  It is easy to check that w = u · v, (w) = (w) = 6, (u) = (v) = 3, and (u) = (v) = 4.  Thus u, v belong to the interval [1, w]_≤ but not to the interval [1, w]_≤_R.


Can one characterize the elements w for which [1, w]_≤ = [1, w]_≤_R?  In particular, does equality hold for all regular elements w?





 §.§ Generating function by reflection length?

One possibility, suggested by Remark <ref>, is that instead of writing a generating function for factorizations using fixed space dimension, one should write a generating function that records the reflection length (g) of the factors.  However, there is again an obstruction in terms of choosing a basis: typically in these groups there are elements of reflection length > n, so basis polynomials of degree > n would be required, and it is not clear what would be a good choice of such polynomials.



alpha








§ TABLES OF CHARACTER POLYNOMIALS



In this section, we collect tables of the character polynomials f_χ(x) := ∑_w ∈ W(w) x^(w) for the exceptional complex reflection groups.  These were computed on CoCalc using Sage <cit.> and GAP <cit.>.  We show only the characters χ such that χ(c^-1) ≠ 0 where c is a fixed Coxeter element.  One feature common to all groups is the appearance of the degrees with the trivial character

    f_triv(x) = ∑_w ∈ W x^ w = ∏ (x - 1 + d_i)

and the coexponents with the determinant character

    f_det(x) = ∑_w ∈ W(w) x^ w = ∏ (x - e^*_i)

(in the real cases, the sign character) – cf. Section <ref>.



 §.§ Rank two






















There are twelve well generated exceptional groups of rank 2.  The tables below give the coexponents (e^*_1, e^*_2), the degrees (d_1, d_2), and, for each character χ such that χ(c^-1) ≠ 0, the dimension (χ) = χ(1), the character value χ(c^-1), and the character polynomial f_χ, expressed in the basis

    P_2 = (x - e^*_1)(x - e^*_2)/d_1 · d_2,      P_1 = x - 1/d_1,      P_0 = 1.

In the first two tables, two groups appear in each table; for the subsequent (larger) groups, each group appears in its own table, possibly in several columns.







margin=.5in
































 §.§ Rank three


For the five exceptional groups of rank 3, all of which are well generated, we give for each character χ such that χ(c^-1) ≠ 0 the character polynomial f_χ expressed in the given basis (see Section <ref>).














 §.§ Higher ranks

We give the relevant character polynomials.  Except in G_32, we do not reexpress them in a different basis.  





























