Вы здесь

An Algebraic Geometric Approach to Multidimensional Symbolic Dynamics

Дата записи:
Дата публикации:
Код для блога:

We study low complexity multidimensional words and subshifts using tools of algebraic geometry. The low complexity assumption is that, for some finite shape D, the word or the subshift has at most |D| distinct patterns of shape D. We express words as multivariate formal power series over integers and notice that the low complexity assumption implies that there is an annihilating polynomial: a polynomial whose formal product with the power series is zero. We prove that the word must then be a sum of periodic words over integers, possibly with unbounded values. As a specific application of the method we obtain an asymptotic version of the well-known Nivat's conjecture: we can show that a two-dimensional word that has low complexity with respect to arbitrarily large rectangles D must be periodic.