Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653351 | European Journal of Combinatorics | 2016 | 28 Pages |
Abstract
The Morse–Hedlund Theorem states that a bi-infinite sequence ηη in a finite alphabet is periodic if and only if there exists n∈Nn∈N such that the block complexity function Pη(n)Pη(n) satisfies Pη(n)≤nPη(n)≤n. In dimension two, Nivat conjectured that if there exist n,k∈Nn,k∈N such that the n×kn×k rectangular complexity Pη(n,k)Pη(n,k) satisfies Pη(n,k)≤nkPη(n,k)≤nk, then ηη is periodic. Sander and Tijdeman showed that this holds for k≤2k≤2. We generalize their result, showing that Nivat’s Conjecture holds for k≤3k≤3. The method involves translating the combinatorial problem to a question about the nonexpansive subspaces of a certain Z2Z2 dynamical system, and then analyzing the resulting system.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Van Cyr, Bryna Kra,