Complexity of short rectangles and periodicity

Van Cyr; Bryna Kra

doi:10.1016/j.ejc.2015.10.003

Complexity of short rectangles and periodicity

Van Cyr, Bryna Kra

Mathematics

Research output: Contribution to journal › Article › peer-review

9 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	146-173
Number of pages	28
Journal	European Journal of Combinatorics
Volume	52
DOIs	https://doi.org/10.1016/j.ejc.2015.10.003
State	Published - Feb 1 2016

Funding

The authors thank the Institute Henri Poincar\u00E9 for hospitality while part of this work was completed. The second author was partially supported by NSF grant 1500670 .

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2015.10.003

Cite this

@article{a8cb38a113b547288722eb8b90bdec2a,

title = "Complexity of short rectangles and periodicity",

abstract = "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.",

author = "Van Cyr and Bryna Kra",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier Ltd.",

year = "2016",

month = feb,

day = "1",

doi = "10.1016/j.ejc.2015.10.003",

language = "English (US)",

volume = "52",

pages = "146--173",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

}

TY - JOUR

T1 - Complexity of short rectangles and periodicity

AU - Cyr, Van

AU - Kra, Bryna

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

SN - 0195-6698

VL - 52

SP - 146

EP - 173

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

ER -

Complexity of short rectangles and periodicity

Abstract

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this