We present a direct bijection between reduced pipe dreams and reduced bumpless pipe dreams by interpreting reduced compatible sequences on bumpless pipe dreams and show that this bijection preserves Monk's formula, establishing its canonical nature.

§ INTRODUCTION

Schubert polynomials, $\{\S_\pi\:|\: \pi\in S_n\}$, defined by Lascoux and Schützenberger [9], are polynomial representatives of the Schubert classes of the full flag variety $\mathrm{Fl}_n$. They can be defined via the divided difference operators as follows:

\[\S_\pi:=
\begin{cases}
x_1^{n-1}x_2^{n-2}\cdots x_{n-1} & \text{ if }w=n\ n{-}1\ \cdots\ 1,\\
\partial_i \S_{\pi s_i} & \text{ if } \ell(\pi)<\ell(\pi s_i),
\end{cases}
\]

where $s_i$ is the simple transposition $(i\ i{+}1)$, which acts on polynomials by swapping the variables $x_i$ and $x_{i+1}$, and

\[\partial_i f:=\frac{f-s_if}{x_i-x_{i+1}}.\]

Schubert polynomials and their various generalizations are the central objects of interest in Schubert calculus and algebraic combinatorics, and possess very rich combinatorial structures. The Schubert polynomials $\S_\pi$'s expand positively into monomials. Notable combinatorial models for this result involve compatible sequences by Billey-Jockusch-Stanley [3], which are equivalent to pipe dreams (PDs), also called RC-graphs, by Bergeron-Billey [1].

Let $\pi$ be a permutation, then $\S_\pi=\sum_{D\in\PD(\pi)}\wt(D).$

We will introduce the necessary notations in Section <ref>.

Relatively recently, Lam, Lee and Shimozono [8] introduced bumpless pipe dreams (BPDs), in the context of back stable Schubert calculus, that provide another monomial expansion of the Schubert polynomials.

Let $\pi$ be a permutation, then $\S_\pi=\sum_{D\in\BPD(\pi)}\wt(D).$

Theorem <ref> and Theorem <ref> guarantee that there exists a weight-preserving bijection between pipe dreams and bumpless pipe dreams of a fixed permutation. The following question has been of interest since the discovery of bumpless pipe dreams.

Can we explicitly describe a “natural" weight-preserving bijection between $\PD(\pi)$ and $\BPD(\pi)$ for any permutation $\pi$?

The goal of this paper is to answer the above question affirmatively, by providing such a bijection $\varphi$ (Definition <ref>). We then show that our bijection is the “correct" bijection in a precise sense by proving that $\varphi$ preserves Monk's rule (Theorem <ref>).

One notable consequence of Theorem <ref> is that it unifies all attempts to define bijections between pipe dreams and bumpless pipe dreams via any choices of Monk's rules. Specifically, the second author mentioned a family of bijections [5] between pipe dreams and bumpless pipe dreams defined using (co)transition formulas which are special cases of Monk's rule. Each bijection in this family depends on a choice $\alpha$ for each permutation $\pi$ upon which the (co)transition is performed. By Theorem <ref>, we now know that this family of bijections is in fact one single bijection (Definition <ref>).

For the organization of this paper, we first introduce background knowledge in Section <ref>. Then we describe the bijection in Section <ref>. Finally, we show that the bijection preserves Monk's rule in Section <ref>, which is divided into many subsections due to the technicality the proof of our main theorem, Theorem <ref>.

§ PRELIMINARIES

Let $S_{\infty}$ be the infinite symmetric group that consists of bijections from $\Z_{>0}$ to itself with all but finitely many fixed points. Namely, $S_\infty=\bigcup_{n\ge 1} S_n$. The group $S_{\infty}$ is generated by the simple transpositions $s_i:=(i\ i{+}1)$, for $i\in\Z_{>0}$. For $a<b$, let $t_{a,b}$ be the transposition $(a\ b)$. Let $\ell(w)$ be the standard Coxeter length of $w$ and let $\Red(w)$ be the set of reduced words of $w$.

The Bruhat order on $S_{\infty}$ is the transitive closure of the binary relation $w<wt_{a,b}$ if $\ell(w)<\ell(wt_{a,b})$. The cover relation in the Bruhat order is given by $x\lessdot y$ if $x=yt_{a,b}$ for some $a<b$ and $\ell(x)=\ell(y)-1$. Also, let $\DES_L(\pi):=\{i\in \Z_{>0}\:|\: s_i \pi\lessdot \pi\}$ be the set of (left) descents of $\pi$.

The stability property of the Schubert polynomials allows us to work with permutations $\pi\in S_{\infty}$, instead of each symmetric group $S_n$ separately. Recall that the stability property states that for any $m<n$, $\pi\in S_m$, we have $\S_\pi=\S_{\iota(\pi)}$, where $\iota:S_m\hookrightarrow S_n$ is the natural embedding.

§.§ Pipe dreams and compatible sequences

[Pipe dream, RC-graph [1]]
For a permutation $\pi\in S_{\infty}$, a (reduced) pipe dream $D$ of $\pi$ is a tiling of the square grid $\Z_{>0}\times\Z_{>0}$ using two kinds of tiles, the cross-tile  and the elbow-tile , with finitely many -tiles, forming pipes that travel from the north border to the west border, such that for $i\in\Z_{>0}$, the pipe starting at column $i$, which is labeled as pipe $i$, ends at row $\pi(i)$, and  no two pipes cross twice.

We typically draw a pipe dream in a staircase shape of size $n$ if $\pi\in S_n$. Let $\PD(\pi)$ be the set of pipe dreams of $\pi$, and for $D\in\PD(\pi)$, let $\cross(D)$ denote the coordinates of its -tiles. Then the weight of $D$ is defined as
\[\wt(D):=\prod_{(i,j)\in\cross(D)}x_i.\]

Given a pipe dream $D$, we let $\perm(D)$ denote the permutation given by $D$.
[Compatible sequence [3]]
For a permutation $\pi\in S_\infty$ with $\ell(\pi)=\ell$, a tuple of integer sequences $\big(\mathbf{a}=(a_1,\ldots,a_{\ell}),\mathbf{r}=(r_1,\ldots,r_{\ell})\big)$ is a (reduced) compatible sequence of $\pi$ if

* $\mathbf{a}=(a_1,\ldots,a_{\ell})$ is a reduced word of $\pi$,

* $r_1\leq\cdots \leq r_{\ell}$ is weakly increasing,

* $r_j\leq a_j$ for $j=1,\ldots,\ell$,

* $r_j<r_{j+1}$ if $a_j<a_{j+1}$.

There is a straightforward bijection between pipe dreams of $\pi$ and compatible sequences of $\pi$, which we describe here.

We label the square grids with matrix notation and give a total order to the square grids, by going from top to bottom, and within each row, right to left. To be precise, $(i,j)<(i',j')$ if $i<i'$ or $i=i',j>j'$. For $D\in\PD(\pi)$ with $\ell(\pi)=\ell$, order its -tiles $\cross(D)$ in this way as $(r_1,j_1)<\cdots<(r_{\ell},j_{\ell})$. Then its corresponding compatible sequence is $\big(\mathbf{a}=(a_1,\ldots,a_{\ell}),\mathbf{r}=(r_1,\ldots,r_{\ell})\big)$ where $a_k=r_k+j_k-1$. Note that each -tile at coordinate $(i,j)$ corresponds to the simple transposition $s_{i+j-1}$. See [1] for further details on this bijection.

Figure <ref> shows two pipe dreams of $\pi=21543$ of weight $x_1^2x_2x_3$ and their corresponding compatible sequences.

Examples of pipe dreams and their corresponding compatible sequences

As the bijection between pipe dreams and compatible sequences is quite straightforward, we will abuse notation and from now on, consider them to be the same combinatorial objects for simplicity.

For a pipe dream $D\in\PD(\pi)$ with compatible sequence $(\mathbf{a},\mathbf{r})$, its first -tile corresponding to the order on the square grid will play an important role later on, which has coordinate $(r_1,a_1-r_1+1)$. We denote by $\nabla D$ the pipe dream obtained from $D$ by turning this first -tile into a -tile, and write $\pop(D)=(a_1,r_1)$. We have that $\nabla D\in\PD(s_{a_1}\pi)$, where $a_1\in\DES_L(\pi)$ so that $\ell(s_{a_1}\pi)=\ell(\pi)-1$.

§.§ Bumpless pipe dreams

[Bumpless pipe dream [8]]
For a permutation $\pi\in S_{\infty}$, a (reduced) bumpless pipe dream $D$ of $\pi$ is a tiling of the square grid $\Z_{>0}\times\Z_{>0}$ using the following six tiles,

with finitely many -tiles, forming pipes labeled by $\Z_{>0}$ such that pipe $i$ travels from $(\infty,i)$ to $(\pi(i),\infty)$ in the NE direction and that no two pipes cross twice. Among the tiles, “” is pronounced “are” and “” is pronounced “jay”. The name “bumpless” comes from the fact that the  tile “” where two pipes “bump” is forbidden.

We typically draw a bumpless pipe dream in a square grid of size $n\times n$ if $\pi\in S_n$. Let $\BPD(\pi)$ denote the set of bumpless pipe dreams of $\pi$, and for $D\in\BPD(\pi)$, let $\cross(D)$ denote the coordinates of its -tiles and $\blank(D)$ denote the coordinates of its -tiles. Then the weight of $D$ is defined as
\[\wt(D):=\prod_{(i,j)\in\blank(D)}x_i.\]

§ DESCRIPTION OF THE BIJECTION

We start with the following operation on bumpless pipe dreams, which is defined in the rectification process described in [6]. These moves are generalizations of the backwards direction of the insertion proceess described in <cit.>. We follow the definition of droop and undroop moves on bumpless pipe dreams as in <cit.>.

Given $D\in\BPD(\pi)$ with $\ell(\pi)>0$, the following process produces another bumpless pipe dream $\nabla D\in\BPD(\pi')$ where $\ell(\pi')=\ell(\pi)-1$. Suppose $D$ is an $n\times n$ grid. Let $r$ be the smallest row index such that the row $r$ of $D$ contains -tiles. To initialize, mark the rightmost -tile in row $r$ with a label “$\times$".

* If the marked -tile is not the rightmost -tile in a contiguous block of -tiles in its row, move the label “$\times$" to the rightmost -tile of this block. Assume the marked tile has coordinate $(x,y)$, and the pipe going through $(x,y+1)$ is $p$.

* If $p\neq y+1$, suppose the -tile of $p$ in column $y+1$ has coordinate $(x',y+1)$ for some $x'>x$. Call the rectangle with NW corner $(x,y)$ and SE corner $(x',y+1)$ the column move rectangle $U$. We modify the tiles in $U$ as follows:

* For each pipe $q$ intersecting $p$ at some $(z,y+1)$ where $x<z<x'$ and $(z,y)$ is an -tile, let $(z',y)$ be the -tile of $q$ in column $y$. Ignoring the presence of $p$, droop $q$ at $(z,y)$ within $U$, so that $(z,y+1)$ becomes an -tile and $(z',y+1)$ becomes a -tile;

* Undroop pipe $p$ at $(x',y+1)$ into $(x,y)$, and move the mark to $(x',y+1)$.

Go back to step (1) and repeat. The column moves are illustrated in Figure <ref>.

Column moves

* If $p=y+1$, the pipes $y$ and $y+1$ must intersect at some $(x',y+1)$ for some $x'>x$. Replace  this -tile with a -tile, undroop the -turn of this tile into $(x,y)$ and adjust the pipes between row $x$ and $x'$ so that their “kinks shift right”, in a same fashion as described in  Step (2) above. In this case, call the rectangle with NW corner $(x,y)$ and SE corner $(n,y+1)$ the column move rectangle. These moves are shown in Figure <ref>.
We are done after this step.

The final step of deleting a marked -tile

Let $a$ be the column index of the left column of the last column move rectangle as in Step (3).
The final BPD is of the permutation $s_a\pi$. Denote the result by $\nabla D\in\BPD(s_a\pi)$, and write $\pop(D)=(a, r)$. Let the footprints of $D$ be the set of coordinates that are SE corners of the column move rectangles except for the southernmost one.

Note that each step above is invertible. Specifically, given $D'$ and a pair $(a,r)$, we can uniquely recover $D$, if it exists, such that $\nabla D=D'$ and $\pop(D)=(a,r)$, by inverting the above steps: start with crossing the pipe $a$ and pipe $a+1$ where the pipe $a+1$ first turn right (if pipe $a$ and $a+1$ already cross in $D'$, then we know that such $D$ does not exist) and creating a -tile in some row $r'$; then keep doing backward-direction column moves and sliding the -tile to the left until the -tile reaches row $r$. If this -tile cannot land exactly on row $r$, we also conclude that such $D$ does not exist.

Figure <ref> demonstrates how Definition <ref> works for a certain bumpless pipe dream $D\in\BPD(\pi)$ step by step, where $\nabla D\in\BPD(s_a\pi)$ is obtained in the end, with $\pi=2153746$, $a=4$, $\pop(D)=(4,1)$.

An example of obtaining $\nabla D$ with the step number labeled on the arrows

Repeatedly applying the procedure in Definition <ref>, we obtain the the following map, which is the main object of study of this paper.
[The bijection]
Given $D\in\BPD(\pi)$ with $\ell(\pi)=\ell$, let
\[\varphi(D)=\big(\mathbf{a}=(a_1,\ldots,a_{\ell}),\mathbf{r}=(r_1,\ldots,r_{\ell})\big),\]
where $\pop(\nabla^{i-1}D)=(a_i,r_i)$ for $i=1,\ldots,\ell$.

Figure <ref> and Figure <ref> demonstrate two examples of the bijection $\varphi$ in Definition <ref> for $\pi=21543$, whose Schubert polynomial $\mathfrak{S}_{\pi}$ is not multiplicity-free in the monomial expansion (see [4]). Both examples  have weight $x_1^2x_2x_3$.

An example for the bijection $\varphi$ with $\pi=21543$, where the values of $\pop$'s are shown on the arrows.

Another example for the bijection $\varphi$ with $\pi=21543$, where the values of $\pop$'s are shown on the arrows.

For $D\in\BPD(\pi)$, $\varphi(D)$ is a compatible sequence of $\pi$.

We check the conditions of compatible sequences for $\varphi(D)$ as in Definition <ref>. Condition (1) follows from $\nabla D\in\BPD(s_a\pi)$ if $\pop(D)=(a,r)$. Condition (2) is evident from construction, as we are removing -tiles from top to bottom. Note that if $\pop(D)=(a,r)$, with $D\in\BPD(\pi)$, there are no -tiles in the first $r-1$ rows of $D$, meaning that $\pi(i)=i$ for $i=1,\ldots,r-1$, and consequently $a\geq r$. Thus, condition (3) follows. For condition (4), we assume the opposite that $r_{j}\geq r_{j+1}$, i.e. $r_j=r_{j+1}$ and $a_j<a_{j+1}$. Since $a_j<a_{j+1}$, by Lemma 3.2 of [6], the footprints of $\nabla^{j-1}D$ are strictly to the S/W/SW direction of the footprints of $\nabla^j D$. However, the starting point of the footprints of $\nabla^{j-1}D$ is directly east of the footprints of $\nabla^{j}D$ as we start in the same row $r_j=r_{j+1}$. Contradiction.

The map $\varphi$ in Definition <ref> is a weight-preserving bijection between $\BPD(\pi)$ and $\PD(\pi)$, i.e. compatible sequences of $\pi$.

By Lemma <ref>, we have a well-defined map $\varphi$ from $\BPD(\pi)$ to $\PD(\pi)$. Immediate from the construction (Definition <ref>), $\varphi$ is weight-preserving. Since each step $\nabla$ is invertible if a preimage exists, the map $\varphi$ is injective. As both pipe dreams and bumpless pipe dreams enumerate the Schubert polynomial $\mathfrak{S}_\pi$, $\varphi$ is a bijection.

§ PRESERVING MONK'S RULE

In this section, we demonstrate why the map $\varphi$ in Definition <ref> is “canonical", by showing that it preserves Monk's rule.

Let $\pi$ be a permutation and $\alpha$ be a positive integer,

\begin{equation}\label{eq:Monk}
x_{\alpha}\S_\pi+\sum_{\substack{s<\alpha\\\pi t_{s,\alpha}\gtrdot\pi}}\S_{\pi t_{s,\alpha}}=\sum_{\substack{l>\alpha\\\pi t_{\alpha,l}\gtrdot\pi}}\S_{\pi t_{\alpha,l}}.
\end{equation}

This version of Monk's rule is derived from the Monk's rule that expands the product of a linear Schubert polynomial with a general Schubert polynomial. In the cases when the summation on the right-hand of Equation (<ref>) is a single Schubert polynomial, the formula specializes to the transition formula of Schubert polynomials, which is an important inductive formula for Schubert polynomials. In the case when the summation on the left-hand side is empty, the formula specializes to the cotransition formula [7]. In [2], a bijective proof of the transition formula is given using pipe dreams, which can be easily extended to a proof of Monk's rule in its general form. The second author gives a bijective proof of Monk's rule with bumpless pipe dreams in [5], which also generalizes to the equivariant version. It is also remarked in [5] that using either the transition or the cotransition formula, one can construct  bijections inductively of pipe dreams and bumpless pipe dreams. As a corollary of our result, these  inductive bijections agree. We review both weight-preserving bijections for Equation (<ref>) on pipe dreams and bumpless pipe dreams in Section <ref> and Section <ref>.

§.§ Monk's rule on pipe dreams

We present the following maps

\[
\begin{cases}
x_\alpha{\rightsquigarrow}:&\PD(\pi)\rightarrow \bigcup_{\substack{l>\alpha\\\pi t_{\alpha,l}\gtrdot\pi}}\PD(\pi t_{\alpha,l})\\
m_{s,\beta}:&\PD(\pi t_{s,\beta})\rightarrow \bigcup_{\substack{l>\beta\\\pi t_{\beta,l}\gtrdot\pi}}\PD(\pi t_{\beta,l}),\ s<\beta,\pi t_{s,\beta}\gtrdot\pi
\end{cases}
\]

such that $x_{\alpha}{\rightsquigarrow}$ and $m_{s,\beta}$'s for $\beta=\alpha$ together form a weight-preserving bijection from the left-hand side to the right-hand side of Equation (<ref>). To be precise on the weight, $x_{\alpha}{\rightsquigarrow}$ multiplies the weight by $x_{\alpha}$ while $m_{s,\beta}$ preserves the weight. Readers are referred to [2]  for further details, and how these maps can be inverted.

[$x_{\alpha}{\rightsquigarrow},m_{s,\beta}$ on  pipe dreams]
Given $D\in\PD(\pi)$, the following procedure produces $x_{\alpha}{\rightsquigarrow} D$.

* Find the leftmost -tile on row $\alpha$ of $D$ and replace it by .

* If the newly added -tile creates a double crossing with another -tile at coordinate $(i,j)$, replace the -tile at $(i,j)$ with , find the smallest $j'>j$ such that $(i,j')$ is a -tile, and replace it by . Repeat this step.

Analogously, given $\pi$, $D\in\PD(\pi t_{s,\beta})$ such that $\pi t_{s,\beta}\gtrdot\pi$, the following procedure produces $m_{s,\beta}(D)\in\PD(\pi t_{\beta,l})$ for some $l>\beta$ where $\pi t_{\beta,l}\gtrdot \pi$.

* Locate the -tile between pipe $\pi^{-1}(s)$ and $\pi^{-1}(\beta)$ in $D$ at coordinate $(i,j)$. Make it into a -tile. Find the smallest $j'>j$ such that $(i,j')$ is a -tile, and replace it by .

* Exactly the same as step (2) above.

See Figure <ref> for an example.

§.§ Monk's rule on bumpless pipe dreams

We present the analogous maps

\[
\begin{cases}
x_\alpha{\rightsquigarrow}:&\BPD(\pi)\rightarrow \bigcup_{\substack{l>\alpha\\\pi t_{\alpha,l}\gtrdot\pi}}\BPD(\pi t_{\alpha,l})\\
m_{s,\beta}:&\BPD(\pi t_{s,\beta})\rightarrow \bigcup_{\substack{l>\beta\\\pi t_{\beta,l}\gtrdot\pi}}\BPD(\pi t_{\beta,l}),\ s<\beta,\pi t_{s,\beta}\gtrdot\pi
\end{cases}
\]

for bumpless pipe dreams. For details including illustrated examples, see [5]. First we recall from [5] that an almost bumpless pipe dream of $\pi$ is defined by relaxing the condition of bumpless pipe dreams by allowing a single -tile in the grid.

[Basic Monk moves on (almost) bumpless pipe dreams]
We define two basic Monk moves, $\mindroop$ and $\cbswap$, on (almost) bumpless pipe dreams. See Figure <ref>.

$\mindroop$: Let $(a,b)$ be the position of an -turn of a pipe $p$. Note that the tile at $(a,b)$ could be a -tile or -tile. Let $x>0$ be the smallest number where $(a+x,b)$ is not a -tile, and $y>0$ be the smallest number where $(a,b+y)$ is not a -tile. A $\mindroop$ at $(a,b)$ droops $p$ into $(a+x,b+y)$.

$\cbswap$: Suppose $(a,b)$ is a $\bt$-tile of pipes $p$ and $q$, and $p$ and $q$ also have a crossing at $(a',b')$. Then a $\cbswap$ move at $(a,b)$ swaps the two tiles at $(a,b)$ and $(a',b')$.

Furthermore, we consider the initial move that replaces a -tile with a -tile when computing $m_{s,\beta}$, and the final move that replaces a -tile with a -tile also as special basic Monk moves.

Basic monk moves at the circled coordinates

By the stability property of Schubert polynomials, we may embed $\pi$ into a larger symmetric group as necessary so that a $\mindroop$ is always possible.

[$x_{\alpha}{\rightsquigarrow},m_{s,\beta}$ on bumpless pipe dreams]
Given $D\in\BPD(\pi)$, the following procedure produces $x_\alpha \rightsquigarrow D$.

* Let $(\alpha, j)$ be the easternmost -tile in row $\alpha$, initialize $(\mathsf{x},\mathsf{y}):=(\alpha,j)$.

* Perform a $\mindroop$ at $(\mathsf{x},\mathsf{y})$. Let $(z,w)$ be the SE corner of this $\mindroop$.

* If after the $\mindroop$, $(z,w)$ is a -tile, update $(\mathsf{x},\mathsf{y})$ as the position of -tile of pipe $\pi(\alpha)$ in row $z$, and repeat this step.

* If after this $\mindroop$, $(z,w)$ is a -tile, let $q$ be the pipe of the -turn in this tile.

* If $\pi(\alpha)$ and $q$ have already intersected at $(z',w')$, perform a $\cbswap$ move at $(z,w)$. Update $(\mathsf{x},\mathsf{y}):=(z',w')$, and repeat Step (2).

* If $\pi(\alpha)$ and $q$ have not intersected before, replace the -tile with a -tile and stop.

To define $m_{s,\beta}(D)$, replace Step (1) with

(1') Initialize $(\mathsf{x},\mathsf{y})$ to be the position of the -tile of $\pi(s)$ and $\pi(\beta)$. Replace this tile with a -tile.

§.§ The main theorem and the proof

The following is the main theorem of the paper.

For any $\pi\in S_{\infty}$, the bijection $\varphi:\BPD(\pi)\rightarrow\PD(\pi)$ preserves Monk's rule, i.e. $\varphi$ intertwines with $x_{\alpha}{\rightsquigarrow}$, $m_{s,\beta}$'s. Specifically, the following diagrams commute:

(π)[r,"x_α⇝"][d,"φ"]     ⋃_l>α

(π)[r,"x_α⇝"]     ⋃_l>α

(πt_s,β)[r,"m_s,β"][d,"φ"]     ⋃_l>β

(πt_s,β)[r,"m_s,β"]     ⋃_l>β

where $\alpha\in\Z_{>0}$ is arbitrary, and $\pi t_{s,\beta}\gtrdot \pi$ with $s<\beta$.

Despite how simple Theorem <ref> is stated, the proof turns out to rely on  technical lemmas on pipe dreams (Lemma <ref>) and bumpless pipe dreams (Lemma <ref>), which  discuss how much the operator $\nabla$ commutes with $x_{\alpha}{\rightsquigarrow}$'s and $ m_{s,\beta}$'s respectively on pipe dreams and bumpless pipe dreams. We finish the main proof here assuming that both lemmas are already taken care of.

This theorem is a direct consequence of the induction principle and the fact that $\nabla$ and $x_{\alpha}{\rightsquigarrow}, m_{s,\beta}$ interact in the exact same way on pipe dreams (Lemma <ref>) and bumpless pipe dreams (Lemma <ref>).

To be precise, we proceed by induction on $\ell(\pi)$. The base case is $\ell(\pi)=0$, i.e. $\pi=\mathrm{id}$. Take $B\in\BPD(\pi)$, which has no crossings. Its corresponding pipe dream $D:=\varphi(B)$ also has no crossings. By the definition of $x_{\alpha}{\rightsquigarrow}$, $x_{\alpha}{\rightsquigarrow} B$ has a crossing between pipe $\alpha$ and $\alpha+1$ at coordinate $(\alpha+1,\alpha+1)$ and the insertion creates a -tile on row $\alpha$, while $x_{\alpha}{\rightsquigarrow} D$ has a single crossing at coordinate $(\alpha,1)$. By Definition <ref>, $\pop(x_\alpha{\rightsquigarrow} B)=(\alpha,\alpha)$ which gives us $\varphi(x_\alpha{\rightsquigarrow} B)=x_{\alpha}{\rightsquigarrow} D$. For the second commutative diagram, in order for $\pi t_{s,\beta}\gtrdot\pi$, we must have $s=\beta-1$. Any $B\in\BPD(\pi t_{s,\beta})$ must have a crossing between pipe $\beta-1$ and $\beta$ at coordinate $(\beta,\beta)$ and a -tile at coordinate $(k,k)$ for some $k<\beta$. The operation $m_{s,\beta}$ uncrosses the -tile between pipe $\beta-1$ and $\beta$ and inserts a -tile between pipe $\beta$ and $\beta+1$ at coordinate $(\beta+1,\beta+1)$, keeping the position of the -tile. Thus, we see that $\pop(B)=(\beta-1,k)$ and $\pop(m_{s,\beta}(B))=(\beta,k)$, meaning that $\varphi(B)$ has a single -tile at coordinate $(k,\beta-k)$ and $\varphi(m_{s,\beta}(B))$ has a single -tile at coordinate $(k,\beta-k+1)$ so evidently $m_{s,\beta}(\varphi(B))=\varphi(m_{s,\beta}(B))$ as desired. See Figure <ref>.

The base case for the second commutative diagram of Theorem <ref>

Now assume that we have established the commutative property of the above diagrams for permutations $\pi'$ with $\ell(\pi')<\ell$. Now fix $\pi$ with $\ell(\pi)=\ell$ so that $\ell(\pi t_{s,\beta})=\ell+1$. We argue about the second commutative diagram first. Take $B\in\BPD(\pi t_{s,\beta})$ and let $D=\varphi(B)\in\PD(\pi t_{s,\beta})$. Since $D$ and $B$ are bijection, let $\pop(B)=\pop(D)=(i,r)$. Our goal is to show that the bumpless pipe dream $m_{s,\beta}(B)$ and the pipe dream $m_{s,\beta}(D)$ are in bijection via $\varphi$. By Definition <ref> of $\varphi$, it suffices to show that $\pop (m_{s,\beta}(B))=\pop(m_{s,\beta}(D))$ and that $\nabla(m_{s,\beta}(B))$ and $\nabla(m_{s,\beta}(D))$ are in bijection via $\varphi$.

Case (1)(a) of Lemma <ref> and Lemma <ref>: $(s,\beta)\neq(\pi^{-1}(i+1),\pi^{-1}(i))$. By induction hypothesis where $\ell(\perm(\nabla D))=\ell(\perm(\nabla B))=\ell(\pi t_{s,\beta})-1=\ell$, as $\nabla B$ and $\nabla D$ are in bijection, $m_{s,\beta}(\nabla B)$ and $m_{s,\beta}(\nabla D)$ must be in bijection. Therefore, we can let $\rho:=\perm(m_{s,\beta}(\nabla B))=\perm(m_{s,\beta}(\nabla D))$. We further divide into subcases based on whether $i\in\DES_L(\rho)$ and $i+1\in\DES_L(\rho)$, as indicated by Lemma <ref> and Lemma <ref>.

If $i\notin\DES_L(\rho)$, by Lemma <ref> and Lemma <ref>, $\pop(m_{s,\beta}(D))=(i,r)=\pop(m_{s,\beta}(B))$. Furthermore, as $m_{s,\beta}(\nabla D)$ and $m_{s,\beta}(\nabla B)$ are in bijection via $\varphi$, $\nabla(m_{s,\beta}(D))=m_{s,\beta}(\nabla D)$ and $\nabla(m_{s,\beta}(B))=m_{s,\beta}(\nabla B)$ are in bijection.

If $i\in\DES_L(\rho)$ and $i+1\notin$, $\pop(m_{s,\beta}(D))=(i+1,r)=\pop(m_{s,\beta}(B))$ by Lemma <ref> and Lemma <ref>. Then as above, $\nabla(m_{s,\beta}(D))=m_{s,\beta}(\nabla D)$ and $\nabla(m_{s,\beta}(B))=m_{s,\beta}(\nabla B)$ are in bijection.

If $i,i+1\in\DES_L(\rho)$, $\pop(m_{s,\beta}(D))=(i+1,r)=\pop(m_{s,\beta}(B))$. As $m_{s,\beta}(\nabla D)$ and $m_{s,\beta}(\nabla B)$ are in bijection with $\ell(\rho)<\ell(\pi t_{s,\beta})$, induction hypothesis gives us that $m_{\rho^{-1}(i+2),\rho^{-1}(i+1)}(m_{s,\beta}(\nabla D))$ and $m_{\rho^{-1}(i+2),\rho^{-1}(i+1)}(m_{s,\beta}(\nabla B))$ are in bijection via $\varphi$. So $\nabla(m_{s,\beta}(D))$ and $\nabla(m_{s,\beta}(B))$ are in bijection as desired.

Case (1)(b) of Lemma <ref> and Lemma <ref>: $(s,\beta)=(\pi^{-1}(i+1),\pi^{-1}(i))$. The same argument as in Case (1)(a) works here, by going through the different scenarios of whether $i,i+1\in\DES_L(\rho)$ and reading off that $\pop(m_{s,\beta}(B))=\pop(m_{s,\beta}(D))$ and that $\nabla(m_{s,\beta}(B))$ and $\nabla(m_{s,\beta}(D))$ are in bijection via induction hypothesis.

The first commutative diagram, i.e. Case (2) of Lemma <ref> and Lemma <ref>, follows basically from the same argument.

Case (2)(a) of Lemma <ref> and Lemma <ref>: $\alpha\geq r$. As $\nabla D$ and $\nabla B$ are in bijection, by induction hypothesis, the PD $x_{\alpha}{\rightsquigarrow}(\nabla D)$ and the BPD $x_{\alpha}{\rightsquigarrow}(\nabla B)$ are in bijection via $\varphi$. So we can let $\rho=\perm(x_{\alpha}{\rightsquigarrow}(\nabla D))=\perm(x_{\alpha}{\rightsquigarrow}(\nabla B))$. As above, we see that $\pop(x_{\alpha}{\rightsquigarrow}D)=(i,r)=\pop(x_{\alpha}{\rightsquigarrow}B)$ if $i\notin\DES_L(\rho)$ and $\pop(x_{\alpha}{\rightsquigarrow}D)=(i+1,r)=\pop(x_{\alpha}{\rightsquigarrow}B)$ if $i\in\DES_L(\rho)$, so $\pop(x_{\alpha}{\rightsquigarrow}D)=\pop(x_{\alpha}{\rightsquigarrow}B)$.

Moreover, if $i,i+1\in\DES_L(\rho)$, as $x_{\alpha}{\rightsquigarrow}(\nabla D)$ and $x_{\alpha}{\rightsquigarrow}(\nabla B)$ are in bijection with $\ell(\rho)\leq\ell$, by  Case (1), $m_{\rho^{-1}(i+2),\rho^{-1}(i+1)}(x_{\alpha}{\rightsquigarrow}(\nabla D))=\nabla(x_{\alpha}{\rightsquigarrow}D)$ and $m_{\rho^{-1}(i+2),\rho^{-1}(i+1)}(x_{\alpha}{\rightsquigarrow}(\nabla B))=\nabla(x_{\alpha}{\rightsquigarrow}B)$ must be in bijection. If not both of $i,i+1$ belong in $\DES_L(\rho)$, we also have that $\nabla(x_{\alpha}{\rightsquigarrow}D)=x_{\alpha}{\rightsquigarrow}(\nabla D)$ is in bijection with $\nabla(x_{\alpha}{\rightsquigarrow}B)=x_{\alpha}{\rightsquigarrow}(\nabla B)$ by induction hypothesis.

Case (2)(b) is done in the same way.

§.§ Induction on pipe dreams

Referring back to Definition <ref>, we introduce more notations for $x_{\alpha}{\rightsquigarrow}$ and $m_{s,\beta}$'s on pipe dreams. Fix a permutation $\pi$ as in Section <ref>. These maps consist of basic Monk steps of deleting -tiles (i.e. turning a -tile into a -tile), which we denote as $k^-$, and steps of adding -tiles (i.e. turning a -tile into a -tile), which we denote as $k^+$, $k=1,2,\ldots$. Write $(i_{k^-},j_{k^-})$ for the coordinate where step $k^-$ happens, and $(i_{k^+},j_{k^+})$ for the coordinate where step $k^+$ happens. To be precise, the map $x_{\alpha}{\rightsquigarrow}$ consists of steps $1^+,2^-,2^+,3^-,\ldots,q^+$ for some $q\geq1$ and the map $m_{s,\beta}$ consists of steps $1^-,1^+,2^-,2^+,\ldots,p^-,p^+$ for some $p\geq1$. We say that the sequence of coordinates $(i_{1^+},j_{1^+}),(i_{2^-},j_{2^-}),\ldots,(i_{q^+},j_{q^+})$ is the Monk footprints for $x_{\alpha}{\rightsquigarrow}$ and the sequence $(i_{1^-},j_{1^-}),(i_{1^+},j_{1^+}),\ldots,(i_{p^+},j_{p^+})$ is the Monk footprints for $m_{s,\beta}$.

Note that after a step $k^-$, we have a genuinely reduced pipe dream for $\pi$, and after each step $k^+$ except the last one, we have a double crossing at coordinate $(i_{k^+},j_{k^+})$ and $(i_{k+1^{-}},j_{k+1^{-}})$. Also, by definition, $i_k^{-}=i_k^{+}$ for all $k$. Let $i_k:=i_k^{-}=i_k^{+}$.
Also define, for $m_{s,\beta}$, the complete Monk footprints to be

\[\bigcup_{k=1}^p\{(i_k,j_{k^-}),(i_k,j_{k^-}+1),\ldots,(i_k,j_{k^+})\},\]

and for $x_{\alpha}{\rightsquigarrow}$, the complete Monk footprints to be

\[\{(i_1,j_{1^+})\}\bigcup_{k=2}^q\{(i_k,j_{k^-}),(i_k,j_{k^-}+1),\ldots,(i_k,j_{k^+})\}.\]

In other words, the complete Monk footprints are the Monk footprints union all the coordinates strictly between $(i_k,j_{k^-})$ and $(i_k,j_{k^+})$, whose tiles are all 's throughout the process of Definition <ref>, as we show momentarily.

Figure <ref> shows an example of a step by step computation of the Monk's rule on a pipe dream $D\in\PD(\pi t_{s,\beta})$ where $\pi=21786534$, $(s,\beta)=(2,5)$.

An example for basic Monk steps for $m_{s,\beta}$ on some $D\in\PD(\pi t_{s,\beta})$ where $\pi=21786534$, $(s,\beta)=(2,5)$. The tiles that are going to be modified immediately are circled, and the complete Monk footprints are shaded. Notice that area above pipe $6$ is growing towards the SE direction.

The complete Monk footprints consist of distinct coordinates.

We first consider $m_{s,\beta}$ applied to $D\in\PD(\pi t_{s,\beta})$. Keep the notations above for Monk footprints $(i_{1^-},j_{1^-}),(i_{1^+},j_{1^+}),\ldots,(i_{p^+},j_{p^+})$. Let $b=\pi(\beta)$, which is the larger pipe number among the two pipes that intersect at $(i_{1^-},j_{1^-})$ in $D$.

For $k=1,\ldots,p$, let $D^{k}\in\PD(\pi)$ be the pipe dream obtained from $D$ after the basic Monk step $k^-$. The readers are strongly recommended to refer to Figure <ref> for a visualization, where $b=\pi^{-1}(5)=6$.

We use induction on $k$ to show that the grid $(i_{k^+}, j_{k^+})$ in $D^k$, which is a -tile by definition, contains the pipe $b$ as its   part.

For the base case $k=1$, starting with $D$, we replace the -tile at $(i_{1^-},j_{1^-})$ with a -tile, so the  part of this tile is pipe $b$. By Definition <ref>, we search towards the right in $D^1$ for the first -tile at $(i_{1^+}, j_{1^+})$, which must contain pipe $b$ as its  part.

Assume that we have proved this claim for $k-1$, $k\leq p$. To do the step $(k-1)^+$, we insert a -tile in $D^{k-1}$ at coordinate $(i_{k-1^+},j_{k-1^+})$, which is a -tile in $D^{k-1}$ that contains pipe $b$ as its  part by induction hypothesis. As this creates a double crossing with the -tile in $D^{k-1}$ at $(i_{k^-},j_{k^-})$, there must be two pipes $b$ and $c$ that pass through the tiles $(i_{k-1^+},j_{k-1^+})$ and $(i_{k^-},j_{k^-})$ in $D^{k-1}$; and moreover, pipe $b$ must be on the NW side of pipe $c$ within this region, since it starts as the  part of $(i_{k-1^+},j_{k-1^+})$. Denote these two paths between $(i_{k-1^+},j_{k-1^+})$ and $(i_{k^-},j_{k^-})$ as $pb$ and $pc$, for pipe $b$ and pipe $c$ respectively. After we insert a -tile at $(i_{k-1^+},j_{k-1^+})$ and delete the -tile at $(i_{k^-},j_{k^-})$ to obtain $D^k$, pipe $b$ now travels between these two tiles via path $pc$, and contains the  part of $(i_{k^-},j_{k^-})$. Therefore, searching from this tile towards the right for the first -tile at $(i_{k^+},j_{k^+})$, we see that it's  part belongs to pipe $b$. The induction step is now complete.

The claim and the above analysis immediately implies that the area bounded by the pipe $b$ and the $x,y$-axis in $D^k$ strictly increases as $k$ increases. This monotonicity is enough for us to conclude the lemma statement, as the added tiles in the complete Monk footprints after each step lie between the pipe $b$ in $D^{k-1}$ and the pipe $b$ in $D^k$, so they will never overlap.

The proof for $x_{\alpha}{\rightsquigarrow}$ is exactly the same so we will not repeat the details here.

We note that Lemma <ref> gives us that $\pop(m_{s,\beta}(D))$, $\pop(x_{\alpha}{\rightsquigarrow} D)$ is either $(i,r)$ or $(i+1,r)$, if $\pop(D)=(i,r)$.

Let $\pi\in S_\infty$. The following statements are true.

* Suppose $D\in\PD(\pi t_{s,\beta})$, where $s<\beta$ and $\pi t_{s,\beta}\gtrdot \pi$. Let $\pop(D)=(i,r)$.

* If $(s,\beta)\neq (\pi^{-1}(i+1), \pi^{-1}(i))$, let  $\rho:=\perm(m_{s,\beta} (\nabla D))$. Then

\[\pop(m_{s,\beta}(D))=
\begin{cases}(i+1,r) & \text{ if } i\in \DES_L(\rho)\\(i,r) & \text {otherwise}
\end{cases}. \]

\[\nabla(m_{s,\beta}(D))=
\begin{cases}m_{\rho^{-1}(i+2),\rho^{-1}(i+1)}(m_{s,\beta}(\nabla D)) & \text{ if } i,i+1\in \DES_L(\rho)\\
m_{s,\beta}(\nabla D) & \text {otherwise}
\end{cases}. \]

* If $(s,\beta)= (\pi^{-1}(i+1), \pi^{-1}(i))$, then $\pop(m_{s,\beta}(D))=(i+1,r)$. Furthermore, let $\rho:=\perm(\nabla(D))$. Then,

\[\nabla(m_{s,\beta}(D))=
\begin{cases}m_{\rho^{-1}(i+2),\rho^{-1}(i+1)}(\nabla D) & \text{ if } i+1\in \DES_L(\rho)\\
\nabla D & \text {otherwise}
\end{cases}. \]

* Suppose $D\in\PD(\pi)$ and $\pop(D)=(i,r)$.

* If $\alpha\ge r$, let $\rho:=\perm(x_\alpha{\rightsquigarrow} (\nabla D))$. Then
\[\pop(x_\alpha{\rightsquigarrow} D)=
\begin{cases}(i+1,r) & \text{ if } i\in \DES_L(\rho)\\(i,r) & \text {otherwise}
\end{cases}. \]

\[\nabla(x_\alpha{\rightsquigarrow} D)=
\begin{cases}
m_{\rho^{-1}(i+2),\rho^{-1}(i+1)}(x_\alpha{\rightsquigarrow}(\nabla D)) & \text{ if } i,i+1\in \DES_L(\rho)\\
x_\alpha{\rightsquigarrow}(\nabla D) & \text {otherwise}
\end{cases}. \]

* If $\alpha < r$, then $\pop(x_\alpha \rightsquigarrow D)=(\alpha, \alpha)$, and $\nabla(x_\alpha{\rightsquigarrow} D)=D$.

Figure <ref> demonstrates an example of a critical case of this Lemma, showing how the operators $\nabla$ and $m_{s,\beta}$'s on the pipe dreams interact.

We will focus more on Case (1)(a), since Case (1)(b) is essentially a degenerate Case of (1)(a), and Case (2) uses the same argument as Case (1).

Case (1)(a): $D\in\PD(\pi t_{s,\beta})$, $s<\beta$, $\pi t_{s,\beta}\gtrdot\pi$, $\pop(D)=(i,r)$ and $(s,\beta)\neq(\pi^{-1}(i+1),\pi^{-1}(i))$. Recall that $\pop(D)=(i,r)$ means that the first -tile of $D$ is located at $(r,i-r+1)$, i.e. the $r$th row is the top row of $D$ with a -tile, and that the -tile in the $r$th row furthest to the right has coordinate $(r,i-r+1)$, which is the intersection of pipe $i$ and $i+1$. The pipe dream $\nabla D$ is obtained from $D$ by deleting this -tile.

Assume that $m_{s,\beta}D$ consists of basic Monk steps $1^-,1^+,\ldots,p^-,p^+$, at Monk footprints $F=\{(i_{1^-},j_{1^-}),\ldots,(i_{p^+},j_{p^+})\}$. Let the complete Monk footprints be
\[C=\bigcup_{k=1}^p C_k,\quad\text{where }C_k:= \{(i_{k},j_{k^-}),(i_k,j_{k^-}+1),\ldots,(i_k,j_{k^+})\}.\]

We further divide into subcases. In all the subcases, let $\rho:=\perm(m_{s,\beta}(\nabla D))$.

Subcase (1)(a)(i): $(r,i-r+1)\notin C$.

This condition of the current subcase directly gives us $\pop(m_{s,\beta}(D))=(i,r)$. We then compare the process of $m_{s,\beta}$ applied to $D$ and $\nabla D$. Each basic monk move that is applied to $D$ will be applied to $\nabla D$ in the exact same way, as the first -tile of $D$, which is the only difference between $D$ and $\nabla D$, is not part of the conversation. In the end, we obtain that $m_{s,\beta}(\nabla D)$ equals $m_{s,\beta}(D)$ taken away the first -tile at $(r,i-r+1)$, i.e. $m_{s,\beta}(\nabla D)=\nabla(m_{s,\beta}(D))$. Moreover, recall that $\rho=\perm(m_{s,\beta}(\nabla D))$, so $\perm(m_{s,\beta}D)=s_i\rho$ since $m_{s,\beta}D$ and $m_{s,\beta}(\nabla D)$ differs at the -tile at $(r,i-r+1)$ which corresponds to the simple transposition $s_i$. By the reduced criterion of these pipe dreams, $i\notin\DES_L(\rho)$.

Subcase (1)(a)(ii): $(r,i-r+1)\in C_p$.

This condition of the current subcase is saying that when we are doing the Monk's rule $m_{s,\beta}$D, the last two basic steps are deleting the -tile at $(i_p,j_{p^-})$, which resolves a previous double crossing, and then inserting a -tile at $(r,i-r+2)$, which does not create a double crossing so that we stop here. Consequently, $\pop(m_{s,\beta}D)=(i+1,r)$ by definition.

Again, we compare the process $m_{s,\beta}(D)$ with $m_{s,\beta}(\nabla D)$. The basic Monk steps are the same before step $p$. At step $(p-1)^+$, in $m_{s,\beta}(D)$, a double crossing is created with the -tile at coordinate $(i_p,j_{p^-})=(r,j_{p^-})$, which is one of the -tile in $D$ belonging to the block of rightmost -tiles in row $r$. We split the discussions based on whether $(r,j_{p^-})$ is the rightmost -tile in row $r$ of $D$, i.e. whether $(r,j_{p^-})$ is in $\nabla D$ or not, and then arrive at the same conclusion.

If $(r,j_{p^-})\notin\cross(\nabla D)$, i.e. $j_{p^-}=i-r+1$, we know that $m_{s,\beta}(\nabla D)$ ends at step $(p-1)^+$. The permutation $\rho=\perm(m_{s,\beta}(\nabla D))$ is also the permutation we obtained from the process of $m_{s,\beta}$ applying to $D$ after move $p^-$ so $\rho=\pi$ in fact. The move $p^-$ removes a -tile that corresponds to the simple transposition $s_i$, so $i\in\DES_L(\rho)$. And the move $p^+$ adds a -tile at coordinate $(r,i-r+2)$ that corresponds to the simple transposition $s_{i+1}$, so $\perm(m_{s,\beta}D)=s_{i+1}\rho$ and $i+1\notin\DES_L(\rho)$. Moreover, $\nabla(m_{s,\beta}D)$ removes the -tile at $(r,i-r+2)$ from $m_{s,\beta}D$ so we observe that $\nabla(m_{s,\beta}D)=m_{s,\beta}(\nabla D)$.

If $(r,j_{p^-})\in\cross(\nabla D)$, i.e. $j_{p^-}<i-r+1$, then the process of $m_{s,\beta}$ applied to $\nabla D$ deletes the -tile at $(r,j_{p^-})$ at step $p^-$, and adds a -tile at $(r,i-r+2)$ at step $p^+$, arriving at the pipe dream that equals $m_{s,\beta}$ applying to $D$ after step $p^-$, which is reduced so we stop. This also gives $\nabla(m_{s,\beta}D)=m_{s,\beta}(\nabla D)$. In $m_{s,\beta}(\nabla D)$, the coordinate $(r,i-r+1)$ contains a -tile so $i\in\DES_L(\rho)$ and since adding a -tile to coordinate $(r,i-r+2)$ yields a reduced pipe dream $m_{s,\beta}D$, we have $i+1\notin\DES_L(\rho)$.

The conclusion does not depend on whether $(r,j_{p^-})\in\cross(\nabla D)$.

Subcase (1)(a)(iii): $(r,i-r+1)\in C_q$, for some $q<p$. By Lemma <ref>, $\pop(m_{s,\beta}D)=(i+1,r)$ since the first -tile of $m_{s,\beta}D$ must be located at $(r,i-r+2)$.

As above, the basic Monk steps for $m_{s,\beta}D$ and $m_{s,\beta}(\nabla D)$ agree for the steps up to $(q-1)^+$, where in $m_{s,\beta}D$, a double crossing is created at $(i_{q-1^+},j_{q-1^+})$ and at $(i_{q^-},j_{q^-})=(r,j_{q^-})$. Either $(r,j_{q^-})\notin\cross(\nabla D)$ or $(r,j_{q^-})\in\cross(\nabla D)$. Both situations will yield the same conclusion.

If $(r,j_{q^-})\notin\cross(\nabla D)$, i.e. $j_{q^-}=i-r+1$, then the process of $m_{s,\beta}$ applied to $\nabla D$ ends after step $(q-1)^+$. Since $m_{s,\beta}(\nabla D)$ would have a double crossing if $(r,i-r+1)$ were a -tile, $s_i\rho$ is not reduced and thus $i\in\DES_L(\rho)$. Now, $m_{s,\beta}(\nabla D)\in\BPD(\rho)$ is precisely the pipe dream of $m_{s,\beta}$ applied to $D$ after move $q^-$. The step $q^+$ of applying $m_{s,\beta}$  to $D$ adds a -tile at coordinate $(r,i-r+2)$ whose corresponding simple transposition is $s_{i+1}$, which creates a double crossing with the -tile at $(i_{q+1^-},j_{q+1^-})$, as $q<p$. This means that $i+1\in\DES_L(\rho)$.

To simulate the steps $q+1^-,q+1^+,\ldots,p^-,p^+$ of $m_{s,\beta} D$, we can uncross the -tile at coordinate $(i_{q+1^-},j_{q+1^-})$, which is a crossing between pipe $i+1$ and $i+2$, of $m_{s,\beta} D$, and continue with step (2) of Definition <ref>. This is saying that the basic Monk steps of $m_{\rho^{-1}(i+2),\rho^{-1}(i+1)}$ applying to $m_{s,\beta}(\nabla D)$ are precisely the same as the basic Monk steps $q+1^-,q+1^+,\ldots,p^-,p^+$ of $m_{s,\beta}$ applying to $D$, as the -tile at coordinate $(r,i-r+2)$ will not be involved in these steps by Lemma <ref>. See Figure <ref> for an example.

An example for Subcase (1)(a)(iii) of Lemma <ref>, with $\pi=\rho=21786534$, $(i,r)=(5,1)$, $(s,\beta)=(2,5)$. The first step $1^-$ of each Monk move is circled and all the other grids in Monk's footsteps are shaded.

If $(r,j_{q^-})\in\cross(\nabla D)$, i.e. $j_{q^-}<i-r+1$, then the the process of $m_{s,\beta}$ applied to $\nabla D$ ends after step $q^+$, which yields a pipe dream that equals $m_{s,\beta}$ applied to $D$ after step $q^-$ so $\rho=\perm(m_{s,\beta}(\nabla D))=\pi$. The first -tile of $m_{s,\beta}(\nabla D)$ is at coordinate $(r,i-r+1)$ so $i\in\DES_L(\rho)$, and since we would have a double crossing if the coordinate $(r,i-r+2)$ were a -tile, $i+1\in\DES_L(\rho)$. To simulate the steps $q+1^-,q+1^+,\ldots,p^-,p^+$ for computing $m_{s,\beta}$ applied to $D$, we can as above uncross the -tile at $(i_{q+1^-},j_{q+1^-})$ by applying $m_{\rho^{-1}(i+2),\rho^{-1}(i+1)}$, and concluding that $\nabla (m_{s,\beta}D)=m_{\rho^{-1}(i+2),\rho^{-1}(i+1)} m_{s,\beta}(\nabla D)$.

As a summary for Case (1)(a), we divide into subcases based on the local conditions of whether and where the first -tile $(r,i-r+1)$ of $D$ appears in the complete Monk footprints $C$, but it turns out that this division is also governed by the “global condition" of whether $i\in \DES_L(\rho)$ and $i+1\in\DES_L(\rho)$ where $\rho=\perm(m_{s,\beta}(\nabla D))$. Specifically, if $i\notin\DES_L(\rho)$, we are in Subcase (1)(a)(i); if $i\in\DES_L(\rho)$ and $i+1\notin\DES_L(\rho)$, we are in Subcase (1)(a)(ii); if $i,i+1\in\DES_L(\rho)$, we are in subcase (1)(a)(iii). The analysis above within the subcases agree with the lemma statement, so we are done with Case (1)(a).

Case (1)(b): $(s,\beta)=(\pi^{-1}(i+1),\pi^{-1}(i))$ where $\pop(D)=(i,r)$. As in case (1)(a), let the Monk footprints be $F=\{(i_{1^-},j_{1^-}),\ldots,(i_{p^+},j_{p^+})\}$ and define $\rho:=\perm(\nabla D)$. The case condition says that $(i_{1^-},j_{1^-})=(r,i-r+1)$, $(i_{1^+},j_{1^+})=(r,i-r+2)$. By Lemma <ref>, the first -tile remains at coordinate $(r,i-r+2)$ throughout the rest of the Monk steps $2^-,\ldots,p^+$. Thus, we already have $\pop(m_{s,\beta} D)=(i+1,r)$.

Subcase (1)(b)(i): $p=1$. Here, the -tile at $(r,i-r+2)$, which corresponds to the simple transposition $s_{i+1}$, does not create a double crossing, so $i+1\notin \DES_L(\rho)$. As $m_{s,\beta}(D)$ is obtained from $D$ by moving the first -tile one step right, $\nabla (m_{s,\beta}D)=\nabla D$ as desired.

Subcase (1)(b)(ii): $p\geq2$. Here, the -tile at $(r,i-r+2)$ creates a double crossing after step $1^+$, so $i+1\in\DES_L(\rho)$. To simulate the basic Monk steps $2^-,2^+,\ldots,p^-,p^+$ of $m_{s,\beta}$ applied to $D$ on $\nabla D$, we need to remove the -tile at $(i_{2^-},j_{2^-})$ which is the crossing between pipe $i+1$ and $i+2$, and then continue applying Step (2) of Definition <ref>. This means that $m_{\rho^{-1}(i+2),\rho^{-1}(i+2)}$
applied to $\nabla D$ gives us $m_{s,\beta} D$ without the first -tile at $(r,i-r+2)$. So $m_{\rho^{-1}(i+2),\rho^{-1}(i+2)}(\nabla D)=\nabla(m_{s,\beta}D)$ as desired.

We are now done with Case (1), which is the map $m_{s,\beta}$. Case (2) deals with the map $x_{\alpha}{\rightsquigarrow}$. The exact same argument from Case (1)(a) is applicable to Case (2)(a), by dividing into subcases based on whether the first -tile of $D$ appears in the Monk footprints of $m_{s,\beta}D$, analyzing whether $i\in\DES_L(\rho)$, $i+1\in\DES_L(\rho)$ where $\rho:=\perm(x_{\alpha}{\rightsquigarrow} (\nabla D))$, and simulating the Monk steps of $m_{s,\beta}D$ via $x_{\alpha}{\rightsquigarrow} (\nabla D)$ and potentially one more Monk move $m_{\rho^{-1}(i+2),\rho^{-1}(i+1)}$. So we will not repeat the details here. Case (2)(b) is a degenrate case where the newly inserted -tile at coordinate $(\alpha,1)$ has become the first -tile of $x_{\alpha}{\rightsquigarrow} D$. We evidently have $\pop(x_{\alpha}{\rightsquigarrow} D)=(\alpha,\alpha)$ and $\nabla (x_{\alpha}{\rightsquigarrow} D)=D$ as desired.

§.§ Induction on bumpless pipe dreams

Before spelling out the technical details, we take a moment to explain our ideas intuitively. Our main idea is to perform two corresponding Monk's rule computations on the bumpless pipe dreams $D$ and $\nabla D$ in parallel and study how these two processes are related. Generically, by “corresponding Monk's rule computations” we mean applying $x_\alpha{\rightsquigarrow}$ or $m_{s,\beta}$ to both $D$ and $\nabla D$. Lemma <ref> spells out the special cases in detail. Each computation of Monk's rule consists of a sequence of basic Monk moves. We will see that in most cases, we may cut the sequence of moves applied to $D$ into $m$ subsequences, and also cut the sequence applied to $\nabla D$ as $m$ corresponding subsequences (two corresponding subsequences might have different number of basic moves), such that before the start of each pair of corresponding subsequences, the two (almost) bumpless pipe dreams are related by $\nabla$, and the first basic moves in the corresponding subsequences start at corresponding tiles (which we define below). Therefore in most cases, applying Monk's rule commutes with applying $\nabla$. In the critical cases when they don't commute, we may still find corresponding sequences as described above until a basic Monk move affect the last column move rectangle in a certain way. The detailed analysis of the critical cases is in Lemma <ref>. The technical difficulties on bumpless pipe dreams, as compared to on pipe dreams, come from the fact that $\nabla$ on pipe dreams is simply removing a cross, whereas on bumpless pipe dreams the procedure is not local.

We first extend the definition of $\nabla$ (Definition <ref>) to almost bumpless pipe dreams by introducing the following column moves:

(2') In the column moves defined in Step (2) of Definition <ref>, simultaneously replace exactly one -tile of the same two pipes in the input and output with a -tile. This is illustrated in Figure <ref>.

(3') To extend the column moves defined in Step (3) of Definition <ref>, add the following column moves:

* If $(x,y)$ is a marked tile and the pipe passing through $(x,y+1)$ is $y+1$, and the -tile is in column $y$ below row $x$, follow the same rule as described in Step (3) of Definition <ref>;

* If $(x,y)$ is a marked tile, pipes $y$ and $y+1$ cross at $(x',y+1)$ for some $x'>x$, and there is a -tile of pipes $y+1$ and $q$ with coordinate $(z,y+1)$ for some $x<z<x'$, define the column move by first replacing the -tile by a -tile and following Step (3) of Definition 3.1, and then replace the -tile of $y$ and $q$ by a -tile.

Extra column moves for almost bumpless pipe dreams in (2'). We suppress the four possibilities for each arrow by using gray  to indicate other possibilities.

Extra column moves for almost bumpless pipe dreams in (3').

The operator $\nabla$ is not defined on all almost bumpless pipe dreams for $\pi$. See Figure <ref> for examples. Specifically, there are the following cases. If $(x,y)$ is a marked tile, let $p$ be the pipe that passes through $(x,y+1)$ which is either a -tile or -tile. Let $(x',y+1)$ be the position of the -turn of $p$ in column $y+1$. If such a position does not exist, the column move is defined. If this is a -tile, and the tile at $(x',y)$ is a -tile of pipes $p$ and $q$, $q$ must also intersect $p$ at a tile between row $x$ and $x'$. In this case a column move is undefined. If $(x',y+1)$ is a -tile, let $q$ be the other pipe of this . If $p=y$ and $q=y+1$, the column move is undefined. Suppose now we can find $(x'',y+1)$ that is the -tile of $q$ in column $y+1$. If $p$ and $q$ cross at $(x'',y)$, the column move is also not defined. It is okay to have these undefined cases, because these configurations will not appear right before the first moves of each pair of corresponding subsequences of basic Monk moves, in which case we need $\nabla$ to be defined.

Examples for when a column move is not defined on an almost bumpless pipe dream (the bottom row of the first rectangle is also the bottom row of the bumpless pipe dream)

Let $\D$ be an (almost) bumpless pipe dream of $\pi$. Suppose after this extension of the definition of $\nabla$, $\nabla$ is defined on $\D$.

Let $\E=\nabla \D$, and suppose $\pop(D)=(i,r)$. We say that a tile $(a,b)$ with $a\ge r$ in $\D$ and a tile $(a',b')$ with $a'\ge r$ in $\E$ are corresponding tiles if in the case that $\D$ and $\E$ each contains a -tile $(a,b)$ and $(a',b')$ are these -tiles, or in the case that neither $\D$ nor $\E$ contains -tiles, $(a,b)$ and $(a',b')$ are both -tiles of pipes $\perm(D)(x)$ and $\perm(E)(x)$ for some $x$, and $a=a'$.

In Figure  <ref>, the first $(\D,\E)$ pair has pairs of corresponding tiles $((2,4),(2,3))$, $((3,3),(3,4))$, $((4,2),(4,2))$, $((4,6),(4,6))$, $((5,5),(5,4))$, and $((6,4),(6,5))$; the second $(\D,\E)$ pair has $((3,4),(4,3))$ as a pair of corresponding tiles.

Examples of corresponding tiles

We remark that in the process of performing two corresponding Monk's rule computations on $D$ and $\nabla D$, at the beginning of each corresponding subsequences of basic moves, there will always be a single pair of corresponding tiles of interest that is determined by the algorithm, even though there can be multiple pairs of corresponding tiles in two bumpless pipe dreams related by $\nabla$ according to the definition. Furthermore, outside of the union
$\mathcal{U}$ of column move rectangles of $\D$ and $\nabla \D$, a pair of corresponding tiles have the same coordinates, since $\D$ and $\nabla \D$ are identical outside of $\mathcal{U}$.

Suppose $\E=\nabla\D$, $\pop(\D)=(i,r)$, and $(a,b)$ in $\D$ and $(a',b')$ in $\E$ are corresponding tiles. Suppose $(a,b)$ is not the southernmost tile with an -turn in column $i+1$.
Then there is a sequence of basic Monk moves following Steps (2) and (3) of Definition <ref> starting with a $\mindroop$ at $(a,b)$ in $\D$, and a corresponding sequence (consisting of possibly different number of steps) of basic Monk moves starting at $(a',b')$ in $\E$ such that after applying both sequences of moves, the resulting (almost) bumpless pipe dreams $\widetilde{\D}$ and $\widetilde{E}$ satisfy  $\widetilde{\E} = \nabla \widetilde{\D}$ and $\pop(\widetilde{\D})=(i,r)$. Furthermore, $\widetilde{\D}$ has more basic Monk moves available if and only if $\widetilde{\E}$ does, and these moves are $\mindroop$s at corresponding tiles.

Let $\mathcal{U}$ be the union of column move rectangles for $\D$ and $\E$. If the basic Monk move at $(a,b)$ affects only tiles in outside of $\mathcal{U}$, then $(a,b) = (a',b')$ and we simultaneously perform the move at $(a,b)$ in $\D$ and $\E$ and get $\widetilde{\D}$ and $\widetilde{\E}$. The next basic Monk moves in $\widetilde{\D}$ and $\widetilde{\E}$ start at the same location.

If the $\mindroop$ at $(a,b)$ affects tiles in $\mathcal{U}$, let $U$ be the column move rectangle that contains $(a,b)$ if it exists; otherwise let $U$ be the column move rectangle that intersects row $a$ closest to $(a,b)$. Notice that the tile $(a,b)$ could be to the left or right of $U$.

We now do a detailed case analysis.  The readers are strongly recommended to refer to the figures while reading. In each accompanying figure of this proof, the vertical arrows are $\nabla$ and the horizontal arrows correspond to sequences of basic Monk moves described in the text; the positions of $\D$, $\E$, $\widetilde{\D}$, and $\widetilde{\E}$ are NW, SW, NE, and SE, respectively. The corresponding tiles in $\D$ and $\E$ where the sequence of basic Monk moves start at are circled.

Case (1) (Figure <ref>). If the tile $(a,b)$ is to the right of $U$, the only way a $\mindroop$ at $(a,b)$ could affect a column move rectangle is when $(a,b)$ is the -turn of a pipe $p$   with a -tile at some $(x,b)$ with $x>a$, where $(x,b)$ is the NE corner of a column move rectangle $U'$.
We perform the $\mindroop$ at $(a,b)$.

* If this $\mindroop$ does not create a -tile, let the result be $\widetilde{\D}$.
The only affected tile in $U'$ by this move is $(x,b)$. The corresponding $\mindroop$ move at $(a, b)$ in $\E$ changes the tiles in exactly the same way outside of $U'$, and at $(x,b)$ the $\jt$-tile becomes a -tile. Let $\widetilde{\E}$ be the result after this move. Then $\widetilde{\E}=\nabla\widetilde{\D}$, and the next basic Monk move in $\widetilde{\D}$ is at $(x,b)$, whereas the next move in $\widetilde{\E}$ is at $(x,b-1)$. These are corresponding tiles.

* If this $\mindroop$ creates a -tile, we check if a $\cbswap$ is necessary. If not, the situation is similar to (a); otherwise, we perform a $\cbswap$ move and let the result be $\widetilde{\D}$. We also perform the $\mindroop$ at $(a,b)$ in $\E$ followed by a $\cbswap$ and obtain $\widetilde{\E}$. We have $\widetilde{\E}=\nabla \widetilde{\D}$, and the next $\mindroop$s in $\widetilde{\D}$ and $\widetilde{\E}$ are at the corresponding - tiles.

Case (1) of Lemma <ref>. In (1)(b) we show the case when the new -tile is in $U'$, but it's possible that the new -tile is outside of a column move rectangle.

Now we consider Cases (2) to (4) when $(a,b)$ is inside a column move rectangle $U$, and $U$ is not the southernmost column move rectangle. Let $U'$ be the column move rectangle immediately SE of $U$. Let $(x,y)$ be the NE corner of $U$. $U'$ could be the southernmost column move rectangle, but the analysis for this case is similar to the case when $U'$ is not. Therefore we focus attention on the case when $U'$ is not the southernmost column move rectangle. Suppose the pipe that goes through the NE corner of $U$ is $p$ and the pipe that goes through the NE corner of $U'$ is $p'$.

Case (2) (Figure <ref>).  The tile $(x,y)$ in $\D$ is an -tile and $(a,b)=(x,y)$. In this case, $(a',b')=(x,y-1)$. There are three subcases to consider:

* $U$ and $U'$ have nonempty intersection, and the pipe $p'$ has an -tile in column $y+1$ that is below row $x$.    First we argue that in this case the width of the rectangle that bounds this $\mindroop$ cannot be larger than 2, because otherwise, the tile $(x,y+1)$ must be a -tile, and the pipe that contains the vertical segment of this cross would be forced to cross $p$ twice.

In $\D$, starting at $(x,y)$, perform all consecutive basic Monk moves that are available in column $y$. At the same time, perform all consecutive $\mindroop$ moves that are available in column $y-1$ in $\E$.
Pipes $p$ and $p'$ would bump at a $\bt$-tile in $\D$ and $\E$.
If $p$ and $p'$ do not intersect, we replace this $\bt$-tile with a  tile in $\D$ and $\E$ and let the results be $\widetilde{\D}$ and $\widetilde{\E}$.
If $p$ and $p'$ already intersect, we simultaneously perform the $\cbswap$ move in $\D$ and $\E$, and let the results be $\widetilde{\D}$ and $\widetilde{\E}$. Since the column moves run NW to SE and the $\cbswap$ moves modify tiles that are NE-SW to each other, the new -tiles created in $\D$ and $\E$ after the corresponding $\cbswap$ moves must be outside of $\mathcal{U}$, and therefore at the same location.

Suppose $(z,y+1)$ is the SE corner of $U'$. Then we see that the rectangle $U''$ with $(x,y)$ as the NW corner and $(z,y+1)$ as the SE corner is a column move rectangle. Replacing $U\cup U'$ with $U''$ in $\mathcal{U}$, we see that $\widetilde{\E}=\nabla \widetilde{\D}$.

* $U$ and $U'$ have nonempty intersection, $(x,y+1)$ is a -tile, and $p'$ has an -tile in column $y+1$ of $\D$ that is  above row $x$. In this case, perform all the basic Monk moves available in column $y$ in $\D$. If a -tile is created at the end, perform also the next move that replaces this tile with a . Let the result be $\widetilde{\D}$. In $\E$, perform all the basic Monk moves available in column $y-1$.  In this case, $p$ would create a bump with $p'$ at $(x',y)$, the SE corner of $U$. Since $p$ and $p'$ already cross at $(x,y+1)$, a $\cbswap$ needs to be performed, and after this we perform all the basic Monk moves available in column $y+1$. If a -tile is created at the end, perform also the next move that replaces this tile with a . Let the result be $\widetilde{\E}$.  Suppose $(z,y+1)$ is the SE corner of $U'$. Let $U''$ be the rectangle with $(x,y)$ as its NW corner and $(z,y+1)$ as its SE corner. Then $U''$ is a column move rectangle. Replacing $U\cup U'$ with $U''$ in $\mathcal{U}$, we see that $\widetilde{\E} = \nabla \widetilde{\D}$. It is also easy to see that the next basic Monk moves in $\widetilde{\D}$ and $\widetilde{\E}$ are at corresponding tiles.

* If $U$ and $U'$ do not intersect, we exhaust all the basic Monk moves available in column $y$ in $\D$ and let the result be $\widetilde{\D}$. Correspondingly, we exhaust all moves available in column $y-1$ in $\E$ and let the result be $\widetilde{\E}$.   Let $U''$ be the rectangle obtained by shifting $U$ to the right by one tile.
Replacing $\mathcal{U}$ with $(\mathcal{U}\setminus U)\cup U''$, we see that $\widetilde{\E}=\nabla \widetilde{\D}$. It is also easy to see that the next basic Monk moves in $\widetilde{\D}$ and $\widetilde{\E}$ are at corresponding tiles.

Cases (2) of Lemma <ref>. The illustration of (2)(b) omits the  case analysis similar to Case (1).

Case (3) (Figure <ref>).
The tile $(a,b)$ in $\D$ is a $\bt$ that previously was a  of $p$ and $q$ for some pipe $q$. Then $(a',b')$ is a also  $\bt$ tile that was previously a  of $p$ and $q$ in $\E$. The case here analysis is parallel to the three cases in (2), so we omit the details, but include the illustrations.

Cases (3) of Lemma <ref>.

Case (4) (Figure <ref>.) The -turn at $(a,b)$ inside $U$ belongs to a pipe $q$ intersecting $p$ at $(a,y)$. Here $b=y-1$. In the figure, we show the cases for when $(a,b)$ is an -tile or when $(a,b)$ is a -tile separately. The corresponding $\mindroop$ in $\E$ is at $(a,y)$. In $\D$, exhaust the basic Monk moves in column $y-1$, and if at the end a -tile is created, perform the move that replaces it with a -tile. In the meantime, exhaust the basic Monk moves in column $y$ of $\E$, and if at the end a -tile is created, perform the move that replaces it with a -tile. These moves preserve the fact that $U$ is a column move rectangle. Let the results be $\widetilde{\D}$ and $\widetilde{\E}$. We have $\widetilde{\E}=\nabla \widetilde{\D}$. The next $\mindroop$s in $\widetilde{\D}$ and $\widetilde{\E}$, if exist, are at corresponding tiles.

Case (4) of Lemma <ref>

We now consider the Cases (5) and (6) when $(a,b)$ is to the left of $U$, and $U$ is not the southernmost column move rectangle.
Case (5) (Figure <ref>.)
The SW corner $(x',y')$ of $U$ in $\D$ is a $\htile$-tile and $a=x'$, $b<y'$. We also have $(a',b')=(a,b)$. We perform a single $\mindroop$ at $(a,b)$ in both $\D$ and $\E$. Again, if a $\bt$-tile is created, we perform also the move that replaces it with a -tile. The results are $\widetilde{\D}$ and $\widetilde{\E}$.

Case (5) of Lemma <ref>

Case (6) (Figure <ref>).
The -turn at $(a,b)$  belongs to a pipe $q$ intersecting $p$ at $(a,y)$, and $(a,b)$ is outside of $U$. Pipe $q$ intersects $p$ at $(a,y-1)$ in $\E$ and the corresponding $\mindroop$ in $\E$ is also at $(a,b)$. We exhaust all basic Monk moves in column $b$ in $\D$, and at the same time exhaust all basic Monk moves in column $b$ in $\E$. If this does not create a -tile with pipe $p$, let the results be $\widetilde{\D}$ and $\widetilde{\E}$. $U$ remains a column move rectangle and $\widetilde{\E}=\nabla \widetilde{\D}$. This is illustrated as Case (6)(a). If a -tile of $p$ and $q$ is created, we have again three cases to consider parallel to Case  (3). these are illustrated as Case (6), (b)–(d).

Case (6) of Lemma <ref>

Now consider Cases (7) and (8) when $U$ is the southernmost column move rectangle. Recall from the assumption of the lemma that $(a,b)$ is not the southernmost -turn in the east-side column of $U$.

Case (7) (Figure <ref>). Suppose $b=i$ and $(a,b)$ is the southernmost tile in column $i$ that contains an -turn. Then $(a',b')=(a,i+1)$.
We simultaneously exhaust the basic Monk moves in column $i$ of $\D$ and in column $i+1$ of $\E$. The last move in  either sequence must be a $\mindroop$ that creates a bump at $(c,j)$, the SE corner of the both $\mindroop$ moves. The next move replaces this bump with a -tile, and let the results be $\widetilde{\D}$ and $\widetilde{\E}$. We give separate illustrations for $(a,b)$ is an -tile versus a -tile.

Case (7) of Lemma <ref>

Case (8) Suppose $b=i$ and $(a,b)$ is above the southernmost -tile in column $i$. This is similar to Case (4).

Finally, we consider the cases when $U$ is the southernmost column move rectangle and $(a,b)$ is left of $U$.

Case (9) (Figure <ref>.) These cases are similar to (6)(a). We omit the details, but include the illustration for reference.

Case (9) of Lemma <ref>

After replacing $\PD$'s by $\BPD$'s, the statements in Lemma <ref> hold.

We give a proof for Case (1); Case (2) is similar.

Case (1)(a).
Let $\D$ be the almost bumpless pipe dream of $\pi$ obtained from $D$ by replacing the crossing of pipes $\pi t_{s,\beta}(s)$ and $\pi t_{s,\beta}(\beta)$  with a -tile, and let $\E=\nabla \D$. $\E$ is the almost bumpless pipe dream of $s_i\pi$ obtained from $\nabla D$ by replacing the crossing of pipes $s_i\pi t_{s,\beta}(s)$ and $s_i\pi t_{s,\beta}(\beta)$ in with a -tile.

Consider simultaneously the process of computing $m_{s,\beta}(D)$ and $m_{s,\beta}(\nabla D)$ by modifying $\D$ and $\E$ with basic Monk moves, and let $\D_0:=\D$ and $\E_0:=\E$. Applying Lemma <ref> repeatedly, for each timestep $d=0,1,2,\cdots$, we let $\D_{d+1}:=\widetilde{\D_d}$ and $\E_{d+1}:=\widetilde{\E_d}$. Let $\mathcal{U}_d$ be the union of column move rectangles where $\D_d$ and $\E_d$ differ for each $d$, and let $U_d$ denote the southernmost one in each $\mathcal{U}_t$. We stop at step $t$ when either we encounter a $\mindroop$ at the southernmost -turn $(a,i+1)$ in column $i+1$ of $\D$, in which case the corresponding $\mindroop$ is at the southernmost -turn $(a',i)$ in column $i$ of $\E$, or such moves never occur and the computation of Monk's rule is complete. In the latter case, $\nabla(m_{s,\beta}(D))=m_{s,\beta}(\nabla D)$, $\pop(m_{s,\beta}(D))=(i,r)$, and $i\not\in \DES_L(\rho)$. We now do a careful analysis of the former case.

We consider the case when
$(a,i+1)$ in $\D_t$ is an -tile where the case for when it is a -tile is similar. In this case $a'=a$. We exhaust the basic Monk moves in column $i$ of $\E_t$ starting at $(a,i)$. When this is done, pipes $i$ and $i+1$ create a -tile. Since these two pipes have not crossed before, replacing this $\bt$-tile with a -tile terminates the algorithm. Let the result be $\E_{t+1}$, so $\E_{t+1}=m_{s,\beta}(\nabla(\D))$. Notice that in this case $\rho=\pi$, and in particular $i\in \DES_L(\rho)$.

If $i+1\not\in\DES_L(\pi)$, it must be the case that the southernmost -tile in $\D_t$ of column $i+2$ is below row $a$, and pipes $i+1$ and $i+2$ do not cross. Therefore, after exhausting the basic Monk moves in column $i+1$ starting at $(a,i+1)$, pipes $i+1$ and $i+2$ create a -tile, and we are done after we replace it with a -tile. Let the result be $\D_{t+1}$. The southernmost column move rectangle in $\D_{t+1}$ is $U_t$ shifted to the right by one tile. Therefore, $\nabla(m_{s,\beta}(D))=m_{s,\beta}(\nabla D)$, $\pop(m_{s,\beta}(D))=(i+1,r)$.

If $i+1\in \DES_L(\pi)$, we consider two cases:

* The tile $(a,i+2)$ in $\D_t$ is a -tile where pipes $i+1$ and $i+2$ cross. Let $\D'_{t+1}$ be the computed from $\D_t$ by exhausting all basic Monk moves in column $i+1$. As a result, the southernmost column move rectangle in $\D'_{t+1}$ is $U_t$ shifted to the right by one tile. Meanwhile, in $\E_{t+1}$, the -tile of $i+1$ and $i+2$ is at $(a,i+2)$. Replacing it with a -tile and exhausting the basic Monk moves in column $i+2$ gives $\E'_{i+1}$ so that $\nabla \D'_{t+1}=\E'_{i+1}$. We see that the rest of basic Monk moves that finish the computation of $m_{s,\beta}(D)$ and $m_{\pi^{-1}(i+2),\pi^{-1}(i+1)}(m_{s,\beta}(\nabla D))$ do not affect the union of column move rectangles. This case is illustrated in Figure <ref>.

Case (1)(a)(i) of Lemma <ref>.

* In $\D_t$, pipes $i+1$ and $i+2$ cross in a column $j>i+2$. Let $\D'_{t+1}$ be obtained from $\D_t$ by exhausting the basic Monk moves in column $i+1$, followed by a $\cbswap$. Let $U_{t+1}$ be $U_t$ shifted to the right by one unit.
At this point, $\D'_{t+1}$ and $\E_{t+1}$ differ within $U_{t+1}$ by a column move. In $\E_{t+1}$ replace the -tile of $i+1$ and $i+2$ in with a -tile and let the result be $\E'_{t+1}$. Then $\nabla \D'_{t+1}=\E'_{t+1}$. Again, the remaining basic Monk moves only affect tiles outside of the union of column move rectangles. This case is illustrated in Figure <ref>.

Case (1)(a)(ii) of Lemma <ref>.

In both cases, $\nabla(m_{s,\beta}(D))=m_{\rho^{-1}(i+2),\rho^{-1}(i+1)}(m_{s,\beta}(\nabla D))$ and $\pop(m_{s,\beta(D)})=(i+1,r)$.

Case (1)(b).  Let $\D$ be the almost bumpless pipe dream of $\pi$ obtained by replacing the -tile at $(a, i+1)$ of pipes $i$ and $i+1$ with a -tile. In this case $\perm(\D)=s_i\pi=\rho$.

If $i+1\not\in \DES_L(\rho)$, then it must be the case that in $\D$, there is an -tile $(b,i+2)$ of pipe $i+2$  for some $b>a$, and $i+2$ does not cross with $i+1$. Therefore, exhausting the basic Monk moves in column $i+1$ of $\D$ and then replace the -tile at $(b,i+2)$ with a -tile completes the computation $m_{s,\beta}(D)$. We see that in this case $\pop(m_{s,\beta}(D))=(i+1,r)$ and $\nabla(m_{s,\beta}(D))=\nabla D$. See Figure <ref> for an illustration of this case.

Case (1)(b) of Lemma <ref>.

If $i+1\in \DES_L(\rho)$, we may again consider two cases depending on whether the -tile of pipes $i+1$ and $i+2$ in $\D$ is in column $i+2$. The argument is similar to the parallel cases in (1)(a), so we omit the details.

§ ACKNOWLEDGEMENTS

We thank Allen Knutson and Alex Yong for helpful conversations.

[1]
Nantel Bergeron and Sara Billey.
RC-graphs and Schubert polynomials.
Experiment. Math., 2(4):257–269, 1993.

[2]
Sara C. Billey, Alexander E. Holroyd, and Benjamin J. Young.
A bijective proof of Macdonald's reduced word formula.
Algebr. Comb., 2(2):217–248, 2019.

[3]
Sara C. Billey, William Jockusch, and Richard P. Stanley.
Some combinatorial properties of Schubert polynomials.
J. Algebraic Combin., 2(4):345–374, 1993.

[4]
Alex Fink, Karola Mészáros, and Avery St. Dizier.
Zero-one Schubert polynomials.
Math. Z., 297(3-4):1023–1042, 2021.

[5]
Daoji Huang.
Bijective proofs of monk's rule for schubert and double schubert
polynomials with bumpless pipe dreams.
arXiv preprint arXiiv:2010.15048, 2020.

[6]
Daoji Huang.
Schubert products for permutations with separated descents.
arXiv preprint arXiv:2105.01591, 2021.

[7]
Allen Knutson.
Schubert polynomials, pipe dreams, equivariant classes, and a
co-transition formula.
arXiv preprint arXiv:1909.13777, 2019.

[8]
Thomas Lam, Seung Jin Lee, and Mark Shimozono.
Back stable schubert calculus.
arXiv preprint arXiv:1806.11233, 2018.

[9]
Alain Lascoux and Marcel-Paul Schützenberger.
Polynômes de Schubert.
C. R. Acad. Sci. Paris Sér. I Math., 294(13):447–450,


$SO(N)\backslash SL(N)$ using the matrix 131313Take care that the coordinates
$y_{i}$ and $x_{ij}$ are not the same as in (3.4).

$Y_{0}[n]=n_{1}^{2}+\sum_{i=2}^{N}y_{i}^{2}n_{i}^{2}+\sum_{i<j}x_{ij}n_{i}n_{j}\;.$
(A.5)

Now, solving the condition that $Y_{0}[n]=1$ for all roots of $A_{N}$, one
obtains

$y_{i}^{2}=1\;,\qquad y_{i}^{2}+y_{j}^{2}-x_{ij}=1\;,$ (A.6)

which determines $y_{i}=x_{ij}=1$ and fixes the $A_{N}$ point
$H=(N+1)^{-\frac{1}{N}}C_{A_{N}}$.

One can consider similarly the symmetric point $D_{N{+}1}$ in $SO(N)\backslash
SL(N)$. Starting form (4.33) and shifting $n_{2}\rightarrow n_{2}-n_{N+1}$ one
obtain the equivalent representative of the $D_{N{+}1}$ Cartan matrix

$C^{\prime}_{D_{N{+}1}}=2\sum_{i=1}^{N+1}n_{i}^{2}+2\sum_{\begin{subarray}{c}i<j\\\
(i,j)\neq(2,N+1)\end{subarray}}n_{i}n_{j}\;,$ (A.7)

where the second sum is over all pairs except $n_{2}n_{N+1}$. One checks that
$H=2^{-\frac{2}{N+1}}C^{\prime}_{D_{N+1}}$ is in the Grenier domain with the
triangular form

$\displaystyle Y_{0}$ $\displaystyle=$
$\displaystyle\Bigl{(}n_{1}+\frac{1}{2}\sum_{i=2}^{N+1}n_{i}\Bigr{)}^{2}+\frac{3}{4}\Bigl{(}n_{2}+\frac{1}{3}\sum_{i=3}^{N}n_{i}-\frac{1}{3}n_{N+1}\Bigr{)}^{2}$
(A.8)
$\displaystyle+\frac{1}{2}\sum_{k=2}^{N-1}\frac{k+2}{k+1}\biggl{(}n_{k+1}+\frac{1}{k+1}\sum_{i=k+2}^{N}n_{i}+\frac{2}{k+2}n_{N+1}\biggr{)}^{2}+\frac{4}{N+1}n_{N+1}^{2}\;,$

and the sub-components

$\displaystyle Y_{0}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{N+1}n_{i}^{2}+\sum_{\begin{subarray}{c}i<j\\\
(i,j)\neq(2,N+1)\end{subarray}}n_{i}n_{j}$ $\displaystyle Y_{1}$
$\displaystyle=$
$\displaystyle\sum_{i=2}^{N+1}n_{i}^{2}+\frac{2}{3}\sum_{\begin{subarray}{c}2\leq
i<j\\\ (i,j)\neq(2,N+1)\end{subarray}}n_{i}n_{j}-\frac{2}{3}n_{2}n_{N+1}\;,$
$\displaystyle Y_{k\geq 2}$ $\displaystyle=$
$\displaystyle\sum_{i=k+1}^{N+1}n_{i}^{2}+\frac{2}{k+2}\sum_{k+1\leq i<j\leq
N}n_{i}n_{j}+\frac{4}{k+2}n_{N+1}\sum_{i=k+1}^{N}n_{i}\;.$ (A.9)

The triangular form of $Y_{0}$ exhibits that all $x_{ij}\in[0,\frac{1}{2}]$
but $x_{2,N+1}=-\frac{1}{3}\in[-\frac{1}{2},\frac{1}{2}]$. The sub-components
all have minimum length vectors of length one, and $H$ is therefore in the
Grenier domain. This point sits on the boundary because the inequalities
$Y_{0}[n]\geq 1$ are saturated for all $D_{N+1}$ roots, i.e.

$\displaystyle n_{i}$ $\displaystyle=$ $\displaystyle\pm\delta_{i,j}\;,\qquad
n_{i}=\delta_{i,j}-\delta_{i,k}\quad\mbox{for}\;(j,k)\neq(2,N+1)\;{\rm
or}\;(N+1,2)\;,$ $\displaystyle n_{i}$ $\displaystyle=$
$\displaystyle\pm(\delta_{i,j}-\delta_{i,2}-\delta_{i,N+1})\quad\mbox{for}\;j\neq
2,N+1\;,$ $\displaystyle n_{i}$ $\displaystyle=$
$\displaystyle\pm(\delta_{i,j}+\delta_{i,k}-\delta_{i,2}-\delta_{i,N+1})\quad\mbox{for}\;j,k\neq
2,N+1\;.$ (A.10)

For $Y_{k}$ with $k=1$ and $k\geq 3$, the only vectors of length $1$ are
$n_{i}=\delta_{i,j}$ for all $j\geq k+1$. For $k=2$ one gets all vectors
$n_{i}=\delta_{i,j}$ with $j\geq 3$ and the vectors
$n_{i}=\pm\delta_{i,j}\mp\delta_{i,N+1}$ for $3\leq i\leq N$. Writing the
equalities $Y_{0}[n]=1$ for all $D_{N+1}$ roots for the generic matrix

$Y_{0}[n]=n_{1}^{2}+\sum_{i=2}^{N}y_{i}^{2}n_{i}^{2}+\sum_{i<j}x_{ij}n_{i}n_{j}$
(A.11)

one obtains

$\displaystyle y_{i}^{2}=1\;,\qquad
y_{i}^{2}+y_{j}^{2}-x_{ij}=1\quad\mbox{for}\;(i,j)\neq(2,N+1)\;,$ (A.12)
$\displaystyle
y_{i}^{2}+y_{2}^{2}+y_{N+1}^{2}-x_{i2}-x_{i\,N+1}+x_{2\,N+1}=1\quad\mbox{for}\;i\neq
2,N+1\;,$ $\displaystyle
y_{i}^{2}+y_{j}^{2}+y_{2}^{2}+y_{N+1}^{2}+x_{ij}-x_{i2}-x_{i\,N+1}-x_{j2}-x_{j\,N+1}+x_{2\,N+1}=1\quad\mbox{for}\;i,j\neq
2,N+1\;.$

This implies that $y_{i}=1$ and $x_{ij}=1$ except for $x_{2\,N+1}=0$ and
therefore $H=2^{-\frac{2}{N+1}}C^{\prime}_{D_{N+1}}$.

In general one does not expect reducible matrices to correspond to a zero
dimensional boundary of the Grenier domain. Take as an example
$H=(2N+2)^{-\frac{1}{N+1}}C_{A_{N}+A_{1}}$ with

$C_{A_{N}+A_{1}}[n]=2\sum_{i=1}^{N+1}n_{i}+2\sum_{i<j\leq N}n_{i}n_{j}\;.$
(A.13)

One checks similarly that $H$ is in the Grenier domain, but the saturated
inequalities still allow for a dimension $N$ boundary parametrised by

$Y_{0}[n]=\sum_{i=1}^{N+1}n_{i}+\sum_{i<j\leq
N}n_{i}n_{j}+\sum_{i=1}^{N}x_{i}n_{N+1}n_{i}\;,$ (A.14)

provided they satisfy

$\sum_{i=1}^{k}x_{i}^{2}-\frac{2}{k+1}\sum_{i<j\leq k}x_{i}x_{j}\leq 1\;,$
(A.15)

for all $k$ between $1$ and $N$.

For the lattice $A_{5}^{+2}$, the matrix (4.35)

$C_{\\!A_{5}^{+2}}=\left(\begin{array}[]{ccccc}\;2&\;1&\;1&\;1&\;2\\\
\;1&\;2&\;1&\;1&\;2\\\ \;1&\;1&\;2&\;1&\;2\\\ \;1&\;1&\;1&\;2&\;2\\\
\;2&\;2&\;2&\;2&\;\frac{10}{3}\end{array}\right)\;$ (A.16)

is not in the Grenier domain. But using the $SL(5,\mathds{Z})$ matrix

$\gamma=\left(\begin{array}[]{ccccc}\;0&\;0&\;0&\;1&\;1\\\
\;1&\;1&\;0&\;0&\;1\\\ \;0&\;1&\;1&\;0&\;1\\\ \;0&\;1&\;0&\;0&\;0\\\
-1&-2&-1&-1&-2\end{array}\right)\;,$ (A.17)

one obtains that

$C^{\prime}_{\\!A_{5}^{+2}}=\gamma^{\intercal}C_{\\!A_{5}^{+2}}\gamma$ (A.18)

is. This is manifest in the upper triangular form

$C^{\prime}_{\\!A_{5}^{+2}}[n]=\frac{4}{3}\Biggl{(}\bigl{(}n_{1}+\tfrac{1}{2}n_{2}+\tfrac{1}{4}n_{3}+\tfrac{1}{4}n_{4}+\tfrac{1}{2}n_{5}\bigr{)}^{2}\\\
+\frac{3}{4}\biggl{(}\bigl{(}n_{2}+\tfrac{1}{2}n_{3}-\tfrac{1}{2}n_{4}\bigr{)}^{2}+\bigl{(}n_{3}+\tfrac{1}{2}n_{4}+\tfrac{1}{2}n_{5}\bigr{)}^{2}+\frac{3}{4}\Bigl{(}\bigl{(}n_{4}+\tfrac{1}{3}n_{5}\bigr{)}^{2}+\tfrac{8}{9}n_{5}^{\;2}\Bigr{)}\biggr{)}\Biggr{)}\;.$
(A.19)

This bilinear form admits 30 vectors of norm square $\frac{4}{3}$ in
$\mathds{Z}^{5}$, the 15 weights in the Weyl orbit of the highest weights
$\Lambda_{2}$ and the 15 in the Weyl orbit of $\Lambda_{4}$. The corresponding
conditions $Y_{0}[n]=1$ determine $C^{\prime}_{\\!A_{5}^{+2}}$, and the
lattice $A_{5}^{+2}$ is therefore at a dimension-zero boundary of the Grenier
domain.

##  Appendix B Invariant polynomials at the $A_{N}$ symmetric point

We prove here that there are indeed only two quadratic invariant polynomials
at the $A_{N}$ symmetric point by constructing them explicitly. We can easily
see that for any polynomial $F(\tilde{p})$, its average on ${\rm S}_{N+1}$
defined by

$\langle F(\tilde{p})\rangle_{{\rm S}_{N+1}}=\frac{1}{\lvert{\rm
S}_{N+1}\lvert}\sum_{\gamma\in{\rm
S}_{N+1}}F(\gamma^{\intercal}\tilde{p}\gamma)\;,$ (B.1)

is an ${\rm S}_{N+1}$-invariant polynomial. Therefore by calculating the
$\langle\tilde{p}_{ij}\rangle_{{\rm S}_{N+1}}$ and
$\langle\tilde{p}_{ij}\tilde{p}_{rs}\rangle_{{\rm S}_{N+1}}$ we can generate
all independent ${\rm S}_{N+1}$-invariant linear and quadratic polynomials. We
start with the linear polynomials where the calculations are less tedious but
are completely analogous to the quadratic case. We can see that141414Actually
it is not obvious that we don’t need to take another average on ${\rm S}_{N}$
in the end but it turns out that this is indeed not the case

$\langle\tilde{p}_{ij}\rangle_{{\rm
S}_{N+1}}=\langle\langle\tilde{p}_{ij}\rangle_{{\rm
S}_{N}}\rangle_{\mathds{Z}_{N+1}}$ (B.2)

It is easy to see that the average on ${\rm S}_{N}$ doesn’t depend on $i,j$
explicitly however the result will differ if $i=j$ or $i\neq j$. Therefore
there are naively only two possible linear invariant polynomials. We can
easily compute the two independent averages on ${\rm S}_{N}$.

$\displaystyle\langle\tilde{p}_{ii}\rangle_{{\rm S}_{N}}$
$\displaystyle=\frac{1}{N!}\sum_{\sigma\in{\rm
S}_{N}}\tilde{p}_{\sigma^{-1}(i)\sigma^{-1}(i)}=\frac{1}{N}\sum_{i=1}^{N}\tilde{p}_{ii}$
(B.3) $\displaystyle\langle\tilde{p}_{ij}\rangle_{{\rm S}_{N}}$
$\displaystyle=\frac{1}{N!}\sum_{\sigma\in{\rm
S}_{N}}\tilde{p}_{\sigma^{-1}(i)\sigma^{-1}(j)}=\frac{2}{N(N-1)}\sum_{i<j}\tilde{p}_{ij}$
(B.4)

where $i\neq j$ in the second line. Hence all that remains is to calculate
$\langle\tilde{p}_{ij}\rangle_{\mathds{Z}_{N+1}}$. If we use the convention
that the indices $i,j$ of $\tilde{p}_{ij}$ are taken modulo $N+1$ we can write
an arbitrary number of iterations of the transformation $\sigma_{f}$ in the
simplified form

$\sigma_{f}^{k}.\tilde{p}_{ij}=\tilde{p}_{N-k+1N-k+1}+\tilde{p}_{i-kj-k}-\tilde{p}_{i-kN-k+1}-\tilde{p}_{j-kN-k+1}$
(B.5)

for all $k\geq 0$. We find that

$\langle\tilde{p}_{ij}\rangle_{\mathds{Z}_{N+1}}=\frac{1}{N+1}\left(\sum_{k=1}^{N}\tilde{p}_{kk}+\sum_{k=1}^{N+1}\tilde{p}_{k+ik+j}-\sum_{k=1}^{N}\tilde{p}_{k+ik}-\sum_{k=1}^{N}\tilde{p}_{k+jk}\right)$
(B.6)

for any $i,j$. Hence we find that

$\displaystyle\langle\tilde{p}_{ii}\rangle_{{\rm S}_{N+1}}$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\langle\tilde{p}_{ii}\rangle_{\mathds{Z}_{N+1}}=\frac{2}{N(N+1)}\left(N\sum_{i=1}^{N}\tilde{p}_{ii}-2\sum_{i<j}\tilde{p}_{ij}\right)=0$
(B.7) $\displaystyle\langle\tilde{p}_{ij}\rangle_{{\rm S}_{N+1}}$
$\displaystyle=\frac{2}{N(N-1)}\sum_{i<j}\langle\tilde{p}_{ij}\rangle_{\mathds{Z}_{N+1}}=\frac{1}{N(N+1)}\left(N\sum_{i=1}^{N}\tilde{p}_{ii}-2\sum_{i<j}\tilde{p}_{ij}\right)=0$
(B.8)

where we have used the traceless condition and where $i\neq j$ in the second
line. Therefore there are no linear ${\rm S}_{N+1}$-invariant polynomials of
$\tilde{p}$. This means that $C_{A_{N}}$ as defined in (4.30) is an extremum
of any automorphic function on $SO(N)\backslash SL(N)$.

We will now apply the same reasoning to show that there are only two
independent quadratic ${\rm S}_{N+1}$-invariant polynomials of $\tilde{p}$. We
can show that

$\displaystyle\sigma_{f}^{k}.\tilde{p}_{ij}\tilde{p}_{rs}=$
$\displaystyle\sigma_{f}^{k}.\tilde{p}_{ij}\,\sigma_{f}^{k}.\tilde{p}_{rs}$
$\displaystyle=$ $\displaystyle(\tilde{p}_{N-k+1N-k+1})^{2}$
$\displaystyle-\tilde{p}_{N-k+1N-k+1}(\tilde{p}_{i-kN-k+1}+\tilde{p}_{j-kN-k+1}+\tilde{p}_{r-kN-k+1}+\tilde{p}_{s-kN-k+1})$
$\displaystyle+\tilde{p}_{N-k+1N-k+1}(\tilde{p}_{i-kj-k}+\tilde{p}_{r-ks-k})+(\tilde{p}_{i-kN-k+1}+\tilde{p}_{j-kN-k+1})(\tilde{p}_{r-kN-k+1}+\tilde{p}_{s-kN-k+1})$
$\displaystyle-\tilde{p}_{i-kj-k}(\tilde{p}_{r-kN-k+1}+\tilde{p}_{s-kN-k+1})-\tilde{p}_{r-ks-k}(\tilde{p}_{i-kN-k+1}+\tilde{p}_{j-kN-k+1})$
$\displaystyle+\tilde{p}_{i-kj-k}\tilde{p}_{r-ks-k}$ (B.9)

For all $i,j,r,s$. Let us now calculate
$\langle\tilde{p}_{ij}\tilde{p}_{rs}\rangle_{\mathds{Z}_{N+1}}$

$\displaystyle\langle\tilde{p}_{ij}\tilde{p}_{rs}\rangle_{\mathds{Z}_{N+1}}=$
$\displaystyle\frac{1}{N+1}\left(\sum_{k=1}^{N}(\tilde{p}_{kk})^{2}-\sum_{k=1}^{N}\tilde{p}_{kk}(\tilde{p}_{ik+ik}+\tilde{p}_{k+jk}+\tilde{p}_{k+rk}+\tilde{p}_{k+sk})\right.$
$\displaystyle+\sum_{k=1}^{N}\tilde{p}_{kk}(\tilde{p}_{k+ik+j}+\tilde{p}_{k+rk+s})+\sum_{k=1}^{N}(\tilde{p}_{k+ik}+\tilde{p}_{k+jk})(\tilde{p}_{k+rk}+\tilde{p}_{k+sk})$
$\displaystyle-\sum_{k=1}^{N}\tilde{p}_{k+ik+j}(\tilde{p}_{k+rk}+\tilde{p}_{k+sk})-\sum_{k=1}^{N}\tilde{p}_{k+rk+s}(\tilde{p}_{k+ik}+\tilde{p}_{k+jk})$
$\displaystyle\left.+\sum_{k=1}^{N+1}\tilde{p}_{k+ik+j}\tilde{p}_{k+rk+s}\right)$
(B.10)

for all $i,j,r,s$. We can now calculate the average on ${\rm S}_{N+1}$ in an
analogous way to the linear case. Just like the linear case we can see that
the average on ${\rm S}_{N}$ will not depend on $i,j,r,s$ explicitly, however
the result will differ depending on if some indices are equal to each other.
One can see that there are 7 different averages to compute:
$\langle(\tilde{p}_{ii})^{2}\rangle_{{\rm S}_{N+1}}$,
$\langle\tilde{p}_{ii}\tilde{p}_{ij}\rangle_{{\rm S}_{N+1}}$,
$\langle\tilde{p}_{ii}\tilde{p}_{jj}\rangle_{{\rm S}_{N+1}}$,
$\langle(\tilde{p}_{ij})^{2}\rangle_{{\rm S}_{N+1}}$,
$\langle\tilde{p}_{ii}\tilde{p}_{jr}\rangle_{{\rm S}_{N+1}}$,
$\langle\tilde{p}_{ij}\tilde{p}_{ir}\rangle_{{\rm S}_{N+1}}$ and
$\langle\tilde{p}_{ij}\tilde{p}_{rs}\rangle_{{\rm S}_{N+1}}$ where all indices
are assumed to be different. We can decompose each of them on a basis of ${\rm
S}_{N}$ invariant polynomials as

$\displaystyle
a_{1}\sum_{i=1}^{N}(\tilde{p}_{ii})^{2}+a_{2}\sum_{i<j}\tilde{p}_{ii}\tilde{p}_{jj}+a_{3}\sum_{i\neq
j}\tilde{p}_{ii}\tilde{p}_{ij}+a_{4}\sum_{i<j}(\tilde{p}_{ij})^{2}$
$\displaystyle+a_{5}\sum_{i=1}^{N}\sum_{\begin{subarray}{c}j<l\\\ j\neq i\\\
l\neq
i\end{subarray}}\tilde{p}_{ii}\tilde{p}_{jl}+a_{6}\sum_{i=1}^{N}\sum_{\begin{subarray}{c}j<l\\\
j\neq i\\\ l\neq
i\end{subarray}}\tilde{p}_{ij}\tilde{p}_{il}+a_{7}\sum_{\begin{subarray}{c}i\neq
j\neq m\neq l\\\ i<j\\\ m<l\\\ i<m\end{subarray}}\tilde{p}_{ij}\tilde{p}_{ml}$
(B.11)

For $N>2$ we can check that only three out of the seven averages are actually
independent and they are linearly dependent with the Killing-Cartan form

$\displaystyle\,\mbox{tr}\,C_{A_{N}}^{-1}\,\tilde{p}\,C_{A_{N}}^{-1}\,\tilde{p}=$
$\displaystyle\frac{4}{(N+1)^{2}}\Biggl{(}N^{2}\sum_{i=1}^{N}(\tilde{p}_{ii})^{2}+2\sum_{i<j}p_{ii}\tilde{p}_{jj}\Biggr{.}$
$\displaystyle-4N\sum_{i\neq
j}\tilde{p}_{ii}\tilde{p}_{ij}+2(N^{2}+1)\sum_{i<j}(\tilde{p}_{ij})^{2}$
$\displaystyle\Biggl{.}+4\sum_{i=1}^{N}\sum_{\begin{subarray}{c}j<l\\\ j\neq
i\\\ l\neq
i\end{subarray}}\tilde{p}_{ii}\tilde{p}_{jl}-4(N-1)\sum_{i=1}^{N}\sum_{\begin{subarray}{c}j<l\\\
j\neq i\\\ l\neq
i\end{subarray}}\tilde{p}_{ij}\tilde{p}_{il}+8\sum_{\begin{subarray}{c}i\neq
j\neq m\neq l\\\ i<j\\\ m<l\\\
i<m\end{subarray}}\tilde{p}_{ij}\tilde{p}_{ml}\Biggr{)}$ (B.12)

as well as

$\displaystyle\text{tr}(C_{A_{N}}^{-1}$
$\displaystyle\tilde{p})^{2}=\frac{4}{(N+1)^{2}}\Biggl{(}N^{2}\sum_{i=1}^{N}(\tilde{p}_{ii})^{2}+2N^{2}\sum_{i<j}\tilde{p}_{ii}\tilde{p}_{jj}-4N\sum_{i\neq
j}\tilde{p}_{ii}\tilde{p}_{ij}\Biggr{.}$
$\displaystyle\Biggl{.}+4\sum_{i<j}(\tilde{p}_{ij})^{2}-4N\sum_{i=1}^{N}\sum_{\begin{subarray}{c}j<l\\\
j\neq i\\\ l\neq
i\end{subarray}}\tilde{p}_{ii}\tilde{p}_{jl}+8\sum_{i=1}^{N}\sum_{\begin{subarray}{c}j<l\\\
j\neq i\\\ l\neq
i\end{subarray}}\tilde{p}_{ij}\tilde{p}_{il}+8\sum_{\begin{subarray}{c}i\neq
j\neq m\neq l\\\ i<j\\\ m<l\\\
i<m\end{subarray}}\tilde{p}_{ij}\tilde{p}_{ml}\Biggr{)}=0$ (B.13)

which vanishes once the traceless condition is imposed. This proves that there
are two independent non trivial quadratic ${\rm S}_{N+1}$-invariant
polynomials of $\tilde{p}$. The other non trivial independent polynomial is
given by one of the averages, we give the simplest one

$\langle(\tilde{p}_{ii})^{2}\rangle_{{\rm
S}_{N+1}}=\frac{2}{(N+1)N}\left(N\sum_{i=1}^{N}(\tilde{p}_{ii})^{2}-4\sum_{i\neq
j}\tilde{p}_{ii}\tilde{p}_{ij}+2\sum_{i<j}\tilde{p}_{ii}\tilde{p}_{jj}+4\sum_{i<j}(\tilde{p}_{ij})^{2}\right)$
(B.14)

In the case $N=2$ only the first four averages exist and they are all
proportional to the Killing-Cartan form once the traceless condition is
imposed. Therefore we can recover the well known result that $A_{2}$ is a
local minimum (and indeed the global minimum) for the $SL(2)$ Eisenstein
series.

## References

  * [1] E. Palti, “The Swampland: Introduction and Review,” Fortsch. Phys. 67 no. 6, (2019) 1900037, arXiv:1903.06239 [hep-th].
  * [2] D. J. Gross and J. H. Sloan, “The Quartic Effective Action for the Heterotic String,” Nucl. Phys. B291 (1987) 41–89.
  * [3] M. B. Green, J. G. Russo, and P. Vanhove, “Low energy expansion of the four-particle genus-one amplitude in type II superstring theory,” JHEP 0802 (2008) 020, arXiv:0801.0322 [hep-th].
  * [4] M. B. Green, J. G. Russo, and P. Vanhove, “Modular properties of two-loop maximal supergravity and connections with string theory,” JHEP 0807 (2008) 126, arXiv:0807.0389 [hep-th].
  * [5] M. B. Green and J. H. Schwarz, “Supersymmetrical String Theories,” Phys. Lett. B109 (1982) 444–448.
  * [6] M. B. Green and M. Gutperle, “Effects of D-instantons,” Nucl. Phys. B498 (1997) 195–227, arXiv:hep-th/9701093.
  * [7] M. B. Green and P. Vanhove, “D-instantons, strings and M-theory,” Phys. Lett. B408 (1997) 122–134, arXiv:hep-th/9704145.
  * [8] N. Berkovits, “Construction of $R^{4}$ terms in $\mathcal{N}=2$ $D=8$ superspace,” Nucl. Phys. B 514 (1998) 191–203, arXiv:hep-th/9709116.
  * [9] B. Pioline, “A note on non-perturbative $R^{4}$ couplings,” Phys. Lett. B431 (1998) 73–76, arXiv:hep-th/9804023.
  * [10] M. B. Green and S. Sethi, “Supersymmetry constraints on type IIB supergravity,” Phys. Rev. D59 (1999) 046006, arXiv:hep-th/9808061.
  * [11] N. A. Obers and B. Pioline, “Eisenstein series and string thresholds,” Commun. Math. Phys. 209 (2000) 275–324, arXiv:hep-th/9903113.
  * [12] M. B. Green and P. Vanhove, “The low energy expansion of the one-loop type II superstring amplitude,” Phys. Rev. D61 (2000) 104011, arXiv:hep-th/9910056.
  * [13] D. Kazhdan, B. Pioline, and A. Waldron, “Minimal representations, spherical vectors, and exceptional theta series. I” Commun. Math. Phys. 226 (2002) 1–40, hep-th/0107222.
  * [14] A. Basu and S. Sethi, “Recursion Relations from Space-time Supersymmetry,” JHEP 09 (2008) 081, arXiv:0808.1250 [hep-th].
  * [15] M. B. Green and P. Vanhove, “Duality and higher derivative terms in M theory,” JHEP 0601 (2006) 093, arXiv:hep-th/0510027 [hep-th].
  * [16] B. Pioline, “$R^{4}$ couplings and automorphic unipotent representations,” JHEP 03 (2010) 116, arXiv:1001.3647 [hep-th].
  * [17] M. B. Green, S. D. Miller, and P. Vanhove, “Small representations, string instantons, and Fourier modes of Eisenstein series,” J. Number Theor. 146 (2015) 187–309, arXiv:1111.2983 [hep-th].
  * [18] G. Bossard and V. Verschinin, “Minimal unitary representations from supersymmetry,” JHEP 1410 (2014) 008, arXiv:1406.5527 [hep-th].
  * [19] G. Bossard and V. Verschinin, “$\mathcal{E}\nabla^{4}R^{4}$ type invariants and their gradient expansion,” JHEP 03 (2015) 089, arXiv:1411.3373 [hep-th].
  * [20] H. P. A. Gustafsson, A. Kleinschmidt, and D. Persson, “Small automorphic representations and degenerate Whittaker vectors,” arXiv:1412.5625 [math.NT].
  * [21] G. Bossard and V. Verschinin, “The two $\nabla^{6}$ R4 type invariants and their higher order generalisation,” JHEP 07 (2015) 154, arXiv:1503.04230 [hep-th].
  * [22] D. Gourevitch, H. P. A. Gustafsson, A. Kleinschmidt, D. Persson, and S. Sahi, “Fourier coefficients of minimal and next-to-minimal automorphic representations of simply-laced groups,” Can. J. Math. 74 no. 1, (2022) 122–169, arXiv:1908.08296 [math.NT].
  * [23] M. F. Paulos, J. Penedones, J. Toledo, B. C. van Rees, and P. Vieira, “The S-matrix bootstrap II: two dimensional amplitudes,” JHEP 11 (2017) 143, arXiv:1607.06110 [hep-th].
  * [24] M. F. Paulos, J. Penedones, J. Toledo, B. C. van Rees, and P. Vieira, “The S-matrix bootstrap. Part III: higher dimensional amplitudes,” JHEP 12 (2019) 040, arXiv:1708.06765 [hep-th].
  * [25] J. Elias Miró, A. L. Guerrieri, A. Hebbar, J. a. Penedones, and P. Vieira, “Flux Tube S-matrix Bootstrap,” Phys. Rev. Lett. 123 no. 22, (2019) 221602, arXiv:1906.08098 [hep-th].
  * [26] A. Guerrieri, J. Penedones, and P. Vieira, “Where Is String Theory in the Space of Scattering Amplitudes?,” Phys. Rev. Lett. 127 no. 8, (2021) 081601, arXiv:2102.02847 [hep-th].
  * [27] A. Guerrieri, H. Murali, J. Penedones, and P. Vieira, “Where is M-theory in the space of scattering amplitudes?,” JHEP 06 (2023) 064, arXiv:2212.00151 [hep-th].
  * [28] S. R. Coleman and J. Mandula, “All Possible Symmetries of the S Matrix,” Phys. Rev. 159 (1967) 1251–1256.
  * [29] S. O. Aks, “Proof that scattering implies production in quantum field theory,” J. Math. Phys.  6, no.4, 516-532 (1965).
  * [30] A. Antónes, M. S. Costa and J. Pereira, “Exploring Inelasticity in the S-Matrix Bootstrap,” arXiv:2301.13219 [hep-th].
  * [31] M. J. Duff, J. T. Liu, and R. Minasian, “Eleven-dimensional origin of string-string duality: A One loop test,” Nucl. Phys. B 452 (1995) 261–282, arXiv:hep-th/9506126.
  * [32] E. Witten, “Five-brane effective action in M theory,” J. Geom. Phys. 22 (1997) 103–133, arXiv:hep-th/9610234.
  * [33] H.-C. Kim, G. Shiu, and C. Vafa, “Branes and the Swampland,” Phys. Rev. D 100 no. 6, (2019) 066006, arXiv:1905.08261 [hep-th].
  * [34] A. L. Guerrieri, J. Penedones, and P. Vieira, “S-matrix bootstrap for effective field theories: massless pions,” JHEP 06 (2021) 088, arXiv:2011.02802 [hep-th].
  * [35] E. Kiritsis and B. Pioline, “On $R^{4}$ threshold corrections in type IIB string theory and (p,q) string instantons,” Nucl. Phys. B508 (1997) 509–534, arXiv:hep-th/9707018.
  * [36] M. B. Green, J. G. Russo, and P. Vanhove, “Automorphic properties of low energy string amplitudes in various dimensions,” Phys.Rev. D81 (2010) 086008, arXiv:1001.2535 [hep-th].
  * [37] R. Rankin, “A minimum problem for the Epstein zeta function,” Glasg. Math. Assoc. no. 1, (1953) 149–158.
  * [38] P. Sarnak and A. Strömbergsson, “Minima of Epstein’s Zeta function and heights of flat tori,” Invent. math no. 165, (2006) 115–151.
  * [39] S. Ryshkov, “On the question of final $\zeta$-optimality of lattices providing the closest lattice packing of $n$-dimensional spheres,” Sib. Math. J. no. 14, (1974) 743–750.
  * [40] S. Caron-Huot, Y.-Z. Li, J. Parra-Martinez, and D. Simmons-Duffin, “Causality constraints on corrections to Einstein gravity,” JHEP 05 (2023) 122, arXiv:2201.06602 [hep-th].
  * [41] M. B. Green, J. G. Russo, and P. Vanhove, “String theory dualities and supergravity divergences,” JHEP 1006 (2010) 075, arXiv:1002.3805 [hep-th].
  * [42] G. Bossard and A. Kleinschmidt, “Supergravity divergences, supersymmetry and automorphic forms,” JHEP 08 (2015) 102, arXiv:1506.00657 [hep-th].
  * [43] C. M. Hull and P. K. Townsend, “Unity of superstring dualities,” Nucl. Phys. B438 (1995) 109–137, hep-th/9410167.
  * [44] H. M. A. Speiser and H. Weyl, “Gesammelte Abhandlungen von Hermann Minkowski. Unter Mitwirkung von Andreas Speiser und Hermann Weyl herausgegeben von David Hilbert.” Leipzig u. Berlin: B. G. Teubner. gr. $8^{\circ}$, 1911.
  * [45] D. Grenier, “Fundamental domains for the general linear group,” Pac. J. Math. 132 no. 2, (1988) 293–317.
  * [46] D. H. Peterson and K. Kac, “Infinite flag varieties and conjugacy theorems,” Proc. Nat. Acad. Sci. U.S.A. 80 (1983) 1778–1782.
  * [47] J. Cassels, “On a problem of Rankin about the Epstein zeta function,” Glasg. Math. Assoc. no. 4, (1963) 73–80.
  * [48] P. Epstein, “Theorie allgemeiner Zetafunctionen, II.,” Math. Ann. no. 63, (1907) 205–216.
  * [49] J. Conway and N. Sloane, Sphere Packings, Lattices and Groups.  Springer, New York, 1999.
  * [50] A. Terras, “On the minima of quadratic forms and the behaviour of the Epstein and Dedekind Zeta functions,” Journal of Number Theory no. 12, (1980) 258–272.
  * [51] H. Cohn, A. Kumar, S. Miller, D. Radchenko, and M. Viazovska, “On the minima of quadratic forms and the behaviour of the Epstein and Dedekind Zeta functions,” Annals of mathematics 196 no. 3, (2022) 983–1082, arXiv:1902.05438 [math.MG].
  * [52] E. Dade, “The maximal finite groups of $4\times 4$ integral matrices,” Illinois J. Math. 9 no. 1, (1965) 99.
  * [53] W. Plesken and M. Pohst, “On Maximal Finite Irreducible Subgroups of $GL(n,\mathds{Z})$: I. The five and seven dimensional cases.,” Mathematics of Computation 31 no. 138, (1977) 536–551.
  * [54] W. Plesken and M. Pohst, “On Maximal Finite Irreducible Subgroups of $GL(n,\mathds{Z})$: V. The eight-dimensional case and a complete description of dimensions less than ten.,” Mathematics of Computation 34 no. 149, (1980) 277.