Aperiodic points in ${\mathbb{Z}}^2$-subshifts

Abstract

We consider the structure of aperiodic points in ${\mathbb{Z}}^2$-subshifts, and in particular the positions at which they fail to be periodic. We prove that if a ${\mathbb{Z}}^2$-subshift contains points whose smallest period is arbitrarily large, then it contains an aperiodic point. This lets us characterise the computational difficulty of deciding if an ${\mathbb{Z}}^2$-subshift of finite type contains an aperiodic point. Another consequence is that ${\mathbb{Z}}^2$-subshifts with no aperiodic point have a very strong dynamical structure and are almost topologically conjugate to some $\mathbb{Z}$-subshift. Finally, we use this result to characterize sets of possible slopes of periodicity for ${\mathbb{Z}}^3$-subshifts of finite type.

13 pages, accepted to ICALP 2018