Probabilistic 2D cellular automata with memory lifetime increasing like $e^{L^2}$

Question

Consider 2-state probabilistic cellular automata on an $L\times L$ torus square lattice which has the all-$0$ and all-$1$ configurations as fixed points, thinking of something similar to Toom's rule or an Ising-like majority rule. Consider a perturbation of such a cellular automaton where all the transition probabilities are changed up to some small $\epsilon$. Evolving with the perturbed cellular automaton from time $0$ in the all-$0$ (all-$1$) configuration to time $t$, say that a logical fault occurred if running the unperturbed cellular automaton after time $t$ does not eventually converge to the all-$0$ (all-$1$) state.

Question: Is there some cellular automaton with a proven upper bound of $c_0 t(\frac{\epsilon}{\epsilon_0})^{(\frac{L}{L_0})^2}$ of the probability of a logical fault, for all $\epsilon$-perturbations?

I'm not too attached to my way of defining the logical fault as above. For example, one might also simply use a global majority vote to decide whether a fault happened. Or one might look at a single site and bound its probability of being in the $0$ state ($1$ state) by something like $c_1\epsilon + c_0 t(\frac{\epsilon}{\epsilon_0})^{(\frac{L}{L_0})^2}$. Or, one could look at the global stochastic matrix corresponding one time step of the perturbed cellular automaton, and assert that the gap between the two highest-magnitude eigenvalues scales like $e^{-L^2}$. Feel free to answer the question for any definition that seems most natural to you.

In Gacs proof of Toom's rule fault tolerance, the scaling seems to be like $e^{-L}$ instead of $e^{-L^2}$. I assume the same is true for Tooms original proof. (Bonus question: Does anyone know how to access the english version of Toom's original paper, "Stable and Attractive Trajectories in Multicomponent Systems"? His website seems to be down now.) I believe this might be due to the fact that on a finite torus non-simply connected configurations do not converge to all-$0$ or all-$1$. Generating a non-simply connected loop of $1$'s in a background of $0$'s only requires $O(L)$ local faults.

Intuitively, I would expect a $e^{-L^2}$ scaling, since flipping from all-$0$ to all-$1$ means having a temporal domain wall in spacetime, which requires $O(L^2)$ local faults if every cluster of errors is fixed in linear time in the size of the cluster. So the probability for such a domain wall scales like $\epsilon^{L^2}$. The number of such domain walls on the other hand only scales like $t(\frac{1}{\epsilon_0})^{L^2}$. Does anyone agree or disagree with this intuition? Are there any insights from numerical experiments on this?

Answer 1

Intuitively, I would expect a $e^{-L^2}$ scaling, since flipping from all-$0$ to all-$1$ means having a temporal domain wall in spacetime, which requires $O(L^2)$ local faults if every cluster of errors is fixed in linear time in the size of the cluster. So the probability for such a domain wall scales like $\epsilon^{L^2}$. The number of such domain walls on the other hand only scales like $t(\frac{1}{\epsilon_0})^{L^2}$. Does anyone agree or disagree with this intuition?

I think I do disagree.

Consider a deterministic Toom-type CA rule with the property that clusters of cells in one state surrounded on all sides by cells in the other state cannot expand outside some finite bounding region, and must shrink and eventually disappear unless this bounding region wraps around the torus.

For example, for Toom's original rule, one such bounding region consists of all cells that share either a row or a column with a cell in the cluster. This implies that if the cells in at least one whole column and at least one whole row of the lattice are all in the same state $a \in \{0, 1\}$, then all cells will eventually converge to state $a$ under the (unperturbed) rule.

In particular, note that flipping the states of all cells in one row and one column of an $L \times L$ lattice requires only $O(L)$ state changes, and thus its probability of happening under the perturbed rule should scale with $e^{-L}$. And once such a flip happens, the entire lattice will (at least under the unperturbed rule) eventually flip.

Furthermore, I conjecture that this is in fact a general property of bistable CA rules like these: on an $L \times L$ lattice there are always configurations of $O(L)$ cells that, if all flipped to the same state, will cause the entire lattice to flip to that state in $O(L)$ time steps. Typically all that's necessary is for the configuration to wrap around the toroidal lattice in two different directions, so that the remaining cells outside the configuration do not connect around the torus.