Multidimensional extension of the Morse-Hedlund theorem

DOI10.1016/J.EJC.2012.08.003zbMATH Open1338.68227arXiv1109.5801OpenAlexW1999186591MaRDI QIDQ691591FDOQ691591

Authors: Fabien Durand, Michel Rigo 

Publication date: 3 December 2012

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

Abstract: A celebrated result of Morse and Hedlund, stated in 1938, asserts that a sequence $x$ over a finite alphabet is ultimately periodic if and only if, for some $n$, the number of different factors of length $n$ appearing in $x$ is less than $n+1$. Attempts to extend this fundamental result, for example, to higher dimensions, have been considered during the last fifteen years. Let $dge2$. A legitimate extension to a multidimensional setting of the notion of periodicity is to consider sets of $$ definable by a first order formula in the Presburger arithmetic $$. With this latter notion and using a powerful criterion due to Muchnik, we exhibit a complete extension of the Morse--Hedlund theorem to an arbitrary dimension $d$ and characterize sets of $$ definable in $$ in terms of some functions counting recurrent blocks, that is, blocks occurring infinitely often.

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

Recommendations

• Subword complexity and periodicity in two or more dimensions
• Complexity of short rectangles and periodicity
• Periodicity and local complexity
• Low complexity functions and convex sets in \(\mathbb{Z}^k\)
• Double sequences of low complexity

zbMATH Keywords

Presburger arithmeticMorse-Hedlund theoremrecurrent blocksultimate periodicity

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Combinatorics on words (68R15) First-order arithmetic and fragments (03F30)

Cited In (13)

• Aperiodic two-dimensional words of small abelian complexity
• Nonexpansive \(\mathbb{Z}^{2}\)-subdynamics and Nivat's conjecture
• A more reasonable proof of Cobham's theorem
• Low complexity functions and convex sets in \(\mathbb{Z}^k\)
• Higher order multi-dimensional extensions of Cesàro theorem
• Multidimensional generalizations of Jacobi's envelope theorem
• Double sequences of low complexity
• On periodic decompositions, one-sided nonexpansive directions and Nivat's conjecture
• An alphabetical approach to Nivat's conjecture
• Recurrence along directions in multidimensional words
• Complexity of short rectangles and periodicity
• On a group theoretic generalization of the Morse-Hedlund theorem
• On the Hans Lewy Extension Phenomenon in Higher Codimension

This page was built for publication: Multidimensional extension of the Morse-Hedlund theorem

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