  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_1c_3c_5...$ and $c_0c_2c_4...$, 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
$\phi(z)=\sum_{k=1}^\infty\alpha(k)z^k$ which satisfies a general functional
equation relating $\phi(z)$ and $\phi(z^p)$ for some prime $p$. We show that
there is a continuous, piecewise quadratic function $f$ on $[1/p, 1]$ for which
$\lim_{k\to\infty}(\alpha(k)/k^2 - f(p^{-\langle\log_p k\rangle})) = 0$, where
$\langle y\rangle$ denotes the fractional part of $y$. We use this result to
show that for certain positive integer sequences $s_k\to\infty$ with a
parameter $x\in [1/p,1]$, the ratio $\alpha(s_k(x))/s_k(x)^2$ tends to $f(x)$,
and that the limit superior and inferior of $\alpha(k)/k^2$ are given by the
extremal values of $f$.
