Complexity of short rectangles and periodicity

Abstract

The Morse-Hedlund Theorem states that a bi-infinite sequence $\eta$ in a finite alphabet is periodic if and only if there exists $n\in \mathbb{N}$ such that the block complexity function $P_{\eta }(n)$ satisfies $P_{\eta }(n)\le n$. In dimension two, Nivat conjectured that if there exist $n,k\in \mathbb{N}$ such that the $n\times k$ rectangular complexity $P_{\eta }(n,k)$ satisfies $P_{\eta }(n,k)\le nk$, then $\eta$ is periodic. Sander and Tijdeman showed that this holds for $k\le 2$. We generalize their result, showing that Nivat's Conjecture holds for $k\le 3$. 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.

Cited by in corpus (1)

• Complexity and directional entropy in two dimensions