%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2024}
\articlenumber{91}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{example}{Example}
\newtheorem{remark}{Remark}
\newtheorem{definition}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{alg}{Algorithm}

\usepackage{lipsum}

\usepackage{tikz}
\usepackage{caption}
\usepackage{subcaption}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% fonts, commands, etc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\newcommand{\C}{{\mathbb{C}}}
\renewcommand{\H}{{\mathbb{H}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\Q}{{\mathbb{Q}}}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\N}{{\mathbb{N}}}
\newcommand{\T}{{\mathbb{T}}}
\renewcommand{\P}{{\mathbb{P}}}
\renewcommand{\SS}{{\mathbb{S}}}
\newcommand{\SSS}{\mathds{S}}
\newcommand{\id}{\mathds{1}}
\newcommand{\bfa}{\mathbf{a}}


\newcommand{\capprod}{\smallfrown}
\newcommand{\cupprod}{\smallsmile}

\newcommand{\hcup}{\smallsmile}
\newcommand{\hcap}{\smallfront}

\newcommand{\kcup}{\cdot}
\newcommand{\kcap}{\smallfrown}
\newcommand{\less}{\!\setminus\!}
\newcommand{\dirac}{\mbox{$\not\negthinspace\partial$}}

\renewcommand{\t}{\mathfrak{t}}
\newcommand{\su}{\mathfrak{su}}
\newcommand{\g}{\mathfrak{g}}
\newcommand{\algs}{\mathfrak{s}}
\newcommand{\h}{\mathfrak{h}}
\newcommand{\p}{\mathfrak{p}}
\renewcommand{\k}{\mathfrak{k}}
\renewcommand{\a}{\mathfrak{a}}
\renewcommand{\b}{\mathfrak{b}}
\renewcommand{\iff}{\Leftrightarrow}
\newcommand\tensor{\otimes}
\newcommand\Tensor{\bigotimes}
\newcommand{\grad}{\rm grad\mbox{ }}
\newcommand{\fl}{\mathscr{F}\ell}
\newcommand{\spn}{\mathfrak{sp}_n}

\newcommand{\into}{\hookrightarrow}
\newcommand{\onto}{\twoheadrightarrow}
\newcommand\lie[1]{{\mathfrak #1}}

%\renewcommand{\mod}{\mathbin{/\!/}}
\newcommand{\modzero}{{/\!\!/\!_{0}\,}}
\newcommand{\mmod}{{/\!\!/\!\!/\!\!/}}
\newcommand{\defi}{\textbf}
\newcommand{\dom}{\backslash}
\newcommand{\pf}{\text{pf}}
\newcommand{\init}{\mathop{\mathrm{init}}}


% \newcommand{\cal}{\mathcal{}}

\newcommand{\clmnd}{c_{\lambda, \mu}^{\nu,d}}
\newcommand{\wideclmnd}{\widetilde{c_{\lambda, \mu}^{\nu,d}}}
\newcommand{\wt}{\operatorname{wt}}
\newcommand{\wtv}{\operatorname{wt}^v}
\newcommand{\wth}{\operatorname{wt}^h}
\newcommand{\sh}{\operatorname{sh}}

\newcommand\sbullet[1][.5]{\mathbin{\vcenter{\hbox{\scalebox{#1}{$\bullet$}}}}}
\newcommand\sasterisk[1][.5]{\mathbin{\vcenter{\hbox{\scalebox{#1}{$\coAsterisk$}}}}}
\newcommand\stimes[1][.5]{\mathbin{\vcenter{\hbox{\scalebox{#1}{$\times$}}}}}
\newcommand\sstar[1][.5]{\mathbin{\vcenter{\hbox{\scalebox{#1}{$\star$}}}}}


\definecolor{limegreen}{rgb}{0.2, 0.8, 0.2}
\definecolor{amethyst}{rgb}{0.6, 0.4, 0.8}
\definecolor{deeppink}{rgb}{1.0, 0.08, 0.58}
\newcommand{\liz}{\textcolor{limegreen}}
\newcommand{\sarah}{\textcolor{blue}}
\newcommand{\yuxuan}{\textcolor{deeppink}}
\newcommand{\brown}{\textcolor{brown}}
\newcommand{\red}{\textcolor{red}}
\newcommand{\yellow}{\textcolor{yellow}}
\newcommand{\purple}{\textcolor{amethyst}}
\newcommand{\orange}{\textcolor{orange}}
\newcommand{\green}{\textcolor{limegreen}}
\newcommand{\blue}{\textcolor{blue}}

\newcommand\blfootnote[1]{%
  \begingroup
  \renewcommand\thefootnote{}\footnote{#1}%
  \addtocounter{footnote}{-1}%
  \endgroup
}

%% define your title in the usual way
\title[Crystal Chute Moves on Pipe Dreams]{Crystal Chute Moves on Pipe Dreams}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
% \author[Optional shorter names]{Longer names me\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}\addressmark{1}, \and you\addressmark{2}}
\author{Sarah Gold\addressmark{1}, Elizabeth Mili\'cevi\'c\addressmark{2}, \and Yuxuan Sun\thanks{\href{mailto:sun00816@umn.edu}{sun00816@umn.edu}}\addressmark{3}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Upper School Mathematics, Friends' Central School, Wynnewood, PA 19096 \\ \addressmark{2}Department of Mathematics, Haverford College, Haverford, PA 19041 \\ \addressmark{3}School of Mathematics, University of Minnesota Twin Cities, Minneapolis, MN 55455}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{Schubert polynomials represent a basis for the cohomology of the complete flag variety and thus play a central role in geometry and combinatorics. In this context, Schubert polynomials are generating functions over various combinatorial objects, such as rc-graphs or reduced pipe dreams. By restricting Bergeron and Billey’s chute moves on rc-graphs, we define a Demazure crystal structure on the monomials of a Schubert polynomial.  As a consequence, we provide a method for decomposing Schubert polynomials as sums of key polynomials, complementing related work of Assaf and Schilling via reduced factorizations with cutoff, as well as Lenart’s coplactic operators on biwords.}

%% put your French abstract here, or comment this out if you don't have one
% \resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Schubert polynomial, pipe dream, rc-graph, chute move, Demazure crystal} %%!!!!!!



%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}

Schubert polynomials are fundamental objects which lie at the intersection of geometry, representation theory, and algebraic combinatorics. By a classical theorem of Borel, the cohomology of the manifold of complete flags in $\mathbb{C}^n$ with integer coefficients is canonically isomorphic to the quotient of $\mathbb{Z}[x_1, \dots, x_n]$ by the ideal generated by the symmetric polynomials without constant term \cite{Borel}. The geometry of the flag variety is best captured by the cohomology classes of the Schubert varieties, which correspond to Schubert polynomials under Borel's isomorphism, generalizing the role of the Schur polynomials in the cohomology of the Grassmannian. In addition to encoding geometric information about the flag variety, individual Schubert polynomials also exhibit rich combinatorial and representation theoretic structures, as developed in \cite{LS-NCschuberts, KohnertThesis, reiner_key_1995, lenart_unified_2004, assaf_demazure_2018} and explored further in the present work.


\subsection{Schubert and key polynomials}

Given any permutation $w \in S_n$, the \emph{Schubert polynomial} $\mathfrak{S}_w \in \Z[x_1, \dots, x_n]$ can be calculated recursively using a sequence of divided difference operators, by the original definition of Lascoux and Sch\"utzenberger \cite{LS-schuberts}, inspired by the work of Demazure \cite{Demazure} and Bernstein--Gel$'$fand--Gel$'$fand \cite{BGG}. 
Based on a conjecture of Stanley, the first combinatorial formula for Schubert polynomials was given by Billey, Jockusch, and Stanley using the language of \emph{rc-graphs} \cite{billey_combinatorial_1993}, with an alternate proof by Fomin and Stanley \cite{fomin_schubert_1994}.  An equivalent combinatorial description for Schubert polynomials was later provided by Fomin and Kirillov \cite{FominKirillov}, rebranded by Knutson and Miller as \emph{reduced pipe dreams} \cite{KnutsonMiller}, following the conventions of Bergeron and Billey \cite{BilleyBergeron}. Besides being attractive ways to visually represent Schubert polynomials, pipe dreams generalize to flag manifolds the role of the semistandard Young tableaux for Grassmannians, while admitting generalizations to other cohomological contexts.


 

Many combinatorial models for Schubert polynomials also involve a family of operators, which permute the individual monomials. To highlight several examples most closely related to this work, Bergeron and Billey define \emph{chute and ladder moves} on rc-graphs  \cite{BilleyBergeron}, the inspiration for which they attribute to Kohnert's thesis \cite{KohnertThesis}.  Miller provides a mitosis algorithm which lists reduced pipe dreams recursively by induction on the weak order on $S_n$ \cite{Miller}.
Lenart develops operations on biwords which correspond to the coplactic operators on tableaux \cite{lenart_unified_2004}. Morse and Schilling define a family of operators on \emph{reduced factorizations} in \cite{MorseSchilling}, which restricts to an action on Schubert polynomials via the semi-standard key tableaux of Assaf and Schilling \cite{assaf_demazure_2018}. 

All of the operators mentioned above encode useful combinatorics about Schubert polynomials; however, some of them additionally carry representation-theoretic information. The most natural approach to track the representation theory is often through Kashiwara's \emph{crystals} \cite{KashiwaraCrystal}, which are graphical models for the irreducible representations of a complex semisimple Lie algebra.  Lenart summarizes many results in \cite{lenart_unified_2004} using the language of crystal operators rooted in a \emph{pairing process} on rc-graphs, though the details are carried out via jeu de tacquin on biwords, most naturally associated with the combinatorics of semistandard Young tableaux. More explicitly, Assaf and Schilling prove in \cite[Theorem 5.11]{assaf_demazure_2018} that the set of all reduced factorizations for $w \in S_n$ satisfying an additional \emph{cutoff criterion} decomposes as a union of Demazure crystals.


The decomposition of a combinatorial model for Schubert polynomials into a union of Demazure crystals thus also yields a description of how $\mathfrak{S}_w$ is expressed as a sum of key polynomials $\kappa_a$, as in \cite[Corollary 5.12]{assaf_demazure_2018}. Tableaux versions of such formulas include the original of Lascoux and Sch\"utzenberger \cite{LS-NCschuberts}, a related result of Reiner and Shimozono \cite{reiner_key_1995} on factorized row-frank words, and so on. The main goal of this paper is to provide such a decomposition for Schubert polynomials as sums of key polynomials, expressed in terms of reduced pipe dreams.



\subsection{Main results}

Inspired by the chute moves of \cite{BilleyBergeron} on rc-graphs,  we develop a crystal structure on the monomials of a Schubert polynomial, giving a method for decomposing Schubert polynomials as sums of key polynomials, complementing the closely related works \cite{assaf_demazure_2018, lenart_unified_2004}.
Our \emph{crystal chute moves} on reduced pipe dreams are either raising or lowering operators, denoted $e_i$ and $f_i$, respectively.  If the raising operator $e_i(D)$ applied to a reduced pipe dream $D$ for the given permutation $w \in S_n$ equals zero for all $1 \leq i <n$, then we say $D \in RP(w)$ is a \emph{highest weight pipe dream}. We direct the reader to Section \ref{sec:schuberts} for precise definitions of all relevant terminology. 

The highest weight pipe dreams naturally index the key polynomials in the decomposition below, as they are in bijection with a pair consisting of a partition $\lambda_D$ having $n$ parts and a permutation $\pi_D \in S_n$, such that $\a_D = \pi_D(\lambda_D)$ for a unique composition $a_D$. 


\begin{thm}\label{thm:main-key} 
Given any $w \in S_n$, the Schubert polynomial may be expressed as 
\begin{equation*}
    \mathfrak{S}_w(x_1, \dots, x_n) = \sum\limits_{\substack{D \in RP(w) \\ e_i(D) = 0,\; \forall 1 \leq i < n}} \kappa_{a_D}(x_1, \dots, x_n),
\end{equation*}
where the composition $a_D = \operatorname{wt}(\widetilde{D})$ for a diagram $\widetilde{D}$ constructed from the highest weight pipe dream $D$; see Algorithm~\ref{alg:EG} for details.
\end{thm}

Figure \ref{fig:main-ex} on the next page shows how $\mathfrak{S}_{[21543]}$ decomposes as the sum of three key polynomials, indexed by the three pipe dreams with no incoming lowering edges, having weights $\lambda_D \in \{(2,1,1,0), (2,2,0,0), (3,1,0,0)\}$ recording the number of crosses in each row, with respective truncating permutations $\pi_D \in \{ s_2s_1s_3,s_2,s_3s_2\}$ read from the edges.



\begin{figure}
    \centering
    \includegraphics[scale=1.15]{chuteCrystalGraph.pdf}
    \caption{The Demazure crystal structure on reduced pipe dreams for $w = [21543]$. Crosses that will be moved by the lowering operators $f_i$ are in shown green.}
    \label{fig:main-ex}
\end{figure}

\section{A Crystal Structure on Pipe Dreams}\label{sec:schuberts}



In this section, we review the combinatorics of Schubert polynomials in the language of reduced pipe dreams. We then define crystal chute moves by restricting the chute moves of \cite{BilleyBergeron} on rc-graphs via a pairing process. 



\subsection{Schubert polynomials and pipe dreams}\label{sec:pipedreams}


Reduced pipe dreams index the monomials of Schubert polynomials, as we review in Theorem \ref{thm:PDSchub}. Fix an $n \in \N$ and consider the $n\times n$ grid, indexed such that the box in row $i$ from the top and column $j$ from the left is labeled by $(i,j)$, as for matrix entries. A \emph{pipe dream} is a diagram $D$ obtained by covering each box on the grid with one of two square tiles: a cross \includegraphics[height=\fontcharht\font`\B]{cross.pdf}  or an elbow \includegraphics[height=\fontcharht\font`\B]{elbow.pdf}. Further, crosses are only permitted in boxes $(i,j)$ such that $i+j \leq n$, so we will typically only draw the portion of $D$ which lies on or above the main anti-diagonal. 


By connecting the crosses and elbows on each tile in the unique possible way, as shown in Figure \ref{fig:main-ex}, we can view the resulting diagram as a network of \emph{pipes} moving north and east, with water flowing in from the left of the grid and out at the top. 
The water in each pipe enters and exits from a unique pair of row and column indices, so that each pipe dream corresponds to a permutation on the set $[n] = \{1, \dots, n\}$ as follows. The one-line notation for a permutation $w \in S_n$ records the action of $w$ on $[n]$ in the form $w = [w_1 \cdots w_n]$, where we write $w_i = w(i)$ for brevity. A diagram $D$ is a pipe dream \emph{for the permutation} $w = [w_1 \cdots w_n]$ if the pipe entering row $i$ exits from column $w_i$ for all $i \in [n]$. For example, each of the diagrams in Figure \ref{fig:PDex} below is a pipe dream for the same permutation $w = [21543] \in S_5$. 


\begin{figure}[ht]
    \centering
    \includegraphics[scale=1.2]{PDex.pdf}
    \caption{Several reduced pipe dreams for $w = [21543] \in S_5$.}
    \label{fig:PDex}
\end{figure}


A pipe dream is \emph{reduced} if each pair of pipes crosses at most once, as in Figure \ref{fig:PDex}. Denote by $RP(w)$ the set of all reduced pipe dreams for a given permutation $w$. We denote by $D_+$ the set of all boxes of $D$ which are covered by a cross; note that $D_+$ uniquely determines $D$.  Provided that the pipe dream is reduced, \cite[Lemma 1.4.5]{KnutsonMiller} says that the number of crosses in $D \in RP(w)$ equals the length of the permutation, or the number of its inversions, given by $|D_+| = \ell(w) = \#\{ i < j \mid w_i > w_j\}$.

The \emph{weight of a pipe dream} $D \in RP(w)$, denoted by $\wt(D)$, is the weak composition of $\ell(w)$ whose $i^{\text{th}}$ coordinate equals the number of crosses in row $i$ of $D$.  For example, the three weight vectors corresponding to the pipe dreams from Figure \ref{fig:PDex} below are $(2,1,1,0), (2,2,0,0),$ and $(3,1,0,0)$ recorded from left to right, all of which happen to be partitions in this example. 


Schubert polynomials are generating functions over reduced pipe dreams, as illustrated by the following result, originally proved by Billey, Jockusch and Stanley \cite{billey_combinatorial_1993}, later reproved by Fomin and Stanley \cite{fomin_schubert_1994}, and recorded here in the language of pipe dreams.

\begin{thm}[Corollary 2.1.3 \cite{KnutsonMiller}]\label{thm:PDSchub}
Let $w \in S_n$. Then
\begin{equation}\label{eq:SchubPD}
    \mathfrak{S}_w(x_1, \dots, x_n) = \sum\limits_{D \in RP(w)} \mathbf{x}^{\wt(D)}.
\end{equation}
\end{thm}

\noindent We use $\mathbf{x}$ to denote a monomial in the variables $x_1, \dots, x_n$. Given any vector $\mathbf{v} = (v_1, \dots, v_n) \in \Z_{\geq 0}^n$, the notation $\mathbf{x}^{\mathbf{v}} = x_1^{v_1}\cdots x_n^{v_n}$ is used throughout.



\subsection{Crystal chute moves}\label{sec:crystalchutes}

In this section, we describe a family of operators on the set $RP(w)$ of reduced pipe dreams for a given permutation, which we show in our main theorem  produces a Demazure crystal structure on the monomials of $\mathfrak{S}_w$.

\begin{definition}\label{def:pairing}
Given a reduced pipe dream \(D\) for a permutation in $S_n$, fix a row index $i \in [n]$. Denote the rightmost cross in row \(i\) by $c$.  (Since crosses only occur in boxes $(i,j)$ such that $i + j \leq n$, then $D$ has no crosses in row $n$.) We define a \emph{pairing process on row} $1 \leq i <n$ of $D$ as follows:
	 \begin{enumerate}
        \item Look for an unpaired cross $c_+$ in row \(i+1\) such that $c_+$ lies weakly to the right of $c$ in $D$. If there are multiple such $c_+$, choose the leftmost $c_+$.
   \begin{enumerate}
       \item If such $c_+$ exists, we say that $c$ and $c_+$ are \emph{paired}. 
       \item If no such $c_+$ exists, we say that $c$ is \emph{unpaired}.
   \end{enumerate}
		 \item Denote by $c'$ the cross in row $i$ which is both closest to $c$ and lies to the left of $c$.
   \begin{enumerate}
       \item If such $c'$ exists, we reset \(c := c'\) and start again from step (1). 
       \item If no such $c'$ exists, the pairing process on row $i$ is complete.
   \end{enumerate}
	\end{enumerate}
\end{definition}


We illustrate the pairing process on the righthand pipe dream from Figure \ref{fig:PDex} below.

\begin{example}\label{ex:pairing}
 Fix $i=1$ and identify $c = (1,4)$ as the rightmost cross in row 1. Since there are no crosses in row 2 which lie weakly right of $c$, then $c_+$ does not exist and $c$ is unpaired in step (1b). 

 \begin{figure}[h!]
    \centering
    \includegraphics[scale=1.2]{pair.pdf}
    \caption{The pairing process applied to row 1 of a reduced pipe dream. We color paired crosses green and unpaired crosses red.}
    \label{fig:pairing}
\end{figure}

In step (2), we identify $c' = (1,3)$ as the cross in row 1 closest to and left of the original $c=(1,4)$. We thus return to step (1) applied to $c=(1,3)$. We identify $c_+ = (2,3)$ as a cross in row 2 which is weakly right of $c = (1,3)$, and so these crosses get paired in step (1a).

The only remaining cross $c' = (1,1)$ is unpaired since all crosses in row 2 are now paired. The pairing process is complete, having analyzed all crosses in row 1.
\end{example}



After running the pairing process on row $i$ of $D \in RP(w)$, we define an operator $f_i$ on $D$ which produces another element of $RP(w)$ whenever it is nonzero.



\begin{definition}\label{def:crystalchutes} 
    Let $D \in RP(w)$ for $w \in S_n$. Fix an $1 \leq i < n$ and run the pairing process on row $i$ of $D$.
    If all crosses in row $i$ are paired, then set $f_i(D) = 0$.  Otherwise, denote by $(i,j)\in D_+$ the leftmost unpaired cross in row $i$. 
    
    If $(i,k) \in D_+$ for all $1 \leq k \leq j$, then set $f_i(D) = 0$. Otherwise, define $m \in \N$ such that:
    \begin{enumerate}
        \item[(a)] $(i,j-m), (i+1, j-m) \notin D_+$ and
        \item[(b)] $(i,j-k), (i+1,j-k) \in D_+$ for all $1 \leq k <m$.
    \end{enumerate}
    Define a new diagram $f_i(D)$ by
    \begin{equation*}
        f_i(D)_+ = \left\{D_+ \backslash (i,j) \right\} \cup \{(i+1, j-m)\}.
    \end{equation*}
    The family of operators $f_i$ for $1 \leq i <n$ are called \emph{(lowering) crystal chute moves}.
\end{definition}

    In words, the crystal chute move $f_i$ exchanges the leftmost unpaired cross at $(i,j)$ and the elbow at $(i+1, j-m)$, where $m$ is chosen such that the rectangle strictly between this pair of tiles is filled by crosses.  
    


We now illustrate how to apply the crystal chute moves on a reduced pipe dream.

\begin{example}\label{ex:fpipes}

Consider the sequence shown in Figure \ref{fig:crystalchute-ex}, in which we instead begin with the lefthand pipe dream $D$ for $w = [21543]$ from Figure \ref{fig:PDex}.  If we run the pairing process on row 1, the leftmost unpaired cross is $(1,4) \in D_+$. Properties (a) and (b) hold for $m=1$, and the corresponding rectangle of crosses between $(1,4) \in D_+$ and the elbow at $(2,3)$ is empty in this case. To apply $f_1$, the red cross in $(1,4)$ moves to the blue elbow in position $(2,3)$, resulting in the middle diagram in Figure \ref{fig:crystalchute-ex}.  

  \begin{figure}[ht]
    \centering
    \includegraphics[scale=1.2]{crystalchute-ex.pdf}
    \caption{Applying a sequence of crystal chute moves to a reduced pipe dream.}
    \label{fig:crystalchute-ex}
    \end{figure}

    Running the pairing process next on row 2 of the middle pipe dream, $(2,3)$ is the leftmost unpaired cross, and $m=2$, corresponding to the tile of paired crosses in rows 2 and 3 which are preserved under applying $f_2$.  Here instead, the red cross at $(2,3)$ jumps over this rectangle of crosses to the blue elbow in position $(3,1)$, resulting in the third diagram in Figure \ref{fig:crystalchute-ex}.

\end{example}


We now define a second family of operators $e_i$ to be precisely the inverse of the crystal chute moves from Definition \ref{def:crystalchutes}.

\begin{definition}\label{def:inversechutes}
Let $D \in RP(w)$ for $w \in S_n$. Fix an $1 \leq i < n$ and run the pairing process on row $i$ of $D$. If all crosses in row $i+1$ are paired, then set $e_i(D)=0$. Otherwise, denote by $(i+1,\ell) \in D_+$ the rightmost unpaired cross in row $i+1$.

Let $n>\ell$ be minimal such that $(i+1,n) \notin D_+$. Define a new diagram $e_i(D)$ by
   \begin{equation*}
             e_i(D)_+ = \left\{D_+ \backslash (i+1,\ell) \right\} \cup \{(i, n)\}.
   \end{equation*}
   The family of operators $e_i$ for $1 \leq i < n$ are called \emph{(raising) crystal chute moves}.
\end{definition}


We now have well-defined raising and lowering operators on reduced pipe dreams.

\begin{proposition}\label{prop:e_iwelldef}
    The raising crystal chute move $e_i: RP(w) \to RP(w) \cup \{0\}$ is well-defined for all $1 \leq i < n$, satisfying $\wt(e_i(D)) = \wt(D) + \alpha_i$ for any $D \in RP(w)$. Moreover, the raising and lowering crystal chute moves are mutually inverse.
\end{proposition}


The pipe dreams $D$ on which $e_i(D) = 0$ for all $1 \leq i < n$ play a distinguished role in the statement of Theorem \ref{thm:main} below, so we highlight them here.

\begin{definition}
     If $e_i(D)=0$ for all $1 \leq i <n$, then $D$ is a \emph{highest weight pipe dream}. %If $f_i(D)=0$ for all $1 \leq i <n$, then we refer to $D$ as a \emph{lowest weight pipe dream}. 
\end{definition}



\subsection{Demazure crystals and the main theorem}\label{sec:mainthm}

We refer the reader to \cite{bump_crystal_2017} for more background on crystals. Given a partition $\lambda$ with $n$ parts, the type $A_{n-1}$ crystal of highest weight $\lambda$ is denoted by $B(\lambda)$, and the character of the crystal $B(\lambda)$ is the Schur polynomial $s_\lambda(x_1, \dots, x_n)$. 

Demazure crystals are subsets of $B(\lambda)$ truncated by a permutation which restricts the set of raising and lowering operators. More precisely, for any subset $X \subseteq B(\lambda)$ and any index $1 \leq i < n$, we define $\mathfrak{D}_i$ in terms of lowering operators as
\begin{equation*}
\mathfrak{D}_i (X) = \{ b \in B(\lambda) \mid b \in f^k_i(X)\; \text{for some}\; k \geq 0\}.
\end{equation*}
Now given any $\pi \in S_n$, write $\pi = s_{i_1} \cdots s_{i_p}$ as a product of simple transpositions $s_i = (i, i+1)$ where the expression for $\pi$ is reduced, meaning that $p= \ell(\pi)$ is minimal. If $u_\lambda$ denotes the highest weight element of $B(\lambda)$, the \emph{Demazure crystal} associated to the pair $(\lambda, \pi)$ is defined by
\begin{equation*}
    B_\pi(\lambda) = \mathfrak{D}_{i_1} \cdots \mathfrak{D}_{i_p}(u_\lambda).
\end{equation*}
The character of the Demazure crystal $B_\pi(\lambda)$ generalizes the Demazure characters of \cite{Demazure-characters}, as conjectured by Littelmann \cite{Littelmann} and proved by Kashiwara \cite{Kashiwara}. Moreover, the character of the Demazure crystal $B_\pi(\lambda)$ is the key polynomial $\kappa_a(x_1, \dots, x_n)$ indexed by the composition $a$ such that $a = \pi(\lambda)$. 


Our main theorem says that the set of reduced pipe dreams for a permutation admits a Demazure crystal structure determined by the crystal chute moves from Section \ref{sec:crystalchutes}.

\begin{thm}\label{thm:main} 
Given any $w \in S_n$, the operators $e_i$ and $f_i$ for $1 \leq i < n$ define a type $A_{n-1}$ Demazure crystal structure on $RP(w)$. That is, 
\begin{equation*}
    RP(w) \cong \bigcup\limits_{\substack{D \in RP(w) \\ e_i(D) = 0,\; \forall 1 \leq i < n}} B_{\pi_D}(\wt(D)),
\end{equation*}
where the truncating permutation $\pi_D$ is the shortest permutation such that $\operatorname{wt}(\widetilde{D}) = \pi_D(\wt(D))$, for a diagram $\widetilde{D}$ constructed algorithmically from the highest weight pipe dream $D$; see Theorem~\ref{thm:AlgCor}.
\end{thm}


\noindent Theorem \ref{thm:main} is the pipe dream analog of \cite[Theorem 5.11]{assaf_demazure_2018}, phrased there in terms of reduced factorizations for $w$ meeting a cutoff condition. Refer to Figure \ref{fig:main-ex} in the introduction to see how $RP([21543])$ decomposes into the union of three Demazure crystals.



\section{Permutation Indexing the Demazure Crystal}\label{sec:permutation}

This section explains the algorithm for identifying the truncating permutation from a highest weight pipe dream, equivalently the composition defining the corresponding key polynomial. We begin by describing how to obtain a new diagram $\widetilde{D}$ from any highest weight pipe dream $D$.

\begin{alg}\label{alg:EG}
Let $D$ be a highest weight pipe dream.
\begin{enumerate}
    \item For each cross in row $i$, shift it to the right by $i-1$.
    \item For each row, beginning in the lowest row, move the leftmost cross down to the row such that its row and column index match. Fix these crosses.
    \item Set $\ell = 2$.
    \begin{enumerate}
        \item Beginning at the bottom row containing unfixed crosses, consider the leftmost unfixed cross. Move that cross down to the lowest possible row, remaining in its current column, such that:
        \begin{enumerate}
            \item The cross may not move through other crosses;
            \item The cross is the $\ell^\text{th}$ cross from the left in its new row; and
            \item The cross does not have any previously fixed crosses to its right in the new row.
        \end{enumerate}
        \item Fix this moved cross.
        \item Repeat steps (a) and (b) untill all rows with unfixed crosses have been considered.
    \end{enumerate}
    \item Increment $\ell$ by 1, and repeat step (3).
\end{enumerate}
Once all crosses are fixed, the algorithm terminates. Denote the resulting diagram by $\widetilde{D}$.
\end{alg}


We illustrate Algorithm~\ref{alg:EG} on an example.


\begin{example}\label{ex:alg}
    Consider the permutation $w = [4726315] \in S_7$. One of its highest weight pipe dreams $D$ is depicted in Figure \ref{fig:highestWeights}.      The result after applying steps (1) and (2) of Algorithm \ref{alg:EG} to $D$ is in Figure \ref{fig:crossesShifted}, with fixed crosses marked in red. 

\begin{figure}[ht]
\centering
\begin{minipage}{.5\textwidth}
  \centering
  \includegraphics[width=.8\linewidth]{step1.pdf}
  \captionof{figure}{A highest weight pipe dream $D$ for  $w = [4726315] \in S_7$.}
  \label{fig:highestWeights}
\end{minipage}%
\begin{minipage}{.5\textwidth}
  \centering
  \includegraphics[width=.8\linewidth]{step3.pdf}
  \captionof{figure}{The result of applying steps (1) and (2) of Algorithm \ref{alg:EG} to $D$.}
  \label{fig:crossesShifted}
\end{minipage}
\end{figure}

\begin{figure}[ht]
\centering
\begin{minipage}{.5\textwidth}
  \centering
  \includegraphics[width=.8\linewidth]{step4.pdf}
  \captionof{figure}{The diagram after completing the first iteration of step (3).}
  \label{fig:ellIs2}
\end{minipage}%
\begin{minipage}{.5\textwidth}
  \centering
  \includegraphics[width=.8\linewidth]{step5.pdf}
  \captionof{figure}{The diagram $\widetilde{D}$ after completing Algorithm \ref{alg:EG}.}
  \label{fig:ellIs5}
\end{minipage}
\end{figure}



     We now move to the iterative step (3). Set $\ell = 2$. We begin on the lowest row with an unfixed cross, that being row $3$. We move the leftmost unfixed cross in this row, that being the cross at $(3,5)$, down in its column to a position that meets criteria (i) through (iii). We first observe that there is a cross at $(5,5)$, meaning that we are unable to move our cross to row $5$ or any row below it. Our only option is to move this cross to row $4$. Observe that a cross at $(4,5)$ would be the second cross in its row. Thus, we move the cross at $(3,5)$ to $(4,5)$ and fix it there.


    The two crosses at $(2,3)$ and $(1,2)$ cannot move lower without violating (i).  These two crosses are thus also fixed, completing the round of moves for $\ell=2$.
     At the end of this round, we obtain the diagram shown in Figure \ref{fig:ellIs2}. We then increment $\ell$ to $3$, and repeat the process. We omit the details, but the final result $\widetilde{D}$ is shown in Figure \ref{fig:ellIs5}.

\end{example}


Finally, the truncating permutation $\pi_D$ is obtained from the diagram $\widetilde{D}$ as follows.

\begin{thm}\label{thm:AlgCor}
Let $D \in RP(w)$ be a highest weight pipe dream for $w \in S_n$. Then $\pi_D \in S_n$ from Theorem \ref{thm:main} is the unique shortest permutation such that $\operatorname{wt}(\widetilde{D}) = \pi_D(\wt(D))$.  In addition, the composition $a_D = \wt(\widetilde{D})$ from Theorem \ref{thm:main-key} indexes the key polynomial corresponding to $(\pi_D, \wt(D))$.
\end{thm}

We conclude by extracting the truncating permutation $\pi_D$ and the composition $a_D$ from Example \ref{ex:alg} via Theorem \ref{thm:AlgCor}.

\begin{example}
    For the highest weight pipe dream $D$ in Example \ref{ex:alg}, we have $\wt(D) = (5,3,3,1,1,0)$. After applying Algorithm \ref{alg:EG}, we obtained the diagram $\widetilde{D}$ in Figure \ref{fig:ellIs5} such that $a_D = \wt(\widetilde{D}) = (3,5,1,3,1,0)$.  The shortest permutation $\pi_D$ such that $a_D = \pi_D(\wt(D))$ equals $\pi_D = s_1s_3$, since $(3,5,1,3,1,0) = s_1s_3(5,3,3,1,1,0)$.
\end{example}


%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way

\acknowledgements{The authors thank Anne Schilling and Sarah Mason for helpful correspondence. This work has also benefited from numerous related discussions with Jo\~ao Pedro Carvalho. The authors were partially supported by NSF Grant DMS-2202017.}

\printbibliography



\end{document}
