Geodesics Toward Corners in First Passage Percolation

Abstract

For stationary first passage percolation in two dimensions, the existence and uniqueness of semi-infinite geodesics directed in particular directions or sectors has been considered by Damron and Hanson (Commun Math Phys 325(3):917–963, 2014), Ahlberg and Hoffman (Random coalescing geodesics in first-passage percolation, arXiv:1609.02447 [math.PR]), and others. However the main results do not cover geodesics in the direction of corners of the limit shape $\mathcal {B}$, where two facets meet. We construct an example with the following properties: (i) the limiting shape is an octagon, (ii) semi-infinite geodesics exist only in the four axis directions, and (iii) in each axis direction there are multiple such geodesics. Consequently, the set of points of $\partial \mathcal {B}$ which are in the direction of some geodesic does not have all of $\mathcal {B}$ as its convex hull.

1 Introduction

We consider stationary first passage percolation (FPP) on a lattice $\mathbb {L}$ with site set $\mathbb {Z}^2$, and with a set of bonds which we denote $\mathcal {E}$. We are mainly interested in the usual set of nearest-neighbor bonds $\mathcal {E}= \{ (x,y) ; \Vert x-y \Vert _1 =1\}$, though in Sect. 2 we consider $\mathcal {E}$ with added diagonal bonds to construct a simpler example. Each bond e of $\mathcal {E}$ is assigned a random passage time $\tau _e\ge 0$, and the configuration $\tau$ is assumed stationary under lattice translations; the measure on the space $\varOmega = [0,\infty )^\mathcal {E}$ of configurations $\tau$ is denoted $\mathbf {P}$, with corresponding expectation $\mathbf {E}$. For sites x, y of $\mathbb {L}$, a path $\gamma$ from x to y in $\mathbb {L}$ is a sequence $x=x_0,\dots ,x_n=y$ with $x_i,x_{i+1}$ adjacent in $\mathbb {L}$ for all i; we may equivalently view $\gamma$ as a sequence of edges. The passage time $T(\gamma )$ of $\gamma$ is $T(\gamma ) = \sum _{e\in \gamma } \tau _e$. For sites x, y we define

$$\begin{aligned} T(x,y) = \inf \{T(\gamma ): \gamma \text { is a path from } x \text { to } y\}. \end{aligned}$$

A geodesic from x to y is a path which achieves this infimum. A semi-infinite geodesic $\varGamma$ from a site x is a path with (necessarily distinct) sites $x=x_0,x_1,\dots$ for which every finite segment is a geodesic, and the direction of $\varGamma$, denoted $\text {Dir}(\varGamma )$, is the set of limit points of $\{x_n/|x_n|: n\ge 1\}$. It is of interest to understand semi-infinite geodesics, and in particular the set of directions in which they exist.

It is standard to make the following assumptions, from [7].

Assumption A1

• (i) $\mathbf {P}$ is ergodic with respect to lattice translation;

• (ii) $\mathbf {E}(\tau _e^{2+\epsilon })<\infty$ for any $e\in \mathcal {E}$, for some $\epsilon >0$.

Under A1, an easy application of Kingman’s sub-additive theorem gives that for each $x\in \mathbb {Z}^2$ the limit

$$\begin{aligned} \mu (x) = \lim _{n\rightarrow \infty } \frac{T(0,nx)}{n} \end{aligned}$$

exists. This $\mu$ extends to $\mathbb {Q}^2$ by restricting to n for which $nx\in \mathbb {Z}^2$, and then to $\mathbb {R}^2$ by continuity; the resulting function is a norm (provided the limit shape defined below is bounded). Its unit ball is a nonempty convex symmetric set which we denote $\mathcal {B}$. The wet region at time t is $\mathcal {B}(t) = \{x+[-\tfrac{1}{2},\tfrac{1}{2}]^2: T(0,x)\le t\}$. The shape theorem of Boivin [2] says that with probability one, given $\epsilon >0$, for all sufficiently large t we have

$$\begin{aligned} (1-\epsilon )\mathcal {B}\subset \frac{\mathcal {B}(t)}{t} \subset (1+\epsilon )\mathcal {B}, \end{aligned}$$

so $\mathcal {B}$ is called the limit shape. Häggström and Meester [6] showed that every compact convex B with the symmetries of $\mathbb {Z}^2$ arises as the limit shape for some stationary FPP process.

We add the following assumptions, also used in [4, 7] and outlined in [1] (see A2).

Assumption A2

• (iii) $\mathbf {P}$ has all the symmetries of the lattice $\mathbb {L}$;

• (iv) if $\alpha ,\gamma$ are finite paths, with the same endpoints, differing in at least one edge then $T(\alpha ) \ne T(\gamma )$ a.s.;

• (v) $\mathbf {P}$ has upward finite energy: for any bond e and any t such that $\mathbf {P}(\tau _e>t)>0$, we have

  $$\begin{aligned} \mathbf {P}(\tau _e>t\mid \{\tau _f:f\ne e\}) >0 \quad \text {a.s.}; \end{aligned}$$

• (vi) the limit shape $\mathcal {B}$ is bounded (equivalently, $\mu$ is strictly positive except at the origin.)

Thanks to (iv), the union of all geodesics from a fixed site x to sites $y\in \mathbb {Z}^2$ is a tree, and we denote it $\mathcal {T}_x=\mathcal {T}_x(\tau )$. By [7], $\mathcal {T}_x$ contains at least 4 semi-infinite geodesics, and Brito and Hoffman [3] give an example in which there are only 4 geodesics, and the direction for each corresponds to an entire closed quadrant of the lattice.

To describe the directions in which semi-infinite geodesics may exist, we introduce some terminology. A facet of $\mathcal {B}$ is a maximal closed line segment F of positive length contained in $\partial \mathcal {B}$; the unique linear functional equal to 1 on F is denoted $\rho _F$. For each angle from 0 there corresponds a unique point of $\partial \mathcal {B}$ in the ray from 0 at that angle; a facet thus corresponds to a sector of angles, or of unit vectors. We say a point $v\in \partial \mathcal {B}$ is of type i ($i=0,1,2$) if v is an endpoint of i facets. We may divide points of $\partial \mathcal {B}$ (or equivalently, all angles) into 6 classes:

• (1) exposed points of differentiability, that is, exposed points of $\partial \mathcal {B}$ where $\partial \mathcal {B}$ is differentiable, necessarily type 0;

• (2) facet endpoints of differentiability, or equivalently, type-1 points where $\partial \mathcal {B}$ is differentiable;

• (3) facet interior points, necessarily type-0;

• (4) half rounded corners, that is, type-1 points where $\partial \mathcal {B}$ is not differentiable;

• (5) fully rounded corners, that is, type-0 points where $\partial \mathcal {B}$ is not differentiable;

• (6) true corners, meaning type-2 points.

Associated to any semi-infinite geodesic $\varGamma =\{x_0,x_1,\dots \}$ is its Busemann function $B_\varGamma :\mathbb {Z}^2\times \mathbb {Z}^2\rightarrow \mathbb {R}$ given by

$$\begin{aligned} B_\varGamma (x,y) = \lim _{n\rightarrow \infty } (T(x,x_n) - T(y,x_n)). \end{aligned}$$

From [1, Theorems 2.5 and 2.6], we know the following, under Assumptions A1 and A2. Almost surely, there exists for any semi-infinite geodesic $\varGamma$ a linear functional $\rho _\varGamma$ on $\mathbb {R}^2$ with the property that $B_\varGamma$ is linear to $\rho _\varGamma$, that is,

$$\begin{aligned} \lim _{|x|\rightarrow \infty } \frac{1}{|x|}\left| B_\varGamma (0,x) - \rho _\varGamma (x) \right| = 0. \end{aligned}$$

Still from [1], the set $\{\rho _\varGamma =1\}$ is always a supporting line of $\mathcal {B}$, so its intersection with $\partial \mathcal {B}$ is either an exposed point v or a facet F, and then $\text {Dir}(\varGamma )$ is equal to $\{v\}$ or contained in F (modulo normalizing to unit vectors.) Thus $\text {Dir}(\varGamma )$ determines $\rho _\varGamma$, unless $\text {Dir}(\varGamma )$ consists of only a corner of some type. Furthermore, there is a closed set $\mathcal {C}_*$ of linear functionals such that the set of functionals $\rho _\varGamma$ which appear for some $\varGamma$ is almost surely equal to $\mathcal {C}_*$. If $v\in \partial \mathcal {B}$ is not a corner, there is a $\rho$ such that $\{\rho =1\}$ is the unique tangent line to $\partial \mathcal {B}$ at v, and we have $\rho \in \mathcal {C}_*$.

In [1], Ahlberg and Hoffman define a random coalescing geodesic (or RC geodesic), which is, in loose terms, a mapping which selects measurably for each $\tau$ a semi-infinite geodesic $\varGamma _0=\varGamma _0(\tau )$ in $\mathcal {T}_0(\tau )$, in such a way that when the mapping is applied via translation to obtain $\varGamma _x\in \mathcal {T}_x$, $\varGamma _0$ and $\varGamma _x$ coalesce a.s. for all x. The following statements are valid under Assumptions A1 and A2: they are part of, or immediate consequences of, results of Ahlberg and Hoffman [1, Theorems 12.1 and 12.2], strengthening earlier results from [7] and [4].

• (I) For each exposed point of differentiability $v\in \partial \mathcal {B}$, there is a.s. a unique RC geodesic $\varGamma$ with $\text {Dir}(\varGamma ) = \{v/|v|\}$.

• (II) For each half rounded corner $v\in \partial \mathcal {B}$, there is a.s. at least one RC geodesic $\varGamma$ with $\text {Dir}(\varGamma ) = \{v/|v|\}$; for one such $\varGamma$ the linear functional $\rho _\varGamma$ corresponds to a limit of supporting lines taken from the non-facet side of v. This uses the fact that $\mathcal {C}_*$ is closed.

• (III) For each fully rounded corner $v\in \partial \mathcal {B}$, there are a.s. at least two RC geodesics $\varGamma$ with $\text {Dir}(\varGamma ) = \{v/|v|\}$, with distinct linear functionals $\rho _\varGamma$ corresponding to limits of supporting lines from each side of v.

• (IV) Given a facet F with corresponding sector $S_F$ of unit vectors, there is a.s. a unique RC geodesic $\varGamma$ with $\text {Dir}(\varGamma )\subset S_F$ and $\rho _\varGamma =\rho _F$. For any other RC geodesic $\varGamma$ with $\text {Dir}(\varGamma )\cap S_F\ne \emptyset$, this intersection is a single endpoint of $S_F$ which must be a corner.

But relatively little has been proved about geodesics, or RC geodesics, in the directions of true corners (where several supporting lines coexist), for instance when the limit shape is a polygon, see e.g. the discussion in Sect. 3.1 of [5]. One may ask, must every true-corner direction be in $\text {Dir}(\varGamma )$ for some geodesic $\varGamma$? Equivalently, must the convex hull of

$$\begin{aligned} \mathcal {V}_\mathrm{geo} := \{v\in \partial \mathcal {B}: v/|v| \in \text {Dir}(\varGamma ) \text { for some semi-infinite geodesic } \varGamma \} \end{aligned}$$

be all of $\mathcal {B}$? Further, we can consider the nonuniqueness set

$$\begin{aligned} \mathcal {N}:= \big \{ u\in S^1: \text { there exist multiple semi-infinite geodesics } \varGamma \text { with } \text {Dir}(\varGamma ) = \{u\} \big \}. \end{aligned}$$

For each fully rounded corner v we have $\mathbf {P}(v\in \mathcal {N})=1$. For each non-corner $v\in \partial \mathcal {B}$ we have $\mathbf {P}(v\in \mathcal {N})=0$, but in the case of $\mathcal {B}$ with no corners this does not mean $\mathcal {N}$ is empty. If every point of $\partial \mathcal {B}$ is an exposed point of differentiability then there is at least one geodesic in every direction; the union of all semi-infinite geodesics from 0 is therefore a tree with infinitely many branches, and each branching produces a point of $\mathcal {N}$, so $\mathcal {N}$ is infinite a.s. In the example of Brito and Hoffman [3], the limit shape is a diamond with true corners on the axes, and for each of these corners v there is a.s. no geodesic $\varGamma$ with $\text {Dir}(\varGamma )= \{v/|v|\}$, so $\mathbf {P}(v\in \mathcal {N})=0$. This suggests the question, must $\mathbf {P}(v\in \mathcal {N})=0$ for true corners?

Our primary result is an example of FPP process, which we call fast diagonals FPP, in which some true corners have no geodesic, and others have multiple geodesics a.s. This means in particular that the convex hull of $\mathcal {V}_\mathrm{geo}$ is not all of $\mathcal {B}$.

Theorem 1

The fast diagonals FPP process (defined in Sect. 3.2) satisfies Assumptions A1-A2, and has the following properties:

• (i) The limit shape is an octagon, with corners on the axes and main diagonals.

• (ii) Almost surely, every semi-infinite geodesic $\varGamma$ is directed in an axis direction (that is, $\text {Dir}(\varGamma )$ consists of a single axis direction.)

• (iii) Almost surely, for each axis direction there exist at least two semi-infinite geodesics directed in that direction.

We first introduce a simpler example in Sect. 2, which does not satisfy Assumption A2 (in particular (iv) and (v)), but encapsulates the key ideas of our construction. The remaining main part of the paper is devoted to modifying this example in order to satisfy Assumption A2, which brings many complications, see Sect. 3.

In Theorem 1 the shape is an octagon, and therefore [7] tells that there must therefore be at least eight geodesics, one for each flat edge of the shape. In our example, there are no geodesics associated to the supporting lines that only touch the shape at the diagonal corners, and the geodesics associated to the flat pieces are asymptotically directed along the axes. However, questions remains regarding the geodesics directed along the axis—for example, are there only two geodesics in each axis direction? Put differently, are there geodesics associated to supporting lines that intersect the shape only at the corners on the axes? Our guess is that, in our example, there are indeed a.s. only two geodesics in the direction of the axis, but the question remains as to whether it is possible to build a model with more than two geodesics in a corner direction.

Our result can perhaps be adapted to produce more general polygons, with polygon vertex directions alternating between those having two or more geodesics and those having none, and with no other directions with geodesics. In higher dimensions, the possibility of analogous examples is unclear.

Remark 1

We make some informal comments here, without full proof, about the linear functionals associated to the geodesics in Theorem 1, and about geodesics versus RC geodesics.

Let us consider the collection $\mathcal {G}_{E,x}$ of geodesics directed eastward from x, and the union $\mathcal {T}_{E,x}$ of all such geodesics. For $x=0$, each such eastward geodesic $\varGamma$ has a height $h(\varGamma )$ of its final point of intersection with the vertical axis. We claim that all semi-infinite geodesics contained in $\mathcal {T}_{E,0}$ are in $\mathcal {G}_{E,0}$, and $h(\varGamma )$ is bounded over $\varGamma \in \mathcal {G}_{E,0}$, a.s. In fact there can be no westward geodesic contained in $\mathcal {T}_{E,0}$ because any eastward geodesic from 0 passing through any point near the negative horizontal axis sufficiently far west from 0 must cross a northward or southward geodesic on its way back eastward, contradicting uniqueness of point-to-point geodesics (i.e. Assumption A2(iv).) Regarding northward geodesics contained in $\mathcal {T}_{E,0}$, they are ruled out when we show in the proof of (ii) in Sect. 3.4 that there is a.s. a random R such that, roughly speaking, no eastward geodesic “goes approximately northward for a distance greater than R before turning eastward,” and similarly for southward in place of northward. This also shows the boundedness of $h(\varGamma )$.

Now any limit of geodesics in $\mathcal {G}_{E,0}$ must be contained in $\mathcal {T}_{E,0}$, and it follows from our claim that any such limit is in $\mathcal {G}_{E,0}$.

It follows that among all eastward geodesics $\varGamma$ in $\mathcal {G}_{E,0}$ with a given value of $h(\varGamma )$, there is a leftmost one, where “leftmost” is defined in terms of the path $\varGamma$ in the right half plane after the point $(0,h(\varGamma ))$. Hence boundedness of h shows there is a leftmost geodesic $\varGamma _L$ overall in $\mathcal {G}_{E,0}$. It is then straightforward to show that $\rho _{\varGamma _L}$ must be the linear functional equal to 1 on the side of $\mathcal {B}$ connecting the positive horizontal axis to the main diagonal. By [1, Theorem 2.6], $\varGamma _L$ is a.s. the unique geodesic with corresponding linear functional $\rho _{\varGamma _L}$, so by [1, Theorem 12.1], $\varGamma _L$, viewed now as a function of the configuration $\tau$ and initial point x, must be an RC geodesic.

Similar considerations apply symmetrically to other directions and to rightmost geodesics. Therefore we can replace “geodesics” with “RC geodesics” in Theorem 1(iii).

2 Simple Example: Diagonal Highways Only

For this section we consider the lattice $\mathbb {L}$ with site set $\mathbb {Z}^2$, with the set of bonds $\mathcal {E}= \{ (x,y) ; \Vert x-y \Vert _{\infty } =1 \}$, which adds diagonal bonds to the usual square lattice. We frequently identify bonds and path steps by map directions: either SW/NE or SE/NW for diagonal bonds, and N, NE, etc. for steps. By axis directions we mean horizontal and vertical, or N, E, W, S, depending on the context. For a preceding b in a path $\gamma$, we write $\gamma [a,b]$ for the segment of $\gamma$ from a to b.

We assign all horizontal and vertical bonds passage time 1. (This makes the model in a sense degenerate, which is one of the aspects we modify in Sect. 3.) Let $\tfrac{1}{2}< \theta < 1$ and $(2\theta )^{-1}<\eta <1$. For diagonal bonds, for $k\ge 1$, a highway of class k consists of $2^k-1$ consecutive bonds, all oriented SW/NE or all SE/NW. The collection of all highways of all classes is denoted $\mathbb {H}$, and a highway configuration, denoted $\omega$, is an element of $\{0,1\}^{\mathbb {H}}$. When a coordinate is 1 in $\omega$ we say the corresponding highway is present in $\omega$. To obtain a random highway configuration, for each of the two orientations we let southernmost points of class-k highways occur at each $x\in \mathbb {Z}^2$ independently with probability $(\theta /2)^k$, for each $k\ge 1$. Every diagonal bond is a highway of class 0. For each diagonal bond e we have

$$\begin{aligned} \mathbf {P}(e \text { is in a present class-}k \text { highway}) = 1 - \left( 1 - \frac{\theta ^k}{2^k} \right) ^{2^k-1} \le \theta ^k, \quad k\ge 1, \end{aligned}$$

(1)

so with probability one, e is in only finitely many present highways. Thus for diagonal e we can define $k(e)=\max \{k: e$ is in a present class-k highway$\}$ if this set is nonempty, and $k(e)=0$ otherwise, and then define its passage time

$$\begin{aligned} \tau _e = {\left\{ \begin{array}{ll} \sqrt{2}(1+\eta ^{k(e)}) &{}\text {if } k(e)\ge 1;\\ 3 &{}\text {if } k(e)=0. \end{array}\right. } \end{aligned}$$

(2)

For all horizontal and vertical bonds we define $\tau _e=1$. Note that the value 3 ensures non-highway diagonal bonds never appear in geodesics.

Let $A_1,A_2$ denote the positive horizontal and vertical axes, respectively, each including 0. Let

$$\begin{aligned} r_k = \sum _{j= k}^{\infty } \theta ^j = \frac{\theta ^{k}}{1-\theta }, \end{aligned}$$

so that $\mathbf {P}( e$ is in some present highway of class $\ge k)\le r_k$. We fix C and take $k_0$ large enough so

$$\begin{aligned} \eta ^{k_0}<\frac{1}{32},\quad r_{k_0} \le \frac{1}{2}, \quad 0.1 \cdot 2^k(\eta ^{k-1}-\eta ^{k}) > \frac{4C}{r_k} \quad \text {for all } k\ge k_0, \end{aligned}$$

(3)

the last being possible by our choice of $\eta$.

Proposition 1

The stationary FPP process defined as above has the following properties:

• (i) The limit shape is an octagon, with corners on the axes and main diagonals.

• (ii) The only infinite geodesics are vertical and horizontal lines (and the only geodesics starting at the origin are indeed the vertical and horizontal axes).

Proof

Let us first show that $\mathcal {B}$ is an octagon with Euclidean distance 1 in the axis and diagonal directions, and a facet in each of the 8 sectors of angle $\pi /4$ between an axis and a diagonal. As a lower bound for the passage time from (0, 0) to (a, b), we readily have that for $0\le b\le a$ (the other cases being treated symmetrically):

$$\begin{aligned} \tau \big ( (0,0),(a,b) \big ) \ge \sqrt{2} b + (a-b)\, . \end{aligned}$$

For an upper bound, it follows from $\theta >1/2$ that the horizontal (or vertical) distance from the origin to the nearest diagonal highway H connecting the postive horizontal axis to height b is o(b) a.s. (see (6)), so as $b\rightarrow \infty$

$$\begin{aligned} \tau \big ( (0,0),(a,b) \big ) \le (\sqrt{2} +o(1) ) b + (a-b)\, . \end{aligned}$$

This reflects the fact that one route from (0, 0) to (a, b) is to follow the axis horizontally to a diagonal highway H, then follow H to the top or right side of the rectangle $[0,a]\times [0,b]$, then follow that side of the rectangle to (a, b), provided H intersects the rectangle. The linearity of the asymptotic expression $\sqrt{2} b + (a-b)$ means that the limit shape is flat between any diagonal and an adjacent axis, while the asymptotic speed is 1 out any axis or diagonal, so the limit shape $\mathcal {B}$ is an octogon. This proves item (i) and we focus on item (ii).

Step 1: Construction of a “success” event For x in the first quadrant Q, let $\varDelta (x)$ denote the Euclidean distance in the SW direction from x to $A_1\cup A_2$. Let $\widehat{G}_k=\{x\in Q:\varDelta (x) = (2^{k-1}+1)\sqrt{2}\}$, which is a translate of $A_1\cup A_2$. For $j> k$ define three random sets of highways:

$$\begin{aligned} \mathcal {G}_{k,j}= & {} \{\text {all present SW/NE highways of class } j \text { intersecting both } A_1\cup A_2 \text { and } \widehat{G}_k\},\\ \mathcal {G}_{k,j}'= & {} \{\text {all present SW/NE highways of class } j \text { crossing } A_1\cup A_2 \text { but not } \widehat{G}_k\},\\ \mathcal {G}_{k,j}''= & {} \{\text {all present SW/NE highways of class } j \text {crossing } \widehat{G}_k \text { but not } A_1\cup A_2\}. \end{aligned}$$

Note that these three sets are independent of each other, and intersections with each along any given line have density at most $\theta ^j$, by (1). We also highlight that $\mathcal {G}_{k,j}$ for $j\le k-1$ is empty, since highways of class $\le k-1$ are too short to connect $A_1\cup A_2$ and $\widehat{G}_k$. Again, using (1), intersections with $\mathcal {G}_{k,k}$ have density (over sites)

$$\begin{aligned} \mathbf {P}(0\in \mathcal {G}_{k,k}) \ge 1 - \left( 1 - \frac{\theta ^k}{2^k} \right) ^{2^k-1} \ge 1 - e^{-\theta ^k/2} \ge \frac{\theta ^{k}}{2}. \end{aligned}$$

(4)

Here $0\in \mathcal {G}_{k,k}$ is a shorthand notation for 0 being in a highway in $\mathcal {G}_{k,k}$, and the last inequality holds provided that k is sufficiently large. Let

$$\begin{aligned} \widehat{H}_{i,k} = \text {the highway intersecting }A_i \text { closest to } 0 \text { among all in } \cup _{j \ge k} \mathcal {G}_{k,j}, \quad i=1,2, \end{aligned}$$

and let $\widehat{U}_k=(\widehat{X}_{1,k},0)$ and $\widehat{V}_k=(0,\widehat{X}_{2,k})$ denote the corresponding intersection points in $A_1$ and $A_2$. Let $\widehat{\varOmega }_k$ denote the open region bounded by $A_1\cup A_2,\widehat{G}_k, \widehat{H}_{1,k}$, and $\widehat{H}_{2,k}$, see Fig. 1.

Fig. 1

Representation of the region $\widehat{\varOmega }_k$, which is enclosed by $A_1,A_2,\widehat{G}_k$ and $\widehat{H}_{1,k},\widehat{H}_{2,k}$. Here, the event $\widehat{I}_k$ is realized

We define the event $\widehat{F}_k = \widehat{I}_k\cap \widehat{M}_k$ (success at stage k) where

• (i) $\widehat{I}_k: \max (\widehat{X}_{1,k},\widehat{X}_{2,k}) \le C/r_k$,    with C from (3);

• (ii) $\widehat{M}_k:$ every SW/NE highway intersecting $\widehat{\varOmega }_k$ is in classes $1,\dots ,k-1$.

Note that a highway intersecting $\widehat{\varOmega }_k$ cannot intersect both $A_1\cup A_2$ and $\widehat{G}_k$, by definition of $\widehat{H}_{i,k}$.

We claim there exists $\lambda >0$ such that

$$\begin{aligned} \mathbf {P}(\widehat{F}_k) \ge \lambda \text { for all } k\ge k_0. \end{aligned}$$

(5)

Let us first prove that $\mathbf {P}(\widehat{I}_k)$ is bounded away from 0. Similarly to (4), we have that $\mathbf {P}\big ( 0\in \bigcup _{j\ge k} \mathcal {G}_{k,j} \big )\ge r_k/3$, so for $i=1,2$, by independence,

$$\begin{aligned} \mathbf {P}(\widehat{X}_{i,k} > C/r_k) \le \exp \left( -C/3 \right) =: \zeta <1, \quad \text {for all } k\ge k_0. \end{aligned}$$

(6)

By independence, we get that $\mathbf {P}(\widehat{I}_k)\ge (1-\zeta )^2$.

We next prove that $\mathbf {P}(\widehat{M}_k\mid \widehat{I}_k)$ is bounded away from 0 for $k\ge k_0$. In fact, by the above-mentioned independence of the three sets of highways, by (1) and (3) we have

$$\begin{aligned} \mathbf {P}(\widehat{M}_k\mid \widehat{I}_k) \ge \min _{x_1,x_2\le C/r_k} \mathbf {P}( \widehat{M}_k\mid \widehat{X}_{1,k}=x_1,\widehat{X}_{2,k}=x_2) \ge \min _{x_1,x_2\le C/r_k} (1-r_k)^{x_1+x_2-1} \ge e^{-2C}. \end{aligned}$$

This completes the proof of (5). A slight modification of this proof shows that for fixed $\ell$, for k sufficiently large we have $\mathbf {P}(\widehat{F}_k\mid \sigma (\widehat{F}_1,\dots ,\widehat{F}_\ell ))>\lambda /2$, and it follows that $\mathbf {P}(\widehat{F}_k\ i.o.)=1$.

Step 2: Properties of geodesics in case of a success We now show that when $\widehat{F}_k$ occurs, for every $x\notin A_1\cup A_2 \cup \widehat{\varOmega }_k$ in the first quadrant, every geodesic $\widehat{\varGamma }_{0x}$ from 0 to x follows $A_1$ from 0 to $\widehat{U}_k$, or $A_2$ from 0 to $\widehat{V}_k$. Since x is in the first quadrant, it is easily seen that any geodesic from 0 to x has only N, NE and E steps. Let $\widehat{p}_x=(r,s)$ be the first site of $\widehat{\varGamma }_{0x}$ not in $A_1\cup A_2 \cup \widehat{\varOmega }_k$. Besides the geodesic $\widehat{\varGamma }_{0x}[0, \widehat{p}_x]$, we define an alternate path $\psi _x$ from 0 to $\widehat{p}_x$ as follows; for this we assume $\widehat{p}_x$ is in the first quadrant on or below the main diagonal, and make the definition symmetric for $\widehat{p}_x$ elsewhere.

• (i) If $\widehat{p}_x \in \widehat{H}_{1,k}$ we let $\psi _x$ follow $A_1$ east from 0 to $\widehat{U}_k$, then NE from $\widehat{U}_k$ to $\widehat{p}_x$ on $\widehat{H}_{1,k}$.

• (ii) If $\widehat{p}_x$ is in the horizontal part of $\widehat{G}_k$ we let $\widehat{U}_k'$ be the intersection of $\widehat{H}_{1,k}$ with the vertical line through $\widehat{p}_x$, and let $\psi _x$ be the path east from 0 to $\widehat{U}_k$, then NE to $\widehat{U}_k'$, then north to $\widehat{p}_x$. (Here we assume $k_0$ is chosen large enough so that $C/r_k < 2^{k-1}$, ensuring that $\widehat{p}_x$ is farther east than $\widehat{U}_k$.)

• (iii) Otherwise $\widehat{p}_x$ is adjacent to $A_1$ and the final step of $\widehat{\varGamma }_{0x}[0,\widehat{p}_x]$ is from some $\widehat{U}_k''\in A_1$ to $\widehat{p}_x$, N or NE. We let $\psi _x$ go east from 0 to $\widehat{U}_k''$, then take one step (N or NE) to $\widehat{p}_x$.

In case (i), the path $\psi _x$ has no N steps, and it is easily seen that any path in $A_1\cup A_2\cup \varOmega _k$ from 0 to $\widehat{p}_x$ containing some N steps will be strictly slower than $\psi _x$, and hence is not a geodesic. Thus every geodesic from 0 to $\widehat{p}_x$ has s NE and $r-s$ E steps. Since success occurs at stage k, any diagonal bonds in $\widehat{\varGamma }_{0x}[0,\widehat{p}_x] \backslash \widehat{H}_{1,k}$ have passage time strictly more than $\sqrt{2}(1+\eta ^{k})$, making $\widehat{\varGamma }_{0x}[0,\widehat{p}_x]$ strictly slower than $\psi _x$, which contradicts the fact that $\widehat{\varGamma }_{0x}[0,\widehat{p}_x]$ is a geodesic. It follows that we must have $\widehat{\varGamma }_{0x}[0,\widehat{p}_x] = \psi _x$, which means $\widehat{\varGamma }_{0x}$ indeed follows $A_1$ from 0 to $\widehat{U}_k$.

In case (ii), we have $s=2^{k-1}+1$ and $0\le r-s \le \widehat{X}_{1,k}$. Let q be the number of NE steps in $\widehat{\varGamma }_{0x}[0,\widehat{p}_x]$, so it must have $s-q$ N and $r-q$ E steps. Each of the diagonal bonds has passage time at least $\sqrt{2}(1+\eta ^{k-1})$, so its passage time satisfies

$$\begin{aligned} T(\widehat{\varGamma }_{0x}[0,\widehat{p}_x])\ge & {} \sqrt{2}(1+\eta ^{k-1})q + (s-q) + (r-q) \ge \sqrt{2}(1+\eta ^{k-1})q + 2(s-q) \\\ge & {} \sqrt{2}(1+\eta ^{k-1})s. \end{aligned}$$

By contrast, the northward segment of $\psi _x$ has length $\widehat{X}_{1,k}-(r-s)$, so

$$\begin{aligned} T(\psi _x)&\le 2\widehat{X}_{1,k} - (r-s) + \sqrt{2}(1+\eta ^{k})(r-\widehat{X}_{1,k}) \\&\le 2 \widehat{X}_{1,k} + \sqrt{2}(1+\eta ^{k})s \\&\le \sqrt{2}(1+\eta ^{k})s + \frac{2 C}{r_k}\, . \end{aligned}$$

Hence by (3),

$$\begin{aligned} T(\widehat{\varGamma }_{0x}[0,\widehat{p}_x]) - T(\psi _x) \ge \sqrt{2}(\eta ^{k-1}-\eta ^{k})s - \frac{2C}{r_k} = (2^{k-1}+1)\sqrt{2}(\eta ^{k-1}-\eta ^{k}) - \frac{2C}{r_k} > 0. \end{aligned}$$

But this contradicts the fact that $\widehat{\varGamma }_{0x}$ is a geodesic. Thus we cannot have $\widehat{p}_x$ in the horizontal part of $\widehat{G}_k$—and similarly not in the vertical part.

In case (iii), since the unique geodesic between any two points of $A_1$ is a segment of $A_1$, it is straightforward that we must have $\widehat{\varGamma }_{0x}[0,\widehat{p}_x] = \psi _x$. Again, $\widehat{\varGamma }_{0x}$ follows $A_1$ from 0 to $\widehat{U}_k$.

Step 3: Conclusion If $\widehat{\varGamma }$ is any semi-infinite geodesic from 0 which has infinitely many points in the (closed) first quadrant, then for each of the infinitely many k for which $\widehat{F}_k$ occurs, the initial segment of $\widehat{\varGamma }$ must follow an axis from the origin to $\widehat{U}_k$ or $\widehat{V}_k$. But since $\widehat{X}_{1,k},\widehat{X}_{2,k} \rightarrow \infty$, this means $\widehat{\varGamma }$ itself must be one of these axes. It follows that all horizontal and vertical lines are semi-infinite geodesics, and no other paths. $\square$

3 Modification for Square Lattice, Finite Energy, and Unique Geodesics

The preceding simpler example does not satisfy A2 (iv) or (v), and it does not allow the use of results known only for the usual square lattice. The first difficulty is to adapt our construction of Sect. 2 so that it does not have diagonal bonds: we remove the diagonal bonds, and we replace diagonal highways with zigzag highways (alternating horizontal and vertical steps) as done in [6]. Then, in order to verify the upward finite energy, we need to introduce horizontal/vertical highways, and make highways of class k not have a fixed length. In order to ensure the unique geodesics condition, we add auxiliary randomization. All together, this adds significant complications. Primarily, since the graph is planar, there is sharing of bonds between, for example, horizontal and zigzag highways where they cross. Since the passage times are different in the two types of highways, each shared bond slows or speeds the total passage time along at least one of the highways, compared to what it would be without the other highway. We must ensure that the number of such crossings is not a primary determinant of which paths are geodesics.

Once we have properly define a passage time configuration (the fast diagonals FPP), our strategy will be similar to that of the simple example of Sect. 2: we will define a “success” event, and show that when a success occurs geodesics approximately follow an axis for a long distance, at least until they reach a very fast zigzag highway.

3.1 Definition of the Fast Diagonals FPP Process

We now select parameters $\eta ,\widetilde{\eta },\theta ,\widetilde{\theta },\mu$: $\theta ^k$ (resp. $\widetilde{\theta }^k$) will roughly correspond to the densities of zigzag (resp. horizontal/vertical) highways of class k, defined below, and $\eta ^k$ (resp. $\widetilde{\eta }^k$) will roughly correspond to the slowdown of a zigzag (resp. horizontal/vertical) highway—that is the higher the class, the faster the highway. We will choose the parameters so that the horizontal/vertical highways are not too infrequent relative to zigzag ones ($\widetilde{\theta }^{c_\theta } > \theta$ for a certain power $c_\theta <1$) and are less slowed down ($\widetilde{\eta } <\eta$) than zigzag ones. Loosely speaking we want the passage times to be much more affected by the zigzag highways encountered than by the horizontal/vertical ones, but fast zigzag highways have to be easily reachable by nearby horizontal/vertical highways, so the choice of parameters must be precise.

The actual choice of the parameters is as follows: we choose $c_{\theta } \in (0.4,0.5)$ and $c_{\widetilde{\theta }} ,\delta >0$ to verify

$$\begin{aligned} \theta =2^{-c_\theta },\quad \widetilde{\theta }= 2^{-c_{\widetilde{\theta }}}, \quad \theta ^{c_\theta c_{\widetilde{\theta }}/(1-c_\theta (c_{\widetilde{\theta }}-4\delta ))}< \eta< \min \Big (\frac{7}{8},\theta ^{2/3} \Big ),\quad \widetilde{\eta }< \min \Big ( \frac{1}{2\theta }, \eta /2\Big ) , \end{aligned}$$

(7)

and

$$\begin{aligned} \theta< \mu < \min (\widetilde{\theta }^{c_\theta },\eta ,(\theta \eta )^{1-c_\theta (c_{\widetilde{\theta }}-4\delta )}\theta ^{-4c_\theta \delta }). \end{aligned}$$

(8)

To see that this choice of parameters is possible, notice that $c_\theta /(1-c_\theta )>2/3$ and $\theta ^{c_\theta /(1-c_\theta )} < 7/8$ so we can choose $0<4\delta<c_{\widetilde{\theta }}<1$ such that $c_\theta c_{\widetilde{\theta }}/(1-c_\theta (c_{\widetilde{\theta }}-4\delta ))>2/3$ and $\theta ^{c_\theta c_{\widetilde{\theta }}/(1-c_\theta (c_{\widetilde{\theta }}-4\delta ))} < 7/8$. Note that since $c_\theta c_{\widetilde{\theta }}<0.5$, the third condition in (7) guarantees $\eta >\theta$; since $c_\theta <0.5$ this also means

$$\begin{aligned} 2\eta \theta>2\theta ^2>1, \end{aligned}$$

(9)

guaranteeing that one can make a modification of (3) hold also here:

$$\begin{aligned} 0.1 \cdot 2^k(\eta ^{k-1}-\eta ^{k}) > \frac{4C}{r_k} + 0.2 \quad \text {for all } k\ge k_0 \end{aligned}$$

(10)

by choosing $k_0$ large enough. Further, the first inequality in that third condition in (7) is equivalent to $\theta < (\theta \eta )^{1-c_\theta (c_{\widetilde{\theta }}-4\delta )}\theta ^{-4c_\theta \delta }$. Together these show $\mu$ can be chosen to satisfy (8).

Highways and types of bonds A zigzag highway is a set of (adjacent) bonds in any finite path which either (i) alternates between N and E steps, starting with either, called a SW/NE highway, or (ii) alternates between N and W steps, starting with either, called a SE/NW highway. If the first step in the path is N, we say the highway is V-start; if the first step is W or E we say it is H-start. A SW/NE highway is called upper if it is above the main diagonal, and lower if it is below, and analogously for SE/NW highways. Note a SW/NE highway is not oriented toward SW or NE, it is only a set of bonds, and similarly for SE/NW. The length |H| of a highway H is the number of bonds it contains. To each zigzag highway H we associate a random variable $\mathcal {U}_H$ uniformly distributed in [0, 1] and independent from highway to highway.

For each $k\ge 1$ we construct a random configuration $\omega ^{(k)}$ of zigzag highways of class k: these highways can have any length $1,\dots ,2^{k+3}$. Formally we can view $\omega ^{(k)}$ as an element of $\{0,1\}^{\mathbb {H}_k}$, where $\mathbb {H}_k$ is the set of all possible class-k zigzag highways; when a coordinate is 1 in $\omega ^{(k)}$ we say the corresponding highway is present in $\omega ^{(k)}$. To specify the distribution, for each length $j\le 2^{k+3}$ and each $x\in \mathbb {Z}^2$, a SW-most endpoint of a present length-j H-start SW/NE highway of class k occurs at x with probability $\theta ^k/2^{2k+4}$, independently over sites x and classes k, with the same for V-start, and similarly for SE/NW highways. We write $\omega =(\omega ^{(1)},\omega ^{(2)},\dots )$ for the configuration of zigzag highways of all classes. Note that due to independence, for $k< l$, a given zigzag highway (of length at most $2^{k+3}$) may be present when viewed as a class-k highway, and either present or not present when viewed as a class-l highway, and vice versa. Formally, then, a present highway in a configuration $\omega$ is an ordered pair (H, k), with k specifying a class in which H is present, but we simply refer to H when confusion is unlikely.

A horizontal highway of length j is a collection of j consecutive horizontal bonds, and similarly for a vertical highway. Highways of both these types are called HV highways. For each $k\ge 1$ we construct a configuration $\widetilde{\omega }^{(k)}$ of HV highways of class k: these highways can have any length $1,\dots ,2^k$, and for each length $j\le 2^k$ and each $x\in \mathbb {Z}^2$, a leftmost endpoint of a present length-j horizontal highway of class k occurs at x with probability $\widetilde{\theta }^k/2^{2k}$, independently over sites x, and similarly for vertical highways. We write $\widetilde{\omega }= (\widetilde{\omega }^{(1)},\widetilde{\omega }^{(2)},\dots )$ for the configuration of HV highways of all classes.

We now combine the classes of zigzag highways and “thin” them into a single configuration by deletions—we stress that following our definitions, each site is a.s. in only finitely many highways. We do the thinning in two stages, first removing those which are too close to certain other zigzag highways, then those which are crossed by a HV highway with sufficiently high class.

Specifically, for stage-1 deletions we define a linear ordering (a ranking) of the SW/NE highways present in $\omega$, as follows. Highway $(H',k)$ ranks above highway (H, l) if one of the following holds: (i) $k>l$; (ii) $k=l$ and $|H'|>|H|$; (iii) $k=l$, $|H'|=|H|$, and $\mathcal {U}_{H'}>\mathcal {U}_H$. Let $d_1(A,B)$ denote the $\ell ^1$ distance between the sets A and B of sites or bonds. We then delete any SW/NE highway (H, k) from any $\omega ^{(k)}$ if there exists another present SW/NE highway $(H',l)$, with $d_1(H,H')\le 22$ which ranks higher than (H, k). We then do the same for SE/NW highways. The configuration of highways that remain in some $\omega ^{(k)}$ after stage-1 deletions is denoted $\omega ^\mathrm{zig,thin,1}$. Here the condition $d_1(H,H')\le 22$ is chosen to follow from $d_1(H,H')<3/(1-\eta )-1$; we have chosen $\eta <7/8$ in (7) so the value 22 works.

For stage-2 deletions, we let $\zeta = \delta /(c_{\widetilde{\theta }}-\delta )$, and for each $m\ge 1$ we delete from $\omega ^\mathrm{zig,thin,1}$ each zigzag highway of class m which shares a bond with an HV highway of class $(1+\zeta )m/c_{\widetilde{\theta }}$ or more (as is always the case when such highways intersect, unless the intersection consists of a single endpoint of one of the highways.) The configuration of highways that remain in some $\omega ^{(k)}$ after both stage-1 and stage-2 deletions is denoted $\omega ^\mathrm{zig,thin,2}$. For a given zigzag highway (H, m) in $\omega ^\mathrm{zig,thin,1}$, for each bond e of H there are at most $2^\ell$ possible lengths and $2^\ell$ possible endpoint locations for a class-$\ell$ HV highway containing e, so the probability (H, m) is deleted in stage 2 is at most

$$\begin{aligned} 2^{m+3} \sum _{\ell \ge (1+\zeta )m/c_{\widetilde{\theta }}} 2^{2\ell }\cdot \frac{\widetilde{\theta }^\ell }{2^{2\ell }} = \frac{8}{1-\widetilde{\theta }}\ 2^{-\zeta m}. \end{aligned}$$

(11)

Following stage-2 deletions we make one further modification, which we call stage-3 trimming. Suppose $(H,k),(H',l)$ are zigzag highways of opposite orientation (SW/NE vs SE/NW) in $\omega ^\mathrm{zig,thin,2}$, and x is an endpoint of H. If $d_1(x,H')\le 1$, then we delete from H the 4 final bonds of H, ending at x, creating a shortened highway $\widehat{H}$. (Formally this means we delete (H, k) from $\omega ^\mathrm{zig,thin,2}$ and make $(\widehat{H},k)$ present, if it isn’t already.) The resulting configuration is denoted $\omega ^\mathrm{zig,thin}$. This ensures that for any present SW/NE zigzag highway H and SE/NW zigzag highway $H'$, either H and $H'$ fully cross (meaning they intersect, and there are at least 2 bonds of each highway on either side of the intersection bond) or they satisfy $d_1(H,H')\ge 2$.

This construction creates several types of bonds, which will have different definitions for their passage times. A bond e which is in no highway in $\omega ^\mathrm{zig,thin}$ but which has at least one endpoint in some highway in $\omega ^\mathrm{zig,thin}$ is called a boundary bond. A bond e in any highway in $\omega ^\mathrm{zig,thin}$ is called a zigzag bond. A HV bond is a bond in some HV highway in some $\widetilde{\omega }^{(k)}$. An HV-only bond is an HV bond which is not a zigzag bond. A backroad bond is a bond which is not a zigzag bond, HV-only bond, or boundary bond.

Moreover, there are special types of boundary and zigzag bonds that arise when a SW/NE zigzag highway crosses a SE/NW one, so we need the following definitions for bonds in $\omega ^\mathrm{zig,thin}$. For zigzag bonds, we distinguish:

• (i) The first and last bonds (or sites) of any zigzag highway are called terminal bonds (or terminal sites.) A bond which is by itself a length-1 highway is called a doubly terminal bond; other terminal bonds are singly terminal bonds. Bonds which are not the first or last bond of a specified path are called interior bonds.

• (ii) An adjacent pair of zigzag bonds in the same direction (both N/S or both E/W, which are necessarily from different highways, one SW/NE and one SE/NW) is called a meeting pair, and each bond in the pair is a meeting zigzag bond.

• (iii) A zigzag bond for which both endpoints are meeting-pair midpoints is called an intersection zigzag bond. Equivalently, when a SW/NE highway intersects a SE/NW one, the bond forming the intersection is an intersection zigzag bond.

• (v) A zigzag bond which is not a meeting, intersection, or terminal zigzag bond is called a normal zigzag bond.

For boundary bonds, we distinguish the following:

• (vi) A boundary bond is called a semislow boundary bond if either (a) it is adjacent to two meeting bonds (and is necessarily parallel to the intersection bond, separated by distance 1), called an entry/exit bond, or (b) it is adjacent to an intersection bond.

• (vi) A boundary bond e is called a skimming boundary bond if one endpoint is a terminal site of a zigzag highway, and the corresponding terminal bond is perpendicular to e.

• (vii) A boundary bond which is not a semislow or skimming boundary bond is called a normal boundary bond.

These special type of bonds are represented in Fig. 2.

Fig. 2

Different types of bonds near a crossing of two zigzag highways, and their compensated core passage times, see (14)

Definition of the passage times. For each edge e we associate its zigzag class

$$\begin{aligned} k(e)= {\left\{ \begin{array}{ll} \max \{k: e \text { is in a class-}k \text { zigzag highway in }\omega ^\mathrm{zig, thin} \} &{}\text {if this set is nonempty}, \\ 0, &{}\text {otherwise}, \end{array}\right. } \end{aligned}$$

and its HV class

$$\begin{aligned} \widetilde{k}(e)= {\left\{ \begin{array}{ll} \max \{k: e \text { is in a class-}k \text { HV highway in }\widetilde{\omega }^{(k)} \} &{}\text {if this set is nonempty}, \\ 0, &{}\text {otherwise}. \end{array}\right. } \end{aligned}$$

We then define a bond e to be slow if

$$\begin{aligned} \xi _e' \le 4^{-k(e)\vee \widetilde{k}(e)}, \end{aligned}$$

(12)

where $\xi _e'$ is uniform in [0, 1], independent from bond to bond. Slow bonds exist only to ensure that upward finite energy holds.

We next define the raw core passage time $\alpha _e=\alpha _e(\widetilde{\omega },\omega ^\mathrm{zig,thin})$ of each bond e, mimicking ideas of the simple example of Sect. 2. For non-slow e we set

$$\begin{aligned} \alpha _e = {\left\{ \begin{array}{ll} 0.7 &{}\text {if } e \text { is a zigzag bond}\\ 0.9 &{}\text {if } e \text { is an HV-only bond}\\ 1 &{}\text {if } e \text { is a backroad bond or non-HV boundary bond}, \end{array}\right. } \end{aligned}$$

(13)

and for slow e, we set $\alpha _e=1.2$. Then we define the compensated core passage time $\alpha _e^*=\alpha _e^*(\omega ,\omega ^\mathrm{zig,thin})$ for non-slow e by

$$\begin{aligned} \alpha _e^* = {\left\{ \begin{array}{ll} 0.5 &{}\text {if } e \text { is an intersection zigzag bond}\\ 0.7 &{}\text {if } e \text { is a normal zigzag bond}\\ 0.8 &{}\text {if } e \text { is a meeting bond, or a singly terminal zigzag bond}\\ 0.9 &{}\text {if } e \text { is a doubly terminal zigzag bond, or an HV-only bond which is either }\\ &{}\qquad \text {non-boundary or a skimming boundary bond} \\ 1 &{}\text {if } e \text { is a backroad bond, or a normal boundary bond}\\ 1.1 &{}\text {if } e \text { is a semislow boundary bond}, \end{array}\right. } \end{aligned}$$

(14)

and for slow e, we set $\alpha _e^*=1.3$. The term “compensated” refers mainly to the following: when an HV highway crosses a zigzag one, it typically intersects one normal zigzag bond and two normal boundary bonds. The sum of the raw core passage times for these 3 bonds is $0.9+0.7+0.9=2.5$, whereas in the absence of the zigzag highway the sum would be $3\times 0.9=2.7$. With the compensated times, the sum is restored to 2.7, and in that sense the HV highway does not “feel” the zigzag highway. The compensation picture is more complicated when the HV highway crosses near the intersection of a SW/NE highway and a SE/NW highway (which necessarily fully cross.) It must be done so that (16) and (17) below hold, whether the HV highway contains intersection bonds, meeting bonds or entry/exit bonds, see Fig. 2.

In a similar sense, a SW/NE highway does not “feel” a crossing by a SE/NW highway.

The idea in the definition of $\alpha _e^*$ is that we compensate for the “too fast” zigzag bonds in an HV highway (0.7 vs 0.9) by extracting a toll of 0.1 for entering or exiting a zigzag highway. If the entry/exit is through a terminal or meeting zigzag bond (as when passing through a meeting block), then the toll is paid by increasing the time of that bond from 0.7 to 0.8. In the meeting case, to avoid increasing the total time along the zigzag highway, the core passage time of the adjacent intersection bond is reduced to 0.5. If the entrance/exit for the zigzag highway is made through any other type of zigzag bond, the toll is paid by increasing the adjacent boundary bond in the path from 0.9 (if it’s an HV bond) to 1. There is an exception in an entry/exit bond, which may be both entrance and exit: the toll for such a bond is 0.2.

Due to the stage-1 deletions, any two parallel zigzag highways $H,H'$ in $\omega ^\mathrm{zig,thin}$ satisfy

$$\begin{aligned} d_1(H,H')\ge 23, \end{aligned}$$

(15)

and as a result, the compensation described by (14) is sufficient for our purposes; without a lower bound like (15), more complicated highway-crossing situations would be possible, producing for example meeting zigzag bonds which are also intersection zigzag bonds.

We thus have the following property: suppose H is an HV highway for which the first and last bonds are HV-only, and $\varGamma$ is a path which starts and ends with non-zigzag bonds. Then

$$\begin{aligned} \sum _{e\in H} \alpha _e^* = 0.9|H|, \qquad \sum _{e\in \varGamma } \alpha _e^* \ge 0.7|\varGamma |. \end{aligned}$$

(16)

End effects may alter this for general HV highways and paths, but it is easily checked that every HV highway H and path $\varGamma$ satisfies

$$\begin{aligned} \Big | \sum _{e\in H} \alpha _e^* - 0.9|H| \Big | \le 0.4, \qquad \sum _{e\in \varGamma } \alpha _e^* \ge 0.7|\varGamma | - 0.2. \end{aligned}$$

(17)

We use another auxiliary randomization to ensure unique geodesics: for each bond e we let $\xi _e$ be uniform in [0, 1], independent from bond to bond (and independent of the $\xi _e'$’s used above). We can now define the full passage times $\tau _e$ (based on the configurations $\omega ^\mathrm{zig,thin}$ and $\widetilde{\omega }$) by

$$\begin{aligned} \tau _e= \alpha _e^* + \sigma _e, \end{aligned}$$

(18)

where $\sigma _e$ (the slowdown) is defined to be $0.1 \xi _e$ if e is a slow bond, and for non-slow e

$$\begin{aligned} \sigma _e = 0.1 \times {\left\{ \begin{array}{ll} \eta ^{k(e)} + \widetilde{\eta }^{k(e)}\xi _e &{}\text {if } e \text { is a zigzag bond,} \\ \widetilde{\eta }^{\widetilde{k}(e)} + \widetilde{\eta }^{\widetilde{k}(e)}\xi _e &{}\text {if } e \text { is an HV-only bond,}\\ \widetilde{\eta }^{\widetilde{k}(e)}\xi _e &{}\text {if } e \text { is either a backroad bond, or a boundary bond which is not HV.} \end{array}\right. } \end{aligned}$$

(19)

Hence, this corresponds to a slowdown of order $\eta ^k$ (per bond) in class-k zigzag highways, and of order $\widetilde{\eta }^{\widetilde{k}}$ (per bond) in class-$\widetilde{k}$ HV-highways. We refer to the resulting stationary FPP process as the fast diagonals FPP process. We stress that the presence of the independent variables $\xi _e$ ensures that Assumption A2(iv) is satisfied, and (since $\sigma _e\le 0.2$ in all cases) the presence of slow bonds ensures the positive finite energy condition A2(v); the rest of A1 and A2 are straightforward.

First observations and notations It is important that since $\eta >\widetilde{\eta }$, passage times along long zigzag highways are much more affected by the class of the highway than are times along HV highways. In fact, by increasing $k_0$ we may assume $(2\widetilde{\eta })^{k_0}<\eta ^{k_0}<1/16$, recalling we chose $\widetilde{\eta }<\eta /2$. Then if H is an HV highway of class $k\ge k_0$ (so of length at most $2^{k+3}$), we have

$$\begin{aligned} 0.1 \sum _{e\in H} (\widetilde{\eta }^{k} + \widetilde{\eta }^{k}\xi _e) \le 1.6 (2\widetilde{\eta })^k < 0.1, \end{aligned}$$

(20)

so the maximum effect on $\sum _{e\in H} \tau _e$ of all the variables involving $\widetilde{\eta }$ is less than 0.1, hence is less than the effect of the $\alpha _e^*$ value for any single bond e.

Henceforth we consider only $k\ge k_0$, n setting the scale of $\widehat{\varOmega }_k$. Let $r_k = \sum _{j=k}^\infty \theta ^j$ and $\widetilde{r}_k = \sum _{j=k}^\infty \widetilde{\theta }^j$. Define $q_k = \log _2(2C/r_k) = c_\theta k+b$ where b is a constant.

The following subsections prove Theorem 1. The strategy is similar to that of Sect. 2: we first construct in Sect. 3.2 an event $F_k$ that a.s. occurs for a positive fraction of all k’s, and then show in Sect. 3.3 that when $F_k$ occurs geodesics have to stay near the axis. We conclude the proof of Theorem 1 in Sect. 3.4.

3.2 Construction of a “Success” Event

Analogously to Sect. 2, we construct a random region $\varOmega _k$ (which is an enlarged random version of $\widehat{\varOmega }_k$), and a deterministic region $\varTheta _k$ which may contain $\varOmega _k$, as follows.

As before we write $A_1,A_2$ for the positive horizontal and vertical axes, Q for the first quadrant, and now also $A_3, A_4$ for the negative horizontal and vertical axes, respectively. We write $G_k^1$ for the set $\{x\in Q:\varDelta (x) = 2^k\sqrt{2}\}$ (formerly denoted $\widehat{G}_k$) and $\widetilde{G}_k^1$ for $\{x\in Q:\varDelta (x) = (2^k+4)\sqrt{2}\}$; successively rotating the lattice by 90$^\circ$ yields corresponding sets $G_k^2,G_k^3,G_k^4$ and $\widetilde{G}_k^2,\widetilde{G}_k^3,\widetilde{G}_k^4$ in the second, third and fourth quadrants, respectively. Let $H_{NE,L,k}$ and $H_{NE,U,k}$ be the lower and upper zigzag highways in $\omega ^\mathrm{zig,thin,2}$ of class k or more, intersecting both $\widetilde{G}_k^1$ and $\widetilde{G}_k^3$, which intersect $A_1$ and $A_2$, respectively, closest to 0. Let $U_k^{NE} = (X_{1,k}^{NE},0)$ be the leftmost point of $A_1\cap H_{NE,L,k}$, and $V_k^{NE}=(0,X_{2,k}^{NE})$ the lowest point of $A_2\cap H_{NE,U,k}$. Rotating the lattice 90$^\circ$ yields analogous highways $H_{NW,L,k}$ and $H_{NW,U,k}$ each intersecting $\widetilde{G}_k^2$ and $\widetilde{G}_k^4$, and intersections points $U_k^{NW} = (X_{1,k}^{NW},0)$ and $V_k^{NW}=(0,X_{2,k}^{NW})$ with axes $A_3$ and $A_2$, respectively. Here we have used $\widetilde{G}_k^i$ and not $G_k^i$ so that stage-3 trimming does not prevent $H_{*,\cdot ,k}$ from reaching appropriate $G_k^i$.

Let $\ell _{1,k}$ and $\ell _{3,k}$ be the vertical lines $\{\pm 2C/r_k\}\times \mathbb {R}$ crossing $A_1$ and $A_3$ respectively, and $\ell _{2,k}$ and $\ell _{4,k}$ the horizontal lines $\mathbb {R}\times \{\pm 2C/r_k\}$ crossing $A_2$ and $A_4$. Let $J_{N,k}$ (and $J_{S,k}$, respectively) denote the lowest (and highest) horizontal highway above (and below) the horizontal axis intersecting both $\ell _{1,k}$ and $\ell _{3,k}$. Analogously, let $J_{E,k}$ (and $J_{W,k}$) be the leftmost (rightmost) vertical highway to the right (left) of the vertical axis intersecting both $\ell _{2,k}$ and $\ell _{4,k}$. Let $(Y_{E,k},0)$ be the intersection of $J_{E,k}$ with $A_1$, and analogously for $(0,Y_{N,k}),(Y_{W,k},0)$ and $(0,Y_{S,k})$ in $A_2,A_3$, and $A_4$.

Let $\varOmega _k^{NE}$ be the open region bounded by $H_{NE,L,k},H_{NE,U,k},G_k^1$, and $G_k^3$, and let $\varOmega _k^{NW}$ be the open region bounded by $H_{NW,L,k},H_{NW,U,k},G_k^2$, and $G_k^4$. Then let $\varOmega _k=\varOmega _k^{NW}\cup \varOmega _k^{NE}$ (an X-shaped region), see Fig. 3.

Let $h_{NE,L,k}$ and $h_{NE,U,k}$ denote the SW/NE diagonal lines through $(C/r_k,0)$ and $(0,C/r_k)$ respectively, and let $h_{NW,L,k}$ and let $h_{NW,U,k}$ denote the SE/NW diagonal lines through $(-C/r_k,0)$ and $(0,C/r_k)$, respectively. Let $\varTheta _k^{NE}$ denote the closed region bounded by $h_{NE,L,k},h_{NE,U,k},G_k^1$ and $G_k^3$, and $\varTheta _k^{NW}$ the closed region bounded by $h_{NW,L,k},h_{NW,U,k},G_k^2$ and $G_k^4$. Then let $\varTheta _k=\varTheta _k^{NW}\cup \varTheta _k^{NE}$. In the event of interest to us, the nonrandom region $\varTheta _k$ will contain the random region $\varOmega _k$.

Fig. 3

Representation of the different regions of interest (the picture focuses on the upper-right quadrant, and the scales are not respected): $\varOmega _k^{NE}$ is the shaded region enclosed by $H_{NE,U,k}, H_{NE,L,k}$ and $G_k^i$ ($i=1,3$); $\varTheta _k^{NE}$ is the region enclosed by $h_{NE,U,k}, h_{NE,L,k}$ and $G_k^i$ ($i=1,3$). The construction of $\varOmega _k^{NW}$ and $\varTheta _k^{NW}$ is symmetric by rotation of 90$^\circ$

We now construct an event $F_k$, which we will show occurs for a positive fraction of all k, a.s. We show in Sect. 3.3 that $F_k$ ensures that all finite geodesics from 0 to points outside $\varOmega _k$ must stay near one of the axes until leaving $\varOmega _k^{NW}\cap \varOmega _k^{NE}$. For $m>c_{\widetilde{\theta }}q_k/(1+\zeta )$ let $R_{k,m}^*$ be the number of class-m zigzag highways in $\omega ^{(m)}$ intersecting $J_{*,k}$ in $\varTheta _k$, for $*=$ N, E, S, W. Here $\zeta$ is from the definition of stage-2 deletions. Note that since the class of $J_{*,k}$ is at least $q_k$, any intersecting highways of class $m\le c_{\widetilde{\theta }}q_k/(1+\zeta )$ are removed in stage-2 deletions, so $R_{k,m}^*$ counts those which might remain (depending on the class of $J_{*,k}$).

Fix $c\in (0,C/2)$ and define the events

$$\begin{aligned} I_k^*:= & {} \Big \{ \, \frac{c}{r_k} \le X_{i,k}^* \le \frac{C}{r_k} \text { for } i=1,2\, \Big \}, \text { for } *= \text { NE, NW}, \qquad I_k = I_k^{NE}\cap I_k^{NW},\\ M_k^{NE}:= & {} \bigg \{ \hbox {every SW/NE highway } H\notin \{H_{NE,L,k},H_{NE,U,k}\} \hbox { in } \omega \hbox { intersecting } \varTheta _k^{NE} \hbox { is in classes } 1,\dots ,k-1\bigg \}\, , \end{aligned}$$

and analogously for $M_k^{NW}$, and let $M_k = M_k^{NE}\cap M_k^{NW}.$ Define also

$$\begin{aligned}&\widetilde{D}_k: |Y_{*,k}| \le \frac{C}{\widetilde{r}_{q_k}} \text { for } *=E,N,W,S.\\&E_{1,k}: \sum _{m>c_{\widetilde{\theta }}q_k/(1+\zeta )} R_{k,m}^*\eta ^m \le c_1(\eta ^3\theta ^{-2})^{c_\theta \delta k} (\mu ^{-1}\eta )^k, \text { for } *=E,N,W,S. \end{aligned}$$

with $c_1$ to be specified and $\delta$ from (7), noting that by the bound on $\eta$ in (7) we have $\eta ^3\theta ^{-2}<1$, and

$$\begin{aligned}&E_{2,k}: \text { there are no slow bonds in any } J_{*,k} (*= \text {N, E, S, W})\\&\quad \text {nor in any } H_{*,\cdot ,k} (*= \text { NE, NW}, \cdot = \text {U, L}). \end{aligned}$$

Finally, we set $F_k = I_k \cap M_k \cap \widetilde{D}_k \cap E_{1,k} \cap E_{2,k}$. Note that when $F_k$ occurs we have $\varOmega _k\subset \varTheta _k$.

Lemma 1

There exists some $\kappa _1$ such that

$$\begin{aligned} \liminf _{n\rightarrow \infty } \frac{1}{n} \sum _{k=1}^n 1_{F_k} \ge \kappa _1 \quad {\mathrm{a.s.}} \end{aligned}$$

(21)

Moreover, letting $n_1(\omega )<n_2(\omega ) <\cdots$ be the indices for which $\omega \in F_k$, we have

$$\begin{aligned} \limsup _{j\rightarrow \infty } \frac{n_{j+1}}{n_{j}} =1 \quad \mathrm{a.s.} \end{aligned}$$

(22)

Proof

In the events $I_k$ and $M_k$, the highways $H_{*,\cdot ,k}$ and associated values $X_{i,k}^*$ are taken from the configuration $\omega ^\mathrm{zig,thin,2}$. Using instead the configuration $\omega ^\mathrm{zig,thin,1}$ yields different events, which we denote $I_k^1$ and $M_k^1$ respectively. Let $F_k^1 = I_k^1 \cap M_k^1 \cap \widetilde{D}_k$ (noting we do not intersect with $E_{1,k}, E_{2,k}$ here). First, we prove the following.

Claim 1

There exists $\kappa _1>0$ such that

$$\begin{aligned} \liminf _{n\rightarrow \infty } \frac{1}{n} \sum _{k=1}^n 1_{F_k^1} \ge \kappa _1 \quad \mathrm{a.s.} \end{aligned}$$

Proof (Proof of Claim 1)

As a first step, we show that

$$\begin{aligned} \inf _{k\ge k_0} \mathbf {P}(I_k^1\cap M_k^1)>0. \end{aligned}$$

(23)

For a lower SW/NE zigzag highway H, let $(x_0(H),0)$ be the intersection point in $A_1$ closest to (0, 0) when one exists, and similarly for an upper SW/NE zigzag highway H let $(0,y_0(H))$ be the intersection point in $A_2$ closest to (0, 0). We call H k-connecting if H intersects both $G_k^1$ and $G_k^3$. The event $I_k^1\cap M_k^1$ contains the event

The parts of $A_k$ for the 4 types of zigzag highways (upper vs lower, SW/NE vs SE/NW) are independent, so to bound the probability of $A_k$ we can consider just one of these parts and take the fourth power of the corresponding probability. In particular, considering lower SW/NE highways H of class $\ell \ge k$ intersecting $\varTheta _k^{NE}$, there are at most $2^{\ell +3}$ possible lengths for H, at most $2^{\ell +3}C/r_k$ possible SW-most points, and the choice of H-start or V-start, so at most $2^{2\ell +7}C/r_k$ possible highways. Also, considering lower SW/NE highways H of class $m\ge k$ which are k-connecting and satisfy $\tfrac{c}{r_k}\le x_0(H)\le \tfrac{C}{r_k}-23$, there are at least $2^{m+1}(C-c)/r_k$ possible lower endpoints, and $2^{m+1}$ possible lengths, for H. Therefore considering only lower highways, and since $c<C/2$ we have

$$\begin{aligned} \mathbf {P}(I_k^1\cap M_k^1)^{1/4} \ge \mathbf {P}(A_k)^{1/4}&\ge \sum _{m\ge k} \frac{2^{2m+2}(C-c)}{r_k}\ \frac{\theta ^m}{2^{2m+4}} \prod _{\ell \ge k} \left( 1 - \frac{\theta ^\ell }{2^{2\ell +4}} \right) ^{2^{2\ell +7}C/r_k} \nonumber \\&\ge \left( \sum _{m\ge k} \frac{C\theta ^m}{8r_k} \right) \exp \left( -\sum _{\ell \ge k}\frac{16C\theta ^\ell }{r_k} \right) \nonumber \\&= \frac{C}{8}e^{-16C}, \end{aligned}$$

(24)

proving (23).

A similar but simpler proof also using a count of highways yields that $\inf _{k\ge k_0} \mathbf {P}(\widetilde{D}_k)>0$, so by independence we have

$$\begin{aligned} \inf _{k\ge k_0} \mathbf {P}(F_k^1)\ge \kappa _0>0 \end{aligned}$$

(25)

for some $\kappa _0$. But Claim 1 is a stronger statement, and we now complete its proof, using (25).

Let $\mathcal {H}_k$ denote the set of all SW/NE highways in $\omega$ which intersect $\varTheta _k^{NE}$, together with all SE/NW highways which intersect $\varTheta _k^{NW}$. Let $\mathcal {F}_k$ denote the $\sigma$-field generated by $\mathcal {H}_k$, and let $\mathcal {C}_k$ denote the largest j such that $\mathcal {H}_k$ contains a highway of class j. For $m\ge k$, class-m SW/NE highways intersecting $\varTheta _k^{NE}$ have at most $(2C/r_k)(2^{m+3}+2^{k+3})$ possible SW-most endpoints, and $2^{m+3}$ possible lengths, and 2 directions for the initial step (V- or H-start), so the number of such highways is bounded by a sum of Bernoulli random variables, each with parameter (success probability) less than 1 / 2 and with total mean at most

$$\begin{aligned} 2^{m+4}\frac{2C}{r_k}(2^{m+3}+2^{k+3})\frac{\theta ^m}{2^{2m+4}} \le \frac{32C\theta ^m}{r_k}. \end{aligned}$$

The same is true for SE/NW highways. Hence for $n\ge 0$ the number of highways of class at least $k+n$ is bounded by a similar sum of Bernoulli variables of total mean at most $32Cr_{k+n}/r_k$. It follows that for any $n\ge 0$,

$$\begin{aligned} \mathbf {P}(\mathcal {C}_k-k \ge n)&\le \mathbf {P}(\text {some highway in } \omega \text { of class } k+n \text { or more intersects } \varTheta _k)\nonumber \\&\le \frac{32Cr_{k+n}}{r_k} = 32C\theta ^n. \end{aligned}$$

(26)

Let $n_0$ be the least integer with $\theta ^{n_0}<c/C$. Define a random sequence of indices $1=K_1<K_2<\dots$ inductively as follows: having defined $K_i$, let $K_{i+1}:=\max \{\mathcal {C}_{K_i} , (K_i+n_0) \} +1$. Here $k\ge K_i+n_0$ ensures $C/r_{K_i} < c/r_k$, and $k>\mathcal {C}_{K_i}$ ensures that $H_{NE,L,k},H_{NE,U,k}$ do not intersect $\varTheta _{K_i}^{NE}$, and likewise for NW in place of NE. For any $j,\ell$, and any $A\in \mathcal {F}_j$, the event $A\cap \{K_i=j,\mathcal {C}_j=\ell \}$ only conditions zigzag highways in $\mathcal {H}_j$, and ensures that no SW/NE (or SE/NW) highways of class $\ge k = \max (j+n_0,\ell )+1$ intersect $\varTheta _j^{NE}$ (or $\varTheta _j^{NW}$, respectively); in particular it ensures that $\widehat{X}_{i,k}^*>C/r_j$ for $*=$ NE, NW. Therefore since $C/r_j < c/r_k$ this event increases the probability of $I_k^1\cap M_k^1$: for such $j,\ell ,k,A$,

$$\begin{aligned} \mathbf {P}\big (I_k^1\cap M_k^1 \mid A\cap \{K_i=j,\mathcal {C}_j=\ell \} \big ) \ge \mathbf {P}( I_k^1\cap M_k^1). \end{aligned}$$

Similarly the bound in (26) is still valid conditionally: for such $j,\ell ,k$,

$$\begin{aligned} \mathbf {P}\big (\mathcal {C}_k-k \ge n \mid A\cap \{K_i=j,\mathcal {C}_j=\ell \} \big ) \le 32C\theta ^n \quad \text {for all } n\ge 0. \end{aligned}$$

(27)

It follows that for some $c_2>0$,

$$\begin{aligned} \limsup _{i\rightarrow \infty } \frac{K_i}{i} \le c_2\quad \mathrm{a.s.} \end{aligned}$$

(28)

On the other hand, it is straightforward that for some $\kappa _2>0$, for all $j<k$ and all $B\in \sigma (\widetilde{D}_1,\dots ,\widetilde{D}_j)$,

$$\begin{aligned} \mathbf {P}(\widetilde{D}_k \mid B ) \ge \kappa _2\mathbf {P}(\widetilde{D}_k) \quad \mathrm{a.s.}, \end{aligned}$$

so by independence of HV highways from zigzag ones, using (25),

$$\begin{aligned} \mathbf {P}\big (F_k^1 \mid A\cap B \cap \{K_i=j,\mathcal {C}_j=\ell \} \big ) \ge \kappa _2\mathbf {P}(F_k^1) \ge \kappa _2\kappa _0. \end{aligned}$$

(29)

Since A, B are arbitrary, it follows that the variables $1_{F_{K_i}}$ dominate an independent Bernoulli sequence with parameter $\kappa _2\kappa _0$, so

$$\begin{aligned} \liminf _{m\rightarrow \infty } \frac{1}{m} \sum _{i=1}^m 1_{F_{K_i}^1} \ge \kappa _2\kappa _0\quad \mathrm{a.s.} \end{aligned}$$

This, combined with (28), proves Claim 1 with $\kappa _1=\kappa _2\kappa _0/c_2$. $\square$

Note that by (27), the variables $K_{i+1}-K_i, i\ge 1$ are dominated by an i.i.d. sequence of the form “constant plus geometric random variable.”

Let us go back to the proof of Lemma 1. Let $B_k$ denote the event that none of the 4 highways $H_{*,\cdot ,k}(\omega ^\mathrm{zig,thin,1})$ are deleted in stage-2 deletions, then we have

$$\begin{aligned} I_k^1 \cap M_k^1 \cap B_k \subset I_k\cap M_k. \end{aligned}$$

(30)

Claim 2

We have

$$\begin{aligned} \sum _k \mathbf {P}(B_k^c\cap I_k^1)< \infty \ ; \quad \sum _k \mathbf {P}(E_{2,k}^c\cap \widetilde{D}_k)< \infty \quad \text { and } \quad \sum _k \mathbf {P}(E_{1,k}^c) < \infty . \end{aligned}$$

Proof (Proof of Claim 2)

Let $Z_{*,\cdot ,k}^H$ denote the class of the zigzag highway $H_{*,\cdot ,k}(\omega ^\mathrm{zig,thin,1})$, for $*=$ NE, NW and $\cdot =$ U, L, and let $Z_{*,k}^J$ denote the class of the HV highway $J_{*,k}$ for $*=$ N, E, W, S. Then, by (11), for $n\ge 0$

$$\begin{aligned} \mathbf {P}\big (B_k^c \mid I_k^1\cap \{Z_{NE,L,k}^H = k+n\} \big ) \le \frac{8}{1-\widetilde{\theta }}\ 2^{-\zeta (k+n)} \le \frac{8}{1-\widetilde{\theta }}\ 2^{-\zeta k}\, . \end{aligned}$$

(31)

Since the upper bound is independent of n, summing over n we get that $\mathbf {P}(B_k^c \cap I_k^1) \le 8 (1-\widetilde{\theta })^{-1} 2^{-\zeta k}$, and the first item of Claim 2 is proven.

Similarly,

$$\begin{aligned} \mathbf {P}\big (E_{2,k}^c \mid \widetilde{D}_k\cap \{Z_{N,k}^J = q_k+n\} \big ) \le 2^{q_k+n+3}4^{-(q_k+n)} \le 8\cdot 2^{-q_k}. \end{aligned}$$

so we get that $\mathbf {P}\big ( E_{2,k}^c \cap \widetilde{D}_k \big ) \le 2^{- q_k +3}$, and the second item of Claim 2 is proven.

For the last item, recall $c_{\widetilde{\theta }}/(1+\zeta ) = c_{\widetilde{\theta }}-\delta$. We have from the upper bound for $\mu$ in (8)

$$\begin{aligned} \sum _{m>c_{\widetilde{\theta }}q_k/(1+\zeta )} \theta ^{m-k-c_\theta \delta m}\eta ^m&\le c_1 (\theta ^{1-c_\theta \delta }\eta )^{(c_\theta (c_{\widetilde{\theta }}-\delta )-1)k}\mu ^k \theta ^{-c_\theta \delta k} (\mu ^{-1}\eta )^k \nonumber \\&\le c_1 (\eta ^3 \theta ^{-2})^{c_\theta \delta k} (\mu ^{-1}\eta )^k, \end{aligned}$$

(32)

so

$$\begin{aligned} \mathbf {P}(E_{1,k}^c) \le 4\sum _{m>c_{\widetilde{\theta }}q_k/(1+\zeta )} \mathbf {P}\left( R_{k,m}^N > \theta ^{m-k-c_\theta \delta m} \right) \, . \end{aligned}$$

Analogously to (26) we have that $\mathbf {E}(R_{k,m}^N) \le c_3\theta ^m /r_k$ and by Markov’s inequality,

$$\begin{aligned} \mathbf {P}(E_{1,k}^c) \le c_4 \sum _{m>c_{\widetilde{\theta }}q_k/(1+\zeta )} \theta ^{c_\theta \delta m} \le c_5\theta ^{c_6k}. \end{aligned}$$

This proves the last item of Claim 2. $\square$

Equation (21) in Lemma 1 now follows from (30), Claims 1 and 2, and the Borel-Cantelli lemma. Equation (22) comes additionally from the remark made at the end of the proof of Claim 1. $\square$

3.3 Properties of Geodesics in Case of a Success

For $x\notin \varOmega _k$, we let $\varGamma _{0x}$ be the geodesic from 0 to x (unique since the $\xi _e$ are continuous random variables.) For $p,q\in \varGamma _{0x}$ we denote by $\varGamma _{0x}[p,q]$ the segment of $\varGamma _{0x}$ from p to q. We let $p_x$ be the first point of $\varGamma _{0x}$ outside $\varOmega _k$. We then define $t_x$ in the boundary of the “near-rectangle” $\varOmega _k^{NE}\cap \varOmega _k^{NW}$ as below.

Note that this boundary consists of 4 zigzag segments, one from each highway $H_{*,\cdot ,k}$ ($*=$ NE, NW; $\cdot =$ U, L). Some boundary points (one bond or site at each “corner”) are contained in 2 such segments; we call these double points. Removing all double points leaves 4 connected components of the boundary, which we call disjoint sides of $\varOmega _k^{NE}\cap \varOmega _k^{NW}$, each contained in a unique highway $H_{*,\cdot ,k}$. The set $\varOmega _k \backslash (\varOmega _k^{NE}\cap \varOmega _k^{NW})$ has 4 connected components, which we call arms, extending from $\varOmega _k^{NE}\cap \varOmega _k^{NW}$ in the directions NW, NE, SE, SW. Each arm includes one disjoint side of $\varOmega _k^{NE}\cap \varOmega _k^{NW}$ (recalling that the sets $\varOmega _k^*$ are open.)

If $p_x$ is not a double point then it is contained in the boundary of one of the arms, and we let $t_x$ be the first point of $\varGamma _{0x}[0,p_x]$ in that arm (necessarily in a disjoint side; see Case 3 of Fig. 4.) If instead $p_x$ is a double point, then we pick arbitrarily one of the two highways $H_{*,\cdot ,k}$ containing it, and let $t_x$ be the first site of $\varGamma _{0x}[0,p_x]$ in that highway.

For $\mu$ from (8), let $L_{N,k}$ denote the horizontal line $\mathbb {R}\times \{\mu ^{-k}\}$ which, at least on the event $F_k$, lies above $J_{N,k}$ and below $G_k^1$ (since $1/2< \mu < \widetilde{\theta }^{c_{\theta }}$); $L_{*,k}$ is defined analogously for $*=$ E, S, W. We define $\varLambda _{H,k}$ to be the “horizontal axis corridor,” meaning the closure of the portion of $\varOmega _k^{NE}\cap \varOmega _k^{NW}$ strictly between $L_{S,k}$ and $L_{N,k}$, and let $\varLambda _{V,k}$ denote the similar “vertical axis corridor.” The primary part of establishing directedness in axis directions is showing that all semi-infinite geodesics remain in these corridors until they exit out the far end, at least for many k, via the following deterministic result.

Lemma 2

For sufficiently large k, when $F_k$ occurs, for all $x\notin \varOmega _k$ we have either $\varGamma _{0x}[0, t_x]\subset {\varLambda }_{H,k}$ or $\varGamma _{0x}[0, t_x]\subset {\varLambda }_{V,k}$.

Proof

Let us start with a claim analogous to what we proved in Sect. 2. Recall the definitions of $\varGamma _{0x}$ and $p_x$.

Claim 3

When $F_k$ occurs, for all $x\notin \varOmega _k$ we have $p_x \notin G_k^1\cup G_k^2\cup G_k^3\cup G_k^4$.

Proof (Proof of Claim 3)

Suppose $p_x=(r,s)$ is in the horizontal part of $G_k^1$ (so $r\ge s=2^k$) and let ${U}_k'$ be the upper endpoint of the bond which is the intersection of $H_{NE,L,k}$ and the vertical line through $p_x$. Define the alternate path $\pi _x$ from 0 east to $U_k^{NE}$, then NE along $H_{NE,L,k}$ to $U_k'$, then north to $p_x$. We now compare the passage times of $\varGamma _{0x}[0,p_x]$ versus $\pi _x$.

We divide the bonds of the lattice into NW/SE diagonal rows: the jth diagonal row $R_j$ consists of those bonds with one endpoint in $\{(x_1,x_2):x_1+x_2=j-1\}$ and the other in $\{(x_1,x_2):x_1+x_2=j\}$. We call a bond $e\in \varGamma _{0x}[0,p_x]$ a first bond if for some $j\ge 1$, e is the first bond of $\varGamma _{0x}[0,p_x]$ in $R_j$, and we let N be the number of first bonds in $\varGamma _{0x}[0,p_x]$ which are in SE/NW highways. There are at least 2s first bonds, and any first bond e not in any SE/NW highway satisfies $\tau _e \ge 0.7+0.1\eta ^{k-1}$, since from $F_k\subset M_k$ we have $k(e)\le k-1$. From (15), letting $q=| \varGamma _{0x}[0,p_x]|\ge 2s$, at most q / 24 SE/NW highways intersect $\varGamma _{0x}[0,p_x]$. Since no two first bonds can be in the same SE/NW highway, we thus have $N\le q/24$. Therefore using (17),

$$\begin{aligned} T( \varGamma _{0x}[0,p_x])&\ge (2s-N)(0.7+0.1\eta ^{k-1}) + (q-2s+N)0.7 - 0.2 \nonumber \\&= 2s(0.7+0.1\eta ^k) + 2s(0.1\eta ^{k-1}-0.1\eta ^k) + (q-2s)0.7 - 0.1N\eta ^{k-1} - 0.2 \nonumber \\&\ge 2s(0.7+0.1\eta ^k) + 2s(0.1\eta ^{k-1}-0.1\eta ^k) + (q-2s)0.7 - \frac{q}{240}\eta ^{k-1} - 0.2. \end{aligned}$$

(33)

If $q\ge 3s$ then $q(0.7-\eta ^{k-1}/240) \ge 1.4s$ so from (33) we get

$$\begin{aligned} T( \varGamma _{0x}[0,p_x]) \ge 2s(0.7+0.1\eta ^k) + 2s(0.1\eta ^{k-1}-0.1\eta ^k) - 0.2. \end{aligned}$$

(34)

If instead $q<3s$ then since $1-\eta \ge 1/8$ we have $s(0.1\eta ^{k-1}-0.1\eta ^k) \ge s\eta ^{k-1}/80 \ge q\eta ^{k-1}/240$, so

$$\begin{aligned} T( \varGamma _{0x}[0,p_x]) \ge 2s(0.7+0.1\eta ^k) + s(0.1\eta ^{k-1}-0.1\eta ^k) - 0.2. \end{aligned}$$

(35)

By contrast, the NE segment of $\pi _x$ has length $2(r-X_{1,k}^{NE})$, the N segment has length $X_{1,k}^{NE}-(r-s)$, and all bonds have passage times at most 1.4, so we have for large k

$$\begin{aligned} T(\pi _x)&\le 1.4 X_{1,k}^{NE} + 1.4(X_{1,k}^{NE} - (r-s)) + 2(0.7+0.1\eta ^k + 0.1\widetilde{\eta }^k)(r-X_{1,k}^{NE}) \\&\le 2.8 X_{1,k}^{NE} + 2s(0.7+0.1\eta ^k +0.1 \widetilde{\eta }^k) \\&\le 2s(0.7+0.1\eta ^k) + \frac{4C}{r_k}, \end{aligned}$$

where we used that $X_{1,k}^{NE} \le C/r_k$, and that $\widetilde{\eta }^k s = (2\widetilde{\eta })^k \le C/r_k$, using (7). Therefore by (9) we get

$$\begin{aligned} T(\varGamma _{0x}[0,p_x]) - T(\pi _x) \ge 0.1\cdot 2^k(\eta ^{k-1}-\eta ^k) - \frac{4C}{r_k} - 0.2 > 0. \end{aligned}$$

This contradicts $\varGamma _{0x}[0,p_x]$ being a geodesic, so $p_x$ cannot be in the horizontal part of $G_k^1$. All other cases are symmetric, so Claim 3 is proved. $\square$

We need to further restrict the location of $\varGamma _{0x}[0,p_x]$. When $F_k$ occurs, we begin by dividing the sites of each $H_{*,\cdot ,k}$ (with $*=$ NW, NE and $\cdot =$ L, U) into accessible and inaccessible sites In $H_{NE,L,k}$ we define as inaccessible the sites strictly between its intersection with $J_{N,k}$ and its intersection with $J_{W,k}$; the rest of the sites are accessible. Lattice symmetry yields the definition of accessible in the other 3 zigzag paths.

This definition enables us to define canonical paths to reach accessible points, which we need below. Given a site $a\in J_{N,k}\cap \varOmega _k^{NE}$ and an accessible site $b\in H_{NE,L,k}$ in the first quadrant, there is a canonical path from a to b which follows $J_{N,k}$ from a to $H_{NE,L,k}$, then (changing direction 45$^\circ$) follows $H_{NE,L,k}$ to b. Similarly we can define canonical paths from sites $a\in J_{S,k}\cap \varOmega _k^{NW}$ to accessible $b\in H_{NW,U,k}$ in the fourth quadrant, with further extension by lattice symmetries. When two points a, b lie in the same horizontal or vertical line, we define the canonical path from a to b to be the one which follows that line.

We say $\varGamma _{0x}[0,p_x]$ is returning if it contains a point of $L_{*,k}$, followed by a point of $J_{*,k}$, where both values $*$ (N, E, W or S) are the same. We recall that by definition, from (8) we have $\theta<\mu <\widetilde{\theta }^{c_\theta }$ which ensures that, when $F_k$ occurs, the height of $\varLambda _{H,k}$ is much less than its length, but much more than the height of $J_{N,k}$. Recall the definitions of $p_x,t_x$ from the beginning of the section.

Claim 4

If $F_k$ occurs and $\varGamma _{0x}[0,t_x]\not \subset {\varLambda }_{H,k} \cup {\varLambda }_{V,k}$, then either $\varGamma _{0x}[0,p_x]$ is returning, or at least one of $t_x,p_x$ is accessible.

Proof

Suppose $F_k$ occurs, $\varGamma _{0x}[0,t_x]\not \subset {\varLambda }_{H,k} \cup {\varLambda }_{V,k}$, and neither $t_x$ nor $p_x$ is accessible. We may assume $p_x$ lies in $H_{NE,L,k}$ on or above $H_{NW,U,k}$, as other cases are symmetric; then $t_x\in H_{NW,U,k}$ (or we may assume so, if $p_x$ is a double point.) Since $\varGamma _{0x}[0,t_x]\not \subset {\varLambda }_{H,k} \cup {\varLambda }_{V,k}$, $\varGamma _{0x}[0,t_x]$ must intersect $L_{N,k}\cup L_{S,k}$; let $q_x$ be the first such point of intersection. If $q_x\in L_{S,k}$, then the fact that $t_x$ is not accessible (it must lie above $J_{S,k}$) means that $\varGamma _{0x}[0,p_x]$ is returning. If $q_x\in L_{N,k}$, then the fact that $p_x$ is not accessible (hence lying below $J_{N,k}$) again means that $\varGamma _{0x}[0,p_x]$ is returning. This proves Claim 4. $\square$

We now complete the proof of Lemma 2, by a contradiction argument. Assume that $F_k$ occurs, but for some $x\notin \varOmega _k$ we have $\varGamma _{0x}[0,t_x] \not \subset {\varLambda }_{H,k} \cup {\varLambda }_{V,k}$. As in the proof of Claim 4, we may assume $p_x$ lies in $H_{NE,L,k}$ on or above $H_{NW,U,k}$, and then that $t_x\in H_{NW,U,k}$. Let $q_x\in L_{N,k}\cup L_{S,k}$ be as in the proof of Claim 4, and let $a_x$ be the last point of $\varGamma _{0x}[0,q_x]$ in $J_{*,k}$, with subscript $*=$ N or S according as $q_x\in L_{N,k}$ or $q_x\in L_{S,k}$. Thus $\varGamma _{0x}[0,p_x]$ follows a path $0\rightarrow a_x\rightarrow q_x\rightarrow t_x\rightarrow p_x$.

By Claim 4, we now have three cases:

• Case 1 $\varGamma _{0x}[0,p_x]$ is returning. In this case we define $b_x$ to be the first point of $\varGamma _{0x}[q_x,p_x]$ in the line $J_{*,k}$ ($*=$ N or S) containing $a_x$.

• Case 2 $\varGamma _{0x}[0,p_x]$ is not returning, and $p_x$ is accessible (hence above $J_{N,k}$, so necessarily $q_x \in L_{N,k}$). In this case we define $b_x=p_x$.

• Case 3 $\varGamma _{0x}[0,p_x]$ is not returning, $p_x$ is inaccessible (hence below $J_{N,k}$, so necessarily $q_x \in L_{S,k}$), and $t_x$ is accessible. In this case we define $b_x=t_x$.

In all three cases we compare passage times for $\varGamma _{0x}[a_x,b_x]$ to that of the canonical path from $a_x$ to $b_x$, which we denote $\gamma _x$, and we obtain our contradiction by showing that

$$\begin{aligned} T(\gamma _x) < T( \varGamma _{0x}[a_x,b_x]), \end{aligned}$$

(36)

see Fig. 4.

Fig. 4

Cases 1–2–3 (from left to right). The path $\varGamma _{0x}$ is the curved line going through $a_x, q_x$ and $b_x$, and the canonical path $\gamma _x$ is the dashed line joining $a_x$ to $b_x$ through highways

Since $E_{2,k}$ occurs, there are no slow bonds in $\gamma _x$, so to prove (36) we may and do assume there are no slow bonds at all. Cases 2 and 3 are essentially symmetric, so we focus on Case 2 first, then the simpler Case 1.

We write (in Case 2)

$$\begin{aligned} a_x = (u,Y_{N,k}), \quad q_x = (y,\mu ^{-k}), \quad b_x = p_x = (r,s), \end{aligned}$$

(37)

and we let $(d,Y_{N,k})$ denote the left endpoint of the bond $J_{N,k}\cap H_{NE,L,k}$.

The class of the highway $J_{N,k}$ is at least $q_k$, so due to stage-2 deletions, the only zigzag highways intersecting $J_{N,k}$ have class greater than $c_{\widetilde{\theta }}q_k/(1+\zeta )$. From (17), (20) and the definition of $E_{1,k}$ we have

$$\begin{aligned} T(\gamma _x)&\le 0.9(d-u) + 0.4 + \sum _{m>c_{\widetilde{\theta }}q_k/(1+\zeta )} R_{k,m}\eta ^m + 2(s-Y_{N,k})(0.7+0.1\eta ^k) + 0.2 \nonumber \\&\le 0.9(d-u) + 2(s-Y_{N,k})(0.7+0.1\eta ^k) + 0.6 + c_1(\eta ^3\theta ^{-2})^{c_\theta \delta k} (\mu ^{-1}\eta )^k. \end{aligned}$$

(38)

Our aim is to show that for some $c_7$,

$$\begin{aligned} T( \varGamma _{0x}[a_x,b_x]) \ge 0.9(d-u) + 2(s-Y_{N,k})(0.7+0.1\eta ^k) + c_7 (\mu ^{-1}\eta )^k, \end{aligned}$$

(39)

which with (38) is sufficient to yield (36) for all large k, since $\mu ^{-1}\eta >1$ by (8) and $\eta ^3\theta ^{-2}<1$ by (7).

The rest of the proof is devoted to showing (39), by analyzing the type (and number of each type) of bonds that the path $\varGamma _{0x}$ uses.

We observe first that the intersection of a geodesic with any one zigzag highway is always connected, since we have assumed there are no slow bonds. A singleton bond in a path $\varGamma$ is a zigzag bond in $\varGamma$ which is preceded and followed in $\varGamma$ by boundary bonds. We divide $\varGamma _{0x}[a_x,b_x] = (a_x=z_0,z_1,\dots ,z_n=b_x)$ into the following types of segments:

• (i) zigzag segments: maximal subsegments which do not contain two consecutive non-zigzag bonds. A zigzag segment must start and end with a boundary bond, unless it starts at $a_x$ or ends at $b_x$.

• (ii) intermediate segments: the segments in between two consecutive zigzag segments, the segment up to the first zigzag segment, and the segment after the final zigzag segment (any of which may be empty.)

Within zigzag segments we find

• (iii) component segments: maximal subsegments contained in a single zigzag highway.

For each component segment in $\varGamma _{0x}[a_x,b_x]$ that is not both an intersection bond and a singleton bond, there is a unique highway orientation (SW/NE or SE/NW) determined by the zigzag highway containing the segment. We define $\varPhi (e)$ to be this orientation, for each bond e in the segment. For singleton bonds in $\varGamma$ that are also intersection bonds, we assign $\varPhi (e)$ arbitrarily. We say that a zigzag highway H intersects $\varGamma _{0x}[a_x,b_x]$ redundantly if the intersection is a single bond e and the orientation of H is not $\varPhi (e)$.

We let $z_{n_{2j-2}},z_{n_{2j-1}}$ be the endpoints of the jth intermediate segment, $1\le j\le J+1$, so $\beta _j= \varGamma _{0x}[z_{n_{2j-1}},z_{n_{2j}}]$ is the jth zigzag segment, $1\le j \le J$. For any path $\varGamma$ we define

$$\begin{aligned} T_{\alpha ^*}(\varGamma ) = \sum _{e\in \varGamma } \alpha _e^*. \quad \end{aligned}$$

(40)

For $*=$ Z, B, H, V we define

$$\begin{aligned} N_*(\varGamma ) = \big | \{e\in \varGamma : e \text { has property } * \} \big |, \end{aligned}$$

where subscripts and corresponding properties are as follows:

$$\begin{aligned}&Z: \text { zigzag} ,\qquad B: \text { not zigzag},\qquad H: \text { horizontal}, \qquad V: \text { vertical},\\&\quad N: \text { northward step in } \varGamma \text { (E, W, S similar)}. \end{aligned}$$

We may combine subscripts to require multiple properties, for example $N_{ZH}(\varGamma ) = | \{e\in \varGamma : e$ is a horizontal zigzag bond$\}|$, and we use superscripts NE or NW to restrict the count to zigzag bonds with $\varPhi (e) =$ SW/NE or SE/NW, respectively. We also let $N_{Hi}(\varGamma )$ be the number of zigzag highways intersecting $\varGamma$ non-redundantly. Note that if for example a SW/NE highway segment is traversed by $\varGamma$ in the NE direction, the number of N and E steps differs by at most 1. It follows that for every geodesic $\varGamma$ we have

$$\begin{aligned} N_{Hi}(\varGamma ) \ge D(\varGamma ) :=&\,|N_{ZE}^{NE}(\varGamma ) - N_{ZN}^{NE}(\varGamma )| + |N_{ZW}^{NE}(\varGamma ) - N_{ZS}^{NE}(\varGamma )| \nonumber \\&+ |N_{ZE}^{NW}(\varGamma ) - N_{ZS}^{NW}(\varGamma )| + |N_{ZW}^{NW}(\varGamma ) - N_{ZN}^{NW}(\varGamma )|. \end{aligned}$$

(41)

We now make some observations about geodesics and zigzag segments. We show that a zigzag segment $\beta _j$ may contain multiple bonds of at most one zigzag highway (which we call primary, when it exists)—any zigzag bonds in $\beta _j$ not in the primary highway are necessarily singleton bonds, and there are at most 2 of these; if $\beta _j$ intersects 3 zigzag highways non-redundantly then the primary highway must lie between the two singletons. Moreover, any non-zigzag interior bond of some $\beta _j$ must be an entry/exit bond. Indeed, due to the stage-3 trimming, in order for $\varGamma$ to switch from one zigzag highway to another within $\beta _j$ (with at least two bonds on each) there would need to be one of the following succession of steps (or some lattice rotation thereof): (i) N, E, E, E, S with the middle one being an exit/entry bond; (ii) N, E, E, S with the middle 2 being meeting zigzag bonds; (iii) N, E, S with the middle one being an intersection bond. We refer to Fig. 2 for a picture. But (since we are assuming no slow bonds) none of these patterns can occur in a geodesic, because omitting the N and S steps always produces a faster path. Then (15) and the stage-3 trimming establish the remaining properties mentioned.

For $2\le j\le J-1$, if $\beta _j$ contains a primary highway then the bonds of $\beta _j$, from the initial bond through the first bond of the primary highway, must follow one of the following patterns (we refer to Fig. 2):

• (i) skimming boundary, terminal

• (ii) boundary (not skimming), zigzag (not intersection)

• (iii) semislow boundary, intersection, meeting

• (iv) boundary (not skimming), meeting, meeting

• (v) boundary (not skimming), meeting, intersection (followed by meeting)

• (vi) boundary (not skimming), zigzag (not intersection), entry/exit, zigzag (not intersection).

The same is true in reverse order at the opposite end of $\beta _j$. (Note that certain patterns cannot appear in a geodesic $\varGamma$, for example a semislow boundary bond with both endpoints in meeting bonds cannot be adjacent in $\varGamma$ to either meeting bond, so these are not listed here.) If there is no primary highway then the full $\beta _j$ follows one of the following patterns, or its reverse:

• (vii) boundary (not skimming), zigzag (not intersection), boundary (not skimming)

• (viii) skimming boundary, singly terminal, boundary (not skimming)

• (ix) skimming boundary, doubly terminal, skimming boundary

• (x) semislow boundary, intersection, semislow boundary

• (xi) normal boundary, zigzag (not intersection), entry/exit, zigzag (not intersection), normal boundary.

It is readily checked from this that in all cases

$$\begin{aligned} T_{\alpha ^*}(\beta _j)&\ge 0.9N_B(\beta _j) + 0.7N_Z(\beta _j) + 0.2N_{Hi}(\beta _j), \quad 2\le j\le J-1. \end{aligned}$$

(42)

For $j=1,J$, $\beta _j$ is a truncation of a path as in (i)–(xi), omitting a (possibly empty) segment of bonds at one end, and we similarly have

$$\begin{aligned} T_{\alpha ^*}(\beta _j) \ge 0.9N_B(\beta _j) + 0.7N_Z(\beta _j) + 0.2N_{Hi}(\beta _j) - 0.2, \quad j=1,J, \end{aligned}$$

and therefore

$$\begin{aligned}&T_{\alpha ^*}( \varGamma _{0x}[a_x,b_x]) \ge 0.9N_B( \varGamma _{0x}[a_x,b_x]) + 0.7N_Z( \varGamma _{0x}[a_x,b_x]) + 0.2N_{Hi}( \varGamma _{0x}[a_x,b_x]) - 0.4. \end{aligned}$$

(43)

By (43) and (41) we have

$$\begin{aligned} T_{\alpha ^*}(\varGamma _{0x}[a_x,b_x]) \ge 0.9N_B(\varGamma _{0x}[a_x,b_x]) + 0.7N_Z(\varGamma _{0x}[a_x,b_x]) + 0.2D(\varGamma _{0x}[a_x,b_x]) - 0.4, \end{aligned}$$

(44)

and from the definition of $M_k^{NE}$,

$$\begin{aligned} T(\varGamma _{0x}[a_x,b_x])&\ge T_{\alpha ^*}(\varGamma _{0x}[a_x,b_x]) + 0.1\eta ^{k-1} \big ( N_{ZN}^{NE}(\varGamma _{0x}[a_x,b_x]) + N_{ZE}^{NE}(\varGamma _{0x}[a_x,b_x]) \big ). \end{aligned}$$

(45)

In view of (37) and (44)–(45), let us consider the question of minimizing

$$\begin{aligned}&0.9(n_{BE} + n_{BW} + n_{BN} + n_{BS}) \nonumber \\&\quad + 0.7\left( n_{ZN}^{NE} + n_{ZE}^{NE} + n_{ZW}^{NE} + n_{ZS}^{NE} + n_{ZN}^{NW} + n_{ZE}^{NW} + n_{ZW}^{NW} + n_{ZS}^{NW} \right) \nonumber \\&\quad + 0.2\Big ( |n_{ZE}^{NE} - n_{ZN}^{NE}| + |n_{ZW}^{NE} - n_{ZS}^{NE}| + |n_{ZE}^{NW} - n_{ZS}^{NW}| + |n_{ZW}^{NW} - n_{ZN}^{NW}| \Big ) \nonumber \\&\quad + 0.1\eta ^{k-1}(n_{ZN}^{NE} + n_{ZE}^{NE}) - 0.4 \end{aligned}$$

(46)

subject to all 8 variables being nonnegative integers satisfying

$$\begin{aligned} n_{ZE}^{NE} + n_{ZE}^{NW} - n_{ZW}^{NE} - n_{ZW}^{NW} + n_{BE} - n_{BW}&= (d-u)+(s-Y_{N,k}) = N_H(\gamma _x), \end{aligned}$$

(47)

$$\begin{aligned} n_{ZN}^{NE} - n_{ZS}^{NW} - n_{ZS}^{NE} + n_{ZN}^{NW} + n_{BN} - n_{BS}&= s-Y_{N,k} = N_V(\gamma _x), \end{aligned}$$

(48)

$$\begin{aligned} n_{ZN}^{NE} + n_{ZN}^{NW} + n_{BN}&= (s-Y_{N,k}) + g, \end{aligned}$$

(49)

$$\begin{aligned} n_{ZS}^{NE} + n_{ZS}^{NW} + n_{BS}&= g, \end{aligned}$$

(50)

$$\begin{aligned} n_{ZN}^{NW} + n_{BN}&= j, \end{aligned}$$

(51)

for some fixed $g\ge 0$ and $0\le j\le (s-Y_{N,k})+g$. Here (50) is redundant but we include it for ready reference, and despite (51) we formulate the problem with $n_{ZN}^{NW}$ as a variable, to match the rest of the problem. Further, g may be viewed as an “overshoot”, the number of northward steps beyond the minimum needed to reach the height s of $p_x$, and j is the number of northward steps taken “inefficiently,” that is, not in NE/SW zigzag highways. Since $q_x$ is at height $\mu ^{-k}$, we may restrict to $s+g\ge \mu ^{-k}$, and thus from the definition of $\widetilde{D}_k$, also to

$$\begin{aligned} s-Y_{N,k}+g\ge \mu ^{-k} - \frac{C}{\widetilde{r}_{q_k} } \ge \frac{ \mu ^{-k} }{2}, \end{aligned}$$

(52)

the last inequality being valid for large k, following from the fact that $\widetilde{r}_{q_k}$ is a constant multiple of $\widetilde{\theta }^{ -c_{\theta }k }$ while $\mu < \widetilde{\theta }^{ c_{\theta } }$ by (8). To study this we use the concept of shifting mass from one variable $n_{\bullet }^*$ to a second one, by which we mean incrementing the second by 1 and the first by $-1$. We also use canceling mass between two variables in (47) or two in (48), one appearing with $``+"$ and the other with $``-"$, by which we mean decreasing each variable by 1.

Shifting mass from $n_{BS}$ to $n_{ZS}^{NE}$, or from $n_{BN}$ to $n_{ZN}^{NW}$, does not increase (46), so a minimum exists with $n_{BS}=n_{BN}=0$, so we may eliminate those two variables. Among the variables $n_{\bullet }^*$ in (47), if a variable with “$+$” and a variable with “−” are both nonzero, then canceling (unit) mass between them decreases (46) by at least 1; this means that a minimum exists with all negative terms on the left in (47) equal to 0. Then shifting mass in (48) from $n_{ZS}^{NE}$ to $n_{ZS}^{NW}$, or in (47) from $n_{BE}$ to $n_{ZE}^{NW}$, does not increase (46) (since the preceding step has set $n_{ZW}^{NE}$ and $n_{ZW}^{NW}$ to 0), so there is a minimum with also $n_{ZS}^{NE}=n_{BE}=0$. With these variables set to 0, the problem becomes minimizing

$$\begin{aligned}&0.7\left( n_{ZE}^{NE} + n_{ZE}^{NW} + s-Y_{N,k}+2g \right) + 0.2\Big ( |n_{ZE}^{NE} - (s-Y_{N,k}+g-j)| + |n_{ZE}^{NW} - g| + j\Big ) \nonumber \\&\quad + 0.1\eta ^{k-1}(s-Y_{N,k}+g-j + n_{ZE}^{NE}) - 0.4 \end{aligned}$$

(53)

subject to

$$\begin{aligned} n_{ZE}^{NE} + n_{ZE}^{NW}&= (d-u)+(s-Y_{N,k}). \end{aligned}$$

(54)

Setting $n_{ZE}^{NE}=z, n_{ZE}^{NW} = (d-u)+(s-Y_{N,k})-z$ and considering the effect of incrementing z by 1, we see that (53) is minimized (not necessarily uniquely) at

$$\begin{aligned} z= \min \Big ((s-Y_{N,k})+g-j,[(s-Y_{N,k})+(d-u)-g]\vee 0\Big ). \end{aligned}$$

(55)

We now consider two cases.

Case 2A $2g-j\le d-u$. Here we have $z=(s-Y_{N,k})+g-j\ge 0$ in (55), and the corresponding minimum value of (53) is

$$\begin{aligned}&0.9(d-u) + 0.7\cdot 2(s-Y_{N,k}) + g+0.4j + 0.1\eta ^{k-1}(2(s-Y_{N,k})+2(g-j)) - 0.4\\&\quad \ge 0.9(d-u) + 0.7\cdot 2(s-Y_{N,k}) +g+ 0.1\eta ^{k-1} \cdot 2(s-Y_{N,k}) - 0.4\\&\quad \ge 0.9(d-u) + (0.7 + 0.1 \eta ^{k-1}) 2(s-Y_{N,k}) + 0.1\eta ^k(\eta ^{-1}-1) \cdot 2 (s-Y_{N,k}+g) - 0.4. \end{aligned}$$

For the first inequality, we used that $0.4 j\ge 0.2 \eta ^{k-1} j$, and for the second one that $g \ge 0.2\eta ^k(\eta ^{-1}-1)g$, for k sufficiently large. With (45) and (52) this shows that

$$\begin{aligned}&T( \varGamma _{0x}[a_x,b_x]) \ge 0.9(d-u) + (0.7 + 0.1\eta ^k)\cdot 2(s-Y_{N,k}) + 0.1 \eta ^k(\eta ^{-1}-1)\mu ^{-k} - 0.4. \end{aligned}$$

Since $\eta >\mu$ by (8), this proves (39).

Case 2B $2g-j>d-u$, so that

$$\begin{aligned} 0.8g \ge 0.4(d-u) + 0.1\eta ^{k-1} j. \end{aligned}$$

(56)

Here we have $z=[(s-Y_{N,k})+(d-u)-g]\vee 0$ in (55), and the corresponding minimum value of (53) in the case $z = (s-Y_{N,k})+(d-u) -g>0$ (the case $z=0$ being treated similarly) is

$$\begin{aligned}&0.5(d-u) + 0.7\cdot 2(s-Y_{N,k}) + 1.8g + 0.1\eta ^{k-1}((d-u) + 2(s-Y_{N,k}) - j) - 0.4 \\&\quad \ge 0.9(d-u) + 0.7\cdot 2(s-Y_{N,k}) + g+ 0.1\eta ^{k-1}\cdot 2(s-Y_{N,k}) - 0.4 \end{aligned}$$

where the inequality follows from (56). Then (39) follows as in Case 2A.

We now briefly explain the modifications of the above argument to treat Case 1. Analogously to (37), we write

$$\begin{aligned} a_x = (u,Y_{N,k}), \quad q_x = (y,\mu ^{-k}), \quad b_x = (v,Y_{N,k}), \end{aligned}$$

and we may assume $v-u>0$, since otherwise we can consider the path $\varGamma _{0x}[a_x,b_x]$ running backwards. Similarly to (38), we have

$$\begin{aligned} T(\gamma _x)&\le 0.9(v-u) + 0.5 + \sum _{m>c_{\widetilde{\theta }}q_k/(1+\zeta )} R_{k,m}\eta ^m \nonumber \\&\le 0.9(v-u) + 0.5 + c_1(\eta ^3\theta ^{-2})^{c_\theta \delta k} (\mu ^{-1}\eta )^k. \end{aligned}$$

(57)

and similarly to (39) we want to show

$$\begin{aligned} T(\varGamma _{0x}[a_x,b_x]) \ge 0.9(v-u) + c_7 (\mu ^{-1}\eta )^k \end{aligned}$$

(58)

in order to obtain (36). Then, in the proof above, we replace $d-u$ with $v-u$ and $s-Y_{N,k}$ with 0 in the constraints (47)–(51) and in (52). Otherwise the proof remains the same, establishing (58). In the end, in all the Cases 1–3 we have the contradiction (36), and Lemma 2 is proven. $\square$

3.4 Conclusion of the Proof of Theorem 1

Item (ii) This follows from the combination of Lemma 1 and Lemma 2. For a configuration $\omega$ let $n_1(\omega )<n_2(\omega )<\dots$ be the indices k for which $\omega \in F_k$. Let $\varGamma _0$ be an infinite geodesic starting from the origin, with sites $0=x_0,x_1,\dots$. Then Lemma 2 says that for each $j\ge 1$, $\varGamma _0$ is contained in either $\varLambda _{H,n_j}$ or $\varLambda _{V,n_j}$ until it leaves $\varOmega _{n_j}^{NE}\cap \varOmega _{n_j}^{NW}$; accordingly, we say $\varGamma _0$ is horizontal at stage j or vertical at stage j.

Suppose $\varGamma _0$ is horizontal at stage j, and vertical at stage $j+1$. The horizontal coordinate of the first point of $\varGamma _0$ outside $\varOmega _{n_j}^{NE}\cap \varOmega _{n_j}^{NW}$ then has magnitude at least $c/r_{n_j} - \mu ^{-n_j}$ but at most $\mu ^{-n_{j+1}}$ (since $\varGamma _0$ is vertical at stage $j+1$.) Since $\theta < \mu$ by (8), this means that for large j we have $c/(2r_{n_j}) \le \mu ^{-n_{j+1}}$. Choosing $\epsilon >0$ small enough so that $\mu ^{1+\epsilon }>\theta$, thanks to (22) we get that for large j, $n_{j+1} \le (1+\epsilon ) n_j$, so that

$$\begin{aligned} \Big (\frac{\mu ^{1+\epsilon } }{\theta } \Big )^{n_j} \le \frac{\mu ^{n_{j+1}}}{r_{n_j}} \le \frac{2}{c}. \end{aligned}$$

But this can only be true for finitely many j. Hence there exists a random $J_0$ such that for $j\ge J_0$, either $\varGamma _0$ is horizontal at stage j for all $j\ge J_0$, or $\varGamma _0$ is vertical at stage j for all $j\ge J_0$. (We call $\varGamma _0$ horizontal or vertical, accordingly.) Using again that $n_{j+1}/n_j \rightarrow 1$, we get that

$$\begin{aligned} \mu ^{-n_{j+1}} \ll \frac{c}{ r_{n_j} } \quad \text {as } j\rightarrow \infty , \end{aligned}$$

that is, the width of $\varLambda _{*,n_{j+1}}$ is much less than the length of $\varLambda _{*,n_j}$, for $*=$ H, V. This guarantees that for such $\varGamma _0$, the angle to $x_i$ from an axis approaches 0, that is, $\varGamma _0$ is directed in an axis direction, proving Theorem 1(ii).

Remark 2

The above reasoning gives that geodesics reaching horizontal distance $n= c/r_{k}= c' \theta ^{-k}$ deviate from the horizontal axis by at most $\mu ^{-k}$. In the other direction, heuristically, in order to reach horizontal distance $n = c/r_{k}$, the most efficient way should involve a route going as soon as possible (through a succession of horizontal and zigzag highways) to the closest horizontal highway that reaches at least distance $c/r_k$, and then following that highway. This suggests that in order to reach distance $n=c/r_k$, geodesics have a transversal fluctuation of order at least $1/\widetilde{r}_{q_k} = c \widetilde{\theta }^{- c_\theta k}=c\theta ^{-c_{\widetilde{\theta }}k}$, or equivalently order $n^{c_{\widetilde{\theta }}}$, as this is the typical vertical distance to the closest horizontal highway reaching n.

Suppose $c_{\widetilde{\theta }}>10/11$. Then choosing $c_\theta$ slightly less than 0.5, then $\eta$ slightly less than 2/3, and then $\delta$ sufficiently small, we satisfy (7), (8), and the conditions preceding them, and further, $\widetilde{\theta }^{c_\theta }$ is the smallest of the 3 quantities on the right side of (8). This means we can choose $\mu$ arbitrarily close to $\widetilde{\theta }^{c_\theta }=\theta ^{c_{\widetilde{\theta }}}$. Thus our upper bound of $\mu ^{-k}$ becomes $n^{c_{\widetilde{\theta }} +o(1)}$, nearly matching the heuristic lower bound. Hence in this case we expect geodesics reaching horizontal distance n to have transversal fluctuations of order $n^{c_{\widetilde{\theta }} +o(1)}$, with at least all values $c_{\widetilde{\theta }}\in (10/11,1)$ being possible.

Item (i) It follows readily from an upper bound in the same style as the lower bound (24) that for $\epsilon >0$, $\mathbf {P}(X_{i,k}^{*} \ge \epsilon 2^k)$ is summable over k, so that $X_{i,k}^{*} =o(2^k)$ a.s. (meaning there are long diagonal highways close to the origin), and therefore the asymptotic speed in any diagonal direction is $\sqrt{2}/1.4$, and similarly along an axis it is 1 / 0.9.

Observe that (43) in the proof of Lemma 2 is valid for all geodesics, as that is the only property of $\varGamma _{0x}(a_x,b_x)$ that is used. Consider then the geodesic from (0, 0) (in place of $a_x$) to some point (r, s) with $0\le s\le r$ (in place of $b_x$.) It is easy to see that the right side of (43) is not increased if we replace the geodesic with a path of 2s consecutive zigzag bonds (heading NE) and $r-s$ horizontal bonds heading east—effectively this means consolidating all zigzag bonds into a single highway. It follows that the passage time is

$$\begin{aligned} \tau ((0,0),(r,s)) \ge \left( .9(r-s) + 1.4s\right) (1+o(1)) \quad \text {as } b\rightarrow \infty . \end{aligned}$$

From the fact that there are, with high probability, long HV and zigzag highways close to any given point (reflected in the fact that $X_{*,k}=o(2^k)$ and $Y_{*,k}=o(2^k)$), we readily obtain the reverse inequality. The linearity of the asymptotic expression $.9(r-s) + 1.4s$ means that the limit shape is flat between any diagonal and an adjacent axis. It follows that the limit shape $\mathcal {B}$ is an octogon, with vertex (1 / .9, 0) on the horizontal axis, $(\sqrt{2}/1.4,\sqrt{2}/1.4)$ on the SW/NE diagonal, and symmetrically in other quadrants, proving Theorem 1(i).

Item (iii) Let F be the facet of B in the first quadrant between the horizontal axis and the main diagonal, and let $\rho _F$ be the linear functional equal to 1 on F. We have from Theorem 1.11 in [4] that there is a semi-infinite geodesic $\varGamma _F$ with $\text {Dir}(\varGamma _F) \subset \{v/|v|:v\in F\}$, and Theorem 4.3, Corollary 4.7 and Proposition 5.1 of [4] show that $\varGamma _F$ has Busemann function linear to $\rho _F$. But all geodesics are directed in axis directions so we must have $\text {Dir}(\varGamma _F)=\{(1,0)\}$. Let $\widehat{F}$ be the facet which is the mirror image of F across the horizontal axis. From lattice symmetry, we have $\text {Dir}(\varGamma _{\widehat{F}})=\{(1,0)\}$ and its Busemann function is linear to $\rho _{\widehat{F}}$. Since the Busemann functions differ, we must have $\varGamma _F\ne \varGamma _{\widehat{F}}$. This and lattice symmetry prove Theorem 1(iii).