Complexity of Short Rectangles and Periodicity

The Morse-Hedlund Theorem states that a bi-infinite sequence eta in a finite alphabet is periodic if and only if there exists n is an element of N such that the block complexity function P-eta(n) satisfies P-eta(n) \u3c= n. In dimension two, Nivat conjectured that if there exist n, k is an element of N such that the n x k rectangular complexity P-eta(n, k) satisfies P-eta(n, k) \u3c= nk, then eta is periodic. Sander and Tijdeman showed that this holds for k \u3c= 2. We generalize their result, showing that Nivat\u27s Conjecture holds for k \u3c= 3. The method involves translating the combinatorial problem to a question about the nonexpansive subspaces of a certain Z(2) dynamical system, and then analyzing the resulting system. (C) 2015 Elsevier Ltd. All rights reserved