The rectangle complexity of functions on two-dimensional lattices

AbstractLet X be a non-empty set. Let f:Z2→X. All vectors which occur have integer coefficients, and for a→=(a1,a2), b→=(b1,b2) we write a→⩽b→ or a→<b→ if aj⩽bj or aj<bj for j=1,2, respectively. Let b→>0. A b→-block is a set of the form Bb→(c→)≔{x→∈Z2|c→⩽x→<c→+b→}. A b→-pattern is the restriction of f to some b→-block. The total number of distinct b→-patterns is called the b→-complexity of f. A conjecture of the authors implies that f is periodic if there is a b→>0 such that the b→-complexity of f does not exceed b1b2. In this paper, we prove the statement for b→=(n,2) where n is any positive integer