Complexity of short rectangles and periodicity

DOI10.1016/J.EJC.2015.10.003zbMATH Open1327.05004arXiv1307.0098OpenAlexW1918855253MaRDI QIDQ896072FDOQ896072

Authors: Van Cyr, Bryna Kra 

Publication date: 11 December 2015

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

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.

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

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
• scientific article; zbMATH DE number 1400043

zbMATH Keywords

Morse-Hedlund theoremNivat's conjecture

Mathematics Subject Classification ID

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

Cites Work

• Expansive Subdynamics
• Title not available (Why is that?)
• Tilings and rotations on the torus: A two-dimensional generalization of Sturmian sequences
• On a conjecture on bidimensional words.
• Periodicity and local complexity
• Multidimensional extension of the Morse-Hedlund theorem
• The complexity of functions on lattices
• Nonexpansive $\mathbb {Z}^2$-subdynamics and Nivat’s Conjecture
• Subword complexity and periodicity in two or more dimensions
• The rectangle complexity of functions on two-dimensional lattices

Cited In (11)

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

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)