\PassOptionsToPackage{dvipsnames}{xcolor} \documentclass[ALCO, Unicode]{cedram} \usepackage[matrix,arrow,tips,curve]{xy} \usepackage{tikz} \usetikzlibrary{calc,decorations.markings,arrows.meta} \usepackage{tkz-graph} \usepackage{bm} \usepackage{upgreek} \usepackage[english]{babel} \usepackage{csquotes} \usepackage{tikz-cd} \usepackage{subcaption} \usepackage{float} \usepackage{hyperref} \usepackage{microtype} \usepackage{dsfont} \newcommand{\one}{\mathds{1}} \usepackage{caption} \newcommand{\B}{\mathcal{B}} \newcommand{\colorA}{Orchid} \newcommand{\colorB}{Tan} \newcommand{\colorC}{JungleGreen} \newcommand{\colorD}{NavyBlue} \newcommand{\colorE}{gray} \newcommand{\conv}{\mathrm{conv}} \newcommand{\GW}{\mathrm{GW}} \newcommand{\id}{\mathrm{id}} \newcommand{\Inv}{\mathrm{Inv}} \newcommand{\N}{\mathbb{N}} \newcommand{\Newton}{\mathrm{Newton}} \newcommand{\Pair}{\mathcal{P}} \newcommand{\R}{\mathbb{R}} \newcommand{\supp}{\mathrm{supp}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\ZZZ}{\mathbb{Z}_{\ge 0}} \title [Newton polytopes of dual Schubert polynomials] {Newton polytopes of dual Schubert polynomials} \author{\firstname{Serena} \lastname{An}} \address{Massachusetts Institute of Technology\\ Department of Mathematics\\ Cambridge\\ MA 02139 (USA)} \email{anser@mit.edu} \author{\firstname{Katherine} \lastname{Tung}} \address{Harvard University\\ Department of Mathematics\\ Cambridge\\ MA 02138 (USA)} \email{katherinetung@college.harvard.edu} \author{\firstname{Yuchong} \lastname{Zhang}} \address{University of Michigan\\ Department of Mathematics\\ Ann Arbor\\ MI 48109 (USA)} \email{zongxun@umich.edu} \keywords{Newton polytope, dual Schubert polynomial, M-convex} \subjclass{05E05, 14N15, 52B40} \begin{document} \begin{abstract} The M-convexity of dual Schubert polynomials was first proven by Huh, Matherne, M\'esz\'aros, and St.\ Dizier in 2022. We give a full characterization of the support of dual Schubert polynomials, which yields an elementary alternative proof of the M-convexity result, and furthermore strengthens it by explicitly characterizing the vertices of their Newton polytopes combinatorially. Using this characterization, we give a polynomial-time algorithm to determine if a coefficient of a dual Schubert polynomial is zero, analogous to a result of Adve, Robichaux, and Yong for Schubert polynomials. \end{abstract} \maketitle \section{Introduction} The dual Schubert polynomials $\{D^w\}_{w\in S_{n}}$, introduced by Bernstein, Gelfand, and Gelfand~\cite{BGG}, are given by the following combinatorial formula~\cite{PostnikovStanley}. Let the edge $u \lessdot ut_{ab}$ in the (strong) Bruhat order have weight \[m(u \lessdot ut_{ab}) \coloneqq x_a + x_{a+1} + \cdots + x_{b-1},\] and let the saturated chain $C = (u_0 \lessdot u_1\lessdot\cdots \lessdot u_{\ell})$ have weight \[m_C\coloneq m(u_0 \lessdot u_1)m(u_1 \lessdot u_2)\cdots m(u_{\ell - 1} \lessdot u_{\ell}).\] \begin{defi}\label{def:dualSchubert} For $w \in S_n$, the \emph{dual Schubert polynomial $D^w$} is defined by \[D^w(x_1, \dots,x_{n-1}) \coloneqq \frac{1}{\ell(w)!} \sum_C m_C(x_1, \dots,x_{n-1}),\] where $\ell(w)$ denotes the Coxeter length of $w$, and the sum is over all saturated chains~$C$ from $\id$ to $w$. \end{defi} Dual Schubert polynomials possess deep geometric and algebraic properties. For example, the $\lambda$-degree of a Schubert variety $X_w$ can be expressed as $\ell(w)! \cdot D^w(\lambda)$~\cite{PostnikovStanley}. Additionally, dual Schubert polynomials form a dual basis to Schubert polynomials under a certain natural pairing $\langle \cdot, \cdot \rangle$ on polynomials~\cite{PostnikovStanley}. In recent years, dual Schubert polynomials have attracted increasing interest~\cite{InvolRC, Hamaker,HuhMeszaroLorSchur}. We continue the study of dual Schubert polynomials by fully characterizing their \emph{supports} (set of exponent vectors) and \emph{Newton polytopes} (convex hull of the support). \begin{theorem}\label{theorem:support} The support of the dual Schubert polynomial $D^w$ is \[\supp (D^w)= \sum_{(a,b) \in \Inv(w)}\{e_a, e_{a+1}, \dots, e_{b-1}\},\] where the right-hand side is a Minkowski sum of sets of elementary basis vectors. The sum is over pairs of indices $(a, b)$ for which there is an inversion in $w$. \end{theorem} A polynomial $f$ has a \textit{saturated Newton polytope (SNP)} if its support is all integer points in its Newton polytope. The SNP property was first defined by Monical, Tokcan and Yong~\cite{NewtonPolyinAC}. Many polynomials with algebraic combinatorial significance are known to have SNP, such as Schur polynomials~\cite{Rado} and resultants~\cite{GKZ}. Monical, Tokcan, and Yong proved SNP for additional families of polynomials, including cycle index polynomials, Reutenauer's symmetric polynomials linked to the free Lie algebra and to Witt vectors, Stembridge's symmetric polynomials associated to totally nonnegative matrices, and symmetric Macdonald polynomials. Subsequent work of Fink, M\'esz\'aros, and St.\ Dizier proved SNP for key polynomials and Schubert polynomials~\cite{FMD}, work of Castillo, Cid Ruiz, Mohammadi, and Monta\~no proved SNP for double Schubert polynomials~\cite{DoubleSchSNP}, and work of Huh, Matherne, M\'esz\'aros, and St.\ Dizier~\cite{HuhMeszaroLorSchur} proved Lorentzian-ness, which implies SNP, for dual Schubert polynomials. Proving SNP can be difficult given that many polynomial operations, such as multiplication, do not preserve SNP. However, a wide range of techniques have been harnessed to prove SNP. For instance, Rado uses elementary combinatorial techniques~\cite{Rado}, Fink, M\'esz\'aros, and St.\ Dizier rely on representation theory~\cite{FMD}, and Castillo et al.\ as well as Huh et al.\ use results from algebraic geometry~\cite{DoubleSchSNP,HuhMeszaroLorSchur}. As a corollary of Theorem~\ref{theorem:support}, we obtain an elementary proof of the following result. \begin{coro}\textup{(}\cf \cite[Proposition~18]{HuhMeszaroLorSchur}\textup{)}\label{thm:M-conv} Dual Schubert polynomials are \emph{M-convex}; equivalently, they have SNP and their Newton polytopes are generalized permutahedra. \end{coro} Strengthening this result, we fully characterize the vertices of $\Newton(D^w)$. \begin{coro}\label{thm:DSPNPVert} For $w\in S_n$, the vertices of $\Newton(D^w)$ are \[\{\alpha\in\ZZ_{\ge 0}^{n-1} \mid x^{\alpha}\text{ has coefficient }1\text{ in }\prod_{(a,b) \in \Inv(w)} (x_a+x_{a+1}+\dots +x_{b-1})\}.\] \end{coro} Furthermore, in light of \cite[Corollary~8.2]{postnikovpermutohedra}, we give a combinatorial characterization of the vertices of $\Newton(D^w)$ using rectangle tilings of staircase Young diagrams. This paper is organized as follows. In Section~\ref{section:preliminaries}, we give the necessary relevant background and definitions. In Section~\ref{section:Mconvexity}, we prove that dual Schubert polynomials are M-convex. In Section~\ref{section:vertices}, we characterize the vertices of Newton polytopes of dual Schubert polynomials in two different ways. In Section~\ref{section:vanishing}, we solve the vanishing problem for dual Schubert polynomials in polynomial time, extending a result in~\cite{ARY}. \section{Preliminaries}\label{section:preliminaries} \subsection{Bruhat order} In this paper, we use standard terminology for the (strong) Bruhat order. The readers are referred to \cite[Chapter~2]{BjornerBrenti} for a more detailed exposition. Let $S_n$ be the symmetric group on the set $[n] \coloneqq \{1, \dots, n\}$. We write each permutation $w\in S_n$ in one-line notation as $w = w(1)w(2)\cdots w(n)$. Each permutation $w \in S_n$ can be expressed as a product of \emph{simple transpositions} $s_i = \{(i, i+1) : 1\le i\le n-1\}$. If $w = s_{i_1}\cdots s_{i_{\ell}}$ is expressed as a product of simple transpositions with $\ell$ minimal among all such expressions, then the string $s_{i_1}\cdots s_{i_{\ell}}$ is called a \emph{reduced decomposition} of $w$. We call $\ell \coloneqq \ell(w)$ the \emph{(Coxeter) length} of $w$. An \emph{inversion} of $w$ is an ordered pair $(a,b)\in [n]^2$ such that $a< b$ and $w(a)>w(b)$. We denote the set of all inversions of $w$ by $\Inv(w)$. It is well-known that $\ell(w) = |\Inv(w)|$. Given $1\le a < b\le n$, let $t_{ab}$ act on $w\in S_n$ such that $wt_{ab}$ is the permutation obtained by transposing the two numbers in positions $a$ and $b$ in $w$. \begin{defi}(\cite{BjornerBrenti})\label{def:bruhatorder} We define a partial order $\le$ on $S_n$ called the \emph{strong Bruhat order} as follows. Let $u, v\in S_n$ and $\ell = \ell(v)$. We have $u\le v$ if and only if for any reduced decomposition $s_{i_1}\cdots s_{i_{\ell}}$ of $v$, there exists a reduced decomposition $s_{j_1}\cdots s_{j_k}$ of $u$ such that $s_{j_1}\cdots s_{j_k}$ is a substring of $s_{i_1}\cdots s_{i_{\ell}}$. If additionally $\ell(v) = \ell(u) + 1$, we write $u\lessdot v$. Alternatively, we may characterize the covering relation as follows. For~$u, v \in S_n$, we have $u \lessdot v$ if and only if $v = ut_{ab}$ and $\ell(v) = \ell(u) + 1$. \end{defi} For $u\le w$ in the Bruhat order of $S_n$, the \emph{(Bruhat) interval} $[u, w]$ is the subposet containing all $v\in S_n$ such that $u\le v\le w$. \subsection{Postnikov--Stanley polynomials} For $w \in S_n$, we define Postnikov--Stanley polynomials, which generalize dual Schubert polynomials. \begin{defi}(\cite{PostnikovStanley}) Given $u\le w $ in $ S_n$, the \emph{Postnikov--Stanley polynomial} $D_u^w$ is defined by \[D_u^w(x_1, \dots, x_{n-1}) \coloneqq \frac{1}{(\ell(w) - \ell(u))!}\sum_{C} m_C(x_1, \dots, x_{n-1}),\] where the sum is over all saturated chains $C$ from $u$ to $w$. \end{defi} As defined in the introduction, the \emph{dual Schubert polynomial} $D^w$ is given by $D^w\coloneq D_{\id}^w$. \begin{exam}\label{ex:PS} Let $u = 213$ and $w = 321$. In the Bruhat order of $S_3$, there are two saturated chains from $u$ to $w$, namely $213\lessdot 231\lessdot 321$ and $213\lessdot 312\lessdot 321$, as shown in Figure~\ref{fig:123to321}. The first chain has weight $x_1x_2$ and the second chain has weight $(x_1 + x_2) \cdot x_2$. Thus, $D_{213}^{321} = \frac{1}{2!}(x_1 x_2 + (x_1 + x_2)\cdot x_2)$. \end{exam} \begin{figure} \centering \begin{tikzpicture}[auto=center,every node/.style={circle, fill=white,scale=0.7,draw=black, solid}, scale=1.75, label distance=0.5mm] \node (a) at (0, 0) {}; \node[label=left:{\large $213$}] (b) at (-1, 1) {}; \node[label=right:{\large $132$}] (d) at (1, 1) {}; \node[label=left:{\large $231$}] (e) at (-1, 2) {}; \node[label=right:{\large $312$}] (g) at (1, 2) {}; \node (h) at (0, 3) {}; \node[draw=none, fill=none] at ($(a)-(0, 0.25)$) {\large $123$}; \node[draw=none, fill=none] at ($(h)+(0, 0.25)$) {\large $321$}; \draw (a)--node [draw=none] {\large $x_1$}(b); \draw (a)--node [draw=none] {\large $x_2$}(d); \draw[line width=0.75mm, \colorA] (b)--node [draw=none] {\large $x_2$}(e); \draw[line width=0.75mm, \colorA] (e)--node [draw=none] {\large $x_1$}(h); \draw[line width=0.75mm, \colorB] (g)--node [draw=none] {\large $x_2$}(h); \draw (d)--node [draw=none] {\large $x_1$}(g); \draw[line width=0.75mm, \colorB] (b)--node [near start, draw=none] {\large $x_1 + x_2$}(g); \draw (d)--node [near start, draw=none] {\large $x_1 + x_2$}(e); \end{tikzpicture} \caption{Calculating the Postnikov--Stanley polynomial $D_{213}^{321}$.} \label{fig:123to321} \end{figure} \begin{rema} Dual Schubert polynomials $D^w$ and Postnikov--Stanley polynomials $D_u^w$ are defined for $u,w$ in any Weyl group $W$~\cite{PostnikovStanley}. However, we only consider the case $W = S_n$ in this paper. For a treatment of dual Schubert polynomials and Postnikov--Stanley polynomials in their full generality, please see our follow-up paper~\cite{PSLorentzian}. \end{rema} \subsection{Newton polytopes} We formalize the parenthetical definitions of the Newton polytope given in the introduction. \begin{defi}\label{def:expvector} For a tuple $\alpha = (\alpha_1, \dots, \alpha_n)\in \ZZ_{\ge 0}^n$, let $x^\alpha$ denote the monomial \[x^\alpha \coloneqq x_1^{\alpha_1}\cdots x_n^{\alpha_n}\in \R[x_1, \dots, x_n].\] We call $\alpha$ the \emph{exponent vector} of $x^{\alpha}$. \end{defi} \begin{defi}\label{def:supp} Let $f = \sum_{\alpha \in \ZZZ^{n}} c_{\alpha} x^{\alpha} \in \R[x_{1}, \ldots, x_{n}]$ be a polynomial. The \emph{support} of $f$, denoted $\supp(f)$, is the set of exponent vectors $\alpha$ of the nonzero terms of $f$. \end{defi} \begin{defi}\label{def:newton} The \emph{Newton polytope} of a polynomial $f\in \R[x_1, \dots, x_n]$, denoted $\Newton(f)$, is the convex hull of $\supp(f)$ in $\mathbb{R}^n$. \end{defi} The support and Newton polytope of a polynomial behave nicely with respect to polynomial addition and multiplication as follows. \begin{prop}\label{prop:suppsumprod} For two polynomials $f, g\in\R_{\ge 0}[x_1, \dots, x_n]$, we have \begin{align*} \supp(fg) &=\supp(f)+\supp(g)\\ \supp(f+g) &=\supp(f)\cup\supp(g), \end{align*} where $+$ in the first line denotes the Minkowski sum. \end{prop} \begin{prop}[\cite{NewtonPolyinAC}]\label{prop:Newtonsumprod} For two polynomials $f, g\in\R_{\ge 0}[x_1, \dots, x_n]$, we have \begin{align*} \Newton(fg) &=\Newton(f)+\Newton(g)\\ \Newton(f+g) &=\conv(\Newton(f)\cup\Newton(g)), \end{align*} where $+$ in the first line denotes the Minkowski sum, and $\conv$ denotes the convex hull. \end{prop} \begin{defi}(\cite{NewtonPolyinAC}) A polynomial $f \in \R[x_1, \dots, x_n]$ has \emph{saturated Newton polytope (SNP)} if $\supp(f)$ consists of all integer points in $\Newton(f)$. \end{defi} \begin{exam}\label{ex:snp} As computed in Example~\ref{ex:PS}, $D_{213}^{321} = x_1x_2+\frac{1}{2}x_2^2$, so its Newton polytope $\Newton(D_{213}^{321})$ is the line segment from $(1, 1)$ to $(0, 2)$ in $\R^2$. There are no integer points on this line segment besides the endpoints, so $D_{213}^{321}$ has SNP. \end{exam} \begin{rema} A nonexample for SNP is the polynomial \[f = x^{(0, 1, 3)} + x^{(0,3,1)} + x^{(1,0,3)} + x^{(1,3,0)} + x^{(3,0,1)} + x^{(3,1,0)},\] because $\Newton(f)$ contains the integer point $(0, 2, 2)$, but there is no $cx^{(0, 2, 2)}$ monomial in $f$ for $c$ nonzero. \end{rema} \subsection{Matroid polytopes}\label{section:matroidpolytopes} Matroid polytopes, a special type of Newton polytope, were heavily used in~\cite{DoubleSchSNP} to prove that double Schubert polynomials have SNP and characterize their Newton polytopes. We also leverage the following results about matroid polytopes to discuss products of linear polynomials in Section~\ref{section:SCNP} and characterize the Newton polytope of dual Schubert polynomials in Section~\ref{section:newtongeneralizedpermutahedra}. \begin{defi} A \emph{matroid} $M = (E, \B)$ consists of a finite set $E$ and a nonempty collection of subsets $\B$ of $E$, called the \emph{bases} of $M$, which satisfy the \emph{basis exchange axiom}: if $B_1, B_2\in \B$ and $b_1\in B_1 \setminus B_2$, then there exists $b_2\in B_2 \setminus B_1$ such that $B_1 \setminus \{b_1\}\cup \{b_2\}\in \B$. \end{defi} In the remainder of this section, we let $E = [n]$. \begin{defi} The \emph{matroid polytope} $P(M)$ of a matroid $M = ([n], \B)$ is \[P(M) = \conv(\{\zeta^B : B\in \B\}),\] where $\zeta^B = (\one_{i\in B})_{i=1}^n$ denotes the indicator vector of $B$. \end{defi} Generalized permutahedra were first studied in~\cite{postnikovpermutohedra}, and many nice connections to matroid polytopes have been found since. A \emph{standard permutahedron} (or \emph{permutohedron}) is the convex hull in $\R^n$ of the vector $(0, 1, \dots, n-1)$ and all permutations of its entries. \emph{Generalized permutahedra}, which are deformations of standard permutahedra, are defined as follows. \begin{defi} The \emph{generalized permutahedron} $P_n^z(\{z_I\})$ associated to the collection of real numbers $\{z_I\}$ for $I\subseteq [n]$ is given by \[P_n^z(\{z_I\}) = \left\{t\in\R^n : \sum_{i\in I} t_i\ge z_I \text{ for } I\neq [n], \sum_{i=1}^n t_i = z_{[n]}\right\}.\] \end{defi} \begin{prop}[\cite{MatroidPolytopes}]\label{prop:permutahedraminkowskisum} Generalized permutahedra are closed under Minkowski sums: \[P_n^z(\{z_I\}) + P_n^z(\{z_I'\}) = P_n^z(\{z_I + z_I'\}).\] \end{prop} \begin{defi}\label{def:rankfunction} For a matroid $M = ([n], \B)$, the \emph{rank function} $r_M: 2^{[n]}\to\ZZ_{\ge 0}$ on subsets of $[n]$ is given by \[r_M(S) = \max\{\#(S\cap B) : B\in\B\}.\] \end{defi} \begin{prop}[\cite{MatroidPolytopes}]\label{prop:matroidsarepermutahedra} Matroid polytopes are generalized permutahedra with \begin{align*} P(M) &= P_n^z(\{r_M([n]) - r_M([n]\setminus I)\})\\ &= \left\{t\in\R^n : \sum_{i\in I} t_i\le r_M(I) \text{ for } I\neq [n], \sum_{i=1}^n t_i = r_M([n])\right\}. \end{align*} \end{prop} \begin{defi}(\cite{DicreteConvexAnaly}) A subset $\mathcal{J} \subset \ZZ^n$ is \emph{M-convex} if for any index $i \in [n]$ and any $\alpha, \beta \in \mathcal{J}$ whose $i$th coordinates satisfy $\alpha_i > \beta_i$, there is an index $j \in [n]$ satisfying \[ \alpha_j < \beta_j \quad \text{and} \quad \alpha - e_i + e_j \in \mathcal{J} \quad \text{and} \quad \beta - e_j + e_i \in \mathcal{J}. \] A polynomial is \emph{M-convex} if $\supp(f)$ is an M-convex set. \end{defi} \begin{prop}\textup{(}\cite[Theorem 4.15]{DicreteConvexAnaly},~\cite{HuhMeszaroLorSchur}\textup{)}\label{prop:Mconvex=SNP+GP} A homogeneous polynomial $f$ is M-convex if and only if $f$ has SNP and $\Newton(f)$ is a generalized permutahedron. \end{prop} \section{M-convexity of dual Schubert polynomials}\label{section:Mconvexity} In this section, we prove Theorem~\ref{theorem:support} and Corollary~\ref{thm:M-conv}. Our key insight is that the support of any dual Schubert polynomial $D^w$ always matches the support of the weight of a specific chain in $[\id,w]$. After showing that the weight of any chain has SNP and has a Newton polytope that is a generalized permutahedron, we obtain the desired result. \subsection{The single chain Newton polytope (SCNP) property}\label{section:SCNP} We introduce the {single chain Newton polytope} property and show that it implies, but is not equivalent to, the SNP property. \begin{defi} \label{SCNP} The Postnikov--Stanley polynomial $D_{u}^w$ has \emph{single chain Newton polytope (SCNP)} if there exists a saturated chain $C$ in the interval $[u, w]$ such that \[\supp(m_C) = \supp(D_u^w).\] Such a saturated chain $C$ is called a \emph{dominant chain} of the interval $[u, w]$. \end{defi} \begin{exam} Given the Postnikov--Stanley polynomial $D_{213}^{321} = \frac{1}{2!}(x_1 x_2 + (x_1 + x_2)\cdot x_2)$, the saturated chain $C = (213 \lessdot 312 \lessdot 321)$ has weight $m_C = (x_1 + x_2)\cdot x_2$, which satisfies \[\supp(m_C) = \supp(D_{213}^{321}).\] Thus, $C$ is a dominant chain of $[213, 321]$, and $D_{213}^{321}$ has SCNP. \end{exam} \begin{rema}\label{example:13244231} The SCNP property is stronger than the SNP property: for example, $D_{1324}^{4231}$ has SNP but not SCNP, according to calculations with SageMath~\cite{sagemath}. As Postnikov--Stanley polynomials do not necessarily have SCNP, the method of using SCNP to prove SNP for dual Schubert polynomials does not generalize to Postnikov--Stanley polynomials. \end{rema} The following propositions motivate the definition of SCNP. \begin{prop}\label{prop:linearprodSNP} If a polynomial $f\in \R[x_1,\dots,x_n]$ can be written as a product of nonnegative linear combinations of $x_1, \dots, x_n$, then $f$ has SNP. \end{prop} \begin{proof} This follows from \cite[Theorem 3.4]{2009minkowski}. \end{proof} \begin{prop}\label{prop:SCNPtoSNP} If $D_u^w$ has SCNP, then $D_u^w$ has SNP. \end{prop} \begin{proof} By Proposition~\ref{prop:linearprodSNP}, the chain weight $m_C$ has SNP for any saturated chain $C$ in the Bruhat order. If, by the definition of SCNP, there exists a saturated chain $C$ in the interval $[u, w]$ such that $\supp(m_C) = \supp(D_u^w)$, then $D_u^w$ also has SNP. \end{proof} \subsection{Using SCNP to prove SNP}\label{subsec:dualschubSCNP} In this section, we prove that dual Schubert polynomials have SCNP. As a corollary, we obtain Theorem~\ref{theorem:support} and the result that dual Schubert polynomials have SNP. \begin{defi} For a Bruhat interval $[u,w]$, a saturated chain \[u = w_0\lessdot w_1\lessdot w_2\lessdot \dots \lessdot w_{\ell} = w\] from $u$ to $w$ is a \emph{greedy chain} if it satisfies the following condition for all $i\in [\ell]$: writing $w_{i}=w_{i-1}t_{ab}$ for $a < b$, there does not exist $w'_{i-1}\lessdot w_{i}$ with $w'_{i-1} \in [u,w]$ such that \begin{enumerate}[label=\textnormal{(\roman*)}] \item $w_{i}=w'_{i-1}t_{ab'}$ for $b'>b$, or \item $w_{i}=w'_{i-1}t_{a'b}$ for $a' b$ be the smallest integer such that $w(r)\in [w(b), w(a)]$; note that such an $r$ exists because $j > b$ has this property. Then $\ell(wt_{ar})=\ell(w)-1$, which contradicts the fact that $C$ is a greedy chain. Case~(iv) is similar to case (ii). In conclusion, we have $\Inv(w_{\ell-1})=\Inv(w)\setminus \{(a,b)\}$, which implies \[\GW(w)=\GW(w_{\ell-1})\cdot (x_{a}+x_{a+1}+\dots+x_{b-1}),\] as desired. \end{proof} \begin{defi}\label{def:dominant pairing} We define a partial order $\preceq$ on $\{(a,b)\in \N^2\mid a