Critical bond and site percolation on the cubic lattice Z^3
===========================================================

A complete proof that no infinite open cluster exists at criticality,
for both bond and site percolation on the three-dimensional integer
lattice.

HISTORY. Broadbent and Hammersley (1957) introduced percolation to
model a fluid moving through a random medium. In two dimensions,
Harris (1960) and Kesten (1980) settled the bond case on the square
lattice, and Russo (1981) the site case. In high dimensions d >= 11
for bond (d > 10) the lace expansion of Hara and Slade (1990),
sharpened by Fitzner-van der Hofstad (2017), proves the analogous
statement; Heydenreich-Matzke (2020) did the site analogue.
Grimmett-Marstrand (1990) proved slab thresholds tend to the
full-lattice threshold, and Duminil-Copin, Sidoravicius, Tassion
(2016) proved nonpercolation on slabs. The theorem we prove below
handles the cubic lattice in all dimensions d >= 3 directly,
including right at p_c, without any high-dimensional hypothesis.

~ . ~

ABSTRACT (informal). Picture Z^3. In BOND percolation every EDGE is
independently "open" with probability p; paths follow open edges. In
SITE percolation every VERTEX is independently "open" with probability
p; paths follow open vertices. An open path is a chain of adjacent
open objects, a CLUSTER is a maximal connected union of open objects,
and an INFINITE CLUSTER is an open cluster of infinitely many objects.

The critical probability p_c is the sharp threshold: for p < p_c,
every cluster is almost surely finite; for p > p_c, an infinite
cluster exists with positive probability. The question is whether an
infinite cluster survives at p = p_c.

Theorem (main). For bond percolation on Z^3, at p = p_c the prob-
ability that any infinite open cluster exists is zero. The same
holds for site percolation at its own critical probability.

The proof has five parts:
(1) A finite comparison inequality for independent hyperedges.
(2) A planar boundary count that proves p_c < 1 and appears again
    in the final sum.
(3) An extension estimate that moves a connection through a fresh
    region, using many well-separated "seed boxes".
(4) A fixed relay geometry of thirteen rectangle-to-rectangle steps,
    transferring a connection between neighboring inner boxes.
(5) An adaptive exploration using every coarse cube in Z^2, which
    produces an infinite cluster at some parameter q < p_c, a
    contradiction.

Do not panic if any part looks technical on first reading: each
section states its goal informally before doing the details.

NOTATION. For x = (x_1,x_2,x_3) in Z^3 and r >= 0, put
  Lambda_r(x) = { x + y : y in {-r,-r+1,...,r}^3 }.
Write Lambda_r = Lambda_r(0) with 0 = (0,0,0). For a set T and vertex
x, "x <-> T" means some open path joins x to a vertex of T.
"o <-> v" is shorthand for "o <-> {v}". If S is a set, x <-> S
means x <-> s for some s in S. A BIT is either an edge (bond model)
or a vertex (site model) depending on which model we are using.
A bit is "internal to a vertex set W" if the site lies in W (site
model), or the edge has both endpoints in W (bond model). An event
is INCREASING if adding open bits can only help it become true; it
is DECREASING if adding open bits can only hurt it. Classical
examples: {u <-> T}, {u is open}, {some connection inside W}.

Section 1. The finite comparison
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The main finite tool: reaching a set A of possible relays, when
every relay in A nearly always reaches a target T, gives only small
chance of reaching A but missing T. This is what lets a proof
"walk" a connection through intermediate boxes. We need it for
independent hyperedges with nonuniform probabilities because along
the way some bits are already fixed (probability 0 or 1).

A FINITE HYPERGRAPH has a finite node set and a finite collection
of nonempty subsets called HYPEREDGES. Each hyperedge is
independently open with its own probability in [0,1]; an open
hyperedge joins all its nodes into one cluster. Writing C(x) for the
cluster of x (always containing x) and C(S) = union_{s in S} C(s),
random percolation is the partition of nodes induced by the open
hyperedges.

Proposition 1.1 (joint connection comparison). In independent
percolation on a finite hypergraph, with arbitrary hyperedge
probabilities in [0,1], fix any node o and nonempty node sets A, T.
Then
  P( o <-> A and o <-> T ) >= P( o <-> A ) * min_{a in A} P( a <-> T ).

Corollary 1.2 (failure comparison). If every a in A satisfies
P( a <-> T ) >= 1 - b, then
  P( o <-> A and NOT o <-> T ) <= b.
This also holds after any deterministic set of bits has been fixed,
provided the remaining bits keep their independent product law.

Proof of Corollary 1.2 from Prop. 1.1 for hypergraphs.
P(o<->A, o<->T) >= P(o<->A)*(1-b). Subtract from P(o<->A):
P(o<->A, not o<->T) = P(o<->A) - P(o<->A, o<->T) <= P(o<->A)*b <= b. []

For BOND percolation, each edge is a hyperedge of its two endpoints,
so Proposition 1.1 applies directly.

For SITE percolation, use the incidence trick. Create a node x' for
each vertex x, and a connector node (x,z) for each unordered adjacent
pair {x,z}. For each vertex x, form the hyperedge
  { x' } union { (x,z) : z adjacent to x },
with the same probability that x is open. Then x' <-> z' in the
hypergraph if and only if x <-> z in the site model (do a proof by
induction on path length). The only difference: x' is always self-
connected in the hypergraph (its own hyperedge has it), whereas in
the site model x is self-connected only if x is open. So on the
site event { o open, o<->A, not o<->T }, the same event holds in
the hypergraph. Applying Proposition 1.1 and subtraction bounds the
hypergraph failure event by b, hence the site failure event by b. []

Now we prove the proposition. The heart is a positivity lemma on
"cluster columns".

Setup. For a hypergraph G and a node set w, define G \ w as the
hypergraph obtained by deleting the nodes of w and every hyperedge
that meets w. KEY FACT: on an exact-cluster event { C(S) = w } of
positive probability, the surviving hyperedges of G \ w keep their
original independent laws. Reason: the event only asserts "the
cluster of S inside w is exactly w" (no hyperedge from w reaches
outside) and "every hyperedge crossing w to its complement is
closed". It says nothing about hyperedges disjoint from w. So
conditioning on it does not change the laws of those. The same
observation applies after an earlier deletion.

Fix an ordered list x_1, ..., x_n of distinct nodes (not necessarily
every node). Define
  S_k = { x_1, ..., x_{k-1} },
  E_k = { C(x_k) meets S_k is empty },
  d_k = P( E_k ) > 0,
  mu_k = conditional law of C(x_k) given E_k.
E_k has positive probability because we can close all hyperedges
through x_k, isolating it from S_k. For a function F on clusters,
define
  h_k(i)    = E_{mu_k}[ 1{ x_i in U } ],
  v_k^F(i)  = E_{mu_k}[ 1{ x_i in U } F(U) ].
Then H := (h_1 | h_2 | ... | h_n) is unit lower triangular: the
k-th column has h_k(k) = 1 and h_k(i) = 0 for i < k. The reason:
E_k says x_k is not connected to any earlier listed node.

Lemma 1.3 (cluster columns). If F is nonnegative and increasing
under inclusion, then
  v_k^F - mu_k(F) h_k  belongs to the cone of { h_j : k < j <= n },
i.e. it is a nonnegative linear combination of the later columns.
Equivalently, H^{-1} v_k^F has nonnegative coordinates.

Proof of Lemma 1.3. Descending induction on k.

Base case k = n. Only x_n = s remains, so C(x_n) = { x_n } union
"unreachable" on E_n. Hence v_n^F = mu_n(F) h_n directly.

Inductive step. Assume the lemma for every j > k. Write s = x_k,
S = S_k, W = C(S). For a set w with S subset w and s not in w, put
  c(w) = E[ F( C^{G \ w}(s) ) ],
where the expectation uses the original product law on the surviving
hyperedges. Enlarging w deletes more, so c(w) is NONINCREASING in w.

First-listed-node decomposition. Fix a row i. Look at row i of the
moments. For j > k let L_{ij} be the event "the first listed node of
C(x_i) is x_j". Conditioning on an exact value W = w with s not in w,
the mean of F(C(s)) is c(w). If x_i avoids w, its cluster contains
the listed node x_i and avoids all earlier listed nodes (those lie
in w); hence its first listed node is s iff x_i <-> s, and
otherwise it is exactly one x_j with j > k. On L_{ij}, conditioning
further on C(x_j) = U, the set U avoids s and the extra condition
"first listed node is x_j" adds only avoidance and membership
information on U; so exact-cluster conditioning leaves the mean of
F(C(s)) at c(w U U). Partitioning the total mean by the mutually
exclusive possibilities "first listed node is s" or "is some x_j"
and subtracting c(w) times the total probability 1 gives
  E[ 1{ x_i <-> s } F(C(s)) | W = w ]
    = c(w) P( x_i <-> s | W = w )
      + sum_{j>k} E[ 1{ L_{ij} } ( c(w) - c(w U C(x_j)) ) | W = w ].
The term c(w U C(x_j)) is only used on L_{ij}; when x_i is in w, all
L_{ij} are empty under the conditioning and both sides vanish.

Now average over mu_k. Given C(s) = U avoiding S, the conditional
law of W = C(S) is the law of W_U := C^{G \ U}(S). So the first term
on the right averages to v_k^{PF}(i) where
  (PF)(U) := E[ c(W_U) ].
For a residual term, the exact event identity is
  E_k cap L_{ij}  =  E_k cap E_j cap { x_i <-> x_j }.
Reason: a cluster avoiding the earlier listed nodes also avoids
their entire clusters; on E_j with C(x_j) = U the conditional law
of W becomes W_U, and the leftover restriction E_k is "s not in W_U".
Dividing by d_k and summing over j > k gives the column identity
  v_k^F = v_k^{PF} + sum_{j>k} (d_j / d_k) v_j^{R_F},
where
  R_F(U) := E[ 1{ s not in W_U } ( c(W_U) - c(W_U U U) ) ].

Properties of R_F. Sample all hyperedge bits once. For deterministic
U, the event { W_U = w } tests only bits of hyperedges meeting w and
disjoint from U. Every full-graph hyperedge avoiding w therefore
keeps its original independent law after conditioning. When s is not
in w, the two clusters
  C^{G \ W_U}(s)   and   C^{G \ (W_U U U)}(s)
therefore have exactly the marginal laws defining c(W_U) and
c(W_U U U). The first contains the second, so R_F >= 0.

To see R_F is increasing, take U subset U'. Then W_{U'} subset W_U.
On { s not in W_U }, replacing U by U' first makes the first cluster
larger (we delete the smaller set W_{U'}), and second, the second
cluster C^{G \ (W_U U U)}(s) = C^{G \ U}(s) equals the corresponding
object for U' (because in G \ U the s-cluster avoids W_U entirely,
so deleting W_U removes nothing). Hence both clusters move the right
direction and the integrand is nondecreasing in U. R_F is thus
nonnegative and increasing.

Uniform convergence. The map P is a Markov transition: from U, first
sample W_U, then sample C^{G \ W_U}(s) independently. Under the
joint law of (C(s), W) given E_k, these are the successive
conditional laws of W given C(s), and of C(s) given W. So mu_k is
a stationary measure for P. Also, every transition assigns
probability at least
  a := prod_{e: s in e}(1 - p_e) > 0
to the singleton {s}, because closing all hyperedges through s
isolates s. The standard "common-mass" decomposition then gives for
any real g on the state space:
  max Pg - min Pg <= (1 - a) ( max g - min g ).
Iterating,
  sup_U | (P^t F)(U) - mu_k(F) | <= (1-a)^t (max F - min F) -> 0.
So P^t F converges uniformly to the constant mu_k(F).

Finishing the induction. Each v_j^{R_F} for j > k is, by the
induction hypothesis, a nonnegative combination of h_j, ..., h_n.
So v_k^F - v_k^{PF} sits in the cone spanned by h_j for j > k. Since
P and its iterates preserve "nonnegative increasing", the same
holds with F replaced by P^t F. The cone is closed (its generators
belong to the basis of columns of H), and P^t F -> mu_k(F)
uniformly, so v_k^F - mu_k(F) h_k is in the cone. Adding mu_k(F) h_k
expresses v_k^F as a nonnegative combination of columns. []

Proof of Proposition 1.1. First suppose every hyperedge probability
is strictly less than 1 (so "closing" events have positive
probability). Fix a list as in Lemma 1.3. For
  F(U) = 1{ some x_j in U with j > k },
closing all hyperedges through x_k isolates it, so mu_k(F) < 1. A
direct computation gives
  v_k^F - mu_k(F) h_k = (1 - mu_k(F)) ( h_k - e_k ),
where e_k is the k-th basis vector. Lemma 1.3 gives nonnegative
Gamma_{jk} with
  h_k = e_k + sum_{j>k} Gamma_{jk} h_j.
Set Gamma = (Gamma_{jk}) with zeros on and above the diagonal. In
column form, H = I + H Gamma; H is unit lower triangular, hence
invertible, so H^{-1} = I - Gamma. Also
  H d = 1  and  (I - Gamma) 1 = d.
Here (H d)_i = sum_k d_k h_k(i) = sum_k P(first listed node of C(x_i)
= x_k) = 1, and the second follows from the first and H^{-1} = I - Gamma.

If o is in A, Proposition 1.1 is immediate. Otherwise, take the
list to be exactly the nodes of A in any order, followed by x_n = o.
Set
  F(U) = 1{ U meets A and U meets T },
  y_i  = E[ F(C(x_i)) ].
Then y_n = P(o<->A, o<->T), and for i < n we have y_i = P(x_i<->T)
because x_i in A automatically. Partition by the first listed node:
  y = sum_k d_k v_k^F.
Each restriction to D_k is nonnegative and increasing, so by Lemma
1.3, (I - Gamma) y has nonnegative coordinates. Row n reads
  y_n >= sum_{i<n} Gamma_{ni} y_i.
The weights are nonnegative and sum to
  sum_{i<n} Gamma_{ni} = 1 - d_n = P(o <-> A),
because d_n = P(o is not connected to any A-node) = P(not o<->A).
So
  y_n >= P(o<->A) * min_{i<n} P(x_i <-> T)
       = P(o<->A) * min_{a in A} P(a <-> T),
which is Proposition 1.1.

Finally, allow hyperedge probabilities equal to 1. Every finite-
event probability is a polynomial in the hyperedge parameters, so
the strict inequality extends to the closed cube in parameter space
by continuity. []

That completes the finite comparison. Everything else in the paper
uses the failure bound of Corollary 1.2, with A a chosen set of
"relay points".

Section 2. Planar boundary count and p_c < 1
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Before proving anything about criticality we need two facts: p_c < 1
(so percolation at p close to 1 is certain to produce an infinite
cluster), and an elementary count of "boundary cycles" that will
appear again in the exploration. Both use a planar slice of Z^3.

Dual square lattice. Consider Z^2 with its usual squares. Its dual
squares live at Z^2 + (1/2,1/2). Each dual edge crosses exactly one
primal edge; this gives a bijection primal edges <-> dual edges. For
a finite set X of primal vertices, its DUAL BOUNDARY is the set of
dual edges crossing primal edges with exactly one endpoint in X.

Lemma 2.1 (boundary cycles). There are deterministic families C_n
of simple dual cycles of length n, with |C_n| <= 2n 3^n, such that
the dual boundary of every finite X subset Z^2 containing 0 contains
a cycle from C_1 union C_2 union ... . Moreover, for each such cycle
we can fix at least n/7 crossed primal edges with pairwise disjoint
endpoints.

Proof. At a dual vertex the boundary degree counts changes of
membership around a primal square, and is therefore even. The finite
dual boundary therefore decomposes into edge-disjoint simple cycles.

Consider the positive horizontal ray from 0 along the x-axis. The
total number of boundary crossings of this ray is odd: it starts
inside X and ends outside. So at least one cycle in the decomposition
crosses the positive ray an odd number of times. But any closed dual
cycle crosses the whole horizontal line an even number of times (by
counting changes of sign of the "height"). So the same cycle also
crosses the negative ray. If the cycle has length n, a positive
crossing must have horizontal coordinate t + 1/2 with 0 <= t < n:
the horizontal distance to a negative crossing is less than n. Define
C_n to be the set of all simple cycles of length n having an anchored
crossing of the positive ray at t + 1/2 with t in [0,n) and an odd
number of positive-ray crossings. Overcount: choose the anchored
edge (n choices), an orientation (2 choices), and a non-backtracking
continuation (at most 3 choices at each of the remaining n steps).
This gives at most 2n 3^n cycles.

Finally, greedily pick crossed primal edges in a fixed order,
each time discarding all edges incident to either endpoint of the
picked edge. Each pick discards at most seven edge-endpoints (itself
plus up to six neighbors; the primal graph has degree four, so each
endpoint has three other incident edges: at most 6 total). The
selected edges have pairwise disjoint endpoints and number at least
n/7. []

Lemma 2.2 (p_c < 1 for both models). For bond percolation on Z^3
and its planar subgraph Z^2, p_c^bond < 1. For site percolation the
same bound holds for p_c^site.

Proof. It suffices to percolate on a coordinate copy of Z^2.

Bond case. If the origin cluster of a Z^2 slice is finite, every
primal edge crossed by its dual boundary is closed. Lemma 2.1 and
a union bound over cycles give the bound
  P_p( the origin has a finite Z^2-cluster )
    <= sum_{n>=1} 2n 3^n (1-p)^n.
Since 3(1-p) < 1 for p close enough to 1, the series converges to
a number strictly less than 1. So at some p < 1 the origin has
positive probability of having an infinite Z^2-cluster; percolating
on a subset of Z^3 gives an infinite Z^3-cluster with positive
probability there, hence p_c^bond <= that p < 1.

Site case. Separate the event that 0 is closed. On { 0 is open },
if the (Z^2) cluster of 0 is finite, each edge crossed by the
boundary cycle of the cluster has a closed endpoint (site model:
a path from inside to outside must use a closed endpoint). For
a fixed cycle, pick the crossed primal edges with disjoint endpoints
(k >= n/7 of them by Lemma 2.1). The union over choices of one
closed endpoint of each edge has probability at most
[2(1-p)]^k. Hence
  P_p( no infinite Z^2-cluster through 0 )
    <= (1-p) + sum_{n>=1} 2n 3^n [2(1-p)]^{n/7}.
For p close enough to 1, 2(1-p) < 1, and both displayed series
converge to a number strictly less than 1. So p_c^site < 1. []

Now suppose, for contradiction, that at p = p_c an infinite cluster
exists with positive probability. Applying Lemma 2.2 gives
0 < p_c < 1, so p in (0,1) throughout. We need one more fact: at p_c
the existence of an infinite cluster has probability 0 or 1.

Lemma 2.3 (0-1 law for existence). Let A be the event that some
infinite open cluster exists. Then P_p(A) is 0 or 1.

Proof. The event A is unchanged by adding or removing finitely many
edges (in the bond model) or vertices (site model), because deleting
finitely many bits can never turn infinitely many clusters into
infinitely many clusters of the same infinite set -- more precisely
deleting one edge splits one cluster into at most two, so deleting
finitely many bits leaves only finitely many components at least one
of which is infinite. Also A is measurable: it is determined by
countably many finite-path tests. So A is independent of every
finite-bit event. Finite-bit events approximate all events in
probability, so A is independent of itself: P(A) = P(A)^2, hence
P(A) in {0,1}. []

Consequently, under the contradiction assumption P_p(A) = 1. So for
any box:
  P_p( Lambda_m meets an infinite cluster ) -> 1 as m -> infinity.
We will use this to choose the seed size m shortly.

Harris positive association (used right below and in the extension
estimate). Let X_1,...,X_N be independent bits. Let f, g be
INCREASING functions of the bits. Then E[f g] >= E[f] E[g].
Likewise for decreasing functions, and for any finite family of
events.

Proof (induction on N, conditioning on the last bit). Write
f(x_1,...,x_N) = f_0 + x_N (f_1 - f_0) and similarly for g, where
f_0, f_1, g_0, g_1 depend only on (x_1,...,x_{N-1}) and f_1 >= f_0,
g_1 >= g_0 (increasing). Expand E[f g]:
  E[f g] = E[f_0 g_0] + E[ x_N ( f_0 g_1 + f_1 g_0 - 2 f_0 g_0 ) ]
         + E[ x_N^2 ( f_1 - f_0 )( g_1 - g_0 ) ].
The last term is >= 0. The middle term is E[x_N] E[ ... ] by
independence, which equals p E[ ( f_1 - f_0 ) g_0 + f_0 ( g_1 - g_0 ) ].
By induction, E[f_0 g_0] >= E[f_0] E[g_0], so
  E[f g] >= E[f_0]E[g_0] + p E[g_0]E[f_1 - f_0] + p E[f_0]E[g_1 - g_0]
          = E[ f_0 + p(f_1 - f_0) ] E[ g_0 + p(g_1 - g_0) ]
          = E[f] E[g].  []

Section 3. Quarter-faces and the choice of scales
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The proof of the theorem needs one finite set of numbers, chosen once
and for all, together with a parameter q < p_c at which every relevant
quarter-face connection succeeds with high probability.

Quarter-faces. For u in Z^3 and b >= 0, Lambda_b(u) is the lattice
cube of radius b at u. A QUARTER-FACE of Lambda_b(u) is obtained as
follows: pick a coordinate i in {1,2,3}, a sign sigma in {-1,+1} for
the "normal", and a sign eps_j in {-1,+1} for each of the two
transverse coordinates j != i. Then
  F_{i,sigma}^{eps}(u,b)
    = { u + x : x_i = sigma b, 0 <= eps_j x_j <= b for j != i }.
There are 3 (normal axes) * 2 (normal signs) * 4 (transverse sign
pairs) = 24 quarter-faces. They overlap on their boundaries; the
overlaps do not matter.

Lemma 3.1 (choice of scales). Under the contradiction assumption
(an infinite cluster at p_c), there are numbers
  f, delta, eta, tau, gamma in (0,1),
  positive integers m, K, R, r,
  and q in (p/2, p)
with the following properties. First, f < 1/2 and
  (S) sum_{n>=1} 2n 3^n (2f)^{n/7} < 1.
The tolerances satisfy
  (E) delta + 52 eta / delta < f,
      tau < eta/4,
      gamma < delta,
      2 gamma / tau < eta/4.
Let M be the number of internal bits of Lambda_m, and set
  rho_0 = (p/2)^{M+1},
  L     = K (8m+5)^3,
  alpha = (1-p)^L.
Then
  (G) 4 / (K rho_0)        < eta/4,
      R                    > m,
      1 / (alpha (R-m))    < eta/4,
      r                    > 100 (R+1).
And, for every l in { 2r, 2r+1, 10r }, every u in Z^3, and every
quarter-face F of Lambda_l(u),
  (QF) P_q( Lambda_m(u) <-> F inside Lambda_l(u) ) > 1 - gamma.
Here "inside Lambda_l(u)" means the open path stays in the cube.

Proof. Choose f small enough first, so that (S) holds. Then choose
delta < f. Then choose eta small enough for "delta + 52 eta/delta < f".
Then choose tau < eta/4 small enough. Then choose gamma < min(delta,
eta tau / 8) so that "2 gamma/tau < eta/4".

To choose m: by the 0-1 law applied under the contradiction assumption
and Lemma 2.2, for parameter p the seed box Lambda_m meets an infinite
cluster with probability -> 1 as m -> infinity. Choose m large enough
that
  P_p( Lambda_m meets no infinite cluster ) < (gamma/2)^{24}.

For every integer l > m, an infinite cluster meeting Lambda_m gives
an open path from Lambda_m to the vertex boundary of Lambda_l inside
that cube. So
  P_p( Lambda_m misses the whole vertex boundary of Lambda_l
       inside Lambda_l ) < (gamma/2)^{24}.
By signed coordinate symmetry, all 24 quarter-face-miss events of
Lambda_l have the same probability, say a_l. These are DECREASING
events of a finite product of independent bits; Harris's inequality
(iterated) then gives
  a_l^{24} <= P_p( Lambda_m misses every quarter-face inside Lambda_l )
           < (gamma/2)^{24}.
Hence a_l < gamma/2 for every l > m.

Now M and rho_0 are fixed and positive. Choose K large enough for
"4/(K rho_0) < eta/4", then define L = K(8m+5)^3 and alpha = (1-p)^L.
Choose R > max(m, 1 + 4/(alpha eta)) so that "1/(alpha(R-m)) < eta/4".
Then choose r > 100(R+1) so that r is much larger than R. All these
choices precede the choice of q.

At each of the three radii 2r, 2r+1, 10r, the quarter-face connection
event "Lambda_m(u) <-> F inside Lambda_l(u)" involves finitely many
bits, so its probability is a polynomial in the percolation parameter.
By the choice of m we have this probability > 1 - gamma/2 at parameter
p. Because there are only 24 quarter-faces and 3 radii, and each
event's probability is a continuous function of the parameter, one
common value q in (p/2, p) makes all of them > 1 - gamma
simultaneously. []

Fix these choices once and for all. For the rest of the paper,
"q" is the parameter from Lemma 3.1, and "unrevealed bits" always
have probability q on every side. Bits already fixed have probability
0 or 1, which the finite comparison covers.

Section 4. The extension estimate
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Aim. Take a "current box" B, a "target" T that has quarter-faces
available from every point of B^{(R)}, and a fresh region D that
contains B^{(R)}. Show that a connection from outside D to B usually
continues to T. This gives a way to "walk" a connection from one box
to the next using many well-separated seed boxes, kept
probabilistically independent by disjointness.

Setup. Let D be a rectangular block of Z^3 (a product of three
integer intervals), and let B be another rectangle inside D. Put
B^{(j)} for the expansion of B by j in every coordinate direction.
"Internal to D" means: site inside D (site model), or edge with both
endpoints in D (bond model). The bits internal to D all have
parameter q; every other bit has an arbitrary probability in [0,1],
including possibly 0 or 1 (already fixed).

Lemma 4.1 (extension estimate). Let G be a finite subgraph of Z^3
containing D and every internal edge of D. Let o in V(G) and let T
subset V(G). Suppose a rectangle B satisfies
  B^{(R)} subset D,       o not in B^{(R)},
and suppose that for every u in B^{(R)} there exists a radius
l in {2r, 2r+1, 10r} such that Lambda_l(u) subset D and SOME
quarter-face of Lambda_l(u) is contained in T. Then, for connections
in G,
  P( o <-> B and NOT o <-> T ) < eta.

Proof. We split into four steps.

Step 1 (choose a layer). For m <= j <= R-1, expose only bits
internal to the graph OUTSIDE B^{(j)} (i.e., edges not meeting B^{(j)},
or sites not in B^{(j)}). Let Y_j be the exterior neighbors of
B^{(j)} (vertices outside B^{(j)} that border B^{(j)}) that are
reachable from o by an open path in this outside graph. Set
N_j = |Y_j|. Any path from o to B must enter B^{(j)} for the first
time, entering through some exterior neighbor of B^{(j)}; and since
o is outside B^{(R)} and B subset B^{(j)}, that first entry exists
whenever o <-> B. Hence on { o <-> B } we have N_j >= 1.

Consider the event "1 <= N_j < L AND all edges { y, z_y } with
y in Y_j (and z_y the unique neighbor of y inside B^{(j)}) are
closed" (in the bond model; in the site model replace "edges closed"
by "sites z_y closed"). Given the outside bits, these are unexposed
parameter-q bits; the conditional probability of this event is at
least (1-q)^{N_j} >= (1-p)^L = alpha because N_j < L and q < p.
Call this event the "closure at level j". If it occurs, o cannot
enter B^{(j)} at all, hence cannot reach B.

The closure events are PAIRWISE DISJOINT over j. If closure at
level j happens with 1 <= N_j < L, then o cannot enter B^{(j)}. For
i < j, every exterior neighbor of B^{(i)} lies in B^{(i+1)} subset
B^{(j)}, so those exterior neighbors are also unreachable, giving
N_i = 0, contradicting the requirement 1 <= N_i < L in the closure
event at level i. So closures at different levels cannot both occur.

Consequently
  sum_{j=m}^{R-1} P( 1 <= N_j < L ) <= alpha^{-1},
because the closure at level j has conditional probability >= alpha
given 1 <= N_j < L, and the closures are disjoint.

Since o <-> B implies N_j >= 1, we have
  sum_{j=m}^{R-1} P( o <-> B, N_j < L ) <= alpha^{-1}.
Fix a deterministic layer j in {m, ..., R-1} such that
  P( o <-> B, N_j < L ) <= 1 / ( alpha (R-m) ).    (*)

Step 2 (fixture: internal vs external bits). Set C := B^{(j)}. Let
xi be the configuration of bits internal to C, and zeta be the
configuration of bits internal to the outside graph. Then Y_j is a
function of zeta. For the BOND model the remaining bits are the
crossing bonds { y, z_y } for exterior neighbors y; XI and ZETA and
the crossing bonds are independent, and all bits of xi and crossing
bits have parameter q (they lie inside B^{(j+1)} subset D, whose
internal bits all have parameter q). For the SITE model xi and zeta
already partition the bits.

Step 3 (relay quality). For each exterior neighbor y of C, choose
a center v_y so that
  U_y := Lambda_m(v_y) subset C,   z_y in U_y,   || v_y - y ||_inf <= m+1.
Do this by clamping each coordinate of z_y to the shrunk interval
[ -j + m, j - m ] in that coordinate direction of C. The shrunk
interval is nonempty because j >= m.

Let O_y be the event that every internal bit of U_y is open. Then O_y
is determined by xi and has probability q^M. Define
  g_y    = P( v_y <-> T | xi ),   the target probability given xi,
  A_xi   = { v_y : y an exterior neighbor of C, g_y > 1 - tau }.
The set A_xi is determined by xi alone, and depends on the bits of
the crossing bonds only through the parameter q (they are averaged
out).

For fixed y, apply the quarter-face hypothesis at u = v_y: there is
l in {2r, 2r+1, 10r} with Lambda_l(v_y) subset D and a quarter-face
F_y of Lambda_l(v_y) contained in T. By (QF) the increasing event
Q_y := { Lambda_m(v_y) <-> F_y inside Lambda_l(v_y) } has probability
> 1 - gamma. On O_y cap Q_y the center v_y connects to T. Positive
association (Harris, applied to O_y and Q_y, both increasing) gives
  P( O_y and NOT v_y <-> T ) <= q^M ( 1 - P(Q_y) ) <= q^M gamma.
Since O_y is determined by xi,
  tau * P( O_y, g_y <= 1 - tau )
    <= E[ 1_{O_y} ( 1 - g_y ) ]
    =  P( O_y, NOT v_y <-> T )
    <= q^M gamma.    (**)

Step 4 (reach A_xi; the barrier). Condition on zeta. Whenever
N_j >= L, greedily choose K exterior neighbors y_1,...,y_K from Y_j
at pairwise supx distance > 4m+2. The greedy selection works because
each choice excludes at most (8m+5)^3 candidates, while |Y_j| >= L =
K(8m+5)^3. Their centers v_y have pairwise supx distance > 2m, so the
seed boxes U_{y_k} are vertex-disjoint.

Call an entrance y SUCCESSFUL if O_y holds and, in the bond model,
also the crossing bond { y, z_y } is open; in the site model y is
already open because y in Y_j is reachable (so y and its incoming
edge are open), and the open seed U_y contains z_y. In either model,
"successful" implies an open path from o all the way to v_y.

Given zeta, successes are independent Bernoulli trials with common
parameter
  c = q^{M+1}   for bonds,     c = q^M     for sites,
and c >= rho_0 (by the definition of rho_0 and q > p/2). Let S count
successes. Chebyshev's inequality:
  P( S < Kc/2 | zeta ) <= 4 / (Kc) <= 4 / (K rho_0).   (***)

Let Z count successful entrances whose center fails the defining
condition for A_xi: g_y <= 1 - tau. By (**) and summing over the K
choices,
  P( O_y, g_y <= 1 - tau | zeta ) <= q^M gamma / tau,
so E[Z | zeta] <= Kc gamma / tau; Markov gives
  P( Z >= Kc/2 | zeta ) <= 2 gamma / tau.    (****)

If S >= Kc/2 and Z < Kc/2, some successful entrance has center in
A_xi. So o <-> A_xi with all this. Combining (*), (***), (****),
  P( o <-> B, NOT o <-> A_xi )
    <= 1/(alpha(R-m)) + 4/(K rho_0) + 2 gamma/tau.    (*****)

Now apply the failure comparison (Corollary 1.2) with the barrier
A_xi as a deterministic set. Condition on xi; then A_xi is fixed.
Every v in A_xi satisfies P( v <-> T | xi ) = g_v > 1 - tau. So
  P( o <-> A_xi, NOT o <-> T | xi ) <= tau.
Integrating, and splitting the event { o <-> B, NOT o <-> T }
according to whether o <-> A_xi,
  P( o <-> B, NOT o <-> T )
    <= 1/(alpha(R-m)) + 4/(K rho_0) + 2 gamma/tau + tau < eta.
Each of the four terms is bounded by eta/4: the first by (G), the
second by (G), the third by (E), and tau by (E). []

Section 5. The neighbor relay geometry
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Coarse cubes. For v = (v_1, v_2) in Z^2 define
  c_v = (20r+1) (v_1, v_2, 0),
  Q_v = Lambda_{10r}(c_v)     (the coarse cube),
  B_v = Lambda_{4r}(c_v)      (the inner box).
The cubes Q_v (and their inner boxes B_v) are pairwise vertex-disjoint
for distinct v, because 20r+1 > 20r and each cube has horizontal half-
width 10r (resp. 4r). For nearest neighbors v, x in Z^2, the INTERFACE
I_{vx} is the set of lattice edges from Q_v to Q_x. The union
D = Q_v U Q_x is a rectangular prism (product of three intervals).

Lemma 5.1 (neighbor relay). Let v, x be nearest neighbors in Z^2 and
let G be a finite lattice subgraph containing D = Q_v U Q_x together
with all lattice edges internal to D. Give all internal bits of D
parameter q and all other bits arbitrary probabilities in [0,1]. If
o in V(G) lies outside D, then
  P( o <-> B_v and NOT o <-> B_x ) <= 13 eta,
with all connections taken in G.

Proof. By a translation and signed permutation of coordinates, we may
reduce to c_v = 0 and c_x = (20r+1, 0, 0). Then D equals
  [ -10r, 30r+1 ] x [ -10r, 10r ] x [ -10r, 10r ] (intersected with Z^3),
because the horizontal spans of Q_v and Q_x are [-10r, 10r] and
[10r+1, 30r+1], which combine to a single interval with no lattice gap.

We construct rectangles P_0, ..., P_13 with P_0 = B_v = Lambda_{4r}(0)
and P_13 subset B_x = Lambda_{4r}(20r+1, 0, 0), such that Lemma 4.1
applies with B = P_i and T = P_{i+1} for every i = 0, ..., 12. Then
a union bound gives
  P( o <-> P_0, NOT o <-> P_13 ) <= 13 eta.
Since P_0 = B_v and P_13 subset B_x, we get the Lemma.

The construction has 13 moves: 3 contractions shrink P_0 down to
a cube at the origin, then 10 translations slide that cube to c_x.

Contractions (moves 1, 2, 3). For t = 1, 2, 3 let P_t = Lambda_{w_t}(0)
with half-widths
  a_{t,h} = 2r + tR   for h <= t,
  a_{t,h} = 4r + tR   for h > t,
in the h-th coordinate direction, h = 1, 2, 3.

Fix t in {1, 2, 3} and take u in P_{t-1}^{(R)}. By definition of the
R-expansion, |u_h| <= 2r + tR for h < t and |u_h| <= 4r + tR for
h >= t. Consider Lambda_{2r}(u) with the quarter-face whose normal is
coordinate t, oriented toward the origin: its normal sign is OPPOSITE
to sign(u_t) (either sign when u_t = 0), and its two transverse signs
are chosen OPPOSITE to sign(u_h) (either sign when u_h = 0). Then:
- |the face's normal coordinate| = ||u_t| - 2r| <= max(2r, |u_t|-2r)
  <= 2r + tR = a_{t,t};
- |each transverse coordinate| <= max(|u_h|, 2r) <= a_{t,h}.
So this quarter-face of Lambda_{2r}(u) sits inside P_t. Also every point
of Lambda_{2r}(u) has |coordinate_h| <= |u_h| + 2r <= 6r + 3R < 10r
(since r > 100(R+1) >= (10/6)R + 1), so Lambda_{2r}(u) subset D. And
o is outside D, hence outside P_{t-1}^{(R)}. So Lemma 4.1 applies with
B = P_{t-1}, T = P_t, l = 2r.

Translations (moves 4, ..., 13). Define
  s_i = 2r          for i = 1, ..., 9,
  s_10 = 2r + 1,
  z_0 = 0,   z_i = (s_1 + ... + s_i, 0, 0),
and target cubes
  P_{3+i} = Lambda_{w_i}(z_i),    w_i = 2r + (3+i)R,
for i = 1, ..., 10. So z_10 = (s_1 + ... + s_10, 0, 0) = (20r+1, 0, 0)
= c_x and w_10 = 2r + 13R < 4r (since r > 100(R+1) >= R), so
P_13 = Lambda_{w_10}(z_10) subset B_x.

Fix i in {1, ..., 10} and take u in P_{2+i}^{(R)}. Since
P_{2+i} = Lambda_{w_i}(z_{i-1}), we have |u_h - (z_{i-1})_h| <= w_i for
each h. Consider Lambda_{s_i}(u) with the quarter-face whose normal is
coordinate 1 with POSITIVE sign, and whose transverse signs are chosen
toward the origin (relative to z_i, in coordinates 2 and 3). Then:
- the normal coordinate is x_1 = u_1 + s_i, so x_1 - (z_i)_1 =
  u_1 - (z_{i-1})_1 has absolute value <= w_i;
- each transverse coordinate has |x_h| <= max(|u_h - (z_{i-1})_h|, s_i)
  <= w_i, using s_i <= w_i (which holds because s_i <= 2r+1 and w_i >=
  2r+4R).
So this quarter-face of Lambda_{s_i}(u) sits inside P_{3+i}. Also every
point of the full cube Lambda_{s_i}(u) satisfies:
- x_1 - (z_{i-1})_1 in [-w_i - s_i, w_i + s_i] with (z_{i-1})_1 in
  [0, 18r], so x_1 in [-2r - 13R - 1, 22r + 13R + 1];
- |x_h| <= w_i + s_i <= 4r + 13R + 1 for h = 2, 3.
Since r > 100(R+1), we have 13R + 1 < 6r and 13R < 8r, so from
x_1 >= -2r - 13R - 1 >= -2r - 6r = -8r > -10r and x_1 <= 22r + 13R + 1
<= 22r + 8r + 1 = 30r + 1, and |x_h| <= 4r + 13R + 1 <= 4r + 6r =
10r, the full cube Lambda_{s_i}(u) sits inside D. And o is outside D,
hence outside P_{2+i}^{(R)}. So Lemma 4.1 applies with B = P_{2+i},
T = P_{3+i}, l = s_i in {2r, 2r+1} subset {2r, 2r+1, 10r}.

Finish. Moves 1-13 chain B_v = P_0 -> P_1 -> ... -> P_13 subset B_x,
each contributing at most eta to the chance of a disconnection. So
  P( o <-> P_0, NOT o <-> P_13 ) <= 13 eta,
which gives the conclusion. []

We will use Lemma 5.1 exactly once per processed vertex in the
exploration: when a pending v is processed and a neighbor x is being
tested, the surrounding prism is D = Q_v U Q_x, the root o is
outside D, and the internal bits of D have parameter q. The rest of
Section 6 uses this in the form stated without further modification.