On the order of lazy cellular automata
Pith reviewed 2026-05-18 06:20 UTC · model grok-4.3
The pith
Lazy cellular automata have order at most the number of fibers of their active pattern p, achieved exactly when p is quasi-constant.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The order of a lazy cellular automaton τ is bounded above by the cardinality of the fibers of its active transition p under the group action. This upper bound is attained when p is a quasi-constant pattern.
What carries the argument
the fibers of p under the group action on placements of the pattern, which determine how many distinct iterates the lazy update can produce
If this is right
- When the fibers of p are finite the generated semigroup under composition is finite.
- Quasi-constant patterns realize the maximum possible order among all lazy automata with a given fiber count.
- Iterates of τ can be distinguished by how they act on configurations whose active sites lie in different fibers.
- The long-term dynamics of τ consist of at most that many distinct global functions before repetition begins.
Where Pith is reading between the lines
- Choosing patterns p with successively larger but finite fiber sets yields lazy automata of arbitrary finite order.
- The result suggests that symmetry properties of the trigger pattern control the complexity of the iteration semigroup even on infinite groups.
Load-bearing premise
The fibers of p are well-defined and finite, and the lazy update commutes with shifts so that the distinct iterates are counted exactly from these fibers.
What would settle it
A lazy cellular automaton whose number of distinct iterates exceeds the number of fibers of its pattern p, or a non-quasi-constant p for which the bound is attained.
read the original abstract
We study the most elementary family of cellular automata defined over an arbitrary group universe $G$ and an alphabet $A$: the lazy cellular automata, which act as the identity on configurations in $A^G$, except when they read a unique active transition $p \in A^S$, in which case they write a fixed symbol $a \in A$. As expected, the dynamical behavior of lazy cellular automata is relatively simple, yet subtle questions arise since they completely depend on the choice of $p$ and $a$. In this paper, we investigate the order of a lazy cellular automaton $\tau : A^G \to A^G$, defined as the cardinality of the set $\{ \tau^k : k \in \mathbb{N} \}$. In particular, we establish a general upper bound for the order of $\tau$ in terms of the fibers of $p$, and we prove that this bound is attained when $p$ is a quasi-constant pattern.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies lazy cellular automata over an arbitrary group G and finite alphabet A. These maps act as the identity on A^G except when a configuration contains the unique active local pattern p in A^S, in which case they write a fixed symbol a. The order of such a map τ is defined as the cardinality of the set of its iterates {τ^k : k ∈ ℕ}. The central results are a general upper bound on this order expressed in terms of the fibers of p under the group action, together with a proof that the bound is attained precisely when p is quasi-constant.
Significance. If the derivations hold, the results give a clean, fiber-based characterization of the dynamical order for this elementary family of CA. The attainment theorem for quasi-constant patterns supplies an explicit tight case and demonstrates that the bound is sharp. This supplies a concrete, group-theoretic handle on iterate cardinality that may serve as a baseline for studying more complex shift-commuting maps.
minor comments (3)
- §2, Definition 2.3: the notation for the fiber equivalence relation induced by the group action is introduced without an explicit statement that the fibers are finite; a one-sentence remark confirming finiteness under the standing assumptions would improve readability.
- Theorem 3.4: the proof sketch refers to 'commutation of lazy update with shifts' but does not cite the precise lemma establishing that distinct fiber states determine distinct iterates; adding the lemma number would make the argument easier to follow.
- Figure 1: the caption does not indicate the group G or the specific quasi-constant pattern used in the example; adding these details would clarify the illustration of the attainment case.
Simulated Author's Rebuttal
We thank the referee for their positive summary of our work on the order of lazy cellular automata and for recommending minor revision. We appreciate the recognition that the fiber-based upper bound and the attainment result for quasi-constant patterns provide a clean group-theoretic characterization. Since the report contains no specific major comments or requested changes, we interpret the minor revision as an opportunity for any editorial polishing or minor clarifications that the editor may suggest.
Circularity Check
No significant circularity identified
full rationale
The paper defines lazy cellular automata over a group G and alphabet A, with the order of τ as the cardinality of the set of its iterates. It derives a general upper bound on this order expressed in terms of the fibers of the input pattern p under the group action, then proves attainment of the bound specifically for quasi-constant p. These steps rest on the standard definitions of the lazy update rule, shift-commuting properties of cellular automata, and finiteness of fibers, all introduced as part of the setup rather than derived from the target result. No equation or claim reduces the bound or its attainment to a tautological re-expression of the inputs by construction, and no self-citation chain or fitted parameter is invoked as load-bearing evidence. The derivation therefore supplies independent mathematical content grounded in the given assumptions.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption The configuration space is A^G equipped with the natural shift action of the group G.
Reference graph
Works this paper leans on
-
[1]
Balbi, P. P., Mattos, T., Ruivo, E.: Characterisation of the elementary cellular automata with neighbourhood priority based deterministic updates. Comun. Nonlinear Sci. Numer. Simulat. 104(2022) 106018.https://doi.org/10.1016/j.cnsns.2021.106018
-
[2]
Balbi, P. P., Mattos, T., Ruivo, E.: From Multiple to Single Updates Per Cell in Elementary Cellular Automata with Neighbourhood Based Priority. In: Das, S., Roy, S., Bhattacharjee, K. (eds) The Mathematical Artist. Emergence, Complexity and Computation45, Springer, Cham., 2022.https://doi.org/10.1007/978-3-031-03986-7_6 11
-
[3]
Castillo-Ramirez, A., Maga˜ na-Chavez, M. G., Veliz-Quintero, E.: Idempotent cellular au- tomata and their natural order,Theoretical Computer Science, 1009,https://doi.org/10. 1016/j.tcs.2024.114698
-
[4]
Castillo-Ramirez, A., Maga˜ na-Chavez, M. G., Santos Ba˜ nos, L. de los.: One-dimensional cellular automata with a unique active transition,Dynamical Systems, 1-15,https://doi. org/10.1080/14689367.2025.2487698
-
[5]
In: Gadouleau, M., Castillo-Ramirez, A
Castillo-Ramirez, A., Veliz-Quintero, E.: On the Minimal Memory Set of Cellular Automata. In: Gadouleau, M., Castillo-Ramirez, A. (eds) Cellular Automata and Discrete Complex Systems. AUTOMATA 2024. Lecture Notes in Computer Science, vol 14782. Springer, Cham, 2024.https://doi.org/10.1007/978-3-031-65887-7_7
-
[6]
Ceccherini-Silberstein, T., Coornaert, M.: Cellular Automata and Groups. 2nd Ed. Springer Monographs in Mathematics, Springer Cham, 2023.https://doi.org/10.1007/ 978-3-031-43328-3
work page 2023
-
[7]
Concha-Vega, P., Goles, E., Montealegre, P., R´ ıos-Wilson, M., & Santiva˜ nez, J.: Introducing the activity parameter for elementary cellular automata. Int. J. Mod. Phys. C33(9)(2022) 2250121.https://doi.org/10.1142/S0129183122501212
-
[8]
Fates, N.: A tutorial on elementary cellular automata with fully asynchronous updating. Nat. Comput.19(1) (2020) 179–197.https://doi.org/10.1007/s11047-020-09782-7
-
[9]
Fates, N.: Asynchronous Cellular Automata. In: Meyers, R. (eds) Encyclopedia of Complex- ity and Systems Science. Springer, Berlin, Heidelberg, 2018.https://doi.org/10.1007/ 978-3-642-27737-5_671-2
work page 2018
-
[10]
M.: The Subsemigroup Generated By the Idempotents of a Full Transformation Semigroup, J
Howie, J. M.: The Subsemigroup Generated By the Idempotents of a Full Transformation Semigroup, J. London Math. Soc.s1-41(1966) 707-716.https://doi.org/10.1112/jlms/ s1-41.1.707
-
[11]
Theoretical Computer Science334(2005) 3 – 33.https://doi.org/10.1016/j.tcs.2004.11.021
Kari, J.: Theory of cellular automata: a survey. Theoretical Computer Science334(2005) 3 – 33.https://doi.org/10.1016/j.tcs.2004.11.021
-
[12]
(1997): Languages, equicontinuity and attractors in cellular automata
K˚ urka, P. (1997): Languages, equicontinuity and attractors in cellular automata. Ergodic Theory and Dynamical Systems17(2), 417–433.https://doi.org/10.1017/ S014338579706985X
work page 1997
-
[13]
Rotman, J.: An Introduction to the Theory of Groups. 4th Ed. Springer New York, 1995
work page 1995
-
[14]
(1983): Statistical mechanics of cellular automata
Wolfram, S. (1983): Statistical mechanics of cellular automata. Reviews of Modern Physics, 55(3), 601–644. 12
work page 1983
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.