Mathematics – Combinatorics
Scientific paper
2011-09-27
Mathematics
Combinatorics
Scientific paper
Nivat's conjecture is about the link between the pure periodicity of a subset $M$ of $\ZZ^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\ge 2$. A legitimate extension to a multidimensional setting of the notion of periodicity is to consider sets of $\ZZ^d$ definable by a first order formula in the Presburger arithmetic $<\ZZ;<,+>$. With this latter notion and using a powerful criterion due to Muchnik, we solve an analogue of Nivat's conjecture and characterize sets of $\ZZ^d$ definable in $<\ZZ;<,+>$ in terms of some functions counting recurrent blocks, that is, blocks occurring infinitely often.
Durand Fabien
Rigo Michel
No associations
LandOfFree
Some answer to Nivat's conjecture: A characterization of periodicity with respect to block complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Some answer to Nivat's conjecture: A characterization of periodicity with respect to block complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Some answer to Nivat's conjecture: A characterization of periodicity with respect to block complexity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-62184