On chemical distances and shape theorems in percolation models with longrange correlations
Abstract
In this paper we provide general conditions on a one parameter family of random infinite subsets of to contain a unique infinite connected component for which the chemical distances are comparable to the Euclidean distance. In addition, we show that these conditions also imply a shape theorem for the corresponding infinite connected component.
By verifying these conditions for specific models, we obtain novel results about the structure of the infinite connected component of the vacant set of random interlacements and the level sets of the Gaussian free field. As a byproduct we obtain alternative proofs to the corresponding results for random interlacements in [8], and while our main interest is in percolation models with longrange correlations, we also recover results in the spirit of [2] for Bernoulli percolation.
Finally, as a corollary, we derive new results about the (chemical) diameter of the largest connected component in the complement of the trace of the random walk on the torus.
Percolation was introduced in [7] as a mathematical model of a porous medium, where the physical space is modeled by the lattice , and the pure substance is described as a random subset of . A central question is to understand physical properties of , and how universal these properties are for various distributions of . Mathematically speaking, what can be said about the connectivity properties and the geometry of the subgraph of spanned by ? In this paper we consider the general situation when the set has a unique infinite connected component which covers a positive fraction of . We define the chemical distance of to be the length of the shortest nearest neighbor path connecting and in , and we want to understand when the longscale behavior of the resulting random metric space is similar to that of the underlying space .
In the case of supercritical Bernoulli percolation (when every vertex of is in with probability independently of each other), [2, Theorem 1.1] asserts the existence of a constant such that the probability that the chemical distance of is greater than decays exponentially as . Using this control on chemical distances as well as Kingman’s subadditive ergodic theorem one can deduce a shape theorem which states that the chemical ball of radius in , rescaled by , converges almost surely with respect to the Hausdorff distance to a deterministic compact convex set of as (see, e.g., [11, Corollary 5.4]).
In this paper we extend the shape theorem from the supercritical Bernoulli setting to a general class of correlated percolation models, by proving novel results about chemical distances in these models. In our setup, we deal with a oneparameter family of probability measures (describing the law of at different densities) satisfying the following conditions:

P1: spatial ergodicity;

P2: stochastic monotonicity in ;

P3: weak decorrelation for monotone events;

S1: local uniqueness of ;

S2: continuity of the density of in ;
see Section 1 for the rigorous definitions and our general results Theorem 1.3 (which states that chemical distance on is comparable to Eucledian distance) and Theorem 1.5 (the shape theorem).
As we will show, the above conditions are general enough to be satisfied by many models, including random interlacements, the vacant set of random interlacements, and the level sets of the Gaussian free field (see Sections 2.2, 2.3, and 2.4, respectively). In our context, the last two models are particularly challenging since, in contrast to random interlacements, they exhibit percolation phase transitions. For the time being we cannot deal with their entire supercritical phases. However, our framework allows us to identify the only condition that is missing: as soon as S1 is extended up to criticality, our results will also hold for the entire supercritical phases. Let us also emphasize here that the above models give rise to random subsets of with polynomial decay of correlations, but still they satisfy the weak decorrelation condition P3, as we show in Sections 2.2, 2.3, and 2.4.
Historically, the asymptotic linear behaviour of chemical distances along rays in supercritical Bernoulli percolation was proved for all and in [13, (5.5)]. In order to deduce the shape theorem, one also needs a uniform control of the chemical distances in large balls: the exponentially decaying bound (for all ) of [2, Theorem 1.1] improved the polynomially decaying bound (for sufficiently high ) of [12, Lemma 2.8]. Corresponding properties of the chemical distance on the random interlacement at level have recently been derived in [8, Theorems 1.1 and 1.3]. However, the techniques of [8] heavily rely on the specific connectivity properties of , and in particular, the question of whether these results hold for the vacant set of random interlacements also had remained unsolved (and similarly for the level sets of Gaussian free field). In addition to answering these questions positively, our method also provides a general, model independent approach. This allows for a possible application our results to other percolation models by checking the conditions P1 – P3 and S1 – S2 in order to derive chemical distance results and shape theorems for them. In this context, it would for example be interesting to see whether the random cluster model (see [15] for a reference) satisfies all of the above conditions.
Another potential advantage of our general framework is that it seems to capture the key properties (i.e., P1 – P3 and S1 – S2) of a dependent percolation model which imply that the geometry of is similar to that of . In particular, recent progress indicates that our conditions imply that simple random walk on behaves similarly to random walk on , see Remark 1.7 for further discussion.
Finally, using a connection between random interlacements and random walk on the discrete torus, we obtain new results about the (chemical) diameter of the giant connected component in the complement of the random walk trace (see Section 2.5).
1 Model and results
We consider a one parameter family of probability measures , , on the measurable space , , where the sigmaalgebra is generated by the canonical coordinate maps , (i.e., for and ).
For any , we define
We view as a subgraph of in which the edges are drawn between any two vertices of within distance from each other. (For , the norm of is defined in the usual way by .) We denote by the subset of vertices of which are in infinite connected components of .
In this paper we will focus on connectivity properties of . We will prove that under certain conditions (see P1 – P3 and S1 – S2) on the family of probability measures , , the graph is connected and “looks like” the underlying lattice . Roughly speaking, we show that on large scales the graph distance in behaves like a metric induced by a norm on .
We will now define conditions on the family , . After that we will state the main results (Theorems 1.3 and 1.5) of the paper. Particular examples of probability measures satisfying the conditions (and results) below will be given in Section 2. Note that our aim was to formulate our conditions in a general and flexible form, in order to facilitate the extension of the main results of this paper to other percolation models.
The numbers as well as the dimension are going to be fixed throughout the paper, and we omit the dependence of various constants on , , and .

For any , is invariant and ergodic with respect to the lattice shifts.
To state the next two conditions we need the following definition.

For any with , and any increasing event , . (Usually, this condition is referred to as stochastic monotonicity of .)
Conditions P1 and P2 are rather general and are satisfied by many families of probability measures. The condition P3 below is more restrictive than the above two. It states that , , satisfy a certain weak decorrelation inequality. For and , we denote by
the closed ball in with radius and center . (For , the norm of is defined by .) We write for .

Let be an integer. Let . For , let be decreasing events, and increasing events. There exist and such that for any integer and satisfying
(1.1) if , then
(1.2) and
(1.3) where is a real valued function satisfying
for all . (1.4)
Remark 1.1.
At first sight it may look like condition P3 is rather strong and asserts that the correlations should decay much faster than any polynomial ( for any ). However, the fact that we deal with different parameters and (and a very restricted class of events) allows for measures with polynomial decay of correlations to satisfy P3. Examples of such families of measures for are random interlacements and the level sets of the Gaussian free field, for which
We will discuss these examples in more details in Sections 2.2 – 2.4. In the literature, the idea behind the proof of inequalities of the form (1.2) and (1.3) is often referred to as “sprinkling”.
While P1 – P3 are general conditions on the family , , the next condition S1 pertains to the connectivity properties of . It can be understood as a certain local uniqueness property for macroscopic connected components in . Roughly speaking, this condition implies that with high probability, large enough boxes intersect exactly one connected component of with large diameter.
(1.5) 
In particular, in the case we recover the set of vertices of contained in infinite connected components of .

There exists a function such that
(1.6) and for all and , the following inequalities are satisfied:
and
(1.7)
It is not difficult to see that if the family , , satisfies S1, then for any ,
a.s., the set is nonempty and connected,  (1.8) 
and there exist and such that for all ,
(1.9) 
Moreover, using a standard covering argument, if the family , , is invariant under the lattice shifts and satisfies S1, then for any and , there exist and such that for all ,
(1.10) 
We omit the proof of (1.10) and refer the reader to the derivation of Proposition 1 from Lemma 13 in [28], where essentially the same statement is proved.
Our final condition S2 on the measures , , concerns the density of ,
(1.11) 

The function is positive and continuous on .
In fact, the positivity of already follows from (1.8), if we assume that , , are invariant with respect to lattice shifts and satisfy S1. Note that if we assume P2, then
is nondecreasing on . 
Remark 1.2.
Condition S2 is the price that we pay for asking for decorrelation inequalities only in the weak form of P3 (see the proofs of Lemmas 4.2 and 4.4). If the inequalities (1.2) and (1.3) in P3 were true for , then we would not need the assumption S2. However, as we discuss in Remark 1.1, there are many percolation models with longrange correlations for which (1.2) and (1.3) fail to hold with , but conditions P3 and S2 are still valid.
The main result of our paper is the following theorem. For , let denote the chemical distance (also known as the internal or graph distance) in between and , i.e.,
Here we use the usual convention , i.e., we set if and are in different connected components of .
Theorem 1.3 (Chemical distance).
Assume that the family of probability measures , , on , , satisfies the conditions P1 – P3 and S1 – S2. For any , there exist and such that for all ,
(1.12) 
where comes from condition S1 (see (1.6)).
Remark 1.4.
If a probability measure is invariant under the lattice shifts and satisfies S1, then using a union bound one can already derive a weak version of (1.12). Indeed, for any , there exist and such that for all ,
However, in order to prove (1.12), we need to quantify correlations in some way. In this paper we achieve this by assuming P3.
Using standard methods, we can deduce from Theorem 1.3 a shape theorem for balls of . For and , we denote by the ball in with center and radius , i.e.,
The shape theorem states that large balls in with respect to the metric after rescaling have an asymptotic deterministic shape.
Theorem 1.5 (Shape theorem).
Assume that the family of probability measures , , satisfies P1 – P3 and S1 – S2. Then for any there exists a convex compact set such that for each , there exists a almost surely finite random variable satisfying
Remark 1.6.
(i) The set preserves symmetries of In particular, if
is invariant with respect to the isometries of which preserve and , then so is .
(ii) Since , , satisfy P2, it follows that
for any with , .
We prove Theorem 1.5 in Section 8 using Theorem 1.3 and Kingman’s subadditive ergodic theorem [16] in a standard fashion.
Let us now describe the strategy for the proof of Theorem 1.3. In this description we will say that a path is “short” if its length is comparable to the distance of its endvertices. We will set up a general multiscale renormalization scheme, which involves the recursive definition of unfavorable regions on higher and higher scales. Our aim is to iteratively construct short nearest neighbor paths in : given a short path (not necessarily in ) which avoids the unfavorable regions on a given scale, we modify this path in a way that the resulting path (still not necessarily in ) avoids the unfavorable regions on the previous scale as well. We choose our scales to grow faster than geometrically in order to achieve an upper bound on the length of the iteratively constructed path which is uniform in the number of iterations. Our definition of the favorable region on the bottom scale implies (due to S1) that such region contains a unique macroscopic connected component which is locally connected to the macroscopic connected components of all the neighboring favorable regions. By “glueing” such connected components together, we are able to locally modify short paths (not necessarily in ) that avoid unfavorable regions on the bottom scale to obtain short nearest neighbor paths in . The weak decorrelation inequalities of P3 allow us to set up a renormalization scheme in which unfavorable regions on higher scales become very unlikely. This is a tricky part, since we should be satisfied only with monotone events (note here that the local uniqueness event in the probability of inequality (1.7) is not monotone!) and cope with different parameters ( and ) in the decorrelation inequalities. All in all, favorable regions on high scales are likely and allow for short paths in . We use this conclusion to define an event such that (a) implies the event on the lefthand side of (1.12) and (b) is at least .
Remark 1.7.
It is natural to ask whether the conditions P1 – P3 and S1 – S2 are sufficient for obtaining finer results about the structure of , e.g., quenched Gaussian bounds on the transition kernel of a simple random walk on and a quenched invariance principle for the walk. In the case of Bernoulli percolation, the corresponding Gaussian bounds were proved in [3] (see also [19] for a partial result) using extensively techniques and results of [2], and the quenched invariance principle was subsequently proved in [31] for and in [5, 20] for all using the results of [3]. Techniques of the above papers heavily rely on tools valid only for weakly dependent models, such as the LiggettSchonmannStacey theorem [18], and are not applicable even to the specific models treated in Sections 2.2–2.4. We believe that the multiscale renormalization scheme developed in this paper will find applications in the proof of the above questions not only for specific examples of models, but in the full generality of assumptions P1 – P3 and S1 – S2. In fact, the quenched invariance principle for random walk on under assumptions P1 – P3 and S1 – S2 has been recently proved in [26]. The proof of [26] is based on a careful analysis of our renormalization scheme and our main result Theorem 1.3. Also, the recent preprint [21] takes advantage of our setup and main result Theorem 1.3 in order to derive quenched large deviations for simple random walk on the infinite connected component
The rest of the paper is organized as follows.
In Section 2 we give applications of our main results by demonstrating particular models in which the conditions P1 – P3 and S1 – S2 are satisfied. Our main focus is on the models for which only weak decorrelation inequalities of the form (1.2) and (1.3) are available. In particular, in Section 2.2 we show that our results give an alternative approach to the results of [8] for random interlacements, in Section 2.3 we show that our results hold for the vacant set of random interlacements in a (sub)phase of the supercritical parameters, and in Section 2.4 we show that the level sets of the Gaussian free field fit into our setup for a (sub)phase of the supercritical parameters. The results of Sections 2.3 and 2.4 are new. Finally, in Section 2.5 we apply results of Section 2.3 to obtain new results about the (chemical) diameter of the giant connected component in the complement of the random walk trace on the torus.
In Section 3 we define the multiscale renormalization scheme in an abstract setting. We define the notion of unfavorable regions and state conditions under which the higher scale unfavorable regions are unlikely.
In Section 4 we define the connectivity patterns of favorable regions on the bottom scale of our scheme, bringing into play two families of events of high probability, one increasing and one decreasing.
In Section 5 we use the events from Section 4 and the notion of favorable/unfavorable regions from Section 3 to define good and bad regions on all scales. We then describe explicitly how to modify a path through a good region on one scale to obtain a path through a good region on a lower scale without increasing its length by too much. This gives us one iteration in the construction of short paths in .
In Section 7 we prove the main result of Section 3 (see Theorem 3.1) verifying the conditions under which high scale regions are favorable with very high probability. We use the weak decorrelation inequalities to prove that a good upper bound on the probability of unfavorable events on a certain scale results in an even better bound on the next scale.
In Section 8 we prove Theorem 1.5 using Theorem 1.3 and Kingman’s subadditive ergodic theorem [16] in a standard fashion.
Throughout the paper, , , denote the canonical basis in . Constants are denoted by and . Their values may change from place to place. We omit the dependence of constants on , , and , but reflect the dependence on other parameters in the notation.
2 Applications
In this section we give a number of examples for which our conditions and results hold. In particular, we show that Theorems 1.3 and 1.5 hold for

the vacant set of random interlacements at level in the (nonempty) regime of socalled “local uniqueness”, which is believed to coincide with the whole supercritical phase (see Section 2.3),

the level sets of the Gaussian free field, also in the (nonempty) regime of local uniqueness (see Section 2.4).
The results in Sections 2.3 and 2.4 are new, and in particular, they cannot be derived using the techniques of [8] (see Remark 2.1 for further discussion). Let us also point out that the above models (a), (b) and (c) give rise to random subsets of with polynomial decay of correlations, but still they satisfy the strong concentration bound (1.12).
In Section 2.5 we apply the results of Section 2.3 to study the (chemical) diameter of the largest connected component in the complement of the trace of random walk on a discrete torus.
2.1 Bernoulli percolation
Bernoulli site percolation with parameter on , , satisfies all the conditions P1 – P3 and S1 – S2 (see, e.g., [14]). In this case is just the product measure on with .
2.2 Random interlacements
Random interlacements at level on , , is a random subset of , which arises as the local limit as of the set of sites visited by a simple random walk on the discrete torus , , when it runs up to time , see [33, 38]. The distribution of is determined by the equations
(2.1) 
where denotes the discrete capacity of . For any , is an infinite almost surely connected random subset of (see [33, (2.21)]) with polynomially decaying correlations
(2.2) 
(see [33, (1.68)]). Geometric properties of random interlacements have been extensively studied in the last few years (see [8, 17, 24, 25, 27, 28, 29]).
Remark 2.1.
The fact that the conclusions of Theorems 1.3 and 1.5 hold for the random interlacements at level has been recently established in [8, Theorems 1.3 and 1.1]. The key idea in the proofs of [8] is a certain refinement of the strategy developed in [27], which crucially relies on the fact that for any finite the random set can be generated as the union of independent random walk traces on , see [33, (1.53)]. The goal of this section is to observe (based on earlier results about random interlacements) that the laws of satisfy conditions P1 – P3 and S1 – S2. As a result, we obtain an alternative, model independent approach to the results of [8].
Theorem 2.2.
Remark 2.3.
Theorem 1.3 applied to the distribution of gives a weaker result than [8, Theorem 1.3], since the bound on the righthand side of (1.12) is not as good as the stretched exponential bound in [8, Theorem 1.3]. Nevertheless, this weaker bound is still sufficient for us to deduce Theorem 1.5, thus giving an alternative proof of [8, Theorem 1.1].
Proof of Theorem 2.2.
The fact that the distributions of , , satisfy condition P3 for any given follows from the more general decoupling inequalities [34, Theorem 2.1] applied to the graph (see also [34, Remark 2.7(1)]). We will use the notation introduced in [34, Section 2]. We take in (1.1). Our choice of parameters in [34, Theorem 2.1] is the following:
We also use the notation instead of here. Note that with the above choice of parameters we have and (since and ). In [34, Theorem 2.1], the inequality is required, so we need to choose . With the above choice of parameters, and satisfy condition (2.7) of [34, Theorem 2.1] for all (for some suitably big ), so (1.2) and (1.3) immediately follow from [34, (2.8) and (2.9)] with the function , thus the distributions of , indeed satisfy condition P3.
By [33, (2.21)], for any , is an almost surely connected infinite subset of , in particular we have (see (1.5)) for any . The distributions of , , satisfy S1 by [28, Proposition 1], and S2 by (2.1) (since is a positive and continuous function of ).
We have checked that the distributions of satisfy P1 – P2 and S1 – S2 for all , and P3 for (and any given ). The proof of Theorem 2.2 is complete.
Remark 2.4.
Property P3 can also be derived using the recent result of [23, Theorem 1.1].
∎
2.3 Vacant set of random interlacements
The vacant set of random interlacements at level in dimension is defined as the complement of random interlacements at level :
(2.3) 
In particular, it follows from (2.1) that the distribution of is determined by the equations
and it follows from (2.2) that the correlations in decay polynomially.
In the same way as random interlacements, the vacant set at level arises as the local limit as of the set of sites not visited by a simple random walk (we call it the vacant set, too) on the discrete torus , , when it runs up to time . In fact, the connection between the vacant sets of random interlacements and a simple random walk on is in terms of a strong coupling of [37, Theorem 1.1]. This coupling provided a powerful tool to study the fragmentation of by a simple random walk using existing results about the geometry of . In particular, it was shown in [37] that the fragmentation question is intimately related to the existence of a nontrivial phase transition in for : there exists such that

for any , almost surely, all connected components of are finite, and

for any , almost surely, contains an infinite connected component.
The fact that was proved in [33], and the positivity of was established in [33] when , and later in [32] for all . It is also known (see [35]) that if there exists an infinite connected component in , then it is almost surely unique.
In this section we focus on the supercritical phase of (regime (ii) above). More specifically, we would like to derive conclusions of Theorems 1.3 and 1.5 for the vacant set . While it would be desirable to obtain results for all , our understanding of the supercritical phase is not yet good enough to do so. In Theorem 2.5 we prove that there exists such that the conclusions of Theorems 1.3 and 1.5 hold for with . We believe that (see Remark 2.6). Even in the present form, the result of Theorem 2.5 below is new for any choice of dimension and level .
Theorem 2.5.
Proof of Theorem 2.5.
For , let denote the distribution of . Recall from (2.3) that for any , . From this and Theorem 2.2 it is immediate that the family , , satisfies conditions P1 and P2, and the family , , satisfies condition P3 for any .
Let be the largest such that the family , , satisfies condition S1. It follows from (1.8) that . The positivity of for all follows from the main result of [9] (for , it also follows from [36, (1.2) and (1.3)]).
Finally, the family , , satisfies condition S2 by [35, Corollary 1.2].
We have checked that the distributions of satisfy P1 – P2 for , P3 for (and any given ), S1 for (with ), and S2 for . Since , the proof of Theorem 2.5 is complete. ∎
Remark 2.6.
Assumption S1 is satisfied by Bernoulli percolation in the whole supercritical phase (see e.g. [14, (7.89),(8.98)]). Thus it is reasonable to conjecture that , i.e., that the distributions of satisfy S1 for all . The verification of this conjecture would in particular imply that the conclusions of Theorems 1.3 and 1.5 hold for for any .
2.4 Level sets of the Gaussian free field
The Gaussian free field on , , is a centered Gaussian field under the probability measure with covariance , for all , where denotes the Green function of the simple random walk on . The random field exhibits longrange correlations, since decays like as .
For any , we define the excursion set above level as
(2.4) 
We view as a random subgraph of . For any , there exists such that

for any , almost surely contains a unique infinite connected component, and

for any , almost surely all the connected components of are finite.
The finiteness of was established in [6] when , and later in [30] for all . The nonnegativity of was shown in [6], and the uniqueness in [30, Remark 1.6].
In this section we show that the excursion set of the Gaussian free field satisfies the assumptions and results of this paper in a certain subregime of the supercritical phase . The relation between and is discussed in Remark 2.9.
The main result of this section is the following theorem.
Theorem 2.7.
Proof.
The assumption P1 is satisfied by , , see the discussion above [30, Lemma 1.5].
The family , , satisfies P2, since the inclusion holds for all by (2.4).
The fact that the distributions , , satisfy P3 follows from Lemma 2.8 below.
Recall that denotes the canonical sigmaalgebra on , and denote by the canonical sigmaalgebra on . For an event in or , we denote by the indicator of . For any and , we define the event by
(2.5) 
Lemma 2.8.
Let . Let and be integers. Let . For , let be decreasing events, and increasing events. Let . There exist and such that if
then
(2.6) 
and
(2.7) 
The proof of Lemma 2.8 is similar to that of [30, Proposition 2.2], but some new ideas are needed here since the latter is not strong enough in order to imply P3 — see also the issue discussed in [30, Remark 2.3 (3)]. We postpone the proof of Lemma 2.8 to after finishing the rest of the proof of Theorem 2.7. Note that one could use the more recent decoupling inequality of [22] to obtain P3 — however, for selfcontainedness we include Lemma 2.8 and its short proof.
To see that Lemma 2.8 implies that P3 is satisfied by the family , , note that for any such that , we have that . In particular, we get that . It is now immediate from Lemma 2.8 that , satisfies P3 for any choice of and .
We proceed with S1. Let be the smallest such that the family , , satisfies condition S1. Define and note that (i.e., ) follows from (1.8) and the definition of . We will now prove that (i.e., ).
We say that are connected in if there exists such that , and for all . Essentially the same proof as the one of [30, (2.64)] implies that for any there exists and constants and such that
Observing that the laws of and are the same under , we immediately obtain that the connected components in the complement of are very small for any . Then, a standard argument based on the connectedness of boundaries (see, e.g., the proof of [9, Corollary 3.7]) implies that the distribution of satisfies S1 for any . Let . For any , we have that . Therefore, the family , satisfies condition S1. In particular, .
Remark 2.9.
Similarly to Remark 2.6, it is reasonable to conjecture that , i.e., that the distribution of satisfies S1 for all . As soon as this conjecture is verified, the conclusions of Theorems 1.3 and 1.5 extend to the excursion set for any parameter in the supercritical regime . Proving that may be quite hard. A reasonable start would be to prove that . A strict inequality, i.e., , would be even better, but at the moment there is no rigorous argument even for the statement that for all . It is only known that when the dimension is large, see [30, Theorem 3.3]. Extending the result of [30, Theorem 3.3] to all dimensions is thus another interesting open problem, see [30, Remark 3.6 (3)].
Proof of Lemma 2.8.
Let for . Let be the event that
By [30, (2.63)], there exists and constants and such that for all . From now on we fix such and write for . In order to prove (2.7) we only need to show that there exists a constant such that with defined as
(2.8) 
for every and every pair , of increasing events in satisfying the assumptions of Lemma 2.8, we have
(2.9) 
(Here, to simplify notation, we replaced of (2.7) by , and of (2.7) by , hopefully without confusion.)
Denote by the union of and the set of vertices of connected to by a simple path in . Note that if occurs, then
Denote by the set of subsets of that can arise as a realization of with positive probability. We start proving (2.9) by writing
(2.10) 
Note that the event is measurable with respect to the subsigmaalgebra of generated by , where
(2.11) 
According to [30, Remark 1.3], for every there exists a probability measure on such that is a centered Gaussian field under with for all , and
(2.12) 
where , is given by