%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2021}
\articlenumber{66}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage{latexsym,verbatim,multirow,graphicx,epsfig,enumerate,
  paralist,xypic,hyperref,float}
\usepackage{subcaption}
\captionsetup[subfigure]{labelfont=rm}
\usepackage{xcolor}
\usepackage[normalem]{ulem}
\usepackage{tikz}
\usepackage{bm}
\usepackage{epigraph}
%\usepackage[pagebackref]{hyperref}


\usepackage{comment}


\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{corollary}[theorem]{Corollary}

\theoremstyle{definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{definition}[theorem]{Definition}
 \newtheorem{question}[theorem]{Question}
% \newtheorem{convention}{Convention}
% \newtheorem*{main}{Main Question}




\newcommand{\op}[1]{\operatorname{#1}}

\newcommand\xx{{\mathbf{x}}}
\newcommand\yy{{\mathbf{y}}}
\newcommand\pp{{\mathbf{p}}}
\newcommand\rr{{\mathbf{r}}}
\newcommand\ee{{\mathbf{e}}}


\newcommand{\boldt}{{\bf t}}
\newcommand{\boldalpha}{{\boldsymbol{\alpha}}}
\newcommand{\boldbeta}{{\boldsymbol{\beta}}}
\newcommand\abs{\operatorname{abs}}
\newcommand\mult{\operatorname{mult}}
\newcommand\defining{\operatorname{def}}
\newcommand\rad{\operatorname{rad}}
\newcommand\corad{\operatorname{corad}}
\newcommand\rank{\operatorname{rank}}
\newcommand\codim{\operatorname{codim}}
\newcommand\one{\mathbf{1}}
\newcommand\Sym{\operatorname{Sym}}
\newcommand\Hom{\operatorname{Hom}}
\newcommand\Cat{\operatorname{Cat}}
\newcommand\Hilb{\operatorname{Hilb}}
\newcommand\Conj{\operatorname{Conj}}
\newcommand\Ind{\operatorname{Ind}}
\newcommand\Par{\operatorname{Par}}
\newcommand\Frac{\operatorname{Frac}}
\newcommand\Irr{\operatorname{Irr}}
\newcommand\Aut{\operatorname{Aut}}
\newcommand\Tr{\operatorname{Tr}}
\newcommand\wt{\operatorname{wt}}
\newcommand\fix{\operatorname{fix}}
\newcommand\maj{\operatorname{maj}}
\newcommand\sgn{\operatorname{sgn}}
\newcommand\normchi{\widetilde{\chi}}
\newcommand\Class{\operatorname{Cl}}
\newcommand\Nref{\operatorname{N^{\operatorname{ref}}}}
\newcommand\Nhyp{\operatorname{N^{\operatorname{hyp}}}}
\newcommand\hcprod{{*}}
\newcommand\rk{\operatorname{rk}}
%\newcommand\hcprod{{\circ}}
\newcommand{\ibar}{\bar\imath}
\newcommand{\jbar}{\bar\jmath}
\newcommand\Span{\operatorname{span}}
\newcommand{\diag}{\operatorname{diag}}
\newcommand{\occ}{\operatorname{occ}}
\newcommand{\vol}{\operatorname{Vol}}

%\newcommand{\defn}[1]{\textbf{#1}}
\newcommand{\defn}[1]{\textit{{#1}}}
\newcommand{\type}[1]{\mathrm{#1}}
%\newcommand{\B}{\mathcal{B}}

\newcommand\OOO{{\mathcal{O}}}

\newcommand\CCC{{\mathcal{C}}}
\newcommand\ccc{{\mathcal{c}}}

\newcommand\llambda{{\vec{\lambda}}}

\newcommand\CC{{\mathbb{C}}}
\newcommand\ZZ{{\mathbb{Z}}}
\newcommand\NN{{\mathbb{N}}}
\newcommand\QQ{{\mathbb{Q}}}
\newcommand\RR{{\mathbb{R}}}
\newcommand\FF{{\mathbb{F}}}
\newcommand\Gr{{\mathbb{G}}}
\newcommand\GL{{\mathrm{GL}}}

\newcommand{\cn}{\varsigma}
\newcommand{\cnn}{\varsigma_{(n - 1, 1)}}

\newcommand{\poly}[3]{P_{#1}^{(#2)}(#3)}

\newcommand{\Nar}{N}
\newcommand{\z}{\zeta}
\newcommand{\lR}{\ell_{R}}
\newcommand{\ltr}{\ell_R^{\textrm{tr}}}

\newcommand{\id}{\mathrm{id}}

\newcommand\Symm{\mathfrak{S}}
\newcommand{\Ftr}{F^\textrm{tr}}
\newcommand{\Fred}{F^{\textrm{red}}}


\newcommand{\jbl}[1]{{\bf \color{red} \# #1 \# }}

\newcommand{\ahm}[1]{{\bf \color{blue} \# #1 \# }}

\newcommand{\theo}[1]{{\bf \color{olive} \# #1 \#}}


\usepackage{lipsum}


%% define your title in the usual way
%\title[Optional shorter title]{Something to do with math}
\title{Hurwitz numbers for reflection groups}


%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{
Theo Douvropoulos\thanks{\href{mailto: 	
douvropoulos@math.umass.edu}{douvropoulos@math.umass.edu}. TD was partially supported by the European Research Council, grant ERC-2016-STG 716083 ``CombiTop''.}\addressmark{1}, 
Joel Brewster
Lewis\thanks{\href{mailto:jblewis@gwu.edu}{jblewis@gwu.edu}.  JBL was partially supported by an ORAU Powe Award, a Simons Collaboration Grant (634530), and the GWU UFF.}\addressmark{2}, 
\and
Alejandro H.\ Morales\thanks{\href{mailto:ahmorales@math.umass.edu}{ahmorales@math.umass.edu}. AHM was partially supported by a NSF grant (DMS-1855536).}\addressmark{1}
}



%\author[Optional shorter names]{Longer names me\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}\addressmark{1}, \and you\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics and Statistics, University of Massachussets, Amherst, MA, USA \\ \addressmark{2}Department of Mathematics, George Washington University, Washington, DC, USA}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We give formulas for the number of transitive reflection
  factorizations of a parabolic quasi-Coxeter element in a Weyl group or complex
  reflection group,  generalizing the Hurwitz formulas for the symmetric group.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{transitive factorizations, quasi-Coxeter elements, Weyl groups}




%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{66Douvropoulos.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above


%TODO 9/29
%- flesh out intro
%- flesh out background
%- proof exceptional cases of Theorem 3.3. (Theo)
%- finish proof of Theorem 3.3 reflection groups


\section{Introduction}

In the late 19th century, Hurwitz (an early disciple of Riemann surface theory) was the first to recognize that the structure of Riemann surfaces with finitely many branch points is intrinsically combinatorial.  In particular, he showed in \cite{Hurwitz} that they are determined via (classes of) factorizations of the identity in the symmetric group $\mathfrak{S}_n$. 
In the same work \cite[\S~7]{Hurwitz}, he gave a complete analysis for
the case of genus-$0$ surfaces with all but one branch points being
simple. In combinatorial terms, these correspond to minimum-length
\emph{transitive} factorizations $\tau_1\cdots \tau_k=\sigma$ of a given element
$\sigma$ in $\mathfrak{S}_n$ in transpositions $\tau_i$, with transitivity
referring to the natural action of the group $\langle
\tau_i\rangle_{i=1}^k$ on the set $[n]:=\{1,\dots,n\}$. If $\lambda=(\lambda_1,\cdots,\lambda_c)$ is the cycle structure of $\sigma$, in which case it is easy to see that $k=n+c-2$, Hurwitz's celebrated formula for the number $H_0(\lambda)$ of such factorizations  has a beautiful product structure
\begin{equation}
H_0(\lambda)=(n+c-2)!\cdot n^{c-3}\cdot \prod_{i=1}^c\dfrac{\lambda_i^{\lambda_i}}{(\lambda_i-1)!}.
\label{EQ: Hurwitz formula}
\end{equation} 
In particular, for factorizations of the identity, this
gives $H_0(1^n)=(2n-2)!\cdot n^{n-3}$. These {\em (single) Hurwitz numbers of genus
  $0$} also count certain 
connected planar graphs embedded in the sphere ({\em planar maps}; see, e.g., \cite{LZ}).


In the 1980s, work of Stanley \cite{St80} and Jackson \cite{J88}
rekindled the interest in the enumeration of factorizations in
$\mathfrak{S}_n$ even if, at the time, they were unaware of the
topological context. In a different vein, the next few decades saw the emergence of Coxeter combinatorics; one of its main breakthroughs was the realization that theorems about $\mathfrak{S}_n$ are often shadows of more general results that hold for all reflection groups $W$. In our context of factorizations, this means replacing transpositions with reflections $\tau_i\in W$.


The intersection of these two areas has witnessed a lot of research activity recently
\cite{CC,D2,LM}, especially for factorizations of Coxeter elements $c\in W$, generalizing the long cycle case $\lambda=(n)$. In general, however, analogs of \eqref{EQ: Hurwitz formula} have been hard to find, not least because it is unclear how to define transitivity in reflection groups. In $\mathfrak{S}_n$, transitivity corresponds to the connectedness of the map or Riemann surface, both of which have no analogs for $W$. 

An equivalent way to interpret this notion of transitivity is to require that the factorization cannot be realized in any \emph{proper} Young subgroup of $\Symm_n$. This approach is valid for arbitrary reflection groups $W$, where we will thus say that $\tau_1\cdots \tau_k=g$ is a {\color{blue} \emph{transitive reflection factorization}} of an element $g\in W$, if the $\tau_i$ are reflections and they generate the whole group $W$. We are particularly interested in the ``genus-$0$" case, where the number $k$ of terms is minimum for the element $g$. We call this number $k$ the {\color{blue} \emph{transitive reflection length}} of $g$ and denote it by $\ltr(g)$ (leaving the symbol $\lR(g)$ to stand  for the usual reflection length of $g$, which does not require transitivity of the factorization). We write $\Ftr_W(g)$ for the number of such \emph{minimum length} transitive reflection factorizations of $g$.

In this work we establish (essentially) uniform formulas for these counts $\Ftr_W(g)$,  which then might be called {\color{blue} \emph{$W$-Hurwitz numbers}}. They generalize the previously mentioned Hurwitz formulas to any Weyl group $W$ (see also \S~\ref{Sec: complex case} for the complex case) and any parabolic quasi-Coxeter element $g\in W$ (this is a wide class of elements which for example contains all  $g\in \mathfrak{S}_n$). Partial results for the ``higher genus'' case appear in \S~\ref{Sec: Higher genus}.

There are many combinatorial approaches to the proof and
interpretation of the Hurwitz formulas (e.g., \cite{B-MS,GJ99b}). In
particular, Duchi--Poulalhon--Schaeffer \cites{DPS_II} give a
bijective proof where the term $n^{c-3}$ in \eqref{EQ: Hurwitz formula} roughly counts certain trees on the $c$-many cycles of $g\in\mathfrak{S}_n$. Our main Theorem~\ref{thm:main} indicates that something similar happens for all reflection groups $W$. Those trees are replaced by the collection $RGS(W)$ of (length-$n$) {\color{blue}\emph{reflection generating sets}} of $W$, and a relative version $RGS(W,g)$ (see \S~\ref{sec: background}). For the special case that $g=\op{id}\in W$, Thm.~\ref{thm:main} for instance implies the formula
\begin{equation}
\Ftr_W(id)=(2n)!\cdot |RGS(W)|\cdot\dfrac{1}{I(W)},
\label{EQ: F_W(id)}
\end{equation} 
where $n=\rank(W)$ and $I(W)$ is the connection index of the Weyl group $W$. Indeed, for $\mathfrak{S}_n$, the collection $RGS(\mathfrak{S}_n)$ corresponds precisely to the $n^{n-2}$ trees on $[n]$ and since $I(\mathfrak{S}_n)=n$, this gives a direct generalization of the Hurwitz number $H_0(1^n)$ of \eqref{EQ: Hurwitz formula}. 

Among elements $g\in W$, the parabolic quasi-Coxeter ones have a unique decomposition $g=g_1\cdot g_2\cdots g_m$ that generalizes the cycle-type decomposition of permutations and where each $g_i$ is a quasi-Coxeter element of some irreducible parabolic subgroup of $W$ (see \S~\ref{sec: background}). We write $\Fred(g_i)$ for the number
of \emph{reduced} (i.e., of minimum length, and thereby not transitive unless $\ell_R(g_i)=n$)
reflection factorizations of $g_i$. These quantities are analogs of
the numbers $\lambda_i^{\lambda_i-2}$ in $\mathfrak{S}_n$ and are
described in \S~\ref{sec: background}; they are all given by product formulas. With these notations, our main theorem is as follows. 
\begin{theorem}\label{thm:main}
For a Weyl group $W$, and any parabolic quasi-Coxeter element $g\in W$
with decomposition $g=g_1\cdot g_2\cdots g_m$, the number $\Ftr_W(g)$
of minimum-length transitive reflection factorizations of $g$ is given by the formula  
\begin{equation}
\Ftr_W(g)=\ltr(g)!\cdot
|RGS(W,g)|\cdot\dfrac{I(W_g)}{I(W)}\cdot\prod_{i=1}^m\dfrac{\Fred(g_i)}{\ell_R(g_i)!}
\, ,
\label{EQ: F_W(g)}
\end{equation}
where $\ltr(g)$ is the transitive reflection length of $g$, $W_g$ is the smallest parabolic subgroup containing $g$, and $I(W)$ and $\Fred(g_i)$ are as above.
\end{theorem}

The result for reducible groups follows easily from the
case of irreducible groups that we prove in Section~\ref{sec:main
  results}. In Section~\ref{Sec: complex case} we generalize
(conjecturally unless $g=\id$) Theorem~\ref{thm:main} to all
well-generated complex reflection groups. The appearance of the quantity $|RGS(W,g)|$ in the formula \eqref{EQ: F_W(g)} seems
very reasonable, but it cannot be explained on a purely naive basis.
In particular, the number of subsets of the terms in a minimum-length
transitive reflection factorization of $g$ that belong to $RGS(W,g)$
is not constant, already in $\Symm_n$ and for the identity $g= \id$.  


%For example, take the two factorizations 
%\[
%(12)(12)(23)(23)=\id\qquad\text{ and }\qquad (12)(23)(13)(23)=\id.
%\] 
%The first one has four subsets with two elements that generate the whole group and two that don't, while the second one has five subsets that generate $\Symm_3$ and only one that doesn't.
%This makes it more complicated to find some sort of overcounting
%argument to explain why the number of generating sets appears in the
%formula.  
%Is there one even just for $\Symm_n$?

%\acknowledgements{We thank Gilles Schaeffer for
%suggesting we look at transitive factorizations of the identity in
%complex reflection groups.}

\section{Quasi-Coxeter elements and reflection generating sets} \label{sec: background}

%In this abstract, we present Thm.~\ref{thm:main} in the level of generality of {\color{blue} \emph{Weyl groups}} (even though it can be extended to a more general case, see \S~\ref{Sec: complex case}). These are finite subgroups $W$ of $\op{GL}(\RR^n)$, generated by euclidean reflections, that further admit a $W$-equivariant, essential, {\color{blue} \emph{root lattice}} $\mathcal{Q}$. They have been classified in three infinite families $A_n,B_n,D_n$, and five exceptional groups $E_6,E_7,E_8,F_4$, and $G_2$ (see the classical reference \cite{Kane}). 
%
%Weyl groups $W$ have an assortment of related objects; in particular, a crustallographic root system $\Phi$ with set of simple roots $\Delta:=\{\alpha_i\}_{i=1}^n$, and a bilinear form $(\cdot,\cdot)$. They have an associated coroot lattice $\check{\mathcal{Q}}$ comprised of the coroots $\check{\alpha}:=2\alpha/(\alpha,\alpha)$ for each root $\alpha\in \mathcal{Q}$, and a weight lattice $\mathcal{P}$ defined as the dual lattice to $\check{\mathcal{Q}}$. There is an inclusion $\mathcal{Q}\subset \mathcal{P}$ and the index $I(W):=[\mathcal{P}:\mathcal{Q}]$ is an important invariant of $W$, known as its {\color{blue} \emph{connection index}}; it agrees with the determinant of the Cartan matrix $\big[(\alpha_i,\check{\alpha_j})\big]_{i,j}$ :

In this abstract, we present Thm.\ \ref{thm:main} in the level of generality of {\color{blue} \emph{Weyl groups}} (even though it can be further extended, see \S~\ref{Sec: complex case}). These are finite subgroups $W$ of $\op{GL}(\RR^n)$, generated by euclidean reflections, that further admit the $W$-equivariant, essential, \emph{root lattice} $\mathcal{Q}$ and \emph{coroot lattice} $\check{\mathcal{Q}}$ (see the classical reference \cite{Kane}). They have an assortment of related objects; in particular, roots $\alpha\in \mathcal{Q}$ and coroots $\check{\alpha}\in\check{\mathcal{Q}}$, and a weight lattice $\mathcal{P}$ defined as the dual lattice to $\check{\mathcal{Q}}$. There is an inclusion $\mathcal{Q}\subset \mathcal{P}$ and the index $I(W):=[\mathcal{P}:\mathcal{Q}]$ is an important invariant of $W$, known as its {\color{blue} \emph{connection index}}; it agrees with the determinant of the Cartan matrix $\big[(\alpha_i,\check{\alpha_j})\big]_{i,j}$ for a set of simple roots $\{\alpha_i\}$. Weyl groups are classified in three infinite families $\Symm_{n+1}=A_n,B_n,D_n$, where $n$ is the \emph{rank} of the group, and five exceptional cases $E_6,E_7,E_8,F_4$, and $G_2$. The corresponding connection indices are $n+1,2,4$ for the infinite families and $3,2,1,1,1$ for the exceptional groups.

%
%\begin{table}[h!]
%  \begin{center}
%    \label{tab:table1}
%    \begin{tabular}{l||c|c|c|c|c|c|c|c}
%      $W$ & $\Symm_n$ & $B_n/C_n$ & $D_n$ & $E_6$ & $E_7$ & $E_8$ & $F_4$ & $G_2$  \\
%      \hline
%      $I(W)$ & $n$ & $2$ & $4$ & $3$ & $2$ & $1$ & $1$ & $1$ \\
%    \end{tabular}
%   \caption{Connection indices for crystallographic Weyl groups $W$.}
%  \end{center}
%\end{table}

Our main Theorem~\ref{thm:main} extends the Hurwitz formulas
\eqref{EQ: Hurwitz formula} to the collection of parabolic
quasi-Coxeter classes in Weyl groups $W$. To define those, recall
first that a \emph{standard} parabolic subgroup $W_I$ of $W$ is any
subgroup generated by a subset $\{s_i\}_{i\in I}$ of the simple
generators of $W$ and that any subgroup conjugate to some $W_I$ is
simply called a \emph{parabolic subgroup} of $W$. An element $g\in W$
is then called {\color{blue}\emph{parabolic quasi-Coxeter}} if it has
a minimum-length reflection factorization $g=t_1\cdots t_{\ell_R(g)}$
whose terms $\{t_i\}$ generate a parabolic subgroup of $W$, and it is
called {\color{blue} \emph{quasi-Coxeter}} if they generate all of
$W$. To justify the name, notice that Coxeter elements (products of
the simple generators $\{s_i\}$ in any order, and their conjugates)
are always quasi-Coxeter. Similarly, parabolic Coxeter elements are
parabolic quasi-Coxeter. To see finally that Theorem~\ref{thm:main} fully generalizes the Hurwitz formulas, notice that in $\Symm_n$ all reflection subgroups are parabolic, therefore all elements are parabolic quasi-Coxeter elements.

Quasi-Coxeter elements were introduced by Voigt \cite{Voigt} and
rediscovered and generalized to the parabolic case by Baumeister et
al. \cite{BGRW}. Both works considered the Hurwitz action on reduced
(i.e., minimum-length) reflection factorizations of elements $g\in W$
and showed that it is transitive if and only if $g$ is parabolic
quasi-Coxeter. The sizes of these Hurwitz orbits, equivalently the
numbers $\Fred(g)$ of reduced reflection factorizations of $g$, were
computed by Kluitmann and Voigt \cite{KV}, independently by Stump
(private communication); below we give them only for the infinite
families. It was observed that they all factor as products of small
primes and a uniform formula for them has been proposed by the first
author \cite{theo_qCox}. In the groups $\mathfrak{S}_n$ and $B_n$ the
only quasi-Coxeter classes are the Coxeter ones, but in $D_n$ we have
$\lfloor \frac{n}{2}\rfloor$ classes denoted by $D_{k,n-k}$ which
contain Coxeter elements of the $B_k\times B_{n-k}$ reflection
subgroups of $B_n$ (viewing $D_n$ as a subgroup of $B_n$).

\begin{table}[h!]
  \begin{center}
    \begin{tabular}{l||c|c|c}
      $g$ & $\Symm_n$ & $B_n$ & $D_{k,n-k}$ \\
      \hline
      $\Fred(g)$ & $n^{n-2}$ & $n^n$ & $\displaystyle 2\cdot (n-1)\cdot\binom{n-2}{k-1}\cdot k^k\cdot (n-k)^{n-k}$ \\
    \end{tabular}
   \caption{Enumeration of reduced reflection factorizations for quasi-Coxeter elements.}
       \label{tab:table1}
  \end{center}
\end{table}


For any element $g$ of $W$, we write $W_g$ for its \emph{parabolic closure}, i.e., the smallest parabolic subgroup that contains it. The group $W_g$ can be written as a product $W_g=W_1\times\cdots \times W_m$ of irreducible components. Gobet \cite{gobet} defined a generalization of the cycle-decomposition of permutations and showed that parabolic quasi-Coxeter elements have a unique such decomposition $g=g_1\cdot g_2\cdots g_m$ where each $g_i$ is quasi-Coxeter for $W_i$. The number $\Fred(g)$  of reduced reflection factorizations of $g$ will be a product of the $\Fred(g_i)$ and a multinomial coefficient, thus also a product of small primes.

For a Weyl group $W$ of rank $n$, we will call any set of $n$
reflections that generate $W$, a {\color{blue} \emph{reflection generating set}} of $W$ and we will write $RGS(W)$ for the collection of such sets. Every reduced reflection factorization of a parabolic quasi-Coxeter element $g$ can be minimally extended to a reflection generating set of $W$ \cite[Prop.~6.2]{BGRW}, which then allows for a relative version of this notion. For each such $g$, we define the collection $RGS(W,g)$ of {\color{blue} \emph{relative reflection generating sets}} for $g$ as ($\mathcal{R}$ stands for the set of reflections of $W$)
\begin{equation}
\label{EQ: Defn of RGS(W,g): B}
RGS(W,g):=\Big\{ S\subset \mathcal{R} \colon |S|=n-\lR(g) \text{ such that } \langle S,T_g\rangle=W\Big\},
\end{equation}
where $T_g$ is any set of reflections that make up a reduced reflection factorization of $g$.



\subsubsection*{Genus-$1$ Hurwitz numbers}

Formula~\eqref{EQ: Hurwitz formula} is for the {\em (single) Hurwitz numbers of genus
  $0$}. In general, the genus-$g$ Hurwitz numbers $H_g(\lambda)$ count 
transitive factorizations $\tau_1\cdots \tau_k$ of a given
element $\sigma$ in $\mathfrak{S}_n$ of cycle type $\lambda$ into $k=n+c+2g-2$
transpositions $\tau_i$. In addition to the product formula for
$H_0(\lambda)$, the genus-$1$ numbers $H_1(\lambda)$ have a
closed formula that we will use in the proof of our main
theorem. Let $e_i$ denote the $i$th elementary symmetric function.

\begin{lemma}[Goulden-Jackson \cite{GJ99}]
\label{GJVGJV}
  For $\lambda=(\lambda_1,\ldots,\lambda_c)$,
  \[
H_1(\lambda) = \frac{1}{24} (n+c)! \left(\prod_{i=1}^c
  \frac{\lambda_i^{\lambda_i}}{(\lambda_i-1)!}\right) \left( n^c -
  n^{c-1}  - \sum_{i=2}^c (i-2)!n^{c-i}  e_i(\lambda) \right).
\]
In particular $H_1(1^n) = \frac{1}{24} (2n)! (n^n - n^{n-1} -
\sum_{i=2}^n \binom{n}{i} (i-2)! n^{n-i})$. 
 \end{lemma}






\section{Main results}
\label{sec:main results}


In order to enumerate minimum-length reflection factorizations, it is necessary first to understand the length at which these factorizations occur.  Our first result gives a formula for the transitive reflection length of parabolic quasi-Coxeter elements. 

\begin{proposition}\label{Prop: l^tr(w)=2n-lr(w)}
Suppose that $w$ is a parabolic quasi-Coxeter element in a Weyl group $W$ of rank $n$.  Then the transitive reflection length of $w$ is given by the formula
\[
\ltr(w) = 2n - \lR(w) = n + \dim \fix(w).
\]
\end{proposition}
\begin{proof}
Fix any element $w$ of a Weyl group $W$ and any transitive reflection factorization of $w$ of minimum length, and let $\ell = \ell_R(w)$ be the reflection length of $w$.  We have by \cite[Cor.~1.4]{LR} that there is another transitive factorization 
 \begin{equation}
\label{EQ: LR for w}
w=r_1\cdots r_\ell\cdot r_{\ell+1}\cdot r_{\ell+1}^{-1}\cdots r_{\ell+k}\cdot r_{\ell+k}^{-1}
\end{equation}
of the same length $\ltr(w) = \ell + 2k$.  The factors $r_1,\cdots,r_{\ell+k}$ in this second factorization must also generate $W$, so $\ell+k\geq n$. Therefore
\[
\ltr(w)=\ell+2k=2(\ell+k)-\ell\geq 2n - \lR(w).
\]
On the other hand, since $w$ is parabolic quasi-Coxeter, we have by \cite[Prop.~6.2]{BGRW} that there is some length-$\ell$ reflection factorization $w = r_1 \cdots r_\ell$ of $w$ that can be extended to a length-$n$ factorization $w' = r_1 \cdots r_\ell \cdot r_{\ell + 1} \cdots r_n$ of some element $w'$ in which the factors generate the group $W$.  Then $w =   r_1 \cdots r_\ell \cdot r_{\ell + 1}  \cdot r_{\ell + 1}^{-1}  \cdots r_n \cdot r_n^{-1}$ is a reflection factorization of $w$ of length $\ell + 2(n - \ell) = 2n - \lR(w)$ whose factors generate $W$, and consequently $\ltr(w) \leq 2n - \lR(w)$.
\end{proof}

%\begin{remark}
%The proof of \cite[Cor.~1.4]{LR}, used above, is not uniform.  If $w$ is a parabolic Coxeter element, then by choosing in its conjugacy class a representative $w'$ such that $\ell_S(w') = \lR(w')$, we can replace this result with \cite[Lem.~2.3]{WY}, which does have a uniform proof. \theo{We can kill this remark for space}
%\end{remark}



%In this section we define the objects that appear in the formula of
%our main theorem.


%\jbl{Will these already be defined in the introduction???}

%\theo{It is easy to see that \eqref{EQ: Defn of RGS(W,g): A} $\Rightarrow$ \eqref{EQ: Defn of RGS(W,g): B}, but the opposite direction is not yet clear. It probably needs something like ``all reduced reflection factorizations of some \emph{parabolic quasi-Coxeter} $g\in W$ are realizable in $W_{V^g}$", which I think appears in the literature only for real $W$.} 

%In the symmetric group, \eqref{EQ: Defn of RGS(W,g): A} agrees exactly with the notion of transitivity, so we could instead just say that the set $S\cup \{g\}$ is transitive if we decide  to use this definition. The second version \eqref{EQ: Defn of RGS(W,g): B} is also nice because it allows us to refer to $RGS(W,g)$ as the \emph{relative} generating sets of $W$ with respect to $g$. Now, the following seems to be true:




%For a Weyl group $W$, let $I(W)$ denote its connection coefficient (or connection index), that is, the index of the root lattice in the weight lattice; it also equals the determinant of the Cartan matrix of $W$. For the groups $(\Symm_n,B_n,D_n,F_4,E_6,E_7,E_8)$, it is given respectively by $(n,2,4,1,3,2,1)$. 
%Then we have the following result.





%\epigraph{\footnotesize But if you happen to be deaf and dumb\\
%And do not understand a word I say,
%Then wave your hand, to signify as much.}{Fragment of a Greek tragedy}

We prove now our Theorem~\ref{thm:main}, enumerating transitive
reflection factorizations of parabolic quasi-Coxeter elements in Weyl
groups. We split the proof into two parts: we first
handle the  classical types $A_n$, $B_n$, and $D_n$, and then separately the exceptional types.
We sketch the proof in types $A_n$ and $D_n$; the proof of type
$B_n$ is similar. 

\subsubsection*{Sketch of proof of Theorem~\ref{thm:main} in classical
  types}


 

%
%\begin{theorem}\label{Thm: Weyl case}
%If $W$ is a Weyl group of rank $n$, then the number $\Ftr_W(\id)$ of minimum-length (i.e., length-$2n$) transitive reflection factorizations of the identity $\id\in W$ is
%\[
%\Ftr_W(\id)=(2n)!\cdot\dfrac{1}{I(W)}\cdot |RGS(W)|.
%\]
%More generally, if $g$ is any parabolic quasi-Coxeter element in $W$, then $\Ftr_W(g)$ is given by
%\[
%\Ftr_W(g) = \frac{\ltr(g)!}{\lR(g)!}\cdot |RGS(W,g)| \cdot \frac{I(W_g)}{I(W)} \cdot G_W(g),
%\]
%where $W_g=W_{V^g}$ is the (unique) minimal parabolic subgroup that contains $g$ (equivalently the parabolic subgroup that fixes $V^g$), $I(W)$ as before denotes the connection index, \jbl{and $G_W$ \ldots}. 
%\end{theorem} 

%
%Notice that for $\Symm_n$, we have $I(\Symm_n)=n$ which recovers the Hurwitz formula $\Ftr_{\Symm_n}(\id)=(2n-2)!\cdot n^{n-3}$. \jbl{is this metnioend above??}\theo{Yes}





\noindent {\bf Type A:} As we have mentioned before, in type A all elements are parabolic quasi-Coxeter. We start with some $g\in \Symm_n$ of cycle type
$\lambda=(\lambda_1,\cdots,\lambda_c)$ and we first look at the right side
of \eqref{EQ: F_W(g)}. By Prop.~\ref{Prop: l^tr(w)=2n-lr(w)}, we have that $\ltr(g)= n+c-2 $. The set $RGS(\Symm_n,g)$ can be described via
 trees on the $c$-many cycles of $g$: after adding a reduced factorization of $g$ to a relative generating set, the total set of transpositions will give a tree on $[n]$. Since there are $\lambda_i\cdot\lambda_j$ possible edges between the $i$th and $j$th cycles, 
each tree on $[c]$ appears with total multiplicity $\prod_{i=1}^c \lambda_i^{\deg(T_i)}$. Now the weighted
Cayley theorem implies that $$|RGS(\Symm_n,g)|=\sum_{T\text{ a tree on
  }[c]}\prod_{i=1}^c\lambda_i^{\deg(T_i)}=\lambda_1\cdots
\lambda_c\cdot
(\lambda_1+\cdots+\lambda_c)^{c-2}=\big(\prod\lambda_i\big)\cdot
n^{c-2}.$$ Moreover, the parabolic subgroup corresponding to $g$ is just a Young subgroup of type $\Symm_{\lambda}:=\Symm_{\lambda_1}\times\cdots\times\Symm_{\lambda_c}$, which means that its connection index is $I(\Symm_{\lambda})=\lambda_1\cdots\lambda_c$. Finally, we have $\prod\Fred(g_i) =
\prod_{i=1}^c \lambda_i^{\lambda_i-2}$ corresponding to minimum-length reflection factorizations of the cycles $g_i$ of $g$. Multiplying all these quantities together gives
exactly the expression of formula \eqref{EQ: Hurwitz formula} for $H_0(\lambda)$, which is by definition the left side of \eqref{EQ: F_W(g)}.



\bigskip


%\noindent {\bf Type B:} In type B, there are two types of parabolic subgroups: those of the form $\Symm_\lambda$ for $\lambda \vdash n$, and those of the form $B_k \times \Symm_{\lambda}$ for $\lambda \vdash n - k$.  The parabolic quasi-Coxeter elements for the first type have all cycles positive, while those of the second type have exactly one negative cycle.  
%
%
%Suppose $g$ has $c$ cycles, all positive.  We begin with the right side.  In this case $\lR(g) = n - c$ and the minimum-length reflection factorizations are precisely the same as those restricted to the subgroup, so $G_{B_n}(g) = G_{\Symm_n}(g) =  \binom{n - c}{\lambda_1 - 1; \cdots; \lambda_c - 1} \cdot \prod_i \lambda_i ^{\lambda_i - 2}$.  A relative generating set of reflections must include at least one diagonal reflection (otherwise everything belongs to the subgroup of type $D_n$) and must induce a connected graph when taken together with the a shortest reflection factorization of $g$ (otherwise everything belongs to a maximal reflection subgroup of type $B_k \times B_{n - k}$ for some $k$).  Taking the contraction of such a graph with respect to the factors in the shortest factorization, we see that the transposition-like factors in the relative generating set form a tree on the $c$ cycles of $g$, where an edge connected to cycle $C$ has $|C|$ choices of endpoint in that cycle.  Thus, taking account of sign, we have
%\[
%|RGS(B_n, g)| = n \cdot 2^{c - 1} \sum_{T \text{ a tree on } [c]} \prod_{i = 1}^c \lambda_i ^{\deg(i)} = n \cdot 2^{c - 1} \cdot (\lambda_1 + \ldots + \lambda_c)^{c - 2} \cdot \prod_i \lambda_i %= (2n)^{c - 1}\cdot \prod_i \lambda_i
%\]
%by the weighted Cayley theorem.  Combining these results and simplifying \jbl{?}, the right side of the claimed equality in this case is
%\[
%\frac{(n + c)!}{(n - c)!} \cdot (2n)^{c - 1}\cdot \prod_i \lambda_i \cdot \frac{\prod_i \lambda_i}{2} \cdot \binom{n}{\lambda} \cdot \prod_i \lambda_i ^{\lambda_i - 2}.
%\] 
%
%Now we consider the left side.  A transitive reflection factorization of an element in $B_n$ must contain at least one diagonal reflection and must correspond to a connected graph; since the element under consideration has all cycles positive, it must include at least two diagonal reflections.  Comparing reflection lengths, it follows that minimum-length transitive factorizations of an element $g$ with all $c$ cycles positive include two diagonal factors, and their transpositions project under $\pi$ to a shortest transitive $\Symm_n$-factorization of $\pi(g)$.  Thus, the number of such projections is $\binom{n + c}{2} \cdot H_0(\lambda)% =  \frac{1}{2} \cdot (n + c)! \cdot n^{c - 3} \prod_{i} \frac{\lambda_i^{\lambda_i}}{(\lambda_i - 1)!}
%$.  Comparing with~\eqref{EQ: Hurwitz formula} and the previous paragraph, we see that it suffices to show that each such projection has precisely $2^{c - 1} \cdot n^2$ preimages.  Indeed, fixing a spanning tree of the (multi)graph induced by the factorization, it is not difficult to see that for any choice of which of the $n$ diagonal entries the two sign-changes effect and which of two signs to give the $c - 1$ edges not in the spanning tree, these choices and the requirement that the factorization multiplies to $g$ uniquely determine the signs of the edges in the spanning tree. 
%
%If instead the element $g$ has a single negative cycle of length $k$ (and $c - 1$ positive cycles), the calculations in the preceding case change as follows: we have $\lR(g) = n - c + 1$ and $G_{B_n} = \binom{n - c + 1}{k; \lambda_1 - 1; \cdots; \lambda_{c - 1} - 1} \cdot k^k \cdot \prod_i \lambda_i^{\lambda_i - 2}$.  Relative generating sets must have the same tree structure but no longer require a diagonal reflection, so $|RGS(B_n, g)| = 2^{c - 1} \cdot n^{c - 2} \cdot k \cdot \prod_i \lambda_i$, and the entire right side is equal to 
%\[
%\frac{(n + c - 1)!}{(n - c + 1)!} \cdot 2^{c - 1} \cdot n^{c - 2} \cdot k \cdot \prod_i \lambda_i \cdot \frac{2 \prod_i \lambda_i}{2} \cdot \binom{n - c + 1}{k; \lambda_1 - 1; \cdots; \lambda_m - 1} \cdot k^k \cdot \prod_i \lambda_i^{\lambda_i - 2}.
%\]
%
%On the left side, we see by identical reasoning that a transitive reflection factorization of $g$ in this case consists of a single diagonal reflection and $n + c - 2$ transpositions, whose projections under $\pi$ give a transitive factorization of $\pi(g)$.  Thus, the number of such projections is $\binom{n + c - 1}{1} H_0(\lambda + k)$, where $\lambda + k$ denotes the cycle type of $\pi(g)$.  An identical argument to the previous case shows that each projection has $2^{c - 1} \cdot n$ preimages, and consequently by~\eqref{EQ: Hurwitz formula} the left side in this case is
%\[
%2^{c - 1}n \cdot (n + c - 1) \cdot (n+c-2)!\cdot n^{c-3}\cdot \frac{k^k}{(k - 1)!} \prod_i \dfrac{\lambda_i^{\lambda_i}}{(\lambda_i-1)!},
%\]
%which is easily seen to be equal to the number we computed for the right side.
%
%\medskip
%

\noindent {\bf Type D:} We represent the elements in $D_n$ as signed permutations acting on
$\pm i$, $i=1,\ldots,n$. Any element $g$ in $D_n$ is a product of
disjoint cycles.  Such cycles are positive or negative depending on if
the number of sign changes in the cycle is even or odd.  Given an
element $g$ in $D_n$, the projection $\pi(g)$ in $\Symm_n$ is the permutation
obtained by removing the signs from the entries.  Following Zaslavsky \cite{Z}, one may think of sets of reflections in
type D as the edges of a signed graph.


The group $D_n$ has two types of parabolic subgroups: those of the form $\Symm_\lambda$ for $\lambda \vdash n$, and those of the form $D_k \times \Symm_{\lambda}$ for $\lambda \vdash n - k$.  The parabolic quasi-Coxeter elements for the first type have all cycles positive, while those of the second type have exactly two negative cycles.  We consider the second case first.


Suppose that $g$ has two negative cycles and $c - 2$ positive cycles, and the two negative cycles have sizes $k_1$, $k_2$ (with $k_1 + k_2 = k$).  We have in this case that $\lR(g) = n - c + 2$ and therefore $\ltr(g) = n + c - 2$, which is also the length of a shortest transitive $\Symm_n$-factorization of the projection $\pi(g)$.  It follows that the projection into $\Symm_n$ of a shortest transitive factorization of $g$ produces a shortest transitive factorization of $\pi(g)$.  Fix a subset of factors in such a factorization that form a spanning tree on $[n]$.  It is not difficult to see that we may choose the signs on the other $c - 1$ factors independently, and the signs on the $n - 1$ fixed edges will be uniquely determined by the choices and the requirement to be a factorization of $g$.  It follows immediately in this case that the left side of \eqref{EQ: F_W(g)} is equal to $2^{c - 1} \cdot H_0(\lambda + k_1 + k_2) = 2^{c - 1}  \cdot (n + c - 2)! \cdot n^{c - 3} \cdot \frac{k_1^{k_1} k_2^{k_2}}{(k_1-1)!(k_2-1)!}\prod \frac{\lambda_i^{\lambda_i}}{(\lambda_i - 1)!}$.

Still considering the same element $g$ with two negative cycles, we move to the right side of \eqref{EQ: F_W(g)}.  A relative generating set of reflections for such an element $g$ must induce a connected graph when taken together with a shortest reflection factorization of $g$.  Taking the contraction of such a graph with respect to the factors in the shortest factorization, we see that the factors in the relative generating set form a tree whose $c - 1$ vertices are the $c - 2$ positive cycles of $g$ and a single vertex for the two negative cycles, where an edge connected to a vertex $C$ has $|C|$ choices of endpoint in that cycle.  Thus, taking account of sign, we have
$
|RGS(D_n, g)| = 2^{c - 2} \sum_{T \text{ a tree on } [c - 1]} \prod_{i = 1}^{c - 2} \lambda_i ^{\deg(i)} \cdot k^{\deg(c - 1)}
$.  By the weighted Cayley theorem, this simplifies to 
\[
2^{c - 2} \cdot (\lambda_1 + \ldots + \lambda_{c - 2} + k)^{c - 3}
\cdot k \cdot \prod_i \lambda_i  = 2^{c - 2} \cdot n^{c - 3} \cdot k
\cdot \prod_i \lambda_i.
\]
For this element $g$ we have $\frac{I(W_g)}{I(W)} = \frac{4 \prod_i \lambda_i}{4}$.  Finally, since there are $2 \frac{(k - 1)!}{(k_1 - 1)!(k_2 - 1)!} k_1^{k_1} k_2^{k_2}$ shortest factorizations of a quasi-Coxeter element in $D_k$ whose cycles have lengths $k_1$ and $k_2$ (see Table~\ref{tab:table1}), we have $\prod\Fred(g_i) = 2 \frac{(k - 1)!}{(k_1 - 1)!(k_2 - 1)!} k_1^{k_1} k_2^{k_2} \cdot \prod_i^{c-2} \lambda_i^{\lambda_i - 2}$.  Plugging these factors in to the right side of \eqref{EQ: F_W(g)} gives exactly the value $\Ftr_W(w)$ computed in the previous paragraph.

Finally, suppose that $g$ has $c$ cycles, all positive. Thus $\lR(g) = n - c$.  Since the minimum-length reflection
factorizations of $g$ are precisely the same as those restricted to its parabolic
subgroup, we have $\prod\Fred_{D_n}(g_i) = \prod\Fred_{\Symm_n}(g_i) = \prod_i^c \lambda_i
^{\lambda_i - 2}$.  A relative generating set must consist of $c$
edges and induce a connected signed graph when taken together with the
a shortest reflection factorization of $g$.  Taking the contraction of
such a graph with respect to the factors in the shortest
factorization, the transposition-like factors in the relative
generating set form a signed ``unicycle'': a connected graph with $c$
vertices (the cycles of $g$) and $c$ edges, where again the edges are
weighted so that an edge connected to cycle $C_i$ has $|C_i| =
\lambda_i$ choices of endpoint in that cycle.  Moreover, in the unique
cycle in this graph, the number of negatively signed transpositions
must be odd (otherwise, all reflections belong to a subgroup conjugate
to $\Symm_n$).  We may count such graphs as follows: if the cycle is a
loop, with both endpoints in cycle $C_i$, then it may be chosen in
$\binom{\lambda_i}{2}$ ways, while the rest of the set forms a signed
weighted tree on $c$ vertices.  Thus, the contribution from this case
is 
\[
2^{c - 1} n^{c - 2} \prod_i \lambda_i \cdot \sum_i
\binom{\lambda_i}{2} = 2^{c - 2}n^{c - 2}(-n +
\sum_i \lambda_i^2) \prod_i \lambda_i .
\] 
Otherwise, the cycle has some length $k \geq 2$.  Let the vertices in the cycle be indexed by $S = \{s_1, \ldots, s_k \} \in \binom{[c]}{k}$.  Contracting the edges of the cycle gives a signed weighted tree on $c - k + 1$ vertices, of weights $\{\lambda_i \colon i \not \in S\} \cup \{\lambda_{s_1} + \ldots + \lambda_{s_k}\}$.  This weighting has the feature that the generating functions by weights for the relevant trees and unicycles are closely related: they differ by a factor of $2^{k - 2} (k - 1)! \cdot (\lambda_{s_1} \cdots \lambda_{s_k})^2$, where the first factor accounts for the number of different ways of inserting a signed cycle while the second factor accounts for the weights from adding the edges of the cycle.  By the weighted Cayley theorem, the generating function for the trees is precisely 
\[
(\lambda_{s_1} + \ldots + \lambda_{s_k}) \cdot \prod_{i \not \in S} \lambda_i \cdot (\lambda_1 + \ldots + \lambda_c)^{c - k - 1} \cdot 2^{c - k} = (\lambda_{s_1} + \ldots + \lambda_{s_k}) \cdot \prod_{i \not \in S} \lambda_i \cdot n^{c - k - 1} \cdot 2^{c - k},
\]
and consequently the generating function for the unicycles in this case is
\[
(\lambda_{s_1} + \ldots + \lambda_{s_k}) \lambda_{s_1} \cdots \lambda_{s_k} \cdot 2^{c - 2} (k - 1)! n^{c- k - 1} \prod_i \lambda_i .
\]
Thus
%\[
%|RGS(g, D_n)| =  2^{c - 2} \prod_i \lambda_i  
%\left({\color{red} n^{c - 2} \sum_{i} (\lambda_i^2 - \lambda_i) +}
%\sum_{k = 2}^n (k - 1)! n^{c- k - 1} \sum_{S \in \binom{[c]}{k}} (\lambda_{s_1} + \ldots + \lambda_{s_k}) \lambda_{s_1} \cdots \lambda_{s_k}
%\right),
%\]
\begin{align*}
|RGS(D_n,g)| &=  2^{c - 2} \prod_i \lambda_i  
\Big(-n^{c - 1}  +
\sum_{k = 1}^c (k - 1)! n^{c- k - 1} \sum_{S \in \binom{[c]}{k}} (\lambda_{s_1} + \ldots + \lambda_{s_k}) \lambda_{s_1} \cdots \lambda_{s_k}
\Big)\\
&=  2^{c - 2} \prod_i \lambda_i  
\Big(-n^{c - 1}  + \sum_{k = 1}^c (k - 1)! n^{c- k - 1} m_{21^{k-1}}(\lambda)\Big),
\end{align*}
where $m_{\mu}(\lambda)$ is the {\em monomial symmetric function} in
the variables $\lambda$. Now $m_{2,1^{k-1}}= e_{k,1}-(k+1) e_{k+1}$, and since $e_1(\lambda)=n$ the right side of the last expression becomes
\begin{multline*}
  2^{c - 2} \prod_i \lambda_i  
\Big(-n^{c - 1}  +  \sum_{k=1}^c (k-1)! n^{c-k} e_k(\lambda) - \sum_{k=1}^c (k-1)! (k+1)
  n^{c-k-1} e_{k+1}(\lambda)\Big).
\end{multline*}
The first term of the first sum in this expression is
$n^{c-1}e_1(\lambda)=n^c$. Separating this term and combining the
remaining terms with the second sum gives
\begin{align*}
|RGS(D_n,g)| &=  2^{c - 2} \prod_i \lambda_i  
\Big(n^c - n^{c-1} -\sum_{k=2}^c  (k-2)!n^{c-k} e_k(\lambda)\Big),
\end{align*}
so for this $g$ the entire right side of  \eqref{EQ: F_W(g)}  is
%\[
%\frac{(n + c)!}{(n - c)!}  \cdot  \binom{n - c}{\lambda_1 - 1; \cdots; \lambda_c - 1} \cdot \prod_i \lambda_i ^{\lambda_i } \cdot
%2^{c - 4}  \sum_{k = 2}^n (k - 1)! n^{c- k - 1} \sum_{S \in \binom{[c]}{k}} (\lambda_{s_1} + \ldots + \lambda_{s_k}) \lambda_{s_1} \cdots \lambda_{s_k}.
%\]
\begin{align*}
\frac{(n + c)!}{(n - c)!}  \cdot  \binom{n - c}{\lambda_1 - 1; \cdots; \lambda_c - 1} \cdot \prod_i \lambda_i ^{\lambda_i } \cdot
2^{c - 4} \Big(n^c - n^{c-1} -\sum_{k=2}^c  (k-2)!n^{c-k}
  e_k(\lambda)\Big).
\end{align*}
This is exactly $3 \cdot 2^{c-1} \cdot
H_1(\lambda)$, where we used the formula for $H_1(\lambda)$ in Lemma~\ref{GJVGJV}.


Now we consider the left side of equation \eqref{EQ: F_W(g)},
still in the case that $g$ is an element of $D_n$ with all positive
cycles.  Projecting a transitive factorization of $g$ into $\Symm_n$, we produce a
connected transposition factorization having $n + c$ factors of a
permutation $\pi(g)$ whose transitive reflection length (in $\Symm_n$)
is $n + c - 2$.  That is, it is a genus-$1$ transitive factorization
in the symmetric group.  The number of such factorizations is
$H_1(\lambda)$.  Moreover, each of these may
be lifted by assigning appropriate signs to a transitive factorization
of $g$ in $D_n$ in the same number of ways; accounting simultaneously
for the requirements that the product is $g$ and the reflections
generate $D_n$, this number turns out to be $3 \cdot 2^{c - 1}$. \qed


%\begin{remark}
%As a special case of \eqref{EQ: F_W(id)} for type $D$ we have that 
%\[
%|RGS(D_n)| = \frac{3\cdot 2^{n+1}}{(2n)!} H_1(1^n) = 2^{n-2}(n^n -
%n^{n-1} - \sum_{i=2}^n \binom{n}{i} (i-2)! n^{n-i}).
%\]
%This matches the sequence \cite[A320064]{oeis} counting {\em signed
%  pseudotrees} 
%that was recently
%studied in \cite{ardila2020} in the context of {\em Ehrhart theory} of Coxeter
%permutahedra. 
%\end{remark}



\subsubsection*{Sketch of computer proof of Theorem~\ref{thm:main} for
  the exceptional types} \label{sec: computer}

For the exceptional Weyl groups $G_2$, $F_4$, $E_6$, $E_7$, and $E_8$, we prove our main theorem by direct calculation of both sides of \eqref{EQ: F_W(g)} via SageMath and CHEVIE \cites{chevie}{sagemath}. It turns out that the most efficient way to do this will further count transitive reflection factorizations of arbitrary length. We follow the traditional approach via representation theory and the lemma of Frobenius \cite[\S~4]{CC} to first determine the exponential generating functions of \emph{not necessarily transitive} reflection factorizations of an element $g$:

\begin{equation}
\mathcal{F}_W(g;t):=\sum_{N\geq 0}\#\{(\tau_1,\dots,\tau_N)\in\mathcal{R}^N:\ \tau_1\cdots\tau_N=g\}\cdot \dfrac{t^N}{N!}.\label{EQ: Defn F_{W,g}(t)}
\end{equation}
They can be computed as a finite sum of exponentials via the formula \cite[(4.3)]{CC} 
$$\mathcal{F}_W(g;t)=\dfrac{1}{|W|}\cdot\sum_{\chi\in\widehat{W}}\chi(1)\cdot
\chi(g^{-1})\cdot\op{exp}\left(\dfrac{\chi(\mathcal{R})}{\chi(1)}\cdot
  t\right),$$ where
$\widehat{W}$ denotes the set of irreducible (complex) characters of
$W$ (these are produced by CHEVIE, which realizes reflection groups
via their permutation action on roots)
and $\chi(\mathcal{R}):=\sum_{\tau\in\mathcal{R}}\chi(\tau)$. Any factorization enumerated
in \eqref{EQ: Defn F_{W,g}(t)} will be transitive for the group
$W':=\langle \tau_1,\dots,\tau_N\rangle$ generated by its
elements. Then, a simple inclusion-exclusion argument gives us the
corresponding generating functions for \emph{transitive}
factorizations: \begin{equation} \label{eq: mobius transitive}\mathcal{F}^{\textrm{tr}}_W(g;t)=\sum_{g\in W'\subset W}\mu(W,W')\cdot\mathcal{F}_{W'}(g;t),\end{equation} where we sum over all \emph{reflection} subgroups $W'$ of $W$ (that contain $g$) ordered by reverse inclusion. Having established the generating function $\mathcal{F}_{W}^{\textrm{tr}}(g;t)$, and since it remains a finite
sum of exponentials, we can immediately calculate its leading term, which equals
$\Ftr_W(g)\cdot \big(t^{\ltr(g)}/\ltr(g)!\big)$. To compute finally the
quantity $|RGS(W,g)|$ of \eqref{EQ: F_W(g)}, we
consider all possible $(n-\ell_R(g))$-subsets of the set of reflections in $W\setminus W_g$ and check whether they extend an arbitrary reflection factorization of $g$ to a reflection generating set of $W$.\qed



%The most computationally heavy part of this process is constructing the lattice of reflection subgroups of $W$. To do this, we calculate one factorization $\tau_1\cdots\tau_k=g$ in each Hurwitz orbit of reduced reflection factorizations for a collection of conjugacy class representatives $g$ of $W$. The family of groups $W_{g,\bm\tau}:=\langle \tau_i\rangle$ \emph{and all their conjugates} form then a complete list of the reflection subgroups of $W$.



%
%
%After Baumeister et al. \cite{BGRW}, if a set of reflections of size $n$ generates $W$, then their product in any order is a quasi-Coxeter element. Moreover any reduced factorization of a quasi-Coxeter element generates the whole group and they all lie in the same Hurwitz orbit. These Hurwitz orbit sizes, or equivalently the numbers of reduced factorizations, have been computed by Voigt and Kluitmann \cite{Kluitmann}. (They are also easy to calculate in sage and Christian Stump had done it in the past; these numbers all factor nicely, but this is another story!) After you count these, add them up for each quasi-Coxeter element, and divide by $n!$ (to get sets of reflections), you have the numbers $|RGS(W)|$ and can compare (see attached code); it works for all Weyl groups (including $E_8$).
%
%For the family $B_n$, the only quasi-Coxeter elements are the usual Coxeter elements. That is, generating sets of reflections are exactly those that appear in reduced factorizations of Coxeter elements, so we would have something like 
%\[
%|RGS(B_n)| = \underbrace{2^{n-1}\cdot (n-1)!}_{\#\text{ of Cox. elts}}\quad \cdot \underbrace{\quad\quad\quad\quad n^n \quad\quad\quad\quad}_{\#\text{ of red. facns of Cox. elts in }B_n} \cdot \dfrac{1}{n!}=(2n)^{n-1},
%\]
%(this is \cite[A052746]{oeis}, see \cite{ardila2020})
%where the last term $(1/n!)$ is for turning tuples into sets. (Alternatively, not using quasi-Coxeter elements: minimum generating sets in $B_n$ consist of a tree of $n - 1$ transpositions, each of which is either signed or unsigned, and a single sign-change; hence the number of them is $n^{n - 2} \cdot 2^{n - 1} \cdot n = (2n)^{n - 1}$.)  Moreover, we have shown before that $$F_{B_n}(\id)=\binom{2n}{2}\cdot n^2\cdot \phi(2)\cdot 2^{n-1}\cdot \big[(2n-2)!\cdot n^{n-3}\big]=(2n)!\cdot\dfrac{1}{2}\cdot (2n)^{n-1},$$ which agrees with the theorem (the connection index is $I(B_n)=2$).

%For the family $D_n$, again we know the quasi-Coxeter elements and the number of reduced reflection factorizations for each of them (see the paper \cite{Kluitmann} by Kluitmann on Voigt's thesis in the bibliography): 
%%
%There are $\lfloor n/2\rfloor$ different conjugacy classes of quasi-Coxeter element in $D_n$: they are in fact the Coxeter elements of the reflection subgroups $B_k\times B_{n-k}\leq B_n$, and we denote them $D(k,n-k)$, $1\leq k\leq \lfloor n/2 \rfloor$. The centralizer of $D(k,n-k)$ in $D_n$ has size $2\cdot k\cdot (n-k)$ when $k\neq n-k$ and $n^2$ when $k=n-k$, and the number of reduced reflection factorizations of $D(k, n - k)$ is 
%$2\cdot k^k\cdot (n-k)^{n-k}\cdot (n-1)\cdot \binom{n-2}{k-1}$. 
%So, 

%\begin{align*}
%|RGS(D_n)| & = \sum_{k=1}^{n-1}\underbrace{\dfrac{2^{n-1}\cdot n!}{4\cdot k\cdot (n-k)} }_{\text{almost }\#\text{ of q-Cox. elts }D(k,n-k)}\cdot \underbrace{ 2\cdot k^k\cdot (n-k)^{n-k}\cdot (n-1)\cdot \binom{n-2}{k-1}}_{\#\text{ of red facns of any }D(k,n-k)}\cdot \dfrac{1}{n!} \\
%& =  \frac{2^{n - 2}}{n} \sum_{k=1}^{n-1} \binom{n}{k} \cdot  k^k\cdot (n-k)^{n-k}.
%\end{align*}

%(this matches \cite[A320064]{oeis}, see \cite{ardila2020}) On the other hand, according to Theorem~\ref{Thm: F_W(t) for G(m,p,n)} we have $F_{D_n}(\id)=2^{n-1}\cdot 3\cdot H_1(1^n)$ and so by the formula for $H_1(1^n)$ (see Theorem~\ref{GJVGJV}) we have
%\[
%F_{D_n}(\id)=2^{n-1}\cdot 3\cdot \frac{1}{24} \cdot (2n)! \cdot \left(n^n - n^{n-1} -
%\sum_{i=2}^n \binom{n}{i} (i-2)! n^{n-i}\right).
%\]

%Since the connection index for $D_n$ is $I(D_n)=4$, the desired statement is equivalent to 
%\[
%\sum_{k=1}^{n-1}\binom{n}{k}k^k(n-k)^{n-k}+\binom{n}{k+1}n^{n-k}(k-1)!   \overset{???}{=}  n^{n+1}-n^n.
%\]
%Here is a proof of this identity using generating functions and OEIS. Let 
%\[
%a_n =\sum_{k=1}^{n-1}\binom{n}{k}k^k(n-k)^{n-k} = n! \sum_{k=0}^{n-2} n^k/k!
%\quad \textrm{and} \quad
%b_n = \sum_{k=1}^n \binom{n}{k+1}n^{n-k}(k-1)!,
%\]
%with exponential generating functions
%\[
%A(x) := \sum_{n \geq 0} a_n \frac{x^n}{n!} = T(x)^2/(1-T(x))^2, \quad B(x):=\sum_{n \geq 0} b_n \frac{x^n}{n!} =T(x)^2/(1-T(x))^3
%\]
%where $T(x)=-W(-x)$ is the
 % exponential generating function for $n^{n-1}$ and $W(x)$ is the
 % Lambert W function. The exponential generating function
%for $n^{n+1}-n^n$ is 
%\[
%C(x):=\sum_{n \geq 0} (n^{n+1}-n^n) \frac{x^n}{n!} = x\frac{d}{dx} (  x\frac{d}{dx} T(x) - T(x)).
%\]
%By derivative properties of $W(x)$ we have that $x\frac{d T(x)}{dx} = T(x)/(1 - T(x))$ and then it follows by a computation that $A(x)+B(x)=C(x)$.






\section{Generalization to complex reflection groups}
\label{Sec: complex case}

There is significant evidence that our Theorem~\ref{thm:main} extends naturally to all well-generated complex reflection groups (finite subgroups of $\op{GL}(\CC^n)$ generated by $n$ unitary reflections). The quantity $|RGS(W,g)|$ is replaced by a statistic on the relative generating sets that in the case of Weyl groups always equals $I(W_g)/I(W)$. To introduce this statistic, we need an analog of roots, but we will not require that they form a $W$-equivariant collection. That is, for each reflection $\tau$ of $W$ and its unique  $\zeta\neq 1$ eigenvalue, we pick any nonzero element $\rho_{\tau}$ of the $\zeta$-eigenspace of $\tau$. We further normalize their lengths, defined via the standard Hermitian inner product $(\cdot,\cdot)$, to satisfy $(\rho,\rho)=2$ for all roots $\rho$.

\begin{definition}
The {\color{blue} \emph{Grammian determinant}} $\op{GD}(\bm\rho)$  of a set of roots $\bm{\rho}:=\{\rho_i\}$ is $$\op{GD}(\bm{\rho}):=\det\big( \langle \rho_i,\rho_j\rangle\big)_{ij}.$$ 
\end{definition}

In a Weyl group $W$, we may simultaneously consider roots $\rho$, coroots $\check{\rho}$, and \emph{normalized} roots $\tilde{\rho}$, satisfying $(\tilde{\rho},\tilde{\rho})=2$ as above. Now, \cite[Cor.~1.2]{BW} shows that roots $\rho_i$ and coroots $\check{\rho_i}$ that correspond to a reflection generating set of $W$ always form $\ZZ$-bases of the root and coroot lattices $\mathcal{Q}$ and $\check{\mathcal{Q}}$ respectively. This forces that $\op{det}\big(\langle \rho_i,\check{\rho_j}\rangle\big)_{i,j}=I(W)$, which then further implies that $\op{GD}(\bm\tilde{\bm\rho})=I(W)$ since $\op{det}\big(\langle \rho_i,\check{\rho_j}\rangle\big)_{i,j}=\op{det}\big(\langle \tilde{\rho_i},\tilde{\rho_j}\rangle\big)_{i,j}$. The following result, which has a proof very much analogous to the work in \S~\ref{sec:main results}, is then a direct generalization of the case $g=\id$, displayed in \eqref{EQ: F_W(id)}, of Theorem~\ref{thm:main}. 

\begin{theorem}
\label{Thm: Complex case: id}
For a well-generated complex reflection group $W$ of rank $n$, the number of minimum-length transitive reflection factorizations of the identity $\id\in W$ is given by
\[
\Ftr_W(\id) =(2n)!\cdot \sum_{\{\tau_i\}\in RGS(W) }\dfrac{1}{\op{GD}(\bm{\rho_{\bm\tau}})},
\]
where the sum is over all subsets of $n$ reflections $\{\tau_i\}$ that generate $W$ and $\rho_{\tau_i}$ is a root for $\tau_i$.
\end{theorem}

When $W$ is not a Weyl group, this is a non-trivial sum and the numbers $\op{GD}(\bm{\rho_{\bm\tau}})$ that appear are not constant. For instance, in $H_3$, there are two ``generalized" Coxeter classes related by a reflection automorphism; generating sets that correspond to factorizations of elements from one class have Grammian determinant $3+\sqrt{5}$, while the others have Grammian determinant $3-\sqrt{5}$. Notice here that the cummulative contribution of two such sets paired by the automorphism is a rational number $\frac{1}{3+\sqrt{5}}+\frac{1}{3-\sqrt{5}}=\frac{3}{2}$. Generating sets corresponding to the third quasi-Coxeter class satisfy $\op{GD}(\bm\rho)=2$.

There is in fact a similar full generalization of Theorem~\ref{thm:main} for well generated groups, but we have not completed our work on it. We state it here as a conjecture.

\begin{conjecture}
\label{Conj. Ftr complex case}
If $W$ is a well-generated complex reflection group and $g$ a parabolic quasi-Coxeter element in $W$ with decomposition $g=g_1\cdots g_m$, then 
$$\Ftr_W(g)=\ltr(g)!\cdot\prod_{i=1}^m\dfrac{\Fred(g_i)}{\ell_R(g_i)!}\cdot  \sum_{\{\tau_i\}\in RGS(W,g)}\dfrac{\op{GD}(\bm{\rho}_g)}{\op{GD}(\bm{\rho_{\bm\tau}}\cup\bm{\rho}_g)},$$ 
where $\bm\rho_{\bm\tau}$ denotes the set of roots associated with a relative generating set ${\bm \tau} = \{\tau_i\}$ and $\bm\rho_g$ corresponds to a fixed reduced reflection factorization of $g$.
\end{conjecture}


\section{Higher genus counts in the infinite family}
\label{Sec: Higher genus}

As discussed in Section~\ref{sec: computer}, the 
proof for the exceptional types gives in \eqref{eq: mobius
  transitive} the complete enumeration for
 transitive factorizations of arbitrary length. In this section, we study
the analogous generating functions for the infinite family $G(m,p,n)$
of complex reflection groups. The generating functions are defined as 
$\mathcal{F}^{\textrm{tr}}_W(g;t):=\sum_{N\geq 0}
\Ftr_W(g,N)\cdot t^N / N!$ where $\Ftr_W(g,N)$ is
the number of length-$N$ transitive reflection factorizations of
$g\in W$. The following theorem expresses $\mathcal{F}^{\textrm{tr}}_W(g;t)$
for elements $g$ in $G(m,p,n)$ with only weight-$0$ cycles in terms of the
generating functions of the symmetric group
$\Symm_n=G(1,1,n)$.


\begin{theorem}\label{Thm: F_W(t) for G(m,p,n)}
For an element $g\in G(1,1,n) \subset G(m,p,n)$, we have
\begin{align}
\mathcal{F}^{\textrm{tr}}_{G(m,p,n)}(g;t) & =\dfrac{1}{(m/p)^{n-1}}\cdot\mathcal{F}^{\textrm{tr}}_{G(p,p,n)}\big(g;(m/p)\cdot t\big)\cdot\mathcal{F}^{\textrm{tr}}_{G(m/p,1,1)}(\id;nt), \\
%\intertext{and}
\mathcal{F}^{\textrm{tr}}_{G(m, m, n)}(g;t) & = m^{c-1} \sum_{d | m} \mu(m / d) \cdot d^{2 - c-n} \cdot 
\mathcal{F}^{\textrm{tr}}_{G(1,1, n)}(g; d t),
\end{align}
where $c$ is the number of cycles of $g$ and $\mu$ is the number-theoretic M\"obius function.
%In particular,
%\[
%\mathcal{F}_{G(m,1,n)}(t) =\dfrac{1}{m^{n-1}}\cdot \mathcal{F}_{G(1,1,n)}(mt)\cdot\mathcal{F}_{G(m,1,1)}(nt).
%\]
\end{theorem}
The proof is similar to that presented for type D in Section~\ref{sec:main results}: there is a natural projection map that sends any reflection factorization in $G(m, p, n)$ to a factorization in $\Symm_n$ as a product of transpositions.  Each of these factorizations may be lifted back to $G(m, p, n)$ in a predictable number of ways.  In $G(m, p, n)$ with $p < m$, the lifting must account for the introduction of diagonal reflections (the analogues of sign-change reflections in type B), giving rise to the term corresponding to the cyclic group $G(m/p, 1, 1)$; in $G(m, m, n)$, the lift must generate the full $G(m, m, n)$ and not any subgroup $G(d, d, n)$ for $d \mid m$, leading to the M\"obius inversion.


%\theo{Maybe get rid of corollary below if we don't have space (and replace with D-Y-Z recursion}
%\begin{cor}\label{cor: F_W(id) for G(m,1,n), G(m,m,n)}
%For a group $W$ in the infinite family, one has that the number $\Ftr_W(\id)$ of minimum-length transitive factorizations of the identity $\id$ is given by
%\begin{align*}
%\Ftr_{G(m, 1, n)}(\id) &= \binom{2n}{2} \cdot n^2 \cdot m^{n - 1} \cdot \phi(m) \cdot {\color{red} n^{n - 3} \cdot (2n - 2)!} =\dfrac{1}{2}\cdot (mn)^{n-1}\cdot \phi(m)\cdot (2n)! %\; ;\\
%\Ftr_{G(m, m, n)}(\id) &= H_1(1^{n}) \cdot m^{n - 1} \cdot \sum_{d \mid m} d^2 \cdot \mu(m/d) \; ; 
%\end{align*}
%and for $m > p > 1$, $\Ftr_{G(m, p, n)} = \binom{2n + 2}{2} \cdot n
%\phi(m / p)$ times $\Ftr_{G(p, p, n)}$.
%\end{cor}

\begin{comment}
\begin{proof}[Proof of Theorem~\ref{Thm: F_W(t) for G(m,p,n)}]
In $G(m, 1, n)$, the term $\mathcal{F}_{G(1, 1, n)}(mt)$ is for factors of the form $(ij^{\xi})$ (so $m$-many options for the $\xi$) and $\mathcal{F}_{G(m,1,1)}(nt)$ is for the $(ii^{\xi})$'s ($n$ options for the $i$'s). The product is a diagonal matrix with sum of weights equal to $0$ and an overcounting argument should give the result.

Similarly, in $G(m, p, n)$, \jbl{something or other}.

%Finally, consider the group $G = G(m, m, n)$.   We can project any reflection factorization in $G$ into $S_n$ in the obvious way.  The projection of any length-$\ell$ generating factorization is a length-$\ell$ connected factorization of the identity in $S_n$; let the number of these be $K_\ell$.  Fix one such factorization $F$; we count its preimage under projection.

%Since the projection of $F$ generates $S_n$, it corresponds to a connected graph; choose a spanning tree and use the
%Hurwitz action to move these factors to the front.  The remaining
%$\ell - n + 1$ factors factor an $n$-cycle, hence they are still a
%connected graph; choose another spanning tree and use the Hurwitz
%action to move its factors to the rear.  Choose the weights of the
%first spanning tree arbitrarily.  (This accounts for the factor $m^{n - 1}$.)
%The reflections in this prefix generate a subgroup of $G$
%isomorphic to $S_n$, so let's just say for convenience that it
%actually is $S_n$.  (One can make this more concrete: there is a unique-up-to-multiplication-by-scalar-matrices diagonal matrix $d$ such that conjugating the entire factorization by $d$ carries the first $n - 1$ factors to be honest transpositions, generating $S_n$ on the nose.)

%Next, we prepare for an inclusion-exclusion argument.  Choose the weights of the middle $\ell - 2n + 2$ factors arbitrarily.  The product of the first $\ell - n + 1$ factors is an element whose projection is an $n$-cycle, and the last $n - 1$ factors also factor the same $n$-cycle.  It is not difficult to show that the weights of the last $n - 1$ factors are uniquely determined by the requirement that $F$ factors the identity in
%$G(m, m, n)$.  [Aside: I think also if you wanted to factor any
%diagonal element in $G$, this would be true, and so we'd get the same count.]
%However, not all such choices give a factorization that generates $G$: in particular, the reflection subgroups of $G$ that contain $S_n$ are exactly those of the form $G(d, d, n)$ for $d \mid m$, and if the middle $\ell - 2n + 2$ factors all lie in some such subgroup then the last $n - 1$ factors will as well.  Therefore the total number of factorizations of $\id$ of length $\ell$ that generate $G$ is
%\[
%K_\ell \cdot m^{n - 1} \cdot \sum_{d \mid m} d^{\ell - 2n + 2} \mu(m / d).
%\]
The generating function result follows immediately.
\end{proof}

\jbl{Here's an argument for elements in $\Symm_n \subset G(m, m, n)$.} 

Let $g \in G = G(m, m, n)$ be an element whose $c$ cycles all have weight $0$ (i.e., a conjugate of a permutation), and let the cycle type be $\lambda$.  The projection of any length-$\ell$ transitive reflection factorization of $g$ into $\Symm_n$ is a length-$\ell$ connected transposition factorization of $\pi(g)$ in $\Symm_n$.  Say the number of these factorizations is $K_\ell$.  Fix one such factorization $F$; we could the number of its preimages $\widetilde{F}$ under the projection.

Since the projection $F$ generates $\Symm_n$, it corresponds to a connected graph.  Contracting the vertices in each cycle to a single vertex, the result must still be connected, and consequently we can choose a spanning tree of the contracted graph.  Each edge in the spanning tree comes from a particular factor in the factorization; use the Hurwitz action to move these $c - 1$ factors to the front of the factorization.  The remaining $\ell - c + 1$ factors factor an $n$-cycle, hence they still form a connected graph; choose a spanning tree and use the Hurwitz action to move its $n - 1$ factors to the end of the factorization.  
Choose the weights of the first $c - 1$ factors in $\widetilde{F}$ arbitrarily, in $m^{c - 1}$ ways.
When taken together with any shortest factorization of $g$, the reflections in this prefix generate a subgroup of $G$
isomorphic to $S_n$, so let's just say for convenience that it
actually is $S_n$.  (One can make this more concrete: there is a unique-up-to-multiplication-by-scalar-matrices diagonal matrix $d$ such that conjugating the entire factorization by $d$ carries $g$ to an element of $\Symm_n$ and carries the first $c - 1$ factors to honest transpositions, generating $S_n$ on the nose.)

Next, we prepare for an inclusion-exclusion argument.  Choose the weights of the middle $\ell - c - n + 2$ factors in $\widetilde{F}$ arbitrarily.  It is not difficult to show that the weights of the last $n - 1$ factors are uniquely determined by these choices and the requirement that $\widetilde{F}$ is a factorization of $g$.
However, not all such choices give a factorization that generates $G$: in particular, the reflection subgroups of $G$ that contain $S_n$ are exactly those of the form $G(d, d, n)$ for $d \mid m$, and if the middle $\ell - c - n + 2$ factors all lie in some such subgroup then the last $n - 1$ factors will as well.  Therefore the total number of factorizations of $g$ of length $\ell$ that generate $G$ is
\[
K_\ell \cdot m^{c - 1} \cdot \sum_{d \mid m} d^{\ell - c - n + 2} \mu(m / d).
\]
It follows immediately that 
\begin{align*}
\mathcal{F}^{\textrm{tr}}_{G(m, m, n)}(g; t)  &= 
  \sum_{\ell \geq 0} \left(K_\ell \cdot m^{c - 1} \cdot \sum_{d \mid
                                  m} d^{\ell - c - n + 2} \mu(m /
                                  d)\right)t^\ell  \\
  &= m^{c - 1} \sum_{d \mid m} d^{2 - c - n} \mu(m / d)  \sum_{\ell
    \geq 0}K_\ell \cdot (dt)^\ell = m^{c - 1} \sum_{d \mid m} d^{2 - c - n} \mu(m / d) \mathcal{F}^{\textrm{tr}}_{\Symm_n}(g; dt)
\end{align*}






%The given factorization $F$ corresponds to a connected graph on vertex set $[n]$ with $2n$ edges.  Choose a spanning tree of this graph, and let $(t_{i_1}, \ldots, t_{i_{n - 1}})$ be the corresponding factors.  There are $m^{n - 1}$ ways to choose a preimage $\widetilde{t}_{i_j}$ for each of the factors in the spanning tree.  The group of diagonal elements in $G(m, 1, n)$ acts by conjugation on the set of all such tuples $(\widetilde{t}_{i_1}, \ldots, \widetilde{t}_{i_{n - 1}})$, and this action is transitive on this set.  Moreover, this action extends to an action on preimages of $F$.  Consequently the total number of factorizations is precisely $m^{n - 1}$ times the number in which we take $\widetilde{t}_{i_j} = t_{i_j}$ to be a permutation matrix.  
%
%The Hurwitz action gives a bijection between preimages of $F$ and preimages of some $F'$ in which the first $n - 1$ factors form a spanning tree, and this is compatible with the previous simplification.  So the remaining factors correspond to a connected graph with $n + 1$ edges and $n$ vertices, whose product is fixed.  The preimages of every leaf-edge in such a graph is forced by the fixed product, and by iteratively removing leaves we are left with the ``core'', which is a graph with two-dimensional cycle space.  {\bf One can show} that in such a graph there are two edges whose weights can be chosen freely, with all other weights determined from these.  Moreover, the two selected weights belong to a subgroup $d \ZZ/m\ZZ$ of $\ZZ/m\ZZ$ (here $d \mid m$) if and only if the weights of all edges do, and this happens if and only if the set of preimages belongs to $G(m/d, m/d, n)$.  It follows immediately that
%\[
%F_{G(m, m, n)}(\id) = K \cdot m^{n - 1} \cdot \sum_{d \mid m} d^2 \cdot \mu(m/d).
%\]
%This is easily seen to agree with Theo's calculations in $D_n$.




\acknowledgements{We thank Gilles Schaeffer for
suggesting we look at transitive factorizations of the identity in
complex reflection groups.}

\end{comment}


\printbibliography



\end{document}


%\bibliographystyle{alpha}
%\bibliography{ref-fac-gen}

\newpage


\section{Generating reflection length}
% \subsection*{The identity}
\begin{conjecture}
In a complex reflection group $G$, one has $\ltr(\id)$ is twice the size of a minimum generating set.
\end{conjecture}
\begin{proof}
Both quantities are obviously additive over direct products, so it suffices to consider the case of irreducible groups.

One inequality is straightforward: if $\{r_1, \ldots, r_k\}$ is a minimum generating set then 
\begin{equation}
\label{eq:dumb factorizations of id}
\id = r_1 \cdot r_1^{-1} \cdot r_2 \cdot r_2^{-1} \cdots r_k \cdot r_k^{-1}
\end{equation}
is a reflection factorization of $\id$ that generates the group.

If $G$ is real, then it follows from \cite[Cor.~1.4]{LR} that every reflection factorization of $\id$ is Hurwitz-equivalent to a factorization of the form \eqref{eq:dumb factorizations of id}.  Since Hurwitz moves preserve the subgroup generated by the factors, we have equality in this case.  \jbl{NB: not uniform because LR is not uniform!}

\theo{Maybe we can use recent work of Wegener and Yahiatene, arxiv:1901.05781, where they (uniformly) show in Lemma~2.3 that for any element $w\in W$ (for \emph{any} Coxeter group W) you can bring any reflection factorization of $w$, via Hurwitz moves, into the form of \eqref{eq:dumb factorizations of id} but for the first $m$ factors where $m=l_S(m)$, the simple reflection length. Since $l_S(\id)=0$, this should be enough for us?

This should probably also cover the case of parabolic Coxeter elements: If $w\in W$ is a parabolic Coxeter element, we can find in its conjugacy class a representative $w'$ such that $l_S(w')=\lR(w')$. Then proceed as above..? The answer would then be $$\ltr(w)=\lR(w)+2(n-\lR(w))=2n-\lR(w).$$} \jbl{I agree}

In $G(m, m, n)$, upon projecting to $\Symm_n$, one needs a set of transpositions that generate $\Symm_n$, so at least $2n - 2$ of them.  However, any connected set of $2n - 2$ reflections in $G(m, m, n)$ that multiply to the identity generate a subgroup isomorphic to $\Symm_n$ \jbl{why?}.  Therefore $2n$ are needed.

For $G(m, p, n)$ with $p < n$, at least one diagonal reflection is required to generate the group; so at least two are required (to get the total weight right while factoring the identity).  At least $2n - 2$ transposition-like reflections are required for connectivity; in $G(m, 1, n)$, two diagonal reflections whose weight is a primitive $m$th root together with a connected set of transposition-like factors does generate the whole group, but for $G(m, p, n)$ with $1 < p < m$ they generate only $G(m/p, 1, n)$ or something like that, so we need the extra two transposition-like factors.

Finally, one should be able to check by brute force in the non-real exceptional groups.  This has been carried out for the groups $G_i$ where $i \in \{4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 24\}$.  Excluding the exceptional real cases
% ($G_{23} = H_3$, $G_{28} = F_4$, $G_{30} = H_4$, G_{35, 36, 37} = E_{6, 7, 8})
, this leaves the following groups to be checked:
\begin{itemize}
\item rank $2$, not well generated: $G_{11}, G_{15}, G_{19}, G_{22}$
\item rank $3$, well generated: $G_{25}$, $G_{26}$, $G_{27}$
\item rank $4$, well generated: $G_{29}$, $G_{32}$
\item rank $4$, not well generated: $G_{31}$
\item rank $5$, well generated: $G_{33}$
\item rank $6$, well generated: $G_{34}$
\end{itemize}
\end{proof}

%\subsection*{Other elements}
More generally, consider the case of arbitrary $w$.  We have in $\Symm_n$ that $\ltr(w) = 2(n - 1) - \lR(w)$.  
\begin{conjecture}
\label{conj:upper bound on transitive reflection length}
For any element $w$ in a complex reflection group $G$,
\[
\ltr(w) \geq 2 (\textrm{minimum size of a generating set}) - \lR(w).
\]
\end{conjecture}
\begin{proof}[Discussion]
{\bf For real reflection groups $W$}, here is a proof after \cite{LR}. Start with a transitive factorization of $w$ of minimum length and bring it via Hurwitz moves to the form \begin{equation}
\label{EQ: LR for w}
w=r_1\cdots r_l\cdot r_{l+1}\cdot r_{l+1}^{-1}\cdots r_{l+k}\cdot r_{l+k}^{-1},
\end{equation}
where $l=\lR(w)$. Since $r_1,\cdots,r_{l+k}$ generate $W$, we have that $l+k\geq$~(minimum size of a generating set). We then have 
\[
\ltr(w)=l+2k=2(l+k)-l\geq 2(\text{minimum size of a generating set})-\lR(w). \qedhere
\]

{\bf In the case that $G$ is a group for which every minimal generating set of reflections has the same size}, a proof is given below as part of the proof of Conjecture~\ref{conj:formula for transitive reflection length}.
\end{proof}


\begin{remark}
It seems like there should be a good general-purpose reason for this to be true.  In the case of well generated groups and elements that lie below some Coxeter element in absolute order, I believe equality holds.  Here are some examples where equality does not hold in the real case:
\begin{itemize}
\item In a dihedral group $D_{2 \times n}$, if $g$ is a rotation of order $m < n$, then any length-$2$ reflection factorization generates a subgroup isomorphic to $D_{2 \times m}$, so $\ltr(g) = 4$.
\item In $B_3$, the examples are $-I$, with $\ltr(-I) = 5$; the diagonal element with eigenvalues $-1, -1, 1$ ($\ltr = 6$); and the element $[(23); (-1, 1, -1)]$ ($\ltr = 5$)
\item In $D_4$, the only example is $-I$, with $\ltr = 6$
\item In $H_3$, the only example is $-I$, with $\ltr = 5$
\end{itemize}
\end{remark}

Let $S$ be the set of elements of minimum reflection length that have a reflection factorization that generates.  (So when $G$ is well-generated, $S$ consists of the quasi-Coxeter elements, while when $G$ is not well-generated it should consist of some elements of reflection length $\rk(G) + 1$ that are products of minimum generating sets.)  Let $d(g, S)$ be the distance from $g$ to the nearest point of $S$ in the Cayley graph of $G$ generated by reflections (i.e., the underlying graph of the Hasse diagram of the reflection order on $G$).  Then 
\[
\ltr(w) \leq d(w, S) + (\textrm{minimum size of a generating set})
\]
since we can write $w = s \cdot g$ for some $s \in S$ and some $g$ with reflection length $d(w, S)$, and concatenating factorizations of $s$ and $g$ gives a reflection factorization of $w$ that generates the group and has the length of the right side.  (However, it is not clear that such a factorization is a minimum-length transitive factorization fo $w$ !)

\begin{conjecture}
\label{conj:formula for transitive reflection length}
With $S$ as above, 
\[
\lR^*(w) = d(w, S) + (\textrm{minimum size of a generating set}).
\]
\end{conjecture}
\begin{proof}[Discussion]
{\bf In the case that $G$ is a group for which every minimal generating set of reflections has the same size}: pick any minimum-length transitive factorization of $w$, and consider a minimal subset of the factors that generates the group; by the hypothesis on $G$, it is actually a minimum generating set.  Bring this minimum generating set in front via Hurwitz moves, and call its product $s$. Now by definition $w=s\cdot g$ with $s\in S$ and $\lR^*(w)=\text{(minimum size of a generating set)}+\lR(g)$, and since $s \in S$ we have $\lR(g)\geq d(w,S)$. 

Under the given hypothesis, this also establishes Conjecture~\ref{conj:upper bound on transitive reflection length}, since all elements of $S$ lie at rank (minimum size of a generating set) in the reflection ordering, and so also $d(w, S) \geq \text{(minimum size of a generating set)} - \lR(w)$.

{\bf In the case that $G$ is a real reflection group and $w\in G$ is a parabolic quasi-Coxeter element, or equivalently (?) it satisfies that $\lR(w)+d(w,S)=(\text{minimum size of a generating set})$}, then the inequality again becomes an equality: We have shown above that for real $G$, we always have $\lR^*(w)\geq 2(\text{minimum size of a generating set})-\lR(w)$. With our assumption, this becomes $$\lR^*(w)\geq (\text{minimum size of a generating set})+d(w,S),$$ which completes the argument (since the opposite inequality is already known).
\end{proof}

\theo{ I am listing here all (?) things we know:
\begin{enumerate}
\item For \emph{all} $W$ and $w\in W$, we have $$\lR^*(w)\leq d(w,S)+(\text{minimum size of a generating set}).$$
\item For all \emph{real} $W$ and $w\in W$, we have $$\lR^*(w)\geq 2(\text{minimum size of a generating set})-\lR(w).$$
\item Whenever \emph{minimum = minimal}, we have $$\lR^*(w)=d(w,S)+(\text{minimum size of a generating set}).$$
\item For real $W$ and $w\in W$ a \emph{parabolic quasi-Coxeter element}, we have $$\lR^*(w)=2(\text{minimum size of a generating set})-\lR(w)=d(w,S)+(\text{minimum size of a generating set}).$$ If moreover, $w$ is a \emph{parabolic Coxeter element} (and $W$ still real), then the proof is uniform by \cite{WY}.
\item No experiments yet for a counter-example of the equality $$\lR^*(w)=d(w,S)+(\text{minimum size of a generating set}).$$
\end{enumerate}}
\jbl{I agree with this.}

\begin{proposition}
If $W$ is a Weyl group, then minimal = minimum.  That is, given a set $X$ of reflections of $W$ that generate $W$, $X$ contains a minimum (size = rank of $W$) set of reflections that generate.
\end{proposition}
\begin{proof}[Proof 1]
We apologize to the reader in advance for this proof.

The group $G_2$ consists of the symmetries of a regular hexagon, with six reflections.  A set of more than $3$ reflections contains two whose fixed lines make an angle of $30^\circ$, and this pair generates the group; the only sets of size $3$ that do not contain two such reflections are the set consisting of the three reflections across the diagonals of the hexagon, and its complement; both of these sets generate a subgroup isomorphic to the symmetric group $\Symm_3$, rather than all of $G_2$.

The group $F_4$ has $24$ reflections.  Of the subsets of size $4$, exactly $2160$ generate the group.  By a brute-force search on Sage, there are no subsets of reflections that generate the whole group but do not contain one of these minimum generating sets.  (And the calculation has been re-confirmed independently by Theo.)

In the group $B_n$, view any set of reflections as a signed graph on $[n]$ (loops allowed).  In order for a set of reflections to generate, the graph must be connected (otherwise it generates a subgroup of a conjugate of $B_k \times B_{n - k}$ for some $k$) and must contain at least one loop (otherwise it generates a subgroup of $D_n$).  Any connected graph with a loop contains a spanning tree with a loop; the subset of reflections corresponding to this subgraph is a minimum generating set for $B_n$.

Otherwise, the group $W$ is simply laced.  By \cite[Lem.\ 5.12]{BGRW}, if $W$ is simply laced, then a set of reflections in $W$ generates $W$ if and only if the roots orthogonal to the reflecting hyperplanes span the whole root lattice (here span means $\ZZ$-span, of course).  By \cite[Thm.\ 4.1]{BalnojanHertling}, if a set of roots generates the root lattice, then it contains a $\ZZ$-basis for the root lattice.  And finally again by \cite[Lem.\ 5.12]{BGRW}, the reflections corresponding to this $\ZZ$-basis form a minimum generating set for $W$.
\end{proof}

\jbl{Remarks: BH is case-by-case.  This result of BGRW is extended to non-simply laced types in \cite{BW}, where the condition is that the roots should span the root lattice and simultaneously the coroots should span the coroot lattice; it was not clear to me how to use this with the BH result.  Also the result (Cor.\ 1.2(b)) in BW is mis-stated, we would have to clarify if we quote it.}

\begin{proof}[Proof 2]
Our proof has two parts: first, we show that if there is a Weyl group $W$ with a minimal but non-minimum generating set of reflections, then there is some (maybe other) Weyl group $W'$ with a minimal generating set of reflections of size $\rk(W') + 1$; second, we show that in every Weyl group $W$, every generating set of size $\rk(W) + 1$ is non-minimal (i.e., contains a proper subset that generates).

For the first part, from among all Weyl groups $W$ that have a minimal generating set $S$ that contains more than $\rk(W)$ reflections, find the minimum rank $n$ that occurs, and among the examples of rank $n$, choose one where the size $|S|$ is as small as possible (while still being larger than $n$).  Choose a reflection $t \in S$, and let $W' = \langle S \smallsetminus t \rangle \subsetneq W$.  We must have $\rk(W') = n$: otherwise, since $|S \smallsetminus t| \geq n > \rk(W')$, we have by the choice of $n$ that $S \smallsetminus t$ contains a proper subset $S'$ that generates $W'$, and then $S' \cup t$ generates $W$, contradicting the minimality of the generating set $S$.  Since $\rk(W') = n$ and $W'$ is generated by $S \smallsetminus t$, we have by the minimality assumption on $|S|$ that $|S \smallsetminus t| = n$ and consequently $|S| = n + 1$, as needed.

For the second part, [blah blah blah circuits and stuff but I have to do the work]
\end{proof}


\begin{remark}
Theo has also checked that in types $H_3$ and $H_4$, every minimal generating set of reflections is minimum.  However, it is not the case for dihedral groups in general!  For example, in the dihedral group of order $2 \cdot 30$, take the reflection through the $x$-axis, the reflection that lies above it at an angle of $2\pi/30$, and the reflection that lies below it at an angle of $-3\pi/30$.  The first two generate a group of order $2 \times 15$, the first and third generate a group of order $2 \times 10$, and the last two generate a group of order $2 \times 5$.  

More generally, we have that ``minimal = minimum'' for the dihedral group of type $I_2(m)$ if and only if $m$ has at most two prime factors; we prove this now.  As discussed in \cite[\S3.2]{LR}, for any three reflections $r_1, r_2, r_3$ we can choose orthogonal roots $\alpha_1, \alpha_2, \alpha_3$ such that the angles between them have measures $\frac{\pi}{m} A_{12}$, $\frac{\pi}{m} A_{13}$, and $\frac{\pi}{m} A_{23}$ where $A_{12}, A_{13}, A_{23}$ are integers in $\{1, \ldots, m - 1\}$ with sum $2m$; moreover, the three reflections generate the whole group if and only if $\gcd(A_{12}, A_{13}, A_{23}) = 1$.   Likewise, it's easy to see that reflections $r_i$ and $r_j$ generate the group if and only if $\gcd(A_{ij}, m) = 1$.  

Suppose first that $m$ is divisible by at most two primes $p$, $q$, and that $A_{12}, A_{13}, A_{23}$ are integers in $\{1, \ldots, m - 1\}$ such that $A_{12} + A_{13} + A_{23} = m$ and $\gcd(A_{12}, A_{13}, A_{23}) = 1$.  From the first equation, if $p$ divides two of the $A_{ij}$ then it divides all three, which contradicts the second equation; likewise for $q$.  But then one of the $A_{ij}$ is divisible by neither $p$ nor $q$ and so is relatively prime to $m$; thus in this case two of the reflections generate.  

On the other hand, suppose that $m$ is divisible by at least three primes; then we can write $m = p \cdot q \cdot r$ where $p, q, r > 1$ are pairwise relatively prime (though not necessarily prime themselves).  By the Chinese Remainder Theorem, we can simultaneously solve the systems of congruences 
\[
\begin{cases}
A_{12} \equiv 0 \pmod p \\
A_{12} \equiv 1 \pmod q \\
A_{12} \equiv 1 \pmod r
\end{cases}
\textrm{ and }
\begin{cases}
A_{13} \equiv 1 \pmod p \\
A_{13} \equiv 0 \pmod q \\
A_{13} \equiv -1 \pmod r
\end{cases}
\]
to produce unique integers $A_{12}, A_{13} \in \{1, \ldots, m - 1\}$, and define $A_{23} = 2m - A_{12} - A_{13}$.  By construction, $\gcd(A_{12}, m) = p$, $\gcd(A_{13}, m) = q$, and $\gcd(A_{23}, m) = r$, so no pair of $r_1, r_2, r_3$ generates the group.  However, the three reflections together do generate, as $\gcd(A_{12}, A_{13}, A_{23}) = \gcd(A_{12}, A_{13}, m) = \gcd(\gcd(A_{12}, m), \gcd(A_{13}, m)) = \gcd(p, q) = 1$.
\end{remark}

\begin{remark}
Similarly, in the complex case, it is not necessarily the case that ``minimal = minimum'', even in the groups $G(m, 1, n)$ and $G(m, m, n)$.  For example, in $G(6, 1, n)$ we can use two diagonal reflections with eigenvalues $-1$ and $\exp(2\pi i/3)$ along with $n - 1$ transpositions, and in $G(6, 6, 3)$ Sage tells me that the following set generates and is minimal:
\[
\left \{
\begin{bmatrix}
1 & & \\ && 1 \\ &1&
\end{bmatrix}, 
\quad
\begin{bmatrix}
1 & & \\ && -1 \\ &-1&
\end{bmatrix}, 
\quad
\begin{bmatrix}
\omega & & \\ &\overline{\omega}& \\ && 1
\end{bmatrix}, 
\quad
\begin{bmatrix}
\overline{\omega} & & \\ &\omega& \\ && 1
\end{bmatrix}, 
\right\},
\]
where $\omega = \exp(2\pi i/6)$.  

In addition, I have done some computer experiments, with the following results:
\begin{itemize}
\item every minimal generating set of reflections is minimum in $G_4$, $G_5$, $G_6$, $G_8$, $G_{12}$, and $G_{13}$;
\item there exist non-minimum minimal generating sets of reflections in $G_{14}$, $G_{17}$, $G_{20}$, $G_{21}$, $G_{24}$, and $G_{27}$; and
\item in $G_7$, $G_9$, $G_{10}$, $G_{16}$, $G_{18}$, $G_{25}$, there are no minimal generating sets of reflections whose size is exactly $1$ larger than the size of a minimum generating set.  (So if there exist non-minimum minimal generating sets of reflections, they must have size at least $2$ more than the size of a minimum generating set.)
\end{itemize} 
I have not checked $G_{11}$, $G_{15}$, $G_{19}$, $G_{22}$, $G_{26}$, or any of the non-real groups of rank $\geq 4$.
\end{remark}


\section{Counting in the infinite family}

\ahm{Include known results for $\mathcal{F}_{G(1,1,n)}(t)$ and $\mathcal{F}_{G(m,1,1)}(t)$}

consider the exponential generating function $\mathcal{F}_W(t):=\sum_{\ell\geq 0}\text{FAC}_W(\ell)\cdot \dfrac{t^\ell}{\ell!}$ where $\text{FAC}_W(\ell)$ is the number of transitive length-$\ell$ reflection factorizations of $\id\in W$. 
\begin{theorem}\label{Thm: F_W(t) for G(m,p,n)}
We have the following two formulas
\begin{align}
\mathcal{F}_{G(m,p,n)}(t) & =\dfrac{1}{(m/p)^{n-1}}\cdot\mathcal{F}_{G(p,p,n)}\big((m/p)\cdot t\big)\cdot\mathcal{F}_{G(m/p,1,1)}(nt) \\
\mathcal{F}_{G(m, m, n)}(t) & = m^{n-1} \sum_{d | m} \mu(m / d) \cdot d^{2 - 2n} \cdot 
\mathcal{F}_{S_n}(d t),
\end{align}
where $\mu$ is the number-theoretic M\"obius function.
%In particular,
%\[
%\mathcal{F}_{G(m,1,n)}(t) =\dfrac{1}{m^{n-1}}\cdot \mathcal{F}_{G(1,1,n)}(mt)\cdot\mathcal{F}_{G(m,1,1)}(nt).
%\]
\end{theorem}
\theo{Maybe get rid of corollary below if we don't have space (and replace with D-Y-Z recursion}
\begin{cor}\label{cor: F_W(id) for G(m,1,n), G(m,m,n)}
For a group $W$ in the infinite family, one has that the number $F_W(\id)$ of minimum-length transitive factorizations of the identity $\id$ is given by
\[
F_{G(m, 1, n)}(\id) = \binom{2n}{2} \cdot n^2 \cdot m^{n - 1} \cdot \phi(m) \cdot {\color{red} n^{n - 3} \cdot (2n - 2)!} =\dfrac{1}{2}\cdot (mn)^{n-1}\cdot \phi(m)\cdot (2n)! \; ;
\]
\[
F_{G(m, m, n)}(\id) = K_{n + 1} \cdot m^{n - 1} \cdot \sum_{d \mid m} d^2 \cdot \mu(m/d) \; ; 
\]
and for $m > p > 1$, $F_{G(m, p, n)}(\id) = \binom{2n + 2}{2} \cdot n \phi(m / p)$ times $F_{G(p, p, n)}(\id)$ \jbl{double-check this}.
\end{cor}

\begin{proof}
In $G(m, 1, n)$, the term $\mathcal{F}_{G(1, 1, n)}(mt)$ is for factors of the form $(ij^{\xi})$ (so $m$-many options for the $\xi$) and $\mathcal{F}_{G(m,1,1)}(nt)$ is for the $(ii^{\xi})$'s ($n$ options for the $i$'s). The product is a diagonal matrix with sum of weights equal to $0$ and an overcounting argument should give the result.

Similarly, in $G(m, p, n)$, \jbl{something or other}.

Finally, consider the group $G = G(m, m, n)$.   We can project any reflection factorization in $G$ into $S_n$ in the obvious way.  The projection of any length-$\ell$ generating factorization is a length-$\ell$ connected factorization of the identity in $S_n$; let the number of these be $K_\ell$.  Fix one such factorization $F$; we count its preimage under projection.

Since the projection of $F$ generates $S_n$, it corresponds to a connected graph; choose a spanning tree and use the
Hurwitz action to move these factors to the front.  The remaining
$\ell - n + 1$ factors factor an $n$-cycle, hence they are still a
connected graph; choose another spanning tree and use the Hurwitz
action to move its factors to the rear.  Choose the weights of the
first spanning tree arbitrarily.  (This accounts for the factor $m^{n - 1}$.)
The reflections in this prefix generate a subgroup of $G$
isomorphic to $S_n$, so let's just say for convenience that it
actually is $S_n$.  (One can make this more concrete: there is a unique-up-to-multiplication-by-scalar-matrices diagonal matrix $d$ such that conjugating the entire factorization by $d$ carries the first $n - 1$ factors to be honest transpositions, generating $S_n$ on the nose.)

Next, we prepare for an inclusion-exclusion argument.  Choose the weights of the middle $\ell - 2n + 2$ factors arbitrarily.  The product of the first $\ell - n + 1$ factors is an element whose projection is an $n$-cycle, and the last $n - 1$ factors also factor the same $n$-cycle.  It is not difficult to show that the weights of the last $n - 1$ factors are uniquely determined by the requirement that $F$ factors the identity in
$G(m, m, n)$.  [Aside: I think also if you wanted to factor any
diagonal element in $G$, this would be true, and so we'd get the same count.]
However, not all such choices give a factorization that generates $G$: in particular, the reflection subgroups of $G$ that contain $S_n$ are exactly those of the form $G(d, d, n)$ for $d \mid m$, and if the middle $\ell - 2n + 2$ factors all lie in some such subgroup then the last $n - 1$ factors will as well.  Therefore the total number of factorizations of $\id$ of length $\ell$ that generate $G$ is
\[
K_\ell \cdot m^{n - 1} \cdot \sum_{d \mid m} d^{\ell - 2n + 2} \mu(m / d).
\]
The generating function result follows immediately.
\end{proof}

%The given factorization $F$ corresponds to a connected graph on vertex set $[n]$ with $2n$ edges.  Choose a spanning tree of this graph, and let $(t_{i_1}, \ldots, t_{i_{n - 1}})$ be the corresponding factors.  There are $m^{n - 1}$ ways to choose a preimage $\widetilde{t}_{i_j}$ for each of the factors in the spanning tree.  The group of diagonal elements in $G(m, 1, n)$ acts by conjugation on the set of all such tuples $(\widetilde{t}_{i_1}, \ldots, \widetilde{t}_{i_{n - 1}})$, and this action is transitive on this set.  Moreover, this action extends to an action on preimages of $F$.  Consequently the total number of factorizations is precisely $m^{n - 1}$ times the number in which we take $\widetilde{t}_{i_j} = t_{i_j}$ to be a permutation matrix.  
%
%The Hurwitz action gives a bijection between preimages of $F$ and preimages of some $F'$ in which the first $n - 1$ factors form a spanning tree, and this is compatible with the previous simplification.  So the remaining factors correspond to a connected graph with $n + 1$ edges and $n$ vertices, whose product is fixed.  The preimages of every leaf-edge in such a graph is forced by the fixed product, and by iteratively removing leaves we are left with the ``core'', which is a graph with two-dimensional cycle space.  {\bf One can show} that in such a graph there are two edges whose weights can be chosen freely, with all other weights determined from these.  Moreover, the two selected weights belong to a subgroup $d \ZZ/m\ZZ$ of $\ZZ/m\ZZ$ (here $d \mid m$) if and only if the weights of all edges do, and this happens if and only if the set of preimages belongs to $G(m/d, m/d, n)$.  It follows immediately that
%\[
%F_{G(m, m, n)}(\id) = K \cdot m^{n - 1} \cdot \sum_{d \mid m} d^2 \cdot \mu(m/d).
%\]
%This is easily seen to agree with Theo's calculations in $D_n$.

Here is data for the leading terms for all the exceptional WG groups of rank $2$:
\begin{itemize}
\item For $G_{4}$:
$216 = 3^2 \cdot 4!$
\item For $G_{5}$:
$864 = 2^2 \cdot 3^2 \cdot 4!$
\item For $G_{6}$:
$864 = 2^2 \cdot 3^2 \cdot 4!$
\item For $G_{8}$:
$576 = 2^3 \cdot 3 \cdot 4!$
\item For $G_{9}$:
$2304 = 2^5 \cdot 3 \cdot 4!$
\item For $G_{10}$:
$3456 = 2^4 \cdot 3^2 \cdot 4!$
\item For $G_{14}$:
$3456 = 2^4 \cdot 3^2 \cdot 4!$
\item For $G_{16}$:
$14400 = 2^3 \cdot 3 \cdot 5^2 \cdot 4!$
\item For $G_{17}$:
$28800 = 2^4 \cdot 3 \cdot 5^2 \cdot 4!$
\item For $G_{18}$:
$43200 = 2^3 \cdot 3^2 \cdot 5^2 \cdot 4!$
\item For $G_{20}$:
$6480 = 2 \cdot 3^3 \cdot 5 \cdot 4!$
\item For $G_{21}$:
$25920 = 2^3 \cdot 3^3 \cdot 5 \cdot 4!$
\end{itemize}
All these numbers are super nice \ldots.  (Of course rank 2 was nice in the last Lewis--Morales paper, too.)  Here are more groups (notice $G_{27}$!):
\begin{itemize}
\item For $G_{7}$ (rank 2, not wg, length 6): $414720 = 2^6 \cdot 3^2 \cdot 6!$
\item For $G_{11}$ (rank 2, not wg, length 6): $4976640 = 2^8 \cdot 3^3 \cdot 6!$
\item For $G_{12}$ (rank 2, not wg, length 6): $92160 = 2^7 \cdot 6!$
\item For $G_{13}$ (rank 2, not wg, length 6): $414720 = 2^6 \cdot 3^2 \cdot 6!$
\item For $G_{15}$ (rank 2, not wg, length 6): $2488320 = 2^7 \cdot 3^3 \cdot 6!$
\item For $G_{19}$ (rank 2, not wg, length 6): $311040000 = 2^7 \cdot 3^3 \cdot 5^3 \cdot 6! $
\item For $G_{22}$ (rank 2, not wg, length 6): $5529600 = 2^9 \cdot 3 \cdot 5 \cdot 6!$
\item For $G_{23} = H_3$, (rank 3, wg, length 6): $172800 = 2^4 \cdot 3 \cdot 5 \cdot 6!$
\item For $G_{24}$ (rank 3, wg, length 6): $282240 = 2^3 \cdot 7^2 \cdot 6!$
\item For $G_{25}$ (rank 3, wg, length 6): $388800 = 2^2 \cdot 3^3 \cdot 5 \cdot 6!$
\item For $G_{26}$ (rank 3, wg, length 6): $933120 = 2^4 \cdot 3^4 \cdot 6!$
\item For $G_{27}$ (rank 3, wg, length 6): $5961600 = 2^3 \cdot 3^2 \cdot 5 \cdot 23 \cdot 6!$
\item For $G_{28} = F_4$, (rank 4, wg, length 8): $87091200 = 2^4\cdot 3^3\cdot 5\cdot 8!$
\item For $G_{29}$ (rank 4, wg, length 8): $1128960000 = 2^5 \cdot 5^3 \cdot 7 \cdot 8!$
\item For $G_{30} = H_4$, (rank 4, wg, length 8): $23962176000 = 2^2
  \cdot 3 \cdot 5^2 \cdot 7 \cdot 283 \cdot 8!$ 
\item For $G_{31}$ (rank 4, not wg, length 10): $12933043200 =2^2 \cdot 3^4 \cdot 11\cdot
  10!$
\item For $G_{32}$ (rank 4, wg, length 8): $22338892800= 2^3 \cdot
  3^6 \cdot 5 \cdot 19\cdot 8!$
\item For $G_{33}$ (rank 5, wg, length 10 ): $1357577625600=2^5 \cdot 3^3 \cdot 433 \cdot  10!$
\item For $G_{34}$ (rank 6, wg, length 12): $1273988354391244800=2^5 \cdot
  3^4 \cdot 7^2 \cdot 43 \cdot 487 \cdot 12!$
\item E6: $2^3 \cdot 3^5 \cdot 137 \cdot 12!$
\item E7: $2^7 \cdot 3^2 \cdot 229 \cdot 373 \cdot 14!$
\item E8: $2^6 \cdot 3^3 \cdot 5 \cdot 31671671 \cdot 16!$
\end{itemize}
This was produced either by stupid brute force or by an inclusion-exclusion over the lattice of reflection subgroups. 

\section{Answers for Weyl groups, and more}
\begin{remark}
Here are the values of $|RGS(G_n)|$ for various well-generated exceptional groups:

Rank 2:
\begin{itemize}
\item For $G_{4}$:
$24$
\item For $G_{5}$:
$48$
\item For $G_{6}$:
$48$
\item For $G_{8}$:
$48$
\item For $G_{9}$:
$96$
\item For $G_{10}$:
$192$
\item For $G_{14}$:
$96$
\item For $G_{16}$:
$960$
\item For $G_{17}$:
$960$
\item For $G_{18}$:
$1920$
\item For $G_{20}$:
$240$
\item For $G_{21}$:
$480$
\end{itemize}
Higher rank
\begin{itemize}
\item For $G_{23} = H_3$): $380$ (ugly!) 
\item For $G_{24}$ (rank 3, wg): $392$
\item For $G_{25}$ (rank 3, wg): $1440$
\item For $G_{26}$ (rank 3, wg): $1728$
\item For $G_{27}$ (rank 3, wg): $6480$
\item For $G_{28} = F_4$, (rank 4, wg): $2160$
\item For $G_{29}$ (rank 4, wg): $28000$
\item For $G_{30} = H_4$, (rank 4, wg): $355800 = 2^3 \cdot 3 \cdot 5^2 \cdot 593$
\item For $G_{32}$ (rank 4, wg): $984960 = 2^7 \cdot 3^4 \cdot 5
  \cdot 19$
\item For $G_{33}$ (rank 5, wg): $748224=2^6 \cdot 3^3 \cdot 433$
\item For $G_{34}$ (rank 6, wg): ???
\end{itemize}
\end{remark}

\subsection{A generalization for real $W$ and possibly all cases}

\jbl{This section needs to be cleaned up.}

There is some evidence that it is a really good idea to replace the factor $|RGS(W)|$ with a \emph{weighted} summation of the reflection generating sets. A good weight would probably be related to the volume of the parallelepiped spanned by the roots $\tau_i$ that correspond to the reflections in such a set. Indeed, for a Weyl group $W$ this volume is constant for all sets $\bm{\tau}$ because they in fact generate the root lattice (as a $\mathbb{Z}$-lattice) (by Baumeister--Wegener \cite{BW}).

\begin{definition}
We write $\vol^2(\bm{\tau})$ for the squared volume of the parallelepiped spanned by a set of roots $\bm{\tau}:=\{\tau_i\}$. It is equal to the determinant of the Gram matrix of $\bm{\tau}$: $$\vol^2(\bm{\tau}):=\det\big( \langle \tau_i,\tau_j\rangle\big)_{ij}.$$ In what follows we will assume all roots $\tau_i$ have norm equal to $\sqrt{2}$ (possibly $\sqrt{e_h}$ for the higher order reflections) and the inner product is the usual one (and the standard Hermitian for the complex case).
\end{definition}

\begin{conjecture}
\label{volume conjecture}
For a well-generated complex reflection group $W$ of rank $n$, the number $F_W(\id)$ of ``transitive" reflection factorizations of the identity $\id\in W$ is given by
\[
F_W(\id):=(2n)!\cdot \sum_{\langle \sigma_{\tau_i}\rangle=W}\dfrac{1}{\vol^2(\bm{\tau})},
\]
where the sum is over all subsets of $n$ reflections $\{\sigma_{\tau_i}\}$ that generate $W$ and $\tau_i$ is a root for $\sigma_{\tau_i}$.
\end{conjecture}
\begin{proof}[Discussion]
{\bf In the case $W$ is a Weyl group}, for every generating set of reflections $\{\sigma_{\tau_i}\}$ and corresponding set of roots $\bm{\tau}$, we have that the connection index satisfies $I(W)=\vol^2(\bm{\tau})$ (again, this is classical, see Baumeister--Wegener). Then the result follows immediately from Thm.~\ref{Thm: Weyl case} in this case.

{\bf For the exceptional groups $G_i$ with $4 \leq i \leq 30$}, this has been checked by computer.  Here are some interesting things that happen: this is a non-trivial sum (for one, the numbers $\vol^2(\bm{\tau})$ that appear are not constant)! For instance in $H_3$, there are two ``generalized" Coxeter classes related by a reflection automorphism, indexed as $(H,3,0)$ and $(H,3,2)$ in the code. Their sets $\bm{\tau}$ have volumes $3+\sqrt{5}$ and $3-\sqrt{5}$. Notice that $$\dfrac{1}{3+\sqrt{5}}+\dfrac{1}{3-\sqrt{5}}=\dfrac{3}{2},$$ while the other quasi-Coxeter class $(H,3,1)$ has volumes equal to $2$. There are $600$ elements in each of $(H,3,0)$ and $(H,3,2)$ and $1080$ elements in $(H,3,1)$. We have that $$600\cdot \dfrac{3}{2}+1080\cdot\dfrac{1}{2}=1440,$$ exactly as the data suggests (we need to divide by $n!=6$ to get $1440/6=240$ as we sum over sets $\{\sigma_{\tau_i}\}$, not tuples).

The situation for $H_4$ is similar, with pairs of volumes like $\dfrac{7\pm\sqrt{5}}{2}$ and $\dfrac{3\pm\sqrt{5}}{2}$ connected by reflection automorphisms, and whose inverses sum to nice numbers (in these cases, $7$ and $3$).

In $G_{16}$, there is an element all of whose reduced reflection factorizations generate the whole group, but that form two different Hurwitz orbits! This is a counterexample in the complex case to the Baumeister et al. (real) theorem for quasi-Coxeter elements. (The two pairs of conjugacy classes of the two reflections (not the hyperplanes!) are different (in one the exponents are $(1/5,4/5)$ vs $(2/5,3/5)$ in the other). So, assuming a fixed set of conjugacy classes for the factorizations, the Hurwitz action is transitive. The class is described in the code trans\_id.sage.)

{\bf For the infinite family $G(m, 1, n)$}, minimum generating sets of reflections are exactly those sets consisting of a spanning tree and a loop such that the weight of the loop is a primitive $m$th root of unity.  (Proof: a minimum-size generating set of reflections in $G(m, 1, n)$ must contain at least $n - 1$ transposition-like reflections (in order to be connected) and at least one diagonal reflection (in order to contain elements outside $G(m, m, n)$).  Any set consisting of a spanning tree of transposition-like reflections (arbitrary weights) and a diagonal reflection whose eigenvalue is a primitive $m$th root of unity will generate; if the diagonal reflection is not a primitive $m$th root, it belongs in some $G(p, 1, n)$ and so all factors do and so they do not generate.) The product of such a set (in any order) is always a Coxeter element (in the appropriate sense), and so by Bessis + Reiner--Ripoll--Stump we might as well conjugate/Hurwitz it so that it has a factorization consisting of a diagonal reflection on the first coordinate (with $\tau_0 = (\sqrt{2}, 0, \ldots, 0)$) and then the simple transpositions (with $\tau_i = (0, \ldots, 0, 1, -1, 0, \ldots, 0)$).  The associated Gram matrix is 
\[
\begin{bmatrix} 
2 & \sqrt{2} & 0 & 0 & \cdots & 0 \\
\sqrt{2} & 2 & -1 & 0 & \cdots & 0 \\
0 & -1 & 2 & -1 & \cdots & 0 \\
0 & 0 & -1 & 2  & \cdots & 0 \\
\vdots & & &  & \ddots & \\
0 & 0 &  \cdots & 0 & -1 & 2
\end{bmatrix}
\]
or something like that (maybe the off-diagonal entries should all be negative?), and it's not terribly hard to show by induction that this has determinant $2$.  Further, applying a Hurwitz move conjugates one reflection by another; at the level of the orthogonal vectors $\tau_i$, this should replace $\tau_i$ with $\tau_i + \kappa \tau_j$ for some complex scalar $\kappa$ (maybe I have to mumble words here about how the reflections are unitary with respect to the inner product and so the image of $\tau_i$ under $r_j$ is still the orthogonal vector to the reflecting hyperplane of $r_j r_i r_{j - 1}$).  In terms of the Gram matrix, this amounts to simultaneously adding $\kappa$ times row $j$ to row $i$ and adding $\overline{\kappa}$ times column $j$ to column $i$, which does not change the determinant.  So in any minimal generating set of reflections for $G(m, 1, n)$, the associated squared volume is $2$.  The number of minimum-size generating sets in $G(m, 1, n)$ is $n^{n - 2} \cdot m^{n - 1} \cdot n\phi(m)$, so indeed, we have
\begin{align*}
\sum_{\langle \sigma_{\tau_i}\rangle=W}\dfrac{1}{\vol^2(\bm\tau)} &=\underbrace{\dfrac{1}{2}}_{\vol^2(\bm\tau)}\cdot \underbrace{m^{n-1}\cdot (n-1)!\cdot\phi(m)}_{\# \text{ of gen'd Cox. elts}}\cdot \underbrace{n^n}_{\text{size of Hurwitz orbits}}\cdot\underbrace{\dfrac{1}{n!}}_{\text{tuples to sets}} \\
&= \dfrac{1}{2}\cdot m^{n-1}\cdot n^{n-1}\cdot\phi(m),
\end{align*}
which exactly agrees with Thm.~\ref{Thm: F_W(t) for G(m,p,n)}.

{\bf For the infinite family $G(m, m, n)$}, minimum generating sets in $G(m, m, n)$ are exactly those sets consisting of a uncyclic graph (i.e., connected, with the same number of edges and vertices) such that in the unique cycle, the sum of the weights in the appropriate cyclic orientation is a primitive $m$th root of unity.  (Proof-ish: A minimum-size generating set of reflections in $G(m, m, n)$ must contain a spanning tree of $n - 1$ transposition-like reflections.  Any such set of reflections generates a subgroup $H \cong S_n$ \jbl{why?}, so when $m > 1$ at least one more reflection is required.  For any pair $\{a, b\} \in \binom{[n]}{2}$, there is a unique reflection $r_{ab}$ in $H$ whose underlying transposition is $(a, b)$.  If we add a reflection $t_{ab}$ whose underlying transposition is $(a, b)$ to our putative generating set, the two reflections $r_{ab}$ and $t_{ab}$ generate a dihedral group of some order $2k$, where $k$ is the order of the roots of unity that are eigenvalues of $r_{ab} t_{ab}$.  In particular, the set generates if and only if $k = m$; the number of choices of $t_{ab}$ is $\phi(m)$.)
The product of such a set (in any order) is always an element with two cycles in which one cycle has weight a primitive $m$th root of unity (and the weight of the other is forced to be the inverse).  When one of the cycles is a $1$-cycle, this is a Coxeter element, but in general not.  However, according to Jiayuan, in all these cases the elements being factored have a single Hurwitz orbit of shortest factorizations. Moreover, again according to Jiayuan, we have in each Hurwitz orbit a factorization in a simple standard form, where up to conjugacy the factorization is like $(12) \cdot (23) \cdot (i- 1 \, i) \cdot (i - 1 \, i)^\omega \cdot (i \, i + 1) \cdots (n - 1 \, n)$, so in particular the unique cycle is a $2$-cycle, and the Grammian for this factorization is
\[
\begin{bmatrix}
2 & -1 & 0 & 0 & 0 & 0 & 0 & 0\\
-1 & 2 & -1 & 0 & 0 & 0 & 0 & 0\\
0 & -1 & 2 & -1 & 1& 0 & 0  & 0\\
0 & 0 & -1 & 2 & -1 - \overline{\omega} & - 1 & 0 & 0\\
0 & 0 & 1 & -1 - \omega & 2 & \omega & 0 & 0\\
0 & 0 & 0 & -1 & \overline{\omega} & 2 & -1  & 0 \\
0 & 0 & 0 & 0 & 0 & -1 & 2 & -1 \\
0 & 0 & 0 & 0 & 0 & 0 & -1 & 2 
\end{bmatrix}.
\]
(This fits very well with Carter's theory and classification of conjugacy classes. The quasi-Coxeter elements in $D_n$ according to Carter all have diagrams like this: 
\begin{figure}[h]
\includegraphics[scale=0.5]{q_cox_Dn.png}
\end{figure}

\noindent )
And one can show \jbl{ok, but it's true} that the determinant of this matrix (and hence the $\vol^2$ associated to all factorizations of this element) is $2 - ( \omega + \overline{\omega})$.


But then also we have the sum $\sum_{\omega: \textrm{prim $m$th root of $1$}} \frac{1}{2 - \omega - \overline{\omega}}$ to deal with.  It seems that if you sum over all non-$1$ $m$th roots of unity in this sum you get $\frac{m^2 - 1}{12}$ (by doing a bunch of small cases, maybe there is a short number theory reason to know this) and so then Moebius inversion gets you what you need, I guess.  (The unicyclic graph counts are not nice but presumably are providing the factor that comes from genus-$1$ factorizations of the identity in $S_n$.) 


\jbl{Below this point needs to be rewritten into a proper proof}

\theo{I think we can avoid the unicyclic graph counts if we use the transitive factorization counts of 2-cycle elements in $S_n$ (which we have after the Hurwitz formulas). As said above all minimal generating sets for $G(m,m,n)$ if taken in a product in \emph{any} order will give an element with two cycles and weights $(\omega,\overline{\omega})$ [[of course, by changing the order you might change the lengths of the two cycles and possibly the $\omega$'s but you still stay in the same family of elements]].

There is {\color{black} probably (in Reiner-Ripoll-Stump ?)} a Galois group action that breaks this family in orbits of size $\phi(m)$ by changing the weights $(\omega,\overline{\omega})$. Then we just need to count all transitive factorizations of any 2-cycle with weights $(e^{2\pi i/m},e^{-2\pi i/m})$ and multiply the result by

\ahm{Need to prove this.}

\begin{equation}
\sum_{\omega:\text{ prim }m\text{th root of 1}}\dfrac{1}{(1-\omega)(1-\overline{\omega})}=\dfrac{1}{12}\sum_{d|m}d^2\mu(m/d),
\end{equation}after the comments above. [[By the way, this is sequence A023023 in oeis which is the 1/12 of A007434.]]

There are $\dfrac{n!}{\alpha\beta}$ elements of cycle type $(\alpha,\beta)$ or $\dfrac{n!}{2(n/2)^2}$ if $\alpha=\beta=n/2$. Each of these elements has $(n-1)\binom{n-2}{\alpha-1}\cdot \alpha^{\alpha}\cdot\beta^{\beta}$ transitive reflection factorizations of length $n$. For each of those, there correspond $m^{n-1}$ ways to lift the reflections and get a 2-cycle in $G(m,m,n)$ with weights $(e^{2\pi i/m},e^{-2\pi i/m})$. {\color{black} Aghhh, is this clear?? Maybe this has to go through the unicyclic graphs after all -but without counting them.}

Putting these all together, we have 
$$
\sum_{\langle \sigma_{\tau_i}\rangle=W}\dfrac{1}{\vol^2(\bm\tau)}=\sum_{k=1}^{n-1}\underbrace{\dfrac{n!}{2\cdot k\cdot(n-k)}}_{\# \text{ of elts }(k,n-k)}\cdot \underbrace{m^{n-1}}_{\#\text{ to lift reflns }}\cdot \underbrace{k^k\cdot (n-k)^{n-k}\cdot (n-1)\cdot \binom{n-2}{k-1,n-k-1}}_{H_0\big((k,n-k)\big)}\cdot \underbrace{\dfrac{1}{12}\sum_{d|m}d^2\mu(m/d)}_{\displaystyle \sum_{\omega:\text{ prim}}\dfrac{1}{2-\omega-\overline{\omega}}}\cdot\dfrac{1}{n!},
$$ 
where the last term $\dfrac{1}{n!}$ is to turn tuples to sets. This expression is equal to 
$$
\dfrac{1}{(2n)!}\cdot K_{n+1}\cdot m^{n-1}\cdot \sum_{d \mid m}d^2\cdot\mu(m/d)
$$ 
by the (exact) same calculation as in the Weyl case of $D_n$. This is exactly what we wanted after Corol.~\ref{cor: F_W(id) for G(m,1,n), G(m,m,n)} and the proof is complete.
}



\end{proof}

\jbl{Here are some leftover comments that did not get incorporated into the proofs above:

Minimum generating sets in $G(m, p, n)$ for $1 < p < m$ consist of minimum generating sets for $G(m, m, n)$ with the addition of a diagonal reflection whose root of unity is primitive for the quotient of $m$th over $p$th roots of unity.

\bigskip

The number of minimum generating sets in $G(m, m, n)$ is a lot messier: something like $m^{n - 1}\phi(m)\cdot \sum_{k = 2}^{n} \frac{(n)_k}{(2 - \delta_{k, 2})} \cdot n^{n - k - 1} $.  (Again this is basically unicyclic graphs.)

}


\begin{remark}
Broue-Corran-Michel \cite{BCM} (see bibliography folder) have recently published an article on ``Cyclotomic root systems and bad primes". There they give analogs of the connection index $I(W)$ for all complex reflection groups. It seems so far that all the volumes $\text{Vol}^2(\bm{\tau})$ that appear are the elements in the Galois orbit of the numbers $I(W)$ of BCM (this should be easy to see for the dihedral groups, check their Lemma~6.9). This suggests that these $\text{Vol}^2(\bm{\tau})$ are nice objects.
\end{remark}

\begin{remark}
The previous Remark also suggests rewriting the formula for $F_W(\id)$ via a possible analog of Weyl's formula ($|W|=I(W)\cdot n!\cdot c_1\cdots c_n$) for complex reflection groups. BCM try to give such an analog (see their Section 8) but do not offer candidates for the $c_i$'s. It might be possible that there is a different such factorization/formula for $|W|$ for every different $\text{Vol}^2(\bm{\tau})$. The advantage then of such a reformulation: $$F_W(\id)=\dfrac{1}{|W|}\cdot \Big( \sum_{\langle \sigma_{\tau_i}\rangle =W}\dfrac{|W|}{\text{Vol}^2(\bm{\tau})} \Big)\cdot (2n)!,$$ is that it fits very well the representation theoretic picture that has the factor $\dfrac{1}{|W|}$ in front and the term $(z-1)^{2n}$ which gives the $(2n)!$ in the end. Then, the polynomials that appear in between might be a weird statistic on the $\bm{\tau}$'s (this is somewhat the case in $S_n$). Of course some grouping would have to happen first as $\text{Vol}^2(\bm{\tau})$ are not always integers; in fact, this grouping should be stronger than the Galois orbit as for example in $H_4$, it happens that $7\not|\ |W|$. Or the statistic might not be integer.

\noindent In any case, it seems that if there is a chance for something this good, the Weyl case should be done first.
\end{remark}


\section{Results in the symmetric group}



\begin{theorem}[Goulden-Jackson, Vakil; Goulden-Jackson-Vainshtein for $\alpha=1^n$]
\label{GJVGJV}
  For $\alpha=(\alpha_1,\ldots,\alpha_m)$,
  \[
H_1(\alpha) = \frac{1}{24} (n+m)! \left(\prod_{i=1}^m
  \frac{\alpha_i^{\alpha_i}}{(\alpha_i-1)!}\right) \left( n^m -
  n^{m-1}  - \sum_{i=2}^m (i-2)! e_i(\alpha) n^{m-i}\right),
\]
where $e_i(\alpha)$ is the elementary symmetric function in the $\alpha$. In particular $H_1(1^n) = \frac{1}{24} (2n)! (n^n - n^{n-1} -
\sum_{i=2}^n \binom{n}{i} (i-2)! n^{n-i})$. 
 \end{theorem}

Bousquet-M\'elou and Schaeffer have this formula for transitive
factorizations, not necessarily using transpositions.

\begin{theorem}[Bousquet-M\'elou--Schaeffer \cite{B-MS}] \label{thm:
    Bousquet-Melou and Schaeffer}
Let $\sigma_0$ be a permutation with cycle type $\alpha$. The number
$\tilde{H}_0(\alpha)$ of $m$-tuples $(\sigma_1,\ldots,\sigma_m)$ of permutations
of size $n$ such that (i) $\sigma_1\cdots \sigma_m = \sigma_0$, (ii)
the group they generate is transitive, (iii) $\sum_{i=0}^m c(\sigma_i)
= n(m-1)+2$ is 
\[
m \cdot \frac{(m-1)n-1)!}{((m-1)n - c(\sigma_0)+2)!} \prod_{i}
\alpha_i \binom{m\alpha_i-1}{\alpha_i},
\]
in particular $\tilde{H}_0(1^n) = m(m-1)^{n} \frac{((m-1)n-1)!}{((m-2)n+2)!}$.
\end{theorem}

The result above is a polynomial in $m$ and the leading coefficient is
the Hurwitz formula for transpositions.
 
\ahm{Can we test an analogue of this formula for the identity?}

\theo{Mostly unsuccessful attempts in \S\ref{sec: W-analog for B-M,S}.} 

\subsection{Proper, monotone, inequivalent factorizations}

Following notation from Berkolaiko--Irving, let $F_{\alpha,g}(r)$ be
the number of transitive genus-$g$ factorizations of length $r$ of
some $\phi$ of cycle type $\alpha$. Let $P_{\alpha,g}(r)$ be these
factorizations that are proper, i.e. with no identity factor. Then
\[
F_{\alpha,g}(r) = \sum_k \binom{r}{k} P_{\alpha,g}(k).
\]

\theo{So, do we have for instance $\tilde{H}_0(\alpha)=F_{\alpha,0}$ with $\tilde{H}$ the BM-S function above?}

Let $\tilde{C}_{\alpha,g}(r)$ be the number of inequivalent (i.e., up
to commutation of factors) genus-$g$ transitive factorizations of length $r$. Let
$M_{\alpha,g}$ be the number of genus-$g$ monotone (also called primitive)
transitive factorizations of some $\pi \in \mathcal{C}_{\alpha}$. 

\begin{theorem}[Berkolaiko-Irving] \label{thm: Berkolaiko Irving}
\[
(-1)^{|\alpha|+\ell(\alpha)} M_{\alpha,g} = \sum_{r\geq 0} (-1)^r
\tilde{C}_{\alpha,g} (r) = \sum_{r \geq 0} (-1)^r P_{\alpha,g}(r) = F_{\alpha,g}(-1).
\]
\end{theorem}

\theo{The polynomial $F_{\alpha,g}(r)$ looks a bit like the zeta polynomial of some poset. Maybe especially for $g=0$ and in relation to Joel's poset (it isn't \emph{exactly} one though). If it were a zeta polynomial, $\mathcal{Z}(-1)$ would give us the Moebius function of the poset. Is there a similar interpretation here?}

As a corollary of Theorem~\ref{thm:
    Bousquet-Melou and Schaeffer} and \ref{thm: Berkolaiko Irving} we obtain the following result first proved by Goulden, Guay-Paquet and Novak

\begin{corollary}[Goulden, Guay-Paquet, Novak]
For $\alpha=(\alpha_1,\ldots,\alpha_m)$ we have that
\[
M_{\alpha,0} = (2n+1)^{(m-3)} \prod_{i=1}^m \alpha_i \binom{2\alpha_i}{\alpha_i},
\]
where $(x)^{(k)}=x(x+1)\cdots (x+k-1)$. In particular $M_{1^n,0}=2^n
(2n+1)^{(n-3)}$ and $M_{n,0}=\frac{1}{n+1}\binom{2n}{n}$.
\end{corollary}





\begin{remark}[\cite{AMMHN}]
One can use Jucys-Murphy elements $J_i = (1,i)+(2,i)+\cdots +(i-1,i)$ to relate  factorizations
with monotone factorizations.
\[
(1+t J_1)(1+tJ_2)\cdots (1+t J_n) = \sum_{\sigma \in \mathfrak{S}_n}
t^{n-c(\sigma)} \sigma,
\]
where 
\[
(1-tJ_1)^{-1} \cdots (1-t J_n)^{-1}
\]
generates monotone factorizations, since $J_1^{a_1} J_2^{a_2}\cdots
J_n^{a_n}$ generates monotone factorizations with $\sum_i a_i$ factors. Thus the generating
function of monotone factorizations is $(\sum_{\sigma \in
  \mathfrak{S}_n} (-t)^{n-c(\sigma)} \sigma)^{-1}$. 
\end{remark}




\subsection{An observation about divisibility}
\label{sec:divisibility}
If $w$ is an element of $S_n$ of cycle type $\alpha$, then the number of shortest transposition factorizations (not transitive/connected/generating) of $w$ is 
\[
\binom{n - m}{\alpha_1 - 1; \dots; \alpha_m - 1}\cdot \prod_i \alpha_i^{\alpha_i - 2}.
\]
Comparing with Theorem~\ref{thm:S_n genus 0}, we have that the ratio of shortest transitive factorizations to shortest factorizations is
\begin{equation}
\frac{(n + m - 2)!}{(n - m)!} \cdot  n^{m - 3} \cdot \prod_i \alpha_i ^2.\label{EQ: ration S_n}
\end{equation}
\ahm{Is this true for any length not just shortest?}

This is always an integer (obvious for $m \geq 3$; for $m = 2$ you have an available factor ``$n$" in the first factorial to cancel the $n^{-1}$; for $m = 1$ you have miraculous cancellation because $\alpha_1 = n$, though of course in that case the two sets of factorizations are the same).  I did a bunch of testing in other groups (dihedral for $m < 8$, $G(m, 1, 2)$ for $m < 8$, $B_3$, $G(3, 1, 3)$, $D_4$, $H_3$, exceptional CRGs of rank 3, $G_4$, $G_5$, $G_6$, $G_{14}$) and it seems to be always true for elements that lie below a Coxeter element have this property.  

In type B (see Section~\ref{sec:non-identity elements}), an element in conjugacy class $(\lambda, \mu)$ is a parabolic Coxeter element exactly when $\ell(\mu) \leq 1$ is the case of a parabolic Coxeter element; these have the property that their number of shortest (not transitive) reflection factorizations is easy to count, and it seems likely \jbl{check this!!!} that the same integer divisibility we see in type A happens in this case.  

However, for elements that are not parabolic Coxeter, the divisibility can fail.  In particular, take the Coxeter element of type $D_3$ inside the group $B_3$ (that is, an element in conjugacy class $(\varnothing, 21)$), of reflection length $3$,  it has $12$ factorizations using one transposition-like and two diagonal reflections and $16$ factorizations using three transposition-like and no diagonal reflections, for a total of $28$; but it has $1440$ shortest (length-$5$) factorizations that generate $B_3$, and $28 \nmid 1440$.

\begin{conjecture}
If $W$ is a (well generated?) complex reflection group and $w$ is a parabolic (quasi?-)Coxeter element, then the ratio of the number of shortest transitive reflection factorizations of $w$ to the number of shortest non-transitive reflection factorizations of $w$ is an integer.
\end{conjecture}





Here is an attempt to generalize the above for all (well-generated) complex reflection groups:

\begin{conjecture}
\label{general complex conj}
If $W$ is a well-generated complex reflection group, $g$ a parabolic quasi-Coxeter element, and $RGS(W,g)$ is defined as above, then the ratio $F_W(g)/G_W(g)$ of shortest transitive to (plain) shortest reflection factorizations of $g$ is given by:
$$\dfrac{F_W(g)}{G_W(g)}=\dfrac{\lR^*(g)!}{\lR(g)!}\cdot \sum_{\{\sigma_{\tau_i}\}\in RGS(W,g)}\dfrac{\op{GD}(\bm{\tau}_g)}{\op{GD}(\bm{\tau}\cup\bm{\tau}_g)},$$ 
where $GD$ denotes the Grammian determinant for a set of vectors (previously written as $\vol^2$) and $\bm{\tau}$ is the set of roots (with length $\sqrt{2}$) that correspond to the reflections in any relative generating set from $RGS(W,g)$ and $\bm{\tau}_g$ are the roots that correspond to any reduced reflection factorization of $g$.
\end{conjecture}
\theo{At least over $\RR$ (and via the $\vol^2$ interpretation) it is not difficult to see that the ratio $GD(\bm{\tau}_g)/GD(\bm\tau\cup\bm{\tau}_g)$ does not depend on the choice of $\bm{\tau}_g$. In particular, we can choose any vectors that span the moved space of $g$; they don't have to be roots. I don't see how else to phrase that ratio though as a statistic on $\bm{\tau}$.}
\begin{proof}[Discussion]
When $g$ is the identity in $W$, the above conjectures agree with Thm.~\ref{Thm: Weyl case} and Conj.~\ref{volume conjecture} respectively.

For the symmetric group, it is easy to check. Start with an element $g\in S_n$ of cycle type $\alpha=(\alpha_1,\cdots,\alpha_m)$. The set $RGS(S_n,g)$ essentially consists of weighted trees on the $m$ cycles of $g$ (indeed, each transitive set $S\cup\{g\}$ must be connected). To count their multiplicity notice that between two cycles $\alpha_i$ and $\alpha_j$ we can bring $\alpha_i\cdot\alpha_j$ edges. That is, each tree $T$ on $[m]$ is weighted by $$\prod_{i=1}^m \alpha_i^{\deg(T_i)},$$ where $\deg(T_i)$ denotes the degree of the vertex $i$ of the tree $T$. Now the weighted Matrix-Tree theorem (the classical one, not the one by Chapuy-Douvropoulos) implies that $$\sum_{T\text{ a tree on }[m]}\prod_{i=1}^n\alpha_i^{\deg(T_i)}=\alpha_1\cdots \alpha_m\cdot (\alpha_1+\cdots+\alpha_m)^{m-2}=\big(\prod\alpha_i\big)\cdot n^{m-2}.$$ Now, for a reducible reflection group $W=W_1\times\cdots \times W_s$, we will have $I(W)=I(W_1)\cdots I(W_s)$. In our case this means that $$I(W_g)=I(S_{\alpha_1})\cdots I(S_{\alpha_m})=\alpha_1\cdots \alpha_m,$$ which along with $I(S_n)=n$ completes the argument after \eqref{EQ: ration S_n}.  
\end{proof}

\theo{
This has been checked for all Weyl groups of rank $\leq 6$ and might not be too hard to prove for $B_n$ and $D_n$. We could probably compute $E_7$ and $E_8$ in a better computer. \sout{It is unclear what to try for the complex groups (we'd want some statistic of $S$ to replace the whole quotient $\dfrac{I(W_g)}{I(W)}$; we should check if the one for Conj.~\ref{volume conjecture} works).}


There \emph{might} be some relation also with the recent work \cite{ASV} where the authors calculate the volumes of those sub-polytopes of the permutahedron that are the fixed sets of some element $g\in S_n$. In particular, the term $n^{m-2}$ appears in their formula too, which is however not \emph{exactly} the same as \eqref{EQ: ration S_n}. [[Also, the topology of the permutahedron is not exactly compatible with the topology of the transportation polytope (if not anything else, their dimensions are very different) so I am not sure if there is really something there]].

\ahm{Would it be more related to look at elements of the
  transportation polytope fixed by $g \in S_n$?}

It is also unclear what to do with non parabolic-quasi-Coxeter elements $g$. For those elements, there is no set $S$ of $\rank(W)-\lR(w)$ elements such that $S\cup\{g\}$ is \emph{transitive}. Moreover, even if we only look at the ratio between transitive factorizations and a \emph{single} Hurwitz orbit of reduced factorizations, sometimes it is not an integer! (for instance in $F_4$; it would be nice to get a counter example in $D_n$; perhaps it remains true for all classes in $B_n$).
}


\section{Counting factorizations of other elements}
\label{sec:non-identity elements}
Just the leading terms here. 

%In $B_n$, conjugacy classes are indexed by pairs $(\lambda, \mu)$ of partitions of total size $n$: $\lambda$ gives the cycle type of the cycles of weight $0$, and $\mu$ gives the cycle type of the cycles of weight $1$.  Elements are parabolic Coxeter elements (i.e., they lie below a Coxeter element in the reflection order, i.e., they are noncrossing) if $\ell(\mu) \leq 1$.  What appears to happen is this:
%\[
%H^B_0(\lambda, \varnothing) = \binom{n + \ell(\lambda)}{2} \cdot n^2 \cdot 2^{\ell(\lambda) - 1} \cdot H^A_0(\lambda)
%\]
%and
%\[
%H^B_0(\lambda, \langle k\rangle) = (n + \ell(\lambda)) \cdot n \cdot 2^{\ell(\lambda)} \cdot H^A_0(\lambda + k)
%\]
%where $\lambda + k$ means ``add a part of size $k$ to $\lambda$''.  I think it's not too hard to find this believable, based on the earlier stories and what goes on for the reflection length.  With somewhat less evidence, it also seems that $H^B_0(\lambda, \mu)$ actually depends only on $\lambda + \mu$ and the parity of $\ell(\mu)$ (i.e., whether the element belongs to $D_n$ or not).
%
%One might be able to tell a similar story in $G(m, 1, n)$, where one relevant question will be whether the weight of the element generates the full cyclic group (i.e., whether it's a primitive root mod $m$) or not: the answer to that question determines how many diagonal reflections are needed in a shortest transitive factorization.

In $B_n$, conjugacy classes are indexed by pairs $(\lambda, \mu)$ of partitions of total size $n$: $\lambda$ gives the cycle type of the cycles of weight $0$, and $\mu$ gives the cycle type of the cycles of weight $1$.  The reflection length of such an element is $n - \ell(\lambda)$; the number of minimum length reflection factorizations (not transitive ones) is actually kind of tricky, because you have a different flavor of factorizations for each matching on the parts of $\mu$.  The transitive reflection length of these elements is 
\[
\ell_{B_n}^*(\lambda, \mu) = n - 1 + \ell(\lambda) + \ell(\mu) + \one_{\ell(\mu) \textrm{ is even}},
\]
for the following reason: the projection of such an element into $S_n$ has cycle type $\lambda \cup \mu$ and so has transitive reflection length $n - 2 + \ell(\lambda) + \ell(\mu)$, and at least one sign-change must be present.  Moreover, \jbl{one can show} that transitive factorizations exist with this many factors when $\ell(\mu)$ is odd; when $\ell(\mu)$ is even, they do not because the total sign is positive, and so a second diagonal factor is required, and again \jbl{one can show} that then factorizations exist.

Moreover, one can refine the preceding argument into a counting argument.  First consider the case that $\ell(\mu)$ is odd.  To build a factorization, start with a connected transposition factorization in $S_n$ of the projection (selected in $H^A_0(\lambda \cup \mu)$ ways).  Choose one of $n - 1 + \ell(\lambda) + \ell(\mu)$ positions to put the diagonal reflection and choose one of $n$ diagonal reflections it could be.  From the transposition-like factors, roughly speaking the following thing should happen: you can choose the signs on all but $n$ of them freely, as long as the remaining $n$ are connected; and then those $n$ are forced by the need to get the product right and generate the whole group. \jbl{Obviously, there are details to be worked out; at least the following formula is true in $B_3$.}  
I believe this produces the following result:
\[
H^B_0(\lambda, \mu) = (n - 1 + \ell(\lambda) + \ell(\mu)) \cdot n \cdot 2^{\ell(\lambda) + \ell(\mu) - 1} \cdot H^A_0(\lambda \cup \mu).
\]
On the other hand, if $\ell(\mu)$ is even, we need to choose positions for two sign-changes instead of one, and so we get 
\[
H^B_0(\lambda, \mu) = \binom{n + \ell(\lambda) + \ell(\mu)}{2} \cdot n^2 \cdot 2^{\ell(\lambda) + \ell(\mu) - 1} \cdot H^A_0(\lambda \cup \mu)
\]
in that case.

In $G(m, 1, n)$, precisely the same story carries over; the distinction between $\ell(\mu)$ even versus odd should become the question of whether the weight of the element is a primitive root or not, i.e., whether the element belongs to any subgroup $G(m, p, n)$ with $p > 1$.  If the weight of $w$ is a primitive root ($w$ does not belong to any such subgroup), we have $\ell_{(m, 1, n)}^*(w) = 1 + \ell_A^*(\pi(w))$, while if the weight is not a primitive root (so $w$ belongs to some $G(m, p, n)$ with $p > 1$), we need two diagonal reflections and we get $\ell_{(m, 1, n)}^*(w) = 2 + \ell_A^*(\pi(w))$.  And this should lift to a counting argument in a similar way; I would expect formulas like 
\[
H^{(m, 1, n)}_0(w) = \begin{cases}
\overbrace{\ell_{(m, 1, n)}^*(w)}^{\textrm{diag location}} \cdot \overbrace{n}^{\textrm{which diag}} \cdot \overbrace{H^A_0(\pi(w))}^{\textrm{the transps}} \cdot \overbrace{m^{\ell_{(m, 1, n)}^*(w) - n}}^{\textrm{weights of transps}} & w \not \in G(m, p, n) \textrm{ for any } p > 1, \\[12pt]
\underbrace{\binom{\ell_{(m, 1, n)}^*(w)}{2}}_{\textrm{diag location}} \cdot \underbrace{n^2 \cdot (\textrm{a n.t. factor})}_{\textrm{which diag}} \cdot \underbrace{H^A_0(\pi(w))}_{\textrm{the transps}} \cdot \underbrace{m^{\ell_{(m, 1, n)}^*(w) - n}}_{\textrm{weights of transps}} & \textrm{o.w.}
\end{cases}
\]
but I have not verified this in any calculations yet.


I think that a similar thing could be done in type D, but it becomes a hassle; and in general even the formula for $\lR(w)$ is theoretically problematic for $G(m, p, n)$ with arbitrary parameters.  (To be precise: it is the maximum value over the set partitions of the cycles of some quantity; and actually computing this maximum is NP-hard.  I might be overstating how much of an impediment this is in practice, since we could say magic words like ``let $\Pi$ be a set partition of the cycles that maximizes blah blah blah'', but the point is there is some genuinely nontrivial structure here, and it seems like there is probably also the same genuinely nontrivial kind structure in the value of $\lR^*(w)$ for $G(m, p, n)$.)

\section{Approaches towards a uniform proof of Thm.~\ref{Thm: Weyl case} (for Weyl groups)}

Here are some (with various degrees of speculation) ideas towards a uniform proof:

\subsection{Requiring some non-trivial recursion on $F_W(\id)$}
\label{sec: uniform approached: recursion}

Deligne (after Tits and Zagier) in the '70s and Reading independently in '08 \cite{Reading} gave a recursion to count minimal (transitive) reflection factorizations of the Coxeter element; i.e. the number $F_W(c)=h^nn!/|W|$. It states that $$F_W(c)=\dfrac{h}{2}\cdot\sum_{s\in S}F_{W\langle s\rangle}(c'),$$ where $W_{\langle s\rangle}$ is the parabolic subgroup of $W$ generated by the simple reflections $S\setminus\{s\}$ and $c'$ one of its Coxeter elements. It has a uniform proof by enumerating factorizations with respect to the last reflections and grouping those last reflections in their $c$-orbits.

It might be possible for a similar recursion to exist for $F_W(\id)$. Of course we can count tuples with respect to the last reflection, but what we get is $$F_W(\id)=\dfrac{hn}{2}\cdot F_W(t),$$ where $t$ is any fixed reflection of $W$. This is clear, since $W$ has $hn/2$ reflections ($W$ is assumed Weyl) and since we can conjugate the whole factorization by some element $w\in W$ to change the last reflection to $t$ \jbl{Only in the oddly laced case, this doesn't work for $B_n$}. However, it is not very useful: it does not get us into any parabolic subgroup. \theo{Any ideas?} \jbl{In the recurrences above, both the group and the element being factored change.  If you amp up the recurrence to try to take both into account, you end up with something like the poset from before.  But I don't know how useful this really is; in particular, you don't have to stay in parabolic subgroups, right?  (E.g.\ $\begin{bmatrix} -1 & \\ & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & \\ & -1 \end{bmatrix} \cdot \begin{bmatrix} & 1 \\ 1 & \end{bmatrix} \cdot \begin{bmatrix} & -1 \\ -1 & \end{bmatrix}$ or whatever.)}

\subsection*{and comparing it with the Burman recursion}

After work of Burman et al. in \cite{BPT}, we have that \begin{equation}h^n=\sum_{\bm \tau\in\CC\text{-bases}(W)}\vol^2(\bm\tau),\label{EQ: Burman-recursion-I}\end{equation} where $\bm\tau$ is any \emph{unordered} set of roots that is a $\CC$-basis of the ambient space $V$. In fact, the stronger \begin{equation}
(h+t)^n=\sum_{\bm\tau \in\CC\text{-ind.}(W)}\vol^2(\bm\tau)\cdot t^{n-|\bm\tau|},\label{EQ: Burman-recursion-II}
\end{equation} where now the sum is over all $\CC$-independent subsets of roots $\bm\tau$ and $|\bm\tau|$ is the size of the set $\bm\tau$.

This last equation is a combination of \cite[Corol.~2.4]{BPT} and the fact that the $W$-Laplacian matrix (defined as $L_W:=\sum_{\tau\in \mathcal{R}}\big(\mathbf{\id}_n-\rho_V(\tau)\big)$ has all eigenvalues equal to $h$ (which itself is a standard counting involving $|\mathcal{R}|+|\mathcal{R}^*|=hn$).

In a Weyl group, the number $\vol^2(\bm\tau)$ depends only on the \emph{reflection} subgroup $W'$ generated by $\bm\tau$ and equals the connection index $I(W')$. Every subset $\bm\tau$ of roots that is a $\CC$-basis of $V$ generates a maximal rank reflection subgroup of $W$. Combining these, we can rewrite the two equations above as
\begin{equation}
h^n=\sum_{W'\leq_{\max} W}|RGS(W')|\cdot I(W'),\label{EQ: Burman-recursion-RGS-I}
\end{equation}where $W'$ is a maximal-rank reflection subgroup of $W$, and
\begin{equation}
(h+t)^n=\sum_{W'\leq W}|RGS(W')|\cdot I(W')\cdot t^{n-\rank(W')},\label{EQ: Burman-recursion-RGS-II}
\end{equation}where $W'$ is \emph{any} reflection subgroup of $W$.

To use these recursions to prove Thm.~\ref{Thm: Weyl case}, we would need to find a \emph{uniform} proof that 
\begin{equation}
\sum_{W'\leq_{\max}W}F_{W'}(\id)\cdot I(W')^2=h^n\cdot (2n)!,
\label{EQ: Burman-recursion-F_W(id)-I}
\end{equation}
or the more general
\begin{equation}
\sum_{W'\leq W}F_{W'}(\id)\cdot I(W')^2\cdot\dfrac{t^{n-\rank(W')}}{(2\cdot\rank(W'))^2}=(h+t)^n.
\label{EQ: Burman-recursion-F_W(id)-II}
\end{equation} Obviously the first equation looks easier. There is a caveat though: to do the base case of the induction uniformly after proving \eqref{EQ: Burman-recursion-F_W(id)-I} we would need to show \emph{uniformly} that every reflection group has a maximal rank reflection subgroup of type $A$. This might be doable by the Borel-de Siebenthal algorithm, but I'm not sure. Of course, any reflection group (but for $A_1$) has smaller rank reflection subgroups, so this wouldn't be an issue for \eqref{EQ: Burman-recursion-F_W(id)-II}.


\subsection*{or comparing it with a possible De-Concini \& Procesi-like recursion}Assuming a nice recursion for $F_W(\id)$ is found, we would need an equivalent one for $|RGS(W)|$. De-Concini and Procesi give a uniform recursion for calculating the related numbers $d(W)$ of $\CC$-bases of the root system \cite[\S~2.4]{DeCP}, which involves the maximal \emph{parabolic} subgroups of $W$. [[The relation is that $|RGS(W)|$ counts $\ZZ$-bases of the root system (and simultaneously of the coroot system ?) while $d(W)$ counts $\CC$-bases]]. Their recursion:
$$d(W)=\dfrac{1}{2n}\sum_{i=1}^n\Big( [W:W_i]\cdot |R-R_i|\cdot d(W_i)\Big),$$where $W_i$ is the parabolic subgroup that corresponds to removing the $i$-th simple of $W$ and $R$ and $R_i$ are the sets of reflections of $W$ and $W_i$ respectively. 

\subsection{Proving a form that is more compatible with representation theory}
\label{sec: uniform weyl rep theory}

Weyl's formula for the size of crystallographic reflection groups $W$ of rank $n$ states   that $$|W|=I(W)\cdot n! \cdot c_1\cdots c_n,$$ where the $c_i$'s are the coefficients that express the longest root $\tilde{\alpha}$ as a sum of simple roots. Their product is related to the volume of a parallelepiped that is important in the proof (see Humphreys' book, \S4.9). Using this theorem of Weyl, we can rewrite Thm.~\ref{Thm: Weyl case} as $$F_W(\id)=\dfrac{1}{|W|}\cdot \Big( \prod_{i=1}^n c_i\Big) \cdot |RGT(W)|\cdot (2n)!,$$ where $RGT(W)$ denotes the reflection generating \emph{tuples} for $W$ (i.e. $|RGT(W)|= n!\cdot|RGS(W)|$).

This is much more compatible with representation theory. In particular, the number $\displaystyle\Big(\prod_{i=1}^nc_i\Big)\cdot |RGT(W)|$ should be the evaluation $\Phi(1)$ of these polynomials $\Phi$ that appear after the Frobenius lemma (and inclusion-exclusion).

\theo{This might be better, but I'm not sure. It is a bit reminiscent of the zonotope of the root system, but it's not the same: you don't get all tuples of roots that are $\CC$-bases but only those that are in fact a $\ZZ$-basis for the root lattice.} 

\subsection{Interpreting $I(W)$ as some sort of overcounting}

The connection index is usually defined as the index $[\mathcal{P}:\mathcal{Q}]$ of the root lattice $\mathcal{Q}$ inside the weight lattice $\mathcal{P}$ of a Weyl group $W$. In that sense $I(W)$ is the order of the \emph{group} $\mathcal{P}/\mathcal{Q}$. 

Now this group appears in many places and we may hope that some realization of it somehow knows certain symmetries that appear in the enumeration (so that it can give an overcounting argument). The group structure is important. For instance in $D_n$, while the connection index is always $4$, the group $\mathcal{P}/\mathcal{Q}$ is cyclic only for $D_4$ (and equal to $C_2\times C_2$ for $D_n$, $n\geq 5$).

The group $\mathcal{P}/\mathcal{Q}$ is also the center of the Lie group \theo{ no idea how this could be useful!} and it is (almost!) also the \emph{symmetry group} of the affine Dynkin diagram. This is better and hopefully the next interpretation brings it even closer to our objects:

\begin{proposition}\cite[Lemma~1,p.~15]{Sawin}\newline
If we write $\alpha_i$ for the simple roots of a Weyl group $W$ and $\theta$ for its highest root, and if $c_i$ are the coefficients $\theta=\sum c_i\alpha_i$, then for the $\alpha_i$'s with $c_i=1$, there is a \emph{unique} $g_i\in W$ that sends the standard basis $\{\alpha_i\}$ to the basis $\{\alpha_j\}_{j\neq i}\cup\{-\theta\}$.
\end{proposition}
\begin{proof}[Discussion]
I believe it turns out that the group $\mathcal{P}/\mathcal{Q}$ is isomorphic to the subgroup of $W$ which consists precisely of these $g_i$ along with the identity element (it is not a priori clear that the $g_i$'s with the identity form a group). \theo{In fact, it is remarkable that for the symmetric group, this is just the cyclic group generated by some long cycle! (which long cycle depends on the choice of simple roots, 12,23,34, etc. gives (123..n).)} In this way, there is a nice realization of $\mathcal{P}/\mathcal{Q}$ \emph{inside} $W$, one that also acts on some bases.

It is known that the $\alpha_i$'s with $c_i=1$ form the orbit of the vertex corresponding to $-\theta$ in the affine dynkin diagram under its group of symmetries. I am not sure if the previous paragraph appears explicitly in the literature but Nathan Williams agrees it's true.

Still, this isn't yet too hopeful: For one we cannot map an arbitrary Z-basis of the root lattice to the standard one (the angles won't match). Then, I'm not sure if this group $\mathcal{P}/\mathcal{Q}\hookrightarrow W$ acts meaningfully on all these bases... (i.e.  $\theta$ can't always be the highest root \theo{right?}). Even if it does, what is our overcounting?
\end{proof}
  


\section{On possible polytopal/geometric interpretations of the functions $\mathcal{F}_W(t)$}

\theo{The exposition here isn't meant for the actual paper; it's very conversational, but  I though it would  be too psychedelic if everything was in olive}

The exponential generating functions $\mathcal{F}_W(t)$ can be given via the Frobenius lemma and inclusion-exclusion in the poset of reflection subgroups of $W$. Some (easy) representation theory and combinatorics show that they always have the form $$\mathcal{F}_W(t)=\dfrac{1}{|W|}\cdot\Phi_W(e^t)\cdot (e^t-1)^{2n}\cdot\dfrac{1}{e^{t|\mathcal{R}^*|}},$$ where $\Phi_W$ is a \emph{monic} polynomial in $\ZZ[e^t]$ with degree $hn-2n$ (this is the only representation theoretic part; it involves the bounds $-|\mathcal{R}^*|\leq \widetilde{\chi}(\mathcal{R})\leq |\mathcal{R}|$ which translate to the statement about the monicity and the degree after writing down the Frobenius lemma).

In the case of the symmetric group $G(1,1,n)$, the polynomial $\Phi_{G(1,1,n)}$ is equal to the $h$-polynomial of the (central) transportation polytope $T_{n,n-1}$. \theo{Disclaimer ;) : This has been proven by comparing a recursion due to Pak \cite{Pak} on the polytopes side with a recursion due to Dubrovin-Yang-Zagier \cite{DYZ} on the Hurwitz numbers side -thanks to a suggestion of Baptiste Louf. This theorem has a conjectural generalization for arbitrary classes $\lambda$ (i.e. not just $\lambda=1^n$) due to Theo, which has led to a work in progress, possibly with Baptiste and Guillaume.} This naturally suggests:

\begin{question}
For a given (Weyl ?) reflection group $W$, is there a polytope $T_W$ that encodes the polynomial $\Phi_W$ as its $h$- or $h^*$-polynomial?
\end{question}
\begin{proof}[Discussion]
The reason that the $h^*$-polynomial might be a better object comes from the generalized conjecture for arbitrary $\lambda$. For $\lambda=1^n$, the transportation polytope $T_{n,n-1}$ is simple and reflexive. After centering it first, its polar dual $T_{n,n-1}^{\circ}$ is simplicial and has a unimodular triangulation where each simplex has an apex at the origin and a facet as its base (simpliciality is standard because $\gcd(n,n-1)=1$, the part about the triangulation is after calculations in polymake). This means that the $h^*$-polynomial of $T_{n,n-1}^{\circ}$ agrees with the $h$-polynomial of $T_{n,n-1}$.   
\end{proof}


\subsection{On the topological structure of $T_W$}

It might be quite hard to guess what the polytopes $T_W$ should be; we have no natural coordinate space, the dimension $(h-2)\cdot n$ is very large \theo{but if the correct object is the $h^*$-polynomial of $T_W^{\circ}$, its degree does not necessarily equal the dimension (maybe $T_W^{\circ}$ is a rational polytope)} and generally the computation of $h^*$-polynomials is somewhat slow. However, we might have a better chance to understand the topological structure of $T_W$ by copying the type-A case. If we are lucky and the actual polytope $T_W$ turns out to be simple, we could calculate its $h$-polynomial just from its graph. \theo{This might not be enough to compute candidates for $\Phi_W(t)$, see later on.}

In the type-A case, the vertices of $T_{n,n-1}$ are \emph{canonically} indexed by edge-and-vertex labeled trees. Two such trees $\Delta_1$ and $\Delta_2$ which are adjacent in the graph of $T_{n,n-1}$ differ only in a single edge. In particular, they are adjacent if and only if an edge $(j_1,j_2)$ labeled $i$ in $\Delta_1$ is replaced by an edge $(j_1,j')$ in $\Delta_2$ (respectively $(j',j_2)$), also labeled $i$, such that the shortest part from $j_1$ to $j'$ (respectively from $j_2$ to $j'$) in $\Delta_1$ \emph{starts} with $(j_1,j_2)$ (respectively with $(j_2,j_1)$). Each edge of a tree can be altered to $n-2$ different edges to get adjacent trees. This means that the degree of each vertex of the polytope is $(n-1)\cdot (n-2)$ (indeed the dimension of $T_{n,n-1}$). Below is an example of three trees that form a path in $T_{12,11}$:

\begin{figure}[h]
\centering
\includegraphics[scale=0.5]{trans_pol.png}
\end{figure}

Below is the complete graph of $T_{3,2}$. Notice that in this case, $T_{3,2}$ is $2$-dimensional, so it is ``equal" to its graph. Also in general though, because $T_{n,n-1}$ is simple, its graph determines its $f$- and $h$-vectors.

\begin{figure}[H]
\centering
\includegraphics[scale=0.31]{t_32.png}
\end{figure}

The set of edge-and-vertex labeled trees is precisely the set $RGT(W)$ of \S\ref{sec: uniform weyl rep theory} for the symmetric group $S_n$ (i.e. the set of (ordered) tuples of reflections of minimum size $n$ which generate $S_n$). After Thm.~\ref{Thm: Weyl case} and its rewriting according to Weyl's theorem as in \S\ref{sec: uniform weyl rep theory}, we \emph{must} have $\Phi(1)=\Big(\prod_{i=1}^nc_i\Big)\cdot |RGT(W)|$.

It is then possible \theo{This is very speculative !} that the polytope $T_W$ has $|RGT(W)|$-many vertices and is simple. Moreover, that its polar has a triangulation with an apex at the origin and all facets as bases of the simplices, and that all such simplices have (normalized) volume equal to $\prod_{i=1}^n c_i$. Indeed, for the symmetric group $S_n$ all $c_i$ are equal to 1, so this is true in that case. Then, the polar $T_W^{\circ}$ would have normalized volume $\Phi_W(1)$ and we would hope that its $h^*$-polynomial is precisely $\Phi_W(X)$ (again, this is what happens for $W=S_n$).

The transportation polytope theory describes not only the topology of the polytope via trees, but also its complete geometry. You can read the coordinates of the polytope by the labeled trees. So, it is possible that whatever guess we make for the graph of $T_W$, copying the neighborhood condition for $T_{n,n-1}$ described above, will also suggest a geometric realization that will have (or its polar dual) the correct $h^*$-vector. \theo{This is very, very speculative, but it is possible that it could work maybe for type-B..? Here, the $c_i$'s are $1,2,\cdots,2$, that is, $\prod_{i=1}^nc_i=2^{n-1}$.

\noindent In particular, after Thm.~\ref{Thm: F_W(t) for G(m,p,n)} we have for $B_n$ that $$\Phi_{B_n}(X)=\Phi_{S_n}(X^2)\cdot (X+1)^{2n-2}\cdot (1+X+\cdots + X^{n-1})^2,$$ where $X$ is should be replaced by $e^t$ to get the exponential generating function. With $\Phi_{S_n}(X)$ being the $h$-, equivalently $h^*$-polynomial, of $T_{n,n-1}$ what polytope has $\Phi_{B_n}(X)$ as its $h$- \emph{or} $h^*$-polynomial?}

\ahm{What would be the natural graph whose vertices are $RGT(W)$?}
\theo{It's unclear yet! We would like to somehow generalize the $S_n$ situation above, but how?}
\ahm{Braun showed that when $P$ is a reflexive polytope ($P$ and its dual $P$
  are lattice polytopes) and $Q$
  contains the origin then for the \emph{free sum} $P \oplus Q =
  conv( 0^{d(P)} \times Q \cup P \times 0^{d(Q)})$ we
  have that $h^*(P\oplus Q) = h^*(P)h^*(Q)$.}
\theo{See also Stapledon's later work \cite{Stapledon}}


\section{Attempts towards a $W$-version of the Bousquet-Melou \& Schaeffer formula}
\label{sec: W-analog for B-M,S}


We would like to have a formula for the polynomials $P_{W,\id}(m)$ that count factorizations $\sigma_1\cdots \sigma_m=\id$ in $W$ such that (i) $\sum \lR(\sigma_i)=\lR^*(\id)=2n$ and (ii) the factorization is \emph{transitive}. 

It is easy to see that these function $P_{W,\id}(m)$ are indeed polynomials, as there are only finitely many tuples $(\sigma_i)$ that satisfy (i) if all $\sigma_i\neq \id$. So essentially all factorizations result from this finite set after arbitrarily adding several terms $\sigma_j=\id$. By standard stuff on turning strict chains to possibly lazy chains, this also implies that the degree of this polynomial will be $2n=\lR^*(\id)$ and its leading coefficient will be $F_W(\id)/(2n)!$ where $F_W(\id)$ counts the transitive, length-$2n$ reflection factorizations of the identity $\id\in W$ \textbf{with the same definition of transitivity as one chose in (ii)}.

There are at least a few difficulties/approaches here:
\begin{enumerate}
\item If we want to keep the same definition of transitivity as in the rest of the paper (i.e. that there is no proper reflection subgroup $W'<W$ which contains all terms $\sigma_i$) it is unlikely that we will get a factoring formula as in B-M,S. Indeed, in Weyl groups, the leading term of the polynomial $P_{W,\id}(m)$ will be after Thm.~\ref{Thm: Weyl case} equal to $|RGS(W)|/I(W)$ which as we saw doesn't always factor nicely; more details in \S\ref{sec: W-version B-M,S: transitivity}.\theo{If we don't care that it factors nicely, Alejandro has asked whether it might be the Hilbert polynomial of some polytope..?}
\item If we really want a product formula, it would have a leading coefficient which factors nicely too. That means that we want some count of \emph{reflection} factorizations of the identity $\id\in W$ that factors. No version of transitivity so far gives that, but there is a \emph{weighted} version that does. Perhaps we can generalize that; more details in \S\ref{sec: W-version B-M,S: product formula}.
\item A representation theoretic approach is quite tricky: For a notion of transitivity as in part (1) you would need to subtract (from the Frobenius lemma) factorizations that lie in proper reflection subgroups. You cannot do that recursively though, because some factorizations belong to many different minimal reflection subgroups. For instance $w\cdot w^{-1}=\id$ in $B_n$ with $w$ a Coxeter element of some reflection subgroup $B_k\times B_{n-k}$. It is easy to see that $w$ also belongs to some $D_n\leq B_n$.
\end{enumerate}


\subsection{Defining transitivity analogously to the rest of the paper}
\label{sec: W-version B-M,S: transitivity}


Here is some data for small reflection groups. The polynomials $P_{W,\id}(m)$ below count factorizations $\sigma_1\cdots\sigma_m=\id$ in $W$, such that $\sum \lR(\sigma_i)=\lR^*(\id)=2n$, and such that the factorization does not exist in a reflection subgroup of $W$ (i.e. there does not exist a \emph{reflection} subgroup $W'\leq W$ that contains all $\sigma_i$). The ``Hilbert series numerators" $H_{W,\id}(q)$ are the numerators of the series $\sum_{m\geq 0}P_{W,\id}(m)q^m$ (the denominator is always $(1-q)^{2n+1}$).

The polynomial $P_{W,\id}(m)$ has degree $2n$ and after Thm.~\ref{Thm: Weyl case}, its leading coefficient is precisely $|RGS(W)|/I(W)$. Similarly the sum of the coefficients of $H(q)$ has to be equal to $F_W(\id)$. The leading coefficient of $H(q)$ is the total number of quasi-Coxeter elements of $W$ (all of this for real $W$).[[It is not a priori clear why the coefficients of $P(m)$ are integers]].

\begin{enumerate}
\item For $A_2=I_2(3)$:\quad $P(m)=(m-1)^3m$ \quad\quad and \quad\quad $H(q)=2q^2 + 14q^3 + 8q^4$.
\item For $B_2=I_2(4)$:\quad  $P(m)=(2m^2 - 6m + 5)(m - 1)m$ \quad\quad and \quad\quad $H(q)=2q^2 + 20q^3 + 26q^4$.
\item For $I_2(5)$:\quad \quad \quad \, $P(m)=(5m^2 - 15m + 12)(m - 1)m$ \quad and \quad $H(q)=4q^2 + 52q^3 + 64q^4$.
\item For $I_2(6)$:\quad \quad \quad \, $P(m)=(6m^2 - 24m + 25)(m - 1)m$ \quad and \quad $H(q)=2q^2 + 32q^3 + 110q^4$.
\item For $I_2(7)$:\quad\quad \quad\, $P(m)=(14m^2 - 49m + 45)(m - 1)m$ \quad and \quad $H(q)=6q^2 + 114q^3 + 216q^4$.
\item For $I_2(8)$:\quad\quad\quad\, $P(m)=2(8m^2 - 32m + 33)(m - 1)m$\quad and \quad $H(q)=4q^2 + 88q^3 + 292q^4$.
\item For $I_2(9)$:\quad\quad\quad\, $P(m)=3(9m^2 - 36m + 37)(m - 1)m$\quad and \quad $H(q)=6q^2 + 150q^3 + 492q^4$.
\item For $I_2(10)$:\quad\quad\quad\ $P(m)=2(15m^2 - 65m + 71)(m - 1)m$\quad and \quad $H(q)=4q^2 + 112q^3 + 604q^4$.
\item For $I_2(11)$:\quad\quad\quad\ $P(m)=5(11m^2 - 44m + 45)(m - 1)m$\quad and \quad $H(q)=10q^2 + 310q^3 + 1000q^4$.

*****************************************************************************
\item For $A_3$:\quad\quad\quad $P(m)=(4m - 5)(m - 1)^4m$\quad and \quad $H(q)=6q^2 + 294q^3 + 1338q^4 + 1098q^5 + 144q^6$.
\item For $B_3$:\quad\quad\quad $P(m)=2(9m^4 - 51m^3 + 111m^2 - 111m + 44)(m - 1)m$ \quad \theo{Looks really bad!!} \newline and the ``Hilbert series numerator" $H(q)=8q^2 + 688q^3 + 4944q^4 + 6016q^5 + 1304q^6$.
\end{enumerate}

\subsection{A weighted count to get a product formula}
\label{sec: W-version B-M,S: product formula}

For Weyl groups, an easy corollary of some work of Burman is that $$\sum_{W'\leq W}|RGS(W')|\cdot I(W')=h^n,$$ where the sum is over all \emph{maximal rank} reflection subgroups $W'\leq W$ (including $W$ itself), $h$ is the Coxeter number of $W$ and $I(W')$ the connection index of $W'$ (which is also a Weyl group). After our Thm.~\ref{Thm: Weyl case} this can be rewritten as \begin{equation}
\sum_{W'\leq W}F_{W'}(\id)\cdot I(W')^2=h^n\cdot (2n)!,\label{EQ: weighted count factors}
\end{equation} where the sum is again over all \emph{maximal rank} reflection subgroups of $W$ (including $W$).

\ahm{Is there an analogue of this equationa above with Conjecture. 4.5?}
\theo{At least trivially, it seems no. Because in complex types different factorizations in the same $W'$ have different weights..}

After this, it seems reasonable (maybe) to define $$\overline{P}_{W,\id}(m):=\sum_{\sigma_1\cdots \sigma_m=\id}I\big(W(\bm\sigma)\big)^2,$$ where $W(\bm\sigma)$ is \emph{any} minimal reflection subgroup of $W$ that contains all terms $\sigma_i\in\bm\sigma$ and the summation is over all factorizations $\bm\sigma$ such that $\sum \lR(\sigma_i)=\lR^*(\id)=2n$ and $W(\bm\sigma)$ has rank $n$.
\theo{For this to make sense, we would need that all such minimal reflection subgroups have the same connection index. This seems true so far but has not been tested!}\newline
As before, the function $\overline{P}_{W,\id}(m)$ will be a polynomial and of degree $2n$, but now its leading coefficient will be $h^n$. I only have data for these groups so far:
\begin{enumerate}
\item For $A_2=I_2(3)$: $\overline{P}(m)=9(m-1)^3m$
\item For $B_2=I_2(4)$: $\overline{P}(m)=4(2m-1)(2m-3)(m-1)m$ \quad\theo{An accident maybe??}
\item For $G_2=I_2(6)$: $\overline{P}(m)=18(2m^2-4m+1)(m-1)m$ \quad \theo{not nice! the $(m-1)m$ factor is standard}
\item For $B_3$: $\overline{P}(m)=8/3\cdot(81 m^4 - 69 m^3 - 1626 m^2 + 5186 m - 4576)(m - 1)m$\quad \theo{If I did it right, it's evidence against...}
\end{enumerate} 



\printbibliography

\end{document}

\section{A section}

\lipsum[3]

\begin{equation}\label{eqn:eq1}
\int_0^\infty \exp(-x)dx = 1.
\end{equation}

\begin{lem}\label{lem:lem1}
\lipsum[11]
\end{lem}

\lipsum[10]

\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{plot}
\caption{A plot of a function.}
\label{fig:plot}
\end{figure}

\subsection{A subsection}

\lipsum[5]

\begin{align*}
1 + 1 + 1 &= 2 + 1 \\ &= 3.
\end{align*}

\subsubsection{A subsubsection}

\lipsum[17]

Here is a citation~\cite{greenwade93} with URL. Here is another
citation~\cite{MR4}, which is the earliest-numbered Math Review with a
functioning DOI: MR0000004. Finally, a reference to
equation~\eqref{eqn:eq1}. And a reference to Figure~\ref{fig:plot}.

\acknowledgements{\lipsum[20]}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way

\printbibliography

\end{document}
