Multidimensional extension of the Morse–Hedlund theorem

A celebrated result of Morse and Hedlund, stated in 1938, asserts that a sequence xx over a finite alphabet is ultimately periodic if and only if, for some nn, the number of different factors of length nn appearing in xx is less than n+1n+1. Attempts to extend this fundamental result, for example, to higher dimensions, have been considered during the last fifteen years. Let d≥2d≥2. A legitimate extension to a multidimensional setting of the notion of periodicity is to consider sets of ZdZd definable by a first order formula in the Presburger arithmetic 〈Z;<,+〉〈Z;<,+〉. 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 dd and characterize sets of ZdZd definable in 〈Z;<,+〉〈Z;<,+〉 in terms of some functions counting recurrent blocks, that is, blocks occurring infinitely often.