2013/04/16 by Kevin Garbe, Garbe, Kevin
Computer Science · Mathematics · #Cellular Automata and Applications #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #math.CO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1304.4635
arxiv created 2013/04/16 · openalex publication_date 2013/04/16 · arxiv updated 2013/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We examine the behavior of the coefficients of powers of polynomials over a finite field of prime order. Extending the work of Allouche-Berthe, 1997, we study a(n), the number of occurring strings of length n among coefficients of any power of a polynomial f reduced modulo a prime p. The sequence of line complexity a(n) is p-regular in the sense of Allouche-Shalit. For f=1+x and general p, we derive a recursion relation for a(n) then find a new formula for the generating function for a(n). We use the generating function to compute the asymptotics of a(n)/n2 as n approaches infinity, which is an explicitly computable piecewise quadratic in x with n= [pm/x] and x is a real number between 1/p and 1. Analyzing other cases, we form a conjecture about the generating function for general a(n). We examine the matrix B associated with f and p used to compute the count of a coefficient, which applies to the theory of linear cellular automata and fractals. For p=2 and polynomials of small degree we compute the largest positive eigenvalue, λ, of B, related to the fractal dimension d of the corresponding fractal by d= log2(λ). We find proofs and make a number of conjectures for some bounds on λ, and upper bounds on its degree.