Multidimensional extension of the Morse-Hedlund theorem (Q691591)

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)].