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
en_US
Patrocinador
dc.description.sponsorship
This work was partially supported by ECOS C00E03 (French–Chilean Cooperation), FONDAP on
Applied Math and Fondecyt 1010442.