2.1 Partitions

Let $n$ be a positive integer. A composition of $n$ is a sequence $\mu =(\mu _1,\dots ,\mu _\ell )$ of positive integers that sum to $n$ . We let $\ell (\mu )$ denote the length of $\mu$ , the number of its parts, and $|\mu |:=\sum _{i}\mu _i$ its size. We say that a composition $\mu$ is a partition if its parts are weakly decreasing. We use the notation $\mu \models n$ to indicate that $\mu$ is a composition of $n$ , and $\mu \vdash n$ to indicate that $\mu$ is a partition of $n$ . We use Young diagrams in French notation to display a partition as

\begin{equation*} \mu =\{(i,j)\in \mathbb {Z}_+\times \mathbb {Z}_+ : j\le \mu _i\}, \end{equation*}

where each element of this set represents a cell in the diagram. The conjugate partition of $\mu$ , denoted by $\mu ^{\prime}=(\mu ^{\prime}_1,\mu ^{\prime}_2,\dots )$ , is obtained by reflecting the Young diagram of $\mu$ along the diagonal $y=x$ .

For a cell $u$ in a partition $\mu$ , we define the arm (coarm) of $u$ , denoted by $\mathrm {arm}_\mu (u)$ ( $\mathrm {coarm}_\mu (u)$ ), as the number of cells strictly to the right (left) of $u$ in the same row. Similarly, we define the leg (coleg) of $u$ , denoted by $\mathrm {leg}_\mu (u)$ ( $\mathrm {coleg}_\mu (u)$ ), as the number of cells strictly above (below) $u$ in the same column. For example, for a partition $\mu =(5,4,3,1)$ and a cell $u=(2,2)$ , we have $\mathrm {arm}_\mu (u)=2, \mathrm {coarm}_\mu (u)=1, \mathrm {leg}_\mu (u)=1$ and $\mathrm {coleg}(u)_\mu =1$ as displayed in the following diagram.

2.2 Symmetric functions

Let $\mathbf {Sym}$ be the graded ring of symmetric functions in infinite variables $X=x_1,x_2,\dots$ over the ground field $\mathbb {C}(q,t)$ . We use the notation from [Reference MacdonaldMac88] for families of symmetric functions indexed by a partition: $m_\lambda$ for the monomial symmetric function, $h_\lambda$ for the homogeneous symmetric function, $e_\lambda$ for the elementary symmetric function, $p_\lambda$ for the power sum symmetric function, $s_\lambda$ for the Schur function, and $J_\lambda$ for the integral form Macdonald polynomial (or Macdonald $J$ -polynomial). The (Hall) inner product on symmetric functions, denoted by $\langle -,-\rangle$ , is defined by

\begin{equation*} \langle s_\lambda , s_\mu \rangle = \delta _{\lambda ,\mu }. \end{equation*}

The modified Macdonald polynomials are defined using a plethystic substitution as follows:

\begin{equation*} \widetilde {H}_\mu [X;q,t] = t^{n(\mu )}J_\mu \bigg[\dfrac {X}{1-t^{-1}};q,t^{-1}\bigg], \end{equation*}

where $n(\mu )=\sum _i (i-1)\mu _i$ . Each of the above families of symmetric functions form a basis for $\mathbf {Sym}$ .

2.3 Quasisymmetric functions

Let $\mathbf {QSym}$ be the graded ring of quasisymmetric functions in infinite variables $X=x_1,x_2,\dots$ over the ground field $\mathbb {C}(q,t)$ . Given a composition $\alpha =(\alpha _1,\alpha _2,\dots ,\alpha _\ell )\models n$ , the monomial quasisymmetric function $M_\alpha [X]$ is defined by

\begin{equation*} M_\alpha [X] := \sum _{i_1\lt i_2\lt \cdots \lt i_\ell } x_{i_1}^{\alpha _1}x_{i_2}^{\alpha _2}\cdots x_{i_\ell }^{\alpha _\ell }, \end{equation*}

and the (Gessel’s) fundamental quasisymmetric function [Reference GesselGes84] $F_\alpha [X]$ is defined by

\begin{equation*} F_\alpha [X] := \sum _{\beta \le \alpha }M_\beta , \end{equation*}

where $\beta \le \alpha$ means we can obtain $\alpha$ by adding consecutive parts of $\beta$ . Each of the above two families forms a basis for $\mathbf {QSym}$ .

Compositions of $n$ are in one-to-one correspondence with the subsets of $[n-1]$ . We will define the natural bijection $\mathrm {Comp}$ from $2^{[n-1]}$ to compositions of $n$ by

\begin{align*} \mathrm {Comp}:\{s_1\lt s_2\lt \cdots \lt s_\ell \} \mapsto (s_1,s_2-s_1,\dots ,s_\ell -s_{\ell -1},n-s_\ell ), \quad \mathrm {Comp}({\varnothing })=(n). \end{align*}

The inverse of $\mathrm {Comp}$ is denoted by $\mathrm {Set}$ . Under this correspondence, for a subset $S\subseteq [n-1]$ , we write $F_{n,S}$ as shorthand for $F_{\mathrm {Comp}(S)}$ . If $n$ is clear from the context, we write $F_{S}$ for $F_{n,S}$ . Given a permutation $w\in \mathfrak {S}_n$ , we will usually associate to it a fundamental quasisymmetric function $F_{\mathrm {iDes}(w)}$ , where

\begin{equation*} \mathrm {iDes}(w):=\mathrm {Des}(w^{-1})=\left\{i:w^{-1}_i\gt w^{-1}_{i+1}\right\}. \end{equation*}

We end this section with a useful identity which will be used in § 6. For $n\ge 1$ , define a linear operator $E_n^\perp$ on $\mathbf {QSym}$ by

(2.1) \begin{align} E_{n}^\perp F_\alpha =\begin{cases} F_{\beta ^-} & \text {if} \ \alpha = (1^{(n-1)},\beta ),\\ 0 & \text {otherwise}, \end{cases} \end{align}

where $\beta ^-$ is the composition obtained by subtracting one from the first component of $\beta$ if $\beta _1\gt 1$ , with $\beta ^{-}=(\beta _2,\dots )$ otherwise. It is worth noting that for a composition $\beta =(b_1,\dots ,b_r)$ there are two compositions

\begin{equation*} \alpha ^{(1)}=(\underbrace {1,\dots ,1}_{n-1},b_1+1,b_2,\dots ,b_r), \quad \alpha ^{(2)}=(\underbrace {1,\dots ,1}_{n},b_1,\dots ,b_r) \end{equation*}

such that $E_{n}^\perp F_{\alpha ^{(1)}}=E_{n}^\perp F_{\alpha ^{(2)}}=F_{\beta }$ . Then the skewing operator $e_n^\perp$ on symmetric functions is related to $E_n^\perp$ as follows.

Proposition 2.1 [Reference Gelfand, Krob, Lascoux, Leclerc, Retakh and ThibonGKLLRT95]. For a symmetric function $f$ , we have

\begin{equation*} e_n^\perp f = E_n^\perp f, \end{equation*}

where $f$ on the right-hand side is considered a quasisymmetric function.

For the rest of the paper, we abuse the notation and refer to $E_n^{\perp }f$ as $e_n^{\perp }f$ for $f\in \mathbf {QSym}$ .

3.1 Plethystic formula for the Macdonald polynomials

We first review the plethystic formula for Macdonald polynomials studied by Garsia, Haiman, and Tesler in [Reference Garsia and TeslerGT96, Reference Garsia, Haiman and TeslerGHT99]. To do so, we introduce some relevant notation and basic facts. Let $g[t_1,t_2,\dots ]$ be a Laurent series in the variables $t_1,t_2,\dots$ . If a symmetric function $f$ is expressed as the formal power series

\begin{equation*} f = \hat {f}[p_1,p_2,\dots ], \end{equation*}

then the plethystic substitution of $g$ into $f$ is

\begin{equation*} f[g] = \hat {f}[p_1,p_2,\dots ]|_{p_k\mapsto g[t_1^k,t_2^k,\dots ]}. \end{equation*}

We will use brackets to denote plethystic substitutions. We use two different minus signs, $-$ and $\epsilon$ , to mean

\begin{equation*} p_k[-X]=-p_k[X] \quad \text { and } \quad p_k[\epsilon X] = (-1)^k p_k[X]. \end{equation*}

It is worth noting that for a symmetric function $f$ , we have

\begin{equation*} \omega f [X] = f[-\epsilon X], \end{equation*}

where $\omega$ is the involution on $\mathbf {Sym}$ sending $p_\lambda \rightarrow (-1)^{|\lambda |-\ell (\lambda )}p_\lambda$ . We denote the biexponent generator for a given partition $\mu$ by $B_\mu (q,t)$ , which can be expressed as

\begin{equation*}B_\mu (q,t) := \sum _{c\in \mu } q^{\mathrm {coarm}_\mu (c)}t^{\mathrm {coleg}_\mu (c)}.\end{equation*}

Additionally, we define $M := (1-q)(1-t)$ and $D_\mu =D_\mu (q,t) := MB_\mu (q,t) - 1$ .

Following the notation of [Reference Garsia and TeslerGT96], the $*$ -inner product, denoted by $\langle -, - \rangle _*$ , is defined by

\begin{equation*}\langle p_{\rho },p_{\nu }\rangle _* = \begin{cases} (-1)^{|\rho |-\ell (\rho )} z_\rho \prod _i (1-q^{\rho _i})(1-t^{\rho _i}) & \text { if } \rho =\nu, \\ 0 & \text { otherwise,}\end{cases}\end{equation*}

where $z_\rho$ is the integer that makes $n!/z_\rho$ the number of permutations of cycle type $\rho$ . It is straightforward to check that $\langle f,g\rangle _*=\langle \omega (f),\omega (g)\rangle _*$ for any symmetric functions $f$ and $g$ . The modified Macdonald polynomials form an orthogonal basis with respect to the $*$ -inner product [Reference Garsia and TeslerGT96, Theorem 1.1]. In particular, we have

(3.1) \begin{equation} \big\langle \widetilde {H}_\mu ,\widetilde {H}_\lambda \big\rangle _*=\begin{cases} \tilde {h}_\mu (q,t)\tilde {h}^{\prime}_\mu (q,t) &\text { if } \mu = \lambda, \\ 0, &\text { otherwise,} \end{cases} \end{equation}

where

\begin{equation*} \tilde {h}_\mu (q,t) =\prod _{c\in \mu }\big(q^{\mathrm {arm}_\mu (c)}-t^{\mathrm {leg}_\mu (c)+1}\big) \quad \text {and} \quad \tilde {h}^{\prime}_\mu (q,t)=\prod _{c\in \mu }(t^{\mathrm {leg}_\mu (c)}- q^{\mathrm {arm}_\mu (c)+1}). \end{equation*}

The $*$ -inner product has several useful properties, one of which is [Reference Garsia, Haiman and TeslerGHT99, Proposition 1.8]: for two symmetric functions $P$ and $Q$ of degree $n$ , we have

(3.2) \begin{equation} \langle P[X],Q[X] \rangle _* = \langle P[MX], \omega Q[X]\rangle , \end{equation}

where $\langle -,-\rangle$ is the usual Hall inner product.

Garsia, Haiman, and Tesler provided a general result for the $*$ -inner product with modified Macdonald polynomials, which extends the plethystic formula for the $(q,t)$ -Kostka polynomials due to Garsia and Tesler [Reference Garsia and TeslerGT96]. To state their result, it is helpful to introduce the notation $g^*[X] := g[X/M]$ for a symmetric function $g[X]$ . The main theorem of their work can be presented as follows.

Theorem 3.1 [Reference Garsia, Haiman and TeslerGHT99, Theorem 1.2]. For a symmetric function $f$ , define $\Pi ^{\prime}_f$ by

\begin{equation*} \Pi ^{\prime}_f[X;q,t] := \nabla ^{-1} f[X-\epsilon ]. \end{equation*}

Then for every partition $\mu \vdash n \geq m$ we have

\begin{equation*} \langle e^*_{n-m}f,\widetilde {H}_\mu \rangle _* = \Pi ^{\prime}_f[D_\mu ;q,t]. \end{equation*}

3.2 Proof of Theorem 1.1 parts (a) and (b)

Let $\mu$ be a partition of $n$ . By applying (3.2) and Theorem 3.1, we have

\begin{align*} \Pi ^{\prime}_{f}[D_\mu ;q,t] &= \langle e_{n-m}f[MX], \omega \widetilde {H}_\mu \rangle =\langle f[MX], e_{n-m}^\perp \omega \widetilde {H}_\mu \rangle \\ &=\langle f[X], \omega (e_{n-m}^\perp \omega \widetilde {H}_\mu ) \rangle _*= \langle \omega f[X], e_{n-m}^\perp \omega \widetilde {H}_\mu \rangle _*. \end{align*}

For a partition $\lambda \vdash m$ , we let $f$ in the above equation be $\widetilde {H}_\lambda$ . We apply the well-known symmetry of modified Macdonald polynomials (e.g. Theorem 1.5 in [Reference Garsia and TeslerGT96]), which is

\begin{equation*} \omega \widetilde {H}_\mu =T_\mu \mathrm {rev}(\widetilde {H}_\mu ), \end{equation*}

where $\mathrm {rev}$ is an involution on $\mathbf {Sym}$ defined by $(q,t)$ -reversal:

\begin{equation*} \mathrm {rev}(f) = f|_{q\mapsto q^{-1}, t\mapsto t^{-1}}. \end{equation*}

Then we have

(3.3) \begin{align} \Pi ^{\prime}_{\widetilde {H}_\lambda }[D_\mu ;q,t] &= \langle \omega \widetilde {H}_\lambda [X], e_{n-m}^\perp \omega \widetilde {H}_\mu \rangle _* \nonumber\\&= \langle T_\lambda \mathrm{rev}(\widetilde {H}_\lambda ),T_\mu e^{\perp}_{n-m} \mathrm{rev}(\widetilde {H}_\mu )\rangle _{*} = T_\mu T_\lambda \langle \mathrm {rev}(\widetilde {H}_\lambda ), e^\perp _{n-m} \mathrm {rev}(\widetilde {H}_\mu )\rangle _*. \end{align}

To extract the operator $\mathrm {rev}$ to the outside of the $*$ -inner product, we need the following lemma.

Lemma 3.2. For two symmetric functions $f,g \in \mathbf {Sym}$ of degree $m$ , we have

\begin{equation*} \langle \mathrm {rev}(f), \mathrm {rev}(g) \rangle _*= (qt)^m \mathrm {rev}\left (\langle f, g \rangle _* \right ). \end{equation*}

Proof. It suffices to show the claim for $p_{\rho }\mbox{ and }p_{\nu }$ for partitions $\rho ,\nu \vdash m$ . We have

\begin{align*} \langle \mathrm {rev}(p_{\rho }), \mathrm {rev}(p_\nu ) \rangle _* &= \langle p_\rho , p_\nu \rangle _* = (-1)^{|\rho |-\ell (\rho )}z_\rho \delta _{\rho ,\nu } \prod _{i\ge 1}(1-q^{\rho _i})(1-t^{\rho _i}) \\ &= (qt)^m (-1)^{|\rho |-\ell (\rho )}z_\rho \delta _{\rho ,\nu } \prod _{i\ge 1}(1-q^{-\rho _i})(1-t^{-\rho _i}) = (qt)^m \mathrm {rev}\left (\langle p_\rho ,p_\nu \rangle _* \right ). \end{align*}

Applying Lemma 3.2 to (3.3) gives

\begin{equation*} \dfrac {1}{(qt)^mT_\mu T_\lambda }\langle \widetilde {H}_\lambda , e_{n-m}^\perp \widetilde {H}_\mu \rangle _*= \mathrm {rev} (\Pi ^{\prime}_{\widetilde {H}_\lambda }[D_\mu ;q,t]). \end{equation*}

By using the orthogonality relation (3.1), we see that

(3.4) \begin{equation} e_{n-m}^\perp \widetilde {H}_\mu = (qt)^m T_\mu \sum _{\lambda \vdash m} \mathrm {rev} (\Pi ^{\prime}_{\widetilde {H}_\lambda }[D_\mu ;q,t] )\dfrac {T_\lambda \widetilde {H}_\lambda }{\tilde {h}_\lambda \tilde {h}^{\prime}_\lambda }. \end{equation}

Now, let $\mu \vdash n+1$ be a partition and let $\mu ^{(1)},\dots ,\mu ^{(k)}\subseteq \mu$ be $k$ distinct partitions such that

\begin{equation*} |\mu \setminus \mu ^{(1)}|=\cdots =|\mu \setminus \mu ^{(k)}|=1. \end{equation*}

Then the Macdonald intersection polynomial can be written as

\begin{equation*} \mathrm {I}_{\mu ^{(1)},\dots ,\mu ^{(k)}}[X;q,t] =\sum _{i=1}^k \prod _{j\neq i}\bigg(\frac {z_j}{z_j-z_i}\bigg) \widetilde {H}_{\mu ^{(i)}}, \end{equation*}

where we write $z_i=T_{\mu ^{(i)}}/T_\mu$ . Note that $T_{\mu ^{(i)}}=z_iT_\mu$ and $T_{\cap _{i=1}^k \mu ^{(i)}}=z_1\cdots z_k T_\mu$ . Then using (3.4) we can show that $e^\perp _{n-m}\mathrm {I}_{\mu ^{(1)},\dots ,\mu ^{(k)}}[X;q,t]$ is equal to

(3.5) \begin{align} &(qt)^m {z_1\cdots z_k T_\mu } \sum _{\lambda \vdash m} \bigg (\sum _{i=1}^k \frac {\mathrm {rev}(\Pi ^{\prime}_{\widetilde {H}_\lambda }[D_{\mu ^{(i)}};q,t] )}{\prod _{j\neq i}(z_j-z_i)} \bigg )\dfrac {T_\lambda \widetilde {H}_\lambda }{\tilde {h}_\lambda \tilde {h}^{\prime}_\lambda }\nonumber \\[5pt] &\quad =(qt)^m T_{\cap _{i=1}^k \mu ^{(i)}} \sum _{\lambda \vdash m} \bigg (\sum _{i=1}^k \frac {\mathrm {rev} (\Pi ^{\prime}_{\widetilde {H}_\lambda }[D_{\mu ^{(i)}};q,t] )}{\prod _{j\neq i}(z_j-z_i)} \bigg)\dfrac {T_\lambda \widetilde {H}_\lambda }{\tilde {h}_\lambda \tilde {h}^{\prime}_\lambda }. \end{align}

We will make use of a well-known equality, which we state as a lemma.

Lemma 3.3. Let $z_1,\ldots ,z_k$ be variables. Then for a polynomial $g(z)$ (in one variable $z$ ) of degree less than $k-1$ , we have

\begin{equation*}\sum _{i=1}^k \dfrac {g(z_i)}{\prod _{j \neq i} (z_j-z_i)}=0.\end{equation*}

If $g(z)$ is a polynomial of degree $k-1$ with leading term $az^{k-1}$ , then

\begin{equation*}\sum _{i=1}^k \dfrac {g(z_i)}{\prod _{j \neq i} (z_j-z_i)}=(-1)^{k-1}a.\end{equation*}

Proof of Theorem 1.1(a) (Vanishing identity). Consider the expression in (3.5) and assume $m\lt k-1$ . Then the term

\begin{align*} \mathrm {rev}(\Pi ^{\prime}_{\widetilde {H}_{\lambda}} [D_\mu ^{(i)};q,t]))&= \mathrm {rev}(\nabla ^{-1}\widetilde {H}_\lambda \left [D_\mu -\epsilon -Mz_i^{-1};q,t\right ]) \\[4pt] &=T_\lambda \widetilde {H}_\lambda \bigg[D_\mu (q^{-1},t^{-1}) -\epsilon - \dfrac {M}{qt}z_i;q^{-1},t^{-1}\bigg ] \end{align*}

is a polynomial in $z_i$ of degree $m$ which is less than $k-1$ . As a consequence, using Lemma 3.3, we have that (3.5) vanishes. This completes the proof.

Proof of Theorem 1.1(b). In (3.5), let $m=k-1$ . Then

\begin{equation*} \mathrm {rev}(\Pi ^{\prime}_{\widetilde {H}_{\lambda}} \,[D_\mu ;q,t]))=T_\lambda \widetilde {H}_\lambda \bigg[D_\mu (q^{-1},t^{-1}) -\epsilon - \dfrac {M}{qt}z_i;q^{-1},t^{-1}\bigg] \end{equation*}

is a polynomial of degree $k-1$ in $z_i$ . Moreover, the leading term is equal to

\begin{align*} T_\lambda \widetilde {H}_\lambda \bigg[-\dfrac {M}{qt};q^{-1},t^{-1}\bigg] &= \omega \widetilde {H}_\lambda \bigg[-\dfrac {M}{qt};q,t\bigg] \\[4pt]&=(-qt)^{1-k} \widetilde {H}_\lambda \left [M;q,t\right ] \\[4pt]&=(-qt)^{1-k} M \Pi _\lambda B_\lambda, \end{align*}

where $\Pi _{\lambda }$ is a constant associated to a partition $\lambda$ and is defined as

\begin{equation*} \Pi _{\lambda }:=\prod _{c\in \lambda \setminus \{(1,1)\}}(1-q^{\mathrm {coarm}_{\lambda }(c)}t^{\mathrm {coleg}_{\lambda }(c)}). \end{equation*}

Here, the last equality can be obtained from the generalized Macdonald–Koornwinder reciprocity [Reference Garsia, Haiman and TeslerGHT99, Theorem 3.3] when $\mu =(1)$ . Using Lemma 3.3, (3.5) becomes

\begin{align*} e_{n+1-k}^\perp \mathrm {I}_{\mu ^{(1)},\dots ,\mu ^{(k)}}[X;q,t] &= (qt)^{k-1}T_{\bigcap _{i=1}^k \mu ^{(i)}} \sum _{\lambda \vdash k-1} \bigg (\sum _{i=1}^k \prod _{j\neq i}\frac {1}{z_j-z_i} \mathrm {rev}(\Pi ^{\prime}_{\widetilde {H}_\lambda }[D_\mu ;q,t]))\bigg)\dfrac {T_\lambda \widetilde {H}_\lambda }{\tilde {h}_\lambda \tilde {h}^{\prime}_\lambda } \\&=T_{\bigcap _{i=1}^k \mu ^{(i)}} \sum _{\lambda \vdash k-1} \dfrac {M \Pi _\lambda B_\lambda T_\lambda \widetilde {H}_\lambda }{\tilde {h}_\lambda \tilde {h}^{\prime}_\lambda }=T_{\bigcap _{i=1}^k \mu ^{(i)}} \nabla e_{k-1}, \end{align*}

where the last equality is from [Reference HaimanHai02, Theorem 3.2].

4.1 Fermionic formulas

Several important families of $q$ -polynomials that arise in combinatorics and representation theory can be expressed using fermionic formulas. These formulas involve a sum of products of $q$ -multinomials and nonnegative powers of $q$ . The origin of these formulas can be traced back to the Bethe ansatz [Reference BetheBet93] and $q$ -Kostka polynomial $K_{\lambda ,\mu }(q)$ (see [Reference Kerov, Kirillov and ReshetikhinKKR86]). Similarly, we refer to a fermionic formula for the sums of products of $q$ -multinomials and nonnegative powers of $q$ and $t$ .

Garsia and Haiman [Reference Garsia and HaimanGH96a] introduced a rational function $C_n(q,t)$ called the $q,t$ -Catalan numbers and conjectured that $C_n(q,t)$ is the Hilbert series of the diagonal coinvariant alternants, or $\langle D_n[X;q,t], e_n\rangle$ . This number $C_n(q,t)$ specializes to the well-known $q$ -Catalan numbers

\begin{equation*} q^{\binom {n}{2}}C_n(q,1/q) = C^{(1)}_n(q) \quad \text {and}\quad C_n(1,q)=C_n(q,1)=C^{(2)}_n(q), \end{equation*}

where $C^{(1)}_n(q)$ is the major-index generating function over Dyck words and $C^{(2)}_n(q)$ is the area generating function for Dyck paths, justifying the name $q,t$ -Catalan numbers. Haglund [Reference HaglundHag03] gave a fermionic formula for $C_n(q,t)$ :

(4.1) \begin{equation} C_n(q,t) = \sum _{\alpha \models n} t^{\sum _{i=1}^{\ell (\alpha )}(i-1)\alpha _i}q^{\sum _{i=1}^{\ell (\alpha )} \binom {\alpha _i}{2} } \prod _{1\le i\le \ell (\alpha )-1} \bigg(\begin{array}{c}\alpha _i + \alpha _{i+1} -1\\[3pt]\alpha _{i+1}\end{array}\bigg)_{\!\!q}. \end{equation}

Meanwhile, Haglund and Loehr [Reference Haglund and LoehrHL05] conjectured a fermionic formula for the Hilbert series of the diagonal coinvariant algebra, or $\mathcal {H}_n(q,t)=\langle D_n[X;q,t], e_{(1^n)} \rangle$ . This conjecture was eventually proved in [Reference Carlsson and MellitCM18, Reference Carlsson and OblomkovCO18], yielding the formula

(4.2) \begin{equation} \mathcal {H}_n(q,t) = \sum _{\sigma \in \mathfrak {S}_n}t^{\mathrm {maj}(\sigma )}\prod _{i=1}^{n} [u_i(\sigma )-1]_q, \end{equation}

where $\mathrm {maj}(\sigma )=\sum _{i\in \mathrm {Des}(\sigma )}i$ and $u_i$ is defined as follows. For a permutation $\sigma$ , define a sequence $\sigma ^{\prime}$ by setting $\sigma ^{\prime}_i=\sigma _i$ for $1\le i \le n$ and $\sigma ^{\prime}_{n+1}=0$ . For each $1 \le i \le n$ , $u_i(\sigma )$ is the length of the longest consecutive sequence $\sigma ^{\prime}_{i},\dots, \sigma ^{\prime}_{j}$ satisfying either of the following:

• – $\sigma ^{\prime}_{i},\dots, \sigma ^{\prime}_{j}$ has no descent;

• – $\sigma ^{\prime}_{i},\dots, \sigma ^{\prime}_{j}$ has one descent and $\sigma ^{\prime}_i\gt \sigma ^{\prime}_j$ .

In § 4.2, we review a generalization (Theorem 4.6) of these two fermionic formulas (4.1) and (4.2).

4.2 Modified labeled Dyck paths and the shuffle formula

The shuffle theorem concerns a combinatorial formula $D_n[X;q,t]$ for $\nabla e_n$ as a generating function over parking functions. Several equivalent formulations of $D_n[X;q,t]$ exist in the literature. For our purpose, we will use the version presented in [Reference Loehr and NieseLN14, Theorem 14] employing the concept of modified labeled Dyck paths, which Haglund and Loehr first investigated in [Reference Haglund and LoehrHL05].

Definition 4.1. A Dyck path of length $n$ is a lattice path from $(0,0)$ to $(n,n)$ that does not go below the line $y=x$ . We denote a Dyck path by a sequence of $E$ and $N$ , where $E$ is an eastward step and $N$ is a northward step. We say that a Dyck path has a corner at $(i,j)$ if there is an eastward step from $(i-1,j)$ to $(i,j)$ followed by a northward step from $(i,j)$ to $(i,j+1)$ . Given a Dyck path $\pi$ and a permutation $w$ , a labeled Dyck path $L(\pi ,w)$ is a Dyck path $\pi$ with its $i$ th eastward step and $i$ th northward step labeled by $w_{n+1-i}$ . For example, in the left diagram of Figure 1, $\pi =NNNENNENEEEE$ and $w=326514$ , so we have

\begin{equation*} L(\pi ,w)=((N,4),(N,1),(N,5),(E,4),(N,6),(N,2),(E,1),(N,3),(E,5),(E,6),(E,2),(E,3)). \end{equation*}

The permutation $w$ can be obtained from $L(\pi ,w)$ by reading labels of the northward steps from top to bottom (or, equivalently, by reading labels of the eastward steps from right to left). We say that a pair $(\pi ,w)$ is a modified labeled Dyck path if for each corner of $\pi$ at $(i,j)$ , the label of the $i$ th eastward step is less than the label of the $(j+1)$ th northward step in $L(\pi ,w)$ . We represent a modified labeled Dyck path $(\pi ,w)$ by a Dyck path $\pi$ and a permutation $w$ assigned to the diagonal $y=x$ from top to bottom.

The set of modified labeled Dyck paths of length $n$ will be denoted by $\mathrm {MLD}(n)$ . We call a cell an $(i, j)$ -box if $i$ and $j$ are the $x$ - and $y$ -coordinates of its upper-right corner. Then for a pair $(\pi ,w)$ of a Dyck path $\pi$ of length $n$ and a permutation $w$ of length $n$ , the quantity $\mathrm {area}^{\prime}(\pi ,w)$ is defined as the number of pairs $(i,j)$ such that the $(i,j)$ -box lies between $\pi$ and the diagonal $y=x$ and the label of the $i$ th eastward step is less than the label of the $j$ th northward step in $L(\pi ,w)$ .

Given a Dyck path $\pi$ of length $n$ , we define its bounce path as follows. Begin at $(0,0)$ and move northward until the beginning of an eastward step is encountered. Then, travel eastward until the diagonal $y=x$ is reached. From this point, repeat the process by traveling northward until the next eastward step is encountered and then moving eastward until the diagonal $y=x$ is reached. Continue this manner until we reach $(n,n)$ . The bounce vector $\overrightarrow {b}(\pi )=(\alpha _1,\alpha _2,\dots )$ associated to the Dyck path is a composition of $n$ , obtained by reading the lengths of the individual bounces of the path from bottom to top. Then we define $\mathrm {bounce}(\pi )$ to be $\sum _{i=1}^{\ell (\alpha )}(i-1)\alpha _i$ .

Figure 1

An example and a nonexample of a modified labeled Dyck path.

The following theorem reformulates the shuffle formula $D_n[X;q,t]$ in terms of modified labeled Dyck paths.

Theorem 4.3 [Reference Loehr and NieseLN14, Theorem 14]. We have

\begin{equation*} D_n[X;q,t]=\sum _{(\pi ,w)\in \mathrm {MLD}(n)}t^{\mathrm {bounce}(\pi )}q^{\mathrm {area}^{\prime}(\pi ,w)}F_{\mathrm {iDes}(w)}. \end{equation*}

In other words, the shuffle theorem is equivalent to the identity

\begin{equation*} \nabla e_n=\sum _{(\pi ,w)\in \mathrm {MLD}(n)}t^{\mathrm {bounce}(\pi )}q^{\mathrm {area}^{\prime}(\pi ,w)}F_{\mathrm {iDes}(w)}. \end{equation*}

4.3 The fermionic formula

For a (quasi)symmetric function $f$ of degree $n$ and a composition $\beta \models n$ , we denote by $[F_{\beta }](f)$ the coefficient of $F_{\beta }$ in the expansion of $f$ into fundamental quasisymmetric functions. Then the following lemma is immediate.

Lemma 4.4. For a composition $\beta =(\beta _1,\beta _2,\dots )$ of $n$ , let $e_\beta =e_{\beta _1}e_{\beta _2}\cdots$ be the elementary symmetric function. Then for a symmetric function $f$ of homogeneous degree $n$ , we have

\begin{equation*} \langle f, e_{\beta }\rangle = \sum _{\substack {\alpha \models n \\ [n-1]\setminus \mathrm {Set}(\beta ) \subseteq \mathrm {Set}(\alpha ) }}[F_\alpha ](f), \end{equation*}

where the map $\mathrm {Set}$ is the bijection between compositions of $n$ and $2^{[n-1]}$ .

It is easy to check that given a permutation $w\in \mathfrak {S}_n$ , we have

(4.3) \begin{equation} \langle F_{\mathrm {Des}(w)}),e_{\beta }\rangle =1 \quad \text {if and only if}\quad \{i: w_{i}\lt w_{i+1}\}\subseteq \mathrm {Set}(\beta ). \end{equation}

Note that (4.1) and (4.2) give fermionic formulas for $\langle D_n[X;q,t],e_{n}\rangle$ and $\langle D_n[X;q,t],e_{(1^n)}\rangle$ , respectively. We will present a fermionic formula for $\langle D_{n}[X;q,t],e_{\beta }\rangle$ for general compositions $\beta \models n$ , which essentially follows from [Reference Haglund, Haiman, Loehr, Remmel and UlyanovHHLRU05, Equation (63)]. With that purpose in mind, we introduce some notation.

For positive integers $i\mbox{ and }j$ , the lightning bolt set $\mathrm {LB}(i,j)$ is the set of positions that are weakly above $(i,j-1)$ together with the positions that are weakly below $(i,j)$ :

\begin{equation*} \mathrm {LB}(i,j) := \{(a,j-1):a\le i\} \cup \{(a,j):a\ge i\}. \end{equation*}

Here, we have used matrix coordinates for $(i, j)$ . Illustratively, the set $\mathrm {LB}(i,j)$ can be represented as in Figure 2.

Figure 2

The lightning bolt set $\mathrm {LB}(i,j)$ .

We denote the set of nonnegative integer matrices by $\mathrm {Mat}^{\ge 0}=\bigcup _{1\le r,\ell }{\mathrm {Mat}^{\ge 0}_{r\times \ell }}$ , where $\mathrm {Mat}^{\ge 0}_{r\times \ell }$ is the set of nonnegative integer matrices with $r$ rows and $\ell$ columns. A row sum vector (respectively, column sum vector) of a matrix $M$ is denoted by $\mathrm {rsum}(M)$ (respectively, $\mathrm {csum}(M)$ ), and let $|M|$ be the sum of entries of $M$ . For example, the matrix

\begin{equation*} M=\bigg[\begin{matrix} a & \quad b \\ c & \quad d \end{matrix}\bigg] \end{equation*}

gives $\mathrm {rsum}(M)=(a+b,c+d)$ , $\mathrm {csum}(M)=(a+c,b+d)$ , and $|M|= a+b+c+d$ . For a matrix $M\in \mathrm {Mat}^{\ge 0}_{r\times \ell }$ and $1\le i \le r, 2 \le j \le \ell$ , we define $\mathrm {lb}(M;(i,j))$ as

\begin{equation*} \mathrm {lb}(M;(i,j)) := \sum _{(a,b)\in \mathrm {LB}(i,j)}M_{a,b}. \end{equation*}

We also define $\mathrm {lb}(M)$ as

\begin{equation*} \mathrm {lb}(M) := \binom {M_{1,1}+\dots +M_{r,1}}{M_{1,1},\dots ,M_{r,1}}_{\!\!q} \prod _{\substack {1\le i \le r\\ 2\le j \le \ell }} \binom {\mathrm {lb}(M;(i,j))-1}{M_{i,j}}_q, \end{equation*}

where the first term on the right is the $q$ -multinomial coefficient and the second term is the product of $q$ -binomial coefficients. We use the convention $\binom {-1}{0}_q=\binom {0}{0}_q=1$ . The following basic property of $\mathrm {lb}(M)$ is worth noting.

We now state the fermionic formula for $\langle D_n[X;q,t],e_{\beta }\rangle$ of Haglund et al. [Reference Haglund, Haiman, Loehr, Remmel and UlyanovHHLRU05]. Their original formulation uses the concept of a ‘ $\beta$ -shuffle’, whereas we employ a different formulation. Specifically, $\langle D_n[X;q,t],e_{\beta }\rangle$ is expressed as a sum of products of $\mathrm {lb}(M)$ and nonnegative powers of $q$ and $t$ over all nonnegative integer matrices $M$ of size $\ell (\beta ) \times \ell (\alpha )$ that satisfy certain constraints.

Theorem 4.6 [Reference Haglund, Haiman, Loehr, Remmel and UlyanovHHLRU05]. For a composition $\beta \models n$ , we have

\begin{equation*} \langle D_n[X;q,t],e_{\beta }\rangle = \sum _{\alpha \models n} t^{\sum _{i=1}^{\ell (\alpha )}(i-1)\alpha _i} \sum _{\substack {M \in \mathrm {Mat}^{\ge 0} \\ \mathrm {rsum}(M)=\beta \\ \mathrm {csum}(M)=\alpha }} q^{\sum _{i,j}\binom {M_{i,j}}{2} } \mathrm {lb}(M). \end{equation*}

For the sake of completeness, we provide a proof in § 4.4 of our formulation. We end this section with an explanation of how (4.1) and (4.2) can be regarded as special cases of the theorem above. Observe that the fermionic formula for $q,t$ -Catalan numbers (4.1) can be derived directly from Theorem 4.6 by setting $\beta =(n)$ .

To demonstrate that (4.2) also follows from Theorem 4.6, let $\beta =(1^n)$ . In this scenario, the summation is conducted over all nonnegative integer matrices with $n$ rows, each of whose rows contains precisely one nonzero entry, which is 1.

We can establish a correspondence between such matrices $M$ and permutations $\sigma (M)$ as follows: read the row numbers of the ones from top to bottom, starting from the rightmost column and moving leftward. For instance, the matrix

(4.4) \begin{equation} M=\begin{bmatrix} 1 & \quad 0 & \quad 0\\ 0 & \quad 1 & \quad 0\\ 1 & \quad 0 & \quad 0\\ 0 & \quad 0 & \quad 1 \end{bmatrix} \end{equation}

corresponds to the permutation $\sigma (M)=4213$ . For a permutation $\sigma \in \mathfrak {S}_n$ , let $\mathrm {Des}(\sigma )=\{d_1\lt \cdots \lt d_{\ell }\}$ . Then for $1\leq i \leq \ell +1$ , we define a word $\sigma ^{(i)}:=\sigma _{d_{i-1}+1}\cdots \sigma _{d_{i}}$ where we set $d_0=0$ and $d_{\ell +1}=n$ . In other words, $\sigma ^{(i)}$ is the $i$ th increasing run of $\sigma$ . For example, for $\sigma =4213$ we have $\sigma ^{(1)}=4$ , $\sigma ^{(2)}=2$ , and $\sigma ^{(3)}=13$ . Now we define an $n\times (\ell +1)$ matrix $M(\sigma )$ by letting its entries be defined as follows:

\begin{equation*} M(\sigma )_{i,j}:= \begin{cases} 1&\text { if } i\text { appears in } \sigma ^{(\ell +2-j)},\\ 0&\text { otherwise}. \end{cases} \end{equation*}

It is straightforward to see that $M(4213)$ is the matrix $M$ given in (4.4). We claim that $M(\sigma )$ is the unique matrix $M$ with $\mathrm {lb}(M)\neq 0$ among matrices satisfying $\sigma (M)=\sigma$ . To see this, suppose that $M^{\prime}$ is a matrix with $\sigma (M^{\prime})=\sigma$ and $M^{\prime}\neq M(\sigma )$ . Then there exists $\sigma ^{(r)}$ such that there are distinct $i, i^{\prime} \in \sigma ^{(r)}$ and distinct $j, j^{\prime}$ where $M_{i,j} = 1$ and $M_{i^{\prime},j^{\prime}} = 1$ . Assume that $\sigma ^{(i)}$ starts in the $b$ th column and let $a$ be the maximal integer such that $M^{\prime}_{a,b}=1$ . Then we have $M^{\prime}_{c,d}=0$ for all $(c,d)\in \mathrm {LB}(a,b)\setminus \{(a,b)\}$ . This implies $\binom {\mathrm {lb}(M^{\prime};(a,b))-1}{M^{\prime}_{a,b}}=\binom {0}{1}_q=0$ and hence $\mathrm {lb}(M^{\prime})=0$ . For example,

\begin{equation*} M^{\prime}=\begin{bmatrix} 0& \quad 1 & \quad 0 & \quad 0\\ 0& \quad 0 & \quad 1 & \quad 0\\ 1& \quad 0 & \quad 0 & \quad 0\\ 0& \quad 0 & \quad 0 & \quad 1 \end{bmatrix} \end{equation*}

yields $\sigma (M^{\prime})=4213$ and $\sigma ^{(3)}=13$ lies in the first and the second columns. We have $\mathrm {lb}(M^{\prime})=0$ since $\binom {\mathrm {lb}(M^{\prime};(1,2))-1}{M^{\prime}_{1,2}}=\binom {0}{1}_q = 0$ .

Let $\sigma$ be a permutation with $\mathrm {Des}(\sigma ) = \{d_1\lt \cdots \lt d_\ell \}$ , and consider $M=M(\sigma )$ . For $j\gt 1$ pick any $i$ such that $M_{i,j}=1$ and let $m$ be the corresponding position in $\sigma (M)=\sigma$ , i.e. $\sigma _m = i$ . Then it is easy to check that $u_m(\sigma )=\mathrm {lb}(M;(i,j))$ . Entries equal to 1 in the first column of $M$ correspond to $\sigma ^{(\ell +1)}=\sigma _{d_{\ell }+1}\cdots \sigma _{n}$ , and for each $d_{\ell }+1\leq m\leq n$ we have $u_m(\sigma )=n+2-m$ . Therefore we have

\begin{equation*} \prod _{m=d_{\ell }+1}^{n}[u_m(\sigma )-1]_q=[n-d_{\ell }]_q\cdots [1]_q = [n-d_\ell ]_q!\,, \end{equation*}

which equals $\binom {M_{1,1}+\dots +M_{n,1}}{M_{1,1},\dots ,M_{n,1}}_q=\binom {n-d_\ell }{1,\dots ,1}_q$ . This shows that $\mathrm {lb}(M(\sigma ))=\prod _{m=1}^{n}[u_m(\sigma )-1]_q$ . Since we have $\mathrm {maj}(\sigma )=\sum _{i\ge 1} (i-1)\alpha _i$ where $\alpha =\mathrm {csum}(M(\sigma ))$ , letting $\beta =(1^n)$ in Theorem 4.6 gives (4.2).

4.4 Proof of Theorem 4.6

In this subsection, we consider only $M\in \mathrm {Mat}^{\geq 0}$ without a zero column or a zero row. We provide a combinatorial interpretation of $\mathrm {lb}(M)$ in terms of modified labeled Dyck paths (Proposition 4.8). To that end, we fix a matrix $M \in \mathrm {Mat}^{\ge 0}_{r\times \ell }$ . We define a vector $m\in \mathbb {Z}_{\ge 0}^{r\ell }$ obtained by reading the entries of $M$ from left to right and top to bottom, i.e. $m_{n(i,j)}= M_{i,j}$ , where $n(i,j):= \ell (i-1)+j$ for $1 \leq j \leq \ell$ . Then we set

\begin{equation*} I(M;(i,j)) := \bigg[1 + \sum _{a=1}^{n(i,j)-1} m_a, \sum _{a=1}^{n(i,j)} m_a\bigg]. \end{equation*}

Now we define $\mathrm {MLD}(M)$ to be the set of all modified labeled Dyck paths $(\pi ,w)$ that satisfy the following conditions:

1. (1) the bounce vector $\overrightarrow {b}(\pi )=(\alpha _1,\alpha _2,\dots )=\mathrm {csum}(M)$ ;

2. (2) the set of entries of $w$ on the bounce corresponding to column $(\ell -j+1)$ is equal to $\bigcup\nolimits _{i=1}^{r} I(M;(i,j))$ ;

3. (3) elements of $I(M;(i,j))$ are decreasing in $w$ .

Example 4.7. Let $M=\left (\left[\begin{smallmatrix} 1 & \quad\!\!\!\! 2\\ 2 & \quad\!\!\!\!1 \end{smallmatrix}\right] \right )$ . Then the associated vector $m = (1,2,2,1)$ and intervals $I(M;(i,j))$ are

\begin{equation*} I(M;(1,1))=\{1\}, \quad I(M;(1,2))=\{2,3\}, \quad I(M;(2,1))=\{4,5\}, \quad I(M;(2,2))=\{6\}. \end{equation*}

By definition, a modified labeled Dyck path $(\pi ,w)\in \mathrm {MLD}(M)$ satisfies the following conditions:

1. (1) the bounce vector $\overrightarrow {b}(\pi )=(3,3)$ ;

2. (2) $I(M;(1,1))\cup I(M;(2,1))=\{1,4,5\}=\{w_4,w_5,w_6\},\quad \text{and}\quad I(M;(1,2))\cup I(M;(2,2))=\{2,3,6\}= \{w_1,w_2,w_3\}$ ;

3. (3) 4 and 5 are placed in decreasing order and 2 and 3 are placed in decreasing order in $w$ .

The modified labeled Dyck path on the left in Figure 1 belongs to $\mathrm {MLD}(M)$ . For the same Dyck path $\pi$ and $w=632541$ , one can check that $(\pi ,w)\in \mathrm {MLD}(M)$ .

For $(\pi ,w)\in \mathrm {MLD}(M)$ , we have $\langle F_{\mathrm {iDes}(w)},e_{\beta }\rangle =1$ if $\beta =\mathrm {rsum}(M)$ . Conversely, given $(\pi ,w)\in \mathrm {MLD}(n)$ such that $\langle F_{\mathrm {iDes}(w)},e_{\beta }\rangle =1$ for some $\beta \models n$ , we define a matrix $M$ as follows. Let $\alpha =\overrightarrow {b}(\pi )$ be the bounce vector. We also let $s_j=\sum _{j\lt b} \alpha _b$ and $t_i=\sum _{b\lt i} \beta _b$ . Then we define the $\ell (\beta ) \times \ell (\alpha )$ matrix $M$ by letting its entries be as follows:

\begin{align*} M_{i,j}=\left |\left \{w_{s_j+1}, \dots , w_{s_{j-1}}\right \}\ \cap \left [t_{i}+1,t_{i+1}\right ]\right |. \\[-12pt] \end{align*}

Note that we have $(\pi ,w)\in \mathrm {MLD}(M)$ and $\mathrm {rsum}(M)=\beta$ . Furthermore, $M$ is the unique matrix with this property. Therefore, together with Theorem 4.3, we obtain

(4.5) \begin{align} \langle D_{n}[X;q,t],e_{\beta }\rangle =1= \sum _{\substack {M\in \mathrm {Mat}^{\ge 0} \\ \mathrm {rsum}(M)=\beta }}\sum _{{(\pi ,w)\in \mathrm {MLD}(M)}}t^{\mathrm {bounce}(\pi )}q^{\mathrm {area}^{\prime}(\pi ,w)}. \end{align}

Proposition 4.8. Let $M\in \mathrm {Mat}^{\ge 0}_{r\times \ell }$ . Then $\mathrm {lb}(M)$ is a generating function for $\mathrm {area}^{\prime}$ over all modified labeled Dyck paths $\mathrm {MLD}(M)$ :

\begin{equation*} \mathrm {lb}(M) = q^{-\sum _{i,j}\binom {M_{i,j}}{2}}\sum _{(\pi ,w)\in \mathrm {MLD}(M)} q^{\mathrm {area}^{\prime}(\pi ,w)}. \end{equation*}

Proof. Let $\ell = 1$ . If $(\pi , w) \in \mathrm {MLD}(M)$ then the bounce vector of $\pi$ is of length 1, so $\pi$ must be the full Dyck path, i.e. $\pi = N \cdots N E \cdots E$ . For a permutation $w \in \mathfrak {S}_{|M|}$ , $(\pi , w) \in \mathrm {MLD}(M)$ if and only if the elements in $I(M; (i, 1))$ are in decreasing order in $w$ for all $i$ . Then there is a natural bijection

\begin{equation*} \phi : \mathrm {MLD}(M) \rightarrow W_{M_{1,1}, M_{2,1}, \dots , M_{r,1}}, \end{equation*}

where $W_{M_{1,1}, M_{2,1}, \dots , M_{r,1}}$ is the set of words of consisting of $M_{i,1}$ instances of $i$ , and $\phi (\pi ,w)$ is defined as the word obtained from the permutation $w$ by replacing entries in the interval $I(M; (i, 1))$ with $i$ . Then, note that

(4.6) \begin{equation} \mathrm {area}^{\prime}(\pi , w) = \mathrm {inv}(w) = \sum _{i=1}^r \binom {M_{i,1}}{2} + \mathrm {inv}(\phi (\pi ,w)). \end{equation}

One can see this by dividing the contributions to $\mathrm {inv}(w)$ into two cases. The first case consists of the pair of entries in the same interval $I(M; (i, 1))$ for some $i$ , contributing $\sum _{i=1}^r \binom {M_{i,1}}{2}$ . The second case consists of the pair of integers in different intervals, $I(M; (i, 1))$ and $I(M; (i^{\prime}, 1))$ , which are out of order. The contribution of the latter case is given by the usual inversions of $\phi (\pi ,w)$ . By (4.6), we have

\begin{equation*} \sum _{(\pi , w) \in \mathrm {MLD}(M)} q^{\mathrm {area}^{\prime}(\pi , w)} = q^{\sum _{i=1}^r \binom {M_{i,1}}{2}} \binom {M_{1,1} + \dots + M_{r,1}}{M_{1,1}, \dots , M_{r,1}}_{\!q} = q^{\sum _{i=1}^r \binom {M_{i,1}}{2}} \mathrm {lb}(M). \end{equation*}

Here, we have used the fact that the inversion generating function of $W_{M_{1,1}, M_{2,1}, \dots , M_{r,1}}$ is the $q$ -multinomial coefficient $\binom {M_{1,1} + \dots + M_{r,1}}{M_{1,1}, \dots , M_{r,1}}_{\!q}$ .

Suppose that $\ell \gt 1$ , and let us proceed by induction on the sum $n=|M|$ . We are dealing with $M$ without a zero column, so the base case $|M|=1$ has been covered. Let $c$ be the smallest index $i$ such that $M_{i,\ell }\neq 0$ , and let $M^{\prime}$ be the matrix obtained from $M$ by replacing $M_{c,\ell }$ with zero. If the rightmost column of $M^{\prime}$ is a zero column, we simply erase that column.

Let $s=\mathrm {lb}(M;(c,\ell ))$ and let $W^{0}_{s,M_{c,\ell }}$ be the set of 0-1 sequences of length $s$ with $M_{c,\ell }$ ones starting with a zero. Suppose we construct a bijection

\begin{align*} \Phi :\mathrm {MLD}(M) &\rightarrow \mathrm {MLD}(M^{\prime})\times W^{0}_{s,M_{c,\ell }}\\ (\pi ,w) &\mapsto (\Phi _1(\pi ,w), \Phi _2(\pi ,w)) \end{align*}

such that

(4.7) \begin{equation} \mathrm {area}^{\prime}(\pi ,w)=\mathrm {area}^{\prime}\left (\Phi _1(\pi ,w)\right ) + \mathrm {inv}\left (\Phi _2(\pi ,w)\right ) + \binom {M_{c,\ell }}{2}. \end{equation}

Then we have

\begin{align*} \sum _{(\pi ,w)\in \mathrm {MLD}(M)} q^{\mathrm {area}^{\prime}(\pi ,w)} & = q^{\binom {M_{c,\ell }}{2}} \sum _{(\pi ,w)\in \mathrm {MLD}(M^{\prime})} q^{\mathrm {area}^{\prime}(\pi ,w)} \sum _{\sigma \in W^{0}_{s,M_{c,\ell }}}q^{\mathrm {inv}(\sigma )}\\ &=q^{\sum _{i,j}\binom {M_{i,j}}{2}}\mathrm {lb}(M^{\prime}) \binom {\mathrm {lb}(M;(c,\ell ))-1}{M_{c,\ell }}_{\!q}\\ &=q^{\sum _{i,j}\binom {M_{i,j}}{2}}\mathrm {lb}(M). \\[-12pt] \nonumber \end{align*}

Here, the first equality follows from (4.7). The second equality follows from the induction hypothesis, and the last equality follows from the definition of $\mathrm {lb}(M)$ . Therefore, it suffices to construct such a bijection $\Phi$ satisfying (4.7).

Given a modified labeled Dyck path $(\pi ,w)\in \mathrm {MLD}(M)$ , recall that each step in $\pi$ has an associated label which we encoded in $L(\pi ,w)$ (see Definition 4.1). Let $\mathrm {csum}(M)=\alpha$ then $\pi$ must pass through specific points $X_0$ and $X_1$ given by

(4.8) \begin{align} X_{0} = \bigg(\sum _{1\le j \le \ell -2}\alpha _j,\sum _{1\le j \le \ell -1}\alpha _j\bigg) \quad \text {and} \quad X_{1} = \bigg(\sum _{1\le j \le \ell -1}\alpha _j,n\bigg). \\[-14pt] \nonumber \end{align}

In other words, the subpath from $X_0$ to $X_1$ corresponds to the last bounce of $\pi$ and we let $P(\pi ,w)$ be a subsequence of $L(\pi ,w)$ for this subpath, denoted by $P(\pi ,w)=(P_1,\dots ,P_{\alpha _{\ell -1}+\alpha _{\ell }})$ . If $P_j=(E,a)$ for some label $a$ then we have $a\in \bigcup _{i=1}^r I(M;(i,\ell -1))$ , and if $P_j=(N,a)$ we have $a\in \bigcup _{i=1}^r I(M;(i,\ell ))$ . Define sets $A$ , $B$ , and $C$ given by

\begin{align*} A&=\bigg\{(E,a): a\in \bigcup _{i=1}^c I(M;(i,\ell -1))\bigg\}\cup \bigg\{(N,a): a\in \bigcup _{i=c+1}^r I(M;(i,\ell ))\bigg\},\\ B&=\{(N,a): a\in I(M;(c,\ell ))\},\\ C&=\bigg\{(E,a): a\in \bigcup _{i=c+1}^r I(M;(i,\ell -1))\bigg\}. \end{align*}

Then each $P_i$ belongs to exactly one of $A$ , $B$ , or $C$ . We define $\Phi _1(\pi ,w)$ to be $(\pi ^{\prime},w^{\prime})$ whose $L(\pi ^{\prime},w^{\prime})$ is obtained from $L(\pi ,w)$ by deleting elements $P'_i$ in $B$ and replacing each label $\gamma \in \bigcup _{c\lt i\le r,1\le j \le \ell }I(M;(i,j))$ by $\gamma -M_{c,\ell }$ to standardize the labels. From $P(\pi ,w)$ we replace elements $P_i$ in $A$ by 0 and $P_i$ in $B$ by 1, and delete elements $P_i$ in $C$ . The resulting 0-1 sequence is defined to be $\Phi _2(\pi ,w)$ .

Given that $(N,a)\in A$ and $(N,b)\in B$ imply $a\gt b$ , it follows that $(\pi ^{\prime},w^{\prime})$ remains a modified labeled Dyck path. Let $j$ be the minimal number such that $P_j$ is in $A$ or $B$ . If $P_j \in B$ then $j\gt 1$ , since $P_1$ must be of the form $(E,a)$ . Thus, $P_{j-1}\in C$ , which would violate the condition for a modified labeled Dyck path. Therefore $P_j\in A$ , implying that $\Phi _2(\pi ,w)$ starts with 0. This confirms that $\Phi$ is well defined.

Now we describe an inverse map from $(\pi ^{\prime},w^{\prime})\in \mathrm {MLD}(M^{\prime})$ and $v\in W^{0}_{s,M_{c,\ell }}$ . As before, let $P(\pi ,w^{\prime})=(P^{\prime}_1,\dots )$ be a subsequence of $L(\pi ^{\prime},w^{\prime})$ corresponding to the last bounce. The following observation is crucial.

• – Given a sequence $\bar {v}$ of $0$ , $1$ , and $2$ where there are no consecutive terms 2 and 1 (in this order), we can uniquely determine $\bar {v}$ if we know the sequences $v$ (obtained from $\bar {v}$ by deleting terms that are 2’s) and $v^{\prime}$ (obtained from $\bar {v}$ by deleting terms that are 1’s).

Using this observation, proceed as follows.

1. (1) Generate a 0-2 sequence: from $P(\pi ^{\prime}, w^{\prime})$ , create a 0-2 sequence $v^{\prime}$ by replacing any $P^{\prime}_i$ in

   \begin{equation*} C^{\prime} = \bigg\{(E, a) : a \in \bigcup _{i=c+1}^r I(M^{\prime}; (i, \ell -1))\bigg\} \end{equation*}
   with 2 and replacing any $P^{\prime}_i$ not in $C^{\prime}$ with 0.

2. (2) Construct $\bar {v}$ : using the above observation, combine $v$ and $v^{\prime}$ to reconstruct $\bar {v}$ , which consists of 0, 1, and 2.

3. (3) Insert elements: insert elements of $B$ into the sequence $P(\pi ^{\prime}, w^{\prime})$ according to the positions of ones in $\bar {v}$ .

4. (4) Standardize labels: Shift the labels in $L(\pi ^{\prime}, w^{\prime})$ properly to standardize them, yielding $L(\pi , w)$ for some $(\pi , w) \in \mathrm {MLD}(M)$ .

Thus, we have demonstrated that $\Phi$ is a bijection. Equation (4.7) follows straightforwardly from the construction.

Example 4.9. Let $(\pi ,w)$ be the modified labeled Dyck path on the left in Figure 1 in $\mathrm {MLD}\left (\left[\begin{smallmatrix} 1 & \quad\!\!\!\! 2\\ 2 & \quad\!\!\!\! 1\\ \end{smallmatrix}\right]\right ).$ Or, equivalently, we could describe $(\pi ,w)$ as a modified labeled Dyck path such that

\begin{equation*} L(\pi ,w)=((N,4),(N,1),(N,5),(E,4),(N,6),(N,2),(E,1),(N,3),(E,5),(E,6),(E,2),(E,3)), \end{equation*}

where its $i$ th component presents the $i$ th labeled step.

Let $\Phi$ be the bijection $\Phi :\mathrm {MLD}\left (\left[\begin{smallmatrix} 1 & \quad\!\!\!\! 2 \\ 2 & \quad\!\!\!\! 1 \end{smallmatrix}\right]\right ) \rightarrow \mathrm {MLD}\left (\left[\begin{smallmatrix} 1 & \quad\!\!\!\! 0 \\ 2 & \quad\!\!\!\! 1 \end{smallmatrix}\right]\right )\times W^{0}_{4,2}$ defined in the proof of Proposition 4.8. First, deleting steps labeled with numbers in the interval $I(M;(1,2))=\{2,3\}$ gives

\begin{equation*} ((N,4),(N,1),(N,5),(E,4),(N,6),(E,1),(E,5),(E,6)) \end{equation*}

or, equivalently, the following diagram.

Then, by replacing each label $\gamma \in I(M;(2,1))\cup I(M;(2,2)) = \{4,5,6\}$ by $\gamma -M_{c,\ell }=\gamma -2$ , we have the following modified labeled Dyck path $\Phi _1(\pi ,w)$ which is in $\mathrm {MLD}\left (\left[\begin{smallmatrix} 1 & \quad\!\!\!\! 0\\2 & \quad\!\!\!\! 1\\ \end{smallmatrix} \right]\right )$ .

Let $\alpha =\mathrm {csum}(M)=(3,3)$ . The labeled subpath of $L(\pi ,w)$ starting from

\begin{equation*} \bigg (\sum _{1\le j \le \ell -2}\alpha _j,\sum _{1\le j \le \ell -1}\alpha _j\bigg )=(0,3) \end{equation*}

and ending at

\begin{equation*} \bigg (\sum _{1\le j \le \ell -1}\alpha _j,n\bigg )=(3,6) \end{equation*}

is $P(\pi ,w)=((E,4),(N,6),(N,2),(E,1),(N,3),(E,5))$ . We get $\sigma (\pi ,w)=462135$ by reading its labels. The 0–1 word obtained from $\sigma (\pi ,w)$ by replacing numbers in

\begin{equation*} \bigcup _{(a,b)\in \mathrm {lb}(1,2)\setminus \{(1,2)\}} I(M;(a,b))=I(M;(1,1))\cup I(M;(2,2))=\{1,6\} \end{equation*}

with zeros, numbers in $I(M;(c,\ell ))=\{2,3\}$ with ones, and deleting the other numbers is $\Phi _2\left (\pi ,w\right )=0101$ . We can also check that

\begin{equation*} \mathrm {area}^{\prime}(\pi ,w) = 6 = 4 + 1 + 1 = \mathrm {area}^{\prime}(\Phi _1(\pi ,w)) + \mathrm {inv}(\Phi _2(\pi ,w)) + \binom {M_{1,2}}{2}. \end{equation*}

Proof of Theorem 4.6. Partitioning the sum on the right-hand side of (4.5) by the bounce vector, we have

\begin{align*} \langle D_n[X;q,t],e_{\beta }\rangle &=\sum _{\alpha \models n} t^{\sum _{i=1}^{\ell (\alpha )}(i-1)\alpha _i} \sum _{\substack {M \in \mathrm {Mat}^{\ge 0} \\ \mathrm {csum}(M)=\alpha \\ \mathrm {rsum}(M)=\beta }} \sum _{(\pi ,w)\in \mathrm {MLD}(M)} q^{\mathrm {area}^{\prime}(\pi ,w)}\\&=\sum _{\alpha \models n} t^{\sum _{i=1}^{\ell (\alpha )}(i-1)\alpha _i} \sum _{\substack {M \in \mathrm {Mat}^{\ge 0} \\ \mathrm {csum}(M)=\alpha \\ \mathrm {rsum}(M)=\beta }} q^{\sum _{i,j}\binom {M_{i,j}}{2}} \mathrm {lb}(M), \end{align*}

where the last equality follows from Proposition 4.8.

5.1 A generalization of modified Macdonald polynomials

In [Reference Kim, Lee and OhKLO22], the authors introduce a generalized version of the modified Macdonald polynomials. A diagram $D$ consists of a collection of cells, with a specific cell at the bottom of each column referred to as a bottom cell. For a diagram $D$ , the size $|D|$ of $D$ is the total number of cells it contains. In this paper, we only consider diagrams that are connected and finite. As in the partition case, we index rows of $D$ from the bottom and columns of $D$ from the left. Denote the cell of $D$ in the $i$ th row and $j$ th column by $(i,j)$ . We represent a diagram $D$ by

\begin{equation*} D = [D^{(1)},D^{(2)},\dots ], \end{equation*}

where $D^{(j)}$ denotes the set of $i$ such that $(i,j)$ is a cell of $D$ . Throughout the paper, we assume that each column $D^{(j)}$ of a diagram $D$ forms an interval.

Figure 3.

An example of a filled diagram.

Let $\mathbb {F}$ be a field that includes $\mathbb {C}(q,t)$ , the field of rational functions in $q$ and $t$ . A filled diagram $(D,f)$ consists of a diagram $D$ and a filling function

\begin{equation*} f:D\setminus \{\text {bottom cells of }D\}\rightarrow \mathbb {F} \end{equation*}

which assigns a scalar from $\mathbb {F}$ to each cell of $D$ excluding the bottom cells. We represent a filled diagram $(D,f)$ by displaying the corresponding values of $f$ for each cell in the diagram; see Figure 3 for an example. For a subdiagram $E$ of $D$ , we consider a sub-filled diagram $(E,f\vert _{E})$ of $(D,f)$ where the filling $f\vert _{E}$ is inherited from $f$ .

To establish a total order $N_D:D\rightarrow [|D|]$ on cells in $D$ , we order them from left to right in each row and proceed row by row from top to bottom. We define two functions, $\mathrm {inv}_D:\mathfrak {S}\rightarrow \mathbb {F}$ and $\mathrm {maj}_{(D,f)}\rightarrow \mathbb {F}$ , in the spirit of the functions $\mathrm {inv}_\mu$ and $\mathrm {maj}_\mu$ defined in [Reference Haglund, Haiman and LoehrHHL05]. For cells $u=(i,j)$ and $v=(i^{\prime},j^{\prime})$ of $D$ , we say that a pair $(u,v)$ is an attacking pair if either

\begin{equation*} (1)\ i=i^{\prime} \text { and } j\lt j^{\prime} \quad \text { or }\quad \text { (2) }i=i^{\prime}+1 \text { and } j\gt j^{\prime}. \end{equation*}

For a permutation $w\in \mathfrak {S}_{|D|}$ we consider a pair $(u,v)$ of cells in $D$ to be an inversion pair of $w$ if $(u,v)$ is an attacking pair and $w_{N_D(u)}\gt w_{N_D(v)}$ . We denote the set of inversion pairs of $w$ by $\mathrm {Inv}_D(w)$ and define $\mathrm {inv}_D(w)$ to be

\begin{equation*} \mathrm {inv}_D(w) := q^{|\mathrm {Inv}_D(w)|}. \end{equation*}

We say that a cell $(i,j)$ in $D$ is a descent of $w$ if $w_{N_D(i,j)}\gt w_{N_D(i-1,j)}$ . We denote the set of descents of $w$ by $\mathrm {Des}_D(w)$ and define $\mathrm {maj}_{(D,f)}(w)$ as the product of $f(u)$ over all cells $u$ which are descents of $w$ , i.e.

\begin{equation*} \mathrm {maj}_{(D,f)}(w) := \prod _{u\in \mathrm {Des}_D(w)} f(u). \end{equation*}

Finally, we define $\mathrm {stat}_{(D,f)}(w)$ by

\begin{equation*} \mathrm {stat}_{(D,f)}(w) := \mathrm {inv}_D(w)\mathrm {maj}_{(D,f)}(w). \end{equation*}

Now, we define the modified Macdonald polynomial of a filled diagram $(D,f)$ .

Definition 5.1. Let $(D,f)$ be a filled diagram of size $n$ . The (generalized) modified Macdonald polynomial of $(D,f)$ is defined by

\begin{equation*} \widetilde {H}_{(D,f)}[X]:=\sum _{w\in \mathfrak {S}_{|D|}} \mathrm {stat}_{(D,f)}(w)F_{\mathrm {iDes}(w)}. \end{equation*}

If we define the standard filling $f^{\mathrm {st}}_\mu$ of a partition $\mu$ by assigning $f^{\mathrm {st}}_\mu (u)=q^{-\mathrm {arm}_\mu (u)}t^{\mathrm {leg}_\mu (u)+1}$ to each cell $u$ in $\mu$ , then the modified Macdonald polynomial of the filled diagram $(\mu ,f^{\mathrm {st}}_\mu )$ is the usual modified Macdonald polynomial $\widetilde {H}_\mu$ by the celebrated Haglund–Haiman–Loehr formula [Reference Haglund, Haiman and LoehrHHL05]:

\begin{equation*} \widetilde {H}_{(\mu ,f^{\mathrm {st}}_\mu )}[X] = \widetilde {H}_\mu [X;q,t]. \end{equation*}

5.2 Column exchange rule and cycling

There can be two distinct filled diagrams $(D,f)$ and $(D^{\prime},f^{\prime})$ with the same modified Macdonald polynomials. In this subsection, we review such examples studied in [Reference Kim, Lee and OhKLO22]. The first one is the column exchange rule. We first recall some terminology.

Definition 5.2. For positive integers $n\gt m$ , we define $\mathcal {V}(n,m)$ to be the set of all filled diagrams $(\mu ,f_{\mu })$ such that $\mu =[[n],[m]]$ and a filling $f_\mu$ on it satisfies the following condition:

(5.1) \begin{equation} f_\mu (i,1) = q^{-1}f_\mu (m+1,1) f_\mu (i,2) \quad \text {for }1 < i\leq m. \end{equation}

For $(\mu ,f_{\mu })\in \mathcal {V}(n,m)$ , we let $S(\mu ,f_{\mu })$ be the filled diagram $(\lambda ,f_{\lambda })$ such that $\lambda =[[m],[n]]$ and

\begin{align*} \begin{cases} f_\lambda (i,2)=f_\mu (i,1)& \text {for }i\gt m+1,\\ f_\lambda (m+1,2)=q^{-1}f_\mu (m+1,1),\\f_\lambda (m+1,2) f_\lambda (i,1) = f_\lambda (i,2)=f_\mu (i,1)& \text {for }1\lt i\leq m. \end{cases}\end{align*}

See Figure 4 for an example.

Let $(D,f)$ be a filled diagram such that the restriction to the $j$ th and $(j+1)$ th columns is in $\mathcal {V}(n,m)$ for some $n\gt m$ . We define $S_j(D,f)$ to be the filled diagram obtained from $(D,f)$ by applying the map $S$ to the two columns ( $j$ th and $(j+1)$ th columns). Clearly, the map $S_j$ is injective, so we may consider $S_j^{-1}(D,f)$ if it exists. Given two filled diagrams $(D,f)$ and $(D^{\prime},f^{\prime})$ , we write $(D,f)\cong (D^{\prime},f^{\prime})$ if they are related by a sequence of operators of the form $S_j$ or $S_j^{-1}$ .

Figure 4.

The filled diagram $(\mu ,f_{\mu })\in \mathcal {V}(n,m)$ is of the form on the left for some $a_i$ , $b_i$ , and $\alpha$ in $\mathbb {F}$ . The right figure shows the corresponding $S(\mu ,f_{\mu })$ .

With the assumptions in Proposition 5.3, conditions $(\phi 1)$ and $(\phi 2)$ are enough to imply $\widetilde {H}_{(D,f)}[X]=\widetilde {H}_{(D^{\prime},f^{\prime})}[X]$ . However, we need a more refined identity (5.3) coming from the condition $(\phi 3)$ that will be used in the proof of Lemma 6.12 and Lemma 6.18. We define some terminology to state (5.3).

Definition 5.4. For diagram $D$ and a composition $\alpha =(\alpha _1,\dots ,\alpha _{r})$ of size less than or equal to $|D|$ , we define $\mathrm {OP}(D;\alpha )$ to be the set of tuples $(A_1,\dots ,A_{r})$ of disjoint subsets $A_i\subseteq D$ such that $|A_i|=\alpha _i$ . For a tuple $(A_1, \dots , A_{r})\in \mathrm {OP}(D;\alpha )$ , let $B_i=\{N_D(u): u\in A_i\}$ where $N_D$ is the total order on cells of $D$ defined in § 5.1. We define $\sigma (D;(A_1, \dots , A_{r}))$ to be the permutation obtained by first listing elements $[|D|]\setminus \bigcup\nolimits _{i=1}^{r}B_i$ in decreasing order, followed by elements in $B_1$ in decreasing order, then elements in $B_2$ in decreasing order, and so on.

For instance, let $D = [\{1,2,3,4,5\},\{1,2,3,4\},\{2,3\}]$ be a diagram and

\begin{equation*} (A_1,A_2,A_3)=(\{(2,2),(3,1),(3,3) \},\{(2,1),(3,2)\}, \{ (2,3),(4,2),(5,1)\})\in \mathrm {OP}(D;(3,2,3)). \end{equation*}

Pictorially, $(A_1,A_2,A_3)$ is displayed by labeling cells in $A_i$ by $i$ as on the leftin Figure 5. According to the total order $N_D$ (given on the right in Figure 5), the permutation associated to $(A_1,A_2,A_3)$ is

\begin{equation*} \sigma (D;(A_1,A_2,A_3))=(11,10,2,\underbrace {8,6,4}_{3},\underbrace {7,5}_{2},\underbrace {9,3,1}_{3}). \end{equation*}

Figure 5.

An element of $\mathrm {OP}(D,(3,2,3))$ and a natural ordering $N_{D}$ of $D$ .

By (4.3), letting $m=|D|-\sum _{i=1}^{r}\alpha _i$ , we have

(5.2) \begin{equation} \langle \widetilde {H}_{(D,f)}[X]),e_{(m,\alpha )}\rangle =\sum _{L\in \mathrm {OP}(D;\alpha )}\mathrm {stat}_{(D,f)}(\sigma (D;L)^{-1}). \end{equation}

Now we further refine the set $\mathrm {OP}(D;\alpha )$ .

Definition 5.5. Let $D$ be a diagram with $\ell$ rows. For $L=(A_1,\dots ,A_r)\in \mathrm {OP}(D;\alpha )$ , we define an $r\times \ell$ matrix $\mathrm {type}(D;L)$ by letting its entries be as follows:

\begin{align*} \mathrm {type}(D;L)_{i,j}=\text {the number of cells in the }j\text {th row of }D\text { that are in }A_i. \end{align*}

Now we define $\mathbf {OP}(D;M)$ to be the set of tuples $L$ such that $\mathrm {type}(D;L)=M$ . Note that $\mathrm {rsum}(\mathrm {type}(D;L))=\alpha$ if $L\in \mathrm {OP}(D;\alpha )$ . With this notion, we partition $\mathrm {OP}(D;\alpha )$ into the union

\begin{equation*} \mathrm {OP}(D;\alpha )=\bigcup _{\mathrm {rsum}(M)=\alpha }\mathbf {OP}(D;M). \end{equation*}

Given $(D,f)\cong (D^{\prime},f^{\prime})$ , let $\phi$ be the map in Proposition 5.3. By the conditions $(\phi 1)$ and $(\phi 2)$ , $\phi$ gives a stat-preserving bijection between

\begin{equation*} \{\sigma (D;L)^{-1}:L\in \mathrm {OP}(D;\alpha )\} \quad \text {and} \quad \{\sigma (D^{\prime};L)^{-1}:L\in \mathrm {OP}(D^{\prime};\alpha )\}. \end{equation*}

Moreover, the condition $(\phi 3)$ implies that if $\phi (\sigma (D;L)^{-1})=\sigma (D^{\prime};L^{\prime})^{-1}$ , we have $\mathrm {type}(D;L)=\mathrm {type}(D^{\prime};L^{\prime})$ . In other words, $\phi$ gives a bijection between

\begin{equation*} \{\sigma (D;L)^{-1}:L\in \mathbf {OP}(D;M)\} \quad \text {and}\quad \{\sigma (D^{\prime};L)^{-1}:L\in \mathbf {OP}(D^{\prime};M)\}. \end{equation*}

We conclude that for any $M\in \mathrm {Mat}^{\geq 0}$ ,

(5.3) \begin{equation} \sum _{L\in \mathbf {OP}(D;M)}\mathrm {stat}_{(D,f)}(\sigma (D;L)^{-1})=\sum _{L\in \mathbf {OP}(D^{\prime};M)}\mathrm {stat}_{(D^{\prime},f^{\prime})}(\sigma (D^{\prime};L)^{-1}). \end{equation}

We end this section by recalling the cycling rule. Given a diagram $D=[D^{(1)},\dots ,D^{(\ell )}]$ , consider a diagram

\begin{equation*} D^{\prime}=[D^{(2)},\dots ,D^{(\ell )},D^{(1)}+1], \end{equation*}

where $I+1=\{a+1:a\in I\}$ for an interval $I$ . In other words, $D^{\prime}$ is a diagram obtained by moving the leftmost column of $D$ to the right end and placing it one cell up. Cells in $D$ and $D^{\prime}$ are naturally in bijection. To a filling $f$ of $D$ we can associate a filling $f^{\prime}$ of $D^{\prime}$ inherited from $f$ via this natural bijection. Then we define $\mathrm {Cyc} (D,f):=(D^{\prime},f^{\prime})$ . Then the following lemma is well known and its proof is straightforward (see [Reference Kim, Lee and OhKLO22, Lemma 3.6], for example).

Lemma 5.6 [Cycling rule]. Let $(D,f)$ be a filled diagram and $(D^{\prime},f^{\prime})=\mathrm {Cyc}(D,f)$ . Then we have

\begin{align*} \widetilde {H}_{(D,f)}[X] = \widetilde {H}_{(D^{\prime},f^{\prime})}[X]. \\[-16pt] \end{align*}

6.1 Deforming the filled diagram $(\mu ^{(i)},f^{\mathrm {st}}_{\mu ^{(i)}})$

In this subsection, we introduce a filled diagram $(\overline {\delta }_{k,i},\overline {f}_{k,i})$ that possesses the property

\begin{equation*} \widetilde {H}_{\left(\mu ^{(i)},f^{\mathrm {st}}_{\mu ^{(i)}}\right)}[X]=\widetilde {H}_{\left(\overline {\delta }_{k,i},\overline {f}_{k,i}\right)}[X]. \end{equation*}

For the computation of $\mathrm {I}_{\mu ^{(1)},\dots ,\mu ^{(k)}}$ , we will utilize $(\overline {\delta }_{k,i},\overline {f}_{k,i})$ in place of $(\mu ^{(i)},f^{\mathrm {st}}_{\mu ^{(i)}})$ .

Definition 6.1. We define

\begin{equation*} \left(\overline {\delta }_{k,i},\overline {f}_{k,i}\right):=\mathrm {Cyc} (S_1\dots S_{i-1}(\mu ^{(i)},f^{\mathrm {st}}_{\mu ^{(i)}}) ). \end{equation*}

Refer to Figure 6 for an illustrative example. In other words, we perform the following procedure: we shift the $i$ th column of $(\mu ^{(i)},f^{\mathrm {st}}_{\mu ^{(i)}})$ all the way to the left by applying $S_1\cdots S_{i-1}$ , and then we take the first column (previously the $i$ th column) and move it to the far right using the operator $\mathrm {Cyc}$ . It can be verified that the local condition (5.1) is always satisfied during the application of the operators $S_1\cdots S_{i-1}$ . For a detailed proof, we refer to [Reference Kim, Lee and OhKLO22, Lemma 5.2].

Lemma 6.2. We have $\overline {\delta }_{k,i}=[I_1,I_2,\dots ,I_k]$ , where $I_j$ is the interval given by

\begin{equation*} I_j = \begin{cases} [2k-j] &\text {if } j\lt i, \\ [2k-j-1] &\text {if } i\le j\lt k, \\ [2,2k-i] &\text {if } j=k. \end{cases} \end{equation*}

The filling $\overline {f}_{k,i}$ on $\overline {\delta }_{k,i}$ is given by

\begin{align*} \overline {f}_{k,i}(a,b) = \begin{cases} q^{b-k}t^{2k-a-b+1}&\text {if } a\le k \ \mathrm{ and }\ b\lt i,\\ q^{b-k+1}t^{2k-a-b}&\text {if } a\le k\ \mathrm{ and }\ i\le b\lt k,\\ q^{i-k} t^{2k-i-a+1}&\text {if } a\le k\ \mathrm{ and }\ b=k,\\ q^{a+b-2k}t^{2k-a-b+1}&\text {if } a\gt k\ \mathrm{ and }\ b\lt i,\\ q^{a+b-2k+1}t^{2k-a-b}&\text {if } a\gt k\ \mathrm{ and }\ i\le b \lt k,\\ q^{i+a-2k-1}t^{2k-i-a+1}&\text {if } a\gt k\ \mathrm{ and }\ b=k. \end{cases} \\[-12pt] \end{align*}

Figure 6.

The figure on the left depicts the filled diagram $(\mu ^{(3)},f^{\mathrm {st}}_{\mu ^{(3)}})$ , while the one in the center represents the filled diagram $S_1 S_2(\mu ^{(3)},f^{\mathrm {st}}_{\mu ^{(3)}})$ . Finally, the figure on the right illustrates the filled diagram $(\overline {\delta }_{4,3}, \overline {f}_{4,3})$ , which is obtained by applying the operator $\mathrm {Cyc}$ to the figure in the center.

Proof. The standard filling of $\mu ^{(i)}$ is given by

\begin{align*} f^{\mathrm {st}}_{\mu ^{(i)}}(a,b)= \begin{cases} q^{b-k}t^{2k-a-b+1}&\text {if } a\le k\mbox{ and } b\neq i,\\ q^{i-k}t^{2k-a-i}&\text {if } a\le k\mbox{ and } b= i,\\ q^{a+b-2k}t^{2k-a-b+1}&\text {if } k\lt a\lt 2k-i\mbox{ and } b\neq i\text { or }a\gt 2k-i,\\ q^{a+i-2k}t^{2k-a-i}&\text {if } a\gt k\mbox{ and } b=i,\\ q^{b-i+1}t^{i-b+1}&\text {if } a=2k-i. \end{cases} \\[-12pt] \end{align*}

While applying the operator $S_1\dots S_{i-1}$ , the only changes of the filling occur in the $(2k-i)$ th row upon multiplying by $q^{-1}$ . Writing $(D,f)=S_1\dots S_{i-1}(\mu ^{(i)},f^{\mathrm {st}}_{\mu ^{(i)}})$ , we have

\begin{equation*} D = [[2k-i-1],[2k-1],\dots ,[2k-i+1],[2k-i-1],\dots ,[k]] \end{equation*}

and

\begin{align*} f(a,b)= \begin{cases} q^{i-k} t^{2k-a-i}&\text {if } a\le k\mbox{ and } b=1,\\ q^{b-k-1}t^{2k-a-b+2}&\text {if } a\le k\mbox{ and } 1\lt b\le i,\\ q^{b-k}t^{2k-a-b+1}&\text {if } a\le k\mbox{ and } b\gt i,\\ q^{a+i-2k}t^{2k-a-i}&\text {if } a\gt k\mbox{ and } b=1,\\ q^{a+b-2k-1}t^{2k-a-b+2}&\text {if } a\gt k\mbox{ and } 1\lt b\le i,\\ q^{a+b-2k}t^{2k-a-b+1}&\text {if } a\gt k\mbox{ and } b\gt i. \end{cases} \\[-12pt] \end{align*}

Applying the operator $\mathrm {Cyc}$ completes the proof.

Remark 6.3. Let $\lambda$ be a partition and $(D,f)$ a filled diagram satisfying $(D,f)\cong (\lambda ,f_{\lambda }^{\mathrm {st}})$ . Then [Reference Haglund, Haiman and LoehrHHL08, Theorem 5.1.1] implies $\widetilde {H}_{(D,f)}[X]=\widetilde {H}_{(\lambda ,f^{\mathrm {st}}_{\lambda })}[X]$ . In particular, letting $(D,f)=S_{1}\dots S_{i-1}(\mu ^{(i)},f^{\mathrm {st}}_{\mu ^{(i)}})$ , we obtain

\begin{equation*} \widetilde {H}_{(D,f)}[X]=\widetilde {H}_{\left(\mu ^{(i)},f^{\mathrm {st}}_{\mu ^{(i)}}\right)}[X] \end{equation*}

without using Proposition 5.3. However, [Reference Haglund, Haiman and LoehrHHL08, Theorem 5.1.1] is not enough for our purposes later when we deal with $z$ -deformed filled diagrams in § 6.3. Moreover, we need a more refined identity (5.3).

6.2 Lightning bolt formula for Macdonald intersection polynomials

In this subsection, we state the lightning bolt formula for Macdonald intersection polynomials (Proposition 6.4), which essentially proves Theorem 1.1(c).

By (5.2), for a composition $\beta \models k-1$ we have

(6.1) \begin{align} \langle e^{\perp }_{n+1-k}\mathrm {I}_{\mu ^{(1)},\dots ,\mu ^{(k)}}[X;q,t],e_{\beta }\rangle &=\sum _{i=1}^{k} \bigg (\prod _{j\neq i}\dfrac {T_{\mu ^{(j)}}}{T_{\mu ^{(j)}}-T_{\mu ^{(i)}}}\bigg )\sum _{L\in \mathrm {OP}(\overline {\delta }_{k,i};\beta )}\mathrm {stat}_{(\overline {\delta }_{k,i},\overline {f}_{k,i})} (\sigma (\overline {\delta }_{k,i};L)^{-1} )\nonumber \\ &=\sum _{\substack {M\in \mathrm {Mat}^{\ge 0}_{r\times (2k-1)} \nonumber \\\mathrm {rsum}(M)=\beta }}\sum _{i=1}^{k} \bigg (\prod _{j\neq i}\dfrac {T_{\mu ^{(j)}}}{T_{\mu ^{(j)}}-T_{\mu ^{(i)}}}\bigg )\sum _{L\in \mathbf {OP}(\overline {\delta }_{k,i};M)}\nonumber \\[5pt]&\mathrm {stat}_{(\overline {\delta }_{k,i},\overline {f}_{k,i})} (\sigma (\overline {\delta }_{k,i};L)^{-1} ).\end{align}

Now we present the remarkable observation which we refer to as the lightning bolt formula for Macdonald intersection polynomials. This formula establishes a connection between the Macdonald intersection polynomial and the fermionic formula for the shuffle formula (Theorem 4.6). The next subsections are devoted to a proof of Proposition 6.4.

Proposition 6.4. For $M\in \mathrm {Mat}^{\ge 0}_{r\times (2k-1)}$ such that $|M|=k-1$ , writing $\alpha =\mathrm {csum}(M)$ , we have

\begin{align*} & \sum _{i=1}^{k} \bigg (\prod _{j\neq i}\dfrac {T_{\mu ^{(j)}}}{T_{\mu ^{(j)}}-T_{\mu ^{(i)}}}\bigg )\sum _{L\in \mathbf {OP}(\overline {\delta }_{k,i};M)}\mathrm {stat}_{(\overline {\delta }_{k,i},\overline {f}_{k,i})} (\sigma (\overline {\delta }_{k,i};L)^{-1} )\\[6pt]&\qquad =T_{\bigcap _{i=1}^k \mu ^{(i)}}(t^{\sum _{i=1}^{\ell (\alpha )}(i-1)\alpha _i}q^{\sum _{i,j} \binom {M_{i,j}}{2}} ) \mathrm {lb}(M). \end{align*}

We end this subsection with a proof of Theorem 1.1(c) assuming Proposition 6.4.

Proof of Theorem 1.1(c). For any $\beta \models k-1$ , by Proposition 6.4 and (6.1) we have

\begin{equation*} \bigg\langle \dfrac {1}{T_{\bigcap _{i=1}^k \mu ^{(i)}}}e_{n+1-k}^\perp \left (\mathrm {I}_{\mu ^{(1)},\dots ,\mu ^{(k)}}[X;q,t]\right ),\:e_{\beta }\bigg\rangle =\sum _{\alpha }\sum _{\substack {M\in \mathrm {Mat}^{\ge 0}_{\ell (\beta )\times (2k-1)}\\ \mathrm {csum}(M)=\alpha \\ \mathrm {rsum}(M)=\beta }}(t^{\sum _{i=1}^{\ell (\alpha )}(i-1)\alpha _i}q^{\sum _{i,j} \binom {M_{i,j}}{2}} ) \mathrm {lb}(M), \end{equation*}

where the sum on the right-hand side is over vectors $\alpha$ of length $2k-1$ whose entries are nonnegative integers. By applying Lemma 4.5, we can deduce that if $\mathrm {csum}(M)$ is not in the form of $(\alpha ^{\prime},0,\dots ,0)$ for a composition $\alpha ^{\prime}\models k-1$ , then $\mathrm {lb}(M)=0$ . Consequently, our focus narrows down to matrices where $\mathrm {csum}(M)$ takes the form $(\alpha ^{\prime},0,\dots ,0)$ for some $\alpha ^{\prime}\models k-1$ . Using Theorem 4.6, we can finally conclude that

\begin{equation*} \bigg\langle \dfrac {1}{T_{\bigcap _{i=1}^k \mu ^{(i)}}}e_{n+1-k}^\perp \left (\mathrm {I}_{\mu ^{(1)},\dots ,\mu ^{(k)}}[X;q,t]\right )\!, \:e_{\beta }\bigg\rangle =\langle D_{k-1}[X;q,t],\,e_{\beta }\rangle \end{equation*}

for any $\beta \models k-1$ , which is enough to deduce that

\begin{equation*} \dfrac {1}{T_{\bigcap _{i=1}^k \mu ^{(i)}}}e_{n+1-k}^\perp \left (\mathrm {I}_{\mu ^{(1)},\dots ,\mu ^{(k)}}[X;q,t]\right )=D_{k-1}[X;q,t]. \end{equation*}

Our current objective is to prove Proposition 6.4. In § 6.3, we will demonstrate that it is sufficient to establish Proposition 6.17, the proof of which will be provided in § 6.4.

6.3 Reducing to the rectangular case

We first introduce a $z$ -deformation $(\overline {\delta }_{k,i},\overline {f}^{\mathbf {z}}_{k,i})$ of the filled diagram $(\overline {\delta }_{k,i},\overline {f}_{k,i})$ , where the filling $\overline {f}_{k,i}^{\textbf {z}}$ on $\overline {\delta }_{k,i}$ is defined as follows:

(6.2) \begin{equation} \overline {f}_{k,i}^{\textbf {z}}(a,b) = \begin{cases} q z_{2k+1-a}/z_b &\text {if } b\lt i, \\[3pt] q z_{2k+1-a}/z_{b+1} &\text {if } i\le b\lt k,\\[3pt] q z_{2k+1-a}/z_i &\text {if } a\le k\mbox{ and } b=k,\\[3pt] z_{2k+1-a}/z_i &\text {if } a\gt k\mbox{ and } b=k. \end{cases} \end{equation}

Figure 7 shows $(\overline {\delta }_{4,3},\overline {f}_{4,3}^{\textbf {z}})$ , which is a $z$ -deformation of $(\overline {\delta }_{4,3},\overline {f}_{4,3})$ shown on the right of Figure 6.

Figure 7.

A $z$ -deformed filled diagram $(\overline {\delta }_{4,3},\overline {f}_{4,3}^{\textbf {z}})$ .

By Lemma 6.2, one can directly see that substituting

(6.3) \begin{equation} z_j = \begin{cases} q^{1-j}t^{j-1}&\text {if } j\le k,\\[3pt] q^{-k}t^{j-1}&\text {if } j \gt k \end{cases} \end{equation}

recovers $(\overline {\delta }_{k,i}\overline {f}_{k,i})$ . We now introduce a $z$ -deformed version of Proposition 6.4.

Proposition 6.5. For $M\in \mathrm {Mat}^{\ge 0}_{r\times (2k-1)}$ such that $|M|=k-1$ , letting $\alpha =\mathrm {csum}(M)$ , we have

\begin{align*} & \sum _{i=1}^{k} \bigg (\prod _{j\neq i}\dfrac {z_j}{z_j-z_i}\bigg )\sum _{L\in \mathbf {OP}(\overline {\delta }_{k,i};M)}\mathrm {stat}_{(\overline {\delta }_{k,i},\overline {f}^{\mathbf {z}}_{k,i})} (\sigma (\overline {\delta }_{k,i};L)^{-1} )\\[5pt]&\quad =q^{({4k^3-6k^2-k})/{3}+\sum _{i,j}\binom {M_{i,j}}{2}}\bigg(\frac {z_k\prod _{i=1}^{k-1}z_{2k-i}^{k-\alpha _i}}{z_{2k-1}\prod _{i=1}^{k-1}z_i^{2k-2i-1} }\bigg) \mathrm {lb}(M). \end{align*}

On the right-hand side, we may consider only $\alpha$ such that $\alpha _\ell =0$ for $\ell \geq k$ (otherwise $\mathrm {lb}(M)=0$ ), and a simple computation shows that

\begin{align*} \frac {T_{\mu ^{(i)}}}{T_{\mu ^{(j)}}}=\frac {z_i}{z_j},\quad q^{({4k^3-6k^2-k})/{3}}\bigg(\frac {z_k\prod _{i=1}^{k-1}z_{2k-i}^{k-\alpha _i}}{z_{2k-1}\prod _{i=1}^{k-1}z_i^{2k-2i-1} }\bigg)=T_{\bigcap _{i=1}^k \mu ^{(i)}}(t^{\sum _{i=1}^{k-1}(i-1)\alpha _i}) \end{align*}

under the specialization (6.3). Therefore Proposition 6.4 follows from Proposition 6.5. We will reduce Proposition 6.5 to Proposition 6.17, which analyzes the rectangular case. Here is the outline of the strategy.

1. (1) We first establish the equivalence between Proposition 6.5 and (6.6) by introducing a complementary statistic $\overline {\mathrm {stat}}$ (Definition 6.6).

2. (2) We restrict our attention to the almost rectangular shape $\overline {R}_{k}$ in the first $k$ rows (shown on the left in Figure 8), utilizing Lemma 6.11 and Lemma 6.12. This reduction transforms (6.6) into (6.12).

3. (3) We establish a connection between the rectangular shape $R_k$ (on the right in Figure 8) and $\overline {R_k}$ in Lemma 6.16.

4. (4) We present Proposition 6.17 and demonstrate that when combined with Lemma 6.16 and Lemma A.1, it completes the proof of Proposition 6.5.

Definition 6.6. Given a filled diagram $(D,f)$ , let $L=(A_1,\dots ,A_r)\in \mathbf {OP}(D;M)$ for some $M\in \mathrm {Mat}^{\geq 0}$ . We set $A_0=D\setminus \bigcup _{i=1}^r A_i$ , so that for every cell $u\in D$ there exists unique $\ell$ such that $u\in A_{\ell }$ . We define $\overline {\mathrm {Inv}}_D(L)$ as the set of attacking pairs $(u,v)$ that do not belong to $\mathrm {Inv}_D(\sigma (D;L)^{-1})$ . In other words, $\overline {\mathrm {Inv}}_D(L)$ consists of pairs $(u,v)$ of cells in $D$ such that $(u,v)$ is an attacking pair and $u$ belongs to $A_{\ell }$ while $v$ belongs to $A_{\ell ^{\prime}}$ with $ \ell \lt \ell ^{\prime}$ . We define $\overline {\mathrm {inv}}_D(L)$ as the product of $q$ over all pairs $(u,v)\in \overline {\mathrm {Inv}}_D(L)$ .

Next, we define $\overline {\mathrm {Des}}_D(L)$ as the set of cells in $D$ that are not bottom cells and are not in $\mathrm {Des}_D(\sigma (D;L)^{-1})$ . In other words, $\overline {\mathrm {Des}}_D(L)$ consists of cells $(i,j)$ in $D$ such that $(i,j)\in A_{\ell }$ and $(i-1,j)\in A_{\ell ^{\prime}}$ for $\ell \lt \ell ^{\prime}$ , where $A_0$ is defined as before. We let $\overline {\mathrm {maj}}_{(D,f)}(L)$ denote the product of $f(u)$ over all cells $u\in \overline {\mathrm {Des}}_D(L)$ . Finally, we define $\overline {\mathrm {stat}}_{(D,f)}$ as follows:

\begin{equation*} \overline {\mathrm {stat}}_{(D,f)}(L) := \overline {\mathrm {inv}}_{D}(L)\overline {\mathrm {maj}}_{(D,f)}(L). \end{equation*}

By definition, we have

\begin{equation*} \mathrm {stat}_{(D,f)}(\sigma (D;L)^{-1})=\frac {\mathrm {stat}_{(D,f)}(w_0)}{\overline {\mathrm {stat}}_{(D,f)}(L)}=\frac {\mathrm {stat}_{(D,f)}(w_0)}{\overline {\mathrm {inv}}_D(L)\overline {\mathrm {maj}}_{D,f}(L)}, \end{equation*}

where $w_0$ is the longest permutation in $\mathfrak {S}_{|D|}$ .

Lemma 6.7. For each $1\le i\le k$ ,

\begin{equation*} \mathrm {stat}_{(\overline {\delta }_{k,i},\overline {f}_{k,i}^{\textbf {z}})}(w_0)= q^{({4k^3-3k^2-4k})/{3}}\dfrac {z_i\prod _{j=1}^{k-1}z_{2k-j}^k}{z_{2k-1}\prod _{j=1}^{k-1}z_j^{2k-2j}} \end{equation*}

for the longest permutation $w_0$ .

Proof. For simplicity, let $(D,f)=(\overline {\delta }_{k,i},\overline {f}_{k,i})$ . We claim that

(6.4) \begin{equation} \mathrm {maj}_{(D,f)}(w_0) = q^{(({3k^2-5k})/{2}) + i-1}\dfrac {z_i\prod _{j=1}^{k-1}z_{2k-j}^k}{z_{2k-1}\prod _{j=1}^{k-1}z_j^{2k-2j}} \end{equation}

and

(6.5) \begin{equation} \mathrm {inv}_{D}(w_0) = q^{(({8k^3-15k^2+7k})/{6})+1-i}, \end{equation}

which completes the proof.

The first claim, (6.4), follows directly from the definition of $\overline {f}_{k,i}$ in (6.2) and the fact that $\mathrm {maj}_{(D,f)}(w_0)=\prod _{c\in D}\overline {f}_{k,i}(c)$ . To see (6.5), note that for a given cell $u=(a,b)$ , the number of pairs $(u,v)$ in attacking position in $D$ is

\begin{equation*} \begin{cases} k-1 &\text { if } 1\lt a\le k\mbox{ and } 1\le b \le k,\\ k-b-1 &\text { if } a=1\mbox{ and } 1\le b\lt k,\\ 2k-a-1 &\text { if } k\lt a\le 2k-i\mbox{ and } 1\le b\le 2k-a-1 \text { or if } 2k-i\lt a\lt 2k\mbox{ and } 1\le b\le 2k-a,\\ 2k-a &\text { if } k\lt a\le 2k-i\mbox{ and } b=k.\\ \end{cases} \end{equation*}

Therefore, the total number of such attacking pairs, i.e. the total number of inversion pairs of $w_0$ , is

\begin{align*} & k(k-1)^2 + \sum _{1\le b \lt k}(k-b-1) + \sum _{k\lt a\le 2k-i}(2k-a-1)^2 + \sum _{2k-i\lt a\lt 2k}(2k-a-1)(2k-a) \\[6pt]&\qquad + \sum _{k\lt a\le 2k-i}(2k-a)\\&\quad = \frac {8k^3-15k^2+7k}{6}+1-i. \end{align*}

By the above lemma, the term $(\prod _{j\neq i}z_j)\mathrm {stat}_{(\overline {\delta }_{k,i},\overline {f}_{k,i}^{\textbf {z}})}(w_0)$ is independent of $i$ , so the left-hand side of Proposition 6.5 becomes

\begin{align*} q^{\frac {4k^3-3k^2-4k}{3}}\dfrac {z_k\prod _{j=1}^{k-1}z_{2k-j}^k}{z_{2k-1}\big (\prod _{j=1}^{k-1}z_j^{2k-2j-1}\big ) }\sum _{i=1}^{k} \bigg(\prod _{j\neq i}\dfrac {1}{z_j-z_i}\bigg)\sum _{L\in \mathbf {OP}(\overline {\delta }_{k,i};M)}\frac {1}{\overline {\mathrm {stat}}_{(\overline {\delta }_{k,i},\overline {f}^{\mathbf {z}}_{k,i})}(L)}. \end{align*}

Therefore, after the cancellation, Proposition 6.5 is equivalent to the following: for $M\in \mathrm {Mat}^{\ge 0}_{r\times (2k-1)}$ such that $|M|=k-1$ , letting $\alpha =\mathrm {csum}(M)$ , we have

(6.6) \begin{equation} \sum _{i=1}^{k} \bigg(\prod _{j\neq i}\dfrac {1}{z_j-z_i}\bigg)\sum _{L\in \mathbf {OP}(\overline {\delta }_{k,i};M)}\frac {1}{\overline {\mathrm {stat}}_{(\overline {\delta }_{k,i},\overline {f}^{\mathbf {z}}_{k,i})}(L)}=\bigg(\frac {q^{\sum _{i,j}\binom {M_{i,j}}{2}}}{q^{k(k-1)}\prod _{i=1}^{k-1}z_{2k-i}^{\alpha _i}}\bigg)\mathrm {lb}(M). \end{equation}

Now we analyze (6.6). Before doing so, we define some terminology and prove preparatory lemmas (Lemmas 6.11 and 6.12).

For a diagram $D$ , note that $\mathbf {OP}(D;M)$ makes sense if $M$ has $\ell$ columns where $\ell$ is the number of rows in $D$ . For a matrix $M$ with $\ell ^{\prime}$ columns such that $\ell ^{\prime}\lt \ell$ , we consider $\overline {M}$ obtained by appending $\ell -\ell ^{\prime}$ zero columns to $M$ . From now on, with an abuse of notation, we refer to $\mathbf {OP}(D;\overline {M})$ as $\mathbf {OP}(D;M)$ .

Let $D$ be a diagram and $E$ a subdiagram of $D$ . Given $L=(A_1,\dots ,A_r)\in \mathbf {OP}(D;M)$ , we define $L \vert _E$ as $(A_1 \cap E,\dots ,A_r \cap E)$ .

Definition 6.8. We define the diagram $\overline {R}_k$ to be the subdiagram of $\overline {\delta }_{k,i}$ obtained by restricting to the first $k$ rows and the diagram $R_k$ to be the subdiagram of $\overline {R}_k$ obtained by restricting to the first $k-1$ columns. In other words, $\overline {R}_k=[I_1,I_2,\dots ,I_k]$ and $R_k=[I_1,I_2,\dots ,I_{k-1}]$ , where $I_j$ is the interval given by

\begin{equation*} I_j = \begin{cases} [k] & \text {if } j\lt k,\\ [2,k] & \text {if } j=k. \end{cases} \end{equation*}

We define $(\overline {R}_{k},\overline {g}^{\mathbf {z}}_{k,i})$ and $(R_{k},g_{k,i}^{\mathbf {z}})$ to be corresponding sub-filled diagrams of $(\overline {\delta }_{k,i},\overline {f}^{\mathbf {z}}_{k,i})$ .

To describe the filling $\overline {g}^{\mathbf {z}}_{k,i}$ , it is convenient to introduce the following operator.

Definition 6.9. For a function $P(z_1,\dots ,z_{k-1})$ of variables $z_1,\dots ,z_{k-1}$ , let $\eta _{k,i}$ be the operator that shifts the indices of variables by

\begin{equation*} \eta _{k,i}\left (P(z_1,\dots ,z_{k-1})\right ):= P(z_1,\dots ,z_{i-1},z_{i+1},\dots ,z_{k}). \end{equation*}

Using the operator $\eta _{k,i}$ , we can write the filling $\overline {g}^{\mathbf {z}}_{k,i}$ of $\overline {R}_k$ as

\begin{equation*} \overline {g}^{\mathbf {z}}_{k,i}(a,b)= \begin{cases} \eta _{k,i}\bigg(\dfrac {q(z_{2k+1-a})}{z_b}\bigg) &\text{if } b\lt k, \\[12pt]\dfrac {q(z_{2k+1-a})}{z_i} &\text {if } b=k. \end{cases} \end{equation*}

For example, recall the filled diagram $(\overline {\delta }_{4,3},\overline {f}_{4,3}^{\textbf {z}})$ in Figure 7. Taking the sub-filled diagram by restricting to the first four rows, we obtain the filled diagram $(\overline {R}_{4},\overline {g}^{\mathbf {z}}_{4,3})$ (on the left in Figure 8). Again by restricting to the first three columns, we obtain the filled diagram $({R}_{4},g^{\mathbf {z}}_{4,3})$ (on the right in Figure 8).

Figure 8.

The filled diagrams $(\overline {R}_{4},\overline {g}^{\mathbf {z}}_{4,3})$ and $({R}_{4},{g}_{4,3}^{\mathbf {z}})$ .

The following two lemmas will be used to transform (6.6) to (6.12), which only concerns the reduced elements in $\mathbf {OP}(D;M)$ .

Figure 9.

On the left is $L$ , which is reduced, while $L^{\prime}$ on the right is not reduced.

Lemma 6.11. Let $M\in \mathrm {Mat}^{\ge 0}_{r\times (k-1)}$ and let $\gamma$ be a vector of nonnegative integers of length $k-1$ . Furthermore, assume that $|M|-|\gamma |\lt k-1$ . Then we have

\begin{equation*} \sum _{i=1}^{k}\bigg(\prod _{j\neq i}\frac {1}{z_j-z_i}\bigg)\sum _{\substack {L\in \mathbf {OP}(\overline {R}_k;M)\\ \gamma (\overline {R}_k;L)=\gamma }}\frac {1}{\overline {\mathrm {stat}}_{(\overline {R}_k,\overline {g}^{\mathbf {z}}_{k,i})}(L)}=0. \end{equation*}

Proof. Let $\alpha =\mathrm {csum}(M)$ and $L\in \mathbf {OP}(\overline {R}_k;M)$ such that $\gamma (\overline {R}_k;L)=\gamma$ . For each $1\leq j\leq k-1$ , there are exactly $\alpha _j-\gamma _j$ cells in the $(j+1)$ th row of $\overline {R}_k$ that are in $\overline {\mathrm {Des}}_{\overline {R}_k}(L)$ . Note that if $c$ is a cell in the $(j+1)$ th row of $\overline {R}_k$ , we have $\overline {g}^{\mathbf {z}}_{k,i}(c)=q({z_{2k-j}})/{z_{\ell }}$ for some $1\leq \ell \leq k$ . Therefore we can write

(6.7) \begin{equation} \sum _{\substack {L\in \mathbf {OP}(\overline {R}_k;M) \\ \gamma (\overline {R}_k;L)=\gamma }}\frac {1}{\overline {\mathrm {stat}}_{(\overline {R}_k,\overline {g}_{k,i})}(L)}=\frac {P_i(z_1,\dots ,z_k)}{\prod _{j=1}^{k-1}z_{2k-j}^{\alpha _j-\gamma _j}} \end{equation}

for some polynomial $P_i(z_1,\dots ,z_k)$ of degree $\sum (\alpha _i-\gamma _i)=|M|-|\gamma |\lt k-1$ . As we have $P_i=P_j$ when $z_i=z_j$ due to the description of the fillings $\overline {g}^{\mathbf {z}}_{k,i}$ and $\overline {g}^{\mathbf {z}}_{k,j}$ , Lemma A.2 finishes the proof.

Lemma 6.12. Let $M\in \mathrm {Mat}^{\ge 0}_{r\times (2k-1)}$ and write $\mathrm {csum}(M)=\alpha$ . If there exists $\ell \leq k-1$ such that $\alpha _{\ell }=0$ and $\sum _{i=1}^{\ell -1}\alpha _i\lt k-1$ , we have

(6.8) \begin{equation} \sum _{i=1}^{k}\bigg (\prod _{j\neq i}\frac {1}{z_j-z_i}\bigg )\sum _{\substack {L\in \mathbf {OP}(\overline {\delta }_{k,i};M)}}\frac {1}{\overline {\mathrm {stat}}_{(\overline {\delta }_{k,i},\overline {f}^{\mathbf {z}}_{k,i})}(L)}=0. \end{equation}

Proof. Let $(D^{(1)},f^{(1)}_i)$ be the sub-filled diagram of $(\overline {\delta }_{k,i},\overline {f}^{\mathbf {z}}_{k,i})$ obtained by restricting to the first $\ell$ rows, and let $(D^{(2)}_i,f^{(2)}_i)$ be the remaining sub-filled diagram from the $(\ell +1)$ th row and above. Note that the shape $D^{(1)}$ is independent of $i$ . For $L=(A_1,\dots ,A_r)\in \mathbf {OP}(\overline {\delta }_{k,i};M)$ , there is no cell in the $\ell$ th row that is in $\bigcup\nolimits _{t=1}^{r}A_t$ as $\alpha _{\ell }=0$ . Therefore we have

\begin{align*} \overline {\mathrm {Inv}}_{\overline {\delta }_{k,i}}(L)=\overline {\mathrm {Inv}}_{D^{(1)}}(L\vert _{D^{(1)}}) \cup \overline {\mathrm {Inv}}_{D^{(2)}_i}(L\vert _{D^{(2)}_i}), \quad \overline {\mathrm {Des}}_{\overline {\delta }_{k,i}}(L)=\overline {\mathrm {Des}}_{D^{(1)}}(L\vert _{D^{(1)}}) \cup \overline {\mathrm {Des}}_{D^{(2)}_i}(L\vert _{D^{(2)}_i}), \end{align*}

which gives $\overline {\mathrm {stat}}_{(\overline {\delta }_{k,i},\overline {f}^{\mathbf {z}}_{k,i})}(L)=\overline {\mathrm {stat}}_{(D^{(1)},f^{(1)}_i)}(L\vert _{D^{(1)}})\overline {\mathrm {stat}}_{(D^{(2)}_i,f^{(2)}_i)}(L\vert _{D^{(2)}_i})$ . Note that we have $\mathrm {type}(D^{(1)};L\vert _{D^{(1)}})=M^{(1)}$ and $\mathrm {type}(D^{(2)}_i;L\vert _{D^{(2)}_i})=M^{(2)}$ . Here, $M^{(1)}$ represents the sub-matrix of $M$ obtained by restricting it to the first $\ell$ columns. Similarly, $M^{(2)}$ is the sub-matrix of $M$ obtained by restricting it from the $(\ell +1)$ th column to the $(2k-1)$ th column. We conclude that

\begin{align*} & \sum _{L\in \mathbf {OP}(\overline {\delta }_{k,i};M)}\frac {1}{\overline {\mathrm {stat}}_{(\overline {\delta }_{k,i},\overline {f}^{\mathbf {z}}_{k,i})}(L)} \\&\quad =\sum _{L^{(1)}\in \mathbf {OP}(D^{(1)};M^{(1)})}\frac {1}{ \overline {\mathrm {stat}}_{(D^{(1)},f^{(1)}_i)}(L^{(1)})}\sum _{L^{(2)}\in \mathbf {OP}(D^{(2)}_i;M^{(2)})}\frac {1}{ \overline {\mathrm {stat}}_{(D^{(2)}_i,f^{(2)}_i)}(L^{(2)})}. \end{align*}

For $1\leq i,j\leq k$ , we have

\begin{equation*} S_{i}^{-1}\dots S_{k-1}^{-1}(D_{i}^{(2)},f_{i}^{(2)})=S_{j}^{-1}\dots S_{k-1}^{-1}(D_{j}^{(2)},f_{j}^{(2)}), \end{equation*}

which gives $(D_{i}^{(2)},f_{i}^{(2)})\cong (D_{j}^{(2)},f_{j}^{(2)})$ . From the identity $\widetilde {H}_{(D_{i}^{(2)},f_{i}^{(2)})}[X]=\widetilde {H}_{(D_{j}^{(2)},f_{j}^{(2)})}[X]$ , taking the coefficient of $F_{(1,\dots ,1)}$ gives

(6.9) \begin{equation} \mathrm {stat}_{(D_{i}^{(2)},f_{i}^{(2)})}(w_0)=\mathrm {stat}_{(D_{j}^{(2)},f_{j}^{(2)})}(w_0) \end{equation}

where $w_0$ is the longest permutation of the size $|D^{(2)}_i|$ . We also have

(6.10) \begin{equation} \sum _{L\in \mathbf {OP}(D^{(2)}_i;M^{(2)})}\mathrm {stat}_{(D_{i}^{(2)},f_{i}^{(2)})}(\sigma (D^{(2)}_i;L)^{-1})=\sum _{L\in \mathbf {OP}(D^{(2)}_j;M^{(2)})}\mathrm {stat}_{(D_{j}^{(2)},f_{j}^{(2)})}(\sigma (D^{(2)}_j;L)^{-1}) \end{equation}

by (5.3).

By (6.9) and (6.10), we deduce that the term $\sum _{L^{(2)}\in \mathbf {OP}(D^{(2)}_i;M^{(2)})} ({1}/({ \overline {\mathrm {stat}}_{(D^{(2)}_i,f^{(2)}_i)}(L^{(2)})}))$ is independent of $i$ , i.e. for $1\le i \le k$ we have

\begin{equation*} \sum _{L^{(2)}\in \mathbf {OP}(D^{(2)}_1;M^{(2)})}\frac {1}{ \overline {\mathrm {stat}}_{(D^{(2)}_1,f^{(2)}_1)}(L^{(2)})} = \sum _{L^{(2)}\in \mathbf {OP}(D^{(2)}_i;M^{(2)})}\frac {1}{ \overline {\mathrm {stat}}_{(D^{(2)}_i,f^{(2)}_i)}(L^{(2)})}. \end{equation*}

Therefore, we conclude that the left-hand side of (6.8) is equal to

\begin{align*} \sum _{L^{(2)}\in \mathbf {OP}(D^{(2)}_1;M^{(2)})}\frac {1}{ \overline {\mathrm {stat}}_{(D^{(2)}_1,f^{(2)}_1)}(L^{(2)})}\sum _{i=1}^{k}\bigg (\prod _{j\neq i}\frac {1}{z_j-z_i}\bigg )\sum _{L^{(1)}\in \mathbf {OP}(D^{(1)};M^{(1)})}\frac {1}{ \overline {\mathrm {stat}}_{(D^{(1)},f^{(1)}_i)}(L^{(1)})}.\\[-4pt] \end{align*}

Finally, we have

\begin{align*} & \sum _{i=1}^{k}\bigg (\prod _{j\neq i}\frac {1}{z_j-z_i}\bigg )\sum _{L^{(1)}\in \mathbf {OP}(D^{(1)};M^{(1)})}\frac {1}{ \overline {\mathrm {stat}}_{(D^{(1)},f^{(1)}_i)}(L^{(1)})}\\[8pt]&\quad = \sum _{i=1}^{k}\bigg (\prod _{j\neq i}\frac {1}{z_j-z_i}\bigg )\sum _{L^{(1)}\in \mathbf {OP}(\overline {R}_k;M^{(1)})}\frac {1}{ \overline {\mathrm {stat}}_{(\overline {R}_k,\overline {g}_{k,i})}(L^{(1)})} = 0, \end{align*}

where the first equality is obvious and the last equality follows from Lemma 6.11 since $|M^{(1)}|=\sum _{i=1}^{\ell }\alpha _i\lt k-1$ .