Geodesic length and shifted weights
in first-passage percolation

Irregular and stochastic growth surrounds us, for example in tumors, bacterial colonies, infections, spread of fluid in a porous medium, and propagating flame fronts. These phenomena attract the attention of mathematicians, scientists and engineers in various disciplines. Simplified mathematical models of stochastic growth have been studied in probability theory for over half a century. This work has inspired some of the central innovations of modern probability, such as the subadditive ergodic theorem, and created new connections between probability and other parts of mathematics, such as representation theory, integrable systems, and partial differential equations.

A class of much-studied stochastic growth models possess a metric-like structure where growth progresses along paths that optimize an energy functional defined in terms of a random environment. Depending on whether the optimal path is chosen through minimization or maximization, these models are called first-passage percolation and last-passage percolation.

A variety of settings for first- and last-passage percolation are studied. The admissible paths can be general or they can be restricted to be directed along some spatial directions. The underlying space can be a graph, the continuum, or a mixture of the two. In the graph case, the environment is given by random weights attached to the vertices or the edges. The most typical choice of graph is the $d$-dimensional integer lattice $\mathbb{Z}^{d}$. The one-dimensional case usually reduces to classical probability so the real work begins from the planar case $d=2$.

Much progress in the planar case has taken place over the past 25 years under the rubric Kardar-Parisi-Zhang universality. A universal planar continuum limit, the directed landscape, has recently been constructed [8]. It is expected to be the scaling limit of a wide class of planar first- and last-passage percolation models, but this remains conjectural at present. Evidence for the universality comes from proofs that certain special exactly solvable directed models converge to the directed landscape [9]. We refer the reader to articles [4, 6] and the monograph [2] for general introductions to the field.

Our paper studies first-passage percolation with undirected paths on the integer lattice in arbitrary dimension. This has proved to be, in a sense, the most challenging model, as no exactly solvable version has been discovered. A proof that this model lies in the KPZ class, while universally expected, appears well beyond reach in the current state of the field. Our results concern properties of the geodesics and the regularity of the limiting norm as we perturb the random weights by a common additive constant. We turn to discuss the background.

In first-passage percolation (FPP) a random pseudometric is defined on $\mathbb{Z}^{d}$ by $T_{x,y}=\inf_{\pi}\sum_{e\hskip 0.55pt\in\hskip 0.55pt\pi}t(e)$ where the $\{t(e)\}$ are nonnegative, independent and identically distributed (i.i.d.) random weights on the nearest-neighbor edges between vertices of $\mathbb{Z}^{d}$ and the infimum is over self-avoiding paths $\pi$ between the two points $x$ and $y$. A minimizing path is called a geodesic between $x$ and $y$. FPP was introduced by Hammersley and Welsh [12] in 1965 as a simplified model of fluid flow in an inhomogeneous medium. A precise technical definition of the model comes in Section 2.

The fundamental questions of FPP concern the behavior of the passage times $T_{x,y}$ and the geodesics as the distance between $x$ and $y$ grows. At the level of the law of large numbers, under suitable hypotheses, normalized passage times converge with probability one: $n^{-1}T_{\mathbf{0},x_{n}}\to\mu(\xi)$ as $n\to\infty$, whenever $n^{-1}x_{n}\to\xi\in\mathbb{R}^{d}$. The special case $\mu(\mathbf{e}_{1})=\lim_{n\to\infty}n^{-1}T_{\mathbf{0},n\mathbf{e}_{1}}$ of the limit is also called the time constant.

The limiting shape function $\mu$ is a norm that characterizes the asymptotic shape of a large ball. Define the randomly growing ball in $\mathbb{R}^{d}$ for $t\geq 0$ by $B(t)=\{x\in\mathbb{R}^{d}:T_{\mathbf{0},\lfloor{x}\rfloor}\leq t\}$ where $\lfloor{x}\rfloor\in\mathbb{Z}^{d}$ is obtained from $x\in\mathbb{R}^{d}$ by taking integer parts coordinatewise. Under the right assumptions, as $t\to\infty$ the normalized ball $t^{-1}B(t)$ converges to the unit ball $\mathcal{B}=\{\xi\in\mathbb{R}^{d}:\mu(\xi)\leq 1\}$ defined by the norm $\mu$.

The shape function $\mu$ is not explicitly known in any nontrivial example. Soft properties such as convexity, continuity, positive homogeneity, and $\mu(\xi)>0$ for $\xi\neq\mathbf{0}$ when zero-weight edges are subcritical, are readily established. But anything beyond that, such as strict convexity or differentiability, remain conjectural. The only counterexample to this state of affairs is the classic Durrett-Liggett [10] planar flat edge result, sharpened by Marchand [15], and then extended by Auffinger and Damron [1] to include differentiability at the boundary of the flat edge.

The FPP shape theorem occupies a venerable position as one of the fundamental results of the subject of random growth models and as an early motivator of subadditive ergodic theory. The reader is referred to the monograph [2] for a recent overview of the known results and open problems.

The success of the shape theorem contrasts sharply with the situation of another natural limit question, namely the behavior of the normalized Euclidean length (number of edges) of a geodesic as one endpoint is taken to infinity. No useful subadditivity or other related property has been found. This issue has been addressed only a few times over the 55 years of FPP study and the results remain incomplete.

The fundamental observation due to Hammersley and Welsh is the connection between (i) the limit of the normalized length of the geodesic and (ii) the derivative of the shape function as a function of a weight shift. For $h\in\mathbb{R}$ let $\mu^{(h)}(\xi)$ denote the shape function for the shifted weights $\{t(e)+h\}$. Let $\underline{L}_{\hskip 0.9pt\mathbf{0},x}^{(h)}$ be the minimal Euclidean length of a geodesic from the origin to the point $x$ for the shifted weights $\{t(e)+h\}$. Then the important fact is that when $n^{-1}x_{n}\to\xi$,

provided the derivative at $h$ on the right-hand side exists.

The shape function $\mu^{(h)}(\xi)$ is a concave function of $h$ and hence the derivative in (1.1) exists and the limit holds for all but countably many shifts $h$. But since the time constant itself remains a mystery, not a single specific nontrivial case where this identity holds has been identified. The first results on the size of the set of exceptional $h$ at which the derivative on the right fails are proved in the present paper and summarized in Sections 1.5 and 1.6 below.

Here is a brief accounting of the history of (1.1).

Hammersley and Welsh (Theorem 8.2.3 in [12]) gave the first version of (1.1). It was proved for the time constant of planar FPP, so for $d=2$ and $\xi=\mathbf{e}_{1}$, and for the particular sequence $x_{n}=(n,0)$. Their result applied to the geodesic of the so-called cylinder passage time from $(0,0)$ to $(n,0)$, and the mode of convergence in (1.1) was convergence in probability.

The limit (1.1) was improved in 1978 by Smythe and Wierman (Theorem 8.2 in [18]) and in 1980 by Kesten [13], in particular from convergence in probability to almost sure convergence. The ultimate version has recently been established by Bates (Theorem 1.25 in [3]): almost sure convergence in (1.1) without any moment assumptions on the weights, in all directions $\xi$, provided the derivative on the right exists.

A handful of precise results related to (1.1) exist in specific situations defined by criticality in percolation. Let $p_{c}$ denote the critical probability of Bernoulli bond percolation on $\mathbb{Z}^{d}$. When $\mathbb{P}(t(e)=0)\geq p_{c}$ the FPP problem becomes in a sense degenerate. Geodesics to far-away points can take advantage of long paths of zero-weight edges and the shape function $\mu$ becomes identically zero.

Zhang [21] proved in 1995 that in the supercritical case defined by $\mathbb{P}(t(e)=0)>p_{c}$, for $\xi=\mathbf{e}_{1}$ and $h=0$, the limit on the left in (1.1) exists and equals a nonrandom constant. In the planar critical case, that is, $d=2$, $\mathbb{P}(t(e)=0)=1/2=p_{c}$ and $h=0$, Damron and Tang [7] proved that the left-hand side in (1.1) blows up in all directions $\xi$.

In 2003 Steele and Zhang [19] proved the first, and before the present paper the only, precise result about the derivative in (1.1), valid for subcritical planar FPP with Bernoulli weights. When the distribution is $\mathbb{P}(t(e)=0)=p=1-\mathbb{P}(t(e)=1)$, there exists $\delta>0$ such that, if $\tfrac{1}{2}-\delta\leq p<\tfrac{1}{2}$, $d=2$ and $\xi=\mathbf{e}_{1}$, then the derivative in (1.1) fails to exist at $h=0$. Thus the Hammersley-Welsh differentiability criterion for the convergence of normalized geodesic length faces a limitation.

We move on to describe the contents of our paper. To investigate (1.1) and more broadly properties of geodesic length, we develop a convex duality between the weight shift $h$ and a parameter that captures the asymptotic length of a path. This puts the limit (1.1) into a convex-analytic framework. To account for the possibility of nondifferentiability in (1.1), we enlarge the class of paths considered from genuine geodesics to $o(n)$-approximate geodesics. These are paths whose endpoints are order $n$ apart and whose passage times are within $o(n)$ of the optimal passage time. Through these we can capture the entire superdifferential of the shape function as a function of the shift $h$.

To be able to work explicitly with the path-length parameter, we introduce a version of FPP that minimizes over paths with a given number of steps but drops the requirement that paths be self-avoiding (Section 2.3). A further useful variant of the restricted path length FPP process allows zero-length steps that do not increase the passage time. The shape functions $g$ and $g^{o}$ of these altered models are no longer positively homogeneous, but they turn out to be continuously differentiable along rays from the origin (Theorem 2.16).

The restricted path length shape functions $g$ and $g^{o}$ are connected with the FPP shape function $\mu$ in several ways. A key fact is that $g$ and $g^{o}$ agree with $\mu$ on certain subsets of $\mathbb{R}^{d}$ described by positively homogeneous functions that are connected with geodesic length (Theorems 2.11 and 2.16). Second, $g$ and $g^{o}$ generate $\mu$ as the maximal positively homogeneous convex function dominated by $g$ and $g^{o}$ (Remark 2.15). Third, $g$ and $g^{o}$ contain the information for generating all the shifts $\mu^{(h)}$ through convex duality (Theorem 2.17 and Remark 2.18).

From this setting we derive two types of main results for FPP: results on the Euclidean length of geodesics and on the regularity of the shape function as a function of the weight shift, briefly summarized in the next two paragraphs. The proofs come through a combination of

1. (i)

   versions of the van den Berg-Kesten modification arguments [20],

2. (ii)

   the convex duality (Theorem 2.17), and

3. (iii)

   a shape theorem for the altered FPP models (Theorem 2.9 and Theorem B.1 in Appendix B).

Our results are valid on $\mathbb{Z}^{d}$ in all dimensions $d\geq 2$, under the standard moment bound needed for the shape theorem and the assumption that the minimum of the edge weight $t(e)$ has probability strictly below $p_{c}$.

One of our fundamental results is that with probability one, all geodesics from the origin to far enough lattice points $x$ have length at least $(1+\delta)|x|_{1}$ for a fixed constant $\delta>0$ (Theorem 2.5). The equality in (1.1) between the limiting normalized length of the geodesic and the derivative of the shape function, which is conditional on the existence of these quantities, is generalized to an unconditional identity between the entire interval of the asymptotic normalized lengths of the $o(n)$-approximate geodesics and the superdifferential of the shape function as a function of the weight shift (Theorem 2.17). When the random weight $t(e)$ has an atom at zero or at least two atoms that satisfy suitable linear relations with integer coefficients, there are multiple geodesics whose lengths vary on the same scale as the distance between the endpoints (Theorem 2.6). For any weight distribution with at least two atoms, this happens on a countable dense set of shifts (Theorem 2.7).

A second suite of main results concerns the regularity of the shape function $\mu^{(h)}(\xi)$ as a function of the weight shift $h$, in a fixed spatial direction $\xi\in\mathbb{R}^{d}\hskip 0.7pt\setminus\{\mathbf{0}\}$. This function is strictly concave in $h$ (Theorem 2.2). In the situations where the atoms of $t(e)$ bring about geodesics whose asymptotic normalized lengths vary, the concave function $h\mapsto\mu^{(h)}(\xi)$ acquires points of nondifferentiability. In particular, there is a countable dense set of these singularities whenever the edge weight has two atoms (Theorems 2.6 and 2.7). We extend the Steele-Zhang nondifferentiability result [19] mentioned above to all dimensions, all directions $\xi$, and all distributions with an atom at the origin. Furthermore, we disprove their conjecture that $h=0$ is the only nondifferentiability point in the Bernoulli case (Remark 2.8).

Section 2 describes the models and the main results. Section 3 describes open problems that arise from this work.

The proofs are divided into four sections. Section 4 develops soft results about the relationships between the different shape functions and the Euclidean lengths of optimal paths. The main technical Sections 5 and 6 contain the modification arguments. The final Section 7 combines the results from Sections 4, 5 and 6 to prove the main theorems.

Four appendixes contain auxiliary results that rely on standard material. Appendix A extends the FPP shape function to weights that are allowed small negative values. Appendix B proves a shape theorem for the restricted path length versions of FPP. Appendix C contains the Peierls argument that sets the stage for the modification proofs. Appendix D presents a lemma about the subdifferentials of convex functions.

We close this introduction with a mention of a significant recent extension to the differentiability approach to limits along geodesics, due to Bates [3]. By representing the weights as functions $t(e)=\tau(U_{e})$ of uniform random variables, one can consider perturbations $\widetilde{t}(e)=\tau(U_{e})+\psi(U_{e})$ of the weights and differentiate the shape function in directions $\psi$ in infinite dimensions. This way the limit in (1.1) can be upgraded to convergence of the empirical distribution of weights along a geodesic, again whenever the required derivative exists. This holds for various uncountable dense collections of weight distributions, exactly as (1.1) holds for an uncountable dense set of shifts $h$.

These more general limit results continue to share the fundamental shortcoming of the limit in (1.1), namely, that no particular nontrivial case can be identified where the limit holds. If $\mathbb{P}(t(e)=0)\geq p_{c}$ the empirical measure along a geodesic converges trivially to a pointmass at zero.

Finding extensions of our results to the general perturbations of [3] presents an interesting open problem.

Here is notation that the reader may wish quick access to. $\mathbb{Z}_{+}=\{0,1,2,3,\dotsc\}$, $\mathbb{N}=\{1,2,3,\dotsc\}$, and $\mathbb{R}_{+}=[0,\infty)$. For $n\in\mathbb{N}$, $[n]=\{1,2,\dotsc,n\}$. Standard basis vectors in $\mathbb{R}^{d}$ are $\mathbf{e}_{1}=(1,0,\dotsc,0)$, $\mathbf{e}_{2}=(0,1,0,\dotsc,0),\dotsc,\mathbf{e}_{d}=(0,\dotsc,0,1)$ and $\mathbf{0}$ is the origin of $\mathbb{R}^{d}$. The $\ell^{1}$ norm of $x=(x_{1},\dotsc,x_{d})\in\mathbb{R}^{d}$ is $|x|_{1}=\sum_{i=1}^{d}|x_{i}|$. Particular subsets of $\mathbb{R}^{d}$ that recur are $\mathcal{R}=\{\pm\mathbf{e}_{1},\dotsc,\pm\mathbf{e}_{d}\}$, $\mathcal{R}^{o}=\mathcal{R}\cup\{\mathbf{0}\}$, $\mathcal{U}=\operatorname{co}\mathcal{R}=\{\xi\in\mathbb{R}^{d}:|\xi|_{1}\leq 1\}$, and the topological interior $\operatorname{int}\mathcal{U}$.

A finite or infinite path or sequence is denoted by $x_{m\hskip 0.6pt{\boldsymbol{:}}\hskip 0.3ptn}=(x_{m},\dotsc,x_{n})$ for $-\infty\leq m\leq n\leq\infty$. Other notation for lattice paths are $x_{\raisebox{0.5pt}{\scaleobj{0.5}{\bullet}}}$ and $\pi$. The steps of a path are the nearest-neighbor edges $e_{i}=\{x_{i-1},x_{i}\}$. A finite path $x_{m\hskip 0.6pt{\boldsymbol{:}}\hskip 0.3ptn}$ that satisfies $|x_{n}-x_{m}|_{1}=n-m$ is called an $\ell^{1}$-path.

A positively homogeneous function $f$ satisfies $f(cx)=cf(x)$ for $c>0$ whenever both $cx$ and $x$ are in the domain of $f$ [17, p. 30]. One-sided derivatives of a function defined around $s\in\mathbb{R}$ are defined by $f^{\prime}(s+)=\lim_{h\searrow 0}h^{-1}[f(s+h)-f(s)]$ and $f^{\prime}(s-)=\lim_{h\searrow 0}h^{-1}[f(s)-f(s-h)]$.

The diamond $\diamond$ is a wild card for three superscripts $\langle{\tt empty}\rangle$ (no superscript at all), $o$ (zero steps allowed), and sa (self-avoiding) that distinguish different FPP processes with restricted path length.

A real number $r$ is an atom of the random edge weight $t(e)$ if $\mathbb{P}\{t(e)=r\}>0$. $M_{0}=\mathop{\mathrm{ess\,sup}}t(e)$ and $r_{0}=\mathop{\mathrm{ess\,inf}}t(e)$. Superscript $(b)$ on any quantity means that it is computed with weights shifted by $b$: $t^{(b)}(e)=t(e)+b$.

The symbol $\triangle$ marks the end of a numbered remark.

The authors would like to thank Michael Damron for sketching a route to prove the lower bound in Theorem 2.11(ii), and an anonymous referee for spotting a mistake in the proof of Theorem 2.17.

Fix an arbitrary dimension $d\geq 2$. Let ${\mathcal{E}}_{d}=\{\{x,y\}:x,y\in\mathbb{Z}^{d},|x-y|_{1}=1\}$ denote the set of undirected nearest-neighbor edges between vertices of $\mathbb{Z}^{d}$. $(\Omega,\mathfrak{S},\mathbb{P})$ is the probability space of an environment $\omega=(t(e):e\in{\mathcal{E}}_{d})$ such that the edge weights $\{t(e):e\in{\mathcal{E}}_{d}\}$ are independent and identically distributed (i.i.d.) real-valued random variables. Translations $\{\theta_{x}\}_{x\hskip 0.55pt\in\hskip 0.55pt\mathbb{Z}^{d}}$ act on $\Omega$ by $(\theta_{x}\omega){\{u,v\}}=t(\{x+u,x+v\})$ for a nearest-neighbor edge $\{u,v\}$.

A nearest-neighbor path $\pi=x_{0\hskip 0.6pt{\boldsymbol{:}}\hskip 0.3ptn}=(x_{i})_{i=0}^{n}$ is any finite sequence of vertices $x_{0},x_{1},\dotsc,x_{n}\in\mathbb{Z}^{d}$ that satisfy $|x_{i+1}-x_{i}|_{1}=1$ for each $i$. The steps of $\pi$ are the nearest-neighbor edges $e_{i}=\{x_{i-1},x_{i}\}$. The Euclidean length $|\pi|$ of $\pi$ is the number of edges, so in this case $|\pi|=n$. Then we call $\pi$ an $n$-path. The passage time of $\pi$ is the sum of the weights of its edges:

These definitions apply even if the path repeats vertices or edges, as will be allowed at times in the sequel. For notational consistency we also admit the zero-length path $\pi=x_{0\hskip 0.6pt{\boldsymbol{:}}\hskip 0.3pt0}=(x_{0})$ that has no edges and has zero passage time and length: $T(\pi)=|\pi|=0$.

The main results are described next in three parts: results for standard FPP in Section 2.2, results for restricted path-length FPP in Section 2.3, including the connections between the two types of FPP, and finally in Section 2.4 the duality between weight shift and geodesic length.

In standard first-passage percolation (FPP) the passage time between two points is defined as the minimal passage time over all self-avoiding paths. A path $\pi=x_{0\hskip 0.6pt{\boldsymbol{:}}\hskip 0.3ptn}=(x_{i})_{i=0}^{n}$ is self-avoiding if $x_{i}\neq x_{j}$ for all pairs $i\neq j$. Let $\Pi^{\text{\rm{\,sa}}}_{x,y}$ denote the collection of all self-avoiding paths from $x$ to $y$, of arbitrary but finite length. Define the passage time between $x$ and $y$ as

This definition gives $T_{x,x}=0$ because the only self-avoiding path from $x$ to $x$ is the zero-length path. A geodesic is a self-avoiding path $\pi$ that minimizes in (2.2).

When $t(e)\geq 0$ the restriction to self-avoiding paths is superfluous in the definition of $T_{x,y}$. Let $p_{c}$ denote the critical probability of Bernoulli bond percolation on $\mathbb{Z}^{d}$. A frequently used assumption in FPP is that zero-weight edges are subcritical:

For nonnegative weights, the assumption (2.3) guarantees the existence of a geodesic (Prop. 4.4 in [2]).

For $b\in\mathbb{R}$, define $b$-shifted weights by

All the quantities associated with weights $\omega^{(b)}$ acquire the superscript. For example, $T^{(b)}_{x,y}$ is the passage time in (2.2) under weights $\omega^{(b)}$. Let

denote the (essential) lower bound of the weights. So in particular, $\omega^{(-r_{0})}$ is the weight configuration shifted so that the lower bound is at zero. Since we shift weights, most of the time we have to replace (2.3) with this assumption:

Let $\{t_{i}\}$ denote i.i.d. copies of the edge weight $t(e)$. The following moment assumption will be employed for various values of $p$.

We record the Cox-Durrett shape theorem ([5], Thm. 2.17 in [2]), with a small extension to weights that can take negative values. This theorem is proved as Theorem A.1 in Appendix A.

If we require the shape function only for a single nonnegative weight distribution without the shifts, then (2.6) can be replaced with the weaker assumption (2.3), and we will occasionally do so. The shape function of unshifted weights is denoted by $\mu=\mu^{(0)}$.

To emphasize dependence on $b$ with $\xi\neq\mathbf{0}$ fixed, we write

Several of our main results concern the regularity of $\mu_{\xi}$ and its connections with geodesic length. The reason for allowing negative weights by extending the shift $b$ below $-r_{0}$ is to enable us to talk about the regularity of $\mu_{\xi}(b)$ at $b=-r_{0}$. Throughout this paper, $\varepsilon_{0}$ is the constant specified in Theorem 2.1.

Concavity implies that one-sided derivatives $\mu_{\xi}^{\prime}(b\pm)$ for $b>-r_{0}-\varepsilon_{0}$ exist, $\mu_{\xi}^{\prime}(b-)\geq\mu_{\xi}^{\prime}(b+)$, and as functions of $b$, they are nonincreasing, $\mu_{\xi}^{\prime}(b-)$ is left-continuous, and $\mu_{\xi}^{\prime}(b+)$ is right-continuous. Strict concavity is the novel part of the theorem. This property is proved in Section 7, based on the modification argument of Section 5.2.

Introduce the notation

with the superscripted variants $\underline{L}^{(b)}_{\hskip 0.9pt\mathbf{0},x}=\underline{L}_{\hskip 0.9pt\mathbf{0},x}(\omega^{(b)})$ and $\overline{L}^{\hskip 0.7pt(b)}_{\hskip 0.9pt\mathbf{0},x}=\overline{L}_{\hskip 0.9pt\mathbf{0},x}(\omega^{(b)})$ for shifted weights $\omega^{(b)}$. For a continuous weight distribution $\underline{L}_{\hskip 0.9pt\mathbf{0},x}=\overline{L}_{\hskip 0.9pt\mathbf{0},x}$ almost surely because in that case geodesics are unique almost surely. This is not the case for all shifts because as $b$ increases the geodesic jumps occasionally and at the jump locations there are two geodesics.

Recall that a geodesic for standard FPP is by definition self-avoiding. Under the assumptions of Theorem 2.1, Theorem A.1 in Appendix A proves that the following holds on an event $\Omega_{0}$ of full probability: $\overline{L}^{\hskip 0.7pt(b)}_{\hskip 0.9pt\mathbf{0},x}<\infty$ for all $x\in\mathbb{Z}^{d}$ and $b>-r_{0}-\varepsilon_{0}$, and there exist a finite deterministic constant $c$ and a finite random constant $K$ such that

We justify part (i) of Theorem 2.2. This sets the stage for further discussion. Let $b>-r_{0}-\varepsilon_{0}$. Take $0<\delta\leq b+r_{0}+\varepsilon_{0}$ and $\eta>0$. Considering the shifted weights on the minimal and maximal length geodesics of $T^{(b)}_{\mathbf{0},x}$ leads to

Rearrange to

Here are the arguments for the properties of $\mu_{\xi}$ claimed in part (i) of Theorem 2.2.

1. (i.a)

   Strict increasingness. In (2.12) take $x=x_{n}$ such that $x_{n}/n\to\xi$. Since $\overline{L}^{\hskip 0.7pt(b)}_{\hskip 0.9pt\mathbf{0},x}\geq|x|_{1}$, the inequality $\mu_{\xi}(b-\delta)\leq\mu_{\xi}(b)-\delta|\xi|_{1}$ follows by taking the limit (2.8) in (2.12).

2. (i.b)

   Concavity follows by taking the same limit in (2.13).

3. (i.c)

   Continuity of $\mu_{\xi}$ on the open interval $(-r_{0}-\varepsilon_{0},\infty)$ follows from concavity.

Since $\underline{L}^{(b)}_{\hskip 0.9pt\mathbf{0},x}\geq|x|_{1}$, (2.13) and the monotonicity of the derivatives give the easy bound

A corollary of the strict concavity given in Theorem 2.2(ii) is the strict inequality $\mu_{\xi}^{\prime}(b\pm)>|\xi|_{1}$. The next theorem records a slight strengthening of this and consequences of (2.11) and (2.13). A precise proof is given in Section 7.

The first inequality in (2.15) says that the strict concavity gap $\mu_{\xi}^{\prime}(b+)>|\xi|_{1}$ is uniform across all directions $|\xi|_{1}=1$. This point is further strengthened to a uniformity for fixed weight configurations $\omega$ in Theorem 2.5.

The first inequality in (2.15) implies that asymptotically the lengths of geodesics in a particular direction $\xi$ exceed the $\ell^{1}$-distance. The next theorem strengthens this to a uniformity across all sufficiently faraway lattice endpoints. Its proof in Section 7 relies on the convex duality described in Section 2.4, the restricted path length shape theorem of Appendix B, and the modification arguments of Section 5.

We turn to nondifferentiability results for $\mu_{\xi}$. An atom of the weight distribution is a value $r\in\mathbb{R}$ such that $\mathbb{P}\{t(e)=r\}>0$.

For unbounded weights the result above can be proved under more general assumptions on the atoms (see Theorem 6.2 in Section 6).

The proof of Theorem 2.7 in Section 7.2 constructs the singularity set $B$ explicitly from two atoms of $t(e)$ as a countably infinite union of arithmetic sequences.

Next we discuss FPP models that restrict the length of the paths over which the optimization takes place but give up the self-avoidance requirement. Remark 2.15 below characterizes the FPP shape function $\mu$ as the positively homogeneous convex function generated by the restricted path shape functions. In the next Section 2.4 this leads to the convex duality of $\mu_{\xi}$ and a sharpening of Theorem 2.3, and further conceptual understanding of the previous results.

It turns out convenient to consider also a version whose paths are allowed zero steps. In this case the set $\mathcal{R}=\{\pm\mathbf{e}_{1},\dotsc,\pm\mathbf{e}_{d}\}$ of admissible steps is augmented to $\mathcal{R}^{o}=\mathcal{R}\cup\{\mathbf{0}\}$. For $x,y\in\mathbb{Z}^{d}$ and $n\in\mathbb{N}$ define three classes of paths $x_{0\hskip 0.6pt{\boldsymbol{:}}\hskip 0.3ptn}=(x_{i})_{i=0}^{n}$ from $x$ to $y$ of length $n$, presented here from largest to smallest:

The superscript in $\Pi^{\text{\rm{\,sa}}}$ is for self-avoiding. Paths in $\Pi_{\hskip 0.55ptx,(n),y}$ and $\Pi^{o}_{\hskip 0.55ptx,(n),y}$ are allowed to repeat both vertices and edges. Paths in $\Pi_{\hskip 0.55ptx,(n),y}$ are called $\mathcal{R}$-admissible, and those in $\Pi^{o}_{\hskip 0.55ptx,(n),y}$ $\mathcal{R}^{o}$-admissible. An $n$-path $x_{0\hskip 0.6pt{\boldsymbol{:}}\hskip 0.3ptn}$ from $x_{0}=x$ to $x_{n}=y$ is an $\ell^{1}$-path if $n=|y-x|_{1}$. For $n=0$ and $\diamond\in\{\langle{\tt empty}\rangle,o,\text{sa}\}$ we define each collection $\Pi^{\,\diamond}_{\hskip 0.55ptx,(0),x}$ as consisting only of the zero-length path $(x)$. For $x\neq y$, $\Pi_{\hskip 0.55ptx,(n),y}$ and $\Pi^{\text{\rm{\,sa}}}_{\hskip 0.55ptx,(n),y}$ are nonempty if and only if $n-|y-x|_{1}$ is a nonnegative even integer, while $\Pi^{o}_{\hskip 0.55ptx,(n),y}$ is nonempty if and only if $n\geq|y-x|_{1}$.

With the three classes of paths go three collections of points reachable by an admissible path of length $n$ from the origin: for the three superscripts $\diamond\in\{\langle{\tt empty}\rangle,o,\text{sa}\}$, define

If $0\leq k<n$, any $k$-path can be augmented to an $n$-path by adding $n-k$ zero steps, and hence we have $\mathcal{D}^{o}_{n}=\cup_{0\leq k\leq n}\mathcal{D}_{k}$.

The environment $\omega=(t(e):e\in{\mathcal{E}}_{d})$ is extended to zero steps by stipulating that zero steps always have zero weight, even when weights are shifted: $t^{(b)}(\{x,x\})=0$ $\forall x\in\mathbb{Z}^{d}$ and $b\in\mathbb{R}$.

Define three point-to-point first-passage times between two points $x,y\in\mathbb{Z}^{d}$ with restricted path lengths: for $\diamond\in\{\langle{\tt empty}\rangle,o,\text{sa}\}$,

If $\Pi^{\,\diamond}_{\hskip 0.55ptx,(n),y}=\varnothing$, set $G^{\,\diamond}_{x,(n),y}=\infty$. Obvious relations hold between these passage times and the standard FPP from (2.2):

and

For nonnegative weights the restriction to self-avoiding paths is superfluous for $T_{x,y}$ and hence