[theorem]

# Rational Noncrossing Coxeter–Catalan Combinatorics

Pavel Galashin  Department of Mathematics, University of California, Los
Angeles, 520 Portola Plaza, Los Angeles, CA 90025<EMAIL_ADDRESS>,
Thomas Lam  Department of Mathematics, University of Michigan, 2074 East Hall,
530 Church Street, Ann Arbor, MI 48109-1043<EMAIL_ADDRESS>,  Minh-Tâm
Trinh  Massachusetts Institute of Technology, 77 Massachusetts Avenue,
Cambridge, MA 02139<EMAIL_ADDRESS>and  Nathan Williams  University of Texas at
Dallas, 800 W. Campbell Rd. Richardson, TX 75080-3021
<EMAIL_ADDRESS>
###### Abstract.

We solve two open problems in Coxeter–Catalan combinatorics. First, we
introduce a family of rational noncrossing objects for any finite Coxeter
group, using the combinatorics of distinguished subwords. Second, we give a
type-uniform proof that these noncrossing Catalan objects are counted by the
rational Coxeter–Catalan number, using the character theory of the associated
Hecke algebra and the properties of Lusztig’s exotic Fourier transform. We
solve the same problems for rational noncrossing parking objects.

###### Key words and phrases:

Coxeter–Catalan combinatorics, rational Catalan number, $q$-Catalan number,
noncrossing partitions, parking functions, Hecke algebra, Coxeter group,
rational Cherednik algebra

###### 2020 Mathematics Subject Classification:

Primary: 05A15. Secondary: 05E05, 05E10, 20C08.

P.G. was supported by an Alfred P. Sloan Research Fellowship and by the
National Science Foundation under Grants No. DMS-1954121 and No. DMS-2046915.
T.L. was supported by Grants No. DMS-1464693 and No. DMS-1953852 from the
National Science Foundation. M.T. was supported by the National Science
Foundation under Grant No. 2002238. N.W. was partially supported by Simons
Foundation Collaboration Grant No. 585380.

##  1\. Introduction

###  1.1. Rational $W$-Catalan numbers and $W$-nonnesting combinatorics

The Catalan number

$\mathrm{Cat}_{n}\coloneqq\frac{1}{n+1}\binom{2n}{n}=\frac{1}{2n+1}\binom{2n+1}{n}$

famously counts Dyck paths with $2n$ steps. More generally, if $p$ is a
positive integer coprime to $n$, then the _rational Catalan number_
$\mathrm{Cat}_{n,p}\coloneqq\frac{1}{p+n}\binom{p+n}{n}$ counts _rational Dyck
paths_ : the lattice paths in a $p\times n$ rectangle that stay above the
diagonal [Biz54, ARW13]. For instance, Figure 1 shows that
$\mathrm{Cat}_{5,3}=7$. Taking $p=n+1$ recovers the classical case:
$\mathrm{Cat}_{n,n+1}=\frac{1}{2n+1}\binom{2n+1}{n}=\mathrm{Cat}_{n}$.

Figure 1. The rational Dyck paths counted by $\mathrm{Cat}_{5,3}$.

Rational Dyck paths admit several generalizations that depend uniformly on an
irreducible finite Weyl group $W$:

  * •

for $p=h+1$, where $h$ is the Coxeter number of $W$, one can take antichains
in the positive root poset or dominant regions of the Shi arrangement [Shi87,
Rei97];

  * •

for $p=kh+1$, one can take certain $k$-tuples of roots that encode dominant
regions of the $k$-Shi arrangement [Ath04, Ath05]; and

  * •

for any $p$ coprime to $h$, one can take coroots inside a certain $p$-fold
dilation of the fundamental alcove [Hai94, KF96, Som97, Sag00, CP02, Thi16,
TW17].

These generalizations are collectively known as _nonnesting objects_ , because
when $W$ is the symmetric group $\mathfrak{S}_{n}$ and $p=n+1$, they admit
natural bijections to the classical nonnesting partitions of $n$.

Henceforth, all reflection groups are finite, real, and irreducible. Let $W$
be a Weyl group of rank $r$ and Coxeter number $h$. (If $W=\mathfrak{S}_{n}$,
then $r=n-1$ and $h=n$.) For any integer $p$ coprime to $h$, the _rational
$W$-Catalan numbers_ [Hai94] are given by

$\displaystyle{\mathrm{Cat}_{p}(W)}\coloneqq\prod_{i=1}^{r}\frac{p+e_{i}}{d_{i}},$

where the numbers $d_{i}$ are integers known as the _degrees_ of $W$, and the
numbers $e_{i}=d_{i}-1$ are known as the _exponents_ of $W$. If
$W=\mathfrak{S}_{n}$, then $d_{i}=i+1$ and $e_{i}=i$, giving
$\mathrm{Cat}_{p}(\mathfrak{S}_{n})=\mathrm{Cat}_{n,p}$. Together, [Hai94,
Theorem 7.4.2] and [Thi16, Lemma 8.2] give a uniform proof that the families
of nonnesting objects above are counted by ${\mathrm{Cat}_{p}(W)}$.

For an arbitrary Coxeter group $W$ (in fact, for any well-generated complex
reflection group) with Coxeter number $h$ and $p$ coprime to $h$, [GG12]
extend the definition above to

(1.1)
${\mathrm{Cat}_{p}(W)}\coloneqq\prod_{i=1}^{r}\frac{p+(pe_{i}\operatorname{mod}{h})}{d_{i}}.$

If $W$ is a Weyl group, then multiplication by $p$ permutes the residues of
the exponents modulo $h$ by [Spr74, Proposition 4.7] and [STW15, Proposition
8.1.2], so the new definition of ${\mathrm{Cat}_{p}(W)}$ specializes to the
previous one. In the generality of Coxeter groups, however, a uniform
definition of nonnesting objects has not been found.

###  1.2. Rational $W$-noncrossing combinatorics

The Catalan numbers $\mathrm{Cat}_{n}$ count many other objects beyond Dyck
paths—in particular, they also count the noncrossing partitions of $n$. If
$p=kh+1$, then several families of _noncrossing objects_ counted by
$\mathrm{Cat}_{p}(W)$ can be defined uniformly for any finite Coxeter group
$W$, including $W$-noncrossing partitions [Rei97, Bes03, Bes15, Arm09],
generalizations of cluster exchange graphs for finite-type cluster algebras
[FZ03a, FR05, CLS14], and Coxeter-sortable elements [Rea07a, Rea07a, STW15].
The $W$-noncrossing partitions can even be defined for well-generated complex
reflection groups.

These families are of a very different nature from the nonnesting objects of
Section 1.1. They are defined beyond crystallographic reflection groups, their
definition depends on the choice of a Coxeter element, and they satisfy a
recursive property called the Cambrian recurrence. However:

  1. (1)

For any $W$, the uniform definition of rational noncrossing families for
_arbitrary_ $p$ coprime to $h$ has been an open problem for roughly a decade.

  2. (2)

For any of the kinds of noncrossing families above, the proof of their
_uniform enumeration_ by $\mathrm{Cat}_{p}(W)$ for all $W$ has been an open
problem since their definition.

For further discussion of these problems, see the summary report from the 2012
American Institute of Mathematics workshop on rational Catalan combinatorics
[Wil12, Sections 1.1–1.2], as well as [STW15, Chapter 8], [BR16, Section 7],
[Bod19, Section 8], and [ARW13, Section 1].

We resolve both problems. Our first result is the uniform definition of a
rational noncrossing family for any Coxeter group $W$ (Definition 1.1). Our
second result is their enumeration (Theorem 1.4).

###  1.3. Rational $W$-noncrossing objects

Let $S\subseteq W$ be a system of simple reflections, and let
$\mathbf{c}=(s_{1},s_{2},\dots,s_{r})$ be an ordering of $S$, which we will
call a _Coxeter word_. Let $p$ be a positive integer coprime to $h$, and let
$\mathbf{c}^{p}$ be the concatenation of $p$ copies of $\mathbf{c}$. Thus
$\mathbf{c}^{p}=(s_{1},s_{2},\dots,s_{m})$, where $s_{i}=s_{i-r}$ for all
$i>r$, is a word of length $m=pr$.

Given a _subword_ $\mathbf{u}=(u_{1},u_{2},\cdots,u_{m})$ of $\mathbf{c}^{p}$,
meaning $u_{i}\in\\{s_{i},e\\}$ for every $i\in[m]\coloneqq\\{1,2,\dots,m\\}$,
we set $u_{(i)}\coloneqq u_{1}u_{2}\cdots u_{i}\in W$ for each $i$. We write
$e$ for the identity of $W$, and say that $\mathbf{u}$ is an _$e$ -subword_ if
$u_{(m)}=e$. We say that $\mathbf{u}$ is _distinguished_ [Deo85, MR04] if
$u_{(i)}\leq u_{(i-1)}s_{i}$ in the weak order for all $i\in[m]$, where we set
$u_{(0)}\coloneqq e$. In other words, the symbol $s_{i}$ must be used in
$\mathbf{u}$ if it decreases the length of $u_{(i-1)}$. We write
$\operatorname{e}_{\mathbf{u}}$ for the number of symbols of $\mathbf{c}^{p}$
skipped in $\mathbf{u}$: that is,
$\operatorname{e}_{\mathbf{u}}\coloneqq|\\{i\mid\mathbf{u}_{i}=e\\}|$. The
following definition is closely related to [GL20, Definition 9.3]; see also
[KW13].

######  Definition 1.1.

A _maximal $\mathbf{c}^{p}$-Deogram_ is a distinguished $e$-subword
$\mathbf{u}$ of $\mathbf{c}^{p}$ for which $\operatorname{e}_{\mathbf{u}}=r$.
The set of maximal $\mathbf{c}^{p}$-Deograms is denoted
$\mathcal{M}_{e,\mathbf{c}^{p}}(W)$.

See Figure 2 for an example of Definition 1.1. In general, any $e$-subword
$\mathbf{u}$ of $\mathbf{c}^{p}$ satisfies $\operatorname{e}_{\mathbf{u}}\geq
r$, as we show in Corollary 4.9. Thus the maximal $\mathbf{c}^{p}$-Deograms
are precisely the distinguished $e$-subwords of $\mathbf{c}^{p}$ that use the
maximal possible number of symbols.

######  Remark 1.2.

We can interpret maximal $\mathbf{c}^{p}$-Deograms as certain _closed walks_
on $W$ on the Hasse diagram of the weak Bruhat order, or equivalently, on the
directed Cayley graph of $(W,S)$. The walk corresponding to an $e$-subword
$\mathbf{u}$ of $\mathbf{c}^{p}$ is the sequence of elements
$(e=u_{(0)},u_{(1)},\dots,u_{(m)}=e)$: that is, the walk starts at $e$, and
for each letter $s_{i}$, it either _follows_ the corresponding edge of the
Cayley graph or _stays_ in place.

In this model, the distinguished condition on $\mathbf{u}$ becomes the
condition that the walk must follow the edge labeled by $s_{i}$ whenever it
points downward in weak order. In particular, maximal
$\mathbf{c}^{p}$-Deograms correspond to distinguished closed walks starting
and ending at $e$ with precisely $r$ stays.

######  Remark 1.3.

For $W=\mathfrak{S}_{n}$, we can also interpret maximal
$\mathbf{c}^{p}$-Deograms in terms of _wiring diagrams_ , as illustrated in
Figure 3. A maximal $\mathbf{c}^{p}$-Deogram consists of $n-1$ elbows  inside
the wiring diagram of $\mathbf{c}^{p}$ with the property that the resulting
permutation is the identity, i.e., the left and the right endpoints of each
wire have the same labels.

In this model, the distinguished condition becomes the condition that for each
elbow $E$, the two participating wires intersect an even number of times to
the left (or equivalently, to the right) of $E$. We associate to $E$ a
_colored inversion_ (Definition 4.3). The inversion $(i\kern 1.00006ptj)$
records the left endpoints $i,j\in[n]$ of the two wires participating in $E$.
Its _color_ , indicated by the number of dots above $(i\kern 1.00006ptj)$,
equals the number of intersection points to the left of $E$ between the two
wires participating in $E$. See also [GL20, Figure 5] and Remark 2.12.

######  Theorem 1.4.

For any (irreducible, finite) Coxeter group $W$ of rank $r$ and Coxeter number
$h$, Coxeter word $\mathbf{c}$, and (positive) integer $p$ coprime to $h$, we
have

$\displaystyle|\mathcal{M}_{e,\mathbf{c}^{p}}(W)|={\mathrm{Cat}_{p}(W)}.$

See Figures 2 and 3 for an example of Theorem 1.4. The proof occupies Sections
4 to 6.

Even in the Catalan case $p=h+1$, all previous results on the enumeration of
$W$-noncrossing objects relied on the classification of Coxeter groups. In
Section 8, we show that the objects in $\mathcal{M}_{e,\mathbf{c}^{p}}(W)$ are
truly _noncrossing_ by showing that they are in natural uniform bijection with
the three families of $W$-noncrossing objects mentioned in Section 1.2 [Arm09,
STW15]. Our work therefore provides the first uniform proof that each of these
$W$-noncrossing families is counted by the _$W$ -Catalan numbers_
$\mathrm{Cat}(W)\coloneqq\mathrm{Cat}_{h+1}(W)$. In particular, our results
give the first uniform proof that the number of clusters in a finite-type
cluster algebra is counted by $\mathrm{Cat}(W)$ [FZ03b, Theorem 1.9].

We generalize this bijection between $\mathcal{M}_{e,\mathbf{c}^{p}}(W)$ and
the three families of $W$-noncrossing objects to the _Fuss–Catalan_ ($p=kh+1$)
setting. Since the zeta polynomial of the noncrossing partition lattice counts
the Fuss–Catalan noncrossing partitions [Cha04, Proposition 9], taking the
leading coefficient of $k$ in $\prod_{i=1}^{r}\frac{kh+d_{i}}{d_{i}}$
immediately gives a new uniform proof of the formula $\frac{r!h^{r}}{|W|}$ for
the number of maximal chains in the noncrossing partition lattice [Del74,
Rea08, Mic16].

######  Remark 1.5.

For $W=\mathfrak{S}_{n}$, Theorem 1.4 is comparable to [GL20, Proposition
9.5]. This result states that $\mathrm{Cat}_{n,p}$ counts maximal
$f_{p,n+p}$-Deograms, where $f_{p,n+p}$ is a permutation (rather than a word)
in the larger symmetric group ${\mathfrak{S}_{n+p}}$. It would be interesting
to give such an interpretation for other Weyl groups $W$, even for classical
types. See Open Problem 2.11 and Remark 2.12.

$\begin{array}[]{|cccc!{\graytablecolor\vrule}cccc!{\graytablecolor\vrule}cccc|}\hline\cr
s_{1}&s_{2}&s_{3}&s_{4}\hfil\lx@intercol\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color@gray@fill{0.6}&s_{1}&s_{2}&s_{3}&s_{4}\hfil\lx@intercol\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color<EMAIL_ADDRESS>\hline\cr&&&\hfil\lx@intercol\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color@gray@fill{0.6}&&&&\hfil\lx@intercol\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color<EMAIL_ADDRESS>s_{1}&s_{2}&(1\kern
1.00006pt4)&s_{4}\hfil\lx@intercol\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color@gray@fill{0.6}&s_{1}&s_{2}&(2\kern
1.00006pt5)&s_{4}\hfil\lx@intercol\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color@gray@fill{0.6}&s_{1}&s_{2}&(3\kern
1.00006pt4)&\ddot{(4\kern 1.00006pt5)}\\\ s_{1}&s_{2}&(1\kern
1.00006pt4)&s_{4}\hfil\lx@intercol\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color@gray@fill{0.6}&(2\kern
1.00006pt3)&s_{2}&s_{3}&(3\kern
1.00006pt4)\hfil\lx@intercol\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color@gray@fill{0.6}&s_{1}&(2\kern
1.00006pt5)&s_{3}&s_{4}\\\ s_{1}&s_{2}&(1\kern 1.00006pt4)&(4\kern
1.00006pt5)\hfil\lx@intercol\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color@gray@fill{0.6}&s_{1}&s_{2}&(2\kern
1.00006pt4)&s_{4}\hfil\lx@intercol\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color@gray@fill{0.6}&s_{1}&s_{2}&(3\kern
1.00006pt5)&s_{4}\\\ s_{1}&(1\kern
1.00006pt3)&s_{3}&s_{4}\hfil\lx@intercol\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color@gray@fill{0.6}&s_{1}&s_{2}&(2\kern
1.00006pt5)&s_{4}\hfil\lx@intercol\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color@gray@fill{0.6}&(1\kern
1.00006pt4)&s_{2}&s_{3}&(4\kern 1.00006pt5)\\\ s_{1}&(1\kern
1.00006pt3)&s_{3}&s_{4}\hfil\lx@intercol\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color@gray@fill{0.6}&s_{1}&(2\kern
1.00006pt4)&s_{3}&s_{4}\hfil\lx@intercol\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color@gray@fill{0.6}&\ddot{(1\kern
1.00006pt2)}&(2\kern 1.00006pt5)&s_{3}&s_{4}\\\ (1\kern
1.00006pt2)&s_{2}&s_{3}&(2\kern
1.00006pt5)\hfil\lx@intercol\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color@gray@fill{0.6}&s_{1}&(1\kern
1.00006pt4)&s_{3}&s_{4}\hfil\lx@intercol\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color@gray@fill{0.6}&s_{1}&s_{2}&(3\kern
1.00006pt5)&s_{4}\\\ (1\kern 1.00006pt2)&(2\kern
1.00006pt3)&s_{3}&s_{4}\hfil\lx@intercol\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color@gray@fill{0.6}&s_{1}&(1\kern
1.00006pt4)&s_{3}&s_{4}\hfil\lx@intercol\color[rgb]{0.6,0.6,0.6}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0.6,0.6}\pgfsys@color@gray@stroke{0.6}\pgfsys@color@gray@fill{0.6}&s_{1}&(2\kern
1.00006pt5)&s_{3}&s_{4}\\\ \hline\cr\end{array}$ Figure 2. For
$W=\mathfrak{S}_{5}$, $\mathbf{c}=(s_{1},s_{2},s_{3},s_{4})$, and $p=3$, each
row above depicts one of the seven maximal $\mathbf{c}^{p}$-Deograms in the
set $\mathcal{M}_{e,\mathbf{c}^{p}}(W)$ from Definition 1.1. For each
$\mathbf{u}\in\mathcal{M}_{e,\mathbf{c}^{p}}(W)$, we have replaced the
positions $i$ where $u_{i}=e$ with the corresponding colored inversions from
Remark 1.3. Compare with Figure 1.  Figure 3. Wiring diagrams for Figure 2,
illustrating Remark 1.3.

###  1.4. Rational $W$-parking functions

Let $\mathbf{a}=(a_{1},a_{2},\dots,a_{n})$ be a sequence of positive integers
and $(b_{1}\leq b_{2}\leq\dots\leq b_{n})$ its increasing rearrangement. We
say that $\mathbf{a}$ is a _parking function_ if $b_{i}\leq i$ for all $i$.
The number of parking functions of length $n$ is well known to be
$(n+1)^{n-1}$ [KW66].

######  Example 1.6.

For $n=3$, the $16$ parking functions are given by

$\displaystyle(1,1,1),\ (1,1,2),\ (1,2,1),\ (2,1,1),\ (1,1,3),\ (1,3,1),\
(3,1,1),\ (1,2,2),$ $\displaystyle(2,1,2),\ (2,2,1),\ (1,2,3),\ (1,3,2),\
(2,1,3),\ (2,3,1),\ (3,1,2),\ (3,2,1).$

For a Coxeter group $W$ with $h$, $\mathbf{c}$, and $p$ as above, we can use
distinguished subwords to define rational $W$-analogues of parking functions
that we call _rational noncrossing $W$-parking objects_. Recall from Remark
1.2 that each $e$-subword $\mathbf{u}$ of $\mathbf{c}^{p}$ gives rise to a
closed walk $(e=u_{(0)},u_{(1)},\dots,u_{(m)}=e)$ in weak order, starting and
ending at $e$. To define our parking objects, we instead consider closed walks
starting and ending at arbitrary $v\in W$. More precisely, given $v\in W$, we
say that a subword $\mathbf{u}$ of $\mathbf{c}^{p}$ is _$v$ -distinguished_ if
we have $vu_{(i)}\leq vu_{(i-1)}s_{i}$ for all $i$.

######  Definition 1.7.

Given $v\in W$, a _maximal $(\mathbf{c}^{p},v)$-Deogram_ is a
$v$-distinguished $e$-subword $\mathbf{u}$ of $\mathbf{c}^{p}$ satisfying
$\operatorname{e}_{\mathbf{u}}=r$. Let
$\mathcal{M}^{(v)}_{e,\mathbf{c}^{p}}(W)$ be the set of maximal
$(\mathbf{c}^{p},v)$-Deograms, and let

$\displaystyle{\mathcal{P}_{e,\mathbf{c}^{p}}(W)}\coloneqq\bigsqcup_{v\in
W}\mathcal{M}^{(v)}_{e,\mathbf{c}^{p}}(W).$

In the language of Remark 1.2, each element
$\mathbf{u}\in{\mathcal{P}_{e,\mathbf{c}^{p}}(W)}$ gives rise to a
distinguished closed walk $(v=vu_{(0)},vu_{(1)},\dots,vu_{(m)}=v)$ with
precisely $r$ stays. We note that the same subword $\mathbf{u}$ may belong to
$\mathcal{M}^{(v)}_{e,\mathbf{c}^{p}}(W)$ for several different $v\in W$, in
which case it gives rise to several different closed walks. We consider these
closed walks to be distinct elements of ${\mathcal{P}_{e,\mathbf{c}^{p}}(W)}$.

######  Theorem 1.8.

For any Coxeter group $W$ of rank $r$ and Coxeter number $h$, Coxeter word
$\mathbf{c}$, and integer $p$ coprime to $h$, we have

(1.2) $\displaystyle\left|{\mathcal{P}_{e,\mathbf{c}^{p}}(W)}\right|=p^{r}.$

For $W=\mathfrak{S}_{n}$ and $p=n+1$, the right-hand side of (1.2) becomes
$(n+1)^{n-1}$. See Figures 4 and 12 for examples of Theorem 1.8.

Figure 4.  The 16 elements of ${\mathcal{P}_{e,\mathbf{c}^{p}}(W)}$ for
$W=\mathfrak{S}_{3}$, $\mathbf{c}=(s_{1},s_{2})$, and $p=4$. For each
$v\in\mathfrak{S}_{n}$, we list the maximal $(v,\mathbf{c}^{p})$-Deograms in
the top row of the corresponding table. They are shown together with their
_$v$ -twisted colored inversions_ defined in Sections 2.3 and 8.5. The bottom
row of each table illustrates the bijection from Section 2.3 between the set
$\mathcal{P}_{e,\mathbf{c}^{n+1}}(W)$ and the set of labeled noncrossing
partitions. Compare with Examples 1.6 and 12.

###  1.5. $q$-Deformations and Hecke algebra traces

We will deduce Theorems 1.4 and 1.8 from stronger statements involving
$q$-numbers: that is, polynomials of the form $[a]_{q}\coloneqq
1+q+\cdots+q^{a-1}$. Let

(1.3)
$\mathrm{Cat}_{p}(W;q)\coloneqq\prod_{i=1}^{r}\frac{[p+(pe_{i}\operatorname{mod}{h})]_{q}}{[d_{i}]_{q}},$

the $q$-analogue of ${\mathrm{Cat}_{p}(W)}$ from (1.1).

For any word $\mathbf{w}=(s_{1},s_{2},\ldots,s_{m})$ and $u,v\in W$, let
$\mathcal{D}^{(v)}_{u,\mathbf{w}}$ be the set of $v$-distinguished
$u$-subwords of $\mathbf{w}$, not necessarily maximal. For any
$\mathbf{u}\in\mathcal{D}^{(v)}_{u,\mathbf{w}}$, recall from Section 1.3 that
$\operatorname{e}_{\mathbf{u}}\coloneqq|\\{i\in[m]\mid\mathbf{u}_{i}=e\\}|$.
We set $\operatorname{d}^{(v)}_{\mathbf{u}}\coloneqq|\\{i\in[m]\mid
vu_{(i)}<vu_{(i-1)}\\}|$ and

(1.4) $\displaystyle R^{(v)}_{u,\mathbf{w}}(q)$
$\displaystyle=\sum_{\mathbf{u}\in\mathcal{D}^{(v)}_{u,\mathbf{w}}}(q-1)^{\operatorname{e}_{\mathbf{u}}}q^{\operatorname{d}^{(v)}_{\mathbf{u}}}.$

We abbreviate $\mathcal{D}_{u,\mathbf{w}}=\mathcal{D}^{(e)}_{u,\mathbf{w}}$
and $R_{u,\mathbf{w}}(q)=R^{(e)}_{u,\mathbf{w}}(q)$. The polynomials
$R_{u,\mathbf{w}}(q)$ are generalizations of the celebrated $R$-polynomials of
Kazhdan–Lusztig [KL79]. In Section 4, we define $R^{(v)}_{u,\mathbf{w}}(q)$ by
a recurrence, and then deduce the closed formula above from an analogous
recurrence for $\mathcal{D}^{(v)}_{u,\mathbf{w}}$. The $q$-deformations of
Theorems 1.4 and 1.8 are as follows:

######  Theorem 1.9 (Corollaries 6.13 and 6.15).

For any Coxeter group $W$ of rank $r$ and Coxeter number $h$, Coxeter word
$\mathbf{c}$, and integer $p$ coprime to $h$, we have

  1. (1)

$\phantom{\sum\limits_{v\in
W}{}}R_{e,\mathbf{c}^{p}}(q)=(q-1)^{r}\mathrm{Cat}_{p}(W;q),$

  2. (2)

$\sum\limits_{v\in W}R^{(v)}_{e,\mathbf{c}^{p}}(q)=(q-1)^{r}[p]_{q}^{r}.$

For $W=\mathfrak{S}_{n}$, the right-hand side of 1.9(1) equals
$(q-1)^{n-1}\mathrm{Cat}_{n,p}(q)$, where

$\displaystyle\mathrm{Cat}_{n,p}(q)\coloneqq\frac{1}{[p+n]_{q}}\genfrac{[}{]}{0.0pt}{}{p+n}{n}_{q},$

where
$\genfrac{[}{]}{0.0pt}{}{p+n}{n}_{q}\coloneqq\frac{[p+n]_{q}!}{[p]_{q}![n]_{q}!}$
and $[m]_{q}!\coloneqq[1]_{q}[2]_{q}\cdots[m]_{q}$.

######  Example 1.10.

For $W=\mathfrak{S}_{3}$ and $p=4$, we compute (1.4) and compare it with
1.9(2):

$\displaystyle(q-1)^{-r}\sum_{v\in
W}R^{(v)}_{e,\mathbf{c}^{p}}(q)={\overbrace{\left(1+q^{2}+q^{3}+q^{4}+q^{6}\right)}^{v=e}}+2q{\overbrace{\left(1+q^{2}+q^{4}\right)}^{v\in\\{s_{1},s_{2}\\}}}+2q^{2}{\overbrace{\left(1+q^{2}\right)}^{v\in\\{s_{1}s_{2},s_{2}s_{1}\\}}}+q^{3}{\overbrace{\left(1\right)}^{v=s_{1}s_{2}s_{1}}}=[4]_{q}^{2}.$

The sets $\mathcal{M}^{(v)}_{e,\mathbf{c}^{p}}(W)$ are shown in Figures 4 and
12. The $v=e$ piece of the sum recovers the rational $q$-Catalan number
$\mathrm{Cat}_{4}(\mathfrak{S}_{3};q)=\mathrm{Cat}_{3,4}(q)=1+q^{2}+q^{3}+q^{4}+q^{6}$
of 1.9(1).

The proofs given in Sections 4 to 6 require some background in the
representation theory of Coxeter groups.

In Section 5, we recall that the group ring $\mathbb{Z}[W]$ can be deformed to
a $\mathbb{Z}[q^{\pm 1}]$-algebra called the _Hecke algebra_
$\mathcal{H}_{W}$. Every word $\mathbf{w}$ in the simple reflections of $W$
gives rise to a corresponding element $T_{\mathbf{w}}$ of the Hecke algebra.
We will show that $R_{e,\mathbf{w}}(q)$ can be expressed in terms of the value
of $T_{\mathbf{w}}$ under a certain $\mathbb{Z}[q^{\pm 1}]$-linear trace. For
general $u,v\in W$, a similar result holds for $R^{(v)}_{u,\mathbf{w}}(q)$.

In Section 6, we compare the trace to the right-hand sides of Theorem
1.9(1–2). The key idea is to decompose the trace as a linear combination of
the characters of the simple $\mathcal{H}_{W}$-modules. Using a theorem of
Springer, we deduce that for a Coxeter word $\mathbf{c}$, the trace of
$T_{\mathbf{c}^{p}}$ can be expressed as a linear combination of values of the
form $\mathrm{Feg}_{\chi}(e^{2\pi i\frac{p}{h}})$, where $\chi$ runs over the
irreducible characters of $W$ and $\mathrm{Feg}_{\chi}$ is a polynomial called
the _fake degree_ of $\chi$. On the other hand, using a result from [Tri21],
we show that the right-hand side of 1.9(1) can be expressed as a linear
combination of values of the form $\mathrm{Deg}_{\chi}(e^{2\pi
i\frac{p}{h}})$, where $\mathrm{Deg}_{\chi}$ is a polynomial called the
_unipotent_ or _generic degree_ of $\chi$.

Although fake degrees and generic degrees originated in the work of Deligne
and Lusztig on representations of finite groups of Lie type, they can be
defined purely in terms of the structure of $\mathcal{H}_{W}$. For the
symmetric group $\mathfrak{S}_{n}$, we have
$\mathrm{Feg}_{\chi}=\mathrm{Deg}_{\chi}$ for every $\chi$. But for general
Coxeter groups, these polynomials are related by a nontrivial pairing
$\\{-,-\\}_{W}$ on the set of irreducible characters $\mathrm{Irr}(W)$,
discovered by Lusztig and known as the _(truncated) exotic Fourier transform_
(Theorem 6.12). Ultimately, we show that 1.9(1) is equivalent to a certain
identity (6.16) for $\mathrm{Feg}_{\chi}$ and $\mathrm{Deg}_{\chi}$, that is a
consequence of symmetry and block-diagonality properties of the exotic Fourier
transform: See parts (2)–(3) of Theorem 6.12.

While these properties can be stated uniformly for all Coxeter groups,
Lusztig’s proofs of these properties are not uniform even for Weyl groups.
Moreover, there is no uniform definition of $\\{-,-\\}_{W}$ for general
Coxeter groups. See Section 6.5 for an extensive discussion of this issue.

######  Remark 1.11.

As we explain in Section 6.5, $\\{-,-\\}_{W}$ arises as the restriction to
$\mathrm{Irr}(W)$ of a pairing $\\{-,-\\}$ on a superset
$\mathrm{Udeg}(W)\supseteq\mathrm{Irr}(W)$. The pairing is the actual _exotic
Fourier transform_ : When $W$ is a Weyl group, $\\{-,-\\}$ is a precise
nonabelian generalization of the usual Fourier transform on a finite abelian
group. The name “truncated” for $\\{-,-\\}_{W}$ comes from the preprint
[Mic22], which appeared while our paper was in preparation.

###  1.6. Braid Richardson varieties

Our final goal is to introduce algebraic varieties
$\accentset{\circ}{R}^{(v)}_{e,\mathbf{w}}$ whose point counts over a finite
field of order $q$ recover the $q$-formulas above. These varieties appear in
[Deo85, MR04, WY07] when $\mathbf{w}$ is a reduced word of an element $w\in
W$, in which case $\accentset{\circ}{R}_{u,\mathbf{w}}$ becomes isomorphic to
an _open Richardson variety_ $\accentset{\circ}{R}_{u,w}$. Related
constructions appear in [Mel19, CGGS21, Tri21]. See [Tri21, Appendix B] for
further references.

Let $\mathbb{F}$ be a field. Fix a split, connected reductive algebraic group
$G$ over $\mathbb{F}$ with Weyl group $W$. Let $\mathcal{B}$ be the _flag
variety_ of $G$, i.e., the variety of all Borel subgroups of $G$. The group
$G$ acts on $\mathcal{B}$ by conjugation: If $g\in G$ and $B\in\mathcal{B}$,
then we set $g\cdot B\coloneqq gBg^{-1}$.

Fix a pair of opposed $\mathbb{F}$-split Borel subgroups
$B_{+},B_{-}\in\mathcal{B}$, and set $H\coloneqq B_{+}\cap B_{-}$. We can
identify $W$ with $N_{G}(H)/H$. We write $w\cdot B_{+}\coloneqq\dot{w}\cdot
B_{+}$, where $\dot{w}\in G$ is any lift of $w\in W$ to $N_{G}(H)$. For any
two Borels $B_{1},B_{2}\in\mathcal{B}$, there is a unique $w$ such that
$(B_{1},B_{2})=(g\cdot B_{+},gw\cdot B_{+})$ for some $g\in G$. In this case,
we write $B_{1}\xrightarrow{w}B_{2}$ and say that $(B_{1},B_{2})$ are in
_relative position $w$_. For example, $B_{+}\xrightarrow{w_{\circ}}B_{-}$,
where $w_{\circ}$ is the longest element of $W$, whereas
$B_{1}\xrightarrow{e}B_{2}$ if and only if $B_{1}=B_{2}$.

If $W=\mathfrak{S}_{n}$, then we can take $G=\mathrm{GL}_{n}(\mathbb{F})$, the
general linear group of $\mathbb{F}^{n}$. In this case, $\mathcal{B}$ is the
variety of _complete flags_

(1.5) $\displaystyle V_{\bullet}=(V_{0}\subset V_{1}\subset\cdots\subset
V_{n})\in\mathbb{F}^{n}$

where $\dim V_{i}=i$ for all $i$. The relative position of two such flags
$U_{\bullet},V_{\bullet}$ is the unique permutation $w\in\mathfrak{S}_{n}$
such that $\dim(U_{i}\cap V_{j})=|\\{1\leq k\leq i\mid w^{-1}(k)\leq j\\}|$
for all $i,j$.

For any $u\in W$ and any word $\mathbf{w}=(s_{1},s_{2},\dots,s_{m})\in S^{m}$,
not necessarily reduced, we will define an algebraic variety
$\accentset{\circ}{R}_{u,\mathbf{w}}$ over $\mathbb{F}$. When $u=e$, it is

(1.6)
$\accentset{\circ}{R}_{e,\mathbf{w}}=\left\\{(B_{1},\ldots,B_{m})\in\mathcal{B}^{m}\mid
B_{+}\xrightarrow{s_{1}}B_{1}\xrightarrow{s_{2}}\cdots\xrightarrow{s_{m}}B_{m}\xleftarrow{w_{\circ}}B_{-}\right\\}.$

More generally, for $v\in W$, let

(1.7)
$\accentset{\circ}{R}^{(v)}_{e,\mathbf{w}}=\left\\{(B_{1},\ldots,B_{m})\in\mathcal{B}^{m}\mid
v\cdot
B_{+}\xrightarrow{s_{1}}B_{1}\xrightarrow{s_{2}}\cdots\xrightarrow{s_{m}}B_{m}\xleftarrow{vw_{\circ}}B_{-}\right\\}.$

For a specific calculation, see Example 7.3. We show in Section 7 that Theorem
1.9 has the following geometric interpretation.

######  Theorem 1.12.

Suppose that $\mathbb{F}=\mathbb{F}_{q}$ is a finite field with $q$ elements,
where $q$ is a prime power. Then for any Weyl group $W$ of rank $r$ and
Coxeter number $h$, Coxeter word $\mathbf{c}$, and integer $p$ coprime to $h$,
we have

$\displaystyle\left|\accentset{\circ}{R}_{e,\mathbf{c}^{p}}(\mathbb{F}_{q})\right|$
$\displaystyle=\phantom{\sum\limits_{v\in
W}{}}R_{e,\mathbf{c}^{p}}(q)=(q-1)^{r}\mathrm{Cat}_{p}(W;q),$
$\displaystyle\left|\bigsqcup_{v\in
W}\accentset{\circ}{R}^{(v)}_{e,\mathbf{c}^{p}}(\mathbb{F}_{q})\right|$
$\displaystyle=\sum\limits_{v\in
W}R^{(v)}_{e,\mathbf{c}^{p}}(q)=(q-1)^{r}[p]_{q}^{r}.$

###  1.7. Future work

A natural problem would be to generalize our work to the $(q,t)$-level in the
spirit of [GL20, Tri21], where the point count on the left-hand side is
replaced by the _mixed Hodge polynomial_ of the corresponding variety, and the
right-hand side is replaced by the rational $(W,q,t)$-analogs of Catalan
numbers and parking functions; see [GG12].

The dichotomy between $W$-nonnesting objects and $W$-noncrossing objects
appears to be related to a nonabelian Hodge correspondence and a $P=W$
phenomenon for braid Richardson varieties; see [Tri20, Section 4.9]. We hope
to return to this possibility in the future.

Another natural problem would be to extend the construction of rational
noncrossing objects to well-generated complex reflection groups, which still
have a well-defined rational Catalan number [GG12].

### Acknowledgments

We thank Theo Douvropoulos, Eric Sommers, and Dennis Stanton for helpful
conversations regarding character computations. We thank Thomas Gobet for
pointing out the reference [Dye01]. We thank Olivier Dudas and George Lusztig
for responding to questions about the representation theory of Coxeter groups.

##  2\. Type $A$ Combinatorics

As a warm-up, we discuss the structure of Deograms in type $A$, and give
bijections between maximal Deograms and well-known Catalan objects. Throughout
this section, let $W=\mathfrak{S}_{n}$. Recall that $\mathfrak{S}_{n}$ has
rank $r=n-1$ and Coxeter number $h=n$. We concentrate on the _Fuss–Catalan_
case $p=h+1=n+1$ and the _Fuss–Dogolon_ case $p=h-1=n-1$. In both cases, the
number of maximal $\mathbf{c}^{p}$-Deograms is given by the classical Catalan
number:

$|\mathcal{M}_{e,\mathbf{c}^{n+1}}(\mathfrak{S}_{n})|=\mathrm{Cat}_{n}\quad\text{and}\quad|\mathcal{M}_{e,\mathbf{c}^{n-1}}(\mathfrak{S}_{n})|=\mathrm{Cat}_{n-1},$

where $\mathrm{Cat}_{n}=\frac{1}{n+1}\binom{2n}{n}$ and
$\mathbf{c}=(s_{1},s_{2},\dots,s_{n-1})$.

Throughout this section, we omit the proofs, leaving them as exercises for the
interested reader. In Section 8, we will give bijections to known Catalan and
parking objects for general Coxeter groups $W$ and integers $p=kh+1$ with
$k\geq 1$.

###  2.1. The case $p=n+1$: binary search trees, noncrossing matchings, and
noncrossing partitions

Up to commutation moves, the braid word $\mathbf{c}^{n+1}$ can be decomposed
as
$\mathbf{c}^{n+1}=\mathbf{w}^{\prime}_{\circ}\cdot\mathbf{c}^{\ast}\cdot\mathbf{w}^{\prime\prime}_{\circ}$,
where $\mathbf{c}^{\ast}=s_{n-1}\cdots s_{2}s_{1}$, and

$\displaystyle\mathbf{w}^{\prime}_{\circ}\coloneqq
s_{1}\cdot(s_{2}s_{1})\cdots(s_{n-1}\cdots
s_{2}s_{1})\quad\text{and}\quad\mathbf{w}^{\prime\prime}_{\circ}\coloneqq(s_{n-1}\cdots
s_{2}s_{1})\cdot(s_{n-1}\cdots s_{2})\cdots s_{n-1}$

are two reduced words for $w_{\circ}$. In the wiring diagram of
$\mathbf{c}^{n+1}$, $\mathbf{w}^{\prime}_{\circ}$ forms an upright triangle on
the left while $\mathbf{w}^{\prime\prime}_{\circ}$ forms a downright triangle
on the right; see Figure 5.

Following Remark 1.3, we identify elements of
$\mathcal{M}_{e,\mathbf{c}^{n+1}}(\mathfrak{S}_{n})$ with ways to insert $n-1$
elbows into the wiring diagram of $\mathbf{c}^{n+1}$. Recall that to each
elbow $E$ we associate a _colored inversion_ consisting of a reflection
$(i\kern 1.00006ptj)$ and a _color_ $k\in\mathbb{Z}$. Here, $i<j$ are the
labels of the left endpoints of the two strands participating in $E$, and $k$
is the number of times these two wires intersect to the left of $E$.

######  Lemma 2.1.

If
$\mathbf{c}^{n+1}=\mathbf{w}^{\prime}_{\circ}\cdot\mathbf{c}^{\ast}\cdot\mathbf{w}^{\prime\prime}_{\circ}$
as above, then in any maximal $\mathbf{c}^{n+1}$-Deogram $\mathbf{u}$, none of
the elbows of $\mathbf{u}$ appears in $\mathbf{c}^{\ast}$. The elbows
appearing in $\mathbf{w}^{\prime}_{\circ}$ all have color $0$, and those
appearing in $\mathbf{w}^{\prime\prime}_{\circ}$ all have color $2$.

An example is shown in the top row of Figure 6.

Figure 5. The decomposition
$\mathbf{c}^{n+1}=\mathbf{w}^{\prime}_{\circ}\cdot\mathbf{c}^{\ast}\cdot\mathbf{w}^{\prime\prime}_{\circ}$
from Section 2.1. Figure 6. The bijections from Section 2.1: maximal
$\mathbf{c}^{n+1}$-Deograms (first row), binary search trees (second row),
noncrossing partitions (third row), and noncrossing matchings (fourth row).

####  2.1.1. Binary search trees

To a maximal $\mathbf{c}^{n+1}$-Deogram $\mathbf{u}$, we associate a binary
tree $T_{\operatorname{BST}}(\mathbf{u})$ with vertex set $[n]$ as follows:

  * •

for every colored inversion $(i\kern 1.00006ptj)$ of $\mathbf{u}$ of color
$0$, $i$ is a left child of $j$ in $T_{\operatorname{BST}}(\mathbf{u})$; and

  * •

for every colored inversion $\ddot{(i\kern 1.00006ptj)}$ of $\mathbf{u}$ of
color $2$, $j$ is a right child of $i$ in
$T_{\operatorname{BST}}(\mathbf{u})$.

A binary tree $T$ with vertex set $[n]$ is a _binary search tree_ if, for any
node $i$, the nodes in the left (resp., right) subtree of $i$ have labels less
than (resp., greater than) $i$. Such objects are in bijection with the binary
trees on $n$ _un_ labeled vertices; see [Sta15, Figure 1.3].

######  Proposition 2.2.

For each maximal $\mathbf{c}^{n+1}$-Deogram $\mathbf{u}$, the binary tree
$T_{\operatorname{BST}}(\mathbf{u})$ is a binary search tree. The map
$\mathbf{u}\mapsto T_{\operatorname{BST}}(\mathbf{u})$ is a bijection between
maximal $\mathbf{c}^{n+1}$-Deograms and binary search trees with vertex set
$[n]$.

This bijection is illustrated in the first two rows of Figure 6.

####  2.1.2. Noncrossing partitions

Next, given a maximal $\mathbf{c}^{n+1}$-Deogram $\mathbf{u}$, let
$\pi(\mathbf{u})\in\mathfrak{S}_{n}$ be the product of the reflections
corresponding to the colored inversions of $\mathbf{u}$ of color $0$, and let
$\Pi(\mathbf{u})$ be the set partition of $[n]$ given by the cycles of
$\pi(\mathbf{u})$.

######  Proposition 2.3.

For any maximal $\mathbf{c}^{n+1}$-Deogram $\mathbf{u}$, the set partition
$\Pi(\mathbf{u})$ is a noncrossing partition of $[n]$. The map
$\mathbf{u}\mapsto\Pi(\mathbf{u})$ is a bijection between maximal
$\mathbf{c}^{n+1}$-Deograms and noncrossing partitions of $[n]$.

An example is illustrated the third row of Figure 6. For a more general
statement, see Theorem 8.8. Noncrossing partitions appear in [Sta15] as item
160.

######  Remark 2.4.

Applying the construction above to the colored inversions of $\mathbf{u}$ of
color $2$ instead yields the Kreweras complement of $\Pi(\mathbf{u})$.

####  2.1.3. Noncrossing matchings

Finally, let $\mathbf{w}^{\prime}_{\circ}$ be the wiring diagram of
$w_{\circ}$ as above. Label the left endpoints of
$\mathbf{w}^{\prime}_{\circ}$ by $1,2,\dots,n$ bottom-to-top, and label the
right endpoints by $\bar{1},\bar{2},\dots,\bar{n}$ top-to-bottom. Let
$[\bar{n}]\coloneqq\\{\bar{1},\bar{2},\dots,\bar{n}\\}$. We shall consider
noncrossing matchings (item 61 in [Sta15]) of the set $[n]\sqcup[\bar{n}]$
with respect to the cyclic ordering $(\bar{1},1,\bar{2},2,\dots,\bar{n},n)$.
Given a maximal $\mathbf{c}^{n+1}$-Deogram $\mathbf{u}$, let
$\operatorname{m}(\mathbf{u}):[n]\to[\bar{n}]$ be the map obtained by
restricting $\mathbf{u}$ to the $\mathbf{w}^{\prime}_{\circ}$-part of
$\mathbf{c}^{n+1}$.

######  Proposition 2.5.

For every maximal $\mathbf{c}^{n+1}$-Deogram $\mathbf{u}$, the map
$\operatorname{m}(\mathbf{u})$ is a noncrossing matching of
$[n]\sqcup[\bar{n}]$. The map $\mathbf{u}\mapsto\operatorname{m}(\mathbf{u})$
is a bijection between maximal $\mathbf{c}^{n+1}$-Deograms and noncrossing
matchings of $[n]\sqcup[\bar{n}]$.

See the fourth row of Figure 6.

###  2.2. The case $p=n-1$: noncrossing alternating trees

We start with a structural result for maximal $\mathbf{c}^{n-1}$-Deograms,
illustrated in the top row of Figure 7.

######  Lemma 2.6.

In any maximal $\mathbf{c}^{n-1}$-Deogram $\mathbf{u}$, each of the $n-1$
copies of $\mathbf{c}$ contains exactly one elbow. All elbows of $\mathbf{u}$
have color $0$.

Figure 7. The bijection from Section 2.2: maximal $\mathbf{c}^{n-1}$-Deograms
(top row) versus noncrossing alternating trees (bottom row).

Given a maximal $\mathbf{c}^{n-1}$-Deogram $\mathbf{u}$, let
$T^{\mathrm{NC}}_{\operatorname{alt}}(\mathbf{u})$ be the tree with vertex set
$[n]$ containing an edge $\\{i,j\\}$ for each colored inversion $(i\kern
1.00006ptj)$ of $\mathbf{u}$. A tree $T$ with vertex set $[n]$ is
_alternating_ if, upon directing each edge $\\{i,j\\}$ of $T$ from the smaller
number $i$ to the larger number $j$, we find that every vertex is either a
source or a sink. We say that $T$ is _noncrossing_ if we can draw $T$ in the
plane, with the vertices on a line in increasing order and the edges in the
closed half-plane above the line, such that no two edges cross.

######  Proposition 2.7.

For every maximal $\mathbf{c}^{n-1}$-Deogram $\mathbf{u}$, the tree
$T^{\mathrm{NC}}_{\operatorname{alt}}(\mathbf{u})$ is a noncrossing
alternating tree. The map $\mathbf{u}\mapsto
T^{\mathrm{NC}}_{\operatorname{alt}}(\mathbf{u})$ is a bijection between
maximal $\mathbf{c}^{n-1}$-Deograms and noncrossing alternating trees with
vertex set $[n]$.

See Figure 7. Noncrossing alternating trees appear in [Sta15] as item 62.

######  Remark 2.8.

Noncrossing alternating trees have already been related to Deograms in [GL20,
Remark 9.7]. We do not have a direct bijection between these two classes of
Deograms; see Open Problem 2.11(3) below.

###  2.3. Parking functions

Let $\Pi=\\{B_{1},B_{2},\dots,B_{k}\\}$ be a noncrossing partition of $[n]$.
We say that the tuple
$\tilde{\Pi}=\\{(B_{1},L_{1}),(B_{2},L_{2}),\dots,(B_{k},L_{k})\\}$ is a
_labeled noncrossing partition_ , or equivalently, a _noncrossing parking
function_ , if:

  * •

$\\{B_{1},B_{2},\dots,B_{k}\\}$ is a noncrossing partition of $[n]$,

  * •

$\\{L_{1},L_{2},\dots,L_{k}\\}$ is a set partition of $[n]$, which need not be
noncrossing, and

  * •

$|B_{i}|=|L_{i}|$ for all $i=1,2,\dots,k$.

In other words, to each part $B_{i}$ of $B$ we associate a set $L_{i}$ of
$|B_{i}|$-many labels, so that each element of $[n]$ appears as a label
exactly once. Noncrossing parking functions are known to be in bijection with
parking functions; see e.g. [Ede80, ARR15].

Let $v\in\mathfrak{S}_{n}$. Consider a maximal $(\mathbf{c}^{n+1},v)$-Deogram
$\mathbf{u}$. In Section 8.5, we associate to $\mathbf{u}$ a set of _$v$
-twisted colored inversions_. This means we again view $\mathbf{u}$ as a way
to insert $n-1$ elbows into the wiring diagram of $\mathbf{c}^{n+1}$, and for
each elbow $E$, we consider a colored inversion $(i\kern 1.00006ptj)$ with
color $k$ defined in the same way as above. Note that $E$ has a bottom strand
and a top strand. Writing $i$ (resp., $j$) for the left endpoint of the bottom
(resp., top) strand, we need no longer have $i<j$. However, since $\mathbf{u}$
is $v$-distinguished, we must have $v(i)<v(j)$. We set the _$v$ -twisted
color_ $k^{\prime}$ of $(i\kern 1.00006ptj)$ to be $k$ if $i<j$ and $k+1$ if
$i>j$, and refer to the resulting pair $((i\kern 1.00006ptj),k^{\prime})$ as
the _$v$ -twisted colored inversion_ of $\mathbf{u}$. The $v$-twisted colored
inversions of the $16$ Deograms in
$\mathcal{P}_{e,\mathbf{c}^{n+1}}(\mathfrak{S}_{n})$ are shown in Figure 4.

######  Lemma 2.9.

For any maximal $(\mathbf{c}^{n+1},v)$-Deogram $\mathbf{u}$, the $v$-twisted
color of any elbow is either $0$ or $2$.

Let $\mathbf{u}$ be a maximal $(\mathbf{c}^{n+1},v)$-Deogram. Let
$\pi^{(v)}(\mathbf{u})\in\mathfrak{S}_{n}$ be obtained by multiplying all
reflections $(i\kern 1.00006ptj)$ of $v$-twisted color $0$, and let
$\Pi^{(v)}(\mathbf{u})=\\{B_{1},B_{2},\dots,B_{k}\\}$ be the set partition of
$[n]$ given by the cycles of $\pi^{(v)}(\mathbf{u})$. To each part $B_{i}$ of
$\Pi^{(v)}(\mathbf{u})$, we associate a set of labels
$L_{i}\coloneqq\\{v(j)\mid j\in B_{i}\\}$. We denote the resulting noncrossing
parking function by
${\tilde{\Pi}}^{\mathchoice{\raisebox{-3.0pt}{$\displaystyle(v)$}}{\raisebox{-3.0pt}{$\textstyle(v)$}}{\raisebox{-3.0pt}{$\scriptstyle(v)$}}{\raisebox{-3.0pt}{$\scriptscriptstyle(v)$}}}(\mathbf{u})=\\{(B_{1},L_{1}),(B_{2},L_{2}),\dots,(B_{k},L_{k})\\}$.

######  Proposition 2.10.

For any $v\in\mathfrak{S}_{n}$ and maximal $(\mathbf{c}^{n+1},v)$-Deogram
$\mathbf{u}$, the tuple
${\tilde{\Pi}}^{\mathchoice{\raisebox{-3.0pt}{$\displaystyle(v)$}}{\raisebox{-3.0pt}{$\textstyle(v)$}}{\raisebox{-3.0pt}{$\scriptstyle(v)$}}{\raisebox{-3.0pt}{$\scriptscriptstyle(v)$}}}(\mathbf{u})$
is a noncrossing parking function. The map
$\mathbf{u}\mapsto{\tilde{\Pi}}^{\mathchoice{\raisebox{-3.0pt}{$\displaystyle(v)$}}{\raisebox{-3.0pt}{$\textstyle(v)$}}{\raisebox{-3.0pt}{$\scriptstyle(v)$}}{\raisebox{-3.0pt}{$\scriptscriptstyle(v)$}}}(\mathbf{u})$
is a bijection between $\mathcal{P}_{e,\mathbf{c}^{n+1}}(\mathfrak{S}_{n})$
and the set of noncrossing parking functions.

See Figure 4 for an example. See Theorem 8.17 for a uniform generalization to
Coxeter groups and parameters of the form $p=kh+1$.

###  2.4. Open problems

We conclude this section with several purely combinatorial bijective problems
which do not easily follow from our results. Many of them are closely related
to the problem of finding a bijection between noncrossing and nonnesting
objects; see [Wil12, Problem 1].

Let $f_{p,n+p}\in\mathfrak{S}_{n+p}$ be the permutation sending $i\mapsto i+p$
for $1\leq i\leq n$ and $i\mapsto i-n$ for $n+1\leq i\leq n+p$.

######  Open Problem 2.11.

Let $p,n$ be two coprime positive integers.

  1. (1)

Find a bijection between $\mathcal{M}_{e,\mathbf{c}^{p}}(\mathfrak{S}_{n})$
and the set of rational Dyck paths inside a $p\times n$ rectangle.

  2. (2)

Find a bijection between $\mathcal{M}_{e,\mathbf{c}^{p}}(\mathfrak{S}_{n})$
and $\mathcal{M}_{e,(\mathbf{c}^{\prime})^{n}}(\mathfrak{S}_{p})$, where
$\mathbf{c}$ is a Coxeter word in $\mathfrak{S}_{n}$ and $\mathbf{c}^{\prime}$
is a Coxeter word in $\mathfrak{S}_{p}$.

  3. (3)

Find a direct bijection between
$\mathcal{M}_{e,\mathbf{c}^{p}}(\mathfrak{S}_{n})$ and the set of _maximal
$f_{p,n+p}$-Deograms_ of [GL20, Definition 9.3].

  4. (4)

Find a bijection between $\mathcal{P}_{e,\mathbf{c}^{p}}(\mathfrak{S}_{n})$
and the set of _rational parking functions_ as defined in, e.g., [ALW16].

  5. (5)

Find a statistic $\operatorname{stat}$ on
$\mathcal{M}_{e,\mathbf{c}^{p}}(\mathfrak{S}_{n})$ and on
$\mathcal{P}_{e,\mathbf{c}^{p}}(\mathfrak{S}_{n})$ such that

$\mathrm{Cat}_{p}(\mathfrak{S}_{n};q)=\sum_{\mathbf{u}\in\mathcal{M}_{e,\mathbf{c}^{p}}(\mathfrak{S}_{n})}q^{\operatorname{stat}(\mathbf{u})}\quad\text{and}\quad[p]_{q}^{n-1}=\sum_{\mathbf{u}\in\mathcal{P}_{e,\mathbf{c}^{p}}(\mathfrak{S}_{n})}q^{\operatorname{stat}(\mathbf{u})};$

cf. Example 1.10. More generally, do this for an arbitrary Coxeter group $W$.

######  Remark 2.12.

For Open Problem 2.11(3), one can give an indirect recursive bijection between
our maximal $\mathbf{c}^{p}$-Deograms and the maximal $f_{p,n+p}$-Deograms of
[GL20, Definition 9.3] by applying a sequence of _Markov moves_. Namely, it is
known that the braid word $\mathbf{c}^{p}$ and the positive braid lift of
$f_{p,n+p}$ give rise to the same link called the _$(p,n)$ -torus link_.
Moreover, these braids can be related to each other by a sequence of
_positive_ Markov moves, i.e., braid moves and positive (de)stabilizations.
The associated braid varieties change in a predictable way (cf. [CGGS21]), and
one can check that each positive Markov move induces a bijection on the
associated sets of maximal Deograms. The problem of finding a direct, non-
recursive bijection remains open.

######  Remark 2.13.

Whereas maximal $\mathbf{c}^{p}$-Deograms are in bijection with maximal
$f_{p,n+p}$-Deograms, maximal $(\mathbf{c}^{p},v)$-Deograms appear to be
counted by other _positroid Catalan numbers_ [GL21], enumerating maximal
$f_{v,p,n+p}$-Deograms for other permutations
$f_{v,p,n+p}\in{\mathfrak{S}}_{n+p}$. Explicitly, when $n<p$, the permutation
$f_{v,p,n+p}$ corresponds to the bounded affine permutation
$\tilde{f}_{v,p,n+p}\coloneqq\tilde{v}\tilde{f}_{p,n+p}\tilde{v}^{-1}$, where

  * •

$\tilde{f}_{p,n+p}$ is the bounded affine permutation corresponding to
$f_{p,n+p}$, and

  * •

$\tilde{v}:\mathbb{Z}\to\mathbb{Z}$ is an $(n+p)$-periodic affine permutation
lifting $v$, sending $i\mapsto v(i)$ for $1\leq i\leq n$ and $i\mapsto i$ for
$n+1\leq i\leq n+p$.

In particular, when the affine permutation $\tilde{f}_{v,p,n+p}$ is not
bounded, we conjecture that the set of $(\mathbf{c}^{p},v)$-Deograms is empty.

##  3\. Coxeter Groups

Let $W$ be a finite Coxeter group: that is, a finite group for which we can
find a subset $S\subset W$ and a group presentation

(3.1) $\displaystyle W=\left\langle s\in S\mid(st)^{m(s,t)}=1\right\rangle$

in which $m(s,t)\geq 1$ and $m(s,s)=1$ for all $s,t\in S$. We say that $W$ is
_irreducible_ if and only if it is not a product of smaller Coxeter groups,
yet also not the trivial group. Henceforth, we always assume that $W$ is
irreducible.

The _rank_ of $W$ is the integer $r\coloneqq|S|$. We refer to elements of $S$
as _simple reflections_. For an arbitrary element $w\in W$, the _length_
$\ell(w)$ of $w$ is the smallest integer $m\geq 0$ such that $w$ can be
expressed as a product of $m$ simple reflections, possibly with repetition.
There is a unique element of maximal length called the _longest element_ ,
which we denote by $w_{\circ}\in W$. For $w\in W$ and $s\in S$, we write
$ws<w$ if $\ell(ws)<\ell(w)$ and $ws>w$ if $\ell(ws)>\ell(w)$. The _weak
order_ on $W$ is the partial order formed by the transitive closure of these
relations.

A (standard) _Coxeter element_ of $W$ with respect to $S$ is an element formed
by taking the product over all simple reflections in some ordering. It is
known that all Coxeter elements are conjugate. Their common order is called
the _Coxeter number_ of $W$ and denoted $h$.

A (general) _reflection_ is an element of the form $s^{u}\coloneqq usu^{-1}$
for some $s\in S$ and $u\in W$. We write $T$ for the set of all reflections:
that is,

$\displaystyle T\coloneqq\\{s^{u}\mid(s,u)\in S\times W\\}.$

The _reflection length_ $\ell_{T}(w)$ of $w$ is the smallest integer $m\geq 0$
such that $w$ can be expressed as a product of $m$ general reflections.

Every Coxeter group admits a faithful representation on a (finite-dimensional)
real vector space $V$, which sends each reflection in $W$ to a hyperplane
reflection in $V$. Such a representation is called a _reflection
representation_ of $W$. After possibly passing to a quotient, we can assume
that the only $W$-invariant vector is zero: that is, $V^{W}=0$. In this case,
$\dim(V)=r$, and by a theorem of Chevalley, the ring of $W$-invariant
polynomials on $V$ is freely generated by $r$ homogeneous polynomials.

The _degrees_ of $W$ are the degrees $d_{1}\leq d_{2}\leq\cdots\leq d_{r}$ of
these polynomials, which do not depend on the choice of reflection
representation. The _exponents_ of $W$ are the integers $e_{i}=d_{i}-1$.
Recall from (1.1) that for any positive integer $p$ coprime to $h$, we set

$\displaystyle\mathrm{Cat}_{p}(W)\coloneqq\prod_{i=1}^{r}\frac{p+(pe_{i}\operatorname{mod}{h})}{d_{i}},$

where $0\leq(pe_{i}\operatorname{mod}{h})<h$ is the integer in that range
congruent to $pe_{i}$ modulo $h$.

##  4\. Words and Subwords

###  4.1. Distinguished subwords

A _word_ is any finite sequence $\mathbf{w}=(s_{1},s_{2},\ldots,s_{m})$ of
elements of $S$, possibly with repetition. If $w=s_{1}s_{2}\cdots s_{m}$, then
we refer to $\mathbf{w}$ as a _$w$ -word_, and if $m=\ell(w)$, then we say it
is _reduced_. We say that a word $\mathbf{c}$ is a _Coxeter word_ if it is an
ordering of $S$.

A _subword_ of $\mathbf{w}$ is a sequence
$\mathbf{u}=(u_{1},u_{2},\dots,u_{m})$ in which $u_{i}\in\\{s_{i},e\\}$ for
all $i$. For any such sequence, we set $u_{(i)}=u_{1}u_{2}\cdots u_{i}\in W$.
If $u_{(m)}=u$, then we refer to $\mathbf{u}$ as a _$u$ -subword_ of
$\mathbf{w}$.

######  Definition 4.1 ([Deo85, MR04]).

Let $u\in W$. We say that a $u$-subword $\mathbf{u}$ of $\mathbf{w}$ is
_distinguished_ if $u_{(i)}\leq u_{(i-1)}s_{i}$ for all $i$. We write
$\mathcal{D}_{u,\mathbf{w}}(W)$ (or $\mathcal{D}_{u,\mathbf{w}}$ for short)
for the set of distinguished $u$-subwords of $\mathbf{w}$. For any $u$-subword
$\mathbf{u}$ of $\mathbf{w}$, we write

$\displaystyle\operatorname{e}_{\mathbf{u}}$ $\displaystyle=|\\{i\in[m]\mid
u_{i}=e\\}|,$ $\displaystyle\operatorname{d}_{\mathbf{u}}$
$\displaystyle=|\\{i\in[m]\mid u_{(i)}<u_{(i-1)}\\}|.$

We write
$\mathcal{D}_{u,\mathbf{w}}^{k}\coloneqq\\{\mathbf{u}\in\mathcal{D}_{u,\mathbf{w}}\mid\operatorname{e}_{\mathbf{u}}=k\\}$.
In the special case where
$k=\min_{\mathbf{u}\in\mathcal{D}_{u,\mathbf{w}}}\operatorname{e}_{\mathbf{u}}$,
we write
$\mathcal{M}_{u,\mathbf{w}}(W)=\mathcal{M}_{u,\mathbf{w}}\coloneqq\mathcal{D}_{u,\mathbf{w}}^{k}$.
For $u=e$, the minimal value $k$ is given in Proposition 4.8 below.

We give an equivalent characterization of distinguished subwords among the set
of all subwords using reflections. A _colored reflection_ is a pair $(t,k)\in
T\times\mathbb{Z}_{\geq 0}$, i.e., a reflection $t$ decorated by a nonnegative
integer $k$. Given a subword $\mathbf{u}=(u_{1},u_{2},\cdots,u_{m})$ of a word
$\mathbf{w}=(s_{1},s_{2},\ldots,s_{m})$ and an index $j\in[m]$, we obtain a
colored reflection

(4.1) $\displaystyle
t_{j}(\mathbf{u})\coloneqq(s_{j}^{u_{(j)}},k_{j}),\quad\text{where }\quad
k_{j}\coloneqq\left|\left\\{1\leq i<j\mid
s_{i}^{u_{(i)}}=s_{j}^{u_{(j)}}\text{ and }u_{i}\neq e\right\\}\right|.$

For brevity in examples, we may also record the color $k$ using $k$ dots above
the reflection. See Remark 1.3 for an alternative description of colored
reflections in type $A$.

######  Example 4.2.

For $W=\mathfrak{S}_{2}=\\{e,s\\}$ and $\mathbf{u}=(s,s,s)$, we have
$t_{1}(\mathbf{u})=(s,0)=s$, $t_{2}(\mathbf{u})=(s,1)=\dot{s}$, and
$t_{3}(\mathbf{u})=(s,2)=\ddot{s}$.

######  Definition 4.3.

If $\mathbf{w}=(s_{1},s_{2},\dots,s_{m})$ is a word and $\mathbf{u}$ is a
subword of $\mathbf{w}$, then we set

$\displaystyle\mathrm{inv}(\mathbf{u})$
$\displaystyle\coloneqq\left(t_{1}(\mathbf{u}),t_{2}(\mathbf{u}),\dots,t_{m}(\mathbf{u})\right).$

We write $\mathrm{inv}_{e}(\mathbf{u})$ for the subsequence of
$\mathrm{inv}(\mathbf{u})$ obtained by restricting to the indices $j$ for
which $u_{j}=e$. We also write
$\overline{\mathrm{inv}}(\mathbf{u})\coloneqq\left(s_{1}^{u_{(1)}},s_{2}^{u_{(2)}},\dots,s_{m}^{u_{(m)}}\right)$
(resp., $\overline{\mathrm{inv}}_{e}(\mathbf{u})$) for the sequence obtained
from $\mathrm{inv}(\mathbf{u})$ (resp., $\mathrm{inv}_{e}(\mathbf{u})$) by
forgetting the colors.

######  Proposition 4.4.

A subword $\mathbf{u}$ of a word $\mathbf{w}$ is distinguished if and only if
each colored reflection in $\mathrm{inv}_{e}(\mathbf{u})$ has even color.

###### Proof.

This follows directly from the definitions. ∎

######  Example 4.5.

Let $W=\mathfrak{S}_{5}$, the Weyl group of type $A_{4}$,
$c=s_{1}s_{2}s_{3}s_{4}$, and $\mathbf{c}=(s_{1},s_{2},s_{3},s_{4})$. Then
$\left|\mathcal{M}_{e,\mathbf{c}^{3}}\right|=7$, which is a rational
$W$-Catalan number for $A_{4}$. The $7$ elements of
$\mathcal{M}_{e,\mathbf{c}^{3}}$ are illustrated in Figure 2. Each element
$\mathbf{u}$ gives a decomposition of $c^{3}$ as a product of reflections in
$\overline{\mathrm{inv}}_{e}(\mathbf{u})$. For example, the bottom row in
Figure 2 decomposes $c^{3}=(1\kern 1.00006pt4\kern 1.00006pt2\kern
1.00006pt5\kern 1.00006pt3)$ as the product $(1\kern 1.00006pt2)(2\kern
1.00006pt3)(1\kern 1.00006pt4)(2\kern 1.00006pt5)$.

######  Remark 4.6.

We explain how to recover a subword $\mathbf{u}\in\mathcal{D}_{e,\mathbf{w}}$
from the corresponding sequence $\mathrm{inv}_{e}(\mathbf{u})$ (cf. [PS15,
Remark 3.5]). Read the letters in $\mathbf{w}=(s_{1},s_{2},\ldots,s_{m})$ from
left to right. For a given position $j$, tentatively set $u_{j}=s_{j}$ and
compute $(s_{j}^{u_{(j)}},k)$, where $k$ is defined as in (4.1). If
$(s_{j}^{u_{(j)}},k)$ is the next unread colored reflection in
$\mathrm{inv}_{e}(\mathbf{u})$, then we set $u_{j}=e$. Otherwise, we keep
$u_{j}=s_{j}$.

######  Proposition 4.7.

Let $\mathbf{w}$ be a $w$-word, and let $\mathbf{u}$ be a $u$-subword of
$\mathbf{w}$. Then

$\displaystyle\prod_{t\in\overline{\mathrm{inv}}_{e}(\mathbf{u})}t=wu^{-1},$

where the product is taken from left to right.

###### Proof.

Indeed, it follows from Definition 4.3 that
$\left(\prod_{t\in\overline{\mathrm{inv}}_{e}(\mathbf{u})}t\right)^{-1}w=u$. ∎

######  Proposition 4.8.

Let $\mathbf{w}=(s_{1},s_{2},\ldots,s_{m})$ be a $w$-word. Then

$\ell_{T}(w)=\min_{\mathbf{u}\in\mathcal{D}_{e,\mathbf{w}}}\operatorname{e}_{\mathbf{u}}.$

###### Proof.

When $\mathbf{w}$ is a reduced word for $w$, the result follows from [Dye01,
Theorem 1.3]; see also [BDSW14]. Suppose the word $\mathbf{w}$ is not reduced.
Let
$\tilde{\ell}(\mathbf{w})\coloneqq\min_{\mathbf{u}\in\mathcal{D}_{e,\mathbf{w}}}\operatorname{e}_{\mathbf{u}}$.
By Corollary 5.2, proved independently in the next section,
$\tilde{\ell}(\mathbf{w})$ is invariant under applying braid and commutation
moves to $\mathbf{w}$. (See the proof of [Rie08, Proposition 7.2] for an
explicit bijection.) So we may assume that
$\mathbf{w}=(\mathbf{w}_{1},s,s,\mathbf{w}_{2})$ for some words
$\mathbf{w}_{1},\mathbf{w}_{2}$ and $s\in S$.

Let $\mathbf{w}^{\prime}\coloneqq(\mathbf{w}_{1},s,\mathbf{w}_{2})$ and
$\mathbf{w}^{\prime\prime}\coloneqq(\mathbf{w}_{1},\mathbf{w}_{2})$. Let
$w^{\prime},w^{\prime\prime}\in W$ be the corresponding Weyl group elements.
We have $w=w^{\prime\prime}$ and $w^{\prime}=wt$ for some reflection $t\in T$.
It follows that
$\ell_{T}(w)=\min\left(\ell_{T}(w^{\prime})+1,\ell_{T}(w^{\prime\prime})\right)$.
On the other hand, if
$\mathbf{u}^{\prime\prime}=(\mathbf{u}_{1},\mathbf{u}_{2})\in\mathcal{D}_{e,\mathbf{w}^{\prime\prime}}$
then
$\mathbf{u}\coloneqq(\mathbf{u}_{1},s,s,\mathbf{u}_{2})\in\mathcal{D}_{e,\mathbf{w}}$
satisfies
$\operatorname{e}_{\mathbf{u}}=\operatorname{e}_{\mathbf{u}^{\prime\prime}}$.
Similarly, if
$\mathbf{u}^{\prime}=(\mathbf{u}_{1},x,\mathbf{u}_{2})\in\mathcal{D}_{e,\mathbf{w}^{\prime}}$,
where $x\in\\{e,s\\}$, then either
$\mathbf{u}\coloneqq(\mathbf{u}_{1},x,e,\mathbf{u}_{2})$ or
$\mathbf{u}\coloneqq(\mathbf{u}_{1},e,x,\mathbf{u}_{2})$ is an element of
$\mathcal{D}_{e,\mathbf{w}}$ satisfying
$\operatorname{e}_{\mathbf{u}}=\operatorname{e}_{\mathbf{u}^{\prime}}+1$. This
shows
$\tilde{\ell}(\mathbf{w})\leq\min\left(\tilde{\ell}(\mathbf{w}^{\prime})+1,\tilde{\ell}(\mathbf{w}^{\prime\prime})\right)$.
Conversely, any element $\mathbf{u}\in\mathcal{M}_{e,\mathbf{w}}$ must be of
the form $(\mathbf{u}_{1},s,s,\mathbf{u}_{2})$,
$(\mathbf{u}_{1},s,e,\mathbf{u}_{2})$, or
$(\mathbf{u}_{1},e,s,\mathbf{u}_{2})$, which implies
$\tilde{\ell}(\mathbf{w})\geq\min\left(\tilde{\ell}(\mathbf{w}^{\prime})+1,\tilde{\ell}(\mathbf{w}^{\prime\prime})\right)$.
By induction, we get $\ell_{T}(w)=\tilde{\ell}(\mathbf{w})$. ∎

######  Corollary 4.9.

If $\mathbf{c}$ is a Coxeter word and $p$ an integer coprime to $h$, then

$\displaystyle
r=\min_{\mathbf{u}\in\mathcal{D}_{e,\mathbf{c}^{p}}}\operatorname{e}_{\mathbf{u}}.$

###### Proof.

Let $c\in W$ be the Coxeter element corresponding to $\mathbf{c}$. It is known
that $\ell_{T}(c^{p})=r$ [RRS17, Theorem 1.3]. (If $W$ is a Weyl group, then
$c^{p}$ is conjugate to $c$, but this is not necessarily true when $W$ is a
Coxeter group that is not a Weyl group.) Applying Proposition 4.8 to
$w=\mathbf{c}^{p}$ and $u=e$ shows that $\operatorname{e}_{\mathbf{u}}=r$ for
all $\mathbf{u}\in\mathcal{M}_{e,\mathbf{c}^{p}}$. ∎

######  Remark 4.10.

Proposition 4.7 implies more generally that for a $w$-word $\mathbf{w}\in
S^{m}$ and $u\in W$, we have
$\ell_{T}(wu^{-1})\leq\min_{\mathbf{u}\in\mathcal{D}_{u,\mathbf{w}}}\operatorname{e}_{\mathbf{u}}$.
However, the analog of Proposition 4.8 does not hold in this generality, as
mentioned in [GL20, Remark 9.4]: For $u=s_{2}$ and
$\mathbf{w}=(s_{1},s_{2},s_{3},s_{2},s_{1})$ in $\mathfrak{S}_{4}$, we have
$\ell_{T}(wu^{-1})=2$, but
$\min_{\mathbf{u}\in\mathcal{D}_{u,\mathbf{w}}}\operatorname{e}_{\mathbf{u}}=4$.

###  4.2. The Deodhar recurrence

Henceforth, given a word $\mathbf{w}=(s_{1},s_{2},\dots,s_{m})$ and $s\in S$,
we write $\mathbf{w}\mathbf{s}\coloneqq(s_{1},s_{2},\dots,s_{m},s)$. The
distinguished subwords of $\mathbf{w}$ obey a certain recurrence due to
Deodhar.

######  Proposition 4.11 ([Deo85, Lemma 5.2]).

Let $\mathbf{w}$ be a word, let $u\in W$, and let $s\in S$. Then for all $k$,
we have a natural bijection

$\displaystyle\mathcal{D}_{u,\mathbf{w}\mathbf{s}}^{k}\simeq\begin{cases}\mathcal{D}_{us,\mathbf{w}}^{k}&\text{if
$us<u$},\\\
\mathcal{D}_{us,\mathbf{w}}^{k}\sqcup\mathcal{D}_{u,\mathbf{w}}^{k-1}&\text{if
$us>u$}.\end{cases}$

###### Proof.

Let $\mathbf{w}=(s_{1},s_{2},\dots,s_{m})$, $s\in S$, and
$\mathbf{w}\mathbf{s}\coloneqq(s_{1},s_{2},\dots,s_{m},s)$. Let $\mathbf{u}$
be a distinguished $u$-subword of $\mathbf{w}\mathbf{s}$. If $us<u$, then a
distinguished subword of $\mathbf{w}\mathbf{s}$ cannot satisfy
$u_{(m)}=u_{(m+1)}=u$, so it must satisfy $u_{(m)}=us$. This gives a bijection
$\mathcal{D}_{u,\mathbf{w}\mathbf{s}}^{k}\simeq\mathcal{D}_{us,\mathbf{w}}^{k}$.
If instead $us>u$, then either $u_{(m)}=us$, in which case $u_{(m+1)}=u$, or
else $u_{(m)}=u$, in which case $u_{(m+1)}=u$ as well. This gives a bijection
$\mathcal{D}_{u,\mathbf{w}\mathbf{s}}^{k}\simeq\mathcal{D}_{us,\mathbf{w}}^{k}\sqcup\mathcal{D}_{u,\mathbf{w}}^{k-1}$.
∎

In analogy with this _Deodhar recurrence_ on distinguished subwords of
$\mathbf{w}$, we define the _$R$ -polynomials_ $R_{u,\mathbf{w}}(q)$ for all
$u\in W$ as follows. For the empty word
$\mathbf{w}={\boldsymbol{\varnothing}}$, set

(4.2) $\displaystyle
R_{u,{\boldsymbol{\varnothing}}}(q)\coloneqq\begin{cases}1&\text{if $u=e$},\\\
0&\text{if $u\neq e$}.\end{cases}$

Assume that $\mathbf{w}=(s_{1},s_{2},\dots,s_{m-1})$ is a word for which the
polynomials $R_{u,\mathbf{w}}(q)$ have already been defined. Let $s\in S$ and
$\mathbf{w}\mathbf{s}\coloneqq(s_{1},s_{2},\dots,s_{m-1},s)$ as before. Set

(4.3) $\displaystyle
R_{u,\mathbf{w}\mathbf{s}}(q)\coloneqq\begin{cases}R_{us,\mathbf{w}}(q)&\text{if
$us<u$},\\\ qR_{us,\mathbf{w}}(q)+(q-1)R_{u,\mathbf{w}}(q)&\text{if
$us>u$}.\end{cases}$

For reduced words $\mathbf{w}$, the polynomials $R_{u,\mathbf{w}}(q)$ were
originally defined by Kazhdan–Lusztig in [KL79, KL80] using the Hecke algebra
of $W$; see Proposition 5.1.

######  Corollary 4.12.

For each word $\mathbf{w}$ and $u\in W$, we have

(4.4) $\displaystyle
R_{u,\mathbf{w}}(q)=\sum_{\mathbf{u}\in\mathcal{D}_{u,\mathbf{w}}}(q-1)^{\operatorname{e}_{\mathbf{u}}}q^{\operatorname{d}_{\mathbf{u}}}.$

In particular, we also have

(4.5) $\displaystyle\lim_{q\to
1}\frac{1}{(q-1)^{\ell_{T}(w)}}{R_{e,\mathbf{w}}(q)}=\left|\mathcal{M}_{e,\mathbf{w}}\right|$

by Corollary 4.9.

######  Example 4.13.

Let $W=\mathfrak{S}_{2}=\\{e,s\\}$. Then (4.3) gives

$\displaystyle R_{e,{\boldsymbol{\varnothing}}}(q)$ $\displaystyle=1,$
$\displaystyle R_{e,(s)}(q)$ $\displaystyle=q-1,$ $\displaystyle R_{s,(s)}$
$\displaystyle=1,$ $\displaystyle R_{e,(s,s)}(q)$ $\displaystyle=q^{2}-q+1,$
$\displaystyle R_{s,(s,s)}(q)$ $\displaystyle=q-1,$ $\displaystyle
R_{e,(s,s,s)}(q)$ $\displaystyle=(q-1)(q^{2}+1).$

On the other hand, $\mathcal{D}_{e,(s,s,s)}=\\{(e,e,e),(e,s,s),(s,s,e)\\}$ and

$\displaystyle\operatorname{e}_{(e,e,e)}$ $\displaystyle=3,$
$\displaystyle\operatorname{d}_{(e,e,e)}$ $\displaystyle=0,$
$\displaystyle\operatorname{e}_{(e,s,s)}$ $\displaystyle=1,$
$\displaystyle\operatorname{d}_{(e,s,s)}$ $\displaystyle=1,$
$\displaystyle\operatorname{e}_{(s,s,e)}$ $\displaystyle=1,$
$\displaystyle\operatorname{d}_{(s,s,e)}$ $\displaystyle=1.$

Therefore,

$\displaystyle\sum_{\mathbf{u}\in\mathcal{D}_{e,(s,s,s)}}(q-1)^{\operatorname{e}_{\mathbf{u}}}q^{\operatorname{d}_{\mathbf{u}}}$
$\displaystyle=(q-1)^{3}+2(q-1)q=(q-1)(q^{2}+1),$

verifying the first claim of Corollary 4.12.

Moreover, $\mathcal{M}_{e,(s,s,s)}=\left\\{(e,s,s),(s,s,e)\right\\}$ and
$\lim_{q\to 1}\frac{1}{q-1}R_{u,(s,s,s)}(q)=2=\mathrm{Cat}(\mathfrak{S}_{2})$,
verifying the second claim of Corollary 4.12.

###  4.3. The twisted Deodhar recurrence

For any $v\in W$, there is a generalization of Definition 4.1:

######  Definition 4.14.

We say that a subword $\mathbf{u}$ of a word $\mathbf{w}$ is _$v$
-distinguished_ if $vu_{(i)}\leq vu_{(i-1)}s_{i}$ for each $i\in[m]$.
Generalizing $\operatorname{d}_{\mathbf{u}}$, we write
$\operatorname{d}^{(v)}_{\mathbf{u}}$ for the number of $i\in[m]$ such that
$vu_{(i)}<vu_{(i-1)}$.

We write $\mathcal{D}^{(v)}_{u,\mathbf{w}}$ for the set of $v$-distinguished
$u$-subwords of $\mathbf{w}$. As before, we write
$\mathcal{D}^{(v),k}_{u,\mathbf{w}}\subseteq\mathcal{D}^{(v)}_{u,\mathbf{w}}$
for the subset of elements $\mathbf{u}$ such that
$\operatorname{e}_{\mathbf{u}}=k$. In the special case where
$k=\max_{\mathbf{u}\in\mathcal{D}^{(v)}_{u,\mathbf{w}}}\operatorname{e}_{\mathbf{u}}$,
we write
$\mathcal{M}^{(v)}_{u,\mathbf{w}}=\mathcal{D}^{(v),k}_{u,\mathbf{w}}$.

Proposition 4.11 generalizes to a bijection

$\displaystyle\mathcal{D}_{u,\mathbf{w}\mathbf{s}}^{(v),k}\simeq\begin{cases}\mathcal{D}_{us,\mathbf{w}}^{(v),k}&\text{if
$vus<vu$},\\\
\mathcal{D}_{us,\mathbf{w}}^{(v),k}\sqcup\mathcal{D}_{u,\mathbf{w}}^{(v),k-1}&\text{if
$vus>vu$}.\end{cases}$

As before, we define polynomials $R^{(v)}_{u,\mathbf{w}}(q)$ by induction. Set
$R^{(v)}_{u,{\boldsymbol{\varnothing}}}(q)\coloneqq
R_{u,{\boldsymbol{\varnothing}}}(q)$, and for any word $\mathbf{w}$ and $s\in
S$, set

(4.6)
$\displaystyle{R^{(v)}_{u,\mathbf{w}\mathbf{s}}}(q)=\begin{cases}{R^{(v)}_{us,\mathbf{w}}}(q)&\text{if
$vus<vu$}\\\
{qR^{(v)}_{us,\mathbf{w}}(q)+(q-1)R^{(v)}_{u,\mathbf{w}}(q)}&\text{if
$vus>vu$}.\end{cases}$

Then Corollary 4.12 generalizes to the identity

$\displaystyle{R^{(v)}_{u,\mathbf{w}}}(q)=\sum_{\mathbf{u}\in\mathcal{D}^{(v)}_{u,\mathbf{w}}}(q-1)^{\operatorname{e}_{\mathbf{u}}}q^{\operatorname{d}^{(v)}_{\mathbf{u}}}.$

##  5\. The Hecke Algebra

###  5.1. Preliminaries

As before, $W$ is an arbitrary finite Coxeter group and $S\subseteq W$ is a
system of simple reflections. Let $A=\mathbb{Z}[q^{\pm 1}]$. The _Hecke
algebra_ of $(W,S)$ is the $A$-algebra $\mathcal{H}_{W}$ freely generated by
symbols $T_{w}$ for $w\in W$, modulo the relations

(5.1) $\displaystyle T_{w}T_{s}=\begin{cases}qT_{ws}+(q-1)T_{w}&\text{if
$ws<w$},\\\ T_{ws}&\text{if $ws>w$},\end{cases}$

for all $w\in W$ and $s\in S$. The goal of this section is to relate the
$R$-polynomials $R_{u,\mathbf{w}}(q)$ and their twisted versions
$R^{(v)}_{u,\mathbf{w}}(q)$ to the values of appropriate elements of
$\mathcal{H}_{W}$ under certain $A$-linear traces.

The Hecke algebra specializes to $\mathbb{Z}[W]$, in the sense that there is a
ring isomorphism $\mathcal{H}_{W}/(q-1)\xrightarrow{\sim}\mathbb{Z}[W]$ that
sends $T_{w}\mapsto w$ for all $w$. It follows that $\mathcal{H}_{W}$ forms a
free $A$-module with basis $\\{T_{w}\\}_{w\in W}$. Furthermore, there is an
involutive ring automorphism $D:\mathcal{H}_{W}\to\mathcal{H}_{W}$ defined by
$D(q)=q^{-1}$ and $D(T_{w})=T_{w^{-1}}^{-1}$ for all $w\in W$, so we find that
$\\{T_{w}^{-1}\\}_{w\in W}$ forms another free $A$-basis of $\mathcal{H}_{W}$.
Note that $D$ is _not_ itself $A$-linear.

###  5.2. $R$-polynomials via the Hecke algebra

For any word $\mathbf{w}=(s_{1},s_{2},\dots,s_{m})$, we set
$T_{\mathbf{w}}\coloneqq T_{s_{1}}T_{s_{2}}\cdots T_{s_{m}}$. Note that if
$\mathbf{w}$ is a reduced $w$-word, then $T_{\mathbf{w}}=T_{w}$.

######  Proposition 5.1.

For any word $\mathbf{w}$ and $v\in W$, we have

(5.2) $\displaystyle T_{v}D(T_{\mathbf{w}})=q^{\ell(v)}\sum_{u\in
W}R^{(v)}_{u,\mathbf{w}}(q^{-1})q^{-\ell(vu)}T_{vu}.$

###### Proof.

We induct on the length of $\mathbf{w}$. The base case
$\mathbf{w}={\boldsymbol{\varnothing}}$ is satisfied by (4.2). Suppose the
result holds for $\mathbf{w}=(s_{1},\ldots,s_{m})$. To prove it for
$\mathbf{w}\mathbf{s}=(s_{1},\ldots,s_{m},s)$, write

$\displaystyle T_{v}D(T_{\mathbf{w}\mathbf{s}})=q^{\ell(v)}\sum_{u\in
W}Q^{(v)}_{u,\mathbf{w}\mathbf{s}}(q^{-1})q^{-\ell(vu)}T_{vu}$

for some $Q^{(v)}_{u,\mathbf{w}}(q)\in\mathbb{Z}[q^{\pm 1}]$. Since
$D(T_{\mathbf{w}\mathbf{s}})=D(T_{\mathbf{w}})D(T_{s})$, we compute using
(5.1) that

$\displaystyle q^{-\ell(v)}T_{v}D(T_{\mathbf{w}})$
$\displaystyle=q^{-\ell(v)}T_{v}D(T_{\mathbf{w}\mathbf{s}})D(T_{s})^{-1}$
$\displaystyle=\sum_{u\in
W}Q^{(v)}_{u,\mathbf{w}\mathbf{s}}(q^{-1})q^{-\ell(vu)}T_{vu}T_{s}$
$\displaystyle=\sum_{\begin{subarray}{c}x\in W\\\
vxs<vx\end{subarray}}Q^{(v)}_{x,\mathbf{w}\mathbf{s}}(q^{-1})q^{-\ell(vx)}qT_{vxs}+\sum_{\begin{subarray}{c}x\in
W\\\
vxs<vx\end{subarray}}Q^{(v)}_{x,\mathbf{w}\mathbf{s}}(q^{-1})q^{-\ell(vx)}(q-1)T_{vx}$
$\displaystyle\qquad+\sum_{\begin{subarray}{c}u\in W\\\
vus>vu\end{subarray}}Q^{(v)}_{u,\mathbf{w}\mathbf{s}}(q^{-1})q^{-\ell(vu)}T_{vus}$
$\displaystyle=\sum_{\begin{subarray}{c}u\in W\\\
vus<vu\end{subarray}}Q^{(v)}_{u,\mathbf{w}\mathbf{s}}(q^{-1})q^{-\ell(vus)}T_{vus}+\sum_{\begin{subarray}{c}u\in
W\\\
vus>vu\end{subarray}}(q-1)Q^{(v)}_{us,\mathbf{w}\mathbf{s}}(q^{-1})q^{-\ell(vus)}T_{vus}$
$\displaystyle\qquad+\sum_{\begin{subarray}{c}u\in W\\\
vus>vu\end{subarray}}qQ^{(v)}_{u,\mathbf{w}\mathbf{s}}(q^{-1})q^{-\ell(vus)}T_{vus}.$

At the same time, by the inductive hypothesis,

$\displaystyle q^{-\ell(v)}T_{v}D(T_{\mathbf{w}})=\sum_{u\in
W}R^{(v)}_{u,\mathbf{w}}(q^{-1})q^{-\ell(vu)}T_{vu}=\sum_{u\in
W}R^{(v)}_{us,\mathbf{w}}(q^{-1})q^{-\ell(vus)}T_{vus}.$

Equating coefficients, we find that:

  1. (1)

If $vus<vu$, then
$Q^{(v)}_{u,\mathbf{w}\mathbf{s}}(q^{-1})=R^{(v)}_{us,\mathbf{w}}(q^{-1})$.

  2. (2)

If $vus>vu$, then
$(q-1)Q^{(v)}_{us,\mathbf{w}\mathbf{s}}(q^{-1})+qQ^{(v)}_{u,\mathbf{w}\mathbf{s}}(q^{-1})=R^{(v)}_{us,\mathbf{w}}(q^{-1})$.

We observe that in case (2), $(vus)s<vus$, so by case (1),
$Q^{(v)}_{us,\mathbf{w}\mathbf{s}}(q^{-1})=R^{(v)}_{u,\mathbf{w}}(q^{-1})$.
Therefore, we can rewrite case (2) as:

  1. (2)

If $us>u$, then
$Q^{(v)}_{u,\mathbf{w}\mathbf{s}}(q^{-1})=q^{-1}R^{(v)}_{us,\mathbf{w}}(q^{-1})+(q^{-1}-1)R^{(v)}_{u,\mathbf{w}}(q^{-1})$.

By (4.6), we deduce that
$Q^{(v)}_{u,\mathbf{w}\mathbf{s}}(q)=R_{u,\mathbf{w}\mathbf{s}}(q)$ for all
$u$, completing the induction. ∎

For reduced $\mathbf{w}$, the following result is usually taken to be the
_definition_ of the $R$-polynomials $R_{u,\mathbf{w}}(q)$; cf. [KL79,
(2.0.a)].

######  Corollary 5.2.

For any word $\mathbf{w}$ and $u\in W$, we have

$\displaystyle D(T_{\mathbf{w}})=\sum_{u\in
W}R_{u,\mathbf{w}}(q^{-1})q^{-\ell(u)}T_{u}.$

###  5.3. Two traces

If $A$ is any commutative ring and $H$ is any $A$-algebra, then a _trace_ on
$H$ is an $A$-linear map $\tau:H\to A$ such that $\tau(ab)=\tau(ba)$ for all
$a,b\in H$. Taking $A=\mathbb{Z}[q^{\pm 1}]$ and $H=\mathcal{H}_{W}$, let
$\tau^{+},\tau^{-}:\mathcal{H}_{W}\to A$ be the traces defined $A$-linearly
by:

$\displaystyle\tau^{\pm}(T_{w}^{\pm 1})$
$\displaystyle\coloneqq\begin{cases}1&w=e,\\\ 0&w\neq
e\end{cases}\qquad\text{for $w\in W$.}$

We have the following identities [GL20, (2.10)] for $u,v\in W$:

(5.3) $\tau^{\pm}(T_{u}^{\pm 1}T_{v^{-1}}^{\pm
1})=\begin{cases}q^{\pm\ell(u)}&\text{if $u=v$;}\\\ 0&\text{if $u\neq
v$.}\end{cases}$

So Proposition 5.1 implies:

######  Corollary 5.3.

For any word $\mathbf{w}$ and $u,v\in W$, we have

(5.4) $\displaystyle
R^{(v)}_{u,\mathbf{w}}(q)=q^{\ell(v)}\tau^{-}(T_{v^{-1}}^{-1}T_{\mathbf{w}}T_{vu}^{-1}).$

###### Proof.

Right-multiply both sides of (5.2) by $q^{-\ell(v)}T_{(vu)^{-1}}$ to get

$\displaystyle R^{(v)}_{u,\mathbf{w}}(q^{-1})$
$\displaystyle=q^{-\ell(v)}\tau^{+}(T_{v}D(T_{\mathbf{w}})T_{(vu)^{-1}})=q^{-\ell(v)}\tau^{+}(D(T_{v^{-1}}^{-1}T_{\mathbf{w}}T_{vu}^{-1})).$

Then observe that $\tau^{+}\circ D=D\circ\tau^{-}$. ∎

######  Corollary 5.4.

For any word $\mathbf{w}$ and $u\in W$, we have

(5.5) $\displaystyle R_{u,\mathbf{w}}(q)$
$\displaystyle=\tau^{-}(T_{\mathbf{w}}T_{u}^{-1}).$

##  6\. Characters of the Hecke Algebra

###  6.1. Characters of $W$

Let $W$ be a Coxeter group. The goal of this section is to relate the traces
from Section 5 to $q$-deformed rational $W$-Catalan numbers, by way of
character-theoretic arguments inspired by [Tri21]. As a consequence, we will
show that Theorem 1.9 follows from the existence and properties of Lusztig’s
exotic Fourier transform.

For the convenience of the reader, CHEVIE [GHL+96] code for this section
appears at [GLTW22]. (Our proofs do not rely on any code.) In type $A$, the
objects and formulas below admit explicit interpretations in the world of
symmetric functions, as we review in Section 6.7.1.

######  Remark 6.1.

One can also prove Theorem 1.9 directly from the results in [Tri21] together
with results of Kálmán and Gordon–Griffeth. More precisely, it follows from
combining Corollary 5.4, the $W$-analogue of [Kál09, Proposition 3.1], [Tri21,
Corollary 8.6.2], [Tri21, Corollary 11], [Tri21, Corollary 13], and [GG12,
Section 1.12], in that order. Below, we take a simpler approach that isolates
the role of the exotic Fourier transform to the greatest extent possible. We
still rely on Gordon–Griffeth, but avoid relying on Kálmán.

Fix a subfield $\mathbb{Q}_{W}\subseteq\mathbb{C}$ over which every (complex)
representation of $W$ is defined. Let $\mathrm{Irr}(W)$ be the set of
irreducible characters of $W$, and let $R_{W}$ be the representation ring of
$W$, or equivalently, the ring generated by the class functions
$\chi:W\to\mathbb{Q}_{W}$, for $\chi\in\mathrm{Irr}(W)$, under pointwise
addition and multiplication. We write $(-,-)_{W}:R_{W}\times
R_{W}\to\mathbb{Z}$ for the multiplicity pairing on $R_{W}$, i.e., the
symmetric bilinear pairing given by the identity matrix with respect to the
$\mathbb{Z}$-basis $\\{\chi\\}_{\chi\in\mathrm{Irr}(W)}$.

We write $1$ and $\varepsilon$ for the trivial and sign characters of $W$,
respectively. Explicitly, $1(w)=1$ and $\varepsilon(w)=(-1)^{\ell(w)}$ for all
$w\in W$.

Fix a reflection representation $V$ such that $V^{W}=0$, or equivalently,
$\dim(V)=r$. Let $\varsigma_{i}:W\to\mathbb{Q}_{W}$ be the character of the
$i$th symmetric power of $V$: that is,
$\varsigma_{i}(w)=\mathrm{tr}(w\mid\mathrm{Sym}^{i}(V))$. Let

$\displaystyle{[\mathrm{Sym}]_{q}}$
$\displaystyle=\sum_{i}q^{i}\varsigma_{i}\in R_{W}[\\![q]\\!].$

The element $[\mathrm{Sym}]_{q}$ only depends on $W$ and not on the choice of
the reflection representation $V$.

###  6.2. Characters of $\mathcal{H}_{W}$

Let $K=\mathbb{Q}_{W}(q^{\pm\frac{1}{2}})\supseteq A$. The $K$-algebra

$\displaystyle K\mathcal{H}_{W}=K\otimes_{A}\mathcal{H}_{W}$

is known to be isomorphic to $K[W]$, the group algebra of $W$ over $K$; see
[GP00, Theorem 7.4.6]. In particular, they have the same representation
theory: Every $K\mathcal{H}_{W}$-module of finite $K$-dimension is a direct
sum of simple $K\mathcal{H}_{W}$-modules, and the simple
$K\mathcal{H}_{W}$-modules are in bijection with the simple $K[W]$-modules.
Moreover, the latter are in bijection with the irreducible representations of
$W$, because by construction, every representation of a finite Coxeter group
can be defined over $K$.

Recall the definition of trace from Section 5.3. Every
$K\mathcal{H}_{W}$-module $M$ of finite $K$-dimension defines a trace
$\chi_{M}:K\mathcal{H}_{W}\to K$ called its _character_ : namely,

$\displaystyle\chi_{M}(a)=\mathrm{tr}_{K}(a\mid M).$

Since $K\mathcal{H}_{W}$ is split semisimple, the character $\chi_{M}$
determines $M$ up to isomorphism.

We say that a trace $\tau:K\mathcal{H}_{W}\to K$ is _symmetrizing_ if the
$K$-bilinear form on $K\mathcal{H}_{W}$ defined by $a\otimes b\mapsto\tau(ab)$
is nondegenerate. In this case, the _symmetrizer_ of $\tau$ is the element
$\Sigma(\tau)\in K\mathcal{H}_{W}\otimes_{K}K\mathcal{H}_{W}$ defined by

$\displaystyle\Sigma(\tau)=\sum_{i}e_{i}\otimes f_{i},$

for any choice of ordered $K$-bases $(e_{i})_{i}$, $(f_{i})_{i}$ for
$K\mathcal{H}_{W}$ that are dual to one another under the bilinear form. We
write $\bar{\Sigma}(\tau)\in K\mathcal{H}_{W}$ for the image of $\Sigma(\tau)$
under the multiplication map $K\mathcal{H}_{W}\otimes_{K}K\mathcal{H}_{W}\to
K\mathcal{H}_{W}$. This element is central in $K\mathcal{H}_{W}$.

We now state a version of _Schur orthogonality_ for $K\mathcal{H}_{W}$. Let
$\mathrm{Irr}(W)$ be the set of characters of simple $K[W]$-modules up to
isomorphism. Each $\chi\in\mathrm{Irr}(W)$ restricts to a class function
$\chi:W\to\mathbb{Q}_{W}$. At the same time, via the isomorphism
$K\mathcal{H}_{W}\xrightarrow{\sim}K[W]$, we can pull back $\chi$ to the
character of a simple $K\mathcal{H}_{W}$-module. We denote the resulting
character by $\chi_{q}:K\mathcal{H}_{W}\to K$. Schur orthogonality for
$K\mathcal{H}_{W}$ says that for any symmetrizing trace
$\tau:K\mathcal{H}_{W}\to K$, we have a decomposition

(6.1)
$\displaystyle\tau=\sum_{\chi\in\mathrm{Irr}(W)}\frac{1}{\mathbf{s}_{\tau}(\chi_{q})}\chi_{q},$

where $\mathbf{s}_{\tau}(\chi_{q})\in K$ is a scalar characterized by the
property that $\bar{\Sigma}(\tau)$ acts by
$\chi(e)\mathbf{s}_{\tau}(\chi_{q})$ on any $K\mathcal{H}_{W}$-module with
character $\chi_{q}$. We say that $\mathbf{s}_{\tau}(\chi_{q})$ is the _Schur
element_ for $\chi_{q}$ with respect to $\tau$. We can view its defining
property as a version of Schur’s lemma for the central element
$\bar{\Sigma}(\tau)\in K\mathcal{H}_{W}$.

###  6.3. The sign twist

Abusing notation, let $\tau^{+},\tau^{-}:K\mathcal{H}_{W}\to K$ denote the
$K$-linear extensions of the $A$-linear traces from Section 5. It turns out
that both are symmetrizing. Namely, if we set

$\displaystyle\sigma_{w}$ $\displaystyle\coloneqq q^{-\frac{\ell(w)}{2}}T_{w}$

for all $w\in W$, then (5.3) becomes equivalent to:

$\displaystyle\Sigma(\tau^{\pm})$ $\displaystyle=\sum_{w\in W}\sigma_{w}^{\pm
1}\otimes\sigma_{w^{-1}}^{\pm 1}.$

Now we can relate the Schur elements of these traces. In what follows, we will
write $\mathbf{s}^{\pm}(\chi_{q})$ in place of
$\mathbf{s}_{\tau^{\pm}}(\chi_{q})$ for clarity. Recall that $\varepsilon$ is
the sign character of $W$.

######  Proposition 6.2.

For all $\chi\in\mathrm{Irr}(W)$, we have
$\mathbf{s}^{+}(\chi_{q})=\mathbf{s}^{-}((\varepsilon\chi)_{q})$.

###### Proof.

For all $\chi$, we have

$\displaystyle\mathbf{s}^{\pm}(\chi_{q})$
$\displaystyle=\frac{1}{\chi(e)}\sum_{w\in W}\chi_{q}(\sigma_{w}^{\pm
1})\chi_{q}(\sigma_{w^{-1}}^{\pm 1}).$

Since $(\varepsilon\chi)(e)=\chi(e)$ and $\varepsilon^{2}=1$, it is enough to
show that

$\displaystyle\varepsilon(w)\chi_{q}(\sigma_{w^{-1}}^{-1})=(\varepsilon\chi)_{q}(\sigma_{w})$

for all $w\in W$ and $\chi\in\mathrm{Irr}(W)$. Indeed, this is [GP00,
Proposition 9.4.1(b)], once we observe that the $K$-algebra involution they
call $\gamma^{K}$ is, in our notation, given by
$\gamma^{K}(\sigma_{w})=\varepsilon(w)\sigma_{w^{-1}}^{-1}$ for all $w\in W$.
∎

###  6.4. Periodic elements of $\mathcal{H}_{W}$

Recall that $w_{\circ}$ denotes the longest element of $W$. The definition
below is adapted from a standard definition at the level of the positive braid
monoid of $W$, which we will not need until Section 8.1.

######  Definition 6.3.

For any word $\mathbf{w}=(s_{1},\ldots,s_{m})$, we set
$\sigma_{\mathbf{w}}\coloneqq\sigma_{s_{1}}\sigma_{s_{2}}\cdots\sigma_{s_{m}}=q^{-\frac{m}{2}}T_{\mathbf{w}}$.
We say that $\mathbf{w}$ is _periodic_ if
$\sigma_{\mathbf{w}}^{m}=\sigma_{w_{\circ}}^{2p}$ for some $p,m$ with $m\neq
0$. In this case, we say that $\frac{p}{m}$ is the _slope_ of $\mathbf{w}$.

######  Example 6.4.

If $\mathbf{c}$ is a Coxeter word, then $\sigma_{\mathbf{c}}^{p}$ is periodic
of slope $\frac{p}{h}$ for any integer $p$.

For all $\chi\in\mathrm{Irr}(W)$, the _fake_ and _generic degrees_ of $\chi$
are respectively

(6.2) $\displaystyle\mathrm{Feg}_{\chi}(q)$
$\displaystyle\coloneqq\frac{(\chi,[\mathrm{Sym}]_{q})_{W}}{(1,[\mathrm{Sym}]_{q})_{W}},$
(6.3) $\displaystyle\mathrm{Deg}_{\chi}(q)$
$\displaystyle\coloneqq\frac{\mathbf{s}^{+}(1_{q})}{\mathbf{s}^{+}(\chi_{q})},$

where in (6.2), we have extended $(-,-)_{W}$ to a pairing
$R_{W}[\\![q]\\!]\times R_{W}[\\![q]\\!]\to\mathbb{Z}[\\![q]\\!]$ by
linearity. It turns out that $\mathrm{Feg}_{\chi}(q)\in\mathbb{Z}[q]$ and
$\mathrm{Deg}_{\chi}\in\mathbb{Q}_{W}[q]$. At $q=1$, both polynomials
specialize to the _degree_ of $\chi$, i.e., the $\mathbb{Z}[q^{\pm
1}]$-dimension of the underlying $\mathcal{H}_{W}$-module:

(6.4) $\mathrm{Feg}_{\chi}(1)=\mathrm{Deg}_{\chi}(1)=\chi(1).$

For $\mathrm{Feg}_{\chi}(1)$, this follows from the discussion in [Spr74,
Section 2.5], and for $\mathrm{Deg}_{\chi}(1)$, see [GP00, Section 8.1.8]. In
addition, $\mathbf{s}^{+}(1_{q})$ is the Poincaré polynomial of $W$, which, by
a formula of Bott–Solomon [Sol66], can be written as

(6.5) $\displaystyle\mathbf{s}^{+}(1_{q})$ $\displaystyle=\sum_{w\in
W}q^{\ell(w)}=\prod_{i=1}^{r}\frac{1-q^{d_{i}}}{1-q}=\frac{1}{(1-q)^{r}(1,[\mathrm{Sym}]_{q})_{W}}.$

We will show that:

  1. (1)

The values of fake degrees at roots of unity are related to the values of
$\tau^{\pm}(\sigma_{\mathbf{w}})$ for periodic $\mathbf{w}$.

  2. (2)

The values of generic degrees at roots of unity are related to $q$-deformed
rational $W$-Catalan numbers.

Recall that $T\subset W$ is the set of reflections. In what follows, let
$N\coloneqq|T|=\ell(w_{\circ})$ and

(6.6) $\displaystyle\operatorname{c}(\chi)\coloneqq\frac{1}{\chi(e)}\sum_{t\in
T}\chi(t).$

Note that $\operatorname{c}(1)=N$. More generally, it turns out that
$\operatorname{c}(\chi)\in\mathbb{Z}$.

######  Remark 6.5.

In [Tri21], the integer $\operatorname{c}(\chi)$ was called the _content_ of
$\chi$, because for $W=\mathfrak{S}_{n}$, it is the content of the integer
partition of $n$ corresponding to $\chi$. Explicitly, the _content_ of an
integer partition $\lambda=(\lambda_{1}\geq\lambda_{2}\geq\cdots\geq 0)$ is
the sum
$\operatorname{c}(\lambda)\coloneqq\sum_{i=1}^{\infty}\sum_{j=1}^{\lambda_{i}}(j-i)$.

######  Theorem 6.6 (Springer).

If $\chi\in\mathrm{Irr}(W)$ and $\mathbf{w}$ is a periodic word of slope
$\nu\in\mathbb{Q}$, then

(6.7)
$\chi_{q}(\sigma_{\mathbf{w}})=q^{\nu\operatorname{c}(\chi)}\mathrm{Feg}_{\chi}(e^{2\pi
i\nu}).$

###### Proof.

Combine [Tri21, Corollary 9.2.2] and [Spr74, Theorem 4.2(v)]. ∎

######  Corollary 6.7.

If $\mathbf{w}$ is a periodic $w$-word of slope $\nu\in\mathbb{Q}$, then

$\displaystyle\tau^{+}(\sigma_{\mathbf{w}})$
$\displaystyle=\frac{1}{\mathbf{s}^{+}(1_{q})}\sum_{\chi\in\mathrm{Irr}(W)}q^{\nu\operatorname{c}(\chi)}\mathrm{Feg}_{\chi}(e^{2\pi
i\nu})\mathrm{Deg}_{\chi}(q),$ $\displaystyle\tau^{-}(\sigma_{\mathbf{w}})$
$\displaystyle=\frac{\varepsilon(w)}{\mathbf{s}^{+}(1_{q})}\sum_{\chi\in\mathrm{Irr}(W)}q^{-\nu\operatorname{c}(\chi)}\mathrm{Feg}_{\chi}(e^{2\pi
i\nu})\mathrm{Deg}_{\chi}(q).$

###### Proof.

The first identity follows from combining (6.1), (6.3), and Theorem 6.6. To
get the second identity from the first, observe that

$\displaystyle\frac{1}{\mathbf{s}^{-}(\varepsilon\chi_{q})}(\varepsilon\chi)_{q}(\sigma_{\mathbf{w}})$
$\displaystyle=\frac{1}{\mathbf{s}^{+}(\chi_{q})}(\varepsilon\chi)_{q}(\sigma_{\mathbf{w}})$
by Proposition 6.2
$\displaystyle=\frac{\mathrm{Deg}_{\chi}(q)}{\mathbf{s}^{+}(1_{q})}(\varepsilon\chi)_{q}(\sigma_{\mathbf{w}})$
by (6.3)
$\displaystyle=\frac{\mathrm{Deg}_{\chi}(q)}{\mathbf{s}^{+}(1_{q})}q^{\nu\operatorname{c}(\varepsilon\chi)}\mathrm{Feg}_{\varepsilon\chi}(e^{2\pi
i\nu})$ $\displaystyle\text{by~{}\lx@cref{creftype~refnum}{thm:periodic-
springer}}.$

We have $\operatorname{c}(\varepsilon\chi)=-\operatorname{c}(\chi)$ because
$\varepsilon(t)=-1$ for all $t\in T$. Moreover, $w$ is regular by [Tri21,
Corollary 9.3.6], so

$\displaystyle\mathrm{Feg}_{\varepsilon\chi}(e^{2\pi
i\nu})=(\varepsilon\chi)(w)=\varepsilon(w)\chi(w)=\varepsilon(w)\mathrm{Feg}_{\chi}(e^{2\pi
i\nu})$

by [Spr74, Theorem 4.2]. ∎

######  Remark 6.8.

When $W$ is a Weyl group of Coxeter number $h$, the right-hand sides of the
identities in Corollary 6.7 each simplify to a sum of precisely $h$ nonzero
terms, as we now explain. (See also [Ree19, Section 6].)

Suppose that $\mathbf{c}$ is a $c$-word. For any $\chi\in\mathrm{Irr}(W)$ and
$p$ coprime to $h$, we have $\mathrm{Feg}_{\chi}(e^{\frac{2\pi
ip}{h}})=\chi(c^{p})$ by §2.7 and Theorem 4.2(v) of [Spr74], so it suffices to
determine the number of $\chi$ for which $\chi(c^{p})$ is nonzero. Since $W$
is a Weyl group, $c^{p}$ is conjugate to the Coxeter element $c$ by [Spr74,
Proposition 4.7], allowing us to assume $p=1$. Let $C$ and $W\cdot c$ denote
the centralizer and conjugacy class of $c$ in $W$, respectively. Then $c$
generates $C$ by [Spr74, Corollary 4.4], so by Schur orthogonality,

$\displaystyle h=|C|=\frac{|W|}{|W\cdot
c|}=\sum_{\chi\in\mathrm{Irr}(W)}|\chi(c)|^{2}.$

Since $W$ is a Weyl group, we have $\mathbb{Q}_{W}=\mathbb{Q}$, which in turn
implies that the values of $\chi(c)$ in the last expression are all rational
integers. But by direct inspection we can find at least $h$ irreducible
characters $\chi$ for which $\chi(c)$ is nonzero. So in the last expression
above, we must have $\chi(c)=\pm 1$ for exactly $h$ irreducible characters
$\chi$, and $\chi(c)=0$ for all other $\chi$. Alternatively,111We thank Eric
Sommers for this argument. one can deduce this conclusion in a case-free way
from the fact that the trace of $c$ on any irreducible character is $1$, $0$,
or $-1$ [Kos76, Theorem 1]. Altogether, we have shown that when $W$ is a Weyl
group,

$\displaystyle\\{\chi\in\mathrm{Irr}(W):\chi(c)\neq
0\\}|=|\\{\chi\in\mathrm{Irr}(W):\mathrm{Feg}_{\chi}(e^{\frac{2\pi
ip}{h}})\neq 0\\}|=h.$

The behavior of the values $\chi(c)$ for noncrystallographic Coxeter groups is
a little more irregular:

  * •

In type $H_{3}$, where $h=10$, the value of $\chi(c)$ is nonzero for $8$ of
the $10$ irreducible characters $\chi$.

  * •

In type $H_{4}$, where $h=30$, it is nonzero for $24$ of the $34$ irreducible
characters.

  * •

In types $I_{2}(2m-1)$ and $I_{2}(4m-2)$, it is nonzero for all irreducible
characters. In type $I_{2}(4m)$, there is a single irreducible character for
which it vanishes. (Note that the Coxeter number of $I_{2}(m)$ is equal to
$2m$.)

For any $\nu\in\mathbb{Q}$, let $L_{\nu}$ denote the simple spherical module
of the rational Cherednik algebra of $W$ of central charge $\nu$. Let
$[L_{\nu}]_{q}\in R_{W}[q]$ be its graded character, normalized to be a
polynomial in $q$ with nonzero constant term. We will not give an exposition
of rational Cherednik algebras here, as we will not need $L_{\nu}$ itself, but
only a formula involving $[L_{\nu}]_{q}$. In what follows, recall from (1.3)
that

$\displaystyle\mathrm{Cat}_{p}(W;q)\coloneqq\prod_{i=1}^{r}\frac{[p+(pe_{i}\operatorname{mod}{h})]_{q}}{[d_{i}]_{q}},$

where $[a]_{q}=1+q+\cdots+q^{a-1}$.

######  Theorem 6.9.

If $p$ is a positive integer coprime to $h$, then:

  1. (1)

[GG12, Section 1.12] We have

(6.8) $\displaystyle(1,[L_{p/h}]_{q})_{W}=\mathrm{Cat}_{p}(W;q).$

  2. (2)

[Tri21, Corollaries 11 and 13] We have

(6.9)
$\displaystyle[L_{p/h}]_{q}=q^{\frac{rp}{2}}\sum_{\chi\in\mathrm{Irr}(W)}q^{-\frac{p}{h}\operatorname{c}(\chi)}\mathrm{Deg}_{\chi}(e^{\frac{2\pi
ip}{h}})\chi\cdot[\mathrm{Sym}]_{q}.$

In particular, $\frac{rp}{2}-\frac{p}{h}\operatorname{c}(\chi)\in\mathbb{Z}$
for all $\chi$ such that $\mathrm{Deg}_{\chi}(e^{\frac{2\pi ip}{h}})\neq 0$.

###### Proof.

We explain how to deduce part (2) from the results of [Tri21]. Observe that
$\frac{1}{2}rh=\ell(w_{\circ})=N$. So in the notation of [Tri21], the right-
hand side of (6.9) is the graded character
$(q^{\frac{1}{2}})^{2N\frac{p}{h}-r}[\Omega_{p/h}]_{q}$. Given the way we
normalize $[L_{p/h}]_{q}$ to be polynomial with nonzero constant term, [Tri21,
Corollary 13] identifies this character with $[L_{p/h}]_{q}$. ∎

######  Remark 6.10.

In analogy with Remark 6.8, the right-hand side of (6.9) simplifies to a sum
of precisely $r+1$ nonzero terms, where $r$ is the rank of $W$. If we write
$\Lambda_{k}$ for the character of the $k$th exterior power of the reflection
representation of $W$, then it turns out that:

(6.10) $\mathrm{Deg}_{\chi}(e^{\frac{2\pi
ip}{h}})=\begin{cases}(-1)^{k},&\text{if $\chi=\Lambda_{k}$ for some $0\leq
k\leq r$;}\\\ 0,&\text{otherwise}.\end{cases}$

By direct calculation,

(6.11) $\operatorname{c}(\Lambda_{k})=N-hk=h\left(\frac{1}{2}r-k\right),$

which leads to the formula

(6.12) $\displaystyle{[L_{p/h}]_{q}}=\sum_{0\leq k\leq
r}(-q^{p})^{k}\Lambda_{k}\cdot[\mathrm{Sym}]_{q}.$

Note that Gordon–Griffeth themselves cite [BR11, Proposition 4.2], which
relies on (6.12).

We sketch the proof of (6.10), relying freely on background explained in
[Tri21, §A.11]. First, by Theorem 6.6 and Remark 6.9 of [BGK97], the non-
principal $\Phi_{h}$-blocks of $K\mathcal{H}_{W}$ all have defect $0$. The
principal $\Phi_{h}$-block of $K\mathcal{H}_{W}$ has defect $1$, and its
Brauer tree is a line graph in which the vertices are the characters
$\Lambda_{k}$ ordered by $k$. (In non-crystallographic types, this result
depends on the case-by-case methods of [Mül97].) Next, [Tri21, Lemma 10.8.2]
shows that for $\chi$ in the blocks of defect $0$, we have
$\mathrm{Deg}_{\chi}(e^{2\pi i\frac{p}{h}})=0$, whereas for
$\chi=\Lambda_{k}$, we have $\mathrm{Deg}_{\chi}(e^{2\pi
i\frac{p}{h}})=(-1)^{k}$.

######  Corollary 6.11.

If $p$ is a positive integer coprime to $h$, then

(6.13) $\displaystyle(1-q)^{r}q^{-\frac{rp}{2}}\mathrm{Cat}_{p}(W;q)$
$\displaystyle=\frac{1}{\mathbf{s}^{+}(1_{q})}\sum_{\chi\in\mathrm{Irr}(W)}q^{-\frac{p}{h}\operatorname{c}(\chi)}\mathrm{Feg}_{\chi}(q)\mathrm{Deg}_{\chi}(e^{\frac{2\pi
ip}{h}}).$

###### Proof.

Since $W$ is a Coxeter group, every character $\chi\in\mathrm{Irr}(W)$ is
defined over the real numbers. This means $(1,\chi\cdot(-))_{W}=(\chi,-)_{W}$.
So combining (6.8) and (6.9) gives

$\displaystyle
q^{-\frac{rp}{2}}\mathrm{Cat}_{p}(W;q)=\sum_{\chi\in\mathrm{Irr}(W)}q^{-\frac{p}{h}\operatorname{c}(\chi)}\mathrm{Deg}_{\chi}(e^{\frac{2\pi
ip}{h}})(\chi,[\mathrm{Sym}]_{q})_{W}.$

Multiplying both sides by $(1-q)^{r}$, then invoking (6.2) and (6.5), we get
the result. ∎

###  6.5. The exotic Fourier transform

The following result is proved in [Lus84, Chapter 4].

######  Theorem 6.12 (Lusztig).

There is a pairing
$\\{-,-\\}_{W}:\mathrm{Irr}(W)\times\mathrm{Irr}(W)\to\mathbb{Q}_{W}$ that
satisfies the following conditions:

  1. (1)

For all $\chi\in\mathrm{Irr}(W)$, we have

(6.14)
$\mathrm{Feg}_{\chi}(q)=\sum_{\phi\in\mathrm{Irr}(W)}{\\{\phi,\chi\\}_{W}}\mathrm{Deg}_{\phi}(q).$

  2. (2)

For all $\phi,\chi\in\mathrm{Irr}(W)$, we have
$\\{\phi,\chi\\}_{W}=\\{\chi,\phi\\}_{W}$.

  3. (3)

For all $\phi,\chi\in\mathrm{Irr}(W)$ such that $\\{\phi,\chi\\}_{W}\neq 0$,
we have $\operatorname{c}(\phi)=\operatorname{c}(\chi)$.

Let $q_{1},q_{2},q_{3}$ be arbitrary parameters and $\nu\in\mathbb{Q}$. Then
the identity

(6.15)
$\sum_{\chi\in\mathrm{Irr}(W)}q_{1}^{\nu\operatorname{c}(\chi)}\mathrm{Feg}_{\chi}(q_{2})\mathrm{Deg}_{\chi}(q_{3})=\sum_{\chi\in\mathrm{Irr}(W)}q_{1}^{\nu\operatorname{c}(\chi)}\mathrm{Feg}_{\chi}(q_{3})\mathrm{Deg}_{\chi}(q_{2})$

follows from Theorem 6.12 via a double-summation argument. We can now prove
1.9(1).

######  Corollary 6.13.

Let $\mathbf{c}$ be a Coxeter word, and let $p$ be a positive integer coprime
to $h$. Then we have $R_{e,\mathbf{c}^{p}}(q)=(q-1)^{r}\mathrm{Cat}_{p}(W;q)$.

###### Proof.

We show that the stated identity
$R_{e,\mathbf{c}^{p}}(q)=(q-1)^{r}\mathrm{Cat}_{p}(W;q)$ is equivalent to the
identity

(6.16)
$\sum_{\chi\in\mathrm{Irr}(W)}q^{-\frac{p}{h}\operatorname{c}(\chi)}\mathrm{Feg}_{\chi}(e^{\frac{2\pi
ip}{h}})\mathrm{Deg}_{\chi}(q)=\sum_{\chi\in\mathrm{Irr}(W)}q^{-\frac{p}{h}\operatorname{c}(\chi)}\mathrm{Feg}_{\chi}(q)\mathrm{Deg}_{\chi}(e^{\frac{2\pi
ip}{h}}),$

which is a specialization of (6.15). Suppose that $\mathbf{c}$ is a $c$-word.
Then $\varepsilon(c)=(-1)^{r}$, so

(6.17) $\displaystyle R_{e,\mathbf{c}^{p}}(q)$
$\displaystyle=q^{\frac{rp}{2}}\tau^{-}(\sigma_{\mathbf{c}}^{p})$ by Corollary
5.4 (6.18)
$\displaystyle=\frac{(-1)^{r}q^{\frac{rp}{2}}}{\mathbf{s}^{+}(1_{q})}\sum_{\chi\in\mathrm{Irr}(W)}q^{-\frac{p}{h}\operatorname{c}(\chi)}\mathrm{Feg}_{\chi}(e^{2\pi
i\frac{p}{h}})\mathrm{Deg}_{\chi}(q)$
$\displaystyle\text{by~{}\lx@cref{creftype~refnum}{cor:fake-degree-at-root-of-
unity}}.$

So the result follows from Corollary 6.11. ∎

####  6.5.1. Uniformity

Lusztig’s proof of Theorem 6.12 is not uniform. Below, we explain which parts
can be made uniform and in which settings.

For every irreducible finite Coxeter group $W$, Lusztig defines

  1. (I)

a finite set $\mathrm{Udeg}(W)$,

  2. (II)

an embedding $\mathrm{Irr}(W)\hookrightarrow\mathrm{Udeg}(W)$,

  3. (III)

an extension of the function $\chi\mapsto\mathrm{Deg}_{\chi}$ on
$\mathrm{Irr}(W)$ to a function on $\mathrm{Udeg}(W)$,

  4. (IV)

a pairing $\\{-,-\\}:\mathrm{Udeg}(W)\times\mathrm{Udeg}(W)\to\mathbb{Q}_{W}$,
now called the _nonabelian_ or _exotic Fourier transform_ , satisfying
conditions (1)–(3) of Theorem 6.12.

We take $\\{-,-\\}_{W}$ to be the restriction of $\\{-,-\\}$ to
$\mathrm{Irr}(W)\times\mathrm{Irr}(W)$.

In [Lus93], Lusztig gives a uniform characterization of (I)-(III) by a list of
axioms, and proves that the axioms always admit a solution. However, beyond
Weyl groups, this proof uses case-by-case arguments. The definition of (IV)
beyond Weyl groups also uses case-by-case arguments. For dihedral types, it is
constructed uniformly in [Lus94], and for type $H_{4}$, it is constructed in
[Mal94]. For type $H_{3}$, the details are scattered in the literature; see
[Tri21, Remark 7.5.4]. We do not know a definition of the restricted pairing
$\\{-,-\\}$ that is uniform for Coxeter groups and independent of (I)-(II).

For Weyl groups, there are two ways to define $\\{-,-\\}$. In what follows,
suppose that $\mathbb{F}_{q}$ is a finite field of order $q$, and that $G$ is
a split, connected reductive algebraic group over $\mathbb{F}_{q}$ with Weyl
group $W$.

In [Lus84, Chapter 4], Lusztig defines the data (I)-(IV) as follows; see also
[Tri21, Section 8.2]. For (I)-(III), the constructions are uniform in $G$.

  1. (I)

$\mathrm{Udeg}(W)$ is the set of _unipotent_ irreducible representations of
$G(\mathbb{F}_{q})$. The definition of a unipotent representation uses
Deligne–Lusztig varieties [DL76, Section 7.8].

  2. (II)

The embedding $\mathrm{Irr}(W)\hookrightarrow\mathrm{Udeg}(W)$ sends each
character $\chi$ to a representation $\rho_{\chi}$ called the corresponding
_unipotent principal series representation_.

  3. (III)

For general $\rho\in\mathrm{Udeg}(W)$, the number
$\mathrm{Deg}_{\rho}(q)\coloneqq\rho(1)$ turns out to be a polynomial in $q$
that is independent of the prime power and recovers $\mathrm{Deg}_{\chi}$ when
$\rho=\rho_{\chi}$.

  4. (IV)

First, for any finite group $\mathfrak{G}$, Lusztig uniformly defines a set
$\mathfrak{M}(\mathfrak{G})$ and a hermitian unitary pairing
$\\{-,-\\}_{\mathfrak{G}}:\mathfrak{M}(\mathfrak{G})\times\mathfrak{M}(\mathfrak{G})\to\mathbb{C}$.

For each $\chi\in\mathrm{Irr}(W)$, let $a(\chi)$ be the largest power of $q$
dividing $\mathrm{Deg}_{\chi}(q)$. The subsets of $\mathrm{Irr}(W)$ on which
$a$ is constant are called _families_. For each family
$\mathcal{F}\subseteq\mathrm{Irr}(W)$, Lusztig defines

    1. (a)

a finite group $\mathfrak{G}_{\mathcal{F}}$, in a uniform manner;

    2. (b)

an embedding
$\mathfrak{M}(\mathfrak{G}_{\mathcal{F}})\hookrightarrow\mathrm{Udeg}(W)$, in
a case-by-case manner, such that as we run over families $\mathcal{F}$, the
disjoint union of these embeddings is a bijection.

The pairing $\\{-,-\\}$ on $\mathrm{Udeg}(W)$ is defined as the block sum of
the pairings $\\{-,-\\}_{\mathfrak{G}_{\mathcal{F}}}$ on the subsets
$\mathfrak{M}(\mathfrak{G}_{\mathcal{F}})$. The embeddings above are chosen in
such a way that condition (1) of Theorem 6.12 is guaranteed; see [Lus84,
Theorem 4.23]. Moreover, for the groups $\mathfrak{G}$ that actually get
assigned to families, it turns out that $\\{-,-\\}_{\mathfrak{G}}$ is real-
valued, hence symmetric orthogonal. (It further turns out that
$\\{-,-\\}_{\mathfrak{G}}$ takes values in $\mathbb{Q}_{W}$.)

In this approach, the construction of $\\{-,-\\}$ is not uniform, but
conditions (1) and (2) of Theorem 6.12 follow immediately and uniformly once
it is shown that [Lus84, Theorem 4.23] is satisfied for the right choice of
embeddings in (IV)(b). As for condition (3): [BM97, Section 4.21] shows
uniformly that $\operatorname{c}(\chi)=N-a(\chi)-A(\chi)$ for all
$\chi\in\mathrm{Irr}(W)$, where $A(\chi)=\deg_{q}\mathrm{Deg}_{\chi}(q)$. One
can check case-by-case that $A$ is also constant on families, and therefore,
so is $c$, which verifies condition (3).

Each irreducible character $\chi\in\mathrm{Irr}(W)$ also uniformly defines a
virtual representation $R_{\chi}$ called the corresponding _almost-character_.
The actual statement of [Lus84, Theorem 4.23] says that
$(\varrho,R_{\chi})_{G(\mathbb{F}_{q})}=\Delta(\varrho)\\{\varrho,\rho_{\chi}\\}$
for all $\chi\in\mathrm{Irr}(W)$ and $\varrho\in\mathrm{Udeg}(W)$, where
$\Delta:\mathrm{Udeg}(W)\to\\{\pm 1\\}$ is defined case-by-case in [Lus84,
Section 4.14]. However, $\Delta(\rho)=1$ when $\rho$ is a principal series
representation. This means that if we only care about the restricted pairing
$\\{-,-\\}_{W}$ on $\mathrm{Irr}(W)$, then we can take

$\displaystyle\\{\phi,\chi\\}_{W}\coloneqq(\rho_{\phi},R_{\chi})_{G(\mathbb{F}_{q})}$

as a uniform _definition_. In this approach, condition (1) of Theorem 6.12
immediate, but there is no uniform proof of conditions (2) or (3).

######  Remark 6.14.

Let us similarly address the uniformity of the proofs of the results we need
from [Tri21]. The only place affected in our work is 6.9(2), which relies on:

  * •

[Tri21, Corollary 11], which in turn relies on a Lemma 10.6.1 stating that
$\mathrm{Deg}_{\varepsilon\chi}(e^{2\pi
i\nu})=(-1)^{2N\nu}\mathrm{Deg}_{\chi}(e^{2\pi i\nu})$.

The proof of the lemma relies on $\\{-,-\\}_{W}$ by way of 6.12(1). It seems
possible that a proof avoiding the exotic Fourier transform can be found. Note
that in our application, where $\nu=p/h$ for $p$ coprime to $h$, the sign on
the right-hand side disappears.

  * •

[Tri21, Corollary 13], which follows from the results about the
$\Phi_{h}$-block theory of $K\mathcal{H}_{W}$ that we mentioned in Remark
6.10. The characterization of the principal block in terms of defect is proved
uniformly for Weyl groups in [BGK97, Theorem 6.6], but there does not appear
to be a uniform proof for general Coxeter groups.

###  6.6. The $q$-parking count

We now prove 1.9(2).

######  Corollary 6.15.

Let $\mathbf{c}$ be a Coxeter word, and let $p$ be a positive integer coprime
to $h$. Then we have $\sum_{v\in
W}R^{(v)}_{e,\mathbf{c}^{p}}(q)=(q-1)^{r}[p]_{q}^{r}$.

###### Proof.

Applying Corollary 5.3 and (6.1), we find

$\sum_{v\in W}R^{(v)}_{e,\mathbf{c}^{p}}(q)=\tau^{-}\left(\sum_{v\in
W}q^{\ell(v)}T_{v^{-1}}^{-1}T_{\mathbf{c}^{p}}T_{v}^{-1}\right)=\sum_{\chi\in\mathrm{Irr}(W)}\frac{1}{\mathbf{s}^{-}(\chi_{q})}\sum_{v\in
W}\chi_{q}\left(q^{\ell(v)}T_{v^{-1}}^{-1}T_{\mathbf{c}^{p}}T_{v}^{-1}\right).$

By (5.3), the bases $(T_{v}^{-1})_{v\in W}$ and
$(q^{\ell(v)}T_{v^{-1}}^{-1})_{v\in W}$ are dual to each other with respect to
$\tau^{-}$. Applying the second display equation on page 226 of [GP00], we see
that the above sum simplifies to

$\sum_{v\in
W}R^{(v)}_{e,\mathbf{c}^{p}}(q)=\sum_{\chi\in\mathrm{Irr}(W)}\dim(\chi)\cdot\chi_{q}(T_{\mathbf{c}^{p}}).$

(In the notation of  _loc. cit._ , we are taking $\phi$ to be the operator by
which $T_{\mathbf{c}^{p}}$ acts on the $\mathcal{H}_{W}$-module of character
$\chi_{q}$.) By (6.7), (6.4), and (6.15),

$q^{\frac{rp}{2}}\sum_{\chi\in\mathrm{Irr}(W)}q^{\frac{p}{h}\operatorname{c}(\chi)}\mathrm{Deg}_{\chi}(1)\mathrm{Feg}_{\chi}(e^{\frac{2\pi
ip}{h}})=q^{\frac{rp}{2}}\sum_{\chi\in\mathrm{Irr}(W)}q^{\frac{p}{h}\operatorname{c}(\chi)}\mathrm{Deg}_{\chi}(e^{\frac{2\pi
ip}{h}})\mathrm{Feg}_{\chi}(1).$

By (6.10)–(6.11), (6.4), and the formula $\dim(\Lambda_{k})=\binom{r}{k}$,
this becomes

$q^{\frac{rp}{2}}\sum_{0\leq k\leq
r}q^{p(r/2-k)}\dim(\Lambda_{k})(-1)^{k}=q^{rp}\sum_{0\leq k\leq
r}(-1)^{k}\binom{r}{k}q^{-pk}=q^{rp}(1-q^{-p})^{r}=(q-1)^{r}[p]_{q}^{r}.\qed$

###  6.7. Explicit computations in type $A$

In this subsection, we specialize the results above to $W=\mathfrak{S}_{n}$.

####  6.7.1. Symmetric functions

We refer the reader to [Sta99] for background on symmetric functions. Let
$\Lambda_{q}$ be the ring of symmetric functions over the field
$\mathbb{Q}(q)$. For $n\geq 0$, let $\Lambda_{q}^{n}$ denote the subspace of
degree-$n$ homogeneous polynomials. It has a basis of _Schur functions_
$s_{\lambda}$, indexed by the set $\operatorname{Par}(n)$ of partitions
$\lambda\vdash n$. The set $\mathrm{Irr}(\mathfrak{S}_{n})$ can be identified
canonically with $\operatorname{Par}(n)$. For $\lambda\vdash n$, we write
$\chi_{\lambda}\in\mathrm{Irr}(\mathfrak{S}_{n})$ to denote the corresponding
character. The trivial character $1$ corresponds to the single-row partition
$\lambda=(n)$, while the sign character $\varepsilon$ corresponds to the
single-column partition $\lambda=(1,1,\dots,1)$. The scalar product
$(-,-)_{\mathfrak{S}_{n}}$ corresponds to the _Hall inner product_
$\langle-,-\rangle$ on $\Lambda_{q}$. The Schur functions form an orthonormal
basis with respect to $\langle-,-\rangle$.

First, we claim that the inverses of the Schur elements
$\mathbf{s}^{+}(\chi_{\lambda})$ can be given in terms of the _principal
specializations_ of the Schur functions $s_{\lambda}$:

(6.19) $\frac{1}{\mathbf{s}^{+}(\chi_{\lambda})}=(1-q)^{n}\cdot
s_{\lambda}(1,q,q^{2},\dots).$

An explicit formula for the right-hand side (the _$q$ -hook length formula_)
can be found in [Sta99, Corollary 7.21.3]. Specifically, for a partition
$\lambda=(\lambda_{1}\geq\lambda_{2}\geq\dots\geq 0)$, let

$|\lambda|\coloneqq\sum_{i}\lambda_{i}\quad\text{and}\quad
b(\lambda)\coloneqq\sum_{i}(i-1)\lambda_{i}.$

View $\lambda$ as a Young diagram in English notation, and let $h(u)$ denote
the _hook-length_ of a box $u\in\lambda$. Then [Sta99, Corollary 7.21.3] reads

$s_{\lambda}(1,q,q^{2},\dots)=\frac{q^{b(\lambda)}}{(1-q)^{n}\prod_{u\in\lambda}[h(u)]_{q}}.$

The left-hand side of (6.19) is computed in [GP00, Theorem 10.5.2]. Comparing
the two sides gives the proof of (6.19).

We can now compute the generic degrees $\mathrm{Deg}_{\chi_{\lambda}}(q)$. For
the trivial character $\chi_{(n)}=1$, (6.19) yields

(6.20) $\frac{1}{\mathbf{s}^{+}(1)}=(1-q)^{n}\cdot
s_{(n)}(1,q,q^{2},\dots)=\frac{1}{[n]_{q}!},$

in agreement with (6.5). Applying [Sta99, Corollary 7.21.5], we find that

$\mathrm{Deg}_{\chi_{\lambda}}(q)=\frac{q^{b(\lambda)}[n]_{q}!}{\prod_{u\in\lambda}[h(u)]_{q}}=\sum_{T\in\operatorname{SYT}(\lambda)}q^{\operatorname{maj}(T)}.$

Here, $\operatorname{SYT}(\lambda)$ is the set of standard Young tableaux of
shape $\lambda$ and $\operatorname{maj}(T)$ is the _major index_ of $T$,
defined as the sum of all $i$ such that $i+1$ appears in a lower row of $T$
than $i$. As expected from (6.4), $\mathrm{Deg}_{\chi_{\lambda}}(1)$ equals
the dimension $\left|\operatorname{SYT}(\lambda)\right|$ of the irreducible
representation of $\mathfrak{S}_{n}$ corresponding to $\chi_{\lambda}$.

Next, we compute the fake degrees. By [Sta99, Exercise 7.73], we have

(6.21) $[\mathrm{Sym}]_{q}=\sum_{\lambda\vdash
n}s_{\lambda}(1,q,q^{2},\dots)s_{\lambda}.$

As an immediate consequence,

$\displaystyle(\chi_{\lambda},[\mathrm{Sym}]_{q})_{\mathfrak{S}_{n}}=s_{\lambda}(1,q,q^{2},\dots).$

This implies that the fake degrees coincide with the generic degrees:
$\mathrm{Feg}_{\chi_{\lambda}}(q)=\mathrm{Deg}_{\chi_{\lambda}}(q)$. The
exotic Fourier transform $\\{-,-\\}_{\mathfrak{S}_{n}}$ therefore coincides
with the scalar product $(-,-)_{\mathfrak{S}_{n}}$, i.e., for
$\phi,\chi\in\mathrm{Irr}(\mathfrak{S}_{n})$, we have
$\\{\phi,\chi\\}_{\mathfrak{S}_{n}}=1$ if $\phi=\chi$ and
$\\{\phi,\chi\\}_{\mathfrak{S}_{n}}=0$ otherwise.

######  Remark 6.16.

Using the Cauchy identity [Sta99, Theorem 7.12.1], one can check that the
right-hand side of (6.21) equals $h_{n}[X/(1-q)]$, where the square brackets
denote the plethysm [Sta99, Defintion A.2.6]. More generally, one can show
that the operation $\chi\mapsto\chi\cdot[\mathrm{Sym}]_{q}$ on class functions
corresponds to the plethystic substitution $f\mapsto f[X/(1-q)]$ on symmetric
functions.

######  Conjecture 6.17.

Let $W=\mathfrak{S}_{n}$. Then (6.15) gives the following explicit sum:

$\frac{1}{[n]!_{q}}\sum_{w\in
W}q_{1}^{\nu\operatorname{c}(\mathrm{shape}(\mathrm{RSK}(\mathrm{Foata}^{-1}(w)))}q_{2}^{\mathrm{maj}(w)}q_{3}^{\ell(w)}$

where $\operatorname{c}$ is given explicitly in Remark 6.5, $\mathrm{maj}$ is
the usual major index in $\mathfrak{S}_{n}$, $\mathrm{RSK}$ denotes the usual
Robinson-Schensted insertion, and
$\mathrm{Foata}:\mathfrak{S}_{n}\to\mathfrak{S}_{n}$ is Foata’s bijection
[FS78].

####  6.7.2. A streamlined proof of Theorem 1.9

Below, we reprove Theorem 1.9 in type $A$ by direct calculation, avoiding the
machinery needed for the previous proof. Note that the type-$A$ case of 1.9(1)
is a specialization of V. Jones’s formula for the HOMFLYPT polynomial of the
$(n,p)$-torus knot [Jon87, Theorem 9.7]. Explicitly, in the notation of _loc.
cit._ , $\mathrm{Cat}_{p}(W;q)$ is the $q$-coefficient of the smallest power
$\lambda$ in Jones’s formula.

Let $W=\mathfrak{S}_{n}$. Recall that $r=n-1$, that the exponents and degrees
of $\mathfrak{S}_{n}$ are given by $e_{i}=d_{i}-1=i$ for $1\leq i\leq n-1$,
that the Coxeter number is $h=d_{n-1}=n$, and that the irreducible
representations of $\mathfrak{S}_{n}$ are indexed by partitions $\lambda\vdash
n$.

By Remark 6.10, we have $\mathrm{Deg}_{\chi_{\lambda}}(e^{\frac{2\pi
ip}{h}})=0$ unless $\chi_{\lambda}$ is the character of an exterior power of
the reflection representation, or equivalently, unless $\lambda$ is the hook
partition $(n-k,1^{k})$ for some $k$. Following _loc. cit._ , we write
$\Lambda_{k}=\chi_{(n-k,1^{k})}$, so that $\dim(\Lambda_{k})=\binom{n-1}{k}$
and

(6.22)
$\mathrm{Feg}_{\Lambda_{k}}(q)=\mathrm{Deg}_{\Lambda_{k}}(q)=q^{\binom{k+1}{2}}\genfrac{[}{]}{0.0pt}{}{n-1}{k}_{q}.$

Evaluations of $q$-binomial coefficients at roots of unity are well known; see
e.g. [Sag92] and references therein. In particular, for $p$ coprime to $n$ and
$\zeta=e^{\frac{2\pi ip}{n}}$, we get

(6.23)
$\mathrm{Feg}_{\Lambda_{k}}(\zeta)=\mathrm{Deg}_{\Lambda_{k}}(\zeta)=\zeta^{\binom{k+1}{2}}\genfrac{[}{]}{0.0pt}{}{n-1}{k}_{\zeta}=(-1)^{k},$

in agreement with (6.10).

By (6.11) (or, alternatively, by Remark 6.5), we have

(6.24) $\operatorname{c}(\Lambda_{k})=\binom{n}{2}-kn=\frac{n(n-2k-1)}{2}.$

We now prove a more explicit version of Theorem 1.9 in type $A$.

######  Theorem 6.18.

Let $W=\mathfrak{S}_{n}$. For $p$ coprime to $h=n$, we have

$\displaystyle R_{e,\mathbf{c}^{p}}(q)$
$\displaystyle=(q-1)^{n-1}\frac{1}{[n+p]_{q}}\genfrac{[}{]}{0.0pt}{}{n+p}{n}_{q}\qquad\text{and}$
$\displaystyle\sum_{v\in\mathfrak{S}_{n}}R^{(v)}_{e,\mathbf{c}^{p}}(q)$
$\displaystyle=(q-1)^{n-1}[p]_{q}^{n-1}.$

###### Proof.

Write $\zeta=e^{\frac{2\pi ip}{n}}$. We compute:

$\displaystyle R_{e,\mathbf{c}^{p}}(q)$
$\displaystyle=\frac{(-1)^{r}q^{\frac{rp}{2}}}{\mathbf{s}^{+}(1_{q})}\sum_{\chi\in\mathrm{Irr}(\mathfrak{S}_{n})}q^{-\frac{p}{h}\operatorname{c}(\chi)}\mathrm{Feg}_{\chi}(q)\mathrm{Deg}_{\chi}(\zeta)$
by (6.17)–(6.18)
$\displaystyle=\frac{(-1)^{n-1}q^{\frac{(n-1)p}{2}}}{[n]_{q}!}\sum_{k=0}^{n-1}q^{-\frac{p}{n}\operatorname{c}(\Lambda_{k})}\mathrm{Feg}_{\Lambda_{k}}(q)\mathrm{Deg}_{\Lambda_{k}}(\zeta)$
by (6.10) and (6.20)
$\displaystyle=\frac{(-1)^{n-1}q^{\frac{(n-1)p}{2}}}{[n]_{q}!}\sum_{k=0}^{n-1}q^{\frac{-p(n-2k-1)}{2}}q^{\binom{k+1}{2}}\genfrac{[}{]}{0.0pt}{}{n-1}{k}_{q}(-1)^{k}$
by (6.22)–(6.24)
$\displaystyle=\frac{(-1)^{n-1}}{[n]_{q}!}\sum_{k=0}^{n-1}q^{\binom{k}{2}}\genfrac{[}{]}{0.0pt}{}{n-1}{k}_{q}(-1)^{k}q^{(p+1)k}$
$\displaystyle=\frac{1}{[n]_{q}!}\prod_{i=1}^{n-1}(q^{p+i}-1)=(q-1)^{n-1}\frac{1}{[n+p]}\genfrac{[}{]}{0.0pt}{}{n+p}{n}_{q}$
by the $q$-binomial theorem.

Similarly, we compute:

$\displaystyle\sum_{v\in\mathfrak{S}_{n}}R^{(v)}_{e,\mathbf{c}^{p}}(q)$
$\displaystyle=q^{\frac{rp}{2}}\sum_{\chi\in\mathrm{Irr}(\mathfrak{S}_{n})}\dim(\chi)q^{\frac{p}{h}\operatorname{c}(\chi)}\mathrm{Feg}_{\chi}(\zeta)$
by Section 6.6
$\displaystyle=q^{(n-1)p}\sum_{k=0}^{n-1}(-1)^{k}\binom{n-1}{k}q^{-pk}$ by
(6.24) and (6.23) $\displaystyle=q^{(n-1)p}(1-q^{-p})^{n-1}$ by the binomial
theorem $\displaystyle=(q-1)^{n-1}[p]_{q}^{n-1}.$

##  7\. Braid Richardson Varieties

Let $\mathbb{F},G,\mathcal{B},B_{+},B_{-},H$ be defined as in Section 1.6.
That is:

  * •

$\mathbb{F}$ is a field,

  * •

$G$ is a split, connected reductive algebraic group over $\mathbb{F}$ with
Weyl group $W$,

  * •

$\mathcal{B}$ is the flag variety of $G$,

  * •

$B_{+}$ and $B_{-}$ are opposed $\mathbb{F}$-split Borels, and

  * •

$H\coloneqq B_{+}\cap B_{-}$, a split maximal torus of $G$.

Recall that for any $(B,B^{\prime})\in\mathcal{B}^{2}$, the notation
$B\xrightarrow{w}B^{\prime}$ means $(B,B^{\prime})$ are in relative position
$w$. For a fixed Borel $B$, the set $\\{B^{\prime}\in\mathcal{B}\mid
B\xrightarrow{w}B^{\prime}\\}$ is isomorphic as an algebraic variety to an
affine space of dimension $\ell(w)$. In particular, if $B$ is an
$\mathbb{F}_{q}$-point of $\mathcal{B}$ (where $q$ is a prime power), then
this set contains $q^{\ell(w)}$ $\mathbb{F}_{q}$-points of $\mathcal{B}$.

######  Definition 7.1.

Let $\mathbf{w}=(s_{1},s_{2},\ldots,s_{m})\in S^{m}$ and fix $u\in W$. Define
the _braid Richardson variety_ by

$\accentset{\circ}{R}_{u,\mathbf{w}}=\left\\{(B_{+}=B_{0}\xrightarrow{s_{1}}B_{1}\xrightarrow{s_{2}}\cdots\xrightarrow{s_{m}}B_{m}\xleftarrow{uw_{\circ}}B_{-})\mid
B_{i}\in\mathcal{B}\text{ for all $i$}\right\\}.$

Note that $\accentset{\circ}{R}_{u,\mathbf{w}}$ is nonempty whenever
$\mathbf{w}$ admits at least one $u$-subword.

We now take $\mathbb{F}=\mathbb{F}_{q}$, a finite field of $q$ elements. The
following relation between braid Richardson varieties and $R$-polynomials will
be proved after Theorem 7.4.

######  Proposition 7.2.

For all words $\mathbf{w}\in S^{m}$ and all $u\in W$,

$R_{u,\mathbf{w}}(q)=\left|\accentset{\circ}{R}_{u,\mathbf{w}}(\mathbb{F}_{q})\right|.$

######  Example 7.3.

We continue Example 4.13. Let $G=\operatorname{SL}_{2}$ with $W=\\{e,s\\}$.
Then $|\mathcal{B}(\mathbb{F}_{q})|=q+1$. Let us denote the elements of
$\mathcal{B}(\mathbb{F}_{q})$ by
$\mathcal{B}(\mathbb{F}_{q})=\\{B_{0}=B_{+},B_{1},B_{2},\dots,B_{q}=B_{-}\\}$.
Then $B_{i}\xrightarrow{e}B_{i}$ and $B_{i}\xrightarrow{s}B_{j}$ for $i\neq
j$. By analyzing which Borel subgroups are equal to $B_{-}$, we compute that

$\displaystyle\accentset{\circ}{R}_{e,(s,s,s)}=\left\\{\begin{array}[]{rl}(B_{+}\xrightarrow{s}B_{i}\xrightarrow{s}B_{j}\xrightarrow{s}B_{k}\xleftarrow{s}B_{-})&\text{for
$1\leq i\leq q-1$ and $0\leq j,k\leq q-1$ with $i\neq j\neq k$},\\\
(B_{+}\xrightarrow{s}B_{-}\xrightarrow{s}B_{i}\xrightarrow{s}B_{j}\xleftarrow{s}B_{-})&\text{for
$0\leq i,j\leq q-1$ with $i\neq j$},\\\
(B_{+}\xrightarrow{s}B_{i}\xrightarrow{s}B_{-}\xrightarrow{s}B_{j}\xleftarrow{s}B_{-})&\text{for
$1\leq i\leq q-1$ and $0\leq j\leq q-1$}\end{array}\right\\}.$

Thus $\accentset{\circ}{R}_{e,(s,s,s)}(q)=(q-1)^{3}+2q(q-1)=(q-1)(q^{2}+1).$

The following result appears in [Deo85] (see also [MR04, WY07]) for reduced
words $\mathbf{w}$, but the argument in [Deo85] extends to the case where
$\mathbf{w}$ is arbitrary.

######  Theorem 7.4 ([Deo85, MR04, WY07]).

Let $W$ be a Weyl group. For a $u$-subword $\mathbf{u}$ of
$\mathbf{w}=(s_{1},s_{2},\ldots,s_{m})$, let

$\accentset{\circ}{R}_{\mathbf{u},\mathbf{w}}=\left\\{(B_{0}\xrightarrow{s_{1}}B_{1}\xrightarrow{s_{2}}\cdots\xrightarrow{s_{m}}B_{m}\xleftarrow{uw_{\circ}}B_{-})\mid
B_{-}\xrightarrow{u_{(i)}w_{\circ}}B_{i}\text{ for
$i\in\\{0,1,\ldots,m\\}$}\right\\}.$

Then

(7.1)
$\accentset{\circ}{R}_{u,\mathbf{w}}=\bigsqcup_{\mathbf{u}\in\mathcal{D}_{u,\mathbf{w}}}\accentset{\circ}{R}_{\mathbf{u},\mathbf{w}}\quad\text{with}\quad\accentset{\circ}{R}_{\mathbf{u},\mathbf{w}}(\mathbb{F})\simeq(\mathbb{F}^{\ast})^{\operatorname{e}_{\mathbf{u}}}\times\mathbb{F}^{\operatorname{d}_{\mathbf{u}}}.$

Thus, Proposition 7.2 follows by comparing (7.1) with (4.4). We may therefore
interpret Theorem 7.4 as a geometric incarnation of Corollary 4.12. Applying a
similar argument to the variety
$\accentset{\circ}{R}^{(v)}_{e,\mathbf{c}^{p}}$ defined in (1.7), we find for
all $v\in W$ and all integers $p$ that

(7.2)
$\left|\accentset{\circ}{R}_{e,\mathbf{c}^{p}}(\mathbb{F}_{q})\right|=R_{e,\mathbf{c}^{p}}(q)\quad\text{and}\quad\left|\accentset{\circ}{R}^{(v)}_{e,\mathbf{c}^{p}}(\mathbb{F}_{q})\right|=R^{(v)}_{e,\mathbf{c}^{p}}(q).$

Theorem 1.12 then follows from Theorem 1.9.

##  8\. Noncrossing Combinatorics

For Weyl groups, the uniformly-defined rational _nonnesting_ Coxeter–Catalan
objects from Section 1.1 are counted by ${\mathrm{Cat}_{p}(W)}$. As reviewed
in Section 1.3, it has been an open problem to give a uniform definition of a
rational _noncrossing_ family counted by ${\mathrm{Cat}_{p}(W)}$.

There are three previously-defined families of noncrossing Coxeter–Catalan
objects, which are all in uniform bijection with each other. Each of these
families has a generalization to the Fuss–Catalan ($p=kh+1$) and Fuss–Dogolon
($p=kh-1$) levels of generality. In this section, for simplicity, we will only
treat the Fuss–Catalan case.

Fix a Coxeter word $\mathbf{c}=(s_{1},s_{2},\ldots,s_{r})$. We will review the
three noncrossing families, then prove that the elements of
$\mathcal{M}_{e,\mathbf{c}^{p}}$ are naturally rational noncrossing objects by
giving direct bijections between $\mathcal{M}_{e,\mathbf{c}^{kh+1}}$ and the
Coxeter–Fuss–Catalan noncrossing families.

###  8.1. Noncrossing Objects and Bijections

A Coxeter group $W$ with system of simple generators $S$ defines a
corresponding _positive braid monoid_ $\mathbf{B}^{+}_{W}$, equipped with a
generating set $\mathbf{S}$ in bijection with $S$. For all $s\in S$, we write
$\mathbf{s}\in\mathbf{S}$ to denote the corresponding generator. As a monoid,
$\mathbf{B}^{+}_{W}$ is freely generated by $\mathbf{S}$ modulo the braid
relations

$\displaystyle\overbrace{\mathbf{s}\mathbf{t}\mathbf{s}\cdots}^{m(s,t)}=\overbrace{\mathbf{t}\mathbf{s}\mathbf{t}\cdots}^{m(s,t)}$

for _distinct_ $s,t\in S$, for the same integers $m(s,t)$ as in (3.1). Thus
there is a surjective homomorphism of monoids $\mathbf{B}^{+}_{W}\to W$ that
sends $\mathbf{s}\mapsto s$. Note that it factors through a surjective
homomorphism of rings $\mathbb{Z}[q^{\pm
1}][\mathbf{B}^{+}_{W}]\to\mathcal{H}_{W}$, where $\mathcal{H}_{W}$ is the
Hecke algebra from Section 5.

For any word $\mathbf{w}=(s_{1},s_{2},\dots,s_{m})\in S^{m}$, we abuse
notation by again writing $\mathbf{w}$ to denote the product
$\mathbf{s}_{1}\mathbf{s}_{2}\cdots\mathbf{s}_{m}\in\mathbf{B}^{+}_{W}$. In
the case where $\mathbf{w}$ is a reduced $w$-word for some $w\in W$, this
product only depends on $w$, not on $\mathbf{w}$.

The _weak order_ $(\mathbf{B}^{+}_{W},\leq_{R})$ on $\mathbf{B}^{+}_{W}$ is
the lattice formed by the transitive closure of the relation $\lessdot_{R}$
defined by $\mathbf{w}\lessdot_{R}\mathbf{w}\mathbf{s}$ for
$\mathbf{s}\in\mathbf{S}$ and $\mathbf{w}\in\mathbf{B}^{+}_{W}$. The map
$w\mapsto\mathbf{w}$, where $\mathbf{w}\in\mathbf{B}^{+}_{W}$ is a reduced
word for $w$, defines a canonical lift from $W$ onto the weak order interval
$[e,\mathbf{w}_{\circ}]_{R}\subset\mathbf{B}^{+}_{W}$. Here,
$\mathbf{w}_{\circ}$ is the lift of the longest element $w_{\circ}\in W$, also
known as the _half-twist_.

$\begin{array}[]{|cccccccc|cc|cccccccc|}\lx@intercol\hfil\mathrm{Sort}^{(2)}(\mathfrak{S}_{3},\mathbf{c})\hfil\lx@intercol&\lx@intercol\hfil\mathrm{NC}^{(2)}(\mathfrak{S}_{3},\mathbf{c})\hfil\lx@intercol&\lx@intercol\hfil\mathrm{Clus}^{(2)}(\mathfrak{S}_{3},\mathbf{c})\hfil\lx@intercol\\\
\hline\cr(1\kern 1.00006pt2)&(2\kern
1.00006pt3)&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\big{(}(1\kern
1.00006pt2),&(2\kern 1.00006pt3)\big{)}&(1\kern 1.00006pt2)&(2\kern
1.00006pt3)&s_{1}&s_{2}&s_{1}&s_{2}&s_{1}&s_{2}\\\ s_{1}&(1\kern
1.00006pt3)&\dot{(1\kern
1.00006pt2)}&\cdot&\cdot&\cdot&\cdot&\cdot&\big{(}(1\kern
1.00006pt3),&\dot{(1\kern 1.00006pt2)}\big{)}&s_{1}&(1\kern
1.00006pt3)&\dot{(1\kern 1.00006pt2)}&s_{2}&s_{1}&s_{2}&s_{1}&s_{2}\\\
s_{1}&(1\kern 1.00006pt3)&s_{1}&\cdot&\ddot{(1\kern
1.00006pt2)}&\cdot&\cdot&\cdot&\big{(}(1\kern 1.00006pt3),&\ddot{(1\kern
1.00006pt2)}\big{)}&s_{1}&(1\kern 1.00006pt3)&s_{1}&s_{2}&s_{1}&\ddot{(1\kern
1.00006pt2)}&s_{1}&s_{2}\\\ (1\kern 1.00006pt2)&s_{2}&\cdot&\dot{(2\kern
1.00006pt3)}&\cdot&\cdot&\cdot&\cdot&\big{(}(1\kern 1.00006pt2),&\dot{(2\kern
1.00006pt3)}\big{)}&(1\kern 1.00006pt2)&s_{2}&s_{1}&s_{2}&\dot{(2\kern
1.00006pt3)}&s_{2}&s_{1}&s_{2}\\\ (1\kern
1.00006pt2)&s_{2}&\cdot&s_{2}&\cdot&\ddot{(2\kern
1.00006pt3)}&\cdot&\cdot&\big{(}(1\kern 1.00006pt2),&\ddot{(2\kern
1.00006pt3)}\big{)}&(1\kern
1.00006pt2)&s_{2}&s_{1}&s_{2}&s_{1}&s_{2}&s_{1}&\ddot{(2\kern 1.00006pt3)}\\\
s_{1}&s_{2}&(2\kern 1.00006pt3)&\dot{(1\kern
1.00006pt3)}&\cdot&\cdot&\cdot&\cdot&\big{(}(2\kern 1.00006pt3),&\dot{(1\kern
1.00006pt3)}\big{)}&s_{1}&s_{2}&(2\kern 1.00006pt3)&\dot{(1\kern
1.00006pt3)}&s_{1}&s_{2}&s_{1}&s_{2}\\\ s_{1}&s_{2}&(2\kern
1.00006pt3)&s_{2}&\cdot&\ddot{(1\kern 1.00006pt3)}&\cdot&\cdot&\big{(}(2\kern
1.00006pt3),&\ddot{(1\kern 1.00006pt3)}\big{)}&s_{1}&s_{2}&(2\kern
1.00006pt3)&s_{2}&s_{1}&s_{2}&\ddot{(1\kern 1.00006pt3)}&s_{2}\\\
s_{1}&s_{2}&s_{1}&\dot{(1\kern 1.00006pt2)}&\dot{(2\kern
1.00006pt3)}&\cdot&\cdot&\cdot&\big{(}\dot{(1\kern 1.00006pt2)},&\dot{(2\kern
1.00006pt3)}\big{)}&s_{1}&s_{2}&s_{1}&\dot{(1\kern 1.00006pt2)}&\dot{(2\kern
1.00006pt3)}&s_{2}&s_{1}&s_{2}\\\ s_{1}&s_{2}&s_{1}&s_{2}&\dot{(1\kern
1.00006pt3)}&\ddot{(1\kern 1.00006pt2)}&\cdot&\cdot&\big{(}\dot{(1\kern
1.00006pt3)},&\ddot{(1\kern
1.00006pt2)}\big{)}&s_{1}&s_{2}&s_{1}&s_{2}&\dot{(1\kern
1.00006pt3)}&\ddot{(1\kern 1.00006pt2)}&s_{1}&s_{2}\\\
s_{1}&s_{2}&s_{1}&\dot{(1\kern 1.00006pt2)}&s_{1}&\cdot&\ddot{(2\kern
1.00006pt3)}&\cdot&\big{(}\dot{(1\kern 1.00006pt2)},&\ddot{(2\kern
1.00006pt3)}\big{)}&s_{1}&s_{2}&s_{1}&\dot{(1\kern
1.00006pt2)}&s_{1}&s_{2}&s_{1}&\ddot{(2\kern 1.00006pt3)}\\\
s_{1}&s_{2}&s_{1}&s_{2}&s_{1}&\dot{(2\kern 1.00006pt3)}&\ddot{(1\kern
1.00006pt3)}&\cdot&\big{(}\dot{(2\kern 1.00006pt3)},&\ddot{(1\kern
1.00006pt3)}\big{)}&s_{1}&s_{2}&s_{1}&s_{2}&s_{1}&\dot{(2\kern
1.00006pt3)}&\ddot{(1\kern 1.00006pt3)}&s_{2}\\\
s_{1}&s_{2}&s_{1}&s_{2}&s_{1}&s_{2}&\ddot{(1\kern 1.00006pt2)}&\ddot{(2\kern
1.00006pt3)}&\big{(}\ddot{(1\kern 1.00006pt2)},&\ddot{(2\kern
1.00006pt3)}\big{)}&s_{1}&s_{2}&s_{1}&s_{2}&s_{1}&s_{2}&\ddot{(1\kern
1.00006pt2)}&\ddot{(2\kern 1.00006pt3)}\\\ \hline\cr\end{array}$ Figure 8. Let
$\mathbf{c}=(s_{1},s_{2})$. Left: the 12 $\mathbf{c}$-sortable elements in
$\mathrm{Sort}^{(2)}(\mathfrak{S}_{3},\mathbf{c})$. In each row, we have
replaced the position of the leftmost $s_{j}$ ($j=1,2$) not appearing in
$\mathbf{w}(\mathbf{c})$ with the corresponding colored reflection in the skip
tuple. Middle: The 12 elements in
$\mathrm{NC}^{(2)}(\mathfrak{S}_{3},\mathbf{c})$. Right: The 12 elements of
$\mathrm{Clus}^{(2)}(\mathfrak{S}_{3},\mathbf{c})$. We have replaced the
positions $i$ where $u_{i}=e$ with the corresponding colored reflection in
$\mathrm{inv}_{e}(\mathbf{u})$.

####  8.1.1. Sortable Elements

The first family of noncrossing objects we review are the Coxeter-sortable
elements, introduced at the Coxeter–Catalan level of generality by Reading
[Rea06, Rea07b, Rea07a] and extended to the Fuss–Catalan level by Stump,
Thomas, and Williams [STW15].

Let $\mathbf{c}^{\infty}\in S\times S\times\cdots$ be the infinite sequence
formed by repeated concatenations of $\mathbf{c}$. The _$\mathbf{c}$ -sorting
word_ $\mathbf{w}(\mathbf{c})$ of $\mathbf{w}\in\mathbf{B}^{+}_{W}$ is the
lexicographically-first subword of $\mathbf{w}$ occurring in
$\mathbf{c}^{\infty}$. We write $\mathbf{w}(\mathbf{c},i)$ for the word formed
by restricting $\mathbf{w}(\mathbf{c})$ to the $i$th copy of $\mathbf{c}$ in
$\mathbf{c}^{\infty}$.

######  Definition 8.1 ([Rea07a, STW15]).

An element $\mathbf{w}\in\mathbf{B}^{+}_{W}$ is _$\mathbf{c}$ -sortable_ if
$\mathbf{w}(\mathbf{c},i+1)$ is a subword of $\mathbf{w}(\mathbf{c},i)$ for
all $i$. We write $\mathrm{Sort}^{(\infty)}(W,\mathbf{c})$ for the set of all
such $\mathbf{w}$. We also write

$\displaystyle\mathrm{Sort}^{(m)}(W,\mathbf{c})\coloneqq\\{\mathbf{w}\in\mathrm{Sort}^{(\infty)}(W,\mathbf{c}):\mathbf{w}\leq_{R}\mathbf{w}_{\circ}^{m}\\}.$

######  Example 8.2.

The 12 elements of $\mathrm{Sort}^{(2)}(\mathfrak{S}_{3},(s_{1},s_{2}))$ are
illustrated in Figure 8(left) together with their _skip tuples_ , defined as
follows. For $1\leq j\leq n-1$, let $(t_{j},k_{j})$ be the colored reflection
in $\mathrm{inv}(\mathbf{w}(\mathbf{c}))$ corresponding to the leftmost simple
reflection $s_{j}$ that does not appear in $\mathbf{w}(\mathbf{c})$. We define
the _skip tuple_ of $\mathbf{w}$ to be the collection
$\mathrm{skip}_{\mathbf{c}}(\mathbf{w})$ of all $(t_{j},k_{j})$, ordered by
when they appear in $\mathrm{inv}(\mathbf{w}(\mathbf{c}))$.

By [Spe09], the element $\mathbf{w}_{\circ}$ is $\mathbf{c}$-sortable for any
$\mathbf{c}$. For example, for $\mathfrak{S}_{4}$, we have

$\displaystyle\mathbf{w}_{\circ}(s_{1},s_{2},s_{3})$
$\displaystyle=(\underbrace{s_{1},s_{2},s_{3}}_{\mathbf{w}_{\circ}(\mathbf{c},1)},\underbrace{s_{1},s_{2},\cdot}_{\mathbf{w}_{\circ}(\mathbf{c},2)},\underbrace{s_{1},\cdot,\cdot}_{\mathbf{w}_{\circ}(\mathbf{c},3)},\cdots)$
$\displaystyle\text{and}\qquad\mathbf{w}_{\circ}(s_{2},s_{1},s_{3})$
$\displaystyle=(\underbrace{s_{2},s_{1},s_{3}}_{\mathbf{w}_{\circ}(\mathbf{c},1)},\underbrace{s_{2},s_{1},s_{3}}_{\mathbf{w}_{\circ}(\mathbf{c},2)},\cdot,\cdot,\cdot,\cdots).$

####  8.1.2. Noncrossing Partitions

The second noncrossing family we review are the noncrossing partitions,
introduced in the Coxeter–Catalan level of generality by Bessis [Bes03] and
extended to the Fuss–Catalan level by Armstrong [Arm09].

The _absolute order_ $\leq_{T}$ is the partial order on $W$ induced by
$\ell_{T}$. That is, $u\leq_{T}w$ if and only if
$\ell_{T}(u)+\ell_{T}(u^{-1}w)=\ell_{T}(w)$. The covering relations in this
poset are therefore of the form $u\lessdot_{T}w$ whenever $u^{-1}w\in T$, and
we label the corresponding edge $u\to w$ of the Hasse diagram of
$(W,\leq_{T})$ by $t\coloneqq u^{-1}w$. See Figure 9.

Figure 9. The Hasse diagram of the absolute order
$(\mathfrak{S}_{3},\leq_{T})$, with edges labeled by reflections.

The _( $W$-)noncrossing partitions_ are defined to be the elements of the
absolute order interval $\mathrm{NC}(W,c)\coloneqq[e,c]_{T}$. Observe that
each element of $T$ appears exactly once as an inversion in the
$\mathbf{c}$-sorting word for $\mathbf{w}_{\circ}$. This gives rise to a total
order on $T$: For two reflections $t_{1},t_{2}\in T$, we write
$t_{1}\leq_{\mathbf{c}}t_{2}$ if and only if $t_{1}$ appears before $t_{2}$ in
$\mathrm{inv}(\mathbf{w}_{\circ}(\mathbf{c}))$. The poset $\mathrm{NC}(W,c)$
is known to be _EL-shellable_ with respect to the ordering on $T$ given by
$\leq_{\mathbf{c}}$, which amounts to the following statement.

######  Proposition 8.3 ([STW15, Proposition 4.1.4]).

Every noncrossing partition has a unique $\leq_{\mathbf{c}}$-increasing
factorization into reflections. In other words, for each $\pi\in[e,c]_{T}$,
there exists a unique $m$-tuple $(t_{1},t_{2},\dots,t_{m})\in T^{m}$, where
$m=\ell_{T}(\pi)$, such that $\pi=t_{1}t_{2}\dots t_{m}$ and
$t_{1}\leq_{\mathbf{c}}t_{2}\leq_{\mathbf{c}}\dots\leq_{\mathbf{c}}t_{m}$.

For instance, choosing $\mathbf{c}=(s_{1},s_{2})$ in $\mathfrak{S}_{3}$, we
have $(1\kern 1.00006pt2)\leq_{\mathbf{c}}(1\kern
1.00006pt3)\leq_{\mathbf{c}}(2\kern 1.00006pt3)$. The interval $[e,c]_{T}$
consists of all elements of $\mathfrak{S}_{3}\setminus\\{s_{2}s_{1}\\}$, and
each of them indeed has a unique $\leq_{\mathbf{c}}$-increasing factorization
into reflections, as Figure 9 illustrates.

Generalizing a construction of Edelman in type $A$ [Ede80], Armstrong [Arm09]
defined the Fuss–Catalan analogue of noncrossing partitions to be
$k$-multichains $\pi_{1}\leq_{T}\cdots\leq_{T}\pi_{k}$ in $\mathrm{NC}(W,c)$,
recovering $\mathrm{NC}(W,c)$ for $k=1$. For $0\leq i\leq k$, define
$\delta_{i}\coloneqq\pi_{i}^{-1}\pi_{i+1}$, with the convention that
$\pi_{0}=e$ and $\pi_{k+1}=c$. Factoring each $\delta_{i}$ into reflections
using $\leq_{\mathbf{c}}$ as above, it is convenient to think of these
multichains as a factorization of $c$ into colored reflections (with colors
$0,1,\ldots,k$ corresponding to the factors
$\delta_{0},\delta_{1},\ldots,\delta_{k}$), such that the reflections in any
color increase with respect to $\leq_{\mathbf{c}}$.

######  Definition 8.4 ([Arm09, STW15]).

Given $k\in\mathbb{N}$, we write

$\displaystyle\mathrm{NC}^{(k)}(W,\mathbf{c})\coloneqq\left\\{\big{(}(t_{1},k_{1}),(t_{2},k_{2}),\ldots,(t_{r},k_{r})\big{)}\in(T\times\mathbb{Z})^{r}\
\middle|\begin{array}[]{c}t_{1}t_{2}\cdots t_{r}=c,\\\ 0\leq
k_{1}\leq\cdots\leq k_{r}\leq k,\text{ and}\\\ \text{if }k_{i}=k_{i+1}\text{
then }t_{i}\leq_{\mathbf{c}}t_{i+1}\end{array}\right\\}.$

The 12 elements of $\mathrm{NC}^{(2)}(\mathfrak{S}_{3},(s_{1},s_{2}))$ are
illustrated in Figure 8(middle).

####  8.1.3. Clusters

The third noncrossing family we review are the clusters, introduced in the
Coxeter–Catalan level of generality by Fomin and Zelevinsky [FZ03a] and
extended to the Fuss–Catalan level in several different guises, by several
different authors [FR05, Tza08, STW15]. We present a definition using the
notation of Section 4. Let $\mathbf{c}\mathbf{w}_{\circ}^{k}(\mathbf{c})$ be
the $\mathbf{c}$-sorting word of $\mathbf{c}\mathbf{w}_{\circ}^{k}$ (which is
just $\mathbf{c}$ followed by the $\mathbf{c}$-sorting word of
$\mathbf{w}_{\circ}^{k}$).

######  Definition 8.5 ([FR05, CLS14, STW15]).

We write

$\displaystyle\mathrm{Clus}^{(k)}(W,\mathbf{c})\coloneqq\\{\text{$w_{\circ}^{k}$-subwords
$\mathbf{u}$ of $\mathbf{c}\mathbf{w}_{\circ}^{k}(\mathbf{c})$ satisfying
$\operatorname{e}_{\mathbf{u}}=r$}\\}.$

The $12$ elements
$\mathbf{u}\in\mathrm{Clus}^{(2)}(\mathfrak{S}_{3},(s_{1},s_{2}))$ and their
sets $\mathrm{inv}_{e}(\mathbf{u})$ are illustrated in Figure 8(right).

Since $w_{\circ}$ is an involution, $w_{\circ}^{k}$ must be either $e$ or
$w_{\circ}$, depending on the parity of $k$. Thus,
$\mathrm{Clus}^{(k)}(W,\mathbf{c})$ contains all $w_{\circ}^{k}$-subwords of
$\mathbf{c}\mathbf{w}_{\circ}^{k}(\mathbf{c})$, not necessarily distinguished,
that skip exactly $r$ letters. These conditions are very similar to the ones
in Definition 1.1, and we make this similarity precise in the proof of Theorem
8.8 below.

####  8.1.4. Bijections and Enumeration

Recall that previously, the three families of noncrossing objects defined in
Sections 8.1.1, 8.1.2 and 8.1.3 had been enumerated case by case, using
combinatorial models and computer calculations:

######  Theorem 8.6 ([Rea07a, STW15]).

For all $k\in\mathbb{N}$, non-uniform arguments show that

$\displaystyle\left|\mathrm{Sort}^{(k)}(W,\mathbf{c})\right|=\left|\mathrm{NC}^{(k)}(W,\mathbf{c})\right|=\left|\mathrm{Clus}^{(k)}(W,\mathbf{c})\right|={\mathrm{Cat}_{kh+1}(W)}.$

Our main result in this section is their _uniform_ enumeration.

######  Theorem 8.7 ([Rea07a, STW15]).

We have the following uniform bijections:

  * •

$\mathbf{w}\mapsto\mathrm{skip}_{\mathbf{c}}(\mathbf{w})$ is a bijection
$\mathrm{Sort}^{(k)}(W,\mathbf{c})\xrightarrow{\sim}\mathrm{NC}^{(k)}(W,\mathbf{c})$.

  * •

$\mathbf{u}\mapsto\mathrm{inv}_{e}(\mathbf{u})$ is a bijection
$\mathrm{Clus}^{(k)}(W,\mathbf{c})\xrightarrow{\sim}\mathrm{NC}^{(k)}(W,\mathbf{c})$.

In particular, arguments uniform for all Coxeter groups $W$ show that

$\left|\mathrm{Sort}^{(k)}(W,\mathbf{c})\right|=\left|\mathrm{NC}^{(k)}(W,\mathbf{c})\right|=\left|\mathrm{Clus}^{(k)}(W,\mathbf{c})\right|.$

See Figure 8 for an example.

###  8.2. Rational Noncrossing Partitions

Assuming Theorem 8.7, we prove that $\mathcal{M}_{e,\mathbf{c}^{kh+1}}$
naturally forms a noncrossing Fuss-Catalan family by giving a uniform
bijection from its elements to noncrossing partitions. This implies that the
more general sets $\mathcal{M}_{e,\mathbf{c}^{p}}$ should be considered
rational noncrossing families.

######  Theorem 8.8.

Fix $k\in\mathbb{N}$. Then there is a uniform bijection

$\displaystyle\mathcal{M}_{e,\mathbf{c}^{kh+1}}$
$\displaystyle\simeq\mathrm{NC}^{(k)}(W,\mathbf{c})$ $\displaystyle\mathbf{u}$
$\displaystyle\mapsto\big{(}(t,i):(t,2i)\in\mathrm{inv}_{e}(\mathbf{u})\big{)}.$

###### Proof.

Observe that $w_{\circ}^{2}=e$ in $W$ and
$\mathbf{w}_{\circ}^{2}=\mathbf{c}^{h}$ in $\mathbf{B}^{+}_{W}$. In
particular, the $\mathbf{c}$-sorting word for
$\mathbf{c}\mathbf{w}_{\circ}^{2k}$ is just
$\mathbf{c}\mathbf{w}_{\circ}^{2k}(\mathbf{c})=\mathbf{c}^{kh+1}$. By
Definition 8.5, $\mathrm{Clus}^{(2k)}(W,\mathbf{c})$ consists of $e$-subwords
of $\mathbf{c}^{kh+1}$ that skip exactly $r$ letters. Therefore, by
Proposition 4.4, $\mathcal{M}_{e,\mathbf{c}^{kh+1}}$ is exactly the subset of
$\mathrm{Clus}^{(2k)}(W,\mathbf{c})$ consisting of those subwords $\mathbf{u}$
such that each colored reflection in $\mathrm{inv}_{e}(\mathbf{u})$ has even
color. By Theorem 8.7, the map $\mathbf{u}\mapsto\mathrm{inv}_{e}(\mathbf{u})$
is a bijection
$\mathrm{Clus}^{(2k)}(W,\mathbf{c})\xrightarrow{\sim}\mathrm{NC}^{(2k)}(W,\mathbf{c})$.
Therefore, by Definition 8.4, $\mathcal{M}_{e,\mathbf{c}^{kh+1}}$ is in
bijection with sequences
$\big{(}(t_{1},2k_{1}),(t_{2},2k_{2}),\ldots,(t_{r},2k_{r})\big{)}$ satisfying

  * •

$t_{1}t_{2}\cdots t_{r}=c$,

  * •

$0\leq k_{1}\leq\cdots\leq k_{r}\leq k$, and

  * •