Abstract :
[en] Nivat's conjecture is about the link between the pure periodicity of a subset M of Z^2, i.e., invariance under translation by a fixed vector, and some upper bound on the function counting the number of different rectangular blocks occurring in $M$. Attempts to solve this conjecture have been considered during the last fifteen years. Let d>1. A legitimate extension to a multidimensional setting of the notion of periodicity is to consider sets of Z^d definable by a first order formula in the Presburger arithmetic <Z;<,+>. With this latter notion and using a powerful criterion due to Muchnik, we solve an analogue of Nivat's conjecture and characterize sets of Z^d definable in <Z;<,+> in terms of some functions counting recurrent blocks, that is, blocks occurring infinitely often.
Scopus citations®
without self-citations
10