%~Mouliné par MaN_auto v.0.19.1 2018-08-16 10:27:57
\documentclass[ALCO,Unicode,ThmDefs]{cedram}
\OneNumberAllTheorems

\usepackage{tikz}
\usepackage{wrapfig}

\usetikzlibrary{decorations.markings}

\graphicspath{{./figures/}}

\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}
\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}}

\let\oldforall\forall
\renewcommand*{\forall}{\mathrel{\oldforall}}
\let\oldexists\exists
\renewcommand*{\exists}{\mathrel{\oldexists}}

\title{Schubert polynomials, 132-patterns, and Stanley's conjecture}

\author[\initial{A.} \middlename{E.} Weigandt]{\firstname{Anna} \middlename{E.} \lastname{Weigandt}}
\address{University of Illinois at Urbana-Champaign\\
Dept.~of Mathematics\\
1409 W.~Green St.\\
Urbana\\
IL 61801, USA}
\email{weigndt2@illinois.edu}
\thanks{The author was supported by the Ruth V.~Shaff and Genevie I.~Andrews Fellowship.}

\keywords{Schubert polynomials, permutation patterns}
%\subjclass{missing subjclass}

\begin{abstract}
Motivated by a recent conjecture of R.~P.~Stanley we offer a lower bound for the sum of the coefficients of a Schubert polynomial in terms of $132$-pattern containment.
\end{abstract}


\begin{document}
\maketitle


\section{Introduction}

This paper is motivated by a conjecture of R.~P.~Stanley~\cite[Conjecture~4.1]{stanley2017some} concerning the \emph{Schubert polynomials} of A.~Lascoux and M.-P.~Sch\"utzenberger~\cite{Lascoux.Schutzenberger}. A \emph{permutation} is a bijection from the set $\{1,2,\ldots,n\}$ to itself. We typically represent a permutation in one-line notation. For instance, $w=25143$ is the permutation which maps $1$ to $2$, $2$ to $5$, $3$ to $1$, and so on. The \emph{symmetric group} $S_n$ consists of the set of permutations.

If $w_0=n \, n-1 \, \ldots \, 1$ is the longest permutation in $S_n$, define
\[
\mathfrak S_{w_0}:=x_1^{n-1}x_2^{n-2}\cdots x_{n-1}.
\]
For any other $w\in S_n$, there is some $i$ so that $w(i)<w(i+1)$. Then $\mathfrak S_{w}=\partial_i \mathfrak S_{ws_i}$, where $\partial_if:=\frac{f-s_if}{x_i-x_{i+1}}$ and $s_i=(i,i+1)$ acts on $f$ by exchanging the variables $x_i$ and $x_{i+1}$. The $\partial_i$'s satisfy the same braid and commutativity relations as the simple transpositions and so $\mathfrak S_w$ is well defined. The polynomial $\mathfrak S_w$ is called a \emph{Schubert polynomial}. We will use an equivalent definition for Schubert polynomials as a weighted sum over \emph{pipe dreams}. See Section~\ref{section:background} for these definitions.

We are interested in the following specialization: $\nu_w:=\mathfrak S_w(1,1,\ldots, 1).$ Let
\begin{equation}\label{eqn:132patterns}
P_{132}(w):=\{(i,j,k): i<j<k \enspace \text{and} \enspace w(i)<w(k)<w(j)\}.
\end{equation}
Write $\eta_w:=\#P_{132}(w)$. If $\eta_w\geq 1$ then $w$ \emph{contains} the pattern $132$.

\begin{exam}\label{example:contains132}
Let $w=25143$. Below, we list the elements of $P_{132}(w)$ by marking in bold the positions $i<j<k$ for which $(i,j,k)\in P_{132}(w)$.
\[
\mathbf{25}1\mathbf{4}3 \quad \mathbf{25}14\mathbf{3} \quad \mathbf{2}51\mathbf{43} \quad 25\mathbf{143} \quad
\]
As such, $\eta_w=4$.
\end{exam}

We prove that $\eta_w$ provides a lower bound for $\nu_w$.
\begin{theo}[The $132$-bound]\label{theorem:bound}
For any $w\in S_n$, $\nu_w\geq \eta_w+1$.
\end{theo}

As a corollary, we obtain the following conjecture of R.~P.~Stanley~\cite[Conjecture~4.1]{stanley2017some}.
\begin{coro}\label{cor:main}
$\nu_w=2$ if and only if $\eta_w=1$.
\end{coro}

\begin{proof}

Let $w\in S_n$. If $\eta_w=0$ then $\nu_w=1$~\cite[Chapter~4]{macdonald1991notes}. If $\eta_w=1$ then $\nu_w=2$~\cite[Section~4]{stanley2017some}. Otherwise, $\eta_w\geq 2$. Then we apply Theorem~\ref{theorem:bound} and obtain
\[
\nu_w\geq \eta_w+1 \geq 3.
\]
As such, $\nu_w=2$ if and only if $\eta_w=1$.
\end{proof}


\section{Background on Permutations and Pipe Dreams}\label{section:background}


We will recall the necessary background on permutations and Schubert polynomials; our references are~\cite[Chapter~2]{manivel2001symmetric} and~\cite{bergeron1993rc} respectively. Each permutation has an associated \emph{rank function} $r_w$, where
\begin{equation}\label{eqn:rank}
r_w(i,j):=\#\{k:1\leq k\leq i \enspace \text{and} \enspace w(k)\leq j\}.
\end{equation}
The pair $(i,j)$ is an \emph{inversion} of $w$ if $i<j$ and $w(i)>w(j)$. Equivalently, each inversion corresponds to a 21-pattern in $w$. The \emph{length} of a permutation is the number inversions,
\begin{equation}
\ell(w):=\#\{(i,j): i<j
\enspace \text{and} \enspace w(i)>w(j)\}.
\end{equation}
The \emph{Rothe diagram} of $w\in S_n$ is the set
\begin{equation}\label{eqn:rothe}
D(w):=\{(i,j):1\leq i,j\leq n, w(i)>j, \enspace \text{and} \enspace w^{-1}(j)>i\}.
\end{equation}
Notice immediately from~\eqref{eqn:rothe}, we have
\begin{equation}\label{eqn:diagramsym}
D(w^{-1})=D(w)^t.
\end{equation}
The diagram $D(w)$ is in bijection with the set of inversions of $w$ by the map
\begin{equation}\label{eqn:diaginvbij}
(i,j)\mapsto (i,w^{-1}(j)).
\end{equation}


\begin{wrapfigure}{r}{.175\textwidth}
\centering
\vspace{-1em}
\begin{tikzpicture}[x=1em,y=1em]
\draw[step=1,gray!30,very thin] (0,1) grid (5,6);
\draw[color=black, thick](0,1)rectangle(5,6);
\filldraw [black](1.5,5.5)circle(.1);
\filldraw [black](4.5,4.5)circle(.1);
\filldraw [black](0.5,3.5)circle(.1);
\filldraw [black](3.5,2.5)circle(.1);
\filldraw [black](2.5,1.5)circle(.1);
\filldraw[color=black, fill=gray!30, thick](0,5)rectangle(1,6);
\filldraw[color=black, fill=gray!30, thick](0,4)rectangle(1,5);
\filldraw[color=black, fill=gray!30, thick](3,4)rectangle(4,5);
\filldraw[color=black, fill=gray!30, thick](2,4)rectangle(3,5);
\filldraw[color=black, fill=gray!30, thick](2,2)rectangle(3,3);
\draw[thick] (.5,3.5)--(.5,1);
\draw[thick] (1.5,5.5)--(1.5,1);
\draw[thick] (2.5,1.5)--(2.5,1);
\draw[thick] (3.5,2.5)--(3.5,1);
\draw[thick] (4.5,4.5)--(4.5,1);
\draw[thick] (1.5,5.5)--(5,5.5);
\draw[thick] (4.5,4.5)--(5,4.5);
\draw[thick] (0.5,3.5)--(5,3.5);
\draw[thick] (3.5,2.5)--(5,2.5);
\draw[thick] (2.5,1.5)--(5,1.5);
\end{tikzpicture}
\vspace{-1em}
\end{wrapfigure} We may visualize $D(w)$ as follows. For each $i=1,\ldots, n$, plot $(i,w(i))$. Then, strike out all boxes to the right and below each of the plotted points. The boxes which remain form $D(w)$. For example, $D(25143)$ is pictured to the right. Notice that we use matrix conventions; cell $(i,j)$ sits in the $i$th row from the top and the $j$th column from the left.



Schubert polynomials can be written as a sum over \emph{pipe dreams}. Pipe dreams appear in the literature under various names; they are the \emph{pseudo-line configurations} of S.~Fomin and A.~N.~Kirillov~\cite{fomin1996yang} and the \emph{RC-graphs} of N.~Bergeron and S.~C.~Billey~\cite{bergeron1993rc}. They were studied from a geometric perspective by A.~Knuston and E.~Miller~\cite{knutson2005grobner}.

Let $\mathbb Z_{> 0}\times \mathbb Z_{> 0}$ be the semi-infinite grid, starting from the northwest corner. A \emph{pipe dream} is a tiling of this grid with \includegraphics[scale=.6]{elbow}'s (elbows) and a finite number of $+$'s (pluses). For simplicity, we will often draw the elbows as dots. We freely identify each pipe dream with a subset of $\mathbb Z_{> 0}\times \mathbb Z_{> 0}$ by recording the coordinates of the pluses. Associate a weight monomial to $\mathcal P$:
\[
{\tt wt}(\mathcal P)=\prod_{(i,j)\in \mathcal P} x_i.
\]
Equivalently, the exponent of $x_i$ counts the number of pluses which appear in row $i$ of $\mathcal P$.

\begin{wrapfigure}{l}{0.17\textwidth}
\centering
\includegraphics[width=0.17\textwidth]{25143}
\vspace{-2em}
\end{wrapfigure} We may interpret $\mathcal P$ as a collection of overlapping strands, using the rule that a strand never bends at a right angle. The $+$'s indicate the positions where two strands cross. Each row on the left edge of $\mathbb Z_{> 0}\times \mathbb Z_{> 0}$ is connected by some strand to a unique column along the top, and vice versa. If the $i$th row is connected to the $j$th column, let $w_{\mathcal P}(i):=j$. There exists some $n$ so that $w_{\mathcal P}(i)=i$ for all $i>n$, so $w_{\mathcal P}\in S_\infty$. In practice, we identify $w_\mathcal P$ with its representative in some finite symmetric group. For example, if $\mathcal P$ is the pipe dream pictured above, then we write $w_\mathcal P=25143$.

If $\#\mathcal P=\ell(w_\mathcal P)$ then $\mathcal P$ is \emph{reduced}. Let
\[
{\tt RP}(w):=\{\mathcal P: w_\mathcal P=w \enspace \text{and} \enspace \mathcal P \enspace \text{is reduced}\}.
\]
\begin{theo}[\cite{bergeron1993rc,fomin1996yang}]\label{thm:pipe}
\begin{equation}\label{eqn:schubertdef}
\mathfrak S_w=\sum_{\mathcal P\in {\tt RP}(w)}{\tt wt}(\mathcal P).
\end{equation}
\end{theo}

Recall, $\nu_w:=\mathfrak S_w(1,1,\ldots, 1).$ Immediately from~\eqref{eqn:schubertdef}, $\nu_w=\#{\tt RP}(w)$.

\begin{exam}\label{example:schub}
The reduced pipe dreams for $w=25143$ are pictured below.
\[
\left[
\begin{array}{ccccc}
+ & \cdot & + & +&\cdot\\
+ & \cdot & + & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot & \cdot
\end{array}\right]
\quad
\left[
\begin{array}{ccccc}
+ & \cdot & + & \cdot&\cdot\\
+ & + & + & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot & \cdot
\end{array}\right]
\quad
\left[
\begin{array}{ccccc}
+ & \cdot & + & +&\cdot\\
+ & \cdot & \cdot & \cdot&\cdot\\
\cdot & + & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot & \cdot
\end{array}\right]
\quad
\left[
\begin{array}{ccccc}
+ & \cdot & \cdot & +&\cdot\\
+ & + & \cdot & \cdot&\cdot\\
\cdot & + & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot & \cdot
\end{array}\right]
\]
\[
\left[
\begin{array}{ccccc}
+ & \cdot & \cdot & \cdot&\cdot\\
+ & + & + & \cdot&\cdot\\
\cdot & + & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot & \cdot
\end{array}\right]
\quad
\left[
\begin{array}{ccccc}
+ & \cdot & + & +&\cdot\\
+ & \cdot & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot&\cdot\\
+ & \cdot & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot & \cdot
\end{array}\right]
\quad
\left[
\begin{array}{ccccc}
+ & \cdot & \cdot & +&\cdot\\
+ & + & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot&\cdot\\
+ & \cdot & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot & \cdot
\end{array}\right]
\quad
\left[
\begin{array}{ccccc}
+ & \cdot & \cdot & \cdot&\cdot\\
+ & + & + & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot&\cdot\\
+ & \cdot & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot & \cdot
\end{array}\right]
\]
Therefore,
\[
\mathfrak S_w=x_1^3x_2^2 + x_1^2x_2^3 + x_1^3x_2x_3 + x_1^2x_2^2x_3 + x_1x_2^3x_3 + x_1^3x_2x_4 + x_1^2x_2^2x_4 + x_1x_2^3x_4
\]
and $\nu_w=8$.
\end{exam}

There are two pipe dreams which have an explicit description in terms of $w$. Let
\begin{equation}\label{eqn:m}
m_i(w)=
\#\{j:(i,j)\in D(w)\}.
\end{equation}
Then the \emph{bottom pipe dream} is
\begin{equation}\label{eqn:botbound}
\mathcal B_w=\{(i,j):j\leq m_i(w)\}.
\end{equation}
Graphically, $\mathcal B_w$ is obtained from $D(w)$ by replacing each box with a plus and then left justifying within each row. We define the \emph{top pipe dream} as the transpose of the bottom pipe dream of $w^{-1}$:
\[
\mathcal T_w:=\mathcal B_{w^{-1}}^t.
\]
By~\eqref{eqn:diagramsym}, $\mathcal T_w$ is obtained from $D(w)$ by top justifying pluses within columns.
\begin{exam}\label{example:bottomtop}
Let $w=25143$.
\[
\mathcal B_w=\left[
\begin{array}{ccccc}
+ & \cdot & \cdot & \cdot&\cdot\\
+ & + & + & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot&\cdot\\
+ & \cdot & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot & \cdot
\end{array}\right]
\hspace{3em}
\mathcal T_w=\left[
\begin{array}{ccccc}
+ & \cdot & + & +&\cdot\\
+ & \cdot & + & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot&\cdot\\
\end{array}\right]
\]
Pictured above are the bottom and top pipe dreams for $w$.
\end{exam}

N.~Bergeron and S.~C.~Billey gave a procedure to obtain any pipe dream in ${\tt RP}(w)$ algorithmically, starting from $\mathcal B_w$. A \emph{ladder move} is an operation on pipe dreams which produces a new pipe dream by a replacement of the following type.
\[
\begin{array}{cc}
\cdot &\cdot \\
+&+\\
+&+\\
\vdots &\vdots \\
+&+\\
+ & \cdot
\end{array} \quad \mapsto \quad
\begin{array}{cc}
\cdot &+ \\
+&+\\
+&+\\
\vdots &\vdots \\
+&+\\
\cdot & \cdot
\end{array}
\]
In the above picture, the columns and rows are consecutive. If $\mathcal P\mapsto \mathcal P'$ is a ladder move, then $\mathcal P\in {\tt RP}(w)$ if and only if $\mathcal P'\in {\tt RP}(w)$. In other words, ${\tt RP}(w)$ is closed under ladder moves~\cite{bergeron1993rc}. Furthermore, any element of ${\tt RP}(w)$ can be reached by some sequence of ladder moves from the bottom pipe dream.

\begin{theo}[{\cite[Theorem~3.7]{bergeron1993rc}}]\label{theorem:bb}
If $\mathcal P\in {\tt RP}(w)$, then $\mathcal P$ can be obtained by a sequence of ladder moves from $ \mathcal B_w$.
\end{theo}

We will mostly focus on a special type of ladder move. A \emph{simple ladder move} is a replacement of the following form.
\[
\begin{array}{cc}\cdot &\cdot \\ + & \cdot
\end{array} \quad \mapsto \quad
\begin{array}{cc}\cdot &+ \\ \cdot & \cdot
\end{array}
\]

The outline of the proof is as follows. In Lemma~\ref{lemma:biject}, we show that any sequence of ladder moves connecting $\mathcal B_w$ to $\mathcal T_w$ must use only simple ladder moves. The exact number of pipe dreams in any such sequence, is $\eta_w+1$. Since each pipe dream in the sequence is distinct, this provides a lower bound for $\nu_w=\#{\tt RP}(w)$.



\section{Proof of Theorem~\ref{theorem:bound}}\label{section:proof}
We start by interpreting $\eta_w$ as a weighted sum over $D(w)$. The ``32'' in each 132-pattern of $w$ corresponds to a box $(i,j)\in D(w)$. The ``1'' contributes to the rank function $r_w(i,j)$.
\begin{lemm}\label{lemma:eta}
\[
\eta_w=\sum_{(i,j)\in D(w)} r_w(i,j).
\]
\end{lemm}
\begin{proof}
Suppose $(i,j,k)\in P_{132}(w)$. Then $w(j)>w(k)$ and $w^{-1}(w(k))=k>j$. By~\eqref{eqn:rothe}, we have $(j,w(k))\in D(w)$. Furthermore, $i\leq j$ and $w(i)\leq w(k)$. Then by~\eqref{eqn:rank},
\[
\#\{\ell:(\ell,j,k)\in P_{132}(w)\}\leq \#\{\ell:\ell\leq j \enspace \text{and} \enspace w(\ell)\leq w(k)\}=r_w(j,w(k)).
\]
Then
\begin{equation}\label{eqn:1}
\eta_w\leq \sum_{(i,j)\in D(w)} r_w(i,j).
\end{equation}
On the other hand, suppose $(i,j)\in D(w)$. Then
\[
w(i)>j=w(w^{-1}(j)) \enspace \text{and} \enspace w^{-1}(j)>i.
\]
Take
\[
k\in \{k:k\leq i \enspace \text{and} \enspace w(k)\leq j\}.
\]
Since $(i,j)\in D(w)$, we must have $k<i$ and $w(k)<j$. Then
\[
k<i<w^{-1}(j) \enspace \text{and} \enspace w(k)<w(w^{-1}(j))<w(i)
\]
and so
\[
(k,i,w^{-1}(j))\in P_{132}(w).
\]
As such, if $(i,j)\in D(w)$,
\[
\#\{\ell:(\ell,i,w^{-1}(j))\in P_{132}(w)\}\geq r_w(i,j).
\]
Therefore,
\begin{equation}\label{eqn:2}
\eta_w\geq \sum_{(i,j)\in D(w)} r_w(i,j).
\end{equation}
As such,
\[
\eta_w= \sum_{(i,j)\in D(w)} r_w(i,j).\qedhere
\]
\end{proof}

\begin{exam}
Again, let $w=25143$. Below, we label each box $(i,j)\in D(w)$ with $r_w(i,j)$.
\[
\begin{tikzpicture}[x=1em,y=1em]
\draw[step=1,gray!30,very thin] (0,1) grid (5,6);
\draw[color=black, thick](0,1)rectangle(5,6);
\filldraw [black](1.5,5.5)circle(.1);
\filldraw [black](4.5,4.5)circle(.1);
\filldraw [black](0.5,3.5)circle(.1);
\filldraw [black](3.5,2.5)circle(.1);
\filldraw [black](2.5,1.5)circle(.1);
\filldraw[color=black, fill=gray!30, thick](0,5)rectangle(1,6);
\filldraw[color=black, fill=gray!30, thick](0,4)rectangle(1,5);
\filldraw[color=black, fill=gray!30, thick](3,4)rectangle(4,5);
\filldraw[color=black, fill=gray!30, thick](2,4)rectangle(3,5);
\filldraw[color=black, fill=gray!30, thick](2,2)rectangle(3,3);
\draw[thick] (.5,3.5)--(.5,1);
\draw[thick] (1.5,5.5)--(1.5,1);
\draw[thick] (2.5,1.5)--(2.5,1);
\draw[thick] (3.5,2.5)--(3.5,1);
\draw[thick] (4.5,4.5)--(4.5,1);
\draw[thick] (1.5,5.5)--(5,5.5);
\draw[thick] (4.5,4.5)--(5,4.5);
\draw[thick] (0.5,3.5)--(5,3.5);
\draw[thick] (3.5,2.5)--(5,2.5);
\draw[thick] (2.5,1.5)--(5,1.5);
\node[] at (.5,5.5){0};
\node[] at (.5,4.5){0};
\node[] at (2.5,4.5){1};
\node[] at (3.5,4.5){1};
\node[] at (2.5,2.5){2};
\end{tikzpicture}
\]
As such,
\[
\sum_{(i,j)\in D(w)} r_w(i,j)=4.
\]
In Example~\ref{example:contains132}, we found that $\eta_w=4$. This agrees with Lemma~\ref{lemma:eta}.
\end{exam}



If $\mathcal P\in{\tt RP}(w)$, let $\mathbf a_{\mathcal P}:=(a_\mathcal P(1),\ldots, a_\mathcal P(n))$ where
\begin{equation}\label{eqn:antidiagcount}
a_\mathcal P(k)=\#\{(i,j)\in \mathcal P:i+j-1=k\}.
\end{equation}
Equivalently, $a_\mathcal P(k)$ is the number of pluses that occur in the $k$th antidiagonal of $\mathcal P$. Notice if $\mathcal P\mapsto \mathcal P'$ is a simple ladder move, then $\mathbf a_{\mathcal P}=\mathbf a_{\mathcal P'}$. If $\mathcal P\mapsto \mathcal P'$ is a ladder move which is not simple, then $\mathbf a_{\mathcal P}\neq \mathbf a_{\mathcal P'}$.
\begin{exam}
Let $\mathcal P,\mathcal P'\in {\tt RP}(25143)$ be as pictured below.
\[
\mathcal P=\left[
\begin{array}{ccccc}
+ & \cdot & \cdot & \cdot&\cdot\\
+ & + & + & \cdot&\cdot\\
\cdot & + & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot & \cdot
\end{array}\right] \hspace{3em} \mathcal P'=\left[
\begin{array}{ccccc}
+ & \cdot & + & \cdot&\cdot\\
+ & + & + & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot&\cdot\\
\cdot & \cdot & \cdot & \cdot & \cdot
\end{array}\right]
\]
Although $\mathcal P'$ can be obtained from $\mathcal P$ by a ladder move, it is not a simple ladder move. Indeed, $\mathbf a_{\mathcal P}=(1,1,1,2,0)$ and $\mathbf a_{{\mathcal P}'}=(1,1,2,1,0)$. Therefore, $\mathbf a_{\mathcal P}\neq \mathbf a_{{\mathcal P}'}$.
\end{exam}

This idea extends to sequences of ladder moves.

\begin{lemm}\label{lemma:simpleladder}
Suppose there is a path of ladder moves from $\mathcal P$ to $\mathcal Q$:
\begin{equation}\label{eqn:otherplus}
\mathcal P=\mathcal P_0\mapsto\mathcal P_1\mapsto \cdots \mapsto \mathcal P_N=\mathcal Q.
\end{equation}
Each ladder move in \eqref{eqn:otherplus} is simple if and only if $\mathbf a_{\mathcal P}=\mathbf a_{\mathcal Q}$.
\end{lemm}

\begin{proof}\ 

$(\Rightarrow)$ Assume each $\mathcal P_i\mapsto \mathcal P_{i+1}$ is a simple ladder move. Then $\mathcal P_{i+1}$ is obtained from $\mathcal P_{i}$ by moving a single plus to a new position in the same antidiagonal. As such, $\mathbf a_{\mathcal P_i}=\mathbf a_{\mathcal P_{i+1}}$ for each $i$. Therefore $\mathbf a_{\mathcal P}=\mathbf a_{\mathcal Q}.$

$(\Leftarrow)$ We prove the contrapositive. Suppose there is a nonsimple ladder move in the sequence~\eqref{eqn:otherplus}. It acts by removing a plus from the $i$th antidiagonal and replacing it in the $j$th antidiagonal with $i<j$. In particular, we may pick $j$ to be the maximum such label. By the maximality, no plus moves into the $j$th antidiagonal from a different antidiagonal. Then $a_{\mathcal P}(j)> a_{\mathcal Q}(j)$ and so $\mathbf a_{\mathcal P}\neq \mathbf a_{\mathcal Q}.$
\end{proof}

Fix an indexing set $I$. A labeling of a pipe dream is an injective map $\mathcal L_\mathcal P:\mathcal P\rightarrow I$. Suppose $\mathcal P\mapsto \mathcal P'$ is a simple ladder move. Then $\mathcal P'$ inherits a labeling from $\mathcal P$ as follows:
\[
\mathcal L_{\mathcal P'}(i,j)=
\begin{cases}
\mathcal L_{\mathcal P}(i,j) & \text{if} \enspace (i,j)\in \mathcal P\\
\mathcal L_{\mathcal P}(i+1,j-1) & \text{otherwise}.
\end{cases}
\]
Since $\mathcal P\mapsto \mathcal P'$ is a simple ladder move, $\mathcal P'$ is obtained from $\mathcal P$ by adding some $(i,j)$ to $\mathcal P$ and removing $(i+1,j-1)$. Therefore $\mathcal L_{\mathcal P'}$ is well defined. If there is a path of simple ladder moves from $\mathcal P$ to $\mathcal Q$, then $\mathcal Q$ inherits the labeling $\mathcal L_\mathcal Q$ from $\mathcal L_\mathcal P$ inductively.

\begin{lemm}\label{lemma:justsimple}
Let $L_\mathcal P$ be a labeling. Suppose $\mathcal Q$ can be reached from $\mathcal P$ by simple ladder moves. Then $\mathcal Q$ inherits the same labeling from $\mathcal P$ regardless of the choice of sequence.
\end{lemm}

\begin{proof}
Suppose $\mathcal P\mapsto \mathcal P'$ is a simple ladder move. Then within any antidiagonal, both pipe dreams have the same set of labels in the same relative order. Iterate this argument along a path of simple ladder moves from $\mathcal P$ to $\mathcal Q$. Then, in each antidiagonal, $\mathcal P$ and $\mathcal Q$ have the same set of labels, still in the same relative order. As such, the labeling is uniquely determined and independent of the choice of path.
\end{proof}

\begin{lemm}\ \label{lemma:biject}
\begin{enumerate}[label=(\roman*)]
\item \label{3.6.i} The map
\[
(i,j)\mapsto (i,j-r_w(i,j))
\]
is a bijection between $D(w)$ and $\mathcal B_w$.
\item \label{3.6.ii} The map
\[
(i,j)\mapsto (i-r_w(i,j),j)
\]
is a bijection between $D(w)$ and $\mathcal T_w$.
\item \label{3.6.iii} $\mathcal B_w$ and $\mathcal T_w$ are connected by simple ladder moves.
\end{enumerate}
\end{lemm}

\begin{proof}\ 

\ref{3.6.i}.
Suppose $\ell>i$ and $w(\ell)<w(i)$. Since $w^{-1}(w(\ell))=\ell>i$ and $w(i)>w(\ell)$, by~\eqref{eqn:rothe}, we have $(i,w(\ell))\in D(w)$. Therefore,
\[
w(\ell)\in \{j:(i,w(j))\in D(w)\}.
\]
By~\eqref{eqn:m}, the $i$th row of $D(w)$ has as many boxes as there are pluses in the $i$th row of $\mathcal B_w$. Let
\[
j_1<j_2<\cdots<j_{m_i(w)}
\]
be the sequence obtained by sorting the set $\{j:(i,j)\in D(w)\}$. Then
\begin{align*}
j_\ell-r_w(i,j_\ell)&=j_\ell-\#\{k:k\leq i \enspace \text{and} \enspace w(k)\leq j_\ell\}\\
&=\#\{k:k> i \enspace \text{and} \enspace w(k)\leq j_\ell\}\\
&=\#\{j:(i,j)\in D(w) \enspace \text{and} \enspace j\leq j_\ell \}\\
&=\ell.
\end{align*}
Therefore $(i,j_\ell)\mapsto (i,\ell)$. Since $1\leq \ell\leq m_i(w)$ the map is well defined. This holds for any
\[
\ell\in \{1,\ldots,m_i(w)\}
\]
so the map is surjective. By definition, $j_\ell=j_{\ell'}$ if and only if $\ell=\ell'$, giving injectivity. As such, this is a bijection.

\ref{3.6.ii}. Let $\phi$ be the map defined by $(i,j)\mapsto (j,i)$. Restricted to $D(w)$, $\phi$ is a bijection between $D(w)$ and $D(w^{-1})$. By the definition of $\mathcal T_w$, the restriction
\[
\phi: \mathcal B_{w^{-1}}\rightarrow \mathcal T_w
\]
is also a bijection.

Let
\[
\psi:\mathcal P(w^{-1})\rightarrow \mathcal B_w
\]
be the map in \ref{3.6.i}. Then the composition
\[
D(w)\xrightarrow{\phi} D(w^{-1})\xrightarrow{\psi} \mathcal B_{w^{-1}} \xrightarrow{\phi}\mathcal T_w
\]
is a bijection. Computing directly,
\begin{align*}
\phi(\psi(\phi(i,j)))&=\phi(\psi(j,i))\\
&=\phi(j,i-r_{w^{-1}}(j,i))\\
&=(i-r_{w^{-1}}(j,i),j).
\end{align*}
Applying~\eqref{eqn:rank},
\begin{align*}
r_{w^{-1}}(j,i)&=\#\{k:k\leq j \enspace \text{and} \enspace w^{-1}(k)\leq i\}\\
&=\#\{\ell:w(\ell)\leq j \enspace \text{and} \enspace w^{-1}(w(\ell))\leq i\}\\
&=\#\{\ell: \ell\leq i \enspace \text{and} \enspace w(\ell)\leq j \}\\
&=r_w(i,j).
\end{align*}
Therefore,
\[
\phi(\psi(\phi(i,j)))=(i-r_w(i,j),j).
\]

\ref{3.6.iii}. By Theorem~\ref{theorem:bb}, there is a path of ladder moves from $\mathcal B_w$ to $\mathcal T_w$. Applying~\eqref{eqn:antidiagcount} and the bijections in parts \ref{3.6.i} and \ref{3.6.ii},
\begin{align*}
\mathbf a_{\mathcal B_w}(k)&=\#\{(i,j)\in D(w):i+(j-r_w(i,j))-1=k\}\\
&=\#\{(i,j)\in D(w):(i-r_w(i,j))+j-1=k\}\\
&=\mathbf a_{\mathcal T_w}(k).
\end{align*}
By Lemma~\ref{lemma:simpleladder}, the path uses only simple ladder moves.
\end{proof}

In light of the previous lemma, we may label the pluses of $\mathcal B_w$ using the map $(i,j)\mapsto (i,j-r_w(i,j))$, \ie we refer to the plus which is the image of $(i,j)$ as $+_{(i,j)}$. Likewise we label $\mathcal T_w$ using the map $(i,j)\mapsto (i-r_w(i,j),j)$.

\begin{lemm}\label{lemma:inherit}
The above labeling of $\mathcal T_w$ is the same as the labeling it inherits from $\mathcal B_w$.
\end{lemm}

\begin{proof}
It is enough to show that within any given antidiagonal the labels in $\mathcal B_w$ and $\mathcal T_w$ are the same and have the same relative order. If $(i,j)\in D(w)$, then $+_{(i,j)}$ is in position $(i,j-r_w(i,j))$ in $\mathcal B_w$ and in position $(i-r_w(i,j),j)$ in $\mathcal T_w$. Since
\[
i+j-r_w(i,j)=i-r_w(i,j)+j,
\]
they are in the same antidiagonal.

Now consider the $r$th antidiagonal in $\mathcal B_w$. Suppose the sorted list of pluses from top to bottom is
\[
+_{(i_1,j_1)}, +_{(i_2,j_2)}, \cdots, +_{(i_k,j_k)}.
\]
Since the map from $D(w)$ is by left justification, we must have $i_1<i_2<\cdots<i_k$. As $i_\ell+j_\ell-1=r$ for all $\ell$, it follows that $j_1>j_2>\cdots>j_k$. Since the map from $D(w)$ to $\mathcal T_w$ is by top justification, the sorted list of pluses from top to bottom must also be
\[
+_{(i_1,j_1)}, +_{(i_2,j_2)}, \cdots, +_{(i_k,j_k)}.
\]
Therefore, the labeling which $\mathcal T_w$ inherits from $\mathcal B_w$ coincides with the labeling determined by the map $(i,j)\mapsto (i-r_w(i,j),j)$.
\end{proof}

We conclude with the proof of the $132$-bound.

\begin{proof}[Proof of Theorem~\ref{theorem:bound}]
By Lemma~\ref{lemma:biject}, there is a path of simple ladder moves connecting $\mathcal B_w$ to $\mathcal T_w$, say
\begin{equation}\label{eqn:pipesequence}
\mathcal B_w=\mathcal P_0\mapsto\mathcal P_1\mapsto \cdots \mapsto \mathcal P_N=\mathcal T_w.
\end{equation}
Let $n_{i,j}=\#\{k: \text{$\mathcal P_k \mapsto \mathcal P_{k+1}$ moves $+_{(i,j)}$}\}$. By definition, $\mathcal P_k \mapsto \mathcal P_{k+1}$ moves exactly one plus, labeled by an element of $D(w)$. Therefore,
\begin{equation}\label{eqn:n}
N=\sum_{(i,j)\in D(w)}n_{i,j}.
\end{equation}

\begin{enonce}{Claim}\label{claim:plusrank}
If $(i,j)\in D(w)$ then $n_{i,j}=r_w(i,j)$.
\end{enonce}

\begin{proof}
By Lemma~\ref{lemma:inherit}, $+_{(i,j)}$ must move from position $(i,j-r_w(i,j))$ in $\mathcal B_w$ to position $(i-r_w(i,j),j)$ in $\mathcal T_w$. At each step $+_{(i,j)}$ remains stationary or it moves up a row and one column to the right. As such, $+_{(i,j)}$ must move exactly $i-(i-r_w(i,j))=r_w(i,j)$ times to go from row $i$ to row $i-r_w(i,j)$.
\end{proof}

Then
\begin{align*}
\eta_w&=\sum_{(i,j)\in D(w)} r_w(i,j) &&\text{(by Lemma~\ref{lemma:eta})}\\
&=\sum_{(i,j)\in D(w)} n_{i,j} &&\text{(by Claim~\ref{claim:plusrank})}\\
&=N &&\text{(by~\eqref{eqn:n})}.
\end{align*}
Each $\mathcal P_i$ in the sequence~\eqref{eqn:pipesequence} is distinct. As such, $\#{\tt RP}(w)\geq N+1$. Therefore
\[
\nu_w=\#{\tt RP}(w)\geq N+1=\eta_w+1. \qedhere
\]
\end{proof}

\begin{exam}
Let $w=25143$. Below, we give a sequence of simple ladder moves connecting $\mathcal B_w$ to $\mathcal T_w$. The last row and column of each pipe dream has been omitted.
\begin{multline*}
\left[
\begin{array}{cccc}
+_{(1,1)} & \cdot & \cdot & \cdot\\
+_{(2,1)} & +_{(2,3)} & +_{(2,4)} & \cdot\\
\cdot & \cdot & \cdot & \cdot\\
+_{(4,3)} & \cdot & \cdot & \cdot\\
\end{array}\right]
\mapsto
\left[
\begin{array}{cccc}
+_{(1,1)} & \cdot & \cdot & +_{(2,4)}\\
+_{(2,1)} & +_{(2,3)} & \cdot & \cdot\\
\cdot & \cdot & \cdot & \cdot\\
+_{(4,3)} & \cdot & \cdot & \cdot\\
\end{array}\right]
\mapsto
\left[
\begin{array}{cccc}
+_{(1,1)} & \cdot & \cdot & +_{(2,4)}\\
+_{(2,1)} & +_{(2,3)} & \cdot & \cdot\\
\cdot & +_{(4,3)} & \cdot & \cdot\\
\cdot & \cdot & \cdot & \cdot\\
\end{array}\right]
\\
\mapsto
\left[
\begin{array}{cccc}
+_{(1,1)} & \cdot & +_{(2,3)} & +_{(2,4)}\\
+_{(2,1)} & \cdot & \cdot & \cdot\\
\cdot & +_{(4,3)} & \cdot & \cdot\\
\cdot & \cdot & \cdot & \cdot\\
\end{array}\right]
\mapsto
\left[
\begin{array}{cccc}
+_{(1,1)} & \cdot & +_{(2,3)} & +_{(2,4)}\\
+_{(2,1)} & \cdot & +_{(4,3)} & \cdot\\
\cdot & \cdot & \cdot & \cdot\\
\cdot & \cdot & \cdot & \cdot\\
\end{array}\right]
\end{multline*}
Notice for each $(i,j)\in D(w)$, the plus $+_{(i,j)}$ moves $r_w(i,j)$ times. For instance, $r_w(4,3)=2$ and $+_{(4,3)}$ moves twice. This follows from Claim~\ref{claim:plusrank}. The above sequence from $\mathcal B_w$ to $\mathcal T_w$ uses $\eta_w+1=5$ pipe dreams in total. This agrees with the $132$-bound, $\nu_w\geq\eta_w+1$.
\end{exam}



\longthanks{The author would like to thank Alexander Yong for helpful conversations and feedback. The author also thanks the anonymous referees for their comments and suggestions which improved the exposition of this work. }


\nocite{*}


\bibliographystyle{amsplain-ac}
\bibliography{ALCO_Weigandt_4}
\end{document}
