============================================================
NO BIGEODESICS IN PLANAR FIRST-PASSAGE PERCOLATION
a self-contained writeup of the proof under the minimum-of-four
second-moment condition
============================================================
SECTION 1. WHAT WE ARE DOING
First-passage percolation (FPP) assigns a random cost to every edge of
the square lattice Z^2 (viewed as a graph with vertices Z^2 and
nearest-neighbour edges). Every edge e gets an independent random
weight t_e with the same distribution G on [0, infinity). The passage
time T(x,y) between two vertices x,y is the smallest total cost of a
finite walk from x to y, where each edge is charged its weight every
time the walk uses it.
A FINITE GEODESIC between x and y is a walk that achieves the minimum
T(x,y). A RAY starting at x is a simple infinite path p=(p_0=x, p_1,
p_2, ...) such that every finite segment p[i..j] is a finite geodesic
in the sense above. A BIGEODESIC is a doubly infinite simple path
v=(..., v_{-1}, v_0, v_1, ...) such that every finite segment is a
finite geodesic.
CONJECTURE (planar no-bigeodesics, attributed to Furstenberg via
Kesten). For iid continuous edge weights on Z^2 there are almost
surely no bigeodesics.
THEOREM 1 (main result). Assume G has no atoms and that, for four
independent samples X_1,...,X_4 of G,
E[ (min{X_1,X_2,X_3,X_4})^2 ] < infinity.
Then with probability one there is no bigeodesic. The conclusion
holds in a single probability-one event that simultaneously excludes
every bigeodesic; no regularity of the limit shape (strict convexity,
curvature, differentiability, finite mean weight) is required.
The law G may be singular continuous or compactly supported.
WHY THIS IS HARD. There is a subtle QUANTIFIER trap. The classical
theory gives: for every FIXED linear functional rho, almost surely
there is exactly one ray starting at every vertex with that
"direction". But a bigeodesic, if one existed, would choose its own
random direction rho. The null set for "fixed rho" may depend on rho,
so we cannot directly intersect countably many events to also cover
"random rho". This paper closes that gap.
THE STRATEGY, IN ONE PARAGRAPH. Every ray has a label, a linear
functional rho that describes the average direction of the ray at
infinity. The two ends of a bigeodesic have opposite labels. A budget
argument shows: if you have a bigeodesic whose upper label lies in a
narrow band of width W (measured by rho(e1)), and you inflate the
environment so the bigeodesic gets a bigger cost by at least b, then
an arbitrarily far away reference pair of rays at the edges of that
band absorbs the cost through Busemann telescoping. This forces
(b / l) * q <= W, where l is a grid spacing and q is the probability
that a grid site produces such a marked bigeodesic. We construct
marks with q bounded below by a constant p/8 while l is fixed and
b/M -> infinity, so eventually (b/l)q > W, contradiction.
Two sub-problems have to be solved:
(A) obtain a large gain b without distorting the environment too
much (change of law must stay bounded), and
(B) force two marked bigeodesics to have DIFFERENT labels even
though we cannot a priori measure them.
Both are handled by raising finitely many edges with a slowly decaying
probability delta_h ~ 1 / (h log h) at height h. The sum of
delta_h diverges (so a long path can gain arbitrarily much), while
the sum of h * delta_h^2 converges (so the change-of-law loss stays
small). For (B), a strictly raised edge among the first R_0 steps of
one marked path cannot lie in the other's raised region if the sites
are far apart. Combining the two regions in one "union metric"
preserves both marked paths, and any shared label would then force a
strictly cheaper detour in one individual metric - impossible. So
distinct marked sites have distinct labels.
Everything else (charts, cones, Busemann pair uniqueness, boundary
comparison) supports those two facts. We now write it out
systematically.
SECTION 2. SETTING AND FOUNDATIONAL FACTS
2.1 NOTATION.
E = the set of unoriented nearest-neighbour edges of Z^2.
Omega = [0,infinity)^E with the product sigma-algebra (and its
completion). P = G^E.
For a finite walk gamma, cost(gamma) = sum over each traversal of
an edge's weight. T(x,y) = inf over finite walks from x to y of
cost(gamma).
A finite geodesic is a walk achieving T(x,y).
A ray is p=(p_0,p_1,...) with p_0 fixed, simple, every finite segment
p[i..j] a finite geodesic.
A bigeodesic is v=(...,v_{-1},v_0,v_1,...) similarly indexed by Z.
Two rays coalesce if, after deleting finitely many initial vertices,
they agree.
We draw lattice edges as straight segments; two lattice paths
"intersect" when they share a lattice vertex.
2.2 LEMMA (finite uniqueness). Almost surely every pair of vertices
has a unique finite geodesic.
Proof. Edge weights are positive a.s. Pick c>0 with
a = 4 E[exp(-c t_e)] < 1 (dominated convergence). For a fixed x and
K<infinity, the probability that some j-edge simple path from x has
cost <= K is at most exp(cK) a^j; summing over j is finite. So only
finitely many simple paths from x have cost <= K a.s. Take the
countable intersection over rational K>0 and vertices x. Every walk
erases loops to a simple path without increasing cost, so the infimum
is attained among finitely many simple paths.
Suppose two different simple paths p,q have the same endpoints and
the same cost. Conditional on all other edge weights, equality
prescribes the weight of one edge in their symmetric difference (the
first edge they disagree on, then follow p from its end): a single
value of the nonatomic weight. Probability zero. Countably many
pairs p,q. Done.
2.3 LEMMA (Busemann functions exist and behave). For every ray p and
every vertex x, the limit
B_p(0,x) := lim_{j -> inf} [ T(0,p_j) - T(x,p_j) ]
exists as a finite number, and the map (x,y) -> B_p(x,y) :=
B_p(0,y) - B_p(0,x) has:
(a) additivity and antisymmetry: B_p(x,y)+B_p(y,z)=B_p(x,z),
B_p(x,y)=-B_p(y,x);
(b) metric bound |B_p(x,y)| <= T(x,y);
(c) calibration: B_p(p_i,p_j)=T(p_i,p_j) for i<=j;
(d) invariance under deleting a finite prefix of p;
(e) equal Busemann functions for coalescing rays.
Proof. Fix a basepoint p_0. The sequence
a_j(x) = T(x,p_j) - T(p_0,p_j)
is decreasing in j: by the triangle inequality and calibration of
p segments. It is bounded below by -T(x,p_0). So a_inf(x) exists.
Set B_p(x,y) = a_inf(y) - a_inf(x). Additivity and antisymmetry are
automatic. Metric bound: |a_j(x)-a_j(y)| <= T(x,y) by triangle
inequality. Calibration: for i<=j, T(p_i,p_j)=B_p(p_i,p_j) because
the finite segment is geodesic. Tail invariance: a_j(x) only depends
on p from index j onwards. Coalescence: if p,q eventually agree,
their limits agree.
2.4 STRUCTURAL INPUT (Ahlberg-Hoffman + shape theorem). There exist a
deterministic norm m on R^2 and a deterministic closed set
C <= S := boundary of the dual unit ball of m, such that:
(i) Almost surely, T(0,x) = m(x) + o(|x|) as |x| -> infinity.
(ii) Almost surely, simultaneously over ALL rays p from ALL lattice
vertices, there is a UNIQUE rho_p in C, called the LABEL of p,
with B_p(0,x) = rho_p(x) + o(|x|) as |x| -> infinity; moreover
the limit direction of p lies in A(rho_p), the set of contact
directions of rho_p (directions d in the unit circle with
m(d)=rho_p(d)).
(iii) For each FIXED rho in C, almost surely there is exactly one
ray g_rho(x) from each x with label rho; the family {g_rho(x)}
coalesces, and it is BACKWARDS FINITE: for every fixed vertex z,
only finitely many x have z in g_rho(x).
Moreover m and C inherit the reflection and rotation symmetries of
Z^2; in particular C = -C.
Reference: Ahlberg-Hoffman (arXiv:1609.02447v2), Assumption A1,
Theorems 2.5-2.6, 10.8-10.11, Proposition 4.5. Assumption A1 only
requires the minimum-of-four second moment of our Theorem 1 (this is
where that inequality is used). The shape theorem is Cox-Durrett.
The separate boundary-expectation step of Ahlberg-Hoffman Lemma 4.6
is replaced by our Appendix so that the structural input keeps its
moment scope; we do not need to actually strengthen assumptions.
2.5 COROLLARY (fixed-label exclusion). For each fixed rho in C, almost
surely no bigeodesic has an end with label rho. Simultaneously for
each member of any deterministic countable D subset C.
Proof. Suppose a bigeodesic has forward end of label rho. Its forward
rays from each backward vertex b_i all have label rho by tail
invariance. Backwards finiteness of the family {g_rho(x)} says only
finitely many x have any fixed vertex z in g_rho(x). But the middle
vertex z lies on g_rho(b_i) for every i, contradicting finiteness
since there are infinitely many distinct b_i. For countable D,
intersect the countably many probability-one events.
2.6 LEMMA (uniform metric approximation). Almost surely
T(x,y) = m(y-x) + o(|x|+|y|)
uniformly over the pair (x,y).
Proof. Ahlberg-Hoffman Proposition 3.4: for every eps>0, a.s. there is
N<infinity with |T(z,z+v)-m(v)| <= eps max{|z|,|v|} when |z|>=N and
v arbitrary. Given x,y, take z to be the endpoint with larger norm and
v the displacement. Then |z|>=(|x|+|y|)/2 and
max{|z|,|v|} <= |x|+|y|. Symmetry finishes.
2.7 LEMMA (finite-change). Suppose two environments differ on a finite
set F of edges, with K = sum_{e in F} |t'_e - t_e|. Then
|T'(x,y) - T(x,y)| <= K for all x,y.
If a path p is a ray in both environments with asymptotically linear
Busemann functions in both, then p has the SAME label in both. If
t'_e >= t_e for all e and a geodesic path uses only unchanged edges,
it remains geodesic in the new (larger) metric.
Proof. Costs of simple paths change by at most K (each simple path
uses each changed edge at most once). Taking infima gives the
distance bound. For the label: |B'_p(x,y)-B_p(x,y)| <= 2K from the
definition, and asymptotic linearity of both at scale x=nv forces
equal linear parts. The geodesic assertion is immediate from
monotonicity.
2.8 A COMMON PROBABILITY-ONE EVENT. When we apply a simultaneous
pathwise assertion of 2.4 in a finitely modified environment whose
law is absolutely continuous with respect to P, the assertion still
holds almost surely. Since there are countably many such
environments and deterministic parameters in each construction, we
may intersect their probability-one events into a single event of
probability one. All subsequent arguments are pathwise on that
event (or on countable-intersections of such events).
2.9 MEASURABILITY CONVENTIONS. On the standard Borel space Omega x
(path space), the conditions "p is a ray", "p is a bigeodesic", "p
and q coalesce", "B_p is asymptotically linear to rho" are Borel:
every clause is tested on countably many finite paths and rational
tolerances. Existential projections (e.g. "some ray with this label
exists from this vertex") are analytic, hence universally measurable.
A witnessing path on such an event is selected completion-measurably.
When we later impose an additional condition on ALL rays of a chart
from a specified vertex, this is a coanalytic (universally
measurable) set with a one-witness complement; we intersect this
filter OUTSIDE any existential path projection. No universal
quantifier is put inside a projected relation. All the arguments
below use this discipline.
SECTION 3. CHARTS, LOCAL ORDER, CONES
3.1 LEMMA (opposite functionals). Let an oriented bigeodesic pass
through z, and let p^+,p^- be its two one-sided rays from z. Then for
every w in Z^2,
B_{p^+}(z,w) + B_{p^-}(z,w) <= 0.
Consequently rho_{p^-} = -rho_{p^+}. Moving the basepoint along the
bigeodesic does not change either label or either Busemann function.
Proof. For vertices p_i^+ and p_j^- on the two arms:
T(z,p_i^+) + T(z,p_j^-) = T(p_i^+,p_j^-) <= T(w,p_i^+) + T(w,p_j^-).
Subtract the right side and let i,j -> infinity: the bigeodesic
inequality follows. Asymptotic linearity of B_{p^+}+B_{p^-} is that
of (rho_{p^+}+rho_{p^-})(w-z) plus a lower-order term; feeding
w = z +/- n e_k and dividing by n gives (rho_{p^+}+rho_{p^-})(e_k)=0
for k=1,2, so the sum is zero. Basepoint invariance is tail
invariance of Busemann (2.3).
3.2 CHOICE OF COORDINATES. We allow rotations and reflections
preserving Z^2. Under them, e_1 is the horizontal direction and e_2
the vertical. Because m and C inherit the symmetries of Z^2, we have
-C = C.
3.3 LEMMA (countably many charts). There is a deterministic countable
set D subset C, symmetric under negation, and a countable family of
CHARTS with the following properties. Each chart is specified by:
(a) a choice of lattice coordinates, and (b) a compact arc J of the
dual unit circle S with distinct endpoints rho_l, rho_r that belong
to C. Set I = C intersected with J. Then:
- (contact separation) There is c>0 such that every rho in J and
every d in A(rho) satisfy d_2 >= c.
- (order) The horizontal coordinate r(rho) := rho(e_1) is injective
on J and strictly increasing along J from rho_l to rho_r, with
r(rho_l)<r(rho_r).
- (coverage) Every rho in C minus D lies in the RELATIVE INTERIOR of
some chart arc I.
- (exclusion of exceptional labels) By 2.5 no bigeodesic has an end
in D or in -D.
Consequently almost surely every bigeodesic can be oriented so its
upper label is interior to a chart and its lower label is the
negation.
Proof. Let K = {x : m(x)<=1}
and K* = dual unit ball. For rho in the boundary of K*, the exposed
face F_rho of K is a point or a line segment, and A(rho) is the
radial image of F_rho.
- Functionals with A(rho) of cardinality >1 form a set that is
countable: the interior of each nondegenerate face corresponds to
a unique supporting line, hence a unique rho, and each
nondegenerate circular arc of contact directions contains a
rational angle.
- Functionals that are isolated on one circular side of C are also
countably many: they are endpoints of components of
boundary(K*) \ C, and each open component of the complement meets
a fixed countable dense set of the circle.
Consider a remaining rho in C, so |A(rho)|=1 and C accumulates on
both circular sides. A lattice rotation makes the unique contact
direction d have d_2>0. The contact correspondence rho -> A(rho) is
upper-semicontinuous, so by compactness there is an open boundary
neighbourhood of rho on which every contact has d_2 >= some c>0.
Pick once and for all a countable dense D_0 subset C. In that
neighbourhood, choose points of D_0 on both sides of rho; the compact
boundary arc through rho between them lies inside the neighbourhood.
There are countably many pairs from D_0 and finitely many lattice
coordinates, so a countable chart family suffices. Define D to be
D_0 union the two countable exceptional sets above and their
negations.
Injectivity/monotonicity of r on J: Suppose rho,lambda two chart
points with rho(e_1)=lambda(e_1) and lambda(e_2)>rho(e_2). Take any
d in A(rho); since d_2>0,
lambda(d) = rho(d) + lambda(e_2)-rho(e_2) * d_2 > rho(d) = m(d),
contradicting lambda in K* (the dual ball). Hence rho is the top
point of the vertical slice of K* at its horizontal coordinate, and
r is strictly monotone along an arc. On the opposite arc -I the same
r is strictly monotone with orientation reversed. Combined with 3.1
and 2.5, almost surely every bigeodesic's upper label lies in a chart
interior and its upper contacts tend upward, while its lower contacts
tend downward. Done.
3.4 FROM NOW ON. Fix a chart with label set I. UPPER LABEL means a
label in I, LOWER LABEL means a label in -I. rho_L=rho_l,
rho_R=rho_r are the chart endpoints, r_L=r(rho_L), r_R=r(rho_R), and
W_I := r_R - r_L is the chart width. All "upper rays" point upwards in
the c-separated contact sector of 3.3, and "lower rays" point
downwards.
3.5 A PLANAR FACT. Two disjoint polygonal arcs joining the lower and
upper boundary lines of a strip, both interior to the open strip, have
their left-right endpoint orders the same on the two boundary lines.
(Proof: put the arcs inside a rectangle and run the Jordan curve
theorem on one arc plus one boundary route. Endpoints in reversed
order lie on opposite sides of the Jordan curve, so the other arc
must cross. Nearest-neighbour lattice intersections are lattice
vertices: unit edges either overlap or meet at endpoints.)
3.6 LEMMA (local ray order). Two upper rays p,q from different
starting vertices with disjoint tails have a stable left-right order
at their first visits to row {x_2=N} as N -> infinity. If p is left
of q in that order, then r(rho_p) <= r(rho_q). In particular distinct
labels give disjoint tails and strictly ordered first arrivals by
increasing r.
Proof. Distinct labels have only finitely many common vertices
(2.3(e): infinity of common vertices forces coalescence, hence equal
labels). Choose an integer h above both starts, above all
intersections, and above any finite prefix before the disjoint tails.
After their last visits to row h both rays lie strictly above;
for large N their first arrivals at row N come down onto the ordered
tails, so the order stabilizes.
For strict order we run the row-zero deficit argument. Take
u=(-n,0), v=(n,0). Concatenate the finite geodesic v -> p_j and
p[j..]: this is a finite walk gamma_j. Define
delta_j = T(v,p_j) - B_p(v,p_j) >= 0; delta_j -> 0.
Inside gamma_j, every visited vertex w satisfies
0 <= T(v,w) - B_p(v,w) <= delta_j (* approximation defect)
on the initial geodesic (bounded by delta_j via calibration and
triangle inequality) and on the tail (via triangle inequality and
calibration). Define xi_j similarly for q with u. Because horizontal
directions e_1,-e_1 are OUTSIDE the contact set of any label in the
chart,
gamma_def := min_{lambda in {rho_p,rho_q}, s in {+1,-1}}
[ m(s e_1) - lambda(s e_1) ] > 0,
so any row-zero visit is very expensive: using 2.6 and asymptotic
linearity (rooted at v and u), for some bound K_eps and any
w=(t,0) with d=|t -/+ n| >= n/2,
T(v,w) - B_p(v,w) >= (gamma_def - 10 eps) d - 3 K_eps.
Choosing eps small and n large, the deficit exceeds gamma_def n/4, so
every row-zero visit of gamma_j lies at horizontal coordinate in
(n/2, 3n/2), and every row-zero visit of xi_j likewise in
(-3n/2, -n/2). Now climb to a row N above all finite building
blocks; both walks reach it on their exact upward tails. Their last
row-zero visits have order (xi_j left, gamma_j right); their first
row-N visits have the reverse order (gamma_j left, xi_j right).
By 3.5 their intervening ladder arcs cross at a lattice vertex w_j.
Using the approximation defect (*) on the pieces up to w_j,
B_p(u,v) <= T(u,w_j) - T(v,w_j) + delta_j
<= B_q(u,w_j) - B_q(v,w_j) + delta_j + delta'_j
= B_q(u,v) + delta_j + delta'_j.
Let j -> inf; hence B_p(u,v) <= B_q(u,v). But B_p(u,v) = 2n r(rho_p)
+ o(n) and B_q(u,v) = 2n r(rho_q) + o(n) (asymptotic linearity at u,v
for fixed n). Dividing by 2n and n -> inf gives r(rho_p) <= r(rho_q).
Strict inequality for distinct labels follows from injectivity of r.
3.7 CONES AND CONFINEMENT. Choose s>0 small enough that every upper
contact in the chart has d_2>2s|d_1| and every lower contact has
-d_2>2s|d_1| (possible by compactness and 3.3). Define offset cones
Q^+(z,H) = { w : + (w_2-z_2) >= s|w_1-z_1| - H },
Q^-(z,H) = { w : - (w_2-z_2) >= s|w_1-z_1| - H }.
PROPOSITION 3.8 (uniform confinement). Almost surely there is finite
H(z)>=1 for every z such that every upper ray from z is contained in
Q^+(z,H(z)) and every lower ray from z is contained in Q^-(z,H(z)).
Moreover for every fixed L<infinity,
max_{|z|<=L n} H(z) = o(n) as n -> inf.
Proof. Let Lambda = {rho_L, rho_R, -rho_L, -rho_R}. For each lambda in
Lambda, 2.4(iii) gives the unique ray g_lambda_z from every z and the
common Busemann function B_lambda. Let sigma_lambda=+1 for upper
endpoints and -1 for lower. Define
H(z) = 1 + max_{lambda in Lambda} sup_{w in g_lambda_z}
[ s|w_1-z_1| - sigma_lambda(w_2-z_2) ]_+.
Each supremum is finite: the ray's contact direction lies strictly
inside the cone {sigma_lambda d_2 <= s|d_1|} because the honest
contact slope is 2s, so outside a finite prefix the positive part is
zero.
Uniform o(n): put a_lambda(x) = B_lambda(0,x)-lambda(x) = o(|x|).
Calibration along g_lambda_z gives
T(z,w) = lambda(w-z) + a_lambda(w) - a_lambda(z).
For |z|<=Ln and d=w-z with |d|>=eta n, we have
|x|+|y| <= (1+2L/eta)|d|, and 2.6 + rooted asymptotics give
sup [m(w-z)-lambda(w-z)] / |w-z| -> 0,
uniformly over such (z,w). Since m(d)-lambda(d) is continuous and
strictly positive on {sigma_lambda d_2 <= s|d_1|} (all zeros strictly
inside the 2s cone), for large n every far displacement lies in the
s-cone; the remaining displacements have offset at most
(s+1) eta n. Let eta -> 0.
Trap intermediate rays. Fix z and any upper ray p with
r(rho_L) < r(rho_p) < r(rho_R). Let a=g_{rho_L}_z, b=g_{rho_R}_z,
Q=Q^+(z,H(z)). Their common finite prefix ends at v; their tails are
disjoint (labels differ). Suppose p visits w outside Q. Choose N
above the whole common prefix, above the finite prefix of p up to w,
and large enough for ray-order stabilization (3.6). The three first
arrivals a_N,b_N,p_N at row N have horizontal coords in strict order
(a_N)_1<(p_N)_1<(b_N)_1. The arcs a[v,a_N], b[v,b_N] together with the
row segment [a_N,b_N] form a simple closed curve J; its bounded Jordan
domain D is inside Q (each arc lies in Q, and the segment by
convexity of Q). p's last edge into p_N is vertical from below, so
near p_N it lies inside D. So p must pass from outside D to inside D
before its first row-N arrival, i.e. after w. If it entered through
the top segment we would already have a row-N visit. So it meets one
of the two arcs a[v,a_N] or b[v,b_N] at some lattice vertex u. Both
p[z,u] and the corresponding bounding prefix are finite geodesics;
uniqueness makes them equal. But the bounding prefix lies in Q, while
p[z,u] contains w outside Q: contradiction. So every intermediate
upper ray lies in Q. Endpoint-label rays are already the unique
g_lambda_z. Reflection reverses for lower rays. The derivation was
pathwise on a single event and applied to an arbitrary ray, so it
is a simultaneous assertion for all rays.
3.9 LEMMA (crossing from separated sites). Let x_1<y_1 and suppose
upper rays p from x and q from y satisfy p subset Q^+(x,H_x) and
q subset Q^+(y,H_y). If
s(y_1-x_1) > H_x + H_y + |x_2-y_2|,
and r(rho_p) > r(rho_q), then the rays intersect. Same with lower rays
and lower cones (using horizontal coords of lower labels).
Proof. For upper rays put h=max(x_2,y_2). Both rays have a last visit
to row h (they tend upward); call those vertices x^,y^. By cone
bounds,
|x^_1 - x_1| <= (h-x_2+H_x)/s,
|y^_1 - y_1| <= (h-y_2+H_y)/s.
Adding the two horizontal slack terms and using
(h-x_2)+(h-y_2)=|x_2-y_2|, the separation inequality gives
x^_1 < y^_1. If the rays did not intersect, their tails above row h
would give two disjoint ladder arcs reversed in order versus labels
(3.6), contradiction. Lower rays: h=min(x_2,y_2), reflect in
horizontal axis.
3.10 COROLLARY. On each fixed horizontal row, the required separation
on row |y_1 - x_1| for the crossing criterion is LINEAR in the sum
of the offsets, plus a fixed height term. By 3.8, for sites
y=(N,h) and any fixed ball, the offsets H(y)=o(N). Thus for
sufficiently large N the crossing criterion applies uniformly to all
reverse-ordered pairs of rays starting at any pair of fixed sites on
a fixed row and at y, and also from any other fixed site y' on the
same row.
SECTION 4. EXCEPTIONAL LABELS AND OPPOSITE COALESCENCE
Fix a chart I. We work on the common event where 2.4, 2.6, and 3.8 all
hold.
4.1 LEMMA (calibrated rays). Let p be a ray with Busemann function B.
For any vertex x there is a ray q starting at x with
T(x,q_j) = B(x,q_j) for every j,
and q has the SAME label as p.
Proof. Take finite geodesics from x to p_k. Since p is simple,
|p_k| -> infinity; local finiteness and a diagonal subsequence give a
local limit ray q from x. Each prefix of q eventually equals a prefix
of some finite geodesic, so q is a simple infinite geodesic.
By 2.3, d_k(x) := T(x,p_k) - B(x,p_k) >= 0 -> 0. For w on the
geodesic x -> p_k, 0 <= T(x,w) - B(x,w) <= T(x,p_k) - B(x,p_k) =
d_k(x) (using B(w,p_k) <= T(w,p_k)). Passing to the limit gives
T(x,q_j)=B(x,q_j) along the subseq. For the label: for any w,
T(x,q_j)-T(w,q_j) <= B(x,q_j)-B(w,q_j)=B(x,w), so B_q(x,w) <= B(x,w).
Writing rho,sigma for labels of p,q, asymptotic linearity at w=+/-k e_i
gives sigma(e_i) <= rho(e_i) and (using antisymmetry) sigma(e_i) >=
rho(e_i). So sigma = rho.
4.2 DEFINITION (exceptional labels). A label rho in I is EXCEPTIONAL
in an environment omega if at least one of the following holds:
(E1) two DISTINCT rays of label rho start at the same vertex;
(E2) two rays of label rho have DIFFERENT Busemann functions.
Write E_I(omega) for the set of exceptional labels in I. Similarly for
-I.
4.3 PROPOSITION (countability). Almost surely E_I(omega) is at most
countable. Same for -I.
Proof of E1 (branching countability). Fix a vertex x and two distinct
first edges e,f at x. Claim: at most TWO labels in I have a ray from x
starting with e AND another ray from x starting with f.
Suppose, to the contrary, that rho_1<rho_2<rho_3 in r-order have such
rays. Six rays total. Geodesics from x form a tree (uniqueness of
finite geodesics: rays can only diverge and never re-meet). Choose a
horizontal row high enough that the six first-arrival vertices are
distinct and arranged in three consecutive 2-groups (one per label);
possible because distinct labels have disjoint tails (3.6) and rays
in the e,f branches never meet away from x. Color each of the six by
its first edge (E or F). Each 2-group contains one E and one F, so
the six-letter color word has >= 3 color changes, hence an alternating
length-4 subsequence. Join the two E-colored endpoints along their
common e-branch and the two F-colored endpoints along their common
f-branch. These arcs are disjoint (interiors strictly below the row),
but their endpoints alternate along the row. The first arc plus the
row segment between its ends bounds a Jordan region; the second arc
must cross it away from the row. Contradiction.
Countability follows by taking the countable union over vertices x and
first-edge pairs (e,f).
Proof of E2 (Busemann nonuniqueness countability). Choose a pair x<y
so far apart that 3.9 applies to every reverse-ordered pair of upper
rays from x,y. If B,B' are Busemann functions of upper rays with
labels rho (from x) and sigma (from y) and r(rho)<r(sigma), then
B(x,y) <= B'(x,y). Indeed, take a B-calibrated ray at y (4.1), a
B'-calibrated ray at x, get intersection w, use calibration and
metric bounds:
B(x,y) = B(x,w)-T(y,w) <= T(x,w)-T(y,w)
<= T(x,w)-B'(y,w) = B'(x,y).
Consequently for FIXED x,y (far apart enough), the value ranges
S_rho(x,y) := {B_p(x,y) : p a ray with label rho} satisfy
sup S_rho(x,y) <= inf S_sigma(x,y) whenever r(rho)<r(sigma).
The nonempty open intervals (inf S_rho, sup S_rho) are pairwise
disjoint, hence countable many labels can have a nonzero range at
(x,y). For arbitrary u,v, 3.8 lets us pick y_N=(N,0) so large that the
crossing criterion applies between u and y_N and between v and y_N.
If two Busemann functions of the same label disagree at (u,v), then
additivity forces a disagreement at (u,y_N) or at (v,y_N). Taking the
countable union over u,v gives countability for E2. Reflection gives
the lower-sector statement.
4.4 LEMMA (independent exceptional environments). Let V,W be
independent iid environments. Almost surely, simultaneously for every
rho in E_I(V), all W-rays of label -rho coalesce.
Proof. On the standard Borel configuration space, "p is a simple
ray with label rho" and the exceptionality tests
[p_1(0) = p_2(0) and p_1 != p_2] or
[exists x,y: B_{p_1}(x,y) != B_{p_2}(x,y)]
and the common-tail test
exists a,b>=0 forall k>=0 : q_1(a+k)=q_2(b+k)
are all Borel (2.9). So the bad event
J := { (V,W) : some rho in E_I(V) has two W-rays of label -rho
that do not coalesce }
is analytic, hence measurable in the completion of P*P. For almost
every V in the countability event of 4.3, its section J_V is a
COUNTABLE union over rho in E_I(V) of FIXED-PARAMETER events that
have probability zero in W (2.4(iii) with -rho in C). So P(J_V)=0
for almost every V. Completed-product Fubini gives (P*P)(J)=0. The
remark after 2.9 explains where the universal "all rays" filter is
imposed (outside any existential projection).
4.5 THE HALF-PLANE COUPLING. Let U be iid. For n>=1 set
H_n = { z : z_2 = -n } (a horizontal line)
E_n^+ = { {x,y} : x~y, x_2>=-n, y_2>=-n } (edges at/above H_n).
Let A^{(n)},D^{(n)}, n=1,2,..., be independent iid arrays (each with
law G per coordinate), all independent of U. Define
(V_n)_e = U_e if e in E_n^+, A^{(n)}_e if not in E_n^+,
(W_n)_e = D^{(n)}_e if e in E_n^+, U_e if not in E_n^+.
For every n, (V_n,W_n) has law P*P: the U-coordinates kept in its two
members are disjoint, and the replacement coordinates are independent.
Independence between pairs (V_n,W_n) for different n is neither
asserted nor needed.
4.6 LEMMA (half-plane transfer). There is a deterministic increasing
sequence n_k -> infinity and a probability-one event for the coupling
of 4.5 such that:
(i) For every FINITE collection of upper U-rays and every finite
K subset Z^2, all sufficiently large k have: every ray p in the
collection is a V_{n_k}-ray with EXACTLY its original label, and
B_p^{V_{n_k}}(x,y) = B_p^U(x,y) for all x,y in K. More
precisely, for each such k and p and each x in K,
T_{V_{n_k}}(x,p_j)=T_U(x,p_j) for all sufficiently large j.
(ii) For each fixed n>=1, every lower U-ray q has a tail that is a
W_n-ray with exactly its original label.
Proof. Fix the common event per 2.9 for U and for all V_n,W_n.
Moving-cut metric convergence: put
E_n(T) = sup_{x,y in Z^2} |T(x,y)-m(y-x)| / (|x|+|y|+n).
For a fixed typical metric, E_n(T) -> 0: 2.6 dominates the numerator
outside a finite set of pairs, and the maximum on the finite leftover
divided by n tends to zero. Since each V_n is iid, E_{n_k}(T_{V_{n_k}})
-> 0 in probability for a deterministic increasing subsequence n_k;
Borel-Cantelli gives E_{n_k}(T_{V_{n_k}}) -> 0 along that subsequence.
Part (i): fix an upper U-ray p with label rho in I. Rooted asymptotic
defect:
a(w) = B_p^U(0,w) - rho(w) = o(|w|),
B_p^U(x,z) = rho(z-x)+a(z)-a(x).
Since rho has strictly upper contacts, there is a uniform gap
gamma := min_{|d|=1, d_2<=0} [m(d)-rho(d)] > 0.
For x in K and z in H_n (n>=2 max_K + 1), the vector d = z-x points
downward, |z-x|>=|z|/2 and |x|+|z|+n <= 5|z-x|. So
T_{V_n}(x,z) - B_p^U(x,z)
>= gamma |z-x| - E_n(T_{V_n}) (|x|+|z|+n) - |a(z)| - |a(x)|.
All the "errors" are o(|z-x|) uniformly over K and H_n: E_n is
o(1) by the subsequence, |a(z)| = o(|z|) as |z|>=n->inf. So for all
large k,
T_{V_{n_k}}(x,z) - B_p^U(x,z) >= (gamma/2)|z-x| >= (gamma/4) n_k,
uniformly over x in K and z in H_{n_k}. The U version of the same
estimate also holds.
The last-cut comparison. For j large p_j is strictly above H_n. Take
any finite walk x -> p_j that touches the cut at some z (last such
vertex). Its suffix from z lies strictly above the cut, uses only
E_n^+ edges, and its cost in V_n is at least B_p^U(z,p_j). So
cost_{V_n}(walk) >= T_{V_n}(x,z) + B_p^U(z,p_j)
= B_p^U(x,p_j) + [T_{V_n}(x,z) - B_p^U(x,z)].
The bracket is >= (gamma/4) n_k, so the walk is strictly more
expensive than the corresponding segment cost B_p^U(x,p_j) for x=p_0
in a large-enough ball. Hence every prefix of p minimizes in V_{n_k}
for all large k, so p stays a V_{n_k}-ray.
For x in K: by 2.3, T_U(x,p_j)-B_p^U(x,p_j) -> 0. So for large k this
defect is smaller than (gamma/4) n_k. By the U version of the last-cut
estimate, any U-geodesic to p_j must avoid the cut. Since edges above
E_n^+ are unchanged, that U-geodesic is an unchanged competitor in
V_{n_k}; because the V_{n_k} bound excludes any cut-touching
competitor, we conclude
T_{V_{n_k}}(x,p_j) = T_U(x,p_j) for all sufficiently large j.
This holds simultaneously for all finitely many x in K, so subtracting
distance equalities preserves every B_p(x,y) with x,y in K.
Exact label identification at a fixed cut. Fix one n=n_k for which p
was preserved, and freeze U,V_n,H_n. Choose 0<c<1 and x in the strict
sector x_2 >= c|x|, z in H_n, d = z-x (so d_2<0). Then
|d| >= x_2 + n >= c|x|, |z| <= |d|+|x|, and |z-x| >= kappa
(|x|+|z|) with kappa = c/(c+2)>0 uniformly over the infinite cut.
So by 3.3
m(d) - rho(d) >= gamma kappa (|x|+|z|).
Bounding |a(w)| <= eps|w|+C_eps and using 2.6 (uniform in U and in
the fixed V_n), we get for |x| large in the sector and every z in H_n
min{ T_{V_n}(x,z), T_U(x,z) } - B_p^U(x,z)
>= (gamma kappa/2)(|x|+|z|).
This is the FIXED-CUT barrier. Its error at x was explicitly retained.
So for every such x, the calibration defect tends to zero as the
target runs out along p, and the last-cut argument shows
T_{V_n}(x,p_j)=T_U(x,p_j) for all sufficiently large j. Meanwhile
p_0 has T_{V_n}(p_0,p_j)=T_U(p_0,p_j) for every j (p_0 arbitrary, not
necessarily in the sector). So
B_p^{V_n}(p_0,x) = B_p^U(p_0,x)
for every far-out x in the sector x_2 >= c|x|.
Take c=1/2, x=k e_2 and x=k(e_1+e_2). Dividing by k and using
asymptotic linearity in the two fixed environments: their labels
agree at e_2 and at e_1+e_2. Those two vectors are independent, so
the labels are equal.
All steps for finite collections follow by taking the maximum
threshold. Thus (i).
Part (ii): fix n. Let q be a lower U-ray with label lambda in -I.
Use the "opposite" gap
gamma_- = min_{|d|=1, d_2>=0} [m(d)-lambda(d)] > 0,
a_-(w) = B_q^U(0,w)-lambda(w) = o(|w|).
For c small enough that q_{j,2} <= -c|q_j| eventually (true: contact
directions strictly in the lower sector), if x_2 <= -c|x|, |x|>=2n/c,
z in H_n, then |z-x| >= (c/2)|x| and |x|+|z| <= (1+4/c)|z-x|. Since
z-x points upward, the same fixed-metric estimates give
min{ T_{W_n}(x,z), T_U(x,z) } - B_q^U(x,z)
>= [gamma_- c / (2(c+4))] (|x|+|z|).
This uses only the uniform estimate in the fixed metric W_n (which is
almost surely typical, having iid law).
Choose a=q_L far along q so the barrier applies at a and the remaining
tail lies strictly below H_n. Any walk from a to a later q_j that
touches the cut: take its last cut vertex z; the suffix after z goes
downward with all vertices strictly below H_n, and every edge of that
suffix is outside E_n^+, hence unchanged between U and W_n (only
horizontal edges on the cut are new). The barrier shows the walk is
strictly more expensive than the segment of q. Walks avoiding the
cut have their U cost. So the tail from a is a W_n-ray with the
same distances.
Finally, for far x in the strict lower sector, the U-defect relative
to q_j tends to zero, and the barrier plus the last-cut argument
give T_{W_n}(x,q_j)=T_U(x,q_j) for all sufficiently large j. Using
the preserved anchor a yields equality B_q^{W_n}(a,x)=B_q^U(a,x) for
x in the sector. Taking x=-k e_2 and x=-k(e_1+e_2), asymptotic
linearity in the two fixed metrics identifies the label of the
W_n-tail as exactly lambda.
All W_n were included in the initial probability-one intersection, so
the argument applies to every fixed n and every lower ray.
4.7 PROPOSITION (opposite coalescence at exceptional labels). Almost
surely, simultaneously for all rho in E_I(U), every two U-rays of
label -rho coalesce. Almost surely the same holds with upper and
lower exchanged. These conclusions hold simultaneously across the
countable chart family.
Proof. Use the coupling of 4.5. For every n, 4.4 applies to
(V_n,W_n); intersect over n and with the event of 4.6.
Fix rho in E_I(U) and two upper rays witnessing its exceptionality.
If they witness branching, their distinct paths and common start are
preserved by 4.6(i) for every sufficiently deep subsequence cut. If
they witness different Busemann functions, choose one pair (x,y)
where those functions differ and include x,y in the finite witness
set of 4.6(i). At every sufficiently deep subsequence cut the two
paths retain both their exact label rho and those unequal evaluations.
In either case choose one such cut n: rho lies in E_I(V_n).
Now let q,q' be any two lower U-rays of label -rho. 4.6(ii) at that
fixed n supplies tails of both that are W_n-rays of the SAME exact
label -rho. Those coalesce because (V_n,W_n) is an independent pair
(4.4). So q and q' coalesce on their tails (equality of tails is
equality of vertex sequences). The argument made arbitrary pathwise
choices after the common event was fixed, so we get the simultaneous
assertion in the coupling, hence in its U marginal; reflection gives
the reversed statement; countably many charts all at once.
SECTION 5. THE LABEL BUDGET ON A HORIZONTAL LINE
5.0 THE LOGICAL ROLE. This section gives the tool that ultimately kills
the existence of a bigeodesic: a single inequality relating three
quantities - the gain b, the grid spacing l, and a marking probability
q. Every other section either feeds into this or uses it.
5.1 THE PICTURE. Suppose T is the base metric, T^k is obtained from T by
INCREASING finitely many edges near a lattice site k (so all distances
in T^k are at least those in T). Suppose a bigeodesic through k in T^k
has upper label rho between two reference labels alpha<beta (in
r-order), and suppose on the initial portions of its two arms we have
paid a total EXTRA cost of at least b > 0 relative to T.
Intuition: pick a far-away reference site y on the same horizontal row,
to the RIGHT of k. The alpha-family and the -beta-family of T have
unique rays from y (2.4(iii)). Because alpha is strictly left of rho
and -beta is strictly right of -rho (by the ordering r(-beta) =
-r(beta) < -r(rho) = r(-rho)), those reference rays cross the two arms
of our marked bigeodesic (3.9). Their crossing points must be OUTSIDE
the ball of changed edges (choosing y far enough). So the extra cost b
is paid strictly BEYOND the crossing points.
Now run a competing walk: from the upper crossing w^+, go backwards
along the upper reference ray to y, then forwards along the lower
reference ray from y to w^-. This competing walk has a base cost of
B_alpha(y,w^+) + B_{-beta}(y,w^-), which is unchanged in T^k. Compare
it to the actual marked bigeodesic segment from w^- through k to w^+,
whose cost in T^k is at least g^+ + B_alpha(k,w^+) for the upper piece
and g^- + B_{-beta}(k,w^-) for the lower piece, with g^+ + g^- >= b.
Optimality of the marked segment (it is a bigeodesic in T^k) says
g^+ + g^- + B_alpha(k,w^+) + B_{-beta}(k,w^-)
<= B_alpha(y,w^+) + B_{-beta}(y,w^-).
Additivity (B(x,z) = B(x,y)+B(y,z)) cancels the increments at the two
crossings, leaving exactly
b <= B_alpha(y,k) + B_{-beta}(y,k).
Call this the BUDGET INEQUALITY.
The telescoping argument: for consecutive grid sites k_j=(jl,0) marked
in the same bin (alpha,beta), the incremental form
B_alpha(k_{j+1}, k_j) + B_{-beta}(k_{j+1}, k_j)
of the budget sums along the row. Both fixed-label Busemanns are
asymptotically linear with slopes r(alpha) and -r(beta), so on the
horizontal line
B_alpha(0, k_j) + B_{-beta}(0, k_j) = -[r(beta)-r(alpha)] jl + o(jl).
Summing the budget inequality over many consecutive marks and letting
the total number of marks extend to infinity gives
(b / l) * q_{alpha,beta} <= r(beta) - r(alpha),
where q_{alpha,beta} is the marginal probability that any given grid
site is marked in this bin.
We now make all of that precise.
5.2 PARTITIONS. Choose deterministic nested finite sets
D_1 subset D_2 subset ... of labels in I,
with union D_I dense in I and containing both rho_L and rho_R, and also
containing the endpoints of every complementary interval of r(I) in its
convex hull. There are countably many such intervals, so possible.
The BINS of the partition Pi_j are the intervals
(alpha, beta)_I = { rho in I : r(alpha) < r(rho) < r(beta) },
as (alpha,beta) run over consecutive pairs of D_j in r-order. Empty
bins are allowed. Widths always sum to
sum over bins (r(beta)-r(alpha)) = W_I = r_R - r_L.
Every two DISTINCT labels in I minus D_I land in different bins for
large enough j: if a label lies strictly between them, density of D_I
gives an intervening element of some D_j; if they are endpoints of a
complementary interval, they are both already in D_I, contradiction.
By 2.5, on a single probability-one event no bigeodesic has an end
label in D_I union (-D_I), AND the fixed-functional structural
conclusions of 2.4(iii) hold simultaneously for every element of
D_I union (-D_I) in some countable collection of environments. Fix
that event once for the whole construction.
5.3 LEMMA (comparison after a finite increase). Suppose T is the base
metric and T^k is obtained by increasing finitely many edge weights.
Both environments satisfy all the structural inputs of 2.4. Let k,y
lie on the same horizontal row with k_1<y_1, and let (alpha,beta)_I be
a bin. Suppose the following:
(i) Every changed edge has both endpoints in {z: |z-k|_inf <= R},
R>=1.
(ii) In T^k there is an oriented bigeodesic through k with upper
label rho in (alpha,beta)_I. Its arms p^+,p^- lie in
Q^+(k,H_p) and Q^-(k,H_p).
(iii) Finite initial portions of these two arms have all vertices in
the ball of radius R about k, and the total increase from T
to T^k along those portions is at least b>0.
(iv) The BASE rays from y of labels alpha and -beta lie in
Q^+(y,H_c) and Q^-(y,H_c).
Then there is a separation S = S(s, R, H_p, H_c) such that y_1-k_1 > S
implies
b <= B_alpha(y,k) + B_{-beta}(y,k). (*)
One may take
S = max{ R + (R+H_c)/s, (H_p+H_c)/s } <= C_s (1 + R + H_p + H_c),
with C_s depending only on s. In particular S is uniform over bins and
does not depend on the size of the increase.
Proof. Let d = y_1 - k_1. If w is in the ball of radius R about k,
then |w_2 - y_2| <= R and |w_1 - y_1| >= d - R. Membership in either
comparator cone would need R >= s(d-R) - H_c; so
d > R + (R+H_c)/s
makes the two base reference rays AVOID the ball entirely. Their edge
weights are unchanged in T^k, and everything else only increased, so
they remain geodesic rays in T^k with unchanged labels (2.7).
Increase d further, if necessary, to apply 3.9 with offsets
H_p (marked arms) and H_c (reference rays). The marked upper ray p^+
starts at k (left of y at site) but has r(rho) > r(alpha), so 3.9
applies with STRICT reverse order: the upper reference from y meets
p^+. The lower reference from y meets p^- likewise, since
r(-beta) = -r(beta) < -r(rho) = r(-rho) makes the lower reference
to the LEFT of the marked lower arm while y is right of k. Let the
crossings be w^+ and w^-. By the cone-avoidance estimate, both lie
OUTSIDE the ball of radius R. Consequently both occur after the whole
prescribed initial gain portion of their respective arm. (Even if
the arm wanders into and out of the ball, every vertex of the
prescribed portion is in the ball by (iii), so no vertex of the
prescribed portion can equal a crossing at w^+ or w^-.)
Let g^+, g^- be the increases along those prescribed portions, so
g^+ + g^- >= b. Writing cost_T for the cost of a specified finite path
in the base weights, domination by passage time and then by a Busemann
increment gives
cost_{T^k}( p^+[k, w^+] ) >= g^+ + cost_T( p^+[k,w^+] )
>= g^+ + B_alpha(k, w^+),
cost_{T^k}( p^-[k, w^-] ) >= g^- + cost_T( p^-[k,w^-] )
>= g^- + B_{-beta}(k, w^-).
The marked segment from w^- through k to w^+ is minimizing in T^k
because it lies on a bigeodesic. A competing finite walk follows the
lower reference ray backwards from w^- to y, then follows the upper
reference ray from y to w^+. Its cost in T^k equals its base cost (no changed edge is used, both
crossings lie outside the changed ball), namely
B_alpha(y, w^+) + B_{-beta}(y, w^-).
Both terms are forward-along-the-ray costs. The alpha ray from y
runs upward through w^+, with cost B_alpha(y,w^+) along it. The
-beta ray from y runs downward through w^-, with cost B_{-beta}(y,w^-)
along it. Both costs are nonnegative.
Non-disjointness of the two reference portions is irrelevant: a
finite walk may repeat vertices, and its cost counts every traversal.
Comparison with the marked segment gives
b + B_alpha(k, w^+) + B_{-beta}(k, w^-)
<= B_alpha(y, w^+) + B_{-beta}(y, w^-).
Additivity B_alpha(k,w^+) = B_alpha(k,y) + B_alpha(y,w^+) and
B_{-beta}(k,w^-) = B_{-beta}(k,y) + B_{-beta}(y,w^-) cancels the
w-increments, and the surviving inequality is exactly (*).
Both the avoidance bound and the crossing-separation bound have the
claimed dependence on offsets and R. Done.
5.4 PROPOSITION (label budget). Fix a bin (alpha,beta)_I, an integer
spacing l >= 1, and a gain b > 0. Place a common probability space with
a random marking of sites k_j = (jl, 0), j in Z. Suppose:
(a) every site k_j has the SAME marginal probability q_{alpha,beta}
of being marked in this bin, and
(b) the base environment has all the fixed-label asymptotics of 2.4,
and
(c) for any two SUCCESSIVE marked sites k<y in the bin, the
comparison (*) of 5.3 holds.
Then
(b / l) * q_{alpha,beta} <= r(beta) - r(alpha). (**)
No independence or ergodicity of the marks is assumed.
Proof. Set w = r(beta) - r(alpha) > 0. For j>=0, put
A_j = B_alpha(0,k_j) + B_{-beta}(0,k_j).
By asymptotic linearity of the two fixed-label Busemanns,
A_j = -w j l + e_j, e_j = o(j l) as j -> infinity.
(The minus sign: alpha(e_1)+(-beta)(e_1) = r(alpha) - r(beta) = -w.)
Let E_N = max_{0<=j<=N} |e_j|. We claim E_N/(N l) -> 0 a.s. For any
delta>0 choose J such that |e_j| <= delta j l for j>=J. The finitely
many earlier errors have a finite maximum C_J. Then E_N <=
max{C_J, delta N l}. Let N -> infinity; then delta -> 0. This
handles random first/last marked indices uniformly.
Let m_N = number of marked sites in {k_0,...,k_N}. If m_N >= 2, list
their indices as i_1 < i_2 < ... < i_{m_N}. Summing (*) over
consecutive marked sites and using additivity telescopes:
b (m_N - 1)
<= A_{i_1} - A_{i_{m_N}}
= w l (i_{m_N} - i_1) + e_{i_1} - e_{i_{m_N}}
<= w l N + 2 E_N.
For m_N = 0 or 1 the same upper bound applies to b (m_N - 1)_+.
Hence in all cases
b m_N <= b + w N l + 2 E_N,
and dividing by N l,
limsup_{N->inf} m_N/(N l) <= w/b almost surely. (***)
Now for expectation. Use the deterministic bound
0 <= m_N/(N l) <= (N+1)/(N l) <= 2/l, N>=1.
Fatou's lemma applied to the nonnegative random variables
2/l - m_N/(N l) gives the bounded reverse-Fatou inequality
limsup_N E[ m_N/(N l) ] <= E[ limsup_N m_N/(N l) ] <= w/b.
Equal marginal probabilities q_{alpha,beta} across the sites via
linearity of expectation give E[m_N] = (N+1) q_{alpha,beta}. Hence
q_{alpha,beta} / l <= w / b
which is precisely (**). Crucially, this proof takes no expectation
of a Busemann error or a Busemann increment.
5.5 USABLE EDGES. Before the one-edge density argument we fix a
"usable fraction" of a long simple path.
LEMMA 5.6. There exist real numbers a_0 < b_0 with
p_a := G([0, a_0]) > 0,
q := G([0, b_0)) < 1/64,
p_b := G([b_0, infinity)) = 1 - q > 0.
Call an edge USABLE if its weight is >= b_0, and put
theta := 8 sqrt(q) < 1. For any vertex x and integer n_0 >= 1:
P( some simple path from x of length j >= n_0 has fewer than
j/2 usable edges )
<= theta^{n_0} / (1 - theta).
If U_n is the event that EVERY simple path from [-3n,3n]^2 of length
>= n/2 has at least half its edges usable, then
P(U_n^c) <= (6n+1)^2 theta^{ceil(n/2)}/(1-theta) -> 0.
Almost surely every fixed vertex x eventually has all its long simple
paths satisfying the fraction bound.
Proof. Let a be the bottom of the support of G (finite, no atom at a).
As b -> a+ the probability G([0,b)) -> 0 while staying positive.
Choose b_0 > a so G([0,b_0)) < 1/64, and a_0 in (a, b_0). Then
p_a > 0 by definition of the bottom of support.
For a fixed simple path of length j, its edges are distinct. The
probability that at least j/2 of them are unusable is bounded by
sum_{k >= j/2} C(j,k) q^k <= 2^j q^{j/2}.
There are at most 4^j nearest-neighbour simple paths of length j from
a given x. So
P( some such path has >= j/2 unusable ) <= 4^j * 2^j * q^{j/2}
= (8 sqrt(q))^j = theta^j.
Summing over j >= n_0 gives theta^{n_0}/(1-theta). The box version
follows by a further union bound over (6n+1)^2 starting vertices.
Finally, the tail events decrease in n_0 with probability tending to
zero; countability gives the last assertion. No moment of an
individual edge weight is used.
5.7 THE ONE-EDGE BUDGET: EXPECTED EDGE-LABEL COUNT. Fix a chart I.
For an edge e={x, x+v} with v a unit vector, and H>=1, define
N_e(H) = 0 if e is unusable or the following regularity fails;
N_e(H) = # { rho in I : e lies on a bigeodesic of upper label rho }.
The "regularity" referred to is: from each endpoint z of e, EVERY ray
of label in I lies in Q^+(z,H), and EVERY ray of label in -I lies in
Q^-(z,H). (N_e(H) can be infinity; see below.)
The universal "all-ray" regularity is measurable as a coanalytic
event (2.9); we impose it OUTSIDE any existential path projection.
PROPOSITION 5.8. There is C finite, depending only on the chart and
the weight law G, such that for every lattice edge e and every H>=1,
E[ N_e(H) ] <= C (H+1).
Proof. FIX a unit vector v. Let e_k = {k, k+v} for sites k on a
horizontal grid (spacing chosen below). Use a base iid environment t
and independent resamples t^_e with law G for each such edge.
The individual environment t^k = t off e_k, = t^_e_k on e_k. Each
t^k is itself iid. Take the common probability-one event for the base
and for all the countably many individual environments, including the
D_I/-D_I exclusions and shared comparative Busemann asymptotics
(5.2).
Fix a bin (alpha,beta)_I. Let A_e^{alpha,beta}(H) be the event, in an
iid environment, that e is usable, the regularity holds, AND some
bigeodesic with upper label in the bin uses e. Mark a grid site k in
this bin if BOTH:
t_{e_k} <= a_0, and A_{e_k}^{alpha,beta}(H) holds in t^k.
The key independence: t_{e_k} alone is independent of the WHOLE
individual environment t^k (which depends on t off e_k and the
resample t^_{e_k}). So
q_{alpha,beta} = p_a * P( A_e^{alpha,beta}(H) )
is the common marginal marking probability, uniform in k, uniform in
v.
On a marking event, the one changed edge has been increased by at
least b_0 - a_0. Witnessing bigeodesics pass through k; one of the
two directions has e_k as its first edge. Use that edge as the gain
portion of the arm; use the empty portion of the other arm. The
modification and both gain portions fit in a ball of radius one, and
the total gain is at least b = b_0 - a_0 > 0.
The regularity in t^k confines marked arms with offset H. We must
ALSO bound the base comparator rays at y=k: base regularity was not
assumed. Take any base ray q from k with label in I or -I. If q
avoids e_k, all its edge weights are unchanged and q remains a ray
(monotonicity), with unchanged label (2.7). Its offset is <= H by the
regularity in t^k. If q uses e_k first, its tail from k+v avoids e_k
and remains a ray in t^k with unchanged label; the tail lies in the
corresponding cone at k+v with offset H. Then for either sign,
+/- (w_2-k_2-v_2) >= s|w_1-k_1-v_1| - H
implies
+/- (w_2-k_2) >= s|w_1-k_1| - (H + |v_2| + s|v_1|).
Including the initial vertex k and the initial edge by convexity
confines the whole base ray with offset at most H+1+s. So the base
comparator has offset H_c = H+1+s at both labels alpha and -beta.
Choose grid spacing l = l(H) large enough for 5.3 with R=1, H_p=H,
H_c=H+1+s. We can choose
2 <= l(H) <= C_0 (H+1)
for a chart-dependent constant C_0, uniformly in the direction v (the
lower bound makes the edges e_k at distinct grid sites distinct, the
upper bound keeps l bounded by C_0(H+1)). Any two marked sites are
now sufficiently separated for 5.3. Applying 5.4 and the marking
inequality:
P( A_e^{alpha,beta}(H) )
<= [l(H) / ((b_0 - a_0) p_a)] (r(beta)-r(alpha)).
For a finite partition Pi_j, let K_j(e,H) count the number of
OCCUPIED bins among the labels counted by N_e(H). By linearity of
expectation and the chart-width identity,
E[ K_j(e,H) ] <= l(H) W_I / ((b_0 - a_0) p_a). (****)
On the event excluding D_I as bigeodesic labels, refinement never
loses a counted label: K_j is nondecreasing in j. Every FINITE
collection of distinct counted labels is eventually in distinct
bins. Hence K_j(e,H) -up-> N_e(H) also when the latter is infinite
(apply the separation assertion to arbitrarily large finite
collections). Monotone convergence, followed by the spacing bound
2 <= l(H) <= C_0(H+1), gives
E[ N_e(H) ] <= C (H+1)
with C from C_0, b_0-a_0, p_a, W_I. Translation invariance and the
finite number of edge directions give one constant for all e.
SECTION 6. FORKS AND UNIQUENESS OF BUSEMANN PAIRS
6.1 SETUP. Continue with the fixed chart I. An UPPER FORK at x
consists of two bigeodesics, oriented towards upper labels in I,
with the SAME upper label, coinciding backwards from x, and with
different first edges forwards from x. Equivalently: a common
backwards tail and a split at x. (A LOWER FORK is the same with
orientation reversed.) Forks are existence events with two path
witnesses and a label witness, hence measurable in the completed
space (2.9).
6.2 PROPOSITION (no forks). Almost surely there is no upper or lower
fork in any of the countably many charts.
Proof. We exclude upper forks in one chart; the reflected argument
excludes lower forks; the union over the countably many charts then
gives the proposition.
Work on the event of 4.7 (opposite coalescence). Every upper fork
label rho satisfies (E1) of 4.2, so rho is exceptional; hence all
lower rays of label -rho coalesce. Consequently a FINITE collection
of bigeodesics with common upper label rho has a common lower tail.
For n>=2 let F_n be the number of upper fork sites in [-n,n]^2, and
let p_fork = P(0 is an upper fork). The chart and the fork condition
are translation invariant, so
0 <= F_n <= (2n+1)^2, E[F_n] = (2n+1)^2 p_fork. (i)
Fix eps>0 and H_n = ceil(eps n). Let G_n be the intersection of the
usable-edge event U_n of 5.6 with the event that R_e(H_n) holds for
EVERY edge e with both endpoints in the outer box [-2n,2n]^2. By 3.8
(boxed uniformity) and 5.6 (probability tail), P(G_n^c) -> 0 for
each fixed eps.
DETERMINISTIC INEQUALITY ON G_n, for n>=2:
(n/4) F_n <= sum_{e in [-2n,2n]^2} N_e(H_n). (ii)
Fix, for each of the F_n upper fork sites x, an ordered pair
(p^+_x, p^-_x) of bigeodesics realizing the fork, with common upper
label rho_x. Group the witnesses by their exact label rho; a group of
q >= 1 fork sites has 2q witnesses (sharing possibly common prefixes
below their splits, but distinct forward arms).
Claim 1 (common past, tree). The 2q witnesses of a group share a
vertex o below every split, and the union of their forward halves
from o is a rooted tree with root o.
Proof: the 2q lower rays all have label -rho; since rho is exceptional
(E1), 4.7 makes them pairwise coalesce. A finite pairwise-coalescing
family has a common tail (beyond all merging points). Choose o far
enough out. Each forward half is a ray from o (a tail of a geodesic is
geodesic). If two forward halves meet at vertex z, finite uniqueness
(2.2) forces their shared initial segments from o to z to be identical;
so two distinct forward halves agree on an initial segment and split
at most once, and never diverge and re-meet. Each visited vertex
v != o therefore has a unique parent (its predecessor on any path
reaching it), and the resulting graph is acyclic and connected: a
rooted tree.
Claim 2 (finite subtree, leaf count). Let T be the finite subtree of
that tree obtained by keeping, for each of the q split vertices s (one
per fork site), the root paths from o to the two children of s
immediately after the split. Let L be the number of leaves of T. Then
L - 1 = sum_{u in T : deg_T^+(u) > 0} (deg_T^+(u) - 1) >= q.
Proof: in any finite rooted tree, sum of deg^+ over internal vertices
equals |edges| = |V_T| - 1, and |V_T| - 1 = (L - 1) + (# internal
vertices). Solving gives the identity. Each split s has
deg_T^+(s) >= 2, contributing >= 1. So L >= q + 1.
Claim 3 (leaf continuations). Each leaf of T is a child of a fork
vertex in [-n,n]^2, hence lies in [-n-1,n+1]^2. From each leaf,
follow its witness bigeodesic forwards until the first hit of the
boundary of the outer box [-2n,2n]^2. This is the leaf continuation.
Then:
(a) it starts at a vertex of [-n-1,n+1]^2 subset [-3n,3n]^2;
(b) it has length >= n-1 >= n/2 (distance in sup norm from leaf to
the outer-box boundary is 2n - (n+1) >= n-1);
(c) every edge has both endpoints in the outer box;
(d) continuations of distinct leaves are pairwise vertex-disjoint.
Proof of (c): we stop at the first boundary hit. Every prior vertex is
strictly inside the outer box; unit steps between strictly-interior
vertices have both endpoints in the outer box.
Proof of (d): two continuations from leaves L_1 != L_2 sharing a
vertex w would give two forward paths o -> L_i -> w on their
respective witness bigeodesics, hence two o-to-w geodesics. Finite
uniqueness makes them agree; so L_1 and L_2 lie on a single root path
of T, making them comparable ancestors, contradicting their being
distinct leaves.
Claim 4 (usable edges credit the label). On G_n, each leaf
continuation satisfies U_n (start in [-3n,3n]^2, length >= n/2),
so at least half its edges are usable; by (b), at least n/4 usable
edges, all inside the outer box. On G_n, R_e(H_n) holds for every such
edge e. Also e lies on a genuine witness bigeodesic with upper label
rho and both arms lying in the appropriate cones (R_e(H_n) applied at
each endpoint), so e contributes rho to N_e(H_n). Distinct leaf
continuations of the SAME group do not share an edge (Claim 3(d)), so
within a group no edge is credited twice with rho. Two different
groups have different rho and thus distinct (e,rho) pairs even when
the underlying edge is the same.
Sum over groups. A group with q_g fork sites contributes at least L_g
leaf continuations, each yielding >= n/4 usable edge-label credits,
so contributes >= (n/4) L_g to sum_e N_e(H_n). Groups are disjoint in
labels, so their contributions are disjoint in (e,rho) pairs. Also
sum_g L_g >= sum_g (q_g + 1) >= sum_g q_g = F_n whenever F_n >= 1,
and (ii) is trivial when F_n = 0. Hence (ii).
Expectation step. Take expectations of (ii) on G_n:
(n/4) E[F_n 1_{G_n}] <= sum_e E[N_e(H_n) 1_{G_n}]
<= sum_e E[N_e(H_n)].
From (i), E[F_n 1_{G_n}] >= (2n+1)^2 (p_fork - P(G_n^c)). The outer
box has 2(4n)(4n+1) <= 40 n^2 edges. Using 5.8:
(n/4)(2n+1)^2 (p_fork - P(G_n^c)) <= 40 C n^2 (ceil(eps n)+1).
The loss (n/4)(2n+1)^2 P(G_n^c) = o(n^3) for fixed eps, while the
right side is O(eps n^3). Divide by n^3 and let n -> infinity:
p_fork <= 40 C eps.
Send eps -> 0: p_fork = 0. Countability of vertices excludes every
upper fork almost surely. Reflecting the vertical axis excludes every
lower fork. Union over the countable chart family finishes the proof.
6.3 COROLLARY (common Busemann pair for a common label). On a single
probability-one event, whenever two oriented bigeodesics p,q in any
fixed chart have the SAME upper label, their two Busemann functions
agree:
B_{p^+} = B_{q^+}, B_{p^-} = B_{q^-}.
This is simultaneous over all bigeodesics and their possibly random
labels. It also holds almost surely in every environment whose law
is absolutely continuous with respect to the iid law, and
simultaneously for a countable collection of such environments.
Proof. Work on the intersection of the probability-one events of
4.7, 6.2, and the structural inputs.
Two bigeodesics with common upper label rho. If their upper Busemann
functions differ, rho satisfies (E2), so by 4.3 it is exceptional. By
4.7 all lower rays of label -rho coalesce; in particular the lower
rays of p,q coalesce, so some sufficiently far vertex o lies on the
common lower tail. The forward portions of p and q from o are upper
geodesic rays. If they had a common tail, by tail invariance of the
Busemann function their upper Busemanns would agree, contradiction;
so they must split at a first vertex. Finite uniqueness prevents any
later meeting, so the split is an upper fork with common past,
contradicting 6.2. Thus the upper Busemanns agree.
If lower Busemanns differ, the lower label -rho satisfies (E2), so it
is exceptional; by 4.7 the UPPER rays of p,q coalesce. Reverse the
previous argument to get a forbidden lower fork. Hence both equalities.
All deductions are pathwise on the stated event. No uncountable union
of fixed-label null events is taken; no coalescence of every
one-sided family at random labels is invoked. Absolute continuity
transfers the event to each changed environment (2.8); countable
intersection gives the final assertion.
SECTION 7. FINITE PERTURBATIONS: GAIN WITHOUT DENSITY COST
7.1 SETUP. Fix a chart I with slope s>0 and the partitions Pi_j of
5.2. Fix a deterministic H_0 >= 1 and let p > 0 be the probability of
the following event B(0) in an iid environment: there is a bigeodesic
through 0 whose upper label is in I, whose two arms lie in
Q^+(0,H_0) and Q^-(0,H_0). Later (section 8) we reduce a positive
probability of bigeodesics to precisely this situation.
We construct, for every positive integer M, MARKS with probability
bounded below independently of M, and with a large gain M along the
initial portion of the selected bigeodesic in an inflated environment.
A separate tiny requirement - a strictly raised edge among the first
R_0 steps - prevents two marks on a well-separated grid from having
the same label. R_0 is FIXED; the larger radius needed for gain M
depends on M.
7.2 THRESHOLDS AND STANDARD TRIPLES. Use the a_0<b_0 of 5.6. Put
p_a = G([0,a_0]) > 0, p_b = G([b_0, infinity)) > 0, g = b_0-a_0>0,
q = G([0,b_0)) with 8 sqrt(q) < 1. An edge is usable if its weight is
>= b_0.
Let mu = G^E be the iid law of the base environment. Take, independently
for every edge e, a triple (X_e, U_e, Z_e) where
X_e ~ G, U_e ~ Unif[0,1], Z_e ~ G(. | [b_0, infinity)),
jointly independent, triples independent across edges. The base
environment is X = (X_e)_e with metric T. All variants below use these
same triples (a "shared" family).
For an edge e with endpoints w,w', put h(e)=max(|w_2|,|w'_2|) and
delta_h = eta / [ (h+2) log(h+2) ], h >= 0,
with eta>0 chosen shortly, independently of M. Require delta_0 <= p_a/2.
Define the indicator
xi_e = 1{ X_e <= a_0 and U_e <= delta_{h(e)}/p_a },
Xhat_e = Z_e if xi_e = 1, X_e otherwise.
Then Xhat_e >= X_e, and Xhat_e - X_e >= g whenever xi_e = 1.
For a horizontal site k=(k_1,0) and integer R>=1, the raised region is
A_k(R) = { e : h(e) <= R and
max_{w endpoint of e} |w_1-k_1| <= 1 + (h(e)+H_0)/s }.
Set Y^{k,R}_e = Xhat_e on A_k(R) and X_e elsewhere; this environment
has metric T^{k,R}. For two horizontal sites k,y, set Y^{k,y,R} to use
Xhat_e on the union A_k(R) union A_y(R), with metric T^{k,y,R}. In an
overlap, one sample Xhat_e is used; we never inflate an edge twice.
Justification of the geometric bound: if a bigeodesic through k has
arms in Q^\pm(k,H_0), then every vertex w of either arm satisfies
s|w_1-k_1| <= |w_2| + H_0,
which implies that every edge of that bigeodesic with h(e) <= R lies
in A_k(R). In particular the first R upper-arm edges lie in A_k(R):
the j-th edge has h(e) <= j.
7.3 LEMMA (uniform change of law). Every individual environment
Y^{k,R} and every union environment Y^{k,y,R} has law absolutely
continuous with respect to mu, and there is C finite (dependent only
on s, H_0, p_a, p_b) such that the density L_{k,R} = dLaw(Y^{k,R})/dmu
satisfies
E_mu [ L_{k,R}^2 ] <= exp(C eta^2),
|| Law(Y^{k,R}) - mu ||_TV <= (1/2) sqrt( exp(C eta^2) - 1 ).
The bounds are uniform in k and R.
Proof. For h=h(e), the law of Xhat_e has density relative to G:
lambda_h(t) = 1 - (delta_h/p_a) 1_{[0,a_0]}(t)
+ (delta_h/p_b) 1_{[b_0,infinity)}(t).
The two indicator sets are disjoint. Direct integration gives
int lambda_h dG = 1,
int lambda_h^2 dG = 1 + (p_a^{-1} + p_b^{-1}) delta_h^2.
For any deterministic finite replaced set, independence of the triples
makes the full density a product of one-edge densities; the exterior
is its original iid product. Absolute continuity holds.
For an individual region, let N_h count edges of height h in A_k(R).
At positive height h, horizontal edges of the boundary rows have
h(e)=h, vertical edges lie in the two strips adjoining those rows
toward height zero. Each of these rows/strips contains at most
2(1+(h+H_0)/s)+1 admissible edges, so there is c_s = 12+8/s with
N_h <= c_s (h + H_0 + 1).
Then
E_mu[ L_{k,R}^2 ] = prod_{e in A_k(R)} (1 + (p_a^{-1}+p_b^{-1})
delta_{h(e)}^2)
<= exp{ c_s (p_a^{-1}+p_b^{-1}) eta^2 *
sum_{h>=0} (h+H_0+1) / ((h+2)^2 log^2(h+2)) }.
The series is finite; leading terms are 1/(h log^2 h). This gives C.
Finally, since E_mu L_{k,R}=1, Cauchy-Schwarz gives the TV bound.
Choose eta>0 so small that delta_0 <= p_a/2 and the TV bound above
is at most p/8. Fixed for the rest.
7.4 LEMMA (posterior law). Fix k,R. Conditional on the whole
individual environment Y^{k,R}, the indicators (xi_e : e in A_k(R))
are independent Bernoulli with success probabilities
theta_e( Y^{k,R}_e ) = 1_{[b_0,infinity)}(Y^{k,R}_e)
* delta_{h(e)} / (p_b + delta_{h(e)}).
The assertion includes the conditioning on all the unchanged
exterior edges. If a simple path is selected measurably from this
individual output ALONE, the same product law holds on any finite
prefix of the selected path lying in A_k(R), once that prefix is
fixed by the conditioning.
Proof. For e in A_k(R), put Y_e=Xhat_e, h=h(e). As measures in t,
P(xi_e=1, Y_e in dt) = (delta_h/p_b) 1_{[b_0,infinity)}(t) G(dt),
P(xi_e=0, Y_e in dt) = [1 - (delta_h/p_a) 1_{[0,a_0]}(t)] G(dt).
The first identity multiplies the low-input probability p_a, the
replacement probability delta_h/p_a (conditional on X_e<=a_0), and
the conditional law of Z_e. In the second, the original sample is
retained, except for the removed mass on [0,a_0]. Dividing the second
density by the sum gives the posterior.
The pairs (xi_e,Y_e) are independent across A_k(R), so their
conditional kernel given the output vector is the product of the
kernels just computed. The exterior outputs (Y_e for e notin A_k(R))
= (X_e for e notin A_k(R)) are independent of the inside triples.
A monotone-class argument extends to all of sigma(exterior).
For the path-prefix assertion, the path space is standard Borel;
a selector measurable in the completion has a Borel version. Given
the output, a finite prefix of that version is a fixed list of
distinct edges; restricting the product kernel to that list proves
the assertion. This does NOT include output at another site.
7.5 CHOICE OF n_0 AND THE EVENT E_{k,R}. Choose deterministic n_0 so
that the event
U_{n_0}(k) = { every simple path from k of length d >= n_0 has at
least d/2 usable edges }
has iid failure probability at most p/8. (Direct from 5.6; the
geometric tail tends to zero; no moment of a single edge weight is
used.)
Write
E_{k,R} = { Y^{k,R} in B(k) intersect U_{n_0}(k) },
where B(k) is the translate of B(0). The TV estimate implies,
UNIFORMLY in k,R:
P( E_{k,R} ) >= p - p/8 - p/8 >= p/2.
By 2.9 select a witnessing oriented bigeodesic and its upper label
using Y^{k,R} alone. Use the same selection rule at 0 and at its
horizontal translates (translate the selector accordingly). On
E_{k,R}, the usable-prefix condition is already determined by the
output, so it adds no information when applying 7.4.
7.6 LEMMA (divergent gain along selected prefixes). There is fixed
R_0 >= n_0 such that, for each positive integer M, one can choose
R(M) >= R_0 so that: on E_{k,R(M)}, conditional on Y^{k,R(M)}, with
probability at least 3/4 the selected upper arm has
(a) a strict raise among its first R_0 edges, AND
(b) a total increase at least M along its first R(M) edges.
Proof. Fix an output in E_{k,R}. Let e_1,e_2,... be the successive
edges of the selected upper arm. For j<=R these belong to A_k(R) and
have h(e_j) <= j. Set
a_j = 1{ Y^{k,R}_{e_j} >= b_0 } (usable indicator),
A_d = sum_{j<=d} a_j,
N_d = sum_{j<=d} xi_{e_j},
mu_d = E[ N_d | Y^{k,R} ].
Under the conditioning, the a_j and the selected edges are fixed and
A_d >= d/2 for d>=n_0 (usable-prefix event). The decreasing sequence
f_j = ((j+2) log(j+2))^{-1} gives
mu_d >= gamma sum_{j<=d} a_j f_j,
with gamma = eta / (p_b + delta_0) > 0. (Each usable edge contributes
the probability in 7.4, at least eta f_j / (p_b + delta_0).)
Summation by parts on a_j f_j using A_j >= j/2 (for j>=n_0) gives
sum_{j<=d} a_j f_j
= A_d f_d + sum_{j<d} A_j (f_j - f_{j+1})
>= (1/2)[ d f_d + sum_{j=n_0}^{d-1} j (f_j - f_{j+1}) ]
= (1/2)[ n_0 f_{n_0} + sum_{j=n_0+1}^{d} f_j ].
The last expression tends to infinity (as a harmonic-like sum). So
there is a deterministic increasing lower bound m_d for mu_d, tending
to infinity.
Variance: the selected path is simple, so 7.4 gives
Var(N_d | Y^{k,R}) = sum_{j<=d} theta_{e_j}(1-theta_{e_j})
<= mu_d.
Choose R_0 >= n_0 with m_{R_0} >= 8. For every R >= R_0, Chebyshev:
P( N_{R_0} = 0 | Y^{k,R} ) <= 1/mu_{R_0} <= 1/8.
This choice of R_0 does NOT depend on R or M. For the requested gain,
put K_M = ceil(M/g), and pick R = R(M) >= R_0 so large that
m_R >= max{2K_M, 32}. Chebyshev again:
P( N_R < K_M | Y^{k,R} ) <= mu_R / (mu_R - K_M)^2 <= 4/mu_R <= 1/8.
At least K_M successful raises give total increase >= g K_M >= M on
the first R edges. Union bound over the two failure events: >= 3/4.
7.7 PROPOSITION (marks with an arbitrary toll). With R_0 fixed as
above, for every positive integer M the common coupling defines marks
J_M(k) in {0,1} at all horizontal sites, with equal marginal
probability at every site and
P( J_M(k) = 1 ) >= p/4.
A mark selects a bigeodesic p_k in T^{k,R(M)} through k, with upper
label rho_k in I avoiding all partition endpoints. Its arms lie in
Q^\pm(k,H_0). Its first R(M) upper-arm edges have total increase at
least M over the base environment, and one of its first R_0 upper-arm
edges has increase at least g. All changes occur in a deterministic
bounded neighbourhood of k whose radius may depend on M.
Proof. Take R=R(M) from 7.6. On E_{k,R}, use the already selected
path; mark when BOTH success requirements of 7.6 hold. Together with
the probability bound P(E_{k,R}) >= p/2, the lemma gives
P(J_M(k)=1) >= (p/2)(3/4) = 3p/8 >= p/4.
All asserted path properties are part of the selection or the marking
test. The region A_k(R) lies in a ball about k of radius at most
D_R = R + 1 + (R+H_0)/s,
and the prescribed gain portion lies in the ball of radius R.
Horizontal translations preserve the distribution of triples and
their heights. The selection rule and tests translate accordingly, so
marks have equal marginals (in fact the construction is stationary
under horizontal translations). Marks at different sites may be
dependent.
Subsequent FILTERS on marks may depend on the base environment or on
other marks and hence may bias the latent variables xi_e. We use the
UNCONDITIONAL bound P(J_M(k)=1) >= p/4 after those filters, without
reapplying 7.4.
7.8 UNIONS AND DISTINCT LABELS. Before selecting pairs of marks, fix
the common probability-one event needed for all comparisons. There
are countably many integer radii, sites, and pairs of sites. By 7.3,
each corresponding individual or union environment is absolutely
continuous with respect to mu. So almost surely the base and every
one of these environments satisfy: all structural inputs, 3.1, the
simultaneous conclusion of 6.3, and exclusion of bigeodesic labels
in D_I union (-D_I). Intersect with the countably many
probability-one events needed for selectors and conditional
estimates.
Choose the grid spacing l once and for all so that
l > R_0 + 1 + (R_0+H_0)/s,
and restrict marks to Lambda = {(jl,0) : j in Z}. This l is
independent of M.
LEMMA 7.9 (preservation in a union). Fix M, R=R(M), and suppose
distinct sites k,y in Lambda are marked. Then the selected paths
p_k,p_y are bigeodesics in the union metric T^* = T^{k,y,R}. Every
edge of p_k has the same weight there as in T^{k,R}; every edge of
p_y has the same weight in T^* as in T^{y,R}. Their labels are
preserved. Moreover, any raised edge among the first R_0 upper-arm
edges of p_y lies OUTSIDE A_k(R) and has its base weight in T^{k,R}.
Proof. For each edge of p_k of height at most R, the whole-path-width
bound s|w_1-k_1| <= |w_2|+H_0 puts both endpoints within the width
bound of A_k(R). Its individual weight is already Xhat_e, so passage
to the union leaves it unchanged. For an edge of height > R neither
region changes its base weight. Edgewise assertion. The same for p_y.
All other weights weakly increase in passing from either individual
environment to the union. Every segment of its selected bigeodesic
therefore still minimizes: its cost is unchanged, and no competitor
becomes cheaper. Only finitely many edges differ between an individual
environment and the union, so passage distances change by their total
finite increase; labels of the retained rays are preserved by 2.7.
Now suppose e is one of the first R_0 upper-arm edges of p_y. Both
endpoints have |w_1-y_1| <= R_0 and h(e) <= R_0. For any such endpoint,
|w_1-k_1| >= |y_1-k_1| - R_0 > 1 + (R_0+H_0)/s
>= 1 + (h(e)+H_0)/s,
where the grid spacing was used. Hence e notin A_k(R). If e is raised
in T^{y,R}, its increase in the union over T^{k,R} is at least g.
Moreover e cannot lie on p_k: every edge of p_k in this height slab
already belongs to A_k(R).
PROPOSITION 7.10 (no repeated marked label). Almost surely, for each
positive integer M, the selected upper labels at distinct marked sites
of Lambda are distinct.
Proof. On the common event of 7.8, suppose two distinct marked sites
k != y have rho_k = rho_y =: rho. By 7.9 both selected bigeodesics
persist with this label in T^* = T^{k,y,R}. By 6.3 their upper and
lower Busemann functions in this metric agree; denote by B^+, B^- the
common pair. For u on p_y, the bigeodesic inequality of 3.1 based at
k (on p_k) and then at u (on p_y) gives
B^+(k,u) + B^-(k,u) <= 0, B^+(u,k) + B^-(u,k) <= 0.
By additivity and antisymmetry, both are equalities, so
B^+(k,u) + B^-(k,u) = 0 for all u in p_y. (aa)
Take a raised edge e = {u,v} among the first R_0 upper-arm edges of
p_y, oriented towards the upper end (u -> v). Let t_e^* be its weight
in T^*. Calibration along the bigeodesic gives
B^+(u,v) = T^*(u,v) = t_e^*. (bb)
The last equality is because the single-edge segment v-u is itself
minimizing along p_y in T^*.
Let x_N^-, x_N^+ tend respectively to the lower and upper ends of p_k,
with k between them. Set
L_N^* = T^*(x_N^-, u) + t_e^* + T^*(v, x_N^+),
D_N^* = T^*(x_N^-, x_N^+).
L_N^* is the cost of an admissible finite walk; hence L_N^* >= D_N^*.
Because p_k is a bigeodesic,
D_N^* = T^*(x_N^-, k) + T^*(k, x_N^+). The signs in the Busemann
definition then give
T^*(x_N^-, u) - T^*(x_N^-, k) -> -B^-(k,u),
T^*(v, x_N^+) - T^*(k, x_N^+) -> -B^+(k, v).
It follows that
L_N^* - D_N^*
-> -B^-(k,u) - B^+(k,v) + t_e^*
= -[B^-(k,u)+B^+(k,u)] - B^+(u,v) + t_e^*
= 0,
by (aa) and (bb).
Choose minimizing finite approach paths in T^* from x_N^- to u and
from v to x_N^+, and join them by the specified traversal u->v of e.
Call this finite walk W_N. Its branches may intersect each other, the
selected bigeodesics, or e itself; its cost is L_N^* with every
traversal counted. By 7.9, the weight of e in T^{k,R} is its base
weight X_e. So its increase Delta = t_e^* - X_e >= g > 0.
On returning from T^* to T^{k,R}, every traversal weakly decreases in
cost, and the middle traversal of e decreases by Delta. Consequently
cost_{T^{k,R}}(W_N) <= L_N^* - Delta. (cc)
Any further traversal of e can only increase this saving.
On the other hand, the segment of p_k between x_N^- and x_N^+ has
cost D_N^* in both metrics (7.9). For sufficiently large finite N, we
have L_N^* - D_N^* < Delta. Then (cc) makes W_N strictly cheaper in
T^{k,R} than that segment, contradicting minimality. So the labels
are distinct.
This is a pathwise argument for every marked pair on the common
event, hence simultaneously for all positive integers M.
SECTION 8. THE FINAL COMPARISON AND PROOF OF THE MAIN THEOREM
Proof of Theorem 1. We argue by contradiction. Suppose bigeodesics
exist with positive probability.
(8.1) REDUCTION TO A CHART AND A DETERMINISTIC EVENT. Every bigeodesic
contains a lattice vertex. By countability of Z^2 and countability of
the chart family (3.3), and by exclusion of D-exceptional labels (5.2),
there is a chart I and a fixed vertex v such that, in this chart, a
bigeodesic through v with upper label in I has positive probability.
Translate v to 0 and use the chart's lattice coordinates. By 3.8,
almost surely the two arms of this bigeodesic lie in Q^\pm(0, H) for
some finite integer H. Taking the countable union over integer H gives
a deterministic H_0 >= 1 for which the event B(0) of 7.1 has
probability p > 0. Removing the countably many deterministic
partition endpoints D_I union (-D_I) does not change this
probability, by Corollary 2.5.
(8.2) THE MARKS AND THEIR BASE ENVIRONMENT. Apply Proposition 7.7
for each positive integer M, with the fixed spacing l from 7.8.
Two FILTERS on the marks.
First filter (base comparator confinement). For a horizontal site k,
let R_K(k) be the event that, in the UNCHANGED base environment,
every ray from k with label in I lies in Q^+(k,K) and every ray from k
with label in -I lies in Q^-(k,K). By 3.8,
mu( R_K(k)^c ) -> 0 as K -> infinity.
Choose deterministic K >= 1, INDEPENDENT OF M, so that this failure
probability is at most p/8. It is the same at every horizontal site
by translation invariance. Retain the mark when R_K(k) holds:
Jtil_M(k) = J_M(k) 1_{ R_K(k) }.
Unconditional subtraction (no independence needed):
q_M := P( Jtil_M(k)=1 ) >= P(J_M(k)=1) - mu(R_K(k)^c) >= p/4 - p/8
= p/8.
The filter is applied AFTER selecting the paths. It is a coanalytic
(universally measurable) event (2.9); not part of a projected relation.
Second filter (deterministic separation within bins). The near
radius R_0, the spacing l, and the comparator offset K are FIXED
independent of M. For each M we choose R(M) per 7.7, but at fixed M
the radius R(M) is a fixed finite number.
The selected arms have offset H_0, the base comparator rays have
offset K, the changed region has radius at most D_{R(M)} (7.7), and
the prescribed gain portion has radius at most R(M). By 5.3, there is
a finite deterministic horizontal separation S(M) that works for
EVERY bin of EVERY partition Pi_j: the cone bounds control the
comparators uniformly over bins, and the geometric bounds on
changed region and gain portion are bin-independent. Increase S(M)
if necessary to be nonnegative. This may grow with M, but it does
not affect the already fixed grid spacing l.
For the finite partition Pi_j, retain a site k with Jtil_M(k)=1 only
if there is NO other retained site y with Jtil_M(y)=1, |y-k| in
(0, S(M)], and selected label rho_y in the SAME bin as rho_k. Denote
this last indicator by J_{M,j}(k), with common marginal q_{M,j}. The
test concerns at most 2 floor(S(M)/l) other sites and is measurable
from the previously selected labels and marks.
At fixed j, two surviving marks in the same bin have separation
strictly greater than S(M), so 5.3 applies to consecutive surviving
marks of that bin, with gain b=M. Therefore 5.4 applies to the marks.
(8.3) THE LAST FILTER VANISHES AS j -> infinity for fixed M.
On the common event of 7.8, fix an outcome with Jtil_M(k)=1. By
7.10, every other marked site y != k - in particular every one of
the finitely many retained neighbours within distance S(M) - has
rho_y != rho_k. The nested partitions eventually put each such pair
(y with k) into DIFFERENT bins. The maximum of the finitely many
separating indices is finite, so k survives the last filter for every
subsequent partition. If Jtil_M(k)=0, all its final indicators are
zero. Hence
J_{M,j}(k) -> Jtil_M(k) almost surely as j -> infinity,
q_{M,j} -> q_M (bounded convergence).
No rate of random-label separation is required.
(8.4) BUYING THE CONTRADICTION. For a bin (alpha,beta)_I of Pi_j,
let q_{M,j}^{alpha,beta} be the probability that a given site survives
and its selected label lies in that bin. Applying 5.4 with b=M gives
q_{M,j}^{alpha,beta} <= (l/M) (r(beta)-r(alpha)).
Every selected label avoids the partition endpoints, so each
surviving mark belongs to EXACTLY one bin. Summing over the finitely
many bins of Pi_j and using their total width W_I:
q_{M,j} = sum_{bins} q_{M,j}^{alpha,beta}
<= (l/M) sum_{bins} (r(beta)-r(alpha))
= (l W_I) / M. (dd)
The label-budget bound uses only equal marginal marking probabilities
and the pathwise comparison. The dependencies introduced by shared
raises and by both filters are permitted.
Sending j -> infinity for fixed M combines q_M >= p/8, q_{M,j} -> q_M,
and (dd):
p/8 <= q_M <= (l W_I) / M.
But p, l, W_I were all fixed BEFORE M was chosen. Pick any integer
M > 8 l W_I / p. Then p/8 > l W_I / M, contradiction.
Hence the event "there exists a bigeodesic with positive probability"
is impossible, so almost surely there are no bigeodesics.
(8.5) COUNTABILITY BOOKKEEPING. The above argument used:
- the countable chart family (3.3),
- the deterministic countable set D_I union (-D_I) of excluded
partition endpoints (5.2),
- countably many integer radii R, sites k, and unions (7.8),
- countable intersections of the sets V_n,W_n in the coupling (4.5),
- countably many applications of the structural input (2.8).
All these are countable, and all arguments were pathwise on the
intersection of the resulting probability-one events. So the
contradiction genuinely excludes the existence event in the
unconditional law, and no exceptional direction is left unaddressed.
The perturbation argument of 7.2-7.6 uses only the nonatomic
marginal law, two separated sets of positive mass (near 0 and near
infinity in the support of G), and the structural conclusions under
the minimum-of-four second-moment assumption. All densities in the
change-of-law calculation are taken relative to G itself, including
when G is singular. A density with respect to Lebesgue measure, an
unbounded support, and a finite mean for a single weight are not
required.
APPENDIX. BOUNDARY COMPARISON WITHOUT BOUNDARY INTEGRABILITY
A.1 ROLE. The structural input of 2.4 cites Ahlberg-Hoffman
(arXiv:1609.02447v2), Assumption A1, Theorems 2.5-2.6 and 10.8-10.11,
Proposition 4.5. In their proof of Proposition 4.4 there is a
boundary-expectation step (their Lemma 4.6) that presumes INTEGRABLE
restricted passage times on a coordinate half-plane. Their Assumption
A1 (our minimum-of-four second moment) does not, by itself, provide
such integrability. For instance, a continuous law with tail
P(t_e > t) = (1+t)^{-1/2} ( log(e+t) )^{-3/8}, t >= 0,
satisfies A1 (min-of-four second moment finite) but the minimum of
TWO independent weights has INFINITE mean, and the cost of leaving a
diagonal-half-plane boundary vertex is at least such a minimum. So
integrability of the restricted Busemann increment cannot be
inferred from A1. The following replaces the problematic step, so
that 2.4 stays with its stated (moment-only) scope.
A.2 TERMINOLOGY. In the sense of Ahlberg-Hoffman Definition 2.3, a
random coalescing geodesic is a measurable choice, for the origin,
of a ray whose lattice translates coalesce almost surely. G(x) is
the translated ray from x; B_G is their common Busemann function on
all of Z^2. The full-plane asymptotic linearity of B_G is
Ahlberg-Hoffman Proposition 4.2, which precedes the boundary argument.
Let H be any of the eight axial or diagonal half-planes used there.
Let z be a primitive lattice vector parallel to its boundary, and
T_H the restricted passage metric on H. Assume G eventually enters
every translate of H.
Restricted minimizers: the finite-path uniqueness argument of 2.2
extends to the half-plane lattice, because the simple half-plane
paths form a subcollection of the full-plane simple paths and the
same nonatomic tie argument applies. Positivity of every edge weight
rules out loops in a minimizing walk. This gives unique finite
restricted minimizers, pathwise and simultaneously for all translates
of H.
A.3 LEMMA (finite boundary correction). For x in H intersect Z^2, the
limit
D_G(x) = lim_{j -> infinity} [ T_H(x,v_j) - T(x,v_j) ]
exists, is finite and nonnegative, and is independent of the target
ray v_j of G (any ray of G goes here). The boundary increments
D_G(k z), k in Z, are stationary under boundary translations, and
B_G^H(x,y) = B_G(x,y) + D_G(x) - D_G(y) (A3)
where B_G^H is the restricted half-plane Busemann limit.
Proof. Choose a vertex a on the common tail of G beyond the last exit
of any target ray from H. The segment from a to each later v_j
minimizes for both T_H and T. The sequences
T_H(x,v_j) - T(a,v_j), T(x,v_j) - T(a,v_j)
are decreasing (triangle inequality along the calibrated tail) and
bounded in absolute value by T_H(x,a) and T(x,a) respectively
(finiteness: the half-plane lattice is connected and all weights
finite). Their limits exist. Their difference is nonnegative (T_H >=
T) and defines D_G(x).
Any two rays of G share a tail, so choosing a different target ray
does not change either limit. A boundary translation by k z preserves
H and replaces the target ray with another of the same family; the
definition is covariance-stationary. No choice of auxiliary anchor a
appears in the limit. Measurability follows from the measurable ray
choice and countably many limiting distances. Subtracting the two
limits at x and y gives (A3).
A.4 LEMMA (a nonnegative stationary difference vanishes). Let
Delta(k,l), k,l in Z, be a finite, additive, stationary process with
Delta(k,k+1) >= 0 a.s. If Delta(0,n)/n -> 0 in probability, then
every increment Delta(k,k+1) is zero almost surely.
Proof. Set X_k = min{ Delta(k,k+1), 1 }, so X_k >= 0 and A_n :=
(1/n) sum_{k<n} X_k <= Delta(0,n)/n -> 0 in probability, A_n <= 1.
For any eps>0,
E[A_n] <= eps + P(A_n > eps) -> eps,
and stationarity gives E[A_n] = E[X_0] for all n, so X_0 = 0 a.s.
Stationarity, countability of Z, and additivity give Delta(k,l)=0
for every pair a.s. Neither integrability of Delta nor ergodicity is
used.
A.5 PROPOSITION (fixed-functional boundary comparison). Two random
coalescing geodesics with the SAME full-plane Busemann linear
functional rho agree almost surely (under the assumptions of
Theorem 1).
Proof. Let G, G' be two families with common functional rho. By
Ahlberg-Hoffman Proposition 4.3, their contact sector is contained
in the interior of one of the eight half-planes H; both G, G'
eventually enter every translate of H.
We need two ingredients about the restricted family, both reducing
to finitely many steps:
(i) Eventual containment, positive probability. By the geometric
part of Ahlberg-Hoffman Lemma 4.6 (which does not use the
expectation step), there is positive probability that the ray from
the origin is CONTAINED in H. A vertex minimizing the normal
coordinate starts a suffix contained in its half-plane; finiteness
plus coalescence identifies this suffix with the selected ray.
Countability of the vertices and covariance give positive
probability at a fixed vertex. Boundary translations of an iid
environment are ergodic (also for diagonal H), so there is such a
starting vertex in either direction along the boundary.
(ii) Stabilization. Choose two such roots on opposite sides of the
origin; their contained rays coalesce, and their portions up to
first common vertex form a finite simple connecting arc. If the
origin lies on this arc, its selected suffix is already contained
in H. Otherwise pick consecutive boundary contacts of the arc on
opposite sides of the origin. The intervening subarc plus the
boundary segment bounds a Jordan region adjacent to the origin.
Choose a vertex w on the common tail of the two bounding rays and
the target ray, outside this region and beyond the connecting arc.
Then every restricted minimizer from the origin to a target beyond
w must meet the separating subarc. From the meeting point, the
bounding-ray suffix to target lies in H and is a full-plane
minimizer; restricted uniqueness forces this suffix, so passage
through w. The prefix to w is the fixed restricted minimizer to w.
This proves stabilization and coalescence with the full-plane
family, including when bounding rays revisit the boundary. Doing
this at every boundary root gives G_H, G'_H; their common Busemann
functions on the boundary are exactly the restricted limits of A.3.
Now, if G, G' differ with positive probability, then because the
restricted family coalesces, the event that G, G' coalesce is
invariant under boundary translations. Under coalescence, finite
uniqueness forces any shared root's selected ray to be identical.
So boundary ergodicity makes DISTINCTNESS an almost-sure event.
The same invariance and ergodicity make their asymptotic planar
order deterministic (Ahlberg-Hoffman Section 4.5). Orient the
boundary vector z so that the finite crossing comparison in
Ahlberg-Hoffman equation (12) gives
Delta(k,l) := B_{G}^H(kz, lz) - B_{G'}^H(kz, lz) >= 0, k<l. (A5)
For clarity: the comparison chooses a crossing of G_H(kz) with
G'_H(lz), and common-tail vertices x of the primed rays and y of the
unprimed rays beyond the crossing. Swapping the two pieces at the
crossing gives walks pi_x from kz to x and pi_y from lz to y, and
Delta(k,l) = [ T_H(pi_y) - T_H(lz, y) ] + [ T_H(pi_x) - T_H(kz, x) ].
Both summands are nonnegative finite excesses. No expectation is used.
Put Z(x) = D_G(x) - D_{G'}(x). By (A3),
Delta(0,n) = B_G(0, nz) - B_{G'}(0, nz) + Z(0) - Z(nz).
The first term divided by n tends to zero almost surely (full-plane
linearity and factorization of the two functionals through rho). For
each eps>0, finiteness of Z and stationarity give
P(|Z(nz)|>n eps) = P(|Z(0)|>n eps) -> 0,
so Delta(0,n)/n -> 0 in probability. Delta is additive and stationary
under boundary shifts, so A.4 and (A5) imply Delta(k,l) = 0 for every
pair a.s.
The final uniqueness argument is finite. Distinct same-root restricted
rays have a finite common initial portion. Choose a deterministic bound
m on its length that holds with positive probability; boundary
ergodicity makes two starting roots farther apart than 2m appear.
In the crossing comparison, at least one swapped walk differs from its
corresponding minimizing path (if both were geodesics, their crossing
vertex would lie in the common initial portion from each root; two
roots within 2m of each other would follow, contradiction). Both excess
terms are nonnegative and sum to zero, so a DISTINCT swapped walk is
also minimizing: contradicting uniqueness. So the restricted families
agree, hence G = G'.
A.6 CONCLUSION OF THE APPENDIX. A.5 supplies the conclusion of
Ahlberg-Hoffman Proposition 4.4 without the boundary-expectation step
of their Lemma 4.6. The other later use of Lemma 4.6 in that paper
(proof of its Lemma 9.6) uses only the geometric construction and
coalescence, both of which we retain. Hence the structural input of
2.4 keeps its stated minimum-moment scope; no integrability of a
diagonal boundary Busemann function has been inserted.
============================================================
End of the writeup. The single probability-one event on which the
whole proof runs (Theorem 1's a.s. assertion) is the intersection,
over all countable deterministic choices made in sections 2-7, of
the corresponding probability-one events. On that event, for every
bigeodesic and every chart the conclusion holds simultaneously: no
such bigeodesic exists.
============================================================