Multidimensional extension of the Morse-Hedlund theorem (Q691591)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Multidimensional extension of the Morse-Hedlund theorem |
scientific article |
Statements
Multidimensional extension of the Morse-Hedlund theorem (English)
0 references
3 December 2012
0 references
A well-known theorem by \textit{M. Morse} and \textit{G. A. Hedlund} [Am. J. Math. 60, 815--866 (1938; Zbl 0019.33502); ibid. 62, 1--42 (1940; Zbl 0022.34003)] states that if \(x \in A^{\mathbb{N}}\), where \(A\) is a finite alphabet, then \(x\) is ultimately periodic if and only if there exists \(n\) such that the number of different factors of length \(n\) appearing in \(x\) is bounded from above by \(n\). A version of this theorem applies to any subset \(M\) of \(\mathbb{N}\) by considering its characteristic sequence over the alphabet \(\{0,1\}\), the ultimate periodicity of this sequence translating to \(M\) being a finite union of arithmetic progressions. In this very interesting paper, the authors provide a complete extension of this fundamental theorem to an arbitrary higher dimension \(d\), \(d \geq 2\). They also obtain a characterization of sets \(M\) in \(\mathbb{Z}^d\) defined by a first-order formula of the Presburger arithmetic \(\langle \mathbb{Z}<, + \rangle\) (this is their notion of periodicity). To do so, they estimate the number of different blocks of size \(n\) occurring infinitely often in \(M\) via the powerful criterion for definability in Presburger arithmetic due to \textit{An. A. Muchnik} [Theor. Comput. Sci. 290, No. 3, 1433--1444 (2003; Zbl 1052.68079)].
0 references
Morse-Hedlund theorem
0 references
Presburger arithmetic
0 references
ultimate periodicity
0 references
recurrent blocks
0 references