Shape changing identities for permuted-basement nonsymmetric Macdonald polynomials
(Extended Abstract)
June 01, 2026
Abstract
Permuted-basement Macdonald polynomials \(E_\alpha^\sigma(\mathbf{x};q,t)\) are nonsymmetric generalizations of symmetric Macdonald polynomials that form a basis for the polynomial ring \(\mathbb{Q}(q,t)[\mathbf{x}]\) for each fixed \(\sigma\). There are combinatorial formulas for them as generating functions over composition-shaped non-attacking fillings. In this extended abstract, we bijectively prove identities for the relationship between \(E_\alpha^\sigma\), \(E_\alpha^{\sigma s_i}\), \(E_{s_i\alpha}^\sigma\), and \(E_{s_i\alpha}^{\sigma s_i}\). These identities correspond to two combinatorial operations on non-attacking fillings: (1) swapping adjacent entries in the basement, generalizing a result of Alexandersson (2019), and (2) swapping adjacent parts in the shape, which yields a straightening rule for expanding \(E_\alpha^\sigma\) in the polynomials \(\{E_{s_i\alpha}^\tau\}_\tau\).
1 Introduction↩︎
The nonsymmetric Macdonald polynomials \(E_\alpha(x_1, \ldots, x_n; q, t)\), indexed by weak compositions \(\alpha= \def\temp{\alpha_1,\ldots,\alpha_n}\ifx\temp\empty \varnothing \else \readlist\thecycle{\alpha_1,\ldots,\alpha_n} \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} \fi\), were introduced in [1]–[3] as a generalization of the symmetric Macdonald polynomials \(P_\lambda\). They are the monic eigenfunctions of the Cherednik–Dunkl operators and form a basis of the polynomial ring \(\mathbb{Q}(q, t)[x_1, \ldots, x_n]\).
The permuted-basement Macdonald polynomials \(E_\alpha^\sigma(x_1, \ldots, x_n; q, t)\), first defined by [4], introduce an additional level of indexing, pairing a weak composition \(\alpha\) with a permutation \(\sigma\in \mathscr{S}_{n}\). They are obtained from the nonsymmetric Macdonald polynomials by applying sequences of Demazure–Lusztig operators. Throughout, we fix \(n \in \mathbb{Z}_{\geq 0}\) and work in the ring \(\mathbb{Q}(q,t)[\mathbf{x}]\) where \(\mathbf{x}=x_1,\ldots,x_n\). All weak compositions \(\alpha\) are assumed to have \(n\) parts, and all permutations \(\sigma\) lie in \(\mathscr{S}_{n}\). For \(k \in \mathbb{Z}_{\geq 0}\), write \([k]\coloneq\{1,2,\ldots,k\}\).
There is a combinatorial interpretation for \(E_\alpha^\sigma\) as the generating function of non-attacking fillings of shape \(\alpha\) and basement \(\sigma\), due to [4] and as a generalization of [5]. Our main results are 1 3, which we prove using bijective arguments: for the former, we construct a probabilistic bijection on non-attacking fillings, and for the latter, we construct a pair of bijections on signed fillings.
Theorem 1. Let \(\alpha\) be a composition with \(\alpha_i=\alpha_{i+1}\) for some \(i\in[n-1]\). Then, \[E_{\alpha}^{\sigma}(\mathbf{x}; q, t) = E_{\alpha}^{\sigma s_i}(\mathbf{x}; q, t).\]
Remark 2. [6], Theorem 22 proves 1 for the case where \(\sigma_i = \sigma_{i+1} + 1\). We have not found an explicit reference for the result in full generality.
Theorem 3. Let \(\alpha\) be a composition with \(\alpha_i > \alpha_{i+1}\) for some \(i \in [n-1]\). Then, we have \[\label{eq:three32term} E_{\alpha}^{\sigma}(\mathbf{x}; q, t) = E_{s_i \alpha}^{\sigma s_i}(\mathbf{x}; q, t) + c_{i, \alpha, \sigma}(q, t) E_{s_i \alpha}^{\sigma}(\mathbf{x}; q, t),\tag{1}\] where \[c_{i, \alpha, \sigma}(q, t) =t^{\mathop{\mathrm{twinv}}(s_i \alpha, \sigma) - \mathop{\mathrm{twinv}}(\alpha, \sigma)} \frac{1 - t}{1 - q^{\mathop{\mathrm{leg}}(u) + 1} t^{\mathop{\mathrm{arm}}(u)}} \times \begin{cases} 1 & \sigma_i>\sigma_{i+1} \\ q^{\mathop{\mathrm{leg}}(u) + 1} t^{\mathop{\mathrm{arm}}(u)} & \sigma_i < \sigma_{i+1}\,,\end{cases}\] in which \(u = (i + 1, \alpha_{i+1} + 1) \in {\operatorname{dg}\ifx&&\else^{()}\fi}(s_i \cdot \alpha)\) and \[\mathop{\mathrm{twinv}}(\alpha, \sigma) = |\{(k, l) : k < l \text{ and } \alpha_k \geq \alpha_l \text{ and } \sigma_k < \sigma_l\}|.\]
Remark 4. [6], Proposition 17 proves 3 for the case where \(\sigma_i = \sigma_{i+1} + 1\). The specialization for \(q=0\) is proved in [7]. To the best of our knowledge, the identity 1 in the above generality is new.
Remark 5. In both identities with \(\sigma s_i\) in the basement, \(s_i\) acts on the right of \(\sigma\), swapping adjacent entries. This contrasts with the usual Demazure–Lusztig action \(T_i E_\alpha^\sigma=t^* E_\alpha^{s_i \sigma}\) (see [4]) where \(s_i\) acts on the left, and for \(\sigma=id\) yields the known identity [5]. Hence, our identities describe a new property for \(E_\alpha^\sigma\).
In 2, we introduce the polynomials \(E_\alpha^\sigma(\mathbf{x};q,t)\) as generating functions over non-attacking and signed fillings of composition shapes. We prove 1 in 3 with a probabilistic bijection, and 3 in 4 using a \({\operatorname{maj}\ifx&&\else^{()}\fi}\)/\({\operatorname{inv}\ifx&&\else^{()}\fi}\)-preserving column-swapping bijection on signed fillings. We conclude in 5 with a straightening rule giving the coefficients in the expansion of \(E_\alpha^\sigma\) in the basis \(\{E_\beta^\tau\}\).
Acknowledgements.↩︎
We thank Per Alexandersson, Sarah Mason, and Arun Ram for helpful discussions, and thank Donghyun Kim for directing us to [8].
2 Preliminaries↩︎
A composition is a sequence \(\alpha = \def\temp{\alpha_1, \alpha_2, \ldots, \alpha_n}\ifx\temp\empty \varnothing \else \readlist\thecycle{\alpha_1, \alpha_2, \ldots, \alpha_n} \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} \fi\) of nonnegative integers. Define \(\mathop{\mathrm{rev}}(\alpha)= \def\temp{\alpha_n, \alpha_{n-1}, \ldots, \alpha_1}\ifx\temp\empty \varnothing \else \readlist\thecycle{\alpha_n, \alpha_{n-1}, \ldots, \alpha_1} \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} \fi\), \(\mathop{\mathrm{inc}}(\alpha)\) to be the weakly increasing rearrangement of the parts of \(\alpha\).
Given a permutation \(\pi \in \mathscr{S}_{n}\) and a composition \(\alpha\), the left action of \(\pi\) on \(\alpha\) is the composition \(\pi \cdot \alpha = \def\temp{\alpha_{\pi^{-1}(1)}, \alpha_{\pi^{-1}(2)}, \ldots, \alpha_{\pi^{-1}(n)}}\ifx\temp\empty \varnothing \else \readlist\thecycle{\alpha_{\pi^{-1}(1)}, \alpha_{\pi^{-1}(2)}, \ldots, \alpha_{\pi^{-1}(n)}} \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} \fi\). This choice of notation guarantees that \(\sigma \cdot (\pi \cdot \alpha) = (\sigma \pi) \cdot \alpha\) for all \(\sigma, \pi \in \mathscr{S}_{n}\). Note that \(\mathop{\mathrm{rev}}(\alpha) = w_0 \cdot \alpha\), where \(w_0 = \left[ \readlist\thecycle{n, n-1, \ldots, 1} \foreachitem\i\in\thecycle{\ifnum\icnt=1\else,\fi\i} \right]\). For permutations themselves, we use the usual product. In particular, \(\sigma s_i= \left[ \readlist\thecycle{\sigma_1,\ldots,\sigma_{i+1},\sigma_i,\ldots,\sigma_n} \foreachitem\i\in\thecycle{\ifnum\icnt=1\else,\fi\i} \right]\), that is, right multiplication by \(s_i\) swaps \(\sigma_i\) and \(\sigma_{i+1}\).
2.1 Combinatorial formulas for \(E_\alpha^\sigma(\mathbf{x};q,t)\)↩︎
The skyline diagram of a composition \(\alpha\) is the set \({\operatorname{dg}\ifx&&\else^{()}\fi}(\alpha) = \left\{ (i, r) \,:\, i \in [n] \text{ and } r \in [\alpha_i] \right\}\), where \((i,r)\) is a box in column \(i\) and row \(r\). The augmented skyline diagram is the set \(\mathop{\mathrm{\widehat{dg}}}(\alpha) = {\operatorname{dg}\ifx&&\else^{()}\fi}(\alpha) \cup \left\{ (i, 0) \,:\, i \in [n] \right\},\) where an zeroth row called the basement is added to the bottom of \({\operatorname{dg}\ifx&&\else^{()}\fi}(\alpha)\).
Let \(u = (i, r) \in {\operatorname{dg}\ifx&&\else^{()}\fi}(\alpha)\). The arm set of \(u\) is defined as \[\mathop{\mathrm{Arm}}(u) = \big\{ (j, r-1) \in \mathop{\mathrm{\widehat{dg}}}(\alpha) \,:\, j < i \text{ and } \alpha_{j} < \alpha_{i} \big\} \cup \big\{ (j, r) \in {\operatorname{dg}\ifx&&\else^{()}\fi}(\alpha) \,:\, j > i \text{ and } \alpha_{j} \leq \alpha_{i} \big\}.\] The leg statistic and arm statistic of \(u\) are defined as \(\mathop{\mathrm{leg}}(u) = \alpha_i-r\) and \(\mathop{\mathrm{arm}}(u) = \left|\mathop{\mathrm{Arm}}(u)\right|\). The box south of \(u = (i, r)\) is the box \(d(u) = (i, r-1) \in \mathop{\mathrm{\widehat{dg}}}(\alpha)\).
A box \(u = (i_u, r_u)\) attacks \(v = (i_v, r_v)\) in \({\operatorname{dg}\ifx&&\else^{()}\fi}(\alpha)\) if \(r_u = r_v\) and \(i_u < i_v\), that is, \(u\) and \(v\) are in the same row and \(u\) is to the left of \(v\); or \(r_v = r_u - 1\) and \(i_v < i_u\), that is, \(u\) is in the row directly above \(v\) and \(u\) is to the right of \(v\), as in one of the configurations below:
Figure 1: 
.
Figure 2: 
.
A non-augmented filling of shape \(\alpha\) is a map \(T \colon {\operatorname{dg}\ifx&&\else^{()}\fi}(\alpha) \to [n]\). An augmented filling of shape \(\alpha\) and basement \(\sigma \in \mathscr{S}_{n}\) is a map \(T \colon \mathop{\mathrm{\widehat{dg}}}(\alpha) \to [n]\) such that \(T(i, 0) = \sigma_i\) for all \(i \in [n]\). A filling \(T\), augmented or not, is non-attacking if \(T(u) \neq T(v)\) whenever box \(u\) attacks box \(v\). Let \(\mathop{\mathrm{F}}(\alpha, \sigma)\) and \(\mathop{\mathrm{NAF}}(\alpha, \sigma)\) denote the sets of fillings and non-attacking fillings, respectively, of shape \(\alpha\) with basement \(\sigma\).
The content of a filling \(T\) is the composition \(\beta= \def\temp{\beta_1, \beta_2, \ldots, \beta_n}\ifx\temp\empty \varnothing \else \readlist\thecycle{\beta_1, \beta_2, \ldots, \beta_n} \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} \fi\), where \(\beta_i = |\{u\in{\operatorname{dg}\ifx&&\else^{()}\fi}(\alpha) : T(u)=i\}|\). We write \(\mathbf{x}^T = x_1^{\beta_1} x_2^{\beta_2} \cdots x_n^{\beta_n}\). Let \(\mathop{\mathrm{NAF}}(\alpha, \sigma, \beta)\) denote the set of non-attacking fillings of shape \(\alpha\), basement \(\sigma\), and content \(\beta\).
Let \({\operatorname{Des}\ifx&&\else^{()}\fi}(T) = \{ u \in {\operatorname{dg}\ifx&&\else^{()}\fi}(\alpha) : T(u) > T(d(u)) \}\) be the set of descents in \(T\). The major index of \(T\) is \({\operatorname{maj}\ifx&&\else^{()}\fi}(T) = \sum_{u \in {\operatorname{Des}\ifx&&\else^{()}\fi}(T)} \left(\mathop{\mathrm{leg}}(u) + 1\right)\). See 3 for an example.
![Figure 3: A non-attacking augmented filling T of shape \alpha = \def\temp{2, 2, 0, 1}\ifx\temp\empty \varnothing \else \readlist\thecycle{2, 2, 0, 1} \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} \fi, basement \sigma = \left[ \readlist\thecycle{3, 1, 2, 4} \foreachitem\i\in\thecycle{\ifnum\icnt=1\else,\fi\i} \right], and \mathop{\mathrm{content}}(T) = \def\temp{1, 2, 0, 2}\ifx\temp\empty \varnothing \else \readlist\thecycle{1, 2, 0, 2} \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} \fi. The descents in T are shaded, with legs \mathop{\mathrm{leg}}(1,2)=\mathop{\mathrm{leg}}(2,2)=0 and \mathop{\mathrm{leg}}(2,1)=1. Thus, {\operatorname{maj}\ifx&&\else^{()}\fi}(T) = 1 + 1 + 2 = 4.](/article/2606.02395/_pdflatex/ceqvmsrt.png "fig:")
We define the inversion and coinversion statistics, following [5]. Given \(a, b \in [n]\), let \(\readlist\thecycle{a, b} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} } = 1\) if \(a > b\), and \(\readlist\thecycle{a, b} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} } = 0\) otherwise. Given \(a, b, c \in [n]\), define \(\readlist\thecycle{a, b, c} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} } = \readlist\thecycle{a, b} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} } + \readlist\thecycle{b, c} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} } - \readlist\thecycle{a, c} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} } \in \{0, 1\}\). A triple in \(\mathop{\mathrm{\widehat{dg}}}(\alpha)\) is a tuple \((u, v, w)\) of boxes such that \(v \in \mathop{\mathrm{Arm}}(u)\) and \(w = d(u)\). There are two possible configurations, shown in 4.
None
Figure 4: Configurations in which \((u, v, w)\) forms a triple..
A triple \((u, v, w)\) is an inversion (resp. coinversion) triple if \(\readlist\thecycle{T(u), T(v), T(w)} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} } = 1\) (resp. \(0\)), and \({\operatorname{inv}\ifx&&\else^{()}\fi}(T)\) (resp. \({\operatorname{coinv}\ifx&&\else^{()}\fi}(T)\)) denotes the number of such triples in \(T\).
Theorem 6 ([4]). The permuted-basement Macdonald polynomial is given by \[E^{\sigma}_{\alpha}(\mathbf{x}; q, t) = \mkern-15mu \sum_{T \in \mathop{\mathrm{NAF}}(\alpha, \sigma)} \mkern-15mu {\operatorname{wt}\ifx&&\else^{()}\fi}(T), \quad \text{where} \quad {\operatorname{wt}\ifx&&\else^{()}\fi}(T) = \mathbf{x}^T q^{{\operatorname{maj}\ifx&&\else^{()}\fi}(T)} t^{{\operatorname{coinv}\ifx&&\else^{()}\fi}(T)} \mkern-20mu \prod_{\substack{u \in {\operatorname{dg}\ifx&&\else^{()}\fi}(\alpha) \\ T(u) \neq T(d(u))}} \mkern-15mu \tfrac{1 - t}{1 - q^{1 + \mathop{\mathrm{leg}}(u)} t^{1 + \mathop{\mathrm{arm}}(u)}}.\]
Adapting the strategy in [9] for the symmetric Macdonald polynomials, we derive a formula for \(E_\alpha^\sigma\) in terms of signed fillings (also called superfillings).
We replace the alphabet \([n]\) with the signed alphabet \([n]_{\pm} = \{1 < \bar{1} < 2 < \bar{2} < \cdots < n < \bar{n}\}\), where \(\bar{i}\) denotes the negative of \(i\). For \(a, b \in [n]_{\pm}\), define \(|a|\) to be the unsigned value of \(a\), and define \(\readlist\thecycle{a, b} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} } = 1\) if \(a > b\) or \(a = b\) are negative, and \(\readlist\thecycle{a, b} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} } = 0\) otherwise. A signed augmented filling of shape \(\alpha\) and basement \(\sigma \in \mathscr{S}_{n}\) is a map \(T \colon \mathop{\mathrm{\widehat{dg}}}(\alpha) \to [n]_{\pm}\) such that \(T(i, 0) = \sigma_i\) for all \(i \in [n]\). We extend the definitions of descents, major index, triples, and coinversions to signed fillings by using the updated \(\readlist\thecycle{\cdot, \cdot} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} }\) function for comparisons between pairs of entries. Let \(\mathop{\mathrm{F}}_\pm(\alpha, \sigma)\) denote the set of signed augmented fillings of shape \(\alpha\) and basement \(\sigma\). For \(T\in\mathop{\mathrm{F}}_\pm(\alpha, \sigma)\), let \(|T|\in\mathop{\mathrm{F}}(\alpha, \sigma)\) be the filling obtained by taking the absolute value of each entry in \(T\), and let \(\operatorname{neg}(T)\) be the number of negative entries in \(T\). Let \(\mathop{\mathrm{NAF}}_\pm(\alpha, \sigma) = \{T \in \mathop{\mathrm{F}}_\pm(\alpha, \sigma) : |T| \in \mathop{\mathrm{NAF}}(\alpha, \sigma)\}\) denote the set of signed non-attacking fillings.
Lemma 1. The permuted-basement Macdonald polynomial is given by \[\label{eq:signed} E^{\sigma}_{\alpha}(\mathbf{x}; q, t) = \mkern-10mu \sum_{T \in \mathop{\mathrm{F}}_\pm(\alpha, \sigma)} \mkern-10mu {\operatorname{wt}\ifx&&\else^{()}\fi}_\pm(T), \quad \text{where} \quad {\operatorname{wt}\ifx&&\else^{()}\fi}_\pm(T) = \frac{\mathbf{x}^{|T|} q^{{\operatorname{maj}\ifx&&\else^{()}\fi}(T)} t^{{\operatorname{coinv}\ifx&&\else^{()}\fi}(T)} (-t)^{\operatorname{neg}(T)}}{\prod_{u \in {\operatorname{dg}\ifx&&\else^{()}\fi}(\alpha)} (1 - q^{1 + \mathop{\mathrm{leg}}(u)} t^{1 + \mathop{\mathrm{arm}}(u)})}.\tag{2}\]
Proof sketch. Adapting [9], there exists a \({\operatorname{wt}\ifx&&\else^{()}\fi}_\pm\)-sign-reversing involution on \(\mathop{\mathrm{F}}_\pm(\alpha, \sigma)\) with signed non-attacking fillings as fixed points. Thus, the right-hand side of 2 equals \(\sum_{T \in \mathop{\mathrm{NAF}}_\pm(\alpha, \sigma)} {\operatorname{wt}\ifx&&\else^{()}\fi}_\pm(T)\). We then group the signed non-attacking fillings \(T\) with equal \(|T|\), yielding a compact formula over unsigned non-attacking fillings. By noting that \({\operatorname{wt}\ifx&&\else^{()}\fi}(S) = \sum_{|T| = S} {\operatorname{wt}\ifx&&\else^{()}\fi}_\pm(T)\) for any \(S \in \mathop{\mathrm{NAF}}(\alpha, \sigma)\), we have that \(\sum_{T \in \mathop{\mathrm{NAF}}_\pm(\alpha, \sigma)} {\operatorname{wt}\ifx&&\else^{()}\fi}_\pm(T)\) equals the formula in 6. ◻
2.2 Probabilistic bijections↩︎
Probabilistic bijections, also referred to as bijectivization or coupling by [10], generalize weight-preserving bijections, and allow one to prove equalities of generating functions for combinatorial sets that either differ in cardinality, or do not admit a direct weight-preserving bijection. Our exposition follows [11].
Definition 1. Let \(A\) be an algebra. Let \(\mathbf{T}\) and \(\mathbf{U}\) be sets. A probability map from \(\mathbf{T}\) to \(\mathbf{U}\) is a function \(\operatorname{prob}_{} \colon \mathbf{T} \times \mathbf{U} \to A\) such that for every \(T \in \mathbf{T}\), we have \(\sum_{U \in\mathbf{U}} \operatorname{prob}_{}(T, U) = 1\).
Definition 2 (Probabilistic bijection [11]). Let \(A\) be an algebra. Let \(\mathbf{T}\) and \(\mathbf{U}\) be finite sets equipped with weight functions \({\operatorname{wt}\ifx&&\else^{()}\fi}_{\mathbf{T}} \colon \mathbf{T} \to A\) and \({\operatorname{wt}\ifx&&\else^{()}\fi}_{\mathbf{U}} \colon \mathbf{U} \to A\). A probabilistic bijection between \((\mathbf{T}, {\operatorname{wt}\ifx&&\else^{()}\fi}_{\mathbf{T}})\) and \((\mathbf{U}, {\operatorname{wt}\ifx&&\else^{()}\fi}_{\mathbf{U}})\) is a pair of probability maps \(\operatorname{prob}_{\mathbf{T}} \colon \mathbf{T} \times \mathbf{U} \to A\) and \(\operatorname{prob}_{\mathbf{U}} \colon \mathbf{U} \times \mathbf{T} \to A\) such that for every \(T \in \mathbf{T}\) and \(U \in \mathbf{U}\), we have \[{\operatorname{wt}\ifx&&\else^{()}\fi}_{\mathbf{T}}(T) \operatorname{prob}_{\mathbf{T}}(T, U) = {\operatorname{wt}\ifx&&\else^{()}\fi}_{\mathbf{U}}(U) \operatorname{prob}_{\mathbf{U}}(U, T).\]
Proposition 7. Let \(\operatorname{prob}_{\mathbf{T}} \colon \mathbf{T} \times \mathbf{U} \to A\) and \(\operatorname{prob}_{\mathbf{U}} \colon \mathbf{U} \times \mathbf{T} \to A\) form a probabilistic bijection between \((\mathbf{T}, {\operatorname{wt}\ifx&&\else^{()}\fi}_{\mathbf{T}})\) and \((\mathbf{U}, {\operatorname{wt}\ifx&&\else^{()}\fi}_{\mathbf{U}})\). Then, \[\sum_{T \in \mathbf{T}} {\operatorname{wt}\ifx&&\else^{()}\fi}(T) = \sum_{U \in\mathbf{U}} {\operatorname{wt}\ifx&&\else^{()}\fi}(U).\]
3 A probabilistic bijection for non-attacking fillings↩︎
Because of the complexity of the weight of a non-attacking filling, there is no ordinary weight-preserving bijection between \(\mathop{\mathrm{NAF}}(\alpha,\sigma)\) and \(\mathop{\mathrm{NAF}}(\alpha,\sigma s_i)\) to prove 1. However, a probabilistic bijection overcomes this obstacle. This section is based on [12].
We define a map on non-attacking fillings from which we will construct a probabilistic bijection between \(\mathop{\mathrm{NAF}}(\alpha,\sigma)\) and \(\mathop{\mathrm{NAF}}(\alpha,\sigma s_i)\). Our technique is an adaptation to non-attacking fillings of a deterministic operator introduced in [13] and used in [14] to bijectively prove certain column swapping identities on \(\mathop{\mathrm{F}}(\lambda)\), and a generalization of the probabilistic operator defined in [15] for fillings of partition shapes for the symmetric Macdonald polynomials.
Fix \(\sigma\in\mathscr{S}_{n}\) and let \(\alpha\) be a composition with \(i\in[n-1]\) such that \(\alpha_i=\alpha_{i+1}\).
Definition 3. Given a filling \(T\) of shape \(\alpha\) and \(r \in [0, \alpha_i]\), let \(\mathfrak{t}_{i}\ifx&r&\else^{(r)}\fi(T)\) be the filling obtained by swapping the entries in boxes \((i, r)\) and \((i+1, r)\) in \(T\). Let \(\mathfrak{t}_{i}\ifx&0, r&\else^{[0, r]}\fi = \mathfrak{t}_{i}\ifx&r&\else^{(r)}\fi \circ \cdots \circ \mathfrak{t}_{i}\ifx&1&\else^{(1)}\fi \circ \mathfrak{t}_{i}\ifx&0&\else^{(0)}\fi\), be a sequence of swaps in the first \(r+1\) rows in the columns \(i\) and \(i+1\).
Note that for any \(r\geq 0\), \(t_i^{(r)}\) preserves the content of a filling, and if \(T \in \mathop{\mathrm{F}}(\alpha, \sigma)\), then \(\mathfrak{t}_{i}\ifx&0, r&\else^{[0, r]}\fi(T) \in \mathop{\mathrm{F}}(\alpha, \sigma s_i)\). However, \(\mathfrak{t}_{i}\ifx&r&\else^{(r)}\fi\) does not in general preserve the non-attacking property, so it does not give a valid map from \(\mathop{\mathrm{NAF}}(\alpha,\sigma)\) to \(\mathop{\mathrm{NAF}}(\alpha,\sigma s_i)\). Instead, we will use \(\mathfrak{t}_{i}\ifx&r&\else^{(r)}\fi\) to define a probabilistic bijection between the two sets, as follows.
Definition 4 (\(\rho_{i}^{(r)}\)). Let \(T \in \mathop{\mathrm{NAF}}(\alpha, \sigma)\) be a non-attacking filling. Let \(r \in [0, \alpha_i-1]\). We define \(\rho_{i}^{(r)}(T) \in \mathbb{Q}(q, t)\). Let \(a = T(i, r)\), \(b = T(i+1, r)\), \(c = T(i, r+1)\), and \(d = T(i+1, r+1)\). Let \(A = \mathop{\mathrm{arm}}(i+1, r+1)\) and \(\ell = \mathop{\mathrm{leg}}(i+1, r+1)\). Then, the value of \(\rho_{i}^{(r)}(T)\) is given in 1.
| condition | sub-condition | \(\rho_{i}^{(r)}(T)\) | \(1 - \rho_{i}^{(r)}(T)\) |
|---|---|---|---|
| \(|\{a, b, c, d\}| = 4\) | \(\readlist\thecycle{c, d, a} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} } = \readlist\thecycle{c, d, b} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} }\) | \(0\) | \(1\) |
| \(\readlist\thecycle{c, d, a} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} } = \readlist\thecycle{d, c, b} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} }\) | \(1\) | \(0\) | |
| \(b = c\) | \(0\) | \(1\) | |
| 2-4 \(|\{a, b, c, d\}| = 3\) | \(b = d\) | \(1\) | \(0\) |
| 2-4 | \(a = c\) | \(t^{1 - \readlist\thecycle{d, a, b} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} } } \frac{1 - q^{\ell+1}t^{A+1}}{1-q^{\ell+1}t^{A+2}}\) | \((q^{\ell+1}t^{A+1})^{ \readlist\thecycle{d, a, b} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} } } \frac{1-t}{1 - q^{\ell+1}t^{A+2}}\) |
| \(|\{a, b, c, d\}| = 2\) | \(a = c\), \(b = d\) | \(1\) | \(0\) |
Definition 5 (\(\operatorname{prob}_{i}\)). The map \(\operatorname{prob}_{i} \colon \mathop{\mathrm{NAF}}(\alpha, \sigma) \times \mathop{\mathrm{F}}(\alpha, \sigma s_i) \to \mathbb{Q}(q, t)\) is defined for \(T \in \mathop{\mathrm{NAF}}(\alpha, \sigma)\) and \(U \in \mathop{\mathrm{F}}(\alpha, \sigma s_i)\) by letting \[\operatorname{prob}_{i}(T, U) = \left( \prod_{r = 0}^{h-1} \rho_{i}^{(r)}(T) \right) \left( 1 - \rho_{i}^{(h)}(T) \right)\] if there exists \(h \in [0, \alpha_i]\) such that \(U = \mathfrak{t}_{i}\ifx&0, h&\else^{[0, h]}\fi(T)\), and \(\operatorname{prob}_{i}(T, U) = 0\) otherwise.
Proposition 8. The map \(\operatorname{prob}_{i} \colon \mathop{\mathrm{NAF}}(\alpha, \sigma) \times \mathop{\mathrm{F}}(\alpha, \sigma s_i) \to \mathbb{Q}(q, t)\) is a probability map, that is, for all \(T \in \mathop{\mathrm{NAF}}(\alpha, \sigma)\), \(\sum_{U \in \mathop{\mathrm{F}}(\alpha, \sigma s_i)} \operatorname{prob}_{i}(T, U) = 1\).
The main result of this section is 9. Define \({\operatorname{wt}\ifx&&\else^{()}\fi}(T) = \mathbf{x}^T {\operatorname{wt}_{q, t}\ifx&&\else^{()}\fi}(T)\) for \[{\operatorname{wt}_{q, t}\ifx&&\else^{()}\fi}(T) = q^{{\operatorname{maj}\ifx&&\else^{()}\fi}(T)} t^{{\operatorname{coinv}\ifx&&\else^{()}\fi}(T)} \prod_{u \in {\operatorname{dg}\ifx&&\else^{()}\fi}(\alpha),\;T(u) \neq T(d(u))} \frac{1 - t}{1 - q^{1 + \mathop{\mathrm{leg}}(u)} t^{1 + \mathop{\mathrm{arm}}(u)}}.\]
Theorem 9 (adapted from [15]). The pair of maps \[\begin{gather} {\operatorname{prob}_{i}} \colon \mathop{\mathrm{NAF}}(\alpha, \sigma, \beta) \times \mathop{\mathrm{NAF}}(\alpha, \sigma s_i, \beta) \to \mathbb{Q}(q, t) \\ {\operatorname{prob}_{i}} \colon \mathop{\mathrm{NAF}}(\alpha, \sigma s_i, \beta) \times \mathop{\mathrm{NAF}}(\alpha, \sigma, \beta) \to \mathbb{Q}(q, t) \end{gather}\] defines a probabilistic bijection between \(\mathop{\mathrm{NAF}}(\alpha, \sigma, \beta)\) and \(\mathop{\mathrm{NAF}}(\alpha, \sigma s_i, \beta)\) with respect to the weight function \({\operatorname{wt}_{q, t}\ifx&&\else^{()}\fi}\). In other words, for all \(T \in \mathop{\mathrm{NAF}}(\alpha, \sigma, \beta)\) and \(U \in \mathop{\mathrm{NAF}}(\alpha, \sigma s_i, \beta)\), \[{\operatorname{wt}_{q, t}\ifx&&\else^{()}\fi}(U)\operatorname{prob}_{i}(U, T) = {\operatorname{wt}_{q, t}\ifx&&\else^{()}\fi}(T)\operatorname{prob}_{i}(T, U).\]
Example 1. Let \(n = 4\), \(\alpha = \def\temp{2, 2, 0, 1}\ifx\temp\empty \varnothing \else \readlist\thecycle{2, 2, 0, 1} \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} \fi\), \(\sigma = \left[ \readlist\thecycle{3, 1, 2, 4} \foreachitem\i\in\thecycle{\ifnum\icnt=1\else,\fi\i} \right]\), \(\beta = \def\temp{1, 2, 0, 2}\ifx\temp\empty \varnothing \else \readlist\thecycle{1, 2, 0, 2} \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} \fi\). Let \(i = 1\) and note that \(\alpha_1 = \alpha_2 = 2\). Moreover, note that \(\sigma s_i = \left[ \readlist\thecycle{1, 3, 2, 4} \foreachitem\i\in\thecycle{\ifnum\icnt=1\else,\fi\i} \right]\). 9 implies that the maps \(\operatorname{prob}_{1} \colon \mathop{\mathrm{NAF}}(\alpha, \sigma, \beta) \times \mathop{\mathrm{NAF}}(\alpha, \sigma s_1, \beta) \to \mathbb{Q}(q, t)\) and \(\operatorname{prob}_{1} \colon \mathop{\mathrm{NAF}}(\alpha, \sigma s_1, \beta) \times \mathop{\mathrm{NAF}}(\alpha, \sigma, \beta) \to \mathbb{Q}(q, t)\) form a probabilistic bijection.
We have \(\mathop{\mathrm{NAF}}(\alpha, \sigma, \beta) = \{ \textcolor{red!50!black}{T_1}, \textcolor{red!50!black}{T_2}, \textcolor{red!50!black}{T_3} \}\), and \(\mathop{\mathrm{NAF}}(\alpha, \sigma s_i, \beta) = \{ \textcolor{blue!50!black}{U_1}, \textcolor{blue!50!black}{U_2} \}\), shown in the left and right sides of 5, respectively. 5 shows the values of \(\operatorname{prob}_{1}(T, U)\) and \(\operatorname{prob}_{1}(U, T)\) for each pair of fillings.
![Figure 5: For \alpha=2201, \sigma=[3,1,2,4], \beta=1202, we show T_i \in \mathop{\mathrm{NAF}}(\alpha,\sigma,\beta) and U_j \in \mathop{\mathrm{NAF}}(\alpha,\sigma s_1,\beta) and their q,t-weights. The label of an arrow from A to B is \operatorname{prob}_{1}(A,B).](/article/2606.02395/_pdflatex/rmzbeisk.png "fig:")
The fact that the maps form a probabilistic bijection can be checked by computing that, for each \(T \in \{\textcolor{red!50!black}{T_1}, \textcolor{red!50!black}{T_2}, \textcolor{red!50!black}{T_3}\}\) and each \(U \in \{\textcolor{blue!50!black}{U_1}, \textcolor{blue!50!black}{U_2}\}\), we have \(\operatorname{prob}_{1}(T, U) {\operatorname{wt}_{q, t}\ifx&&\else^{()}\fi}(T) = \operatorname{prob}_{1}(U, T) {\operatorname{wt}_{q, t}\ifx&&\else^{()}\fi}(U)\). Moreover, using the fact that there exists a probabilistic bijection between \(\{\textcolor{red!50!black}{T_1}, \textcolor{red!50!black}{T_2}, \textcolor{red!50!black}{T_3}\}\) and \(\{\textcolor{blue!50!black}{U_1}, \textcolor{blue!50!black}{U_2}\}\), 9 implies that their \(q, t\)-weight generating functions are equal: \[[x^\beta]E_\alpha^\sigma={\operatorname{wt}_{q, t}\ifx&&\else^{()}\fi}(\textcolor{red!50!black}{T_1}) + {\operatorname{wt}_{q, t}\ifx&&\else^{()}\fi}(\textcolor{red!50!black}{T_2}) + {\operatorname{wt}_{q, t}\ifx&&\else^{()}\fi}(\textcolor{red!50!black}{T_3}) = {\operatorname{wt}_{q, t}\ifx&&\else^{()}\fi}(\textcolor{blue!50!black}{U_1}) + {\operatorname{wt}_{q, t}\ifx&&\else^{()}\fi}(\textcolor{blue!50!black}{U_2})=[x^\beta]E_\alpha^{\sigma s_i}.\]
1 now follows from 9 by applying 7 to obtain \([x^\beta]E_\alpha^\sigma=[x^\beta]E_\alpha^{\sigma s_i}\) for each content \(\beta\).
4 Bijection preserving major index and inversion number↩︎
To prove 3, we start by returning to the general set of fillings \(\mathop{\mathrm{F}}(\alpha)\) and construct a weight-preserving bijection that exchanges two adjacent columns producing a filling in \(\mathop{\mathrm{F}}(s_i\alpha)\). This bijection is equivalent to [8], though we give a simplified presentation. In what follows, we work with fillings over an arbitrary totally ordered alphabet. Fix a composition \(\alpha\) and an index \(i\in[n-1]\) such that \(\alpha_i>\alpha_{i+1}\mathrel{\vcenter{:}}= m\).
Our goal is to build a bijection that preserves row content and the statistics \({\operatorname{maj}\ifx&&\else^{()}\fi}\) and \({\operatorname{inv}\ifx&&\else^{()}\fi}\). Thus we must determine which rows swap entries when the two columns are exchanged, focusing on maintaining a “local” preservation of the \({\operatorname{inv}\ifx&&\else^{()}\fi}\) statistic. Since Type I triples in columns \(i,i+1\) of \(T\) become Type II triples in its image \(\phi(T)\), we aim to match the inversion types of the corresponding triples between \(T\) and \(\phi(T)\). In many cases, for local preservation of \({\operatorname{inv}\ifx&&\else^{()}\fi}\), the necessary swaps between consecutive rows are interdependent; we capture this dependence by grouping such rows into blocks, which will correspond to sets of adjacent rows that must be swapped simultaneously.
Definition 6. For a filling \(T \in \mathop{\mathrm{F}}(\alpha)\) and \(r\in[m-1]\), we say that the rows \(r\) and \(r+1\) are intertwined if \(\readlist\thecycle{a, c, d} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} } \neq \readlist\thecycle{b, c, d} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} }\), where \(a = T(i, r+1)\), \(b = T(i+1, r+1)\), \(c = T(i, r)\), and \(d = T(i+1, r)\). A block is a maximal consecutive set of intertwined rows. Equivalently, \([m]\) decomposes uniquely into blocks such that consecutive rows are in different blocks if and only if they are not intertwined. See 6.
We construct a filling \(\phi(T) \in \mathop{\mathrm{F}}(s_i \cdot \alpha)\) derived from \(T\), starting by copying all entries in \(T\) outside of columns \(i\) and \(i+1\). Then, for the upper rows \([m+1,\alpha_i]\), we copy the entries from column \(i\) of \(T\) to column \(i+1\) of \(\phi(T)\). What remains is to determine the entries in columns \(i,i+1\) in rows \([m]\) of \(\phi(T)\); this reduces to choosing which blocks are swapped and which remain unchanged, where swapping a block means swapping the entries between columns \(i\) and \(i+1\) within the block.
Focusing on a block of \(T\), let \((a,b)\) and \((c,d)\) be the entries in columns \((i,i+1)\) in the top row and bottom row of the block, respectively. Let \((e,f)\) and \((g,h)\) be the entries in columns \((i,i+1)\) in the row immediately above the block and in the row immediately below the block, respectively. \(f\) may be undefined if it doesn’t exist, and we set \(g=h=\infty\) if the block is the bottommost block. See [fig:general-block] for an illustration.
Then, we place the block in \(\phi(T)\) by swapping the block if \(\readlist\thecycle{c, d, g} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} } \neq \readlist\thecycle{e, a, b} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} }\), and leaving it unchanged otherwise. Non-intertwinedness ensures that the \({\operatorname{inv}\ifx&&\else^{()}\fi}\) contributions of distinct blocks are independent; thus the total contribution to \({\operatorname{inv}\ifx&&\else^{()}\fi}\) is preserved for each block. 7 shows the procedure with the filling from 6 as the input.
The inversion number is preserved between \(T\) and \(\phi(T)\), by construction. Miraculously, the major index is preserved as well, which can be verified with a case analysis.
Theorem 10 ([8]). The map \(\phi \colon \mathop{\mathrm{F}}(\alpha) \to \mathop{\mathrm{F}}(s_i \cdot \alpha)\) is a bijection satisfying \(\mathbf{x}^{|T|} = \mathbf{x}^{|\phi(T)|}\), \({\operatorname{maj}\ifx&&\else^{()}\fi}(T) = {\operatorname{maj}\ifx&&\else^{()}\fi}(\phi(T))\), and \({\operatorname{inv}\ifx&&\else^{()}\fi}(T) = {\operatorname{inv}\ifx&&\else^{()}\fi}(\phi(T))\) for all \(T \in \mathop{\mathrm{F}}(\alpha)\).
As an auxiliary construction, define \(\psi(T)\) to be the filling obtained from \(\phi(T)\) by swapping the bottommost block. The map \(\psi\) changes the statistics \({\operatorname{inv}\ifx&&\else^{()}\fi}\) and \({\operatorname{maj}\ifx&&\else^{()}\fi}\) in a controlled way, as follows.
Theorem 11 ([8]). Assume \(\alpha_i > \alpha_{i+1}\). The map \(\psi \colon \mathop{\mathrm{F}}(\alpha) \to \mathop{\mathrm{F}}(s_i \cdot \alpha)\) is a bijection such that, for all \(T \in \mathop{\mathrm{F}}(\alpha)\) satisfying \(\readlist\thecycle{{T(i, 1)},{T(i+1, 1)}} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} } = 1\), we have \(\mathbf{x}^{|T|} = \mathbf{x}^{|\psi(T)|}\), and \[({\operatorname{inv}\ifx&&\else^{()}\fi}(T),{\operatorname{maj}\ifx&&\else^{()}\fi}(T)) = \begin{cases} ({\operatorname{inv}\ifx&&\else^{()}\fi}(\psi(T)) + A,\,{\operatorname{maj}\ifx&&\else^{()}\fi}(\psi(T)) - (L+1)) & \text{if } \readlist\thecycle{{\psi(T)(i, 1)},{\psi(T)(i+1, 1)}} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} } = 1\,, \\ ({\operatorname{inv}\ifx&&\else^{()}\fi}(\psi(T)) + 1,\,{\operatorname{maj}\ifx&&\else^{()}\fi}(\psi(T))) & \text{if } \readlist\thecycle{{\psi(T)(i, 1)},{\psi(T)(i+1, 1)}} \chi_{ \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} } = 0\,. \end{cases}\]
Remark 12. [8] define \(\phi\) and \(\psi\) by a recursive procedure that examines the filling from the bottom row upward and may invoke either map at intermediate steps. Their definition is less transparent, but is well suited to induction. Their recursive constructions produce the same bijections as our nonrecursive descriptions.
Remark 13. As a corollary, we get a simple bijective proof of [5].
4.1 Shape changing identity↩︎
In this subsection, we establish 3. Each permuted-basement Macdonald polynomial admits a signed filling expansion as in 1, thus 1 is equivalent to \[\label{eq:Fill32pm} \sum_{T\in\mathop{\mathrm{F}}_\pm(\alpha,\sigma)}{\operatorname{wt}\ifx&&\else^{()}\fi}_\pm(T) = \sum_{T\in\mathop{\mathrm{F}}_\pm(s_i\alpha,\sigma s_i)}{\operatorname{wt}\ifx&&\else^{()}\fi}_\pm(T) + c_{i,\alpha,\sigma}(q, t) \sum_{T\in\mathop{\mathrm{F}}_\pm(s_i\alpha,\sigma)}{\operatorname{wt}\ifx&&\else^{()}\fi}_\pm(T).\tag{3}\] We relate each element of the left-hand sum to a pair of elements in the right-hand sums, using 10 11 as building blocks.
Using the signed \(\chi\) function, we extend \(\phi\) and \(\psi\) to maps on signed augmented fillings \(\mathop{\mathrm{F}}_\pm(\alpha,\sigma)\). Because each map may or may not interchange the \(i\)th and \((i+1)\)th basement entries, their natural domain is \(\mathop{\mathrm{F}}_\pm(s_i\alpha,\sigma)\,\cup\,\mathop{\mathrm{F}}_\pm(s_i\alpha,\sigma s_i).\) Nevertheless, \(\psi(T)\) is obtained from \(\phi(T)\) by swapping the bottommost block, so exactly one of \(\phi(T)\) and \(\psi(T)\) lies in \(\mathop{\mathrm{F}}_\pm(s_i\alpha,\sigma s_i)\), and the other lies in \(\mathop{\mathrm{F}}_\pm(s_i\alpha,\sigma)\). Hence for each \(T\) there exist unique \[f(T)\in \mathop{\mathrm{F}}_\pm(s_i\alpha,\sigma s_i),\qquad g(T)\in \mathop{\mathrm{F}}_\pm(s_i\alpha,\sigma)\] such that \(\{f(T),g(T)\}=\{\phi(T),\psi(T)\}\). The bijections \(f\) and \(g\) associate, to each \(T\in\mathop{\mathrm{F}}_\pm(\alpha,\sigma)\), a pair of fillings appearing on the right side of 3 . 2, proved using 11, asserts that their weights match the required contributions in 3 .
Lemma 2. For all \(T \in \mathop{\mathrm{F}}_\pm(\alpha, \sigma)\), we have \[{\operatorname{wt}\ifx&&\else^{()}\fi}_\pm(T) = {\operatorname{wt}\ifx&&\else^{()}\fi}_\pm(f(T)) + c_{i, \alpha, \sigma}(q, t) {\operatorname{wt}\ifx&&\else^{()}\fi}_\pm(g(T)),\] where \(c_{i, \alpha, \sigma}(q, t)\) is as in 3.
Using 2 and summing over all \(T \in \mathop{\mathrm{F}}_\pm(\alpha, \sigma)\), we obtain 3 and hence 3.
Example 2. For \(\alpha = \def\temp{3, 2}\ifx\temp\empty \varnothing \else \readlist\thecycle{3, 2} \foreachitem\i\in\thecycle{\ifnum\icnt=1\else\fi\i} \fi\), \(\sigma = \left[ \readlist\thecycle{2, 1} \foreachitem\i\in\thecycle{\ifnum\icnt=1\else,\fi\i} \right]\), and \(i = 1\), we have \(c_{i, \alpha, \sigma}(q, t) = \frac{1 - t}{1 - q^{1} t^{1}}\). Below, we show a filling \(T\in\mathop{\mathrm{F}}_\pm(\alpha,\sigma)\) and its derived fillings \(f(T)\) and \(g(T)\). We compute \({\operatorname{wt}\ifx&&\else^{()}\fi}_\pm(T) = \frac{x_1^3x_2^2 q^4 t^1 (-t)^3}{(1-qt)P(q, t)}\), \({\operatorname{wt}\ifx&&\else^{()}\fi}_\pm(f(T)) = \frac{x_1^3x_2^2 q^4 t^2 (-t)^3}{(1-qt^2)P(q, t)}\), and \({\operatorname{wt}\ifx&&\else^{()}\fi}_\pm(g(T)) = \frac{x_1^3x_2^2 q^4 t^1 (-t)^3}{(1-qt^2)P(q, t)}\), where \(P(q, t) = {\scriptstyle (1-qt)(1-q^2t)(1-q^2t^2)(1-q^2t^3)}\). We confirm 2 for this \(T\) by checking that \[\frac{x_1^3x_2^2 q^4 t^1 (-t)^3}{(1-qt)P(q, t)} = \frac{x_1^3x_2^2 q^4 t^2 (-t)^3}{(1-qt^2)P(q, t)} + \frac{1 - t}{1 - q^{1} t^{1}}\; \frac{x_1^3x_2^2 q^4 t^1 (-t)^3}{(1-qt^2)P(q, t)}.\]
Figure 8: 
.
Remark 14. The inversion number for an augmented filling of shape \(\alpha\) with basement \(\sigma\) and the inversion number for its associated non-augmented filling are not the same; they differ by \(\mathop{\mathrm{twinv}}(\alpha,\sigma)\). This discrepancy explains why the exponent \(\mathop{\mathrm{twinv}}(s_i \alpha, \sigma) - \mathop{\mathrm{twinv}}(\alpha, \sigma)\) appears in \(c_{i, \alpha, \sigma}(q, t)\).
Remark 15. Instead of using the signed filling formula of 1 to prove 3, one could also attempt to work directly with the non-attacking fillings appearing in the compact expression of 6. One approach is to adapt the recursive construction for \(\phi\) and \(\phi\) from [8], introducing suitable weights to produce a probabilistic bijection on non-attacking fillings, although we do not develop this idea here.
5 Straightening↩︎
Definition 7. For compositions \(\alpha\) and \(\beta\) that are rearrangements of each other, let \(\pi_\alpha, \pi_\beta \in\mathscr{S}_{n}\) be the shortest permutations such that \(\pi_\alpha \cdot \alpha=\mathop{\mathrm{inc}}(\alpha)\) and \(\pi_\beta \cdot \beta=\mathop{\mathrm{inc}}(\beta)\). Define the Bruhat order on compositions by \(\alpha \succ \beta\) if and only if \(\pi_\alpha > \pi_\beta\) in Bruhat order.
The identity of 3 generalizes to a straightening rule, allowing us to expand \(E_\alpha^\sigma\) in the polynomials \(\{E_{\tau\alpha}^\theta\}_\theta\) whenever \(\alpha\succ \tau\alpha\). Moreover, we obtain an explicit expression for the coefficients by keeping track of when the first or second term of the right hand side of 1 arises.
For a reduced word \(\tau=s_{i_k}\cdots s_{i_1}\) and a subset \(I=\{j_1,\ldots,j_\ell\}\subseteq [k]\), define \(\tau_I\mathrel{\vcenter{:}}= s_{i_{j_\ell}}\cdots s_{i_{j_1}}\) to be the corresponding subword of \(\tau\), indexed by \(I\). Define also the \(j\)-truncated index set \(I^{<j}=I\cap [j-1]\) and the \(j\)-truncated subword \(\tau^{<j}_I\mathrel{\vcenter{:}}= \tau_{I^{<j}}\) indexed by this set. Notice that this corresponds to the sequence of transpositions indexed by \(I\), contained within the first \(j-1\) elements of \(\tau\), from the right.
Proposition 16. Let \(\alpha\) be a composition and let \(\beta=\tau\alpha\) for a reduced word \(\tau=s_{i_k}\cdots s_{i_1}\) satisfying \(\alpha\succ\beta\). Then, \[E_\alpha^\sigma(\mathbf{x};q,t)=\sum_{I\subseteq[k]}\Phi(\alpha,\sigma;\tau,I)E_{\beta}^{\sigma\tau_I}(\mathbf{x};q,t),\qquad \Phi(\alpha,\sigma;\tau,I)=\prod_{j\not\in I}\Psi(\alpha^{(j)},\sigma \tau^{<j}_I,i_j).\] where \(\Psi(\beta,\rho,i)=c_{i,\beta,\rho}(q,t)\) as given in 3.
The coefficients in the expansion above are sums of terms of the form \[q^at^b\prod_{(i,j)\in D}\frac{1-t}{1-q^it^j},\qquad a,b\in\mathbb{Z}_{\geq 0},\qquad D\subset\mathbb{Z}_{>0}^2\,,\] where \(D\) is a finite multiset bounded by the box containing \({\operatorname{dg}\ifx&&\else^{()}\fi}(\alpha)\). At \(t=0\), these coefficients are in \(\mathbb{Z}_{\geq 0}[q]\), and at \(q=0\), the expansion is a non-negative integer linear combination of monomials of the form \(t^a(1-t)^b\).
Corollary 1. Let \(\alpha\) and \(\beta\) be a compositions with \(\alpha\succ\beta\). Then, \[E_\alpha^\sigma(\mathbf{x};q,0)=\sum_{\theta}d_{\alpha,\sigma,\theta}(q)E_{\beta}^{\theta}(\mathbf{x};q,0),\qquad d_{\alpha,\sigma,\theta}(q)\in\mathbb{Z}_{\geq 0}[q].\]
In particular, since we always have \(\alpha\succeq\mathop{\mathrm{inc}}(\alpha)\), the straightening rule yields a “nice” formula for the expansion of \(E_\alpha^\sigma\) in the ASEP polynomials \(\{F_\beta\}_{\beta\in \mathscr{S}_{n}(\alpha)}=\{E_{\mathop{\mathrm{inc}}(\alpha)}^\theta\}_{\theta}\), with coefficients in the form described above.
Question 17. Find a combinatorial interpretation for the coefficients \(d_{\alpha, \sigma, \beta}(q)\) in 1.