Wavelengths distribution of chaotic travelling waves in some cellular automata

Travelling waves (TW) solutions under the dynamics of one-dimensional infinite cellular automata (CA) exist abundantly in many cases. We show that for any permutative CA, unstable TW are dense in the space of configurations. Then, we consider the cases where the number of states is a prime number, so that the state space is a finite field K and the automata rules are linear on IM. We give an algorithm for the computation of the TW for any integer velocity of propagation larger than the interaction range. Then, we show that their wavelengths are characterized in terms of zeros of an associated family of polynomials over IM and we describe the mathematical complexity of wavelengths distributions in various linear CA laws. We also obtain some exponential lower bound for the growth of the number of waves in terms of the velocity in rule 90. (C) 2001 Published by Elsevier Science B.V.