TY - JOUR

T1 - Complexity of short rectangles and periodicity

AU - Cyr, Van

AU - Kra, Bryna

N1 - Funding Information:
The authors thank the Institute Henri Poincaré for hospitality while part of this work was completed. The second author was partially supported by NSF grant 1500670 .
Publisher Copyright:
© 2015 Elsevier Ltd.

PY - 2016/2/1

Y1 - 2016/2/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84945920747&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84945920747&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2015.10.003

DO - 10.1016/j.ejc.2015.10.003

M3 - Article

AN - SCOPUS:84945920747

VL - 52

SP - 146

EP - 173

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

ER -