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 are integers modulo some prime p. We consider the asymptotic behavior of the line complexity sequence alpha(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 polynomial T (x) = c(0) + c(1)x + ... + c(n)x(n) with c(0), c(n) not equal 0, we construct odd and even parts of the polynomial from the strings 0c(1)c(3)c(5) ... c(1+ 2left perpendicular(n-1)/2right perpendicular) and c(0)c(2)c(4) ... c(2left perpendicular) (n/2) (right perpendicular), respectively. We prove that alpha(T) (k) satisfies recursions of a specific form if the odd and even parts of T are relatively prime. We also define the order of such a recursion and 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 consider an abstract generating function phi(z) = Sigma(infinity)(k=1) alpha(k)z(k) which satisfies a functional equation relating phi(z) and phi(z(p)). We show that there is a continuous, piecewise quadratic function f on [1/p, 1] for which lim(k -> 8)(alpha(k)/k(2) - f (p(-< logpk >))) = 0 (here < y > = y - left perpendicular y right perpendicular. We use this result to show that for certain positive integer sequences s(k) (x) -> infinity with a parameter x is an element of [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.