# Ideal RSK and the directed landscape

Duncan Dauvergne  Bálint Virág  Duncan Dauvergne and Bálint Virág

# The directed landscape from Brownian motion

Duncan Dauvergne  Bálint Virág  Duncan Dauvergne and Bálint Virág

###### Abstract

We define an almost sure bijection which constructs the directed landscape
from a sequence of infinitely many independent Brownian motions. This is the
analogue of the RSK correspondence in this setting. The Brownian motions arise
as a marginal of the extended Busemann process for the directed landscape, and
the inverse map gives an explicit and natural coupling where Brownian last
passage percolation converges in probability to the directed landscape. We use
this map to prove that the directed landscape on a strip can be reconstructed
from the Airy line ensemble. Along the way, we describe two more new versions
of RSK in the semi-discrete setting, build a general theory of sorting via
Pitman operators, and construct extended Busemann processes for the directed
landscape and Brownian last passage percolation.

###### Contents

  1. 1 Introduction
    1. 1.1 Multi-path LPP and functional RSK
    2. 1.2 The first limit: RSK for functions $f:\mathbb{R}\to\mathbb{R}^{n}$
    3. 1.3 The second limit: RSK for functions $f\in\mathcal{C}^{\mathbb{N}}(\mathbb{R})$
    4. 1.4 The final limit: RSK for the directed landscape
    5. 1.5 Future research directions
    6. 1.6 Background and related work
  2. 2 Preliminaries
    1. 2.1 Basics of last passage percolation
    2. 2.2 Shape and continuity bounds for Brownian LPP
    3. 2.3 The directed landscape
  3. 3 The double sorting monoid and RSK on $\mathcal{C}^{n}(\mathbb{R})$
    1. 3.1 An abstract theory of sorting
    2. 3.2 $\mathfrak{D}_{n}$-actions and Pitman operators
    3. 3.3 Sorting and last passage percolation
    4. 3.4 Burke theorems
  4. 4 RSK on $\mathcal{C}^{\mathbb{N}}(\mathbb{R})$: From Pitman to Busemann
    1. 4.1 Multi-path Busemann functions
    2. 4.2 The law of the multi-path Busemann process
    3. 4.3 The Busemann shear
  5. 5 RSK for the directed landscape
    1. 5.1 The extended stationary horizon and the directed landscape
    2. 5.2 RSK for the directed landscape
    3. 5.3 Single-slit and double-slit Busemann functions
    4. 5.4 From multi-path to restricted Busemann functions
    5. 5.5 Optimizers converging to rays

##  1 Introduction

The Kardar-Parisi-Zhang (KPZ) universality class is a collection of one-
dimensional random growth models and two-dimensional random metrics that are
expected to have the same limiting behaviour under rescaling. Over the past
thirty years, our understanding of this class has improved dramatically thanks
to the discovery of a handful of exactly solvable models. The directed
landscape was constructed in [DOV22] as the full scaling limit of one of these
models, Brownian last passage percolation (LPP). More recently, other exactly
solvable last passage models [DV21b], the KPZ equation [Wu23] (see also
[Vir20, QS23]), and coloured ASEP and the stochastic six vertex model [ACH24]
have been shown to converge to the directed landscape. The directed landscape
is conjectured to be the full scaling limit of all KPZ models, including
models of planar first and last passage percolation with only weak
restrictions on the weights. See Section 1.6 for more background.

The directed landscape $\mathcal{L}$ is a random variable taking values in
$\mathcal{C}(\mathbb{R}^{4}_{\uparrow})$, the space of continuous functions
from

$\mathbb{R}^{4}_{\uparrow}=\\{u=(p;q)=(x,s;y,t)\in\mathbb{R}^{4}:s<t\\}$

to $\mathbb{R}$ with the compact topology (i.e. the topology of uniform-on-
compact convergence). The construction in [DOV22] builds the directed
landscape from its two-dimensional marginal the Airy sheet
$\mathcal{S}(x,y):=\mathcal{L}(x,0;y,1)$ in an analogous way to how Brownian
motion is built from the normal distribution. The Airy sheet is in turn built
as a complicated function of the Airy line ensemble, a sequence of paths
$\mathcal{A}_{i}:\mathbb{R}\to\mathbb{R},i\in\mathbb{N}$ which is in turn
defined via a determinantal formula111Though note that the Airy line ensemble
has recently been given a more satisfying probabilistic characterization, see
[AH23].. As one of the highlights of this paper, we give an alternate
construction of the directed landscape through a simpler and more classical
object: independent Brownian motions.

Our construction is an almost sure bijection mapping a sequence of independent
two-sided Brownian motions $B:=(B_{i}:i\in\mathbb{N})$ to the directed
landscape $\mathcal{L}$ restricted to the lower half-plane
$\mathbb{H}^{2}_{\uparrow}=\\{(x,s;y,t)\in\mathbb{R}^{4}:s<t\leq 0\\}$. Here
and throughout the paper, our Brownian motions will have variance $2$, as is
the convention for KPZ limits. The map taking
$\mathcal{L}|_{\mathbb{H}^{2}_{\uparrow}}$ to $B$ has a more natural geometric
definition, so we use this map to state our main theorem, even though the map
taking $\mathcal{L}|_{\mathbb{H}^{2}_{\uparrow}}$ to $B$ is ultimately more
interesting. The paths $B_{i},i\in\mathbb{N}$ are defined from $\mathcal{L}$
through the following multi-path Busemann function definition:

$\sum_{i=1}^{k}B_{i}(x)=\lim_{t\to-\infty}\mathcal{L}(0^{k},-t;x^{k},0)-\mathcal{L}^{k}(0^{k},-t;0^{k},0).$
(1)

Here we write $\mathcal{L}(x^{k},s;y^{k},t)$ for the maximal length in
$\mathcal{L}$ of a collection of $k$ disjoint paths $\pi_{1},\dots,\pi_{k}$
from $(x,s)$ to $(y,t)$, see Section 1.4 for a more detailed definition.

######  Theorem 1.1.

The environment $B$ defined by the map in (1) is a sequence of independent
two-sided Brownian motions. Moreover, there is an explicit inverse map that
recovers $\mathcal{L}|_{\mathbb{H}^{2}_{\uparrow}}$ from $B$ almost surely.

The inverse map in Theorem 1.1 can loosely be described in two steps:

  * •

First, for every $a\in\mathbb{R}$ we construct a new environment of
independent two-sided Brownian motions $B^{a}=(B^{a}_{i},i\in\mathbb{N})$ of
drift $a$ by looking at multi-path Brownian LPP Busemann functions in the
environment $B$, in a certain direction parametrized by $a$.

  * •

By the main theorem of [DOV22] (see Theorem 1.6), there is a natural rescaling
of the environments $B^{a}$ so that they converge to
$\mathcal{L}|_{\mathbb{H}^{2}_{\uparrow}}$ distribution as $a\to-\infty$. It
turns out that convergence also happens in probability, and hence recovers
$\mathcal{L}|_{\mathbb{H}^{2}_{\uparrow}}$ from $B$.

The reader may wonder about the restriction of $\mathcal{L}$ to the lower
half-plane. By symmetry, we can also define $\mathcal{L}$ on the upper half-
plane from a Brownian environment, and hence by patching these constructions
together construct $\mathcal{L}$ on the full plane from a bi-infinite sequence
of independent Brownian motions.

The map in Theorem 1.1 is a version of the Robinson-Schensted-Knuth (RSK)
correspondence in the scaling limit, where $\mathcal{L}$ corresponds to the
integer-valued matrix in classical RSK and $B$ corresponds to the pair of
Young tableaux. This RSK perspective is what drives the whole paper, and very
roughly, we will obtain Theorem 1.1 by passing a classical version of RSK
through _three_ limit transitions. In the remainder of the introduction, we
will describe each of these limits in detail.

###  1.1 Multi-path LPP and functional RSK

To introduce the RSK correspondence, we need to first define multi-path LPP
across a functional environment. Consider a continuous function
$f:\mathbb{R}\to\mathbb{R}^{I}$, where $I\subset\mathbb{Z}$ is an interval.
For a nonincreasing right-continuous function $\pi:[x,y]\to\\{m,\dots,n\\}$
(henceforth a path from $(x,n)$ to $(y,m)$) define its length with respect to
$f$ by

$\|\pi\|_{f}=\sum_{i=m}^{n}f_{i}(t_{i-1})-f_{i}(t_{i})$ (2)

where $t_{i}=\inf\\{t\in[x,y]:\pi_{i}(t)\leq i\\}$. We then define the last
passage value

$f[(x,n)\to(y,m)]=\max_{\pi:(x,n)\to(y,m)}\|\pi\|_{f},$ (3)

where the supremum is over all paths from $(x,n)$ to $(y,m)$. Last passage
percolation (LPP) is best thought of as a kind of directed metric on the set
$\mathbb{R}\times I$ with distances distorted by the environment $f$, and
where we maximize rather than minimize path length. With this perspective in
mind, paths that achieve the maximum in (3) are called geodesics. We also need
to define multi-path last passage values. First, for a linearly ordered set
$X$, we write

$X^{k}_{\leq}=\\{(x_{1},\dots,x_{k})\in X^{k}:x_{1}\leq x_{2}\leq\cdots\leq
x_{k}\\},$

and similarly define $X^{k}_{<},X^{k}_{\geq},X^{k}_{>}$. Consider
$\mathbf{p}=(\mathbf{x},\mathbf{n}),\mathbf{q}=(\mathbf{y},\mathbf{m})\in\mathbb{R}^{k}_{\leq}\times
I^{k}_{\leq}$. We say that $\pi=(\pi_{1},\dots,\pi_{k})$ is a disjoint
$k$-tuple from $\mathbf{p}$ to $\mathbf{q}$ if each $\pi_{i}$ is a path from
$(x_{i},n_{i})$ to $(y_{i},m_{i})$ and if $\pi_{i}(t)<\pi_{i+1}(t)$ for
$t\in(x_{i},y_{i})\cap(x_{i+1},y_{i+1})$. If there is at least one disjoint
$k$-tuple from $\mathbf{p}$ to $\mathbf{q}$, we can define the multi-path last
passage value

$f[\mathbf{p}\to\mathbf{q}]=\sup_{\pi:\mathbf{p}\to\mathbf{q}}\sum_{i=1}^{k}\|\pi_{i}\|_{f},$

where the supremum is over all disjoint $k$-tuples from $\mathbf{p}$ to
$\mathbf{q}$. We call a $k$-tuple achieving the above supremum a (disjoint)
optimizer. To simplify the notation for multi-path last passage values in the
situations that occur most, we write $x^{k}:=(x,\dots,x)\in\mathbb{R}^{k}$.
Typically, we will consider multi-path last passage when all the points in
$\mathbf{p}$ lie on a common vertical or horizontal line (and similarly for
$\mathbf{q}$). In this case, we will write
$\mathbf{p}=(\mathbf{x},n):=(\mathbf{x},n^{k})$ and
$\mathbf{p}=(x,\mathbf{n}):=(x^{k},\mathbf{n})$. See Figure 1 for
illustrations of this definition.

$5$$4$$3$$2$$1$ Figure 1: A disjoint optimizer for $k=3$ from $((0,0,0.2),5)$
to $((0.7,0.9,1),1)$. Note that in our coordinate system, we view paths as
moving up and to the right across the page.

Via Greene’s theorem [Gre74], we can describe many classical versions of RSK
in terms of multi-path LPP across a continuous environment
$f:[a,b]\to\mathbb{R}^{n}$. Essentially, the RSK map takes $f$ to a pair of
environments $W^{U}f,W^{R}f$ which record multi-path last passage values from
the bottom corner $(a,n)$ to the upper (U) boundary $[a,b]\times\\{1\\}$ and
the right (R) boundary $\\{b\\}\times\\{1,\dots,n\\}$ of
$[a,b]\times\\{1,\dots,n\\}$, respectively. More precisely, letting
$T_{n}:=\\{(i,j)\in\\{1,\dots,n\\}^{2}:i\leq n-j+1\\}$, define two functions
$W^{U}f:[a,b]\to\mathbb{R}^{n}$ and
$W^{R}f:T_{n}\to\mathbb{R},(i,j)\mapsto(W^{R}f)_{i}(j)$ as follows:

$\displaystyle\sum_{i=1}^{k}(W^{U}f)_{i}(r)$
$\displaystyle=f[(a^{k},n)\to(x^{k},1)],\qquad$ $\displaystyle 1\leq k\leq
n,\;\;x\in[a,b].$ (4) $\displaystyle\sum_{i=1}^{k}(W^{R}f)_{i}(j)$
$\displaystyle=f[(a^{k},n)\to(x^{k},j)],\qquad$ $\displaystyle(k,j)\in T_{n}.$

The map $f\mapsto Wf:=(W^{U}f,W^{R}f)$ has many remarkable properties. We
highlight three that are particularly important for this paper:

Invertibility:

The RSK map $W$ is invertible on its image with an explicit inverse. Moreover,
its image is easy to describe: a pair $(h,g)$ equals $Wf$ for some continuous
$f$ if and only if $h:[a,b]\to\mathbb{R}^{n}$ is continuous function into the
ordered set $\mathbb{R}^{n}_{\leq}$ with $h(a)=0$, $g$ satisfies the Gelfand-
Tsetlin inequalities $g_{i}(j)\geq g_{i}(j+1)\geq g_{i+1}(j)$, and
$h(b)=g_{\cdot}(1)$. The inequalities in this description of the image imply
that $h,g$ can be viewed as path representations of Young tableaux, and the
condition $h(b)=g_{\cdot}(1)$ says that these tableaux have the same shape. By
restricting to certain classes of piecewise linear functions $f$ in our
framework we can recover classical matrix versions of RSK (i.e. the Robinson-
Schensted correspondence for permutations, usual RSK, dual RSK).

Measure Preservation:

The bijectivity of RSK implies that it maps nice measures to nice measures.
For example, if $a,b\in\mathbb{Z}$ and $f$ is an environment of independent
Bernoulli walks, then $W^{U}f$ consists of $n$ independent Bernoulli walks
conditioned to stay ordered. Similarly, if $B:[a,b]\to\mathbb{R}^{n}$ is an
environment of independent Brownian motions, then $W^{U}B$ consists of $n$
non-intersecting Brownian motions. There are similar interpretations for
$W^{R}$.

Isometry:

The map $W^{U}$ preserves bottom-to-top last passage values. More precisely,
we have the _boundary isometry_

$f[(\mathbf{x},n)\to(\mathbf{y},1)]=W^{U}f[(\mathbf{x},n)\to(\mathbf{y},1)]$
(5)

for all $f,\mathbf{x},\mathbf{y}$. Similarly, $W^{R}$ preserves left-to-right
passage values.

We refer the reader to [DNV22] for precise versions of the statements above
and a presentation of RSK in this framework, and [Ful97, Sta99] for more
classical presentations.

In this paper, we will take three successive limits of RSK so that at every
stage we have useful and interesting notions of invertibility, measure
preservation, and isometry. Our final limit of the RSK correspondence will
make explicit the function in Theorem 1.1.

###  1.2 The first limit: RSK for functions $f:\mathbb{R}\to\mathbb{R}^{n}$

In Section 3, we define an RSK map on the domain

$\mathcal{C}^{n}(\mathbb{R}):=\\{f:\mathbb{R}\to\mathbb{R}^{n}:\lambda(f):=\lim_{x\to\pm\infty}\frac{f(x)}{x}\text{
exists}\\}.$

This map is the limit of RSK on functions $f:[a,b]\times\\{1,\dots,n\\}$ where
we take $a\to-\infty,b\to\infty$. We restrict to functions with an asymptotic
slope for simplicity; the map could be defined on a larger space, but we will
not need this here. The motivation for taking this limit is that when we let
$[a,b]$ tend to $(-\infty,\infty)$, the RSK correspondence becomes simpler and
picks up additional symmetries. In particular, the inverse map in this setting
becomes a straightforward conjugation of the forward map.

Since our right boundary $\\{b\\}\times\\{1,\dots,n\\}$ is tending to
infinity, the information from $W^{R}f$ should disappear in this limit, and
the correspondence should now produce just a single function
$Wf=(Wf_{1},\dots,Wf_{n})$, which takes the place of $W^{U}f$. The corner
$(a,n)$ that played the key anchoring role in (4) also converges to
$(-\infty,n)$ in this limit. For this reason, we need to define last passage
from $-\infty$: for $\mathbf{m}\in\\{1,\dots,n\\}^{k}_{<}$, let

$f[(-\infty,\mathbf{m})\to(\mathbf{x},1)]:=\lim_{t\to-\infty}f[(t,\mathbf{m})\to(\mathbf{x},1)]+\sum_{i=1}^{k}f_{m_{i}}(t).$
(6)

This limit does not necessarily exist, but if we ask that
$f\in\mathcal{C}^{n}_{<}(\mathbb{R}):=\\{f\in\mathcal{C}^{n}(\mathbb{R}):\lambda(f)\in\mathbb{R}^{n}_{<}\\}$
then it is always will. With the above setup in place, we can now take the
limit of the RSK formula (4) to describe $Wf$ when
$f\in\mathcal{C}^{n}_{<}(\mathbb{R})$:

$\sum_{i=1}^{k}Wf_{i}(x)=f[(-\infty,(n,\dots,n-k+1))\to(x^{k},1)].$ (7)

With this definition, we have versions of invertibility, measure preservation,
and isometry.

######  Theorem 1.2.

The map $W$ in (7) has the following properties:

  1. 1.

(Invertibility) $W$ maps $\mathcal{C}^{n}_{<}(\mathbb{R})$ bijectively onto
$\mathcal{C}^{n}_{>}(\mathbb{R}):=\\{f\in\mathcal{C}^{n}(\mathbb{R}):\lambda(f)\in\mathbb{R}^{n}_{>}\\}$.
Moreover, the inverse map is given by
$RWR:\mathcal{C}^{n}_{>}(\mathbb{R})\to\mathcal{C}^{n}_{<}(\mathbb{R})$, where
$R:\mathcal{C}^{n}(\mathbb{R})\to\mathcal{C}^{n}(\mathbb{R})$ is the
reflection map $Rf(x)=f(-x)$.

  2. 2.

(Measure preservation) Let $\mu_{\lambda}$ denote the law on
$\mathcal{C}^{n}(\mathbb{R})$ of $n$ independent Brownian motions with drift
vector $\lambda$ and variance $2$. Then if $\lambda\in\mathbb{R}^{n}_{<}$ and
$B\sim\mu_{\lambda}$, then $WB-WB(0)\sim\mu_{\lambda^{*}}$ where
$\lambda^{*}=(\lambda_{n},\dots,\lambda_{1})$.

  3. 3.

(Isometry) The isometry (5) holds with $Wf$ in place of $W^{U}f$.

Parts of Theorem 1.2 are not completely new. Indeed, the isometry is
essentially immediate from the isometry in the finite setting, and the fact
that $RWR$ inverts $W$ is related to a similar description of the inverse RSK
map on functions $f:[0,\infty)\to\mathbb{R}^{n}$ given in [DNV22]. The
bijection $W$ turns out to also be the same as a certain queuing map described
in Sorensen’s Ph.D. thesis [Sor23], see Section 2.3.3 and Lemma 2.3.18
therein. The description in terms of multi-path LPP and the connection with
RSK is not discussed there.

When $n=2$, the measure preservation property in Theorem 1.2 is well-known:
this is one aspect of the so-called Brownian Burke theorem, first observed in
[HW90] and applied to LPP in [OY01]. To move from measure preservation for
$n=2$ to general $n$, we will build the $n$-line map by repeatedly applying
the $2$-line map to pairs of adjacent lines. This approach to RSK was first
developed in the closely related context of functions
$f:[0,\infty)\to\mathbb{R}^{n}$ by Biane, Bougerol, and O’Connell [BBO05],
building on work of [OY01, OY02, O’C03]. This approach was further studied in
[DOV22, DNV22]. We expand on these ideas here, and along the way describe a
whole family of useful and interesting maps on the space of functions
$\mathcal{C}^{n}(\mathbb{R})$ which generalize the maps $W$ and $RWR$. This
broader family will be crucial for understanding the next limit transition.
Each of these maps have nice invertibility, measure-preservation, and isometry
properties and are useful for studying different aspects and models of LPP.

To describe things more precisely, define the Pitman transform
$\mathcal{P}:\mathcal{C}^{2}(\mathbb{R})\to\mathcal{C}^{2}(\mathbb{R})$ by
letting $\mathcal{P}|_{\mathcal{C}^{2}_{<}(\mathbb{R})}$ be the $2$-line map
$W$ described above, and setting
$\mathcal{P}|_{\mathcal{C}^{2}_{\geq}(\mathbb{R})}=\text{id}$. Next, for
$i=1,\dots,n-1$, define sorting operators
$\tau_{i},\bar{\tau}_{i}:\mathbb{R}^{n}\to\mathbb{R}^{n}$ by

$\tau_{i}(x)=\begin{cases}x,\qquad&x_{i}\geq x_{i+1},\\\
(x_{1},\dots,x_{i+1},x_{i},\dots,x_{n}),\qquad&x_{i}<x_{i+1}\end{cases}$

and

$\bar{\tau}_{i}(x)=\begin{cases}x,\qquad&x_{i}\leq x_{i+1},\\\
(x_{1},\dots,x_{i+1},x_{i},\dots,x_{n}),\qquad&x_{i}>x_{i+1}.\end{cases}$

Equivalently, $\bar{\tau}_{i}=R\tau_{i}R$, where $Rx=-x$. Let
$\mathfrak{D}_{n}$ denote the monoid generated by the
$\tau_{i},\bar{\tau}_{i},i=1,\dots,n-1$. We then define operators
$\mathcal{P}_{\tau_{i}},\mathcal{P}_{\bar{\tau}_{i}}:\mathcal{C}^{n}(\mathbb{R})\to\mathcal{C}^{n}(\mathbb{R})$
by setting

$\mathcal{P}_{\tau_{i}}(f_{1},\dots,f_{n})=(f_{1},\dots,f_{i-1},\mathcal{P}(f_{i},f_{i+1}),f_{i+2},\dots,f_{n}),$

and letting $\mathcal{P}_{\bar{\tau}_{i}}=R\mathcal{P}_{\tau_{i}}R$. It turns
out that these definitions extend to an action of the whole monoid
$\mathfrak{D}_{n}$. For an arbitrary element
$\sigma=\pi_{1}\cdots\pi_{k}\in\mathfrak{D}_{n}$ where
$\pi_{i}\in\\{\tau_{i},\bar{\tau}_{i},i=1,\dots,n-1\\}$, we can define
$\mathcal{P}_{\sigma}=\mathcal{P}_{\pi_{1}}\cdots\mathcal{P}_{\pi_{k}}$; this
definition is independent of the choice of the decomposition
$\pi_{1}\cdots\pi_{k}$ of $\sigma$, and we have the following theory for this
monoid action, which can be viewed as a generalization of Theorem 1.2.

######  Theorem 1.3.

The maps $\mathcal{P}_{\sigma},\sigma\in\mathcal{D}_{n}$ have the following
properties.

  1. 1.

(Invertibility via last passage) Let $f\in\mathcal{C}^{n}_{\leq}(\mathbb{R})$.
Let $O(f)$ denote the orbit of $f$ under the action of
$\mathcal{P}_{\sigma},\sigma\in\mathfrak{D}_{n}$ and let $O(\lambda(f))$
denote the orbit of $\lambda(f)$ under the action of $\mathfrak{D}_{n}$. Then
the map $g\mapsto\lambda(g)$ is a bijection from $O(f)$ to $O(\lambda(f))$ and
$\lambda\circ\mathcal{P}_{\sigma}=\sigma\circ\lambda$ as functions from
$O(f)\to O(\lambda(f))$. Moreover, if $g\in O(f)$, then for all
$x\in\mathbb{R},k\in\\{1,\dots,n\\}$ we have

$\sum_{i=1}^{k}g_{i}(x)=f[(-\infty,\mathbf{m}^{k,g})\to(x^{k},1)],$

where $\mathbf{m}^{k,g}\in\\{1,\dots,n\\}^{k}_{<}$ is the minimal vector such
that as multi-sets,

$\\{\lambda(g)_{1},\dots,\lambda(g)_{k}\\}=\\{\lambda(f)_{\mathbf{m}^{k,g}_{1}},\dots,\lambda(f)_{\mathbf{m}^{k,g}_{k}}\\}.$

  2. 2.

(Measure preservation) If $\lambda\in\mathbb{R}^{n}$ and $B\sim\mu_{\lambda}$,
then
$\mathcal{P}_{\sigma}B-\mathcal{P}_{\sigma}B(0)\sim\mu_{\sigma(\lambda)}$.

  3. 3.

(Isometry) The isometry (5) holds with $\mathcal{P}_{\sigma}f$ in place of
$W^{U}f$.

Theorem 1.3 can be interpreted as saying that given an environment $f$, we can
build a family of boundary isometric environment $\mathcal{P}_{\sigma}f$ which
permute the slopes of the lines of $f$ in different ways. We can access
different information about last passage values across $f$ by studying
different elements in this family. Theorem 1.3 is proven in the text as a
combination of Corollary 3.5, Lemma 3.6, and Proposition 3.10. The special
case of Theorem 1.2 is given in Corollary 3.12.

###  1.3 The second limit: RSK for functions
$f\in\mathcal{C}^{\mathbb{N}}(\mathbb{R})$

Next, we take a limit of RSK on $\mathcal{C}^{n}(\mathbb{R})$ as $n\to\infty$.
This is the goal of Section 4. This limit naturally results in Busemann
functions for Brownian LPP, foreshadowing the description of the maps in
Theorem 1.1. Let
$B=(B_{i},i\in\mathbb{N})\in\mathcal{C}^{\mathbb{N}}(\mathbb{R})$ be an
environment of independent two-sided Brownian motions with no drift. For
$\theta\in[0,\infty)^{k}_{\leq}$ and $\mathbf{x}\in\mathbb{R}^{k}_{\leq}$
define the multi-path Busemann function

$\mathcal{B}^{\theta}(\mathbf{x};B)=\lim_{t\to-\infty}B[(t,{\left\lfloor\theta|t|\right\rfloor}+k)\to(\mathbf{x},1)]-N_{\theta}(t)$
(8)

Here the notation ${\left\lfloor\theta t\right\rfloor}$ should be understood
coordinatewise: ${\left\lfloor\theta
t\right\rfloor}=({\left\lfloor\theta_{1}t\right\rfloor},\dots,{\left\lfloor\theta_{k}t\right\rfloor})$.
We use similar coordinatewise notation throughout the paper. We have added
$+k$ above to ensure that the Busemann function is well-defined even if
$\theta=0^{k}$. The function $N_{\theta}(t)$ is a normalization term needed in
order to ensure that the limit (8) exists. There are a couple of different
choices for this normalization term; we choose the normalization that retains
the most information. Letting $\hat{\theta}\in[0,\infty)^{m}_{<}$ be uniquely
chosen so that
$\theta=(\hat{\theta}_{1}^{\ell_{1}},\dots,\hat{\theta}_{m}^{\ell_{m}})$, set

$N_{\theta}(t):=\sum_{j=1}^{m}B[(t,\lfloor\hat{\theta}_{i}^{\ell_{i}}|t|\rfloor+k)\to(0^{\ell_{i}},1)],$

where the operation
$\hat{\theta}_{i}^{\ell_{i}}\mapsto\lfloor\hat{\theta}_{i}^{\ell_{i}}|t|\rfloor+k$
should again be understood coordinatewise. Busemann functions are closely
linked to the study of semi-infinite optimizers. A semi-infinite optimizer in
direction $\theta$ ending at $(\mathbf{x},1)$ is a $k$-tuple
$\pi=(\pi_{1},\dots,\pi_{k})$ such that
$\pi_{i}:(-\infty,x_{i}]\to\mathbb{N}^{k}$, $\pi(t)/t\to\theta$ as
$t\to-\infty$ and such that $\pi|_{[y,x_{k}]}$ is an optimizer ending at
$(\mathbf{x},1)$ for any $y<x_{1}$. A semi-infinite optimizer with one path is
called a semi-infinite geodesic.

The single-path Busemann process and semi-infinite geodesics in Brownian LPP
have been extensively studied in recent years. The state-of-the-art results
are due to Seppäläinen and Sorensen [SS23b], building on [ARAS20, SS23a]. They
showed that there is a random countable set $\Theta\subset[0,\infty)$ such
that for $\theta\notin\Theta$, the limit (8) exists for all $x\in\mathbb{R}$
and the process $(\theta,x)\mapsto\mathcal{B}^{\theta}(x;B)$ is continuous in
both $x$ and $\theta$ on $\mathbb{R}\times[0,\infty)\setminus\Theta$.
Moreover, semi-infinite geodesics exist ending at all points and in all
directions $\theta$, and for $\theta\notin\Theta$, all semi-infinite geodesics
in direction $\theta$ eventually coalesce. We use these results to help build
an analogous toolkit for working with multi-path Busemann functions for
Brownian LPP, see Section 4.1 for details.

Now let us return to the problem of defining a limit for the RSK
correspondence on $\mathcal{C}^{n}(\mathbb{R})$ as $n\to\infty$. Consider the
Brownian environment $B$ as above, and let
$B^{\prime}\in\mathcal{C}^{\mathbb{N}}(\mathbb{R})$ be an independent Brownian
environment, where each $B^{\prime}_{i}$ has drift $a>0$. For each
$n\in\mathbb{N}$, let
$W^{n}=\mathcal{P}_{\sigma_{n}}(B_{1},\dots,B_{n},B_{1}^{\prime},\dots,B_{n}^{\prime})$,
where $\sigma_{n}$ is chosen so that the slopes are reversed, i.e.
$\lambda(W^{n})=(a^{n},0^{n})$. By Theorem 1.3.2,
$W^{n}-W^{n}(0)\sim\mu_{(a^{n},0^{n})}$. In particular, $W^{n}-W^{n}(0)$
converges in law as $n\to\infty$ to an environment
$B^{a}\in\mathcal{C}^{\mathbb{N}}(\mathbb{Z})$ of infinitely many independent
Brownian motions with slope $a$. It turns out that this convergence also
happens almost surely, and that $B^{a}$ is described purely in terms of
Busemann functions for the unsloped environment $B$; the dependence on
$B^{\prime}$ disappears in the limit. We have now defined a collection of maps
indexed by $a>0$ that play the role of RSK on
$\mathcal{C}^{\mathbb{N}}(\mathbb{R})$. It turns out they are invertible,
measure-preserving, and naturally satisfy a Busemann isometry.

To make things more precise, define
$\mathcal{W}^{\lambda}(\mathbf{x};B):=\mathcal{B}^{\lambda|\lambda|/2}(\mathbf{x};B),$
which parametrizes Busemann functions by the asymptotic slope of the function
$\mathbf{x}\mapsto\mathcal{W}^{\lambda}(\mathbf{x};B)$, rather than the
Busemann direction. For $a\geq 0$ we can alternately define
$B^{a}\in\mathcal{C}^{\mathbb{N}}(\mathbb{R})$ by the formula

$\sum_{i=1}^{k}B^{a}_{i}(x)=\mathcal{W}^{a^{k}}(x^{k};B),\qquad
k\in\mathbb{N}.$ (9)

We also build environments for $a<0$. First, for an environment $f$, define
$Rf(x)=f(-x)$, and for $\mathbf{x}\in\mathbb{R}^{k}_{\leq}$, let
$-\mathbf{x}=(-x_{k},\dots,-x_{1})\in\mathbb{R}^{k}_{\leq}$. For
$\theta\in(-\infty,0]^{k}_{\leq},\mathbf{x}\in\mathbb{R}^{k}_{\leq}$, define

$\mathcal{W}^{\theta}(\mathbf{x};B)=\mathcal{B}^{\theta|\theta|/2}(\mathbf{x};B):=\mathcal{B}^{-\theta|\theta|/2}(-\mathbf{x};RB),\qquad$

See Figure 2 for an illustration of this definition when
$\theta\in(-\infty,0)$. Using this definition, we can understand formula (9)
for arbitrary $a\in\mathbb{R}$. The full suite of RSK transformations
$B\mapsto B^{a},a\in\mathbb{R}$ exhibits a group structure, and acts on
Busemann functions via a simple parameter translation.

######  Theorem 1.4.

Let $B=(B_{i},i\in\mathbb{N})$ be an environment of independent two-sided
Brownian motions with zero drift. Then:

  1. 1.

(Invertibility and group structure) For any $a,b\in\mathbb{R}$, almost surely:

$B^{0}=B,\qquad(B^{a})^{-a}=B,\qquad(B^{a})^{b}=B^{a+b}.$

  2. 2.

(Measure preservation) For any $a\in\mathbb{R}$, $B^{a}$ is a sequence of
independent Brownian motions of drift $a$.

  3. 3.

(Busemann isometry) Fix $a\in\mathbb{R}$ and
$\lambda\in(-\infty,0]^{k}_{\leq}\cup[0,\infty)^{k}_{\leq}$. Suppose also that
$\lambda+a\in(-\infty,0]^{k}_{\leq}\cup[0,\infty)^{k}_{\leq}$. Then a.s. for
all $\mathbf{x}\in\mathbb{R}^{k}_{\leq}$ we have

$\mathcal{W}^{\lambda+a}(\mathbf{x};B)=\mathcal{W}^{\lambda}(\mathbf{x};B^{a}).$

Theorem 1.4.3 also allows us to define the function
$\mathcal{W}^{\lambda}(\mathbf{x};B)$ when $\lambda\in\mathbb{R}^{k}_{\leq}$
but possibly has coordinates of both signs: we simply set
$\mathcal{W}^{\lambda}(\mathbf{x};B)=\mathcal{W}^{\lambda-\lambda_{1}}(\mathbf{x},B^{-\lambda_{1}})$.
Theorem 1.4 is proven in the text as Theorem 4.12.

We can also take different limits of the RSK correspondence on
$\mathcal{C}^{n}(\mathbb{R})$ that result in new representations for the
multi-path Busemann process for $B$. More precisely, let
$\theta\in[0,\infty)^{k}_{\leq}$ and let $B^{\prime}\sim\mu_{\theta}$. Let the
transform $\mathcal{P}_{\sigma_{n}},\sigma_{n}\in\mathfrak{D}_{n+k}$ be chosen
so that $W^{n}:=\mathcal{P}_{\sigma}(B_{1},\dots,B_{n},B^{\prime})$ satisfies
$\lambda(W^{n})=(\theta,0^{n})$. Again, the maps $W^{n}-W^{n}(0)$ have an
almost sure limit $W$ as $n\to\infty$ which comes from the Busemann process
for $B$. The next theorem describes this limit.

######  Theorem 1.5.

Let $\theta\in[0,\infty)^{k}_{\leq}$, and define
$W=(W_{1},\dots,W_{k}):\mathbb{R}\to\mathbb{R}^{k}$ by the formula:

$\sum_{i=1}^{\ell}W_{i}(x)=\mathcal{W}^{(\theta_{1},\dots,\theta_{\ell})}(x^{\ell};B),\qquad
1\leq\ell\leq k.$

Then $W-W(0)\sim\mu_{\theta}$. Moreover, consider any
$\mathbf{n}\in\\{1,\dots,k\\}^{\ell}_{<}$ for some $\ell\leq k$ and suppose
that $\mathbf{n}\leq\mathbf{m}$ for any
$\mathbf{m}\in\\{1,\dots,k\\}^{\ell}_{<}$ with $\theta_{n_{i}}=\theta_{m_{i}}$
for all $i$. Then almost surely, for all
$\mathbf{x}\in\mathbb{R}^{\ell}_{\leq}$ we have

$\mathcal{B}^{(\theta_{n_{1}},\dots,\theta_{n_{\ell}})}(\mathbf{x};B)=W[(-\infty,\mathbf{n})\to(\mathbf{x},1)].$
(10)

The identity (10) may look familiar to the reader in the special case when
$\mathbf{n}$ is a singleton. Indeed, as part of their comprehensive study of
Brownian Busemann functions, Seppäläinen and Sorensen [SS23b] showed that
given $\theta\in[0,\infty)^{k}_{<}$, there exists an environment
$\tilde{W}\sim\mu_{\theta}$ such that the following identity holds in
distribution, as functions of $(x,i)\in\mathbb{R}\times\\{1,\dots,k\\}$.

$\tilde{W}[(-\infty,i)\to(x,1)]-\tilde{W}[(-\infty,i)\to(0,1)]\stackrel{{\scriptstyle
d}}{{=}}\mathcal{W}^{\theta_{i}}(x;B)$ (11)

One upshot of Theorem 1.5 is that we realize this as an _almost sure identity_
, naturally constructing $\tilde{W}$ in terms of $B$. A multi-path almost sure
approach to the identity (11) was previously suggested in [Dau23b, Remark
1.3.4] and developed there in the context of the Airy sheet. Theorem 1.5 is
proven in the text as Theorem 4.9.

16cm

Figure 2: Semi-infinite geodesics in $B$, indexed by the direction
$\theta\in\mathbb{R}$. To make sense of the direction when $\theta<0$, we look
along down-right paths, or equivalently, paths in the reversed environment.
Figure 3: Semi-infinite geodesics in $\mathcal{L}$. The colouring of paths in
Figures 2 and 3 is chosen so that the start points and directions match in the
two pictures under the version of the RSK correspondence in Theorem 1.7.

###  1.4 The final limit: RSK for the directed landscape

At this point, we have constructed analogues of the RSK correspondence on an
infinite line environment on $\mathbb{R}\times\mathbb{N}$ indexed by
$a\in\mathbb{R}$. We can make one final limiting transition. This transition
can be either viewed through taking $a\to\pm\infty$ in Theorem 1.4, or
equivalently by decreasing the spacing between lines to $0$, in a manner that
takes Brownian LPP to the directed landscape. This is the goal of Section 5.
We start by recalling the main theorem of [DOV22], which defines the directed
landscape as the scaling limit of Brownian LPP.

######  Theorem 1.6 (Theorem 1.5, [DOV22]).

For every $a\in\mathbb{R}$, let $B^{a}\in\mathcal{C}^{\mathbb{Z}}(\mathbb{R})$
be an environment of independent two-sided Brownian motions of common drift
$a$. Let $(x,s)_{a}=(x-as/4,\lfloor sa^{3}/8\rfloor+1)$. Then as
$a\to-\infty$,

$\mathcal{L}^{a}(x,s;y,t):=B^{a}[(x,s)_{a}\to(y,t)_{a}]-\frac{a^{2}}{4}(t-s)\stackrel{{\scriptstyle
d}}{{\to}}\mathcal{L}(x,s;y,t).$

In Theorem 1.6, the convergence in distribution is in the compact topology on
$\mathcal{C}(\mathbb{R}^{4}_{\uparrow})$. Just as with LPP, the directed
landscape is best thought of as assigning distances to pairs of points
$p=(x,s),q=(y,t)$. The value $\mathcal{L}(p;q)$ is best thought of as a
distance between two points $p$ and $q$ in the space-time plane, and indeed,
it satisfies a reverse triangle inequality

$\mathcal{L}(x,s;y,t)\geq\mathcal{L}(x,s;z,r)+\mathcal{L}(z,r;y,t),$ (12)

just like LPP. Unlike a usual metric, $\mathcal{L}$ is not symmetric, does not
assign distances to every pair of points in the plane, and may take negative
values.

We define the analogue of RSK for $\mathcal{L}$ by modifying the Busemann
definition (9) for the limiting context. To set things up properly we need to
define path lengths, geodesics, and optimizers in the directed landscape. For
a continuous function $\pi:[s,t]\mapsto\mathbb{R}$, referred to as a path, let
$\bar{\pi}(r)=(\pi(r),r)$. Following [DOV22, Section 12], define the length of
$\pi$ by

$\|\pi\|_{\mathcal{L}}=\inf_{k\in\mathbb{N}}\inf_{s=t_{0}<t_{1}<\ldots<t_{k}=t}\sum_{i=1}^{k}\mathcal{L}(\bar{\pi}(t_{i-1});\bar{\pi}(t_{i}))\,.$
(13)

Next, for $s<t$ and $\mathbf{x},\mathbf{y}\in\mathbb{R}^{k}_{\leq}$, define
the extended landscape value

$\mathcal{L}(\mathbf{x},s;\mathbf{y},t)=\max_{\pi=(\pi_{1},\dots,\pi_{k})}\sum_{i=1}^{k}\|\pi_{i}\|_{\mathcal{L}},$
(14)

where the maximum is over all disjoint $k$-tuples of paths
$\pi=(\pi_{1},\dots,\pi_{k})$ with $\pi(r)\in\mathbb{R}^{k}_{<}$ for
$r\in(s,t)$, and such that $\pi(s)=\mathbf{x},\pi(t)=\mathbf{y}$. In [DZ21],
the authors show that the maximum in (14) is almost surely achieved for all
$s<t$ and $\mathbf{x},\mathbf{y}\in\mathbb{R}^{k}_{\leq}$. As before, we call
a maximizer a disjoint optimizer, or geodesic if $k=1$. Moreover, the extended
landscape is continuous, and is the limit of multi-path Brownian LPP. Using
this structure, we can define (multi-path) Busemann functions in $\mathcal{L}$
as in (8). For $\theta,\mathbf{x}\in\mathbb{R}^{k}_{\leq}$, let

$\mathfrak{B}^{\theta}(\mathbf{x};\mathcal{L}):=\lim_{t\to-\infty}\mathcal{L}(\theta|t|,t;\mathbf{x},0)-\sum_{j=1}^{m}\mathcal{L}(\hat{\theta}^{\ell_{i}}|t|,t;0^{\ell_{i}},0).$
(15)

Putting aside the question of Busemann existence for one moment, by analogy
with (9), for every $a\in\mathbb{R}$ we can define an RSK map for
$\mathcal{L}$. For $a\in\mathbb{R}$, define
$B^{\mathcal{L},a}(\cdot)\in\mathcal{C}^{\mathbb{N}}(\mathbb{R})$ by:

$\sum_{i=1}^{k}B^{\mathcal{L},a}_{i}(x)=\mathfrak{B}^{(a/2)^{k}}(x;\mathcal{L}).$
(16)

We can now ask for the usual properties of these maps: invertibility, measure-
preservation, isometry. The next theorem gives analogues of these properties
here.

######  Theorem 1.7.

Let $\mathcal{L}$ denote the directed landscape, and let
$\mathbb{H}^{2}_{\uparrow}=\\{(x,s;y,t)\in\mathbb{R}^{4}:s<t\leq 0\\}$. For
every $a\in\mathbb{R}$ define an environment
$B^{\mathcal{L},a}\in\mathcal{C}^{\mathbb{N}}(\mathbb{R})$ as in (16) from
$\mathcal{L}|_{\mathbb{H}^{2}_{\uparrow}}$. Then:

  1. 1.

(Measure preservation) For any $a\in\mathbb{R}$, $B^{\mathcal{L},a}$ is a
sequence of independent Brownian motions of drift $a$. Moreover, the joint law
of $B^{\mathcal{L},a},a\in C$ is the same as the joint law of the environments
$B^{a},a\in C$ in Theorem 1.4 for any countable set $C\subset\mathbb{R}$ (we
restrict to countable $C$ to avoid topological issues). In particular, almost
surely $B^{\mathcal{L},a+b}=(B^{\mathcal{L},a})^{b}$ for any fixed
$a,b\in\mathbb{R}$.

  2. 2.

(Busemann isometry) For any $a\in\mathbb{R}$ and
$\lambda\in\mathbb{R}^{k}_{\leq}$, a.s. for all
$\mathbf{x}\in\mathbb{R}^{k}_{\leq}$ we have

$\mathcal{W}^{\lambda+a}(\mathbf{x};B^{\mathcal{L},a})=\mathfrak{B}^{(\lambda+a)/2}(\mathbf{x};\mathcal{L}).$

  3. 3.

(Invertibility) If we let the environment
$\mathcal{L}^{a}|_{\mathbb{H}^{2}_{\uparrow}}$ be defined as in Theorem 1.6
where $B^{a}=B^{\mathcal{L},a}$, then

$\mathcal{L}^{a}|_{\mathbb{H}^{2}_{\uparrow}}\stackrel{{\scriptstyle\mathbb{P}}}{{\to}}\mathcal{L}|_{\mathbb{H}^{2}_{\uparrow}}$

as $a\to-\infty$, where the convergence in probability is in the compact
topology on functions from $\mathbb{H}^{2}_{\uparrow}\to\mathbb{R}$. Since any
two of the environments $B^{a,\mathcal{L}},B^{b,\mathcal{L}}$ are a.s.
measurable functions each other by part $1$, this implies that for every
$a_{0}\in\mathbb{R}$ there is a measurable map
$f:\mathcal{C}^{\mathbb{N}}(\mathbb{R})\to\mathcal{C}(\mathbb{H}^{2}_{\uparrow})$
such that $\mathcal{L}|_{\mathbb{H}^{2}_{\uparrow}}=f(B^{\mathcal{L},a_{0}})$
a.s.

Theorem 1.7 contains Theorem 1.1, and is proven in the text as part of the
stronger Theorem 5.8. To understand where Theorem 1.7 comes from, we should
examine what happens to the Busemann functions for $B^{a}$ under the scaling
in Theorem 1.6. If we momentarily assume that we can exchange the order of the
$t\to-\infty$ limit in (8) and the $a\to-\infty$ limit in Theorem 1.6, we can
use the coupling of the environments $B^{a}$ in Theorem 1.4 to see that:

$\begin{split}\mathfrak{B}^{\theta}(\mathbf{x};\mathcal{L})&\stackrel{{\scriptstyle
d}}{{=}}\lim_{a\to-\infty}\mathcal{B}^{a^{3}/(2a+8\theta)}(\mathbf{x};B^{a})=\lim_{a\to-\infty}\mathcal{W}^{|a|\sqrt{1/(1+4\theta/a)}}(\mathbf{x};B^{a})\\\
&=\lim_{a\to-\infty}\mathcal{W}^{|a|\sqrt{1/(1+4\theta/a)}+a}(\mathbf{x};B)=\mathcal{W}^{2\theta}(\mathbf{x};B).\end{split}$
(17)

Putting this together gives a candidate for the law of the extended Busemann
process $\mathfrak{B}^{\theta}(\mathbf{x};\mathcal{L})$, which is verified by
Theorem 1.7.1,2. Comparing Figures 2 and 3 illustrates this part of the
theorem. The law we have identified is consistent with known results about the
single-path Busemann process in the directed landscape [RV21, Bus21, BSS24].
In [Bus21], the process $\mathfrak{B}^{\theta}(x,\mathcal{L})$ for
$\theta,x\in\mathbb{R}$ was termed the stationary horizon, so naturally, we
call the extended process
$(\theta,\mathbf{x})\mapsto\mathfrak{B}^{\theta}(\mathbf{x},\mathcal{L})$ for
arbitrary
$(\theta,\mathbf{x})\in\bigcup_{k=1}^{\infty}\mathbb{R}^{k}_{\leq}\times\mathbb{R}^{k}_{\leq}$
the extended stationary horizon.

Now, given Theorem 1.7.1,2, the coupling of the environments $\mathcal{L}^{a}$
through the environments $B^{\mathcal{L},a}$ given a sequence of maps
converging to $\mathcal{L}$ in law, and whose multi-path Busemann functions
converge in probability. One may optimistically expect that in such a
coupling, we also have convergence in probability of the directed landscape on
the whole lower half-plane. Indeed, this is the case, and is verified by
Theorem 1.7.3! To prove this, we require a different suite of ideas, based
around proving optimizer rigidity in the directed landscape and constructing
double-slit Busemann functions, see Sections 5.3, 5.4, 5.5 for details.

Theorem 1.7 also allows us to prove a version of the same theorem restricted
to a strip, resolving a conjecture from [DZ21, Conjecture 1.10]. For this
theorem and throughout the paper, for a topological space $X$ we let
$\mathcal{C}(X)$ denote the space of continuous functions $f:X\to\mathbb{R}$
with the compact topology.

######  Theorem 1.8.

Let $\mathcal{L}$ denote the directed landscape restricted to the strip
$\mathbb{S}^{2}_{\uparrow}=\\{(x,s;y,t)\in([0,1]\times\mathbb{R})^{2}:s<t\\},$
and define
$\mathfrak{A}\in\mathcal{C}(\mathbb{R}\times\mathbb{N}),(i,x)\mapsto\mathfrak{A}_{i}(x)$
by the formula

$\sum_{i=1}^{k}\mathfrak{A}_{i}(x)=\mathcal{L}(0^{k},0;x^{k},1).$

Then $\mathfrak{A}\in\mathcal{C}(\mathbb{R}\times\mathbb{N})$ is a parabolic
Airy line ensemble and there is a measurable function
$f:\mathcal{C}(\mathbb{R}\times\mathbb{N})\to\mathcal{C}(\mathbb{S}^{2}_{\uparrow})$
with $f(\mathfrak{A})=\mathcal{L}$ almost surely.

The function $f$ in Theorem 1.8 is not as useful as the function in Theorem
1.7, as we do not have an explicit definition for it. However, its existence
is almost immediate given Theorem 1.7 and a multi-path RSK isometry proven in
[DZ21], see Corollary 5.10 for details.

###  1.5 Future research directions

Our hope is that the present work opens up a new method both for understanding
the directed landscape, and for proving convergence to it. With this in mind,
we pose a set of future research directions that arise naturally from the
work, and seem accessible with current techniques.

While we prove that the directed landscape can be constructed from independent
Brownian motions, we use the existence of the directed landscape and
properties to help facilitate the proofs. We also use estimates on the shape
of Brownian melon, which stem from determinantal formulas for Brownian LPP and
the Airy line ensemble. Nonetheless, our approach suggests that an appeal to
such formulas should not be necessary for identifying the directed landscape
since we do not use formulas in an essential way. With this in mind, it seems
natural to suggest the following.

######  Problem 1.9.

Construct the directed landscape directly from Brownian last passage
percolation without any appeal to determinantal formulas.

At the opposite end of the spectrum, there is the possibility of using exact
formulas to extract a quantitative convergence result from Theorem 1.7.

######  Problem 1.10.

In the coupling in Theorem 1.7, show that there exists $\alpha>0$ such that
for any compact set $K\subset\mathbb{H}^{2}_{\uparrow}$ we have

$\mathbb{E}\sup_{u\in
K}|\mathcal{L}^{a}(u)-\mathcal{L}(u)|\leq|a|^{-\alpha+o(1)}$

as $a\to-\infty$. Optimize $\alpha$.

Currently, there are models in the KPZ universality class for which we do not
have sufficient access to exact formulas to prove convergence to the directed
landscape, but nonetheless have descriptions for their stationary
distributions. Some examples include multi-species (or coloured) versions of
the totally asymmetric zero-range process and q-PushTASEP, see [AMM22, ANP23],
and [FM, Mar20] for older work on the more classical models of coloured TASEP
and ASEP. The stationary distributions in these settings have queuing-
theoretic descriptions that are discrete analogues of the single-path Brownian
Busemann process. All this work suggests that there is multi-path RSK
structure underlying these models, which would provide an avenue for landscape
convergence.

######  Problem 1.11.

Prove that discrete particle systems whose multi-type stationary distributions
have queuing-theoretic descriptions converge to the directed landscape.

Our chief example for Problem 1.11 was going to be coloured TASEP; however,
shortly before posting this paper, coloured TASEP, coloured ASEP and the
stochastic six-vertex model were all shown to converge to the directed
landscape! See [ACH24] for details.

Finally, as a by product of the proof of Theorem 1.3, we show that certain
models of ‘zigzag’ Brownian LPP have Brownian stationary measures, see Example
3.9. An extension of the ideas in this paper should show that such models have
multi-path Busemann functions with a tractable description close of that of
Theorem 1.4, 1.5, and hence these models should converge to the directed
landscape. Proving this seems like a natural testing ground for the ideas of
the present paper. Here is one concrete problem.

######  Problem 1.12.

Let $B=(B_{i},i\in\mathbb{Z})$ be an environment of independent Brownian
motions of drift $1$ if $i$ is even and drift $-1$ if $i$ is odd. For points
$(x,n),(y,m)\in\mathbb{R}\times\mathbb{Z}$ with $n>m$ define

$B[(x,n)\rightsquigarrow(y,m)]=\sup_{z_{n+1}=x,\dots,z_{m}=y}\sum_{i=m}^{n}B_{i}(z_{i})-B_{i}(z_{i+1}),$

where in the supremum, we require $z_{i+1}\leq z_{i}$ if $i$ is odd, and
$z_{i+1}\geq z_{i}$ if $i$ is even. This requirement along with the drift
condition on the Brownian paths means the above supremum is always finite.
Prove that under some scaling, this model converges to the directed landscape.

###  1.6 Background and related work

We give a brief review of the literature on KPZ, RSK, and the directed
landscape, focusing on papers closely related to the present work. For a
gentle introduction to KPZ suitable for a newcomer to the area, see [Rom15] or
the introductory articles [Cor16, Gan22]. Review articles and books that go
into more depth include [FS10, Qua11, WFS17, Zyg18].

The importance of RSK to problems in the KPZ universality class goes back at
least to [LS77, VK77], who identified the law of large numbers for the longest
increasing subsequence in a uniform permutation. The Baik-Deift-Johansson
theorem [BDJ99] went further, analyzing exact formulas for the Young tableaux
arising from RSK to identify the one-point distribution $\mathcal{L}(0,0;0,1)$
as a GUE Tracy-Widom random variable, see also [Joh00]. Prähofer and Spohn
expanded on these methods [PS02] to prove convergence to the parabolic Airy
line ensemble for the PNG droplet, see also [Joh03]. The Prähofer-Spohn
theorem can be viewed as taking the KPZ scaling limit of the Young tableaux
side of the RSK correspondence. More recent approaches to studying KPZ limits
have found exact formulas for multi-time distributions, see [JR20, BL19] and
[MQR] for the construction of the KPZ fixed point.

A series of papers by O’Connell and coauthors [OY01, OY02, O’C03, BBO05]
developed RSK in the semi-discrete setting and started to understand the
correspondence in terms of Pitman transforms. One of the upshots of this work
was a version of the RSK isometry which had also been observed in [NY04]. This
isometry was used in [DOV22] as the key tool for constructing the directed
landscape, and of course drives much of the present paper.

The relevance of Busemann functions to studying KPZ models goes back to
Hoffman [Hof05, Hof08] in first passage percolation. See [ADH17, Section 5]
for discussion surrounding open problems on Busemann functions in that
setting. In solvable models of last passage percolation, Busemann functions
have been used to study competition and coexistence, to construct stationary
solutions and establish uniqueness of these solutions, and to establish
results about semi-infinite geodesics, see [CP12, CP13, BCK14, GRASY15,
GRAS17a, GRAS17b] for a sample of recent work in this direction. The last-
passage/queuing-theoretic description for the law of the stationary horizon in
(11) has its roots in the work of Ferrari and Martin [FM07, FM] on coloured
TASEP and the Hammersley process. A similar description in exponential LPP was
given by Seppäläinen and Fan [FS20] before being adapted to Brownian LPP
[SS23a]. Busemann functions in the directed landscape were first studied in
[RV21]. The law of the whole stationary horizon found in [Bus21, SS23b],
connected to the directed landscape in [BSS24], and shown to be the scaling
limit for stationary measures in discrete models in [BSS22, BSS23].

The use of multi-path last passage values and disjoint optimizers to extract
information about underlying geometry in KPZ is a more recent phenomenon.
Hammond [Ham22, Ham20] first connected exact statistics about disjoint
optimizers from a common point in Brownian LPP to the rarity of disjoint
geodesics. A precise combinatorial connection between disjoint optimizers and
the RSK isometry was exploited in [DOV22], and used there as a key tool in the
original construction of the directed landscape. The theory of disjoint
optimizers at the level of the directed landscape was developed in [DZ21].
This was used to help classify geodesic networks in the directed landscape in
[Dau23a], and to prove structural results about the spacetime difference
profile in [GZ22]. The phenomenon of optimizer rigidity for large $k$ that is
so important in the proof of Theorem 1.7 was anticipated in the watermelon
scaling exponents uncovered in [BGHH22].

##  2 Preliminaries

In this section, we gather a few basic results about LPP and the directed
landscape. For basic definitions, we refer the reader back to the
introduction.

###  2.1 Basics of last passage percolation

Recall the definition of LPP, multi-path LPP, geodesics, and semi-infinite
optimizers in Section 1.2. We use the following basic facts about these
objects throughout the paper. We state all results here for $k$-path
optimizers and multi-path last passage values. When $k=1$, these results
specialize to the simpler setting of geodesics and last passage values.
Throughout Section 2.1, we fix $f\in\mathcal{C}^{\mathbb{Z}}(\mathbb{R})$. All
results will also apply for $f\in\mathcal{C}^{I}(\mathbb{R})$ for integer
intervals $I$, when the relevant objects are well-defined. For
$\mathbf{p}=(\mathbf{x},\mathbf{n}),\mathbf{q}=(\mathbf{y},\mathbf{m})\in\mathbb{R}^{k}_{\leq}\times\mathbb{Z}^{k}_{\leq}$,
we call $(\mathbf{p},\mathbf{q})$ an endpoint pair if there is at least one
disjoint $k$-tuple from $\mathbf{p}$ to $\mathbf{q}$.

######  Lemma 2.1 (Optimizer existence: Lemma 2.2, [DZ21]).

Let $(\mathbf{p},\mathbf{q})$ be an endpoint pair. Then there exists an
optimizer $\pi^{L}$ from $\mathbf{p}$ to $\mathbf{q}$ such that
$\pi^{L}\leq\pi$ for any optimizer $\pi$ from $\mathbf{p}$ to $\mathbf{q}$. We
call $\pi^{L}$ the leftmost optimizer. Similarly, there exists a rightmost
optimizer $\pi^{R}$ from $\mathbf{p}$ to $\mathbf{q}$ such that
$\pi^{R}\geq\pi$ for any optimizer $\pi$ from $\mathbf{p}$ to $\mathbf{q}$.

######  Lemma 2.2 (Optimizer monotonicity: Lemma 2.3, [DZ21]).

Let $(\mathbf{p},\mathbf{q})$ and $(\mathbf{p}^{\prime},\mathbf{q}^{\prime})$
be two endpoint pairs of sizes $k$. Suppose that:

  1. 1.

$\mathbf{p}=(\mathbf{x},n)$ and $\mathbf{p}^{\prime}=(\mathbf{x}^{\prime},n)$
for some $\mathbf{x}\leq\mathbf{x}^{\prime}\in\mathbb{R}^{k}_{\leq}$, or else
$\mathbf{p}=(x,\mathbf{n})$ and $\mathbf{p}^{\prime}=(x,\mathbf{n}^{\prime})$
for some $\mathbf{n}\leq\mathbf{n}^{\prime}\in\mathbb{Z}^{k}_{\leq}$.

  2. 2.

$\mathbf{q}=(\mathbf{y},n)$ and $\mathbf{q}^{\prime}=(\mathbf{y}^{\prime},n)$
for some $\mathbf{y}\leq\mathbf{y}^{\prime}\in\mathbb{R}^{k}_{\leq}$, or else
$\mathbf{q}=(y,\mathbf{m})$ and $\mathbf{q}^{\prime}=(y,\mathbf{m}^{\prime})$
for some $\mathbf{m}\leq\mathbf{m}^{\prime}\in\mathbb{Z}^{k}_{\leq}$.

Then letting $\pi$ be the rightmost optimizer from $\mathbf{p}$ to
$\mathbf{q}$, and $\pi^{\prime}$ be the rightmost optimizer from
$\mathbf{p}^{\prime}$ to $\mathbf{q}^{\prime}$ we have that
$\pi\leq\pi^{\prime}$.

Technically, [DZ21, Lemma 2.2] only applies when
$\mathbf{p}=(\mathbf{x},n),\mathbf{p}^{\prime}=(\mathbf{x}^{\prime},n)$ and
$\mathbf{q}=(\mathbf{y},n),\mathbf{q}^{\prime}=(\mathbf{y}^{\prime},n)$.
However, the proof goes through verbatim is the slightly more general setting
above.

######  Lemma 2.3 (Metric composition law).

Let $(\mathbf{p},\mathbf{q})=(\mathbf{x},\mathbf{n};\mathbf{y},\mathbf{m})$ be
an endpoint pair of size $k$ and let $\ell\in\\{m_{k}+1,\dots,n_{1}\\}$. Then

$f[\mathbf{p}\to\mathbf{q}]=\max_{\mathbf{z}}f[\mathbf{p}\to(\mathbf{z},\ell)]+f[(\mathbf{z},\ell-1)\to\mathbf{q}],$

where the maximum is taken over $\mathbf{z}\in\mathbb{R}^{k}_{\leq}$ such that
both $(\mathbf{p};\mathbf{z},\ell)$ and $(\mathbf{z},\ell-1;\mathbf{q})$ are
endpoint pairs. Similarly, if $z\in[x_{k},y_{1}]$, then

$f[\mathbf{p}\to\mathbf{q}]=\max_{\mathbf{l}\in\mathbb{Z}^{k}_{<}}f[\mathbf{p}\to(z,\mathbf{l})]+f[(z,\mathbf{l})\to\mathbf{q}],$

where the maximum is taken over $\mathbf{l}\in\mathbb{Z}^{k}_{<}$ such that
both $(\mathbf{p};z,\mathbf{l})$ and $(z,\mathbf{l};\mathbf{q})$ are endpoint
pairs.

######  Lemma 2.4 (Quadrangle inequality, Lemma 2.4, [DZ21]).

Let
$(\mathbf{p},\mathbf{q})=(\mathbf{x},\mathbf{n};\mathbf{y},\mathbf{m}),(\mathbf{p}^{\prime},\mathbf{q}^{\prime})=(\mathbf{x}^{\prime},\mathbf{n}^{\prime};\mathbf{y}^{\prime},\mathbf{m}^{\prime})$
be endpoint pairs satisfying the conditions of Lemma 2.2. Suppose that
$(\mathbf{p},\mathbf{q}^{\prime})$ and $(\mathbf{p}^{\prime},\mathbf{q})$ are
also endpoint pairs. Then:

$f[\mathbf{p}\to\mathbf{q}^{\prime}]+f[\mathbf{p}^{\prime}\to\mathbf{q}]\leq
f[\mathbf{p}\to\mathbf{q}]+f[\mathbf{p}^{\prime}\to\mathbf{q}^{\prime}]$

with equality if there exists a point $z\in[x_{k}^{\prime},y_{1}]$ and
optimizers $\pi$ from $\mathbf{p}$ to $\mathbf{q}$, $\pi^{\prime}$ from
$\mathbf{p}^{\prime}$ to $\mathbf{q}^{\prime}$ such that
$\pi(z)=\pi^{\prime}(z)$.

The ‘equality if’ claim in Lemma 2.4 is not contained in [DZ21], but it is
easy to see. In this case, the paths
$\pi|_{(-\infty,z)}\oplus\pi^{\prime}|_{[z,\infty)}$ and
$\pi^{\prime}|_{(-\infty,z)}\oplus\pi|_{[z,\infty)}$ (here $\oplus$ denotes
paths concatenation), are disjoint $k$-tuples from $\mathbf{p}$ to
$\mathbf{q}^{\prime}$ and $\mathbf{p}^{\prime}$ to $\mathbf{q}$ whose lengths
sum to
$f[\mathbf{p}\to\mathbf{q}]+f[\mathbf{p}^{\prime}\to\mathbf{q}^{\prime}]$,
proving the reverse inequality in Lemma 2.4. We end with a straightforward
statement regarding last passage across lines and common shifts of the
environment, whose proof we leave to the reader.

######  Lemma 2.5 (Last passage commutes with shifts).

Let $g:\mathbb{R}\to\mathbb{R}$ be any continuous function, and let
$f+g\in\mathcal{C}^{\mathbb{Z}}(\mathbb{R})$ be given by
$(f_{i}+g,i\in\mathbb{Z})$. Then for any endpoint pairs
$\mathbf{p}=(\mathbf{x},\mathbf{n}),\mathbf{q}=(\mathbf{y},\mathbf{m})\in\mathbb{R}^{k}_{\leq}\times\mathbb{Z}^{k}_{\leq}$,
we have:

$(f+g)[\mathbf{p}\to\mathbf{q}]=f[\mathbf{p}\to\mathbf{q}]+\sum_{i=1}^{k}[g(y_{i})-g(x_{i})].$

We will typically use Lemma 2.5 when $g$ is a constant or linear function. We
will typically refer to these five results without reference, as they should
be viewed as part of the basic language for working with geodesics and
optimizers.

###  2.2 Shape and continuity bounds for Brownian LPP

We will need two complementary limit shape theorems for Brownian LPP. For the
first proposition, for $n\in\mathbb{N}$ and $x,\alpha,b,w>0$ we define

$\mathcal{N}_{b,w}(n,x,a)=\sqrt{8nx}+\sqrt{x}n^{-1/6}(a+b\log^{2/3}(n^{1/3}|\log(x/w)|+1)).$

Note that for any $\alpha>0$, we have

$\mathcal{N}_{b,\alpha w}(n,\alpha
x,a)=\sqrt{\alpha}\mathcal{N}_{b,w}(n,x,a).$ (18)

######  Proposition 2.6 (Proposition 4.3, [DV21a]).

There exist positive constants $b,c$ and $d$ such that for all $w,a>0$ and
$n\geq 1$, the probability that

$B[(-x,n)\to(0,1)]\leq\mathcal{N}_{b,w}(n,x,a),\;\;\forall x\in(0,\infty)$

is greater than or equal to $1-ce^{-da^{3/2}}$.

The bound in Proposition 2.6 is chosen to minimize the error term at $x=w$.
Note that in [DV21a], Proposition 2.6 is stated when $w=1$. The general case
follows by Brownian scaling. We will typically use Proposition 2.6 when
$w=n/\theta$ for some $\theta>0$, in which case the mean term $\sqrt{8nx}\sim
n\sqrt{8/\theta}$ when $x\sim w$ and the error term is
$\sqrt{xn^{-1/6}}=O(n^{1/3})$, as is expected for KPZ models. Note that
Proposition 2.6 also provides a uniform upper bound on multi-path last passage
values, by virtue of the bound

$B[(\mathbf{x},n)\to(\mathbf{y},1)]\leq\sum_{i=1}^{k}B[(x_{i},n)\to(y_{i},1)].$

A corresponding lower bound also holds. We only state this at the level of the
one-point bound.

######  Proposition 2.7 (Lemma A.4, [DV21a]).

For every $k\in\mathbb{N}$, there exist positive constants
$c_{k},d_{k},k\in\mathbb{N}$ such that the following holds. For all $m>0$ and
all endpoint pairs $(\mathbf{x},n),(\mathbf{y},1)$ with
$\mathbf{x},\mathbf{y}\in\mathbb{R}^{k}_{\leq}$ we have

$\mathbb{P}\left(|B[(\mathbf{x},n)\to(\mathbf{y},1)]-\sum_{i=1}^{k}\sqrt{8n(x_{i}-y_{i})}|\geq
m\sqrt{x}n^{-1/6}\right)\leq c_{k}e^{-d_{k}m^{3/2}}.$

Note that in the statement of Lemma A.4, [DV21a], there are restrictions on
$\mathbf{x},\mathbf{y}$. However, these restrictions are not used in the proof
of that lemma. A typical application of Propositions 2.6 and 2.7 will be to
bound the location of the argmax in the metric composition law from Brownian
LPP. This is why we need a uniform upper bound but only a pointwise lower
bound.

###  2.3 The directed landscape

In this final preliminary section, we collect basic results about the directed
landscape. We start with the axiomatic description of $\mathcal{L}$ in terms
of the marginal $\mathcal{S}(x,y)=\mathcal{L}(x,0;y,1)$, known as the Airy
sheet. We have the following uniqueness theorem, see Definition 10.1 and
Theorem 10.9 of [DOV22].

######  Theorem 2.8.

The directed landscape $\mathcal{L}:\mathbb{R}^{4}_{\uparrow}\to\mathbb{R}$ is
the unique random continuous function satisfying:

  1. 1.

(Airy sheet marginals) For any $t\in\mathbb{R}$ and $s>0$ we have

$\mathcal{\mathcal{L}}(x,t;y,t+s^{3})\stackrel{{\scriptstyle
d}}{{=}}s\mathcal{S}(x/s^{2},y/s^{2})$

jointly in all $x,y$. That is, the increment over time interval $[t,t+s^{3})$
is an Airy sheet of scale $s$.

  2. 2.

(Independent increments) For any disjoint time intervals
$\\{[t_{i},s_{i}]:i\in\\{1,\dots k\\}\\}$, the random functions
$\\{\mathcal{L}(\cdot,t_{i};\cdot,s_{i}):i\in\\{1,\dots,k\\}$ are independent.

  3. 3.

(Metric composition law) Almost surely, for any $r<s<t$ and $x,y\in\mathbb{R}$
we have that

$\mathcal{L}(x,r;y,t)=\max_{z\in\mathbb{R}}[\mathcal{L}(x,r;z,s)+\mathcal{L}(z,s;y,t)].$

Note that Definition 10.1 in [DOV22] states the independent increment property
for disjoint open intervals, rather than closed intervals. The two are
equivalent by continuity. The directed landscape has invariance properties
which we use throughout the paper.

######  Lemma 2.9 (Lemma 10.2, [DOV22]).

We have the following equalities in distribution as random functions in
$\mathcal{C}(\mathbb{R}^{4}_{\uparrow})$. Here $r,c\in\mathbb{R}$, and $q>0$.

  1. 1.

(Time stationarity)

$\displaystyle\mathcal{L}(x,t;y,t+s)\stackrel{{\scriptstyle
d}}{{=}}\mathcal{L}(x,t+r;y,t+s+r).$

  2. 2.

(Spatial stationarity)

$\mathcal{L}(x,t;y,t+s)\stackrel{{\scriptstyle
d}}{{=}}\mathcal{L}(x+c,t;y+c,t+s).$

  3. 3.

(Flip symmetry)

$\mathcal{L}(x,t;y,t+s)\stackrel{{\scriptstyle
d}}{{=}}\mathcal{L}(-y,-s-t;-x,-t).$

  4. 4.

(Shear stationarity)

$\mathcal{L}(x,t;y,t+s)\stackrel{{\scriptstyle
d}}{{=}}\mathcal{L}(x+ct,t;y+ct+sc,t+s)+s^{-1}[(x-y)^{2}-(x-y-sc)^{2}].$

  5. 5.

($1:2:3$ rescaling)

$\mathcal{L}(x,t;y,t+s)\stackrel{{\scriptstyle
d}}{{=}}q\mathcal{L}(q^{-2}x,q^{-3}t;q^{-2}y,q^{-3}(t+s)).$

As discussed in the introduction (see (13) and surrounding discussion), we can
define path length and geodesics in the directed landscape. We record one
strong convergence lemma for geodesics that will be used in Section 5.1.

######  Lemma 2.10.

For two $\mathcal{L}$-geodesics
$\pi:[s,t]\to\mathbb{R},\gamma:[s^{\prime},t^{\prime}]\to\mathbb{R}$, define
the overlap $O(\pi,\gamma)$ to be the closure of the set
$\\{r\in(s,t)\cap(s^{\prime},t^{\prime}):\pi(r)=\gamma(r)\\}$. Also let
$\Gamma(S)$ denote the set of geodesics with endpoints in a set
$S\subset\mathbb{R}^{4}_{\uparrow}$. Then the following claims hold almost
surely:

  1. 1.

(Theorem 1, [Bha24] or Lemma 3.3.2, [Dau23a]) For any $\mathcal{L}$-geodesics
$\pi,\gamma$, $O(\pi,\gamma)$ is always a closed interval.

  2. 2.

(Part of Proposition 3.5, [Dau23a]) For two geodesics,
$\gamma:I\to\mathbb{R},\pi:I^{\prime}\to\mathbb{R}$, define

$d_{o}(\gamma,\pi)=\lambda(I)+\lambda(I^{\prime})-2\lambda(O(\pi,\gamma)),$

For any compact set $K\subset\mathbb{R}^{4}_{\uparrow}$, this is a metric on
$\Gamma(K)$ that turns $\Gamma(K)$ into a compact Polish space.

Lemma 2.10.2 ensures that any pointwise limit of a sequence of geodesics is
also a geodesic, and moreover, is also a limit in the stronger sense of
overlap. The overlap structure of landscape geodesics allows us to treat them
more like their discrete counterparts in LPP.

We move on to bounds on the extended directed landscape, see (14) for the
definition. We start with a version of Theorem 1.6 for the full extended
landscape. For this theorem, recall the scaling
$(\mathbf{x},s)_{a}=(\mathbf{x}-as/4,{\left\lfloor sa^{3}/8\right\rfloor})$.
In the introduction, we used this notation only for singletons $\mathbf{x}$.
Here we extend its use to vectors in $\mathbb{R}^{k}_{\leq}$. We also let
$\mathfrak{X}_{\uparrow}$ be the space of all points
$(\mathbf{x},s;\mathbf{y},t)$, where $s<t\in\mathbb{R}$ and
$\mathbf{x},\mathbf{y}$ lie in the same space $\mathbb{R}^{k}_{\leq}$ for some
$k\in\mathbb{N}$.

######  Theorem 2.11 (Theorem 1.5/1.6, [DZ21]).

For every $a\in\mathbb{R}$, let
$B^{a}=(B^{a}_{i}:\mathbb{R}\to\mathbb{R},i\in\mathbb{Z})$ be an environment
of independent two-sided Brownian motions of common drift $a$, and for a point
$(\mathbf{x},s;\mathbf{y},t)\in\mathfrak{X}_{\uparrow}$ with
$\mathbf{x},\mathbf{y}\in\mathbb{R}^{k}_{\leq}$, define

$\mathcal{L}^{a}(\mathbf{x},s;\mathbf{y},t)=B^{a}[(\mathbf{x},s)_{a}\to(\mathbf{y},t)_{a}]-\frac{ka^{2}}{4}(t-s),$

when the right-hand side exists, and simply set
$\mathcal{L}^{a}(\mathbf{x},s;\mathbf{y},t)=-\infty$ otherwise. Then as
$a\to-\infty$,

$\mathcal{L}^{a}(\mathbf{x},s;\mathbf{y},t)\stackrel{{\scriptstyle
d}}{{\to}}\mathcal{L}(\mathbf{x},s;\mathbf{y},t),$

where the underlying topology is compact convergence of functions on
$\mathfrak{X}_{\uparrow}$.

Theorem 2.11 is stated with drift-free Brownian motions in [DZ21]. The
translation between the two theorems is immediate since last passage commutes
with common shifts of the environment (Lemma 2.5).

Analogues of Lemmas 2.1, 2.2, 2.3, and 2.4 hold in the directed landscape, and
we record here the results we need in that context.

######  Lemma 2.12 (Optimizer existence in $\mathcal{L}$: Theorem 1.7,
[DZ21]).

Almost surely, for every choice of $(\mathbf{x},s,\mathbf{y},t)$ there is a
disjoint $k$-tuple $\pi=(\pi_{1},\dots,\pi_{k})$ with

$\sum_{i=1}^{k}\|\pi\|_{\mathcal{L}}=\mathcal{L}(\mathbf{x},s;\mathbf{y},t).$

That is, the maximum (14) is attained for every $\mathbf{x},s,\mathbf{y},t$.
For any fixed $(\mathbf{x},s,\mathbf{y},t)$, almost surely this disjoint
optimizer is unique.

Unlike in the semi-discrete setting, Lemma 2.1 is actually quite a difficult
result. Its proof takes up a large part of the paper [DZ21]. In the $k=1$ case
of geodesics, the result is easier, and was proven in [DOV22, Theorem 1.7,
Lemma 13.2], where the existence of leftmost and rightmost geodesics is also
shown. Because Lemma 2.12 does not give the existence of leftmost and
rightmost optimizers, the analogue of optimizer monotonicity for $\mathcal{L}$
is slightly more subtle.

######  Lemma 2.13 (Optimizer monotonicity in $\mathcal{L}$: see Lemma 7.7,
[DZ21]).

Almost surely the following holds in $\mathcal{L}$. Let
$\mathbf{x}\leq\mathbf{x}^{\prime}\in\mathbb{R}^{k}_{\leq}$,
$\mathbf{y}\leq\mathbf{y}^{\prime}\in\mathbb{R}^{k}_{\leq}$, $s<t$, and let
$\pi,\pi^{\prime}$ be optimizers in $\mathcal{L}$ from $(\mathbf{x},s)$ to
$(\mathbf{y},t)$ and $(\mathbf{x}^{\prime},s)$ to $(\mathbf{y}^{\prime},t)$,
respectively. Then if either $\pi$ or $\pi^{\prime}$ is the unique optimizer
between its endpoints, we have $\pi\leq\pi^{\prime}$.

Observe that in the setting of Lemma 2.2, we can also conclude that
$\pi\leq\pi^{\prime}$ if there exists
$\mathbf{x}^{\prime\prime},\mathbf{y}^{\prime\prime}$ with
$\mathbf{x}\leq\mathbf{x}^{\prime\prime}\leq\mathbf{x}^{\prime}$ and
$\mathbf{y}\leq\mathbf{y}^{\prime\prime}\leq\mathbf{y}^{\prime}$ such that
there is a unique optimizer from $(\mathbf{x}^{\prime\prime},s)$ to
$(\mathbf{y}^{\prime\prime},t)$. Such
$\mathbf{x}^{\prime\prime},\mathbf{y}^{\prime\prime}$ will exist almost surely
for all $\mathbf{x},\mathbf{y},\mathbf{x}^{\prime},\mathbf{y}^{\prime}$ for
which $x_{i}<x_{i}^{\prime},y_{i}<y_{i}^{\prime}$ for all $i$.

######  Lemma 2.14 (Metric composition law, Proposition 6.9, [DZ21]).

Almost surely, for every $r<s<t$ and
$\mathbf{x},\mathbf{y}\in\mathbb{R}^{k}_{\leq}$ for some $k\in\mathbb{N}$ we
have

$\mathcal{L}(\mathbf{x},r;\mathbf{y},t)=\max_{z\in\mathbb{R}^{k}_{<}}\mathcal{L}(\mathbf{x},r;\mathbf{z},s)+\mathcal{L}(\mathbf{z},s;\mathbf{y},t).$

######  Lemma 2.15 (Quadrangle inequality, Lemma 5.7, [DZ21]).

Almost surely, for all $\mathbf{x}\leq\mathbf{x}^{\prime}$ and
$\mathbf{y}\leq\mathbf{y}^{\prime}$ in $\mathbb{R}^{k}_{\leq}$ and $s<t$, we
have

$\mathcal{L}(\mathbf{x},s;\mathbf{y}^{\prime},t)+\mathcal{L}(\mathbf{x}^{\prime},s;\mathbf{y},t)\leq\mathcal{L}(\mathbf{x},s;\mathbf{y},t)+\mathcal{L}(\mathbf{x}^{\prime},s;\mathbf{y}^{\prime},t).$

We end with a shape bound on the extended directed landscape.

######  Lemma 2.16 (Lemma 6.7, [DZ21]).

For any $\eta>0$ and $k\in\mathbb{N}$, there is a random constant $R>1$, such
that for any $\mathbf{x},\mathbf{y}\in\mathbb{R}^{k}_{\leq}$ and $s<t$, we
have

$\left|\mathcal{L}(\mathbf{x},s;\mathbf{y},t)+\sum_{i=1}^{k}\frac{(x_{i}-y_{i})^{2}}{t-s}\right|<RG(\mathbf{x},\mathbf{y},s,t)^{\eta}(t-s)^{1/3}$

where

$G(\mathbf{x},\mathbf{y},s,t)=\left(1+\frac{\|\mathbf{x}\|_{1}+\|\mathbf{y}\|_{1}}{(t-s)^{2/3}}\right)\left(1+\frac{|s|}{t-s}\right)(1+|\log(t-s)|).$

Also $\mathbb{P}(R>a)<ce^{-da}$ for any $a>0$, where $c,d>0$ are constants
depending on $k,\eta$.

##  3 The double sorting monoid and RSK on $\mathcal{C}^{n}(\mathbb{R})$

In this section we build up the theory of Pitman transforms and the double
sorting monoid. One aspect of this theory is a version of the RSK
correspondence for functions $f\in\mathcal{C}^{n}(\mathbb{R})$. However, the
theory as a whole offers a much richer picture.

###  3.1 An abstract theory of sorting

Let $S_{n}$ denote the symmetric group with $n$ elements, and let
$\pi_{i}=(i,i+1)$ denote the adjacent transposition in $S_{n}$ swapping
$i,i+1$. The adjacent transpositions $\pi_{1},\dots,\pi_{n-1}$ generate the
symmetric group, together with the relations

$\displaystyle\pi_{i}\pi_{i+1}\pi_{i}$
$\displaystyle=\pi_{i+1}\pi_{i}\pi_{i+1},\quad$ $\displaystyle
i=1,\dots,n-2\qquad$ (Braid relation) (19) $\displaystyle\pi_{i}\pi_{j}$
$\displaystyle=\pi_{j}\pi_{i},\quad$ $\displaystyle|i-j|\geq 2\qquad$
(Commutation relation) (20) $\displaystyle\pi_{i}^{2}$
$\displaystyle=\text{id},\quad$ $\displaystyle i=1,\dots,n-1\qquad$
(Involution relation) (21)

Now, let $G(S_{n})$ be the monoid of all functions $f:S_{n}\to S_{n}$ (with
the operation of function composition). For $i=1,\dots,n-1$ define the
adjacent sorting operator $\tau_{i}\in G(S_{n})$ by:

$\displaystyle\tau_{i}(\chi)=\begin{cases}\chi,\qquad&\chi^{-1}(i)>\chi^{-1}(i+1),\\\
\pi_{i}\chi,\qquad&\chi^{-1}(i)<\chi^{-1}(i+1).\end{cases}$

Define the sorting monoid $\mathfrak{M}_{n}$ as the submonoid of $G(S_{n})$
generated by the elements $\tau_{i},i=1,\dots,n-1$. The following description
of the operators $\tau_{i}$ may also be enlightening. Recall that the
inversion number of a permutation $\pi$ is given by:

$\operatorname{Inv}(\pi)=\\#\\{(i,j)\in\\{1,\dots,n\\}^{2}:i<j,\pi(i)>\pi(j)\\}.$

Then the operator $\tau_{i}$ takes the permutation $\chi$ and applies the
adjacent transposition $\pi_{i}$ if and only if doing so increases the
inversion number. The effect of this is that composition by the element
$\tau_{i}$ pushes $\chi$ further away from the identity permutation and closer
to the reverse permutation $n\cdots 1$. From this point of view, we can think
of repeated applications of $\tau_{i}$ as sorting into reverse order.

Abstractly the sorting monoid can be given by a set of relations that is quite
similar to the relations above for the symmetric group. Indeed, the $\tau_{i}$
still satisfy the braid and commutation relations (19) and (20), but rather
than satisfying the involution relation (21), they satisfy an idempotent
relation:

$\displaystyle\tau_{i}^{2}$ $\displaystyle=\tau_{i},\quad$ $\displaystyle
i=1,\dots,n-1\qquad$ (Idempotent relation) (22)

Because the relations for the $\tau_{i}$ are so similar to the relations for
the adjacent transpositions $\pi_{i}$, the theory of the sorting monoid is
closely related to the theory of the symmetric group itself. In fact, this
theory is almost equivalent to the study of reduced decompositions of elements
of the symmetric group, and the map $\pi\mapsto\pi(\text{id})$ defines a
bijection from $\mathfrak{M}_{n}\to S_{n}$ that commutes with both the braid
and commutation relations.

The RSK correspondence across lines can be viewed as arising from an action of
$\mathfrak{M}_{n}$. This perspective was taken up in [BBO05]. In our setting,
we will need to consider a related action of a larger monoid in $G(S_{n})$.
Define the reverse adjacent sorting operator $\bar{\tau}_{i}\in G(S_{n})$ by

$\displaystyle\bar{\tau}_{i}(\chi)=\begin{cases}\chi,\qquad&\chi^{-1}(i)<\chi^{-1}(i+1),\\\
\pi_{i}\chi,\qquad&\chi^{-1}(i)>\chi^{-1}(i+1).\end{cases}$

The operators $\bar{\tau}_{i}$ sort permutations towards the identity, rather
than towards the reverse permutation. Let the double sorting monoid
$\mathfrak{D}_{n}$ be the submonoid of $G(S_{n})$ generated by the elements
$\tau_{i},\bar{\tau}_{i},i=1,\dots,n-1$. Unlike with $\mathfrak{M}_{n}$, it
does not seem straightforward to describe the double sorting monoid in terms
of a set of relations or to relate it directly to the symmetric group. Because
of this, we will need the following abstract proposition in order to define
actions of $\mathfrak{D}_{n}$.

######  Proposition 3.1.

Let $D$ be a partially ordered set and suppose that we have maps
${\boldsymbol{\tau}}_{i}:D^{n}\to D^{n}$,
$\bar{\boldsymbol{\tau}}_{i}:D^{n}\to D^{n}$, $i=1,\ldots n-1$ satisfying the
following conditions.

  1. (i)

The maps ${\boldsymbol{\tau}}_{i}$ satisfy the braid, commutation, and
idempotent relations (19), (20), (22) as do the maps
$\bar{\boldsymbol{\tau}}_{i}$. Moreover, we have the mixed commutation
relation
${\boldsymbol{\tau}}_{i}\bar{\boldsymbol{\tau}}_{j}=\bar{\boldsymbol{\tau}}_{j}{\boldsymbol{\tau}}_{i}$
whenever $|i-j|\geq 2$.

  2. (ii)

${\boldsymbol{\tau}}_{i}d=d$ if $d_{i}\not>d_{i+1}$ and
$\bar{\boldsymbol{\tau}}_{i}d=d$ if $d_{i}\not<d_{i+1}$.

  3. (iii)

For $d\in D^{n}$, let $\Xi_{d}$ be the set of elements $\xi\in S_{n}$ such
that for $i,j\in\\{1,\dots,n\\}$ we have

$d_{i}<d_{j}\qquad\implies\qquad\xi^{-1}(i)<\xi^{-1}(j).$

Then for any $d\in D^{n}$ and $i=1,\dots,n-1$ we have
$\Xi_{{\boldsymbol{\tau}}_{i}d}=\tau_{i}\Xi_{d}$ and
$\Xi_{\bar{\boldsymbol{\tau}}_{i}d}=\bar{\tau}_{i}\Xi_{d}$.

  4. (iv)

${\boldsymbol{\tau}}_{i}\bar{\boldsymbol{\tau}}_{i}d=d$ if $d_{i}\not<d_{i+1}$
and $\bar{\boldsymbol{\tau}}_{i}{\boldsymbol{\tau}}_{i}d=d$ if
$d_{i}\not>d_{i+1}$.

Then:

  1. (I)

For a word $\mathbf{w}$ in
${\boldsymbol{\tau}}_{i},\bar{\boldsymbol{\tau}}_{i}$, let $w$ be the
corresponding word in $\tau_{i},\bar{\tau}_{i}$ in $\mathfrak{D}_{n}$. For any
$d\in D^{n}$,

$\Xi_{\mathbf{w}d}=w\Xi_{d}.$

  2. (II)

Consider $d\in D^{n}$, words $\mathbf{w},\mathbf{w}^{\prime}$ in
${\boldsymbol{\tau}}_{i},\bar{\boldsymbol{\tau}}_{i}$ and let $w,w^{\prime}$
be the corresponding words in $\tau_{i},\bar{\tau}_{i}$ in $\mathfrak{D}_{n}$.
Suppose that there exists $\xi\in\Xi_{d}$ such that $w\xi=w^{\prime}\xi$. Then
$\mathbf{w}d=\mathbf{w}^{\prime}d$. In particular, if $w,w^{\prime}$ evaluate
to the same word in $\mathfrak{D}_{n}$, then $\mathbf{w},\mathbf{w}^{\prime}$
define the same map from $D^{n}\to D^{n}$.

  3. (III)

The map ${\boldsymbol{\tau}}_{i}\mapsto\tau_{i}$,
$\bar{\boldsymbol{\tau}}_{i}\mapsto\bar{\tau}_{i}$ extends to a monoid
homomorphism between the monoid $T$ generated by the maps
${\boldsymbol{\tau}}_{i},\bar{\boldsymbol{\tau}}_{i},$ $i=1,\ldots,n-1$ and
the double sorting monoid $\mathfrak{D}_{n}$. If there is an element $d\in
D^{n}$ with $d_{1}<d_{2}<\dots<d_{n}$ then this is a monoid isomorphism.

Throughout the proof (and in claims (I, II) above) , we use the convention
that for a word $\mathbf{w}=\mathbf{w}_{k}\cdots\mathbf{w}_{1}$ where
$\mathbf{w}_{i}\in\\{{\boldsymbol{\tau}}_{i},\bar{\boldsymbol{\tau}}_{i}:i=1,\dots,n-1\\}$,
we write $w=w_{k}\cdots w_{1}$ for the word in $\mathfrak{D}_{n}$ given by
taking $\mathbf{w}$ and replacing all instances of
${\boldsymbol{\tau}}_{i},\bar{\boldsymbol{\tau}}_{i}$ with
$\tau_{i},\bar{\tau}_{i}$. Similarly, we write
$\tilde{w}=\tilde{w}_{k}\cdots\tilde{w}_{1}$ for the word in $S_{n}$ given by
mapping both ${\boldsymbol{\tau}}_{i},\bar{\boldsymbol{\tau}}_{i}$ to the
adjacent transposition $\pi_{i}=(i,i+1)$.

###### Proof.

Part (I). By induction, it suffices to check (I) for
$\mathbf{w}={\boldsymbol{\tau}}_{i}$ and
$\mathbf{w}=\bar{\boldsymbol{\tau}}_{i}$, in which case it is the content of
(iii).

Part (II). Let $\xi\in\Xi_{d}$ be such that $w\xi=w^{\prime}\xi$. Let us call
the letter $w_{\ell}$ in the word $w_{k}\cdots w_{1}$ ineffective for $d$ if
$w_{\ell}\cdots w_{1}\xi=w_{\ell-1}\cdots w_{1}\xi$. We call a word $w$
effective for $d$ if it has no ineffective letters. By part (I), we have that
$w_{\ell-1}\cdots w_{1}\xi\in\Xi_{\mathbf{w}_{\ell-1}\cdots\mathbf{w}_{1}d}$.
Therefore by (ii), we have that
$\mathbf{w}_{\ell}\cdots\mathbf{w}_{1}d=\mathbf{w}_{\ell-1}\cdots\mathbf{w}_{1}d$.
Therefore, we may drop all ineffective letters from $w,w^{\prime}$ along with
the corresponding letters from $\mathbf{w},\mathbf{w}^{\prime}$ without
changing $w\xi,w^{\prime}\xi,\mathbf{w}d,\mathbf{w}^{\prime}d$. In other
words, to prove part (II) it suffices to show that

$w\xi=w^{\prime}\xi\qquad\implies\qquad\mathbf{w}d=\mathbf{w}^{\prime}d$ (23)

whenever $w,w^{\prime}$ have no ineffective letters.

Now, suppose that the left equation in (23) holds for two words $w,w^{\prime}$
which are effective for $d$. The effectiveness of $w,w^{\prime}$ implies that
every letter in $w,w^{\prime}$ acts as an adjacent transposition in the
composition $w\xi,w^{\prime}\xi$ and so

$w\xi=\tilde{w}\xi,\qquad w^{\prime}\xi(d)=\tilde{w}^{\prime}\xi.$

This implies that $\tilde{w}\xi=\tilde{w}^{\prime}\xi$, and so
$\tilde{w},\tilde{w}^{\prime}$ represent the same element of the symmetric
group. Therefore there is a sequence of words
$\tilde{w}=u^{1},\dots,\tilde{w}^{\prime}=u^{k}$ in the alphabet
$\pi_{1},\dots,\pi_{n-1}$ such that for all $i=1,\dots,k$, $\tilde{w}_{i}$ and
$u^{i},u^{i+1}$ differ from each other by one of the relations (19), (20),
(21).

Next, given each of the words $u^{i}$ in the $\pi_{i}$, there is a unique way
to change each letter $\pi_{i}$ to either ${\boldsymbol{\tau}}_{i}$ or
$\bar{\boldsymbol{\tau}}_{i}$ so that every letter in the resulting word
$w^{i}$ is effective. Moreover, this change is consistent in the sense that
the assignment of bars agrees on consecutive words $w^{i},w^{i-1}$ everywhere
except where the relation is used. This procedure also gives rise to a
sequence of words
$\mathbf{w}=\mathbf{w}^{1},\dots,\mathbf{w}^{k}=\mathbf{w}^{\prime}$ in
${\boldsymbol{\tau}}_{i},\bar{\boldsymbol{\tau}}_{i}$.

To complete the proof of (II), we just need to show that
$\mathbf{w}^{i}d=\mathbf{w}^{i-1}d$ for all $i=2,\dots,k$. First suppose that
$u^{i-1},u^{i}$ differ by a commutation relation (20) so that
$u^{i-1}=\tilde{a}\pi_{\ell}\pi_{j}\tilde{b},u^{i}=\tilde{a}\pi_{j}\pi_{\ell}\tilde{b}$.
Then there is a unique choice of
$f(\pi_{\ell})\in\\{{\boldsymbol{\tau}}_{\ell},\bar{\boldsymbol{\tau}}_{\ell}\\}$
and $f(\pi_{j})\in\\{{\boldsymbol{\tau}}_{j},\bar{\boldsymbol{\tau}}_{j}\\}$
such that

$\mathbf{w}^{i-1}=\mathbf{a}f(\pi_{\ell})f(\pi_{j})\mathbf{b},\qquad\mathbf{w}^{i}=\mathbf{a}f(\pi_{j})f(\pi_{\ell})\mathbf{b}.$

By the commutation relation in (i), we have that
$\mathbf{w}^{i-1}=\mathbf{w}^{i}$. Next, suppose that $u^{i-1},u^{i}$ differ
by an involution relation (21) so that
$u^{i-1}=\tilde{a}\pi_{j}^{2}\tilde{b},u^{i}=\tilde{a}\tilde{b}$ (or vice
versa, with the $\pi_{j}^{2}$ on $u^{i}$). Then
$\mathbf{w}^{i}=\mathbf{a}\mathbf{b}$ and either

$\mathbf{w}^{i-1}=\mathbf{a}{\boldsymbol{\tau}}_{j}\bar{\boldsymbol{\tau}}_{j}\mathbf{b}\qquad\text{
or
}\qquad\mathbf{w}^{i-1}=\mathbf{a}{\boldsymbol{\tau}}_{j}\bar{\boldsymbol{\tau}}_{j}\mathbf{b}.$

Without loss of generality, assume that
$\mathbf{w}^{i-1}=\mathbf{a}{\boldsymbol{\tau}}_{j}\bar{\boldsymbol{\tau}}_{j}\mathbf{b}$.
First, since the word $w^{i}$ is effective for $d$ we have that
$\bar{\tau}_{j}b\xi\neq b\xi$ and so $[b\xi]^{-1}(j)>[b\xi]^{-1}(j+1).$ Now by
part i, $b\xi\in\Xi_{\mathbf{b}d}$, and so
$\mathbf{b}d_{j}\not<\mathbf{b}d_{j+1}$. Therefore by (iv),
${\boldsymbol{\tau}}_{j}\bar{\boldsymbol{\tau}}_{j}$ acts as the identity in
$\mathbf{w}^{i-1}d$, and so $\mathbf{w}^{i-1}d=\mathbf{w}^{i}d$.

Finally, suppose that $u^{i-1},u^{i}$ differ by a braid relation (19), so that
$u^{i-1}=\tilde{a}\pi_{j}\pi_{j+1}\pi_{j}\tilde{b}$ and
$u^{i}=\tilde{a}\pi_{j+1}\pi_{j}\pi_{j+1}\tilde{b}$ (or vice versa). Without
loss of generality, we may assume $j=1$. Here we divide into cases based on
the relative order of $\alpha_{1},\alpha_{2},\alpha_{3}$, where
$\alpha_{i}:=[b\xi]^{-1}(i)$, as the relative order of the $\alpha_{i}$
determines the barring on the operators
${\boldsymbol{\tau}}_{1},{\boldsymbol{\tau}}_{2}$ in
$\mathbf{w}^{i},\mathbf{w}^{i-1}$.

Case 1: $\alpha_{1}<\alpha_{2}<\alpha_{3}$ or
$\alpha_{1}>\alpha_{2}>\alpha_{3}$. In the first of these cases,
$\mathbf{w}^{i-1}=\mathbf{a}{\boldsymbol{\tau}}_{1}{\boldsymbol{\tau}}_{2}{\boldsymbol{\tau}}_{1}\mathbf{b}$
and
$\mathbf{w}^{i}=\mathbf{a}{\boldsymbol{\tau}}_{2}{\boldsymbol{\tau}}_{1}{\boldsymbol{\tau}}_{2}\mathbf{b}$
and in the second of these cases,
$\mathbf{w}^{i-1}=\mathbf{a}\bar{\boldsymbol{\tau}}_{1}\bar{\boldsymbol{\tau}}_{2}\bar{\boldsymbol{\tau}}_{1}\mathbf{b}$
and
$\mathbf{w}^{i}=\mathbf{a}\bar{\boldsymbol{\tau}}_{2}\bar{\boldsymbol{\tau}}_{1}\bar{\boldsymbol{\tau}}_{2}\mathbf{b}$.
In either case, $\mathbf{w}^{i-1}=\mathbf{w}^{i}$ by the braid relation in
(i).

Case 2: $\alpha_{3}<\alpha_{1}<\alpha_{2}$ or
$\alpha_{3}>\alpha_{1}>\alpha_{2}$. We only deal with the first of these
options, since as in Case 1, the second option is symmetric after swapping
bars and non-bars. In this case,
$\mathbf{w}^{i-1}=\mathbf{a}\bar{\boldsymbol{\tau}}_{1}\bar{\boldsymbol{\tau}}_{2}{\boldsymbol{\tau}}_{1}\mathbf{b}$
and
$\mathbf{w}^{i}=\mathbf{a}{\boldsymbol{\tau}}_{2}\bar{\boldsymbol{\tau}}_{1}\bar{\boldsymbol{\tau}}_{2}\mathbf{b}$.
Letting $e=\mathbf{b}d$, we have that $b\xi\in\Xi_{e}$, and so

$e_{3}\not>e_{1},\qquad e_{3}\not>e_{2},\qquad e_{1}\not>e_{2}.$

Now, we have that

${\boldsymbol{\tau}}_{2}\bar{\boldsymbol{\tau}}_{1}\bar{\boldsymbol{\tau}}_{2}e={\boldsymbol{\tau}}_{2}\bar{\boldsymbol{\tau}}_{1}\bar{\boldsymbol{\tau}}_{2}\bar{\boldsymbol{\tau}}_{1}{\boldsymbol{\tau}}_{1}e={\boldsymbol{\tau}}_{2}\bar{\boldsymbol{\tau}}_{2}\bar{\boldsymbol{\tau}}_{1}\bar{\boldsymbol{\tau}}_{2}{\boldsymbol{\tau}}_{1}e.$

Here the first equality follows from (iv). The second equality is a braid
relation for the $\mathbf{b}\tau_{i}$. Setting
$f=\bar{\boldsymbol{\tau}}_{1}\bar{\boldsymbol{\tau}}_{2}{\boldsymbol{\tau}}_{1}e$,
by (I) we have that $\bar{\tau}_{1}\bar{\tau}_{2}\tau_{1}b\xi\in\Xi_{f}$ and
so the ordering on the $\alpha_{i}$ guarantees that $f_{2}\not>f_{3}$.
Therefore ${\boldsymbol{\tau}}_{2}\bar{\boldsymbol{\tau}}_{2}$ acts as the
identity on $f$ by (iv), and so
${\boldsymbol{\tau}}_{2}\bar{\boldsymbol{\tau}}_{1}\bar{\boldsymbol{\tau}}_{2}e=\bar{\boldsymbol{\tau}}_{1}\bar{\boldsymbol{\tau}}_{2}{\boldsymbol{\tau}}_{1}e$
and hence $\mathbf{w}^{i-1}d=\mathbf{w}^{i}d$, as desired.

Case 2’: $\alpha_{1}<\alpha_{3}<\alpha_{2}$ or
$\alpha_{1}>\alpha_{3}>\alpha_{2}$. Again, we only deal with the first option.
In this case,
$\mathbf{w}^{i-1}=\mathbf{a}{\boldsymbol{\tau}}_{1}\bar{\boldsymbol{\tau}}_{2}\bar{\boldsymbol{\tau}}_{1}\mathbf{b}$
and
$\mathbf{w}^{i}=\mathbf{a}\bar{\boldsymbol{\tau}}_{2}\bar{\boldsymbol{\tau}}_{1}{\boldsymbol{\tau}}_{2}\mathbf{b}$,
and the same proof as in Case 2 will work with the roles of
${\boldsymbol{\tau}}_{1}$, $\bar{\boldsymbol{\tau}}_{1}$ and
${\boldsymbol{\tau}}_{2}$, $\bar{\boldsymbol{\tau}}_{2}$ reversed. This
completes the proof of (II).

Part (III). The fact that the map $w\mapsto\mathbf{w}$ is a monoid
homomorphism follows from (II). To see that it is an isomorphism when there
exists $d\in D^{n}$ be such that $d_{1}<d_{2}<\dots<d_{n}$, consider two
distinct elements $w,w^{\prime}\in\mathfrak{D}_{n}$ and a permutation $\chi$
with $w\chi\neq w^{\prime}\chi$. Let $w^{\prime\prime}\in\mathfrak{D}_{n}$ be
an element with $w^{\prime\prime}\text{id}=\chi$, and let $d\in D^{n}$ be such
that $d_{1}<d_{2}<\dots<d_{n}$. Then
$\Xi_{\mathbf{w}^{\prime}\mathbf{w}^{\prime\prime}d}=w^{\prime}w^{\prime\prime}\Xi_{d}=w^{\prime}\chi$,
and
$\Xi_{\mathbf{w}\mathbf{w}^{\prime\prime}d}=ww^{\prime\prime}\Xi_{d}=w\chi$.
Since $w\chi\neq w^{\prime}\chi$ this implies that
$\mathbf{w}\neq\mathbf{w}^{\prime}$. ∎

######  Example 3.2.

The following is essentially the simplest example of an application of
Proposition 3.1. Consider $\mathbf{x}\in\mathbb{R}^{n}$, and for
$i=1,\dots,k-1$ define

$\displaystyle{\boldsymbol{\tau}}_{i}(\mathbf{x})$
$\displaystyle=\begin{cases}\mathbf{x},\qquad&x_{i}\geq x_{i+1},\\\
(x_{1},\dots,x_{i-1},x_{i+1},x_{i},x_{i+2},\dots,x_{n}),\qquad&x_{i}<x_{i+1},\end{cases}$
$\displaystyle\bar{\boldsymbol{\tau}}_{i}(\mathbf{x})$
$\displaystyle=\begin{cases}\mathbf{x},\qquad&x_{i}\leq x_{i+1},\\\
(x_{1},\dots,x_{i-1},x_{i+1},x_{i},x_{i+2},\dots,x_{n}),\qquad&x_{i}>x_{i+1},\end{cases}$

It is straightforward to check that these maps satisfy the conditions of
Proposition 3.1, and hence extend to an action of $\mathfrak{D}_{n}$ on
$\mathbb{R}^{n}$. We call this action the basic action of $\mathfrak{D}_{n}$
on $\mathbb{R}^{n}$.

Example 3.2 shows that the double sorting monoid can be used to sorts lists
with possibly equal elements.

###  3.2 $\mathfrak{D}_{n}$-actions and Pitman operators

We next define a $\mathfrak{D}_{n}$-action on the space
$\mathcal{C}^{n}(\mathbb{R})$ of continuous functions
$f:\mathbb{R}\to\mathbb{R}^{n}$ with an asymptotic slope. First, define the
Pitman operator
$\mathcal{P}:\mathcal{C}^{2}(\mathbb{R})\to\mathcal{C}^{2}(\mathbb{R})$ by
following rules. If $\lambda_{1}(f)\geq\lambda_{2}(f)$, then set
$\mathcal{P}f=f$. If $\lambda_{1}(f)<\lambda_{2}(f)$, then define

$\begin{split}\mathcal{P}f_{1}(x)&=f[(-\infty,2)\to(x,1)]=f_{1}(x)+\sup_{z\leq
x}[f_{2}(z)-f_{1}(z)],\\\
\qquad\mathcal{P}f_{2}(x)&=f_{1}(x)+f_{2}(x)-\mathcal{P}f_{1}(x)=f_{2}(x)-\sup_{z\leq
x}[f_{2}(z)-f_{1}(z)].\end{split}$ (24)

In the above expression and in the remainder of the paper, we write
$\mathcal{P}f_{i}:=(\mathcal{P}f)_{i}$ to streamline notation. Next, define
the co-Pitman operator
$\bar{\mathcal{P}}:\mathcal{C}^{2}(\mathbb{R})\to\mathcal{C}^{2}(\mathbb{R})$
by letting $\mathcal{P}f=f$ if $\lambda_{1}(f)\leq\lambda_{2}(f)$, and setting

$\begin{split}\bar{\mathcal{P}}f_{1}(x)&=f_{1}(x)+\sup_{z\geq
x}[f_{2}(z)-f_{1}(z)],\\\
\qquad\bar{\mathcal{P}}f_{2}(x)&=f_{2}(x)-\sup_{z\geq
x}[f_{2}(z)-f_{1}(z)]\end{split}$ (25)

if $\lambda_{1}(f)>\lambda_{2}(f)$. The co-Pitman operator can be given by
conjugating the Pitman operator. Indeed, if we let $Rf(x)=f(-x)$ denote the
reflection map, then $\bar{\mathcal{P}}=R\mathcal{P}R.$ Similarly, if we let
$\hat{R}f_{1}(x)=-f_{2}(-x)$ and $\hat{R}f_{2}(x)=-f_{1}(-x)$ denote the
180-degree rotation of the environment, then
$\bar{\mathcal{P}}=\hat{R}\mathcal{P}\hat{R}.$

Next, for $f\in\mathcal{C}^{n}(\mathbb{R})$ and $i=1,\dots,n-2$ define

$\mathcal{P}_{\tau_{i}}f=(f_{1},\dots,f_{i-1},\mathcal{P}(f_{i},f_{i+1}),f_{i+2},\dots,f_{n}),$

and similarly set $\mathcal{P}_{\bar{\tau}_{i}}=R\mathcal{P}_{\tau_{i}}R$. Our
goal in the remainder of this section is to extend the Pitman operators
$\mathcal{P},\bar{\mathcal{P}}$ to actions of the double sorting monoid on
$\mathcal{C}^{n}(\mathbb{R})$. To do so, we check the conditions of
Proposition 3.1. We first record an _isometric_ property for Pitman operators.
This isometric property is one of the key reasons that Pitman operators are so
useful in the study of last passage percolation.

Following [DNV22], we say that two environments
$f,g\in\mathcal{C}^{n}(\mathbb{R})$ are boundary isometric and write $f\sim g$
if

$f[(\mathbf{x},n)\to(\mathbf{y},1)]=g[(\mathbf{x},n)\to(\mathbf{y},1)]$ (26)

for any vectors
$\mathbf{x},\mathbf{y}\in\mathbb{R}^{k}_{\leq},k\in\mathbb{N}$. We say that a
map $F:\mathcal{C}^{n}(\mathbb{R})\to\mathcal{C}^{n}(\mathbb{R})$ is a
(boundary) isometry if $Ff\sim f$ for all $f\in\mathcal{C}^{n}(\mathbb{R})$.

######  Lemma 3.3.

For all $n\in\mathbb{N}$ and $i\in\\{1,\dots,n-1\\}$, the operators
$\mathcal{P}_{\tau_{i}},\mathcal{P}_{\bar{\tau}_{i}}$ are boundary isometries.

###### Proof.

We will just check that $\mathcal{P}_{\tau_{i}}$ is an isometry. The claim for
$\mathcal{P}_{\bar{\tau}_{i}}$ follows from the fact that $X$ is an isometry
if and only if $\hat{R}X\hat{R}$ is an isometry for any map $X$. If
$\lambda_{i}(f)\geq\lambda_{i+1}(f)$, then $\mathcal{P}_{\tau_{i}}f=f$ and the
claim is immediate. Now suppose $\lambda_{i}(f)<\lambda_{i+1}(f)$. We check
that (26) holds for a fixed $\mathbf{x},\mathbf{y}$. Let
$T=\operatorname*{arg\,max}_{z\leq x_{1}}f_{i+1}(z)-f_{i}(z)$, and let
$f^{\prime}=f-f(T)$. Observing that $f\sim f^{\prime}$ and
$\mathcal{P}_{\tau_{i}}f\sim\mathcal{P}_{\tau_{i}}f-f(T)=\mathcal{P}_{\tau_{i}}f^{\prime}$,
it suffices to show that (26) holds for $\mathbf{x},\mathbf{y}$ with $f,g$
replaced by $f^{\prime},\mathcal{P}_{\tau_{i}}f^{\prime}$. In this case,
$f^{\prime}(T)=0$ and by the definition of $T$, for $x_{1}\leq z$ we have that

$\mathcal{P}_{\tau_{i}}f_{i}^{\prime}(z)=f^{\prime}[(T,2)\to(z,1)],\qquad\mathcal{P}_{\tau_{i}}f_{i+1}^{\prime}+\mathcal{P}_{\tau_{i}}f_{i}^{\prime}=f_{i+1}+f_{i}.$

For an operator defined using the left-hand sides above on continuous
functions $f^{\prime}:[T,\infty)\to\mathbb{R}^{n}$ with $f^{\prime}(T)=0$,
boundary isometry is proven as Lemma 4.3 in [DOV22]. ∎

We are now ready to prove the basic algebraic relations for Pitman operators.

######  Lemma 3.4.

The Pitman operators $\mathcal{P}_{\tau_{i}},\mathcal{P}_{\bar{\tau}_{i}}$
have the following properties.

  1. i.

Recall that $\lambda:\mathcal{C}^{n}(\mathbb{R})\to\mathbb{R}^{n}$ denotes the
slope map, and let ${\boldsymbol{\tau}}_{i},\bar{\boldsymbol{\tau}}_{i}$
denote the generators for the basic $\mathfrak{D}_{n}$-action on
$\mathbb{R}^{n}$ introduced in Example 3.2. Then for
$f\in\mathcal{C}^{n}(\mathbb{R})$ and $i=1,\dots,n-1$ we have
$\lambda\mathcal{P}_{\tau_{i}}f={\boldsymbol{\tau}}_{i}\lambda f$ and
$\lambda\mathcal{P}_{\bar{\tau}_{i}}f=\bar{\boldsymbol{\tau}}_{i}\lambda f$.

  2. ii.

The maps $\mathcal{P}_{\tau_{i}}$ satisfy the braid, commutation, and
idempotent relations (19), (20), (22) as do the maps
$\mathcal{P}_{\bar{\tau}_{i}}$. Moreover, we have the mixed commutation
relation
$\mathcal{P}_{\bar{\tau}_{i}}\mathcal{P}_{\tau_{j}}=\mathcal{P}_{\tau_{j}}\mathcal{P}_{\bar{\tau}_{i}}$
when $|i-j|\geq 2$.

  3. iii.

$\mathcal{P}_{\tau_{i}}\mathcal{P}_{\bar{\tau}_{i}}f=f$ if
$\lambda_{i}(f)\leq\lambda_{i+1}(f)$ and
$\mathcal{P}_{\bar{\tau}_{i}}\mathcal{P}_{\tau_{i}}f=f$ if
$\lambda_{i}(f)\geq\lambda_{i+1}(f)$.

###### Proof.

Part i. Here we just need to observe that if $\lambda_{1}(f)<\lambda_{2}(f)$
then $\lambda(\mathcal{P}f)=(\lambda_{2}(f),\lambda_{1}(f))$.

Part ii. The commutation relation (20) and the mixed commutation relation are
immediate. The idempotent relation (22) follows from part i, which implies
that $\lambda_{1}(\mathcal{P}f)\geq\lambda_{2}(\mathcal{P}f)$ for any
$f\in\mathcal{C}^{2}(\mathbb{R})$, and hence $\mathcal{P}$ acts as the
identity on its image. It suffices to check braid relation when $n=3$, and by
symmetry, only the unbarred identity

$\mathcal{P}_{\tau_{1}}\mathcal{P}_{\tau_{2}}\mathcal{P}_{\tau_{1}}f=\mathcal{P}_{\tau_{2}}\mathcal{P}_{\tau_{1}}\mathcal{P}_{\tau_{2}}f.$
(27)

We divide into cases, depending on the order of the slope $\lambda(f)$.

Case 1: $\lambda_{1}(f)<\lambda_{2}(f)<\lambda_{3}(f)$. Letting $g,h$ denote
the left- and right-hand sides of (27). Observing that Pitman operators
$\mathcal{P}_{\tau_{i}}$ preserve the sum $f_{1}+f_{2}+f_{3}$, it suffices to
show that $g_{1}=h_{1}$ and $g_{3}=h_{3}$. We will only prove the first of
these equalities as the second follows from a symmetric argument. We claim
that

$h_{1}=(\mathcal{P}_{\tau_{1}}\mathcal{P}_{\tau_{2}}f)_{1}=g_{1}.$ (28)

The first equality in (28) is immediate since $\mathcal{P}_{\tau_{2}}$ does
not affect line $1$. For the second equality, using that
$\lambda_{1}(f)\vee\lambda_{2}(f)<\lambda_{3}(f)$ we have that

$(\mathcal{P}_{\tau_{1}}\mathcal{P}_{\tau_{2}}f)_{1}(x)=f_{1}(x)+\sup_{z_{2}\leq
z_{1}\leq x}[f_{2}(z_{1})-f_{1}(z_{1})]+[f_{3}(z_{2})-f_{2}(z_{2})].$ (29)

In other words, we get the top line
$(\mathcal{P}_{\tau_{1}}\mathcal{P}_{\tau_{2}}f)_{1}$ by reflecting $f_{2}$
off of $f_{3}$, and then reflecting $f_{1}$ off of the result. Next, we can
rewrite the right-hand side of (29) as

$\sup_{z_{2}\leq x}f_{3}(z_{2})+f[(z_{2},2)\to(x,1)].$

By Lemma 3.3, this equals

$\sup_{z_{2}\leq
x}f_{3}(z_{2})+\mathcal{P}_{\tau_{1}}f[(z_{2},2)\to(x,1)]=\sup_{z_{2}\leq
x}\mathcal{P}_{\tau_{1}}f_{3}(z_{2})+\mathcal{P}_{\tau_{1}}f[(z_{2},2)\to(x,1)].$

Now, by part i, the inequality
$\lambda_{1}(f)\vee\lambda_{2}(f)<\lambda_{3}(f)$ is preserved by the map
$\mathcal{P}_{\tau_{1}}$. Hence the equality (29) also holds with
$\mathcal{P}_{\tau_{1}}f$ in place of $f$. Putting this together with the
previous three displays we get that
$(\mathcal{P}_{\tau_{1}}\mathcal{P}_{\tau_{2}}f)_{1}=(\mathcal{P}_{\tau_{1}}\mathcal{P}_{\tau_{2}}\mathcal{P}_{\tau_{1}}f)_{1}$,
giving the second equality in (28).

Case 2: $\lambda_{i}(f)\geq\lambda_{i+1}(f)$ for some $i\in\\{1,2\\}$. In this
case, using the slope-interchange property in part i and working through
different cases, in the composition
$\mathcal{P}_{\tau_{1}}\mathcal{P}_{\tau_{2}}\mathcal{P}_{\tau_{1}}f$ we have
that

  * •

The rightmost $\mathcal{P}_{\tau_{1}}$-operator acts as the identity if $i=1$;

  * •

The leftmost $\mathcal{P}_{\tau_{1}}$-operator acts as the identity if $i=2$.

Similarly, in the composition
$\mathcal{P}_{\tau_{2}}\mathcal{P}_{\tau_{1}}\mathcal{P}_{\tau_{2}}f$ we have
that

  * •

The rightmost $\mathcal{P}_{\tau_{2}}$-operator acts as the identity if $i=2$;

  * •

The leftmost $\mathcal{P}_{\tau_{2}}$-operator acts as the identity if $i=1$.

Therefore if $i=1$ then both sides of (27) are equal to
$\mathcal{P}_{\tau_{1}}\mathcal{P}_{\tau_{2}}f$, and if $i=2$ then both sides
of (27) are equal to $\mathcal{P}_{\tau_{2}}\mathcal{P}_{\tau_{1}}f$.

Part iii. This is also shown in the appendix of [SS23a], though the language
used there is different. We only check the first identity as the second
follows by symmetry. If $\lambda_{i}(f)=\lambda_{i+1}(f)$, then the identity
holds since both $\mathcal{P}_{\tau_{i}}$ and $\mathcal{P}_{\bar{\tau}_{i}}$
act as the identity. Now assume $\lambda_{i}(f)<\lambda_{i+1}(f)$. Since the
sum $f_{i}+f_{i+1}$ is preserved by both $\mathcal{P}_{\tau_{i}}$ and
$\mathcal{P}_{\bar{\tau}_{i}}$ it suffices to check that
$\mathcal{P}_{\bar{\tau}_{i}}\mathcal{P}_{\tau_{i}}f_{i}=f_{i}$. Define
$Sf(x)=\sup_{z\leq x}f_{i+1}(x)-f_{i}(x)$ so that

$\mathcal{P}_{\bar{\tau}_{i}}\mathcal{P}_{\tau_{i}}f_{i}(x)=f_{i}(x)+Sf(x)+\sup_{z\geq
x}[f_{i+1}(z)-f_{i}(z)-2Sf(z)].$

Noting that $Sf\geq f_{i+1}-f_{i}$ and that $Sf$ is non-decreasing we can see
that

$\mathcal{P}_{\bar{\tau}_{i}}\mathcal{P}_{\tau_{i}}f_{1}(x)\leq
f_{1}(x)+Sf(x)+\sup_{z\geq x}[-Sf(z)]=f_{1}(x).$

On the other hand, since $f_{1},f_{2}$ are continuous and the difference
$f_{2}(z)-f_{1}(z)\to\infty$ with $z$, there must exist $z_{0}\geq x$ where
$f_{2}(z_{0})-f_{1}(z_{0})=Sf(z_{0})=Sf(x).$ Therefore
$\mathcal{P}_{\bar{\tau}_{i}}\mathcal{P}_{\tau_{i}}f_{1}(x)\geq f_{1}(x)$,
yielding the result. ∎

Given Lemma 3.4, we can use Proposition 3.1 to extend the definition of Pitman
operators to the whole monoid $\mathfrak{D}_{n}$. Indeed, for
$\sigma\in\mathfrak{D}_{n}$, let $\xi_{k}\cdots\xi_{1}=\sigma$ where each
$\xi_{i}\in\\{\tau_{i},\bar{\tau}_{i}:i=1,\dots,n-1\\}$ and define

$\mathcal{P}_{\sigma}=\mathcal{P}_{\xi_{k}}\cdots\mathcal{P}_{\xi_{1}}.$

######  Corollary 3.5.

The map
$\sigma\mapsto\mathcal{P}_{\sigma}:\mathcal{C}^{n}(\mathbb{R})\to\mathcal{C}^{n}(\mathbb{R})$
is a monoid isomorphism of $\mathfrak{D}_{n}$. Moreover, letting
$\lambda:\mathcal{C}^{n}(\mathbb{R})\to\mathbb{R}^{n}$ denote the slope map,
for any $\sigma\in\mathfrak{D}_{n}$ we have

$\lambda\circ\mathcal{P}_{\sigma}=\sigma\circ\lambda$

where on the right-hand side of this equation $\sigma$ acts on
$\mathbb{R}^{n}$ through the basic action.

###### Proof.

To prove that the map $\sigma\mapsto\mathcal{P}_{\sigma}$ is unambiguously
defined and yields a monoid isomorphism we check the conditions of Proposition
3.1 where $D=\mathcal{C}^{1}(\mathbb{R})$ is given the partial order induced
by the slope map $\lambda$. Property (i) in Proposition 3.1 is guaranteed by
Lemma 3.4.ii, property (ii) is guaranteed by the definition, property (iii) is
guaranteed by Lemma 3.4.i, and property (iv) follows from Lemma 3.4.iii. The
‘Moreover’ claim then follows by Lemma 3.4.i again. ∎

The Pitman transforms described in this section have more structure than the
abstract monoid actions in Proposition 3.1. In particular, we can describe
orbits of elements in $\mathcal{C}^{n}(\mathbb{R})$ using this structure.

######  Lemma 3.6.

Consider the action
$\sigma\mapsto\mathcal{P}_{\sigma}:\mathcal{C}^{n}(\mathbb{R})\to\mathcal{C}^{n}(\mathbb{R})$,
and for $f\in\mathcal{C}^{n}(\mathbb{R})$ let
$O(f)=\\{\mathcal{P}_{\sigma}f:\sigma\in\mathfrak{D}_{n}\\}$ denote its orbit.
Let $O(\lambda(f))$ be the orbit of $\lambda(f)$ under the basic action of
$\mathfrak{D}_{n}$ on $\mathbb{R}^{n}$. Then:

  1. i.

For any $g\in O(f)$ there exists $\sigma\in\mathfrak{D}_{n}$ such that
$\mathcal{P}_{\sigma}g=f$ and so $O(f)=O(g)$.

  2. ii.

The slope map $g\mapsto\lambda(g)$ is a bijection from $O(f)$ to
$O(\lambda(f))$.

###### Proof.

For part i, if $g\in O(f)$ then $g=\mathcal{P}_{\sigma}f$ for some word
$\sigma=\pi_{k}\cdots\pi_{1}$ where
$\pi_{j}\in\\{\tau_{i},\bar{\tau}_{i}:i=1,\dots,n-1\\}$. Then from the
definition of $\mathcal{P}$ and Lemma 3.4.iii there exists a word
$\sigma^{\prime}=\pi_{1}^{\prime}\cdots\pi_{k}^{\prime}$ where each
$\pi_{j}^{\prime}$ equals either $\pi_{j}$ or its barred/unbarred version,
such that
$\mathcal{P}_{\sigma^{\prime}\sigma}f=\mathcal{P}_{\sigma^{\prime}}g=f$.

For part ii, by Corollary 3.5 the map $\lambda:O(f)\to O(\lambda(f))$ is onto.
Now suppose that $g_{1},g_{2}\in O(f)$ are such that
$\lambda(g_{1})=\lambda(g_{2})$. Using the notation $\Xi_{g_{1}}$ from
Proposition 3.1, let $\xi\in\Xi_{g_{1}}$. We will aim to find
$\sigma\in\mathfrak{D}_{n}$ with $\sigma\xi=\xi$ and
$\mathcal{P}_{\sigma}g_{1}=g_{2}$. If we can find such a $\sigma$, then by
Proposition 3.1(II), we have that
$g_{2}=\mathcal{P}_{\sigma}g_{1}=\mathcal{P}_{\text{id}}g_{1}=g_{1}$, as
desired. First, since $\lambda:O(f)\to O(\lambda(f))$ is onto we can find
$h\in O(f)=O(g_{1})$ with $\lambda(h)_{1}\geq\dots\geq\lambda(h)_{k}$. Let
$\sigma_{1}\in\mathfrak{D}_{n}$ be such that
$\mathcal{P}_{\sigma_{1}}g_{1}=h$. Since $O(h)=O(f)$ by part i, we can then
find $\sigma_{2}$ such that
$\mathcal{P}_{\sigma_{2}\sigma_{1}}g_{1}=\mathcal{P}_{\sigma_{2}}h=g_{2}$. We
can write $\sigma_{1}=\hat{\tau}_{i_{k}}\cdots\hat{\tau}_{i_{1}}$ and
$\sigma_{2}=\hat{\tau}_{j_{\ell}}\cdots\hat{\tau}_{j_{1}}$ where
$\hat{\tau}_{i}\in\\{\tau_{i},\bar{\tau}_{i}\\}$ for all $i$. We may also
assume that $\sigma_{1},\sigma_{2}$ are effective, in the sense that for any
$a\leq k$ or $b\leq\ell$ we have

$\mathcal{P}_{\hat{\tau}_{i_{a}}\cdots\hat{\tau}_{i_{1}}}g_{1}\neq\mathcal{P}_{\hat{\tau}_{i_{a-1}}\cdots\hat{\tau}_{i_{1}}}g_{1},\qquad\mathcal{P}_{\hat{\tau}_{j_{b}}\cdots\hat{\tau}_{j_{1}}}h\neq\mathcal{P}_{\hat{\tau}_{j_{b-1}}\cdots\hat{\tau}_{j_{1}}}h.$

Now, let $\tilde{\sigma}_{1}=\pi_{i_{k}}\cdots\pi_{i_{1}}$ and
$\tilde{\sigma}_{2}=\pi_{j_{\ell}}\cdots\pi_{j_{1}}$ be the corresponding
products of adjacent transpositions in $S_{n}$. Effectiveness of
$\sigma_{1},\sigma_{2}$ implies that
$\tilde{\sigma}_{2}\tilde{\sigma}_{1}\xi=\sigma_{2}\sigma_{1}\xi$. Next, let
$\Pi(h)$ be the set of adjacent transpositions $\pi_{i}$ such that
$\lambda(h)_{i}=\lambda(h)_{i+1}$, and let $H(h)\subset S_{n}$ be the subgroup
generated by $\Pi(h)$. Consider $\tilde{\kappa}\in H(h)$, and let
$\pi_{m_{k}}\cdots\pi_{m_{1}}$ be a reduced word for $\tilde{\kappa}$, written
in the alphabet $\Pi(h)$. There is a unique way to map the $\pi_{m_{i}}$ to
$\\{\tau_{m_{i}},\bar{\tau}_{m_{i}}\\}$ such that the resulting element
$\kappa\in\mathfrak{D}_{n}$ is effective on $\sigma_{1}\xi$. Hence
$\tilde{\kappa}\tilde{\sigma}_{1}\xi=\kappa\sigma_{1}\xi$. On the other hand,
from the definition of the Pitman transform applied to lines of equal slope,
$\mathcal{P}_{\kappa\sigma_{1}}g_{1}=\mathcal{P}_{\kappa}h=h$ for all
$\kappa\in H(h)$, so by the effectiveness of $\sigma_{2}$ on $h$ we have that
$\tilde{\sigma}_{2}\kappa\sigma_{1}\xi=\sigma_{2}\kappa\sigma_{1}\xi$. We also
have that $\mathcal{P}_{\sigma_{2}\kappa\sigma_{1}}g_{1}=g_{2}$ and hence
$\sigma_{2}\kappa\sigma_{1}\xi=\tilde{\sigma}_{2}\tilde{\kappa}\tilde{\sigma}_{1}\xi\in\Xi_{g_{2}}=\Xi_{g_{1}}$.
Finally, the map

$\tilde{\kappa}\mapsto\sigma_{2}\kappa\sigma_{1}\xi=\tilde{\sigma}_{2}\tilde{\kappa}\tilde{\sigma}_{1}\xi$

from $H(h)\to\Xi_{g_{1}}$ is a bijection. Indeed, this map is one-to-one by
the invertibility of $\tilde{\sigma}_{2},\tilde{\sigma}_{2}$ and it is easy to
see that $|H(h)|=|\Xi_{g_{1}}|$ (these are conjugate subgroups). Hence there
must be some $\kappa$ with $\sigma_{2}\kappa\sigma_{1}\xi=\xi$. Setting
$\sigma=\sigma_{2}\kappa\sigma_{1}$ then gives the desired sorting element. ∎

######  Corollary 3.7.

Let $f\in\mathcal{C}^{n}(\mathbb{R})$, and let $g\in O(f)$, where $O(f)$ is
the $\mathcal{P}$-orbit of $f$. Let $I$ be a set of the form
$\\{1,\ldots,k\\}$ or $\\{k,\ldots,n\\}$, and suppose that
$\lambda(f)_{j}=\lambda(g)_{j}$ for all $j\in I$. Then $f_{j}=g_{j}$ for all
$j\in I$.

###### Proof.

We can find $\sigma\in\mathfrak{D}^{n}$ with $\sigma\lambda(f)=\lambda(g)$,
where $\sigma$ acts through the basic action and can be written as a product
of adjacent transpositions that do not use coordinates of $I$. By Lemma 3.6,
$\mathcal{P}_{\sigma}f=g$, and since $\mathcal{P}_{\sigma}$ only affects
coordinates in $I^{c}$, $f_{j}=g_{j}$ for all $j\in I$. ∎

###  3.3 Sorting and last passage percolation

The goal of this section is to represent the $\mathfrak{D}_{n}$-action from
Corollary 3.5 in terms of last passage values. First consider
$f\in\mathcal{C}^{n}(\mathbb{R})$ with $\lambda(f)\in\mathbb{R}^{n}_{\leq}$,
and recall the definition of last passage from $-\infty$ in (6). The limit in
that definition exists when $\mathbf{m}\in\\{1,\dots,n\\}^{k}_{<}$ satisfies
the following property:

$\text{If $m_{i}$ is a coordinate of $\mathbf{m}$ but $m_{i}-1$ is not, then
$\lambda_{m_{i-1}}<\lambda_{m_{i}}$}.$ (30)

Moving forward, we will say $\mathbf{m}$ satisfies (30) with respect to
$\lambda$ when the slope vector is not clear context. We call a $k$-tuple of
paths $\pi=(\pi_{1},\dots,\pi_{k})$, where each
$\pi_{j}:(-\infty,x_{j}]\to\\{1,\dots,n\\}$ is a nonincreasing cadlag path
satisfying $\pi_{j}(x_{j})=1$ and $\lim_{t\to-\infty}\pi_{j}(t)=m_{j}$ a
disjoint optimizer from $(-\infty,\mathbf{m})$ to $(\mathbf{x},1)$ if
$\pi|_{[t,x_{k}]}$ is a disjoint optimizer for all $t<x_{1}$. The condition
(30) guarantees that disjoint optimizers from $(-\infty,\mathbf{m})$ to
$(\mathbf{x},1)$ exist and that they are pointwise limits of disjoint
optimizers from $(t,\mathbf{m})$ to $(\mathbf{x},1)$ as $t\to-\infty$.

For $f\in\mathcal{C}^{n}(\mathbb{R})$, we can describe elements of its
$\mathcal{P}$-orbit $O(f)$ using last passage percolation. We start with a few
examples before moving towards a general theory.

######  Example 3.8 (LPP to the top).

Let $f\in\mathcal{C}^{n}(\mathbb{R})$ and suppose that
$\lambda(f)_{k}<\lambda(f)_{j}$ for all $j<k$. Then

$f[(-\infty,k)\to(x,1)]=\mathcal{P}_{\tau_{1}\cdots\tau_{k-1}}f_{1}(x).$ (31)

This is almost immediate from the definition and the fact that the Pitman
transform $\mathcal{P}_{\tau_{i}}$ switches the slopes of $f_{i},f_{i+1}$ when
$\lambda(f)_{i}<\lambda(f)_{i+1}$.

######  Example 3.9 (Zigzag last passage percolation).

Let $f\in\mathcal{C}^{n}(\mathbb{R})$, suppose that
$\lambda(f)\in\mathbb{R}^{n}_{<}$. Let $g\in O(f)$, and let $\xi\in S_{n}$ be
such that

$\lambda(g)_{\xi^{-1}(1)}<\cdots<\lambda(g)_{\xi^{-1}(n)}.$

Then for every $j\in\\{1,\dots,n\\}$,

$f[(-\infty,j)\to(x,1)]=\mathcal{P}_{\sigma_{j}}g_{1}(x),\qquad\sigma_{j}=\sigma_{j,1}\cdots\sigma_{j,\xi^{-1}(j)-1},\qquad\sigma_{j,i}=\begin{cases}\tau_{i},\quad&j<\xi_{g}(i)\\\
\bar{\tau}_{i},&j>\xi_{g}(i)\end{cases}$

Indeed, by the previous example we have that
$f[(-\infty,j)\to(x,1)]=\mathcal{P}_{\tau_{1}\cdots\tau_{j-1}}f_{1}(x)$, and
moreover
$\lambda(\mathcal{P}_{\tau_{1}\cdots\tau_{j-1}}f)_{1}=\lambda(f)_{j}$.
Similarly, by construction
$\lambda(\mathcal{P}_{\sigma_{j}}g)_{1}=\lambda(f)_{j}$. Therefore by
Corollary 3.7 we have that
$\mathcal{P}_{\tau_{1}\cdots\tau_{j-1}}f_{1}=\mathcal{P}_{\sigma_{j}}g_{1}$.
We can rewrite $\mathcal{P}_{\sigma_{j}}g_{1}$ more explicitly as a kind of
zig-zag last passage percolation. Let $k=\xi^{-1}(j)$. Then

$\mathcal{P}_{\sigma_{j}}g_{1}(x)=g_{1}(x)+\sup_{\mathbf{y}\in\mathbb{R}^{k}}\left(\sum_{i=2}^{k}g_{i}(y_{i})-g_{i-1}(y_{i})\right),$

where the supremum is over all vectors $\mathbf{y}\in\mathbb{R}^{k}$ with
$y_{1}=x$ and satisfying the inequalities $y_{i}\leq y_{i-1}$ or $y_{i}\leq
y_{i-1}$ for all $2\leq i\leq k$ depending on whether
$\lambda(g)_{k}>\lambda(g)_{i-1}$ or $\lambda(g)_{k}<\lambda(g)_{i-1}$.
Remarkably, the Brownian Burke theorem (see Section 4) implies that we can
construct models of zig-zag last passage percolation across independent
Brownian motions whose stationary measures are themselves Brownian motions!

Both of the previous examples are special cases of the following general
proposition.

######  Proposition 3.10 (Orbit elements as last passage values).

Let $f\in\mathcal{C}^{n}(\mathbb{R})$ with
$\lambda(f)\in\mathbb{R}^{n}_{\leq}$, let $g\in O(f)$, let
$k\in\\{1,\dots,n\\}$, and let $\mathbf{x}\in\mathbb{R}^{k}_{\leq}$. Recall
that $\Xi_{g}\subset S_{n}$ is the set of permutations satisfying

$\lambda(g)_{\xi_{g}^{-1}(1)}\leq\cdots\leq\lambda(g)_{\xi_{g}^{-1}(n)}.$ (32)

There exists a unique vector $\mathbf{m}\in\\{1,\dots,n\\}^{k}_{<}$ satisfying
(30) for $\lambda(f)$ such that $\mathbf{m}=\xi\\{1,\dots,k\\}$ for some
$\xi\in\Xi_{g}$ (here thinking of $\mathbf{m}$ as a subset). We have

$g[(-\infty,(1,\dots,k))\to(\mathbf{x},1)]=f[(-\infty,\mathbf{m})\to(\mathbf{x},1)].\qquad$
(33)

In particular, if $x=x_{1}=\dots=x_{n}$ then

$g_{1}(x)+\dots+g_{k}(x)=f[(-\infty,\mathbf{m})\to(x^{k},1)].$

The proof of Proposition 3.10 is an induction based on the following lemma.

######  Lemma 3.11.

Let $f\in\mathcal{C}^{n}(\mathbb{R})$. Define
$\sigma=\tau_{n-1}\cdots\tau_{1}$. If $\lambda(f)_{1}<\lambda(f)_{i}$ for all
$i>1$, then for all $\mathbf{x}\in\mathbb{R}^{n-1}_{\leq}$:

$f[(-\infty,(2,\ldots,n))\to(\mathbf{x},1)]=\mathcal{P}_{\sigma}f[(-\infty,(1,\ldots,n-1))\to(\mathbf{x},1)].$
(34)

In particular, if $x_{1}=\dots=x_{n-1}=x$ then:

$f[(-\infty,(2,\ldots,n))\to(x^{n-1},1)]=\sum_{i=1}^{n-1}\mathcal{P}_{\sigma}f_{i}(x).$
(35)

###### Proof.

We actually prove the restricted case (35) first and then use this to prove
the general version (34). To shorten notation, we write
$[i,j]:=(i,i+1,\dots,j)\in\mathbb{R}^{j-i+1}$ through the proof. First, for
$t\leq x$ we have

$f[(t,[1,n])\to(x^{n},1)]=\sum_{i=1}^{n}f_{i}(x)-f_{i}(t)=\sum_{i=1}^{n}\mathcal{P}_{\sigma}f_{i}(x)-f_{i}(t).$
(36)

The first equality is by definition, and the second equality uses that Pitman
transforms preserve the sum of all lines. Moreover, it is easy to check from
the definition that

$\displaystyle f[(t,$ $\displaystyle[2,n])\to(x^{n},1)]$
$\displaystyle=f[(t,[1,n])\to(x^{n},1)]+f_{1}(t)-f_{n}(x)+\max_{t\leq
y_{1}\leq\dots\leq y_{n-1}\leq x}\sum_{i=1}^{n-1}f_{i+1}(y_{i})-f_{i}(y_{i}).$

Now, since $\lambda(f)_{1}<\lambda(f)_{i}$ for all $i>1$, the final term above
equals

$\max_{y_{1}\leq\dots\leq y_{n-1}\leq
x}\sum_{i=1}^{n-1}f_{i+1}(y_{i})-f_{i}(y_{i}).$

for all small enough $t$, and this minimum is attained. Therefore by (36), to
verify (35) we just need to show that

$\mathcal{P}_{\sigma}f_{n}(x)=f_{n}(x)-\max_{y_{1}\leq\dots\leq y_{n-1}\leq
x}\sum_{i=1}^{n-1}f_{i+1}(y_{i})-f_{i}(y_{i}).$ (37)

As in Example 3.8, this is essentially immediate from the definition (24) and
an induction since $\lambda(f)_{1}<\lambda(f)_{i}$ for all $i>1$.

We move to the general case. Fix $t\leq x_{1}$. By Lemma 3.3 we have that

$f[(t,[2,n])\to(\mathbf{x},1)]=\mathcal{P}_{\sigma}f[(t,[2,n])\to(\mathbf{x},1)].$

Now, since $\lambda(f)_{1}<\lambda(f)_{i}$ for all $i\geq 1$, then there
exists $t_{0}$ such that the function

$t\mapsto f[(t,[2,n])\to(\mathbf{x},1)]+\sum_{i=2}^{n}f_{i}(t)$

is constant for $t\leq t_{0}$, and hence equals the left-hand side of (34). On
the other hand, since $\lambda(f)_{1}<\lambda(f)_{i}$ for $i>1$ we have
$\lambda(\mathcal{P}_{\sigma}f)_{n}=\lambda(f)_{1}<\lambda(\mathcal{P}_{\sigma}f)_{i}=\lambda(f)_{i+1}$
for $i<n$. Therefore for all $t$ small enough we have

$\displaystyle\mathcal{P}_{\sigma}$ $\displaystyle
f[(t,[2,n])\to(x,1)]+\sum_{i=2}^{n}\mathcal{P}_{\sigma}f_{i}(t)$
$\displaystyle=\mathcal{P}_{\sigma}f[(x_{1},[1,n-1])\to(\mathbf{x},1)]+\sup_{y_{1}\leq\dots\leq
y_{n-1}\leq
x_{1}}\sum_{i=1}^{n-1}\mathcal{P}_{\sigma}f_{i+1}(y_{i})-\mathcal{P}_{\sigma}f_{i}(y_{i})$
$\displaystyle=\mathcal{P}_{\sigma}f[(-\infty,[1,n-1])\to(\mathbf{x},1)]+\sum_{i=1}^{n-1}\mathcal{P}_{\sigma}f_{i}(x_{1})+\sup_{y_{1}\leq\dots\leq
y_{n-1}\leq
x_{1}}\sum_{i=1}^{n-1}\mathcal{P}_{\sigma}f_{i+1}(y_{i})-\mathcal{P}_{\sigma}f_{i}(y_{i})$

Call the latter two terms on the right-hand side above $G(x_{1})$. Combining
all of the above displays gives that for all small enough $t$ we have the
equality

$f[(-\infty,[2,n])\to(\mathbf{x},1)]=\mathcal{P}_{\sigma}f[(-\infty,[1,n-1])\to(\mathbf{x},1)]+G(x_{1})+\sum_{i=2}^{n}f_{i}(t)-\mathcal{P}_{\sigma}f_{i}(t).$

Therefore

$\displaystyle
f[(-\infty,[2,n])\to(\mathbf{x},1)]-f[(-\infty,[2,n])\to(x^{n-1},1)]$
$\displaystyle=$
$\displaystyle\mathcal{P}_{\sigma}f[(-\infty,[1,n-1])\to(\mathbf{x},1)]-\mathcal{P}_{\sigma}f[(-\infty,[1,n-1])\to(x^{n-1},1)].$

On the other hand, (35) ensures that the second terms on both the right- and
left-hand sides above are equal, and hence so are the first terms, yielding
(34). ∎

###### Proof of Proposition 3.10.

First, we can construct $\mathbf{m}$ by recursively constructing
$\xi\in\Xi_{g}$. Indeed, for every $i\in\\{1,\dots,n\\}$, we always let
$\xi(i)$ be the minimal index
$j\in\\{1,\dots,n\\}\setminus\\{\xi(1),\dots,\xi(i-1)\\}$ with
$\lambda(f)_{j}=\lambda(g)_{i}$. Since $\lambda(g)$ is a permutation of
$\lambda(f)$, this process results in a permutation $\xi$. Moreover, the use
of minimal indices in the construction implies that resulting vector
$\mathbf{m}$ satisfies (30) for $\lambda(f)$. Uniqueness of $\mathbf{m}$
follows since $\lambda(f)\in\mathbb{R}^{n}_{\leq}$.

To prove (33), first assume that $m_{k}>k$. Let $\ell\in\\{1,\dots,m_{k}-1\\}$
be the maximal index with $\ell\notin\\{m_{1},\dots,m_{k-1}\\}$. Let
$\mathbf{m}_{2}=(\ell+1,\ell+2,\ldots,m_{k})$ so we can write
$\mathbf{m}=(\mathbf{m}_{1},\mathbf{m}_{2})$. Since $\mathbf{m}$ satisfies
(30), both $\mathbf{m}_{1},\mathbf{m}_{2}$ also satisfy (30) and so we may
define last passage from $(-\infty,\mathbf{m}_{1}),(-\infty,\mathbf{m}_{2})$.
Next, for $\mathbf{y}\in\mathbb{R}^{m_{k}-\ell}_{\leq}$, define

$\displaystyle
G(f,\mathbf{y},\mathbf{m}_{1}):=\lim_{t\to-\infty}f[(t^{|\mathbf{m}_{1}|},\mathbf{y};\mathbf{m}_{1},(\ell-1)^{m_{k}-\ell})\to(\mathbf{x},1)]+\sum_{i\in\mathbf{m}_{1}}f_{i}(t).$

Using this kind of hybrid last passage value, we can write down the following
metric composition law:

$\displaystyle f$
$\displaystyle[(-\infty,\mathbf{m})\to(\mathbf{x},1)]=\sup_{\mathbf{y}\in\mathbb{R}^{m-\ell}_{\leq}}f[(-\infty,\mathbf{m}_{2})\to(\mathbf{y},\ell)]+G(f,\mathbf{y},\mathbf{m}_{1}).$

Now, the condition (30) implies that $\lambda(f)_{\ell}<\lambda(f)_{j}$ for
all $j>\ell$. Therefore by Lemma 3.11 we may write the above as

$\displaystyle\sup_{\mathbf{y}\in\mathbb{R}^{m-\ell}_{\leq}}f^{\prime}$
$\displaystyle[(-\infty,\mathbf{m}_{2}^{\prime})\to(\mathbf{y},\ell)]+G(f^{\prime},\mathbf{y},\mathbf{m}_{1})=f^{\prime}[(-\infty,\mathbf{m}^{\prime})\to(\mathbf{x},1)],$

where $f^{\prime}={\boldsymbol{\tau}}_{\ell}\cdots{\boldsymbol{\tau}}_{m-1}f$,
$\mathbf{m}_{2}^{\prime}=\\{\ell,\ldots,m_{k}-1\\}$ and
$\mathbf{m}^{\prime}=(\mathbf{m}_{1},\mathbf{m}_{2}^{\prime})$. Note that
$G(f^{\prime},\mathbf{y},\mathbf{m}_{1})$ involves lines $1,\ldots,\ell-1$
only, which are equal in $f$ and $f^{\prime}$. Now, observe that our
construction gives that
$\lambda(f^{\prime})_{m_{i}^{\prime}}=\lambda(f)_{m_{i}}$ for all $i$, and
that in the new environment $f^{\prime}$, the vector $\mathbf{m}^{\prime}$
satisfies (30) for $\lambda(f^{\prime})$. Therefore if $m_{k}-1\neq k$ we can
repeat the above argument with $\mathbf{m}^{\prime},f^{\prime}$ in place of
$\mathbf{m},f$ to get $\mathbf{m}^{\prime\prime},f^{\prime\prime}$ with
$m^{\prime\prime}_{k}=m_{k}-2$,
$\lambda(f^{\prime\prime})_{m_{i}^{\prime\prime}}=\lambda(f)_{m_{i}}$ for all
$i$, and $\mathbf{m}^{\prime\prime}$ satisfying (30) for
$\lambda(f^{\prime\prime})$. Continuing in this way, we end at an environment
$h$ satisfying

$f[(-\infty,\mathbf{m})\to(\mathbf{x},1)]=h[(-\infty,(1,\dots,k))\to(\mathbf{x},1)]=h[(x_{1}^{k},k)\to(\mathbf{x},1)]+\sum_{i=1}^{k}h_{i}(x_{1})$

and satisfying $\lambda(h)_{i}=\lambda(f)_{m_{i}}$ for all $i$. If $m_{k}=m$,
we can avoid the above argument entirely and simply let $h=f$.

Now, there is a sorting operator $\sigma\in\mathfrak{D}_{n}$ which can be
written as a product of $\tau_{i},\bar{\tau}_{i},i\leq k-1$ such that
$\sigma\lambda(g)_{j}=\lambda(h)_{j}$ for all $j\leq k$. Therefore by
Corollary 3.7 we have that $\mathcal{P}_{\sigma}g_{j}=h_{j}$ for all $j\leq
k$, and so

$\displaystyle h[(x_{1}^{k},k)\to(\mathbf{x},1)]+\sum_{i=1}^{k}h_{i}(x_{1})$
$\displaystyle=g[(x_{1}^{k},k)\to(\mathbf{x},1)]+\sum_{i=1}^{k}g_{i}(x_{1})$
$\displaystyle=g[(-\infty,(1,\dots,k))\to(\mathbf{x},1)].$

Here the first equality uses that Pitman transforms preserve sums and are
boundary isometries (Lemma 3.3). Putting this together with the previous
display yields the result. ∎

The following corollary of Proposition 3.10 gives a clean formula for
inverting the full sort, where we completely reverse the order of the slopes.
This corollary can be viewed as describing the RSK correspondence in this
setting.

Let $\mathcal{C}^{n}_{\leq}(\mathbb{R}),\mathcal{C}^{n}_{\geq}(\mathbb{R})$ be
the subsets of $\mathcal{C}^{n}(\mathbb{R})$ such that if
$f\in\mathcal{C}^{n}_{\leq}(\mathbb{R})$ then
$\lambda(f)\in\mathbb{R}^{n}_{\leq}$ and if
$f\in\mathcal{C}^{n}_{\geq}(\mathbb{R})$ then
$\lambda(f)\in\mathbb{R}^{n}_{\geq}$. By Lemma 3.6, for
$f\in\mathcal{C}^{n}_{\leq}(\mathbb{R})$ there is a unique element
$\mathcal{P}_{\operatorname{RSK}}f$ in the $\mathcal{P}$-orbit of $f$ such
that $\mathcal{P}_{\operatorname{RSK}}f\in\mathcal{C}^{n}_{\geq}(\mathbb{R})$
and given $g\in\mathcal{C}^{n}_{\geq}(\mathbb{R})$, there is a unique element
$\mathcal{Q}_{\operatorname{RSK}}g$ in its $\mathcal{P}$-orbit contained in
$\mathcal{C}^{n}_{\geq}(\mathbb{R})$. Lemma 3.6.1 guarantees that these maps
are inverses, so we have defined a bijection

$\mathcal{P}_{\operatorname{RSK}}:\mathcal{C}^{n}_{\leq}(\mathbb{R})\to\mathcal{C}^{n}_{\geq}(\mathbb{R})$

with inverse $\mathcal{Q}_{\operatorname{RSK}}$. The next corollary gives a
simple global description of these maps without appealing to iterated Pitman
transforms. This is the analogue of Greene’s theorem in the present setting.

######  Corollary 3.12.

Let $f\in\mathcal{C}^{n}_{\leq}(\mathbb{R})$, let
$g=\mathcal{P}_{\operatorname{RSK}}f$, and set $Rg(x)=g(-x)$. For every
$k\in\\{1,\dots,n\\}$ let $\mathbf{n}_{k}\in\\{1,\dots,n\\}^{k}_{<}$ denote
the unique maximal vector (in the coordinatewise order) satisfying (30) for
$\lambda(f)$. Similarly, let $\mathbf{m}_{k}\in\\{1,\dots,n\\}^{k}_{<}$ denote
the unique maximal vector (in the coordinatewise order) satisfying (30) for
$-\lambda(f)=(-\lambda(f)_{k},\dots,-\lambda(f)_{1})$. Then:

$\displaystyle f[(-\infty,\mathbf{n}_{k})\to(x^{k},1)]$
$\displaystyle=g_{1}(x)+\dots+g_{k}(x),\qquad\text{ and }$ $\displaystyle
Rg[(-\infty,\mathbf{m}_{k})\to(-x^{k},1)]$
$\displaystyle=f_{1}(x)+\dots+f_{k}(x).$

###### Proof.

The recovery formulas for $g$ from $f$ are both special cases of Proposition
3.10. To recover $f$ from $g$ , first let $\sigma$ be such that
$\mathcal{P}_{\sigma}g=f$. Now, from the formulas
$\mathcal{P}_{\bar{\tau}_{i}}=R\mathcal{P}_{\tau_{i}}R$ and the identity
$R^{2}=\text{id}$, we have that $Rf=\mathcal{P}_{\bar{\sigma}}Rg$, where
$\bar{\sigma}$ is the given by taking the word $\sigma$ and mapping
$\tau_{i}\mapsto\bar{\tau}_{i}$ and $\bar{\tau}_{i}\mapsto\tau_{i}$
everywhere. Moreover, $Rg\in\mathcal{C}^{n}_{\leq}(\mathbb{R})$ so we can
apply Proposition 3.10 to recover $Rf$ from $Rg$. Applying $R$ to $Rf$ then
yields the formula above. ∎

A different approach to the bijection in Corollary 3.12 was developed in
Sorensen’s Ph.D. thesis using queuing maps rather than multi-path last
passage, e.g. see Section 2.3.3 and Lemma 2.3.18 in [Sor23]. Another
perspective on Corollary 3.12 is in terms of the Schützenberger involution.
Indeed, we can write
$\mathcal{Q}_{\operatorname{RSK}}=R\mathcal{P}_{\operatorname{RSK}}R$, where
$Rf(x)=f(-x)$. From this point of view, the fact that
$\mathcal{P}_{\operatorname{RSK}}$ inverts $\mathcal{Q}_{\operatorname{RSK}}$
on $\mathcal{C}^{n}_{\leq}(\mathbb{R})$ says that
$\mathcal{P}_{\operatorname{RSK}}R$ is an involution when restricted to
$\mathcal{C}^{n}_{\geq}(\mathbb{R})$. If we consider
$\mathcal{C}^{n}_{\geq}(\mathbb{R})\subset\mathcal{C}^{n}(\mathbb{R})$ as the
analogue of the set of Young tableaux, we can understand
$\mathcal{P}_{\operatorname{RSK}}R$ as the Schützenberger involution in the
present setting. See [Ful97, Appendix A] for discussion of the classical
Schützenberger involution and [BOZ21] for a comprehensive modern account of
the connection between the Schützenberger involution, last passage
percolation, and directed polymer partition functions.

###  3.4 Burke theorems

Pitman transforms behave well with Brownian inputs. At the level of the two-
line Pitman transform, this is the well-known Brownian Burke property, which
has been previously used in the study of LPP in [OY01, SS23a, SS23b]. For this
theorem and throughout the remainder of the paper, for a vector
$\lambda\in\mathbb{R}^{n}$ we let $\mu_{\lambda}$ denote the law of $t\mapsto
B(t)+\lambda t$, where $B\in\mathcal{C}^{n}_{0}(\mathbb{R})$ is $k$-tuple of
independent, two-sided Brownian motions of variance $2$.

######  Theorem 3.13 (Brownian Burke property).

Let $B=(B_{1},B_{2})\sim\mu_{(\lambda_{1},\lambda_{2})}$ for some
$\lambda_{2}>\lambda_{1}$. Then
$\mathcal{P}B-\mathcal{P}B(0)\sim\mu_{(\lambda_{2},\lambda_{1})}$.

###### Proof.

This is part of [OY01, Theorem 4]. We translate the language in order to
assist the reader navigating between that paper and ours. It suffices to prove
the theorem when $\lambda_{1}=0$, since the Pitman transform $\mathcal{P}$
commutes with a common linear shift of both functions (Lemma 2.5).

In the language of that paper, O’Connell and Yor show the following. Let
$B^{\prime},C:\mathbb{R}\to\mathbb{R}$ be two-sided, independent standard
Brownian motions, and let $m>0$. Define functions
$q,e,d:\mathbb{R}\to\mathbb{R}$ as follows:

$\displaystyle q(t)$ $\displaystyle=B_{t}^{\prime}+C_{t}-mt+\sup_{s\leq t}(ms-
C_{s}-B_{s}),$ $\displaystyle d(t)$ $\displaystyle=B_{t}^{\prime}+q(0)-q(t),$
$\displaystyle e(t)$ $\displaystyle=C_{t}+q(0)-q(t).$

Theorem 4 in [OY01] states $d,e$ are independent standard Brownian motions and
that $(d,e)|_{(-\infty,t]}$ is independent of $q|_{[t,\infty)}$ for any
$t\in\mathbb{R}$. We can rewrite their result in terms of Pitman transforms.
Define $B_{1}(t)=\sqrt{2}B_{t}^{\prime},B_{2}(t)=\sqrt{2}(mt-C_{t})$ and
observe that if $m=\lambda_{2}/\sqrt{2}$, then
$B=(B_{1},B_{2})\sim\mu_{(0,\lambda_{2})}$. Then

$\displaystyle\sqrt{2}q(t)$ $\displaystyle=\mathcal{P}B_{1}(t)-B_{2}(t),$
$\displaystyle\qquad\sqrt{2}d(t)$
$\displaystyle=B_{1}(t)+B_{2}(t)+\mathcal{P}B_{1}(0)-\mathcal{P}B_{1}(t)=\mathcal{P}B_{2}(t)-\mathcal{P}B_{2}(0).$
$\displaystyle\sqrt{2}(mt-e(t))$
$\displaystyle=B_{2}(t)+\mathcal{P}B_{1}(t)-B_{2}(t)-\mathcal{P}B_{1}(0)=\mathcal{P}B_{1}(t)-\mathcal{P}B_{1}(0)$

The claim that $d,e$ are independent standard Brownian motions gives that
$(\sqrt{2}(mt-e),\sqrt{2}d)=\mathcal{P}B-\mathcal{P}B(0)\sim\mu_{(\lambda_{2},0)}$.
∎

The following corollary extends the Brownian Burke property to the double
sorting monoid. For this corollary and in the remainder of the paper, we write
$f^{0}:=f-f(0)$ for $f\in\mathcal{C}^{I}(\mathbb{R})$, and write
$\mathcal{P}^{0}_{\sigma}f=(\mathcal{P}_{\sigma}f)^{0}$.

######  Corollary 3.14.

Let $B\sim\mu_{\lambda}$ for some vector $\lambda\in\mathbb{R}^{n}$. Then for
any $\sigma\in\mathfrak{D}_{n}$ we have

$\mathcal{P}_{\sigma}^{0}B\sim\mu_{\sigma\lambda},$ (38)

where $\sigma$ acts on $\lambda$ by the basic action.

###### Proof.

First, if $\sigma=\tau_{i}$ for some $i=1,\dots,n-1$ and
$\lambda_{i}<\lambda_{i+1}$, then (38) holds by Theorem 3.13. If
$\lambda_{i}\geq\lambda_{i+1}$, then (38) holds since
$\mathcal{P}_{\tau_{i}}B=B$ and $\tau_{i}\lambda=\lambda$. The case of general
$\sigma$ follows by induction. ∎

We end this section with a simple consequence of Corollary 3.14 and
Proposition 3.10. This corollary can be viewed as implying the existence of
stationary measures for Brownian LPP.

######  Corollary 3.15.

Consider vectors $\lambda\in\mathbb{R}^{n},\eta\in\mathbb{R}^{m}$ and suppose
that $\lambda_{i}>\eta_{j}$ for all $i\in\\{1,\dots,n\\},j\in\\{1,\dots,m\\}$.
Let $W=(B^{\prime},B)\sim\mu_{(\eta,\lambda)}$. Then for
$\mathbf{n}\in\\{1,\dots,n\\}^{k}_{<},\mathbf{x}\in\mathbb{R}^{k}_{\leq}$, we
have

$\displaystyle
W[(-\infty,\mathbf{n}+m)\to(\mathbf{x},1)]-W[(-\infty,\mathbf{n}+m)\to(0^{k},1)]\stackrel{{\scriptstyle
d}}{{=}}B[(-\infty,\mathbf{n})\to(\mathbf{x},1)],$

where here $\mathbf{n}+m=(n_{1}+m,\dots,n_{k}+m)$, and the equality in
distribution is joint in all $\mathbf{n},\mathbf{x}$.

###### Proof.

Let $\sigma\in\mathfrak{D}_{n+m}$ be such that
$\sigma(\nu,\lambda)=(\lambda,\nu)$ under the basic $\mathbb{R}$-action. Then
by Proposition 3.10, we have

$W[(-\infty,\mathbf{n}+m)\to(\mathbf{x},1)]=\mathcal{P}_{\sigma}W[(-\infty,\mathbf{n})\to(\mathbf{x},1)]$

for all $\mathbf{x},\mathbf{n}$ for which either side is defined. On the other
hand $\mathcal{P}_{\sigma}^{0}W\stackrel{{\scriptstyle d}}{{=}}(B,B^{\prime})$
by Corollary 3.14, yielding the result. ∎

##  4 RSK on $\mathcal{C}^{\mathbb{N}}(\mathbb{R})$: From Pitman to Busemann

In this section we study limits of Pitman transforms on
$\mathcal{C}^{n}(\mathbb{R})$ as $n\to\infty$. As discussed in the
introduction, this is natural when we work with a line environment of
independent Brownian motions. The resulting limits are expressed in terms of
Busemann functions. Because of this, in taking this limit we will
simultaneously build up a theory of multi-path Busemann functions in Brownian
LPP. Throughout this section, we let $B=(B_{i}:i\in\mathbb{Z})$ be an
environment of independent $2$-sided Brownian motions. Also, recall from
Section 1.3 the definition of multi-path Busemann functions and semi-infinite
geodesics and optimizers.

###  4.1 Multi-path Busemann functions

To study multi-path Busemann functions, we first need to understand single-
path Busemann functions. The theory in this setting was built by Seppäläinen
and Sorensen [SS23a, SS23b], and we use their results as a starting point.

######  Theorem 4.1.

In the environment $B$, define the centered Busemann function ending at
$(x,n)\in\mathbb{R}\times\mathbb{Z}$ in direction $\theta\in[0,\infty)$ by

$\mathcal{B}^{\theta}(x,n)=\lim_{t\to-\infty}B[(t,{\left\lfloor\theta
t+n\right\rfloor})\to(x,n)]-B[(t,{\left\lfloor\theta
t+n\right\rfloor})\to(0,1)].$ (39)

Then there exists a random countable set $\Theta\subset(0,\infty)$ such that
the following claims hold on an almost sure set $\Omega$:

  1. 1.

(Busemann existence, [SS23b, Theorem 2.5(i)] and [SS23a, Theorem 3.5(viii)]).
For any $(x,n)\in\mathbb{R}\times\mathbb{Z}$ and
$\theta\in(0,\infty)\setminus\Theta$ the above limit exists and is equal to

$\lim_{t\to-\infty}B[(t,\pi(t))\to(x,n)]-B[(t,\pi(t))\to(0,1)]$

for any function $\pi:(-\infty,x\wedge 0]\to\mathbb{R}$ such that
$\pi(t)/|t|\to\theta$ as $t\to-\infty$. When $\theta=0,n=1$, the above limit
exists and $\mathcal{B}^{\theta}(x,1)=B_{1}(x)$.

  2. 2.

(Metric composition, [SS23a, Theorem 3.5(vi)]). We have the following metric
composition law for Busemann functions. For any $n>m\in\mathbb{Z}$,
$x\in\mathbb{R}$, and direction $\theta\in(0,\infty)\setminus\Theta$ we have

$\mathcal{B}^{\theta}(x,m)=\max_{z\leq
x}\mathcal{B}^{\theta}(z,n)+B[(z,n-1)\to(x,1)].$

  3. 3.

(Geodesic existence, [SS23a, Theorem 3.1(i), Theorem 4.3(ii)]). There exist
semi-infinite geodesics ending at every point
$(x,n)\in\mathbb{R}\times\mathbb{Z}$ in every direction $\theta\in(0,\infty)$.
Moreover, for every $\theta\in(0,\infty)$,
$(x,n)\in\mathbb{R}\times\mathbb{Z}$ there exist leftmost and rightmost
geodesics $\pi^{L},\pi^{R}$ from $\theta$ to $(x,n)$ in the sense that for
every geodesic $\tau$ in direction $\theta$ ending at $(x,n)$ we have
$\pi^{L}\leq\tau\leq\pi^{R}$.

  4. 4.

(Geodesic monotonicity, [SS23a, Theorem 4.3(iii)]). For
$\theta_{1}\leq\theta_{2},n\in\mathbb{N}$ and $x_{1}\leq x_{1}$, if
$\pi^{L}_{i},i=1,2$ is the leftmost geodesic from $\theta_{i}$ to $(x_{i},n)$,
then $\pi^{L}_{1}\leq\pi^{L}_{2}$. An identical statement holds for rightmost
geodesics.

  5. 5.

(Geodesic coalescence, [SS23b, Theorem 2.8(i)]). For
$\theta\in(0,\infty)\setminus\Theta$, any two semi-infinite geodesics
$\pi,\tau$ in direction $\theta$ eventually coalesce, i.e. $\pi(t)=\tau(t)$
for all small enough $t$. Moreover, there is a unique semi-infinite geodesic
in direction $\theta$ and ending at $(x,n)$ for every
$x\in\mathbb{Q},n\in\mathbb{Z}$.

  6. 6.

($0$-directed geodesics, [SS23a, Theorem 4.3(iv, vi)]). For every
$(x,n)\in\mathbb{R}\times\mathbb{Z}$ the unique semi-infinite geodesic in
direction $0$ ending at $(x,n)$ is the constant path
$\pi:(-\infty,x]\to\mathbb{R},\pi\equiv n$.

Moreover, by [SS23b, Theorem 2.5], $\mathbb{P}(\theta\in\Theta)=0$ for all
$\theta>0$. Therefore we may assume $\mathbb{Q}\cap\Theta=\emptyset$ on
$\Omega$.

We will write $\mathcal{B}^{\theta}(x,n;\mathcal{B})$ in place of
$\mathcal{B}^{\theta}(x,)$ if the environment is not clear from context and
let $\mathcal{B}^{\theta}(x):=\mathcal{B}^{\theta}(x,1)$. Moving forward, we
will write $\mathcal{I}:=[0,\infty)\setminus\Theta$.

######  Remark 4.2.

In the above theorem, we have aimed to follow the notation of [SS23a, SS23b]
but have made a few changes in order to better integrate it with our present
setup. Our Busemann functions follow semi-infinite paths starting at
$t=-\infty$, whereas the semi-infinite paths in [SS23a, SS23b] end at
$t=\infty$ instead. We also use Brownian motions of variance $2$ instead of
$1$. A more important difference is that our Busemann function in direction
$\theta$ is their Busemann function in direction $1/\theta$. This choice is
more natural for our eventual study of RSK in the directed landscape. Finally,
the versions of Theorem 4.1.2 and Theorem 4.1.5 stated in [SS23b] give queuing
representations equivalent to our descriptions.

We now extend the definition of Busemann functions to multiple distinct
directions. Later we will use a continuity argument to allow for repeated
directions. For this definition, for $\theta\in\mathcal{I}^{k}_{\leq}$, write
$\pi^{\theta}=(\pi^{\theta_{1}},\dots,\pi^{\theta_{k}})$, where
$\pi^{\theta_{i}}$ is the unique geodesic in direction $\theta_{i}$ ending at
$(0,1)$.

######  Proposition 4.3.

For $\theta\in\mathcal{I}^{k}_{<},\mathbf{x}\in\mathbb{R}^{k}_{\leq}$, define

$\mathcal{B}^{\theta}(\mathbf{x})=\lim_{t\to-\infty}B[(t,{\left\lfloor\theta|t|+k\right\rfloor})\to(\mathbf{x},1)]-\sum_{i=1}^{k}B[(t,{\left\lfloor\theta_{i}|t|+k\right\rfloor})\to(0,1)].$
(40)

Then the following claims hold on an almost sure set $\Omega^{\prime}$.

  1. 1.

The limit (40) exists for all
$k\in\mathbb{N},\theta\in\mathcal{I}^{k}_{<},\mathbf{x}\in\mathbb{R}^{k}_{\leq}$.
Moreover, for any $k$-tuple of semi-infinite paths
$\pi=(\pi_{1},\dots,\pi_{k})$ in direction $\theta$, we have

$\mathcal{B}^{\theta}(\mathbf{x})=\lim_{t\to-\infty}B[(t,\pi(t))\to(\mathbf{x},1)]-\sum_{i=1}^{k}B[(t,\pi_{i}(t))\to(0,1)].$
(41)

  2. 2.

There exists leftmost and rightmost semi-infinite optimizers in every
direction $\theta\in[0,\infty)^{k}_{\leq}$ ending at every point
$(\mathbf{x},1),\mathbf{x}\in\mathbb{R}^{k}_{\leq}$. Moreover, if we let
$\tau^{\mathbf{x},\theta}$ denote the leftmost semi-infinite optimizer in
direction $\theta$ ending at $(\mathbf{x},1)$, then
$\tau^{\mathbf{x},\theta}\leq\tau^{\mathbf{x}^{\prime},\theta^{\prime}}$
whenever $\mathbf{x}\leq\mathbf{x}^{\prime},\theta\leq\theta^{\prime}$.
Monotonicity similarly holds for rightmost optimizers.

  3. 3.

Any semi-infinite optimizer $\tau$ in a direction
$\theta\in\mathcal{I}^{k}_{<}$ eventually coalesces with the $k$-tuple of
paths $\pi^{\theta}$ in the sense that
$\tau|_{(-\infty,t]}=\pi^{\theta}|_{(-\infty,t]}$ for small enough $t$.

To prove Proposition 4.3 we require two simple lemmas. For the first lemma, we
let $\pi^{\theta,y}$ denote the rightmost geodesic in direction $\theta$,
ending at $(y,1)$.

######  Lemma 4.4.

The following event holds a.s. For every $k\in\mathbb{N},a>0$ and every
compact box
$K=\prod_{i=1}^{k}[\theta_{i}^{-},\theta_{i}^{+}]\subset\mathbb{R}^{k}_{<}$
there exist vectors $\mathbf{y},\mathbf{z}\in\mathbb{Q}^{k}_{\leq}$ with
$\mathbf{y}\leq-a^{k}\leq a^{k}\leq\mathbf{z}$ such that for any $\theta\in
K$, the $k$-tuples of semi-infinite rightmost geodesics
$\pi^{\theta,\mathbf{y}}:=(\pi^{\theta,y_{1}},\dots,\pi^{\theta,y_{k}})$ and
$\pi^{\theta,\mathbf{z}}:=(\pi^{\theta,z_{1}},\dots,\pi^{\theta,z_{k}})$ are
both disjoint $k$-tuples. In particular, they are both disjoint optimizers.

###### Proof.

By induction it is enough to prove the result when $k=2$. Moreover, by
countable additivity it is enough to prove that the result for every fixed
$\theta_{i}^{-},\theta_{i}^{+}\in\mathbb{Q}$ a.s. and it is enough to prove
the existence of $\mathbf{y}$ since the existence of $\mathbf{z}$ follows by
symmetry. Finally, by monotonicity of geodesics (Theorem 4.1.3),
$\pi^{\theta,\mathbf{y}}$ is a disjoint $k$-tuple for all $\theta\in K$ if and
only if $\pi^{(\theta_{1}^{+},\theta_{2}^{-}),\mathbf{y}}$ is. We will prove
this latter statement.

For every fixed $\theta\geq 0$, the process $x\mapsto\pi^{\theta,x}(x+\cdot)$
is stationary, since the same holds for the background environment $B-B(x)$.
Therefore for any pair $\theta_{1}<\theta_{2}\in[0,\infty)$, any
$w\in\mathbb{R}$, and any function $f:(-\infty,w]\to\mathbb{R}$ with
$f(t)/|t|\to\theta_{2}$ as $t\to\infty$ a.s. there exists a random integer
$Y<w$ such that $\pi^{\theta_{1},Y}(u)<f(u)$ for $u\leq Y$. Setting
$f=\pi^{\theta_{2}^{-},-a}$ and $\mathbf{y}=(Y,-a)$, the lemma follows. ∎

######  Lemma 4.5.

The following holds almost surely. For every $k\geq
1,\theta\in\mathcal{I}^{k}_{<}$ and $a>0$, there exists $\epsilon>0$,
$\mathbf{y}\leq-a^{k}<a^{k}\leq\mathbf{z}$, and $T<y_{1}$ such that whenever
$\|\theta_{1}-\theta\|_{\infty}<\epsilon,\|\theta_{2}-\theta\|_{\infty}<\epsilon$,
we have:

  * •

For any $i=1,\dots,k$, any geodesics from $\theta_{1,i}$ to $y_{i}$ and
$\theta_{2,i}$ to $z_{i}$ are equal at time $T$.

  * •

Any geodesics from $\theta_{1,i}$ to $y_{i},i=1,\dots,k$ are mutually
disjoint. Similarly, any geodesics from $\theta_{2,i}$ to $z_{i}$,
$i=1,\dots,k$, are mutually disjoint.

For the proof of the lemma, it will be convenient to use the Hausdorff