Complexity of short rectangles and periodicity

Van Cyr, Bryna Kra

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


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

Original languageEnglish (US)
Pages (from-to)146-173
Number of pages28
JournalEuropean Journal of Combinatorics
StatePublished - Feb 1 2016

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Complexity of short rectangles and periodicity'. Together they form a unique fingerprint.

Cite this