# Kinetically constrained models out of equilibrium

Ivailo Hartarsky  Technische Universität Wien, Institut für Stochastik und
Wirtschaftsmathematik, Wiedner Hauptstraße 8-10, A-1040, Vienna, Austria
<EMAIL_ADDRESS>Fabio Lucio Toninelli
Technische Universität Wien, Institut für Stochastik und
Wirtschaftsmathematik, Wiedner Hauptstraße 8-10, A-1040, Vienna, Austria
<EMAIL_ADDRESS>
###### Abstract

We study the full class of kinetically constrained models in arbitrary
dimension and out of equilibrium, in the regime where the density $q$ of
facilitating sites in the equilibrium measure (but not necessarily in the
initial measure) is close to $1$. For these models, we establish exponential
convergence to equilibrium in infinite volume and linear time precutoff in
finite volume with appropriate boundary condition. Our results are the first
out-of-equilibrium results for any model in the so-called critical class,
which is covered in its entirety by our treatment, including e.g. the
Fredrickson–Andersen 2-spin facilitated model. In addition, they generalise,
unify and sometimes simplify several previous works in the field. As
byproduct, we recover and generalise exponential tails for the connected
component of the origin in the upper invariant trajectory of perturbed
cellular automata and in the set of eventually infected sites in subcritical
bootstrap percolation models. Our approach goes through the study of
cooperative contact processes, last passage percolation, Toom contours, as
well as a very convenient coupling between contact processes and kinetically
constrained models.

MSC2020: 60K35; 82C22
Keywords: kinetically constrained models, contact processes, perturbed
cellular automata, bootstrap percolation, convergence to equilibrium,
precutoff

##  1 Introduction

Kinetically constrained models (KCM) were introduced in order to study the
liquid-glass transition [Fredrickson84] (see [Ritort03, Garrahan11,
Cancrini09] for reviews). They are Markov processes featuring a parameter
$q\in[0,1]$ tuning the density of facilitating sites. Purposefully, KCM are
reversible w.r.t. the product Bernoulli measure with parameter $q$. Indeed, it
has been proposed that the real-world liquid-glass transition has a purely
dynamical origin, that is not reflected in the equilibrium measure. KCM were
introduced precisely with the purpose of testing whether glassy behaviour
could be explained purely in dynamical terms. Despite having a trivial
stationary measure, the degenerate rates of KCM make them very hard to tackle
mathematically, by making their dynamics non-attractive, cooperative,
heterogeneous, admitting multiple invariant measures, not satisfying coercive
inequalities and sometimes featuring ergodicity breaking phase transitions.

In recent years a detailed understanding of KCM at equilibrium has been
achieved, especially in two dimensions (see [Hartarsky22phd]*Chapter 1 for an
overview). However, from the physical perspective it is essential to
understand their behaviour out of equilibrium, typically after a quench from
one temperature to a different one. Rigorous results in this direction are
rather limited and will be the subject of a detailed account in Section 4.
Suffice it to say that with the exception of [Chleboun13], all out-of-
equilibrium results pertain to the class of so-called supercritical modes, for
which a finite patch of facilitating sites can trigger relaxation. On the
other hand, [Chleboun13] treats subcritical models with an orientation. The
main goal of the present work is to deal with critical models. However, our
methods work in the greatest possible generality, so we will also cover the
other universality classes. Our main results are: the proof that the mixing
time of the process in a box of side $n$ and boundary condition entirely
composed of facilitating sites is of order $n$ (see Theorem 3.1) and the proof
of exponential convergence to equilibrium for the infinite-volume dynamics
started from a Bernoulli initial condition in the ergodic regime (see Theorem
3.3). A comparison with earlier results is given in Section 4.

The main novelties of the present work are as follows. Firstly, we set up a
general scheme for proving exponential decay for the size of connected
clusters of objects in dependent settings (see Section 9) and showcase two
applications of independent interest going far beyond the needs of our main
results. We further devise a simple and very robust technique for coupling
interacting particle systems, even in the absence of attractiveness (see
Section 7). Moreover, as opposed to previous studies, we develop tools to
tackle cooperative models (such that no finite set of facilitating sites is
able to propagate), including several useful renormalisation techniques (see
Sections 6, 8 and 11). In particular, we provide the first out-of-equilibrium
results for any kinetically constrained model in the _critical universality
class_.

A major limitation for the study of KCM out of equilibrium is that, like ours,
most results work in the perturbative regime of high density of facilitating
sites for the equilibrium measure and not necessarily the initial one.
Exceptions to this are [Chleboun13], heavily relying on orientation, and
results on the East model [Blondel13b, Chleboun14, Chleboun14, Chleboun16,
Couzinie22, Faggionato12, Faggionato13, Ganguly15, Mareche19a], where a model-
specific miracle greatly simplifies the problem. Our study will also be
restricted to the perturbative regime for the equilibrium measure, but not the
initial one. Nevertheless it is our hope that, once a robust renormalisation
scheme is found for controlling KCM in the non-perturbative regime in terms of
the perturbative one, our tools will enable the treatment of the full class of
KCM out-of-equilibrium.

##  2 Models

In this section we define our models of interest, KCM, along with several
other models, which will play an auxiliary role in the proofs. The reader
eager to see the statements of the results in Section 3 will only need
Sections 2.1 and 2.2.

###  2.1 Update families

Let $\|\cdot\|$, $\langle\cdot,\cdot\rangle$ and $d(\cdot,\cdot)$ denote the
Euclidean norm, scalar product and distance respectively. An _update family_
$\mathcal{U}$ is a finite non-empty family of finite non-empty subsets of
${\mathbb{Z}}^{d}\setminus\\{0\\}$ called _update rules_. We refer to unit
vectors

$u\in S^{d-1}=\left\\{v\in{\mathbb{R}}^{d}:\|v\|=1\right\\}$

as _directions_. We denote by
${\mathbb{H}}_{u}=\\{x\in{\mathbb{Z}}^{d}:\langle x,u\rangle<0\\}$. A
direction $u$ is _unstable_ for an update family $\mathcal{U}$, if there
exists $U\in\mathcal{U}$ such that $U\subset{\mathbb{H}}_{u}$. An update
family is _not trivial subcritical_ if it has an unstable direction and
_trivial subcritical otherwise_.

While we will not need to distinguish between the other universality classes,
it is useful to introduce them for the sake of discussing previous less
general results. We say that an update family is _supercritical_ , if there is
an open hemisphere consisting only of unstable directions. We say that it is
_subcritical_ (trivial or non trivial), if every hemisphere contains an open
set of stable directions. Finally, the update family is _critical_ if it is
neither supercritical nor subcritical. We will call _oriented_ the update
families such that there exists $u\in S^{d-1}$ such that
$U\subset{\mathbb{H}}_{u}$ for all $U\in\mathcal{U}$.

Let us introduce an illustrative example corresponding to the classical
_Fredrickson-Andersen $j$-spin facilitated model_ (FA-$j$f). Its update family
$\mathcal{U}=\\{X\subset\\{e_{1},\dots,e_{d},-e_{1},\dots,-e_{d}\\},|X|=j\\}$
is given by all $j$-element subsets of the $2d$ nearest neighbours of the
origin. One can check that for $j=1$ this family is supercritical, for
$j\in\\{2,\dots,d\\}$ it is critical, while for $j>d$ it is trivial
subcritical. The reader may keep in mind the case $j=d$, which is also the
most interesting one, throughout the paper. Indeed, all difficulties we face
are present for this model.

In the rest of the work, adopting the language of bootstrap percolation and of
the contact process, we will refer to “facilitating sites” as to “infected”
and they will coincide with the vertices $x$ of ${\mathbb{Z}}^{d}$ where the
configuration $\eta$ equals $\eta_{x}=1$.

###  2.2 Kinetically constrained models

The $\mathcal{U}$-KCM is a continuous time Markov process with state space
$\Omega=\\{0,1\\}^{{\mathbb{Z}}^{d}}$ defined by the following graphical
construction. To each $x\in{\mathbb{Z}}^{d}$ we attach an independent Poisson
point process $P_{x}$ on $[0,\infty)$ of intensity 1 and uniform random
variables $(U_{x}(t))_{t{\in P_{x}}}$ on $[0,1]$, which are independent and
independent of those for other sites. The model has a further parameter
$q\in[0,1]$, which we call the _equilibrium density_. We denote by
$\eta_{x}(t)$ the state of site $x\in{\mathbb{Z}}^{d}$ in the configuration at
time $t\in[0,\infty)$. Define the _constraint_ at $x\in{\mathbb{Z}}^{d}$ for a
configuration $\eta\in\Omega$ by

$c_{x}(\eta)=\mathbbm{1}_{\exists U\in\mathcal{U},\forall u\in
U,\eta_{x+u}=1}.$ (2.1)

We have

$\eta_{x}(t)=\begin{cases}\mathbbm{1}_{U_{x}(t)\leq q}&t\in P_{x}\text{ and
}c_{x}(\eta(t-))=1,\\\ \eta_{x}(t-)&\text{otherwise.}\end{cases}$ (2.2)

We remark immediately, that $c_{x}(\eta)$ does not depend on $\eta_{x}$, so
$c_{x}(\eta(t-))=c_{x}(\eta(t))$ for all $t\in P_{x}$ and
$x\in{\mathbb{Z}}^{d}$. It is easy to see that this entails that the
$\mathcal{U}$-KCM is reversible w.r.t. the product Bernoulli measure
$\mu_{q}=\mathrm{Ber}(q)^{\otimes{\mathbb{Z}}^{d}}$. We emphasise that
$\mathcal{U}$-KCM are not attractive, i.e. the natural stochastic order is not
preserved by the dynamics. We refer to sites in state $1$ as _infected_ and
sites in state $0$ as _healthy_. Hence, the constraint asks for the presence
of suitably arranged infections around the site we are trying to update.

One defines ${q_{\rm c}^{\mathrm{\scriptstyle{KCM}}}}$ as the infimum of all
$q\in[0,1]$ such that 0 is a simple eigenvalue of the generator of the
$\mathcal{U}$-KCM with parameter $q$. That is, ${q_{\rm
c}^{\mathrm{\scriptstyle{KCM}}}}$ is the critical parameter for ergodicity. We
will also need the critical parameter of the spectral gap of the generator of
the $\mathcal{U}$-KCM:

${\tilde{q}_{\rm
c}^{\mathrm{\scriptstyle{KCM}}}}=\inf\left\\{q>0:\mathrm{gap}>0\right\\},$

which is believed to be always equal to ${q_{\rm
c}^{\mathrm{\scriptstyle{KCM}}}}$; this has been shown in several cases (see
Remark 3.4).

Fix $\Lambda\subset{\mathbb{Z}}^{d}$. For any $\omega\in\Omega$ we denote by
$\omega_{\Lambda}\in\Omega_{\Lambda}=\\{0,1\\}^{\Lambda}$ the restriction of
$\omega$ to $\Lambda$. We define the $\mathcal{U}$-KCM $\eta$ on $\Lambda$
with boundary condition $\tau\in\Omega_{{\mathbb{Z}}^{d}\setminus\Lambda}$ by
setting the configuration equal to $\tau$ outside $\Lambda$ at all times. We
denote the fully infected (resp. healthy) configuration by ${\mathbf{1}}$
(resp. ${\mathbf{0}}$).

We next introduce the _mixing time_ of the $\mathcal{U}$-KCM on a finite set
$\Lambda$ with some boundary condition
$\tau\in\Omega_{{\mathbb{Z}}^{d}\setminus\Lambda}$. Given $\delta\in(0,1)$, we
define

${t_{\rm mix}}(\delta)=\inf\left\\{t\geq
0:{\max_{\xi\in\Omega_{\Lambda}}}d_{\mathrm{TV}}\left({\mathbb{P}}\left(\eta^{{\xi}}(t)\in\cdot\right),\mu_{q}\right)\leq\delta\right\\}\in(0,\infty],$

where $d_{\mathrm{TV}}(\mu,\nu)=\sup_{A}(\mu(A)-\nu(A))$ with the supremum
running over all events $A$ for the arbitrary probability measures $\mu$ and
$\nu$ and $\eta^{\xi}$ is the $\mathcal{U}$-KCM with initial condition $\xi$.

###  2.3 Contact processes

The $\mathcal{U}$-contact process (CP) is defined by the same graphical
construction as the $\mathcal{U}$-KCM and the same constraint as in Eq. 2.1.
However, we set

$\zeta_{x}(t)=\begin{cases}1&t\in P_{x},c_{x}(\zeta(t-))=1,U_{x}(t)\leq q,\\\
0&t\in P_{x},U_{x}(t)>q,\\\ \zeta_{x}(t-)&\text{otherwise},\end{cases}$ (2.3)

instead of Eq. 2.2. That is, the constraint $c_{x}(\zeta(t-))=1$ is no longer
required to be satisfied in order to update the configuration at site $x$ to
the value $0$. We define the $\mathcal{U}$-CP in finite volume with a boundary
condition analogously to what was done for KCM in Section 2.2.

Contrary to KCM, CP are attractive (see [Liggett05] for background), we may
therefore define its upper invariant measure $\bar{\nu}$ as the $t\to\infty$
limit in law of $\zeta^{\mathbf{1}}(t)$, the $\mathcal{U}$-CP with initial
condition ${\mathbf{1}}$, and define the critical point

${q_{\rm
c}^{\mathrm{\scriptstyle{CP}}}}=\inf\left\\{q>0:\bar{\nu}\neq\delta_{{\mathbf{0}}}\right\\}.$

It is known that ${q_{\rm c}^{\mathrm{\scriptstyle{CP}}}}<1$ if and only if
$\mathcal{U}$ is not trivial subcritical [Gray99]*Corollary 18.3.2. On the
other hand, a classical comparison with a branching process shows that
${q_{\rm c}^{\mathrm{\scriptstyle{CP}}}}>0$ for any $\mathcal{U}$ (see e.g.
[Liggett99]*Section I.1).

###  2.4 Last passage percolation

Given an update rule $U\subset{\mathbb{H}}_{u}$ for some $u\in S^{d-1}$, we
define the $U$-last passage percolation (LPP) on $\Lambda=\\{1,\dots,n\\}^{d}$
as follows. Endow each $x\in\Lambda$ with an i.i.d. exponentially distributed
random variable $T(x)$ with mean $1$. For each $x\not\in\Lambda$ set
$s_{x}=0$. For every $x\in\Lambda$ inductively define the _LPP time of $x$_ by
$s_{x}=T(x)+\max_{y\in U}s_{x+y}$. Indeed, this is possible, because $U$ is
contained in an open half-plane. Note that the set of vertices $x$ where
$s_{x}\leq t$ for the $U$-LPP coincides with the set of infected vertices at
time $t$ in the configuration of the $\\{U\\}$-KCM in the box $\Lambda$, with
entirely infected boundary condition and parameter $q=1$. Note also that if
$U={\\{0,-1\\}^{d}\setminus\\{0\\}}$, the $U$-LPP coincides with the standard
$\\{-e_{1},\dots,-e_{d}\\}$-LPP.

###  2.5 Cellular automata with death

A _cellular automaton_ (CA or $\phi$-CA when we want to emphasise the
dependence on the map $\phi$) is specified by a map $\phi:\Omega\to\\{0,1\\}$
depending only on finitely many sites. Given an initial condition
$\omega(0)\in\Omega$, we inductively define for all $t\geq
1,x\in\mathbb{Z}^{d}$

$\omega_{x}(t)=\phi\left(\omega_{\cdot-x}(t-1)\right).$

The CA is said to be an _eroder_ , if for all finite
$A\subset{\mathbb{Z}}^{d}$ there exists $T(A)<\infty$ such that
$\omega(0)=\mathbbm{1}_{{\mathbb{Z}}^{d}\setminus A}$ implies
$\omega(T(A))={\mathbf{1}}$, that is, finite sets of 0s become extinct after a
finite time. The CA is _attractive_ , if $\phi$ is non-decreasing for the
pointwise partial order on $\Omega$.

Given a cellular automaton $\phi$, we further consider its version with
_death_ as follows. Let $\xi_{x,t}$ be i.i.d. Bernoulli variables with
parameter $\delta\in[0,1]$. Then the automaton with map $\phi$ and $\delta$
death is defined by

$\omega_{x}(t)=\begin{cases}\phi(\omega_{\cdot-x}(t-1))&\xi_{x,t}=0,\\\
0&\xi_{x,t}=1,\end{cases}$ (2.4)

for all $t\geq 1$ starting from a given initial condition
$\omega(0)\in\Omega$. We further denote by $\bar{\nu}$ the _upper invariant
measure_ —the limit of the law of the cellular automaton with $\delta$ death
and initial condition ${\mathbf{1}}$, $\omega^{\mathbf{1}}(t)$, as
$t\to\infty$. One then defines its stability threshold

$\delta_{\mathrm{c}}=\sup\left\\{\delta\in[0,1]:{\bar{\nu}\neq\delta_{{\mathbf{0}}}}\right\\},$

where $\delta_{\mathbf{0}}$ is the Dirac measure on ${\mathbf{0}}$. It is a
classical result of Toom [Toom80] that $\delta_{\mathrm{c}}>0$ if and only if
the CA defined by $\phi$ is an eroder.

###  2.6 Bootstrap percolation

The $\mathcal{U}$-bootstrap percolation (BP) is the particular CA whose map
$\phi$ is defined via

$\omega_{x}(t)=\omega_{x}(t-1)\vee c_{x}(\omega(t-1))$ (2.5)

for all $t\geq 1,x\in\mathbb{Z}^{d}$, with $c_{x}$ defined as in Eq. 2.1. One
commonly considers

${q_{\rm
c}^{\mathrm{\scriptstyle{BP}}}}=\inf\left\\{q\in[0,1]:\lim_{t\to\infty}{\mathbb{P}}\left(\omega^{\mu_{q}}_{0}(t)=0\right)=0\right\\},$

where $\omega^{\mu_{q}}$ is the $\mathcal{U}$-BP with initial condition
distributed according to $\mu_{q}$ (there is no other randomness involved). It
is known [Cancrini08] that in fact for the same update family $\mathcal{U}$ we
have ${q_{\rm c}^{\mathrm{\scriptstyle{KCM}}}}={q_{\rm
c}^{\mathrm{\scriptstyle{BP}}}}$.

##  3 Results

We are now ready to state our main results. The first one concerns the mixing
time of KCM or CP in finite volume with infected boundary.

######  Theorem 3.1 (Linear mixing).

Let $\mathcal{U}$ be an update family, which is not trivial subcritical. There
exists $\varepsilon=\varepsilon(\mathcal{U})>0$ such that for all
$q\in[1-\varepsilon,1]$ the $\mathcal{U}$-KCM on $[1,n]^{d}$ with infected
boundary condition exhibits precutoff in linear time: there exists
$C=C(\mathcal{U})>0$ such that for all $\delta\in(0,1)$ and $n$ large enough
depending on $\delta$,

$n/C\leq{t_{\rm mix}}(\delta)\leq Cn.$ (3.1)

The same holds for the $\mathcal{U}$-CP.

######  Remark 3.2.

Let us note that all the conditions above are essential. Indeed, trivial
subcritical models are simply not ergodic, as they admit finite healthy
regions which cannot change [Balister22]*Lemma 7.3. Moreover, there exist non-
trivial subcritical models with ${q_{\rm c}^{\mathrm{\scriptstyle{KCM}}}}$
arbitrarily close to 1 [Hartarsky21]*Proposition 7.1, so one cannot hope
$\varepsilon$ to be independent of $\mathcal{U}$. Finally, one can not change
the boundary condition to healthy or periodic (restricting to the ergodic
component), since it is known that even 2-neighbour bootstrap percolation with
these boundary conditions may have quadratic infection time [Benevides15].
Indeed, the $\mathcal{U}$-BP infection time is a lower bound on the
$\mathcal{U}$-KCM one (see [Martinelli19]*Lemma 4.3).

Our second main result establishes that, in infinite volume, $\mathcal{U}$-KCM
converge exponentially fast to their equilibrium measure.

######  Theorem 3.3 (Exponential convergence).

Let $\mathcal{U}$ be any update family and $\alpha>0$. Then, there exist
$\varepsilon\in(0,1)$ and $c>0$, such that for any $p\in[{\tilde{q}_{\rm
c}^{\mathrm{\scriptstyle{KCM}}}}{+\alpha},1]$ and $q\in[1-{\varepsilon},1]$
the following holds. Let $(\eta^{\mu_{p}}(t))_{t\geq 0}$ be the infinite
volume $\mathcal{U}$-KCM with initial distribution111The initial condition is
assumed to be product mostly for simplicity. It will be clear from the proof
that e.g. any initial condition stochastically dominating $\mu_{p}$ would do.
$\mu_{p}$ and parameter $q$. Then for all local functions
$f:\Omega\to{\mathbb{R}}$ and $t\geq 0$

$\left|{\mathbb{E}}\left[f(\eta^{\mu_{p}}(t))\right]-\mu_{q}(f)\right|\leq
e^{-ct}\|f\|_{\infty}\cdot|\operatorname{supp}f|/c,$

where $\operatorname{supp}f$ is the set of sites on whose state the value of
$f$ depends.

As in Remark 3.2, one cannot hope for $\varepsilon$ independent of
$\mathcal{U}$. However, one should expect both Theorems 3.1 and 3.3 to hold
for any $q>{q_{\rm c}^{\mathrm{\scriptstyle{KCM}}}}+\alpha$.

######  Remark 3.4.

Since ${\tilde{q}_{\rm c}^{\mathrm{\scriptstyle{KCM}}}}$ appears directly in
Theorem 3.3, let us mention that for supercritical and critical models it is
known that ${\tilde{q}_{\rm c}^{\mathrm{\scriptstyle{KCM}}}}={q_{\rm
c}^{\mathrm{\scriptstyle{KCM}}}}=0$ [Hartarsky21, Balister22b].222While
[Hartarsky21] is formulated in two dimensions, the parts we will use do
generalise rather straightforwardly to higher dimensions. Let us mention
specifically, that for supercritical and critical models [Balister22b] gives a
stretched exponential decay of the tail of the infection time of the origin,
but this can be improved to exponential via a standard renormalisation
argument (see [Schonmann92]). For trivial subcritical update families we have
${\tilde{q}_{\rm c}^{\mathrm{\scriptstyle{KCM}}}}={q_{\rm
c}^{\mathrm{\scriptstyle{KCM}}}}=1$ [Cancrini08, Balister22], so that Theorem
3.3 is empty, as it should. For subcritical non-trivial families it is known
that $0<{q_{\rm c}^{\mathrm{\scriptstyle{KCM}}}}\leq{\tilde{q}_{\rm
c}^{\mathrm{\scriptstyle{KCM}}}}<1$ [Cancrini08, Balister22, Hartarsky21] and
the second inequality is believed to be an equality, but this is an important
open problem. Nevertheless, equality has been shown for oriented update
families [Hartarsky22sharpness] and the general case was reduced to a related
question involving only $\mathcal{U}$-BP in [Hartarsky21]. Furthermore,
Theorem 3.3 cannot hold for $p<{q_{\rm
c}^{\mathrm{\scriptstyle{KCM}}}}={q_{\rm c}^{\mathrm{\scriptstyle{BP}}}}$,
since then a.s. there are sites whose state remains 0 forever. Hence, if the
conjecture ${q_{\rm c}^{\mathrm{\scriptstyle{KCM}}}}={\tilde{q}_{\rm
c}^{\mathrm{\scriptstyle{KCM}}}}$ holds, the range of values for $p$ in the
theorem is the best possible.

Finally, let us mention that in the course of the proof of our main results we
will derive consequences on exponential decay in space-time for eroder
attractive cellular automata with death and on space exponential decay for the
set of sites eventually reaching state 1 in $\mathcal{U}$-BP for subcritical
$\mathcal{U}$ with initial condition $\mu_{q}$. The reader interested in these
developments (Corollaries 9.7 and 9.5) can directly refer to Section 9, which
can be read independently of the remainder of the paper.

##  4 Background

Before turning to the proof of Theorems 3.3 and 3.1, let us discuss previous
work on KCM out of equilibrium. We start by mentioning that results of a
different kind, concerning graphs whose size diverges jointly with the
parameter $q$ tending to $0$, can be found in [Chleboun14, Pillai17, Pillai19,
Hartarsky22CBSEP], while large deviations in trajectory space have been
studied in [Bodineau12].

Along the lines of our work, much more has been done, mostly for supercritical
models, especially the $\\{\\{-e_{1}\\},\dots,\\{-e_{d}\\}\\}$-KCM called the
East model and FA-1f, that is, the
$\\{\\{-e_{1}\\},\dots,\\{-e_{d}\\},\\{e_{1}\\},\dots,\\{e_{d}\\}\\}$-KCM. In
all cases roughly the same route has been followed, to the extent possible,
along the following steps in that order, each one relying on the previous one.

  1. Step 1.

Theorem 3.3, possibly with a weaker stretched exponential decay.

  2. Step 2.

Positive speed of the infection front and the corresponding precutoff, that
is, Theorem 3.1.

  3. Step 3.

Ergodicity of the process seen from the front and law of large numbers for the
front position.

  4. Step 4.

CLT for the front position and cutoff.

Step 1 was performed first for the East model in $d=1$ in [Cancrini10]. Like
all results on this model, that relies on orientation and further favourable
properties, allowing the results to hold for all $q>0$. For FA-1f Step 1 was
done with stretched exponential decay for FA-1f for $q$ large enough in
[Blondel13] (pure exponential in $d=1$). For the East model in $d>1$ stretched
exponential decay was proved in [Chleboun15]. Convergence for FA-1f was
improved to pure exponential in [Mountford19] for $q$ large enough. For the
East model in $d>1$ the same was done in [Mareche19a]. The exponential decay
was then generalised to all supercritical models in any dimension for $q$
large enough in [Mareche20], thus including the ones of [Mountford19,
Blondel13], as well as [Cancrini10, Chleboun15, Mareche19a] up to the
restriction on $q$. The most general of the above results, [Mareche20], is
contained in Theorem 3.3. In summary, before the present work, Theorem 3.3 was
known only for supercritical KCM.

Turning to Step 2, Theorem 3.1 was proved for the East model for any $q>0$ in
[Chleboun15]. We believe that even for FA-1f in dimension $d>1$ Theorem 3.1 is
new. However, there is another important work in the direction of Theorem 3.1.
Namely, in [Chleboun13] this result was proved with a weaker upper bound of
order $n\log n$, assuming that the update family is oriented. It should be
noted that orientation rules out the possibility for the model to be critical
and is a very convenient feature for the analysis, as we will see. On the
other hand, the approach of [Chleboun13] has the major advantage of working
for any $q>{q_{\rm c}^{\mathrm{\scriptstyle{KCM}}}}$ owing to
[Hartarsky22sharpness]*Theorem 1.6 and [Hartarsky21]*Theorem 3.7.

Moving on to Step 3, in $d=1$ it has been established that the front has a
well-defined speed and that the law of the configuration behind the front
converges to a limit for large times. This is done for the East model in
[Blondel13b] for any $q>0$ and in [Blondel19] for FA-1f for $q$ large enough.
In [Chleboun16, Couzinie22] the East model was studied in $d>1$ with the aim
to examine the limit shape of the set of updated sites starting from a single
infection. Results are still far from establishing that such a limit shape
actually exists, but some control on the speed of the front in different
directions is obtained.

Finally, Step 4 was achieved in $d=1$ for the East model in [Ganguly15] (see
[Faggionato12, Faggionato13] for further results about the $d=1$ East process
out of equilibrium) and for FA-1f at $q$ close to 1 in [Ertul22]. We should
also mention that in [Lacoin14]*Theorem 2.4 Step 4 was performed for FA-2f in
$d=2$ in the somewhat degenerate case $q=1$, which also coincides with the
zero-temperature Ising model with appropriate external field. This can also be
viewed as a continuous time version of 2-neighbour BP or a non-oriented LPP.

While it would be extremely interesting to see Step 3 and Step 4 established
for general update families, this seems rather remote, given that even the
$d$-dimensional East model for $d>1$ has not been handled at that level yet.
As it is the case for the 1-dimensional East model and FA-1f, we expect that
our Theorems 3.3 and 3.1 and the tools developed to prove them will play an
important role in attacking these questions.

##  5 Outline of the proof

Let us start by sketching the proof of Theorem 3.3, which is slightly simpler.
The proof is composed of several steps corresponding to Sections 6, 7, 8 and
9, which are put together in Section 10.

The first step (see Section 6) is to improve our initial condition $\mu_{p}$
with $p>{\tilde{q}_{\rm c}^{\mathrm{\scriptstyle{KCM}}}}$ to one with high
density of infections. This is achieved via a renormalisation drawing on
[Hartarsky21]. It roughly says that, since $p>{\tilde{q}_{\rm
c}^{\mathrm{\scriptstyle{KCM}}}}$, the probability that a site does not become
infected within time $t$ in the $\mathcal{U}$-BP dynamics with the same
initial condition decays exponentially with $t$. Since the parameter $q$ of
our $\mathcal{U}$-KCM is close to 1, the same holds for it up to a large
enough time, since the $\mathcal{U}$-KCM essentially reduces to the
$\mathcal{U}$-BP in the absence of recovery events. Hence, looking at a
renormalised lattice, we may assume that the initial condition of our dynamics
is product with high density of infections.

The second step (see Section 7) is to reduce the study of the
$\mathcal{U}$-KCM to the CP with update family consisting of a single rule
$U_{0}$ that is oriented. While there is a standard monotone comparison (see
Claim 7.2) that guarantees that all infections of the $\\{U_{0}\\}$-CP are
infections in the $\mathcal{U}$-KCM, we need to go further. Namely, we
establish that studying a certain set that depends not only on the
configuration, but also on the history of the CP, we are able to deduce that
the $\mathcal{U}$-KCM not only has lots of infections, but has actually
coupled for all initial conditions larger than the one of the CP.

Hence, we have reduced our problem to one about the $\\{U_{0}\\}$-CP with
parameter $q_{0}$ close to 1 and initial condition close to ${\mathbf{1}}$. In
doing so, we have lost the reversibility and the product invariant measure of
the KCM, but we have gained attractiveness and orientation for the CP.
Nevertheless, we are not done yet, because the $\\{U_{0}\\}$-CP is by far not
as simple as the classical CP, as its dynamics is still cooperative, because
$U_{0}$ may contain more than one vertex.

The third step (see Section 8) is a further renormalisation generalising and
somewhat simplifying the one of [Mareche20], itself stemming from
[Mountford19]. It transforms the $\\{U_{0}\\}$-CP into a $\mathcal{U}_{0}$-BP
with (little) death, where
$\mathcal{U}_{0}=\\{\\{0,-1\\}^{d}\setminus\\{0\\}\\}$. To achieve this, we
tessellate space-time into large boxes of carefully chosen geometry. Roughly
speaking, we ensure that if all neighbours of a box in the directions given by
$\mathcal{U}_{0}$ are fully infected, then infection propagates with high
probability to the box of interest. Moreover, an infected box remains such at
the next time step with high probability. If either of these high probability
events fails, we view that as a death in the renormalised BP process. We have
thus made our process even simpler, as it now evolves in discrete time and no
longer depends on the original update family $\mathcal{U}$, while remaining
cooperative.

The fourth step (see Section 9) is to show that the $\mathcal{U}_{0}$-BP is
exponentially unlikely to have large space-time clusters of healthy sites.
This can be traced back through the previous steps to the CP and then the KCM
to yield Theorem 3.3 (see Section 10). In fact, we prove this in general for
any CA with death which is an eroder (recall Section 2.5), by developing a
novel and very general scheme for leveraging exponential bounds on the
probability of occurrence of objects rooted at a given point to exponential
bounds on clusters of such objects and applying this to Toom contours
[Toom80], as recently revisited in [Swart22]. Alternatively, one could employ
a multi-scale renormalisation argument, as in [Balister22] transported to the
setting of CA with death via [Hartarsky22sharpness], but this would degrade
Theorem 3.3 to stretched exponential convergence at best.

Finally, we turn to the proof of Theorem 3.1, which still relies on all of the
above, but requires a substitute for the first step above, concerning the
initial condition, since we need to deal even with the ${\mathbf{0}}$ one.
This alternative first step (see Section 11) consists in yet another
renormalisation, this time from the $\\{U_{0}\\}$-CP to the standard LPP. We
show that after the LPP time at a renormalised site, the corresponding box is
coupled for the CP. To do this, somewhat surprisingly, we look at times when
sites become healthy in the CP. Using the orientation of the $\\{U_{0}\\}$-CP,
we have that, once all sites on whose state the constraint at a given site $v$
depends on are coupled, it remains to wait for a single update at $v$ to the
state 0, in order to couple the state at $v$, too. Although these updates are
rare ($q_{0}$ is close to 1), it still takes a time of order 1 to couple the
entire box corresponding to a renormalised site, given that the ones it
depends on (in the LPP sense) are already coupled. Thus, to ensure the CP is
coupled on a box $\Lambda$ of size $n$, it suffices to wait until the LPP on a
(renormalised) box of size of order $n$ reaches all sites. The latter is known
to be linear from [Greenberg09].

Hence, after a linear time the CP has reached its equilibrium distribution in
the box with ${\mathbf{1}}$ boundary condition. By attractiveness of CP, this
distribution stochastically dominates the restriction to the box $\Lambda$ of
the infinite volume upper stationary measure. Moreover, the CP lower bounds
the KCM with any initial condition, so, after this burn-in time, we may
perform the same procedure as for the proof of Theorem 3.3. Namely, we exploit
the relation between $\\{U_{0}\\}$-CP and $\mathcal{U}$-KCM, renormalise the
former to $\mathcal{U}_{0}$-BP with death and, finally, use that the latter
has exponentially small probability to have large healthy space-time clusters.
Using this exponential bound, we get that it suffices to wait for a time of
order $\log n$ to ensure that the $\mathcal{U}$-KCM has coupled with high
probability, once we have waited for the initial linear burn-in time needed
for the LPP to reach all sites in the renormalised version of $\Lambda$.

##  6 Warming up the initial condition

In this section we start by showing that if the initial condition is
$\mu_{p}$, with $1-p<1-{\tilde{q}_{\rm c}^{\mathrm{\scriptstyle{KCM}}}}$
possibly much larger than the equilibrium density $1-q$ of healthy sites,
after a sufficiently large but finite time the law of the process dominates a
renormalised Bernoulli measure with _large_ infection density, but still not
the equilibrium one.

Let us note that the vectors $v^{\prime}_{i}$ in the next lemma are arbitrary
at this point. The reader is encouraged to think of them as the canonical
basis of ${\mathbb{R}}^{d}$, while a more convenient choice will appear in
Section 8.

######  Lemma 6.1.

Let $\mathcal{U}$ be an update family, $\alpha>0$, $\varepsilon_{3}>0$ and let
$v_{1}^{\prime},\dots,v_{d}^{\prime}\in{\mathbb{Z}}^{d}$ be linearly
independent. There exists $R_{0}\in\\{1,2\dots\\}$ such that for any $R\geq
R_{0}$ there exists $T_{0}$ such that for any $T\geq T_{0}$ there exists
$\varepsilon_{1}>0$ such that for any $p\in[{\tilde{q}_{\rm
c}^{\mathrm{\scriptstyle{KCM}}}}+\alpha,1]$ and $q\in[1-\varepsilon_{1},1]$
the following holds. Set
$\hat{B}=\sum_{i=1}^{d}(v^{\prime}_{i}[0,R))\subset{\mathbb{R}}^{d}$ and
$\hat{B}_{x}=\hat{B}+\sum_{i=1}^{d}x_{i}v^{\prime}_{i}$ for every
$x\in{\mathbb{Z}}^{d}$. We can couple all $\mathcal{U}$-KCM
$\eta^{\mu_{p^{\prime}}}$ with parameter $q$ and initial conditions
$\mu_{p^{\prime}}$ for $p^{\prime}\geq p$ together with
$\xi\sim\mu_{1-\varepsilon_{3}}$ so that for every $x\in{\mathbb{Z}}^{d}$,

$\xi_{x}=1\Rightarrow\;\forall p^{\prime}\geq
p,\eta^{\mu_{p^{\prime}}}_{\hat{B}_{x}}(T)={\mathbf{1}}_{\hat{B}_{x}}.$

###### Proof.

Fix $\alpha>0$. From [Hartarsky21]*Theorems 3.5 and 3.7${}^{\ref{foot:qctBP}}$
we have that there exists $c=c(\alpha)\in(0,\infty)$ such that the
$\mathcal{U}$-BP (without death) $\omega$ satisfies
${\mathbb{P}}(\omega_{0}^{\mu_{p}}(t)=0)\leq e^{-ct}$ for every
$p\in[{\tilde{q}_{\rm c}^{\mathrm{\scriptstyle{KCM}}}}+\alpha,1]$ and integer
$t\geq 0$. Choose $R>0$ large enough depending on $c$ and some fixed
$\varepsilon_{2}>0$. For convenience, we require $\sqrt{R}\in{\mathbb{N}}$.
Then

${\mathbb{P}}\left(\omega_{\hat{B}}^{\mu_{p}}\left(\sqrt{R}\right)={\mathbf{1}}_{\hat{B}}\right)\geq
1-\varepsilon_{2}.$

Since $R$ is large enough, the above event only depends on
$\omega^{\mu_{p}}(0)$ restricted to
$\bigcup_{z\in\\{-1,0,1\\}^{d}}\hat{B}_{z}$.

Let us now choose $T>0$ large enough depending on $R$ in such a way that with
probability at least $1-\varepsilon_{2}$ for each
$i\in\\{0,\dots,\sqrt{R}-1\\}$ and
$x\in\bigcup_{z\in\\{-1,0,1\\}^{d}}\hat{B}_{z}$ we have
$P_{x}\cap(iT/\sqrt{R},(i+1)T/\sqrt{R})\neq\varnothing$, where we recall that
$P_{x}$ is the Poisson process associated to $x$ from Section 2.2. Finally, if
$q$ is close enough to 1 depending also on $T$, we get that with probability
at least $1-\varepsilon_{2}$, we have $U_{x}(t)\leq q$ for all $t\in
P_{x}\cap[0,T)$ and $x\in\bigcup_{z\in\\{-1,0,1\\}^{d}}\hat{B}_{z}$.

We claim that if all three events above occur for some $x\in{\mathbb{Z}}^{d}$,
that is,
$\omega^{\mu_{p}}_{\hat{B}_{x}}(\sqrt{R})={\mathbf{1}}_{\hat{B}_{x}}$,
$P_{y}\cap(iT/\sqrt{R},(i+1)T/\sqrt{R})\neq\varnothing$ and $U_{y}(t)\leq q$,
for all $y\in{\bigcup_{z\in x+\\{-1,0,1\\}^{d}}\hat{B}_{z}}$,
$i\in\\{0,\dots,\sqrt{R}-1\\}$ and $t\in P_{y}\cap[0,T)$, then

$\eta_{\hat{B}_{x}}^{\mu_{p^{\prime}}}(T)={\mathbf{1}}_{\hat{B}_{x}}\text{ for
any }p^{\prime}\geq p.$ (6.1)

Since $\omega^{\mu_{p}}_{\hat{B}_{x}}(\sqrt{R})={\mathbf{1}}_{\hat{B}_{x}}$
and $R$ is large (hence much larger than $\sqrt{R}$), there exists $X$ with
$\hat{B}_{x}\subset X\subset\bigcup_{z\in\\{-1,0,1\\}^{d}}\hat{B}_{x+z}$ such
that the $\mathcal{U}$-BP process $\omega^{\mu_{p},X}$ on $X$ with boundary
condition ${\mathbf{0}}_{{\mathbb{Z}}^{d}\setminus X}$ and initial state
$\omega_{X}^{\mu_{p}}(0)$ satisfies
$\omega^{\mu_{p},X}(\sqrt{R})={\mathbf{1}}_{X}$. 333To see this, one may
remove the infections at distance more than $C\sqrt{R}$ from $\hat{B}_{x}$ for
some large constant $C>0$, since they do not reach $X$ by time $\sqrt{R}$, and
take $X$ to be the set of all sites infected by the remaining ones up to time
$\sqrt{R}$. Then we can prove by induction on $i\in\\{0,\dots,\sqrt{R}\\}$
that for all $y\in{X}$ we have
$\eta_{y}^{\mu_{p^{\prime}}}(iT/\sqrt{R})\geq\omega_{y}^{\mu_{p},X}(i)$.

The base is the monotone coupling of the initial conditions. For the induction
step, observe that by assumption, for the KCM, no attempt is made to change
any state to 0, but at least one attempt is made to change each site to 1.
Since the constraint $c_{y}$ is non-decreasing in the configuration and the
$\eta_{X}^{\mu_{p^{\prime}}}$ process is non-decreasing in time, if for some
$y\in X$ and $i\in\\{0,\dots,\sqrt{R}-1\\}$ we have $c_{y}(\omega^{X}(i))=1$,
then for any $t\in(iT/\sqrt{R},(i+1)T/\sqrt{R})$ we have
$c_{y}(\eta^{\mu_{p^{\prime}}}(t))=1$. Applying this to some $t\in
P_{y}\cap(iT/\sqrt{R},(i+1)T/\sqrt{R})\neq\varnothing$, we obtain the
induction step:

$\displaystyle\eta^{\mu_{p^{\prime}}}_{y}\left((i+1)T/\sqrt{R}\right)$
$\displaystyle{}\geq\eta^{\mu_{p^{\prime}}}_{y}(t)=c_{y}\left(\eta^{\mu_{p^{\prime}}}(t)\right)\vee\eta^{\mu_{p^{\prime}}}_{y}(t-)$
$\displaystyle{}\geq
c_{y}\left(\omega^{\mu_{p},X}(i)\right)\vee\eta^{\mu_{p^{\prime}}}_{y}\left(iT/\sqrt{R}\right)$
$\displaystyle{}\geq
c_{y}\left(\omega^{\mu_{p},X}(i)\right)\vee\omega^{\mu_{p},X}_{y}(i)=\omega^{\mu_{p},X}(i+1).$

Hence, the claimed Eq. 6.1 follows by taking $i=\sqrt{R}$.

Thus, for every $x\in{\mathbb{Z}}^{d}$, on an event $E_{x}$ of probability at
least $1-3\varepsilon_{2}$, the $\mathcal{U}$-KCM with initial condition
$\mu_{p^{\prime}}$ coupled in a monotone way satisfy Eq. 6.1. Moreover, by
construction the events $E_{x}$ are 1-dependent in terms of $x$, so by the
Liggett–Schonmann–Stacey theorem [Liggett97], the set of $x$ such that $E_{x}$
is realised stochastically dominates an i.i.d. configuration with parameter at
least $1-\varepsilon_{3}$ such that $\varepsilon_{3}\to 0$ if
$\varepsilon_{2}\to 0$. ∎

##  7 Coupling KCM and CP

In this section we examine the coupling between KCM and CP. Let $\mathcal{U}$
be an update family which is not trivial subcritical and let
$\|\mathcal{U}\|=\max_{U\in\mathcal{U},x\in U}\|x\|$. Fix
$U_{0}\in\mathcal{U}$ such that $U_{0}\subset{\mathbb{H}}_{u}$ for some $u\in
S^{d-1}$ (this is possible since the update family $\mathcal{U}$ is assumed
not to be a trivial subcritical one). Let us fix a domain
$\Lambda\subset{\mathbb{Z}}^{d}$ and boundary condition
$\tau\in\Omega_{{\mathbb{Z}}^{d}\setminus\Lambda}$. Fix two parameters $0\leq
q_{0}\leq q\leq 1$. Fix an initial condition $\xi\in\Omega_{\Lambda}$ and
denote by $\zeta$ the $\\{U_{0}\\}$-CP on $\Lambda$ with boundary condition
$\tau$, initial condition $\xi$ and parameter $q_{0}$.

We define the set $O_{t}\subset\\{x\in\Lambda:\zeta_{x}(t)=0\\}$ of _orange_
healthy sites to be the càdlàg process with jumps at
$\bigcup_{x\in\Lambda}P_{x}$ defined as follows. We first set
$O_{0}=\\{x\in\Lambda:\xi_{x}=0\\}$, so that all healthy sites are initially
orange. Then, for each $x\in\Lambda$ and $t\in P_{x}$, we set

$O_{t}=\begin{cases}O_{t-}\setminus\\{x\\}&\zeta_{x}(t)=1,\\\
O_{t-}\cup\\{x\\}&\zeta_{x}(t)=0,\exists y\in
O_{t-},d(x,y)\leq\|\mathcal{U}\|,\\\ O_{t-}&\zeta_{x}(t)=0,\forall y\in
O_{t-},d(x,y)>\|\mathcal{U}\|.\end{cases}$ (7.1)

It is clear that $x\in O_{t}$ implies $\zeta_{x}(t)=0$, so that $O_{t}$ is
indeed a subset of the healthy sites in the $\\{U_{0}\\}$-CP $\zeta$. Indeed,
by construction, $\bigcup_{x\in\Lambda}P_{x}$ are the only times when the
$\\{U_{0}\\}$-CP $\zeta$ may change.

######  Lemma 7.1.

Consider the $\\{U_{0}\\}$-CP $\zeta$ on $\Lambda$ with boundary condition
$\tau$, initial condition $\xi$ and parameter $q_{0}$. Also consider the
$\mathcal{U}$-KCM $\eta^{\mathbf{1}}$ and $\eta^{\xi^{\prime}}$ with parameter
$q\geq q_{0}$ on $\Lambda$ with boundary condition $\tau$ and initial
conditions ${\mathbf{1}}$ and $\xi^{\prime}\in\Omega_{\Lambda}$ respectively,
for some $\xi^{\prime}\geq\xi$. Then for any $t\geq 0$ we have that

$\left\\{x\in\Lambda:\eta_{x}^{{\mathbf{1}}}(t)\neq\eta_{x}^{\xi^{\prime}}(t)\right\\}\subset
O_{t}.$ (7.2)

In particular, if $O_{t}=\varnothing$, then
$\eta^{\mathbf{1}}(t^{\prime})=\eta^{\xi^{\prime}}(t^{\prime})$ for all
$t^{\prime}\geq t$ and $\xi^{\prime}\geq\xi$. The same holds, if we replace
the $\mathcal{U}$-KCM by the $\mathcal{U}$-CP.

Before proving the lemma, let us prove the following standard fact.

######  Claim 7.2.

Consider the $\mathcal{U}$-KCM $\eta^{\xi^{\prime}}$ and $\\{U_{0}\\}$-CP
$\zeta$ as in Lemma 7.1. Then for all $t\geq 0$ we have

$\zeta_{x}(t)\leq\eta^{\xi^{\prime}}_{x}(t)\text{ for all }x\in{\Lambda}.$
(7.3)

###### Proof.

Equation 7.3 holds at $t=0$ since $\xi^{\prime}\geq\xi$. Assume Eq. 7.3 holds
for all $t^{\prime}<t\in P_{x}$ for some $x\in\Lambda$. If $U_{x}(t)>q_{0}$,
Eq. 7.3 clearly remains true, since $\zeta_{x}(t)=0$. On the other hand, if
$U_{x}(t)\leq q_{0}\leq q$ and $\zeta_{x}(t)=1$, we have two possibilities. If
$\zeta_{x}(t-)=1$, we are done by using Eq. 7.3 for $t-$. Instead, if
$\zeta_{x}(t-)=0$, then necessarily
$\zeta_{x+U_{0}}(t-)=\zeta_{x+U_{0}}(t)={\mathbf{1}}$. But then Eq. 7.3 for
$t-$ implies that the constraint $c_{x}$ is satisfied in
$\eta^{\xi^{\prime}}(t)$, so that $\eta^{\xi^{\prime}}_{x}(t)=1$, concluding
the proof of the claim. ∎

###### Proof of Lemma 7.1.

Since $\xi^{\prime}\geq\xi$ and initially all healthy sites in $\xi$ are
orange, Eq. 7.2 holds at $t=0$. Fix $x\in\Lambda$ and $t\in P_{x}$ and assume
that Eq. 7.2 holds for any $t^{\prime}<t$. Further assume for a contradiction
that $\eta_{x}^{\mathbf{1}}(t)\neq\eta_{x}^{\xi^{\prime}}(t)$, but $x\not\in
O_{t}$. We consider several cases.

Assume $\zeta_{x}(t)=1$. Then by Claim 7.2
$\eta_{t}^{\mathbf{1}}(t)=\eta_{t}^{\xi^{\prime}}(t)=1$, so Eq. 7.2 holds. For
the $\mathcal{U}$-CP instead of the $\mathcal{U}$-KCM, Claim 7.2 is a direct
consequence of attractiveness.

Assume the contrary, that $\zeta_{x}(t)=0$. If there exists $y\in O_{t-}$ such
that $d(x,y)\leq\|\mathcal{U}\|$, then by definition $x\in O_{t}$, so Eq. 7.2
cannot fail at $x$.

The remaining case is $\zeta_{x}(t)=0$ and there does not exist $y\in O_{t-}$
such that $d(x,y)\leq\|\mathcal{U}\|$. Then from Eq. 7.2 at $t-$ the
$\eta^{\mathbf{1}}$ and $\eta^{\xi^{\prime}}$ processes coincide in the
neighbourhood of $x$, so they do so also after the attempted update at $x$,
regardless whether it is successful or not. ∎

##  8 Renormalisation of CP to BP with death

Recall from Section 7 that $U_{0}\in\mathcal{U}$ is such that
$U_{0}\subset{\mathbb{H}}_{u}$ for some $u\in S^{d-1}$. In this section we
perform a simple renormalisation of the $\\{U_{0}\\}$-CP to the
$\mathcal{U}_{0}$-BP with death (recall from Sections 2.5 and 2.6 that BP is a
CA, so we may consider its version with death), where $\mathcal{U}_{0}$
contains a single set given by $\\{0,-1\\}^{d}\setminus\\{0\\}$. The
renormalisation is similar to the ones used in [Mareche20, Mareche19a,
Mountford19], where one obtains oriented percolation as a result of the
renormalisation. We start by fixing the relevant geometry.

$u_{2}$$u_{1}$$R\lambda_{2}v_{2}$$R\lambda_{1}v_{1}$$Te_{d+1}$ (a) The box $B$
defined in Eq. 8.1 with its base $\hat{B}$, containing the vectors
$u_{1},\dots,u_{d}$, shaded.

$u_{2}$$u_{1}$$u$ (b) The $2^{d}$ box bases $\hat{B}_{x+y}$ for
$y\in\\{0,-1\\}^{d}$. The Poisson process points $p_{z}$ occur in the hatched
base $\hat{B}_{x}$ in the order of increasing $\langle z,u\rangle$, as
indicated by the hatching direction.

$B_{x-(1,1),\tau-1}$$B_{x-(0,1),\tau-1}$$B_{x-(1,0),\tau-1}$$B_{x,\tau}$ (c)
If the shaded box $B_{x,\tau}$ is good, we are able to propagate the infection
from the three hatched boxes to $B_{x,\tau}$.

Figure 1: Illustration of the renormalisation of Section 8 in the case $d=2$.

Fix linearly independent directions $(u_{i})_{i=1}^{d}$ such that:

  * •

for all $i\in\\{1,\dots,d\\}$, $\lambda^{\prime}_{i}u_{i}\in{\mathbb{Z}}^{d}$
for some $\lambda^{\prime}_{i}>0$;

  * •

the $u_{i}$ are sufficiently close to $u$ so that
$U_{0}\subset{\mathbb{H}}_{u_{i}}$.

The latter condition can be guaranteed thanks to the fact that the half-spaces
${\mathbb{H}}_{u_{i}}$ were defined as open sets. For each $i$ let us
decompose, via the Gram-Schmidt algorithm, $u_{i}=v_{i}+u_{i}^{\prime}$ with
$\langle v_{i},u_{j}\rangle=0$ for all $j\neq i$ and
$u_{i}^{\prime}\in\mathrm{Vect}(\\{u_{j}:j\neq i\\})$. In what follows we
consider time as the $d+1$-th coordinate and we abusively identify $u_{i}\in
S^{d-1}$ with $(u_{i},0)\in S^{d}$ for all $i$ to lighten notation and
similarly we identify $v_{i}$ with $(v_{i},0)$. By examining the Gram-Schmidt
algorithm, one can check that there also exist $\lambda_{i}>0$ such that
$\lambda_{i}v_{i}\in{\mathbb{Z}}^{d}$. Define the _space-time box_ (see Fig.
1(a))

$\displaystyle B$
$\displaystyle{}=\sum_{i=1}^{d}(\lambda_{i}v_{i}[0,R))+[0,T)e_{d+1}$
$\displaystyle{}=\left\\{a\in{\mathbb{R}}^{d}:\forall
i\in\\{1,\dots,d\\},\frac{\langle
a,u_{i}\rangle}{\lambda_{i}\|v_{i}\|^{2}R}\in[0,1)\right\\}\times[0,T)\subset\mathbb{R}^{d+1}$
(8.1)

for an integer constant $R>0$ chosen sufficiently large depending on $U_{0}$
and all $u_{i},v_{i}$ and another constant $T>0$ chosen also sufficiently
large depending on $R$. We refer to
$\hat{B}=\sum_{i=1}^{d}(\lambda_{i}v_{i}[0,R))\subset{\mathbb{R}}^{d}$ as the
_base_ of $B$ and to $\hat{H}=[0,T)$ as its _height_. For any
$(x,\tau)=(x_{1},\dots,x_{d},\tau)\in{\mathbb{Z}}^{d+1}$ we set
$B_{x,\tau}=B+\sum_{i=1}^{d}R\lambda_{i}x_{i}{v}_{i}+T\tau e_{d+1}$, which we
view as our renormalised space-time points. We similarly define $\hat{B}_{x}$
and $\hat{H}_{\tau}$ as the corresponding space and time projections. This
notation is consistent with that of Section 6 for
$v^{\prime}_{i}=\lambda_{i}v_{i}$.

For each $(x,\tau)\in{\mathbb{Z}}^{d+1}$ we define the event $E_{x,\tau}$ that
the point $(x,\tau)$ is _good_ if the following two conditions, only depending
on the Poisson processes points $(z,t)$ and the uniform random variables
$U_{z}(t)$ with $(z,t)$ contained in
$\bigcup_{y\in\\{0,-1\\}^{d}}B_{x+y,\tau}\cup B_{x+y,\tau-1}$, are satisfied:

  * •

$U_{z}(t)\leq q_{0}$ for all $t\in(\hat{H}_{\tau}\cup\hat{H}_{\tau-1})\cap
P_{z}$ and $z\in\bigcup_{y\in\\{0,-1\\}^{d}}\hat{B}_{x+y}$, where we recall
that $P_{z}$ is the Poisson process associated to vertex $z$;

  * •

For each $z\in\hat{B}_{x}$ there exists $p_{z}\in P_{z}\cap\hat{H}_{\tau-1}$
and $\langle z,u\rangle>\langle z^{\prime},u\rangle$ implies
$p_{z}>p_{z^{\prime}}$.

The box is called _bad_ if it is not good.

The following lemma provides the desired coupling between the $\\{U_{0}\\}$-CP
with parameter $q_{0}$, denoted $\zeta$, and a $\mathcal{U}_{0}$-BP with
death, denoted $\widetilde{\omega}$. In fact, the $\widetilde{\omega}$ process
will not quite be a $\mathcal{U}_{0}$-BP with death, but is defined in the
same way, given the Bernoulli variables $\xi_{x,t}$ from Eq. 2.4, which will
however not be i.i.d. (the tilde is there to remind us of this difference).
Nevertheless, we will somewhat abusively refer to it as a $\mathcal{U}_{0}$-BP
with death despite this.

######  Lemma 8.1.

Consider the $\mathcal{U}_{0}$-BP $\widetilde{\omega}$ with death on
${\mathbb{Z}}^{d}$ with death marks $\xi_{x,\tau}=1$ at points
$(x,\tau)\in{\mathbb{Z}}^{d}\times{\mathbb{N}}$ such that $B_{x,\tau}$ is bad.
Further let its initial condition be given by the configuration where infected
sites $x$ are exactly the sites $x\in{\mathbb{Z}}^{d}$ such that:

  * •

$\hat{B}_{x}$ is fully in state 1 in the initial condition $\zeta{(0)}$ of the
$\\{U_{0}\\}$-CP with parameter $q_{0}$;

  * •

$U_{z}(t)\leq q_{0}$ for all $z\in\hat{B}_{x}$ and $t\in\hat{H}_{0}\cap
P_{z}$.

Then for all $(x,\tau)\in{\mathbb{Z}}^{d}\times{\mathbb{N}}$ and $(y,t)\in
B_{x,\tau}$, if $\zeta_{y}(t)=0$, then $\widetilde{\omega}_{x}(\tau)=0$.

###### Proof.

We prove the statement by induction on $\tau\geq 0$. The base case follows
from the definition of the initial condition of $\widetilde{\omega}$.
Therefore, let $\tau\geq 1$ and assume by contradiction that $\zeta_{y}(t)=0$,
$\widetilde{\omega}_{x}(\tau)=1$ for some $(y,t)\in B_{x,\tau}$. If
$\widetilde{\omega}_{x}(\tau-1)=1$, then by induction $\zeta_{y}((\tau-1)T)=1$
and by the first condition for $B_{x,\tau}$ being good (which holds, because
otherwise $\widetilde{\omega}_{x}(\tau)=0$, since bad boxes are deaths) this
remains true until time $t$, leading to a contradiction. Thus, we may assume
that $\widetilde{\omega}_{x}(\tau-1)=0$, so that (by the definition Eq. 2.5 of
BP) $\widetilde{\omega}_{x+z}(\tau-1)=1$ for all
$z\in\\{0,-1\\}^{d}\setminus\\{0\\}$ and $\zeta_{w}((\tau-1)T)=1$ for all
$w\in\hat{B}_{x+z}$ by induction hypothesis. Since the box $B_{x,\tau}$ is
good, there has been no attempt to put $0$ at $y$ after time $\tau T$ in the
contact process, so it suffices to show that $\zeta_{y}(\tau T)=1$ to reach a
contradiction.

We claim that by our choice of geometry (see Fig. 1),

$U_{0}+\hat{B}_{x}\subset\bigcup_{z\in\\{0,-1\\}^{d}}\hat{B}_{x+z}.$ (8.2)

To see this, notice that

$\displaystyle\hat{B}_{x}$
$\displaystyle{}=\left\\{a\in{\mathbb{R}}^{d}:\forall
i\in\\{1,\dots,d\\},\frac{\langle
a,u_{i}\rangle}{\lambda_{i}\|v_{i}\|^{2}R}\in[x_{i},x_{i}+1)\right\\},$
$\displaystyle\bigcup_{z\in\\{0,-1\\}^{d}}\hat{B}_{x+z}$
$\displaystyle{}=\left\\{a\in{\mathbb{R}}^{d}:\forall
i\in\\{1,\dots,d\\},\frac{\langle
a,u_{i}\rangle}{\lambda_{i}\|v_{i}\|^{2}R}\in[x_{i}-1,x_{i}+1)\right\\}.$

Therefore, for any $a\in\hat{B}_{x}$, $b\in a+U_{0}$ and $i\in\\{1,\dots,d\\}$
we have

$\lambda_{i}\|v_{i}\|^{2}R(x_{i}-1)\leq\langle
a,u_{i}\rangle-\|\mathcal{U}\|\leq\langle b,u_{i}\rangle<\langle
a,u_{i}\rangle<\lambda_{i}\|v_{i}\|^{2}R(x_{i}+1),$

if we choose $R$ large enough so that
$\lambda_{i}\|v_{i}\|^{2}R>\|\mathcal{U}\|$ for every $i$. Hence,
$b\in\bigcup_{z\in\\{0,-1\\}^{d}}\hat{B}_{x+z}$ as claimed.

Finally, observe that by the second condition for $B_{x,\tau}$ being good,
there has been a sequence of attempts at times $p_{a}\in\hat{H}_{\tau-1}$ to
put $1$ at each site $a\in\hat{B}_{x}$. Since the sequence is in the order of
increasing scalar product with $u$ and $a+U_{0}$ is contained in
$(a+{\mathbb{H}}_{u})\cap\bigcup_{z\in\\{0,-1\\}^{d}}\hat{B}_{x+z}$ (again,
provided that $R$ is large enough), the constraint $c_{a}({\zeta(p_{a})})$ is
fulfilled for each of them, so we are done. ∎

The following corollary will be more convenient for our purposes.

######  Corollary 8.2.

Fix $U_{0}$ as above and $\delta>0$. There exist $\varepsilon_{3}>0$ and
$R_{1}>0$ such that for any $R\geq R_{1}$ there exists $T_{1}$ such that for
any $T\geq T_{1}$ there exists $\varepsilon_{4}>0$ such that for any
$q_{0}\in[1-\varepsilon_{4},1]$ the following holds. Consider the
$\\{U_{0}\\}$-CP $\zeta$ with parameter $q_{0}$ and initial condition given by
$\zeta_{y}(0)=\xi_{x}$ for all $y\in\hat{B}_{x}$ and $x\in{\mathbb{Z}}^{d}$,
where $\xi\sim\mu_{1-\varepsilon_{3}}$. Then the trajectory at times $\tau\geq
1$ of the $\mathcal{U}_{0}$-BP with $\delta$ death and initial condition
${\mathbf{1}}$ is stochastically dominated by the the process given by

$\hat{\omega}_{x}(\tau)=\mathbbm{1}_{\forall(y,t)\in
B_{x,\tau-1},\zeta_{y}(t)=1}.$

###### Proof.

Fix $\varepsilon_{3}>0$ small enough depending on $\delta$. Taking $T$ large
after $R$ and then $\varepsilon_{4}>0$ small, it is clear that the probability
of a box being good can be made larger than $1-\varepsilon_{3}$. Moreover,
good boxes together with the initial condition $\widetilde{\omega}(0)$ from
Lemma 8.1 form a percolation with bounded range of dependence. Therefore, by
the Liggett–Schonmann–Stacey theorem [Liggett97] it stochastically dominates
an independent percolation with parameter $1-\delta$, provided
$\varepsilon_{3}$ is small enough. By attractiveness of $\mathcal{U}_{0}$-BP,
this together with Lemma 8.1 completes the proof. Indeed, we simply observed
that the first step of $\mathcal{U}_{0}$-BP with $\delta$ death and initial
condition ${\mathbf{1}}$ has distribution $\mu_{1-\delta}$. ∎

##  9 Exponential decay

In this section we establish several exponential decay properties. It can be
viewed independently of the rest of the paper and will entail results of
independent interest. We therefore adopt a rather abstract and general
framework, to keep the approach as flexible as possible. It will be convenient
to work in ${\mathbb{Z}}^{D}$ with $D\geq 1$, which will play the role of
$d+1$ in our original setting.

###  9.1 Decorated set systems

######  Definition 9.1 ($k$-connectivity).

Fix a positive real $k$. We say that a set $X\subset{{\mathbb{R}}}^{D}$ is
_$k$ -connected_, if for every $x,y\in X$ there exists a sequence
$x_{0}=x,x_{1},\dots,x_{m}=y$ of elements of $X$ such that
$d(x_{i},x_{i+1})\leq k$ for all $i\leq m-1$.

######  Definition 9.2 (Decorated set system).

A _decorated set_ is a pair $(Z,\gamma)$ with $Z\subset{\mathbb{Z}}^{D}$
nonempty and bounded and $\gamma\in\Gamma_{Z}$ for some set $\Gamma_{Z}$,
which may be empty for some $Z\subset{\mathbb{Z}}^{D}$, making them impossible
to decorate. Two decorated sets $(Z_{1},\gamma_{1})$ and $(Z_{2},\gamma_{2})$
are called _disjoint_ , if $Z_{1}\cap Z_{2}=\varnothing$. A _decorated set
system_ is a probability measure ${\mathbb{P}}$ and a function $E$ that
associates to each decorated set $(Z,\gamma)$ an event $E(Z,\gamma)$ in such a
way that for any finite set of disjoint decorated sets
$(Z_{i},\gamma_{i})_{i\in I}$ we have

${\mathbb{P}}\left(\bigcap_{i\in I}E(Z_{i},\gamma_{i})\right)\leq\prod_{i\in
I}{\mathbb{P}}\left(E(Z_{i},\gamma_{i})\right).$ (9.1)

In all applications below of this construction, we will actually have equality
in (9.1) but we work under this more general condition, as the proof of
Proposition 9.3 works exactly the same with inequality or with equality. In
what follows for any $X\subset{\mathbb{R}}^{D}$ we denote
$\operatorname{diam}(X)=\sup_{x,y\in X}(d(x,y))$ with the convention
$\operatorname{diam}(\varnothing)=-\infty$.

######  Proposition 9.3.

Consider a decorated set system. Assume that for some $C>1$ and $\epsilon>0$
small enough depending on $C$ the following hold:

  1. 1.

For all decorated sets $(Z,\gamma)$ we have $\operatorname{diam}(Z)\leq C|Z|$.

  2. 2.

For every $z\in{\mathbb{Z}}^{D}$ the number of decorated sets $(Z,\gamma)$
such that $|Z|=n$ and $z\in Z$ is at most $C^{n}$.

  3. 3.

For all decorated sets $(Z,\gamma)$ we have
${\mathbb{P}}(E(Z,\gamma))\leq\epsilon^{|Z|/C}$.

Fix $n,k\geq 1$ and $x\in{\mathbb{Z}}^{D}$. Then the probability that $x$ is
the endpoint of a $k$-connected path $P$ to $y\in{\mathbb{Z}}^{D}$, such that
$d(x,y)\geq n$ and for all $p\in P$ there exists a decorated set
$(Z_{p},\gamma_{p})$ such that $p\in Z_{p}$ and $E(Z_{p},\gamma_{p})$ occurs,
is at most $\epsilon^{n/({7}C+{7}k)^{2}}$.

Note that the second condition implies that $\Gamma_{Z}$ is finite for every
$Z$. Proposition 9.3 will be proved in Section 9.3, but before that, let us
provide a few applications to make the abstract setting more concrete.

###  9.2 Applications

While it is not hard to imagine examples of decorated set systems satisfying
the conditions of Proposition 9.3, let us give a more explicit toy example to
get used to the notion before turning to more interesting applications based
on Toom contours and variants thereof.

######  Example 9.4.

Consider a field of i.i.d. Bernoulli random variables $\xi_{x}$ for
$x\in{\mathbb{Z}}^{D}$. For each finite non-empty $Z\subset{\mathbb{Z}}^{D}$
the set of decorations $\Gamma_{Z}$ is empty if $Z$ is not a 1-connected path
and a singleton otherwise. The event $E(Z,\gamma)$ corresponds to
$\bigcap_{x\in Z}\\{\xi_{x}=1\\}$. Then Eq. 9.1 is satisfied by independence.
Condition 1 of Proposition 9.3 follows by 1-connectedness. Condition 2 holds,
because one can encode a 1-connected path by the sequence of its increments,
so the number of paths containing $z\in{\mathbb{Z}}^{D}$ of cardinality $n$ is
at most $n(2D)^{n}$. Condition 3 is also verified, since
${\mathbb{P}}(E(Z,\gamma))=({\mathbb{P}}(\xi_{0}=1))^{|Z|}$. Hence, if the
Bernoulli variables have a sufficiently small parameter, Proposition 9.3
yields an exponentially small bound on the probability that one can find a
$k$-connected path starting at 0 such that each of its points belongs to a
$1$-connected path with all Bernoulli variables equal to 1. Thus, in this case
this degenerates into looking for a $k$-connected path in the set of sites
with Bernoulli variable equal to 1, so the conclusion of the proposition is a
classical fact.

The next corollary will be used to control the $\mathcal{U}_{0}$-BP with death
we recovered in Corollary 8.2. We formulate it more generally for cellular
automata with death.

######  Corollary 9.5.

Let $k$ be a positive real number and let the map $\phi$ define a CA which is
attractive and an eroder, as defined in Section 2.5. Then there exist $c>0$
and $\delta_{0}>0$ such that for all $\delta\in(0,\delta_{0}]$ the $\phi$-CA
$\omega^{\bar{\nu}}$ with death parameter $\delta$ and with initial condition
given by its upper invariant measure $\bar{\nu}$ satisfies the following.
Denoting by $A_{x,t}$ the maximal $k$-connected component of
$(x,t)\in{\mathbb{Z}}^{d+1}$ with $\omega^{\bar{\nu}}_{a}(s)=0$ for all
$(a,s)\in A_{x,t}$, it holds that

${\mathbb{P}}\left(\operatorname{diam}(A_{x,t})\geq\ell\right)\leq\delta^{c(\ell+1)}.$

######  Remark 9.6.

Let us note that Corollary 9.5 provides a much more straightforward and
general proof of several of the main results of [Poncelet13] (see Theorems 5,
6 and 7 there).

###### Proof of Corollary 9.5.

Corollary 9.5 follows directly from Proposition 9.3, applied to the decorated
set system given by Toom contours [Toom80, Swart22] and their presence. Since
these notions are rather technical to define, while the details of the
definition are irrelevant, let us instead highlight the high level viewpoint,
referring to [Swart22] for more details (the facts we will need were actually
already known since [Toom80]).

A Toom contour rooted at $z\in{\mathbb{Z}}^{d+1}$ consists of a finite set
$Z\subset{\mathbb{Z}}^{d+1}$ (with $z\in Z$) equipped with a complicated
decoration taking the form of a connected coloured oriented multigraph with
vertex set $Z$, such that the endpoints of each edge are at most at some
bounded mutual distance (depending on the support of $\phi$). Connectedness
readily implies condition 1.

In each Toom contour one can identify a set $Z_{*}\subset Z$ of sinks. A
contour is said to be present if $\xi_{x,t}=1$ (recall Section 2.5) for each
sink $(x,t)$, so that disjoint decorated sets occur independently. In
particular, Toom contours form a decorated set system and their probability of
occurrence is $\delta^{|Z_{*}|}$. A key and highly non-trivial fact
[Swart22]*Theorem 7 is that if $\omega_{x}^{\bar{\nu}}(t)=0$, then some non-
empty finite Toom contour rooted at $(x,t)$ occurs. Moreover, [Swart22]*Lemma
13 ensures that the number of edges (and, therefore, the number of vertices by
connectedness) of a Toom contour is at most a constant multiple of $|Z_{*}|$,
thus proving condition 3 . Finally, [Swart22]*Lemma 14 shows that the number
of Toom contours containing a given point and with $N$ edges is at most
exponential in $N$ and, therefore, in the number of vertices by the previous
result, so condition 2 is also satisfied. ∎

The next corollary will not be used in the proof of our main results, but we
include it, since it is of independent interest and follows analogously.

######  Corollary 9.7.

Consider $\mathcal{U}^{\prime}$-BP $\omega$ with subcritical
$\mathcal{U}^{\prime}$. Fix $p>0$ and let $C_{0}$ be the $k$-connected
component of the origin in
$\\{x\in{\mathbb{Z}}^{d}:\lim_{t\to\infty}\omega_{x}^{\mu_{p}}(t)=1\\}$. Then
there exists $c=c(\mathcal{U}^{\prime},k)>0$ such that for all $p>0$ small
enough and $\ell\geq 0$ we have

${\mathbb{P}}(\operatorname{diam}(C_{0})\geq\ell)\leq p^{c(\ell+1)}.$

We recall that non-subcritical models are exactly those with ${q_{\rm
c}^{\mathrm{\scriptstyle{BP}}}}=0$ [Balister22, Balister22b], so
$C_{0}={\mathbb{Z}}^{d}$ for all $p>0$ and it is meaningless to consider them
in the above sense.

######  Remark 9.8.

Corollary 9.7 provides a positive answer to [Balister16]*Question 12 in the
perturbative regime. As pointed out in [Hartarsky21]*Section 7.1.2, the stated
exponential decay cannot hold for all $p<{q_{\rm
c}^{\mathrm{\scriptstyle{BP}}}}$ in general. Nevertheless, in the spirit of
[Alves21a] one could expect that it does hold up to a different critical
threshold $p_{\mathrm{c}}(k)\leq{q_{\rm c}^{\mathrm{\scriptstyle{BP}}}}$, past
which the diameter is a.s. infinite. On a different note, Corollary 9.7 was
proved by more classical means and used in [Blanquicett20]*Theorem 4.2 for
_trivial_ subcritical update families in two dimensions for $k=1$, which we
therefore vastly generalise.

###### Proof of Corollary 9.7.

Corollary 9.7 follows from Proposition 9.3 essentially along the same lines as
Corollary 9.5 follows from Proposition 9.3, but using a different decorated
set system. Namely, we consider the space embeddings of shattered contours,
which are the central object of study in [Hartarsky22Toom]444Note that in
[Hartarsky22Toom] the roles of 0 and 1 are exchanged with respect to the
present work., similarly to Toom contours in [Swart22]. Again, the definition
of these objects, which are projections of equivalence classes of Toom
contours, is rather technical and unimportant for us, so we refer to
[Hartarsky22Toom] for those details. Instead, let us indicate that the
presence of a finite non-empty shattered contour rooted at
$x\in{\mathbb{Z}}^{d}$ is implied by
$\lim_{t\to\infty}\omega_{x}^{\mu_{p}}(t)=1$ [Hartarsky22Toom]*Corollary 4.3;
their numbers of edges and vertices are bounded by a constant multiple of the
number of sinks [Hartarsky22Toom]*Lemma 5.2; the number of shattered Toom
contours rooted at a given point is at most exponentially large in the number
of sinks [Hartarsky22Toom]*Lemma 5.3. ∎

Thus, our only remaining task in this section is to prove Proposition 9.3.
Before doing so, let us mention a natural question closely related to
Corollary 9.5.

######  Question 9.9.

Fix $\varepsilon>0$. Is it true that for the $\mathcal{U}_{0}$-BP with
$\delta$ death, with $\delta>0$ small enough, the upper invariant measure
stochastically dominates $\mu_{1-\varepsilon}$? More generally, is this true
for any attractive eroder?

###  9.3 Proof of Proposition 9.3

We fix a decorated set system and $C$, $\epsilon$, $n$, $k$, and $x$ as in
Proposition 9.3. Since our sets can be quite fuzzy we begin by regularising
them.

######  Definition 9.10.

Given a non-empty $Z\subset{\mathbb{Z}}^{d}$, we set

$\bar{Z}:=\left\\{x\in{\mathbb{Z}}^{d}:d(x,Z)\leq
3(1+\operatorname{diam}(Z))\right\\}.$

Let us fix a $k$-connected path $P=(p_{0}=x,p_{1},\dots,p_{l}=y)$ with
$d(x,y)\geq n$. We further fix decorated sets $(Z_{p},\gamma_{p})$ with $p\in
Z_{p}$ for each $p\in P$. We next run the following algorithm.

######  Algorithm 9.11.

Define $i_{0}=0$, $I_{0}=\\{0\\}$ and $X_{0}=\bar{Z}_{p_{0}}$ and initialise
$t=0$. While $P\not\subset X_{t}$, repeat the following, then return
$(I_{t},X_{t},t)$. Increment $t$ by setting $t:=t+1$. Set $i_{t}=\min\\{j\leq
l:p_{j}\not\in X_{t-1}\\}$. Let $J_{t}=\\{j\in I_{t-1}:Z_{p_{j}}\cap
Z_{p_{i_{t}}}\neq\varnothing\\}$. Set $I_{t}=\\{i_{t}\\}\cup(I_{t-1}\setminus
J_{t})$. Set $X_{t}=\bigcup_{j\in I_{t}}\bar{Z}_{p_{j}}$.

By definition, if the algorithm terminates and outputs $(I_{t},X_{t},t)$, then
$P\subset X_{t}$. Moreover, by induction we have that for all $t^{\prime}\leq
t$ it holds that $Z_{a}\cap Z_{b}=\varnothing$ for all $a\neq b\in
I_{t^{\prime}}$, using the definition of $J_{t^{\prime}}$. To see that
Algorithm 9.11 terminates, it suffices to see that $X_{t^{\prime}}\cap P$ is
strictly increasing in $t^{\prime}$, since $P$ is finite (on the other hand,
we note that $I_{t^{\prime}}$ is not necessarily monotone in $t^{\prime}$. In
order to prove this, we first show that $X_{t^{\prime}}\cap P$ is non-
decreasing and then exhibit an element which is in $X_{t^{\prime}}\cap P$, but
not in $X_{t^{\prime}-1}\cap P$.

######  Claim 9.12.

For any $t^{\prime}\in\\{1,\dots,t\\}$ we have $X_{t^{\prime}}\cap P\supset
X_{t^{\prime}-1}\cap P$.

###### Proof.

By the definitions of $X_{t^{\prime}}$ and $I_{t^{\prime}}$, we have that

$X_{t^{\prime}-1}\setminus X_{t^{\prime}}\subset\bigcup_{j\in
J_{t^{\prime}}}\bar{Z}_{p_{j}}\setminus\bar{Z}_{p_{i_{t^{\prime}}}}.$ (9.2)

Thus, it remains to show that
$\bar{Z}_{p_{i_{t^{\prime}}}}\supset\bar{Z}_{p_{j}}$ for all $j\in
J_{t^{\prime}}$.

Fix $j\in J_{t^{\prime}}\subset I_{t^{\prime}-1}$, so $Z_{p_{j}}\cap
Z_{p_{i_{t^{\prime}}}}\neq\varnothing$ by the definition of $J_{t^{\prime}}$.
Then

$\operatorname{diam}\left(Z_{p_{i_{t^{\prime}}}}\right)\geq
d\left(p_{i_{t^{\prime}}},p_{j}\right)-\operatorname{diam}\left(Z_{p_{j}}\right)\geq
d\left(p_{i_{t^{\prime}}},p_{j}\right)/3+2+\operatorname{diam}\left(Z_{p_{j}}\right),$

where we first used the triangle inequality, then the fact that
$p_{i_{t^{\prime}}}\not\in\bar{Z}_{{p}_{j}}$ by definition of $i_{t^{\prime}}$
and $X_{t^{\prime}-1}$. But then
$\bar{Z}_{p_{i_{t^{\prime}}}}\supset\bar{Z}_{p_{j}}$ by the triangle
inequality and we are done. ∎

We next claim that for any $t^{\prime}\in\\{1,\dots,t\\}$ we have

$p_{i_{t^{\prime}}}\in X_{t^{\prime}}\setminus
X_{t^{\prime}-1}=\bar{Z}_{p_{i_{t^{\prime}}}}\setminus\bigcup_{j\in
I_{t^{\prime}-1}}\bar{Z}_{p_{j}}.$ (9.3)

Indeed, if $p_{i_{t^{\prime}}}\in\bar{Z}_{p_{j}}$ for some $j\in
I_{t^{\prime}-1}$, that would imply $p_{i_{t^{\prime}}}\in X_{t^{\prime}-1}$
by the definition of $X_{t^{\prime}-1}$, but this contradicts the definition
of $i_{t^{\prime}}$.

Combining Claims 9.12 and 9.3, we get that Algorithm 9.11 does terminate, so
$I_{t},X_{t},t$ are well defined.

######  Claim 9.13.

$X_{t}$ is $k$-connected.

###### Proof.

We prove by induction that $X_{t^{\prime}}$ is connected for all
$t^{\prime}\in\\{0,\dots,t\\}$. The base follows since $X_{0}=\bar{Z}_{p_{0}}$
is $k$-connected, by Definitions 9.10 and 9.1 and $k\geq 1$. By Eq. 9.3,
$X_{t^{\prime}}\setminus
X_{t^{\prime}-1}\subset\bar{Z}_{p_{i_{t^{\prime}}}}\subset X_{t^{\prime}}$,
the last inclusion using the definition of $X_{t^{\prime}}$ and
$I_{t^{\prime}}$. Moreover, by the proof of Claim 9.12 $X_{t^{\prime}}\supset
X_{t^{\prime}-1}$. Thus, since $\bar{Z}_{p_{i_{t^{\prime}}}}$ is
$k$-connected, it remains to show that
$d(X_{t^{\prime}-1},\bar{Z}_{p_{i_{t^{\prime}}}})\leq k$. In fact, the
stronger statement $d(p_{i_{t^{\prime}}},X_{t^{\prime}-1})\leq k$ holds,
because the definition of $i_{t^{\prime}}$ gives $p_{i_{t^{\prime}}-1}\in
X_{t^{\prime}-1}$, and $i_{t^{\prime}}\neq 0$ for $t^{\prime}>0$, since
$X_{t^{\prime}-1}\supset X_{0}=\bar{Z}_{p_{0}}\ni p_{0}$ and because
consecutive $p_{j}$ are at distance at most $k$. ∎

By Claim 9.13 we can extract from $I_{t}$ a sequence
$i^{\prime}_{1},\dots,i^{\prime}_{m}$ such that $d(Y_{j},Y_{j+1})\leq k$,
$x\in Y_{1}$ and $y\in Y_{m}$, where $Y_{j}=\bar{Z}_{p_{i^{\prime}_{j}}}$.
This provides us with the following type of object.

######  Definition 9.14 (Chain).

A _chain starting at $x$ of length at least $n$_ is a sequence of disjoint
decorated sets $(V_{j},\gamma_{j})_{j=1}^{m}$ such that
$d(\bar{V}_{j},\bar{V}_{j+1})\leq k$ for all $j\leq m-1$, $x\in\bar{V}_{1}$
and there exists $y\in\bar{V}_{m}$, such that $d(x,y)\geq n$.

We are now ready to do a union bound over all chains, since their decorated
sets are disjoint, so the events involved are negatively correlated. Hence,
the probability in Proposition 9.3 is at most the sum over all chains
$(V_{j},\gamma_{j})_{j=1}^{m}$ starting at $x$ of length at least $n$ of

$\prod_{j=1}^{m}\epsilon^{|V_{j}|/C}.$ (9.4)

Observe that by condition 1 of Proposition 9.3, we have

$n\leq\sum_{i=1}^{m}\left(k+\operatorname{diam}\left(\bar{V}_{i}\right)\right)\leq
mk+{6}m+{7}\sum_{i=1}^{m}\operatorname{diam}\left(V_{i}\right)\leq{7(C+k)}\sum_{i=1}^{m}|V_{i}|.$
(9.5)

Further note that for any $i\in\\{1,\dots,m-1\\}$ the distance between an
arbitrarily chosen point in $V_{i}$ and one in $V_{i+1}$ is at most

$k+\operatorname{diam}\left(\bar{V}_{i}\right)+\operatorname{diam}\left(\bar{V}_{i+1}\right)\leq
k+{12}+{14}C\max(|V_{i}|,|V_{i+1}|).$

Therefore, the number of ways to fix the positions of one distinguished point
$\pi_{i}$ in each $V_{i}$ with $\pi_{1}=x$ is at most

$\prod_{i=1}^{m-1}(1+2(k+{12}+{14}C\max(|V_{i}|,|V_{i+1}|)))^{d}\leq\prod_{i=1}^{m}30(k+C|V_{i}|)^{2d}.$
(9.6)

Combining Eqs. 9.4, 9.5 and 9.6 with condition 2 of Proposition 9.3, the
probability we seek to bound in Proposition 9.3 is at most

$\sum_{\begin{subarray}{c}m,n_{1},\dots,n_{m}\geq 1\\\ \sum_{i=1}^{m}n_{i}\geq
n/(7(C+k))\end{subarray}}\prod_{i=1}^{m}C^{n_{i}}30(k+Cn_{i})^{2d}\epsilon^{n_{i}/C}.$
(9.7)

For $\epsilon$ small enough Eq. 9.7 is clearly at most
$\epsilon^{n/{({7}C+{7}k)^{2}}}$ as desired, completing the proof of
Proposition 9.3.

##  10 Assembling Theorem 3.3

In this section we assemble the results of Sections 6, 7, 8 and 9 in order to
prove Theorem 3.3. Therefore, let us fix an update family $\mathcal{U}$ which
is not trivial subcritical (otherwise ${\tilde{q}_{\rm
c}^{\mathrm{\scriptstyle{KCM}}}}=1$ and there is nothing to prove) and
$U_{0}\in\mathcal{U}$ such that $U_{0}\in{\mathbb{H}}_{u}$ for some $u\in
S^{d-1}$. Let $v_{i}^{\prime}=v_{i}\lambda_{i}$ for all $i\in\\{1,\dots,d\\}$,
where $v_{i},\lambda_{i}$ are chosen as in Section 8. Let $\delta_{0}$ be as
in Corollary 9.5 for $k=\sqrt{d+1}$ and $\phi$ be the map corresponding to
$\mathcal{U}_{0}$-BP (recall from Section 8 that
$\mathcal{U}_{0}=\\{\\{0,-1\\}^{d}\setminus\\{0\\}\\}$), which is clearly an
eroder attractive cellular automaton. Then let $\varepsilon_{3}$ be as in
Corollary 8.2, setting $\delta=\delta_{0}$. Fix $\alpha>0$. Let
$R=\max(R_{0},R_{1})$, where $R_{0}$ is as in Lemma 6.1 and $R_{1}$ is as in
Corollary 8.2. Let $T=\max(T_{0},T_{1})$, where $T_{0}$ is as in Lemma 6.1 and
$T_{1}$ is as in Corollary 8.2. Let $\varepsilon_{1}$ be as in Lemma 6.1.
Finally, let $p\in[{\tilde{q}_{\rm c}^{\mathrm{\scriptstyle{KCP}}}}+\alpha,1]$
and $\varepsilon=\min(\varepsilon_{1},\varepsilon_{4})$, with
$\varepsilon_{4}$ from Corollary 8.2, and $q\in[1-\varepsilon,1]$.

Let $\eta^{\mu_{p}}$ denote the $\mathcal{U}$-KCM on ${\mathbb{Z}}^{d}$ with
parameter $q$ and initial condition with law $\mu_{p}$ and $\eta^{\mu_{q}}$ be
the stationary $\mathcal{U}$-KCM with the same parameter. The initial
conditions are coupled so that $\eta^{\mu_{q}}(0)\leq\eta^{\mu_{p}}(0)$ if
$q\leq p$ and vice versa, if the inverse inequality holds. Note, however,
that, due to the non-attractiveness of KCM, this inequality need not be
preserved by the dynamics.

Since $\eta^{\mu_{q}}$ is stationary, we get that

$\left|{\mathbb{E}}\left[f(\eta^{\mu_{p}}(t))-\mu_{q}(f)\right]\right|\leq\|f\|_{\infty}\cdot{\mathbb{P}}\left(\eta_{S}^{\mu_{p}}(t)\neq\eta^{\mu_{q}}_{S}(t)\right),$

where $S$ denotes the support of the local function $f$. By a union bound over
the sites of $S$ and translation invariance, for all $t\geq 0$

${\mathbb{P}}\left(\eta_{S}^{\mu_{p}}(t)\neq\eta^{\mu_{q}}_{S}(t)\right)\leq|S|\cdot{\mathbb{P}}\left(\eta_{0}^{\mu_{p}}(t)\neq\eta_{0}^{\mu_{q}}(t)\right).$

We start by running the two KCM up to time $T$. Then Lemma 6.1 gives that
$\min(\eta^{\mu_{p}}_{y}(T),\eta^{\mu_{q}}_{y}(T))\geq\xi_{x}$ for all
$x\in{\mathbb{Z}}^{d}$, $y\in\hat{B}_{x}$, where
$\xi\sim\mu_{1-\varepsilon_{3}}$ is suitably coupled with the two KCM. In the
application of Lemma 6.1, $p$ is given by $\min(p,q)$.

Let $\zeta$ be the $\\{U_{0}\\}$-CP on ${\mathbb{Z}}^{d}$ starting at time $T$
with parameter $q_{0}={1-}\varepsilon_{4}\leq q$ and initial condition given
by $\zeta_{y}(T)=\xi_{x}$ for all $y\in\hat{B}_{x}$ and
$x\in{\mathbb{Z}}^{d}$. Further recall its orange healthy sites $O_{t}$ from
Section 7, which we now define w.r.t. the initial time $T$ instead of $0$.
Lemma 7.1 and the Markov property give that for all $t\geq T$

${\mathbb{P}}\left(\eta_{0}^{\mu_{p}}(t)\neq\eta_{0}^{\mu_{q}}(t)\right)\leq{\mathbb{P}}(0{\in}O_{t}).$
(10.1)

Recall Eqs. 7.1 and 9.1. Observe that by construction $0\in O_{t}$ implies not
only that $\zeta_{0}(t)=0$, but also that there exists a
$\|\mathcal{U}\|$-connected set $K\subset{\mathbb{Z}}^{d}\times[T,\infty)$ in
space-time which contains $(0,t)$, intersects the hyperplane
${\mathbb{Z}}^{d}\times\\{T\\}$ and satisfies $\zeta_{x}(\theta)=0$ for all
$(x,\theta)\in K$. Indeed, whenever a site is added to $O_{t}$, it has to be
at distance at most $\|\mathcal{U}\|$ from an orange site. Let us call $E_{t}$
the event that $(0,t)$ belongs to a $\|\mathcal{U}\|$-connected component of
space-time points $(x,\theta)\in{\mathbb{Z}}^{d}\times[0,t]$ with
$\zeta_{x}(\theta)=0$, that intersects ${\mathbb{Z}}^{d}\times\\{T\\}$. Then
we just showed that

${\mathbb{P}}(0{\in}O_{t})\leq{\mathbb{P}}(E_{t}).$ (10.2)

We are then ready to apply Corollary 8.2. To that end, let $\omega$ be the
$\mathcal{U}_{0}$-BP with $\delta_{0}$-death and initial condition
${\mathbf{1}}$. Corollary 8.2 gives that we can couple $\omega$ and $\zeta$ in
such a way that for all $x\in{\mathbb{Z}}^{d}$ and $\tau\geq 1$,
$\omega_{x}(\tau)=1$ implies that $\zeta_{y}(t)=1$ for all $(y,t)\in
B_{x,\tau}$.

Then for $t\geq T$ the event $E_{t}$ implies that there is a
$\sqrt{d+1}$-connected component of space-time points
$(x,\tau)\in{\mathbb{Z}}^{d+1}$ such that $\omega_{x}(\tau)=0$ containing both
$(0,\lfloor t/T\rfloor)$ and a point in ${\mathbb{Z}}^{d}\times\\{1\\}$. Let
us denote this event by $F_{\lfloor t/T\rfloor-1}$, so that that for any
$\tau\geq 0$

${\mathbb{P}}(E_{t})\leq{\mathbb{P}}\left(F_{\lfloor t/T\rfloor-1}\right).$
(10.3)

Since the $\mathcal{U}_{0}$-BP with $\delta_{0}$ death is attractive and
${\mathbf{1}}$ is the maximal initial condition, denoting by
$F_{\tau}^{\bar{\nu}}$ the event $F_{\tau}$ with $\omega$ replaced by the
process $\omega^{\bar{\nu}}$ with initial condition distributed according to
its upper invariant measure, we get that for some $c>0$ and any $\tau\geq 0$

${\mathbb{P}}(F_{\tau})\leq{\mathbb{P}}\left(F^{\bar{\nu}}_{\tau}\right)\leq\delta_{0}^{c(\tau+1)},$
(10.4)

where we applied Corollary 9.5. Note that $c$ is now an absolute constant, as
it no longer depends on $\mathcal{U}$, but only on $\mathcal{U}_{0}$, which is
fixed.

Putting Eqs. 10.4, 10.3 and 10.2 together, we get that for all $t\geq T$

${\mathbb{P}}(0\in O_{t})\leq\delta_{0}^{c\lfloor t/T\rfloor}.$ (10.5)

Further recalling Eq. 10.1, this yields

$\left|{\mathbb{E}}\left[f(\eta^{\mu_{p}}(t))-\mu_{q}(f)\right]\right|\leq\|f\|_{\infty}|S|\delta_{0}^{c\lfloor
t/T\rfloor},$

completing the proof of Theorem 3.3.

##  11 Renormalisation of CP to LPP

In this section we perform a renormalisation somewhat similar to the one from
Section 8. This will allow us to control the $\\{U_{0}\\}$-CP on the box
$\Lambda=\\{1,\dots,n\\}^{d}$ with parameter $q_{0}\in[0,1)$ in terms of the
$\\{0,-1\\}^{d}\setminus\\{0\\}$-LPP slowed down by some factor, which we
denote $\mathcal{U}_{0}$-LPP for convenience (recall $\mathcal{U}_{0}$ and
$U_{0}$ from Sections 7 and 8). As noted in Section 2.4, the
$\mathcal{U}_{0}$-LPP coincides with the usual
$\\{-e_{1},\dots,-e_{d}\\}$-LPP, so we will be able to exploit the fact that
this model is known to propagate ballistically.

Recall the boxes $\hat{B}_{x}$ from Section 8 (also recall Fig. 1) and the
direction $u\in S^{d-1}$ such that $U_{0}\subset{\mathbb{H}}_{u}$. For each
$x\in{\mathbb{Z}}^{d}$ we will define its _passage time_ $t_{x}\in[0,\infty)$.
First let

$\Xi=\left\\{x\in{\mathbb{Z}}^{d}:\hat{B}_{x}\cap\Lambda\neq\varnothing\right\\}.$
(11.1)

We set $t_{x}=0$ for all $x\not\in\Xi$. For all other $x$ we define $t_{x}\geq
0$ by induction as follows. The stopping time $t_{x}$ is the first time
$t>\tilde{t}_{x}:=\max_{y\in\\{-1,0\\}^{d}\setminus\\{0\\}}t_{x+y}$ such that
for every $z\in\hat{B}_{x}\cap\Lambda$ there exists $p_{z}\in
P_{z}\cap[\tilde{t}_{x},t]$ such that:

  * •

$U_{z}(p_{z})>q_{0}$

  * •

the collection $(p_{z})_{z\in\hat{B}_{x}}$ satisfies that $\langle
z,u\rangle>\langle z^{\prime},u\rangle$ implies $p_{z}>p_{z^{\prime}}$.

The use of these passage times is clear in the following lemma, where, as
usual, $\zeta$ denotes the $\\{U_{0}\\}$-CP on $\Lambda$ with parameter
$q_{0}$ and boundary condition
${\mathbf{1}}_{{\mathbb{Z}}^{d}\setminus\Lambda}$.

######  Lemma 11.1.

For any $x\in{\mathbb{Z}}^{d}$, $z\in\hat{B}_{x}$ and $t\geq t_{x}$ we have
$\zeta^{\mathbf{1}}_{z}(t)=\zeta^{\mathbf{0}}_{z}(t)$.

###### Proof.

If $z\in\hat{B}_{x}\setminus\Lambda$, the claim is trivial because
$\zeta_{{z}}^{\mathbf{1}}(t)=\zeta_{{z}}^{\mathbf{0}}(t)=1$ for all $t$.
Otherwise, we proceed by induction and we assume that the claim has been
proven for all $z^{\prime}\in\hat{B}_{y}$, $y{\in
x+(\\{0,-1\\}^{d}\setminus\\{0\\})}$, and we want to prove it for
$z\in\hat{B}_{x}$. By the induction hypothesis, the two processes are
perfectly coupled for $t\geq\tilde{t}_{x}$ in the boxes $\hat{B}_{y}$ for
$y{{\in x+(\\{0,-1\\}^{d}\setminus\\{0\\})}}$.

For $z,z^{\prime}\in{\mathbb{Z}}^{d}$ we write $z{\prec}z^{\prime}$ if
$\langle z,u\rangle{<}\langle z^{\prime},u\rangle$. Within the box
$\hat{B}_{x}$, we proceed by induction with respect to this partial order to
show that $\zeta^{\mathbf{1}}_{z}(t)=\zeta^{\mathbf{0}}_{z}(t)$ for all $t\geq
p_{z}$, where $(p_{z})_{z\in\hat{B}_{x}}$ are provided by the definition of
$t_{x}$. Assume that this is proved for all
$z^{\prime}{\prec}z\in\hat{B}_{x}$. Then
$\zeta^{\mathbf{1}}_{z}(p_{z})=\zeta^{\mathbf{0}}_{z}(p_{z})=0$, since
$U_{z}(p_{z})>q_{0}$ (recall Eq. 2.3). Moreover, using Eq. 8.2 and the fact
that $U_{0}{\subset}\mathbb{H}_{u}$, we obtain

$z+U_{0}\subset\bigcup_{y\in\\{0,-1\\}^{d}}\hat{B}_{x+y}\cap\\{z^{\prime}\in{\mathbb{Z}}^{d}:z^{\prime}\prec
z\\}.$

Since the r.h.s. above is coupled at all times $t\geq p_{z}$ by induction
hypothesis, the definition of the $\\{U_{0}\\}$-CP (see Eqs. 2.3 and 2.1)
gives that $\zeta^{\mathbf{1}}_{z}(t)=\zeta^{\mathbf{0}}_{z}(t)$ for all
$t\geq p_{z}$, as desired. ∎

Combining Lemma 11.1 and the results of [Greenberg09], we next prove the
following.

######  Proposition 11.2.

Let $q_{0}\in[0,1)$. There exists $c_{0}=c_{0}(U_{0},q_{0})<\infty$ such that
for every $\delta>0$ and $n$ large enough (depending on $\delta$), the mixing
time of the $\\{U_{0}\\}$-CP with parameter $q_{0}$ (in the box $\Lambda$,
with ${\bf 1}$ boundary condition) satisfies

$t_{\rm mix}(\delta)\leq c_{0}n.$ (11.2)

Note that here we do not need $q_{0}$ to be large. However, for small $q_{0}$
the CP in infinite volume has trivial upper invariant measure and the mixing
time in the box should be logarithmic in $n$.

###### Proof.

It is not hard to check that $t_{x}-\tilde{t}_{x}$ is stochastically dominated
by the sum of $|\hat{B}|$ independent exponential random variables of
parameter $1-q_{0}$. On the other hand, the size of $\hat{B}_{x}$ depends only
on the set $U_{0}$. Since the sum of $N$ exponential random variables is
stochastically dominated by a single exponential random variable with suitably
large ($N$-dependent) expectation, we have that $t_{x}-\tilde{t}_{x}$ is
stochastically dominated by an exponential random variable of parameter
depending on $q_{0}$ and $U_{0}$. Since LPP is monotone in the quantities
$t_{x}-\tilde{t}_{x}$, which are clearly independent for different $x$, we get
that $t_{x}$ is smaller than the passage time of a $\mathcal{U}_{0}$-LPP
slowed down by a factor $\theta(q_{0},U_{0})\in[1,\infty)$, which we noted in
Section 2.4 to coincide with the standard $\\{-e_{1},\dots,-e_{d}\\}$-LPP
slowed down by the same factor.

By Lemma 11.1 and attractiveness of CP we have that
$\max_{x\in{\mathbb{Z}}^{d}}t_{x}$ is an upper bound on the coupling time of
the $\\{U_{0}\\}$-CP on $\Lambda$ with boundary condition ${\mathbf{1}}$. The
proof of Proposition 11.2 is then concluded via the next result. ∎

######  Proposition 11.3.

Denote by $(s_{x})_{x\in\mathbb{Z}^{d}}$ the passage times of the standard
$\\{-e_{1},\dots,-e_{d}\\}$-LPP in the set $\Xi$ defined in Eq. 11.1, with
$s_{x}=0$ if $x\not\in\Xi$. Then, there exists $C=C(U_{0})<\infty$ such that
for every $\delta>0$, for $n$ large enough (depending on $\delta$) we have

$\mathbb{P}\left(\max_{x\in{\mathbb{Z}}^{d}}s_{x}\geq nC\right)\leq\delta.$
(11.3)

######  Remark 11.4.

The proposition is, essentially, a byproduct of the main result of
[Greenberg09]. In that paper, the authors upper bound the mixing time of a
discrete-time Markov chain on $d-$dimensional discrete monotone sets. That
dynamics depends on a bias parameter $\lambda$, that is assumed to be
sufficiently large, depending only on the dimension $d$. In the limit
$\lambda\to\infty$, the dynamics reduces to (a discrete-time version of)
standard $d-$dimensional LPP. For the reader’s convenience, we give a
streamlined proof of Proposition 11.3 in the context of (continuous-time LPP)
and along the way we slightly improve the main statement of [Greenberg09]
(which, translated into our language, would give Eq. 11.3 with $nC$ replaced
by $nC\log(1/\delta)$.)

###### Proof of Proposition 11.3.

First of all, using monotonicity of LPP, we can replace the set $\Xi$ by a
cube $\\{1,\dots,\ell\\}^{d}$ that contains it. Using the fact that $\Xi$ has
diameter upper bounded by $n$ times a $U_{0}$-dependent constant, we assume
henceforth that $\Xi$ is a cube with $\ell=O(n)$.

We say that a subset $\sigma\subset\Xi$ is a _monotone set_ if the conditions
that $x\in\sigma$ and $y\preceq x$ (that is, $y\leq x$ componentwise) imply
that $y\in\sigma$. We define a continuous-time Markov chain on the collection
$\Sigma$ of monotone sets; the state of the chain at time $t$ is denoted
$\sigma(t),$ and we let $\sigma(0):=\emptyset$. Each $x\in\Xi$ has an
independent Poisson clock of rate $1$. When the clock at $x$ rings, if
$x\not\in\sigma(t-)$ and if $\sigma(t-)\cup\\{x\\}\in\Sigma$, then we let
$\sigma(t)=\sigma(t-)\cup\\{x\\}.$ Otherwise, nothing happens. It is easy to
check that this dynamics is equivalent to standard
$\\{-e_{1},\dots,-e_{d}\\}$-LPP in the sense that the process
$(\sigma(t))_{t\geq 0}$ has the same law as the process $(\\{x\in\Xi:s_{x}\leq
t\\})_{t\geq 0}.$ In particular, Eq. 11.3 is equivalent to proving that

$\mathbb{P}(\sigma(nC)=\Xi)>1-\delta.$ (11.4)

The monotone set dynamics is reversible with respect to the trivial stationary
measure concentrated on the absorbing state $\sigma=\Xi$, because
$\sigma(t)\supset\sigma(s)$ for $t>s$. For this reason, (11.4) is equivalent
to the fact that the mixing time of the monotone set dynamics satisfies
$t_{\rm mix}(\delta)\leq Cn$, for $n$ large enough. The idea of [Greenberg09]
is to use path coupling with an exponential metric. That is, fix $\gamma>0$
and let $\underline{1}=(1,\dots,1)\in{\mathbb{Z}}^{d}$. Given
$\sigma,\sigma^{\prime}\in\Sigma$ that differ by a single vertex, say,
$\sigma=\sigma^{\prime}\cup\\{x\\}$, define
$d_{\gamma}(\sigma,\sigma^{\prime})=e^{-\gamma\langle
x,\underline{1}\rangle}$, and extend $d_{\gamma}$ to be a distance on the
whole state space $\Sigma$. The path coupling method (see [Greenberg09] and
[Levin09]*Ch. 14 in the discrete time setting, but the method is analogous in
continuous time) consists in proving that there exists some $\alpha>0$ such
that for each pair $(\sigma,\sigma^{\prime})$ differing by a single vertex
there exists a coupling of the processes $(\sigma(t),\sigma^{\prime}(t))$ with
initial conditions $\sigma,\sigma^{\prime}$ such that

$\left.\frac{d}{dt}\mathbb{E}\left[d_{\gamma}(\sigma(t),\sigma^{\prime}(t))\right]\right|_{t=0}\leq-\alpha
d_{\gamma}(\sigma,\sigma^{\prime}).$ (11.5)

If this is the case, then

$t_{\rm mix}(\delta)\leq\frac{1}{\alpha}\log({\rm
diam}_{\gamma}(\Sigma)/\delta),$ (11.6)

with ${\rm diam}_{\gamma}(\Sigma)$ the diameter of $\Sigma$ with respect to
the metric $d_{\gamma}$. In the case of the exponential metric above,
$\log{\rm diam}_{\gamma}(\Sigma)=O(\ell)$ and, recalling that $\ell=O(n),$ Eq.
11.6 implies that $t_{\rm mix}(\delta)\leq Cn$, for $n$ large enough, as
desired. The computation of the time derivative in Eq. 11.5 is very similar to
the computation of the discrete-time derivative in [Greenberg09]*Sec. 4, so we
do not repeat it: one finds that there is exactly one update (the one at $x$)
that decreases the distance by $d_{\gamma}(\sigma,\sigma^{\prime})$, and at
most $d$ updates (at vertices neighbouring $x$) that increase the distance by
$e^{-\gamma}d_{\gamma}(\sigma,\sigma^{\prime})$. Altogether,

$\left.\frac{d}{dt}\mathbb{E}\left[d_{\gamma}\left(\sigma(t),\sigma^{\prime}(t)\right)\right]\right|_{t=0}\leq-\left(1-de^{-\gamma}\right)d_{\gamma}(\sigma,\sigma^{\prime}),$
(11.7)

which gives Eq. 11.5 with $\alpha>0$ for $\gamma$ large enough. This concludes
the proof. ∎

##  12 Assembling Theorem 3.1

###### Proof of the lower bound in Eq. 3.1.

Let

$\Lambda_{\ell}=\left\\{\lfloor n/2\rfloor-\ell,\dots,\lfloor
n/2\rfloor+\ell\right\\}^{d}.$

One can choose $\ell$ large enough (depending on $\delta$ and $q$, but not on
$n$) so that the probability, under the stationary measure for the process in
the box $\Lambda=\\{1,\dots,n\\}^{d}$ with boundary condition ${\mathbf{1}}$,
that $\Lambda_{\ell}$ is in state ${\mathbf{0}}$ is smaller than $\delta/2$.
For the $\mathcal{U}-$KCM, this is obvious, since the stationary measure is a
Bernoulli product measure with parameter $q>0$. For the $\mathcal{U}-$CP, this
follows from the fact that the stationary measure is stochastically larger
than the restriction to $\Lambda$ of the upper invariant measure $\bar{\nu}$
on ${\mathbb{Z}}^{d}$ (recall Section 2.3). The latter is ergodic (see
[Liggett05]*Theorem III.2.3.(f)) and non-trivial under the assumption that
$q{>{q_{\rm c}^{\mathrm{\scriptstyle{CP}}}}}$, which is the case, since we are
assuming that $q$ is sufficiently close to $1$ and ${q_{\rm
c}^{\mathrm{\scriptstyle{CP}}}}<1$ for $\mathcal{U}$ which is not trivial
subcritical (recall Section 2.3).

On the other hand, starting the dynamics (either KCM or CP) from the
${\mathbf{0}}$ configuration in $\Lambda$ with ${\mathbf{1}}$ boundary
condition, with high probability it takes a time at least $cn$ (with $c$
independent of $\delta$) before the state in $\Lambda_{\ell}$ changes. This
follows from the definition of the dynamics, the fact that the box
$\Lambda_{\ell}$ is at distance at least $n/4$ from the boundary of $\Lambda$
and from standard estimates on first passage percolation (see e.g.
[Liggett99]*Section I.1). ∎

###### Proof of the upper bound in Eq. 3.1.

We need to show that, for every $\delta>0$ and $n$ large enough (depending on
$\delta$), the $\mathcal{U}$-KCM in $\Lambda$ with parameter $q$ and boundary
condition ${\bf 1}$, started from the initial state ${\bf 1}$ has coupled at
time $cn$ with the one started from an arbitrary configuration
$\xi^{\prime}\in\Omega_{\Lambda}$, with probability at least $1-\delta$. The
proof for the $\mathcal{U}$-CP is identical and therefore omitted.

From Proposition 11.2 we know that (up to a total variation error $\delta/2$)
for any $t\geq T_{0}:=c_{0}n$ the $\\{U_{0}\\}$-CP with parameter $q_{0}\leq
q$ large enough, in $\Lambda$ with boundary condition ${\mathbf{1}}$ and any
initial condition, has coupled. Namely, denoting these processes by
$\zeta^{\xi^{\prime\prime},\Lambda}$ for initial conditions
$\xi^{\prime\prime}\in\Omega_{\Lambda}$, we get

${\mathbb{P}}\left(\forall t\geq
T_{0},\zeta^{{\mathbf{0}},\Lambda}(t)=\zeta^{{\mathbf{1}},\Lambda}(t)\right)\geq
1-\delta/2.$

By attractiveness we have that at any time $\zeta^{{\mathbf{1}},\Lambda}$
dominates the restriction to $\Lambda$ of the infinite volume $\\{U_{0}\\}$-CP
$\zeta^{\mathbf{1}}$ with initial condition ${\mathbf{1}}$ and parameter
$q_{0}$. Thus,

${\mathbb{P}}\left(\forall t\geq T_{0},\forall
x\in\Lambda,\zeta_{x}^{\mathbf{1}}{(t)}\leq\zeta_{x}^{{\mathbf{0}},\Lambda}{(t)}\right)\geq
1-\delta/2.$

For all $t\geq T_{0}$, let $O_{t}^{\mathbf{1}}$ denote the set of orange
healthy sites for $\zeta^{\mathbf{1}}$ and let $O_{t}^{{\mathbf{0}},\Lambda}$
denote the one of $\zeta^{{\mathbf{0}},\Lambda}$, where both are initialised
at time $T_{0}$ to be equal to the set of all healthy sites and then defined
via Eq. 7.1. It is easily seen that the set of orange sites is non-increasing
in the trajectory, so

${\mathbb{P}}\left(\forall t\geq T_{0},O^{\mathbf{1}}_{t}\cap\Lambda\supset
O_{t}^{{\mathbf{0}},\Lambda}\right)\geq 1-\delta/2.$

Moreover, applying Lemma 7.1 (and Claim 7.2 up to time $T_{0}$), a union bound
and translation invariance, we have that for $t\geq T_{0}$

$\mathbb{P}\left(\eta^{\bf
1}(t)\neq\eta^{\xi^{\prime}}(t)\right)\leq{\mathbb{P}}\left(O^{{\mathbf{0}},\Lambda}_{t}\neq\varnothing\right)\leq\delta/2+|\Lambda|\cdot{\mathbb{P}}\left(0\in
O_{t}^{\mathbf{1}}\right).$ (12.1)

The proof of Theorem 3.1 is therefore concluded, using monotonicity once again
together with Eq. 10.5, taking e.g. $t=T_{0}+\sqrt{n}$, since none of the
other quantities depend on $n$. Indeed, in Section 10, Eq. 10.5 was valid for
the $\\{U_{0}\\}$-CP starting from an initial configuration renormalising to
$\xi\sim\mu_{1-\varepsilon_{3}}$ with $\varepsilon_{3}$ small enough, while
here we simply have $\varepsilon_{3}=0$. ∎

## Acknowledgements

This work was supported by the Austrian Science Fund (FWF): P35428-N. We thank
Paul Chleboun, Laure Marêché, Rob Morris, Réka Szabó and Cristina Toninelli
for enlightening discussions.

## References