Consider some deterministic, monotonic, eroding binary cellular automata on some lattice $\mathbb{Z}^d$, and consider the set of initial states $I(L)$ in which all of the vertices are $0$ except for finitely many, and these finitely many $1$'s are within some hypercube of side length $L$ centered at the origin. I am interested on bounds depending on $L$ for the time it takes for this eroding cellular automata to evolve a state $J\in I(L)$ into the all $0$ state. Call this time $T(J)$.


I am interested in whether one could find an example where $T$ asymptotically dominates $L$. That is, can one find a monotonic, eroding binary cellular automata for which


$$\lim\_{L \to \infty} \sup\_{J \in I(L)} \frac{T(J)}{L} = \infty ? $$


My intuition says that the answer is no, as such a model would likely provide a heuristic counterexample to Toom's proof of stability of monotonic eroders under small amounts of probabilistic noise, but I would like to understand why monotonicity and erosion are sufficient to make the limit above non-infinite.




---


I am new to the field of cellular automata and still learning the language, but I hope my question is well-posed. Please let me know if any parts are unclear or if I should clarify definitions.


By monotonic and eroding, I mean the definitions from chapter one of [Lise Ponselet's thesis](https://arxiv.org/pdf/1312.3612.pdf).
Colloquially, I believe a monotonic update rule means that if I have some configuration $J$ and consider a configuration $K$ that looks like $J$ except some $0$'s are replaced with $1$'s, the update rule will leave $K$ with at least as many $1$'s as $J$ after a given update. Colloquially, I believe an eroding cellular automata takes a finite number of updates to remove a finite number of $1$'s from an otherwise all $0$ configuration.



Binary cellular automata: How slowly can an eroder remove $1$'s?
The answer is no.


According to [1] this is proved in [2] and in some paper of Toom from 1979 that does not seem to be listed in their bibliography. I cannot access [2] or any paper of Toom. I am a little unsure of myself here as I never had to write this stuff and don't have access to any of the classical references, but I think the following argument should be standard or wrong.


On page 12 of Ponselet's thesis it is stated that Toom proves that the precise criterion for erosion is the following erosion criterion.



> 
> Definition (Erosion Criterion). A monotonic binary CA is said to satisfy the Erosion Criterion if $\bigcap\_{j=1}^J \mathrm{conv}(Z\_j) = \emptyset$ where $Z\_j$ are the *zero sets* meaning minimal subsets of the lattice such that if you have zeroes in those positions then you have zeroes at the origin in the image of the CA.
> 
> 
> 


Here $\mathrm{conv}$ denotes the convex hull in $\mathbb{R}^d$. Note that the family of zero sets fully characterizes a monotone CA, and the zero sets are contained in its finite neighborhood as a CA.



> 
> Theorem [Toom]. The Erosion Criterion is the erosion criterion for monotone CA over the binary alphabet.
> 
> 
> 


Now if you satisfy the erosion criterion, then there is a simple geometric way to see that erosion is linear. Take an arbitrary cell $v$, and consider the area $(v+\mathrm{conv}(Z\_j)) \cap \mathbb{Z}^d$ on the previous time step. If all of those cells contain zero, then we have $0$ in $v$ at the present step. Consider then $v+2\mathrm{conv}(Z\_j) \cap \mathbb{Z}^d$; if all those cells contain zero then two steps later you have $0$ at $v$. Namely if $c|\_{v+2\mathrm{conv}(Z\_j) \cap \mathbb{Z}^d} \equiv 0$ then because
$v+Z\_j+Z\_j \subset v + \mathrm{conv}(Z\_j) + \mathrm{conv}(Z\_j) \cap \mathbb{Z}^d = v + 2\mathrm{conv}(Z\_j) \cap \mathbb{Z}^d$ we have $\phi(c)|\_{v + Z\_j} \equiv 0$ where $\phi$ is our CA, and then of course $\phi^2(c)\_v = 0$.


Continuing this logic, we see that if $t$ steps before we had only zeroes in $v + t\mathrm{conv}(Z\_j) \cap \mathbb{Z}^d$ then we have 0 at $v$ on the present step. But now if $\bigcap\_{j=1}^J \mathrm{conv}(Z\_j) = \emptyset$, then in linearly many steps $t = O(n)$, the $n^d$-hypercube does not even intersect one of the sets $v+t\mathrm{conv}(Z\_j)$ (no matter where this hypercube is located), since the distances between the blown-up convex hulls are blowing up proportionally to $t$. So we're done.


[1] *de Meneyes, Moisés Lima; Toom, André*, A nonlinear eroder in presence of one-sided noise, Braz. J. Probab. Stat. 20, No. 1, 1-12 (2006). [ZBL1272.60049](https://zbmath.org/?q=an:1272.60049).


[2] *Gal’perin, G. A.*, One-dimensional local monotone operators with memory, Sov. Math., Dokl. 17, 688-692 (1976); translation from Dokl. Akad. Nauk SSSR 228, 277-280 (1976). [ZBL0366.94059](https://zbmath.org/?q=an:0366.94059).


