Complexity of short rectangles and periodicity

2013/06/29 by Cyr, Van, Kra, Bryna
#37B10 #37B50 (primary) #68R15 #Dynamical Systems (math.DS) #FOS: Mathematics

paper · doi:10.48550/arxiv.1307.0098

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 \ZZ dynamical system, and then analyzing the resulting system.

Related

• Nonexpansive Z² subdynamics and Nivat's conjecture
• Multidimensional extension of the Morse--Hedlund theorem
• Nivat's conjecture holds for sums of two periodic configurations
• The periodic complexity function of the Thue-Morse word, the Rudin-Shapiro word, and the period-doubling word
• Abelian Nivat's conjecture for non-rectangular patterns