Dynamic of cyclic automata over <f>Z2</f>

Let <f>K</f> be the two-dimensional grid. Let <f>q</f> be an integer greater than 1 and let <f>Q={0,…,q-1}</f>. Let <f>s : Q→Q</f> be defined by <f>s(α)=(α+1) mod q</f>, <f>∀α ∈ Q</f>.In this work we study the following dynamic <f>F</f> on <f>QZ2</f>. For <f>x ∈ QZ2</f> we define <f>Fv(x)=s(xv)</f> if the state <f>s(xv)</f> appears in one of the four neighbors of <f>v</f> in <f>K</f> and <f>Fv(x)=xv</f> otherwise.For <f>x ∈ QZ2</f>, such that <f>{v∈Z2 : xv ≠ 0}</f> is finite we prove that there exists a finite family of cycles such that the period of every vertex of <f>K</f> 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 <f>n⩾1</f> and every collection <f>k1,…,kn</f> of non-negative integers there exists <f>yn ∈ QZ2</f> such that <f>|{v∈Z2 : ynv ≠ 0}| = O(k12+⋯+kn2)</f> and the period of the vertex (0,0) is <f>p·lcm{k1,…,kn}</f>, for some even integer <f>p</f>. [Copyright &y& Elsevier]