Stable Multi-Level Monotonic Eroders

Cellular automata, CA for short, are a class of dynamical systems that are discrete in both space and time. A CA consists of a finite or infinite grid of identical finite state machines, usually called cells, that interact with only finitely many neighbors. At each time step, each machine synchronously enters a new state based on the current states of itself and its neighbors. The grid is usually assumed to be homogeneous, that is, each machine has a neighborhood of identical shape and uses the same update function.

In this article, we consider monotonic cellular automata with random errors. In a monotonic CA, the state set of the finite state machines is totally ordered, and the dynamics of the system respects this order. They are closely related to bootstrap percolation, introduced in [1], in which the state set is {0,1}, a cell cannot change its state from 1 to 0, and the system is initiated from a random configuration. In general, we denote by 0 the bottom element of the state set. The dynamical properties of arbitrary monotonic CA in dimension 1 were studied by Gal’perin [3, 4], who gave a computable characterization of those automata that erase arbitrary finite islands in a sea of 0-states. We introduce randomness into the model by allowing each machine to make an error with some fixed small probability, turning it into a probabilistic cellular automaton. See [6] and references therein for a survey on this topic. In fact, since we allow the errors of different states to be dependent, our model is somewhat more general than probabilistic cellular automata. We prove a version of Gal’perin’s result in this extended setting. More explicitly, we characterize those one-dimensional monotonic cellular automata for which the asymptotic density of 0-states in the trajectory started from the all-0 configuration tends to zero with the error rate. We call a CA that satisfies this condition a stable eroder. As a corollary, we also show that it is decidable whether a given monotonic automaton is a stable eroder.

The proof of our result is split into two sections, one for each direction of the equivalence. One direction of the proof, that our condition only holds for stable eroders, uses combinatorial objects that record the causal relationships between nonzero states in a trajectory of the CA, inspired by the work of Toom [11]. We show that a nonzero state is always accompanied by such an object, as well as a set of errors whose size is comparable to the size of the object. A counting argument then bounds the probability of the nonzero state. For the converse direction, we prove that if a CA does not satisfy our condition, one can find a finite island of nonzero states that persists forever with an arbitrarily high probability. We show how randomly occurring errors will “repair” the borders and internal structure of the island faster than the CA can erode it away.

Let \(\mathbb {Z}^{d}\) denote the d-dimensional integer lattice. We fix a finite state set S, endow it with the discrete topology, and endow \(S^{\mathbb {Z}^{d}}\) with the product topology. The shift by \(\textbf {n} \in \mathbb {Z}^{d}\) is the function \(\sigma ^{\textbf {n}} : S^{\mathbb {Z}} \to S^{\mathbb {Z}}\) defined by σⁿ(x)_v = x_v+n for all \(x \in S^{\mathbb {Z}^{d}}\) and \(\textbf {v} \in \mathbb {Z}^{d}\). If d = 1, we denote σ = σ¹. A cellular automaton is a function from \(S^{\mathbb {Z}^{d}}\) to itself that is continuous and commutes with each σⁿ. By the Curtis-Lyndon-Hedlund Theorem, it has a finite neighborhood: the value of f(x)₀ depends only on finitely many coordinates of x. A radius of f is an integer r ≥ 0 such that f(x)₀ depends only on \(x|_{[-r, r]^{d}}\). A radius gives rise to a local rule: a function \(F : S^{[-r, r]^{d}} \to S\) such that \(f(x)_{\textbf 0} = F(x|_{[-r, r]^{d}})\). Indexing an element \(\eta \in S^{\mathbb {Z}^{d} \times \mathbb {N}}\) by \((\textbf {n}, t) \in \mathbb {Z}^{d} \times \mathbb {N}\) is denoted \(\eta _{\textbf {n}}^{t}\), and \(\eta ^{t} \in S^{\mathbb {Z}^{d}}\) is the t’th d-dimensional slice of η.

Denote by \({\mathscr{M}}(S^{\mathbb {Z}^{d}})\) the set of Borel probability measures on \(S^{\mathbb {Z}^{d}}\), and similarly for \(S^{\mathbb {Z}^{d} \times \mathbb {N}}\). Consider a mapping R from \({\mathscr{M}}(S^{\mathbb {Z}^{d}})\) to \({\mathscr{M}}({{S}^{\mathbb {Z}^{d} \times \mathbb {N}}})\). For a measure μ, we consider R(μ) as a random variable with values in \(S^{\mathbb {Z}^{d} \times \mathbb {N}}\). We say that R is a stochastic symbolic process, if Such a mapping is determined by its images on point measures. If μ is a point measure concentrated on \(x \in S^{\mathbb {Z}^{d}}\), we denote R(μ) = R(x), and call it a random trajectory with initial condition x. We say that R is an 𝜖-perturbation of f, if for any \(x \in S^{\mathbb {Z}^{d}}\) and any finite set \(C \subset \mathbb {Z}^{d} \times \mathbb {N}\), the probability that \(R(x)_{\textbf {v}}^{t+1} \neq f(R(x)^{t})_{\textbf {v}}\) holds for all (v, t) ∈ C is at most 𝜖^|C|. In this context, the set of coordinates \((\textbf {v}, t) \in \mathbb {Z}^{d} \times \mathbb {N}\) with \(R(x)_{\textbf {v}}^{t+1} \neq f(R(x)^{t})_{\textbf {v}}\) is usually called the error set of R(x).

For now on, consider only linearly ordered state sets: S = {0,1,…,m} for some m ≥ 1. For \(x, y \in S^{\mathbb {Z}^{d}}\), we denote x ≥ y if x_v ≥ y_v holds for all \(\textbf {v} \in \mathbb {Z}^{d}\). A cellular automaton \(f : S^{\mathbb {Z}^{d}} \to S^{\mathbb {Z}^{d}}\) is monotonic if x ≥ y implies f(x) ≥ f(y) for all \(x, y \in S^{\mathbb {Z}^{d}}\). For a ∈ S, the all-a configuration is denoted by \(\hat {0}\). The state a is called quiescent for f, if \(f(\hat {0}) = \hat {0}\). We will always assume that the extremal states 0 and m are quiescent. A configuration \(x \in S^{\mathbb {Z}^{d}}\) is an a-island, if \(\hat {0} \leq x\) and x_v = a for all but finitely many \(\textbf {v} \in \mathbb {Z}^{d}\). A 0-island will simply be called an island.

The notion of an eroder has appeared many times in the literature with different names, including nilpotency on finite configurations. It simply means that a CA removes all islands in a finite (but not necessarily uniform) number of steps.

With the terminology of [11], this means that the all-0 trajectory is attractive. Our aim is to extend this notion to cellular automata with random perturbations. Of course, a nontrivial 𝜖-perturbation of a deterministic CA will almost surely never reach the uniform zero configuration \(\bar {0}\). Thus we present the following definition, which is equivalent to the all-0 trajectory being stable, again using the terminology of [11].

The following result justifies our terminology.

It is known that for automata with more than two states, the converse does not hold: there exist automata that are eroders but not stable eroders. One such example is given in [10], and we present a slight modification of it here for completeness.

Note that if U is a, b-forcing at level k and V is a, b-forcing at level ℓ, then U + V is a, b-forcing at level k + ℓ, and thus some subset W ⊂ U + V satisfies \(W \in \mathcal {V}^{k + \ell }_{a,b}(f)\). Forcing sets are analogous to zero sets as usually defined for binary cellular automata, and in that context, they can be used to characterize eroders.

It is not immediately clear whether one can algorithimically decide if a cellular automaton is a, b-shrinking for given states a, b, since Definition 3.6 refers to an unbounded variable k, but there may exist a bound K, computable from the radius of f and the number of states, such that f is a, b-shrinking precisely when \(\tau ^{k}_{a,b}(f) = \emptyset \) for some k ≤ K. We show by an example that it is not sufficient to consider the case k = 1. However, the condition turns out to be decidable for one-dimensional cellular automata. This follows from the results of [3, 4], and we repeat it explicitly in Lemma 4.4. The decidability of the condition in the multi-dimensional case is left open.

It is known that this characterization of eroders generalizes to larger alphabets in the one-dimensional case, but not in the multi-dimensional case. This was proved in [3], and we repeat it in Theorem 4.6. In this article, we will show that the characterization of stable eroders likewise generalizes to larger alphabets in the one-dimensional case (although the generalization is different). The multi-dimensional case is left open.

The next three sections are devoted to the proof of this result.

In this section, we fix a one-dimensional monotonic automaton \(f : S^{\mathbb {Z}} \to S^{\mathbb {Z}}\) with radius r ≥ 0 and consider the evolution of certain configurations under f.

See Fig. 1 for a visualization of the definition. We know from the work of Gal’perin [3] that these quantities, which we call the Gal’perin rates of f, always exist and are rational numbers. Furthermore, they can be effectively computed from the local rule of f [4, 9]. The following result is also convenient.

The characterization of eroders in one dimension is the following.

This condition is not equivalent to f being 0,a-shrinking for all quiescent a ∈ S ∖{0}. More explicitly, if f is 0,m-shrinking where m ∈ S is the maximal state, then it is an eroder, but the converse does not hold in general. In the one-dimensional case, see Example 4.8. Also, the condition implies that the time required for f to erode an island is at most linear in the diameter of the island, and in two dimensions examples of slower eroders are known, even in the case that the automaton is decreasing, that is, f(x) ≤ x holds for all \(x \in S^{\mathbb {Z}^{2}}\) [8].

We will now reformulate our main result, Theorem 3.10, in terms of Gal’perin rates.

We list here some generally useful lemmas.

Of course, there also exists a < d ≤ b such that R_{a, d} = L_{a, b} by symmetry.

In this section, we prove the first part of Theorem 4.7: automata that satisfy the stability condition are stable eroders. The proof follows the ideas presented in [11]. The high level idea is that we take an 𝜖-perturbation of f, and consider a single coordinate (0,T) in a random trajectory starting fom the uniform zero configuration. Assuming the coordinate has a nonzero state, we construct a geometric object that records the ‘reason’ for this event, that is, traces it back to some finite subset of coordinates where errors have occurred. We prove that the size of this subset grows linearly with the size of the object, and there is an exponential number of objects of a given size. A simple calculation then shows that the probability of (0,T) having a nonzero state approaches 0 with 𝜖. The main difference to [11] is that our geometric objects are polygons instead of trees.

For the remainder of this section, fix a monotonic cellular automaton f on \(S^{\mathbb {Z}}\) that satisfies the stability condition for the quiescent states 0 = a₁ < ⋯ < a_k = m. For convenience, we denote \(L_{n} = L_{a_{n}, a_{n+1}}\), \(R_{n} = R_{a_{n+1}, a_{n}}\), S_n = {a ∈ S|a_n < a ≤ a_n+ 1} and \(S_{n}^{+} = \cup _{\ell \geq n} S_{\ell }\) for n ∈{1,…,k − 1}. By Lemma 4.4, there exist k_n > 0 and forcing sets \(U_{n}, V_{n} \in \mathcal {V}^{k_{n}}_{a_{n}, a_{n+1}}(f)\) such that U_n, V_n ⊂{−k_nr,…,k_nr} and \(-k_{n} L_{n} \leq u_{n} = {\max \limits } U_{n} < {\min \limits } V_{n} = v_{n} \leq -k_{n} R_{n}\). Recall the number K from Lemma 4.2. We may assume that hold for all n; this can be guaranteed by taking a large enough power of f that is divisible by each k_n. Let R be an 𝜖-perturbation of f for some small 𝜖 > 0, and consider the random trajectory \(\eta = R(\hat {0})\). We will prove that \({\text {Pr}[\eta _{0}^{T}} > 0] \stackrel {\epsilon \to 0}{\longrightarrow } 0\) uniformly in T.

We define some more auxiliary concepts before proceeding with the proof. Define four sets of integer vectors:

Finally, define the random error set by \(E = \{ (i, t) \in \mathbb {Z} \times \mathbb {N} | \eta ^{t+1}_{i} \neq f(\eta ^{t})_{i} \}\).

Let T ≥ 1 be an arbitrary positive integer. We will now construct a system of geometric shapes on the vertex set \(W = \{ (i, t) \in \mathbb {Z} \times \mathbb {N} | t \leq T, |i| \leq r (T - t) \}\) parametrized by the states S_n ⊂ S and a set C ⊂ W such that \({\eta ^{t}_{i}} \in S_{n}\) for all (i, t) ∈ C. For a set \(P \subset \mathbb {R}^{2}\), denote its border by ∂P. By a polygon we mean a closed and bounded subset of \(\mathbb {R}^{2}\) that is a finite union of triangles and line segments. In particular, a polygon may not be equal to the closure of its interior.

Item (d) in Definition 5.1 is a technical constraint that is easy to enforce during the construction and makes the proof of Lemma 5.2 simpler. If the condition does not hold, we say that the pair (i, t),(j, t) violates condition (d) in 〈P, X〉. Similarly, the constraint on maximizing \(\tilde n\) in item (e) simplifies the proofs of Lemma 5.4 and Lemma 5.6 without affecting the construction in any other way.

See Fig. 2 for a visualization of a space-time polygon. The shaded area is P, the black dots are the vertices w_i in the list X, and each arrow is a line segment \(\overline {w_{i} w_{i+1}}\). An edge is in \({{\Delta }^{C}_{n}}\) if it points east, in \({{\Delta }^{B}_{n}}\) if it points west, in \({{\Delta }^{L}_{n}}\) if southwest and in \({{\Delta }^{R}_{n}}\) if northwest. Some edges in the figure are labeled with the set they belong to. Note that horizontal line segments may be traversed twice, as is the case near the rightmost vertex. The darker shaded areas at the bottom are parts of a space-time polygon of level \(\tilde n\) for some \(\tilde n > n\), and the dashed lines denote the support point relation. The vertices in X with dashed lines have type 1. Vertices enclosed in boxes are produced by errors, and they have type 2. Other vertices have type 3; one of the triangles is depicted in the figure.

Intuitively, a space-time polygon on level n records the ‘reason’ for the vertices in the set C being in the state n. It resembles the notion of truss in [11]. The idea of the proof is that a coordinate \((i, t) \in \mathbb {Z}^{2}\) with \({\eta ^{t}_{i}} \neq 0\) gives rise to a finite collection of space-time polygons, a constant fraction of whose vertices have type 2, that is, are caused by errors. The number of such collections with N vertices in total grows exponentially with N, and by choosing the error rate 𝜖 small enough, we can bound the probability that any collection of polygons enables \({\eta ^{t}_{i}} \neq 0\). We begin by showing that in a single polygon 〈P, X〉, the number of vertices of type 1 or 2 grows linearly with the size of the set X.

We will now construct a set Q(C) of disjoint space-time polygons of level n whose union contains C, the set of initial vertices. We construct the polygons iteratively, maintaining a set Q_p(C) of ‘incomplete polygons’ that are allowed to violate condition (d) and the second part of condition (e) in Definition 5.1, meaning that the vertices at time t may not have a type. We start with Q₀(C) being the collection of single-vertex polygons 〈{w},〈w〉〉 for w ∈ C.

Assume then that we have constructed the set Q_p(C) for some p ≥ 0. There are three possible conditions that prevent us from choosing Q(C) = Q_p(C), which we refer to as violations: If none of these violations hold, then Q_p(C) consists of disjoint space-time polygons of level n. Namely, if w ∈ W is a vertex of some polygon 〈P, X〉∈ Q_p(C), then it has a type in one of them (since violation 1 does not hold), which must be 〈P, X〉 since the polygons are disjoint. Similarly, if v, w ∈ W occur in the list of some polygon 〈P, X〉∈ Q_p(C), then it does not violate condition (d) in some polygon (since violation 2 does not hold), which must be 〈P, X〉. We now show how to handle the violations one by one. The first two cases involve adding new simple polygons to the set Q_p(C), and they are visualized in Fig. 4. In the last case, we show how to merge two intersecting polygons into one, which is a more involved process.

Suppose that violation 1 holds: there exist 〈P, X〉∈ Q_p(C) and w = (i, t) ∈ X that has no type in any polygon of Q_p(C) it belongs to. In particular, (i, t − 1) does not contain an error and \(\eta ^{t-1}_{i + j} \notin S^{+}_{n+1}\) for all − r ≤ j ≤ r. Since U_n and V_n are a_n, a_n+ 1-forcing sets and \({\eta ^{t}_{1}} \in S_{n}\), there exist j_L ∈ U_n and j_R ∈ V_n such that \(\eta ^{t-i}_{i + j_{L}}, \eta ^{t-1}_{i + j_{R}} \in S_{n}\). We also have \((j_{L}, -1) \in {{\Delta }^{R}_{n}}\), \((j_{R}, 1) \in {{\Delta }^{L}_{n}}\) and \((j_{R} - j_{L}, 0) \in {{\Delta }^{C}_{n}}\). Denote X^′ = 〈w,(i + j_L, t − 1),(i + j_R, t − 1)〉, and let \(P' \subset \mathbb {R}^{2}\) be the triangle spanned by these three points. Then 〈P^′, X^′〉 is a (possibly incomplete) three-vertex polygon and w has type 3 in it. We define Q_p+ 1(C) = Q_p(C) ∪{〈P^′, X^′〉}, and w is no longer a witness for violation 1.

Suppose then that violation 2 holds, so that some polygon 〈P, X〉∈ Q_p(C) violates condition (d): some v = (i, t),w = (j, t) ∈ X satisfy 0 < i − j ≤ 2r. Thus we have \(v - w \in {{\Delta }^{C}_{n}}\) and \(w - v \in {{\Delta }^{B}_{n}}\). Let \(P' = \overline {v w}\) and X^′ = 〈v, w〉. Then 〈P^′, X^′〉 is a polygon with two vertices that satisfies every condition of Definition 5.1 except the latter part of (e). In particular, the pair v, w does not violate condition (d) in 〈P^′, X^′〉. We define Q_p+ 1(C) = Q_p(C) ∪{〈P^′, X^′〉}, and then v, w is no longer a witness for violation 2.

Suppose finally that violation 3 holds: there exist 〈P, X〉,〈P^′, X^′〉∈ Q_p(C) such that P ∩ P^′≠∅. We construct a new polygon that contains the union P ∪ P^′. Let \(\tilde P\) be the polygon obtained by filling all holes in P ∪ P^′, and let \(\tilde X = \langle {w_{1}, \ldots , w_{z}}\rangle \) be the list obtained by traversing the border of \(\tilde P\) in the counterclockwise direction and enumerating the elements of X ∪ X^′ in the order they are encountered. Finally, let \(\hat P\) be the simply connected polygon whose border is exactly the union of the line segments \(\overline {w_{i} w_{i+1}}\). We claim that \((\hat P, \tilde X)\) is a valid space-time polygon. It is easy to see that \(w_{i} \in W \cap \partial \hat P\) for all i ∈{1,…,z}, and we now show that the differences of successive elements of the list \(\tilde X\) have the correct form.

To finish the treatment of violation 3, we define \(Q_{p+1}(C) = (Q_{p}(C) \setminus \{\langle P, X \rangle , \langle P', X' \rangle \}) \cup \{ \langle \hat P, \tilde X \rangle \}\).

Now, all three constructions detailed above have the property that the union of all polygons in Q_p+ 1(C) contains the union of all polygons in Q_p(C). In particular, if a vertex or pair of vertices witnesses violation 1 or 2 and we apply the construction to them, they cannot witness the violation again at any later stage. Since there are finitely many sets of polygons on the vertex set W, we eventually reach a set Q_p(C) that avoids violations 1, 2 and 3, and choose Q(C) = Q_p(C). As claimed, it is a set of disjoint space-time polygons of level n whose union contains C. At this point we also remark that in any polygon 〈P, X〉∈ Q(C), any point w ∈ X whose time coordinate is maximal is an element of C. In particular, X ∩ C≠∅. However, note also that C is not necessarily a subset of X, since some of its elements may cease to be vertices as polygons are merged, and become interior points instead.

We will now use the construction of space-time polygons to bound the probability of a given coordinate (0,T) having a nonzero state in the random trajectory η. For this purpose, suppose that \({\eta ^{T}_{0}} > 0\), and let n₀ ∈{1,…,k − 1} be such that \({\eta ^{T}_{0}} \in S_{n_{0}}\). Define the initial set of vertices as \(C_{n_{0}} = \{(0, T)\}\), and construct the set of level-n₀ space-time polygons \(Q(C_{n_{0}})\). Recall that each vertex w = (i, t) that has type 1 in some polygon of \(Q(C_{n_{0}})\) has a support point supp(w) = (j, t − 1) at some level n > n₀ with |i − j|≤ nr. Inductively, for each n₀ < n ≤ k, we define C_n ⊂ W as the set of level-n support points of the polygons in \(\bigcup _{p < n} Q(C_{p})\): This defines an indexed family \((Q(C_{n}))_{n = n_{0}}^{k}\) of sets of space-time polygons, where the polygons of each set Q(C_n) are disjoint.

Fix two numbers n₀ ≤ n < ℓ ≤ k, and let 〈P, X〉∈ Q(C_ℓ) and 〈P^′, X^′〉∈ Q(C_n) be two space-time polygons of different levels. This means that 〈P, X〉 is constructed at a later stage than 〈P^′, X^′〉, and its vertices have higher states. The statements of Lemmas 5.4, 5.5 and 5.6 refer to these polygons. The series of results shows that the two polygons can intersect only if P ⊂ P^′. First, we show that the vertex lists of the polygons are separated horizontally by at least r steps.

Next, we show that every element of each set of support points C_ℓ is close to the border of the polygon that contains it. We will use this fact to show that the total perimeter of all polygons in Q(C_ℓ) is bounded from below by a constant multiple of |C_ℓ|.

We now show that out of all vertices in the system \((Q(C_{n}))_{n=n_{0}}^{k}\), a positive fraction have type 2. Recall that we showed already in Lemma 5.2 that for each individual space-time polygon, a positive fraction of its vertices have type 1 or 2. The idea is that since type 1 vertices have support points, they give rise to new polygons of higher levels, and the polygons of level k, the maximum, have no type 1 vertices.

Next, we estimate the number of different space-time polygon systems rooted at the coordinate (0,T) having a certain perimeter size \(|\mathcal {X}| = H\). Knowing this size, we can characterize the entire system \((Q(C_{n}))_{n = n_{0}}^{k}\) as follows. First, for each polygon 〈P, X〉∈ Q(C_n) in the system, there exists a vertex w = (i, t) ∈ X ∩ C_n (for example, one that maximizes t). If n > n₀, there also exist ℓ < n, another polygon 〈P^′, X^′〉∈ Q(C_ℓ), and a vertex w^′ = (j, t + 1) ∈ X^′ such that w = supp(w^′) and |i − j|≤ kr. We fix one such pair (w, w^′) and call it the base of 〈P, X〉. Now, we construct a list L of vertices as follows. We begin with the polygon 〈P, X〉 containing the topmost vertex w₁ = (0,T), and set L₁ = X = 〈w₁,…,w_|X|〉.

Suppose now that we have constructed a list L_p for some p ≥ 1. If there is a polygon 〈P^′, X^′〉 that has not been processed yet, and its base (w^′, w) has a vertex w ∈ L_p, then we replace w in L_p by the list of vertices 〈w, w^′, w1′,…,wq′,w^′, w〉 where X^′ = 〈w^′, w1′,…,wq′〉, and denote the resulting list by L_p+ 1. If such a polygon does not exist, then the list L_p = L = 〈w₁,…,w_s〉 contains every vertex in \(\mathcal {X}\) at least once and at most 2kr times, so that |L|≤ 2krH. Furthermore, for each index i ∈{1,…,s} we have w_i+ 1 − w_i ∈{−kr,…,kr}×{− 1,0,1}. Since the list L, together with the mapping L →{1,…,k} that sends each vertex (i, t) to the number n such that \({\eta ^{t}_{i}} \in S_{n}\), characterizes \(\mathcal {X}\) completely, the number of different systems \((Q(C_{n}))_{n = n_{0}}^{k}\) with \(|\mathcal {X}| = H\) is at most \({\sum }_{s = H}^{2 k r H} (3 k (2 k r + 1))^{s} \leq (3 k (2 k r + 1))^{(2 k r + 1) H}\).

Now, if we have \({\eta ^{T}_{0}} > 0\), then there exists a system \(\mathcal {P} = (Q(C_{n}))_{n = 1}^{k}\) of time-space polygons of some size H > 0 rooted at (0,T); we denote this event by \(W(\mathcal {P})\). By Lemma 5.8, such a system contains at least βH vertices of type 2, which correspond to a subset of the random error set E. Since η is generated by an 𝜖-perturbation of the cellular automaton f, the probability of \(W(\mathcal {P})\) is at most 𝜖^βH. Thus we have

since we have 𝜖^β < (3k(2kr + 1))^2kr+ 1 for all small enough 𝜖. Then f is a stable eroder, and we have proved the first half of Theorem 4.7.

In this section, we prove the second half of Theorem 4.7: every one-dimensional stable eroder satisfies the stability condition. The idea of the proof is the following. We assume that a CA f does not satisfy the stability condition, and our goal is to show that for all 𝜖 > 0, there exists a finite island that f almost surely never erodes, if each coordinate of the trajectory contains an error with probability of 𝜖 independently of the others. Intuitively, the random errors extend the borders of the island faster than the automaton can erode it. We begin by proving an alternative formulation of the stability condition for one-dimensional automata.

Now, we define a special kind of 𝜖-perturbation of a cellular automaton: one where errors occur independently with probability 𝜖, and always produce a fixed state a ∈ S unless it would cause the state to decrease. Our goal is to prove that if a CA fails to satisfy the condition of Lemma 6.1, then these perturbations form a counterexample to it being a stable eroder.

Note that R(x)^t+ 1 ≥ f(R(x)^t) holds for all \(x \in S^{\mathbb {Z}}\) and \(t \in \mathbb {N}\), since an error can only increase the value of a coordinate.

The following result is a stronger version of Proposition 3.3. It tells us that in order to prove that a CA f is not a stable eroder, it suffices to find a finite island that any given independent perturbation of f never erodes away with arbitrarily high probability. Note that we fix a sequence of coordinates that the evolving island must contain. Also, we cannot require that an island survives forever with probability 1, since f might be an eroder, and there is a small but positive probability that no errors occur in the vicinity of the island before it is eroded away.

For the remainder of this section, we fix a monotonic automaton f that does not satisfy the condition of Lemma 6.1. Then there exists a quiescent state ω ∈ S ∖{0} such that L_{a, ω} ≤ R_{ω, a} for all quiescent a < ω. If there are several such states, let ω be the lowest one. We fix a small 𝜖 > 0, and let R be the independent ω, 𝜖-perturbation of f. Note that a random trajectory R(x) will not contain a state greater than ω if \(x \leq \hat {\omega }\), so we can safely forget the states {ω + 1,…,m} and assume S = {0,…,ω}.

The intuition for an inductive state a is that with a high probability, every large enough island of ω-states surrounded by a-states will spread at an average speed strictly greater than L_{a, ω} − R_{ω, a}. This causes a “cone” of ω-states to appear in the trajectory of the configuration. Our goal in the remainder of this section is to prove Proposition 6.5: every state a < ω is inductive. In particular, the lowest state 0 is inductive, and then we can apply Lemma 6.3 to the island configurations \({}^{\infty } 0 \omega ^{N} . \omega ^{N} 0^{\infty }\) to prove that f is not a stable eroder.

We will actually prove the following one-sided versions of inductivity, which makes the arguments conceptually simpler.

Most of the remainder of this section is devoted to the proof of Proposition 6.5. It suffices to prove (4), since the other case is symmetric. We will use an auxiliary result about biased random walks.

We prove Proposition 6.5 by downward induction on the state a, and the idea of the proof is this. We consider the configuration of (4) for a large \(N \in \mathbb {N}\). By Lemma 4.10, there exists a quiescent state a < b ≤ ω with L_{b, a} = R_{ω, a}. Either b = ω or b is inductive. In the former case, we essentially have a biased random walk on the ω, a-interface of the configuration \({}^{\infty } \omega . \omega ^{N} a^{\infty }\). The random walk is slightly biased to the right of R_{ω, a}, and we can apply Lemma 6.7 to it. In the latter case, we maintain two regions in the random trajectory: an inner region of ω-states, and an outer region of quiescent states at least b. The surface of the outer region behaves like a random walk as in the first case, and the surface of the inner region is constantly “repaired” by randomly appearing patches of ω-states that produce small ω-cones as per the induction hypothesis. Before proceeding with the proof, we formalize the argument about random walks, since it is used in both cases. Recall the number K > 0 from Lemma 4.2.

We proceed with the proof of Proposition 6.5 by (4). Assume first that b = ω, so that L_{ω, a} = R_{ω, a}. When N > K, we can apply Lemma 6.8 to M = N − K, and choose 𝜃_a = q = 𝜖^K+ 1/2, δ_a = d and Q_a = 1 to obtain (4).

Suppose now that a < b < ω, so that b is inductive by the induction hypothesis. Without loss of generality, we assume that R_{ω, a} > 0. If this is not the case, we compose f with a large right shift, which does not change its eroding properties. Define \(x = {}^{\infty } \omega . \omega ^{N} a^{\infty }\) and 𝜃_a = 𝜖^K+ 1/3. We will determine the values of δ and Q later.

Our goal in this proof is to maintain an inner region of ω-states and a slightly wider outer region of states that are at least b. The above definitions formalize this goal. A trajectory is ω-good if we are able to maintain the inner region indefinitely, and b-good if we maintain the outer region indefinitely. As in the proof of the case b = ω, maintaining the outer region indefinitely is relatively simple.

We now turn to the problem of maintaining the inner region. For convenience, we make the following observation about the state b: in a trajectory that starts from a configuration above \(\hat {b}\) and contains a long sequence of ω-states, with a high probability one finds a large rectangle of ω-states. This is simply because one expects to find an infinite cone of ω-states by the inductive hypothesis of Proposition 6.5, inside which the rectangle can be picked. See Fig. 8 for a visualization. Note that we have a lot of freedom in choosing the numbers α and β. In particular, we can choose α as large as we want, and β as small as we want. Recall the definition D_b = (L_{b, ω} + R_{ω, b})/2.

The constant α in the Observation should be chosen so that any coordinate of y to the right of Cα has no influence on the evolution of the ω-rectangle. Such a choice is possible due to the finite radius of f. The rectangle is nonempty for large enough C, since we assumed R_{a, ω} > 0. We will now dispose of the requirement of ω-states in Observation 6.11 by considering a smaller ω-rectangle.

In the case that the outer region can be maintained indefinitely, in the sense that the trajetory is b-good, the evolution of the inner region can be seen as a two-dimensional generalized bootstrap percolation process. Initially, all cells (i,0) with i ≤ N are active. Lemma 6.12 implies the following for all large enough C. If i + C(α + rβ) ≤ t(R_{ω, a} + 2𝜃_a), so that all cells between (i, t) and (i + C(α + rβ),t) are within the outer region, then with a combined probability of at least \(1 - \lambda ^{C^{Q_{b}/3}}\), the cell (i + j, t + s) is active for each (j, s) ∈ [CD_b, CD_b + (R_{ω, a} + 𝜃_a)Cβ] × [C, C + Cβ]. These probabilities are independent for those choices of (i, t) that are far enough from each other, depending on the respective choices of C, and all of them are positively correlated. In this way, we obtain an initial distribution \(A_{0} \subset \mathbb {Z} \times \mathbb {N}\) of active cells in a two-dimensional random configuration in the form of a half-infinite line at time 0 and a random collection of rectangles. The set A_k+ 1 contains all cells of A_k, and each cell (i, t) such that (i + j, t − 1) ∈ A_k for each − r ≤ j ≤ r. As a limit of this percolation process, we obtain a set \(A_{\infty } = \bigcup _{k = 0}^{\infty } A_{k}\) of active cells, with the property that \(R(x)^{t}_{i} = \omega \) for all \((i, t) \in A_{\infty }\). Thus, the conditional probability of R(x) being ω-good given that it is b-good is at least the probability of \((i, t) \in A_{\infty }\) for all t ≥ 0 and i ≤ t(R_{ω, a} + 𝜃_a).

The following lemma establishes a lower bound for the probability of maintaining the inner region indefinitely, expressed as a property of the set \(A_{\infty }\). The idea of the proof is to show that with high probability the rectangles in A₀, together with the cells activated by the initial half-line, cover the entire discrete line of coordinates (i, t) with i ≈ t(R_{ω, a} + 𝜃_a).

Together with the union bound, Lemma 6.10 and Lemma 6.13 imply that the probability of R(x) being ω-good and b-good is at least \(1 - d^{N - K} - \xi ^{N^{Q_{b}/3}}\) for large enough N. We now choose ξ < δ_a < 1 arbitrarily, and set Q_a = Q_b/3. With these choices (4) holds, which finishes the proof of Proposition 6.5.

We have presented a characterization of those one-dimensional monotonic cellular automata that erode finite islands in the presence of sufficiently low random noise. The characterization was given in terms of forcing sets (Definition 3.9 and Theorem 3.10), and alternatively in terms of Gal’perin rates (Theorem 4.7). Since the Gal’perin rates of a one-dimensional monotonic CA can be computed from the local rule [4, 9], we further obtain the following.

In the context of probabilistic cellular automata, another interesting property is ergodicity, meaning the phenomenon where the system’s initial state eventually becomes irrelevant. The ergodicity of random perturbations of deterministic cellular automata has recently been studied in [7]. The authors consider several classes of noisy CA, including nilpotent, permutive and linear, but not monotonic CA.

Consider a one-dimensional monotonic CA f on S = {0,…,m}, suppose that the states 0 and m are quiescent, and let R be an 𝜖-perturbation of f. We present some necessary or sufficient conditions for the ergodicity of R. Suppose first that R only introduces increasing errors (that is, R(x)^t+ 1 ≥ f(R(x)^t) holds for all \(t \in \mathbb {N}\)). Then we have \(\lim _{t \to \infty } R(\hat {m})^{t} = \hat {m}\). If f a stable eroder, then \(\lim _{t \to \infty } R(\hat {0})^{t} \neq \hat {m}\) for small enough 𝜖, so R is not ergodic.

Suppose then that f is not a stable eroder. Lemma 6.1 gives us a quiescent state ω > 0 with L_{a, ω} ≤ R_{ω, a} for all a < ω. We again choose ω to be minimal. In this case, if R is the independent ω, 𝜖-perturbation of f, the results of Section 6 imply that \(\lim _{t \to \infty } \text {Pr} [\forall i \in C : R(\hat {0})^{t}_{i} \geq \omega ] = 1\) for any finite set \(C \subset \mathbb {Z}\). Since f is monotonic, we can replace \(\hat {0}\) by an arbitrary measure and the result still holds. If ω = m, this implies that R is ergodic. However, if ω < m, then R is not ergodic, since \(R(\hat {0})^{t}\) converges to the point measure on \(\hat {\omega }\). Furthermore, it can be the case that even the independent maximizing m, 𝜖-perturbation of f is not ergodic for any 𝜖. We show this by an example.

Finally, consider the two-dimensional cellular automaton f with state set {0,1} and neighborhood N = {(0,0),(1,0),(0,1)}, where the local rule always chooses the majority state in the three cells of N. This automaton was first studied by Toom. It is monotonic, and we can apply Proposition 3.8 to show that it is a stable eroder. In fact, since f is symmetric with respect to switching the states 0 and 1, it is also a stable eroder toward 1, meaning that if a small perturbation of f is initialized on the all-1 configuration, the probability of any single cell to contain 0 is low. With our results, we can show that in the one-dimensional case, such an automaton does not exist.

On the other hand, there does exist a one-dimensional monotonic CA that is an eroder in both directions. The classical non-monotonic example of this phenomenon is the Gács-Kurdyumov-Levin automaton [2], which has two states. A four-state radius-1 example is given in [12, Section 8.2]. It is monotonic, but the alphabet is only partially ordered ({0,1}² with component-wise comparisons). We present a monotonic three-state CA with a linearly ordered alphabet.

The results proved in this article concern one-dimensional cellular automata on linearly ordered alphabets of size at least 3: we prove that such a CA is a stable eroder if and only if it satisfies the stability condition. As stated in Section 3, we do not know if our results generalize to the multi-dimensional case, nor whether the class of multi-dimensional stable eroders is decidable. For the binary alphabet, the answer to both questions is positive due to Proposition 3.8.

Note that we have formulated the stability condition in all dimensions (see Definition 3.9), so the direct generalization of Theorem 3.10 from \(\mathbb {Z}\) to \(\mathbb {Z}^{d}\) for all d ≥ 1 is well-defined. Of course, it is also possible that stable eroders are characterized by a simple geometric condition, but our version is not the correct one.

The class of multi-dimensional monotonic eroders with more than two states is likewise mysterious. To our knowledge, its decidability status is unknown, and no simple characterization has been conjectured. Another property related to eroders is the speed of erosion. We discussed this subject briefly in Section 4. For a fixed one-dimensional eroder f, every finite island x satisfies \(f^{n}(x) = \hat {0}\) for some n ≥ 0 that is linear in the diameter of x, and the rate is computable from f. In the multi-dimensional context this is no longer true [8], and it is unknown whether the time of erosion can exhibit busy beaver-type behavior.