Dynamic of cyclic automata over Z2

Abstract

Let K be the two-dimensional grid. Let q be an integer greater than 1 and let Q={0; : : : ; q−1}. Let s :Q → Q be de0ned by s( ) = ( + 1) mod q, ∀ ∈ Q. In this work we study the following dynamic F on QZ2 . For x ∈ QZ2 we de0ne Fv(x)=s(xv) if the state s(xv) appears in one of the four neighbors of v in K and Fv(x) = xv otherwise. For x ∈ QZ2 , such that {v ∈ Z2 : xv = 0} is 0nite we prove that there exists a 0nite family of cycles such that the period of every vertex of K divides the lcm of their lengths. This is a generalization of the same result known for 0nite graphs. Moreover, we show that this upper bound is sharp. We prove that for every n¿1 and every collection k1; : : : ; kn of non-negative integers there exists yn ∈ QZ2 such that |{v ∈ Z2 : yn v = 0}| = O(k2 1 + · · · + k2 n ) and the period of the vertex (0,0) is p · lcm{k1; : : : ; kn}, for some even integer p. c

2004 Elsevier B.V. All rights reserved