Graph distances in scale-free percolation: the logarithmic case

Abstract

Scale-free percolation is a stochastic model for complex networks. In this spatial random graph model, vertices $x,y\in\mathbb{Z}^d$ are linked by an edge with probability depending on independent and identically distributed vertex weights and the Euclidean distance $|x-y|$ . Depending on the various parameters involved, we get a rich phase diagram. We study graph distance and compare it to the Euclidean distance of the vertices. Our main attention is on a regime where graph distances are (poly-)logarithmic in the Euclidean distance. We obtain improved bounds on the logarithmic exponents. In the light tail regime, the correct exponent is identified.

1. Introduction

1.1. The model

We study scale-free percolation, which we henceforth abbreviate as SFP. This is a stochastic model for real networks such as social networks, biological networks, the internet, etc. that was introduced in [9]. Many real networks share ubiquitous features such as scale-free degrees and small-world behaviour. Our model, SFP, is an infinite spatial random graph model that exhibits these features; it is embedded into the hypercubic lattice $\mathbb{Z}^d$ and shows geometric clustering. Closely related models are based on point processes rather than the fixed grid structure of $\mathbb Z^d$ , and such models have been studied on finite and infinite domains. We discuss these variants in Section 1.4.

We now describe the model in detail. We consider the lattice $\mathbb{Z}^d$ with fixed dimension $d\ge1$ and construct a locally finite random subgraph of the complete graph on the vertex set $\mathbb{Z}^d$ . Recall that a graph is called locally finite if all its vertices have finite degrees. To each vertex $x\in \mathbb{Z}^d$ , we assign an independent and identically distributed (i.i.d.) weight $W_x$ which follows a power-law distribution with parameter $\tau-1$ ( $\tau>1$ ), i.e. $\mathbb{P}(W_x\geq w)= w^{-(\tau-1)}$ , $ w\geq 1$ . Conditioning on these weights, we declare an edge $\{x,y\}$ to be open independently of the status of other edges with probability

(1.1) \begin{align}p_{x,y}=1-\exp\!\bigg({-}\lambda\frac{W_xW_y}{|x-y|^{\alpha}}\bigg),\end{align}

where $|\cdot|$ denotes the Euclidean norm and $\alpha, \lambda>0$ are further parameters of the model. We write $x\sim y$ if the edge $\{x,y\}$ is open. The object of interest in the present study is the subgraph induced by the open edges; we call its connected components clusters.

Scale-free percolation indeed generates scale-free networks in the sense that the degrees of vertices follow a power-law distribution with tail exponent

(1.2) \begin{equation}\gamma=\alpha(\tau-1)/d.\end{equation}

That is,

\begin{equation*}\mathbb{P}(D_x\geq k)=k^{-\gamma}\ell(k),\quad k\in\mathbb{N}, \end{equation*}

where $D_x$ is the degree of $x\in \mathbb{Z}^d$ and $\ell$ is slowly varying at infinity, cf. [9].

The focus of the present paper is on graph distances. Recall that the graph distance between two vertices is defined as the length of a shortest open path connecting them. If the vertices are in different clusters (and hence such open paths do not exist), then the graph distance is $\infty$ . Graph distances in real networks, in particular social networks, have been the focus of network research since Milgram’s experimental discovery of the small-world effect (casually phrased as ‘six degrees of separation’), and have also been investigated theoretically since then, e.g. [17, 18].

On finite networks, say with N vertices, ‘small world’ means that the graph distance between two points is much shorter than a regular structure would suggest, e.g. $(\!\log N)^{O(1)}$ as $N\to\infty$ . Our network is infinite, and we therefore give a different interpretation to the small-world effect. We call an infinite subgraph $\mathcal C\subset\mathbb{Z}^d$ a small-world graph if the graph distance D(x, y) on $\mathcal C$ is much smaller than the Euclidean distance, i.e. if

(1.3) \begin{equation} D(x,y)=\big(\!\log|x-y|\big)^{O(1)}\qquad \text{as $|x-y|\to\infty$}.\end{equation}

For graph distances in scale-free percolation, a rich phase diagram has been established in the literature: conditional on two points, x and y say, to be in the (unique) infinite component, we get that, with high probability (as $|x-y|\to\infty$ ),

• if $\gamma\le1$ then $D(x,y)\le 2$ , cf. [15];

• if $\alpha<d$ , then $D(x,y)\leq \lceil d/(d-\alpha) \rceil$ , cf. [15];

• if $\gamma \in (1,2)$ and $\alpha > d$ , then $D(x,y)=\frac{2}{|\log\!(\gamma-1)|}\log\log|x-y|$ , cf. [9, 22];

• if $\gamma>2$ and $\alpha>2d$ , then $D(x,y)\gtrsim |x-y|$ , cf. [10, 19].

This behaviour (together with our new results) is summarized in Fig. 1. The results in the first three cases are referred to as the ‘ultra-small-world’ phenomenon, because the asymptotics are of smaller order than the requirements of (1.3). In these regimes, shortest paths are typically formed by vertices that have the highest weight in a certain neighbourhood (locally dominanting vertices or hubs). In contrast, for $d<\alpha < 2d$ and $\gamma >2$ , the weights are more homogeneous, and it is not sufficient to consider only dominant vertices to find the shortest paths. In this regime, there is a fine interplay between weights and spatial positions of various vertices, which leads to (poly-)logarithmic upper and lower bounds on graph distances. The aim of this paper is to identify the right logarithmic power, thereby completing the phase diagram.

Figure 1. Graph distances in different regimes of scale-free percolation. The shaded regions are those we are interested in. The areas (a), (b), and (c) represent our improved bounds established in Theorem 1.1.

At the phase boundaries ( $\gamma=1$ and $\gamma=2$ ) we expect that the graph distances depend on the precise tail behaviour of the connectivity function in (1.1), so that any universality is lost.

1.2. Main results

Before stating the main results, we first introduce some parameters:

(1.4) \begin{align} &\alpha_1\,:\!=\,\alpha \wedge \frac{\alpha(\tau-1)}{2}=\alpha\wedge\frac{\gamma d}2, \qquad \alpha_2 \,:\!=\,\alpha \wedge (\alpha(\tau-1)-d)=\alpha\wedge (\gamma-1)d,\end{align}

(1.5) \begin{align} &\Delta\,:\!=\,\frac{\log 2}{\log\!(2d/{\alpha})},\qquad\Delta_1\,:\!=\,\frac{\log 2}{\log\!(2d/{\alpha_1})},\quad \Delta_2\,:\!=\,\frac{\log 2}{\log\!(2d/{\alpha_2})}.\end{align}

Here, $x\wedge y$ means the minimum of x and y. If $\gamma$ in (1.2) is larger than 2, then $d<\alpha_1\leq\alpha_2\leq\alpha<2d$ . As a consequence, $1<\Delta_1\leq\Delta_2\leq\Delta$ .

Deijfen et al. showed in [9] that, for $d<\alpha<2d$ and $\gamma>1$ , if $\mathbb{P}(W=0)<1$ then there exists a critical value $\lambda_\textrm{c}\in(0,\infty)$ such that for $\lambda>\lambda_\textrm{c}$ there exists a unique infinite cluster. We thus may condition on two vertices x and y being in the same infinite cluster.

Theorem 1.1. For scale-free percolation with parameters $\lambda>\lambda_\textrm{c}$ , $\gamma>2$ , and $d<\alpha<2d$ , we have, for any $\varepsilon>0$ ,

\begin{equation*}\lim_{|x-y|\to \infty}\mathbb{P}\big((\!\log |x-y|)^{\Delta_1-\varepsilon}\leq D(x,y)\leq (\!\log |x-y|)^{\Delta_2+\varepsilon} \mid x,y\in\mathcal{C}_{\infty}\big)=1.\end{equation*}

Depending on the values of $\gamma$ and $\alpha$ , the various minima in (1.4) give rise to three different regimes. These are depicted in Fig. 1. Writing $\mathcal{C}_{\infty}$ for the unique infinite cluster in the graph, we get:

1. (a) for $\gamma>2$ , $\alpha(\tau-2)<d$ , and arbitrary $\varepsilon>0$ ,

   \begin{equation}\nonumber \lim_{|x-y|\to \infty}\mathbb{P}\big((\!\log |x-y|)^{\Delta_1-\varepsilon}\leq D(x,y)\leq (\!\log |x-y|)^{\Delta_2+\varepsilon} \mid x,y\in\mathcal{C}_{\infty}\big)=1;\end{equation}

2. (b) for $\tau<3$ , $\alpha(\tau-2)\geq d$ , and arbitrary $\varepsilon>0$ ,

   \begin{equation}\nonumber \lim_{|x-y|\to \infty}\mathbb{P}\big((\!\log |x-y|)^{\Delta_1-\varepsilon}\leq D(x,y)\leq (\!\log |x-y|)^{\Delta+\varepsilon} \mid x,y\in\mathcal{C}_{\infty}\big)=1;\end{equation}

3. (c) for $\tau\geq 3$ and arbitrary $\varepsilon>0$ ,

   \begin{equation}\nonumber \lim_{|x-y|\to \infty}\mathbb{P}\big((\!\log |x-y|)^{\Delta-\varepsilon}\leq D(x,y)\leq (\!\log |x-y|)^{\Delta+\varepsilon} \mid x,y\in\mathcal{C}_{\infty}\big)=1.\end{equation}

Note that here the upper bounds in (b) and (c) are from [10].

Despite the improvements in both the upper and lower bounds, the reader may observe that there is still a gap between them in cases (a) and (b) in our result. Therefore, it remains open as to what the correct exponent is. The main difficulty in closing the gap between the upper and lower bounds is that we do not have a precise estimate for the probability of a path being open in scale-free percolation. Lemma 2.2 gives a nice upper bound. However, in view of Proposition 3.2, it appears that this bound is not optimal for $\tau<3$ . As shown in Proposition 3.2, the actual asymptotics of the probability of a path being open in SFP are heterogeneous in the exponents of edges, which poses a great difficulty.

In fact, our methods also apply to more general forms of connection probabilities than (1.1). We return to this observation in Remark 3.1. If we make the extra assumption that additionally all nearest-neighbour edges are open, then a comparison with long-range percolation (explained in the following paragraph) gives the following improvement to (b) and (c) above: there exists $C>0$ such that

(1.6) \begin{equation} \lim_{|x-y|\to \infty}\mathbb{P}\big(D(x,y)\leq C(\!\log |x-y|)^{\Delta}\big)=1.\end{equation}

Note that the extra assumption ensures that $x,y\in\mathcal{C}_{\infty}$ .

1.3. Comparison with long-range percolation

Before we proceed to the proofs of the results, we first introduce a related (though easier) model named long-range percolation. Our analysis of scale-free percolation is crucially based on techniques developed for long-range percolation.

Long-range percolation (henceforth LRP) is also defined on the lattice $\mathbb{Z}^d$ for fixed dimension $d\geq 1$ . Independently of all the other edges, the edge $\{x,y\}$ is open with probability $p^{\scriptscriptstyle \rm LRP}_{xy}$ . A typical choice of $p^{\scriptscriptstyle \rm LRP}_{xy}$ is

\begin{equation*}p^{\scriptscriptstyle \rm LRP}_{xy}=1-\exp\!\bigg({-}\frac{\lambda}{|x-y|^{\alpha}}\bigg).\end{equation*}

Note that $p^{\scriptscriptstyle \rm LRP}_{xy}$ is equal to $p_{xy}$ for scale-free percolation (as defined in (1.1)) if $W_x\equiv1$ or $\tau=\infty$ .

Biskup et al. studied the graph distances in long-range percolation and obtained sharp results.

Theorem 1.2. ([3, 4, 20].) Consider the long-range percolation with connection probability $\{p_{xy}\}$ such that

(1.7) \begin{equation} \liminf_{|x-y|\to \infty}p^{\scriptscriptstyle \rm LRP}_{xy}|x-y|^{\alpha} >0 \end{equation}

for some $\alpha>0$ . If $d <\alpha <2d$ and a unique infinite open cluster exists, then, for all $\varepsilon>0$ , we have

\begin{equation*} \lim_{|x-y|\to \infty}\mathbb{P}\big(( \log |x-y|)^{\Delta-\varepsilon}\leq D(x,y) \leq (\!\log |x-y|)^{\Delta+\varepsilon} \mid x,y \in \mathcal{C}_{\infty}\big)=1. \end{equation*}

If, moreover, we have the stronger form of connection probability

\begin{align*} p^{\scriptscriptstyle \rm LRP}_{xy}=1-\exp\!\bigg({-}\frac{\lambda}{|x-y|^{\alpha}}\bigg), \end{align*}

and assume the existence of all nearest-neighbour edges, then there exist constants $C>c>0$ such that

\begin{equation*} \lim_{|x-y|\to \infty}\mathbb{P}\big(c( \log |x-y|)^{\Delta}\leq D(x,y) \leq C(\!\log |x-y|)^{\Delta}\big)=1. \end{equation*}

Trapman [20], moreover, identified the growth of the balls $\{x\in\mathbb{Z}^d\,:\, D(0,x)\le n\}$ for LRP with $d<\alpha<2d$ .

Now we can describe a coupling between LRP and SFP. To this end, we view the two models from another perspective: to each edge $\{x,y\}$ of the graph, we assign an i.i.d. Uniform[0, 1]-distributed random variable $U_{xy}$ . Then, for the scale-free percolation model, we consider for each edge $\{x,y\}$ the event

\begin{align*}A_{x,y}\,:\!=\,\bigg\lbrace U_{xy}\leq 1-\exp\!\bigg({-}\lambda\frac{W_xW_y}{|x-y|^{\alpha}}\bigg)\bigg\rbrace,\end{align*}

and we make the edge $\{x,y\}$ open whenever $A_{x,y}$ occurs. In the same way, for long-range percolation we consider the event

\begin{equation*}B_{x,y}\,:\!=\,\bigg\lbrace U_{xy}\leq 1-\exp\!\bigg({-}\lambda\frac{1}{|x-y|^{\alpha}}\bigg)\bigg\rbrace.\end{equation*}

We have thus constructed a coupling for the two models: since $W_x\geq 1$ for all $x\in \mathbb{Z}^d$ , we have

\begin{align*} 1-\exp\!\bigg({-}\lambda \frac{1}{|x-y|^{\alpha}}\bigg) \leq 1-\exp\!\bigg({-}\lambda \frac{W_x W_y}{|x-y|^{\alpha}}\bigg),\end{align*}

which implies $A_{x,y}\supseteq B_{x,y}$ , and thus scale-free percolation dominates long-range percolation in the sense that all the open edges in the LRP remain open in SFP. We therefore get that distances in LRP are an upper bound for distances in SFP, and in particular get the upper bound (1.6).

For the remaining regimes, there are many rigorous results about the graph distance D(x, y) as $|x-y|\to \infty$ . When $\alpha <d$ , [1] showed that D(x, y) is bounded by some (explicit) constant. When $\alpha> 2d$ , [2] showed that D(x, y) $\geq |x-y|$ . For the borderline case $\alpha=2$ for $d=1$ , [12] showed that $D(x,y)\approx |x-y|^{\delta}$ for some $\delta\in (0,1)$ .

1.4. Related work

Various aspects of scale-free percolation (also known as heterogeneous long-range percolation) have been investigated in the literature, both on the lattice $\mathbb{Z}^d$ [10, 15] and as a continuum analogue [8, 11], where vertices are given as a Poisson point process. The results in the present paper have been obtained on $\mathbb{Z}^d$ , but it appears that we do not make use of the lattice structure in any crucial way, so that analogue results should hold for a continuum version of the model. A continuum version of scale-free percolation on a finite domain (properly rescaled) is known a geometric inhomogeneous random graph; see [5, 6, 7].

It has been pointed out recently [13, 14] that (continuum) scale-free percolation, as well as many other random graph models, can be understood as special cases of the weight-dependent random connection models. In the language of [13], scale-free percolation corresponds to the weight-dependent random-connection model with a product kernel and polynomial profile function. Note that the parametrization in [13] is different; see in particular [13, Table 2].

For related recent work on spatial preferential attachment graphs we refer to [16].

1.5. Overview

We first prove the lower bound in Section 2. More precisely, we show that the probability that there exists a shorter path than the lower bound is negligible. We do this by estimating the path probability and counting the eligible paths using a so-called ‘hierarchy’ argument. In Section 3 we prove the upper bound with a double edge argument.

2. Proof of the lower bound

In order to prove the lower bound, we derive variants of Biskup’s arguments [3] in the setting of scale-free percolation. Similar to [3], we split the argument into three propositions. The key difference between SFP and LRP is that adjacent edges in the former model are only conditionally independent. We resolve this by adjusting the definition of a hierarchy and combine it with estimates from [9] to break up the dependence structure.

Definition 2.1. Given an integer $n\geq 1$ and distinct vertices $x,y\in \mathbb{Z}^d$ , we say that the collection $\mathcal{H}_n(x,y)=\{(z_{\sigma})\,:\,\sigma \in \{0,1\}^k, k=1,2,\dots,n;\ z_{\sigma}\in \mathbb{Z}^d\}$ is a hierarchy of depth n connecting x and y if

1. (i) $z_0=x$ and $z_1=y$ ;

2. (ii) $z_{\sigma 00}=z_{\sigma 0}$ and $z_{\sigma 11}=z_{\sigma 1}$ for all $k=0,1,\dots,n-2$ and all $\sigma \in \{0,1\}^k$ ;

3. (iii) for all $k=0,1,\dots,n-2$ and all $\sigma \in \{0,1\}^k$ such that $z_{\sigma 01} \neq z_{\sigma 10}$ , the edge $\{z_{\sigma 01},z_{\sigma 10}\}$ is open;

4. (iv) each edge $\{z_{\sigma 01},z_{\sigma 10}\}$ as specified in (iii) appears only once in $\mathcal{H}_n(x,y)$ ;

5. (v) for $z_{\sigma_1},z_{\sigma_2}$ in $\mathcal{H}_n(x,y)$ with $k\in\{0,1,\dots,n-1\} $ , $\sigma_1,\sigma_2\in \{0,1\}^{k+1}$ , and $\sigma_1\neq \sigma_2$ , we have $z_{\sigma_1}=z_{\sigma_2}$ if and only if there exists $\sigma \in \{0,1\}^k$ such that ${\sigma_1}={\sigma 0}$ and ${\sigma_2}={\sigma 1}$ . In this case, we call the vertices $z_{\sigma_1}$ and $z_{\sigma_2}$ degenerate, otherwise non-degenerate.

The vertices $(z_{\sigma})$ are called sites of the hierarchy $\mathcal{H}_n(x,y)$ .

In the toy example depicted in Fig. 2, we find two overlapping sites. For $z_{001} ({=}z_{0011})$ and $z_{0010}$ , there exists $\sigma=(0,0,1)\in \{0,1\}^3$ such that $z_{\sigma 1}=z_{\sigma0}$ . Therefore, this is a degenerate site in the sense of Condition (v). Similarly for $z_{010}$ and $z_{0101}$ .

Figure 2. A hierarchy of depth 4 with two degenerate sites $z_{001}$ and $z_{010}$ .

Remark 2.1. With only Conditions (i)–(iv), our definition would coincide with [3, Definition 2.1]. In addition, we impose Condition (v) to make sure that every element $(z_{\sigma}) \in \mathcal{H}_n(x,y)$ can be fitted into a vertex self-avoiding path connecting x and y. By adding an additional condition, we realise that the set of all hierarchies here is a subset of the hierarchies defined in [3], and this will be helpful when we count the eligible hierarchies, e.g. in (2.18).

The hierarchy $\mathcal{H}_n(x,y)$ is essentially a (random) subgraph of the complete graph with vertex set $\mathbb Z^d$ . Condition (iv) ensures that the number of open edges in this subgraph is at most $2^{n-1}$ , and Condition (v) guarantees that the degree of all vertices in $\mathcal{H}_n$ is no more than 2.

Since the shortest path connecting x and y is necessarily vertex self-avoiding, meaning that the weight of a single vertex appears at most twice in the path, we can estimate the probability of such a path by the Cauchy–Schwarz inequality.

Lemma 2.1. ([9, Lemma 4.3]) Let $x,y\in \mathbb{Z}^d$ be distinct. Then, for all $\delta>0$ , there exists a constant $C_{\delta}\,:\!=\,C(\delta, \lambda)>1$ such that

(2.1) \begin{equation}\mathbb{E}\Bigg[\bigg(\lambda\frac{W_xW_y}{|x-y|^{\alpha}}\wedge 1\bigg)^2\Bigg]^{1/2} \leq C_{\delta}|x-y|^{-\alpha_1+\delta},\end{equation}

where $\alpha_1$ is defined as in (1.4).

Proof. From the proof of [9, Lemma 4.3] we know that

\begin{equation*}\mathbb{E}\Bigg[\bigg(\lambda\frac{W_xW_y}{|x-y|^{\alpha}}\wedge 1\bigg)^2\Bigg] \leq C_1\!\left(1+\log |x-y|\right)|x-y|^{-2\alpha_1} \end{equation*}

for some constant $C_1\in (0,\infty)$ . Then, for all $\delta>0$ , we have

\begin{equation*}\lim_{r \to \infty}\frac{1+\log r}{r^{2\delta}}=0.\end{equation*}

Hence, there exists a constant $C_2>0$ such that $1+ \log r\leq C_2 r^{2\delta}$ for all $r >0$ . Then we choose $C_{\delta}\,:\!=\,\sqrt{C_1C_2} \vee 2$ as desired.

Remark 2.2. Actually, the estimation above can be further refined for $\tau>3$ . If $\tau>3$ , the weights $W_x$ and $W_y$ have finite variance. In this case, we can get rid of the $\delta$ in (2.1). On the other hand, since we can choose $\delta$ arbitrarily small, the refinement does not change our result. For our purpose, we choose $\delta$ small enough that $\alpha-\delta>d$ and $\alpha_1-\delta>d$ .

Now we estimate the probability that a path is open from above. Note that we call $\pi$ a path of length n if there exist $n+1$ distinct vertices $x_0,\dots,x_n\in \mathbb{Z}^d$ such that $\pi=(x_0,\dots,x_n)$ . We say that $\pi$ is open if all the edges $\{x_{i-1},x_i\}_{i=1,\dots,n}$ are open.

Lemma 2.2. ([9, Theorem 4.2]) Let $\pi\,:\!=\,(z_0,z_1,\dots,z_n) \in \big(\mathbb{Z}^d\big)^{n+1}$ be a path of length n. Then, for all $\delta>0$ , $\mathbb{P}(\pi\ is\ open)\leq \prod_{i=1}^{n}C_{\delta}|z_i-z_{i-1}|^{-\alpha_1+\delta}$ , where the constant $C_{\delta}$ is as in Lemma 2.1.

The proof of Lemma 2.2 can be found in the proof of [9, Theorem 4.2], which combines the Cauchy–Schwarz inequality with the alternating independence of the edges in the path. With Lemma 2.2, we immediately realise that SFP behaves similarly to LRP in the sense that they have similar upper bounds for the probability of a path, which also indicates that the lower bound of SFP might be treated similarly to LRP.

Definition 2.2. Let $x,y\in \mathbb{Z}^d$ be distinct, $\eta\in (0, \alpha_1/(2d))$ , and $n\geq 2$ . We define $\mathcal{E}_n=\mathcal{E}_n(\eta)$ as the event that every hierarchy $\mathcal{H}_n(x,y)$ of depth n connecting x and y such that

(2.2) \begin{equation}|z_{\sigma 01}-z_{\sigma 10}|\geq |z_{\sigma 0}-z_{\sigma 1}|(\!\log N)^{-\Delta_1}\end{equation}

holds for all $k=0,1,\dots,n-2$ , and all $\sigma \in \{0,1\}^k$ also satisfy the bounds

(2.3) \begin{equation}\prod_{\sigma \in \{0,1\}^k}|z_{\sigma 0}-z_{\sigma 1}|\vee 1\geq N^{(2\eta)^k} \quad \text{ for all }\ \ k=1,2,\dots,n-1,\end{equation}

where $N=|x-y|$ is the Euclidean distance between x and y.

With help of Lemma 2.2 we now can estimate the probability of the event $\mathcal{E}_n$ .

Proposition 2.1. Let $\eta\in (0, \alpha_1/(2d))$ . Pick $\delta>0$ so small that $\alpha_1-\delta-d>0$ and $\alpha_1-\delta\in (2d\eta, \alpha_1)$ ; then, there exists a constant $c_1>0$ such that, for all $x,y\in \mathbb{Z}^d$ with $N=|x-y|$ satisfying

\begin{align*} \eta^n\log N & \geq 2(\alpha_1-\delta-d),\\ \mathbb{P}(\mathcal{E}^{\textrm{c}}_{n+1}\cap \mathcal{E}_n) & \leq (\!\log N)^{c_1 2^n}N^{-(\alpha_1-\delta-2d\eta)(2\eta)^n},\\ \mathbb{P}(\mathcal{E}^{\textrm{c}}_2) & \leq (\!\log N)^{c_1}N^{-(\alpha_1-\delta-2d\eta)}.\end{align*}

We modify the proof of [3, Lemma 4.5] to fit our model.

Let $\mathcal{A}(n)$ be the set of all $2^n$ -tuples $(z_{\sigma})$ of sites (or hierarchies) such that (2.2) holds for all $\sigma\in \{\{0,1\}^k\,:\, k=0,1,\dots,n-1\}$ and (2.3) is true for $k=1,2,\dots,n-1$ but not for $k=n$ . Then

(2.4) \begin{equation}\mathbb{P}(\mathcal{E}^{\textrm{c}}_{n+1}\cap \mathcal{E}_n)\leq \sum_{(z_{\sigma})\in \mathcal{A}(n)}\mathbb{P}(\mathcal{H}_n(x,y) \text{ with sites }(z_{\sigma})).\end{equation}

Here, the event ‘ $\mathcal{H}_n(x,y) \text{ with sites }(z_{\sigma})$ ’ means that all the edges in this hierarchy with sites $(z_{\sigma})$ are open as in Definition 2.1(iii).

Now we fix one single hierarchy $\mathcal{H}_n(x,y)$ with sites $(z_{\sigma})$ and estimate its probability. Typically, a hierarchy consists of isolated edges, i.e. edges that do not share a common vertex. However, since we also allow degenerate vertices as in Definition 2.1(v), there might be adjacent edges in the hierarchy. Nevertheless, we can decompose one hierarchy into several disjoint connected components, as exemplified in Fig. 2. Condition (v) ensures that each of the connected components is an open path.

Example 2.1. Consider the toy example in Fig. 2. This hierarchy $\mathcal{H}_4(x,y)$ can be divided into five disjoint paths:

\begin{alignat*}{2} \pi_1 & = (z_{0110},z_{110},z_{001},z_{0001}), & \pi_2&=(z_{01},z_{10}),\\ \pi_3 & = (z_{1001},z_{1010}), \quad \pi_4=(z_{101},z_{110}), \quad & \pi_5&=(z_{1101},z_{1110}).\end{alignat*}

Now assume that the hierarchy $\mathcal{H}_n(x,y)$ can be divided into m disjoint open paths $\pi_i$ , $ i=1,2,\dots,m$ , with $\pi_i=(x_{i0},x_{i1},\dots,x_{im_i})$ and $x_{ij}\in (z_{\sigma})$ . Then, independence of edge occupation implies

\begin{align*}\mathbb{P}(\mathcal{H}_n(x,y) \text{ with sites }(z_{\sigma}))&= \mathbb{P}\bigg(\bigcap_{k=0}^{n-1}\bigcap_{\sigma\in \{0,1\}^k}\{z_{\sigma01}\sim z_{\sigma10}\}\bigg) \\&=\mathbb{P}\bigg(\bigcap_{i=1}^m \{\pi_i \text{ is open}\}\bigg)=\prod_{i=1}^m\mathbb{P}(\pi_i\text{ is open}),\end{align*}

where we rearrange the open edges in the hierarchy in the second step and use the fact that these open paths are vertex-disjoint and therefore independent in the last step. Further,

\begin{align*}\mathbb{P}(\mathcal{H}_n(x,y) \text{ with sites }(z_{\sigma}))&\leq \prod_{i=1}^m \prod_{j=1}^{m_i}C_{\delta}\left|x_{im_j}-x_{im_{j-1}}\right|^{-\alpha_1+\delta}\\&=\prod_{k=0}^{n-1} \prod_{\sigma \in \{0,1\}^k}\frac{C_{\delta}}{\left(\left|z_{\sigma01}-z_{\sigma10}\right|\vee 1\right)^{\alpha_1-\delta}},\end{align*}

where we apply Lemma 2.2 first and then bring the edges back in the original order again. In the last step we add the maximum with 1 to make sure that the denominator is not zero.

Likewise, we denote the ‘gaps’ in the hierarchy by $t_{\sigma}\,:\!=\,z_{\sigma 0}-z_{\sigma 1}$ , and $t_{\emptyset}\,:\!=\,x-y$ . With this notation, we rewrite condition (2.2) as

(2.5) \begin{align}|z_{\sigma 01}-z_{\sigma 10}|\geq |t_{\sigma}|(\!\log N)^{-\Delta_1}\end{align}

and condition (2.3) as

(2.6) \begin{align}\prod_{\sigma \in \{0,1\}^k}|t_{\sigma}|\vee 1\geq N^{(2\eta)^k}.\end{align}

Let $\mathcal{B}(k)$ be the set of all collections $(t_{\sigma})_{\sigma\in \{0,1\}^k}$ of vertices in $\mathbb{Z}^d$ such that (2.6) is true. Then (2.4) implies

\begin{equation*}\mathbb{P}(\mathcal{E}^{\textrm{c}}_{n+1}\cap\mathcal{E}_{n})\leq \left|\mathcal{B}^{\textbf{c}}(n)\right|\prod_{k=0}^{n-1}\Bigg(\sum_{(t_{\sigma})\in \mathcal{B}(k)}\prod_{\sigma\in \{0,1\}^k}C_{\delta}\bigg(\frac{(\!\log N)^{\Delta_1}}{|t_{\sigma}|\vee 1}\bigg)^{\alpha_1-\delta}\Bigg) .\end{equation*}

Note that for $k=0$ , we have $|t_{\emptyset}|=N$ . Hence, the estimation above can be written as

(2.7) \begin{equation}\left|\mathcal{B}^{\textrm{c}}(n)\right|\frac{(C_{\delta}(\!\log N)^{\Delta_1(\alpha_1-\delta)})^{2^n}}{N^{\alpha_1-\delta}}\prod_{k=1}^{n-1}\Bigg(\sum_{(t_{\sigma})\in \mathcal{B}(k)}\prod_{\sigma\in \{0,1\}^k}\frac{C_{\delta}}{\left(|t_{\sigma}|\vee 1\right)^{\alpha_1-\delta}}\Bigg) . \end{equation}

For each k there are at most $2^k$ multipliers in the product over all $\sigma\in \{0,1\}^k$ (the number is smaller if degenerate sites exist). Therefore, there are in total $\sum_{k=0}^{n-1}2^k=2^n-1$ and we get the exponent $2^n$ in the numerator in the first fraction.

In addition, for $n=2$ the event $\mathcal{E}^{\textrm{c}}_2$ means that there exists a hierarchy with sites $(z_{\sigma})$ of depth 2 such that $|z_{01}-z_{10}|\geq |z_0-z_1|(\!\log N)^{-\Delta_1}=N(\!\log N)^{-\Delta_1}$ and $|z_0-z_{01}||z_{11}-z_1|\leq N^{2\eta}$ . Therefore,

(2.8) \begin{equation}\mathbb{P}(\mathcal{E}^{\textrm{c}}_2)\leq \sum_{(t_{\sigma})\notin \mathcal{B}(1)}\mathbb{P}(z_{01}\sim z_{10})\leq |\mathcal{B}^{\textrm{c}}(1)|\frac{C_{\delta}(\!\log N)^{\Delta_1(\alpha_1-\delta)}}{N^{\alpha_1-\delta}}.\end{equation}

In order to estimate (2.7) and (2.8), we need two lemmas from the appendix of [3]. First, for $\kappa\in \mathbb{N}$ and $b>0$ , we let $\Theta_\kappa(b)=\big\{ (n_i)\in \mathbb{N}^\kappa\,:\, n_i\geq 1, \prod_{i=1}^\kappa n_i\geq b^\kappa\big\}$ , and $\Theta^{\textrm{c}}_\kappa(b)$ be its complement in $\mathbb{N}^\kappa$ . Then one has the following estimates.

Lemma 2.3 ([3, Lemma A.1]). For each $\varepsilon>0$ there exists a constant $g_1=g_1(\varepsilon)<\infty$ such that

\begin{equation*}\sum_{(n_i)\in \Theta_{\kappa}(b)}\prod_{i=1}^\kappa\frac{1}{n_i^{1+\beta}}\leq (g_1b^{-\beta}\log b)^\kappa\end{equation*}

is true for all $\beta>0$ , all $b>1$ , and all $\kappa\in \mathbb{N}$ with

\begin{equation*}\beta-\frac{\kappa-1}{\kappa\log b}\geq \varepsilon.\end{equation*}

Lemma 2.4 ([3, Lemma A.2]). There exists a constant $g_2<\infty$ such that, for each $\beta>1$ , each $b\geq e/4$ , and any $\kappa\in \mathbb{N}$ , $\sum_{(n_i)\in \Theta^{\textrm{c}}_\kappa(b)}\prod_{i=1}^{\kappa}n_i^{\beta-1}\leq (g_2b^{\beta}\log b)^\kappa$ .

Let $(n_{\sigma})$ be a collection of positive integers with $n_{\sigma}\leq |t_{\sigma}|\vee 1<n_{\sigma}+1$ . Note that $|\{x\in \mathbb{Z}^d\,:\, n\leq |x|\vee 1<n+1\}|\leq cn^{d-1}$ for some positive constant $c=c(d)$ independent of n. Then, for each $n_{\sigma}$ there exist at most $cn_{\sigma}^{d-1}$ such $t_{\sigma}$ s. Therefore,

(2.9) \begin{align}\sum_{(t_{\sigma})\in \mathcal{B}(k)}\prod_{\sigma\in \{0,1\}^k}\frac{C_{\delta}}{(|t_{\sigma}|\vee 1)^{\alpha_1-\delta}}&\leq \sum_{(n_{\sigma})\in \Theta_{2^k}(N^{\eta^k})}\prod_{\sigma\in \{0,1\}^k}\bigg(cn_{\sigma}^{d-1}\frac{C_{\delta}}{n^{\alpha_1-\delta}_{\sigma}}\bigg)\nonumber \\&\leq\frac{(C_{\delta}cg_1)^{2k}(\eta^k)^{2^k}(\!\log N)^{2^k}}{N^{\eta^k2^k(\alpha_1-\delta-d)}},\end{align}

where we have applied Lemma 2.3 in the last step with $\beta=\alpha_1-\delta-d$ , $b=N^{\eta^k}$ , and $\kappa=2^k$ . Since $\eta<1$ , we obtain the further bound

\begin{equation*}\sum_{(t_{\sigma})\in \mathcal{B}(k)}\prod_{\sigma\in \{0,1\}^k}\frac{C_{\delta}}{(|t_{\sigma}|\vee 1)^{\alpha_1-\delta}}\leq \frac{(C_1\log N)^{2^k}}{N^{(\alpha_1-\delta-d)(2\eta)^k}},\end{equation*}

where we choose $C_1\,:\!=\,cC_{\delta}g_1$ . Now it is left to estimate the size of $\mathcal{B}^{\textrm{c}}(n)$ , and this can be done with help of Lemma 2.4 as $\sum_{(t_{\sigma})\notin \mathcal{B}^{\textrm{c}}(n)} 1 \leq (C_2\log N)^{2^n}N^{d(2\eta)^n} $ with $\beta=d$ , $b=N^{\eta^n}$ , and $\kappa=2^n$ .

Now (2.7) can be simplified to

\begin{align*}(C_2\log N)&^{2^n}N^{d(2\eta)^n}\frac{(C_{\delta}(\!\log N)^{\Delta_1(\alpha_1-\delta)})^{2^n}}{N^{\alpha_1-\delta}}\prod_{i=1}^{n-1}\frac{(C_1\log N)^{2^k}}{N^{(\alpha_1-\delta-d)(2\eta)^k}}\nonumber \\&\leq (C_1C_2C_{\delta}(\!\log N)^{\Delta_1(\alpha_1-\delta)+2})^{2^n}N^{-\left((\alpha_1-\delta-d)\sum_{k=1}^{n-1}(2\eta)^k+\alpha_1-\delta-d(2\eta)^n\right)}\nonumber \\&\leq (\!\log N)^{c_1 2^n}N^{-(\alpha_1-\delta-2d\eta)(2\eta)^n},\end{align*}

where the last step uses the bound $(\alpha_1-\delta-d)\sum_{k=1}^{n-1}(2\eta)^k+\alpha_1-\delta-d(2\eta)^n\geq (\alpha_1-\delta-2d\eta)(2\eta)^n$ .

Our further strategy is to show that an open path with distance shorter then poly-logarithm is impossible. More precisely, we show that the existence of a shorter path is contained in some event with negligible probability. The event we use is as follows.

Definition 2.3. Let $x,y\in \mathbb{Z}^d$ be distinct and $n\in \mathbb{N}$ . We define $\mathcal{F}_n\,:\!=\,\mathcal{F}_n(x,y)$ as the event that, for every hierarchy of depth n connecting x and y and satisfying (2.2), every collection of (vertex self-avoiding and) mutually disjoint paths $\pi_{\sigma}$ with $\sigma \in \{0,1\}^{n-1}$ such that $\pi_{\sigma}$ connects $z_{\sigma 0}$ and $z_{\sigma 1}$ without using any vertex from the hierarchy (except for the endpoints $z_{\sigma 0}$ and $z_{\sigma 1}$ ) obeys the bound

(2.10) \begin{equation}\sum_{\sigma \in \{0,1\}^{n-1}}|\pi_{\sigma}|\geq 2^n.\end{equation}

It might be instructive to look at the complement $\mathcal{F}_n^{\textrm{c}}$ : this is the event that there exists such a hierarchy between x and y satisfying (2.2), but the edges filling the gaps violate (2.10). In the following proposition we construct such a hierarchy in $\mathcal{F}_n^{\textrm{c}}$ from the shortest path.

Proposition 2.2 ([3, Lemma 4.6].) Let $\varepsilon\in (0,\Delta_1)$ . If $N=|x-y|$ is sufficiently large and

(2.11) \begin{equation}n>\frac{\Delta_1-\varepsilon}{\log 2}\log \log N,\end{equation}

then $\{D(x,y)\leq (\!\log N)^{\Delta_1-\varepsilon}\} \cap \mathcal{F}_n=\emptyset$ .

Proof. The proof of [3, Lemma 4.6] still holds here for the event with modified hierarchy, because the hierarchy there was constructed from the shortest path in which all the vertices have degree at most 2.

Now we start to fill the ‘gaps’ in the hierarchy. More precisely, we relate the events $\mathcal{E}_n$ and $\mathcal{F}_n$ by the following proposition.

Proposition 2.3. Let $\eta\in (0,\alpha_1/(2d))$ . For $\delta>0$ so small that $\alpha_1-\delta-d>0$ and $\alpha_1-\delta\in (2d\eta, \alpha_1)$ , there exists a constant $c_2>0$ such that, for all distinct $x,y\in \mathbb{Z}^d$ with $N=|x-y|$ satisfying $\eta^n\log N\geq 2(\alpha_1-\delta-d)$ , $\mathbb{P}\left(\mathcal{F}^{\textrm{c}}_n\cap \mathcal{E}_n\right)\leq \left(\log N\right)^{c_22^n}N^{-(\alpha_1-\delta)(2\eta)^{n-1}}$ .

The idea of proof is to first fix one hierarchy with the sites $(z_{\sigma})$ , and estimate the probability that the paths that fill the gaps of this hierarchy have a certain length. Then the gap-filling paths and the open edges in the hierarchy constitute a path connecting x and y. With help of Lemma 2.2 we get the upper bound by summing over all possible hierarchies.

Proof. Let $\mathcal{A}^*(n)$ be the set of all collections $(z_{\sigma})$ , $\sigma \in \{0,1\}^n$ , satisfying (2.2) for $k=0,$ $1,\dots,n-2$ and (2.3) for $k=1,2,\dots,n-1$ . Then

(2.12) \begin{equation}\mathbb{P}(\mathcal{F}_n^{\textrm{c}} \cap \mathcal{E}_n)=\sum_{(z_{\sigma})\in \mathcal{A}^*(n)}\mathbb{P}(\mathcal{F}^{\textrm{c}}_n\cap \mathcal{H}_n \text{ on } (z_{\sigma})).\end{equation}

Here, ‘ $\mathcal{F}_n^{\textrm{c}}\cap\mathcal{H}_n$ on $(z_{\sigma})$ ’ means that $ \mathcal{H}_n$ with sites $(z_{\sigma})$ is a hierarchy satisfying $\mathcal{F}_n^{\textrm{c}}$ , as explained after Definition 2.3.

We estimate the summands on the right-hand side of (2.12) by considering all possible lengths of $\pi_{\sigma}$ . More precisely, let $(m_{\sigma})$ be a tuple of non-negative integers for $\sigma \in \{0,1\}^{n-1}$ . Then

(2.13) \begin{equation}\mathbb{P}(\mathcal{F}^{\textrm{c}}_n\cap \mathcal{H}_n \text{ on } (z_{\sigma}))=\sum_{(m_{\sigma})}\mathbb{P}(\mathcal{F}^{\textrm{c}}_n\cap \mathcal{H}_n \text{ on } (z_{\sigma}) \text{ with } (|\pi_{\sigma}|)=(m_{\sigma})).\end{equation}

Note that the open path $\pi_{\sigma}$ fills the gap between $z_{\sigma 0}$ and $z_{\sigma 1}$ in $\mathcal{H}_n$ for all $\sigma\in \{0,1\}^{n-1}$ . All such open paths, together with all the open edges $(z_{\sigma 01}, z_{\sigma 10}),\sigma\in \{0,1\}^{n-2}$ , constitute a self-avoiding open path between x and y. Let $\Gamma_{\sigma}(m_{\sigma})$ be the set of all paths of length $m_{\sigma}$ connecting $z_{\sigma 0}$ and $z_{\sigma 1}$ , i.e. $\Gamma_{\sigma}(m_{\sigma})=\big\{\pi\,:\,\pi=(x_0,x_1,\dots,x_{m_{\sigma}}) \text{ with } x_0=z_{\sigma 0} \text{ and }x_{m_{\sigma }}=z_{\sigma1}\big\}$ . Now we estimate the probability in (2.13) as

(2.14) \begin{align} \mathbb{P}(\mathcal{F}^{\textrm{c}}_n & \cap \mathcal{H}_n \text{ on } (z_{\sigma}) \text{ with } (|\pi_{\sigma}|)=(m_{\sigma}))\nonumber\\&=\mathbb{E}\big[\mathbb{P}(\mathcal{F}^{\textrm{c}}_n\cap \mathcal{H}_n \text{ on } (z_{\sigma}) \text{ with } (|\pi_{\sigma}|)=(m_{\sigma})) \mid (W_x)_{x\in \mathbb{Z}^d}\big]\nonumber\\&=\mathbb{E}\Bigg[\mathbb{P}\Bigg(\bigcap_{\sigma\in \{0,1\}^{n-1}}\{z_{\sigma 0}\stackrel{\pi_{\sigma}}{\longleftrightarrow} z_{\sigma 1}\}\bigcap_{\sigma\in \{0,1\}^{n-2}}\{z_{\sigma01}\sim z_{\sigma 10}\} \mid (W_x)_{x\in \mathbb{Z}^d}\Bigg)\Bigg],\end{align}

where $\{z_{\sigma 0}\stackrel{\pi_{\sigma}}{\longleftrightarrow} z_{\sigma 1}\}$ means $\pi_{\sigma}$ connects $z_{\sigma0}$ and $z_{\sigma 1}$ .

By the conditional independence of edges, we rewrite (2.14) as

(2.15) \begin{align}\mathbb{P}&(\mathcal{F}^{\textrm{c}}_n\cap\mathcal{H}_n \text{ on }(z_{\sigma}) \text{ with }(|\pi_{\sigma}|)=(m_{\sigma})) \nonumber\\& \leq \sum_{\substack{(\pi_{\sigma}): \pi_{\sigma}=(x_{\sigma 0},\dots,x_{\sigma m_{\sigma}}) \\ \text{vertex-disjoint}}}\mathbb{E}\Bigg[\prod_{\sigma \in \{0,1\}^{n-1}}\mathbb{P}(\pi_{\sigma}\mid(W_x)_{x \in \mathbb{Z}^d} )\prod_{k=0}^{n-2}\prod_{\sigma^{\prime} \in \{0,1\}^k}p_{z_{\sigma^{\prime} 01}z_{\sigma^{\prime} 10}}\Bigg]\nonumber\\&=\sum_{\substack{(\pi_{\sigma}): \pi_{\sigma}=(x_{\sigma 0},\dots,x_{\sigma m_{\sigma}}) \\ \text{vertex-disjoint}}}\mathbb{E}\Bigg[\prod_{\sigma \in \{0,1\}^{n-1}}\prod_{i=1}^{m_{\sigma}}p_{x_{\sigma (i-1)},x_{\sigma i}}\prod_{k=0}^{n-2}\prod_{\sigma^{\prime} \in \{0,1\}^k}p_{z_{\sigma^{\prime} 01}z_{\sigma^{\prime} 10}}\Bigg] ,\end{align}

where we sum over all possible paths between $z_{\sigma0}$ and $z_{\sigma1}$ for all $\sigma\in \{0,1\}^{n-1}$ and $p_{xy}$ is the connection probability as in (1.1).

In the expectation in (2.15) the probability is divided into two parts: the first double product involves the edges filling the gaps in the hierarchy, while the second double product is about the open edges in the hierarchy, as depicted in Fig. 3.

Figure 3. A hierarchy of depth 3 with site $(z_{\sigma})_{\sigma\in \{0,1\}^3}$ . The gap-filling paths are $\{\pi_{\sigma}\}$ with $\sigma\in \{0,1\}^2$ . In this example, $|\pi_{00}|=1$ , $|\pi_{01}|=3$ , $|\pi_{10}|=1$ , $|\pi_{11}|=2$ , and $\sum|\pi_{\sigma}|=7<2^3=8$ . We see that the paths here, together with the edges in the hierarchy, form a path connecting x and y.

Note that all these paths $(\pi_{\sigma})$ have mutually disjoint vertices. Therefore, for fixed sites $(z_{\sigma})$ and fixed paths $(\pi_{\sigma})$ , we obtain a self-avoiding open path starting from x and ending in y. Now we use Lemma 2.2 to bound the probability of this path, i.e. the expectation in (2.15), as

\begin{multline*}\mathbb{E}\Bigg[\prod_{\sigma \in \{0,1\}^{n-1}}\prod_{i=1}^{m_{\sigma}}p_{x_{\sigma (i-1)},x_{\sigma i}}\prod_{k=0}^{n-2}\prod_{\sigma^{\prime} \in \{0,1\}^k}p_{z_{\sigma^{\prime} 01}z_{\sigma^{\prime} 10}}\Bigg]\\\leq \prod_{\sigma \in \{0,1\}^{n-1}}\prod_{i=1}^{m_{\sigma}}\frac{C_{\delta}}{(|x_{\sigma (i-1)}-x_{\sigma i}|\vee 1)^{\alpha_1-\delta}}\prod_{k=0}^{n-2}\prod_{\sigma^{\prime} \in \{0,1\}^{k}}\frac{C_{\delta}}{|z_{\sigma^{\prime} 01}-z_{\sigma^{\prime} 10}|^{\alpha_1-\delta}}.\end{multline*}

Then, (2.15) becomes

\begin{align*}\mathbb{P}(\mathcal{F}^{\textrm{c}}_n&\cap\mathcal{H}_n \text{ on }(z_{\sigma}) \text{ with }(|\pi_{\sigma}|)=(m_{\sigma}))\\& \leq \sum_{(\pi_{\sigma})}\prod_{\sigma \in \{0,1\}^{n-1}}\prod_{i=1}^{m_{\sigma}}\frac{C_{\delta}}{(|x_{\sigma (i-1)}-x_{\sigma i}|\vee 1)^{\alpha_1-\delta}}\prod_{k=0}^{n-2}\prod_{\sigma^{\prime} \in \{0,1\}^{k}}\frac{C_{\delta}}{|z_{\sigma^{\prime} 01}-z_{\sigma^{\prime} 10}|^{\alpha_1-\delta}}\\&=\Bigg(\prod_{\sigma \in \{0,1\}^{n-1}}Q_{m_{\sigma}}\!(z_{\sigma 0},z_{\sigma 1})\Bigg)\prod_{k=0}^{n-2}\prod_{\sigma^{\prime} \in \{0,1\}^{k}}\frac{C_{\delta}}{|z_{\sigma^{\prime} 01}-z_{\sigma^{\prime} 10}|^{\alpha_1-\delta}} ,\end{align*}

where

\begin{equation*}Q_m(u,v)\,:\!=\,\sum_{\substack{\pi=(x_0,\dots,x_m)\\x_0=u, \,x_m=v}}\prod_{i=1}^{m}\frac{C_{\delta}}{(|x_{i-1}-x_i|\vee 1)^{\alpha_1-\delta}}.\end{equation*}

Here, the sum runs over self-avoiding paths $\pi$ of length m, and therefore $Q_m(u,v)$ is the upper bound for the probability that u and w are connected by an open path with length m. Note that for all $u,v\in \mathbb{Z}^d$ with $u \neq v$ and $\alpha>d$ , there exits a constant $a \in (0,\infty)$ , independent of u and v, such that

(2.16) \begin{equation}\sum_{w\in \mathbb{Z}^d, w\notin \{u,v\}}\frac{1}{|u-w|^{\alpha}}\frac{1}{|v-w|^{\alpha}}\leq \frac{a}{|u-v| ^{\alpha}}.\end{equation}

The estimate above can be obtained by splitting the sum into two cases: $\{w\in \mathbb{Z}^d\,:\, |u-w|\leq |v-w|\}$ and $\{w\in \mathbb{Z}^d\,:\, |u-w|> |v-w|\}$ . In the first case we have $|v-w|\geq 1/2|u-v|$ , and since $\alpha>d$ , $\sum_{w\neq u} 1/|u-w|^{\alpha}<\infty$ . A similar argument holds for the second case.

Then we can bound $Q_m(u,v)$ from above by applying (2.16) m times iteratively and obtain

(2.17) \begin{equation}Q_m(u,v)\leq \frac{(C_{\delta}a)^m}{(|u-v|\vee 1)^{\alpha_1-\delta}}.\end{equation}

If we now sum over all the possible combinations of $(m_{\sigma})$ with $\sum_{\sigma}m_{\sigma}<2^n$ , we obtain the upper bound

\begin{align*}\mathbb{P}(\mathcal{F}_n^{\textrm{c}}&\cap \mathcal{H}_n \text{ on } (z_{\sigma})) \nonumber\\& \leq \sum_{(m_{\sigma})\,:\, \sum_{\sigma}m_{\sigma}<2^n}\!\Bigg(\prod_{\sigma \in \{0,1\}^{n-1}}Q_{m_{\sigma}}\!(z_{\sigma 0},z_{\sigma 1})\Bigg)\prod_{k=0}^{n-2}\prod_{\sigma^{\prime} \in \{0,1\}^{k}}\frac{C_{\delta}}{|z_{\sigma^{\prime} 01}-z_{\sigma^{\prime} 10}|^{\alpha_1-\delta}}\\& \leq (4aC_{\delta})^{2^n}\prod_{\sigma\in \{0,1\}^{n-1}}\frac{1}{(|z_{\sigma 0}-z_{\sigma 1}|\vee 1)^{\alpha_1-\delta}}\prod_{k=0}^{n-2}\prod_{\sigma^{\prime} \in \{0,1\}^{k}}\frac{C_{\delta}}{|z_{\sigma^{\prime} 01}-z_{\sigma^{\prime} 10}|^{\alpha_1-\delta}}\\& \leq (4aC_{\delta})^{2^n} \prod_{k=0}^{n-1}\prod_{\sigma \in \{0,1\}^k}\frac{C_{\delta}(\!\log N)^{(\alpha_1-\delta)\Delta^{\prime}}}{(|z_{\sigma 0}-z_{\sigma 1}|\vee 1)^{\alpha_1-\delta}}.\end{align*}

Here, we first used the estimation for $Q_m(u,v)$ in (2.17) and the fact that the number of such eligible tuples $(m_{\sigma})$ is at most $4^{2^n}$ , and subsequently used the fact that on $\mathcal{E}_n$ the lengths of open edges in the hierarchy are subject to the constraint (2.5).

We now can estimate the desired probability as

(2.18) \begin{align}\mathbb{P}(\mathcal{F}^{\textrm{c}}_n\cap \mathcal{E}_n)&=\sum_{(z_{\sigma})\in \mathcal{A}^*(n)}(4aC_{\delta})^{2^n} \prod_{k=0}^{n-1}\prod_{\sigma \in \{0,1\}^k}\frac{C_{\delta}(\!\log N)^{(\alpha_1-\delta)\Delta^{\prime}}}{(|z_{\sigma 0}-z_{\sigma 1}|\vee 1)^{\alpha_1-\delta}}\end{align}

\begin{align}&\leq \frac{(C_1(\!\log N)^{\Delta_1(\alpha_1-\delta)})^{2^n}}{N^{\alpha_1-\delta}}\prod_{k=0}^{n-1}\sum_{(t_{\sigma})\in \mathcal{B}(k)}\prod_{\sigma\in \{0,1\}^k}\frac{C_{\delta}}{(|t_{\sigma}|\vee 1)^{\alpha_1-\delta}}\nonumber.\end{align}

Recall that $\mathcal{B}(k)$ is the set of all collections $(t_{\sigma})$ , $\sigma\in \{0,1\}^k$ , of vertices in $\mathbb{Z}^d$ such that (2.6) is true. Then, by applying Lemma 2.3 again (as in (2.9)), together with $\alpha_1-\delta+(\alpha_1-\delta)$ $\sum_{k=1}^{n-1}(2\eta)^k\geq (\alpha_1-\delta)(2\eta)^{n-1}$ , the result follows.

Proof of Theorem 1.1 ,lower bound. By Proposition 2.2 we can bound the probability of the event $\{D(x,y)\leq (\!\log N)^{\Delta_1-\varepsilon}\}$ by the probability of the event $\mathcal{F}_n^{\textrm{c}}$ once Proposition 2.2 holds. That is, if the depth of the hierarchy n satisfies (2.11), $\mathbb{P}\big(D(x,y)\leq (\!\log N)^{\Delta_1-\varepsilon}\big)\leq \mathbb{P}(\mathcal{F}^{\textrm{c}}_n)$ .

Now we fix $\varepsilon\in(0,\Delta_1-1)$ . Since $2^{-1/{\Delta_1}}={\alpha_1}/{2d}$ by (1.5), we can choose $\delta>0$ and $\eta$ such that $2^{-{1}/{(\Delta_1-\varepsilon})}<\eta<({\alpha_1-\delta})/{2d}$ , so that, in particular,

\begin{equation*}\frac{\Delta_1-\varepsilon}{\log 2}<\frac{1}{\log 1/\eta}.\end{equation*}

We further fix $\delta_1\in (0, \alpha_1-\delta-2d\eta)$ . For large N we thus find $n\in\mathbb{N}$ such that

(2.19) \begin{equation} \frac{\Delta_1-\varepsilon}{\log 2}\log \log N <n \leq \frac{\log \log N+\log\frac{\delta_1}{c_1}-\log\log\log N}{\log 1/\eta}.\end{equation}

We henceforth assume that N is large enough that, for $c_1$ from Proposition 2.1,

(2.20) \begin{equation}(\!\log N)^{c_12^n}\leq N^{\delta_1(2\eta)^n}.\end{equation}

In this case, the right-hand side of (2.19) is further bounded from above by

\begin{equation*} \frac{\log\log N-\log2(\alpha_1-\delta-d)}{\log1 /\eta}.\end{equation*}

Therefore, we may apply the assertions of Proposition 2.1, 2.2, and 2.3 (Proposition 2.1 even for all smaller values of n), and we thus get

(2.21) \begin{align}\nonumber\mathbb{P}\big(D(x,y)\leq (\!\log N)^{\Delta_1-\varepsilon}\big)&\leq \mathbb{P}(\mathcal{F}^{\textrm{c}}_n)\leq \mathbb{P}(\mathcal{E}^{\textrm{c}}_n)+\mathbb{P}(\mathcal{F}_n^{\textrm{c}}\cap\mathcal{E}_n)\nonumber\\&\leq \sum_{k=3}^n\mathbb{P}(\mathcal{E}^{\textrm{c}}_k\cap\mathcal{E}_{k-1})+\mathbb{P}(\mathcal{E}_2^{\textrm{c}})+\mathbb{P}(\mathcal{F}_n^{\textrm{c}}\cap\mathcal{E}_n).\nonumber\\&\leq \varepsilon^{\prime}+\varepsilon^{\prime}+\varepsilon^{\prime}=3\varepsilon^{\prime}.\end{align}

Using Proposition 2.1 and (2.20), we get, for $k\leq n$ , $\mathbb{P}(\mathcal{E}^{\textrm{c}}_{k+1}\cap\mathcal{E}_k)\leq N^{-(\alpha_1-\delta-2d\eta-\delta_1)(2\eta)^k}$ , and Proposition 2.3 yields a similar bound for $\mathbb{P}(\mathcal{F}_n^{\textrm{c}}\cap\mathcal{E}_n)$ . Since $2\eta>1$ , we thus get the right-hand side of (2.21) arbitrarily close to 0 by choosing N sufficiently large.

Translation invariance and the Fortuin–Kasteleyn–Ginibre (FKG) inequality yield $\mathbb{P}(x,y\in \mathcal{C}_{\infty})\geq \mathbb{P}(x\in \mathcal{C}_{\infty})^2>0$ . Therefore, we have $\lim_{|x-y|\to \infty}\mathbb{P}(D(x,y)\leq (\!\log |x-y|)^{\Delta_1-\varepsilon} \mid x,y\in \mathcal{C}_{\infty})=0$ , as desired.

3. Proof of the upper bound

The upper bound in Theorem 1.1(b) and (c) is already established in [10], so we restrict our attention here to the case $\tau\in (2,3)$ . Interestingly, for $\tau>3$ the logarithmic power of the upper and lower bounds match, and we have thus identified the correct exponent.

Unlike in long-range percolation, edges in scale-free percolation are only conditionally independent. Intuitively speaking, adjacent edges are positively correlated due to the weight of their joint vertex (see [21, Exercise 9.45]). Here we state a more general result, which is implied by the FKG inequality.

Proposition 3.1. Let $\pi=(x_i)_{i=0,\dots,n}$ be a path in scale-free percolation and $k\in\{1,\dots,n-1\}$ , and let $\pi_1$ and $\pi_2$ be two subpaths of $\pi$ by cutting $\pi$ at vertex $x_k$ . That is, $\pi_1=(x_i)_{i=0,\dots,k}$ and $\pi_2=(x_i)_{i=k,\dots,n}$ . Then $\mathbb{P}(\pi \ is\ open)\geq \mathbb{P}(\pi_1\ is\ open)\mathbb{P}(\pi_2\ is\ open)$ .

From Proposition 3.1 we see that two adjacent edges (or even paths) in scale-free percolation are indeed positively correlated. The next result tells us that in some cases the positive correlation is significant.

Proposition 3.2. (Probability of adjacent edges.) In scale-free percolation with $\tau \in (2,3)$ there exist $x_0>0$ and $c_2>c_1>0$ such that, for all $x,y,z\in \mathbb{Z}^d$ with $|x-y|\geq |y-z|\geq x_0$ , we have $c_1|x-y|^{-\alpha}|y-z|^{-\alpha(\tau-2)}\leq \mathbb{P}(x\sim y\sim z)\leq c_2|x-y|^{-\alpha}|y-z|^{-\alpha(\tau-2)}$ .

Proof. We start by calculating the probability of this joint occurrence as

\begin{equation*}\mathbb{P}(x\sim y\sim z)=\mathbb{E}\bigg[\bigg(1-\exp\!\bigg({-}\frac{\lambda W_xW_y}{|x-y|^{\alpha}}\bigg)\bigg)\bigg(1-\exp\!\bigg({-}\frac{\lambda W_yW_z}{|y-z|^{\alpha}}\bigg)\bigg)\bigg].\end{equation*}

For $t\in(0,\infty)$ , we have $\frac{1}{2}(t\wedge 1)\leq 1-{\textrm{e}}^{-t}\leq t\wedge 1$ , so that

(3.1) \begin{equation}\mathbb{P}(x\sim y\sim z) \leq \mathbb{E}\bigg[\bigg(\frac{\lambda W_xW_y}{|x-y|^{\alpha}}\wedge 1\bigg)\bigg(\frac{\lambda W_yW_z}{|y-z|^{\alpha}} \wedge 1\bigg)\bigg]\leq 4\,\mathbb{P}(x\sim y\sim z),\end{equation}

and it is sufficient to compute the expectation in the middle.

First, we show that the two single weights $W_x$ and $W_z$ do not play a role in the result. On the one hand, we know $W_x\geq 1$ , therefore

\begin{equation*}\mathbb{E}\bigg[\bigg(\frac{\lambda W_xW_y}{|x-y|^{\alpha}}\wedge 1\bigg)\bigg(\frac{\lambda W_yW_z}{|y-z|^{\alpha}} \wedge 1\bigg)\bigg]\geq \mathbb{E}\bigg[\bigg(\frac{\lambda W_y}{|x-y|^{\alpha}}\wedge 1\bigg)\bigg(\frac{\lambda W_y}{|y-z|^{\alpha}} \wedge 1\bigg)\bigg] .\end{equation*}

On the other hand, $st\wedge 1 \leq s(t\wedge 1)$ ( $s\geq 1 \text{ and }t > 0$ ) implies

\begin{align*}\mathbb{E}\bigg[\bigg(\frac{\lambda W_xW_y}{|x-y|^{\alpha}}\wedge 1\bigg)\bigg(\frac{\lambda W_yW_z}{|y-z|^{\alpha}} \wedge 1\bigg)\bigg] &\leq \mathbb{E}\bigg[W_x\bigg(\frac{\lambda W_y}{|x-y|^{\alpha}}\wedge 1\bigg)\bigg(\frac{\lambda W_y}{|y-z|^{\alpha}} \wedge 1\bigg)W_z\bigg] \\&={\mu}^2\mathbb{E}\bigg[\bigg(\frac{\lambda W_y}{|x-y|^{\alpha}}\wedge 1\bigg)\bigg(\frac{\lambda W_y}{|y-z|^{\alpha}} \wedge 1\bigg)\bigg],\end{align*}

where $\mu\,:\!=\,\mathbb{E}[W_x]< \infty$ since $\tau >2$ . Together with (3.1), we thus obtain

\begin{equation*}\frac{1}{\mu^2}\mathbb{P}(x\sim y \sim z) \leq \mathbb{E}\bigg[\bigg(\frac{\lambda W_y}{|x-y|^{\alpha}}\wedge 1\bigg)\bigg(\frac{\lambda W_y}{|y-z|^{\alpha}} \wedge 1\bigg)\bigg]\leq 4\mathbb{P}(x\sim y\sim z).\end{equation*}

Thus it suffices to compute the expectation

\begin{align*}\mathbb{E}\bigg[\bigg(\frac{\lambda W_y}{|x-y|^{\alpha}}\wedge 1\bigg)&\bigg(\frac{\lambda W_y}{|y-z|^{\alpha}} \wedge 1\bigg)\bigg] \\&=\int_{\mathbb{R}} \bigg(\frac{\lambda u}{|x-y|^{\alpha}}\wedge 1\bigg)\bigg(\frac{\lambda u }{|y-z|^{\alpha}} \wedge 1\bigg) \, {\textrm{d}} W_y(u)\\&=\int_{1}^{\infty}\bigg(\frac{\lambda u}{|x-y|^{\alpha}}\wedge 1\bigg)\bigg(\frac{\lambda u }{|y-z|^{\alpha}} \wedge 1\bigg)(\tau-1)u^{-\tau} \, {\textrm{d}} u .\end{align*}

We now split the domain of integration into three intervals: $[1,|y-z|^{\alpha}/\lambda]$ , $(|y-z|^{\alpha}/\lambda,|x-y|^{\alpha}/\lambda]$ , and $(|x-y|^{\alpha}/\lambda, \infty)$ . After some calculation, we obtain

\begin{multline*}\mathbb{E}\bigg[\bigg(\frac{\lambda W_y}{|x-y|^{\alpha}}\wedge 1\bigg)\bigg(\frac{\lambda W_y}{|y-z|^{\alpha}} \wedge 1\bigg)\bigg]\\=\frac{\tau-1}{(3-\tau)(\tau-2)}\frac{\lambda}{|x-y|^{\alpha}}\frac{\lambda^{\tau-2}}{|y-z|^{\alpha(\tau-2)}}-\frac{\tau-1}{3-\tau}\frac{\lambda}{|x-y|^{\alpha}}\frac{\lambda}{|y-z|^{\alpha}}-\frac{\lambda^{\tau-1}}{\tau-2}\frac{1}{|x-y|^{\alpha(\tau-1)}}.\end{multline*}

We may therefore choose

\begin{equation*}c_2\,:\!=\,\frac{\tau-1}{(3-\tau)(\tau-2)}\mu^2\lambda^{\tau-1}.\end{equation*}

For $\tau\in (2,3)$ , we find that the first term dominates the sum when $|y-z|\rightarrow\infty$ (the other terms are negative, but the total sum is trivially nonnegative). Hence, there exist positive constant $x_0$ and $c_1$ such that $\mathbb{P}(x\sim y\sim z)\geq c_1|x-y|^{-\alpha}|y-z|^{-\alpha(\tau-2)}$ for $|y-z|\geq x_0$ .

In fact, the weights of two end points do not contribute to the significant positive correlation in Proposition 3.2, as we formulate in the next corollary.

Corollary 3.1. In scale-free percolation with $\tau \in (2,3)$ , there exist constants $c_i=c_i(a,b)>0$ for $i=1,2$ and $x_0=x_0(a,b)>0$ such that, for all $x,y,z\in \mathbb{Z}^d$ with $|x-y|\geq |y-z|\geq x_0$ ,

\begin{equation*}c_1|x-y|^{-\alpha}|y-z|^{-\alpha(\tau-2)}\leq \mathbb{P}(x\sim y\sim z\mid W_x=a,W_z=b)\leq c_2|x-y|^{-\alpha}|y-z|^{-\alpha(\tau-2)}.\end{equation*}

In particular, for constants $M>m>0$ , there exist $C_i=C_i(a,b, m, M)>0$ , $i=1,2$ , and $x^{\prime}_0=x^{\prime}_0(a,b)>0$ such that, if $|x-y|$ and $|y-z|$ are comparable in the sense $m|x-y|\leq |y-z| \leq M|x-y|$ , then

\begin{multline*}C_1|x-y|^{-\alpha(\tau-1)/2}|y-z|^{-\alpha(\tau-1)/2} \\ \leq \mathbb{P}( x\sim y\sim z\mid W_x=a,W_z=b) \leq C_2|x-y|^{-\alpha(\tau-1)/2}|y-z|^{-\alpha(\tau-1)/2} \end{multline*}

for all $|x-y|\geq x^{\prime}_0$ .

In light of Proposition 3.1 and 3.2 and Corollary 3.1, we now aim to construct a path with edges of comparable length. Instead of connecting two vertices directly, we use an intermediate vertex as a ‘bridge’ to connect the two vertices. For $x,y\in\mathbb{Z}^d$ , $A\subset\mathbb{Z}^d$ , we write $\{x\sim A \sim y\}=\bigcup_{z\in A}\{x\sim z\sim y\}$ for the event that x and y are connected via an ‘intermediate vertex’ in A.

Proposition 3.3. For $\beta\in (0,1)$ , there exist constants $N_0,K>0$ such that, for all $x,y\in \mathbb{Z}^d$ with $N\,:\!=\,|x-y|\geq N_0$ , it is true that

\begin{equation*}\mathbb{P}\left(x\sim A \sim y \right) \geq \frac{K}{N^{2\alpha_1-d\beta}},\end{equation*}

where $A\,:\!=\,\big(\frac12(x+y)+[{-}N^\beta,N^\beta]^d\big)\cap\mathbb{Z}^d$ is the cube with side length $N^{\beta}$ centred at the middle point of the line segment between x and y.

Proof. Since $\beta<1$ , there exist constants $l=l(\beta,d)$ and $L=L(\beta,d)$ with $L>l>0$ and $N_1>0$ such that $lN\leq|x-z|\leq LN$ and $lN\leq|y-z|\leq LN$ for all $z\in A$ and all $N\geq N_1$ . Therefore, $|x-z|$ and $|y-z|$ are comparable in the sense of Corollary 3.1. Thus, we have $\mathbb{P}(x\sim A \sim y)\geq \mathbb{P}(x\sim A \sim y\mid W_x=1,W_y=1)=1-\prod_{z\in A}(1-\mathbb{P}(x\sim z \sim y\mid W_x=W_y=1))$ , where we used the conditional independence of edges and the independence of vertex weights. We estimate this further using Corollary 3.1 and get that there exist $N_2>0$ and $c_1>0$ such that, for all $N\geq N_2$ ,

\begin{equation*} \mathbb{P}(x\sim z \sim y\mid W_x=W_y=1)\geq c_1\frac{1}{|x-z|^{\alpha_1}}\frac{1}{|z-y|^{\alpha_1}}\geq \frac{c_1}{L^{2\alpha_1}}\frac{1}{N^{2\alpha_1}}.\end{equation*}

Note that the right-hand side of this inequality is independent of z, which allows us to estimate

\begin{align*}\mathbb{P}(x\sim A \sim y )\geq 1-\bigg(1-\frac{c_1}{L^{2\alpha_1}N^{2\alpha_1}}\bigg)^{N^{d\beta}}.\end{align*}

Now we use the elementary bound $1-t\leq {\textrm{e}}^{-t} \leq 1-\frac{1}{2}t$ ( $0<t<1$ ) to conclude that

\begin{equation*}\bigg(1-\frac{c_1}{L^{2\alpha_1}N^{2\alpha_1}}\bigg)^{N^{d\beta}}\leq {\textrm{e}}^{-CN^{d\beta-2\alpha_1}/L^{2\alpha_1}}\leq 1-\frac{c_1}{2N^{2\alpha_1-d\beta}L^{2\alpha_1}}.\end{equation*}

Since $d\beta-2\alpha_1<0$ , there exists $N_3>0$ such that $c_1N^{d\beta-2\alpha_1}/L^{2\alpha_1}<1$ for all $N\geq N_3$ , and consequently also $c_1N^{-2\alpha_1}L^{-2\alpha_1}<1$ . Finally, we have

\begin{equation*}\mathbb{P}(x\sim A \sim y)\geq \frac{c_1}{2N^{2\alpha_1-d\beta}L^{2\alpha_1}}\end{equation*}

for all $N\geq N_0\,:\!=\,\max\{N_1,N_2,N_3\}$ , and choose

\begin{equation*}K\,:\!=\,\frac{c_1}{2L^{2\alpha_1}}\end{equation*}

as desired.

With these preparations we finally prove the upper bound.

Proof of Theorem 1.1 , upper bound. Since the adjacent paths in scale-free percolation are positively correlated (by Proposition 3.1) and the probability of the compound edge ‘ $x\sim A \sim y$ ’ decays algebraically with exponent $2\alpha_1-d\beta$ (by Proposition 3.3), we have that the probability of a path being open in SFP dominates that in LRP with edge probability decaying with exponent $2\alpha_1-d\beta$ in (1.7). Therefore, the graph distance in SFP in this case is no more than twice the distance in long-range percolation with connection probability as in (1.7) but with $\alpha$ replaced by $2\alpha_1-d\beta$ . Since we can choose $\beta$ arbitrarily close to 1, the result follows from Theorem 1.2.

Remark 3.1. In this paper we made a specific choice for the connection probability in (1.1). However, the proofs for both lower and upper bounds in Sections 2 and 3 only require asymptotics of the connection probability to estimate the path, for example in Lemma 2.1 and Proposition 3.2. Therefore, our results generalise to the scale-free percolation with connection probability

\begin{equation*}p_{x,y}=\Theta\bigg(\frac{\lambda W_xW_y}{|x-y|^{\alpha}}\wedge 1\bigg)\end{equation*}

provided that a unique infinite cluster exists.