Proof. Integrating the Gamma density with the substitution \(y=(\lambda-\theta)t\) gives the moment identity. At \(\theta=\lambda/2\) it reads \(\mathbb Ee^{\lambda\tau/2}=2^\kappa\). Independence and exponential Markov inequality give \[\mathbb P\left(V>\frac{2A\kappa}{\lambda}v\right) \le e^{-A\kappa v}2^{\kappa M} \le e^{-A\kappa(1-\log 2)v}.\] ◻

Proof. Each of \(a_-\) and \(a_+\) is a subgradient at zero of the convex function \(t\mapsto\mu(u+te_2)\). If \(x(z)>0\), write \(z=x(z)(u+r(z)x(z)^{-1}e_2)\) and use positive homogeneity to get \(f_\sigma(z)\le\mu(z)\). If this inequality failed at any other point \(z\), then a sufficiently small positive convex combination of \(z\) with \(u\) would still violate it, by convexity, and would have positive first coordinate. This is impossible. The average \(f\) is also bounded above by \(\mu\). Equation (5) is the respective one-sided derivative expansion. ◻

Proof. Turning an allowed crossing into a fast crossing. Put \(n=s^3\). Choose a fixed \(\eta>0\) such that \[\eta m_0>K+16\left\lvert a_+\right\rvert+1,\] and set \(\delta=\eta s/n\) and \(\alpha=1-\delta\). Take \(s\) sufficiently large that \(0<\delta\le1/2\). Multiply every internal edge weight of the region defining \(E(s,n)\) by \(\alpha\), leaving the other weights unchanged. If \(P\) witnesses \(E(s,n)\) before this operation, its transverse displacement obeys \(\left\lvert r(\Delta P)\right\rvert\le16s\), and in the modified environment \[\begin{split} H_+(P) &<\alpha(m_0n+Ks)-m_0n-a_+r(\Delta P)\\ &\le \bigl(K-\eta m_0+16\left\lvert a_+\right\rvert\bigr)s -\eta K\frac{s^2}{n}<-s. \end{split}\] This computation includes every traversal if \(P\) repeats an edge. Let \(F(s,n)\) be the crossing event \(H_+(P)<-s\) in the same region, and let \(Q\) be the law of the modified environment. The deterministic implication gives \[ \mathbb P(E(s,n))\le Q(F(s,n)). \tag{13}\]

The cost of the change of measure. Under \(Q\), a modified edge has distribution \(\operatorname{Gamma}(\kappa,\lambda/\alpha)\). On \(t>0\) its likelihood ratio with respect to the original edge law is \[L_\delta(t) =\frac{p_{\kappa,\lambda/\alpha}(t)}{p_{\kappa,\lambda}(t)} =\alpha^{-\kappa} \exp\{-\lambda(\alpha^{-1}-1)t\}.\] Both densities are positive on \((0,\infty)\), including when \(0<\kappa<1\). Direct integration gives \[\begin{split} \mathbb E[L_\delta(\tau_e)^2] &=\alpha^{-2\kappa}\frac{\lambda^\kappa}{\Gamma(\kappa)} \int_0^\infty t^{\kappa-1} e^{-\lambda(2/\alpha-1)t}\,\mathrm d t\\ &=\alpha^{-2\kappa}(2/\alpha-1)^{-\kappa} =\bigl(\alpha(2-\alpha)\bigr)^{-\kappa} =(1-\delta^2)^{-\kappa}. \end{split}\] The region has at most \((3n+1)(16s+2)\) vertices and at most twice that many internal unoriented edges. Thus the number \(M\) of modified coordinates is at most \(144ns\). The likelihood ratio is a product over these distinct coordinates, regardless of path multiplicity. By independence, \[\begin{split} \mathbb E\left[\left(\frac{\mathrm d Q}{\mathrm d\mathbb P}\right)^2\right] &=(1-\delta^2)^{-\kappa M} \le \exp(2\kappa M\delta^2)\\ &\le \exp\left(288\kappa\eta^2\frac{s^3}{n}\right) =\exp(288\kappa\eta^2). \end{split}\] Transfer back to the original law. Lemma 8, applied under the original law with \(A=1\), \(R=8\), and \(\varepsilon=1\), gives \(\mathbb P(F(s,n))\to0\) because \(n/s=s^2\to\infty\). Cauchy–Schwarz therefore gives \[\mathbb P(E(s,n))\le Q(F(s,n)) \le e^{144\kappa\eta^2}\mathbb P(F(s,n))^{1/2}\longrightarrow0.\] All supports and the norm in \(F(s,n)\) are those of the original fixed law; no shape theorem for the modified environment is used. ◻

Proof. Short crossings are likely. First suppose \(n\to\infty\) with \(n\leq Cs\), and put \(q=(n,\lfloor bn\rfloor)\). Then \[\mu(q)\leq m_0n+\mu(e_2),\qquad -1<r(q)\leq0.\] Apply Lemma 5 at scale \(n\), with endpoints \(0,q\), with cost error \(\eta n\) where \(\eta=K/(4C)\), and with tube radius \(\delta_0n\), where \[0<\delta_0\leq\min\{1/4,1/(2C)\}.\] The endpoints have Euclidean distance at most \(3n\). Since \(\left\lvert b\right\rvert\leq1\), changing a point by Euclidean distance \(t\) changes its \(r\)-coordinate by at most \(\sqrt2t\). The resulting tube is inside \(-n\leq x\leq2n\), and inside \(\left\lvert r\right\rvert\leq8s\) for all sufficiently large \(s\): its transverse extent is at most \(1+\sqrt2\delta_0n\). With probability tending to one its path cost is at most \[m_0n+\mu(e_2)+\eta n \leq m_0n+\mu(e_2)+Ks/4 <m_0n+Ks.\] This proves (14) when \(n\to\infty\).

If \(n\) remains bounded, direct lattice paths from \(0\) to \((n,\lfloor bn\rfloor)\) use a bounded number of edges and remain in a bounded transverse region with \(0\leq x\leq n\). Their costs are bounded in probability, whereas \(Ks\to\infty\). This proves the same assertion for bounded \(n\). The two cases give the joint limit in (14) by the subsequence criterion.

The first dyadic threshold. Lemma 9 shows that the dyadic integer \(2^{3k}\) satisfies (15) for all sufficiently large \(k\). Thus \(L_k\) exists and has the stated upper bound. If \(L_k/2^k\) failed to tend to infinity, a subsequence would satisfy \(L_k\leq C2^k\) for some fixed \(C\), contradicting (14) and (15). The last assertion follows from the definition of the first dyadic length; it uses no monotonicity in \(n\) of the events \(E(s,n)\). ◻

Proof. The positive sequence \(L_k2^{-4k}\) is at most \(2^{-k}\), so it tends to zero and has infinitely many strict record minima. Take these indices for \(\mathcal K\). At a record index \(k\), comparison with \(k-j\) gives \[L_k2^{-4k}\leq L_{k-j}2^{-4(k-j)},\] which is (17). ◻

Proof. Let \(F_{\kappa,\lambda}\) be the Gamma distribution function and define its quantile function by \[\Phi(u)=F_{\kappa,\lambda}^{-1}(u)\quad(0\le u<1), \qquad\Phi(1)=+\infty.\] Here \(\Phi(0)=0\). The density is positive for every \(t>0\), so the distribution function is continuous and strictly increasing from zero to one. Consequently \(\Phi\) is increasing and continuous on \([0,1)\). Represent the independent weights as \[\tau_e=\Phi(U_e),\qquad U_e=\sum_{h\ge1}2^{-h}B_{e,h},\] where all \(B_{e,h}\) are independent Bernoulli variables of parameter \(1/2\). At precision \(t\) put \[U_e^{(t)}=2^{-t}+\sum_{h=1}^t2^{-h}B_{e,h}, \qquad \tau_e^{(t)}=\Phi(U_e^{(t)}).\] Then \(U_e^{(t)}\downarrow U_e\); because \(U_e<1\) almost surely, continuity of \(\Phi\) gives \(\tau_e^{(t)}\downarrow\tau_e\) almost surely on the finite union of the edge sets under consideration. Define \(A_j^{(t)}\) and \(D^{(t)}\) by using these rounded weights.

At each fixed precision, the events \(A_j^{(t)}\) are decreasing events of finitely many independent bits. Fixing all precision-\(t\) bits of the edges of a witnessing path forces its strict cost inequality regardless of the other bits. Edge-disjoint path witnesses thus give disjoint bit certificates. Complement the bits so that the events are increasing. For each certificate, retain its realized one-bits and set every other bit to zero. This configuration still belongs to the event, because it agrees with the realized configuration on the certificate, and its one-set lies inside that certificate. Disjoint certificates therefore give disjoint positive witnesses in the convention of (Berg and Kesten 1985); any unused one-bits can be assigned by monotonicity. The finite Bernoulli BK inequality (Berg and Kesten 1985, Theorem 3.3, Equation (3.4)), iterated over the list, gives \[\mathbb P(D^{(t)})\le\prod_{j=1}^q\mathbb P(A_j^{(t)}) \le\prod_{j=1}^q\mathbb P(A_j).\] Monotone disjoint occurrence is associative, so iteration allows repeated events. The second inequality follows from \(\tau_e^{(t)}\ge\tau_e\).

The events \(D^{(t)}\) increase with \(t\). A fixed finite list of original witnessing paths involves finitely many traversals. Its rounded path costs decrease to the original costs, so every strict inequality holds at all sufficiently fine precisions. Conversely, every rounded witness remains a witness with the original weights. Therefore, up to a null set, \[D(A_1,\ldots,A_q)=\bigcup_{t\ge1}D^{(t)}.\] Continuity of probability from below proves (29). No bound on the Gamma density or on the derivative of its quantile function is used, so the proof includes \(0<\kappa<1\). ◻

Proof. There are three possible exit behaviors. A transverse exit uses the slope gap, a backward exit has large defect by nonnegativity, and a forward exit reduces to the crossing event after controlling its outer pieces.

If \(\left\lvert r(\Delta Q)\right\rvert\ge s\), the support identity gives \[\min_{\sigma\in\{-,+\}}H_\sigma(Q) =H(Q)-c\left\lvert r(\Delta Q)\right\rvert <(\eta-c)s\le-3\eta s<-\eta s.\] The whole chunk is then a witness for the first defining event.

Otherwise a longitudinal exit occurred, and \(x(\Delta Q)\in\{-2L,2L\}\). In the negative case, nonnegative weights and (32) imply \[H(Q)\ge2m_0L-\left\lvert a\right\rvert(s+1)>\eta s,\] contrary to the hypothesis.

It remains to consider \(x(\Delta Q)=2L\). The initial column is strictly to the left of \((i+1)L\), and the final column is at or to the right of \((i+2)L\). Let \(z\) be the first vertex of \(Q\) on column \((i+2)L\), and let \(p\) be the last vertex on column \((i+1)L\) preceding \(z\). The subpath \(Q'\) from \(p\) to \(z\) stays between these two columns. Its transverse offsets from \(v_{i+1,h}\) have absolute value at most \(2s+2\le8s\). Consequently \(Q'\) fits inside the translate of the block defining \(E(s,L)\) at \(v_{i+1,h}\).

Write \(Q=Q_{\rm in}*Q'*Q_{\rm out}\), allowing an empty outer part. If either outer part has \(H<-\eta s\), it witnesses the first defining event, because it lies in \(\mathcal B_{i,h}\) and \(\min_\sigma H_\sigma\le H\). Otherwise additivity gives \(H(Q')<3\eta s\). Since \(\left\lvert r(\Delta Q')\right\rvert\le2(s+1)\), we obtain \[\tau(Q') <m_0L+3\eta s+2\left\lvert a\right\rvert(s+1) <m_0L+Ks.\] Thus \(Q'\) witnesses the second defining event. ◻

Proof. For each oriented nearest-neighbor 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 decreases from a value at least \(-\eta s\) to a value below \(-\eta s\). By (32), the defect of this prefix is at least \(-\eta s-C_f\ge-2\eta s\). Every split prefix is a witness for the original chunk’s event \(\mathcal A_{i,h}\): it remains in the same box, and \(\min_\sigma H_\sigma\le H<-\eta s\).

If this procedure splits off \(t\) prefixes, simplicity of \(P\) makes their edge sets disjoint, so \(t\le M_Q\). The unsplit final part has \(H\ge-\eta s\). Additivity now gives \[H(Q)\ge-\eta s-2\eta s t \ge-\eta s-2\eta s M_Q,\] which proves (34).

For a full chunk with \(M_Q=0\), Lemma 15 gives \(H(Q)\ge\eta s\). If \(M_Q\ge1\), then \[-\eta s-2\eta s M_Q \ge\eta s-4\eta s M_Q.\] This proves (35). Apply that bound to all full chunks and use (34), weakened to \(-\eta s-4\eta sM_Q\), on the remainder. Their sum is (36).

Finally, choose a family attaining \(M_Q\) in each chunk. Distinct chunks of a simple path have disjoint edge sets, so the union of these families is still edge-disjoint. The assertion does not require their associated events or their boxes to be distinct. ◻

Proof. First quantify how many witnesses a path of small defect must supply. Let \(B_N\) be the event that there exists such a simple path with \(N\) full chunks and \(H(P)<N\eta s/2\). If it occurs, (36) implies \[M_{\rm tot}>\frac N8-\frac14.\] For all sufficiently large \(N\), we may therefore select exactly \(t_N=\lfloor N/16\rfloor\) of the edge-disjoint witnesses supplied by Lemma 16.

Next count the possible event lists. List the chunk indices in order, including the index of the remainder. The first is \((0,0)\). Each coordinate of consecutive indices differs by at most \(3\), by the displacement bounds for a full chunk and (33). There are consequently at most \(49^N\) possible index itineraries. For a fixed itinerary, the numbers of selected witnesses in its \(N+1\) positions form a weak composition of \(t_N\). The number of these compositions is \[\binom{N+t_N}{t_N}\le2^{N+t_N}\le4^N.\] The allocation is indexed by positions along the itinerary, so repeated visits to one coarse cell retain separate positions. Each composition specifies a list of \(t_N\) events \(\mathcal A_{i,h}\), with repetitions when appropriate. Its selected witnesses certify disjoint occurrence of that list. Lemma 14 and (31) bound its probability by \((2q_0)^{t_N}\). There is no additional count of witness paths: that lemma bounds the existence of all choices of disjoint witnessing paths at once. Thus the path-dependent selection is covered by a union over deterministic itineraries and compositions. Taking this union yields \[ \mathbb P(B_N)\le196^N(2q_0)^{\lfloor N/16\rfloor} \tag{38}\] for all sufficiently large \(N\). All the events involved are measurable; in particular, finite lattice paths form a countable family.

Put \(p=2q_0\). Condition (30) implies \(0<p<1\) and \(196p^{1/16}<1\), while the right-hand side of (38) is at most \[p^{-1}\bigl(196p^{1/16}\bigr)^N.\] Thus \(\sum_N\mathbb P(B_N)<\infty\). The first Borel–Cantelli lemma proves the simultaneous eventual bound (37) for all the paths in the proposition. ◻

Proof. Fix an arbitrary deterministic \(b\in[-1,1]\) and suppose that \(c>0\). Make all the preceding choices for this \(b\), including the single fixed scale \(k\). For positive integers \(t\), let \[z_t=(t,\lfloor bt\rfloor).\] A path from \(0\) to \(z_t\) with \(N\) full chunks has \(N+1\) chunks when the remainder is included. Each changes the \(x\)-coordinate by at most \(2L\), so \[ N+1\ge\frac{t}{2L}. \tag{39}\]

Work on the probability-one event where the shape theorem and Proposition 17 both hold. For each \(t\), choose a finite path from \(0\) to \(z_t\) with cost at most \(T(0,z_t)+1\) and erase its loops. The resulting simple path \(P_t\) still has cost between \(T(0,z_t)\) and \(T(0,z_t)+1\), since the edge weights are nonnegative. The shape theorem gives \(T(0,z_t)/t\to m_0\), and \[f(z_t)=m_0t+a(\lfloor bt\rfloor-bt)=m_0t+O(1).\] It follows that \[ \frac{H(P_t)}{t}\longrightarrow0. \tag{40}\]

On the other hand, the numbers \(N_t\) of full chunks of \(P_t\) tend to infinity by (39). Proposition 17 therefore applies for all sufficiently large \(t\) and gives \[\liminf_{t\to\infty}\frac{H(P_t)}t \ge\frac{\eta s}{2} \liminf_{t\to\infty}\frac{N_t}{t} \ge\frac{\eta s}{4L}>0.\] This contradicts (40). Hence \(c>0\) is impossible, and convexity gives \(a_-=a_+\).

The choice of \(b\) was arbitrary and deterministic. The corner gap of the deterministic norm is itself deterministic, and the argument excludes a positive gap for each such \(b\). Accordingly the conclusion holds for every \(b\in[-1,1]\); no intersection of uncountably many probability-one events is being asserted or needed. ◻

Proof. By the joint stationarity of the edge and private inputs, it is enough to consider \(i=0\). Combining the centered cocycle identity with (47) gives \[P_{n,\omega}(X_1) =P_{n,\omega}(d) +P_{n,\theta_d\omega} \bigl(X_0(\theta_d\omega,\theta_dU)\bigr).\] The first term has mean zero; the second has the law of \(P_n(X_0)\). All terms are integrable because each cut lies on one of finitely many deterministic edges, where domination bounds its calibration value by a finite sum of weights and a deterministic linear term. Taking expectations proves the first identity, and (44) proves the second. The mean of \(P_n(X_0)\) itself need not vanish. ◻

Proof. A fixed vertex starts at most \(4\cdot3^{m-1}\) self-avoiding paths of length \(m\). For each path, independence and the identity \(\mathbb Ee^{-5\tau_e}=1/6\) give \[\mathbb P(\tau(\gamma)\le t)\le e^{5t}6^{-m}.\] Sum over paths and over \(m\ge R\) to obtain (49).

For the geodesic estimate, compare with a deterministic coordinate path of length \(\ell=|z|_1\) and cost \(S\). Its exponential moment gives \(\mathbb P(S>t)\le2^\ell e^{-t/2}\). Since weights are positive, a geodesic is self-avoiding. If it has at least \(R\) edges and \(S\le t\), it is counted by (49) with \(V=\{0\}\). Taking \(t=(\log2)R/10\) makes both probabilities exponentially small in \(R\) when \(R\ge40\ell\). The same estimate excludes arbitrarily long paths of bounded cost. Comparing with \(S\) therefore also proves existence of a finite minimizing path. ◻

Proof. We concatenate geodesics between closely spaced deterministic anchors, restricting each geodesic to a small ball to make the rule local. Choose an integer \(m\) large enough that, with \(\delta=1/m\), \[\delta\max(|A|_1,|B|_1)\le r/(1000K_{\mathrm{lat}}).\] Increase the fixed divisibility requirement so that \(n\delta A\) and \(n\delta B\) are lattice vectors. For \(d=A\) or \(B\), join successive deterministic anchors \(k\delta d\) by a minimizing path restricted to the lattice portion of the \(\|\cdot\|_*\)-ball of scaled radius \(r/4\) about the first anchor. Each microscopic edge has \(\|\cdot\|_*\)-length at most \(K_{\mathrm{lat}}/n\), so a coordinate path between the anchors stays within \(K_{\mathrm{lat}}\delta|d|_1\le r/1000\) of the first anchor. The restricted minimum therefore exists. Use a translation-covariant tie rule.

Restriction changes the minimum only if the unrestricted geodesic leaves the ball. Such a geodesic has at least \(rn/(4K_{\mathrm{lat}})\) edges, so Lemma 23, with integer rounding, bounds this event by \(Ce^{-c_s n}\) for large \(n\). On that event the increase is at most the coordinate-path cost \(S_k\). Since \((\mathbb ES_k^2)^{1/2}\le C_s n\), Cauchy–Schwarz bounds the expected increase by \(C_s n e^{-c_s n/2}\).

For each patch, Lemma 20 bounds the mean unrestricted cost above its norm value by \(C_s\sqrt n\log(2+n)\). The latter value is \(\mu(n\delta d)=n\delta h(d)\) because \(d\) lies in the cone of the face. Summing over the \(m\) patches in a unit period proves the first inequality in (50); increasing \(C'_s\) gives the second.

Parametrize each patch monotonically from \(k\delta\) to \((k+1)\delta\), for example proportionally to its number of edge occurrences. Its \(\|\cdot\|_*\)-distance from its nominal location is at most \(r/4+\delta\|d\|_*\le r/4+K_{\mathrm{lat}}\delta|d|_1<r\). The inputs for each patch lie within this same distance of every nominal point in the patch. Thus the radius-ten locality condition holds. The rule commutes with translation by \(d\), and each period has finite expected cost. This proves admissibility. ◻

Proof. Two routes around a large square have small expected defects if \(\beta\) is small. We decrease weights near the middle of one route, leaving the other route and their common endpoints fixed. The first route then becomes a cheaper competitor, while the change in law is small enough to transfer that saving back to the original environment.

The two routes. Fix an admissible pair with common bound \(\beta\). Write \((\xi,\eta)=[A\ B]^{-1}x\) for its oblique coordinates, and put \(\rho=2r\). Choose the fixed even integer \[L=200.\] Use four translated roads, with nominal lines \[\begin{aligned} \eta=0,\quad\eta=L &\quad\text{for the two $A$-roads},\\ \xi=0,\quad\xi=L &\quad\text{for the two $B$-roads}. \end{aligned}\] They use the same physical edge weights and independent private inputs. Their strips have oblique half-width at most \(\rho\).

At each nominal corner, determine the intersection from parameter windows of half-width \(4\rho\) on the two incident roads. One road crosses the square of coordinate half-width \(2\rho\) from left to right inside its horizontal strip, and the other crosses from bottom to top inside its vertical strip. The elementary planar crossing property for a rectangle gives an intersection. Nearest- neighbor lattice edges can meet only at a common vertex or along a common edge. If \(K_{\mathrm{lat}}/n\le r\), a common vertex can be chosen with coordinate distance at most \(2\rho\) from the corner and with both nominal parameters within \(3\rho\) of their corner values: moving from an interior intersection to an endpoint of its edge costs at most \(2K_{\mathrm{lat}}/n\le\rho\) in coordinates, after which tracking costs at most another \(\rho\) in nominal parameter. The chosen vertex remains in the inspected windows. Select the lexicographically first eligible vertex and then the first pair of eligible occurrences. These finite choices give a measurable local corner rule.

The bottom and right sides, traversed forward between these selected corners, form \(R_1\); the left and top sides form \(R_2\). Their initial and terminal vertices agree. Since \(3\rho<1\), every side used is a subpath of the periods with indices \(-1,0,\ldots,L\). Nonnegative defects and Lemma 22 give, with \(C_R=2(L+2)\), \[ \mathbb ED_n(R_j)\le C_R\beta,\qquad j=1,2, \qquad |\tau(R_1)-\tau(R_2)|\le D_n(R_1)+D_n(R_2). \tag{52}\]

A region traversed by only one route. Consider the deterministic middle-side parallelogram \[S=\{(L/2)A+uA+vB:|u|\le2,\ |v|\le2\},\] and let \(\mathcal E_n(S)\) be the edges having both endpoints in \(S\cap\mathcal G_n\). The entire input support of \(R_2\), including its selected endpoints and the middle corner, is outside \(S\). Indeed that support is contained in the \(\|\cdot\|_*\)-neighborhood of radius \(10\) of the deterministic union \(\mathcal C\) of the left and top nominal segments and all incident nominal corner windows of parameter half-width \(4\rho\). The coordinate distance from \(S\) to \(\mathcal C\) is at least \(L/2-2-4\rho\). By (45), its \(\|\cdot\|_*\)-distance is at least \(\tfrac34(L/2-2-4\rho)>10\). The same separation holds for the unused corner window. Thus changing only weights in \(\mathcal E_n(S)\) leaves \(R_2\) and its endpoints unchanged, even when its rule and corner selections are recomputed.

The bottom-road portion with nominal parameters between \(L/2-1\) and \(L/2+1\) belongs to \(R_1\). For sufficiently large \(n\), every edge meeting this portion has both endpoints in \(S\). Discarding the first and last partial edges leaves endpoints with coordinate separation at least \(2-2\rho-4K_{\mathrm{lat}}/n\ge1\). Each microscopic edge has \((A,B)\)-coordinate length at most \(2K_{\mathrm{lat}}/n\), so the resulting lattice path has at least \(n/(2K_{\mathrm{lat}})\) edges, up to integer rounding. Loop erasure preserves the endpoints and their separation, so the resulting self-avoiding path obeys the same length bound and has no greater cost.

There are at most \(C_V n^2\) vertices in \(S\cap\mathcal G_n\), where one may take \(C_V=(8M+3)^2\). Apply Lemma 23 with \[R=\lfloor n/(2K_{\mathrm{lat}})\rfloor,\qquad a_*=(\log2)/(40K_{\mathrm{lat}}),\qquad t=a_*n.\] For \(n\ge4K_{\mathrm{lat}}\) the resulting bound is \[ \mathbb P\left( \text{the cost of $R_1$ charged to $\mathcal E_n(S)$ is below $a_*n$} \right) \le q_n:=C n^2e^{-cn}, \tag{53}\] The constants \(c,C>0\) depend only on \(K_{\mathrm{lat}},M\). Uniformity in the road rule follows because the cheap-path event includes every self-avoiding path starting at every vertex of \(S\).

Perturbation and transfer of the saving. Keep the private inputs fixed. For \(0<\varepsilon\le1/2\), put \(a_n=1-\varepsilon/n\) and multiply every weight in \(\mathcal E_n(S)\) by \(a_n\). Let \(\mathbb P\) be the original joint law of weights and private inputs, and \(\mathbb Q\) its pushforward under this map. Write \(m_n=|\mathcal E_n(S)|\). Since each vertex is charged at most two undirected edges, \(m_n\le C_E n^2\), where \(C_E=2C_V\). The relative entropy of a scaled exponential variable with respect to an unscaled one is \(a_n-1-\log a_n\). Product additivity, followed by Pinsker’s inequality (Erven and Harremoës 2014, Theorem 31, order one), with total variation taken as one half of the \(L^1\) distance, gives \[ \begin{split} D_{\mathrm{KL}}(\mathbb Q\Vert\mathbb P) &=m_n(a_n-1-\log a_n)\le C_E\varepsilon^2,\\ \|\mathbb Q-\mathbb P\|_{\mathrm{TV}} &\le C_{\mathrm{TV}}\varepsilon, \qquad C_{\mathrm{TV}}=\sqrt{C_E/2}. \end{split} \tag{54}\] Here we used \(-x-\log(1-x)\le x^2\) for \(0\le x\le1/2\).

Set \(\lambda=a_*\varepsilon/2\). Let \(E\) be the event that the cost of the current \(R_2\) exceeds passage time between its current endpoints by at least \(\lambda\). This event uses only the current \(R_2\), its endpoints and the passage metric. In the perturbation coupling, outside the event in (53), the old \(R_1\) saves at least \(a_*\varepsilon\). It still joins the endpoints of the unchanged \(R_2\). If its old cost exceeded that of \(R_2\) by at most \(\lambda\), it is therefore a competitor cheaper by at least \(\lambda\) after perturbation. Equation (52) and Markov’s inequality give \[\mathbb Q(E) \ge1-q_n- \mathbb P\bigl(D_n(R_1)+D_n(R_2)>\lambda\bigr) \ge1-q_n-\frac{2C_R\beta}{\lambda}.\] Only the old \(R_1\) is used as a competitor; its recomputed rule may produce a different path. Transferring \(E\) to the original law by (54) yields \[\mathbb P(E) \ge1-q_n-C_{\mathrm{TV}}\varepsilon -\frac{2C_R\beta}{\lambda}.\] In the original environment domination implies \(D_n(R_2)\ge\lambda\) on \(E\), also for its random endpoints. Hence \[C_R\beta\ge\lambda\mathbb P(E) \ge\lambda(1-q_n-C_{\mathrm{TV}}\varepsilon)-2C_R\beta.\] Fix \(\varepsilon>0\) with \(C_{\mathrm{TV}}\varepsilon\le1/8\) and then take \(n\) large enough that \(q_n\le1/8\). Rearranging yields \[\beta\ge \frac{a_*\varepsilon}{8C_R}=:c_0>0.\] The constants in \(c_0\) depend only on the uniform geometry bounds and the fixed locality radius. Taking the infimum over admissible pairs proves (51). The transfer used the event \(E\), so no comparison of calibrations in the two environments was needed. ◻

Proof. We build a grid from the two road families, then attach any additional anchor to that grid by a bounded signed trip. Put an \(A\)-road on each line \(jB+\mathbb RA\) and a \(B\)-road on each line \(iA+\mathbb RB\). Write physical coordinates in the basis \((A,B)\). The coordinate-conversion bound implies that the first road lies in \(|x_2-j|\leq\delta\) and the second in \(|x_1-i|\leq\delta\), where \(\delta=2r\). Take \(r_0=1/100\), so \(8\delta<1/2\).

The portions whose nominal parameters are within \(4\delta\) of the nominal crossing connect opposite sides of a small rectangle. The planar crossing property gives an intersection of the two portions. An intersection lies in both strips and hence within coordinate distance \(\delta\) of the nominal crossing. Nearest-neighbor paths meet at a common vertex or along a common edge. Each scaled edge has \((A,B)\) coordinate length at most \(2K_{\rm lat}/n\leq\delta\); a vertex of that edge therefore has coordinate distance at most \(2\delta\) from the crossing and nominal parameter distance at most \(3\delta\) on either road. It lies within the inspected portions. Choose the first such vertex occurrence along the \(A\) portion, breaking any remaining tie by its occurrence on the \(B\) portion. This choice uses only those two bounded portions, is covariant under lattice translations, and specifies \(X_{(i,j)}\) together with its occurrence label on each road. Loops and repeated visits cause no ambiguity because occurrences, rather than only vertex names, are used.

The disjoint parameter windows order neighboring intersections along the relevant road. Define \(E_{z,1}\) as the \(Q\)-cost of the intervening forward \(A\) portion, and define \(E_{z,2}\) using the \(B\) portion. Each portion lies in a fixed number of marked periods, so additivity and nonnegativity bound its expected defect by \(C\beta\). This proves (55).

Tracking and locality put all inputs in a fixed number of unit parallelograms. Assign boundary weights by a fixed half-open convention and private inputs to the cell of their nominal location. Since each microscopic input is assigned to one cell, the cell variables are independent.

To attach an additional anchor, follow its road with either sign to a nearby transverse network road, then follow that road to a network intersection. A bounded number of network intervals reaches any other anchor under consideration. All nominal distances are bounded, and crossings use the same local selection rule. The error on each signed interval is its signed defect, whose absolute value is bounded by complete-period defects. The triangle inequality gives the stated comparison. Its constant depends on the allowed anchor distance, independently of the number of other labels. ◻

Proof. We decompose a local increment according to the finite sets of cells on which it depends. Each component can be integrated locally; an exterior detour controls the error where that integration is cut off.

For a nonempty finite \(S\subset\mathbb Z^2\), define \[\Pi_S F=\sum_{I\subset S}(-1)^{|S|-|I|} \mathbb E[F\mid\mathcal F_I].\] These are finite-product ANOVA (Hoeffding) projections; see Efron and Stein (Efron and Stein 1981, sec. 2) for the classical square-integrable decomposition. Here we use only finite inclusion–exclusion identities in \(L^1\). Each projection has mean zero and \(L^1\) operator norm at most \(2^{|S|}\). If \(F\) is measurable with respect to a finite cell set \(N\), then \(\Pi_SF=0\) unless \(S\subset N\), and \[ F=\mathbb EF+\sum_{\varnothing\ne S\subset N}\Pi_SF. \tag{59}\] Cancellation and independence prove both identities directly in \(L^1\); no infinite or \(L^2\) expansion is involved.

A comparison supported on \(Q_H(z)\) has components only on sets of at most \(m=(2H+1)^2\) cells and diameter at most \(2H\). Accordingly, let \(\mathscr S\) be the collection of nonempty finite sets \(S\) with \(|S|\leq m\) and \(\operatorname{diam}_\infty S\leq2H\). Let \(k(S)\) be the lexicographically least point of \(S\), put \[U_S=Q_R(k(S)),\qquad z_S=k(S)+(R+4H+10)e_1,\] and use \(z_S\) as a reference beyond the cutoff \(U_S\). Define \[ g_{z,\lambda}=\mathbb EV_{z,\lambda} +\sum_{\substack{S\in\mathscr S\\z\in U_S}} \Pi_S\bigl(V_{z,\lambda}-V_{z_S,0}\bigr). \tag{60}\] There are only a bounded number \(N_H\) of summands: \(k(S)\) must lie in \(Q_R(z)\) and \(S\subset Q_{2H}(k(S))\). For example \(N_H\leq(2R+1)^2 2^{(4H+1)^2}\) suffices. Every summand is measurable with respect to cells in \(Q_{R+2H}(z)\) and has mean zero. This proves locality and (57).

The cutoff error. Suppose \(z\in U_S\) but a neighbor \(z'\) lies outside. There is a lattice path from \(z\) to \(z_S\) of length at most \(20(R+4H+10)\) lying outside \(Q_{R-2}(k(S))\): follow the boundary of \(Q_R(k(S))\) to its eastern side and then move east. Every local support \(Q_H(u)\) along this path is disjoint from \(S\subset Q_{2H}(k(S))\). If necessary first switch from label \(\lambda\) to label \(0\) at \(z\). By (56), telescoping and the projection norm, \[ \left\|\Pi_S(V_{z,\lambda}-V_{z_S,0})\right\|_1 \leq [20(R+4H+10)+1]2^m\varepsilon. \tag{61}\] Each local comparison has zero \(\Pi_S\) projection because its support misses \(S\). The connected exterior in two dimensions is used exactly at this step.

Recovery of an increment. Consider an edge \((z,\lambda),(z',\lambda')\) from the hypothesis and write \(W=V_{z',\lambda'}-V_{z,\lambda}\) and \(E\) for its local comparison. The centered variables satisfy \(\|W-\mathbb EW-E+\mathbb EE\|_1\leq2\varepsilon\). Every nonempty subset of \(Q_H(z)\) contributes to both endpoint gauges, since \(R>H+1\). A set contributing at both endpoints gives \(\Pi_SW\), within \(2^m\varepsilon\) of \(\Pi_SE\); this latter projection vanishes when the set is not contained in \(Q_H(z)\). A set contributing at only one endpoint is controlled by (61). Thus (59), the centered error bound above and at most \(2N_H\) component errors prove (58). For a same-index label change there are no cutoff terms.

Finally, the choices \(k(S)\), \(U_S\) and \(z_S\) commute with index translations. The random summands in (60) contain only differences of \(V\), so a random common additive constant under translation cancels. Covariance of the increments and the deterministic means therefore passes to the gauge. ◻

Proof. Use the same deterministic coarse cell partition in every world. Within each cell, group the common tube coordinates, common private coordinates, and additional coordinates of that world. These cells are independent. Until we establish that a projection is common to all worlds, \(\Pi_S\) denotes the finite-cell projection in the product space of the world under consideration.

We first replace each calibration difference in the gauge formula by a common baseline cost. Let \(x\) be the anchor’s coarse index, and choose a marked anchor \(y\) on the same baseline, a fixed integer number \(L_0\) of periods earlier. Take \(L_0\) large enough that \(y\) lies outside every cutoff \(U_S\) contributing at \(x\) in (60), with an additional margin of \(4H+20\). The coordinate-conversion bound allows one choice of \(L_0\) for all \(0<s<1/4\).

Let \(Q_{y,x}\) be the forward baseline cost from \(y\) to \(x\). The traveled edges lie in the baseline’s own preserved tube, and the path and its marked occurrences depend only on \((\eta_0,\xi)\). Thus \(Q_{y,x}\) is the same random variable in every world. Adding the period defects along this fixed number of periods gives \[\|Q_{y,x}-P^j(X_x)+P^j(X_y)\|_1\leq C\beta.\]

Fix a contributing set \(S\). Attach \(y\) to the comparison network locally near \(y\), and connect that network anchor to the reference anchor at \(z_S\) by signed comparisons along the boundary of \(Q_R(k(S))\) and its exterior. Such a route can reach the square’s boundary, follow it to the eastern side, and then move east to \(z_S\), just as in the cutoff argument leading to (61). The initial attachment is separated from \(S\) by the margin at \(y\). Along the remaining route, the local supports \(Q_H(u)\) miss \(S\subset Q_{2H}(k(S))\), since \(R=8H+20\). The route has bounded length: \(L_0\) is fixed, \(k(S)\in Q_R(x)\), and \(z_S-k(S)\) is fixed by the gauge construction.

Every local comparison on this route therefore has zero \(\Pi_S\) projection. Telescoping their calibration differences, using their \(O(\beta)\) errors and the bounded projection norm, yields \[\|\Pi_S(P^j(X_y)-P^j(X_{z_S,0}))\|_1\leq C\beta.\] Combining this estimate with the preceding baseline estimate shows that each summand of \(g_x^j\) differs by \(O(\beta)\) from \(\Pi_SQ_{y,x}\).

It remains to check that these projected baseline costs, including the deterministic mean term, are common to all worlds. The joint marginal law of the world weights and the shared baseline is the same in every world: the baseline uses its own tube weights together with private inputs independent of that world’s actual exterior. Since the calibration map is also the same, the mean \(m_x=\mathbb EP^j(X_x)\) is independent of \(j\). Define \[g_x^{\rm in}=m_x+ \sum_{\substack{S\in\mathscr S\\x\in U_S}} \Pi_SQ_{y,x}.\] For any cell subset, conditioning \(Q_{y,x}\) on its independent \(\eta_{\rm other}\) or \(\zeta^j\) coordinates adds no information to its \((\eta_0,\xi)\) coordinates. Consequently, every conditional expectation in \(\Pi_SQ_{y,x}\) is a function only of that subset’s \((\eta_0,\xi)\) coordinates. These conditional expectations, and hence the projections themselves, can be chosen as the same functions in every world. They have no dependence on weights in the other preserved tubes.

Only a fixed number of sets \(S\) contributes, all within the fixed support radius of (60). Summing the projection errors proves (66) and locality, with constants independent of the number of worlds. The displayed construction also proves the independence assertion: disjoint baseline tubes supply disjoint sets of product edge weights, their private input collections are independent, and \(m_x\) is deterministic.

Finally, interpolate the common anchor gauges using the common raw baseline cost. In (63), the raw \(Q\) terms cancel when the two interpolations are subtracted. For \(t\in[i,i+1]\), their discrepancy is therefore the linear interpolation of the discrepancies at \(i\) and \(i+1\). Its supremum is bounded by the sum of those two anchor discrepancies. A bounded interval meets only a bounded number of periods, which proves the stated expected supremum bound. ◻

Proof. We first check phase dependence, including that of the conditional expectations used to construct a gauge. An anchor is determined by local weights, local private inputs, and the phases of the roads in a fixed neighborhood. The calibration itself depends on the weights alone. Each projected variable in (60) is the difference of calibration values at two anchors: the anchor carrying the gauge label and the reference anchor indexed by \(z_S\). Both anchors lie within a fixed distance of the gauge’s location. Indeed, for a gauge indexed by \(z\), one has \(k(S)\in Q_R(z)\) and \(z_S=k(S)+(R+4H+10)e_1\).

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. This applies to every projection and to the deterministic anchor mean in the gauge formula. The number of potentially involved \(B\)-wall indices is bounded by their spatial range, independently of the number of possible phase values. The spatial support of each projection is the one given by Lemma 27.

All mesh offsets lie in one bounded fundamental cell. Thus the supports of the gauges being averaged lie in one fixed larger neighborhood, 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, namely the expected calibration value at that anchor, so averaging preserves this mean. For a switch between two labels, the triangle inequality applied to the average of their within-mesh gauge differences preserves the switch estimate without a factor \(|\mathcal H|\). Interpolation is affine in the anchor gauges and uses the same physical road cost on every mesh. It therefore commutes with averaging. The construction from the preserved incoming road can be averaged in the same way; its common-tube comparison and its dependence only on the baseline’s own tube inputs and private field are preserved.

Translation by \(A\) advances the wall index by one and the absolute row height by \(s\). Since \(\theta_j=js+\phi_j\), its action on relative phases is the ordinary shift of the sequence \((\phi_j)_{j\in\mathbb Z}\). The road rules, spatial inputs, and gauge construction are covariant under this joint translation, giving covariance under \(A\). Translating the decorated network by \(aB\), \(a\in\mathcal H\), adds \(a\) modulo one to every wall phase and permutes the offset meshes. Integer carries are absorbed by unit-period covariance. The independent uniform phase law is invariant under this addition, and the spatial product law is translation invariant. This proves the asserted covariance of the row laws.

Finally, the non-phase inputs for an entire column lie in a strip of fixed width about that column. Sufficiently separated columns have disjoint strips and disjoint finite sets of wall-phase indices. The 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. The strip width and the range of wall indices are independent of \(|\mathcal H|\) and \(\sigma\), as required. ◻

Proof. First suppose all indicators are independent. If a path visits \(\ell\) distinct marked sites, list them in their order of first encounter as \(z_1,\ldots,z_\ell\). 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 \(\ell^1\) length \(d\). The number of possible lists is therefore at most \[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.\] The identity follows from \(\sum_{d\ge0}(d+1)x^d=(1-x)^{-2}\), followed by summing coefficients through degree \(L\). The count includes lists that cannot occur along a path, which only increases the bound.

Distinctness makes the probability that a specified list is marked at most \(p^\ell\). If \(M_L\) is the maximum in the statement and \(a=C(L+1)\sqrt p\), the union bound gives \[ \mathbb P(M_L\ge\ell) \le\min\{1,(a/\ell)^{2\ell}\}. \tag{68}\] For \(a\le1/2\), summing over \(\ell\ge1\) gives at most \(\sum_{\ell\ge1}a^{2\ell}\le2a^2\). For \(a>1/2\), split at \(\lceil2a\rceil\): the initial sum is \(O(a)\) and the remaining sum is geometric. Thus \(\mathbb EM_L\le C\min\{a,a^2\}\), after adjusting constants also for \(1/2<a<1\). Combining this with \(M_L\le L+1\) proves (67).

For a partition into independence classes, apply the same list count to sites in each class and sum the resulting \(q\) maxima. No independence between classes is needed. For example, when \(I_z\) depends on independent inputs in \(z+[-R,R]^2\), residue classes modulo an integer greater than \(2R\) give the required partition. The same partition argument works when sigma-fields generated by sets at distance greater than a fixed range are independent.

Only the budget for successive distances entered the counting argument, so it also proves the assertion about lists. An invertible linear identification of a fixed full-rank lattice with \(\mathbb Z^2\) changes this budget by a fixed factor and proves the lattice version. ◻

Proof. For \(u\ge0\), \[u\mathbf1_{\{u>T\}} =T\mathbf1_{\{u>T\}}+ \int_T^\infty\mathbf1_{\{u>t\}}\,dt.\] Take the supremum over paths, move it inside the nonnegative integral as an upper bound, and apply Lemma 34 at every level. Tonelli’s theorem gives (69), possibly with an infinite right-hand side. Integrating \(\sqrt A\,t^{-2}\) proves the fourth-power assertion.

The sharper minimum of \((L+1)\sqrt{p(t)}\) and \((L+1)^2p(t)\) in (67) can also be used inside the integral. In particular, the estimate has no additive constant independent of \(t\) to be integrated over an infinite interval. ◻

Proof. Before selecting an object, form \[V=\max_{(c_1,\ldots,c_m)}\min_{1\le i\le m}U_{c_i},\] where the maximum ranges over all tuples in the region with pairwise disjoint supports, including those that no admissible object supplies. Set \(V=0\) if there are no such tuples. This is a local variable and gives the required simultaneous domination. For each fixed tuple, independence and Markov’s inequality bound the probability that all \(m\) values exceed \(t\) by \(\min\{1,(A/t)^m\}\). There are at most \(J^m\) tuples, so a union bound proves the tail estimate. Finally, \[\mathbb EV^4=4\int_0^\infty t^3\mathbb P(V>t)\,dt<\infty \qquad(m>4).\] The conditional proof is identical. The object itself may depend on the whole environment: independence is used only for each fixed tuple, before taking the finite maximum. ◻

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. 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 a null set, by its neighboring tiles on the other side. It therefore has at least \(k\) neighbors. Both finite Hall conditions hold.

Here is the compactness step giving a perfect matching. By finite Hall’s theorem (Hall 1935, Theorem 1), any prescribed finite set of left vertices is covered by a finite matching \(M_1\), and any prescribed finite set of right vertices by a finite matching \(M_2\). The union of the two matchings consists of alternating paths and cycles, together with common edges. On each component one can choose an alternating matching covering all prescribed vertices. Internal vertices are covered by either choice. On an odd-length path, one choice covers both endpoints. On an even-length path, the endpoints lie on the same side, and the matching that covered the prescribed vertices on that side already covers every prescribed endpoint. Thus one matching covers both prescribed finite sets.

Exhaust the two vertex sets by finite sets and choose such a matching at each stage. A diagonal subsequence converges on every edge. Since each vertex has finite degree and is covered at all sufficiently large stages, exactly one of its incident edges belongs to the limit. The limit is a perfect matching.

Let \(\psi(z)=w\) for the matched pair. An intersection point has the form \(Tz+Tq=w+q'\), with \(q,q'\in Q\), giving the stated displacement bound. Translate the first tiling by \(a\) to obtain the affine statement, with the same error relative to \(Tz+a\). ◻

Proof. The scalar prefactor makes the determinant one. In \(E\)-coordinates, the map contracts the first extent of the box by \(F\) and expands the second by \(F\). The prefactor and \(U\) have uniform bounds, so the transformed diameter is at most \(C(N/F+F\delta N)+C_F\). The fundamental-tile bound in Lemma 37 bounds the matching error uniformly in \(E\) for fixed \(F\). Adding this error proves (72). Its \(N\)-dependent coefficient \(C\) is independent of \(F\); the deformation of the fixed margins and the matching error are included in \(C_F\).

For \(v=z_j-z_i\), condition (70) gives \(v=Ea+e\) with \(a\ge0\) coordinatewise and \(|e|\le CH\). The vector \(T_FEa\) is in the cone generated by \(u_1,u_2\), strictly inside \(\mathcal K\). Consequently its distance to the complement of \(\mathcal K\), and each of its positive coordinates, are at least \(\rho_{\mathcal K}|T_FEa|\) for a fixed \(\rho_{\mathcal K}>0\). For fixed \(F\), \[|T_FEa|\ge c_F(|v|-CH),\qquad |T_Fe|\le C_FH,\] with \(c_F>0\). Replacing \(T_Fv\) by \(\psi_F(z_j)-\psi_F(z_i)\) adds at most twice the matching error. Choose \(R_F\) so that the cone margin and the two coordinate margins exceed these errors plus \(r_0\) whenever \(|v|>R_F\). Compactness of the allowed matrices makes this choice uniform in \(E\). ◻

Proof. Fix a law and \(t>0\), and set \(p=\mathbb P(Y_z>t)\). There is nothing to prove if \(p=0\). Otherwise choose \(L\) comparable to \(p^{-1/2}\), with lattice-dependent comparison constants, so that \(L\ge1\) and \([-L,L]^2\) contains at least \(p^{-1}\) lattice sites. Independence implies that some value in the square exceeds \(t\) with probability at least \(1-e^{-1}\). Since singletons are allowed in \(G\), \[(1-e^{-1})t\le\mathbb EG_n(L,0) \le C_0L+C_1\le Cp^{-1/2}.\] Rearrange and combine with \(p\le1\). The constants do not depend on the law. ◻

Proof. Fix \(F\), and take \(R_F\) from Lemma 38. We divide the selected values into nearby collisions, which have a lighter tail, and one separated set, to which the collection bound applies.

Collision values. Define the local field \[D_z=Y_z\mathbf1_{\{\exists w\in\Lambda:\ 0<|w-z|\le R_F, \ Y_w\ge Y_z\}}.\] If \(D_z>t\), both \(Y_z\) and one distinct neighboring value exceed \(t\). Independence and Lemma 39 give \[ \mathbb P(D_z>t) \le\sum_{0<|w-z|\le R_F}\mathbb P(Y_z>t,Y_w>t) \le C_F\min\{1,t^{-4}\}. \tag{75}\] This argument includes laws with atoms. The dependence range of \(D\) is fixed once \(F\) is fixed. The path budget and Corollary 35 therefore bound the expected supremum of its selected tail sums by \(C_F(N+1)/T\).

Separated values. For any admissible sequence, keep one occurrence of each site in its original order and pay a factor \(m_0\) for multiplicity. Among these sites with \(Y_z>T\), process values in decreasing order, breaking ties by a fixed deterministic order. Retain a site if its distance from every previously retained site is greater than \(R_F\). Every discarded site has a distinct retained neighbor with at least its value, so its value equals \(D_z\). The retained sites are pairwise separated by more than \(R_F\).

Put the retained sites back in their original order. The all-pairs order condition still holds, so their images under the deterministic bijection \(\psi_F\) form an admissible directed chain. They lie in a deterministic square with radius \[L_F=\max\{1,C(N/F+F\delta N)+C_F\}.\] The transported field \(\widetilde Y_w=Y_{\psi_F^{-1}(w)}\) has exactly the original iid law. Thus the retained reward is at most the corresponding \(G_n(L_F,x_F)\) in this transported field, for a deterministic center \(x_F\).

Crucially, the same square and the same field permutation work for every original admissible sequence. Hence this domination holds after taking the supremum over those sequences, even though the pruning and the retained chain depend on the observations. By (73), its expectation is at most \[C(N/F+F\delta N)+C_F\le CN/F+C_F \qquad(\delta\le F^{-2}).\] Add the collision estimate and absorb the fixed factor \(m_0\) to obtain (74).

Choose \(F\) first so that \(C/F<\varepsilon/3\), then choose \(T_0\) so that \(C_F/T_0<\varepsilon/3\), and set \(\delta_0=F^{-2}\). The remaining terms vanish after division by \(N(n)\to\infty\), uniformly over the laws. For finitely many types, bound the supremum of a sum by the sum of the suprema. For a finite-range field, first split into finitely many sublattices on which each fixed template has an iid law, provided the collection hypothesis holds for every such law. Apply the argument separately and sum. ◻

Proof. The case \(B=0\) is immediate. Otherwise fix a deterministic row and omission set. Split the centered sum into its \(q\) residue classes. Within each class the summands are independent, have support in intervals of length at most \(2B\), and number at most \(N/q+1\). For the total sum to have absolute value greater than \(\varepsilon N\), some class sum must have absolute value greater than \(\varepsilon N/q\). Hoeffding’s inequality (Hoeffding 1963, Theorem 2, Equation (2.6)) and a union bound therefore give, for \(N\ge q\), \[ 2q\exp\left(-\frac{\varepsilon^2N}{4qB^2}\right) \tag{77}\] as an upper bound on this probability.

It remains to count the choices over which the supremum is taken. Put \(V=\lfloor\delta N\rfloor\). For a fixed initial row, stars and bars gives \(\binom{N-1+V}{V}\) choices of the absolute increments with sum at most \(V\). Their signs have at most \(2^V\) choices. The total number of rows is therefore at most \[(2\lfloor N^d\rfloor+1)2^V\binom{N-1+V}{V} \le (2\lfloor N^d\rfloor+1) \exp\{Nh_{\mathrm{row}}(\delta)\},\] where \[h_{\mathrm{row}}(\delta) =\delta\log2+(1+\delta)\log(1+\delta)-\delta\log\delta \longrightarrow0\quad(\delta\downarrow0).\] For \(0<\eta\le1/2\), there are at most \((N+1)\exp\{Nh_{\mathrm{bin}}(\eta)\}\) omission sets, where \(h_{\mathrm{bin}}(\eta)=-\eta\log\eta-(1-\eta)\log(1-\eta)\). Choose \(\delta,\eta\) so that the two entropy terms sum to less than \(\varepsilon^2/(8qB^2)\). Multiplying the counts by (77) gives a polynomial factor times \(2q\exp\{-\varepsilon^2N/(8qB^2)\}\), uniformly in \(n\).

If rows are specified only at nonomitted columns, assume the same bound on their first specified row and on their successive jumps. Extend to the full interval by holding that first row on the initial gap and, at each later gap, holding the old row until the next specified column. Hold the last row on the final gap. This does not increase the total variation and gives a row counted above. Indicators have \(B=1\). For a fixed finite sum, apply the result to each summand with a divided tolerance, then use the triangle inequality and a finite union bound. Alternatively, the sum itself has a fixed bound and can be treated directly when its combined supports satisfy the column independence condition. ◻

Proof. For every \(u\ge0\), a geometric sum gives \[\sum_{j=0}^{J-1}2^jM_0\mathbf1_{\{u>2^jM_0\}}\le2u.\] Take expectations and sum over \(a\). At least one of the \(J\) resulting nonnegative summands is no larger than their average, which is at most \(2A/J\). ◻

Proof. For \(I\subseteq\mathcal N(c)\) put \(\mathcal F_I=\sigma(\eta_d:d\in I)\), and define \[W_c=\sum_{I\subseteq\mathcal N(c)} \mathbb E[U_c\mid\mathcal F_I].\] Independence of the input cells and measurability of \(U_c\) give \[\mathbb E[U_c\mid\mathcal F_{\mathcal D}] =\mathbb E[U_c\mid\mathcal F_{\mathcal D\cap\mathcal N(c)}].\] This is one of the nonnegative summands defining \(W_c\). There are at most \(2^{m_0}\) summands, each with expectation \(\mathbb EU_c\). Since only the finitely many intersections with \(\mathcal N(c)\) matter, versions can be chosen for which all the inequalities hold simultaneously. ◻

Proof. The nominal \(h\)-coordinate increases along either road at a fixed positive rate, and tracking changes it by a bounded additive amount. The slab condition therefore lets us pass the full observation halo by moving a fixed number of periods before the incoming window or after the outgoing window. The relevant transverse-road index is chosen from the deterministic test type. For example, on an incoming \(B\)-wall of nominal first coordinate \(i\), take the \(A\)-road of index \[j_a=\left\lfloor \frac{h(c_-)-M_0-\ell_1i}{\ell_2}\right\rfloor,\] where the fixed \(M_0\) exceeds the final slab padding \(b_0\), its input halo, and the support radius of a connector by a strict margin. Then use the canonical intersection of those two prescribed roads. On an incoming \(A\)-wall interchange the coordinates; for exits use the analogous ceiling above the upper face. Tracking changes the \(h\)-level by only \(O(\rho)\), absorbed by the margin. The chosen parameter differs by a bounded amount from the cut window. Thus the index choice uses no unrevealed input, and all possible attachment occurrences remain in fixed local windows.

The first and last road portions in the asserted concatenation are physical forward portions. Additivity of signed corrected costs gives \[\begin{aligned} C_{W_-}(a,x)&=C_{W_-}(a,x_0)+C_{W_-}(x_0,x),\\ C_{W_+}(y,b)&=C_{W_+}(y,y_0)+C_{W_+}(y_0,b). \end{aligned}\] Adding \(C_\pi(x,y)\) proves (84), whatever the relative orders of \(x,x_0\) and of \(y,y_0\). In particular, neither signed center arm has to be traversed backward. A label change at an exterior intersection adds the corresponding difference of the two local gauges. All extra signed travels and switches lie in the bounded windows of Section 6.1. Their absolute costs are therefore bounded by \(U_{c_-}+U_{c_+}\) after a fixed enlargement of those envelopes. ◻

Proof. Normalize the two costs together: \[S_c=W_c/\beta+V_c/a_n.\] By (79) and Lemma 43, \(\mathbb ES_c\le C\) uniformly. Increase the fixed support radius \(R_0\) to include the cell diameter.

Separated candidates. Choose \(m\) nested annuli about a potential exit mark, with annulus widths larger than the diameter bound for a component of the road complement, and with gaps larger than \(4R_0\). Also choose an integer \(J>2R_0+1+2\rho\). Take \(H_m\) large enough that all annuli fit inside its ball and \(H_m>(m-1)J+2\rho+1\), then take \(K>20H_m\). On the path portion preceding an exit mark, use the last passage from the outer boundary of this ball to the mark. Its successive crossings of the annuli meet the road network; choose one occurrence at such a meeting in each annulus. If the mark is not at a cell center, allow every unit cell meeting the annulus enlarged by two cell diameters. The larger gaps ensure disjoint input supports for any candidate tuple having one cell in each enlarged annulus. The finite number of such tuples depends on \(K,m,R_0\), but not on \(n\).

One bound for every path. For the mark cell \(z\), let \(\mathcal T_z\) contain every possible annular tuple and every horizontal tuple described below, allowing all center offsets within \(z\), and set \[E_z=\max_{(c_1,\ldots,c_m)\in\mathcal T_z} \min_{1\le j\le m}S_{c_j}.\] A finite list of discretized annular and horizontal patterns suffices, because the allowed candidate sets are subsets of a fixed finite list of unit cells. For each fixed tuple, independence, Markov’s inequality, and the uniform mean bound give \[\mathbb P(S_{c_1}>t,\ldots,S_{c_m}>t)\le (C/t)^m.\] Taking the union over \(\mathcal T_z\) proves (86). The actual path supplies a tuple in this list. Choose the candidate minimizing \(S_c\), breaking ties by the deterministic cell and occurrence order. This gives (85) for every path on the same event, regardless of how that path was selected.

Geometry and gauges. The selected cut lies within \(H_m<K/10\) of its mark. A preliminary exit has displacement exactly \(K\) from the preceding mark, in the continuous max norm, so the triangle inequality gives the asserted displacement bounds. Each portion between preliminary marks stays in its \(K\)-ball. The two adjacent short terminal portions give the \(O(K)\) diameter bound. The selected cut occurs after the preceding preliminary mark, since that mark lies outside the small terminal ball. Thus the cuts preserve path order.

Finally, \[\mathbb P(a_nE_z>\varepsilon n) \le C_K\left(\frac{a_n}{\varepsilon n}\right)^m \le C_{K,\varepsilon}n^{-m\vartheta}.\] A union bound over \(O(n^q)\) mark cells proves the fourth assertion. The single objective \(S_c\) is essential here: it selects both bounds at once, so the same product estimate controls the charge and the gauge.

Horizontal terminal portions. Let \([t_-,t_+]\) be the terminal occurrence-time interval and let \(P\) linearly interpolate the fine cuts on their time intervals. The diameter bound gives \(|P(t)-\gamma(t)|_\infty\le\delta_f\) in the present coordinates. For \(t_-\le a\le b\le t_+\), the increment \(P(b)-P(a)\) is a sum of nonnegative multiples of the good fine increments. Hence, for \(\Delta=\gamma(b)-\gamma(a)\) in these coordinates, \[ \Delta_1\ge-2\delta_f,\qquad |\Delta_2|\le\kappa\Delta_1+2(1+\kappa)\delta_f. \tag{88}\] This includes both partial fine segments at the ends. At \(a=t_-,b=t_+\) we have \(|\Delta|_\infty=H_m\). The strict inequality in (87) excludes \(\Delta_1=-H_m\) and \(|\Delta_2|=H_m\), so \(\Delta_1=H_m\). Thus the last boundary hit is on the left face. By lastness and continuity, all later points of the terminal arc are in the open ball.

Put \(p_1=\xi_1(\gamma(t_-))\) and choose the wall levels \[i_j=\lfloor p_1+\rho\rfloor+1+(j-1)J,\qquad 1\le j\le m.\] Our choice of \(H_m\) gives \(p_1<i_j-\rho\) and \(\xi_1(\gamma(t_+))>i_j+\rho\). A proper \(B\)-road in each such vertical strip separates these two sides: apply the planar rectangle-crossing property to a bounded vertical road portion and a left-to-right subarc. Select the first meeting along the terminal arc. It is a vertex occurrence, since an interior meeting of two square-lattice paths lies on a common edge whose entering vertex would already be a meeting; the initial arc point is outside the wall. At repeated road visits choose the first eligible vertex occurrence in the bounded window determined by the cut cell. The first meetings with \(i_1,\ldots,i_m\) occur in that order, because reaching a later wall requires crossing every earlier wall. All of them lie strictly inside the terminal ball.

The center of a cell meeting \(W_{i_j}\) has first coordinate within \(\rho+1/2\) of \(i_j\). Distinct candidate centers are therefore separated by at least \(J-1-2\rho>2R_0\), so their input supports are disjoint. For a fixed mark cell all candidates lie in a fixed finite \((H_m+1)\)-neighborhood. The horizontal tuples were included in \(\mathcal T_z\) before the common objective was maximized, so the same product estimate applies without conditioning on the path or on its terminal test. The selected point stays on the terminal arc, preserving the preceding order and displacement bounds. ◻

Proof. Minimality gives \(c\ge-u\), and \(a_{\mathcal D}\ge0\) gives \[c^-\le u_+\le (u-a_{\mathcal D})_++a_{\mathcal D}.\] Lemma 43 bounds \(a_{\mathcal D}\) by the two \(W/\beta\) terms in (90).

On \(\{Y>0\}\), Lemma 44 realizes the internal minimizer with normalized corrected cost at most \(-u+(U_{c_-}+U_{c_+})/\beta\). Taking its conditional mean yields \(-u+a_{\mathcal D}=-Y\). The envelopes already bound every admissible attachment occurrence, so this estimate holds for the selected minimizer. ◻

Proof. Choose the chain and realize its route. Observe the inputs of every test in the sparse array. In the given finite square, choose a reward-maximizing chain, resolve ties lexicographically, and omit zero-reward sites. This is a function of the observations. Fix an external southwest and an external northeast corridor intersection, outside the square by \(3S\) in both coordinates, with the same prescribed intersection-label convention. These endpoints depend on the square, not on the observed chain.

Route monotonically on the corridor grid from the start to the southwest portal of the first selected cell, use that tunnel and its private access, then continue from its northeast portal to the next southwest portal. The assumed \(2S\) gaps make both coordinates of each latter displacement nonnegative, with a full corridor spacing to spare. Continue similarly to the fixed end. Every portion is a physical forward road portion or a physical internal tunnel path. Thus the result is an actual path.

Its total ordinary-corridor length is \(O(L+S)\), by telescoping the two positive coordinate increments. A chain has at most \(C(L/S+1)\) sites. The private uncharged connector lengths are \(O(S)\) per site, so their total length is also \(O(L+S)\). The number of road switches has the same bound when measured in unit road spacings. The two short charged attachments at each site are excluded from this count.

All selected route costs are integrable. A used tunnel has \(Y>0\) and therefore has negative center-label cost. Rearranging that cost identity bounds its positive physical passage cost by a bounded \(nh\) displacement and the integrable local gauge and raw-arm envelopes. Charged attachments and ordinary finite road portions are integrable by the same window estimates. The chain is finite, and its maximum reward is integrable by the bound following (89). Thus the conditional costs and the expectation rearrangements below are finite.

Take conditional expected costs. For every prescribed ordinary connector, its full input support misses all observations. Its inputs therefore retain their product law under the conditioning. Subdivide the connector into unit road periods and apply the local envelopes to those periods and its switches. Its expected normalized corrected cost is at most a constant times its nominal length plus its number of switches. Summing uses only linearity of conditional expectation; connectors may share unobserved inputs.

The support of a charged access envelope meets no observation other than its own test. Independence gives \[\mathbb E[U_{c_-}+U_{c_+}\mid\hbox{all observations}] =\mathbb E[U_{c_-}+U_{c_+}\mid\mathcal F_{\mathcal D_p}].\] Thus each selected tunnel together with its charged attachments has conditional expected normalized corrected cost at most \(-Y_p\), by Lemma 46. Consequently the completed path \(\Pi\) satisfies \[ \mathbb E\left[\frac{Q_n(\Pi)-\Delta g(\Pi)}{\beta} \,\middle|\,\hbox{all observations}\right] \le C(L+S)-G_n(L). \tag{92}\]

Apply the calibration at the fixed endpoint windows. Corrected costs use only differences of gauges. For this endpoint calculation, undo any common deterministic centering and use the original mean-matching gauge representatives; the corrected cost of \(\Pi\) is unchanged. The constructed path has endpoint labels prescribed by translated copies of the exterior anchor convention. Calibration domination gives, pathwise, \[Q_n(\Pi)-\Delta g(\Pi) \ge (P_n-g)(x_{\mathrm{end}})-(P_n-g)(x_{\mathrm{start}}).\] Although an endpoint intersection is random, it lies in a prescribed bounded road window. Put \(R_W=P_n-g_W\) on that exterior road and choose a fixed marked anchor \(k\) before the entire window of possible endpoint occurrences \(t\). Equation (57) gives \(\mathbb ER_W(k)=0\), and the defect and interpolation identities give \[R_W(t)-R_W(k)=-D_W(k,t)+C_W(k,t).\] The interval is covered by a fixed number of complete road periods. Additivity and nonnegativity bound its defect by the defects of those periods; Lemma 29 controls its corrected cost. Thus the expected supremum of the absolute right side is at most \(C\beta\). In particular, \[\bigl|\mathbb E(P_n-g)(x_{\mathrm{start}})\bigr| +\bigl|\mathbb E(P_n-g)(x_{\mathrm{end}})\bigr| \le C\beta.\] The estimate covers every possible intersection occurrence and allowed endpoint label. Consequently the expected normalized corrected cost of \(\Pi\) is at least \(-C\). Taking expectations in (92) yields \(\mathbb EG_n(L)\le C(L+S)+C\), and the fixed \(S\) is absorbed into \(C_0\). The bound holds at each finite \(L\), uniformly over the tunnel law; no law-dependent limiting passage is needed. ◻

Proof. Put \(F=S_\mu\setminus U\). If the first assertion failed, there would be \(t_j\downarrow0\) and probability measures \(\nu_j\) with barycenters within \(t_j\) of \(a\) and \(\nu_j(F)\ge e>0\). A weakly convergent subsequence exists on the compact sphere. Its limit \(\nu\) has barycenter \(a\), and the closed-set inequality gives \(\nu(F)\ge\limsup_j\nu_j(F)\ge e\).

The convex hull of \(F\) is compact and omits \(a\). Indeed, Carathéodory’s theorem would otherwise express \(a\) as a finite nontrivial convex combination of points different from \(a\), contrary to extremality. If \(\nu(F)=1\), its barycenter lies in that convex hull. If \(0<\nu(F)<1\), the conditional barycenters on \(F\) and its complement lie in the norm ball and express \(a\) as a nontrivial convex combination. Extremality makes both equal to \(a\), whereas the first lies in the convex hull of \(F\). Both cases are impossible, proving \(\omega_U(t)\to0\).

For the second assertion put \(S=\sum_i\mu(z_i)>0\) and give \(z_i/\mu(z_i)\) mass \(\mu(z_i)/S\). Its barycenter is \((\sum_i z_i)/S\), at distance at most \[\frac{d_0+d_0|a|}{1-d_0}\le C_a d_0\] from \(a\). The mass on \(F\), multiplied by \(S\le(1+d_0)N\), is the left side of (97). ◻

Proof. Let \(B_0\) be the bad set. For \(\theta>0\), put \[R=\{i:\text{some index interval }I\ni i \text{ has }|I\cap B_0|>\theta|I|\}.\] A one-dimensional maximal-interval bound gives \(|R|\le3|B_0|/\theta\): select disjoint witness intervals in decreasing order of length. Their triple enlargements cover all discarded witness intervals, and their lengths sum to at most \(|B_0|/\theta\). Every interval containing a retained index therefore has bad density at most \(\theta\).

Let \(\ell_1,\ell_2\) be the coordinate functionals of \(\mathcal C_2\). Compactness and the strict cone inclusion give \(\ell_j(x_{i+1}-x_i)\ge\kappa_0K\) at good indices, whereas at bad indices they are at least \(-CK\). Choose \(\theta<\kappa_0/(2(C+\kappa_0))\). Every interval containing a retained index then satisfies \[\ell_j\left(\sum_{i\in I}(x_{i+1}-x_i)\right) \ge\tfrac12\kappa_0K|I|.\] Apply this to the interval between two retained cut indices, then absorb the bounded errors in choosing their centers. To include the initial endpoint and a retained starting-cut representative \(x_i\), use the prefix through increment \(i\) and subtract that increment, whose size is at most \(CK\). The suffix from \(x_i\) already contains the retained index. Center rounding adds another bounded error. The coordinate matrices range in a fixed compact set, so these errors remain uniform as the cone enlargement shrinks.

For multiplicity, apply the same density argument to \(h\). After decreasing \(\theta\) if necessary, it gives \(h(x_j-x_i)\ge cK(j-i)\) on the relevant intervals, where \(c\) is independent of the cone enlargement. Only boundedly many retained centers can therefore lie in any fixed-radius ball.

For the cost assertion, bound each removed gauge difference separately: \[\begin{align*} \sum_{i\in R}(Q_i-\widetilde g_{i+1}+\widetilde g_i) &\ge n\{c_*|B_0|-(\epsilon_n^{\rm raw}+2\lambda)|R|\}\\ &\ge n\left\{c_*-\frac{3(\epsilon_n^{\rm raw}+2\lambda)}{\theta}\right\}|B_0|. \end{align*}\] Choose \(\lambda<c_*\theta/24\) and then \(n\) large. The bracket is at least \(c_*/2\), retaining a positive penalty per bad index. The set \(R\) depends only on the bad indices, so this conclusion holds for every assignment of effective gauges satisfying the stated bound. ◻

Proof. An edge-only event and fine directions. Choose the nearest endpoint and the geodesic by fixed tie conventions. The metric and cheap-path estimates give an event \(\mathsf M_n\) depending only on the edge weights, with \(\rho_n=\mathbb P_{\rm edge}(\mathsf M_n^c)\to0\), on which \[ |Q_n(\gamma)|\le q_nN,\qquad |\gamma|_{\rm edges}\le CNn,\qquad \gamma\subset[-CN,CN]^2,\qquad q_n=C\frac{(Nn)^\chi+1}{N}\to0. \tag{106}\] Here \(L>99\) makes \((Nn)^{0.99}=o(N)\); endpoint rounding contributes only \(O(1)\) to \(Q_n\). Write \(T_n(x,y)=T(nx,ny)\) for scaled metric-graph endpoints. On the same event, every such pair in a fixed enlargement of this box and at the bounded scaled distances used below satisfies \[T_n(x,y)\ge n\mu(y-x)-e_n,\qquad e_n=C_Kn^\chi=o(n).\] The graph-endpoint assertion includes the maximum incident-edge bound from Lemma 20. Thus it holds simultaneously before any cuts are chosen.

The fine choices in the stated parameter order can be made as follows. Choose the rational approximation to \(a\), a neighborhood \(U\), and \(\varepsilon_f>0\) so that every increment directed in \(U\) satisfies \[u(z)\ge0,\qquad |y(z)|\le\varepsilon_f u(z) \le\tfrac12\eta\sigma\,\mu(z).\] Indeed \(u(a)>0\), \(y(a)\to0\) as \(v\to a\), and \(u(z)\le C\mu(z)\) by fixed norm comparison. Take \(\varepsilon_f\) small enough and choose the fixed radius \(\varrho\) so that \[ \kappa=s+d\varepsilon_f\le\tfrac12,\quad 12\varrho<H_m,\quad \varrho<\sigma/100,\quad 2(1+s)\varrho<b/10,\quad 2r+4d\varrho<b'. \tag{107}\] These conditions are compatible because \(s<1/4\) and \(2r<b'\).

Use the fine exit partition of radius \(\varrho\) in the \((A,B)\) maximum norm. Each fine trace has diameter at most \(2\varrho\), including the final incomplete trace. The edge budget bounds the number of fine segments by \(CN/\varrho+1\). For their increments \(z_i\), put \(S_n=\sum_i\mu(z_i)\). Summing the metric lower bounds gives \[nS_n\le nN+C+q_nN+(CN/\varrho+1)e_n,\] while the triangle inequality and endpoint rounding give \(S_n\ge N-C/n\) and \(|\sum_i z_i-Na|\le C/n\). Thus both errors in Lemma 48, divided by \(N\), are at most \[d_n=C\left(\frac1{nN}+\frac{q_n}{n} +\frac{e_n}{n\varrho}+\frac{e_n}{nN}\right)\to0.\] Define \[\epsilon_n^{\rm fine}=(1+d_n)\omega_U(C_a d_n)\to0.\] The total norm mass outside \(U\) is at most \(\epsilon_n^{\rm fine}N\). Every full fine increment has norm length at least \(c\varrho\), so there are at most \(C\epsilon_n^{\rm fine}N/\varrho+1\) bad increments, including a possible bad incomplete one. A zero final segment is omitted. The good transverse variation is at most \(\tfrac12\eta\sigma S_n\le\eta\sigma N\) for large \(n\), and the bad variation is at most \(C\epsilon_n^{\rm fine}N\). All these bounds hold on the same edge event for every road law.

Cuts and the uniform good event. Place the actual preliminary \(K\)-exit marks in the \((A,B)\) maximum norm. At each mark test every fine interval whose occurrence-time interval meets the terminal arc, including at either endpoint. The coordinate identities \[u=d\xi_1,\qquad y=s\xi_1+\xi_2\] put every good fine displacement in \(\mathcal G_\kappa\) of (87). With \(\delta_f=2\varrho\), \(\kappa\le1/2\) and \(12\varrho<H_m\) imply its exact strict condition \[H_m>\frac{2(1+\kappa)}{1-\kappa}\delta_f.\] If every fine interval meeting the terminal arc is good, use the \(B\)-wall candidates of Lemma 45; otherwise use its annulus candidates. Both tuple families and all future datum choices were included before this test in the single objective \(W_c/\beta+V_c/a_n\).

With \(a_n=C_1n^{1-\vartheta}\), that lemma supplies \[ \mathbb P_{\mathfrak r}(E_z>t)\le C_K\min(1,t^{-m_*}),\qquad W_{\rm cut}/\beta\le E_z,\qquad V_{\rm cut}\le a_nE_z. \tag{108}\] The inequalities cover every allowed effective gauge at the chosen cut. Let \(\mathcal Z_n\) be the deterministic set of possible mark cells in the box of (106), with its fixed boundary enlargement. It has at most \(Cn^{2L+10}\) cells. Define \[\Omega_{n,\mathfrak r} =\mathsf M_n\cap\{\max_{z\in\mathcal Z_n}a_nE_z\le\lambda n\}.\] The union bound in the selected-cuts lemma gives \[\mathbb P_{\mathfrak r}(\Omega_{n,\mathfrak r}^{\,c}) \le \rho_n+C_{\lambda,K}n^{\,2L+10-m_*\vartheta} =:\pi_n\longrightarrow0\] uniformly in \(\mathfrak r\). No independence between the metric event and the cut fields is needed. A selected cut lies within \(H_m\) of its mark. Since successive preliminary displacements equal \(K\), selected displacements lie between \(K-2H_m\) and \(K+2H_m\), in particular between \(K/2\) and \(2K\). The intervening pieces and the two terminal fragments have diameter \(O(K)\).

The halo and its cost. Each terminal fragment has raw cost at least \(-e_n\), so the selected pieces have total raw cost at most \(q_nN+2e_n\). Every such piece has raw cost at least \(-e_n\). For an off-\(\mathcal C_1\) displacement in the fixed annulus, compactness gives a positive lower bound for \(\mu(z)-h(z)\). For a unit backward \(h\)-excursion, split before, during, and after the excursion; \(\mu\ge|h|\) gives raw cost at least \(2n-3e_n\). For some fixed \(c_*>0\), bad pieces therefore cost at least \(c_*n\) for large \(n\). Let \(B_0\) be their index set. The edge budget gives at most \(CN/K+C\) pieces, whence \[\frac{|B_0|}{N} \le C\left(\frac{q_n}{n}+\frac{e_n}{nK} +\frac{e_n}{nN}\right).\] Use the fixed \(\lambda<c_*\theta/24\) from the halo lemma and \(\epsilon_n^{\rm raw}=e_n/n\). The halo set \(R\) depends only on \(B_0\), and \(|R|\le3|B_0|/\theta\). On \(\Omega_{n,\mathfrak r}\) the gauge bound holds simultaneously for every later datum, so the removed cost is nonnegative for the eventual shared choices. They telescope on the full consecutive list, giving \[\sum_{i\notin R}c_i^{\rm cost} \le\sum_i c_i^{\rm cost} \le c_0^{-1}(q_nN+2e_n+2\lambda n).\]

The halo’s endpoint order puts the retained centers in (102): the second \(E\)-coordinate of \(a\) tends to zero as \(\mathcal C_2\) shrinks to \(\mathcal C\). The endpoint and center errors stay bounded because \(E\) ranges in a compact family. Each preliminary exit uses at least \(cKn\) edges, so there are \(O(N/K)\) centers. Their successive-distance budget, including the initial \(O(K)\) distance, is \(O(N)\). The halo lemma also gives the stated multiplicity bound.

Rows and regular links. Track the fine polygon by hysteresis: keep its current row until it leaves the central sub-band of half-width \(b/4\), then choose the nearest row. Since \(\sigma<b/10\), each change except possibly the first consumes at least \(b/10\) of transverse variation. The row-index variation is bounded by a constant times that variation divided by \(\sigma\), plus a constant times the number of changes. It is at most \[C_K\eta N+C_{\rm fixed}\epsilon_n^{\rm fine}N+O(1).\] Let \(\mathcal I_0\) contain exactly the pieces whose closed occurrence-time intervals meet a row change or a bad fine interval, or which are incident to a failed terminal test. Define this set on the full selected list, regardless of membership in \(R\). A row-change time lies in at most two closed coarse intervals. A fine trace has diameter at most \(2\varrho\). Its closed occurrence-time interval can meet at most two closed coarse intervals, since otherwise it contains two consecutive cuts separated by \(K/2\). Each terminal arc occurs after its preceding preliminary mark. A fine interval meeting three terminal arcs would contain two consecutive preliminary marks, separated by \(K\). Each failed test is incident to at most two pieces and is charged to a bad fine interval meeting its terminal arc. Thus \[|\mathcal I_0| \le C_K\eta N+C_{\rm fixed}\epsilon_n^{\rm fine}N+O(1).\]

On a piece outside \(\mathcal I_0\), every fine interval meeting it chronologically is good. The polygon calculation in (88), now applied to any submotion of this piece with \(\delta_f=2\varrho\), gives horizontal drawdown at most \(4d\varrho\). The path is within transverse distance \(2(1+s)\varrho\) of its fine polygon. The hysteresis and (107) therefore keep the whole piece in one full row band, with drawdown less than \(b'\). Its two successful terminal tests supply \(B\)-wall vertex occurrences. Write \(k_i\) for this constant hysteresis row. Two adjacent pieces outside \(\mathcal I_0\) have the same row: their closed time intervals share a cut, and a change there would put the incident pieces in \(\mathcal I_0\).

The first \((A,B)\) coordinate increases across this piece. Its maximum norm displacement is at least \(K-2H_m\). If the negative first coordinate realized that norm, its size would be at most \(4\varrho\) by (88); if the second coordinate realized it, its size would be at most \(4(1+\kappa)\varrho/(1-\kappa)\le12\varrho\). Both contradict \(12\varrho<H_m<K/20\). Hence the first-coordinate increase is at least \(K-2H_m\). Since \(\rho=2r\) is the wall tracking width in these coordinates, the terminal wall index exceeds the initial one by at least \(K-2H_m-2\rho>0\).

Split the piece at successive first meetings of the next \(B\)-wall. At each intermediate meeting, use one occurrence of that wall for both adjoining subpaths. Planarity forces a meeting before passage beyond that wall’s far padded side, and the drawdown bound for every submotion supplies the backward allowance. End the final subpath at the original terminal cut, even if it met that wall earlier. Its overshoot is at most \(2r+4d\varrho<b'\), so the entire trailing portion is retained. These are admissible links in (94); the piece diameter bounds their number by a fixed \(q_K\). Write \(q_i\le q_K\) for this number.

Figure 3 shows the terminal-wall candidates and the first-meeting decomposition of a regular piece, including its final subpath after an earlier visit to the terminal wall.

Distinct columns. At every original cut put \[v_h=\left\lfloor \xi_1(x_h)+\tfrac12\right\rfloor, \qquad 0\le h\le m_N.\] At a cut on \(W_j\), tracking gives \(\lvert \xi_1(x_h)-j\rvert\le\rho+O(1/n)<1/2\) for large \(n\), so \(v_h=j\). Form one integer walk by expanding each piece outside \(\mathcal I_0\cup R\) into its \(q_i\) positive unit wall steps from \(v_i\) to \(v_{i+1}\), and replacing each piece in \(\mathcal I_0\cup R\) by the jump between these endpoints. Include the two terminal jumps \(0\to v_0\) and \(v_{m_N}\to j_n\). The walk begins at \(0\), ends at \(j_n\), and is fixed before any whole piece is rejected by the following scan. Each jump has magnitude \(O(K)\), including the terminal jumps. If \(q_{\rm all}\) is the number of unit steps and \(P,D\) are the sums of the positive and negative jump magnitudes, then \[q_{\rm all}+P-D=j_n,\qquad P+D\le C_K\bigl(|\mathcal I_0|+|R|+1\bigr).\] Scan this fixed walk once, updating its running maximum at every visited vertex. Call a unit step \(j\to j+1\) a candidate if its endpoint is a new strict maximum and is at most \(j_n\), and let \(q_{\rm rec}\) be the number of candidates. For each integer level \(\ell\in\{1,\ldots,j_n\}\), the first step whose endpoint is at least \(\ell\) is either a candidate unit step ending at \(\ell\) or a positive jump. A positive jump is charged at most its magnitude. Hence \[j_n-q_{\rm rec}\le P,\qquad q_{\rm all}-q_{\rm rec} =D-P+(j_n-q_{\rm rec})\le D.\] This counts every rejected unit step, including record steps beyond \(j_n\). Let \(\mathcal C_{\rm rec}\) be the pieces outside \(\mathcal I_0\cup R\) containing at least one rejected step, and set \[\mathcal I=(\mathcal I_0\cup\mathcal C_{\rm rec})\setminus R, \qquad \mathcal G=\{0,\ldots,m_N-1\}\setminus(R\cup\mathcal I).\] Distinct pieces in \(\mathcal C_{\rm rec}\) contain distinct rejected steps, so \(\lvert\mathcal C_{\rm rec}\rvert\le D\). Keep all links of the pieces in \(\mathcal G\), without rescanning the walk. They are candidate steps, so their columns are distinct, increasing, and in \(\mathcal J_n\). Discarding a whole piece loses at most \(q_K\) candidates, and therefore \[|\mathcal I|\le|\mathcal I_0|+D,\qquad |\mathcal J_n\setminus\{j:(j,k)\in\mathcal L\}| \le P+q_KD.\] The bounds on \(P,D\) prove the stated irregular and omission bounds. Since \(u(a)/d\) is bounded above and below, \(j_n\) is comparable to \(N\); for sufficiently small \(\eta\), the omission bound also gives \(\lvert\mathcal L\rvert\ge cN\) for large \(n\).

The selected rows form a chronological subsequence of the hysteresis rows, so deleting terms cannot increase variation. Hold the old row across each omitted gap, as in Lemma 41. The box in (106) bounds the first selected row by \(CN/\sigma\le j_n^2\) for large \(n\). This proves (104).

Shared data and the tunnel charge. After these masks are fixed, assign one datum to every original cut \(x_h\), \(0\le h\le m_N\), retaining its selected road label and occurrence. If at least one incident original piece belongs to \(\mathcal G\), use that piece’s row center on the cut’s \(B\)-wall. When both incident pieces belong to \(\mathcal G\), their rows agree by the argument for closed time intervals above, and they use the same selected wall occurrence, so they request the same center. If neither incident piece belongs to \(\mathcal G\), use the prescribed reference center for the cut cell and road label. At \(h=0,m_N\), only the one existing incident piece is considered. Use this datum for both incident pieces even if one belongs to \(R\) or \(\mathcal I\); all incidence here is incidence in the original list.

The masks \(R,\mathcal I_0,\mathcal C_{\rm rec}\) did not use the eventual data, and the simultaneous \(V_{\rm cut}\) bound covers all the prescribed choices. Thus these are the shared data used in the telescope over the full list and the halo estimate above, which holds for every allowed datum choice. Every piece in \(\mathcal G\) receives its own row center at both endpoints. Any retained nonregular piece accepting a neighboring center is already in \(\mathcal I\), while any removed incident piece is in \(R\); the datum choice requires no further irregular or omission charge. For \(i\in\mathcal G\), let \(\gamma_{i,\nu}\) be its consecutive physical subpaths from the decomposition at first meetings. Intermediate center arms cancel, including across the retained terminal subpath, and give \[\beta c_i^{\rm cost} =\sum_{\nu=0}^{q_i-1} L_{v_i+\nu,k_i}(\gamma_{i,\nu}) \ge\sum_{\nu=0}^{q_i-1}X_{v_i+\nu,k_i}.\] This proves (103).

For each retained piece, choose the access type with its cut cells, road labels, the two prescribed center conventions just used, and its rounded padded domain. This type belongs to the fixed finite family, and \(H(\gamma_i)=\beta c_i^{\rm cost}\) in (83). For the tunnel comparison, choose an exterior wall occurrence \(a_i\) before both \(\bar x_i,x_i\), and \(b_i\) after both \(x_{i+1},\bar x_{i+1}\), as in Lemma 44. Additivity gives \[C(a_i,\bar x_i)+\beta c_i^{\rm cost}+C(\bar x_{i+1},b_i) =C(a_i,x_i)+Q_n(\gamma_i)-g(x_{i+1})+g(x_i) +C(x_{i+1},b_i).\] The right side is the corrected cost of the physical forward concatenation in Lemma 44. Those attachments enter the access charge; a negative signed arm is never treated as a negative physical traversal. Every retained piece lies in its padded \(h\)-slab because it has no unit backward \(h\)-excursion. Lemma 46 therefore gives (105). At each coarse center, sum all cut error fields in its fixed \(O(K)\) neighborhood and over the finite cut-type list. This fixed local field dominates the two selected endpoint errors for every allowed piece, keeps a fixed range, and preserves the tail exponent. The finite type and phase-template lists are those fixed in Section 6.6.

Finally, one common deterministic error sequence is \[\epsilon_n=C_{\rm fixed}\left(q_n+\frac{e_n}{n}+\frac nN +\epsilon_n^{\rm fine}+\frac1N\right)\to0.\] The fixed constant absorbs \(1/\varrho,1/\sigma,1/\theta,1/c_0\) and the bounded endpoint adjustments. The preceding cost, halo, irregular, omission, and row estimates then have exactly the stated bounds. Together with the uniform \(\pi_n\) above, this proves the proposition. ◻

Proof. Fix an error \(\varepsilon>0\), to be chosen relative to \(\zeta\). Choose \(F,T\) in (109), reserving the corresponding upper bound for the final \(\delta\). By (111), choose \(J\) after \(T,M\) so that \((q_KM+2T)C_KJ^{-1/2}<\varepsilon\), and then choose \(\eta\) so that its contribution has the same bound.

Apply Lemma 41 to \(f_{J,M}(X_{j,k}/\beta)\), using the original column independence from Lemma 33. Its fixed bound is \(\max(J,M)\). The interval length \(j_n\) is comparable to \(N\); hence (104) meets the lemma’s row and omission tolerances after decreasing \(\eta\) and taking \(n\) large. Uniformly over the road law, with probability tending to one, \[\left|\sum_{(j,k)\in\mathcal L}f_{J,M}(X_{j,k}/\beta) -|\mathcal L|\mathbb E f_{J,M}(X/\beta)\right| \le\varepsilon N\] on the extraction event. The supremum in the row lemma is taken before the rows and omissions are selected.

If (112) failed uniformly, choose an offending sequence of scales and road laws. On the geometric and row events the capped sum is at least \(c\zeta N-\varepsilon N\), while (101) bounds the left side of (110) by \(\epsilon_nN\). Since \(\mathcal E_J\) is empty off the good event, (111) and (109) bound the expected nonnegative losses in (110) by \(C\varepsilon N\) for all large \(n\). By Markov’s inequality, they are at most \(4C\varepsilon N\) with probability at least \(3/4\). This event intersects the geometric and row events. Choosing \(\varepsilon<c\zeta/(10C+10)\) contradicts (110). Every threshold and geometric tolerance was fixed before \(n\), proving the asserted uniformity. ◻

Proof. Fix an error \(\varepsilon>0\). Choose \(F,T\) as in (109), uniformly over the finite type family, and reserve the corresponding upper bound for the final \(\delta\). Choose \(M_0\ge M_{\rm prescribed}\) so large that \(2TC_s/M_0<\varepsilon\). Let \(A\) bound the sum of the first moments of \((X^{(a)}/\beta)^-\) and the \(U_b\). Choose \(H\) so large that \(2A/H<\varepsilon\). Lemma 42 ensures that for each law some level in the fixed menu satisfies \[ M\sum_a\mathbb P(X^{(a)}<-M\beta) +M\sum_b\mathbb P(U_b>M)\le\varepsilon. \tag{116}\] We fix all concentration and geometric tolerances for the whole menu before selecting this law-dependent level.

For equal caps, the square-root probability in (111) would be multiplied by the cap. Instead use the original row-link fields and their column independence. For every \(M\in\mathcal M\) and every link template, apply Lemma 41 separately to \(\mathbf1_{\{X_{j,k}^{(a)}<-M\beta\}}\) and to the capped costs. Take a finite union of these conclusions, using \(M_{\max}=2^{H-1}M_0\) as a common bound. The resulting event has probability tending to one uniformly over the law, and controls all candidate levels before one is selected.

On this event and the corresponding extraction events, the selected negative-link indicators have frequency at most their marginal probability plus a fixed error \(\nu\). Columns are distinct, so each exceptional regular piece is counted by at least one such indicator. For any candidate \(M\), the regular exceptions in (110) with \(J=M\) therefore cost at most \[C_K(M+T)N\left[\sum_a\mathbb P(X^{(a)}<-M\beta)+\nu\right].\] The irregular contribution is at most \((q_KM+2T)(C_K\eta+\epsilon_n)N\). After fixing \(M_{\max}\), choose \(\nu\), the row and omission tolerances, and \(\eta\) so that their contributions are at most \(\varepsilon N\). The term containing \(\epsilon_n\) then has the same bound for large \(n\). Select a level satisfying (116). Its \(M\)-weighted term is \(O(\varepsilon N)\); its \(T\)-weighted term is small by the same bound or by \(\mathbb P(X<-M\beta)\le C_s/M_0\).

The capped row sums at this level are compared with their means by the same simultaneous concentration event. The extraction gives \(|\mathcal L|\ge cN\) and retained cost at most \(\epsilon_nN\) for each template. Markov applied to the finite sum of their \(H_N\)’s supplies a loss event of fixed positive probability, which intersects all the events whose probabilities tend to one. The contradiction in the asymmetric proof, with \(\varepsilon\) sufficiently small relative to \(\zeta\), therefore proves (114) for every template. Equation (116) gives (115). The same cap is used for both conclusions; no expectation bound on a discarded heavy negative tail is required. ◻

Proof. The local rule. Consecutive flagged indices belong to the same cluster when their difference is at most \(G_*\). A cluster with extremes \(a\leq b\) is accepted exactly when \(b-a\leq L_*\) and \[U_{a-B_*}^-=U_{b+B_*}^+=1.\] For such a cluster replace the primary slots shown in Figure 4: \[ I(a,b)=[a-B_*,b+B_*]\cap\mathbb Z. \tag{129}\]

Use the incoming transition, then the spare baseline, then the outgoing transition. The spare portion runs from parameter \(a-B_*+T_*\) to parameter \(b+B_*+1-T_*\). This interval has nonnegative length because \(B_*>T_*\). The endpoints of the whole replacement are precisely \(c_{a-B_*}\) and \(c_{b+B_*+1}\). Its normalized corrected cost \(C(a,b)\) is in their primary gauge convention and satisfies \[ |C(a,b)|\leq2K_\delta+\sum_{i\in I(a,b)}V_i. \tag{130}\] This follows by exact telescoping through the two transitions and the spare gauge. Different accepted intervals are disjoint because distinct clusters have gap greater than \(G_*>2B_*\). All long or infinite clusters are left unchanged.

The latter instruction has an exact finite implementation. A proposed leftmost flag \(a\) and rightmost flag \(b\in[a,a+L_*]\) form a complete short cluster if and only if they are flagged, all consecutive flag gaps in \([a,b]\) are at most \(G_*\), and there is no flag in \([a-G_*,a-1]\) or \([b+1,b+G_*]\). These tests read only \([a-G_*,a+L_*+G_*]\). They can never accept a portion of a longer or infinite cluster. Let \(O_i\) indicate replacement of slot \(i\). A cluster covering \(i\) has \[a\in[i-L_*-B_*,i+B_*],\] so \(O_i\) is determined by flags within distance \(13B_*\) of \(i\) and transition tests within distance \(10B_*\) of \(i\). It follows in particular that \[ O_i\leq\sum_{a=i-L_*-B_*}^{i+B_*}F_a, \qquad \mathbb EO_i\leq H_*p. \tag{131}\]

Uncovered positive costs. If a flagged slot is left uncovered because its cluster is long or infinite, it contains a flag at distance strictly greater than \(R\). Following its chain from \(i\) until the first such flag gives an index \(j\) with \[R<|j-i|\leq R+G_*.\] There are \(2G_*\) possible witnesses. If the cluster is short but not accepted, one of the possible incoming tests indexed in \([i-L_*-B_*,i-B_*]\), or outgoing tests indexed in \([i+B_*,i+L_*+B_*]\), fails. Each of these at most \(2(L_*+1)\) tests is independent of \(Z_i\), because its index is more than \(R\) away. Applying independence to these deterministic possible witnesses, before any random choice of an extreme, gives \[ \mathbb E[Z_i^+F_i(1-O_i)] \leq C_0\{2G_*p+2(L_*+1)\delta\}. \tag{132}\] For example each remote-flag term is \(\mathbb E[Z_i^+F_iF_j]=\mathbb E[Z_i^+F_i]p\leq C_0p\); the failed-test terms are analogous. Thus the expectation of an uncovered large cost is bounded directly, even if rare values carry a substantial part of the first moment.

Retained and discarded primary costs. The retained costs satisfy \[ (1-O_i)Z_i\leq W_i+MO_i+Z_i^+F_i(1-O_i). \tag{133}\] Indeed on a covered slot the right side is at least \(-M+M=0\); on an uncovered slot only the portion of \(Z_i\) above \(M\) can increase its clipped value. In particular discarding negative primary costs loses at most \(M\) times the covered density, whether or not those costs are correlated with nearby flags.

Replacement costs. By (131) and independence of the entire spare and primary fields, \[ \mathbb E[V_iO_i]\leq H_*C_Vp. \tag{134}\] We have bounded the success indicator by the event of a nearby primary flag; success itself need not be independent of \(V_i\).

Accepted clusters have density at most \(p\), so their two successful transitions contribute at most \(2K_\delta p\) to the mean upper bound. Charge the remaining bound in (130) to the leftmost flag of its cluster. By stationarity, its mean per slot is bounded by \(\mathbb E[V_0O_0]\); unused spare slots in that display are simply overcharged. Summing these bounds with (132)–(134) proves (128). Each charge and each reassignment involves a uniformly bounded number of slots. Hence all charges are integrable, and the expectation calculation requires only first moments. ◻

Proof. The structural constants \(C_{\rm tr},R_{\rm out},C_1\) are uniform in sufficiently small \(s\) and the nearby rational directions. First choose an integer \[ D\geq\max\{1000C_{\rm tr},R_{\rm out}/10,1\}. \tag{135}\] Next fix rational \(0<s<1/10\) and \(\epsilon>0\) so small that \(DC_1s<1/4\) and \(D\epsilon<1/4\). The geometry and the constants \(R,B_*,G_*,L_*,H_*,C_0,C_V\) have already been fixed uniformly. If \(C_0=0\), the primary costs vanish almost surely and no replacements are necessary. Otherwise choose \[\delta\leq\min\left\{\frac12, \frac{\epsilon}{6(L_*+1)C_0}\right\},\] then the corresponding transition cap \(K_\delta\). Set \[A_*=2G_*C_0+H_*C_V+2K_\delta, \qquad M_0\geq\max\{1,3C_0A_*/\epsilon\}, \qquad \eta\leq\frac{\epsilon}{3(H_*+1)}.\] Choose the finite matched-cap range from (L) with this \(M_0,\eta\), and then fix the geometric comparison tolerances and the rational directions so that it applies uniformly over that range. At every sufficiently large admissible \(n\), choose its deterministic good cap. Equation (122) gives \(Mp\leq\eta\), while \(p\leq C_0/M_0\) by Markov’s inequality. In (128) the failed-test error, the terms \(A_*p\), and the terms \((H_*+1)\eta\) are each at most \(\epsilon/3\). We obtain an actual stationary local road with \[ \mathbb E Q_n(\hbox{one old output slot}) \leq(C_1s+\epsilon)\beta. \tag{136}\] Regard \(D\) old slots as one new period and use space units \(Dn\). The tracking error is then at most \(s/1000\), the input radius at most \(10\), and the rule commutes with translation by \(DA\) in old units, that is by \(A\) in new units. Reindexing the private product field by this rescaling preserves its shift-invariant law: a new lattice shift corresponds to the old lattice shift multiplied by \(D\). Thus it is in the original road class at scale \(Dn\). The same construction in the other direction gives a pair with common mean bound \[ D(C_1s+\epsilon)\beta. \tag{137}\] All the rational meshes have fixed denominators; multiplication of an admissible \(n\) by the integer \(D\) preserves admissibility.

Let \(b(n)\) be the infimum of the common mean bound over that road class. Invoke the uniform input estimates with the fixed enlarged prefactor \(2C_s\); this changes only the threshold for \(n\). That threshold is therefore uniform over members with \(\beta\leq2C_s n^{1-c}\). Since \(b(n)\leq C_s n^{1-c}\), for each sufficiently small \(t>0\) one can choose a pair with \(\beta\leq b(n)+t\leq2C_s n^{1-c}\). Apply (137) and then let \(t\downarrow0\); existence of a minimizing road is unnecessary. This proves \[ b(Dn)\leq D(C_1s+\epsilon)b(n). \tag{138}\] All directions, meshes, and tolerances are fixed in the stated order, and the choices give \(\rho=D(C_1s+\epsilon)<1/2\). This proves the assertion for all admissible \(n\) above the common threshold. ◻

Proof. Damron–Hanson’s product-measure hypothesis A1\('\) holds: the common law is continuous, and the minimum \(Y\) of the four weights incident to the origin is exponential of rate \(4\lambda\), whence \(\mathbb EY^2=1/(8\lambda^2)<\infty\). Their geometric assumptions (2.1)–(2.2) require differentiability at the chosen boundary point and at both endpoints of its supporting face. The preceding supporting-line calculation identifies that face with \(\{v_u\}\). Thus their supporting sector is exactly the direction \(u\). Theorems 1 and 2 of (Damron and Hanson 2017) give the convergence, coalescence, bigeodesic exclusion, and Busemann statements on one probability-one event for this fixed \(u\). Their normalized supporting vector is \(\rho_u=\nabla\mu(u)\) by that calculation.

For completeness, uniqueness follows from the convergence assertion. If \((x=x_0,x_1,\ldots)\) is any infinite geodesic of direction \(u\), then its segment ending at \(x_n\) is \(\Gamma(x,x_n)\) by uniqueness of finite geodesics. These segments converge both to that infinite geodesic and to \(\Gamma_x^u\), so the paths agree. ◻

Proof. Set \(p_n=a_n-z_n\) and \(q_n=b_n-z_n\). Translation invariance gives \(\mathbb P(z_n\in\Gamma(a_n,b_n))= \mathbb P(0\in\Gamma(p_n,q_n))\). If the asserted probabilities had positive limsup, the event that \(0\in\Gamma(p_n,q_n)\) for infinitely many \(n\) would have positive probability. Intersect this event with \(\Omega_u\) from Corollary 55. Restrict to the infinite set of indices for which \(0\in\Gamma(p_n,q_n)\). On the intersection, the arm from \(0\) to \(q_n\) converges locally to \(\Gamma_0^u\). Both arms have lengths tending to infinity, since their endpoints tend to infinity. Local finiteness of the lattice permits a diagonal subsequence along which the other arm also converges to an infinite path. Every finite segment of the resulting two-sided path is a segment of one of the finite geodesics \(\Gamma(p_n,q_n)\), and hence is geodesic. The two arms have no vertex in common except \(0\), because each finite geodesic is simple. This constructs a bigeodesic with an end of direction \(u\), contradicting Corollary 55. The first assertion uses \(a_n=0\), \(b_n=nv\), and \(z_n=\lfloor n/2\rfloor v\). ◻

Proof. Theorem 2 gives a \(C^1\) boundary. We verify that such a compact planar convex body has infinitely many extreme points. At a boundary point choose a supporting line. Its intersection with the body is a point or a compact segment, and its endpoints are extreme points of the body: any convex decomposition of an endpoint must stay in the supporting line, where extremality is immediate. Thus every boundary point is a convex combination of extreme points. Every interior point lies between two boundary points, so the whole body is the convex hull of its extreme points. If there were only finitely many, the body would be a polygon with nonempty interior. At a vertex of that polygon the two adjacent sides give distinct supporting lines, contradicting differentiability. Hence the number of extreme points exceeds forty.

The Gamma density is absolutely continuous, has no atom at zero, and has a finite exponential moment by Lemma 3. All the hypotheses of (Dembin et al. 2024, Theorem 1.2) are therefore satisfied. Apply that theorem at rate one to obtain \(C_\kappa\). The coupling \(t_e^{(\kappa,\lambda)}= t_e^{(\kappa,1)}/\lambda\) leaves every geodesic unchanged and proves the assertion for all positive rates with the same constant. ◻

Proof. The Gamma law is atomless for every \(\kappa>0\), including \(\kappa<1\). For four independent samples, \[\mathbb E\bigl[\min(\tau_1,\ldots,\tau_4)^2\bigr] \le \mathbb E\tau_1^2 =\frac{\kappa(\kappa+1)}{\lambda^2}<\infty.\] Thus the continuity and minimum-second-moment hypotheses of (Ahlberg et al. 2026, Theorem 1) hold.

The infinite seed set causes no ambiguity in the arrival-time comparison. If \(I_1\) is nonempty, choose one seed as a finite upper bound for \(T(I_1,z)\). Only finitely many seeds lie in the corresponding passage ball about \(z\), so the infimum is attained. Simple paths from distinct seeds to \(z\) have different edge sets. Conditioning on all edge weights except one in their symmetric difference and using atomlessness rules out equal costs; countability gives this simultaneously for all such paths and sites. Thus the shared-metric competition is described by the displayed strict comparison defining \(\mathcal E_2\).

Theorem 2 gives a \(C^1\) boundary. For the fixed \(\theta\), put \(h(\theta)=\max_{x\in\mathcal B}x\cdot\theta>0\). The supporting line \[L_\theta=\{x:x\cdot\theta=h(\theta)\}\] is perpendicular to the positive \(\theta\)-ray and meets that ray at \(h(\theta)\theta\). At any contact point with \(\mathcal B\), the \(C^1\) boundary makes \(L_\theta\) the unique supporting line, hence a tangent in the sense of (Ahlberg et al. 2026); the contact point need not lie on the ray. For a seed set \(I\subset\mathbb Z^2\setminus\{0\}\), write \(\mathcal E_2(I)=\{z\in\mathbb Z^2:T(0,z)<T(I,z)\}\), with the same empty-set convention for \(T(I,z)\). If \(I\subset J\), then \(T(J,z)\le T(I,z)\) and hence \(\mathcal E_2(J)\subset\mathcal E_2(I)\). If \(\alpha<\pi/2\), choose \(\alpha<\alpha'<\pi/2\). The source’s cone of half-angle \(\alpha'\) contains the closed \(\alpha\)-cone, regardless of its boundary convention, so its Theorem 1 gives positive survival for the closed \(\alpha\)-cone as well. If \(\alpha\ge\pi/2\), the closed \(\alpha\)-cone contains the closed critical half-plane. Theorem 5 gives almost-sure finite type-2 growth for that half-plane, and monotonicity gives the same conclusion for the larger cone. This proves the stated closed-cone convention throughout \([0,\pi]\), without strict convexity, for every prescribed orientation.

When \(\kappa=1\), the shared exponential edge field gives the equal-rate two-type Richardson model. The coupling \(\tau_e^{(\lambda)}=\tau_e^{(1)}/\lambda\) multiplies both arrival times by the same positive constant and leaves every comparison defining \(\mathcal E_2\) unchanged. This proves the stated specialization. ◻