One-dimensional cellular automata with random rules: longest temporal period of a periodic solution (Q2119677)

The authors study the behavior of periodic solutions for one-dimensional one-way cellular automata (CA) for which the next state of a cell is a function of the current state and its \(r-1\) \textit{left} neighbors. By ``periodic solution'' they mean a configuration in the space-time diagram which has finite spatial period \(\sigma\) and finite temporal period \(\tau\). In particular, having fixed \(\sigma\), they study the behavior of the random variable \(X_{\sigma,n}\) defined as the maximum temporal period of a periodic solution for an \(n\)-state CA, given the spatial period \(\sigma\). The main result of the paper (Theorem 1.1) states that for \(\sigma\leq{r}\) the random variable \(X_{\sigma,n}/\sqrt{n^{\sigma}}\) converges in distribution to a nontrivial limit. The proof involves an intermediate result (Theorem 1.2) about the behavior of \(C_n/n^\sigma\), where \(C_n\) is the number of equivalence classes, modulo translations, of those initial conditions which satisfy the following two additional properties: \begin{itemize} \item[1.] They are spatially periodic of \textit{minimum} period \(\sigma\); \item[2.] The temporal evolution never reduces the minimum spatial period below \(\sigma\). \end{itemize} The arguments rely on basic results in number theory and probability theory, as well as on simple but ingenious graph-theoretic constructions. However, the proof of Theorem 1.1 relies on the independence of a certain family of random variables, which is satisfied for \(\sigma\leq{r}\) but not for \(\sigma>r\). A case for which this family is not independent is given in the Conclusions section. The authors conjecture that the main theorem remains valid for \(\sigma>r\), and support it with some numerical experiments.