Periodicity and local complexity

AbstractWe consider the complexity of bi-infinite words in one and two dimensions. A result of Morse and Hedlund in one dimension states that if the complexity, pξ(n), of a word satisfies pξ(n)⩽n for some n, then the word ξ is periodic. The corresponding question in two dimensions (whether pξ(m,n)⩽mn implies that ξ is periodic) is known as the Nivat conjecture. In this paper, we strengthen the one-dimensional result of Morse and Hedlund and prove a weak form of the Nivat conjecture, namely that if for a bi-infinite two-dimensional word ξ, pξ(m,n)⩽mn/16 then ξ is periodic