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
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references