The structure of translational tilings

Abstract: Let $F$ be a finite subset of an additive group $G$, and let $E$ be a subset of $G$. A (translational) tiling of $E$ by $F$ is a partition of $E$ into disjoint translates $a+F, a \in A$ of $F$. The periodic tiling conjecture asserts that if a periodic subset $E$ of $G$ can be tiled by $F$, then it can in fact be tiled periodically; among other things, this implies that the question of whether $E$ is tileable by $F$ at all is logically (or algorithmically) decidable. This conjecture was established in the two-dimensional case $G = {\bf Z}^2$ by Bhattacharya by ergodic theory methods; we present a new and more quantitative proof of this fact, based on a new structural theorem for translational tilings. On the other hand, we show that for higher dimensional groups the periodic tiling conjecture can fail if one uses two tiles $F_1,F_2$ instead of one; indeed, the tiling problem can now become undecidable. This is established by developing a "tiling language" that can encode arbitrary Turing machines.

This is joint work with Rachel Greenfeld.

analysis of PDEsclassical analysis and ODEsfunctional analysis

Audience: researchers in the topic

OARS Online Analysis Research Seminar

Series comments: Visit our homepage for further information