Characteristic and minimal polynomials of linear cellular automata (Q2477874): Difference between revisions

The paper considers the cellular automaton defined by Wolfram's Rule 90 given by \[ W_nx =(x_n+x_2,x_1+x_3,\ldots,x_{n-1}+x_1) \] with the components of the vector \(x\) belonging to \(\{0,1\}\) and the addition modulo 2. It is known that for cellular automata over finite fields, all forward orbits converge to a periodic cycle in finite time. The paper restates the proof that all period lengths are equal to orders of the factors of the minimal polynomial of the map. It is found a closed form expression for the minimal polynomial of Rule 90. Further connections with Rule 150 are made and data on all periods up to \(n=40\) for Rules 90 and 150 are provided.