Nivat's conjecture is an open problem in symbolic dynamics and combinatorics on words concerning the relationship between local pattern complexity and global periodicity in two-dimensional configurations. Proposed by French computer scientist Maurice Nivat at the 1997 International Colloquium on Automata, Languages and Programming (ICALP), it is a two-dimensional analogue of the Morse–Hedlund theorem.
Statement Let be a finite alphabet and let be a two-dimensional configuration. For positive integers and , let be the number of distinct rectangular patterns that occur in . The configuration is called periodic if there is a nonzero vector such that for every .
Nivat's conjecture states that if there exist positive integers such that
then is periodic.
Partial results Several weaker forms and special cases of the conjecture have been proved. Quas and Zamboni proved periodicity under the stronger bound . Cyr and Kra later proved periodicity under the bound .
For rectangles of fixed small height, Sander and Tijdeman proved the conjecture for height at most 2, and Cyr and Kra extended this to height at most 3. Kari and Moutot proved that the conjecture holds for uniformly recurrent configurations.
See also Complexity function Morse–Hedlund theorem Symbolic dynamics Combinatorics on words
References