Periodicity and decidability of tilings of ${\mathbb{Z}}^2$

Abstract

We prove that any finite set $F\subset {\mathbb{Z}}^2$ that tiles ${\mathbb{Z}}^2$ by translations also admits a periodic tiling. As a consequence, the problem whether a given finite set $F$ tiles ${\mathbb{Z}}^2$ is decidable.