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 defined by s(?)=(?+1)modq, ??Q. In this work we study the following dynamic F on Q Z2. For xQZ2 we define 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 xQZ2, such that {vZ2:xv?0} is finite we prove that there exists a finite 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 finite 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 ynQZ2 such that |{vZ2:ynv?0}|=O(k12+...+kn2) and the period of the vertex (0,0) is p·lcm{k1,...,kn}, for some even integer p. © 2004 Elsevier B.V. All rights reserved.