Upper bounds on the one-arm exponent]Upper bounds on the one-arm exponent for
dependent percolation models
Vivek Dewan^1
$^1$Institut Fourier, Université Grenoble Alpes
Stephen Muirhead^2
$^2$School of Mathematics and Statistics, University of Melbourne

We prove upper bounds on the one-arm exponent $\eta_1$ for dependent percolation models; while our main interest is level set percolation of smooth Gaussian fields, the arguments apply to other models in the Bernoulli percolation universality class, including Poisson-Voronoi and Poisson-Boolean percolation. More precisely, in dimension $d=2$ we prove $\eta_1 \le 1/3$ for Gaussian fields with rapid correlation decay (e.g. the Bargmann-Fock field), and in general dimensions we prove $\eta_1 \le d/3$ for finite-range fields and $\eta_1 \le d-2$ for fields with rapid correlation decay. Although these results are classical for Bernoulli percolation (indeed they are best-known in general), existing proofs do not extend to dependent percolation models, and we develop a new approach based on exploration and relative entropy arguments. We also establish a new Russo-type inequality for smooth Gaussian fields which we use to prove the sharpness of the phase transition for finite-range fields.

[2010]60G60 (primary); 60F99 (secondary)

§ INTRODUCTION

The critical phase of percolation models is believed (see, e.g., <cit.>) to be described by critical exponents which govern the power-law behaviour of macroscopic observables at, or near, criticality. In this paper we consider the one-arm exponent; we introduce this in the classical setting of Bernoulli percolation, before generalising to a class of dependent percolation models induced by the excursion sets of smooth Gaussian fields (`Gaussian percolation').

Fix a dimension $d \ge 2$, consider the lattice $\mathbb{Z}^d = (\mathcal{V}, \mathcal{E})$, and declare each edge $e \in \mathcal{E}$ to be `open' independently with probability $p \in [0,1]$. The resulting law $\mathbb{P}_p$ of the open subset of $\mathcal{E}$ is known as Bernoulli percolation on $\mathbb{Z}^d$ with parameter $p$. Defining the connection event

\[  \{ A \longleftrightarrow B \} := \{ \text{there exists a path of open edges that intersects $A$ and $B$}\} \]

where $A, B \subset\mathcal{V}$,[We allow the path to be empty, so that $\{A  \longleftrightarrow B \}$ occurs if $A \cap B \neq \emptyset$.] and denoting by $\Lambda_R := [-R, R]^d \subset\mathcal{V}$ the box of size $R$, it is well known  [23] that there exists $p_c = p_c(d) \in (0, 1)$, satisfying $p_c(2) = 1/2$ and $p_c(d) < 1/2$ for $d \ge 3$, such that

\[ \theta(p) := \mathbb{P}_p[ 0  \longleftrightarrow \infty  ] := \lim_{R \to \infty} \mathbb{P}_p[ 0  \longleftrightarrow \partial \Lambda_R ]  = \begin{cases} 0 &  \text{if } p < p_c , \\  >  0 & \text{if } p > p_c . \end{cases} \]

Although it is still open to prove $\theta(p_c) = 0$ for $d \ge 3$, it has been shown that [11, 2]

\begin{equation}
\label{e:mflb}
\theta(p) \ge c (p - p_c)
\end{equation}

for a constant $c = c(d)$ and $p > p_c$ sufficiently close to $p_c$; this is known as the mean-field lower bound
and is expected to be tight for dimensions $d \ge d_c = 6$ in which critical exponents take their mean-field value.

At criticality $p = p_c$ it is believed that connection probabilities between scales obey a power law, in the sense that there exists $\eta_1 > 0$ such that, as $R \to \infty$ and for $r = o(R)$,

\begin{equation}
\label{e:eta1heu}
\mathbb{P}_{p_c}[ \Lambda_r \longleftrightarrow \partial \Lambda_R   ]  = (r/R)^{-\eta_1 + o(1)} .
\end{equation}

While the existence of the one-arm exponent $\eta_1$ is not known rigorously, since we are interested in upper bounds we define

\begin{equation}
\label{e:eta}
\eta_1 := \liminf_{R \to \infty}  \frac{- \log \mathbb{P}_{p_c}[ 0 \longleftrightarrow \partial \Lambda_R   ] }{ \log R}  .
\end{equation}

Clearly upper bounds on (<ref>) imply upper bounds on the exponent in (<ref>) assuming its existence. Note however that the choice of $\liminf$, rather than $\limsup$, in the definition of $\eta_1$ is deliberate and yields a priori weaker upper bounds (see however Remark <ref>).

The phenomenon of universality suggests that a wide class of dependent percolation models behave similarly to Bernoulli percolation at, or near, criticality, and in particular $\eta_1$ should be identical inside this class. In this paper we consider the following class of dependent models. Let $f$ be a continuous stationary-ergodic centred Gaussian field on $\mathbb{R}^d$, and for $\ell \in \mathbb{R}$ write $\mathbb{P}_\ell[\cdot]$ to denote $\mathbb{P}[ f + \ell \in \cdot \,]$ (abbreviating $\P = \P_0$). Then the excursion sets $\{ f   + \ell \ge 0 \} := \{ x \in \mathbb{R}^d : f(x) + \ell \ge 0\}$ induce a stationary ergodic percolation model on $\mathbb{R}^d$ via the connectivity relation

\[  \{ A \longleftrightarrow B \} := \{ \text{there exists a path in $\{f  \ge 0\}$ that intersects $A$ and $B$}\} \]

for closed sets $A, B \subset\mathbb{R}^d$. Recalling the box $\Lambda_R := [-R, R]^d$ (now considered a subset of $\mathbb{R}^d$), by monotonicity there exists $\ell_c = \ell_c(f) \in [-\infty, \infty]$ such that

\[ \theta(\ell) := \mathbb{P}_\ell[ \Lambda_1 \longleftrightarrow \infty  ] :=  \lim_{R \to \infty} \mathbb{P}_\ell[ \Lambda_1  \longleftrightarrow \partial \Lambda_R  ] = \begin{cases} 0 &  \text{if } \ell < \ell_c , \\ > 0 & \text{if } \ell > \ell_c , \end{cases} \]

where the choice of $\{ \Lambda_1   \longleftrightarrow \partial \Lambda_R\}$ rather than $ \{ 0   \longleftrightarrow \partial \Lambda_R\}$ is to avoid the possibility of local obstructions (relevant only in the case that the FKG inequality is not available; see the comments after (<ref>)). Under general conditions it is known that $\ell_c = 0$ if $d = 2$ and $\ell_c \in (-\infty, 0]$ if $d \ge 3$ (see [44, 38, 22, 42, 37] and [35, 36] respectively for sufficient conditions, which are implied by the assumptions in this paper, namely Assumption <ref> below). Similarly to for Bernoulli percolation, for this class of models we define

\begin{equation}
\label{e:etagf}
\eta_1 := \liminf_{R \to \infty}  \frac{-\log \mathbb{P}_{\ell_c}[ \Lambda_1   \longleftrightarrow \partial \Lambda_R ] }{\log R} .\end{equation}

In this case the mean-field lower bound (<ref>) has not yet been established; indeed in this paper we prove it for Gaussian fields with finite-range dependence.

§.§ Upper bounds on the one-arm exponent

We now present our main results, which are upper bounds on $\eta_1$. We begin with Bernoulli percolation; although the results are not new in this case, they are illustrative for general models.

For Bernoulli percolation on $\mathbb{Z}^d$,

\[    \eta_1 \le \begin{cases} 1/3 & d = 2, \\ d/3 & d \ge 3 . \end{cases} \]

If $d=2$, the bound $\eta_1 \le 1/3$ was first given in [29][In the paper the argument is attributed to van den Berg.] which established that $\mathbb{P}_{p_c}[  0   \longleftrightarrow \partial \Lambda_R]  \ge c R^{-1/3}$. Recently this was improved to $\ge c R^{-1/6}$  [14], giving $\eta_1 \le 1/6$. It is believed that $\eta_1 = 5/48$, but this is known rigorously only for very specific models [47].

In general dimension the hyperscaling inequality $\eta_1 \le d/(1+\delta)$ has been established rigorously [9], where $\delta$ is the critical exponent governing the volume of critical clusters. In light of the mean-field bound $\delta \ge 2$ [2], this implies $\eta_1 \le d/3$.[Although [9] assumes the existence of the exponent $\delta$, one can extract the unconditional bound $\eta_1 \le d/3$ from the proof.] In high dimension $d \ge 11$ it is known that $\eta_1$ takes its mean-field value $\eta_1 = 2$ [31, 20], see also Corollary <ref> below. It is believed that

\[  \eta_1 = \begin{cases} 0.48\ldots  & d = 3, \qquad \qquad   0.95\ldots \qquad d=4 , \\ 1.5\ldots & d = 5 , \qquad \qquad 2  \qquad  \qquad  \hspace{0.3cm} d \ge d_c =  6 . \end{cases} \]

In particular, the bound $\eta_1 \le d/3$ is expected to be tight at the upper-critical dimension $d_c=6$ (indeed, it implies $d_c \ge 6$ since it shows that $\eta_1 = 2$ cannot occur for $d \le 5$).

As for lower bounds on $\eta_1$, in $d=2$ one can use RSW estimates to prove that $\eta_1 > \varepsilon$ (which can be quantified, but is small), however if $d \in \{3, 4, 5, 6\}$ it is still wide open to prove $\eta_1 > 0$ (there are partial results in intermediate dimensions, e.g. for spread-out models).

For the bound $\eta_1 \le 1/3$ in $d=2$, we could replace the liminf in the definition of $\eta_1$ in (<ref>) with limsup, since the argument yields $\mathbb{P}_{p_c}[ 0 \longleftrightarrow \partial \Lambda_R] \ge c R^{-1/3}$, see (<ref>). In fact, the argument gives the stronger bound $\P_{p_c}[ A_2(R) ]  \ge c R^{-2/3}$, where $A_2(R)$ is the (polychromatic) two-arm event; see Section <ref> for the definition and more details.

Similarly, if $d \ge 3$ one can modify our argument to give $\mathbb{P}_{p_c}[ 0 \longleftrightarrow \partial \Lambda_R] \ge c R^{-d/3}$ by working under an (unproven) assumption that critical `box-crossing' probabilities do not converge to $1$, which to our knowledge is a new inference; see Remark <ref> for details. Note that this assumption is expected to be true if $d < d_c = 6$, but likely not if $d \ge 6$.

Previous proofs of Theorem <ref> rely heavily on specific properties of Bernoulli percolation (such as the BK inequality, used to prove $\delta \ge 2$, and in the case of the stronger bound $\eta_1 \le 1/6$ if $d=2$, on the `parafermionic observable'), and hence do not extend easily to dependent percolation models. On the contrary, we give a new proof of Theorem <ref> that extends naturally to a wide class of dependent models; our next result illustrates this for Gaussian percolation.

Let us begin by stating some assumptions. Recall that $f$ is a continuous stationary-ergodic centred Gaussian field. We will always assume that $f$ has a spatial moving average representation $f = q \star W$, where $q \in L^2(\mathbb{R}^d) \neq 0$ is Hermitian (i.e. $q(x) = q(-x)$), $W$ is the white noise on $\mathbb{R}^d$, and $\star$ denotes convolution; a sufficient condition is that the covariance kernel $K(\cdot) := \mathbb{E}[f(0) f(\cdot)] = (q \star q)(\cdot)$ is in $L^1(\mathbb{R}^d)$, since then we may define $q :=\mathcal{F}[ \sqrt{ \rho } ]$, where $\mathcal{F}$ dentotes the Fourier transform and $\rho = \mathcal{F}[K] \in C^0(\R^d)$ is the spectral density of the field.

For our main results we will further assume that $q$ satisfies the following basic properties:

[Basic assumptions on the Gaussian field]

* (Regularity) $q$ is three-times differentiable and each of these derivatives is in $L^2(\R^d)$.

* (Decay of correlations, with parameter $\beta > d$) There exists a $c > 0$ such that, for all $x \in \mathbb{R}^d$,

\[   \max\{ |q(x)| , \, |\nabla q(x)| \} \le  c |x|^{-\beta } .  \]

* (Symmetry) $q$ is symmetric under negation and permutation of the coordinate axes.

Let us explain some consequences of Assumption <ref>. The regularity condition implies that $K  = q \star q \in C^6(\mathbb{R}^d)$, and hence $f$ is $C^2$-smooth almost surely (see <cit.>). The decay condition implies that $q \in L^1(\R^d)$ and so also $K \in L^1(\R^d)$, which ensures that the spectral density is continuous and $(f, \nabla f, \nabla^2 f)$ is non-degenerate (i.e. its evaluation on a finite number of distinct points is a non-degenerate Gaussian vector, see <cit.>). The symmetry assumption is crucial in $d=2$ (for instance, to prove RSW estimates), but it also simplifies some aspects of the proof in all dimensions. Finally, as we mentioned above, if $d=2$ then Assumption <ref> is sufficient to prove that $\ell_c = 0$ (see <cit.> and Remark 1.9 therein).

For most of our results we also assume

\begin{equation}
\label{a:pos1}
\tag{POS}
\int q := \int_{\mathbb{R}^d} q(x) \, dx > 0 .
\end{equation}

This is equivalent to the spectral density being positive at the origin, and is a natural assumption when studying how properties of a Gaussian field change with the level; see e.g. [38, 5].

For some of our results we further assume that $f$ is positively correlated:

\begin{equation}
\label{a:pos2}
\tag{POS'}
\text{$K(x) = (q \star q)(x) \ge 0$ for all $x \in \mathbb{R}^d$.}
\end{equation}

This is equivalent to the FKG inequality holding for the field (i.e. the field is positively associated), so that events increasing with respect to the field are positively correlated [41].[Although in [41] this is proven only for finite Gaussian vectors, one can deduce positive associations for all increasing events considered in this paper via standard approximation arguments, see <cit.>.] Note that (<ref>) is stronger than (<ref>) (the former implies that the spectral density is positive definite, and so strictly positive at the origin unless $K = 0$).

Recall that the mean-field lower bound (<ref>) is not known for Gaussian percolation. We introduce it as an assumption: There exists $c > 0$ such that, for $\ell > \ell_c$ sufficiently close to $\ell_c$,

\begin{equation}
\label{a:mflb}
\tag{MFB}
\text{$\theta(\ell)  := \mathbb{P}_\ell[ \Lambda_1 \longleftrightarrow \infty  ]   \ge c (\ell - \ell_c)$.}
\end{equation}

While we expect (<ref>) to hold in great generality, in this paper we prove it only for finite-range dependent fields, see Theorem <ref> below.

For Gaussian percolation we prove the following upper bounds on the one-arm exponent:

Suppose $f = q \star W$ satisfies Assumption <ref> with parameter $\beta$ and (<ref>).

* If $d\ge3$ and $\beta >  4d-4$, then $\eta_1 \leq  \min\{ \frac{d-2 + \alpha(3d-1)}{1+2\alpha}, d-1 \}$ where $\alpha =  \frac{3d-4}{2\beta-5d+4}$.

* If $d\ge2$, $\beta > 2d-1$, and (<ref>) holds, then $\eta_1  \le  \min\{ \max\{ \frac{d}{3} +  \frac{\alpha(d-1)}{3},  \frac{\alpha(2d-1)}{3} \} , d-1\}$ where $\alpha =  \frac{3d-2}{2\beta-d}$.

* If $d=2$, $\beta > \frac83$, and (<ref>) holds, then $\eta_1 \le  \min\{ \frac{1}{3} + \frac{5}{6(\beta-1)}, \frac12 \} $.

To illustrate Theorem <ref> consider the example of the Bargmann-Fock field with covariance kernel $K(x) = e^{-|x|^2/2}$ (see [4] for background and motivation), which is easily seen to satisfy Assumption <ref> for every parameter $\beta$ and also (<ref>).
According to the Harris criterion (see [51], or [7] for further discussion), it is expected that Gaussian percolation is in the Bernoulli percolation universality class if $K(x) \ll c |x|^{-2/\nu }$ where $\nu = \nu(d)$ is the correlation length exponent of Bernoulli percolation (see Section <ref>). In particular the Bargmann-Fock field is expected to belong to this class, and hence possess the same exponents as Bernoulli percolation.

Suppose $f = q \star W$ satisfies Assumption <ref> for every parameter $\beta$ and (<ref>) (e.g. the Bargmann-Fock field). Then

\[    \eta_1 \le \begin{cases} 1/3  & d = 2, \\ d-2  & d \ge 3 . \end{cases} \]

Further, if (<ref>) holds then $\eta_1 \le d/3$ .

Take $\beta \to \infty$ in Theorem <ref>.

One can also consider the example of finite-range dependent fields, i.e. for which

\begin{equation}
\label{a:bou}
\tag{BOU}
q \text{ has bounded support,}
\end{equation}

noting that this supersedes the second condition in Assumption <ref>.

Suppose $f = q \star W$ satisfies Assumption <ref> and (<ref>)–(<ref>). Then $\eta_1 \le d/3$.

Take $\beta \to \infty$ in the second statement of Theorem <ref> ((<ref>) holds by Theorem <ref>).

Previously for Gaussian percolation it was known only that $\eta_1 \le 1/2$ in $d=2$, and $\eta_1 \le d-1$ in $d \ge 3$ (the former is a consequence of RSW estimates [4, 43, 38], and see [12], or the proof of Theorem <ref>, for the latter); hence the bounds in Theorem <ref> exceed what was known in all dimensions for large $\beta$. Notably, as for Bernoulli percolation, the bound $d/3$ is expected to be tight if $d = 6$. We emphasise that Corollary <ref> does not assume positive correlations, and so applies to a class of models that lack positive associations.

As in Remark <ref>, if $d=2$ we could replace the liminf in the definition of $\eta_1$ with limsup, since the proof yields polynomial lower bounds on $\mathbb{P}_{\ell_c}[ \Lambda_1 \longleftrightarrow \partial \Lambda_R]$ (see (<ref>)). Indeed the proof gives polynomial lower bounds on the two-arm event; for example for the Bargmann-Fock field we prove that, for every $\varepsilon > 0$ there is a $c > 0$ such that

\[ \P_{\ell_c}[ \{ \text{there exists a path in $\{f = 0\}$ that intersects $\Lambda_1$ and $\partial \Lambda_R$} \}  ] \ge c R^{-2/3 - \varepsilon} .\]

§.§ Relations to other critical exponents

The methods used to prove the above results also give bounds on $\eta_1$ in terms of other critical exponents. For simplicity we state these only for Bernoulli percolation, but similar bounds can be proven for Gaussian percolation (which, under Assumption <ref> and (<ref>)–(<ref>), would match those in Theorem <ref> below).

Let us introduce the relevant exponents. Recall the mean-field lower bound  (<ref>) on $\theta(p)$. It is expected that $\theta(p) \to 0$ as a power law as $p \downarrow p_c$; although this is not known rigorously (except in high dimension), we will assume that the corresponding exponent exists

\[ \beta = \lim_{p \downarrow p_c} \frac{ \log \theta(p)}{\log |p_c-p|} \in (0, 1] .\]

Below criticality $p < p_c$, it is known that connection probabilities decay exponentially [34, 2, 18] and that the limit

\[  \frac{1}{\xi(p)} :=   \lim_{R \to \infty} \frac{ - \log \mathbb{P}_p[  0 \longleftrightarrow\partial \Lambda_R    ] }{R} \in (0, \infty)      \]

exists <cit.>. The correlation length $\xi(p)$ is expected to diverge as a power law as $p \uparrow p_c$, and we will again assume that the corresponding exponent exists

\[   \nu =  \lim_{p \uparrow  p_c}  \frac{ - \log \xi(p) }{\log |p_c-p|} \in (0, \infty)  . \]

Similarly, as $p \uparrow p_c$ the susceptibility $\chi(p)  :=  \sum_{v \in \Z^d} \P_p[ 0 \longleftrightarrow v]  < \infty$ is expected to diverge as a power law, and we will assume the existence of

\[   \gamma =  \lim_{p \uparrow p_c}  \frac{ - \log \chi(p) }{\log |p_c-p|}   \in (0, \infty) . \]

Finally we also assume that the critical two-point function decays as a power law with exponent

\[  d - 2 + \eta := \lim_{|v|_\infty \to \infty} \frac{ -\log \mathbb{P}_{p_c}[ 0 \longleftrightarrow v] }{\log |v|_\infty}  \in (0, \infty),\]

where $|\cdot|_\infty$ denotes the sup-norm. It is well known that $\nu \ge 2/d$ [10], $\gamma \ge 1$ [3], and $\eta \le 1$ [24].

For Bernoulli percolation on $\Z^d$, assuming the existence of $\beta, \nu, \gamma$ and $\eta$,

\begin{equation}
\label{e:new}
\frac{2-\gamma}{\nu} \le \eta_1 \le \bar{\eta}_1 \le  \min\Big\{ d - \frac{2}{\nu}, \frac{2-\eta}{2/\beta-1}  \Big\}  ,
\end{equation}

where $\bar{\eta}_1$ is defined as in (<ref>) with limsup replacing liminf. Moreover

\[ \eta_1 \le   \frac{d}{2/\beta+1}  \qquad \text{and} \qquad  \bar{\eta}_1 \le 1 - \frac{1}{\nu}, \ \text{if } d = 2 .\]

To our knowledge the bounds in (<ref>) are new even for Bernoulli percolation, and $\eta_1 \ge \frac{2-\gamma}{\nu}$ may be of particular interest as a lower bound on $\eta_1$. The bound $\eta_1 \le   \frac{d}{2/\beta+1}$ is implied by the hyperscaling inequality in [9], and for $  \bar{\eta}_1 \le 1 - \frac{1}{\nu}$ if $d=2$ see [29, 50].

For Bernoulli percolation in sufficiently high dimension it is known that the exponents $\nu$, $\gamma$ and $\eta$ exist and take their mean-field values $\nu = 1/2$ [26], $\gamma = 1$ [3], and $\eta=0$ [27]. Hence Theorem <ref> gives a new proof of the result of Kozma and Nachmias that $\eta_1 = 2$ in high dimension:

For Bernoulli percolation on $\Z^d$, there exists $d_0 > 0$ such that, if $d \ge d_0$,

\[   \lim_{R \to \infty} \frac{- \log \P_{p_c}  [ 0 \longleftrightarrow \partial \Lambda_R ]  }{\log R}  = 2 . \]

Our argument is significantly simpler than the one in [31], however it yields only

\[   c_1 R^{-2} \le  \P_{p_c} [ 0 \longleftrightarrow \partial \Lambda_R ] \le  c_2 R^{-2}  (\log R)^4  \]

whereas [31] proved that $\P_{p_c} [ 0 \longleftrightarrow \partial \Lambda_R ]  \asymp R^{-2}$ in the sense of bounded ratios (see Remark <ref>). Another difference is that we deduce $\eta_1 = 2$ in any dimension from the bounds $\nu \le 1/2$ and $\eta \ge 0$ (see Remark <ref>, or recall the Fischer inequality $\gamma/\nu \le 2-\eta$), whereas the argument in [31] uses as input $d > 6$ and the two-sided bound $\eta = 0$ (or more precisely $ \mathbb{P}_{p_c}[ 0 \longleftrightarrow v] \asymp |v|_\infty^{-d+2}$).

§.§ Sharpness of the phase transition for smooth Gaussian fields

As well as bounds on the one-arm exponent, a second aim of this paper is to establish the sharpness of the phase transition for smooth finite-range dependent Gaussian fields, and in addition verify the mean-field lower bound (<ref>) for such fields. For this we adapt the celebrated argument of Duminil-Copin, Raoufi and Tassion [16] by exploiting a new `Russo-type inequality' for smooth Gaussian fields (see Proposition <ref>); we expect this inequality will have further applications.

Suppose $f=q \star W$ is $C^2$-smooth and satisfies (<ref>). Then for every $\ell < \ell_c$ there exist  $c_1, c_2 > 0$ such that, for $R \ge 1$,

\[  \mathbb{P}_\ell[  \Lambda_{1} \longleftrightarrow \partial \Lambda_R  ]  \le c_1 e^{-c_2 R} . \]

Moreover, the mean-field lower bound (<ref>) holds.

For Gaussian percolation the sharpness of the phase transition was only known so far in two cases: (i) in $d=2$ assuming Assumption <ref> and (<ref>) [38], and (ii) for certain discrete Gaussian fields on $\mathbb{Z}^d$ satisfying (<ref>) [13]. The mean-field lower bound (<ref>) was not known for any smooth Gaussian fields. We emphasise that in Theorem <ref> we do not assume (<ref>), so this theorem holds for a class of fields lacking positive associations.

Clearly if (<ref>) holds then $f$ is finite-range dependent, but we do not know whether every finite-range dependent $f$ can be represented as $q \star W$ for $q$ with bounded support (although this seems very natural, and it is true if $d=1$, see [19]). If we demand in addition that $q$ be supported on half of the support of $K$ then, rather surprisingly, this is false [19]. On the other hand, under (<ref>) it is true <cit.>. Moreover, it is known [45] that if $f$ is finite-range dependent and isotropic (i.e. $K$ is rotationally symmetric) it can be represented as a countable sum of independent $f_i = q_i \star W_i$ for $q_i$ with uniformly bounded support. Since it is straightforward to extend our proof of Theorem <ref> to handle such fields, the conclusions of Theorem <ref> (and Corollary <ref>) also hold if $f$ is smooth, finite-range dependent, and isotropic.

§.§ Other models

Other than Bernoulli percolation and level set percolation of Gaussian fields, the arguments adapt naturally to many other models in the Bernoulli percolation universality class. For instance, both Poisson-Voronoi and Poisson-Boolean percolation can be treated in a very similar way (although in the latter case the obtained bounds may depend on the decay of the radius distribution, and also some of our arguments in $d=2$ do not apply since the model lacks self-duality). Indeed the necessary tools to apply the OSSS inequality in these settings, analogous to the arguments in Section <ref>, have already been developed in [15] and [17] respectively. For brevity we do not discuss details here.

While this work was begin finalised we learned that similar arguments to those we use to prove $\eta_1 \le 1/3$ if $d=2$ were previously used in the general setting of increasing Boolean functions [8]; see Section <ref> for a statement of the relevant result from [8] and a comparison to what we prove.

§.§ Outline of the paper

In Section <ref> we study Bernoulli percolation and give the proof of Theorems <ref> and <ref>. In Section <ref> we adapt the arguments to the Gaussian setting, and give the proof of Theorem <ref> subject to an auxiliary result (Proposition <ref>). In Section <ref> we establish the Russo-type inequality for smooth Gaussian fields mentioned above, and apply it to prove Proposition <ref> and Theorem <ref>. The appendix contains a technical result on orthogonal decompositions of Gaussian fields.

§.§ Acknowledgements

The second author was partially supported by the Australian Research Council (ARC) Discovery Early Career Researcher Award DE200101467. The authors thank Damien Gayet, Tom Hutchcroft, Ioan Manolescu and Hugo Vanneuville for helpful discussions, comments on an earlier draft, and for pointing out references [14] (Ioan) and [8, 49] (Hugo). This work was initiated while the first author was visiting Queen Mary University of London and we thank the University for its hospitality.

§ BERNOULLI PERCOLATION

In this section we focus on Bernoulli percolation, which serves as a template for the extension of the arguments to dependent percolation models.

Let us begin by introducing notation for connection events. For $k, R> 0$, define the box $B_k(R):=  [-R, R] \times [-kR, kR]^{d-1}  \subset\mathcal{E}$, and the `box-crossing event'

\[ \textrm{Cross}_k(R) := \Big\{ \{-R\} \times [-kR,kR]^{d-1}  \stackrel{B_k(R)}{\longleftrightarrow} \{R\} \times[-kR,kR]^{d-1}  \Big\}  , \]

where $\{ A  \stackrel{E}{\longleftrightarrow} B \} :=  \{ \text{there exists a path of open edges in $E \subset \mathcal{E}$ that intersects $A$ and $B$}\}$. For $R \ge 0$, define the one-arm event

\[  A_1(R) :=  \{ 0 \longleftrightarrow \partial \Lambda_R \} .\]

Restricting for a moment to $d=2$, we also introduce the (polychromatic) two-arm event $A_2(R)$ that was mentioned in Remark <ref>. Consider the dual lattice $(\mathbb{Z}^2)^\ast$; in this graph an edge is considered open if and only if the unique edge $e \in \mathcal{E}$ that it crosses is closed (i.e. not open). Note that each vertex $v \in\mathcal{V}$ has four neighbouring dual vertices, and for $A \subset \mathcal{V}$ let $A^\star$ be the union of these neighbours over $v \in A$.  For $A, B \subseteq\mathcal{V}$ define

\[ \{ A \stackrel{E}{\doublepath} B\}  = \{ A  \stackrel{E}{\longleftrightarrow} B \}   \cap \{ \text{there exists a dual path in $E$ that intersects $A^\star$ and $B^\star$} \}, \]

where a dual path in $E$ is a path of dual edges that cross closed edges in $E$, and abbreviate $\{A \doublepath B\} = \{ A \stackrel{\Z^2}{\doublepath} B\}$. For $R \ge 0$, define

\[  A_2(R) :=  \{  0 \doublepath \partial \Lambda_R \}  \qquad \text{and} \qquad \eta_2 := \liminf_{R \to \infty} \frac{-\log \mathbb{P}_{p_c}[ A_2(R) ]}{\log R} . \]

We make the elementary observation that

\begin{equation}
\label{e:eta1eta2}
\eta_2 \ge 2 \eta_1
\end{equation}

where $\eta_1$ is defined in (<ref>). To see this, note that by the FKG inequality

\[ \mathbb{P}_{p}[ A_2(R) ] \le   \mathbb{P}_{p}[ A_1(R) ] \, \mathbb{P}_{p}[  \{ \text{there exists a dual path that intersects $0^\ast$ and $\Lambda_R^\star$} \}] . \]

Since Bernoulli percolation on $\mathbb{Z}^2$ is self-dual at $p_c = 1/2$, and by translation invariance,

\[    \mathbb{P}_{p_c}[  \{ \text{there exists a dual path that intersects $0^\ast$ and $\Lambda_R^\star$} \}] \le 4 \mathbb{P}_{p_c}[ A_1(R-1) ]  .\]

Hence $\mathbb{P}_{p_c}[ A_2(R) ]  \le  4 \mathbb{P}_{p_c}[ A_1(R-1) ]^2$, and (<ref>) follows immediately.

Let us return to the general setting of Bernoulli percolation on $\mathbb{Z}^d$. The case $d \ge 3$ of Theorem <ref> is proven by combining the following result with the mean-field lower bound (<ref>):

For $0 < p \le q < 1$ and $R \ge 1$,

\[ \mathbb{P}_q[  A_1(R) ] - \mathbb{P}_p [A_1(R) ]  \le  \max \! \Big\{ \! \frac{\sqrt{2}}{\sqrt{q(1-q)}}, \! \frac{\sqrt{2}}{\sqrt{p(1-p)}}  \! \Big\} (q-p)  \sqrt{  \mathbb{P}_{q}[A_1(R)]   \sum_{v \in \Lambda_R} \! \! \P_p[ 0 \longleftrightarrow v ]}  . \]

For the case $d=2$ of Theorem <ref> we rely instead on the following inequalities:

Let $k \ge 1$. Then there exists $c > 0$ such that, for $p \in (0, 1)$ and $R \ge 1$,

\[  \frac{d}{d p} \mathbb{P}_p[  \textrm{Cross}_k(R) ] \le \frac{c R^{d/2}}{\sqrt{p(1-p)}}  \times \begin{cases}  \sqrt{ \mathbb{P}_{p}[A_2(R)]} & d=2 , \\    \sqrt{  \mathbb{P}_{p}[A_1(R)] }  & d \ge 2. \end{cases}  \]

Let $d=2$ and $k \ge 1$. Then there exists $c > 0$ such that, for $p \in (0, 1)$ and $R \ge 8$,

\begin{equation}
\label{e:lbb}
\frac{d}{d p} \mathbb{P}_{p} [ \textrm{Cross}_k(R)] \ge \frac{c}{p(1-p)} \frac{ \P_p[ \textrm{Cross}_{1/(8k)}(kR)]^4  \big(1-\P_p[\textrm{Cross}_{8k}(R/8)] \big)^2}{\mathbb{P}_{p}[A_2(R)]} .
\end{equation}

We prove Propositions <ref>–<ref> later in the section; for now we complete the proof of our main results (Theorems <ref> and <ref>). First we recall some standard facts:

* There exists $\delta > 0$ and $p' = p'(R) \le p_c$ such that, for $R \ge 1$,

\[ \mathbb{P}_{p'}[\textrm{Cross}_5(R)] =  \delta .  \]

* (RSW) Let $d=2$ and $k > 0$. Then there exists $\delta > 0$ such that, for $R \ge 1$,

\[  \mathbb{P}_{p_c}[\textrm{Cross}_k(R)]  \in (\delta, 1-\delta) . \]

For the first statement, a classical bootstrapping argument (see, e.g., <cit.>) shows that $\mathbb{P}_{p_c}[\textrm{Cross}_5(R)] >  \delta$, and the result follows by continuity in $p$. The second statement amounts to the classical RSW estimates.

In the proof $c > 0$ are constants that depend only on the dimension and may change from line to line. We begin with the case $d \ge 3$. We may assume that $\mathbb{P}_{p_c}[ A_1(R) ]  \to 0$ as $R \to \infty$ since otherwise $\eta_1 = 0$. Define $q = q(R) > p_c$ such that

\[ \P_q[A_1(R)] = \min\{ 2 \P_{p_c}[A_1(R)] , 1\} , \]

which exists since $p \mapsto \P_p[A_1(R)]$ is continuous and strictly increasing. Note that $q(R) \to p_c$ as $R \to \infty$ since otherwise

\[  \limsup_{R \to \infty} \P_{p_c}[A_1(R)] \ge \limsup_{R \to \infty} \theta(q(R))/2 > 0 . \]

By the mean-field lower bound (<ref>), for sufficiently large $R$

\begin{equation}
\label{e:toab1}
\P_{p_c}[A_1(R)] =  \P_q[A_1(R)]/2 \ge \theta(q)/2 \ge c(q-p_c)  .
\end{equation}

Now apply Proposition <ref> to $p = p_c$ and $q = q(R)$; this yields

\[  \mathbb{P}_{p_c} [A_1(R) ]  =   \mathbb{P}_{q} [A_1(R) ]  - \mathbb{P}_{p_c} [A_1(R) ]   \le  c (q-p_c)  \sqrt{ \mathbb{P}_{p_c}[A_1(R)]   \sum_{v \in \Lambda_R} \P_{p_c}[ 0 \longleftrightarrow v ]}  \]

for large $R$. Combining with (<ref>), we deduce that

\begin{equation}
\label{e:mainineq}
\mathbb{P}_{p_c}[A_1(R)]   \sum_{v \in \Lambda_R} \P_{p_c}[ 0 \longleftrightarrow v ]  \ge c
\end{equation}

for all $R \ge 1$.

We now show that $\eta_1 \le d/3$ follows from (<ref>). If $\eta_1 = 0$ there is nothing to prove, so assume $\eta_1 > 0$ and fix $\eta^\ast \in (0, \eta_1)$. Then by the definition of $\eta_1$

\begin{equation}
\label{e:etaast}
\mathbb{P}_{p_c}[ A_1(R) ]  \le R^{- \eta^\ast}
\end{equation}

for large $R$; in particular, via an integral comparison,

\begin{equation}
\label{e:intcomp}
\sum_{v \in \Lambda_R}  \mathbb{P}_{p_c}[ A_1(\lfloor |v|_\infty/2 \rfloor) ]^2 \le  \max\{ R^{d-2\eta^\ast} , 1\} (\log R)
\end{equation}

for large $R$.  Next observe that $\{0 \longleftrightarrow v\}$ implies the occurrence of

\[ \{0 \longleftrightarrow \Lambda_{ \lfloor |v|_\infty/2 \rfloor } \}  \qquad \text{and} \qquad  \{v \longleftrightarrow v + \Lambda_{ \lfloor |v|_\infty/2 \rfloor} \}  \]

which depend on disjoint subsets of edges. Hence by translation invariance and (<ref>)

\begin{equation}
\label{e:split}
\sum_{v \in \Lambda_R}  \P_{p_c}[ 0 \longleftrightarrow v ]   \le  \sum_{v \in \Lambda_R}  \P_{p_c}[ A_1(\lfloor |v|_\infty/2 \rfloor )]^2  \le \max\{ R^{d-2\eta^\ast} , 1\} (\log R)
\end{equation}

for large $R$, and so

\[ c \le  \mathbb{P}_{p_c}[A_1(R)]   \sum_{v \in \Lambda_R} \P_{p_c}[ 0 \longleftrightarrow v ]  \le R^{-\eta^\ast} \max\{ R^{d-2\eta^\ast} , 1\} (\log R) .\]

This implies  $\eta^{\ast} \le d/3$, and since $\eta^\ast < \eta_1$ was arbitrary, we deduce $\eta_1 \le d/3$.

We now turn to the case $d = 2$. By Propositions <ref>–<ref> and the RSW estimates (the second statement of Lemma <ref>), for large $R$

\[  \frac{c}{\mathbb{P}_{p_c}[A_2(R)]} \le  \frac{d}{d p} \mathbb{P}_p[ \textrm{Cross}_1(R)] \Big|_{p= p_c}  \le   c R  \sqrt{  \mathbb{P}_{p_c}[A_2(R)] }  \]

which yields, for large $R$,

\begin{equation}
\label{e:twoarm1}
\mathbb{P}_{p_c}[A_2(R)]  \ge c  R^{-2/3} .
\end{equation}

By the discussion after (<ref>), this implies

\begin{equation}
\label{e:limsup2}
\mathbb{P}_{p_c}[A_1(R)]  \ge c  R^{-1/3}
\end{equation}

for large $R$, and hence $\eta_1 \le 1/3$.

One could replace the right-hand side of (<ref>) with the (perhaps simpler) expression

\[ \frac{c}{p(1-p)} \frac{\P_p[\textrm{Cross}_k(R)] \big(1-\P_p[\textrm{Cross}_k(R)] \big)}{ \frac{1}{R^2} \sum_{i,j=0}^{R} \mathbb{P}_{p_c}[A_2(\min\{i,j\} )] } .\]

While this suffices to prove $\eta_1 \le 1/3$, it does not yield the stronger bounds (<ref>)–(<ref>).

In the case $d \ge 3$ our argument does not imply $ \mathbb{P}_{p_c}[A_1(R)]  \ge c R^{-d/3}$. However, as mentioned in Remark <ref>, one can obtain this by working under a `box-crossing' assumption.

First, by modifying the proof of Proposition <ref> one can prove that, for every $k \ge 1$ there exists a $c > 0$ such that, for $p \in (0, 1)$ and $R \ge 2$,

\[  \frac{d}{d p} \mathbb{P}_p[  \textrm{Cross}_k(R)]  \ge  \frac{c}{p(1-p)} \frac{\mathbb{P}_p[\textrm{Cross}_k(R)]^2 \big(1-\P_p[\textrm{Cross}_{2k}(R/2) ] \big) }{ \mathbb{P}_p[A_1(R)]}  .\]

Next assume the following box-crossing property: For every $k \ge 1$ and $\delta_0 \in (0, 1)$ there are $\delta_1 \in (0, 1)$ and $R_0 > 0 $ such that, for $R \ge R_0$ and $p \le p_c$,

\begin{equation}
\label{a:box}
\tag{BOX}
\mathbb{P}_{p}[ \textrm{Cross}_k(R) ] < 1 - \delta_0  \quad \implies \quad \mathbb{P}_{p}[ \textrm{Cross}_{2k}(R/2) ] <  1 - \delta_1 .
\end{equation}

Then by working on the sequence $p' = p'(R) \le p_c$ at which $\P_{p'}[  \textrm{Cross}_5(R)] = \delta$, guaranteed by the first statement of Lemma <ref>, and comparing upper and lower bounds on $\frac{d}{d p} \mathbb{P}_p[  \textrm{Cross}_5(R)]|_{p = p'}$, one deduces the result.

Note that (<ref>) states roughly that if box-crossings do not occur with high probability for one aspect ratio, then they do not occur with high probability for other aspect ratios. This is known in $d=2$ by the RSW estimates in Lemma <ref>, and is strongly believed to hold if $d < 6$ [9]. Although (<ref>) seems difficult to verify, it is quite natural to work under this assumption; e.g. in [9] hyperscaling relations were proven under a version of (<ref>), although interestingly they use this assumption to obtain lower bounds on $\eta_1$.

In the proof $c > 0$ are constants that depend only on the dimension and may change from line to line, and $o(1)$ denotes a quantity that decays to zero as $R \to \infty$.

We begin with the bounds $\eta_1 \le d / (2/\beta+1)$ and $\bar{\eta}_1 \le (2-\eta)/(2/\beta-1)$ which require only a slight change to the argument used to prove $\eta_1 \le d/3$ above. Recall (<ref>) and let $q(R) \to p_c$ be defined as in (<ref>). By the definition of the exponent $\beta$, one can replace (<ref>) with

\[   \P_{p_c}[A_1(R)] \ge \theta(q)/2 \ge c(q-p_c)^{\beta + o(1)} , \]

which gives, in place of (<ref>),

\begin{equation}
\label{e:mainineq2}
\mathbb{P}_{p_c}[A_1(R)]^{\frac{2}{\beta}- 1 + o(1)} \sum_{v \in \Lambda_R} \P_{p_c}[ 0 \longleftrightarrow v ]  \ge c    ,
\end{equation}

for large $R$. Then using (<ref>), for any $\eta^\ast \in (0, \eta_1)$ and large $R$ we have

\[ R^{-\eta^\ast (\frac{2}{\beta}- 1) + o(1) }  \max\{ R^{d-2\eta^\ast} , 1\} (\log R)   \ge c ,    \]

which implies $ \eta_1 \le d / (2/\beta+1)$. On the other hand, by the definition of the exponent $\eta$,

\[ \sum_{v \in \Lambda_R} \P_{p_c}[ 0 \longleftrightarrow v ]   = R^{2 - \eta + o(1) } , \]

which by (<ref>) implies

\[  \mathbb{P}_{p_c}[A_1(R)] \ge R^{-(2-\eta)/(2/\beta-1)  + o(1) }  \]

and hence $\bar{\eta}_1 \le (2-\eta)/(2/\beta-1)$.

To prove the remaining bounds we use the fact that, by a super-multiplicativity argument (see <cit.>), there is a $c_1 > 0$ such that

\begin{equation}
\label{e:tpexp}
\mathbb{P}_p[ 0 \longleftrightarrow v ] \le e^{-c_1  |v|_\infty /\xi(p) }
\end{equation}

for all $p < p_c$ and $v \in \Z^d$. We also recall the standard facts <cit.> that $\xi(p)$ is continuous, strictly increasing, and $\xi(p)\to \infty$ as $p \uparrow p_c$.

Let $C > 0$ be a constant to be fixed later, and for $R$ sufficiently large, let $p' = p'(R) \uparrow p_c$ be such that $R = C \xi(p') \log \xi(p')$. Since we have the a priori bound $\P_{p_c}[A_1(R)] \ge c R^{-(d-1)/2}$ [24, 48], we can take $C > 0$ sufficiently large so that, by (<ref>) and the union bound,

\[  \mathbb{P}_{p'}[A_1(R) ]  \le c R^{d-1} e^{-c_1 C  \log \xi(p') } \le c R^{d-1} R^{-c_1 C + o(1) }  \le  \P_{p_c}[A_1(R)] / 2  \]

for large $R$.  Then applying Proposition <ref> to $p = p'$ and $q = p_c$ gives, for large $R$,

\[  \mathbb{P}_{p_c} [A_1(R) ] /2  \le   \mathbb{P}_{p_c} [A_1(R) ]  - \mathbb{P}_{p'} [A_1(R) ]   \le  c (p_c-p') \sqrt{ \mathbb{P}_{p_c}[A_1(R)]   \sum_{v \in \Lambda_R} \P_{p'}[ 0 \longleftrightarrow v ]}   \]

or, equivalently,

\begin{equation}
\label{e:mainineq3}
\P_{p_c}[A_1(R)]  \le c (p_c-p')^2  \sum_{v \in \Lambda_R} \P_{p'}[ 0 \longleftrightarrow v ] .
\end{equation}

Since $\sum_{v \in \Lambda_R} \P_{p'}[ 0 \longleftrightarrow v ] \le \chi(p')$, and by the definition of the exponents $\nu$ and $\gamma$, this implies

\[\P_{p_c}[A_1(R)]  \le c  (p_c-p')^2  \chi(p')  \le c     \xi(p')^{-2/\nu + o(1) } \xi(p')^{\gamma/\nu + o(1)} = R^{-(2-\gamma)/\nu + o(1)}   \]

for large $R$, which implies $\eta_1 \ge (2-\gamma)/\nu$.

Finally, let $\delta > 0$ be such that $\mathbb{P}_{p_c}[\textrm{Cross}_5(R)]  \ge  \delta$ for large $R$ (possible by the first statement of Lemma <ref>), and again let $p' = p'(R) \uparrow p_c$ be such that $R = C \xi(p') \log \xi(p')$. Then

\[  \mathbb{P}_{p'}[\textrm{Cross}_5(R) ] \le  \delta/2 \]

for large $R$, and we deduce that there exists $p'' \in (p',p_c)$ such that

\[    \frac{d}{d p} \mathbb{P}_p[ \textrm{Cross}_5(R)] \Big|_{p= p''}  \ge \frac{\delta/2}{p_c-p'} .   \]

On the other hand, by Proposition <ref> and monotonicity in $p$,

\[  \frac{d}{d p} \mathbb{P}_p[  \textrm{Cross}_5(R) ] \Big|_{p= p''} \le   c  R^{d/2} \sqrt{ \P_{p_c}[A_1(R)] } \]

and hence

\[     (p_c-p')^2 R^d \, \P_{p_c}[A_1(R)]     \ge  c  \]

for large $R$. By the definition of the exponent $\nu$, this implies

\[  \xi(p')^{-2/\nu + o(1)} R^d \P_{p_c}[A_1(R)]  =  R^{d-2/\nu + o(1)}  \P_{p_c}[A_1(R)]    \ge c \]

for large $R$, which implies that $\bar{\eta}_1 \le d - 2/\nu$. The bound $\bar{\eta}_1 \le 1 - 1/\nu$ in $d=2$ is similar, except we use two-arm events as in the proof of Theorem <ref>.

As mentioned in Remark <ref>, by combining the high-dimensional bounds [26, 27]

\[   \xi(p) \le c(p_c-p)^{-1/2}   \qquad \text{and} \qquad \P_{p_c}[ 0 \longleftrightarrow v ] \le c |v|_{\infty}^{-d+2}   \]

with (<ref>) and (<ref>), one arrives at a quantitative version of Corollary <ref>, namely the bounds

\[  c_1 R^{-2}  \le \P_{p_c}[A_1(R)] \le c_2 R^{-2} (\log R)^4. \]

§.§ Exploration algorithms

To prove Propositions <ref>–<ref> we make use of exploration algorithms, which we introduce in a general setting.

Let $X =  (X_i)$ be a countable set of random variables taking values in arbitrary probability spaces. A (randomised) algorithm $\mathcal{A}$ on $X$ is a random adapted procedure that sequentially reveals a subset of the coordinates $X_i$ and returns a value. We say that $\mathcal{A}$ determines an event $A$ if it returns the value $\id_A$ almost surely. The revealment $\textrm{Rev}(i)$ of a given coordinate $X_i$ is the probability that $\mathcal{A}$ reveals this coordinate.

For Bernoulli percolation we consider algorithms on $X = (X_e)_{e \in \mathcal{E}}$ for $X_e = \id_{e \text{ open}}$. A useful property of the events $A_1(R)$ and $\textrm{Cross}_k(R)$ is the existence of determining algorithms whose revealments are controlled by connection probabilities. Recall the box $B_k(R)  \subset \mathcal{E}$, and define its right half $B_k^+(R) := [0, R] \times [-kR, kR]^{d-1}  \subset \mathcal{E}$. If $d=2$, define also its top-right quarter $B_k^\dagger(R) := [0, R] \times [0,kR]  \subset \mathcal{E}$.

For every $p \in (0, 1)$ and $R \ge 1$ there is an algorithm determining $A_1(R)$ such that, under $\mathbb{P}_p$,

\[  \sum_{e \in  \mathcal{E}}  \textrm{Rev}(e) \le 2 \sum_{v \in \Lambda_R}  \P_p[ 0 \longleftrightarrow v] . \]

Moreover for every $k \ge 1$, $p \in (0, 1)$ and $R \ge 1$ there are algorithms determining $\textrm{Cross}_k(R)$ such that, under $\mathbb{P}_p$,

\[   \max_{e \in  B_k^+(R)}  \textrm{Rev}(e) \le \, 2 \P_p[A_1(R)]  ,\]

and, if $d=2$,

\[  \max_{e \in  B_k^\dagger(R)}  \textrm{Rev}(e) \le 2 \P_p[A_2(R)] . \]

We only give a sketch of proof; for more details see the proof of Lemma <ref> which gives analogous statements in the Gaussian setting.

Recall the definition of $\{A \stackrel{E}{\longleftrightarrow}  B \} $, and for each edge $e \in \mathcal{E}$ let $\{e \stackrel{E}{\longleftrightarrow}  B \} $ be the union of $\{v \stackrel{E}{\longleftrightarrow}  B \} $ over the endpoints $v$ of $e$, and $\{e \stackrel{E}{\doublepath}  B \} $ similarly.

For the first statement, let $\Wc$ be the random subset of $B_1(R)$ defined by

\[ \Wc:=  \Big\{ e \in B_1(R) \Big| \big\{ 0 \stackrel{B_1(R)}{\longleftrightarrow}  e \big\} \Big\} .\]

Then consider the algorithm that sequentially reveals $\Wc$ starting from the origin. This determines $A_1(R)$ and satisfies

\[   \sum_{e \in \mathcal{E}} \textrm{Rev}(e) = \sum_{e \in B_1(R)} \P_p \Big[ \Big\{0 \stackrel{B_1(R)} {\longleftrightarrow} e \Big\} \Big]  \le 2 \sum_{v \in \Lambda_R} \P_p [ \{0 \longleftrightarrow v \} ]. \]

For the second statement define instead

\[ \Wc:=  \Big\{ e \in B_k(R) \Big| \big\{ e \stackrel{B_k(R)}{\longleftrightarrow}  \{-R\}\times[-kR,kR]^{d-1} \big\} \Big\} .\]

Then consider the algorithm that sequentially reveals $\Wc$ starting from the vertical hyperplane $  \{-R\}\times[-kR,kR]^{d-1}$. This determines $\textrm{Cross}_k(R)$ since any crossing of $B_k(R)$ intersects the hyperplane $\{-R\} \times [-kR, kR]^{d-1}$, and the revealments for edges in $B_k^+(R)$ are bounded by

\[ \max_{e \in B_k^+(R)}  \P_p \Big[ \Big\{e \stackrel{B_k(R)}{\longleftrightarrow}  \{-R\}\times[-kR,kR]^{d-1} \Big\} \Big] \le 2 \P_p[A_1(R)] . \]

For the third statement define instead

\[ \Wc:=\Big\{ e \in B_k(R) \Big|\ \big\{ e \stackrel{B_k(R)}{\doublepath}  \big( \{-R\}\times[-kR,kR] \big) \cup \big( [-R,R]\times\{-kR\} \big) \big\} \Big\} \]

and consider the algorithm that sequentially reveals $\Wc$ starting from the union of the vertical and horizontal lines $\{-R\}\times[-kR,kR]$ and $[-R,R]\times\{-kR\}$. This determines $\textrm{Cross}_k(R)$, since if we reveal all interfaces that intersect these vertical and horizontal lines then we also determine $\textrm{Cross}_k(R)$. Moreover the revealments for edges in $B_k^\dagger(R)$ are bounded by

\begin{equation*}
\max_{e \in B_k^\dagger(R)} \P_p \Big[ \Big\{e \stackrel{B_k(R)}{\doublepath} \big( \{-R\}\times[-kR,kR] \big) \cup \big( [-R,R]\times\{-kR\} \big)  \Big\} \Big]  \le 2 \P_p[A_2(R)] .  \qedhere
\end{equation*}

§.§ Proof of Propositions <ref> and <ref>

We prove a general bound valid for arbitrary events, which extends a result from [40] (see also <cit.> and [50] for similar arguments):

Let $p, q \in (0,1)$, let $A$ be an event depending on a finite number of edges, let $\mathcal{A}$ be an algorithm determining $A$, and let $\mathcal{E}' \subseteq\mathcal{E}$ be a subset of edges. Then

\begin{equation}
\label{e:genub1}
|\mathbb{P}_{p;q}^{\mathcal{E}'}[A]  - \mathbb{P}_p[A] | \le  \max \! \Big\{ \!   \frac{1}{\sqrt{p(1-p)}}, \frac{1}{\sqrt{q(1-q)}} \! \Big\} |p-q|  \sqrt{  \max\{ \mathbb{P}_p[A] , \mathbb{P}_{p;q}^{\mathcal{E}'}[A] \}   \E_p  |\Wc_{\mathcal{E}'}|    }
\end{equation}

where $\P_{p; q}^{\mathcal{E}'}$ denotes the modification of $\mathbb{P}_p$ in which the parameter on $\mathcal{E}'$ is set to $q$ (remaining at $p$ on other edges), and $\Wc_{\mathcal{E}'}$ is the set of edges in $\mathcal{E}'$ that are revealed by $\mathcal{A}$. In particular,

\begin{equation}
\label{e:genub2}
\Big| \sum_{e \in \mathcal{E}'} \frac{\partial}{\partial p_e}  \mathbb{P}_p[A] \Big| \le \frac{1}{\sqrt{p(1-p)}}  \sqrt{ \P_p[A] \E_p  |\Wc_{\mathcal{E}'}| } ,
\end{equation}

where $\frac{\partial}{\partial p_e}$ denotes the derivative with respect to the parameter on $e$.

Our proof of Proposition <ref> is different to previous approaches in the literature (see Remark <ref>), and relies on properties of the relative entropy. For $P$ and $Q$ probability measures on a common measurable space, the relative entropy (or Kullback-Leibler divergence) from $P$ to $Q$ is defined as

\[   D_{KL}(P || Q) := \int \log \Big( \frac{dP}{dQ} \Big) \, dP  \]

if $P$ is absolutely continuous with respect to $Q$, and $D_{KL}(P || Q) := \infty$ otherwise; $D_{KL}(P || Q)$ is non-negative by Jensen's inequality. If $X$ and $Y$ are random variables taking values in a common measurable space, with respective laws $P$ and $Q$, we also write $D_{KL}(X || Y)$ for $D_{KL}(P||Q)$. We shall need two basic properties of the relative entropy (see <cit.>):

* (Chain rule) Let $X = (X_1, X_2)$ and $Y = (Y_1, Y_2)$ be random variables taking values in a common product measurable space. Then

\begin{equation}
\label{e:chain}
D_{KL}(X || Y) = D_{KL}(X_1 || Y_1) +  \mathbb{E}_{x \sim X_1} \big[  D_{KL}( (X_2 | X_1 = x)  || (Y_2 | Y_1 = x ) ) \big] .
\end{equation}

* (Contraction) Let $X$ and $Y$ be random variables taking values in a common measurable space and let $F$ be a measurable map from that space. Then

\begin{equation}
\label{e:contract}
D_{KL}( X || Y ) \ge  D_{KL}( F(X) || F(Y) )  .
\end{equation}

We first state a simple lemma on the relative entropy of stopped sequences of i.i.d. random variables. A stopping time for a real-valued sequence $X = (X_i)_{i \ge 1}$ is a positive integer $\tau = \tau(X)$ such that $\{\tau \ge n + 1\}$ is determined by $(X_i)_{i \le n}$. We define the corresponding stopped sequence $X^\tau = (X^\tau_i)_{i \ge 1}$ as $X^\tau_i = X_i$ for $i \le \tau$, and $X^\tau_i = \dagger$ for $i > \tau$, where $\dagger$ is an arbitrary symbol.

Let $X = (X_i)^n_{i \ge 1}$ and $Y = (Y_i)^n_{i \ge 1}$ be finite real-valued sequences of i.i.d. random variables with respective univariate laws $\mu$ and $\nu$, let $\tau \le n$ be a stopping time, and let $X^\tau$ and $Y^\tau$ be the corresponding stopped sequences. Then

\[ D_{KL} \big(   X^\tau \big\|   Y^\tau \big)  =  \E[\tau(X)]  \, D_{KL}( \mu \| \nu )   .   \]

Define $X^{k \wedge \tau} =  (X^\tau_i)_{i \le k}$ and analogously for $Y$. By the chain rule (<ref>), for $1 \le k \le n-1$,

\begin{align*}
& D_{KL} \big(   X^{(k+1) \wedge \tau} \big\|   Y^{(k+1) \wedge \tau} \big) \\
&  \quad  =  D_{KL} \big(   X^{k \wedge \tau}  \big\| Y^{k \wedge \tau}  \big)   \! +  \E_{x \sim (X^\tau_i)_{i \le k}} \!  \big[ D_{KL} \! \left( X^\tau_{k+1} \big| (X^\tau_i)_{i \le k} \! = \! x  \big\| Y^\tau_{k+1}  \big| (Y^\tau_i)_{i \le k}  \! = \! x \right)  \! \big]  \\
&  \quad  =  D_{KL} \big(   X^{k \wedge \tau}  \big\| Y^{k \wedge \tau}  \big)   \! +  \E_{x \sim (X^\tau_i)_{i \le k}} \!  \big[  \id_{\tau(X) \ge k+1} D_{KL} \! \left( X_{k+1} \big| (X^\tau_i)_{i \le k} \! = \! x  \big\| Y_{k+1}  \big| (Y^\tau_i)_{i \le k}  \! = \! x \right)  \! \big]  \\
&   \quad =  D_{KL} \big(   X^{k \wedge \tau}  \big\| Y^{k \wedge \tau}  \big)   \! +\P[\tau(X)\ge k+1]  D_{KL}( \mu \| \nu ) \end{align*}

where in the last step we used that $\tau$ is a stopping time. Hence, by induction,

\begin{equation*}
D_{KL} \big(   X^\tau \big\|   Y^\tau \big)   =   \sum_{1 \le k \le n-1} \P[\tau(X) \ge k+1] D_{KL}( \mu \| \nu )  =    \E[\tau(X)] D_{KL}( \mu \| \nu ) .   \qedhere
\end{equation*}

We also need a variant of Pinsker's inequality:

Let $P$ and $Q$ be probability measures on a common measurable space and let $A$ be an event. Then

\[ |P(A) - Q(A)| \le  \sqrt{ 2 \max\{ P(A), Q(A) \} D_{KL}(P \| Q)} .  \]

We use a standard reduction to the binary case. Let $\textrm{Ber}(x)$ and $\textrm{Ber}(y)$ be Bernoulli random variables with respective parameters $x := P(A) $ and $y := Q(A)$. By the contraction property (<ref>) $D_{KL}(P \| Q) \ge D_{KL}( \textrm{Ber}(x) \| \textrm{Ber}(y))$, so it suffices to prove that

\begin{equation}
\label{e:pinsker}
(x-y)^2 \le    2 \max\{x,y \}   D_{KL}( \textrm{Ber}(x) \| \textrm{Ber}(y)) .
\end{equation}

If $x \in \{0,1\}$ or $y \in \{0, 1\}$ then (<ref>) is trivial since either the right-hand side is infinite (if $x \neq y$) or both sides are zero (if $x=y$). On the other hand, if $x,y \in (0, 1)$ then

\begin{align*}
& D_{KL}( \textrm{Ber}(x) \| \textrm{Ber}(y))  :=   x \log \frac{x}{y} +  (1-x)  \log \frac{1-x}{1-y}   = \int_y^x  \frac{x-s}{s(1-s)} ds   \\
& \qquad  \ge \frac{1}{  \max\{ x, y \} }  \int_y^x  (x-s)  ds  =   \frac{1}{   2 \max\{ x, y \} }  (x-y)^2
\end{align*}

where we used that $\sup_{ s \in [a, b] } s(1-s) \le \max\{  a, b \} $ for $0 \le a \le b \le 1$.

In the proof we could replace $\max\{ x,y \} $ with $\min\{ \max\{ x,y \} , 1/4 \}$, which recovers the classical Pinsker's inequality $d_{TV}(P, Q) := \sup_A |P(A) - Q(A)| \le  \sqrt{ D_{KL}(P \| Q) / 2 } $.

Recall that $\mathcal{W}_{\mathcal{E}'}$ denotes the edges in $\mathcal{E}'$ that are revealed by the algorithm, and let $W = (W_i)_{i \le |\mathcal{W}_{\mathcal{E}'}|}$ denote the configuration on $\mathcal{W}_{\mathcal{E}'}$ listed in the order of revealment. Moreover let $W'$ denote the configuration on edges in $\mathcal{E} \setminus \mathcal{E}'$

First suppose that the algorithm $\mathcal{A}$ depends only on the configuration (i.e. there is no auxiliary randomness). Then the event $A$ is measurable with respect to $(W, W')$, and so by Lemma <ref>

\[   |\mathbb{P}_{p;q}^{\mathcal{E}'}[A]  - \mathbb{P}_p[A] |  \le \sqrt{ 2 \max\{  \mathbb{P}_p[A] ,  \mathbb{P}_{p;q}^{\mathcal{E}'}[A]   \}      D_{KL}( (X, Z)  || (Y, Z) )    ]  }  \]

where $(X,Z)$ (resp. $(Y,Z)$) is a random variable with the law of $(W,W')$ under $\P_p$ (resp. $\P_{p;q}^{\mathcal{E}'}$). Moreover, conditionally on $W'$, $W$ has the law, under $\P_p$ (resp. $\mathbb{P}_{p;q}^{\mathcal{E}'}$), of a sequence of i.i.d. Bernoulli random variables with parameter $p$ (resp. $q$) stopped at the stopping time $|\mathcal{W}_{\mathcal{E}'}|$. Hence by the chain rule for the Kullback-Liebler divergence and Lemma <ref>,

\[ D_{KL}( (X, Z)  || (Y, Z) )  =  \E \big[  D_{KL}( (X | \mathcal{F}_Z)  || (Y | \mathcal{F}_Z) ) \big] =   \E_p |\mathcal{W}_{\mathcal{E}'}|  D_{KL}(\Ber(p) \| \Ber(q) )   \]

where $\mathcal{F}_{Z}$ denotes the $\sigma$-algebra generated by $Z$. Combining we have

\begin{equation}
\label{e:genub3}
|\mathbb{P}_{p;q}^{\mathcal{E}'}[A]  - \mathbb{P}_p[A] |  \le \sqrt{ 2 \max\{  \mathbb{P}_p[A] ,  \mathbb{P}_{p;q}^{\mathcal{E}'}[A]   \}     \E_p |\mathcal{W}_{\mathcal{E}'}|  D_{KL}(\Ber(p) \| \Ber(q) )      }  .
\end{equation}

Finally since

\begin{align*}
& D_{KL}(\Ber(p) \| \Ber(q) )   := p\log\frac{p}{q}+(1-p)\log\frac{1-p}{1-q}  =  \int_q^p  \frac{p-s}{s(1-s)} ds \\
&  \qquad  \le \max\Big\{   \frac{1}{p(1-p)}, \frac{1}{q(1-q)}   \Big\}  \int_q^p (p-s) ds = \max\Big\{   \frac{1}{2p(1-p)}, \frac{1}{2q(1-q)}   \Big\} (p-q)^2
\end{align*}

the proof is complete.

The general case follows by averaging over any auxiliary randomness in the algorithm, since by Jensen's inequality $\E[ \sqrt{  \E[| \mathcal{W}_{\mathcal{E}'} | \mathcal{G} ] } ] \le \E[ \sqrt{ | \mathcal{W}_{\mathcal{E}'} |  } ]$ for any sub-$\sigma$-algebra $\mathcal{G}$.

For comparison we sketch an alternative approach which is closer to that appearing in previous works (e.g. [40]); this leads to the bound

\begin{equation}
\label{e:ubalt}
\Big| \sum_{e \in \mathcal{E}'} \frac{\partial}{\partial p_e}  \mathbb{P}_p[A] \Big|  \le \frac{1}{p(1-p)}  \sqrt{   \P_p[A]  \E_p  |\Wc_{\mathcal{E}'}|}
\end{equation}

which is comparable to (<ref>), although we believe it to be less general than the non-differential statement (<ref>) (in particular, it does not seem straightforward to obtain (<ref>) from (<ref>)).

Consider Russo's formula

\begin{align}
\label{e:russocov}
\Big| \sum_{e \in \mathcal{E}'} \frac{\partial}{\partial p_e}  \mathbb{P}_p[A] \Big|  & =\frac{1}{p(1-p)} \Big| \sum_{e \in \mathcal{E}'} \cov_p(\id_A,\id_{e \text{ open}}) \Big|
\end{align}

and decompose the sum as

\[\sum_{e \in \mathcal{E}'}   \cov_p \left(\one_A \one_{\rev(e)},\id_{e \text{ open}} \right)+\sum_{e \in \mathcal{E}'}  \cov_p\left(\one_A \one_{\rev(e)^\compl},\id_{e \text{ open}}\right) \]

where $\rev(e)$ denotes the event that $e$ is revealed by the algorithm. One can check that $\one_A\one_{\rev(e)^\compl}$ is independent of $\id_{e \text{ open}}$ and so the second sum vanishes. Hence (<ref>) is at most

\[ \frac{1}{p(1-p)} \Big| \sum_{e \in \mathcal{E}'}  \cov_p\left(\one_A \one_{\rev(e)},\id_{e \text{ open}} \right)  \Big| \leq  \frac{1}{p(1-p)}  \sqrt{ \P_p[A] \E_p \Big[ \Big( \sum_{e \in \mathcal{E}'}  \one_{\rev(e)}(\id_{e \text{ open}}-p)\Big)^2\Big] }  \]

where we used the the Cauchy-Schwartz inequality. For edges $e$ and $f$ introduce the event

\[ \rev(e,f):=\rev(e)\cap\rev(f)\cap\{e \text{ is revealed before }f\}. \]

Again one checks that, for $e\neq f$, $\one_{\rev(e,f)}(\id_{e \text{ open}}-p)$ is independent of $\id_{f \text{ open}}$. Hence

\[ \E_p \Big[\Big(\sum_{e \in \mathcal{E}'}  \one_{\rev(e)}(\id_{e \text{ open}}-p)\Big)^2\Big]   = \sum_{e \in \mathcal{E}'} \E_p \left[\one_{\rev(e)}(\id_{e \text{ open}}-p)^2\right]  \le \sum_{e \in \mathcal{E}'}   \E_p[ \id_{\rev(e)} ] = \E_p |\Wc_{\mathcal{E}'} | , \]

since off-diagonal terms are zero by independence, and we used that $(\id_{e \text{ open}}-p)^2 \le 1$. Combining the above gives (<ref>).

We can now complete the proof of Propositions <ref> and <ref>:

This follows directly from (<ref>) (with $\mathcal{E}' = \mathcal{E}$) by considering the algorithm in Lemma <ref> that determines $A_1(R)$ such that

\begin{equation*}  \E_p | \mathcal{W}_{\mathcal{E}'} | = \sum_{e \in \mathcal{E}}  \textrm{Rev}(e) \le 2 \sum_{v \in \Lambda_R}  \P_p[ 0 \longleftrightarrow v] . \qedhere
\end{equation*}

For $d\ge 2$, recall the box $B_{k}(R)$ and its right half $B_k^+(R) := [0, R] \times [-kR, kR]^{d-1}$. Consider the algorithm in Lemma <ref> that determines $\textrm{Cross}_k(R)$ such that

\[  \sum_{e \in B^+_k(R)} \text{Rev}(e) \le  c R^d \max_{e \in B^+_k(R)} \text{Rev}(e) \le 2 c R^d  \, \P_p[A_1(R)] .\]

for $c = c(k) > 0$. By reflective symmetry in the vertical axis,

\[ \frac{d}{d p} \P_p[\textrm{Cross}_k(R) ] = \sum_{e \in B_k(R)}  \frac{\partial}{\partial p_e} \P_p[\textrm{Cross}_k(R) ] \le 2 \sum_{e \in B_k^+(R)} \frac{\partial}{\partial p_e} \P_p[\textrm{Cross}_k(R) ]  \]

and hence, applying (<ref>) (with $\mathcal{E}' = B_k^+(R)$)

\[ \frac{d}{d p} \P_p[\textrm{Cross}_k(R) ]  \le \frac{1}{\sqrt{p(1-p)}}    \sqrt{\E_p  |\Wc_{\mathcal{E}'}|   }  \le  \frac{\sqrt{2c} \, R^{d/2}}{\sqrt{p(1-p)} } \sqrt{\P_p[A_1(R)] } . \]

For $d=2$, recall the top-right quarter $B_k^\dagger(R) := [0, R] \times [0,kR]$ of the box $B_k(R)$. Consider the algorithm in Lemma <ref> that determines $\textrm{Cross}_k(R)$ such that

\[  \sum_{e \in B^\dagger_k(R)} \text{Rev}(e)   \le  c R^2  \max_{e \in B_k^\dagger(R)} \text{Rev}(e) \le  2 c R^2 \, \P_p[A_2(R)]  \]

for $c = c(k) > 0$. Again by reflective symmetry (this time in both axes)

\[ \frac{d}{d p} \P_p[\textrm{Cross}_k(R) ] = \sum_{e \in B_k(R)}  \frac{\partial}{\partial p_e} \P_p[\textrm{Cross}_k(R) ] \le 4 \sum_{e \in B_k^\dagger(R) } \frac{\partial}{\partial p_e} \P_p[\textrm{Cross}_k(R) ]  ,\]

and the result follows from (<ref>) (with $\mathcal{E}' = B^\dagger_k(R)$) as in the previous case.

§.§ Proof of Proposition <ref>

We begin by introducing the OSSS inequality. Let $X =  (X_i)_{i=1}^n$ be a finite sequence of independent random variables taking values in arbitrary probability spaces, and let $A$ be an event. Then the resampling influence of $X_i$ on $A$ is

\begin{equation}
\label{e:infl}
\Infl(i) := \mathbb{P}[  \id_{X \in A} \neq \id_{X^{(i)} \in A} ]
\end{equation}

where $X^{(i)}$ denotes $X$ with the coordinate $X_i$ resampled.

For every algorithm $\mathcal{A}$ determining $A$,

\[ \Var(\one_A)\leq \frac{1}{2} \sum\limits_{i=1}^n \textrm{Rev}(i)\Infl(i) \]

where $\textrm{Rev}(i)$ is the revealment of $X_i$ under $\mathcal{A}$.

Returning to the setting of Bernoulli percolation, combining the OSSS inequality with Russo's formula yields the following:

Let $p \in (0, 1)$, let $A$ be an increasing event depending on a finite number of edges, let $\mathcal{A}$ be an algorithm determining $A$, and let $\mathcal{E}' \subseteq\mathcal{E}$ be a subset of edges. Then

\[ \sum_{e \in \mathcal{E}'} \frac{\partial}{\partial p_e} \P_p[A] \geq \frac{4}{p(1-p)}\frac{ \Var_p \big[  \P_p[A   \: | \: \mathcal{F}_{\mathcal{E}'} ] \big]}{\max_{e \in \mathcal{E}'} \textrm{Rev}(e)} ,\]

where $\mathcal{F}_{\mathcal{E}'}$ is the $\sigma$-algebra generated by the edges in $\mathcal{E}'$, and the revealements $\textrm{Rev}(e)$ are under $\P_p$.

If $p=1/2$, the quantity $\Var_p [  \P_p[A   |  \mathcal{F}_{\mathcal{E}'} ]  ] $ has an interpretation as the square-sum of the Fourier coefficients of $\id_A$ supported on non-empty subsets of $\mathcal{E}'$ (see, e.g., [21]).

Let $X_0$ denote the vector of configurations on edges $e \notin \mathcal{E'}$, and $(X_e)_{e \in \mathcal{E}'}$ be the configuration on the remaining edges. Then by the OSSS inequality (Theorem <ref>) applied to $X = (X_0, (X_e)_{e \in \mathcal{E}'})$, and bounding the revealment of $X_0$ by $1$,

\[  \Var_p(\one_A) \le  \frac{1}{2} \Big( \Infl(0) +   \sum_{e \in \mathcal{E}'} \textrm{Rev}(e) \Infl(e) \Big) \]

where $\Infl(0)$ and $\Infl(e)$ are defined as in (<ref>) under $\P_p$. Next observe that

\begin{align*}
\frac12 \Infl(0) & =  \frac{1}{2} \E_p \big[ \P_p[ \text{the outcome of $A$ changes when the edges $e \notin \mathcal{E}'$ are resampled}  \: | \: \mathcal{F}_{\mathcal{E}'}  ] \big] \\
&=  \E_p \big[ \P_p[A  \: | \: \mathcal{F}_{\mathcal{E}'}] (1- \P_p[A  \: | \: \mathcal{F}_{\mathcal{E}'} ]) \big] = \E_p \big[ \Var_p[\id_A  \: | \: \mathcal{F}_{\mathcal{E}'} ]  \big] ,
\end{align*}

and hence, by the law of total variance,

\[ \Var_p(\one_A)  -   \Infl(0)/2  =    \Var_p(\one_A)  - \E_p \big[ \Var_p[\id_A  \: | \: \mathcal{F}_{\mathcal{E}'} ]  \big]  =  \Var_p\big[ \P_p[A  \: | \: \mathcal{F}_{\mathcal{E}'} ]  \big] .  \]

This yields the following extension of the OSSS inequality

\begin{equation}
\label{e:OSSSext}
\Var_p \big[ \P_p[A  \: | \: \mathcal{F}_{\mathcal{E}'} ]  \big]  \le  \frac{1}{2} \sum_{e \in \mathcal{E}'} \textrm{Rev}(e) \Infl(e) \le    \frac{ \max_{e \in \mathcal{E}'} \textrm{Rev}(e)}{2} \sum_{e \in \mathcal{E}'} \Infl(e).
\end{equation}

We deduce the result by combining with Russo's formula for increasing events, namely

\[ \sum_{e \in \mathcal{E}'} \frac{\partial}{\partial p_e} \P_p[A] = \frac{2}{p(1-p)} \sum_{e \in \mathcal{E}'} \Infl(e)   \]

(which coincides with (<ref>) since $\cov_p(\one_A, \one_{e \text{ open}})=2 \Infl(e)$ for increasing $A$).

Recall the top-right quarter $B_k^\dagger(R)$ and set $\mathcal{E}' = B_k^\dagger(R)$. We claim

\begin{equation}
\label{e:var}
\textrm{Var}_p \big[ \P_p [ \textrm{Cross}_k(R)  \: | \: \mathcal{F}_{\mathcal{E}'} ] ]  \ge  \P_p[  \textrm{Cross}_{1/(8k)}(kR) ]^4 (1- \P_p[  \textrm{Cross}_{8k}(R/8) ] )^2   .
\end{equation}

Assuming (<ref>), the statement follows by applying Proposition <ref> to the algorithm in Lemma <ref> that determines $\textrm{Cross}_k(R)$ whose revealments on $B_k^\dagger(R)$ are bounded by $2 \P_p[A_2(R)]$.

To prove (<ref>), remark first that, for any event $A$ and sub-$\sigma$-algebra $\mathcal{G}$,

\begin{align}
\label{e:varbound}
\textrm{Var} [ \P [ A | \mathcal{G} ] ]   =  \E [   (  \P [ A | \mathcal{G} ]  - \P[A] )^2 ]   & \ge    \sup_{A' \in \mathcal{G}}  \E [   (  \P [ A | \mathcal{G} ]  - \P[A] )^2 \, \id_{A'} ]  \\
\nonumber & \ge \sup_{A' \in \mathcal{G}} \P[A'] ( \P[A | A' ] - \P[A]   )^2
\end{align}

where the second inequality is Jensen's. Hence it is enough to construct an event $A'$, measurable with respect to the configuration on the top-right quarter, such that $ \textrm{Cross}_k(R)$ becomes substantially more likely if $A'$ occurs (see Figure <ref> for an illustration).

\begin{align*}
& A' :=  \Big\{ \{R/4\} \times [R/4,R/2]  \stackrel{[R/4,R] \times [R/4,R/2]}{\longleftrightarrow} \{R\} \times[R/4,R/2]  \Big\} \\
&  \qquad \qquad  \cap  \Big\{ [R/4,R/2] \times \{R/4\}  \stackrel{[R/4,R/2] \times [R/4,kR]}{\longleftrightarrow} [R/4,R/2] \times \{kR\}  \Big\} ,
\end{align*}

which is measurable with respect to $\mathcal{F}_{\mathcal{E}'}$. By the FKG inequality and symmetry (and an obvious event inclusion), $\P_p[A'] \ge \P_p[ \textrm{Cross}_{1/(8k)}(kR)]^2$. Define also the events

\begin{align*}
B_1 & :=   \Big\{ \{-R\} \times [R/2,3R/4]  \stackrel{[-R,R/2] \times [R/2,3R/4]}{\longleftrightarrow} \{R/2\} \times[R/2,3R/4]  \Big\}   \\
B_2 &:=    \Big\{ \{3R/4\}  \times [-kR,kR]  \stackrel{[3R/4,R] \times [-kR, kR]}{\longleftrightarrow} \{R\} \times [-kR,kR]  \Big\}
\end{align*}

which are defined on disjoint domains and are translated copies of, respectively, $\textrm{Cross}_{1/6}(3R/2)$ and $\textrm{Cross}_{8k}(R/8)$. Finally, define

\[ C \! := \! \! \Big\{ \! \{-R\} \times [-kR, kR] \stackrel{B_k(R)}{\longleftrightarrow} \big( \{R/2\} \times [R/2,kR]  \big) \! \cup \! \big( [R/2,R] \times \{R/2\} \big) \! \cup \! \big(  \{R\} \times [-kR, R/2] \big) \!  \Big\}  \]

and observe (i) $\textrm{Cross}_k(R) \subseteq C$, (ii) on $A'$, $\textrm{Cross}_k(R) = C$, and (iii) $B_1 \cap B_2^\compl \subseteq C \setminus \textrm{Cross}_k(R)$. Hence

\begin{align*}
\P_p [ \textrm{Cross}_k(R)  | A' ]  - \P_p [ \textrm{Cross}_k(R) ]  & = \P_p[C | A' ] - \P_p[ \textrm{Cross}_k(R) ]  \ge \P_p[C] -  \P_p[ \textrm{Cross}_k(R) ]   \\
& = \P_p[ C \setminus \textrm{Cross}_k(R) ]  \ge \P_p[B_1 \cap B_2^\compl]   = \P_p[B_1] (1-\P_p[B_2])  \\
& \ge \P_p[  \textrm{Cross}_{1/(8k)}(kR) ]  \big(1- \P_p[  \textrm{Cross}_{8k}(R/8) ] \big) ,
\end{align*}

where the second step is by the FKG inequality, the penultimate step uses disjoint domains, and the final step is an obvious event inclusion. Applying (<ref>) (with $A = \textrm{Cross}_k(R)$ and $\mathcal{G} = \mathcal{F}_{\mathcal{E}'}$) gives (<ref>).

An illustration of the proof of (<ref>). The first panel shows the event $A'$. The second illustrates how, on $A'$, the event $C$ is equivalent to $\textrm{Cross}_k(R)$. The third shows how the crossing given by $B_1$, combined with the dual crossing given by $B_2^\compl$, realises $C$ but not $\textrm{Cross}_k(R)$.

§.§ A general bound for revealments of increasing events

Combining Propositions <ref> and <ref> yields a general lower bound on the revealments of increasing events:

In the setting of Proposition <ref> (in particular the event $A$ is increasing),

\[   \max_{e \in \mathcal{E}'} \textrm{Rev}(e) \ge   \frac{ \big(4  \Var_p \big[ \, \P_p[A  \: | \: \mathcal{F}_{\mathcal{E}'} ]  \big] \big)^{2/3} }{ (p(1-p) \P_p[A] |\mathcal{E}'|)^{1/3}}   .\]

By (<ref>) and Proposition <ref> we have

\begin{align*}
\frac{4}{p(1-p)} \frac{  \Var_p \big[ \, \P_p[A  \: | \: \mathcal{F}_{\mathcal{E}'} ]  \big] }{  \max_{e \in \mathcal{E}'} \textrm{Rev}(e) } & \le \sum_{e \in \mathcal{E}'} \frac{\partial}{\partial p_e} \P_p[A] \\
& \le \frac{1}{\sqrt{p(1-p)}} \sqrt{\P_p[A] \E_p |\Wc_{\mathcal{E}'}| }  \le \frac{1}{\sqrt{p(1-p)}} \sqrt{\P_p[A] |\mathcal{E}'| \max_{e \in \mathcal{E}'} \textrm{Rev}(e) }
\end{align*}

and rearranging gives the result.

Proposition <ref> generalises a result from [8] which considered the case $p = 1/2$ and $\mathcal{E}'$ is the set of edges on which $A$ depends; denoting by $n$ the cardinality of this set of edges, this gives

\begin{equation}
\label{e:bsw}
\max_e \textrm{Rev}(e) \ge \frac{ \big( 8 \Var_{1/2}[ \id_A ] \big)^{2/3}}{ (\P_{1/2}[A] n)^{1/3}}
\end{equation}

which is comparable to <cit.>, although (<ref>) has a stronger constant.

§ LEVEL SET PERCOLATION OF GAUSSIAN FIELDS

We now establish our main results in the case of Gaussian percolation; the proof will closely follow the approach for Bernoulli percolation in Section <ref>. For $k, R > 0$, recall the box $B_k(R):=  [-R, R] \times [-kR, kR]^{d-1}$, which we now view as a subset of $\mathbb{R}^d$. Then define

\[  \textrm{Cross}_k(R) := \Big\{ \{-R\} \times [-kR,kR]^{d-1}  \stackrel{B_k(R)}{\longleftrightarrow} \{R\} \times[kR,kR]^{d-1}  \Big\}  \]

\[ \{ A  \stackrel{E}{\longleftrightarrow} B \} :=  \{ \text{there exists a path in $\{f \ge 0\} \cap E$ that intersects $A$ and $B$}\}  . \]

For $0 \le r \le R$ define

\[A_1(r,R):=\{ \Lambda_r \longleftrightarrow \partial \Lambda_R\}  \qquad \text{and} \qquad A_2(r,R):=\{ \Lambda_r   \doublepath \partial \Lambda_R\} \]

\[\{A   \stackrel{E}{\doublepath} B\} = \{A    \stackrel{E}{\longleftrightarrow}B  \}\cap \{ \text{there exists a path in $\{f  \le 0\} \cap E$ that intersects $A$ and $B$}\}  , \]

and $\{A \doublepath B \} = \{A  \stackrel{\R^d}{\doublepath} B \}$. By continuity of $f$, if $d=2$ then $A_2(r, R)$ could equivalently be defined as

\[      A_2(r,R)=   \{ \text{there exists a path in $\{f  = 0\}$ that intersects $\Lambda_r$ and $\partial \Lambda_R$}\} . \]

We make the elementary observation that $\P_{\ell_c}[ A_2(r, R)] \le \P_{\ell_c}[A_1(r, R)]$, and moreover if $d=2$ and under (<ref>) (so the FKG inequality is available; c.f. (<ref>)) then

\begin{equation}
\label{e:eta1eta22}
\P_{\ell_c}[ A_2(r, R)] \le \P_{\ell_c}[A_1(r, R)]^2 .
\end{equation}

We now state the analogues of Propositions <ref>–<ref>, which concern Gaussian fields $f = q \star W$ with finite-range dependence. Recall the Dini derivatives, defined for $f: \R \to \R$ as

\[ \frac{d^+}{dx}f(x)=\limsup\limits_{\varepsilon \downarrow 0}\frac{f(x+\varepsilon)-f(x)}{\varepsilon} \quad \text{and} \quad \frac{d^-}{dx}f(x)=\liminf\limits_{\varepsilon \downarrow 0}\frac{f(x+\varepsilon)-f(x)}{\varepsilon} .\]

Suppose $f = q \star W$ satisfies Assumption <ref> and (<ref>)–(<ref>), and let $r  >  0$ be such that $q$ is supported on $\Lambda_r$. Then for $\ell \le \ell'$ and $R \ge r \ge 1$,

\[ \mathbb{P}_{\ell'}[ A_1(1,R)] - \mathbb{P}_\ell[ A_1(1,R)]   \le \frac{r^{d/2}(\ell'-\ell)}{\int q}  \sqrt{  \mathbb{P}_{\ell'}[A_1(1,R)]   \! \! \sum_{v \in r \Z^d \cap \Lambda_{R+2r}} \! \! \P_\ell[ \Lambda_1 \longleftrightarrow v + \Lambda_{6r} ]}  . \]

Suppose $f = q \star W$ satisfies Assumption <ref> and (<ref>)–(<ref>), and let $r  >  0$ be such that $q$ is supported on $\Lambda_r$. Then for $k \ge 1$ there exists $c = c(k)>0$ such that, for $\ell \in \mathbb{R}$ and $R \ge 4r > 0$,

\[ \frac{d^+}{d \ell} \mathbb{P}_\ell[ \textrm{Cross}_k(R)] \leq  \frac{c   R^{d/2}}{\int q}
\begin{cases} \sqrt{ \P_\ell[A_2(2r,R-2r)] } & d=2, \\  \sqrt{ \P_\ell[A_1(2r,R-2r)] }  & d\ge2.
\end{cases} \]

Suppose $f = q \star W$ satisfies Assumption <ref> and (<ref>)–(<ref>), and let $r  >  0$ be such that $q$ is supported on $\Lambda_r$. Then for $k \ge 1$ there exists $c = c(k)>0$ such that, for $\ell \in \R$ and $R \ge 8r > 0$,

\begin{equation}
\label{e:lbgf1}
\frac{d^-}{d \ell} \mathbb{P}_\ell[ \textrm{Cross}_k(R)]  \geq  \frac{c}{ \|q\|_2 }\frac{ \P_\ell[\textrm{Cross}_k(R)]\big(1- \P_\ell[\textrm{Cross}_k(R)]\big) }{\frac{r}{R}  \sum_{i=2}^{R/r}\P_\ell[A_1(2r,ir)] }  ,
\end{equation}

and, if $d=2$ and (<ref>) holds,

\begin{equation}
\label{e:lbgf2}
\frac{d^-}{d \ell} \mathbb{P}_\ell[ \textrm{Cross}_k(R)] \geq   \frac{c}{\|q\|_2} \frac{ \P_\ell[\textrm{Cross}_{1/(8k)}(kR)]^4 \big(1 - \P_\ell[\textrm{Cross}_{8k}(R/8)] \big)^2 }{  \P_\ell[A_2(2r,R-2r)]} .
\end{equation}

We prove Propositions <ref>–<ref> later in the section; for now we establish our main result Theorems <ref>. For this we need two auxiliary results; these are rather standard, but we give details on their proof at the end of the section. The first is the analogue of Lemma <ref>:

Suppose $f = q \star W$ satisfies Assumption <ref> with parameter $\beta>d$.

* There exists $\delta > 0$ and $\ell' = \ell'(R) \le \ell_c$ such that, for $R \ge 1$,

\[ \mathbb{P}_{\ell'}[\textrm{Cross}_5(R)] =  \delta .  \]

* (RSW) Let $d=2$ and $k > 0$ and suppose that (<ref>) holds. Then there exists $\delta > 0$ such that, for $R \ge 1$,

\[ \P_{\ell_c}[\textit{Cross}_k(R)] \in (\delta, 1-\delta) .\]

The second allows us to compare a Gaussian field with an approximation that satisfies (<ref>). Fix a smooth symmetric cutoff function $\varphi: \R \to [0,1]$ such that $\varphi(x) = 1$ for $\|x\|_\infty \le 1/2$, $\varphi(x) = 0$ for $\|x\|_\infty \ge 1$. For $r > 0$ define

\begin{equation}
\label{e:fr}
f_r := q_r \star W
\end{equation}

where $q_r(x) := q(x) \varphi(|x|/r)$. Note that $q_r$ is supported on $\Lambda_r$, and also, since $q \in L^1(\R^d) \cap L^2(\R^d)$, as $r \to \infty$,

\begin{equation}
\label{e:qconv}
\|q_r\|_2 \to \|q\|_2  \qquad \text{and} \qquad \int q_r \to \int q.
\end{equation}

Remark that if either Assumption <ref> or (<ref>) holds for $f$ then it holds for $f_r$ (on the other hand, deducing this for (<ref>) seems difficult but we do not need it). In particular, as discussed in Section <ref>, if $d=2$ and Assumption <ref> holds for $f$ then $\ell_c(f) = \ell_c(f_r) = 0$.

The following lemma, essentially taken from [38], allows us to compare $f$ and $f_r$:

Suppose $f = q \star W$ satisfies Assumption <ref> with parameter $\beta>d$ and (<ref>). Then there exist $c_1, c_2 > 0$ such that, for $r, R \ge 2$, increasing event $A$ measurable with respect to $f|_{B(R)}$, and $\ell \in \R$,

\[ \left|\P_\ell[f\in A]-\P_\ell[f_r\in A]\right|\leq c_1 \big( R^{d/2} (\log R)  r^{-(\beta-d/2)} +  e^{ - c_2 (\log R)^2 } \big). \]

The same conclusion holds if $A$ is the intersection of one increasing and one decreasing event which are both measurable with respect to $f|_{B(R)}$.

We are now ready to prove Theorem <ref>:

In the proof $c > 0$ are constants that depend only on $f$ (and the choice of the cutoff function $\varphi$ in (<ref>)) and may change from line to line. The bound $\eta_1 \le d-1$, and also $\eta_1 \le 1/2$ if $d=2$ and (<ref>) holds, are rather classical; in fact they are true for any $\beta > d$. For the former, combining $\mathbb{P}_{\ell_c}[\textrm{Cross}_5(R)] \ge \delta$ (the first statement of Lemma <ref>) with the union bound applied along the hyperplane $\{0\} \times [-kR, kR]$ gives $\P_{\ell_c}[A_1(1, R)] \ge c R^{-(d-1)}$. For the latter, by combining the RSW estimates (the second statement of Lemma <ref>) with Lemma <ref> one can deduce (see [4, 38] for similar arguments)

\[ \P_{\ell_c}\big[   \{-R\} \times [-R,R]   \stackrel{B_1(R)}{\doublepath} \{R\} \times [-R,R]  \big]  \ge c \big( 1-   R^{1 -(\beta-1)}(\log R) \big) \ge c / 2 \]

for sufficiently large $R$. By the union bound applied along $\{0\} \times [-R, R]$ this implies $\P_{\ell_c}[A_2(1,R)] \ge c R^{-1}$, and given (<ref>) we see that  $\P_{\ell_c}[A_1(1,R)] \ge c R^{-1/2}$.

We now prove the remaining bounds, beginning with the first statement. Fix $1 > \alpha > \frac{d/2}{\beta-d/2}$ and $\eta_1 > \eta^\ast > 0$ (if $\eta_1 = 0$ there is nothing to prove). Then by monotonicity in $\ell$, the union bound, and the definition of $\eta_1$,

\[ \mathbb{P}_\ell[ A_1(r, R ) ]  \le  \mathbb{P}_{\ell_c}[ A_1(r,R) ]  \le c r^{d-1} \mathbb{P}_{\ell_c}[A_1(1, R-r)]  \le r^{d-1} R^{-\eta^\ast}   \]

for all $\ell \le \ell_c$, $R$ sufficiently large, and $r \in [1, R/2]$. Set $r = R^\alpha$. Then by an integral comparison,

\begin{align*}
\frac{r}{R} \sum_{i=2}^{R/r} \mathbb{P}_{\ell}[ A_1(2r,ir )] & \le  c  r^{-\eta^\ast+(d-1)}  \times  \frac{r}{R} \sum_{i=2}^{R/r} i^{-\eta^\ast}   \\
&  \le  c  r^{-\eta^\ast+(d-1)} (R/r)^{-\min\{\eta^\ast,1\}}(\log (R/r) ) \\
& \le c (\log R) \big( R^{\alpha(d-1-\eta^\ast) -(1-\alpha)\min\{\eta^\ast,1\} } \big)
\end{align*}

for $\ell \le \ell_c$ and large $R$. Consider the field $f_r$ defined in (<ref>). By Lemma <ref>,

\[ \P_\ell[f_r\in A_1(r', R)]  \le \P_\ell[A_1(r', R)]  + c R^{d/2  - \alpha(\beta-d/2)} (\log R) + c e^{ - c (\log R)^2 }  \]

for $\ell \le \ell_c$ and $2 \le r' \le R$, and hence

\[ \frac{r}{R} \sum_{i=2}^{R/r} \mathbb{P}_{\ell}[f_r \in A_1(2r,ir )]  \le c (\log R) \big( R^{\alpha(d-1-\eta^\ast) -(1-\alpha)\min\{\eta^\ast,1\} }  + R^{d/2 - \alpha(\beta-d/2)} \big) \]

for $\ell \le \ell_c$ and large $R$. Moreover, by Lemma <ref> there are $\delta > 0$ and $\ell' = \ell'(R) \le \ell_c$ such that $ \P_{\ell'}[\textrm{Cross}_5(R)] = \delta$. Hence, again by Lemma <ref>,

\[ \P_{\ell'}[f_r \in \textrm{Cross}_5(R)]\big(1-\P_{\ell'}[f_r \in \textrm{Cross}_5(R)]\big)  \ge \delta(1-\delta) - c R^{d/2 - \alpha(\beta-d/2)} (\log R)  \ge \delta(1-\delta)/2   \]

for large $R$, where we used that $\alpha > \frac{d/2}{\beta-d/2}$.

We now apply Propositions <ref> and <ref> to the field $f_r$ at the sequence of levels $\ell'(R) \le \ell_c$. First, by (<ref>) (recalling (<ref>))

\begin{align}
\label{e:oab1gf}
\frac{d}{d \ell} \mathbb{P}_\ell[ f_r \in \textrm{Cross}_5(R)] \Big|_{\ell= \ell'}  & \ge \frac{c \delta(1-\delta)}{  \|q_r\|_2}  \Big( \frac{r}{R} \sum_{i=2}^{R/r} \mathbb{P}_{\ell'}[f_r \in A_1(2r,ir )] \Big)^{-1}  \\
\nonumber & \ge  c (\log R)^{-1}  \big( R^{\alpha(d-1-\eta^\ast) -(1-\alpha)\min\{\eta^\ast,1\} }  +  R^{d/2 - \alpha(\beta-d/2)}  \big) ^{-1}
\end{align}

for large $R$. Similarly, by Proposition <ref>,

\begin{align}
\label{e:oab2gf}
\frac{d}{d \ell} \mathbb{P}_\ell[ f_r \in \textrm{Cross}_5(R) ] \Big|_{\ell= \ell'} & \le  c R^{d/2 }  \Big(  \mathbb{P}_{l'}[f_r \in A_1(2r,R)] \Big)^{1/2}  \\
\nonumber & \le  c R^{d/2} \big( R^{- \eta^\ast + \alpha(d-1) }  +  R^{d/2 - \alpha(\beta-d/2) }(\log R) \big)^{1/2} \\
\nonumber & \le  c \sqrt{\log R} \big( R^{d/2- \eta^\ast/2 + \alpha(d-1)/2 }  +  R^{3d/4 - \alpha(\beta-d/2)/2} \big)
\end{align}

for large $R$, where we used that $\sqrt{a+b} \le \sqrt{a} + \sqrt{b}$ for $a,b > 0$. Comparing (<ref>) and (<ref>) and expanding the brackets we deduce that at least one of the exponents

\begin{align*}
& E_1 :=\big(3d/4 - \alpha(\beta-d/2)/2 \big) + \big(d/2 - \alpha(\beta-d/2) \big)  \\
& E_2 := \big(d/2- \eta^\ast/2 + \alpha(d-1)/2\big) + \big(d/2 - \alpha(\beta-d/2)\big)    \\
& E_3 := \big(d/2- \eta^\ast/2 + \alpha(d-1)/2 \big)  + \big( \alpha(d-1-\eta^\ast) - (1-\alpha)\min\{\eta^\ast, 1\} \big) \\
&  E_4 :=\big(3d/4 - \alpha(\beta-d/2)/2 \big) +  \big( \alpha(d-1-\eta^\ast) - (1-\alpha)\min\{\eta^\ast, 1\} \big)
\end{align*}

must be non-negative. The first is equivalent to $\alpha \le \frac{5d}{6(\beta-d/2)}$. The second implies that $\eta^\ast \le \frac{d}{3} + \alpha(d-1)$, assuming that $\alpha > \frac{5d}{6(\beta-d/2)}$. The third is equivalent to either $\eta^\ast \le \frac{d}{3}  + \alpha(d-1)$ (if $\eta^\ast \le 1$) or $\eta^\ast \le \frac{d-2+\alpha(3d-1)}{1+2\alpha}$ (if $\eta^\ast > 1$). Finally, the fourth implies either $\eta^\ast \le \frac{d}{3}  + \alpha(d-1)$ (if $\eta^\ast \le 1$, assuming that $\alpha > \frac{5d}{6(\beta-d/2)}$) or $\alpha \le \frac{3d-4}{2\beta-5d + 4}$ (if $\eta^\ast > 1$). One can check that, since $d\ge3$, $ \frac{5d}{6(\beta-d/2)} < \frac{3d-4}{2\beta-5d + 4}$ and $ \frac{d}{3}  + \alpha(d-1) <  \frac{d-2+\alpha(3d-1)}{1+2\alpha}$. Hence we conclude that if $ \alpha > \frac{3d-4}{2\beta-5d + 4}$ then $\eta^\ast \le  \frac{d-2+\alpha(3d-1)}{1+2\alpha}$. Sending $\alpha \to  \frac{3d-4}{2\beta-5d + 4}$ from above gives the result.

The proof of the remaining statements are similar, and closer to the arguments in Section <ref>. For the second statement, fix $1 > \alpha > \frac{3d/2-1}{\beta-d/2}$ and $\eta_1 > \eta^\ast > 0$. As in the proof of the first statement,

\begin{equation}
\label{e:oab3gf}
\mathbb{P}_{\ell_c}[ A_1(2r, R ) ]  \le r^{d-1} R^{-\eta^\ast}
\end{equation}

for large $R$ and $r \in [1, R/4]$. Now let $r = R^\alpha$. Since we have the a priori bound $\P_{\ell_c}[A_1(1, R) ] \ge c R^{-(d-1)}$ (from the start of the proof), by Lemma <ref>

\begin{align}
\label{e:compare}
| \P_{\ell_c}[f_r \in A_1(r', R')]  -  \P_{\ell_c}[A_1(r', R') ] | & \le   c R^{d/2  - \alpha(\beta-d/2)} (\log R) + c e^{ - c (\log R)^2 } \\
\nonumber & \le   \P_{\ell_c}[A_1(r', R')]  / 2
\end{align}

for large $R$ and $1 \le r' \le R' \le R$, where we used that $d/2 - \alpha(\beta-d/2) \le -(d-1)$ by the definition of $\alpha$. Observe next that, for $|x| \ge 18r$, the event $\Lambda_1 \longleftrightarrow x + \Lambda_{6r}$ implies the occurrence of the events

\[  \{   A_1(1, |x|_\infty/3)  \}   \qquad \text{and} \qquad \{  x + A_1(6r, |x|_\infty/3)  \}  , \]

which are measurable with respect to disjoint domains separated by distance $r$. Since $f_r$ is $r$-dependent, for large $R$ and $18r \le |x| \le R+2r$ this implies

\begin{align*}
\P_{\ell_c}[  f_r \in \Lambda_{2r} \longleftrightarrow x + \Lambda_{6r} ]  &  \le \P_{\ell_c}[  f_r \in A_1(1, |x|_\infty/3) ] \P_{\ell_c}[  f_r \in A_1(6r, |x|_\infty/3) ]  \\
& \le 4  \P_{\ell_c}[  A_1(1, |x|_\infty/3) ]  \P_{\ell_c}[  A_1(6r, |x|_\infty/3) ]  \\
& \le c  r^{d-1}  |x|_\infty^{-2\eta^\ast}
\end{align*}

where we used (<ref>) and then (<ref>). Then by an integral comparison, for large $R$,

\begin{align*}
\sum_{v \in r \Z^d \cap \Lambda_{R+2r}} \! \! \P_\ell[  f_r \in \Lambda_{2r} \longleftrightarrow v + \Lambda_{6r} ]  & \le  c  + c r^{d-1}  \sum_{v \in r \Z^d \cap \Lambda_{R+2r} \setminus \{0\} } \! \!   |v|_\infty^{-2\eta^\ast}   \\
&  \le c + c   r^{d-1}  \max\{ r^{-2\eta^\ast}   (R/r)^{d-2 \eta^\ast } (\log (R/r) ) , 1\}    \\
&  \le c R^{\max\{ \alpha(d-1), -\alpha+d-2\eta^\ast \} } (\log R) .
\end{align*}

Next define, for large $R$,

\[ \ell'(R) = \inf\{ \ell > \ell_c :  \P_\ell[A_1(1, R)] = 2 \P_{\ell_c}[A_1(1, R) ] \}  ,\]

which exists by continuity in $\ell$ (see Lemma <ref>), and since $\P_{\ell_c}[A_1(1, R) ] > 0$ and

\[ \P_\ell[A_1(1, R)]  \ge  \P\big[ \sup_{x \in \Lambda_R} f(x)  \le \ell \big] \to 1   \]

as $\ell \to \infty$. By the mean-field lower bound (<ref>), for large $R$,

\begin{align}
\label{e:mfbuse}
\P_{\ell_c}[A_1(1,R)]/2 =  \P_{\ell'}[A_1(1,R)]/4 \ge \theta(\ell')/4 \ge c(\ell'-\ell_c)  ,
\end{align}

where we used that $\ell'(R) \to \ell_c$ as $R \to \infty$, since otherwise

\[ \limsup_{R \to \infty} \P_{\ell_c}[A_1(1,R)]  \ge \limsup_{R \to \infty} \theta(\ell'(R))/2 > 0  \]

which contradicts (<ref>). Similarly to (<ref>) we also have

\begin{align*}
|  \P_{\ell'}[f_r \in A_1(1,R)]   -  \P_{\ell'}[ A_1(1,R)]   | &  \le   c R^{d/2  - \alpha(\beta-d/2)} (\log R) + c e^{ - c (\log R)^2 } \\
&  \le   \P_{\ell_c}[ A_1(1,R)]   =  \P_{\ell'}[ A_1(1,R)]/2   .
\end{align*}

Then applying Proposition <ref> to the field $f_r$, for large $R$,

\begin{align*}
\mathbb{P}_{\ell_c}[ A_1(1,R)] & = \mathbb{P}_{\ell'}[ A_1(1,R)] - \mathbb{P}_{\ell_c}[ A_1(1,R)]    \le 2 ( \mathbb{P}_{\ell'}[ f_r \in A_1(1,R)] - \mathbb{P}_{\ell_c}[  f_r \in A_1(1,R)]   )  \\
&  \le \frac{2 r^{d/2}(\ell'-\ell_c)}{\int q}  \sqrt{  \mathbb{P}_{\ell'}[A_1(1,R)]   \! \! \sum_{v \in r \Z^d \cap \Lambda_{R+2r}} \! \! \P_{\ell_c}[ \Lambda_{2r} \longleftrightarrow v + \Lambda_{6r} ]}   \\
&  \le  \frac{2(\ell'-\ell_c)}{\int q}   R^{\alpha d/2}  \sqrt{ R^{-\eta^\ast}   R^{\max\{ 0, \alpha(d-1), -\alpha+d-2\eta^\ast \} } (\log R) } .
\end{align*}

Comparing with (<ref>) implies that  $\alpha d -\eta^\ast + \max\{ \alpha(d-1), -\alpha+d-2\eta^\ast \} \ge 0$, and so $\eta^\ast \le \max\{ d/3 +  \alpha(d-1)/3, \alpha (2d-1) \}$, and sending $\alpha \to  \frac{3d/2-1}{\beta-d/2}$ from above gives the result.

Finally, consider the third statement. Fix  $1 > \alpha > \frac{5}{3(\beta-1)}$ and $r = R^\alpha$. By the RSW estimates (the second statement of Lemma <ref>) and Lemma <ref>,

\[    \P_{\ell_c}[f_r \in \textrm{Cross}_5(R)]\big(1-\P_{\ell_c}[f_r \in \textrm{Cross}_5(R)] \big) \le c - c  R^{1 -\alpha(\beta-1)} (\log R) < c /2  \]

for large $R$. Then by (<ref>) and Proposition <ref> we have, for large $R$,

\[  c  \mathbb{P}_{\ell_c}[f_r \in A_2(2r,R-2r )]^{-1}   \le  \frac{d}{d \ell} \mathbb{P}_\ell[ f_r \in \textrm{Cross}_5(R)] \Big|_{\ell= \ell_c}    \le   c  R \sqrt{\mathbb{P}_{\ell_c}[f_r \in A_2(2r,R-2r ) ]}  \]

which gives $ \mathbb{P}_{\ell_c}[f_r \in A_2(2r, R-2r )]   \ge  c R^{-2/3}$ for large $R$. Applying the union bound and  Lemma <ref> (valid since $A_2(3 \sqrt{2}r, R)$ is the intersection of an increasing and a decreasing event) yields

\[  \mathbb{P}_{\ell_c}[A_2(1,R-2r )]  \ge c r^{-1} \mathbb{P}_{\ell_c}[A_2(2r,R-2r )] \ge c  R^{-\alpha} \big( R^{-2/3} -  R^{1 - \alpha(\beta-1)} (\log R)  \big) . \]

Sending $\alpha \to \frac{5}{3(\beta-1)}$ from above gives that, for every $\varepsilon > 0$,

\begin{equation}
\label{e:twoarm2}
\mathbb{P}_{\ell_c}[A_2(1,R )] \ge c_2   R^{-2/3 - 5/(3(\beta - 1)) - \varepsilon}   .
\end{equation}

for $c_2 = c_2(\varepsilon) > 0$ and large $R$. Hence by the FKG inequality (see (<ref>))

\begin{equation}
\label{e:limsup4}
\mathbb{P}_{\ell_c}[A_1(1,R )]  \ge ( \mathbb{P}_{\ell_c}[A_2(1,R )] )^{1/2} \ge  c_3 R^{-1/3- 5/(6(\beta-1)) - \varepsilon/2}
\end{equation}

for $c_3 = c_3(\varepsilon) > 0$ and large $R$, which gives the result.

§.§ Randomised algorithms

Recall from Definition <ref> that (randomised) algorithms are adapted procedures that sequentially reveal a subset of random variables $X =  (X_i)$ and return a value. In the Bernoulli case we took $X_e = \id_{e \text{ open}}$ indexed by the edges of $\Z^d$. In the Gaussian setting we will instead decompose the field $f = \sum f_S$ into independent components indexed by a partition of $\R^d$ into disjoint boxes $S$, and take $X_S = f_S$.

Fix a constant $s > 0$ and partition $\mathbb{R}^d$ into boxes $S \in \mathcal{S}_s$ which are translations of $[0, s)^d$ by the lattice $s \mathbb{Z}^d$. Then one can decompose $f = \sum_{S \in \mathcal{S}_s} f_S$ where

\[  f_S(\cdot) =  (q \star W|_S )(\cdot) =  \int_{y \in \mathbb{R}^d} q(\cdot-y) dW|_S(y) =   \int_{y \in S} q(\cdot-y) dW(y)  \]

are independent centred almost surely continuous Gaussian fields,[For fixed $s > 0$ we can suppose they are simultaneously continuous almost surely by countability.] and $W|_S = W \id_S$ is the restriction of the white noise $W$ to $S$.[More precisely $(W|_S)_{S \in \mathcal{S}_s}$ are defined by setting, for $g \in L^2(\mathbb{R}^d)$, $\int_{y \in \mathbb{R}^d} g(y) dW|_S(y)$ to be jointly centred Gaussian random variables with covariance

\[   \mathbb{E} \Big[   \int_{y \in \mathbb{R}^d} g_1(y) dW|_{S_1}(y) \int_{y \in \mathbb{R}^d} g_2(y) dW|_{S_2}(y)  \Big] = \begin{cases} \int_{y \in S_1} g_1(y)g_2(y) dy  & \text{if } S_1 = S_2, \\ 0 & \text{else}. \end{cases} \]
We then introduce the collection $\mathcal{A}_s$ of algorithms that adaptively reveal a subset of $(f_{S})_{S \in \mathcal{S}_s}$. For brevity we say that a box $S \in \mathcal{S}_s$ is revealed if $f_S$ (or equivalently $W|_S$) is revealed. As in Definition <ref>, $\text{Rev}(S)$ is the probability that $S$ is revealed.

In the case that $f$ satisfies (<ref>), we make the important distinction between the set of boxes that are revealed by an algorithm, and the set $V \subset \R^d$ on which the field $f$ is determined by an algorithm.
More precisely, for $V \subset \R^d$ and a set of boxes $\mathcal{P} \subset \mathcal{S}_s$, we say that $f$ is determined on $V$ using $\mathcal{P}$ if $f|_V = (\sum_{S \in \mathcal{P}} f_S)|_V$, or equivalently, if $((\bigcup_{S \in \mathcal{S}_s \setminus \mathcal{P}}\Supp(q\star \one_S))\cap V=\emptyset$.

We now state the analogue of Lemma <ref>. Recall the box $B_k(R) = [-R,R] \times [-kR, kR]^{d-1}$, its right half $B_k^+(R) = [0, R] \times [-kR, kR]^{d-1}$, and in the case $d=2$, its top-right quarter $B_k^\dagger(R) = [0, R] \times [0,kR]$, all considered as subsets of $\R^d$.

Suppose $f = q \star W$ satisfies Assumption <ref> and (<ref>), and let $r > 0$ be such that $q$ is supported on $\Lambda_r$. Then for every $\ell \in \R$ and $R \ge r$ there is an algorithm in $\mathcal{A}_r$ determining $A(1, R)$ such that, under $\P_\ell$,

\[    \sum_{S \in \mathcal{S}_r} \textrm{Rev}(S) \le  \sum_{v \in r \Z^d \cap \Lambda_{R+2r}} \! \! \P_\ell[ \Lambda_1 \longleftrightarrow v + \Lambda_{6r} ] .  \]

Moreover for every $k \ge 1$, $\ell \in \R$, and $ R \ge 4r > 0$, there are algorithms in $\mathcal{A}_r$ determining $\textrm{Cross}_k(R)$ such that, under $\mathbb{P}_\ell$, these algorithms satisfy respectively

\[   \max_{S \in \mathcal{S}_r } \textrm{Rev}(S) \le \frac{4r}{R}\sum\limits_{i=2}^{R/r}\P_\ell[A_1(2r ,ir)]  \ , \quad \max_{S \in \mathcal{S}_r  : d(S, B_k^+(R)) < r }  \! \! \textrm{Rev}(S) \le \P_\ell[A_1(2r, R-2r)]  ,\]

and, if $d=2$,

\[  \max_{S \in \mathcal{S}_r  : d(S,B_k^\dagger(R) ) < r}  \! \! \textrm{Rev}(S) \le  \P_\ell[A_2(2r, R-2r)] . \]

We begin by introducing some notation. Distinct boxes $S, S' \in \mathcal{S}_r$ are adjacent if their closures have non-empty intersection. For a set of boxes $\mathcal{P} \subset \mathcal{S}_r$ define its outer boundary

\[ \partial^+ P :=  \{S \in \mathcal{S}_r \setminus  \mathcal{P} : \text{ $S$ is adjacent to a box $S' \in \mathcal{P}$ } \} , \]

so in particular $\partial^+ \{S\}$ are the boxes adjacent to $S$. Define also the interior $\textrm{int}(\mathcal{P}) := \{ S \in  \mathcal{P} : \partial^+ \{S\} \subseteq \mathcal{P}  \}$. Note that, since $q$ is supported on $\Lambda_r$, $f$ is determined on $\textrm{int}(\mathcal{P})$ using $\mathcal{P}$. A primal (resp. dual) path will designate a path in $\{f \geq 0\}$ (resp. $\{f \leq 0\}$) and a level line will designate a path in $\{f = 0\}$; these paths are contained in a set of boxes $\mathcal{P} \subset \mathcal{S}_r$ if they are contained in $\cup_{S \in \mathcal{P}} S$. The left and right sides of $B_k(R)$ are respectively $\{-R\} \times [-kR, kR]^{d-1}$ and $\{R\} \times [-kR, kR]^{d-1}$, and if $d=2$ the top and bottom sides are defined similarly.

For the first statement consider the following algorithm:

* Reveal every box that intersects $\Lambda_1$ as well as all adjacent boxes.

* Iterate the following steps:

* Let $\Wc \subset \mathcal{S}_r$ be the boxes that have been revealed.

* Identify the set $\Uc \subseteq \partial^+ (\textrm{int}(\Wc))$ such that, for each $S \in \Uc$, there is a primal path contained in $\textrm{int}(\Wc) \cap \Lambda_R$ between $\Lambda_1$ and the boundary of $S$ (measurable since $f$ is determined on $\textrm{int}(\Wc)$). In other words, $\Uc$ contains all boxes on which $f$ is not yet determined but which are connected to $\Lambda_1$ by a primal path in $\Lambda_R$ that has been determined.

* If $\Uc$ is empty end the loop. Otherwise reveal the boxes in $\partial^+ \Uc \setminus \Wc$.

* If $\textrm{int}(\Wc) \cap \Lambda_R$ contains a primal path between $\Lambda_1$ and $\partial \Lambda_R$ output $1$, otherwise output $0$.

This algorithm determines $A(1, R)$ since $\textrm{int}(\Wc)$ eventually contains all the components of $\{f \ge 0\} \cap \Lambda_R$ that intersect $\Lambda_1$. To estimate the sum of revealments $\rev(S)$, a box $S$ is revealed if and only if either (i) it is adjacent to a box that intersects $\Lambda_1$, or (ii) there is a primal path in $\Lambda_R$ between $\Lambda_1$ and a box adjacent to $S$. If $S = v + [0, r)^2$ and $\Lambda_1 \cap (v + \Lambda_{6r}) = \emptyset$ then the latter implies the occurrence of $\Lambda_1 \longleftrightarrow v + \Lambda_{6r}$. Summing over $S$ gives

\[ \sum_{S \in \mathcal{S}_r} \textrm{Rev}(S) \le      \sum_{v \in r \Z^d \cap \Lambda_{R+2r}} \P_p[ \Lambda_1 \longleftrightarrow v + \Lambda_{6r}] .\]

For the second statement, the first algorithm is:

* Draw a random integer $i$ uniformly in $[-R/r, 0]$, define $L=\{i r\}\times[-kR,kR]^{d-1}$, and reveal every box that intersects $L \cap B_k(R)$, as well as all adjacent boxes.

* Iterate the following steps:

* Let $\Wc \subset \mathcal{S}_r$ be the boxes that have been revealed.

* Identify the set $\Uc \subseteq \partial^+ (\textrm{int}(\Wc))$ such that, for each $S \in \Uc$, there is a primal path contained in $\textrm{int}(\Wc) \cap B_k(R)$ between $L \cap B_k(R)$ and the boundary of $S$.

* If $\Uc$ is empty end the loop. Otherwise reveal the boxes in $\partial^+ \Uc \setminus \Wc$.

* If $\textrm{int}(\Wc) \cap B_k(R)$ contains a primal path between the left and right sides of $B_k(R)$ output $1$, otherwise output $0$.

This algorithm determines $\textrm{Cross}_k(R)$ since $\textrm{int}(\Wc)$ eventually contains all the components of $\{f \ge 0\} \cap B_k(R)$ that intersect $L \cap B_k(R)$, and any primal path in $B_k(R)$ between its left and right sides must intersect $L \cap B_k(R)$. To estimate the revealments $\rev(S)$ of this algorithm, a box $S$ is revealed if and only if either (i) it is adjacent to a box that intersects $L \cap B_k(R)$, or (ii) there is a primal path in $B_k(R)$ between $L$ and a box adjacent to $S$. If $d'$ denotes the distance from the centre of $S$ to $L$, this implies the occurrence of (a translation of) the event $A_1(2r, d')$. Averaging over $i \in [-R/r, 0]$ gives

\[ \rev(S) \le  \frac{r}{R}  \Big(  4 + 2 \sum_{i = 3}^{R/r} \P_\ell[A_1(2r,ir)] \Big) \le  \frac{4r}{R}  \sum_{i = 2}^{R/r} P_\ell[A_1(2r,ir)]  . \]

For the second algorithm we modify the above by setting $L$ as $\{-R\}\times[-kR,kR]^{d-1}$, and repeating all other steps. A box $S \in \mathcal{S}_r$ such that $d(S, B_k^+(R)) < r$ is only revealed if there is a primal path in $B_k(R)$ between $L$ and a box adjacent to $S$, which as before implies the occurrence of (a translation of) the event $A_1(2r, d)$, where $d$ is the distance from the centre of $S$ to $L$. Since $d$ is at least $R-2r$, $\rev(S) \le \P_\ell[A_1(2r, R-2r)]$ as required.

The final algorithm (specific to $d=2$) is:

* Define $L_1=[-R,R]\times\{-kR\}$ and $L_2=\{-R\}\times[-kR,kR]$, and reveal every box that intersects $(L_1\cup L_2) \cap B_k(R)$, as well as all adjacent boxes.

* Iterate the following steps:

* Let $\Wc \subset \mathcal{S}_r$ be the boxes that have been revealed.

* Identify the set $\Uc \subseteq \partial^+(\textrm{int}(\Wc))$ such that, for each $S \in \Uc$, there is a level line contained in $\textrm{int}(\Wc) \cap B_k(R)$ between $(L_1\cup L_2) \cap B_k(R)$ and the boundary of $S$.

* If $\Uc$ is empty end the loop. Otherwise reveal the boxes in $\partial^+ \Uc \setminus \Wc$.

* If $\textrm{int}(\Wc) \cap B_k(R)$ contains a primal (resp. dual) path between the left and right (resp. top and bottom) sides of $B_k(R)$ terminate with output $1$ (resp. $0$).

* Since $\textrm{int}(\Wc)$ contains all components of $\{f = 0\} \cap B_k(R)$ that intersect $L_1 \cap L_2$ and the algorithm has not yet terminated, exactly one of $\{f \ge 0\} \cap B_k(R)$ or $\{f \le 0\} \cap B_k(R)$ has a component that intersects all four sides of $B_k(R)$. Partition $B_k(R)$ into regions $(P_i)$ using the components of $\{f = 0\} \cap B_k(R)$ that intersect $L_1\cup L_2$. Let $\mathbb{A}$ to be the region $P_i$ which contains the top-left corner of $B_k(R)$, and set $\mathcal{C}=1$ (resp. $\mathcal{C}=0$) if $f$ is positive (resp. negative) on $P_i$. Then iterate the following:

* If $\mathbb{A}$ contains a path in $B_k(R)$ between its left and right sides  terminate with output $\mathcal{C}$.

* Change the value of $\mathcal{C}$ (from $0$ to $1$ or $1$ to $0$), and add to $\mathbb{A}$ the region $P_i$ that is adjacent to it.

The final loop is illustrated in Figure <ref>; it terminates almost surely since there are a finite number of connected components of $\{f=0\} \cap B_k(R)$ (recall that $f$ is $C^1$-smooth). Note that the algorithm does not necessarily reveal all components of $\{f = 0\}$ inside $B_k(R)$ – any components which are closed loops or only touch the top and right sides of $B_k(R)$ are not revealed – but these do not affect whether $\textrm{Cross}_k(R)$ occurs.

The final loop of the algorithm in the proof of the third statement of Lemma <ref>; this loop occurs when there is no left-right or top-bottom paths in $\{f=0\} \cap B_k(R)$. In this example the loop expands the area $\mathbb{A}$ three times in order to determine the sign $\mathcal{C}$ of the crossing.

To estimate the revealments of this algorithm, a box $S \in \mathcal{S}_r$ such that $d(S, B_k^\dagger(R)) < r$ is only revealed if there is a level line in $B_k(R)$ between $L_1 \cap L_2$ and a box adjacent to $S$, which implies the occurrence of (a translation of) the event $A_2(2r, d')$, where $d'$ is the distance from the centre of $S$ to $L_1 \cap L_2$. Since $d'$ is at least $R-2r$, $\rev(S) \le \P_\ell[A_2(2r, R-2r)]$ as required.

§.§ Proof of Propositions <ref>–<ref>

Before proving Propositions <ref> and <ref> we give the analogue of Proposition <ref>, which applies to continuous stationary Gaussian fields $f = q \star W$ (note that we do not need to assume Assumption <ref>):

Suppose $f = q \star W$ is continuous. Then for every $\ell \in \R$, event $A$, $s > 0$, algorithm $\mathcal{A} \in \mathcal{A}_s$ that determines $A$, set of boxes $\mathcal{S}' \subseteq \mathcal{S}_s$, and $\varepsilon \ge 0$,

\[ \big| \P_\ell \big[f+ \varepsilon \! \sum_{S \in \mathcal{S}'} q \star \id_S \in A \big] - \P_\ell[f\in A]  \big| \le \varepsilon s^{d/2} \! \!  \sqrt{  \max\Big\{ \P_\ell[A], \P_\ell \big[f+ \varepsilon \! \sum_{S \in \mathcal{S}'} q \star \id_S \in A \big] \Big\} \E_\ell  |\Wc_{\mathcal{S}'}| }, \]

where $\Wc_{\mathcal{S}'}$ is the set of boxes in $\mathcal{S}'$ that are revealed by $\mathcal{A}$. In particular, if (<ref>) holds,

\begin{equation}
\label{e:genubgau2}
\big| \P_{\ell + \varepsilon} \big[A \big] - \P_\ell[f\in A]  \big| \le \frac{\varepsilon s^{d/2} }{\int q} \! \!  \sqrt{  \max \{ \P_\ell[A], \P_{\ell + \varepsilon}  [ A  ]  \} \E_\ell  |\Wc| },
\end{equation}

where $\Wc$ is the set of all boxes in $\mathcal{S}_s$ that are revealed by $\mathcal{A}$ .

Consider $S \in \mathcal{S}_s$. We use the decomposition (see Proposition <ref> in the appendix)

\[ f_S(\cdot) \stackrel{d}{=} \frac{Z_S (q \star \id_S)(\cdot)}{s^{d/2}} + g_S(\cdot), \]

where $Z_S$ is a standard normal random variable and $g_S$ is a continuous Gaussian field independent of $Z_S$, which implies also that

\[  f_S(\cdot) + \varepsilon (q \star \id_S)(\cdot) \stackrel{d}{=} \frac{(Z_S +  \varepsilon s^{d/2})(q \star \id_S)(\cdot)}{s^{d/2}} + g_S(\cdot) . \]

The same argument that led to (<ref>) (this time with $W$ equal to $(Z_S)_{S \in  \Wc_{\mathcal{S}' }}$ in the order of revealment, and $W'$ containing $Z_S$ on $S \notin \mathcal{S}'$ as well as $g_S$ for all $S$) yields in this case

\begin{align*}
& \big| \P_\ell \big[f+ \varepsilon \sum_{S \in \mathcal{S}'} q \star \id_S \in A \big] - \P_\ell[f\in A]  \big| \\
& \qquad \le \sqrt{ 2 \max\Big\{ \P_\ell[A], \P_\ell \big[f+ \varepsilon \sum_{S \in \mathcal{S}'} q \star \id_S \in A \big] \Big\} \E_\ell  |\Wc_{\mathcal{S}'}| D_{KL}( Z \| Z +  \varepsilon s^{d/2})   }
\end{align*}

where $Z$ is a standard normal random variable. Since $D_{KL}(Z \| Z +  \varepsilon s^{d/2}) = \varepsilon^2 s^d/ 2$ we have the first statement. For second statement, notice that $\sum_{S \in \mathcal{S}_s} (q \star \id_S) =   (q \star \id)(x)   =  \int q$. Then set $\mathcal{S}' = \mathcal{S}_s$ and replace $\varepsilon \mapsto \varepsilon / \int q$ in the first statement.

This follows directly from (<ref>) by considering the algorithm in Lemma <ref> that determines $A_1(1, R)$ such that

\begin{equation*}  \E_\ell |\mathcal{W}|  =   \sum_{S \in \mathcal{S}_r} \textrm{Rev}(S) \le  \sum_{v \in r \Z^d \cap \Lambda_{R+2r}} \! \! \P_\ell[ \Lambda_1 \longleftrightarrow v + \Lambda_{6r} ] . \qedhere
\end{equation*}

We begin with the general case $d \ge 2$. We first partition the set of boxes $\{ S \in \mathcal{S}_r :  d(S, B_k(R)) < r \}$ that cover $B_k(R)$ into the disjoint sets

\[ \mathcal{S}'_1 = \{ S \in \mathcal{S}_r :  d(S, B_k^+(R)) < r \} \qquad \text{and} \qquad \mathcal{S}'_2= \{ S \in \mathcal{S}_r :  d(S, B_k(R)) < r \} \setminus \mathcal{S}'_1 \]

Note that $\mathcal{S}'_1 $ and $ \mathcal{S}'_2$ correspond roughly to boxes which cover, respectively, the right-half $B_k^+(R)$ and its complement $B_k(R) \setminus B_k^+(R)$, except that we enforce disjointness (see Remark <ref> for an explanation) so we do not have exact reflective symmetry. However the reflection of $\mathcal{S}'_2$ in the hyperplane $\{0\} \times \R^{d-1}$ is contained in $\mathcal{S}'_1$.

By disjointness and since $q$ is supported on $\Lambda_r$, for every $x \in B_k(R)$ we have

\[   \sum_{i = 1,2} \sum_{S \in \mathcal{S}'_i} (q \star \id_S)(x)  =    \sum_{S \in \mathcal{S}'_1 \cup \mathcal{S}'_2 } (q \star \id_S)(x)  =   (q \star \id)(x)   =  \int q .  \]

Then by the multivariate chain rule for Dini derivatives

\begin{align*}
\frac{\partial^+}{\partial \ell} \P_\ell \big[\textrm{Cross}_k(R) \big] = &   \frac{1}{\int q}  \frac{\partial^+}{\partial \varepsilon}  \P_\ell \big[f+   \varepsilon  \sum_{i = 1,2} \sum_{S \in \mathcal{S}'_i}  q \star \id_S   \in \textrm{Cross}_k(R) \big] \Big|_{\varepsilon = 0}  \\
&  \le \frac{1}{\int q} \sum_{i=1,2}   \frac{\partial^+}{\partial \varepsilon}  \P_\ell \big[f+   \varepsilon \sum_{S \in \mathcal{S}'_i  } q \star \id_S   \in \textrm{Cross}_k(R) \big] \Big|_{\varepsilon = 0}   .
\end{align*}

Now consider the algorithm in Lemma <ref> that determines $\textrm{Cross}_k(R)$ such that, under $\P_\ell$,

\[  \max_{S \in \mathcal{S}'_1 }   \textrm{Rev}(S) \le \P_\ell[A_1(2r, R-2r)]  .   \]

By reflective symmetry, there is also an algorithm determining  $\textrm{Cross}_k(R)$  such that, under $\P_\ell$,

\[  \max_{S \in \mathcal{S}_2'}   \textrm{Rev}(S) \le \P_\ell[A_1(2r, R-2r)]  .   \]

Since also $\max_{i=1,2} |\mathcal{S}'_i|  \le c_1 (R/ r)^d$ for some $c_1  > 0$ depending only on $k$ and $d$, applying Proposition <ref> gives

\[ \frac{\partial^+}{\partial \ell} \P_\ell \big[\textrm{Cross}_k(R) \big]   \le  \frac{r^{d/2}}{2 \int q}  \sqrt{c_1 (R/r)^d   \P_\ell[A_1(2r, R-2r)]  }  =   \frac{c_2 R^{d/2} }{\int q}  \sqrt{ \P_\ell[A_1(2r, R-2r)]  }  \]

for some $c_2 = c_2(k,d) > 0$, as required.

For $d=2$ we consider the top-right quadrant $B_k^\dagger(R)$ and the algorithm in Lemma <ref> that determines $\textrm{Cross}_k(R)$ such that

\[  \max_{ \{ S \in \mathcal{S}_r :  d(S, B_k^\dagger(R)) < r \} }   \textrm{Rev}(S) \le \P_\ell[A_2(2r, R-2r)]  .   \]

Then a similar argument to in the previous case (except partitioning $\{ S \in \mathcal{S}_r :  d(S, B_k(R)) < r \}$ into $\cup_{i = 1,\ldots,4} \mathcal{S}'_i$ into four disjoint sets that approximate the four quadrants of $B_k^+(R)$ and using reflective symmetry in both axes) yields the result.

Since we do not assume $q \ge 0$, it is not necessarily true that

\[    \frac{\partial^+}{\partial \varepsilon}  \P_\ell \big[f+   \varepsilon  q \star \id_S   \in \textrm{Cross}_k(R) \big]  \ge 0 \]

for every $S \in \mathcal{S}_r$. Hence in the proof of Proposition <ref> it was crucial that we partitioned $\{ S \in \mathcal{S}_r :  d(S, B_k(R)) < r \}$ disjointly into $\cup_i \mathcal{S}'_i$, since otherwise we could not deduce that

\[ \frac{\partial^+}{\partial \ell} \P_\ell \big[\textrm{Cross}_k(R) \big] \le   \frac{1}{\int q}  \frac{\partial^+}{\partial \varepsilon}  \P_\ell \big[f+   \varepsilon  \sum_{i=1,2} \sum_{S \in \mathcal{S}'_i}  q \star \id_S   \in \textrm{Cross}_k(R) \big] \Big|_{\varepsilon = 0}  . \]

To prove Proposition <ref> we need the analogue of Proposition <ref>. We say that an event $A$ is compactly supported if $A$ is measurable with respect to $f|_D$ for a compact $D \subset \R^d$, and is a continuity event if $\ell \mapsto \mathbb{P}_\ell[ f + g \in A ]$ is continuous for every smooth function $g : \R^d \to \R$; for example, $\textrm{Cross}_k(R)$ and $A_i(r, R)$, $i=1,2$, are compactly supported continuity events by Lemma <ref> below.

Suppose $f = q \star W$ satisfies Assumption <ref> and (<ref>), and let $r  >  0$ be such that $q$ is supported on $\Lambda_r$. Then there exists a $c > 0$ depending only on $d$ such that, for every $\ell \in \R$, increasing compactly supported continuity event $A$, $s > 0$, algorithm $\mathcal{A} \in \mathcal{A}_s$ determining $A$, and set of boxes $\mathcal{S}' \subseteq\mathcal{S}_s$,

\begin{equation}
\label{e:lbderiv}
\frac{d^-}{d \ell} \mathbb{P}_\ell[A]   \ge \frac{c \min\{1,(s/r)^d \}}{\|q\|_2} \frac{\textrm{Var}_\ell [ \mathbb{P}_\ell[A | \mathcal{F}_{\mathcal{S}' } ] ] }{\max_{S \in \mathcal{S}' } \textrm{Rev}(S)} ,
\end{equation}

where $\mathcal{F}_{\mathcal{S}'}$ denotes the $\sigma$-algebra generated by $(f_S)_{S \in \mathcal{S}'}$, and the revealments $\textrm{Rev}(S)$ are under $\P_\ell$.

The proof of (<ref>) shows that it can be strengthened by replacing $\frac{d^-}{d \ell} \mathbb{P}_\ell[A]   =   \frac{d^-}{d \varepsilon} \P_\ell[f   + \varepsilon \in A] $ with $\frac{d^-}{d \varepsilon} \P_\ell[f   + \varepsilon g_{S'} \in A]$ where $g_{\mathcal{S}'}(\cdot) := \id_{d(\cdot, \mathcal{S}' ) \le 2r} $, but we do not need this.

In [38] a similar result (in the case $\mathcal{S}' = \mathcal{S}_s$) was proven for an approximation of the field $f$ in which the white noise is replaced with its discretisation at scale $\varepsilon \ll 1$. However, since one needed to take $\varepsilon \ll 1$ in the approximation  (e.g. in $d=2$ one needs $\varepsilon \ll 1/R$ if the event is supported on $B(R)$), this approach results in a prefactor $\varepsilon^{d/2}$ that decays rapidly in the scale of the event. Although this prefactor is also present in (<ref>) as $s \to 0$, the difference is that one can work with fixed $s$.

We prove Proposition <ref> in Section <ref> below. Let us complete the proof of Proposition <ref>:

For the first statement we apply Proposition <ref> (in the case $s=r$, $\mathcal{S}' = \mathcal{S}_s$, and $A = \textrm{Cross}_k(R)$, which is a continuity event by Lemma <ref>) to the algorithm in Lemma <ref> that determines $\textrm{Cross}_k(R)$ whose revealments are bounded by $\frac{4r}{R}\sum\limits_{i=2}^{R/r}\P_\ell[A_1(2r ,ir)]$.

For the second statement we follow the proof of Proposition <ref> in the Bernoulli case, except using Proposition <ref> (in the case $s=r$, $\mathcal{S}' = \{S \in \mathcal{S}_s  : d(S,B_k^\dagger(R) ) < r \}$, and $A = \textrm{Cross}_k(R)$) and the algorithm in Lemma <ref> that determines $\textrm{Cross}_k(R)$ whose revealments on $\mathcal{S}'$ are bounded by $\P_\ell[A_2(2r, R-2r)]$. To control the conditional variances in (<ref>) we use the same argument as in the proof of Proposition <ref>; in particular the FKG inequality is available and, since $R \ge 8r$, the events $B_1$ and $B_2$ are independent as in the Bernoulli case.

Similarly to in Section <ref>, combining Propositions <ref> and <ref> yields a general lower bound on the revealments of increasing events. We omit the proof, but the result is the following. Suppose $f = q \star W$ satisfies Assumption <ref> and (<ref>)–(<ref>). Let $r$ be such that $q$ is supported on $\Lambda_r$, let $\ell \in \R$, let $R \ge r$, let $A$ be an increasing continuity event supported on $B(R)$, let $s > 0$, and let $\mathcal{A} \in \mathcal{A}_s$ be an algorithm determining $A$. Then there exists a $c > 0$ depending only on $d$ such that

\[   \max_{S \in \mathcal{S}_s} \textrm{Rev}(S) \ge   \frac{ c \big( (\int q) / \|q\|_2 \min\{1, (s/r)^d \}  \Var_\ell[ \id_A ]  \big)^{2/3} }{  \P_\ell[A]^{1/3} R^{d/3}}   \]

where the revealments $\textrm{Rev}(S)$ are under $\P_\ell$.

One can also prove a lower bound on $\max_{S \in \mathcal{S}'} \textrm{Rev}(S)$ for general $\mathcal{S}' \subset \mathcal{S}_s$, analogous to Proposition <ref>, however in that case we would need $q \ge 0$ (for the same reason as explained in Remark <ref> above) and also the refinement to Proposition <ref> mentioned in Remark <ref>.

§.§ Proof of auxiliary results

To finish the section we prove Lemmas <ref> and <ref>:

We first observe that $g := f - f_r = (q-q_r) \star W$ is a $C^1$-smooth stationary Gaussian field satisfying

\[ \E[ g(0)^2 ] = \int_{x \in \R^d} (q-q_r)^2(x) \, dx  =  \int_{|x| > r/2} q(x)^2 (1 - \varphi(|x/r|))^2 \, dx \le  \int_{|x| > r/2} q(x)^2  \le c_1  r^{d-2\beta} ,   \]

for some $c_1 > 0$ and we used that $|q(x)| \le  c |x|^{-\beta}$ by Assumption <ref>. Similarly, for every direction $v \in \mathbb{S}^1$,

\[ \E[ (\partial_v g(0) )^2 ]  =  \int_{ |x| > r/2} (\partial_v (q(x)(1 - \varphi(|x/r|)) )^2 \, dx   \le c_2  r^{d-2\beta} ,   \]

for some $c_2 > 0$ that depends on the (uniformly bounded) derivatives of $\varphi$, and we used that $|\nabla q(x)| \le  c |x|^{-\beta}$ by Assumption <ref>. Then by a Borell-TIS argument (see <cit.> for the case $d=2$, and the proof is identical in all dimensions) there exist $c_3, c_4 > 0$ such that, for all $R, r \ge 2$,

\begin{equation}
\label{e:btis}
\P [  \| f - f_r \|_{\infty, B(R)} >  c_3 (\log R) r^{-(\beta - d/2)} ]   \le c_3 e^{-c_4 (\log R)^2}
\end{equation}

We also note the following consequence of (<ref>) which can be proved with a Cameron-Martin argument (see <cit.> for the case $d=2$, and the proof is identical in all dimensions): there exists a $c_5 > 0$ such that, for $R \ge 1$, increasing event $A'$ measurable with respect to $f|_{B(R)}$, $\ell \in \R$ and $t > 0$,

\begin{equation}
\label{e:cm}
\P_\ell[ \{f  + t \in A' \} \setminus \{ f  \in A' \} ] =  \P_\ell[f  + t  \in A' ]  - \P_\ell[ f  \in A'  ] \le c_5 t R^{d/2} .
\end{equation}

We now complete the proof, for which we may assume that $\ell = 0$. Consider $A = A_1 \cap A_2$ where $A_1$ is increasing, $A_2$ is decreasing, and both $A_1$ and $A_2$ are measurable with respect to $f|_{B(R)}$. Abbreviate $t = c_3 (\log R) r^{-(\beta-d/2)}$ and define $E = \{ \| f - f_r \|_{\infty, B(R)} > t \}$. Then

\begin{align*}
& \P[ f_r \in A_1 \cap A_2 ]  \le \P[ f_r \in A_1 \cap A_2 \cap E^c]  + \P[E]  \\
& \quad \le \P[ \{ f + t \in A_1 \} \cap \{f - t \in A_2 \}   ]  + \P[E]  \\
& \quad \le \P[ f \in A_1 \cap A_2 ] + \P[ \{f + t \in A_1 \} \setminus \{ f   \in A_1 \} ] +  \P[ \{f -t \in A_2 \} \setminus \{ f  \in A_2 \} ]   + \P[E] \\
& \quad \le  \P[ f \in A_1 \cap A_2 ]  +   2 c_5  t R^{d/2}   +  c_3 e^{-c_4 (\log R)^2}
\end{align*}

where in the second inequality we used that $A_1$ (resp. $A_2$) is increasing (resp. decreasing) and measurable with respect to $f|_{B(R)}$, and the final inequality was by (<ref>) and (<ref>). Similarly

\begin{align*}
& \P[ f_r \in A_1 \cap A_2 ]    \ge \P[ \{ f - t \in A_1 \} \cap \{f + t \in A_2 \}  \cap E^c ]  \\
& \quad \ge \P[ f \in A_1 \cap A_2] - \P[ \{f  \in A_1 \} \setminus \{ f -t  \in A_2 \} ] - \P[ \{f  \in A_2 \} \setminus \{ f + t  \in A_2 \} ]  - \P[E] \\
& \quad \ge \P[ f \in A_1 \cap A_2] -  2 c_5  t R^{d/2}   - c_3 e^{-c_4 (\log R)^2}
\end{align*}

which gives the result.

For the first statement, it is enough to prove that

\begin{equation}
\label{e:boot}
\liminf_{R \to \infty}  \mathbb{P}_{\ell_c}[\textrm{Cross}_5(R)] > 0
\end{equation}

since then the result follows by the continuity of $\ell \mapsto \mathbb{P}_\ell[\textrm{Cross}_5(R)]$ (by Lemma <ref> below for instance). By a classical bootstrapping argument <cit.> and Lemma <ref>, there are $c_1, \varepsilon > 0$ such that

\begin{equation}
\label{e:boot2}
\mathbb{P}_\ell[\textrm{Cross}_5(3R)] \le c_1 \big(  \mathbb{P}_\ell[\textrm{Cross}_5(R)]^2 + R^{-\varepsilon} \big)
\end{equation}

for $\ell \in \R$ and $R$ sufficiently large. A consequence of (<ref>) and the continuity of $\ell \mapsto \mathbb{P}_\ell[\textrm{Cross}_5(R)]$ is that

\[ \liminf_{R \to \infty}  \mathbb{P}_\ell[\textrm{Cross}_5(R)]  < 1/c_1   \quad \implies \quad  \liminf_{R \to \infty}  \mathbb{P}_{\ell'}[\textrm{Cross}_5(R)]  = 0 \quad \text{for some } \ell' > \ell .\]

Covering the annulus $\Lambda_{5R} \setminus \Lambda_{3R}$ with $2d$ symmetric copies of $B_5(R)$, one can find a finite collection of copies $A_i$ of $\textrm{Cross}_5(R)$  such that $ \{\Lambda_1 \longleftrightarrow \infty\} \subseteq A_1(3R, 5R)  \subseteq \cup_i A_i $. Hence we also have

\[ \liminf_{R \to \infty}  \mathbb{P}_{\ell'}[\textrm{Cross}_5(R)] = 0 \quad \implies \quad \P_{\ell'}[\Lambda_1 \longleftrightarrow \infty] = 0  \quad \implies \quad \ell' \le \ell_c , \]

and so we deduce (<ref>).

For the second statement we refer to [38] where it is shown that the RSW estimates hold under Assumption <ref> and (<ref>) (indeed the recent work [30] shows that the correlation decay in Assumption <ref> is not even needed).

We also state a continuity result that we used in the section:

Let $f$ be a $C^2$-smooth Gaussian field on $\R^d$ such that $(f(x), \nabla f(x), \nabla^2 f(x))$ is non-degenerate for every $x \in \R^d$. Then for every $k \ge 1$ and $R \ge r > 0$,

\[   \P_\ell[\textrm{Cross}_k(R) ]   \qquad \text{and} \qquad    \P_\ell[A_i(r, R) ] \, , \ i=1,2     \]

are continuous functions of $\ell \in \R$.

Since $f$ is $C^2$-smooth and $(f(x), \nabla f(x), \nabla^2 f(x))$ is non-degenerate, by Bulinskaya's lemma <cit.> the critical points of $f$, as well as its restriction to a smooth hypersurface, are almost surely locally finite and have distinct critical levels. Since the events $\{f + \ell \in \textrm{Cross}_k(R)\}$ and $\{f + \ell \in A_i(r, R)\}$ depend only on the (stratified) diffeomorphism class of the level set $\{f + \ell = 0\}$ restricted to, respectively, $B_k(R)$ and $\Lambda_R \setminus \Lambda_r$, by the (stratified) Morse lemma <cit.> almost surely there is a $\delta > 0$ such that $\id_{\{f + \ell + s \in \textrm{Cross}_k(R) \}}$ and $\id_{\{f + \ell + s \in A_i(r, R) \}}$ are constant on $s \in (-\delta, \delta)$, which is equivalent to the claimed continuity.

§ THE OSSS INEQUALITY FOR SMOOTH GAUSSIAN FIELDS AND APPLICATIONS

In this section we establish a new Russo-type inequality for smooth Gaussian fields which we use to prove Proposition <ref>, with Theorem <ref> following as an application. We consider a field $f = q \star W$ which is $C^2$-smooth and satisfies (<ref>), and let $r > 0$ be such that $q$ is supported on $\Lambda_r$. In particular this implies that $(f(0), \nabla f(0), \nabla^2 f(0))$ is non-degenerate. We emphasise that in this section neither (<ref>) nor (<ref>) play any role.

As in Section <ref>, fix $s > 0$ and consider the orthogonal decomposition $f = \sum_{S \in \mathcal{S}_s} f_S$ where

\[ f_S(\cdot) =  (q \star W|_S )(\cdot) =  \int_{y \in \mathbb{R}^d} q(\cdot-y) dW_S(y) =   \int_{y \in S} q(\cdot-y) dW(y) . \]

The proof of Proposition <ref> is based on an application of the OSSS inequality (Theorem <ref>) to the independent fields $(f_S)_{S \in \mathcal{S}_s}$. In this context the resampling influences (c.f. (<ref>)) are defined, for each $S \in \mathcal{S}_s$, as

\[   \Infl_A(S) :=   \mathbb{P}_\ell \big[ \id_{\{f \in A\}} \neq \id_{\{f^{(S)} \in A\}} \big]  \]

where $f^{(S)}$ denotes the field $f = \sum_{S \in \mathcal{S}_s} f_S$ with $f_S$ resampled. Just as for other recent applications of the OSSS inequality in percolation theory [16, 15, 17], the crucial mechanism is that $\frac{d^-}{d \ell} \P_\ell[A]$ is bounded below by the sum of the resampling influences. Recall the definition of compactly supported continuity events from the statement of Proposition <ref>.

There exists a constant $c > 0$ depending only on $d$ such that, for every $\ell \in \R$, $s > 0$, and increasing compactly supported continuity event $A$,

\[ \frac{d^-}{d \ell} \mathbb{P}_\ell[A]  \ge \frac{c \min\{1, (s/r)^d\}}{\|q\|_2} \sum_{S \in \mathcal{S}_s}  \Infl_A(S)  \]

where the resampling influences $\Infl_A(S)$ are under $\P_\ell$.

Before proving Proposition <ref>, let us complete the proof of Proposition <ref>.

The OSSS inequality (Theorem <ref>), combined with the reasoning leading to (<ref>), gives

\[  \textrm{Var}_\ell [ \mathbb{P}_\ell[A | \mathcal{F}_{\mathcal{S}' } ] ] \le  \frac{1}{2} \sum_{S \in \mathcal{S}'} \textrm{Rev}(S) \Infl_A(S)    \]

and hence (true for arbitrary event $A$)

\[   \sum_{S \in \mathcal{S}_s}   \Infl_A(S)  \ge \sum_{S \in \mathcal{S}'}   \Infl_A(S)  \ge \frac{2 \textrm{Var}_\ell[ \mathbb{P}_\ell[A | \mathcal{F}_{\mathcal{S}' } ] ] }{  \max_{S \in \mathcal{S}'} \textrm{Rev}(S) }  .   \]

Combining with Proposition <ref> yields the result.

The main idea in the proof of Proposition <ref>, which distinguishes it from the discretisation approach in [38], is to use an orthonormal decomposition of each $f_S$ to interpret $\frac{d^-}{d \ell} \mathbb{P}_\ell[A]$ and the resampling influences $\Infl_A(S)$ as measuring, respectively, the `boundary' and `volume' of certain sets in Gaussian space. Then we can apply Gaussian isoperimetry to deduce the result. For a set $E \subset\mathbb{R}^n$ we denote

\[ E^{+\varepsilon} := \{ x \in \mathbb{R}^n : \text{ there exists } y \in E \text{ s.t. } |x-y|_2 \le \varepsilon \} \]

to be the $\varepsilon$-thickening of $E$.

There exists a constant $c > 0$ such that, for every measurable $E \subset\mathbb{R}^n$ and $\varepsilon \ge 0$,

\[ \mathbb{P}[X \in E^{+\varepsilon} \setminus E] \ge   \sqrt{\frac{2}{\pi}}    \mathbb{P}[X \in E] (1 - \mathbb{P}[X \in E]) \varepsilon    -  c \varepsilon^2  \]

where $X$ is an $n$-dimensional standard Gaussian vector.

Let $\varphi(x)$ and $\Phi(x)$ denote the standard normal pdf and cdf respectively. The classical Gaussian isoperimetric inequality states that

\[  \liminf_{\varepsilon \downarrow 0} \varepsilon^{-1}  \mathbb{P}[X \in E^{+\varepsilon} \setminus E]     \ge \varphi( \Phi^{-1}( \mathbb{P}[X \in E] )   ) .  \]

A simple consequence (see, e.g., <cit.>) is that, for any $\varepsilon \ge 0$,

\begin{equation}
\label{e:iso1}
\mathbb{P}[X \in E^{+\varepsilon}] \ge   \Phi(\Phi^{-1}(\mathbb{P}[X \in E]) + \varepsilon  ).
\end{equation}

By Taylor expanding $\Phi$ on the right-hand side of (<ref>) we have

\[ \mathbb{P}[X \in E^{+\varepsilon} \setminus E] \ge   \varepsilon \varphi(\Phi^{-1}(\mathbb{P}[X \in E]) ) - \frac{1}{2} \sup_{x \in \mathbb{R}} |\varphi'(x)| \varepsilon^2    , \]

and the result follows since, for all $x \in \mathbb{R}$, $\varphi(x) \ge \sqrt{\frac{2}{\pi}} \, \Phi(x) (1-\Phi(x))$(as can be seen from the fact that the Mill's ratio $(1-\Phi(x))/\varphi(x)$ is decreasing on $x \ge 0$), and since $|\varphi'(x)|$ is uniformly bounded on $x \in \mathbb{R}$.

We use the following orthogonal decomposition of $f_S$ (see Proposition <ref> in the appendix). Let $Z = (Z_i)_{i \ge 1}$ be a sequence of i.i.d. standard normal random variables and let $(\varphi_i)_{i \ge 1}$ be an orthonormal basis of $L^2(S)$. Then

\begin{equation}
\label{e:odecom}
f^n_S := \sum_{i \ge 1}^n Z_i (q \star \varphi_i) \Rightarrow f_S ,
\end{equation}

in law with respect to the $C^0$-topology.

By linear rescaling, we may suppose without loss of generality that $\ell = 0$, $\|q\|_2 = 1$, and that $q$ is supported on $\Lambda_1$ (i.e. $r=1$). For each $S \in \mathcal{S}_s$, let $g_S : \R^d \to [0,1]$ be a smooth function such that $g_S(x) = 1$ on $\{x : d(x, S) \le 1\}$ and $g_S(x) = 0$ on $\{x : d(x, S) \ge 2\}$. Then $\sum_{S \in \mathcal{S}_s}g_S(x) \le c_1 \max\{1, s^{-d}\}$ for some constant $c_1 > 0$ depending only on $d$. Therefore, since $A$ is increasing, and by the multivariate chain rule for Dini derivatives,

\begin{equation}
\label{e:rusfin0}
\frac{d^-}{d \varepsilon} \mathbb{P}[f + \varepsilon \in A]  \Big|_{\varepsilon = 0} \ge \frac{1}{c_1 \max\{1, s^{-d}\}}  \sum_{S \in \mathcal{S}_s} \frac{d^-}{d \varepsilon} \mathbb{P}[f + \varepsilon g_S \in A]  \Big|_{\varepsilon = 0} .
\end{equation}

For each $S \in \mathcal{S}_s$, let $f'_S$ denote an independent copy of $f_S$, define $h_S = f - f_S$, and let $\mathcal{F}_{h_S}$ be the $\sigma$-algebra generated by $h_S$. We next claim that, almost surely over $\mathcal{F}_{h_S}$,

\begin{equation}
\label{e:rusfin}
\frac{d^-}{d \varepsilon} \mathbb{P}[f_S + h_S +  \varepsilon g_S \in A | \mathcal{F}_{h_S} ] \Big|_{\varepsilon = 0}   \ge     c_2   \mathbb{P}[ \id_{\{f_S + h_S  \in A\}} \neq \id_{\{f'_S + h_S \in A \}} | \mathcal{F}_{h_S} ]
\end{equation}

for some universal $c_2 > 0$. Together with (<ref>), this will complete the proof of Proposition <ref> since

\begin{align*}
\frac{d^-}{d \varepsilon} \mathbb{P}[f_S + \varepsilon g_S \in A]  \Big|_{\varepsilon = 0} & \ge  \E \Big[ \frac{d^-}{d \varepsilon} \mathbb{P}[f_S + h_S +  \varepsilon g_S \in A | \mathcal{F}_{h_S} ] \Big|_{\varepsilon = 0}  \Big]  \\
& \ge c_2 \E \big[      \mathbb{P}[ \id_{\{f_S + h_S  \in A\}} \neq \id_{\{f'_S + h_S \in A \}} | \mathcal{F}_{h_S}  ]  \big] \\
& =:  c_2 \Infl_A(S) .
\end{align*}

where the first inequality is Fatou's lemma, and the second inequality is by (<ref>).

It remains to prove (<ref>). Henceforth we fix $S \in \mathcal{S}_s$, condition on $h_S$, and drop $\mathcal{F}_{h_S}$ from the notation. Let $(\varphi_i)_{i \ge 1}$ be an orthonormal basis of $L^2(S)$ and recall the decomposition (<ref>). Fixing $n \in \mathbb{N}$ and viewing $\{f_S^n + h_S \in A\}$ as a Borel set $E$ in the $n$-dimensional Gaussian space generated by the standard Gaussian vector $Z^n = (Z_i)_{1 \le i \le n}$, by Proposition <ref>

\begin{equation}
\label{e:rus2}
\mathbb{P}[Z^n \in E^{+\varepsilon} \setminus E]   \ge   c_3  \varepsilon   \mathbb{P}[Z^n \in E] (1 - \mathbb{P}[Z^n \in E])  -  c_4 \varepsilon^2
\end{equation}

for some $c_3, c_4 > 0$ and every $\varepsilon \ge 0$. Consider $y  = (y_i) \in \mathbb{R}^n$ such that $\| y \|_2 = \varepsilon$. By Young's convolution inequality, and since $\varphi_i$ are an orthonormal basis,

\[  \Big\|   \sum_{i \le n} y_i  (q \star   \varphi_i)   \Big\|_\infty \le \|q \|_2 \Big\| \sum_{i \le n} y_i \varphi_i \Big\|_2  =    \|y\|_2 = \varepsilon .  \]

Since $ q \star \varphi_i$ is supported on  $\{x : d(x, S) \le 1 \}$, and recalling that $g_S(\cdot) := \id_{d(\cdot, S) \le 1}$, this gives

\[   \sup_{y : |y|_2 \le \varepsilon}  \, \sum_{i \le n} (Z_i +y_i )( q \star \varphi_i ) - f^n_S  =   \sup_{y : |y|_2 \le \varepsilon}  \,   \sum_{i \le n} y_i  (q \star   \varphi_i)   \le  \varepsilon  g_S . \]

Therefore, since $A$ is increasing,

\begin{align*}
\mathbb{P}[f^n_S +  h_S + \varepsilon  g_S \in A]  - \mathbb{P}[ f^n_S + h_S \in A ]   &\ge    \mathbb{P}[\cup_{y : |y| \le \varepsilon}  \{ Z^n + y \in E \} ] - \mathbb{P}[Z^n \in E]  \\
&  =      \mathbb{P}[Z^n \in E^{+\varepsilon} \setminus E ]  .
\end{align*}

Combining with (<ref>),

\begin{equation}
\label{e:rusfin2}
\mathbb{P}[f^n_S +  h_S + \varepsilon g_S \in A]  - \mathbb{P}[ f^n_S + h_S \in A ]  \ge   c_3   \varepsilon   \mathbb{P}[f^n_S + h_S \in A] (1 - \mathbb{P}[f^n_S + h_S \in A])  - c_4 \varepsilon^2   .
\end{equation}

It remains to prove that almost surely (with respect to $h_S$), as $n \to \infty$,

\begin{equation}
\label{e:cont1}   \mathbb{P}[f^n_S + h_S \in A] \to   \mathbb{P}[f_S + h_S \in A]  \quad \text{and} \quad  \mathbb{P}[f^n_S +  h_S + \varepsilon g_S \in A]  \to  \mathbb{P}[f_S +  h_S + \varepsilon g_S \in A]  ,
\end{equation}

since then sending $n \to \infty$ in (<ref>) yields

\[     \mathbb{P}[f_S +  h_S + \varepsilon g_S \in A]  - \mathbb{P}[ f_S + h_S \in A ]   \ge c_3 \varepsilon  \mathbb{P}[f_S + h_S \in A] (1 - \mathbb{P}[f_S + h_S \in A])  - c_4 \varepsilon^2, \]

which gives (<ref>) after sending $\varepsilon \to 0$.

So let us justify (<ref>). Recall that $A$ is an increasing continuity event; this means that for almost every $f = f_S + h_S$ there exists $\delta > 0$ such that

\[   \id_{\{f_S + h_S  + s \in A\}}  \qquad \text{and} \qquad   \id_{\{ f_S + h_S + \varepsilon g_S + s \in A \}}  \]

are constant for $s \in (-\delta,\delta)$. Then since $f^n_S \to f_S$ in law with respect to the $C^0$-topology, we have (<ref>) (by the Portmanteau lemma for instance).

Note that in the proof of Proposition <ref> we did not require that the Borel set $E$ in the $n$-dimensional Gaussian space generated by $Z^n$ be increasing, since Gaussian isoperimetry is valid for arbitrary sets. This allows us to avoid any requirement that $q \star \varphi_i$ be a positive function, in contrast to the discretisation approach in [38].

§.§ Application to the sharpness of the phase transition for finite-range Gaussian fields

We conclude the section by proving Theorem <ref>, following the approach in [16]. For this we only need the special case $s=r$ and $\mathcal{S}' = \mathcal{S}_s$ of Proposition <ref>.

By linear rescaling and adjusting constants, we may assume without loss of generality that $q$ is supported on $\Lambda_1$, and prove the theorem for $\Lambda_2$ replacing $\Lambda_1$.

For $R \ge 0$ define $g_R(\ell):= \mathbb{P}_\ell[A_1(2, R)]$ (recall that this means $g_R(\ell) := 1$ if $R \in [0, 2]$), and its limit $g_R :=\lim_{R \to \infty} g_R(\ell) = \P_\ell[ \Lambda_2 \longleftrightarrow \infty]$. We will first establish the differential inequality

\begin{equation}
\label{e:dcrt}
\frac{d^-}{d \ell} g_R(\ell)  \ge   \frac{c_1 g_R(\ell)(1-g_R(\ell)}{ \frac{1}{R} \sum_{i = 0}^{R-1}  g_i(\ell) }
\end{equation}

for some $c_1 > 0$, every $R$ sufficiently large, and every $\ell \in \R$. Recall the notation from the beginning of the proof of Lemma <ref> and for $R \ge 2$ consider the following algorithm in $\mathcal{A}_1$ (essentially taken from [16]):

* Draw a random integer $i$ uniformly in $[2, R]$, and reveal every box that intersects $\partial \Lambda_i$, as well as all adjacent boxes.

* Iterate the following steps:

* Let $\Wc \subset \mathcal{S}_1$ be the boxes that have been revealed.

* Identify the set $\Uc \subseteq \partial^+ (\textrm{int}(\Wc))$ such that, for each $S \in \Uc$, there is a primal path contained in $\textrm{int}(\Wc) \cap \Lambda_R$ between $\partial \Lambda_i$ and the boundary of $S$.

* If $\Uc$ is empty end the loop. Otherwise reveal the boxes in $\partial^+ \Uc \setminus \Wc$.

* If $\textrm{int}(\Wc)$ contains a primal path between $\Lambda_2$ and $\Lambda_R$ output $1$, otherwise output $0$.

This algorithm determines $A_1(2, R)$ since $\textrm{int}(\Wc)$ eventually contains all the components of $\{f \ge 0\} \cap \Lambda_R$ that intersect $\partial \Lambda_i$, and any primal path between $\Lambda_2$ and $\Lambda_R$ must intersect $\partial \Lambda_i$. To estimate the revealments $\rev(S)$ under $\P_\ell$, note that a box $S$ is revealed if and only if either (i) it intersects, or is adjacent to a box that intersects, $\partial \Lambda_i$, or (ii) there is a primal path in $\Lambda_R$ between $\partial \Lambda_i$ and a box adjacent to $S$. If $d'$ denotes the distance from the centre of $S$ to $\Lambda_i$, this implies the occurrence of (a translation of) the event $A_1(2, d')$. Averaging on $i \in [2,R]$, we have

\[ \rev(S) \le  \frac{1}{R-1}  \Big(  4 + 2 \sum_{i = 3}^{R-1} \P_\ell[A_1(2,i)] \Big) \le  \frac{4}{R-1}  \sum_{i = 0}^{R-1} g_i(\ell)    \le  \frac{5}{R}  \sum_{i = 0}^{R-1} g_i(\ell)  \]

for sufficiently large $R$.  Applying Proposition <ref> (with $s=1$ and $\mathcal{S}' = \mathcal{S}_1$, recalling that $A_1(2, R)$ is a continuity event by Lemma <ref>) gives that

\[ \frac{d^-}{d \ell} g_R(\ell)  \ge \frac{ c_2 g_R(\ell) (1-g_R(\ell))}{\max_{S \in \mathcal{S}_1} \textrm{Rev}(S) }   \ge \frac{ c_2 g_R(\ell)(1-g_R(\ell)}{ \frac{5}{R} \sum_{i = 0}^{R-1} g_i(\ell)}  \]

for some $c_2 > 0$ and sufficiently large $R$, which gives (<ref>).

We now argue that (<ref>) implies the result. First assume that there exists a $\ell_0 > \ell_c$ such that $g(\ell_0) < 1$ (this is clear if $f$ satisfies (<ref>), since then $\P [ \inf_{x \in \Lambda_{3}} f(x) \ge \ell ]    >  0$ for every $\ell \in \R$, but not in general). Then by monotonicity $1 - g_\ell(R) >   (1 - g(\ell_0)/2$ for all $\ell < \ell_0$ and large $R$. Hence setting $c_3 = c_1 (1-g(\ell_0))/2> 0$ and defining $f_R(\ell) = g_R(\ell)/c_3$ we have

\[   \frac{d^-}{d \ell} f_R(\ell)  \ge   \frac{f_R(\ell)}{ \frac{1}{R} \sum_{i = 0}^{R-1}  f_i(\ell) } . \]

for all $\ell < \ell_0$ and large $R$, and applying <cit.>[Although this lemma is stated for differentiable functions, it is easy to check that the proof goes through without differentiability since it only uses $f(b) - f(a) \ge \int_a^b   \frac{d^-}{d x} f(x) dx$.] yields the result. On the other hand, if $g(\ell_0) = 1$ for every $\ell_0 > \ell_c$ then the second statement of the theorem is immediate. To prove the first statement, instead choose a $\ell_0 < \ell_c$ and repeat the above argument. This implies the statement for $\ell < \ell_0$, and taking $\ell_0 \uparrow \ell_c$ gives the claim.

§ ORTHOGONAL DECOMPOSITION OF $F_S$

For completeness we present a classical orthogonal decomposition of the Gaussian field

\[ f_S(\cdot)  = (q \star W|_S)(\cdot) = \int_{y \in S} q(\cdot-y) dW(y) \]

where $S \subset \mathbb{R}^d$ is a compact domain, $q \in L^2(\mathbb{R}^d)$, and $W$ is the white noise on $\mathbb{R}^d$. In this section we shall assume only that $f_S$ is continuous, all other conditions on $q$ being irrelevant.

Let $(Z_i)_{i \ge 1}$ be a sequence of i.i.d. standard normal random variables and let $(\varphi_i)_{i \ge 1}$ be an orthonormal basis of $L^2(S)$. Then, as $n \to \infty$,

\[ f^n_S := \sum_{i \ge 1}^n Z_i (q \star \varphi_i) \Rightarrow f_S \]

in law with respect to the $C^0$-topology on compact sets. In particular,

\[ f_S(\cdot) \stackrel{d}{=} \frac{Z_1 (q \star \id_S)(\cdot)}{\sqrt{\text{Vol}(S)}} + g(\cdot) \]

where $g$ is an continuous Gaussian field independent of $Z_1$.

Remark that, for each $x \in \mathbb{R}^d$, $f^n_S(x) \Rightarrow f_S(x)$ in law since they are centred Gaussian random variables and

\[  \mathbb{E} \Big[ \Big(\sum_{i \ge 1}^n Z_i (q \star \varphi_i)(x)  \Big)^2 \Big] = \sum^n_{i \ge 1} \Big(\int_S q(x-s) \varphi_i(s) \, dx \Big)^2  \to   \int_S q(x-s)^2  \, dx    = \mathbb{E}[f_S(x)^2]  \]

by Parseval's identity. Note also that the functions $q \star \varphi_i$ are continuous (as a convolution of $L^2$ functions), and so each $f^n_S$ is continuous. Hence the first statement of the proposition follows by an application of Lemma <ref> below. For the second statement, set $\varphi_1$ to be constant on $S$.

Let $(f_i)_{i \ge 1}$ be a sequence of independent continuous centred Gaussian fields on $\mathbb{R}^d$ and define $g_n :=\sum^n_{i \ge 1} f_i$. Suppose there exists a continuous Gaussian field $g$ on $\R^d$ such that, for each $x \in \mathbb{R}^d$, $g_n(x) \Rightarrow g(x)$ in law. Then $g_n \Rightarrow g$ in law with respect to the $C^0$-topology on compact sets.

We follow the proof of <cit.>. Since $g_n(x)$ is a sum of independent random variables converging in law, by Levy's equivalence theorem we may define $g(x)$ as the almost sure limit of $g_n(x)$. Fix a compact set $\Omega \subset \mathbb{R}^d$, and consider $(g_n)_{n \ge 1}$ as elements of the Banach space $C(\Omega)$ of continuous functions on $\Omega$ equipped with the $C_0$-topology. By the Itô-Nisio theorem <cit.>, it suffices to show that

\[  \int_\Omega  g_n \, d \mu \to \int_\Omega g \, d \mu \]

in mean (and so in probability) for every finite signed Borel measure $\mu$ on $\Omega$. Define the continuous functions $u_n(x) := \mathbb{E}[g_n(x)^2]$ and $u(x) := \mathbb{E}[g(x)^2]$. Then