Complexity of short rectangles and periodicity

DOI10.1016/J.EJC.2015.10.003MaRDI QIDQ896072zbMATH OpenOpenAlexFDO

Authors Van Cyr, Bryna Kra

Publication date 11 December 2015

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.0098

zbMATH Keywords

Morse-Hedlund theoremNivat's conjecture

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics on words (68R15)

Abstract: The Morse-Hedlund Theorem states that a bi-infinite sequence $eta$ in a finite alphabet is periodic if and only if there exists $ninN$ such that the block complexity function $P_{e}ta(n)$ satisfies $P_{e}ta(n)leqn$. In dimension two, Nivat conjectured that if there exist $n,kinN$ such that the $nimesk$ rectangular complexity $P_{eta}(n,k)$ satisfies $P_{eta}(n,k)leqnk$, then $eta$ is periodic. Sander and Tijdeman showed that this holds for $kleq2$. We generalize their result, showing that Nivat's Conjecture holds for $kleq3$. The method involves translating the combinatorial problem to a question about the nonexpansive subspaces of a certain $$ dynamical system, and then analyzing the resulting system.

Recommendations

• Nonexpansive \(\mathbb{Z}^{2}\)-subdynamics and Nivat's conjecture
• Periodicity and local complexity
• Nivat's conjecture holds for sums of two periodic configurations
• An alphabetical approach to Nivat's conjecture
• Publication:4939596

Cites work

• scientific article; zbMATH DE number 3602448 (Why is no real title available?)
• Expansive Subdynamics
• Multidimensional extension of the Morse-Hedlund theorem
• Nonexpansive \(\mathbb{Z}^{2}\)-subdynamics and Nivat's conjecture
• On a conjecture on bidimensional words.
• Periodicity and local complexity
• Subword complexity and periodicity in two or more dimensions
• The complexity of functions on lattices
• The rectangle complexity of functions on two-dimensional lattices
• Tilings and rotations on the torus: A two-dimensional generalization of Sturmian sequences

Cited in

(13)

• An alphabetical approach to Nivat's conjecture
• An algebraic geometric approach to multidimensional words
• Nivat's conjecture holds for sums of two periodic configurations
• On periodic decompositions, one-sided nonexpansive directions and Nivat's conjecture
• Nivat's conjecture and pattern complexity in algebraic subshifts
• The rectangle complexity of functions on two-dimensional lattices
• Multidimensional extension of the Morse-Hedlund theorem
• On a group theoretic generalization of the Morse-Hedlund theorem
• The complexity of functions on lattices
• Nonexpansive \(\mathbb{Z}^{2}\)-subdynamics and Nivat's conjecture
• Periodicity and local complexity
• Complexity and directional entropy in two dimensions
• Low complexity functions and convex sets in \(\mathbb{Z}^k\)

This page was built for publication: Complexity of short rectangles and periodicity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896072)