%% 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{93}
%% 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}

\usepackage{amsthm, amssymb}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{pgf}
\usepackage{tikz}
\usepackage{tikz-cd}
\usetikzlibrary{positioning,shapes,shadows,arrows}
\usepackage{bbm,bm}
\usepackage{enumitem}
\usepackage{mathabx}
\usepackage{comment}
\usepackage{ytableau}
\usepackage{thmtools}
\usepackage{thm-restate}
\usepackage{microtype}


\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem*{thm_main}{Theorem~\ref{T: FS on BPD}}
\newtheorem*{thm_main_chain}{Theorem~\ref{T: BPD to chain}}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{conj}[thm]{Conjecture}
\theoremstyle{remark}
\newtheorem{exa}[thm]{Example}
\newtheorem{rem}[thm]{Remark}
\newtheorem{defn}[thm]{Definition}
\newtheorem{prob}[thm]{Problem}

\newcommand{\E}{\mathcal{E}}
\newcommand{\N}{\mathcal{N}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\BPD}{\mathsf{BPD}}
\newcommand{\FT}{\mathsf{FT}}
\newcommand{\df}{:=}
\newcommand{\fS}{\mathfrak{S}}
\newcommand{\id}{\mathsf{id}}
\newcommand{\growth}{\mathsf{growth}}
\newcommand{\Growth}{\mathsf{Growth}}

\newcommand{\chain}{\mathsf{chain}}
\newcommand{\PD}{\mathsf{PD}}
\newcommand{\rev}{\mathsf{rev}}
\newcommand{\word}{\mathsf{word}}
\newcommand{\wt}{\mathsf{wt}}
\newcommand{\WT}{\mathsf{WT}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\std}{\mathsf{std}}
\newcommand{\shift}{\mathsf{shift}}

\newcommand{\btile}{
 \begin{tikzpicture}[x=1em,y=1em,thick,color = blue]
\draw[step=1,gray,thin] (0,0) grid (1,1);
\draw[color=black, thick, sharp corners] (0,0) rectangle (1,1);
\end{tikzpicture}}

\newcommand{\htile}{
\begin{tikzpicture}[x=1em,y=1em,thick,color = blue]
\draw[step=1,gray,thin] (0,0) grid (1,1);
\draw[color=black, thick, sharp corners] (0,0) rectangle (1,1);
\draw(1.0,0.5)--(0.0,0.5);
\end{tikzpicture}
}

\newcommand{\vtile}{
\begin{tikzpicture}[x=1em,y=1em,thick,color = blue]
\draw[step=1,gray,thin] (0,0) grid (1,1);
\draw[color=black, thick, sharp corners] (0,0) rectangle (1,1);
\draw(0.5,1.0)--(0.5,0.0);
\end{tikzpicture}}

\newcommand{\ptile}{
\begin{tikzpicture}[x=1em,y=1em,thick,color = blue]
\draw[step=1,gray,thin] (0,0) grid (1,1);
\draw[color=black, thick, sharp corners] (0,0) rectangle (1,1);
\draw(0.5,1.0)--(0.5,0.0);
\draw(1.0,0.5)--(0.0,0.5);
\end{tikzpicture}}

\newcommand{\rtile}{
\begin{tikzpicture}[x=1em,y=1em,thick,rounded corners,color = blue]
\draw[step=1,gray,thin] (0,0) grid (1,1);
\draw[color=black, thick, sharp corners] (0,0) rectangle (1,1);
\draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0);
\end{tikzpicture}}

\newcommand{\jtile}{
\begin{tikzpicture}[x=1em,y=1em,thick,rounded corners,color = blue]
\draw[step=1,gray,thin] (0,0) grid (1,1);
\draw[color=black, thick, sharp corners] (0,0) rectangle (1,1);
\draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5);
\end{tikzpicture}}

\newcommand{\bumptile}{
\begin{tikzpicture}[x=1em,y=1em,thick,rounded corners,color = blue]
\draw[step=1,gray,thin] (0,0) grid (1,1);
\draw[color=black, thick, sharp corners] (0,0) rectangle (1,1);
\draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0);
\draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5);
\end{tikzpicture}}

\definecolor{darkblue}{rgb}{0.0,0,0.7} % darkblue color
\definecolor{darkred}{rgb}{0.7,0,0} % darkred color
\definecolor{darkgreen}{rgb}{0, .6, 0} % darkgreen color
\newcommand{\definition}[1]{{\color{darkred}\emph{#1}}} % emphasis of a definition
\newcommand{\Tianyi}[1]{\todo[size=\tiny,inline,color=purple!30]{#1
\\ \hfill --- Tianyi}}

%% define your title in the usual way
\title{Analogues of two classical pipedream results on bumpless pipedreams}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Tianyi Yu\thanks{\href{tiy059@ucsd.edu}{tiy059@ucsd.edu}}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, UC San Diego, La Jolla, CA 92093, U.S.A.}

%% put the date of submission here
\received{Mar. 30}

%% 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 are distinguished representatives of Schubert cycles in the cohomology of the flag variety. Pipedreams (PD) and bumpless pipedreams (BPD) are two combinatorial models of Schubert polynomials. There are many classical results on PDs. For instance, Fomin and Stanley represented each PD as an element in the nil-Coexter algebra. Lenart and Sottile converted each PD into certain chains in the Bruhat order. This paper establishes the BPD analogues of both viewpoints. Our
results lead to a bijection between PDs and BPDs via Lenart's growth diagram.}

%% 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, pipedreams, Fomin-Kirillov algebra, Bruhat orders}

%% 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}
Fix $n \in \mathbb{Z}_{\geq 0}$. 
For a permutation $w \in S_n$,
Lascoux and Sch\"utzenberger~\cite{LS:Schubert}
recursively define the \definition{Schubert polynomial} 
$\fS_w$.
The base case is 
$\fS_{w_0} := x_{1}^{n-1} x_2^{n-2} \cdots x_{n-1}$
where $w_0$ is the permutation with 
one-line notation $[n, n-1, \cdots, 1]$.
To compute $\fS_w$ for other $w \in S_n$,
we need the \definition{divided difference operator} 
$\partial_i(f) := \frac{f - f(\cdots, x_{i+1}, x_i, \cdots)}{x_i - x_{i+1}}$.
Let $s_{i} \in S_n$ denote the transposition that swaps $i$ and $i+1$.
Then for any $w \in S_n$ and $i \in [n-1]$:
$$
\partial_i(\fS_w) = \begin{cases}
\fS_{w s_i} & \text{if $w(i) > w(i+1)$,} \\
0  & \text{if $w(i) < w(i+1)$.}
\end{cases}
$$



The Schubert polynomials represent Schubert cycles in flag varieties and have been extensively investigated.
Schubert polynomials have two distinct combinatorial formulas involving ``pipes'': pipedreams (PD)~\cite{BB, BJS} and bumpless pipedreams (BPD)~\cite{LLS}.
Both are fillings of grids with certain tiles. 
When we refer to cells of a grid, 
we use the matrix coordinates:
row $1$ is the topmost row 
and column $1$ is the leftmost column. 
A \definition{pipedream} is a filling of a staircase
grid:
The grid has a cell in row $i$ column $j$ for each $i + j \leq n + 1$.
The rightmost cell in each row is $\jtile$.
The rest of the cells can be $\ptile$ (crossing)
or $\bumptile$ (bump), but two pipes cannot cross more than once.
A \definition{bumpless pipedream (BPD)}
is a consistent filling of an $n \times n$ grid with six types of cells:
$
\vtile, \htile, \ptile, \jtile, \rtile$
and $\btile$ (blank).
Pipes enter from each cell on the bottom
and exit on the right edge. 
In addition, two pipes cannot cross more than once.
The permutation associated to each PD (resp. BPD) 
can be read off as follows:
Label the pipes $1, 2, \dots, n$ along the top (resp. bottom) edge,
follow the pipes, and read the labels from top to bottom on the left (resp. right) edge. 

\begin{exa}
\label{E: PD}
When $n = 5$, we present a PD
and a BPD associated with $[2,5,1,4,3]$:

$$
\begin{tikzpicture}[x=1.5em,y=1.5em,thick,rounded corners, color = blue]
\draw[step=1,black, thin] (0,0) grid (1,1);
\draw[step=1,black,thin] (0,1) grid (2,2);
\draw[step=1,black,thin] (0,2) grid (3,3);
\draw[step=1,black,thin] (0,3) grid (4,4);
\draw[step=1,black,thin] (0,4) grid (5,5);
\draw(0, 0.5)--(0.5,0.5)--(0.5,2.5)--(1.5,2.5)--(1.5,4.5)--(2.5,4.5)--(2.5,5);
\draw(0, 1.5)--(1.5,1.5)--(1.5,2.5)--(2.5,2.5)--(2.5,3.5)--(3.5,3.5)--(3.5,5);
\draw(0, 2.5)--(0.5,2.5)--(0.5,5);
\draw(0, 3.5)--(2.5,3.5)--(2.5,4.5)--(4.5,4.5)--(4.5,5);
\draw(0, 4.5)--(1.5,4.5)--(1.5,5);
\end{tikzpicture}
\quad\quad\quad
\begin{tikzpicture}[x=1.5em,y=1.5em,thick,rounded corners, color = blue]
\draw[step=1,gray,thin] (0,0) grid (5,5);
\draw[color=black, thick, sharp corners] (0,0) rectangle (5,5);
\draw(0.5, 0)--(0.5,2.5)--(5,2.5);
\draw(1.5, 0)--(1.5,3.5)--(2.5,3.5)--(2.5,4.5)--(5,4.5);
\draw(2.5, 0)--(2.5,0.5)--(5,0.5);
\draw(3.5, 0)--(3.5,1.5)--(5,1.5);
\draw(4.5, 0)--(4.5,3.5)--(5,3.5);
\end{tikzpicture}
$$


\end{exa}


Let $\PD(w)$ (resp. $\BPD(w)$) be the set of all
PDs (resp. BPDs) associated 
with $w \in S_n$.
For $P \in \PD(w)$ (resp. $P \in \BPD(w)$),
the weight of $P$, denoted as $\wt(P)$, 
is a sequence of $n-1$ integers where the $i^{th}$ entry
is the number of $\ptile$ (resp. $\btile$) on row $i$.
For instance, the PD and BPD in Example~\ref{E: PD}
both have weight $(2,2,0,1)$.
If $\alpha = (\alpha_1, \cdots, \alpha_{n-1})$ 
is a sequence of $n-1$ non-negative integers,
we use $x^{\alpha}$ to denote the monomial
$x_1^{\alpha_1} \cdots x_{n-1}^{\alpha_{n-1}}$.

\begin{thm}\cite{BB, BJS, LLS}
\label{T: PD}
For $w \in S_n$, $\fS_w = \sum_{P \in \PD(w)} x^{\wt(P)}= \sum_{D \in \BPD(w)} x^{\wt(D)}$.
\end{thm}

There is a recent surge of research
connecting BPDs with PDs and finding 
BPD analogue of classical PD apparatus
\cite{GH, KUZ, KW, W}.
This paper establishes the BPD analogue of two classical stories on PDs:

\begin{itemize}
\item The nil-Coexter algebra $\N_n$ is generated by 
$u_1, \cdots, u_{n-1}$.
Fomin and Stanley~\cite{FS} defined the following elements in $\mathbb{Q}[x_1, \cdots, x_{n-1}] \otimes \N_n$:
$$
A_i(x_i) := (1 + x_i u_{n-1}) (1 + x_i u_{n-2}) \cdots (1 + x_i u_{i}) \textrm{ and }
\fS^\PD := A_1(x_1) \cdots A_{n-1}(x_{n-1}).
$$
Combinatorially, after expanding $\fS^\PD$,
each term $x^\alpha u_{i_1}\cdots u_{i_k}$ 
naturally corresponds to a $P \in \PD(w)$
with $\alpha = \wt(P)$ and $i_1\cdots i_k$ is a reduced word of $w$.
Algebraically, Fomin and Stanley
proved $\fS^\PD = \sum_{w \in S_n} \fS_w u_{i_1}\cdots u_{i_l}$
where $i_1 \cdots i_l$ 
is any reduced word of $w$.
Consequently, they obtain an operator theoretic proof of the PD fomula.

\item 
The Bruhat order is a partial order
on $S_n$.
Lenart and Sottile~\cite{LeSo}
defined a bijection from $\PD(w)$
to chains 
$(w_1, w_2, \cdots, w_n)$ in
the Bruhat order
where $w_1 = w$, $w_n = w_0$
and there is an increasing
$i$-chain from $w_i$ to $w_{i+1}$
for $i \in [n-1]$
(See Section~\ref{SS: Schubert}).
\end{itemize}


Since the introduction of BPDs, 
finding a BPD analogue of the Fomin-Stanley construction has been an open problem. 
Instead of the nil-Coexter algebra, 
we consider the Fomin-Kirillov 
algebra $\E_n$~\cite{FK-algebra}.
It is generated by $d_{i,j}$ 
for $1 \leq i < j \leq n$
and has a right action on $\mathbb{Q}[S_n]$ 
denoted as $\odot$.
Define the following elements in $\mathbb{Q}[x_1, \cdots, x_{n-1}] \otimes \E_n$:
$$
R_i(x_i) := 
(x_i + d_{1, i+1} + \cdots + d_{i,i+1})
(x_i + d_{1, i+2} + \cdots + d_{i,i+2})
\cdots
(x_i + d_{1, n} + \cdots + d_{i,n}), \textrm{ and}
$$
$$
\fS^\BPD := w_0 \odot (R_1(x_1) R_2(x_2) \cdots R_{n-1}(x_{n-1})).
$$
Combinatorially, after expanding $\fS^\BPD$,
we show each term $x^\alpha w$
naturally corresponds to a $D \in \BPD(w)$
with $\alpha = \wt(D)$.
Algebraically, we establish Theorem~\ref{T: FS on BPD}, obtaining an operator
theoretic proof of the BPD formula.
\begin{thm_main}
We have $\fS^\BPD = \sum_{w \in S_n} \fS_w w$.
\end{thm_main}

A crucial tool to understand 
$\fS^\BPD$ is a novel encoding 
algorithm $\Phi$ that encodes each 
element of $\BPD(w)$ 
as partial fillings of a staircase grid which we call \definition{flagged tableaux}.
We denote the image of $\BPD(w)$ under $\Phi$ as $\FT(w)$.
Each $T \in \FT(w)$
corresponds to a chain 
in the Bruhat order
denoted as $\chain(T) = (w_n, \cdots, w_1)$.
Then we establish Theorem~\ref{T: BPD to chain}, obtaining a BPD analogue of Lenart and Sottile's work. 
\begin{thm_main_chain}
The map $\chain(\cdot)$
is a bijection from $\FT(w)$
to chains $(w_n, \cdots, w_1)$ in 
the Bruhat order where
$w_n = w$, $w_1 = w_0$
and there is an increasing $i$-chain
from $w_{i+1}$ to $w_i$.
Consequently,
$\chain \circ \Phi$ is
a bijection from $\BPD(w)$
to such chains.
\end{thm_main_chain}

In other words, 
PDs and BPDs can both be viewed
as certain chains in the Bruhat order,
exhibiting a duality. 
Finally, we use Lenart's growth diagram~\cite{L_growth} 
to obtain a bijection between these chains,
obtaining a bijection between
$\PD(w)$ and $\BPD(w)$.
We conjecture this bijection
agrees with the existing bijection
of Gao and Huang~\cite{GH}.
This conjecture has been verified on $S_7$.

\textbf{Organization}:
In~\S\ref{S: Background},
we cover some necessary background. 
In~\S\ref{S: encode BPD},
we define the encoding map 
$\Phi: \BPD(w) \rightarrow \FT(w)$
and establish Theorem~\ref{T: BPD to chain}. 
In~\S\ref{S: construction},
we construct our BPD analogue of the 
Fomin-Stanley construction.
In~\S\ref{S: Growth},
we use Lenart's growth diagram
to build a bijection between 
$\PD(w)$ and $\BPD(w)$.
In~\S\ref{S: Double},
we describe one conjecture
that extends the chain formulas
of $\fS_w$
to double Schubert polynomials. 

\section{Background}
\label{S: Background}
\subsection{Fomin-Stanley construction}
\label{SS: FS}

A \definition{reduced word} of $w \in S_n$
is a word $i_1 i_2 \cdots i_l$ such that
$w = s_{i_1} \cdots s_{i_l}$ and $l$ is minimized.
One can read off a reduced word of $w$ 
from every $P \in \PD(w)$ as follows:
Go through its crossings from top to bottom
and right to left in each row.
For a crossing in row $r$ column $c$,
read off $r + c - 1$.
For instance, the PD in 
Example~\ref{E: PD} gives 
$41324$ which is a reduced word of $[2,5,1,4,3]$.

The \definition{nil-Coexter algebra} $\N_n$ is generated by $u_1, \cdots, u_{n-1}$
satisfying:
\begin{align*}
\begin{cases}
u_i^2 & = 0,\\
u_i u_j & =  u_j u_i \textrm{ if $|i-j| \geq 2$ },\\
u_i u_{i+1} u_i & =  u_{i+1} u_i u_{i+1} \textrm{ if $i \in [n-2]$.}
\end{cases}
\end{align*}

Consider $a = u_{i_1} \cdots u_{i_l} \in \N_n$, we have
$a \neq 0$ if and only if $i_1 \cdots i_l$
is a reduced word of some $w \in S_n$.
In this case,
$a = u_{j_1} \cdots u_{j_{l'}}$
if and only if $j_1 \cdots j_{l'}$
is a reduced word for the same $w$.
Fomin and Stanley~\cite{FS}
defined the following elements in $\Q[x_1, \cdots, x_{n-1}] \otimes \N_n$:
\begin{align*}
A_i(x_i) & := (1 + x_i u_{n-1})(1 + x_i u_{n-2}) \cdots (1 + x_i u_{i}) \textrm{ for $i \in [n-1]$, and}\\
\fS^\PD & := A_1(x_1) A_2(x_2) \cdots A_{n-1}(x_{n-1}).
\end{align*}
Combinatorially, 
$\fS^\PD = \sum_{P} x^{\wt(P)} u_{i_1}\cdots u_{i_l}$
where the sum runs over all PD
and $i_1 \cdots i_l$ is the reduced word read off from the PD.
Algebraically, Fomin and Stanley
showed that 
\begin{align}
\label{EQ: classical FS}
\fS^\PD = \sum_{w \in S_n} \fS_w u_{i_1}\cdots u_{i_l}, 
\end{align}
where $i_1 \cdots i_l$ 
is an arbitrary reduced word of $w$.
This formula would imply 
the PD formula in Theorem~\ref{T: PD}.
Fomin and Stanley proved 
(\ref{EQ: classical FS})
by showing 
$\partial_i(\fS^\PD) = \fS^\PD u_i$
for any $i \in [n-1]$.
This equation then reduces
to 
$\partial_i(R_i(x_i) R_{i+1}(x_{i+1}))
= R_i(x_i) R_{i+1}(x_{i+1}) u_i$.
In \S\ref{S: construction},
we present the BPD analogue
of (\ref{EQ: classical FS})
and establish our equation
in a similar way. 


\subsection{Bruhat order}
\label{SS: Schubert}
For $1 \leq i < j \leq n$, we use $t_{i,j}$
to denote the permutation
that swaps $i$ and $j$.
For $w \in S_n$,
let $\ell(w) := |\{(i,j): i < j, w(i) > w(j)|$.
Let $\leq$ be the \definition{Bruhat order}
on $S_n$, 
where the cover relation is given by
$u \lessdot w \textrm{ if $w = ut_{i,j}$ and $\ell(w) = \ell(u) + 1$}$.
We say $C = (w_1, w_2, \cdots, w_d)$ 
is a \definition{Bruhat chain}
from $w_1$ to $w_d$ if $w_1 \leq w_2 \leq \cdots \leq w_d$.
The length of $C$ is $d - 1$.
The \definition{weight} of $C$, denoted as $\wt(C)$, 
is a sequence of length $d-1$ 
where the $i^{th}$ entry
is $\ell(w_{i+1}) - \ell(w_i)$. 
The chain is \definition{saturated}
if $w_1 \lessdot w_2 \lessdot \cdots \lessdot w_d$.
We may represent a saturated chain as
$$
w_1 \xrightarrow{t_{a_1, b_1}} w_2 \xrightarrow{t_{a_2, b_2}}
\cdots \xrightarrow{t_{a_{d-1}, b_{d-1}}} w_d,
$$
where $a_i < b_i$ and $w_{i+1} = w_i t_{a_i, b_i}$.

Take $k \in [n-1]$.
We use $\leq_k$ to denote the 
\definition{$k$-Bruhat order} on $S_n$.
Its cover relation is given by
$
u \lessdot_k w \textrm{ if $u \lessdot w$ and 
$w = ut_{i,j}$ for some $i \leq k < j$}$.
Similarly, we can define 
$k$-Bruhat chains and saturated $k$-Bruhat chains. 
For simplicity, we say ``\definition{$k$-chains}'' in place of
``$k$-Bruhat chains''.
The $k$-Bruhat order can be used to describe
the Monk's rule~\cite{Monk}:
$
\fS_w (x_1 + \cdots + x_k) = \sum_{w \lessdot_k u} \fS_u$
for any $w \in S_n$ and $k \in [n-1]$
such that $w(j) = n$ for some
$j > k$.
Sottile generalized the Monk's rule 
by considering multiplying $\fS_w$
with 
$$
h_d(x_1, \cdots, x_k) := \sum_{1 \leq i_1 \leq \cdots \leq i_d \leq k}x_{i_1} \cdots x_{i_d},
$$
where $k \in [n-1]$ and $d \in \mathbb{Z}_{> 0}$.
Say a saturated $k$-chain
$w_1 \xrightarrow{t_{a_1, b_1}} w_2 \xrightarrow{t_{a_2, b_2}}
\cdots \xrightarrow{t_{a_{d-1}, b_{d-1}}} w_d
$
is \definition{increasing}
if $w_1(a_1) < w_2(a_2) < \cdots < w_{d-1}(a_{d-1})$.
In other words, the smaller number 
swapped is increasing. 
It is not hard to show
for any $u, w \in S_n$ and $k \in [n-1]$,
there is at most one increasing 
$k$-chain from $u$ to $w$.

\begin{thm}\cite{Sot}
\label{T: Pieri}
Take $u \in S_n$ and $d \in \Z_{\geq 0}$.
For any $k \in [n-1]$ such that
$n, n-1, \cdots, n - d + 1$ are among $w(k+1), \cdots, w(n)$,
then
$$
\fS_u \times h_d(x_1, \cdots, x_k) = \sum_{w} \fS_w.
$$
The sum is over all $w$ such that 
there is an increasing $k$-chain 
from $u$ to $w$ with length $d$.
\end{thm}

Lenart and Sottile~\cite{LeSo} view PDs as certain Bruhat chains.
We introduce the following 
definition to describe 
their chains in a more
general way.


\begin{defn}
We say a Bruhat chain $C = (w_1, w_2, \cdots, w_l, w_{l+1})$
is \definition{compatible} with a sequence $(k_1, \cdots, k_l)$ if 
there exists an increasing $k_i$-chain from $w_i$
to $w_{i+1}$ for each $i \in [l]$.
\end{defn}

Lenart and Sottile~\cite{LeSo} described a bijection from 
$\PD(w)$ to chains from $w$ to $w_0$ 
compatible with $(1, 2, \cdots, n-1)$:
Take $P \in \PD(w)$.
For $i \in [n]$,
let $P_i$ be the pipedream
obtained from $P$ by changing all bumps
above row $i$ into crossings.
Let $w_i$ be the permutation associated with
$P_i$.
Then $(w_1, \cdots, w_n)$ is the resulting chain. 
In addition, 
if we change bumps in row $i$ of $P_i$ into
crossings from left to right,
permutations of the intermediate pipedreams
will form the increasing 
$i$-chain 
from $w_i$ to $w_{i+1}$.

\begin{exa}
\label{E: Lenart Sottile}  

Let $P$ be the pipedream in Example~\ref{E: PD}.
Then its corresponding chain is
$([2,5,1,4,3], [5,3,1,4,2], [5,4,1,3,2],[5,4,3,2,1],[5,4,3,2,1])$.
The increasing $1$-chain
from $[2,5,1,4,3]$ to $[5,3,1,4,2]$
is given by:
$[2,5,1,4,3]
\xrightarrow{t_{1,5}} [3,5,1,4,2]
\xrightarrow{t_{1,2}} [5,3,1,4,2]$.
\end{exa}

If a pipedream $P$ is sent to the chain $C$, then $\wt(C) = (n-1, \cdots, 1) - \wt(P)$
where the subtraction is entry-wise.
Thus, this bijection
recovers a result of Bergeron and Sottile: 
\begin{cor}\cite{BS}
\label{C: BS}
For $w \in S_n$, $\fS_w = \sum_{C} x^{(n-1, \cdots, 1) - \wt(C)}$,
where the sum is over all chains
from $w$ to $w_0$ 
compatible with $(1, 2, \cdots, n-1)$.
\end{cor}

We end this section by extending 
Corollary~\ref{C: BS} using
the following observation:

\begin{prop}
\label{P: Swap chains}
Pick $u, w \in S_n$, $k_1, k_2 \in [n-1]$
and $d_1, d_2 \in \mathbb{Z}_{\geq 0}$.
The number of chains from $u$ to $w$ compatible with $(k_1, k_2)$ and has weight $(d_1, d_2)$
matches the number of chains from $u$ to $w$ compatible with $(k_2, k_1)$ and has weight $(d_2, d_1)$.
\end{prop}
\begin{proof}

By Theorem~\ref{T: Pieri}, 
the number of chains $(u, v, w)$ compatible with $(k_1, k_2)$ and has weight $(d_1, d_2)$
is the coefficient of $\fS_w$ 
in $\fS_u \times h_{d_1}(x_1, \cdots, x_{k_1}) \times h_{d_2}(x_1, \cdots, x_{k_2})$.
The proof is finished by the commutativity of 
polynomial multiplication.
\end{proof}

Since we have two sets with the same
size, it would be natural to ask: 

\begin{prob}
\label{prob: chain}
Find an explicit bijection
between the two set of chains in Proposition~\ref{P: Swap chains}. 
\end{prob}

In \S\ref{S: Growth}, we show Lenart's growth diagram~\cite{L_growth} solves Problem~\ref{prob: chain} in a special case.

Combining Corollary~\ref{C: BS} and Proposition~\ref{P: Swap chains}, we deduce:

\begin{cor}
\label{C: Bruhat formula}
Take $w \in S_n$ and $\gamma \in S_{n-1}$.
If $(d_1, \cdots, d_{n-1})$
is a sequence of numbers, 
let $\gamma^{-1}(d_1, \cdots, d_{n-1}) :=(d_{\gamma^{-1}(1)}, \cdots, d_{\gamma^{-1}(n-1)})$.
We also view $\gamma$
as a sequence of numbers.
Then 
$\fS_w = \sum_{C} x^{(n-1, \cdots, 1) - \gamma^{-1}(\wt(C))}$,
summing over all chains from $w$ 
to $w_0$ compatible with $\gamma$.
\end{cor}

This corollary implies that we have
a combinatorial formula of $\fS_w$ involving Bruhat chains
for each choice of $\gamma \in S_{n-1}$. 
Under Lenart and Sottile's bijection,
the PD formula is identified with
the Bruhat chain formula when $\gamma = [1, 2, \cdots, n-1]$. 
In~\S\ref{S: encode BPD},
we identify the BPD formula
with the Bruhat chain formula
when $\gamma = [n-1, n-2, \cdots, 1]$.


\section{Encoding BPDs as flagged tableaux and chains}
\label{S: encode BPD}

We first encode each 
BPD as the following combinatorial object.
\begin{defn}
A \definition{flagged tableau}
is a staircase grid
with a cell in row $i$
column $j$ if $i + j \leq n$.
Moreover, each cell in row $i$ is empty
or filled with a number in $[i]$.    
\end{defn}

We define an encoding map $\Phi$
from $\BPD(w)$ to the set of flagged tableaux.

\begin{defn}
Take $D \in \BPD(w)$ for some $w \in S_n$.
For $i \in [n]$, 
there are $(i-1)$ pipes exiting from
the top from row $i$ of $D$,
so there are $(i-1)$ $\ptile$,
$\vtile$ and $\jtile$.
We mark these cells, and then 
mark the rightmost unmarked
cell in row $i$.
There will be $n - i$ unmarked cells.
To fill the cell in row $i$ column 
$j$ of $\Phi(D)$,
we look at the 
$j^\textsuperscript{th}$
leftmost unmarked cell 
in row $i$ of $D$.
If it is a blank,
we leave the cell in 
$\Phi(D)$ unfilled. 
Otherwise, it contains a pipe
that ends in row $p$ for some $p \leq i$.
We fill the cell
in $\Phi(D)$ by $p$.
\end{defn}


\begin{exa}
\label{E: Phi}
Assume $n = 6$.
Take $D \in \BPD([2,1,6,5,3,4])$
as depicted on the left. 
Then we perform the encoding algorithm and
mark certain cells red. 
Finally, we obtain $\Phi(D)$.

\[
\begin{tikzpicture}[x=1.5em,y=1.5em,thick,rounded corners, color = blue]
\draw[step=1,gray,thin] (0,0) grid (6,6);
\draw[color=black, thick, sharp corners] (0,0) rectangle (6,6);
\draw(0.5, 0)--(0.5,3.5)--(4.5,3.5)--(4.5,4.5)--(6,4.5);
\draw(1.5, 0)--(1.5,2.5)--(2.5,2.5)--(2.5,4.5)--(3.5,4.5)--(3.5,5.5)--(6,5.5);
\draw(2.5, 0)--(2.5,1.5)--(6,1.5);
\draw(3.5, 0)--(3.5,0.5)--(6,0.5);
\draw(4.5, 0)--(4.5,2.5)--(6,2.5);
\draw(5.5, 0)--(5.5,3.5)--(6,3.5);
\end{tikzpicture}
\quad\quad
\begin{tikzpicture}[x=1.5em,y=1.5em,thick,rounded corners, color = blue]
\draw[step=1,gray,thin] (0,0) grid (6,6);
\draw[color=black, thick, sharp corners] (0,0) rectangle (6,6);
\draw(0.5, 0)--(0.5,3.5)--(4.5,3.5)--(4.5,4.5)--(6,4.5);
\draw(1.5, 0)--(1.5,2.5)--(2.5,2.5)--(2.5,4.5)--(3.5,4.5)--(3.5,5.5)--(6,5.5);
\draw(2.5, 0)--(2.5,1.5)--(6,1.5);
\draw(3.5, 0)--(3.5,0.5)--(6,0.5);
\draw(4.5, 0)--(4.5,2.5)--(6,2.5);
\draw(5.5, 0)--(5.5,3.5)--(6,3.5);
\fill[red, semitransparent, sharp corners] (0,0) rectangle (1,1);
\fill[red, semitransparent, sharp corners] (1,0) rectangle (2,1);
\fill[red, semitransparent, sharp corners] (2,0) rectangle (3,1);
\fill[red, semitransparent, sharp corners] (3,0) rectangle (4,1);
\fill[red, semitransparent, sharp corners] (4,0) rectangle (5,1);
\fill[red, semitransparent, sharp corners] (5,0) rectangle (6,1);
\fill[red, semitransparent, sharp corners] (0,1) rectangle (1,2);
\fill[red, semitransparent, sharp corners] (1,1) rectangle (2,2);
\fill[red, semitransparent, sharp corners] (3,1) rectangle (4,2);
\fill[red, semitransparent, sharp corners] (4,1) rectangle (5,2);
\fill[red, semitransparent, sharp corners] (5,1) rectangle (6,2);
\fill[red, semitransparent, sharp corners] (0,2) rectangle (1,3);
\fill[red, semitransparent, sharp corners] (2,2) rectangle (3,3);
\fill[red, semitransparent, sharp corners] (4,2) rectangle (5,3);
\fill[red, semitransparent, sharp corners] (5,2) rectangle (6,3);
\fill[red, semitransparent, sharp corners] (2,3) rectangle (3,4);
\fill[red, semitransparent, sharp corners] (4,3) rectangle (5,4);
\fill[red, semitransparent, sharp corners] (5,3) rectangle (6,4);
\fill[red, semitransparent, sharp corners] (3,4) rectangle (4,5);
\fill[red, semitransparent, sharp corners] (5,4) rectangle (6,5);
\fill[red, semitransparent, sharp corners] (5,5) rectangle (6,6);
\end{tikzpicture}
\quad\quad
\raisebox{1.75cm}{$\Phi(D)$ = \raisebox{0.9cm}{
\begin{ytableau}
\: & \: & \: & 1 & 1\cr
\: & \: & 1 & 2\cr
2 & 2 & 2\cr
1 & \:\cr
5 \end{ytableau}}}
\]
\end{exa}

To precisely
describe the image of $\BPD(w)$ under $\Phi$,
we need the following definition.

\begin{defn}
The \definition{reading word} 
of a flagged tableau $T$, 
denoted as $\word(T)$,
is a sequence of pairs obtained as follows. 
Go through entries of $T$ from top to bottom, and right to left in each row.
When we see the number $i$ in  column $c$, 
we write the pair $(i, n+1-c)$.
\end{defn}

By the definition of flagged tableaux,
for each pair in the reading word,
the first entry is smaller than the second.

\begin{exa}
In Example~\ref{E: Phi}, $\word(\Phi(D)) = 
(1,2)(1,3)(2,3)(1,4)(2,4)(2,5)(2,6)(1,6)(5,6)$.
\end{exa}

Let $T$ be a flagged tableau with reading word
$(a_1, b_1), \cdots, (a_d, b_d)$.
For $i \in [d]$,
we let $w_i = w_0 t_{a_1, b_1} \cdots t_{a_i, b_i}$.
Then we say $T$ is \definition{associated} with the permutation
$w_d$ if 
$$
w_d \xrightarrow{t_{a_d, b_d}} w_{d-1} \xrightarrow{t_{a_{d-1}, b_{d-1}}} \cdots \xrightarrow{t_{a_{2}, b_2}} w_1
\xrightarrow{t_{a_{1}, b_1}}
w_0
$$
is a saturated Bruhat chain. Let $\FT(w)$
consist of all flagged tableaux
associated with $w$.
\begin{exa}
In Example~\ref{E: Phi},
$\Phi(D)$ is associated with 
$[2,1,6,5,3,4]$ because:
\begin{align*}
& [2,1,6,5,3,4] 
\xrightarrow{t_{5,6}} [2,1,6,5,4,3]
\xrightarrow{t_{1,6}} [3,1,6,5,4,2]
\xrightarrow{t_{2,6}} [3,2,6,5,4,1]
\xrightarrow{t_{2,5}} [3,4,6,5,2,1]\\
\xrightarrow{t_{2,4}} & [3,5,6,4,2,1]
\xrightarrow{t_{1,4}} [4,5,6,3,2,1]
\xrightarrow{t_{2,3}} [4,6,5,3,2,1]
\xrightarrow{t_{1,3}} [5,6,4,3,2,1]
\xrightarrow{t_{1,2}} [6,5,4,3,2,1]  
\end{align*}
is a saturated Bruhat chain
from $[2,1,6,5,3,4]$ to $w_0$.
Notice that $D \in \BPD([2,1,6,5,3,4])$.
\end{exa}

For a flagged tableau $T$,
define the \definition{weight} of $T$,
denoted as $\wt(T)$,
to be a sequence of $n-1$ numbers 
whose $i\textsuperscript{th}$
entry is the number of blanks in row $i$. 
Then we have:

\begin{prop}
\label{P: BPD FT}
For $w \in S_n$, 
$\Phi$ is a weight-preserving bijection from 
$\BPD(w)$ to $\FT(w)$.
\end{prop}

We may turn $T$ into a chain compatible with
$(n-1, \cdots, 2, 1)$ as follows.  
Suppose $T$ has reading word 
$(a_1, b_1), \cdots, (a_d, b_d)$
and set 
$w_i = w_0 t_{a_1, b_1} \cdots t_{a_i, b_i}$
for $i \in [d]$.
Let $m_i$ be the number of non-empty cells above
row $i+1$ of $T$ for $i = 0, 1. \cdots, n-1$.
Clearly, 
$(w_{m_{i}}, w_{m_{i} - 1}, \cdots, w_{m_{i - 1}})$
is an $i$-chain.
Moreover, we can check 
it is an increasing $i$-chain.
Then define $\chain(T) := (w_{m_{n-1}}, \cdots, w_{m_{1}}, w_0)$,
which is compatible with $(n-1, \cdots, 2, 1)$.
\begin{exa}
Let $T$ be the $\Phi(D)$ 
in Example~\ref{E: Phi}.
Then $\chain(T)$ is 
$$([2,1,6,5,3,4], [2,1,6,5,4,3], [3, 1, 6, 5, 4, 2], [3, 5, 6, 4, 2, 1], [4, 6, 5, 3, 2, 1], [6,5,4,3,2,1]).$$
\end{exa}

\begin{thm}
\label{T: BPD to chain}
The map $\chain(\cdot)$
is a bijection from $\FT(w)$
to Bruhat chains from $w$ to $w_0$
compatible with $(n-1, \cdots, 2, 1)$.
Consequently,
$\chain \circ \Phi$ is
a bijection from $\BPD(w)$
to such chains.
\end{thm}

The bijection $\chain \circ \Phi$
is an analogue
of Lenart and Sottile's bijection~\cite{LeSo} on $\PD(w)$.
Notice that for $D \in \BPD(w)$, 
if $\wt(D) = (\alpha_1, \cdots, \alpha_{n-1})$
then $$\wt(\chain(\Phi(D))) = (1 - \alpha_{n-1}, \cdots, n-2 - \alpha_2, n - 1 - \alpha_1).$$
Thus, we have identified the BPD 
formula of $\fS_w$ with the Bruhat chain formula in Corollary~\ref{C: Bruhat formula}
with $\gamma = [n-1, \cdots,2, 1]$.


\section{Analogue of Fomin-Stanley construction on BPDs}
\label{S: construction}

We now construct $\fS^\BPD$, our analogue of $\fS^\PD$,
as a generating function of
the flagged tableaux, or equivalently BPDs. 
Instead of the nil-Coexter algebra $\N_n$, our construction
uses the \definition{Fomin-Kirillov algebra}~\cite{FK} $\E_n$,
generated by $\{d_{i,j}: 1 \leq i < j \leq n\}$ satisfying: 
\begin{align*}
\begin{cases}
d_{i,j}^2 & = 0 \textrm{ if $i < j$ }, \\
d_{i,j} d_{j,k}  & = d_{i,k} d_{i,j} + d_{j,k} d_{i,k}
\textrm{ if $i < j < k$ },\\
d_{j,k} d_{i,j}  & = d_{i,j} d_{i,k} + d_{i,k} d_{j,k}
\textrm{ if $i < j < k$ },\\
d_{i,j} d_{k,l}  & = d_{k,l} d_{i,j} 
\quad \textrm{if $i < j$, $k < l$ and $i, j, k, l$ distinct.}\\    
\end{cases}
\end{align*}


Fomin and Kirillov described an action of $\E_n$ on $\Q[S_n]$.
In this paper, we adopt a slightly different convention
and consider a right action of $\E_n$ on $\Q[S_n]$.
For $w \in S_n$,
$$
 w \odot d_{i,j} := \begin{cases}
w t_{i,j} & \text{if $wt_{i,j} \lessdot w$} \\
0 & \text{otherwise.}
\end{cases}
$$

Define
$A:= \Q[x_1, \cdots, x_{n-1}] \otimes \E_n$.
It acts on $\Q[x_1, \cdots, x_{n-1}][S_n]$ from the right:
$(fw) \odot (g \otimes e) = (fg)(w \odot e)$
for any $f, g \in \Q[x_1, \cdots, x_{n-1}]$, $w \in S_n$
and $e \in \E_n$.
We may identify $\E_n$ and $\Q[x_1, \cdots, x_{n-1}]$
as subalgebras of $A$.

\begin{defn}
Take $i \in [n-1]$.
For $i < j$, define $B_{i, j} \in \E_n$
as 
$B_{i,j} := 
d_{1, j} + \cdots + d_{i, j}$.
Define $R_i(x_i) \in A$ as
$R_i(x_i) := 
(x_i + B_{i, i+1})
(x_i + B_{i, i+2})
\cdots(x_i + B_{i, n})$.
Finally, define 
$\fS^\BPD$ 
$\in \Q[x_1, \cdots x_{n-1}][S_n]$ as 
$\fS^\BPD := w_0 \odot 
(R_1(x_1) R_2(x_2) \cdots R_{n-1}(x_{n-1}))$.
\end{defn}
We show $\fS^\BPD$ is a generating function
of flagged tableaux, or equivalently all BPDs:



\begin{prop}
We have
$$
\fS^\BPD = \sum_{w \in S_n} \sum_{T \in \FT(w)} x^{\wt(T)}w
= \sum_{w \in S_n} \sum_{D \in \BPD(w)} x^{\wt(D)}w.
$$
\end{prop}
\begin{proof}
If we expand $R_i(x_i)$, each term corresponds to
one way of filling row $i$ of a flagged tableau.
The expression $(x_i + B_{i, j})$ in $R_i(x_i)$
corresponds to ways of 
filling the cell at row $i$ 
and column $n+1-j$: 
$x_i$ means to leave the box empty
and $d_{p,j}$
means to fill it with $p$.
If we expand 
$R_1(x_1) \cdots R_{n-1}(x_{n-1})$,
for each term 
$x^\alpha d_{a_1, b_1} \cdots d_{a_k, b_k}$,
there is a flagged tableau 
$T$ with $\wt(T) = x^\alpha$
and $\word(T) = (a_1,b_1)\cdots (a_k, b_k)$.
Let $w = w_0 \odot d_{a_1, b_1} \cdots d_{a_k, b_k}$. 
If $w = 0$, we know $T$ is not associated with any permutation.
Otherwise, $T \in \FT(w)$.
Thus, we have the first equation.
The second equation follows from Proposition~\ref{P: BPD FT}. 
\end{proof}

Now we establish the BPD analogue of~(\ref{EQ: classical FS}).

\begin{thm}
\label{T: FS on BPD}
We have 
$\fS^\BPD = \sum_{w \in S_n} \fS_{w} w$.  
\end{thm}
Our proof is similar to the arguments
of Fomin and Stanley. 
Consider a right action of $\N_n$ on $S_n$
with $w \odot u_i = w t_{i, i+1}$ if $w(i) < w(i+1)$
and $w \odot u_i = 0$ otherwise.
We may extend this action to $\Q[x_1, \cdots, x_{n-1}][S_n]$
by setting $f \odot u_i = f$ for all $f \in \Q[x_1, \cdots, x_{n-1}]$.
Similar to Fomin and Stanley's approach, 
Theorem~\ref{T: FS on BPD} reduces to: 
\begin{prop}
\label{P: FS on BPD}
For each $i \in [n-1]$,
$\partial_i(\fS) = \fS \odot u_i$.   
\end{prop}
\begin{proof}[Proof Sketch]
The left hand side
is just 
$
w_0 \odot R_1(x_1) \cdots \partial_i(R_i(x_i)R_{i+1}(x_{i+1})) \cdots R_{n-1}(x_{n-1})$.
We turn the right hand side into 
$ 
w_0 \odot R_1(x_1) \cdots R_{i}(x_i)
\:u_{i, i+1}\: 
R_{i+1}(x_{i+1})
\cdots R_{n-1}(x_{n-1})
$.
Then we show 
$w_0 \odot
R_1(x_1) \cdots R_{i-1}(x_{i - 1})$
is in the span of terms $x^{\alpha} w$
where $x^\alpha$ is a monomial
involving $x_1, \cdots, x_{i-1}$
and $w \in S_n$ satisfies $w(i+1) > \cdots > w(n)$.
We just need 
\begin{align*}
x^\alpha w \odot \partial_i((R_i(x_i)R_{i+1}(x_{i+1}))
= x^\alpha w \odot R_{i}(x_i) \:u_{i, i+1}\: 
R_{i+1}(x_{i+1}) \textrm{ for such $x^\alpha w$}.    
\end{align*}
We then establish this equation via a complicated  but routine
computation. 
\end{proof}

Fomin and Kirillov~\cite{FK-algebra} defined the  \definition{Dunkl element}
$\theta_i := -\sum_{j < i} d_{j, i} + \sum_{j > i} d_{i,j} \in \E_n$
for $i \in [n]$.
They showed 
the Dunkl elements $\theta_1, \cdots, \theta_n$
commute with each other. 
We end this subsection by providing an alternative way to write $\fS^\BPD$ using Dunkl elements.

\begin{prop}
\label{P: Ultimate FS}
We have $\fS^\BPD = w_0 \odot \prod_{1 \leq i < j \leq n} (x_i - \theta_j)$.
Notice that terms 
multiplied on the right
hand side commute with each other, so the $\prod$ notation makes sense. 
\end{prop}

\begin{rem}
Sergey Fomin kindly informed the author that
$w_0 \odot \prod_{1 \leq i < j \leq n} (x_i - \theta_j)$
seems related to the following variation of Cauchy identity of Schubert polynomials:
\begin{align}
\label{EQ: Cauchy}
\prod_{1 \leq i < j \leq n} (x_i - y_j) = \sum_{w \in S_n} \fS_w(x_1, \cdots, x_{n-1})\fS_{w w_0}(-y_n, \cdots, -y_2).
\end{align}
Indeed, by the Monk's rule,~(\ref{EQ: Cauchy})
is equivalent to $w_0 \odot \prod_{1 \leq i < j \leq n} (x_i - \theta_j) = \sum_{w \in S_n}\fS_w w$.
In other words, Theorem~\ref{T: FS on BPD}
and Proposition~\ref{P: Ultimate FS}
form an alternative proof of~(\ref{EQ: Cauchy}).
\end{rem}


\section{Bijection between pipedreams and bumpless pipedreams}
\label{S: Growth}

In this section,
we present a weight preserving
bijection between $\PD(w)$ and $\BPD(w)$. 
By~\cite{LeSo} and Theorem~\ref{T: BPD to chain},
we just need a weight reversing bijection
between chains from $w$ to $w_0$ compatible with $(1,\cdots, n-1)$ and those compatible with $(n-1,\cdots, 1)$. 

This task can be done by Lenart's growth 
diagram~\cite{L_growth},
which can be viewed as the following algorithm.
Given $k_1, k_2 \in [n-1]$
and chains $C_1, C_2$,
where $C_1$ (resp. $C_2$)
is a saturated $k_1$-chain from $u$ to $v$
(resp. $k_2$-chain from $v$ to $w$),
the algorithm outputs a saturated 
$k_2$-chain from $u$ to $v'$ and a 
saturated $k_1$-chain from $v'$ to $w$.
Moreover, the $k_1$-chain 
(resp. $k_2$-chain) in the output
has the same length as $C_1$ (resp. $C_2$). 

Assume $C_1 = (u_1, \cdots, u_{d_1})$ and 
$C_2 = (w_1, \cdots, w_{d_2})$ where $u_{d_1} = w_1$.
We first draw:
$$
u_1 \xrightarrow{k_1} u_2 \xrightarrow{k_1}
\cdots \xrightarrow{k_1} u_{d_1 - 1} \xrightarrow{k_1} w_1
\xrightarrow{k_2} w_2 \xrightarrow{k_2}
\cdots \xrightarrow{k_2} w_{d_2}.
$$
We start from this labeled chain and apply a
local move: 
Find a part of the chain
that looks like $a \xrightarrow{k_1} b \xrightarrow{k_2} c$.
We must have $a \lessdot_{k_1} b \lessdot_{k_2} c$.
There exists a unique $b' \in S_n$
such that $b' \neq b$
and $a \lessdot b' \lessdot c$.
If $a \lessdot_{k_2} b' \lessdot_{k_1} c$,
we replace this part of the chain by
$a \xrightarrow{k_2} b' \xrightarrow{k_1} c$.
Otherwise, 
we must have $a \lessdot_{k_2} b' \lessdot_{k_1} c$
and we replace this part
by $a \xrightarrow{k_2} b \xrightarrow{k_1} c$.
We keep applying this local move until 
the labeled chain looks like:
$$
u_1' \xrightarrow{k_2} u_2' \xrightarrow{k_2}
\cdots \xrightarrow{k_2} u_{d_2 - 1}' \xrightarrow{k_2} w_1'
\xrightarrow{k_1} w_2' \xrightarrow{k_1}
\cdots \xrightarrow{k_1} w_{d_1}'.
$$
Then we output
the $k_2$-chain $(u_1', \cdots, u_{d_2-1}', w_1')$ and the $k_1$-chain
$(w_1', \cdots, w_{d_1}')$.
 

\begin{exa}
\label{E: growth}
Say the inputs are: $k_1 = 2$, $k_2 = 3$, 
$C_1 = ([2,1,4,3], [2,4,1,3], [3,4,1,2])$, 
and $C_2 = ([3,4,1,2], [3,4,2,1])$.
We start from the following labeled chain
and apply local moves: 
$$
[2,1,4,3] \xrightarrow{2} [2,4,1,3] \xrightarrow{2} [3,4,1,2]
\xrightarrow{3} [3,4,2,1].
$$
$$
[2,1,4,3] \xrightarrow{2} [2,4,1,3] \xrightarrow{3} [2,4,3,1]
\xrightarrow{2} [3,4,2,1],
$$
$$
[2,1,4,3] \xrightarrow{3} [2,3,4,1] \xrightarrow{2} [2,4,3,1]
\xrightarrow{2} [3,4,2,1].
$$
Therefore, the outputs are $([2,1,4,3], [2,3,4,1])$ and $([2,3,4,1], [2,4,3,1], [3,4,2,1])$. 
\end{exa}

We may use Lenart's growth diagram
to define a map $\growth_{k_1, k_2}$.
\begin{defn}
Take a chain $(u,v,w)$ that is compatible with
$(k_1, k_2)$.
Let $C_1$ (resp. $C_2$)
be the increasing $k_1$-chain (resp. $k_2$-chain)
from $u$ to $v$ (resp. $v$ to $w$).
Input $C_1, C_2, k_1, k_2$
to Lenart's growth diagram,
obtaining a $k_2$-chain from $u$
to $v'$ and a $k_1$-chain from $v'$
to $w$.
Then define $\growth_{k_1, k_2}(u,v,w)$
as $(u, v', w)$.
\end{defn}

The map $\growth_{k_1, k_2}$
does not solve Problem~\ref{prob: chain}.
When $(u,v,w)$ is compatible with $(k_1, k_2)$, $\growth_{k_1, k_2}(u,v,w)$
might not be compatible with $(k_2, k_1)$:
By Example~\ref{E: growth}, we have
$$\growth_{2,3}([2,1,4,3], [3,4,1,2], [3,4,2,1])
= ([2,1,4,3], [2,3,4,1], [3,4,2,1]),$$
which is not compatible with $(3,2)$,
but $([2,1,4,3], [3,4,1,2], [3,4,2,1])$
is compatible with $(2, 3)$.
Nevertheless, 
$\growth_{k_1, k_2}$
solves Problem~\ref{prob: chain}
in the following special case.


\begin{lemma}
\label{L: growth}
Take $1 \leq k_2 < k_1 \leq n-1$
and $u, w \in S_n$ such that 
$w(k_1+1) > w(k_1+2) > \cdots > w(n)$
and $w(j) = n + 1 - j$ 
for each $j \in [k_2]$.
Then $\growth_{k_1,k_2}$ is
a weight reversing 
bijection from chains $(u,v,w)$
compatible with $(k_1, k_2)$
to chains $(u,v',w)$
compatible with $(k_2, k_1)$.
\end{lemma}

Now we use $\growth_{k_1,k_2}$ to derive a map $\Growth$.
This map is defined on a chain 
$C = (w_n, \cdots, w_1)$ from $w$ to $w_0$ 
compatible with $(n-1, \cdots,2, 1)$.
It first applies $\growth_{2,1}$, $\growth_{3,1}$, $\cdots$, 
$\growth_{n-1,1}$ 
to get a chain compatible with $(1, n-1, \cdots, 2)$.
Then it applies 
$\growth_{3,2}, \cdots, \growth_{n-1,2}$
to get a chain compatible with $(1, 2, n-1, \cdots, 3)$.
Eventually, it produces a chain
compatible with $(1,2, \cdots, n-1)$
defined as $\Growth(C)$.
We can check when we apply 
each $\growth_{k_1, k_2}$,
the condition in Lemma~\ref{L: growth} is satisfied.
\begin{prop}
For $w \in S_n$,
the map $\Growth$ is a weight-reversing bijection
from $\{$chains from $w$ to $w_0$ compatible with
$(n-1, \cdots, 1)\}$
to $\{$chains from $w$ to $w_0$ compatible with
$(1, \cdots, n-1)\}$.
\end{prop}
By~\cite{LeSo} and Theorem~\ref{T: BPD to chain},
$\Growth$ leads to a weight preserving bijection
between $\PD(w)$ and $\BPD(w)$, which we conjecture agrees with the bijection of Gao-Huang~\cite{GH}.

\begin{exa}
Consider the chain 
$([2,1,4,3],[2,3,4,1],[2,4,3,1],[4,3,2,1])$
which is
compatible with $(3,2,1)$
and has weight $(1,1,2)$.
We apply $\growth_{2,1}$
and then $\growth_{3,1}$
to get $([2,1,4,3],[4,1,3,2],[4,2,3,1],[4,3,2,1])$
which is compatible with $(1,3,2)$ and has weight 
$(2,1,1)$.
Finally, use $\growth_{3,2}$
to get 
$([2,1,4,3],[4,1,3,2],[4,3,1,2],[4,3,2,1])$
which is compatible with $(1,2,3)$ and has weight 
$(2,1,1)$.
\end{exa}

\section{Extending Corollary~\ref{C: Bruhat formula} to double Schubert polynomials}
\label{S: Double}
The \definition{double Schubert polynomial} $\fS_w(\textbf{x},\textbf{y})$
is in $x_1, \cdots, x_{n-1}$
and $y_1, \cdots, y_{n-1}$.
It recovers $\fS_w$ after setting
each $y_i$ to $0$
and can be computed using 
PDs and BPDs:
For $P \in \PD(w)$ (resp. $\BPD(w)$),
let $\WT(P)$ 
be the product over $\ptile$ (resp. $\btile$) in $P$,
where the tile in row $i$ column $j$ gives $(x_i - y_j)$.
By~\cite{KM, W}, $\fS_w (\textbf{x},\textbf{y})$
$= \sum_{P \in \PD(w)} \WT(P)
= \sum_{P \in \BPD(w)} \WT(P)$.

Take $\gamma \in S_{n-1}$
and let $C = (w_1, \cdots, w_n)$ 
be a chain compatible with $\gamma$.
Define $\WT_\gamma(C)$
as $\prod_{i = 1}^{n-1} \prod_t (x_{\gamma_i} - y_{w_i(t)})$,
where $t$ runs over all 
$t > \gamma_i$
such that $w_i(t) = w_{i+1}(t)$.
After setting all $y_i$ to $0$, $\WT_\gamma(C)$
recovers $x^{(n-1, \cdots, 1) - \gamma^{-1}(\wt(C))}$.
The following conjecture
extends Corollary~\ref{C: Bruhat formula}
and has been checked for all $w \in S_n$ for $n \leq 8$ and all $\gamma \in S_{n-1}$:
\begin{conj}
For $\gamma \in S_{n-1}$, 
we have $\fS_w$ $(\textbf{x},\textbf{y}) = \sum_{C: \textrm{chain from $w$ to $w_0$ compatible with $\gamma$}} \WT_\gamma(C)$. 
\end{conj}
This conjecture agrees with the PD and BPD formula
when $\gamma = [1, \cdots, n-1]$ 
and $\gamma = [n-1, \cdots, 1]$
respectively 
via the bijections in~\cite{LeSo}
and Theorem~\ref{T: BPD to chain}.

\acknowledgements{}
We thank Yibo Gao for suggesting 
this project.
We thank Yibo Gao and Zachary Hamaker for many important suggestions, including using Lenart's Growth diagram to
obtain a bijection between PDs and BPDs.
We thank Yuhan Jiang and Brendon Rhoades for
carefully reading an earlier version
of this paper and providing valuable comments. 

\printbibliography
\end{document}
