Polynomiality of factorizations in reflection groups

Many recent results in the literature have begun to uncover the structure inherent to factorizations in complex reflection groups [BGJ08, CS14, Mic16, dHR18, Dou18, LM19]. In much of the existing literature, the authors fix an element of a complex reflection group and compute an explicit formula for the generating series of all factorizations of that element. The formulas that have been found are quite compelling, especially the uniform formula discovered by Chapuy and Stump for factoring Coxeter elements in well-generated complex reflection groups [CS14], generalizing a result of Jackson that computes all factorizations of a long cycle in a symmetric group [Jac88].

The polynomial structure presented in this paper is somewhat orthogonal to the previous results. In particular, the previous results in the work cited above studied formulas for a fixed $\omega$ and varying $m$, which is equivalent to fixing $\ell$ while varying $g$. The polynomial structure, on the other hand, only arises when we fix $g$ and $\ell$ and we vary $\omega$, not just in a single group, but throughout all $G(r,s,n)$ with $n\geq\ell$.

Another distinction between this work and the previous papers is that most of the previous results use Burnside’s character formula to study factorization numbers. Since our focus is on connected factorizations, these techniques are less immediately applicable.

While the polynomials in this paper are not given by explicit formulas, they provide a very general structural understanding of factorization numbers for complex reflection groups. Most of the previous results with explicit formulas study factorization numbers of Coxeter elements in well-generated complex reflection groups (Douvropoulos also extended these formulas to regular elements [Dou18]). In the family $G(r,s,n)$, the only well-generated groups are those for which $s=1$ or $s=r$, and the Coxeter elements are very special, generalizing the long cycle in the case of $S_{n}$. Polynomiality, on the other hand, reveals a structure inherent to the collection of all factorization numbers for all groups $G(r,s,n)$.

However, if one requires explicit formulas for factoring specific elements in $G(r,s,n)$, then the methods of this paper are also useful. In particular, Corollary 3.5 provides an explicit comparison between the factorization series of $\omega\in G(r,s,n)$ and that of $\pi(\omega)\in S_{n}$. As an example application, we use the known formula for calculating factorizations of long cycles in $S_{n}$ to write a generating series for factoring long cycles in $G(r,s,n)$ (Corollary 3.6).

Section 2 collects information about complex reflection groups and various types of factorizations. We begin in 2.1 with a review of complex reflection groups, describing in detail the groups $G(r,s,n)$ that are of primary interest in this work. In 2.2, we define the particular factorization numbers $f_{m}^{\omega}$ that we study, along with a refinement $f_{m_{1},m_{2}}^{\omega}$ that will be important. In 2.3, we introduce a useful graph-theoretic interpretation of these factorizations. We close Section 2 with a discussion of connected factorization numbers $\widetilde{f}_{m}^{\omega}$ and $\widetilde{f}_{m_{1},m_{2}}^{\omega}$, and we describe how to recover all factorizations from the connected ones.

Section 3 contains the main results of this paper. These results all follow from Theorem 3.1, which compares factorization numbers for $\omega\in G(r,s,n)$ with those of $\pi(\omega)\in S_{n}$. More specifically, Theorem 3.1 expresses $\widetilde{f}_{m}^{\omega}$ as a linear combination of the numbers $\widetilde{f}_{m^{\prime}}^{\pi(\omega)}$ with $m^{\prime}\leq m$. From this comparison result and the polynomiality implied by the ELSV formula, it then follows that the factorization numbers $\widetilde{f}_{m}^{\omega}$ are determined by polynomials. That the bounds on the degree work out so nicely was a pleasant surprise, and is a result of the specific structure of the comparison in Theorem 3.1. We close Section 3 by providing an explicit comparison between factorization series of $\omega\in G(r,s,n)$ and $\pi(\omega)\in S_{n}$, and we use this to compute a formula for the factorization series of long cycles in $G(r,s,n)$.

The authors are grateful to Stanza Coffee on 16th Street in San Francisco for providing a pleasant environment in which to ponder polynomiality, and they are especially indebted to Luis for pouring the tastiest espressos that fueled their progress.

The second named author learned about the results of [CS14] at the Workshop on Moduli Spaces, Integrable Systems, and Topological Recursions hosted by the Université de Montréal in January 2016; he thanks the organizers for the invitation to participate and Guillaume Chapuy for his talk on the results of [CS14], which initiated this investigation.

This work was partially supported by the National Science Foundation (RUI DMS-2001439).

Let $V$ be a finite-dimensional complex vector space. A linear transformation $\rho\in\mathrm{GL(V)}$ is said to be a reflection of V if it has finite order and if the fixed-point set

$$\{\mathrm{\mathbf{v}}\in V\;|\;\rho(\mathrm{\mathbf{v}})=\mathrm{\mathbf{v}}\}$$

is a complex hyperplane in $V$. A complex reflection group is a finite subgroup $G\subset\mathrm{GL}(V)$ that is generated by reflections.

The data of a complex reflection group is more than just an abstract group; the complex vector space $V$ and an embedding in $\mathrm{GL}(V)$ must also be specified. As opposed to reflections of real vector spaces, reflections of complex vector spaces do not necessarily have order two. A simple example of a complex reflection with order greater than two is multiplication by a primitive $r$th root of unity, with $r>0$, viewed as an element of $\mathrm{GL}(\mathbb{C})$.

The next example provides a general description of all of the reflections that will be considered in this paper and establishes notation that will be used throughout.

The previous example provides us with a wealth of complex reflections. The next two examples describe the complex reflection groups that can be generated by sets of these reflections. We begin with the most classical example: the symmetric group.

The class of complex reflection groups that are of primary interest in this work are a natural generalization of the symmetric group. They are described in the following example.

Irreducible complex reflection groups were classified by Shephard and Todd in [ST54]. In addition to the infinite family $G(r,s,n)$ described in Example 2.3, Shephard and Todd described a list of 34 exceptional groups, and they showed that every complex reflection group can be decomposed uniquely as a product, each factor of which is either $G(r,s,n)$ for some $(r,s,n)$ or one of the exceptional groups. As the only infinite family in the classification, the groups of the form $G(r,s,n)$ play an especially important role in the theory of complex reflection groups.

There are two natural group homomorphisms between complex reflection groups that are important. The first is the homomorphism

$$\pi:G(r,s,n)\rightarrow S_{n}$$

that replaces every nonzero entry in a matrix $\omega\in G(r,s,n)$ with $1$. The second is the homomorphism

$$\phi:G(r,s,n)\rightarrow\mu_{r/s}$$

that computes the product of all of the nonzero entries in a matrix $\omega\in G(r,s,n)$. The function $\delta$ appearing in the statement of polynomiality is related to the homomorphism $\phi$; it is defined by

	$\displaystyle\delta:G(r,s,n)$	$\displaystyle\rightarrow\{0,1\}$
	$\displaystyle\omega$	$\displaystyle\mapsto\begin{cases}1&\text{ if }\phi(\omega)=1,\\ 0&\text{ if }\phi(\omega)\neq 1.\end{cases}$

Given an element $\omega\in G(r,s,n)$, our goal is to study the number of ways it can be factored into reflections. More precisely, define the factorization set $F^{\omega}_{m}\subseteq R^{m}$ to be the set of ways to write $\omega$ as a product of $m$ reflections:

$$F^{\omega}_{m}:=\left\{(\rho_{1},\dots,\rho_{m})\in R^{m}\;|\;\rho_{m}\cdots\rho_{1}=\omega\right\}.$$

We are interested in the size of this factorization set:

$$f^{\omega}_{m}:=|F^{\omega}_{m}|.$$

Notice that the notation $(r,s,n)$ has been omitted from these definitions because it is encoded by the element $\omega$, which is always understood to be an element of some $G(r,s,n)$.

Given a factorization

$$\rho_{m}\cdots\rho_{1}=\omega\in G(r,s,n),$$

we obtain an identity in $S_{n}$ by applying the homomorphism $\pi$:

$$\pi(\rho_{m})\cdots\pi(\rho_{1})=\pi(\omega)\in S_{n}.$$

However, $\left(\pi(\rho_{1}),\dots,\pi(\rho_{m})\right)$ is not necessarily an element of $F^{\pi(\omega)}_{m}$, because $\pi(\rho_{j})$ will be the identity whenever $\rho_{j}\in R_{2}$. Thus, if we want to compare factorizations in $G(r,s,n)$ with factorizations in $S_{n}$, it makes sense to refine the factorizations by the number of factors that belong to $R_{1}$ and $R_{2}$.

For an element $\omega\in G(r,s,n)$ and nonnegative integers $m_{1}$ and $m_{2}$ such that $m=m_{1}+m_{2}$, define the refined factorization set as

$$F^{\omega}_{m_{1},m_{2}}:=\left\{(\rho_{1},\dots,\rho_{m})\in R^{m}\;\Big{|}\;{\rho_{m}\cdots\rho_{1}=\omega\atop|\{i\;|\;\rho_{i}\in R_{j}\}|=m_{j}}\right\}\subseteq F_{m}^{\omega},$$

and define

$$f^{\omega}_{m_{1},m_{2}}:=|F^{\omega}_{m_{1},m_{2}}|.$$

Notice that

$$f^{\omega}_{m}=\sum_{m_{1}+m_{2}=m}f_{m_{1},m_{2}}^{\omega}.$$

Applying the homomorphism $\pi$ to each factor then defines a function from the factorization set $F^{\omega}_{m_{1},m_{2}}$ to the factorization set $F^{\pi(\omega)}_{m_{1}}$, which, by a slight abuse of notation, we also denote by $\pi$:

(2.2)

$$\pi:F^{\omega}_{m_{1},m_{2}}\rightarrow F^{\pi(\omega)}_{m_{1}}.$$

In order to compare the number of factorizations of $\omega\in G(r,s,n)$ to the number of factorizations of $\pi(\omega)\in S_{n}$, it suffices to understand the preimages of the function in (2.2).

To assist in our study of the factorization sets introduced in the previous subsection, we introduce a combinatorial interpretation of those sets in terms of decorated graphs, and we prove several results concerning these graphs that will be useful in Section 3.

For our purposes, a graph on the vertex set $V=[n]=\{1,\dots,n\}$ consists of an ordered set of edges $E=(e_{1},\dots,e_{m})$ where each edge $e\in E$ is a multiset of order two: $e=\{i,j\}$ with $i,j\in[n]$. For clarity, it’s worth noting that

• •

  the set of edges is ordered, and

• •

  self-edges and multiple edges are allowed.

We often require subsets of edges to preserve the ordering, and we write $E^{\prime}\preceq E$ to denote a subset of edges with the induced ordering. The ordered set of edges containing two distinct vertices is denoted $E_{1}\preceq E$ and the ordered set of self-edges is denoted $E_{2}\preceq E$.

The graphs that encode factorizations in $G(r,s,n)$ have an additional edge labeling. In particular, we decorate each edge $e\in E$ by an integer $\mathrm{k}(e)$ that satisfies the following constraints:

$$\begin{cases}0\leq\mathrm{k}(e)<r&\text{ if }e\in E_{1},\\ 0<\mathrm{k}(e)<r/s&\text{ if }e\in E_{2}.\end{cases}$$

We define $\Gamma_{m}(r,s,n)$ to be the set of graphs with $m$ ordered edges on the vertex set $[n]$ along with an edge labeling as above. If $r=s$, then $E_{2}=\emptyset$, because self-edges are impossible to label under the above constraints. Let $\Gamma_{m_{1},m_{2}}(r,s,n)\subseteq\Gamma_{m}(r,s,n)$ denote the subset of graphs such that $|E_{1}|=m_{1}$ and $|E_{2}|=m_{2}$.

The reason we have introduced decorated graphs is because each graph in $\Gamma_{m}(r,s,n)$ corresponds to an $m$-tuple of reflections $(\rho_{1},\dots,\rho_{m})\in R^{m}\subseteq G(r,s,n)^{m}$ in a natural way. Specifically, for each edge $e\in E$, we associate a reflection $\rho\in R$ via the rule

(2.3)

$$\rho=\begin{cases}\sigma_{ij}^{\mathrm{k}(e)/r}&\text{ if }e=\{i,j\}\in E_{1}\text{ with }i<j,\\ \tau_{i}^{s\mathrm{k}(e)/r}&\text{ if }e=\{i,i\}\in E_{2}.\end{cases}$$

Conversely, given an $m$-tuple of reflections $(\rho_{1},\dots,\rho_{m})\in R^{m}\subseteq G(r,s,n)^{m}$, we associate a decorated graph in $\Gamma_{m}(r,s,n)$ with edges and edge labels specified by

(2.4)

$$(e,\mathrm{k}(e))=\begin{cases}\left(\{i,j\},k\right)&\text{ if }\rho=\sigma_{ij}^{k/r}\in R_{1},\\ \left(\{i,i\},k\right)&\text{ if }\rho=\tau_{i}^{sk/r}\in R_{2}.\end{cases}$$

The identifications in (2.3) and (2.4) are inverse to each other, and we henceforth use them to identify the set of graphs in $\Gamma_{m}(r,s,n)$ with the set of $m$-tuples of reflections in $G(r,s,n)$:

(2.5)

$$\Gamma_{m}(r,s,n)=R^{m}\subseteq G(r,s,n)^{m}.$$

The subset $\Gamma_{m_{1},m_{2}}(r,s,n)\subseteq\Gamma_{m}(r,s,n)=R^{m}$ corresponds to those $m$-tuples of reflections where $m_{1}$ of the reflections belong to $R_{1}$ and $m_{2}$ of the reflections belong to $R_{2}$.

Given a graph $\gamma\in\Gamma_{m}(r,s,n)$, let $\omega$ be the product of the corresponding $m$-tuple of reflections: $\omega=\rho_{m}\cdots\rho_{1}$. Then, by definition, $(\rho_{1},\dots,\rho_{m})\in F^{\omega}_{m}$. For each $\omega\in G(r,s,n)$, let $\Gamma^{\omega}_{m}\subseteq\Gamma_{m}(r,s,n)$ and $\Gamma^{\omega}_{m_{1},m_{2}}\subseteq\Gamma_{m_{1},m_{2}}(r,s,n)$ denote the subsets of graphs whose corresponding reflections multiply to $\omega$. By definition, the identification (2.5) induces an identification of these subsets with the appropriate factorization sets:

	$\displaystyle\Gamma_{m}(r,s,n)=$	$\displaystyle\;R^{m}$
	$\displaystyle\Gamma^{\omega}_{m}\;\;\;=\;\;$	$\displaystyle\;F_{m}^{\omega}$
	$\displaystyle\Gamma^{\omega}_{m_{1},m_{2}}\;=\;\;$	$\displaystyle\;F_{m_{1},m_{2}}^{\omega}.$

Our next goal is to better understand the subsets $\Gamma_{m}^{\omega}\subseteq\Gamma_{m}(r,s,n)$. In particular, given a graph in $\Gamma_{m}(r,s,n)$, we know that it belongs to $\Gamma_{m}^{\omega}$ for some $\omega$, and we would like to be able to describe $\omega$ in terms of the graph. For this, we turn to a discussion of ordered edge walks.

Let $\gamma\in\Gamma_{m}(r,s,n)$ be a graph with edge set $E=(e_{1},\dots,e_{m})$. A directed edge $\vec{e}=(i_{0},i_{1})$ consists of an edge $e=\{i_{0},i_{1}\}\in E$ along with a choice of ordering of the two vertices. Notice that every edge in $E_{1}$ has two possible directions, while edges in $E_{2}$ have only one possible direction. Given a directed edge $\vec{e}=(i_{0},i_{1})$, we denote the head and tail by $\mathrm{h}(\vec{e})=i_{1}$ and $\mathrm{t}(\vec{e})=i_{0}$, respectively. A walk in $\gamma$ is a set of directed edges $w=(\vec{s}_{1},\dots,\vec{s}_{\ell})$ such that $\mathrm{h}(\vec{s}_{j})=\mathrm{t}(\vec{s}_{j+1})$ for $j=1,\dots,\ell-1$. A step of the walk refers to a single directed edge $\vec{s}_{j}$. The start and end of the walk refer to $\mathrm{t}(\vec{s}_{1})$ and $\mathrm{h}(\vec{s}_{\ell})$, respectively. We use the following notation to denote walks:

$$w=(i_{0}\stackrel{{\scriptstyle s_{1}}}{{\longrightarrow}}i_{1}\stackrel{{\scriptstyle s_{2}}}{{\longrightarrow}}\cdots\stackrel{{\scriptstyle s_{\ell}}}{{\longrightarrow}}i_{\ell}),$$

where $\mathrm{h}(\vec{s}_{j})=i_{j}$ and $\mathrm{t}(\vec{s}_{j})=i_{j-1}$ for all $j=1,\dots,\ell$. We say that a walk is ordered if the order of the steps is consistent with the ordering of edges: $(s_{1},\dots,s_{\ell})\preceq E$.

Given a graph $\gamma\in\Gamma_{m}(r,s,n)$ and a vertex $i\in[n]$, there is a natural ordered walk $w_{i}=w_{i}(\gamma)$ that starts at vertex $i$ and sequentially walks along the edges $e_{1},e_{2},\dots,e_{m}$. More specifically, starting at vertex $i=i_{0}$, let $s_{1}=\{i_{0},i_{1}\}$ be the first edge in $E$ that contains $i_{0}$, and define $\vec{s}_{1}=(i_{0},i_{1})$. Next, let $s_{2}=\{i_{1},i_{2}\}$ be the first edge in $E$ that occurs after $s_{1}$ and contains $i_{1}$, and define $\vec{s}_{1}=(i_{1},i_{2})$. Continue in this way until, for some $i_{\ell}$, there does not exist an edge in $E$ that occurs after $s_{\ell}$ and contains $i_{\ell}$. When this happens, stop the recursion, and define

$$w_{i}(\gamma)=(i_{0}\stackrel{{\scriptstyle s_{1}}}{{\longrightarrow}}i_{1}\stackrel{{\scriptstyle s_{2}}}{{\longrightarrow}}\cdots\stackrel{{\scriptstyle s_{\ell}}}{{\longrightarrow}}i_{\ell}).$$

If $i$ is not contained in any edges, then $w_{i}$ is the trivial walk that starts and ends at $i$ and does not have any steps.

The next result is a useful observation about these ordered edge walks. It can be checked explicitly in Example 2.6.

So far, the ordered walks $w_{i}$ only take into account the ordering of the edges, but not the labels. We now take into consideration the edge labels. We define the weight of a directed edge by

$$\mathrm{k}(\vec{e})=\begin{cases}\mathrm{k}(e)&\text{ if }\mathrm{h}(\vec{e})>\mathrm{t}(\vec{e}),\\ s\mathrm{k}(e)&\text{ if }\mathrm{h}(\vec{e})=\mathrm{t}(\vec{e}),\\ -\mathrm{k}(e)&\text{ if }\mathrm{h}(\vec{e})<\mathrm{t}(\vec{e}),\end{cases}$$

where the three cases are referred to as up-steps, loops, and down-steps, respectively. The weight of a walk $w=(\vec{s}_{1},\dots,\vec{s}_{\ell})$ is defined by

$$\mathrm{k}(w)=\sum_{j=1}^{\ell}\mathrm{k}(\vec{s}_{j}).$$

Given the above definitions, we are now ready to characterize those graphs in $\Gamma_{m}(r,s,n)$ that correspond to factorizations of $\omega\in G(r,s,n)$. This is the content of the next result.

Before proving the proposition, we return one last time to our running example.

Our main results in Section 3 are stated in terms of connected factorizations. In this subsection, we introduce connected factorizations and describe how they generalize the transitive factorizations in $S_{n}$. We also prove that every factorization number can be computed from the connected factorization numbers.