Expansivity and Periodicity in Algebraic Subshifts

Abstract

<p>A d-dimensional configuration c : Zd −→ A is a coloring of the d-dimensional infinite grid by elements of a finite alphabet A ⊆ Z. The configuration c has an annihilator if a non-trivial linear combination of finitely many translations of c is the zero configuration. Writing c as a d-variate formal power series, the annihilator is conveniently expressed as a d-variate Laurent polynomial f whose formal product with c is the zero power series. More generally, if the formal product is a strongly periodic configuration, we call the polynomial f a periodizer of c. A common annihilator (periodizer) of a set of configurations is called an annihilator (periodizer, respectively) of the set. In particular, we consider annihilators and periodizers of d-dimensional subshifts, that is, sets of configurations defined by disallowing some local patterns. We show that a (d −1)-dimensional linear subspace S ⊆ Rd is expansive for a subshift if the subshift has a periodizer whose support contains exactly one element of S. As a subshift is known to be finite if all (d − 1)-dimensional subspaces are expansive, we obtain a simple necessary condition on the periodizers that guarantees finiteness of a subshift or, equivalently, strong periodicity of a configuration. We provide examples in terms of tilings of Zd by translations of a single tile. <br></p><p>Keywords Symbolic dynamics · Annihilator · Periodicity · Expansivity · Golomb-Welch conjecture · Periodic tiling problem</p>