Periodic solutions of one-dimensional cellular automata with uniformly chosen random rules (Q2121743)

Cellular automata (CA) are models of synchronous computation where all the cells in a grid are updated according to the current state of the cell and its neighbors, with the latter's offsets being the same for each cell. If the grid is one-dimensional and discrete, then the space-time diagram of the evolution can be represented in the plane. The authors discuss the case in which the latter is periodic in both time and space, in which case it can be identified with a rectangular tile; the diagram is then called a periodic solution (PS). For CA having only a left and a center neighbor, the authors prove the following main theorems, stated in the introduction and proved in Section 4: \begin{itemize} \item[1.] Given positive integers \(\tau\) and \(\sigma\), let: \[ \lambda_{\tau, \sigma} = \frac{1}{\tau \sigma} \sum_{d \,|\, \gcd(\tau, \sigma)} d \cdot \varphi(d) \] where \(\varphi\) is Euler's totient function. Then the number of periodic solutions with minimal temporal period \(\tau\) and minimal spatial period \(\sigma\) for a randomly chosen CA rule on \(n\) states converges weakly, for \(n\to\infty\), to a Poisson distribution of parameter \(\lambda_{\tau,\sigma}\), and the convergence rate for total variation distance is \(O(1/n)\). \item[2.] Let \(\mathcal{S}\) be a finite set of pairs of positive integers and let: \[ \lambda_{\mathcal{S}} = \sum_{(\tau, \sigma) \in \mathcal{S}} \lambda_{\tau, \sigma} \] Then the number of periodic solutions with minimal temporal period \(\tau\) and minimal spatial period \(\sigma\) such that \( (\tau, \sigma) \in \mathcal{S} \), for a randomly chosen CA rule on \(n\) states, converges weakly, for \(n\to\infty\), to a Poisson distribution of parameter \(\lambda_{\mathcal{S}}\), and the convergence rate for total variation distance is \(O(1/n)\). \end{itemize} As a corollary, for fixed \(\sigma\), the smallest \(\tau\) for which a randomly chosen CA with \(n\) states has a periodic solution converges weakly to a nontrivial distribution. Preliminary to the proofs of the main theorems, the discussion in Section 3 gives several insights into the character of periodic solutions. The final discussion suggests possible future directions, including a relaxation of the condition that the set \(\mathcal{S}\) from Theorem 2 be finite, and an analysis of the special cases where the local rule is additive or left permutive.