Paper detail

Complexity of short rectangles and periodicity

The Morse-Hedlund Theorem states that a bi-infinite sequence $η$ in a finite alphabet is periodic if and only if there exists $n\in\N$ such that the block complexity function $P_η(n)$ satisfies $P_η(n)\leq n$. In dimension two, Nivat conjectured that if there exist $n,k\in\N$ such that the $n\times k$ rectangular complexity $P_η(n,k)$ satisfies $P_η(n,k)\leq nk$, then $η$ is periodic. Sander and Tijdeman showed that this holds for $k\leq2$. We generalize their result, showing that Nivat's Conjecture holds for $k\leq3$. The method involves translating the combinatorial problem to a question about the nonexpansive subspaces of a certain $\ZZ$ dynamical system, and then analyzing the resulting system.