Sparse maximum-period cellular automata with small directed diameter
Lizhong Chen · Zenodo (CERN European Organization for Nuclear Research) · 2026
We construct binary linear cellular automata on prescribed near-square regions of exactly N cells with maximum period 2N-1: all nonzero states form a single cycle. For every 36 ≤ N ≤ 999, exact certificates give Moore-local, null-boundary matrices using at most 2N-4 directed nonself dependencies, compared with 2N-2 for the standard bidirectional serpentine path. Each cell has at most three distinct incident cell labels, counting self-dependence once. The worst-case first nonzero influence time equals the directed diameter, which is at most H+W+2 for bounding dimensions H,W. A parameterised directed-cactus family provides explicit edge-diameter tradeoffs and two certified choices at every 37 ≤ N ≤ 999. Independently, for N ≥ 268, a uniform construction gives matrices with fewer than (2-1/150000)N-2 dependencies and diameter below 2√N under the same locality and incident-label constraints. Their influence time is N-1. We also bound short observation ranks by local input rank and give maximum-period examples with short-window linear relations. The interval 1000 ≤ N < 268 remains uncovered. This deposit contains only the PDF of manuscript v007 (44 pages), including the revised exposition, design explanations and a statement on the use of AI-assisted tools. The matching computational certificates and reproducibility package are version v012, doi:10.5281/zenodo.23583993. Its MANUSCRIPT-SHA256.json identifies this exact PDF. The paper includes complete mathematical arguments; exact finite computation and its scope are identified separately. This manuscript substantially revises and extends the earlier arXiv:2610.06983v1.