Periodicity and decidability of translational tilings by rational polygonal sets

Abstract

The periodic tiling conjecture asserts that if a region $\Sigma \subset {\mathbb{R}}^d$ tiles ${\mathbb{R}}^d$ by translations then it admits at least one fully periodic tiling. This conjecture is known to hold in $\mathbb{R}$, and recently it was disproved in sufficiently high dimensions. In this paper, we study the periodic tiling conjecture for polygonal sets: bounded open sets in ${\mathbb{R}}^2$ whose boundary is a finite union of line segments. We prove the periodic tiling conjecture for any polygonal tile whose vertices are rational. As a corollary of our argument, we also obtain the decidability of tilings by rational polygonal sets. Moreover, we prove that any translational tiling by a rational polygonal tile is weakly-periodic, i.e., can be partitioned into finitely many singly-periodic pieces.

15 pages, 6 figures