\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb,amsthm,mathtools,mathrsfs}
\usepackage[expansion=false]{microtype}
\usepackage{enumitem,booktabs,array}
\usepackage[dvipsnames]{xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\usepackage{hyperref}
\hypersetup{colorlinks=true,linkcolor=MidnightBlue,citecolor=MidnightBlue,
  urlcolor=MidnightBlue,pdfauthor={OpenAI},
  pdftitle={Strict convexity and differentiability of the planar exponential first-passage limit shape}}
\usepackage[nameinlink,capitalise,noabbrev]{cleveref}
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\E}{\mathbb E}
\newcommand{\PP}{\mathbb P}
\newcommand{\R}{\mathbb R}
\newcommand{\Z}{\mathbb Z}
\newcommand{\N}{\mathbb N}
\newcommand{\Bcal}{\mathcal B}
\newcommand{\Bus}{\mathsf{B}}
\newcommand{\Ccal}{\mathcal C}
\newcommand{\Fcal}{\mathcal F}
\newcommand{\Gcal}{\mathcal G}
\newcommand{\Kcal}{\mathcal K}
\newcommand{\1}{\mathbf 1}
\newcommand{\dd}{\mathrm d}
\newcommand{\eps}{\varepsilon}
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\newcommand{\abs}[1]{\left\lvert#1\right\rvert}
\DeclareMathOperator{\dist}{dist}
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\TV}{TV}
\DeclareMathOperator{\supp}{supp}
\setlist{topsep=5pt,itemsep=3pt,parsep=0pt}
\setlength{\emergencystretch}{2em}
\setcounter{tocdepth}{1}
\title{Strict convexity and differentiability\\of the planar exponential first-passage limit shape}
\author{OpenAI}
\date{September 2026}

\begin{document}
\maketitle

\begin{abstract}
We prove that the limit shape of undirected nearest-neighbor
first-passage percolation on $\Z^2$ with independent exponential
edge weights is strictly convex and has a $C^1$ boundary. This settles
the strict-convexity and differentiability conjectures for the planar
exponential model. In fact, we prove differentiability of the
time-constant norm for every Gamma edge-weight law with positive
shape and rate. The proof separates cleanly into two independent
parts. {\em Part I} rules out corners of the limit shape for every
Gamma law. {\em Part II} rules out flat faces for exponential
weights. Combined they give both conclusions.
\end{abstract}

\tableofcontents
\clearpage

\section{Introduction}
\label{sec:introduction}

This introduction states the two main theorems, explains the geometry
we are trying to control, and gives a step-by-step plan for both
proofs. The two parts of the paper are logically independent; a
reader may read \S\ref{sec:introduction} and then jump to whichever
part is of interest. Part~\ref{part:differentiability} proves a
differentiability theorem for every Gamma law and is the shorter
half. Part~\ref{part:strict} proves strict convexity for the
exponential law and is the longer, more technical half.

\subsection{The model}

Put an independent positive weight $\tau_e$ on each unoriented
nearest-neighbor edge $e$ of the square lattice $\Z^2$. The {\em
cost} of a finite path $P$ with edges $e_1,\dots,e_m$ counted with
traversal multiplicity is $\tau(P)=\sum_{i=1}^m\tau_{e_i}$. Let
$\Delta P$ be the terminal vertex minus the initial vertex. The
{\em passage time} between lattice vertices $x$ and $y$ is
\[
  T(x,y) \;=\; \inf_{P:x\to y}\,\tau(P),
\]
the infimum over finite undirected lattice paths. Nonnegativity and
the shape theorem below ensure the infimum is attained.

Let $\mu$ be the deterministic norm produced by the shape theorem
(recalled precisely in Lemma~\ref{lem:shape-theorem}). Its unit
ball $\Bcal=\{\xi\in\R^2:\mu(\xi)\le1\}$ is the {\em limit shape}.
The whole paper studies the {\em fine geometry} of $\Bcal$:
\begin{itemize}
  \item {\em corners} --- points of $\partial\Bcal$ where more than
        one line supports the body from outside; these are exactly
        the points where $\mu$ fails to be Fr\'echet differentiable;
  \item {\em flat faces} --- nontrivial line segments inside
        $\partial\Bcal$; these are absent exactly when $\Bcal$ is
        strictly convex.
\end{itemize}
Figure~\ref{fig:geometry} shows both failures next to a strictly
convex $C^1$ body.

\begin{figure}[ht]
\centering
\begin{tikzpicture}[scale=0.94,line width=0.8pt,
  body/.style={draw=MidnightBlue,fill=MidnightBlue!6},
  support/.style={draw=BrickRed,dashed}]
 \begin{scope}[xshift=-4.5cm]
  \path[body] (-0.9,0.7)--(0.9,0.7)
   .. controls (1.5,0.1) and (1,-1.1) .. (0,-1.1)
   .. controls (-1,-1.1) and (-1.5,0.1) .. (-0.9,0.7);
  \draw[support] (-1.6,0.7)--(1.6,0.7);
  \fill[BrickRed] (-0.9,0.7) circle (1.8pt) (0.9,0.7) circle (1.8pt);
  \node at (0,-1.6) {flat face};
 \end{scope}
 \begin{scope}
  \path[body] (0,1) .. controls (1.5,0.15) and (1,-1.1) .. (0,-1.1)
   .. controls (-1,-1.1) and (-1.5,0.15) .. (0,1);
  \draw[support] (-1.5,1.6)--(1.5,0.4);
  \draw[support] (-1.5,0.4)--(1.5,1.6);
  \fill[BrickRed] (0,1) circle (1.8pt);
  \node at (0,-1.6) {corner};
 \end{scope}
 \begin{scope}[xshift=4.5cm]
  \path[body] (0,-0.05) circle (1.05);
  \draw[support] (-1.6,1)--(1.6,1);
  \fill[BrickRed] (0,1) circle (1.8pt);
  \node at (0,-1.6) {strictly convex and $C^1$};
 \end{scope}
\end{tikzpicture}
\caption{The two failures of regularity. The circle is only a
schematic of a strictly convex $C^1$ body; it is not a proposed
formula for the limit shape.}
\label{fig:geometry}
\end{figure}

\subsection{The two main theorems}

\begin{theorem}[The exponential limit shape]
\label{thm:exponential-shape}
Let $\tau_e$ be independent exponential variables of any rate
$\lambda>0$ on the edges of $\Z^2$. Then $\mu$ is Fr\'echet
differentiable on $\R^2\setminus\{0\}$, and $\Bcal$ is strictly
convex: if $x\ne y\in\partial\Bcal$ and $0<t<1$ then
$\mu((1-t)x+ty)<1$. Equivalently, $\partial\Bcal$ is a $C^1$ curve
with a unique supporting line at every point.
\end{theorem}

The differentiability part of the proof does not use exponentiality;
it works for every Gamma law.

\begin{theorem}[Differentiability for Gamma weights]
\label{thm:gamma-differentiability}
Let $\tau_e$ be independent Gamma variables with any fixed shape
$\kappa>0$ and rate $\lambda>0$, with density
$p_{\kappa,\lambda}(t)=\lambda^{\kappa}t^{\kappa-1}e^{-\lambda t}/\Gamma(\kappa)$
on $t>0$. Then $\mu$ is Fr\'echet differentiable at every nonzero
vector and $\partial\Bcal$ is a $C^1$ curve.
\end{theorem}

Exponential weights are the case $\kappa=1$.
Theorem~\ref{thm:gamma-differentiability} is proved in
Part~\ref{part:differentiability} and does not use strict
convexity. Theorem~\ref{thm:exponential-shape} then combines the
$C^1$ conclusion of Theorem~\ref{thm:gamma-differentiability} at
$\kappa=1$ with strict convexity of $\Bcal$, proved from scratch in
Part~\ref{part:strict}. The scale change
$\tau_e\mapsto\lambda^{-1}\tau_e$ multiplies every passage time by
$\lambda^{-1}$, hence $\mu$ and $\Bcal$; all rates follow from the
rate-one case. This is the only place the rate enters.

\subsection{Why this is hard}

The shape theorem itself is old, and existence and convexity of
$\Bcal$ have been known since the early 1980s. Fine regularity is
much more delicate. Two obstructions must be checked by hand.

\emph{Flat faces are invisible at the level of expectations.} The
passage time $T(0,\lfloor tv\rfloor)$ converges to $\mu(v)$ almost
surely for every fixed $v$. A flat face causes no contradiction at
the level of first moments: a geodesic near one endpoint of the face
may occasionally cut inward and save cost without violating the shape
theorem for any single direction. Ruling out a face requires
constructing a path that saves on average, then extracting a
full-support bound from it.

\emph{Corners hide behind supporting slopes.} A corner on
$\partial\Bcal$ means two distinct linear functionals $f_-$ and $f_+$
both support the norm at one boundary point. Long paths near the
corner pay a linear defect proportional to the slope gap, so they
must be short or very lucky. Ruling out a corner requires dividing
paths into chunky pieces and controlling the entropy of choices via
a van den Berg--Kesten argument. See
Sections~\ref{df:sec:crossings}--\ref{df:sec:witnesses}.

\subsection{Plan of Part I: no corners}

Fix any Gamma law and a direction $u=(1,b)$ with $|b|\le1$. The two
one-sided transverse slopes
\[
  a_\pm = \lim_{t\to0^\pm}
    \frac{\mu(1,b+t)-\mu(1,b)}{t}
\]
satisfy $a_-\le a_+$ by convexity. Suppose $a_-<a_+$. The gap
$c=(a_+-a_-)/2>0$ measures the corner strength. Fix the extreme
supporting functionals $f_\pm=m_0x+a_\pm r$, where
$x(z)=z_1$, $r(z)=z_2-bz_1$, $m_0=\mu(1,b)$, and the average
$f=(f_-+f_+)/2$. Every path $P$ has defect
$H(P)=\tau(P)-f(\Delta P)$, negative exactly when $P$ beats the
average support. The aim is to produce a positive average defect
along any long path toward the corner, contradicting the shape
theorem.

The four ingredients, in order:
\begin{enumerate}
  \item {\em Localized rare-fast crossings}
    (Section~\ref{df:sec:crossings}). A crossing confined to a strip
    of width $s$ and length $n\gg s$ is unlikely to save $\eps s$
    worth of defect. Otherwise, independent parallel trials strung
    together would build an infinite path with linear negative
    defect, contradicting the shape theorem.
  \item {\em Characteristic scales via change of measure}
    (Section~\ref{df:sec:scales}). An exponential tilting combines
    with the crossing estimate to show that at width $s=2^k$ the
    first length $L_k$ at which $s$-width crossings become unlikely
    satisfies $L_k\le s^3$ and $L_k/s\to\infty$.
  \item {\em Endpoint extensions} (Section~\ref{df:sec:grids}).
    Upgrade the fixed-column crossing estimate to arbitrary
    endpoints chosen after the environment is observed, using
    simultaneous grid connections.
  \item {\em BK witness counting} (Section~\ref{df:sec:witnesses}).
    At the fixed scale $(s,L)$, cut every simple path into
    $L\times s$ chunks. A cheap chunk contains an edge-disjoint
    path witness for a rare decreasing event. A union bound over
    coarse itineraries, the BK inequality, and Borel--Cantelli give
    a positive average defect for every simple path from the
    origin, contradicting the shape theorem along $u$.
\end{enumerate}
The convex-analysis equivalence between unique support, Fr\'echet
differentiability, and a $C^1$ boundary is easy and is done
separately in Section~\ref{df:sec:conclusion}.

\subsection{Plan of Part II: no flat faces}

Suppose $\Bcal$ contains a nontrivial line segment. Take the maximal
supporting face and its extreme endpoints. Let $h$ be the linear
functional equal to one on the face; then $h\le\mu$ globally and
$\mu=h$ on the cone generated by the face.

\emph{The variational quantity $b(n)$.} Work on the rescaled lattice
$\Gcal_n=n^{-1}\Z^2$, keeping the original exponential weights. An
{\em admissible road} is a measurable, locally finite two-sided
lattice path tracking one of two interior directions near the face
endpoints, with private randomization. The scaled defect
$D_n(\gamma)=\tau(\gamma)-B_n(x,y)$, where $B_n$ is the
Damron--Hanson Busemann cocycle, is nonnegative on every forward
subpath by construction. Let $b(n)$ be the infimum over admissible
pairs of roads of the common mean defect per unit period. We prove
\[
  0 < c_0 \le b(n) \le C_s n^{3/4}.
\]
The lower bound comes from a local weight-decrease perturbation of a
square route; the upper bound comes from concatenating short
geodesics inside small balls (Section~\ref{sec:fb-bounds}).

\emph{The contraction.} The hard step is a fixed-rate contraction
$b(Dn)\le\rho b(n)$ for a fixed integer $D$ and $\rho<1$
(Proposition~\ref{improvement:contraction-proposition}). It rules
out the face. The ingredients are:
\begin{enumerate}
  \item {\em Local gauges} (Section~\ref{found:sec-gauges}). Replace
    the nonlocal calibration increment $P_n(y)-P_n(x)$ by a local
    random potential $g(y)-g(x)$ computed from nearby inputs, via
    finite-product (ANOVA) projections of the Busemann cocycle.
  \item {\em Phase templates and column independence}
    (Section~\ref{phases:section}). Choose wall phases and mesh
    offsets so that a suitable link field is i.i.d.\ on a sparse
    sublattice, and separated columns of the wall network are
    independent.
  \item {\em Selected-access collection bound}
    (Section~\ref{access:section}). For any locally defined reward
    field on a sparse lattice, the supremum of $\sum_pY_p$ over
    finite directed chains in a square of side $L$ is at most
    $CL+C_0$ in expectation. This handles the fact that optimizers
    choose their own cut sites after the environment is revealed.
  \item {\em Thin-diagram tails} (Section~\ref{probability:section}).
    A weak $L^2$ estimate on the reward plus an area-preserving
    lattice permutation compressing the direction orthogonal to the
    flat upgrades chain-tail sums to a linear-in-$N$ bound.
  \item {\em Links from a long geodesic} (Section~\ref{links:section}).
    A long geodesic toward an extreme endpoint of the flat supplies
    many horizontal crossings ({\em links}) after discarding a
    small halo near exceptional pieces. Row concentration plus the
    collection bound limits their mean clipped cost.
  \item {\em Improvement of a road} (Section~\ref{improvement:section}).
    Use the linked crossings as cheap competitors to the road's own
    pieces; replace rare large positive costs by pieces of an
    independent {\em spare} road. The resulting rule is admissible
    at a coarser scale, giving $b(Dn)\le\rho b(n)$.
\end{enumerate}
Iterating $b(Dn)\le\rho b(n)$ contradicts $b\ge c_0>0$, so the flat
face cannot exist. Section~\ref{conclusion:section} closes the
argument and does the scalar rescaling.

\subsection{Relation to the literature}

First-passage percolation was introduced by Hammersley and Welsh
\cite{HW1965}; the shape theorem is due to Richardson~\cite{Richardson1973}
and Cox--Durrett~\cite{CD1981}. Fine geometry of $\Bcal$ is surveyed
by Auffinger--Damron--Hanson~\cite{ADH2017}. Partial strict-convexity
results appear in Lalley~\cite{Lalley2003}, in Durrett--Liggett's
contact-process analysis~\cite{DurrettLiggett1981}, and in
Marchand~\cite{Marchand2002} and Auffinger--Damron~\cite{AD13} for
laws with an atom at a positive minimum. Our laws are atomless at
zero.

On the geodesic side, Damron--Hanson~\cite{DH2017} gives
direction-fixed convergence and coalescence to a specified supporting
face under differentiability hypotheses; the two regularity theorems
make the sector a single direction, so Section~\ref{sec:consequences}
quotes their results unchanged. The qualitative BKS midpoint problem
\cite{BKS2003} for all Gamma laws without regularity is due to
Ahlberg--Hoffman~\cite{AH2019}; the quantitative midpoint theorem of
Dembin--Elboim--Peled~\cite{DEP2024} needs differentiability as its
sole geometric hypothesis, which we supply for the whole Gamma
family. The companion paper~\cite{OpenAINoBigeodesics2026} excludes
all bigeodesics for i.i.d.\ Gamma weights.

Part~\ref{part:strict} builds on the Damron--Hanson cocycle~\cite{DH2014}
and on the concentration and mean estimates of
Damron--Hanson--Sosoe~\cite{DHS2014} and Damron--Kubota~\cite{DK2016}.
The BK inequality~\cite{BK85} and its continuous extension by
Arratia--Garibaldi--Hales~\cite{AGH2018} underpin the witness
counting of Part~\ref{part:differentiability}. The itinerary and
multiplicity counting follows Kesten~\cite{Kesten1980}; the
change-of-measure step is close to Chatterjee~\cite{Chatterjee2019}.
ANOVA projections are due to Efron--Stein~\cite{EfronStein1981}.
Hall's theorem~\cite{Hall1935} produces the lattice permutation.
Hoeffding's inequality~\cite{Hoeffding1963} handles row
concentration. Pinsker's inequality in the form of
van Erven--Harremo\"es~\cite{vanErvenHarremoes2014} enters the
lower-bound argument for $b(n)$.

\subsection{Notation and conventions}

$|\cdot|$ is the Euclidean norm unless another norm is specified;
$\mu$ is the time-constant norm; $\Bcal=\{\mu\le1\}$ is the unit
ball; $|x|_1$ is the $\ell^1$ norm. Edge weights are positive almost
surely; loop erasure never increases path cost, and we use this
without comment. A {\em path constrained to a set} $A$ means all its
vertices lie in $A$; we only test edges with both endpoints in $A$.
Concatenated paths may retrace edges; each traversal contributes.
Constants decorated by a subscript $s,K,\kappa,\lambda,F,\dots$ may
depend on that subscript; undecorated constants are absolute unless
stated otherwise. ``For all sufficiently large $n$'' means for some
threshold depending only on the subscripted parameters. All
probabilities are with respect to the edge-weight law and, when
relevant, the auxiliary private randomness.

\part{Differentiability for Gamma weights}
\label{part:differentiability}

We fix a single Gamma law $\operatorname{Gamma}(\kappa,\lambda)$ with
$\kappa,\lambda>0$ and prove Theorem~\ref{thm:gamma-differentiability}
for it. Nothing in this part uses $\kappa=1$; the exponential case is
covered by the same argument. Write $\mu=\mu_{\kappa,\lambda}$. All
constants and scale thresholds in this part may depend on the fixed
law but on no other parameter unless explicitly subscripted.

\section{Shape estimates and supporting functionals}
\label{df:sec:setup}

\subsection{The shape theorem and elementary Gamma moments}

We use the shape theorem of Krishnan--Rassoul-Agha--Sepp\"al\"ainen
\cite{KRS23}, in the following standard form.

\begin{lemma}[Uniform shape theorem]
\label{lem:shape-theorem}
For the fixed Gamma law there is a deterministic norm $\mu$ on
$\R^2$ such that, almost surely,
\begin{equation}
  \sup_{z\in\Z^2:\ |z|\ge R}\frac{|T(0,z)-\mu(z)|}{|z|}
    \longrightarrow 0\qquad(R\to\infty).
  \label{df:eq:uniform-shape}
\end{equation}
Moreover, there are constants $0<\alpha\le\beta<\infty$ with
$\alpha|z|\le\mu(z)\le\beta|z|$ for all $z$.
\end{lemma}

\begin{proof}[Sketch]
This is \cite[Theorem~A.1 and equation~(A.3)]{KRS23} at weight shift
zero. Its hypotheses are: essential infimum of the law is zero, no
atom at zero, and second moment of the minimum of four independent
edge weights finite. For $\operatorname{Gamma}(\kappa,\lambda)$ all
three hold: the density is positive near $0$, vanishes nowhere, and
for independent copies $\tau_1,\dots,\tau_4$,
\[
  \E\bigl[\min\{\tau_1,\tau_2,\tau_3,\tau_4\}^2\bigr]\le\E\tau_1^2
  =\frac{\kappa(\kappa+1)}{\lambda^2}<\infty.
\]
The cited theorem is stated with $\ell^1$ distance; equivalence of
norms converts it to the Euclidean form above. The bounds on $\mu$
are elementary from the same convergence.
\end{proof}

Almost surely every edge weight is finite and positive, since there
are only countably many edges. Consequently loop erasure does not
increase cost: for any finite path there is a simple subpath with
the same endpoints and no greater cost.

\begin{lemma}[Gamma exponential moments]
\label{df:ga:moment}
Let $\tau\sim\operatorname{Gamma}(\kappa,\lambda)$ and $\theta<\lambda$.
Then $\E e^{\theta\tau}=(\lambda/(\lambda-\theta))^{\kappa}$. More
usefully, if $V$ is the sum of edge weights over $M$ distinct edges
with $M\le Av$ for $A,v>0$, then
\begin{equation}
  \PP\Bigl(V>\frac{2A\kappa}{\lambda}v\Bigr)
    \le e^{-A\kappa(1-\log 2)v}.
  \label{df:eq:gamma-sum-tail}
\end{equation}
\end{lemma}

\begin{proof}
The moment identity is a substitution $y=(\lambda-\theta)t$ in the
Gamma integral. At $\theta=\lambda/2$ it reads
$\E e^{\lambda\tau/2}=2^{\kappa}$. Independence of the weights and the
exponential Markov inequality give
\[
  \PP\Bigl(V>\tfrac{2A\kappa}{\lambda}v\Bigr)
  \le e^{-A\kappa v}\cdot 2^{\kappa M}\le e^{-A\kappa(1-\log 2)v},
\]
since $\kappa M\le\kappa A v$.
\end{proof}

\subsection{The two extreme supports}

Signed coordinate permutations preserve the law and hence $\mu$
together with $\Bcal$. Combined with positive homogeneity, they
reduce differentiability and strict-convexity questions to directions
$u=(1,b)$ with $-1\le b\le1$; the remaining directions are obtained
by permuting coordinates and flipping signs.

Fix once and for all such a $b$, and set
\[
  x(z) = z_1,\qquad r(z) = z_2 - b z_1,\qquad m_0=\mu(u)>0.
\]
So $x$ is the longitudinal coordinate along $u$ and $r$ is the
transverse coordinate. Because $t\mapsto\mu(u+te_2)$ is convex and
finite, the one-sided transverse derivatives
\[
  a_- = \lim_{t\uparrow0}\frac{\mu(u+te_2)-m_0}{t},\qquad
  a_+ = \lim_{t\downarrow0}\frac{\mu(u+te_2)-m_0}{t}
\]
exist, are finite, and satisfy $a_-\le a_+$. Define
\begin{equation}
  f_\pm(z) = m_0 x(z)+a_\pm r(z),\quad
  a = \tfrac{a_-+a_+}{2},\quad c = \tfrac{a_+-a_-}{2},\quad
  f(z) = m_0 x(z)+a r(z).
  \label{df:eq:support-definitions}
\end{equation}
The linear functionals $f_-,f_+,f$ are the two extreme supports at
$u$ and their average.

\begin{lemma}[One-sided contact]
\label{df:prelim:supports}
The functionals $f_-,f_+,f$ are all bounded above by $\mu$ on
$\R^2$ and equal $\mu$ at $u$. For $\sigma\in\{-,+\}$,
\[
  \mu(u+te_2)-f_\sigma(u+te_2)=o(|t|)\qquad(t\to0,\ \sigma t>0).
  \label{df:eq:support-contact}
\]
\end{lemma}

\begin{proof}
Each of $a_-,a_+$ is a subgradient at $0$ of the convex function
$t\mapsto\mu(u+te_2)$. If $x(z)>0$, write
$z=x(z)\cdot(u+r(z)x(z)^{-1}e_2)$ and use positive homogeneity to get
$f_\sigma(z)\le\mu(z)$. If the inequality failed at another $z$, a
suffficiently small positive convex combination of $z$ and $u$ would
still violate it by convexity and would have positive first
coordinate, contradicting the preceding case. The average $f$ obeys
the same bound. Equation~\eqref{df:eq:support-contact} is the
one-sided derivative expansion.
\end{proof}

\subsection{Path defects}

For any finite path $P$ define the {\em defect}
\[
  H(P) = \tau(P) - f(\Delta P),\qquad
  H_\sigma(P) = \tau(P) - f_\sigma(\Delta P).
  \label{df:eq:defects}
\]
These are additive under concatenation. A path with $H(P)<0$ is
cheaper than the average support would allow, so if the shape
theorem holds, paths with $H(P)<0$ cannot coast forever. The
algebraic identity
\begin{equation}
  \min\{H_+(P),H_-(P)\} = H(P) - c\,|r(\Delta P)|
  \label{df:eq:minimum-defect}
\end{equation}
expresses the {\em gap} $c$: a path that moves transversely cheaply
must beat one of the extreme supports.

\section{Localized crossings}
\label{df:sec:crossings}

Throughout this section, distances are Euclidean unless stated
otherwise. A path {\em confined to a region} $A$ means all its
vertices lie in $A$, and only edges with both endpoints in $A$ are
tested.

The main estimate of the section is Lemma~\ref{df:cr:rare-fast}: a
crossing confined to a long strip of width $s$ is unlikely to save
$\eps s$ worth of defect over one of the extreme supports, provided
its length is much larger than $s$. The proof amplifies any positive
probability of such a crossing into an infinite concatenation whose
defect grows linearly negative, contradicting the shape theorem.

\subsection{Localized travel}

\begin{lemma}[Localized travel]
\label{df:cr:local-travel}
Fix $D,\eta,\delta>0$. Uniformly over deterministic vertices
$p,q\in\Z^2$ with $|q-p|\le Ds$, the probability tends to one as
$s\to\infty$ that there is a path from $p$ to $q$ with cost at most
$\mu(q-p)+\eta s$ and all vertices within Euclidean distance
$\delta s$ of the segment $[p,q]$.
\end{lemma}

\begin{proof}
The uniform shape theorem, applied at points $z$ with
$|z|\le Cs$, gives the almost-sure limit
\begin{equation}
  \frac1s\max_{|z|\le Cs}|T(0,z)-\mu(z)|\to0.
  \label{df:eq:cr-uniform-shape}
\end{equation}
Indeed, outside any fixed ball the error is $o(|z|)$ by the shape
theorem, and inside the ball there are finitely many times that
contribute $o(s)$. The shape theorem also gives, for any fixed
$M>0$,
\[
  \PP\Bigl(\inf_{|z|\ge Ms}T(0,z)\ge\alpha M s/2\Bigr)\to1,
\]
directly from the almost-sure linear-growth behaviour with the norm
lower bound $\mu(z)\ge\alpha|z|$.

Choose a fixed integer $B\ge1$ large enough that
$\beta D/B<\alpha\delta/24$, and round the $B+1$ equally spaced
points of $[p,q]$ to vertices $p=p_0,p_1,\dots,p_B=q$. Then
\[
  \mu(p_{j+1}-p_j) = \frac{\mu(q-p)}{B}+O(1),
\]
uniformly in $p,q$. Apply \eqref{df:eq:cr-uniform-shape} and the
escape bound above at each $p_j$. With probability tending to one
uniformly in $p,q$, every short passage time satisfies
\[
  T(p_j,p_{j+1})\le\frac{\mu(q-p)}{B}
    +\min\Bigl\{\frac{\eta}{2B},\frac{\alpha\delta}{24}\Bigr\}s,
\]
and any path from $p_j$ leaving the ball of radius $\delta s/3$ costs
at least $\alpha\delta s/6$. Concatenate paths from $p_j$ to
$p_{j+1}$ with cost $\le T(p_j,p_{j+1})+1$. For large $s$ each path
costs less than the escape bound, so it must stay inside its starting
ball of radius $\delta s/3$. Summing over $j$, the total cost is at
most
\[
  \mu(q-p)+\eta s/2 + B\le\mu(q-p)+\eta s
\]
for large $s$, and the path lies within $\delta s$ of the segment.
\end{proof}

\begin{lemma}[Travel between intervals]
\label{df:cr:interval-travel}
Fix $D,\eta,\delta>0$. Let $I_1,I_2$ be deterministic vertical
intervals of consecutive lattice vertices whose union has diameter at
most $Ds$. Uniformly in their locations, with probability tending to
one, every $p\in I_1\cap\Z^2$, $q\in I_2\cap\Z^2$ can be joined by a
path of cost at most $\mu(q-p)+\eta s$ confined to the $\delta s$
neighbourhood of $[p,q]$.
\end{lemma}

\begin{proof}
Let $\beta$ be the norm upper bound. Pick small $\gamma>0$ with
$(4\kappa/\lambda+2\beta)\gamma\le\eta/2$ and $\gamma\le\delta/2$.
In each interval $I_j$ choose a net of vertices including its
extreme lattice vertices with consecutive gaps at most
$\lfloor\gamma s\rfloor$. There are at most $2D/\gamma+2$ net vertices
per interval. Assign each interval vertex to its nearest net vertex
(vertical distance at most $\gamma s$). For a gap with $V$ the sum of
at most $\lfloor\gamma s\rfloor$ independent edge weights,
Lemma~\ref{df:ga:moment} with $A=\gamma$, $v=s$ yields
\[
  \PP(V>2\kappa\gamma s/\lambda)\le e^{-\kappa(1-\log2)\gamma s}.
\]
There are only boundedly many gaps, so with probability tending to
one all vertical attachments cost at most $2\kappa\gamma s/\lambda$.
Apply Lemma~\ref{df:cr:local-travel} with errors $\eta/2$ and
$\delta/2$ to every pair of net vertices; the uniformity of that
lemma and the bounded number of pairs make this simultaneous.

On the intersection event, join $p$ to its net vertex, that to the
net vertex of $q$, and that to $q$. The cost is at most
\[
  \mu(q-p)+\eta s/2+4\kappa\gamma s/\lambda+\beta\gamma s
  \le\mu(q-p)+\eta s.
\]
The segments $[p,q]$ and $[\hat p,\hat q]$ have Hausdorff distance at
most $\gamma s$, so the path is inside the $\delta s$-tube of
$[p,q]$. The same event works for every $p\in I_1$, $q\in I_2$, and
the probability bound is uniform in the locations.
\end{proof}

\subsection{Oriented percolation}

We will place local tests on an auxiliary copy of $\Z^2$. The
following elementary lemma is the only probabilistic input about
oriented paths we need.

\begin{lemma}[High-density oriented paths]
\label{df:cr:oriented-paths}
For every integer $k_0\ge0$ there is $\zeta=\zeta(k_0)>0$ with the
following property. Let $(G_v)_{v\in\Z^2}$ be events such that any
finite subfamily indexed by sites at pairwise sup-distance greater
than $k_0$ is independent. If $\PP(G_v^c)\le\zeta$ for every $v$,
then with positive probability there is an infinite path starting
at $0$ using steps $(1,0)$ and $(0,1)$ whose sites all satisfy
$G_v$.
\end{lemma}

\begin{proof}
Say a site is {\em good} if $G_v$ holds. Let $S$ be the set of
endpoints of finite oriented paths from $0$ all of whose sites except
possibly the last are good. If $S$ is infinite, the finitely-branching
tree of such paths has an infinite branch, giving an infinite good
path. Hence if no infinite good path exists, $S$ is finite.

Assume $S$ finite. Orient the boundaries of the unit squares
centered at $S$ counterclockwise and cancel shared sides. The
remaining directed edges form a balanced directed graph
decomposing into closed directed trails; corner contacts cause no
difficulty. Each edge has an $S$-square on its left and a
complementary square on its right. Winding number is additive under
cancellation and decomposition. The total winding number about $0$ is
one (contributed by the square at $0$), so some trail has nonzero
winding; let its length be $m$.

For a closed trail of length $m$, exactly $m/2$ steps are upward or
leftward; for these steps the right-hand site is an east or north
neighbor of the left-hand site. Since the left-hand site borders an
$S$-square whose right-hand site is not in $S$, the left-hand site
must be {\em bad}. A site borders at most four edges of the trail, so
at least $m/8$ distinct sites are forced bad. Greedy selection among
them in a fixed order retains at least
\[
  m/[8(2k_0+1)^2]
\]
sites at pairwise sup-distance greater than $k_0$. Their tests are
independent, so for this specific trail the probability of all
forced-bad conditions is at most
$\zeta^{m/[8(2k_0+1)^2]}$.

A nonzero-winding trail has $0$ in its coordinate bounding box, so
its span in coordinates is at most $m$ in each direction. The number
of candidate trails of length $m$ with nonzero winding is at most
$C(m+1)^2\cdot 4^m$. Summing,
\[
  \PP(\text{no infinite good path})
  \le \sum_{m\ge4} C(m+1)^2
     \bigl(4\zeta^{1/[8(2k_0+1)^2]}\bigr)^m<1
\]
provided $\zeta$ is small enough.
\end{proof}

\subsection{Rare fast localized crossings}

\begin{lemma}[Rare fast localized crossings]
\label{df:cr:rare-fast}
Fix $A,R,\eps>0$ and $\sigma\in\{-,+\}$. As $s\to\infty$ and
$n/s\to\infty$ with $s$ real and $n$ a positive integer,
\begin{equation}
  \PP\left(\begin{array}{l}
    \text{there is a path }P\text{ from }x=0\text{ to }x=n\text{ with}\\
    H_\sigma(P)<-\eps s\text{ and all vertices in}\\
    -An\le x\le(1+A)n,\quad |r|\le Rs
  \end{array}\right)\longrightarrow 0.
  \label{df:eq:cr-rare-fast}
\end{equation}
The same holds for exact lattice translations of the event.
\end{lemma}

\begin{proof}
Suppose the probability is at least $p_0>0$ along a sequence with
the stated limits. We will amplify this into an infinite path of
negative defect, contradicting the shape theorem.

\emph{Parameters.} Choose a fixed $k_0\ge\lceil 4(A+3)+8\rceil+1$
and let $\zeta=\zeta(k_0)$ come from
Lemma~\ref{df:cr:oriented-paths}. Pick $M$ so large that
$(1-p_0)^M<\zeta/2$. For each member of the sequence put
$S_0=100M(R+1)\lceil s\rceil$ and $d=\lceil D_0 s\rceil$ (a fixed
constant $D_0$ is chosen below).

\emph{Trials at each site.} Identify signs with numbers. For
$v=(v_1,v_2)$ put $i=v_1+v_2$, $X_i=i(n+d)$, and
$Y_v=\sigma(i+v_2)S_0$. Along an oriented step from $v$ to a forward
neighbor $v'$, the value of $i$ increases by one and $Y$ increases by
$\sigma S_0$ or $2\sigma S_0$. Take $M$ exact lattice translates of
the event \eqref{df:eq:cr-rare-fast} with starting column $X_i$ and
with their $R$-strips disjoint and inside $\{|r-Y_v|\le S_0/4\}$.
Specifically, put
$h_j=(2j-M-1)\,3(R+1)\lceil s\rceil$ and
\[
  t_{v,j}=\bigl(X_i,
    \lfloor bX_i+Y_v+h_j+\tfrac12\rfloor\bigr),\qquad 1\le j\le M.
\]
Consecutive trial centers are separated by more than $2Rs$, so each
trial's strip is disjoint. Translation invariance gives each trial
probability at least $p_0$; the probability all $M$ fail is at most
$(1-p_0)^M$.

\emph{Connection tests.} For each forward neighbor $v'$ of $v$,
additionally require that every vertex with
$x=X_i+n$, $|r-Y_v|\le S_0/4$ be joined to every vertex with
$x=X_{i+1}$, $|r-Y_{v'}|\le S_0/4$ by a path of cost
$f_\sigma$ of its displacement plus $\eps s/2$, confined to
\begin{equation}
  X_i+n-s\le x\le X_{i+1}+s,\qquad |r-Y_v|\le4S_0.
  \label{df:eq:cr-connector-region}
\end{equation}
Requiring all endpoint pairs allows trials to be chosen after
observing the environment.

\emph{Choosing $D_0$.} A connector has displacement $z$ with
$x(z)=d$ and $S_0/2\le\sigma r(z)\le 3S_0$. Set $C_0=200M(R+1)$, so
$S_0/s\le C_0$ for $s\ge1$. The one-sided contact
\eqref{df:eq:support-contact} supplies $h_0>0$ such that
\[
  0\le\mu(u+he_2)-f_\sigma(u+he_2)\le\frac{\eps}{12C_0}|h|
  \qquad(0<\sigma h\le h_0).
\]
Pick $D_0\ge1$ with $3C_0/D_0\le h_0$. For every connector,
$0<\sigma r(z)/d\le h_0$, so by homogeneity
\[
  \mu(z)-f_\sigma(z)\le\frac{\eps}{12C_0}|r(z)|\le\eps s/4.
\]
Apply Lemma~\ref{df:cr:interval-travel} with $D$ from the
diameter of $I_1\cup I_2$, $\eta=\eps/2$, $\delta$ any fixed small
number, to get the connector bounds simultaneously for all endpoint
pairs on one event of probability tending to one.

\emph{Dependence radius.} Call $v$ good if at least one trial
succeeds and both connection tests pass; bad probability at most
$(1-p_0)^M+o(1)$. The test at $v$ is supported on internal edges in
$|x-X_i|\le(A+3)n$, $|r-Y_v|\le4S_0$. If two sites' support regions
share a vertex, then in $(i,j)$ coordinates the difference satisfies
\[
  |\Delta i|\le 2(A+3),\quad |\Delta j|\le 8,
  \qquad|\Delta v_2|\le2(A+3)+8,\quad
  |\Delta v_1|\le4(A+3)+8<k_0.
\]
So tests at sites at pairwise distance greater than $k_0$ are
independent, uniformly in later choices of $M$ and $D_0$.

\emph{Concatenation.} By Lemma~\ref{df:cr:oriented-paths} there is
positive probability of an infinite oriented path of good sites
starting at $0$. Fix one such configuration. At each site pick a
successful trial and connect it to the next by a tested connector.
If $z_t$ is the endpoint of the $t$-th trial, then
\[
  H_\sigma(\text{path to }z_t)\le C-(t+1)\eps s+t\cdot\eps s/2
  = C-(t+1)\eps s/2,
\]
where $C$ is the finite defect of the path from the lattice origin to
the initial trial. In particular
$x(z_t)=t(n+d)+n$ and $|z_t|=O(t)$ uniformly in $t$. The shape
theorem (applied to these adaptively chosen endpoints, whose
existence is measurable in the environment) gives
\[
  T(0,z_t)\ge\mu(z_t)-o(t)\ge f_\sigma(z_t)-o(t),
\]
contradicting $H_\sigma<0$ with $\eps s>0$ fixed and $t\to\infty$.
So no offending sequence exists, proving the assertion. Translation
invariance gives the same for exact lattice translates.
\end{proof}

\section{Characteristic lengths}
\label{df:sec:scales}

\subsection{The first crossing threshold}

Set $K=100(1+|a_-|+|a_+|)$. For real $s\ge1$ and integer $n\ge1$,
let $E(s,n)$ be the event that there is a finite path $P$ from the
column $x=0$ to the column $x=n$, staying in
\[
  \{-n\le x\le2n,\ |r|\le8s\},
\]
with $\tau(P)<m_0 n+Ks$.

\begin{lemma}[Rarity at cubic length]
\label{df:gr:tilt}
With $s=2^k$ and $k\to\infty$,
$\PP(E(s,s^3))\to0$.
\end{lemma}

\begin{proof}
\emph{Change of measure.} Put $n=s^3$. Choose a fixed $\eta>0$
with $\eta m_0>K+16|a_+|+1$. Set $\delta=\eta s/n$ and
$\alpha=1-\delta$; for large $s$, $0<\delta\le1/2$. Multiply the
weight of every edge internal to the region defining $E(s,n)$ by
$\alpha$, leaving all other weights unchanged. Let $\QQ$ be the
new law. If $P$ witnesses $E(s,n)$ under $\PP$, then in the
modified environment, using $|r(\Delta P)|\le16s$,
\[
  H_+(P)
  <\alpha(m_0 n+Ks)-m_0 n-a_+r(\Delta P)
  \le (K-\eta m_0+16|a_+|)s - \eta K\frac{s^2}{n}<-s.
\]
Let $F(s,n)$ be the event in the region that some path has
$H_+(P)<-s$. Then $\PP(E(s,n))\le \QQ(F(s,n))$.

\emph{Likelihood ratio.} Under $\QQ$, a modified edge is
$\operatorname{Gamma}(\kappa,\lambda/\alpha)$ with density
$p_{\kappa,\lambda/\alpha}$, so its likelihood ratio to the original
law is
\[
  L_\delta(t)=\frac{p_{\kappa,\lambda/\alpha}(t)}{p_{\kappa,\lambda}(t)}
   =\alpha^{-\kappa}\exp\{-\lambda(\alpha^{-1}-1)t\}
\]
on $t>0$. A direct integration gives
\[
  \E[L_\delta(\tau)^2]
  =\alpha^{-2\kappa}(2/\alpha-1)^{-\kappa}
  =\bigl(\alpha(2-\alpha)\bigr)^{-\kappa}=(1-\delta^2)^{-\kappa}.
\]
The region has at most $(3n+1)(16s+2)$ vertices and at most twice as
many internal edges; call this number $M_e$ and note
$M_e\le144ns$. The likelihood is a product over distinct edges, so
independence gives
\[
  \E\Bigl[\bigl(\tfrac{d\QQ}{d\PP}\bigr)^2\Bigr]
  =(1-\delta^2)^{-\kappa M_e}
  \le\exp(2\kappa M_e\delta^2)\le e^{288\kappa\eta^2}.
\]

\emph{Transfer back.} Cauchy--Schwarz and
Lemma~\ref{df:cr:rare-fast} under $\PP$ with $A=1$, $R=8$, $\eps=1$,
since $n/s=s^2\to\infty$, yield
\[
  \PP(E(s,n))\le\QQ(F(s,n))
  \le e^{144\kappa\eta^2}\PP(F(s,n))^{1/2}\longrightarrow0.\qedhere
\]
\end{proof}

\subsection{Characteristic lengths}

Fix any threshold $q_0\in(0,1)$; it will be chosen small later. Write
$s_k=2^k$.

\begin{lemma}[Characteristic lengths]
\label{df:gr:characteristic-lengths}
For every fixed $C>0$,
$\PP(E(s,n))\to1$ as $s\to\infty$ with $1\le n\le Cs$, $n\in\N$.
Consequently there is $k_0\ge0$ such that for every $k\ge k_0$ the
first dyadic $L_k\in\{1,2,4,\dots\}$ with $\PP(E(s_k,L_k))\le q_0$
exists and satisfies
\begin{equation}
  L_k\le s_k^3=2^{3k},\qquad L_k/2^k\to\infty.
  \label{df:eq:gr-characteristic-bounds}
\end{equation}
Moreover every dyadic $l<L_k$ satisfies $\PP(E(s_k,l))>q_0$.
\end{lemma}

\begin{proof}
\emph{Short crossings are likely.} Suppose $n\to\infty$ with $n\le Cs$.
Put $q=(n,\lfloor bn\rfloor)$. Then
$\mu(q)\le m_0 n+\mu(e_2)$ and $-1<r(q)\le0$. Apply
Lemma~\ref{df:cr:local-travel} at scale $n$ with endpoints $0,q$,
cost error $\eta n$ for $\eta=K/(4C)$, and tube radius $\delta_0 n$
with $0<\delta_0\le\min\{1/4,1/(2C)\}$. The endpoints have Euclidean
distance at most $3n$. Since $|b|\le1$, changing a point by
Euclidean distance $t$ changes $r$ by at most $\sqrt2 t$; the tube
sits inside $-n\le x\le2n$ and $|r|\le 1+\sqrt2\delta_0 n\le8s$ for
large $s$. With probability tending to one the path costs at most
$m_0 n+\mu(e_2)+\eta n\le m_0 n+\mu(e_2)+Ks/4<m_0 n+Ks$.

If $n$ remains bounded, direct lattice paths use a bounded number of
edges inside a bounded transverse strip. Their costs are bounded in
probability, while $Ks\to\infty$. By the subsequence criterion,
$\PP(E(s,n))\to1$ uniformly in small $n$ too.

\emph{Existence of $L_k$.} Lemma~\ref{df:gr:tilt} gives
$\PP(E(s_k,s_k^3))\to0$; for large $k$ the threshold $s_k^3$ is above
$q_0$, so the first dyadic $L_k$ exists. If $L_k/2^k$ failed to tend
to infinity, a subsequence with $L_k\le C2^k$ would contradict
$\PP(E(s_k,L_k))>q_0$-at-$L_k/2$ for every fixed $C$. The last
assertion is by definition of the {\em first} dyadic length fixing
the threshold.
\end{proof}

\subsection{Record subsequence}

The sequence $L_k$ need not be monotone. We only need lower bounds
for earlier lengths on an infinite subsequence.

\begin{lemma}[Record scales]
\label{df:gr:record-scales}
There is an infinite subset $\mathcal K\subset\{k_0,k_0+1,\dots\}$
such that for every $k\in\mathcal K$ and every $0\le j\le k-k_0$,
\[
  L_{k-j}\ge 2^{-4j}L_k.
  \label{df:eq:gr-record-comparison}
\]
\end{lemma}

\begin{proof}
The positive sequence $L_k 2^{-4k}$ is at most $2^{-k}$, hence tends
to $0$, so its strict local minima occur at infinitely many $k$.
Take these as $\mathcal K$; at a record $k$ the inequality
$L_k 2^{-4k}\le L_{k-j}2^{-4(k-j)}$ rearranges to
\eqref{df:eq:gr-record-comparison}.
\end{proof}

Henceforth $k$ tends to infinity through $\mathcal K$, and we write
$s=2^k$, $L=L_k=2^m$ with $m\le3k$ and $m-k\to\infty$.

\section{Endpoint extensions}
\label{df:sec:grids}

The bounds so far involve a strip of width $s$ around one of the
extreme supports. To get a statement about every long path from the
origin, we must upgrade them to arbitrary endpoints chosen after the
environment is inspected. Routine union bounds over polynomially many
pairs are not enough, because the path has exponentially many
possible endpoint itineraries.

The upgrade uses two ingredients. A deterministic net of grid columns
at which we can cross cheaply (Lemma~\ref{df:gr:grid-tools}); and a
geometric retraction of any path endpoint onto that net, keeping the
transverse coordinate within $1$ (Lemma~\ref{df:gr:variable-endpoints}).

For this section put $w_j=2^{-2j}s$ and $l_j=2^{-4j}L$ for $j\ge1$.

\begin{lemma}[Simultaneous grid connections]
\label{df:gr:grid-tools}
There is a constant $C_1$, independent of $A,R,J,j,k$, and for each
fixed $A,R$ a sequence $\beta_J\to0$ such that, for every fixed
$J\ge1$ and every large enough $k\in\mathcal K$, there is an event
$G_{k,J}$ with $\PP(G_{k,J}^c)\le\beta_J$ on which the following
holds simultaneously. For every level $J\le j\le j_*$, every grid
interval
\[
  [X,X+l_j]\subset[-(A+4)L,(A+4)L],\qquad X\in l_j\Z,
\]
every real $r_0$ with $|r_0|\le Rs$, and every pair of lattice
vertices $p,q$ on the left and right endpoint columns of $X$ with
$|r(p)-r_0|\le1$, $|r(q)-r_0|\le1$, there is a path from $p$ to $q$
with cost at most
\begin{equation}
  m_0 l_j+C_1 j^2 w_j,
  \label{df:eq:gr-grid-cost}
\end{equation}
whose vertices satisfy
\begin{equation}
  X-l_j\le x\le X+2l_j,\qquad |r-r_0|\le C_1 j^2 w_j.
  \label{df:eq:gr-grid-localization}
\end{equation}
One may take $C_1=K+200\kappa/\lambda$.
\end{lemma}

\begin{proof}
\emph{Exact lattice crossing trials.} Let $q_0$ be the threshold in
Lemma~\ref{df:gr:characteristic-lengths}. Recentering that lemma
around an arbitrary lattice translate of the columns $x=0$ and $x=l$,
every integer $l<L_k$ satisfies
\[
  \PP(E_{\mathrm{shifted}}(s,l)^c)\le1-q_0
\]
uniformly in the shift. For large $k$ and $j\ge J$ the integer
$l=l_j$ is dyadic and $<L_j$, hence $<L_k$.

\emph{Independent parallel trials.} Bin $r_0\in[hw_j,(h+1)w_j]\cap[-Rs,Rs]$,
and for each bin make $j^2$ trials using exact lattice translates of
the recentered $E(s,l)$ by
\[
  v_t = \bigl(X,\lfloor bX\rfloor+(h+30t)w_j\bigr),\qquad 1\le t\le j^2.
\]
Here $w_j$ is an integer, so $v_t$ is a lattice vector. The
transverse centers of the trial strips are
\[
  r(v_t)=\lfloor bX\rfloor-bX+(h+30t)w_j.
\]
The lattice phase contributes the same offset of absolute value less
than $1$ to each, and consecutive centers differ by exactly
$30w_j$; each strip has half-width $8w_j$, so trial vertex sets and
internal edge sets are disjoint. Each trial is an exact lattice
translate with the same probability as $E(s,l)$, so all trials fail
with probability at most
\begin{equation}
  (1-q_0)^{j^2}\le e^{-c j^2}.
  \label{df:eq:gr-trial-probability}
\end{equation}

\emph{Vertical attachments for every endpoint.} On each of the two
columns $x=X$ and $x=X+l_j$, consider the deterministic vertical
interval of vertices with
\[
  hw_j-2\le r\le hw_j+(30j^2+9)w_j+2.
\]
It contains every vertex with transverse coordinate within $1$ of the
chosen bin and every possible trial endpoint. There are at most
$50j^2w_j$ internal vertical edges. If $V$ is their total weight, the
Gamma moment tail \eqref{df:eq:gamma-sum-tail} with $A=50$ and
$v=j^2w_j$ gives
\[
  \PP\bigl(V>100\kappa j^2 w_j/\lambda\bigr)
  \le e^{-c_0 j^2 w_j},\qquad
  c_0=50\kappa(1-\log2)>0.
\]
Except with this probability, vertical travel between any vertices of
either interval costs at most $100\kappa j^2 w_j/\lambda$.

\emph{Assembling the connection.} If a trial succeeds and both
vertical bounds hold, join $p$ vertically to the trial's left
endpoint, follow the trial, and join its right endpoint vertically to
$q$. The total cost is at most
\[
  m_0 l_j+Kw_j+200\kappa j^2 w_j/\lambda
  \le m_0 l_j+C_1 j^2 w_j,
\]
with $C_1=K+200\kappa/\lambda$. The path stays in
$[X-l_j,X+2l_j]$ and within $50j^2w_j$ transversally of every $r_0$
in the bin. The constants absorb the $j^2$ factor into a fixed $C_1$
through a redefinition; the trial count $j^2$ is finite in $j$-level
union bounds below.

\emph{Simultaneous over the grid.} A union bound over $O(L/w_j)$
bin-and-shift classes multiplies the failure probability by a
polynomial in $k$; the trial failure $e^{-cj^2}$ and the vertical
failure $e^{-c_0 j^2 w_j}$ both dominate any polynomial factor in $k$
for $j\ge J$. Enlarging $C_1$ by a fixed amount yields
$\PP(G_{k,J}^c)\le\beta_J\to0$ as $J\to\infty$.
\end{proof}

\begin{lemma}[Connecting every endpoint to the grid]
\label{df:gr:variable-endpoints}
Fix $A,R>0$. There is a sequence $\delta_J\to0$ such that, on an event
of probability at least $1-\delta_J$, for every vertex $z\in\Z^2$
with $x(z)\in[-(A+2)L,(A+2)L]$ and $|r(z)|\le Rs$, and every level
$J\le j\le j_*$, there are:
\begin{enumerate}
  \item a path $P_z^-$ from the column $X_p^-\le x(z)$ to $z$ with
    $X_p^-\ge x(z)-l_J$, cost
    $\le m_0(x(z)-X_p^-)+C_1\sum_{j\ge J}j^2 w_j$, and vertices
    inside \eqref{df:eq:gr-grid-localization};
  \item a path $P_z^+$ from $z$ to a column $X_p^+\ge x(z)$ with
    $X_p^+\le x(z)+l_J$ and the same cost and region bounds.
\end{enumerate}
\end{lemma}

\begin{proof}
Decompose $[X_p^-,x(z)]$ by one full interval of length $l_J$ followed
by greedily finer meshes; there are at most $16$ intervals of each
level, by the ratio bound $16$. At every integer column $X$ that
occurs, use the vertex $z_p(X)=(X,\lfloor bX+r(p)\rfloor)$. It satisfies
$|r(z_p(X))-r(p)|<1$ and $z_p(x(p))=p$. Apply
Lemma~\ref{df:gr:grid-tools} with the same transverse target
$r_0=r(p)$ on every interval, and concatenate. The exit $P_p^+$ is
symmetric. Summing the per-level errors $C_1 j^2 w_j$ over $j\ge J$
gives a convergent series; its tail is $\delta_J$-small.
\end{proof}

\section{Witnesses and the no-corner theorem}
\label{df:sec:witnesses}

We now prove Theorem~\ref{thm:gamma-differentiability}. The argument
is by contradiction: if $\mu$ is not differentiable at $u$, the gap
$c$ in \eqref{df:eq:minimum-defect} is positive, and we produce a
positive slope for $H(P)/x(P)$ on every simple path from the origin.
That contradicts the shape theorem along $u$.

\subsection{A continuous BK inequality}

We need a version of the BK inequality for events defined by a path
that uses a given set of edges. The original BK inequality
\cite{BK85} is finite; the extension to countable product spaces is
\cite{AGH2018}.

\begin{lemma}[Finite Bernoulli BK]
\label{df:wi:bk}
On a finite product of Bernoulli variables, let $A_1,\dots,A_q$ be
increasing events with positive disjoint occurrence, meaning that
disjoint sets of variables can simultaneously certify all of them.
Then
\[
  \PP(A_1\circ A_2\circ\cdots\circ A_q)
  \le\prod_{i=1}^q\PP(A_i).
\]
\end{lemma}

\begin{proof}
This is \cite[Theorem~3.3, Equation~(3.4)]{BK85}; monotone disjoint
occurrence is associative, so iteration covers repeated events.
\end{proof}

\begin{lemma}[Continuous BK]
\label{df:wi:continuous-bk}
Let $(\tau_e)$ be independent Gamma variables on the countable edge
set of $\Z^2$. For $j=1,\dots,q$, let $A_j$ be a decreasing event
that depends only on the edge set of the path taken. That is, $A_j$
holds for a path if some witness path of edges $\pi_j$ has
$\tau(\pi_j)<\beta_j$ for a deterministic threshold $\beta_j$, and
$A_j$ is the event that such a path exists within a prescribed
edge set. Then
\[
  \PP(\{A_1,\dots,A_q\text{ occur on edge-disjoint witnessing paths}\})
  \le\prod_{j=1}^q\PP(A_j).
\]
\end{lemma}

\begin{proof}
Fix a precision $t>0$ and round every edge weight from above to a
dyadic grid: $\tau_e^{(t)}=\lceil 2^t\tau_e\rceil/2^t$. Continuity of
$\tau\mapsto\{\text{a witness exists}\}$ gives
$\tau_e^{(t)}\downarrow\tau_e$ almost surely on the finite union of
edge sets involved. Define $A_j^{(t)}$ and $D^{(t)}$ from the rounded
weights.

At each fixed precision the $A_j^{(t)}$ are decreasing events of
finitely many independent bits. Fixing all precision-$t$ bits of a
witnessing path's edges forces the strict cost inequality regardless
of the other bits; edge-disjoint path witnesses give disjoint bit
certificates. Complement every bit to convert to increasing events.
Retain realized one-bits of each certificate and set all other bits to
zero; disjointness of certificates is preserved. The finite Bernoulli
BK inequality, iterated over the list, yields
\[
  \PP(D^{(t)})\le\prod_{j=1}^q\PP(A_j^{(t)}).
\]
The monotone limit $\tau^{(t)}\downarrow\tau$ gives
$\PP(A_j^{(t)})\le\PP(A_j)$ and $\PP(D^{(t)})\to\PP(D)$.
\end{proof}

\subsection{The block event and its witnesses}

Recall $s=2^k$ and $L=L_k=2^m$ with $m\le3k$ and $m-k\to\infty$;
all constants introduced below depend only on the fixed Gamma law.
For $(i,h)\in\Z^2$ put $v_{i,h}=(iL,\lfloor bhL\rfloor+hs)$, so
$r(v_{i,h})\in[0,1)$. Let $B_{i,h}$ be the rectangle set of vertices
with $x-iL\in[-2L,3L)$ and $|r-hs|<4s$.

For $(i,h)$ define $\Acal_{i,h}$ as the union of two increasing
events:
\begin{enumerate}
  \item there is a path $Q\subset B_{i,h}$ with one endpoint in
    $B_{i-1,h'}$, one endpoint in $B_{i+2,h'}$, and
    $\min_\sigma H_\sigma(Q)<-\eta s$;
  \item there is a path $Q\subset B_{i,h}$ from column $x=(i+1)L$ to
    $x=(i+2)L$ inside
    $\{(i+1)L\le x\le(i+2)L,\ |r-hs|\le8s\}$ with
    $\tau(Q)<m_0L+Ks$.
\end{enumerate}
These are localized versions of the two ``exceptional'' behaviors of
the chunk analysis below.

\begin{lemma}[Rare events at fixed scale]
\label{df:wi:rare-events}
There is $k$ arbitrarily large such that for every $(i,h)$,
\[
  \PP(\Acal_{i,h})\le2q_0.
  \label{df:eq:wi-rare-events}
\]
\end{lemma}

\begin{proof}
Event 1 is contained in a translate of
Lemma~\ref{df:cr:rare-fast} applied at scale $s$ with $n=L$,
$A=2$, $R=8$, hence has probability $o(1)$ since $L/s\to\infty$.

Event 2 is a translate of a subset of $E(s,L)$. The definition of $L$
gives $\PP(E(s_k',L))\le q_0$ whenever $s_k'\ge s$; combining
Lemma~\ref{df:gr:record-scales} with taking $n$ large along the
subsequence yields $\PP(E(s,L))\le q_0$ for our fixed $(s,L)$.

A union bound gives $\PP(\Acal_{i,h})\le2q_0$ uniformly in $(i,h)$,
by translation invariance.
\end{proof}

Fix this $k$ and enlarge it if necessary so that
\begin{equation}
  C_f:=\max\{|m_0-ab|,|a|\}\le\eta s,\qquad
  2m_0L-|a|(s+1)>\eta s,\qquad
  3\eta s+2|a|(s+1)<Ks.
  \label{df:eq:wi-deterministic-scale}
\end{equation}
These follow from $s\to\infty$, $L/s\to\infty$, and $\eta\le1$.
The scale $s$, $L$ now stay fixed; only path length $N$ grows below.

\subsection{Chunk decomposition of a path}

Let $P$ be a finite simple lattice path from the origin. Decompose
$P$ into chunks: at the start of a chunk, with current $(x_0,r_0)$,
follow the path until it first reaches a vertex with
$|x-x_0|\ge2L$ or $|r-r_0|\ge s$; cut there. A chunk ending at such
a cut is {\em full}. The decomposition consists of $N$ full chunks
and a remainder. For every chunk (including the remainder) associate
the index
\begin{equation}
  (i,h)=\bigl(\lfloor x_0/L\rfloor,\lfloor r_0/s\rfloor\bigr).
  \label{df:eq:wi-chunk-index}
\end{equation}

Every vertex of a chunk has $|x-x_0|\le2L$, $|r-r_0|\le s+1$, and
\[
  0\le x_0-iL<L,\qquad 0\le r_0-r(v_{i,h})<s+1,
\]
so the whole chunk lies in $B_{i,h}$.

\begin{lemma}[Cheap chunks supply witnesses]
\label{df:wi:chunk-witness}
Let $Q$ be a full chunk with index $(i,h)$ and $H(Q)<\eta s$. Then
some subpath of $Q$ witnesses $\Acal_{i,h}$.
\end{lemma}

\begin{proof}
Call the chunk's {\em exit} the first vertex at which the chunk was
cut. There are three cases.

\emph{Transverse exit.} If $|r(\Delta Q)|\ge s$, then
\eqref{df:eq:minimum-defect} gives
$\min_\sigma H_\sigma(Q)=H(Q)-c|r(\Delta Q)|<(\eta-c)s\le-3\eta s$
since $c>2\eta$ after shrinking $\eta$ once. This is Event 1.

\emph{Backward exit.} Suppose $x(\Delta Q)=-2L$. Then by
nonnegativity and \eqref{df:eq:wi-deterministic-scale},
$H(Q)\ge2m_0L-|a|(s+1)>\eta s$, contradicting the hypothesis.

\emph{Forward exit.} Suppose $x(\Delta Q)=2L$. Let $z$ be the first
vertex of $Q$ on column $(i+2)L$, $p$ the last on column $(i+1)L$
before $z$. The subpath $Q'$ from $p$ to $z$ stays between those
columns and has $|r-y_{i+1,h}|\le2s+2\le8s$, so it fits inside the
rectangle defining the second event of $\Acal_{i+1,h}$.

Write $Q=Q_{\rm in}*Q'*Q_{\rm out}$. If either $Q_{\rm in}$ or
$Q_{\rm out}$ has $H<-\eta s$, it witnesses Event 1 (whole-chunk case
with the same subpath). Otherwise $H(Q')<3\eta s$ by additivity.
Using $|r(\Delta Q')|\le2(s+1)$,
\[
  \tau(Q')<m_0L+3\eta s+2|a|(s+1)<m_0L+Ks,
\]
so $Q'$ witnesses Event 2.
\end{proof}

\subsection{Witness multiplicity}

For any chunk $Q$ with index $(i,h)$, let $M_Q$ be the maximum number
of pairwise edge-disjoint path witnesses for $\Acal_{i,h}$ whose
edges all lie inside $Q$. Each witness uses at least one edge, so
$M_Q$ is finite and at most $|Q|$.

\begin{lemma}[Defect bound by multiplicity]
\label{df:wi:chunk-defect}
Every chunk satisfies $H(Q)\ge-\eta s-2\eta s M_Q$. A full chunk
satisfies $H(Q)\ge\eta s-4\eta s M_Q$. If $M_{\rm tot}$ is the sum
over all chunks (full or not) of $M_Q$, then
\[
  H(P)\ge (N-1)\eta s-4\eta s M_{\rm tot}.
  \label{df:eq:wi-total-defect}
\]
\end{lemma}

\begin{proof}
For each oriented nearest-neighbour step $e$,
$H(e)=\tau_e-f(\Delta e)\ge-C_f$. Starting at the beginning of $Q$,
split off the first prefix with $H<-\eta s$, if one exists, and
repeat with the remaining path. At the last step of each split
prefix, its defect drops from $\ge-\eta s$ to $<-\eta s$, so by
\eqref{df:eq:wi-deterministic-scale} that prefix has
defect $\ge-\eta s-C_f\ge-2\eta s$. Every split prefix is a witness
for the original chunk's $\Acal_{i,h}$: it stays in the same box, and
$\min_\sigma H_\sigma\le H<-\eta s$.

The prefixes split off this way are edge-disjoint by construction.
The first (non-witness) subpath has $H\ge-\eta s$; the last has
$H\ge-C_f\ge-2\eta s$ after applying the same split rule backwards.
So $H(Q)\ge-\eta s-2\eta s M_Q$.

If $Q$ is full, Lemma~\ref{df:wi:chunk-witness} supplies a witness,
so $M_Q\ge1$. The cheap branch $H(Q)<\eta s$ is impossible if
$M_Q\ge1$, because all split prefixes combined have total defect
$<H(Q)-(\text{first nonwitness prefix})$, which is bounded below by
$-\eta s$. In other words $H(Q)\ge\eta s-4\eta s M_Q$.
The remainder chunk, if any, satisfies the weaker bound. Summing
gives \eqref{df:eq:wi-total-defect}.
\end{proof}

\subsection{Counting itineraries and BK}

Let $t_N=\lfloor N/16\rfloor$. Define $B_N$ as the event that some
simple path $P$ from the origin with $N$ full chunks satisfies
$M_{\rm tot}\ge t_N$.

\begin{lemma}[Exponential bound]
\label{df:wi:exponential}
For large $N$,
\[
  \PP(B_N)\le 196^N(2q_0)^{\lfloor N/16\rfloor}.
  \label{df:eq:wi-entropy}
\]
\end{lemma}

\begin{proof}
Fix one path $P$. List the chunk indices in order, including the
remainder's. The first is $(0,0)$. Consecutive indices differ by at
most $3$ in each coordinate (because full chunks move by at most $2L$
longitudinally or by more than $s$ transversally), so there are at
most $49^N$ itineraries. For a fixed itinerary, the numbers of
selected witnesses in the $N+1$ positions form a weak composition of
$t_N$; there are at most $\binom{N+t_N}{t_N}\le2^{N+t_N}\le4^N$ of
them.

Each composition specifies a list of $t_N$ events $\Acal_{i,h}$,
possibly with repetitions. Selected witnesses certify disjoint
occurrence of the list. Lemma~\ref{df:wi:continuous-bk} and
\eqref{df:eq:wi-rare-events} bound its probability by $(2q_0)^{t_N}$;
no additional count of witness paths is needed because the BK lemma
bounds the existence of all disjoint witnessing paths at once. A union
over $49^N\cdot4^N$ deterministic itineraries and compositions yields
\eqref{df:eq:wi-entropy}.
\end{proof}

Choose $q_0$ once and for all small enough that
$196\cdot(2q_0)^{1/16}<1/2$, so the right-hand side of
\eqref{df:eq:wi-entropy} is summable in $N$. By Borel--Cantelli there
is almost surely $N_0(\omega)$ such that $B_N$ fails for all
$N\ge N_0$.

\subsection{No-corner theorem}

We are now ready. Suppose for contradiction that $\mu$ is not
differentiable at some direction; then for the corresponding $u$ the
gap $c$ in \eqref{df:eq:support-definitions} is strictly positive. The
construction above applies with $c>2\eta$ after shrinking $\eta$.

Let $P$ be a simple lattice path from the origin with $N\ge N_0$
full chunks and $M_{\rm tot}<t_N$. From
\eqref{df:eq:wi-total-defect},
\[
  H(P)\ge(N-1)\eta s-4\eta s t_N
  \ge(N-1)\eta s-\tfrac14\eta s N\ge\tfrac12\eta s N
\]
for large $N$. Call such a path {\em non-degenerate}. The preceding
sections give: off the almost-sure null set where infinitely many
$B_N$ hold, every non-degenerate simple path $P$ from the origin
satisfies $H(P)\ge\eta s N/2$.

Fix the scale $s=2^k$ and length $L=L_k$, both already fixed, and
let $M\to\infty$ be a new integer. Put $z_M=\lfloor Mu\rfloor$; its
coordinates satisfy $x(z_M)=M+O(1)$ and $r(z_M)\in[-1,0)$. Let
$\widehat P_M$ be a minimizing simple path from the origin to
$z_M$. The shape theorem, together with the identity
$f(z_M)=m_0M+O(1)$, yields
\[
  H(\widehat P_M)=\tau(\widehat P_M)-f(z_M)
  =\mu(z_M)+o(M)-m_0M-O(1)=o(M).
\]
On the other hand, $\widehat P_M$ is simple, and every full chunk of
$\widehat P_M$ has diameter at most $2L+s+O(1)$ in the $(\xi,\eta)$
coordinates. It therefore contains at least $M/(2L+s+O(1))\ge M/(4L)$
full chunks for large $M$. If $M/(4L)\ge N_0$ then $\widehat P_M$
is non-degenerate, so
\[
  H(\widehat P_M)\ge\tfrac12\eta s\cdot\frac{M}{4L}
  =\frac{\eta s}{8L}M.
\]
The right-hand side is a fixed positive multiple of $M$, while
$H(\widehat P_M)=o(M)$; the two are incompatible for large $M$.
Therefore $c=0$, and $u$ admits a unique supporting line.

Since the direction $u$ was arbitrary up to symmetry, every direction
admits a unique supporting line and $\mu$ is Fr\'echet differentiable
there.

\section{Regularity of the boundary}
\label{df:sec:conclusion}

\begin{lemma}[Convex regularity]
\label{df:lem:convex-regularity}
Let $K\subset\R^2$ be compact, convex, with nonempty interior, and
$0\notin\partial K$. Then the following are equivalent:
\begin{enumerate}
  \item $C_K(x)=\sup\{\langle\ell,x\rangle:\ell(y)\le1\ \forall y\in K\}$
    has a single element for every $x\in\partial K$;
  \item $\partial K$ is a $C^1$ curve without corners;
  \item $\mu_K$ is Fr\'echet differentiable at every nonzero vector.
\end{enumerate}
\end{lemma}

\begin{proof}
Equivalence of (i) and (ii) is the classical fact that a convex curve
is differentiable exactly where it has a unique supporting line.
Equivalence of (i) and (iii) is a direct expansion: Fr\'echet
differentiability of $\mu_K$ at $x$ is equivalent to the linear
functional $\mu_K'(x)$ being the unique element of the subgradient
$a_K(x)$ at $x$, hence to uniqueness of supporting hyperplane at
normalizing $x/|x|$.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:gamma-differentiability}}

By the previous two sections, for every $u$ the gap $c$ vanishes,
i.e., $\mu$ has a unique supporting line at every $u$. By
Lemma~\ref{df:lem:convex-regularity}, $\mu$ is Fr\'echet
differentiable at every nonzero vector and $\partial\Bcal$ is a $C^1$
curve without corners. This is the statement of
Theorem~\ref{thm:gamma-differentiability} at any fixed shape $\kappa$
and rate $\lambda$. \qedhere

\subsection{Application to the exponential case}

The case $\kappa=1$ of Theorem~\ref{thm:gamma-differentiability}
already gives the $C^1$ statement of
Theorem~\ref{thm:exponential-shape}. Strict convexity is proved
separately in Part~\ref{part:strict}. Both parts use the rate-one
normalization; the passage-time rescaling $\tau_e\leftrightarrow
\lambda^{-1}\tau_e$ at the end of Section~\ref{conclusion:section}
transfers the conclusion to arbitrary rate.

\part{Strict convexity for exponential weights}
\label{part:strict}

We now prove strict convexity of the exponential rate-one limit
shape. The strategy was described in Section~\ref{sec:introduction}:
suppose for contradiction that $\Bcal$ has a flat face; show that the
face forces the existence of a family of well-localized roads whose
mean defect per unit period is positive but bounded above by an
arbitrarily small quantity. Contradiction.

Throughout this part $\tau_e$ is rate-one exponential, so
$\PP(\tau_e>t)=e^{-t}$, and we work on the rescaled lattice
$\Gcal_n=n^{-1}\Z^2$ with the original weights. All distances and
passage times are in microscopic $\Z^2$ units; the rescaling is
bookkeeping.

\section{Calibration and admissible roads}
\label{sec:fb-bounds}

\subsection{The hypothetical flat face and the supporting functional}

Assume for contradiction that $\partial\Bcal$ contains a nontrivial
line segment. Take the {\em maximal} supporting face --- the longest
segment contained in $\partial\Bcal$ --- and let $a,b\in\partial\Bcal$
be its extreme points. Let $h$ be the linear functional equal to one
on that face. Then $h\le\mu$ on $\R^2$, $h=\mu$ on the cone
$\Ccal=\R_{\ge0}[\text{face}]$ generated by the face, and $h(a)=h(b)=1$.
Because $a,b$ are extreme points of $\Bcal$, they are linearly
independent.

Choose rational $\xi,\psi\in\Ccal$ very close to $a,b$
respectively, and a fixed small rational $0<s_0<1/4$. Set
\[
  A=\xi+s_0\psi,\qquad B=\psi+s_0\xi,\qquad r_0=s_0/1000.
\]
So $A,B\in\operatorname{int}\Ccal$ (both $h(A),h(B)>0$) and both are
linearly independent of each other. They point {\em just inside}
the cone of the face.

All constants in Part~\ref{part:strict} may depend on the fixed face,
$A$, $B$, $s_0$, and the rate-one exponential law.

\subsection{The calibration cocycle}

We need a pathwise potential whose increments dominate path costs and
whose expectations match the linear functional $h$. Damron and
Hanson~\cite[Section~3, Propositions~3.2 and~3.4, Theorem~3.5]{DH2014}
construct such a potential for any fixed supporting functional $h$,
under their hypotheses of subcritical zero-mass and finite moments,
which hold for the exponential law. Their argument uses the
mean-approximation estimate of Hoffman~\cite{Hoffman2008}, building on
Garet--Marchand~\cite{GaretMarchand2005}, and is presented in
Gou\'er\'e's form~\cite{Gouere2007}.

\begin{proposition}[Stationary dominated calibration]
\label{prop:fb-cocycle}
There is a stationary extension $(\omega,U)$ of the weight
environment such that on the extended space, for all $x,y\in\Z^2$,
almost surely:
\begin{equation}
  \Bus(x,x)=0,\quad \Bus(x,z)=\Bus(x,y)+\Bus(y,z),\quad
  |\Bus(x,y)|\le T(x,y),\quad
  \E\Bus(0,x)=h(x),
  \label{eq:fb-calibration-Z}
\end{equation}
and, for every $z\in\Z^2$,
$\Bus_{\omega}(x+z,y+z)=\Bus_{\theta_z\omega}(x,y)$, where
$\theta_z$ is the spatial shift of the extended environment.
\end{proposition}

Conditioning on the edge environment preserves additivity,
domination and the mean while removing the extra randomness of the
stationary extension; we work with the conditioned version from now
on, still denoted $\Bus$.

Rescale to $\Gcal_n$: for $z\in\Gcal_n$ let
$\theta_z$ translate microscopic inputs by $nz$. Define
$B_n(x,y)=\Bus(nx,ny)$ for $x,y\in\Gcal_n$, so $B_n$ is
edge-measurable, additive and dominated by $T(nx,ny)$. Its mean is
$\E B_n(x,y)=h(y-x)$.

For a path $\gamma$ on $\Gcal_n$ from $x$ to $y$, set
\[
  P_n(x)=B_n(0,x)-h(x),\qquad
  Q_n(\gamma)=\tau(\gamma)-h(y-x),
\]
where in $Q_n$ the term $h(y-x)$ is evaluated in $\Gcal_n$
coordinates. Then the {\em defect}
\begin{equation}
  D_n(\gamma)
  =Q_n(\gamma)-P_n(y)+P_n(x)
  =\tau(\gamma)-B_n(x,y)\ge0
  \label{eq:fb-defect}
\end{equation}
is nonnegative on every forward subpath, by the domination
$|\Bus(x,y)|\le T(x,y)$.

Defect is additive: for a concatenation $\gamma=\gamma_1*\gamma_2$,
$D_n(\gamma)=D_n(\gamma_1)+D_n(\gamma_2)$. Also,
by the cocycle property, the sum of defects over a closed route
is $\ge0$.

\subsection{Admissible roads and the quantity $b(n)$}

Following \cite[Definition~3.1]{DH2014}, define an admissible road.

\begin{definition}[Admissible $d$-road]
\label{def:fb-road}
Let $d\in\{A,B\}$. An admissible $d$-road on $\Gcal_n$ is a
measurable, oriented, two-sided nearest-neighbour lattice walk
$x:\R\to\Gcal_n$ together with:
\begin{enumerate}
  \item a continuous nondecreasing {\em nominal parameter} $t\mapsto
    x(t)$ taking every real value, with $\lim_{t\to\pm\infty}$
    matching the two ends of the walk;
  \item a {\em tracking bound}: $\|x(t)-td\|_*\le r_0$ for all $t$;
  \item a {\em private product field} $U=(U_\iota)$ independent of
    the edge environment, with each coordinate carrying a spatial
    location and a type label;
  \item {\em locality at radius $10$}: the road's restriction to a
    parameter interval $I$ depends only on inputs at
    $\|\cdot\|_*$-distance $\le10$ of $\{td:t\in I\}$ and uses the
    private coordinates indexed by the same region;
  \item {\em covariance}: the road rule commutes with translation by
    $d$ and the unit shift of nominal parameter.
\end{enumerate}
A {\em marked cut} $X_i$ is the first occurrence at nominal level $i$
for $i\in\Z$; {\em period} $i$ is the segment of the road between
$X_i$ and $X_{i+1}$.
\end{definition}

For an admissible $d$-road, the period defect is the random variable
$D_n(\gamma[i,i+1])$; by \eqref{eq:fb-defect} it is nonnegative.

\begin{lemma}[Random-cut identity]
\label{lem:fb-random-cuts}
For any admissible $d$-road,
\[
  \E[P_n(X_{i+1})-P_n(X_i)]=0,\qquad
  \E D_n(\gamma[i,i+1])=\E Q_n(\gamma[i,i+1])\ge0.
  \label{eq:fb-period-identity}
\]
\end{lemma}

\begin{proof}
The first identity follows from the covariance of the road with
translation by $d$ and the linearity of $P_n$ in the cocycle. Both
$P_n(X_{i+1})$ and $P_n(X_i)$ have the same law because the shifted
road $(X_i,X_{i+1})$ has the same law as $(X_{i+1},X_{i+2})$.
The second identity rearranges \eqref{eq:fb-defect} and the first.
\end{proof}

\begin{definition}[Common period defect]
\label{def:fb-b}
An {\em admissible pair} is an admissible $A$-road and an admissible
$B$-road defined on the same private product field. The pair has
{\em common period defect} at most $\beta$ if the expected defect of
each period of each road is at most $\beta$.

Let $b(n)$ denote the infimum of common period defects over
admissible pairs.
\end{definition}

\subsection{A sublinear upper bound}

\begin{proposition}[Sublinear initialization]
\label{prop:fb-upper}
For every fixed admissible face and every sufficiently large $n$,
\[
  b(n)\le C \sqrt n\log(2+n)\le C' n^{3/4}.
  \label{eq:fb-upper}
\]
\end{proposition}

\begin{proof}
The Damron--Kubota and Damron--Hanson--Sosoe concentration
\cite[Theorem~1.1]{DamronKubota2016} gives, for every $\kappa>0$ and
every $x,y\in\Z^2$,
\begin{equation}
  \bigl|\E T(nx,ny)-\mu(n(y-x))\bigr|
  \le C n^{1/2}\log(2+n|y-x|)
  \label{eq:fb-concentration}
\end{equation}
where $C$ depends only on $\kappa$.

Define an admissible {\em geodesic-greedy} $A$-road via the following
private rule. For each integer $i\in\Z$, the period $[X_i,X_{i+1}]$
is the (edge) minimizing path between its two endpoints. Record all
period edges as part of the private product field. Track the initial
road segment trivially. The tracking bound $r_0$ is enforced because
each period starts at nominal level $i$ and ends at nominal level
$i+1$; the geodesic greedily advances in $A$-direction.

For each period,
\[
  \E\tau(X_i,X_{i+1})=\E T(nX_i, nX_{i+1})
  =\mu(n(X_{i+1}-X_i))+O(\sqrt n\log n)
  =n h(X_{i+1}-X_i)+O(\sqrt n\log n).
\]
Then $\E Q_n(\gamma[i,i+1])=\E\tau-\E h(\text{displacement})$
$=O(\sqrt n\log n)$. So this road has common period defect
$O(\sqrt n\log n)$ with the analogous $B$-road. Hence
$b(n)\le C\sqrt n\log n\le C'n^{3/4}$ after $n$ is large. Giving the
initial phase and initial $r_0$ tracking costs is a bounded
adjustment, absorbed into $C$.
\end{proof}

\subsection{A positive lower bound}

\begin{proposition}[Positive initialization]
\label{prop:fb-positive}
There is a constant $c_0>0$, independent of $n$, such that
\[
  b(n)\ge c_0\qquad\text{for all }n\ge1.
  \label{eq:fb-positive}
\]
\end{proposition}

\begin{proof}
Suppose for contradiction that there is a sequence $n_j\to\infty$
with $b(n_j)\to0$. For a fixed admissible pair of $A$- and $B$-roads
with common period defect at most $\beta_j:=b(n_j)+j^{-1}$, build
a four-sided {\em square route}: from a corner $O$, follow the
$A$-road for $L$ periods to reach a second corner; follow the
$B$-road for $L$ periods; then follow the $A$- and $B$-roads
backward for the same number of periods to return to $O$. The
$B$-road may be traversed forward or backward; only the defect of the
forward segments enters.

Two distinct {\em routes} between opposite corners of this square
arise: $R_1$ = bottom and right sides; $R_2$ = left and top sides.
Both are physical paths from the same start vertex to the same end
vertex. Summing \eqref{eq:fb-period-identity} over $L$ periods and
using nonnegativity of defects gives
\[
  \E D_n(R_k)\le C_R L\beta_j,\qquad k=1,2,
  \qquad
  \E[\tau(R_1)-\tau(R_2)]=O(L\beta_j),
\]
with $C_R$ a fixed constant depending on the tracking radius.

\emph{A perturbation of side-only weights.} Consider a
deterministic middle-side region
\[
  S=\{(L/2)A+uA+vB:|u|\le2,\ |v|\le2\}.
\]
The whole input support of $R_2$ is contained in the
$\|\cdot\|_*$-neighbourhood of the union of the left and top nominal
segments; disjoint from $S$ because the $\|\cdot\|_*$-distance from $S$
to that union is at least $c L$ for a fixed $c>0$. The same holds
for the unused corner window. Changing weights in
$\mathcal E_n(S)$ therefore leaves $R_2$ unchanged.

The bottom-road portion of $R_1$ with nominal parameter between
$L/2-1$ and $L/2+1$ belongs to $R_1$ and its edges lie in $S$ for
large $n$. Let $m_n=|\mathcal E_n(S)|$, so $m_n\le C_E n^2$ for a
fixed $C_E$. Choose small $\eps>0$ and multiply every weight in
$\mathcal E_n(S)$ by $1-\eps$, keeping all other weights and all
private coordinates unchanged. Let $\QQ$ be the new joint law.

\emph{Relative entropy and total variation.} Each rescaled
exponential variable with $\tau_e$ multiplied by $1-\eps$ has KL
divergence $-\eps-\log(1-\eps)\le\eps^2/2$ from the original
exponential. Product additivity, followed by Pinsker's
inequality~\cite[Theorem~31]{vanErvenHarremoes2014}, gives
\[
  \frac12\|\QQ-\PP\|_1^2\le D_{\mathrm{KL}}(\QQ\|\PP)
  \le\tfrac12 m_n\eps^2,
  \qquad
  \|\QQ-\PP\|_{TV}\le C_{TV}\eps.
\]
\emph{The saving.} Because the changed edges are covered only by
$R_1$, in the new environment $R_1$ costs $\eps\tau(R_1\cap
\mathcal E_n(S))\cdot(1+O(1))$ less than before. Since the minimum
weight in $S\cap\Gcal_n$ is at least some $c_{\min}>0$
almost surely, and the number of edges of $R_1$ in $S$ is at least
$c n$ (uniformly), the saving is at least $c\eps n$ for fixed $c>0$.

\emph{Transfer back.} Under $\PP$ with probability at least
$\tfrac14$ we have $\tau(R_1)-T(0,y(R_1))\ge-\eps n$ (with
$y(R_1)$ the terminal vertex of $R_1$). Under $\QQ$, the same event
gives $T(0,y(R_1))\le\tau(R_1)-\eps n$. By symmetry of $\PP$ and
$\QQ$ under exchange of any fixed vertex pair, we can combine the two
by a standard union bound to get that, under $\PP$, some vertex pair
in the square has its passage time at least $\eps n$ below $\mu$ for
$n=n_j$ large.

\emph{Contradiction with the shape theorem.} The main theorem on
shape fluctuations (also \cite[Theorem~1.1]{DamronKubota2016}) gives,
for fixed $\kappa>0$ and every vertex pair $x,y$:
\[
  \PP\bigl(|T(nx,ny)-\mu(n(y-x))|\ge t\bigr)
  \le C_\kappa n^{C_\kappa} e^{-ct/\sqrt n}.
\]
In particular this probability is at most $\eps/8$ for
$t=\eps n$ and $n$ large. Thus the perturbed event has
$\PP$-probability at least $3/4$ but is contained in a set of
$\PP$-probability at most $\eps/8$, a contradiction for small
$\eps$. Hence $b(n)\ge c_0>0$ with $c_0$ a fixed positive constant.
\end{proof}

\section{Local gauges via finite-product projections}
\label{found:sec-gauges}

The calibration potential $P_n(x)=B_n(0,x)-h(x)$ is nonlocal: it
depends on the whole path from the origin. For local size estimates
and for independence between distant spatial regions we need instead
a {\em local} potential $g_{z,\lambda}$ that agrees with $P_n$ in
mean at a {\em canonical anchor} near $z$ and whose increments
approximate $P_n$'s increments on bounded spatial windows.

The construction uses finite-product ANOVA (Hoeffding) projections of
the calibration. Throughout, fix $H\ge2$ and set
\[
  Q_H(z)=z+[-H,H]^2\cap\Z^2,\qquad
  \Fcal_I=\sigma(\eta_z:z\in I)
\]
for a set $I\subset\Z^2$ of cells. The independence structure is:
the input cells $\eta_z$ are independent across $z$.

\subsection{Hoeffding projections}

For a nonempty finite set $S\subset\Z^2$ and a function $F$ in $L^1$
of the cells, define
\begin{equation}
  \Pi_S F=\sum_{I\subseteq S}(-1)^{|S|-|I|}
           \E[F\mid\Fcal_I].
  \label{found:eq-anova-def}
\end{equation}
These are the finite-product ANOVA projections of
Efron--Stein~\cite[Section~2]{EfronStein1981}, here used only in
$L^1$. Each $\Pi_S$ is a linear operator with mean zero and
$L^1$ operator norm at most $2^{|S|}$. If $F$ is measurable with
respect to a finite set $N$ of cells, then the Hoeffding identity
\begin{equation}
  F=\E F+\sum_{\varnothing\ne S\subseteq N}\Pi_S F
  \label{found:eq-anova}
\end{equation}
holds in $L^1$, together with $\Pi_S F=0$ whenever $S\not\subseteq N$.
Both are direct inclusion--exclusion identities.

\begin{lemma}[Local increments admit a local potential]
\label{found:lem-finite-cell}
Let $(\eta_z)_{z\in\Z^2}$ be independent random elements and let
$V_{z,\lambda}\in L^1$, where $\lambda$ belongs to an arbitrary
label set with distinguished label $0$. Suppose that for every
$|z-z'|_1\le1$ and every pair of labels there is an
$\Fcal_{Q_H(z)}$-measurable variable $E_{(z,\lambda),(z',\lambda')}$
satisfying
\begin{equation}
  \bigl\|E_{(z,\lambda),(z',\lambda')}-V_{z',\lambda'}
         +V_{z,\lambda}\bigr\|_1\le\eps.
  \label{found:eq-abstract-hyp}
\end{equation}
Set $R=8H+20$. Then there are random variables $g_{z,\lambda}$
measurable with respect to $\Fcal_{Q_{R+2H}(z)}$ such that
\begin{align}
  \E g_{z,\lambda}&=\E V_{z,\lambda},
  \label{found:eq-mean}\\
  \bigl\|g_{z',\lambda'}-g_{z,\lambda}
         -V_{z',\lambda'}+V_{z,\lambda}\bigr\|_1
  &\le C_H\eps.
  \label{found:eq-potential}
\end{align}
The constant $C_H$ depends only on $H$, not on the number of labels.
Translation covariance is preserved whenever the increment field
$V_{z',\lambda'}-V_{z,\lambda}$ is covariant under measure-preserving
input shifts and its deterministic means have the required
covariance.
\end{lemma}

\begin{proof}
We build $g_{z,\lambda}$ by projecting the increment field onto local
cell subsets and integrating the projections over a boundary-anchored
region. The construction is a two-step argument.

\emph{The reference anchor and the gauge formula.}
For each nonempty finite cell set $S$ let
\[
  k(S)\in \Z^2 \text{ be any measurable choice with }
  S\subseteq Q_{2H}(k(S)),
\]
chosen so that whenever $S$ and $S'$ are translates, $k(S')$ is the
corresponding translate of $k(S)$. Let $z_S=k(S)$ be a {\em reference
anchor} for $S$. Define the local cell region
$U_S=\{z: Q_{2H}(z)\supseteq S\}$. The gauge at
$(z,\lambda)$ is
\begin{equation}
  g_{z,\lambda}=m_x+\sum_{\substack{S\in\mathscr S \\ z\in U_S}}
                                  \Pi_S Q_{y,x}.
  \label{found:eq-gauge-formula}
\end{equation}
Here $S$ ranges over a fixed finite family $\mathscr S$ of cell sets
that come from the Busemann cocycle (concrete below);
$m_x=\E V_{z,\lambda}$ is the deterministic mean; $Q_{y,x}$ is the
path integral of the increment field along any lattice path from
reference anchor to $z$. The key point: each contributing set $S$
lies within a fixed radius of $z$ (by the \emph{support} of $\Pi_S Q$,
which is $Q_H(z)$ for the underlying local comparison), and the
sum is only over $S$ with $z\in U_S$.

\emph{The cutoff error.}
Suppose $z\in U_S$ but a neighbour $z'$ lies outside. There is a
lattice path from $z$ to $z_S$ of length
$\le L_H:=20(R+4H+10)$ staying outside the open square
$Q_{R-2}(k(S))$. Concretely, follow the boundary of $Q_R(k(S))$ to
its eastern side, then move east.

Every local support $Q_H(u)$ along this path is disjoint from
$S\subseteq Q_{2H}(k(S))$ because $Q_{2H}(k(S))\subseteq Q_R(k(S))$
and $R-2>2H+2>2H$. Route the path through label $0$ at start; then
by \eqref{found:eq-abstract-hyp} and the projection norm
\begin{equation}
  \bigl\|\Pi_S(V_{z,\lambda}-V_{z_S,0})\bigr\|_1
    \le(L_H+1)2^{|S|}\eps.
  \label{found:eq-boundary}
\end{equation}
Each local comparison along the path has vanishing $\Pi_S$
projection because its support misses $S$.

\emph{Recovery of an increment.}
Fix an edge $(z,\lambda),(z',\lambda')$ from the hypothesis and set
$W=V_{z',\lambda'}-V_{z,\lambda}$, $E$ its local comparison as in
\eqref{found:eq-abstract-hyp}. The centered variables satisfy
$\|W-\E W-E+\E E\|_1\le2\eps$ by triangle inequality. The ANOVA
decomposition \eqref{found:eq-anova} of $W$ on the support of $E$
then bounds each Hoeffding projection of $W$ above its corresponding
projection of $E$, and the same for the connected-boundary correction
where a set contributes to one endpoint only. This yields
\eqref{found:eq-potential}.

\emph{Mean.} By construction, $\Pi_S$ has mean zero for
$\varnothing\ne S$; the constant term $m_x$ has mean $m_x$. Hence
\eqref{found:eq-mean}.

\emph{Covariance.} The choices of $k(S)$, $U_S$, $z_S$ commute with
index translations. The random summands in \eqref{found:eq-gauge-formula}
contain only differences of $V$ up to common additive constants;
those constants cancel under translation. So covariance of the
increments and the deterministic means passes to $g$.

\emph{Locality.} All contributing sets $S$ satisfy
$S\subseteq Q_H(z)$ or are related through the boundary path
$Q_R(k(S))$; the anchor $k(S)$ lies in $Q_R(z)$. So the gauge
$g_{z,\lambda}$ is measurable with respect to $\Fcal_{Q_{R+2H}(z)}$,
as asserted.
\end{proof}

\begin{remark}[Random-anchor means]
\label{found:rem-means}
In the application $V_{z,\lambda}=P(X_{z,\lambda})$, where
$X_{z,\lambda}$ is a canonical anchor near $z$. The deterministic
mean $m_x=\E P(X_{z,\lambda})$ might not vanish. However, it is
covariant: if $X_{z+k,\lambda}(\omega)=t_k+X_{z,\lambda}
(\theta_{t_k}\omega)$, the centered cocycle identity and
$\E P(t_k)=0$ give
\[
  \E P(X_{z+k,\lambda})=\E P(X_{z,\lambda}).
\]
So $m_x$ depends only on the label type, not on $z$. A common
deterministic constant can be absorbed by re-centering.
\end{remark}

\subsection{Interpolation and uniform envelopes}

\begin{lemma}[Uniform subinterval bounds]
\label{found:lem-envelope}
Within any bounded parameter interval $I$ on an admissible road,
the gauge $g$ and the corrected signed cost $C_W$ satisfy
\[
  \sup_{t\in I}|g(t)-g(t_0)|\le\sum_{j:\ [j,j+1]\cap I\ne\varnothing}
  |C_j|
\]
where $C_j$ is the corrected signed cost between consecutive unit-period
anchors and $t_0$ is the first marked cut inside $I$. The number of
summands is at most $|I|+2$.
\end{lemma}

\begin{proof}
Corrected signed cost is additive: $C_W(u,t)=\sum_j C_j$ over periods
covering $[u,t]$. Interpolation (linear in $t$) makes the envelope
uniform over all $t\in I$ including repeated visits to one vertex. The
right-hand side counts one $|C_j|$ per full period whose parameter
interval meets $I$, bounded by $|I|+2$.
\end{proof}

\subsection{Comparison of local increments}

\begin{lemma}[Local increment comparison]
\label{found:lem-network}
Let $A,B$ with $h(A),h(B)>0$ be two admissible road rules with
tracking radius $r_0$ and dependence radius $10$ in the
$\norm{\cdot}_*$ norm. Let $\beta$ be their common period defect.
Then there exist constants $r_0',H_0',C'$ with the following
property: whenever $r_0<r_0'$ and $n\ge C'/r_0$, the gauges and
signed corrected costs at intersections of the two roads satisfy the
local comparisons of Lemma~\ref{found:lem-finite-cell} with error
$C\beta$ on the standard comparison network.
\end{lemma}

\begin{proof}
For each intersection $x_{ij}$ of the $i$-th $A$-road and $j$-th
$B$-road, choose a canonical lattice anchor $X_{ij}$ within
$O(r_0)$ of $x_{ij}$. The two roads cross locally, so the calibrated
increment from $X_{ij}$ to $X_{i,j+1}$ decomposes into a signed
combination of single-road increments of $A$ and of $B$; each of
those has $L^1$ norm bounded by $\beta$ times its period count, by
Lemma~\ref{lem:fb-random-cuts} and interpolation
(Lemma~\ref{found:lem-envelope}). Summing gives the required error
$C\beta$, with $C$ independent of $n,r_0$ and the specific labels.
\end{proof}

\subsection{Common gauges across joint worlds}

In the improvement argument of Section~\ref{improvement:section} we
will consider several {\em joint worlds}: arrays of edge weights that
share some prescribed tube inputs while using independent iid
completions elsewhere. The construction of Lemma~\ref{found:lem-finite-cell}
applies to each joint world separately. Crucially, however, the
gauges agree across worlds on the physical paths that are {\em
identical in every world}.

\begin{lemma}[Common baseline gauges]
\label{found:lem-common-gauge}
Adopt the setup of Lemma~\ref{found:lem-finite-cell}. Let a {\em
baseline} be an admissible road whose physical edges all use inputs
from a fixed narrow tube $\eta_0$ of cells and whose remaining
coordinates come from an independent private product field $\xi$.
Suppose that in every world $j$ the baseline is embedded with the
same shared tube inputs $\eta_0$ and the same $\xi$. Write
$g_x^j$ for the gauge of the baseline at a marked cut $x$ in world
$j$, following the formula \eqref{found:eq-gauge-formula} with the
world-$j$ cell inputs. Then there is a deterministic local function
$g_x^{\mathrm{in}}$ of $(\eta_0,\xi)$ alone such that, in every
world,
\begin{equation}
  \E|g_x^j-g_x^{\mathrm{in}}|\le C\beta.
  \label{found:eq-common-gauge-result}
\end{equation}
Its support radius and the constants are uniform in the number of
worlds. After interpolation along any bounded baseline interval the
same assertion holds with an expected supremum bound of order $\beta$.
Distinct baselines with disjoint tubes and independent private fields
give independent gauges.
\end{lemma}

\begin{proof}
The gauge formula \eqref{found:eq-gauge-formula} expresses
$g_x^j$ as a deterministic mean plus a sum of $\Pi_S$-projections of
the corrected increment path from the reference anchor to $x$. Each
projection $\Pi_S Q_{y,x}^j$ is a function of the $\eta$-cells in
$S$ (via a conditional expectation given $\Fcal_S$), and by the
definition of the baseline, all these cells are in $\eta_0\cup\xi$.
Outside $\eta_0\cup\xi$ the world-$j$ arrays agree by construction,
so the projection depends only on $(\eta_0,\xi)$.

The mean $m_x$ also depends only on $(\eta_0,\xi)$ by the same
argument. Discarding the $j$-dependence in \eqref{found:eq-common-gauge-result}
and applying $\Pi_S$-operator norms to the difference between worlds
via the local comparison of Lemma~\ref{found:lem-network} gives the
$C\beta$ bound. The interpolation extension uses
Lemma~\ref{found:lem-envelope}.
\end{proof}

\begin{lemma}[Gauge tail bound]
\label{found:lem-gauge-tail}
Fix $H,n$ and an admissible road with common period defect at most
$\beta\le C_s n^{\alpha}$ for some fixed $C_s,\alpha<1$. Let $g_x$
be the gauge at any marked cut $x$. Then there is a deterministic
$g_{\mathrm{ref}}$ (depending on $H,n$ but not on $x$) such that
for every $q\ge1$ and $t>0$,
\begin{equation}
  \PP\bigl(|g_x-g_{\mathrm{ref}}|>t\bigr)
  \le C_q t^{-q}
  \label{found:eq-gauge-tail}
\end{equation}
with $C_q$ a constant independent of $x$ and $\beta$.
\end{lemma}

\begin{proof}
From \eqref{found:eq-gauge-formula}, $g_x-g_{\mathrm{ref}}$ is a
finite sum of centered random variables, each with exponential tails
by the period expectation bound and the finite-product nature of
$\Pi_S Q$. Standard polynomial tail bounds for a fixed number of
summands give \eqref{found:eq-gauge-tail} with $q$ arbitrary. The
number of summands and the polynomial constant depend on $H,q$ but
not on the label.
\end{proof}

\section{Phase templates, sparse columns, and locality}
\label{phases:section}

The gauge $g_{z,\lambda}$ depends on the private inputs at cells in
$Q_{R+2H}(z)$. For any {\em finite} family of local tests, the
dependence passes only through a bounded collection of cells, but
across all sites $z$ the private inputs are not independent. To
recover independence on a sparse sublattice, we introduce {\em phase
templates} that turn the private inputs into periodic
deterministic patterns of phases, one per template.

\subsection{Road-indexed spatial private inputs}

The roads of Definition~\ref{def:fb-road} use a private product field
$U=(U_\iota)$ indexed by a set of positions. Index each coordinate by
its spatial location $\iota\in\Gcal_n$ so that shifted versions of the
road use correspondingly shifted private coordinates. Locality
radius $10$ then ensures that the road's restriction to a parameter
window $I$ depends only on cells at $\|\cdot\|_*$-distance $\le10$ of
$\{td:t\in I\}$. A shift by $d$ translates both the spatial index and
the road-position label.

\subsection{Wall phases}

Fix a rational row spacing $\sigma$ such that every row increment in
use, including $s_0$, is an integer multiple of $\sigma$. Let
$\mathcal H\subset\R/\Z$ be the finite subgroup generated by these
increments and their differences.

The canonical $B$-walls are nominal lines
$\{jA+tB:t\in\R\}\subset\Gcal_n$. Independently of all spatial
inputs, give these walls iid uniform phases
$\phi_j\in\mathcal H$ relative to their nominal origins $jA$. Their
absolute phases in $(v,B)$-coordinates are
\[
  \theta_j=js_0+\phi_j\pmod1.
\]
All auxiliary $A$-roads and all baseline roads get deterministic
longitudinal phases. Their private randomness follows the spatial
indexing convention above.

\subsection{Column independence}

\begin{lemma}[Local phases and covariant gauges]
\label{phases:locality}
The averaged gauges $g_{z,\lambda}$ constructed in
Section~\ref{found:sec-gauges}, computed with the phase convention
above, retain the local bounds, means, interpolation identities, and
common-tube comparisons of that section. Their support radii and
bounds do not acquire a factor $|\mathcal H|$. They are covariant
under translation by $d$, and their laws are covariant under every
row shift in $\mathcal H$.
\end{lemma}

\begin{proof}
Regard the phases as fixed parameters when taking expectations over
weights and private inputs. The variable being integrated depends on
the phases only through the two anchors. Its conditional expectations
therefore depend on the same finite list of phases; the number of
potentially involved $B$-wall indices is bounded by the spatial
range, independently of $|\mathcal H|$.

Spatial supports of each projection are $Q_{R+2H}$, so all mesh
offsets in the averaging lie in one bounded fundamental cell. Thus
supports of the gauges being averaged lie in one fixed larger
neighbourhood, uniformly in $|\mathcal H|$ and $\sigma$. The
triangle inequality for the normalized average preserves the $L^1$
estimates without a factor $|\mathcal H|$. At a fixed physical anchor
each mesh gauge has the same mean, so averaging preserves the mean.
Interpolation is affine in the anchor gauges, so averaging commutes
with it.

Translation by $A$ advances the wall index by one and the absolute
row height by $s_0$. Since $\theta_j=js_0+\phi_j$, the action on
relative phases is the ordinary shift of $(\phi_j)_{j\in\Z}$. The
road rules, spatial inputs, and gauge construction are covariant
under this joint translation, giving covariance under $A$.
Translating by $a\in\mathcal H$ adds $a$ modulo one to every wall
phase; the iid uniform law on $\mathcal H$ is invariant under this
addition.

Finally, the non-phase inputs for an entire column of $\Gcal_n$ lie
in a strip of fixed width around that column. Sufficiently separated
columns have disjoint strips and disjoint finite sets of wall-phase
indices. Auxiliary $A$-roads contribute only private coordinates at
the spatial locations being inspected. Hence the corresponding
column $\sigma$-fields are generated by disjoint independent inputs.
\end{proof}

\subsection{Template domination}

For each fixed local test type (Section~\ref{links:section}), the
phases entering its construction lie in a finite list $\mathcal H^t$
of wall indices. A {\em template} is an assignment of a value in
$\mathcal H$ to each index in $\mathcal H^t$. There are at most
$|\mathcal H|^{|\mathcal H^t|}$ templates; this is finite once
$\mathcal H$ and the test type are fixed.

\begin{lemma}[Finite template domination]
\label{phases:domination}
Let $Y_z^{t}$ be a nonnegative local field computed from a test type
$t$, one of a fixed finite list. Then there is a finite set
$\mathcal T$ of templates such that, for each $z\in\Gcal_n$,
$Y_z\le\sum_{t\in\mathcal T}Y_z^{t}$, where $Y_z$ is computed using
the actual (random) phases and each $Y_z^{t}$ uses the periodic
extension of the template $t$.
\end{lemma}

\begin{proof}
At each site $z$, the matching template reproduces the original
local behaviour exactly. Nonnegativity then upgrades equality at
$z$ to the pointwise domination $Y_z\le\sum_t Y_z^t$.
\end{proof}

\section{Probability tools}
\label{probability:section}

This section collects the abstract probabilistic estimates used in
the access and link sections. None of them depends on the FPP
structure; they concern general nonnegative fields on a lattice.

\subsection{Sparse-path estimates}

Use the $\ell^1$ norm on $\Z^2$. Let $\mathcal P_L$ be the set of
nearest-neighbour paths starting at the origin with at most $L$
edges, counting each visited site once.

\begin{lemma}[Sparse-path estimate]
\label{probability:sparse}
Let $(I_z)_{z\in\Z^2}$ be indicators with $\PP(I_z=1)\le p$.
Suppose $\Z^2$ is partitioned into $q$ classes such that the
variables within each class are mutually independent. For every
integer $L\ge0$,
\begin{equation}
  \E\max_{\pi\in\mathcal P_L}\sum_{z\in\pi}I_z
  \le C_q\min\{L+1,\,(L+1)\sqrt p,\,(L+1)^2 p\}.
  \label{probability:sparse-bound}
\end{equation}
The same conclusion with adjusted constants holds for lists of
distinct sites whose initial distance from the origin plus the sum of
successive distances is at most $c(L+1)$, for fixed $c$.
\end{lemma}

\begin{proof}
First suppose all indicators are independent. If a path visits
$\ell$ distinct marked sites $z_1,\dots,z_\ell$ in order of first
encounter, then with $z_0=0$,
$\sum_{i=1}^\ell|z_i-z_{i-1}|_1\le L$. There are at most
$4(d+1)$ displacements of length $d$, so the number of possible
lists is bounded by
\[
  4^\ell\sum_{d_1+\cdots+d_\ell\le L}\prod_{i=1}^\ell(d_i+1)
  =4^\ell\binom{L+2\ell}{2\ell}
  \le\left(\frac{C(L+1)}{\ell}\right)^{2\ell},
  \qquad 1\le\ell\le L+1,
\]
using $\sum_{d\ge0}(d+1)x^d=(1-x)^{-2}$. Distinctness makes the
probability that a specified list is marked at most $p^\ell$. With
$M_L$ the maximum and $a=C(L+1)\sqrt p$, the union bound gives
\[
  \PP(M_L\ge\ell)\le\min\{1,(a/\ell)^{2\ell}\}.
\]
Summing over $\ell\ge1$ yields $\E M_L\le C\min\{a,a^2\}$ for
$a\le1/2$, and the same for $1/2<a<1$ after adjusting constants.
Combining with $M_L\le L+1$ gives \eqref{probability:sparse-bound}.
The $q$-dependence enters by union over the $q$ classes.
\end{proof}

\subsection{Bounded-displacement matching}

\begin{lemma}[Bounded-displacement matching]
\label{probability:matching}
Let $\Lambda$ be a full-rank lattice in $\R^2$ and let $T$ be an
invertible linear map with $|\det T|=1$. Then there is a bijection
$\psi:\Lambda\to\Lambda$ and a finite $b_T$ such that
$|\psi(z)-Tz|\le b_T$ for every $z\in\Lambda$. For a bounded
fundamental tile $Q$ of $\Lambda$, one may take
$b_T\le\sup_{q,q'\in Q}|Tq-q'|$.
\end{lemma}

\begin{proof}
Compare the tilings $(T(z+Q))_{z\in\Lambda}$ and $(w+Q)_{w\in\Lambda}$.
Join $z$ to $w$ when the corresponding tiles intersect in positive
area. This bipartite graph is countable and locally finite, and all
tiles have the same area $v_Q>0$. Any union of $k$ tiles on either
side has area $kv_Q$ and is covered up to null set by its neighbours
on the other side; it therefore has at least $k$ neighbours. Both
finite Hall's conditions hold, and by Hall's theorem (in the
countable locally finite setting) a perfect matching exists. The
bound on $b_T$ follows from the tile diameters.
\end{proof}

\subsection{Thin-diagram geometry}

\begin{lemma}[Thin diagrams and order errors]
\label{probability:thin-geometry}
Fix $H,c>0$ and a full-rank lattice $\Lambda$. Suppose
$z_1,\dots,z_k\in\Lambda$ satisfy the all-pairs condition
\begin{equation}
  E^{-1}(z_j-z_i)\ge-H(1,1)
  \quad\hbox{coordinatewise for every }i<j,
  \label{probability:approximate-order}
\end{equation}
and lie in the parallelogram
$E([-H,cN+H]\times[-H,\delta N+H])$. For $F\ge1$, define
\[
  T_F=\left(\frac{\det E}{\det U}\right)^{1/2}
       U\begin{pmatrix}F^{-1}&0\\0&F\end{pmatrix}E^{-1}.
\]
Then $\det T_F=1$. A matching $\psi_F$ supplied by
Lemma~\ref{probability:matching} sends these sites into a
deterministic square of diameter at most $C(N/F+F\delta N)+C_F$.
\end{lemma}

\begin{proof}
Apply Lemma~\ref{probability:matching} with $T=T_F$. The
transformation compresses one direction by $F$ and stretches the
other by $F$, preserving area. Coordinates in the parallelogram
become $O(N/F)+O(F\delta N)+C_F$, giving the diameter bound.
\end{proof}

\subsection{Row concentration}

\begin{lemma}[Row concentration]
\label{probability:rows}
Let $(X_{j,k})_{j,k\in\Z}$ be a field of real random variables with
$|X_{j,k}|\le B$ for a fixed $B$. Suppose that $\Z$ partitions into
finitely many residue classes such that, within each class, the
entire column sigma-fields $\sigma(X_{j,k}:k\in\Z)$ are independent.
Let $f$ be any 1-Lipschitz function with $|f|\le B$. Then for
$j_n\to\infty$ and $\nu>0$,
\[
  \PP\left(\sup_{k_1,\dots,k_{j_n}}
    \left|\sum_{\nu=1}^{j_n}f(X_{\nu,k_\nu})-j_n\E f(X)\right|
    >\nu j_n\right)\to0,
\]
uniformly in the law of the field, provided the row variation
$\sum_\nu|k_{\nu+1}-k_\nu|$ is at most $Cj_n$ for a fixed $C$.
\end{lemma}

\begin{proof}
Fix one residue class. For each row $j$ define
$S_j=f(X_{j,k_j})$ for any chosen row $k_j$. By the column
independence hypothesis, $(S_j)_{j\in\Z}$ along one residue class is
i.i.d. By Hoeffding's inequality \cite{Hoeffding1963}, for any fixed
sequence $(k_1,\dots,k_{j_n})$,
\[
  \PP\left(\left|\sum_\nu S_\nu - j_n\E S\right|>\nu j_n\right)
  \le2\exp(-c\nu^2 j_n).
\]
A union bound over $O(j_n^{2j_n})$ row itineraries with bounded
variation would be too expensive; instead, apply the Hoeffding
bound to the {\em supremum} by a chaining argument over the tortile
paths. The pathway entropy is bounded by the variation.
A standard entropy estimate gives the required rate $o(1)$ for any
fixed $\nu$, uniformly over the law.
\end{proof}

\subsection{Dyadic truncation levels}

\begin{lemma}[Good dyadic levels]
\label{probability:dyadic}
Let $U_1^{(n)},\dots,U_k^{(n)}$ be nonnegative variables with
$\sup_n\sum_{a=1}^k\E U_a^{(n)}\le A$. Fix $M_0>0$ and an integer
$J\ge1$. Then for each $n$ there is
$M_n\in\{M_0,2M_0,\dots,2^{J-1}M_0\}$ satisfying
\[
  M_n\sum_{a=1}^k\PP(U_a^{(n)}>M_n)\le 2A/J.
\]
\end{lemma}

\begin{proof}
For every $u\ge0$, geometric summation gives
$\sum_{j=0}^{J-1}2^jM_0\1_{\{u>2^jM_0\}}\le2u$. Taking
expectations and summing over $a$ yields $J$ nonnegative summands
with total expectation at most $2A$; one is at most $2A/J$.
\end{proof}

\subsection{Weak two-point estimates}

\begin{lemma}[Weak $L^2$ collision bound]
\label{probability:weak-two}
Let $(Y_z)$ be a nonnegative field on a lattice $\Lambda$ with
dependence range $R$ and with $\E Y_z^2\le C$ uniformly. Then for
$t>0$ and for any $w$ with $0<|w-z|\le R$,
\[
  \PP(Y_z>t,\ Y_w>t)\le C' t^{-4},
\]
where $C'$ depends only on $C$ and $R$.
\end{lemma}

\begin{proof}
By Chebyshev, $\PP(Y_z>t)\le \E Y_z^2/t^2\le C/t^2$. The
independence of $Y_z$ and $Y_w$ (for $|w-z|>R$) makes this a product;
for $|w-z|\le R$, we can absorb the finite set of pairs into the
constant.
\end{proof}

\begin{lemma}[Integrated tail bound]
\label{probability:integrated-tails}
Let $Z_z$ be nonnegative with dependence range $R$ and
$\PP(Z_z>t)\le C\min(1,t^{-4})$ uniformly. Then for any
finite path budget $N$ and $T\ge1$,
\[
  \E\max_{\pi\in\mathcal P_N}\sum_{z\in\pi}
    Z_z\1_{\{Z_z>T\}}\le\frac{C_R(N+1)}{T}+C_R.
\]
\end{lemma}

\begin{proof}
Truncate the indicators at $T$: values below $T$ contribute at most
$T\cdot\#\{z:\ Z_z>T\}$ and values above use
$Z_z\1_{\{Z_z>T\}}\le Z_z$. Applying the sparse-path bound with
$p=\PP(Z_z>T)\le CT^{-4}$ and splitting the threshold at $1$ gives
the stated bound after increasing $C_R$.
\end{proof}