On pre-periods of discrete influence systems (Q1087853)

We investigate sequences \(\{y_ k\}^{\infty}_{k=0}\) of vectors defined by \(y_{k+1}=f(Ay_ k)\) where A is a symmetric matrix and f is a gradient (or subgradient) of a convex function. Special transformations of this type are often considered in connection with cellular automata. We proved earlier [Discrete Appl. Math. 13, 27-32 (1986; Zbl 0588.93048)] that the only possible periods of such a sequence are 1 or 2. Here we give upper bounds on the number of steps before a period in cases \(f(x)=(f_ 1(x_ 1),...,f_ n(x_ n))\) where the \(f_ i's\) are threshold, multi-threshold or, if the \(x_ i's\) are vectors of lower dimension, cyclically monotone functions. The bound is tight for threshold functions.