2.1 Combinatorial statistics and tableaux

A composition is a sequence $\alpha =(\alpha _1,\dots , \alpha _k)$ , of k nonnegative integers called its parts. The number of nonzero parts is given by $\ell (\alpha )$ , and $|\alpha |=\sum _i\alpha _i$ is the sum of the parts. Denote by $\operatorname {\mathrm {sort}}(\alpha )$ and $\operatorname {\mathrm {inc}}(\alpha )$ the compositions obtained by rearranging the parts of $\alpha $ in weakly decreasing and increasing order, respectively. If $\alpha $ is a weakly decreasing composition, we call it a partition. For a partition $\lambda $ , define the conjugate partition $\lambda '=(\lambda _1',\ldots ,\lambda _{\ell (\lambda )}')$ by $\lambda ^{\prime }_j=|\{i:\lambda _i\geq j\}|$ , and define $n(\lambda )=\sum _i {\lambda _i'\choose 2}$ . We may equivalently use the frequency notation to describe a partition $\lambda $ as a multiplicity vector. Let $m_i(\lambda )$ be the number of parts of size i in $\lambda $ ; then we may write $\lambda $ as $\langle 1^{m_1(\lambda )}2^{m_2(\lambda )}\ldots \rangle $ . If each part of $\lambda $ appears at most once, we call $\lambda $ a strict partition.

Given a partition or composition $\alpha =(\alpha _1,\dots , \alpha _n)$ , its diagram $\operatorname {\mathrm {\texttt {dg}}}(\alpha )$ is a sequence of bottom-justified columns with $\alpha _i$ cells in the i-th column. In this article we will only be considering diagrams for partitions (although the leftmost and rightmost diagrams in Figure 1 are composition diagrams). Note that in this article, $\operatorname {\mathrm {\texttt {dg}}}(\lambda )$ corresponds to the Ferrers diagram of the conjugate partition $\lambda '$ .

Figure 1 We show the diagrams of the compositions $\alpha =(2,3,4,1,3,2)$ , $\lambda (\alpha )$ , and $\operatorname {\mathrm {inc}}(\alpha )$ . The cell $u=(2,3)$ has $\operatorname {\mathrm {\texttt {leg}}}(u)$ equal to $2, 1, 0$ in each diagram, respectively.

The columns of a partition or composition diagram $\operatorname {\mathrm {\texttt {dg}}}(\alpha )$ are labeled from left to right, and the rows from bottom to top. The notation $u=(r,c)$ refers to the cell in row r and column c (opposite of the convention of Cartesian coordinates). We denote by $\operatorname {\mathrm {South}}(u)=\operatorname {\mathrm {South}}(r,c)$ the cell $(r-1,c)$ directly below u, if it exists; if $r=1$ and $\operatorname {\mathrm {South}}(u)$ doesn’t exist, we set the convention $\operatorname {\mathrm {South}}(u)=\infty $ . The leg of a cell $u=(r,j)\in \operatorname {\mathrm {\texttt {dg}}}(\alpha )$ is denoted $\operatorname {\mathrm {\texttt {leg}}}(u)=\alpha _j-r$ and is equal to the number of cells above in the same column as u. See Figure 1 for an example.

A filling $\sigma :\operatorname {\mathrm {\texttt {dg}}}(\alpha ) \to \mathbb {Z}^+$ is an assignment of positive integers to the cells of $\operatorname {\mathrm {\texttt {dg}}}(\alpha )$ . For a cell $u\in \operatorname {\mathrm {\texttt {dg}}}(\alpha )$ , $\sigma (u)$ denotes the entry in the cell u. The content of a filling $\sigma $ is recorded as a monomial in the variables $X=x_1,x_2,\ldots $ , and is denoted by $x^{\sigma } := \prod _{u\in \operatorname {\mathrm {\texttt {dg}}}(\lambda )} x_{\sigma (u)}$ . Define the major index of a filling $\sigma $ , denoted $\operatorname {\mathrm {\texttt {maj}}}(\sigma )$ , by

$$\begin{align*}{{\texttt{maj}}}(\sigma) = \sum_{\substack{u\in {{\texttt{dg}}}(\lambda)\\\sigma(u)>\sigma({\mathrm{South}}(u))}} ({{\texttt{leg}}}(u)+1). \end{align*}$$

We shall also define two types of non-attacking fillings.

Definition 2.2. For two cells $x=(r_1,i),y=(r_2,j)\in \operatorname {\mathrm {\texttt {dg}}}(\lambda )$ with $i<j$ , we say they are $\operatorname {\mathrm {\texttt {inv}}}$ -attacking if $r_1=r_2$ or $r_2=r_1+1$ . We say x and y are $\operatorname {\mathrm {\texttt {quinv}}}$ -attacking if $r_1=r_2$ or if $i<j$ and $r_2=r_1-1$ . The configurations comparing the two definitions are shown below:

A filling of $\operatorname {\mathrm {\texttt {dg}}}(\lambda )$ is $\operatorname {\mathrm {\texttt {inv}}}$ -non-attacking if no pair of $\operatorname {\mathrm {\texttt {inv}}}$ -attacking cells contains the same entry. Similarly, a filling of $\operatorname {\mathrm {\texttt {dg}}}(\lambda )$ is $\operatorname {\mathrm {\texttt {quinv}}}$ -non-attacking if no pair of $\operatorname {\mathrm {\texttt {quinv}}}$ -attacking cells contains the same entry.

2.2 Definitions of $P_{\lambda }$ , $J_{\lambda }$ , and $\widetilde {H}_{\lambda }$

For $X=x_1,x_2,\ldots $ a set of indeterminates, let $\operatorname {\mathrm {Sym}}$ be the ring of symmetric functions in X with coefficients in $\mathbb {Q}(q,t)$ . The Macdonald polynomial $P_{\lambda }(X;q,t)$ is characterized as the unique polynomial in $\operatorname {\mathrm {Sym}}$ that is orthogonal with respect to the $q,t$ -generalization of the Hall inner product, and can be written as

$$\begin{align*}P_{\lambda}(X;q,t)=m_{\lambda}(X)+\sum_{\mu< \lambda} b_{\mu,\lambda}(q,t)m_{\mu}(X), \end{align*}$$

where the usual dominance order on partitions is used: $\mu \leq \lambda $ if and only if $\mu _1+\cdots +\mu _k\leq \lambda _1+\cdots +\lambda _k$ for all $k\geq 1$ . When $P_{\lambda }(X;q,t)$ is scaled by a certain product of linear terms, one obtains the integral form $J_{\lambda }(X;q,t)$ , whose coefficients are in $\mathbb {Z}[q,t]$ . Define

(2.1) $$ \begin{align} {\mathrm{PR}}_{\lambda}(q,t)=\prod_{u\in{{\texttt{dg}}}(\lambda)}(1-q^{{{\texttt{leg}}}(u)}t^{{{\texttt{arm}}}(u)+1}),\qquad \widetilde{{\mathrm{PR}}}_{\lambda}(q,t)=\prod_{u\in\overline{{{\texttt{dg}}}}(\lambda)}(1-q^{{{\texttt{leg}}}(u)+1}t^{{{\texttt{arm}}}(u)+1}) \end{align} $$

where $\overline {\operatorname {\mathrm {\texttt {dg}}}}(\lambda )$ is the set of cells in $\operatorname {\mathrm {\texttt {dg}}}(\lambda )$ not in the bottom row. The integral form is then defined as $J_{\lambda }(X;q,t)=\operatorname {\mathrm {PR}}_{\lambda }(q,t) P_{\lambda }(X;q,t)$ .

In [Reference Garsia and Haiman8], Garcia and Haiman defined the modified Macdonald polynomials by plethystic substitution into $J_{\lambda }(X;q,t)$ :

(2.2) $$ \begin{align} \widetilde{H}_{\lambda}(X;q,t)=t^{n(\lambda)}J_{\lambda}\Big[\frac{X}{1-t^{-1}};q,t^{-1}\Big]. \end{align} $$

We postpone the definition of plethystic substitution until Section 2.4, where the plethystic relationship in equation (2.2) is interpreted combinatorially through superization. This interpretation was used in [Reference Haglund, Haiman and Loehr10] to derive the following formula for $P_{\lambda }$ in terms of $\operatorname {\mathrm {\texttt {inv}}}$ -non-attacking fillings:

(2.3) $$ \begin{align} P_{\lambda}(X;q,t)=\frac{\widetilde{{\mathrm{PR}}}_{\lambda}(q,t)}{{\mathrm{PR}}_{\lambda}(q,t)}\hspace{-0.2in}\sum_{\substack{\sigma:{{\texttt{dg}}}(\lambda)\rightarrow\mathbb{Z}^+\\\sigma\,{\mathrm{inv-non-attacking}}}}x^{\sigma}q^{{{\texttt{maj}}}(\sigma)}t^{{{\texttt{coinv}}}(\sigma)}\prod_{\substack{u\in{{\texttt{dg}}}(\lambda)\\\sigma(u)\neq\sigma({\mathrm{South}}(u))}}\frac{1-t}{1-q^{{{\texttt{leg}}}(u)+1}t^{{{\texttt{arm}}}(u)+1}}. \end{align} $$

For a discussion of the prefactor $\widetilde {\operatorname {\mathrm {PR}}}_{\lambda }(q,t)/\operatorname {\mathrm {PR}}_{\lambda }(q,t)$ , see [Reference Corteel, Haglund, Mandelshtam, Mason and Williams5, Section 4].

Although the statistics $\operatorname {\mathrm {\texttt {maj}}}$ and $\operatorname {\mathrm {\texttt {coinv}}}$ appearing in the above formula are well behaved, the formula itself is unsatisfying because many of the tableaux appearing in the sum compress to a single term in the polynomial, making the computation quite inefficient for certain $\lambda $ ’s. For example, when $\lambda =(1^k)$ , $P_{\lambda }=m_{1^k}$ , and the coefficient $[x^{\lambda }]P_{\lambda }(X;q,t)=1$ , whereas in the formula above, there are $k!$ tableaux contributing to the coefficient of $x^{\lambda }$ .

The multiline queue formula of [Reference Corteel, Mandelshtam and Williams6] was a significant improvement over (2.3) in the sense of having fewer terms; however, translating it into the tableaux setting resulted in having to define complicated statistics, making such a tableaux formula impractical. On the other hand, in [Reference Corteel, Haglund, Mandelshtam, Mason and Williams5, Equation 4.10], a tableaux formula was given in terms of sorted non-attacking fillings of $\operatorname {\mathrm {\texttt {dg}}}(\operatorname {\mathrm {inc}}(\lambda ))$ and the generalized statistics $\operatorname {\mathrm {\texttt {coinv}}}'$ and $\operatorname {\mathrm {\texttt {arm}}}'$ from [Reference Haglund, Haiman and Loehr10]. This formula was based on the fact that $P_{\lambda }$ can be written as a sum over certain permuted basement Macdonald polynomials. However, the statistics $\operatorname {\mathrm {\texttt {coinv}}}'$ and $\operatorname {\mathrm {\texttt {arm}}}'$ are more complicated than the statistics $\operatorname {\mathrm {\texttt {arm}}}$ and $\operatorname {\mathrm {\texttt {inv}}}$ in (2.3), and don’t correspond directly to statistics on multiline queues.

2.3 Two formulas for $\widetilde {H}_{\lambda }$

In this section, we describe the formulas (1.1) due to [Reference Haglund, Haiman and Loehr10] and (1.2) due to [Reference Ayyer, Mandelshtam and Martin2] for $\widetilde {H}_{\lambda }(X;q,t)$ .

Define the function $\mathcal {Q}:\mathbb {N}^3\rightarrow \{0,1\}$ by $\mathcal {Q}(a,b,c)=0$ if the entries $a,b,c$ satisfy one of the following inequalities and $\mathcal {Q}(a,b,c)=1$ otherwise:

(2.4) $$ \begin{align} a\leq b<c\quad\text{or}\quad c<a\leq b \quad\text{or}\quad b<c<a. \end{align} $$

2.3.1 HHL statistics

For a cell $u=(r,k)\in \operatorname {\mathrm {\texttt {dg}}}(\lambda )$ , its arm denoted $\operatorname {\mathrm {Arm}}(u)$ is the set of cells in its row to its right, and $\operatorname {\mathrm {\texttt {arm}}}(u)=|\operatorname {\mathrm {Arm}}(u)|=\lambda ^{\prime }_r-k$ . Below, the shaded cells correspond to $\operatorname {\mathrm {Arm}}(u)$ :

A $\Gamma $ -triple is a triple of cells $x=(r,i), y=(r-1,i), z=(r,j)$ where $j>i$ , so that $z\in \operatorname {\mathrm {Arm}}(x)$ . When $r=1$ , it is called a degenerate $\Gamma $ -triple. A $\Gamma $ -triple is an inversion in a filling $\sigma $ of $\operatorname {\mathrm {\texttt {dg}}}(\lambda )$ if the entries $a=\sigma (x)$ , $b=\sigma (y)$ , and $c=\sigma (z)$ in the configuration below are cyclically increasing when read counterclockwise. Ties are broken with respect to top-to-bottom, left-to-right reading order on the entries. By convention, $\sigma (y)=\infty $ in a degenerate triple:

Equivalently, a $\Gamma $ -triple with contents $a,b,c$ in the configuration above is an inversion if $\mathcal {Q}(a,b,c)=0$ , and a coinversion if $\mathcal {Q}(a,b,c)=1$ . The total number of inversion triples in $\sigma $ is denoted by $\operatorname {\mathrm {\texttt {inv}}}(\sigma )$ , and the number of coinversion triples is $\operatorname {\mathrm {\texttt {coinv}}}(\sigma )=n(\lambda )-\operatorname {\mathrm {\texttt {inv}}}(\sigma )$ .

2.3.2 Queue statistics

For a cell $u=(r,k)\in \operatorname {\mathrm {\texttt {dg}}}(\lambda )$ , its arm $\operatorname {\mathrm {\widehat {Arm}}}(u)$ is the set of cells in the row below strictly to its right, and $\operatorname {\mathrm {\widehat {\texttt {arm}}}}(u)=|\operatorname {\mathrm {\widehat {Arm}}}(u)|=\lambda ^{\prime }_{r-1}-k$ . An L-triple is a triple of cells $x=(r,i)$ , $y=(r-1,i)$ , $z=(r-1,j)$ where $j>i$ , so that $z\in \operatorname {\mathrm {\widehat {Arm}}}(x)$ . Below, the shaded cells correspond to $\operatorname {\mathrm {\widehat {Arm}}}(u)$ :

When $r=\lambda _k$ , it is called a degenerate L-triple. An L-triple is a queue inversion (or $\operatorname {\mathrm {\texttt {quinv}}}$ ) in a filling $\sigma $ if the entries $a=\sigma (x)$ , $b=\sigma (y)$ , $c=\sigma (z)$ in the configuration below are cyclically increasing when read counterclockwise. Ties are broken with respect to top-to-bottom, right-to-left reading order on the entries. By convention $\sigma (x)=0$ in a degenerate triple:

Equivalently, an L-triple with contents $a,b,c$ in the configuration above is a $\operatorname {\mathrm {\texttt {quinv}}}$ triple if $\mathcal {Q}(a,b,c)=0$ , and if $\mathcal {Q}(a,b,c)=1$ we call it a $\operatorname {\mathrm {\texttt {coquinv}}}$ triple. The total number of $\operatorname {\mathrm {\texttt {quinv}}}$ triples in $\sigma $ is denoted by $\operatorname {\mathrm {\texttt {quinv}}}(\sigma )$ , and the number of $\operatorname {\mathrm {\texttt {coquinv}}}$ triples is $\operatorname {\mathrm {\texttt {coquinv}}}(\sigma )=n(\lambda )-\operatorname {\mathrm {\texttt {quinv}}}(\sigma )$ .

With these statistics, $\widetilde {H}_{\lambda }(X;q,t)$ can be written as a sum over fillings $\sigma :\operatorname {\mathrm {\texttt {dg}}}(\lambda )\rightarrow \mathbb {Z}^+$ either in terms of the $\operatorname {\mathrm {\texttt {inv}}}$ statistic in (1.1) or in terms of the $\operatorname {\mathrm {\texttt {quinv}}}$ statistic in (1.2).

Remark 2.4. Recently, an interesting bijection relating the statistics $\operatorname {\mathrm {\texttt {inv}}}$ and $\operatorname {\mathrm {\texttt {quinv}}}$ was found in [Reference Jin and Lin13].

Example 2.5. In the tableau $\sigma $ below, the cell $u=(2,2)$ has $\operatorname {\mathrm {\texttt {leg}}}(u)=1$ , $\operatorname {\mathrm {\texttt {arm}}}(u)=3$ and $\operatorname {\mathrm {\widehat {\texttt {arm}}}}(u)=7$ . $\operatorname {\mathrm {\texttt {maj}}}(\sigma )=5$ , $\operatorname {\mathrm {\texttt {inv}}}(\sigma )=6$ , and $\operatorname {\mathrm {\texttt {quinv}}}(\sigma )=14$ . Thus this filling contributes $x_1^5x_2^3x_3^6x_4x_5q^5t^{6}$ to (1.1) and $x_1^5x_2^3x_3^6x_4x_5q^5t^{14}$ to (1.2).

2.4 Formulas for $P_{\lambda }$ and $J_{\lambda }$ from $\widetilde {H}_{\lambda }$ via superization

We recall briefly the definition of plethystic substitution (see [Reference Haglund9, Chapter 1] for a full treatment). Let $X=x_1,x_2,\ldots $ and $Y=y_1,y_2,\ldots $ be two alphabets. For a formal power series or polynomial $A\in \operatorname {\mathrm {Sym}}$ in the indeterminates X, define the plethystic substitution of A into the power sum symmetric function $p_k=\sum _j x_j^k$ by $p_k[A]=A(x_1^k,x_2^k,\ldots )$ . For a symmetric function f, extend the definition of plethystic substitution by expanding f in the power sum basis and substituting $p_k[A]$ for $p_k(A)$ to obtain $f[A]$ . By convention, when X appears inside brackets, it is treated as a formal power series as $f[X]=f[x_1+x_2+\cdots ]$ , so that $f[X]=f(X)$ and $f[X+Y]=f(X,Y)$ . We will also use the notation $f[\varepsilon X]=f(-X)=f(-x_1,-x_2,\ldots )$ .

We recall the classical notion of superization of a symmetric function $f\in \operatorname {\mathrm {Sym}}$ (see, for instance, [Reference Haglund, Haiman, Loehr, Remmel and Ulyanov12] for details). Define the super-alphabet $\mathcal {A}=\mathbb {Z}^+\cup \mathbb {Z}^-=\{1,\bar 1,2,\bar 2,\ldots \}$ , where the elements of the usual alphabet $\mathbb {Z}^+=\{1,2,\ldots \}$ are referred to as the “positive” letters, and those of $\mathbb {Z}^-=\{\bar 1,\bar 2,\ldots \}$ as the “negative” letters. The total ordering on $\mathcal {A}\cup \{0,\infty \}$ is chosen to be:

$$\begin{align*}0<1<\bar1<2<\bar2<\cdots<\infty. \end{align*}$$

When standardizing a word in the alphabet $\mathcal {A}$ , ties between two equal letters are broken by saying the leftmost one is smaller if they are positive and the leftmost one is larger if they are negative. To make this precise, we introduce the notation $I(a,b)$ for any $a,b\in \mathcal {A}\cup \{0,\infty \}$ to generalize the notion of a descent on $\mathcal {A}\cup \{0,\infty \}$ with respect to the total ordering above:

$$\begin{align*}I(a,b)=\begin{cases} 1,&a>b\ \text{or}\ a=b\in\mathbb{Z}^-,\\ 0,&a<b\ \text{or}\ a=b\in\mathbb{Z}^+. \end{cases} \end{align*}$$

Note in particular that if $a\neq b$ , then $I(a,b)=\delta _{a>b}$ (where $\delta _F$ is the truth function that outputs 1 if F is true and 0 otherwise). Otherwise, we have $I(a,a)=0$ and $I(\bar a,\bar a)=1$ for any $a\in \mathbb {Z}^+$ . For example, $I(1,2)=I(\bar 1,\bar 2)=I(2,\bar 2)=I(1,1)=I(1,\infty )=0$ and $I(2,1)=I(\bar 2,2)=I(\bar 2,\bar 2)=I(1,0)=1$ .

The notation $I(a,b)$ allows us to extend the definitions of the major index, $\operatorname {\mathrm {\texttt {inv}}}$ , and $\operatorname {\mathrm {\texttt {quinv}}}$ to super fillings. Let $\sigma :\operatorname {\mathrm {\texttt {dg}}}(\lambda )\rightarrow \mathcal {A}$ , and define

$$\begin{align*}{{\texttt{maj}}}(\sigma)=\sum_{\substack{u\in{{\texttt{dg}}}(\lambda)\\I(\sigma(u),\sigma({\mathrm{South}}(u))=1}} {{\texttt{leg}}}(u)+1. \end{align*}$$

For $a,b,c\in \mathcal {A}\cup \{0,\infty \}$ , we say $\mathcal {Q}(a,b,c)=0$ if and only if exactly one of the following is true:

$$\begin{align*}\{I(a,b)=1, I(c,b)=0, I(a,c)=0\}. \end{align*}$$

Note that it is impossible for all three to be true, so if more than one is true, $\mathcal {Q}(a,b,c)=1$ . When $\sigma =|\sigma |$ , this definition coincides with the inequalities in (2.4), and thus characterizes $\operatorname {\mathrm {\texttt {inv}}}(\sigma )$ and $\operatorname {\mathrm {\texttt {quinv}}}(\sigma )$ when $\sigma $ is a super filling.

Definition 2.7. Let X and Y be two alphabets. The superization of a symmetric function $f(X)$ is

$$\begin{align*}\widetilde{f}(X,Y) := f[X-\varepsilon Y].\end{align*}$$

In particular, we have

(2.5) $$ \begin{align} f[X(t-1);q,t]= f[tX-\varepsilon X;q,t]=\widetilde{f}(tX,\varepsilon X;q,t). \end{align} $$

Due to [Reference Haglund, Haiman and Loehr10, Proposition 4.3], if

$$\begin{align*}f(X;q,t)=\sum_{\sigma:{{\texttt{dg}}}(\lambda)\rightarrow \mathbb{Z}^+}q^{{{\texttt{maj}}}(\sigma)}t^{\iota(\sigma)}x^{\sigma},\end{align*}$$

where $\iota (\sigma )$ can be either $\operatorname {\mathrm {\texttt {inv}}}(\sigma )$ or $\operatorname {\mathrm {\texttt {quinv}}}(\sigma )$ , one obtains a formula for its superization $\widetilde {f}(X,Y)=f[X-\varepsilon Y]$ as a generating function over super fillings $\sigma :\operatorname {\mathrm {\texttt {dg}}}(\lambda )\rightarrow \mathcal {A}$ :

(2.6) $$ \begin{align} \widetilde{f}(X,Y;q,t)=\sum_{\sigma:{{\texttt{dg}}}(\lambda)\rightarrow \mathcal{A}}q^{{{\texttt{maj}}}(\sigma)}t^{\iota(\sigma)}z^{\sigma} \end{align} $$

where $z_i=x_i$ if $i\in \mathbb {Z}^+$ and $z_i=y_i$ if $i\in \mathbb {Z}^-$ .

Rearranging (2.2) for $J_{\lambda }(X;q,t)$ , we get

(2.7) $$ \begin{align} J_{\lambda}(X;q,t)&=t^{n(\lambda)}\widetilde{H}_{\lambda}[X(1-t);q,t^{-1}]=t^{n(\lambda)+n}\widetilde{H}_{\lambda}[X(t^{-1}-1);q,t^{-1}]. \end{align} $$

As detailed in [Reference Haglund, Haiman and Loehr10, Lemma 5.2] and [Reference Ayyer, Mandelshtam and Martin2, Section 3], (2.6) and (2.5) imply, respectively,

(2.8) $$ \begin{align} \widetilde{H}_{\lambda}[X(t-1);q,t] &= \sum_{\sigma:{{\texttt{dg}}}(\lambda)\rightarrow \mathcal{A}}(-1)^{m(\sigma)}q^{{{\texttt{maj}}}(\sigma)}t^{p(\sigma)+{{\texttt{inv}}}(\sigma)}x^{|\sigma|},\end{align} $$

(2.9) $$ \begin{align} &= \sum_{\sigma:{{\texttt{dg}}}(\lambda)\rightarrow\mathcal{A}}(-1)^{m(\sigma)}q^{{{\texttt{maj}}}(\sigma)}t^{p(\sigma)+{{\texttt{quinv}}}(\sigma)}x^{|\sigma|}. \end{align} $$

These compress to formulas for $J_{\lambda }$ in terms of $\operatorname {\mathrm {\texttt {inv}}}$ - and $\operatorname {\mathrm {\texttt {quinv}}}$ -non-attacking super fillings, respectively:

(2.10) $$ \begin{align} J_{\lambda}(X;q,t) &= t^{n(\lambda)+n} \sum_{\substack{\sigma:{{\texttt{dg}}}(\lambda)\rightarrow \mathcal{A}\\|\sigma| {\mathrm{inv-non-attacking}}}}(-1)^{m(\sigma)}q^{{{\texttt{maj}}}(\sigma)}t^{-p(\sigma)-{{\texttt{inv}}}(\sigma)}x^{|\sigma|}, \end{align} $$

(2.11) $$ \begin{align} &= t^{n(\lambda)+n} \sum_{\substack{\sigma:{{\texttt{dg}}}(\lambda)\rightarrow \mathcal{A}\\|\sigma| {\mathrm{quinv-non-attacking}}}}(-1)^{m(\sigma)}q^{{{\texttt{maj}}}(\sigma)}t^{-p(\sigma)-{{\texttt{quinv}}}(\sigma)}x^{|\sigma|}.\end{align} $$

In [Reference Haglund, Haiman and Loehr10, Section 8], it is shown how to further compress (2.10) to obtain (2.3) by grouping together and evaluating the total contribution of all super fillings that have the same absolute value to obtain the HHL tableaux formulas in terms of $\operatorname {\mathrm {\texttt {inv}}}$ -non-attacking tableaux. In [Reference Mandelshtam, Orr and Wen18], an analogous strategy is used to compress (2.11) to obtain the following formulas in terms of $\operatorname {\mathrm {\texttt {quinv}}}$ -non-attacking tableaux.

Theorem 2.8 [Reference Mandelshtam, Orr and Wen18, Theorem 5.3]

The symmetric Macdonald polynomial $P_{\lambda }(X;q,t)$ is given by

(2.12) $$ \begin{align} P_{\lambda}(X;q,t) = \frac{1}{{\mathrm{perm}}_{\lambda}(t)}\hspace{-0.2in}\sum_{\substack{\sigma:{{\texttt{dg}}}(\lambda)\rightarrow\mathbb{Z}^+\\\sigma\,{\mathrm{quinv-non-attacking}}}}\hspace{-0.2in}q^{{{\texttt{maj}}}(\sigma)}t^{{{\texttt{coquinv}}}(\sigma)} x^{\sigma}\hspace{-0.2in} \prod_{\substack{u,~{\mathrm{South}}(u)\in{{\texttt{dg}}}(\lambda)\\\sigma(u)\neq\sigma({\mathrm{South}}(u))}}\frac{1-t}{1-q^{{{\texttt{leg}}}(u)+1}t^{{\mathrm{\widehat{\texttt{arm}}}}(u)+1}}. \end{align} $$

Remark 2.10. In comparing (2.12) to (2.3), one notices the absence of the prefactor $\widetilde {\operatorname {\mathrm {PR}}}_{\lambda }(q,t)/\operatorname {\mathrm {PR}}_{\lambda }(q,t)$ . This comes from the fact that

(2.13) $$ \begin{align} {\mathrm{PR}}_{\lambda}(q,t)=\prod_{u\in{{\texttt{dg}}}(\lambda)}(1-q^{{{\texttt{leg}}}(u)}t^{{{\texttt{arm}}}(u)+1})={\mathrm{perm}}_{\lambda}(t)\prod_{u\in\overline{{{\texttt{dg}}}}(\lambda)}(1-q^{{{\texttt{leg}}}(u)+1}t^{{\mathrm{\widehat{\texttt{arm}}}}(u)+1}), \end{align} $$

and so all terms of the form $(1-q^{\ell }t^a)$ in the numerator are cancelled in the product $P_{\lambda }(X;q,t)=\operatorname {\mathrm {PR}}_{\lambda }(q,t)^{-1}J_{\lambda }(X;q,t)$ when the $\operatorname {\mathrm {\texttt {quinv}}}$ and $\widehat {\texttt {arm}}$ statistics are used.

As a corollary we obtain a (co)quinv formula for the integral form $J_{\lambda }(X;q,t)$ .

(2.14) $$ \begin{align} J_{\lambda}(X;q,t)=\hspace{-0.4in}\sum_{\substack{\sigma:{{\texttt{dg}}}(\lambda)\rightarrow\mathbb{Z}^+\\\sigma\,{\mathrm{quinv-non-attacking}}}}\hspace{-0.3in}q^{{{\texttt{maj}}}(\sigma)}t^{{{\texttt{coquinv}}}(\sigma)} x^{\sigma}\hspace{-0.2in} \prod_{\substack{u\in\overline{{{\texttt{dg}}}}(\lambda)\\\sigma(u)=\sigma({\mathrm{South}}(u))}}\hspace{-0.3in}(1-q^{{{\texttt{leg}}}(u)+1}t^{{\mathrm{\widehat{\texttt{arm}}}}(u)+1})\hspace{-0.2in}\prod_{\substack{u\in{{\texttt{dg}}}(\lambda)\\\sigma(u)\neq\sigma({\mathrm{South}}(u))}}\hspace{-0.3in}(1-t). \end{align} $$

It should be noted that the first product is over cells $u\in \overline {\operatorname {\mathrm {\texttt {dg}}}}(\lambda )$ above the bottom row, while the second product is over all cells $u\in \operatorname {\mathrm {\texttt {dg}}}(\lambda )$ , accounting for all necessary factors of $(1-t)$ .

Noting the prefactor $\operatorname {\mathrm {perm}}_{\lambda }(t)^{-1}$ in the formula (2.12), in [Reference Mandelshtam, Orr and Wen18] we conjectured the compact formula (1.3), which uses $\operatorname {\mathrm {\texttt {coquinv}}}$ -sorted $\operatorname {\mathrm {\texttt {quinv}}}$ -non-attacking fillings, and thereby eliminates this prefactor. We prove this conjecture in Section 3.

Example 2.11. We compute $P_{2,2}(X;q,t)$ using Theorem 1.1 to get

$$\begin{align*}P_{(2,2)}(X;q,t) = m_{22}+\frac{(1+q)(1-t)}{1-qt}m_{211}+ \frac{(2+t+3q+q^2+3qt+2q^2t)(1-t)^2}{(1-qt)(1-qt^2)}m_{1111}. \end{align*}$$

The common factor of $\frac {(1-t)^2}{(1-qt)(1-qt^2)}$ was left out from the weights of the fillings for $m_{1111}$ .

2.5 Compact formulas for $\widetilde {H}_{\lambda }$ via inv-flip and quinv-flip operators $\tau _j$ and $\rho _j$

Definition 2.12. Let $\lambda =\langle 1^{m_1}2^{m_2}\cdots k^{m_k}\rangle $ be a partition. We define $\operatorname {\mathrm {perm}}_{\lambda }(t)$ to be the t-analog of the stabilizer of $\lambda $ in $S_{\ell (\lambda )}$ :

$$\begin{align*}{\mathrm{perm}}_{\lambda}(t):=[m_1]_t!\cdots [m_k]_t! \end{align*}$$

where $[k]_t:=1+\cdots +t^{k-1}$ and $[k]_t!:=[k]_t[k-1]_t\cdots [1]_t$ .

We generalize the above to define $\operatorname {\mathrm {perm}}(\sigma )$ where $\sigma $ is a filling of a partition shape.

Definition 2.13. Let $\sigma ^{(i)}$ be a filling of a $m\times i$ rectangular diagram (m columns of length i) such that there are k distinct columns with multiplicities $\{m_1,\ldots ,m_k\}$ , so that $m_1+\cdots +m_k=m$ . We define the statistic $\operatorname {\mathrm {perm}}(\sigma ^{(i)})$ to be the inversion generating function of a word in the letters $\langle 1^{m_1}\cdots k^{m_k}\rangle $ :

$$\begin{align*}{\mathrm{perm}}(\sigma^{(i)}) = {m \brack m_1,\ldots,m_k}_t:=\frac{[m]_t!}{[m_1]_t!\cdots[m_k]_t!}. \end{align*}$$

Then, for a filling $\sigma :\operatorname {\mathrm {\texttt {dg}}}(\lambda )\rightarrow \mathbb {Z}^+$ , for $1\leq i\leq \lambda _1$ , let $\sigma ^{(i)}$ be the (possibly empty) rectangular block consisting of the columns of height i of $\sigma $ (per convention, $\operatorname {\mathrm {perm}}(\emptyset )=1$ ). Define

$$\begin{align*}{\mathrm{perm}}(\sigma) = \prod_{i=1}^{\lambda_1} {\mathrm{perm}}(\sigma^{(i)}). \end{align*}$$

Described in another way, $\operatorname {\mathrm {perm}}(\sigma )$ is the t-analog of the number of distinct ways of permuting the columns of $\sigma $ within the shape $\operatorname {\mathrm {\texttt {dg}}}(\lambda )$ .

In particular, if $\sigma $ is a ( $\operatorname {\mathrm {\texttt {inv}}}$ or $\operatorname {\mathrm {\texttt {quinv}}}$ ) non-attacking filling of $\operatorname {\mathrm {\texttt {dg}}}(\lambda )$ , all of its columns are necessarily distinct, and so $\operatorname {\mathrm {perm}}(\sigma )=\operatorname {\mathrm {perm}}_{\lambda }(t)$ .

Example 2.14. We compute $\operatorname {\mathrm {perm}}(\sigma )$ for the tableau $\sigma $ from Example 2.5. There are two distinct columns of height 1, each appearing twice, so the multiplicities are $\{2,2\}$ and thus

$$\begin{align*}{\mathrm{perm}}(\sigma^{(1)})={4\brack 2,2}_t=[4]_t[3]_t/[2]_t.\end{align*}$$

For height 2, there are three columns with multiplicities $\{2,1\}$ , giving

$$\begin{align*}{\mathrm{perm}}(\sigma^{(2)})={3\brack 2,1}_t=[3]_t.\end{align*}$$

Finally, for height 3, there are two distinct columns with multiplicities $\{1,1\}$ , so

$$\begin{align*}{\mathrm{perm}}(\sigma^{(3)})={2\brack 1,1}_t=[2]_t.\end{align*}$$

Thus $\operatorname {\mathrm {perm}}(\sigma ) =\prod _i\operatorname {\mathrm {perm}}(\sigma ^{(i)})=[4]_t[3]_t^2$ .

By choosing a canonical way of sorting columns of equal height in a filling, the formulas (1.1) and (1.2) for $\widetilde {H}_{\lambda }$ can be written more compactly. This was first done in [Reference Corteel, Haglund, Mandelshtam, Mason and Williams5, Theorem 3.5] for the $\operatorname {\mathrm {\texttt {inv}}}$ formula and was later replicated in [Reference Mandelshtam, Orr and Wen18, Theorem 4.2] for the $\operatorname {\mathrm {\texttt {quinv}}}$ analog.

Theorem 2.15. The modified Macdonald polynomial can be obtained as

(2.15) $$ \begin{align} \widetilde{H}_{\lambda}(X;q,t)& = \sum_{\substack{\sigma:{{\texttt{dg}}}(\lambda)\rightarrow\mathbb{Z}^+\\\sigma\,{\mathrm{inv-sorted}}}} {\mathrm{perm}}(\sigma)x^{\sigma}q^{{{\texttt{maj}}}(\sigma)}t^{{{\texttt{inv}}}(\sigma)}, \end{align} $$

(2.16) $$ \begin{align} &= \sum_{\substack{\sigma:{{\texttt{dg}}}(\lambda)\rightarrow\mathbb{Z}^+\\\sigma\,{\mathrm{quinv-sorted}}}} {\mathrm{perm}}(\sigma)x^{\sigma}q^{{{\texttt{maj}}}(\sigma)}t^{{{\texttt{quinv}}}(\sigma)}. \end{align} $$

where the first sum is over $\operatorname {\mathrm {\texttt {inv}}}$ -sorted fillings and the second sum is over $\operatorname {\mathrm {\texttt {quinv}}}$ -sorted fillings according to Definition 2.19.

We outline the strategy for proving Theorem 2.15 as a warm-up for the proof of Theorem 1.1.

2.5.1 The operators $\tau _i$ and $\rho _i$

The operator $\tau _i$ was introduced in [Reference Loehr and Niese16] to act on fillings as an inversion flip operator, characterized by the following properties: it preserves the content and the major index, and when it acts nontrivially, it changes the number of inversions by exactly 1.

For a partition $\lambda $ , we say $1\leq i\leq \ell (\lambda )$ is $\lambda $ -compatible if $\lambda _i=\lambda _{i+1}$ . We say that a transposition $s_i$ is $\lambda $ -compatible if the index i is $\lambda $ -compatible. Moreover, we call two indices $i<j \lambda $ -comparable if $\lambda _i=\lambda _j$ .

For a word $w = w_1 w_2 \cdots w_k \in \mathbb {Z}_{>0}^k$ , the left action of the simple transposition $s_i \in S_k$ (for $1 \le i < k$ ) is defined by swapping the entries at positions i and $i+1$ :

$$\begin{align*}s_i \cdot w = w_1 \cdots w_{i-1} w_{i+1} w_i w_{i+2} \cdots w_k. \end{align*}$$

Then, we define the set of $\lambda $ -compatible permutations of w, denoted $\operatorname {\mathrm {Sym}}_{\lambda }(w)$ , to be the set of words obtained by applying a sequence of $\lambda $ -compatible transpositions to w (applied from right to left):

$$\begin{align*}{\mathrm{Sym}}_{\lambda}(w)=\{w'\in\mathbb{Z}_{>0}^k:w'=s_{i_u}\cdots s_{i_1}\cdot w,\ \text{with each } s_{i_j}\ \lambda\text{-compatible for} 1\leq j\leq u\}. \end{align*}$$

For a filling $\sigma $ of $\operatorname {\mathrm {\texttt {dg}}}(\lambda )$ and $\lambda $ -compatible i, define the operator $\mathfrak {t}_i^{(r)}$ to act on $\sigma $ by swapping the entries of the squares $(r,i)$ and $(r,i+1)$ . For $1\leq r,s\leq \lambda _i$ , the compact notation $\mathfrak {t}_i^{[r,s]}:=\mathfrak {t}_i^{(r)}\circ \mathfrak {t}_i^{(r+1)}\circ \cdots \circ \mathfrak {t}_i^{(s)}$ represents a sequence of swaps of entries in consecutive rows between the same pair of adjacent columns. Note that since the $\mathfrak {t}_i^{(r)}$ ’s act on rows independently, they commute, and so $\mathfrak {t}_i^{[r,s]}=\mathfrak {t}_i^{[s,r]}$ . See Example 2.16.

Example 2.16. For example, when $\lambda =(3,3,3,2,2)$ , the $\lambda $ -compatible indices are $\{1,2,4\}$ . For $\sigma $ below, we compute $\mathfrak {t}_2^{[2,3]}(\sigma )$ , $\mathfrak {t}_4^{(2)}(\sigma )$ , and $\mathfrak {t}_4^{[1,2]}(\sigma )$ , with the swapped entries shown in bold:

Definition 2.17 (The operator $\tau _i$ )

For a partition $\lambda $ and a $\lambda $ -compatible index i, let $\sigma :\operatorname {\mathrm {\texttt {dg}}}(\lambda )\rightarrow \mathbb {Z}^+$ . If columns i and $i+1$ are identical in $\sigma $ , $\tau _i(\sigma )=\sigma $ . Otherwise, let $\ell '$ be minimal such that $\sigma (\ell ',i)\neq \sigma (\ell ',i+1)$ , and let $\ell '\geq h'\leq \lambda _i$ be minimal such that $\mathcal {Q}(\sigma (h'+1,i),\sigma (h',i),\sigma (h'+1,i+1))=\mathcal {Q}(\sigma (h'+1,i+1),\sigma (h',i),\sigma (h'+1,i+1))$ , where per convention, $\sigma (\lambda _i+1,i)=0$ for all i. Then $\tau _i(\sigma )=\mathfrak {t}_i^{[\ell ',h']}(\sigma )$ , swapping the entries in rows $\ell '$ through $h'$ between columns i and $i+1$ , while keeping all other entries unchanged. See Example 2.20.

In [Reference Ayyer, Mandelshtam and Martin2], we defined analogous operators for the $\operatorname {\mathrm {\texttt {quinv}}}$ statistic. These operators were also originally called $\tau _i$ , but we shall assign to them the new name $\rho _i$ to distinguish from the original $\tau _i$ ’s.

Definition 2.18 (The operators $\rho _i$ )

For a partition $\lambda $ and a $\lambda $ -compatible index i, let $\sigma :\operatorname {\mathrm {\texttt {dg}}}(\lambda )\rightarrow \mathbb {Z}^+$ . If columns i and $i+1$ are identical in $\sigma $ , $\rho _i(\sigma )=\sigma $ . Otherwise, let $\ell $ be maximal such that $\sigma (\ell ,i)\neq \sigma (\ell ,i+1)$ , and let $1\geq h\leq \ell $ be maximal such that $\mathcal {Q}(\sigma (h,i),\sigma (h-1,i),\sigma (h-1,i+1))=\mathcal {Q}(\sigma (h,i+1),\sigma (h-1,i),\sigma (h-1,i+1))$ where per convention, $\sigma (0,i)=\infty $ for all i. Then $\rho _i(\sigma )=\mathfrak {t}_i^{[h,\ell ]}(\sigma )$ , swapping the entries in rows h through $\ell $ between columns i and $i+1$ , while keeping all other entries unchanged. See Example 2.20.

Another description of $\rho _i$ , which will be useful for comparison to the definitions in Section 3, is as follows. Define $\rho _i(\sigma ):=\rho _i^{(\lambda _i)}(\sigma )$ , where the operator $\rho _i^{(r)}$ is defined recursively to act on $\sigma $ as follows based on the contents $a=\sigma (r,i)$ , $b=\sigma (r,i+1)$ , $c=\sigma (r-1,i)$ , $d=\sigma (r-1,i+1)$ in the configuration

1. i. If $\sigma (r,i)=\sigma (r,i+1)$ , $\rho _i^{(r)}(\sigma )=\rho _i^{(r-1)}(\sigma )$ .

2. ii. Otherwise, if $\mathcal {Q}(a,c,d)=\mathcal {Q}(b,c,d)$ , $\rho _i^{(r)}(\sigma )=\mathfrak {t}_i^{(r)}(\sigma )$ , and

3. iii. If $\mathcal {Q}(a,c,d)=\mathcal {Q}(b,c,d)$ , $\rho _i^{(r)}(\sigma )=\rho _i^{(r-1)}(\mathfrak {t}_i^{(r)}(\sigma ))$ .

The intuition behind this definition is that $\rho _i$ scans the rows of $\sigma $ in columns $i,i+1$ from top to bottom, swaps the first pair of differing entries between the two columns (which changes the contribution to $\operatorname {\mathrm {\texttt {quinv}}}$ from the affected L-triple by $\pm 1$ ), and then sequentially swaps the entries in the rows below to prevent any additional changes to $\operatorname {\mathrm {\texttt {quinv}}}$ coming from the L-triples in the rows below. There is a similar recursive definition for $\tau _i$ , which we will omit.

Definition 2.19. For a partition $\lambda $ , we say $\sigma :\operatorname {\mathrm {\texttt {dg}}}(\lambda )\rightarrow \mathbb {Z}^+$ is $\operatorname {\mathrm {\texttt {inv}}}$ -sorted if $\operatorname {\mathrm {\texttt {inv}}}(\sigma )\leq \operatorname {\mathrm {\texttt {inv}}}(\tau _i(\sigma ))$ for any $\lambda $ -compatible i. If $\sigma $ is $\operatorname {\mathrm {\texttt {inv}}}$ -non-attacking, we say it is $\operatorname {\mathrm {\texttt {coinv}}}$ -sorted if and only if every pair of adjacent entries in the bottom-row cells $(1,i),(1,i+1)$ for $\lambda $ -compatible i is increasing from left to right (meaning that $\operatorname {\mathrm {\texttt {coinv}}}(\sigma )\leq \operatorname {\mathrm {\texttt {coinv}}}(\tau _i(\sigma ))$ ). Analogously, we say $\sigma $ is $\operatorname {\mathrm {\texttt {quinv}}}$ -sorted if $\operatorname {\mathrm {\texttt {quinv}}}(\sigma )\leq \operatorname {\mathrm {\texttt {quinv}}}(\rho _i(\sigma ))$ for any $\lambda $ -compatible i. If $\sigma $ is $\operatorname {\mathrm {\texttt {quinv}}}$ -non-attacking, we say it is $\operatorname {\mathrm {\texttt {coquinv}}}$ -sorted if and only if every pair of topmost adjacent entries $(\lambda _i,i),(\lambda _{i},i+1)$ for $\lambda $ -compatible i is increasing from left to right (meaning that $\operatorname {\mathrm {\texttt {coquinv}}}(\sigma )\leq \operatorname {\mathrm {\texttt {coquinv}}}(\tau _i(\sigma ))$ ). See Example 2.21.

Example 2.20. Suppose $\sigma $ has columns $i,i+1$ as shown below, with $\lambda _i=6$ . For $\tau _i(\sigma )$ , we have $\ell '=1$ , and $h'=2$ , since applying $\mathfrak {t}_i^{(2)}$ changes the triple at rows $h',h'+1$ from to , which is not an $\operatorname {\mathrm {\texttt {inv}}}$ triple in both cases. For $\rho _i(\sigma )$ , we have $\ell =5$ , and $h=3$ , since applying $\mathfrak {t}_i^{(3)}$ changes the triple at rows $h,h-1$ from to , which is a $\operatorname {\mathrm {\texttt {quinv}}}$ triple in both cases.

Example 2.21. We show an $\operatorname {\mathrm {\texttt {inv}}}$ -sorted tableau $\sigma _1$ , a $\operatorname {\mathrm {\texttt {coinv}}}$ -sorted $\operatorname {\mathrm {\texttt {inv}}}$ -non-attacking tableau $\sigma _2$ , a $\operatorname {\mathrm {\texttt {quinv}}}$ -sorted tableau $\sigma _3$ , and a $\operatorname {\mathrm {\texttt {coquinv}}}$ -sorted $\operatorname {\mathrm {\texttt {quinv}}}$ -non-attacking tableau $\sigma _4$ :

The following lemma establishes the key properties of the $\tau _i$ ’s and the $\rho _i$ ’s, which are to preserve the $\operatorname {\mathrm {\texttt {coinv}}}$ and change the $\operatorname {\mathrm {\texttt {inv}}}$ and $\operatorname {\mathrm {\texttt {quinv}}}$ , respectively, in a controlled way.

Lemma 2.22 [Reference Corteel, Haglund, Mandelshtam, Mason and Williams5, Lemmas 3.9, 3.10, 3.11] and [Reference Ayyer, Mandelshtam and Martin2, Lemmas 7.5 and 7.6]

Let $\lambda $ be a partition, let i be $\lambda $ -compatible and let $\sigma :\operatorname {\mathrm {\texttt {dg}}}(\lambda )\rightarrow \mathbb {Z}^+$ .

1. i. $\tau _i$ and $\rho _i$ are involutions.

2. ii. If columns $i,i+1$ of $\sigma $ are not identical, then $\operatorname {\mathrm {\texttt {inv}}}(\tau _i(\sigma ))=\operatorname {\mathrm {\texttt {quinv}}}(\sigma )\pm 1$ and $\operatorname {\mathrm {\texttt {quinv}}}(\rho _i(\sigma ))=\operatorname {\mathrm {\texttt {quinv}}}(\sigma )\pm 1$ .

3. iii. $\operatorname {\mathrm {\texttt {maj}}}(\tau _i(\sigma ))=\operatorname {\mathrm {\texttt {maj}}}(\rho _i(\sigma ))= \operatorname {\mathrm {\texttt {maj}}}(\sigma )$ .

The formula (2.15) is proved in [Reference Corteel, Haglund, Mandelshtam, Mason and Williams5] by using the $\tau _i$ ’s to generate the entire set of fillings ${\sigma :\operatorname {\mathrm {\texttt {dg}}}(\lambda )\rightarrow \mathbb {Z}^+}$ from the set of $\operatorname {\mathrm {\texttt {inv}}}$ -sorted fillings, so that each $\operatorname {\mathrm {\texttt {inv}}}$ -sorted tableau $\nu $ generates a set of fillings with total weight equal to $x^{\nu }t^{\operatorname {\mathrm {\texttt {inv}}}(\nu )}q^{\operatorname {\mathrm {\texttt {maj}}}(\nu )}\operatorname {\mathrm {perm}}(\nu )$ . Similarly, (2.16) is proved in [Reference Mandelshtam, Orr and Wen18] following an identical strategy, by generating the entire set of fillings $\sigma :\operatorname {\mathrm {\texttt {dg}}}(\lambda )\rightarrow \mathbb {Z}^+$ from applying $\rho _i$ ’s to the set of $\operatorname {\mathrm {\texttt {quinv}}}$ -sorted fillings, so that each $\operatorname {\mathrm {\texttt {quinv}}}$ -sorted tableau $\nu $ generates a set of fillings with total weight equal to $x^{\nu }t^{\operatorname {\mathrm {\texttt {quinv}}}(\nu )}q^{\operatorname {\mathrm {\texttt {maj}}}(\nu )}\operatorname {\mathrm {perm}}(\nu )$ . We need one final technical definition to execute these strategies.

2.5.2 Positive distinguished subexpressions

Using the fact that the symmetric group $S_{\ell }$ is generated by simple transpositions $\{s_1,\ldots ,s_{\ell -1}\}$ , we can use compositions of $\tau _i$ ’s or $\rho _i$ ’s to generate the set of all possible $\lambda $ -compatible permutations of the columns of a given filling $\sigma $ of $\operatorname {\mathrm {\texttt {dg}}}(\lambda )$ where $\ell =\ell (\lambda )$ . Unfortunately, in general, neither the $\tau _i$ ’s nor the $\rho _i$ ’s satisfy braid relations. Thus one must choose a canonical way to compose sequences of $\tau _i$ ’s (resp. $\rho _i$ ’s) to that each filling in $\operatorname {\mathrm {\texttt {dg}}}(\lambda )\rightarrow \mathbb {Z}^+$ is generated by a unique $\operatorname {\mathrm {\texttt {inv}}}$ -sorted (resp. $\operatorname {\mathrm {\texttt {quinv}}}$ -sorted) filling via a well-defined sequence of operators. This is done for the $\tau _j$ ’s using positive distinguished subexpressions (PDS) in [Reference Corteel, Haglund, Mandelshtam, Mason and Williams5, Section 3.2].

The notion of a PDS of a reduced expression originates from [Reference Marsh and Rietsch19]. For a fixed n, the corresponding set of PDS is a subset of the reduced words generated by the simple transpositions $\{s_1,\ldots ,s_{n-1}\}$ , which forms a spanning tree on the Bruhat lattice. In other words, for any permutation $\pi \in S_n$ , the PDS $s_{i_k}\cdots s_{i_1}$ corresponding to $\pi $ is the reduced word coming from the unique path from the identity permutation $id$ to $\pi $ on this spanning tree, so that $\pi =s_{i_k}\cdots s_{i_1}\circ id$ . There is not a unique choice for the set of PDS, but for the sake of concreteness, we will use the same set of PDS as is described in [Reference Corteel, Haglund, Mandelshtam, Mason and Williams5, Section 3.2], which we present in the following definition.

Definition 2.23. Fix n and let $w_0=(n,n-1,\ldots ,2,1)$ . Fix the reduced expression for $w_0$ to be $w_0=s_1(s_2s_1)\cdots (s_{n-1}\cdots s_2s_1)=s_{i_t},\ldots ,s_{i_1}$ (with $t={n\choose 2}$ ). For a permutation $\pi \in S_n$ , define $\operatorname {\mathrm {PDS}}(\pi )=v_t\cdots v_1$ where $v_j\in \{s_{i_j},e\}$ , defined as follows. For two permutations $\alpha ,\beta \in S_n$ , we write $\alpha <\beta $ if $\ell (\alpha )<\ell (\beta )$ . Set $v_{(0)}=\pi $ , and set

$$\begin{align*}v_{(j)}=\begin{cases} v_{(j-1)}s_{i_j}&\text{if}\ v_{(j-1)}s_{i_j}<v_{(j-1)}\\ v_{(j-1)}&\text{otherwise}.\end{cases} \end{align*}$$

Then $v_j=s_{i_j}$ if $v_{(j-1)}s_{i_j}<v_{(j-1)}$ and $v_j=e$ otherwise. Finally, for a permutation $\lambda $ , we define $\operatorname {\mathrm {PDS}}(\lambda ):=\{\operatorname {\mathrm {PDS}}(\alpha ):\alpha \cdot \lambda =\lambda \}$ to be the set of PDS corresponding to the $\lambda $ -compatible permutations. For a filling $\sigma $ of $\operatorname {\mathrm {\texttt {dg}}}(\lambda )$ , we define $\operatorname {\mathrm {PDS}}(\sigma )$ to be the subset of $\operatorname {\mathrm {PDS}}(\lambda )$ that corresponds to all possible permutations of the columns of $\sigma $ within the shape $\operatorname {\mathrm {\texttt {dg}}}(\lambda )$ .

Now let $\nu :\operatorname {\mathrm {\texttt {dg}}}(\lambda )\rightarrow \mathbb {Z}^+$ be a $\operatorname {\mathrm {\texttt {inv}}}$ -sorted (resp. $\operatorname {\mathrm {\texttt {quinv}}}$ -sorted filling). We shall define a family of tableaux $\{\tau _i\}\nu $ (resp. $\{\rho _i\}\nu $ ), generated by applying sequences of $\tau _i$ ’s (resp. $\rho _i$ ’s) corresponding to $\operatorname {\mathrm {PDS}}(\nu )$ , the set of $\nu $ -compatible PDS. Then,

(2.17) $$ \begin{align} \{\sigma:{{\texttt{dg}}}(\lambda)\rightarrow\mathbb{Z}^+\} = \biguplus_{\substack{\sigma:{{\texttt{dg}}}(\lambda)\rightarrow\mathbb{Z}^+\\\sigma\,{\mathrm{inv-sorted}}}} \{\tau_i\}\sigma=\biguplus_{\substack{\sigma:{{\texttt{dg}}}(\lambda)\rightarrow\mathbb{Z}^+\\\sigma\,{\mathrm{quinv-sorted}}}} \{\rho_i\}\sigma. \end{align} $$

If $\nu $ is a $\operatorname {\mathrm {\texttt {quinv}}}$ -sorted filling, let $\sigma =\rho _{i_k}\circ \cdots \circ \rho _{i_1}(\sigma )\in \{\rho _j\}\nu $ , where $s_{i_k}\cdots s_{i_1}\in \operatorname {\mathrm {PDS}}(\nu )$ . By Lemma 2.22, $\operatorname {\mathrm {\texttt {quinv}}}(\sigma )=t^k\operatorname {\mathrm {\texttt {quinv}}}(\nu )$ . (Morally, this sequence of operators is permuting the columns of $\nu $ by the permutation $s_{i_k}\cdots s_{i_1}$ .) The length (i.e., inversion) generating function of the set $\operatorname {\mathrm {PDS}}(\sigma )$ is precisely equal to $\operatorname {\mathrm {perm}}(\sigma )$ . Thus we obtain

$$\begin{align*}\sum_{\sigma\in\{\rho_j\}\nu}x^{\sigma}q^{{{\texttt{maj}}}(\sigma)}t^{{{\texttt{quinv}}}(\sigma)} = x^{\nu}q^{{{\texttt{maj}}}(\nu)}t^{{{\texttt{quinv}}}(\nu)}{\mathrm{perm}}(\nu).\end{align*}$$

A similar equality holds for $\nu $ that is $\operatorname {\mathrm {\texttt {inv}}}$ -sorted with $\tau _i$ replacing $\rho _i$ and $\operatorname {\mathrm {\texttt {inv}}}$ replacing $\operatorname {\mathrm {\texttt {quinv}}}$ above. Combined with (2.17), this proves Theorem 2.15.