Existence of a low-growth surjective cellular automaton

About 20 years old · traced to

Let ΣN\Sigma_N be the space of doubly infinite sequences over an alphabet of NN symbols, let SNS_N be its shift map, and let f:ΣN→ΣNf:\Sigma_N\to\Sigma_N be a surjective one-dimensional cellular automaton. For each kk, let Pk(SN)P_k(S_N) be the set of points fixed by SNkS_N^k, let P=∣Per⁡(f∣Pk(SN))∣P=|\operatorname{Per}(f|P_k(S_N))| be the number of points in Pk(SN)P_k(S_N) that are also periodic under ff, and define

νk(f,SN)=P1/k,ν(f,SN)=lim sup⁡kνk(f,SN).\nu_k(f,S_N)=P^{1/k},\qquad \nu(f,S_N)=\limsup_k\nu_k(f,S_N).

Low-growth existence conjecture. There exists N>1N>1 and a surjective cellular automaton ff on NN symbols such that ν(f,SN)<N\nu(f,S_N)<N. The surrounding discussion poses related quantitative questions about lower bounds for ν(f,SN)\nu(f,S_N), while this existence claim is presented without a supplied resolution status.

References

Primary source

Mike Boyle and Bryant Lee, “Jointly periodic points in cellular automata: computer explorations and conjectures”, arXiv:math/0607178 (2006).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.