Line Complexity Asymptotics of Polynomial Cellular Automata

Cellular automata are discrete dynamical systems that consist of patterns of symbols on a grid, which change according to a locally determined transition rule. In this paper, we will consider cellular automata that arise from polynomial transition rules, where the symbols in the automaton are integers modulo some prime $p$. We are principally concerned with the asymptotic behavior of the line complexity sequence $a_T(k)$, which counts, for each $k$, the number of coefficient strings of length $k$ that occur in the automaton. We begin with the modulo $2$ case. For a given polynomial $T(x) = c_0 + c_1x + …

• c_nx^n$with$c_0,c_n\neq 0$, we construct odd and even parts of the polynomial from the strings $0c_1{c}_3{c}_5\mathrm{.}\mathrm{.}\mathrm{.}$ and $c_0{c}_2{c}_4\mathrm{.}\mathrm{.}\mathrm{.}$, respectively. We prove that for polynomials for which the odd and even parts are relatively prime, $a_T(k)$ satisfies recursions of a specific form. We also consider powers of transition rules modulo $p$, introducing a notion of the order of a recursion. We show that the property of “having a recursion of some order” is preserved when the transition rule is raised to a positive integer power. Extending to a more general setting, we investigate the asymptotics of $a_T(k)$ by considering an abstract generating function $\varphi (z)={\sum }_{k=1}^{\mathrm{\infty }}\alpha (k)z^k$ which satisfies a general functional equation relating $\varphi (z)$ and $\varphi (z^p)$ for some prime $p$. We show that there is a continuous, piecewise quadratic function $f$ on $[1\mathrm{/}p,1]$ for which ${\lim }_{k\to \mathrm{\infty }}(\alpha (k)\mathrm{/}{k}^2-f(p^{-⟨{\log }_{p}k⟩}))=0$, where $⟨y⟩$ denotes the fractional part of $y$. We use this result to show that for certain positive integer sequences $s_k\to \mathrm{\infty }$ with a parameter $x\in [1\mathrm{/}p,1]$, the ratio $\alpha (s_k(x))\mathrm{/}{s}_k(x{)}^2$ tends to $f(x)$, and that the limit superior and inferior of $\alpha (k)\mathrm{/}{k}^2$ are given by the extremal values of $f$.