# The directed landscape

Duncan Dauvergne  Janosch Ortmann  Bálint Virág

###### Abstract

The conjectured limit of last passage percolation is a scale-invariant,
independent, stationary increment process with respect to metric composition.
We prove this for Brownian last passage percolation. We construct the Airy
sheet and characterize it in terms of the Airy line ensemble. We also show
that last passage geodesics converge to random functions with Hölder-$2/3^{-}$
continuous paths. This work completes the construction of the central object
in the Kardar-Parisi-Zhang universality class, the directed landscape.

##  1 Introduction

Figure 1: An example of last passage across three functions. The purple path
is the last passage path from $(x,3)$ to $(y,1)$. It can be viewed as either
maximizing the sum of increments along the path, or minimizing the sum of
gaps. We will always think of our sequences of functions as being labelled so
that $f_{i}$ sits above $f_{i+1}$. Our notions of ‘right’ and ’left’ in the
paper are with respect to this picture.

For a sequence of differentiable real-valued functions
$f=(\dots,f_{-1},f_{0},f_{1},\dots)$ with domain $\mathbb{R}$, and coordinates
$x\leq y$ and $n\leq m$, define the last passage value as

$f[(x,m)\rightarrow(y,n)]=\sup_{\pi}\int_{x}^{y}f^{\prime}_{\pi(t)}(t)\,dt.$
(1)

Here the supremum is over nonincreasing functions $\pi:[x,y]\to\mathbb{Z}$
with $\pi(x)=m$ and $\pi(y)=n$. The integral is just a sum of increments of
$f$ (see Figure 1), so the same can be defined for continuous $f$, in
particular for a sequence $B$ of independent two-sided Brownian motions. This
model, Brownian last passage percolation, is a representative of a class of
models that have been the focus of intense research in recent years. By
continuity, optimizing paths exist in (1); let $\pi_{n}$ denote one for
$B[(0,n)\rightarrow(1,1)]$.

######  Theorem 1.1.

In law, as random functions in the uniform norm,

$\frac{\pi_{n}(s)-n(1-s)}{n^{2/3}}\stackrel{{\scriptstyle d}}{{\to}}\Pi(s).$

The limit $\Pi$ is the directed geodesic, a random Hölder-$2/3^{-}$ continuous
function defined in terms of a new limiting object, the directed landscape.
The directed landscape is the full four-parameter scaling limit of Brownian
last passage percolation. To describe it completely, we must first discuss the
Airy line ensemble.

The Airy line ensemble is a random sequence of functions
$\mathcal{A}_{1}>\mathcal{A}_{2}>\ldots$ constructed by Prähofer and Spohn
(2002) (see also Adler and Van Moerbeke (2005) and Corwin and Hammond (2014)).
The sequence of functions $\\{A_{i}(t)+t^{2}:i\in\mathbb{Z}\\}$ is stationary
and locally Brownian with variance $2$, as is the convention in this field.
The top line $\mathcal{A}_{1}$ is known as the Airy process (sometimes Airy2)
and describes the large-$n$ scaling limit of the function $y\mapsto
B[(0,n)\rightarrow(y,1)]$. The remaining lines also have limiting last passage
interpretations. This scaling is different from the previous version of the
present paper. This version of $\mathcal{A}$ is sometimes referred to as the
parabolic Airy line ensemble.

The Airy line ensemble doubles as the limiting eigenvalue process of Brownian
motion on Hermitian matrices. Construction of the Airy sheet, the scaling
limit of the two-parameter function $(x,y)\mapsto B[(x,n)\rightarrow(y,1)]$
(conjectured in Corwin et al. (2015)) remained open. This is partly because it
seems to be fundamentally different from random matrix limits. As our first
step in the construction of the directed landscape, we show that the Airy
sheet law is already contained in the Airy line ensemble.

######  Definition 1.2.

The Airy sheet is a random continuous function
$\mathcal{S}:\mathbb{R}^{2}\to\mathbb{R}$ so that

  1. (i)

$\mathcal{S}$ has the same law as $\mathcal{S}(\cdot+t,\cdot+t)$ for all
$t\in\mathbb{R}$.

  2. (ii)

$\mathcal{S}$ can be coupled with an Airy line ensemble so that
$\mathcal{S}(0,\cdot)=\mathcal{A}_{1}(\cdot)$ and for all
$(x,y,z)\in\mathbb{Q}^{+}\times\mathbb{Q}^{2}$ there exists a random integer
$K_{x,y,z}$ so that for all $k\geq K_{x,y,z}$ almost surely

$\mathcal{A}[(-\sqrt{k/(2x)},k)\rightarrow(z,1)]-\mathcal{A}[(-\sqrt{k/(2x)},k)\rightarrow(y,1)]=\mathcal{S}(x,z)-\mathcal{S}(x,y).$
(2)

######  Remark 1.1.

  1. 1.

We will prove later that Definition 1.2 uniquely determines a probability
measure on random continuous functions. In other words, the Airy sheet, as
defined here, exists and is unique in law.

  2. 2.

We will show in upcoming work that the Airy sheet is also the limit of
classical integrable models of last passage percolation: geometric,
exponential, and Poisson models. We expect it to be a universal limit object
in universality class of Kardar et al. (1986), see Corwin (2016) for an
informal description. We prove the Brownian last passage case in this paper.
However, one consequence of our upcoming work will be that any limiting
formula established in one of these models will apply to all others as well.

  3. 3.

Definition 1.2 is not in terms of explicit formulas for distributions, which
has been traditionally the main approach to KPZ (Kardar-Parisi-Zhang) limits.
A celebrated example of such a definition is that of the Schramm-Loewner
evolution. As is the case there, what may be more desirable than exact
formulas is a set of tools to work directly with this limiting object. Even in
the case of Brownian motion, tools such as Itô calculus and the Cameron-Martin
theorem are arguably more useful than exact formulas for the normal
distribution. In this paper we concentrate on establishing the Airy sheet and
the directed landscape as a limit; in upcoming work we use the present
description of the Airy sheet and the directed landscape to understand the
limiting geometry.

  4. 4.

Tightness for the Airy sheet limit for certain models is known (i.e. see
Pimentel (2018)); a short proof for Brownian last passage is provided in Lemma
8.4. Uniqueness of the limit is much harder, and is one of the main results of
this paper. Theorem 1.3 says that Brownian last passage percolation looks the
same on all scales in a precise sense.

  5. 5.

The process $\mathcal{S}(x,y)+(x-y)^{2}$ is stationary in both variables, and
$\mathcal{S}(0,0)$ has Tracy-Widom distribution.

  6. 6.

By monotonicity, (2) is equivalent to the following Busemann function
definition. For every triple $x,y,z\in\mathbb{R}^{+}\times\mathbb{R}^{2}$, the
left hand side of (2) converges to the right hand side as $k\to\infty$, see
Remark 8.1. Busemann functions have been used previously in last passage
percolation to study problems around infinite geodesics (i.e. see Cator and
Pimentel (2012), Georgiou et al. (2017)).

######  Theorem 1.3.

The Airy sheet exists and is unique. Moreover, for every $n$, there exists a
coupling so that

$B[(2x/n^{1/3},n)\rightarrow(1+2y/n^{1/3},1)]=2\sqrt{n}+2(y-x)n^{1/6}+n^{-1/6}(\mathcal{S}+o_{n})(x,y),$

where $o_{n}$ are random functions asymptotically small in the sense that on
every compact set $K\subset\mathbb{R}^{2}$ there exists $a>1$ with
$\mathbb{E}a^{\sup_{K}|o_{n}|^{3/2}}\to 1$.

A direct consequence of this theorem is the celebrated 1-2-3 (or KPZ) scaling
for Airy sheets. Namely define the Airy sheet of scale $s$ by

$\mathcal{S}_{s}(x,y)=s\,\mathcal{S}(x/s^{2},y/s^{2}).$

Let $\mathcal{S}_{s},\,\mathcal{S}_{t}$ be independent Airy sheets of scale
$s$ and $t$. Then the metric composition is an Airy sheet of scale $r$:

$\mathcal{S}_{r}(x,z)=\max_{y\in\mathbb{R}}\mathcal{S}_{s}(x,y)+\mathcal{S}_{t}(y,z),\qquad\text{
with }r^{3}=s^{3}+t^{3}.$

Thus the Airy sheet is an analogy of the Gaussian distribution in the metric
composition semigroup, inspiring a definition of the analogy of Brownian
motion there. It is natural to have a parameter space

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

representing increments from time $s$ to time $t$. We will think of
$\mathbb{R}^{4}_{\uparrow}$ as representing ordered pairs of points in
spacetime with a one-dimensional space. The coordinates $x$ and $y$ are
spatial and the coordinates $s$ and $t$ are temporal.

######  Definition 1.4.

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

$\mathcal{L}(x,r;y,t)=\max_{z\in\mathbb{R}}\mathcal{L}(x,r;z,s)+\mathcal{L}(z,s;y,t)\qquad\text{
for all }\;(x,r;y,t)\in\mathbb{R}^{4}_{\uparrow},\;s\in(r,t),$ (3)

and with the property that $\mathcal{L}(\cdot,t_{i};\cdot,t_{i}+s_{i}^{3})$
are independent Airy sheets of scale $s_{i}$ for any set of disjoint time
intervals $(t_{i},t_{i}+s_{i}^{3})$.

See Figure 2 for an illustration of the construction of the directed
landscape.

Figure 2: An illustration of the metric composition law for the directed
landscape/Brownian last passage percolation. The geodesic/last passage path
from $(x,r)$ to $(y,t)$ passes through a point $(z^{*},s)$ for some
$z^{*}\in\mathbb{R}$, giving that the right hand side of (3) is greater than
or equal the left. Also, for any $z\in\mathbb{R}$, a concatenation of the
geodesic from $(x,r)$ to $(z,s)$ with the geodesic from $(z,s)$ to $(y,t)$
gives a candidate for a maximizing path from $(x,r)$ to $(y,t)$, yielding the
opposite inequality. The original Brownian lines that give rise to
$\mathcal{L}(\cdot,r;\cdot,s)$ and $\mathcal{L}(\cdot,s;\cdot,t)$ are
independent. This allows us to build up $\mathcal{L}$ at any finite set of
times using metric composition with independent increments, and hence
construct the directed landscape from independent Airy sheets analogously to
the construction of Brownian motion.

######  Remark 1.2.

  1. 1.

We will prove later that Definition 1.4 uniquely determines a probability
measure on random continuous functions from $\mathbb{R}^{4}_{\uparrow}$ to
$\mathbb{R}$. So the directed landscape as defined here exists and is unique
in law.

  2. 2.

We will show in upcoming work that the directed landscape is also the limit of
classical integrable models of last passage percolation: geometric,
exponential, and Poisson models. We expect it to be a universal limit object
in the KPZ universality class, capturing all important limiting information.
We prove the Brownian last passage case in this paper. One consequence of our
upcoming work will be that any limiting formula established in one of these
models will apply to all others as well.

  3. 3.

Independent increment processes on semigroups are more complicated than those
on groups; for example, for Brownian motion, $B(s)-B(0)$ and $B(t)-B(0)$
clearly determine the increment $B(s)-B(t)$. In semigroups, the increments
cannot be computed this way and have to be specified for all pairs of times
$s<t$. This what the directed landscape does for the metric composition
semigroup.

  4. 4.

The two-time formula of Johansson (2017) gives the joint distribution of any
pair of directed landscape values of the form
$\big{(}\mathcal{L}(x,r;y_{1},s_{1}),\mathcal{L}(x,r;y_{2},s_{2})\big{)}$.
Johansson and Rahman (2019) extend this to multiple endpoints $(y_{i},s_{i})$.

  5. 5.

The KPZ fixed point of Matetski et al. (2016) is a Markov process in $t$ which
can be written in terms of the directed landscape and its initial condition
$h_{0}$ as

$h_{t}(y)=\sup_{x\in\mathbb{R}}h_{0}(x)+\mathcal{L}(x,0;y,t).$

This is not yet proven, since the KPZ fixed point is established as the limit
of TASEP, i.e. essentially exponential last passage percolation. However, it
will follow from the generalization of either Matetski et al. (2016) or the
present paper to the other model, both of which are in the works.

  6. 6.

The directed landscape contains more information than the KPZ fixed point,
namely the joint distribution of the coupled evolution for all initial
conditions. This allows for a full description of the law of limiting
geodesics as in Theorem 1.1 and the scaling limit of TASEP second class
particle trajectories which will be described in upcoming work.

  7. 7.

Since convergence to the directed landscape is uniform on compact sets and the
directed landscape is continuous, this immediately implies that last passage
values along any space-like curve converge uniformly to an Airy process.
Previous approaches to such results include finding specific determinantal
formulas for space-like curves (i.e. Borodin and Olshanski (2006), Borodin and
Ferrari (2008)) and geometric analysis of slow decorrelations (i.e. Ferrari
(2008), Corwin et al. (2012)).

  8. 8.

The negative of the directed landscape can be though of as a “signed directed
metric” on $\mathbb{R}^{2}$; it satisfies the triangle inequality for points
in the right time order. In this sense it is similar to Perelman’s
$\mathcal{L}$-distance, see Perelman (2002).

Letting $(x,s)_{n}=(s+2x/n^{1/3},-\lfloor sn\rfloor)$, the translation between
limiting and pre-limiting locations, we have the following limit theorem.

######  Theorem 1.5 (Full scaling limit of Brownian last passage).

There exists a coupling of Brownian last passage percolation and the directed
landcape $\mathcal{L}$ so that

$B_{n}[(x,s)_{n}\rightarrow(y,t)_{n}]\;\;=\;\;2(t-s)\sqrt{n}+2(y-x)n^{1/6}+n^{-1/6}(\mathcal{L}+o_{n})(x,s;y,t).$

Here each $B_{n}$ is a sequence of independent Brownian motions, and $o_{n}$
is a random function asymptotically small in the sense that on every compact
set $K\subset\mathbb{R}^{4}_{\uparrow}$ there exists $a>1$ with
$\mathbb{E}a^{\sup_{K}|o_{n}|^{3/4}}\to 1$.

We have strong control over the modulus of continuity of the directed
landscape.

######  Proposition 1.6.

Let $\mathcal{R}(x,t;y,t+s)=\mathcal{L}(x,t;y,t+s)+(x-y)^{2}/s$ denote the
stationary version of the directed landscape. Let
$K\subset\mathbb{R}^{4}_{\uparrow}$ be a compact subset. Then

$|\mathcal{R}(u)-\mathcal{R}(v)|\leq
C\left(\tau^{1/3}\log^{2/3}(\tau^{-1}+1)+\xi^{1/2}\log^{1/2}(\xi^{-1}+1)\right).$

for all $\xi,\tau>0$ and points $u,v\in K$ with spatial and temporal
coordinates of distance at most $\xi,\tau$ respectively. Here $C$ is a random
constant depending on $K$ with $\mathbb{E}a^{C^{3/2}}<\infty$ for some $a>1$.

The spatial fluctuations of $\mathcal{L}$ have been known to be locally
Brownian since Corwin and Hammond (2014). The temporal modulus of continuity
has also been previously obtained in the context of Poisson last passage
percolation, see Hammond and Sarkar (2018), building on related work from Basu
et al. (2014) and Basu et al. (2017). Rather than using such results as a
starting point for the proof of Proposition 1.6, we deduce the proposition
from explicit probability bounds on two-point differences (see Lemma 2.8 and
Lemma 10.4).

The directed landscape is a rich object containing all asymptotic information
about last passage percolation in this scaling. In particular, as advertised
above, we can take limits of last passage paths.

For a continuous path $h:[t,s]\to\mathbb{R}$, define the length of $h$ by

$\int d\mathcal{L}\circ
h=\inf_{k\in\mathbb{N}}\;\;\inf_{t=t_{0}<t_{1}<\dots<t_{k}=s}\;\;\sum_{i=1}^{k}\mathcal{L}(h(t_{i-1}),t_{i-1};h(t_{i}),t_{i+1}).$

This is the analogy of defining the length of a curve in Euclidean space by
piecewise linear approximation. We call $h$ a directed geodesic if equality
holds for all subdivisions before taking any infima. We show that with
probability one, directed geodesics exist between every pair of endpoints.

Moreover, for any fixed pair of endpoints $(x,t)$ and $(y,s)$ (but not all
endpoints simultaneously) the directed geodesic between that pair of endpoints
is almost surely unique and Hölder-$2/3^{-}$ continuous. In particular, it is
more regular than a Brownian path!

######  Theorem 1.7 (Continuity of directed geodesics).

Fix $u=(x,t;y,s)\in\mathbb{R}^{4}_{\uparrow}$. Then almost surely, there is a
unique directed geodesic $\Pi_{u}$ from $(x,t)$ to $(y,s)$. The distribution
only depends on $u$ through scaling, and for $u=(0,0;0,1)$ we have

$|\Pi_{u}(t+s)-\Pi_{u}(t)|\leq Cs^{2/3}\log^{1/3}(2/s)$

for all $s>0$ with $t,t+s\in[0,1]$. The random constant satisfies
$\mathbb{E}a^{C^{3}}<\infty$ for some $a>1$.

Let $\pi_{n,(x,s,y,t)}$ be a path from $(x,s)_{n}$ to $(y,t)_{n}$ that
maximizes (1). We also show that the joint limit of last passage paths is
given by the joint distribution of directed geodesics. Since each last passage
path $\pi_{n,(x,s,y,t)}$ has domain $[s+2xn^{-1/3},t+2yn^{-1/3}]$, we need to
first compose $\pi_{n}$ with the affine shift $h_{n,(x,s,y,t)}$ that maps the
interval $[s,t]$ to $[s+2xn^{-1/3},t+2yn^{-1/3}]$ to talk about convergence to
$\Pi_{(x,s,y,t)}$.

######  Theorem 1.8 (Convergence of last passage paths).

In the coupling of Theorem 1.5 there exists a set $A$ of probability 1 such
that the following holds. For $u\in\mathbb{R}^{4}_{\uparrow}$, let $C_{u}$ be
the set where the directed geodesic $\Pi_{u}$ is unique in $\mathcal{L}$. Then
for any $u\in\mathbb{R}^{4}_{\uparrow}$, we have that

$\frac{\pi_{n,u}\circ h_{n,u}+nh_{n,u}}{n^{2/3}}\to\Pi_{u}\quad\text{
uniformly, on the event $A\cap C_{u}$}.$

Our approach to the proofs is probabilistic. It is based on understanding the
geometry of last passage percolation using a continuous version of the
Robinson-Schensted-Knuth (RSK) correspondence. Interestingly, our reliance on
formulas is minimal – we only use estimates about the Airy line ensemble from
the paper Dauvergne and Virág (2018), which relies solely on the determinantal
nature of the Airy point process and the Brownian Gibbs property of the Airy
line ensemble. On the other hand, our results easily imply convergence of
formulas. The super-exponential control of the error term in Theorem 1.3
guarantees, for example, uniform convergence of moment generating functions.

The key observation for our proof is a combinatorial fact about the RSK
correspondence, whose application to Brownian paths was developed in O’Connell
and Yor (2002). The continuous RSK correspondence maps an $n$-tuple of
continuous functions $f:[0,1]\times\\{1,\ldots,n\\}\to\mathbb{R},(x,i)\mapsto
f_{i}(x)$ to $Wf$ in the same space, which we call the melon of $f$. The
functions in the melon are ordered decreasingly. The main property used in the
last passage literature is that the melon satisfies

$(Wf)_{1}(t)=f[(0,n)\rightarrow(t,1)].$

We use the stronger fact that for any $s<t$, remarkably

$Wf[(s,n)\rightarrow(t,1)]=f[(s,n)\rightarrow(t,1)].$

This formula also holds for $k$ disjoint paths with arbitrary start and end
points $(s_{i},n),(t_{i},1)$ for $i=1,\dots,k$, see Proposition 4.1. A version
of this formula in the special case when $s_{i}=0$ for all $i$ was previously
obtained and studied in the context of geometric RSK by O’Connell and Warren
(2016). The formula is also closely related to the semigroup property of the
plactic monoid, see Chapter 2 of Fulton (1997).

Note that with $B$ restricted to the first $n$ lines, $WB$ has the law of
Brownian motions conditioned not to intersect; these converge to the Airy line
ensemble in the right scaling. So one might hope that the last passage problem
in $WB$ converges to a last passage problem in the Airy line ensemble. This
seems incredible at first because lot of the last passage is taking place in
parts of the melon that disappear in the limit. Indeed, the limit only sees
the top few lines and a time window of order $n^{-1/3}$.

The technical part of the proof is to show that the last passage path from
$(2xn^{-1/3},n)$ to $(1,1)$ in $WB$ follows a parabola of the form
$k\mapsto(1-2\sqrt{k/(2x)}n^{-1/3},k)$. We do this by analyzing a last passage
problem on the Airy line ensemble. Now for nearby $x,x^{\prime}$ the parabolas
diverge as $k\to\infty$ while the last passage values should be close. This
suggests that there is not much information contained in these paths away from
the top corner. We turn this intuition into a proof in Section 6.

The directed landscape can be patched together from Airy sheets. For the
convergence of last passage percolation to the directed landscape, there is a
technical tightness issue that we handle in Section 11.

The focus of this paper is to construct the limiting objects, and we do not
explore their properties in detail here. However, our description makes
several natural questions about the directed landscape accessible. We will
analyze the geometry of this object in future work.

Our results complete the construction of the central object in the Kardar-
Parisi-Zhang universality class. Although the full construction is new,
several aspects of the directed landscape have been studied previously. This
is a very partial review of the literature, with results most directly related
to the present work. For a gentle introduction suitable for a newcomer to the
area, see Romik (2015). Review articles and books focusing on more recent
developments include Corwin (2016), Ferrari and Spohn (2010), Quastel (2011),
Takeuchi (2018) and Weiss et al. (2017).

The Baik et al. (1999) proof for the length of the longest increasing
subsequence was the first to give the single point distribution of
$\mathcal{L}$ as Tracy-Widom in a slightly different model, see also Johansson
(2000a). Baryshnikov (2001) and Gravner et al. (2001) showed this convergence
for Brownian last passage percolation by establishing showing that
$B[(0,n)\to(1,1)]$ is equal in law to the top eigenvalue of the Gaussian
Unitary Ensemble. As discussed above, this connection was extended to all
eigenvalues at the level of a last passage process by O’Connell and Yor
(2002).

Prähofer and Spohn (2002) proved convergence of last passage values to
$\mathcal{L}(0,0;y,1)$ jointly for different values of $y$. This the top line
of the Airy line ensemble. Corwin et al. (2013) extended the analysis to
continuum statistics of functions of $y$. Corwin and Hammond (2014) showed the
Brownian Gibbs property of the Airy line ensemble, making it more accessible
to probabilistic analysis. Corwin et al. (2015) predicted many of the results
of the present paper.

After predictions by Dotsenko (2013), Johansson (2017, 2018) gave the joint
distribution of $\mathcal{L}(a,b),\mathcal{L}(a,c)$ for fixed $a,b,c$.
Matetski et al. (2016) derived a formula for the distribution of
$g\mathcal{S}$, the metric composition of a fixed function $g$ and the Airy
sheet $\mathcal{S}$. Baik and Liu (2019) found formulas for the joint
distribution of $\\{\mathcal{L}^{\prime}(a,b_{i}):i\in\\{1,\dots,k\\}\\}$ for
any fixed $a,b_{1},\dots,b_{k}$ for a related limiting object
$\mathcal{L}^{\prime}$ that in our language would be the directed landscape on
the cylinder. We note the conjectured limit $\mathcal{L}^{\prime}$ can be
described by wrapping the directed landscape $\mathcal{L}$ around the cylinder
and redefining path lengths locally. Recently, Johansson and Rahman (2019)
proved formulas analogous to those of Baik and Liu with $\mathcal{L}$ in place
of $\mathcal{L}^{\prime}$.

More probabilistic and geometric methods have been used by various authors in
conjunction with integrable inputs to prove qualitative statements about
limits of last passage percolation. As an early example, Johansson (2000b)
studied transversal fluctuations. More recently, Pimentel (2018) showed
tightness of the Airy sheet in a different model, and that the Airy sheet
locally looks like a sum of independent Brownian motions. Ferrari and Occelli
(2019) analyzed the covariance of last passage values at two different times.
Other examples include Basu et al. (2014), Basu et al. (2017), and Hammond and
Sarkar (2018) discussed above.

Hammond (2016) used a probabilistic approach to prove Radon-Nikodym derivative
and other regularity bounds for parts of the Airy line ensemble with respect
to Brownian bridges. Subsequent papers (see Hammond (2017b, a, c)) combined
this work with geometric reasoning to understand problems about the geometry
of last passage paths in Brownian last passage percolation and the roughness
of limiting growth profiles in that model.

We also need a strong probabilistic understanding of the Airy line ensemble in
order to prove Theorem 1.3. For this we use results from Dauvergne and Virág
(2018), which for our purposes provide stronger quantitative control than the
results of Hammond discussed above.

##  2 Preliminaries

###  2.1 Last passage across general functions

For an interval $I\subset\mathbb{Z}$, let $C^{I}$ be the space of all
continuous functions

$f:\mathbb{R}\times I\to\mathbb{R},\qquad(x,i)\mapsto f_{i}(x).$

We will often think of $f$ as a sequence of functions $\\{f_{i}:i\in I\\}$.
When $I=\\{1,\dots,n\\}$, we will simply write $C^{n}$. We call a
nonincreasing function $\pi:[x,y]\to I$ which is cadlag on $(x,y)$ and
satisfies $\pi(x)=\ell$ and $\pi(y)=m$ a path from $(x,\ell)$ to $(y,m)$. Our
paths are nonincreasing instead of nondecreasing to accommodate the natural
indexing of the Airy line ensemble.

We define the length of $\pi$ with respect to a coordinatewise differentiable
function $f\in C^{I}$ by

$\int df\circ\pi:=\int_{x}^{y}f^{\prime}_{\pi(t)}(t)dt.$

For each $\pi$, this is just a sum of increments of $f$, so this definition
extends to all continuous $f$. Now for $x\leq y\in\mathbb{R}$ and $m<\ell\in
I$ we define the last passage value of $f$ from $(x,\ell)$ to $(y,m)$ by

$f[(x,\ell)\to(y,m)]=\sup_{\pi}\int df\circ\pi,$

where the supremum is taken over all paths $\pi$ from $(x,\ell)$ to $(y,m)$.
See Figure 1 for an illustration of this definition. We say that a point
$(x,t)$ lies along a path $\pi:[s,r]\to\mathbb{Z}$ if $t\in[s,r]$ and if

$\lim_{q\to t^{-}}\pi(q)\geq x\geq\lim_{q\to t^{+}}\pi(q).$

In other words, if the graph of $\pi$ is connected at its jumps by vertical
lines, then $(x,t)$ will lie on this connected version of the graph.

For $f\in C^{I}$, define the gap process $g=g(f)$ by $g_{i}=f_{i}-f_{i+1}$. We
can alternately define path length in terms of the gap process. For a non-
increasing path $\pi$ from $(x,\ell)$ to $(y,m)$, we have

$\int df\circ\pi=f_{m}(y)-f_{\ell}(x)-\sum_{i=m}^{\ell-1}g_{i}(t_{i}),$ (4)

where the times $t_{i}$ correspond to the jumps of the path $\pi$. Thus the
last passage value can be thought of as a difference of endpoints minus a
minimal sum of gaps. This definition will be useful when we deal with non-
intersecting sets of lines $f\in C^{I}$ whose gap processes are non-negative.

We now extend the definition of last passage to disjoint collections of paths.
Let

$U=\\{(x_{i},\ell_{i}):i\in\\{1,\dots k\\}\\}\qquad\;\text{and}\;\qquad
V=\\{(y_{i},m_{i}):i\in\\{1,\dots k\\}\\}$

be two sequences of ordered pairs in $\mathbb{R}\times I$ with $x_{i}\leq
y_{i}$ and $m_{i}\leq\ell_{i}$ for all $i$. The points $x_{i}$ and $y_{i}$
will be endpoints of disjoint paths $\pi_{i}$ with range
$\\{m_{i},\dots,\ell_{i}\\}$. Define $\mathcal{Q}(U,V)$ to be the set of
$k$-tuples of functions $\mathbf{\pi}=(\pi_{1},\dots,\pi_{k})$ satisfying the
following conditions:

  1. (i)

For all $i\in\\{1,\dots,k\\}$, the function $\pi_{i}$ is a path from
$(x_{i},\ell_{i})$ to $(y_{i},m_{i})$.

  2. (ii)

For all $i\in\\{1,\dots,k-1\\}$, we have that $\pi_{i}(t)<\pi_{i+1}(t)$ for
all $t\in(x_{i},y_{i})\cap(x_{i+1},y_{i+1})$. In order to ensure existence of
last passage paths, we do not enforce a disjointness condition at the
endpoints. This guarantees that the set $\mathcal{Q}(U,V)$ is closed in a
natural topology on paths (we define this precisely in Lemma 3.4).

We refer to elements of $\mathcal{Q}(U,V)$ as paths from $U$ to $V$. For a
path $\pi\in\mathcal{Q}(U,V)$, we define the length of $\pi$ with respect to
$f$ by

$\int df\circ\pi=\sum_{i=1}^{k}\;\int df\circ\pi_{i}.$

With the above definition of $\mathcal{Q}(U,V)$, we say that $(U,V)$ is an
endpoint pair if the following conditions hold. For this definition
$U=\\{(x_{i},\ell_{i})\\}_{i\in\\{1,\dots,k\\}}$ and
$V=\\{(y_{i},m_{i})\\}_{i\in\\{1,\dots,k\\}}$.

  1. (i)

For all $i\in\\{1,\dots,k\\}$, we have that $x_{i}<y_{i}$ and
$\ell_{i}>m_{i}$.

  2. (ii)

For all $i\in\\{1,\dots k-1\\}$, we have that $x_{i}\leq x_{i+1}$ and
$y_{i}\leq y_{i+1}$.

  3. (iii)

The set of paths $\mathcal{Q}(U,V)$ is non-empty.

For an endpoint pair $(U,V)$ and a function $f\in C^{I}$, we define the last
passage value of $f$ across $(U,V)$ by

$f[U\rightarrow V]=\sup_{\pi\in\mathcal{Q}(U,V)}\;\int df\circ\pi.$

In the case when $k=1$, we recover the previous definition of the last passage
path.

We also define the set of last passage paths between
$U=\\{(x_{i},\ell_{i})\\}_{i\in\\{1,\dots,k\\}}$ and
$V=\\{(y_{i},m_{i})\\}_{i\in\\{1,\dots,k\\}}$ by

$P_{f}[U,V]=\left\\{\pi\in\mathcal{Q}(U,V):\int
df\circ\pi=\sup_{\sigma\in\mathcal{Q}(U,V)}\;\int df\circ\sigma\right\\}.$

We will omit the subscript $f$ above when the function $f$ is clear from
context or does not change throughout a proof.

###  2.2 Melons

Let $C^{n}_{+}$ be the space of continuous functions

$f:[0,\infty)\times\\{1,\dots,n\\}\to\mathbb{R},(x,i)\mapsto f_{i}(x).$

For $f\in C^{n}_{+}$, we can define a function $Wf\in C^{n}_{+}$ by the
formula

$\sum_{i=1}^{k}(Wf)_{i}(t)=f[(0,n)^{k}\rightarrow(t,1)^{k}],\qquad\qquad\text{
for all }k\in\\{1,\dots,n\\},t\in[0,\infty).$

Here $(s,i)^{k}$ is the sequence with $k$ copies of the points $(s,i)$. The
function $Wf$ can be thought of as the recording tableau of a continuous
version of the Robinson-Schensted-Knuth bijection. We call $Wf$ the melon of
$f$. We will explore the process of constructing melons more in Section 4.
Paths in the melon $Wf$ are ordered so that
$(Wf)_{1}\geq(Wf)_{2}\geq\dots\geq(Wf)_{n}$ (at the level of finite RSK, this
is a consequence of the Young tableaux inequalities). This is where the term
melon comes from: since paths in $Wf$ avoid each other and all start from $0$,
they look like stripes on a watermelon.

###  2.3 Brownian last passage percolation and the Airy line ensemble

We now introduce the main object of study in this paper, Brownian last passage
percolation. See Weiss et al. (2017) for background on the integrable aspects
of this model. Let $B\in C^{\mathbb{Z}}$ be a sequence of independent two-
sided Brownian motions. Let $B^{n}$ be $B$ restricted to
$\mathbb{R}^{+}\times\\{1,\ldots\,n\\}$. We are concerned with finding limits
of last passage values across the sequence $B$. By a result in Section 4, we
will be able to relate these last passage values values to last passage values
across the Brownian $n$-melon $WB^{n}$.

There are many remarkable descriptions of the Brownian $n$-melon $WB^{n}$. The
description that will be most useful to us here is that $WB^{n}$ can be
described as the distributional limit as $\epsilon\to 0$ of a sequence of $n$
independent Brownian motions $B^{i}_{\epsilon}:[0,1/\epsilon]\to\mathbb{R}$
with $B^{i}_{\epsilon}(0)=i\epsilon$ conditioned so that

$B^{1}_{\epsilon}(t)>B^{2}_{\epsilon}(t)>\dots>B^{n}_{\epsilon}(t).$

This was first proven by O’Connell and Yor (2002), see also Biane et al.
(2005). The top lines of the Brownian $n$-melon have a scaling limit known as
the Airy line ensemble. This next theorem was proven in many parts, see
Prähofer and Spohn (2002), Johansson (2003), Adler and Van Moerbeke (2005),
Corwin and Hammond (2014).

######  Theorem 2.1.

Let $WB^{n}$ be a Brownian $n$-melon. Define the rescaled melon
$A^{n}=(A^{n}_{1},\dots,A^{n}_{n})$ by

$A^{n}_{i}(y)=n^{1/6}\left((WB^{n})_{i}(1+2yn^{-1/3})-2\sqrt{n}-2yn^{1/6}\right).$

Then $A^{n}$ converges to a random sequence of functions
$\mathcal{A}=(\mathcal{A}_{1},\mathcal{A}_{2},\dots)\in C^{\mathbb{N}}$ in law
with respect to product of uniform-on-compact topology on $C^{\mathbb{N}}$.
For every $y\in\mathbb{R}$ and $i<j$, we have that
$\mathcal{A}_{i}(y)>\mathcal{A}_{j}(y)$. The function $\mathcal{A}$ is called
the Airy line ensemble.

Figure 3: A ‘Brownian melon’ from time $0$ to time $1$. If we zoom in around
the location $(1,2\sqrt{n})$ on a $O(n^{-1/3})\times O(n^{-1/6})$ box, then we
get the Airy line ensemble.

The shifted line ensemble $\mathcal{R}(y)=\mathcal{A}(y)+y^{2}$ is stationary
in time. We will refer to this object as the stationary Airy line ensemble.

The top line of the Airy line ensemble is known as the Airy process (also
called the Airy2 process). We now collect a few key facts about the Airy line
ensemble and the Airy process. For this proposition and throughout the paper,
we say that a Brownian motion (or bridge, or melon) has variance $v$ if its
quadratic variation in an interval $[s,t]$ is proportional to $v(t-s)$.

######  Proposition 2.2.

Fix an interval $[a,a+b]\subset\mathbb{R}$ and $k\in\mathbb{N}$, and define
$B_{i}(t)=\mathcal{A}_{i}(a+t)-\mathcal{A}_{i}(a)$ for $i\in\\{1,\dots,k\\}$.
Then on the interval $[0,b]$ the sequence $(B_{1},\dots,B_{k})$ is absolutely
continuous with respect to the law of $k$ independent Brownian motions with
variance $2$.

The one-point distribution of times in the Airy process can be described by
the Tracy-Widom distribution (also called the Tracy-Widom GUE distribution).
This fact will be used throughout the paper, so we state it here as a theorem.
See Ramirez et al. (2011) for short proofs of the tail bounds.

######  Theorem 2.3.

[Tracy and Widom (1994)] Let $\mathcal{R}$ denote the stationary Airy line
ensemble. For every $t\in\mathbb{R}$, the random variable $\mathcal{R}_{1}(t)$
has Tracy-Widom distribution. In particular, it satisfies the tail bounds

$\mathbb{P}(\mathcal{R}_{1}(t)>m)\leq
ce^{-dm^{3/2}}\quad\;\text{and}\;\quad\mathbb{P}(\mathcal{R}_{1}(t)<-m)\leq
ce^{-dm^{3}}$

for universal constants $c$ and $d$.

We will also use the following bound on two-point distributions of the Airy
process.

######  Lemma 2.4 (Dauvergne and Virág (2018), Lemma 6.1).

There are constants $c,d>0$ such that for every $t\in\mathbb{R},s>0,$ and
$a>7s^{3/2}$, the stationary Airy process $\mathcal{R}_{1}$ satisfies

$\mathbb{P}(|\mathcal{R}_{1}(t)-\mathcal{R}_{1}(t+s)|>a\sqrt{s})\leq
ce^{-da^{2}}.$

Finally, we will also need the finite versions of Theorem 2.3 and Lemma 2.4,
as well as a proposition bounding the entire Brownian $n$-melon below a
particular function.

######  Theorem 2.5 (Ledoux and Rider (2010)).

Let $W^{n}_{1}$ be the top line of a Brownian $n$-melon. There exist constants
$c$ and $d$ such that for all $m>0$ and all $n\geq 1$ we have

$\mathbb{P}(|W^{n}_{1}(1)-2\sqrt{n}|\geq mn^{-1/6})\leq ce^{-dm^{3/2}}.$

######  Proposition 2.6 (Dauvergne and Virág (2018), Proposition 4.1).

Fix $a>0$. There exist constants $c,d>0$ such that for every $n\in\mathbb{N}$,
$t>0,\;s\in[0,atn^{-1/3}]$, and $m>0$ we have

$\mathbb{P}\bigg{(}\left|W_{1}^{n}(t)-W_{1}^{n}(t+s)-s\sqrt{n/t}\right|>m\sqrt{s}\bigg{)}\leq
ce^{-dm^{3/2}}.$

######  Proposition 2.7 (Dauvergne and Virág (2018), Proposition 4.3).

There exist positive constants $b,c,$ and $d$ such that for all $m>0$ and
$n\geq 1$, with probabity at least $1-ce^{-dm^{3/2}}$ we have

$W^{n}_{1}(t)\leq
2\sqrt{nt}+\sqrt{t}n^{-1/6}[m+b\log^{2/3}(n^{1/3}\log(t\;\vee\;t^{-1})+1)]\;\;\text{
for all }t\in[0,\infty).$

Here $a\vee b$ is the maximum of $a$ and $b$.

###  2.4 Modulus of Continuity

In order to construct many of the objects in the paper, we will need a way of
translating tail bounds on two-point differences into modulus of continuity
bounds. For this, we use the Lemma 3.3 from Dauvergne and Virág (2018). This
lemma should be thought of as a generalized version of Lévy’s modulus of
continuity for Brownian motion.

######  Lemma 2.8.

Let $T=I_{1}\times\dots\times I_{d}$ be a product of bounded real intervals of
length $b_{1},\dots,b_{d}$. Let $c,a>0$. Let $\mathcal{H}$ be a random
continuous function from $T$ taking values in a vector space $V$ with norm
$|\cdot|$. Assume that for every $i>0$, there exists
$\alpha_{i}\in(0,1),\beta_{i},r_{i}>0$ such that

$\mathbb{P}(|\mathcal{H}(t+e_{i}r)-\mathcal{H}(t)|\geq mr^{{\alpha_{i}}})\leq
ce^{-a{m^{{\beta_{i}}}}}$ (5)

for every coordinate vector $e_{i}$, every $m>0$ with $t,t+re_{i}\in T$ and
$r<r_{i}$. Set $\beta=\min_{i}\beta_{i},\alpha=\max_{i}\alpha_{i}$, and
$b=\max_{i}b$. Then with probability one we have

$|\mathcal{H}(t+s)-\mathcal{H}(t)|\leq
C\left(\sum_{i=1}^{d}|s_{i}|^{\alpha_{i}}\log^{1/\beta_{i}}\left(\frac{2b^{\alpha/\alpha_{i}}}{|s_{i}|}\right)\right),$
(6)

for every $t,t+s\in T$ with $|s_{i}|\leq r_{i}$ for all $i$. Here $C$ is
random constant satisfying

$\mathbb{P}(C>m)\leq cc_{0}e^{-c_{1}m^{\beta}},$

where $c_{0}$ and $c_{1}$ are constants that depend on
$\alpha_{1},\dots\alpha_{d},\beta_{1},\dots,\beta_{d},d$ and $a$. Notably,
they do not depend on $b$ or $c$.

###  2.5 Notation

We now introduce notation for last passage values across Brownian motions,
Brownian melons, and the Airy line ensemble. This notation will be used
throughout the paper starting in Section 6. Letting $B\in C^{\mathbb{Z}}$ be a
sequence of independent two-sided Brownian motions, we first define

$\displaystyle[x\rightarrow y]_{n}$ $\displaystyle:=B[(x,n)\rightarrow(y,1)],$

where $(x,n)^{k}$ is the sequence of $(x,n)$ exactly $k$ times. We will often
omit the subscript $n$ from the brackets and simply write $[x\rightarrow y]$
when the value of $n$ is clear from context. We will also use the mixed
notation

$[(x,k)\rightarrow
y]_{n}:=B[(x,k)\rightarrow(y,1)]\quad\;\text{and}\;\quad[x\rightarrow(y,k)]_{n}:=B[(x,n)\rightarrow(y,k)].$

For last passage values in the melon $WB^{n}$, we will use all the same
notation with curly brackets $\\{\;\\}$ in place of square ones $[\;]$. We
will also use angled brackets $\langle\;\rangle$ for last passage values
across the stationary Airy line ensemble:

$\langle(x,k)\rightarrow y\rangle:=\mathcal{A}[(x,k)\rightarrow(y,1)].$

We will write $\pi\\{x,y\\}$ for the rightmost last passage path in $WB^{n}$
from $(x,n)$ to $(y,1)$. Here a last passage path $\pi$ is ‘rightmost’ if
$\pi\geq\tau$ for any other last passage path $\tau$, see Lemma 3.5. We
similarly write $\pi[x,y]$ be the rightmost last passage path in $B^{n}$ from
$(x,n)$ to $(y,1)$.

To avoid carrying around $n^{-1/3}$ spatial terms, we will often use the
notation

$\bar{x}=2xn^{-1/3}\quad\;\text{and}\;\quad\hat{y}=1+2yn^{-1/3}$

when the value of $n$ is clear from context.

##  3 The geometry of last passage paths

Last passage paths can be thought of as geodesics in a metric space. This is a
guiding principle for many of the proofs in the paper. With this intuition in
mind, we devote this section to stating and proving some basic facts about the
geometry of last passage paths. Many of these facts are well-known and well-
used in the context of last passage percolation, but we nonetheless include
proofs here for completeness and clarity.

For the rest of this section, let $f\in C^{\mathbb{Z}}$. The first lemma
states that last passage paths have the geodesic property that they maximize
length between any two points on the path. Its proof is straightforward and
hence omitted.

######  Lemma 3.1.

(Geodesic Property) Let $((x,\ell),(y,m))$ be an endpoint pair of single
points. Then for any $\pi$ in the set of last passage paths
$P_{f}[(x,\ell),(y,m)]$, and any times $s<t\in[x,y]$, we have that

$\int_{s}^{t}fd\pi=\max\left\\{\int_{s}^{t}fd\tau:\;\;\tau\text{ is a path
from }(s,\pi(s))\text{ to }(t,\pi(t))\right\\}.$

The next fact is a straightforward consequence of Lemma 3.1. Its proof is
again omitted.

######  Lemma 3.2.

(Metric Composition Law) Let $((x,\ell),(y,m))$ be an endpoint pair of single
points. Then for any $k\in\\{m,\dots,\ell\\}$, we have that

$\displaystyle f[(x,\ell)\rightarrow(y,m)]$
$\displaystyle=\sup_{z\in[x,y]}f[(x,\ell)\rightarrow(z,k)]+f[(z,k)\rightarrow(y,m)]$
$\displaystyle=\sup_{z\in[x,y]}f[(x,\ell)\rightarrow(z,k)]+f[(z,k-1)\rightarrow(y,m)].$

Lemma 3.2 implies a triangle inequality for last passage values. For any
$x\leq z\leq y$ we have

$f[(x,\ell)\rightarrow(y,m)]\geq
f[(x,\ell)\rightarrow(z,k)]+f[(z,k)\rightarrow(y,m)].$ (7)

It will also be useful to understand the right hand side above as a function
of $z$.

######  Lemma 3.3.

Let $((x,\ell),(y,m))$ be an endpoint pair and fix $k\in\\{m,\dots,\ell\\}$.
For $z\in[x,y]$, define

$h_{1}(z)=f[(x,\ell)\rightarrow(z,k)]-f_{k}(z)\quad\;\text{and}\;\quad
h_{2}(z)=f[(z,k)\rightarrow(y,m)]+f_{k}(z).$

Then

$f[(x,\ell)\rightarrow(y,m)]=\sup_{z\in[x,y]}h_{1}(z)+h_{2}(z),$

the function $h_{1}$ is monotone increasing and the function $h_{2}$ is
monotone decreasing.

###### Proof.

The representation of $f[(x,\ell)\rightarrow(y,m)]$ as a supremum over
$h_{1}+h_{2}$ follows immediately from Lemma 3.2. To see that $h_{1}$ and
$h_{2}$ are monotone, observe that each is equal to a fixed term that is
independent of $z$ minus an infimum over a sum of gaps (see the alternate
definition of length in (4)). The size of the set over which this infimum is
being taken is increasing in $z$ for $h_{1}$ and decreasing in $z$ for
$h_{2}$, implying monotonicity. ∎

For a $k$-tuple of paths $\pi=(\pi_{1},\dots,\pi_{k})$ with range in
$\mathbb{Z}$, define the graph

$\Gamma(\pi)=\left\\{(t,\pi_{i}(t))\in\mathbb{R}\times\mathbb{Z}:i\in\\{1,\dots,k\\},t\text{
in the domain of $\pi_{i}$}\right\\}\subset\mathbb{R}\times\mathbb{Z}.$

We then define a metric $d_{k}$ between $k$-tuples of paths by setting
$d_{k}(\pi,\tau)$ to be the Lebesgue measure of the symmetric difference
$\Gamma(\pi)\triangle\Gamma(\tau)$. We call the topology induced by this
metric the graph topology on $k$-tuples of paths.

The following lemma is then immediate from the definition of the graph
topology, since length is a continuous function in this space and the set of
paths $\mathcal{Q}(U,V)$ is closed for any endpoint pair $(U,V).$

######  Lemma 3.4.

For any endpoint pair $(U,V)$, the set $P[U,V]$ is closed in the graph
topology.

The next lemma shows that in the set $P[(x,\ell),(y,m)]$ we can pick out
rightmost and leftmost paths.

######  Lemma 3.5.

Let $((x,\ell),(y,m))$ be an endpoint pair. There exist paths
$\pi^{-},\pi^{+}\in P[(x,\ell),(y,m)]$ such that for any $\pi\in
P[(x,\ell),(y,m)]$ and any $z\in[x,y]$ we have

$\pi^{-}(z)\leq\pi(z)\leq\pi^{+}(z).$

We refer to $\pi^{-}$ as the leftmost last passage path and $\pi^{+}$ as the
rightmost last passage path.

###### Proof.

Since the set of last passage paths is closed (Lemma 3.4), it suffices to show
that for any paths $\pi_{1},\pi_{2}\in P[(x,\ell),(y,m)]$, that there exist
paths $\tau_{1},\tau_{2}\in P[(x,\ell),(y,m)]$ such that

$\tau_{1}(z)\leq\pi_{i}(z)\leq\tau_{2}(z)\quad\text{ for }i=1,2.$

For each $z\in[x,y]$, define $\tau_{1}(z)\leq\tau_{2}(z)$ to be the order
statistics of $(\pi_{1}(z),\pi_{2}(z))$. It can be checked that
$\tau_{1},\tau_{2}\in\mathcal{Q}((x,\ell),(y,m))$. Also,

$\int df\circ\tau_{1}+\int df\circ\tau_{2}=\int df\circ\pi_{1}+\int
df\circ\pi_{2},$

since the paths $\tau_{1}$ and $\tau_{2}$ cover the same parts of lines in $f$
as $\pi_{1}$ and $\pi_{2}$. Since the paths $\pi_{1}$ and $\pi_{2}$ maximize
length in the set $\mathcal{Q}((x,\ell),(y,m))$, each of the paths $\tau_{i}$
must maximize length as well. ∎

Rightmost and leftmost last passage paths also exhibit a monotonicity property
in their endpoints. We only state this lemma for single paths, as this is how
we will use it.

######  Lemma 3.6.

(Monotonicity of last passage paths) For $x\leq y$, let $\pi^{+}[x,y]$ denote
the rightmost last passage path in $P[(x,n),(y,1)]$. Then $\pi^{+}[x,y]$ is a
monotone increasing, right continuous function of both $x$ and $y$ in the
graph topology on paths.

Similarly $\pi^{-}[x,y]$ is a monotone decreasing, left continuous function of
both $x$ and $y$.

###### Proof.

Right continuity is clear by continuity of length in the graph topology, so it
suffices to prove monotonicity. Let $x_{1}\leq x_{2}$ and $y_{1}\leq y_{2}$.
For $z\in[x_{2},y_{1}]$, let $\tau_{1}(z)\leq\tau_{2}(z)$ be the order
statistics of

$(\pi^{+}[x_{1},y_{1}](z),\pi^{+}[x_{2},y_{2}](z)).$

To prove monotonicty, it is enough to show that
$\tau_{i}=\pi^{+}[x_{i},y_{i}]$ for $i=1,2$ on the interval $[x_{2},y_{1}]$.
We can extend $\tau_{1}$ to the interval $[x_{1},x_{2}]$ by defining it to be
equal to $\pi^{+}[x_{1},y_{1}]$ there and similarly extend $\tau_{2}$ to
$[y_{1},y_{2}]$ by setting it to be equal to $\pi^{+}[x_{2},y_{2}]$. We have
that $\tau_{i}\in\mathcal{Q}((x_{i},n),(y_{i},1))$ for $i=1,2$. Moreover,

$\int df\circ\tau_{1}+\int df\circ\tau_{2}=\int
df\circ\pi^{+}[x_{1},y_{1}]+\int df\circ\pi^{+}[x_{2},y_{2}].$

Since $\pi^{+}[x_{1},y_{1}]$ and $\pi^{+}[x_{2},y_{2}]$ maximize weight, we
have that $\tau_{i}\in P[(x_{i},n),(y_{i},1)]$ for $i=1,2$. Moreover,
$\tau_{2}\geq\pi^{+}[x_{2},y_{2}]$ by construction. Since
$\pi^{+}[x_{2},y_{2}]$ is a rightmost last passage path, this is in fact
equality. Hence $\tau_{1}=\pi^{+}[x_{1},y_{1}]$ as well. ∎

We now show that paths exhibit a tree structure.

######  Proposition 3.7.

Let $x_{1}\leq x_{2}\leq y_{1}\leq y_{2}$ be points in $\mathbb{R}$. Let
$\pi^{+}[x_{i},y_{i}]$ denote the rightmost last passage path in
$\mathcal{Q}((x_{i},n),(y_{i},1))$. Then there is a (possibly empty) interval
$[a,b]\subset[x_{2},y_{1}]$ such that the following holds.

  1. (i)

$\pi^{+}[x_{1},y_{1}](s)=\pi^{+}[x_{2},y_{2}](s)\text{ for all }s\in[a,b).$

  2. (ii)

$\pi^{+}[x_{1},y_{1}](s)<\pi^{+}[x_{2},y_{2}](s)\text{ for all
}s\in[x_{2},y_{1}]\setminus[a,b].$

The discrepancy at the endpoint $b$ is due to the fact that the paths are
cadlag; it has no true role. In particular, if $x_{1}=x_{2}$, then the last
passage paths to $y_{1}$ and $y_{2}$ follow the same path up to time $b$, and
are entirely disjoint afterwards (so they form two branches in a tree).

The same tree structure holds for $\pi^{-}$ in place of $\pi^{+}$.

###### Proof.

Let

$I=\\{t\in[x_{2},y_{1}]:\pi[x,y_{1}](s)=\pi[x,y_{2}](s)\\},$

and define $b=\sup I$ and $a=\inf I.$ Since both $\pi^{+}[x_{1},y_{1}]$ and
$\pi^{+}[x_{2},y_{2}]$ are rightmost last passage paths, the geodesic property
of last passage paths (Lemma 3.1) implies that $\pi^{+}[x_{i},y_{i}]|_{[a,b)}$
is a rightmost last passage path between the points

$(a,\pi^{+}[x_{i},y_{i}](a))\quad\;\text{and}\;\quad(b,\lim_{z\to
b^{-}}\pi^{+}[x_{i},y_{i}](z)).$

Since these points are the same for $i=1,2$ by the definition of $b$ and $a$,
this implies that
$\pi^{+}[x_{1},y_{1}]|_{[a,b)}=\pi^{+}[x_{2},y_{2}]|_{[a,b)}.$ Combining this
with monotonicity (Lemma 3.6) proves the lemma. ∎

We end this section with a monotonicity proposition for sums of last passage
values.

######  Proposition 3.8.

Let $x=(x_{1},n),y=(y_{1},1)$ and define $x^{\prime}$,$y^{\prime}$ similarly.
Assume $x_{1}\leq x_{1}^{\prime}<y_{1}\leq y_{1}^{\prime}\in\mathbb{R}$. Then

$f[x\rightarrow y]+f[x^{\prime}\rightarrow y^{\prime}]\geq f[x\rightarrow
y^{\prime}]+f[x^{\prime}\rightarrow y].$

###### Proof.

By the ordering on the points, there must exist a point $z=(t,k)$ that lies
along both the rightmost last passage paths from $x$ to $y^{\prime}$ and
$x^{\prime}$ to $y$. The result is then the sum of the triangle inequalities

$\displaystyle f[x\rightarrow y]$ $\displaystyle\geq f[x\rightarrow
z]+f[z\rightarrow y]\qquad\;\text{and}\;$ $\displaystyle
f[x^{\prime}\rightarrow y^{\prime}]$ $\displaystyle\geq
f[x^{\prime}\rightarrow z]+f[z\rightarrow y^{\prime}].\qquad\qquad\qed$

##  4 Melons

Recall that $C^{n}_{+}$ is the space of $n$-tuples of continuous functions
from $[0,\infty)$ to $\mathbb{R}$. Recall also the melon map $f\mapsto Wf$
(introduced in Section 2) defined so that

$\sum_{i=1}^{k}(Wf)_{i}(t)=f[(0,n)^{k}\rightarrow(t,1)^{k}]$

for all $k\in\\{1,\dots,n\\}$ and $t\in[0,\infty)$. In this section, we show
that certain last passage values are preserved by the map $f\mapsto Wf$.

To do this, we first approach the construction of $Wf$ by successively sorting
pairs of functions. This approach is taken in O’Connell and Yor (2002), Biane
et al. (2005). Let $f_{1},f_{2}:[0,\infty)\to\mathbb{R}$ be two continuous
functions. For $x<y\in[0,\infty)$, define the maximal gap size

$G(f_{1},f_{2})(x,y)=\max_{s\in[x,y]}[f_{2}(s)-f_{1}(s)].$

Then the last passage values satisfy

$\displaystyle W(f_{1},f_{2})_{1}(t)$
$\displaystyle=f_{1}(t)-f_{2}(0)+G(f_{1},f_{2})(0,t)$ $\displaystyle
W(f_{1},f_{2})_{2}(t)$ $\displaystyle=f_{2}(t)-f_{1}(0)-G(f_{1},f_{2})(0,t)$

Now let $f\in C^{n}_{+}$. For $i\in\\{1,\dots,n-1\\}$, define

$\sigma_{i}(f)=(f_{1},f_{2},\dots,f_{i-1},W(f_{i},f_{i+1})_{1},W(f_{i},f_{i+1})_{2},f_{i+2}\dots,f_{n}).$

Now let $(i_{1},\dots,i_{n\choose 2})$ be any sequence of numbers in
$\\{1,\dots,n-1\\}$ such that $\tau_{i_{1}}\dots\tau_{i_{n\choose 2}}$ is the
reverse permutation $n(n-1)\dots 1$, where $\tau_{i}=(i,i+1)$ is the adjacent
transposition. Then we can alternately define the melon of $f$ by

$Wf:=\sigma_{i_{1}}\dots\sigma_{i_{n\choose 2}}(f).$

By the theory developed in Biane et al. (2005), this is the same object as our
previous definition of the melon and is independent of the choice of reduced
decomposition. We use this construction of $Wf$ to prove the following
proposition.

######  Proposition 4.1.

Let $n,k\in\mathbb{N}$, and let $U=\\{(x_{i},1)\\}_{i\in\\{1,\dots k\\}}$ and
$V=\\{(y_{i},n)\\}_{i\in\\{1,\dots k\\}}$ be an endpoint pair with $x_{i}\geq
0$ for all $i$. Then for any $f\in C^{n}_{+}$, we have that

$f[U\rightarrow V]=Wf[U\rightarrow V].$

We will prove this proposition in three steps. We first deal with the case
$n=2$, when $U$ and $V$ each have one element.

######  Lemma 4.2.

Let $f=(f_{1},f_{2})$. For every $0\leq x<y$, we have that

$f\big{[}(x,2)\rightarrow(y,1)\big{]}=Wf\big{[}(x,2)\rightarrow(y,1)\big{]}.$

###### Proof.

Last passage values are left unchanged by shifting functions up or down by a
constant. Hence we may assume that $f_{1}(0)=f_{2}(0)=0$. To avoid carrying
bulky notation, we also set

$s(x,y)=G(f_{1},f_{2})(x,y)$

to be the maximal gap size. We have that

$\displaystyle f\big{[}(x,2)\rightarrow(y,1)\big{]}$
$\displaystyle=f_{1}(y)-f_{2}(x)+s(x,y)\qquad\;\text{and}\;$ $\displaystyle
Wf\big{[}(x,2)\rightarrow(y,1)\big{]}$
$\displaystyle=f_{1}(y)+s(0,y)-f_{2}(x)+s(0,x)+\sup_{t\in[x,y]}[f_{2}(t)-f_{1}(t)-2s(0,t)].$

Therefore to prove the lemma, it is enough to show that

$s(x,y)-s(0,y)-s(0,x)=\sup_{t\in[x,y]}[f_{2}(t)-f_{1}(t)-2s(0,t)].$ (8)

To prove (8), we divide into cases. First suppose that $s(0,x)=s(0,y)$. In
this case, since $s(0,\cdot)$ is an non-decreasing function, we have that
$s(0,t)=s(0,x)=s(0,y)$ for all $t\in[x,y]$. Therefore

$\displaystyle\sup_{t\in[x,y]}[f_{2}(t)-f_{1}(t)-2s(0,t)]$
$\displaystyle=\sup_{t\in[x,y]}[f_{2}(t)-f_{1}(t)]-s(0,y)-s(0,x)$
$\displaystyle=s(x,y)-s(0,y)-s(0,x).$

For the case when $s(0,x)<s(0,y)$, observe that

$\sup_{t\in[x,y]}[f_{2}(t)-f_{1}(t)-2s(0,t)]\leq-\inf_{t\in[x,y]}s(0,t)=-s(0,x).$
(9)

Moreover, since $s(0,\cdot)$ increases on the interval $[x,y]$, continuity of
the functions $f_{1}$ and $f_{2}$ imply that there exist times $t_{1}$ and
$t_{2}$ in $[x,y]$ such that

$s(0,t_{1})=f_{2}(t_{1})-f_{1}(t_{1})=s(0,x)\qquad\;\text{and}\;\qquad
f_{2}(t_{2})-f_{1}(t_{2})=s(0,y).$

The first equation above implies that the inequality in (9) is in fact
equality, and the second equation implies that $s(x,y)=s(0,y)$. Combining
these facts proves (8). ∎

Next, we extend the $n=2$ case to deal with an arbitrary number of paths.

######  Lemma 4.3.

Let $f=(f_{1},f_{2}).$ For every endpoint pair of the form
$U=\\{(x_{i},2)\\}_{i\in\\{1,\dots k\\}}$ and
$V=\\{(y_{i},1)\\}_{i\in\\{1,\dots k\\}}$, we have that

$f\big{[}U\rightarrow V\big{]}=Wf[U\rightarrow V].$

###### Proof.

The condition that $(U,V)$ is an endpoint pair implies that $y_{i}\leq
x_{i+2}$ for all $i\in\\{1,\dots,k-2\\}$. Secondly, whenever $x_{i+1}<y_{i}$,
if $\pi\in\mathcal{Q}(U,V)$ then

$\pi_{i}(t)=1\;\text{and}\;\pi_{i+1}(t)=2\qquad\text{ for all
}t\in(x_{i+1},y_{i}].$ (10)

Therefore we can write

$\displaystyle\sup_{\pi\in\mathcal{Q}(U,V)}\sum_{i=1}^{k}\int df\circ\pi_{i}=$
$\displaystyle\sup_{\pi\in\mathcal{Q}(U,V)}\left(\sum_{i=1}^{k}\int_{x_{i}\vee
y_{i-1}}^{y_{i}\wedge
x_{i+1}}df\circ\pi_{i}+\sum_{i=1}^{k-1}\mathbf{1}(x_{i+1}<y_{i})[f_{1}(y_{i})+f_{2}(y_{i})-f_{1}(x_{i+1})-f_{2}(x_{i+1})]\right).$

In the above formula, we treat $y_{0}$ as $0$ and $x_{k+1}$ as $\infty$. Now,
since $(Wf)_{1}+(Wf)_{2}=f_{1}+f_{2}$, the second term under the right hand
supremum above is preserved by mapping $f\mapsto Wf$. We need to check that
the same is true of the first term. Since the intervals $(x_{i}\vee
y_{i-1},y_{i}\wedge x_{i+1})$ are all disjoint from each other, the only
condition that forces interactions between the coordinates of a path
$\pi\in\mathcal{Q}(U,V)$ is condition (10). Therefore

$\sup_{\pi\in\mathcal{Q}(U,V)}\sum_{i=1}^{k}\int_{x_{i}\vee
y_{i-1}}^{y_{i}\wedge
x_{i+1}}df\circ\pi_{i}=\sum_{i=1}^{k}\;\;\sup_{\pi_{i}\in\mathcal{Q}((x_{i}\vee
y_{i-1},2),(y_{i}\wedge x_{i+1},1))}\;\;\int df\circ\pi_{i}.$

By Lemma 4.2, each supremum term in the sum on the right hand side is
preserved by the map $f\mapsto Wf$. ∎

Before proving Proposition 4.1, we record an extension of the metric
composition law in Lemma 3.2. First, for a set of $k$-tuples
$W=\\{(w_{i},m)\\}_{i\in\\{1,\dots,k\\}}$, define
$W^{-}=\\{(w_{i},m-1)\\}_{i\in\\{1,\dots,k\\}}$.

######  Lemma 4.4.

Let $f\in C^{\mathbb{Z}}$. Let $(U,V)$ be an endpoint pair of the form
$U=\\{(x_{i},n)\\}_{i\in\\{1,\dots,k\\}}$,
$V=\\{(y_{i},1)\\}_{i\in\\{1,\dots,k\\}}$, and let $m\in\\{1,\dots,n-1\\}$.
Then

$f[U\rightarrow V]=\sup_{W}f[U\rightarrow W]+f[W^{-}\rightarrow V],$

where the supremum is taken over all $k$-tuples
$W=\\{(w_{i},m)\\}_{i\in\\{1,\dots,k\\}},$ such that both $(U,W)$ and
$(W^{-},V)$ are endpoint pairs.

The proof of Lemma 4.4 is straightforward and hence we omit it.

###### Proof of Proposition 4.1..

It is enough to show that for any sequence of continuous paths
$f=(f_{1},\dots,f_{n})$ with $f_{i}(0)=0$ for all $i$ and any
$m\in\\{1,\dots,n-1\\}$, that

$\sigma_{m}f[U\rightarrow V]=f[U\rightarrow V].$

For any $f$, by Lemma 4.4 applied twice, we can write

$f[U\rightarrow V]=\sup_{(Z,W)}\Big{(}f[U\rightarrow W]+f[W^{-}\rightarrow
Z]+f[Z^{-}\rightarrow V]\Big{)}$ (11)

Here the supremum is over all pairs
$(Z=\\{(z_{i},m)\\}_{i\in\\{1,\dots,k\\}},W=\\{(w_{i},m+2)\\}_{i\in\\{1,\dots,k\\}})$
such that each of $(U,W),(W^{-},Z)$, and $(Z^{-},V)$ are all endpoint pairs.
For a fixed pair $(Z,W)$, when we apply $\sigma_{m}$ to $f$, the first and
third terms under the supremum in (11) do not change since the relevant
components $f_{i}$ do not change. The middle term is preserved under the
transformation $\sigma_{m}$ by Lemma 4.2. Hence the right hand side of (11) is
also preserved under the map $f\mapsto\sigma_{m}f$. ∎

We finish this section with a straightforward consequence of Proposition 4.1.
We say that two paths $\pi_{1}$ and $\pi_{2}$ are disjoint if either
$\pi_{1}>\pi_{2}$ or $\pi_{1}<\pi_{2}$ on the entire interior of both
functions’ domains. For this lemma, we introduce the following notation.
Suppose that $f\in C^{n}$ or $f\in C^{\mathbb{Z}}$. We define
$\pi_{f}^{+}[x,y]$ as the rightmost last passage path in the set
$P_{f}[(x,n),(y,1)]$ (and similarly define the leftmost path
$\pi_{f}^{-}[x,y]$).

######  Lemma 4.5.

Let $U=((x_{1},n),(x_{2},n))$ and $V=((y_{1},1),(y_{2},1))$ be an endpoint
pair with $0\leq x_{1}$. The paths $\pi_{f}^{-}[x_{1},y_{1}]$ and
$\pi_{f}^{+}[x_{2},x_{2}]$ are disjoint if and only if the paths
$\pi_{Wf}^{-}[x_{1},y_{1}]$ and $\pi_{Wf}^{+}[x_{2},x_{2}]$ are disjoint.

###### Proof.

The paths $\pi_{f}^{-}[x_{1},y_{1}]$ and $\pi_{f}^{+}[x_{2},y_{2}]$ are
disjoint precisely when

$f[(x_{1},n)\to(y_{1},1)]+f[(x_{2},n)\to(y_{2},1)]=f[U\to V].$ (12)

To see this, note that if the paths $\pi_{f}^{-}[x_{1},y_{1}]$ and
$\pi_{f}^{+}[x_{2},y_{2}]$ are disjoint, then
$(\pi_{f}^{-}[x_{1},y_{1}],\pi_{f}^{+}[x_{2},y_{2}])$ forms a last passage
path from $U$ to $V$. Moreover, if equality holds in (12), then there must
exist $\pi\in P_{f}[(x_{1},n),(y_{1},1)]$ and $\tau\in
P_{f}[(x_{2},n),(y_{2},n)]$ that are disjoint. Pushing these paths further
left right, respectively, preserves disjointness.

Now, Proposition 4.1 implies that (12) holds if and only if it holds with $Wf$
in place of $f$. By the same reasoning as above, this is true if and only if
the paths $\pi_{Wf}^{-}[x_{1},y_{1}]$ and $\pi_{Wf}^{+}[x_{2},x_{2}]$ are
disjoint. ∎

##  5 Properties of melon paths

In this section, we collect some key combinatorial facts about last passage
paths in melons. We first record the following basic fact about the location
of last passage paths. We state this lemma for functions $f\in C^{n}_{+}$ that
start at $0$ and stay ordered, as any melon $Wf$ has this property.

######  Lemma 5.1.

Let $f\in C^{n}_{+}$ be such that $f_{i}(0)=0$ for all $i\in\\{1,\dots,n\\}$
and $f_{i}\geq f_{i+1}$ for all $i\in\\{1,\dots,n-1\\}$. Fix $j<k\leq
n\in\mathbb{N}$. Let
$U=\\{(x_{i},n)\\}_{i\in\\{1,\dots,k\\}},V=\\{(y_{i},1)\\}_{i\in\\{1,\dots,k\\}}$
be an endpoint pair with $x_{i}=0$ for all $i\in i\in\\{1,\dots,j\\}$. Then
there exists a last passage path

$\pi\in P_{f}[U,V]$

such that $\pi_{i}(t)=i$ for all $t\in(0,y_{1}),i\in\\{1,\dots,j\\}$.

###### Proof.

Let $g$ be the gap process of $f$ defined by $g_{i}=f_{i}-f_{i+1}$. By the
identity (4), we can write

$\begin{split}f[U\rightarrow
V]&=\sup_{\tau\in\mathcal{Q}(U,V)}\sum_{i=1}^{k}\left(f_{1}(y_{i})-f_{n}(x_{i})-\sum_{r=1}^{n-1}g_{r}(T_{r}(\tau_{i}))\right)\\\
&=\sum_{i=1}^{k}\left(f_{1}(y_{i})-f_{n}(x_{i})-\inf_{\tau\in\mathcal{Q}(U,V)}\sum_{r=1}^{n-1}g_{r}(T_{r}(\tau_{i}))\right).\end{split}$
(13)

Here $T_{r}(\tau_{i})$ is the time when the path $\tau_{i}$ jumps up to line
$r$. Hence, any last passage path $\pi$ across $f$ minimizes the sum of the
gaps. In particular, this implies that if $\pi$ is a last passage path, then
for $i\in[1,j]$ when $x_{i}=0$, we can replace each function $\pi_{i}$ with a
function that immediately jumps up to line $i$ to take advantage of the zero-
sized gaps there: since $g_{i}(t)\geq 0$ for all $i,t$, this process cannot
decrease the length of the path. By the ordering constraints on the functions
$\\{\pi_{i}\\}_{i\in\\{1,\dots,k\\}}$, we must also have have that
$\pi_{i}(t)\geq i$ for all $t<y_{1}$. ∎

### Melons opened up at other times

We will use melons starting at points other than $0$. Let $f\in C^{n}$. We
define the melon at $z$ by

$W_{z}f=Wf(z+\cdot).$

We also define the reversing maps $R_{z}:C^{n}\to C^{n}$ by

$R_{z}f_{i}(t)=-f_{n+1-i}(z-t).$

We can now define the reverse melon opened up at $z$ by $W^{*}_{z}f=WR_{z}f$.
We record the following fact about reverse melon last passage values. The
proof follows straight from the definition and Proposition 4.1, and so we omit
it.

######  Lemma 5.2.

Let $f\in C^{n}$ and let
$U=\\{(x_{i},n)\\}_{i\in\\{1,\dots,k\\}},V=\\{(y_{i},1)\\}_{i\in\\{1,\dots,k\\}}$
be an endpoint pair. For any $z\geq y_{k}$, we have that

$f[U\rightarrow V]=R_{z}f[V_{z}\rightarrow U_{z}]=W^{*}_{z}f[V_{z}\rightarrow
U_{z}].$

Here $U_{z}=\\{(z-x_{i},1)\\}_{i\in\\{1,\dots,k\\}}$ and
$V_{z}=\\{(z-y_{i},n)\\}_{i\in\\{1,\dots,k\\}}$.

In the remainder of this section, we will build a path transformation lemma
which represents $f[(x,n)\rightarrow(y,k)]$ in terms of a first passage value
across a reverse melon. For $f\in C^{n}$ and $k<n$ define the  backwards first
passage value

$F(f)[(x,1)\rightarrow(y,k)]=\inf_{\pi}\int df\circ\pi,$

where the infimum is taken over all non-decreasing cadlag functions
$\pi:[x,y]\to\\{1,\dots,k\\}$.

######  Lemma 5.3.

Let $f\in C^{n}$. For every $0\leq x<z$, we have that

$\displaystyle
Wf[(x,n)\rightarrow(z,k)]=(Wf)_{k}(z)-F(W^{*}_{z}f)[(z-x,1)\to(z,k)].$

The proof of this lemma is illustrated in Figure 4.

(a)

(b)

(c)

Figure 4: An illustration of the proof of Lemma 5.3. We want to understand the
last passage value in the melon from $(x,n)$ to $(z,k)$; here $n=5$ and $k=3$.
To do this, note that this is the bottom path in a collection of $k-1$
disjoint last passage paths from $(0,n)$ to $(z,1)$ and one path from $(x,n)$
to $(z,1)$: this is Figure 4 (a). We can then ‘demelonize’ (Figure 4 (b)) and
then ‘remelonize’ at $z$ after reversing the original lines (Figure 4 (c)).
These transformations leave the appropriate last passage values (i.e the sum
of the lengths of the coloured paths) unchanged. In Figure (c), the last
passage paths use the top 3 lines up to time $k$, except for the graph of one
increasing path from $(z-x,1)$ to $(z,3)$: this path gives the first passage
value that appears in the statement of the lemma. This is only a sketch, i.e.
Figures (a) and (c) are not truly the melon and reverse melon of Figure (b).

###### Proof.

To simplify notation in the proof, we write $\\{z^{k-1},w\\}$ for the
$k$-tuple of points consisting of $k-1$ copies of $z$ and one copy of $w$.
Similarly, we write $\\{w,z^{k-1}\\}$ if the points are in the opposite order.
First by Lemma 5.1, there is a last passage path

$\pi\in P_{Wf}[\\{(0,n)^{k-1},(x,n)\\},(z,1)^{k}]$

with $\pi_{i}(t)=i$ for all $t\in[0,z]$ and $i\leq k-1$. The only constraint
on the remaining path $\pi_{k}$ is that it avoids the first $k$ lines. In
other words, $\pi_{k}$ must be a last passage path from $(x,n)$ to $(z,k)$.
Moreover,

$\sum_{i=1}^{k-1}\int df\circ\pi_{i}=Wf[(0,n)^{k-1}\to(z,1)^{k-1}],$

again because of Lemma 5.1. Putting these facts together gives that

$\begin{split}Wf&[(x,n)\to(z,k)]\\\
&=Wf[\\{(0,n)^{k-1},(x,n)\\}\to(z,1)^{k}]-Wf[(0,n)^{k-1}\to(z,1)^{k-1}].\end{split}$
(14)

We now analyze the first term on the right hand side above. By Proposition
4.1, this term does not change when we replace $Wf$ by the original function
$f$. We can then use Lemma 5.2 to rewrite it in terms of the last passage
values in the reverse melon $W^{*}_{z}f$ opened up at $z$. This gives that

$\begin{split}Wf[\\{(0,n)^{k-1},(x,n)\\}\to(z,1)^{k}]=W^{*}_{z}f[(0,n)^{k}\to\\{(z-x,1),(z,1)^{k-1}\\}].\end{split}$
(15)

By Lemma 5.1, there exists a path

$\pi\in P_{W^{*}_{z}f}[(0,n)^{k},\\{(z-x,1),(z,1)^{k-1}\\}]$

such that $\pi_{i}(t)\leq i$ for all $t>0$ and $i\in\\{1,\dots,k\\}$. Hence
$\pi|_{[0,z-x]}$ will be a last passage path from $(0,n)^{k}$ to $(z-x,1)^{k}$
in $W^{*}_{z}f$. In particular, this implies that

$\displaystyle W^{*}_{z}f[(0,n)^{k}$
$\displaystyle\to\\{(z-x,1),(z,1)^{k-1}\\}]$
$\displaystyle=W^{*}_{z}f[(0,n)^{k}\to(z-x,1)^{k}]+\sup_{\tau}\sum_{i=2}^{k}\int_{z-x}^{z}dW_{z}^{*}f\circ\tau_{i}$
(16)

where the supremum above is over all sequences of non-increasing paths
$\tau=(\tau_{2},\dots,\tau_{k})$ with $\tau_{i}(t)\leq i$ and
$\tau_{i}<\tau_{i+1}$ on the interval $(z-x,z)$. This restriction on the paths
$\tau_{i}$ implies that there exists a non-decreasing path
$\tau_{*}:[z-x,z]\to\\{1,\dots,k\\}$ whose graph is disjoint from each of the
graphs of the paths $\tau_{i}$ and such that the graph

$\Gamma(\tau)=\Big{\\{}(t,\tau_{i}(t)):t\in[z-x,z],i\in\\{2,\dots,k,*\\}\Big{\\}}$

is equal to all of $[z-x,z]\times\\{1,\dots,k\\}$. In particular, this implies
that

$\sum_{i=2}^{k}\int_{z-x}^{z}dW_{z}^{*}f\circ\tau_{i}+\int_{z-x}^{z}dW_{z}^{*}f\circ\tau_{*}=W^{*}_{z}f[(0,n)^{k}\to(z,1)^{k}]-W^{*}_{z}f[(0,n)^{k}\to(z-x,1)^{k}].$

Hence the right hand side of (16) is equal to

$W^{*}_{z}f[(0,n)^{k}\to(z,1)^{k}]-\inf_{\tau^{*}}\int_{z-x}^{z}dW_{z}^{*}f\circ\tau_{*},$

where the infimum is taken over all non-decreasing paths
$\tau_{*}:[z-x,z]\to\\{1,\dots,k\\}$. This infimum is simply the backwards
first passage value $F(W^{*}_{z}f)[(z-x,1)\to(z,k)]$. Finally, combining this
representation with (14) and (15) implies that

$\begin{split}Wf[(x,n)\to(z,k)]&=W^{*}_{z}f[(0,n)^{k}\to(z,1)^{k}]\\\
&-Wf[(0,n)^{k-1}\to(z,1)^{k-1}]-F(W^{*}_{z}f)[(z-x,1)\to(z,k)].\end{split}$
(17)

We can rewrite the first term on the right hand side above in terms of a last
passage time across $Wf$ by using Lemma 5.2 and Proposition 4.1. This gives
that

$W^{*}_{z}f[(0,n)^{k}\to(z,1)^{k}]=Wf[(0,n)^{k}\to(z,1)^{k}].$

Furthermore, by Lemma 5.1, the above last passage is equal to
$(Wf)_{1}(z)+\dots+(Wf)_{k}(z)$. The second term on the right hand side of
(17) can similarly be written as $(Wf)_{1}(z)+\dots+(Wf)_{k-1}(z)$, completing
the proof of the lemma. ∎

##  6 The Airy line ensemble last passage problem

Recall the scaling operations $\bar{x}=2xn^{-1/3}$ and $\hat{y}=1+2yn^{-1/3}$,
and the bracket notation $[]$, $\\{\\}$, and $\langle\rangle$ for last passage
across Brownian motions, a Brownian melon, and the Airy line ensemble. Our
goal is to understand Brownian last passage percolation from $\bar{x}$ to
$\hat{y}$ by analyzing last passage across Brownian melons. By Lemma 3.2, this
analysis can be broken down into an analysis of a last passage problem across
the top right corner of the melon and a last passage problem up to that
corner. By continuity, the last passage problem across the top right corner
will translate to a last passage problem in the Airy line ensemble.

The harder part is the last passage up to the top right corner, whose values
seem not to be contained in the limiting Airy line ensemble information; these
are values of the form $\\{\bar{x}\to(\hat{z},k)\\}_{n}$. To tackle this
problem, we approximate a variant,

$\\{\bar{x}\to(\hat{z},k)\\}_{n}-W_{k}^{n}(\hat{z}),$

which has the added advantage of monotonicity in $z$ (see Lemma 3.3). In the
sequel, for a random array $\\{R_{n,k}:n,k\in\mathbb{N}\\}$ we will write

$R_{n,k}={\mathfrak{o}}(r_{n,k})\qquad\text{ if for all
}\epsilon>0\qquad\;\;\sum_{k=1}^{\infty}\limsup_{n\to\infty}\mathbb{P}(|R_{n,k}/r_{n,k}|<\epsilon)<\infty.$
(18)

The idea behind this notation is that if we can pass to a limit in $n$ to get
a sequence $R_{k}$, then by the Borel-Cantelli lemma, $R_{k}/r_{k}\to 0$
almost surely.

######  Proposition 6.1.

For each $n$, let $W^{n}=WB^{n}$ be a Brownian $n$-melon. Let $x>0$,
$\epsilon>0$ and let $z_{k}$ be an arbitrary sequence of real numbers. Let

$F^{n}_{k}(z)=n^{1/6}\left[\\{\bar{x}\to(\hat{z},k)\\}_{n}-W_{k}^{n}(\hat{z})+2xn^{1/6}\right].$

Then

$F^{n}_{k}(z_{k})=2\sqrt{2kx}+2z_{k}x+{\mathfrak{o}}(\sqrt{k}).$

We first reduce this problem to a last passage problem through the Airy line
ensemble. In the same setup as above we have the following.

######  Lemma 6.2.

Fix $k\in\mathbb{N}$. Then

$F_{n}^{k}(z_{k})-2z_{k}x\stackrel{{\scriptstyle
d}}{{\to}}\langle(0,k)\rightarrow(x,1)\rangle\qquad\;\text{as}\;n\to\infty.$
(19)

###### Proof.

By Lemma 5.3, we have

$F^{n}_{k}(z_{k})-2xn^{1/3}=-n^{1/6}F(W^{*}_{\hat{z}_{k}}B^{n})[(\hat{z}_{k}-\bar{x},1)\to(\hat{z}_{k},k)]$

where the function $F$ on the right hand side is the backwards first passage
value in the reverse melon opened up at $\hat{z}_{k}$. Reverse melons opened
up at $\hat{z}_{k}$ converge in distribution to the Airy line ensemble. This
uses Theorem 2.1 and the fact that any reverse melon is equal in distribution
to a usual Brownian $n$-melon.

Since backwards first passage values are continuous with respect to uniform
convergence on compact sets, the limit (19) is the backwards first passage
value

$-F(\mathcal{A})[(z_{k}-x,1)\rightarrow(z_{k},k)]-\frac{z_{k}x}{2}.$

The claim now follows from the stationarity and flip symmetry of the
stationary Airy line ensemble and the fact that a backward first passage value
across $f(\cdot)$ is equal to the negative of a last passage value across
$f(-\;\cdot)$. The correction term on the left hand side of (19) accounts for
the parabolic shape of the Airy line ensemble. ∎

We are now ready to prove the key theorem about last passage values across the
Airy line ensemble. Together with Lemma 6.2 this implies Proposition 6.1.

######  Theorem 6.3.

Fix $x>0$, and recall that $\langle(0,k)\rightarrow x\rangle$ is the last
passage value across the Airy line ensemble $\mathcal{A}$ from line $k$ at
time $0$ to line $1$ at time $x$. Then there exists a constant
$d\in\mathbb{N}$ such that for every $\epsilon>0$, we have

$\sum_{k\in\mathbb{N}}\mathbb{P}\left(\frac{\langle(0,k)\rightarrow
x\rangle-{2\sqrt{2kx}}}{k^{9/21}\log^{d}k}>\epsilon\right)<\infty.$

in probability as $k\to\infty$.

We expect that the true fluctuation $\langle(0,k)\rightarrow x\rangle$ around
$2\sqrt{2kx}$ should be $O(k^{-1/6})$ as in Brownian last passage percolation,
not $o(k^{9/21}\log^{d}k)$. While the error we get could be improved by a more
careful application of our methods, even our most optimistic heuristic proofs
of the above theorem did not yield this error. It would be of interest to
improve the above result to get a bound that is $o(1)$ as $k\to\infty$, as
this would yield a slightly nicer representation of the Airy sheet in the
limit; see Problem 14.4.

To prove this theorem we require structural results about the Airy line
ensemble from Dauvergne and Virág (2018). We start with two definitions.

######  Definition 6.4.

Fix $t>0$. For a fixed $\ell>0$, define $s_{i}=it/\ell$ for all
$i\in\\{0,1,\dots,\ell\\}$. For $k,\delta>0$, we define a random graph
$G_{k}(t,\ell,\delta)$ on the set

$S_{k}(\ell)=\\{1,\dots,k\\}\times\\{1,\dots,\ell\\},$

where the points $(i,j)$ and $(i+1,j)$ are connected if either

$|\mathcal{A}_{i}(s_{j-1})-\mathcal{A}_{i+1}(s_{j-1})|\leq\delta\quad\;\text{or}\;\quad|\mathcal{A}_{i}(s_{j})-\mathcal{A}_{i+1}(s_{j})|\leq\delta.$

######  Definition 6.5.

The bridge representation $\mathcal{B}^{k}(t,\ell,\delta)$ of the Airy line
ensemble $\mathcal{A}$ is a sequence
$(\mathcal{B}_{1},\dots,\mathcal{B}_{2k})$ of functions from $[0,t]$ to
$\mathbb{R}$ constructed as follows. For every
$(i,j)\in\\{1,\dots,2k\\}\times\\{1,\dots,\ell\\}$, sample a Brownian bridge
$B_{i,j}:[s_{j-1},s_{j}]\to\mathbb{R}$ of variance $2$ with

$B_{i,j}(s_{j-1})=\mathcal{A}_{i}(s_{j-1})\quad\;\text{and}\;\quad
B_{i,j}(s_{j})=\mathcal{A}_{i}(s_{j}),$

where the bridges $B_{i,j}$ and $B_{i^{\prime},j}$ are conditioned not to
intersect if $(i,j)$ and $(i^{\prime},j)$ are in the same component of
$G_{2k}(t,\ell,\delta)$. We then define the $i$th line $\mathcal{B}_{i}$ of
the line ensemble $\mathcal{B}^{k}(t,\ell,\delta)$ by concatenating the
bridges $B_{i,j}$. That is, $\mathcal{B}_{i}|_{[s_{j-1},s_{j}]}=B_{i,j}$ for
all $j\in\\{1,\dots,\ell\\}$.

See Figure 5 for an illustration of the bridge representation of
$\mathcal{A}$. We now state the main structural result about the Airy line
ensemble from Dauvergne and Virág (2018).

######  Theorem 6.6.

There exist constants $c,d>0$ such that the following holds for all $k\geq 3$,
$t>0$, $\gamma\in(c\log(\log k)/\log k,2],$ and $\ell\geq tk^{2/3+\gamma}$.
The total variation distance between the laws of top $k$ lines of the bridge
representation $\mathcal{B}^{k}(t,\ell,k^{-1/3-\gamma/4})$ and the top $k$
lines of the Airy line ensemble restricted to the interval $[0,t]$ is bounded
above by

$\ell e^{-d\gamma k^{\gamma/12}}.$

(a)

(b)

Figure 5: An illustration of the bridge representation $\mathcal{B}$ of the
Airy line ensemble. Figure 5(a) is the Airy line ensemble, with points at
three times identified. Points with the same time coordinate are grouped
together if they are close. To sample the bridge representation on this grid,
we erase all lines between the specified points and resample independent
Brownian bridges that are conditioned not to intersect each other if either of
their endpoints are close (i.e. have the same colour). The result is Figure
5(b). If we only look at the top half of the lines in the bridge
representation, then with high probability they do not intersect each other
and resemble the Airy line ensemble.

The above theorem gives that at the right scale, the Airy line ensemble can be
represented as sequences of concatenated Brownian bridges. This will allow us
to relate last passage across the Airy line ensemble to last passage across
concatenated Brownian bridges, and then in turn to Brownian last passage. We
will also need a structural result showing that edges in the graph
$G_{2k}(t,\ell,\delta)$ are rare, and a result about deviations of the Airy
line ensemble.

######  Proposition 6.7 (Proposition 7.4, Dauvergne and Virág (2018)).

Fix $\gamma>0$, and let $k\in\mathbb{N},t\in[0,\infty),\ell\geq
tk^{2/3+\gamma}$ and $\delta=k^{-1/3-\gamma/4}$. Let the graph
$G=G_{2k}(t,\ell,\delta)$ be as in Definition 6.4. For each
$j\in\\{1,\dots,\ell\\}$, let

$V_{j}=\\{x\in\\{1,\dots,2k\\}:\deg_{G}(x,j)\geq 1\\}.$

In other words, $V_{j}$ is the set of vertices in $G$ with second coordinate
$j$ that are connected to at least one other vertex. Then for any
$\alpha\in(0,1],\;i\in\\{{\left\lfloor
k^{\alpha}\right\rfloor}+1,\dots,2k\\},$ and $m\leq k^{2\alpha/3}$, we have
that

$\mathbb{P}(|V_{j}\cap\\{i-{\left\lfloor
k^{\alpha}\right\rfloor},\dots,i\\}|>mk^{\alpha-3\gamma/4})\leq ce^{-dm}.$

Here $c$ and $d$ are universal constants.

######  Theorem 6.8 (Theorem 8.1, Dauvergne and Virág (2018)).

There exists a constant $d>0$ such that for any $t>0$, we have that

$\sum_{k\in\mathbb{N}}\mathbb{P}\left(\sup_{s,s+r\in[0,t]}\frac{|\mathcal{A}_{k}(s)-\mathcal{A}_{k}(s+r)|}{\sqrt{r}\log^{1/2}(1+r^{-1})\log^{d}k}>1\right)<\infty.$
(20)

The proof of Theorem 6.3 relies on rewriting each line in the bridge
representation of the Airy line ensemble as a Brownian motion plus error
terms. Understanding last passage in this case can be handled by the following
subadditivity lemma. The proof is straightforward, and so we omit it.

######  Lemma 6.9.

For $f\in C^{n}$, let

$L(f)=f[(0,n)\rightarrow(t,1)]$

be the last passage value across $f$ from time $0$ to time $t$, and let
$F(f)=-L(-f)$ be the first passage value across $f$, again from the point
$(0,n)$ to $(t,1)$. Then for any $f,g\in C^{n}$ we have that

$L(f)+F(g)\leq L(f+g)\leq L(f)+L(g).$

###### Proof of Theorem 6.3.

We set $x=1$ for notational simplicity as the value of $x$ plays no important
role. Let $\mathcal{B}_{k}=\mathcal{B}^{k}(1,{\left\lceil
k^{2/3+\gamma}\right\rceil},k^{-1/3-\gamma/4})$ be the bridge representation
induced the by the graph

$G_{k}:=G_{2k}(1,{\left\lceil k^{2/3+\gamma}\right\rceil},k^{-1/3-\gamma/4}).$

Let $\\{s^{k}_{i}:i\in\\{1,\dots,{\left\lceil
k^{2/3+\gamma}\right\rceil}\\}\\}$ be the division of time that gives rise to
$G_{k}$. Here $\gamma\in(0,1/3)$ is a parameter that we will optimize over
later in the proof. By Theorem 6.6, we can couple all the representations
$\mathcal{B}_{k}$ with the Airy line ensemble $\mathcal{A}$ so that

$\sum_{k\in\mathbb{N}}\mathbb{P}\left(\mathcal{B}_{k}|_{\\{1,\dots,k\\}\times[0,1]}\neq\mathcal{A}|_{\\{1,\dots,k\\}\times[0,1]}\right)<\infty.$

Hence it suffices to analyze the last passage time $L(\mathcal{B}_{k})$ from
$(0,k)$ to $(x,1)$.

Step 1: Splitting up the paths. By representing each of the Brownian bridges
used to create $\mathcal{B}^{k}=(\mathcal{B}_{k,1},\dots,\mathcal{B}_{k,k})$
as a Brownian motion minus a random linear term, we can write

$\mathcal{B}_{k,j}=H_{k,j}+R_{k,j}+X_{k,j}.$

Here the $k$-tuple $H_{k}=(H_{k,1},\dots,H_{k,k})$ consists of $k$ independent
Brownian motions of variance $2$ on $[0,1]$. The functions $R_{k,j}$ are
piecewise linear with pieces defined on the time intervals
$[s^{k}_{i-1},s^{k}_{i}]$ for $i\in\\{0,\dots,{\left\lceil
k^{2/3+\gamma}\right\rceil}\\}$, and the error term $X_{k,j}$ is equal to zero
except for on intervals $[s^{k}_{i-1},s^{k}_{i}]$ where the vertex $(j,i)$ is
in a component of size greater than one in the graph $G_{k}$. On such
intervals, $X_{k,j}$ is the difference between a Brownian bridge from $0$ to
$0$ and a Brownian bridge conditioned to avoid $U_{j,i}-1$ other Brownian
bridges with certain start and endpoints, where $U_{j,i}$ is the size of the
component of $(j,i)$ in $G_{k}$.

Now let $L(f)=f[(0,k)\rightarrow(1,1)]$ for $f\in C^{k}$, and let
$F(f)=-L(-f)$. By subadditivity of last passage values (Lemma 6.9), we have
that

$L(H_{k})+F(R_{k})+F(X_{k})\leq L(\mathcal{B}^{k})\leq
L(H_{k})+L(R_{k})+L(X_{k}).$ (21)

By Theorem 2.5, the main term

$L(H_{k})=2\sqrt{2k}+Y_{k}k^{-1/6},$ (22)

where $\\{Y_{k}\\}_{k\in\mathbb{N}}$ is a sequence of random variables
satisfying a tail bound

$\mathbb{P}(|Y_{k}|>m)\leq ce^{-dm^{3/2}}$

for $c,d$ independent of $m$ and $n$.

Step 2: Bounding the piecewise linear term. First, we have the bound

$|L(R_{k})|,|F(R_{k})|\leq M_{k},$

where $M_{k}$ is the maximum absolute slope of any of the piecewise linear
segments in $R_{k}$. The slopes in $R_{k}$ come from increments in the Airy
line ensemble minus the increments of the Brownian motions $H_{k}$ on the grid
points. Recalling that $S_{k}(\ell)=\\{1,\dots,k\\}\times\\{1,\dots,\ell\\}$,
we have the following upper bound for $M_{k}$:

${\left\lceil k^{2/3+\gamma}\right\rceil}\left[\max_{(i,j)\in
S_{k}({\left\lceil
t^{2/3+\gamma}\right\rceil})}|H_{k,j}(s_{i})-H_{k,j}(s_{i-1})|+\max_{(i,j)\in
S_{k}({\left\lceil
t^{2/3+\gamma}\right\rceil})}|\mathcal{A}_{k}(s_{i})-\mathcal{A}_{k}(s_{i-1})|\right].$

By a standard Gaussian bound on the first term and Theorem 6.8 for the second
term, we have that for some $d\in\mathbb{N}$, that

$\sum_{k\in\mathbb{N}}\mathbb{P}\left(M_{k}\geq
k^{1/3+\gamma/2}\log^{d}k\right)<\infty.$ (23)

Step 3: Bounding the large component error. To bound $L(X_{k})$ and
$F(X_{k})$, we divide $\\{1,\dots,k\\}$ into $n={\left\lceil
k^{2/3+\gamma}\right\rceil}$ intervals

$I_{k,i}=\left\\{{\left\lfloor\frac{(i-1)k}{n}\right\rfloor}+1,\dots,{\left\lfloor\frac{ik}{n}\right\rfloor}\right\\},\qquad
i\in\\{1,\dots,n\\}.$

This, and the division of time into the intervals $[s_{i-1},s_{i}]$ for
$i\in\\{1,\dots,n\\}$ breaks the line ensemble $X_{k}$ into $n^{2}$ boxes.
Each last passage path can meet at most $2n-1$ of these boxes. So we have that

$L(X_{k})\leq(2n-1)Z_{k},$ (24)

where $Z_{k}$ is the maximal last passage value among all values that start
and end in the same box (including the boundary). Specifically,

$Z_{k}=\max_{(i,j)\in[1,n]^{2}}\max\left\\{X_{k}[(\ell_{1},r_{1})\rightarrow(\ell_{2},r_{2})]:\ell_{1},\ell_{2}\in
I_{k,i},\;r_{1},r_{2}\in[s_{j-1},s_{j}]\right\\}.$

We have that $Z_{k}\leq N_{k}D_{k}$, where

$\displaystyle N_{k}$
$\displaystyle=\max_{(i,j)\in[1,n]^{2}}\left|\left\\{\ell\in
I_{k,i}:X_{\ell}|_{[s_{j-1},s_{j}]}\neq 0\right\\}\right|\quad\;\text{and}\;$
$\displaystyle D_{k}$
$\displaystyle=\max\bigg{\\{}|X_{k,\ell}(t)-X_{k,\ell}(r)|:\ell\in[1,k],t,r\in[s_{i-1},s_{i}]\text{
for some }i\in\\{1,\dots,n\\}\bigg{\\}}.$

That is, $N_{k}$ is the maximum number of nonzero line segments in any box,
and $D_{k}$ is the maximum increment over any line segment in a box. Since
$X_{k,j}=\mathcal{B}_{k,j}-H_{k,j}-R_{k,j}$, we can bound $D_{k}$ in terms of
the deviations of the other paths. This can be done by using the bound on
$M_{k}$ above, Theorem 6.8, and standard bounds on Gaussian random variables.
We get that for some constant $d\in\mathbb{N}$, that

$\sum_{k=1}^{\infty}\mathbb{P}\left(D_{k}>k^{-1/3-\gamma/2}\log^{d}k\right)<\infty.$
(25)

The quantity $N_{k}$ is equal to the maximum number of edges in the graph
$G_{k}$ in a region of the form $I_{k,i}\times\\{j\\}$ for some
$j\in\\{1,\dots,n\\}$. This can be bounded by using Proposition 6.7 and a
union bound, and gives that

$\sum_{k\in\mathbb{N}}\mathbb{P}\left(N_{k}>k^{1/3-\gamma}k^{-3\gamma/4}\log^{2}k\right)<\infty.$

Combining this with the bound in (24) and (25) implies that for some constant
$d>0$, that

$\sum_{k\in\mathbb{N}}\mathbb{P}\left(L(X_{k})>k^{2/3-5\gamma/4}\log^{d}k\right)<\infty.$
(26)

We can symmetrically bound $F(X_{k})$.

Step 4: Putting it all together. By combining the inequalities (21), (22),
(23) and (26), we get that for some $d\in\mathbb{N}$ that

$\sum_{k\in\mathbb{N}}\mathbb{P}\left(|L(\mathcal{B}^{k})-2\sqrt{k}|>k^{2/3-5\gamma/4}\log^{d}k+k^{1/3+\gamma/2}\log^{d}k\right)<\infty.$

Taking the optimal $\gamma=4/21$ and increasing the power of $\log k$ from $d$
to $d+1$ completes the proof. ∎

##  7 Melon paths are parabolas

In this section, we use the results of Section 6 to establish bounds on the
location of melon last passage paths. We will also establish that last passage
paths that start or end close together meet with high probability. These two
facts will allow us to construct the Airy sheet in Section 8. Throughout the
section we write $W=WB^{n}$ for the melon paths, and use the last passage and
scaling notation introduced in Section 2.

The triangle inequality (7) for the last passage path on the melon says

$\\{\bar{x}\rightarrow\hat{y}\\}\geq\\{\bar{x}\rightarrow(\hat{z},k)\\}+\\{(\hat{z},k)\rightarrow\hat{y}\\}$
(27)

with equality holding if and only if $(\hat{z},k)$ is along some last passage
path from $\bar{x}$ to $\hat{y}$. Let $Z^{n}_{k}(x,y)$ denote the largest
value of $z$ so that equality holds in (27). Note that $Z^{n}_{1}(x,y)=y$, and
for $k\geq 2$, the time $Z^{n}_{k}(x,y)$ can also be characterized as the
unique time such that both $(Z^{n}_{k}(x,y),k)$ and $(Z^{n}_{k}(x,y),k-1)$ lie
on the rightmost last passage path from $\bar{x}$ to $\hat{y}$ in the melon.
Because of this, $Z^{n}_{k}$ is a non-decreasing function in both variables by
monotonicity of last passage paths (Lemma 3.6).

######  Lemma 7.1.

Let $K$ be a compact subset of $(0,\infty)\times\mathbb{R}$. Then we have

$\sup_{(x,y)\in
K}\left|Z^{n}_{k}(x,y)-\sqrt{\frac{k}{2x}}\right|={\mathfrak{o}}(\sqrt{k}).$

###### Proof.

We first fix $x,y\in K$, rescale by $n^{1/6}$ and center so that the triangle
inequality (27) reads $H_{n}\geq F^{n}_{k}(z)+G^{n}_{k}(z)$ with

$\displaystyle H_{n}$ $\displaystyle=$ $\displaystyle
n^{1/6}\\{\bar{x}\rightarrow\hat{y}\\}-2n^{2/3}-2(y-x)n^{1/3}$ $\displaystyle
F^{n}_{k}(z)$ $\displaystyle=$ $\displaystyle
n^{1/6}(\\{\bar{x}\rightarrow(\hat{z},k)\\}-W^{n}_{k}(\hat{z}))+2xn^{1/3}$
$\displaystyle G^{n}_{k}(z)$ $\displaystyle=$ $\displaystyle
n^{1/6}(W^{n}_{k}(\hat{z})+\\{(\hat{z},k)\rightarrow\hat{y}\\})-2y^{1/3}-2n^{2/3}.$

The functions $-F^{n}_{k}(z)$ and $G^{n}_{k}(z)$ are non-increasing in $z$ by
Lemma 3.3. Also, since $\\{(\hat{z},k)\rightarrow\hat{y}\\}$ is equal to
$W^{n}_{1}(\hat{y})-W^{n}_{k}(\hat{z})$ minus a non-negative sum of gaps (see
(4)), we have the bound

$G^{n}_{k}(z)\leq n^{1/6}W^{n}_{1}(\hat{y})-2yn^{1/3}-2n^{2/3}.$ (28)

The right hand side above is independent of $k$ and is a tight sequence of
random variables by Theorem 2.5. Proposition 6.1 implies that gives

$F^{n}_{k}(z_{k})=2\sqrt{2kx}+2z_{k}x+{\mathfrak{o}}(\sqrt{k})$

over any sequence $z_{k}$. Since $H_{n}$ is also tight by Theorem 2.5, the
triangle inequality gives

$G^{n}_{k}(z_{k})\;\leq\;-2\sqrt{2kx}-2z_{k}x+{\mathfrak{o}}(\sqrt{k})$

Since the left hand side does not depend on $x$, minimizing in $x$ should
reveal the relationship of $k$, $x$, and the optimal $z_{k}$. The minimum
happens when $2xz^{2}=4$, at which the minimal value is $k/z$ (assuming
$z<0$). With $a>0$ and $x^{\prime}=1/(2a^{2})$ we get the bound

$G^{n}_{k}(-a\sqrt{k})\;\leq\;-\frac{\sqrt{k}}{a}+{\mathfrak{o}}(\sqrt{k})$

Now, let $z_{k}=-\alpha\sqrt{k/x}$. We have

$F^{n}_{k}(z_{k})+G^{n}_{k}(z_{k})\leq
2\sqrt{2kx}-{2\alpha{\sqrt{k/x}}\,x}-\frac{1}{\alpha}\sqrt{kx}+{\mathfrak{o}}(\sqrt{k})=-2\sqrt{kx}(\alpha-1/\sqrt{2})^{2}/\alpha+{\mathfrak{o}}(\sqrt{k})$

These bounds are for a fixed deterministic sequence $z_{k}$. However, using
the monotonicity of $F^{n}_{k}$ and $G^{n}_{k}$ in $z$ and their individual
bounds at a sufficiently fine but finite mesh of values $\alpha_{m}$ we get

$\sup_{z:\;|z+\sqrt{k/(2x)}|>\epsilon\sqrt{k}}F^{n}_{k}(z)+G^{n}_{k}(z)\leq-c\epsilon^{2}\sqrt{kx}+{\mathfrak{o}}(\sqrt{k})$

The only technical difficulty comes from controlling the sum outside a compact
subinterval of $\alpha$-values in $(0,\infty)$. Here we can use that
$F^{n}_{k}$ is decreasing in $\alpha$, so $F^{n}_{k}(y)$ is an upper bound,
and that $G^{n}_{k}$ has an upper bound (28) which is tight in $n$.

Since for $z=Z^{n}_{k}$ we have $F^{n}_{k}+G^{n}_{k}=H^{n}$, and $H^{n}$ is
tight in $n$, we get that
$Z^{n}_{k}(x,y)=\sqrt{k/(2x)}+{\mathfrak{o}}(\sqrt{k})$ for $x,y$ fixed. Since
$Z^{n}_{k}(x,y)$ is monotone in $x$ and $y$, the claim follows. ∎

Recall that two paths $\pi$ and $\tau$ are disjoint if either $\pi>\tau$ or
$\tau>\pi$ on the intersection of the interiors of both their domains.

######  Lemma 7.2.

Fix $x>0$ and $y_{1}<y_{2}\in\mathbb{R}$. Then

$\lim_{\epsilon\to
0^{+}}\limsup_{n\to\infty}\mathbb{P}\big{(}\pi\\{\bar{x},\hat{y}_{1}\\}\;\;\;\;\text{and}\;\;\;\;\pi\\{\bar{x}+\bar{\epsilon},\hat{y}_{2}\\}\text{
are disjoint}\big{)}=0.$

###### Proof.

We will prove the statement with the leftmost last passage path
$\pi^{-}\\{\bar{x},\hat{y}_{1}\\}$ in place of the rightmost path
$\pi\\{\bar{x},\hat{y}_{1}\\}$. We can do this since disjointness of the
rightmost path $\pi\\{\bar{x},\hat{y}_{1}\\}$ with
$\pi\\{\bar{x}+\bar{\epsilon},\hat{y}_{2}\\}$ plus monotonicity (Lemma 3.6)
immediately implies disjointness of the leftmost path
$\pi^{-}\\{\bar{x},\hat{y}_{1}\\}$ with
$\pi\\{\bar{x}+\bar{\epsilon},\hat{y}_{2}\\}$.

By Lemma 4.5, disjointness of the paths $\pi^{-}\\{\bar{x},\hat{y}_{1}\\}$ and
$\pi\\{\bar{x}+\bar{\epsilon},\hat{y}_{2}\\}$ is equivalent to disjointness of
the original Brownian last passage paths $\pi^{-}[\bar{x},\hat{y}_{1}]$ and
$\pi[\bar{x}+\bar{\epsilon},\hat{y}_{2}]$. Here $\pi^{-}[\bar{x},\hat{y}_{1}]$
is the leftmost last passage path in $B^{n}$ from $\bar{x}$ to $\hat{y}_{1}$.
Hence we just need to show

$\lim_{\epsilon\to
0^{+}}\limsup_{n\to\infty}\mathbb{P}\big{(}\pi^{-}[\bar{x},\hat{y}_{1}]\;\;\;\;\text{and}\;\;\;\;\pi[\bar{x}+\bar{\epsilon},\hat{y}_{2}]\text{
are disjoint}\big{)}=0.$

By time-reversal symmetry of Brownian motion, it is enough to prove that for
$x_{1}<x_{2}\in\mathbb{R}$ and $y\in\mathbb{R}$, that

$\lim_{\epsilon\to
0^{+}}\limsup_{n\to\infty}\mathbb{P}\big{(}\pi^{-}[\bar{x}_{1},\hat{y}]\;\;\;\;\text{and}\;\;\;\;\pi[\bar{x}_{2},\hat{y}+\bar{\epsilon}]\text{
are disjoint}\big{)}=0.$

By translation invariance and Brownian scaling, we may assume that
$x_{1}=y=0$. Again by Lemma 4.5, we can translate back to melon paths in this
case. In particular, we just need to show that $\pi^{-}\\{0,0\\}$ and
$\pi\\{\bar{x}_{2},\hat{\epsilon}\\}$ are disjoint with probability tending to
$0$ in the appropriate way. By Lemma 5.1, the path $\pi^{-}\\{0,0\\}$ simply
follows the top line in $WB^{n}$. Hence these paths are disjoint precisely
when $Z^{n}_{2}(x_{2},\epsilon)\geq 0$. We show that

$\lim_{\epsilon\to
0^{+}}\limsup_{n\to\infty}\mathbb{P}(Z^{n}_{2}(x_{2},\epsilon)\geq 0)=0.$ (29)

By monotonicity, it is enough to take the limit over
$\epsilon\in\mathbb{Q}^{+}$. For this, first note that by Lemma 7.1, for each
$k$ the sequence of random variables $Z^{n}_{k}(x_{2},\epsilon)$ is tight.
Therefore, for any subsequence $Y\subset\mathbb{N}$ we can find a further
subsequence $Y_{0}\subset Y$ and a coupling of the Brownian melons
$\\{WB^{n}:n\in Y_{0}\\}$ such that for all $\epsilon\in\mathbb{Q}^{+}$ and
$k\in\mathbb{N}$, each of the sequences $\\{Z^{n}_{k}(x_{2},\epsilon):n\in
Y_{0}\\}$ converges almost surely to a limit $Z_{k}(x_{2},\epsilon)$. By
Theorem 2.1, we can also choose this coupling in such a way that the top
corner of $\\{WB^{n}:n\in Y_{0}\\}$ converges almost surely to the Airy line
ensemble.

Now fix $\epsilon\in\mathbb{Q}$. For any $k\in\mathbb{N}$, the points
$\\{(Z_{i}(x_{2},\epsilon),i):i\in\\{1,\dots,k\\}\\}$ are along the last
passage path from $(Z_{k}(x_{2},\epsilon),k)$ to $(\epsilon,1)$ in the Airy
line ensemble since they lay along a last passage path in the finite case.
Also Lemma 7.1 ensures that almost surely, $Z_{k}(x_{2},\epsilon)\to-\infty$
as $k\to\infty$. In particular, not all values of $Z_{k}(x_{2},\epsilon)$
equal to $\epsilon$. Since the Airy line ensemble is absolutely continuous on
any compact set with respect to $k$ independent Brownian motions by
Proposition 2.2, this guarantees that $Z_{2}(x_{2},\epsilon)$ has a continuous
distribution, and so $Z_{2}(x_{2},\epsilon)<\epsilon$ almost surely.

Finally, Brownian scaling applied to the melons $WB^{n}$ implies that

$Z_{2}(x_{2},\epsilon)\stackrel{{\scriptstyle d}}{{=}}Z_{2}(x_{2},0)+\epsilon$

for any $\epsilon\in\mathbb{Q}$. Combined with the fact that
$Z_{2}(x_{2},\epsilon)<\epsilon$ almost surely, this implies that

$\lim_{\epsilon\to
0^{+},\epsilon\in\mathbb{Q}}\mathbb{P}(Z_{2}(x_{2},\epsilon)\geq 0)=0.$

Since the original subsequence $Y$ was arbitrary, this implies (29). ∎

##  8 Constructing the Airy sheet

In this section, we construct the joint limit of last passage values at two
times, known as the Airy sheet. The definition is motivated by last passage
across melons.

######  Definition 8.1.

The Airy sheet is the law a random continuous function
$\mathcal{S}:\mathbb{R}^{2}\to\mathbb{R}$ so that

  1. (i)

$\mathcal{S}$ has the same law as $\mathcal{S}(\cdot+t,\cdot+t)$ for all
$t\in\mathbb{R}$.

  2. (ii)

$\mathcal{S}$ can be coupled with an Airy line ensemble so that
$\mathcal{S}(0,\cdot)=\mathcal{A}_{1}(\cdot)$ and for all
$(x,y,z)\in\mathbb{Q}^{+}\times\mathbb{Q}^{2}$ there exists a random variable
$K_{x,y,z}\in\mathbb{N}$ so that for all $k\geq K_{x,y,z}$, almost surely

$\big{\langle}(-\sqrt{k/(2x)},k)\rightarrow
z\big{\rangle}-\big{\langle}(-\sqrt{k/(2x)},k)\rightarrow
y\big{\rangle}=\mathcal{S}(x,z)-\mathcal{S}(x,y)$

######  Proposition 8.2.

The Airy sheet is unique.

###### Proof.

Since $\mathcal{A}_{1}(z)+z^{2}$ is stationary and ergodic (see equation
(5.15) in Prähofer and Spohn (2002)), for any fixed $y$ we have that almost
surely,

$\mathcal{S}(0,y)=\lim_{m\to\infty}\frac{1}{2m}\int_{-m}^{m}\mathcal{S}(0,y)-(\mathcal{S}(0,z)+z^{2})dz+\mathbb{E}\mathcal{A}_{1}(0).$

We can then use property (i) to translate the above formula (applied to
$\mathcal{S}(0,y-x)$) to get an almost sure formula for any
$\mathcal{S}(x,y)$:

$\mathcal{S}(x,y)=\lim_{m\to\infty}\frac{1}{2m}\int_{-m}^{m}\mathcal{S}(x,y)-(\mathcal{S}(x,z+x)+z^{2})dz+\mathbb{E}\mathcal{A}_{1}(0).$

When $(x,y)\in\mathbb{Q}^{+}\times\mathbb{Q}$, the integrand on right hand
side above is determined by condition (ii) for rational values of $z$, and
hence is determined by that condition for all values of $z$ by continuity.
Therefore $\\{S(x,y):x\in\mathbb{Q}^{+}\times\mathbb{Q}\\}$ is determined by
the definition of $\mathcal{S}$. By stationarity and continuity, this implies
that the distribution of $\mathcal{S}$ is uniquely determined by its
definition. ∎

######  Remark 8.1.

We can exchange condition (ii) in Definition (8.1) for the following Busemann
function definition. Almost surely, for all $x>0$ and $y,z\in\mathbb{R}$, we
have that

$\lim_{k\to\infty}\big{\langle}(-\sqrt{k/(2x)},k)\rightarrow
z\big{\rangle}-\big{\langle}(-\sqrt{k/(2x)},k)\rightarrow
y\big{\rangle}=\mathcal{S}(x,z)-\mathcal{S}(x,y).$ (30)

This definition can only give rise to one object, since the proof of
Proposition 8.2 goes through with this definition.

Moreover, condition (ii) of Definition 8.1 implies this definition, and so
they must be the same. To see this, note that it clearly implies (30) for
rational triples. To extend to $x\in\mathbb{Q}^{+}$ and $y,z\in\mathbb{R}$,
observe that

$\big{\langle}(-\sqrt{k/(2x)},k)\rightarrow
z+\epsilon\big{\rangle}\geq\big{\langle}(-\sqrt{k/(2x)},k)\rightarrow
z\big{\rangle}+\mathcal{A}_{1}(z+\epsilon)-\mathcal{A}_{1}(z).$

Therefore since the left hand side of (30) is continuous when restricted to
rational $x,y,z$, it is continuous for $x\in\mathbb{Q}^{+}$ and
$y,z\in\mathbb{R}$. To extend to $x\in\mathbb{R}^{+}$, note that the left hand
side of (30) is monotone in $x$ by Proposition 3.8. Therefore it must again be
continuous since it is continuous on rationals.

The Airy sheet exists because it is the limit of Brownian last passage
percolation. More precisely, we have the following. For $n\in\mathbb{N}$ let
$B^{n}$ be an $n$-tuple of independent two-sided Brownian motions and let
$[x\rightarrow y]_{n}$ be the last passage value there from $(x,n)$ to
$(y,1)$. Recall the scaling $\bar{x}=2xn^{-1/3}$ and $\hat{y}=1+2yn^{-1/3}.$
Define the sequence of prelimiting Airy sheets $\mathcal{S}_{n}(x,y)$ by the
formula

$[\bar{x}\rightarrow\hat{y}]_{n}=2\sqrt{n}+(y-x)n^{1/6}+n^{-1/6}\mathcal{S}_{n}(x,y).$

######  Theorem 8.3.

The Airy sheet $\mathcal{S}$ exists. Moreover, there exists a coupling so that
$\mathcal{S}_{n}-\mathcal{S}$ is asymptotically small in the sense that

$\text{for every compact }K\subset\mathbb{R}^{2}\text{ there exists }a>1\text{
with }\mathbb{E}a^{\sup_{K}|\mathcal{S}_{n}-\mathcal{S}|^{3/2}}\to 1.$ (31)

The proof consists of showing tightness and that all subsequential limits
satisfy the definition.

######  Lemma 8.4.

$\mathcal{S}_{n}$ is a tight sequence of random functions in
$C(\mathbb{R}^{2},\mathbb{R})$. Moreover, if $\mathcal{S}$ is a limit of
$\mathcal{S}_{n}$ along a subsequence $Y$, then there exists a coupling of
$\mathcal{S}_{n}$ and $\mathcal{S}$ such that (31) holds.

For the proof, $c$ and $d$ will be constants that may change from line to line
and are independent of $n$. They will depend on an initial choice of a compact
set.

###### Proof.

It suffices to prove tightness on any compact set $K=[-b,b]^{2}$. First, by
Theorem 2.3, we have

$\mathbb{P}(|\mathcal{S}_{n}(0,0)|>m)\leq ce^{-dm^{3/2}}.$ (32)

Second, $\mathcal{S}_{n}(x,\cdot)$ and $\mathcal{S}_{n}(\cdot,y)$ are both
given by the rescaled top line of a Brownian melon. Therefore tail bounds in
Proposition 2.6 and the modulus of continuity lemma (Lemma 2.8) imply that on
$[-b,b]^{2}$ we have

$|\mathcal{S}_{n}(x,y)-\mathcal{S}_{n}(x^{\prime},y^{\prime})|\leq
C_{n}||(x,y)-(x^{\prime},y^{\prime})||^{1/2}\log^{1/2}\left(\frac{2b}{||(x,y)-(x^{\prime},y^{\prime})||}\right)$

for a sequence of constants $C_{n}$ satisfying

$\mathbb{P}(C_{n}>m)\leq ce^{-dm^{3/2}}.$ (33)

This uniform modulus of continuity bound coupled with the bound on
$\mathcal{S}_{n}(0,0)$ immediately implies tightness of $\mathcal{S}_{n}|_{K}$
(for example, by the Kolmogorov-Chentsov criterion). Moreover, if
$\mathcal{S}_{n}|_{K}\to\mathcal{S}|_{K}$ in distribution along a subsequence,
then we can find a coupling for which
$a^{\sup_{K}|\mathcal{S}_{n}-\mathcal{S}|^{3/2}}\to 1$ for every $a>1$. The
limit $\mathcal{S}$ satisfies the same modulus of continuity estimate as the
sequence $\\{S_{n}\\}$, with a random constant $C$ satisfying the same tails
as in (33). Therefore we have the bound

$a^{\sup_{K}|\mathcal{S}_{n}-\mathcal{S}|^{3/2}}\leq
a^{c(|\mathcal{S}_{n}(0,0)|^{3/2}+|\mathcal{S}(0,0)|^{3/2}+C_{n}^{3/2}+C^{3/2})}.$

All four of the random variables in the exponent above satisfy tail bounds of
the form (32) or (33), and so the above random variable is uniformly
integrable for small enough $a>1$. Hence we can conclude the desired
convergence in expectation. ∎

Any subsequential limit $\mathcal{S}$ of $\mathcal{S}_{n}$ satisfies property
(i) of the Airy sheet since the $\mathcal{S}_{n}$ are stationary on compact
sets up to a $o(1)$ factor by Brownian scaling. So it suffices to show that
any limit restricted to $\mathbb{Q}^{+}\times\mathbb{Q}$ admits the Airy line
ensemble description in the definition.

With this in mind, let $\mathcal{S}$ be any subsequential limit of
$\mathcal{S}_{n}$. By Skorokhod’s representation theorem there is a coupling
of the processes $B^{n}$ and a subsequence $Y$ such that the following
convergences hold on a set $\Omega$ of probability 1. All limits and claims
about $n$ are for $n\in Y$.

  1. 1.

$\mathcal{S}_{n}\to\mathcal{S}$ uniformly on compacts.

  2. 2.

The melon $WB^{n}$ in the scaling in Theorem 2.1 converges to the Airy line
ensemble $\mathcal{A}$ uniformly on compact sets in
$\mathbb{Z}\times\mathbb{R}$. This requires Theorem 2.1.

  3. 3.

$Z_{k}^{n}\to Z_{k}$ pointwise on the set $\mathbb{Q}^{+}\times\mathbb{Q}$.
Moreover, for all $(x,y)\in\mathbb{Q}^{+}\times\mathbb{Q}$ as $k\to\infty$

$Z_{k}(x,y)/\sqrt{k}\to-1/{\sqrt{2x}}.$ (34)

For fixed $(x,y)$, the tightness of the sequences $Z^{n}_{k}(x,y)$ and their
asymptotic limits follows from Lemma 7.1. The extension to all rationals is
standard.

  4. 4.

For every triple $(x,y,z)\in\mathbb{Q}^{+}\times\mathbb{Q}^{2}$ with $y<z$,
there exist random points $X_{1}<x<X_{2}\in\mathbb{Q}^{+}$ such that

$\pi\\{\bar{X}_{1},\hat{y}\\}_{n}\;\;\;\text{and}\;\;\;\pi\\{\bar{X}_{2},\hat{z}\\}_{n}$

are not disjoint for all large enough $n$. That we can guarantee this for one
triple follows from Lemma 7.2. The extension to all rational triples is again
standard.

Just as in the finite case, we can think of the points $Z_{k}$ in property 3
above as lying along a last passage path. With this in mind, for
$(x,y)\in\mathbb{Q}^{+}\times\mathbb{Q}$, define $\pi\langle
x,y\rangle:(-\infty,y]\to\mathbb{Z}$ to be the non-increasing cadlag function
given by

$\pi\langle x,y\rangle(t)=\min\\{k\in\mathbb{N}:Z_{k+1}(x,y)\leq t\\}.$

The paths $\pi\langle x,y\rangle$ are pointwise limits of the paths
$\pi\\{\bar{x},\hat{y}\\}_{n}$ over $Y$. Moreover, convergence to the Airy
line ensemble (Property 2) guarantees that $\pi\langle x,y\rangle$ is a
rightmost last passage path when restricted to any compact interval.

Theorem 8.3 then follows immediately from the following deterministic
statement about the relationship between the subsequential limit $\mathcal{S}$
and the Airy line ensemble $\mathcal{A}$.

######  Lemma 8.5.

On the set $\Omega$, the processes $\mathcal{S}$ and $\mathcal{A}$ satisfy
condition (ii) of Definition 8.1.

Lemma 8.5 puts together all the bounds that we have developed over the
previous few sections. See Figure 6 for a sketch of its proof.

Figure 6: The idea of the proof of Lemma 8.5. We start with points
$\bar{X}_{1}$ and $\bar{X}_{2}$ on either side of a rational $\bar{x}$ whose
melon last passage paths to $\hat{y}$ and $\hat{z}$ are not disjoint. These
last passage paths both follow particular parabolas, so the place where they
meet has to be in the part of the melon that converges to the Airy line
ensemble. The last passage paths from $\bar{x}$ to $\hat{y}$ and $\hat{z}$ are
squeezed by these outer paths, and hence the branch point between the paths
from $\bar{x}$ must also occur in the part of the melon that converges to the
Airy line ensemble.

###### Proof.

The fact that $\mathcal{S}(0,y)=\mathcal{A}(y)$ for all $y\in\mathbb{R}$ is
immediate from the fact that the top line of $WB_{n}$ gives last passage
values from $0$. Now fix $(x,y,z)\in\mathbb{Q}^{+}\times\mathbb{Q}^{2}$ with
$y<z$, and let $X_{1}<x<X_{2}$ be as in property 4 above. By property 3 above,
we can find a random time $T$ such that for all large enough $n$, we have

$\pi\\{\bar{X}_{1},\hat{y}\\}_{n}(\hat{T})<\pi\\{\bar{x},\hat{y}\\}_{n}(\hat{T})\leq\pi\\{\bar{x},\hat{z}\\}_{n}(\hat{T})<\pi\\{\bar{X}_{2},\hat{z}\\}_{n}(\hat{T}).$
(35)

The middle inequality follows from monotonicity of last passage paths (Lemma
3.6). In particular, this inequality also holds for all $t\leq T$ by the tree
structure of last passage paths (Proposition 3.7). However, property 4
guarantees that the paths $\pi\\{\bar{X}_{1},\hat{y}\\}_{n}$ and
$\pi\\{\bar{X}_{2},\hat{z}\\}_{n}$ are not disjoint for all large enough $n$,
so there must be a sequence of times $R_{n}\in[T,y]$ such that for all large
enough $n$,

$\pi\\{\bar{X}_{1},\hat{y}\\}_{n}(\hat{R}_{n})=\pi\\{\bar{X}_{2},\hat{z}\\}_{n}(\hat{R}_{n}).$

We choose $R_{n}$ to be minimal for each $n$. A minimal time exists since the
paths are cadlag. Monotonicity and the tree structure of last passage paths
along with the inequality (35) then implies that

$\pi\\{\bar{x},\hat{y}\\}_{n}(t)=\pi\\{\bar{x},\hat{z}\\}_{n}(t)$

for all $t\leq\hat{R}_{n}$. By the geodesic property of last passage paths
(Lemma 3.1), this implies that

$\displaystyle\mathcal{S}_{n}$ $\displaystyle(x,z)-\mathcal{S}_{n}(x,y)$
$\displaystyle=n^{1/6}\left[\\{(\pi\\{\bar{X}_{1},\hat{y}\\}_{n}(\hat{R}_{n}),\hat{R}_{n})\to
z\\}-\\{(\pi\\{\bar{X}_{1},\hat{y}\\}_{n}(\hat{R}_{n}),R_{n})\to
y\\}\right]-2(z-y)n^{1/3}.$

The convergence of the functions $Z^{n}_{k}$ on
$\mathbb{Q}^{+}\times\mathbb{Q}$ guarantees that the sequence $\\{R_{n}\\}$ is
tight. Letting $R$ be a subsequential limit of $R_{n}$, and passing to the
Airy line ensemble limit in the above formula, we get that

$\mathcal{S}(x,z)-\mathcal{S}(x,y)=\langle(\pi\langle X_{1},y\rangle(R),R)\to
z\rangle-\langle(\pi\langle X_{1},y\rangle(R),R)\to y\rangle.$ (36)

Now, since a point lying along a path is a closed condition, the point
$(\pi\langle X_{1},y\rangle(R),R)$ lies along both of the paths $\pi\langle
X_{1},y\rangle$ and $\pi\langle X_{2},z\rangle$. Also, property 3 guarantees
that there exists a random $K\in\mathbb{N}$ such that

$-\sqrt{k/(2x)}\in[Z_{k}(X_{1},y),Z_{k}(X_{2},z)].$ (37)

for all $k\geq K$. Fix $k\geq K$, and let $\tau_{y}$ and $\tau_{z}$ be the
rightmost last passage paths in the Airy line ensemble from
$(-\sqrt{K/(2x)},K)$ to $(y,1)$ and $(z,1)$ respectively. Monotonicity of last
passage paths along with (37) then implies that the point $(\pi\langle
X_{1},y\rangle(R),R)$ must lie along both $\tau_{y}$ and $\tau_{z}$. The tree
structure of last passage paths then implies that

$\tau_{y}=\pi\langle X_{1},y\rangle\quad\;\text{and}\;\tau_{z}=\pi\langle
X_{2},z\rangle$

on the intervals $[R,y]$ and $[R,z]$, and that $\tau_{y}=\tau_{z}$ on the
interval $[-\sqrt{K/(2x)},R]$. In particular, this allows us to rewrite (36)
as

$\langle(-\sqrt{k/(2x)},k)\to z\rangle-\langle(-\sqrt{k/(2x)},k)\to
y\rangle.\qed$

##  9 Properties of the Airy sheet

In this section we prove a few basic properties of the Airy sheet.

The following properties are inherited from Brownian last passage percolation.
For the second property, use Proposition 3.8.

######  Lemma 9.1.

As a random continuous function in $\mathbb{R}^{2}$ the Airy sheet satisfies

$\mathcal{S}(x,y)\stackrel{{\scriptstyle
d}}{{=}}\mathcal{S}(y,x)\quad\;\text{and}\;\quad\mathcal{S}(x,y)\stackrel{{\scriptstyle
d}}{{=}}\mathcal{S}(-x,-y).$

Moreover, for $x\leq x^{\prime},\;y\leq y^{\prime}$ we have

$\mathcal{S}(x,y)+\mathcal{S}(x^{\prime},y^{\prime})\geq\mathcal{S}(x,y^{\prime})+\mathcal{S}(x^{\prime},y).$

The metric composition law is also inherited from Brownian last passage
percolation. For the proof, we have to guarantee that the prelimiting optimal
location. We first define the Airy sheet of scale $s$ by

$\mathcal{S}_{s}(x,y)=s\mathcal{S}(xs^{-2},ys^{-2}).$

######  Proposition 9.2 (Metric composition law).

Let $\mathcal{S}_{s},\,\mathcal{S}_{t}$ be independent Airy sheets of scale
$s$ and $t$. For $(x,z)\in\mathbb{R}^{2}$, define

$Q(x,y)=\sup_{y\in\mathbb{R}}\mathcal{S}_{s}(x,y)+\mathcal{S}_{t}(y,z),$ (38)

The function $Q$ is an Airy sheet of scale $r$, where $r^{3}=s^{3}+t^{3}$.
Moreover, the largest value $Y^{+}(x,z)$ where the maximum in (38) is achieved
is nondecreasing in both $x$ and $z$. The same holds for $Y^{-}$ defined
analogously.

We have a true maximum, rather than a supremum. To prove Proposition 9.2, we
use the following lemma which gives tightness of the maximum location for two
prelimiting Airy processes.

######  Lemma 9.3.

For $n\in\mathbb{N}$ and $t\in\\{1/n,\dots,(n-1)/n\\}$, let $k=nt$ and
$m=n(1-t)$, and set $s=\min(t,1-t)$. Let $W^{k}_{1}$ and $W^{m}_{1}$ be the
top lines of two independent Brownian melons with $k$ lines and $m$ lines
respectively. Define the melon sum

$A(z)=W^{k}_{1}(z)+W^{m}_{1}(1-z).$

Let $S=\\{z:A(z)=\max_{w\in[0,1]}A(w)\\}$. Then there exist constants $c$ and
$d$ such that for all $r>0$, we have

$\sup_{n\in\mathbb{N}}\sup_{t\in\\{1/n,\dots,(n-1)/n\\}}\mathbb{P}(S\not\subset[t+rs^{1/3}n^{-1/3},t-rs^{1/3}n^{-1/3}])\leq
ce^{-dr^{3/4}}.$

To prove Lemma 9.3, we need the following calculation.

######  Lemma 9.4.

Let $b>0$ be a fixed constant. Then there exists a constant $c$ such that for
all $n\in\mathbb{N},t\in\\{1/n,2/n,\dots,(n-1)/n\\},r>1$ and

$z\in[0,t-c(\min[t,1-t])^{1/3}r^{2}n^{-1/3}]\cap[t+c(\min[t,1-t])^{1/3}r^{2}n^{-1/3},1],$

we have that

$\displaystyle 2$ $\displaystyle\left(\sqrt{ntz}+\sqrt{n(1-t)(1-z)}\right)$
(39)
$\displaystyle+r\left(\sqrt{z}(nt)^{-1/6}+\sqrt{1-z}(n(1-t))^{-1/6}\right)$
(40)
$\displaystyle+\sqrt{z}(nt)^{-1/6}b\log^{2/3}\left((nt)^{1/3}\log\left(\frac{t}{z}\vee\frac{z}{t}\right)+1\right)$
(41)
$\displaystyle+\sqrt{1-z}(n(1-t))^{-1/6}b\log^{2/3}\left((n(1-t))^{1/3}\log\left(\frac{1-t}{1-z}\vee\frac{1-z}{1-t}\right)+1\right)$
(42) $\displaystyle\qquad\qquad\qquad\leq 2\sqrt{n}-rn^{-1/6}.$

Here the notation $a\vee b$ means the maximum of $a$ and $b$.

We leave the proof of Lemma 9.4 to the end of the section. Instead we proceed
with the proof of Lemma 9.3. Throughout the proof, $c$ and $d$ are universal
constants that may change from line to line.

###### Proof.

Define $L_{n}=\max_{z\in[0,1]}A(z).$ The value $W^{k}_{1}(z)$ can be thought
of as a last passage value across $k$ independent Brownian motions
$B_{1},\dots,B_{k}$ in the interval $[0,z]$ and the value $W^{m}_{1}(1-z)$ can
be thought of as a last passage value across $m$ independent Brownian motions
$B_{k+1},\dots,B_{n}$ in the interval $[z,1]$. In particular, by Lemma 3.2,
this means that $L_{n}$ is simply a Brownian last passage value, and so by
Theorem 2.5 there exist constants $c,d>0$ such that for all $n\in N$ and
$r>0$, we have

$\mathbb{P}\left(L_{n}\geq 2\sqrt{n}-rn^{-1/6}\right)\geq 1-ce^{-dr^{3/2}}.$
(43)

Now by Proposition 2.7, there exist constants $b,c,d>0$ such that for any
$n\in\mathbb{N}$ and $r>0$, the probability that

$W^{n}_{1}(t)\leq
2\sqrt{n}\sqrt{t}+\sqrt{t}n^{-1/6}[r+b\log^{2/3}(n^{1/3}\log(t\vee
t^{-1})+1)]\;\;\forall t\in[0,\infty)$

is bounded below by $1-ce^{-dr^{3/2}}.$ The logarithmic error above is chosen
to be minimized at $t=1$. However, by Brownian scaling, we can minimize this
error at any value of $t$. In particular, we will bound the sum
$A(z)=W^{k}_{1}(z)+W^{m}_{1}(1-z)$ by choosing to minimize the error term in
$W^{k}_{1}(z)$ at $t$ and in $W^{m}_{1}(1-z)$ at $1-t$. This gives that with
probability at least $1-ce^{-dr^{3/2}}$, we have

$\begin{split}A(z)\leq&\;2\Big{(}\sqrt{kz}+\sqrt{m(1-z)}\Big{)}+\sqrt{z}k^{-1/6}\left(r+b\log^{2/3}\left(k^{1/3}\log\left(\frac{t}{z}\vee\frac{z}{t}\right)\right)\right)\\\
&+\sqrt{1-z}m^{-1/6}\left(r+b\log^{2/3}\left(m^{1/3}\log\left(\frac{1-t}{1-z}\vee\frac{1-z}{1-t}\right)\right)\right).\end{split}$
(44)

Now, by Lemma 9.4, there is a constant $c$ such that for all
$r>1,n\in\mathbb{N}$, and $t\in\\{1/n,\dots,(n-1)/n\\}$, the right hand side
above is bounded by $2\sqrt{n}-rn^{-1/6}$ for all

$z\in[0,t-cr^{2}s^{1/3}n^{-1/3}]\cup[t+cr^{2}s^{1/3}n^{-1/3},1].$

Combining the bound on the probability of the event in (44) with the bound on
$L_{n}$ in (43) implies the lemma. ∎

###### Proof of Proposition 9.2.

By rescaling, we can assume that $r=1$ and that $x=z=0$. We set up a Brownian
last passage percolation converging to an Airy sheet $\mathcal{S}$ as in the
previous section. Then last passage across the first $s^{3}$ proportion of the
Brownian motions and last passage through the second $t^{3}$ proportion of the
Brownian motions converge jointly in distribution to independent Airy sheets
$\mathcal{S}_{s},\mathcal{S}_{t}$. The metric composition law holds before
taking the limit by Lemma 3.2. This passes through to the limit for
$\mathcal{S}$, $\mathcal{S}_{s}$ and $\mathcal{S}_{t}$ since the location of
any maximum is tight by Lemma 9.3.

This extends to all $(x,z)\in\mathbb{R}^{2}$ simultaneously by monotonicity in
the following way. Setting $\mathcal{S}^{n},\mathcal{S}^{n}_{t},$ and
$\mathcal{S}^{n}_{s}$ to be the corresponding prelimiting Airy sheets, any
location in the set

$S(x,z)=\\{y:\max_{w}\mathcal{S}^{n}(x,w)+\mathcal{S}^{n}_{t}(w,z)=\mathcal{S}^{n}(x,y)+\mathcal{S}^{n}_{t}(y,z)\\}$

is lies along a last passage path. In particular, monotonicity of last passage
paths (Lemma 3.6) guarantees that both $\inf S(x,z)$ and $\sup S(x,z)$ are
increasing functions in both coordinates. Hence the pointwise tightness of
these values implies uniform tightness of these values on any compact set, and
thus metric composition holds for $\mathcal{S}$, $\mathcal{S}_{s}$ and
$\mathcal{S}_{t}$ on all of $\mathbb{R}^{2}$. Therefore the Airy sheet
$\mathcal{S}$ is equal to the function $Q$ defined in (38). The fact that
$Y^{+}$ and $Y^{-}$ are monotone in both coordinates follows from monotonicity
in the finite case. ∎

The monotonicity of $Y^{+}$ and $Y^{-}$ can also be proved without any
reference to the prelimiting Airy sheets by using the inequality in Lemma 9.1.

Our next goal is to give a near optimal bound on the location of the maximum
in Proposition 9.2. This can be stated in terms of the Airy process
$\mathcal{A}=\mathcal{A}_{1}$, the first line of the Airy line ensemble. We
define the Airy process of scale $\sigma$ from the standard one by
$\mathcal{A}_{\sigma}(\cdot)=\sigma\mathcal{A}(\cdot/\sigma^{2})$, just like
the scaling of Airy sheets. For this section, the subscript will refer to the
scale. The Tracy-Widom law of these processes is scaled by $\sigma$. The
Brownian component has variance $2$. The stationary version is

$\mathcal{A}_{\sigma}(z)+\sigma^{-3}z^{2}.$ (45)

For small scales the parabola gets more dominant.

######  Lemma 9.5.

Fix $0<s,t$, and let $\mathcal{A}_{s}$, $\mathcal{A}_{t}$ be two independent
Airy processes of scale $s$ and $t$. Then
$\mathcal{A}=\mathcal{A}_{s}+\mathcal{A}_{t}$ has a unique maximum $A$ at some
location $S$ almost surely. For any $m>0$, we have

$\mathbb{P}(S\not\subset[-ms^{2},ms^{2}])\leq
ce^{-dm^{3}}\;\;\;\text{and}\;\;\;\mathbb{P}(A-\mathcal{A}(0)>ms)\leq
ce^{-dm^{3/2}}.$

In this proof, $c$ and $d$ are universal constants that may change from line
to line.

###### Proof.

The strength of the claims is decreasing in $s$, so we can assume $s\leq t$.
By rescaling, we may also assume that $s+t=1$. Consider the stationary
versions $\mathcal{R}_{s},\mathcal{R}_{t}$ of the Airy processes as in (45)
and let $\mathcal{R}=\mathcal{R}_{s}+\mathcal{R}_{t}$. When
$t\geq(28)^{1/3}s$, Lemma 2.4 and rescaling implies that for all $z>0$, we
have

$\mathbb{P}\left(|\mathcal{R}_{t}(z)-\mathcal{R}_{t}(0)|>s^{-3}z^{2}/4\right)\leq
ce^{-dz^{3}/s^{6}}.$ (46)

When $t\in[s,(28)^{1/3}s]$, we can use the Tracy-Widom one-point bound on
$t\mathcal{R}_{t}(z)$ and $t\mathcal{R}_{t}(0)$ (Theorem 2.3) to get the same
bound. Using this same one-point bound on $s\mathcal{R}_{s}$ we also get

$\mathbb{P}\left(|\mathcal{R}_{s}(z)-\mathcal{R}_{s}(0)|>s^{-3}z^{2}/4\right)\leq
ce^{-dz^{3}/s^{6}}.$

Combining these bounds gives

$\mathbb{P}\left(\mathcal{R}(zs^{2})>\mathcal{R}(0)+sz^{2}/2\right)\leq
ce^{-dz^{3}},$

which after translating back to $\mathcal{A}$ gives that

$\mathbb{P}\left(\mathcal{A}(zs^{2})>\mathcal{A}(0)-sz^{2}/2\right)\leq
ce^{-dz^{3}},$ (47)

Now let $a>0$. By Lemma 2.4, for any $z\in\mathbb{R}$ and $y\in[0,as^{2}]$,
with $\mathcal{R}=\mathcal{R}_{s}+\mathcal{R}_{t}$ we have that

$\mathbb{P}(|\mathcal{R}(z+y)-\mathcal{R}(z)|>\ell\sqrt{y})\leq
ce^{d(49a^{3}-\ell^{2})}$ (48)

for $\ell>0$. By Lemma 2.8, the process $\mathcal{R}$ satisfies the modulus of
continuity bound

$|\mathcal{R}(z+y)-\mathcal{R}(z)|\leq C_{a,b}\sqrt{y}\log^{1/2}(2as^{2}/y)$
(49)

on any interval $[b,b+as^{2}]$ where $C_{a,b}$ is a random constant that
satisfies

$\mathbb{P}(C_{a,b}>\ell+ca^{3/2})\leq ce^{-d\ell^{2}}.$

In particular, we can use (49) and a union bound over intervals of the form
$[b,b+s^{2}]$ to get that there exists a constant $C$ satisfying the same
tails as each of the constants $C_{1,b}$ (with possibly different $c$ and $d$)
such that

$\max_{z\in[m,-m]}\mathcal{R}(zs^{2})-\mathcal{R}(z_{*}s^{2})\leq
Cs\log^{1/2}m.$

Here $z_{*}=\lfloor z\rfloor$ for $z\geq 0$ and $\lceil z\rceil$ otherwise. We
approximate $z$ with an integer closer to $0$ so that the same bound holds for
the non-stationary process $\mathcal{A}$: this way the parabolic decay does
not affect the bound. In particular, this bound combined with the bound (47)
applied to integers gives that

$\mathbb{P}(\mathcal{A}(z)>\mathcal{A}(0)\text{ for some }|z|>ms^{2})\leq
ce^{-dm^{3}}.$

This proves the bound on $S$ in the lemma. The processes
$\mathcal{A}_{s}(z)-\mathcal{A}_{s}(0),\mathcal{A}_{t}(z)-\mathcal{A}_{t}(0)$
are absolutely continuous with respect to Brownian motion of variance $2$ on a
compact interval by Proposition 2.2, and hence so is
$\mathcal{A}(z)-\mathcal{A}(0)$. Hence it has a unique maximum on any compact
interval almost surely. By the above bound on $S$ this implies that
$\mathcal{A}$ has a unique maximum almost surely.

Now we can use (49) again to get that for any $m>0$, we have

$\max_{z\in[-m,m]}\mathcal{A}(zs^{2})-\mathcal{A}(0)\leq(C+cm^{3/2})s\sqrt{m}$

for a constant $C$ satisfying

$\mathbb{P}(C>\ell)\leq ce^{-d\ell^{2}}$

for $\ell>0$. We get the desired bound on $A-\mathcal{A}(0)$ by writing

$\mathbb{P}(A-\mathcal{A}(0)>ms)\leq\mathbb{P}(|S|\geq\sqrt{m/3}s^{2})+\mathbb{P}\left(\max_{|z|\leq\sqrt{m/3}}\mathcal{A}(zs^{2})-\mathcal{A}(0)>ms\right).\qed$

Now we prove Lemma 9.4. The proof of this lemma is essentially Taylor
expansion. However, keeping track of what is happening with all the terms gets
rather complex, and so we have included a proof here. Throughout the proof,
$c_{0},c_{1},$ and $c_{2}$ are positive constants that may change from line to
line and may depend on the constant $b$ in the statement of the lemma.

###### Proof.

By symmetry, it is enough to prove the lemma for $t\leq 1/2$. We will also
write $z=t+\alpha$ where $\alpha\in[-t,1-t]$.

Step 1: Bounding the main term (39). We have the bounds

$\sqrt{1+x}\leq 1+\frac{x}{2}-\frac{x^{2}}{12},\quad
x\in[-1,1]\quad\;\text{and}\;\quad\sqrt{1+x}\leq\sqrt{2}+\frac{x-1}{2\sqrt{2}},\quad
x\geq 1.$ (50)

Using the first bound above, we can bound the term (39) on the interval
$\alpha\in[-t,t]$:

$\displaystyle 2\left(\sqrt{ntz}+\sqrt{n(1-t)(1-z)}\right)$
$\displaystyle=2\sqrt{n}\left(t\sqrt{1+\alpha/t}+(1-t)\sqrt{1-\alpha/(1-t)}\right)$
$\displaystyle\leq
2\sqrt{n}\left(1-\frac{\alpha^{2}}{12t}\right),\qquad\alpha\in[-t,t].$ (51)

We can similarly bound (39) on the interval $\alpha\in[t,1-t]$ by using the
first bound in (50) on the $t$ term and the second bound on the $1-t$ term.
This gives

$2\left(\sqrt{ntz}+\sqrt{n(1-t)(1-z)}\right)\leq
2\sqrt{n}\left(1-c_{0}\alpha\right),\qquad\alpha\in[t,1-t].$ (52)

Step 2: Bounding the error terms (40) + (41) + (42). We first consider the
case $\alpha\in[-t,0]$. Since $t\leq 1/2$ and $z=t+\alpha\leq t$, (40) is
bounded by $3rn^{-1/6}$. Now by using that $\log(x)\leq x-1$ and that
$\sqrt{t+\alpha}\leq\sqrt{t}$, we can bound (41) above by

$\displaystyle n^{-1/6}$
$\displaystyle\left((t+\alpha)^{1/3}b\log^{2/3}\left((nt)^{1/3}\frac{|\alpha|}{t+\alpha}+1\right)\right)$
$\displaystyle=c_{1}n^{-1/6}\left((t+\alpha)^{1/3}\log^{2/3}\left((nt)^{1/3}|\alpha|+t+\alpha\right)-(t+\alpha)^{1/3}\log^{2/3}(t+\alpha)\right)$
$\displaystyle\leq c_{1}n^{-1/6}\left(\log(n^{1/3}|\alpha|+1)+1\right).$ (53)

We can also use the bound $\log(x)\leq x-1$ and the fact that $1-t$ and $1-z$
are bounded away from zero to get that for $\alpha\in[-t,0]$, that (42) is
bounded above by

$\displaystyle\sqrt{1-z}(n(1-t))^{-1/6}b\log^{2/3}\left((n(1-t))^{1/3}\frac{|\alpha|}{1-t}+1\right)\leq
c_{1}n^{-1/6}\left(\log\left(|\alpha|n^{1/3}+1\right)+1\right).$

Combining this with the bound (53) and the bound of $3rn^{-1/6}$ on (40) for
$\alpha\in[-t,0]$ gives that

(40)+(41)+ (42) $\displaystyle\leq
c_{1}n^{-1/6}\left(\log(n^{1/3}|\alpha|+1)+1+3r\right)$ $\displaystyle\leq
c_{1}n^{-1/6}\left(\log(n^{1/3}|\alpha|+1)+r\right)\qquad\alpha\in[-t,0].$
(54)

We have folded the constant term into the $r$ term by using that $r\geq 1$.
Now when $\alpha\in[0,1-t]$, we can bound (40) by

$rcn^{-1/6}\left(1+t^{-1/6}\sqrt{\alpha}\right).$ (55)

Again using that $\log(x)\leq x-1$, we can bound the term (41) for
$\alpha\in[0,1-t]$ by

$\displaystyle\sqrt{t+\alpha}(nt)^{-1/6}b\log^{2/3}$
$\displaystyle\left((nt)^{1/3}\frac{\alpha}{t}+1\right)$
$\displaystyle\leq\left(\sqrt{t}+\sqrt{\alpha}\right)t^{-1/6}n^{-1/6}b\left(\log^{2/3}\left(n^{1/3}\alpha+t^{2/3}\right)+\log^{2/3}(t^{-2/3})\right)$
$\displaystyle\leq
c_{1}n^{-1/6}\left(1+\sqrt{\alpha}t^{-1/6}\log(t^{-2/3})+(\sqrt{\alpha}t^{-1/6}+1)\log(n^{1/3}\alpha+1)\right).$
(56)

We can also bound (42) for $\alpha\in[0,1-t]$ by

$\displaystyle\sqrt{1-t-\alpha}(n(1-t))^{-1/6}b$
$\displaystyle\left(\log^{2/3}\left((n(1-t))^{1/3}\alpha+1-t-\alpha\right)-\log^{2/3}(1-t-\alpha)\right)$
$\displaystyle\leq c_{1}n^{-1/6}\left(1+\log(n^{1/3}\alpha+1)\right).$

Combining this with the bounds (55) and (56) implies that

$\displaystyle\text{\eqref{E:err-0} + \eqref{E:err-1} + \eqref{E:err-2}}\leq
c_{1}n^{-1/6}\left((\sqrt{\alpha}t^{-1/6}+1)\log(n^{1/3}\alpha+1)+r+r\sqrt{\alpha}t^{-1/6}\log(t^{-2/3})\right)$
(57)

for $\alpha\in[0,1-t]$. Note that on the interval $[0,t]$, this reduces to the
bound (54).

Step 3: The case $\alpha\in[-t,t]$. By combining the inequalities (51), (54),
and (57), we get that the inequality in the lemma holds whenever

$\displaystyle
c_{1}\frac{\alpha^{2}n^{2/3}}{t}-c_{2}\log(n^{1/3}|\alpha|+1)>c_{3}r.$

Making the substitution $\alpha=\beta r^{2}t^{1/3}n^{-1/3}$ and using that
$t<1$, the above statement is implied by the inequality

$c_{1}r^{4}\beta^{2}-c_{2}\log(|\beta|r+1)>c_{3}r.$

This holds for all $r>1$ as long as $\beta$ is large enough.

Step 4: The case $\alpha\in[t,1-t]$. By combining the inequalities (52) and
(57) we get that the inequality in the lemma holds whenever

$c_{0}n^{2/3}\alpha-
c_{1}\left((\sqrt{\alpha}t^{-1/6}+1)\log(n^{1/3}\alpha+1)+r+r\sqrt{\alpha}t^{-1/6}\log(t^{-2/3})\right)>0$

Again making the substitution $\alpha=\beta r^{2}t^{1/3}n^{-1/3}$ the left
hand side above is equal to

$c_{0}n^{1/3}\beta r^{2}t^{1/3}-c_{1}\left((1+\sqrt{\beta}rn^{-1/6})\log(\beta
r^{2}t^{1/3}+1)+r(1+\sqrt{\beta}rn^{-1/6}\log(t^{-2/3}))\right).$

Since $t\geq n^{-1}$, this is bounded below by

$c_{0}\beta r^{2}-c_{1}\left((1+r\sqrt{\beta})\log(\beta
r+1)+r(1+\sqrt{\beta}r)\right).$

For all large enough $\beta$, this is strictly greater than $0$ for all $r>1$.
∎

##  10 The directed landscape

The goal of this section is to construct the directed landscape, a scale-
invariant, stationary, independent increment process with respect to metric
composition. The following definition is based on analogies from last passage
percolation. Recall that

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

Let $C(\mathbb{R}^{4}_{\uparrow},\mathbb{R})$ be the space of continuous
functions from $\mathbb{R}^{4}_{\uparrow}$ to $\mathbb{R}$ with the uniform-
on-compact topology.

######  Definition 10.1.

A directed landscape is a random function $\mathcal{L}$ taking values in the
space $C(\mathbb{R}^{4}_{\uparrow},\mathbb{R})$ that satisfies the following
properties.

  1. I.

(Airy sheet marginals) For any $t\in\mathbb{R}$ and $s>0$ the increment over
time interval $[t,t+s^{3})$,

$(x,y)\mapsto\mathcal{\mathcal{L}}(x,t;y,t+s^{3})$

is an Airy sheet of scale $s$.

  2. II.

(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}),\quad i\in\\{1,\dots,k\\}$

are independent.

  3. III.

(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)]\quad\text{
for all }x,y\in\mathbb{R}.$

We note here that the metric composition law implies a triangle inequality for
the directed landscape. For any $r<s<t$ and $x,y,z\in\mathbb{R}$ we have that

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

Condition (iii) could be weakened so that the metric composition law only
holds at every fixed quintuple $(r,s,t,x,y)$ almost surely, rather than at all
quintuples simultaneously.

We need to show that an object satisfying the above properties exists and is
unique. Before constructing the directed landscape, we note that if such an
object $\mathcal{L}$ exists and is unique, then it must have the following
symmetries.

######  Lemma 10.2.

Let $\mathcal{L}$ denote the directed landscape. Assuming that $\mathcal{L}$
exists and is unique, we have the following equalities in distribution as
functions in $C(\mathbb{R}^{4}_{\uparrow},\mathbb{R})$. Here
$r,c\in\mathbb{R}$, and $q>0$.

  1. 1.

(Time stationarity)

$\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 symmetries)

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

  4. 4.

(Skew 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.

(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)).$

###### Proof.

All of these statements can be checked by straightforward computation. The
only tools needed are symmetries and rescaling properties of the Airy sheet,
along with the definition of the directed landscape. ∎

We will also work with the process

$\mathcal{L}(x,t;y,t+s)+\frac{(x-y)^{2}}{s}.$ (58)

which has true spatial stationarity instead of skew-stationarity. We first
construct the directed landscape on an appropriate dense subset of
$\mathbb{R}^{4}_{\uparrow}$. Define the sets

$S_{k}=\\{(x,t;y,s)\in\mathbb{R}_{\uparrow}^{4}:t<s,2^{k}t,2^{k}s\in\mathbb{Z}\\}.$

and let $S=\bigcup_{k}S_{k}$.

######  Lemma 10.3.

There exist a random function $\mathcal{L}:S\to\mathbb{R}$ satisfying
conditions I-III in the definition of the directed landscape. Its law is
unique.

###### Proof.

Any process $\mathcal{L}:S\to\mathbb{R}$ can be viewed as a random function
from the countable set

$D=\\{s<t:2^{k}s,2^{k}t\in\mathbb{Z}\text{ for some $k\in\mathbb{N}$}\\}$

to the space of functions from $\mathbb{R}^{2}\to\mathbb{R}$. As conditions
I-III above determine the joint distribution of
$\mathcal{L}(d_{1}),\dots,\mathcal{L}(d_{k})$ for any $d_{1},\dots,d_{k}\in
D$, the distribution of a process satisfying these conditions is unique. We
now show that $\mathcal{L}$ exists.

First we define $\mathcal{L}$ for parameters in the set $S_{k}$. For this,
pick independent Airy sheets $B_{i}$ for each $i\in\mathbb{Z}$, and for
$t=i/2^{k}$ and $s^{3}=1/2^{k}$ we define

$s^{-1}\mathcal{L}_{k}(s^{2}x,t;s^{2}y,t+s^{3})=B_{i}(x,y).$

Moreover, for $j=i+\ell$, $\ell\geq 1$ we define

$\mathcal{L}_{k}(x_{0},i/2^{k};x_{\ell},j/2^{k})=\max_{(x_{1},\ldots
x_{\ell-1})\in\mathbb{R}^{\ell}}\sum_{q=1}^{\ell}\mathcal{L}_{k}\left(x_{q-1},\frac{i+q-1}{2^{k}};x_{q},\frac{i+q}{2^{k}}\right).$

By the metric composition law for Airy sheets (Proposition 9.2) the following
holds. First, $\mathcal{L}_{k}$ satisfies properties I-III on the set $S_{k}$.
Also, for $k<k^{\prime}$ the process $\mathcal{L}_{k^{\prime}}$ restricted to
$S_{k}$ has the same law as $\mathcal{L}_{k}$. Kolmogorov’s extension theorem
then provides a limiting process $\mathcal{L}$ on $S=\bigcup_{k}S_{k}$, which
when restricted to $S_{k}$ has the same law as $\mathcal{L}_{k}$ for all $k$.
Therefore the process $\mathcal{L}$ satisfies properties I-III. ∎

In order to show that $\mathcal{L}$ has a unique continuous extension to
$\mathbb{R}^{4}_{\uparrow}$ it suffices check that $\mathcal{L}$ is almost
surely uniformly continuous on $K\cap S\cap\mathbb{Q}^{4}$ for any compact set
$K\subset\mathbb{R}^{4}_{\uparrow}$. This follows by proving an explicit tail
bound on two-point differences for $\mathcal{L}$.

######  Lemma 10.4.

Let $\mathcal{L}$ be any random function defined on the dyadic set $S$ that
satisfies conditions I and III in the definition of the directed landscape.
Let $\mathcal{K}$ be the stationary version of $\mathcal{L}$ as defined in
(58). Let $(x_{i},t_{i};y_{i},s_{i})$ for $i=1,2$ be points in $S$. Define

$\xi=||(x_{1},y_{1})-(x_{2},y_{2})||,\;\;\tau=||(t_{1},s_{1})-(t_{2},s_{2})||\;\;\;\text{and}\;\;\;\delta=\min(|t_{1}-s_{1}|,|t_{2}-s_{2}|).$

Then as long as $\xi\leq\delta^{2/3}$, we have that

$\mathbb{P}\left(|\mathcal{K}(x_{1},t_{1};y_{1},s_{1})-\mathcal{K}(x_{2},t_{2};y_{2},s_{2})|\geq
m\tau^{1/3}+\ell\xi^{1/2}\right)\leq ce^{-dm^{3/2}}+ce^{-d\ell^{2}}.$

for universal constants $c$ and $d$.

Throughout the proof, $b,c$ and $d$ are universal constants that may change
from line to line.

###### Proof.

We will first change spatial coordinates and then change time coordinates. By
Lemma 2.4 applied twice, we have bound

$\mathbb{P}(|\mathcal{K}(x_{1},t_{1};y_{1},s_{1})-\mathcal{K}(x_{2},t_{1};y_{2},s_{1})|>\ell\xi^{1/2})\leq
ce^{-d\ell^{2}}.$

This used the fact that $\mathcal{K}$ has rescaled stationary Airy sheet
marginals. The upper bound on $\xi$ comes from the fact that Lemma 2.4 (after
Airy sheet rescaling) can only be applied when $\ell\geq
7\delta^{-1}\xi^{3/2}$. We now bound the difference when we change time.
Without loss of generality, assume that $s_{1}\leq s_{2}$. By the triangle
inequality, it suffices to show that

$\displaystyle\mathbb{P}(|\mathcal{K}(x_{2},t_{1};y_{2},s_{1})$
$\displaystyle-\mathcal{K}(x_{2},t_{1};y_{2},s_{2})|>m\tau^{1/3})\;\;\;\text{and}\;$
$\displaystyle\mathbb{P}(|\mathcal{K}(x_{2},t_{1};y_{2},s_{2})$
$\displaystyle-\mathcal{K}(x_{2},t_{2};y_{2},s_{2})|>m\tau^{1/3})$

are bounded by $ce^{-dm^{3/2}}$. We will just bound the first term, as the
second term can be bounded similarly. For this, we assume that $s_{2}>s_{1}$,
else this is $0$. We first consider the case $x_{2}=y_{2}=0$. By the metric
composition law for $\mathcal{L}$, we have that

$\displaystyle\mathcal{L}(0,t_{1};0,s_{1})$
$\displaystyle+\mathcal{L}(0,s_{1};0,s_{2})\leq\mathcal{L}(0,t_{1};0,s_{2})\leq\max_{z\in\mathbb{R}}[\mathcal{L}(0,t_{1};z,s_{1})+\mathcal{L}(z,s_{1};0,s_{2})].$
(59)

By Lemma 9.5, we have that

$\max_{z\in\mathbb{R}}[\mathcal{L}(0,t_{1};z,s_{1})+\mathcal{L}(z,s_{1};0,s_{2})]\leq
m|s_{1}-s_{2}|^{1/3}+\mathcal{L}(0,t_{1};0,s_{1})+\mathcal{L}(0,s_{1};0,s_{2})$
(60)

with probability at least $1-ce^{-dm^{3/2}}$. Also, the random variable
$\mathcal{L}(0,s_{1};0,s_{2})$ is a rescaled Tracy-Widom2 random variable by
Theorem 2.3, and so it satisfies

$\mathbb{P}(|\mathcal{L}(0,s_{1};0,s_{2})|>m|s_{1}-s_{2}|^{1/3})\leq
ce^{-dm^{3/2}}$

for universal constants $c$ and $d$. Together with (59) and (60), this gives
that

$\mathbb{P}(|\mathcal{L}(0,t_{1};0,s_{1})-\mathcal{L}(0,t_{1};0,s_{2})|>m\tau^{1/3})\leq
ce^{-dm^{3/2}}.$

For the case when $(x_{2},y_{2})\neq(0,0)$, note that while $\mathcal{L}$ may
not satisfy the skew and spatial symmetry properties in Lemma 10.2, any skewed
or spatially shifted version will still have Airy sheet marginals and satisfy
the metric composition law. Hence the above bound goes through with the same
values of $c$ and $d$. ∎

The process $\mathcal{L}$ constructed in Lemma 10.3 thus has a unique
continuous extension to $\mathbb{R}^{4}_{\uparrow}.$ We cannot quite conclude
that it satisfies Definition 10.1 since we need to check that the metric
composition law extends off of $S$. To prove this, we first prove various
uniform bounds on $\mathcal{L}$. These will also be used later when
constructing directed geodesics.

The first result gives an essentially optimal modulus of continuity, up to
constant factors. For this, we define

$K_{b}=[-b,b]^{4}\cap\\{(x,t;y,t+s)\in\mathbb{R}^{4}_{\uparrow}:s\geq
b^{-1}\\}.$

######  Proposition 10.5.

Let

$\mathcal{K}(x,t;y,t+s)=\mathcal{L}(x,t;y,t+s)+\frac{(x-y)^{2}}{s}$

denote the stationary version of the directed landscape. For two points
$\\{u_{i}=(x_{i},t_{i};y_{i},s_{i})\\}_{i=1,2}$, let $\tau=\tau(u_{1},u_{2})$
and $\xi=\xi(u_{1},u_{2})$ be as defined in Lemma 10.4. Then for any
$u_{1},u_{2}\in K_{b}$ with $\xi\leq b^{-2/3}$, we have that