×

Jointly periodic points in cellular automata: computer explorations and conjectures. (English) Zbl 1147.37009

Let \(Z\) denote the integers, let \(A\) be an ‘alphabet’ of \(N\) letters, and let \(\Sigma_N=A^Z\) be the Cantor space of all bi-infinite sequences of symbols in \(A\). Let \(S_N:\Sigma_N\rightarrow\Sigma_N\) be the ‘shift’ map. A cellular automaton (CA) is a continuous function \(f:\Sigma_N\rightarrow\Sigma_N\) which commutes with \(S_N\); equivalently, \(f\) is defined by applying a ‘local rule’ at each index in \(Z\). We say \(f\) is surjective if \(f(\Sigma_N)=\Sigma_N\).
A sequence \(x\in\Sigma_N\) is jointly periodic if there exist integers \(p,q\geq 0\) such that \(S_N^p(x)=x\) and \(f^q(x)=x\). This paper is an investigation of the following
Density Conjecture. For any surjective CA \(f\), the set of jointly periodic points is dense in \(\Sigma_N\).
This conjecture is known to be true for surjective right-closing CA [M. Boyle and B. Kitchens, Indag. Math., New Ser. 10, No. 4, 483–493 (1999; Zbl 1024.37007)], or for surjective CAs with equicontinuous points [F. Blanchard and P. Tisseur, Ann. Inst. Henri PoincarĂ©, Probab. Stat. 36, No. 5, 569–582 (2000; Zbl 0964.37011)], and has also previously been investigated by F. Blanchard [“Dense points in cellular automata” (unpublished, 2000)].
To get some insight into the Density Conjecture, the authors attempt to asymptotically measure the ‘size’ the set of jointly periodic points in \(\Sigma_N\). To be precise, for any \(k\geq 0\), let \(P_k(S_N)\) be the set of all sequences \(x\in\Sigma_N\) with \(S_N^k(x)=x\); this is a set of cardinality \(N^k\). Let \(p_k\) be the number of elements of \(P_k(S_N)\) which are also periodic for \(f\); hence \(p_k\leq N^k\). The authors define \(\nu_k(f)=p_k^{1/k}\); hence \(\nu_k(f)\leq N\). Let \(\nu(f)=\limsup_{k\rightarrow \infty} \nu_k(f)\). Intuitively, if \(\nu(f)\approx N\), then \(p_k \approx N^k\) for all large \(k\), which means that a ‘large proportion’ of the elements of \(P_k(S_N)\) are \(f\)-periodic – this would seem to support the Density Conjecture. Thus, the authors ask the following questions:
For all surjective CAs \(f\) on \(\Sigma_N\),
(a) Is \(\nu(f)\geq \sqrt{N}\) always?
(b) Is \(\nu(f)> 1\) always?
(c) Is there any \(f\) such that \(\nu(f) < N\)?
If the Density Conjecture is false, then the answer to question (c) is ‘yes’. (However, if the Density Conjecture is true, then the answer to (c) could still be ‘yes’).
Section 3 of the paper discusses four conditions under which \(\nu(f)\) is large:
(1) If there is a subshift of \(\Sigma_N\) which is fixed by \(f\), and has \(S_N\)-entropy close to \(\log(N)\), then \(\nu(f)\approx N\).
(2) If \(f\) is a surjective linear CA, then \(\nu(f)= N\) (Proposition 3.4).
(3) If \(f\) has equicontinuous points, then \(\nu(f)= N\) [F. Blanchard and P. Tisseur (loc. cit.)].
(4) If the polynomial representation of \(f\) has certain nice properties, then \(\nu(f)= N\) [F. Rhodes, Dynamical systems, Proc. Spec. Year, College Park/Maryland, Lect. Notes Math. 1342, 638–644 (1988; Zbl 0661.54039)].
In particular, condition #1 is used to prove an interesting result (Theorem 3.2): For any surjective CA \(f\) on \(\Sigma_N\), and any \(\varepsilon>0\), there is an invertible CA \(\varphi\) such that \(\nu(\varphi f)>N-\varepsilon\). This means, roughly, that there is no property of CA which can be used to settle question (c), and which is invariant under composition with invertible CA.
Section 4 of the paper then summarizes the results of some very extensive computer experiments conducted by the authors, which strongly support the Density Conjecture, and suggest an affirmative answer to questions (a,b,c) above.
For example, these experiments prove (by simple exhaustion of all possible cases) Proposition 5.1, which states: For every span-4 surjective CA, the set of jointly periodic points is at least 13-dense. (Here, span-4 means the local rule depends on only 4 adjacent letters (e.g. \(x_{-1},x_0,x_1,x_2\)) and depends nontrivially on the leftmost (\(x_{-1}\)) and rightmost (\(x_2\)) of these. 13-dense means that every word of length 13 in \(\Sigma_N\) appears in some jointly-periodic sequence.)
The data from these experiments is summarized in 33 tables which do not appear in the printed form of the paper, but which are available online from the Experimental Mathematics journal website, and also on Boyle’s own webpage.

MSC:

37B15 Dynamical aspects of cellular automata
37B10 Symbolic dynamics
54H20 Topological dynamics (MSC2010)
37-04 Software, source code, etc. for problems pertaining to dynamical systems and ergodic theory
PDF BibTeX XML Cite
Full Text: DOI arXiv Euclid