No percolation at criticality on quasi-transitive graphs

Proof. Choose a representative in each of the finitely many orbits. For each representative and each orbit, fix a path to that orbit, and let C_0 bound the lengths of these finitely many paths. Translating them proves the density assertion. To compare balls, move the center of a ball attaining V_+(r) within distance C_0 of a center attaining V_-(r+C_0). The translated smaller ball lies in the larger one. Also B(x,r+s) is covered by the radius-s balls centered in B(x,r), proving the second inequality.

Thus \log V_+(r) is subadditive. Dividing a radius into blocks of any fixed length shows that its quotient by r converges to its infimum. This proves existence of \gamma. Finally V_+(r-C_0)\le |B(x,r)|\le V_+(r) for r\ge C_0 gives the claimed uniform growth conclusions.□

Proof. Let D bound the degrees of G. We first prove an averaged estimate on any finite induced subgraph F. Independently of the edge states, mark each vertex with probability 1-e^{-h}, where 0<h\le1. Let T_e be the event that the endpoints of e lie in distinct clusters both containing a mark. Let N_e count the marked clusters incident to e, counting a cluster only once even when it contains both endpoints, and put I_e=\mathbf1_{\{N_e\ge1\}}. Flipping e does not change the union of its endpoint clusters, so I_e is unchanged by that flip. For closed e, \mathbf1_{T_e}=N_e-I_e, whereas for open e, N_e=I_e. With q=1-p, conditioning on all other edges therefore gives

where c(K) and o(K) count the closed and open edges incident to K, respectively. Each incidence is counted once per cluster.

Explore a cluster C_v, querying all its incident edges, including internal edges, once each. If T is the number of queries and m=|C_v|, then T\le Dm and, when T>0, m\le T+1\le2T. The fresh query bits are independent Bernoulli variables of parameter p; after stopping, extend them with independent auxiliary bits. Let Z_j be their centered partial sums. Since o(C_v) is the number of open query bits,

Rewrite the sum over clusters in (6) as a sum over vertices, dividing the summand by the cluster size. Averaging the marks and taking absolute values gives

with value zero when T=0. Doob’s maximal inequality yields

Partitioning according to 2^k\le T<2^{k+1}, the expectation in (7) is at most

For the last bound, split the sum where 2^kh first exceeds one; both resulting geometric series are bounded by a constant times \sqrt h. On H_s(e), conditional on the edges, the two clusters are marked with probability at least (1-e^{-hs})^2. Taking h=1/s therefore proves

uniformly for p\ge p_*.

To pass to an individual edge, choose C_0' so that every vertex orbit is C_0'-dense. Fix an edge e=xy and a center o. For every vertex of B(o,n), choose a point in the orbit of x within distance C_0'. There are at least |B(o,n)|/V_+(C_0') distinct chosen points. At each, an automorphic copy of e has both endpoints in B(o,n+C_0'+1). Each unoriented edge is counted at most twice, so the number of distinct copies is at least

For fixed s, subexponential growth gives arbitrarily large n with

Otherwise iteration of this fixed-width expansion would force exponential growth. Set F=G[B(o,n+C_0'+s+1)]. A connected cluster with at least s vertices has a connected s-vertex witness within distance s-1 of any specified vertex. Thus H_s in the full graph implies H_s in F for each selected copy; restriction also preserves distinctness. All copies have the same full-graph probability. Apply (8) and the displayed bounds to obtain the proposition. The constants do not depend on the orbit of e.□

Proof. Given one exact object under avoidance, the other has its ordinary product-cluster law after deleting the first object’s vertices. Indeed, the exact object fixes its open internal edges, its closed internal edges, and its closed boundary edges; all edges wholly outside it retain their independent laws. Avoidance is then automatic. By restriction of a common configuration, this conditional law is stochastically decreasing as the deleted object grows.

Start with a deterministic admissible object at A, sample the object at B by this conditional law, then update the object at A in the same manner, and repeat. Association is preserved at every half-step. To see this, conditional on the current object, the next object is an increasing function of independent bits and is associated by Harris’s inequality. The two conditional means of increasing functions of the next object are decreasing functions of the current object. Their covariance is nonnegative when the current object is associated. The conditional covariance identity proves the assertion.

The two-step chain on the A objects has the avoidance marginal as a stationary law, because its updates are the two conditional laws of that joint distribution. Every transition has a common positive mass at the minimal object consisting of A and no open edges: close all edges incident to A in its update. This probability is bounded below by the product of the closed-edge probabilities over all edges of G. Subtracting that common mass from every transition shows that total variation distances contract by a factor strictly less than one. Consequently the chain converges to its stationary law. Association passes to this finite-state limit, proving association of C(A); the same argument applies to C(B).

Finally, the conditional mean of g(C(B)) given C(A) is decreasing in C(A). Association of the latter object makes its covariance with the increasing function f(C(A)) nonpositive. Taking conditional expectations proves the claimed cross covariance.□

Proof. The claim is immediate if w\in B or B=\varnothing. The conditional probabilities of E form a martingale along the search. At a query its conditional variance increment is pq d_e^2. The search decides E, so

Given the pre-query prefix, the probability of an actual open pivot is p d_e. Thus (9) equals \EE W. It also bounds the diagonal terms in \EE W^2, since p d_e(qd_e)^2\le pq d_e^2.

It remains to bound the products of weights from two pivots. We prove the following conditional estimate for each earlier query f:

Its right side is the pivotal probability before reading f. Multiplying by the probability p that f is open and by its weight qd_f will bring the pair sum back within the variance budget (9).

Fix this prefix and condition on f being open, with new head z. If z\in B there are no later queries. Otherwise contract the vertices reached before f to a root A and delete f for the connectivity calculations that follow. Those vertices are connected by known open edges and contain no target vertex. If f is an actual pivot, z connects to B without using A, while A does not connect to B. The depth-first subsearch from z then succeeds before any older stack entry is resumed. We call this subsearch, stopped on success or exhaustion, the phase.

At a query e in the phase, contract its already reached vertices to S, containing z, and wire B to one target vertex. Keep A and S separate: their only known open link before deletion was f. Delete queried closed edges. All unqueried edges remain independent, including older stack edges whose endpoints may now lie in A and S. Whether still pending or already skipped, they have not been tested. The tail of e lies in S and its head b is unreached.

In this residual product graph with e held closed, let

The remaining possibility is that all three are connected. Define

Here and until the next conditioning all probabilities refer to the unqueried product bits with f,e deleted. In the actual search f is open, so A and S are wired together when computing d_e. Consequently

Indeed, opening e joins the wired source to the target exactly in the \alpha or \sigma cases. In the second case A was already connected to S without f, so f is not pivotal; the first case gives both pivots.

Apply Lemma 3.2 with root sets A and S\cup B, using the increasing events b\leftrightarrow A and S\leftrightarrow B in their respective cluster objects. It gives \gamma u\le v\beta. Reversing the roles, with roots B and A\cup S, gives \sigma u\le x\alpha. The two decreasing isolation events A\not\leftrightarrow S\cup B and B\not\leftrightarrow A\cup S have intersection of probability u. Harris’s inequality therefore gives

In particular, when u>0,

The open-edge information in the cluster objects matters here: the union of the root vertices alone does not determine S\leftrightarrow B.

We now pay for these later pivotal weights with a second martingale. An actual pivot f requires the old root A to avoid both z and the target. Accordingly, for the rest of the phase condition the deleted-f configuration on the fixed event

Let U_{\rm init} be its probability at the beginning of the phase. If it is zero, no pair involving an actual pivot f contributes. Otherwise, under this conditioned law, let r be the conditional probability of z\leftrightarrow B along the phase. This is a bounded martingale even though its query bits are no longer Bernoulli with parameter p.

At the current prefix write U_0,U_1 for the probabilities of U when e is closed and open. The partition above gives

The corresponding probabilities of U\cap\{z\leftrightarrow B\} are v and v+\alpha-\gamma. Hence, whenever U_1>0,

The conditional bit probabilities under the tilt are pU_1/U_{\rm pre} and qU_0/U_{\rm pre}.

Bayes’s formula multiplies the ordinary probability of this prefix by U_{\rm pre}/U_{\rm init}. Thus, after multiplying the tilted martingale variance budget by U_{\rm init}, its contribution at this prefix, expressed under the ordinary phase law, is

If \alpha>0, then u>0 and U_1\ge\alpha>0; moreover U_1,U_{\rm pre}\le U_0. Equations (14) and (13) therefore give

When \alpha=0, discard the nonnegative variance contribution. The total converted variance is at most

The last equality is precisely the pivotal event for f before its bit is read. Using (11), the converted variance therefore bounds the conditional expected sum on the left of (10). All contributions when f is pivotal occur inside the phase, as noted above, so this proves that estimate with the sum over every later query.

Multiply (10) by pq d_f, average over the prefix of f, and sum over f. The sum of products over ordered pivot pairs is bounded by \EE\sum_f pq d_f^2\le1. Combining this with the diagonal bound and the factor two for cross terms in W^2 proves \EE W^2\le3.□

Proof. Write q=1-p. At a pre-query node h of algorithm i, let e be the bit it queries and put b_h=\EE_Q[X_e-p\mid h]. The transcript entropy chain rule and the elementary Bernoulli bound

give

The Bernoulli reference at each node is still p, since its own history has not read that bit. The displayed bound follows from \log t\le t-1, including endpoint values by continuity.

Assign independent uniform priorities in [0,1] to the algorithms and run them in priority order, caching previously read bits. Each algorithm follows exactly its original path; a cached answer supplies the same bit without a fresh query. For every fixed priority order, the combined fresh-query transcript is a function of the configuration. Data processing and the entropy chain rule give total fresh-query entropy at most D(Q\Vert\mu). The binary lower bound d(r\Vert p)\ge2(r-p)^2 follows because its second derivative in r is 1/(r(1-r))\ge4, and its value and first derivative vanish at r=p. It implies

where b_g is the conditional bias given the entire global pre-query history and the fixed priorities.

Fix a local node h of algorithm i with Q(h)>0, querying e, and condition its priority to be t. For a configuration \omega, let K_e(\omega) be the number of algorithms that read e. On configurations visiting h, 1\le K_e\le a, Q-almost surely. The read paths are unchanged by caching. Conditional on such a configuration, the query at h is fresh exactly when all other K_e-1 users have priority larger than t, an event of probability (1-t)^{K_e-1}. The number K_e may be correlated with X_e under Q, so this freshness weight cannot be pulled out of a conditional expectation of the bias. Retain their dependence by defining

Pool the global pre-query nodes at which this local node is visited fresh, averaging the other priorities. Their total probability is Q(h)w_h(t), and the sum of their probability-weighted biases is Q(h)z_h(t). This pooling is legitimate before the bit is read: the current local node and membership in the cache are determined by the global pre-query history. Cauchy–Schwarz thus bounds their total squared-bias contribution below by

with value zero when w_h(t)=0. Every global fresh query belongs to exactly one local node, so these lower bounds can be summed over all nodes.

At priority zero no other algorithm precedes i, so z_h(0)=b_h: this endpoint recovers the original local bias. The overlap bound makes z_h a polynomial of degree at most a-1, since K_e\in\{1,\ldots,a\} on the conditional Q support. Also 0\le w_h\le1. For any polynomial z of degree at most a-1, the classical shifted-Legendre endpoint bound [27, Tables 18.3.1 and 18.6.1] gives

Indeed, expand in the orthonormal shifted Legendre polynomials of degrees 0,\ldots,a-1. Their squared endpoint values are 1,3,\ldots,2a-1, with sum a^2, and Cauchy–Schwarz gives (19). Integrating (18) therefore yields at least Q(h)b_h^2/a^2. Combine with (17) and then (16) to prove the lemma.

No overlap bound under \mu was used. The random variable K_e may be correlated with X_e under Q; this correlation is retained inside z_h(t) throughout the argument.□

Proof. Suppose instead that critical percolation has an infinite cluster with positive probability. Let \theta>0 be the uniform lower bound in (2), and let D be the maximum degree. By (1), \pc>0. All constants below may depend on G and \theta, but will be independent of the scales and of p\in[\pc/2,\pc).

A band of finite cluster sizes. Choose an arbitrarily large integer L\ge2. The event \{|C_v|\ge L\} is determined by a finite ball: if a cluster has at least L vertices, a rooted spanning exploration finds L of them within distance L-1 of v. Finite-event continuity and the finitely many orbits therefore allow a single p\in[\pc/2,\pc) for which

All clusters at this p are finite almost surely. We seek a size s\ge L at which every vertex still has cluster-tail probability at least \theta/2, while some vertex has a cluster in the band [s,s^2) with probability at least (\log s)^{-2}. The first condition will force connections between nearby vertices; the second will supply a finite cluster small enough to find another large cluster nearby.

Set s_j=L^{2^j}. The bands [s_j,s_j^2) are disjoint, and the required lower bounds (\log s_j)^{-2} have a summable total. Let k\ge1 be the first index for which F_{s_k}(z)<\theta/2 for some orbit representative z. Such an index exists because the finite-cluster tails decrease to zero. For this z,

On the other hand, \sum_{j\ge0}(\log s_j)^{-2}=4/(3(\log L)^2)<\theta/4 when L is sufficiently large. Hence there are j<k and s=s_j such that

In particular s\to\infty as L\to\infty.

A nearby pair of large distinct clusters. Let r be the least integer with V_-(r)\ge s^4. Such an integer exists: an infinite connected locally finite graph has vertices at every distance from each vertex, so V_-(r)\ge r+1. The growth hypothesis implies

Indeed, for every fixed M>0, eventually V_-(t)\ge t^M. If r-1 is beyond this threshold, minimality gives (r-1)^M\le V_-(r-1)<s^4, so r<1+s^{4/M}. The alternative that r-1 remains below the threshold only improves the bound. Letting M be arbitrarily large proves (35).

Condition on an exact incidence exposure of a band cluster K=C_z, with s\le|K|<s^2. Its exterior has independent product law. Resample all incidence edges of K independently with parameter p, leaving the exterior unchanged. For every fixed such exposure, the resampled full configuration has law \PP_p, so the expected number of vertices in B(z,r) belonging to clusters of size at least s in that configuration is at least (\theta/2)|B(z,r)|.

In the exterior graph G\setminus K, at most

vertices lie in K or in exterior clusters of size less than s that are adjacent to K. Every vertex whose resampled cluster has size at least s, but whose exterior cluster has size less than s, lies in this set: otherwise its exterior cluster is unaffected by resampling incidence edges of K. Consequently, uniformly in the fixed band exposure, the expected number of vertices of B(z,r) in exterior clusters of size at least s is at least

for sufficiently large L, because |B(z,r)|\ge s^4. In the original configuration these exterior clusters are distinct from C_z=K. Averaging over the band event and then over B(z,r) therefore gives a deterministic y\in B(z,r) such that

Put c_0=\theta^2/8, and choose the smallest distance d of any pair x,z' satisfying

The preceding pair shows that d\le r. Distinct clusters rule out d=0. Proposition 3.1 rules out d=1 for all sufficiently large L, since its uniform bound Cs^{-1/2} is smaller than c_0(\log s)^{-2}. For any pair u,v at distance less than d, Harris’s inequality and (34) give probability at least \theta^2/4 that both cluster sizes are at least s. By the minimality of d, the probability that they are also distinct is less than c_0f\le c_0. Thus

A finite graph to which interpolation applies. Fix a geodesic from x to z' of length d. We now choose a finite induced ball F sufficiently large; the parameter p, size s, pair, and path remain fixed during this choice. First include the balls of radius s around x,z'. Every configuration in the infinite-graph event (36) then has two distinct endpoint clusters of size at least s in F as well: the size witnesses lie in those balls, and restriction cannot join distinct clusters. Therefore the finite endpoint-event probability \delta_F satisfies the exact lower bound

No limiting equality or loss in this bound is needed.

For each proper pair on the geodesic, its path-index separation is less than d, so (37) applies. Connections in increasing finite induced balls increase to the full event, since every witnessing path is finite. There are only finitely many pairs, so enlarge F until their finite-graph connection probabilities are all at least \theta^2/16.

Finally, all clusters at this fixed subcritical p are finite almost surely. Enlarge F further until, for each edge e of the fixed geodesic, the probability that either full endpoint cluster is not contained in F is at most s^{-1}. If both clusters are contained, their restrictions equal the original clusters. Hence

for every path edge. Enlarging F preserves the earlier endpoint and connection bounds.

Apply Proposition 4.1 in F with c=\theta^2/16. Its constants are uniform: p\ge\pc/2>0 and 1-p\ge1-\pc>0. By (34), (35), and (38), some path edge satisfies

But (39) gives

for s\ge1, a contradiction as L\to\infty. This proves the theorem.□

Proof. Sample all edges of G once and use their restrictions for every graph below. Conditional on an exact value W_U=w, the edges induced outside w have product law, including those involving the previously deleted vertices U. Consequently R_F(U) is the expectation of

in this common configuration. This quantity is nonnegative.

If U\subseteq U', then W_{U'}\subseteq W_U. On \{s\notin W_U\}, the first cluster in D_U grows when U is replaced by U'. The second cluster is exactly C^{G\setminus U}(s): in G\setminus U the cluster of s is disjoint from the union of the S-clusters. The corresponding second cluster for U' is C^{G\setminus U'}(s) and can only shrink. Increasingness of F therefore gives D_{U'}\ge D_U on this event. On its complement, D_U=0 and D_{U'}\ge0. Taking expectations proves the claim.□

Proof. We induct downward in k. At a fixed index, exposing the earlier clusters will split v_k^F into an averaged version of itself and nonnegative contributions from later columns. Repeating the averaging will replace F by its mean and leave exactly the difference in (41).

For k=N, both vectors in the difference have only their Nth coordinate nonzero, so the difference vanishes. Fix k<N and assume the claim for all larger indices. Write s=x_k, S=S_k, W=C(S), and c(w)=\mathbb E^{G\setminus w}F(C(s)) for w\supseteq S avoiding s. The function c is nonincreasing in w by restriction coupling.

Condition on W=w and s\notin w, and use the independent product law outside w. If x_i\notin w, partition its cluster by its earliest distinguished vertex. This is x_k exactly when x_i\in C(s); write L_{il}^w for the case where it is x_l, l>k. Conditional on the exact cluster U=C^{G\setminus w}(x_l) in the latter case, the expected value of F(C(s)) is c(w\cup U). Partitioning the expectation c(w) in this way yields

If x_i\in w, every term is zero instead.

We first average the leading term in (42). Given C(s)=U under E_k, the earlier-root cluster W has the law of W_U=C^{G\setminus U}(S), by the product law outside the exposed cluster. Define

This function is nonnegative and increasing, since W_U shrinks with U and c decreases with its argument. Conditioning first on W and then on C(s) shows that the averaged leading term is

The remaining terms give later columns. More precisely, averaging (42) conditional on E_k gives

Here the residual uses the fixed roots s,S of this induction step. To check the normalization, on E_k the event L_{il}^W is exactly E_l\cap\{x_i\in C(x_l)\}. Given C(x_l)=U under E_l, the S-cluster is W_U with product law in G\setminus U, and the remaining condition E_k is s\notin W_U. Division by d_k and conditioning on E_l give precisely the factor d_l/d_k. Lemma 6.2 shows that every F_l is nonnegative and increasing. The induction hypothesis therefore places every term v_l^{F_l} in the cone generated by h_j with j>k.

Thus one application of P leaves a remainder in the cone of later columns. To iterate this decomposition, we identify the limit of P^jF. The operator P first samples W conditional on C(s) and then samples C(s) conditional on W. Both are conditional laws of the joint distribution given E_k, so \mu_k is stationary for this two-step Markov chain. These alternating cluster updates are the method of van den Berg, Häggström and Kahn [34, Section 2.1]. Every transition puts mass at least

on \{s\}. Subtracting this common mass from two transition averages shows \operatorname{osc}(Pg)\le(1-a)\operatorname{osc}(g) for every function on the finite state space. Stationarity then implies P^jF\to\mathbb E_{\mu_k}F uniformly.

Iterate (43). Each P^jF remains nonnegative and increasing, so v_k^F-v_k^{P^jF} belongs to the cone generated by the later columns. This cone is closed: on coordinates k+1,\ldots,N its generators form a unit lower-triangular basis. Taking the limit proves (41). Finally H^{-1}h_l is the lth coordinate vector, proving the last assertion.□

Proof of Theorem 6.1. First suppose the graph is finite and all p_e<1. If o\in A, the left side of (40) equals \mathbb P(o\leftrightarrow T) and the inequality is immediate. Otherwise take the distinguished list to consist of the vertices of A followed by x_N=o, and set

This is one nonnegative increasing function, restricted to each \mathcal D_k as needed. Partitioning by the first distinguished vertex gives y=\sum_k d_kv_k^F, so Lemma 6.3 implies H^{-1}y\ge0 coordinatewise. The last row of (44) yields

For i<N, length-zero paths give y_i=\mathbb P(x_i\leftrightarrow T), whereas y_N is the joint probability in the theorem. By (45),

Thus the promised relay weights are \alpha_{x_i}=\Gamma_{Ni} for i<N. They are nonnegative, proving the finite-graph inequality. This argument also covers T=\varnothing, when F=0.

All event probabilities on a finite graph are polynomials in the edge probabilities. Approximating each probability equal to one from below therefore includes deterministic open edges as well as closed ones.

For a countable graph and finite A, exhaust the graph by finite subgraphs containing o and A, and intersect T with their vertex sets. Every connection has a finite witness, so the individual and joint connection events increase to the corresponding events in G. The minimum over the finite set A also converges. This proves (40) for finite A. Finally exhaust a countable nonempty A by finite nonempty sets A_j. The two events involving A_j increase to those involving A, while \min_{a\in A_j}\mathbb P(a\leftrightarrow T) decreases to the infimum over A. Taking limits proves the result.□

Proof. Subtract (40) from \mathbb P(o\leftrightarrow A). For an empty relay set the event on the left is empty.□

Proof. Increase d if necessary so that d\ge1. Let C be a common density radius for the finitely many vertex orbits of \operatorname{Aut}(G). Fix one orbit O, set L=2C+1, and form a graph \Gamma on O by joining distinct vertices whose distance in G is at most L. To connect two points of O, take a path between them in G and replace its intermediate vertices by points of O within distance C. Consecutive replacements are equal or adjacent in \Gamma. Thus \Gamma is connected. It is locally finite, and the image A of \operatorname{Aut}(G) on O is a transitive subgroup of \operatorname{Aut}(\Gamma).

At a radius R=R_j, choose x with |B(x,R)|=V_-(R) and u\in O with d(x,u)\le C. For n=\lfloor(R-C)/L\rfloor,

Writing \beta_\Gamma(n) for the cardinality of a radius-n ball in this transitive graph, we obtain \beta_\Gamma(n)\le R^d. For all sufficiently large such scales, R\le c n with a fixed constant c. Absorbing c^d into an extra power of n gives

for arbitrarily large integers n.

Apply Tessera–Tointon’s Corollary 2.4 with growth exponent d+1, \lambda=1/2, and the transitive group A [30, Corollary 2.4]. Its hypotheses require only one sufficiently large scale and do not require A to be closed in \operatorname{Aut}(\Gamma). The conclusion supplies a normal subgroup H\lhd A whose orbits have finite diameter, such that Q=A/H acts faithfully on \Gamma/H, is finitely generated and virtually nilpotent, and has finite vertex stabilizers. The H-orbits are finite because \Gamma is locally finite.

Let \vartheta:\operatorname{Aut}(G)\to Q be the composite epimorphism, and put K=\ker\vartheta. Its orbits on O are the H-orbits. For an arbitrary v\in G, choose u\in O with d(u,v)\le C. Then

so Kv is finite. Also, \operatorname{Aut}(G)_v moves u within the finite ball B_G(v,C). Hence its image under \vartheta has a finite orbit on the block H(u)\in\Gamma/H. Its stabilizer at that block is a subgroup of the finite Q-stabilizer. The orbit–stabilizer formula therefore makes \vartheta(\operatorname{Aut}(G)_v) finite.

Choose a finite-index nilpotent subgroup N\le Q and let \Lambda=\vartheta^{-1}(N). A finite-index subgroup of a finitely generated group is finitely generated: rewriting a word through a finite set of coset representatives gives a finite generating set. Thus N is finitely generated. Each \operatorname{Aut}(G)-orbit splits into at most [\operatorname{Aut}(G):\Lambda] many \Lambda-orbits. Restricting \vartheta to \Lambda gives \varrho, with the other two properties already proved.□

Proof. Write \gamma_1=N and \gamma_{i+1}=[N,\gamma_i] for the lower central series. The first factor N/\gamma_2 is finitely generated abelian. Modulo \gamma_{i+2}, the commutator product identities give a bilinear map

whose values generate the target. Here bilinearity follows because commutators of one higher weight vanish in the target quotient. Inductively, images of pairs of finite generating sets generate each successive factor. These factors are abelian, and nilpotence makes only finitely many of them nontrivial. Refining each finitely generated abelian factor by adjoining its generators one at a time gives a cyclic series.

For a subgroup J, intersect this series with J. The natural map

is injective, so each inherited factor is cyclic. Lifting generators successively up this finite series shows that J is finitely generated. Suppose its count of infinite factors is still h. Then its image in every infinite cyclic ambient factor is infinite, hence has finite index; its image in a finite factor also has finite index. Induction up the series gives [N:J]<\infty. Explicitly, if J_i=J\cap N_i, then

and [N_i:J_iN_{i+1}] is the index of the image in the cyclic factor. Both indices are finite at each step, starting from the trivial last group. This proves the strict decrease for infinite-index subgroups.

For the last assertion, the first commutator pairing is alternating on N/\gamma_2. If that abelian group has rank at most one, the pairing has only torsion values: its exterior square is a finitely generated torsion group. Its finitely many generating values make \gamma_2/\gamma_3 finite. The displayed bilinear pairing then makes every later factor finite as well. Thus [N,N]=\gamma_2 is finite. Rank zero of the abelianization makes N finite. In rank one, projection of the abelianization onto its infinite cyclic factor gives an epimorphism N\to\mathbb Z with finite kernel.□

Proof. Suppose otherwise. There are countably many finite boxes in \mathbb Z^2 and countably many connected components of their inverse images. Hence some fixed finite box Q and a fixed infinite connected component G' of the induced graph G[\pi^{-1}(Q)] have an infinite open cluster at p=\pc(G) with positive probability. Subgraph monotonicity gives \pc(G')\ge\pc(G); this positive probability gives the reverse inequality. Thus

and G' percolates at its own critical value.

Let \Lambda' consist of the elements of \ker(\phi\varrho) that preserve G'. It has finitely many vertex orbits on G'. Indeed, if x,y\in G' lie in the same \Lambda-orbit and satisfy \pi(x)=\pi(y), choose g\in\Lambda with gx=y. Equation (47) gives \phi\varrho(g)=0. This element preserves the induced graph G[\pi^{-1}(Q)] and maps the component of x to that of y; these are the same component. Thus g\in\Lambda'. There are only finitely many pairs of an original \Lambda-orbit and a level in Q, which proves the claim.

Set N'=\varrho(\Lambda'). Restriction gives an epimorphism \Lambda'\to N' whose kernel has finite orbits and whose vertex stabilizers have finite images. The group N' is nilpotent and is finitely generated by Lemma 7.3. It lies in \ker\phi, which has infinite index in N, so its inherited cyclic series has strictly fewer than h infinite factors. The graph G' is connected, locally finite and infinite. Its intrinsic balls are contained in ambient balls of the same radius, so it has subexponential growth. It therefore satisfies every hypothesis of the smaller-count induction. Theorem 7.1 at that count forbids the critical infinite cluster just found, a contradiction.□

Proof. Letting s\to\infty in Proposition 3.1 shows that, for every edge, the probability that its endpoints lie in distinct infinite clusters is zero. We show that this excludes any two infinite clusters, even if no edge initially joins them.

Otherwise countability gives fixed vertices x,y that belong to distinct infinite clusters with positive probability. Choose a fixed simple path x=x_0,x_1,\ldots,x_d=y. On that event let j be the first index with x_j\in C_y; some fixed j\ge1 occurs on a positive-probability subevent. Force the finitely many prefix edges x_ix_{i+1} for 0\le i<j-1 open (none if j=1). Every endpoint of these edges was outside C_y, so this modification leaves C_y unchanged. It makes C_{x_{j-1}} infinite through x, while that cluster remains distinct from C_{x_j}=C_y. The modified event still has positive probability: condition on all unmodified bits and use that the all-open state of the finite prefix has positive conditional probability. This contradicts the preceding conclusion for the fixed edge x_{j-1}x_j. Thus there is at most one infinite cluster almost surely. Existence is a tail event, so its assumed positive probability is one.□

Proof of Proposition 8.1. Choose o with \pi(o)=0 and put \zeta=e/1000. Countability gives a vertex with positive infinite-cluster probability. Harris’s inequality transfers this positivity along fixed paths to each of the finitely many orbit representatives. Hence

For each fixed nonzero linear functional \ell on \mathbb R^2, the unique infinite cluster is unbounded above in \ell\circ\pi, almost surely. Indeed, the union of all infinite clusters meets \{\ell\circ\pi>r\} with probability at least \theta, by choosing one vertex there. Its unboundedness above is a tail event: changing finitely many edges changes that union by at most finitely many vertices. Continuity from above and the zero-one law give probability one, and uniqueness gives the stated conclusion.

We first construct the two events at o and at \pc, with error smaller than e/8 and failure probability smaller than \eta/10. In each of the two cases below the seed is chosen before the scales that make the coordinate map small. Only after fixing the map will we lower the percolation parameter.

Case 1: no fixed direction supports a strip ray with positive probability. For a unit vector d, a centered strip means \{x:|d^\perp\cdot\pi(x)|\le w\} for some finite w. Translated strips are contained in wider centered strips. In this case the probability of a ray in such a strip is zero for each fixed d. We do not need a statement about the union over all directions.

Cover the unit circle by M arcs of angular radius at most \zeta, with signed unit centers. Choose m_0 so that B(o,m_0) hits the infinite cluster with probability greater than 1-(\eta/20)^M. This choice does not involve any later scale. Fix an arbitrarily large W containing the seed projections well inside the Euclidean ball of radius W. For U\ge W, consider the positive matrices

The parameter space is a disk: all angles at s=0 give W I. Consider open paths from the seed whose last vertex is their first exit from \{|A^{-1}\pi|_2<1\}. Their final normalized radius is between 1 and 1+D_\pi/W. Seed contact with the infinite cluster guarantees such a path, since an infinite ray cannot have bounded projection. Split the exit event according to the M endpoint arcs. Their misses are decreasing events. Harris’s inequality implies that at least one arc is hit with probability greater than 1-\eta/20. Call its center a favored center.

For sufficiently large U, every favored center at a boundary parameter s=1 has its unoriented line within angle \pi/16 of the minor axis, uniformly in \varphi. Otherwise take U_j\to\infty and boundary parameters violating this assertion. A subsequence of their major axes converges to a fixed direction d. Since the arc radii are small, favored exits have major-axis displacement bounded below by a positive constant times U_j, while the whole exit path has transverse displacement at most W+D_\pi. Loop erasure gives arbitrarily long simple open paths from the finite seed. For each fixed length l, all such initial segments lie in the finite union of radius-l balls about the seed. Convergence of the axes is uniform on the projections of this finite set. Since D_\pi<W, it puts these segments in the centered strip about d of width 2W, for all sufficiently large j. Such length-l paths thus have probability at least 1-\eta/20 for every l. These events decrease with l, and finite branching supplies an infinite ray in the strip, a contradiction.

Triangulate the parameter disk so finely that adjacent matrices satisfy \|A_i^{-1}A_j-I\|_2\le\zeta and boundary angle increments are less than \pi/32. Choose one favored center at each vertex. Some adjacent center lines have projective separation at least \pi/8. Indeed, otherwise the principal increments of their doubled line angles have absolute value less than \pi/4. Their sum around each triangle is a multiple of 2\pi of absolute value less than 2\pi, hence zero; summing triangles gives zero around the boundary. On the boundary, however, the doubled angles have lifts 2\varphi+\pi with errors of absolute value less than \pi/8. The mesh condition makes successive lift differences principal increments, whose total is 2\pi. This is a contradiction.

Take such an adjacent pair with matrices A_i,A_j. Let d_1,d_2 be their signed favored unit arc centers in their respective normalized coordinates, so |\det(d_1,d_2)|\ge\sin(\pi/8). Let \Psi send these original centers to (1,1) and (1,-1); its operator norm is less than 10. Set \Phi=\Psi A_i^{-1}. A point of the second path with normalized coordinate u=A_j^{-1}\pi(x) has coordinate A_i^{-1}A_j u under the first matrix. Its displacement from u is at most \zeta|u|_2. Thus arc width, radial overshoot, and this adjacent-matrix error give endpoint error less than e/8 once D_\pi/W<\zeta. The whole paths have coordinate displacement less than 30, and edge increments tend to zero as W\to\infty.

Case 2: some fixed direction supports a strip ray with positive probability. Existence of a ray in some finite-width centered strip in that direction is a tail event: a suffix survives every finite edge modification. Its probability is therefore one. Choose a seed radius m_0 and a width w so that a ray from B(o,m_0) in that strip exists with probability greater than 1-(\eta/30)^2. Enlarge w to contain the seed projection as well. Write the longitudinal and transverse coordinates in these perpendicular axes. Such a ray is longitudinally unbounded in absolute value, by the bounded-projection hypothesis.

Choose an arbitrarily large transverse scale V with w/V<\zeta and D_\pi/V<\zeta. By uniqueness and the preceding directional tail observation, on the seed-strip event the seed also connects to absolute transverse level V. Stop at the first such crossing. Its finite path can be confined to some longitudinal bound M(V) while retaining probability greater than 1-2(\eta/30)^2: increase the bound and use continuity from below. Choose U with M(V)/U<\zeta and D_\pi/U<\zeta. The strip ray also gives a first crossing of absolute longitudinal level U with probability greater than 1-(\eta/30)^2.

Split each kind of exit by its sign. Harris’s inequality on the two misses supplies one favored sign of each kind, each with probability greater than 1-\eta/10. After division by U,V, each endpoint is within supremum distance \zeta of its signed coordinate unit vector, and both paths lie in the square [-2,2]^2. A linear map sending those two vectors to (1,1),(1,-1) gives endpoint error less than e/8 and path displacement less than 30. For any requested operator bound, first take V sufficiently large, then determine the finite bound M(V), and finally take U sufficiently large. The last linear map has norm at most 2, so the composite map has norm at most 2/\min(U,V). No bound on the growth of M(V) is needed. Thus edge increments can be made arbitrarily small after the seed has been fixed.

Let c be a density radius of the orbit \Lambda o and set m=m_0+c. Given y, choose g with d(go,y)\le c. Equivariance translates the two events at o to go, and their seeds lie in B(y,m). Include in the preceding scale choices the requirements |\Phi\pi(go)-\Phi\pi(y)|_\infty<e/8 and that edge increments are at most the requested \rho_0: it suffices to make the operator norm of \Phi smaller than both e/(8(c+1)D_\pi) and \rho_0/D_\pi. The endpoint errors are then at most e/4, and the path bound is less than 100. All choices of m preceded the requested small edge increment.

Only now lower the percolation parameter. Finite paths witness the two events at o. Approximate each by a finite union of path witnesses, preserving a probability greater than 1-\eta, with room to spare. Continuity of these finite events gives the same bounds at a common p'\in[\pc/2,\pc). Their translates give the required bounds at every y by the preceding deterministic containment.□

Proof. Site layers are spaced by T in the time coordinate; within a layer their heights are spaced by 2\mu T. The choices give T>2J and \mu T>\mu J+H, so the Q regions are disjoint. A tube near either endpoint layer has height differing from that endpoint by at most \mu J+H when its time differs by at most J. It therefore misses every other Q in that layer; other layers are excluded by their time coordinates.

Tubes in nonadjacent layer intervals have disjoint time interiors. At a common layer plane, distinct endpoint heights differ by 2\mu T>2H, so adjacent-layer tubes can meet only at a shared endpoint, inside its Q. In the same layer interval, parallel tube axes are separated by 2\mu T. Oppositely sloped axes can approach within 2H only when they share a start, within time H/\mu of that start, or share an end, within time H/\mu of that end. These intersections lie in the corresponding Q, since J>H/\mu. Combining these tube facts with the Q facts proves the vertex claims. An edge in both induced subgraphs has both endpoints in their vertex intersection, proving the last assertion. Edges joining different corridors are never added merely because both their endpoints have been revealed.□

Proof. The empty input is immediate. We first choose a shell at which there are unlikely to be only a few exterior contacts. We will use the contacts to reach a relay set determined by independent interior bits, then apply joint gluing after those bits have been fixed.

A shell with enough contacts. Use distance in the original graph to B_*. For m+1\le j\le R, let X_j be the level-j vertices reachable from * using only vertices at levels at least j and the wired source. It is measurable in the exterior bits with both endpoints at these levels. Hitting B_* requires X_j\ne\varnothing. If 1\le|X_j|<k, closing all edges from X_j to level j-1 has conditional probability at least (1-\pc)^{Dk} and forces the minimum reached level to be exactly j. These minimum-level events are disjoint for different j. Thus some deterministic j satisfies

The edges closed here are fresh collar edges, independent of the exterior. Distance changes by at most one along every original edge; the source wires lie outside all these levels.

Fix this deterministic j. Let \mathcal F_{\rm ext} be the sigma-field generated by edges with both endpoints at levels at least j. It determines X_j and will determine the finite list of contacts used for trials.

An interior relay set. For every level-j vertex v, fix an inward geodesic of length m+1 ending at y_v, and a spanning tree of B(y_v,m). The geodesic and tree lie in the collar, and every one of their edges has an endpoint of level less than j. Let W_v be the event that all these trial edges are open. Its probability satisfies

Let \xi be the configuration on the union of all these fixed trial edge sets, including trials at vertices not ultimately selected. These are fresh product bits, independent of \mathcal F_{\rm ext}. Define

This conditional probability integrates over all remaining bits, including those generating \mathcal F_{\rm ext}. The actual exterior chooses contacts but is not fixed in this target probability. The function g_v is increasing in \xi and has mean at least 1-\eta_0. Harris’s inequality and Markov’s inequality therefore give

Define the relay set before choosing the contact list:

This set contains every good trial vertex and depends only on \xi. Given \xi, each v\in A(\xi) is connected by its trial edges to the whole seed ball, so its conditional probability of reaching T_* is at least 1-\lambda. The remaining law is a countable product with the trial states fixed. Corollary 6.4 gives

It remains to bound the probability that the source hits B_* without reaching this relay set.

Reaching an interior relay from the exterior. Fix an enumeration of the countable vertex set. If |X_j|\ge k, select its first available vertices in this order, using only the exterior, at pairwise distances greater than 4m+2, until the sum of their s_v is in [K,K+1]. Greedy selection deletes at most V_+(4m+2) candidates each time, so (51) guarantees this is possible; the selected list is finite even when X_j is infinite. Each trial lies within distance 2m+1 of its vertex, so the selected trials have disjoint edge sets. Conditional on the exterior, their probability of no success is at most e^{-K}=\kappa/4. By (56) their probability of a successful trial with g_v<1-\lambda is at most (K+1)\eta_0/\lambda\le\kappa/4. These estimates remain valid after selection because the entire \xi law is independent of the exterior selecting the list.

On a hit of B_*, the contact set is nonempty. Outside the small-contact error in (55) and the two trial errors, some selected exterior contact belongs to A(\xi) and is already connected to the source. Thus the probability of hitting B_* without hitting A(\xi) is at most 3\kappa/4. Integrating the conditional gluing bound and using \lambda=\kappa/4 proves (54).□

Proof. Choose o with (t(o),z(o))=(0,0), and wire a synthetic source to the finite ball B(o,m). A revealed history records a union of the edge domains \mathcal Q_v,\mathcal E_{vx} and their actual p' states. In a prospective graph obtained by adding another edge domain, previously revealed states remain fixed and the other edges have their conditional product law. We include only the edges of those domains, even if further original edges join vertices already present. The domains may be infinite; the conditional-law justification below covers this point.

Initialization. At the root site, the two moves reach the corresponding B_1 directly with probability at least 1-\eta_0. From B_1 onward, source wires are outside each input collar, by their time separation and (52). Summing Proposition 9.2 in a fixed child corridor shows that the source misses its child mark with probability at most \eta_0+L\kappa. Reveal \mathcal Q_0. The two conditional predictions for reaching the child marks are both at least 1-\delta on an event of positive probability: the probability that either fails this threshold is at most 2(\eta_0+L\kappa)/\delta<1. Condition on this \mathcal Q_0-measurable event, declare the root good, and store these two predictions. The source already hits M_0 through o. For the rest of the proof, probabilities refer to the law conditioned on this initialization event.

A test and its two exposure times. Process sites by increasing layer a+b, in a fixed order within each layer. A nonroot site is tested if it has a good parent; choose one such parent w deterministically. Sites with no good parent are not tested. Before testing v, let I denote the revealed history. There are two geometric facts at this time. The incoming corridor \mathcal E_{wv} meets I only in its parent’s already known \mathcal Q_w. Every outgoing corridor \mathcal E_{vx} misses I entirely. Indeed, no revealed corridor has endpoint v or either child of v: earlier tests reveal only their own incoming corridors, and all sites of a preceding layer are processed first. Apply Lemma 9.1 to these domains and to \mathcal Q_0.

The first fact preserves the prediction stored when w became good. Intervening reveals meet \mathcal E_{wv} only in \mathcal Q_w, which was already known then, so they leave the other incoming bits independent with parameter p'. The newly included history edges can only add paths. Thus, in the prospective graph I\cup\mathcal E_{wv},

The second fact allows us to estimate both outgoing predictions before revealing the incoming corridor. For a child x of v, use the prospective graph

Conditionally on I, every edge of D_{vx} still has its fresh iid p' law. In particular this includes the shared endpoint region \mathcal Q_v=\mathcal E_{wv}\cap\mathcal E_{vx}, which has not yet been revealed. The source wires lie outside all the input collars, by time separation. Apply Proposition 9.2 to the L+1 consecutive relays, all in this same prospective graph. It gives

A hit of the first region and a miss of the last entails a hit followed by a miss at some consecutive pair, so no independence between the successive estimates is needed.

Now reveal all of \mathcal E_{wv} and call the enlarged history F. The event A_v and every state in \mathcal Q_v are now known. The outgoing edges outside \mathcal Q_v remain unexposed. For each child compute

This product integral fixes the incoming states and integrates over the unexposed outgoing edges; computing it reveals no further edge. Declare v good if A_v occurs and both predictions are at least 1-\delta; otherwise declare the tested site failed. In the good case store both predictions. By conditioning (58) on F,

Together with (57) and Markov’s inequality, this gives the uniform conditional failure bound

Conditional laws for countable reveal domains. We justify the product-law statements also for infinite reveal domains. At any finite slot there are only finitely many earlier decisions and parent choices. For each possible decision sequence, the union R of revealed edge sets is deterministic, and the event of following that sequence is measurable in the coordinates of R. The sequence, its edge states, and every prediction are functions of those coordinates; a prediction is a measurable product integral on the countable complement. On this part of the history space, independence of disjoint coordinate sets gives the original product law on R^c, conditionally on the full revealed states. This is a statement about conditional kernels, and does not condition on a positive-probability individual infinite configuration. It follows either directly by Fubini on the two countable coordinate sets or by first testing cylinder functions on R^c and then using a monotone class argument. The initial conditioning is measurable in \mathcal Q_0 and hence preserves this property. This proves the induction on slots. In particular, future corridor bits are not revealed by decisions based on their conditional probabilities.

A boundary of failed sites. For any fixed finite set S of nonroot sites,

Indeed, enumerate the finite slots up to the last site of S. At its slot, the event that a given site is tested and that the previous specified sites failed is measurable before the test. Apply (59) and iterate. A specified site that is not tested makes the event impossible. A set containing the good root also has probability zero.

If the good set is finite, draw the counterclockwise boundaries of its unit site squares and cancel oppositely oriented shared edges. The remaining directed graph is finite and balanced, so its edges decompose into closed directed trails with no repeated edge. One trail contains the fixed west edge of the root square, since the sites lie in the nonnegative quadrant. In a trail of length l, half the steps point up or left, by horizontal and vertical balance. An up step crosses an east adjacency from a good site to a nongood child; a left step crosses a north adjacency of the same kind. Every such child was tested and failed, because all its parents were processed earlier. Each child has at most two parents, so this trail specifies at least l/4 distinct failed sites.

There are at most 4^l trails of length l starting with the fixed oriented root edge. For each candidate, its up and left edges determine the outside child sites; restricting to edge-distinct trails preserves the preceding multiplicity bound. Equation (60) and a union bound show that the probability of a finite good set is at most the sum in (50), which is less than one.

Thus with positive conditional probability there are infinitely many good sites. Their layers, hence their time coordinates, are unbounded. Each good mark was reached by an actual open path from the wired finite seed at its test, and later reveals do not change those states. The seed therefore has an infinite open component. Removing the synthetic source leaves an infinite cluster from one of its finitely many wired vertices. The initialization event had positive probability, so this conclusion also has positive probability in the unconditioned p' law.

Finally, the chosen parameters satisfy the two numerical hypotheses. They give \eta_0\le\kappa and

The remaining hypothesis is exactly (50).□

Proof of Theorem 1.1. The reduction in Section 2 permits us to work with a simple graph. By Lemma 2.1, its uniform exponential growth rate exists. If this rate is greater than one, Theorem 2.2 applies. Otherwise the graph has subexponential growth.

In this remaining case, if (4) holds, Theorem 5.1 excludes critical percolation. If it does not hold, (5) holds along an unbounded sequence. Proposition 7.2 supplies the group action required by Theorem 7.1, which again excludes critical percolation when \pc<1. Thus every fixed vertex has probability zero of belonging to an infinite critical cluster. The countable union over vertices proves the almost-sure assertion.□

Proof. The graph is infinite, connected, locally finite, and transitive. We verify \pc<1 by a planar boundary count on a coordinate copy of \Z^2. If its origin cluster is finite, the dual edges crossing its edge boundary contain a simple cycle surrounding the origin; all crossed primal edges are closed. To see the existence of such a cycle, the dual boundary has even degree at every vertex and decomposes into simple cycles. The positive horizontal ray from the origin crosses the whole boundary an odd number of times, so one cycle crosses this ray oddly. A closed cycle crosses the whole horizontal line evenly, and hence also crosses the negative ray.

A cycle of length n therefore has a positive-ray crossing at distance less than n from the origin. Choosing that crossing, an orientation, and a nonbacktracking continuation bounds the number of candidates by 2n3^n. Independence bounds the probability that the origin cluster is finite by

For p<1 sufficiently close to one this sum is less than one, so planar percolation occurs with positive probability. The same configuration is a subgraph of \Z^d, proving \pc(\Z^d)<1. Theorem 1.1 now applies.□